LLMs Don't Have to Generate One Token at a Time: How Medusa and Multi-Token Prediction Cheat Autoregression

Hello, I'm Shrijith Venkatramana, and I'm building LiveReview — a blast-radius aware AI code review built for your business-critical systems. Star us to help devs discover the project, give it a try, and share your feedback to help improve the product.

A modern LLM can contain hundreds of billions of parameters, run on extremely expensive accelerators, and still spend most of its inference time doing something that looks embarrassingly sequential:

token 1 -> token 2 -> token 3 -> token 4 -> token 5 -> ...

That is the awkward part of autoregressive generation.

The model may process a whole prompt in parallel during the initial prefill, but once generation starts, the next token depends on the previous token. So generating 100 tokens looks conceptually like running the model 100 times.

And for many serving workloads, that is exactly where the money goes.

A family of techniques tries to break this bottleneck by asking a deceptively simple question:

What if the model could predict several future tokens at once, then verify them in parallel?

That idea leads to speculative decoding, Medusa-style multiple decoding heads, and the broader multi-token prediction approach used during training.

The interesting part is that these are not merely "optimization tricks." They change the computational structure of decoding.

This article develops that idea from first principles and then gets into the engineering details.

1. The problem: your GPU is doing an expensive sequential loop

Consider ordinary autoregressive decoding.

Given a prompt:

The capital of France is

the model predicts:

Paris

Then it feeds the new sequence back through the model:

The capital of France is Paris

and predicts the next token.

Then again:

The capital of France is Paris .

and so on.

Formally, the model factorizes the probability of a sequence as:

P(x1, x2, ..., xT)
    = product over t of P(xt | x1, ..., x(t-1))

That conditional dependence is what makes language modeling so useful.

It is also what makes decoding annoying.

Prefill is parallel; decode is sequential

This distinction matters enormously in production.

Suppose a prompt has 2,000 tokens and we want 200 generated tokens.

During prefill, the transformer can process many positions concurrently:

prompt tokens
     |
     v
parallel transformer computation
     |
     v
KV cache

During decoding:

token 2001
    |
    v
run model
    |
    v
token 2002
    |
    v
run model
    |
    v
token 2003
    |
    v
...

The transformer itself is highly parallelizable.

The dependency graph of generation is not.

This creates an unusual hardware situation. A giant model can spend much of its decoding time limited not by arithmetic throughput but by repeatedly moving a large set of model weights through memory.

This was one of the motivations behind the speculative decoding work by Yaniv Leviathan, Matan Kalman, and Yossi Matias, and later became a central observation in Medusa.

The core question is therefore not:

How do we make one forward pass cheaper?

It is:

How do we get more than one accepted token out of each expensive forward pass?

That is a much more interesting question.

2. The first big idea: speculate, then verify

Imagine that instead of asking the large model for one token, we had a tiny model that could cheaply guess several:

Big model:
"I need to generate the next token."

Small model:
"Here are my guesses:

  the -> capital -> of -> France
"

The big model can then evaluate those candidate tokens in parallel.

Suppose the small model proposes:

the capital of France

The large model might agree with all four:

the   ✓
capital ✓
of    ✓
France ✓

Great. One expensive evaluation effectively produced four tokens.

But perhaps the draft is:

the capital of Germany

and the large model says:

the       ✓
capital   ✓
of        ✓
Germany   ✗

Then we keep the accepted prefix and let the large model continue from the rejected position.

This is the basic idea of speculative decoding.

It is beautifully simple:

cheap model
    |
    | proposes several tokens
    v
candidate sequence
    |
    v
large model verifies them in parallel
    |
    +------> accept several
    |
    +------> reject at first disagreement

Leviathan et al. showed that this could accelerate generation while preserving the output distribution exactly, rather than merely producing "approximately similar" text.

Their 2023 paper reported roughly 2x-3x acceleration on the models they evaluated.

The crucial insight was that autoregressive generation does not mean the expensive model must discover every token sequentially. It only means that the final accepted sequence has to respect the autoregressive distribution.

Speculation lets us take advantage of the fact that many consecutive tokens are easy to predict.

For example:

for i in range(100):
    generate(next_token)

contains many stretches where the answer is nearly obvious:

"San" -> "Francisco"

or

"def" -> " foo" -> "("

or

"New" -> " York"

The large model is still being asked to perform the full computation, but we are trying to amortize that expensive computation across several tokens.

This idea naturally leads to the next question:

Why maintain a second model just to make guesses?

That is where Medusa becomes interesting.

3. Medusa: give the model several extra heads

Medusa, introduced by Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason Lee, Deming Chen, and Tri Dao, takes a different route.

Instead of:

large model + separate draft model

Medusa adds several lightweight decoding heads to the existing model.

Conceptually:

                    +--> head 1 --> token t+1
                    |
transformer trunk --+--> head 2 --> token t+2
                    |
                    +--> head 3 --> token t+3
                    |
                    +--> head 4 --> token t+4

The ordinary language-model head predicts:

P(x[t+1] | context)

A Medusa head can try to predict:

P(x[t+2] | context)

another:

P(x[t+3] | context)

and another:

P(x[t+4] | context)

The heads are cheap compared with running the entire transformer again.

So instead of doing this:

full model
    -> token t+1

full model
    -> token t+2

full model
    -> token t+3

full model
    -> token t+4

we try to do:

one full model pass
    |
    +--> head 1 -> candidates for t+1
    +--> head 2 -> candidates for t+2
    +--> head 3 -> candidates for t+3
    +--> head 4 -> candidates for t+4

The important subtlety is that these predictions are not independent in the final decoding procedure. Medusa uses a tree of candidate continuations and then asks the full model to verify the candidates together.

This is why "multi-token prediction" can sound simpler than it actually is.

The prediction is parallel.

The verification structure is the clever part.

4. Why a tree instead of one straight-line guess?

Suppose Medusa predicts three future positions, and we keep the top two candidates at each position.

Naively, we could have:

position 1: A, B
position 2: C, D
position 3: E, F

But not every combination is meaningful.

The structure is really:

             current context
              /           \
             A             B
           /   \         /   \
          C     D       C'    D'
         / \   / \     /  \   / \
        ... ... ...    ... ... ...

This is a candidate tree.

Why?

Because the second token depends on what happened at the first token.

If the first candidate is A, then predictions for later tokens are conditional on A.

If the first candidate is B, the continuation is different.

A tree therefore lets the system represent multiple possible future sequences without running the full model separately for every path.

This is the key engineering trick.

The transformer can process the tree-shaped set of candidate continuations with a specially constructed attention pattern.

Conceptually:

                   context
                      |
               +------+------+
               |             |
               A             B
             /   \         /   \
            C     D       E     F

The model verifies many of these positions in one batched computation.

This converts part of the problem from:

serial execution

into:

parallel evaluation of possible futures

That is exactly the kind of workload modern GPUs are good at.

A useful mental model

Think of ordinary decoding as exploring one path through a tree:

root -> A -> C -> F -> J -> ...

At every step you pay for another expensive model evaluation.

Medusa says:

Spend one expensive evaluation exploring a small local subtree, then keep the path that survives verification.

That is the entire game.

5. The math: speed comes from accepted tokens per step

The cleanest way to reason about these methods is with one quantity:

L = average number of tokens accepted per expensive model evaluation

Ordinary decoding has approximately:

L = 1

because one model evaluation produces one token.

Suppose a speculative or Medusa-style method gets:

L = 2.5

accepted tokens per verification step.

Then generating 100 tokens requires roughly:

100 / 2.5 = 40

large-model evaluations instead of:

100 / 1 = 100

That gives a first-order speedup of:

100 / 40 = 2.5x

But this is only the idealized calculation.

There is extra work:

head computation
candidate construction
tree attention
verification overhead
sampling
kernel launches

So a more realistic model is:

baseline time
    ~= N * T_model

accelerated time
    ~= (N / L) * (T_model + T_overhead)

and therefore:

speedup
    ~= L * T_model / (T_model + T_overhead)

This equation is worth remembering.

It explains why a method that achieves L = 3 does not necessarily deliver a literal 3x wall-clock improvement.

For example, suppose:

T_model    = 20 ms
T_overhead = 3 ms
L          = 3

Then:

speedup ~= 3 * 20 / 23
        ~= 2.61x

The accelerator is still doing extra work.

It is just doing substantially less serial expensive work.

Acceptance probability matters

Suppose we try to predict four future tokens, and the probability each prediction is accepted is roughly:

p = 0.8

A crude approximation for the probability of getting all four accepted is:

0.8^4 = 0.4096

So only about 41% of branches would survive all four positions.

But we do not actually need all four to succeed.

Getting:

token 1 ✓
token 2 ✓
token 3 ✓
token 4 ✗

is still useful.

The expected number of consecutive accepted tokens is approximately related to:

p + p^2 + p^3 + ... + p^K

for a K-token proposal horizon.

With:

p = 0.8
K = 4

that gives:

0.8 + 0.64 + 0.512 + 0.4096
= 2.3616

So even though all-four acceptance happens only about 41% of the time, we can still average roughly 2.36 accepted positions before considering the stop.

This is why improving head quality can be extremely valuable.

A relatively small increase in acceptance probability compounds across the sequence.

6. Multi-token prediction is also a training idea

Here is where terminology gets confusing.

"Multi-token prediction" can refer to an inference architecture, such as Medusa-style heads, but it can also mean a training objective.

Fabian Gloeckle and colleagues at Meta proposed training language models to predict multiple future tokens from the same shared representation.

Instead of only optimizing:

h_t -> x_(t+1)

the model can optimize several targets:

h_t -> x_(t+1)
h_t -> x_(t+2)
h_t -> x_(t+3)
h_t -> x_(t+4)

with separate output heads.

A simplified loss looks like:

L = L_1 + L_2 + L_3 + ... + L_K

where:

L_1 = cross_entropy(head_1(h_t), x_(t+1))
L_2 = cross_entropy(head_2(h_t), x_(t+2))
...

The trunk is shared.

That means one representation is being asked to encode information about several points in the future.

This turns out to have an interesting side effect: it can change what the network learns internally.

Gloeckle et al. reported improved downstream performance, especially on code-generation tasks. For their 13B models, the multi-token prediction setup improved results on HumanEval and MBPP relative to comparable next-token models, while also offering inference benefits.

That is an interesting departure from the usual story.

Usually we think:

extra training objective
        |
        v
same model quality
        |
        v
maybe cheaper inference

But multi-token prediction can potentially provide:

extra training signal
        |
        +--> better representations
        |
        +--> better downstream capability
        |
        +--> faster generation

So the technique is not merely a serving hack.

It can change the model's learning problem.

Why might predicting farther into the future help?

Consider code:

for user in users:
    print(user.name)

Knowing the immediate next token is useful.

But knowing what is likely to happen several tokens later gives the network a signal about longer local structure.

Predicting:

for
user
in
users

from the same representation forces the model to preserve information about syntactic continuation.

One interpretation is that this encourages representations that contain a more explicit local plan.

That interpretation fits the experiments in the paper, where the authors found evidence connecting multi-token prediction with the development of induction-head-like behavior and algorithmic reasoning on small tasks.

The deeper lesson is that next-token prediction is not the only useful training signal available in an autoregressive model.

7. What this means for an LLM serving engineer

The really useful question is not:

"Is Medusa clever?"

It is:

"When should I deploy something like this?"

The answer depends on the workload.

Case 1: latency-sensitive, batch size ~1

This is the strongest case.

Think:

interactive coding assistant
chat UI
agent tool call
voice response

If your user is waiting for tokens, reducing serial decode steps directly reduces time-to-completion.

Suppose your baseline server produces:

50 tokens/sec

and the workload typically generates:

150 tokens

That is approximately:

3 seconds

of decode time.

If a Medusa-style approach gets an effective 2x speedup, you're around:

1.5 seconds

before accounting for other system overhead.

That is a very meaningful product difference.

Case 2: huge batch sizes

Now the economics become less obvious.

Large batches already give the GPU more parallel work.

You may be trading:

fewer sequential iterations

against:

more candidate computation

and more complicated scheduling.

This is one reason the exact operating point matters.

A technique that is spectacular for:

batch size = 1

can have a much smaller payoff when the GPU is already saturated.

Interestingly, the multi-token-prediction experiments reported by Gloeckle et al. also found inference benefits at larger batch sizes, so the idea is not inherently limited to interactive serving.

The correct engineering approach is empirical benchmarking, not assuming that a published speedup transfers directly to your serving stack.

Case 3: model economics

Suppose you are paying roughly:

$4 / GPU-hour

for an accelerator.

A workload that consumes:

1,000 GPU-hours/month

costs roughly:

$4,000/month

If an optimization genuinely cuts required GPU-hours by 40%, the theoretical savings are:

$1,600/month

per equivalent GPU-hour workload.

At hyperscale, that becomes enormous.

But the real economic variable is not "speedup."

It is:

cost per generated token

You should measure:

GPU cost / accepted output token

under the actual workload distribution.

And this is where acceptance rate, sequence length, batching, KV-cache behavior, kernel efficiency, and scheduling all matter.

8. Medusa versus speculative decoding

The two approaches attack the same bottleneck from different directions.

Speculative decoding

large model
    ^
    |
verify
    ^
    |
small draft model
    |
propose many tokens

Advantages:

• No architectural modification to the target model.
• The draft model can be very cheap.
• Exact decoding can be preserved with the appropriate verification/sampling scheme.
• The idea works with existing pretrained models.

Costs:

• You need another model.
• You now have another model to load, serve, version, and optimize.
• The draft model must be sufficiently aligned with the target model to get a useful acceptance rate.
• You have two model execution paths to schedule.

Medusa

                    +--> head 1
                    |
large model trunk --+--> head 2
                    |
                    +--> head 3
                    |
                    +--> head 4

Advantages:

• No separate draft model.
• Additional heads are tiny relative to the backbone.
• Candidate proposals can be generated directly from the backbone's representation.
• The implementation is conceptually compact.

Costs:

• You generally need model-specific training or adaptation.
• Head quality can be weaker than that of a dedicated draft model.
• Verification requires tree-style machinery.
• Fine-tuning the whole backbone introduces additional concerns about preserving the original model's capabilities.

This is why Medusa introduced two variants.

Medusa-1 freezes the backbone and trains the new heads.

That is operationally attractive because the original model is essentially preserved.

Medusa-2 trains the backbone jointly with the new heads.

That can give better prediction quality and higher speedups, but the training procedure has to preserve the quality of the base model.

The published Medusa experiments reported more than 2.2x acceleration for Medusa-1 in their settings, while Medusa-2 reached roughly 2.3x-2.8x in the final ICML version.

Those numbers are useful as evidence that the approach works.

They should not be interpreted as a universal multiplier for every model and serving stack.

9. The deeper idea: turn serial computation into speculative parallelism

There is a broader systems principle hiding underneath all of this.

Modern hardware is extremely good at:

do many related things simultaneously

It is much worse at:

do one tiny thing
wait
do another tiny thing
wait
do another tiny thing

Autoregressive decoding creates exactly the second pattern.

Medusa and speculative decoding change the shape of the workload.

Instead of:

             ┌── expensive ──┐
context ---> │ model          │ ---> token
             └───────────────┘
                    |
                    v
             ┌── expensive ──┐
token ------>│ model          │ ---> token
             └───────────────┘
                    |
                    v
                  ...

we try to construct:

                    context
                       |
              candidate generation
                       |
          +------------+------------+
          |            |            |
         A             B            C
          |            |            |
          +------------+------------+
                       |
                parallel verification
                       |
                 accepted prefix

The model is no longer merely a function that maps:

context -> next token

for execution purposes.

We are treating it more like a machine that can cheaply explore a small neighborhood of possible futures.

That perspective opens several avenues.

You can vary:

number of prediction heads

You can vary:

number of candidate tokens per head

You can vary:

tree shape

You can dynamically allocate more candidates when the model is uncertain.

You can use different proposal models.

You can train models explicitly for longer-horizon prediction.

And you can combine these approaches.

The common theme is always the same:

Spend one expensive model evaluation to obtain more than one useful token.

10. A practical way to think about deploying it

For an engineer evaluating one of these systems, I would start with five measurements.

1. Baseline decode latency

Measure:

milliseconds / generated token

at the actual:

batch size
prompt length
sequence length
quantization
GPU

you care about.

2. Acceptance statistics

Measure:

average accepted tokens / verification step

rather than merely reporting the number of heads.

Four heads with:

L = 1.2

may be much worse than three heads with:

L = 2.4

3. Verification overhead

Measure:

candidate generation
tree construction
attention
sampling
synchronization

separately.

Otherwise it is easy to mistake a benchmark micro-optimization for an end-to-end improvement.

4. Cost per token

Measure:

GPU-seconds / accepted output token

rather than just:

tokens / second

A server that is 20% faster but requires 30% more GPU capacity may not actually be an improvement.

5. Quality preservation

This is particularly important for Medusa-style adaptation.

You care about:

base-model quality

and:

accelerated-model quality

separately.

A speedup obtained by quietly changing the generation distribution is a different trade-off from exact speculative decoding.

That distinction should be explicit in your architecture review.

11. Wrapping Up

At first glance, autoregressive generation appears fundamentally sequential:

token t
  -> token t+1
       -> token t+2
            -> token t+3

But that is only the structure of the final dependency.

It does not necessarily mean we have to perform one expensive full-model computation for every final token.

Speculative decoding exploits this with another model.

Medusa exploits it with additional decoding heads and tree verification.

Multi-token prediction attacks the problem earlier, at training time, by teaching the network to predict several future tokens from shared representations.

These techniques point toward a broader shift in how we think about LLM inference.

The interesting question is no longer simply:

"How fast can I run one forward pass?"

It is:

"How much useful sequential progress can I extract from one forward pass?"

That is a much richer optimization problem.

And arguably, it is one of the more important ones in LLM systems engineering because the transformer has become so large that shaving milliseconds from a single operation is often less interesting than reducing how many times we need to perform the expensive operation in the first place.

For developers building inference infrastructure, agents, coding assistants, or high-volume generation systems, that distinction can translate directly into latency, GPU utilization, and dollars.

The next time you see an LLM generating 100 tokens one by one, it is worth asking:

What if those 100 tokens only required 40 expensive model evaluations?

That is essentially the game Medusa is playing.

Your team's attention is limited, and the deluge of AI-generated code is making it harder to keep production stable while also shipping at high velocity.