Speculative decoding speeds up large language models by letting a cheap "drafter" guess several tokens ahead and having the big model check all the guesses in one parallel pass. Every accepted guess saves one slow sequential step. The check is strictly left to right. When the first guessed token is wrong, everything after it is thrown away. In languages such as Hindi, Turkish, Korean or German, case endings rather than position mark who did what to whom. A drafter can therefore guess the right words in a different but equally grammatical order: object before subject, say, where the big model prefers subject before object. Today the whole draft is discarded on the first word. Yet the subject phrase and the verb the drafter produced are often exactly what the big model emits two or three steps later.
We propose to stop throwing that work away while keeping speculative decoding exact, meaning the output is the same as plain decoding. When a draft is rejected, we cut it into phrase-sized chunks at case-marker and postposition boundaries and keep those chunks in a small pool. In later steps, we offer them as extra branches in the draft tree at the next phrase boundary. The big model verifies them like any other candidate, so the output distribution is unchanged. The bet is that in free-word-order languages a large share of rejections are order misses rather than word misses. If so, recycled phrases will raise the number of tokens accepted per step, and the gain should grow with how freely a language orders its constituents.
Core Claim
Our first claim is diagnostic. A measurable fraction of speculative rejections in morphologically rich target languages are order misses. We define an order miss as a rejected drafted phrase that reappears verbatim in the big model's output within the same clause, at a later position. Our second claim is that recycling those phrases as tree branches recovers acceptance length at a fixed budget of tree nodes. The third claim is a specific, falsifiable prediction: the recovered speedup increases with the word-order entropy of the target language and is close to zero for English. This mirrors the finding of CSSL that order-invariance training helps scrambling languages but gives no significant gain on English.
The contribution differs from prior speculative decoding work in where it looks for candidates. It mines them from the system's own rejected drafts, segmented by morphology, rather than from a drafter's forward guesses. It does not touch the acceptance rule.
Positioning
The speculative decoding side supplies the method. Blockwise Parallel Decoding introduced the draft-and-back-off loop with exact equivalence to greedy decoding. The speculative decoding survey catalogs drafter families and reports translation as the task with the lowest speedups on Spec-Bench. That observation motivates this work. Medusa adds prediction heads at fixed offsets and verifies a tree of candidates with a tree attention mask; we reuse that verification machinery. Graph-Structured Speculative Decoding merges branches that share identical token runs into a shared graph. It is the closest existing idea, since it also exploits redundancy among drafts. It differs from ours in two ways. It only merges identical sequences within one draft tree at the same step, and it has no notion of a phrase that moved. We carry phrases across steps, after rejection, to new positions. For sampling rather than greedy decoding, tree Monte Carlo speculative sampling shows that unbiased verification over candidate trees is possible. Recycled branches are just additional tree nodes, so exactness carries over.
Two papers constrain the design. Yi et al. show that drafters trained on English collapse on other languages, and that specialized, self-distilled small drafters fix much of this. They also find that the input language matters more than the output language. That could mean multilingual rejections are mostly comprehension failures, not order misses, which would undercut us. We take it head on: the diagnostic in our first experiment measures the order-miss share directly, and a low share kills the project. Yi et al. further found that a 1B drafter was slower than a 68M one because of memory contention. This rules out "just make the drafter bigger" and pushes us toward a mechanism that costs almost nothing to draft. Recycling only touches a pool of previously drafted tokens. Grammar-Aligned Decoding shows that grammar masking distorts the output distribution, and that its correction needs extensive sampling. That is why we leave verification untouched and inject syntax only on the proposal side, where it cannot bias outputs.
The parsing side supplies the linguistic lever and the evaluation axis. Sima'an and Tsarfaty and Arun and Keller show that models assuming stable linear adjacency break under scrambling. Ahrenberg's field grammar separates constituent identity from surface position. That is precisely the abstraction a recycled phrase pool needs: a constituent is a unit whose slot can vary. Universal Dependencies v2 gives us per-language morphological features to find case-marker boundaries cheaply. It also provides the treebanks from which we compute each language's word-order entropy.
Research Program
The work has three parts.
The first part is a rejection taxonomy. We run standard speculative decoding with a self-distilled specialized drafter in the style of Yi et al., then label every rejection. A rejection is an order miss if the rejected drafted span, of two or more tokens, appears in the big model's final output within the same sentence and within a window of later positions. It is a word miss otherwise. We report the order-miss share per language and its correlation with UD-derived order entropy. Order entropy is the entropy of the relative order of subject, object, oblique and verb dependents under their head.
The second part builds constituent recycling. After each verification step, the unaccepted suffix of the draft is segmented at phrase boundaries. Boundary cues are tokens whose UD features include a case value, plus postpositions and determiners. The cue inventory is a per-language lookup table extracted from UD training data, so no parser runs at inference time. The resulting chunks enter a pool and are dropped once emitted or after a fixed number of steps. When the accepted text reaches a phrase boundary, the system attaches the most recent pooled chunks as sibling branches beside the drafter's own continuation, within a fixed total node budget. Verification is the standard tree-masked pass. The greedy outputs are therefore identical to plain decoding, and the tree-sampling variant stays unbiased.
The third part is analysis. We look at how gains vary with order entropy, with node budget, and with serving batch size. The survey and MoE-Inference-Bench note that spare compute for verification shrinks as batches grow, and extra branches are not free.
Baselines
The naive reference point is plain autoregressive decoding, which defines a 1.0x speedup. It is also used to confirm token-for-token identity of greedy outputs for every method.
The strongest competitor is a language-specialized, self-distilled small drafter in the style of Yi et al.. It is the strongest because it already removes most of the language-mismatch penalty. Its reported result is a 2.42x speedup on WMT16 De-En, with acceptance length rising from 1.47 to 3.03 over a general drafter. We train it ourselves for each target language with the same data and tuning budget as our system. Recycling is then added on top of this exact drafter, so any gain is attributable to recycling alone.
The second strong competitor is Graph-Structured Speculative Decoding. It reports a 1.70x to 1.94x overall speedup across models, on a suite of tasks that includes WMT-14 En-De. We run it with the same drafter and the same node budget, because it is the existing method that also exploits redundancy among drafts. Medusa is included as the self-drafting reference, with heads trained on the same per-language data. Its fixed-offset heads give a natural contrast for displaced phrases.
Two ablations isolate the key ingredient. The first, n-gram recycling, pools rejected suffixes as fixed-length token windows and attaches them at every position, with no morphology. The second, random-boundary recycling, cuts chunks at random points with matched chunk lengths. Beating the strongest baseline means a statistically reliable increase in mean accepted tokens per step and in wall-clock speedup over the specialized drafter at equal node budget, on at least the high-entropy languages. Beating the ablations means that phrase-boundary segmentation, not mere reuse, accounts for a meaningful part of the gain.
Why not just…?
Why not just train the drafter on scrambled sentences, or make it order-invariant as CSSL does? Invariance is the wrong goal for a drafter. A drafter is rewarded for predicting the big model's particular order, not for treating all orders alike. Self-distillation in Yi et al. already pushes it toward that particular order. Permutation augmentation would, if anything, spread the drafter's probability across orders the big model will reject. We test this directly by training a drafter variant with a contrastive permutation objective modeled on CSSL. We expect it to lower acceptance relative to the self-distilled drafter.
Why not just use a larger drafter? Yi et al. found their 1B drafter slower end to end than a 68M one because of memory-bandwidth contention. A larger drafter may also simply learn the big model's order preferences better and close the gap we target. We include one larger drafter size and report the order-miss share it leaves behind. If that share falls to near zero, recycling is unnecessary at that scale, and we will say so.
Why not just keep a plain cache of rejected tokens and match n-grams? This is the real threat. Much of the benefit may come from reuse itself, with morphology adding little. The n-gram recycling ablation settles it. If it matches phrase-boundary recycling at equal node budget, we drop the linguistic segmentation. The contribution then reduces to the rejection taxonomy and a simple, language-agnostic recycling cache. Our reason for expecting a difference is that unsegmented windows waste tree nodes on fragments that straddle phrases and attach at positions where no phrase can begin. That waste should matter most when the node budget is small.
Why not just relax verification to accept a reordered phrase? That would change the model's output and abandon the exactness guarantee that makes speculative decoding safe to deploy. Grammar-Aligned Decoding shows how quickly distribution changes compound. We keep verification exact and leave lossy acceptance out of scope.
Proposed Experiments
The target model is a single multilingual instruction-tuned model, paired with 68M-scale per-language drafters. Tasks are translation out of English: WMT-14 En-De, where GSD's numbers give a reference, and the WMT16 De-En direction, which reproduces Yi et al.'s setting as a sanity check. We add English-to-Hindi, English-to-Turkish and English-to-Korean continuation and translation sets. These are built from sentences in the corresponding UD treebanks, since the file lists no standard speculative-decoding benchmark for these directions. English-target generation on Spec-Bench and MT-Bench serves as the fixed-order control. Metrics are mean accepted tokens per verification step, wall-clock speedup at batch sizes 1, 8 and 32, order-miss share, and an exact-match check of greedy outputs against plain decoding.
Two kill criteria are fixed in advance. The first concerns the diagnostic. If the order-miss share among rejections is small and does not rise with UD order entropy, the premise fails, and we stop and report the negative result, which would itself refine Yi et al.'s input-dominance finding. The second concerns the method. Recycling should raise accepted tokens per step over the specialized drafter on Turkish, Hindi and Korean, with a gain that increases with order entropy and a negligible gain on English. If the English gain is as large as the scrambling-language gain, the mechanism is generic reuse, not word-order recovery, and the n-gram ablation becomes the honest headline. A final check at batch 32 tells us whether the extra branches still pay for themselves once spare verification compute shrinks.
References
- CSSL: Contrastive Self-Supervised Learning for Dependency Parsing on Relatively Free Word Ordered and Morphologically Rich Low Resource Languages
- Blockwise Parallel Decoding for Deep Autoregressive Models
- Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding
- Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads
- Graph-Structured Speculative Decoding
- Accelerated Speculative Sampling Based on Tree Monte Carlo
- Towards Fast Multilingual LLM Inference: Speculative Decoding and Specialized Drafters
- Grammar-Aligned Decoding
- Three-Dimensional Parametrization for Parsing Morphologically Rich Languages
- Lexicalization in Crosslinguistic Probabilistic Parsing: The Case of French
- A Grammar Combining Phrase Structure and Field Structure
- Universal Dependencies v2: An Evergrowing Multilingual Treebank Collection
- MoE-Inference-Bench: Performance Evaluation of Mixture of Expert Large Language and Vision Models