Your Package Manager Is Solving SAT. Go's Refuses To: Minimal Version Selection Explained

Most package managers answer the question "which versions should I install?" with a search. Cargo runs a backtracking solver. apt, DNF, and Conda can invoke literal SAT solvers. Go looked at the same problem and refused to search at all: its resolver, Minimal Version Selection (MVS), deliberately picks the oldest version of every dependency that satisfies the stated requirements, and in exchange gets a resolver with no backtracking, no solver, and no lockfile. That choice is one of the most misunderstood decisions in package management — and the reasoning behind it is a genuinely sharp piece of engineering.

Version selection is literally SAT

In Version SAT, Russ Cox shows that deciding whether a valid installation exists is NP-complete, via a direct reduction from 3-SAT. The construction is compact: one package per boolean variable with two mutually conflicting versions (representing true and false), one package per clause with three versions (each depending on one literal of the clause), and a root package depending on every clause package. If the package manager can install the root, reading off which variable versions got installed yields a satisfying assignment.

The reduction only needs four assumptions, all of which describe an ordinary package manager:

1. A dependency can name specific versions of another package.
2. Everything you depend on must be installed.
3. Different versions of a package can have different dependencies.
4. Two versions of the same package cannot be installed at once.

This isn't a theoretical curiosity. Cox catalogs real systems that ship actual SAT or constraint solvers to install software: 0install (which switched from heuristics to a SAT solver), Chef (Gecode), Debian's apt-get, Eclipse (sat4j), Fedora's DNF, FreeBSD's pkg (picosat), OCaml's OPAM, OpenSUSE (libsolv), Anaconda, and Solaris pkg (minisat). Cargo doesn't embed a third-party solver, but its resolver documentation describes the same shape of computation: pick a candidate version, recurse, and backtrack to try an alternative when a conflict appears.

NP-complete doesn't mean slow in practice — solvers are good, and dependency graphs are usually tame. It means the worst case is a search, resolution can fail with "no solution found," and the answer you get can depend on heuristics and tie-breaking rather than on anything a human can predict from reading the manifests.

The escape hatch: only allow minimum constraints

MVS, described in Minimal Version Selection, sidesteps the reduction by removing its fuel. In a go.mod file, a require directive states a minimum version — never a maximum, never an exclusion of a range, never "exactly this one":

module example.com/app

go 1.22

require (
    github.com/pkg/a v1.2.0
    github.com/pkg/b v1.4.1
)

With only lower bounds in the graph, constraints can never contradict each other. The Go modules reference states the whole algorithm in one sentence: MVS starts at the main module, traverses the requirement graph, and tracks the highest required version of each module; those highest-required versions are the build list. There is nothing to search and nothing to backtrack over — resolution is a graph reachability pass. Cox notes the restricted constraint language lands in the intersection of three tractable SAT subclasses (2-SAT, Horn-SAT, and dual-Horn-SAT), which is what guarantees a unique minimal answer exists.

The name trips people up, so it's worth being precise: "minimal" does not mean Go ignores your dependencies' needs. The selected version of each module is the maximum of all stated minimums. If your app requires a v1.2.0 but some other dependency requires a v1.5.0, everyone gets v1.5.0. What Go never does is jump past every stated requirement to whatever was published last night.

Reproducibility without a lockfile

Cargo defaults to the highest compatible version: bitflags = "1.0" means >=1.0.0,<2.0.0, and Cargo will happily take 1.2.1 today and 1.3.5 after the next release. That's why Cargo.lock exists — the docs describe it as balancing reproducible builds against a manifest whose meaning changes as the registry grows. The lockfile pins what the range-based resolution would otherwise let drift.

MVS gets the same reproducibility from the algorithm itself. Since the build list is the maximum of stated minimums, and stated minimums only change when someone edits a go.mod, publishing a new version has no effect on anyone's build. The Go modules reference is explicit that the build list is deterministic and "is not saved in a 'lock' file" — it's recomputed by every module-aware command. And no, go.sum is not Go's lockfile: it holds cryptographic checksums for verifying module integrity, not version choices. Delete it and resolution picks the same versions; it exists so you notice if a proxy serves you tampered code.

Go 1.17 tightened the practical story further with module graph pruning: for dependencies whose own go.mod declares go 1.17 or higher, MVS only loads their immediate requirements rather than the full transitive closure, which is why modern go.mod files list every transitive dependency explicitly.

High-fidelity builds: the actual argument

Cox's deeper claim is about fidelity: how close your build of a library is to the build its author tested. He calls a build low-fidelity when it deviates from the author's dependency versions without justification — the way go get -u-style "upgrade everything" behavior might hand you C 1.3 and E 1.3 when the author developed and tested against C 1.2. Under MVS, your build uses newer versions than the author's only when some other module in your program forces them. Every deviation has a reason you can point to in a go.mod file.

The flip side is the strongest criticism of MVS: by default you keep running old code, including code with known bugs, until you explicitly run an upgrade. Cox's response is twofold. First, the maximum-of-minimums rule means a single actively-maintained dependency requiring a v1.5.0 drags every build that includes it forward — the ecosystem's floor rises collectively. Second, the alternative failure mode is worse in his view: with range constraints, a dependency deep in your graph can pin you down aggressively. He cites the Kubernetes Go client requiring a two-year-old version of a YAML library, blocking every downstream user from features in newer releases. MVS refuses to give dependencies that power: upper bounds don't exist, and exclude and replace directives only take effect in the top-level module being built, so a library can raise your floor but never fence your ceiling.

The tradeoff, stated honestly

Both designs are coherent; they optimize for different failure modes.

Both ecosystems also lean on the other escape hatch from Version SAT: letting incompatible major versions coexist as effectively different packages. Cargo will build rand 0.6.5 and rand 0.7.3 into the same binary when requirements can't unify (at the cost of the two rands having incompatible types), and Go gives each major version its own module path for the same reason.

Cox summarizes the MVS design goal as being "understandable. Predictable. Boring." If you've ever had a CI build break because a transitive dependency released a bad version overnight — with no change in your repo — you've felt exactly the failure mode MVS was built to delete. The cost is that staying current becomes a chore you must schedule instead of a side effect you get for free. That's not a solved problem; it's a picked tradeoff.

References

• Minimal Version Selection (Go & Versioning, Part 4) — Russ Cox
• Version SAT — Russ Cox
• Dependency Resolution — The Cargo Book
• Go Modules Reference — go.dev

go-modulesdependency-resolutionpackage-managerscargosemver