Paper deep dive
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
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 8/29/2026, 4:24:35 AM
Summary
The paper introduces Selective Regenerative Decoding (SRD), an inference-time decoding method for Large Language Models that improves sample efficiency and reasoning quality. Unlike atomic trajectory selection methods like Best-of-N or Speculative Rejection, SRD performs segment-level intervention by routing candidate trajectories to Keep, Refine, or Discard based on reward scores. It preserves high-quality prefixes of borderline candidates and regenerates only degraded suffixes, achieving provable gains in sample efficiency (1.28-1.36x over rejection sampling) and matching Best-of-N accuracy with fewer tokens across benchmarks like MATH500, GPQA Diamond, HotpotQA, and AlpacaEval.
Entities (10)
Relation Signals (8)
Selective Regenerative Decoding → evaluatedon → HotpotQA
confidence 98% · Across MATH500, GPQA Diamond, HotpotQA, and AlpacaEval ... SRD matches Best-of-N accuracy
Selective Regenerative Decoding → evaluatedon → AlpacaEval
confidence 98% · Across MATH500, GPQA Diamond, HotpotQA, and AlpacaEval ... SRD matches Best-of-N accuracy
Selective Regenerative Decoding → evaluatedon → MATH500
confidence 98% · Across MATH500, GPQA Diamond, HotpotQA, and AlpacaEval ... SRD matches Best-of-N accuracy
Selective Regenerative Decoding → evaluatedon → GPQA-Diamond
confidence 98% · Across MATH500, GPQA Diamond, HotpotQA, and AlpacaEval ... SRD matches Best-of-N accuracy
Selective Regenerative Decoding → uses → AceMath-7B-RM
confidence 95% · Reward Model: AceMath-7B-RM
Selective Regenerative Decoding → uses → Llama-3.1-8B-Instruct
confidence 95% · Generation Model: Llama-3.1-8B-Instruct
Selective Regenerative Decoding → matchesaccuracyof → Best-of-N
confidence 92% · SRD matches Best-of-N accuracy with substantially fewer generated tokens
Selective Regenerative Decoding → outperforms → Speculative Rejection
confidence 90% · SRD ... outperforms speculative rejection in low-compute regimes.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.24338v1
- Canonical: https://arxiv.org/abs/2608.24338v1
Trouble viewing inline? Open PDF directly →
Full Text
73,435 characters extracted from source content.
Expand or collapse full text
Selective Regenerative Decoding: Trajectory-Level Intervention for Inference-Time Reasoning We show the sample efficiency of RSD to be lower compared to a speculative version of SRD in . Sophia Xiao Pu †thanks: Work done as a research intern at Amazon. Affiliation: University of California, Santa Barbara Yumo Xu †thanks: Work done while at Amazon. Affiliation: Netflix Sailik Sengupta †thanks: Correspondence: sailiks@amazon.com Affiliation: Amazon Science Millennium Bismay Affiliation: Amazon Science Ruixue Lian22footnotemark: 2 Affiliation: Meta James Gung Affiliation: Amazon Science Yi-an Lai Affiliation: Amazon Science Arshit Gupta Affiliation: Amazon Science Abstract 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 suffix while preserving all the useful prefix of borderline candidates — without requiring a larger target model. Under mild assumptions, SRD achieves a provable 1.281.28–1.36×1.36× sample efficiency gain 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 Best-of-Nτ1 _1✓Selectτ2 _2×Discardτ3 _3×DiscardSpeculative Rejectionτ1 _1✓Acceptτ2 _2×Rejectuseful prefix lostτ3 _3×RejectSRD (Ours)τ1 _1✓Keepτ2 _2✓Refineregeneratedτ3 _3×DiscardHigh qualityDegradedRegeneratedgeneration steps Figure 1: Comparison of decoding strategies on three trajectories (τ1 _1: high quality throughout; τ2 _2: high-quality prefix with degraded suffix; τ3 _3: low quality). Best-of-N fully generates all candidates and selects the best, discarding the rest. Speculative Rejection terminates trajectories when quality drops, saving compute but permanently losing useful prefixes. SRD preserves τ2 _2’s high-quality prefix and selectively regenerates only its degraded suffix (teal), recovering a trajectory that both baselines waste. Allocating additional computation at inference time improves the reasoning quality of large language models Huang et al. (2025); Khanov et al. (2024); Stiennon et al. (2022); Sun et al. (2024); Mudgal et al. (2023); Liao et al. (2025). While ARGS Khanov et al. (2024), and DeAL Huang et al. (2025) formulate decoding as a general reward-guided search procedure, a growing body of work seeks to improve the accuracy and efficiency of the search. Best-of-N Nakano et al. (2021); Stiennon et al. (2022) generates multiple complete trajectories and selects the highest-scoring one; speculative rejection Sun et al. (2024) terminates low-reward prefixes early to reduce cost; Reward-guided Speculative Decoding Liao et al. (2025) uses a reward model to accept or reject draft steps from a smaller model; and Controlled Decoding Mudgal et al. (2023) steers token selection via a learned prefix-aware value function. Despite their differences, these methods treat reasoning trajectories as atomic units. Best-of-N defers all decisions until full trajectories are generated, incurring redundant computation. Speculative rejection makes earlier decisions, but they are irreversible—once a prefix is rejected, any high-quality reasoning it contains is permanently lost. This is particularly wasteful for long-form reasoning, where trajectories frequently contain strong prefixes that degrade only in later steps. A more efficient strategy would preserve what is already good and intervene only where quality drops. We introduce Selective Regenerative Decoding (SRD), a sample-efficient decoding algorithm that enables segment-level intervention within reasoning trajectories (Figure ). SRD operates in three phases: it generates multiple candidates, routes each to Keep, Refine, or Discard based on rank-normalized reward scores, and selectively regenerates only the degraded suffixes of borderline candidates using higher-temperature sampling—without requiring a larger target model. By preserving useful prefixes and rewriting only where quality degrades, SRD recovers computation that rejection-based methods waste. We prove that, under mild assumptions, SRD achieves a provable 1.281.28–1.36×1.36× sample efficiency gain over rejection sampling with strictly higher expected best-trajectory quality with the gain growing as the candidate pool grows—characterized in general by (1+ρ⋅pM/pH)(1+ρ· p_M/p_H)—and satisfies formal termination and weak monotonicity guaranties (§). Empirically, across MATH500 Hendrycks et al. (2021), GPQA Diamond Rein et al. (2024), HotpotQA Yang et al. (2018), and AlpacaEval Li et al. (2023) with multiple generation–reward model combinations, SRD matches Best-of-N accuracy with substantially fewer generated tokens and outperforms speculative rejection in low-compute regimes (§). Ablation studies reveal that the effectiveness of SRD’s refinement depends on reward model calibration: conservative global rerouting excels under stable rewards, while local self-comparison is more robust under noisy signals (§). Because SRD requires only a generative model and a reward model, it is complementary to speculative decoding Leviathan et al. (2023) and prefix value functions Mudgal et al. (2023), which can be composed with it. Our main contributions are: • A three-phase generation–routing–refinement algorithm that enables segment-level intervention in reasoning trajectories without a target model. • Formal proofs that SRD achieves strictly better sample efficiency and expected trajectory quality than rejection sampling, with termination and monotonicity guarantees. • Empirical demonstration that SRD consistently improves the accuracy–compute tradeoff across four benchmarks spanning mathematical reasoning, multi-hop QA, and instruction following, with ablations characterizing when and why refinement helps. 2 Related Work Standard decoding methods, beyond greedy decoding, explore the local neighborhood for every generated token, such as top-k Fan et al. (2018), nucleus sampling Holtzman et al. (2019), temperature-based token-sampling Ackley et al. (1985), or the local neighborhood of a path of decoded tokens, such as beam-search Freitag and Al-Onaizan (2017), contrastive search Su et al. (2022), and Best-of-N Nakano et al. (2021); Stiennon et al. (2022). While exploring a larger search neighborhood may lead to decoding candidates that are more optimal (w.r.t. a particular objective), such non-adaptive policies represent uninformed search strategies guided by the generation model’s priors and language heuristics. When viewed as a search process in the space of tokens, we can impose informed heuristics to better guide generated trajectories Och et al. (2001); Lu et al. (2022); Khanov et al. (2024); Huang et al. (2025). For problems that need reasoning beyond what is well encoded in the language model’s priors, these reward signals can be used during the forward-pass Willard and Louf (2023); Wang et al. (2023), with look-ahead Bertsch et al. (2023); Wan et al. (2023); Huang et al. (2025); Nakshatri et al. (2025), and in exploring search graphs/trees Yao et al. (2023); Roy et al. (2024). Along these lines, our work relates more closely to methods that consider pruning search trajectories from a generated set. For example, speculative rejecting Sun et al. (2024) evaluates top-k beams or candidate paths with a reward model, and discards less promising prefixes early. Unfortunately, its binary rejection strategy can permanently discard promising candidates that have low-rewards at the start. To relax this strict rejection criterion, Reward-Guided Speculative Decoding [RSD; Liao et al. (2025)] performs a relaxed variant of speculative decoding Leviathan et al. (2023), where a draft model proposes a candidate reasoning step and a reward model decides to accept/reject the draft step. If rejected, a larger (and more capable) reasoning model is used to generate the next reasoning step. However, RSD operates on a single search candidate and doesn’t explore multiple search candidate. On the other hand, Controlled Decoding (CD), which introduced an inference-time guidance of policy model’s token selection by using a learned prefix value function in tandem, is an implicit way to influence the local search neighborhood for each token rather than having an explicit rejection mechanism Mudgal et al. (2023). In our work, we first consider generating set of multiple reasoning paths at each reasoning step. Then, an explicit reward model assesses the promise of each candidate in the set, marking them to be either kept, discarded, or refined. When salvaged, the search candidate undergoes localized surgery to allow exploration of the search neighborhood. Thus, we mitigate the lack of look-ahead in existing approaches and explore the search neighborhood without the need for any target/teacher model (used in speculative decoding and RSD) or a prefix value-function (in CD). Note that both of these elements can thereby be used with SRD. 3 Approach We present Selective Regenerative Decoding (SRD), a sample-efficient search algorithm that improves upon standard rejection sampling by introducing a refinement mechanism (without access to a larger target model) for borderline candidates. Unlike rejection sampling, which treats trajectory generation as atomic, our approach recognizes that trajectories are compositional and that many generated trajectories can contain high-quality prefixes but suffer from degradation in later steps. Thus, discarding such trajectories entirely wastes valuable computation. Instead, we propose to salvage these candidates through targeted regeneration. 3.1 Problem Setting Consider a discrete action space A and let =T=A denote the space of trajectories, where each trajectory τ=(a1,a2,…,ak)τ=(a_1,a_2,…,a_k) is a sequence of k discrete actions. We assume access to: ∙ A generative model G that produces trajectories τ∼τ . ∙ A reward model R:→ℝR:T that scores trajectory quality. Our goal is to identify high-quality trajectories efficiently, minimizing the number of samples required to obtain trajectories exceeding a quality threshold, all without access to a target/teacher model. 3.2 Algorithm Overview At each search iteration, SRD operates in three phases: generation, routing, and refinement. Algorithm provides the complete procedure. Phase 1: Generation. We sample n candidate trajectories independently from the generative model: =τ1,τ2,…,τn,τi∼.C=\ _1, _2,…, _n\, _i . (1) Phase 2: Routing. Each candidate is evaluated using the reward model and assigned a normalized score based on its relative rank. Specifically, we sort candidates by their reward scores in descending order and assign each trajectory a rank r∈0,1,…,n−1r∈\0,1,…,n-1\, where r=0r=0 denotes the highest-scoring candidate. We then compute a normalized score: u(τ)=1−r(τ)n−1,u(τ)=1- r(τ)n-1, (2) yielding u∈[0,1]u∈[0,1] with larger values indicating better relative quality. Then, routing decisions are determined by comparing u(τ)u(τ) against two thresholds, θlow _low and θhigh _high, where 0≤θlow<θhigh≤10≤ _low< _high≤ 1: Route(τ)=Keep,u(τ)≥θhigh,Refine,θlow<u(τ)<θhigh,Discard,u(τ)≤θlow. Route(τ)= casesKeep,&u(τ)≥ _high,\\ Refine,& _low<u(τ)< _high,\\ Discard,&u(τ)≤ _low. cases (3) Phase 3: Regeneration. Trajectories routed to Refine undergo a targeted regeneration procedure. For each such trajectory τ, we identify a regeneration boundary by evaluating reward scores at fixed intervals of m<km<k steps and selecting the earliest position j at which reward degrades relative to the preceding prefix: j=minj∈m,2m,…:R(τ1:j+m)<R(τ1:j)j= \j∈\m,2m,…\:\\ R( _1:j+m)<R( _1:j) \ (4) We then regenerate the suffix τj+1:k _j+1:k using a higher-temperature sampling strategy, updating the trajectory: τ τ =(τ1:j,τ~j+1:k), =( _1:j, τ_j+1:k), (5) τ~j+1:k τ_j+1:k ∼high−temp(⋅∣τ1:j). _high-temp(· _1:j). The refined trajectory τ is then re-evaluated and ranked jointly with other active candidates. It is retained only if subsequently routed to Keep; otherwise, it is discarded. Termination Guarantees. To ensure termination, we impose two constraints: (i) a maximum regeneration span length LmaxL_ , and (i) a maximum number of refinement attempts per trajectory NrefineN_refine. These bounds guarantee that the algorithm terminates in at most n⋅Nrefinen· N_refine refinement operations. Algorithm 1 Selective Regenerative Decoding 1: Generative model G, reward model R, sample size n, thresholds θlow,θhigh _low, _high, scoring interval m, max refinements NrefineN_refine, max span LmaxL_ 2: Set of accepted trajectories K 3: ←τi∼i=1C←\ _i \_i=1 ⊳ Generate candidates 4: ←∅K← , ℛ←∅R← ⊳ Initialize kept and refine sets 5: for τ∈τ do 6: Compute u(τ)u(τ) based on rank in C 7: if u(τ)≥θhighu(τ)≥ _high then 8: ←∪τK ∪\τ\ 9: else if u(τ)>θlowu(τ)> _low then 10: ℛ←ℛ∪(τ,0)R ∪\(τ,0)\ ⊳ Add with refinement count 0 11: end if 12: end for 13: while ℛ≠∅R≠ do 14: (τ,c)←Pop(ℛ)(τ,c)← Pop(R) 15: if c≥Nrefinec≥ N_refine then 16: continue ⊳ Max refinements reached 17: end if 18: j←FindBoundary(τ,R,m)j← FindBoundary(τ,R,m) 19: if k−j>Lmaxk-j>L_ then 20: j←k−Lmaxj← k-L_ ⊳ Limit regeneration span 21: end if 22: τ←(τ1:j,τ~j+1:k)τ←( _1:j, τ_j+1:k) where τ~j+1:k∼high−temp(⋅∣τ1:j) τ_j+1:k _high-temp(· _1:j) 23: Compute u(τ)u(τ) based on rank in ∪ℛ∪τK ∪\τ\ 24: if u(τ)≥θhighu(τ)≥ _high then 25: ←∪τK ∪\τ\ 26: else if u(τ)>θlowu(τ)> _low then 27: ℛ←ℛ∪(τ,c+1)R ∪\(τ,c+1)\ 28: end if 29: end while 30: return K 3.3 Theoretical Analysis We establish two main results: SRD has (i) improved sample efficiency compared to rejection sampling, and (i) higher expected solution quality. We begin by introducing the necessary notation and assumptions. Notation and Assumptions Let the generative distribution G induce the following partition of probability mass: pH p_H =IPτ∼[u(τ)≥θhigh], =I -1.49994ptP_τ [u(τ)≥ _high ], (6) pM p_M =IPτ∼[θlow<u(τ)<θhigh], =I -1.49994ptP_τ [ _low<u(τ)< _high ], (7) pL p_L =IPτ∼[u(τ)≤θlow], =I -1.49994ptP_τ [u(τ)≤ _low ], (8) where pH+pM+pL=1p_H+p_M+p_L=1. These are population-level quantities; the rank-based score u(τ)u(τ) is a consistent finite-sample estimator of them Appendix- . Assumption 3.1 (Refinement Efficacy). There exists a constant ρ∈(0,1]ρ∈(0,1] such that for any trajectory τ with θlow<u(τ)<θhigh _low<u(τ)< _high, the refinement procedure produces an acceptable trajectory with probability at least ρ: IP[Route(Refine(τ))=Keep]≥ρ.I -1.49994ptP [ Route( Refine(τ))= Keep ]≥ρ. (9) This assumption captures the intuition that refinement is beneficial, i.e. trajectories in the middle tier have salvageable prefixes, and regenerating their suffixes with increased diversity yields acceptable results with non-negligible probability. Results in support this empirically. Assumption 3.2 (Independence). Refinement outcomes are independent across trajectories, and each refinement attempt is independent of previous attempts on the same trajectory. Sample Efficiency Our first result establishes SRD requires fewer samples than pure rejection sampling to obtain at least one acceptable trajectory with high probability. Theorem 3.3 (Sample Efficiency). Let δ∈(0,1)δ∈(0,1) be a failure probability. Under Assumptions and , (i) pure rejection sampling requires at least Nreject≥ln(1/δ)pHN_reject≥ (1/δ)p_H samples to obtain at least one acceptable trajectory with probability ≥1−δ≥ 1-δ. In comparison, (i) SRD requires at least NSRD≥ln(1/δ)pH+ρ⋅pMN_SRD≥ (1/δ)p_H+ρ· p_M samples to achieve the same guarantee. Thus, (i) the efficiency gain of SRD over rejection sampling is characterized by: NrejectNrefine=1+ρ⋅pMpH. N_rejectN_refine=1+ ρ· p_Mp_H. (10) The complete proof is provided in Appendix and emperical evidence is provided in Appendix . We note that the efficiency gain is most pronounced when pHp_H is small (high-quality trajectories are rare) and pM⋅ρp_M·ρ is substantial (many refinable trajectories exist and refinement is effective). In the regime where ρ⋅pM≥pHρ· p_M≥ p_H, SRD achieves at least a factor of 2 improvement in sample efficiency. Expected Quality Improvement Beyond sample efficiency, SRD also improves the expected quality of the best trajectory found. Assumption 3.4 (Stochastic Dominance of Refinement). For trajectories in the refinable region, the refinement operation produces outputs whose reward distribution stochastically dominates that of fresh samples from the same region: R(Refine(τ))⪰stR(τ)for τ,τ R( Refine(τ)) _stR(τ) τ,τ (11) with θlow<u(τ),u(τ)<θhigh with _low<u(τ),u(τ)< _high where ⪰st _st denotes first-order stochastic dominance. This holds naturally given a larger target model for regeneration, and is motivated here by refinement preserving high-quality prefixes while regenerating problematic suffixes with increased diversity. Theorem 3.5 (Expected Quality Improvement). Let Rmax(n)=maxi∈[n]R(τi)R_ (n)= _i∈[n]R( _i) denote the best reward from n samples under pure rejection sampling, and let Rmax(n)R_ (n) denote the best reward from SRD. Under Assumptions –: [Rmax(n)]≥[Rmax(n)]+Δn,E [R_ (n) ] [R_ (n) ]+ _n, (12) where Δn>0 _n>0 for all n≥1n≥ 1.Moreover, under mild regularity conditions on the reward distribution, the improvement satisfies: Δn=Ω(pM⋅ρn⋅(1+pM⋅ρ)). _n= ( p_M·ρn·(1+p_M·ρ) ). (13) While the complete proof appears in Appendix , we highlight that the improvement Δn _n decreases with n, which may seem counterintuitive. This reflects the diminishing marginal returns of additional candidates, i.e. as n grows, both algorithms are increasingly likely to find near-optimal trajectories, so the gap between them shrinks. Emperical proof has been provided in Appendix . Finally, SRD satisfies two correctness properties that follow directly from the algorithm construction: it terminates in at most n⋅Nrefinen· N_refine refinement operations and O(n⋅Nrefine)O(n· N_refine) reward evaluations, and it is weakly monotone — the best kept reward RtR_t is non-decreasing in the number of refinement operations t, so refinement never degrades the incumbent solution. Formal statements and proofs are in (Propositions and ). 4 Experiments 4.1 Experimental Settings Tasks and Metrics. We evaluate on four datasets spanning reasoning and instruction-following: MATH500 Hendrycks et al. (2021) (mathematical reasoning, accuracy), GPQA Diamond Rein et al. (2024) (scientific QA, accuracy following Liao et al. (2025)), HotpotQA Yang et al. (2018) (multi-hop QA, EM and F1), and AlpacaEval Li et al. (2023) (instruction following, GPT-4o-mini win rate following Sun et al. (2024)). Generation and Reward Models. We pair task-appropriate generation and reward models, using the ten combinations listed in . Reward models are matched to task type: math- and reasoning-specific models for MATH500 and GPQA, a retrieval-augmented QA model for HotpotQA, and general-purpose preference models for AlpacaEval. We intentionally decouple generation and reward models throughout, so the evaluation signal is external rather than biased toward the generator’s own preferences Panickssery et al. (2024). The same generation model serves as both drafter and editor. Prompt templates are in Appendix . Generation Model Reward Model MATH500 Llama-3.1-8B-Instruct AceMath-7B-RM Qwen2.5-Math-1.5B-Instruct AceMath-7B-RM GPQA DIAMOND Llama-3.1-8B-Instruct Skywork-o1-Open-PRM-7B Qwen3-4B-Instruct Skywork-o1-Open-PRM-7B AlpacaEval Llama-3.1-8B-Instruct FsfairX-LLaMA3-RM-v0.1 Llama-3.1-8B-Instruct RM-Mistral-7B Qwen3-4B-Instruct FsfairX-LLaMA3-RM-v0.1 Qwen3-4B-Instruct RM-Mistral-7B HotpotQA Llama-3.1-8B-Instruct Llama3.1-RAG-Reward-v2 Table 1: Generation and reward model combinations used for each dataset. Baselines. We compare against three inference-time decoding baselines, all sharing SRD’s generation model, prompt template, and sampling hyperparameters and differing only in decoding strategy: Temperature Sampling (N=1N=1, a single trajectory); Best-of-N (BoN), which fully generates N candidates and selects the highest-reward one; and Speculative Rejection (Spec-Rej) Sun et al. (2024), which scores prefixes during generation and permanently terminates low-reward trajectories. Full baseline descriptions are in Appendix . We exclude Reward-guided Speculative Decoding Liao et al. (2025) from the main comparison because it assumes access to a larger target model for regeneration, whereas SRD and all baselines above operate with only a single generative model and a reward model. We provide a controlled comparison with a speculative variant of SRD under RSD’s setting in . 4.2 Main results Figure 2: Accuracy-compute trade-offs of inference-time decoding methods across four benchmarks and multiple generation-reward model combinations. Compute is measured by the average number of generated tokens from the language model. SRD consistently achieves competitive performance with respect to Best-of-N and Speculative Rejection under lower or comparable generation budgets by selectively reusing and refining partial trajectories. N Acc. Time (s) In Tok. Out Tok. Drafter (time/calls) Scorer (time/calls) Editor (time/calls) Router (time/calls) 10 0.544 7.21 6629 2166 4.73 / 4.1 1.29 / 5.6 1.18 / 1.0 <0.01 / 3.8 50 0.611 18.07 32895 10927 7.43 / 4.2 6.98 / 6.6 3.59 / 2.2 <0.01 / 5.3 100 0.640 29.76 65737 21840 10.96 / 4.2 13.53 / 6.7 5.13 / 2.3 <0.01 / 5.5 Table 2: Component-level breakdown of SRD on MATH500 under different values of N. We report overall accuracy, runtime, token statistics, and per-component time and call frequency in the format of time / calls. We evaluate Selective Regenerative Decoding (SRD) on four benchmarks and compare it with several inference-time decoding baselines under an accuracy–compute tradeoff setting. Throughout this section, we report task-level evaluation metrics (e.g., accuracy, F1, or win rate), rather than reward scores. All decoding hyperparameters and implementation details are provided in Appendix . Overall Trends. As shown in Figure , SRD consistently forms a distinct tradeoff frontier between the early rejection method (Spec-Rej) and full trajectory sampling (Best-of-N). In particular, SRD achieves accuracy levels comparable to or exceeding Spec-Rej when limited additional computation is permitted. Rather than operating at a single fixed point, SRD explores a different region of the accuracy–compute tradeoff by enabling segment-level intervention within a single trajectory. This allows computation to be allocated conditionally, based on intermediate trajectory quality, rather than uniformly across complete candidates. This trend is particularly evident on reasoning-centric tasks such as MATH500, GPQA, and HotpotQA, where intermediate reasoning errors are common and suggest opportunities for partial trajectory correction. Mathematical and Reasoning Tasks. On MATH500 with LLaMA-3.1-8B, SRD achieves 0.544 accuracy at N=10N=10 using only 2,166 output tokens, scaling to 0.640 at N=100N=100 with 21,840 tokens (Table ). As shown in Figure , these accuracy levels are comparable to Best-of-N at substantially lower token budgets for both Qwen2.5-Math-1.5B and LLaMA-3.1-8B. While Best-of-N can further improve accuracy by sampling more complete candidates, this comes at the cost of proportionally increased token generation. On the more challenging GPQA benchmark, overall accuracy is lower across all methods, reflecting task difficulty. SRD exhibits a more stable accuracy–compute curve in the low- and mid-budget regimes. Although Best-of-N can achieve higher accuracy under large budgets, its compute cost grows rapidly, indicating diminishing returns from purely increasing candidate diversity. Multi-hop Question Answering. On HotpotQA, SRD attains performance comparable to Best-of-N using a moderate number of generated tokens. Given that HotpotQA requires multi-step reasoning over multiple pieces of evidence, this result suggests that selectively refining partial trajectories can effectively reduce redundant generation of entire reasoning chains. Instruction-following Evaluation. On AlpacaEval, evaluation is based on preference comparisons and therefore exhibits higher variance. Despite this, SRD demonstrates a consistent accuracy–compute trend across all four generation–reward model combinations tested (Table ). At similar or lower generation budgets, SRD typically achieves win rates comparable to Best-of-N and substantially outperforms single-sample decoding, indicating that SRD remains effective even under noisier reward signals. 4.3 Empirical Validation of Theoretical Quantities To directly validate the quantities in Theorem , we measure the routing distribution and refinement success rate on MATH500 with Qwen2.5-Math-1.5B-Instruct (N=10N=10). The accuracy–compute tradeoffs in Figure and the scaling behavior in Table (0.544 at N=10N=10 to 0.640 at N=100N=100) provide indirect support for sample efficiency, but do not directly measure ρ, pHp_H, or pMp_M; we address this gap here. We observe pH=0.525p_H=0.525, pM=0.148p_M=0.148, and pL=0.324p_L=0.324, with a refinement efficacy of ρ^=1.0 ρ=1.0 (all refinement attempts yielded trajectories routed to Keep). Substituting into the efficiency gain formula from Theorem gives 1+ρ^⋅pM/pH=1.281+ ρ· p_M/p_H=1.28, indicating that SRD requires approximately 22% fewer samples than pure rejection sampling to achieve the same success guarantee. These results are consistent across N: at N=20N=20 and N=30N=30, we observe ρ^=1.0 ρ=1.0 with efficiency gains of 1.35×1.35× and 1.36×1.36× respectively, as larger candidate pools produce more mid-tier trajectories amenable to refinement. Extended results across values of N are provided in Appendix . We additionally validate Theorem by comparing RmaxR_ between SRD and rejection sampling under a coupled setting where both methods start from identical initial drafts (via seeded generation). SRD achieves higher mean RmaxR_ than RS at both N=10N=10 (Δn=+0.36 _n=+0.36) and N=20N=20 (Δn=+0.28 _n=+0.28), with SRD winning more samples in both cases (23 vs. 9 and 27 vs. 12, respectively). Refinement success rates range from 78–100%, confirming Assumption . Notably, the SRD advantage grows with N (Δn=+1.29 _n=+1.29 at N=30N=30), as larger candidate pools produce more mid-tier trajectories amenable to refinement. Full details are provided in Appendix . 4.4 Ablation Studies 4.4.1 Effect of Routing Thresholds We analyze the effect of routing thresholds (θhigh,θlow)( _high, _low) on SRD using MATH500 with Llama-3.1-8B-Instruct (N=10N=10), while keeping all other settings fixed. Table reports representative threshold configurations. Performance degrades when the thresholds are overly aggressive or overly permissive, while the default setting (0.5,0.3)(0.5,0.3) achieves the best accuracy-compute tradeoff. We use these defaults across all benchmarks and model combinations in the main results (Figure ), which provides implicit cross-task validation of this choice. θhigh _high θlow _low Accuracy Out Tokens 0.5 0.3 0.5444 2166 0.5 0.5 0.5400 1973 0.5 0.2 0.5267 2325 0.8 0.5 0.4667 1871 0.7 0.3 0.4467 2091 Table 3: Effect of routing thresholds on MATH500 (Llama-3.1-8B-Instruct, N=10N=10). 4.4.2 Effect of Refinement Policies We investigate how different refinement policies—the decision rule applied after regenerating a candidate routed to Refine—affect SRD’s behavior. We vary only the refinement policy and fix all other settings. Refinement Policy Variants. After a candidate routed to Refine undergoes suffix regeneration (Phase 3 in §), a policy determines whether the refined candidate is retained. We consider five policies: Reroute (global) (default) ranks the refined candidate jointly with all active candidates and retains it only if it is routed to Keep. Keep on refine follows the same rerouting procedure but also retains candidates that remain in the Refine tier. Self-compare compares the refined candidate’s reward against its pre-refinement reward, retaining it if R(τ)≥R(τ)+δR(τ)≥ R(τ)+δ, where δ is a fixed margin (δ=0.02δ=0.02 in this study). Force keep unconditionally retains all refined candidates. Refine-BoN performs N parallel regenerations for each refined candidate and retains the highest-reward result (N∈3,5,10N∈\3,5,10\). Refinement Policy Accuracy Out Tokens Dataset: MATH500 Reroute (global) 0.5444 2166 Keep on refine 0.5333 2149 Force keep 0.5267 2162 Refine-Bo3 0.5222 2521 Refine-Bo10 0.5244 3819 Self-compare 0.5156 2175 Refine-Bo5 0.4906 2238 Dataset: GPQA Self-compare 0.3243 2201 Refine-Bo10 0.3176 4030 Force keep 0.3041 2212 Reroute (global) 0.2973 2214 Refine-Bo5 0.2635 2185 Refine-Bo3 0.2635 2618 Keep on refine 0.2635 2185 Table 4: Effect of different refinement policies on representative reasoning tasks (N=10N=10). Scoring Interval Accuracy Out Tokens Dataset: MATH500 1 0.5533 2389 5 0.5422 2383 10 0.5667 2387 20 0.5556 2388 50 0.5689 2387 100 0.5467 2390 Dataset: GPQA 1 0.2365 2208 5 0.2973 2189 10 0.2973 2214 20 0.2500 2191 50 0.2432 2209 100 0.2365 2218 Table 5: Ablation on scoring interval (localization granularity), which determines where SRD begins suffix regeneration within a trajectory routed to Refine. Results. Table reports results on MATH500 and GPQA. We use Llama-3.1-8B-Instruct as the generation model; for reward models, we use AceMath-7B-RM on MATH500 and Skywork-o1-Open-PRM on GPQA. On MATH500, where the reward model provides relatively stable and well-calibrated feedback, the conservative Reroute (global) strategy achieves the highest accuracy while maintaining low generation cost. More permissive strategies and aggressive refinement variants with internal Best-of-N substantially increase generation without improving accuracy. In contrast, on GPQA, which relies on a noisier process reward model, the locally grounded Self-compare strategy achieves the best performance while using fewer generated tokens. Global rerouting-based strategies perform significantly worse, suggesting that global candidate ranking is less reliable under noisy reward signals. Notably, across both regimes, increasing refinement aggressiveness or internal sampling (Refine-BoN) does not improve accuracy and often increases token cost substantially. 4.4.3 Effect of Scoring Interval Mechanism. The scoring interval controls the granularity at which SRD localizes the regeneration boundary j within a trajectory routed to Refine (see Phase 3 in §). Smaller intervals enable finer-grained localization but are more sensitive to local reward fluctuations; larger intervals are more stable but may delay detection of the degradation point. Observation. Across both GPQA and MATH500, as shown in Table , extremely small intervals lead to unstable or premature regeneration, while overly large intervals allow errors to propagate before being detected. A moderate interval consistently yields the most reliable refinement, suggesting a favorable balance between localization precision and reward stability. 5 Conclusion We introduced Selective Regenerative Decoding (SRD), which routes candidate trajectories to keep, refine, or discard and selectively regenerates only degraded suffixes while preserving useful prefixes—achieving a provable (1+ρ⋅pM/pH)×(1+ρ· p_M/p_H)× sample efficiency gain over rejection sampling. Across four benchmarks, SRD consistently matches Best-of-N accuracy with fewer tokens and outperforms speculative rejection in low-compute regimes, with ablations showing that refinement effectiveness depends critically on reward model calibration. Key limitations include reliance on fixed routing thresholds and heuristic boundary selection; learning these end-to-end, as well as extending SRD to settings with adaptive or learned reward signals, are promising directions for future work. Limitations SRD requires coordinating multiple components, including a generation model, a reward model, and an editing mechanism, which may increase implementation overhead and inference-time latency in resource-constrained settings. Moreover, the effectiveness of SRD depends on the quality of the reward model used for routing. Inaccurate or misaligned reward estimates may lead to suboptimal acceptance or salvage decisions. SRD currently relies on fixed routing thresholds and heuristic boundary selection. Learning these policies end-to-end is an interesting direction for future work. Ethical Considerations Directed regeneration and bias amplification. Unlike Best-of-N, which only selects among samples the model would have produced anyway, SRD rewrites content to raise reward. This gives reward model biases more leverage: systematic preferences over length, style, or assertiveness are actively regenerated toward rather than merely selected for, and repeated refinement can compound the effect. We caution against deploying SRD with a reward model that has not been audited on the target distribution. Reward models as the optimization target. SRD’s guarantees are stated with respect to the reward model R, not task correctness: weak monotonicity (Proposition ) ensures the best scored trajectory never degrades, which does not imply improved factual accuracy or safety. When R is misaligned with the intended objective, SRD faithfully optimizes the proxy, and the mechanism that recovers a correct suffix can equally entrench a confidently wrong one that the reward model happens to favor. Our GPQA results show this concretely: under a noisier process reward model, trusting global reward rankings is measurably worse than trusting only local comparisons (§). We therefore report task-level metrics rather than reward scores throughout §. Impact Statement This paper presents Selective Regenerative Decoding (SRD), an inference-time decoding framework aimed at improving the efficiency and reliability of large language model reasoning. By enabling localized refinement within generated trajectories, SRD may help reduce redundant computation and improve performance in long-form reasoning tasks. However, SRD requires coordinating multiple components, including a generation model, a reward model, and an editing mechanism, which may increase implementation complexity and inference-time latency in resource-constrained settings. Moreover, SRD relies on reward model feedback for routing decisions. Biases, miscalibration, or misalignment in reward estimates could lead to suboptimal refinements, which is particularly important to consider in high-stakes or safety-critical applications. SRD currently uses fixed routing thresholds and heuristic boundary selection, and future work may explore more adaptive or learned routing policies. Overall, this work is intended as a general decoding-time contribution, and its broader impacts will depend on the downstream deployment context and the reliability of the reward signals used. References Ackley et al. (1985) D. H. Ackley, G. E. Hinton, and T. J. Sejnowski A learning algorithm for boltzmann machines. Cognitive science 9 (1), p. 147–169. Cited by: §2. Bertsch et al. (2023) A. Bertsch, A. Xie, G. Neubig, and M. R. Gormley It’s mbr all the way down: modern generation techniques through the lens of minimum bayes risk. arXiv preprint arXiv:2310.01387. Cited by: §2. Cover (1999) T. M. Cover Elements of information theory. John Wiley & Sons. Cited by: Remark C.6. David and Nagaraja (2004) H. A. David and H. N. Nagaraja Order statistics. John Wiley & Sons. Cited by: §C.2. Fan et al. (2018) A. Fan, M. Lewis, and Y. Dauphin Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), I. Gurevych and Y. Miyao (Eds.), Melbourne, Australia, p. 889–898. External Links: Link, Document Cited by: §2. Freitag and Al-Onaizan (2017) M. Freitag and Y. Al-Onaizan Beam search strategies for neural machine translation. In Proceedings of the First Workshop on Neural Machine Translation, T. Luong, A. Birch, G. Neubig, and A. Finch (Eds.), Vancouver, p. 56–60. External Links: Link, Document Cited by: §2. Hendrycks et al. (2021) D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt Measuring mathematical problem solving with the math dataset. NeurIPS. Cited by: §1, §4.1. Holtzman et al. (2019) A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi The curious case of neural text degeneration. arXiv preprint arXiv:1904.09751. Cited by: §2. Huang et al. (2025) J. Y. Huang, S. Sengupta, D. Bonadiman, Y. Lai, A. Gupta, N. Pappas, S. Mansour, K. Kirchhoff, and D. Roth DeAL: decoding-time alignment for large language models. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), W. Che, J. Nabende, E. Shutova, and M. T. Pilehvar (Eds.), Vienna, Austria, p. 26280–26300. External Links: Link, Document, ISBN 979-8-89176-251-0 Cited by: §1, §2. Khanov et al. (2024) M. Khanov, J. Burapacheep, and Y. Li ARGS: alignment as reward-guided search. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1, §2. Leviathan et al. (2023) Y. Leviathan, M. Kalman, and Y. Matias Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, p. 19274–19286. Cited by: §1, §2. Li et al. (2023) X. Li, T. Zhang, Y. Dubois, R. Taori, I. Gulrajani, C. Guestrin, P. Liang, and T. B. Hashimoto AlpacaEval: an automatic evaluator of instruction-following models. GitHub. Note: https://github.com/tatsu-lab/alpaca_eval Cited by: §1, §4.1. Liao et al. (2025) B. Liao, Y. Xu, H. Dong, J. Li, C. Monz, S. Savarese, D. Sahoo, and C. Xiong Reward-guided speculative decoding for efficient LLM reasoning. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §C.3, §1, §2, §4.1, §4.1. Lu et al. (2022) X. Lu, S. Welleck, P. West, L. Jiang, J. Kasai, D. Khashabi, R. Le Bras, L. Qin, Y. Yu, R. Zellers, et al. Neurologic a* esque decoding: constrained text generation with lookahead heuristics. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, p. 780–799. Cited by: §2. Mudgal et al. (2023) S. Mudgal, J. Lee, H. Ganapathy, Y. Li, T. Wang, Y. Huang, Z. Chen, H. Cheng, M. Collins, J. Chen, A. Beutel, and A. Beirami Controlled decoding from language models. In Socially Responsible Language Modelling Research, External Links: Link Cited by: §1, §1, §2. Nakano et al. (2021) R. Nakano, J. Hilton, S. Balaji, J. Wu, O. Long, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders, X. Jiang, K. Cobbe, T. Eloundou, G. Krueger, K. Button, M. Knight, B. Chess, and J. Schulman WebGPT: browser-assisted question-answering with human feedback. ArXiv abs/2112.09332. External Links: Link Cited by: §1, §2. Nakshatri et al. (2025) N. S. Nakshatri, S. Roy, R. Das, S. Chaidaroon, L. Boytsov, and R. Gangadharaiah Constrained decoding with speculative lookaheads. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), p. 4681–4700. Cited by: §2. Och et al. (2001) F. J. Och, N. Ueffing, and H. Ney An efficient a* search algorithm for statistical machine translation. In Proceedings of the ACL 2001 Workshop on Data-Driven Methods in Machine Translation, Cited by: §2. Panickssery et al. (2024) A. Panickssery, S. Bowman, and S. Feng Llm evaluators recognize and favor their own generations. Advances in Neural Information Processing Systems 37, p. 68772–68802. Cited by: §4.1. Rein et al. (2024) D. Rein, B. L. Hou, A. C. Stickland, J. Petty, R. Y. Pang, J. Dirani, J. Michael, and S. R. Bowman Gpqa: a graduate-level google-proof q&a benchmark. In First Conference on Language Modeling, Cited by: §1, §4.1. Rényi (1953) A. Rényi On the theory of order statistics. Acta Math. Acad. Sci. Hung. Cited by: §C.2. Roy et al. (2024) S. Roy, S. Sengupta, D. Bonadiman, S. Mansour, and A. Gupta FLAP: flow-adhering planning with constrained decoding in LLMs. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), K. Duh, H. Gomez, and S. Bethard (Eds.), Mexico City, Mexico, p. 517–539. External Links: Link, Document Cited by: §2. Stiennon et al. (2022) N. Stiennon, L. Ouyang, J. Wu, D. M. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. Christiano Learning to summarize from human feedback. External Links: 2009.01325, Link Cited by: §1, §2. Su et al. (2022) Y. Su, T. Lan, Y. Wang, D. Yogatama, L. Kong, and N. Collier A contrastive framework for neural text generation. Advances in Neural Information Processing Systems 35, p. 21548–21561. Cited by: §2. Sun et al. (2024) H. Sun, M. Haider, R. Zhang, H. Yang, J. Qiu, M. Yin, M. Wang, P. Bartlett, and A. Zanette Fast best-of-n decoding via speculative rejection. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, External Links: Link Cited by: §1, §2, §4.1, §4.1. Wan et al. (2023) D. Wan, M. Liu, K. McKeown, M. Dreyer, and M. Bansal Faithfulness-aware decoding strategies for abstractive summarization. arXiv preprint arXiv:2303.03278. Cited by: §2. Wang et al. (2023) S. Wang, S. Jean, S. Sengupta, J. Gung, N. Pappas, and Y. Zhang Measuring and mitigating constraint violations of in-context learning for utterance-to-api semantic parsing. arXiv preprint arXiv:2305.15338. Cited by: §2. Willard and Louf (2023) B. T. Willard and R. Louf Efficient guided generation for large language models. arXiv preprint arXiv:2307.09702. Cited by: §2. Yang et al. (2018) Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. W. Cohen, R. Salakhutdinov, and C. D. Manning HotpotQA: a dataset for diverse, explainable multi-hop question answering. In Conference on Empirical Methods in Natural Language Processing (EMNLP), Cited by: §1, §4.1. Yao et al. (2023) S. Yao, D. Yu, J. Zhao, I. Shafran, T. Griffiths, Y. Cao, and K. Narasimhan Tree of thoughts: deliberate problem solving with large language models. Advances in neural information processing systems 36, p. 11809–11822. Cited by: §2. Appendix A Experimental Settings (Extended) This appendix expands the experimental settings summarized in §. A.1 Baseline Descriptions To ensure a fair comparison, unless otherwise specified, all methods share the same generation model, prompt template, and sampling hyperparameters (e.g., temperature), and differ only in their decoding and selection strategies. Temperature Sampling (N=1N=1). This baseline generates a single trajectory under a fixed temperature setting and serves as the simplest sampling-based baseline. When the temperature is set to 0, this method reduces to strictly greedy decoding. In our experiments, we use the same non-zero temperature as other methods to ensure comparability. Best-of-N (BoN). Best-of-N independently generates N full-length candidate sequences and selects the one with the highest reward score. While this approach increases candidate diversity and often improves final output quality, it incurs substantial generation cost, as all N candidates must be fully generated before selection. Speculative Rejection (Spec-Rej). Speculative Rejection evaluates candidate prefixes during generation using a reward model and terminates low-reward trajectories early, thereby reducing generation cost compared to Best-of-N. This method adopts a binary accept-or-reject strategy: once a trajectory is rejected, it is permanently discarded and no longer extended. Appendix B Component Breakdown and Runtime Analysis To better understand the computational characteristics of SRD, we provide a component-level breakdown on MATH500 under different values of N (Table ). We report task performance, runtime, and per-component time and call frequency. The four components correspond to the phases in §: the drafter is the generative model G that produces candidate trajectories (Phase 1); the scorer is the reward model R used for both routing decisions and regeneration boundary detection (Phases 2–3); the router applies the threshold-based routing logic (Phase 2); and the editor performs suffix regeneration for candidates routed to Refine (Phase 3). Overall trends. As N increases, accuracy consistently improves, while the overall runtime grows moderately. Importantly, the number of component calls remains largely stable across different N, indicating that SRD does not incur additional structural overhead as candidate exploration increases. Instead, the increased cost mainly comes from processing longer trajectories rather than invoking components more frequently. Cost distribution across components. The runtime is dominated by the scorer, followed by the editor, while the router contributes negligible overhead. This suggests that SRD’s computational cost is primarily driven by reward evaluation and localized rewriting, whereas routing decisions themselves are lightweight. Such a cost profile is desirable in practice, as it enables selective intervention without introducing expensive control logic. Selective editing behavior. Even with larger N, the editor is invoked only a small number of times on average, demonstrating that SRD performs localized edits selectively rather than rewriting entire trajectories. This behavior distinguishes SRD from naive Best-of-N approaches and helps explain its favorable accuracy–cost trade-off. Appendix C Proofs This appendix provides complete proofs for all theoretical results presented in Section . We begin by clarifying the population-level interpretation of the routing probabilities, then establish several auxiliary lemmas before proving the main theorems. C.1 Population-Level Interpretation of pHp_H, pMp_M, pLp_L Remark C.1. The quantities pHp_H, pMp_M, and pLp_L defined in Equations (6)–(8) should be interpreted as probabilities under the population distribution – i.e., the probability that the reward model’s score for a random trajectory from G, when compared against the population of all possible outputs, falls in each tier. The algorithm’s rank-based scoring u(τ)=1−r(τ)/(n−1)u(τ)=1-r(τ)/(n-1) is a finite-sample approximation to this population quantity. For large n, the empirical rank converges to the population quantile by the Glivenko-Cantelli theorem. The theoretical analysis operates in the population limit; the algorithm provides a consistent estimator. C.2 Preliminary Lemmas Lemma C.2 (Geometric Failure Probability). Let X1,X2,…,XNX_1,X_2,…,X_N be independent Bernoulli random variables with Pr[Xi=1]=p [X_i=1]=p for some p∈(0,1)p∈(0,1). Then: Pr[∑i=1Xi=0]=(1−p). [ _i=1X_i=0 ]=(1-p). (14) Furthermore, to ensure Pr[∑i=1Xi≥1]≥1−δ [ _i=1X_i≥ 1]≥ 1-δ for some δ∈(0,1)δ∈(0,1), it is necessary and sufficient that: N N ≥ln(1/δ)−ln(1−p) ≥ (1/δ)- (1-p) (15) ≥ln(1/δ)p. ≥ (1/δ)p. Proof. The first claim follows directly from independence: Pr[∑i=1Xi=0]=∏i=1Pr[Xi=0]=∏i=1(1−p)=(1−p). [ _i=1X_i=0 ]= _i=1 [X_i=0]= _i=1(1-p)=(1-p). For the second claim, we require (1−p)≤δ(1-p)≤δ. Taking logarithms: Nln(1−p)≤ln(δ),N (1-p)≤ (δ), and since ln(1−p)<0 (1-p)<0 for p∈(0,1)p∈(0,1): N≥ln(1/δ)−ln(1−p)N≥ (1/δ)- (1-p) Inequality −ln(1−p)≤p- (1-p)≤ p follows from the concavity of the logarithm: for p∈[0,1)p∈[0,1), we have ln(1−p)≥−p/(1−p)≥−p (1-p)≥-p/(1-p)≥-p when p≤1/2p≤ 1/2, and direct computation confirms the bound for p>1/2p>1/2. Alternatively, this follows from the Taylor expansion −ln(1−p)=p+p/2+p/3+⋯≥p- (1-p)=p+p/2+p/3+·s≥ p. Thus: N≥ln(1/δ)−ln(1−p)≥ln(1/δ)p.∎ aligned N&≥ (1/δ)- (1-p)\\ &≥ (1/δ)p. aligned Lemma C.3 (Effective Acceptance Probability). Under Assumptions and , the probability that a single trajectory sampled from G is eventually accepted by SRD (either directly or after Regeneration) is at least: peff=pH+ρ⋅pM,p_eff=p_H+ρ· p_M, (16) where pHp_H, pMp_M, and ρ are defined in Equations (6)–(7) and Assumption , respectively. Proof. A trajectory τ∼τ is eventually accepted if: (a) u(τ)≥θhighu(τ)≥ _high, i.e., it is directly routed to Keep. This occurs with probability pHp_H by Eq.(6). (b) θlow<u(τ)<θhigh _low<u(τ)< _high routed to Refine, probability pMp_M by Eq.(7)), AND the refinement procedure produces an acceptable trajectory (probability ≥ρ≥ρ by Assumption3.1). Events (a) and (b) are mutually exclusive since the regions u≥θhigh\u≥ _high\ and θlow<u<θhigh\ _low<u< _high\ are disjoint. By Assumption 3.2 (independence), the refinement outcome in case (b) is independent of the initial routing. Therefore, by the law of total probability: p_accepted ≥p_H + p_M ⋅ρ= p_eff. Note this is a lower bound: with Nrefine>1N_refine>1 attempts, the effective probability is pH+pM⋅(1−(1−ρ))≥pH+ρ⋅pMp_H+p_M·(1-(1-ρ))≥ p_H+ρ· p_M. ∎ Lemma C.4 (Stochastic Dominance of Maxima). Let X and Z be independent random variables and define Y=maxX,ZY= \X,Z\. Then Y stochastically dominates X: Y⪰stX,Y _stX, (17) with strict dominance (i.e., [Y]>[X]E[Y]>E[X]) whenever Pr[Z>X]>0 [Z>X]>0. Lemma C.5 (Order Statistic Gap). Let X1,…,XnX_1,…,X_n be i.i.d. random variables with continuous distribution F having density f bounded away from zero near the right endpoint of its support. Let X(n)X_(n) and X(n−1)X_(n-1) denote the largest and second-largest order statistics. Then: [X(n)−X(n−1)]=Θ(1n).E[X_(n)-X_(n-1)]= ( 1n ). (18) Proof. This is a classical result in order statistics. By the Rényi representation theorem Rényi (1953), if U(1)≤⋯≤U(n)U_(1)≤·s≤ U_(n) are order statistics of n uniform random variables on [0,1][0,1], then: (U(1),…,U(n))=d(S1Sn+1,S2Sn+1,…,SnSn+1),(U_(1),…,U_(n)) d= ( S_1S_n+1, S_2S_n+1,…, S_nS_n+1 ), where Sk=E1+⋯+EkS_k=E_1+·s+E_k and E1,…,En+1E_1,…,E_n+1 are i.i.d. Exponential(1)/standard-exponential random variables. For the uniform distribution: [U(n)−U(n−1)]=[EnSn+1]=1n+1,E[U_(n)-U_(n-1)]=E [ E_nS_n+1 ]= 1n+1, using the fact that [Ei/Sn+1]=1/(n+1)E[E_i/S_n+1]=1/(n+1) by symmetry. For a general distribution F with density f, we use the probability integral transform: X(k)=F(U(k))X_(k)=F(U_(k)). By a Taylor expansion near the right endpoint: [X(n)−X(n−1)]≈1f(F(1−))⋅[U(n)−U(n−1)]=Θ(1n),E[X_(n)-X_(n-1)]≈ 1f(F(1-))·E[U_(n)-U_(n-1)]= ( 1n ), provided f is bounded away from zero. Please see David and Nagaraja (2004) for a complete treatment. ∎ C.3 Proof of Theorem (Sample Efficiency) Proof. We prove each statement in the theorem separately. Part (i): Lower bound for rejection sampling. In pure rejection sampling, a trajectory τ is accepted if and only if u(τ)≥θhighu(τ)≥ _high. By definition, this occurs with probability pHp_H. Let Xi=[u(τi)≥θhigh]X_i=1[u( _i)≥ _high] for i=1,…,Ni=1,…,N, where τi∼ _i are i.i.d. samples. Then Xi\X_i\ are i.i.d. Bernoulli(pHp_H) random variables. The probability of obtaining at least one accepted trajectory is: Pr[∑i=1Xi≥1]=1−Pr[∑i=1Xi=0]=1−(1−pH). [ _i=1X_i≥ 1 ]=1- [ _i=1X_i=0 ]=1-(1-p_H). To ensure this probability is at least 1−δ1-δ, we require: 1−(1−pH)≥1−δ⟺(1−pH)≤δ.1-(1-p_H)≥ 1-δ (1-p_H)≤δ. By Lemma , this requires: N≥ln(1/δ)pH.N≥ (1/δ)p_H. Part (i): Lower bound for SRD. By Lemma , the effective acceptance probability under SRD is at least peff=pH+ρ⋅pMp_eff=p_H+ρ· p_M. Following the same argument as Part (i), but with pHp_H replaced by peffp_eff: Pr[at least one acceptance]=1−(1−peff)≥1−δ [at least one acceptance]=1-(1-p_eff)≥ 1-δ requires: N≥ln(1/δ)peff=ln(1/δ)pH+ρ⋅pM.N≥ (1/δ)p_eff= (1/δ)p_H+ρ· p_M. Part (i): Efficiency ratio. Given the two above statements, we can simply take a ratio of the statements to show the efficiency gain of SRD over Rejection Sampling: NrejectNrefine=ln(1/δ)/pHln(1/δ)/(pH+ρ⋅pM)=pH+ρ⋅pMpH=1+ρ⋅pMpH.∎ N_rejectN_refine= (1/δ)/p_H (1/δ)/(p_H+ρ· p_M)= p_H+ρ· p_Mp_H=1+ ρ· p_Mp_H. (19) Remark C.6 (Tightness of the Bound). The bounds in Theorem are tight up to constant factors. Precisely, we can use Fano’s inequality Cover (1999) in information theory to show that any algorithm that achieves a success probability of 1−δ1-δ must collect sufficient information to distinguish between the hypothesis that at least one good trajectory exists and no good trajectory exists, and this requires Ω(ln(1/δ)/peff) ( (1/δ)/p_eff) samples. Hence, combining the bounds we have: (i) Rejection sampling is optimal among algorithms that treat each sample as either accept or reject with no intermediate processing. c1ln(1/δ)pH≤Nreject≤c2ln(1/δ)pH c_1 (1/δ)p_H≤ N_reject≤ c_2 (1/δ)p_H (20) (i) SRD is optimal among algorithms that can additionally salvage borderline samples with success probability ρ. c1ln(1/δ)peff≤Nrefine≤c2ln(1/δ)peff c_1 (1/δ)p_eff≤ N_refine≤ c_2 (1/δ)p_eff (21) (i) The efficiency gain in is real and guaranteed since any algorithm with effective acceptance probability of peffp_eff will have a sample complexity of Θ(ln(1/δ)/peff) (ln(1/δ)/p_eff), and increasing peffp_eff by salvaging and regeneration will reduce the samples. Corollary The sample efficiency of Speculative Selective Regenerative Decoding (S-SRD) is higher than that of Reward-guided Speculative Decoding (RSD) Liao et al. (2025). Assuming a larger target model is more accurate on the reasoning problem at hand, we can guarantee that peff≥pHp_eff≥ p_H as any salvaged trajectory (provided the draft model can generate this with non-zero probability) regenerated using a more-accurate target model will be accepted. C.4 Proof of Theorem (Expected Quality Improvement) Proof. The proof proceeds in three steps: (1) constructing a coupling, (2) establishing stochastic dominance, and (3) quantifying the improvement. Step 1: Coupling construction. We construct a coupling between rejection sampling and SRD as follows. Both algorithms receive the same sequence of n initial trajectories τ1,…,τn∼ _1,…, _n . Now, let A denote the set of accepted trajectories. For rejection sampling, we have: reject=τi:u(τi)≥θhigh,A_reject=\ _i:u( _i)≥ _high\, For SRD, the accepted set is: regenerate=reject∪regenerate∩accept,A_regenerate=A_reject _regenerate∩ accept, where regeneratedA_regenerated contains trajectories that were regenerated and subsequently accepted. Under this coupling, reject⊆regenerateA_reject _regenerate by construction. Step 2: Stochastic dominance. Define: X X =Rmax(n)=maxτ∈RSR(τ), =R_ (n)= _τ _RSR(τ), Z Z =maxτ∈regenerate∩acceptR(τ). = _τ _regenerate∩ acceptR(τ). By construction: Rmax(n)=maxX,Z.R_ (n)= \X,Z\. By Lemma , maxX,Z⪰stX \X,Z\ _stX. Moreover, strict dominance holds because: Pr[Z>X]≥Pr[regenerate∩accept≠∅]⋅Pr[Z>X∣regenerate∩accept≠∅]>0. [Z>X]≥ [A_regenerate∩ accept≠ ]· [Z>X _regenerate∩ accept≠ ]>0. The first factor is at least 1−(1−pM⋅ρ)>01-(1-p_M·ρ)>0 by Assumption . The second factor is positive under Assumption , which ensures regenerated trajectories have non-trivial probability of achieving high rewards. Therefore, [Rmax(n)]>[Rmax(n)]E[R_ (n)]>E[R_ (n)], establishing Δn>0 _n>0. Step 3: Quantifying Δn _n. To derive the explicit bound, we analyze the probability that a regenerated trajectory achieves the maximum reward. For this, let NRS=|RS|N_RS=|A_RS| be the number of directly accepted trajectories and NR+A=|regenerate∩accept|N_R+A=|A_regenerate∩ accept| be the number of successfully regenerated trajectories. By linearity of expectation: [NRS] [N_RS] =n⋅pH, =n· p_H, [NR+S] [N_R+S] ≥n⋅pM⋅ρ. ≥ n· p_M·ρ. Under Assumption , the rewards of trajectories in SRDA_SRD are exchangeable, the original accepted trajectories in (∈RS _RS) and regenerated trajectories that are eventually accepted (∈regenerate∩accept _regenerate∩ accept) are i.i.d as per the reward function. Now, by symmetry, each trajectory in SRDA_SRD has probability approximately 1|SRD| 1|A_SRD| of being the maximum. The probability that the maximum comes from regenerate∩acceptA_regenerate∩ accept rather than RSA_RS is approximately: Pr[max from regenerated]≈[NR+S][NH]+[NR+S]=n⋅pM⋅ρn⋅pH+n⋅pM⋅ρ=pM⋅ρpH+pM⋅ρ. [max from regenerated]≈ E[N_R+S]E[N_H]+E[N_R+S]= n· p_M·ρn· p_H+n· p_M·ρ= p_M·ρp_H+p_M·ρ. (22) When a regenerated trajectory achieves the maximum, the improvement over the rejection sampling maximum is, by Lemma : [Rmax(n)−Rmax(n)∣max from regenerated]=Θ(1n)E[R_ (n)-R_ (n) from regenerated]= ( 1n ) (23) Finally, Combining and , we have Δn _n =[Rmax(n)]−[Rmax(n)] =E[R_ (n)]-E[R_ (n)] ≥Pr[max from regenerated]⋅[gap∣max from regenerated] ≥ [max from regenerated]·E[gap from regenerated] =pM⋅ρpH+pM⋅ρ⋅Θ(1n) = p_M·ρp_H+p_M·ρ· ( 1n ) =Ω(pM⋅ρn⋅(pH+pM⋅ρ)) = ( p_M·ρn·(p_H+p_M·ρ) ) =Ω(pM⋅ρn⋅(1+pM⋅ρ)) = ( p_M·ρn·(1+p_M·ρ) ) where the last line uses pH≤1p_H≤ 1. This completes the proof. ∎ C.5 Termination Proposition C.7 (Termination). SRD terminates in at most n⋅Nrefinen· N_refine refinement operations and O(n⋅Nrefine)O(n· N_refine) reward evaluations. Proof. We show that SRD terminates in finite time by bounding the number of Regeneration operations. Each of the n initial trajectories can be regenerated at most NrefineN_refine times (by the counter c in Algorithm ). Once a trajectory has been regenerated NrefineN_refine times, it is never added back to the Regeneration queue ℛR. Furthermore, each Regeneration operation produces at most one new trajectory, which inherits the Regeneration count of its parent (incremented by one). Thus, the total number of trajectories ever created is at most: n+n⋅Nrefine=n(1+Nrefine).n+n· N_refine=n(1+N_refine). Since the Regeneration queue ℛR starts with at most n trajectories and each trajectory exits the queue after at most NrefineN_refine Regeneration attempts, the while loop in Algorithm executes at most n⋅Nrefinen· N_refine iterations. Each iteration involves: 1. Finding the regeneration boundary: O(k/m)O(k/m) reward evaluations. 2. Generating the regenerated suffix: O(1)O(1) call to the generative model. 3. Computing the rank of the regenerated trajectory: O(||+|ℛ|)O(|K|+|R|) comparisons. The total number of reward evaluations is thus: O(n⋅Nrefine⋅km)=O(n⋅Nrefine),O (n· N_refine· km )=O(n· N_refine), since k/mk/m is a constant based on predefined hyperparameter choice. ∎ C.6 Weak Monotonicity Proposition C.8 (Weak Monotonicity). Let tK_t denote the set of kept trajectories after t refinement operations, and let Rt=maxτ∈tR(τ)R_t= _τ _tR(τ) (with Rt=−∞R_t=-∞ if t=∅K_t= ). Then the sequence Rtt≥0\R_t\_t≥ 0 is non-decreasing. Proof. Let tK_t denote the set of kept trajectories after t Regeneration operations, and define Rt=maxτ∈tR(τ)R_t= _τ _tR(τ) (with Rt=−∞R_t=-∞ if t=∅K_t= ). We show that Rt+1≥RtR_t+1≥ R_t for all t≥0t≥ 0. Consider the (t+1)(t+1)-th regeneration operation. Let τ be the trajectory being regenerated, and let τ be the resulting regenerated trajectory. We have 33 cases: Case 1: τ is routed to Keep. Then t+1=t∪τK_t+1=K_t∪\τ\, so Rt+1=maxτ∈t+1R_t+1= _τ _t+1 R(τ)=maxRt,R(τ)≥RtR(τ)= \R_t,R(τ) \≥ R_t. Case 2: τ is routed to regenerate. Then t+1=tK_t+1=K_t, so Rt+1=RtR_t+1=R_t. Case 3: τ is routed to Discard. Then t+1=tK_t+1=K_t, so Rt+1=RtR_t+1=R_t. In all cases, Rt+1≥RtR_t+1≥ R_t, establishing weak monotonicity. ∎ Appendix D Prompt Templates This appendix provides the prompt templates used to generate model responses for different benchmarks. All prompts are used exclusively for generation and are shared across all decoding methods. D.1 HotpotQA HotpotQA Generation Prompt Answer the following question: question Bear in mind that your response should be strictly based on the following passages: passages Your task: 1. Carefully reason step by step, using only the information from the retrieved documents. 2. Explicitly cite the supporting evidence by referencing the corresponding document IDs and sentence indices. 3. Ensure that each reasoning step is verifiable from the given documents. 4. After reasoning, provide the final answer clearly in the format: your final answer here your final answer here D.2 MATH500 MATH500 Generation Prompt Please reason step by step, and put your final answer within . question D.3 GPQA Diamond GPQA Diamond Generation Prompt Please reason step by step, and choose the correct answer from A/B/C/D inside . question AlpacaFarm. For AlpacaFarm, we directly use the original user instruction as the generation input, without any additional task-specific prompt templates or formatting. Appendix E Implementation Details This appendix summarizes the hyperparameter settings and implementation details used in our experiments. Unless otherwise specified, all methods share the same generation model, prompt template, and generation-side hyperparameters. Generation Settings. We use temperature-based sampling for all methods, with temperature set to 0.8, top-p set to 0.9, and top-k set to 50. The maximum generation length is set to 500 tokens for MATH500 and HotpotQA, and 1000 tokens for GPQA and AlpacaFarm. SRD Parameters. Selective Regenerative Decoding uses fixed routing thresholds θlow=0.3 _low=0.3 and θhigh=0.5 _high=0.5. The drafting interval is set to 100 steps, matching the configuration used for Speculative Rejection. The reward model is invoked every 10 decoding steps. We cap the maximum number of regeneration steps at 30 and enforce a minimum of one active candidate to prevent premature termination. Speculative Rejection Parameters. For Speculative Rejection, we follow the original paper’s recommended setting, using a rejection threshold α=0.5α=0.5. All other generation and evaluation settings are identical to those used for SRD and Best-of-N. Reward Model Usage. Reward models are queried with a fixed input format that concatenates the task instruction, input context, and the partially or fully generated output. For methods that perform step-level scoring, including SRD and Speculative Rejection, the most recent reward score is used for routing decisions. No additional reward normalization is applied. For Best-of-N, reward scores are computed on the final completed sequences and used for candidate selection. Hardware. Experiments are run on 8×A100 (40GB) GPUs. Generation uses vLLM, and reward models are executed with HuggingFace Transformers. Appendix F Empirical Validation of Theorem To validate the assumptions underlying Theorem , we directly measure the routing distribution (pHp_H, pMp_M, pLp_L) and refinement efficacy (ρ ρ) from SRD runs. For each configuration, we record how candidates are routed after initial scoring and track the outcome of each refinement attempt (i.e., whether a trajectory routed to Refine is subsequently promoted to Keep). N pHp_H pMp_M pLp_L ρ ρ Efficiency Gain 10 0.522 0.148 0.329 1.00 (100%) 1.28× 20 0.513 0.180 0.305 1.00 (100%) 1.35× 30 0.509 0.182 0.308 1.00 (100%) 1.36× Table 6: Empirical routing distributions and refinement efficacy (ρ ρ) on MATH500 (Qwen2.5-Math-1.5B, AceMath-7B-RM, 50 samples per N). The efficiency gain is computed as 1+ρ^⋅pM/pH1+ ρ· p_M/p_H per Theorem . The measured ρ^=1.0 ρ=1.0 across all values of N shows that all salvage attempts were routed to keep, providing strong empirical support for Assumption . The efficiency gain increases with N (1.28×→1.36×1.28×→ 1.36×) because pMp_M grows slightly while pHp_H remains stable, indicating that larger candidate pools produce more mid-tier trajectories amenable to refinement. The routing distribution is consistent across N, with pH≈0.51p_H≈ 0.51–0.520.52, pM≈0.15p_M≈ 0.15–0.180.18, and pL≈0.31p_L≈ 0.31–0.330.33. We note that while these measurements directly validate sample efficiency of SRD highlighted in Theorem , comparing the reward distributions between SRD and rejection sampling to verify Theorem is considered in the next section. Appendix G Empirical Validation of Theorem To validate Theorem , we compare the maximum reward RmaxR_ achieved by SRD and rejection sampling (RS) under a coupled setting on MATH500 with Qwen2.5-Math-1.5B-Instruct and AceMath-7B-RM. Coupling via Seeded Generation. The proof of Theorem relies on a coupling argument where both SRD and RS process the same initial trajectories. To realize this coupling empirically, we pass a deterministic per-sample seed to vLLM’s SamplingParams, ensuring that both methods receive identical initial drafts and identical continuations for shared candidates. This guarantees the superset property: every candidate RS keeps, SRD also keeps, plus SRD additionally refines mid-tier candidates. N SRD R¯max R_ RS R¯max R_ Δn _n SRD wins RS wins Ties Refine improved Pre → Post 10 17.70 17.34 +0.36±1.70+0.36± 1.70 46% 18% 36% 78% 2.85 → 5.96 20 18.75 18.47 +0.28±4.11+0.28± 4.11 54% 24% 22% 98% 3.41 → 6.79 30 19.96 18.66 +1.29±3.41+1.29± 3.41 52% 24% 24% 100% 3.69 → 6.87 Table 7: Theorem validation on MATH500 (Qwen2.5-Math-1.5B, AceMath-7B-RM, 50 samples per N). Both methods start from identical initial drafts via seeded generation. Δn=R¯max−R¯max _n= R_ - R_ (mean ± std). “Pre → Post” reports mean reward before and after refinement. RS Baseline. The RS baseline uses the same incremental generation loop as SRD—generating N partial drafts, scoring at intermediate checkpoints, and keeping candidates above θhigh _high—but without refinement. This corresponds to the spec_rej decoder mode (SRDDecoder with editor=None, θlow=θhigh=0.5 _low= _high=0.5), matching the rejection sampling defined in §. Results. As shown in Table , SRD achieves higher mean RmaxR_ than RS across all tested values of N, consistent with Theorem ’s prediction that Δn>0 _n>0. SRD wins more samples than RS at every N (46% vs. 18% at N=10N=10; 54% vs. 24% at N=20N=20; 52% vs. 24% at N=30N=30). The ties correspond to cases where both methods’ best candidate is the same high-scoring trajectory that both keep (these are the percentage of high trajectories that needed no refinement). Notably, the SRD advantage grows with N: Δn _n increases from +0.36+0.36 at N=10N=10 to +1.29+1.29 at N=30N=30. This is because larger candidate pools produce more mid-tier trajectories amenable to refinement, and the refined candidates increasingly contribute to RmaxR_ . Refinement success rates confirm this trend (78% → 98% → 100%), with substantial reward improvements across all settings (e.g., 3.69 → 6.87 at N=30N=30), providing direct empirical support for Assumption .