acceptodds
Under review as a conference paper at ICLR 2027

Pareto Frontier of LLM Test-Time Compute: Adaptive Rollouts and Voting Under Token Budgets

Abstract

Large language models improve their test-time accuracy by generating multiple rollouts and aggregating them to produce a final answer by voting. As each additional rollout incurs token costs, test-time compute entails a trade-off between accuracy and inference cost. This raises a question: given a limited token budget, how should the budget be allocated to maximize accuracy? Existing approaches typically adapt the number of rollouts to each query while keeping the voting rule fixed. However, the voting rule itself shall be adapted as well. In particular, commonly used schemes such as self-consistency and best-of- can be viewed as special cases of a broader Boltzmann voting family, and the choice of voting rule directly affects the attainable accuracy ceiling of test-time compute. Motivated by this observation, we formulate the rollout count and voting rule as joint, query-dependent decisions and optimize them under a token-budget constraint. We show that no fixed voting rule is uniformly optimal across all token budgets, whereas the adaptive voting rule yields a cost–accuracy Pareto frontier that dominates the frontier associated with any fixed rule. We further derive a closed-form characterization of the large-budget asymptotics of the Pareto frontier, identifying both the factors that determine the accuracy ceiling and those that govern the rate at which this ceiling is approached. Guided by these results, we propose **PRICE** (**P**riced **R**ollouts and **I**nference-time voting-rule **C**hoice under a token budg**E**t), an algorithm that jointly and adaptively selects the rollout count and voting rule as a function of the token budget. On MATH-500, PRICE consistently outperforms six test-time compute baselines across all evaluated budgets and achieves comparable accuracy using up to – fewer token budgets.

Primary area:
foundation or frontier models, including LLMs
Keywords:
test-time compute, test-time inference, token-budgeted LLM inference, pareto frontier of LLM inference, adaptive voting

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_mjJfOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the joint optimization of rollout allocation and voting rules for LLM test-time compute under token budgets. The authors propose PRICE, which adaptively selects the number of rollouts and voting temperature for each query. The paper provides theoretical characterizations of the accuracy–cost Pareto frontier and evaluates the method on MATH-500.

Critical strengths
  1. The problem of optimizing test-time compute efficiency is relevant and practically meaningful.
  2. The paper provides a relatively comprehensive theoretical analysis.
Critical weaknesses
  1. Incomplete computation cost accounting. My main concern is that the reported token costs exclude self-evaluation scoring, query embeddings, predictor inference, and calibration. Since PRICE relies on these additional components, the reported 2.8–3.5× budget improvement may not translate into comparable end-to-end efficiency gains. A fair comparison accounting for all computational overhead is necessary.
  2. Insufficient ablation of the deployed method. PRICE-deployed combines adaptive voting, learned accuracy prediction, sequential stopping, and budget-aware allocation. However, the experiments do not sufficiently isolate the contribution of adaptive voting in the deployed setting. A baseline using the same predictors and stopping mechanism but a fixed voting rule would be particularly important.
  3. Limited experimental generalization. The main experiments focus on MATH-500 with relatively small language models. It remains unclear whether the improvements generalize to stronger reasoning models, different task domains, or settings with more capable verifiers.
Questions for authors

See weakness.

4 comments

Thank you for recognizing the practical relevance of test-time compute efficiency and the theoretical analysis. This paper is primarily a theoretical study of LLM test-time compute. Its goal is to provide a rigorous understanding of how rollout count and voting rule jointly determine the accuracy vs. token-cost Pareto frontier, and why voting must be part of compute allocation.

  • Joint optimization framework. We provide the first optimization framework to study LLM test-time compute under a token-budget constraint.
  • A rigorous account of adaptive voting. We prove that fixed-rule frontiers can cross as the budget changes, and that the adaptive-voting frontier dominates every fixed-rule frontier. These results explain why adapting the voting rule is important for understanding the attainable accuracy–compute tradeoff.
  • Explicit frontier asymptotics. We theoretically characterize the form of Pareto frontier of LLM test-time compute, rather than drawing empirical curves fitted through experiments.

We have fully addressed the weaknesses and questions raised in your review through clearer score and cost accounting, a comparison experiment to illustrate the benefit of adaptive voting which fixes deployed allocation and stopping, and evaluations on newer models and harder mathematics tasks. We would appreciate a renewed assessment centered on the framework, theoretical contributions, and this additional evidence.

Summary of weaknesses and questions

  • W1 — Computation and scoring. Self-evaluation is one score option; the framework also accepts verifier, reward-model, and intrinsic scores. In the P(True) vLLM study, scoring and all other non-generation work together account for at most 1.48% of PRICE’s cumulative compute time. The 2.8–3.5× result measures generated-token risk reduction; intrinsic scores retain significant gains at all six evaluated Qwen budgets.
  • W2 — Voting potential at fixed allocation and stopping. Replacing only the final vote with a query-dependent oracle improves over majority-only and the best global fixed τ at all twelve budgets, with every pointwise 95% confidence interval above zero.
  • W3 — Newer models and harder tasks. We added Qwen3-4B and Qwen3-8B on Minerva and OlympiadBench benchmarks, with consistent improvements over SC and BoN across the evaluated budgets.

Weakness 1. Score flexibility and computational overhead

Self-evaluation is one choice of score. Our framework accepts any per-response scores, including verifier or reward-model outputs and intrinsic generation statistics. BoN and score-weighted voting methods such as CISC also require scores; the cost of obtaining them depends on the chosen scoring procedure.

Our theoretical analysis uses a token-wise budget: the entropic risk of generated rollout tokens, b = γ⁻¹ log E[exp(γL)]. The 2.8–3.5× result compares the budgets needed to match the submitted SC baseline’s accuracy. P(True) scoring and embedding produce no additional generated tokens; their computation is measured separately below.

For the P(True) implementation, we additionally measure scoring and other online overhead using Qwen2.5-1.5B and Llama3.2-3B on all 500 MATH-500 questions in vLLM with FP16 on an H200 NVL per query. Scoring and all other non-generation work together account for at most 1.48% of PRICE’s cumulative compute time.

Table 1. Compute breakdown (seconds per question). Other online work includes embedding, controller, parsing, clustering/voting, and request preparation.

Component / seconds per questionQwenLlama
Generation23.09912.790
P(True) scoring0.2060.105
Other online work0.1120.058
Total23.41712.953
Non-generation share1.36%1.26%

At matched accuracy, PRICE uses less cumulative computation than SC and CISC. Relative to SC, the reduction is 21.3–32.7% on Qwen and 19.8–30.6% on Llama, including scoring and controller costs.

Table 2. Accuracy-matched mean cumulative compute time (seconds per question).

ModelMatched accuracyPRICE (s)SC (s)CISC (s)
Qwen2.5-1.5B60.8%9.0211.8710.92
Qwen2.5-1.5B62.6%11.4514.5518.90
Qwen2.5-1.5B63.4%12.5418.6323.22
Llama3.2-3B55.0%12.9516.1515.76
Llama3.2-3B57.0%21.4230.8527.25
Llama3.2-3B59.0%34.8946.4838.74

The gains also hold with intrinsic scores. We refit PRICE-deployed for each score and use that score for BoN and calibration-tuned CISC. Each intrinsic score beats the strongest evaluated baseline at all six Qwen budgets, with positive paired-bootstrap 95% confidence intervals. Likelihood and mean top-1 use generation logs without an extra verifier pass.

Table 3. Qwen2.5-1.5B accuracy (%) under generated-token risk budget b. Parentheses show gains over the best of SC, BoN, CISC, AC, ESC, and DeepConf, with matched scores for score-dependent methods.

Budget bP(True)LikelihoodMean top-1LGC
3679.5561.3061.48 (+5.18)61.44 (+5.32)61.47 (+5.28)
5290.6563.3363.58 (+5.13)63.48 (+5.03)63.53 (+5.08)
6658.1964.3164.78 (+4.40)64.85 (+4.60)64.72 (+4.39)
11552.5966.1766.85 (+2.93)66.77 (+2.85)66.77 (+2.85)
14515.8366.5867.37 (+2.75)67.33 (+2.72)67.28 (+2.77)
31982.7967.5668.57 (+1.31)68.71 (+1.47)68.36 (+1.32)

Weakness 2. Voting potential with deployed allocation and stopping fixed

We fix PRICE-deployed’s allocation, rollout trajectories, stopping counts, and token costs, and replace only the final vote. The adaptive voting improves over majority-only and the best global fixed temperature at all twelve budgets, with positive pointwise 95% confidence intervals.

Table 4. Adaptive voting accuracy gains (pp; 95% CI) at generated-token risk budgets.

ModelToken-risk budget bAdaptive voting − majority-onlyAdaptive voting− best fixed voting (pp; 95% CI)
Qwen3,679.55+2.06 [1.47, 2.76]+2.04 [1.46, 2.69]
Qwen5,290.65+2.61 [1.90, 3.42]+2.60 [1.88, 3.37]
Qwen6,658.19+2.87 [2.06, 3.77]+2.87 [1.04, 3.73]
Qwen11,552.59+2.60 [1.64, 3.74]+2.60 [1.60, 3.64]
Qwen14,515.83+2.84 [1.81, 3.06]+2.84 [1.80, 3.97]
Qwen31,982.79+2.26 [1.12, 3.59]+2.25 [1.10, 3.43]
Llama4,426.10+1.40 [0.99, 1.87]+1.38 [0.97, 1.82]
Llama6,234.63+1.77 [1.26, 2.39]+1.76 [1.24, 2.35]
Llama8,072.20+1.94 [1.35, 2.66]+1.91 [1.32, 2.58]
Llama13,783.96+2.34 [1.65, 3.16]+2.33 [1.63, 3.11]
Llama17,425.72+2.50 [1.77, 3.39]+2.48 [1.74, 3.30]
Llama40,399.43+2.56 [1.69, 3.59]+2.53 [1.66, 3.41]

Weakness 3. Newer models, harder tasks, and score choice

We added Qwen3-4B and Qwen3-8B on Minerva and OlympiadBench benchmarks. PRICE shows consistent improvements over the baselines, with confidence intervals excluding zero across the evaluated settings. On Qwen3-8B, PRICE improves over the baseline by 4.2–5.0 pp over Minerva and 2.1–5.6 pp on OlympiadBench over all six budgets.

Tables 5–6 use likelihood scores; Tables 7–8 use P(True). For Tables 7–8, the budget includes generated-output tokens and actual scoring-input tokens. Parentheses report accuracy gains (percentage points) over the stronger of SC and BoN.

Table 5. Qwen3-4B on Minerva with intrinsic likelihood scores. Accuracy (%) under generated-token risk budgets.

Method / budget21.4k29.0k33.0k44.8k52.2k70.6k
SC54.254.855.656.456.656.6
BoN52.552.552.452.151.851.1
PRICE60.2 (+6.1)60.3 (+5.4)60.3 (+4.7)60.4 (+4.0)60.5 (+3.9)60.5 (+3.3)

Table 6. Qwen3-4B on OlympiadBench with intrinsic likelihood scores. Accuracy (%) under generated-token risk budgets.

Method / budget23.2k31.3k39.4k63.9k80.2k129.3k
SC57.658.859.761.061.562.3
BoN55.255.155.155.055.055.0
PRICE63.1 (+5.5)64.4 (+5.6)64.6 (+4.9)64.7 (+3.7)65.0 (+3.5)65.0 (+2.7)

Table 7. Qwen3-8B on Minerva with P(True) scores. Accuracy (%) under processed-token risk budgets, including scoring inputs.

Method / budget22.7k30.6k37.9k50.5k59.2k64.8k
SC53.754.154.554.454.955.0
BoN52.853.253.553.954.054.2
PRICE58.7 (+5.0)59.0 (+4.9)59.1 (+4.6)59.3 (+4.9)59.3 (+4.4)59.3 (+4.2)

Table 8. Qwen3-8B on OlympiadBench with P(True) scores. Accuracy (%) under processed-token risk budgets, including scoring inputs.

Method / budget44.4k56.4k69.7k97.5k117.5k168.8k
SC59.961.261.963.163.563.8
BoN57.859.059.559.960.460.6
PRICE65.5 (+5.6)65.6 (+4.4)65.6 (+3.7)65.8 (+2.7)65.9 (+2.4)65.9 (+2.1)

Authors addressed my concern and thanks for the rebuttal. I raised my score to 3.

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

This paper argues that the previous studies on test-time scaling often adaptively determine the number of rollouts while keeping the voting rule fixed. To address this limitation, the authors propose a method that dynamically controls both the number of rollouts and the voting rule for each problem. Specifically, they unify majority voting (self-consistency) and Best-of-N into a single parameterized family called Boltzmann-weighted voting, allowing the aggregation rule to be selected on a per-problem basis. Experiments on MATH-500 using Qwen2.5-1.5B and Llama 3.2 3B show that the proposed method (PRICE) outperforms six baselines.

Critical strengths
  • The idea of optimizing not only the number of rollouts but also the voting rule is interesting and promising.
  • Although the individual techniques are based on existing research, their combination represents a novel approach.
  • The paper provides a theoretical formulation of the underlying research idea.
Critical weaknesses

Based on the first half of Section 1, the main contribution of this paper appears to be making the voting rule adaptive. However, the research hypothesis stated in lines 076-079 identifies the dynamic selection of both the number of rollouts and the voting rule as the contribution. The authors should first clarify their stance on this point. Of course, adaptively selecting the number of rollouts is practically useful even when the main contribution is adaptive voting. However, if the authors also claim that adaptively selecting the number of rollouts is a contribution, I have the following concerns.

  • Table 1 lists PETS, OptPO, and Solve-then-Learn as related work on budget-aware allocation and uses them to highlight the distinctive features of the proposed method. If so, I believe these methods should be included in the experimental baselines. If the authors choose not to compare against these methods, they should provide a reasonable justification.
  • The authors are also expected to conduct experiments that combine the adaptive rollout allocation methods listed in Table 1 with their proposed adaptive voting rule. This would demonstrate whether adding adaptive voting improves performance, even on top of strong adaptive-rollout baselines.

The experiments in Section 4 use Qwen2.5-1.5B and Llama 3.2 3B. I do not see a convincing justification for choosing non-reasoning LLMs for the experiments on test-time scaling, which is the focus of this study. The model sizes are also arguably too small. Experiments using more recent reasoning LLMs with approximately 8B parameters are desired.

The fact that the experiments are conducted only on MATH-500 is another limitation in assessing the usefulness of the proposed method. In addition to evaluating larger models, the study should demonstrate the effectiveness of its approach on more challenging benchmarks, such as OlympiadBench.

Questions for authors

The abstract states that the proposed method "achieves comparable accuracy using up to 2.8–3.5× fewer token budgets." However, since the evaluation uses an entropic risk budget, the authors should check whether this wording could be correct.

Why does the accuracy of the baseline methods in Table 3, particularly Adaptive-Consistency, show little improvement even as the budget increases?

Are there any results for a baseline that uses majority voting instead of adaptive voting within PRICE-deployed in Table 3?

3 comments

Thank you for recognizing the theoretical results and unified voting formulation. This paper is primarily a theoretical study of LLM test-time compute. Its goal is to provide a rigorous understanding of how rollout count and voting rule jointly determine the accuracy vs. token-cost Pareto frontier, and why voting must be part of compute allocation.

  • Joint optimization framework. We provide the first optimization framework to study LLM test-time compute under a token-budget constraint.
  • A rigorous account of adaptive voting. We prove that fixed-rule frontiers can cross as the budget changes, and that the adaptive-voting frontier dominates every fixed-rule frontier. These results explain why adapting the voting rule is important for understanding the attainable accuracy–compute tradeoff.
  • Explicit frontier asymptotics. We theoretically characterize the form of Pareto frontier of LLM test-time compute, rather than drawing empirical curves fitted through experiments.

PRICE-deployed is an initial implementation intended to illustrate the potential of this framework and its theoretical insights. More effective deployment on larger models and lower-cost integration with existing test-time compute algorithms are important follow-up questions outside the scope of this paper.

We have fully addressed the weaknesses and questions raised in your review through the clarifications and additional results summarized below. We would appreciate a renewed assessment centered on the framework, theoretical contributions, and this additional evidence.

Summary of weaknesses and questions

  • W1 — Contribution and prior works. We clarify the contributions of this work, and explain that integrating adaptive voting into prior works of literature is outside the scope of this work.
  • W2–W3 — Newer models and harder tasks. We added Qwen3-4B and Qwen3-8B on Minerva (272 questions) and OlympiadBench (674 questions), with consistent improvements over SC and BoN across the evaluated budgets.
  • Q1 — Token budget and computation time. The 2.8–3.5× factor measures generated-token risk-averse budget reduction at matched SC accuracy. In separate vLLM measurements, scoring and all other non-generation work together only account for at most 1.48% of PRICE’s cumulative computation time.
  • Q2 — Adaptive-Consistency’s apparent plateau. AC controls sampling through a confidence threshold. Moving from 0.7 to 0.8 yields much higher accuracy and cost; the 0.8 settings exceed the submitted Table 3’s token-risk budget ranges, explaining the nearly flat row.
  • Q3 — Voting potential at fixed allocation and stopping. With deployed allocation and stopping fixed, oracle voting beats majority-only and the best global fixed τ at all twelve budgets. Gains over the latter are 2.04–4.25 pp on Qwen and 1.38–2.83 pp on Llama, with every pointwise 95% confidence interval above zero.

Weakness 1. Clarification of Contributions and Prior works

Our main contribution is a theoretical understanding of LLM test-time compute, rather than a heuristic plug-in that adds an adaptive voting option. We study how rollout allocation and voting jointly determine the accuracy attainable under a token budget. This analysis establishes why adaptive voting matters and characterizes the optimal frontier’s accuracy ceiling and convergence rate.

PETS, OptPO, and Solve-then-Learn are related work on budget-aware allocation, but they study different formulations. PETS allocates a trajectory budget to recover the population majority vote. OptPO uses consensus-based stopping to collect rollouts for test-time policy updates. Solve-then-Learn selects rollout counts under an average-cost constraint with majority voting. Our work jointly optimizes rollout count and voting under a generated-token entropic-risk constraint. Comparing their implementations under this constraint would require adapting their allocation objectives and budget accounting. (PETS, OptPO, Solve-then-Learn)

PRICE-deployed provides an initial empirical demonstration of the potential gains from this joint formulation. The experiments illustrate how theoretical insights can guide allocation and voting decisions. Integrating these insights into existing allocators is an important next step: changing the voting rule changes the value of additional rollouts, so the allocation policy should be reconsidered alongside it. Developing efficient integrations and establishing which implementation performs best are beyond the scope of this work.

Weaknesses 2–3. Newer models and harder benchmarks

We added Qwen3-4B and Qwen3-8B evaluations on Minerva and OlympiadBench benchmarks. PRICE shows consistent improvements over the baselines, with confidence intervals excluding zero across the evaluated settings. On Qwen3-8B, PRICE improves over the baseline by 4.2–5.0 pp over Minerva and 2.1–5.7 pp on OlympiadBench over all six budgets.

Tables 1–2 use likelihood scores; Tables 3–4 use P(True). For Tables 3–4, the budget includes generated-output tokens and actual scoring-input tokens. Parentheses report accuracy gains (percentage points) over the stronger of SC and BoN.

Table 1. Qwen3-4B on Minerva with intrinsic likelihood scores. Accuracy (%) under generated-token risk budgets.

Method / budget21.4k29.0k33.0k44.8k52.2k70.6k
SC54.254.855.656.456.656.6
BoN52.552.552.452.151.851.1
PRICE60.2 (+6.1)60.3 (+5.4)60.3 (+4.7)60.4 (+4.0)60.5 (+3.9)60.5 (+3.3)

Table 2. Qwen3-4B on OlympiadBench with intrinsic likelihood scores. Accuracy (%) under generated-token risk budgets.

Method / budget23.2k31.3k39.4k63.9k80.2k129.3k
SC57.658.859.761.061.562.3
BoN55.255.155.155.055.055.0
PRICE63.1 (+5.5)64.4 (+5.6)64.6 (+4.9)64.7 (+3.7)65.0 (+3.5)65.0 (+2.7)

Table 3. Qwen3-8B on Minerva with P(True) scores. Accuracy (%) under processed-token risk budgets, including scoring inputs.

Method / budget22.7k30.6k37.9k50.5k59.2k64.8k
SC53.754.154.554.454.955.0
BoN52.853.253.553.954.054.2
PRICE58.7 (+5.0)59.0 (+4.9)59.1 (+4.6)59.3 (+4.9)59.3 (+4.4)59.3 (+4.2)

Table 4. Qwen3-8B on OlympiadBench with P(True) scores. Accuracy (%) under processed-token risk budgets, including scoring inputs.

Method / budget44.4k56.4k69.7k97.5k117.5k168.8k
SC59.961.261.963.163.563.8
BoN57.859.059.559.960.460.6
PRICE65.5 (+5.6)65.6 (+4.4)65.6 (+3.7)65.8 (+2.7)65.9 (+2.4)65.9 (+2.1)

Q1. What does the 2.8–3.5× budget reduction mean?

The budget is the entropic risk of total generated rollout tokens, b = γ⁻¹ log E[exp(γL)]. It is measured in token units and accounts for variability in rollout costs. The reported factor compares the budgets needed to match the submitted SC baseline’s accuracy.

A precise abstract wording is: “On MATH-500, PRICE-deployed matches the evaluated SC baseline’s accuracy with a generated-token entropic-risk budget up to 2.8× smaller on Qwen2.5-1.5B and 3.5× smaller on Llama3.2-3B.”

P(True) scoring and embedding generate no additional tokens. Their computation is reported separately: scoring and all other non-generation work together account for at most 1.48% of PRICE’s cumulative compute time in the 500-question vLLM study. Table 5 gives representative breakdowns. At matched accuracy, the time reduction relative to SC is 21.3–32.7% on Qwen and 19.8–30.6% on Llama at the operating points in Table 6.

We benchmark Qwen2.5-1.5B and Llama3.2-3B on all 500 MATH-500 questions in vLLM with FP16. Each method is charged for its actual stopping prefix, including scoring and other online work.

Table 5. Compute breakdown (seconds per question): Qwen at 65.8% accuracy and Llama at 55.0%. Other online work includes embedding, controller, parsing, clustering/voting, and request preparation.

Component / seconds per questionQwenLlama
Generation23.09912.790
P(True) scoring0.2060.105
Other online work0.1120.058
Total23.41712.953
Non-generation share1.36%1.26%

Table 6. Accuracy-matched mean cumulative serial compute time (seconds per question).

ModelMatched accuracyPRICE (s)SC (s)CISC (s)
Qwen2.5-1.5B60.8%9.0211.8710.92
Qwen2.5-1.5B62.6%11.4514.5518.90
Qwen2.5-1.5B63.4%12.5418.6323.22
Llama3.2-3B55.0%12.9516.1515.76
Llama3.2-3B57.0%21.4230.8527.25
Llama3.2-3B59.0%34.8946.4838.74

Q2. Why does Adaptive-Consistency improve so little as the budget grows?

Adaptive-Consistency controls sampling through a confidence threshold, without an explicit token-budget constraint. Following the threshold-sweep approach in the original work, we vary this hyperparameter to obtain different accuracy–cost operating points. Table 7 highlights the large gap between thresholds 0.7 and 0.8.

Table 7. AC accuracy and cost at confidence thresholds 0.7 and 0.8. Mean generated tokens and token-risk budget b are reported separately.

ModelThresholdMean rolloutsMean tokensToken-risk bAccuracy (%)
Qwen0.71.055885,85148.87
Qwen0.812.659,08191,05066.60
Llama0.71.2268115,60244.44
Llama0.816.1012,375116,60360.47

Raising the threshold to 0.8 substantially improves accuracy, but the token-risk cost reaches 91,050 on Qwen and 116,603 on Llama. Both exceed the budget ranges in Table 3 of the submitted paper: 3.7k–32.0k on Qwen and 4.4k–40.4k on Llama. These higher-cost settings receive only negligible weight when matching the reported budgets, producing the nearly flat AC row.

Q3. Voting potential with deployed allocation and stopping fixed

We fix PRICE-deployed’s allocation, rollout trajectories, stopping counts, and token costs, and replace only the final vote.

The adaptive voting improves over majority-only and the best global fixed temperature at all twelve budgets, with positive pointwise 95% confidence intervals. These gains demonstrate the potential of query-dependent voting at unchanged generated-token cost.

Table 8. Oracle-vote accuracy gains (pp; 95% CI) at matched generated-token risk budgets.

ModelToken-risk budget bAdaptive − majority-onlyAdaptive − best fixed voting
Qwen3,679.55+2.06 [1.47, 2.76]+2.04 [1.46, 2.69]
Qwen5,290.65+2.61 [1.90, 3.42]+2.60 [1.88, 3.37]
Qwen6,658.19+2.87 [2.06, 3.77]+2.87 [1.04, 3.73]
Qwen11,552.59+2.60 [1.64, 3.74]+2.60 [1.60, 3.64]
Qwen14,515.83+2.84 [1.81, 3.06]+2.84 [1.80, 3.97]
Qwen31,982.79+2.26 [1.12, 3.59]+2.25 [1.10, 3.43]
Llama4,426.10+1.40 [0.99, 1.87]+1.38 [0.97, 1.82]
Llama6,234.63+1.77 [1.26, 2.39]+1.76 [1.24, 2.35]
Llama8,072.20+1.94 [1.35, 2.66]+1.91 [1.32, 2.58]
Llama13,783.96+2.34 [1.65, 3.16]+2.33 [1.63, 3.11]
Llama17,425.72+2.50 [1.77, 3.39]+2.48 [1.74, 3.30]
Llama40,399.43+2.56 [1.69, 3.59]+2.53 [1.66, 3.41]
Reviewer_GnKNOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Previous test-time compute allocation methods mostly consider the allocation strategy itself when given a fixed voting rule (e.g., best-of-n or majority vote), while this paper innovatively proposes that the voting rule should be adaptive too. Specifically, it formulates the problem using a general Boltzman weighted vote and aims to optimize the tau value for each query. Theoretical and empirical justifications are provided to support the claims.

Critical strengths
  • The formulation of continuous Boltzmann family parameterized by τ\tau is conceptually clean and connects SC and BoN.
  • The theoretical analysis is interesting and clearly showing the advantage of the adaptivity of voting rules.
  • The algorithm is derived using strong duality which decomposes the joint allocation problem into independent per-query subproblems which is mathematically grounded and well-engineered.
Critical weaknesses
  • The empirical evaluation on outdated LLMs (e.g., LLaMA3.2 and Qwen2.5) is not sufficiently convincing for understanding the effectiveness of the proposed method. Authors should at least try two more modern models under different model families (e.g., one can be Qwen3.6).
  • The empirical evaluation ommited the very important study of auxiliary computational and token overheads. For example, the quality score is obtained via self-evaluation which uses substantial tokens and is not included in the token budget, while baselines require no verification cost. The regression predictor itself also introduces another source of auxiliary compute cost and needs to be highlighted in detail.
Questions for authors
  • Could you provide a breakdown of the exact token/FLOP overhead incurred by the self-evaluation prompt per rollout? If the prefill tokens of the self-evaluation pass (or equivalent FLOPs) are included in the realized budget bb, how much do the Pareto frontier gains and the 2.8-3.5×2.8\text{-}3.5\times budget reduction against SC/ESC change?
  • How does PRICE-deployed (not just PRICE-oracle) perform against baselines when restricted strictly to zero-overhead intrinsic scores like Likelihood or Self-certainty?
  • How sensitive is PRICE-deployed to the size of the calibration corpus? Can the Ridge predictors and initial shadow price be calibrated effectively with, say, 100 or 500 queries instead of thousands of queries used in the paper?
  • Could you report a wall-clock time vs. accuracy comparison to demonstrate that the sequential stopping rule, embedding computation, and self-evaluation passes translate to actual latency savings in a live serving environment (e.g., vLLM)?
4 comments

Thank you for recognizing the theoretical results and unified voting formulation. This paper is primarily a theoretical study of LLM test-time compute. Its goal is to provide a rigorous understanding of how rollout count and voting rule jointly determine the accuracy vs. token-cost Pareto frontier, and why voting must be part of compute allocation.

  • Joint optimization framework. We provide the first optimization framework to study LLM test-time compute under a token-budget constraint.
  • A rigorous account of adaptive voting. We prove that fixed-rule frontiers can cross as the budget changes, and that the adaptive-voting frontier dominates every fixed-rule frontier. These results explain why adapting the voting rule is important for understanding the attainable accuracy–compute tradeoff.
  • Explicit frontier asymptotics. We theoretically characterize the form of Pareto frontier of LLM test-time compute, rather than drawing empirical curves fitted through experiments.

PRICE-deployed is an initial implementation intended to illustrate the potential of this framework and its theoretical insights. We have fully addressed the weaknesses and questions raised in your review through the additional model and intrinsic-score evaluations, calibration-sensitivity tests, and scoring-cost and runtime measurements summarized below. We would appreciate a renewed assessment centered on the framework, theoretical contributions, and this additional evidence.

Summary of weaknesses and questions

  • W1 — Newer models and broader mathematics. We added Qwen3-4B and Qwen3-8B on Minerva and OlympiadBench benchmarks. PRICE consistently improves over SC and BoN across the evaluated settings, with confidence intervals excluding zero (Tables 1–4).
  • W2 / Q1 — Budget definition and scoring overhead. The 2.8–3.5× result measures generated-token risk reduction at matched accuracy. Our framework accepts any scores, whose construction is also required by baselines like BoN and CISC. In the 500-question vLLM study, scoring and all other non-generation work together account for at most 1.48% of PRICE’s computation time (Table 5).
  • Q2 — Intrinsic scores. PRICE-deployed improves over the strongest evaluated baseline with other scores, including likelihood, mean top-1, and LGC, at all six Qwen budgets; every paired-bootstrap 95% confidence interval for the gain is above zero (Table 6). Likelihood and mean top-1 use generation logs without an extra verifier pass.
  • Q3 — Calibration sensitivity. With 100 or 500 calibration queries, PRICE retains significant gains across the five budgets in Table 7. Even the weakest 100-query run improves over the strongest baseline by at least 1.02 percentage points.
  • Q4 — Accuracy-matched runtime. In the vLLM comparison, PRICE uses less cumulative computation than SC and CISC at all displayed accuracy levels on both models. Relative to SC, the reduction is 21.3–32.7% on Qwen and 19.8–30.6% on Llama, including scoring and controller costs (Table 8).

Weakness 1. Newer model and broader mathematics evaluation

We added Qwen3-4B and Qwen3-8B evaluations on Minerva and OlympiadBench benchmarks. PRICE shows consistent improvements over the baselines, with confidence intervals excluding zero across the evaluated settings. On Qwen3-8B, PRICE improves over the baseline by 4.2–5.0 pp over Minerva and 2.1–5.6 pp on OlympiadBench over all six budgets.

Tables 1–2 use likelihood scores; Tables 3–4 use P(True). For Tables 3–4, the budget includes generated-output tokens and actual scoring-input tokens. Parentheses report accuracy gains (percentage points) over the stronger of SC and BoN.

Table 1. Qwen3-4B on Minerva with intrinsic likelihood scores. Accuracy (%) under generated-token risk budgets.

Method / budget21.4k29.0k33.0k44.8k52.2k70.6k
SC54.254.855.656.456.656.6
BoN52.552.552.452.151.851.1
PRICE60.2 (+6.1)60.3 (+5.4)60.3 (+4.7)60.4 (+4.0)60.5 (+3.9)60.5 (+3.3)

Table 2. Qwen3-4B on OlympiadBench with intrinsic likelihood scores. Accuracy (%) under generated-token risk budgets.

Method / budget23.2k31.3k39.4k63.9k80.2k129.3k
SC57.658.859.761.061.562.3
BoN55.255.155.155.055.055.0
PRICE63.1 (+5.5)64.4 (+5.6)64.6 (+4.9)64.7 (+3.7)65.0 (+3.5)65.0 (+2.7)

Table 3. Qwen3-8B on Minerva with P(True) scores. Accuracy (%) under processed-token risk budgets, including scoring inputs.

Method / budget22.7k30.6k37.9k50.5k59.2k64.8k
SC53.754.154.554.454.955.0
BoN52.853.253.553.954.054.2
PRICE58.7 (+5.0)59.0 (+4.9)59.1 (+4.6)59.3 (+4.9)59.3 (+4.4)59.3 (+4.2)

Table 4. Qwen3-8B on OlympiadBench with P(True) scores. Accuracy (%) under processed-token risk budgets, including scoring inputs.

Method / budget44.4k56.4k69.7k97.5k117.5k168.8k
SC59.961.261.963.163.563.8
BoN57.859.059.559.960.460.6
PRICE65.5 (+5.6)65.6 (+4.4)65.6 (+3.7)65.8 (+2.7)65.9 (+2.4)65.9 (+2.1)

Weakness 2 / Q1. Auxiliary costs and budget accounting

As emphasized in the paper, our budget is token-wise: the entropic risk of generated tokens. Our goal is to rigorously understand the accuracy–token-budget frontier, rather than to propose a heuristic or engineering optimization for wall-clock speed. Since P(True) scoring and embedding produce no additional generated tokens, the reported 2.8–3.5× measures the reduction in this token budget needed to match the submitted SC baseline’s accuracy.

Our framework supports any per-response scores, including external verifier or reward-model scores and intrinsic signals such as likelihood. It takes these scores as inputs and jointly optimizes rollout allocation and voting.

How scores are obtained is external to the framework. Score-based methods such as BoN and CISC also require this step, whose cost depends on the chosen scorer. We compare these methods using matched scores, holding the scoring procedure fixed.

To address your concern, we also break down the practical overhead of P(True). It reads the True/False logits in one forward pass over the question and extracted answer. In the 500-question serial vLLM study, scoring and all other non-generation work together account for at most 1.48% of PRICE’s cumulative compute time on both Qwen and Llama models. Table 5 gives two representative operating points.

Table 5. Measured seconds per question, including P(True). Other online work includes embedding, controller, parsing, clustering/voting, and request preparation.

Component / seconds per questionQwenLlama
Generation23.09912.790
P(True) scoring0.2060.105
Other online work0.1120.058
Total23.41712.953
Non-generation share1.36%1.26%

Q2. Does PRICE-deployed work with intrinsic scores?

PRICE improves over the strongest evaluated baseline at every tested Qwen budget with each of the three intrinsic scores. We refit the controller for each score and use the same score for BoN and calibration-tuned CISC. Table 6 reports accuracy and gains at matched budgets.

Table 6. Qwen2.5-1.5B accuracy (%) under the paper’s generated-token risk budget b. Parentheses show gains (percentage points) over the best of SC, BoN, CISC, AC, ESC, and DeepConf at each budget. Score-dependent methods use matched scores. P(True) is the original PRICE-deployed result.

Budget bP(True)LikelihoodMean top-1LGC
3679.5561.3061.48 (+5.18)61.44 (+5.32)61.47 (+5.28)
5290.6563.3363.58 (+5.13)63.48 (+5.03)63.53 (+5.08)
6658.1964.3164.78 (+4.40)64.85 (+4.60)64.72 (+4.39)
11552.5966.1766.85 (+2.93)66.77 (+2.85)66.77 (+2.85)
14515.8366.5867.37 (+2.75)67.33 (+2.72)67.28 (+2.77)
31982.7967.5668.57 (+1.31)68.71 (+1.47)68.36 (+1.32)

For each intrinsic score, the gain over the strongest evaluated baseline has a paired-bootstrap 95% confidence interval above zero at all six Qwen budgets.

Likelihood and mean top-1 confidence come from generation logs, requiring no extra verifier pass. DeepConf-style LGC uses top-5 confidence and a 128-token window; these results reuse a teacher-forced cache for its token probabilities.

Q3. Calibration size and price selection before deployment

Calibration size affects accuracy, but PRICE retains significant gains with 100 or 500 total calibration queries. At every budget in Table 7, the paired-bootstrap 95% confidence interval for its gain over the strongest original baseline is above zero. Even the weakest 100-query run improves over the strongest baseline by at least 1.02 percentage points across the budgets shown.

Table 7. Qwen2.5-1.5B accuracy (%) at five generated-token risk budgets with P(True). Parentheses show gains (percentage points) over the strongest original baseline.

Budget bBest baselineFull calibration100 queries500 queries
3679.5554.9261.3060.90 (+5.98)60.88 (+5.96)
5290.6558.4563.3362.97 (+4.52)62.96 (+4.51)
6658.1959.8464.3163.95 (+4.12)63.89 (+4.05)
11552.5963.9366.1765.21 (+1.28)65.46 (+1.54)
14515.8364.3366.5865.56 (+1.22)65.76 (+1.43)

Q4. Accuracy-matched runtime in vLLM

At matched accuracy, PRICE uses less cumulative computation than SC and CISC on both models at the operating points in Table 8. Relative to SC, computation time is reduced by 21.3–32.7% on Qwen2.5-1.5B and 19.8–30.6% on Llama3.2-3B, including scoring and controller costs. These measurements illustrate how the token-budget gains can translate into practical time savings.

We benchmark both models on all 500 MATH-500 questions in vLLM with FP16. Each query runs on a single H200 NVL.

Table 8. Accuracy-matched mean cumulative compute time (seconds per question).

ModelMatched accuracyPRICE (s)SC (s)CISC (s)
Qwen2.5-1.5B60.8%9.0211.8710.92
Qwen2.5-1.5B62.6%11.4514.5518.90
Qwen2.5-1.5B63.4%12.5418.6323.22
Llama3.2-3B55.0%12.9516.1515.76
Llama3.2-3B57.0%21.4230.8527.25
Llama3.2-3B59.0%34.8946.4838.74

Comments on the paper

2 comments
AuthorsOpenReview ↗

A Kind Reminder

Thank you for your time and effort in reviewing our paper. Your comments have been valuable in improving its quality. As the discussion period ends on November 18 (AoE), we would like to kindly check whether our responses have addressed your concerns. We would be happy to provide further clarification if needed.

Best regards,

The Authors

AuthorsOpenReview ↗

Summary of Theoretical Contributions and Rebuttal Updates

We thank the reviewers and Area Chair for their constructive feedback.

This work provides a theoretical understanding of LLM test-time compute. To our knowledge, it is the first work to theoretically characterize the accuracy–token-budget Pareto frontier for LLM test-time compute, including its accuracy ceiling and large-budget convergence rate. We show that fixed-voting frontiers can cross at certain token budgets, establish that the adaptive-voting frontier dominates all fixed-voting frontiers, and derive its asymptotic behavior.

We regret to see that the assessments have largely overlooked our theoretical contributions but mainly focusing on the initial implementation, i.e., PRICE-deployed as an initial implementation originally intended to illustrate this framework’s potential. During rebuttal, we have fully addressed the weaknesses and questions raised by all three reviewers, as summarized below:

  • R1 (GnKN) — Empirical coverage, scoring, and calibration: We added Qwen3-4B and Qwen3-8B evaluations on Minerva and OlympiadBench benchmarks. With intrinsic likelihood scores, PRICE improves accuracy by 1.31–5.18 pp over the strongest evaluated baseline across all six Qwen budgets, with every 95% CI above zero. Gains also remain significant with only 100 or 500 calibration queries across the five reported budgets.
  • R2 (BS2N) — Theoretical novelty and budget-aware optimization: We clarify the novelty of jointly optimizing rollout allocation and voting under token budgets. Integrating adaptive voting with existing allocators is an important direction beyond this paper’s scope. We also explain Adaptive Consistency’s apparent plateau: it controls stopping through a confidence threshold rather than an explicit token-budget constraint. Increasing this threshold from 0.7 to 0.8 raises Qwen accuracy from 48.87% to 66.60%, but increases token-risk cost from 5,851 to 91,050, beyond the evaluated budget range of 3.7k–32.0k.
  • R3 (mjJf) — Computational overhead and adaptive voting: Scoring and all other non-generation work together account for at most 1.48% of computation time. At matched accuracy, PRICE reduces computation time by 21.3–32.7% on Qwen and 19.8–30.6% on Llama relative to Self-consistency. Holding deployed allocation and stopping fixed, our label-assisted study of adaptive-voting potential shows improvements over the best global fixed voting rule at all twelve budgets, with every pointwise 95% CI above zero.

Best,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.