TokenTiming: A Dynamic Alignment Method for Universal Speculative Decoding Model Pairs

AI summary

Overview

Research area: Natural Language Processing — specifically LLM inference acceleration via speculative decoding, with a cross-disciplinary link to Dynamic Time Warping (DTW) from time-series alignment.

Technical level: Intermediate. Readers need familiarity with speculative decoding, tokenizers/vocabularies, and basic dynamic programming, but the core idea is explained geometrically in the paper.

Scope: The paper proposes TokenTiming, a training-free alignment algorithm that lets any off-the-shelf draft model accelerate any target model even when the two models do not share a vocabulary.

What This Paper Is About

Speculative decoding speeds up LLM inference by having a small "draft" model propose several tokens that a larger "target" model verifies in one pass, but standard verification requires both models to share the same vocabulary — a constraint that severely limits which draft models can be used and often forces expensive retraining. TokenTiming removes that constraint by converting the draft token sequence into a string, re-tokenizing it with the target tokenizer to get "proxy target tokens," and then using a DTW-style alignment to map probability distributions from the draft vocabulary onto the target vocabulary losslessly, with no retraining or model modification.

Key Contributions

1. Universal compatibility without shared vocabularies: TokenTiming allows any off-the-shelf draft model to be paired with a target model, even with mismatched tokenizers, by constructing the alignment on the fly at each decoding step.
2. A DTW-based probability transfer mechanism: The method builds a many-to-many mapping between the draft token sequence and the re-tokenized proxy target sequence using Levenshtein-based token distance and a Sakoe-Chiba Band constraint, then transfers probability distributions across that mapping for speculative sampling.
3. Strong and broad empirical results: On summarization, translation, code, and math, TokenTiming reaches up to 1.57× speedup over autoregressive baselines and surpasses the heterogeneous-vocabulary baseline TLI (Token-level Intersection).
4. Closing the gap to homogeneous-vocabulary SD: On 7B/33B models, TokenTiming yields up to 2.27× speedup (OPT-350M draft), approaching Medusa and EAGLE-1/2 while retaining the flexibility of plug-and-play draft model choice.

Main Findings

• Peak speedup of 1.57×: On Qwen3-32B with the Qwen3-0.6B draft, TokenTiming achieves up to a 1.57× speedup, versus TLI's maximum of 1.33× for the same target.
• Large gains on 70B targets: For DeepSeek-R1-Distill-Llama-70B, TokenTiming reaches 1.45× speedup while TLI peaks at 1.09×; for Llama-3.1-70B paired with OPT-350M, TokenTiming reaches 1.32×.
• Notable Phi-4 result: With Qwen2.5-0.5B as the draft, TokenTiming attains its peak of 1.54× on Phi-4, compared with TLI's best of 1.37× on that target.
• Tiny drafts can accelerate huge targets: Draft models as small as 68M parameters (Vicuna-68M) effectively accelerate 70B targets; drafte sizes tested range from 68M to 350M.
• Approaching homogeneous-vocabulary state of the art: On a 7B target, EAGLE-3 reaches 2.58× while the strongest heterogeneous baseline (TLI) peaks at 1.32×; TokenTiming with OPT-350M closes the gap to 1.80×, only 0.78× behind EAGLE-3. On a 33B target, TokenTiming-OPT-350M delivers 2.27×, within 0.44× of EAGLE-3 (2.71×) and already above Medusa (1.71×) and EAGLE-1 (2.21×).
• Task-level superiority over TLI: TokenTiming outperforms TLI on all five evaluation tasks (math, programming, translation, summarization, question answering). For mathematics, the Qwen3-32B + Qwen2.5-0.5B pair reaches 2.53× versus TLI's 1.44×; the paper also reports 2.54× versus 1.62× on summarization and 1.60× versus 0.94× on translation.
• Gains track draft model strength: Strong drafts such as Qwen2.5-0.5B and Qwen3-0.6B push speedup beyond 2× on reasoning-intensive tasks, while lightweight drafts (OPT-350M, Vicuna-68M) reduce the advantage, especially on math and code generation.
• Negligible overhead: DTW adds 0.1% to 0.5% of overall runtime; the paper reports the blocking time introduced per decoding cycle is only 663 μs, and the overhead is amortized by a 1.4× overall speedup.
• Window size matters: Testing w = 4, w = 8, w = 16, and w = ∞ (no Sakoe-Chiba Band), the best-performing setting is w = 8; even though the upper bound of the position deviation Δpos exceeds 8 in some model pairs, constraining the band still improves performance over w = ∞, suggesting appropriate constraints better preserve the token probability distribution.
• Perfect-vocabulary sanity check: With Qwen3-30B-A3B as target and Qwen3-0.6B as draft, the vocabulary intersection ratios are 1.000, and TokenTiming still improves TPS from TLI's 11.71 to 11.90 and speedup from 1.194 to 1.21.
• Repetition filtering: The authors excluded approximately 15% of test samples showing pathological repetitive generation loops, which can inflate speed metrics with near-perfect accept rates, leaving 85% of samples for the main analysis.
• Robustness on fragmented tokenizations: Alignment paths for prompts with special symbols show that even when WordPiece and Byte-Pair Encoding tokenizers segment special characters at different granularities, the end tokens of the two sequences remain aligned, consistent with TokenTiming's probability transfer logic.

Methodology in Plain English

The pipeline works in three steps per decoding cycle.

First, draft token calculation: the draft model autoregressively generates k tokens from the current prefix. Because the two models use different tokenizers, the sequence is first turned back into a plain string using the draft tokenizer, then re-encoded with the target tokenizer. This produces a "proxy target token sequence" whose length frequently differs from the draft sequence.

Second, alignment: TokenTiming runs its Dynamic Token Warping algorithm — a dynamic-programming procedure modeled on Dynamic Time Warping — to find the lowest-cost many-to-many correspondence between draft tokens and proxy target tokens. Token-to-token dissimilarity is measured with Levenshtein (edit) distance. A Sakoe-Chiba Band of width w restricts matching to a diagonal band, cutting complexity from O(k·m) to O(w·max(k,m)).

Third, verification and prefix update: the target model computes true conditional probabilities for the proposed sequence in one parallel pass, while the corresponding draft probabilities are transferred through the alignment (using the terminal token's probability for many-to-one mappings and copying the probability for one-to-many mappings). Each token is accepted with probability min(1, q(t)/p(t)); verification stops at the first rejection. The accepted tokens plus one newly sampled token extend the prefix, and the loop repeats.

The experiments use Spec-Bench with CNN/Daily Mail, WMT14 DE-EN, Natural Questions, and GSM8K, running 480 generations across twenty-five model pairs, with default Hugging Face hyperparameters and metrics including TPS, accept rate, speedup, TTFT, ITL, and Rep-N.

Why This Matters

Impact on research. The shared-vocabulary assumption has been a structural bottleneck in speculative decoding, forcing practitioners toward draft heads trained inside the target model (Medusa, EAGLE) or toward partial fixes like SLEM (no probabilistic sampling) and TLI (limited by the vocabulary intersection). TokenTiming reframes the problem as a sequence-alignment problem and shows that lossless sampling can be preserved across heterogeneous tokenizers without any training, which opens a new axis of research: draft model selection becomes a free variable rather than a constraint of the target.

Real-world applications:

• Latency-sensitive LLM serving: reported reductions in TTFT and ITL translate directly into faster chat and assistant experiences.
• Translation and summarization pipelines: these are among the tasks where the paper reports the largest speedups (up to 2.54× and 1.60× reported at task level).
• Reasoning and math workloads: TokenTiming exceeds 2× speedup on reasoning-intensive tasks when paired with strong small drafts such as Qwen2.5-0.5B and Qwen3-0.6B.
• Coding assistants: the programming task is evaluated in the paper, with gains that hold even though light-weight drafts reduce the advantage where token-level accuracy matters.

Industry relevance. Cloud providers and enterprises run targets ranging from 14B to 70B parameters, including dense, distilled, and Mixture-of-Experts (Qwen3-30B-A3B) architectures. Because TokenTiming accepts off-the-shelf drafts without retraining and works with any model pair, it removes the coupling between target choice and draft infrastructure. Model upgrades no longer invalidate a previously trained draft model, and organizations can reduce serving costs by pairing a 68M–350M draft with a 70B target instead of deploying a larger speculative setup.

Future Directions

• Beyond one-hot probability transfer: the limitations section notes that the probability form is one-hot, transferring only the top-1 token's probability; extending to richer distributions is a natural next step.
• Semantic rather than character granularity: the current DTW distance operates at character granularity rather than semantic granularity, which may limit alignment quality.
• Cross-lingual and cross-tokenization-granularity alignment: the authors note there are differences in alignment effectiveness between languages with different word tokenization granularities.
• Extending the comparison base: RDK (Redistributing draft model Kernels) is cited as related work but excluded from the baselines because its code was inaccessible, and the homogeneous-vocabulary comparison rests on reported figures from Medusa, EAGLE-1, and EAGLE-3 rather than a unified re-implementation.

Target Audience

Researchers and engineers working on LLM inference efficiency and serving systems will get the most from this paper, particularly those who have been blocked by vocabulary mismatch when choosing draft models. It is also relevant to practitioners deploying small models alongside large targets in production, and to students interested in seeing a classic sequence-alignment algorithm (DTW) repurposed for a modern NLP systems problem. Readers with only a beginner-level background in speculative decoding will need to consult the cited SD literature first, since the paper assumes that context throughout its preliminaries and proofs.

Authors’ abstract

Accelerating the inference of large language models (LLMs) has been a critical challenge in generative AI. Speculative decoding (SD) substantially improves LLM inference efficiency. However, its utility is limited by a fundamental constraint: the draft and target models must share the same vocabulary, thus limiting the herd of available draft models and often necessitating the training of a new model from scratch. Inspired by Dynamic Time Warping (DTW), a classic algorithm for aligning time series, we propose the algorithm TokenTiming for universal speculative decoding. It operates by re-encoding the draft token sequence to get a new target token sequence, and then uses DTW to build a mapping to transfer the probability distributions for speculative sampling. Benefiting from this, our method accommodates mismatched vocabularies and works with any off-the-shelf models without retraining and modification. We conduct comprehensive experiments on various tasks, demonstrating 1.57x speedup. This work enables a universal approach for draft model selection, making SD a more versatile and practical tool for LLM acceleration.