- 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
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 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.
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 denote the true acceptability indicator and an imperfect verifier. Suppose its false-positive and false-negative rates are bounded by under the candidate distributions induced by every feasible allocation. If each feasible allocation generates at most candidates per query, then a union bound gives . Now let maximize true portfolio success and globally maximize the verifier-based objective. Writing , we obtain The middle inequality follows from the optimality of for . Consequently, .
Imperfect verification also changes the expected spend analyzed in Section 3. For a fixed query, let be an attempt’s correctness probability, the verifier’s true-positive rate, and its false-positive rate. The probability of stopping after an attempt is . For a fixed cap of independent attempts, each costing including verification, expected spend is , compared with 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.
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 x, and let Ti(x) denote the expenditure required for provider i to produce a verified solution. When ui(x,t)=Pr(Ti(x)≤t), the survival-function identity gives E[minTi(x),ci]=∫0ciPr(Ti(x)>t)dt=∫0cie−αi(x,t)dt=Ri(x,ci). This is precisely the expected-spend expression introduced in our deployment-order analysis, conditional on reaching provider i. 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⌋ is replaced by the smooth extension (1−p)t/q through the substitution k=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), cost q, and an integer cap of K attempts, the exact expected early-stopping cost is Cdiscrete=q∑j=0K−1(1−p)j=qp1−(1−p)K. Integrating the continuous repeated-sampling extension instead gives Ccontinuous=q−log(1−p)1−(1−p)K. Consequently, Ccontinuous/Cdiscrete=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 ci buys ⌊ci/qi(x)⌋ 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.