Lookahead Decoding

The sequential wall: one token, one whole pass

Autoregressive generation is defined by a strict dependency: token x_i is chosen from p_θ(x_i | x_0, …, x_{i-1}), so you cannot compute x_i until x_{i-1} exists. Producing m tokens therefore means m forward passes, run strictly back-to-back. Nothing about the arithmetic forces this to be slow — the latency comes from the memory system.

During decode with batch size one, each step reads every weight in the model from memory to process a single token. A forward pass costs about 2P FLOPs per token for P parameters, but it must also move all P weights (plus the KV cache) across the memory bus. The ratio of compute to bytes moved — the arithmetic intensity — is tiny, so the processor stalls waiting on HBM or system RAM. This is the memory-bound regime: the compute units sit mostly idle on every decode step. Lookahead decoding’s entire premise is that this idle compute is free capacity waiting to be spent.

Decoding as a fixed point: the Jacobi view

Here is the reframing that unlocks everything. Instead of one token at a time, treat a block of m future tokens as the unknowns of a system of equations. Greedy decoding satisfies, for every position i = 1…m:

x_i = argmax p_θ( · | x_0, x_1, ..., x_{i-1} )   for i = 1..m

This is a triangular nonlinear system: the true solution is exactly what sequential decoding produces. But triangular systems can be attacked by Jacobi iteration — start from an arbitrary guess for all m tokens at once, then update every position simultaneously using the current guesses for the positions before it:

x_i^(t+1) = argmax p_θ( · | x_0, x_1^(t), ..., x_{i-1}^(t) )

The key fact: all m of these updates are computed in a single forward pass. A causal transformer already scores every position in parallel; feeding it the current guess sequence yields the next-token prediction at each of the m slots at once. We turned m sequential passes into repeated parallel passes.

Convergence: why iterating in parallel is safe

Does Jacobi iteration reach the right answer? Yes, and provably fast for the greedy case. Observe that position 1 depends only on the fixed prefix x_0, so after the first iteration x_1 is correct and frozen forever. On the next iteration, position 2 now sees the correct x_1, so x_2 locks in. By induction, each iteration guarantees at least one more token converges from the left, so the process reaches the exact autoregressive output in at most m steps.

Worst case, that is no better than sequential decoding. The win is that convergence is often much faster than one token per step: later positions guess correctly early because many continuations are locally predictable (whitespace, closing brackets, common phrases), so a single parallel step can confirm a run of tokens. Plain Jacobi decoding captures some of this but inconsistently. Lookahead decoding’s contribution is to stop discarding the partial guesses each iteration produces, and instead accumulate them into a reusable structure.

The n-gram pool: harvesting the Jacobi trajectory

Every Jacobi iteration produces, at each of its m positions, a short sequence of tokens — a trajectory through candidate continuations. Across iterations these fragments form n-grams: length-N token sequences the model has tentatively proposed. Lookahead decoding keeps a pool (a cache) of these n-grams, indexed by their first token.

The intuition is that the model’s own half-formed guesses are a free source of plausible drafts. When the next confirmed token is some w, the pool is queried for every stored n-gram beginning with w — each a ready-made continuation the model generated moments earlier. For structured text this pays off dramatically: code, markup, and repetitive prose contain the same n-grams over and over ( return, </div>, self.), so the pool fills with n-grams that will be needed again. It evolves: the lookahead branch refreshes it every step and committed tokens prune it, so it always reflects the current context.

Two branches, one forward pass

A lookahead decoding step fuses two jobs into one batched forward pass, kept apart by a custom attention mask so the branches do not attend across each other:

The lookahead branch runs the Jacobi update. It maintains a 2D window — W parallel trajectories (the window size) each looking N tokens ahead (the n-gram size, or levels). In one pass it refines all W×(N−1) positions and emits fresh n-grams into the pool.

The verification branch pulls up to G candidate n-grams from the pool whose first token matches the last confirmed token and lets the model score them. Wherever the model’s greedy prediction agrees with a candidate token, that token is accepted; the longest matching prefix is committed. Because both branches share the step’s single weight load, they are almost free relative to a normal decode — the weights were going to be read anyway. The step advances by 1 + (accepted length) tokens instead of by one.

A worked step: several tokens at once

Suppose the model is emitting Python and has just committed def. The pool, filled by earlier Jacobi iterations, happens to hold an n-gram whose first token is that anchor: def load ( path ) :. The verification branch scores the continuation in the same pass that advances the lookahead window.

anchor:     ... def          (already committed)
candidate:      load  (  path  )  :
model says:     load  (  path  )  :   <- greedy prediction at each slot
match:           Y    Y   Y    Y  Y
accepted 5 tokens in ONE step  →  commit "load(path):"

One memory-bound forward pass advanced the sequence by five tokens instead of one — the anchor def was already committed, and the five tokens after it are the gain. Had the candidate diverged at path — say the model wanted data — the branch would accept the matching prefix load (, commit those, and discard the rest. Nothing incorrect is ever emitted: acceptance requires the token to equal the model’s own greedy choice, so the output is bit-identical to ordinary greedy decoding. Lookahead changes the schedule, never the result.

The FLOPs-for-latency trade

The whole method is one economic bet: spend idle parallel FLOPs to buy back sequential steps. A baseline step processes one token; a lookahead step processes roughly W×(N−1) + G×(N−1) extra tokens. That is many times more FLOPs per step — but the step still loads the weights exactly once, and it was memory-bound with compute to spare. As long as the extra tokens do not push the step past the roofline into the compute-bound regime, they add almost no wall-clock time, yet each accepted token removes an entire future step.

The governing quantity is the average tokens accepted per step. If a run generates T tokens and accepts τ per step, it needs about T/τ steps instead of T. Speedup is bounded by τ from above and by the point where growing per-step FLOPs saturate the hardware: push the window too far and the step turns compute-bound, so the extra FLOPs now cost real time. The sweet spot sits where per-step compute time rises to meet the fixed weight-load time.

Putting numbers on it

Take a 7B model in fp16 on an accelerator with 2 TB/s memory bandwidth and 312 TFLOP/s of compute. Weights are 2 × 7e9 = 14 GB, so each step must move at least 14 GB: 14e9 / 2e12 ≈ 7 ms just to load them. One token costs 2P ≈ 14 GFLOP, which at 312 TFLOP/s is ≈ 0.045 ms — the unit is idle over 99% of the step.

weight-load time / step   ≈ 7.0 ms   (fixed, memory-bound)
process 60 extra tokens   = 60 x 14 GFLOP = 0.84 TFLOP
                          / 312 TFLOP/s   ≈ 2.7 ms  (< 7 ms: still hidden)
process 300 extra tokens  = 4.2 TFLOP / 312 ≈ 13.5 ms (> 7 ms: now compute-bound)

So a window doing ~60 extra tokens per step is essentially free; ~300 is not. The payoff: 200 tokens sequentially cost 200 × 7 = 1400 ms. With lookahead accepting τ ≈ 2.5 tokens/step we need 80 steps at ≈8 ms each (slightly slower from the extra work) = ≈ 640 ms — roughly a 2.2× reduction, paid entirely in otherwise-wasted FLOPs.

Not speculative decoding: no draft model

Lookahead decoding is frequently confused with speculative decoding, and the shared idea is real: both verify several proposed tokens in one parallel forward pass and both exploit the memory-bound decode. The difference is where the proposals come from.

Speculative decoding needs a separate, smaller draft model that autoregressively proposes k tokens, which the large target model then verifies in parallel (with rejection sampling for exactness). That draft model is extra parameters to train, align, load, and serve — a real deployment burden. Lookahead decoding has no draft model and no extra parameters at all. Its candidates are the target model’s own Jacobi trajectory, cached in the n-gram pool — the model drafts for itself, inside the very same forward pass, via an attention mask rather than a second network. The cost is proposal quality: a trained drafter usually guesses better than harvested n-grams, so raw acceptance can be lower. But lookahead is training-free and plug-and-play — nothing to distill, nothing extra to host.

CPU-SLM implications and pitfalls

For a small model running on a CPU — low memory bandwidth, a single latency-sensitive stream — the memory-bound premise holds even more strongly than on a GPU, so lookahead decoding is a natural fit, and structured outputs like code amplify it as the pool fills with recurring boilerplate. But two cautions matter. First, batching competes with lookahead for the same idle FLOPs: at large batch sizes the decode is already compute-bound (many sequences share one weight load), so the spare capacity lookahead feeds on has evaporated. It shines for single-stream, low-latency serving — exactly the CPU-SLM case.

Second, CPUs have far less headroom than GPUs, so the window that saturates compute is much smaller; tune W, N, and G down or the step tips compute-bound and slows. It also adds attention-mask and KV-cache bookkeeping. Size the window from the actual compute/bandwidth roofline, not by guesswork.