acceptodds
Withdrawn from ICLR 2027

Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Spending more compute at inference time can improve large language model (LLM) accuracy, but not every query benefits equally. Under a limited budget, which queries should receive more compute, and which can be answered with less? We formulate this decision as a constrained optimization problem: assign a compute budget to each query to maximize expected accuracy, subject to a limit on average compute cost. To solve this problem, we propose a two-stage Solve-then-Learn (STL) framework. In the solve stage, we use Lagrangian relaxation to construct a budget-allocation oracle with provable optimality guarantees on a calibration set. In the learn stage, we use the oracle allocations as supervision to train a lightweight classifier that predicts a compute budget for each new query before generation. For LLM reasoning, STL assigns different token caps to different questions to improve overall accuracy under a shared average token budget, while keeping the underlying LLM unchanged. Experiments across two benchmarks and three LLMs show that STL outperforms the strongest evaluated baseline in 17 of 18 settings, with an average accuracy gain of 3.90 percentage points and a maximum gain of 8.46 points under the same budget constraint.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Test-time compute allocation, Large language models, Constrained optimization, Lagrangian relaxation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_b8oaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to allocate a shared completion-token budget across questions for a fixed language model. The proposed Solve-then-Learn framework first estimates question-specific accuracy and cost at several token caps, uses a Lagrangian solver to construct allocation labels, and trains a lightweight classifier to predict these labels before generation. A separate sequential executor enforces the total budget by reserving a minimum allowance for unanswered questions. The paper provides finite-table allocation and imitation-error bounds, together with a budget-feasibility guarantee. Experiments cover two mathematics datasets and three models. The primary results report improvements over the strongest evaluated baseline in 17 of 18 settings, averaging 3.90 percentage points, although these results use a cost-calibrated variant that differs from the direct-budget training procedure emphasized in the main description.

Critical strengths

1.The Lagrangian formulation explicitly coordinates compute allocation across questions without requiring diminishing returns in accuracy.

2.The lightweight policy and hard-budget executor support deployment without modifying the underlying model or sampling preliminary answers.

3.Experiments across three models and two datasets show consistent improvements, with ten comparisons against Random remaining significant after multiple-testing correction.

Critical weaknesses

1.The headline results use an earlier cost-calibrated variant, leaving the emphasized direct-budget training procedure insufficiently validated by the primary evaluation.

2.The absence of stronger learned-allocation baselines makes the specific contribution of oracle-label supervision difficult to establish.

3.Incomplete generation records and uncertainty estimates conditioned on fixed response pools limit reproducibility and assessment of robustness to fresh sampling.

Questions for authors

1.Which training variant is intended as the final method, and do the headline conclusions hold under a matched comparison of direct-budget and cost-calibrated training?

2.How does STL compare with learned utility or marginal-reward predictors using the same training data, input features, candidate caps, and budget executor?

3.Can the missing mini/nano sampling settings be recovered, and do the gains persist across independent training runs and newly generated response pools?

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

This paper proposes the Solve-Then-Learn (STL) framework to optimize the allocation of test-time token budgets on a per-problem basis. In the Solve stage, the authors derive an oracle for compute budget allocation via Lagrangian relaxation. In the Learn stage, they train a lightweight classifier to predict compute budgets, using the oracle allocations as supervision. This allows STL to maximize problem-solving accuracy by assigning different token limits to different problems. Experiments evaluating GPT-5.4 mini, GPT-5.4 nano, and Qwen3-235B-A22B on OlympiadBench and AIME-extended report that the proposed method outperforms the baseline methods.

Critical strengths
  • Adapting the maximum number of tokens allocated to each problem is important for practical applications of LLMs, particularly for reducing inference costs and environmental impact.
  • Rather than only predicting problem difficulty, this work addresses the problem of maximizing accuracy under a constrained token budget and proposes the STL framework as a solution.
  • The experimental results demonstrate the effectiveness of the proposed method across all evaluated models.
Critical weaknesses
  • The novelty of the proposed method is not convincing.
    • First, the paper does not cite closely related work, such as Zuo and Zhu (2026), which addresses a very similar problem. Although their approach may not be applicable to black-box LLMs, a comparison should be possible at least for Qwen3-235B-A22B. Such an experimental comparison would also be valuable for investigating the differences between black-box and white-box settings.
    • Section 2 (Related Work) describes the research background and prior work. However, the discussion of prior work largely consists of summarizing existing studies, without clearly comparing them with the present work or explaining how it is positioned relative to them. Consequently, the novelty of this work remains unclear.
  • The baseline methods are too weak to establish the advantages of the proposed method over existing approaches.
    • The experimental results essentially show that the proposed method performs better than a random baseline, but this is insufficient to demonstrate its effectiveness.
    • "Learning How Hard to Think" (Damani et al., 2025), which is cited in the paper, should also be included as a baseline for comparison.
    • As discussed above, a comparison with Zuo and Zhu (2026) is also desirable.

Bowen Zuo and Yinglun Zhu. 2026. Strategic Scaling of Test-Time Compute: A Bandit Learning Approach. ICLR.

Questions for authors

Nothing in particular.

Reviewer_LAvkOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes Solve-then-Learn (STL) to maximize reasoning accuracy by assigning different token budgets to questions under a shared average compute constraint. It uses Lagrangian optimization to derive allocations from calibration data, then trains a lightweight classifier to predict token caps for new questions without modifying the underlying LLM. The authors bound allocation and imitation errors and introduce an execution rule that enforces the total token budget. Across OlympiadBench and AIME-extended with three LLMs, STL outperforms the strongest evaluated baseline in 17 of 18 settings.

Critical strengths
  • The paper addresses a practical problem by optimizing reasoning accuracy under a shared compute budget while accounting for differences in how questions benefit from additional tokens.
  • The proposed framework is practical to deploy since it selects token caps before generation without retraining the underlying LLM.
Critical weaknesses
  • The experiments seem not to be ready. Sec 7 says that "Table 1, Figure 3, and Sections 7.2–7.3 retain results from the earlier procedure. Section 7.4 reports the completed direct-budget cross domain experiment; the primary table and budget sweep have not yet been replaced with results from this revised procedure."
  • Some work already study the budge allocation problem, like Damani et al. (2025). The paper does not compare with these methods.
Questions for authors

Please clarify whether the results are reliable.

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

Related papers

Discussion (0)

Sign in to comment.