Speculative Decoding: Faster Inference Through Speculation

Picture a customer-support chatbot built on a large language model, handling UPI dispute queries for a fintech app during a payment-failure spike — five million conversations a day, roughly 150 tokens per reply. The model does not write a reply as one block of text. It writes it one token at a time: predict the next word, append it, feed the whole sequence back in, predict the next word again. If each token costs 40 milliseconds of GPU time, a 150-token reply takes 6 seconds of pure decoding, repeated across 750 million tokens a day. Shaving that per-token cost in half — to 20 milliseconds — saves roughly 4,167 GPU-hours of decoding time every single day (750,000,000 tokens × 20 ms saved ÷ 3,600,000 ms/hour), which is the difference between provisioning one fleet of inference GPUs and needing nearly double that fleet at peak. This is a hypothetical, illustrative system, not a real company's published figures — but the arithmetic is exactly the kind that inference engineering teams run before deciding whether a technique is worth shipping. Speculative decoding is one of the few techniques that delivers a cut like this for free: no retraining, no loss in output quality, no approximation. It is a scheduling trick dressed up as an algorithm, and understanding why it is exact rather than approximate is the whole chapter.

The bottleneck: why decoding is slow even though it should be fast

You already know that a transformer forward pass is matrix multiplication — GPUs are extraordinarily good at matrix multiplication. So why is generating one token at a time slow? The answer is not compute, it is memory bandwidth. To predict the next token, the GPU must read every weight matrix of the model from its memory into the arithmetic units. For a large model this can be tens of gigabytes of weights, and modern GPUs are far better at doing arithmetic on data once it is loaded than at loading that data in the first place. When you generate a single next token, the amount of arithmetic performed per byte of weight loaded is tiny — you compute one row of output per matrix, then throw the loaded weights away and do it again for the next token. The GPU's compute units sit mostly idle, waiting on memory transfers. This is called being memory-bandwidth-bound, and it is the defining fact of autoregressive LLM decoding: the arithmetic capacity you paid for is going unused.

This idle capacity is the opportunity. If, instead of computing one token's worth of output per weight-load, you could compute several tokens' worth of output using the same weight-load, the extra arithmetic is nearly free — the GPU was going to sit idle during that memory transfer anyway. This is exactly what happens when a transformer processes a whole prompt at once (the "prefill" phase): dozens or hundreds of tokens are scored in parallel in roughly the time it takes to score one, because the weights are loaded once and reused across every position. Speculative decoding's entire trick is to manufacture a batch of positions to verify in parallel, during what would otherwise be slow one-token-at-a-time generation — turning the sequential decode phase into something that behaves like the fast parallel prefill phase.

The mechanism: a small model guesses, a big model checks

Speculative decoding uses two models that share a vocabulary: a small, fast draft model M_q (a distilled or otherwise cheap version of the same family, or even a much smaller separate model) and the large, accurate target model M_p — the model whose output you actually want. The procedure, per round:

1. The draft model generates γ tokens autoregressively, exactly as normal decoding would, but cheaply — it is small, so each of these γ forward passes is fast. Call the proposed tokens x₁, ..., x_γ, and record the draft model's own probability for each, q₁(x₁), ..., q_γ(x_γ).
2. The target model is run once, scoring all γ proposed positions simultaneously in one parallel forward pass (plus one extra position past the last draft token) — exploiting exactly the memory-bandwidth slack described above. This produces the target model's own probabilities p₁(x₁), ..., p_γ(x_γ), p_γ+1(·) for the same positions.
3. Walk through the γ proposed tokens left to right. For token x_i, draw a uniform random number r ~ U(0,1) and accept x_i if r < min(1, p_i(x_i) / q_i(x_i)). If accepted, move to the next token. If rejected, stop accepting and resample a replacement token from the residual distribution p′(x) = max(0, p_i(x) − q_i(x)) / Σ_x max(0, p_i(x) − q_i(x)), then discard every draft token after it.
4. If all γ tokens were accepted, sample one bonus token from p_γ+1, the position the target model scored one step past the draft — since that forward pass already computed it for free.

Every round therefore produces at least one new token (the resampled or bonus token) and at most γ+1, using exactly one expensive target-model call regardless of how many tokens land. The draft model's guesses are cheap insurance; the target model's one parallel pass is the only costly step, and it is shared across every accepted token in the round.

Worked example 1: tracing the accept/reject algorithm by hand

Take a toy vocabulary {A, B, C} and γ = 2 draft tokens, with fixed random draws so the trace is fully deterministic and checkable.

Position 1. Draft model distribution q₁: A = 0.6, B = 0.3, C = 0.1. The draft model samples token A (its most likely token, drawn from this distribution). The target model, scoring this same position in its parallel pass, computes p₁: A = 0.3, B = 0.5, C = 0.2. Acceptance threshold: min(1, p₁(A)/q₁(A)) = min(1, 0.3/0.6) = 0.5. Draw r₁ = 0.3. Since 0.3 < 0.5, A is accepted.

Position 2. Draft distribution q₂: A = 0.2, B = 0.5, C = 0.3. The draft model samples token B. Target distribution at this position, p₂: A = 0.1, B = 0.1, C = 0.8. Acceptance threshold: min(1, p₂(B)/q₂(B)) = min(1, 0.1/0.5) = 0.2. Draw r₂ = 0.6. Since 0.6 is not less than 0.2, B is rejected.

Because position 2 was rejected, we stop accepting and resample from the residual p₂′(x) = max(0, p₂(x) − q₂(x)), renormalized:

raw residual:  A: max(0, 0.1-0.2) = 0.0
               B: max(0, 0.1-0.5) = 0.0
               C: max(0, 0.8-0.3) = 0.5
sum = 0.5
normalized:    A: 0.0   B: 0.0   C: 1.0

The residual distribution puts all its mass on C, so the resampled token is deterministically C. This round therefore outputs the sequence A, C — two tokens — using exactly one target-model forward pass (which scored both position 1 and position 2 in parallel), instead of two sequential target-model calls that ordinary decoding would have required.

Why this is exact, not approximate — and the misconception it corrects

Common misconception: students who have just studied knowledge distillation naturally assume speculative decoding is a similar trade-off — swap in a smaller, weaker model for speed and accept a small quality hit. That is wrong, and it is the single most important thing to understand about this technique. Speculative decoding produces samples from exactly the target model's probability distribution — not an approximation of it. The draft model's job is only to propose candidates; whether a candidate survives is decided entirely by the target model's own probabilities through the accept/resample rule above. The output you get is statistically indistinguishable from running the target model alone, token by token, with the same underlying random draws.

The proof sketch is worth internalizing because the numbers in the worked example were not a coincidence. For any token x, the probability that speculative decoding's accept/reject procedure ultimately outputs x at a given position is P(accept x) + P(reject) · P′(x), where P(accept x) = q(x) · min(1, p(x)/q(x)) = min(p(x), q(x)), and the residual term is built precisely to cover whatever probability mass p assigns to x beyond what q already proposed. Summing the two pieces algebraically returns exactly p(x) for every token — the draft model's distribution cancels out completely. This is why speculative decoding is deployed in production LLM serving systems without any evaluation asterisk: it is a pure latency optimization, mathematically guaranteed to leave output quality untouched, provided the random draws are used consistently as described.

Worked example 2: how much speedup do you actually get?

Let α be the model's average per-token acceptance probability — how often, on average, the target model agrees with the draft model's proposal. (Real acceptance rates vary token to token; treating α as constant is the standard simplifying assumption used to derive a clean, useful throughput estimate, not an exact claim about every position.) With γ draft tokens per round, the expected number of tokens a round produces is a geometric-style sum:

E[tokens per round] = Σ_i=0^γ αⁱ = (1 − α^γ+1) / (1 − α)

This comes from summing over every possible number of acceptances j: with probability α^j(1 − α) exactly j tokens are accepted before a rejection forces a resample (contributing j+1 output tokens), and with probability α^γ all γ are accepted and a bonus token is drawn (contributing γ+1). Working this out for γ = 4, α = 0.7 gives E = (1 − 0.7⁵)/(1 − 0.7) = (1 − 0.16807)/0.3 = 2.7731 tokens per round — independently confirmed by direct enumeration of all five acceptance-count cases (0 through 4 accepted), which also sums to 2.7731.

Now account for cost. Let one target-model forward pass be the unit of time (1.0), and let the draft model cost a fraction c of that — say c = 0.1, a draft model roughly ten times cheaper per token. A round costs 1 + γc = 1 + 4(0.1) = 1.4 time units: one target verification pass plus four cheap draft passes. Compare this to plain autoregressive decoding, which produces exactly 1 token per 1.0 time unit. Speculative decoding produces:

speedup = E[tokens per round] / cost per round
        = 2.7731 / 1.4
        = 1.981×

Roughly a 2× wall-clock speedup for this α and γ, with the output distribution left completely unchanged. This formula also explains why practitioners tune γ carefully rather than maximizing it: past a certain point, additional draft tokens are increasingly likely to be rejected (each extra token multiplies by another factor of α < 1), so their expected contribution shrinks while their guaranteed cost γc grows linearly — the speedup curve has an interior optimum in γ that depends on how well the draft model matches the target model.

Diagram: one round of speculative decoding

Active recall

Attempt each question before reading the answer beneath it.

1. Why is single-token autoregressive decoding slow on a GPU even though GPUs excel at matrix multiplication?
2. In the accept/reject rule, why is the acceptance probability min(1, p_i(x_i)/q_i(x_i)) rather than simply p_i(x_i)?
3. A draft model proposes token X with q(X) = 0.8; the target model assigns p(X) = 0.2. What is the probability this proposal is accepted?
4. If γ = 6 and the draft model's per-token acceptance rate is only α = 0.2 (a poorly matched draft model), what happens to the expected speedup, and why might a serving system choose a smaller γ instead?
5. True or false: speculative decoding changes the probability distribution the system samples from, trading a small amount of output quality for speed. Justify your answer.
6. Why does the target model's single verification pass over γ+1 positions cost roughly the same as verifying just one position, rather than γ+1 times as much?

Answers.

1. Because generating one token requires loading the entire model's weights from GPU memory for a tiny amount of arithmetic (one output row), so the process is bottlenecked on memory bandwidth, not on the GPU's arithmetic throughput — the compute units sit mostly idle waiting for data.
2. Because p_i(x_i) alone is not a valid acceptance rule when q and p can each exceed the other at different tokens — the min with 1 caps it as a proper probability, and this specific form is exactly what is needed so that summing accept-probability plus reject-then-resample-probability reproduces p(x) precisely for every token, not just the proposed one. A plain p_i(x_i) rule would not preserve the target distribution.
3. min(1, 0.2/0.8) = min(1, 0.25) = 0.25, so there is a 25% chance of acceptance and a 75% chance of rejection followed by resampling from the residual distribution.
4. Expected tokens per round becomes (1 − 0.2⁷)/(1 − 0.2) ≈ 1.2499, barely above the 1 token per round you would get with no speculation at all, while the cost still pays for 6 draft calls every round. If those draft calls are not free, the speedup can fall below 1× — actually slower than plain decoding — so a serving system profiles α for the deployed draft/target pair and picks the γ that maximizes E[tokens]/(1+γc), not the largest γ available.
5. False. The accept/reject/resample construction is specifically designed so the marginal probability of any token being output equals p(x) exactly, for every token — proven by summing min(p(x), q(x)) (direct acceptance) and the reject-and-resample contribution, which together telescope to p(x). The draft model only affects how many draft rounds are needed, never what distribution is sampled from.
6. Because decoding is memory-bandwidth-bound: scoring one position already pays the full cost of loading the model's weights from memory, and the GPU's arithmetic units have spare capacity to score several more positions using those same already-loaded weights before that spare capacity runs out — so the marginal compute cost of a few extra positions is largely absorbed, and wall-clock latency stays close to that of a single position.

Think About It

Think about this: How would you explain speculative decoding: faster inference through speculation to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where speculative decoding: faster inference through speculation is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting speculative decoding: faster inference through speculation to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind speculative decoding: faster inference through speculation, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.