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

This paper introduces SpecInfer, a novel system that significantly speeds up the serving of large language models (LLMs) by using a tree-based speculative inference and verification approach. By organizing speculative token predictions into a tree and verifying them in parallel with the LLM, SpecInfer achieves up to 3.5x faster inference while maintaining model quality.

What Problem Does This Paper Address?

Serving large language models (LLMs) like GPT-3 and GPT-4 is computationally expensive and slow due to their massive size and complex architectures. Traditional methods, known as incremental decoding, generate tokens one by one, leading to sequential dependencies and underutilization of hardware. While speculative decoding has been proposed to speed this up by using smaller models to predict tokens, existing methods only consider a single predicted sequence, which often fails to align with the LLM's output due to the significant model capacity gap. This results in limited speedups and can still be a bottleneck for real-time applications.

Methods

SpecInfer tackles this challenge with a two-pronged approach:

  • Tree-based Speculative Inference: Instead of a single speculative sequence, SpecInfer uses "small speculative models" (SSMs) to generate a tree of candidate token sequences. This tree structure allows SpecInfer to explore a much wider range of possibilities and increases the chances of finding a sequence that aligns with the LLM's output. Two methods are used to construct these trees:
  • Expansion-based: Leverages the top-k tokens from a single SSM to create multiple branches in the tree, recognizing that LLM-selected tokens are often within the top few predictions of smaller models.
  • Merge-based: Combines outputs from multiple SSMs to create a more diverse set of speculative sequences, effectively boosting the speculative performance.
  • Tree-based Parallel Decoding and Verification: The LLM is used as a verifier, not an incremental decoder. SpecInfer employs a novel "tree-based parallel decoding" mechanism to efficiently compute attention scores for all tokens within the speculative tree simultaneously. This allows the LLM to verify multiple speculated tokens in a single pass, drastically reducing latency and computational requirements. This is achieved through techniques like "topology-aware causal mask" to handle the tree structure and a depth-first search for efficient key-value cache updates.

Datasets

The paper evaluates SpecInfer on several standard datasets commonly used for LLM prompting and instruction following:

  • Chatbot Instruction Prompts (CIP)
  • ChatGPT Prompts (CP)
  • WebQA
  • Alpaca
  • PIQA

These datasets are used to simulate real-world conversation traces and evaluate the performance of SpecInfer across various prompting scenarios.

Key Insights and Ideas

  • Tree structure is key for speculative performance: By organizing speculative predictions into a tree, SpecInfer can explore a much larger hypothesis space than single-sequence methods, significantly increasing the probability of successful speculation.
  • LLM as a parallel verifier, not a sequential decoder: Shifting the LLM's role from an incremental token generator to a parallel verifier of speculative trees is a core innovation that unlocks significant speedups.
  • Leveraging diverse SSMs and expansion: Combining multiple smaller models (SSMs) or expanding the predictions from a single SSM allows SpecInfer to better cover the LLM's potential outputs, bridging the capacity gap.
  • Efficient tree-based attention: Novel techniques for handling attention mechanisms on tree structures are crucial for parallel verification and avoiding redundant computations.

Key Results

SpecInfer demonstrates substantial performance improvements across different LLM serving scenarios:

  • Distributed LLM Inference: SpecInfer achieves 1.5-2.8x speedup compared to existing systems like vLLM and HuggingFace TGI.
  • Offloading-based LLM Inference: SpecInfer provides a 2.6-3.5x speedup compared to systems like FlexGen, which is particularly impactful for scenarios where LLMs exceed single-GPU memory.
  • Preservation of Quality: Crucially, these speedups are achieved while provably preserving the same generative performance as traditional incremental decoding.
  • Verification Success: The tree-based approach significantly improves the token verification success rate, reaching 96-97% in some cases, compared to 52-57% for single-sequence methods.

Limitations and Future Work

  • Dynamic Tree Expansion: The paper acknowledges that dynamically expanding the token tree based on real-time performance is an open research problem and leaves it as future work. Currently, a static expansion configuration is used.
  • Other Ensemble Learning Methods: While merge-based tree construction uses adaptive boosting, the authors suggest exploring other ensemble learning methods like voting, bagging, and stacking.
  • Hardware Requirements: The experiments were conducted on AWS g5.12xlarge instances, and reproducing the results requires similar hardware.
  • Complexity of Tree Construction: While effective, the expansion and merge strategies for tree construction add complexity compared to simpler speculative methods.

The authors suggest that SpecInfer's techniques are orthogonal to existing hardware optimization methods (like TVM or Ansor) and can be combined for further acceleration.

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.8× for distributed LLM inference and by 2.6-3.5× 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