Speculative Decoding for Multi-Sample Inference (2025)

Abstract: We propose a novel speculative decoding method tailored for multi-sample reasoning scenarios, such as self-consistency and Best-of-N sampling. Our method exploits the intrinsic consensus of parallel generation paths to synthesize high-quality draft tokens without requiring auxiliary models or external databases. By dynamically analyzing structural patterns across parallel reasoning paths through a probabilistic aggregation mechanism, it identifies consensus token sequences that align with the decoding distribution. Evaluations on mathematical reasoning and code generation benchmarks demonstrate a substantial improvement in draft acceptance rates over baselines, while reducing the latency in draft token construction. This work establishes a paradigm shift for efficient multi-sample inference, enabling seamless integration of speculative decoding with sampling-based reasoning techniques.

## introduction nowadays, large language models (llms) increasingly rely on multi-sample aggregation strategies, such as majority voting (self-consistency) @xcite and @xcite , to enhance prediction accuracy in complex reasoning tasks. by generating and aggregating multiple candidate outputs, these methods mitigate individual sampling errors and improve task performance, particularly in mathematical reasoning @xcite . however, this benefit comes at a significant computational cost: generating multiple samples inherently prolongs inference latency, posing a critical challenge for real-world applications where efficiency is paramount. to address latency issues, speculative decoding @xcite @xcite has emerged as a promising acceleration method. by predicting draft tokens in advance † corresponding authors. and verifying them against the original llm, this approach reduces the number of full autoregressive steps. however, existing methods depend on external draft models @xcite or retrievalaugmented databases @xcite to generate drafts, introducing three critical limitations: first, draft tokens sourced externally struggle to fully align with the original llm's output distribution, which lowers token acceptance rates and diminishes the potential speedup. second, querying these external modules or databases inevitably incurs additional latency. third, relying on auxiliary resources incurs extra costs-training a draft model or maintaining a database require additional computational and storage overhead. a critical observation motivates our work: multisample inference yields a rich reservoir of highquality draft tokens. when generating multiple parallel reasoning paths (e.g., for majority voting), the llm produces outputs that, while varied in expression, are all drawn from the same underlying distribution. frequently, these outputs share common substeps-such as intermediate equations in math problems-while differing in ordering or phrasing. importantly, because all paths stem from the same model, their substeps naturally mirror its output tendencies, unlike externally sourced drafts. this inherent alignment makes them ideal candidates for speculative decoding, provided we can effectively extract and aggregate consensus patterns. in this paper, we introduce a novel speculative decoding method explicitly designed for multisample reasoning scenarios. our approach begins by leveraging the overlapping token subsequences generated across parallel reasoning paths to build a dynamic draft token pool. at each inference step, the most recent tokens from any path are used as queries to retrieve matching prefixes from other paths via suffix-based matching. the tokens immediately following these matches are aggregated as candidate drafts. these candidates are then orga-nized into a weighted directed acyclic graph (dag), where the edge weights reflect transition probabilities derived from the llm's distribution. a confidence-weighted search is performed on this dag to extract the highest-likelihood token sequence-prioritizing paths with strong agreement. this consensus-driven process yields draft tokens that closely align with the model's output distribution, ultimately accelerating inference by reducing the number of full autoregressive steps without the need for external modules or datastores. we evaluate our method on four benchmarks using three widely adopted llms under multisample inference settings. our approach achieves much higher token acceptance rate at identical draft lengths, demonstrating superior alignment with the original model's distribution. crucially, the draft construction process incurs lower latency than baselines, as it eliminates costly database queries or auxiliary model inferences. ## background multi-sample inference aggregation strategies aim to enhance reasoning reliability by generating and aggregating multiple candidate outputs. let @xmath0, y 2 , . . . , y n } denote n parallel samples drawn from a language model p θ . two dominant paradigms include: while aggregation techniques enhance accuracy, generating multiple samples increases latency, thereby motivating the development of acceleration methods. speculative decoding speculative decoding reduces inference latency by predicting k-step draft tokens {ỹ 1 , . . . , ỹk } in advance from draft model q and verifying them via the original model p θ . traditional approaches rely on an auxiliary draft model or a retrieval datastore d to propose drafts. for each step t: ## method our method transforms the inherent consensus of multi-sample reasoning paths into high-quality draft tokens through three key components: (1) dynamic construction of a draft pool via cross-path suffix searching, (2) fuzzy suffix matching to handle lexical variations and (3) extraction of consensus subsequences using a dag structure built over aligned reasoning paths. the entire process operates during parallel decoding, requiring no external models or datastores. please refer to appendix a for the algorithm. ## conclusion we present a speculative decoding method that leverages consensus patterns from parallel reasoning paths to accelerate multi-sample inference, eliminating external dependencies. by dynamically synthesizing draft tokens through probabilistic aggregation and graph-based selection, our approach achieves higher acceptance rates and lower latency than baselines. this work bridges speculative decoding with sampling-based reasoning, establishing a resource-efficient paradigm for accelerating llms while preserving their output distribution. this approach could pave the way for the implementation of efficient multi-sample strategies in real-world applications.