cs.LGOct 4, 2026
SaveExpanding LLM Reasoning
Organizations: Keiji AI · University of California, Berkeley
Abstract
Extra inference compute is usually spent on sampling more reasoning chains. We study where inside an existing chain an additional continuation should begin. We define expansion utility, the change in correctness from restarting a chain at a stored step, and measure it at every eligible step for nine models on six benchmarks (41 model and benchmark cells). Restart position matters: steps selected on one set of continuations beat uniform placement when scored on disjoint ones, in held-out audits on 5, 16, and 38 cells (+4.25 points [+2.51, +6.63] in a fresh five-cell audit). A fixed rule that restarts from the last eligible steps, always-last, is a strong baseline: our learned router beats uniform placement but shows no detected gain over it, and on DeepSeek-R1-Distill-Qwen-14B/MATH-500 always-last exceeds the exact self-consistency frontier at matched aggregate generated output by +0.052 [+0.008, +0.098], using 0.774x the aggregate generated output of four-sample self-consistency. Cross-fitted oracle selection still finds held-out headroom beyond declared positional classes, a target for future selectors. Finally, breaking step-label ties by earliest index flips the sign of a pointwise selector's gain over uniform placement in every seed of a five-seed diagnostic with four rollouts per step; randomized ties remove the bias.
Figures & tables
Figure 1: Expansion utility. Restarting a stored chain at step keeps the prefix and samples continuations. Their success rate , taken over all eligible steps, forms the chain’s restart map, and is the expansion utility of restarting at . In this schematic an early restart rarely succeeds and a late one usually does.
Figure 2: Study design. We restart a stored chain at every eligible step and sample continuations (measure); estimate opportunity from the resulting restart map, both on the same draws and on held-out draws that separate selection from scoring (estimate); and compare placement rules (uniform, always-last, and a learned router), with a confidence gate that decides whether to spend a restart at all (decide).
Figure 3: Same-draw restart opportunity varies widely across cells. Each dot is one model and benchmark cell: the Eq. ( 2 ) advantage of the top-ranked steps at a budget over the chain’s mean eligible step, in percentage points; ticks mark benchmark means. The statistic is non-negative by construction; Figure 4 tests whether the selection replicates on held-out draws. The two exploratory Putnam cells (hollow, ) are excluded from aggregates. Per-cell values are in Appendix Table 2 .
Figure 4: Held-out scoring. Advantage of selected restart positions over uniform placement when the same draws select and score (gray) and when selection and scoring use disjoint draws (blue), with intervals where available. The protocols estimate different selectors and cover different cells (Appendix B ).
Figure 5: Placement, spending, and oracle headroom. (a) Paired GR@10 differences over split seeds: the router against uniform placement (both ungated) and against always-last (both ungated, and both gated), and the gate’s effect on each policy (orange involves the router, blue is always-last). Intervals are split-seed stability intervals on one frozen store, not problem-population intervals. (b) Held-out restart-success residual of cross-fitted oracle selection beyond the declared 21-policy depth class and the enriched positional class, in both directions (A to B: sample A selects, sample B scores); numbers at right count cells with a positive residual out of . Intervals resample examples pooled across cells (depth class) or problem clusters (enriched class). This is an oracle target, not a feasible-policy gain. Exact values are in Appendix Tables 7 , 5 , and 6 .
Figure 6: Always-last is more accurate than self-consistency at matched aggregate generated output in the tested cell (DeepSeek-R1-Distill-Qwen-14B/MATH-500, problems, seeds). Left: hollow circles are the best mix of SC(1) to SC(4) at each policy’s own generated output; filled circles are the policy. Margins are for always-last and for the router ( paired bootstrap; Appendix Table 10 ); their difference is not detected. Right: aggregate generated output relative to SC(4), not total tokens or wall-clock time.
Figure 7: Label ties can flip a pointwise selector. (a) Schematic: one chain’s correct continuations out of four at each step (darker cells are higher; outlined cells tie at the maximum). Earliest-index tie breaking always labels the first tied step, which injects an early-position signal; randomized tie breaking labels one tied step at random. (b) GR@10 in a five-seed diagnostic (bars are means; whiskers span the minimum to maximum across seeds), where zero is uniform placement: pointwise BCE moves from with earliest-index ties to with randomized ties, while ListNet is under either rule. Fair-label loss contrasts are in Appendix Table 12 .
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| Quantity | Estimate | Coverage |
|---|---|---|
| Formal Eq. ( 2 ) advantage | pp | positive |
| Pooled eligible-position Gini | cells | |
| Mean within-example eligible Gini | cells | |
| Maximum observed utility | pp | different estimand |
Table 1: Measurement summary. The primary set contains cells; the complete display contains two additional exploratory Putnam cells with . Pooled Gini is computed after pooling positive utility over eligible positions within a cell. The final row is a different estimand from Eq. ( 2 ).
| Model | Benchmark | Eq. (2) pp | pooled Gini | max-utility pp | |
|---|---|---|---|---|---|
| DS-R1-Llama-8B | MATH-500 | 500 | +14.69 | 0.778 | +28.90 |
| DS-R1-Llama-8B | GPQA | 198 | +17.20 | 0.836 | +25.63 |
| DS-R1-Llama-8B | HumanEval | 164 | +9.87 | 0.854 | +19.82 |
| DS-R1-Llama-8B | AIME 2025 | 30 | +2.77 | 0.984 | +2.50 |
| DS-R1-Llama-8B | HMMT | 30 | +9.83 | 0.928 | +11.67 |
| Nemotron-Nano-8B | MATH-500 | 500 | +16.17 | 0.760 | +29.60 |
Table 2: Per-cell measurement record. Putnam rows are exploratory and are excluded from the 41-cell primary aggregate. The max-utility column averages each example’s largest observed utility, a different estimand from Eq. (2) that can fall below it because utility subtracts the base outcome.
| Protocol | Gap |
|---|---|
| Fresh-eight same-draw selection/scoring | |
| Stored winner, eight unseen scoring draws | |
| Fresh four select, disjoint four score | |
| Exhaustive tie-neutral stored 2/2 |
Table 3: Held-out scoring audits estimate different selectors. The five-cell audit has exact-prefix examples. The matrix-wide 2/2 audit covers the primary cells that retain individually labeled continuation outcomes. Values are cell-equal percentage-point advantages over the exact uniform-candidate comparator.
| Protocol | Cell-equal gap | Coverage | Positive cells |
|---|---|---|---|
| Separate A/B samples, symmetric 4/4 | pp | examples | |
| Every second exact boundary | pp | cells | |
| Every third exact boundary | pp | cells | |
| Four fixed normalized anchors | pp | cells |
Table 4: Separately generated samples and boundary density. The symmetric 4/4 result uses separately generated continuation samples at identical prefixes. Boundary thinning changes the candidate set and therefore the magnitude of the same-draw Eq. ( 2 ) statistic; it does not test semantic segmentation. The boundary-density sources report point estimates only, not population intervals.
| Direction | Residual | Positive cells |
|---|---|---|
| A selects, B scores | ||
| B selects, A scores |
Table 5: Held-out oracle-information residual beyond a declared 21-policy depth class. Five-fold cross-fitting, within-chain budget, records and cells; intervals resample examples pooled across cells. This is a held-out oracle residual over the selected depth rule, not a feasible selector’s gain or a deployed-accuracy result.
| Direction | Mean | Problem-cluster CI | Cell-cluster CI | Positive cells |
|---|---|---|---|---|
| A selects, B scores | ||||
| B selects, A scores |
Table 6: Nested-selected enriched positional sensitivity. The candidate family contains the original grid and regularized length-by-rank tables. It does not cover the full arbitrary positional class, and the selected enriched learner trails the original grid out of sample. Intervals cluster by problems or cells as labeled.
| Contrast | Estimate | Interpretation |
|---|---|---|
| Router uniform, ungated | stable in-distribution diagnostic | |
| Router always-last, ungated | no detected increment | |
| Gate effect on router | gate-on minus gate-off | |
| Gate effect on always-last | gate-on minus gate-off | |
| Difference in gate effects | no detected interaction | |
| Router always-last, gated | no detected increment |
Table 7: Separating placement from spending. GR@10 intervals are nominal paired split-seed bootstrap stability intervals on one frozen store, not problem-population intervals. The router-fitted gate threshold is applied unchanged to both placement rules. Crossing-zero intervals are reported as no detected paired difference, not as equivalence.
| Control | Estimate | Scope |
|---|---|---|
| Benchmark-conditional no support | matched seeds | |
| Remove learned depth prior | matched seeds | |
| PRM-feature text-feature variant, ungated | matched seeds | |
| PRM-feature text-feature variant, gated | matched seeds | |
| Log-probability text feature set | -seed matched coverage | |
| Hidden-state text feature set | -seed matched coverage |
Table 8: Component and feature controls. Component contrasts use matched split seeds and GR@10. The log-probability and hidden-state rows are matched-coverage 10-seed mean contrasts; their source artifact did not promote a population interval. Negative or crossing-zero results are reported as scoped nulls, not as evidence that a feature family is generally uninformative.
| Held-out domain | GR@10 over uniform | Positive fits |
|---|---|---|
| Code | ||
| Mathematics | ||
| Science |
Table 9: Within-suite domain-held transfer. The target domain is removed from training and validation, benchmark identity is disabled, and one shared late-only support is used. Estimates are router GR@10 over uniform with problem-cluster intervals. They do not establish improvement over always-last or transfer outside the benchmark suite.
| Policy | Acc. | Output ratio | Frontier | Delta |
|---|---|---|---|---|
| Always-last | ||||
| Router |
Table 10: Exact aggregate generated-output SC frontier on DeepSeek-R1-Distill-Qwen-14B/MATH-500. The panel contains problems and generation seeds. Ratios use aggregate generated output only; they do not measure total tokens or latency. CIs use paired problem bootstrap.
| Control | Estimate | Scope |
|---|---|---|
| Always-last over exact SC frontier | cell-equal, two available MATH cells | |
| Qwen3-32B/MATH-500 alone | individually unresolved | |
| PRM best-of- SC, DeepSeek | problems, seeds | |
| PRM best-of- SC, Qwen3-32B | problems, seeds | |
| Shallow PRM tree SC | generated output | |
| H200 always-last SC accuracy | total tokens; time |
Table 11: Scoped inference-scaling controls. The first two rows are a partial fixed two-model MATH sensitivity, not the incomplete planned 2-by-2 model-by-benchmark panel. PRM best-of- , the shallow tree, and the H200 assay use their own stated cohorts and ledgers and are not pooled with the exact DeepSeek frontier result.
| Protocol | Unmasked ListNet BCE | In benchmark-conditional support |
|---|---|---|
| Primary, 24 seeds | ||
| Locked extension, seeds |
Table 12: Fair-label loss contrast and locked seed extension. The 24-seed comparison is primary; the 64-seed estimate is a post-lock robustness extension, not an independent confirmation. Intervals cluster by problem.