Source-linked AI summary
Selective Regenerative Decoding: Trajectory-Level Intervention for Inference-Time Reasoning
Sophia Xiao Pu, Yumo Xu, Sailik Sengupta, Millennium Bismay, Ruixue Lian, James Gung, Yi-an Lai, Arshit Gupta
TL;DR
Inference-time decoding commonly treats trajectories as indivisible, discarding useful prefixes when later reasoning degrades. SRD performs segment-level routing and suffix regeneration, achieving stronger sample efficiency and matching Best-of-N accuracy with fewer tokens across four benchmarks.
Problem
Existing decoding methods treat reasoning trajectories as atomic, so irreversible rejection can discard high-quality prefixes when later steps degrade.
Method
SRD generates multiple candidates, routes each to keep, refine, or discard, and selectively regenerates degraded suffixes without requiring a larger target model.
Results
Across four benchmarks, SRD matches Best-of-N accuracy with fewer generated tokens and outperforms speculative rejection in low-compute regimes; theoretically, it gains 1.28–1.36× sample efficiency over rejection sampling.
Takeaways & Limitations
Segment-level intervention expands the accuracy–compute tradeoff beyond whole-trajectory selection and can complement speculative decoding and prefix value functions.
Takeaways & Limitations
SRD depends on fixed routing thresholds, heuristic boundary selection, and reward-model quality, which can cause suboptimal acceptance or salvage decisions.
Abstract
from arXiv · showhide
Inference-time decoding methods improve LLM reasoning by exploring multiple candidate trajectories, yet treat each trajectory as atomic: either retaining it whole or discarding it irreversibly. This wastes computation on partially promising candidates whose high-quality prefixes are abandoned alongside degraded suffixes. We introduce Selective Regenerative Decoding (SRD), which routes each candidate to discard, keep, or refine only the degraded portion of the suffix while preserving the useful prefix of borderline candidates, without requiring a larger target model. Under mild assumptions, SRD achieves a provable 1.28-to-1.36-fold gain in sample efficiency over rejection sampling with strictly higher expected trajectory quality, with the gain growing as the candidate pool grows. Across MATH500, GPQA Diamond, HotpotQA, and AlpacaEval with multiple generation-reward model pairs, SRD matches Best-of-N accuracy with substantially fewer generated tokens and outperforms speculative rejection in low-compute regimes. By enabling segment-level intervention rather than whole-trajectory selection, SRD opens a previously underexplored region of the accuracy-compute tradeoff for inference-time reasoning.
1 Introduction
Existing decoding methods either generate complete trajectories before selection or irreversibly terminate degraded candidates. SRD instead preserves useful prefixes and selectively regenerates degraded suffixes, with theoretical and empirical evidence of improved efficiency and accuracy–compute tradeoffs.
- Motivation: Best-of-N fully generates candidate trajectories before selecting the highest-scoring one, while speculative rejection terminates low-reward prefixes irreversibly.Both strategies treat trajectories as atomic units, so rejection can discard useful reasoning prefixes.
- Selective Regenerative Decoding: SRD generates multiple candidates, routes them to KEEP, REFINE, or DISCARD, and selectively regenerates degraded suffixes without requiring a larger target model.The method uses rank-normalized reward scores and higher-temperature sampling for refinement.
- Theory: 1.28–1.36× sample efficiency gain over rejection sampling is provably achieved under mild assumptions, alongside strictly higher expected best-trajectory quality.The gain grows with candidate-pool size and is characterized generally by (1 + ρ · pM/pH).
- Positioning: SRD is designed as a complementary decoding component that can be composed with speculative decoding and prefix value functions.Its core contribution is segment-level intervention without requiring a target model.
- Empirical evaluation: Across four benchmarks, SRD improves the accuracy–compute tradeoff, with ablations examining when refinement helps.The evaluated domains span mathematical reasoning, multi-hop question answering, and instruction following.
2 Related Work
Related inference-time methods guide local token or trajectory search using sampling, reward signals, pruning, or value functions. SRD extends trajectory pruning with explicit keep, discard, and refine decisions over multiple candidate paths without requiring a target model or prefix value function.
- Search-based decoding: Standard decoding methods explore local token neighborhoods or path neighborhoods through sampling, beam search, contrastive search, and Best-of-N.These methods differ in whether search expands around individual tokens or complete decoded paths.
- Reward-guided search: Reward-guided decoding can guide generation during the forward pass, through look-ahead, or across search graphs and trees.These approaches use informed heuristics to steer trajectories beyond the model’s encoded priors.
- Trajectory pruning: Speculative rejection evaluates candidate paths with a reward model and discards less promising prefixes early, but its binary decisions can permanently remove promising candidates.This makes rejection especially restrictive when early rewards underestimate later potential.
- Related approaches: Reward-Guided Speculative Decoding accepts or rejects draft steps and invokes a larger reasoning model after rejection, whereas Controlled Decoding uses a learned prefix value function for token selection.RSD operates on a single search candidate rather than exploring multiple candidates.
- SRD’s distinction: SRD evaluates multiple reasoning paths at each step and explicitly routes candidates to be kept, discarded, or refined through localized regeneration.This explores the search neighborhood without requiring a target model or prefix value function, though those components can be combined with SRD.
3 Approach
SRD treats reasoning trajectories as compositional: it keeps strong candidates, discards weak ones, and selectively regenerates degraded suffixes of borderline candidates. Its analysis establishes sample-efficiency and quality improvements under explicit refinement assumptions, alongside termination and monotonicity guarantees.
- Motivation: SRD preserves useful prefixes while intervening where trajectory quality drops, addressing irreversible loss from whole-trajectory rejection.This design targets long-form reasoning trajectories whose strong prefixes may be followed by degraded suffixes.
- Algorithm Overview: SRD generates candidate trajectories, routes them to KEEP, REFINE, or DISCARD using rank-normalized rewards, and regenerates only degraded suffixes of borderline candidates.Refined trajectories are re-evaluated and retained only if subsequently routed to KEEP.
- Sample Efficiency: Under refinement-efficacy and independence assumptions, SRD requires fewer samples than pure rejection sampling to obtain an acceptable trajectory with high probability.The comparison is formalized for failure probability δ using high-quality probability pH and refinement contribution ρ · pM.
- Sample Efficiency: The efficiency gain is most pronounced when high-quality trajectories are rare and refinable trajectories are both common and effectively refined.When ρ · pM ≥ pH, the analysis states that SRD achieves at least a factor-of-2 improvement in sample efficiency.
- Expected Quality: Under stochastic dominance of refinement, SRD has strictly higher expected best-trajectory quality than pure rejection sampling for every sample count n.The quality improvement Δn is positive, while its magnitude decreases with n because both methods increasingly find near-optimal trajectories.
- Correctness Guarantees: SRD terminates after at most n · Nrefine refinement operations and O(n · Nrefine) reward evaluations, while its incumbent best kept reward is weakly non-decreasing.These properties follow from bounded regeneration attempts and the algorithm’s construction.
4 Experiments
Experiments evaluate SRD across four datasets, model combinations, and accuracy–compute settings, showing competitive performance through selective trajectory reuse and refinement. Ablations examine scaling, routing thresholds, refinement policies, and scoring intervals.
- Experimental Settings: SRD is evaluated on MATH500, GPQA Diamond, HotpotQA, and AlpacaEval using task-appropriate generation and reward-model combinations.Metrics span accuracy, exact match, F1, and GPT-4o-mini win rate.
- Main Results: SRD forms a distinct accuracy–compute frontier between Spec-Rej and Best-of-N, achieving comparable or higher accuracy than Spec-Rej when limited additional computation is available.Compute is measured by average generated language-model tokens.
- Main Results: 0.544 accuracy at N=10 uses 2,166 output tokens on MATH500, increasing to 0.640 at N=100 with 21,840 tokens.These levels are reported as comparable to Best-of-N at substantially lower token budgets for the evaluated generation models.
- Main Results: SRD maintains a stable low- and mid-budget accuracy–compute curve on GPQA, while Best-of-N reaches higher accuracy only under large, rapidly growing compute budgets.On HotpotQA, SRD attains performance comparable to Best-of-N with a moderate number of generated tokens.
- Main Results: SRD typically matches Best-of-N win rates at similar or lower generation budgets across all four AlpacaEval model combinations, despite higher evaluation variance.It also substantially outperforms single-sample decoding in this setting.
- Ablations: The default routing thresholds (0.5, 0.3) achieve the best MATH500 accuracy–compute tradeoff, while overly aggressive or permissive thresholds degrade performance.These defaults are used across the main benchmark and model-combination results.
- Ablations: Conservative global rerouting performs best with stable reward feedback, whereas noisier feedback makes global ranking unreliable and aggressive refinement increases token cost without improving accuracy.Across both MATH500 and GPQA, internal Refine-BoN sampling does not improve accuracy.
- Ablations: Moderate scoring intervals provide the most reliable refinement, while very small intervals cause unstable regeneration and very large intervals allow errors to propagate.The interval balances localization precision against reward stability.
5 Conclusion
The conclusion presents SRD as a segment-level alternative to atomic rejection sampling, combining selective suffix regeneration with preserved prefixes. Across four benchmarks, it reports lower-token Best-of-N-level performance and identifies calibration and fixed heuristics as boundaries.
- Conclusion: SRD routes trajectories to keep, refine, or discard and selectively regenerates degraded suffixes while preserving useful prefixes.The method claims a provable (1 + ρ · pM/pH)× sample-efficiency gain over rejection sampling.
- Conclusion: Across four benchmarks, SRD matches Best-of-N accuracy with fewer tokens and outperforms speculative rejection in low-compute regimes.Ablations show refinement effectiveness depends critically on reward-model calibration.
- Conclusion: Fixed routing thresholds and heuristic boundary selection remain key limitations, with end-to-end learning and adaptive reward signals identified as future directions.These scope boundaries are stated as limitations rather than established failure conditions.
Limitations
SRD’s practical scope is constrained by its multi-component design and reliance on reward-model routing. Fixed thresholds and heuristic boundary selection also remain unresolved design choices.
- SRD coordinates a generation model, reward model, and editing mechanism, increasing implementation overhead and inference-time latency in resource-constrained settings.
- SRD’s routing effectiveness depends on the quality of reward-model estimates.Inaccurate or misaligned estimates may produce suboptimal acceptance or salvage decisions.
- SRD currently relies on fixed routing thresholds and heuristic boundary selection.The paper identifies end-to-end policy learning as future work.
Ethical Considerations
SRD can amplify reward-model biases because it regenerates content toward the reward signal rather than merely selecting among existing samples. Its guarantees concern reward-model scores, not task correctness, and noisier rewards can make global rankings worse than local comparisons.
- SRD’s directed regeneration gives reward-model biases more leverage than Best-of-N selection alone.Preferences for length, style, or assertiveness are actively regenerated toward, and repeated refinement can compound the effect.
- SRD’s guarantees apply to reward-model optimization rather than task correctness, so a misaligned reward can entrench confidently wrong trajectories.Weak monotonicity ensures the best scored trajectory does not degrade, but does not imply improved factual accuracy or safety.
- Under a noisier process reward model, trusting global reward rankings is measurably worse than trusting only local comparisons.The paper therefore reports task-level metrics rather than reward scores throughout its experiments.
Impact Statement
SRD is presented as a localized-refinement framework that may reduce redundant computation and improve long-form reasoning, but deployment requires managing latency, reward-signal reliability, and fixed routing heuristics.
- Localized refinement within generated trajectories may reduce redundant computation and improve performance in long-form reasoning tasks.
- Coordinating the generation model, reward model, and editing mechanism may increase implementation complexity and inference-time latency in resource-constrained settings.
- Biases, miscalibration, or misalignment in reward estimates could produce suboptimal refinements, especially in high-stakes or safety-critical applications.
- SRD uses fixed routing thresholds and heuristic boundary selection, while future work may investigate more adaptive or learned routing policies.Broader impacts depend on deployment context and the reliability of the reward signals used.
B Component Breakdown and Runtime Analysis
SRD’s runtime grows moderately with candidate-pool size while component-call counts remain largely stable. Scoring dominates cost, editing is selective, and routing contributes negligible overhead; the supplied appendix passages also outline the supporting probabilistic analysis.
- Runtime trends: As N increases, SRD accuracy improves while runtime grows moderately and component-call counts remain largely stable.The additional cost mainly comes from processing longer trajectories rather than invoking components more frequently.
- Cost distribution: The scorer dominates runtime, followed by the editor, while the router contributes negligible overhead.This profile indicates that reward evaluation and localized rewriting drive SRD’s computational cost.
- Selective editing: The editor is invoked only a small number of times on average, showing that SRD performs selective localized edits rather than rewriting entire trajectories.This behavior helps explain its accuracy–cost trade-off relative to naive Best-of-N.
- Supporting analysis: The appendix proves the theoretical results by interpreting routing probabilities at the population level and establishing auxiliary lemmas before the main theorems.These passages include effective acceptance, stochastic dominance, and order-statistic arguments under stated assumptions.
C.3 Proof of Theorem 3.3 (Sample Efficiency)
The proof compares rejection sampling with SRD by replacing the high-quality acceptance probability pH with SRD’s effective probability peff = pH + ρ · pM, yielding a sample-efficiency improvement. It also establishes that SRD’s refinement process terminates and its kept-set quality is weakly monotone.
- SRD’s effective acceptance probability is at least peff = pH + ρ · pM, whereas pure rejection sampling accepts trajectories with probability pH.
- The efficiency ratio of SRD over rejection sampling is (pH + ρ · pM)/pH, reflecting the additional contribution of salvaged borderline trajectories.
- Rejection sampling is optimal when samples receive only accept-or-reject processing, while SRD is optimal when borderline samples can also be salvaged.
- A coupling argument gives SRD a kept set containing the rejection-sampling accepted set, with regenerated accepted trajectories providing additional candidates.
- The best trajectory under SRD stochastically dominates the rejection-sampling maximum, with strict improvement when regeneration produces an accepted trajectory that exceeds the existing maximum.
- SRD terminates after at most n · Nrefine refinement operations and O(n · Nrefine) reward evaluations, while its kept-set reward is non-decreasing across refinements.
F Empirical Validation of Theorem 3.3
The empirical validation measures routing frequencies and refinement success on MATH500, then compares the observed efficiency gain with Theorem 3.3’s prediction.
- Table 6 reports routing distributions and refinement efficacy on MATH500 using Qwen2.5-Math-1.5B and AceMath-7B-RM, with the gain computed as 1 + ρ̂ · pM/pH.
- The measured refinement efficacy is ρ̂ = 1.0 across all N, indicating that all observed salvage attempts were routed to KEEP.
- The efficiency gain increases from 1.28× to 1.36× as N grows because pM increases slightly while pH remains stable.
- Across N, the routing distribution remains approximately pH ≈ 0.51–0.52, pM ≈ 0.15–0.18, and pL ≈ 0.31–0.33.
G Empirical Validation of Theorem 3.5
Theorem 3.5 is validated by coupling SRD and rejection sampling on identical initial drafts and comparing their maximum achieved rewards across candidate-pool sizes.
- The coupled experiment uses identical seeded initial drafts and continuations, while the rejection baseline omits refinement from the shared incremental generation loop.
- SRD achieves higher mean Rmax than rejection sampling at every tested N, consistent with the theorem’s predicted positive improvement.
- SRD wins more samples than rejection sampling at N=10, N=20, and N=30: 46% vs. 18%, 54% vs. 24%, and 52% vs. 24%, respectively.
- The SRD advantage grows from ∆n = +0.36 at N=10 to +1.29 at N=30 as refined candidates contribute increasingly to Rmax.
- Refinement success rises from 78% to 98% to 100% across the tested pool sizes, while mean reward improves from 3.69 to 6.87 at N=30.