How does Medusa multi-head decoding accelerate inference without a separate draft model?

Short answer: Medusa adds multiple extra decoding heads on top of the base LLM's final hidden state to predict multiple future tokens ($t+1, t+2, \dots, t+k$) simultaneously in a single forward pass, verifying candidate token trees in parallel to achieve $2-3\times$ speedups without needing a separate draft model.

Detail

Standard speculative decoding requires hosting two distinct models in GPU memory: a small draft model (e.g. Llama-3-8B-Draft) and a target model (e.g. Llama-3-70B).

Medusa eliminates the separate draft model by attaching lightweight feed-forward heads directly to the base model:

Medusa Architecture:
Base LLM Backbone ──► Last Hidden State h_t ──┬──► Original Head ──► Predicts Token t+1
                                              ├──► Medusa Head 1 ──► Predicts Token t+2
                                              ├──► Medusa Head 2 ──► Predicts Token t+3
                                              └──► Medusa Head 3 ──► Predicts Token t+4

Key Innovations in Medusa

1. Single Model Memory Footprint: No VRAM is wasted hosting a secondary draft model.
2. Tree-Based Verification: Generates a tree of candidate token paths and evaluates them in parallel using a custom attention mask in 1 target model pass.
3. Parameter-Efficient Training: Medusa heads are trained on frozen base models using LoRA or simple MLP tuning.

Example

PyTorch conceptual forward pass of a Medusa multi-head architecture:

import torch
import torch.nn as nn

class MedusaModel(nn.Module):
    def __init__(self, base_lm_backbone, hidden_dim=4096, vocab_size=32000, num_heads=4):
        super().__init__()
        self.backbone = base_lm_backbone
        # Add N additional prediction heads
        self.medusa_heads = nn.ModuleList([
            nn.Linear(hidden_dim, vocab_size, bias=False) for _ in range(num_heads)
        ])

    def forward(self, input_ids):
        hidden_states = self.backbone(input_ids) # Single pass backbone
        # Output predictions for t+1, t+2, t+3, t+4 concurrently
        medusa_logits = [head(hidden_states) for head in self.medusa_heads]
        return medusa_logits

Interview tips

• Contrast Medusa with traditional Speculative Decoding: Medusa avoids model memory alignment issues and inter-model tokenizer mismatches.
• Highlight Tree Attention: verifying multiple speculative candidate branches simultaneously using FlashAttention masks.

Related Concepts

• [[How does vLLM PagedAttention manage Virtual Memory Pages to eliminate KV cache fragmentation?]] (#159): How does vLLM PagedAttention manage Virtual Memory Pages to eliminate KV cache fragmentation?
• [[How to lead an ambiguous AI system design interview from requirements to architecture?]] (#196): How to lead an ambiguous AI system design interview from requirements to architecture?

⬅ Back to AI System Design · All topics