Circumventing the Computational Hardness of Computational Arbitrage

Nastaran Okati; Ricardo Olmedo; Moritz Hardt

cs.AIOct 29, 2026

Circumventing the Computational Hardness of Computational Arbitrage

Authors: Nastaran Okati, Ricardo Olmedo, Moritz Hardt

Organizations: Max Planck Institute for Intelligent Systems, and Tübingen AI Center

Abstract

AI model marketplaces host providers with heterogeneous costs and capabilities. These differences create an opportunity for computational arbitrage (Olmedo et al., 2026), in which an intermediary purchases inference from a portfolio of models and resells it to users at a profit. Beyond creating profit opportunities for the arbitrageur, computational arbitrage offers financial value to both consumers and providers and could therefore significantly influence AI model markets. While prior work empirically demonstrates the feasibility of computational arbitrage for small model pools, scaling it to large marketplaces requires arbitrage strategies that are both computationally tractable and inexpensive to identify and deploy. In this work, we formalize computational arbitrage as an allocation problem and prove that it is generally NP-hard. However, we show that the optimal allocation can be computed efficiently under a natural diminishing-returns condition on how model performance scales with inference spending. We further develop a sample-efficient method for estimating model performance from limited data, reducing the upfront cost of identifying arbitrage strategies. Our analysis also yields several economic insights: at the optimum, every funded model delivers the same marginal utility per dollar; arbitrage directs revenue away from providers offering little utility relative to their prices; and it rewards complementary specialization.

Figures & tables

Figure 1: The cost of a given performance target varies by more than an order of magnitude across the market. Expected total cost for each model to reach a

40\%

(top) and a

70\%

(bottom) solve rate on Terminal-Bench 2.0. The figure also shows that the cheapest models differ between the

40\%

and

70\%

targets, indicating that relative cost-effectiveness varies with the desired solve rate. For each model, we give every query the same budget, compute the probability that repeated sampling solves it before the budget is exhausted, and increase the budget until the average solve rate reaches the target. “NA” marks a model that does not reach the target within the budget range considered. Prices are based on the reported cost per trial when available, and otherwise token counts scaled by the LiteLLM price database as of September 2026. Refer to Section D.1 for experimental details.

Figure 2: Arbitrageur improves the cost–performance frontier. Solve rate against total cost on four benchmarks. Each blue curve is one model funded on its own by repeated sampling with early stopping when a solution is found. The arbitrage gain is largest in the mid-budget regime, where models’ strengths are most complementary. DeepSWE is the most concentrated of the four markets where one cheap model is the most cost-effective.

Figure 3: Revenue spreads across providers as budgets increase. Revenue share of each funded provider as a function of the budget per task under the arbitrageur’s cross-validated allocation of Figure 2 , one row per system sorted by per-attempt price (cheapest on top). At lower budgets, revenue goes entirely to the cheaper models; as the budget grows, it spreads among more providers, and even at high budgets cheap models retain a significant share of the revenue. In DeepSWE, a few cheap configurations of one provider offer the highest utility per dollar over most of the budget range.

Figure 4: The greedy deployment order is close to the best fixed order. Expected spend of the arbitrageur’s allocation when the funded models are queried in the greedy order of Equation 6 (solid) or in increasing order of average cost per attempt (dashed), relative to the best fixed order of the funded models found by exact dynamic programming (which remains exponential in the number of funded models, the

0\%

line), as a function of the solve rate. The greedy order matches the best order at the median and stays within

10\%

of it, whereas cheapest first spends up to

16\%

more.

Figure 5: Our estimator consistently outperforms the plug-in estimator. Distribution over

100

random calibration draws of the paired gap in pass@

k

RMSE against the oracle reference, averaged over models and

k\leq 500

, with

n=8

attempts per query–model pair, on MATH, CodeContests, AIME 2024 and AIME 2025; the two estimators are fitted on the same subsample of each draw. The dashed line marks no difference; mass to its right means our estimator is more accurate on that draw, and the annotation gives the share of such draws. The gap is positive on every draw on all benchmarks showing that our estimator consistently has lower RMSE than the plug-in estimator. Results for the MMLU benchmarks are shown in Figure 7 .

Figure 6: An arbitrageur using our estimation method approaches the solve rate of an arbitrageur using the oracle utility curves which use several orders of magnitude more data. On each benchmark of Figure 5 we subsample

n\in\{2,4,8,16\}

attempts per query–model pair, re-estimate the utility curves, run the arbitrage on the estimates and plot the achieved solve rate; the oracle uses all recorded attempts (

10{,}000

per pair on the Monkey Business benchmarks,

{\sim}2{,}500

on AIME) and is the diagonal. For each oracle solve rate we find the budget that the oracle needs to achieve that solve rate and use the same budget for other methods.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Our estimator consistently outperforms the plug-in estimator. Distribution over

100

random calibration draws of the paired gap in pass@

k

RMSE against the oracle reference, averaged over models and

k\leq 500

, with

n=8

attempts per query–model pair, on Global-MMLU-Lite and MMLU-Pro; the two estimators are fitted on the same subsample of each draw. The dashed line marks no difference; mass to its right means our estimator is more accurate on that draw, and the annotation gives the share of such draws. The gap is positive on every draw on all benchmarks showing that our estimator consistently has lower RMSE than the plug-in estimator.

Figure 8: An arbitrageur using our estimation method tracks the solve rate of an arbitrageur using the oracle utility curves which are calculated using several orders of magnitude more data. On each of the MMLU benchmarks, we subsample

n\in\{2,4,8,16\}

attempts per query–model pair, re-estimate the utility curves, run the arbitrage on the estimates and plot the achieved solve rate; the oracle uses all the

2{,}500

recorded attempts and is the diagonal. For each oracle solve rate we find the budget that the oracle needs to achieve that solve rate and use the same budget for the other methods.

Cost-Aware Inference

Cost-aware inference allocates models, computation, and serving resources to meet quality goals at lower latency, energy use, and monetary cost.

See all 298 papers

Computational Arbitrage in AI Model Markets
Mar 23, 2026Ricardo Olmedo, Bernhard Schölkopf, Moritz HardtCost-Aware Inference
Max Planck Institute for Intelligent Systems, Tübingen
A Compute Center Anyone Can Join: A Peer-to-Peer System for AI Inference
Nov 1, 2026Yimo Lin, Zhen ZhangDistributed Inference Verifiable Outsourced Computation
Yunyong Century (Beijing) Artificial Intelligence Technology Co., Ltd. · Tsinghua University
Test-Time Compute Games
Jan 29, 2026Ander Artola Velasco, Dimitrios Rontogiannis, Stratis Tsirtsis +1LLM Serving Cost-Aware Inference
Max Planck Institute for Software Systems, Kaiserslautern, Germany · Hasso Plattner Institute, Potsdam, Germany

Mar 23, 2026J/K move · Enter open · S save

Computational Arbitrage in AI Model Markets

Ricardo Olmedo, Bernhard Schölkopf, Moritz Hardt

Max Planck Institute for Intelligent Systems, Tübingen

Cost-Aware Inference

Open paper AskPDF arXiv

Consider a market of competing model providers selling query access to models with varying costs and capabilities. Customers submit problem instances and are willing to pay up to a budget for a verifiable solution. An arbitrageur efficiently allocates inference budget across providers to undercut the market, thus creating a competitive offering with no model-development risk. In this work, we initiate the study of arbitrage in AI model markets, empirically demonstrating the viability of arbitrage and illustrating its economic consequences. We conduct an in-depth case study of SWE-bench GitHub issue resolution using two representative models, GPT-5 mini and DeepSeek v3.2. In this verifiable domain, simple arbitrage strategies generate net profit margins of up to 40%. Robust arbitrage strategies that generalize across different domains remain profitable. Distillation further creates strong arbitrage opportunities, potentially at the expense of the teacher model's revenue. Multiple competing arbitrageurs drive down consumer prices, reducing the marginal revenue of model providers. At the same time, arbitrage reduces market segmentation and facilitates market entry for smaller model providers by enabling earlier revenue capture. Our results suggest that arbitrage can be a powerful force in AI model markets with implications for model development, distillation, and deployment.

Abstract

Cost-Aware Inference

Explore similar work

Computational Arbitrage in AI Model Markets

A Compute Center Anyone Can Join: A Peer-to-Peer System for AI Inference

Test-Time Compute Games