Breaking Entropy Bounds: MTP Rejection Sampling for Faster RL Training

Quick answer

Bebop is a method from Alibaba’s Qwen team for keeping multi-token prediction (MTP) fast during reinforcement learning. The problem it solves: MTP gives a free inference speedup by drafting several tokens at once, but during RL the policy’s entropy rises, and the paper proves the MTP acceptance rate is linearly bounded by that entropy. As entropy climbs the draft tokens get rejected more often and the speedup decays. Bebop attacks this with two moves that have to be separated. First, accept drafts by rejection sampling instead of greedy target-only checking, which makes acceptance equal 1 - d_TV(p, q) and degrade smoothly. Second, train the MTP head with a total-variation (TV) loss that directly minimizes that same quantity. Together they hold acceptance near 95% (about a 10% absolute gain over the cross-entropy baseline) and flatten the entropy-acceptance slope from -1.68 to -0.06, which translates to up to 1.8x faster end-to-end asynchronous RL on Qwen3.5, Qwen3.6, and Qwen3.7. The accuracy of the trained model does not change; this is a rollout-throughput method, not an objective change.

Why MTP decays exactly when you need it

MTP and speculative decoding give you tokens in bulk: a small head drafts the next few tokens, the main model verifies them, and accepted drafts skip a forward pass. The accepted run length is the whole game. In stable inference that length is high. In RL it isn’t, and the paper pins down why. Acceptance under greedy target-only sampling follows α ≈ a - b·H(p): a linear function of the policy entropy H(p). RL training deliberately keeps entropy up for exploration, so the very dynamics that make RL work erode the thing making rollouts cheap. This matters because rollout generation, not the gradient step, is where async RL spends its wall-clock, so a 10% acceptance drop is a direct tax on training speed.

The uncomfortable result is the second proposition. You might assume that switching to rejection sampling, or training the draft head to match the target distribution with a standard KL or cross-entropy loss, fixes the entropy dependence. It does not. CE/KL training still yields α ≈ a - b·H(p) with roughly the same slope, because those losses produce a uniform per-token mismatch that accumulates across the exponentially large effective support a high-entropy distribution opens up. The mismatch isn’t where the probability mass is. That is the bound the title is about.

The two components, and which one carries the gain

This is the part to read carefully, because the headline pairs two ideas that do different work.

Rejection sampling is the inference-time decision rule. Instead of accepting a draft only when it equals the target’s argmax, you accept token v with probability min(p(v), q(v)), so the accepted output is provably unbiased regardless of draft quality, and acceptance becomes 1 - d_TV(p, q). This buys smoothness: acceptance degrades continuously under policy updates rather than falling off a cliff. On its own it does not break the entropy bound, as proposition 2 shows.

The TV loss is the training-time fix that actually breaks the bound. It minimizes d_TV(p, q) = 1 - Σ min(p(v), q(v)) directly, the exact quantity rejection sampling cares about. Its gradient is bounded (|∂L/∂z_j| ≤ 1) and proportional to q_j, so optimization effort goes where probability mass actually is, producing a probability-proportional mismatch instead of CE’s uniform one. The payoff is proposition 4: d_TV ≤ δ/2, independent of H. The end-to-end multi-step variant chains this across the γ draft steps and weights earlier steps more, since acceptance compounds multiplicatively. So the honest decomposition: rejection sampling makes degradation smooth, the e2e TV loss makes acceptance entropy-invariant. Swap TV back to CE under the same rejection sampling and the entropy slope returns to -1.68 (figure 8). The loss is the load-bearing piece.

Key results

• Acceptance, Qwen3.5-35A3B (γ=3, rejection sampling): e2e TV over the CE baseline lifts SWE-Bench from 75.1% to 83.1% (+8.0), agentic tasks from 90.3% to 97.0% (+6.7), math 75.0% to 78.0%, code 71.3% to 74.6%. Out-of-distribution MT-Bench gains only +2.3 (65.3% to 67.6%).
• Entropy invariance: the acceptance-vs-entropy slope during RL is -1.68 for target-only and for rejection sampling with CE, but -0.06 for rejection sampling with TV, a roughly 95% reduction. This is the figure-8 result that operationalizes “breaking the bound.”
• Loss ablation (same model and data): KL divergence adds +0.0 to +0.2 over CE (negligible), reverse KL +1.0 to +1.3, per-step TV +2.4 to +5.2, e2e TV +3.0 to +8.0. The ranking is consistent: the further you move toward directly optimizing TV, the better.
• Throughput: per-step RL latency falls 1.5 to 1.8x versus a no-MTP baseline, with agentic rollouts hitting 2.4x; acceptance-rate gain and throughput gain correlate at r=0.81 (figure 9b).
• End-to-end: up to 1.8x faster asynchronous RL on Qwen3.5, Qwen3.6, and Qwen3.7, with model accuracy held constant since rejection sampling guarantees unbiased output.
• No online MTP needed: starting from a TV checkpoint and continuing MTP updates with CE during RL erodes the gain back toward the CE baseline, and continuing with TV adds nothing. Pre-RL TV training is sufficient, which removes the memory overhead of training the head online.

Is the baseline strong, and does cost change the verdict

The comparison is internal: CE, KL, reverse KL, per-step TV, e2e TV, all on the same Qwen models and data. That is a fair like-for-like test of the loss objective, and CE is the standard MTP/speculative-decoding training target, so beating it is meaningful. What the paper does not do is benchmark against a separate speculative-decoding family such as EAGLE-style heads or independent draft models, so “Bebop is the best way to draft” is not established, only “TV is the best loss for an MTP head under RL entropy.” On cost, the verdict survives because the only price is a one-time pre-RL training pass with a fused full-vocabulary TV kernel; there is no per-step online MTP training and no accuracy give-up. The throughput win is real spend saved on rollouts, which is where async RL burns time. This sits alongside other on-policy distillation work for drafting like Draft-OPD, and the broader speculative-decoding mechanics in Domino.

Limits and open questions

The full-vocabulary TV loss needs fused kernels; a top-K=20,000 approximation slows convergence and hurts performance (figure 14b), so memory is a real constraint on very large vocabularies. The gains are in-distribution: +8.0 on SWE-Bench but only +2.3 on out-of-distribution MT-Bench, so a draft head tuned this way may not transfer to traffic far from the RL data. Acceptance still drops with generation position and with sampling temperature, since both raise entropy, and long agentic rollouts show periodic acceptance fluctuation (the “bubble problem”). Everything is on Qwen models with GRPO as the RL backbone, so generalization to other model families and RL algorithms is assumed rather than shown, and there is no head-to-head against non-MTP speculative-decoding methods. The proof also assumes bounded per-token mismatch δ; under extreme entropy shifts a residual entropy dependence in δ is not ruled out.

FAQ

Does Bebop make the RL-trained model more accurate, or only faster?

Only faster. Rejection sampling accepts token v with probability min(p(v), q(v)), which guarantees the sampled output matches the target model’s distribution exactly regardless of how good the draft is. So Bebop changes rollout throughput, up to 1.8x on async RL, while leaving benchmark scores unchanged. Anyone reading “breaking entropy bounds” as a reasoning-accuracy result is misreading it; the entropy in question is the policy’s sampling entropy, and the bound is on MTP acceptance, not on task performance.

In Bebop, is the speedup from rejection sampling or from the TV loss?

Mostly the TV loss. Rejection sampling makes acceptance equal 1 - d_TV(p, q) and degrade smoothly, but on its own it stays entropy-bounded with the same -1.68 slope as greedy target-only sampling (proposition 2). The e2e TV loss is what flattens the slope to -0.06 by producing probability-proportional rather than uniform mismatch. Swap the loss back to CE under identical rejection sampling and the entropy bound returns. Rejection sampling is the necessary decision rule; the loss is what breaks the bound.

Why does cross-entropy-trained MTP still degrade under rejection sampling in Bebop?

Because CE and KL produce a uniform per-token mismatch between draft and target. When RL pushes entropy up, the target distribution spreads probability over an exponentially larger effective support, and that uniform mismatch accumulates across all those tokens. TV loss instead concentrates its gradient where the probability mass is (the gradient is proportional to q_j), so the mismatch stays small exactly where it costs acceptance. That is why CE-RS keeps the -1.68 entropy slope while TV-RS reaches -0.06.

Do you need to keep training the MTP head during RL with Bebop?

No, and that is a practical finding. Starting from a TV-trained checkpoint and continuing to update the head with CE during RL erodes acceptance back toward the CE baseline, while continuing with TV adds nothing measurable. Pre-RL TV training is sufficient and avoids the memory cost of online head training. This contrasts with on-policy distillation methods like N-GRPO where the rollout policy itself keeps changing during training.

One line: Bebop proves MTP acceptance is bounded by policy entropy during RL, then breaks that bound with a total-variation loss plus rejection sampling, holding acceptance near 95% for up to 1.8x faster training at zero accuracy cost. Read the original paper on arXiv.