PaperlayerView exact revision on arXiv

Source-linked AI summary

Breaking Entropy Bounds: Accelerating RL Training via MTP with Rejection Sampling

Yucheng Li, Huiqiang Jiang, Yang Xu, Jianxin Yang, Yi Zhang, Yizhong Cao, Yuhao Shen, Fan Zhou, Rui Men, Jianwei Zhang, An Yang, Bowen Yu, Bo Zheng, Fei Huang, Junyang Lin, Dayiheng Liu, Jingren Zhou

arXiv:2606.12370v1cs.LGcs.CL

TL;DR

MTP can accelerate RL rollouts, but acceptance rates degrade as policy entropy shifts. Bebop uses rejection sampling and an end-to-end TV loss with lightweight pre-RL training, achieving higher and stable acceptance across RL.

  • Problem

    RL rollout inference is a major training bottleneck, while MTP acceptance degrades during RL as target-model entropy shifts constrain achievable acceptance.

  • Method

    Bebop combines probabilistic rejection sampling with an end-to-end TV loss that directly optimizes multi-step acceptance, using lightweight pre-RL MTP training.

  • Results

    Across mathematical reasoning, code generation, and agentic tasks, Bebop yields ∼10% acceptance-rate improvements, up to 95% acceptance, and up to 25% extra inference throughput.

  • Takeaways & Limitations

    Lightweight pre-RL TV training with rejection sampling maintains consistent acceptance and speedup throughout RL, eliminating costly online MTP updates.

  • Takeaways & Limitations

    TV-based entropy invariance holds only within the entropy range covered by SFT data; substantially higher RL exploration entropy can restore entropy-dependent acceptance degradation.

Abstract

from arXiv · show

Reinforcement learning (RL) has become a key component in modern large language models, yet the rollout stage remains the key bottleneck in RL training pipelines. Although Multi-Token Prediction (MTP) offers a natural solution to accelerate rollouts through speculative decoding, many studies have observed that MTP acceptance rates degrade significantly during RL training, leading to limited speedup performance. To address this bottleneck, we present Bebop, a systematic study of MTP in LLM post-training, and offer practical recipes to integrate MTP into large-scale RL pipelines. First, we reveal that the MTP acceptance rate is fundamentally bounded by the fluctuation of model entropy, which demonstrates a clear negative linear relationship with the rise of entropy in the RL stage. Second, we show that probabilistic rejection sampling largely alleviates the disturbance introduced by entropy in RL compared to greedy draft sampling. We further identify that the conventional MTP training objectives (cross-entropy or KL) are suboptimal in such settings, and therefore we propose a novel end-to-end TV loss that directly optimizes multi-step rejection sampling acceptance rate, yielding ~10% acceptance rate improvements, achieving up to 95% acceptance rates and up to 25% extra inference throughput gains across mathematical reasoning, code generation, and agentic tasks. Third, we test various online MTP training strategies during RL and show that pre-RL MTP training with e2e TV loss and rejection sampling achieves a consistent acceptance rate and speedup throughout the entire RL, eliminating the need for costly online MTP updating. We provide extensive experiments and analysis that validate our findings. Experimental results show our method achieves up to 1.8x end-to-end acceleration in async RL training of Qwen3.5, Qwen3.6, and Qwen3.7 models.

1 Introduction

Bebop addresses declining MTP acceptance during RL by pairing probabilistic rejection sampling with a pre-RL end-to-end TV loss. This combination stabilizes acceptance rates without online MTP updates and accelerates asynchronous RL pipelines.

  • Motivation: RL rollout inference dominates end-to-end training time, while direct MTP use during RL suffers declining acceptance rates and limited speedup.The decline is linked to high or increasing policy entropy and policy–draft mismatch caused by weight updates.
  • Rejection sampling: Rejection sampling mitigates entropy-driven degradation because acceptance depends on policy–draft distributional overlap rather than maxy p(y).Target-only acceptance decreases as entropy rises, whereas rejection sampling uses full distributional overlap.
  • RL adaptation: A lightweight pre-RL MTP phase using e2e TV loss and rejection sampling maintains consistent acceptance throughout RL and eliminates costly online MTP training.The policy–draft mismatch caused by policy updates is reported as negligible.
  • MTP training: The end-to-end TV loss directly optimizes multi-step rejection-sampling acceptance, outperforming CE/KL objectives and yielding an extra ∼10% improvement.It also produces stable, inherently entropy-invariant MTP training.
  • Empirical validation: Up to 1.8× end-to-end acceleration is achieved for asynchronous RL pipelines across Qwen3.5, Qwen3.6, and Qwen3.7 models on reasoning, coding, and agentic tasks.The paper also analyzes TV-loss draft distributions, rejection-sampling robustness, temperature, and generation length.

2 Preliminaries

This section introduces MTP speculative decoding, its acceptance mechanisms, and the RL training setting. It establishes that MTP acceptance rates degrade during RL, with later prediction steps declining more, and that entropy-driven fluctuation dominates distribution mismatch.

  • MTP speculative decoding: MTP augments autoregressive LLMs with lightweight draft heads that sequentially predict multiple future tokens in a draft-then-verify process.The target model distribution is p(·|x, y<t), while the draft distribution is q(·|x, y<t).
  • MTP speculative decoding: Acceptance length—the expected number of accepted tokens per verification step—directly determines inference throughput.Its value depends on the acceptance method used during verification.
  • Acceptance methods: Target-only sampling greedily selects the draft token and accepts it with probability p(ˆy), whereas rejection sampling accepts a sampled draft token with probability min(1, p(ˆy)/q(ˆy)).Rejection sampling preserves the exact target distribution p regardless of draft quality, while target-only sampling can provide higher throughput for low-acceptance drafts by avoiding draft-probability computation overhead.
  • RL framework: The RL setup uses GRPO, where the policy generates trajectories for prompts sampled from D, receives scalar rewards, and optimizes a clipped surrogate objective using group-normalized advantages.Each prompt produces a group of G trajectories sampled from the rollout policy πθold.
  • MTP degradation during RL: 1.2% at step 1 and 3.5% at step 3 are the observed per-step MTP acceptance-rate declines during RL, with later prediction steps degrading more.The broader decline ranges from 1.2% at step 1 to 3.5% at step 3, and decomposition analysis identifies entropy-driven fluctuation as dominant while distribution mismatch remains comparatively small.

3 Target Entropy Constraints on MTP Acceptance

Target entropy constrains MTP acceptance: higher entropy lowers target-only acceptance through a robust linear relationship and continues to impair rejection sampling under CE/KL-trained drafts. Because policy entropy fluctuates during RL, this sensitivity limits achievable speedup.

  • Target-Only Sampling: High target entropy spreads probability mass across tokens, increasing draft ranking errors and reducing target-only acceptance.When entropy is low, a moderately accurate draft can still place mass on dominant tokens and achieve high acceptance.
  • Target-Only Sampling: Target-only acceptance decreases approximately linearly with target entropy, with the relationship remaining robust across model sizes, tasks, and training stages.Imperfect drafts steepen the slope but preserve linearity.
  • Rejection Sampling: Under rejection sampling, acceptance equals the total-variation overlap between target and draft distributions, so maximizing acceptance is equivalent to minimizing TV distance.This reframes rejection-sampling optimization as a distribution-matching problem.
  • Rejection Sampling: Rejection-sampling acceptance is not directly bounded by policy entropy, but CE/KL-trained drafts accumulate mismatches more strongly as target entropy rises, increasing TV distance.The resulting entropy relationship has a slope comparable to target-only sampling, though empirically slightly steeper.
  • Implications for RL: Under CE/KL-trained MTP, both rejection and target-only sampling remain sensitive to entropy shifts, inherently limiting speedup during RL.Policy entropy fluctuates significantly during RL, propagating this sensitivity into achievable acceleration.

4 Optimizing MTP for RL Training

This section introduces TV-based objectives for MTP training, directly targeting rejection-sampling acceptance rather than KL’s indirect proxy. The end-to-end TV loss accounts for multi-step compounding and yields probability-focused, entropy-stable optimization.

  • Motivation: TV loss directly minimizes the total variation distance that determines rejection-sampling acceptance, whereas CE/KL optimize it only indirectly through Pinsker’s upper bound.CE and forward KL have identical gradients, but KL minimization does not efficiently minimize TV distance.
  • Gradient behavior: TV gradients are bounded and proportional to q_j, concentrating updates on acceptance-relevant high-probability tokens while suppressing irrelevant vocabulary tails.Tokens with q_j ≤ p_j are encouraged, rejected-token logits are suppressed, and near-zero-q_j tokens receive approximately zero gradient.
  • End-to-end TV loss: The end-to-end TV loss optimizes normalized expected acceptance length by weighting earlier steps more heavily and capturing multiplicative multi-step verification effects.Its effective step weights adapt to current draft quality, emphasizing positions that limit acceptance.
  • Entropy–acceptance relationship: Over 95%, the entropy–acceptance slope is empirically reduced by TV training compared with CE/KL training.TV produces probability-proportional mismatch, while CE/KL produce approximately uniform per-token mismatch that accumulates with effective support.
  • Entropy–acceptance relationship: TV-trained draft models achieve substantially more stable acceptance rates across varying target entropy, unlike CE/KL-trained models’ strong negative correlation.The analysis attributes this stability to entropy-independent TV under probability-proportional mismatch.

5 MTP Adaptation Strategy for RL

The decomposition analysis shows that rejection sampling makes RL-time acceptance degradation almost entirely entropy-driven, with negligible draft–target mismatch from backbone updates. Consequently, pre-RL TV adaptation maintains acceptance throughout RL without online MTP updates, while joint co-training is mainly useful when target-only sampling suffers mismatch.

  • Decomposition analysis: Under target-only sampling, entropy increases and draft–target mismatch both contribute to acceptance degradation, whereas rejection sampling with CE loss is almost entirely entropy-driven.For rejection sampling with CE loss, ∆αmismatch ≈0, indicating that RL weight updates have little effect on draft–target TV overlap.
  • Decomposition analysis: Rejection sampling with TV loss shows near-zero acceptance change across RL training, indicating stable draft–target alignment despite backbone updates.The decomposition attributes acceptance changes to entropy shifts and residual draft–target mismatch caused by backbone updates.
  • Pre-RL adaptation: A one-time pre-RL TV adaptation during SFT maintains high acceptance throughout RL and removes MTP optimizer-state memory and gradient-update costs during RL.This strategy avoids costly online MTP updating while preserving acceptance performance.
  • Online MTP updating: Continuing MTP updates during RL provides no significant improvement from a well-trained TV checkpoint, while CE updates degrade acceptance toward the RS w/ CE baseline.CE makes the draft distribution smoother and erodes the gains from TV training.
  • Online MTP updating: When co-training is needed for target-only sampling, separate learning rates and gradient-norm normalization provide the best trade-off without altering backbone RL optimization.The MTP loss flows only through draft heads, so backbone gradients remain unaffected.

6 Experiments

Experiments show that e2e TV loss with rejection sampling improves MTP acceptance, preserves it during RL despite entropy changes, and accelerates RL rollouts. These gains extend across models, tasks, and training configurations, while online MTP updates can erode them.

  • SFT acceptance: 3–8% acceptance-rate improvements on in-distribution tasks and up to 2.3% on out-of-distribution MT-Bench result from e2e TV loss over CE and KL baselines.On Agent tasks, the CE baseline already reaches 90.3% acceptance, with further improvement from e2e TV loss.
  • SFT acceptance: 95% acceptance is reached after multi-step SFT, especially on agent tasks, and acceptance rates increase consistently with model size.Qwen3.7 models use e2e TV loss, whereas Qwen3.6 models use CE loss.
  • RL stability: RS w/ TV maintains stable or improving acceptance length throughout RL, including SWE workloads with slightly increasing entropy.In reasoning RL, acceptance increases primarily because policy entropy drops rather than because draft alignment alone improves.
  • RL throughput: 1.5–1.8× lower per-step RL training latency is achieved with MTP and rejection sampling, with up to 2.4× rollout speedup on Agentic RL.The latency gains are consistent across workloads and provide wall-clock savings at scale.
  • RL stability: Over 95% reduction in the entropy–acceptance slope, from −1.68 to −0.06, is achieved with TV loss during RL training.TV loss also shifts the intercept upward, reducing acceptance dependence on target entropy.
  • Online MTP updates: Acceptance converges toward the no-weight-update baseline when MTP weights are updated with CE loss during RL, degrading RS w/ TV toward RS w/ CE.The change reflects a shift in the draft distribution during online MTP updates.

7 Discussion

The discussion explains why e2e TV loss sharpens draft distributions and why rejection sampling remains more robust than target-only sampling under RL-induced distribution shifts. It also shows how temperature, sequence position, and agentic workload structure affect acceptance, with rejection sampling generally preferred in practice.

  • Distributional effects of TV loss: TV loss sharpens draft distributions toward the target’s entropy, unlike smoother CE/KL drafts, improving the overlap relevant to rejection sampling.Its gradient emphasizes tokens near q_j ≈ p_j while ignoring irrelevant low-probability tokens.
  • Distributional effects of TV loss: During RL, TV loss yields target-like draft entropy but larger KL distance, lower α_p>q, and higher α_q>p than CE loss.Switching losses shifts MTP metrics toward the characteristic pattern of the new objective; with RS w/ TV + CE, draft entropy gradually increases.
  • Robustness of acceptance methods: Rejection sampling degrades continuously under ranking shifts, whereas target-only sampling can fail discontinuously; high target entropy amplifies this fragility gap.Despite the qualitative difference, the observed entropy–acceptance slopes are similar for target-only and rejection sampling, with b_TO ≈ b_RS.
  • Temperature and generation position: Higher sampling temperatures increase target entropy and reduce acceptance, while rejection sampling maintains relatively stable acceptance lengths as target-only sampling degrades sharply.Acceptance also tends to be higher early in sequences and lower later, especially in long reasoning generations as entropy increases.
  • Robustness of acceptance methods: 23 out of 24 model–task combinations fall in the RS-better region, confirming that rejection sampling generally outperforms target-only sampling for natively trained MTP models.The diagnostic boundary is dTV(p, q) < 1 − p(ŷ), where ŷ = arg max_y q(y).
  • Agentic workloads: Agentic workloads show long, multi-turn generations with variable entropy and increasing acceptance fluctuations, yet achieve the largest acceptance-rate improvement of 5% from TV-loss training.These workloads include tool calls, code execution, and iterative refinement.

8 Related Work

This section situates Bebop within speculative decoding, reinforcement learning for LLMs, and total variation distance. It connects draft-model acceleration, RL post-training pipelines, and distributional overlap in rejection sampling.

  • Speculative Decoding: Speculative decoding accelerates autoregressive LLM inference by proposing multiple tokens with a lightweight draft model and verifying them in parallel with the target model.Related draft architectures include independent small models, early-exit heads, auxiliary heads, and MTP heads.
  • Reinforcement Learning for LLMs: Reinforcement learning aligns LLMs with human preferences and enhances reasoning and agentic capabilities through rollout, reward evaluation, and policy update stages.GRPO and GSPO improve the optimization objective itself, while asynchronous or partial approaches operate at the system level.
  • Total Variation Distance in Machine Learning: α = ∑y min(p_y, q_y) = 1 − dTV(p, q): in speculative decoding, rejection-sampling acceptance equals distributional overlap measured by total variation distance.TV distance is also used in distribution testing, generative modeling, and Markov-chain convergence analysis.

9 Conclusion

Bebop studies MTP for LLM reinforcement learning and finds that entropy constrains acceptance rates, while end-to-end TV training improves rejection-sampling acceptance. The paper also identifies theoretical and distribution-conditional limitations in its entropy analysis and TV-training guarantees.

  • Key findings: Bebop finds that MTP acceptance rates under target-only and rejection sampling are linearly constrained by the target model’s entropy.This is presented as one of the study’s three key findings.
  • Key findings: ∼10% acceptance-rate improvements, up to 95% acceptance, and up to 25% extra inference throughput result from Bebop’s end-to-end TV loss directly optimizing multi-step rejection-sampling acceptance.The supplied passage reports these outcomes for Bebop’s TV loss.
  • Limitations: The entropy–acceptance analysis relies on heuristically motivated modeling assumptions rather than formally proven assumptions, leaving their tightening open.The assumptions model uniform versus probability-proportional mismatch and are motivated by gradient structures.
  • Limitations: TV training’s entropy invariance is distribution-conditional and holds within the entropy range covered by SFT training data.The passage notes that RL exploration can drive the policy beyond this covered range.

A Derivation of TV Loss Gradient · B Comparison with Forward KL Divergence Gradient

The section derives the TV-loss gradient with detached target probabilities and establishes its boundedness. It contrasts this gradient with forward KL, showing that TV focuses on rejection-sampling-relevant and non-negligible tokens while avoiding large overconfidence-driven forces.

  • A Derivation of TV Loss Gradient: The TV-loss derivation treats the target-model probability p as detached and defines draft probabilities q_j through the softmax of logits z.The draft head outputs logits z ∈R|V|, with q_j obtained by softmax.
  • A Derivation of TV Loss Gradient: The derivation obtains the gradient with respect to each logit z_j by differentiating the TV loss through q_j and the subgradient of min(p_v, q_v).Because p is constant, the derivative of min(p_v, q_v) with respect to q_v is handled using its subgradient.
  • A Derivation of TV Loss Gradient: The gradient uses S = ∑v 1[qv ≤pv] · qv, which aggregates draft probability over tokens satisfying the rejection-sampling condition.The quantity S lies in [0, 1].
  • A Derivation of TV Loss Gradient: The TV gradient is bounded because q_j ∈[0, 1] and |1[qj ≤pj] −S| ≤1.This boundedness follows directly from the stated range of q_j and the indicator-based deviation bound.
  • B Comparison with Forward KL Divergence Gradient: The comparison derives the forward-KL gradient for DKL(p∥q), providing the baseline against which the TV gradient’s behavior is evaluated.The forward KL divergence is defined as DKL(p∥q) = ∑v pv log pv … in the supplied passage.
  • B Comparison with Forward KL Divergence Gradient: Unlike TV, forward KL applies nonzero force to every token with qj ≠ pj, whereas the TV gradient is proportional to qj and ignores low-probability tokens.The distinction follows from the respective gradient structures described in the comparison.
  • B Comparison with Forward KL Divergence Gradient: TV explicitly distinguishes tokens accepted or rejected under rejection sampling through 1[qj ≤pj], while forward KL does not.The indicator directly incorporates the rejection-sampling outcome into the TV gradient.
  • B Comparison with Forward KL Divergence Gradient: When qj ≫pj, forward KL can produce a large gradient, but the TV gradient remains bounded by qj.This limits the effect of overconfident draft probabilities in the TV formulation.

C Analysis of the Reverse KL Divergence … D.2 Target-Only Sampling

The analysis ranks TV loss above reverse KL and forward KL for rejection-sampling optimization, while showing that target-only acceptance decreases with target entropy because distributional concentration and ranking instability worsen.

  • C Analysis of the Reverse KL Divergence: Reverse KL shares TV’s q_j-proportional gradient structure, reducing pressure on low-probability tokens and weakening entropy–acceptance coupling relative to forward KL.This improves capacity allocation compared with forward KL.
  • C Analysis of the Reverse KL Divergence: Reverse KL remains suboptimal because zero-forcing can drop target modes, reducing overlap and rejection-sampling acceptance.Unlike forward KL, reverse KL does not penalize q(v) →0 when p(v)>0.
  • C Analysis of the Reverse KL Divergence: Reverse KL penalizes over-estimation more strongly than under-estimation, driving q(v)≤p(v) while reducing total overlap.Rejection-sampling acceptance penalizes both estimation errors symmetrically through overlap.
  • C Analysis of the Reverse KL Divergence: TV loss > Reverse KL > Forward KL (CE) for suitability to optimize rejection-sampling acceptance rates.TV directly optimizes dTV(p, q) and avoids reverse KL’s zero-forcing and asymmetric-penalty failure modes.
  • D Entropy-Acceptance Relationship under Different Training Objectives: The analysis examines how target-model entropy H(p) constrains MTP acceptance rates under different acceptance methods and training objectives.Finite draft capacity makes the mismatch structure objective-dependent.
  • D.1 Setup and Notation: CE/KL training assumes approximately uniform per-token mismatch, whereas TV training assumes absolute error scales with token probability.These are the two mismatch structures used in the analysis.
  • D.2 Target-Only Sampling: Under target-only sampling, greedy draft selection chooses arg max_y q(y) and accepts the selected token with probability p(ŷ).With a correctly identified target top-1 token, acceptance becomes max_y p(y).
  • D.2 Target-Only Sampling: max_y p(y) decreases monotonically with H(p), with acceptance lower-bounded by exp(−H(p)); empirically, the linear approximation remains robust across scales, tasks, and training stages.The slope estimate is b_TO ∼ exp(−H̄). Ranking errors at high entropy further steepen the negative slope, and b_TO is empirically comparable to b_RS.

D.3 Rejection Sampling with CE/KL Training · D.4 Rejection Sampling with TV Training

CE/KL training creates uniform per-token mismatches, so rejection-sampling acceptance declines as entropy rises. TV training instead produces probability-proportional mismatches, making the acceptance bound entropy-independent under its bounded log-ratio assumption, though finite capacity can restore a weaker correlation.

  • D.3 Rejection Sampling with CE/KL Training: CE/KL-trained drafts therefore exhibit a linear negative entropy–acceptance relationship over moderate entropy ranges.The linearization uses a first-order Taylor approximation when H(p) varies over a moderate range.
  • D.3 Rejection Sampling with CE/KL Training: CE/KL training applies uniform optimization pressure across tokens, causing residual mismatches that accumulate over the effective support as entropy increases.High-entropy distributions spread probability across approximately exp(H(p)) tokens, increasing total TV distance.
  • D.3 Rejection Sampling with CE/KL Training: CE/KL is suboptimal because its KL gradient allocates finite capacity uniformly, rather than because Pinsker’s inequality is intrinsically loose.This allocation also reduces attention to tokens that matter most for rejection-sampling acceptance.
  • D.4 Rejection Sampling with TV Training: TV training gives high-probability tokens stronger gradients and nearly ignores low-probability tokens, directing capacity toward rejection-sampling-relevant mass.Its feedback drives the probability ratio r_j = q_j/p_j toward 1.
  • D.4 Rejection Sampling with TV Training: TV training yields probability-proportional mismatch, |q − p| ≲ δ · p, rather than CE/KL’s uniform mismatch, |q − p| ≲ σ.The proportional-mismatch result relies on bounded log-ratio error over the effective support.
  • D.4 Rejection Sampling with TV Training: Under constant δ, the TV-distance bound is independent of H(p), so TV training substantially weakens entropy dependence in acceptance.Tail tokens contribute negligible probability mass and negligible TV distance.
  • D.4 Rejection Sampling with TV Training: The probability-proportional mismatch is a modeling approximation because optimizer dynamics such as Adam’s second-moment normalization can attenuate raw q_j-proportional gradients.Thus, the analysis does not establish proportional mismatch as an unconditional theorem.
  • D.4 Rejection Sampling with TV Training: Finite draft capacity can make δ entropy-dependent as effective support grows, reintroducing a residual but substantially attenuated entropy–acceptance correlation.Maintaining uniform relative accuracy across more tokens may require additional capacity.

E Rejection Sampling Decision Boundary Derivation … G.2 Gumbel-Max Trick (vLLM)

The paper derives when rejection sampling outperforms target-only sampling, then details fused TV-loss computation and production implementations using multinomial or Gumbel-Max draft sampling. These methods combine sequential acceptance with residual resampling while exposing implementation and memory tradeoffs.

  • E Rejection Sampling Decision Boundary Derivation: RS outperforms target-only sampling when dTV(p, q) < 1 − p(ˆy), where ˆy is the draft’s greedy top-1 token.Equivalently, the draft–target total variation distance must be smaller than the target mass outside the greedy prediction.
  • E Rejection Sampling Decision Boundary Derivation: A sufficiently well-aligned draft always exists for which rejection sampling is beneficial under any non-degenerate target distribution.This follows because 1 − p(ˆy) ≥ 1 − max_y p(y) > 0.
  • F Fused TV Loss Kernel: The fused TV-loss forward and backward kernels compute full-vocabulary loss and draft-logit gradients using tiled vocabulary iteration without materializing softmax outputs.The forward pass computes overlap and auxiliary S, while the backward pass reuses cached quantities to compute gradients.
  • F Fused TV Loss Kernel: The forward kernel stabilizes softmax normalization, accumulates TV overlap and S, and returns a clamped loss ℓ = clamp(1 − overlap, 0, τmax).Tensor-parallel execution reduces normalization and overlap quantities across ranks; an optional top-K path reduces memory from O(|V|) to O(K).
  • G Rejection Sampling Inference Implementation: Production rejection sampling modifies both stages by sampling draft tokens from q, caching draft probabilities, and computing acceptance ratios during verification.This differs from target-only sampling, which selects draft tokens with arg max and accepts using only target probability.
  • G.1 Multinomial Draft Sampling (SGLang): Multinomial sampling accepts each draft token with probability min(1, p_i(ˆy_i)/q_i(ˆy_i)) and stops at the first rejection.If rejection occurs, or all γ drafts are accepted, residual resampling generates the next token using a two-pass CDF inversion.
  • G.1 Multinomial Draft Sampling (SGLang): Multinomial implementation caches full draft probability vectors with memory overhead O(γ × |V|) per request.Here γ denotes the number of MTP steps.
  • G.2 Gumbel-Max Trick (vLLM): vLLM uses Gumbel-Max sampling, computing arg max_v[log q(v)/τ + G_v] and caching temperature-scaled draft logits before verification.Verification separates sequential acceptance from residual-logit computation, then samples the residual distribution with the same Gumbel-Max procedure.
Loading 2606.12370v1…