SpecInfer: Accelerating Large Language Model Serving with Tree-based Speculative Inference and Verification

Instead of asking a big language model for one token at a time, SpecInfer has tiny models guess a whole tree of likely continuations and lets the big model check the entire tree in a single pass — provably changing nothing about the output.

Why this problem is worth solving

A large language model (LLM) generates text by autoregressive decoding: it takes the prompt, produces one token, appends it, and repeats. Each token is conditioned on everything before it — that dependency is what makes the text coherent, and it is also a hard serial chain. Within one request, there is almost nothing to parallelize.

The economics of that chain are brutal. Producing a single token requires reading essentially all of the model’s parameters from GPU memory — for the 175-billion-parameter GPT-3, more than eight 40-gigabyte A100 GPUs just to hold the weights in half precision, and seconds of latency per request. The arithmetic per parameter read is tiny, so the GPU’s compute units idle while memory streams. To avoid recomputing attention over the past, systems cache every previous token’s keys and values, and for long outputs this KV cache itself becomes a memory burden that limits how many requests can run at once.

The situation is even starker for offloading-based serving — running a model bigger than the GPU by keeping parameters in CPU memory and streaming them in for each step. There, every generated token costs a full trip of the model’s weights across the CPU–GPU link. One token, one hundred-gigabyte parade.

The tantalizing asymmetry: generating is serial, but checking is not. Given a draft of the next several tokens, the LLM can compute what it would have produced at every position in a single parallel pass — the same trick it uses on prompts. If someone could guess its output cheaply, most of the serial steps could be collapsed. The question is how to guess well enough for the collapse to pay.

What people did before, and where it broke

Sequence-based speculative decoding supplies the guesser: a small speculative model (SSM) — the paper’s term for a distilled, pruned, or just-smaller sibling of the LLM, like the 68-million-parameter LLaMA next to the 7-billion one. The SSM drafts a sequence of tokens serially (cheap, because it is tiny), and the LLM verifies them all at once. Tokens that match are accepted; the first mismatch ends the gain. The output is exactly what the LLM would have produced alone.

The weakness is structural. An SSM is 100–1000× smaller than its LLM, and that capacity gap bounds how often they agree. The paper measures it: the SSM’s single best guess matches the LLM’s stochastic choice only 52–57% of the time per token (62–70% for greedy decoding). Success of an entire drafted sequence decays exponentially in its length, so long drafts are mostly wasted work, and short drafts barely amortize anything.

But the same measurements contain the escape route: when the SSM’s top guess is wrong, the LLM’s actual token is almost always among the SSM’s next few candidates. Widening from top-1 to top-5 raises per-token coverage from 57% to 96–97% for stochastic decoding (70% to 89% greedy). The information is in the small model — a single sequence is just too narrow a container for it. The search space, however, is vast: a vocabulary of 50,272 tokens makes 50,272⁴ ≈ 6×10¹⁸ possible four-token continuations. Exploring breadth needs a structure, a cheap way to verify many alternatives at once, and — for sampling-based generation — a proof that all of this changes nothing about the output distribution. Those three pieces are SpecInfer.

The idea

Draft a tree

A token tree organizes many candidate continuations compactly: each node holds one token, and the path from the root to any node spells out one candidate sequence. Alternatives that share a prefix share nodes — “machine learning algorithm” and “machine learning system” differ only at the third node.

SpecInfer grows the tree two ways. Expansion exploits diversity within one SSM: at chosen steps, take its top-k tokens instead of one, per a preset configuration (the evaluation uses ⟨1, 1, 3, 1, 1, 1, 1, 1⟩ — draft eight steps deep, branching three ways at the third). Merging exploits diversity across SSMs: several small models each draft, and their outputs merge into one tree that contains every drafted sequence exactly once. To make multiple SSMs usefully different, SpecInfer boost-tunes them: fine-tune the first SSM fully, mark the prompts it now gets right, then tune the next SSM on the remainder — an unsupervised division of labor, with the LLM’s own outputs as the target. The SSMs run in parallel on different GPUs, so speculation latency stays that of a single SSM.

Verify the whole tree in one pass

Naively, each tree branch is a separate sequence needing its own LLM pass and its own KV cache — sharing nothing, recomputing shared prefixes, launching a kernel per branch. SpecInfer instead generalizes attention itself. Tree attention defines, for every node, the attention output computed over that node’s root-path — exactly what sequence attention would give. Two mechanisms make it computable in one shot:

• A shared, depth-first cache. Keys and values for the whole tree live in one KV cache, filled in depth-first order, so shared prefixes are stored and computed once.
• A topology-aware causal mask. Ordinary decoding masks attention so a token sees only its predecessors in the line. SpecInfer’s mask lets each tree node see exactly its ancestors in the tree — siblings and cousins are masked out. With that one change, the attention for every node in the tree fuses into a single GPU kernel, and the results are bit-identical to running each branch separately.

At large batch sizes this tree-based decoding is up to 1.8× faster than sequence-based verification of the same tree — the shared prefixes and the single fused kernel are pure savings.

Accept tokens without changing the model’s behavior

Verification turns the LLM’s one pass into accepted tokens. For greedy decoding (always pick the most likely token), it is a walk: start at the root; while some child matches what the LLM says comes next, step to it; when no child matches, append the LLM’s own token and stop. Note the guarantee hiding there — even a totally wrong tree yields one correct new token, so an iteration is never slower than plain decoding by more than the (small) speculation cost.

For stochastic decoding (sample from the probability distribution — what chat applications actually do), correctness is subtler: the accepted tokens must follow exactly the LLM’s distribution, not the SSMs’. SpecInfer’s multi-step speculative sampling achieves this: at each node, pick a speculated child and accept it with probability min(1, P_LLM(token) / P_SSM(token)); on rejection, subtract the rejected mass from the LLM’s distribution, renormalize, and try the node’s other children before giving up and sampling fresh. The paper proves the output distribution is exactly the LLM’s (Theorem 4.2) and that this multi-step scheme rejects strictly less often than the naive check-if-sampled-token-is- in-the-tree approach (Theorem 4.3) — measured, it verifies 1.2–1.3× more tokens per step.

Why the overheads do not eat the gain

The SSMs add under 1% each to memory. The token tree’s extra KV entries are noise next to the long-sequence KV cache. And the verification pass computes many tree nodes that will be rejected — but it does so using precisely the GPU compute that incremental decoding leaves idle, so per-iteration latency stays flat. The gain is real because the waste was already there.

machine ─ learning ─ algorithm
        │          └ system ─ design
        └ translation ─ model

Why it works

Because checking is parallel even though generating is serial, any correct guess converts serial LLM steps into one shared parameter-read. → Because the LLM’s true token is almost always in the small model’s top few (96–97% in the top 5), a tree of alternatives captures what a single sequence misses — per-token coverage nearly doubles. → Because branches share prefixes and the topology-aware mask fuses all of their attention into one kernel over one shared cache, verifying a whole tree costs about the same as verifying one branch. → Because greedy verification always harvests the LLM’s own token at the divergence point, and multi-step speculative sampling provably preserves the sampling distribution, correctness is not traded — only wasted idle compute is spent. → Therefore each LLM pass yields two to four tokens instead of one, and everything priced per-pass drops proportionally: memory reads in distributed serving (1.5–2.8× faster), and CPU-to-GPU parameter shipments in offloaded serving (2.6–3.5× faster).

What it costs

• Spare compute is the fuel. The verification pass exploits GPU resources that incremental decoding leaves idle. At large batch sizes that slack disappears, and SpecInfer’s advantage shrinks — the paper is explicit that the sweet spot is low-latency, small-batch serving.
• You need good small siblings. Speculation quality rests on SSMs aligned with the LLM — pre-trained same-family variants, or boost-tuned ones (tuned on a general corpus against the LLM’s outputs). A model with no small sibling needs that preparation first.
• Tree width is a knob, not a free lunch. Wider trees verify more tokens but cost more per verification; at batch sizes of 4 and up, width 2–3 wins, not width 5.
• Modest memory overhead. SSM parameters (under 1% each) and the tree’s KV entries — negligible, but nonzero.
• The tree shape is static. The expansion configuration is preset; adapting it to the prompt at runtime is named as an open problem.

The evaluation

Models: LLaMA-7B, OPT-13B, OPT-30B, and LLaMA-65B served with LLaMA-68M and OPT-125M as SSMs — sibling models 100–500× smaller. Prompts from five datasets (Alpaca, ChatGPT Prompts, WebQA, Chatbot Instruction Prompts, PIQA), up to 128 generated tokens. Hardware: two AWS g5.12xlarge nodes, four A10 24-gigabyte GPUs each, 100-gigabit Ethernet.