Guidance Headroom: Measure the Room for Step Guidance Before Investing in Reward Models

Research perspective: new measurement instrument. What reviewers would remember is something concrete and reusable: a 30-problem, R=m=4 "checkup before investing in a PRM," and a plot showing that the point at which outcomes become distinguishable moves later when a model with the same base undergoes SFT-distill → RL. The prerequisite is that it predicts actual PRM gains on held-out models. If the work only shows that V can explain H, reviewers will regard it as an identity and will not remember it.

Before training a PRM or performing step-level tree search, teams usually do not know whether outcomes for a particular model×benchmark combination are already distinguishable at intermediate steps. Reported PRM gains confound three factors: policy headroom, scorer quality, and problem difficulty. This proposal introduces a scorer-independent measurement tool: for each problem, sample R prefix roots at depth d, generate m continuations from each root, score them with the benchmark checker, and split the continuations into an estimation half and a held-out evaluation half to remove the winner's curse. We use one-way ANOVA to remove within-root binomial noise, obtaining the between-root variance component sigma_d^2 and its normalized form V(d); provide an upper bound on oracle gain restricted to single-stage pruning (based on Aven's expected-maximum bound); and define multi-stage oracle headroom H on a cached nested tree. The central test is not whether V can "explain" H (which is close to an identity), but whether a cheap estimate (R=m=4, about 30 problems) can predict actual gains from PRM-guided beam search and best-of-N under leave-one-model-out evaluation using independent rollouts. We also construct an atlas of outcome-resolution timing for base / SFT-distill / RL / instruct variants sharing the same base, on pass-rate-matched problem subsets. This proposal introduces no new search algorithm.

The gains from PRM-guided best-of-N and beam search differ substantially between models, and are often very small for RL models with long CoT. It is currently impossible to distinguish whether this reflects poor PRM quality (low capture), a policy that inherently offers no exploitable signal at early prefixes (low headroom), or problem difficulty. Training a PRM is expensive (requiring step labels or MC rollouts), so an advance go/no-go judgment is needed. With a budget of 8×A100, 4 months, and 2 PhD students, this measurement must be cheap and must be testable against independent actual gains, rather than merely being a self-consistent definition.

The usual practice is to compare PRMs using ProcessBench AUROC or search gains; both entangle the scorer and the policy. Math-Shepherd / OmegaPRM use the same MC rollouts, but only as training labels. Reinterpreting them as policy-level headroom requires a conceptual shift: a PRM can at best match the oracle value function. It must be acknowledged candidly that many experts would already expect "late resolution in RL models with long CoT." The real novelty can therefore come only from precise quantification, an upper bound with an explicit scope, and non-circular prediction of actual gains, rather than from the direction of the result itself.

1. Nested rollout tree and depth definition: for each problem, sample R prefix roots at 4 depths (R=8 for the full version, R=4 for the cheap version), with m continuations per root (8 or 4), scored by the checker. Depth must not depend on an unknown final length. The primary setting uses absolute token offsets or a step-count grid; percentage depths serve only as a comparison normalized retrospectively on completed reference chains. Compare newline, double-newline, and fixed token windows for step segmentation, and report the profile's sensitivity to segmentation. Define boundaries separately for code and GPQA (statements/function blocks for code, paragraphs for GPQA). This component is currently underspecified and must first be settled in the pilot.
2. ANOVA-corrected resolution profile: split continuations into estimation and evaluation halves; use one-way ANOVA to remove within-root binomial variance, obtaining an unbiased between-root variance component sigma_d^2 and the normalized V(d)=sigma_d^2/(p(1-p)); compare these with the naive estimator. Note that after splitting m in half, each half contains only 4 continuations, making individual-root estimates very noisy. Aggregate mainly at the problem/cell level rather than relying on individual-root values.
3. Upper-bound theorem for single-stage pruning: for n prefixes with the oracle retaining the top-k, the accuracy gain over unguided sampling at equal token budgets is at most sigma_d*(n-1)/sqrt(2n-1) (k=1, Aven's bound), with a similar form for general k. This holds only for single-stage pruning; best-of-N reranking of complete solutions is outside the scope of V(d). State the assumptions explicitly in the paper (conditionally i.i.d. continuations and the conversion to equal token budgets), and report the ratio of the bound to the measured oracle gain.
4. Multi-stage oracle headroom H: define it on a survivors-only nested tree. At each depth, branch only from the preceding layer's top-k surviving prefixes to avoid exponential growth, and specify a token budget for each model×dataset. H is the accuracy of oracle-guided successive halving / beam search under a fixed budget minus the equal-token majority-vote or pass-rate baseline, with selected leaves evaluated using the held-out half. H is only an empirical reference value on a finite tree, not an upper bound for all search algorithms; report the final verifier's pass@N headroom separately to distinguish the early-guidance component.
5. Non-circular primary test: use the cheap estimate (R=m=4, one rollout set) as the predictor, and independently sampled rollouts for the outcome, to predict actual guidance gains (tuned Qwen2.5-Math-PRM / Math-Shepherd best-of-N and beam search, plus a label-free consistency-guided baseline). Conduct leave-one-model-out evaluation on held-out models and problems. Downgrade the mixed-effects regression of H on V to a consistency check; it is no longer the primary hypothesis.
6. Regression-based decomposition of PRM gain: abandon the presentation of 'Gain_PRM = H × capture' as an identity. Replace it with the explicit regression gain ~ H + capture + H:capture, where capture is the within-group rank correlation, computed per problem, between PRM prefix scores and held-out MC p_d (Kendall tau / AUROC). Optionally derive the relationship between selection gain and AUROC under an assumed Gaussian latent-value model, as a supplement rather than a central claim; also replace oracle-MC with PRM scores within the same recursive search to isolate the role of capture.
7. RL vs SFT vs base atlas: use model pairs sharing the same base (for example, Qwen2.5 base → SFT-distill → RL → instruct variants), and compare them on pass-rate-matched problem subsets so that p(1-p) is equal across variants, separating 'late resolution' from difficulty and chain length. Include no fewer than approximately 30 cells, 8–10 models, and sizes of 1.5B–32B; for 32B, use at most 2 datasets with 60 problems each.
8. Cheap go/no-go version: evaluate whether estimates using R=m=4 and 30 problems suffice to rank models and agree with full estimates and actual gains; provide stability and fidelity curves.

Each cell is a model×dataset combination. Cache nested rollouts (a survivors-only multi-stage tree) and split them into estimation/evaluation halves. Use independent rollouts for predictors and outcomes. For actual guidance, use tuned PRM best-of-N and beam search (tuning beam width and step segmentation), compared at matched token budgets. Conduct power analysis in advance (simulating with variance components from the pilot) to determine the number of problems per cell. Use pass-rate-matched subsets for the atlas. Compute: 8×A100, approximately 150 GPU-hours for the pilot and approximately 700 GPU-hours for the full study (primarily 1.5B–14B; for 32B, at most 2 datasets with 60 problems each).

• datasets: MATH-500 (near saturation for strong RL models, p(1-p)→0; requires pass-rate matching or selecting only moderately difficult problems); an OlympiadBench subset; combined AIME24+25 (60 problems, very wide confidence intervals); GPQA-Diamond; LiveCodeBench (test execution, a subset); GSM8K only as a saturation sanity check, excluded from the primary test
• baselines: Predictor baselines for PRM gains: PRM ProcessBench F1; policy pass rate/final-answer entropy (difficulty); mean chain length; p(1-p); and combinations of these. Equal-token majority voting and pass-rate-matched unguided sampling as references for gains. Actual guidance: Qwen2.5-Math-PRM and Math-Shepherd best-of-N and beam search (tuned beam width and step segmentation, including newline and double-newline for long CoT). A label-free consistency/agreement-guided baseline (corresponding to the seed idea in the brief). Oracle-MC-guided search and final-verifier pass@N headroom as references. A naive (uncorrected) variance estimator.
• metrics: Primary: prediction error and Spearman correlation for the cheap estimate's (R=m=4) predictions of actual guidance gains (PRM beam/BoN and label-free guidance) under leave-one-model-out evaluation; compare differences in correlation against the difficulty/length/ProcessBench baselines above using Steiger/bootstrap tests. Secondary consistency check: a problem-level mixed-effects model (random intercepts for model and dataset, with problems nested within cells); report the likelihood-ratio test and partial R^2 for adding V(25%) to p(1-p)+length+difficulty, explicitly noting that this result is close to being implied by construction. Regression coefficients and the interaction term in gain ~ H + capture + H:capture. The proportion of oracle H captured by the best actual PRM method. The ratio of the single-stage upper bound to measured oracle k=1 pruning gain (tightness). The RL vs SFT difference in V(25%) after pass-rate matching, with bootstrap CI (resampling problems first, then models). Sensitivity to m, R, depth definitions, and segmentation.
• ablations: Depth grid, R, and m (estimation stability and fidelity of the cheap version); naive vs ANOVA-corrected estimators; depth definitions based on step boundaries vs fixed token windows vs absolute token offsets; held-out evaluation half vs selection on the same half (quantifying the winner's curse); per-problem vs aggregated profiles; base / SFT-distill / RL / instruct variants within the same family; replacing oracle-MC with PRM scores in the same recursive search to isolate capture; pass-rate-matched vs unmatched comparisons
• expected: RL variants with long CoT are expected to have lower V(25%) (late resolution) and smaller H for early pruning; the cheap estimate is expected to rank actual PRM/beam gains on held-out models better than difficulty/chain-length/ProcessBench baselines; capture is expected to decrease further on long CoT, allowing the two causes to be separated. These are expectations, not conclusions: the most likely failures are high collinearity between V and p(1-p), or failure of the cheap estimate to generalize to held-out models.
• falsification criteria: Preregister these criteria, revised into a non-circular form in response to the red team: (a) if the cheap estimate (R=m=4, independent rollouts) does not predict actual PRM/beam gains better than the p(1-p)+chain-length+ProcessBench F1 baseline under leave-one-model-out evaluation (Steiger/bootstrap p>0.05 and error reduction below a prespecified minimum magnitude), abandon the diagnostic-tool claim and reduce the paper to an atlas. (b) If the V(25%) difference between RL and SFT variants sharing the same base is not significant after pass-rate matching, withdraw the 'late resolution' claim. (c) If the single-stage bound is more than 5 times the measured oracle gain in most cells, report it as uninformative. Retain the original likelihood-ratio test of V explaining H (p>0.05 and partial R^2<0.03) only as a consistency check, because it holds almost by construction and cannot serve as an effective kill criterion.

1. Days 1–2: build a nested-rollout pipeline using vLLM + prefix caching; establish the depth definition (absolute token offsets/step counts) and step segmentation; run a smoke test on 20 MATH problems to verify the checker, splitting into halves, and caching. In parallel, read Critical Horizon and Branching Policy Optimization in full to establish the degree of overlap in theorems and estimators and decide whether to adjust the positioning.
2. Days 3–6: using Qwen2.5-7B-Instruct, DeepSeek-R1-Distill-Qwen-7B, and one 7B/14B RL variant, cache R=8 × 4 depths × m=8 rollouts (split into halves) on 100 MATH-500 problems and the combined 60-problem AIME set. First use pass rates to select moderately difficult problems, avoiding p(1-p)→0.
3. Days 7–9: compute ANOVA-corrected sigma_d^2 and V(d); compare single-stage oracle gain with Aven's bound; compute multi-stage H on the survivors-only tree (including held-out evaluation). Examine differences between naive and corrected estimators.
4. Days 10–12: run Qwen2.5-Math-PRM best-of-N/beam at matched token budgets to obtain actual gains and compute per-problem capture; sketch a small-scale gain ~ H + capture regression, and check agreement between the cheap version (R=m=4, 30 problems) and the full version.
5. Days 13–14: conduct power analysis using the pilot's variance components to determine the problem count per cell for the full experiment; perform an interim go/no-go review against the prespecified kill criteria and record the decision on whether to reduce the scope to an atlas. Note: a 3-model pilot is insufficient to test leave-one-model-out prediction; it can only test whether the quantities can be estimated stably and whether the bound holds.

• The primary test is nearly circular: H is defined by selection using MC p_d, and V is the variance of the same p_d; V explaining H holds almost by construction (the red team's fatal issue). → Change the primary outcome to prediction of actual PRM/beam/label-free guidance gains using a cheap estimate from independent rollouts, with leave-one-model-out evaluation; use the V→H regression only as a consistency check.
• V(d) is collinear with difficulty p(1-p), making the diagnostic redundant. → Use pass-rate-matched subsets and comparison baselines; if it remains redundant, reduce the scope to an atlas under the kill criteria.
• Depth definitions and step segmentation alter the profile (percentage depth for long CoT requires an unknown final length). → Use an absolute token/step-count grid as the primary setting and report sensitivity to multiple segmentation methods; settle code and GPQA boundaries first in the pilot, narrowing the scope to mathematics if necessary.
• Compute costs of the multi-stage oracle tree and optimistic bias on a finite tree. → Use survivors-only branching and held-out-half evaluation; reduce the grid to subsets of approximately 6 models×3 datasets; use 32B only in a few cells; analyze sensitivity to m.
• Splitting m=8 leaves only 4 continuations in each half, so individual-root estimates are noisy; AIME has only 60 problems and wide confidence intervals; MATH-500 is saturated for strong models. → Aggregate at the cell/problem level, determine problem counts through power analysis, and increase m or problem counts if necessary; select only moderately difficult problems from saturated datasets.
• PRMs fail out of distribution on long CoT, allowing capture to dominate the actual-gain test. → Model capture explicitly and include label-free consistency guidance as an outcome that does not depend on a PRM.
• Model family, training regime, and difficulty are confounded; others may publish first (the atlas is easy to reproduce). → Use same-base model pairs + pass-rate matching; release the cheap go/no-go tool and preregistered results promptly, focusing the contribution on the non-circular prediction test.
• Most experts already expect the 'late resolution' direction, limiting novelty. → Emphasize quantification, a scoped upper bound, and prediction of actual gains; if the prediction test fails, position the paper honestly as a small analysis rather than a methods paper.

• Q: The primary hypothesis is nearly tautological: H is the gain from selecting prefixes using MC p_d, and V(d) is the between-prefix variance of that same p_d; using V to explain H beyond p(1-p) largely amounts to verifying an identity. A: This criticism is largely valid. Our response is to change the design rather than defend it: make the primary outcome prediction of actual PRM beam/best-of-N and label-free guidance gains using a cheap estimate collected from independent rollouts (leave-one-model-out), retain V→H only as a consistency check, and rewrite the kill criteria accordingly. If the cheap estimate cannot predict actual gains, reduce the paper to an atlas.
• Q: The stated rollout design cannot produce held-out multi-stage oracle H for 10→25→50→75→100%; a complete implementation requires an exponentially branching tree, exceeding the compute budget. A: The original description was indeed insufficient. Revise it to a survivors-only tree: at each depth, branch only from the preceding layer's top-k surviving prefixes, assign token budgets by model and dataset, and reduce the grid to subsets of approximately 6 models×3 datasets. H is only an empirical reference value on a finite tree. The concrete token cost still needs to be measured in the pilot; the current estimate of 700 GPU-hours has not been verified.
• Q: 'Gain_PRM = H × capture' is not an identity, and rank correlation does not map multiplicatively to selection gain; there is no derivation. A: Agreed. We will no longer treat it as an identity, replacing it with the explicit regression gain ~ H + capture + H:capture and testing the interaction term. If the relationship between selection gain and AUROC can be derived under an explicit model such as a Gaussian latent-value model, we will provide it as a supplement; otherwise, retain only the empirical regression.
• Q: Depth is defined as a percentage of final length, but the final length of long CoT is unknown in advance; segmentation can also change the profile substantially. A: Change the primary setting to absolute token offsets/step counts, use percentage depth only as a comparison, and report sensitivity to multiple segmentation methods. The boundary definitions for code and GPQA are currently underspecified, a known gap to resolve in the pilot; otherwise, narrow the scope to mathematics.
• Q: 'Late resolution in RL models' is already widely expected and offers limited novelty; RL, SFT, difficulty, and chain length are also confounded. A: The direction is indeed unsurprising. The contribution lies in quantification, same-base comparisons and pass-rate matching, and whether it can predict actual gains. If the difference disappears after pass-rate matching, we will withdraw this claim (kill criterion b).
• Q: The work is too close to Critical Horizon and other 2026 papers, and others may produce an atlas quickly. A: We can judge the mechanisms to be similar only from the supplied excerpts; the distinctions are held-out estimation, a scoped upper bound, and a test of prediction of actual PRM gains. These must be confirmed by reading the full papers on the pilot's first day. The atlas is indeed easy to reproduce, so the focus is on the prediction test.

ICLR (or the analysis/evaluation track of NeurIPS). This is a paper focused on understanding or providing a tool, and it fits only if the statistical design is rigorous and the cheap estimate can predict actual PRM/search gains on held-out models. If only the result that V explains H remains, it will be regarded as verifying an identity and the fit will be weak; in that case, reduce the work to an atlas or submit to a workshop. The overall internal-review judgment is borderline (individual scores of 2–3, with evidence_plan the lowest).