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

Reinforcement learning (RL) is a cornerstone of modern large language model (LLM) development. It is essential for aligning models with human preferences and boosting reasoning capabilities. However, the training process is notoriously slow. The "rollout" stage—where the model generates text to be evaluated—acts as a massive computational bottleneck. To speed this up, researchers use Multi-Token Prediction (MTP). This technique uses lightweight "draft heads" to predict several future tokens at once. A larger backbone model then verifies them in a single parallel pass (a process called speculative decoding).

While MTP works well during standard inference, it often fails during RL training. As the model learns and its policy evolves, the accuracy of these draft heads tends to plummet. This causes the speedup to evaporate exactly when you need it most. The Bebop paper addresses this by identifying a fundamental limit to MTP speedup: the model's own entropy (a measure of prediction uncertainty).

The entropy-induced MTP bottleneck

Current approaches to accelerating RL via MTP generally rely on two methods: greedy "target-only" sampling or standard cross-entropy (CE) training. In target-only sampling, the system picks the most likely token from the draft and checks if the backbone agrees. This is brittle. The authors show that this method is fundamentally capped by the maximum probability of the target distribution. This cap drops precipitously as the model's uncertainty—its entropy—increases during RL.

Even when using more sophisticated rejection sampling (a method where tokens are sampled probabilistically to ensure an unbiased output), standard MTP training objectives like CE or KL divergence (a measure of how one probability distribution differs from a second) fail to maintain speed. The authors observe that as RL progresses, the backbone model's entropy fluctuates. Consequently, the MTP acceptance rate degrades significantly .

Most existing literature attributes this to "distribution mismatch." This is the idea that the draft heads cannot keep up with the moving target of the updated backbone. However, the paper's decomposition analysis reveals a different culprit. Entropy is the dominant driver of degradation. The mismatch caused by weight updates is actually negligible .

Essentially, the draft heads are being crushed by the rising uncertainty inherent in the RL exploration process.

Decoupling acceptance from uncertainty

The Bebop framework breaks this link by changing how the draft heads are trained and used during rollouts. Instead of trying to mimic the backbone's exact probabilities via CE loss, the authors propose a novel end-to-end (e2e) Total Variation (TV) loss.

The mechanism works in three distinct layers:

1. Probabilistic Rejection Sampling: Bebop utilizes rejection sampling instead of the greedy selection used in target-only sampling. In this mode, a draft token is accepted with a probability $\min(1, p/q)$. Here, $p$ is the target probability and $q$ is the draft probability. The authors prove this method is far less sensitive to entropy shifts. Its acceptance rate is defined by the total distributional overlap (the TV distance) rather than the peak probability of a single token.

2. Direct TV Optimization: The core innovation is the e2e TV loss. Conventional losses like CE try to minimize the distance between distributions indirectly. The TV loss directly optimizes the expected multi-step acceptance length. By minimizing $1 - \text{overlap}$, the gradient specifically targets the tokens that determine if a sequence is accepted. Crucially, the TV loss gradient is "probability-proportional." It concentrates optimization effort on high-probability tokens. It ignores the long tail of the vocabulary to prevent wasting capacity on irrelevant tokens.

3. The Pre-RL Adaptation Strategy: The authors found that the mismatch between the draft and the backbone is minimal under rejection sampling. Therefore, you do not actually need to update the MTP heads during RL. Instead, a single, lightweight training phase using the e2e TV loss before RL begins is sufficient. This creates "entropy-invariant" draft heads that remain stable throughout the entire training run.

Stable acceleration across reasoning and agents

The empirical results suggest that this shift from "matching probabilities" to "maximizing overlap" has profound implications for throughput. The authors report that Bebop achieves up to 1.8× end-to-end acceleration in asynchronous RL training for Qwen3.5, 3.6, and 3.7 models. This means the total training time is cut nearly in half.

On a per-task basis, the gains are most visible in complex environments. The authors measure acceptance rate improvements of up to 8% on agentic and SWE-bench tasks using the e2e TV loss compared to the CE baseline [Table 2]. This helps ensure that the speedup remains consistent even as the task complexity grows. More importantly, while standard MTP acceptance rates crash as training progresses, the Bebop method maintains a remarkably stable acceptance length .

In terms of hardware utility, the paper reports up to 25% extra inference throughput gains across mathematical reasoning, code generation, and agentic tasks. This translates to significant wall-clock savings when scaling to hundreds of thousands of GPU hours. The authors also demonstrate that these gains scale with model size. Larger models reach acceptance rates as high as 95% [Table 3].

Limits of the entropy-invariant claim

There are two technical caveats that practitioners should note.

First, the "entropy invariance" claimed by the authors is conditional. The stability of the MTP heads depends on the draft model having enough capacity. It must cover the entropy range encountered during its pre-RL (SFT) training. If RL drives the policy into an extremely high-entropy regime, the draft heads may face out-of-distribution target distributions. In these edge cases, the entropy-acceptance relationship will return. Users might then need to resort to "online" MTP updates.

Second, the theoretical foundation relies on certain heuristic assumptions. These involve "mismatch structures," such as assuming errors are either uniform or probability-proportional. While the empirical evidence in strongly supports these models, the authors admit these are not formal proofs. A rigorous mathematician might demand a tighter bound on how a capacity-limited draft head behaves as the support size $|S_{eff}|$ grows exponentially with entropy.

The verdict: A practical recipe for RL scaling

If you are building large-scale RL pipelines for reasoning or agentic tasks, the Bebop paper provides a highly actionable recommendation: stop using greedy target-only sampling and switch to rejection sampling with a TV-optimized draft head.

The transition from CE/KL-based training to TV-based training is a rare success. A change in the objective function yields a direct improvement in throughput without requiring complex online synchronization. By decoupling MTP acceleration from the fluctuating entropy of the RL policy, Bebop turns a volatile speedup into a reliable constant. For anyone managing massive GPU clusters for post-training, this is a significant win. The code is reportedly available via the SGLang project; see the paper for the canonical link.

Figures from the paper