Breaking the Dependency Chaos: A Constraint-Driven Python Dependency Resolution Strategy with Selective LLM Imputation Conference: 34th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering; July 05–09, 2026; Montreal, QC, Canada 34th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (FSE Companion ’26), July 05–09, 2026, Montreal, QC, Canada DOI: 10.1145/3803437.3808241 ISBN: 979-8-4007-2636-1/2026/07 CCS: Software and its engineering Empirical software validation CCS: Software and its engineering Software configuration management and version control systems CCS: Software and its engineering Maintaining software
Kowshik Chowdhury, Dipayan Banik, Shazibul Islam Shamim · 2026
Read Breaking the Dependency Chaos: A Constraint-Driven Python Dependency Resolution Strategy with Selective LLM Imputation Conference: 34th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering; July 05–09, 2026; Montreal, QC, Canada 34th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (FSE Companion ’26), July 05–09, 2026, Montreal, QC, Canada DOI: 10.1145/3803437.3808241 ISBN: 979-8-4007-2636-1/2026/07 CCS: Software and its engineering Empirical software validation CCS: Software and its engineering Software configuration management and version control systems CCS: Software and its engineering Maintaining software by Kowshik Chowdhury, Dipayan Banik, Shazibul Islam Shamim (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11772.txt.
Introduction
Kowshik Chowdhury, Dipayan Banik, and Shazibul Islam Shamim replace guesswork in Python dependency resolution with formal constraint solving. Their SMT-LLM system extracts imports deterministically, infers minimum Python versions, queries PyPI before calling a language model, and solves the resulting version constraints with a Z3 solver. On the HG2.9K benchmark it resolved 83.6 percent of snippets, far above the 54.8 percent of an LLM-only rival, and ran about six times faster.
Catalog record
| CREATOR | Kowshik Chowdhury, Dipayan Banik, Shazibul Islam Shamim |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19841 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11772
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Breaking the Dependency Chaos: A Constraint-Driven Python Dependency Resolution Strategy with Selective LLM Imputation Conference: 34th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering; July 05–09, 2026; Montreal, QC, Canada 34th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (FSE Companion ’26), July 05–09, 2026, Montreal, QC, Canada DOI: 10.1145/3803437.3808241 ISBN: 979-8-4007-2636-1/2026/07 CCS: Software and its engineering Empirical software validation CCS: Software and its engineering Software configuration management and version control systems CCS: Software and its engineering Maintaining software Kowshik Chowdhury, Dipayan Banik, Shazibul Islam Shamim Abstract . Dependency resolution is the task of selecting package versions that can be installed together without conflicts. It accounts for a significant share of build failures in modern software projects. In the Python ecosystem, this task is especially challenging due to Python 2/3 incompatibilities, deprecated packages, and widespread missing metadata. Recent work, such as PLLM, tackles this problem by using large language models (LLMs) to infer Python and package versions from code and iteratively repairing them based on build errors. We present SMT-LLM , a hybrid system that replaces LLM-only version guessing with formal constraint solving. SMT-LLM uses deterministic import extraction and Python version detection via abstract syntax tree (AST) analysis, the vermin tool to infer minimum Python versions, and a five-tier import-to-package resolver that queries PyPI before any LLM call. We construct a constraint graph from PyPI metadata and LLM-imputed dependencies for packages with missing metadata, then solve for consistent version assignments using a Z3 satisfiability modulo theories (SMT) solver. On the HG2.9K benchmark using Gemma2:9B (10 GB VRAM), SMT-LLM resolves 83.6% of snippets compared to PLLM’s 54.8%, while reducing median resolution time from 151.5 s to 23.9 s ( 6.3 × \times faster ) and average LLM calls from ∼ {\sim} 24.9 to 2.26 per snippet ( 11 × \times reduction ). † † cc-license: by 1. Introduction Dependency conflicts and failed dependency resolution are widespread in the Python package ecosystem, regularly breaking builds and delaying development. A study of 235 real-world cases from PyPI projects shows that even small changes to version constraints can introduce new conflicts and installation failures, making dependency management difficult in practice ( 13 ) . Given only a code snippet—often years old and missing a requirements.txt file—a dependency resolver must choose the right packages, version numbers, and Python interpreter. It must also handle Python 2/3 compatibility issues, deprecated packages, and missing package metadata ( 6 ) . Existing LLM-based methods, such as PLLM, use iterative prompting to infer these dependencies, but they still fail on nearly half of the HG2.9K benchmark, leaving many snippets unresolved ( 1 ; 5 ) . Figure 1. Overview of the SMT-LLM pipeline Key Insight. Our investigation of PLLM’s failures reveals three structural limitations. L1: Initial guess quality. PLLM guesses both the Python version and all module versions in a single prompt with no metadata lookup. Versions are chosen independently, so conflicting pairs like flask==2.0 (requires werkzeug>=2.0 ) with werkzeug==0.16 go undetected until pip install fails. This also misidentifies the Python version: 17.1% of snippets produce SyntaxErrors from running Python 2 code under Python 3. L2: Repair loop. On failure, PLLM prompts the LLM to replace one module version at a time, ignoring constraint hints pip already provides. If pip reports ‘‘requires werkzeug>=2.0’’ , PLLM discards this and guesses again. This one-at-a-time strategy cannot fix conflicts requiring several packages to change together. L3: Search strategy. PLLM launches three Python versions in parallel but never shares outcomes across them. Python 3.6 may fail five times while 3.8 has already succeeded, yet 3.6 keeps retrying because no early-termination signal propagates across parallel tracks. Our SMT-LLM approach addresses these limitations by restricting the LLM to verifiable factual queries (e.g., “What are flask== 0.10 ’s install_requires ?”) and delegating everything else to deterministic tools. Specifically, SMT-LLM (i) replaces version guessing with AST-based analysis and a five-tier PyPI resolver (addressing L1), (ii) parses pip errors into formal Z3 ( 3 ) constraints instead of blind re-prompting (addressing L2), and (iii) tests Python versions sequentially, stopping at the first success (addressing L3). The contributions are: ❶ A seven-stage hybrid pipeline (Figure 1 ) combining AST-based static analysis, a five-tier PyPI resolver, LLM-imputed constraint graphs, and Z3 SMT solving with Docker-based validation (§ 2 ). ❷ A hard/soft constraint distinction enabling the solver to trust PyPI metadata while treating LLM-imputed dependencies as relaxable (§ 2 , Stage D). ❸ An error-driven constraint refinement loop that parses Docker failures into formal Z3 constraints, strictly narrowing the search space (§ 2 , Stage G). ❹ A Recovery Ladder with LLM alias re-resolution, deterministic Python version sweep, and environment-limitation classification (§ 2 , Stage G). ❺ Evaluation on HG2.9K showing an 83.6% resolution rate, with substantially fewer LLM calls per snippet than PLLM (2.26 vs. {\sim} 24.9) (Table 1 ). 2. The SMT-LLM Pipeline We retain PLLM’s Docker-based validation backend but replace its LLM-centric pipeline with seven stages of deterministic analysis, Z3 constraint solving, and selective LLM imputation (Gemma-2:9B ( 12 ) via Ollama, 10 GB VRAM), as illustrated in Figure 1 . Stage A: Import Extraction. SMT-LLM parses Import and ImportFrom nodes via AST, falling back to regex for Python 2 files that fail parsing ( 16 ) . Standard-library modules are filtered using sys.stdlib_module_names , a hardcoded Python 2 stdlib set, and runtime importlib.util.find_spec() . Django-style submodule imports (e.g., from X.models import Y ) are excluded as project-local code. Snippets whose imports map exclusively to non-Linux, platform-specific modules (Sublime Text APIs, macOS Cocoa bindings, Blender internals, winreg , win32api ) are labeled OtherPass and bypass Docker entirely. These modules are embedded in their host applications, not distributed via PyPI, so detecting them early prevents unnecessary Docker builds that cannot succeed regardless of the selected version. Stage B: Python Version Detection. We use vermin 1 1 1 https://github.com/netromdk/vermin/ , a static analysis tool that inspects AST node types to infer the minimum compatible Python 2 and Python 3 versions. When vermin cannot determine compatibility, the pipeline falls back to [2.7, 3.6, 3.8, 3.9] . For Python 2-only snippets, the pipeline invokes 2to3 within a python:3.9 Docker container when the local lib2to3 module is unavailable (removed in Python 3.13+). This avoids deprecated Python 2.7 Debian Buster images whose EOL apt mirrors are increasingly unreliable. Stage C: Import-to-Package Mapping. Each import must resolve to its PyPI distribution (e.g., sklearn \rightarrow scikit-learn ). The collision table contains 36 curated mappings from PyPI metadata and mapping databases (e.g., pipreqs ( 8 ) ). Tier 3 sends parallel PyPI HEAD requests testing exact-case, lowercase, and capitalized variants. Tier 4 applies nine structural name-variant patterns (e.g., python-{name} , py{name} ). The LLM fallback (Tier 5) is accepted only if validated against PyPI. The pipeline persists all non-trivial mappings to disk for reuse in subsequent runs. Stage D: Constraint Graph Construction. For each package, the PyPI JSON API enumerates candidate versions after filtering yanked releases and Python-incompatible builds. Wheel-available versions are sorted first to avoid source-compilation failures on legacy interpreters. The two-pass era-biased selection picks up to eight candidates: the first pass estimates the snippet’s authorship era as the median of per-package midpoint PyPI