# TETRIS: Optimal Draft Token Selection for Batch Speculative Decoding

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

## Key facts

- Cited by 15 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 22 of its 36 references that are in the map.
- First posted on arXiv 21 Feb 2025.

## Placed in

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

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

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [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)
- [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023)
- [Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding](https://mlsanity.com/paper/2401.07851/) (2024)
- [Speculative Decoding with Big Little Decoder](https://mlsanity.com/paper/2302.07863/) (2023)
- [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023)
- [Large Language Models for Robotics: A Survey](https://mlsanity.com/paper/2311.07226/) (2023)
- [PEARL: Parallel Speculative Decoding with Adaptive Draft Length](https://mlsanity.com/paper/2408.11850/) (2024)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengths](https://mlsanity.com/paper/2405.19715/) (2024)
- [OPT-Tree: Speculative Decoding with Adaptive Draft Tree Structure](https://mlsanity.com/paper/2406.17276/) (2024)
- [Andes: Defining and Enhancing Quality-of-Experience in LLM-Based Text Streaming Services](https://mlsanity.com/paper/2404.16283/) (2024)
- [TurboSpec: Closed-loop Speculation Control System for Optimizing LLM Serving Goodput](https://mlsanity.com/paper/2406.14066/) (2024)
- [AdaEDL: Early Draft Stopping for Speculative Decoding of Large Language Models via an Entropy-based Lower Bound on Token Acceptance Probability](https://mlsanity.com/paper/2410.18351/) (2024)
- [Closer Look at Efficient Inference Methods: A Survey of Speculative Decoding](https://mlsanity.com/paper/2411.13157/) (2024)
- [Minions: Accelerating Large Language Model Inference with Aggregated Speculative Execution](https://mlsanity.com/paper/2402.15678/) (2024)

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

- [ECHO: Elastic Speculative Decoding with Sparse Gating for High-Concurrency Scenarios](https://mlsanity.com/paper/2604.09603/) (2026)
- [MoE-SpeQ: Speculative Quantized Decoding with Proactive Expert Prefetching and Offloading for Mixture-of-Experts](https://mlsanity.com/paper/2511.14102/) (2025)
- [Nightjar: Dynamic Adaptive Speculative Decoding for Large Language Models Serving](https://mlsanity.com/paper/2512.22420/) (2025)
- [D-cut: Adaptive Verification Depth Pruning for Batched Speculative Decoding](https://mlsanity.com/paper/2607.14647/) (2026)
- [Speculative Verification: Exploiting Information Gain to Refine Speculative Decoding](https://mlsanity.com/paper/2509.24328/) (2025)
- [Correctness Forensics for Batch Speculative Decoding: Diagnosing the Ragged Tensor Problem](https://mlsanity.com/paper/2510.22876/) (2025)
- [MineDraft: A Framework for Batch Parallel Speculative Decoding](https://mlsanity.com/paper/2603.18016/) (2026)
- [FASER: Fine-Grained Phase Management for Speculative Decoding in Dynamic LLM Serving](https://mlsanity.com/paper/2604.20503/) (2026)
- [Delay-Adaptive Speculation Control for Low-Latency Edge-Cloud LLM Inference](https://mlsanity.com/paper/2606.20591/) (2026)
- [The Limits of Speculation: Bounding Speculative Decoding in Mixture-of-Experts](https://mlsanity.com/paper/2609.22156/) (2026)
- [Uncovering Scaling Laws for Large Language Models via Inverse Problems](https://mlsanity.com/paper/2509.07909/) (2025)
- [AI-Model Network: Concept, Current State and Future](https://mlsanity.com/paper/2606.27382/) (2026)
- [Fully Rotation-Equivariant Spectral-Spatial Learning for Multispectral Object Detection](https://mlsanity.com/paper/2607.05148/) (2026)
- [CAST: Cost-Aware Speculative Trees from One-Pass Block Drafters](https://mlsanity.com/paper/2610.00321/) (2026)
- [SP2ec: Adaptive Self-Speculative Decoding for Vision-Language Models](https://mlsanity.com/paper/2610.18735/) (2026)

## Abstract (arXiv)

We propose TETRIS, a novel method that optimizes the total throughput of batch speculative decoding in multi-request settings. Unlike existing methods that optimize for a single request or a group of requests as a whole, TETRIS actively selects the most promising draft tokens (for every request in a batch) to be accepted when verified in parallel, resulting in fewer rejected tokens and hence less wasted computing resources. Such an effective resource utilization to achieve fast inference in large language models (LLMs) is especially important to service providers with limited inference capacity. Compared to baseline speculative decoding, TETRIS yields a consistently higher acceptance rate and more effective utilization of the limited inference capacity. We show theoretically and empirically that TETRIS outperforms baseline speculative decoding and existing methods that dynamically select draft tokens, leading to a more efficient batch inference in LLMs.