Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding

Thank you for your review and valuable comments. Please find our responses below, and we are more than happy to further improve our manuscript based on your suggestions.

1. Multi-user and batch-processing scalability.

We appreciate the reviewer's valuable suggestion on the discussion of batch processing. Yggdrasil can also be applied to multi-user or batch-processing scenarios to improve the efficiency of each single request. However, as shown in Figure 2, the source of improvement of speculative decoding originates from the redundant resources in the decoding process. Batch processing will also consume redundant resources by batching multiple requests, which will reduce the effectiveness of speculative decoding.

Recent work $1$ discusses the trade-off between speculative decoding and batch-processing at serving scenarios with fluctuating request rates. Yggdrasil can be integrated into such systems to improve the efficiency of the speculative decoding submodule, while the trade-off between speculative decoding and batch-processing still exists. The major challenge in adapting Yggdrasil for batch processing is that the fewer redundant resources available in the batch-processing scenario will reduce the effectiveness of speculative decoding. In such scenarios, the scheduler also tends to do less speculation and put more resources into batching requests. However, the proposed method can still benefit the single-request scenarios, such as on edge devices or latency-critical applications. We will clarify this point in the revised version of the paper.

$1$ Liu, Xiaoxuan, et al. "Optimizing speculative decoding for serving large language models using goodput." arXiv 2024.

2. Step-by-step breakdown of EGT and draft tree optimization.

Thank you for this suggestion. We study the performance breakdown and the contribution of each optimization in the ablation study in Section 7.4. The results show that all the optimizations contribute to the overall performance improvement. Specifically, graph compilation (O2) accounts for $2.775\\times$ performance improvement and stage-based scheduling (O4) accounts for $1.21\\times$ performance improvement. Please find more details in Section 7.4 and Figure 12.

We will revise Sections 3 and 7.4 to provide a clearer walk-through of the EGT construction and optimization process. In particular, we will annotate Figure 4 with the iterative steps and explicitly trace how speculative branches grow under budget constraints. Additionally, we will expand our ablation discussion to quantify each optimization’s contribution (see below).

3. Resource-constrained evaluation.

We now include results on an RTX 4090 GPU, which is representative of inference-grade hardware. Yggdrasil achieves up to 3.18× speedup in this setting. While we acknowledge that speculative decoding becomes less effective when fewer redundant resources are available, the method still offers gains. Evaluation on edge devices (e.g., Jetson) or TPUs is an exciting direction for future work, and we will mention this in the revision.

Table 1: Speedup benchmark on 4090 normalized to SpecInfer.

4. Dynamic and multi-modal tasks.

Our experiments currently focus on standard benchmarks and align with SpecInfer and Sequoia for fair comparison. Evaluating Yggdrasil on more dynamic or multi-modal tasks is a compelling future direction. We will update the paper to acknowledge this limitation and frame it as part of our ongoing work.

5. Contributions beyond prior work.

While speculative decoding is well-established, Yggdrasil contributes novel system-level optimizations that substantially improve real-world latency. Specifically, our EGT design enables low-overhead branching; our graph compilation transforms dynamic speculative paths into statically optimized kernels; and our latency-aware scheduler coordinates verification and drafting stages. Compared to prior work such as SpecInfer and Sequoia, which focus on speculative algorithms or fixed-depth trees, Yggdrasil introduces a new runtime abstraction that generalizes across speculative strategies. We will emphasize these distinctions more clearly in the revised paper.

Thank you for your review and valuable comments. Please find our responses below, and we are more than happy to further improve our manuscript based on your suggestions.

1. Single-node execution setting.

We apologize for the confusion. All experiments were conducted on a single node with one GPU. While we agree that extending speculative decoding to multi-node settings is an interesting direction, our current work aligns with prior literature by focusing on the single-node scenario. The proposed approach can be extended to multi-GPU environments, though such support would require careful scheduling of drafter model execution across devices—an exciting challenge we leave to future work. We will clarify this setup in the revised manuscript.

2. Per-token latency.

Thank you for your question. Per-token latency is defined as Execution Time / Number of Tokens, and it isolates the efficiency of the decoding process. We use this metric because speculative decoding can produce multiple tokens per decoding step, and per-token latency captures this efficiency more directly than total query execution time.

In contrast, query execution time includes both the prefill phase and decoding: Query Execution Time = Prefill Time + (Per-token Latency × Number of Tokens). By reporting per-token latency separately, we provide a clearer view of decoding performance across methods. We will clarify these definitions in the revised manuscript.

3. Target model selection.

We use different sizes of the Llama-2 series as both target and drafting models to evaluate the efficiency of the proposed method under different execution time settings. Using the models from the same series allows us to have a consistent comparison across different size settings. We pick the model's size setting following previous SOTA works on speculative decoding, such as $1,2$ .

$1$ Miao, Xupeng, et al. "Specinfer: Accelerating large language model serving with tree-based speculative inference and verification." ASPLOS 2024.

$2$ Chen, Zhuoming, et al. "Sequoia: Scalable and robust speculative decoding." NeuIPS 2024.

4. Trivial sequence structure.

By "trivial sequence structure," we refer to static sequence drafting that enables graph compilation without our proposed EGT mechanism. Despite its simplicity and lower AAL, this setup can outperform some advanced tree-based methods due to superior runtime efficiency. We analyze this trade-off in Section 3 (Motivation). Particularly, in the experimental results of Section 7.4, O2 ablates tree-based decoding to evaluate the effectiveness of graph compilation with the trivial sequence structure. We will clarify this terminology and its implications in the revised paper.

5. Model drift and extensibility.

While our work does not directly address model drift, our runtime is designed to be agnostic to model internals and compatible with any target model. Users can incorporate existing drift-handling techniques, such as parameter adjustments or runtime adaptations [3], by plugging them into our scheduling framework. We will make this extensibility clearer in the paper.

While our work does not directly address model drift, our runtime is designed to be agnostic to model internals and compatible with any target model. Our rationale is to provide a transparent runtime that supports any given target model. As such, users can specify any model drift handling method they prefer that modifies the model parameters. For more advanced model drifting handling techniques that require extra runtime processing, such as $3$ , they can also be integrated into our runtime with careful scheduling of such handling processes. We will clarify this point in the revised version of the paper.

$3$ Zhu, Jiaqi, et al. "In-Context Adaptation to Concept Drift for Learned Database Operations." Forty-second International Conference on Machine Learning.

6. Clarifying the AAL-1 adjustment.

We apologize for the confusion regarding the -1 term in AAL-1. The -1 terms mean that we subtract the number calculated by 1 to account for the bonus token of the verification model because they are guaranteed to be accepted. We exclude this token from the AAL calculation to better estimate the quality of speculation.

We appreciate your thoughtful feedback and suggestions. Below, we address your comments and welcome further input to enhance our manuscript.

1. Evaluation on inference GPUs.

We appreciate your suggestion to evaluate our method on inference-focused hardware. While we do not have access to L40 or 3090 GPUs, we conducted additional experiments on an RTX 4090 GPU inference GPU. As shown in the table below, Yggdrasil achieves up to 3.18× speedup compared to baselines, demonstrating its effectiveness even under more constrained computational environments. Due to the 24GB memory limit of the 4090, we only include results using the 7B verifier model.

Table 1: Speedup benchmark on 4090 normalized to SpecInfer.

2. Compatibility with Medusa.

We appreciate the reviewer’s interest in the connection between our method and Medusa-style speculative decoding. While our method is not directly applicable to Medusa-style drafting, since Medusa relies on a statically trained “head” module to generate speculative drafts, our approach introduces a more flexible mechanism that does not require access to the target model’s internals or retraining.

However, some components of our method can benefit Medusa-style decoding. For instance, the latency-aware optimization objective and the verification-width pruning strategy we propose are compatible with and potentially beneficial for improving the runtime efficiency of Medusa.

We will revise the paper to clarify these connections and discuss how the two approaches can complement each other in future work.

3. Integration with vLLM and other systems.

Yes, our method can be integrated into systems like vLLM. The main requirement is incorporating our compile-time optimizations (e.g., graph compilation and scheduling strategies described in Figure 8) into the backend infrastructure. We will elaborate on this integration path in the revision.

Thank you for recognizing the importance of the problem setting and acknowledging the clarity of our motivation and results.

Regarding the desire for additional experiments on larger or alternative model families, we would like to highlight the following:
1. Broad coverage of settings already included.
Our experiments are carefully designed to span a range of drafter and verifier pairings, backend platforms, sampling strategies, and datasets. This includes experiments on multiple model sizes within the LLaMA family, demonstrating consistent generalization in performance across those dimensions.
2. Alignment with prior speculative decoding evaluations.
In constructing these settings, we followed practices established in prior state-of-the-art studies $1,2$ . This ensures a fair comparison and solid baseline alignment.

$1$ Miao, Xupeng, et al. "Specinfer: Accelerating large language model serving with tree-based speculative inference and verification." ASPLOS 2024.

$2$ Chen, Zhuoming, et al. "Sequoia: Scalable and robust speculative decoding." NeuIPS 2024.

3. General empirical trends are robust across configurations.
Across all settings we examined, including varied model sizes and platforms, Yggdrasil reliably reduces latency overhead while preserving decoding quality.

While we believe these experiments convincingly support the general applicability and robustness of our approach, we would be pleased to include additional evaluations, such as on 32B-scale models or different model families, in the final version of the paper if deemed necessary. However, performing such large-scale experiments within the tight window of this rebuttal period presents practical challenges.

We hope this clarifies how our current results substantiate the claims of generality and effectiveness. Thank you again for your careful reading and constructive feedback.