See also: transformers from scratch

see also: AI and Memory Wall (Gholami et al., 2024)

"How is LLaMa.cpp possible?"
great post by @finbarrtimbers https://t.co/yF43inlY87

llama.cpp surprised many people (myself included) with how quickly you can run large LLMs on small computers, e.g. 7B runs @ ~16 tok/s on a MacBook. Wait don't you need supercomputers to work… pic.twitter.com/EIp9iPkZ6x

— Andrej Karpathy (@karpathy) 15 août 2023

Arithmetic intensity can be determined with the following:

Either compute-bound (batch inference, saturated usage) or memory-bound (latency)

• url: thoughts/PD-disaggregated-serving
• description: Prefill/Decode

Prefill/Decode

Lien vers l'original

• url: thoughts/Speculative-decoding

Speculative decoding

Idea: “draft-and-verify” using smaller models to generate a head tokens (quick explanation from karpathy)

Intuitively:

• we generate a small set of lookahead tokens, albeit 2-5 tokens with smaller speculators
• uses the larger model to “verify” the input sequences + draft tokens (then replace tokens that aren’t valid from rejection sampler)

In a sense, we are verify these in parallel instead of autoregressive decoding.

A few techniques such as ngrams, EAGLE are supported in vLLM

EAGLE

Extrapolation Algorithm for Greater Language-model Efficiency

• EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test (Li et al., 2025)
• EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees (Li et al., 2024)
• EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty (Li et al., 2025a)

Motivation:

• speculative sampling relies on the draft models having similar distributions as the target models.
  • use smaller models. i.e: Llama 3.2 3B as draft for Llama 3.3 70B.
  • high overhead for stepping through the whole models would outweighs the benefits

Difference between EAGLE-1 and EAGLE-3

• EAGLE-1’s limitation at its feature prediction constraints, via LM head architecture,
• EAGLE-3 addresses this by use direct token prediction and rely on multi-layer feature fusion called “training-time test”, similar to MLP Speculator

distribution skew

EAGLE does not involve any fine-tuning of the target model, therefore preservation of outputs distributions by EAGLE is theoretically guaranteed for both greedy and non-greedy sampling. This is not the case with Lookahead and Medusa.

EAGLE-1

Observations:

autoregressive on feature-level ¹ is simpler than token-level, given that there are more regularity.

uncertainty in sampling process hinders the performance of predicting the next feature.

feature-level are high-dimensional and continuous, meaning sampling “am” or “always” will results in different feature sequences.

EAGLE address this by inputs the token sequence from one time step ahead including the sampling outcomes into the draft models.

• predicting $f_{\text{always}}$ based on $f_{\text{I}}$ and $t_\text{always}$
• predicting $f_{\text{am}}$ based on $f_{\text{I}}$ and $t_\text{am}$

notation.

• “Features” refers to second-to-top-layer feature of LLM, or the hidden states before LM head
• Token by $t$, embedding by $e$, features by $f$, distributions by $p$
• Sequences are referred as $T_{i:j}$ for $(t_i, t_{i+1},\ldots, t_j)$ ²

architecture

• [feature_seq, token_seq] # [bs, seq_len, hidden_dim], [bs, seq_len]
• token_seq -> token_emb # [bs, seq_len] -> [bs, seq_len, hidden_dim]
• fused_seq = feature_seq * token_emb # [bs, seq_len, 2xhidden_dim] ³
• autoregressive_head:
  • FC layer → reduce # [bs, seq_len, hidden_dim]
  • decoder layer → features
• using tree attention to generate a draft tree of depth $m$ and more than $m$ tokens for $m$ forward pass. ⁴

training

• Smooth L1 loss:

  $$L_\text{reg} = \text{Smooth L1}(f_{i+1} \text{draft}(T_{2:i+1}, F_{1:i}))$$

• classification loss to optimize given objectives:

  $$\begin{aligned} p_{i+2} &= \text{Softmax}(\text{LM\_Head}(f_{i+1})) \\ \hat{p}_{i+2} &= \text{Softmax}(\text{LM\_Head}(\hat{f}_{i+1})) \\ L_{\text{cls}} &= \text{CrossEntropy}(p_{i+2}, \hat{p}_{i+2}) \end{aligned}$$

• Autoregressive head with loss $L = L_{\text{reg}} + w_{\text{cls}} L_{\text{cls}}$

  • set $w_{\text{cls}}=0.1$ given that classification loss is in order magnitude bigger than regression loss

• Dataset: ShareGPT, 68k dialogue

• Hyperparameter:

  • LR: $3e^{-5}$
  • AdamW with beta $(\beta_1, \beta_2)=(0.9,0.95)$
  • gradient clipping: $0.5$

EAGLE-2

tl/dr: Improvement on EAGLE-1 via context-aware dynamic draft tree into this drafting modeling.

EAGLE-3

HASS

Learning Harmonized Representations for Speculative Sampling (Zhang et al., 2025)

HArmonizedSS/HASS

Falcon

Falcon: Faster and Parallel Inference of Large Language Models through Enhanced Semi-Autoregressive Drafting and Custom-Designed Decoding Tree (Gao et al., 2025)

MLP Speculator

via combined tokens/embedding speculators

Accelerating Production LLMs with Combined Token/Embedding Speculators (Wertheimer et al., 2024)

DistillSpec

DistillSpec: Improving Speculative Decoding via Knowledge Distillation (Zhou et al., 2024)

Medusa

https://sites.google.com/view/medusa-llm

FasterDecoding/Medusa

ngrams

apoorvumang/prompt-lookup-decoding

also known as Prompt Lookup Decoding (PLD), HF’s assisted generations

idea: to use string matching from prompt to generate candidate tokens, instead of using a draft-based models.

def find_candidate_pred_tokens(input_ids, max_ngram_size=3, num_pred_tokens=10):
  input_length = input_ids.size(1)
 
  for ngram_size in range(max_ngram_size, 0, -1):
    # Extract the last n tokens as our search ngram
    ngram = input_ids[0, -ngram_size:].tolist()
 
    # Create sliding windows of size ngram_size
    windows = input_ids.unfold(dimension=1, size=ngram_size, step=1)
 
    # Convert ngram to a tensor for comparison
    ngram_tensor = torch.tensor(ngram, device=input_ids.device).unsqueeze(0)
 
    # Find where the windows match the ngram
    matches = (windows == ngram_tensor).all(dim=2)
 
    # Get the indices of matches
    match_indices = matches.nonzero(as_tuple=True)[1]
 
    # Iterate through match indices to find a valid continuation
    for idx in match_indices:
      start_idx = idx + ngram_size
      end_idx = start_idx + num_pred_tokens
      # Ensure we don't go beyond the length of input_ids and avoid self-match
      if end_idx <= input_length and start_idx < input_length - ngram_size:
        return input_ids[0, start_idx:end_idx]
 
  # If no match is found, return an empty tensor
  return torch.tensor([], dtype=torch.long, device=input_ids.device)

lookahead decoding

see also: LMSYS blog,

SPiRE

MagicDec

---

optimization

Optimizing Speculative Decoding for Serving Large Language Models Using Goodput (Liu et al., 2024) optimizes via goodput.

Dynamic Speculation Lookahead Accelerates Speculative Decoding of Large Language Models (Mamou et al., 2024) focuses on dynamic speculative length.

speculative sampling

aliases: SpS, speculative decoding.

Based on:

• Fast Inference from Transformers via Speculative Decoding (Leviathan et al., 2023) ⁵
• Blockwise Parallel Decoding for Deep Autoregressive Models (Stern et al., 2018)
• Accelerating Large Language Model Decoding with Speculative Sampling (Chen et al., 2023)
• vllm/v1/sample/rejection_sampler.py

tl/dr

• Latency is improved at the cost of increasing ops, meaning 2x-3x with T5, with a scale of $\gamma=5$ (also referred in practice as num_speculative_tokens)
• This is not useful when computation resources are limited.
• Walltime improvement by $\frac{1-\alpha^{\gamma +1}}{(1-\alpha)(\gamma c + 1)}$ where $\alpha$ is the approximation $E(\beta)$ (or natural measure of the acceptance rate $\beta$)
• Note that this is different from rejection sampling ⁶, given that non-iterative rejection sampling would yield lower acceptance rate
• Lenience factor $l$ to perform speed versus quality trade-off ⁷ when draft-models distributions is different from target-models’. Note that we can’t use temperature=0 (i.e argmax sampling).
  • Instead we allow some lenience before standardizing the distribution (accept token $x$ sampled from $M_q$ in case of $p(x) \le l \dot \max{p}$)
  • In this case, then similar empirical increases to $\alpha$ to those of temperature=1

goal and algorithm

Let $M_p$ be the target model for task $X$, and $p(x_t \mid x_{<t})$ the distribution we get from model for a prefix $x_{<t}$

Let $M_q$ be the draft/approximation models at the same task, and $q(x_t \mid x_{<t})$ the distribution we get from model for a prefix $x_{<t}$

Objective: to use $M_q$ to generate $\gamma \in \mathbb{Z}^{+}$ completions, and use $M_p$ to verify $\gamma$ tokens in parallel

• Keep when $q(x) \le p(x)$
• Reject when $q(x) \ge p(x)$ for sample with $P=1-\frac{p(x)}{q(x)}$ and sample $x$ again from $p^{'}(x) = \textit{norm}(\textit{max}(0, p(x) - q(x)))$ ⁸

$"\\begin{algorithm}\n\\caption{SpeculativeDecodingStep}\n\\begin{algorithmic}\n\n\\INPUT{$M_p,\\;M_q,\\;\\textit{prefix}$}\n\n\\State $\\triangleright$ Sample $\\gamma$ guesses $x_1,\\dots,x_\\gamma$ from $M_q$\n\\FOR{$i \\gets 1$ \\TO $\\gamma$}\n \\STATE $q_i(x) \\gets M_q\\!\\bigl(\\textit{prefix} + [x_1,\\dots,x_{i-1}]\\bigr)$\n \\STATE $x_i \\sim q_i(x)$\n\\ENDFOR\n\n\\State $\\triangleright$ Run $M_p$ in parallel\n\\STATE $p_1(x),\\dots,p_{\\gamma+1}(x) \\gets\n M_p(\\textit{prefix}),\\dots,\n M_p\\!\\bigl(\\textit{prefix} + [x_1,\\dots,x_\\gamma]\\bigr)$\n\n\\State $\\triangleright$ Determine the number of accepted guesses $n$\n\\STATE $r_1,\\dots,r_\\gamma \\sim U(0,1)$\n\\STATE $n \\gets \\min\\!\\bigl(\\{\\,i-1 \\mid\n 1\\le i\\le\\gamma,\\;\n r_i > \\frac{p_i(x)}{q_i(x)}\\,\\}\\cup\\{\\gamma\\}\\bigr)$\n\n\\State $\\triangleright$ Adjust $M_p$’s distribution if needed\n\\STATE $p'(x) \\gets p_{n+1}(x)$\n\\IF{$n < \\gamma$}\n \\STATE $p'(x) \\gets \\mathrm{norm}\\!\\bigl(\\max\\!\\bigl(0,\\;\n p_{n+1}(x)-q_{n+1}(x)\\bigr)\\bigr)$\n\\ENDIF\n\n\\State $\\triangleright$ Emit one token from $M_p$ and $n$ from $M_q$\n\\STATE $t \\sim p'(x)$\n\\RETURN $\\textit{prefix} + [x_1,\\dots,x_n,t]$\n\n\\end{algorithmic}\n\\end{algorithm}"$

Algorithm 4 SpeculativeDecodingStep

Input: $M_p,\;M_q,\;\textit{prefix}$

$\triangleright$ Sample $\gamma$ guesses $x_1,\dots,x_\gamma$ from $M_q$

for $i \gets 1$ to $\gamma$ do

$q_i(x) \gets M_q\!\bigl(\textit{prefix} + [x_1,\dots,x_{i-1}]\bigr)$

$x_i \sim q_i(x)$

end for

$\triangleright$ Run $M_p$ in parallel

$p_1(x),\dots,p_{\gamma+1}(x) \gets M_p(\textit{prefix}),\dots, M_p\!\bigl(\textit{prefix} + [x_1,\dots,x_\gamma]\bigr)$

$\triangleright$ Determine the number of accepted guesses $n$

$r_1,\dots,r_\gamma \sim U(0,1)$

$n \gets \min\!\bigl(\{\,i-1 \mid 1\le i\le\gamma,\; r_i > \frac{p_i(x)}{q_i(x)}\,\}\cup\{\gamma\}\bigr)$

$\triangleright$ Adjust $M_p$’s distribution if needed

$p'(x) \gets p_{n+1}(x)$

if $n < \gamma$ then

$p'(x) \gets \mathrm{norm}\!\bigl(\max\!\bigl(0,\; p_{n+1}(x)-q_{n+1}(x)\bigr)\bigr)$

end if

$\triangleright$ Emit one token from $M_p$ and $n$ from $M_q$

$t \sim p'(x)$

return $\textit{prefix} + [x_1,\dots,x_n,t]$

acceptance probability

alias: acceptance rate

definition 3.1

acceptance rate $\beta_{x<t}$ given a prefix $x_{<t}$ is the probability of accepting $x_t \sim q(x_t\mid x_{<t})$ via speculative sampling.

$E(\beta)$ is the natural measure of how well $M_q$ approximates $M_p$

$\alpha = E(\beta)$ assuming $\beta$ are i.i.d, (1) is a capped geometrics variables, with success probability of $1 - \alpha$ and cap $\gamma + 1$:

$$E(\text{\# generated tokens}) = \frac{1-\alpha^{\gamma +1}}{1-\alpha}$$

calculating $\alpha$

definition 3.2

Let natural divergence $D_{LK}$ be:

$$D_{LK}(p,q) = \sum_{x} |p(x) - M(x)| = \sum_{x} \mid q(x) - M(x) \mid$$

where $M(x) = \frac{p(x) + q(x)}{2}$

Lemma 3.3

$D_{LK}(p,q) = 1 - \sum_{x} \min{p(x), q(x)}$ ⁹

Corollary 3.4

$D_{LK}(p,q)$ is a symmetric divergence in $[0,1]$, where

$D_{LK}(p,q)=0 \Longleftrightarrow p=q$

$D_{LK}(p,q)=1 \Longleftrightarrow \text{p and q have disjoint support}$

Theorem 3.5

$\beta = 1 - D_{LK}(p,q)$ ¹⁰

Corollary 3.6

$\alpha = 1 - E(D_{LK}(p,q)) = E(min(p,q))$

walltime improvement

With i.i.d assumption speculative sampling reduces $\text{\# of calls}$ to target models by $\frac{1-\alpha^{\gamma +1}}{1-\alpha }$, assuming running on compute resources that support increased concurrency (GPUs.)

For walltime ¹¹ analysis, assuming we can run $\gamma +1$ concurrent evaluation of $M_p$:

cost-efficient

let $c$ be the ratio between time for single run of $M_q$ and the time for single run $M_p$

$c$ is highly dependent on hardware measure. From the paper, $c \approx 0$ to avoid expectancy biases

Theorem 3.8

expected improvement factor in total walltime by $\frac{1-\alpha^{\gamma +1}}{(1-\alpha)(\gamma c + 1)}$ ¹²

Note that we assume there are long enough generations sequence here.

Corollary 3.9

$\forall \alpha > c \space \exists \space \gamma \mid \text{ we will get improvement by a factor of } \frac{1+\alpha }{1+c}$

If we get an improvement for $\gamma$, we’d also get improvement for any $0 < \gamma^{*} < \gamma$, hence we can use (3.8) for $\gamma = 1$, which yields $\frac{1+\alpha}{1+c}$

arithmetic operations

arithmetics operations per token

let $\hat{c}$ be the ratio of arithmetics operations per tokens of $M_q$ to that of $M_p$

Note that the number of operations will then grow by $\gamma +1$, given that we will produce at most $\gamma +1$ tokens per run.

Theorem 3.11

The expected factor of increase in number of operations is $\frac{(1-\alpha)(\gamma \hat{c} + \gamma + 1)}{1-\alpha^{\gamma +1}}$ ¹³

Lien vers l'original

KV

The core “retrieval” bags that contains all previous stored key-value pair or newly added items.

Prefill disaggregation is pretty interesting in a sense that we can separate prefill stage to a separate nodes (Qin et al., 2024)

Question

Why do we need to use KV Cache?

multi-token prediction.

(Gloeckle et al., 2024)

tl/dr: predict $n$-tokens at once, via shared trunk and n dedicated attention heads ¹⁴

Note that during inference, we only employ one attention head

idea: learn from raw-bytes and skip tokenizer/detokenizer protocol.

Let $\mathcal{V}$ be the vocab of given transformers model, and $\mathcal{S} = \mathcal{V}^{*}$ the set of multi-token strings. Assume $\mathcal{V}$ contains token EOS and write $\mathcal{F} \subseteq \mathcal{S}$ for the set of EOS-terminated strings.

Feynman-Kac Transformer model

is a tuple $(s_{0}, \{M_t\}_{t\ge 1}, \{G_t\}_{t\ge 1})$ where:

• $s_{0} \in \mathcal{S}$ is an initial state, which will take as empty string $\epsilon$
• $M_t(s_t \mid s_{t-1}, f_\theta)$ is a Markov kernel from $s_{t-1} \in \mathcal{F}^c$ to $s_t \in \mathcal{S}$, parameterised by a transformer network $f_\theta: \mathcal{F}^c \to \mathbb{R}^{\mid \mathcal{V} \mid}$ mapping non-EOS-terminated strings to vectors of logits
• $G_t(s_{t-1}, s_t, f_\theta)$ is a potential function, mapping a pair $(s_{t-1}, s_t) \in \mathcal{F}^c \times \mathcal{S}$ to a real-valued non-negative score.

Goal: generate from distribution $\mathbb{P}$ that reweights Markov chain $\mathbb{M}$ by potential functions $G_t$. We define step-t filtering posteriors:

Given that $T$ is mostly finite we can then define overall posterior (Lew et al., 2023, p. see 2.2 for examples)