Evaluation: combinatorial ending-range enumeration in the Möbius V3/CL solver¶

Ergo task TT4VOX. Triggered by the V2-V3-V3 solver divergence fixture (logs/fixtures/v2_v3_v3_solver_divergence_25641093.md, a gitignored logs/ artifact since removed): a tick_spacing=1 DAI/WETH pool whose solver-predicted WETH output over-predicted the on-chain (revm, byte-verified) output by ~2.7× because the max_ranges budget was consumed by liquidity_net=0 word-boundary ticks before any initialized tick in the swap direction was reached.

Verdict (TL;DR)¶

Replace the combinatorial ending-range enumeration with an active-set piecewise Möbius walk. The recommendation is not a heuristic preference; it follows from two facts that this document works out below:

The path profit function P(x) = O(x) − x (final output as a function of path input, over any mix of V2 constant-product, V3, and V4 hops) is concave with a continuous first derivative, and is piecewise Möbius (degree-(1,1) rational) in x — exactly Möbius on each ending-range piece, not approximately.
For a concave C¹ piecewise-closed-form function, the piece containing the argmax is found by a monotone one-directional walk over pieces: each per-piece closed-form solve tells you which side of the current piece the optimum lies on. No enumeration of the piece set is ever needed.

The enumeration is therefore pure waste in the common case (10³ tuples × (closed form + 5 simulations) for a 3-hop path, to answer a question decided by one piece) and a silent correctness cap in the tick-sparse case (max_candidates = 10 truncates the piece set with no signal when the argmax piece is outside the prefix). The Q3YMBV boundary-tick collapse is endorsed as an interim patch but does not address either structural property.

Concrete follow-up tasks (files, RED tests, gates): <REDACTED_TOKEN> (active-set walk), EHSWSX (exact affine-shifted per-piece closed form, after 7J22EQ), PXSY47 (objective unification with the step-faithful walker, after 7J22EQ).

1. Where the design lives today¶

Hot path: arb_engine/solve_cycle.rs resolves each hop; V3/V4 hops call V3PoolState::build_int_v3_sequence(tick_spacing, fee, zfo, 10) (rust/crates/foundation/degenbot-pools/src/v3_state.rs), which slices get_cached_tick_ranges(..., max_ranges=15) (compute_tick_ranges in tick_bitmap.rs) down to an IntV3TickRangeSequence (rust/crates/foundation/degenbot-pools/src/int_v3_hop.rs). The all-CL dispatcher calls int_solve_cl_path (rust/crates/engine/degenbot-solvers/src/mobius_v3_int.rs); mixed V2+CL paths go through exact_solve_mixed_path_n / exact_solve_mixed_v2_v3_sequence. All of these enumerate ending-range tuples: max_candidates = 10 per CL hop, mixed-radix counter, per-tuple exact_mobius_solve on the unshifted ending-range IntHopStates, then total_optimal_input = piecewise_optimal + Σ crossing_gross_input, then a ±2 neighbor sweep validated by the piecewise simulator (int_simulate_cl_path_n / int_simulate_mixed_path_n).

Three separate caps sit on the same data flow:

Cap	Site	What it truncates	Failure mode when hit
`gen_ticks` budget (`max_ranges*4+16`)	`compute_tick_ranges`	raw tick walk	silent short walk
`max_ranges = 15`	`get_cached_tick_ranges`	cached boundary list	starvation by zero-net boundary ticks (the fixture)
`max_candidates = 10`	`int_solve_cl_path` + mixed solvers	enumerated piece prefix	argmax piece silently not enumerated

All three degrade silently. None reports “model truncated”; the solver returns a confidently wrong answer (3032343697 WETH vs 1109518347 actual).

2. The mathematical structure the solver actually optimizes¶

2.1 One V3 range is exactly constant-product in virtual reserves¶

Within a tick range with liquidity L and current sqrtPriceX96, the gross-input ↔ output relation is exactly the V2 form with virtual reserves R₀ = L·2⁹⁶/√P, R₁ = L·√P/2⁹⁶ (this is what IntV3TickRangeHop::compute_virtual_reserves computes). So a single range’s output map is the Möbius map y = γ·s·x / (D·r + γ·x).

2.2 Crossing a tick: piecewise Möbius, C¹, concave¶

For a V3 pool, output-vs-input o(x) is piecewise Möbius with breakpoints at the inputs that reach range boundaries. At any breakpoint the spot price is continuous (a tick crossing changes liquidity, not the price). The marginal exchange rate do/dx is γ × (a monotone function of the current spot price within each range), so:

do/dx is continuous across the breakpoint — the liquidity change alters only how fast the rate falls off (second derivative jumps, stays negative on both sides);
do/dx is non-increasing everywhere within each range (price only moves adversely in the swap direction).

Hence o(x) is concave and C¹ on its whole domain, whether the next range is deeper or shallower. (This is the smooth-model statement; EVM floor rounding perturbs it at wei scale — the same staircase the existing ±2 sweep already patches, see §6.)

2.3 Chaining hops preserves the structure¶

Composition of increasing concave functions is concave; V2 hops are smooth concave Möbius. Derivative continuity composes by the chain rule. Profit P(x) = O(x) − x is therefore a concave, C¹, piecewise Möbius function of the path input, with breakpoints wherever any hop crosses a range boundary. Each maximal interval between breakpoints corresponds to exactly one ending-range tuple k = (k₁, …, kₙ).

2.4 Each piece is exactly Möbius — the enumeration was approximating an exact structure¶

The crossing offsets are input-independent constants (this is already documented on IntTickRangeCrossing). Given a tuple k, with per-hop gross-input offsets gᵢ and output offsets oᵢ:

u₁ = x − g₁            y₁ = m₁(u₁) + o₁
u₂ = y₁ − g₂           y₂ = m₂(u₂) + o₂
...
O(x) = mₙ(uₙ) + oₙ

Möbius maps are closed under pre-translation (u = x − g), post-translation (+ o), and composition (SL(2,ℝ) closure; concretely, 2×2 integer matrix multiplication). So on each piece, O(x) = (A·x + B) / (C·x + D) with integer (A, B, C, D) computable directly, and the piece argmax is closed form:

P'(x) = (A·D − B·C) / (C·x + D)² − 1 = 0   ⟹   x* = (√(A·D − B·C) − D) / C

(one isqrt_u512, same discipline as compute_mobius_model_optimal_input; with B = 0 this reduces to the existing x* = (√(K·M) − M) / N). The existing compute_int_mobius_coefficients is already this 2×2 matrix recurrence minus the translation entries, in the same U512 width.

Consequence: the piecewise extension does not stray from the Möbius closed form’s exactness. If anything, the current implementation is the approximation: it composes coefficients from the unshifted ending ranges and then adds Σ crossing_gross_input to the result. For hops ≥ 2 the crossing is spent from an upstream hop’s output, not the path input, so the true input shift involves thresholding through the preceding hop’s map — the additive shift misanchors the per-tuple candidate by O(crossing × price impact), far beyond the ±2 sweep’s reach. Only the validation sims keep the enumerated candidates honest; the “closed form per tuple” is today a heuristic anchor.

3. Why the enumeration design fails — the structural reading¶

With §2 in hand the three failure modes of the enumeration collapse into one: it uses brute-force subset enumeration to locate the argmax piece of a function whose piece structure is monotone.

Wasted work, exponentially in hop count. For a well-behaved pool the argmax piece is almost always (0..2, 0..2, …) — arbs are small relative to pool depth. The enumeration still runs up to 10ʰᵒᵖˢ closed forms + 5× that many piecewise simulations. The active-set walk visits exactly the pieces between input 0 and the argmax, typically 1–3 iterations.
Silent correctness cap. max_candidates truncates the piece prefix. If the argmax piece lies beyond the prefix, the solver does not know. Worse, it composes with the max_ranges starvation: when the prefix consists of zero-liquidity_net boundary ranges (the fixture), every enumerated piece models constant liquidity, so the solver predicts the no-slippage output. Concavity does not save you from enumerating over the wrong model.
The budget is not load-bearing for the math. Nothing in the closed form or the piece geometry needs the enumeration; the cap exists only because the walk that would make it unnecessary was never built.

4. Recommended design: `solve_cl_path_active_set`¶

Replace the mixed-radix loop in int_solve_cl_path, int_solve_v3_v3, and exact_solve_mixed_path_n / exact_solve_mixed_v2_v3_sequence with one active-set routine (V2 hops simply have piece-count 1 and no crossing data):

hypothesis k = (0, …, 0)                      # all hops in base range
best = None
loop at most Σᵢ rangesᵢ iterations:           # hard cap; see §5
    anchor x̂ = per-piece closed form on tuple k   (§2.4, or transitional
                                                   approximate anchor §4.1)
    simulate path O(x̂) with the validation simulator
    record (x̂, O(x̂) − x̂) into best if better
    k' = ending tuple that the walk actually landed in
    if k' == k and x̂ is strictly interior to piece k's input extent:
        break                                  # C¹ concave ⇒ global argmax
    k = k'
±2-exact sweep around best.x with real simulation; return best

4.1 Transitional anchor¶

7J22EQ may ship with the existing per-tuple anchor (unshifted coefficients + additive crossing cost) inside this loop. The loop’s correctness does not depend on anchor precision — the simulation tells the truth about which piece x̂ landed in, and the monotone walk converges regardless; a worse anchor only costs extra iterations. EHSWSX then swaps in the exact affine-shifted coefficients of §2.4 (U512 matrix composition with translation entries, argmax (√(A·D−B·C) − D)/C), making each piece step exact and typically collapsing the walk to 1–2 iterations.

4.2 Convergence argument¶

The breakpoints partition [0, ∞) into intervals; on interval I_k the true P coincides with piece k’s closed-form extension, whose derivative is decreasing (concavity). If piece k’s argmax lies at or beyond the right edge of I_k, then P' ≥ 0 throughout I_k; by C¹ the adjacent piece’s extension also starts with P' ≥ 0, so the optimum lies strictly to the right — the walk never needs to return left. Symmetrically for the left edge. Therefore the walk visits a strictly monotone sequence of pieces and terminates in the argmax piece after crossing at most as many breakpoints as lie between 0 and the argmax — bounded above by Σᵢ rangesᵢ, which is the loop cap. Pool exhaustion (“argmax beyond modeled liquidity”) is the walker hitting its last modeled piece; it degrades to “largest validated candidate”, exactly today’s semantics.

4.3 What happens to the three caps¶

max_candidates dies with the enumeration. There is no tuple budget.
max_ranges = 15 becomes a cache/memory bound only, not a correctness cap. The active-set solver consumes ranges on demand in walk order (the same gen_ticks discipline as v3_simulate_swap, with sparse-mode MissingTickWord propagation); a tick-sparse pool with 40 boundary words and an initialized tick 10,354 ticks away is fully reachable — the fixture failure mode disappears structurally, not by re-shaping the filter.
gen_ticks budget remains as a work ceiling, now hit only by genuinely deep walks, not by boundary-tick interleaving arithmetic (max_ranges*4+16).

PXSY47 then unifies the validation objective with the step-faithful sequential walker (v3_simulate_swap’s compute_swap_step_v3 loop discipline, generalized to an N-hop path), replacing the bespoke piecewise objectives (int_simulate_v3_swap / int_simulate_cl_path_n / int_simulate_mixed_path_n). This retires a whole dual-maintenance seam: today both the piecewise simulator and compute_crossing re-derive the per-boundary rounding of computeSwapStep (the ON5QMD parity), in a second codebase, with their own parity tests. After unification the word-boundary computeSwapStep flooring exists in exactly one place — the walker — which is also the Tier-3 byte-exact oracle path. The Q3YMBV collapse filter (boundary ticks flanking initialized ticks) keeps its value for the cached range list used by non-solver consumers, but the solver no longer depends on boundary-tick presence for rounding parity.

4.4 Performance profile¶

Per candidate path: today O(∏ min(10, rangesᵢ)) closed forms + 5× that many simulations; after: O(walk depth) iterations × (1 closed form + 1 walk) + a constant final sweep. Walk depth for real arbs is 0–3 ranges per hop. This is roughly two orders of magnitude cheaper on 3-hop paths and scales linearly rather than exponentially with hop count — safe headroom to widen path-finding to longer paths. Building sequences also gets cheaper: compute_crossing is only needed for pieces actually visited (and can be incremental in k).

5. Alternatives considered¶

Status quo + Q3YMBV collapse. Patches the mid-tier cap (boundary starvation) but leaves the enumeration’s cost blowup and the silent max_candidates truncation intact, and keeps the approximate per-tuple anchor. Rejected as the end state; endorsed as the interim fix (it is independently correct and nearly complete in the working tree).
Hybrid: enumerate when cheap, walk when sparse. Two solvers to keep in parity; the walk dominates the enumeration in the cheap regime too (the single-range fast path is just the first iteration of the walk). Rejected — one mechanism, no regime switch.
Bisection on the marginal-profit sign. Simulate at x and x+h, sign of (O(x+h) − O(x))/h − 1 brackets the argmax of a concave staircase; O(log U256) iterations is too many simulations, and the wei-scale staircase perturbs the finite-difference sign near the optimum. Kept as a documented fallback safety net inside the iteration cap of solve_cl_path_active_set, not as the primary mechanism.
“Lagrangian/KKT-style” solver. This is what the active-set walk is: the piece identity is the active constraint set; complementary slackness is exactly the rule “the argmax piece is the one whose unconstrained closed-form argmax lies strictly inside it”; the walk’s direction test is the KKT sign check. The recommendation formalizes the task’s KKT alternative as the sequential-walk alternative.

6. Risks and edge cases¶

Wei-scale staircase. EVM floor rounding makes discrete P not exactly concave; the discrete argmax can jog by a couple of wei, and a true optimum within rounding noise of a piece boundary sits in “both pieces”. The final ±2 sweep (same discipline as exact_mobius_solve) plus “best validated candidate” tracking covers this; the walk’s termination check must use the interior test, not exact-argmax equality.
Anchor overshoot with the transitional anchor (7J22EQ). The approximate anchor can land several pieces off when crossing costs are large (downstream shifts are mispriced). Handled by the loop itself — convergence is driven by simulation feedback, and the iteration cap + best-so-far tracking bounds pathological anchors. EHSWSX removes the misanchoring at the root.
U512 width on deep paths. The §2.4 determinant composition inherits the same width discipline as compute_int_mobius_coefficients; at ≥5 hops the coefficient products strain U512. Out of scope for EHSWSX — the current solver has the identical exposure — but EHSWSX must carry a width comment and a debug-assert mirroring the existing U512 → U256 narrowing asserts.
Partial-fill / exhaustion semantics. int_simulate_cl_path_n has an “input below crossing_gross_input → path exhausted” branch that returns zeros mid-path; the walker handles exhaustion by mirroring the contract’s price-limit stop. PXSY47 must preserve the solver-visible distinction between “no profitable input” and “pool exhausted”.
ON5QMD regression risk during transition. Until PXSY47 lands, the objective remains the piecewise simulator whose rounding parity is covered by int_v3_hop.rs’s compute_crossing_matches_onchain_step_walk_for_ multi_range and by v4_word_boundary_solver_divergence.rs. These stay green at every step; 7J22EQ changes which candidates are proposed, not how candidates are validated.

7. Validation / RED-test plan for the follow-up implementation¶

Fixture RED (7J22EQ): reconstruct the block-25641093 V3 DAI/WETH pool state from logs/fixtures/v2_v3_v3_solver_divergence_25641093.md (a gitignored logs/ artifact, since removed) (sqrt_price_x96=1956421190421993762013571523, tick=-74028, liquidity=5407362545736161987, 12 initialized ticks, nearest lower initialized tick −84382) and assert the solver’s predicted hop-2 output for input 4973433520019 DAI zfo is within wei tolerance of 1109518347 — not 3032343697. RED on the enumeration (starved sequence), GREEN with the active-set walk consuming the full tick data.
Property test: for randomized pool states (including tick_spacing=1 with initialized ticks ≥ 20 word boundaries apart — sparse topologies crossing uninitialized word boundaries) and randomized directions, the active-set solver’s returned profit must ≥ the profit of any tuple the old enumeration would have validated within its max_candidates prefix — i.e. never worse than the old design — and must equal max over a fine sample grid within the staircase tolerance.
Iteration-count guard: solver performs ≤ a small multiple of Σ ranges closed forms (assert via a counter in test builds) — this is the regression net against accidentally re-introducing combinatorial behavior.
Keep green: mobius_v3_int.rs unit tests, int_v3_hop.rs crossing parity tests, v4_word_boundary_solver_divergence.rs, the tests/standalone_parity V3/V4 dual-driver pairs, and the Tier-3 just test-tier3-* nets.
PXSY47 specific: byte-exact agreement of the new objective with v3_simulate_swap on the fixture state, and with the revm canonical-bytecode V3 Pool.swap oracle (Tier-3) on pinned mainnet slots.

8. As-built outcome (ergo 7J22EQ, landed)¶

The combinatorial enumeration was removed from int_solve_cl_path, int_solve_v3_v3, exact_solve_mixed_v2_v3_sequence, and exact_solve_mixed_path_n; all four now delegate to solve_active_set_path in mobius_v3_int.rs. max_candidates is gone. The as-built walk differs from the §4 sketch in ways the implementation surfaced:

The enumeration was also corner-blind (a second failure mode found during RED-fixture construction). The per-piece anchor models the ending range as an UNBOUNDED constant-product pool; when the true optimum is “fill the piece to its saturation boundary” the anchor overshoots, the validation sim reports negative profit, and even an UNcapped enumeration finds nothing on geometries with real profit (e.g. 2.5e7 wei on the mixed test fixture). Fix: the walk computes each visited piece’s input window with two monotone bisections over the landed-tuple map (componentwise non-decreasing in x) and refines the stop-region pieces with a windowed ternary search + dense sweep (walk_refine_window) — the two-layer discipline of exact_mobius_solve generalized to windows.
The EVM floor staircase rules out pointwise direction tests. The discrete profit is flat to ±1 wei over tens of wei around the top, so neither “argmax hugs the edge” nor pointwise edge-score comparisons are reliable. The as-built direction test uses straddle probes at ±64 around the right edge with +1-wei tolerance; on stop it refines the current piece AND its forward neighbor (a peak straddling the edge is never mis-attributed).
One-piece steps, no hopscotch in the transitional version: the walk visits consecutive pieces only, which by concavity cannot vault the peak. Exact anchors (EHSWSX) re-enable hopping past clearly-climbing pieces.
Perf (debug build, per solve): single-range 2-hop ≈ 11 µs (was the old fast path’s ~handful of sims); 8-range 2-hop ≈ 5.1 ms vs ≈ 2.7 ms for the legacy enumeration on the same shape. Slower in debug for multi-range, structurally cheaper for tick-sparse pools (no tuple budget); the release profile collapses the gap by an order of magnitude. EHSWSX owns the remaining gap (exact anchors ⇒ fewer probes).
int_simulate_v3_swap now saturates at the range boundary on absurd inputs instead of panicking on the U512→U256 narrowing (window-edge probes can propose domain-scale inputs the enumeration never tried).
Guard instrumentation: thread-local WALK_PIECES_VISITED / WALK_PATH_SIMULATIONS counters with a test asserting pieces ≤ Σ ranges + 2 and sims bounded per range.

Validation on landing: 72 lib tests + the V4 parity nets (v4_word_boundary_solver_divergence, v4_crossing_solver_vs_sim_parity)

degenbot-bot lib (277) + umbrella parity_v3_swap/parity_v4_swap green; clippy -D warnings clean.

9. Cross-references¶

Ergo: TT4VOX (this evaluation), Q3YMBV (interim boundary collapse), 7J22EQ -> EHSWSX, 7J22EQ -> PXSY47 (sequenced follow-ups), ON5QMD (rounding parity), BQ43DK (Tier-3 enforcement).
Fixture: logs/fixtures/v2_v3_v3_solver_divergence_25641093.md (a gitignored logs/ artifact, since removed).
Code: rust/crates/engine/degenbot-solvers/src/mobius_v3_int.rs, rust/crates/engine/degenbot-solvers/src/mobius_int_exact.rs, rust/crates/engine/degenbot-solvers/src/mobius_int.rs, rust/crates/foundation/degenbot-pools/src/int_v3_hop.rs, rust/crates/foundation/degenbot-pools/src/tick_bitmap.rs, rust/crates/foundation/degenbot-pools/src/v3_state.rs (build_int_v3_sequence, v3_simulate_swap), rust/crates/foundation/degenbot-math/src/cl/.
Prior diagnosis doc: docs/architecture/sim_v4_swap_step_rounding.md (removed in the stale-docs cleanup 71ec78b2) (the int_simulate_v3_swap 2-range approximation finding — PXSY47 retires exactly that seam).