# SpecTr: Fast Speculative Decoding via Optimal Transport

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

## Key facts

- Cited by 129 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 15 of its 29 references that are in the map.
- First posted on arXiv 23 Oct 2023.

## Placed in

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

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [LaMDA: Language Models for Dialog Applications](https://mlsanity.com/paper/2201.08239/) (2022)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [One Billion Word Benchmark for Measuring Progress in Statistical Language Modeling](https://mlsanity.com/paper/1312.3005/) (2013)
- [Controlling Linguistic Style Aspects in Neural Language Generation](https://mlsanity.com/paper/1707.02633/) (2017)
- [Inference with Reference: Lossless Acceleration of Large Language Models](https://mlsanity.com/paper/2304.04487/) (2023)
- [Lossless Acceleration for Seq2seq Generation with Aggressive Decoding](https://mlsanity.com/paper/2205.10350/) (2022)

## Built on by (most cited first, 30 of 129)

- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test](https://mlsanity.com/paper/2503.01840/) (2025)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding](https://mlsanity.com/paper/2401.07851/) (2024)
- [A Survey on Efficient Inference for Large Language Models](https://mlsanity.com/paper/2404.14294/) (2024)
- [LLM Inference Unveiled: Survey and Roofline Model Insights](https://mlsanity.com/paper/2402.16363/) (2024)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [Language Model Cascades: Token-level uncertainty and beyond](https://mlsanity.com/paper/2404.10136/) (2024)
- [Fast Best-of-N Decoding via Speculative Rejection](https://mlsanity.com/paper/2410.20290/) (2024)
- [Reward-Guided Speculative Decoding for Efficient LLM Reasoning](https://mlsanity.com/paper/2501.19324/) (2025)
- [Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding](https://mlsanity.com/paper/2402.12374/) (2024)
- [TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding](https://mlsanity.com/paper/2404.11912/) (2024)
- [A Survey of Resource-efficient LLM and Multimodal Foundation Models](https://mlsanity.com/paper/2401.08092/) (2024)
- [Universal Model Routing for Efficient LLM Inference](https://mlsanity.com/paper/2502.08773/) (2025)
- [GliDe with a CaPE: A Low-Hassle Method to Accelerate Speculative Decoding](https://mlsanity.com/paper/2402.02082/) (2024)
- [SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengths](https://mlsanity.com/paper/2405.19715/) (2024)
- [Learning Harmonized Representations for Speculative Sampling](https://mlsanity.com/paper/2408.15766/) (2024)
- [SWIFT: On-the-Fly Self-Speculative Decoding for LLM Inference Acceleration](https://mlsanity.com/paper/2410.06916/) (2024)
- [Accelerating Auto-regressive Text-to-Image Generation with Training-free Speculative Jacobi Decoding](https://mlsanity.com/paper/2410.01699/) (2024)
- [TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling](https://mlsanity.com/paper/2410.16033/) (2024)
- [Kangaroo: Lossless Self-Speculative Decoding via Double Early Exiting](https://mlsanity.com/paper/2404.18911/) (2024)
- [SpecExec: Massively Parallel Speculative Decoding for Interactive LLM Inference on Consumer Devices](https://mlsanity.com/paper/2406.02532/) (2024)
- [Speculative Streaming: Fast LLM Inference without Auxiliary Models](https://mlsanity.com/paper/2402.11131/) (2024)
- [Faster Cascades via Speculative Decoding](https://mlsanity.com/paper/2405.19261/) (2024)
- [Recurrent Drafter for Fast Speculative Decoding in Large Language Models](https://mlsanity.com/paper/2403.09919/) (2024)
- [Multi-Candidate Speculative Decoding](https://mlsanity.com/paper/2401.06706/) (2024)
- [Accelerated Diffusion Models via Speculative Sampling](https://mlsanity.com/paper/2501.05370/) (2025)
- [Accelerating Parallel Sampling of Diffusion Models](https://mlsanity.com/paper/2402.09970/) (2024)
- [A Theoretical Perspective for Speculative Decoding Algorithm](https://mlsanity.com/paper/2411.00841/) (2024)

## Abstract (arXiv)

Autoregressive sampling from large language models has led to state-of-the-art results in several natural language tasks. However, autoregressive sampling generates tokens one at a time making it slow, and even prohibitive in certain tasks. One way to speed up sampling is textitspeculative decoding: use a small model to sample a textitdraft (block or sequence of tokens), and then score all tokens in the draft by the large language model in parallel. A subset of the tokens in the draft are accepted (and the rest rejected) based on a statistical method to guarantee that the final output follows the distribution of the large model. In this work, we provide a principled understanding of speculative decoding through the lens of optimal transport (OT) with textitmembership cost. This framework can be viewed as an extension of the well-known textitmaximal-coupling problem. This new formulation enables us to generalize the speculative decoding method to allow for a set of k candidates at the token-level, which leads to an improved optimal membership cost. We show that the optimal draft selection algorithm (transport plan) can be computed via linear programming, whose best-known runtime is exponential in k. We then propose a valid draft selection algorithm whose acceptance probability is (1-1/e)-optimal multiplicatively. Moreover, it can be computed in time almost linear with size of domain of a single token. Using this new draft selection algorithm, we develop a new autoregressive sampling algorithm called textitSpecTr, which provides speedup in decoding while ensuring that there is no quality degradation in the decoded output. We experimentally demonstrate that for state-of-the-art large language models, the proposed approach achieves a wall clock speedup of 2.13X, a further 1.37X speedup over speculative decoding on standard benchmarks.