Tetris : Optimal Draft Token Selection for Batch Speculative Decoding
Zhaoxuan Wu, Zijian Zhou, Arun Verma, Alok Prakash, Daniela Rus, Bryan Kian Hsiang Low · 2025
Read Tetris : Optimal Draft Token Selection for Batch Speculative Decoding by Zhaoxuan Wu, Zijian Zhou, Arun Verma, Alok Prakash, Daniela Rus, Bryan Kian Hsiang Low (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15197.txt.
Introduction
Zhaoxuan Wu and a team of co-authors present a method to speed up large language models, in two thousand twenty-five. Their method is called TETRIS, and it works when many requests are served at once. A fast draft step proposes words, and a larger model then checks them in parallel.
Older methods pick draft words for one request, or for a whole group at once. TETRIS picks the most promising draft words for each request in the batch. That choice means fewer words are rejected and less computing power is wasted. Tests and theory both showed higher acceptance rates than the older ways, which matters for providers with limited capacity.
Catalog record
| CREATOR | Zhaoxuan Wu, Zijian Zhou, Arun Verma, Alok Prakash, Daniela Rus, Bryan Kian Hsiang Low |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-15197
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tetris : Optimal Draft Token Selection for Batch Speculative Decoding Zhaoxuan Wu, Zijian Zhou, Arun Verma, Alok Prakash, Daniela Rus, Bryan Kian Hsiang Low Abstract 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. 0 0 footnotetext: * Equal contribution. 1 Introduction Transformer-based large language models (LLMs) have shown remarkable abilities to solve different tasks across various domains, such as natural language ( Zhao et al., 2023 ) , computer vision ( Yin et al., 2024 ) , robotics ( Zeng et al., 2023 ) , code generation ( Rozière et al., 2024 ) , among others ( Maslej et al., 2024 ) . However, the autoregressive nature of LLMs (i.e., generating one token at a time) leads to an increasingly sluggish inference speed as the model size increases. To address this problem, a recent widely-used approach is speculative decoding (SD) ( Cai et al., 2024 ; Cheng et al., 2024 ; Leviathan et al., 2023 ; Li et al., 2024a ; Li et al., 2024b ) : It achieves faster inference by using a small draft model to rapidly generate a sequence of (draft) tokens and then a large target model to verify whether to accept or reject them in parallel. When a token is rejected, the draft model generates a new sequence of tokens in the next step, starting from the most recently accepted token. A key aspect of SD is to determine the optimal number of draft tokens (i.e., draft window size ) to generate and verify in each step. Generating more draft tokens allows the target model to verify a longer sequence at once (given sufficient computing resources/capacity for parallel inferences), which can potentially boost inference speed. However, doing so increases the risk of wasting computing resources since all tokens following the first rejected token must be discarded. In contrast, generating fewer draft tokens reduces this risk but limits the potential benefit of SD since the computing resources are not effectively utilized. Therefore, the optimal selection of draft tokens that would be accepted when verified by the target model in parallel is critical to improving both inference speed and resource utilization ( Liu et al., 2024d ) . Figure 1: Standard SD (left) uses a fixed draft window size, while Tetris (right) generates extra draft tokens and dynamically optimizes draft token selection for every request in a batch, resulting in more accepted tokens. Most existing works have focused on optimizing draft token selection for individual user requests ( Agrawal et al., 2024 ; Huang et al., 2024 ; Liu et al., 2024c ; Mamou et al., 2024 ) , but may not work well for profit-driven LLM inference service providers who must manage multiple user requests under a limited inference capacity. Moreover, LLM inference service providers typically charge users based on the number of tokens served ( Fireworks AI, 2025 ; Replicate, 2025 ) . Hence, they are incentivized to maximize the total number of tokens served (i.e., throughput ) across all user requests while ensuring fast response time to meet service level agreement ( Wieder et al., 2011 ) . So, they would employ computing clusters to process large batches of user requests simultaneously and use SD to further improve the inference speed. Such batch processing of user requests entails a fundamentally different optimization objective for SD compared to handling individual requests. For SD of a single request, supposing a fast draft model with negligible runtime, the objective is to maximize the draft window size as long as the target model can verify all draft tokens in parallel by fully utilizing the inference capacity. It can be naively extended to batch processing by widening the draft window for all requests until the inference capacity is reached. This is inefficient as each request may require a different optimal draft token selection due to varying difficulty in speculation (i.e., generating tokens to match the target model’s outputs). This paper presents a theoretical framework that dynamically optimizes the draft token selection for every user request from the perspective of a capacity-limited LLM inference service provider who aims to maximize resource utilization. Since draft token verification is the most time-consuming component of SD, we propose Tetris , a method that greedily selects draft tokens with a high likelihood of acceptance by the target model. The name of our method is derived from the shape of its selected tokens, as shown in Fig. 1 . We demonstrate that Tetris strictly outperforms standard SD by achieving higher total throughput. Our work bridges a critical yet overlooked gap in current research, allowing service providers to improve total throughput with batch SD. The specific contributions of our work here are summarized below: \bullet In Section 3 , we introduce the problem of optimal draft token selection in multi-request settings, and in Section 4.1 , we propose Tetris , a novel method that selects optimal draft tokens in log-linear time for the target model’s verification. \bullet In Section 4.2 , we theoretically show that Tetris achieves optimal throughput at each decoding step and globally in the absence of drafting time (i.e., time to generate draft tokens) under reasonable token acceptance assumptions. \bullet In Section 5 , our empirical results show that Tetris consistently outperforms standard SD and existing methods that use dynamic draft windows for a batch in terms of total throughput and end-to-end latency (including drafting time), highlighting the potential of Tetris to improve inference speed in real-world model service deployments. 2 Related Work Speculative Decoding (SD). By employing a draft-then-verify strategy for lossless accelerations of LLM inference, SD has attracted significant attention recently ( Ryu and Kim, 2024 ; Xia et al., 2024 ) . Recent advancements based on SD have focused on developing more efficient draft models by producing multiple drafts for the next few tokens ( Cai et al., 2024 ; Cheng et al., 2024 ; Li et al., 2024b ) . Additionally, some methods have optimized the speculation accuracy by aligning the draft model with the target model ( Liu et al., 2024e ; Zhou et al., 2024a ) or leveraging the target model itself to draft via techniques like layer skipping ( Zhang et al., 2024 ) . To facilitate more efficient verification, tree attention has been proposed for speedy tree-structured candidate verification ( Miao et al., 2024 ; Spector and Re, 2023 ) . In contrast, our work explores a complementary approach that intervenes between