Two Resolvers, Two Philosophies

Every “Arch vs Debian” piece on the internet is about package freshness, AUR convenience, or how many times you’ve had to reinstall grub. None of them are about the actual engineering decision that differentiates the two: what the dependency resolver is allowed to know, and what it’s allowed to do when it doesn’t have a clean answer.

That decision has a name. It’s the determinism/completeness tradeoff, and it’s not specific to Linux — every package manager that handles conflicts (APT, DNF, Cargo, npm, Spack) sits somewhere on this spectrum, and almost none of them tell you where.

This is a mechanism-level look at where pacman and APT sit, why they sit there, and what it actually costs you in each direction.

Dependency resolution with conflicts is NP-complete

Start from the formal model, because it explains why every resolver design is a compromise, not an oversight.

A resolution is a set of packages S such that every dependency of every package in S is satisfied by something in S, and no package in S conflicts with anything else in S. Recent formal treatments of this problem (the “Package Managers à la Carte” model, and the PACSOLVE Max-SMT formulation) confirm what packaging engineers have known empirically for two decades: once you allow Conflicts and Provides-style virtual packages, finding a valid S is NP-complete, and finding the best S by any reasonable cost function is harder still.

This means every resolver picks two of three:

• Completeness — if a valid resolution exists, the resolver finds it.
• Determinism — identical inputs produce identical outputs, every time, on every machine.
• Speed — resolution completes in bounded, practical time without backtracking search.

DNF’s move from YUM’s ad-hoc checker to libsolv’s SAT-based solver was an explicit trade toward completeness — SAT solvers are complete by construction, at the cost of solver-internal heuristics that aren’t always reproducible across versions. npm’s resolver (Arborist) achieves speed and a form of completeness by side-stepping conflicts entirely — nested node_modules lets two versions of the same package coexist, which most system package managers can’t do because they install into a single shared filesystem namespace.

Pacman and APT made different choices than either of these, and different choices from each other. Here’s what each one actually does.

APT’s immediate resolver: a scoring function with memory

The resolver invoked by apt-get install and dpkg — what the APT internals call the “immediate resolver” — does not search. When it hits a conflict (package A needs to be removed to satisfy package B, or vice versa), it computes a numeric score for every candidate package and keeps the higher-scoring one.

The score weights are not folklore — they’re compiled-in constants. Restated in their own terms:

Look at row six. “Currently installed and not obsolete” is worth +1 in the score formula that decides what gets removed during a conflict.

That single line is the entire thesis of this article. The resolver’s decision isn’t a pure function of (repo state, target packages) — it’s a function of (repo state, target packages, what happens to already be installed on this specific machine). Two machines with identical APT sources and an identical apt install foo command can receive different resolutions if their installed package sets differ in a way that shifts the score landscape around the conflicting packages.

Loading diagram...

This is not a bug, and the APT maintainers have never claimed otherwise — it’s an explicit design choice that lets the resolver be fast and usually find a workable answer without search. The Univention engineering writeup that documents these weights describes exactly this scenario: an internally-built package that the resolver silently refused to upgrade, because the score arithmetic — driven partly by what was already on the box — favored keeping the old one.

Aptitude’s interactive resolver: order matters too

When the immediate resolver can’t find any score-based answer (every option scores worse than not resolving at all), APT-based tools fall back to a second algorithm — what aptitude’s documentation calls the “interactive resolver.” This one does search, and it can find solutions immediate resolution can’t.

But it introduces a second axis of non-determinism: declaration order. When a package depends on exim | mail-transport-agent — an OR-dependency with multiple alternatives — aptitude’s algorithm processes the alternatives strictly in the order they’re written in the package’s control file. The first alternative that can be satisfied wins. Change the order the alternatives are listed in a future package revision (a packaging-metadata change, not a “real” dependency change) and the resolver’s choice can change with it.

So APT-family resolution has two distinct sources of host-dependent or metadata-ordering-dependent behavior, stacked: a scoring heuristic with installed-state as an input, and a fallback search whose branching order is determined by the textual order of alternatives in package metadata.

Pacman: push the ambiguity to packaging time and to you

Pacman’s resolver (libalpm) takes a structurally different approach, and it’s worth being precise about why it can: pacman’s repositories only ever list one version per package. There’s no “resolve which of these seven versions of libfoo satisfies everyone” problem, because there’s exactly one libfoo in core/extra at any moment. This single design constraint eliminates an entire dimension of the resolution problem before the algorithm even runs.

What’s left is: build the dependency graph for the target packages from Depends, walk it, and check Conflicts/Provides/Replaces along the way. There’s no scoring function. There’s no “what’s currently installed” input feeding a removal decision. When the graph walk surfaces an actual conflict — two packages that can’t coexist, or a package that provides the same thing as one already installed — pacman doesn’t decide. It asks.

Loading diagram...

The canonical example shows up constantly on the Arch forums: a user installs a package that provides cron, pacman detects that cronie (already installed, also provides cron) conflicts, and prompts: “cronie and fcron are in conflict. Remove cronie?” The resolver did not weigh cronie’s “currently installed” status against anything. It surfaced the conflict as a binary choice and stopped.

Given the same repo snapshot, the same target package set, and the same answers to the same prompts — pacman’s transaction is identical on every machine, regardless of install history. The “what’s already installed” information that feeds directly into APT’s score formula plays no equivalent role in pacman’s graph walk; it only matters for detecting a conflict exists, not for deciding which side of the conflict wins.

The actual tradeoff

Neither is strictly better. APT’s resolver will, more often, find some installable configuration even in messy multi-repo setups — that’s the entire value of completeness-leaning design, and it’s why APT has historically tolerated third-party repos better than pacman tolerates AUR-adjacent chaos. Pacman’s resolver will, more often, either do exactly the obvious thing or refuse outright — there’s no heuristic middle ground where it quietly does something clever that you’d have to reverse-engineer later.

The “Arch breaks more” folk wisdom and the “Arch is more predictable” folk wisdom are both describing this same property from opposite sides. Pacman fails loudly and immediately on cases its simpler model can’t represent. APT absorbs those same cases into its score function and usually produces something — which is exactly the behavior that, in the Univention case, manifested as a silent refusal to upgrade an internal package for reasons that took source-level investigation to explain.

Why this matters beyond distro preference

If you’re building container base images, CI pipelines, or reproducible build systems, this isn’t trivia — it’s the difference between “this Dockerfile produces the same image on every build” and “this Dockerfile produces the same image on every build as long as the base image’s installed-package set hasn’t drifted.”

An APT-based image rebuild that starts from a slightly different cached layer — same apt-get install line, slightly different pre-existing package set in the layer underneath — has a theoretical path to a different resolution, because the resolver’s score function takes that pre-existing set as an input. A pacman-based image rebuild starting from a different base layer either produces the identical transaction (same repo snapshot, same targets, same Provides/Conflicts graph) or fails with an explicit, file-grep-able error. There’s no silent middle state.

This is the same principle as the validate-then-trust-shared-state pattern that shows up everywhere from io_uring’s TOCTOU class to confused-deputy MCP agents: a system that takes “current state” as an input to a decision function is a system whose output depends on history, and history is exactly the thing reproducibility wants to eliminate. APT’s resolver is fine — it does what it was built to do, well. It’s just built on a different axiom than the one reproducibility needs, and almost nobody states that axiom out loud.

Pacman didn’t get more reproducible because Arch users are more disciplined. It got more reproducible because its repo model removed an entire dimension of the problem, and its conflict handler refused to let “what’s already here” cast a vote.