Can LLMs Resolve Dependencies? A Benchmark for Semantic-Versioning Constraint Reasoning and Dependency Resolution

Abstract

A coding agent that installs packages and untangles version conflicts is implicitly reasoning about semantic-versioning constraints and dependency resolution. Whether current language models can actually do this has not been measured, and that is the gap we address. DepResolve-Bench is a programmatically generated benchmark scored by a deterministic oracle that needs no human labels. We trust the oracle: it agrees with the production node-semver on 2250 sampled cases and, for resolution, with exhaustive search on 3000 instances. The benchmark has two tasks: deciding whether a version satisfies a range over the full npm grammar (Task A), and resolving a multi-package dependency graph or proving it unsatisfiable (Task B), with instance size as a difficulty knob. Five frontier and lightweight API models agree. They have nearly mastered the atomic rules, with Task A macro accuracy spanning 0.92 to 1.00, yet they cannot reliably put those rules together. On resolution the best model reaches 0.91 and the weakest 0.29, and every model degrades as the graphs grow, the strongest falling to 0.82 on the largest instances. A missed satisfiable instance almost always breaks a transitive constraint; on an unsatisfiable one, weaker models invent a resolution anyway (GPT-4o-mini for 44 of 80 such cases, the strongest model for one). How much we let a model reason matters more than which model it is: capped at 200 output tokens every model sits near 0.1, and accuracy climbs as the budget grows. We release the generators, oracle, and item banks; the results argue for keeping a real resolver in the loop rather than handing dependency management to a language model.