Polybasic Speculative Decoding Through a Theoretical Perspective

Ruilin Wang, Huixia Li, Yuexiao Ma, Xiawu Zheng, Fei Chao, Xuefeng Xiao, Rongrong Ji · 2025

Read Polybasic Speculative Decoding Through a Theoretical Perspective by Ruilin Wang, Huixia Li, Yuexiao Ma, Xiawu Zheng, Fei Chao, Xuefeng Xiao, Rongrong Ji (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-2510-26527.txt.

Introduction

Ruilin Wang, with six co-authors, speeds up the slow step of running large language models. Their method is speculative decoding, where a small model drafts the next words and a big model checks them, which keeps output the same while saving time. Most work uses just two models in that draft-and-check loop, with little theory behind the design.

Wang and the team propose a polybasic version that can use several models at once, backed by a full theoretical analysis. They prove a basic theorem that pins down the best possible inference time for such multi-model systems. Tests across model families gave speedups of roughly three to four times, while the output distribution stayed unchanged. Code and proofs are released for others to build on.

Catalog record

CREATORRuilin Wang, Huixia Li, Yuexiao Ma, Xiawu Zheng, Fei Chao, Xuefeng Xiao, Rongrong Ji
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-26527

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Polybasic Speculative Decoding Through a Theoretical Perspective Ruilin Wang, Huixia Li, Yuexiao Ma, Xiawu Zheng, Fei Chao, Xuefeng Xiao, Rongrong Ji Abstract Inference latency stands as a critical bottleneck in the large-scale deployment of Large Language Models (LLMs). Speculative decoding methods have recently shown promise in accelerating inference without compromising the output distribution. However, existing work typically relies on a dualistic draft-verify framework and lacks rigorous theoretical grounding. In this paper, we introduce a novel polybasic speculative decoding framework, underpinned by a comprehensive theoretical analysis. Specifically, we prove a fundamental theorem that characterizes the optimal inference time for multi-model speculative decoding systems, shedding light on how to extend beyond the dualistic approach to a more general polybasic paradigm. Through our theoretical investigation of multi-model token generation, we expose and optimize the interplay between model capabilities, acceptance lengths, and overall computational cost. Our framework supports both standalone implementation and integration with existing speculative techniques, leading to accelerated performance in practice. Experimental results across multiple model families demonstrate that our approach yields speedup ratios ranging from 3.31 × 3.31\times to 4.01 × 4.01\times for LLaMA2-Chat 7B, up to 3.87 × 3.87\times for LLaMA3-8B, up to 4.43 × 4.43\times for Vicuna-7B and up to 3.85 × 3.85\times for Qwen2-7B—all while preserving the original output distribution. We release our theoretical proofs and implementation code to facilitate further investigation into polybasic speculative decoding. 1 Introduction Large Language Models (LLMs) have substantially advanced Natural Language Processing (NLP), achieving leading performance in a wide range of tasks. Yet their exceptional capabilities are tempered by significant computational demands, particularly in low-latency scenarios. Among multiple acceleration techniques, speculative decoding ( Stern et al. 2018 ; Leviathan et al. 2023 ; Xia et al. 2023 ; Chen et al. 2023a ; Anonymous 2025b ; Anonymous 2025a ; Teng et al. 2024 ; Zhang et al. 2024b ) has emerged as a strategy to speed up inference while preserving output fidelity. The current speculative decoding ecosystem largely hinges on draft-then-verify paradigms, which spawn various sub-directions such as the design of lightweight draft models ( Leviathan et al. 2023 ; Xia et al. 2023 ; Chen et al. 2023a ; Kim et al. 2024a ; Svirschevski et al. 2024 ; Yin et al. 2024 ; Sadhukhan et al. 2024 ) , hierarchical token structures ( Stern et al. 2018 ; Miao et al. 2024 ; Du et al. 2024 ) , and unified architectures ( Yi et al. 2024 ; Cai et al. 2024 ) . Verification strategies typically follow three approaches: greedy sampling, speculative sampling ( Leviathan et al. 2023 ) , and typical acceptance ( Cai et al. 2024 ) . Despite these efforts, current strategies remain limited by a dualistic relationship between draft and target models ( Qin et al. 2024 ; Liu et al. 2024 ; Gui et al. 2024 ; Khisti et al. 2024 ) , affecting key parameters such as acceptance length due to inherent capacity disparities between the two models. While some recent works ( Chen et al. 2023b ; Kim et al. ; Spector & Ré 2023 ) investigate multi-level drafts, they still employ a singular top-level target model. Moreover, the field has hitherto lacked an overarching theoretical framework to guide system design and provide robust performance guarantees. In this paper, we introduce a principled polybasic speculative decoding framework that uses multiple interconnected models, grounded in a thorough theoretical analysis. Our investigation yields two central insights. First, we derive a fundamental relationship between the number of forward passes and average acceptance lengths that dictates optimal system-level inference speed. This relationship allows us to precisely quantify potential inference speedups when adding additional models. Second, we establish the capacity of speculative sampling to enhance stability in acceptance lengths. By optimizing sampling parameters, we can reduce variance in token acceptance to achieve more predictable performance. Building on these insights, we propose a unified architecture for polybasic speculative decoding wherein multiple draft models coordinate with each other and with a single target model. Our implementation guidelines detail how to select models, set speculation lengths, and implement multi-stage verification procedures that maximize throughput. Experimental evaluations demonstrate that this approach outperforms typical dualistic methods on diverse tasks including MT-bench ( Zheng et al. 2023 ) , translation, summarization, QA, mathematical reasoning, and Retrieval-Augmented Generation (RAG). Our empirical results indicate that the proposed polybasic framework maintains output fidelity while delivering speedup ratios from 3\times to over 4\times across a range of widely used LLMs (e.g., Vicuna-7B, LLaMA2-Chat 7B, LLaMA3-8B). The main contributions of this work are summarized as follows: • We develop a formal theoretical framework for polybasic speculative decoding, identifying the system-level dependencies between model forward-pass cost, acceptance lengths, and stable acceleration performance. • We prove a fundamental theorem that provides a rigorous expression for optimal inference time in multi-model speculative decoding, highlighting conditions under which additional models improve speedups. • We show that speculative sampling significantly reduces variance in token acceptance lengths for multi-model settings, increasing stability and improving inference throughput. • Our empirical investigation demonstrates the effectiveness of the proposed polybasic approach, achieving notable speedups (up to 4.43\times ) on widely used LLMs across various tasks, while preserving the target model’s output distribution. 2 Related Work The concept of speculative decoding originated from blockwise parallel decoding ( Stern et al. 2018 ) , showcasing the viability of partially parallel language generation. More recently, research on speculative decoding ( Stewart et al. 2024 ; Zafrir et al. 2024 ) has coalesced around two dimensions: drafting strategies for token prediction and verification mechanisms for ensuring correctness. Drafting Strategies. Drafting approaches typically follow either independent or self-drafting protocols. Independent drafting involves utilizing smaller or more efficient models to propose candidate tokens, later verified by a larger model. Methods range from training specialized drafters ( Leviathan et al. 2023 ; Xia et al. 2023 ; Chen et al. 2023a ; Kim et al. 2024a ; Metel et al. 2024 ) to zero-shot usage of pre-existing models ( Spector & Ré 2023 ) . Self-drafting employs the same model at intermediate stages, as in blockwise decoding ( Stern et al. 2018 ; Xiao et al. 2024 ) , early exiting ( Yang et al. 2023 ) , or mask-predict ( Zhao et al. 2024 ) , aiming to amortize computation within the same architecture. Verification Mechanisms. Verification primarily ensures that proposed tokens maintain consistency with the target distribution. Greedy verification ( Kim et al. 2024a ; Xia et al. 2023 ; Agrawal et al. 2024 ) is conceptually straightforward but may hinder speedups for certain tasks. Speculative sampling ( Leviathan et al. 2023 ) introduces a probabilistic acceptance rule that adaptively filters tokens while retaining a high acceptance length. Token-tree-based verification ( Miao et al. 2024 ; Spector & Ré 2023 ; Lu et al. 2024 ; Gao et al. 2024 ) provides hierarchical checks, which can be beneficial for highly parallel architectures. Recent Advances and Limitations. Recent work on cascade or multi-level drafting ( Chen et al. 2023b ; Sun et al. 2024 ) has partially moved beyond the dualistic draft-target scheme. TRIFORCE ( Sun et al. 2024 ) tackles long sequence generation by introducing a two-level hierarchy with retrieval-based drafting and

Read the complete text