AI model marketplaces host providers with heterogeneous costs and capabilities, and those differences create an opening for computational arbitrage: an intermediary purchases inference from a portfolio of models and resells it to users at a profit. Prior work by Olmedo et al. (2026) demonstrated empirically that such arbitrage is feasible for small model pools. A new paper, "Circumventing the Computational Hardness of Computational Arbitrage" (arXiv:2610.40831v1), addresses what it takes to scale the approach to large marketplaces, where arbitrage strategies must be both computationally tractable and inexpensive to identify and deploy.
The paper illustrates the underlying price dispersion with Terminal-Bench figures: reaching a 40% solve rate can cost anywhere from less than a dollar to more than $60, while reaching 70% can cost from roughly $10 to over $180. The authors note that computational arbitrage is not yet deployed at scale because an arbitrageur must decide how to split an inference budget across models as their number grows, must choose the order in which to query them to avoid unnecessary spending, and must know how each model's success probability varies with queries and budget — quantities the paper describes as generally unavailable and prohibitively expensive to estimate through paid model calls.
The work formalizes arbitrage as a budget-allocation problem in which the intermediary picks a query-independent allocation across models to maximize the probability that at least one output is accepted, subject to a total budget, assuming model outputs are conditionally independent given the query. The authors prove the problem is generally NP-hard. They then show that under Assumption 1 — that the log-failure reduction purchased from each model is non-decreasing and concave in spending, formalizing diminishing returns to inference compute — the objective is jointly concave and a global optimum exists, characterized by KKT conditions and found efficiently via cyclic coordinate ascent on the Lagrangian. The authors call the resulting map from budget to best attainable solve rate the arbitrage frontier; on markets with up to 70 models, tracing the full frontier with their method takes under half a second, whereas the exhaustive grid search used in earlier work would be computationally infeasible at that scale. The paper notes that diminishing returns of this kind have been empirically observed for repeated sampling, chain-of-thought reasoning and post-training.
The KKT conditions yield several economic implications. At the optimum, every funded model delivers the same marginal utility per dollar, so reallocating budget among funded models cannot raise utility. Arbitrage directs revenue away from providers that offer little utility relative to their prices — those whose marginal utility per dollar falls below the shadow price receive no revenue at all — which the authors say disciplines pricing regardless of the billing scheme a provider adopts. The allocation rule also rewards complementary specialization: for a fixed average improvement, a provider gains more by targeting queries on which other models are likely to fail.
On deployment, the paper shows that the arbitrageur can lower realized costs by querying funded models sequentially and stopping once an acceptable solution is found, since order affects spending without changing the allocation's success probability. Finding the optimal fixed order is itself NP-hard, so the authors develop a greedy rule that prioritizes models with the highest expected utility per cost on queries missed by earlier models. Across benchmarks, the greedy ordering closely tracks the best order found by exhaustive search.
For estimation, the authors adapt empirical Bayes estimators, building on distributional strategies for predicting inference-time scaling, to recover query-level utility curves from limited data and reduce the upfront cost of identifying arbitrage strategies. Across six benchmarks, an arbitrageur using this method reaches nearly the same solve rate as one estimating the curves from orders of magnitude more data. Across four agentic and coding benchmarks, the strategy achieves a better cost-performance trade-off than any individual model, according to the paper, which states that code and data are available on GitHub.
Sources: arXiv cs.AI.