Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
Authors: Nadav Timor
Jonathan Mamou
Daniel Korat
Moshe Berchansky
Gaurav Jain
Oren Pereg
Moshe Wasserblat
David Harel
Venue: ICML 2025 oral (2025)
Keywords: Speculative Decoding
Large Language Models
Vocabulary Alignment
Heterogeneous Vocabularies
Efficient Inference
Inference Acceleration
Rejection Sampling
Tokenization
Transformer Architectures
Text Generation
Open Source.
Primary area: deep_learning->large_language_models

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.

Accelerating LLM Inference with Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
Nadav Timor! | Jonathan Mamou 2
Daniel Korat 2 Moshe Berchansky? Gaurav Jain Oren Pereg? 2
Moshe Wasserblat
David Harel 1
Abstract
often in practice, such drafters are not available-either because the target model is not part of a model family (ex- amples of families include the StarCoder, Li et al., 2023; Llama, Dubey et al., 2024 and DeepSeek, DeepSeck-A AI et al., 2025) or the smallest model in the same family re- mains too large and slow. An alternative approach training drafter from scratch (Zafrir et al., 2024)- a challenging task that requires computational resources, data, time, and expertise. Even if you successfully train such drafter, an- other problem is that you cannot reuse it for other models with different vocabularies.
Accelerating the inference of large language mod- els (LLMs) is critical challenge in generative AI. Speculative decoding (SD) methods offer substan- tial efficiency gains by generating multiple tokens using a single target forward pass. However, exist- ing 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 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 requir- ing additional training or modifications. Empiri- cally, on summarization, programming, and long- context tasks, our algorithms demonstrate signif- icant speedups of up to 2.8x over standard au- toregressive 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.
Our Contributions. We relax a key constraint of the spec- ulative decoding (SD) framework- the requirement that the drafter must use the same vocabulary as the target model. By allowing heterogeneous vocabularies, we eliminate the requirement to train drafter from scratch and enable any model to operate drafter, thereby significantly broaden the applicability of SD methods. By unlocking any off-the- shelf model to serve as drafter, we were able to find drafters that are more effective even than drafters from the same model family. Our main contributions are:
Algorithm (String-L.evel Exact Match, SLEM): An algorithm that uses plain text as a shared intermediate representation between the draft and target vocabularies, enabling exact matching of tokens. It solves the problem of non-injective tokenizers (Section 3.2) to support any off-the-shelf model pair. We evaluate the algorithm on summarization, programminn, and long-context tasks, demonstrating robust speedups of up to 2.8x over au- toregressive decoding.
Introduction
Speculative decoding (SD; Leviathan et al., 2023; Chen et al., 2023) is an effective method for reducing the latency of LLM inference and increasing its throughput. A neces- sary condition for SD be effective is that the drafter is sufficiently fast and accurate in approximating the target dis- tribution (Timor et al., 2025; Chen et al., 2024). State-of-the- art verification methods for SD employ rejection sampling algorithms that are designed to work with a single vocab- ulary, where the draft tokens are sampled from the same vocabulary as the target tokens (Leviathan et al., 2023; Chen et al., 2023; Miao al., 2024; Sun et al., 2024). However,
Algorithm 4 (Token-Level Intersection, TLI):
purely token-based approach that adjusts the drafter's 's distribution to sample only from the intersection be- tween the two vocabularies and employs the standard SD verification method. We prove theoretically that this approach outperforms a simple "union" strategy by inereasing the probability of accepting tokens (Theo- rem 4.1.. Empirically, Algorithm demonstrates signif- icant speedups of up to 1.7x over autoregressive decod- ing.
Weizmann Institute of Science Intee Labs 'd Matrix. Corre- spondence to: Nadav Timor <adaav timor @ weizmann.ac.il>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Algorithm 3 (String-Level Rejection Sampling, SLRS): A novel verification mechanism that imple-

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
ments rejection sampling the string level instead of the token level. We prove that it is lossless (Theorem 3.2) and guarantees higher expected acceptance rates than string-level exact matching, under the same target dis- tribution (Theorem 3.1). Our theoretical and empiri- cal analysis shows rapid growth in computational cost for vocabularies with longer tokens, thus making this method most suitable for drafters with shorter tokens (Section 3.4).
Algorithm 1 An iteration of speculative decoding for her- erogeneous vocabularies with simple "union" strategy 1: Input: Probability distributions p and q over vocabular- ies T and D, respectively. Drafting lookahead i E N. An input prompt c.
2: Output: A sequence of tokens from T, containing between and + tokens.
3: Procedure:
4: Define probability distributions p' and q' over the vo- cabulary T D as follows. p'(x) p(z) if a e T
We merged our open-source source implementation of Algorithm 2 and Algorithm- 4 into Hugging Face Transformers (Wolf et al., 2020), the most popular LLM library, with more than 378,000 repositories and 6,000 open-source packages that depend on it. Independently of our benchmarks, Hugging Face's core maintainers have thoroughly evaluated the effec- tiveness of SLEM and TLI (Algorithms! 2 and 4) and found our methods to be the most effective among all the specula- tive decoding algorithms they have previously supported- over various use cases and hardware setups. As result, they made SL.M and TLI the default for heterogeneous SD in Hugging Face Transformers.
and p' (1x))= = O otherwise. q = q(z) if x E D and
g(æ²) = 0 otherwise.
5: Run Algorithm 5 with p' i,
As long as p(t) S (t) for all t T, where p is the target and g is the drafter, this simple approach of Algorithm I is optimal in terms of maximizing the probability of accept- ing a draft token. However, this condition is not satisfied if 3 d E D such that (d) > O and d & T because we then have Σxer g(I) < 1. Although the simple approach of Algorithm I extend Algorithm preserves the target distribution because the verification method remains un- changed, it might not yield the maximum probability of accepting target token (see Theorem 4.1). Below, we present Algorithm 4, which improves Algorithm I by adjust- ing the distribution of the drafter such that the probability of sampling tokens that are not in the target vocabulary is zero. This adjustment is done by normalizing the distri- bution of the drafter such that the sum of the probabilities of the tokens that are in the target vocabulary is one. For example, if T {'a', "b') and D= = ('a', "b', 'c'} where 1
All our algorithms are lossless, namely, outputs preserve the target distribution, and we provide acceptance rate expectations (Table 3) and other bounds. Our experi- ceves-coverrng summarization, programming. and long- context tasks- demonstrate speedups versus autoregres- sive decoding. By open-sourcing these methods via Hug- ging Face Transformers, we have already enabled imme- diate, practical acceleration of LLMs under heterogeneous vocabularies a scenario that is increasingly common in real-world deployments.
q('a') = q(bb' = q(t'') of the drafter to be d'a'a) = ('b")) = ž and d'('c') = 0. This approach increases the probability of accepting a draft token while still preserving the target distribution, as The- orem 4.1 proves. However, the expected acceptance rate of both Algorithm 1 and Algorithm 4 might be suboptimal in some other cases. For example, consider the case where T = {'a'} and D = f'a', "aa',"aa) ability that the drafter samples the token 'aa'. Algorithm I and Algorithm 4 are suboptimal because they always reject the token 'aa'. In this example it is easy to see that both models can only generate concatenations of the token 'a', hence we should have accepted the token 'aa', unless it is the last token to generate. Below, we also present Algo- rithm 2, which solves this problem by allowing the drafter to sample tokens that are not in the target vocabulary. Algo- rithm preserves the target distribution because it replaces the standard verification method that guarantees that the out- put tokens distribute according to the target distribution with exact matching, which guarantees that the output tokens are exactly the target tokens.
3. we adjust the distribution
Motivating Examples
Existing SD methods are designed to work with single vocabulary, where the drafter samples from the same vocab- ulary as the target model. As an example, see Algorithm 5, which is the standard SD algorithm proposed by Leviathan et al. (2023); Chen et al. (2023).
'aa'} and there is a nonzero prob-
Algorithm 1 offers simple way extend these methods to operate in cases where the drafter's ss vocabulary differs from the target's 's by virtually extending the vocabularies such that both vocabularies are their union. For example, consider the case of disjoint vocabularies where the target vocabulary is T = } and the draft vocabulary D = {'b'). Although all the draft tokens 'b' are rejected, the target distribution is preserved because we use the standard verification method of SD, which is lossless as proved in Leviathan et al. (2023); Chen et al. (2023). Even if one vocabulary is a proper subset of the other, for example, T = {'a", "b'} and D = =*b), or if T = {'a'} and D = { ('a", 'b'.. the target distribution still preserved thanks to the guarantee of the standard verification method.
2

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
3 Speculative Decoding for Heterogeneous Vocabularies with String-Level Verification
Algorithm 2 (SLEM), an iteration of speculative decoding for heterogeneous vocabularies with verification
w string-level exact match
Notation. Vocabularies are finite sets of strings, also called tokens. We say that a string a is expressible in vocabulary B if there exist strings b1, b2,...,,,, b/2 E B such that a = by @ b2 ( ..... @ bn. where @ denotes string concatenation. We say that a vocabulary is expressible in a vocabulary B if all strings in A are expressible in B. and denote this relationship by A - B", where B" is the Kleene closure of B under string concatenation. Tokenizing string with respect to a vocabulary A is the process of partitioning into a sequence of tokens a1, ....... On. where a1 is the longest prefix of s that is a token in A, 02 is the longest prefix of that is in A after removing d1, and so on. The tokenization of s with respect to A a finite sequence of tokens, denoted by A(s). The i-th token of A(s) is denoted as A(s); A.
1: Input: Target model p and drafter model q over vo- cabularies I and D, respectively, where T - D and D' TT. Drafting lookahead value i E N. A prompt
TT.
2: Output: A non-empty sequence of accepted tokens from T.
Procedure:
4: Tokenize the prompt to the draft vocabulary, D(c)-
5: For j t- ,....,
6: Sample draft token from the drafter condi- tioned on the prompt and previous draft tokens, dj ~ (D(e)edd.....d (where de =c)).
7: Tokenize the concatenation of the draft tokens, (11, .a.,,,..,,,, (m) t (d4 @ d;).
With data parallelism (batching). compute via one target forward pass the m + 1 logits of the target model con- ditioned on the prompt and all the draft continuations,
3.1 String-Level Exact Match (SLEM)
Algorithm 2 one solution to the problem of heterogeneous vocabularies. It implements variant of SD with the ver- ification method of exact matching. The key mechanism involves translating tokens bidirectionally between the draft and target vocabularies. Tokens generated by the drafter are first decoded into text and subsequently re-tokenized using the target model's vocabulary. After the target model verifies the generated tokens, the sequence converted back into the drafter's 's tokenization format for the next iteration. This process ensures that the target model's distribution is preserved while allowing the drafter to operate within its own vocabulary constraints.
PT(c): PT(c)tt ".; PT(c)t @.........
9: Sample a token from each logit, 1 ~ Prie), 12
Pr(e)tt; #m+11 ~ Pr(e) @....r.....
10: Find the first index where the draft differs from the target, j == arg minn)(.......11 t'J #ty.
11: Accept 12, --,,,
corpus when the vocabulary size is greater than the alpha- bet cardinality, which is often the case (see Table 8 for examples). Typically, the corpus used for constructing a vocabulary comprises extensive texts, such as books or col- lections of documents. Unless the target and draft tokenizers are constructed using a narrow corpus, it is reasonable to assume T - D" and D - T because both vocabular- ies usually include all the characters of the alphabet, hence satisfying even stronger relations of the form T - D* and D ~ T
Vocabulary Constraints. Algorithm 2 assumes that the target vocabulary T' is expressible in the draft vocabulary D, i.e., + D* Additionally, it assumes D" T"* namely, every concatenation of draft tokens, dj @ .... @ d, for some i, must be expressible by concatenations of target tokens 1 (D. .tm E T for some m. i.e., T(d (idr@...ddd + 0 in line 7. If these conditions do not hold, converting strings from one vocabulary to another becomes undefined, leading to decreased acceptance rate and rendering the algorithm ineffective. In practice, assuming T - D and D* - T" is reasonable due the way vocabularies are typically con- structed. The process of constructing a vocabulary often begins by determining its size, i.e., the number of tokens it contains. Informally, vocahularies are designed to maximize the frequency of token appearances in a given corpus, avoid splitting frequently co-occurring tokens, or both. Known tokenization methods such as BPE (Sennrich et al., 2016), WordPiece (Schuster & Nakajima, 2012), Unigram (Kudo, 2018), and SentencePiece (Kudo& & Richardson, 2018) are heuristic and greedy approaches that generate vocabularies containing all the characters of the alphabet in the given
3.2 Noj-Iniect Tokenizers
A common issue with tokenizers is that they do not always implement an injective function, meaning that for any given string 8, it is possible for s * decode((ncood(())) can occur due to so-called "normalization steps" or "pre- tokenization rules" that discard certain details of the input text. In practice, common examples include tokenizers that treat multiple spaces as a single space, lowercase all char- acters, or replace accented characters with their standard counterparts, such '6' being replaced by 'e'. In standard autoregressive decoding or speculative decoding, where the target and draft vocabularies are the same, we tokenize the input prompt e into tokens only once at the beginning of the decoding process. Conditioned on the encoded prompt, we sample N tokens f1, f,, directly from the target
This
3

---

Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
(autoregressive decoding) or using rejection sampling pro- cedure with draft tokens (speculative decoding). Then, we return the string c c ( @ @ @ B.N. Since language mod-
in the last run, we need to decode the output of Algorithm 2 back into text before returning the final string. Because each tokenizer might apply different normalization rules, there can be a mismatch between what the target model sees and what the drafter model intended to produce. To handle these mismatches, we look for the longest stretch of matched tokens between the tokens we already accepted in the target tokenizer's is space, and the newly proposed tokens re-encoded in the target tokenizer's space. Conceptually, this search procedure is way of finding the largest overlap (or suffix/prefix match) between the old and new sequences. We then only take the suffix of the new tokens that falls beyond that overlap. This effectively aligns the newly added tokens to the correct place in the target-token space. The algorithm can "look behind" a small number of tokens to try to realign sequences. By doing so, we mitigate the effect of the mismatch and preserve as much of the previously decoded text as possible. We provided the implementation in the Supplementary Material.
els output token IDs, returning this string requires decoding each of the output tokens 4,, 12,..., by from its ID back into text, then, concatenating them with the prompt yields c0L, @l2 1.22..... ........... DIN. Pre-tokenization rules are only applied to the input prompt e once, before applying the model, and therefore they limit the ability of the model to distinguish between different input strings c j c' that are equivalent under pre-tokenization rules, namely, T(c)= = T(d) given non-injective tokenizer T'. This behavior is not necessarily problematic, and has been used in practice for a long time. is important to note that the pre-tokenization rules are not directly applied on the output tokens c, &1 f2...., fy that are concatenated form the final output string. That is, pre- tokenization rules do not alter the tokens t1, t2,................ ......... tty after these tokens are sampled. The final returned string starts with the given prompt e without any modifications and ends with a concatenation of the sampled tokens t @t Dt.2D...tt, Unlike decoding over homogeneous vocabularies where the target vocabulary T and the draft vocabulary D are the same-in decoding over heterogeneous vocabularies, we may have T # D, which limits the ability of the target and drafter models to communicate token IDs. Algorithm 2 employs plain text as an intermediate representation that is shared between the two different vocabularies. This means that the output tokens &,, .2..... fty are decoded back into text and then re-tokenized using the draft vocabulary in line 4. This process may apply pre-tokenization rules to the output tokens, which can lead discrepancy between the output tokens and the target tokens. To evaluate whether various tokenizers exhibit injectivity on a specific dataset, we conduct a simple experiment that heuristically tests the consistency of the decoding and encoding, as detailed in Appendix F. Our findings indicate that some commonly used tokenizers do not maintain injectivity even when tested heuristically specific dataset. When we developed and tested Algorithm 2. we found that the non-injective be- havior of tokenizers significantly impacted the algorithm's 's acceptance rate. To address this issue and broaden the appli- cability of Algorithm 2 to a wider range of tokenizers, we propose the following simple solution.
KV Caching, Storing the KV cache of models is a common practice that has been shown to be crucial for efficient infer- ence (Pope al., 2023; Kwon et al., 2023). In particular, without KV caching, the additional number of operations (e.g., floating-poine operations) required for the decoding might grow quadratically with respect to the number of tokens in the context for self-attention transformers. Algo- rithm implements only a single iteration of SD. SD over heterogeneous vocabularies that is based on Algorithm 2 therefore may include multiple runs of Algorithm 2. These runs are sequential and autoregressive, namely, the output of each run of Algorithm 2 is used as the input for the next run of Algorithm 2. Therefore, implementations of Algorithm 2 should store the KV cache from one run of Algorithm 2 to the next run. With KV caching, the prompt e needs to be encoded into the target and draft vocabularies only once, during the first run of Algorithm 2 (that is, the first itera- tion, also referred to as "pre-filling"), to facilitate line and line 4, respectively.
3.3 Verification via Rejection Sampling
The standard verification method of SD guarantees that the output tokens are distributed according to the target distri- bution, but it does not guarantee that the output tokens are exactly the target tokens, as in exact matching. For example, if the drafter is another instance of the target model p. the standard verification method of SD will accept all the draft tokens because, in general, the expected acceptance rate satisfies Eier min (p(t), q(t) for any drafter q and vocab- ulary T, according to Leviathan et al. (2023). Hence, the expected acceptance rate of drafter that is an instance of the target model is Eter p(t) = 1. For any drafter different from the target model, # p. the expected acceptance rate is strictly lower than one. Theorem 3.1 proves that, in gen-
Algorithm 2 Supports Non-Injective Tokenizers. Given prompt c E T", Algorithm 2 starts by tokenizing it into the draft vocabulary, D(c), in line 4. The prompt is also tokenized into the target vocabulary, T(c), to allow the target model to compute the logits in line 8. Line 7 tokenizes into the target vocabulary the concatenation of the draft tokens that are previously sampled from the drafter, namely, computes T'd2 @ .e.... @ d.). Since the output of Algorithm 2 is in the target vocabulary, following runs of Algorithm 2 can use the output as-is without decoding it back into text. Only
4

---

Lossless Speculltiv Decoding Algorithms for Heterogencous Vocabularies
eral, for any non-trivial target distribution p. the expected acceptance rate of exact matching is strictly less than the ex- pected acceptance rate of SD for homogeneous vocabularies under the same target distribution.
Lookahead. The lookahead controls tradeoff between the probability of accepting token and the number of drafter forwards, since every sampling of draft token requires computing a forward pass of the drafter. The lookahead indicator function Si determines whether the algorithm should stop sampling draft tokens. Naively, we can set Si (1) == [ > n] for some threshold n N, and stop sampling draft tokens after n draft tokens have been sam- pled in line 4 of Algorithm 3. On one hand, increasing the threshold necessarily increases the number of drafter forwards that Algorithm 3 requires. On the other hand, selecting a larger value of n may increase the probability that Algorithm 3 accepts a token because it may increase the number of feasible values of 4 line Small values of may lead to scenarios where some target tokens are never accepted. For example, if the target vocabulary T includes a token t with ten characters, and the longest token in the draft vocabulary D is four characters, selecting < 3 will never accept t. However, since increasing n also in- creases the number of drafter forward passes, it is important to select a value of n that optimizes our objective func- tion, which is, most commonly, maximizing the throughput of the inference or minimizing its latency. Target tokens t E T may correspond to more than one sequence of draft to- kens dj,..., d, E D for which the tokenized concatenation T(d2 @ .d.;) starts with f, namely, [(1 (BB...dd)) = t. These cases are common in practice, especially for a tar- get vocabulary T that is larger and includes longer tokens than the draft vocabulary D. For example, consider a draft vocabulary D = { ('hello_', 'world', 'wo", 'rld') and a tar- get vocabulary T = D U ('hello world'), ). The target token 'hello_ fiolo_wordd' is the first token in the tokenized concatenation of two different sequences of draft tokens: 'hello world' = T''hello_' @ 'world")1 = T T'thello_' @ 'wo' @ 'rld'), In fact, there are infinitely many sequences of draft tokens that start with 'hello. world'. Since Algorithm uses only the first target token T(d1 @ e d it is redundant to sample more than three draft tokens in this example. However, if the first two draft tokens are 'hello.' and 'world', there is no need to sample the third token since the first target token has already been determined. To capture this behavior and avoid unnecessary drafter forwards during inference time, we can calculate the maximum lookahead Vimax at preprocessing time, by calculating the maximum number of draft tokens that need to be sampled to determine the first target token (Neax = 3 in the example above). Defining the lookahead indicator function to be S, (i) = [ > mmmax] is a simple heuristic ensuring that the algorithm stops sampling draft tokens after the first target token has been determined. How- ever, this heuristic might still sample more draft tokens than necessary, as we saw in the example, where the first target token is determined after the two draft tokens, 'hello_' and 'world' have been sampled. To avoid computing unneces- sary drafter forward passes, we can define the lookahead
Theorem 3.1. Let p be a non-trivial larget probability dis- tribution over a vocabulary T, where there exist 11, 12 E 'T' such that p(t,) + p(t2). Let be the drafter probability distribution over the same vocabulary T. q = p. namely, the drafter is another instance of the target model, then the expected acceptance rate of the exact matching method OLEM is strictly less than the expected acceptance rate of the stan- dard speculative decoding method oisD- Namely, it holds that OrgM < OssD-
Proof. See Appendix G.
Since Algorithm 2 implements exact matching verification, its expected acceptance rate is relatively low compared to the standard verification method of SD, which implements a rejection sampling procedure. To increase the acceptance rate of Algorithm 2. we propose Algorithm 3, introducing novel verification method that employs lossless rejection sampling at the string level. Algorithm 3 samples draft tokens autoregressively from the drafter until a lookahead condition is satisfied, then tokenizes the concatenation of the draft tokens into the target vocabulary. It is lossless, as Theorem 3.2 proves, because it uses the same structure as the standard verification method of SD, which is lossless, as proved in Leviathan et al. (2023); Chen et al. (2023). The primary difference is that the probabilities are for generating a certain string rather than a single token.
Algorithm 3 (SLRS), string-level rejection sampling verifi- cation for speculative decoding with heterogeneous vocabu- laries
1: Input: Probability distributions and q over vocab- ularies T' and D, respectively, where T - D and D* - T* Lookahead indicator function S₁ from the current state to a boolean value.
2: Output: A token from T.
3: Procedure:
4: Sample d1, d,, d2 q until satisfies S,
5: Tokenize (2,,2,,... tm)) +- ((d @... 2 d;).
6: If p(t1)= 2 (ftt). accept f1.
7: With probability p(t1).
"(t)), accept
8: Reject tj. Sample i ~ I-Σn min pin(p(")
p(t) min((()))))) return 6,
Theorem 3.2. For any token in the target vocabulary& t T, Algorithum 3 outputs the token with probability p(t) we
define vt) de...d... (..(d,....dd)) (ell))e((.. (1.......)
Σ
II (ddz).
Namely, Algorithm 3 is lossless. Proof. See Appendix G.
5

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
indicator function S1 combine maximum threshold mmax and stopping condition of whether the first target token has been determined. Namely, S1 (i) is true if > n or Pr
tokens d1. ......,,a d, such that their concatenation d1 @ @d, starts with the target token i, namely, 7(d1 @... d:)1 = t. For general vocabularies, the number of such sequences dı.....d; grows rapidly with the length of t. For ex- ample, consider a complete vocabulary Dn that contains all possible strings of length n over a fixed alphabet Σ. A simple case is the alphabet
[(d @ @ d:)1 *
0, and false otherwise. Algorithm 3 and Theorem 3.2 both hold for this more general lookahead indicator function. In cases where the additional drafter forward passes are expensive or longer tokens are less likely to be accepted, setting the threshold n to a value that is strictly less than 7mmax can be beneficial. More sophisticated lookahead indicator func- tions control the lookahead based on additional information about the current state, as has seen in other recent works. For example, Mamou et al. (2024) trained a small neural network to estimate the likelihood of the next draft token being accepted and used this information to decide whether to sample the next draft token or stop drafting. Their experi- ments showed that even a simple controller that attends to the drafter's ' logits is highly effective, and the controller gen- eralizes well across different datasets and tasks. Following their success in both increasing the throughput and reducing the lateney of the inference, Hugging Face's s Transformers, the commonly used open-source library for training and de- ploying LLMs, has recently incorporated such a controller into their default inference pipeline. While implementing the lookahead indicator function S1 as such a controller seems promising, it might be computationally expensive to calculate (t) for longer lookahead values, as Section 3.4 shows.
T(d o... EB d; @ d B... dn)1
= {'a', 'b'), where D1 = {'a', 'b'). D2 = D1 U {'aa', 'ab', 'ba', 'bb'), D3 = D2 U ('ana', 'aab', 'aba", 'baa', 'abbb, 'bab", 'bba', 'bbb'). For such vocabulary D.. the number of terms in the sum of (t) from Theorem 3.2 for target token & of length m S is 2 as Lemma 3.1 proves. Here, the length of token t is defined to be the maximum number of tokens whose concatenation equals to In the example above, 'aaa" has length three because it is the concatenation of three 'a" tokens, while 'aa" of length two because it is the concate- nation of two 'a' tokens.
Lemma 3.1. For a target token of length m. S n. in complete vocabulary Dn that contains all possible strings of length up to over a fixed alphabet E. the number of distinct sequences of draft tokens di,...,d; ,d; such that their concatenation d1 @... @ d, starts with t, namely, (d2 @ + d:); = I, is 2 Proof. See Appendix G.
Appendix C provides details of an experiment con- ducted to examine the complexity of calculating (tt) given the vocabulary of real-world, off-the-shelf drafter (Qwen2-7B- Instruct from Yang et al., 2024). The re- sults indicate that the number of terms in the sum of (t) grows exponentially with the length of the target token f, as predicted by Lemma 3.1. Although Algorithm 3 is lossless (Theorem 3.2) and its acceptance rates are likely to be higher than those of Algorithm 2 (Theorem 3.1), calculating (t) during runtime might be too computationally expensive for practical use cases especially if the drafter's vocabulary includes long tokens, as shown in the proof of Lemma 3.1 and supported by the experiment in Appendix C. Beyond its theoretical guarantees, Algorithm 3 might be suitable in practice only for specific drafters with small vocabularies, where the number of terms in the sum of (t) is manageable. For example, modern models like the recent MambaByte (Wang et al., 2024) could potentially be suitable drafters for Algorithm 3. However, the applicability of Algorithm 3 to a wider range of drafters with larger vocabularies is an open question that requires further research, and we propose it as future work.
Block Verification is Non-Trivian In Algorithm 3, the vocabularies T' and D are related only by T - D* and D' - T rather than by stricter relationships like bijection or D After Algorithm 3 removes the prefix t1 from the concatenation di .... @ d, the remaining string is l2 + @ t'm and its tokenization back into the draft vocabulary D might differ from (d)>1,.... d,). For example, consider simple case where D g T, such that T {'a', 'b'} and D == ('a', "b', "aa") } Let d1 = "aa' and assume that i = 1, meaning that only one draft token is sampled in line 4. We then have T(d1)= = (t2, t2) = ('a',""), "a"). Therefore, the remainder of the drafted string 'aa" after removing é = 'a' is the token to = 'a', which was not sampled. Such scenarios can arise only when shifting from settings where D T to settings where D + T. Applying Algorithm 3 to the string that remains after removing the candidate token t is, therefore, more challenging. This issue makes it non- trivial to generalize the block verification mechanism of Sun et al. (2024) to the case of heterogeneous vocabularies, despite its proven advantage in homogeneous setups.
4 Speculative Decoding for Heterogeneous Vocabularies with Token-Level Verification
3.4 Efficient Calculation of (+(
This section introduces additional algorithms that extend the standard SD framework to operate over heterogeneous
Calculating (t) in line 6 of Algorithm 3 requires summing over all the probabilities of sampling sequences of draft
6

---

Lossless Speculatie Decoding Algorithms for Heterogencous Vocabularies
vocabularies, namely, where the drafter's vocabulary dif- fers from the target's. Unlike Section 3, the algorithms in this section do not use strings as intermediate, shared representation. Instead, they operate at the token level, as in standard SD algorithms (for example, see Algorithm 5). The primary idea is to project the drafter's probability distri- bution over its vocabulary onto the intersection between the vocabularies of the draft and the target models. In doing so, Algorithm 4 adjusts the drafter to sample only tokens that are in the intersection between the two vocabularies while keeping the target model unchanged.
vocabularies is often non-empty because of how tokenizers are constructed. The intuition is based on commonly used tokenization methods, as mentioned in Section 3.1. Our ex- periments with real-world off fff-the-shelf models support the assumption that the intersection between the vocabularies is non-empty. Tokens in the intersection have a non-zero probability of being sampled by both models and, therefore, the intersection supports a non-zero expected acceptance rate, as shown by Leviathan et al. (2023).
5 Empirical Results
Algorithm& 4 (Töken-Level Intersection, TL.),, an iteration of speculative decoding for heterogeneous vocabularies with token-level rejection sampling verification
Our empirical results have had an impact on the open-source ecosystem, with Algorithm and Algorithm 4 successfully integrated into Hugging Face Transformers (Wolf et al., 2020)-the most widely adopted library in the AI field, boasting over 145,000 GitHub stars, more than 378,000 repositories, and 6,000 open-source packages that depend on it. Thanks to their versatility and broad applicability, Algorithm 2 and Algorithm 4 had become the default infer- ence pipeline behavior (in October 2024 and February 2025, respectively), enabling efficient speculative decoding (SD) for heterogeneous vocabularies across diverse applications. The open-source community has quickly embraced our ap- proach to heterogeneous SD, unlocking any model to serve as a drafter, driving widespread adoption and enabling po- tential further enhancements by engineers and researchers. Its seamless integration into existing workflows has empow- ered practitioners to achieve substantial improvements in inference efficiency with minimal effort. This broad adop- tion underscores the practical utility and robustness of our approach in real-world scenarios. The rapid uptake of our algorithms demonstrates their effectiveness across a diverse range of model pairs, tasks, and hardware setups. The fol- lowing section presents only a selection of examples.
1: Input: Probability distributions p and over vocabular- ies T and D, respectively. Drafting lookahead E N.
2: Output: A sequence of tokens from T. containing between and i + tokens.
3: Procedure:
4: Define probability distribution q' over the vocabu- lary T D such that (xxx Ever 4(3)
g(w)
if x E T and
o' (a) = 0 otherwise.
5: Run Algorithm 5 with p. i,
Theorem 4.1 proves that the acceptance rate of Algorithm 4 is greater than or equal to the acceptance rate of the simple solution that Algorithm I implements.
Theorem 4.1. Let p and be target and drafter probabil- ity distributions over vocabularies T and D, respectively. Define p', H1,,100 92 to be probability distributions over T D as follows. (xx = p(x) if x E T and p'(x) = 0 other- wise. (I)) = q(x) if x E D and (x)) = 0 otherwise.
(2(x) E.er q( if x E T and q2(x)) = 0 otherwise.
q(x)
Given the target p', we define an and ar2 to be the probabil- ity of accepting a token x ~ qi and x ~ 42, respectively, by the rejection sampling algorithm of speculative decod- ing from Leviathan et al. (2023); Chen et al. (2023). Then, a1 S agg and the output tokens distribute according to p. Proof. See Appendix G.
We evaluate Algorithm 2 (SLEM) and Algorithm (TLI) over widely used models, tasks, and hardware setups, in- cluding DeepSeek (DeepSeek-Al et al., 2025), Phi (Abdin et al., 2024b;a), Mixtral (Jiang et al., 2024), Qwen2.5 (Qwen et al., 2025), Vicuna (Chiang et al., 2023), Llama (Dubey et al., 2024), CodeLlama (Rozière et al., 2024), Starcoder (Li et al., 2023), and Gemma2 (Team et al., 2024). Ta- ble benchmarks SI.EM and autoregressive decoding (AR) where both employ a temperature of zero. Table bench- marks TLI and AR where both employ a temperature of one. The results demonstrate throughput accelerations over AR of up to 2.8x with SLEM and 1.7x with TLI. Note that the target models in Tables 1 and 2 do not have homogeneous drafters that are available off-the-shelf and therefore we cannot accelerate them using standard SD. Tables 6 and 7 in Appendix D add results for additional models, including those with homogeneous drafters (e.g.. Gemma2). For exact implementation details, we refer the reader to Appendix D.
Although the acceptance rate of Algorithm 4 is at least as high as the acceptance rate of Algorithm 1 (Theorem 4. it still depends on the intersection between the two vocabular- ies. For example, if the intersection is empty, the acceptance rate of both algorithms is zero. This dependency on ac- ceptance rate is not new or unique. Instead, it is a known limitation of SD algorithms. Timor et al. (2025) analyzed the expected speedups of SD for any drafter size and ac- ceptance rate and studied the slowdowns that standard SD algorithms cause given sufficiently low acceptance rates. In practice, the intersection between the draft and target
7

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
Table 1: Benchmark comparing Algorithm 2 (SLEM) and autoregressive decoding (AR) for widely used models, tasks, and hardware setups. The results demonstrate that SLEM increases throughput by up to 2.8x over AR. Note that the target models below do not have homogeneous drafters that are available off-the- off-the-shelf. For some target models, their in-family drafters are heterogeneous, as their vocabularies differ. Examples include the target model phi-4 4 with the drafter Phi-3.
and the DeepSeek-R1-ee Dis-tittiii Qwen. model family.
(ms)
TPOT (ms)
Tokes
Specdup
Tegget
Dutasel
Handware
Method
Drafier
Mixtral 8x228 Instruce-
8c22--lsttuu--ol v0.1
con.dailymai
4 H100 NVL
AR
No Drafter ('Attrepresiiee)
266.8
127.9
7.8
1,0
SLEM
Qwen2 0..36 Instract
321.2
66.3
13.3
L.71
302.4
57.3
16.4
scrolls
HHHH NVL
AR
Deafter (Autenseressive)
13319
163.0
SLUM
Qwenz 0.50 Instract
R1R2
81.0
10.3
1.71
vacuna 680
1364,5
132.5
7.4
1.24
humaneval
4 HIOOONV
AR
No Draftrr (Auuoropressive)
217.5
1279
1,0
SLEM
4844
120
1:55
vicuna Akes
231.5
73.3
12.6
1.61
DeepSeck RT Distill Qwen 140
scrolls
I 6000
AR
No Drafter (Auloregressive))
1481.
87.5
10.9
1.0
SLEM
16684
160
1.48
6km
1366.
17.3
1.59
con daiymail
RIX 6000
AR
No Drafter (Autorogressine)
176.8
51.7
19.2
1.0
SLEM
DeepSeckk Xi---iiill---ees------
2875
69.3
14.1
0.75
68m
243.0
27.4
1,43
openal Inmanneal
TTRIX 0000
AR
No Destier (Antererresiee)
91.3
50.3
1938
SLEM
tiny stareader py
1154
43.8
22.4
1.14
CodeLlama 7b Instract-af
256.6
77.5
12.4
0.63
DeepSast-11-Diatll--ee
13.6
0.69
con.dailymail
AR
Diiteer (Autorogressiee)
2038
SLEM
DeepSeck XI RI-Distil Qwes 1.5
167.1
51.3
18.9
0.91
vicuna-58an
148.1
32.5
30,6
1.47
hamaneval
I HIOONNLL
AK
Drifter (Autoregrestee)
72.0
48.3
2007
Finy stanooder Py
80.
34.2
18.5
1.38
182.7
64.4
14.9
0.72
DeepSeck BeepSSekk-I-DDe KI-Distill-Weee/ 1.58
196.4
50.3
19.5
0.94
NV..
AR
No Txsaior (Antregrestbe))
12.
SLEM
DocpSack D1-5siil----1iiii----aaaa
988
57.6
17.1
vicuna-Akas
979.9
59.8
16.5
1.32
phi4
scralls
T NII
AR
No Taaller (Auleeeresshe))
4833
47
21.
1.00
SLEM
Qwen2.5 3-.ss-i
457.7
29.5
33.9
1.59
2hi-3.5-miii-iae inseruct
646.9
39.6
25.3
1.19
Codel Imma- M-Instmec-hf
AR
No Deafier (Ailrrogeesse)
70.7
46.8
214
1.01
SLEM
tiny stareader
109.7
16.7
59.7
2.79
Codee_lmo------nttree
45.8
2.14
Table 2: Benchmark comparing Algorithm 4 (TLI) and autoregressive decoding (AR) for widely used models, tasks, and hardware setups. The results demonstrate that TLI increases throughput by up to 1.7x over AR. Note that the target models below do not have homogeneous drafters that are available off-the-shelf. For some target models, their in-family drafters are heterogeneous, as their vocabularies differ. Examples include the target model phi-4 4 with the drafter and the DeepSeek-R1-Di st tiltlll1 11-Qwen model family.
Phi-3.
TTFT (ms)
TPOT (ms)
Tokls
Spectup
Target
Datase
Hardware
Method
Drafier
Biktral-c228-nsssaaswe
scrolls
4 H100 NVL
AR
No Drafter (Autovegresive))
1354.7
168.7
5.9
1.0
TLI
QwenZ 50,5 Instractt
1372.
97.8
9.9
1.69
1329.7
138.2
1.22
openal Jumaneval
AR
No Drsther (Autororesssie)
217.5
128.
10
Qwenz. 5 1.33 Instract
200.9
90.5
103
1,4
vicuna-68as
228.5
74.8
13,0
1,67
caildmlll
4 NIL
AR
No Drzfter (Autoregrestve)
266.8
128.1
T1.1
Quen2.5-11 50.55..50..11-mmtraaa
194.5
88.9
11.3
1,4%
vieuna-t8an
297.3
81.0
11.9
1,53
phi-4
scrolls
I HHIDNNVL
AR
No Deifter (Autoregressive)
4874
47.2
2122
1.0
368
1.45
Phi-3 S-mink-insteer
610.4
46.0
21.7
1.05
CodeLioma- Malllaaa------laaaa Instrrccc
Inmaneval
1 X6III
AX
No buatter (Allorogrestee)
HB.
45.3
22.
1.0
TT.
Fin sharooder
68.1
25.9
38.5
1.24
Codel 1oiell-amm-7h-nnttaat-e-
DeepSeok Ri-Diilll
scrolss
T 2000
AR
No Dralter (Autergressii)))
88.3
108
1.0
T1.
Deephack DDDiiill---pa----..
16R07
61.6
161
1.3
vicuna-68as
1502.2
57.2
17.1
1.59
| 6000
AR
Drafier (Allengnessie)
DoeppSook 11-isi/-----iiii--0ee
44.7
1.16
vicuna-t8as
202.4
40.6
24.1
1.51
openti homanoval
1 RTX 6000
AR
No Dealeer (Aulorgrosshee)
90.4
31.9
19.6
1.0
tiny stan_ssnnellerpp
25.4
CodeLluma- Ib-Instact--f
150.2
66.0
14.6
0.75
DoepSock RI ---Diilll-QwmmI... 1.50
172.6
45.6
21.2
1.08
8

---

Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
Tables 8, 9, and 10 in Appendix E examine the vocabular- ies of widely used off-the-shelf target and drafter models. Table 8 shows the vocabulary size of each model. Table 9 shows the size of the intersection between the draft and target vocabularies and the ratio of the intersection size to the target vocabulary size for various model pairs. We can see a wide range of overlap sizes and ratios, however, none of them are empty. This observation consistent with our aforementioned assumption that the intersection between the draft and target vocabularies is non-empty in practice. Table 10 extends Table 9 by showing the overlap sizes and ratios over various tasks.
Table 4: Informal constraints on the drafter for different algorithms to ensure effectiveness. If the constraints are not met, an alternative algorithm should be selected. Since the acceptance rate of Algorithm 4 is always greater than or equal that of Algorithm 1, selecting Algorithm 4 over Algorithm is always beneficial, assuming the implementa- tion overhead is negligible. A necessary condition for the effectiveness of Algorithms 2. 3, and 4 is that the drafter must approximate the target distribution sufficiently well. The effectiveness of Algorithm is further enhanced when the drafter's vocabulary consists of short tokens. The effec- tiveness of Algorithm 4 improves the number of tokens in the intersection between the vocabularies increases.
To facilitate additional standardized benchmarks, we have open-sourced our benchmarking repository, which pro- vides full reproducibility. The code is available at github. http://eybbaardttthf--beo pendix D for implementation details.
Algorithm
Drafter Constraints
Alg 1
Not Applicable (instead, select Alg 4)
See Ap-
Alg 2 (SLEM)
Accurate
Alg (SLRS)
Accurate, short tokens
6 Discussion
Alg 4 (TL.)
Accurate, large overlap of vocabs
To speed up the inference of a given target model, we need to select a drafter and a decoding algorithm. Table 3 summa- rizes the expected probability of accepting the next token for all the speculation algorithms when the drafter has a differ- ent vocabulary than the target. Note that the effectiveness of each algorithm depends on the properties of the drafter. Ta- ble 4 outlines the necessary constraints that the drafter must satisfy for each algorithm to be effective in practice. If these constraints are not met, selecting an alternative algorithm is recommended. Future work is discussed in Appendix A.
process of training dedicated drafter. Furthermore, our approach allows practitioners to integrate SD seamlessly into existing inference pipelines without requiring any mod- ifications to the target model's architecture or retraining pro- cedures. The proposed algorithms expand the applicability of SD to broader range of use cases, including models with different tokenization schemes. This is particularly relevant for practitioners and researchers who rely pre-trained models (e.g., from the Hugging Face Hub), each with dis- tinet vocabularies. Our methods provide practical solutions to unify heterogencous models under a single SD frame- work, enhancing efficiency across diverse applications.
Table 3: Expected acceptance rates given heterogeneous vocabularies for all speculation methods. The expected acceptance rate of Algorithm 1 is always less than or equal to the expected acceptance rate of Algorithm 4, as Theorem 4. proves.
Limitations. A fundamental limitation of SD algorithms is their dependence on the acceptance rate of the drafter and the latency of its forward pass, extensively analyzed in Timor et al. (2025). When the drafter approximates the tar- get distribution inaccurately, the acceptance rate decreases, leading to diminished performance improvements. Our pro- posed methods are no exception to this constraint. Unlike standard SD that limits the drafter in-family models, our algorithms open the door to using off-the-sheif target-drafter pairs that differ in their architecture and the way they were trained, although both can critically affect the acceptance rate. For drafters with a heterogeneous vocabulary, the inherit mismatches in token granularity might further re- duce the likelihood of draft tokens being accepted. Despite these challenges, our algorithms empirically demonstrate significant accelerations not only for heterogeneous drafters (Section 5) but also homogeneous ones (Appendix D) while employing drafters that are faster than the fastest in-family model. However, for cases with insufficiently fast or accu- rate drafters, our methods might fail, as Appendix shows.
Method
Expected Acceptance Rate
Alg 5 (SD)
Undefined
Alg
Eieroo min (p(t),
Alg (SLEM)
Ever (p(t) (t))
Alg 3 (SLRS)
Ever min (p(t), ({)}
Alg 4 (TL.)
Eiern min p(t)) Exeroo a(m)
e(0)
Practical Implications. Practitioners can leverage specu- lative decoding (SD) to significantly accelerate the infer- ence of off-the-shelf LLMs, even when no drafter with the same vocabulary the target model is available. This ad- vancement eliminates the need for extensive computational resources, as it bypasses the costly and time-consuming
9

---

Lossless Speculltive Decoding Algorithms for Heterogencous Vocabularies
Acknowledgments
Kauffmann, P., Lee, J. R., Lee, Y. T., Li, Y., Liu, W., Mendes, C. C. T., Nguyen, A., Price, E.,, de Rosa, G., Saarikivi, O., Salim, A., Shah, S., Wang. X., Ward, R., Wu, Y., Yu, D., Zhang. C., and Zhang, Y. Phi-4 techni- cal report, 2024b. URL.htpss: pettps://arxive /tt.iiaxxvvvor..e.. abs// 08905.
We are grateful to Roy Schwartz from The Hebrew Univer- sity of Jerusalem for his valuable feedback in improving this work. We thank João Gante and the Hugging Face team for reviewing the code and providing valuable feedback that contributed to its implementation in the Transformers library.
Chen, C., Borgeaud, S., Irving, G., Lespiau, J.-B., Sifrre, L., and Jumper, J. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013/4 2023.
This work was partially funded by the Israel Science Founda- tion (ISF grant 3698/21). Additional support was provided by a research grant to David Harel from Louis Lavigne and Nancy Rothman, the Carter Chapman Shreve Family Foundation, Dr. and Mrs. Donald Rivin, and the Estate of Smigel Trust.
Chen, J.. Tiwari, V., Sadhukham, R., Chen, Z., Shi, J., Yen, I. E.-H., and Chen, B. Magicdec: Breaking the latency- throughput tradeoff for long context generation with spec- ulative decoding. arXiv preprint arXiv:2408. 1049, 2024.
Impact Statement
Chen, M., Tworek, J., Jun, H., Yuan, Q., de Oliveira Pinto, H. P., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, L., Bavar- ian, M., Winter, C., Tillet, P., Such, F. P., Cummings, D., Plappert, M., Chantzis, F., Barnes, E., Herbert- Voss, A., Guss, W. H., Nichol, A., Paino, A., Tezak, N., Tang, J., Babuschkin, I., Balaji, S., Jain, S., Saun- ders, W., Hesse, C., Carr, A. N., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M., Brundage, M., Murati, M., Mayer, K., Welinder, P., Mc- Grew, B., Amodei, D., McCandlish, S., Sutskever, I., and Zaremba, W. Evaluating large language models trained code, 2021. URL https: / arxiv orgg /bs/ 2107. 03374. arXiv:2107.03374.
This work lowers the cost and latency of LLM inference- making the serving of these models cheaper, faster, and more accessible to wider range of users.
References
Abdin, M., Aneja, J., Awadalla, H., Awadallah, A., Awan,
A. A., Bach, N., Bahree, A., Bakhtiari, A., Bao, J., Behl, H., Benhaim, A., Bilenko. M., Bjorek. J., Bubeck, S., Cai, M., Cai, Q. Chaudhary, V. Chen, D., Chen, D., Chen, W., Chen, Y.-.., Chen, Y.-L.,, Cheng, H., Chopra, P., Dai, X., Dixon, M. Eldan, R., Fragoso, V., Gao, J., Gao, M., Gao, M., Garg. A., Giorno, A. D.. Goswami, A., Gunasekar, S., Haider, E., Hao, J., Hewett, R. J.. Hu, W., Huynh, J., Iter, D.. Jacobs. S. A., Javaheripi. M., Jin, X., Karampatziakis, N., Kauffmaan, P., Khademi, M., Kim, D.,, Kim, Y. J., Kurilenko, L., Lee, J. R., Lee, Y. T., Li, Y., Li, Y., Liang, C., Liden, L., Lin, X., Lin, Z., Liu, C.,, Liu, L., Liu, M., Liu, W., Liu, X., Luo, C., Madan, P., Mahmoudzadeh, A., Majercak, D., Mazzola, M., Mendes, C. C. T., Mitra, A. Modi, H., Nguyen, A., Norick, B., Patra, B., Perez- Becker, D., Portet, T., Pryzant, R., Qin, H., Radmilac, M., Ren, L.., de Rosa, G., Rosset, C., Roy, S., Ruwase, O., Saarikivi, O., Saied, A., Salim, A., Santacroce, M., Shah, S., Shang, N., Sharma, H., Shen, Y., Shukla, S., Song, X., Tanaka, M., Tupini, A., Vaddamanu, P., Wang, C., Wang, G., Wang, L... Wang, S., Wang, X., Wang, Y., Ward, R., Wen, W., Witte, P., Wu, H., Wu, X., Wyatt, M., Xiao, B., Xu, C., Xu, J., Xu, W., Xue, J., Yadav, S., Yang, F., Yang, J.. Yang, Y., Yang. Z., Yu, D., Yuan, L., Zhang, C., Zhang, C., Zhang, J., Zhang, L. L., Zhang, Y., Zhang, Y., Zhang, Y., and Zhou, X. Phi-3 technical report: A highly capable language model locally on your phone, 2024a. URL /ttttssss//aattt
Chiang, W.-L., Li, Z., Lin, Z., Sheng, Y., Wu, Z., Zhang, H., Zheng. L., Zhuang. S., Zhuang, Y., Gonzalez, J. E., Stoica, I., and Xing, E. P. Vicuna: An open- source chatbot impressing GPT-4 with 90%* ChatGPT quality, 2023. URL https: / mmm.yy..rr/blog.. 2023-03-330 300---3---vvuaaa
DeepSeek-AL, 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., Li, G., Zhang, H., Bao, H., Xu, H., Wang, H. Ding. H., Xin, H., Gao. H., Qu. H., Li, H. Guo, J., Li, J., Wang, J., Chen, J., Yuan, J., Qiu. J.. Li, J., Cai, J. L., Ni, J.. Liang, J., Chen, J., Dong, K., Hu, K., Gao, K., Guan, K., Huang, K. Yu, K., Wang, L., Zhang, L., Zhao, L., Wang, L., Zhang, L., Xu, L., Xia, L., Zhang, M., Zhang, M., Tang, M., Li, M., Wang, M., Li, M., Tian, N., Huang, P., Zhang, P., Wang, Q., Chen, Q., Du, Q. Ge, R., Zhang, R., Pan, R., Wang, R., Chen,
org/ abs 14219.
Abdin, M., Aneja, J., Behl, H., Bubeck, S., Eldan, R., Gu- nasekar, S. Harrison, M., Hewett, R. J., Javaheripi, M.,
10

---

Lossless Speculatie Decoding Algorithms for Heterogencous Vocabularies
R. J., Jin, R. L., Chen, R., Lu, S., Zhou, S., Chen, S., Ye, S., Wang, S., Yu, S., Zhou, S., Pan, S., Li, S. S., Zhou, S., Wu, S., Ye, S., Yun, T., Pei, T., Sun, T., Wang. T., Zeng, W., Zhao, W., Liu, W., Liang, W., Gao, W. Yu, W., Zhang. W., Xiao, W. I.,, An, W., Liu, X., Wang, X., Chen, X., Nie, X., Cheng, X., Liu, X., Xie, X., Liu, X., Yang, X., Li, X., Su, X., Lin, X., Li, X. Q. Jin, X., Shen, X., Chen, X., Sun, X., Wang. X., Song, X., Zhou, X., Wang. X. Shan, X., Li, Y. K., Wang, Y. Q. Wei, Y. X., Zhang, Y. Xu, Y., Li, Y. Zhao, Y., Sun, Y. Wang, Y., Yu, Y., Zhang. Y., Shi, Y., Xiong, Y., He, Y., Piao, Y., Wang. Y., Tan, Y., Ma. Y., Liu, Y., Guo, Y., Ou, Y., Wang, Y., Gong,
Belgium, November 2018. Association for Computa- tional Linguistics. doi: 10. 10.18653/11/1182200 URL
. org//o8-g--eeooooo -2012.
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 Sym- posium on Operating Systems Principles, pp. 611-626, 2023.
Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In Inter- national Conference Machine Learning, pp. 19274 19286. PMLR, 2023.
Y. Zou, Y., He, Y., Xiong, Y. Luo, Y., You, Y., Liu, Y.
Zhou, Y., Zhu, Y. X., Xu, Y., Huang, Y., Li, Y., Zheng, Y. Zhu, Y., Ma. Y., Tang, Y., Zha, Y., Yan, Y., Ren, Z. Z., Ren, Z., Sha, Z., Fu, Z., Xu, Z., Xie, Z., Zhang, Z., Hao, Z., Ma, Z., Yan, Z., Wu, Z., Gu, Z., Zhu, Z.,, Liu, Z., Li, 7., Xie, 7., Song, 7., Pan, 7.,, Huang, Z.,, Xu, Z.., Zhang, Z. and Zhang, Z. Deepseck-rl: Incentivizing reasoning capability in iims via reinforcement learning, 2025. URL https: / arxiv. org/ abc///bs//// 2501 12948.
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., Oblokulov, M., Wang, Z., Murthy, R., Stillerman, T., Patel, S. S., Abulkhanov, D.., Zocca, M., Dey, M., Zhang, Z., Bhat- tacharyya, U., Yu, W., Luccioni, S., Villegas, P., Zh- danov, F,, Lee, T., Timor, N., Ding, J., Schlesinger, C. S., Schoelkopf, H., Ebert, J., Dao, T., Mishra, M., Gu, A., Anderson, C. J., Gavitt, B., Contractor, D., Reddy, S., Fried, D., Bahdanau, D., Jernite, Y., Ferrandis, C. M., Hughes, S., Wolf, T., Guha, A., Werra, L. V., and de Vries, H. Starcoder: may the source be with you! Transac- tions on Machine Learning Research, 2023. ISSN 2835- 8856. URL https: /ttp//peeeeeeeeeeeeeeeeeeeeeeeee nnt. forum? dd=KoFOg41hal Reproducibility Certification.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A. et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.21783 2024.
Jiang, A. Q. Sablayrolles, A., Roux, A., Mensch, A., Savary, B., Bamford, C., Chaplot, D. S., de las Casas, D., Hanna, E. B., Bressand, F., Lengyel, G., Bour, G., Lample, G., Lavaud, L. R., Saulnier, L., Lachaux, M.-A., Stock, P., Subramanian, S., Yang, S., Antoniak, S., Scao, T. I.., Gervet, T., Lavril, T., Wang, T., Lacroix, T., and Sayed, W. E. Mixtral of experts, 2024. URL https: / /arxiv.. org/ brg/abs/// /2t./241...0000 04088.
Mamou, J., Pereg, O., Korat, D., Berchansky, M., Timor, N., Wasserblat, M., and Schwartz, R. Dy- namic speculation lookahcad accelcrates speculative decoding of large language models. In Proceedings of The 4th NeurIPS Efficient Natural Language and Speech Processing Workshop, volume 262 of Proceed- ings of Machine Learning Research, pp. 456-467. PMLR, 2024. URL htth::::: httpp/peeeeegg..e//ee/pe/e mlr press/ v2 v262 /tt//mmmm22444.mmmmmmmmmm 4a. html.
Joao Gante. Assisted generation: a new direc- low-latency text generation, 2023. cot.loccccccoooo////oo/o
tion toward
URL
assisted-generatten.
Kudo, T. Subword regularization: Improving neural network translation models with multiple subword candidates. In Gurevych, and Miyao, Y. (eds.), Proceedings of the 56th Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers). pp. 66-75, Melbourne, Australia, July 2018. Association for Compu- tational Linguistics. doi: 10. 18651//1//1818-0000 URL https: awtaaaannnnngooooae wtg/p10-111/00000
Miao, X., Oliaro, G., Zhang, Z., Cheng, X., Wang, Z. Zhang, Z., Wong, R. Y. Y., Zhu, A., Yang, L., Shi, X., Shi, C., Chen, Z.,, Arfeen, D., Abhyankar, R., and Jia, Z. Specinfer: Accelerating large language model serving with tree-based speculative inference and verifi- cation. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3. ACM, 2024. doi: 10.1 10.1145/3620666.3651333 //dx. doi wrt.orgg////// 1ttp:/00.111/33300
Kudo, T. and Richardson, J. SentencePiece: A sim- ple and language independent subword tokenizer and detokenizer for neural text processing. In Blanco, E. and Lu, W. (eds.), Proceedings of the 2018 Confer- ence on Empirical Methods in Natural Language Pro- cessing: System Demonstrations, pp. 66-71, Brussels,
URL http:
3651335.
Nallapati, R., Zhou, B., dos Santos, C., Gulçehre, Ç., and Xi- ang, B. Abstractive text summarization using sequence-to-

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
sequence RNNs and beyond. In Riezler, S. and Goldberg, Y. (eds.), Proceedings of the 20th SIGNLL Conference on Computational Natural Language Learning, pp. 280-290, Berlin, Germany, August 201 6a. Association for Compu- tational Linguistics. doi: 10.18653/w1/K16441 1028. URL. https: / /tt/aaaaaaaahcccae
long language sequences. In Goldberg, Y., Kozareva, Z., and Zhang, Y. (eds.), Proceedings of the 2022 Confer- ence on Empirical Methods in Natural Language Pro- cessing, pp. 12007-12021, Abu Dhabi, United Arab Emirates, December 2022. Association for Computa- main. tional Linguistics. doi: wwtptthhw.ogoooog//22e2oo org/ 2022. 823. URL https: http///aaaaaahhlcccooo mtt.mmmai...2....
wwg/oo6 1028.
Nallapati, R.. Zhou, B., dos Santos, C., Gulgehre, Ç., and Xiang, B. Abstractive text summarization using sequence- to-sequence RNNs and beyond. In Riezler. S. and Gold- berg, Y. (eds.), Proceedings of the 20th SIGNIJ. Confer- ence on Computational Natural Language Learning, pp. 280-290, Berlin, Germany, 2016b. Association for Com- putational Linguistics. doi: 10.18653/v1/K166 1028. URL ht https: / http://alaanthhhohcc org/ 6-002////
Sun, Z., Ro, J. H.. Beirami, A., and Suresh, A. T. Optimal block-level draft verification for accelerating speculative decoding. arXiv preprint arXiv:2403.1044 2024.
Team, G., Riviere, M., Pathak, S., Sessa, P. G., Hardin, C., Bhupatiraju, S., Hussenot, L., Mesnard, T., Shahriari, B., Ramé, A., Ferret, J., Liu, P., Tafti, P., Friesen, A., Casbon, M., Ramos, S., Kumar, R., Lan, C. L.,, Jerome, S., Tsit- sulin, A., Vieillard, N., Stanczyk, P., Girgin. S., Momchev, N., Hoffmann M., Thakoor, S., Grill, J.-B., Neyshabur, B., Bachem, O., Walton A., Severyn, A., Parrish, A., Ahmad, A., Hutchison, A., Abdagic A., Carl, A., Shen, A., Brock, A., Coenen, A., Laforge, A., Paterson, A., Bastian, B., Piot, B., Wu, B., Royal, B., Chen, C., Kumar, C., Perry, C., Welty, C., Choquette- -hho, C. A., Sinopalnikov, D., Weinberger, D., Vijaykumar, D., Rogozińska, D., Her- bison, D., Bandy, E., Wang, E., Noland, E.,, Moreira, E., Senter, E., Eltyshev, E., Visin, F., Rasskin, G., Wei, G., Cameron, G., Martins, G., Hashemi, H., Klimezak- Plucińska, H., Batra, H., Dhand, H., Nardini, I., Mein, J., Zhou, J., Svensson, J., Stanway, J., Chan, J., Zhou, J. P., Carrasquerra, J., Iljazi, J., Becker, J., Fernandez, J.. van Amersfoort, J., Gordon, J., Lipschultz, J., Newlan, J., yeong Ji, J., Mohamed, K., Badola, K., Black, K., Milli- can, K., McDonell, K., Nguyen, K., Sodhia, K., Greene, K., Sjoesund, I. I.., Usui, I.,, Sifre, I.., Heuermann, L., Lago, L., McNealus, L., Soares, L. B., Kilpatrick, L., Dixon, L., Martins, L., Reid, M., Singh, M., Iverson, M., Görner, M., Velloso, M., Wirth, M., Davidow, M., Miller, M., Rahtz, M., Watson, M., Risdal, M., Kazemi, M., Moynihan, M., Zhang, M., Kahng, M., Park, M., Rahman, M., Khatwani, M., Dao, N., Bardoliwalla, N., Devanathan, N., Dumai, N., Chauhan, N., Wahltinez, O., Botarda, P., Barnes, P., Barham, P., Michel, P., Jin, P., Georgiev, P., Culliton, P., Kuppala, P., Comanescu, R., Merhej, R., Jana, R., Rokni, R. A., Agarwal, R., Mullins, R., Saadat, S., Carthy, S. M., Cogan, S., Per- rin, S., Arnold, S. M. R., Krause, S., Dai, S., Garg, S., Sheth, S., Ronstrom, S., Chan, S.. Jordan, T., Yu, T., Eccles, T., Hennigan, T., Koeisky, T., Doshi, T., Jain, V. Yadav, V., Meshram, V., Dharmadhikari, V., Barkley, W., Wei, W., Ye, W., Han, W., Kwon, W., Xu, X., Shen, Z., Gong, Z., Wei, Z., Cotruta, V., Kirk, P., Rao, A., Giang, M., Peran, L., Warkentin, T., Collins, E., Bar- ral, J., Ghahramani, Z., Hadsell, R., Sculley, D., Banks, J., Dragan, A., Petrov, S., Vinyals, O., Dean, J., Has-
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:606-624 624, 2023.
Qwen, :, Yang, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Li, C., Liu, D., Huang, F., Wei, H., Lin, H., Yang. J., Tu, J., Zhang, J., Yang, J., Yang, J., Zhou, J., Lin, J.. Dang, K., Lu, K., Bao, K. Yang, K., Yu, L., Li, M., Xue, M., Zhang, P., Zhu, Q. Men, R., Lin, R., Li, T., Tang, T. Xia, T. Ren, X., Ren, X., Fan, Y., Su, Y., Zhang, Y., Wan, Y., Liu, Y., Cui, Z., Zhang, Z., and Qiu, Z. Qwen2.5 technical report, 2025. URL https: //arxiv. org/ abs / 2212 15115.
Rozière, B., Gehring, J., Gloeckle, F., Sootla, S., Gat, I., Tan, X. E., Adi, Y., Liu, J.. Sauvestre, R., Remez, T., Rapin, J., Kozhevnikov, A., Evtimov, I., Bitton, J., Bhatt, M.. Ferrer, C. C., Grattafiori, A., Xiong, W., Défossez, A., Copet, J., Azhar, F., Touvron, H., Martin, L.., Usunier, N., Scialom, T., and Synnaeve, G. Code Ilama: Open foundation models for code, 2024. URL https:// a arxiv. orgg abs 22008 12950.
Schuster, M. and Nakajima, K. Japanese and korean voice search. In 2012 IEEE International Conference on Acous- tics, Speech and Signal Processing (ICASSP), pp. 5149- 5152, 2012. doi: LLLL09ICAASSP2222266200000
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, Germany, August 2016. Association for Compu- tational Linguistics. doi: 10. N0.18853/V1/P11-1116 URL https: http:///caantthhooooooo htwp:/thhoooooooooo11--1111111 wwtp://-1///////.//////
Shaham, U., Segal, E., Ivgi, M., Efrat, A., Yoran, O., Ha- viv, A., Gupta, A., Xiong, W., Geva, M., Berant, J., and Levy, O. SCROLLS: Standardized CompaRison over
12

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
sabis, D., Kavukcuoglu, K., Farabet, C., Buchatskaya, E., Borgeaud, S., Fiedel, N., Joulin, A., Kenealy, K., Dadashi, R., and Andreev, A. Gemma 2: Improving open language models at a practical size, 2024. URL https:/ / www.iv.vvvv. org/ abs 22..2440..000 08.18.
Timor, N., Mamou, J., Korat, D., Berchansky, M., Pereg, O., Wasserblat, M., Galanti, T., Gordon, M., and Harel, D. Distributed speculative inference (dsi): Speculation paral- lelism for provably faster lossless language model infer- ence. In International Conference on Learning Represen- tations, 2025. URL https: httpss:://pppeeee..e//mmmmm net/ Forum??:==cJd11g229CC
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 httphtt////// https://open.reviee www.:nee//ouuur id=X1 XNsuksbb.
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., Jer- nite, Y., Plu, J., Xu, C., Scao, T. L., Gugger, S., Drame, M.. Lhoest, Q., and Rush, A. M. Transformers: State- of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natu- ral Language Processing: System Demonstrations, pp. 38-45, Online, October 2020. Association for Compu- tational Linguistics. URL https: / /www aclweb. org/ at//aaathhlgyy/// /2020. mmnlp-demos...
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 1rXiv:2412.15/155 2024.
Zafrir, O., Margulis, I., Shteyman, D., and Boudoukh, G. Fastdraft: How to train your draft, 2024. URL https: //ar/aa /arxivv. org/ abs/ /2111.111.. 11055.
13

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
A
Future Work
Future work includes assessing the effectiveness and applicability of Algorithm real-world scenarios, particularly with drafters of small vocabularies such as Wang al., 2024, and exploring drafter adjustment strategies for Algorithm 4 to increase acceptance rates.
B Standard Speculative Decoding
Generating the next token via autoregressive decoding requires computing a target forward pass. Standard SD methods, like Algorithm 5, tend to utilize this target forward pass to verify multiple candidate tokens at once via a data parallelism technique known as batching, which supported by modern hardware such as GPUs and TPUs. Running Algorithm 5 to generate the next target token requires only one target forward pass (line of Algorithm 5) although the algorithm could generate between one and i+ new tokens. Since computing the target forward pass is often the slowest and most expensive operation in the inference pipeline, the ability of SD methods like Algorithm 5 to reduce the number of required target forward passes is the key to their efficiency, as was previously shown in Leviathan et al. (2023); Chen et al. (2023); Timor et al. (2025).
Algorithm samples draft tokens from the drafter and then decides whether to accept or reject each draft token based on the target model's logits. The algorithm is widely used in practice and has been shown be effective in accelerating the inference of large language models. The algorithm lossless, meaning that outputs tokens that distribute as the output tokens of standard autoregressive decoding.
Algorithm 5 Standard Speculative Decoding (Adapted from Leviathan et al., 2023; Chen al., 2023)
1: Input: Probability distributions and q over a vocabulary T. Drafting lookahead i N. An input prompt c.
2: Output: A sequence of tokens from T', containing between 1 and i + tokens.
3: Procedure:
4: For j + i:
5: Sample draft token from the drafter conditioned on the prompt and previous drafts, dj ~ qeBd, @...dd- (where
dg : c).
6: With data parallelism (batching). compute via one target forward pass the + logits of the target model conditioned the prompt and all the draft continuations, Per Pompdy ".", Potadd (dd--
7: For + i,
8:
+ 2 ..... @ d (where do := c).
9: If (d)) S (d,). with probability (d,))
p=(d,) reject d, and go to line 11 (namely, break this for-loop).
10: Accept the draft token dj.
11: L E 10.,,..., be the number of accepted drafts. Set r + c + d1 ..... dd.
12: Sample & Fn for (t)) = (=(t)-minf (p. (+)))=()) if line ever rejected token. Otherwise, sample t Pa-
I-Lver (in(p. (f))
13: Return dd,....dj... dj
C Empirical Analysis of (t) Computation in Algorithm 3: Challenges and Insights
This section presents our empirical analysis of the computational complexity involved in calculating (t( using a real-world vocabulary. Specifically, we examine the Qwen2 - 7B Instruct model's vocabulary to evaluate how the number of terms in (f) scales with the length of the target token t. Our findings support the theoretical prediction in Lemma 3.1, which states that the number of terms grows exponentially with the token length. We select 150,000 of the shortest tokens from a total of 151,646 tokens the Qwen2- - 7B- Instruct vocabulary to keep the computation tractable. We then count how many ways a target token can be reconstructed by concatenating these shorter tokens. For instance, in the case of 'hello', we found 14 valid combinations out of the 16 that would appear in a complete vocabulary (as defined in Section 3.4), indicating that the vocabulary of this model may be nearly complete for five-character tokens. Figure 1 lists all 14 valid combinations for the string 'hello' and visualizes them in a tree structure, where each leaf node represents valid combination. In general, the number of forward passes of the drafter model that are required to calculate (b() is equal to the number of non-leaf nodes in the tree plus one. In this example, calculating ( (hello') requires 16 forward passes of the drafter model, which makes Algorithm with this vocabulary impractical for many target models that are considered
14

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
state-of-the-art, including the open access models StarCoder (Li et al., 2023), Llama (Dubey et al., 2024), and DeepSeek (DeepSeek-Al et al., 2025). In similar way to the above example for the token 'hello', decompose each of the 150,000 selected tokens into the set of all its corresponding combinations. Table 5 summarizes the statistical properties of the token
1. HH' 'e,, T, T, 'o']
1
2. [H",.' 1oo]
v
8. "e,
10 V
4. "'',''"',
11 0 /
"HH''''l', 'lo']
6.
el
7. "el'o""l"')
0
8. so]
10 V
9. "H,",'"',""""
10. "He'"'"I',''
ell /
11. ",,
ello
12. [Hel', 1oo]]
13. [Helll, 'o']
He
14. [Hello"]
o
10 V
11 V
Hel
V
10 V
Hell /
Hello V
Figure I: Left: All the 14 valid combinations of tokens from the Qwen2-77 IB-Instruct vocabulary that can be concate- nated to form the string 'hello'. Right: Tree visualization all these combinations. Each the 14 checkmarks indicate valid combination, which a leaf in the visualized tree. this example, calculating (t() from Algorithm 3 requires 16 forward passes of the drafter model, which is the number of non-leaf nodes the tree plus one. This large number of forward passes is due the exponential growth in the number of valid combinations the token length increases, shown in Figure 2.
lengths and the number of combinations for the selected tokens. The mean token length is 6.21 characters, with a standard deviation of 2.87. The mean number of combinations is 144.31, with a standard deviation of 880.98. The maximum number of combinations is 65,536. The median number of combinations is 15, and the 75th percentile 56. Figure 2 shows the number of combinations for different token lengths. The number of combinations grows exponentially with the token length, expected. Figure shows the histogram and kernel density estimate of the number of combinations for the 150,000 selected tokens. The distribution is right-skewed, with long tail of tokens having a large number of combinations. This exponential blow-up renders the calculation of (t) computationally infeasible for longer tokens, especially those among the 1,646 longest in the vocabulary. In practice, we could not even count all combinations for those tokens even after hours of computing time on a server, although only counting the combinations an easier task than listing them. These results align with our theoretical expectations. While shorter tokens have a manageable number of decompositions, longer tokens exhibit
15

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
Table 5: Statistical summary of token length and number of combinations for a set of 150,000 shortest tokens (out of a total of 151,646 tokens) in the
vocabulary.
Token Length (Number Characters)
Number of Combinations
Mean
6.21
144,31
Standard Deviation
2.87
Minimum
1.00
1.00
25% Percentile
4.00
7.00
50% (Median)
6.00
15.00
75%
Percentile
8:00
56.00
17.00
a combinatorial explosion, underscoring the importance of using drafter models with smaller, more concise vocabularies to reduce computational overhead. Although Algorithm guarantees lossless speculative decoding, the latency incurred by the computation of rb(t) may be prohibitive when the vocabulary includes very long tokens. Consequently, its applicability might be limited to models with compact or pruned vocabularies such MambaByte (Wang et al., 2024)-thar can balance accuracy with computational feasibility. Further research should explore heuristic or approximate methods to calculate (t) without exhaustive enumeration. Additionally, continued work on vocabulary construction and pruning techniques that reduce redundant token entries could help mitigate these computational challenges.
D Speedups
We evaluate methods various combinations of models, tasks, and hardware setups. Tables 6 and 7 provide full benchmarks for SLEM (Algorithm 2) where the temperature is zero, and TLI (Algorithm 4) where the temperature is one, respectively. The benchmark includes widely used models: DeepSeek (DeepSeek-Al et al., 2025), Phi (Abdin et al., 2024b;a), Gemma2 (Team et al., 2024), Mixtral (Jiang et al., 2024), Qwen2.5 (Qwen et al., 2025), Vicuna (Chiang et al., 2023), Llama (Dubey et al., 2024), CodeLlama (Rozière et al., 2024), and Starcoder (Li et al., 2023). Note that for some targets, all the drafters are heterogeneous despite both target and drafter belonging to the same model family. For example, for the target phi 4, the drafter Phi-3 5-mini -irrii--nsten instruct heterogeneous. This is also the case for the DeepSeek-R1-Dis st. witiilll-wweee 11-Qwen model family, where some in-family models are heterogeneous, and therefore we cannot accelerate them using standard speculative decoding. The datasets span three tasks: code generation using HumanEval (Chen et al., 2021), text summarization using CNN-DailyMail (Nallapati et al., 2016a), and long-context task using SCROLLS (Shaham et al., 2022). For each dataset, the results are averaged over 30 prompts such that we generate between 128 and 512 new tokens for each prompt. AR denotes autoregressive decoding, SD denotes the official implementation Hugging Face Transformers of standard speculative decoding like Algorithm (Joao Gante, 2023).
16

---

Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
60000
50000
Number of Combinations
40000
30000
20000
10000
0
2
4
10
12
14
16
Token Length (Number Characters)
Figure 2: The number of combinations different token lengths the 150,000 selected tokens from 77- vocabulary. We can see that the number of combinations grows exponentially with the to- ken length.
17

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
0.040
Histogram
KDE (PDF estimate)
0.035
Median 15 combinations
0.030
Mean = 144.84 combinations
0.025
Density
0.020
0.015
0.010
0.005
0.000
150
200
250
Number of Combinations
Figure 3: Histogram and Kernel Density Estimate of number of combinations for the 150,000 selected tokens from the "wen2-7B-Instruus vocabulary. We can see that the number of combinations right-skewed, with a long tail of tokens with large number of combinations. For exact values, Table 5.
Table 6: Full benchmark for SLEM (Algorithm 2).
TIFT (ms)
TPOI (ms)
Toke'
Speedop
Target
Dataset
Hardware
Method
Drafte
Mixtral 8x-2aal--22--nnneee Io.
ena Jailymail
H100
AR
No Drafter (Autaregrzssive)
266.8
125.9
7.8
SLEM
QwenZ 35.. In-Innus
M112
65.3
13.3
1.71
300.4
seroll
H10ONVL
Drafier (Amtorogrsssie))
6.0
SLEM
Qwend 3-0.5 In-encc
14422
81.0
10.3
1.71
vidunn-68m
1344.5
132.5
7.4
1.34
openal Janannvall
4" HIOONVL
(Autarog
217.5
78
SLEM
Quen? 3-0 3-0.BB-nnemu
454
A01
12:0
vicunn-68m
231.5
73.1
12.6
1.61
Deepbcet-R RI-Distll-/eeennn
scroll
1 RIX MBRI
AR
No Draiier (Autnregresoie))
87.3
1039
SLEM
DoepScok-Ri RR-Distil-quen.
1.48
vicuno-E8m
56.0
17.3
en dinlymail
AR
No Draligr (Aulonggresinee)
1768
517
19.2
SLEM
DeepSeok-RT -i----ll--eeee-
2373
600
14.1
0.73
243.0
openal humameal
T 6000
Dralier (Aulinggessiv))
503
SLEM
min myy.staroll
1154
438
22.4
1.14
Cidel Tama----sssemss--r
256.6
77.5
12.4
0.63
DeepSeok RI-Distill--e Qwen-
709
DrepSSoo--R Q.ennll---oeen
comllnlymill
Drafier (Antinopreseee))
450
SLEM
DeepSeek RI Distil-Qwen 1.30
167.1
51.3
189
0.91
vicung 68m
148.1
32,5
30.6
1.47
HIOONVL
(Amiunorrosois))
SLUM
dny siarvoder.pp
362
28.5
1.38
Jam--- To-mnsmmcs-
182.7
64.4
14.9
0.72
DeegSeok-R Rl Mi--isiil--ueen.. 18
1964
50.3
19.5
0.94
Dratier (Auturegresivv))
SLEM
DeepScok-R -i-nl Qween
983
57.6
vicuna 68m
979.9
59.3
16.5
1.32
phi-4
scnellss
1 FROONVL
AR
No Dralier (Aulinegrssavv))
4319
47
21.3
SLEM
540 B--nneruct
457.7
19.5
Phi- 3.5 mini instract
616.
39.6
25.3
1.19
CodeLlam- 136 Insorxx hil
humneeaa
1 A8000
AR
No Dralier (Auloregresanee)
207
453
21.4
SLEM
T09.7
16.7
59.7
2.79
Inseruce
DeepSeok RI Dienll-Qwen-I
cm ahalllmmai
Drafier (Aulingreesevv)
1931
31.8
SLEM
DeepSeek KI Distil Distill/jwenn (jwen 1.38
83.1
35.0
24.6
0.48
vieuna 68m
65.2
17.6
58.2
1.07
openat hurmnncl
HOOONV
Dralier (Autumerrssavv))
SLEM
tny starrdder.pp
36.1
23.7
39.6
0.78
Codellama- Insercc-hii hf
138.0
54.1
17.5
0.34
DeepSeek-RR Distill Qwen-I
149.3
42.2
22.7
0.45
H100NYL
Drafier (Autoreeresivve)
SLEM
DeepSeek RI Distill Qwen- 1.5B
296.1
41.1
23.5
0.54
vieuna 68m
245.4
24.6
39.9
0.91
2 9b
scrolls
1 HIOONYL
No Drafier (Autoregresaive)
584.0
95.3
9.9
gemma
739.0
SLEM
Vieuna 68m
592.4
48.
18.6
1.37
HYL
AR
No Drafier (Autoregresaive)
42.6
37.0
27.0
1.0
Cominued un next page
18

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
TIFT ims)
TPOT (ms)
Tis
Speedop
Target
Dataset
Hardware
Method
Drafter
SD
2 2b
446.5
29.1
33.2
1.23
SLDM
24.5
col.dmlymail
NVL
AR
No Drafter (Autaregresiv)))
73.7
57.3
26.7
1.0
SD
gemaiia 2 20-1
125.4
39.7
24,6
0.92
SLEM
Vieuna 68m
RT9
16.9
37.1
1.39
DeepSeck- RI- Liama
openail hummanval
A100
Drafier (Autaregresivve
297.1
8.2
SD
CodeLlama- To Imsoruee hi
428.7
101.5
9.0
1.18
DeepScek RI Discil-Laama 8B
353.5
54.3
18.3
2.25
SLUM
starrode.pp
265.9
84.6
11.8
1.44
H-O
Dratier (uturreressave)
1.6.1
76.1
13.1
SD
CodeL.ama-- To Lastuuc-hir
277.3
913
10:4
0.79
DeepScekk RI Distili Liama SB
223.5
52.8
18.8
1.43
SLEM
DeepSeek RI Disiil Qwen- 1.38
297.3
6016
16.3
1.24
muy nuy.starrodor.py
143.3
63.2
1.19
ena dulymaiii
2 HIOONVL
AR
No Drafar (Autorggrssvve)
250.7
77.6
12.9
SD
DeepScek RI Distili Llamz 8B
452.
75.7
12.5
0.97
Lluma-311 3.1-8B
277.9
74.4
13.4
1.044
Liama 3:2-1B
242.3
51.4
Llana-3 2-38
252.1
66.8
14.9
1.36
SLEM
DeepSeek- Bii--iD-DDilll-ee Sil--iiill//yee--....
296.1
72.3
13.6
1.06
vieuna 68m
263.8
51,5
19.3
scrolls
HIOONVL
Draher (Aminrerrssive))
7.7
SD
DeepSeekk RI Distill Distill-Liama Liama- 8B
2121.4
88.0
10.9
1.42
SLEM
DeepSeek RI Disill Qwen 1.38
1890.9
85.8
11.3
1.47
DeepScok --saall-
scrolls
HIOONVL
Drafier (Autareg
245.3
54.3
23.9
Llama
283.1
24.6
Liama 3.2-3B
353.1
35.2
27.3
0.98
SLEM
DeeyScal-R1 Bi-aa---R-DDialleeeeaa Dis.aille/pnnn...... 1.38
315.7
452
20.2
0.73
vieuna 68m
263.4
27.3
34,9
CRe dullymil
Dratier (Aminregrsssve))
21%
SD3
2-15
48.2
2506
38.6
0.44
Liama 3,2:38
57.2
38.1
26.0
0.57
SLES
Vicuno --nsslll----lll-eeee-----
DoegScaal-1
433
22.7
19.7
openal Inmnnneval
HIOONLL
AK
No Draierr (Amiaregresave)
3199
218
4538
1.0
S15
Codel lama- Ths Insmncs-- Instrce-hh
1440
723
12.
0.27
SLEM
37.1
25.8
Dratier (Antinopessse))
468
SDS
Codel 7hs Instmec-hr
2003
1301
79
0.32
SLEM
starcodes
964
52.6
18.2
0.74
DoepSenk-R Ba--Sek--R--isiil--o- Rl--iorill-Qeen-11
246
20.4
Table 7: Full benchmark for TLI (Algorithm 4).
TIFT (ms)
TPOI
Tokk'
Speedup
Target
Dataset
Hardware
Method
Drafter
serolls
4 H100 NVL.
Drafter (Autaregrzssive)
1334.7
5.9
111
Quen? 3-0 B--eemet
13718
97.8
9.0
1,69
vicunn-68m
1329.7
138.2
7.2
1.22
openal Janannval
4 HTOONVL
AR
No Draferr (Autoregressie))
217.5
128.
7.8
1.0
QuenZ 320 B--nsruc
366
viouno-E8m
238.5
7488
13.0
1.67
ene Amilymal
HIOONVL
AR
No Drahar (Amarogressone)
26.3
121
288
11I
Quen7 3--
833
11.2
1.43
81.0
phi-4
sonells
AR
No Dratier (Aulunggreseve)
457.4
472
21.2
111
Quent 3-1 In-lnccnct
454.
3E5
30.8
1.45
Pti- 3, 3.3.--min-iinttrra
610.
460
21.7
1.03
CodeL Ii
humaneecl
Dratier gAulinerrssaee))
453
Iin ptyysaraoddrppp
159
Codell Inma-7h-isstmeshh
141.3
25.6
39.1
1.77
DeepSeok-R RI Diail Qwenll-Qwen-Iie 14
senells
[ RTX 6000
AR
No Drafier (Aulimprrssevv))
1993
833
103
DouppScak-R -----ssll--uue----
vieuna 68m
1502.
57.2
17.1
emn dinlymail
1 RTX 6000
AR
No Dralier (Anlomgrresine))
1761
S44
18.4
11I
Daeppeekk-R -I---RR----ssoooorro 3N
2013
44.7
21.4
1:16
200.4
R 6000
AR
No Dratier (Aulinggessve))
919
19.5
111
35.6
25.4
Codellama- 7o Insemcc-hif
150.2
66.0
14.6
0.75
DoepSeok- RR-Disiill--uaaee Seeelll-wen---.3
172.6
45.6
1.08
DeepSeck RI Disill Disiill-ween11
cnn dmllmmmaa
H1L
AR
No Drafer (Auturegresavv))
350
1938
50.6
TLI
DeepSrek RI Distil-Qeenn
9510
27.2
36.6
0.72
vicunu-680 68m
108.5
18.4
54.2
1.07
openai hurmaneval
HIOONVL
Drafier (Autoreeresave))
20.0
TLI
tnny slarcodss.pp
400
22.1
44.7
0.9
Coded Juma- hmms----sssss---r
59
30.2
25.3
0.51
DerpSeek RI Distill 1.5B-1.5B
88.3
24.3
40.9
0.82
sonolls
Dratier (Autunggreseee))
230.5
218
TLI
DeepSeek RI DistallQ@eenn
1.38
290.9
29.1
34.2
0.79
vicunu 68m
238.6
25.0
39.2
0.91
gemmma-22 2-9hh
scnells
AR
No Drafier (Aulimgresavve)
S85.
W16
10.4
Comiinedd pags
19

---

Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
TIFT (ms)
TPOT (ms)
Tis
Speedop
Target
Dataset
Hardware
Method
Drafter
TL1
vieuna 68m
603.0
46.0
21.4
2.04
gemmaa 20-11
712.3
37.7
opeaal.humaneval
H1OO
AR
No Draferr (Autaregresive))
42.6
57.3
26.8
1.0
YL1
Vicuna 68m
92.3
25.1
39.2
1.46
5D
2 26-1t
391.
27.
36.4
1:36
con.duilymai
NVL
Drafier (Autoregressive)
37.8
T1.
Vicuna 68m
1001
36.0
33.2
1:36
SD
Wemmma 2 26-11
1178
35.3
29.8
1:33
DeepSeek RI Disiil Liama 70B
ggesal.huranevel
2 A100 80GB PC
Drafter (Autloegressive)
244.0
123.5
8.1
starcoder. py
85.5
SD
Codel.oma-- Tos Lastuucc-
517.3
87.2
11.4
1.41
DeepScekk RI Discill Liama SB
358.2
53.1
18.6
2,5
2 2-IOOONVL
AR
No Drafter (Auluregresaive)
129.9
76.7
13.0
muy starcooryy
1479
55.3
SD
CodeLlama 7b Lasonuce-hi hf
214.3
65.8
14.5
1.31
DeepSeek RI Distill Llama SB
179.7
44.6
22.4
1.72
TL1
DeepScekk -i---iill--Quen---
220.4
45.5
21.9
1.08
acrolls
Drafier (Autoregresaive)
2.7
5D>
Deceyscclc RI -hstill-llam--a
2074
651
15.2
1.98
111
DeepSeekk RI Discill- Soscill-JJwor (wen-1.35
1898.
70.9
13.9
1.82
dulymail
2 HIOONVL
No Drafter (Autoregresavve)
231.
77.9
12.8
DeeyScea--R RI RI-Diiril---amaa Lama--B
TL1
DeepSeck RI Mil--iitil---eeee -/een-l--0e--1..
515.5
59.7
16.7
vicuna 68m
263.4
55.8
17.8
1.29
Elumaa31133 1-3
3023
5916
16.7
1:31
Liama
248.5
51,3
Liuma 3.2-3B
259.6
56.7
17.5
1.37
DeepScok Ril.----Dll-eeeeecc.oo
scrolla
1 HTOONVL
AR
No Draheer (Amnaregrosine))
946.4
77.3
12.5
1.0
TL1
DeepScekk Dissiill -.en-13
99788
43.0
22.7
1.52
viouno-68m
977.1
61.6
15.9
1.27
openal. haninnvaa
HIOONVL
AR
No DraFerr (Amaregrosoone)
723
48.6
20.6
TLI
nny starcoder
96.2
35.5
28.1
1.37
Codel Inma- TT-lssschs
123.4
49.5
DeegSeekk- RI DDisrill-wwen-111
147.4
28.5
35.0
Gna dmlymai
HHONNLL
AR
No Drahar (Amlaregeessee)
121.3
4910
20.4
V1I
DasyScat-R1 -is-rill--uuenn 38
1073
370
26.1
1:28
vicuno- 68m
146.4
3422
DrepSookk -T-enl 3.mm-88
serells
Drafier (Antinopressie))
3667
356
T1I
3244
333
20.6
1.39
vicunn 68m
256.
28.1
34.5
1.29
Hamaa-12-11 2-18
201
349
39.7
Llamaa-32--8 2.338
355.
31.7
31.2
ena dailymail
1 HHOONVL
AR
No Drafter (Amaarggrsssve))
39.6
223
44.9
1.0
111
DaspSeattRR Bt-.:eaa-R---olll---eeee -Tssrll-qwenn 3N
714
310
31.1
0127
vicuan-68m
30.3
1.09
[ima-
256
44.2
1anag-3 2-38
602
29.2
34.2
0.76
openaa Jomnnneva
HIOONVL
AR
No Draferr (Auttregressine)
312
223
44.8
1.0
liny
23.6
Tama- Irsencc-hr
350
TTREX GIN0
AR
No Drahir (Amiaregresoiee)
734
41.1
24.3
slarosder
RL3
30.
25.1
Tm
Codel Ti-sssh-sst
218.6
63.0
DeepSeek-R RI DisiillQwen-I.. 1.5B
14588
35.7
26.0
1.07
E
Vocabularies and Overlap
This section examines the vocabularies of widely used off-the-shelf target and drafter models. Table 8 shows the vocabulary sizes of widely used target and drafter models. Table 9 shows the vocabulary overlap between the target and drafter models. Table 10 shows the ratio of the number of tokens in the intersection between the target and draft vocabularies !T" n D'| to the number of tokens in the target vocabulary (T"), considering only the tokens that appeared in 50 randomly selected prompts for the given task.
Table 8: Vocabulary sizes of widely used target and drafter models.
Targel Model
Vocabulary Size
google/Gemmma-2-0 2--9
256,000
meta- Jamaaa 1-70B
128,256
mistralaiMixtralaaa 22--nsttcctvv
32,768
microsof//Pii. 3. m-meium 128k instruct
32,011
CoddelaamaCCodeLlaaaa 1 Sb-Inntrucc--ii
32,016
Drafter Model
Vocabulary Size
Qwwnn/Qwee2-0035 3-0.22-0.3B-B---- Instrect
131,644
bigcode/tiy begood/tiyyssarrddu..p
49,152
domhle7/vicua-66mm
32,000
20

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
Table 9: Vocabulary overlap metrics for widely used target and drafter models: the size of the intersection between the target vocabulary and the draft vocabulary, and the ratio of the intersection size to the target vocabulary size. We can see a wide range of overlap sizes and ratios.
Target Model
Drafter Model
TnD D
I' D [
Jlama-3.1-706
Owen2-0038-Inssee
109,566
0.85
Gemoma-2-0
vicuna-6866
30,489
Mixtral-8x 2xB Ins.
vicuna- 68m
24,184
0.74
Mixiral 8x22B Instract v0.1
Qwen2 0,5B Instruct
10,566
0.32
Pla- 3ia----medium- 128k-instruss
Swee2--0.BBIInstuue
9,588
0.30
CodeLlama-I Ii--smmttt----sttt--ffii
tny hty_sstaccder_.p
8,481
0.26
F Injectivity of Tokenizers Under the CMM-DM Dataset
The experiment sampled uniformly at random examples from the CNN-DM dataset (Nallapati et al., 2016b), and took the prefix of 100 characters from each example. Using a SentencePiece tokenizer (Kudo & Richardson, 2018) or various other Hugging Face Transformers tokenizers (Wolf al., 2020), we encoded the prefix into tokens, and then decoded the tokens back into text. We then checked whether the original prefix could be recovered by checking whether While tokenizer may implement non-injective function in general, this experiment specifically tested its injectivity on the given dataset. The results of our experiment are summarized in Table 11.
recood(encoder
G Proofs
Theorem 3.1. Let p be a non-trivial target probability distribution over a vocabulary T, where there exist t,,ty bo E T such that p((1) + p(12). Lei q be the drafter probability distribution over the same vocabulary T. 1fq = p. namely, the drafter is another instance of the target model, then the expected acceptance rate of the exact matching method arm is strictly less than the expected acceptance rate of the standard speculative decoding method usn. Namely, it holds that OEM < asn.
Proof. The expected acceptance rate of the standard speculative decoding verification method is OSD Ever min(p(t), q(t) by Leviathan et al. (2023). If p, we have asp Ever min(p(t),
Eier p(t) 1. For exact matching, token / is accepted if it is sampled by both the draft and the target models. Since these are independent events, the probability of accepting t is p(f) p(t) = p(t)?. Thus, we have QEM = =EGTT p(t)2. For any p(t) such that 0 < p(t) < 1, it holds that p(t)² < p(t). Summing over all tokens E T, we get that Eier p(t)² < <EEr p(t) = 1. Therefore, QFM < asn for any non-trivial target distribution p.
Theorem 3.2. For any token in the target vocabulary E T. Algorithm 3 outputs the token t with probability p(t) if we Σ
define (t) = d : (d.))...dd)) (I.....))
II q(d,). Namely, Algorithm 3 is lossless.
Proof. Denote the probability of accepting the token & by Pr [accept t | f). We have that Pr [accept t ||] = 1ff 2 (t). and p(O)
v(t) otherwise. We also have that the probability of sampling tokens from q such that their concatenation forms t is (t). Therefore. Σ, Pr aaccppt = E, Pr (accept [] Pr [4] = E, min (p(t), (t)).. The probability of outputting & is then Pr (output t] = Pr (accept t] + (1 - Σ, Pr [accept t)) T T-E. min (p("),)()))
p(t) p(t)-min(p()) ((1)) = p(t).
Lemma 3.1. For a target token of length m S n in a complete vocabulary D, that contains all possible strings of length up to n over a fixed alphabet Σ, the number of distinct sequences of draft tokens di....,d; dg such that their concatenation di @ ... @ d, starts with t, namely, T(d, @.... B d:)1
is m1
We can approach this counting problem by considering as combinatorial composition, specifically the number of ways to write the length m of the target token as the sum of a sequence of strictly positive integers. Consider the token of length m, which can be decomposed into sequence of tokens t1, f2, ... fm. Each possible partition of m into smaller segments corresponds to a unique way of concatenating draft tokens from the vocabulary. The problem can be reduced to counting how many distinct ways we can concatenate these tokens to obtain the desired target token t. There are exactly 2 ways to achieve this because, at each position between the tokens, we have two choices: either to concatenate the next token with the previous segment or to keep it separate. For example, given the sequence f1, t2 tmm the possible compositions include (11 () 12), (....., .mi 11, (12 @ f3), ...,...,, Imi and (11 ( l2 ( f3), 14, ..., bm and so forth, covering all
Proof.
21

---

Lossless Speculative Decoding Algorithms for Heterogeneous Vocabularies
Table 10: The ratio of the number of tokens in the intersection between the target and draft vocabularies IT' n D'| the number of tokens in the target vocabulary [T"], considering only the tokens that appeared in 50 randomly selected prompts for the given task. Note that (7" n D for a given task could differ from ( DI/[T] because some tokens of T or D might not appear in the prompts of the given task.
Target
Eating
Diadack Ri-Biiidaaaaa nus
Desdlckk Rr-DDedl-
codog
spenz Jereaced
10
Deapbeek -i-nie Lane k0
laaysta
wnch
Despiot Ni-Deellllo
Deggiut Ki Ri-Beeiiiionnn nus
Desploet RI Ri-Beell--am 1.0
cading
speeal benueeed
14
Deajick
lagedt
1.58
Deggiont K: Di-Deliiionss nu
Lian- 11401
emnil
14
Despoutt R--Beel---aa
11-m-11-a11
eates
cre.cafyrual
14
Lisse 1218
1,0
12-0012-91
Ina can
Degdbck-R RiDihilklaaea 7t
colis
1pena Jeraane
2.56
Degdeck Ri-Biillllaas ns
ransadike
loapsts s0ses
bards
3.97
Dengint
Deggiont R:: D--Beti-iinsss
Despleet Rt -il.llll-000 Bameei-----ttt-eeeeee- 1.00
coding
opecal Jenuneed
1.4
Deapout Ri-Bellk-aaa st
Deupdeat 81- Reteeel-----lllOOmmomm 1.50
screll
Degleek Ri B.DiillElmmss 5S
Liare: 1--1B Liau-1
lagget
smits
1G
Deggontt R--Bcilk-lmms
eates
cre.sstyrull
Degpleck Ri- B.Disllllaasss SS
Liane:3 1 1.348
crnulelyrail
1.0
Degdeck Ri- Beellllaa 6S
lry ary.arcceer..p
collig
(peaa Jerezced
0.94
Degpieat R2 di-Deeikhlaaai iS
riceza-lin
cre.dadyrual
Degdiat Ri-heellghassis
Codd Toodikarra----aammat
codog
speeal Ienueeed
C.3
Degdect DicillQsssss
Deppoek
collnn
speas Jeronced
Degjint RI- Et-BeillQaaaiil ins
Deplieet Rt- (lwcll-Qaaaalll 1.30
eares
crn ralyraal
Deagiett Bi-Beelkkaaaslle
nas macoder
coding
spenal Iarazeel
Degplock Ri Dielllaassil icB
creuielyrall
Deggiek Ri-lllll 378
Cold korn co
callig
(peaa Janeznad
callnn
speas
Degpiect R2 Mi-BeillQaras-S
2a-32
Deppicck RJ Di--llllll QnaalliQ-aaii 1.35
Depdickk Ei-Bhellkhaa--t 2a-322
Daydicck Ri- Ri-Bbell-Qooi Quaa---aa- 1.5
srn-ddibrzal
1G
Despbot Bielllua
96
Deedleck- Rt B--BellkOnaaatz ca-izs
iTe dadyraal
6.66
Esspocat Bo
spena Raraziea
Desplok ki (aill-uss 78
Deppieet RI Dee Seart--Qamm Quee 50
Ing care
cmilk
1.
Deipook Qu
Depliei thel Qwar 1.
carm
opena
Despteck Ri Mi-BeillQnaaall
1azza-6ikn
Denplook Beilliaass..
exeea
3.90
Liam-33-38
codog
spcnn.Jateacoe
11aew-1 1.20
12ae 11-5n
13 1--00
Liamu 1 1.an
carn
cre dolyrull
1.
Lixe-2117106
12:10
codin
openal latuaced
E/amu 15-18
carn
10
13am0-11-701
Uaau 12-3
cating
opeaa henuoral
10
Liasn 1 12:38
Oonz? 5u bumot
cating
Lix7x-111776
rad
Laze: 3:38--------
calig
speer Torraied
D3
Laae-221-76--
Liasm-11-80 1aam-21--B-taatrrs
langsts
1Jaru-111 11-203-00 Teome
tearect
11 1520-11-765-pamm
Lianu-1 12-11-1-1-ee Inaree
cading
opeiaa Jeninnnd
1.
13amu-11-000 13mm-11-7tt--pemm-
Liau- 2-11l-eearss
Liase:? 12-B-leattsd
colis
spena Jermacdd
13amu 11775--ppemm
Laau- 2-M--eeara
Qveed S4 bi---ooas
coles
Inseaced
Ukees 1--6--------
Qweel S. S4.18.1 Be-llss
loapsts 500E3
sands
10
1Jamu-111 111700--eammm
viceta-fien
laagets 50XEs
>ards
0.95
Uiaee 11-00-iamne
1l 11-08 Inore
Laauu 15-11 learec
1G
IJamu 11-00----m-
Liamu- 1-11--eaa
crauadyyral
Liane: 2-18 Inateed
langets
sarls
LG
IJamu 11-00---era
Liam-- 2-40 -ill-tearst
earn
crautdyyral
opeadi
Uiaen 100 lestee
540 11.88 balla
langsts
Qweek S. Inllo
1.0
opeca Jensoeed
LJanu-3 3.1 tearse
vicuza-iire
Inag-r
Useee 1.00- Stsreet
0.66
Qoaz2 5413B
coding
opena Jananeed
Nived- SeC78
8
Miseel Missel--i2S bonci-O
Ovee2 2.r25.0.33 Inana
crnuhelyral
09
Miteral 4c225 Swrnec-lll
coling
opena Januneel
0.50
Miviul 2025 Sooni-Ol
srnulelyrall
5.
0ver2.51 58 Ininat
Owee2:5 51158-3soo
Iuggets 530e
smnds
100
Qwee2.51
porers Th-t
Inggets sance
10
poreend 22-8
CTa eadyraal
18
2 sh-1
Inngets sance
sails
2.99
vicearike
Ccn radyrall
rialig
1hi-15
p314
Fh--35 cank ipsset
CIB cadorzal
0.00
Sin tumer
2314
Ovee1 54133-5-133-0000 barnst
STR celornal
14
22

---

Lossless Speculative Decoding Algorithms for Heterogencous Vocabularies
Table 11: Results of injectivity tests for various tokenizers.
Library
Tokenizer
Injective
SentenscPiece
SentencePiece
True
Hugging Face
gp12
True
Hupzing
double7/vicuna--e
Hugging Face
bigcode/Liny starcuder
True
Hugging Face
True
possible ways to concatenate adjacent tokens. Thus, the total number of valid concatenations is 2 which follows from the combinatorial nature of partitioning the sequence into contiguous segments.
Theorem 4.1. Let and 9 be target and drafter probability distributions over vocahularies T and D, respectively. Define p', q1, 92 to be probability distributions over TUD as follows. p' (x) = p(z) if E ' and p'(x) 0 otherwise. qi -
x E D and q1 (x) O otherwise. (2(x) Eeer q(t) if E T and (2(x) 0 otherwise. Given the target pl, define on and ag to be the probability of accepting a token x ~ qı and x ~ 92, respectively, by the rejection sampling algorithm of speculative decoding from Leviathan et al. (2023); Chen et al. (2023). Then, a₁ S ag and the output tokens distribute according to p.
<(w)
Proof. By Leviathan al. (2023), the expected acceptance rate is the sum of the minimum probabilities of the tar- get and draft distributions, namely, we have ai EESTUD min (x),
Exer min q) (x)} s (œ)) = a2 since Ezer ((2) S 1. The output tokens distribute
Exerur min according to p' because the rejection sampling algorithm of speculative decoding preserves the target distribution. Since p' (x) p(x) for I E T, we have that the output tokens distribute according to
Ever min (z), 92())}
23


Reviews:
[{"review_id": "cpF297V7Je", "reviewer": "Reviewer_8FKT", "summary": "This paper addresses a key limitation in existing speculative decoding (SD) methods for large language models (LLMs): the assumption that the drafter and target models share the same vocabulary. The authors propose three novel lossless SD algorithms—String-Level Exact Match (SLEM), String-Level Rejection Sampling (SLRS), and Token-Level Intersection (TLI)—which remove this constraint and support heterogeneous vocabularies. The proposed methods preserve the target distribution and work with off-the-shelf models, eliminating the need for costly retraining. The paper presents thorough theoretical guarantees and empirical evaluations across summarization, programming, and long-context tasks. Notably, one of the proposed methods (SLEM) has already been adopted as the default for heterogeneous SD in Hugging Face Transformers, demonstrating real-world impact.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and for highlighting so many strengths in our work. We appreciate your acknowledgment that **“this paper addresses a key limitation in existing speculative decoding,”** and that **“the paper presents thorough theoretical guarantees and empirical evaluations across summarization, programming, and long-context tasks.”** We also value your remark that **“this idea has a broad impact in the era of speculative decoding,”** and your observation that **“notably, one of the proposed methods (SLEM) has already been adopted as the default for heterogeneous SD in Hugging Face Transformers, demonstrating real-world impact.”** (– After this submission, TLI has also become the default in HF Transformers, as mentioned below.) Furthermore, we are glad you find **“Algorithm 3 is interesting”** and noted that **“Algorithm 3 (SLRS) is theoretically superior in acceptance rates.”** In particular, we are grateful that you recognize how these points underscore the significance of our contribution:\n>**“Strengths:**\n>- **Novel Contribution:** The work **relaxes a long-standing constraint** in speculative decoding—the requirement for vocabulary homogeneity—**broadening its applicability significantly**.\n>- **Lossless and Theoretically Grounded: All proposed algorithms are rigorously proven to be lossless, with clear formal definitions, acceptance rate bounds, and theoretical guarantees (e.g., Theorems 3.1, 3.2, 4.1).**\n>- **Practical and Open Source Impact: The integration of Algorithm 2 into Hugging Face Transformers and its adoption as the default decoding method for heterogeneous vocabularies highlights immediate practical relevance and community validation.”**\n\nBelow, we address your concerns regarding the computational overhead of Algorithm 3 (SLRS) and the dependence of Algorithm 4 (TLI) on vocabulary overlap.\n\n---\n\n## A1. SLRS Proven Advantage\n\nThe paper never claims that SLRS (algorithm 3) is practical *today*, with *existing* off-the-shelf models. Instead, we openly discuss its limitations in Section 3.4, where Lemma 3.3 transparently analyzes the tradeoffs of implementing SLRS with existing off-the-shelf models, which often have almost complete vocabularies (see ‘Vocabulary Constraints’ in Section 3.1 and Appendix D). Lemma 3.3 reveals how practitioners could design *new* vocabularies to facilitate SLRS.\n\nSLRS is mathematically proven to be:\n1. Lossless (Theorem 3.2), as you mentioned in your review (“All proposed algorithms are rigorously proven to be lossless, with clear formal definitions, acceptance rate bounds, and theoretical guarantees”)\n2. Increasing acceptance rates compared to Algorithms 1 and 2 (Table 2), as you mentioned in your review (“Algorithm 3 (SLRS) is theoretically superior in acceptance rates”)\n\nYour review mentions that SLRS is novel and addresses a long-standing key limitation. Therefore, we believe SLRS contributes to the research community by laying down theoretical foundations upon which future works can design vocabularies for heterogeneous drafters. Since heterogeneous drafters are a new research direction that has already shown potential (in this work and by its wide and quick adoption in practice) but has not been previously studied, such contributions could become fundamental.\n\n## A2. TLI's Effectiveness Is Mathematically Proven + New Extensive Benchmarks Over Various Practical Setups\n\nThe effectiveness of any speculative decoding algorithm is controlled by its acceptance rate, and TLI (Algorithm 4) is no exception.  In edge cases of low or no alignment between the draft and target distributions, all the known speculative decoding algorithms are expected to fail, including those in this paper.\n\nTable 2 provides the readers with the expected acceptance rate of all our algorithms, including TLI. We can see that the acceptance rate depends on the probability mass that the intersection supports. Please note that the acceptance rate is governed by the supported probability rather than by the size of the intersection (namely, the number of tokens in the intersection).\n\nNevertheless, practitioners in the past years have often been using BPE, WordPiece, Unigram, or SentencePiece to construct tokenizers that share a reasonably large intersection, thanks to their heuristics (see ‘Vocabulary Constraints’ in Section 3.1 and Appendices C and D). In practice, TLI is highly effective in various setups and, therefore, has recently become the default behavior in Hugging Face Transformers after they conducted a thorough and independent benchmark. Please see [Section 1 of our response to Reviewer a7E7\n](https://openreview.net/forum?id=vQubr1uBUw&noteId=6DDgLIbPNK) for details.\n\n---\n\nThanks so much for your support! We are eager to address any remaining concerns you might have.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "**Dependence on Vocabulary Overlap:**\nAlgorithm 4’s performance depends heavily on the intersection between the drafter and target vocabularies. In edge cases with low or no overlap, performance gains may vanish.", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "- **Lack of analysis of computational overhead in Algorithm 3:**\nWhile Algorithm 3 (SLRS) is theoretically superior in acceptance rates, it may be impractical due to the exponential complexity of computing string probabilities ψ(t), especially for models with large vocabularies.\n\n- **Limited Evaluation of Algorithm 3:**\nThe empirical evaluation focuses primarily on Algorithms 2 and 4. Although Algorithm 3 is interesting, its lack of experimental results makes it hard to judge its practical value.", "relation_to_broader_scientific_literature": "This idea has a broad impact in the era of speculative decoding", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths:**\n1. **Novel Contribution:**\nThe work relaxes a long-standing constraint in speculative decoding—the requirement for vocabulary homogeneity—broadening its applicability significantly.\n\n2. **Lossless and Theoretically Grounded:**\nAll proposed algorithms are rigorously proven to be lossless, with clear formal definitions, acceptance rate bounds, and theoretical guarantees (e.g., Theorems 3.1, 3.2, 4.1).\n\n3. **Practical and Open Source Impact:**\nThe integration of Algorithm 2 into Hugging Face Transformers and its adoption as the default decoding method for heterogeneous vocabularies highlights immediate practical relevance and community validation.\n\n**Weaknesses:**\n\nSee Above", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7gg4X71RIv", "reviewer": "Reviewer_S2J2", "summary": "This paper explores possible solutions for speculative decoding with a drafter model that does not share the vocabulary with the target model. Such methods, if successful, can enable the use of many more models as the drafter model for a large model to reduce the inference cost of large language models. The authors approached this problem with two distinct verification methods for speculative decoding: token match verification, and string match verification. Benchmarks demonstrated the success of the proposed methods when Gemma-2-9B-IT is used as the target model.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and for underscoring several positive aspects of this work. We appreciate your noting that **“Benchmarks demonstrated the success of the proposed methods when Gemma-2-9B-IT is used as the target model,”** including the observation that **“Table 1 shows that with Gemma-2-9B-IT as the target model, Algorithms 2 & 4 can be faster than autoregressive decoding with vicuna-68m as the drafter, and sometimes even exceed the decoding speed of a Gemma-2-2B-IT drafter.”** We also value your statement that **“I checked the proofs in Appendix E. They are correct as far as I can tell.”** Furthermore, we appreciate your recognition that the proposed methods are **“easy to understand and implement,”** **“The experimental design, which mostly involves benchmarks, is sound”** and your emphasis on these:\n>**“Strengths**\n>- The problem is **well-motivated** and successful solutions would be **useful for LLM practitioners**.\n>- **A large number of experiments were conducted to help readers evaluate the effectiveness of the proposed methods.”**\n\n---\n\n### Improved Benchmarks Suggest Significant Speedups In Practice\n\nWe've extended our benchmarks, as mentioned in [A1 for Reviewer a7E7\n](https://openreview.net/forum?id=vQubr1uBUw&noteId=6DDgLIbPNK), and resolved the variance issue in the number of new tokens by filtering out crashed runs before averaging.\n\nWe intentionally include configurations where our methods fail—to highlight their *limitations* instead of cherry-picking the best cases, communicating that practitioners should be careful when selecting heterogeneous drafters.\n\nSLEM and TLI are highly effective in practice and have been widely used in the industry during the past months, which indicates their real-world impact. The algorithms **do not “underperform”**. Like any SD algorithm, their effectiveness is controlled by:\n1. Acceptance rates, as Table 2 provides.\n2. Ratio between the models’ forward latencies.\n\nLarger targets often lead to acceleration, as you noticed. There's also an implementation overhead that has been shown to be negligible in light of the significant empirical speedups.\n\n---\n\n>\"There is no explicit discussion on the correctness of Algorithm 2, but the correctness is also not difficult to prove.\"  \n\nThe algorithm verifies that the final output string exactly matches the string that the target model generates, hence the correctness (losslessness) is derived immediately. What discussion do you believe is missing?\n\n>I don't understand why \"we should accepted the token 'aa'\".\n\nWhat advantage do you get from rejecting the draft token ‘aa’? The target model can only generate strings that contain the character ‘a’.\n\n>It appears to me that Algorithm 2 simply can't work if the vocabulary conditions do not hold. I don't understand why it would instead \"leading to a decreased acceptance rate\" if the acceptance rate is undefined in this context.\n\nThe acceptance rate is always well-defined but might be zero.\n\n>\"it does not guarantee that the output tokens are exactly the target tokens\". I am confused about what \"output tokens\" means here as standard SD draws samples from the target distribution. What makes their samples not \"the target tokens\"? Or is it possible \"output tokens\" here really mean drafter sample tokens (which might get rejected)?\n\nSD algorithms operate on two distributions, given by probability vectors corresponding to the *drafter distribution* and *target distribution*. These algorithms output tokens, which effectively define an *output distribution*. Previous works proved that the output distribution aligns with the target distribution (also known as *losslessness*).\n\nThe fact that two tokens are sampled from the same distribution **does not imply** they are equal, as stated in the paragraph that you mentioned.\n\nThank you so much for asking this question; it has already helped us to improve the paper. We'll add an extended exposition on speculative decoding to enhance the clarity of future revisions.\n\n>Algorithm 3 was not benchmarked\n\nPlease see A1: https://openreview.net/forum?id=vQubr1uBUw&noteId=gIxgR1GrKk.\n\n>Line 12 of Algorithm 5 should be \"if $j < i$ ... or else sample $t$ from $p_x$\".\n\nThanks so much for bringing to our attention this issue. Beyond citing the papers that introduced SD, we included a rephrased version of their algorithm rather than copying it verbatim, as you noticed. Regarding your proposed change, please note that it samples the last token from $r_x$ rather than $p_x$ even if all the drafts are accepted (i.e., $j = i$), and hence **is lossy**.\n\nWe corrected the mistake by editing line 12: Sample $t \\sim r_x$ for $r_x(t):=\\frac{p_x(t)-\\min\\{p_x(t),q_x(t)\\}}{1-\\sum_{t'\\in T}\\min\\{p_x(t'),q_x(t')\\}}$ if line 9 ever rejected a token. Otherwise, sample $t\\sim p_x$.\n\n---\n\nWe are also truly grateful for your additional detailed suggestions for enhancing the ordering and presentation. They've already been very helpful in improving the paper.", "claims_and_evidence": "The main claims of this paper are the correctness and the effectiveness of the proposed algorithms.\n\n\nThe claim of correctness is reasonably substantiated,\n-   The correctness of Algorithms 1, 3, and 4 can be easily established from the proof for the standard speculative decoding algorithm.\n-   There is no explicit discussion on the correctness of Algorithm 2, but the correctness is also not difficult to prove.\n\nHowever, additional data would be necessary to support the claim of effectiveness,\n-   The benchmark results were reported in Table 1 in the main paper, and Table 7 in the appendix. Table 1 shows that with Gemma-2-9B-IT as the target model, Algorithms 2 & 4 can be faster than autoregressive decoding with vicuna-68m as the drafter, and sometimes even exceed the decoding speed of a Gemma-2-2B-IT drafter (same vocabulary as Gemma-2-9B-IT). However, Table 7 paints a different picture,\n    -   There appears to be a trend that the proposed methods appear to not perform well on larger models: On quite a number of target/dataset combinations, the proposed algorithms underperforms or performs similarly to autoregressive decoding (e.g. Llama-3.1-8B-Instruct on CNN Daily Mail, Llama-3.1-70B on scrolls, Mixtral-8x22B-Instruct-v0.1 on scrolls and CNN Daily Mail, Llama-3.1-70B-Instruct on scrolls). While admitted the success of speculative decoding depends the choice of the drafter model, the prevalence of underperforming combinations calls into the question whether other factors are also contributing to the problem.\n    -   Potential buggy implementation: The new token counts when temperature is 0 should be close, if not identical, across different methods on the same target model. However, they are drastically different in Llama-3.1-70B, CodeLlama-13b-Instruct-hf, and Llama-3.1-70B-Instruct.\n-   Algorithm 3 was not benchmarked, and I am not confident that this algorithm can be made practical due to the need to iterate over a large number of possible drafter tokenizations.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the proofs in Appendix E. They are correct as far as I can tell.", "experimental_designs_or_analyses": "The experimental design, which mostly involves benchmarks, is sound. However I have several doubts about the results and analysis of the effectiveness of the proposed methods. See my comments around Table 7 above.", "relation_to_broader_scientific_literature": "This paper is a continuation on the works on using speculative decoding for improving LLM inference speed. It directly builds upon the seminal work on speculative decoding ([Leviathan et al, 2023], [Chen et al, 2023]), in both methods and proofs for correctness.\n\n[Leviathan et al, 2023]: https://proceedings.mlr.press/v202/leviathan23a/leviathan23a.pdf\n[Chen et al, 2023]: https://arxiv.org/pdf/2302.01318", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths\n-   The problem is well-motivated and successful solutions would be useful for LLM practitioners.\n-   A large number of experiments were conducted to help readers evaluate the effectiveness of the proposed methods.\n-   The proposed methods are simple modifications of existing methods, and thus are easy to understand and implement.\n\nWeaknesses:\n\nThe presentation (especially organization and clarity) of this paper has a lot of room for improvement. For example,\n-   Certain parts can be reordered to make the reading flow less disruptive to readers, e.g.the discussion of Algorithms 1 & 4 should be combined into a single Section 2.\n-   \"Algorithm 2 Supports Non-Injective Tokenizers\" should be incorporated into the pseudocode of Algorithm 2. This is a crucial part for the correctness of this algorithm, however the current verbose description is both hard to follow and lacking crucial details (more on the second point later).\n-   Many of the discussions in the text are confusing and unclear. For example,\n    -   (099-104, left column): It appears to me that the condition $p(t) \\leq q(t)$ for all $t \\in T$ can only hold when $p = q$. Algorithm 1 being \"optimal\" in this case is not a terribly useful result. This paragraph seems to try to motivate Algorithm 4, but that can be done in a much simpler way by pointing out any samples from $D - T$ is useless.\n    -   (082-089, right column): It appears to me that Algorithm 4 will sample from $T$ and thus not \"sub-optimal\". I don't understand why \"we should accepted the token 'aa'\".\n    -   (111-114, right column): It appears to me that Algorithm 2 simply can't work if the vocabulary conditions do not hold. I don't understand why it would instead \"leading to a decreased acceptance rate\" if the acceptance rate is undefined in this context.\n    -   (197-198, right column): \"it does not guarantee that the output tokens are exactly the target tokens\". I am confused about what \"output tokens\" means here as standard speculative decoding draws samples from the target distribution. What makes their samples not \"the target tokens\"? Or is it possible \"output tokens\" here really mean drafter sample tokens (which might get rejected)?\n-   The writing can be made much less verbose. For example, (174-178, left column) could have been a simple sentence \"$T \\neq D$ limits the ability of the target and draft models to communicate tokeni IDs\"; and the repeated reference to HuggingFace's wide adoption such as (040-042, right column) and the first paragraph of Section 5 could be just \"our algorithms have already been implemented in the widely used HuggingFace transformers library\".", "other_comments_or_suggestions": "-   Line 12 of Algorithm 5 should be \"if j < i ... or else sample $t$ from $p_x()$\".\n-   Tables 4 & 5 are presented as part of the main paper but are in the appendix. I am confident that the authors will be able to find room for these tables after condensing their writing and removing unnecessary content.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "84NwBQH3Jo", "reviewer": "Reviewer_7xEY", "summary": "The authors provide a comprehensive view of the challenges in performing speculative decoding with different vocabularies.\nThey come up with several solutions to address this, each with its own benefits and weaknesses.\n\nIn my personal experience, this is often a real headache, as training drafters for specific models is often difficult and time consuming.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We appreciate your recognition that our work provides **“a comprehensive view”** of speculative decoding with different vocabularies, that **“The exposition is rigorous, the algorithms are well motivated and the lossless-ness is proved,”** and that we do a **“good job of showing specific examples and failure models of naive solutions.”** We also value your observation that **“The contributions are, to my knowledge, novel and relevant in relation to the literature,”** and that **“The paper is very clear and well written.”** Moreover, we appreciate your personal insight—**“In my personal experience, this is often a real headache, as training drafters for specific models is often difficult and time consuming.”**—which underscores the pressing need to address heterogeneous vocabularies in speculative decoding.\n\n### 1. Intersection Sizes are Provided\n\nYou requested “some example of the size of the intersection between some common tokenizers/vocabulary”. Please note that:\n- Table 5 in Appendix C provides the sizes of the intersections for various target–drafter pairs.  \n- Table 2 shows the expected acceptance rate for each pair, which governs its usefulness.  \n\nWe are eager to address all your concerns in hopes of justifying a higher score. Do you see any model pairs that we could add to Table 5 to significantly improve the paper? We are open to adding them all.\n\n### 2. New Extended Benchmarks\n\n1. Independently of our benchmarks, Hugging Face’s core maintainers have thoroughly evaluated the effectiveness of SLEM and TLI (Algorithms 2 and 4) and found our methods to be the most effective among all the speculative decoding algorithms they currently support. As a result, they made SLEM and TLI the default in Transformers (in Oct ’24 and Feb ’25, respectively), powering 5,000 other libraries with various use cases and hardware setups.\n\n2. Section 1 of [our response to Reviewer a7E7](https://openreview.net/forum?id=vQubr1uBUw&noteId=6DDgLIbPNK) adds larger-scale benchmarks with additional pairs and hardware setups. These updated benchmarks suggest **significant speedups of up to 2.1× for SLEM and 1.69× for TLI**.\n\n3. As [1] extensively studied, predicting the expected speedups of speculative decoding algorithms is possible by accurately estimating the ratio between the models’ forward latencies and acceptance rate. Table 2 provides the expected acceptance rate for all algorithms, and the ratio between the number of parameters of each model is often used as a surrogate for estimating the forward latencies ratio (see [2] for example).\n\nOur updated benchmarks above include 170 configurations of `<target, dataset, hardware, algorithm, drafter>`, each evaluated over 30 prompts, summing to a total of 5,100 runs. We designed these experiments to align with the highest standards of isolation, portability, and reproducibility, such that we completely sanitize the environment before each run—freeing all CPU and GPU memory. As a result, the initial setup of each run incurs a high overhead, especially because we must reload the models into the GPUs after clearing the memory, which can take a few minutes. This process requires reserving access to hardware for over a week when summing across all nodes and costs thousands of dollars, which is expensive given our constrained budget. Even if we had more budget to average over more prompts, since the set of all `<target, dataset, hardware, algorithm, drafter, prompt, seed>` is uncountable, any finite benchmark would still provide almost empty support.\n\nNevertheless, we remain eager to address all your concerns to justify an even higher score. Given our new extended benchmarks, the acceptance rate analysis, the independent HF benchmarks, and the wide adoption in real-world software libraries for several months, what additional configurations could significantly improve the paper? We will do our best to accommodate specific requests within our limited budget toward a camera-ready version.\n\n### 3. Choosing Drafters or Methods is Trivial\n\nIn response to your request for “heuristics”, please note:\n- Table 2 reports the **exact expected acceptance rate** for each method, which—combined with the ratio of forward latency among the models—governs the overall efficiency, as analyzed in [1].\n- Our ‘Limitations’ section discusses at length the interplay between acceptance rates, forward latencies, and speedups.\n\nWhat does “heuristic” mean in this context? We always need to select drafters with the maximum acceptance rate and minimum forward latency.\n\n---\n\nWe truly value your input; your comments have already led to meaningful improvements in our experiments and exposition. **We sincerely appreciate your openness to raising your score in light of new experimental results, practical adoption by Hugging Face, and our explanations**.\n\n---\n\n[1]: arxiv.org/abs/2405.14105, ICLR ’25\n\n[2]: arxiv.org/abs/2211.17192, ICML ’23", "claims_and_evidence": "-", "methods_and_evaluation_criteria": "The evaluation criteria (speedup for different draft/target configurations) make sense.", "theoretical_claims": "The exposition is rigorous, the algorithms are well motivated and the lossless-ness is proved.", "experimental_designs_or_analyses": "The authors also do a good job of showing specific examples and failure models of naive solutions, and coming up with several new methods.\n\nHowever:\n\n* For Algorithm 4, it would be nice to provide some example of the size of the intersection between some common tokenizers/vocabulary, to get a better sense of its usefulness\n* The experiment section is somewhat lacking. The results are only computed for 30 prompt, which is really not much. I believe larger scales experiments are requirements, with more prompts/more seeds. Additionally, the speedups for most of the combinations in Table 1 either non-existent or not really impressive. \n* There is also little explanation for why one drafter or one method would be better than another. It would be nice to see at least some heuristic to understand this better.", "relation_to_broader_scientific_literature": "The contributions are, to my knowledge, novel and relevant in relation to the literature.", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "The paper is very clear and well written.", "other_comments_or_suggestions": "I am open to raising my score in light of some additional experimental results and explanations.", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K4xA0fIMyc", "reviewer": "Reviewer_a7E7", "summary": "This work proposes three methods for using a draft model with a different vocabulary than the target model in a typical speculative decoding framework. The authors propose: 1) string level exact matching (SLEM) in which the draft tokens are decoded back into string representations and reencoded by the target model tokenizer, 2) string level rejection sampling (SLRM) which modifies the above by including rejection sampling at the string level, and 3) token-level intersection (TLI) in which a modified draft vocabulary is sampled is generated as the intersection of target and original draft vocabulary, enabling more typical token-level verification from a subset of the original drafter vocabulary.  The authors explore numerous nuances and challenges that heterogeneous vocabularies introduce such as non-injective tokenizers, KV-cache considerations, lookahead controls which reduce unnecessary forward passes of the draft model. A small empirical study is conducted which compares autoregressive decoding to standard homogeneous SD and heterogeneous SD using SLEM and TLI.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are so grateful for your solid endorsement, rating our paper with the **highest score of 5 out of 5**! We are particularly thankful for your insightful acknowledgment of this work as a significant breakthrough:\n>“I am not aware of any other work that has tackled the heterogeneous vocabulary problem in SD … as such consider this work **seminal**.”\n\nWe deeply appreciate your thoughtful recognition of our **“well written,” “important and timely,” “novel and effective solution” to a “big drawback when trying to use speculative decoding in practice.”** We also thank you for contributing a knowledgeable example of a real-world use case from your clearly strong hands-on experience, highlighting the importance of our solutions to the field-wide, genuine pain of practitioners applying speculative decoding:\n>“The challenge of producing bespoke draft models for each new potential target model is a big drawback when trying to use speculative decoding in practice. Some model families have natural draft candidates, such as Qwen2.5-0.5B for instance. However, even in this case the vocabulary for Qwen2.5-72B actually differs slightly from 0.5B (token IDs aligned but different size vocab.), highlighting the challenges of naively applying SD. Further, many organizations relying on SD may not have the necessary expertise, data, or compute to pretrain their own draft model or drafting heads.”\n\nWe also thank you for reviewing our proofs and affirming their correctness. We truly appreciate your careful reading and for bringing to our attention some typos and suggested improvements in presentation, which have already helped improve the paper.\n\n## A1. New Extended Benchmarks of SLEM and TLI\nIndependently of our benchmarks, Hugging Face’s core maintainers have thoroughly evaluated the effectiveness of SLEM and TLI (Algorithms 2 and 4) and found our methods to be the most effective among all the speculative decoding algorithms they currently support. As a result, they made SLEM and TLI the default in Transformers (in Oct ’24 and Feb ’25, respectively), powering 5,000 other libraries with various use cases and hardware setups.\n\nTo facilitate additional standardized benchmarks, we have open-sourced our benchmarking repository, which provides full reproducibility so anyone can compare our methods and any future alternatives on *exactly the same inputs and hardware*. We will attach a link to this repository upon publication.\n\nFurthermore, here are 2 extended benchmarks of SLEM and TLI, suggesting **up to 2.1× and 1.69× speedups** on various hardware setups: https://imgur.com/a/speculative-decoding-heterogeneous-vocabularies-extended-benchmark-of-algorithms-2-4-uV4PrTR (anon.)\n\n## A2. Integrating SLEM and TLI into vLLM\nThank you so much for your interest in integrating our algorithms into vLLM! Since SLEM and TLI have become the default of Hugging Face Transformers, we have received a lot of interest from users experiencing this pain who have asked about integrating them into vLLM.\n\nThanks to vLLM’s support in disaggregated prefilling, the repeated process of SLEM is nonblocking and therefore should remain effective in both multi-tenancy and high query per second settings. Asynchronous tokenization is expected to increase the throughput in such setups.\n\nWe do not see any theoretical constraints that would limit integration in vLLM or similar inference engines, nor do we see any major engineering gaps. In fact, we believe that vLLM will eventually support speculative decoding for heterogeneous vocabularies using these algorithms or future alternatives.\n\n## A3. Implementation Details\nThanks so much for your interest in SLEM’s implementation! The supplementary materials include the code we contributed to HF Transformers, which aligns with their naming conventions. Some naming differences exist, such as in the lookbehind logic of SLEM. The core logic is in the *AssistedCandidateGeneratorDifferentTokenizers* class, with the lookbehind mechanism implemented via a *diagonal matrix* referenced throughout the code. Helper functions like *_get_tokens_diag* appear only by signature and docstring. The full implementation is available on the *main* branch of HF Transformers.\n\nRegarding SpecBench, please note that while the implementations of SLEM and TLI allow homogeneous drafters, our primary focus is on heterogeneous drafters, in contrast to SpecBench, which benchmarks methods constrained to homogeneous drafters or self-speculation. Homogeneous methods are not applicable when the target lacks a model family (e.g., phi-4, Mixtral-8x22B). Also, homogeneous methods are ineffective if the smallest model in the family is still too slow, further limiting their applicability (e.g., see Figure 2-a in [1]). Some of the remaining methods in SpecBench are supported by HF Transformers and therefore were benchmarked in their independent experiments (see Section 1 above).\n\n---\n\nThank you for your support and feedback!\n\n[1]: arxiv.org/abs/2405.14105, ICLR ’25", "claims_and_evidence": "Yes, in general the claims made are well supported by the discussion, illustrative examples, and proofs.", "methods_and_evaluation_criteria": "Yes, the methods, datasets, and evaluation criteria used are generally standard. One area for improvement would be to include a standardized SD dataset such as SpecBench [1].\n[1] https://github.com/hemingkx/Spec-Bench", "theoretical_claims": "I briefly reviewed the proofs and they appear to be accurate.", "experimental_designs_or_analyses": "No issues noted. The experiments appear to be valid.", "relation_to_broader_scientific_literature": "The challenge of producing bespoke draft models for each new potential target model is a big drawback when trying to use speculative decoding in practice. Some model families have natural draft candidates, such as Qwen2.5-0.5B for instance. However, even in this case the vocabulary for Qwen2.5-72B actually differs slightly from 0.5B (token IDs aligned but different size vocab.), highlighting the challenges of naively applying SD. Further, many organizations relying on SD may not have the necessary expertise, data, or compute to pretrain their own draft model or drafting heads. The proposed solutions and analysis in this work offer a unique, novel, and effective solution to these challenges. I am not aware of any other work that has tackled the heterogenous vocabulary problem in SD and as such consider this work seminal.", "essential_references_not_discussed": "None noted.", "other_strengths_and_weaknesses": "## Strengths\n* Important and timely topic.\n* Original and novel approach to a practical challenge of implementing SD in practice. \n* Well written\n* Illustrative examples included in text\n* Several target / draft pairs and datasets considered. \n* Throughput increases are competitive with homogenous drafters. \n\n## Weaknesses\n* Additional figures to highlight the overall methods may be beneficial to the reader. \n* Some select terms appear in text before definition, eg., lookahead value. \n* No error bars / statistical analysis conducted on empirical results. \n* “30 prompts” from the datasets used for Table 1 is somewhat informal and would be hard to reproduce. It would be best to use a standardized benchmark such as SpecBench. \n* Additional discussion on the overhead for the SLEM method would be helpful. While we see throughput gains here I wonder about integration with more sophisticated inference engines such as vLLM. Could repeated tokenization/decoding block GPU in multi-tenant or high query per second settings?", "other_comments_or_suggestions": "* Algorithm 3 L6-8 could benefit from indentation or endif statements to clarify the conditional branch flow. \n* Table 3: Consider adding “small vocabulary” to SLRS. \n* L102: “draft token However”\n* Suggest highlighting homogenous drafters in results as it’s not always clear which models share a vocab.", "questions_for_authors": "1. In my review of the supplementary materials I did not find the implementation for non-injective tokenizer “look behind”. Please confirm which section of the SM we can find this. \n2. What are some challenges that may be encountered when implementing SLEM for vLLM or other inference engines which rely on asynchronous tokenization on CPU? Has any analysis been conducted on applying your proposed methods for multi-tenant or high query per second settings?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses a limitation of speculative decoding (SD) for large language models—namely, the assumption that the drafter and target model must share the same vocabulary. The authors introduce three lossless, training-free SD algorithms—SLEM, SLRS, and TLI—that decouple vocabulary requirements and maintain correctness of the target model’s output distribution. These methods offer varying trade-offs between theoretical optimality and practical speedup, and are applicable with off-the-shelf models and existing inference engines. The paper is well-motivated, technically solid, and shows clear potential for impact, both theoretically and practically.

A notable strength is the paper's real-world relevance and adoption: two of the proposed methods (SLEM and TLI) are already implemented as defaults in Hugging Face Transformers. The paper also provides provable guarantees and empirical evaluations across multiple LLMs. 

Concerns:

- Reviewer 8FKT raised a concern that SLRS, while theoretically elegant, is currently too costly to deploy, and its utility remains largely conceptual.

- Reviewer 7xEY requests larger-scale benchmarks and more insight into when methods are effective.

These concerns are mostly satisfactorily addressed during rebuttal. 

**Recommendation**. This paper is a strong example of research that combines theoretical insight with real-world relevance. It addresses a timely problem in LLM inference, removes a critical limitation in a widely used technique, and offers solutions that are both elegant and already influential in practice. I recommend acceptance.
Decision: Accept (oral)