# Graph-Structured Speculative Decoding

arXiv: https://arxiv.org/abs/2407.16207 · HTML: https://mlsanity.com/paper/2407.16207/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving.
- Builds on 19 of its 28 references that are in the map.
- First posted on arXiv 23 Jul 2024.

## Placed in

- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [QLoRA: Efficient Finetuning of Quantized LLMs](https://mlsanity.com/paper/2305.14314/) (2023)
- [BLOOM: A 176B-Parameter Open-Access Multilingual Language Model](https://mlsanity.com/paper/2211.05100/) (2022)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Don't Give Me the Details, Just the Summary! Topic-Aware Convolutional Neural Networks for Extreme Summarization](https://mlsanity.com/paper/1808.08745/) (2018)
- [TinyBERT: Distilling BERT for Natural Language Understanding](https://mlsanity.com/paper/1909.10351/) (2019)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [MiniLMv2: Multi-Head Self-Attention Relation Distillation for Compressing Pretrained Transformers](https://mlsanity.com/paper/2012.15828/) (2020)
- [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023)
- [Compression of Generative Pre-trained Language Models via Quantization](https://mlsanity.com/paper/2203.10705/) (2022)
- [ALP-KD: Attention-Based Layer Projection for Knowledge Distillation](https://mlsanity.com/paper/2012.14022/) (2020)
- [Super Tickets in Pre-Trained Language Models: From Model Compression to Improving Generalization](https://mlsanity.com/paper/2105.12002/) (2021)

## Built on by (most cited first, 4 of 4)

- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Speculative Decoding and Beyond: An In-Depth Survey of Techniques](https://mlsanity.com/paper/2502.19732/) (2025)
- [Fast Large Language Model Collaborative Decoding via Speculation](https://mlsanity.com/paper/2502.01662/) (2025)
- [FIRP: Faster LLM inference via future intermediate representation prediction](https://mlsanity.com/paper/2410.20488/) (2024)

## Abstract (arXiv)

Speculative decoding has emerged as a promising technique to accelerate the inference of Large Language Models (LLMs) by employing a small language model to draft a hypothesis sequence, which is then validated by the LLM. The effectiveness of this approach heavily relies on the balance between performance and efficiency of the draft model. In our research, we focus on enhancing the proportion of draft tokens that are accepted to the final output by generating multiple hypotheses instead of just one. This allows the LLM more options to choose from and select the longest sequence that meets its standards. Our analysis reveals that hypotheses produced by the draft model share many common token sequences, suggesting a potential for optimizing computation. Leveraging this observation, we introduce an innovative approach utilizing a directed acyclic graph (DAG) to manage the drafted hypotheses. This structure enables us to efficiently predict and merge recurring token sequences, vastly reducing the computational demands of the draft model. We term this approach Graph-structured Speculative Decoding (GSD). We apply GSD across a range of LLMs, including a 70-billion parameter LLaMA-2 model, and observe a remarkable speedup of 1.73× to 1.96×, significantly surpassing standard speculative decoding.