Elamur Research⌕
☰
home / papers / 2023 / SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification

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

Paper · 2023 · Xupeng Miao, Gabriele Oliaro, Zhihao Zhang et al.

Summary

Serving generative LLMs is slow and expensive because autoregressive decoding emits one token per step, which leaves GPUs underused and makes key-value caches costly in memory. Earlier speculative approaches let a single small model draft one token sequence for the LLM to check, but the large capacity gap between the two models limits how many drafted tokens survive. SpecInfer, built inside the FlexFlow framework, drafts many candidate continuations at once and arranges them as a token tree. The trees come from small speculative models (SSMs), which can be distilled, quantized, pruned or pre-trained smaller siblings of the LLM. The LLM is then used as a verifier rather than a step-by-step decoder: it checks every branch of the tree in a single decoding pass, using tree-based parallel decoding. A multi-step speculative sampling scheme keeps the output distribution identical to ordinary decoding, so quality is provably preserved. Reported speedups over existing serving systems are 1.5–2.8× for distributed multi-GPU inference and 2.6–3.5× for offloading-based single-GPU inference, with no change in generation quality.

Key points

  • Token trees raise the per-token verification success rate under stochastic decoding from roughly 52–57% (sequence-based speculation) to 96–97% (Table 1).
  • Trees are built in two ways. Expansion draws several candidates from one SSM, and merging combines the outputs of multiple SSMs.
  • SSMs are typically 100–1000× smaller than the target LLM. For example, OPT-125M and OPT-350M were pre-trained on the same data as OPT-175B and can serve directly as drafters.
  • The search space is very large. OPT models have a 50,272-token vocabulary, and SpecInfer correctly guesses about 4 future tokens on average, which amounts to about 6×10¹⁸ possible combinations.
  • Code is released in the FlexFlow repository (github.com/flexflow/FlexFlow).

Interesting ideas

  • I1. Drafting many branches instead of one. A cheap model that is often wrong about the single best path can still usually contain the right answer among a few alternatives. This makes "generate many cheaply, verify once expensively" a useful pattern wherever a weak model assists a strong one.
  • I2. Attending only to a token's ancestors. Each tree node is processed as if its ancestors were its preceding context, so all branches fit into one forward pass of the LLM. This style of masking could be reused to score many candidate continuations in parallel, for example in reranking or constrained generation.
  • I3. Merging several small models as an ensemble of drafters. Combining predictions from different SSMs widens coverage of what the LLM might say. It is a practical way to use whatever small distilled or quantized variants are already available, for instance for a Ukrainian-tuned model family.
  • I4. Lossless acceleration as a design goal. The sampling procedure is built so the final output distribution is provably identical to plain decoding. Speedups therefore need no re-evaluation of model quality, which makes such an optimization much easier to adopt in production pipelines.
  • I5. Turning a latency problem into a verification problem. The LLM is treated as a checker rather than a generator. This reframing applies to other sequential bottlenecks where checking a proposal is cheaper or more parallel than producing it.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States506 works · 330,053 citations🎓Carnegie Mellon UniversityPittsburgh · United States598 works · 191,226 citations🎓Tsinghua UniversityBeijing · China415 works · 94,028 citations🎓Peking UniversityBeijing · China315 works · 43,267 citations🎓Shanghai Jiao Tong UniversityShanghai · China212 works · 19,544 citations🎓University of California San DiegoSan Diego · United States89 works · 54,032 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksHardware and Architecture · 167 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,894 works

Cite

Cite as Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang and Xiaoxiang Shi. 2023. SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification. ASPLOS 2024.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/3620666.3651335 · arXiv 2305.09781

@inproceedings{miao2023specinfer,
  title = {{SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification}},
  author = {Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang and Xiaoxiang Shi},
  booktitle = {ASPLOS 2024},
  year = {2023},
  doi = {10.1145/3620666.3651335},
  eprint = {2305.09781},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1145/3620666.3651335}
}

References

8 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020. [4] F Warren Burton. Spec…
  2. PMLR, 2022. [10] Elias Frantar and Dan Alistarh. Sparsegpt: Massive language models can be accurately pruned in one-shot, 2023. [11] Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Gptq: Accurate quantization for generative pre-trained transformers. In International Conference on L… find
  3. Citeseer, 1996. [14] Mudasir A Ganaie, Minghui Hu, AK Malik, M Tanveer, and PN Suganthan. Ensemble deep learning: A review. Engineering Applications of Artificial Intelligence, 115:105151, 2022. [15] Aaron Gokaslan*, Vanya Cohen*, Ellie Pavlick, and Stefanie Tellex. Openwebtext corpus. http://Skylio… find
  4. OpenWebTextCorpus, 2019. [16] John L Hennessy and David A Patterson. Computer architecture: a quantitative approach. find
  5. Elsevier, 2011. [17] Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Joseph Naor, and Daniel Soudry. Accelerated sparse neural training: A provable and efficient method to find n: m transposable masks. Advances in Neural Information Processing Systems, 34:21099–21111, 2021. [18] HuggingFace. La… find
  6. USENIX Association, July 2021. [51] Heming Xia, Tao Ge, Si-Qing Chen, Furu Wei, and Zhifang Sui. Speculative decoding: Lossless speedup of autoregressive translation. [52] Guangxuan Xiao, Ji Lin, Mickael Seznec, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantiza… find
  7. George Zerveas, Vijay Korthikanti, et al. Using deepspeed and megatron to train megatron-turing nlg 530b, a large-scale generative language model. arXiv preprint arXiv:2201.11990, 2022. [44] Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autoregressive models…
  8. IEEE, 2021. [50] Haojie Wang, Jidong Zhai, Mingyu Gao, Zixuan Ma, Shizhi Tang, Liyan Zheng, Yuanzhi Li, Kaiyuan Rong, Yuanyong Chen, and Zhihao Jia. PET: Optimizing tensor programs with partially equivalent transformations and automated corrections. In 15th USENIX Symposium on find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/miao-2023-specinfer-accelerating-generative-large-language/