DySpec: Faster Speculative Decoding with Dynamic Token Tree Structure
inference methods;efficient inference;speculative decoding
Yes
No ethics review needed.
More convincing experimental results that compare with more relevant related work.
1.	The correlation of Hypothesis 1 with the proposed method is well elaborated and explained.
2.	The structure of the paper is clear and easy to follow.
This work proposes a method to dynamically expand the token tree based on the draft distribution. A key difference between this work and existing approaches is that it introduces a smooth dynamic draft token tree construction method, which expands the tree along both width and depth without hyperparameter setup, within the given token budget. However, related works are missing, and the experimental setup should be properly improved.
1.	Lack of related work. Context-aware dynamic draft token tree is not a new idea. I would like to draw your attention to a very related work: “EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees” (EMNLP'24). This paper also proposes adopting dynamic draft token trees and claims a strong positive correlation between the draft model confidence score and the acceptance rate of the token. Another relevant paper is “Dynamic Depth Decoding: Faster Speculative Decoding for LLMs,” which further improves performance by dynamic depth. The methodology of EAGLE-2 is quite similar to this paper but differs in the tree construction method. Including this work in your paper and providing necessary discussion is essential.
2.	Experimental setup and results are weak. First, the dataset is too limited. I recommend adding more datasets like MT-Bench (Zheng et al., 2023), HumanEval (Chen et al., 2021), and GSM8K (Cobbe et al., 2021). Second, the 9.1× speedup is compared with the autoregressive method, and when compared with static tree methods like Sequoia, the results are much less overwhelming. Considering that the experimental setup lacks comparison with state-of-the-art dynamic draft token tree methods, the experiment does not fully convince me of the merits of this methodology.
3.	Writing needs improvement. Section 4.2 is hard to follow. The presentation of Figure 3 should be improved. Additionally, Figure 4 is not clear; please increase the font size.
Yes
No ethics review needed.
None
1. Strong Theoretical Foundation
- Provides rigorous theoretical analysis linking draft distribution to acceptance rate
- Includes formal proofs of optimality under stated assumptions
- Clearly bridges theoretical insights with practical implementation

2. Novel Technical Contributions
- Introduces an innovative dynamic token tree construction approach
- Develops efficient algorithms for both fixed-size and threshold-based tree construction
- Proposes block-sparsity friendly token ordering for optimization

3. Comprehensive Empirical Evaluation
- Tests across multiple model scales (7B to 70B parameters)
- Evaluates on diverse datasets (C4, OpenWebText, CNN DailyMail)
- Compares against strong baselines (Specinfer, Sequoia)
- Examines performance under different temperature settings

4. Implementation Efficiency
- Addresses practical concerns about overhead
- Provides C++ implementation to minimize token tree construction costs
- Includes detailed analysis of computation complexity
This paper introduces DySpec, a novel approach to speculative decoding that employs a dynamic token tree structure to improve inference speed for large language models. The authors present both theoretical and empirical evidence showing that higher draft probabilities correlate with higher acceptance rates. Based on this insight, they develop a greedy strategy for dynamically expanding the token tree at runtime. The method achieves impressive results, demonstrating up to 9.1× throughput improvement and 9.4× reduction in latency on Llama2-70B under low temperature settings, outperforming existing methods like Specinfer and Sequoia.
1. Limited Discussion of Limitations
- Could elaborate more on scenarios where the method might not perform optimally
- More discussion of the trade-offs between fixed-size and threshold-based approaches would be valuable

2. Implementation Details
- Some implementation specifics about the C++ optimizations could be expanded
- Could provide more guidance on threshold selection for different scenarios

3. Experimental Validation
- Could include more ablation studies to isolate the impact of different components
- Additional experiments on more diverse model architectures would strengthen generalizability claims
Yes
No ethics review needed.
- See the summary section 

Please answer some of the question there. I am happy to bump up the score to 6.
- The proposed idea is quite useful and can provide significant speedups for tree based speculative decoding methods. 

- The overheads reported our negligible.
Summary:

The authors propose dyspec to generate an optimal tree. The core idea is based on the idea that the target distribution and draft distribution should match.

The authors based on the idea propose an algorithm to come up with optimal tree. They overcome several implementation challenges and achieve reasonable speedups compared to existing baselines.

“DYSPEC achieves a 9.1× throughput improvement and 9.4× reduction in latency.” ([“DySpec”, p. 2]-> Should compare to SpecInfr or Medusa

“Figure 2: Connection between acceptance rate/target distribution and draft distribution on CNN DailyMail.The density of each block is normalized by column.” ([“DySpec”, p. 3] -> Can you please explain this figure. I think it’s the main motivation for your method, however it is not clearly explained, what this figure is showing.

“Specinfer-Baseline” ([“DySpec”, p. 7] -> Specifinfer requires training the models. What have authors done here.

“DYSPEC leverages CUDA Graph to capture 129 different input lengths ranging from 128 to 258” ([“DySpec”, p. 7-> What is the significance of CUDA Graph here, my understanding is CUDA graph is a mechanism to launch multiple kernels at the same time on the GPU to minimize the overhead of kernel dispatch

“We selected Llama2-7B as the draft model” ([“DySpec”, p. 7] -> What happens when you use the 68M model ?

“Set the maximum draft token tree size to 64, DYSPEC achieves up to a 9.1x improvement in throughput and a 9.4x reduction in latency compared to auto-regressive generation” ([“DySpec”, p. 8]-> Unfair comparison, compare to baselines

Additional experiments -

I would really like to experimentally understand the optimality of your tree. Will it be possible to construct an optimal tree based on some post-hoc data and compare it with the tree generated by Dyspec.
- See the summary section please.
Yes
No ethics review needed.
1. There are concurrent works using similar ideas. For instance, EAGLE 2 (https://arxiv.org/abs/2406.16858) attempts to maximize the acceptance rate based on a similar intuition (see Figure 6 in their paper). The authors should mention these works. What are the differences between your method and EAGLE 2?
1. Dynamic tree-based selection methods have appeared in prior literature. For example, Recurrent Drafter (https://arxiv.org/abs/2403.09919) proposes an RNN draft model and uses beam search for adaptive token selection. Did you modify the draft model architecture in your approach?
1. In practice, small draft models may be overconfident about incorrect answers in reasoning tasks. Have you studied your Hypothesis 1 across different tasks and analyzed the failure examples?
1. Does your method support batch inference? Have you experimented with large batch sizes to push your algorithm to its computational limits and test its throughput?
The proposed token selection method demonstrates improvement over existing methods such as Sequoia and Specinfer.
This paper proposes a draft token selection method in speculative decoding aimed at improving the token acceptance rate. The core idea is to use the draft model's prediction score as evidence to infer the token acceptance rate and use this information to select more promising tokens. The authors provide both theoretical and empirical analyses to support their approach.
1. The paper lacks discussion on existing works that share very similar ideas (see Questions 1 and 2). 
1. The experimental results do not sufficiently validate the method's effectiveness from various perspectives (see Questions 3 and 4).
@inproceedings{
anonymous2024dyspec,
title={DySpec: Faster Speculative Decoding with Dynamic Token Tree Structure},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=orr5uPZY28},
note={under review}
}
While speculative decoding has recently appeared as a promising direction for accelerating the inference of large language models (LLMs), the speedup and scalability are strongly bounded by the token acceptance rate.
Prevalent methods usually organize predicted tokens as independent chains or fixed token trees, which fails to generalize to diverse query distributions. 
In this paper, we propose \textsc{DySpec}, a faster speculative decoding algorithm with a novel dynamic token tree structure. 
We begin by bridging the draft distribution and acceptance rate from 
intuitive and empirical clues, and successfully show that the two variables are strongly correlated. Based on this, we employ a greedy strategy to dynamically expand the token tree at run time. Theoretically, we show that our method can achieve optimal results under mild assumptions. Empirically, \textsc{DySpec} yields a higher acceptance rate and speedup than fixed trees. \textsc{DySpec} can drastically improve the throughput and reduce the latency of token generation across various data distribution and model sizes, which significantly outperforms strong competitors, including Specinfer and Sequoia. Under low temperature setting, \textsc{DySpec} can improve the throughput up to 9.10x and reduce the latency up to 9.4x on Llama2-70B. Under high temperature setting, \textsc{DySpec} can also improve the throughput up to 6.21x, despite the increasing difficulty of speculating more than one token per step for draft model.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
inference methods efficient inference speculative decoding
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/f2ca849a13d7e71287b037b40fe8fb49b2d819e0.pdf
infrastructure, software libraries, hardware, systems, etc.
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
DySpec: Faster Speculative Decoding with Dynamic Token Tree Structure
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission