Yggdrasil: Bridging Dynamic Speculation and Static Runtime  for Latency-Optimal Tree-Based LLM Decoding
Authors: Yue Guan
Changming Yu
Shihan Fang
Weiming Hu
Zaifeng Pan
Zheng Wang
Zihan Liu
Yangjie Zhou
Yufei Ding
Minyi Guo
Jingwen Leng
Venue: NeurIPS 2025 poster ()
Keywords: speculative decoding
machine learning system
large language model
Primary area: deep_learning

Abstract: Speculative decoding improves LLM inference by generating and verifying multiple tokens in parallel, but existing systems suffer from suboptimal performance due to a mismatch between dynamic speculation and static runtime assumptions. We present Yggdrasil, a co-designed system that enables latency-optimal speculative decoding through context-aware tree drafting and compiler-friendly execution. Yggdrasil introduces an equal-growth tree structure for static graph compatibility, a latency-aware optimization objective for draft selection, and stage-based scheduling to reduce overhead. Yggdrasil supports unmodified LLMs and achieves up to $3.98\times$ speedup over state-of-the-art baselines across multiple hardware setups.

Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding
Yue Guan 1,2 Changming Yu Shihan Fang', Weiming Hul Zaifeng Pan", Zheng Wang?, Zihan Liu 1.2 Yangjie Zhou Yufei Ding², Minyi Guo JJngwen Leng 1.2
Shanghai Jiao Tong University
Shhnngaai Qizhi Institute
University of California, San Diego
{bonboru, coonboru,fiche fichmi, ffng--ccounte mang-account,weiimnngghh weiminghu, altair lli,,yjuii...... zhhou guo-my, jaang-jw@ssjppee edu. en,
{zapan, zhw100, yufeiding) Bucsd..)ucdddddeee
Abstract
Speculative decoding improves LLM inference by generating and verifying multiple tokens in parallel, but existing systems suffer from suboptimal performance due mismatch between dynamic speculation and static runtime assumptions. We present Yggdrasil, co-designed system that enables latency-optimal speculative decoding through context-aware tree drafting and compiler-friendly execution. Yggdrasil introduces an equal-growth structure for static graph compatibility, latency- aware optimization objective for draft selection, and stage-based scheduling to reduce overhead. Yggdrasil supports unmodified LLMs and achieves up 3.98x speedup over state-of- titt-oofthheart
the-art art baselines across multiple hardware setups.
Introduction
Generative large language models (LLMs) have demonstrated remarkable performance across a wide range of domains, including language understanding reasoning [42), and multi-modal tasks M.I However, the increasing scale of LLMs introduces substantial computational and memory demands 52). resulting in high latency and deployment costs. To address these bottlenecks, numerous optimization strategies have been proposed (33 28 [9] Among them, speculative decoding 22 stands out for offering lossless acceleration by exploiting parallelism during auto-regressive generation.
Traditional decoding proceeds one token at time, where each new token is causally dependent on the previous one. This strictly sequential nature severely underutilized modern hardware. Speculative decoding breaks this bottleneck by generating multiple candidate tokens and verifying them in parallel using the original model. the draft matches the oracle, multiple tokens can be accepted in a single generation step, improving the overall throughput. This concept echoes classical architectural optimizations like branch prediction 38) and cache prefetching(5).
Yet despite its promise, existing speculative decoding systems fall short of optimal performance due fundamental mismatch between dynamic drafting algorithms and the static assumptions of modern compiler-based runtime. As illustrated in Fig. [ speculative decoding dynamically adjusts tree structures and operator shapes per decoding step to maximize token acceptance. This behavior inherently conflicts with the static dataflow graphs expected by deep learning compilers, which rely on fixed computation patterns for graph fusion, kernel tuning, and memory planning.
Moreover, current methods often optimize average accepted length (AAL) under simplistic assumption which ignoring non-unt mo-uffoorm verification costs. Mcanwhile, runtime systems typically treat speculative
Both authors contribute equally to this work.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Dynami
+
Eque--rowh
Nediva LiNaaaic
Toger Veriiaatoo
Bpcouiatied
dag codoo
00000000
Lauzon
Pratiin
Futl
Esscution
Offee lilin
Mi Alpotiion Centre
to flundime Garzze
(a Yapdrcal
Figure I: Overview of Yggdrasil.
Figure 2: Illustration of speculative decoding.
decoding as a black box without addressing the nontrivial CPU logic overhead, missing opportunities to exploit speculative decoding-spectie optimizations. These interlocked challenges constrain both algorithmic efficiency and system-level performance.
To overcome these limitations, introduce Yggdrasil, a latency-optimal speculative decoding system that co-designs algorithm and runtime execution. Yggdrasil is grounded on three core ideas: (1) Latency-aware objective: a trrdware-profileee optimization target that selects the optimal tree shape (depth, width, verification scope) to minimize real-world latency rather than proxy metrics like AAL (S. 4.1). (2) Equal-Growit Tree (EGT): a novel draft tree structure that ensures static operator shapes for compatibility with compile-time graph optimization, while maintaining flexibility to adapt wewpatiieedediin--yyeee framework that minimizes CPU-GPU coordination costs by eliminating conditional branches and overlapping dependent computations ($. 5)
to decoding context ($- 4.2). (3) Stage-based scheduling:
search
Yggdrasil system is built upon an open-sourced deep learning compiler TorchInductor 2 requires no modification to model architectures, supporting a wide range of LLMs. Across diverse hardware and model configurations, it achieves up to 3.98x speedup over oftte-of-the-art systems including SpecInfer, Sequoia, and vLLM-Spec. This research makes the following key contributions:
We design an equal-growth tree drafting algorithm optimizing a latency-aware objective that enables context-aware speculative decoding while preserving graph compilation compatibility ($. 4
We introduce a stage-scheduled runtime execution framework that reduces overhead by rearranging
and scheduling speculative decoding stages ($. 5
We implement and evaluate Yggdrasil real-world models and datasets, demonstrating consistent gains over existing baselines ($. 6 &
Background
Drafting and Verification. In the speculative decoding process, as shown with Fig. 2 the drafting phase involves generating candidate sequences of tokens for future steps. These sequences are then subjected to the verification phase, where their correctness is assessed by the oracle model. The corresponding models referred to drafter and verifier/target model. By enabling parallel token validation, speculative decoding reduces the number of decoding iterations.
Average Accepted Length. A key performance metric in speculative decoding is the average accepted length (AAL), which measures the average number of tokens accepted per decoding iteration. A higher AAL indicates greater efficiency, as more tokens are appended to the output.
Source of Improvements. The core insight behind the effectiveness speculative decoding lies in its utilization of underused computational resources. Many modern computing devices, such as the H100 GPU card [33], are memory-bound during decoding inference, underutilizing their computational capacity. This underutilization creates opportunity for speculative decoding to maximize resource efficiency. Additionally, the Transformer 43 decoder architecture, which forms the backbone of most LLMs, inherently supports parallelism, making it well-suited for speculative decoding. Specifically, the self-attention mechanism within the Transformer uses sequence-level mask to encode causal dependencies in the input sequence (43] This design verifies the speculative sequence in a single, parallel inference execution, as illustrated Fig. 2 The combination of speculative drafting and efficient sequence-level parallel verification enhances the decoding process.

---

Twn
Surei
Draft Method
Compliation
Reseurch
O-O-O.O-O O-O-O.O-
Adaplivity
Siructure
Dran
Verily
Sequance Partt (Speca live Decoding
Pladuce Koweeeee
Speculative Decoding
Surie
Sequence
3
DISCO (9)
Dynamic
Sequenoe
0
Speciafer
Stati
Tree
0
VLLM
Sequence
Sequoin
Steie
Tree
Yggdrasil
Dynamic
Tree
Mary The Specioler M8 Stmte (reasa)
Figure Comparison of drafting structures.
Table I: Comparison of prior arts.
Ilama-2-7b (Verifier)
Ilaia 68m (Drafter)
(a)
better
Step Latency bettte
Latency better
Lalency (ms)
60
Latency (ms)
40-
Latency (msi:
MLL
20-
10-
Eager Graph
Compltation
Eager Graph Compitation
Spectaerr derpors
R
Specdnser
Gtronss alla Poprrasc
Spectader
a
Verify Number
Verify Number Speedup
Lantery
Figure 4: Benchmark of Figure 5: Latency and speedup characteristics.
Figure 6: Comparison of AAL., per-step latency, and per-token latency.
different runtimes.
Tree-Based Drafting. While speculative decoding utilizes the redundant computational resources in the verification process, its generative drafting phase is still under-utilized as shown in Fig. 2 (b). One advanced approach in speculative decoding is the use of tree-based drafting. where predictions organized hierarchically in tree structure. This structure enables parallel verification and expands the exploration space for candidate tokens. While tree-based drafting significantly broadens the speculative exploration space and increases the AAL metric, its effectiveness is heavily influenced by the tree's 's structure and construction strategy, which impact both system performance and computational overhead.
SpecInfer (31] proposes generating multiple draft sequences with individual drafter models and reducing them into a tree structure. While this approach expands the exploration space. it introduces duplicate speculations, resulting in increased drafting overhead. An alternative approach from SpecInfer involves constructing K-ary tree by sampling the top-K tokens from the prediction distribution at each drafting step. This method covers a wide range of speculative possibilities and guarantees high AAL. However, it becomes impractical for deeper trees due to their exponential complexity, which limits their draft length.
41 introduces fully dynamic tree structure, where the tree's depth and width are determined on-the-fly based on sequence context. This dynamic approach achieves high AAL under a fixed verification budget but incurs significant runtime overhead due to its reliance on dynamic control flows and variable operation shapes, as further discussed in $.
Sequoia S takes a different approach by proposing a dataset-adaptive tree structure that balances AAL and runtime overhead. By profiling the optimal tree structure for given verification budget and dataset distribution. Sequoia optimizes performance. However, it applies the same tree structure all input tokens, disregarding the variability in drafting exploration space across different contexts.
3 Motivation
Although speculative decoding has a significant potential to accelerate L.M inference, existing systems fail to achieve optimal performance due to a fundamental gap between algorithm design and runtime support. To elaborate, we highlight two bottlenecks in the following.
Dynamic drafts break static compilation. As explained in $. [ context-aware tree drafting boosts AAL without increasing the number of verification tokens. Yet this dynamism collides head-on with the static-graphe assumptions baked into today's 's compiler optimizations, as illustrated in Fig. For instance, capturing Llama-2-78 2-BB with CUDA Graphs delivers 2.32x speedup, but the control-flow branches introduced by dynamic drafting cannot be frozen into a single graph, blocking this gain. Operator-level auto-tuning [7] suffers in the same way. Kernels compiled for one fixed shape yield an extra 1.23 speedup, but only when shapes stay constant. In short, the very flexibility that raises AAL deprives us of the compile-time optimizations that make LLM inference fast.
3

---

High AAL is not equal to high end-to-end speedup. Most prior work maximizes AAL under the tacit assumption that more accepted tokens translate linearly into wall-clock savings. That equivalence holds only when verification remains cheap, as in Fig. (a). Once the number of verification tokens grows, the verification latency per step escalates. while the actual per-token speedup curve flattens and eventually reverses(Fig. (b. Optimizing AAL in isolation produces diminishing or even negative returns. Any realistic objective must weigh acceptance gains against verification overhead in the current decoding context.
this case, we can still observe AAL speedup
Summary. These bottlenecks translate into sub- sub-optimal speculative system design as shown in
Fig. 6 Free-based approaches such as Sequoia push AAL high but retain high per-step latency. coopilatioo-oriennte systems like vLLM [27] and TRT-LLM [34] slash step latency through static kemelss yet can't exploit dynamic speculation, capping AAL. These all lead to sub-optimal per-token latency and no existing framework sinultaneously delivers both high AAL. and low runtime latency, exposing an urgent need for techniques that reconcile dynamic drafting with compilation efficiency.
4 Latency-Optimal Tree Speculation
In this section, we introduce novel tree-drafting method to address the challenges of dynamic speculative decoding. We first present a latency-aware optimization objective for speculative decoding. which maximizes the actual system wall time speedup. Then, introduce the context-aware dynamic tree drafting algorithm that is friendly to compile-time optimizations.
4.1 Latency-aware Optimization Objective
As discussed in S. existing systems usually maximize the AAL as an approximation for the system speedup.
Tgenerrtive
N NUMfiteration
Turget
Speedupraive
AAL
(I)
T sppcculative
T Target
where Numaiterttion is the number of forward inference steps executed in the naive generative paradigm to achieve the equal output length of speculative decoding, which is equal to the AAL. However, this approximation overlooks (1) the overhead of drafting iterations and (2) the latency characteristies of the models.
As such, we propose adopting more accurate speedup metric that considers the actual execution latency. We explain begin with the vanilla speculative decoding setting as following.
Igenerative
AAL * Tverifirr (1)
Speedup
T Sspeculative
Nurtaaraft
Trraner
T Tverifier N Wuliidran +
The T Tweriner (W) is the verification time of the verification model with W tokens verified in parallel as shown in Fig. (a). And the Nummrafft is the number of inference iterations of the drafter model to produce the speculation, which is greater equal AAL-I. The -1 term here originates from the bonus token of the verification model. However, this term is non-trivial to estimate as it is dependent on the hardware and model size. Previous works simplify it by strictly restricting the verification number to be smaller than a threshold and treat it as a constant. This simplification overlooks the opportunity to generate more tokens than the threshold with the extra verification time, which is beneficial when the current speculation is of high quality.
The problem is further complicated with the tree speculation since the AAL and Tama ( (Wa (rran) is dependent of the tree structure, specified as follows.
Speedup AAL(Warat draft: Daratt W Wverity) I veriiyyr (1) Epan Tärafer (Wa Wran + T Tverifier ( (werity)
where Waran, Daran, W Wverify are tree-related settings representing the width and depth of the tree. In specific, the depth of the tree determines the number of drafting iterations to launch. And the width of the tree determines the number of tokens to be drafted in parallel. With this objective, we get better estimation of the system latency that reflects the actual dynamic tree structure.

---

Verification Attantion Mask
Head
Wua
X
O
Inboedin
Patractor
Featuu
Depth
Head!
Wed
X 0
0-
Oud Dxch
Yayehool
O-d
Wed Hood
Dx
Mutti-hoad
Dpeth Predicttor
@ Predhet
Draft Whath
Venification Winth
Padle
Prediction
Selection
Proming
Figure 7: Equal-growth tree drafting and pruning.
Figure 8: System implementation.
4.2 Equal-Growth Tree
The challenge is to find the optimum tree structure that maximizes the speedup objective by adapt- ing to the context while being friendly to compile-time time optimizations.
the previous section, Equation 3 reveals that speedup depends not only on the AAL, but on the tightly coupled trio [Wann; Daman Wvenry). Searching this high-dimensional space exactly intractable, so we break the problem into three greedy-but but coodtiatedd-ubb--ecciiinn and introduce the Equal-Growth Tree (EGT) algorithm to bind them together.
EGT predicts the Draf and launches all draft graphs to eliminate per-token control-flow stalls. We then select the Waratt that maximizes the speedup objective under the predicted tree depth. Finally, we prune the draft tree to derive a subtree with size Wventy that maximizes the speedup objective. Together these steps yield context -aditiive yet runtime-friendly tree that outperforms prior synamic-ssquenne methods 30 27 in both AAL and throughput.
Draft Depth Prediction. We first predict Daran, i.e. the number of draft model invocations. A lightweight multi-head depth predictor is inserted with a two-layer MI. encoder and multiple depth prediction heads. The predictor consumes the target model's last-token embedding and outputs the expected acceptance length. We train this predictor offline for each dataset and drafter//erifier pair with training data collected once via profiling on an in-domain validation corpus. Unlike seration-wise approaches, we instantiate all Daraft draft graphs concurrently, eradicating CPU branch mispredictions and maximizing GPU overlap.
Draft Width Selection, We then select Waran to maximize the speedup objective under the predicted tree depth. This is greedy selection balance the trade-off between the AAL and the verification time by selecting the optimal width with predicted depth. While EGT grows exactly Wdran leaves per draft step, we may attach them anywhere in the partial tree: we choose the positions whose path-wise expected AAL gain is largest, using generation probabilities as surrogates for acceptance likelihood 44].
Verification Width Pruning. After drafting, we solve a maximum- subtree problem to respect the verification number W Weerify- Since the other terms in Eq are determined at this point, the problem is reduced to finding a sub-tree in the drafted speculation tree that maximizes the overall speedup objective. This is solved with dynamic programming algorithm that traverses the tree in bottom-up fashion, computing the speedup value for each node and its children. This post-processing is necessary only because online equal-grow is greedy predicted, because if the oracle optimum were known during growth, pruning would be unnecessary.
Lastly, we prepare the generated tree structure for parallel verification by generating the attention mask adhering to the tree's causal dependency(36).
5 Stage-based Scheduling Runtime
With the EGT, we can get runtime- friennde drafting algorithm that launches static computation graphs for GPU execution. However, this not the end of the story. The complex execution flow and dynamic control logic of speculative decoding causes heavy CPU overhead as shown in Fig. (a). That means some GPU operation are launched dynamically by the CPU evaluation results, which lead to bubbles on the GPU wall-time. For example, based on the verification results, apply
5

---

Rew Owpesiinyyy..........oooooo Shank
Growe
Accrpt
DPU
Aoaget Specalliion
Potter
DPU
Don'
Draf
Draf
Vorlection
Durt
Venillia Dynamic Specilativn Decoding
Alsarill Tomp
Suarsaler Plre
Eieccber Plana
Prun
Aozett
Trafle Guoded
DPV
Dritt
Dun
Drift
Voriiction
Deat
Dhufl
Disl:
Dul
Darslles Plan
(loas
(b) Yopskosil Equal- Growth Tree Decoding
[d] Profilee Guided Execution Pian Search
Figure 9: Stage-based speculative decoding scheduling runtime.
the accept speculation management on CPU and determine whether to draft for the last tail token onythe-fly. This leaves the GPU idle when applying the accept speculation stage. To this end, we discuss two speculative decoding- sppccfic runtime optimizations that originates from the dynamic and multi- stage nature of the speculative decoding. We first breaks the dependency between some stages by speculation to bring its execution ahead for better overlapping efficiency. And then we search for the best-performance execution plan under current EGT setting with profiling statistics.
5.1 Ahead-of-Time Stage Execution
In the naive speculative-decoding pipeline pronounced idle periods arise from control-flow depen- dencies, as shown in 1ig.19-a), Our EGT approach mitigates most bubbles in the drafting phase, but the post-verificttin validation step still suffers heavy CPU overhead. We therefore overlap CPU management with GPU inference to reduce wall-clock time. The challenge is that speculative decoding contains data dependencies that seemingly preclude such overlap-foe for example, we must know the set of accepted tokens before identifying the next head token to draft, partitioning execution into discrete stages (Fig. (c)) Our key observation is that several of these dependencies can be speculatively broken by executing downstream stages with a superset of the tokens actually required. Concretely, we advance two stages so they can proceed ahead-of-tines
Ahead-of- -of-emme Tail Draft. Instead of conditionally drafting only the final tail token, we speculatively draft the entire candidate sequence. Once any leaf is accepted, we simply reuse the corresponding results, eliminating the conditional branch. Because both acceptance and tail drafting are lightweight, they can run concurrently. This removes the tail-draft CPU logic from the critical path.
thead-of-Time Head Draft. Head drafting normally decodes a single token using the confirmed root, introducing a small GPU kernel on the execution critical path. We instead propose drafting on the entire forthcoming sequence, issuing the head draft immediately after the previous iteration's bonus draft. The released dependency lets us overlap head drafting with the acceptance stage, further compressing the execution timeline.
5.2 Profile-Guided Execution Plan Search
While ahead-of time execution unlocks overlap, it also inflates model execution overhead by process- ing extra tokens. The trade-off depends on the EGT parameters, the relative cost of each stage, and the target hardware. This results in a large and highly rivironment-dependee this with offline, profile-guided search framework that explores stage-overlap strategies within the block region of Fig. (b.. Upon the raw dependency graph shown in Fig. [c),,, we have the ahead-of-time executions breaking the dependency and the parallel stages that free to schedule. As such, we can search for the best execution plan with profiling results of each stage that estimates the end-to-end latency of each candidate schedule. For the ahead-of-time stages, moving stage forward introduces more drafting computation but creates additional overlap opportunities, making the sweet spot non-trivial. We keep the profiling metrics of both the original and ahead-of-time execution stages and use simple grid search to find the best execution plan. Thanks to the well-defined dependency graph, the search space is small and can be done offline at compile time. We visualize several representative plans in Fig. (c).
design space. We tackle
Implementation
Fig. showcases the architecture of Yggdrasil, which is meticulously designed to optimize spec- ulative decoding for modern inference systems. The system is divided into two tightly integrated

---

SpecInfer
Sequoia
VLLM VLLM-Spec
Yggdrasil
A100 Speedup
4-
PTM
2-
1-
haM
78-16GM
130.00M
130-160m
0-
78-6AM
70-160M
130-08M
130-L60M
O-
70-2aM
133--aM
A40 Speedup
Y N w
3-
2-
2-
78-6aM
78-160M
138-58M
138-1600
60M-
78-6aM
78-160M
1336-8M
138-180M
78-6aM
7B-180M
1338-6M
138-160M
C4
CNN
Wikitext
Figure 10: End-to-end per-token generation latency speedup results over SpecInfer 31
subsystems: (1) compile-time optimization modules and (2) runtime execution modules. At compile time, users provide a draft model, verifier model, and small calibration dataset. From this point forward, the workflow operates in fully model-agnostic manner, requiring source-level modifi- cations to the original networks. Yggdrasil leverages state-of-the-ard ML compilers to lower both models and employs profile-driven cost models to generate execution schedule optimized for the target hardware. Additionally, trains a lightweight depth predictor to guide speculative decoding, ensuring efficient and accurate execution.
At runtime, the core abstraction is the TokenTree class, which encapsulates the semantics of the EGT. The TokenTree seamlessly interacts with the draft and verifier models to generate speculative tokens and verify their correctness. provides robust interfaces for exchanging token sequences and their corresponding KV cache tensors with the draft and verifier models. The KV cache storage, along with other critical metadata such as the tree structure array, attention mask, and leaf positions, is efficiently managed as properties of the TokenTree.
The Yggdrasil system is implemented the PyTorch([2] framework, utilizing the Torchonductor compiler backend to achieve high performance. Importantly, the proposed dynamic speculation tree generation algorithm and pipeline runtime are designed to generalize across wide range of inference systems 34 20), making Yggdrasil a versatile and impactful solution for modern AI workloads.
Evaluation
7.1
Experimental Setup
Testbed. The evaluation of Yggdrasil encompasses servers featuring GPU cards of NVIDIA A100 (80G), A40 and Intel(R) Xcon(R) E5-2620 v3 @ 2.40GHz CPU. Our experiments rely essential dependencies: CUDA-IL: and TorchInductor.
Benchmark and Datasets. The proposed Yggdrasil system is designed to work seamlessly with various target models and datasets, ensuring broad applicability. While factors like model alignment and task complexity influence AAL and speedup, these orthogonal to the system design. Yggdrasill consistently outperforms benchmarks across diverse settings. To demonstrate its effectiveness, we evaluate it on language modeling datasets such C4 [39], Wikipedia 45,, and CNNDaily [18]. We
use Llama-2-7B and Llama-2-15 2-13B 13B as target models, paired with drafting models Llama-68M and
Llama- 160M (31, focusing per-token latency (TPOT) the primary metric.
Baselines. We evaluate the proposed Yggdrasil system by comparing it with a wide spectrum of related systems. For the end-to-end system performance, we compare it to ttate-of-the-ar speculative decoding systems and LLM serving runtimes, including vLLM 20) and FlexFlow [1. To benchmark the effectiveness of the proposed tree structure, we conduct experiments with reference to tree structures from the algorithm communities, including Sequoia [ and SpecInfer [I].
7.2 LLM Decoding Latency Benchmark
We evaluate the end-to-end latency performance of Yggdrasil for LLM decoding, focusing per- token latency to assess decoding efficiency. The results, shown in Fig. 10 highlight that Yggdrasil consistently outperforms all baselines, achieving average decoding latency improvements of 3.98x

---

soquence 2
[b) Sproddp
2-
ESTa32
EGT4/32
128
512
128
512
Yggdmol
Verity Number
Verify Number
Figure 11: AAL and speedup comparison of tree structures on Wikitest dataset.
Draft Width
Draft Width 16
Draft Width
01
02
03
04
O5
Verification Number
32
Speedup
5-
2.91
3.89
4.19
2.96
3.30
4.15
4.68
120 64
1.00
1.00
16
24
4 6
16
24
8
16
24
C4
Wikitext
Draft Depth
Figure 12: Optimization breakdown on Llama-2-7B model with Llama-68n as the drafter.
Figure 13: EGT parameter sensitivity anal- ysis with Llama-2-7B and Llama-68m.
on A100 GPUs and 2.76x on A40 GPUs. This demonstrates the effectiveness of its co-designed approach, surpassing both algorithm-centric designs like Sequoia and system-centric SpecInfer.
Among the baselines, SpecInfer performs the worst due significant overhead from GPU execution and serving runtime. Sequoia and vLLM-Spec leverage TorchInductor [2] for optimized model execution, achieving average speedups of 2.45 and 2.66 over SpecInfer, respectively. However, Yggdrasil further improves the speedup to 3.37x by incorporating context-aware speculation and CUDA-graph optimizations. Notably, the performance gains are more pronounced on A A100 GPUs, which suffer from greater hardware under-utilization, allowing Yggdrasil to maximize its benefits.
7.3 Tree Structure Comparison
We then evaluate the efficacy of the optimization techniques proposed in this work, delivering the end-to-end performance improvement together. We first benchmark the efficacy of the proposed EGT tree structure and the hardware-aware optimization objective.
Tree Structure. We evaluate the AAL of various tree structures in Fig. (1) The sequence speculative decoding paradigm shows limited AAL and quickly saturates as the verification number increases, restricting its speedup potential compared to tree-based structures. Sequoia, the SOTA baseline, achieves good AAL by statically adapting its tree structure based on the dataset and verification number. However, it uses the same tree structure for all inputs, ignoring context. In contrast, EGT dynamically adjusts its width, consistently outperforming Sequoia's static tree under optimal verification settings, highlighting the importance of context-aware tree structure selection.
Context-aware Dynamic Tree. We evaluate the impact of Yggdrasil's dynamic structure selection process using the theoretical speedup from Eq to approximate tree structure effectiveness. The results in Fig. (bb show that sequence speculative decoding achieves the lowest speedup, highlighting the need for tree structures. Static trees like N-way and Sequoia degrade as verification numbers increase due to higher verification latency from resource saturation ($. (). In contrast, EGTs with varying widths achieve optimal speedup under different verification settings. By dynamically selecting the best width and verification number for each request, Yggdrasil consistently outperforms all baselines, leveraging context and hardware characteristics for superior performance.
7.4 Optimization Breakdown
We then analyze the effectiveness of the proposed optimization techniques in the Yggdrasil system. We break down the overall performance improvement into five optimizations as shown in Fig. [2 Their performance and synergy are discussed in the following.
O1 only applying the latency-optimal tree speculation introduced in $. As its improvement largely correlates the runtime support, we benchmarked their effectiveness independently with other tree structures in the previous subsection. Here, O1 could be considered a general baseline, with its improvement reflected by the AAL metrics.
02 adopts graph compilation with the TorchInductor compiler for the drafter and verifier. We find that 02 accounts for average of 2.775x speedup, which is the most significant of the four

---

Per-token Labency 2.
ALL
Per-ooken Latency
Sequoia two
Socupia t-6.6
Speeduup
5-
Youdr asdi-
Youdrazk
78 8aM 78 160M 13B 68M13B 160M
0-
C4
Wikitext
CNN
Figure 14: Comparison with speedup and AAL as the optimization objectives.
Figure Latency with different sampling tem- peratures using Llama-7B and Llama-68M.
optimizations. This stresses the necessity of runtime support for the speculative decoding system. Note that the graph only be achieved with the EGT design to deliver high AAL simultancously. Compared to the end-to-end results, we find that using a trivial yet runtime-friendly sequence structure to fully utilize the compilation optimization outperforms some complex speculation algorithms. Yggdrasil bridges the optimizations to embrace improvements from both.
03 applies verification width pruning using the speedup objective enhance context flexibility. By dynamically adjusting the verification number, this optimization achieves an average speedup of x.07x over O2. The improvement primarily stems from the adaptive verification strategy. which reduces overhead by aligning the verification number with the saturation region the inference wall time curve (Fig. 5). This highlights the effectiveness of adaptive verification, technique applicable to all speculative decoding systems.
04 accounts for the graph- based scheduling optimization discussed in $. 3.51 It achieves an average of 1.21 improvement compared to the previous optimizations. Note that this is measured on the per-token equivalent latency generated by one decoding iteration. Since the number of accepted tokens scales with the wall time all stages in the iteration, this optimization significant to the system's performance. This suggests the importance of exploiting the speculative-decodnng specific optimizations within the existing execution runtime.
05 is the draft depth predictor that predicts the optimal drafting steps given the contextual embed- ding. To compare, we use fixed tree structure of depths of 16 and width of 8 as a baseline when 05 is excluded. We will further analyze the impact of the tree settings below. We find that the predictor brings a 1.10x speedup to the system by explicitly considering the difficulty of the context.
7.5
Sensitivity Analysis
EGT Structure. We conduct sensitivity analysis of the EGT parameters, as shown in Fig. 13 In 4.2, we described our method for determining optimal parameters at runtime. Here, we provide an intuitive exploration of the parameter search space, excluding invalid configurations. The results reveal that the interplay between draft width, draft depth, and verification number significantly impacts the achieved per-token latency. For instance, the combination Daraft = 8, Waraft 8, and W Weerify 64 yields the best performance in this static analysis.
Speedup Objective. Similarly, we conduct an ablation experiment to show the advantage of optimiz- ing the speedup objective rather than AAL on the C4 dataset shown in Fig. [4] Incorporating Eq, demonstrates an extra 8% performance improvement compared to optimizing AAL directly across all drafter-verifier settings. This is because compared to AAL, taking the speedup as the optimization objective enables better capturing of the runtime characteristic, including the dynamic draft and verifier exccution time.
Impact. We study the impact of adjusting the sampling temperature values on Sequoia and Yggdrasil. As Figure [5 shows, both Sequoia and Yggdrasil obtain better performance when the temperature is O. The reason that when the temperature low, the draft model can align better with the target model, resulting in higher AAL. Besides, across different temperatures, Yggdrasil consistently outperforms Sequoia, achieving an average speedup of 1.49x.
Temperature
8 Related Work
Speculative Decoding Variants and Serving Systems. Besides the work discussed in $ 3 there is broad range of research proposing variants of speculative decoding. First, model-transpurent researches improve the draft accuracy or efficiency without modifying the structure of the target model. Lookahead decoding [4], 35), and NEST[ apply more efficient retrieval statistical

---

methods to produce draft tokens instead of the draft model. Several works|31] design more complicated sampling procedures for better drat aceuracy. These works are orthogonal to Yggdrasil. In contrast, model-invasive methods modify the target model to either align the target and drat models [51] or produce the speculations using parts of the target model 266 12 or extra sub- modules 4 [5] to reduce draft overhead. These works require explicit modification of the origin model and are beyond the supporting scope of this work. Additionally, aside the serving systems [31 8 [00 benchmarked in $ SmartSpec [27] and MagicDec [6] study combining speculative decoding and continuous batching and achieving balance between the service level objective (SLO) and throughput improvement in online serving scenarios. However, they do not exploit the execution efficiency of the speculative decoding itself, which the main focus of this paper.
Dynamic Support in ML Systems. Many works study handling the dynamic workloads in machine learning systems. Frameworks like TensorFlow Eager and PyTorch Eager enable dynamic graph construction [16] at runtime but suffer from suboptimal hardware utilization. ML compilers, including Py'Torch 2.0 DietCode [49). Nimble(11), and BladeDISC(50) optimize the models with varying input shapes with adaptive graph transformation and code generation. For models with data-dependent execution paths, Cocktailer (47) Grape Cortex[13), BrainStorm [24 and DyCL optimize dynamic control flows to reduce the runtime overhead. Additionally, in dynamic serving scenarios, DyNet 32), BatchMaker [5], DVABatch(9), Brainstorm (24). ORCA[46). and Llumnix improve GPU utilization and throughput by dynamically adjusting batch sizes or optimizing scheduling. Despite the above advancements, these works still face limitations when handling the additional overhead of speculative decoding, where unpredictable batch sizes and control flows add significant complexity.
Limitations
The core results of Yggdrasil are derived under latency-optimal setting where a single interactive request monopolizes all available GPU memory and compute. This configuration mirrors edge or on-prem deployments where a dedicated accelerator serves one user latency-critical pipeline. While this assumption enables clean analysis of EGT drafting, it is not applicable for the batched, dtroughput-orienter serving. Production inference stacks typically batch tens to hundreds of prompts to maximize accelerator utilization. In that regime, co-coordinating speculative decoding with batch schedulers becomes essential to overall efficiency. Designing a unified policy that jointly decides when to speculate and how to pack requests paramount. short, while Yggdrasil pushes the latency frontier for single-request scenarios, extending the framework to the eitency-throughee joint optimization space, where speculative decoding and batch scheduling are solved together, remains an open line of research.
trade-offs and motivates the
10
Conclusion
In this work, we present Yggdrasil, a novel latency-optimal speculative decoding framework that enables context-aware speculation while preserving compile-time optimizations. Additionally, dynamically minimizes execution latency by adaptively selecting the optimal draft tree based on profiling-driven runtime insights. To further improve efficiency, Yggdrasil employs stage-based execution scheduling strategy, streamlining the speculative decoding workflow. Experimental evalua- tions demonstrate that Yggdrasil achieves substantial performance improvements, delivering superior speedups over state-of of systems.
10

---

Acknowledgment
This work was supported by the National Natural Science Foundation of China (NSFC) Grants 62222210 and Shanghai Qi Zhi Institute Innovation Program SQZ202316. Any opinions, findings, and conclusions in this paper are those of the authors only and do necessarily reflect the views of our sponsors. Jingwen Leng is the corresponding author. The authors express their gratitude to the anonymous reviewers for their insightful feedback, which greatly contributed to this work.
References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. {TensorFlow)> J: a system for (Large-Scale) machine learning. In 12th USENIX symposium operating systems design and implementation (OSDI 16), pages 265-283, 2016.
[2] Jason Ansel, Edward Yang. Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesen- sky, Bin Bao, Peter Bell, David Berard, Evgeni Burovski, Geeta Chauhan, Anjali Chourdia, Will Constable, Alban Desmaison, Zachary De Vito, Elias Ellison, Will Feng, Jiong Gong. Michael Gschwind, Brian Hirsh, Sherlock Huang, Kshiteej Kalambarkar, Laurent Kirsch, Michael Lazos, Mario Lezcano, Yanbo Liang, Jason Liang, Yinghai Lu, C. K. Luk, Bert Maher, Yunjie Pan, Christian Puhrsch, Matthias Reso, Mark Saroufim, Marcos Yukio Siraichi, Helen Suk. Shunting Zhang, Michael Suo, Phil Tillet, Xu Zhao, Eikan Wang, Keren Zhou, Richard Zou, Xiaodong Wang. Ajit Mathews, William Wen, Gregory Chanan, Peng Wu, and Soumith Chintala. Pytorch 2: Faster machine learning through dynamic python bytecode transformation and graph compi- lation. In Proceedings of the 29th ACM International Conference Architectural Support for Programming Languages and Operating Systems, Volume 2, ASPLOS '24, page 929-947, New York, NY, USA, 2024. Association for Computing Machinery.
[3]
Tom B Brown. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
[4] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D Lee, Deming Chen, and Tri Dao. Medusa: Simple Ilm inference acceleration framework with multiple decoding heads. arXiv preprint arXiv:2401.10771 2024.
[5] Pei Cao, Edward W Felten, Anna R Karlin, and Kai Li. A study of integrated prefetching and caching strategies. ACM SIGMETRICS Performance Evaluation Review, 23(1):188-19) 197, 1995.
[6] Jian Chen, Vashisth Tiwari, Ranajoy Sadhukhan, Zhuoming Chen, Jinyuan Shi, Ian En-Hsu Yen, and Beidi Chen. Magicdec: Breaking the sncnncy-throughpu tradeoff for long context generation with speculative decoding. arXiv preprint arXiv:2408. / 1049, 2024.
[7] Simin Chen, Shiyi Wei, Cong Liu, and Wei Yang. Dycl: Dynamic neural network compilation via program rewriting and graph optimization. In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 614-626, 2023.
[8] Zhuoming Chen, Avner May. Ruslan Svirschevski, Yuhsun Huang, Max Ryabinin, Zhihao Jia, and Beidi Chen. Sequoia: Scalable, robust, and hardware-aware speculative decoding. arXiv preprint arXiv:2402. 12374, 2024.
[9] Weihao Cui, Han Zhao, Quan Chen. Hao Wei, Zirui Li, Deze Zeng, Chao Li, and Minyi Guo. [DVABatch]: Diversity-aware (Multi-Entre (nntiiEEttr)) } (Multi-Exit) batching for efficient processing of [DNN} services on (GPUs}. In 2022 USENIX Annual Technical Conference (USENIX ATC 22), pages 183-198, 2022.
[10] Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprini arXiv: 181.00400, 2018.
[11] Alexey Dosovitskiy. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
[12] Mostafa Elhoushi, Akshat Shrivastava, Diana Liskovich, Basil Hosmer, Bram Wasti, Liangzhen Lai, Anas Mahmoud, Bilge Acun, Saurabh Agarwal, Ahmed Roman, et al. Layer skip: Enabling early exit inference and self-speculative decoding. arXiv preprint arXiv:2404.167710 2024.
11

---

[13] David Eliahu, Vishal Bollu, Robert Lucian Chiriac, and Omer Spillinger. Cortex: Produc- tion infrastructure for machine learning scale. [Online]. 2022. https://github. com/
cortexlabs/cortex
[14] Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang. Break the sequential dependency of Ilm inference using lookahead decoding. arXiv preprint arXiv:2402.02057. 2024.
[15] Pin Gao, Lingfan Yu, Yongwei Wu, and Jinyang Li. Low latency rnn inference with cellular batching. In Proceedings of the Thirteenth EuroSys Conference, pages 1-15,2018.
[16] Yue Guan, Yuxian Qiu, Jingwen Leng, Fan Yang, Shuo Yu, Yunxin Liu, Yu Feng, Yuhao Zhu, Lidong Zhou, Yun Liang, Chen Zhang, Chao Li, and Minyi Guo. Amanda: Unified instrumen- tation framework for deep neural networks. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1, ASPLOS '24, page 1-18, New York, NY, USA, 2024. Association for Computing Machinery.
[17] Yue Guan, Changming Yu, Yangjie Zhou, Jingwen Leng, Chao Li, and Minyi Guo. Fractal: Joint multi-level sparse pattern tuning of accuracy and performance for dnn pruning. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, ASPLOS '24, page 416-430, New York, NY, USA, 2024. Association for Computing Machinery.
[18] Karl Moritz Hermann, Tomá Kočiský, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 15, page 1693 1701, Cambridge, MA, USA. 2015. MIT Press.
[19] Weiming Hu, Haoyan Zhang, Cong Guo, Yu Feng, Renyang Guan, Zhendong Hua, Zihan Liu, Yue Guan, Minyi Guo, and Jingwen Leng. M-ant: Efficient low-bit group quantization for llms via mathematically adaptive numerical type. In 2025 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 1 1112-1126, 2025.
[20] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 611-66266 626, 2023.
[21] Woosuk Kwon, Gyeong-In Yu, Eunji Jeong, and Byung-Gon Chun. Nimble: Lightweight and parallel gpu task scheduling for deep learning. Advances in Neural Information Processing Systems, 33:8343-8354 2020.
[22] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pages 19274-19286. PMLR, 2023.
[23] Minghan Li, Xilun Chen, Ari Holtzman, Beidi Chen, Jimmy Lin, Wen-tau Yih, and Xi Victoria Lin. Nearest neighbor speculative decoding for Ilm generation and attribution. arxiv preprint arXiv:2405.1 19325, 2024.
[24] Xin- Ye Li, Jiang-Tian Xue, Zheng Xie, and Ming Li. Think outside the code: Brainstorming boosts large language models in code generation. arXiv preprint wwXiv:2305.10679 2023.
[25] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang, Eagle: Speculative sampling requires rethinking feature uncertainty. arXiv preprint arXiv:2401.15011 2024.
[26] Fangcheng Liu, Yehui Tang, Zhenhua Liu, Yunsheng Ni, Kai Han, and Yunhe Wang. Kangaroo: Lossless self-speculative decoding via double early exiting, arXiv preprint 11X19.2404.18911, 2024.
[27] Xiaoxuan Liu, Cade Daniel, Langxiang Hu, Woosuk Kwon, Zhuohan Li, Xiangxi Mo, Alvin Cheung, Zhijie Deng, Ion Stoica, and Hao Zhang. Optimizing speculative decoding for serving large language models using goodput. arXiv preprint 2xXiv:2406.14066 2024.
12

---

[28] Zihan Liu, Xinhao Luo, Junxian Guo, Wentao Ni, Yangjie Zhou, Yue Guan, Cong Guo, Weihao Cui, Yu Feng, Minyi Guo, Yuhao Zhu, Minjia Zhang, Chen Jin, and Jingwen Leng. Vq-Ilm: High-performance code generation for vector quantization augmented Ilm inference. In 2025 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 1496-1509, 2025.
[29] Jonathan Mamou, Oren Pereg, Daniel Korat, Moshe Berchansky, Nadav Timor, Moshe Wasserblat, and Roy Schwartz. Accelerating Speculative Decoding using Dynamic Speculation Length, May 2024. arXiv:2405.0433 [cs].
[30] Jonathan Mamou, Oren Pereg, Daniel Korat, Moshe Berchansky, Nadav Timor, Moshe Wasserblat, and Roy Schwartz. Accelerating speculative decoding using dynamic specula- tion length. arXiv preprint 24X5::2405.04304 2024.
[31] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, et al. Specinfer: Accelerating large language model serving with tree-based speculative inference and verification. Proceedings of the 29th ACM International Conference Architectural Support for Programming Languages and Operating Systems, Volume 3, pages 932-949, 2024.
[32] Graham Neubig, Chris Dyer, Yoav Goldberg, Austin Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang. Daniel Clothiaux, Trevor Cohn, al. Dynet: The dynamic neural network toolkit. arXiv preprint 17X1v:1001.03990, 2017.
[33] Nvidia. Nvidia h100 tensor core gpu. [Online], 2023, iitta-center/ine /hott/
https: http://wwwn.iiiid. www..omm/eeeeeee comm/nn-sa
[34] Nvidia. Tensorrt-Ilm. [Online]. 2023. httppp//ggtaabb..om////////aaant
[35] Jie Ou, Yueming Chen, and Wenhong Tian. Lossless acceleration of large language model via adaptive n-gram parallel decoding. arXiv preprint arXiv:2404.08698 2024.
[36] Zaifeng Pan, Yitong Ding, Yue Guan, Zheng Wang, Zhongkai Yu, Xulong Tang, Yida Wang, and Yufei Ding. Fasttree: Optimizing attention kernel and runtime for tree-structured LLM inference. In Eighth Conference on Machine Learning and Systems, 2025.
[37] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[38] James Smith. A study of branch prediction strategies. In 25 years of the international symposia Computer architecture (selecied papers), pages 202-215, 1998.
[39] David So, Wojciech Manke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Quoe V Le. Searching for efficient transformers for language modeling. Advances in neural information processing systems, 34:6010-6022, 2021.
[40] Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li, and Wei Lin. Llumnix: Dynamic scheduling for large language model serving. arXiv preprint arXiv: arXiv:2406.03243. 2024.
[41] Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems, 36, 2024.
[42] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsenseqa:: A ques- tion answering challenge targeting commonsense knowledge. arXiv preprint arXiv: 1.0097,,,, 2018.
[43] Vaswani, Attention all you need. Advances Neural Information Processing Systems, 2017.
13

---

[44] Jikai Wang. Yi Su, Juntao Li, Qingrong Xia, Zi Ye, Xinyu Duan, Zhefeng Wang, and Min Zhang. Opt-tree: Speculative decoding with adaptive draft tree structure. arXiv preprint arXiv:2406. / /7776, 2024.
[45] Wikipedia contributors. Plagiarism Wikipedia, the free encyclopedia, 2004. [Online; accessed 22-July-2004).
[46] Gyeong-In Yu, Joo Seong Jeong, Geon- Kim, Soojeong Kim, and Byung-Gor Chun. Orca: A distributed serving system for (Traaesforer-Baseed)) generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pages 521-538, 2022.
[47] Chen Zhang, Lingxiao Ma, Jilong Xue, Yining Shi, Ziming Miao, Fan Yang, Jidong Zhai, Zhi Yang, and Mao Yang. Cocktailer: Analyzing and optimizing dynamic control flow in deep learning. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI
23), pages 681-699, 2023.
[48] Zijian Zhang, Kaiyuan Zheng, Zhaorun Chen, Joel Jang, Yi Li, Chaoqi Wang, Mingyu Ding, Dieter Fox, and Huaxiu Yao. Grape: Generalizing robot policy via preference alignment. arXiv preprint arXiv:2411.19300 2024.
[49] Bojian Zheng. Ziheng Jiang, Cody Hao Yu, Haichen Shen, Joshua Fromm, Yizhi Liu, Yida Wang, Luis Ceze, Tianqi Chen, and Gennady Pekhimenko. Dietcode: Automatic optimization for dynamic tensor programs. Proceedings of Machine Learning and Systems, 4:848- 863, 2022.
[50] Zhen Zheng, 7aifeng Pan, Dalin Wang, Kai Zhu, Wenyi Zhao, Tianyou Guo, Xiafei Qiu, Minmin Sun. Junjie Bai. Feng Zhang, al. Bladedisc: Optimizing dynamic shape machine learning workloads via compiler approach. Proceedings of the ACM on Management of Data, 1(3):1-29, 2023.
[51] Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Ros- tamizadeh, Sanjiv Kumar, Jean-François Kagy, and Rishabh Agarwal. Distillspee: Improving speculative decoding via knowledge distillation. arXiv preprint Xiv:23300008611 2023.
[52] Zixuan Zhou, Xuefei Ning, Ke Hong, Tianyu Fu, Jiaming Xu, Shiyao Li, Yuming Lou, Luning Wang, Zhihang Yuan, Xiuhong Li. al. A survey on efficient inference for large language models. arXiv preprint arXiv:2404.142200 2024.
[53] Xunyu Zhu, Jian Li, Yong Liu, Can Ma and Weiping Wang. A Survey on Model Compression for Large Language Models, September 2023. arXiv:2308.0708 07633 [es].
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We explicitly highlight the contributions and discuss them in detail in the intro- duction section, ensuring alignment with the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We include a section discussing the the limitation of latency-oriented optimiza- tion in the appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer:
[NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We discuss the experimental settings to reproduce the results in the evaluation setup section.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
We will open-source our code once accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //ipss.cc/pill wttpcccppppppppeeeeeeeeeeeeeeeee httpa//gggeeee/eeeeubbiisssssss /Cc////oddiiisssseeeeeee ssiiiiiiiiiiiyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We discuss details of training in the experimental setup section of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The evaluation results is statically averaged over the evaluation set different context-dependdnt samples.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We indicate the details in the experimental setup section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The reaserch conform in every respect with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All asssets are properly cited.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
21


Reviews:
[{"review_id": "NWKFGvx3LV", "reviewer": "Reviewer_Jtf9", "summary": "The paper aims to address  the mismatch between dynamic speculation and static runtime assumptions. The paper presents\nYggdrasil, which contains context-aware tree drafting and compiler-friendly execution. Yggdrasil introduces an equal-growth tree structure for static graph compatibility, a latency-aware optimization objective for draft selection, and stage-based scheduling to\nreduce overhead.  Experimental results demonstrate the effectiveness of the proposed methods.", "questions": "No", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n(1) The problem is interesting and important \n(2) The motivation is clearly presented.\n(3) Experimental results demonstrated the effectiveness.\nWeaknesses:\n(1) More experiments on larger target models (such as 32B) would be appreciated\n(2) More experiments on different series of models would be appreciated, not just LLaMA", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the importance of the problem setting and acknowledging the clarity of our motivation and results.\n\nRegarding the desire for additional experiments on larger or alternative model families, we would like to highlight the following:  \n1\\. **Broad coverage of settings already included.**  \nOur 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.  \n2\\. **Alignment with prior speculative decoding evaluations.**  \nIn 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.\n\n> \\[1\\] Miao, Xupeng, et al. \"Specinfer: Accelerating large language model serving with tree-based speculative inference and verification.\" ASPLOS 2024\\.  \n> \\[2\\] Chen, Zhuoming, et al. \"Sequoia: Scalable and robust speculative decoding.\" NeuIPS 2024\\.\n\n3\\. **General empirical trends are robust across configurations.**  \nAcross all settings we examined, including varied model sizes and platforms, Yggdrasil reliably reduces latency overhead while preserving decoding quality.\n\nWhile 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.\n\nWe hope this clarifies how our current results substantiate the claims of generality and effectiveness. Thank you again for your careful reading and constructive feedback."}, {"review_id": "hrtEt1Tupe", "reviewer": "Reviewer_7bU2", "summary": "Yggdrasil is a speculative LLM decode for low latency query answering in LLMs. it relies on a preprocessing step to control the speculation.Exec results are used to support this design.", "questions": "- Offline model consttruction: do you handle drift?\n\n\"  greater or equal to AAL-1. The -1 term here originates from the136\nbonus token of the verification model \"-> Where is the -1 term?\n\nfollowed by \"However, this term is non-trivial to estimate as it is dependent137\non the hardware and model size:  -> -1?? :)\nThis is a critical point in the paper, so it is a bad point to have a typo or to be unclear :(.", "limitations": "the authors discuss the major limitation", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The man strength of the  model is in using a better definition of latency that includes the actual  costs. \\this is possible through execution profiiing and offline model construction. This allows to coantrol speculation and to select a good tree shape.[\n\nI was a bit disappointed by the evaluation:\n- I suppose this is geared at servers, so I´d  expect to see the number of nodes (1?\\)\n- per token latency: this means the time since the token is  until ? Why not just query execution time?\n- \"We257\nuse Llama-2-7B and Llama-2-13B as target models, paired with drafting models Llama-68M and258\nLlama-160M\"-Why these two similar models?\n- 'we find that using a trivial yet runtime-friendly sequence structure' -> can you please  be specific here?\n- how does this co,pare to the non-speculative baseline?\n\nI would suggest having part of the Limitations App in the main text.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**1. Single-node execution setting.**\n\nWe 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.\n\n2. **Per-token latency.**\n\nThank 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.\n\nIn 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.\n\n**3. Target model selection.**\n\nWe 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\\].\n\n> \\[1\\] Miao, Xupeng, et al. \"Specinfer: Accelerating large language model serving with tree-based speculative inference and verification.\" ASPLOS 2024\\.  \n> \\[2\\] Chen, Zhuoming, et al. \"Sequoia: Scalable and robust speculative decoding.\" NeuIPS 2024\\.\n\n**4. Trivial sequence structure.**\n\nBy \"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.\n\n**5. Model drift and extensibility.**\n\nWhile 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.\n\nWhile 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.\n\n> \\[3\\] Zhu, Jiaqi, et al. \"In-Context Adaptation to Concept Drift for Learned Database Operations.\" Forty-second International Conference on Machine Learning.\n\n**6. Clarifying the AAL-1 adjustment.**\n\nWe 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."}, {"review_id": "eoMTeTubAM", "reviewer": "Reviewer_wxyL", "summary": "This paper proposes Yggdrasil, a co-designed system for speculative decoding of LLM. Specifically, an equal-growth tree drafting algorithm is designed to optimize a latency-aware objective that enables context-aware speculative decoding while preserving graph compilation compatibility. Moreover, a stage-scheduled runtime execution framework is introduced to reduce the overhead by rearranging and scheduling speculative decoding stages. Experiments show that the proposed system outperforms the existing systems in some point.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well organized and easy to follow.\n\n- The proposed latency-optimal speculative decoding framework makes sense and is theoretically better than the accept length based method.\n\n- The proposed stage-based execution scheduling strategy sounds interesting. \n\nWeaknesses:\n\n- The experiments are conducted on A100 and A40, what about the results on inference GPU such as L40 or 3090s?\n\n- The proposed method is tree-based, is it suitable for Medusa?\n\n- Could the proposed method combine with vLLM or other system?", "was_revised": true, "final_justification": "Thanks for the authors' response to my concerns. I decide to maintain my score.\n\n- The authors evaluate the performance on inference-focused hardware and verify the effectiveness of the proposed method.\n\n- The authors demonstrate that the proposed method can be integrated into systems like vLLM, which will increase the practicality of the proposed method.", "rebuttal": "We appreciate your thoughtful feedback and suggestions. Below, we address your comments and welcome further input to enhance our manuscript.\n\n**1. Evaluation on inference GPUs.**\n\nWe 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.\n\n**Table 1: Speedup benchmark on 4090 normalized to SpecInfer.**\n\n| Model | Dataset | SpecInfer | Sequoia | vLLM-Spec | Yggdrasil |\n| :---- | :---- | :---- | :---- | :---- | :---- |\n| 7B-68M | C4 | 1 | 2.12436975 | 1.77777778 | **2.61745953** |\n| 7B-68M | wikitext | 1 | 2.14254587 | 1.36233538 | **2.47883773** |\n| 7B-68M | CNN | 1 | 2.11828104 | 1.68846572 | **2.64091574** |\n| 7B-160M | C4 | 1 | 2.40308989 | 2.85166667 | **3.04366079** |\n| 7B-160M | wikitext | 1 | 2.57425945 | 1.5785351 | **2.92095503** |\n| 7B-160M | CNN | 1 | 2.71867322 | 2.76763382 | **3.18370541** |\n\n**2. Compatibility with Medusa.**\n\nWe 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. \n\nHowever, 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.\n\nWe will revise the paper to clarify these connections and discuss how the two approaches can complement each other in future work.\n\n**3. Integration with vLLM and other systems.**\n\nYes, 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."}, {"review_id": "B7pTl3JNmy", "reviewer": "Reviewer_xZfa", "summary": "This paper presents Yggdrasil, an advanced system designed to optimize speculative decoding in large language model (LLM) inference, aiming to enhance decoding efficiency and reduce latency through integrated algorithmic and runtime optimizations. The core innovation of Yggdrasil lies in its combination of a latency-aware optimization objective, context-aware dynamic tree drafting, and stage-based scheduling, which collectively minimize per-token latency and idle time during CPU-GPU interactions. The system dynamically selects an optimal draft tree structure based on runtime profiling insights, facilitating efficient decoding. Built on the TorchInductor compiler, Yggdrasil is compatible with various LLMs without requiring model modifications. Experimental results show up to 3.98×speedup on A100 GPUs compared to existing methods like SpecInfer and Sequoia, showcasing its superior performance in speculative decoding. Yggdrasil offers significant improvements in latency and throughput, making it a valuable advancement for LLM inference tasks.", "questions": "1. Given that Yggdrasil focuses on single-request latency, are there plans to extend it for multi-request or batch processing? What challenges would arise in adapting it for such environments?\n2. The experiments primarily evaluate Yggdrasil on NVIDIA A100 and A40 GPUs. How does Yggdrasil perform across various hardware, especially on edge devices or resource-constrained environments like mobile devices or TPUs?\n3. While Yggdrasil outperforms several state-of-the-art systems like SpecInfer and Sequoia in single-request latency optimization, How does Yggdrasil perform on more dynamic, multi-modal tasks or with larger model sizes compared to other systems?\n4. How much of the performance improvement is due to the Equal-Growth Tree (EGT), and how do other optimizations like graph compilation and stage-based scheduling contribute?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1) The paper introduces Yggdrasil, a novel framework for optimizing speculative decoding in large language models, achieving significant performance improvements through the integration of latency-aware optimization and runtime execution strategies.\n2) The paper is well-structured, explaining complex concepts like latency-aware optimization, dynamic tree drafting, and stage-based scheduling clearly. Visual aids enhance understanding despite the technical depth.\n3) The work addresses latency reduction in LLM inference, crucial for real-time applications. Its model-agnostic design enhances its applicability across LLMs without requiring modifications.\n4) The paper introduces the Equal-Growth Tree (EGT) algorithm and latency-aware optimization, offering significant advancements over existing systems with its dynamic tree drafting and stage-based scheduling.\n\nWeaknesses:\n1) While the system shows substantial improvements for single-request inference, it does not explore how Yggdrasil scales to multi-user or batch-processing scenarios, which are common in real-world applications. The absence of performance analysis in these contexts may limit its practical utility in large-scale deployment.\n2) Sections on the EGT algorithm and draft tree optimization are technically dense; a step-by-step breakdown and scalability analysis would improve clarity.\n3) The work focuses on single-request optimization, neglecting latency-throughput trade-offs in batch-processing systems, reducing its broader impact.\n4) While original in its optimization strategies, speculative decoding is an established concept, and the incremental contribution could be better highlighted through comparison with existing systems, particularly in how it builds on existing approaches like SpecInfer and Sequoia.", "was_revised": true, "final_justification": "The rebuttal has addressed most of my concerns.", "rebuttal": "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.\n\n**1. Multi-user and batch-processing scalability.**\n\nWe 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.\n\nRecent 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.\n\n> \\[1\\] Liu, Xiaoxuan, et al. \"Optimizing speculative decoding for serving large language models using goodput.\" arXiv 2024\\.\n\n2. **Step-by-step breakdown of EGT and draft tree optimization.**  \n\nThank 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\\.\n\nWe 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).\n\n**3. Resource-constrained evaluation.**\n\nWe 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.\n\n**Table 1: Speedup benchmark on 4090 normalized to SpecInfer.**\n\n| Model | Dataset | SpecInfer | Sequoia | vLLM-Spec | Yggdrasil |\n| :---- | :---- | :---- | :---- | :---- | :---- |\n| 7B-68M | C4 | 1 | 2.12436975 | 1.77777778 | **2.61745953** |\n| 7B-68M | wikitext | 1 | 2.14254587 | 1.36233538 | **2.47883773** |\n| 7B-68M | CNN | 1 | 2.11828104 | 1.68846572 | **2.64091574** |\n| 7B-160M | C4 | 1 | 2.40308989 | 2.85166667 | **3.04366079** |\n| 7B-160M | wikitext | 1 | 2.57425945 | 1.5785351 | **2.92095503** |\n| 7B-160M | CNN | 1 | 2.71867322 | 2.76763382 | **3.18370541** |\n\n**4. Dynamic and multi-modal tasks.**\n\nOur 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.\n\n**5. Contributions beyond prior work.** \n\nWhile 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."}]

Author rebuttal:

Meta-review: The paper introduces Yggdrasil, a system for latency-optimal speculative decoding that combines equal-growth tree drafting, latency-aware optimization, and stage-based scheduling to bridge the gap between dynamic speculation and static runtimes. Reviewers agree the work is well motivated, clearly written, and technically solid, with consistent latency improvements demonstrated over existing baselines. They also highlight that the system design is broadly applicable and compiler-friendly, making it a valuable contribution to LLM serving. 

The main concerns raised were the limited evaluation scope (restricted to LLaMA models and single-node, single-GPU setups), unclear definitions around per-token latency, the AAL-1 adjustment, and the notion of a “trivial sequence structure,” as well as a lack of discussion of batch or multi-user serving scenarios. In their rebuttal, the authors responded thoroughly: they clarified the experimental setup and latency definitions, explained the AAL-1 adjustment and the role of trivial sequence structures, and provided new results on inference hardware (RTX 4090) showing strong speedups. They also discussed scalability, the trade-offs between batching and speculation, and how Yggdrasil integrates with systems like vLLM and could complement Medusa-style decoding.

These clarifications and additions convincingly addressed reviewer concerns, and all reviewers maintained positive recommendations. While broader evaluations (e.g., on larger models or multi-tenant settings) would further strengthen the work, the paper as revised offers a technically solid and practically relevant contribution. Overall, I recommend acceptance.
Decision: Accept (poster)