REVIEW 3 major objections 4 minor 1 cited by
Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read Speculative decoding can now work with models that use different token vocabularies.
desk verdict Useful, well-theorized paper on heterogeneous-vocabulary speculative decoding, but the losslessness claim overreaches for non-injective tokenizers. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a string-level translation of token sequences between two vocabularies. Given a draft vocabulary D and target vocabulary T, the paper defines expressibility and tokenization with respect to a vocabulary, then uses plain text as the shared representation. For SLEM, the key mechanism is exact matching after re-tokenizing draft text with the target tokenizer. For SLRS, the key identity is the acceptance probability function ψ(t), defined as the sum of draft-sequence probabilities whose tokenized concatenation starts with target token t; the proof that the algorithm is lossless relies on this function. For TLI, the key mechanism is projecting the drafter's distribution onto the vocabulary intersection and renormalizing, which the paper proves yields an acceptance rate at least as high as for a union-vocabulary projection.
What would settle it
Run SLEM with a non-injective tokenizer pair, generate a large output sample, and perform a two-sample test comparing the distribution of output strings to autoregressive decoding on the same prompt distribution; if the distributions differ significantly, the losslessness claim for SLEM on such tokenizers fails. A cheaper test is to count whether the longest-stretch realignment ever changes the accepted token sequence in a way that the target model's own re-tokenization would not produce.
Extended reading notes
Core claim
The paper's central claim is that speculative decoding can be made to work with heterogeneous vocabularies, where the draft and target models tokenize text differently. The first method, String-Level Exact Match (SLEM), uses plain text as a shared intermediate: draft tokens are decoded to text, re-tokenized with the target vocabulary, and then verified by exact string matching. The second method, Token-Level Intersection (TLI), renormalizes the drafter's distribution over the intersection of the two vocabularies and applies standard rejection sampling. The third, String-Level Rejection Sampling (SLRS), extends rejection sampling to the string level and is proved lossless via a new acceptance probability function. The paper proves losslessness for all three and proves that TLI has an acceptance rate at least as high as a naive union-vocabulary approach. On real model pairs, SLEM and TLI yield reported speedups over autoregressive decoding, and the paper emphasizes that both algorithms were integrated into a widely used inference library.
Load-bearing premise
The alignment heuristic for non-injective tokenizers in SLEM preserves the target distribution, but the paper does not prove this.
Editorial extensions
If this is right
- Any off-the-shelf model can serve as a drafter, including small models with different tokenizers, so users no longer need to train a drafter from scratch or restrict themselves to in-family drafters.
- For target models that lack a same-vocabulary drafter, heterogeneous speculative decoding provides an acceleration path that standard speculative decoding cannot.
- Faster and cheaper LLM inference could lower serving costs and enable lower-latency applications with models that were previously not amenable to speculative decoding.
- The losslessness guarantees mean the output distribution of the target model is preserved, so the acceleration should not introduce output-quality regressions compared to autoregressive decoding.
- The paper's analysis of ψ(t) shows that string-level rejection sampling is practical only for drafters with short tokens or compact vocabularies, narrowing its use case relative to SLEM and TLI.
Reading between the lines
- The paper's acceptance-rate analysis suggests that, for a given drafter-target pair, the best algorithm could be selected by comparing measured acceptance rates under SLEM, TLI, and SLRS; the paper leaves this algorithm-selection question implicit.
- Because TLI relies on the intersection of vocabularies, it behaves like standard speculative decoding with a restricted drafter distribution; for pairs with small intersections, one might predict that SLEM, which can accept strings spanning multiple target tokens, would outperform TLI, though the paper does not make this comparison explicit.
- A testable extension is measuring whether SLEM's realignment heuristic for non-injective tokenizers preserves the target distribution on a carefully designed corpus of strings that trigger normalization mismatches; the paper does not provide such a test.
- The exponential growth of ψ(t) with token length, shown for real vocabularies, suggests that hybrid or approximate computations of ψ(t) could make SLRS viable for larger vocabularies; the paper leaves this as future work.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes three speculative decoding algorithms that remove the shared-vocabulary constraint between drafter and target models: SLEM (Algorithm 2), which uses plain text as an intermediate representation and string-level exact matching; SLRS (Algorithm 3), which performs rejection sampling at the string level; and TLI (Algorithm 4), which reweights the drafter distribution onto the token-level intersection of the two vocabularies. The paper claims that all three methods are lossless, that they work with off-the-shelf models without training, and that SLEM and TLI yield speedups of up to 2.8x over autoregressive decoding. Theoretical results include Theorem 3.2 (SLRS losslessness), Theorem 3.1 (exact matching has lower acceptance than standard SD under identical distributions), Theorem 4.1 (TLI dominates the union-vocabulary baseline), and Lemma 3.1 on the exponential cost of computing psi(t). The empirical evaluation covers summarization, code generation, and long-context tasks across many model pairs and hardware settings, and the authors report that SLEM and TLI have been integrated into Hugging Face Transformers.
Significance. If the central claims hold, this is a practically useful contribution: it removes a real constraint of speculative decoding, enables off-the-shelf drafters with mismatched tokenizers, and the results are backed by an open-source implementation that has been adopted in a widely used library. The theoretical parts are mostly self-contained and do not fit parameters to reach conclusions; Theorem 4.1 and Theorem 3.2 are genuine, checkable statements. The main value is the SLEM algorithm, whose headline speedups of up to 2.8x come from non-standard model pairs. The main weakness is that the losslessness guarantee for SLEM is established only for injective tokenizers, while the paper claims losslessness for all tokenizers and evaluates SLEM with at least one non-injective tokenizer (vicuna-68m). This gap affects the load-bearing claim of the paper and needs to be resolved before the results can be accepted at face value.
major comments (3)
- [Section 3.2, Algorithm 2, Tables 1 and 11] The abstract and contribution list state that all three methods are lossless, but the losslessness of SLEM is only argued for injective tokenizers. Section 3.2 introduces a heuristic for non-injective tokenizers: the algorithm searches for the longest overlap between previously accepted target tokens and the newly re-tokenized draft sequence, then keeps only the suffix beyond that overlap. This procedure is not part of Algorithm 2's pseudocode, no formal statement is given for it, and no proof shows that the resulting accepted tokens are still draws from the target distribution. Table 11 reports that double7/vicuna-68m is non-injective, and vicuna-68m is used as a drafter in the SLEM speedup results in Tables 1 and 6 (e.g., the 2.1x Mixtral row). The overlap search can merge, drop, or reorder tokens relative to the target model's own sampled sequence, so the state fed to the next iteration need not be a prefix of a target-model draw, breaking the coupling on which exact-match losslessness relies. The authors should either formalize the alignment step as part of the algorithm and prove that it preserves the target distribution, or restrict the losslessness claim to injective tokenizers and adjust the empirical claims accordingly.
- [Section 3.3, Theorem 3.2, Algorithm 3] Theorem 3.2 defines psi(t) with a fixed number of draft tokens i, namely as a sum over sequences d1,...,di. Algorithm 3, however, samples d1,...,d_i until a lookahead indicator S1(i) is satisfied, so the stopping time i is random and the distribution over stopped sequences is not described. The text asserts that 'Algorithm 3 and Theorem 3.2 both hold for this more general lookahead indicator function,' including the recommended early-stopping condition of stopping once the first target token is determined, but no statement or proof of this generalization is provided. The theorem should be restated for a random stopping rule, or the scope of the claimed losslessness should be limited to the fixed-lookahead case.
- [Section 3.4, Lemma 3.1, Appendix G] Lemma 3.1 counts the number of ways to partition the target token t into contiguous substrings and claims this equals the number of draft-token sequences with T(d1+...+di)_1 = t. This equality is not established for the actual tokenization function T, which uses longest-prefix matching. If the target vocabulary contains a token that extends t (for example, t='a' and the vocabulary also contains 'ab'), then a drafted string 'ab' is tokenized with first token 'ab', not 'a', so the condition T(d1+...+di)_1 = t is stricter than the composition count. The 2^{m-1} count is therefore not a proof of the stated claim unless additional conditions on T or on the target and draft vocabularies are imposed. If the lemma is intended only as an illustrative calculation for a specific complete-vocabulary setup, that should be stated precisely; as written, it overstates the generality of the exponential-count result.
minor comments (4)
- [Abstract and Section 5] The abstract says 'our algorithms demonstrate significant speedups,' but only SLEM and TLI are evaluated empirically; SLRS is analyzed theoretically and in Section 3.4 is described as potentially impractical. The wording should be made precise, for example by saying SLEM and TLI demonstrate speedups while SLRS is a theoretical method with feasibility analysis.
- [Tables 1 and 6] The tables mix 'Tok/s' and 'T/s' for the same throughput quantity. The units should be unified, and the TPOT values in the phi-4 rows (e.g., '47' milliseconds) should be given with one decimal place for consistency with the other rows.
- [Section 6, Table 3] The expected acceptance rate for Algorithm 2 is written as P_t [p(t) * psi(t)], which is nonstandard notation for a sum over t in T. Please use an explicit summation, and clarify whether this is the expected acceptance of the first target token or the expected number of accepted tokens per iteration.
- [Section 5] The claim that SLEM and TLI 'had become the default inference pipeline behavior' in Hugging Face Transformers is a strong external-validation claim. It would be helpful to cite the specific Hugging Face release notes or pull requests so that readers can verify the dates and the exact default behavior.
Circularity Check
No circularity found: each algorithm's losslessness follows from target-model sampling or external rejection-sampling proofs, and the empirical speedups are measured rather than fitted.
full rationale
No load-bearing step reduces to its own inputs. Algorithm 2 (SLEM) is argued lossless by an exact-coupling construction: in lines 9-11, tokens are accepted only when they coincide with samples drawn from the target model, so the accepted prefix is exactly a target-model sample. That is a direct construction argument, not an assumed conclusion. The Section 3.2 heuristic for non-injective tokenizers is not accompanied by a proof, and if it changes the accepted sequence it could break the coupling; however, this is an omitted-proof/correctness risk, not a circularity. Algorithm 3 (SLRS) has a formal proof in Theorem 3.2 and Appendix G: ψ(t) is defined as the induced draft-string probability, and the proof computes Pr[output t] = p(t) using the standard rejection-sampling identity; the result is derived, not assumed. Algorithm 4 (TLI) inherits losslessness from the externally proved rejection-sampling method of Leviathan et al. (2023) and Chen et al. (2023), and Theorem 4.1 proves the acceptance-rate comparison by algebra on the definition of q' and the inequality Σ_{x∈T} q(x) ≤ 1. No parameter is fitted and then renamed as a prediction: the acceptance-rate formulas are derived from the definitions of p and q, and the speedup tables are empirical measurements against autoregressive decoding. The self-citations (Timor et al. 2025; Mamou et al. 2024) are contextual background on drafter-speed conditions and lookahead control, and they are not load-bearing for the main losslessness theorems. Accordingly, the derivation chain is self-contained with respect to circularity.
Assumptions & free parameters
free parameters (2)
- draft lookahead i =
varies per experiment
- SLRS threshold n (lookahead) =
not specified in main text
assumptions (3)
- domain assumption Standard SD verification (Algorithm 5) is lossless, as proved by Leviathan et al. (2023) and Chen et al. (2023).
- domain assumption Target vocabulary T is expressible in draft vocabulary D and vice versa (T↠D* and D*↠T*).
- domain assumption The intersection between target and draft vocabularies is non-empty for TLI to have positive acceptance rate.
Cite this review
Pith. "Pith review of Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies." pith.science (2026). https://pith.science/paper/UWRSOLDM
@misc{pith2026250205202,
author = {Pith},
title = {Pith review of: Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies},
year = {2026},
howpublished = {\url{https://pith.science/paper/UWRSOLDM}},
note = {Machine review of arXiv:2502.05202}
}
read the original abstract
Accelerating the inference of large language models (LLMs) is a critical challenge in generative AI. Speculative decoding (SD) methods offer substantial efficiency gains by generating multiple tokens using a single target forward pass. However, existing SD approaches require the drafter and target models to share the same vocabulary, thus limiting the pool of possible drafters, often necessitating the training of a drafter from scratch. We present three new SD methods that remove this shared-vocabulary constraint. All three methods preserve the target distribution (i.e., they are lossless) and work with off-the-shelf models without requiring additional training or modifications. Empirically, on summarization, programming, and long-context tasks, our algorithms demonstrate significant speedups of up to 2.8x over standard autoregressive decoding. By enabling any off-the-shelf model to serve as a drafter and requiring no retraining, this work substantially broadens the applicability of the SD framework in practice.
Figures
Forward citations
Cited by 1 Pith paper
-
Out-of-Vocabulary Sampling Boosts Speculative Decoding
RDK redistributes a pruned drafter's probability mass using a token co-occurrence prior to restore acceptance rates in speculative decoding, but its formal guarantees are not established.
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
-
[2]
Accelerating large language model decoding with speculative sampling
Chen, C., Borgeaud, S., Irving, G., Lespiau, J.-B., Sifre, L., and Jumper, J. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318, 2023
arXiv 2023
-
[3]
Chen, J., Tiwari, V., Sadhukhan, R., Chen, Z., Shi, J., Yen, I. E.-H., and Chen, B. Magicdec: Breaking the latency-throughput tradeoff for long context generation with speculative decoding. arXiv preprint arXiv:2408.11049, 2024
arXiv 2024
-
[4]
DeepSeek-AI, Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., Zhang, X., Yu, X., Wu, Y., Wu, Z. F., Gou, Z., Shao, Z., Li, Z., Gao, Z., Liu, A., Xue, B., Wang, B., Wu, B., Feng, B., Lu, C., Zhao, C., Deng, C., Zhang, C., Ruan, C., Dai, D., Chen, D., Ji, D., Li, E., Lin, F., Dai, F., Luo, F., Hao, G., Chen, G., ...
arXiv 2025
-
[5]
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024
arXiv 2024
-
[6]
Assisted generation: a new direction toward low-latency text generation, 2023
Joao Gante . Assisted generation: a new direction toward low-latency text generation, 2023. URL https://huggingface.co/blog/assisted-generation
2023
-
[7]
Subword regularization: Improving neural network translation models with multiple subword candidates
Kudo, T. Subword regularization: Improving neural network translation models with multiple subword candidates. In Gurevych, I. and Miyao, Y. (eds.), Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp.\ 66--75, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi:10...
-
[8]
Kudo, T. and Richardson, J. S entence P iece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Blanco, E. and Lu, W. (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp.\ 66--71, Brussels, Belgium, November 2018. Association for Computat...
Show all 23 references
-
[9]
H., Gonzalez, J., Zhang, H., and Stoica, I
Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pp.\ 611--626, 2023
2023
-
[10]
Fast inference from transformers via speculative decoding
Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp.\ 19274--19286. PMLR, 2023
2023
-
[11]
B., Zi, Y., Muennighoff, N., Kocetkov, D., Mou, C., Marone, M., Akiki, C., LI, J., Chim, J., Liu, Q., Zheltonozhskii, E., Zhuo, T
Li, R., allal, L. B., Zi, Y., Muennighoff, N., Kocetkov, D., Mou, C., Marone, M., Akiki, C., LI, J., Chim, J., Liu, Q., Zheltonozhskii, E., Zhuo, T. Y., Wang, T., Dehaene, O., Lamy-Poirier, J., Monteiro, J., Gontier, N., Yee, M.-H., Umapathi, L. K., Zhu, J., Lipkin, B., Obloku...
2023
-
[12]
Accelerating speculative decoding using dynamic speculation length
Mamou, J., Pereg, O., Korat, D., Berchansky, M., Timor, N., Wasserblat, M., and Schwartz, R. Accelerating speculative decoding using dynamic speculation length. arXiv preprint arXiv:2405.04304, 2024
2024 arXiv
-
[13]
Miao, X., Oliaro, G., Zhang, Z., Cheng, X., Wang, Z., Zhang, Z., Wong, R. Y. Y., Zhu, A., Yang, L., Shi, X., et al. Specinfer: Accelerating generative large language model serving with tree-based speculative inference and verification. arXiv preprint arXiv:2305.09781, 2023
2023 arXiv
-
[14]
Abstractive text summarization using sequence-to-sequence RNN s and beyond
Nallapati, R., Zhou, B., dos Santos, C., Gu l c ehre, C ., and Xiang, B. Abstractive text summarization using sequence-to-sequence RNN s and beyond. In Riezler, S. and Goldberg, Y. (eds.), Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning , p...
2016 doi
-
[15]
Efficiently scaling transformer inference
Pope, R., Douglas, S., Chowdhery, A., Devlin, J., Bradbury, J., Heek, J., Xiao, K., Agrawal, S., and Dean, J. Efficiently scaling transformer inference. Proceedings of Machine Learning and Systems, 5: 0 606--624, 2023
2023
-
[16]
and Nakajima, K
Schuster, M. and Nakajima, K. Japanese and korean voice search. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.\ 5149--5152, 2012. doi:10.1109/ICASSP.2012.6289079
2012
-
[17]
Neural machine translation of rare words with subword units
Sennrich, R., Haddow, B., and Birch, A. Neural machine translation of rare words with subword units. In Erk, K. and Smith, N. A. (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp.\ 1715--1725, Berlin, Ge...
2016 doi
-
[18]
H., Beirami, A., and Suresh, A
Sun, Z., Ro, J. H., Beirami, A., and Suresh, A. T. Optimal block-level draft verification for accelerating speculative decoding. arXiv preprint arXiv:2403.10444, 2024
2024 arXiv
-
[19]
Distributed speculative inference of large language models
Timor, N., Mamou, J., Korat, D., Berchansky, M., Pereg, O., Wasserblat, M., Galanti, T., Gordon, M., and Harel, D. Distributed speculative inference of large language models. arXiv preprint arXiv:2405.14105, 2024
2024 arXiv
-
[20]
N., and Rush, A
Wang, J., Gangavarapu, T., Yan, J. N., and Rush, A. M. Mambabyte: Token-free selective state space model. In First Conference on Language Modeling, 2024. URL https://openreview.net/forum?id=X1xNsuKssb
2024
-
[21]
L., Gugger, S., Drame, M., Lhoest, Q., and Rush, A
Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma, C., Jernite, Y., Plu, J., Xu, C., Scao, T. L., Gugger, S., Drame, M., Lhoest, Q., and Rush, A. M. Transformers: St...
2020
-
[22]
Yang, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Li, C., Liu, D., Huang, F., Wei, H., et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115, 2024
2024 arXiv
-
[23]
Fastdraft: How to train your draft, 2024
Zafrir, O., Margulis, I., Shteyman, D., and Boudoukh, G. Fastdraft: How to train your draft, 2024. URL https://arxiv.org/abs/2411.11055
2024 arXiv
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.