Draft sources: draft models, n-gram, suffix decoding

§6.2 proved that any draft distribution $q$ leaves the emitted distribution exactly equal to the target's $p$, and reduced the whole economics to one expression: speedup $= E(\alpha,\kappa)/(1+\kappa c)$, with $E = (1-\alpha^{\kappa+1})/(1-\alpha)$, $\alpha$ the per-token acceptance rate and $c$ the cost of one draft step relative to one target step. It then spent its time on the verifier. This chapter is about the other half of that fraction — where $q$ comes from.

As of a556f3f, vLLM's method literal names nine entries — which resolve to thirteen distinct methods once the aliases collapse (§6.6 inventories all of them) — behind that one sampler:

SpeculativeMethod = Literal[
    "ngram",
    "medusa",
    "mlp_speculator",
    "draft_model",
    "suffix",
    "custom_class",
    EagleModelTypes,
    NgramGPUTypes,
    DSparkModelTypes,
]
RejectionSampleMethod = Literal["standard", "synthetic", "block"]

Four of those — ngram, ngram_gpu, suffix, and draft_model — are this chapter's. The EAGLE family and MTP, which draft from the target's own hidden states, belong to §6.4; DSpark, DFlash and the rest of SGLang's zoo to §6.6.

The concrete symptom that makes this a real decision rather than a taxonomy: on a summarisation or code-edit workload, a matcher that costs zero GPU time routinely beats a trained 1B draft model, and on open-ended chat it produces nothing at all — not a smaller speedup, nothing, because there is no repeated span to match. The same two configs swap places when the target grows from 8B to 70B. Neither $\alpha$ nor $c$ alone tells you which. The pair does.

Every draft source is a point on the $(\alpha, c)$ plane. $c$ you can derive from first principles before you own the hardware: in the memory-bound regime it is a ratio of streamed bytes. $\alpha$ you cannot — it depends on the model, the workload, and the temperature, and it is the one number in this chapter that must be measured. So the useful picture is not a scoreboard of speedups; it is the plane with each source's derivable $c$ fixed and its $\alpha$ left free, crossed by the contours of equal speedup.

Fix $\kappa$. The set of $(\alpha, c)$ pairs that deliver the same speedup $s$ is

Two contours matter. $s = 1$ is the break-even against not speculating at all: anything below that curve is a net win. And the contour through the point where your draft model actually sits is the indifference curve — the locus of free drafts that are worth exactly as much as that draft model. Where it crosses $c = 0$ is the acceptance rate a zero-cost matcher needs to tie.

Read the figure as a sentence: a matcher that is right 43% of the time is worth as much as a 1B draft model that is right 70% of the time, when the target is 8B — and the bar rises to 67% when the target is 70B. The bar moves because $c$ moves, and $c$ moves because it is approximated by a parameter ratio under the following assumptions.

If target and draft are both weight-bandwidth-bound, use the same precision and achieve equal bandwidth, streamed weight bytes give an approximate cost ratio:

where $N^{\text{stream}}$ counts parameters actually read per token — every matmul weight plus the output head, but not the input embedding table, which is gathered. Under tensor parallelism of the same degree their ideal shard factors cancel. Actual c can differ because of KV traffic, small-GEMM efficiency, collectives and launch costs. vLLM validates TP compatibility:

    def _raise_if_draft_tp_mismatch(self):
        # Note(Tomas Ruiz) If we run the target model with TP > 1 and
        # the draft model with TP = 1, then the different TP ranks collide.
        # Specifically when all ranks compile the draft model on rank 0
        # (because TP=1), then the torch compile cache is overwritten and corrupted.
        # We need a mechanism like this: https://github.com/vllm-project/vllm/pull/5414
        # To prevent this error, we assert that both TP sizes must be the same.
        spec_cfg = self.speculative_config
        tgt_tp = spec_cfg.target_parallel_config.tensor_parallel_size
        draft_tp = spec_cfg.draft_parallel_config.tensor_parallel_size
        if draft_tp != tgt_tp:
            raise ValueError(
                f"Currently, 'draft_tensor_parallel_size' and 'tensor_parallel_size' "
                f"must be the same. Got {draft_tp} and {tgt_tp}. "
                "Please pass 'draft_tensor_parallel_size' in the speculative_config."
            )

Llama-3.2-1B drafting Llama-3-70B

Llama-3-70B: $L=80$, $d=8192$, $h=64$, $h_{kv}=8$, $d_h=128$, FFN 28,672, vocab 128,256. Per layer that is $2 \times 8192^2$ for Q and O, $2 \times 8192 \times 1024$ for K and V, and $3 \times 8192 \times 28672$ for the gated MLP — 855.6 M parameters. Times 80 layers is 68.451 B, plus a $128{,}256 \times 8192 = 1.051$ B output head: 69.502 B streamed, 139.0 GB in bf16. On four H100s that is 34.75 GB per GPU and a decode floor of $34.75/3350 = 10.37$ ms at batch 1 — 96 tokens per second. Derived.

Llama-3.2-1B ($L=16$, $d=2048$, $h=32$, $h_{kv}=8$, $d_h=64$, FFN 8192, tied embeddings) streams 1.236 B as computed in §6.2. So

A ninefold change in $c$ from one target swap, with the draft untouched. At $\kappa=3$ and an illustrative $\alpha = 0.70$, speedup goes from $2.533/1.495 = 1.69\times$ on the 8B target to $2.533/1.053 = 2.40\times$ on the 70B one. Solving $E(\alpha,3) = 2.4047$ for the free-draft tie gives $\alpha^{\dagger} = 0.666$; at $\kappa=5$ it is 0.661, at $\kappa=7$ it is 0.654. Against the 70B target the indifference threshold is nearly flat in $\kappa$ — because $c$ is small enough that the cost term $1+\kappa c$ barely moves. That flatness is a property of small $c$, not of the formula: repeat the solve at $c = 0.165$ and $\alpha^{\dagger}$ falls from 0.459 at $\kappa=1$ to 0.430 at $\kappa=3$ to 0.314 at $\kappa=7$, because there the cost term more than doubles across that range while $E$ saturates. Derived; recompute it yourself in Exercise 2.

The memory the draft takes before it drafts anything

$c$ is only the time term. The draft model also has weights and a KV cache, and in vLLM its attention layers join the same paged pool as the target's — the proposer looks itself up in the target's already-built kv_cache_config rather than allocating its own:

        # Find which kv_cache_group the draft layers belong to
        self.validate_same_kv_cache_group(kv_cache_config)
        kv_cache_spec = None
        for gid, group in enumerate(kv_cache_config.kv_cache_groups):
            if self._draft_attn_layer_names & set(group.layer_names):
                self.kv_cache_gid = gid
                kv_cache_spec = group.kv_cache_spec
                break

Price it. Llama-3-70B on 4×H100 at gpu_memory_utilization=0.9. An “80 GB” H100 is 79.65 GiB — not 80 GiB, and not 80×10⁹ bytes (§2.1) — so the budget is 71.69 GiB per GPU, minus 32.85 GiB of weight shard — the whole 70.55 B-parameter checkpoint, which is the 69.50 B streamed above plus the 1.05 B input embedding table that is resident but gathered rather than streamed — minus roughly 2 GiB of activations and workspace, leaves a 36.83 GiB KV pool per GPU — 147.3 GiB aggregate. Per token the target's KV is $2 \times 80 \times 8 \times 128 \times 2 = 320$ KiB, so the pool holds 482,772 tokens, or 58 sequences at 8k context.

Add the draft. Its weights are 2.30 GiB, 0.575 GiB per shard, straight off the KV pool. Its KV is $2 \times 16 \times 8 \times 64 \times 2 = 32$ KiB per token — 10% on top of every token you cache. The pool becomes 145.0 GiB holding 352 KiB tokens: 432,026 tokens, 52 sequences, a 10.3% loss of integer request concurrency. The unrounded token-capacity loss is about 10.5%. Derived. This precedes per-step drafting slot reservation, and before you have measured a single acceptance. A zero-parameter draft source costs exactly none of it.

The n-gram proposer takes the last $n$ tokens of prompt-plus-generation, finds an earlier occurrence of that same $n$-gram in the same sequence, and proposes whatever followed it. No weights, no GPU, no distribution — the rejection sampler treats $q$ as one-hot, which §6.2 showed degenerates the accept test to "accept the drafted token with its own target probability".

Why does this work at all? Because for a large class of production traffic the output is mostly a copy of the input. Summarise this document: the summary quotes it. Retrieval-augmented QA: the answer restates retrieved spans, including names and numbers that a 1B draft model would never guess. Code editing: the model reprints the function it is modifying with three tokens changed. Agentic loops and RL rollouts: the same tool-call scaffolding, over and over. In all of these there is a literal earlier occurrence of the current suffix, and the matcher finds it. On open-ended generation — write me a poem — there is not, and $\alpha$ collapses to whatever the model's own repetitiveness gives you, which is close to nothing.

The matcher, read

vLLM's is numba-JIT'd KMP. It does not scan for a fixed $n$; it finds the longest suffix match from prompt_lookup_min through prompt_lookup_max in one linear pass, by reversing the sequence and running the failure function:

    """
    Find the longest n-gram which matches the suffix of the given tokens
    whose length is within [min_ngram, max_ngram] (inclusive).

    If found, we will extract k right after the matched ngram.
    """
# ...
    # Flip tokens, and the goal become to find longest ngram
    # on the rightmost position which matches the prefix with
    # length [min_n, max_n] (inclusive).
    tokens = origin_tokens[::-1]

    # Longest prefix (not including itself) which is a suffix of
    # the current position.
    #   lps[i] = max{v, where tokens[0:v] == tokens[i+1-v:i+1]}
    #
    # As ngram is capped by max_ngram to save memory, we only need to
    # store lps for the first max_ngram prefix.
    lps = np.zeros(max_ngram, dtype=np.int32)

One detail contradicts the folklore. "Prompt lookup" is usually described as finding the most recent occurrence. This implementation deliberately does the opposite:

            # Check if we found a longer valid ngram.
            #
            # Update position when longest_ngram matched prev_lps,
            # as we want to get the target n-gram of the earliest position
            # in the original tokens (i.e.
            # latest position in the reversed tokens)
            if prev_lps >= longest_ngram:
                longest_ngram = prev_lps
                position = i

The >= keeps overwriting position with later indices in the reversed array, which are earlier indices in the original. The GPU implementation makes the same choice with a different mechanism — torch.argmax over the match indicator returns the first true — and says so: "Searches for the earliest prior occurrence of the trailing n-gram" (vllm/v1/spec_decode/ngram_proposer_gpu.py:L56-L58). Among equally long matches, vLLM prefers the oldest occurrence, on the theory that the prompt is a better source of truth than the model's own recent output. Suffix decoding, below, makes recency an explicit and tunable ranking instead.

Defaults, version-stamped at a556f3f: if neither bound is given, both become 5.

        if self.method in ("ngram", "ngram_gpu"):
            # Set default values if not provided
            if self.prompt_lookup_min is None and self.prompt_lookup_max is None:
                # TODO(woosuk): Tune these values. They are arbitrarily chosen.
                self.prompt_lookup_min = 5
                self.prompt_lookup_max = 5

Note that the field's own docstring says prompt_lookup_min "Defaults to 1" (L163-L165) while the code sets 5. The code wins. The e2e test uses min 3 / max 5 with $\kappa=3$ (tests/v1/e2e/spec_decode/ngram_suffix/test_ngram_suffix.py:L27-L32); the shipped example defaults to min 2 / max 5 (examples/features/speculative_decoding/spec_decode_offline.py:L55-L56). Larger $n$ means fewer but more trustworthy matches — it moves you right along Figure 1 only if the extra precision buys more $\alpha$ than the lost coverage costs.

"Costs nothing" is a claim about FLOPs, not about wall clock. The CPU proposer runs inside the step loop, after sampling, and it needs the sampled token ids as Python lists. Materialising them is not free:

    def _to_list(self, sampled_token_ids: torch.Tensor) -> list[list[int]]:
        # This is a short term mitigation for issue mentioned in
        # https://github.com/vllm-project/vllm/issues/22754.
        # `tolist` would trigger a cuda wise stream sync, which
        # would block other copy ops from other cuda streams.
        # A cuda event sync would avoid such a situation. Since
        # this is in the critical path of every single model
        # forward loop, this has caused perf issue for a disagg
        # setup.
        pinned = self.sampled_token_ids_pinned_cpu[: sampled_token_ids.shape[0]]
        pinned.copy_(sampled_token_ids, non_blocking=True)
        self.transfer_event.record()
        self.transfer_event.synchronize()
        return pinned.tolist()

Then the matching itself. It is $O(T)$ per request in the context length $T$, single-threaded by construction, and the thread cap is written so that it can never be anything else:

        # Max number of threads for numba parallel processing.
        if cpu_count:
            # Divide by 2 to use physical cores
            # and not logical cores (hyper-threading).
            # Cap the number of threads to 8 to avoid using too many threads
            # since other components like frontend (incl tokenization)
            # and Structured Outputs also use multiple threads.
            # TODO(ekagra-ranjan): bump up the cap from 1 to 8
            # when TP parallelization for ngram is implemented.
            self.num_numba_thread_available = min(1, (cpu_count // 2))
            # Divide by tp_size to ensure each tensor parallel rank
            # has some threads since all ranks will run this.
            self.num_numba_thread_available //= tp_size
        else:
            self.num_numba_thread_available = 1

The comment says "cap ... to 8"; the expression is min(1, ...), and the TODO explains why. A @njit(parallel=True) kernel with a prange over requests (L177-L189) is therefore running on one thread, and the num_tokens_threshold = 8192 switch that is supposed to enable multi-threading (L36, L102-L106) cannot select more than one. At batch 64 with 8k of context each, that single thread walks roughly $5\times10^{5}$ token positions per step, serially, while the GPU waits.

That is the entire motivation for ngram_gpu: not arithmetic, but keeping the step loop free of host round-trips. Its inner loop replaces KMP with brute-force windowed comparison, which is embarrassingly wasteful and completely parallel:

        for i, ngram_len in enumerate(range(min_ngram_len, max_ngram_len + 1)):
            # Sliding windows of size ngram_len; unfold is O(1) view.
            search_windows = token_ids.unfold(1, ngram_len, 1)
            num_windows = search_windows.shape[1]

            # Trailing suffix (last ngram_len tokens) for each sequence.
            suffix_starts = seq_lengths - ngram_len
            suffix_indices = suffix_starts.unsqueeze(1) + torch.arange(
                ngram_len, device=device
            )
            suffix_indices.clamp_(min=0)
            suffix = torch.gather(token_ids, 1, suffix_indices)

            # Window matches for each sequence.
            matches = (search_windows == suffix.unsqueeze(1)).all(dim=-1)

            # Match must leave room for at least one draft token.
            max_valid_suffix_start = seq_lengths - ngram_len - 1
            window_positions = torch.arange(num_windows, device=device)
            valid_mask = window_positions <= max_valid_suffix_start.unsqueeze(1)
            final_matches = matches & valid_mask

            # Find earliest match (argmax=0 when empty; verify with has_match).
            first_match_idx = torch.argmax(final_matches.int(), dim=1)
            has_match = final_matches[batch_indices, first_match_idx]

Every comparison is data-independent, so the whole thing is one torch.compiled region with CUDAGraphMode.NONE and no branch on any device value — the file's comments say so explicitly ("Avoid data-dependent branching", L120; "Extract draft tokens; gather always runs", L140). The consequence is that the proposer can no longer tell the scheduler how many tokens it produced without a sync, so it doesn't: it pads with $-1$, ships the count home on a dedicated stream, and trims the scheduler's own bookkeeping afterwards (update_scheduler_for_invalid_drafts, L475-L515) — which is also why the runner has to shallow-copy SchedulerOutput before handing it over (vllm/v1/worker/gpu_model_runner.py:L4299-L4314). A sampler can skip invalid $-1$ slots, but scheduled verification positions and bookkeeping are not free end to end.

When it pays: long contexts, large batches, async scheduling, or a disaggregated setup where a host sync stalls other streams. At batch 4 with 512-token contexts, the CPU matcher is fine and the GPU version is paying a kernel launch to save a microsecond.

Fixed-$n$ lookup has three limitations that all come from the same place: it commits to one match. It cannot tell a span it has seen forty times from one it has seen once; it cannot vary the draft length with how confident the match is; and it can only match within the current request. A suffix automaton fixes all three, because it stores every substring of everything it has ingested, in linear space.

vLLM's suffix method is a thin wrapper — the cache, tree, and speculation logic live in Arctic Inference, out of tree. What the wrapper shows is the interface and the per-request lifecycle:

            # Suffix decoding only uses the most recent tokens up to max_tree_depth, so
            # we extract the pattern from the end of the input.
            start = max(0, num_tokens - self.max_tree_depth)
            pattern = input_batch.token_ids_cpu[i, start:num_tokens]
            draft = self.suffix_cache.speculate(
                req_id,
                pattern,
                max_spec_tokens=min(
                    self.num_speculative_tokens, self.max_model_len - num_tokens - 1
                ),
                max_spec_factor=self.max_spec_factor,
                min_token_prob=self.min_token_prob,
            )

Three knobs there are the three fixes. max_spec_factor makes the draft length a function of match quality — "max_spec_tokens = max_spec_factor * prefix_match_length" (vllm/config/speculative.py:L205-L209), so a 10-token match speculates ten times further than a 1-token one at the default factor of 1.0. min_token_prob = 0.1 is a frequency-count threshold: "Will only speculate tokens with estimated probability (based on frequency counts) greater than or equal to this value" (L210-L212). And suffix_decoding_max_cached_requests = 10,000 keeps a global tree of past responses, FIFO-evicted, so a match can come from a different request entirely (L199-L203). Because the draft length is dynamic, num_speculative_tokens stops being a length and becomes a ceiling — the docs recommend 16 or 32 rather than 3 (docs/features/speculative_decoding/suffix.md:L12-L13).

SGLang's suffix automaton, in tree

SGLang builds the same structure itself, in C++, JIT-compiled, and it is readable at this SHA. The state is a textbook suffix automaton with two extra statistics per state:

struct SamState {
  int link = -1;
  int32_t max_len = 0;
  std::unordered_map<int32_t, int> next;
  uint64_t occ_count = 0;
  int64_t max_end_pos = -1;
  std::vector<std::pair<int32_t, int>> children_by_freq;
  std::vector<std::pair<int32_t, int>> children_by_recency;
};

occ_count is how many times this substring occurred; max_end_pos is where it occurred last. Both are computed once at finalize() by propagating up the suffix-link tree in order of decreasing max_len (suffix_automaton.cpp:L98-L112), then each state's children are pre-sorted into two orders — by frequency and by recency. Fixed-$n$ lookup has to choose one occurrence; the automaton keeps a ranked list of continuations at every matched length simultaneously.

Matching is a walk with suffix-link fallback, which is what makes it strictly more informative than a fixed window: on a miss it does not give up, it shortens the match and continues.

  const auto start = len > max_depth ? len - max_depth : 0;
  int state = 0;
  int32_t matched_len = 0;
  for (size_t i = start; i < len; ++i) {
    const auto token = context[i];
    while (state != 0 && !states_[state].next.contains(token)) {
      state = states_[state].link;
      matched_len = std::min<int32_t>(matched_len, states_[state].max_len);
    }
    // ...
  }

  std::vector<SamAnchor> anchors;
  while (state > 0 && matched_len > 0) {
    if (!states_[state].children_by_freq.empty()) {
      anchors.push_back({state, matched_len});
    }
    state = states_[state].link;
    if (state <= 0) {
      break;
    }
    matched_len = std::min<int32_t>(matched_len, states_[state].max_len);
  }
  return anchors;

The second loop is the payoff. It walks the suffix links upward from the deepest match, collecting one anchor per achievable match length: a 9-token match, a 7-token match, a 4-token one, down to 1. The draft is then built from all of them, with the fan-out at each anchor scaled by how long its match was — long match, narrow and confident; short match, wide and hedged:

  auto anchors = match(context, len, param.max_trie_depth);
  const auto max_match_depth = std::max<int32_t>(1, static_cast<int32_t>(param.max_trie_depth - 1));
  const double bfs_breadth_scale = double(param.max_bfs_breadth - param.min_bfs_breadth) / max_match_depth;
  std::vector<Node> tree(draft_token_num + 1);
  int root = 0;
  int cursor = 1;

  for (const auto& anchor : anchors) {
    std::queue<std::tuple<int, double, int>> queue;
    queue.push(
        {root, (max_match_depth - anchor.matched_len) * bfs_breadth_scale + param.min_bfs_breadth, anchor.state});

With the shipped defaults — max_trie_depth = 18, min_bfs_breadth = 1, max_bfs_breadth = 10 (python/sglang/srt/server_args.py:L2327-L2342) — the scale is $(10-1)/17 = 0.53$, so a 17-token match starts at breadth 1 (a straight chain) and a 2-token match starts at breadth $15 \times 0.53 + 1 = 8.9$, and breadth decays by 0.53 per level as the BFS descends. The alternative match_type = "PROB" replaces the queue with a max-heap ordered by a frequency-derived probability (buildFrequency, L217-L283), expanding the globally most likely node next rather than level by level.

Two things separate SGLang's implementation from vLLM's n-gram. First, the draft is a tree, not a chain: speculative_num_draft_tokens is a node budget for the whole tree, and NgramVerifyInput carries a custom_mask and parent/sibling links so one target pass verifies every path (python/sglang/srt/speculative/ngram_info.py:L11-L41; the mask machinery is §6.4's subject). The header comment is blunt about the shape: "NGRAM trees are node-budgeted with no depth cap ... a single long match can chain all draft_token_num nodes" (L47-L52). Second, the corpus is shared across requests and grows as the server runs — every step feeds accepted output back in:

            put_ids = self._efficient_concat_last_n(
                list(req.origin_input_ids[-self.max_trie_depth :]),
                list(req.output_ids[-self.max_trie_depth :]) + prev_tokens,
                self.max_trie_depth,
            )
            batch_tokens.append(put_ids)
            i += 1
        self.ngram_corpus.batch_put(batch_tokens)

And it can be pre-seeded offline: --speculative-ngram-external-corpus-path takes a JSONL corpus tokenized at startup, capped by speculative_ngram_external_corpus_max_tokens (default 10 M) with a separate node budget speculative_ngram_external_sam_budget reserved for its subtree in every draft (python/sglang/srt/server_args.py:L2346-L2359). That budget flag defaults to 0, and 0 is rejected: passing the corpus path without also passing a positive budget (and a budget no larger than speculative_num_draft_tokens - 1) raises at startup — "--speculative-ngram-external-sam-budget must be positive when --speculative-ngram-external-corpus-path is set." (python/sglang/srt/arg_groups/speculative_hook.py:L729-L747). The corpus is opt-in and costs you draft-tree nodes you must explicitly hand it. Corpora can also be added and removed at runtime through POST /add_external_corpus, loaded on a background thread and committed from the scheduler loop (python/sglang/srt/speculative/external_corpus_manager.py:L40-L52). That turns "the draft has to already be in your prompt" into "the draft has to already be in your domain corpus" — a materially different, and much larger, hit rate.

Follow one decode step of a batch of 8 requests with --speculative-algorithm NGRAM --speculative-num-draft-tokens 8.

1. NGRAMWorker._prepare_draft_tokens (python/sglang/srt/speculative/ngram_worker.py:L238) assembles, for each request, the last max_trie_depth = 18 tokens of prompt-plus-output. In overlap mode the previous step's accepted tokens are not yet in req.output_ids, so they are spliced in from spec_info.accept_tokens — which is the one .cpu() in this path, and the code hoists everything it can above it ("Accept-independent prep, hoisted above the blocking .cpu() below", L250).
2. self.ngram_corpus.synchronize() (L283) flushes the previous step's inserts into the automaton, then batch_get(req_ids, batch_tokens, total_lens) (L299) calls into match_stateful, which returns (req_drafts, mask) — a flat $8 \times 8$ token array and its $8 \times 8 \times 8$ ancestry mask.
3. The worker asserts the corpus returned exactly bs * draft_token_num tokens ("here we always enforce it", L302-L306). Unlike vLLM's proposer, which returns an empty list when nothing matches, SGLang always fills the tree — a padded node still costs a verified position.
4. _prepare_for_speculative_decoding (L310) turns the mask into retrieve_next_token/retrieve_next_sibling and rewrites the batch's forward_mode to TARGET_VERIFY. One target forward runs over $8 \times 8 = 64$ positions.
5. Verification is the shared path from §6.2 — eagle_sample, then move_accept_tokens_to_target_kvcache, because a tree's accepted path is scattered.
6. _update_ngram_corpus (L399) pushes the accepted tokens back in, and requests that left the batch have their match state dropped: self.ngram_corpus.erase_match_state(list(departed_rids)) (L522). The automaton keeps the tokens; only the per-request walk cursor is freed.

vLLM's chain path is shorter. propose_draft_token_ids (vllm/v1/worker/gpu_model_runner.py:L5138-L5149) branches on spec_config.method, hands the CPU proposer sampled_token_ids as a list plus token_ids_cpu, and gets back one list[int] per request — empty where no match was found, which the scheduler reads as "this request does not speculate this step". Mixed batches where some requests match and some do not are the normal case, and §6.2's ragged metadata is what makes them a single forward pass.

LoRA compatibility is a method/runner-specific contract, not a general prohibition on model-based drafts. The quoted SGLang validator lists NGRAM, EAGLE, NEXTN, EAGLE3, DFLASH and DSPARK as compatible methods (python/sglang/srt/server_args.py:L9569-L9583). Weightless sources avoid draft-adapter synchronization, while model-based sources still need the supported configuration and an acceptance measurement under the active target adapter.

The draft's memory is subtracted before the pool is sized

The 10.5% concurrency loss derived in §3 is not a runtime slowdown you can profile; it appears as a smaller num_gpu_blocks at startup and shows up later as queueing delay under load. If you add a draft model to a server that was already running near its concurrency limit, the symptom is a longer queue, not a longer step. Check the KV-cache block count in the startup log before and after.

Long wrong drafts burn verification budget

Suffix decoding's dynamic length is a double-edged knob. At max_spec_factor = 2.0 (what the e2e test uses, tests/v1/e2e/spec_decode/ngram_suffix/test_ngram_suffix.py:L33-L36) a 12-token match asks for 24 draft tokens. If the match was coincidental, all 24 positions are verified and discarded — and, worse, all 24 wrote KV entries the scheduler must roll back (§6.2). The cost is not $\kappa c$; $c$ is zero here. The cost is $\kappa+1$ verified positions against the roofline ridge of 295, which at batch 16 is already $16 \times 25 = 400$ positions and past it. For a free draft source, the binding constraint is not draft cost but verification width. min_token_prob exists for exactly this and defaults to 0.1.

Acceptance collapses when the workload shifts, silently

An n-gram proposer configured for a summarisation fleet keeps working when the traffic turns into open-ended chat — it just returns empty drafts, then the occasional wrong one. Nothing errors. The observable is vLLM's mean_acceptance_length and its per-position vector (vllm/v1/spec_decode/metrics.py:L113-L118, walked through in §6.2). Alert on it. It is the only thing in this chapter that tells you your draft source has stopped matching the traffic.

Tokenizer mismatch does not fail loudly enough

Equal vocabulary size is not semantic tokenizer compatibility. Different merges can pass an ID-range check yet produce poorly aligned proposals. Exact rejection remains valid over consistent integer IDs/probabilities; a low acceptance rate is not itself output bias. For deliberate cross-tokenizer pairing, inspect the mapping and probability accounting, use use_heterogeneous_vocab: true and read the intersection size the mapper logs: "VocabMapping initialized: target_vocab=%d, draft_vocab=%d, intersection=%d" (vllm/v1/spec_decode/vocab_mapping.py:L122-L136), which warns below 100 shared tokens.

Earliest, not most recent

If you are reasoning about why a particular draft was proposed, remember that vLLM picks the oldest occurrence of the longest match (L255-L263 above), while SGLang's default match_type = "BFS" ranks continuations by children_by_recency, i.e. max_end_pos — the newest. On a request whose prompt and generation disagree about what follows a span, the two engines will propose different tokens from the same context. Both are correct; only their hit rates differ.

A lookup method can have high acceptance when it finds a match yet match few requests. Report match coverage, proposals per matched request, accepted length and full draft/verify latency separately. Shared suffix stores also need tenant/model/tokenizer namespaces, bounded retention and access controls; retrieving another tenant's text is a privacy boundary even if target verification preserves output probabilities.

def expected_emitted(alpha, depth):
    return sum(alpha ** i for i in range(depth + 1))

def mixture_yield(coverage, alpha, depth):
    return 1 + coverage * (expected_emitted(alpha, depth) - 1)

rare_accurate = mixture_yield(0.1, 0.99, 3)
common_moderate = mixture_yield(0.9, 0.7, 3)
assert rare_accurate < common_moderate
assert abs(mixture_yield(0, 1, 3) - 1) < 1e-12
assert abs(mixture_yield(1, 1, 3) - 4) < 1e-12
print("Expected emitted tokens:", rare_accurate, common_moderate)
print("Compare these with measured full iteration cost, not acceptance alone.")

Run the same prompts through three draft sources and read mean_acceptance_length off the metrics, which is $E$ from §6.2 directly.

# free draft, chain, host-side matcher
python examples/features/speculative_decoding/spec_decode_offline.py \
    --method ngram --num-spec-tokens 3 --prompt-lookup-min 3 --prompt-lookup-max 5 \
    --temp 0 --output-len 256

# same matcher, on the GPU — no flag in the example, so use the server
vllm serve Qwen/Qwen3-8B \
    --speculative-config '{"method": "ngram_gpu", "num_speculative_tokens": 3, "prompt_lookup_min": 2, "prompt_lookup_max": 3}'

# suffix automaton, dynamic draft length (needs: pip install arctic-inference)
vllm serve Qwen/Qwen3-8B \
    --speculative-config '{"method": "suffix", "num_speculative_tokens": 32, "suffix_decoding_max_spec_factor": 2.0}'

# a real draft model, for the contrast
python examples/features/speculative_decoding/spec_decode_offline.py \
    --method draft_model --draft-model Qwen/Qwen3-0.6B --num-spec-tokens 5 --temp 0

The experiment worth doing is not "which is fastest on my laptop prompt". It is: run each source on a summarisation dataset and on an open-ended chat dataset, record $E$ for both, and plot the four points on Figure 1. You will have derived $c$ already; the measurement supplies $\alpha$, and the plane tells you which side of the indifference curve you are on. That sweep is Lab 08, spec-decode acceptance. Everything numeric in this chapter is derived or cited; nothing here was measured.

SGLang's equivalent, with the tree budget rather than a chain length:

python -m sglang.launch_server --model-path Qwen/Qwen3-8B \
    --speculative-algorithm NGRAM --speculative-num-draft-tokens 8 \
    --speculative-ngram-max-trie-depth 18 --speculative-ngram-max-bfs-breadth 10 \
    --speculative-ngram-match-type BFS

• Oliaro et al., SuffixDecoding: A Model-Free Approach to Speeding Up Large Language Model Inference (arXiv:2411.04975) — the technical report vLLM's suffix method points at (vllm/v1/spec_decode/suffix_decoding.py:L10-L14), implemented in ArcticInference.
• Saxena, prompt-lookup-decoding, and the thread vLLM's own docs cite as the reference (docs/features/speculative_decoding/n_gram.md:L3-L4). The original observation that input-grounded tasks make a string matcher a viable drafter.
• vllm/v1/spec_decode/ngram_proposer_gpu.py at a556f3f — read update_scheduler_for_invalid_drafts (L475-L515) alongside gpu_model_runner.py:L4299-L4315 for a complete example of removing a host sync from a step loop by deferring the bookkeeping instead of the work.
• python/sglang/kernels/jit/csrc/ngram_corpus/ — a compact, readable suffix automaton with occurrence counts and recency, plus two draft-tree builders (buildRecency and buildFrequency). Under 300 lines, and the clearest in-tree explanation of what suffix decoding actually does in either project.
• Where this chapter hands off: the accept/reject rule and the $S(B)$ roofline argument are §6.2; drafts that come from the target's own hidden states, and the tree masks that verify them, are §6.4; SGLang's adaptive speculation, DFlash, DSpark and frozen-KV MTP are §6.6. The two formulas reused here live in FORMULAS.