Resolution Order Dependency Causes Incorrect Backtracking

[qiulang]

Summary

When resolving dependencies, uv makes different (incorrect) resolution decisions depending on whether transitive dependency constraints are also specified at the top level. This causes it to pick incompatible package versions and backtrack to ancient versions instead of finding valid solutions.

Minimal Reproduction

Environment

• Index: Any (tested with official PyPI and Chinese mirrors)
• What matter is the date (as in Nov.05 2025) with huggingface-hub has released 1.0.1 while transformers 4.57.1 is the latest

Case 1: Bug - Just install xinference

uv pip compile - <<EOF
xinference
EOF

Result (WRONG):

transformers==4.12.2       # Ancient version from 2021!
huggingface-hub==1.0.1     # Violates transformers' <1.0 constraint
tokenizers==0.10.3         # Ancient version
Resolution time: ~1.6s

Case 2: Works - Add explicit transformers constraint

uv pip compile - <<EOF
transformers>=4.40.0
xinference
EOF

Result (CORRECT):

transformers==4.57.1
huggingface-hub==0.36.0    # Correctly satisfies both constraints
tokenizers==0.22.1
Resolution time: ~167ms

Case 3: Also works - Order doesn't matter when both specified

uv pip compile - <<EOF
xinference
transformers>=4.40.0
EOF

Result (CORRECT):

transformers==4.57.1
huggingface-hub==0.36.0
tokenizers==0.22.1
Resolution time: ~21ms

Root Cause Analysis

The dependency constraints are:

• xinference → huggingface-hub>=0.19.4 (no upper bound)
• xinference → transformers (via peft)
• transformers>=4.40 → huggingface-hub>=0.34.0,<1.0
• gradio (xinference dependency) → huggingface-hub>=0.33.5,<2.0

Valid solution space: huggingface-hub in range [0.34.0, 1.0) (e.g., 0.36.0)

What uv does wrong (Case 1):

1. Processes xinference's loose huggingface-hub>=0.19.4 constraint
2. Sees gradio's <2.0 upper bound
3. Picks huggingface-hub==1.0.1 (satisfies gradio but violates transformers)
4. Later discovers transformers needs <1.0
5. Backtracks transformers to 4.12.2 instead of reconsidering huggingface-hub
6. Results in ancient, incompatible versions

BTW, pip install xinference works

What uv does right (Cases 2 & 3):

1. Has transformers>=4.40.0 as a top-level constraint
2. Considers transformers' huggingface-hub<1.0 requirement from the start
3. Correctly picks huggingface-hub==0.36.0 (in the valid range)
4. Everyone gets modern, compatible versions

Expected Behavior

The resolver should produce the same result regardless of whether transitive constraints are explicitly listed at the top level. In this case:

• uv pip compile "xinference" should produce the same resolution as
• uv pip compile "transformers>=4.40.0\nxinference"

Since a valid solution exists (huggingface-hub 0.36.0), uv should find it in both cases.

Impact

This affects real-world packages like xinference which cannot be installed with uv without workarounds:

# Fails
uv pip install xinference

# Workaround 1: Pre-constrain huggingface-hub
uv pip install "huggingface-hub>=0.34.0,<1.0" xinference

# Workaround 2: Explicitly add transformers constraint
uv pip install transformers xinference

Users are forced to understand the internal dependency tree and manually add constraints, which defeats the purpose of automatic dependency resolution.

Additional Notes

• pip resolves this correctly in all cases (always picks modern versions)
• The resolution time difference (1.6s vs 167ms) suggests uv is doing significant backtracking
• The bug occurs regardless of which package index is used

Suggested Fix

When uv encounters a conflict during backtracking, it should reconsider earlier choices (like huggingface-hub version) rather than always downgrading the package that exposed the conflict (transformers).

Platform

Ubuntu22 / macOS 15

Version

uv 0.9.7

Python version

3.11/3/12 (does not matter)