💬 NLP

EntMTP: Accelerating LLM Inference with Entropy Guided Multi Token Prediction

EntMTP is a training-free scheduler that dynamically adjusts multi-token prediction depth based on local generation entropy to maximize inference throughput while maintaining output quality, achieving up to a 1.36x speedup over existing baselines.

Original authors: Carrie Chen

Published 2026-06-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Carrie Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to write a story, but you have a very strict rule: you can only write one word at a time, and after every single word, you have to stop, double-check your entire life's work to make sure that word is perfect, and then move on. This is how current Large Language Models (LLMs) usually work. It's incredibly accurate, but it's also painfully slow because you're constantly stopping to check your work.

To speed this up, researchers invented a trick called Multi-Token Prediction (MTP). Instead of writing one word and checking, the model tries to guess the next three or four words all at once, like a draft. Then, it does one big "check" to see how many of those guesses were right. If it guessed three words correctly, it saves a lot of time.

However, the paper EntMTP points out a flaw in how this trick is currently used.

The Problem: The "One-Size-Fits-All" Mistake

Currently, models use a static strategy. Imagine you are driving a car. The current method says: "No matter if you are driving on a smooth highway or a bumpy dirt road, you must always keep your foot on the gas pedal at the exact same speed and look exactly 100 feet ahead."

On a smooth highway (low entropy): The road is predictable. You could safely look 100 feet ahead and guess the next few turns perfectly.
On a bumpy dirt road (high entropy): The road is chaotic. Looking 100 feet ahead is a waste of time because you might hit a pothole or a deer. You should only look a few feet ahead and drive cautiously.

Existing models (like Hydra and Medusa) pick one "look-ahead distance" (a specific tree shape) before they start and stick with it forever. This is inefficient. Sometimes they guess too far ahead and waste energy; other times they guess too little and miss a chance to speed up.

The Solution: EntMTP (The Smart Co-Pilot)

The authors propose EntMTP (Entropy-guided Multi-Token Prediction). Think of this as a smart co-pilot that constantly checks the road conditions and tells the driver how far to look ahead.

Reading the "Entropy" (The Road Conditions):
The model constantly measures how "surprising" the next words are.
- Low Entropy (Predictable): The text is flowing smoothly (e.g., "The sun rises in the..."). The co-pilot says, "Easy! Let's guess the next 4 words!"
- High Entropy (Chaotic): The text is tricky or complex (e.g., a difficult math problem or a sudden plot twist). The co-pilot says, "Whoa, this is risky. Let's only guess the next 1 word to be safe."
The "Tree Bank" (The Toolkit):
Before the model even starts writing, the researchers prepare a small "bank" of different guessing strategies (trees). Some are big and aggressive (guessing many words), and some are small and conservative (guessing few words).
- Crucially, they don't just pick one. They create a menu of the best options for different situations.
The Switch (The Gear Shift):
During the writing process, EntMTP acts like a gear shifter.
- If the text is easy, it shifts into High Gear (the big tree) to zoom ahead.
- If the text gets hard, it instantly shifts into Low Gear (the small tree) to avoid crashing.
- The Magic: Switching gears takes almost zero time. It's just a quick pointer swap in the computer's memory, not a heavy rebuild.

The Results: Faster Without Losing Quality

The paper tested this new "Smart Co-Pilot" on three very different types of tasks:

Coding (HumanEval): Writing computer programs.
Math (GSM8K): Solving grade-school math problems.
Chatting (ShareGPT): Having a conversation.

The Outcome:

Speed: EntMTP was consistently 9% to 15% faster than the previous best methods (Hydra). In some cases, it was 36% faster than older methods.
Quality: Because the model still checks its work perfectly, the quality of the writing didn't drop at all. It's like driving faster but arriving at the exact same destination with the same safety.
Efficiency: It achieved this speedup not by making the computer stronger, but by making the computer smarter about when to guess far ahead and when to be careful.

The Bottom Line

Think of the old way as a runner who sprints at full speed for 100 meters, stops to tie their shoe, sprints 100 meters, stops again, regardless of whether the track is flat or full of hurdles.

EntMTP is the runner who looks at the track. If it's flat, they sprint hard. If they see a hurdle coming, they slow down just enough to step over it safely, then immediately sprint again. This allows them to finish the race much faster without tripping.

Technical Summary: EntMTP

Problem Statement

Large Language Models (LLMs) face a significant latency bottleneck due to the sequential nature of autoregressive decoding, where each token generation requires a full forward pass through all model parameters. While Speculative Decoding addresses this by drafting candidate tokens with a cheaper model and verifying them in parallel, Multi-Token Prediction (MTP) approaches like Medusa and Hydra integrate this capability directly into the target model via lightweight heads, eliminating the need for a separate draft model.

However, existing MTP implementations (e.g., Hydra) rely on a static tree-based attention topology. This means the speculation depth and the computational cost for verification remain constant throughout the entire generation sequence, regardless of the context. The authors argue this is fundamentally misaligned with the entropy patterns of natural language:

Low-entropy regions (highly predictable) support reliable multi-step drafting and benefit from deeper trees.
High-entropy regions (unpredictable) require conservative speculation to avoid wasted verification cycles.

Furthermore, the optimal tree topology is task-specific. A topology that is Pareto-optimal for one benchmark (e.g., code generation) may be suboptimal for another (e.g., conversational dialogue), yet current methods often select a single global topology offline.

Methodology: EntMTP

The paper proposes EntMTP (Entropy-guided Multi-Token Prediction), a training-free scheduler that dynamically toggles between different tree-based attention topologies based on a running estimate of local generation entropy. The system operates in two phases:

1. Offline: Constructing the Throughput-Pareto Frontier

Instead of selecting a single static tree, EntMTP builds a bank of task-specific, Pareto-optimal trees:

Greedy Construction: Using a self-rollout procedure on a calibration set, the system greedily constructs a sequence of proposal trees of increasing size. It scores candidate trees based on mean acceptance length, breaking ties by preferring shallower depths and smaller child-rank sums.
Recalibration: To correct for optimistic bias in the initial scoring (where candidates are scored against a larger joint tree), the frontiers are recalibrated against a canonical Hydra self-rollout using each candidate's specific proposal and attention mask.
Throughput Evaluation: The system evaluates the entire acceptance frontier end-to-end on the target workload, measuring wall-clock output tokens per second. This identifies a "Throughput-Pareto bank" ( $B = \{T_1, \dots, T_K\}$ ) of trees that offer the best cost-throughput tradeoffs for that specific task.

2. Online: Inference-Time Tree Scheduler

At runtime, EntMTP selects the optimal tree from the precompiled TopologyBank for each decode step without reconstructing masks or rebuilding kernels (switching is an $O(1)$ pointer swap).

Feature Input: The scheduler consumes off-the-shelf features from the model, specifically the EAGLE-2 path value (derived from the base LM's top-1 probability and the Hydra heads' top-1 probabilities). This scalar $s$ represents the best path value and correlates monotonically with the expected acceptance length.
Selection Policies: The paper introduces three policies to map the feature $s$ $s$ to a tree index:
- ENTMTP∗: A static rule selecting the single task-optimal tree.
- ENTMTP-l: A threshold ladder that bins $s$ into $K$ intervals, selecting different trees for different confidence levels.
- ENTMTPτ: A hysteretic binary rule using separate "on" ( $\tau_{on}$ ) and "off" ( $\tau_{off}$ ) thresholds. This switches between a conservative (small/shallow) tree and an aggressive (large/deep) tree, preventing per-step jitter during entropy fluctuations.

Key Contributions

Identification of Task-Dependence: The paper demonstrates that acceptance behavior and throughput frontiers are highly workload-dependent, invalidating the use of a single global topology for diverse tasks.
Training-Free Dynamic Scheduling: EntMTP introduces a runtime scheduler that adapts speculation depth to local context predictability without requiring additional model training or fine-tuning.
Efficient Implementation: The system achieves dynamic switching with negligible overhead (<0.1 ms per step) by utilizing precompiled attention masks and position offsets, reducing the switching cost to a simple pointer swap.
Lossless Acceleration: The method preserves the exact target distribution, ensuring that gains in speed do not come at the cost of generation quality (perplexity remains within 0.02 nats of the base model).

Results

Evaluated on HumanEval, ShareGPT, and GSM8K benchmarks using Vicuna-7B, EntMTP consistently outperforms existing baselines:

vs. Hydra: EntMTP achieves a 1.09–1.15x speedup over the Hydra default. The dynamic scheduler (ENTMTPτ) yields the best results, reaching 124.7 tok/s on HumanEval (+14.0% over Hydra) and 117.5 tok/s on ShareGPT (+7.8% over Hydra).
vs. Medusa: EntMTPτ achieves a peak speedup of ~1.36x over Medusa baselines.
vs. Autoregressive (AR): EntMTPτ provides a 3.13x to 3.47x speedup over vanilla autoregressive decoding across all benchmarks.
Efficiency: The dynamic scheduler (ENTMTPτ) adds a marginal 0.5–2.1% improvement over the static task-optimal tree (ENTMTP∗), with the largest gains observed on GSM8K where mixing conservative trees during high-entropy reasoning steps recycles verifier cycles.

Significance

The paper claims that EntMTP represents a significant step forward in speculative decoding by aligning the speculation depth with the inherent predictability of the generated text. By moving away from static, one-size-fits-all topologies to a context-aware, entropy-guided approach, EntMTP maximizes the expected accepted-token throughput across the full distribution of generated text. The work demonstrates that significant latency reductions can be achieved through intelligent scheduling of existing MTP architectures without compromising the fidelity of the generated output.