Research map / Large language models / Reasoning and chain of thought
Yggdrasil: Bridging Dynamic Speculation and Static Runtime for Latency-Optimal Tree-Based LLM Decoding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Yggdrasil co-designs latency-aware tree drafting (equal-growth tree) with a compiled, stage-scheduled speculative decoding runtime to speed up unmodified LLM decoding up to 3.98x over SpecInfer, Sequoia and vLLM-Spec.
Problem
Speculative decoding systems optimize average accepted length, which ignores verification latency and clashes with static-graph deep learning compilers, so dynamic tree drafts yield suboptimal wall-clock per-token latency.
Approach
An equal-growth tree (EGT) with predicted depth, width selection and verification-width pruning under a latency-aware speedup objective keeps static operator shapes for TorchInductor, and ahead-of-time stage execution with profile-guided scheduling overlaps CPU logic with GPU work.
Key results
- Achieves average per-token decoding latency speedup of 3.98x on A100 GPUs and 2.76x on A40 GPUs over baselines.
- TorchInductor graph compilation (O2) contributes an average 2.775x speedup in the optimization breakdown.
- Latency-aware speedup objective yields about 8% extra improvement over optimizing AAL directly.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Yggdrasil instead of state-of-the-art speculative decoding systems | LLM decoding · A100 (average decoding) | speedup: 3.98× | Helped |
| use Yggdrasil instead of state-of-the-art speculative decoding systems | LLM decoding · A40 (average decoding) | speedup: 2.76× | Helped |
| add TorchInductor graph compilation (ablation) | Yggdrasil · Llama-2-7B, Llama-68M drafter | speedup: 2.775 × | Helped |
| add verification width pruning using the speedup objective (ablation) | Yggdrasil O2 · Llama-2-7B, Llama-68M drafter | speedup: 1.07× | Helped |
| add graph-based scheduling (ablation) | Yggdrasil · Llama-2-7B, Llama-68M drafter | per-token equivalent latency improvement: 1.21× | Helped |
| add contextual draft depth predictor (ablation) | Yggdrasil · Llama-2-7B, Llama-68M drafter | speedup: 1.10× | Helped |
| optimize speedup instead of AAL (ablation) | Yggdrasil tree selection · C4 | performance: extra 8% | Helped |
| select tree width and verification number dynamically for each request | Yggdrasil EGT · Wikitest | speedup | Helped |
| use a context-adaptive tree instead of Sequoia's static tree | tree-based speculative decoding · Wikitest | AAL | Helped |
| set sampling temperature to 0 | Sequoia and Yggdrasil · Llama-7B and Llama-68M | performance | Helped |
Surprising findings
- Higher average accepted length does not translate linearly into end-to-end speedup once verification token count grows; per-token speedup flattens and can reverse.
- A simple sequence structure that is compilation-friendly can outperform more complex speculation algorithms end-to-end.
Limitations
- Results are for single-request latency-optimal setting; not evaluated for batched throughput serving.
- Depth predictor must be trained offline per dataset and drafter/verifier pair.
- Greedy sub-decisions for tree search are not globally optimal.
Experimental setup
Datasets: C4 Wikipedia CNNDaily
Benchmarks: C4 Wikipedia CNNDaily
Metrics: per-token latency (TPOT) average accepted length speedup
Baselines: SpecInfer Sequoia vLLM-Spec FlexFlow vLLM TRT-LLM
Builds on: SpecInfer Sequoia TorchInductor DISCO
Closest papers by meaning
- SWIFT: On-the-Fly Self-Speculative Decoding for LLM Inference Acceleration (ICLR 2025 · similarity 0.92)
- SpecExec: Massively Parallel Speculative Decoding For Interactive LLM Inference on Consumer Devices (NeurIPS 2024 · similarity 0.92)
- Scaling LLM Speculative Decoding: Non-Autoregressive Forecasting in Large-Batch Scenarios (AAAI 2026 · similarity 0.92)
- SpecForge: A Flexible and Efficient Open-Source Training Framework for Speculative Decoding (ICML 2026 · similarity 0.92)
- SpecBranch: Speculative Decoding via Hybrid Drafting and Rollback-Aware Branch Parallelism (ICLR 2026 · similarity 0.92)
- Dynamic-Width Speculative Beam Decoding for LLM Inference (AAAI 2025 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.