acceptodds
Under review as a conference paper at ICLR 2027

Circumventing the Computational Hardness of Computational Arbitrage

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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Computational arbitrage, AI model markets, Economics of LLMs, LLM pricing

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_VCHbOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies computational arbitrage in AI model markets: exploiting differences in model prices and capabilities to allocate inference budgets more effectively and achieve comparable or higher success rates at lower cost. It formulates this task as a resource allocation problem that maximizes the success probability of a model portfolio under a budget constraint, and investigates budget allocation, model deployment order, and low-cost capability estimation. The authors show that optimal budget allocation is NP-hard in general, but becomes an efficiently solvable convex optimization problem when log-failure reduction exhibits diminishing returns. They also propose a greedy deployment order with early stopping and an empirical Bayes method for estimating model success-rate curves from limited observations. Experiments show that the proposed approach improves the cost–performance trade-off over individual models on the evaluated tasks. The greedy deployment order achieves costs close to those of the optimal fixed order, while allocations based on limited calibration data perform similarly to reference allocations derived from substantially more data.

Critical strengths

S1: The problem is relevant and is clearly formulated. Allocating inference budgets across models with heterogeneous prices and complementary capabilities is practically meaningful. The paper usefully separates allocation, deployment order, and utility estimation.

S2: The paper provides useful theoretical characterization. The concavity result identifies a tractable regime, and the associated optimality conditions provide an intuitive explanation of why complementary specialists can remain valuable alongside inexpensive generalists.

S3: The experiments suggest that model portfolios can improve over individual models and that the proposed ordering heuristic can approach the best fixed order on the evaluated instances. The empirical Bayes estimator also appears useful when calibration data are scarce.

Critical weaknesses

W1: The repeated-sampling formulation uses k=c/q, allowing fractional numbers of attempts, while the early-stopping cost is computed through a continuous integral. Actual calls generally incur discrete costs and produce verifiable outcomes only after completion. These approximations may be consequential at small budgets, where an allocation can be smaller than the cost of one call. The paper should provide an explicit executable policy and evaluate the gap between the continuous solution and discrete deployment.

W2: The optimality guarantee does not directly cover the realized-cost objective used in evaluation. Allocation is optimized under a constraint on total committed budget, whereas deployment is evaluated using expected expenditure after early stopping. Optimizing allocation first and ordering second does not establish optimality for success rate under an expected spending constraint. In particular, an expensive fallback may consume little expected expenditure if it is rarely reached.

W3: The evaluation relies on a strong verification assumption. Portfolio success is defined by whether any candidate is acceptable, and early stopping assumes that this can be recognized reliably. This is reasonable for some benchmark settings, but benchmark correctness labels are not necessarily available to a deployed system. The verifier errors and verification costs may sufficiently affect the reported gains.

W4: The diminishing-returns assumption excludes many practically valuable inference processes. The following scenarios can readily violate this assumption or fall outside the formulation:

  • Setup thresholds: An agent may need to read code, install dependencies, and run tests before it has any meaningful chance of success.
  • Reasoning thresholds: A small reasoning budget may be insufficient, with success probability increasing substantially only after a certain threshold is reached.
  • Tool complementarities: Retrieval followed by execution, or execution followed by debugging, may make later computation more valuable than earlier computation.
  • Cross-model collaboration: A plan or error feedback produced by model A may improve model B’s performance.

These processes involve locally increasing returns or interactions between models, whereas the paper primarily models separate attempts by multiple models, with overall success defined by whether at least one attempt succeeds.

Questions for authors

Please address the points that directly correspond to the concerns raised in the Weaknesses section. No new experiments are required. I would consider a higher rating if the authors could clarify these.

5 comments
AuthorsOpenReview ↗

Continuous vs discrete attempts

We thank the reviewer for their thoughtful feedback, which has helped us clarify our assumptions and strengthen the paper. We address each point below.

W1: Continuous vs discrete attempts

We thank the reviewer for highlighting the distinction. Our general formulation allocates an inference budget and is not restricted to repeated sampling or early stopping. That budget can purchase GPU-seconds, FLOPs, energy, tokens, or additional computation within an inference or search procedure, rather than complete calls. Examples include token-budget forcing in s1 [1, Section 3.1], token-budgeted verifier-guided search (pass@T, where T denotes the number of tokens) [2, Section 4.1], and adaptive computation depth in CALM [3, Section 3.2]. These settings offer resource increments finer than a complete response, motivating a continuous approximation when utility varies gradually at that resolution. LLM theorem provers provide another example. ReProver operates under wall-clock search limits [4, Section 6]. Under proportional runtime billing, an allocation specifies how long a provider may compute before termination; it need not purchase an integer number of complete responses. These examples motivate the general resource abstraction.

The early-stopping integral in our paper has an exact interpretation under runtime-based billing. Fix a query xx, and let Ti(x)T_i(x) denote the expenditure required for provider ii to produce a verified solution. When ui(x,t)=Pr⁡(Ti(x)≤t)u_i(x,t)=\Pr(T_i(x)\leq t), the survival-function identity gives E[min⁡Ti(x),ci]=∫0ciPr⁡(Ti(x)>t)dt=∫0cie−αi(x,t)dt=Ri(x,ci).\mathbb{E}[\min\\{T_i(x),c_i\\}]=\int_0^{c_i}\Pr(T_i(x)>t) \mathrm{d}t=\int_0^{c_i}e^{-\alpha_i(x,t)} \mathrm{d}t=R_i(x,c_i). This is precisely the expected-spend expression introduced in our deployment-order analysis, conditional on reaching provider ii. The identity holds even when completion times are discrete. For fixed-cost repeated calls, the approximation arises when the stepwise survival probability (1−p)⌊t/q⌋(1-p)^{\lfloor t/q\rfloor} is replaced by the smooth extension (1−p)t/q(1-p)^{t/q} through the substitution k=t/qk=t/q in Section 4, rather than the integral itself.

We agree that this distinction matters for repeated sampling, particularly at small budgets. For independent attempts with success probability p∈(0,1)p\in(0,1), cost qq, and an integer cap of KK attempts, the exact expected early-stopping cost is Cdiscrete=q∑j=0K−1(1−p)j=q1−(1−p)Kp.C_{\mathrm{discrete}}=q\sum_{j=0}^{K-1}(1-p)^j=q\frac{1-(1-p)^K}{p}. Integrating the continuous repeated-sampling extension instead gives Ccontinuous=q1−(1−p)K−log⁡(1−p).C_{\mathrm{continuous}}=q\frac{1-(1-p)^K}{-\log(1-p)}. Consequently, Ccontinuous/Cdiscrete=p/[−log⁡(1−p)]<1C_{\mathrm{continuous}}/C_{\mathrm{discrete}}=p/[-\log(1-p)]<1.

To quantify this gap in our experiments, we re-ran the whole pipeline with utility estimates based on integer attempt counts and deployment restricted to complete attempts. At deployment, a cap cic_i buys ⌊ci/qi(x)⌋\lfloor c_i/q_i(x)\rfloor complete attempts, with stopping only after a completed attempt is verified as successful. We evaluate expenditure using the exact discrete expected-cost sum, rather than the continuous integral. This plot shows the result. As expected, the frontier no longer extends to the very small budgets reported in the paper, since a model’s cheapest attainable point is now a single full attempt rather than a fraction of one. At matched solve rate, the integer-attempt frontier is more expensive than the continuous one, and it remains cheaper than the best single model on three of the four benchmarks. On DeepSWE, the two are comparable over most of the range.

In the revised version of the paper, we will include the above domains to clearly distinguish the general allocation framework from its repeated-sampling relaxation and include the above-mentioned experiments to clearly mention and quantify the gap for repeated sampling.

[1] Muennighoff, N., et al. (2025). s1: Simple test-time scaling. EMNLP 2025.

[2] Brandfonbrener, D., et al. (2024). VerMCTS: Synthesizing Multi-Step Programs using a Verifier, a Large Language Model, and Tree Search. NeurIPS 2024.

[3] Schuster, T., et al. (2022). Confident Adaptive Language Modeling. NeurIPS 2022.

[4] Yang, K., et al. (2023). LeanDojo: Theorem Proving with Retrieval-Augmented Language Models. NeurIPS 2023.

AuthorsOpenReview ↗

Realized cost vs total budget

W2: Realized cost vs total budget

We thank the reviewer for identifying this distinction. Our formulation considers an arbitrageur who receives CC dollars from the user and must execute the inference procedure without risking expenditure beyond that amount. This choice is motivated by the classical notion of arbitrage, which excludes the possibility of a negative payoff [1, Chapter 1, Second paragraph]. In our setting, we impose the specific operational requirement that the arbitrageur never spends more than the funds received from the user. The arbitrageur therefore commits only to computations it can afford even if every earlier attempt fails.

The reviewer’s expensive-fallback example illustrates this difference. A rarely reached fallback may cost little in expectation, yet require more than the available budget when it is reached. Such a policy could be feasible under an expected-spending constraint while violating the budget guarantee we study. Our formulation excludes this risk of budget overrun. We, however, agree that the optimality statement should be scoped accordingly, and we will make this explicit. Theorem 2 characterizes the optimum of the committed-budget problem; we do not claim that it is optimal for a problem constrained on expected expenditure. Our figures instead provide an empirical comparison where individual models and the arbitrage policy are deployed under the same stopping rule and evaluated using the same expected-expenditure metric.

Please also note that our allocation formulation in Section 2 is not tied to early stopping or deployment-time verification. It also accommodates settings in which the full allocation is executed. For example, when models run in parallel, or their outputs are collected for majority voting, confidence-based selection, or other aggregation procedures. In these settings, the total committed budget remains the relevant expenditure constraint. When verification permits early stopping, our deployment procedure provides additional savings while preserving the chosen allocation’s success probability.

In the revised paper, we will clarify the motivation for the committed-budget constraint, discuss its applicability beyond early-stopping deployments, and explicitly distinguish committed budget from expected expenditure in our evaluation and in the statement of Theorem 2.

[1] Ross, S. A. (2005). Neoclassical Finance. Princeton University Press.

AuthorsOpenReview ↗

Imperfect verifier

W3: Imperfect verifier

Thanks for raising this concern. Please note that both the arbitrageur and the single-model baselines use the same verifier and early-stopping rule. Verification errors and costs therefore apply to all methods, rather than uniquely to the arbitrageur.

Our formulation follows the coverage-based perspective in repeated-sampling work, which measures whether at least one generated candidate is correct [1, 2]. These works similarly distinguish candidate coverage from practical verification, while explicit error models characterize the resulting deployment gap [3]. Our contribution concerns allocation across providers, rather than the design of the verifier, and we will make this scope explicit.

We can however, bound the effect of imperfect verification on the main objective of Section 2. Let A(x,y)A(x,y) denote the true acceptability indicator and A^(x,y)\widehat A(x,y) an imperfect verifier. Suppose its false-positive and false-negative rates are bounded by ϵ\epsilon under the candidate distributions induced by every feasible allocation. If each feasible allocation generates at most Mmax⁡M_{\max} candidates per query, then a union bound gives ∣U(c)−U^(c)∣≤Mmax⁡ϵ|U(\mathbf c) - \widehat U(\mathbf c)|\leq M_{\max}\epsilon. Now let c⋆\mathbf c^\star maximize true portfolio success and c^\widehat{\mathbf c} globally maximize the verifier-based objective. Writing δ=Mmax⁡ϵ\delta=M_{\max}\epsilon, we obtain U(c⋆)≤U^(c⋆)+δ≤U^(c^)+δ≤U(c^)+2δ.U(\mathbf c^\star)\leq\widehat U(\mathbf c^\star)+\delta\leq\widehat U(\widehat{\mathbf c})+\delta\leq U(\widehat{\mathbf c})+2\delta. The middle inequality follows from the optimality of c^\widehat{\mathbf c} for U^\widehat U. Consequently, U(c⋆)−U(c^)≤min⁡1,2Mmax⁡ϵU(\mathbf c^\star)-U(\widehat{\mathbf c})\leq\min\\{1,2M_{\max}\epsilon\\}.

Imperfect verification also changes the expected spend analyzed in Section 3. For a fixed query, let pp be an attempt’s correctness probability, TPTP the verifier’s true-positive rate, and FPFP its false-positive rate. The probability of stopping after an attempt is a=p,TP+(1−p)FPa=p\\,TP+(1-p)FP. For a fixed cap of KK independent attempts, each costing dd including verification, expected spend is R^=d1−(1−a)Ka\widehat R=d\frac{1-(1-a)^K}{a}, compared with R=d1−(1−p)KpR=d\frac{1-(1-p)^K}{p} under perfect verification. High false acceptance rates can hence reduce expenditure through premature stopping, whereas false rejections can increase it. Imperfect verification can hence also affect deployment order. Note, however, that for a fixed allocation and verifier, our ordering rules in Section 3 remain valid under the stated assumptions. We will clarify these points in the revised version of our paper.

[1] Brown, B., Juravsky, J., Ehrlich, R., Clark, R., Le, Q. V., Ré, C., and Mirhoseini, A. (2024). Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. arXiv:2407.21787.

[2] Schaeffer, R., Kazdan, J., Hughes, J., Juravsky, J., Price, S., Lynch, A., Jones, E., Kirk, R., Mirhoseini, A., and Koyejo, S. (2025). How Do Large Language Monkeys Get Their Power (Laws)? ICML.

[3] Dorner, F. E., Chen, Y., Cruz, A. F., and Yang, F. (2026). ROC-n-reroll: How verifier imperfection affects test-time scaling. ICLR.

Reviewer_h1uCOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies computational arbitrage across AI model providers. The main problem is how to split an inference budget across several models to maximize the probability of solving a query. The authors show that the general allocation problem is NP-hard. Under a diminishing-returns assumption, the objective becomes concave and can be optimized efficiently. They also propose a greedy rule for deciding model order and an empirical Bayes method for estimating model utility from few samples.

Experiments on coding and agentic benchmarks show that the resulting portfolio can improve the cost-performance frontier over individual models. The proposed ordering is also close to the best fixed ordering in the tested settings.

Critical strengths
  1. The problem is important and well motivated. Model prices and capabilities vary a lot, so deciding how to combine providers is practically useful.

  2. The theoretical formulation is clean. The paper separates the hard general problem from a tractable case with diminishing returns. The resulting optimality condition also has a useful economic interpretation.

  3. The empirical Bayes result is promising. The estimator gets close to the oracle using only a small number of samples per model-query pair, while the oracle uses thousands.

Critical weaknesses
  1. The tractable formulation relies on fairly strong assumptions. In particular, model outcomes are assumed to be conditionally independent given the query. Models trained on similar data or from similar model families may have strongly correlated failures.

  2. The key diminishing-returns assumption needs more empirical validation. The efficient optimization result depends on concavity of log-failure reduction with spending. It would be useful to show how often real model-query curves satisfy this assumption.

  3. The experimental baselines could be stronger. The main comparison is against individual models, and the ordering experiment compares against cheapest-first and the optimal fixed order. A comparison with modern cost-aware routing or cascading methods would better establish the value of the full arbitrage approach.

Questions for authors
  1. How robust are the results when model failures are correlated rather than conditionally independent?

  2. How often does the diminishing-returns assumption hold in the actual experimental data?

  3. How does the method compare with strong routing or cascading baselines under the same budget?

3 comments
AuthorsOpenReview ↗

Conditional independence of model outcomes

We thank the reviewer for their feedback and for highlighting points that would benefit from clearer explanation. These comments have helped us identify several ways to strengthen our paper. We address each point below.

Conditional independence of model outcomes

Our assumption concerns independent sampling conditional on the full query and fixed model parameters. It does not require models to be marginally independent. The assumption holds when fixed models generate responses using independent randomness for a fixed query, without communication or shared stochastic state, as discussed in footnote 4 in our paper.

Models trained on similar data may succeed on the same easy queries and fail on the same difficult ones. Our formulation explicitly allows this. For example, suppose half the queries are easy, and half are difficult, and both models succeed with probability 0.9 on easy queries and 0.1 on difficult ones. Even with independent sampling on each fixed query, their correctness indicators have correlation 0.64>0 across the benchmark. Before the query is known, observing one model succeed suggests that the query was easy, making the other model’s success more likely. Once the query is fixed, this shared source of uncertainty is removed.

Formally, let X denote a random query, Yi,YjY_i,Y_j the responses from two different models, and Ai=A(X,Yi),Aj=A(X,Yj)A_i =A(X,Y_i),A_j=A(X,Y_j) their correctness indicators. For fixed inference allocations ci,cjc_i, c_j, conditional independence together with the tower rule gives: Cov⁡(Ai,Aj)=Ex[ui(x;ci)uj(x;cj)]−Ex[ui] Ex[uj]=Cov⁡x(ui(x;ci),uj(x;cj)),\operatorname{Cov}(A_i,A_j)=\mathbb{E}_x[u_i(x;c_i)u_j(x;c_j)]-\mathbb{E}_x[u_i]\,\mathbb{E}_x[u_j]=\operatorname{Cov}_x\big(u_i(x;c_i),u_j(x;c_j)\big), which can be large and positive. Failure indicators have the same covariance. Thus, correlated successes or failures across a benchmark do not by themselves violate our assumption.

This assumption is also used commonly in prior work: For example, Ai et al. (ICML 2026) explicitly adopt it while allowing dependence arising from heterogeneous question difficulty [1, Appendix C, Assumption C.1]. Olmedo et al. (ICML 2026) likewise assume that each provider independently attempts every unsolved issue and use the resulting product of failure probabilities to compute portfolio success [2, Section 3, Equation (8)]. In the related setting of LLM-judge aggregation, Sun et al. (ACL 2025) assume that LLM outputs are conditionally independent given the same ground truth and context [3, Section 4].

We acknowledge that conditional independence can fail when models interact or share stochastic environmental factors. Our analysis considers an LLM market in which providers independently generate responses to a fixed query. We will make these boundaries and the distinction between conditional independence and correlated benchmark performance more prominent in the paper. Thank you for highlighting the need to clarify this modeling assumption.

[1] Ai, R., Pan, Y., Simchi-Levi, D., Tambe, M., and Xu, H. (2026). Beyond Majority Voting: LLM Aggregation by Leveraging Higher-Order Information. In Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:1311–1340.

[2] Olmedo, R., Schölkopf, B., and Hardt, M. (2026). Computational Arbitrage in AI Model Markets. In Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:94640–94655.

[3] Sun, G., Kagrecha, A., Manakul, P., Woodland, P., and Gales, M. (2025). SkillAggregation: Reference-free LLM-Dependent Aggregation. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 15532–15548.

AuthorsOpenReview ↗

Diminishing returns assumption

Diminishing returns assumption

We thank the reviewer for this comment. In preparing this response, we found that the monotonicity and concavity requirements in Assumption 1 follow mathematically for mixtures of fixed-rate independent sampling processes, including the query-specific posterior-predictive model used in Section 4 of our paper as well as distributional approaches used in prior work. Formally, we have the following result:

Proposition. Fix a model ii, a query xx, and a per-attempt cost qi(x)>0q_i(x)>0. Let μi,x\mu_{i,x} be a fixed probability distribution on [0,1)[0,1). Conditional on p∼μi,xp\sim\mu_{i,x}, suppose attempts are independent with the same success probability pp. Define the failure probability by F(k)=Ep[(1−p)k],and hence ui(x,c)=1−F(cqi(x)).F(k)=\mathbb{E}_p[(1-p)^k], \text{and hence } u_i(x,c)=1-F\left(\frac{c}{q_i(x)}\right). Then αi(x,c)=−log⁡(1−ui(x,c))\alpha_i(x,c)=-\log(1-u_i(x,c)) is non-decreasing and concave for c≥0c\geq 0.

Proof. For k1,k2≥0k_1,k_2\geq 0 and λ∈(0,1)\lambda\in(0,1), Hölder's inequality gives

F(λk1+(1−λ)k2)=Ep[((1−p)k1)λ((1−p)k2)1−λ]≤F(k1)λF(k2)1−λ.F\bigl(\lambda k_1+(1-\lambda)k_2\bigr)=\mathbb{E}_p\left[\bigl((1-p)^{k_1}\bigr)^\lambda\bigl((1-p)^{k_2}\bigr)^{1-\lambda}\right]\leq F(k_1)^\lambda F(k_2)^{1-\lambda}.

Thus FF is log-convex, so −log⁡F-\log F is concave. Composition with c/qi(x)c/q_i(x) preserves concavity. Monotonicity follows because (1−p)k(1-p)^k is non-increasing in kk. □\square

For a known per-attempt success probability pi(x)∈[0,1)p_i(x)\in[0,1), the mixing distribution is a point mass and αi(x,c)=−cqi(x)log⁡(1−pi(x)),\alpha_i(x,c)=-\frac{c}{q_i(x)}\log(1-p_i(x)), which is linear and therefore satisfies Assumption 1.

This result requires no particular parametric mixing family and includes the Beta and scaled Kumaraswamy distributions considered by Kazdan et al. (2025) [1] and Schaeffer et al. (2025) [2]. It also covers the query-specific empirical-Bayes posterior-predictive curves of Section 4 by construction.

Diminishing returns beyond repeated sampling

We recognize that the proposition does not cover budgets that purchase more reasoning effort for a query, rather than more attempts. While prior work provides evidence of aggregate diminishing returns in reasoning effort (See our references below Assumption 1), they do not establish the per-query log-failure concavity required by Assumption 1.

As a preliminary investigation, we examine the Global-MMLU-Lite and MMLU-Pro records of Truong et al. (2026), used in Section 5.2 of our paper. After submitting the paper, we obtained additional records that allow us to examine the relationship between response length and correctness for individual queries, focusing on six model–benchmark combinations whose responses include reasoning traces.

For each model–query pair, we estimate ui(x,b)u_i(x,b) as the fraction of that model's responses to xx that are correct and complete within bb output tokens. We then plot the resulting normalized log-failure reduction curve for each query. Please find the plots here. The plots show heterogeneous behavior: many curves exhibit an initial region with little improvement, followed by a rapid increase and eventual saturation. Diminishing returns are visually apparent over substantial portions of the budget range, but some curves also exhibit increasing returns beyond the initial low-budget region. We therefore present this analysis as preliminary evidence about per-query behavior, rather than a validation of Assumption 1 for reasoning effort. Also note that these curves measure successful completion before an output cap under the recorded generation policy. They do not directly measure how success changes when the model is instructed to reason for longer.

Despite searching for additional public datasets, we have not identified one with sufficient repeated trials across controlled reasoning budgets to reliably assess per-query curvature. We view characterizing these per-query utility curves as an interesting research direction in its own right and will make this open empirical question explicit in the revision.

We will further add the above proposition and proof, clarify its direct applicability to repeated sampling, and present the reasoning-length analysis with these limitations. We will also revise the discussion below Assumption 1 to distinguish aggregate empirical observations from evidence for per-query log-failure reduction concavity. We thank the reviewer for prompting these changes.

[1] Kazdan, J., Schaeffer, R., Allouah, Y., Sullivan, C., Yu, K., Levi, N., and Koyejo, S. (2025). Efficient Prediction of Pass@k Scaling in Large Language Models. arXiv:2510.05197.

[2] Schaeffer, R., Kazdan, J., Hughes, J., Juravsky, J., Price, S., Lynch, A., Jones, E., Kirk, R., Mirhoseini, A., and Koyejo, S. (2025). How Do Large Language Monkeys Get Their Power (Laws)? In Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:53132–53176.

AuthorsOpenReview ↗

Relations to cascading and routing

Relations to cascading and routing

Routing and cascading share our goal of improving aggregate performance, but their standard formulations differ from ours in several important respects. Matching the monetary budget alone would therefore not yield a comparison under the same deployment capabilities.

First, our allocation and deployment order are determined offline and shared across queries. At deployment, the policy follows this predetermined schedule and stops when the verifier accepts a response. It requires no additional learned router or response-quality predictor, and incurs no routing-model inference overhead. In contrast, RouteLLM [1] selects a model based on the incoming query, while adaptive cascading methods [2, 3] use intermediate responses or estimated quality to determine whether to continue. Our framework asks: “For this task distribution and budget, how should inference expenditure be allocated across the available models?”

Second, our framework optimizes how much inference budget to allocate to each model, rather than only which model to invoke, alongside model selection and deployment order. This is particularly important when several attempts from a cheaper model substantially improve its success probability while still costing less than a single invocation of a more expensive model. Escalating after one unsuccessful attempt can then miss a more cost-effective option, which is retrying the cheaper model. Standard routing selects a single model, while standard cascading formulations generally consider one invocation of each selected model. Incorporating this decision would require adapting their action spaces and optimization procedures.

We thank the reviewer for raising this concern and will clarify these distinctions and extend the discussion about routing and cascading in the related work.

[1] Ong, I., et al. (2025). RouteLLM: Learning to Route LLMs with Preference Data. ICLR 2025

[2] Chen, L., Zaharia, M., and Zou, J. (2023). FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance. arXiv:2305.05176.

[3] Dekoninck, J., Baader, M., and Vechev, M. (2025). A Unified Approach to Routing and Cascading for LLMs. ICML 2025

Reviewer_E3i8OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The authors prove arbitrage is IN General NP-hard.

Critical strengths

The authors made an effort for the committee to review their work.

Critical weaknesses

The authors do not know the NP hardness is a well known.

Questions for authors

Why do you write a paper without knowing the simple results in the field?

1 comment
AuthorsOpenReview ↗

Clarification of the paper’s contributions

We agree that NP-hardness is established for many allocation problems, and we do not claim that the computational hardness of resource allocation is itself new. Our result establishes hardness for the specific inference-allocation problem formulated in this paper. Could the reviewer identify the prior result they consider equivalent to ours?

More importantly, the NP-hardness result is only one component of our contribution, rather than the paper's central goal. We first translate inference across heterogeneous providers into an allocation problem that connects monetary budgets, query-dependent success probabilities, and portfolio utility. We then identify conditions under which optimal allocation becomes tractable, analyze deployment order and early-stopping expenditure, conduct an extensive empirical evaluation across heterogeneous models and benchmarks, and develop economic insights into how arbitrage affects providers’ incentives, market prices, and complementary specialization.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.