Decode is one token at a time -- and that is the bottleneck

To generate text, a transformer runs a forward pass, samples one token, appends it, and runs again. Producing T tokens means T strictly sequential passes. The painful part is that each decode step is memory-bandwidth bound, not compute bound: with a batch of one and a single new position the arithmetic is tiny, yet the hardware must still stream every weight (and the whole KV cache) from memory to produce that one token.

The consequence is idle compute: the matrix units sit mostly empty while memory bandwidth is the wall. This is the slack speculative methods exploit. If a single pass pays the full weight-loading cost anyway, you may as well push several candidate tokens through it at once. Processing k+1 positions in one pass costs almost the same wall-clock time as processing one, because the bottleneck is loading the weights, not the handful of extra dot products. That ‘extra positions are nearly free’ fact is the physical basis for PLD.

Advertisement

Speculative decoding in one breath: draft, then verify

Speculative decoding replaces k slow sequential steps with one cheap drafting step plus one parallel verification step. First a fast drafter proposes a continuation of k tokens d_1 … d_k. Then the large target model runs once over all k+1 candidate positions in parallel, yielding its own next-token prediction at each.

Verification walks the draft left to right and accepts d_t as long as it agrees with what the target model would itself have produced; at the first disagreement it stops, keeps the target’s own token there, and discards the rest. If a of the k drafted tokens are accepted, the pass emits a+1 tokens — the a agreed draft tokens plus one guaranteed ‘bonus’ token from the verifying pass. Crucially this is exact: for greedy decoding the output is identical to plain decoding, and with the proper rejection-sampling correction it preserves the target’s sampling distribution. Speed changes; the text distribution does not.

Advertisement

The prompt lookup twist: retrieve the draft, do not generate it

Classic speculative decoding pays for its draft by running a smaller model — more weights in memory, more compute per drafted token, and the nuisance of aligning that model with the big one. PLD asks a sharper question: for input-grounded work, where does the next chunk of output usually come from? Very often, verbatim from the prompt. A summarizer reuses the source’s exact names and phrases; a RAG system quotes the retrieved passage; a code-editing model reprints long stretches of the original file untouched between edits.

So PLD throws away the draft model and treats the prompt as a draft source. The proposal is not generated by any network — it is retrieved by a string match against the context. The drafter becomes an n-gram lookup: essentially free, needing no extra parameters, training, or GPU memory. The verification pass is unchanged, so correctness is unchanged; only the quality of the retrieved guesses varies.

The n-gram match, precisely

Let the tokens generated so far end in the suffix S = (g_{i-n+1}, …, g_i) — the last n tokens. Let the context (prompt plus anything retrieved) be P = (p_1, …, p_m). PLD scans P for a position j where the n-gram matches:

find j such that (p_j, …, p_{j+n-1}) = (g_{i-n+1}, …, g_i)
draft  D = (p_{j+n}, …, p_{j+n+k-1})   // the k tokens that FOLLOWED the match

In words: find where in the prompt this recent n-gram occurred, then copy the k tokens that came after it as the guess for what comes next. The hyperparameters are the match length n (often 1–3) and the draft length k (often ~10); with several matches, a common policy prefers the most recent or the longest. The search is a hash-table lookup over P — effectively O(1) amortized — nothing beside a forward pass. If nothing matches, PLD proposes no draft and the step degrades gracefully to a single normal token.

Verification in a single parallel pass

Given draft D = (d_1, …, d_k), the target model runs one forward pass over the current position plus all k drafted positions. At each position it produces its own prediction m_t (for greedy, m_t = argmax of its logits). Acceptance is a left-to-right scan:

a = 0
while a < k and d_{a+1} == m_{a+1}:   // draft agrees with the target
    a = a + 1
emit d_1 … d_a, then emit m_{a+1}   // a accepted + 1 bonus token

The pass yields a+1 tokens for the price of one forward pass. The bonus token m_{a+1} is always the target’s own choice, so even a fully rejected draft (a = 0) still advances by one token — identical to plain decoding. That is why a wrong guess never costs correctness and barely costs time: the extra positions rode along in a pass that was memory-bound anyway. The emitted text is exactly what the target model would have produced alone; PLD only compresses how many passes it took to get there.

Copy rate vs speedup: the governing equation

The number that decides whether PLD helps is the copy rate f: the fraction of output tokens falling inside spans copied verbatim from the context. Split decoding into two regimes. In a copied span, once an n-gram locks on, each verify pass accepts a long run — call the average accepted length L tokens per pass. Outside copied spans the draft is rejected and each pass yields 1 token. The passes needed for T output tokens are then:

passes ≈ (f·T)/L  +  (1-f)·T
speedup = T / passes = 1 / ( f/L + (1-f) )

Read the limits. As f → 0 (nothing copied), speedup → 1: PLD does no harm. As f → 1 and L grows, speedup → L: you approach copying a whole span per pass. The relationship is asymmetric and safe — a high copy rate buys a large multiplier, a low one costs essentially nothing — which is why PLD is an easy win to switch on for grounded workloads.

A worked example

Suppose a document-editing model regenerates a file of T = 1000 tokens, and f = 0.7 of those tokens are unchanged text copied straight from the input. In the copied regions n-gram matching sustains an average accepted draft of L = 8 tokens per pass; the remaining 30% is new edits with no copy benefit.

copied  0.7 × 1000 = 700  →  700 / 8 = 87.5 passes
new     0.3 × 1000 = 300  →  300 / 1 = 300  passes
total   ≈ 388 passes   vs   baseline 1000
speedup 1000 / 388 ≈ 2.6×

The formula gives the same figure: 1 / (0.7/8 + 0.3) ≈ 2.58×. Raise the copy rate to f = 0.9 and it becomes ≈ 4.7×; drop it to f = 0.2 and you get only ≈ 1.2×, a small gain but not a loss. The payoff tracks the copy rate almost linearly at the high end and flattens harmlessly to 1× at the low end.