acceptodds
Under review as a conference paper at ICLR 2027

Keep a Branch: Completion-Aware Width Control for Verifier-Guided Reasoning

Abstract

A branch kept alive by test-time search can survive a layer without advancing, advance without finishing, and finish without winning the final vote. We study how verifier-guided reasoning should choose its width, the number of branches retained per layer, under a fixed token budget, and find that each link of this chain fails separately. On 195 MATH problems, widening a frozen 7B beam from width 1 to 5 under a fixed ceiling halves accuracy, from 82% to 42%. The wide beam leaves 112 runs with no completed answer: at width 5, only 7,116 of the 65,536 budget tokens are newly generated text. Exact-distance labels on 1.22 million planning candidates isolate the earlier links, separating retention of an improving branch from sustained progress toward the goal. The diagnosis yields two requirements for useful exploration: an extra branch must justify its cost, and enough budget must remain to finish one retained path. SCA+ turns them into a per-layer width rule built from an estimated marginal gain and an estimated completion reserve. Under total-token accounting, with verifier calls charged like generation, SCA+ exceeds its strongest budget-aware baseline on MATH by 4.7 points with 16% fewer tokens while both discover correct answers equally often. The margin comes from completion quality: narrower width concentrates tokens per candidate, raises verifier scores at completion and shifts a fixed final vote.

Primary area:
foundation or frontier models, including LLMs
Keywords:
test-time compute, verifier-guided search, beam width control, process reward models, token budget, LLM reasoning

Reviews

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

The paper studies how verifier-guided search should choose its beam width under a fixed total-token budget. It frames search outcomes as a chain: survive a layer, make progress, finish, and win the final vote.

Planning diagnostics. On four planning domains, with Qwen2.5-7B as both proposer and verifier and exact-distance labels on 1.22M candidates, the paper shows that layer-level retention, frontier progress and ranking quality respond differently to width. Oracle-ranking interventions show that width cannot repair near-chance ranking.

Math diagnostics. On 195 MATH problems with Qwen2.5-Math-PRM-7B, the paper uses Pr⁡(S)=Pr⁡(T)Pr⁡(C∣T)Pr⁡(S∣C)\Pr(S)=\Pr(T)\Pr(C|T)\Pr(S|C) to split failures into non-completion, missing correct answer and selection loss. A width-5 beam fails mainly by never completing: 112 of 195 runs, with only 7,116 of 65,536 budget tokens being new output.

Method. SCA+ sets the width at each layer using two learned components:

  1. a ridge-regression gain model Δ^(k)\hat\Delta(k), trained on paired width-kk vs width-1 continuations;
  2. a completion reserve UU with completion probability FF, from Aalen–Johansen estimates on nearest-neighbor development states.

Both are fit on 64 planning tasks and frozen. The paper evaluates on:

  • E4: 7B planning;
  • E5: 480 MATH problems × 3 seeds;
  • E6: 14B planning.

On MATH at 32,768 total tokens, SCA+ reaches 92.4% vs 87.6% for BG-MCTS and 83.3% for BoN with PRM voting, with fewer charged tokens. Pool analysis attributes the margin over BG-MCTS to selection (72 vs 141 selection losses at equal discovery).

Critical strengths
  1. A clean failure decomposition with honest bookkeeping. Splitting outcomes into completion, discovery and selection makes visible where each method loses. The headline example is clear: the wide beam loses to non-completion; BG-MCTS loses to selection despite equal discovery. The paired attribution against the no-gain-model ablation (Appendix H.4) is a rare example of tracing a controller decision to the final vote. Disclosing the alternative-currency results, which partly reverse the comparison, is commendable.
  2. A frozen, cross-domain controller with paired evaluation. The controller is fit on planning only and transferred unchanged to MATH and to a 14B model. Evaluation uses held-out panels, 3 seeds, task-level bootstrap and Holm adjustment. The large margins over every baseline at the primary budget are statistically robust within the chosen accounting.
Critical weaknesses

W1. The main results depend on a cost currency that structurally penalizes wide search and baselines designed for a different currency.

What "charged tokens" counts. The budget includes full re-fed generation input and verifier input, with no prefix caching.

This currency produces the motivating failure. At width 5, prefix and verifier input consume ~89% of the budget (Fig. 3B), which is why the wide beam "never finishes." Under realistic serving with prefix KV-caching, most of that input cost largely disappears. The headline "widening from 1 to 5 halves accuracy" is therefore largely an artifact of the accounting, not a property of search.

The paper's own Appendix J weakens the claims.

  • Output tokens: BG-MCTS at 65k (94.86% with 8,855 output tokens) dominates SCA+ at 32k (92.36% with 9,731).
  • Modeled query time (Table 14, batch4): SCA+ is the slowest method (102 s vs 68 s for BG-MCTS and 65 s for BoN), because narrow search waits serially for scores.

The baseline adaptation favors SCA+. BG-MCTS was designed under output-token budgets and is here charged full-prefix verifier input (15,289 tokens per run), which is exactly the cost SCA+ is built to avoid.

The abstract and TL;DR report "+4.7 pp with 16% fewer tokens" without saying that the result is currency-specific.

W2. Where the gains come from is unclear, and the controller's learned components are not validated where they matter.

Unexplained gaps to fixed widths. SCA+'s action mix is ~55% width 1, 34% width 2, 11% width 3. Yet it beats fixed width 1 by +23.7 pp and fixed width 2 by +17.2 pp on MATH (Table 9). Fixed width 1 also spends only 14.7k of its 32.8k budget, which suggests the 12-layer depth cap or the stopping rule, not width, drives much of that gap. The paper does not explain this.

Ablations all lose roughly the whole margin. Each single ablation costs 9–23 pp, and "no completion filter" falls to fixed-width-1 levels (69.2%). This pattern suggests interacting heuristics and fallbacks rather than two separable estimates.

No evidence the learned estimates work on MATH.

  • The gain model is a 16-feature ridge regression fit on 64 planning tasks against a width-1 reference continuation.
  • The authors acknowledge that its calibration in deployment, where width is re-decided at every layer, is "unmeasured."
  • Yet "SCA (no learned models)" → SCA+ is worth +6 pp on MATH, with no evidence that planning-fit gain predictions are meaningful on math states.

The mechanism claim is circular. "Narrower width raises verifier scores at completion" (0.755 → 0.926) only shows that a search steered toward higher-PRM paths produces higher-PRM completions, which then dominate a PRM-weighted vote. It is a description of PRM-score concentration, not independent evidence of better reasoning.

The scope is narrow:

  • one model family and one PRM;
  • MATH with a 7B model in a small-budget regime (BoN gets only a handful of samples at 32k);
  • a step-level setting (256-token steps, 12 layers) that does not reflect long-CoT reasoning models.
Questions for authors
  1. (Decisive.) Please rerun the E5 comparison under cache-aware accounting (generation input charged only for uncached tokens) or measured wall-clock on a real serving stack. Does SCA+ still lead BG-MCTS, REBASE+F and BoN? Does the width-5 non-completion failure persist?
  2. Why does SCA+ beat fixed width 1 and width 2 by 17–24 pp on MATH when its own action mix is dominated by widths 1–2? How much of this comes from the depth cap or stopping behavior vs the width decisions themselves? Please report completion rates and depth reached for fixed widths in E5.
  3. Is there any calibration evidence for Δ^(k)\hat\Delta(k) and UU on MATH states, e.g. predicted vs realized gain on forked continuations from matched math states? How often does the out-of-support fallback (width ≤ 2) fire in E5?
  4. Was BG-MCTS run with its original output-token budgeting as well? How does SCA+ compare against it in that native currency at matched output tokens?
1 comment
Reviewer_uJ2FOpenReview ↗

Main concern addressed; raising score

Thanks for running everything I asked for.

My main concern was that the gains came from the token accounting. The cache-aware rerun (+5.4 / +6.0 over BG-MCTS, CIs clear of zero) and the measured latency (9.1 s vs 17.9 s) largely settle that. I appreciate that you also show SCA+ only ties BG-MCTS at ~10k output tokens. Please keep that in the main text and qualify the "16% fewer tokens" line in the abstract/TL;DR, since it depends on how tokens are counted.

The depth-cap analysis (U7/U8) answers my question about the fixed-width gap, and the 2x2 ablation shows the two components add up roughly independently.

What remains: the gain model is only weakly calibrated on MATH (rank corr 0.26, single-decision effect not significant at deployment), so I'd present it as a useful heuristic rather than a calibrated estimator. Scope is still one model family and one PRM.

My main concern is addressed, and I'm raising my score from 2 to 3.

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

The paper studies why wider verifier-guided search can fail under a fixed budget. SCA+ combines a predicted widening gain with a reserve for completing one path. A controller developed on planning transfers to MATH and improves accuracy under total-token accounting.

Critical strengths
  1. Separating retention, progress, completion, and selection gives a useful diagnosis of search failure. The comparison with BG-MCTS is particularly informative: similar correct-answer discovery can still produce different final accuracy.
  2. The completion reserve is supported by ablations and transfer without refitting. Shared selectors and task-level confidence intervals make the main accuracy comparison credible.
Critical weaknesses
  1. Efficiency depends strongly on counting input and output tokens equally. Appendix J shows that output-only accounting can reverse the ordering against BG-MCTS. The sensitivity is reported honestly, but measured latency with caching and batching is needed to establish practical savings.
  2. The gain model is trained against width-1 future continuations, while deployment repeatedly changes width. Forecast calibration on deployed trajectories is unmeasured. This matters because errors near the gain threshold directly alter allocation, and the planning-to-math transfer may amplify them.
Questions for authors
  1. Clarification: how well do predicted gains and completion probabilities match outcomes on deployed math trajectories?
  2. Suggested comparison: does SCA+ retain its cost advantage in an implementation using cached prefixes and batched verification?
Reviewer_BBeBOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2(+1)
Presentation
2
Soundness
2
Read review
Paper summary

In test-time search, partial solutions are determined by a verifier which ones to keep. The paper asks how many branches should be kept per step when there is a token budget. An extra branch is only worth it when it survives a layer of selection, advances toward the goal, finishes with a complete answer before the budget runs out, and wins the final vote among the completed answers.

Critical strengths
  • Strong efficiency results on MATH that shows it matches best-of-n, and beats BG-MCTS with fewer tokens.
  • Honest limitations section. The authors admit that the cost advantage depends on how cost is counted. They openly flag the training–deployment mismatch and the single model family.
  • The paper provides a useful practical takeaway that researches can apply - under a fixed budget, widen only when it's worth it, and always save enough to finish one path.
Critical weaknesses
  • The main algorithm lacks novelty. SCA+ is similar to BG-MCTS but learned with a hard budget and a completion reserve. Adaptive width is presented as the main contribution. However, dynamic-width beam decoding is a known technique.
  • The 'wider is worse' motivation is not well founded. When width increases, the performance drops because the runs never finish. However, any budget-aware method such as BG-MCTS already avoids this. It is also possible to just simply force an answer at the end. A fairer motivation would be a fixed-width beam that also forces a final answer at the end.
  • The claim of using fewer tokens depends on counting verifier input tokens. There is no measured run time and FLOPs as cost metrics for fair comparison.
  • Only one model family Qwen is used with one process reward model. There is no harder test or cross-domain test such as competition level maths or code.
  • Planning uses four classical domains with exact distance labels but this is far from realistic LLM planning.
  • The thresholds (85% finish quantile, 0.02 minimum gain) and the width range of 1-5 look tuned on development runs. A sensitivity sweep would show whether accuracy stays flat across values or peak sharply at the chosen ones. Since SCA+ never picks width 4 or 5, the method may in practice reduce to a simple rule such as "width 2 early, width 1 later."
Questions for authors
  • How does SCA+ compare with a fixed rule ("2 branches for L layers, then 1") that uses the same reserve and budget ledger, with L tuned?
  • How were the 85% finish point and the 0.02 minimum gain chosen? Can you show a sensitivity sweep?
  • SCA+ never chooses width 4 or 5. Is the range {1,…,5} meaningful, or does the method only ever choose between 1 and 2?
  • Have you tested another model family (e.g., Llama or Gemma), harder math (AIME, OlympiadBench), code, or realistic agent tasks (ALFWorld, WebShop)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.