ResiSpec: Enhancing Multi-Candidate Speculative Sampling via Residual Distribution Shaping

• Autoregressive decoding generates tokens one by one, repeatedly accesses the expanding KV cache, and leaves GPU compute underused amid an I/O bottleneck.Source: Introduction · p. 1
• Speculative decoding separates generation: a lightweight draft model rapidly proposes candidate tokens at a fraction of the cost, and the target model validates them in one parallel forward pass; longer accepted sequences reduce inference steps.Source: Introduction · p. 1
• Tree-based and batch-sampling methods expand candidate choices to increase accepted tokens per inference step, but later candidates’ acceptance declines as verification chains grow (Cai et al. 2024; Li et al. 2024b).The introduction notes that marginal utility diminishes as batch size or tree width grows, sometimes causing plateaus or efficiency regressions.Source: Introduction · p. 1
• Residual Drift occurs because rejection shifts the target distribution toward the draft model’s blind spots, making remaining pre-sampled candidates irrelevant and forcing resampling.The shift follows from exact verification’s need to sample from a residual distribution after rejecting a draft candidate.Source: Introduction · p. 2
• ResiSpec reshapes verification with an auxiliary proxy of draft density, steering rejection residuals toward draft high-confidence regions so pre-sampled candidates remain viable without compromising target-model statistical integrity.The framework reformulates verification criteria to prevent candidate obsolescence after preceding rejections.Source: Introduction · p. 2
• Up to 1.92× speedup over multi-candidate methods while maintaining zero-bias sampling across benchmarks is demonstrated for ResiSpec.The paper also states that it proves ResiSpec’s mathematical exactness.Source: Introduction · p. 2

Auto-regressive Acceleration and Speculative Decoding

• Speculative decoding (SD) uses a small draft model and parallel target-model verification for lossless acceleration, but its performance is capped by the draft model’s hit rate on one linear sequence.The passage describes autoregressive generation as constrained by memory bandwidth and cites the origins of autoregressive generation and SD (Radford et al. 2019; Mann et al. 2020; Achiam et al. 2023; Touvron et al. 2023a; Leviathan, Kalman, and Matias 2023; Chen et al. 2023).Source: Related Work · p. 2

Multi-Candidate and Tree-Based Speculation

• Multi-candidate methods verify branching paths in parallel, using specialized candidate-generation modules or tree construction approaches such as Sequoia’s dynamic programming.SpecInfer introduced tree-based attention; EAGLE, Medusa, Hydra, and KOALA use specialized heads or lightweight modules, while prior work studies theoretical token-selection criteria (Hu et al. 2025b).Source: Related Work · p. 2

Scalability Limits of Standard Verification Protocols

• ResiSpec optimizes sampling for large branching trees to improve the marginal utility of additional candidates and increase expected token yield.The paper presents this as a response to standard sampling protocols that scale inefficiently as candidate counts grow, bottlenecking acceptance length.Source: Related Work · p. 2

Speculative Decoding

• Speculative decoding drafts γ tokens from the draft model, then verifies them in parallel with the target model to accelerate autoregressive sampling.Each token is accepted with probability min(1, p_tgt(x)/p_dft(x)); if none are accepted, the target model resamples from an adjusted distribution to ensure correctness.Source: Preliminary · p. 2

Multi-candidate Tree-structured Verification

• Tree-structured schemes arrange N speculative tokens by depth d and branching factor b to explore multiple possible future paths.Depth is the number of sequential predictions along each path, and branching factor is the number of parallel candidates at each position.Source: Preliminary · p. 2
• At each tree node, the draft model proposes b independent candidates, which are verified sequentially to preserve the target distribution’s exactness.Candidate xi is accepted with probability min(1, p_tgt^(i)(xi)/q_dft(xi)); rejection updates the target distribution to the residual for the next candidate.Source: Preliminary · pp. 2–3
• In tree verification, acceptance continues down a candidate’s children, while rejection of all b candidates truncates the branch and triggers resampling from the cumulative residual distribution.A tree-attention mask lets the target model verify all paths in T in one forward pass, increasing the potential number of accepted tokens per step.Source: Preliminary · p. 3

Decoding

• Standard verification checks N candidates sequentially, and after x1 is rejected, x2 must be checked against the rejection residual to preserve exactness.The residual is proportional to max(0, p(x)−q(x)).Source: Decoding · p. 3
• The residual assigns zero probability wherever q(x) meets or exceeds p(x), concentrating its mass in the draft model’s blind spots.Meanwhile, every candidate is sampled independently from the original draft distribution q(x).Source: Decoding · p. 3
• This creates a support mismatch: after early rejection shifts verification away from q(x)’s high-density regions, remaining candidates have little statistical visibility.The resulting cascade of candidate obsolescence explains the sharply declining marginal acceptance utility.Source: Decoding · p. 3
• Expanding tree width incurs linear verification cost but yields sub-linear acceptance gains as the residual distribution diverges from the draft distribution.Thus wider speculation spends increasing parallel verification compute on candidates with diminishing acceptance utility.Source: Decoding · p. 3
• Figure 1 shows that subsequent candidates’ acceptance probability rapidly approaches zero after the first candidate, leaving them with near-zero marginal utility.This pattern is reported on CNN/DM with Llama-2-7B and Vicuna-7B targets, a Llama-68M draft, and temperatures 0.6 and 1.0; Appendix Table 5 reports modest EAL improvements and a sharp drop in efficiency score η as candidate count N increases.Source: Figure 1 · p. 3, Decoding · p. 3
• ResiSpec is motivated by re-aligning verification criteria so rejection residuals remain within the draft model’s high-density regions, potentially keeping later candidates useful.The paper presents this as a way to mitigate Residual Drift and break the scaling bottleneck.Source: Decoding · p. 3

Method: Residual Distribution Shaping

• ResiSpec uses a strategically constructed proxy k instead of q during verification to keep the post-rejection residual close to q and sustain later candidates’ acceptance.Figure 2 illustrates how this mitigates residual drift and keeps pre-sampled candidates viable across the verification batch.Source: Method: Residual Distribution Shaping · p. 3, Figure 2 · p. 4

Problem Formulation

• In standard speculative decoding, candidate x is accepted with probability min(1, p(x)/q(x)); ResiSpec uses k(x) in place of q(x) to control the failure state.The residual distribution is p′(x) = r(x)/Z, where r(x) is the unnormalized mass reserved for residual sampling.Source: Problem Formulation · p. 3
• The proxy’s nonnegative slack s(x) restores its normalization but may be nonzero only where residual mass is absent, enforcing disjoint support.The formulation also constrains k(x) so the sampling process remains exact, with marginal distribution p(x).Source: Problem Formulation · pp. 3–4

1. Probability Constraint: P

• A valid proxy k requires slack mass equal to reserved residual mass Z, while satisfying k(x_i) = q(x_i) at the sampled point and r(x) ≤ p(x).The construction objective is to maximize overlap between the shaped residual and draft q, equivalently minimizing their L1 distance.Source: §1 · p. 4

Theoretical Boundaries: Ideal Shaping and Limits

• The L1-optimal residual is r(x) = Zq(x), but its feasible budget is bounded by the minimum p(x)/q(x) over q’s support.With long-tail tokens where p(x) approaches zero and q(x) remains positive, that bound can collapse toward zero; full support also makes ideal alignment force Z = 0, violating local alignment at an overestimated rejected candidate.Source: Theoretical Boundaries: Ideal Shaping… · pp. 4–5

Practical Implementation: The ResiSpec Algorithm

• ResiSpec therefore chooses the smallest feasible Z, set by the local gap q(x_0) − p(x_0), to maintain draft fidelity without exhausting residual mass.Theoretical analysis says L1 distance increases with Z above Z*, while the local gap requires injecting slack where residual mass is zero.Source: Practical Implementation: The ResiSpec… · p. 5
• Against SpecInfer, ResiSpec increased accepted length by up to 1.86× and throughput by up to 1.68×.Table 1 reports results for a 3-branch complete tree of depth 5, averaged over 200 runs.Source: Table 1 · p. 6
• GetProxy clips the initial residual to r_i = min(Zq_i, p_i), redistributes any deficit among tokens with remaining capacity, then constructs k = p − r and sets k(x_0) = q(x_0).This capacity-aware redistribution ensures total residual mass Z while respecting r ≤ p.Source: Practical Implementation: The ResiSpec… · p. 6

Theoretical Verification

• ResiSpec’s iterative residual shaping is provably unbiased, preserving a marginal distribution identical to target p(x) across verification steps, with zero distributional shift versus autoregressive decoding.The theoretical guarantee is supported by empirical validation.Source: Theoretical Verification · p. 6

Experiment Setup

• Evaluations use Llama-2-7B as target and JF68M as draft across CNN/DM, OpenWebText, and C4 at temperatures 1.0 and 0.6.Efficiency is assessed by accepted length and throughput on a single NVIDIA RTX 3090 GPU, averaged over multiple runs.Source: Experiment Setup · p. 6

Main Results

• ResiSpec improves accepted length by up to 1.86× and throughput by up to 1.68× over SpecInfer across tested datasets and temperatures.The comparison uses a 3-branch complete tree with depth 5.Source: Main Results · p. 6
• ResiSpec’s add-on integration with EAGLE and Sequoia improves accepted length and throughput under matched decoding settings.EAGLE accelerates candidate generation, while Sequoia optimizes the verification tree.Source: Main Results · pp. 6–7
• ResiSpec adds no model forward pass; its overhead comes from distribution-level operations after verification, mostly memory-bound GPU operations.Fused kernels could further reduce its latency; Figure 3 breaks down per-step latency and ResiSpec’s internal runtime.Source: Main Results · p. 7, Figure 3 · p. 7

Ablation Study

• Under comparable verification costs, ResiSpec consistently outperforms SpecInfer, with larger gains on deeper, narrower trees.This pattern indicates stronger mitigation of accumulated Residual Drift over longer speculation horizons; additional model pairs and datasets also show consistent accepted-length and throughput improvements.Source: Ablation Study · p. 7, Table 3 · p. 7

Empirical Validation of Distributional Exactness

• The KL divergence between ResiSpec-generated and target distributions remains on the order of 10^-10, consistent with floating-point noise rather than systematic bias.The results support stochastic equivalence to the target model without sacrificing generation quality for speed.Source: Table 4 · p. 7, Empirical Validation of Distributional… · p. 7

Conclusion

• ResiSpec addresses residual drift in multi-candidate speculative decoding by shaping rejection residuals toward the draft, preserving exact sampling and achieving up to 1.92× speedup.As a verification-time add-on, it can complement existing candidate-generation and tree-construction methods.Source: Conclusion · p. 7

A.1 Correctness and Exactness

• Under the Local Alignment condition k(x) = q(x) at the sampled candidate, ResiSpec’s output token has marginal distribution exactly p(x).The theorem defines p(x) as the target distribution and q(x) as the draft distribution.Source: §A.1 · p. 10
• On the acceptance path, local alignment lets the acceptance probability be rewritten using k, so accepted outputs sample from the intersection of p and k.The condition applies at the specific verification point for the proposed token.Source: §A.1 · p. 10
• On rejection, the system samples from the residual distribution, whose normalized mass complements the acceptance mass.The rejection probability is the complement of total acceptance mass, and the residual normalization constant cancels.Source: §A.1 · p. 10
• Summing the mutually exclusive acceptance and rejection paths yields the target marginal for every token x′.The proof applies the law of total probability to the two paths.Source: §A.1 · p. 10
• Any deviation of proxy k from draft q is compensated in the failure state, provided k and q align at the verification point.The residual distribution is coupled to the same proxy used in the acceptance test.Source: §A.1 · p. 10

A.2 Monotonicity of Residual Shaping Loss with Redistribution

• The minimum L1 distance is zero for residual mass Z ≤ Z* and strictly increases for Z > Z*, where Z* is the critical bottleneck capacity.The theorem characterizes how residual mass affects the distance between the normalized residual distribution and the draft distribution.Source: §A.2 · p. 11
• Above Z*, capacity-limited bottleneck tokens must be clipped and mass redistributed elsewhere, increasing the L1 distance and favoring a minimal mass budget.The minimum deviation sets residual mass to target capacity in bottleneck regions and at least the draft-scaled mass elsewhere.Source: §A.2 · p. 11

B Calculation of Empirical Validation of Distributional Exactness

• The empirical exactness check compares the target distribution with the aggregate marginal output distribution of a multi-candidate verification chain.The output is the first accepted candidate, or a sample from the residual distribution if all candidates are rejected.Source: B Calculation of Empirical Validation… · p. 11

B.1 Path-based Marginal Probability Calculation

• Marginal probability accounting sums mutually exclusive paths in which candidates are accepted sequentially after prior rejections, using the reshaped residual after each rejection.The acceptance probability is denoted α_i, and the rejection probability at step i is 1 − β_i.Source: §B.1 · pp. 11–12
• If all n candidates are rejected, the output probability mass comes from sampling directly from the final residual distribution pres,n.This is the fallback path in the marginal-probability calculation.Source: §B.1 · p. 12

B.2 Verification via KL Divergence

• D_KL remained typically <10^-8 across test cases, within expected floating-point error and consistent with no distributional bias.The reconstructed marginal distribution is compared with the target distribution.Source: §B.2 · p. 12

Execution environment

• Matched throughput runs use the same Docker image, checkpoints, dataset order, and single GPU, execute baseline and ResiSpec sequentially, and record logs and CSV summaries.Throughput is generated tokens divided by wall-clock decoding time after warmup.Source: C Reproducibility Details · p. 12

Models and datasets

• Experiments cover Llama-2-7B with Llama-68M, additional fixed-tree model pairs, Sequoia and EAGLE compatibility pairs, and CNN/DM, OpenWebText, and C4.For 200-example runs, matched methods use the same prompt indices; EAGLE runs use two warmup prompts and 200 measured prompts.Source: C Reproducibility Details · p. 12

Decoding configurations

• Fixed-tree runs use a complete 3-branch, depth-5 tree, sequence budget 512, T = 0.6 or 1.0, and p = 1.0; Sequoia and EAGLE use specified matched settings.Sequoia uses its original tree-selection logic and L40 grow maps with M = 384; EAGLE uses total_token=60, depth=5, max_new_tokens=128, and top_k=10 in the main compatibility table, with a top_k=15 sensitivity rerun.Source: C Reproducibility Details · p. 12

ResiSpec integration

• ResiSpec reshapes residual distributions during fixed-tree verification, after Sequoia selects its tree, and between consecutive EAGLE candidate siblings sharing a parent.In Sequoia, the original policy controls tree budget and topology; in EAGLE, p and q are updated by the ResiSpec recurrence after each rejection.Source: C Reproducibility Details · p. 12

Randomness control and timing

• Matched sampling runs use fixed seeds across Python, NumPy, PyTorch CPU and CUDA, deterministic cuDNN, and a per-prompt seed schedule of s + i.Throughput runs disable KL diagnostics; distribution preservation is evaluated separately, and synchronized per-step latency profiling is not mixed with end-to-end throughput measurements.Source: C Reproducibility Details · pp. 12–13

D Ablation Experiment Results

• At fixed speculation depth 4, increasing candidate count yields only modest EAL gains while efficiency score η drops sharply.Results are averaged over CNN/DM using Llama-2-7B.Source: Table 5 · p. 13
• ResiSpec significantly outperforms SpecInfer in accepted length and throughput across different model-pair configurations.The target models were Llama-2-7B and Sheared-LLaMA-2.7B; draft models were Sheared-LLaMA-1.3B, TinyLlama-1.1B, Tiny-Vicuna-1B, and JF68M.Source: Table 6 · p. 14
• The model-pair ablation used Llama-2-7B and Sheared-LLaMA-2.7B as target models, with four listed draft models.The draft models were Sheared-LLaMA-1.3B, TinyLlama-1.1B, Tiny-Vicuna-1B, and JF68M.Source: Table 6 · p. 14