Multi-Path Routing in Decentralized Exchange Networks: Convex Allocation and an Improving-Path Certificate

Ilia Zhavoronkov

REVIEW 5 major objections 4 minor 11 references

Multi-Path Routing in Decentralized Exchange Networks: Convex Allocation and an Improving-Path Certificate

T0 review · 5 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A gas-aware convex router for DEX trades certifies its own route optimality with a single shortest-path query.

desk verdict Useful engineering and honest empirics, but the improving-path certificate is not actually computed by a single shortest-path query. read the letter →

arxiv 2607.22540 v1 pith:G5MIL7HC submitted 2026-04-25 math.OC cs.CE

Ilia Zhavoronkov This is my paper · ORCID

classification math.OCcs.CE MSC 90C2590C35

keywords AMMroutingdecentralizedexchangeconstantfunctionmarketmakersconvexoptimizationKKTconditionsshortestpathgas-awareslippage

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that multi-path routing in decentralized exchange (DEX) networks can be split into two tractable layers: enumerate a small pool-simple candidate path set using gas-aware edge scores, then allocate the trade across those paths as a concave maximization over a simplex. Its central theoretical claim is that the KKT multiplier from that allocation doubles as a certificate: if the largest initial marginal exchange rate of any omitted pool-simple path is no larger than the multiplier, then the candidate allocation is optimal over all pool-simple paths, and checking this condition is a single shortest-path query. On the empirical side, the author's implemented engine, evaluated on repeated WETH-USDT quotes against four production aggregators, reports median shortfall below 5 basis points across six trade sizes and top-3 quote rank in over 57% of epochs. A sympathetic reader would care because it suggests that competitive DEX routing can be achieved without enumerating all possible paths, and that a convex certificate can tell when generated candidates are enough.

What carries the argument

The load-bearing machinery is the path-separable concave allocation plus the improving-path certificate. Edge scores w_a = -log pi_a + gamma g_a embed expected gas cost into graph traversal, and pool-simple paths (paths that never reuse the same liquidity pool) are enforced during enumeration. Allocation over the k candidate paths is a concave maximization over a simplex, whose KKT conditions give a water-filling rule: active paths share a common marginal output lambda*, while inactive paths have initial marginal output no greater than lambda*. The certificate turns lambda* into a threshold and reduces the question 'does any omitted path improve the solution?' to a shortest-path problem on -

What would settle it

Build a small token graph with two candidate paths sharing one pool (for example WETH-USDC-USDT and WETH-USDT, where the WETH-USDC pool is common), compute the separable allocation and its lambda*, verify the certificate passes, then simulate the true constant-function-market-maker reserves during the split; if any omitted path or reallocation improves real output beyond the quoted amount, the certificate has failed outside the separable model.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3: within the path-separable model, where each candidate path's output is a concave nondecreasing function of its own flow, an allocation found by maximizing total output over the candidate set is globally optimal over all pool-simple paths if the maximum initial marginal derivative y'_q(0+) across all omitted paths is at most the KKT multiplier lambda* from the candidate-set allocation. Because y'_q(0+) factorizes as the product of edge derivatives at zero, this condition is checked by a single shortest-path query with edge weights -log phi'_a(0+). The paper also reports that its implemented engine, using k=20 candidate paths, a per-pool price-impact cap

Load-bearing premise

The load-bearing premise is that each path's output depends only on the flow assigned to it, so candidate paths that share a liquidity pool do not influence each other's exchange rates; if that path-separable approximation is not accurate in a given market, the certificate's guarantee stops applying to real execution.

Editorial extensions

If this is right

When the certificate passes, the k=20 candidate set is provably sufficient within the path-separable model, so no exhaustive path enumeration is needed.
The certificate condition is checkable with one shortest-path query, making global optimality verification practical even when the path space is exponential.
Gas-aware enumeration with concave allocation can track the best observed production quote within a few basis points at moderate trade sizes.
At larger trade sizes (2-5 WETH), the reported shortfall is driven by liquidity coverage rather than routing logic, implying that deeper pool integration is the expected lever.
The KKT marginal-equalization condition directly justifies continuous route splitting: splitting flow across active paths is optimal when their marginal outputs are equal.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the model is path-separable, the certificate does not certify real execution optimality when paths share pools; a concrete next test would be to compare the separable verdict against exact coupled simulation with shared-pool reserve updates.
The certificate's threshold uses initial derivatives -log phi'_a(0+), while candidate generation uses gas-adjusted scores; a gas-adjusted version of the certificate might yield a stronger, more execution-relevant optimality check.
The KKT-threshold idea could transfer to other concave routing problems with discrete candidate sets, such as liquidity provision or cross-chain bridge selection, where a dual multiplier can certify candidate sufficiency.
The empirical benchmark is quote-level, not execution-level; a natural follow-up would measure how much of the sub-5-bps shortfall survives to settlement by comparing quoted and on-chain-executed amounts against pool-state-reconstructed optima.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You asked about the multi-path DEX routing paper. The short version: the theory is standard but correctly assembled, the engineering is interesting, and the certificate—which is the headline contribution—does not work as stated.

What is new: the authors combine gas-aware k-shortest-path enumeration with a pool-simple constraint, then allocate flow via a concave water-filling program, and benchmark their engine against four production aggregators on WETH-USDT quotes. The KKT marginal equalization is exactly Angeris et al.'s convex routing in a different wrapper; the paper says as much. The gas-aware edge score and the quote-level benchmark are the genuinely new pieces. The empirical results—median shortfall below 5 bps, top-3 in >57% of epochs—are useful if you care about aggregator competitiveness, and the paper is honest that this is quote-level, not execution-level.

The soft spot is the certificate. Theorem 3 says if the maximum initial marginal gain over all omitted pool-simple paths is below lambda*, the candidate solution is globally optimal. That implication is fine. But the paper claims this maximum can be found by a single shortest-path query with weights -log phi'_a(0+). Two problems. First, shortest paths on the token graph don't enforce pool-simplicity; with multi-token pools like Curve, a vertex-simple token path can reuse the same pool through different token pairs. The paper tracks pool-simplicity during candidate generation but gives no algorithm to enforce it in the certificate query. Second, phi'_a(0+) can exceed one, so the weights are negative. With negative weights and cycles, the shortest walk is unbounded (or, if you require simple paths, the problem is NP-hard). The paper does not restrict to acyclic graphs or nonnegative weights. So the certificate's 'single query' does not compute what the theorem requires, and the reported 'majority of epochs' confirmations are not backed by a valid computation. On top of that, the certificate uses gas-free marginal weights while the engine's objective is gas-aware, so even a correct query would certify the wrong objective.

The path-separable limitation is acknowledged in Section 11 and is a reasonable approximation; that does not bother me. The absence of code/data and the 50-60 epochs per trade size are addressable. The certificate issue is the load-bearing one.

Who is this for? Practitioners building aggregators and researchers in AMM routing will find the benchmark and the path-generation logic useful. The theory section is not the draw. I think it deserves a serious referee, but the referee should insist on a corrected certificate algorithm, a statement of when the certificate actually holds, and a release of the quote data.

Recommendation: engage with it, but treat the certificate claims as provisional.

Referee Report

5 major / 4 minor

Summary. The paper develops a graph-theoretic and convex-optimization framework for multi-path DEX routing. It models the market as a token multigraph with AMM edge functions, generates a candidate set of pool-simple paths using gas-aware edge scores, and solves a separable concave allocation problem over that candidate set. The main theoretical contribution is Theorem 3, an improving-path certificate: if the maximum initial marginal gain of any omitted pool-simple path is at most the KKT multiplier from the candidate-set allocation, then the candidate allocation is globally optimal within the path-separable model. The paper also reports a mainnet empirical evaluation of an implemented engine (8DX), claiming median shortfall below 5 bps and top-3 quote rank above 57% of epochs against four production aggregators on WETH-USDT.

Significance. The convex allocation formulation is a natural and useful reduction for fixed candidate path sets, and Theorem 2 is a standard, correctly proved KKT condition. The idea of using the KKT multiplier as a threshold for improving-path search is appealing and, once the theorem statement is corrected to quantify over omitted paths, gives a sufficient condition under the path-separable model. The empirical comparison is timely and uses a sensible synchronized-quote protocol. However, the paper's headline claims are not currently supported: the certificate computation is not justified as a single shortest-path query under the pool-simple constraint and negative weights; the certificate is derived for a gas-free objective while candidate generation is gas-aware; the formal allocation model omits the stated per-pool price-impact cap; and the empirical text contains a direct contradiction about top-3 percentages. The framework is promising, but substantial revision is needed before the theoretical and empirical claims can be accepted.

major comments (5)

[§5, Theorem 3] The displayed condition in Theorem 3 quantifies over all pool-simple paths q, including paths already in the candidate set P_k. For any active path p with δ*_p>0, concavity gives y'_p(0+) ≥ y'_p(δ*_p)=λ*, and the inequality is strict whenever the marginal derivative is not constant. Thus the condition as written can fail at the true optimum. The proof and surrounding text argue only about omitted paths, so the intended statement is max over q∉P_k. The theorem must be restated with this restriction; as written it is not a valid optimality certificate.
[§5, improving-path search] Even after restricting to omitted paths, the search max_{q∉P_k, pool-simple} y'_q(0+) = min_q Σ_{a∈q} -log φ'_a(0+) is not solvable by a single standard shortest-path query. The paper acknowledges that edge weights can be negative (§5), so Bellman-Ford returns shortest walks, not necessarily pool-simple paths. Moreover, the pool-simple constraint is a resource constraint: a token path can be vertex-simple but still reuse the same pool through different token-pair arcs. Ordinary token-graph shortest-path algorithms do not enforce this constraint. The exact maximization over pool-simple paths generalizes resource-constrained longest path and is NP-hard in general, yet the paper gives no algorithm, restriction (e.g., nonnegative weights, acyclic graph), or discussion of this hardness in the certificate context. Therefore the claim that a single shortest-path query determines whether an omit
[§5 vs Definition 2 (§4)] The certificate's threshold λ* is the KKT multiplier for the gas-free allocation objective U(δ)=Σ_p y_p(δ_p). Candidate generation, however, uses edge scores w_a = -log π_a + γ g_a, so the candidate set P_k depends on gas costs while the certificate's optimality condition does not. The certificate can at most certify optimality for the gas-free path-separable problem; it does not certify the gas-aware routing objective that motivated the candidate set. The paper does not show that the gas term is irrelevant to the marginal entrance condition, and Section 11 only treats gas as a linearized heuristic. This is a load-bearing mismatch between the theoretical certificate and the implemented engine.
[§4, Definition 2 vs §1.1 and §6] The formal allocation problem in Definition 2 is a concave maximization over a simplex with no additional constraints. The text repeatedly states that the implemented engine applies a per-pool price-impact cap during allocation (§1.1, §6). Such a cap couples paths that share a pool and changes the KKT system. Unless the cap is incorporated into the model or shown not to bind in the reported epochs, Theorems 2 and 3 do not apply to the actual allocation used in the empirical evaluation.
[§9.1 and abstract] The abstract states that top-3 quote rank exceeds 57% of epochs, and §9.1 says 'top-3 quotes in at least 57% of epochs across all tested trade sizes.' Yet §9.1 later reports that top-3 presence 'fell to 34% and 57% respectively' at 2 WETH and 5 WETH. These statements are directly contradictory. Additionally, the certificate's 'majority of epochs' claim appears in the abstract and conclusion but no quantitative result, table, or figure for certificate outcomes appears in Section 9. This central empirical assertion is unverifiable from the manuscript.

minor comments (4)

[§9] The empirical comparison uses roughly 50-60 epochs per trade size and reports no confidence intervals or statistical tests. Given the small sample and the self-evaluation of the author's own engine, standard errors or bootstrap intervals would help substantiate the rank and shortfall comparisons.
[§5] The gas term γg_a is added in the log domain as w_a = -log π_a + γg_a, but the units of g_a (output-token cost) and the normalization of γ are not specified. This makes the candidate-generation score difficult to interpret or reproduce.
[§7] The paper states that 'Velora (formerly ParaSwap)' is a production aggregator. The naming and the specific APIs used for quote collection are not described in enough detail for replication; a data availability or reproducibility statement would be valuable.
[§2.4] Reference [10] is cited as an unpublished manuscript 'available from the authors upon request.' If it is used to distinguish the present benchmark from execution-level audits, a public preprint or more detailed citation information would improve verifiability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the KKT-based allocation and improving-path certificate are self-contained mathematical statements; the self-developed empirical engine is an external quote-level comparison, not a derivation that reduces to its inputs.

full rationale

The theoretical derivation is self-contained. Theorems 1 and 2 are standard concavity/KKT results for a separable concave maximization over a simplex, and Theorem 3 supplies a genuine sufficient condition: it checks the complementary-slackness inequality for all omitted pool-simple paths without assuming global optimality. The certificate's threshold condition max_q y'_q(0+) <= lambda* is not definitionally identical to the conclusion; it is the inactive-path KKT inequality for the enlarged path set, and lambda* comes from the candidate-set allocation. No fitted parameter is relabeled as a prediction. The empirical section evaluates the author's own 8DX engine, but the comparison is against external production aggregator quotes; this is a self-evaluation, not a circular derivation. The paper also explicitly disclaims execution-level optimality and, in Section 11, acknowledges the path-separable model ignores cross-pool coupling, the quote-vs-execution gap, and the inability to inspect competitors' internals. The 'single shortest-path query' certificate claim raises a computational correctness concern (pool-simple constraint with negative weights is not handled by ordinary shortest paths), but that is a missing-proof/correctness issue, not circularity. No load-bearing self-citation or definitional identity was found.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central derivation rests on concavity and separability assumptions, plus several undisclosed tuning parameters. The certificate is only valid for the path-separable no-gas objective, while the implemented engine uses a different score during search.

free parameters (4)

k (number of candidate paths) = 20
Chosen to balance compute and quality; no principled justification given; Section 5.
gamma (gas weighting in edge score) = not reported
Trade-off parameter in w_a = -log pi_a + gamma*g_a; must be tuned; value not disclosed; Section 5.
per-pool price-impact cap = not reported
Applied during allocation to bound slippage; value not specified; Sections 1.1 and 4.
Reference input x_bar_a for marginal proxy = not reported
pi_a = phi'_a(x_bar_a); the reference input is undefined, which affects candidate generation; Section 5.

assumptions (4)

domain assumption Assumption 1: AMM edge functions are nondecreasing, concave, differentiable with finite right derivative at 0.
Needed for Lemma 2 and Theorems 1-3; asserted for all arcs, but not verified for the specific V2/V3/Curve pools used in the empirical engine. Section 3.
ad hoc to paper Path-separable model: no cross-path coupling through shared pools.
Explicitly acknowledged in Section 11; without it the certificate only applies to a simplified model, not to actual routing. Section 3 and Theorem 3.
ad hoc to paper Gas cost is modeled as a linear additive term in the edge score, not as a fixed cost in the allocation objective.
The allocation problem U(delta)=sum y_p(delta_p) has no gas term; gas enters only candidate generation, so the certificate checks a different objective. Sections 4-5.
domain assumption Pool-simple paths are admissible and candidate generation can enumerate k loopless pool-simple paths.
The pool-simple constraint is economically motivated but makes the shortest-path certificate question harder; the paper assumes it can be handled by bookkeeping. Section 3 and 5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Multi-Path Routing in Decentralized Exchange Networks: Convex Allocation and an Improving-Path Certificate." pith.science (2026). https://pith.science/paper/G5MIL7HC

@misc{pith2026260722540,
  author       = {Pith},
  title        = {Pith review of: Multi-Path Routing in Decentralized Exchange Networks: Convex Allocation and an Improving-Path Certificate},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G5MIL7HC}},
  note         = {Machine review of arXiv:2607.22540}
}

read the original abstract

We present a graph-theoretic and convex optimization framework for multi-path routing in decentralized exchange networks, together with its implementation and empirical evaluation on Ethereum mainnet. The framework models the market as a directed token multigraph whose arcs carry AMM exchange functions. Routing is decomposed into two implemented layers: candidate path generation via gas-aware marginal k-shortest-path enumeration, where edge scores embed expected execution cost directly into graph traversal with an explicit pool-simple constraint tracked during path construction, and continuous flow allocation over the selected candidates solved as a concave maximization over a simplex with a per-pool price-impact cap. Under standard concavity and monotonicity assumptions, the KKT conditions imply marginal-output equalization across active paths. The central technical contribution is an improving-path certificate: after solving the allocation on k=20 candidate paths, the KKT multiplier is used as a threshold to determine via a single shortest-path query whether any omitted pool-simple path could improve the current solution; in our implementation the certificate confirms sufficiency in the majority of epochs. Execution is protected by an on-chain slippage tolerance enforced at the smart-contract level. We evaluate the implemented engine against four production DEX aggregators on repeated WETH-USDT quote observations across six trade sizes on Ethereum mainnet: median shortfall is below 5 bps across all sizes and top-3 quote rank exceeds 57% of epochs.

Figures

Figures reproduced from arXiv: 2607.22540 by the authors.

**Figure 2.** Distribution of the ratio between the 8DX quote and the best quote observed in each [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Quantile bands of shortfall in basis points relative to the best observed quote. Bands [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Distribution of quote shortfall in basis points relative to the best observed quote. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 2 canonical work pages

[1]

J. Y. Yen. Finding the k shortest loopless paths in a network.Management Science, 17(11):712–716, 1971.https://doi.org/10.1287/mnsc.17.11.712

doi:10.1287/mnsc.17.11.712 1971
[2]

Angeris, T

G. Angeris, T. Chitra, A. Evans, and S. Boyd. Optimal routing for constant function market makers. InProceedings of the 23rd ACM Conference on Economics and Computation (EC ’22), pages 115–128. ACM, 2022.https://arxiv.org/abs/2204.05238

arXiv 2022
[3]

Angeris and T

G. Angeris and T. Chitra. Improved price oracles: Constant function market makers. In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies (AFT ’20), pages 80–91. ACM, 2020.https://arxiv.org/abs/2003.10001

arXiv 2020
[4]

Adams, N

H. Adams, N. Zinsmeister, M. Salem, D. Robinson, and N. Keefer. Uniswap v3 core. Technical report, Uniswap Labs, 2021.https://uniswap.org/whitepaper-v3.pdf

2021
[5]

Danos, H

V. Danos, H. El Khalloufi, and J. Prat. Global order routing on exchange networks. In Financial Cryptography and Data Security Workshops (FC 2021), pages 207–226. Springer, 2021.https://doi.org/10.1007/978-3-662-63958-0_15

work page doi:10.1007/978-3-662-63958-0_15 2021
[6]

G. M. Guisewite and P. M. Pardalos. Minimum concave-cost network flow problems: Applications, complexity, and algorithms.Annals of Operations Research, 25:75–100, 1990. https://doi.org/10.1007/BF02216922

work page doi:10.1007/bf02216922 1990
[7]

Q. He, S. Ahmed, and G. L. Nemhauser. Minimum concave cost flow over a grid network.Mathematical Programming, 150:79–98, 2015. https://doi.org/10.1007/ s10107-014-0752-6

2015
[8]

Zhang, Y

Y. Zhang, Y. Li, and C. J. Tessone. A line graph-based framework for identifying optimal routing paths in decentralized exchanges.arXiv preprint arXiv:2504.15809, 2025.https: //arxiv.org/abs/2504.15809

arXiv 2025

Show all 11 references

[9]

Zhang and C

Y. Zhang and C. J. Tessone. Extensions of a line-graph-based method for token routing in decentralized exchanges.arXiv preprint arXiv:2509.21152, 2025.https://arxiv.org/ abs/2509.21152

2025
[10]

Xi and C

W. Xi and C. C. Moallemi. Quantifying sub-optimality in routing for automated market makers. Unpublished manuscript, Columbia University, 2025. Cited in [9]; available from the authors upon request

2025
[11]

Boyd and L

S. Boyd and L. Vandenberghe.Convex Optimization. Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/. 13

2004

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [1]

J. Y. Yen. Finding the k shortest loopless paths in a network.Management Science, 17(11):712–716, 1971.https://doi.org/10.1287/mnsc.17.11.712

doi:10.1287/mnsc.17.11.712 1971

[2] [2]

Angeris, T

G. Angeris, T. Chitra, A. Evans, and S. Boyd. Optimal routing for constant function market makers. InProceedings of the 23rd ACM Conference on Economics and Computation (EC ’22), pages 115–128. ACM, 2022.https://arxiv.org/abs/2204.05238

arXiv 2022

[3] [3]

Angeris and T

G. Angeris and T. Chitra. Improved price oracles: Constant function market makers. In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies (AFT ’20), pages 80–91. ACM, 2020.https://arxiv.org/abs/2003.10001

arXiv 2020

[4] [4]

Adams, N

H. Adams, N. Zinsmeister, M. Salem, D. Robinson, and N. Keefer. Uniswap v3 core. Technical report, Uniswap Labs, 2021.https://uniswap.org/whitepaper-v3.pdf

2021

[5] [5]

Danos, H

V. Danos, H. El Khalloufi, and J. Prat. Global order routing on exchange networks. In Financial Cryptography and Data Security Workshops (FC 2021), pages 207–226. Springer, 2021.https://doi.org/10.1007/978-3-662-63958-0_15

work page doi:10.1007/978-3-662-63958-0_15 2021

[6] [6]

G. M. Guisewite and P. M. Pardalos. Minimum concave-cost network flow problems: Applications, complexity, and algorithms.Annals of Operations Research, 25:75–100, 1990. https://doi.org/10.1007/BF02216922

work page doi:10.1007/bf02216922 1990

[7] [7]

Q. He, S. Ahmed, and G. L. Nemhauser. Minimum concave cost flow over a grid network.Mathematical Programming, 150:79–98, 2015. https://doi.org/10.1007/ s10107-014-0752-6

2015

[8] [8]

Zhang, Y

Y. Zhang, Y. Li, and C. J. Tessone. A line graph-based framework for identifying optimal routing paths in decentralized exchanges.arXiv preprint arXiv:2504.15809, 2025.https: //arxiv.org/abs/2504.15809

arXiv 2025