Speculative decoding — Hinglish notes

6.1.12 · AI-ML › Scaling & Efficient Architectures

The Sequential Generation Bottleneck

WHAT is the problem?

Standard autoregressive generation ek time par ek token produce karta hai:

p (x_{t} ∣ x_{< t}) = softmax (W_{out} h_{t})

Length $T$ ki ek sequence ke liye, iska matlab hai $T$ sequential forward passes. Har pass:

Memory se model weights load karta hai (billions of parameters)
Latency memory bandwidth se dominate hoti hai, FLOPs se nahi
Sequence dimension ke across parallelize nahi ho sakta

The inefficiency: Modern GPUs ke paas teraflops of compute hai, lekin zyada time memory I/O ke wait mein jaata hai. Model tokens ke beech "idle" rehta hai.

How Speculative Decoding Works

The Two-Model Setup

Draft model $M_{q}$ : Chhota, fast model (e.g., 1B parameters, target se distilled)
Target model $M_{p}$ : Bada, slow model (e.g., 70B parameters, jo hume actually chahiye)

Key property: $M_{q}$ per token 5-10× faster hai lekin thoda kam accurate hai.

The Algorithm (Step-by-Step)

Formula Speculative Decoding Protocol

Input: Prefix $x_{< t}$ , draft model $M_{q}$ , target model $M_{p}$ , lookahead $K$

Step 1: Draft phase (parallel speculation)

For i = 0 to K-1:
    x̃_{t+i} ~ q(· | x_{<t+i})  # Sample from draft model

$K$ candidate tokens generate karta hai: $\tilde{x}_{t}, \tilde{x}_{t + 1}, \dots, \tilde{x}_{t + K - 1}$ Step 2: Verification phase (single parallel pass)

Target model ko $[x_{< t}, \tilde{x}_{t}, \tilde{x}_{t + 1}, \dots, \tilde{x}_{t + K - 1}]$ par run karo
Probabilities lo: $p (\cdot ∣ x_{< t + i})$ for $i = 0, \dots, K - 1$ Step 3: Acceptance sampling Har candidate $\tilde{x}_{t + i}$ ke liye order mein:

Accept with probability: min(1, p(x̃_{t+i} | x_{<t+i}) / q(x̃_{t+i} | x_{<t+i}))
If rejected:
    Resample from adjusted distribution: max(0, p - q) / Z
    Break (reject all subsequent candidates)
If all accepted:
    Sample bonus token from p(· | x_{<t+K})

WHY this works:

Lossless: Acceptance sampling ensure karta hai ki output distribution exactly $M_{p}$ akele se match kare
Fast: Jab draft sahi ho (often 60-80% tokens), hum ek pass mein $K$ tokens accept kar lete hain
Bounded: Worst case sab kuch reject karna hai = standard decoding jaisa hi (koi slowdown nahi)

Derivation of Acceptance Criterion

Goal: Proposals from draft $q (x)$ use karke target distribution $p (x)$ match karo.

Rejection sampling se shuru karo:

$\tilde{x} \sim q (x)$ sample karo
Probability $α = min (1, p (\tilde{x}) / q (\tilde{x}))$ se accept karo

WHY this gives $p (x)$ :

P (accept x) = q (x) \cdot \frac{p ( x )}{q ( x )} = p (x) when p (x) \leq q (x)

Jab $p (x) > q (x)$ , hum probability $1 - p (x) / q (x)$ se reject karte hain aur yahan se resample karte hain:

p_{resample} (x) = \frac{max ( 0 , p ( x ) - q ( x ))}{\int max ( 0 , p ( y ) - q ( y )) d y}

Combined distribution:

P_{final} (x) = q (x) min (1, \frac{p ( x )}{q ( x )}) + (1 - y \sum q (y) min (1, \frac{p ( y )}{q ( y )})) \cdot p_{resample} (x) = p (x)

Math guarantee karta hai ki output exactly target model se match kare.

Worked Example: 4-Token Speculation

| Position | Draft Token | $q$ (draft) | $p$ (target) | Accept? | |----------|-------------|------------|------| | t | "Par" | 0.7 | 0.8 | ✓ (min(1, 0.8/0.7) = 1) | | t+1 | "is" | 0.5 | 0.6 | ✓ (min(1, 0.6/0.5) = 1) | | t+2 | "," | 0.4 | 0.2 | ✗ (min(1, 0.2/0.4) = 0.5, coin flip fails) |

Outcome:

"Par" aur "is" accept karo (ek target pass mein 2 tokens!)
"," reject karo aur position t+2 par $max (0, p - q)$ distribution se resample karo
Probably "." sample hoga (jiska $p = 0.5, q = 0.1$ tha)
Final: 1 draft pass + 1 target pass se 3 tokens generate hue (vs. normally 3 passes)

WHY this step: Position t+2 fail hota hai kyunki target model "," ke upar "." strongly prefer karta hai, toh draft ka "," mein confidence misleading hai. Adjusted distribution draft ki bias hata deta hai.

Speedup Analysis

Expected Acceptance Rate

Maano $α$ = probability ki ek draft token accept ho jaaye (empirically good draft models ke liye 0.6-0.8).

Tokens accepted per speculation:

E [tokens] = i = 0 \sum K - 1 (i + 1) α^{i} (1 - α) + (K + 1) α^{K} = \frac{1 - α ^{K + 1}}{1 - α}

Derivation (indices par dhyan se):

Exactly $i$ tokens accept karo phir reject (for $0 \leq i < K$ ): pehle $i$ candidates accept hote hain (probability $α^{i}$ ) aur $(i + 1)$ -waan reject hota hai (probability $1 - α$ ). Phir hum adjusted distribution se ek token resample karte hain, jisse $i + 1$ output tokens milte hain. Toh term hai $(i + 1) α^{i} (1 - α)$ .
Saare $K$ candidates accept karo (probability $α^{K}$ ): hum additionally ek bonus token sample karte hain, jisse $K + 1$ output tokens milte hain. Toh term hai $(K + 1) α^{K}$ .
Sum karke aur geometric series simplify karne par closed form $\frac{1 - α ^{K + 1}}{1 - α}$ milta hai.

WHY speedup is less than $K$ : Rejections target pass waste kar dete hain. Maximum speedup (jab $α \to 1$ , toh output rate $\to K + 1$ ) hai

Speedup_{m a x} = \frac{c _{p} ( K + 1 )}{K c _{q} + c _{p}},

jo $K + 1$ sirf idealized limit $c_{q} \to 0$ mein equal hota hai (ek free draft model). Nonzero draft cost ke saath draft phase khud time leta hai, isliye true ceiling $K + 1$ se neeche hai. Jab $α \to 0$ , speedup $\to c_{p} / (K c_{q} + c_{p}) \leq 1$ ho jaata hai (koi gain nahi, possibly draft passes se thoda overhead).

Optimizing the Draft Model

WHAT makes a good draft model?

High agreement ( $α$ ): Target ke saath distribution mismatch minimize karo
Low latency: Target se bahut zyada faster hona chahiye (typically >5× speedup)
Same vocabulary: Token spaces bilkul align hone chahiye

HOW to create one:

WHY distillation works best: Explicitly distribution match ke liye optimize karta hai, sirf task accuracy ke liye nahi. 95% task accuracy wala model sirf 60% token-level agreement rakh sakta hai, jabki ek distilled model kam task accuracy par 75%+ agreement achieve kar sakta hai.

Common Mistakes

Practical Implementation Details

Batching Speculation

Challenge: Batch mein alag-alag sequences alag sankhya mein tokens accept kar sakti hain.

Solution: "Sync points" mein process karo:

Saari sequences ko $K$ tokens se draft karo
Target sab verify kare
Har sequence independently 0 se $K$ tokens accept kare
Chhoti sequences ko pad karo, unki current position se continue karo

WHY this works: Target verification phir bhi ek single batched forward pass hai. Asynchrony post-processing mein handle hoti hai.

Temperature and Sampling

Temperature $τ$ ke saath:

Draft $q_{τ} (x) = softmax (logits_{q} / τ)$ se sample karta hai
Target $p_{τ} (x) = softmax (logits_{p} / τ)$ use karta hai
Acceptance criterion unchanged: $min (1, p_{τ} / q_{τ})$

Top-k, nucleus sampling: Adjusted distribution par acceptance sampling ke baad apply karo.

Extensions and Variants

Medusa decoding

Target model pe hi multiple "draft heads" use karta hai (intermediate layers par $K$ chhote prediction heads add karta hai). Alag draft model ki zaroorat nahi, lekin thodi memory trade hoti hai.

Speculative RAG

Retrieval-augmented generation ke liye, draft model tokens aur retrieval queries dono propose karta hai. Target dono verify karta hai.

Multi-candidate speculation

Draft model multiple branches ke saath $K$ candidates ka ek tree propose karta hai. Target saare paths verify karta hai. Jab $α$ low ho tab uncertainty better handle hoti hai.

Recall Feynman Explanation (ELI12)

Socho tum ek essay likh rahe ho aur tumhara ek chhota bhai/behen hai jo bahut fast likhta hai lekin kuch galtiyan karta hai. Trick yeh hai:

Tumhara bhai/behen agle 4 sentences quickly likhta hai ("draft")
Tum ek saath 4 sentences padhte ho aur har ek check karte ho
Agar sentence sahi hai, rakh lo. Agar galat hai, wahan ruko, fix karo, aur bhai/behen ko wahan se dobara shuru karne kaho Yeh tumhare akele likhne se faster kyun hai? Kyunki 4 sentences padhna aur check karna almost utna hi time leta hai jitna tum khud 1 sentence likhte ho. Agar tumhara bhai/behen 4 mein se 2 bhi sahi kar de, tum time bacha rahe ho!

AI mein, "tum" ek giant smart model ho (slow), "bhai/behen" ek small quick model hai (fast lekin kam accurate), aur "sentences" tokens hain. Small model aage guess karta hai, big model ek saath sab check karta hai. Zyada tar guesses sahi hoti hain, toh hum zyada tar slow generation steps skip kar dete hain.

Connections

Model Quantization — Complementary: draft aur target dono quantize karo aur speedup aur badha lo
Flash Attention — Orthogonal memory optimization; dono combine kiye ja sakte hain
Beam Search — Alternative decoding strategy; speculative decoding beam search ke saath compatible hai
Knowledge Distillation — Draft model train karne ke liye use hoti hai
Transformer Architecture — Self-attention samajhne se pata chalta hai memory-bound kyun hai
Distributed Training — Speculative decoding inference latency kam karta hai; distributed training time kam karta hai

#flashcards/ai-ml

Speculative decoding kya hai? :: Ek lossless inference acceleration technique jahan ek fast draft model parallel mein $K$ candidate tokens generate karta hai, aur ek slow target model rejection sampling use karke ek single forward pass mein saare candidates verify karta hai taaki exact target distribution maintain rahe.

Autoregressive decoding slow kyun hai?

Har token ke liye model ke through ek sequential forward pass chahiye hota hai, jo memory-bound hai (billions of parameters load karna) na ki compute-bound, jisse GPU compute resources tokens ke beech idle rehte hain.

Speculative decoding mein acceptance criterion kya hai?

Candidate token

\tilde{x}

ko probability

min (1, p (\tilde{x}) / q (\tilde{x}))

se accept karo jahan

p

target model probability hai aur

q

draft model probability hai. Yeh ensure karta hai output exactly target distribution se match kare.

Speculation mein expected output tokens ki sankhya kya hai?

E [tokens] = \frac{1 - α ^{K + 1}}{1 - α}

jahan

α

probability hai ki ek draft token accept ho aur

K

lookahead length hai. Yeh sum

\sum_{i = 0}^{K - 1} (i + 1) α^{i} (1 - α) + (K + 1) α^{K}

ke barabar hai, 1 (worst case) se

K + 1

(best case) tak range karta hai.

Speculative decoding ke liye ek achha draft model kya banata hai?

(1) Target model ke saath high agreement rate

α

(60-80%), (2) Target se bahut zyada faster (>5× speedup), (3) Same vocabulary aur valid probability distributions. Architecture target se alag ho sakta hai.

Speculative decoding output distribution kyun nahi badalta?

Step 3 mein rejection sampling mathematically guarantee karta hai ki output target model ki distribution se exactly match kare, chahe hum draft model proposals use karein. Yeh statistical correction ke saath "trust but verify" hai.

Draft cost account karte hue maximum theoretical speedup kya hai?

Speedup_{m a x} = \frac{c _{p} ( K + 1 )}{K c _{q} + c _{p}}

jahan

c_{q}, c_{p}

draft/target per-token costs hain. Yeh

K + 1

sirf idealized limit

c_{q} \to 0

mein equal hota hai; nonzero draft cost ceiling ko neeche kar deti hai.

Speculative decoding mein optimal lookahead

K

kya hai?

Typically

K = 4

8

. Bada

K

early rejections hone par wasted computation badhata hai. Optimal

K

expected accepted tokens aur cost ke beech balance karta hai:

K^{*} = ar g max_{K} \frac{E [ accepted ]}{K \cdot c _{q} + c _{p}}

Speculative decoding alag temperatures handle kaise karta hai?

Draft aur target dono sampling se pehle apne logits par temperature

τ

apply karte hain:

q_{τ} = softmax (logits_{q} / τ)

p_{τ} = softmax (logits_{p} / τ)

. Acceptance criterion in temperature-adjusted probabilities use karta hai. Top-k/nucleus acceptance ke baad apply hota hai.