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

Zheng Wang (Alibaba Group, DAMO Academy) · Minyi Guo (Shanghai Jiao Tong University) · Zaifeng Pan (University of California, San Diego) · Yue Guan (University of California, San Diego) · Yufei Ding (University of California, San Diego) · Changming Yu (Shanghai Jiaotong University) · Shihan Fang (Shanghai Jiaotong University) · Weiming Hu (Institute of automation, Chinese academy of science) · Zihan Liu (MBZUAI IFM) · Yangjie Zhou (National University of Singapore) · Jingwen Leng (Shanghai Jiao Tong University)
compiler-friendly executioncontext-aware tree draftingdraft selectiondynamic speculationequal-growth tree structurehardware setupslatency-aware optimizationllm inferenceoverhead reductionspeculative decodingspeedupstage-based schedulingstatic graph compatibilitystatic runtime assumptionsunmodified llms

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.