Inference Optimization Techniques: Speed and Efficiency

The Bottleneck a Bigger GPU Cannot Fix

A bank in Bengaluru puts an LLM copilot into its call-center software: while a human agent talks to a customer, the model reads the live transcript and drafts suggested replies word by word, one token appearing on the agent's screen every fraction of a second. Product wants sub-300ms latency for the first useful sentence. The model is a 70-billion-parameter chat model, because the smaller ones keep hallucinating policy details. The engineering team already knows, from studying the roofline model of GPU throughput, that decoding is memory-bandwidth bound: producing each token means streaming the entire set of weights out of HBM into the compute units, and the arithmetic itself is nearly idle while that streaming happens. Batching more users together helps amortize that stream across many requests at once, and quantizing the weights shrinks how many bytes have to move — both are tools this curriculum has already covered for exactly this reason. But for a single agent's single conversation at low concurrency, neither trick changes the fundamental fact: one token still costs one full pass of the weights through the memory bus, and buying a faster GPU only moves the floor, it does not remove it.

This chapter is about a different lever entirely: instead of making each expensive pass cheaper, make each expensive pass produce more than one token. That is the whole idea behind speculative decoding, introduced independently by Leviathan, Kalman, and Matias ("Fast Inference from Transformers via Speculative Decoding," ICML 2023) and by Chen, Borgeaud, Irving, Lespiau, Sifre, and Jumper at DeepMind ("Accelerating Large Language Model Decoding with Speculative Sampling," 2023). Both papers show the same surprising result: you can get 2 to 3 tokens out of the price of roughly one target-model pass, with a mathematical guarantee that the output is drawn from the exact same probability distribution the large model alone would have produced. Nothing is approximated. That guarantee, and the arithmetic behind the speedup, is what this chapter derives.

The Mechanism: A Cheap Model Proposes, the Expensive Model Verifies in Parallel

Pair the 70B target model with a much smaller "draft" model that shares its tokenizer — often a distilled or earlier-generation sibling from the same family, small enough that a handful of its forward passes together cost far less than one pass of the target. At each decoding round, the draft model runs autoregressively for γ steps (γ is a tuning knob, typically 3 to 8), proposing a short run of candidate tokens x₁, x₂, …, x_γ the way it normally would, one at a time, cheaply.

Now comes the part that does not exist in ordinary decoding: the target model does not generate anything yet. Instead, it runs one single forward pass over the entire drafted sequence at once — position n+1 through n+γ, plus one extra position for a bonus token — computing its own probability distribution at every one of those positions simultaneously. This is legal because a transformer's forward pass over a sequence of length L already computes logits at every position of that sequence as a byproduct of computing the last one; nothing here is quantitatively different from a normal forward pass over L tokens, and since decoding is memory-bandwidth bound, that pass costs about the same whether it evaluates 1 position or γ+1 positions. The target model has effectively graded the draft model's whole guess in the time it would normally take to generate a single token.

Grading, not accepting outright — because the draft model's guesses are not always right, and simply keeping wrong guesses would corrupt the output distribution. That is what the acceptance test in the next section fixes.

Misconception: "Speculative Decoding Trades Accuracy for Speed"

The single most common thing a student (and plenty of engineers) assume on first hearing this description is that speculative decoding must be a lossy shortcut — a smaller, worse model is doing some of the writing, so the output must be somewhat degraded, an acceptable-quality-for-speed tradeoff like a compressed JPEG. This is false, and provably so. The algorithm is constructed as an instance of rejection sampling, and rejection sampling has a classical guarantee: if you set up the accept/reject rule correctly, the accepted samples are distributed exactly according to the target distribution, with zero contribution from the proposal distribution's own shape.

Here is the actual rule. For a proposed token x at some position, let q(x) be the draft model's probability of x at that position and p(x) be the target model's probability of the same token at the same position (both already computed — q from the draft's own softmax when it sampled x, p from the target's single parallel pass). Accept x with probability:

accept_prob = min(1, p(x) / q(x))

If accepted, keep x and move to the next drafted position. If rejected, throw away every draft token from this position onward (they were all conditioned on a token the target model has just disagreed with, so they are no longer trustworthy), and instead sample a replacement token from the residual distribution:

residual(x) = max(p(x) - q(x), 0) / Z,  where Z = sum over all tokens of max(p(x) - q(x), 0)

This residual distribution puts weight exactly where the target model wanted more probability mass than the draft model gave it, and zero weight everywhere the draft already matched or over-weighted. The proof that this combination reproduces p(x) exactly is short enough to walk through in full. Split into two cases for any fixed token x.

Case 1 — the draft over-weighted x, so p(x) ≤ q(x). Then min(1, p(x)/q(x)) = p(x)/q(x), so the probability of emitting x by direct acceptance is q(x) · p(x)/q(x) = p(x). Also, since p(x) ≤ q(x), the residual max(p(x)-q(x), 0) is 0, so x can never be emitted by the resample path. Total probability of emitting x: exactly p(x).

Case 2 — the draft under-weighted x, so p(x) > q(x). Then min(1, p(x)/q(x)) = 1, so direct acceptance contributes q(x) to emitting x. What remains is to show the resample path contributes exactly p(x) - q(x) more. The total probability mass that gets rejected across all tokens is R = Σ_x' q(x')·(1 - min(1, p(x')/q(x'))), which only has nonzero terms where q(x') > p(x'), and there it equals Σ_x' max(q(x') - p(x'), 0). Because p and q are both proper distributions that sum to 1, the total amount by which q exceeds p somewhere must exactly equal the total amount by which p exceeds q elsewhere — both equal the same constant, which is precisely Z from the residual formula above. So R = Z. The resample path then contributes R · residual(x) = Z · (p(x)-q(x))/Z = p(x) - q(x). Adding the two contributions: q(x) + (p(x) - q(x)) = p(x).

Both cases land on exactly p(x). The draft model's only job is to decide which tokens get free-ridden through on a cheap pass and which get corrected; it never gets to change what the final distribution actually is. This is why production systems (vLLM, TensorRT-LLM, and others) can turn speculative decoding on or off purely as a latency knob, with no quality-eval regression to worry about — the two settings are statistically indistinguishable at the distribution level, even though the literal sampled tokens on any one run will differ because of randomness.

Traced Example: Watching One Acceptance Test Run

The acceptance test can be run as ordinary code once q(x) and p(x) are available as arrays. This example uses a toy vocabulary of 4 tokens so every number is checkable by hand; the code below was actually executed, and the output block reproduces exactly what it printed.

import numpy as np

rng = np.random.default_rng(7)

# Draft model's distribution over a 4-token vocabulary at one position
q = np.array([0.10, 0.60, 0.20, 0.10])   # draft (small) model
# Target model's distribution over the same 4 tokens, same position
p = np.array([0.05, 0.30, 0.55, 0.10])   # target (large) model

# Step 1: draft model proposes a token by sampling from q
x = rng.choice(4, p=q)
print("draft proposes token", x)

# Step 2: acceptance probability
accept_prob = min(1.0, p[x] / q[x])
print("acceptance probability", accept_prob)

# Step 3: accept or reject using a fresh uniform draw
u = rng.random()
if u <= accept_prob:
    print("ACCEPTED - keep token", x)
else:
    # Step 4: resample from the residual distribution
    residual = np.maximum(p - q, 0)
    residual = residual / residual.sum()
    x_new = rng.choice(4, p=residual)
    print("REJECTED - resample gives token", x_new)

draft proposes token 1
acceptance probability 0.5
REJECTED - resample gives token 2

Trace it by hand to confirm the code could not have printed anything else. The draft sampled index 1 (q[1] = 0.60, the mode of q — plausible on a single draw). The acceptance ratio is p[1]/q[1] = 0.30/0.60 = 0.5, so accept_prob = 0.5, matching the printed line exactly. The RNG's next draw, u ≈ 0.897, exceeds 0.5, so the branch takes the rejection path — this is a property of the seeded generator, not something to re-derive by hand, but it is a legitimate outcome since a fair coin at accept_prob = 0.5 rejects half the time. On rejection, residual = max(p - q, 0) = max([-0.05, -0.30, 0.35, 0.00], 0) = [0, 0, 0.35, 0], normalized to [0, 0, 1, 0]. With all the probability mass concentrated on index 2, the resample is deterministic in this particular case — it will always land on token 2 regardless of the RNG draw, because that is the only token the target model wanted more of than the draft model offered. Notice what the residual step actually accomplished: q had placed most of its weight on token 1 and token 2 was underrepresented (p[2] = 0.55 versus q[2] = 0.20); rejecting the draft's token-1 guess and routing the correction to exactly the token the target under-supplied is what makes the two-step procedure land on p exactly, as proven above.

Worked Example: How Many Tokens Land Per Expensive Pass?

The per-token acceptance test above is the unit of work; the quantity that actually matters for latency is how many tokens, on average, get emitted for the cost of one target-model pass across a whole γ-token round. Model the acceptance events across a round as independent draws with a shared average acceptance probability α (a simplification the original papers also use for the closed-form result — in practice α varies token to token, but this average-case model predicts measured speedups well). Let K be the number of leading draft tokens accepted before the first rejection, with 0 ≤ K ≤ γ:

P(K = k) = α^k · (1 - α)   for k = 0, 1, ..., γ-1   (k accepts, then a reject)
P(K = γ) = α^γ                                      (all γ accepted, target's spare logit gives a free bonus token)

Every round always emits exactly one token beyond the K accepted draft tokens — either a residual-resampled correction (if K < γ) or a fresh bonus token drawn from the (γ+1)-th position's logits the target model computed for free in the same pass (if K = γ). So the total tokens emitted this round is T = K + 1. Taking the expectation of K using the standard truncated-geometric identity Σₖ k·αᵏ(1-α) + γαᵞ = α(1-α^γ)/(1-α):

E[T] = E[K] + 1
     = α(1 - α^γ)/(1 - α) + 1
     = [α - α^(γ+1) + 1 - α] / (1 - α)
     = (1 - α^(γ+1)) / (1 - α)

Now cost. Let c be the ratio of one draft-model forward pass's wall time to one target-model forward pass's wall time. Because both are memory-bandwidth bound and c is dominated by how many fewer bytes of weight the smaller model streams, a draft model with roughly 1/13 the target's parameter count costs roughly c ≈ 0.08 of a target pass. One round costs γ draft passes (sequential, cheap) plus one target verification pass (parallel, but priced the same as a single-token pass since streaming the weights once is the bottleneck regardless of how many positions ride along) — that is γc + 1 target-pass-equivalents. Naive autoregressive decoding, by contrast, costs exactly 1 target-pass-equivalent per token, so its "tokens per unit cost" is 1. Speculative decoding's tokens per unit cost is E[T]/(γc+1), and the speedup factor relative to naive decoding is just that ratio.

Plug in a concrete, representative case: γ = 4 draft tokens, α = 0.7 (a realistic average acceptance rate when the draft is a smaller model from the same training family as the target, so its next-token distributions are reasonably well aligned), c = 0.08 (a ~7B drafter paired with a ~70-90B target).

α^5 = 0.7^5 = 0.16807
E[T] = (1 - 0.16807) / (1 - 0.7) = 0.83193 / 0.3 = 2.7731 tokens/round
cost = γc + 1 = 4(0.08) + 1 = 1.32 target-pass-equivalents/round
speedup = E[T] / cost = 2.7731 / 1.32 ≈ 2.10×

Roughly 2.1 times the tokens per second, purely from restructuring how the same target model is called, with the mathematically guaranteed output distribution derived earlier. This composes with — it does not replace — batching, KV-cache management, and quantization: those attack how expensive a single forward pass is, speculative decoding attacks how many tokens a single forward pass is worth.

Diagram: One Round of Speculative Decoding

Beyond a Single Chain: Verifying a Tree of Guesses

The γ-token derivation above assumes the draft model commits to one linear chain of guesses per round; if the third guess is wrong, the fourth and any beyond it are wasted no matter how good they individually were, because they were built on a rejected foundation. A natural extension is to let the draft model hedge: instead of one guess per position, propose a small tree of candidates — for instance the top-2 most likely tokens at each branching position — and verify the entire tree in the same single target pass using an attention mask that lets each branch only see its own ancestors. The target model then walks the tree and accepts whichever root-to-leaf path matches longest, so a wrong guess at position 3 no longer wastes positions 4 through γ, only the sibling branches that also turned out wrong. Because the pass is still memory-bandwidth bound, evaluating a modestly wider tree costs little beyond one linear chain, so E[T] rises with tree width while cost barely does. This is the core idea behind Medusa (Cai et al., 2024), which attaches several extra prediction heads directly onto the target model instead of running a separate draft model at all, and EAGLE (Li et al., 2024), which drafts using the target model's own penultimate-layer features to make the small predictor track the target's distribution more closely and push α higher. Both remove the need to train and serve a second model altogether, trading that engineering burden for a more involved verification and masking implementation.

Active Recall

Attempt every question before reading its answer.

1. In one sentence, explain why speculative decoding speeds up decoding without needing a faster GPU or a smaller target model.
2. Draft distribution q = [0.20, 0.50, 0.30] and target distribution p = [0.40, 0.20, 0.40] over a 3-token vocabulary. The draft proposes index 1 (probability 0.50). What is the acceptance probability, and what residual distribution would a rejection resample from?
3. Using E[T] = (1 - α^(γ+1)) / (1 - α), compute the expected tokens per round for α = 0.85, γ = 3.
4. The worked example used γ = 4, α = 0.7, c = 0.08, giving a ≈2.10x speedup. Suppose the draft model is swapped for a more aggressively quantized (and therefore less accurate) version, dropping α to 0.4, with γ and c unchanged. (a) Recompute E[T] and the speedup. (b) An engineer, seeing the drop, doubles γ to 8 hoping more attempts compensate. Recompute E[T] and the speedup at γ = 8, α = 0.4. Does raising γ fix the problem? Explain why or why not.
5. Why might verifying a tree of candidate continuations accept more tokens per target pass than a single linear chain of γ guesses, and what does it cost to gain that benefit?
6. A teammate claims "speculative decoding always at least doubles throughput." Use a number from this chapter to show the claim is false.

Answers

1. Because generating a token is memory-bandwidth bound, not compute bound: one target-model pass over several candidate positions at once costs almost the same as a pass over a single position (the weights only have to stream out of memory once), so verifying and accepting several tokens per expensive pass yields more tokens for roughly the same per-pass cost, instead of trying to make that one pass itself cheaper or faster.

2. Acceptance probability = p[1]/q[1] = 0.20/0.50 = 0.4. Residual: p - q = [0.40-0.20, 0.20-0.50, 0.40-0.30] = [0.20, -0.30, 0.10]; taking max(·, 0) gives [0.20, 0, 0.10], which sums to 0.30, so the normalized residual distribution is [0.667, 0, 0.333] — a rejection would resample index 0 about two-thirds of the time and index 2 the rest, never index 1 again.

3. α^4 = 0.85^4 = 0.52200625. E[T] = (1 - 0.52200625)/(1 - 0.85) = 0.47799375/0.15 ≈ 3.187 tokens per round.

4(a). α = 0.4, γ = 4: α^5 = 0.4^5 = 0.01024. E[T] = (1 - 0.01024)/0.6 = 0.98976/0.6 = 1.6496. Cost is still γc + 1 = 1.32 (c and γ unchanged). Speedup = 1.6496/1.32 ≈ 1.25x — down sharply from 2.10x, because a poorly matched draft model gets rejected far more often, so most rounds end after only one or two accepted tokens.

4(b). α = 0.4, γ = 8: α^9 = 0.4^9 ≈ 0.000262. E[T] = (1 - 0.000262)/0.6 ≈ 0.999738/0.6 ≈ 1.6662. Cost = 8(0.08) + 1 = 1.64. Speedup = 1.6662/1.64 ≈ 1.016x — essentially no gain over naive decoding at all. Doubling γ did not fix the problem, and this is not a coincidence: as γ grows, E[T] saturates toward the ceiling 1/(1-α) (here 1/0.6 ≈ 1.667, since almost all of the geometric mass is used up after a handful of rounds when α is only 0.4), while the cost term γc + 1 keeps growing linearly with γ. Past a small γ, every extra draft token adds almost nothing to E[T] but keeps adding c to the cost, so the ratio falls back toward 1x. The fix for a low-α problem is a better-matched draft model, not more draft tokens per round.

5. A tree lets the draft model hedge with multiple candidate branches at each position instead of a single guess, so one wrong branch does not automatically waste every guess that came after it in the round — only its own sibling subtree is lost. Because the target's verification pass is still one memory-bandwidth-bound pass regardless of how many tree positions it covers, the extra acceptance yield comes at a cost that is small until the tree grows wide enough to become compute bound; the real added cost is engineering: a custom attention mask so each branch only attends to its own ancestors, and extra logic to pick the longest accepted root-to-leaf path.

6. From question 4(b): at α = 0.4 and γ = 8, the speedup is ≈1.016x, barely above the naive baseline and nowhere near double. The teammate's claim only holds in the favorable regime demonstrated in the worked example (a well-matched draft model, α around 0.7); a poorly matched draft model can make speculative decoding almost worthless no matter how the round is tuned.

Think About It

Think about this: How would you explain inference optimization techniques: speed and efficiency 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.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind inference optimization techniques: speed and efficiency, 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.