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

Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, Chunan Shi, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, Zhihao Jia

TL;DR

SpecInfer is a novel serving system that accelerates Large Language Model (LLM) inference by using small "speculative" models to generate a tree of potential token sequences. By verifying this entire tree in a single parallel pass with the LLM, SpecInfer achieves up to a 3.5x speedup in serving latency while mathematically guaranteeing the exact same output quality as standard decoding.

What Problem Does This Paper Address?

Generative LLMs like GPT-4 or LLaMA are notoriously slow and expensive to serve. The primary culprit is autoregressive decoding: the model must generate text one token at a time. Because each token depends on all previous ones, the process is inherently sequential.

For a massive model with 175 billion parameters, every single token requires loading the entire model into GPU memory, which is a massive bottleneck. Furthermore, during this "incremental" phase, GPUs are often under-utilized because the computation for a single token doesn't saturate the hardware's parallel processing power.

Existing "speculative decoding" techniques try to fix this by using a tiny, fast model (a Small Speculative Model or SSM) to guess a sequence of tokens. The big LLM then checks that sequence. If the guess is wrong at token three, everything after it is thrown away. The challenge is that tiny models are often bad at guessing exactly what a giant model will say, leading to frequent "mis-speculations" and wasted effort.

Methods

SpecInfer introduces tree-based speculative inference. Instead of guessing a single sequence, it uses SSMs to generate a token tree representing multiple possible paths the conversation could take.

Figure 1. Comparing the incremental decoding approach used by existing LLM serving systems, the sequence-based speculative inference approach, and the tree-based speculative inference approach used by SpecInfer.

1. Token Tree Construction

SpecInfer uses two main strategies to build these trees:

  • Expansion-based: A single SSM generates its top-$k$ most likely tokens at certain steps, creating branches.
  • Merge-based: Multiple different SSMs (perhaps fine-tuned on different datasets) each provide a guess, and these guesses are merged into a single tree.

2. Tree-based Parallel Decoding

To check these guesses efficiently, the authors developed a novel verification mechanism. Standard Transformers expect a linear sequence, but SpecInfer's Tree Attention allows the LLM to process the entire tree at once. By using a "topology-aware causal mask," the system ensures that each token in the tree only "sees" its actual ancestors, preventing information from leaking across different speculative branches.

3. Multi-step Speculative Sampling (MSS)

For applications using stochastic (randomized) decoding, SpecInfer uses a new sampling algorithm. It provably preserves the LLM's original probability distribution while maximizing the number of tokens accepted from the speculative tree.

An overview of the SpecInfer workflow, from the learning-based speculator to the parallel tree verifier.

Datasets

The researchers evaluated SpecInfer across five diverse datasets to simulate real-world usage:

  • Alpaca: Instruction-following tasks.
  • CP (ChatGPT Prompts): General conversational prompts.
  • WebQA: Question answering.
  • CIP (Chatbot Instruction Prompts): Multi-turn interactions.
  • PIQA: Physical commonsense reasoning.

They tested these using the LLaMA (7B to 65B) and OPT (13B to 175B) model families.

Key Insights and Ideas

  • Diversity Beats Depth: Guessing one long sequence is a "high-risk, high-reward" strategy that often fails. Guessing a diverse tree of shorter sequences significantly increases the "hit rate"—the probability that the LLM's actual choice is somewhere in the speculation.
  • Exploiting Spare Compute: Since the LLM is memory-bandwidth bound during decoding, there is "free" compute available on the GPU. SpecInfer uses this spare capacity to verify dozens of speculative tokens in the same time it would normally take to generate just one.
  • KV Cache Efficiency: Because the speculative candidates are organized as a tree, they share prefixes. SpecInfer's tree-based decoding reuses the Key-Value (KV) cache for these shared prefixes, saving significant memory and computation.

Key Results

SpecInfer demonstrates substantial performance gains over state-of-the-art systems like vLLM and FasterTransformer:

  • Distributed Inference: For models spread across multiple GPUs, SpecInfer is 1.5x to 2.8x faster.
  • Offloading-based Inference: In scenarios where the model is too big for GPU memory and must be swapped from CPU RAM (offloading), SpecInfer achieves a 2.6x to 3.5x speedup.
  • Verification Success: Using a tree with a width of 5 can increase the token verification success rate from ~55% (single sequence) to over 95% for stochastic decoding.

Limitations and Future Work

  • Static Tree Structures: Currently, the "shape" of the token tree (how many branches at which depth) is fixed. The authors note that dynamically adjusting the tree shape based on the SSM's confidence could further improve performance.
  • Batch Size Trade-offs: The speedup is most dramatic at small batch sizes (1-4). As the batch size increases, the GPU becomes more saturated with standard work, leaving less "spare" compute for tree verification.
  • SSM Alignment: While merging multiple SSMs helps, the system still relies on the small models being somewhat aligned with the large one. Better methods for "boost-tuning" these small models remain an area for exploration.

Summary updated

Abstract

This paper introduces SpecInfer, a system that accelerates generative large language model (LLM) serving with tree-based speculative inference and verification. The key idea behind SpecInfer is leveraging small speculative models to predict the LLM's outputs; the predictions are organized as a token tree, whose nodes each represent a candidate token sequence. The correctness of all candidate token sequences represented by a token tree is verified against the LLM in parallel using a novel tree-based parallel decoding mechanism. SpecInfer uses an LLM as a token tree verifier instead of an incremental decoder, which significantly reduces the end-to-end latency and computational requirement for serving generative LLMs while provably preserving model quality. Our evaluation shows that SpecInfer outperforms existing LLM serving systems by 1.5-2.8x for distributed LLM inference and by 2.6-3.5x for offloading-based LLM inference, while preserving the same generative performance. SpecInfer is publicly available at https://github.com/flexflow/FlexFlow/
BibTeX
@inproceedings{miao2024specinfer,
  author = {Xupeng Miao and Gabriele Oliaro and Zhihao Zhang and Xinhao Cheng and Zeyu Wang and Zhengxin Zhang and Rae Ying Yee Wong and Alan Zhu and Lijie Yang and Xiaoxiang Shi and Chunan Shi and Zhuoming Chen and Daiyaan Arfeen and Reyna Abhyankar and Zhihao Jia},
  title = {{SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification}},
  booktitle = {ASPLOS},
  year = {2024},
  doi = {10.1145/3620666.3651335},
}
Figure