When a language model answers a hard question by sampling many reasoning attempts and keeping the one a scoring model likes best (Best-of-N), every attempt runs to completion. This holds even for attempts that, halfway through, clearly cannot beat an answer already in hand. Classical search solved this problem decades ago with branch-and-bound. The best complete solution found so far, the incumbent, sets a bar. Any partial candidate whose optimistic bound on final quality falls below that bar is discarded. As better incumbents arrive, the bar rises and pruning accelerates. We propose to bring this feedback loop to language-model reasoning. Each partial reasoning trace gets a calibrated optimistic estimate of the score its finished answer would receive. A trace is stopped as soon as that estimate falls below the best finished trace's score.
The payoff is a guarantee of a kind current LLM pruning methods lack. The pruned search returns the same answer that full Best-of-N would have returned, except with a user-chosen probability α. The guarantee is certified on unlabeled prompts, because "same answer as full Best-of-N" needs no ground truth. This is the statistical counterpart of the safe-pruning result in Fast Iterative Hard Thresholding Methods with Pruning Gradient Computations. That paper skips up to 98.87% of gradient computations while provably reproducing the exact trajectory of the unpruned algorithm. Compute then flows unevenly by construction. Easy prompts produce a strong early incumbent and most traces die young. Hard prompts produce weak incumbents and traces are allowed to run.
Core Claim
Two current families of pruning methods for reasoning search tie their thresholds to nothing that changes during the search. Rank-based tournaments prune the K worst traces every Δ steps, as in Thought-Level Beam Search for Reasoning. Fixed similarity or score cutoffs are used in Chopping Trees. None of these thresholds tracks what the search has already achieved, and none comes with a statement about what the pruning costs. We claim that three ingredients together give a pruning rule that adapts per prompt and per moment and has a certified fidelity guarantee:
- An incumbent-driven threshold, which rises as better complete answers arrive.
- A learned optimistic bound on each partial trace's final score.
- Calibration of the bound's slack by Learn-then-Test, a distribution-free procedure that picks a threshold so that a chosen risk stays below α with high confidence.
We further claim the incumbent is the load-bearing part. A fixed cutoff calibrated to the same risk level must be conservative enough for the hardest prompts, where all scores are low. It therefore wastes compute on easy prompts. The incumbent rule should not have this problem.
Research Program
The setting is Best-of-N with an outcome scorer $s(\cdot)$. For math this is a process reward model's final-step score. For code it is the test pass rate, as in Adaptive Generate-Rank-Verify. N traces are generated in parallel, and the output $\hat y_{\text{BoN}}$ is the completed trace with the highest score.
The bound. We train a small head on the generator's hidden states at thought boundaries (double newlines). The head predicts a high quantile of the score the trace will eventually receive. The design follows the linear probes of Thought calibration and the hidden-state scorer of Gambit. The training target differs from both. Thought calibration predicts whether the current answer will change. Gambit predicts relative quality for ranking. We predict an optimistic value of the final score by quantile regression, on the model's own rollouts, so no labels are needed.
The rule. Let $\hat u(p)$ be the predicted upper quantile for partial trace $p$. Let $s^*_t$ be the best score among traces completed by time $t$, and let $\lambda \ge 0$ be a slack margin. Trace $p$ is pruned at time $t$ when
$$\hat u(p) + \lambda < s^*_t .$$
Before any trace completes, $s^*_t = -\infty$ and nothing is pruned. Reasoning traces vary widely in length, so short completions usually establish an early incumbent. We also test a single "scout" trace with a short token cap that seeds $s^*$ early.
The guarantee. Define the fidelity loss as the event that the pruned search returns a different answer from full Best-of-N on the same random seeds. On a calibration set of prompts we run full Best-of-N once and replay the pruning rule offline for a grid of λ values. Learn-then-Test then selects the smallest λ satisfying
$$\Pr\left[\hat y_{\text{pruned}} \neq \hat y_{\text{BoN}}\right] \le \alpha \quad \text{with probability at least } 1-\delta \text{ over the calibration draw.}$$
Here α is the tolerated fidelity loss and δ the confidence level. The file names distribution shift as the key weakness of conformal guarantees for thought calibration. Because our loss needs no labels, it can be recalibrated on a few hundred unlabeled prompts from the target distribution. This is the main practical difference from thought calibration's single-trace stopping.
Checking cost. Scoring every trace at every thought boundary costs compute. The bidirectional-search literature, in Front-to-End Bidirectional Heuristic Search, shows that expensive fixpoint bounds lose in wall-clock time to cheaper ones. We therefore borrow the interval rule of Fast IHT. If a check prunes nothing, the interval before the next check on that trace doubles. It resets when the incumbent improves. This makes the check schedule adapt to the search, in contrast to Gambit's fixed Δ.
Two operating modes. In equal-output mode, pruned traces are simply freed, and the method saves tokens while matching Best-of-N within α. In equal-budget mode, freed slots launch fresh samples. This respects Gambit's finding that subtractive pruning starves the hardware. The guarantee is stated only for equal-output mode. Equal-budget mode is evaluated on accuracy.
Baselines
The naive reference is full Best-of-N with the same generator, scorer, N, and seeds. It defines the fidelity target and the token cost we aim to cut. Its accuracy is the ceiling for equal-output mode.
The strongest existing competitor is Gambit, Thought-Level Beam Search for Reasoning. It runs periodic tournaments that prune the K lowest-scoring traces and branch from the K best prefixes. It reports +6.7% on HMMT-24 and +3.3% on AIME-25 over subtractive pruning, token cuts of up to 68.5% versus parallel sampling, and over 2x trace throughput. The file gives no absolute Gambit accuracies, so we reimplement it. We use the same generator, the same hidden-state head architecture, and a Δ and K grid searched on the same development prompts as our λ. Beating it means equal-budget mode reaching higher accuracy at matched tokens on AIME and HMMT. It also means equal-output mode spending fewer tokens at matched fidelity. Gambit offers no fidelity control, so we sweep its hyperparameters and compare along the whole curve.
Two sample-level stoppers are included. Early-Stopping Self-Consistency, Escape Sky-high Cost, stops sampling on windowed consensus. It reports 80.1% fewer samples on GSM8K and 33.8% on MATH, with accuracy within 0.1% of full self-consistency. ADAP, from Adaptive Generate-Rank-Verify, reports 2.9x lower verification cost on HMMT and 5.5x on LiveCodeBench versus fixed budgets. Both stop whole samples rather than partial traces, so they test whether mid-trace pruning adds anything. For tree-search context we report LiteSearch (82.3% on GSM8K at 0.55k tokens versus 80.1% for tree-of-thought breadth-first search at 2.22k). We also report Chopping Trees (85–90% fewer nodes, within about 5% accuracy). Both are compared on GSM8K and MATH500 in tokens-to-accuracy.
Two ablations isolate the ingredients. The first replaces $s^*_t$ with a fixed cutoff, also calibrated by Learn-then-Test to the same α. This isolates the incumbent. The second keeps the incumbent but uses the raw point prediction with λ tuned by hand rather than certified. This isolates calibration.
Why not just…?
Why not just use Gambit's rank tournament with tuned K and Δ? Rank pruning removes a fixed fraction of traces regardless of quality. On an easy prompt it keeps too many. On a prompt where the best trace happens to rank low early, it can remove it, and nothing bounds how often that happens. This is a real competitor on raw accuracy in equal-budget mode, and it may win there. The equal-output fidelity-versus-tokens curve will show whether the incumbent rule dominates at every operating point or only at low α.
Why not just prune below a fixed score cutoff? This is the most serious threat, because a well-tuned cutoff is simple and cheap. Our argument is that a single cutoff safe for the hardest prompts is too loose for easy ones. The calibrated fixed-cutoff ablation tests exactly this at identical α. If it matches the incumbent rule's token savings, the incumbent adds nothing and we will report that. We expect the gap to be largest on mixed-difficulty sets such as MATH500 across its five levels, and we break results down by level.
Why not just stop sampling early, as ESC or ADAP do? Whole-sample stopping saves nothing on traces already launched in parallel, and parallel launch is how serving systems run Best-of-N. ESC is also vulnerable when the model repeats the same wrong derivation, as its authors note. Running both in the same parallel setting, and combining ESC with our rule, will show whether the savings stack.
Proposed Experiments
Models and tools. Generators are Qwen-family reasoning models and AceReason-Nemotron-14B, evaluated with NeMo Skills.
Math scorer. For math we use a process reward model. As a secondary scorer we train one with the ranking objective of Process Reward Model with Q-value Rankings. That model reports 51.4% versus 39.8% on MATH500, and its sharp score drops at the first error should make optimistic bounds tighter.
Code scorer. For code we use LiveCodeBench test pass rates.
Benchmarks and budgets. Benchmarks are GSM8K, MATH500, AIME 2024/2025, HMMT 2024/2025, GPQA-Diamond, and LiveCodeBench, with N in {16, 64}.
Metrics. We report empirical fidelity to full Best-of-N against the target α ∈ {0.01, 0.05, 0.1}. We also report generated tokens and wall-clock time, including probe overhead, and final accuracy.
Decisive checks. Four results would decide the question.
- Realized fidelity loss stays at or below α on held-out prompts from the calibration distribution.
- At α = 0.05, token savings exceed the calibrated fixed-cutoff ablation, with the gap growing with the spread of prompt difficulty.
- Under shift, calibrating on MATH and testing on AIME and HMMT, the guarantee is violated as expected. Recalibrating on 200 unlabeled target prompts restores it.
- The adaptive check interval keeps probe overhead to a small fraction of generation time without reducing savings relative to checking every step.
If the second check fails, the core claim fails, whatever the absolute savings.
References
- Fast Iterative Hard Thresholding Methods with Pruning Gradient Computations
- Thought-Level Beam Search for Reasoning
- Chopping Trees: Semantic Similarity Based Dynamic Pruning for Tree-of-Thought Reasoning
- Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification
- Thought calibration: Efficient and confident test-time scaling
- Front-to-End Bidirectional Heuristic Search with Consistent Heuristics: Enumerating and Evaluating Algorithms and Bounds
- Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning
- LiteSearch: Efficient Tree Search with Dynamic Exploration Budget for Math Reasoning
- Process Reward Model with Q-value Rankings