vllm - 💡(How to fix) Fix [Feature Request] SLEM (String-Level Exact Match) speculative decoding for heterogeneous vocabularies [1 pull requests]

Summary

Implement SLEM (String-Level Exact Match) speculative decoding as a complement to TLI (#38173 / #38174). While TLI restricts the draft model to the vocabulary intersection, SLEM lets the draft use its full vocabulary and verifies at the text level — achieving higher acceptance rates when vocabulary overlap is low (cross-family pairs).

Both algorithms are from the same ICML 2025 oral paper:

Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies Timor et al., https://arxiv.org/abs/2502.05202

Motivation

TLI (PR #38174) works well for same-family pairs with 95%+ vocabulary overlap (e.g., Qwen2.5-0.5B → Qwen2.5-1.5B). But for cross-family pairs — which are the most common real-world scenario — the intersection shrinks significantly:

When TLI constrains draft logits to a 72% intersection, the draft model's quality degrades — it can't express ~28% of its vocabulary, leading to lower acceptance rates and reduced speedup.

SLEM solves this by operating at the string level: the draft generates freely, its output is decoded to text and re-tokenized for the target, and verification uses exact matching. The draft's full expressiveness is preserved.

Algorithm (from the paper)

1. Draft model generates K tokens using its full vocabulary (no logit masking).
2. Decode draft tokens to text, re-tokenize with target tokenizer → m target tokens.
3. Single batched forward pass on target model over the m candidate tokens.
4. Sample from target logits at each position: t'_1, ..., t'_{m+1}.
5. Find first mismatch: j = argmin_j { t'_j != t_j }.
6. Accept t_1, ..., t_{j-1}, t'_j (matched prefix + bonus token from target).

Key properties:

• Provably lossless (Theorem 2.1 in the paper)
• Draft uses full vocabulary → higher quality proposals
• Up to 2.8x speedup reported in the paper (vs. 1.7x for TLI)

References

• Paper: https://arxiv.org/abs/2502.05202
• HuggingFace Transformers implementation (merged): https://github.com/huggingface/transformers/pull/35029
• TLI in vLLM: #38174
• TLI in SGLang: https://github.com/sgl-project/sglang/pull/22883