Unlocking Parallelism in Autoregressive Language Models via Speculative Decoding with Progressive Tree Drafting

# Unlocking Parallelism in Autoregressive Language Models via Speculative Decoding with Progressive Tree Drafting
Source: [https://arxiv.org/html/2607.10661](https://arxiv.org/html/2607.10661)
Zipeng Gao1Zhi Zheng1Qingrong Xia2Junda Lin1Ziwei Zhao1Tong Xu1Zhefeng Wang2Enhong Chen11State Key Laboratory of Cognitive Intelligence,University of Science and Technology of China2Huawei Technologies Co\., Ltd\.\{gaozp619,zhengzhi97,linjunda,zzw22222\}@mail\.ustc\.edu\.cn\{zhengzhi97,tongxu,cheneh\}@ustc\.edu\.cn\{xiaqingrong,wangzhefeng\}@huawei\.com

###### Abstract

Speculative decoding has significantly accelerated Large Language Model \(LLM\) inference by alleviating memory\-bound bottlenecks\. However, traditional speculative decoding typically relies on auxiliary draft modules, incurring significant training and communication overhead\. Although recent methods attempt to generate drafts within the target model itself, they often fail to fully exploit its latent parallel capacity due to a lack of structural coordination\. In this paper, we proposeProgressive Tree Drafting \(PTD\), which employs a structured, guided parallel drafting strategy to harness the model’s parallel potential\. By coupling a progressive tree structure with a stepwise pruning mechanism, PTD actively guides the LLM to explore multiple semantic paths in a single forward pass, ensuring both draft diversity and coherence\. Experiments demonstrate that PTD achieves up to2×2\\timesdecoding speedup across various benchmarks while remaining training\-free and model\-agnostic\. Our code is available at: https://github\.com/MINE\-USTC/PTD\.

## 1Introduction

Speculative decoding has emerged as an important paradigm for accelerating Large Language Model \(LLM\) inference, mitigating the memory\-bound bottlenecks inherent in autoregressive generation\(Yuan et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib21); Xia et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib19)\)\. By transforming the inefficient token\-by\-token processing into a candidate parallel verification process, this paradigm enhances computational utility and inference speed without compromising generation quality\.

The key to speculative decoding is obtaining high\-quality drafts\. Traditional approaches typically employ smaller auxiliary modules to generate drafts, which often incur significant communication overhead and require substantial training effort for model alignment\(Xia et al\.,[2023](https://arxiv.org/html/2607.10661#bib.bib18); Leviathan et al\.,[2023](https://arxiv.org/html/2607.10661#bib.bib11); Chen et al\.,[2023](https://arxiv.org/html/2607.10661#bib.bib5); Miao et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib16); Yang et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib20); Cai et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib4); Stern et al\.,[2018](https://arxiv.org/html/2607.10661#bib.bib17); Li et al\.,[2025](https://arxiv.org/html/2607.10661#bib.bib14)\)\. To mitigate these issues, recent research has shifted toward training\-free, model\-agnostic strategies that generate drafts directly within the target LLM itself\. For instance, Lookahead Decoding \(LADE\)\(Fu et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib8)\)supplements the primary decoding objective with a parallel Jacobi iteration task to predict and refine linear candidate sequences, while Self\-Draft\(Gao et al\.,[2025](https://arxiv.org/html/2607.10661#bib.bib9)\)leverages the intrinsic robustness of LLMs to incorporate an auxiliary drafting task, generating multiple candidate branches through input perturbations\.

While these methods confirm the feasibility of endogenous acceleration, we argue that the latent parallel processing capabilities inherent in AR models remain under\-exploited, primarily due to the independent and unstructured nature of their candidate generation\. Specifically, our in\-depth analysis reveals a critical bottleneck in this paradigm\. As quantified in Figure[2](https://arxiv.org/html/2607.10661#S1.F2)\(right\), our analysis of Self\-Draft shows that more than half of the decoding steps contain branches with over 80% similarity\. This high level of semantic redundancy suggests that simply generating independent linear branches fails to effectively direct the model’s parallel resources toward diverse drafting\. This observation motivates us to rethink: how can we more intentionally and structurally guide the model to transform its parallel potential into high\-quality, diverse drafts?

![Refer to caption](https://arxiv.org/html/2607.10661v1/x1.png)Figure 1:Paradigms of speculative decoding\. \(Left\) Traditional methods using auxiliary draft modules\. \(Right\) Endogenous, training\-free methods\.![Refer to caption](https://arxiv.org/html/2607.10661v1/x2.png)Figure 2:A drafting example \(left\) and the branch similarity analysis \(right\) of Self\-Draft\(Gao et al\.,[2025](https://arxiv.org/html/2607.10661#bib.bib9)\)\. The curve means the proportion of steps with at least two branches above the similarity threshold\.Building on this insight, we propose Progressive Tree Drafting \(PTD\), a novel strategy that reformulates drafting as a structured, guided parallel inference process\. By leveraging a tree structure to merge redundant prefixes, PTD eliminates the computational waste inherent in independent branching\. Furthermore, the integration of a progressively updated evolution with a stepwise pruning mechanism allows PTD to guide the LLM to explore multiple distinct semantic paths within a single forward pass\. This approach ensures the generated drafts are both diverse and coherent, thereby increasing the acceptance rate and unlocking the model’s parallel potential\.

The main contributions of this paper are summarized as follows:

- •We identify and quantify the computational redundancy in existing linear or unstructured drafting methods, revealing that they fail to fully exploit the parallel capacity of AR models\.
- •We introduce Progressive Tree Drafting \(PTD\), a strategy that reformulates drafting into a structured, guided parallel generation process to ensure both draft diversity and coherence\.
- •Experimental results demonstrate that PTD consistently achieves up to a2×2\\timesspeedup across various benchmarks without requiring any auxiliary modules\.

The structure of this paper is as follows: First, we review related works, followed by a detailed description of the proposed method\. Then, we present experimental results to validate its effectiveness\. Finally, we conclude the paper and discuss potential directions for future research\.

## 2Related Works

### 2\.1Speculative Decoding with Additional Modules

The conventional speculative decoding paradigm relies onadditional modules, including independent models and architectural extensions, to generate candidate tokens\. The initial formulation\(Xia et al\.,[2023](https://arxiv.org/html/2607.10661#bib.bib18); Leviathan et al\.,[2023](https://arxiv.org/html/2607.10661#bib.bib11)\)employs a smaller, independentdraft modelto generate candidates, which are then verified by the target LLM\. These methods suffer from serialization bottlenecks and heavy reliance on the draft model’s accuracy\. PEARL\(Liu et al\.,[2025](https://arxiv.org/html/2607.10661#bib.bib15)\)and SwiftSpec\(Zhang et al\.,[2025](https://arxiv.org/html/2607.10661#bib.bib22)\)addresses these synchronization issues by optimizing the interaction protocol between the drafting and verification stages\. Subsequent works like MCSD\(Yang et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib20)\)and SpecInfer\(Miao et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib16)\)extend this by using multiple draft models or sampling strategies to boost diversity, yet the maintenance of separate models remains a bottleneck\. JudgeDecoding\(Bachmann et al\.,[2025](https://arxiv.org/html/2607.10661#bib.bib3)\)adopts a relaxed alignment paradigm to boost verification speed via a marginal accuracy loss\. Retrieval\-based methods such as REST\(He et al\.,[2023](https://arxiv.org/html/2607.10661#bib.bib10)\)substitute the draft model with an external datastore module, but this shifts the dependency to the quality and domain relevance of the retrieved corpus\.

Alternatively, some approaches integrate the drafting module directly into the target model’s architecture\. The EAGLE series\(Li et al\.,[2024a](https://arxiv.org/html/2607.10661#bib.bib12);[b](https://arxiv.org/html/2607.10661#bib.bib13)\), Medusa\(Cai et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib4)\), Blockwise Decoding\(Stern et al\.,[2018](https://arxiv.org/html/2607.10661#bib.bib17)\), Hydra\(Ankner et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib1)\)attachadditional prediction heads or layersto the LLM to predict future tokens in parallel\. Although these architectural modifications reduce communication latency compared to independent models, they fundamentally alter the model structure, requiring substantial extra training and preventing seamless deployment on off\-the\-shelf LLMs\.

### 2\.2Training\-Free Endogenous Acceleration

In contrast to module\-based approaches, a recent line of research focuses onendogenous acceleration, which exploits the target LLM’s latent capabilities to generate drafts without any additional modules or training\. Lookahead Decoding \(LADE\)\(Fu et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib8)\)utilizes the Jacobi iteration method to perform parallel decoding within the original model architecture\. Parallelly, Self\-Draft\(Gao et al\.,[2025](https://arxiv.org/html/2607.10661#bib.bib9)\)leverages the intrinsic robustness of LLMs, employing multi\-branch input perturbations to induce the model to generate its own drafts\.

These methods represent a shift towards architecture\-agnostic acceleration\. However, as discussed in the Introduction, current endogenous methods often rely on linear or iterative generation schemes that lack structural coordination, failing to fully harness the model’s parallel potential\. Our Progressive Tree Drafting \(PTD\) advances this paradigm by introducing a structured, guided exploration mechanism, achieving efficient self\-acceleration without the burden of extra modules\.

## 3Methodology

Conventional autoregressive decoding predicts one token at a time\. Given a prefix𝐗=\[x1,x2,⋯,xt−1\]\\mathbf\{X\}=\[x\_\{1\},x\_\{2\},\\cdots,x\_\{t\-1\}\], the LLM computes the next\-token distributionP​\(yt\|𝐗\)P\(y\_\{t\}\|\\mathbf\{X\}\)and selects the next token with a decoding strategy𝒮\\mathcal\{S\}:

xt=𝒮​\(P​\(yt\|𝐗\)\)x\_\{t\}=\\mathcal\{S\}\(P\(y\_\{t\}\|\\mathbf\{X\}\)\)Speculative decoding generalizes this step by introducing candidate continuations𝐂𝐗\\mathbf\{C\}\_\{\\mathbf\{X\}\}and verifying them in parallel:

xt,xt\+1,…,xt\+k=𝒮​\(P​\(yt,𝐲𝐂\|\[𝐗;𝐂𝐗\]\)\),x\_\{t\},x\_\{t\+1\},\.\.\.,x\_\{t\+k\}=\\mathcal\{S\}\\left\(P\(y\_\{t\},\\mathbf\{y\}\_\{\\mathbf\{C\}\}\|\[\\mathbf\{X\};\\mathbf\{C\}\_\{\\mathbf\{X\}\}\]\)\\right\),
These formulations provide the theoretical foundation for speculative decoding\. In practice, traditional implementations typically rely on external draft models, yet this dependency incurs alignment and communication overhead\. Endogenous acceleration offers a more efficient alternative by leveraging the target model’s internal parallel processing capacity\.

Specifically, the inference behavior of Transformer\-based LLMs is governed by the input content and the attention matrix\. By reconfiguring the input content and the attention mask, we can transfer the model’s attention from a linear path and to a multiple, concurrent reasoning trajectories\. This flexibility allows the LLM to explore a structured semantic space and generate high\-quality drafts in a single forward pass\.

Based on this insight, we develop Progressive Tree Drafting \(PTD\) to transform the model’s parallel potential into actual decoding speedup\. The design of PTD focuses on solving two practical issues: how to organize the parallel drafting paths and how to maintain their contextual coherence\. For the former, we adopt a drafting tree, as its prefix\-sharing nature represents the most complex topology theoretically supported by autoregressive models\. For the latter, we introduce a progressive update algorithm with stepwise pruning to ensure the generated content remains context\-relevant\.

![Refer to caption](https://arxiv.org/html/2607.10661v1/x3.png)Figure 3:Overview of the Progressive Tree Drafting \(PTD\) framework\. Thegreenpathway illustrates the verification process of candidate drafts, while thebluepathway denotes the semantic\-guided progressive tree drafting process\. Theredbox indicates the decoded results\.Figure[3](https://arxiv.org/html/2607.10661#S3.F3)illustrates the overall framework of PTD\. In the following subsections, we begin by introducing the tree expansion and pruning strategies that regulate the dynamic evolution of the drafting tree\. Then, we detail the draft extraction process and the verification mechanism\.

### 3\.1Progressive Tree Drafting

To transform the parallel potential of LLMs into actual speedup, we propose the Progressive Tree Drafting \(PTD\) mechanism\. This section details the tree’s lifecycle, from its structural initialization to its dynamic evolution and pruning\.

Tree Construction\.We represent the drafting structure as a treeT=\(V,E\)T=\(V,E\)\. To bootstrap the progressive process,TTis first initialized with a set of seed nodes\. These nodes can be generated stochastically or derived from semantic information in the context, serving to trigger the LLM’s reasoning across diverse semantic trajectories\.

To ensure semantic consistency, each nodev∈Vv\\in Vmust only attend to its ancestors\. Formally, for any nodevv, the set of its observable prefix nodesπ​\(v\)\\pi\(v\)is defined recursively:

π​\(v\)=\{v\}∪π​\(𝒫​\(v\)\)\\pi\(v\)=\\\{v\\\}\\cup\\pi\(\\mathcal\{P\}\(v\)\)where𝒫​\(v\)\\mathcal\{P\}\(v\)denotes the unique parent of nodevv\. The positional encoding for nodevvis determined by the cardinality ofπ​\(v\)\\pi\(v\), ensuring that the tree\-structured input remains compatible with the Transformer’s causal attention\.

Progressive Expansion\.The inference on the draft treeTt−1T^\{t\-1\}at stepttis formulated as:

xt,𝒟t=𝒮​\(P​\(yt,𝐲T\|\[𝐗;Tt−1\]\)\)x\_\{t\},\\mathcal\{D\}\_\{t\}=\\mathcal\{S\}\\left\(P\\left\(y\_\{t\},\\mathbf\{y\}\_\{T\}\|\[\\mathbf\{X\};T^\{t\-1\}\]\\right\)\\right\)where𝒟t=\{dv∣v∈Vt−1\}\\mathcal\{D\}\_\{t\}=\\\{d\_\{v\}\\mid v\\in V^\{t\-1\}\\\}is the set ofdraft tokensgenerated by all nodes inTt−1T^\{t\-1\}in a single forward pass\. PTD then evolves the draft tree toTt=\(Vt,Et\)T^\{t\}=\(V^\{t\},E^\{t\}\)by appending these newly generated tokens as child nodes:

Vt=Vt−1∪\{dv\}v∈Vt−1,Et=Et−1∪\{\(v,dv\)\}v∈Vt−1V^\{t\}=V^\{t\-1\}\\cup\\\{d\_\{v\}\\\}\_\{v\\in V^\{t\-1\}\},\\quad E^\{t\}=E^\{t\-1\}\\cup\\\{\(v,d\_\{v\}\)\\\}\_\{v\\in V^\{t\-1\}\}
![Refer to caption](https://arxiv.org/html/2607.10661v1/x4.png)Figure 4:Illustration stepwise prune algorithms\.Overhead Constraints\.Generally, the number of nodes in the draft tree ensures the diversity of the drafts it generates, and the expansion process maintains the semantic coherence between the adjacent nodes in the tree\. However, the computational overhead introduced by the draft tree increases progressively as it grows\. Hence, it is necessary to impose constraints on its growth to prevent excessive size, which could otherwise degrade the overall decoding speed\. Specifically, we impose constraints on the tree’s topology along two dimensions:

- •Width Control:We limit the max number of child nodes for each parent\. This prevents low\-confidence tokens from branching excessively, ensuring that the tree focuses on high\-probability reasoning paths\.
- •Stepping Mechanism \(Depth Control\):To prevent the tree from becoming overly deep, we implement a sliding\-window\-style stepping mechanism\. As illustrated in Figure[4](https://arxiv.org/html/2607.10661#S3.F4), when a sub\-tree exceeds a depth threshold, we retain the earliest\-added child and its descendants as the new sub\-tree, pruning all other stale branches\. This stepping\-wise prune mechanism helps preserve the semantic coherence and contextual relevance of the draft tree\.

These parameters allow for fine\-grained control over the draft tree’s complexity to suit different model scales and application requirements\. In the following experimental section, we provide a thorough evaluation of how these constraints influence the trade\-off between drafting efficiency and overall speedup\.

Draft Extraction via Merging\.Finally, we extract semantic subtrees from the expanded draft treeTtT^\{t\}and aggregate them with the existing candidates in the draft cache pool\. Specifically, any subtreeT′T^\{\\prime\}in the draft treeTtT^\{t\}will be merged with the cached candidate tree that shares the same root node value\. We define the following recursive merging functionℳ\\mathcal\{M\}for any two treesTTandT′T^\{\\prime\}with same rootrr:

ℳ​\(T,T′\)=\{\(V∪v,E∪\(r,v\)\),∀v∈σ​\(T′\)∖σ​\(T\)ℳ​\(Tv,Tv′\),∀v∈σ​\(T′\)∩σ​\(T\),\\mathcal\{M\}\(T,T^\{\\prime\}\)=\\begin\{cases\}\\left\(V\\cup v,E\\cup\(r,v\)\\right\),\\forall v\\in\\sigma\(T^\{\\prime\}\)\\setminus\\sigma\(T\)\\\\ \\mathcal\{M\}\(T\_\{v\},T^\{\\prime\}\_\{v\}\),\\forall v\\in\\sigma\(T^\{\\prime\}\)\\cap\\sigma\(T\)\\end\{cases\},whereσ​\(T\)\\sigma\(T\)denotes the set of direct child nodes of the treeTT, andTvT\_\{v\}is the subtree with root ofvvin treeTT\.

### 3\.2Candidate Verification

In parallel with the autoregressive decoding process and the progressive tree drafting process, a candidate tree validation process is concurrently executed during the forward pass\. Given the partially decoded token sequence𝐗\\mathbf\{X\}, we retrieve corresponding drafts from the draft pool, forming the candidate tree𝐂𝐗\\mathbf\{C\}\_\{\\mathbf\{X\}\}\.

To verify this candidate tree, we apply the similar attention mask and positional encoding strategy as used in the drafting process\. Consequently, after a forward pass through the LLM, each node in𝐂𝐗\\mathbf\{C\}\_\{\\mathbf\{X\}\}produces a verification token conditioned on its prefix\. Together with the autoregressive decoding process and the progressive tree drafting process, we formulate the overall model forward process as follows:

xt,𝒟,𝒱=𝒮​\(P​\(yt,𝐲T,𝐲𝐂\|\[𝐗;Ti−1;𝐂𝐗\]\)\),x\_\{t\},\\mathcal\{D\},\\mathcal\{V\}=\\mathcal\{S\}\\left\(P\(y\_\{t\},\\mathbf\{y\}\_\{T\},\\mathbf\{y\}\_\{\\mathbf\{C\}\}\|\[\\mathbf\{X\};T^\{i\-1\};\\mathbf\{C\}\_\{\\mathbf\{X\}\}\]\)\\right\),where𝒱\\mathcal\{V\}denotes theverification tokensthat are generated by each node and its prefix in the candidate tree\.

Finally, the accepted tokens𝐗′\\mathbf\{X\}^\{\\prime\}can be obtained by identifying all eligible edgesℐ\\mathcal\{I\}in the candidate tree\. Under thegreedy decoding strategy, the verification tokens𝒱\\mathcal\{V\}for all nodesV𝐂𝐗V\_\{\\mathbf\{C\}\_\{\\mathbf\{X\}\}\}of the candidate tree𝐂𝐗\\mathbf\{C\}\_\{\\mathbf\{X\}\}are selected based on the model’s highest\-probability predictions\. Eligible edges are identified recursively by verifying whether a node’s verification token appears among its child nodes\. That is:

ℐ=\{\(n,𝒱n\)\|𝒱n∈σ​\(n\),∀n∈V𝐂𝐗\}\.\\mathcal\{I\}=\\\{\(n,\\mathcal\{V\}\_\{n\}\)\|\\mathcal\{V\}\_\{n\}\\in\\sigma\(n\),\\forall n\\in V\_\{\\mathbf\{C\}\_\{\\mathbf\{X\}\}\}\\\}\.
For thesampling decoding strategy, we determine whether each token is accepted using a without\-replacement sampling method based on normalized probabilities, following an approach similar to LADE\(Fu et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib8)\)and SpecInfer\(Miao et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib16)\)\. Specifically, starting from the root node of the candidate draft tree, the LLM produces a probability distributionPvP\_\{v\}over the next token at each nodevv\. Each node may have multiple successor nodes\[c1,c2,…,ck\]\[c\_\{1\},c\_\{2\},\.\.\.,c\_\{k\}\], and a sampling process is iteratively applied to thesekkcandidates\.

At each iteration, a random numberr∼𝒰​\(0,1\)r\\sim\\mathcal\{U\}\(0,1\)is drawn, and the candidates are traversed in order\. Ifr≤Pir\\leq P\_\{i\}, the candidatecic\_\{i\}is selected, and the edge betweencic\_\{i\}and its parent node is marked as eligible and appended to the eligible edge setℐ\\mathcal\{I\}\. If not,PiP\_\{i\}is set to zero, and the remaining probabilities are renormalized\. This process continues until a candidate satisfiesr≤Pir\\leq P\_\{i\}, ensuring that the final selection remains faithful to the original distribution\. We provide the full PTD decoding algorithm, the recursive candidate\-tree sampling algorithm, and the proof of distributional consistency in Appendices[D](https://arxiv.org/html/2607.10661#A4),[E](https://arxiv.org/html/2607.10661#A5), and[F](https://arxiv.org/html/2607.10661#A6)\.

The final accepted sequence is the path formed by eligible edges starting from the root noden0n\_\{0\}\. That is,

𝐗′=\(n0,n1,…​nk,𝒱nk\)\\mathbf\{X\}^\{\\prime\}=\(n\_\{0\},n\_\{1\},\.\.\.n\_\{k\},\\mathcal\{V\}\_\{n\_\{k\}\}\)where∀i<k,\(ni,ni\+1\)∈ℐ\\forall i<k,\(n\_\{i\},n\_\{i\+1\}\)\\in\\mathcal\{I\}and𝐗′\\mathbf\{X\}^\{\\prime\}are the tokens we decoded in a single model forward pass\.

## 4Experiments

### 4\.1Settings

Benchmarks\.To evaluate the performance of PTD across diverse scenarios, we utilize several representative benchmarks\. For general conversation, we use MT\-Bench\(Zheng et al\.,[2023](https://arxiv.org/html/2607.10661#bib.bib23)\), which covers eight distinct task categories with 80 problems in total\. For mathematical reasoning, we randomly sample 100 questions from the GSM\-8k\(Cobbe et al\.,[2021](https://arxiv.org/html/2607.10661#bib.bib7)\)dataset\. For code generation, we employ the full HumanEval\(Chen et al\.,[2021](https://arxiv.org/html/2607.10661#bib.bib6)\)dataset and a 100\-problem test subset from MBPP\(Austin et al\.,[2021](https://arxiv.org/html/2607.10661#bib.bib2)\)\.

Baselines\.We compare PTD against several representative strategies\. Standard Autoregressive \(AR\) decoding serves as the primary baseline, and the training\-free baselines include Lookahead Decoding \(LADE\)\(Fu et al\.,[2024](https://arxiv.org/html/2607.10661#bib.bib8)\)and Self\-Draft\(Gao et al\.,[2025](https://arxiv.org/html/2607.10661#bib.bib9)\)\. All baseline hyperparameters are kept at their default settings\.

Models\.For general conversation \(MT\-Bench\) and mathematical reasoning \(GSM\-100\), we employ LLaMA\-2 \(7B/13B\), LLaMA\-3 \(8B\), Qwen\-2\.5 \(7B/14B/32B\), and Qwen\-3 \(8B/14B\)\. For code generation \(HumanEval, MBPP\-100\), we utilize CodeLLaMA\-7B/13B\.

Metrics\.We employ five metrics for evaluation: \(i\) Throughput \(TP\) \(tokens/s\) for end\-to\-end speed; \(ii\) Accept Length \(AL\) and \(iii\) Hit Rate \(HR\) to characterize draft coherence and diversity; \(iv\) Decoding Efficiency \(DE\), the average tokens produced per forward pass, defined as:

DE=HR⋅AL\+\(1−HR\)\\text\{DE\}=\\text\{HR\}\\cdot\\text\{AL\}\+\(1\-\\text\{HR\}\)and \(v\) Computational Overhead, the average additional tokens processed per step during drafting \(D​f​tDft\) and verification \(V​e​rVer\)\.

All experiments were conducted on NVIDIA L20 GPUs \(48 GB RAM\) using BF16 precision to enhance computational efficiency\. Inference was performed consistently with a batch size of one throughout\. Unless otherwise specified, all draft tokens are obtained via greedy \(Top\-1\) and the draft tree is initialized randomly\. Additional analyses of sampling strategies and initialization are provided in Appendices[A](https://arxiv.org/html/2607.10661#A1)and[B](https://arxiv.org/html/2607.10661#A2)\.

### 4\.2Results

#### 4\.2\.1Main Results

MT\-BenchL2\-7BL2\-13BL3\-8BQ2\-7BQ2\-14BQ2\-32BQ3\-8BQ3\-14BAR \(Ref\.\)1\.00×\\times\(39±\\pm3\.9\)1\.00×\\times\(24±\\pm1\.7\)1\.00×\\times\(38±\\pm2\.6\)1\.00×\\times\(36±\\pm4\.3\)1\.00×\\times\(20±\\pm1\.9\)1\.00×\\times\(10±\\pm0\.6\)1\.00×\\times\(39±\\pm3\.4\)1\.00×\\times\(24±\\pm1\.3\)LADE1\.49×\\times\(58±\\pm9\.8\)1\.38×\\times\(33±\\pm4\.9\)1\.42×\\times\(54±\\pm5\.2\)1\.42×\\times\(51±\\pm8\.8\)1\.45×\\times\(29±\\pm5\.0\)1\.60×\\times\(16±\\pm3\.0\)1\.51×\\times\(59±\\pm7\.3\)1\.29×\\times\(31±\\pm4\.7\)Self\-Draft1\.54×\\times\(60±\\pm12\.1\)1\.54×\\times\(37±\\pm6\.6\)1\.53×\\times\(58±\\pm7\.9\)1\.47×\\times\(53±\\pm12\.5\)1\.50×\\times\(30±\\pm6\.6\)1\.60×\\times\(16±\\pm3\.3\)1\.54×\\times\(60±\\pm9\.5\)1\.38×\\times\(33±\\pm5\.1\)PTD \(Ours\)1\.67×\\times\(65±\\pm11\.1\)1\.67×\\times\(40±\\pm5\.8\)1\.66×\\times\(63±\\pm7\.1\)1\.69×\\times\(61±\\pm15\.4\)1\.75×\\times\(35±\\pm7\.6\)1\.90×\\times\(19±\\pm3\.9\)1\.64×\\times\(64±\\pm6\.9\)1\.54×\\times\(37±\\pm6\.2\)GSM\-100L2\-7BL2\-13BL3\-8BQ2\-7BQ2\-14BQ2\-32BQ3\-8BQ3\-14BAR \(Ref\.\)1\.00×\\times\(43±\\pm0\.9\)1\.00×\\times\(26±\\pm0\.4\)1\.00×\\times\(41±\\pm0\.6\)1\.00×\\times\(39±\\pm1\.9\)1\.00×\\times\(22±\\pm0\.5\)1\.00×\\times\(10±\\pm0\.2\)1\.00×\\times\(40±\\pm1\.3\)1\.00×\\times\(25±\\pm0\.6\)LADE1\.70×\\times\(73±\\pm5\.6\)1\.58×\\times\(41±\\pm3\.3\)1\.71×\\times\(70±\\pm5\.2\)1\.56×\\times\(61±\\pm6\.3\)1\.55×\\times\(34±\\pm3\.8\)1\.80×\\times\(18±\\pm1\.5\)1\.73×\\times\(69±\\pm5\.9\)1\.44×\\times\(36±\\pm2\.7\)Self\-Draft1\.72×\\times\(74±\\pm6\.2\)1\.69×\\times\(44±\\pm4\.5\)1\.80×\\times\(74±\\pm5\.0\)1\.56×\\times\(61±\\pm7\.4\)1\.59×\\times\(35±\\pm4\.2\)1\.90×\\times\(19±\\pm1\.6\)1\.83×\\times\(73±\\pm5\.7\)1\.52×\\times\(38±\\pm3\.8\)PTD \(Ours\)1\.91×\\times\(82±\\pm7\.5\)1\.85×\\times\(48±\\pm4\.2\)1\.93×\\times\(79±\\pm6\.7\)1\.87×\\times\(73±\\pm13\.3\)1\.86×\\times\(41±\\pm5\.9\)2\.30×\\times\(23±\\pm2\.1\)1\.93×\\times\(77±\\pm9\.4\)1\.76×\\times\(44±\\pm5\.2\)Table 1:Speedup performance on MT\-Bench and GSM\-100 across Llama and Qwen model series\. The primary metric is the Speedup Ratio \(n×n\\times\), with throughput \(tokens/s\) and standard deviation shown in small parentheses\.MethodHumanEvalMBPP\-100CL\-7BCL\-13BCL\-7BCL\-13BAR \(Ref\.\)1\.00×\\times\(42±\\pm1\.6\)1\.00×\\times\(25±\\pm0\.7\)1\.00×\\times\(44±\\pm0\.8\)1\.00×\\times\(26±\\pm0\.3\)LADE1\.45×\\times\(61±\\pm5\.7\)1\.44×\\times\(36±\\pm4\.6\)1\.70×\\times\(75±\\pm7\.5\)1\.65×\\times\(43±\\pm4\.1\)Self\-Draft1\.62×\\times\(68±\\pm7\.4\)1\.68×\\times\(42±\\pm5\.4\)1\.86×\\times\(82±\\pm6\.7\)1\.88×\\times\(49±\\pm4\.3\)PTD1\.69×\\times\(71±\\pm7\.4\)1\.72×\\times\(43±\\pm5\.6\)2\.05×\\times\(90±\\pm8\.9\)2\.08×\\times\(54±\\pm5\.4\)Table 2:Speedup and throughput results on code generation benchmarks\. The format follows:Speedup×Speedup\\times\(Throughput±\\pmStd\)\.Tables[1](https://arxiv.org/html/2607.10661#S4.T1)and[2](https://arxiv.org/html/2607.10661#S4.T2)summarize the speedup performance\. We set the maximum tree depth to 6 and the branching factor to 4\. As observed, PTD consistently achieves the highest speedup across all evaluated models and tasks, outperforming state\-of\-the\-art training\-free baselines like LADE and Self\-Draft\.

The advantages of PTD are most pronounced in reasoning\-intensive benchmarks, specifically GSM\-100 \(up to 2\.30×\\times\) and MBPP\-100 \(up to 2\.08×\\times\)\. Because mathematical and coding tasks follow structured logical paths, PTD’s tree\-based evolution effectively maintains high draft coherence while providing broader coverage of the solution space, significantly reducing redundant computations compared to independent branching methods\.

Moreover, PTD achieves stable acceleration across various model generations \(from LLaMA\-2 to Qwen\-3\) as a training\-free, plug\-and\-play solution\. Whether applied to smaller 7B models or the larger Qwen2\-32B \(reaching a peak speedup of 2\.30×\\times\), PTD consistently unlocks the model’s inherent parallel potential with zero extra learning cost, proving its superior versatility in real\-world deployment\.

![Refer to caption](https://arxiv.org/html/2607.10661v1/x5.png)Figure 5:Draft content quality analysis\.Figure[5](https://arxiv.org/html/2607.10661#S4.F5)provides a more in\-depth analysis of decoding efficiency\(DE\), hit rate\(HR\), candidate draft acceptance length\(AL\), and overhead\(Dft/Ver\), which reveals the underlying causes of speed differences among the methods\. On this front, PTD demonstrates a comprehensive advantage\. Specifically, while PTD exhibits a slightly lower HR compared to Self\-Draft, which primarily because Self\-Draft uses specific external data/corpora to boost hit probability, it maintains a substantial lead in AL\. This indicates that PTD\-generated drafts possess superior contextual coherence, allowing the model to accept much longer sequences per verification pass\.

Furthermore, PTD maintains a competitive overhead profile, comparable to Self\-Draft and generally lower than LADE\. This ensures that the structural complexity of PTD does not translate into significant latency during the forward pass, effectively maximizing the net gain in inference speed\. A detailed runtime breakdown is provided in Appendix[C](https://arxiv.org/html/2607.10661#A3)\.

#### 4\.2\.2Draft Tree Analysis

The performance of PTD is governed by the trade\-off between draft quality and computational overhead\. Figure[6](https://arxiv.org/html/2607.10661#S4.F6)analyzes the effects of the maximum number of child nodes \(ww\) and drafting depth \(dd\)\.

Impact of Max Child Nodes \(ww\)\.With depth fixed at 6, increasingwwimproves both Hit Rate \(H​RHR\) and Accept Length \(A​LAL\) by expanding the search breadth and increasing the chance of covering the intended semantic path\. However, throughput follows a rise\-then\-fall trend and peaks atw=4w=4, after which the additional latency of a wider tree outweighs the gains inH​RHRandA​LAL\.

Impact of Max Drafting Depth \(dd\)\.Withw=4w=4,H​RHRremains relatively stable as depth increases, suggesting that the initial hit is driven more by branching diversity than depth\. In contrast,A​LALkeeps increasing because deeper trees allow longer continuation along a correct path\. Throughput peaks atd=6d=6, beyond which the benefit of longer accepted sequences is offset by the overhead of verifying deeper trees\.

Overall, PTD exhibits strong robustness across a broad range of tree configurations\. In practical deployments,wwandddcan be dynamically adapted based on specific model architectures and hardware resources\. In this paper, we utilize a uniform configuration ofw=4w=4andd=6d=6to facilitate a consistent discussion across all evaluations\.

![Refer to caption](https://arxiv.org/html/2607.10661v1/x6.png)
Figure 6:Effect of tree width and depth on PTD performance on LLaMA\-7B\.![Refer to caption](https://arxiv.org/html/2607.10661v1/x7.png)
Figure 7:Draft efficiency of LADE and PTD on LLaMA\-7B and LLaMA\-13B\.

#### 4\.2\.3Draft efficiency

Figure[7](https://arxiv.org/html/2607.10661#S4.F7)compares the drafting efficiency of PTD and LADE across different computational overhead levels\. PTD consistently achieves higher throughput \(TP\) and decoding efficiency \(DE\)\. On LLaMA\-7B, PTD matches LADE’s peak throughput with approximately half the overhead; on LLaMA\-13B, it requires only about one\-third\. PTD also provides substantial speedups under low\-overhead settings, highlighting its potential for large\-scale inference services\. Additional evaluations of generation quality under sampling and acceleration under greedy decoding are provided in Appendices[G](https://arxiv.org/html/2607.10661#A7)and[H](https://arxiv.org/html/2607.10661#A8)\.

## 5Conclusion

In this paper, we introduce PTD, a guided and structured inference acceleration method for autoregressive LLMs\. This framework achieves comprehensive performance gains across diverse models and benchmarks as a training\-free and model\-agnostic solution\. Future research will explore dense semantic representations, like semantic graphs, to enable more guided and efficient draft generation beyond current tree\-based methods\. Besides, we also aim to decouple the drafting and decoding processes to enhance system efficiency and scalability\.

## References

- Ankner et al\. \(2024\)Zachary Ankner, Rishab Parthasarathy, Aniruddha Nrusimha, Christopher Rinard, Jonathan Ragan\-Kelley, and William Brandon\.Hydra: Sequentially\-dependent draft heads for medusa decoding, 2024\.URL[https://arxiv\.org/abs/2402\.05109](https://arxiv.org/abs/2402.05109)\.
- Austin et al\. \(2021\)Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al\.Program synthesis with large language models\.*arXiv preprint arXiv:2108\.07732*, 2021\.
- Bachmann et al\. \(2025\)Gregor Bachmann, Sotiris Anagnostidis, Albert Pumarola, Markos Georgopoulos, Artsiom Sanakoyeu, Yuming Du, Edgar Schönfeld, Ali Thabet, and Jonas Kohler\.Judge decoding: Faster speculative sampling requires going beyond model alignment, 2025\.URL[https://arxiv\.org/abs/2501\.19309](https://arxiv.org/abs/2501.19309)\.
- Cai et al\. \(2024\)Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D\. Lee, Deming Chen, and Tri Dao\.Medusa: Simple llm inference acceleration framework with multiple decoding heads, 2024\.
- Chen et al\. \(2023\)Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean\-Baptiste Lespiau, Laurent Sifre, and John Jumper\.Accelerating large language model decoding with speculative sampling, 2023\.
- Chen et al\. \(2021\)Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert\-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N\. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba\.Evaluating large language models trained on code, 2021\.
- Cobbe et al\. \(2021\)Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman\.Training verifiers to solve math word problems\.*arXiv preprint arXiv:2110\.14168*, 2021\.
- Fu et al\. \(2024\)Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang\.Break the sequential dependency of llm inference using lookahead decoding, 2024\.
- Gao et al\. \(2025\)Zipeng Gao, Qingrong Xia, Tong Xu, Xinyu Duan, Zhi Zheng, Zhefeng Wang, and Enhong Chen\.Multi\-branch self\-drafting for llm inference acceleration\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, volume 39, pp\. 23942–23950, 2025\.
- He et al\. \(2023\)Zhenyu He, Zexuan Zhong, Tianle Cai, Jason D Lee, and Di He\.Rest: Retrieval\-based speculative decoding, 2023\.
- Leviathan et al\. \(2023\)Yaniv Leviathan, Matan Kalman, and Yossi Matias\.Fast inference from transformers via speculative decoding, 2023\.
- Li et al\. \(2024a\)Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang\.Eagle: speculative sampling requires rethinking feature uncertainty\.In*Proceedings of the 41st International Conference on Machine Learning*, ICML’24\. JMLR\.org, 2024a\.
- Li et al\. \(2024b\)Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang\.Eagle\-2: Faster inference of language models with dynamic draft trees, 2024b\.URL[https://arxiv\.org/abs/2406\.16858](https://arxiv.org/abs/2406.16858)\.
- Li et al\. \(2025\)Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang\.Eagle: Speculative sampling requires rethinking feature uncertainty, 2025\.URL[https://arxiv\.org/abs/2401\.15077](https://arxiv.org/abs/2401.15077)\.
- Liu et al\. \(2025\)Tianyu Liu, Yun Li, Qitan Lv, Kai Liu, Jianchen Zhu, Winston Hu, and Xiao Sun\.Pearl: Parallel speculative decoding with adaptive draft length, 2025\.URL[https://arxiv\.org/abs/2408\.11850](https://arxiv.org/abs/2408.11850)\.
- Miao et al\. \(2024\)Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, Chunan Shi, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia\.Specinfer: Accelerating large language model serving with tree\-based speculative inference and verification\.In*Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3*, ASPLOS ’24, pp\. 932–949\. ACM, April 2024\.doi:10\.1145/3620666\.3651335\.URL[http://dx\.doi\.org/10\.1145/3620666\.3651335](http://dx.doi.org/10.1145/3620666.3651335)\.
- Stern et al\. \(2018\)Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit\.Blockwise parallel decoding for deep autoregressive models\.*Advances in Neural Information Processing Systems*, 31, 2018\.
- Xia et al\. \(2023\)Heming Xia, Tao Ge, Peiyi Wang, Si\-Qing Chen, Furu Wei, and Zhifang Sui\.Speculative decoding: Exploiting speculative execution for accelerating seq2seq generation\.In Houda Bouamor, Juan Pino, and Kalika Bali \(eds\.\),*Findings of the Association for Computational Linguistics: EMNLP 2023*, pp\. 3909–3925, Singapore, December 2023\. Association for Computational Linguistics\.doi:10\.18653/v1/2023\.findings\-emnlp\.257\.URL[https://aclanthology\.org/2023\.findings\-emnlp\.257/](https://aclanthology.org/2023.findings-emnlp.257/)\.
- Xia et al\. \(2024\)Heming Xia, Zhe Yang, Qingxiu Dong, Peiyi Wang, Yongqi Li, Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui\.Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding\.In Lun\-Wei Ku, Andre Martins, and Vivek Srikumar \(eds\.\),*Findings of the Association for Computational Linguistics: ACL 2024*, pp\. 7655–7671, Bangkok, Thailand, August 2024\. Association for Computational Linguistics\.doi:10\.18653/v1/2024\.findings\-acl\.456\.URL[https://aclanthology\.org/2024\.findings\-acl\.456/](https://aclanthology.org/2024.findings-acl.456/)\.
- Yang et al\. \(2024\)Sen Yang, Shujian Huang, Xinyu Dai, and Jiajun Chen\.Multi\-candidate speculative decoding\.*arXiv preprint arXiv:2401\.06706*, 2024\.
- Yuan et al\. \(2024\)Zhihang Yuan, Yuzhang Shang, Yang Zhou, Zhen Dong, Zhe Zhou, Chenhao Xue, Bingzhe Wu, Zhikai Li, Qingyi Gu, Yong Jae Lee, Yan Yan, Beidi Chen, Guangyu Sun, and Kurt Keutzer\.Llm inference unveiled: Survey and roofline model insights, 2024\.
- Zhang et al\. \(2025\)Ziyi Zhang, Ziheng Jiang, Chengquan Jiang, Menghan Yu, Size Zheng, Haibin Lin, Henry Hoffmann, and Xin Liu\.Swiftspec: Ultra\-low latency llm decoding by scaling asynchronous speculative decoding, 2025\.URL[https://arxiv\.org/abs/2506\.11309](https://arxiv.org/abs/2506.11309)\.
- Zheng et al\. \(2023\)Lianmin Zheng, Wei\-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P\. Xing, Hao Zhang, Joseph E\. Gonzalez, and Ion Stoica\.Judging llm\-as\-a\-judge with mt\-bench and chatbot arena, 2023\.

## Appendix ASample Strategy for the Draft Tree Expansion

This section analyzes how the draft\-tree expansion strategy affects PTD\. Unless otherwise noted, we use LLaMA\-2\-13B on MT\-Bench and compare greedy expansion with top\-k and top\-p sampling for draft\-tree growth\. For sampled expansion, we first obtain the top\-k or top\-p distribution at each node and then sample draft tokens from that distribution to extend the tree\.

Figure[8](https://arxiv.org/html/2607.10661#A1.F8)shows the resulting trade\-off\. Compared with greedy expansion, top\-k and top\-p increase overhead because they introduce greater diversity and uncertainty, which leads to faster tree growth\. However, the additional overhead yields little improvement in throughput or decoding efficiency\.

![Refer to caption](https://arxiv.org/html/2607.10661v1/x8.png)Figure 8:PTD performance under different sampling strategies for draft tree expansion\.
## Appendix BImpact of Initialization Strategy

This section compares random initialization with a Named Entity Recognition \(NER\)\-based initialization strategy for PTD across the eight MT\-Bench categories\. As shown in Figure[9](https://arxiv.org/html/2607.10661#A2.F9), the effectiveness of the initialization strategy depends on the task type\. For structured domains such as coding, mathematics, and extraction, NER\-based initialization performs better because entity\-aware seeds better capture task\-specific identifiers and core logical elements\. In contrast, the difference between the two methods is small for open\-ended tasks such as creative writing\. These results suggest that specialized initialization is most useful for structured reasoning and less critical for general\-purpose generation\.

![Refer to caption](https://arxiv.org/html/2607.10661v1/x9.png)Figure 9:Performance comparison of PTD under random and NER\-based initialization across eight MT\-Bench tasks\.
## Appendix COverhead Analysis

This section breaks down the runtime overhead of PTD relative to autoregressive decoding on Qwen models\. PTD introduces three additional costs: candidate\-tree retrieval before the forward pass, parallel drafting and verification during the forward pass, and candidate\-pool and draft\-tree updates after the forward pass\. Figure[10](https://arxiv.org/html/2607.10661#A3.F10.1)shows that the dominant overhead comes from the forward pass, where PTD performs additional inference on both the draft tree and the candidate tree, while retrieval and update costs remain negligible\.

![Refer to caption](https://arxiv.org/html/2607.10661v1/x10.png)Figure 10:Run time analysis for Qwen models\.
## Appendix DProgressive Tree Drafting Decoding Algorithm

Algorithm 1Progressive Tree Drafting Decoding Algorithm1:Input:Prompt

𝐗=\[x1,x2,…,xt−1\]\\mathbf\{X\}=\[x\_\{1\},x\_\{2\},\.\.\.,x\_\{t\-1\}\]; max tree depth

dmaxd\_\{\\text\{max\}\}; initial tree

T0=\(V0,E0\)T^\{0\}=\(V^\{0\},E^\{0\}\); max length

NN
2:whileTruedo

3:\{Step 1: Retrieve Candidate Tree\}

4:Retrieve candidate tree

𝒞𝐗←\\mathcal\{C\}\_\{\\mathbf\{X\}\}\\leftarrowRetrieveCandidateTree\(

𝐗\\mathbf\{X\}\)

5:\{Step 2: Generate Next Token\(s\) with Structural Guidance\}

6:

xt,𝒟,𝒱←𝒮​\(P​\(yt,𝐲T,𝐲𝒞∣\[𝐗;Ti−1;𝒞𝐗\]\)\)x\_\{t\},\\mathcal\{D\},\\mathcal\{V\}\\leftarrow\\mathcal\{S\}\\left\(P\(y\_\{t\},\\mathbf\{y\}\_\{T\},\\mathbf\{y\}\_\{\\mathcal\{C\}\}\\mid\\left\[\\mathbf\{X\};T^\{i\-1\};\\mathcal\{C\}\_\{\\mathbf\{X\}\}\\right\]\)\\right\)
7:\{Step 3: Expand the Draft Tree\}

8:

Vi←Vi−1∪\{dv∣∀v∈Vi−1\}V^\{i\}\\leftarrow V^\{i\-1\}\\cup\\\{d\_\{v\}\\mid\\forall v\\in V^\{i\-1\}\\\}
9:

Ei←Ei−1∪\{\(v,dv\)∣∀v∈Vi−1\}E^\{i\}\\leftarrow E^\{i\-1\}\\cup\\\{\(v,d\_\{v\}\)\\mid\\forall v\\in V^\{i\-1\}\\\}
10:if

depth​\(Ti\)\>dmax\\text\{depth\}\(T^\{i\}\)\>d\_\{\\text\{max\}\}then

11:

Ti←T^\{i\}\\leftarrowStepAndPrune\(

TiT^\{i\}\)

12:endif

13:\{Step 4: Merge Subtrees into Candidate Pool\}

14:foreach subtree

Ts′T^\{\\prime\}\_\{s\}in

TiT^\{i\}do

15:Update candidate pool by merging trees using

ℳ\\mathcal\{M\}
16:endfor

17:\{Step 5: Obtain Eligible Edges\}

18:ifUsing Greedy Decodingthen

19:

𝒱←argmax⁡\(P𝒞\)\\mathcal\{V\}\\leftarrow\\operatorname\{argmax\}\(P\_\{\\mathcal\{C\}\}\)
20:

ℰ←\{\(n,𝒱n\)∣𝒱n∈σ​\(n\),∀n∈Vi\}\\mathcal\{E\}\\leftarrow\\\{\(n,\\mathcal\{V\}\_\{n\}\)\\mid\\mathcal\{V\}\_\{n\}\\in\\sigma\(n\),\\forall n\\in V^\{i\}\\\}
21:elseifUsing Sampling Decodingthen

22:

ℰ,𝒱nk←\\mathcal\{E\},\\mathcal\{V\}\_\{n\_\{k\}\}\\leftarrowCandidateTreeRecursiveSample\(

𝒞𝐗\\mathcal\{C\}\_\{\\mathbf\{X\}\}\)

23:endif

24:\{Step 6: Append Chosen Path\}

25:

𝐗′←\(n0,n1,…,nk,𝒱nk\)\\mathbf\{X\}^\{\\prime\}\\leftarrow\(n\_\{0\},n\_\{1\},\.\.\.,n\_\{k\},\\mathcal\{V\}\_\{n\_\{k\}\}\)s\.t\.

∀i<k,\(ni,ni\+1\)∈ℰ\\forall i<k,\(n\_\{i\},n\_\{i\+1\}\)\\in\\mathcal\{E\}
26:Append

𝐗′\\mathbf\{X\}^\{\\prime\}to

𝐗\\mathbf\{X\}
27:if

\|𝐗\|\>N\|\\mathbf\{X\}\|\>Nthen

28:break

29:endif

30:

i←i\+1i\\leftarrow i\+1
31:endwhile

32:Output:Generated sequence

𝐗\\mathbf\{X\}

## Appendix ECandidate Tree Recursive Sampling Algorithm

Algorithm 2Candidate Tree Recursive Sampling1:Input:A node

vv
2:Output:Obtain global eligible edges

ℰ\\mathcal\{E\}
3:

C←σ​\(v\)C\\leftarrow\\sigma\(v\)\{Children of

vv\}

4:while

CCis not emptydo

5:for all

n∈Cn\\in Cdo

6:Sample

r∼𝒰​\(0,1\)r\\sim\\mathcal\{U\}\(0,1\)
7:if

r<P​\(n\)r<P\(n\)then

8:Append

\(v,n\)\(v,n\)to

ℰ\\mathcal\{E\}
9:call

𝒱nk←\\mathcal\{V\}\_\{n\_\{k\}\}\\leftarrowTraversal\(n\)\(n\)

10:return

nkn\_\{k\}
11:else

12:

P​\[n\]←0P\[n\]\\leftarrow 0
13:Renormalize

PPover remaining nodes in

CC
14:endif

15:endfor

16:endwhile

17:\{If no child selected, sampling based on current node distribution\}

18:return

𝒮​\(P​\(v\)\)\\mathcal\{S\}\\left\(P\(v\)\\right\)

## Appendix FProof of Distributional Consistency of the Candidate Tree Recursive Sampling Algorithm

We aim to prove that the sampling algorithm described in Appendix[D](https://arxiv.org/html/2607.10661#A4)selects each candidate nodenin\_\{i\}with probability equal to its original probabilityPiP\_\{i\}\.

##### Sampling Procedure\.

Given a set of candidate nodes\{n1,n2,…,nk\}\\\{n\_\{1\},n\_\{2\},\\dots,n\_\{k\}\\\}and associated probabilitiesPiP\_\{i\}, the algorithm iteratively samples a random variabler∼𝒰​\(0,1\)r\\sim\\mathcal\{U\}\(0,1\)and accepts the first nodenin\_\{i\}such thatr<Pir<P\_\{i\}\(after re\-normalization, if any earlier nodes have been rejected\)\. Ifnin\_\{i\}is not accepted, its probability is set to 0, and the remaining probabilities are re\-normalized\.

##### Objective\.

Let𝒜i\\mathcal\{A\}\_\{i\}denote the event that nodenin\_\{i\}is selected\. We aim to prove:

ℙ​\(𝒜i\)=Pi,∀i∈\{1,2,…,k\}\.\\mathbb\{P\}\(\\mathcal\{A\}\_\{i\}\)=P\_\{i\},\\quad\\forall i\\in\\\{1,2,\\dots,k\\\}\.

##### Base Case \(i=1i=1\)\.

Noden1n\_\{1\}is the first candidate considered\. Since no re\-normalization has occurred yet, its acceptance probability is:

ℙ​\(𝒜1\)=ℙ​\(r<P1\)=P1\.\\mathbb\{P\}\(\\mathcal\{A\}\_\{1\}\)=\\mathbb\{P\}\(r<P\_\{1\}\)=P\_\{1\}\.

##### Inductive Step\.

Suppose that for eachj<ij<i, the probability of selecting nodenjn\_\{j\}is exactlyPjP\_\{j\}, and the algorithm correctly rejectsn1n\_\{1\}throughni−1n\_\{i\-1\}with total probabilityRi−1=∑j=1i−1PjR\_\{i\-1\}=\\sum\_\{j=1\}^\{i\-1\}P\_\{j\}\.

After rejectingn1,…,ni−1n\_\{1\},\\dots,n\_\{i\-1\}, the remaining unnormalized probability is:

Si−1=1−∑j=1i−1Pj\.S\_\{i\-1\}=1\-\\sum\_\{j=1\}^\{i\-1\}P\_\{j\}\.
The normalized probability ofnin\_\{i\}in this residual distribution becomes:

P^i=PiSi−1\.\\hat\{P\}\_\{i\}=\\frac\{P\_\{i\}\}\{S\_\{i\-1\}\}\.
The probability of reachingnin\_\{i\}without accepting any of the previousi−1i\-1nodes is:

ℙ​\(reaching​ni\)=∏j=1i−1\(1−P^j\)\.\\mathbb\{P\}\(\\text\{reaching \}n\_\{i\}\)=\\prod\_\{j=1\}^\{i\-1\}\(1\-\\hat\{P\}\_\{j\}\)\.
However, since:

∏j=1i−1\(1−P^j\)=∏j=1i−1\(1−PjSj−1\)=S1S0⋅S2S1​⋯​Si−1Si−2=Si−1S0=Si−1,\\prod\_\{j=1\}^\{i\-1\}\(1\-\\hat\{P\}\_\{j\}\)=\\prod\_\{j=1\}^\{i\-1\}\\left\(1\-\\frac\{P\_\{j\}\}\{S\_\{j\-1\}\}\\right\)=\\frac\{S\_\{1\}\}\{S\_\{0\}\}\\cdot\\frac\{S\_\{2\}\}\{S\_\{1\}\}\\cdots\\frac\{S\_\{i\-1\}\}\{S\_\{i\-2\}\}=\\frac\{S\_\{i\-1\}\}\{S\_\{0\}\}=S\_\{i\-1\},andS0=1S\_\{0\}=1, this implies:

ℙ​\(reaching​ni\)=Si−1\.\\mathbb\{P\}\(\\text\{reaching \}n\_\{i\}\)=S\_\{i\-1\}\.
Therefore, the total probability of acceptingnin\_\{i\}is:

ℙ​\(𝒜i\)=ℙ​\(reaching​ni\)⋅P^i=Si−1⋅PiSi−1=Pi\.\\mathbb\{P\}\(\\mathcal\{A\}\_\{i\}\)=\\mathbb\{P\}\(\\text\{reaching \}n\_\{i\}\)\\cdot\\hat\{P\}\_\{i\}=S\_\{i\-1\}\\cdot\\frac\{P\_\{i\}\}\{S\_\{i\-1\}\}=P\_\{i\}\.

##### Conclusion\.

By induction, for everyi∈\{1,…,k\}i\\in\\\{1,\\dots,k\\\}, the probability of nodenin\_\{i\}being selected is exactlyPiP\_\{i\}\. Hence, the sampling algorithm yields a sample from the original distributionPP:

ℙ​\(𝒜i\)=Pi∀i\.\\mathbb\{P\}\(\\mathcal\{A\}\_\{i\}\)=P\_\{i\}\\quad\\forall i\.This proves that the sequential rejection\-normalization sampling procedure preserves the target distribution\.

## Appendix GGeneration Quality Evaluation: A Comparison Between PTD and Autoregressive Decoding under the Sampling Strategy

This section compares the generated content of PTD and standard autoregressive decoding under the sampling setting\. We evaluate MT\-Bench, GSM\-100, HumanEval, and MBPP\-100 with LLaMA\-2 \(L\), Qwen\-2\.5 \(Q\), and CodeLLaMA \(CL\) models using Rouge\-1, Rouge\-2, Rouge\-L, and BLEU\.

BenchmarkModelRouge\-1Rouge\-2Rouge\-LBLEUMT\-BenchL\-7B50323417L\-13B51343619Q\-7B42202421Q\-14B48222418Q\-32B48242622GSM\-100L\-7B68535539L\-13B65505336Q\-7B49313426Q\-14B52293128Q\-32B58404138HumanEvalCL\-7B48384026CL\-13B48404321MBPP\-100CL\-7B82778077CL\-13B82788076Table 3:Comparison of generated content between PTD and autoregressive decoding under the sampling strategy\. L, Q, and CL denote LLaMA\-2, Qwen\-2\.5, and CodeLLaMA, respectively\.
## Appendix HAcceleration Performance of Greedy Decoding Strategy

This section reports acceleration results under greedy decoding on MT\-Bench, GSM\-100, HumanEval, and MBPP\-100 using LLaMA\-2 \(L\), Qwen\-2\.5 \(Q\), and CodeLLaMA \(CL\) models\.

BenchmarkModelARLADESelf\-DraftPTDTP\(Std\)TP\(Std\)Imp\.TP\(Std\)Imp\.TP\(Std\)Imp\.MT\-BenchL\-7B40±\\pm4\.159±\\pm9\.447%62±\\pm11\.456%67±\\pm10\.868%L\-13B24±\\pm1\.734±\\pm4\.841%37±\\pm6\.754%40±\\pm6\.467%Q\-7B36±\\pm4\.459±\\pm12\.265%55±\\pm13\.452%70±\\pm20\.093%Q\-14B20±\\pm2\.031±\\pm5\.357%31±\\pm6\.356%36±\\pm6\.881%Q\-32B10±\\pm0\.616±\\pm2\.757%16±\\pm3\.362%19±\\pm3\.688%GSM\-100L\-7B44±\\pm1\.074±\\pm5\.966%75±\\pm6\.768%85±\\pm7\.291%L\-13B26±\\pm0\.441±\\pm3\.358%44±\\pm4\.667%49±\\pm4\.389%Q\-7B40±\\pm2\.172±\\pm8\.280%65±\\pm8\.862%86±\\pm16\.4116%Q\-14B22±\\pm0\.637±\\pm3\.767%37±\\pm4\.669%44±\\pm5\.299%Q\-32B11±\\pm0\.219±\\pm1\.681%19±\\pm1\.282%24±\\pm2\.2125%HumanEvalCL\-7B43±\\pm1\.762±\\pm6\.845%62±\\pm7\.645%74±\\pm8\.574%CL\-13B25±\\pm0\.737±\\pm4\.545%39±\\pm5\.355%44±\\pm5\.874%MBPP\-100CL\-7B45±\\pm0\.877±\\pm6\.471%73±\\pm7\.262%93±\\pm9\.9108%CL\-13B26±\\pm0\.343±\\pm4\.164%48±\\pm4\.582%55±\\pm5\.4107%Table 4:Throughput and relative improvement \(Imp\.\) under greedy decoding for autoregressive decoding \(AR\), LADE, Self\-Draft, and PTD\. L, Q, and CL denote LLaMA\-2, Qwen\-2\.5, and CodeLLaMA, respectively\.BenchmarkModelLADESelf\-DraftPTDDEHRALDft/VerDEHRALDft/VerDEHRALDft/VerMT\-BenchL\-7B1\.950\.692\.3959/231\.960\.952\.0230/302\.230\.712\.7435/23L\-13B1\.830\.672\.2639/171\.960\.952\.0230/302\.200\.712\.7034/22Q\-7B2\.200\.782\.5559/312\.030\.922\.1231/262\.580\.802\.9940/29Q\-14B2\.010\.762\.3139/211\.970\.922\.0531/262\.400\.802\.7642/29Q\-32B1\.870\.722\.2127/152\.020\.922\.1131/252\.430\.772\.8637/27GSM\-100L\-7B2\.230\.722\.7258/222\.290\.942\.3830/322\.520\.733\.0932/21L\-13B2\.060\.702\.5338/162\.290\.942\.3830/322\.480\.723\.0531/20Q\-7B2\.440\.832\.7559/352\.250\.952\.3231/282\.900\.843\.2637/31Q\-14B2\.160\.802\.4539/232\.190\.952\.2531/282\.680\.843\.0041/32Q\-32B2\.160\.802\.4627/172\.340\.962\.4031/292\.910\.843\.2835/30HumanEvalCL\-7B1\.960\.672\.4458/202\.150\.942\.2430/302\.350\.692\.9733/19CL\-13B1\.950\.662\.4538/152\.230\.932\.3330/292\.350\.683\.0031/17MBPP\-100CL\-7B2\.290\.712\.8258/232\.470\.942\.5730/302\.750\.743\.3633/20CL\-13B2\.130\.692\.6338/162\.480\.942\.5930/302\.720\.743\.3432/19Table 5:Decoding efficiency \(DE\), hit rate \(HR\), Accept Length \(AL\), and overheads \(Dft/Ver\) of PTD, LADE, and Self\-Draft under greedy decoding\.