Research map / Large language models / Reasoning and chain of thought
Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
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.
Proposes three lossless speculative decoding methods (SLEM, TLI, SLRS) that let any off-the-shelf drafter with a different vocabulary from the target be used without retraining, with speedups up to 2.8x over autoregressive decoding.
Problem
Standard speculative decoding requires the drafter and target to share a vocabulary, which limits drafter choice and often forces training a new drafter from scratch.
Approach
Three SD variants for heterogeneous vocabularies: string-level exact match (text as shared intermediate representation with re-tokenization), token-level intersection (renormalize drafter onto shared tokens and use standard verification), and string-level rejection sampling (verify whole strings, with probability psi(t) computed over draft sequences).
Key results
- SLEM reaches up to 2.79x speedup over autoregressive decoding (CodeLlama-13b-Instruct-hf with tiny_starcoder_py on HumanEval, 1x A6000).
- TLI achieves up to 1.74x speedup over autoregressive decoding (CodeLlama-13b-Instruct-hf with tiny_starcoder_py on HumanEval).
- Mixtral-8x22B with vicuna-68m drafter via SLEM achieves 2.1x speedup on CNN-DailyMail.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SLEM instead of autoregressive decoding with vicuna-68m as drafter | Mixtral-8x22B-Instruct-v0.1 · CNN/DailyMail | speedup: 1.0 -> 2.1 | Helped |
| Use SLEM instead of autoregressive decoding with DeepSeek-R1-Distill-Qwen-1.5B as drafter | DeepSeek-R1-Distill-Qwen-14B · CNN/DailyMail | speedup: 1.0 -> 0.73 | Hurt |
| Use SLEM instead of autoregressive decoding with vicuna-68m as drafter | DeepSeek-R1-Distill-Qwen-14B · CNN/DailyMail | speedup: 1.0 -> 1.43 | Helped |
| Use SLEM instead of autoregressive decoding with tiny_starcoder_py as drafter | CodeLlama-13b-Instruct-hf · HumanEval | speedup: 1.0 -> 2.79 | Helped |
| Use TLI instead of autoregressive decoding with Qwen2.5-0.5B-Instruct as drafter | Mixtral-8x22B-Instruct-v0.1 · SCROLLS | speedup: 1.0 -> 1.69 | Helped |
| Use TLI instead of autoregressive decoding with CodeLlama-7b-Instruct-hf as drafter | CodeLlama-13b-Instruct-hf · HumanEval | speedup: 1.0 -> 1.77 | Helped |
| Use TLI instead of autoregressive decoding with CodeLlama-7b-Instruct-hf as drafter | DeepSeek-R1-Distill-Qwen-14B · HumanEval | speedup: 1.0 -> 0.75 | Hurt |
| Normalize the drafter distribution to sample only from the target-draft vocabulary intersection | TLI versus the union strategy · Heterogeneous vocabulary distributions | acceptance rate | Helped |
| Use string-level rejection sampling instead of string-level exact matching | SLRS versus SLEM · Heterogeneous vocabulary distributions | expected acceptance rate | Helped |
Surprising findings
- Some heterogeneous drafters underperform autoregressive decoding (speedups below 1, e.g., 0.63x with CodeLlama-7b as drafter for DeepSeek-R1-Distill-Qwen-14B).
- Computing psi(t) for SLRS grows exponentially with token length; for Qwen2-7B vocabulary the maximum number of combinations reached 65,536, making SLRS impractical for long tokens.
Limitations
- Acceptance rate depends heavily on drafter accuracy; inaccurate drafters yield slowdowns.
- SLRS computational cost grows exponentially with drafter token length, limiting practicality.
- TLI acceptance rate depends on vocabulary intersection size and is zero if the intersection is empty.
Experimental setup
Datasets: CNN-DailyMail SCROLLS HumanEval
Benchmarks: CNN-DailyMail SCROLLS HumanEval
Metrics: tokens per second time to first token (ms) time per output token (ms) speedup over autoregressive decoding expected acceptance rate vocabulary intersection size
Baselines: autoregressive decoding standard speculative decoding (Hugging Face)
Builds on: speculative decoding block verification standard speculative decoding rejection sampling
Closest papers by meaning
- SPEED-Bench: A Unified and Diverse Benchmark for Speculative Decoding (ICML 2026 · similarity 0.92)
- A Theoretical Perspective for Speculative Decoding Algorithm (NeurIPS 2024 · similarity 0.92)
- RAPID: Long-Context Inference with Retrieval-Augmented Speculative Decoding (ICML 2025 · similarity 0.92)
- Judge Decoding: Faster Speculative Sampling Requires Going Beyond Model Alignment (ICLR 2025 · similarity 0.92)
- Scaling Up, Speeding Up: A Benchmark of Speculative Decoding for Efficient LLM Test-Time Scaling (ICLR 2026 · similarity 0.91)
- Nearest Neighbor Speculative Decoding for LLM Generation and Attribution (NeurIPS 2024 · 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.