{"id":"f4ac3a64-42e4-491a-87dd-9f01086cfec5","arxiv_id":"2502.05202","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Three lossless speculative decoding algorithms (SLEM, TLI, SLRS) remove the shared-vocabulary constraint, enabling any off-the-shelf model to serve as a drafter for LLM acceleration.","lead":"This paper introduces three speculative decoding methods that let a small 'drafter' model with a different vocabulary accelerate a large LLM, without changing the output distribution. The methods are integrated into Hugging Face Transformers and show up to 2.8x throughput gains over autoregressive decoding.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SLEM's Section 3.2 alignment heuristic for non-injective tokenizers is unproven and can break the exact-match coupling that losslessness relies on, so the central 'all three methods preserve the target distribution' claim rests on an unvalidated patch.","rationale":"The reader's weakest-assumption identification is exactly right: Algorithm 2's losslessness for real heterogeneous pairs hinges on the Section 3.2 alignment heuristic, and the paper gives no proof for it. The clean algorithmic contributions are otherwise plausible: SLEM is lossless for injective tokenizers by exact-match coupling, TLI inherits soundness from standard speculative decoding, and SLRS has a valid rejection-sampling argument for fixed lookahead. The Hugging Face integration and the Table 1 results are real evidence of practical effectiveness, but adoption does not substitute for a distribution-preservation proof, especially when Table 11 shows that the benchmark drafter vicuna-68m is non-injective. Since the reader already assigned a conditional verdict with moderate confidence, and this concern matches that conditional status, no verdict change is needed. The concrete test would convert the concern into a definite finding: a toy enumeration can verify losslessness exactly, and a greedy-equality check on the vicuna-68m rows would show whether the heuristic changes outputs in practice.","tokens_in":1809,"tokens_out":851,"duration_ms":96226,"concrete_test":"Construct a toy pair of non-injective tokenizers (for example, a target tokenizer and a drafter tokenizer whose normalizers collapse repeated spaces) with vocabularies satisfying T↠D* and D*↠T*, and a small target model with known next-token distributions. Exhaustively enumerate all reachable states, draft sequences, and target samples for short continuations, and compute the exact output-token distribution of Algorithm 2 with the Section 3.2 alignment patch. Compare it to the target's autoregressive distribution; any state with unequal probabilities settles whether the heuristic is lossless.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's strongest claim is that all three algorithms are lossless, and the headline speedups are dominated by SLEM (Algorithm 2). For injective tokenizers, SLEM is lossless by a coupling argument: lines 9-11 accept only tokens that the target model itself sampled, so accepted prefixes are exact target draws. Section 3.2, however, patches SLEM for non-injective tokenizers with a heuristic: after re-tokenizing the draft continuation into target tokens, it looks for the longest overlap between previously accepted target tokens and the new target-space sequence, then takes only the suffix beyond that overlap. This is not a formal part of Algorithm 2, and no theorem or proof shows that the resulting accepted tokens are still draws from the target distribution. The overlap search can merge, discard, or reorder tokens from the target's own sample, so the state fed into the next iteration need not be the target model's generated token sequence, destroying the coupling that makes exact matching lossless. Table 11 confirms vicuna-68m is non-injective, and vicuna-68m is used as a drafter in Tables 1, 2, 6, and 7, so the reported 2.8x speedups and the losslessness guarantee for real model pairs depend on this unvalidated heuristic. TLI inherits losslessness from standard speculative decoding, and SLRS with fixed lookahead has a valid rejection-sampling argument, so the gap is specific to the empirically most important algorithm. This is the single most load-bearing concern: it attacks the strongest stated claim in the configuration where the method is actually benchmarked.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes three speculative decoding algorithms that remove the shared-vocabulary constraint between drafter and target models: SLEM (Algorithm 2), which uses plain text as an intermediate representation and string-level exact matching; SLRS (Algorithm 3), which performs rejection sampling at the string level; and TLI (Algorithm 4), which reweights the drafter distribution onto the token-level intersection of the two vocabularies. The paper claims that all three methods are lossless, that they work with off-the-shelf models without training, and that SLEM and TLI yield speedups of up to 2.8x over autoregressive decoding. Theoretical results include Theorem 3.2 (SLRS losslessness), Theorem 3.1 (exact matching has lower acceptance than standard SD under identical distributions), Theorem 4.1 (TLI dominates the union-vocabulary baseline), and Lemma 3.1 on the exponential cost of computing psi(t). The empirical evaluation covers summarization, code generation, and long-context tasks across many model pairs and hardware settings, and the authors report that SLEM and TLI have been integrated into Hugging Face Transformers.","tokens_in":35136,"tokens_out":6258,"duration_ms":70706,"significance":"If the central claims hold, this is a practically useful contribution: it removes a real constraint of speculative decoding, enables off-the-shelf drafters with mismatched tokenizers, and the results are backed by an open-source implementation that has been adopted in a widely used library. The theoretical parts are mostly self-contained and do not fit parameters to reach conclusions; Theorem 4.1 and Theorem 3.2 are genuine, checkable statements. The main value is the SLEM algorithm, whose headline speedups of up to 2.8x come from non-standard model pairs. The main weakness is that the losslessness guarantee for SLEM is established only for injective tokenizers, while the paper claims losslessness for all tokenizers and evaluates SLEM with at least one non-injective tokenizer (vicuna-68m). This gap affects the load-bearing claim of the paper and needs to be resolved before the results can be accepted at face value.","major_comments":[{"comment":"The abstract and contribution list state that all three methods are lossless, but the losslessness of SLEM is only argued for injective tokenizers. Section 3.2 introduces a heuristic for non-injective tokenizers: the algorithm searches for the longest overlap between previously accepted target tokens and the newly re-tokenized draft sequence, then keeps only the suffix beyond that overlap. This procedure is not part of Algorithm 2's pseudocode, no formal statement is given for it, and no proof shows that the resulting accepted tokens are still draws from the target distribution. Table 11 reports that double7/vicuna-68m is non-injective, and vicuna-68m is used as a drafter in the SLEM speedup results in Tables 1 and 6 (e.g., the 2.1x Mixtral row). The overlap search can merge, drop, or reorder tokens relative to the target model's own sampled sequence, so the state fed to the next iteration need not be a prefix of a target-model draw, breaking the coupling on which exact-match losslessness relies. The authors should either formalize the alignment step as part of the algorithm and prove that it preserves the target distribution, or restrict the losslessness claim to injective tokenizers and adjust the empirical claims accordingly.","section":"Section 3.2, Algorithm 2, Tables 1 and 11"},{"comment":"Theorem 3.2 defines psi(t) with a fixed number of draft tokens i, namely as a sum over sequences d1,...,di. Algorithm 3, however, samples d1,...,d_i until a lookahead indicator S1(i) is satisfied, so the stopping time i is random and the distribution over stopped sequences is not described. The text asserts that 'Algorithm 3 and Theorem 3.2 both hold for this more general lookahead indicator function,' including the recommended early-stopping condition of stopping once the first target token is determined, but no statement or proof of this generalization is provided. The theorem should be restated for a random stopping rule, or the scope of the claimed losslessness should be limited to the fixed-lookahead case.","section":"Section 3.3, Theorem 3.2, Algorithm 3"},{"comment":"Lemma 3.1 counts the number of ways to partition the target token t into contiguous substrings and claims this equals the number of draft-token sequences with T(d1+...+di)_1 = t. This equality is not established for the actual tokenization function T, which uses longest-prefix matching. If the target vocabulary contains a token that extends t (for example, t='a' and the vocabulary also contains 'ab'), then a drafted string 'ab' is tokenized with first token 'ab', not 'a', so the condition T(d1+...+di)_1 = t is stricter than the composition count. The 2^{m-1} count is therefore not a proof of the stated claim unless additional conditions on T or on the target and draft vocabularies are imposed. If the lemma is intended only as an illustrative calculation for a specific complete-vocabulary setup, that should be stated precisely; as written, it overstates the generality of the exponential-count result.","section":"Section 3.4, Lemma 3.1, Appendix G"}],"minor_comments":[{"comment":"The abstract says 'our algorithms demonstrate significant speedups,' but only SLEM and TLI are evaluated empirically; SLRS is analyzed theoretically and in Section 3.4 is described as potentially impractical. The wording should be made precise, for example by saying SLEM and TLI demonstrate speedups while SLRS is a theoretical method with feasibility analysis.","section":"Abstract and Section 5"},{"comment":"The tables mix 'Tok/s' and 'T/s' for the same throughput quantity. The units should be unified, and the TPOT values in the phi-4 rows (e.g., '47' milliseconds) should be given with one decimal place for consistency with the other rows.","section":"Tables 1 and 6"},{"comment":"The expected acceptance rate for Algorithm 2 is written as P_t [p(t) * psi(t)], which is nonstandard notation for a sum over t in T. Please use an explicit summation, and clarify whether this is the expected acceptance of the first target token or the expected number of accepted tokens per iteration.","section":"Section 6, Table 3"},{"comment":"The claim that SLEM and TLI 'had become the default inference pipeline behavior' in Hugging Face Transformers is a strong external-validation claim. It would be helpful to cite the specific Hugging Face release notes or pull requests so that readers can verify the dates and the exact default behavior.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid engineering contribution with a plausible theoretical core, and the Hugging Face integration is a meaningful external signal. The main risk is the unproven alignment heuristic for non-injective tokenizers in SLEM, which is the algorithm behind the headline speedups. This is fixable within the manuscript's scope: either prove losslessness under explicit assumptions about the tokenizer, or narrow the claims to injective tokenizers and re-report which table entries remain valid. I do not see grounds for rejection, but the central claim as currently worded is not yet supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read on Timor et al. The three algorithms are a real step forward: they drop the shared-vocabulary requirement that has limited speculative decoding to in-family drafters, and the core ideas are sound. TLI is a simple re-normalization trick with a correct dominance proof over the union baseline. SLRS has a clean rejection-sampling theorem, and the authors are honest that computing psi(t) explodes combinatorially, so its practical use is limited to short-token drafters. SLEM's exact-match coupling for injective tokenizers is correct, and the Hugging Face integration is genuine external validation that these methods work in practice.\n\nThe main soft spot is the non-injective tokenizer handling in Section 3.2. The paper claims all three methods preserve the target distribution, but the alignment heuristic for non-injective tokenizers has no proof. For injective tokenizers, the coupling argument is airtight, but vicuna-68m is non-injective and is used in the benchmarks that produce the headline 2.8x speedups. The search for the longest overlap between previously accepted tokens and re-tokenized draft text can discard, merge, or reorder tokens that the target model actually sampled, so the next iteration's state need not be a target-sample prefix. The losslessness claim for SLEM in that configuration is therefore unproven. This is not a manufactured nitpick; it is the empirically dominant algorithm in the paper.\n\nLesser issues: the speedups are averaged over 30 prompts without error bars, and the variance is visible in the tables, with several configurations below 1.0x. That is a reporting weakness, not a fatal flaw. The self-citations to Timor et al. provide context for drafter-acceptance tradeoffs, which is a legitimate use.\n\nOverall, the paper is worth serious referee time. The injective case is proven and novel, TLI is solid, and the practical impact via Hugging Face is real. The referees should push the authors to either prove the non-injective alignment is lossless or qualify the claim to injective tokenizers and rerun the vicuna-68m benchmarks under that qualification.","headline":"Useful, well-theorized paper on heterogeneous-vocabulary speculative decoding, but the losslessness claim overreaches for non-injective tokenizers.","tokens_in":35708,"tokens_out":1596,"would_cite":true,"duration_ms":20397,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Speculative decoding can now work with models that use different token vocabularies.","keywords":["speculative decoding","heterogeneous vocabularies","lossless inference","string-level exact match","token-level intersection","rejection sampling","LLM inference acceleration"],"falsifier":"Run SLEM with a non-injective tokenizer pair, generate a large output sample, and perform a two-sample test comparing the distribution of output strings to autoregressive decoding on the same prompt distribution; if the distributions differ significantly, the losslessness claim for SLEM on such tokenizers fails. A cheaper test is to count whether the longest-stretch realignment ever changes the accepted token sequence in a way that the target model's own re-tokenization would not produce.","tokens_in":34618,"feed_emoji":"⚡","tokens_out":1586,"duration_ms":18394,"temperature":0.7,"pith_summary":"This paper claims to remove a key constraint of speculative decoding: the drafter and target models no longer need to share the same token vocabulary. The authors propose three decoding algorithms that let any off-the-shelf language model act as a drafter for any other model, without retraining or modifying either model, while provably preserving the target model's output distribution. They report speedups of up to 2.8x over standard autoregressive decoding on summarization, coding, and long-context tasks. If correct, this means faster inference for many model pairs that previously could not use speculative decoding at all.","feed_headline":"Speculative decoding now works across different token vocabularies","feed_subtitle":"Three lossless algorithms let any off-the-shelf model act as a drafter, with speedups up to 2.8x.","key_machinery":"The central object is a string-level translation of token sequences between two vocabularies. Given a draft vocabulary D and target vocabulary T, the paper defines expressibility and tokenization with respect to a vocabulary, then uses plain text as the shared representation. For SLEM, the key mechanism is exact matching after re-tokenizing draft text with the target tokenizer. For SLRS, the key identity is the acceptance probability function ψ(t), defined as the sum of draft-sequence probabilities whose tokenized concatenation starts with target token t; the proof that the algorithm is lossless relies on this function. For TLI, the key mechanism is projecting the drafter's distribution onto the vocabulary intersection and renormalizing, which the paper proves yields an acceptance rate at least as high as for a union-vocabulary projection.","core_discovery":"The paper's central claim is that speculative decoding can be made to work with heterogeneous vocabularies, where the draft and target models tokenize text differently. The first method, String-Level Exact Match (SLEM), uses plain text as a shared intermediate: draft tokens are decoded to text, re-tokenized with the target vocabulary, and then verified by exact string matching. The second method, Token-Level Intersection (TLI), renormalizes the drafter's distribution over the intersection of the two vocabularies and applies standard rejection sampling. The third, String-Level Rejection Sampling (SLRS), extends rejection sampling to the string level and is proved lossless via a new acceptance probability function. The paper proves losslessness for all three and proves that TLI has an acceptance rate at least as high as a naive union-vocabulary approach. On real model pairs, SLEM and TLI yield reported speedups over autoregressive decoding, and the paper emphasizes that both algorithms were integrated into a widely used inference library.","pith_inferences":["The paper's acceptance-rate analysis suggests that, for a given drafter-target pair, the best algorithm could be selected by comparing measured acceptance rates under SLEM, TLI, and SLRS; the paper leaves this algorithm-selection question implicit.","Because TLI relies on the intersection of vocabularies, it behaves like standard speculative decoding with a restricted drafter distribution; for pairs with small intersections, one might predict that SLEM, which can accept strings spanning multiple target tokens, would outperform TLI, though the paper does not make this comparison explicit.","A testable extension is measuring whether SLEM's realignment heuristic for non-injective tokenizers preserves the target distribution on a carefully designed corpus of strings that trigger normalization mismatches; the paper does not provide such a test.","The exponential growth of ψ(t) with token length, shown for real vocabularies, suggests that hybrid or approximate computations of ψ(t) could make SLRS viable for larger vocabularies; the paper leaves this as future work."],"forward_implications":["Any off-the-shelf model can serve as a drafter, including small models with different tokenizers, so users no longer need to train a drafter from scratch or restrict themselves to in-family drafters.","For target models that lack a same-vocabulary drafter, heterogeneous speculative decoding provides an acceleration path that standard speculative decoding cannot.","Faster and cheaper LLM inference could lower serving costs and enable lower-latency applications with models that were previously not amenable to speculative decoding.","The losslessness guarantees mean the output distribution of the target model is preserved, so the acceleration should not introduce output-quality regressions compared to autoregressive decoding.","The paper's analysis of ψ(t) shows that string-level rejection sampling is practical only for drafters with short tokens or compact vocabularies, narrowing its use case relative to SLEM and TLI."],"supporting_citations":[{"why":"Provides the standard speculative decoding algorithm and its rejection sampling verification method, which all three heterogeneous algorithms extend and whose losslessness guarantee is reused.","marker":"Leviathan et al., 2023"},{"why":"Co-originates the standard speculative decoding verification method that TLI directly employs and that SLRS generalizes to the string level.","marker":"Chen et al., 2023"},{"why":"Supplies the block-level draft verification method that the paper notes is nontrivial to generalize to heterogeneous vocabularies.","marker":"Sun et al., 2024"},{"why":"Provides the analysis of how drafter speed and acceptance rate determine speculative decoding speedups, which motivates the empirical performance requirements for the proposed algorithms.","marker":"Timor et al., 2025"},{"why":"Supplies the controller-based lookahead mechanism that the paper suggests could be adapted for SLRS lookahead decisions.","marker":"Mamou et al., 2024"},{"why":"Identifies the Hugging Face Transformers library into which the paper reports SLEM and TLI were integrated and whose tokenizers are used in the injectivity experiments.","marker":"Wolf et al., 2020"},{"why":"Describes BPE, one of the tokenization methods the paper relies on to argue that real vocabularies typically satisfy the expressibility constraints.","marker":"Sennrich et al., 2016"},{"why":"Describes SentencePiece, used in the injectivity experiment and cited in the discussion of tokenizer construction.","marker":"Kudo & Richardson, 2018"},{"why":"Provides the CNN-DailyMail summarization dataset used for the injectivity test and one of the three benchmark task datasets.","marker":"Nallapati et al., 2016b"},{"why":"Provides the HumanEval coding benchmark used for the programming-task speedup evaluations.","marker":"Chen et al., 2021"}],"fun_headline_variants":["Speculative decoding works across different tokenizers","Lossless speculative decoding with mismatched vocabularies","Any off-the-shelf LLM can now serve as a drafter","Three lossless methods for speculative decoding across vocabularies","Use any LLM as drafter with lossless spec decoding"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The alignment heuristic for non-injective tokenizers in SLEM preserves the target distribution, but the paper does not prove this.","fun_headline_variants_meta":{"raw":{"variants":["Speculative decoding works across different tokenizers","Lossless speculative decoding with mismatched vocabularies","Any off-the-shelf LLM can now serve as a drafter","Three lossless methods for speculative decoding across vocabularies","Use any LLM as drafter with lossless spec decoding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000668,"raw_usage":{"total_tokens":3040,"prompt_tokens":929,"completion_tokens":2111,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":2030}},"tokens_in":545,"tokens_out":2111,"duration_ms":14846,"temperature":1.0,"reasoning_tokens":2030,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T20:07:07.307231+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SLEM with a non-injective tokenizer pair, generate a large output sample, and perform a two-sample test comparing the distribution of output strings to autoregressive decoding on the same prompt distribution; if the distributions differ significantly, the losslessness claim for SLEM on such tokenizers fails. A cheaper test is to count whether the longest-stretch realignment ever changes the accepted token sequence in a way that the target model's own re-tokenization would not produce.","supporting_citations":[],"review_version":1}