绕过计算套利的计算困难性

# Circumventing the Computational Hardness of Computational Arbitrage
Source: [https://arxiv.org/html/2610.40831](https://arxiv.org/html/2610.40831)
Ricardo OlmedoMoritz Hardt

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](https://arxiv.org/html/2610.40831#bib.bib3)\), 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\.

## 1Introduction

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 a40%40\\%\(top\) and a70%70\\%\(bottom\) solve rate on Terminal\-Bench 2\.0\. The figure also shows that the cheapest models differ between the40%40\\%and70%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[SectionD\.1](https://arxiv.org/html/2610.40831#A4.SS1)for experimental details\.The proliferation of AI models with heterogeneous costs and capabilities makes it increasingly difficult for users to decide which service to choose\. Even among models offering comparable performance, inference costs can differ substantially\. For example, reaching a40%40\\%solve rate on Terminal\-Bench can cost anywhere from less than a dollar to more than$60\\$60; reaching70%70\\%can cost from roughly$10\\$10to over$180\\$180\(see[Figure1](https://arxiv.org/html/2610.40831#S1.F1)\)\. Such price dispersion creates the potential for*computational arbitrage*, where an intermediary allocates inference budget across model providers, achieves a given level of performance at a lower cost, and resells it to users at a profit\. Computational arbitrage brings broad economic benefits, including lower consumer prices, reduced market segmentation, and easier market entry for smaller providers\([Olmedo et al\., 2026](https://arxiv.org/html/2610.40831#bib.bib3)\)\.

Despite these benefits, computational arbitrage is not yet deployed at scale in AI marketplaces, due to several challenges\. First, given model prices and capabilities, an arbitrageur must determine how to allocate an inference budget across models to maximize utility\. As the number of models grows, exhaustively searching over possible allocations becomes computationally infeasible\. Second, even after the budget is allocated, the arbitrageur must determine the order in which to query models to avoid unnecessary spending\. Third, computing an effective allocation requires knowing how each model’s success probability varies across queries and inference budgets, quantities that are generally unavailable and prohibitively expensive to estimate, as doing so requires many paid model calls\.

In this work, we address these challenges and show that the optimal arbitrage strategy is both tractable to compute and inexpensive to identify and deploy in large model marketplaces\. Our results yield several interesting economic implications\. At the optimum, every funded model delivers the same marginal utility per dollar\. Revenue therefore flows toward providers whose performance justifies their prices, while those offering little utility relative to their prices receive little or no revenue\. This result contributes to the growing literature on LLM service pricing: regardless of the billing scheme used, a provider’s ability to attract revenue ultimately depends on the utility it delivers per dollar\. Providers can therefore compete in two ways: by offering sufficiently low prices or by specializing in queries that other models are likely to fail; computational arbitrage hence creates an incentive for complementary specialization\.

In more detail, we make the following contributions:

- •Optimal arbitrage strategy\.We formulate arbitrage as a budget\-allocation problem and show that it is generally NP\-hard\. We then show that whenever inference spending has diminishing returns in log\-failure reduction, the objective is jointly concave and its global optimum is computable efficiently even in large model markets\. Across four agentic and coding benchmarks, our arbitrage strategy achieves a better cost–performance trade\-off than any individual model \(see[Figure2](https://arxiv.org/html/2610.40831#S5.F2)\)\.
- •Deployment order\.An arbitrageur can reduce their realized costs by querying funded models sequentially and stopping once an acceptable solution is found\. Although we show that finding the optimal fixed order is NP\-hard, we develop a greedy rule that prioritizes models with the highest expected utility per cost on queries missed by earlier models\. Across benchmarks, our greedy ordering closely tracks the best order found by exhaustive search \(see[Figure4](https://arxiv.org/html/2610.40831#S5.F4)\)\.
- •Sample\-efficient utility estimation\.Building on distributional strategies in predicting inference\-time scaling, we adapt empirical Bayes estimators that recover query\-level utility curves from limited data\. Across six benchmarks, an arbitrageur using our estimation method reaches nearly the same solve rate as an arbitrageur estimating the utility curves from orders of magnitude more data \(see[Figures6](https://arxiv.org/html/2610.40831#S5.F6)and[8](https://arxiv.org/html/2610.40831#A4.F8)\)\.111Code and data are available at[https://github\.com/nastaran75/arbitrage\-markets](https://github.com/nastaran75/arbitrage-markets)\.

## 2The optimal arbitrage strategy

We consider a market ofNNmodel providers where each model can map user queries,x∈𝒳x\\in\{\\mathcal\{X\}\}, to proposed solutionsy∈𝒴y\\in\{\\mathcal\{Y\}\}\. The quality of the solution depends on the model, the difficulty of the query, as well as the amount of inference budget,cc, devoted to the query\. For example, the budget could represent the number of sampling attempts\([Chow et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib20)\)or reasoning effort\([Wei et al\., 2022](https://arxiv.org/html/2610.40831#bib.bib35)\)\. Each modeliihence induces a conditional distributionpi​\(y∣x,c\)p\_\{i\}\(y\\mid x,c\)\. LetA:𝒳×𝒴→\{0,1\}A:\{\\mathcal\{X\}\}\\times\{\\mathcal\{Y\}\}\\to\\\{0,1\\\}indicate whetheryyis an acceptable solution to queryxx\. For a given query distributionx∼Dx\\sim Dand a per\-query budgetCC, a rational user would spend the budget on the model that achieves the highest acceptance rate, i\.e\.,arg​maxi∈\[N\]𝔼x∼D,y∼pi\(⋅∣x,C\)\[A\(x,y\)\]\.\\argmax\_\{i\\in\[N\]\}\\mathbb\{E\}\_\{x\\sim D,y\\sim p\_\{i\}\(\\cdot\\mid x,C\)\}\\left\[A\(x,y\)\\right\]\.Surprisingly, this strategy can be suboptimal even when that model outperforms every other model on every query\. Specifically, diminishing returns to inference spending can make allocating additional budget to a weaker model more valuable than spending it on the dominant model\. Furthermore, allocating the budget across multiple models can exploit*complementary*strengths and provide a further reason to diversify\.222[Examples1](https://arxiv.org/html/2610.40831#Thmexample1)and[2](https://arxiv.org/html/2610.40831#Thmexample2)in[AppendixA](https://arxiv.org/html/2610.40831#A1)provide simple two\-model examples in which distributing the budget among the two models strictly beats every single\-model allocation of the same total budget under both scenarios\.

An arbitrageur is an intermediary who benefits from this gap through diversification\. Rather than allocating the entire budget to the most cost\-effective model, the arbitrageur chooses a query\-independent allocation𝒄=\(c1,…,cN\)∈ℝ≥0N\{\\bm\{c\}\}=\(c\_\{1\},\\dots,c\_\{N\}\)\\in\\mathbb\{R\}\_\{\\geq 0\}^\{N\}, such that∑i∈\[N\]ci≤C\\sum\_\{i\\in\[N\]\}c\_\{i\}\\leq C, i\.e\., for every queryxx, an inference budget ofcic\_\{i\}is allocated to modelii\. Let𝒚=\(y1,…,yN\)\{\\bm\{y\}\}=\(y\_\{1\},\\ldots,y\_\{N\}\)denote the outputs produced by theNNmodels under allocation𝒄\{\\bm\{c\}\}\. We denote their joint distribution asp⁡\(𝒚∣x,𝒄\)p\(\{\\bm\{y\}\}\\mid x,\{\\bm\{c\}\}\), with marginalspi​\(yi∣x,ci\)p\_\{i\}\(y\_\{i\}\\mid x,c\_\{i\}\)\. The arbitrageur wants to maximize the acceptance probability, given the budget, i\.e\.,

maximize𝒄∈ℝ≥0NU\(𝒄\):=𝔼x∼D,𝒚∼p\(⋅∣x,𝒄\)\[1−∏i=1N\(1−A\(x,yi\)\)\]s\.t\.\\displaystyle\\underset\{\{\\bm\{c\}\}\\in\\mathbb\{R\}\_\{\\geq 0\}^\{N\}\}\{\\mathrm\{maximize\}\}\\quad U\(\{\\bm\{c\}\}\):=\\mathbb\{E\}\_\{x\\sim D,\{\\bm\{y\}\}\\sim p\(\\cdot\\mid x,\{\\bm\{c\}\}\)\}\\left\[1\-\\prod\_\{i=1\}^\{N\}\\bigl\(1\-A\(x,y\_\{i\}\)\\bigr\)\\right\]~~\\text\{s\.t\.\}~∑i∈\[N\]ci≤C\.\\displaystyle\\sum\_\{i\\in\[N\]\}c\_\{i\}\\leq C\.\(1\)
The combinatorial nature of the problem makes it computationally intractable:333All proofs can be found in[AppendixB](https://arxiv.org/html/2610.40831#A2)\.

###### Theorem 1\.

Finding the optimal arbitrage policy as in[Equation1](https://arxiv.org/html/2610.40831#S2.E1)is NP\-hard\.

We therefore identify conditions under which the problem becomes tractable\. For each model, we first define the utility functionui:𝒳×ℝ≥0→\[0,1\]u\_\{i\}:\{\\mathcal\{X\}\}\\times\\mathbb\{R\}\_\{\\geq 0\}\\to\[0,1\]asui\(x;ci\):=𝔼y∼pi\(⋅∣x,ci\)\[A\(x,y\)\]u\_\{i\}\(x;c\_\{i\}\):=\\mathbb\{E\}\_\{y\\sim p\_\{i\}\(\\cdot\\mid x,c\_\{i\}\)\}\[A\(x,y\)\], and assume that model outputs are conditionally independent given the query\.444This assumption says that conditional on a query, the sampling processes of different LLMs are mutually independent, a natural assumption made also in prior work \([Ai et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib36), Assumption C\.1;[Farinhas et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib51)\)\. This assumption does not restrict arbitrary overlap in models’ strengths and weaknesses*across*queries\.We can hence rewrite the objective in[Equation1](https://arxiv.org/html/2610.40831#S2.E1)as follows:

U⁡\(𝒄\)\\displaystyle U\(\{\\bm\{c\}\}\)=𝔼x∼D\[1−∏i=1N\(1−ui\(x;ci\)\)\]=𝔼x∼D\[1−e−∑i=1Nαi\(x,ci\)\]s\.t\.∑i∈\[N\]ci≤C,\\displaystyle=\\mathbb\{E\}\_\{x\\sim D\}\\left\[1\-\\prod\_\{i=1\}^\{N\}\(1\-u\_\{i\}\(x;c\_\{i\}\)\)\\right\]=\\mathbb\{E\}\_\{x\\sim D\}\\left\[1\-e^\{\-\\sum\_\{i=1\}^\{N\}\\alpha\_\{i\}\(x,c\_\{i\}\)\}\\right\]~~\\text\{s\.t\.\}\\sum\_\{i\\in\[N\]\}c\_\{i\}\\leq C,\(2\)whereαi​\(x,c\):=−log⁡\(1−ui​\(x,c\)\)\\alpha\_\{i\}\(x;c\):=\-\\log\\bigl\(1\-u\_\{i\}\(x;c\)\\bigr\), i\.e\., the log\-failure reduction on queryxxpurchased withccdollars from modelii\. Conditional independence of model outcomes given a query does not restore tractability;555In the reduction proving[Theorem1](https://arxiv.org/html/2610.40831#Thmtheorem1), acceptance outcomes are conditionally independent given the query\.we therefore impose a natural diminishing property on how model performance scales with inference spending; more formally we have the following assumption:

###### Assumption 1\.

For every modeli∈\[N\]i\\in\[N\]and queryx∈𝒳x\\in\{\\mathcal\{X\}\}, the log\-failure reductionc↦αi​\(x,c\)c\\mapsto\\alpha\_\{i\}\(x,c\)is non\-decreasing and concave onℝ≥0\\mathbb\{R\}\_\{\\geq 0\}\.

[Assumption1](https://arxiv.org/html/2610.40831#Thmassumption1)formalizes diminishing returns to inference compute: it requires the log\-failure reduction purchased from each additional dollar to be non\-increasing\. This property has been empirically observed for common inference\-scaling strategies, including repeated sampling\([Schaeffer et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib25)\), chain\-of\-thought reasoning\([Ghosal et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib24);[Snell et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib23)\), and post\-training\([Chen et al\., 2026](https://arxiv.org/html/2610.40831#bib.bib17)\)\.

This assumption makes the allocation problem tractable:

###### Theorem 2\.

Under[Assumption1](https://arxiv.org/html/2610.40831#Thmassumption1),UUis non\-decreasing and jointly concave\. IfDDhas finite support and eachαi​\(x,⋅\)\\alpha\_\{i\}\(x;\\cdot\)is differentiable, a global optimum exists and is characterized by the KKT conditions\. This optimum can be found efficiently using cyclic coordinate\-ascent on the Lagrangian\.

We call the mapC↦U​\(𝒄⋆​\(C\)\)C\\mapsto U\(\{\\bm\{c\}\}^\{\\star\}\(C\)\), giving the best solve rate attainable at each budget, the*arbitrage frontier*\. We trace this frontier by sweeping the shadow priceλ\\lambdaover a grid and maximizing the LagrangianU⁡\(𝒄\)−λ​∑iciU\(\{\\bm\{c\}\}\)\-\\lambda\\sum\_\{i\}c\_\{i\}at each price by cyclic coordinate ascent;[Algorithm1](https://arxiv.org/html/2610.40831#alg1)provides the pseudocode\. Each coordinate\-ascent sweep requiresNNcoordinate updates, whereas exhaustive grid search, as in[Olmedo et al\. \(2026\)](https://arxiv.org/html/2610.40831#bib.bib3), scales exponentially with the number of models\. On the markets of[Section5](https://arxiv.org/html/2610.40831#S5), with up to7070models, tracing the full frontier using our method takes under half a second, whereas exhaustive search would be computationally infeasible at this scale\.

Algorithm 1Tracing the arbitrage frontier1:utility curves

\{ui​\(x,⋅\)\}x∈𝒟,i∈\[N\]\\\{u\_\{i\}\(x;\\cdot\)\\\}\_\{x\\in\{\\mathcal\{D\}\},i\\in\[N\]\}, shadow prices

λ1\>λ2\>⋯\>λL\>0\\lambda\_\{1\}\>\\lambda\_\{2\}\>\\dots\>\\lambda\_\{L\}\>0, maximum number of sweeps

TT
2:

𝒄←𝟎\{\\bm\{c\}\}\\leftarrow\\mathbf\{0\}
3:for

k=1,…,Lk=1,\\ldots,Ldo⊳\\trianglerightshadow prices decrease, so allocated budgets grow

4:for

t=1,…,Tt=1,\\ldots,Tdo

5:

𝒄old←𝒄\{\\bm\{c\}\}^\{\\mathrm\{old\}\}\\leftarrow\{\\bm\{c\}\}
6:for

i=1,…,Ni=1,\\ldots,Ndo

7:

ci←arg​maxz≥0⁡\{U⁡\(c1,…,ci−1,z,ci\+1,…,cN\)−λk​z\}c\_\{i\}\\leftarrow\\argmax\_\{z\\geq 0\}\\bigl\\\{U\(c\_\{1\},\\ldots,c\_\{i\-1\},z,c\_\{i\+1\},\\ldots,c\_\{N\}\)\-\\lambda\_\{k\}z\\bigr\\\}⊳\\trianglerightU⁡\(𝒄\)U\(\{\\bm\{c\}\}\)as in[Equation2](https://arxiv.org/html/2610.40831#S2.E2)

8:endfor

9:if

𝒄=𝒄old\{\\bm\{c\}\}=\{\\bm\{c\}\}^\{\\mathrm\{old\}\}thenbreak

10:endif

11:endfor

12:

𝒄\(k\)←𝒄\{\\bm\{c\}\}^\{\(k\)\}\\leftarrow\{\\bm\{c\}\}
13:endfor

14:return

\{𝒄\(k\)\}k=1L\\\{\{\\bm\{c\}\}^\{\(k\)\}\\\}\_\{k=1\}^\{L\}⊳\\trianglerightthe frontier: solve rateU⁡\(𝒄\(k\)\)U\(\{\\bm\{c\}\}^\{\(k\)\}\)against total allocated budget∑ici\(k\)\\sum\_\{i\}c^\{\(k\)\}\_\{i\}

The KKT conditions characterizing the optimal allocation in[Theorem2](https://arxiv.org/html/2610.40831#Thmtheorem2)yield several interesting implications discussed below\.

#### No further arbitrage opportunities\.

At the optimum, every funded model delivers the same marginal utility per dollar, i\.e\.,

∂U⁡\(𝒄∗\)∂ci=𝔼x∼D​\[∂αi​\(x,ci∗\)∂ci⏟Marginal log\-failure reductionpurchased per dollar forx​e−∑ℓ=1Nαℓ\(x,cℓ∗\)⏟Probability of failure ofthe model pool onx\]​\{=λ,ci∗\>0,≤λ,ci∗=0\.\\displaystyle\\frac\{\\partial U\(\{\\bm\{c\}\}^\{\*\}\)\}\{\\partial c\_\{i\}\}=\\mathbb\{E\}\_\{x\\sim D\}\\\!\\left\[\\underbrace\{\\frac\{\\partial\\alpha\_\{i\}\(x,c\_\{i\}^\{\*\}\)\}\{\\partial c\_\{i\}\}\}\_\{\\begin\{subarray\}\{c\}\\text\{Marginal log\-failure reduction\}\\\\ \\text\{purchased per dollar for $x$\}\\end\{subarray\}\}\\underbrace\{e^\{\-\\sum\_\{\\ell=1\}^\{N\}\\alpha\_\{\\ell\}\(x,c\_\{\\ell\}^\{\*\}\)\}\}\_\{\\begin\{subarray\}\{c\}\\text\{Probability of failure of\}\\\\ \\text\{the model pool on $x$\}\\end\{subarray\}\}\\right\]\\;\\begin\{cases\}=\\lambda,&c\_\{i\}^\{\*\}\>0,\\\\ \\leq\\lambda,&c\_\{i\}^\{\*\}=0\.\\end\{cases\}\(3\)As a result, reallocation of the budget between funded models cannot raise utility, i\.e\., no more arbitrage possibilities are available, which suggests the existence of a single consistent price system\([Ross, 1978](https://arxiv.org/html/2610.40831#bib.bib48);[Harrison and Kreps, 1979](https://arxiv.org/html/2610.40831#bib.bib49);[Dybvig and Ross, 1987](https://arxiv.org/html/2610.40831#bib.bib46);[Varian, 1987](https://arxiv.org/html/2610.40831#bib.bib50)\)\.

#### Arbitrage against arbitrary pricing\.

A growing line of recent work identifies shortcomings in current LLM pricing practices\([Artola Velasco et al\., 2026b](https://arxiv.org/html/2610.40831#bib.bib4);[Cai et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib18);[Saig et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib19)\), and proposes alternatives such as pay\-per\-character or pay\-for\-performance\. Computational arbitrage offers a complementary perspective: the arbitrageur pays1/λ1/\\lambdadollars per unit of marginal utility from every funded provider, i\.e\., the effective price of marginal utility is equalized across providers, and providers whose marginal utility per dollar falls belowλ\\lambdareceive no revenue at all\. This disciplines pricing regardless of the particular billing scheme each provider adopts\. This mechanism parallels the role of arbitrage in goods markets: arbitrage pushes prices to their fundamental values\([Ross, 1976](https://arxiv.org/html/2610.40831#bib.bib43);[Dybvig and Ross, 1987](https://arxiv.org/html/2610.40831#bib.bib46);[Shleifer, 2000](https://arxiv.org/html/2610.40831#bib.bib47)\), and constrains firms’ ability to sustain discriminatory prices\([Malueg and Schwartz, 1994](https://arxiv.org/html/2610.40831#bib.bib44);[Anderson and Ginsburgh, 1999](https://arxiv.org/html/2610.40831#bib.bib45)\)\.

#### Arbitrage values complementary specialization\.

Fix an allocation𝒄\{\\bm\{c\}\}and the other models’ performance curves\. Suppose provideriimakes a feasible local improvement in its marginal utility per dollar:

∂u~i​\(x,ci\)∂ci=∂α~i​\(x,ci\)∂ci​e−α~i​\(x,ci\)=∂αi​\(x,ci\)∂ci​e−αi​\(x,ci\)\+ε​hi​\(x\),hi​\(x\)≥0\.\\frac\{\\partial\\tilde\{u\}\_\{i\}\(x;c\_\{i\}\)\}\{\\partial c\_\{i\}\}=\\frac\{\\partial\\tilde\{\\alpha\}\_\{i\}\(x,c\_\{i\}\)\}\{\\partial c\_\{i\}\}e^\{\-\\tilde\{\\alpha\}\_\{i\}\(x,c\_\{i\}\)\}=\\frac\{\\partial\\alpha\_\{i\}\(x,c\_\{i\}\)\}\{\\partial c\_\{i\}\}e^\{\-\\alpha\_\{i\}\(x,c\_\{i\}\)\}\+\\varepsilon h\_\{i\}\(x\),\\qquad h\_\{i\}\(x\)\\geq 0\.The resulting change in its marginal contribution is

∂U~​\(𝒄\)∂ci−∂U⁡\(𝒄\)∂ci=ε​𝔼x∼D​\[hi​\(x\)​e−∑ℓ≠iαℓ\(x,cℓ\)⏟Probability of failure ofother models onx\]\.\\frac\{\\partial\\tilde\{U\}\(\{\\bm\{c\}\}\)\}\{\\partial c\_\{i\}\}\-\\frac\{\\partial U\(\{\\bm\{c\}\}\)\}\{\\partial c\_\{i\}\}=\\varepsilon\\,\\mathbb\{E\}\_\{x\\sim D\}\\left\[h\_\{i\}\(x\)\\underbrace\{e^\{\-\\sum\_\{\\ell\\neq i\}\\alpha\_\{\\ell\}\(x,c\_\{\\ell\}\)\}\}\_\{\\begin\{subarray\}\{c\}\\text\{Probability of failure of\}\\\\ \\text\{other models on $x$\}\\end\{subarray\}\}\\right\]\.For a fixed average improvement𝔼x∼D​\[hi​\(x\)\]\\mathbb\{E\}\_\{x\\sim D\}\[h\_\{i\}\(x\)\], targeting queries on which the other models are more likely to fail yields a larger increase in the provider’s marginal contribution\. Furthermore, as competing models improve based on the current allocation, this weight decreases on the queries they address\. Thus, the arbitrage allocation rule values*complementary specialization*\.

## 3Optimal deployment order

The optimal allocation identifies how to distribute inference spending across providers to maximize utility under a given budget\. Deploying this allocation raises a complementary question: in what order should the models be queried? In verifiable domains, the arbitrageur can stop as soon as an acceptable solution is found, so deployment order affects realized spending without changing the allocation’s success probability\. Taking the allocation as fixed, we characterize cost\-minimizing deployment orders and examine their implications for provider revenues and incentives\.

Letπ\\pibe the permutation giving the deployment order\. We use the survival function identity to model the spend on each model; after spendingttdollars on modeliifor solving samplexx, the probability that it has not yet succeeded is1−ui​\(x,t\)1\-u\_\{i\}\(x;t\)\. The expected spend on modeliifor queryxx, conditional on reaching it, is therefore

Ri​\(x,ci\):=∫0ci\(1−ui​\(x,t\)\)​𝑑t\.\\displaystyle R\_\{i\}\(x;c\_\{i\}\):=\\int\_\{0\}^\{c\_\{i\}\}\\bigl\(1\-u\_\{i\}\(x;t\)\\bigr\)\\,\\mathrm\{d\}t\.\(4\)The expected spend for solving queryxxis hence:

Rπ​\(x,𝒄\)=∑i=1NRπ⁡\(i\)​\(x,cπ⁡\(i\)\)​∏j<i\(1−uπ⁡\(j\)​\(x,cπ⁡\(j\)\)\)⏟Probability that allearlier models fail onx\.\\displaystyle R^\{\\pi\}\(x;\{\\bm\{c\}\}\)=\\sum\_\{i=1\}^\{N\}R\_\{\\pi\(i\)\}\(x;c\_\{\\pi\(i\)\}\)\\underbrace\{\\prod\_\{j<i\}\\bigl\(1\-u\_\{\\pi\(j\)\}\(x;c\_\{\\pi\(j\)\}\)\\bigr\)\}\_\{\\begin\{subarray\}\{c\}\\text\{Probability that all\}\\\\ \\text\{ earlier models fail on $x$\}\\end\{subarray\}\}\.\(5\)The query\-dependent cost\-minimizing order then has a simple characterization:

###### Proposition 1\.

For a fixed allocation𝐜\\mathbf\{c\}and instancexx, the orderπ\\pithat minimizesRπ​\(x,𝐜\)R^\{\\pi\}\(x;\\mathbf\{c\}\)queries the models in decreasing order of acceptance probability per expected dollar spent,ui​\(x,ci\)Ri​\(x,ci\)\\frac\{u\_\{i\}\(x;c\_\{i\}\)\}\{R\_\{i\}\(x;c\_\{i\}\)\}\.

The per\-query optimum provides a benchmark for deployment and motivates query\-adaptive ordering when reliable performance predictions are available, paralleling results in LLM routing literature\. Without such predictions, we seek a fixed order that minimizes expected cost across the query population\. In the following, we show that finding the optimal deployment order in this case is NP\-hard, using a reduction from the min\-sum set cover problem\.

###### Theorem 3\.

Finding a fixed deployment order that minimizes𝔼x∼D​\[Rπ​\(x,𝐜\)\]\\mathbb\{E\}\_\{x\\sim D\}\[R^\{\\pi\}\(x;\{\\bm\{c\}\}\)\]is NP\-hard\.

Given this hardness result, we adopt a greedy ordering rule inspired by the 4\-approximation algorithm for min\-sum\-set\-cover\([Feige et al\., 2004](https://arxiv.org/html/2610.40831#bib.bib26)\)\. Starting from an empty set, each time we append the model with the largest reach\-weighted coverage per expected dollar\. LetStS\_\{t\}be the set of models already queried up to stepttand letρSt​\(x\)=∏i∈St\(1−ui​\(x,ci\)\)\\rho\_\{S\_\{t\}\}\(x\)=\\prod\_\{i\\in S\_\{t\}\}\(1\-u\_\{i\}\(x;c\_\{i\}\)\); then our greedy algorithm picks a model at stept\+1t\+1such that:

π⁡\(t\+1\)=arg​maxi∉St⁡𝔼x∼D​\[ρSt​\(x\)​ui​\(x,ci\)\]𝔼x∼D​\[ρSt​\(x\)​Ri​\(x,ci\)\],St=\{π⁡\(1\),…,π⁡\(t\)\},\\displaystyle\\pi\(t\+1\)=\\argmax\_\{i\\notin S\_\{t\}\}\\frac\{\\mathbb\{E\}\_\{x\\sim D\}\[\\rho\_\{S\_\{t\}\}\(x\)\\,u\_\{i\}\(x;c\_\{i\}\)\]\}\{\\mathbb\{E\}\_\{x\\sim D\}\\bigl\[\\rho\_\{S\_\{t\}\}\(x\)\\,R\_\{i\}\(x;c\_\{i\}\)\\bigr\]\},\\qquad S\_\{t\}=\\\{\\pi\(1\),\\dots,\\pi\(t\)\\\},\(6\)i\.e\., the model with the highest expected utility per expected dollar spent on yet unsolved samples\.

#### Arbitrage incentivizes models to either be cheap generalists or specialists\.

Given the above greedy deployment order, model providers can have two strategies for maximizing their revenue\. First note that for every query the probability of reaching theiith model in the order,∏j<i\(1−uπ⁡\(j\)​\(x,cπ⁡\(j\)\)\)\\prod\_\{j<i\}\\bigl\(1\-u\_\{\\pi\(j\)\}\(x;c\_\{\\pi\(j\)\}\)\\bigr\), is the probability that models earlier in the order fail to solve the query, and it decreases monotonically for models later in the sequence\. As a result, there is a clear advantage for providers to appear early in the deployment order\. To do so, they need to offer a competitive utility at a low price, as in the first iteration of the greedy algorithm the model with the highest*average*utility per dollar will be selected\. In later iterations, the models with the highest utility per dollar on*unsolved*queries get selected\. In short, models should either simply be cheap enough to appear early in the deployment order or provide complementary strength, solving queries that remain unresolved\.

## 4Reducing the cost of arbitrage

Computing the optimal allocation requires query\-level utility curves\. Estimating these curves with standard unbiased estimators requires many recorded attempts per model–query pair and since each attempt is a paid model call, collecting them can be prohibitively expensive\. In this section, we adapt a distributional approach to obtain query\-level empirical Bayes estimates from limited observations\.

We consider a repeated sampling strategy666Note that finding the optimal arbitrage strategy remains NP\-hard under repeated sampling with integer sample counts; see[Theorem4](https://arxiv.org/html/2610.40831#Thmtheorem4)in[AppendixB](https://arxiv.org/html/2610.40831#A2)\.and assume thatui​\(x,ci\):=passi,x⁡@​ku\_\{i\}\(x;c\_\{i\}\):=\\operatorname\{pass\}\_\{i,x\}@kwherek=ci/qi​\(x\)k=c\_\{i\}/q\_\{i\}\(x\)withqi​\(x\)q\_\{i\}\(x\)representing the average cost per attempt of modeliion queryxx\. Following prior distributional approaches\([Kazdan et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib2);[Schaeffer et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib25)\), we model one\-shot success probabilities across queries using a model\-specific Beta prior\. Since this prior assigns no mass to exactly zero success probability, we augment it with a point mass at zero for queries that remain unsolvable by a given model under repeated sampling, i\.e\.,

passi,x⁡@​1∼πi​δ0\+\(1−πi\)​Beta​\(ai,bi\),\\operatorname\{pass\}\_\{i,x\}@1\\sim\\pi\_\{i\}\\delta\_\{0\}\+\(1\-\\pi\_\{i\}\)\\text\{Beta\}\(a\_\{i\},b\_\{i\}\),whereδ0\\delta\_\{0\}is a point mass at zero andπi\\pi\_\{i\}is the prior probability that a query has zero success probability for modelii\. To stabilize estimation from few attempts per query, we maximize the log marginal likelihood with an additional penalty52​log⁡\(ai\+bi\)\\frac\{5\}\{2\}\\log\(a\_\{i\}\+b\_\{i\}\)\([Gelman et al\., 2013](https://arxiv.org/html/2610.40831#bib.bib9)\), which discourages the fitted Beta distribution from concentrating around a single success probability\. We fit the parameters by maximization marginal likelihood, i\.e\.,

\(a^i,b^i,π^i\)=arg​maxa,b,π\(a\+b\)−5/2∏x∈𝒟\[π𝟏\{si,x=0\}\+\(1−π\)\(ni,xsi,x\)Beta​\(a\+si,x,b\+ni,x−si,x\)Beta​\(a,b\)\],\\displaystyle\(\\hat\{a\}\_\{i\},\\hat\{b\}\_\{i\},\\hat\{\\pi\}\_\{i\}\)=\\argmax\_\{a,b,\\pi\}\\;\(a\+b\)^\{\-5/2\}\\prod\_\{x\\in\{\\mathcal\{D\}\}\}\\left\[\\pi\\bm\{1\}\\\{s\_\{i,x\}=0\\\}\+\(1\-\\pi\)\\binom\{n\_\{i,x\}\}\{s\_\{i,x\}\}\\frac\{\\text\{Beta\}\(a\+s\_\{i,x\},\\,b\+n\_\{i,x\}\-s\_\{i,x\}\)\}\{\\text\{Beta\}\(a,b\)\}\\right\],whereni,xn\_\{i,x\}is the total number of attempts of modeliifor samplexxandsi,xs\_\{i,x\}is the number of successful such attempts\.

This population\-level estimate is insufficient for computational arbitrage as the arbitrageur depends on the entire matrix of model\-query utility curvesui​\(x,ci\)u\_\{i\}\(x;c\_\{i\}\)to find the optimal allocation\. We therefore adapt the fitted model into a query\-level empirical Bayes estimator\. For every model, the fitted distribution is used as a prior for the query\-specific one\-shot success probability pass@11\. Given the observed attempts for modeliion queryxx, the posterior isπ^i,x​δ0\+\(1−π^i,x\)​Beta​\(a^i\+si,x,b^i\+ni,x−si,x\)\\hat\{\\pi\}\_\{i,x\}\\delta\_\{0\}\+\(1\-\\hat\{\\pi\}\_\{i,x\}\)\\text\{Beta\}\(\\hat\{a\}\_\{i\}\+s\_\{i,x\},\\hat\{b\}\_\{i\}\+n\_\{i,x\}\-s\_\{i,x\}\), whereπ^i,x\\hat\{\\pi\}\_\{i,x\}is the posterior probability that modeliihas zero success probability on queryxx, obtained by updating the fitted prior with the observed attempts\. It is zero whenever at least one success is observed\. Hence, the resulting query\-level pass@kkestimator is

passi,x⁡@​k^=\(1−π^i,x\)​𝔼passi,x⁡@​1∼Beta​\(a^i\+si,x,b^i\+ni,x−si,x\)​\[1−\(1−passi,x⁡@​1\)k\]\.\\displaystyle\\widehat\{\\operatorname\{pass\}\_\{i,x\}@k\}=\(1\-\\hat\{\\pi\}\_\{i,x\}\)\\,\\mathbb\{E\}\_\{\\operatorname\{pass\}\_\{i,x\}@1\\sim\\text\{Beta\}\(\\hat\{a\}\_\{i\}\+s\_\{i,x\},\\hat\{b\}\_\{i\}\+n\_\{i,x\}\-s\_\{i,x\}\)\}\\bigl\[1\-\(1\-\\operatorname\{pass\}\_\{i,x\}@1\)^\{k\}\\bigr\]\.\(7\)In the next section, we show that arbitrage strategies based on our estimates achieve near\-oracle solve rates while requiring orders of magnitude fewer model calls for calibration\.

## 5Experiments

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\.![Refer to caption](https://arxiv.org/html/2610.40831v1/fig_rev_main.png)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[Figure2](https://arxiv.org/html/2610.40831#S5.F2), 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[Equation6](https://arxiv.org/html/2610.40831#S3.E6)\(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, the0%0\\%line\), as a function of the solve rate\. The greedy order matches the best order at the median and stays within10%10\\%of it, whereas cheapest first spends up to16%16\\%more\.Figure 5:Our estimator consistently outperforms the plug\-in estimator\.Distribution over100100random calibration draws of the paired gap in pass@kkRMSE against the oracle reference, averaged over models andk≤500k\\leq 500, withn=8n=8attempts 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[Figure7](https://arxiv.org/html/2610.40831#A4.F7)\.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[Figure5](https://arxiv.org/html/2610.40831#S5.F5)we subsamplen∈\{2,4,8,16\}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,00010\{,\}000per pair on the Monkey Business benchmarks,∼2,500\{\\sim\}2\{,\}500on 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\.In this part we evaluate our proposed arbitrage strategy, based on[Theorem2](https://arxiv.org/html/2610.40831#Thmtheorem2), together with the greedy deployment order, as in[Equation6](https://arxiv.org/html/2610.40831#S3.E6), on four agentic and competitive programming benchmarks with recorded dollar costs for each trial\. We further evaluate our estimator proposed in[Section4](https://arxiv.org/html/2610.40831#S4)on several benchmarks with large public records of repeated sampling\.

### 5\.1Arbitrage on real\-world model markets

We evaluate our arbitrage strategy on recent benchmarks spanning competitive\-programming, agentic command\-line and software\-engineering tasks on real codebases\. They evaluate many models over repeated trials, and, unlike most benchmarks, record what each trial costs, allowing us to study both cost–performance trade\-offs and differences in model strengths\.

We use LiveCodeBench, Terminal\-Bench 2\.0, Terminal\-Bench 4\.0, and DeepSWE\.777Refer to[SectionD\.2](https://arxiv.org/html/2610.40831#A4.SS2)for detailed information about each benchmark\.We estimate the mean cost per attemptqi​\(x\)q\_\{i\}\(x\)for all model–query pairs using the reported cost per trial when available, and otherwise the recorded token counts scaled by public prices as of September 2026\. More details on the experimental setup can be found in[AppendixD](https://arxiv.org/html/2610.40831#A4)\.

For each model–query pair, we estimate the success probabilities under repeated sampling, wherecic\_\{i\}translates tok=ci/qi​\(x\)k=c\_\{i\}/q\_\{i\}\(x\)attempts of modeliion queryxx,888For non\-integerkkthe failure probability decays at a constant rate within an attempt\.using the unbiased estimatorpassi,x⁡@​k:=1−\(ni,x−si,xk\)\(ni,xk\)\\operatorname\{pass\}\_\{i,x\}@k:=1\-\\frac\{\\binom\{n\_\{i,x\}\-s\_\{i,x\}\}\{k\}\}\{\\binom\{n\_\{i,x\}\}\{k\}\}\([Chen et al\., 2021](https://arxiv.org/html/2610.40831#bib.bib1)\), frozen past the recorded attempts\.999With at most55–1010recorded attempts, held\-out queries can only be scored within the recorded attempts\. We therefore fit and evaluate the arbitrage strategy within the recorded attempts\. Our pass@kkestimator proposed in[Section4](https://arxiv.org/html/2610.40831#S4), whose value lies in predicting beyond the recorded attempts, is evaluated in[Section5\.2](https://arxiv.org/html/2610.40831#S5.SS2)on benchmarks with thousands of attempts per pair\.The expected spend under repeated sampling that stops upon success is calculated as in[Equation4](https://arxiv.org/html/2610.40831#S3.E4); for a portfolio, models are queried in the greedy order of[Section3](https://arxiv.org/html/2610.40831#S3)and the expected spend is calculated as in[Equation5](https://arxiv.org/html/2610.40831#S3.E5)\. The arbitrageur’s frontier is traced by sweeping the shadow priceλ\\lambdaover a fixed grid of8686values; at each, the allocation and its deployment order are cross\-validated \(leave\-one\-out on Terminal\-Bench 2\.0 and 4\.0,1010\-fold on LiveCodeBench and DeepSWE\)\. Total cost is expected spend per query summed over the problems\.

[Figure2](https://arxiv.org/html/2610.40831#S5.F2)reports the solve rate of the arbitrageur and all the models alone, against their total spend, which shows thatthe arbitrageur consistently improves the cost–performance frontier\. The largest gains occur at intermediate budgets, where combining models with complementary strengths is most valuable\. It can be seen that DeepSWE is the most concentrated of the four markets: one cheap model is the most cost\-effective arm over most of the budget range, so the arbitrageur tracks it and adds a more expensive model of the same provider only at the highest budgets; its gain there is accordingly the smallest\.

[Figure3](https://arxiv.org/html/2610.40831#S5.F3)shows the revenue share of each model provider under the arbitrage strategy\. 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\. These results suggest thatarbitrage can reduce market segmentation by directing revenue towards multiple providers, including smaller models that offer utility for a competitive price\.[Figure4](https://arxiv.org/html/2610.40831#S5.F4)compares the realized spend of our greedy order proposed in[Section3](https://arxiv.org/html/2610.40831#S3)with the best fixed order of the funded models, computed by an exponential\-time dynamic programming algorithm,101010Note that exponential dynamic programming is possible here because only a handful of models receive non\-zero allocations; in larger markets with more funded models, it can become computationally prohibitive\.and with the common heuristic of querying cheapest models first\.Our greedy order matches the best order at most budgetsand remains consistently close to it, unlike the cheapest\-first order\. On DeepSWE at most three models are funded and both ordering rules recover the best order\.

### 5\.2Arbitrage with estimated utility curves

To evaluate the quality of our estimation method proposed in[Section4](https://arxiv.org/html/2610.40831#S4), we need to determine how much of the solve rate an arbitrageur who uses our method to estimate the utility curves loses, compared to an arbitrageur who finds the true utility curves\. To do so, we utilize benchmarks with many recorded attempts per model–query pair, allowing us to construct high\-precision references for utility curves\. We use MATH \(10 models, 128 problems\) and CodeContests \(5 models, 140 problems\) from the Monkey Business benchmarks\([Brown et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib22)\)which provide10,00010,000recorded binary attempts per query–model pair as well as AIME 2024–2025, Global\-MMLU\-Lite\([Singh et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib41)\), and MMLU\-Pro\([Wang et al\., 2024b](https://arxiv.org/html/2610.40831#bib.bib38)\)\(12 models, 30 problems per benchmark\) where we use the2,5002,500recorded binary attempts per pair from[Truong et al\. \(2026\)](https://arxiv.org/html/2610.40831#bib.bib42)\. None of these benchmarks record a price per attempt, so we price attempts by a compute proxy: model parameters times the model’s mean generation length on the problem\. Results for the MMLU benchmarks are reported in[SectionD\.3](https://arxiv.org/html/2610.40831#A4.SS3)\.

We compare three estimation methods: \(i\) the*oracle*which estimatespassi,x⁡@​k\\operatorname\{pass\}\_\{i,x\}@kbased on all the available attempts using the unbiased estimator, \(ii\) the*plug\-in*which estimates based onnnattempts per model\-query pair, using the plug\-in estimatorp^=si,x/n\\hat\{p\}=s\_\{i,x\}/nand extrapolates1−\(1−p^\)k1\-\(1\-\\hat\{p\}\)^\{k\}to anykk, \(iii\) our*empirical Bayes \(EB\)*estimator which estimates based onnnattempts per pair using[Equation7](https://arxiv.org/html/2610.40831#S4.E7)\.

We first compare our method to the plug\-in estimator in terms of the RMSE of the estimated pass@kkcurves, using the oracle as the ground truth\.[Figure5](https://arxiv.org/html/2610.40831#S5.F5)shows thatour estimator consistently has lower RMSE than the plug\-in estimator, suggesting that pooling information across queries \(through the model\-level prior\) substantially improves utility estimation in the low\-data regime\. We next visualize the solve rate of an arbitrageur using different estimators\.[Figure6](https://arxiv.org/html/2610.40831#S5.F6)summarizes the results where for each oracle solve rate, all methods spend the deployment budget the oracle requires for that rate, and we report medians over1010independent draws\. It can be seen thatan arbitrageur using our estimation method tracks the oracle solve rate which uses up to orders of magnitude more data, and hence more cost\. On the CodeContests benchmark, the plug\-in estimator often observes no successful attempts for a query and therefore assigns itp^=0\\hat\{p\}=0, regardless ofkk\. Its achievable solve rate is consequently limited to queries with at least one observed success\. Our estimator avoids this failure mode by borrowing strength across queries through a model\-specific prior\. Similar results for the MMLU benchmarks are reported in[Figure8](https://arxiv.org/html/2610.40831#A4.F8)\.

## 6Further related work

Model cascading\.In model cascading, models are queried sequentially, typically in increasing order of cost, until a satisfactory solution is found\([Varshney and Baral, 2022](https://arxiv.org/html/2610.40831#bib.bib27);[Wang et al\., 2023b](https://arxiv.org/html/2610.40831#bib.bib28);[Chen et al\., 2023](https://arxiv.org/html/2610.40831#bib.bib29);[Aggarwal et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib8);[Ramírez et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib10)\)\. Computational arbitrage addresses the problem of deciding which models should even be funded and how the inference budget should be distributed among them to maximize performance\. Consequently, an optimal arbitrage strategy may exclude models that are dominated by the rest of the portfolio, and its cost\-minimizing deployment order is not necessarily in increasing model cost\.

Model routing\.Model routing assigns each query to one of the several available models, typically using predicted difficulty, quality, or cost to improve the cost–performance trade\-off\([Shnitzer et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib30);[Ding et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib31);[Lu et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib32);[Šakota et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib33)\)\. Computational arbitrage addresses a complementary problem: rather than selecting a single model, it determines how to distribute inference spending across a portfolio of providers, potentially querying and repeatedly sampling from multiple models for the same query\. Routing could nevertheless strengthen an arbitrage strategy by predicting query\-level model performance\. Conversely, research on model routing can adopt arbitrage strategies as benchmark for algorithm development\.

Inference\-time scaling\.A line of work studies the scaling behavior of LLMs in various aspects including context length\([Xiong et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib6)\), inference optimization\([Snell et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib23)\), and repeated sampling\([Brown et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib22);[Schaeffer et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib25);[Kazdan et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib2)\)\. Our work is most closely related to studies of repeated sampling as we estimate query\-level scaling curves under repeated sampling to identify arbitrage strategies using limited data\. Examining arbitrage strategies under other inference\-time scaling methods such as chain\-of\-thought prompting\([Wei et al\., 2022](https://arxiv.org/html/2610.40831#bib.bib35);[Wang et al\., 2023a](https://arxiv.org/html/2610.40831#bib.bib34)\), majority voting\([Wan et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib14)\), and best\-of\-N\([Kalayci et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib16);[Komiyama et al\., 2026](https://arxiv.org/html/2610.40831#bib.bib15)\)is an interesting direction for future work\.

Economics of LLMs\.A rapidly growing literature addresses the economic roles that LLMs can play in society\([Fish et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib52);[Boehmer et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib53);[Filippas et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib54);[Raman et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib55);[Dütting et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib56)\), examines cost\-aware fine\-tuning\([Laufer et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib5)\), test\-time training\([Chen et al\., 2026](https://arxiv.org/html/2610.40831#bib.bib17)\), evaluation\([Erol et al\., 2026](https://arxiv.org/html/2610.40831#bib.bib13);[Wang et al\., 2024a](https://arxiv.org/html/2610.40831#bib.bib12)\)and pricing and incentive problems in LLM markets, including opacity and potential overcharging\([Artola Velasco et al\., 2026b](https://arxiv.org/html/2610.40831#bib.bib4);[Artola Velasco et al\., 2026a](https://arxiv.org/html/2610.40831#bib.bib11);[Sun et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib7);[Cai et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib18);[Saig et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib19)\)\. We study how computational arbitrage can itself reshape the economics of LLM markets by reallocating demand across them, affecting their revenue shares, and creating incentives for competitive pricing and complementary specialization\.

## 7Conclusion

In this work we take a step towards making computational arbitrage practical in large AI model markets\. We identify a natural condition under which the optimal arbitrage strategy can be computed efficiently\. At this optimal allocation, every funded model provides the same marginal utility per dollar, directing revenue toward providers that are either broadly cost\-effective or specialized in queries that the rest of the portfolio is likely to fail on\. The deployment order reinforces these incentives: inexpensive models with strong average performance tend to be queried early, while complementary specialists remain valuable later in the sequence\. Together, these findings suggest that arbitrage can discipline pricing while rewarding specialization in AI model markets\.

## Acknowledgements

We thank Florian Dorner, Ana\-Andrea Stoica, and Yatong Chen for helpful discussions and valuable feedback on this work\.

## References

- Aggarwalet al\.\(2024\)P\. Aggarwal, A\. Madaan, A\. Anand, S\. P\. Potharaju, S\. Mishra, P\. Zhou, A\. Gupta, D\. Rajagopal, K\. Kappaganthu, Y\. Yang,et al\.AutoMix: automatically mixing language models\.Advances in Neural Information Processing Systems37,pp\. 131000–131034\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p1.1)\.
- Aiet al\.\(2025\)R\. Ai, Y\. Pan, D\. Simchi\-Levi, M\. Tambe, and H\. XuBeyond majority voting: LLM aggregation by leveraging higher\-order information\.arXiv preprint arXiv:2510\.01499\.Cited by:[footnote 4](https://arxiv.org/html/2610.40831#footnote4)\.
- Anderson and Ginsburgh \(1999\)S\. P\. Anderson and V\. A\. GinsburghInternational pricing with costly consumer arbitrage\.Review of International Economics7\(1\),pp\. 126–139\.External Links:[Document](https://dx.doi.org/10.1111/1467-9396.00151)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px2.p1.1)\.
- Artola Velascoet al\.\(2026a\)A\. Artola Velasco, D\. Rontogiannis, S\. Tsirtsis, and M\. Gomez\-RodriguezTest\-time compute games\.InAdvances in Neural Information Processing Systems,Note:To appearCited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Artola Velascoet al\.\(2026b\)A\. Artola Velasco, S\. Tsirtsis, N\. Okati, and M\. Gomez\-RodriguezIs your LLM overcharging you? tokenization, transparency, and incentives\.InProceedings of the 43rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.306\.Note:Oral presentationCited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px2.p1.1),[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Boehmeret al\.\(2025\)N\. Boehmer, S\. Fish, and A\. D\. ProcacciaGenerative social choice: the next generation\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 4627–4659\.External Links:[Link](https://proceedings.mlr.press/v267/boehmer25a.html)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Boyd and Vandenberghe \(2004\)S\. Boyd and L\. VandenbergheConvex optimization\.Cambridge University Press\.Cited by:[Appendix B](https://arxiv.org/html/2610.40831#A2.p11.1.1)\.
- Brownet al\.\(2024\)B\. Brown, J\. Juravsky, R\. Ehrlich, R\. Clark, Q\. V\. Le, C\. Ré, and A\. MirhoseiniLarge language monkeys: scaling inference compute with repeated sampling\.arXiv preprint arXiv:2407\.21787\.Cited by:[§D\.3](https://arxiv.org/html/2610.40831#A4.SS3.p1.1),[§5\.2](https://arxiv.org/html/2610.40831#S5.SS2.p1.1),[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Caiet al\.\(2025\)W\. Cai, T\. Shi, X\. Zhao, and D\. SongAre you getting what you pay for? auditing model substitution in LLM APIs\.InWorkshop on Regulatable Machine Learning at the 39th Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=thhrtv9P0s)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px2.p1.1),[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Chenet al\.\(2023\)L\. Chen, M\. Zaharia, and J\. ZouFrugalGPT: how to use large language models while reducing cost and improving performance\.Transactions on Machine Learning Research\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p1.1)\.
- Chenet al\.\(2021\)M\. Chen, J\. Tworek, H\. Jun, Q\. Yuan, H\. P\. d\. O\. Pinto, J\. Kaplan, H\. Edwards, Y\. Burda, N\. Joseph, G\. Brockman,et al\.Evaluating large language models trained on code\.arXiv preprint arXiv:2107\.03374\.Cited by:[Appendix C](https://arxiv.org/html/2610.40831#A3.p1.1),[§D\.1](https://arxiv.org/html/2610.40831#A4.SS1.p1.1),[§5\.1](https://arxiv.org/html/2610.40831#S5.SS1.p3.1)\.
- Chenet al\.\(2026\)Y\. Chen, G\. Zhang, and M\. HardtLeaderboard incentives: model rankings under strategic post\-training\.InProceedings of the 43rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.306\.External Links:[Link](https://arxiv.org/abs/2603.08371)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.p5.1),[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Chowet al\.\(2025\)Y\. Chow, G\. Tennenholtz, I\. Gur, V\. Zhuang, B\. Dai, A\. Kumar, R\. Agarwal, S\. Thiagarajan, C\. Boutilier, and A\. FaustInference\-aware fine\-tuning for best\-of\-N sampling in large language models\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=77gQUdQhE7)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.p1.1)\.
- Dinget al\.\(2024\)D\. Ding, A\. Mallick, C\. Wang, R\. Sim, S\. Mukherjee, V\. Rühle, L\. V\. S\. Lakshmanan, and A\. H\. AwadallahHybrid LLM: cost\-efficient and quality\-aware query routing\.InThe Twelfth International Conference on Learning Representations,Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p2.1)\.
- Düttinget al\.\(2024\)P\. Dütting, V\. Mirrokni, R\. Paes Leme, H\. Xu, and S\. ZuoMechanism design for large language models\.InProceedings of the ACM Web Conference 2024,pp\. 144–155\.External Links:[Document](https://dx.doi.org/10.1145/3589334.3645511),[Link](https://doi.org/10.1145/3589334.3645511)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Dybvig and Ross \(1987\)P\. H\. Dybvig and S\. A\. RossArbitrage\.InThe New Palgrave: A Dictionary of Economics,J\. Eatwell, M\. Milgate, and P\. Newman \(Eds\.\),Vol\.1,pp\. 100–106\.Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px1.p1.2),[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px2.p1.1)\.
- Erolet al\.\(2026\)M\. H\. Erol, B\. El, M\. Suzgun, M\. Yuksekgonul, and J\. Y\. ZouCost\-of\-pass: an economic framework for evaluating language models\.InInternational Conference on Learning Representations,Vol\.2026,pp\. 34103–34127\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Farinhaset al\.\(2024\)A\. Farinhas, H\. Li, and A\. F\. MartinsReranking laws for language generation: a communication\-theoretic perspective\.Advances in Neural Information Processing Systems37,pp\. 111074–111105\.Cited by:[footnote 4](https://arxiv.org/html/2610.40831#footnote4)\.
- Feigeet al\.\(2004\)U\. Feige, L\. Lovász, and P\. TetaliApproximating min sum set cover\.Algorithmica40\(4\),pp\. 219–234\.Cited by:[Appendix B](https://arxiv.org/html/2610.40831#A2.p17.3.1),[§3](https://arxiv.org/html/2610.40831#S3.p4.1)\.
- Filippaset al\.\(2024\)A\. Filippas, J\. J\. Horton, and B\. S\. ManningLarge language models as simulated economic agents: what can we learn from homo silicus?\.InProceedings of the 25th ACM Conference on Economics and Computation,pp\. 614–615\.External Links:[Document](https://dx.doi.org/10.1145/3670865.3673513),[Link](https://doi.org/10.1145/3670865.3673513)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Fishet al\.\(2024\)S\. Fish, P\. Gölz, D\. C\. Parkes, A\. D\. Procaccia, G\. Rusak, I\. Shapira, and M\. WüthrichGenerative social choice\.InProceedings of the 25th ACM Conference on Economics and Computation,pp\. 985\.External Links:[Document](https://dx.doi.org/10.1145/3670865.3673547),[Link](https://doi.org/10.1145/3670865.3673547)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Gelmanet al\.\(2013\)A\. Gelman, J\. B\. Carlin, H\. S\. Stern, D\. B\. Dunson, A\. Vehtari, and D\. B\. RubinBayesian data analysis\.3 edition,Chapman and Hall/CRC\.Cited by:[§4](https://arxiv.org/html/2610.40831#S4.p2.2)\.
- Ghosalet al\.\(2025\)S\. S\. Ghosal, S\. Chakraborty, A\. Reddy, Y\. Lu, M\. Wang, D\. Manocha, F\. Huang, M\. Ghavamzadeh, and A\. S\. BediDoes thinking more always help? mirage of test\-time scaling in reasoning models\.InAdvances in Neural Information Processing Systems,Vol\.38\.External Links:[Document](https://dx.doi.org/10.52202/085713-5747)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.p5.1)\.
- Harrison and Kreps \(1979\)J\. M\. Harrison and D\. M\. KrepsMartingales and arbitrage in multiperiod securities markets\.Journal of Economic Theory20\(3\),pp\. 381–408\.External Links:[Document](https://dx.doi.org/10.1016/0022-0531%2879%2990043-7)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px1.p1.2)\.
- Jainet al\.\(2025\)N\. Jain, K\. Han, A\. Gu, W\. Li, F\. Yan, T\. Zhang, S\. Wang, A\. Solar\-Lezama, K\. Sen, and I\. StoicaLiveCodeBench: holistic and contamination free evaluation of large language models for code\.InThe Thirteenth International Conference on Learning Representations,Cited by:[§D\.2](https://arxiv.org/html/2610.40831#A4.SS2.p2.1)\.
- Kalayciet al\.\(2025\)Y\. Kalayci, V\. Raman, and S\. DughmiOptimal stopping vs best\-of\-N for inference time optimization\.arXiv preprint arXiv:2510\.01394\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2510.01394)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Kaplanet al\.\(2020\)J\. Kaplan, S\. McCandlish, T\. Henighan, T\. B\. Brown, B\. Chess, R\. Child, S\. Gray, A\. Radford, J\. Wu, and D\. AmodeiScaling laws for neural language models\.arXiv preprint arXiv:2001\.08361\.Cited by:[§D\.3](https://arxiv.org/html/2610.40831#A4.SS3.p1.1)\.
- Karp \(1972\)R\. M\. KarpReducibility among combinatorial problems\.InComplexity of Computer Computations,R\. E\. Miller, J\. W\. Thatcher, and J\. D\. Bohlinger \(Eds\.\),pp\. 85–103\.Cited by:[Appendix B](https://arxiv.org/html/2610.40831#A2.p2.1.1)\.
- Kazdanet al\.\(2025\)J\. Kazdan, R\. Schaeffer, Y\. Allouah, C\. Sullivan, K\. Yu, N\. Levi, and S\. KoyejoEfficient prediction of pass@k scaling in large language models\.arXiv preprint arXiv:2510\.05197\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2510.05197)Cited by:[Appendix C](https://arxiv.org/html/2610.40831#A3.p1.1),[Appendix C](https://arxiv.org/html/2610.40831#A3.p2.1),[§4](https://arxiv.org/html/2610.40831#S4.p2.1),[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Komiyamaet al\.\(2026\)J\. Komiyama, D\. Oba, and M\. OyamadaBest\-of\-infinity: asymptotic performance of test\-time LLM ensembling\.InThe Fourteenth International Conference on Learning Representations,External Links:[Link](https://arxiv.org/abs/2509.21091)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Lauferet al\.\(2024\)B\. Laufer, J\. Kleinberg, and H\. HeidariFine\-tuning games: bargaining and adaptation for general\-purpose models\.InProceedings of the ACM Web Conference 2024,pp\. 66–76\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Luet al\.\(2024\)K\. Lu, H\. Yuan, R\. Lin, J\. Lin, Z\. Yuan, C\. Zhou, and J\. ZhouRouting to the expert: efficient reward\-guided ensemble of large language models\.InProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),pp\. 1964–1974\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p2.1)\.
- Malueg and Schwartz \(1994\)D\. A\. Malueg and M\. SchwartzParallel imports, demand dispersion, and international price discrimination\.Journal of International Economics37\(3–4\),pp\. 167–195\.External Links:[Document](https://dx.doi.org/10.1016/0022-1996%2894%2990044-2)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px2.p1.1)\.
- Olmedoet al\.\(2026\)R\. Olmedo, B\. Schölkopf, and M\. HardtComputational arbitrage in AI model markets\.InProceedings of the 43rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.306\.External Links:[Link](https://arxiv.org/abs/2603.22404)Cited by:[§1](https://arxiv.org/html/2610.40831#S1.p1.1),[§2](https://arxiv.org/html/2610.40831#S2.p7.1),[Abstract](https://arxiv.org/html/2610.40831#abstract1.1)\.
- Ramanet al\.\(2024\)N\. K\. Raman, T\. Lundy, S\. J\. Amouyal, Y\. Levine, K\. Leyton\-Brown, and M\. TennenholtzSTEER: assessing the economic rationality of large language models\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 42026–42047\.External Links:[Link](https://proceedings.mlr.press/v235/raman24b.html)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Ramírezet al\.\(2024\)G\. Ramírez, A\. Birch, and I\. TitovOptimising calls to large language models with uncertainty\-based two\-tier selection\.arXiv preprint arXiv:2405\.02134\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p1.1)\.
- Ross \(1976\)S\. A\. RossThe arbitrage theory of capital asset pricing\.Journal of Economic Theory13\(3\),pp\. 341–360\.External Links:[Document](https://dx.doi.org/10.1016/0022-0531%2876%2990046-6)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px2.p1.1)\.
- Ross \(1978\)S\. A\. RossA simple approach to the valuation of risky streams\.The Journal of Business51\(3\),pp\. 453–475\.External Links:[Document](https://dx.doi.org/10.1086/296008)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px1.p1.2)\.
- Saiget al\.\(2024\)E\. Saig, O\. Einav, and I\. Talgam\-CohenIncentivizing quality text generation via statistical contracts\.InAdvances in Neural Information Processing Systems,Vol\.37\.Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px2.p1.1),[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Šakotaet al\.\(2024\)M\. Šakota, M\. Peyrard, and R\. WestFly\-swat or cannon? cost\-effective language model choice via meta\-modeling\.InProceedings of the 17th ACM International Conference on Web Search and Data Mining,pp\. 606–615\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p2.1)\.
- Schaefferet al\.\(2025\)R\. Schaeffer, J\. Kazdan, J\. Hughes, J\. Juravsky, S\. Price, A\. Lynch, E\. Jones, R\. Kirk, A\. Mirhoseini, and S\. KoyejoHow do large language monkeys get their power \(laws\)?\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 53132–53176\.External Links:[Link](https://proceedings.mlr.press/v267/schaeffer25a.html)Cited by:[Appendix C](https://arxiv.org/html/2610.40831#A3.p1.1),[Appendix C](https://arxiv.org/html/2610.40831#A3.p2.1),[§2](https://arxiv.org/html/2610.40831#S2.p5.1),[§4](https://arxiv.org/html/2610.40831#S4.p2.1),[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Shleifer \(2000\)A\. ShleiferInefficient markets: an introduction to behavioral finance\.Oxford University Press,Oxford\.Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px2.p1.1)\.
- Shnitzeret al\.\(2024\)T\. Shnitzer, A\. Ou, M\. Silva, K\. Soule, Y\. Sun, J\. Solomon, N\. Thompson, and M\. YurochkinLarge language model routing with benchmark datasets\.InFirst Conference on Language Modeling,Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p2.1)\.
- Singhet al\.\(2025\)S\. Singh, A\. Romanou, C\. Fourrier, D\. I\. Adelani, J\. G\. Ngui, D\. Vila\-Suero, P\. Limkonchotiwat, K\. Marchisio, W\. Q\. Leong, Y\. Susanto,et al\.Global MMLU: understanding and addressing cultural and linguistic biases in multilingual evaluation\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 18761–18799\.Cited by:[§D\.3](https://arxiv.org/html/2610.40831#A4.SS3.p2.1),[§5\.2](https://arxiv.org/html/2610.40831#S5.SS2.p1.1)\.
- Snellet al\.\(2025\)C\. Snell, J\. Lee, K\. Xu, and A\. KumarScaling LLM test\-time compute optimally can be more effective than scaling parameters for reasoning\.InThe Thirteenth International Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2610.40831#S2.p5.1),[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Sunet al\.\(2025\)G\. Sun, Z\. Wang, B\. Tian, M\. Liu, Z\. Shen, S\. He, Y\. He, W\. Ye, Y\. Wang, and A\. LiCoIn: counting the invisible reasoning tokens in commercial opaque LLM APIs\.arXiv preprint arXiv:2505\.13778\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2505.13778)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Truonget al\.\(2026\)S\. Truong, Y\. Tu, R\. Schaeffer, and S\. KoyejoItem response scaling laws: a measurement theory approach for efficient and generalizable neural scaling estimation\.InProceedings of the 43rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.306\.External Links:[Link](https://arxiv.org/abs/2606.07616)Cited by:[§D\.3](https://arxiv.org/html/2610.40831#A4.SS3.p1.1),[§D\.3](https://arxiv.org/html/2610.40831#A4.SS3.p2.1),[§5\.2](https://arxiv.org/html/2610.40831#S5.SS2.p1.1)\.
- Varian \(1987\)H\. R\. VarianThe arbitrage principle in financial economics\.Journal of Economic Perspectives1\(2\),pp\. 55–72\.External Links:[Document](https://dx.doi.org/10.1257/jep.1.2.55)Cited by:[§2](https://arxiv.org/html/2610.40831#S2.SS0.SSS0.Px1.p1.2)\.
- Varshney and Baral \(2022\)N\. Varshney and C\. BaralModel cascading: towards jointly improving efficiency and accuracy of NLP systems\.InProceedings of the 2022 Conference on Empirical Methods in Natural Language Processing,pp\. 11007–11021\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p1.1)\.
- Wanet al\.\(2025\)G\. Wan, Z\. S\. Xu, S\. Zorc, M\. Baucells, M\. Hu, H\. Wang, and S\. LiBEACON: bayesian optimal stopping for efficient LLM sampling\.arXiv preprint arXiv:2510\.15945\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2510.15945)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Wanget al\.\(2024a\)J\. Wang, S\. Jain, D\. Zhang, B\. Ray, V\. Kumar, and B\. AthiwaratkunReasoning in token economies: budget\-aware evaluation of LLM reasoning strategies\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,pp\. 19916–19939\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p4.1)\.
- Wanget al\.\(2023a\)X\. Wang, J\. Wei, D\. Schuurmans, Q\. Le, E\. Chi, S\. Narang, A\. Chowdhery, and D\. ZhouSelf\-consistency improves chain of thought reasoning in language models\.InThe Eleventh International Conference on Learning Representations,External Links:[Document](https://dx.doi.org/10.48550/arXiv.2203.11171)Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Wanget al\.\(2023b\)Y\. Wang, K\. Chen, H\. Tan, and K\. GuoTabi: an efficient multi\-level inference system for large language models\.InProceedings of the Eighteenth European Conference on Computer Systems,pp\. 233–248\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p1.1)\.
- Wanget al\.\(2024b\)Y\. Wang, X\. Ma, G\. Zhang, Y\. Ni, A\. Chandra, S\. Guo, W\. Ren, A\. Arulraj, X\. He, Z\. Jiang, T\. Li, M\. Ku, K\. Wang, A\. Zhuang, R\. Fan, X\. Yue, and W\. ChenMMLU\-Pro: a more robust and challenging multi\-task language understanding benchmark\.InAdvances in Neural Information Processing Systems 37, Datasets and Benchmarks Track,Cited by:[§D\.3](https://arxiv.org/html/2610.40831#A4.SS3.p2.1),[§5\.2](https://arxiv.org/html/2610.40831#S5.SS2.p1.1)\.
- Weiet al\.\(2022\)J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, B\. Ichter, F\. Xia, E\. H\. Chi, Q\. V\. Le, and D\. ZhouChain\-of\-thought prompting elicits reasoning in large language models\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 24824–24837\.Cited by:[§2](https://arxiv.org/html/2610.40831#S2.p1.1),[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.
- Xionget al\.\(2024\)W\. Xiong, J\. Liu, I\. Molybog, H\. Zhang, P\. Bhargava, R\. Hou, L\. Martin, R\. Rungta, K\. A\. Sankararaman, B\. Oguz,et al\.Effective long\-context scaling of foundation models\.InProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),pp\. 4643–4663\.Cited by:[§6](https://arxiv.org/html/2610.40831#S6.p3.1)\.

## Appendix AAdditional examples

###### Example 1\(Diversification despite pointwise dominance\)\.

Suppose two models have acceptance probabilities

Pry∼p1\(⋅∣x,c\)\[A\(x,y\)=1\]=1−\(1\+c\)−1,Pry∼p2\(⋅∣x,c\)\[A\(x,y\)=1\]=1−\(1\+c\)−9/10\\Pr\_\{y\\sim p\_\{1\}\(\\cdot\\mid x,c\)\}\[A\(x,y\)=1\]=1\-\(1\+c\)^\{\-1\},\\qquad\\Pr\_\{y\\sim p\_\{2\}\(\\cdot\\mid x,c\)\}\[A\(x,y\)=1\]=1\-\(1\+c\)^\{\-9/10\}on every queryxx, and their outputs are conditionally independent given the query\. Model 1 strictly dominates model 2: at every positive budget, it has a higher acceptance probability on every query\.

With a total budget ofC=2C=2, allocating everything to the dominant model gives

Pry∼p1\(⋅∣x,2\)\[A\(x,y\)=1\]=23\.\\Pr\_\{y\\sim p\_\{1\}\(\\cdot\\mid x,2\)\}\[A\(x,y\)=1\]=\\frac\{2\}\{3\}\.Splitting the budget equally instead gives, with independent outputsyi∼pi\(⋅∣x,1\)y\_\{i\}\\sim p\_\{i\}\(\\cdot\\mid x,1\),

Pr\[A\(x,y1\)=1orA\(x,y2\)=1\]\\displaystyle\\Pr\[A\(x,y\_\{1\}\)=1\\text\{ or \}A\(x,y\_\{2\}\)=1\]=1−Pr\[A\(x,y1\)=0\]Pr\[A\(x,y2\)=0\]\\displaystyle=1\-\\Pr\[A\(x,y\_\{1\}\)=0\]\\Pr\[A\(x,y\_\{2\}\)=0\]=1−2−19/10≈0\.732\>23\.\\displaystyle=1\-2^\{\-19/10\}\\approx 0\.732\>\\frac\{2\}\{3\}\.These acceptance probabilities are the same for every query, so the comparison holds under any query distributionDD\. Thus, even allocating the entire budget to a model that dominates every other model on every query can be suboptimal\. Diminishing returns to spending on the dominant model can make diversification beneficial without complementary strengths across queries\.

###### Example 2\(Diversification through complementary strengths\)\.

Suppose we have two models and the query space is partitioned into two equally likely disjoint regions𝒳=𝒳1⊔𝒳2\{\\mathcal\{X\}\}=\{\\mathcal\{X\}\}\_\{1\}\\sqcup\{\\mathcal\{X\}\}\_\{2\}, withD⁡\(𝒳i\)=1/2D\(\{\\mathcal\{X\}\}\_\{i\}\)=1/2\. Modeliiperforms better on𝒳i\{\\mathcal\{X\}\}\_\{i\}, and its utility is

Pr\[A\(x,y\)=1\]=\{1−e−a​c,x∈𝒳i,1−e−b​c,x∉𝒳i,a\>b\>0\.\\Pr\[A\(x,y\)=1\]=\\begin\{cases\}1\-e^\{\-ac\},&x\\in\{\\mathcal\{X\}\}\_\{i\},\\\\ 1\-e^\{\-bc\},&x\\notin\{\\mathcal\{X\}\}\_\{i\},\\end\{cases\}\\qquad a\>b\>0\.Thus, every model’s performance increases with its allocated budget on every query, but it improves faster on queries in its specialty\. Assume further that the models’ outputs are independent conditional on the query\. Allocating the entire budgetCCto either model gives the average acceptance probability of:

Prx∼D,y∼pi\(\.∣x,C\)\[A\(x,y\)=1\]=1−e−a​C\+e−b​C2\.\\Pr\_\{x\\sim D,y\\sim p\_\{i\}\(\.\\mid x,C\)\}\[A\(x,y\)=1\]=1\-\\frac\{e^\{\-aC\}\+e^\{\-bC\}\}\{2\}\.In contrast, if we allocateci=C/2c\_\{i\}=C/2to every model, for every query we have that

Pr\[A\(x,y1\)=1orA\(x,y2\)=1\]=1−e−C2​\(a\+b\)\>1−e−a​C\+e−b​C2,\\Pr\[A\(x,y\_\{1\}\)=1\\text\{ or \}A\(x,y\_\{2\}\)=1\]=1\-e^\{\-\\frac\{C\}\{2\}\(a\+b\)\}\>1\-\\frac\{e^\{\-aC\}\+e^\{\-bC\}\}\{2\},where the strict inequality follows from the arithmetic–geometric mean inequality\. Hence, at the same spendCCon every query, a diversified portfolio can strictly outperform every single model\.

## Appendix BProofs

See[1](https://arxiv.org/html/2610.40831#Thmtheorem1)

###### Proof\.

We use a standard reduction from Maximum Coverage \(MC\), which is NP\-hard\[[Karp, 1972](https://arxiv.org/html/2610.40831#bib.bib40)\]\. In MC, given a collection of setsS:=\(S1,…,SN\)S:=\(S\_\{1\},\\dots,S\_\{N\}\), the objective is to select at mostBBsets such that the number of covered elements of𝒳\{\\mathcal\{X\}\}is maximized\.

Given an instance of MC, letDDbe a uniform distribution over𝒳\{\\mathcal\{X\}\}\. For each setSiS\_\{i\}, we construct modeliisuch that

Pryi∼pi\(⋅∣x,ci\)\[A\(x,yi\)=1\]=𝟏\{x∈Si\}𝟏\{ci≥1\},\\Pr\_\{y\_\{i\}\\sim p\_\{i\}\(\\cdot\\mid x,c\_\{i\}\)\}\\left\[A\(x,y\_\{i\}\)=1\\right\]=\\bm\{1\}\\\{x\\in S\_\{i\}\\\}\\bm\{1\}\\\{c\_\{i\}\\geq 1\\\},and we setC=BC=B\.

Let𝒄:=\(c1,…,cN\)\{\\bm\{c\}\}:=\(c\_\{1\},\\dots,c\_\{N\}\)be an optimal solution to our problem\. LetI⁡\(𝒄\):=\{i:ci≥1\}I\(\{\\bm\{c\}\}\):=\\\{i:c\_\{i\}\\geq 1\\\}\. Modeliisucceeds deterministically onx∈Six\\in S\_\{i\}whenever a budget of at least 1 is assigned to it, and never succeeds outsideSiS\_\{i\}\. Therefore, the portfolio succeeds onxxexactly whenx∈⋃i∈I⁡\(𝒄\)Six\\in\\bigcup\_\{i\\in I\(\{\\bm\{c\}\}\)\}S\_\{i\}, hence we have that

U⁡\(𝒄\)=\|⋃i∈I⁡\(𝒄\)Si\|\|𝒳\|\.U\(\{\\bm\{c\}\}\)=\\frac\{\\lvert\\bigcup\_\{i\\in I\(\{\\bm\{c\}\}\)\}S\_\{i\}\\rvert\}\{\\lvert\{\\mathcal\{X\}\}\\rvert\}\.
Now for any such optimal solution to our problem we construct a solution to MC where a setSiS\_\{i\}is selected wheneveri∈I⁡\(𝒄\)i\\in I\(\{\\bm\{c\}\}\)\. Note that since eachi∈I⁡\(𝒄\)i\\in I\(\{\\bm\{c\}\}\)receives at least one unit of budget,\|I⁡\(𝒄\)\|≤∑i∈I⁡\(𝒄\)ci≤∑i∈\[N\]ci≤B\\lvert I\(\{\\bm\{c\}\}\)\\rvert\\leq\\sum\_\{i\\in I\(\{\\bm\{c\}\}\)\}c\_\{i\}\\leq\\sum\_\{i\\in\[N\]\}c\_\{i\}\\leq B\.

Conversely, given a solution to MC, we construct a solution to our problem by settingci=1c\_\{i\}=1wheneverSiS\_\{i\}is selected andci=0c\_\{i\}=0otherwise\. Our utility equals the fraction of elements covered by the selected sets, thus maximizingU⁡\(𝒄\)U\(\{\\bm\{c\}\}\)is equivalent to MC up to the constant factor1\|𝒳\|\\frac\{1\}\{\|\{\\mathcal\{X\}\}\|\}\. Given both directions of the proof, our problem is NP\-hard\. ∎

See[2](https://arxiv.org/html/2610.40831#Thmtheorem2)

###### Proof\.

We first show that under[Assumption1](https://arxiv.org/html/2610.40831#Thmassumption1)the objective is monotone and jointly concave over the budget simplexΔ:=\{𝒄∈ℝ≥0N:∑i∈\[N\]ci≤C\}\\Delta:=\\\{\{\\bm\{c\}\}\\in\\mathbb\{R\}\_\{\\geq 0\}^\{N\}:\\sum\_\{i\\in\[N\]\}c\_\{i\}\\leq C\\\}\. As a result, every KKT point is a global optimum\.

We start by proving monotonicity and joint concavity\. Recall thatαi​\(x,c\):=−log⁡\(1−ui​\(x,c\)\)\\alpha\_\{i\}\(x;c\):=\-\\log\(1\-u\_\{i\}\(x;c\)\), and that we can rewrite the objective function in[Equation1](https://arxiv.org/html/2610.40831#S2.E1)as:

U\(𝒄\)=𝔼x∼D\[1−exp\(−∑i=1Nαi\(x;ci\)\)\],U\(\{\\bm\{c\}\}\)=\\mathbb\{E\}\_\{x\\sim D\}\[1\-\\exp\(\-\\sum\_\{i=1\}^\{N\}\\alpha\_\{i\}\(x;c\_\{i\}\)\)\],where by assumption, eachαi​\(x,ci\)\\alpha\_\{i\}\(x;c\_\{i\}\)is non\-decreasing and concave, hence,∑i=1Nαi​\(x,ci\)\\sum\_\{i=1\}^\{N\}\\alpha\_\{i\}\(x;c\_\{i\}\)is jointly concave in𝒄\{\\bm\{c\}\}\. Furthermore,g↦1−exp⁡\(−g\)g\\mapsto 1\-\\exp\(\-g\)is strictly increasing and concave ingg, and hence the composition1−exp\(−∑i=1Nαi\(x;ci\)\)1\-\\exp\(\-\\sum\_\{i=1\}^\{N\}\\alpha\_\{i\}\(x;c\_\{i\}\)\)is also jointly concave in𝒄\{\\bm\{c\}\}\. Taking expectation preserves concavity, hence,U⁡\(𝒄\)U\(\{\\bm\{c\}\}\)is jointly concave in𝒄\{\\bm\{c\}\}\. Monotonicity is immediate from eachαi​\(x,ci\)\\alpha\_\{i\}\(x;c\_\{i\}\)being non\-decreasing\. Since eachαi​\(x,⋅\)\\alpha\_\{i\}\(x,\\cdot\)is differentiable, the portfolio utility for every fixedxx,

1−exp\(−∑i=1Nαi\(x,ci\)\)1\-\\exp\\left\(\-\\sum\_\{i=1\}^\{N\}\\alpha\_\{i\}\(x,c\_\{i\}\)\\right\)is continuous in𝒄\{\\bm\{c\}\}\. SinceDDhas finite support,U⁡\(𝒄\)U\(\{\\bm\{c\}\}\)is a finite weighted sum of these continuous functions and is therefore continuous\. SinceΔ\\Deltais compact, the extreme value theorem guarantees thatUUattains a global maximum onΔ\\Delta\.

The feasible setΔ\\Deltais convex and described by affine constraints\. ForC\>0C\>0, the allocationci=C/\(2​N\)c\_\{i\}=C/\(2N\)is strictly feasible, hence Slater’s condition holds\. Therefore, the KKT conditions are both necessary and sufficient\[[Boyd and Vandenberghe, 2004](https://arxiv.org/html/2610.40831#bib.bib21)\]\. As a result, a global maximizer is characterized by the existence ofλ≥0\\lambda\\geq 0such thatλ⁡\(C−∑i=1Nci∗\)=0\\lambda\(C\-\\sum\_\{i=1\}^\{N\}c\_\{i\}^\{\*\}\)=0, and for alli∈\[N\]i\\in\[N\],

∂U⁡\(𝒄∗\)∂ci=𝔼x∼D​\[∂αi​\(x,ci∗\)∂ci⏟Marginal log\-failure reductionpurchased per dollar forx​e−∑ℓ=1Nαℓ\(x,cℓ∗\)⏟Probability of failure ofthe model pool onx\]​\{=λ,ci∗\>0,≤λ,ci∗=0\.\\displaystyle\\frac\{\\partial U\(\{\\bm\{c\}\}^\{\*\}\)\}\{\\partial c\_\{i\}\}=\\mathbb\{E\}\_\{x\\sim D\}\\\!\\left\[\\underbrace\{\\frac\{\\partial\\alpha\_\{i\}\(x,c\_\{i\}^\{\*\}\)\}\{\\partial c\_\{i\}\}\}\_\{\\begin\{subarray\}\{c\}\\text\{Marginal log\-failure reduction\}\\\\ \\text\{purchased per dollar for $x$\}\\end\{subarray\}\}\\underbrace\{e^\{\-\\sum\_\{\\ell=1\}^\{N\}\\alpha\_\{\\ell\}\(x,c\_\{\\ell\}^\{\*\}\)\}\}\_\{\\begin\{subarray\}\{c\}\\text\{Probability of failure of\}\\\\ \\text\{the model pool on $x$\}\\end\{subarray\}\}\\right\]\\;\\begin\{cases\}=\\lambda,&c\_\{i\}^\{\*\}\>0,\\\\ \\leq\\lambda,&c\_\{i\}^\{\*\}=0\.\\end\{cases\}\(8\)
In practice, we maximizeU⁡\(𝐜\)−λ​∑iciU\(\\mathbf\{c\}\)\-\\lambda\\sum\_\{i\}c\_\{i\}over𝐜≥0\\mathbf\{c\}\\geq 0using coordinate ascent, sweeping the shadow priceλ\\lambdaover a grid\. Refer to[Algorithm1](https://arxiv.org/html/2610.40831#alg1)for pseudocode of the algorithm\.

∎

See[1](https://arxiv.org/html/2610.40831#Thmproposition1)

###### Proof\.

Consider two modelsa,ba,boccupying adjacent positions inπ\\pi, reached with common probabilityρ\\rho\(all earlier models failed\), and abbreviateua:=ua​\(x,ca\)u\_\{a\}:=u\_\{a\}\(x;c\_\{a\}\)andRa:=Ra​\(x,ca\)R\_\{a\}:=R\_\{a\}\(x;c\_\{a\}\)\. Their contribution toRπ​\(x,𝒄\)R^\{\\pi\}\(x;\{\\bm\{c\}\}\)isρ⁡\[Ra\+\(1−ua\)​Rb\]\\rho\\bigl\[R\_\{a\}\+\(1\-u\_\{a\}\)R\_\{b\}\\bigr\]ifaaprecedesbbandρ⁡\[Rb\+\(1−ub\)​Ra\]\\rho\\bigl\[R\_\{b\}\+\(1\-u\_\{b\}\)R\_\{a\}\\bigr\]otherwise\. Every position before the pair is unchanged, and every position after the pair sees the same combined survival probability\(1−ua\)​\(1−ub\)\(1\-u\_\{a\}\)\(1\-u\_\{b\}\)regardless of the pair’s internal order, so a swap changes only this pair’s contribution\. Placingaafirst is weakly better iffRa\+\(1−ua\)​Rb≤Rb\+\(1−ub\)​RaR\_\{a\}\+\(1\-u\_\{a\}\)R\_\{b\}\\leq R\_\{b\}\+\(1\-u\_\{b\}\)R\_\{a\}, i\.e\. iffRa​ub≤Rb​uaR\_\{a\}u\_\{b\}\\leq R\_\{b\}u\_\{a\}, or equivalentlyuaRa≥ubRb\\frac\{u\_\{a\}\}\{R\_\{a\}\}\\geq\\frac\{u\_\{b\}\}\{R\_\{b\}\}\. So by an exchange argument the total cost is minimized by sorting the models in decreasing order of their expected utility per cost on every query\. ∎

See[3](https://arxiv.org/html/2610.40831#Thmtheorem3)

###### Proof\.

We reduce from minimum\-sum set cover\. Let𝒳=\{x1,…,xm\}\\mathcal\{X\}=\\\{x\_\{1\},\\dots,x\_\{m\}\\\}be a universe and let𝒮=\{S1,…,SN\}\\mathcal\{S\}=\\\{S\_\{1\},\\dots,S\_\{N\}\\\}be a collection of sets whose union is𝒳\\mathcal\{X\}\. For a permutationπ\\piof the sets, define the cover time of elementxxby

Tπ​\(x\):=min⁡\{t:x∈Sπ⁡\(t\)\}\.T\_\{\\pi\}\(x\):=\\min\\\{t:x\\in S\_\{\\pi\(t\)\}\\\}\.The minimum\-sum set\-cover problem asks for a permutation minimizing

∑x∈𝒳Tπ​\(x\),\\sum\_\{x\\in\\mathcal\{X\}\}T\_\{\\pi\}\(x\),and is NP\-hard\[[Feige et al\., 2004](https://arxiv.org/html/2610.40831#bib.bib26)\]\.

Construct a model\-ordering instance with one query for everyx∈𝒳x\\in\\mathcal\{X\}, drawn uniformly, and one modelpip\_\{i\}for every setSiS\_\{i\}\. Setqi​\(x\)=ci=1q\_\{i\}\(x\)=c\_\{i\}=1and let modelpip\_\{i\}succeed deterministically exactly on the queries contained inSiS\_\{i\}:

pi​\(x\)=\{1,x∈Si,0,x∉Si\.p\_\{i\}\(x\)=\\begin\{cases\}1,&x\\in S\_\{i\},\\\\ 0,&x\\notin S\_\{i\}\.\\end\{cases\}We interpret the endpoint cases in the survival\-function formulation directly\. Ifx∉Six\\notin S\_\{i\}, then

Ri​\(x,1\)=∫01\(1−pi​\(x\)\)t​𝑑t=1,R\_\{i\}\(x;1\)=\\int\_\{0\}^\{1\}\(1\-p\_\{i\}\(x\)\)^\{t\}\\,\\mathrm\{d\}t=1,whereas ifx∈Six\\in S\_\{i\}, then

Ri​\(x,1\)=∫01\(1−pi​\(x\)\)t​𝑑t=0\.R\_\{i\}\(x;1\)=\\int\_\{0\}^\{1\}\(1\-p\_\{i\}\(x\)\)^\{t\}\\,\\mathrm\{d\}t=0\.For a fixed queryxx, every model preceding the first set containingxxfails and contributes one unit of cost\. The first model whose set containsxxsucceeds and terminates the cascade\. Consequently,

Rπ​\(x,𝐜\)=Tπ​\(x\)−1\.R^\{\\pi\}\(x;\\mathbf\{c\}\)=T\_\{\\pi\}\(x\)\-1\.Taking the expectation under the uniform query distribution gives

𝔼x∼D​\[Rπ​\(x,𝐜\)\]=1m​∑x∈𝒳Tπ​\(x\)−1\.\\mathbb\{E\}\_\{x\\sim D\}\[R^\{\\pi\}\(x;\\mathbf\{c\}\)\]=\\frac\{1\}\{m\}\\sum\_\{x\\in\\mathcal\{X\}\}T\_\{\\pi\}\(x\)\-1\.Therefore, an algorithm that computed the optimal model order would also solve minimum\-sum set cover\. Hence, choosing the cost\-minimizing fixed model order is NP\-hard\. ∎

###### Theorem 4\.

Finding an optimal arbitrage policy is NP\-hard, even under repeated sampling strategy\.

###### Proof\.

We use the same reduction from Maximum Coverage as in the general hardness proof\. Given setsS1,…,SN⊆𝒳S\_\{1\},\\dots,S\_\{N\}\\subseteq\{\\mathcal\{X\}\}and a budget ofBBsets, letDDbe uniform over𝒳\{\\mathcal\{X\}\}, setC=BC=B, and assign each model unit cost per attempt,qi​\(x\)=1q\_\{i\}\(x\)=1\. Define its one\-shot success probability by

passi,x@1=𝟏\{x∈Si\}\.\\operatorname\{pass\}\_\{i,x\}@1=\\bm\{1\}\\\{x\\in S\_\{i\}\\\}\.Forki∈ℤ≥0k\_\{i\}\\in\\mathbb\{Z\}\_\{\\geq 0\}independent attempts, its success probability is

passi,x@ki=\{0,ki=0,1−\(1−passi,x⁡@​1\)ki,ki≥1,=𝟏\{x∈Si\}𝟏\{ki≥1\}\.\\operatorname\{pass\}\_\{i,x\}@k\_\{i\}=\\begin\{cases\}0,&k\_\{i\}=0,\\\\ 1\-\(1\-\\operatorname\{pass\}\_\{i,x\}@1\)^\{k\_\{i\}\},&k\_\{i\}\\geq 1,\\end\{cases\}=\\bm\{1\}\\\{x\\in S\_\{i\}\\\}\\bm\{1\}\\\{k\_\{i\}\\geq 1\\\}\.These deterministic outcomes satisfy conditional independence\. Sinceci=kic\_\{i\}=k\_\{i\}, a feasible allocation satisfies∑iki≤B\\sum\_\{i\}k\_\{i\}\\leq B\. WritingI⁡\(𝐤\)=\{i:ki≥1\}I\(\\mathbf\{k\}\)=\\\{i:k\_\{i\}\\geq 1\\\}, its utility is

U⁡\(𝐤\)=\|⋃i∈I⁡\(𝐤\)Si\|\|𝒳\|,\|I⁡\(𝐤\)\|≤B\.U\(\\mathbf\{k\}\)=\\frac\{\\bigl\|\\bigcup\_\{i\\in I\(\\mathbf\{k\}\)\}S\_\{i\}\\bigr\|\}\{\|\{\\mathcal\{X\}\}\|\},\\qquad\|I\(\\mathbf\{k\}\)\|\\leq B\.Thus every feasible allocation selects at mostBBsets with exactly the same normalized coverage\. Conversely, any selection of at mostBBsets is realized by assigning one attempt to each selected model and zero to the others\. Repeated attempts on a selected model yield no additional utility\. The construction and both mappings are polynomial in the Maximum Coverage input size, so an optimal repeated\-sampling allocation yields an optimal Maximum Coverage solution\. ∎

## Appendix CAdditional details on utility estimation methods

Sampling strategy to estimate pass@k\.An unbiased and stable estimator ofpassi,x⁡@​k\\operatorname\{pass\}\_\{i,x\}@kwas proposed by[Chen et al\. \[2021\]](https://arxiv.org/html/2610.40831#bib.bib1):passi,x⁡@​k^:=1−\(ni,x−si,xk\)\(ni,xk\)\\widehat\{\\operatorname\{pass\}\_\{i,x\}@k\}:=1\-\\frac\{\\binom\{n\_\{i,x\}\-s\_\{i,x\}\}\{k\}\}\{\\binom\{n\_\{i,x\}\}\{k\}\}, whereni,xn\_\{i,x\}is the total number of attempts of modeliifor queryxxandsi,xs\_\{i,x\}is the number of successful such attempts; note that the estimator above requiresni,x≥kn\_\{i,x\}\\geq kattempts\. For large values ofkk, it requires many generations per problem which is costly\. Therefore, in the next part we adopt a distributional strategy\[[Schaeffer et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib25),[Kazdan et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib2)\]to estimatepassi,x⁡@​k\\operatorname\{pass\}\_\{i,x\}@k\.

Distributional strategy to estimate pass@k\.Since attempts are i\.i\.d\.,passi,x⁡@​k\\operatorname\{pass\}\_\{i,x\}@kcan be written aspassi,x⁡@​k=1−\(1−passi,x⁡@​1\)k\\operatorname\{pass\}\_\{i,x\}@k=1\-\(1\-\\operatorname\{pass\}\_\{i,x\}@1\)^\{k\}\. Hence, to estimatepassi,x⁡@​k\\operatorname\{pass\}\_\{i,x\}@k, it suffices to estimatepassi,x⁡@​1\\operatorname\{pass\}\_\{i,x\}@1\.[Schaeffer et al\. \[2025\]](https://arxiv.org/html/2610.40831#bib.bib25)propose a distributional strategy estimator where they first select a prior distribution onpassi,x⁡@​1\\operatorname\{pass\}\_\{i,x\}@1, they discretize this distribution according to the sampling resolution, and fit the distribution’s parameters using MLE under the discretized distribution’s PMF\.[Kazdan et al\. \[2025\]](https://arxiv.org/html/2610.40831#bib.bib2)further show that this discretization introduces bias and propose a strategy which does not require discretization\.

## Appendix DAdditional experimental details

### D\.1Details of the performance\-target experiment

We estimate the success probabilitiesui​\(x,ci\)u\_\{i\}\(x;c\_\{i\}\)under repeated sampling using the unbiased estimator of[Chen et al\. \[2021\]](https://arxiv.org/html/2610.40831#bib.bib1)within the recorded attempts and from the empirical Bayes estimator of[Section4](https://arxiv.org/html/2610.40831#S4)beyond that\. For every model–query pair, we find the expected spend under repeated sampling that stops upon success using the survival function∫0ci\(1−ui​\(x,t\)\)​𝑑t\\int\_\{0\}^\{c\_\{i\}\}\(1\-u\_\{i\}\(x;t\)\)\\,\\mathrm\{d\}t\. We use the same budget for each query, find the probability that the query is solved using that budget, find the average solve rate over the dataset, and increase the budget until the solve rate reaches the target\. Budgets are swept over600600log\-spaced points from$10−4\\$10^\{\-4\}to$10\\$10per task\.

### D\.2Benchmark details

*Terminal\-Bench 2\.0*111111[Terminal\-Bench 2\.0](https://hub.harborframework.com/datasets/terminal-bench/terminal-bench-2/latest)is a benchmark of8888shared agentic software engineering tasks\. Of its submissions,7575agent\-\-model systems publish per\-trial artifacts\.121212[Terminal\-Bench 2\.0 leaderboard submission](https://huggingface.co/datasets/harborframework/terminal-bench-2-leaderboard)We keep the2828that record either a per\-trial dollar cost or usable token counts\. Each model–query pair has at most55recorded attempts with binary outcomes\. We estimate the mean cost per attempt for all model\-\-query pairs using the reported cost per trial when available, and otherwise the recorded input, output, and cached token counts scaled by the LiteLLM price database as of September 2026\.131313[LiteLLM price database snapshot, September 17, 2026](https://github.com/BerriAI/litellm/blob/3d0fd127d5a151f7f094462b16ac9c2a01a047b6/model_prices_and_context_window.json)

*LiveCodeBench*141414[LiveCodeBench leaderboard submissions](https://github.com/LiveCodeBench/submissions)\[[Jain et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib39)\]consists of7373models on713713shared problems, however, only3636models record more than one attempt out of which1010models are reasoning models which do not record reasoning traces so their token cost is not recoverable\. We are hence left with2424models\. Each attempt is treated as a separate request and its input is billed without caching\. We use the model\-specific tokenizer when publicly available andcl100k\_base151515[cl100k\_baseBPE tokenizer](https://tiktokenizer.vercel.app/?model=cl100k_base)as a proxy otherwise\. In this regard note that Terminal\-Bench trials are multi\-turn agent runs whose billed context is not recoverable from the stored logs, so systems that report neither cost nor token counts are excluded rather than priced based on proxy tokenizers\. Prices are taken from the same dated LiteLLM and OpenRouter snapshots as Terminal\-Bench; historical list prices are used for models absent from both snapshots\.

*Terminal\-Bench 4\.0*161616[Terminal\-Bench 4\.0 leaderboard](https://github.com/harbor-framework/terminal-bench/tree/main/leaderboard)provides1212agent–model systems on6666shared tasks with55recorded attempts per \(system, task\)\. Here the leaderboard records the dollar cost of every attempt directly, so no token pricing is needed; one submission whose attempts all report a cost of zero is excluded, as a free arm would be infinitely cheap to the arbitrageur\.

*DeepSWE*171717[DeepSWE v1\.1 public trials](https://deepswe.datacurve.ai/)provides7070\(model, reasoning\-effort\) configurations of2828base models run under a common agent harness on111111shared software\-engineering tasks, with44attempts per pair \(a handful of pairs have fewer\) and a recorded dollar cost per attempt\. As in the main text, every configuration is a distinct arm\.

For all benchmarks, we treat each distinct agent–model pair or model–reasoning\-effort configuration as a separate model\.

### D\.3Experimental details of utility curve estimation

For the Monkey Business benchmarks\[[Brown et al\., 2024](https://arxiv.org/html/2610.40831#bib.bib22)\], the dollar cost of an attempt is not available so we use the number of FLOPs of one generation as the compute proxy which is calculated as the model’s parameter count times the mean number of tokens it generates for that question\[[Kaplan et al\., 2020](https://arxiv.org/html/2610.40831#bib.bib37)\]\. The AIME 2024–2025, Global\-MMLU\-Lite and MMLU\-Pro data are the test\-time scaling experiments of[Truong et al\. \[2026\]](https://arxiv.org/html/2610.40831#bib.bib42): we take the outcomes from their response tensor181818[https://huggingface\.co/datasets/stair\-lab/irsl\_testtime\_resmat2](https://huggingface.co/datasets/stair-lab/irsl_testtime_resmat2)and the length of every response from the accompanying per\-response release,191919[https://huggingface\.co/datasets/stair\-lab/denoise\_eval\_query](https://huggingface.co/datasets/stair-lab/denoise_eval_query)which records the number of generated tokens\. We price an attempt on a question at the model’s active parameter count times the mean number of tokens it generates on that question\.

We report the estimation error of our method on the MMLU benchmarks in[Figure7](https://arxiv.org/html/2610.40831#A4.F7), complementing the four benchmarks in[Figure5](https://arxiv.org/html/2610.40831#S5.F5), and repeat the evaluation of[Figure6](https://arxiv.org/html/2610.40831#S5.F6)on Global\-MMLU\-Lite\[[Singh et al\., 2025](https://arxiv.org/html/2610.40831#bib.bib41)\]and MMLU\-Pro\[[Wang et al\., 2024b](https://arxiv.org/html/2610.40831#bib.bib38)\]\. Results are in[Figure8](https://arxiv.org/html/2610.40831#A4.F8)\. For both, we use the3030questions per benchmark and the∼2,500\\sim 2\{,\}500recorded binary attempts per model–question pair released by[Truong et al\. \[2026\]](https://arxiv.org/html/2610.40831#bib.bib42)for1212open\-weight reasoning models\. As these models are self\-hosted, the per\-attempt cost is the compute proxy above\. Note that only the cost ratios matter to the arbitrageur since scaling every cost by the same constant rescales the budget without changing the allocation\.

Figure 7:Our estimator consistently outperforms the plug\-in estimator\.Distribution over100100random calibration draws of the paired gap in pass@kkRMSE against the oracle reference, averaged over models andk≤500k\\leq 500, withn=8n=8attempts 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 subsamplen∈\{2,4,8,16\}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 the2,5002\{,\}500recorded 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\.