Speculative Decoding

A language model writes its answer one token at a time. A token is a small piece of text, often a short word or part of a word. To produce each token, the model runs one forward pass: it feeds the text so far through all of its layers and gets back a score for every possible next token. Every forward pass has to read all of the model's weights (the learned numbers that make up the model) from memory. For a large model, that reading takes most of the time. Writing 100 tokens therefore means reading the weights 100 times.

Speculative decoding reduces the number of those expensive passes. A cheap helper guesses the next several tokens, and the large model checks all of the guesses in one pass. Guesses that match what the large model would have written are kept. The first wrong guess, and everything after it, is thrown away and replaced by the large model's own token. Because the large model has the final word at every position, the finished text is the same text that plain decoding would have produced. Only the speed changes.

This lesson builds the method from small Java simulations. It shows one round of guessing and checking, works out how many tokens a round yields on average, and shows with a sampling experiment that random (non-greedy) output still follows the large model's probabilities exactly. It then compares the kinds of helpers that exist, configures speculation in llama.cpp and vLLM, and explains why it can make a busy server slower. Afterwards you can predict whether speculation will help on a given workload and choose its settings.

Two names recur. The target model is the large model whose output the user wants. The draft (also called the proposer) is anything cheap that guesses the target's next tokens: a small model, a lookup in the text so far, or a few extra layers attached to the target.

The reason this works comes from the roofline model lesson. Decoding one token is memory-bound, which means the speed is limited by how fast the weights can be read from memory, not by how fast the chip can do arithmetic. The arithmetic units sit mostly idle while they wait. Checking five tokens instead of one reads the same weights once and does a little more arithmetic, so it costs almost the same time as checking one. Speculative decoding spends the idle arithmetic on checking guesses.

An analogy: a proofreader can read a page written by an assistant much faster than the assistant can write it, and can approve the first three sentences and fix the fourth. Here the assistant is the draft and the proofreader is the target. The analogy stops at one point: the proofreader in this lesson is exact, so the final page is exactly what the proofreader would have written alone.

Example 1: draft k tokens, verify them in one pass

This example shows a single round of speculative decoding. The toy target always writes the line for i in range ( n ) : total += i, one word per step, and always picks its most likely word (this is called greedy decoding). The draft is a small lookup table that guesses the next word from the previous word only, so it is often wrong. The variable k is the number of guesses per round. The text so far is for i in. When you read the output, look at which guesses survive and which one ends the round.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DraftAndVerify {
    // The target model is the reference: it always produces this text, one word per step (greedy).
    static final String[] TEXT = "for i in range ( n ) : total += i".split(" ");

    static String target(int pos) { return pos < TEXT.length ? TEXT[pos] : "<eos>"; }

    // The draft model guesses the next word from the previous word only (a bigram table).
    static final Map<String, String> DRAFT = new HashMap<>(Map.of(
            "for", "i", "i", "in", "in", "range", "range", "(", "(", "len",
            ")", ":", ":", "return", "total", "+=", "+=", "1"));

    static String draft(String prev) { return DRAFT.getOrDefault(prev, "<unk>"); }

    public static void main(String[] args) {
        int k = 4;
        List<String> out = new ArrayList<>(List.of("for", "i", "in")); // already generated

        // 1. Draft: k cheap calls to the draft model, each feeding on its own guess.
        List<String> proposal = new ArrayList<>();
        String prev = out.get(out.size() - 1);
        for (int i = 0; i < k; i++) {
            prev = draft(prev);
            proposal.add(prev);
        }
        System.out.println("context  : " + out);
        System.out.println("draft    : " + proposal);

        // 2. Verify: one target pass over [last, d1..dk] gives the target's choice at k+1 positions.
        int start = out.size();
        List<String> targetChoices = new ArrayList<>();
        for (int i = 0; i <= k; i++) targetChoices.add(target(start + i));
        System.out.println("target   : " + targetChoices + "  (1 pass, " + (k + 1) + " positions)");

        // 3. Accept the longest prefix where draft and target agree, then take the target's own token.
        int accepted = 0;
        while (accepted < k && proposal.get(accepted).equals(targetChoices.get(accepted))) accepted++;
        out.addAll(proposal.subList(0, accepted));
        out.add(targetChoices.get(accepted));
        System.out.println("accepted : " + accepted + " of " + k + " drafted, plus 1 target token");
        System.out.println("context  : " + out);
        System.out.println("tokens added by this target pass: " + (accepted + 1));
    }
}

context  : [for, i, in]
draft    : [range, (, len, <unk>]
target   : [range, (, n, ), :]  (1 pass, 5 positions)
accepted : 2 of 4 drafted, plus 1 target token
context  : [for, i, in, range, (, n]
tokens added by this target pass: 3

The draft ran four times, and each run fed on the draft's own previous guess: range, (, len, and <unk>. The last guess is <unk> (unknown) because the table has no entry for len. These guesses are cheap because the draft is small.

The target line is the key step. A real engine puts the last accepted token and the four guesses into one batch of five positions, [in, range, (, len, <unk>], and runs the target once. A causal transformer (the kind of model used here) computes scores at every position of a batch, the same way it does when it reads a prompt. So this one pass yields the target's choice after in, after in range, after in range (, and so on. The toy reads those five choices from TEXT: range, (, n, ), :.

Verification compares the two lists from the left:

• Position 1: the draft said range and the target said range. Accepted.
• Position 2: ( against (. Accepted.
• Position 3: the draft said len and the target said n. Rejected.

Everything after the first rejection is discarded, because those guesses were made on a context that is now known to be wrong. The target's own choice at the rejected position, n, is correct by definition, so it is kept. One target pass added three tokens: two accepted guesses and one target token.

Every round adds at least one token, the same one plain decoding would have produced. So speculation never makes the output shorter or different. In the worst case it wastes the work of drafting and the extra positions in the verification batch.

Example 2: greedy verification over a whole answer

This example runs the loop to the end of an answer. It answers two questions: does speculation produce exactly the plain greedy output, and how many target passes does it save? The target text is now two loops and a return, and the draft table is a little larger. The program first decodes plainly to get the reference output, then decodes speculatively with k = 4 and prints one line per target pass. Look at how many tokens each pass adds.

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class GreedySpeculation {
    static final String[] TEXT = ("for i in range ( n ) : total += i ; "
            + "for j in range ( m ) : total += j ; return total").split(" ");
    static String target(int pos) { return pos < TEXT.length ? TEXT[pos] : "<eos>"; }

    static final Map<String, String> DRAFT = Map.ofEntries(
            Map.entry("for", "i"), Map.entry("i", "in"), Map.entry("in", "range"),
            Map.entry("range", "("), Map.entry("(", "len"), Map.entry("n", ")"),
            Map.entry(")", ":"), Map.entry(":", "total"), Map.entry("total", "+="),
            Map.entry("+=", "1"), Map.entry(";", "for"), Map.entry("return", "total"));
    static String draft(String prev) { return DRAFT.getOrDefault(prev, "<unk>"); }

    public static void main(String[] args) {
        // Plain decoding: one target pass per token.
        List<String> plain = new ArrayList<>(List.of("for"));
        int plainPasses = 0;
        while (!plain.get(plain.size() - 1).equals("<eos>")) {
            plain.add(target(plain.size()));
            plainPasses++;
        }

        // Speculative decoding with k = 4.
        int k = 4, targetPasses = 0, draftCalls = 0, drafted = 0, acceptedTotal = 0;
        List<String> out = new ArrayList<>(List.of("for"));
        while (!out.get(out.size() - 1).equals("<eos>")) {
            List<String> proposal = new ArrayList<>();
            String prev = out.get(out.size() - 1);
            for (int i = 0; i < k; i++) { prev = draft(prev); proposal.add(prev); draftCalls++; }
            targetPasses++;                                        // verifies k+1 positions at once
            int start = out.size(), a = 0;
            while (a < k && proposal.get(a).equals(target(start + a))) a++;
            out.addAll(proposal.subList(0, a));
            out.add(target(start + a));
            drafted += k;
            acceptedTotal += a;
            System.out.printf("pass %2d: draft %-30s accepted %d -> +%d tokens%n",
                    targetPasses, proposal, a, a + 1);
        }
        System.out.println("same output as plain decoding: " + out.equals(plain));
        System.out.println("generated tokens   : " + (out.size() - 1));
        System.out.println("plain target passes: " + plainPasses);
        System.out.println("spec target passes : " + targetPasses + ", draft calls: " + draftCalls);
        System.out.printf("acceptance rate    : %d/%d = %.3f%n", acceptedTotal, drafted,
                (double) acceptedTotal / drafted);
        System.out.printf("tokens per target pass: %.2f%n", (double) (out.size() - 1) / targetPasses);
    }
}

pass  1: draft [i, in, range, (]              accepted 4 -> +5 tokens
pass  2: draft [), :, total, +=]              accepted 4 -> +5 tokens
pass  3: draft [in, range, (, len]            accepted 0 -> +1 tokens
pass  4: draft [for, i, in, range]            accepted 1 -> +2 tokens
pass  5: draft [<unk>, <unk>, <unk>, <unk>]   accepted 0 -> +1 tokens
pass  6: draft [range, (, len, <unk>]         accepted 2 -> +3 tokens
pass  7: draft [<unk>, <unk>, <unk>, <unk>]   accepted 0 -> +1 tokens
pass  8: draft [:, total, +=, 1]              accepted 3 -> +4 tokens
pass  9: draft [<unk>, <unk>, <unk>, <unk>]   accepted 0 -> +1 tokens
pass 10: draft [for, i, in, range]            accepted 0 -> +1 tokens
pass 11: draft [total, +=, 1, <unk>]          accepted 1 -> +2 tokens
same output as plain decoding: true
generated tokens   : 26
plain target passes: 26
spec target passes : 11, draft calls: 44
acceptance rate    : 15/44 = 0.341
tokens per target pass: 2.36

The line same output as plain decoding: true shows the guarantee of greedy verification. A token enters the output only if it equals the target's greedy choice at that position. The result is therefore the target's greedy output, token for token, and the draft influences only speed.

The pass lines show that the speed depends on the text:

• Passes 1 and 2 accepted all four guesses, because for i in range ( and n ) : total += follow the draft's table.
• Pass 3 drafted in after i, but the target wrote ;. Nothing was accepted, so the round produced one token, exactly as plain decoding would.
• Pass 4 accepted for and then failed on j, which the draft would have predicted as i.
• Passes 5, 7, and 9 started from j or m, which are missing from the table. The draft proposed <unk> four times and every guess was wasted.

The summary lines count work. Plain decoding needed 26 target passes for 26 tokens (25 words after the first for, plus the end-of-sequence token). Speculation needed 11 passes, which is 2.36 tokens per pass, and 44 draft calls. The acceptance rate is the number of accepted guesses divided by the number of drafted guesses: 15 of 44, or 0.341. Whether 11 target passes plus 44 draft calls take less time than 26 target passes depends on how cheap a draft call is. Example 4 computes that.

Example 3: expected tokens per pass for acceptance rate α and draft length k

The previous example gave one run on one text. To plan, a formula is more useful: how many tokens does one target pass yield on average? Leviathan, Kalman, and Matias ("Fast Inference from Transformers via Speculative Decoding", ICML 2023) use a simple model. Each guess is accepted with probability α (alpha), independently, as long as the guesses before it were accepted. A round then always yields 1 token (the target's own). It yields a second token with probability α, a third with probability α², and so on up to α^k. The expected number of tokens is the sum:

1 + α + α² + ... + α^k = (1 - α^(k+1)) / (1 - α)

A small case by hand: α = 0.5 and k = 2 gives 1 + 0.5 + 0.25 = 1.75 tokens per pass. The program prints a table of this formula for several α and k, then checks the formula with a random simulation.

import java.util.Locale;
import java.util.Random;

public class ExpectedTokens {
    // Expected tokens per target pass when each draft token is accepted with probability alpha,
    // independently, and k tokens are drafted: 1 + alpha + alpha^2 + ... + alpha^k.
    static double expected(double alpha, int k) {
        return alpha == 1.0 ? k + 1 : (1 - Math.pow(alpha, k + 1)) / (1 - alpha);
    }

    public static void main(String[] args) {
        int[] ks = {1, 2, 4, 8, 16};
        System.out.print("alpha");
        for (int k : ks) System.out.printf(Locale.ROOT, "   k=%-3d", k);
        System.out.println("  k=inf");
        for (double alpha : new double[] {0.5, 0.6, 0.7, 0.8, 0.9}) {
            System.out.printf(Locale.ROOT, "%5.1f", alpha);
            for (int k : ks) System.out.printf(Locale.ROOT, "  %6.3f", expected(alpha, k));
            System.out.printf(Locale.ROOT, "  %6.3f%n", 1 / (1 - alpha));
        }

        // Monte Carlo check for alpha = 0.8, k = 4.
        Random rnd = new Random(42);
        double alpha = 0.8;
        int k = 4, rounds = 100_000;
        long tokens = 0;
        for (int r = 0; r < rounds; r++) {
            int accepted = 0;
            while (accepted < k && rnd.nextDouble() < alpha) accepted++;
            tokens += accepted + 1;                               // accepted drafts + 1 target token
        }
        System.out.printf(Locale.ROOT, "simulated alpha=0.8 k=4: %.4f tokens/pass, formula %.4f%n",
                (double) tokens / rounds, expected(alpha, k));
    }
}

alpha   k=1     k=2     k=4     k=8     k=16   k=inf
  0.5   1.500   1.750   1.938   1.996   2.000   2.000
  0.6   1.600   1.960   2.306   2.475   2.500   2.500
  0.7   1.700   2.190   2.773   3.199   3.326   3.333
  0.8   1.800   2.440   3.362   4.329   4.887   5.000
  0.9   1.900   2.710   4.095   6.126   8.332  10.000
simulated alpha=0.8 k=4: 3.3590 tokens/pass, formula 3.3616

Take α = 0.8 and k = 4 as a worked case: (1 - 0.8^5) / (1 - 0.8) = (1 - 0.32768) / 0.2 = 3.3616. The simulation with 100,000 seeded rounds measured 3.3590, which agrees with the formula to two decimals. The "seeded" random generator makes the run repeat exactly.

Read the table row by row. Each row rises quickly for small k and then flattens. The last column is the limit for an endless draft, 1 / (1 - α). At α = 0.5 no draft length gives more than 2 tokens per pass, because the chance that a long run of guesses all survive falls geometrically (halving each time). Going from k = 4 to k = 16 at α = 0.5 gains only 0.062 tokens per pass and costs 12 more draft calls. At α = 0.9 the same change gains more than 4 tokens per pass. The acceptance rate therefore decides how long a draft is worth making.

The model is a simplification. Real acceptance is not independent: predictable stretches of text (closing brackets, repeated identifiers) accept long runs of guesses, and hard stretches reject at once. Engines report acceptance for each position in the draft for that reason (Example 8 and Example 11 use those numbers).

Example 4: speedup estimate including the draft cost

Example 3 counted tokens, but drafting takes time too. Let c be the time of one draft step divided by the time of one target step. For example, if a draft step takes 5 ms and a target step takes 50 ms, then c = 0.1. A round costs k draft steps and one target pass, which is 1 + k·c target-step units, and it yields the expected tokens from Example 3. The speedup over plain decoding is the ratio of the two, the formula given by Leviathan et al.:

speedup = (1 - α^(k+1)) / ((1 - α)(1 + k·c))

The model assumes that verifying k+1 positions costs the same as one decode step. That holds while decoding is memory-bound. Example 12 removes the assumption.

The program has two parts. The first fixes α = 0.8 and c = 0.1 and varies k. The second searches k from 1 to 32 for several combinations of c and α and prints the best k.

import java.util.Locale;

public class SpeedupEstimate {
    static double expected(double alpha, int k) { return (1 - Math.pow(alpha, k + 1)) / (1 - alpha); }

    // One round costs k draft steps (c each, in units of one target step) plus one target pass.
    static double speedup(double alpha, int k, double c) { return expected(alpha, k) / (1 + k * c); }

    public static void main(String[] args) {
        double alpha = 0.8, c = 0.1;
        System.out.println("alpha=0.8, c=0.1");
        for (int k : new int[] {1, 2, 3, 4, 6, 8, 12}) {
            System.out.printf(Locale.ROOT, "  k=%-2d  tokens/pass %.3f  cost/round %.1f  speedup %.3f%n",
                    k, expected(alpha, k), 1 + k * c, speedup(alpha, k, c));
        }
        System.out.println("best k and speedup:");
        System.out.println("  c       alpha=0.6   alpha=0.7   alpha=0.8   alpha=0.9");
        for (double cost : new double[] {0.02, 0.05, 0.1, 0.3, 1.0}) {
            System.out.printf(Locale.ROOT, "  %-4.2f", cost);
            for (double a : new double[] {0.6, 0.7, 0.8, 0.9}) {
                int bestK = 0;
                double best = 1.0;                                 // k = 0 means "do not speculate"
                for (int k = 1; k <= 32; k++) {
                    double s = speedup(a, k, cost);
                    if (s > best) { best = s; bestK = k; }
                }
                System.out.printf(Locale.ROOT, "   k=%-2d %.2fx", bestK, best);
            }
            System.out.println();
        }
    }
}

alpha=0.8, c=0.1
  k=1   tokens/pass 1.800  cost/round 1.1  speedup 1.636
  k=2   tokens/pass 2.440  cost/round 1.2  speedup 2.033
  k=3   tokens/pass 2.952  cost/round 1.3  speedup 2.271
  k=4   tokens/pass 3.362  cost/round 1.4  speedup 2.401
  k=6   tokens/pass 3.951  cost/round 1.6  speedup 2.470
  k=8   tokens/pass 4.329  cost/round 1.8  speedup 2.405
  k=12  tokens/pass 4.725  cost/round 2.2  speedup 2.148
best k and speedup:
  c       alpha=0.6   alpha=0.7   alpha=0.8   alpha=0.9
  0.02   k=6  2.17x   k=8  2.76x   k=11 3.82x   k=19 6.37x
  0.05   k=4  1.92x   k=6  2.35x   k=8  3.09x   k=13 4.67x
  0.10   k=3  1.67x   k=4  1.98x   k=6  2.47x   k=10 3.43x
  0.30   k=1  1.23x   k=2  1.37x   k=3  1.55x   k=5  1.87x
  1.00   k=0  1.00x   k=0  1.00x   k=0  1.00x   k=0  1.00x

The first block fixes α = 0.8 and a draft step that costs 10% of a target step. At k = 4 a round costs 1 + 4 × 0.1 = 1.4 units and yields 3.362 tokens, so the speedup is 3.362 / 1.4 = 2.401 times plain speed. The speedup peaks at k = 6 (2.470) and then falls. At k = 12 the round costs 2.2 units but yields only 4.725 tokens, because the 7th to 12th guesses are rarely reached. Past the peak, each extra draft step costs more time than the tokens it adds on average.

The second block gives the best k for each pair of c and α. Cheaper drafts (smaller c) and better drafts (larger α) both push the best k up. A draft at 2% of the target's cost with α = 0.9 reaches 6.37 times at k = 19. This is the region of n-gram lookups (almost free) on highly repetitive text, which Example 6 shows. A draft at 30% of the target's cost never passes 1.9 times. The last row is a draft as expensive as the target: no k beats plain decoding (k=0 1.00x). This is the case of the tiny model used as its own draft in Example 10.

These numbers are upper bounds. Real engines also pay for sampling, bookkeeping, and rolling back the KV cache (key-value cache, the stored attention data for earlier tokens) of rejected positions.

Example 5: rejection sampling keeps the target distribution

So far the target always picked its single most likely token. Chat models usually sample instead: they pick the next token at random, following the probabilities the model computes, usually with a temperature setting that makes the choice more or less random. Checking "is the draft's token equal to one random sample from the target" would reject more often than necessary. Two papers, Leviathan et al. and Chen et al. ("Accelerating Large Language Model Decoding with Speculative Sampling", 2023), give a better rule called speculative sampling. Let p be the target's probability distribution over the next token and q the draft's.

1. The draft samples a token x from q.
2. The target accepts x with probability min(1, p(x)/q(x)).
3. If x is rejected, the target samples a replacement from the residual distribution, which is max(0, p - q) scaled so that it sums to 1.

Both papers prove that the token that comes out is distributed exactly as p. The program checks the claim with 100,000 seeded samples on a vocabulary of six tokens. It prints p, q, the residual, and how often each token actually came out.

import java.util.Locale;
import java.util.Random;

public class RejectionSampling {
    static int sample(double[] dist, Random rnd) {
        double u = rnd.nextDouble(), cum = 0;
        for (int i = 0; i < dist.length; i++) { cum += dist[i]; if (u < cum) return i; }
        return dist.length - 1;
    }

    public static void main(String[] args) {
        String[] vocab = {"the", "a", "x", "y", "=", ";"};
        double[] p = {0.40, 0.10, 0.20, 0.15, 0.10, 0.05};       // target distribution
        double[] q = {0.20, 0.25, 0.35, 0.05, 0.10, 0.05};       // draft distribution

        double[] residual = new double[p.length];                 // max(0, p - q), normalized
        double sum = 0, acceptProb = 0;
        for (int i = 0; i < p.length; i++) {
            residual[i] = Math.max(0, p[i] - q[i]);
            sum += residual[i];
            acceptProb += Math.min(p[i], q[i]);
        }
        for (int i = 0; i < p.length; i++) residual[i] /= sum;

        Random rnd = new Random(7);
        int n = 100_000, accepted = 0;
        int[] counts = new int[p.length];
        for (int s = 0; s < n; s++) {
            int x = sample(q, rnd);                               // the draft proposes x
            if (rnd.nextDouble() < Math.min(1.0, p[x] / q[x])) { // accept with prob min(1, p/q)
                counts[x]++;
                accepted++;
            } else {
                counts[sample(residual, rnd)]++;                  // otherwise resample from the residual
            }
        }
        System.out.println("token   p(target)  q(draft)  residual  observed");
        for (int i = 0; i < p.length; i++)
            System.out.printf(Locale.ROOT, "%-6s  %9.3f  %8.3f  %8.3f  %8.4f%n",
                    vocab[i], p[i], q[i], residual[i], counts[i] / (double) n);
        System.out.printf(Locale.ROOT, "acceptance: observed %.4f, sum of min(p, q) = %.4f%n",
                accepted / (double) n, acceptProb);
        int top = 0;                                              // the draft's most likely token
        for (int i = 1; i < q.length; i++) if (q[i] > q[top]) top = i;
        System.out.printf(Locale.ROOT, "match check (draft proposes '%s', target samples): acceptance = p = %.3f%n",
                vocab[top], p[top]);
    }
}

token   p(target)  q(draft)  residual  observed
the         0.400     0.200     0.667    0.3989
a           0.100     0.250     0.000    0.0992
x           0.200     0.350     0.000    0.2005
y           0.150     0.050     0.333    0.1514
=           0.100     0.100     0.000    0.1003
;           0.050     0.050     0.000    0.0498
acceptance: observed 0.6985, sum of min(p, q) = 0.7000
match check (draft proposes 'x', target samples): acceptance = p = 0.200

The observed column matches p(target) within sampling noise (0.3989 against 0.400, 0.1514 against 0.150). This holds even though the draft proposes the only half as often as the target wants it and proposes x almost twice as often. Three cases explain the result:

• Tokens the draft over-proposes (a and x, where q is bigger than p) are accepted only part of the time. For x, the acceptance probability is 0.20/0.35, so x comes out with probability 0.35 × 0.20/0.35 = 0.20, which is exactly p.
• Tokens the draft under-proposes (the and y, where p is bigger than q) are always accepted when proposed, and they also receive the probability of the rejections. The residual column holds that share: the has 0.40 - 0.20 = 0.20 and y has 0.15 - 0.05 = 0.10, which scale to 0.667 and 0.333.
• Tokens where p equals q (= and ;) are always accepted and never chosen as replacements.

Here is the full arithmetic for the:

proposed by the draft:          q(the) = 0.20, accepted with min(1, 0.40/0.20) = 1  ->  0.20
chosen after some rejection:    P(reject) = 1 - 0.70 = 0.30, residual share 0.667   ->  0.30 x 0.667 = 0.20
total:                          0.20 + 0.20 = 0.40 = p(the)

The acceptance probability of a proposal is Σ min(p, q) (the sum over all tokens of the smaller of the two probabilities), which here is 0.70. It is the overlap of the two distributions, and the observed rate, 0.6985, agrees. The closer the draft's distribution is to the target's, the higher α is in Example 3.

The last line of the output shows a simpler rule. llama.cpp's verification at the pinned commit (common_sampler_sample_and_accept_n in common/sampling.cpp) samples a token from the target at each position and accepts the draft token only if the two are equal. The draft proposes its most likely token. This rule also keeps the target distribution, because every output token is a real target sample. But the chance of acceptance is only p(x) for the proposed x, here 0.200 instead of 0.70. With greedy target sampling, both rules reduce to "equal to the target's most likely token". llama.cpp's older example program examples/speculative/speculative.cpp implements the full rule: it accepts when r <= p_tgt / p_dft (r is a random number) and builds the residual from max(0, p_tgt - p_dft). vLLM's RejectionSampler (vllm/v1/sample/rejection_sampler.py) states that it follows the algorithm of Leviathan et al.

Example 6: prompt-lookup and n-gram drafting

A draft does not have to be a model. When a model edits code, most of its output repeats text that is already in the prompt. Prompt-lookup decoding exploits this. It takes the last n tokens of the context (an n-gram is a run of n tokens in a row), searches for the same n tokens earlier in the context, and proposes the m tokens that followed them. The program renames a method from sum to total. The answer copies the original code with one change, and the program counts how many tokens each pass gains. Look for the passes where the draft is empty and the passes where it copies a long run.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PromptLookup {
    // Draft by finding the last n tokens earlier in the history and copying the m tokens that followed.
    static List<String> lookup(List<String> history, int n, int m) {
        int len = history.size();
        if (len < n + 1) return List.of();
        List<String> pattern = history.subList(len - n, len);
        for (int j = len - n - 1; j >= 0; j--) {                 // search backwards, skip the current spot
            if (history.subList(j, j + n).equals(pattern)) {
                int from = j + n, to = Math.min(from + m, len);
                return new ArrayList<>(history.subList(from, to));
            }
        }
        return List.of();
    }

    public static void main(String[] args) {
        String code = "int sum ( int [ ] xs ) { int s = 0 ; for ( int x : xs ) s += x ; return s ; }";
        String edited = code.replace("sum", "total");             // the model rewrites the method
        List<String> prompt = new ArrayList<>(Arrays.asList(("Rename sum to total : " + code + " =>").split(" ")));
        String[] answer = (edited + " <eos>").split(" ");

        int n = 2, m = 8, passes = 0, drafted = 0, accepted = 0, out = 0;
        List<String> history = new ArrayList<>(prompt);
        while (out < answer.length) {
            List<String> draft = lookup(history, n, m);
            passes++;
            int a = 0;
            while (a < draft.size() && out + a < answer.length && draft.get(a).equals(answer[out + a])) a++;
            int add = Math.min(a + 1, answer.length - out);        // accepted drafts + the target's token
            for (int i = 0; i < add; i++) history.add(answer[out + i]);
            out += add;
            drafted += draft.size();
            accepted += a;
            System.out.printf("pass %d: draft %-40s accepted %d%n", passes, draft, a);
        }
        System.out.println("answer tokens: " + answer.length + ", target passes: " + passes);
        System.out.println("drafted " + drafted + ", accepted " + accepted);
    }
}

pass 1: draft []                                       accepted 0
pass 2: draft []                                       accepted 0
pass 3: draft []                                       accepted 0
pass 4: draft []                                       accepted 0
pass 5: draft [x, :, xs, ), s, +=, x, ;]               accepted 0
pass 6: draft [], xs, ), {, int, s, =, 0]              accepted 8
pass 7: draft [for, (, int, x, :, xs, ), s]            accepted 8
pass 8: draft [x, ;, return, s, ;, }, =>, int]         accepted 6
answer tokens: 30, target passes: 8
drafted 32, accepted 22

Passes 1 to 4 drafted nothing. After the prompt, the context ended with =>, then => int, int total, and total (. None of these pairs appears earlier, because total is the new name. An empty draft costs nothing, and the round falls back to plain decoding with one token each.

Pass 5 looked up ( int and found its most recent earlier occurrence, ( int x : xs ) in the for loop, so it proposed the loop body. The real answer at that point is ( int [ ] xs ), the parameter list, so the first guess x failed and nothing was accepted. The lookup picks the most recent match, which is not always the right one. Implementations differ in which match they prefer and in whether they require several matches (llama.cpp's --spec-ngram-simple-min-hits).

Passes 6, 7, and 8 copied long runs, with 8, 8, and 6 accepted tokens. In total, 30 answer tokens took 8 target passes instead of 30, with no draft model. (The list printed in pass 6 starts with the token ], which is why the line begins with [].) This is why llama.cpp's documentation (docs/speculative.md) names "rewriting of source code" as the use case for its n-gram methods. It is also why the method matters for coding agents, which rewrite files they have read.

llama.cpp implements several variants: ngram-simple, ngram-map-k, ngram-map-k4v, ngram-mod, and ngram-cache. vLLM has ngram with prompt_lookup_min and prompt_lookup_max (both default to 5 when neither is set, per vllm/config/speculative.py) and suffix, which matches against a tree of earlier responses as well as the prompt.

Example 7: draft model requirements, the shared vocabulary

A small model can serve as a draft, but not any small model. Every model has a vocabulary, the numbered list of all tokens it knows, and each token has an id (its number in the list). Verification compares token ids, so the draft's token 4321 must mean the same text as the target's token 4321. llama.cpp checks this in common_speculative_are_compatible (common/speculative.cpp). The rules are:

• The vocabulary types must match.
• The BOS (beginning of sequence) and EOS (end of sequence) settings and ids must match.
• The sizes may differ by at most SPEC_VOCAB_MAX_SIZE_DIFFERENCE (128).
• The token texts must be equal from id SPEC_VOCAB_CHECK_START_TOKEN_ID (5) up to the smaller size.

The program applies the same rules to toy vocabularies, with a size tolerance of 2 so that it fits the toy. It tests six candidate drafts against one target and prints the first rule that fails.

import java.util.ArrayList;
import java.util.List;

public class VocabCompatibility {
    record Vocab(String name, String type, int bos, int eos, List<String> tokens) {}

    static final int MAX_SIZE_DIFFERENCE = 2;    // llama.cpp uses 128 for real vocabularies
    static final int CHECK_START_ID = 5;         // llama.cpp also starts comparing at id 5

    // Mirrors the checks in llama.cpp common/speculative.cpp (common_speculative_are_compatible).
    static String check(Vocab target, Vocab draft) {
        if (!target.type().equals(draft.type())) return "vocab type differs: " + draft.type();
        if (target.bos() != draft.bos()) return "BOS id differs: " + draft.bos();
        if (target.eos() != draft.eos()) return "EOS id differs: " + draft.eos();
        int diff = Math.abs(target.tokens().size() - draft.tokens().size());
        if (diff > MAX_SIZE_DIFFERENCE) return "size differs by " + diff;
        int common = Math.min(target.tokens().size(), draft.tokens().size());
        for (int id = CHECK_START_ID; id < common; id++)
            if (!target.tokens().get(id).equals(draft.tokens().get(id)))
                return "token " + id + " differs: '" + target.tokens().get(id) + "' vs '" + draft.tokens().get(id) + "'";
        return "compatible";
    }

    static List<String> with(List<String> base, int id, String text) {
        List<String> copy = new ArrayList<>(base);
        copy.set(id, text);
        return copy;
    }

    public static void main(String[] args) {
        List<String> base = List.of("<s>", "</s>", "<pad>", "<x1>", "<x2>", "def", " add", "(", "a", ",", " b", "):");
        List<String> padded = new ArrayList<>(base);
        padded.add("<extra_0>");                                  // a larger model with padded vocabulary

        Vocab target = new Vocab("target-7b", "BPE", 0, 1, base);
        List<Vocab> drafts = List.of(
                new Vocab("same-family-0.5b", "BPE", 0, 1, base),
                new Vocab("padded-vocab", "BPE", 0, 1, padded),
                new Vocab("other-family", "BPE", 0, 1, with(base, 6, " plus")),
                new Vocab("sentencepiece-model", "SPM", 0, 1, base),
                new Vocab("different-eos", "BPE", 0, 2, base),
                new Vocab("special-tokens-only", "BPE", 0, 1, with(base, 3, "<tool>")));
        for (Vocab d : drafts) System.out.printf("%-20s -> %s%n", d.name(), check(target, d));
    }
}

same-family-0.5b     -> compatible
padded-vocab         -> compatible
other-family         -> token 6 differs: ' add' vs ' plus'
sentencepiece-model  -> vocab type differs: SPM
different-eos        -> EOS id differs: 2
special-tokens-only  -> compatible

same-family-0.5b shares the target's tokenizer exactly. This is the usual situation for small and large models released together in one family. padded-vocab has one extra entry at the end. Models in a family often pad the embedding table to a round size, so the rule tolerates a small size difference and compares only the common range.

other-family fails at id 6: the same id means add in one model and plus in the other, so the target would judge the draft's guesses by the wrong text. sentencepiece-model uses a different tokenizer algorithm (the tokenizer lessons describe BPE and SentencePiece), and different-eos would end generation on a different token. The simplified rule shown here checks EOS ids. The real function also compares the "add BOS" and "add EOS" flags.

special-tokens-only differs at id 3 and still passes, because the comparison starts at id 5. The first ids are usually control tokens whose text varies between model conversions. In llama.cpp, a failed check logs a warning, for example draft model vocab type must match target model to use speculation, and speculation is not used. vLLM 0.30.0 has an option for drafts with a different vocabulary, use_heterogeneous_vocab, which "builds a token-level intersection at init and constrains draft logits to shared tokens only" (vllm/config/speculative.py, draft_model method only).

A practical draft also needs a similar training distribution (an instruct-tuned draft for an instruct-tuned target, with the same chat template) and enough speed. A common choice is a model 10 to 50 times smaller from the same family, which keeps c in Example 4 small.

Example 8: EAGLE, Medusa, and multi-token prediction heads

A draft can also live inside the target instead of being a separate model. The target already computes a hidden state for each position, a list of numbers that summarizes the text so far. Small extra layers attached to the target can read that hidden state and guess further tokens, which is much cheaper than running a separate model. Three published designs do this:

• Medusa (Cai et al., "Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads", 2024) adds several heads on the target's last hidden state. A head is a small extra layer that outputs token scores. Head i predicts the token i+1 positions ahead, all at once and independently of the other heads. The paper reports over 2.2 times speedup for Medusa-1 and 2.3 to 3.6 times for Medusa-2.
• EAGLE (Li et al., "EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty", 2024) trains a one-layer draft that reads the target's hidden features and the sampled tokens and drafts one token after another at the feature level. The paper reports 2.7 to 3.5 times latency speedup on LLaMA2-Chat 70B. EAGLE-3 (2025) reads features from several target layers, and its paper reports speedups up to 6.5 times. llama.cpp's docs/speculative.md describes its draft-eagle3 type as "a one-layer transformer trained for a specific target model".
• Multi-token prediction (MTP) trains the model itself with extra modules that predict further tokens (Gloeckle et al., "Better & Faster Large Language Models via Multi-token Prediction", 2024). The DeepSeek-V3 technical report states that the acceptance rate of its second-token prediction is between 85% and 90%, giving about 1.8 times tokens per second.

The program compares the designs through their conditional per-position acceptance rates a[i]. This is the chance that position i+1 is accepted given that the earlier positions were accepted. Independent heads lose accuracy quickly with distance, because head 3 must guess without knowing what heads 1 and 2 chose. The rates for the first three rows are illustrative inputs, not measurements. The MTP rows use the range from the DeepSeek-V3 report.

import java.util.Locale;

public class DraftHeads {
    // a[i] = probability that draft position i+1 is accepted, given that all earlier positions were.
    static void report(String name, double[] a, double draftCost) {
        double unconditional = 1, expected = 1;                   // 1 = the target's own token
        StringBuilder perPos = new StringBuilder();
        for (double ai : a) {
            unconditional *= ai;                                  // P(first i+1 drafts all accepted)
            expected += unconditional;
            perPos.append(String.format(Locale.ROOT, " %.3f", unconditional));
        }
        double speedup = expected / (1 + a.length * draftCost);
        System.out.printf(Locale.ROOT, "%-22s per-position:%s%n", name, perPos);
        System.out.printf(Locale.ROOT, "%-22s mean acceptance length %.3f, cost/round %.2f, speedup %.2fx%n",
                "", expected, 1 + a.length * draftCost, speedup);
    }

    public static void main(String[] args) {
        // Illustrative inputs, not measurements: a separate small model, independent heads,
        // and a feature-level draft head.
        report("separate draft model", new double[] {0.70, 0.70, 0.70, 0.70}, 0.10);
        report("independent heads", new double[] {0.80, 0.60, 0.45, 0.30}, 0.01);
        report("feature-level head", new double[] {0.85, 0.78, 0.72, 0.66}, 0.03);
        // One extra MTP module, using the second-token acceptance range in the DeepSeek-V3 report.
        report("MTP, 1 token (85%)", new double[] {0.85}, 0.0);
        report("MTP, 1 token (90%)", new double[] {0.90}, 0.0);
    }
}

separate draft model   per-position: 0.700 0.490 0.343 0.240
                       mean acceptance length 2.773, cost/round 1.40, speedup 1.98x
independent heads      per-position: 0.800 0.480 0.216 0.065
                       mean acceptance length 2.561, cost/round 1.04, speedup 2.46x
feature-level head     per-position: 0.850 0.663 0.477 0.315
                       mean acceptance length 3.305, cost/round 1.12, speedup 2.95x
MTP, 1 token (85%)     per-position: 0.850
                       mean acceptance length 1.850, cost/round 1.00, speedup 1.85x
MTP, 1 token (90%)     per-position: 0.900
                       mean acceptance length 1.900, cost/round 1.00, speedup 1.90x

The per-position numbers are unconditional rates: the share of rounds in which the first i+1 guesses were all accepted. Each one is the running product of the conditional rates a. For the separate model, 0.70 × 0.70 = 0.490 is the chance that guesses 1 and 2 both survive. vLLM logs exactly this list as "Per-position acceptance rate". The mean acceptance length is 1 plus their sum: the target's own token plus the expected number of accepted guesses. For the separate draft model, 1 + 0.700 + 0.490 + 0.343 + 0.240 = 2.773, which is the same value as α = 0.7, k = 4 in Example 3.

Compare the rows. The independent heads accept fewer tokens per round (2.561) than the separate model (2.773), yet they run faster (2.46 against 1.98 times). A head is a few small matrix multiplications on a hidden state the target already computed, so its cost per draft step is set to 1% of a target step against 10% for the separate model. The feature-level head combines a high first-position rate with a slow decay, because each of its steps sees the previous draft token, and it reaches 2.95 times. The MTP rows check the report's numbers: one extra predicted token accepted 85 to 90% of the time gives a mean length of 1.85 to 1.90, consistent with the reported 1.8 times once overheads are counted.

The trade-off is training. A separate draft model can be any compatible small model. Heads and MTP modules must be trained for one specific target, and a quantized or fine-tuned target may lower their acceptance. Both llama.cpp (draft-eagle3, draft-mtp, draft-dflash, draft-dspark) and vLLM (eagle, eagle3, medusa, mtp, dflash, dspark, among others) support these methods at the pinned versions.

Example 9: tree verification

A chain of guesses is lost at its first wrong guess. If the draft is unsure between two candidates for the next token, it can keep both. A draft tree keeps the top candidates at each depth, and the target verifies the whole tree in one pass. To keep the branches apart, each node gets an attention mask. Attention is the step where each position looks at the earlier tokens, and the mask is a table that says which positions each position may look at. In a tree, a node may look only at its own ancestors, so two branches share one batch without seeing each other. This idea comes from SpecInfer (Miao et al., 2024) and is used by Medusa and EAGLE.

The program builds a tree with two candidates at depth 1 and two after each of them, prints the mask, and walks down the tree against the target's choices.

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class TreeVerification {
    record Node(int id, int parent, String token) {}

    public static void main(String[] args) {
        // Draft tree: 2 candidates for the next token, and 2 candidates after each of them.
        List<Node> tree = new ArrayList<>();
        tree.add(new Node(0, -1, "range"));                      // last accepted token (root)
        tree.add(new Node(1, 0, "("));
        tree.add(new Node(2, 0, "of"));
        tree.add(new Node(3, 1, "len"));
        tree.add(new Node(4, 1, "n"));
        tree.add(new Node(5, 2, "n"));
        tree.add(new Node(6, 2, "the"));

        // Attention mask: a node sees itself and its ancestors (plus the whole earlier context).
        int size = tree.size();
        boolean[][] mask = new boolean[size][size];
        for (Node node : tree)
            for (int a = node.id(); a != -1; a = tree.get(a).parent()) mask[node.id()][a] = true;
        System.out.println("mask (row = query node, column = key node)");
        for (int i = 0; i < size; i++) {
            StringBuilder row = new StringBuilder(String.format("%d %-6s", i, tree.get(i).token()));
            for (int j = 0; j < size; j++) row.append(mask[i][j] ? " 1" : " .");
            System.out.println(row);
        }

        // One target pass over all 7 nodes gives the target's next token after each node.
        Map<Integer, String> targetNext = Map.of(0, "(", 1, "n", 2, "x", 3, "(", 4, ")", 5, ")", 6, "end");

        // Walk down from the root while the target's choice is one of the children.
        List<String> accepted = new ArrayList<>();
        int cur = 0;
        while (true) {
            String want = targetNext.get(cur);
            int next = -1;
            for (Node child : tree) if (child.parent() == cur && child.token().equals(want)) next = child.id();
            if (next == -1) { accepted.add(want + " (target token)"); break; }
            accepted.add(want);
            cur = next;
        }
        System.out.println("nodes verified in one pass: " + size);
        System.out.println("accepted path: " + accepted);
        System.out.println("tokens gained: " + accepted.size());
        // A single chain holds only the first candidate at each depth: range -> ( -> len.
        System.out.println("chain [(, len] would accept: [(] then target token n, tokens gained: 2");
    }
}

mask (row = query node, column = key node)
0 range  1 . . . . . .
1 (      1 1 . . . . .
2 of     1 . 1 . . . .
3 len    1 1 . 1 . . .
4 n      1 1 . . 1 . .
5 n      1 . 1 . . 1 .
6 the    1 . 1 . . . 1
nodes verified in one pass: 7
accepted path: [(, n, ) (target token)]
tokens gained: 3
chain [(, len] would accept: [(] then target token n, tokens gained: 2

Each mask row lists what a node may look at among the tree nodes. Row 3 (len) sees node 0 (range), node 1 ((), and itself, so the target computes the next token after range ( len. Row 5 (n, under of) sees range of n and never sees (. Positions are assigned by depth, so both depth-2 nodes get the same position id. In a plain causal mask, row 6 would see all earlier rows. The tree mask is what makes the batch equivalent to four separate sequences.

The walk starts at the root:

1. The target wants ( after range. Node 1 is (, so it is accepted.
2. After range ( the target wants n. Node 4 is n, so it is accepted.
3. After range ( n the target wants ). That is not in the tree, so ) is added as the target's own token and the round ends with 3 tokens.

The last line of the output shows the chain that keeps only the first candidate at each depth, ( len. It accepts (, fails at len, and gains 2 tokens. The tree gained one more token than the chain.

The price is batch size. This tree verifies 7 positions for a depth of 2, while a chain of depth 2 verifies 3. Trees pay off while the verification pass is memory-bound (Example 12) and become expensive when the batch already fills the GPU's compute. llama.cpp's examples/speculative builds trees from parallel draft sequences, splitting a branch when a candidate's probability exceeds --spec-draft-p-split (default 0.10). The server path at the pinned commit drafts chains.

Example 10: llama.cpp speculative flags with the tiny model as its own draft

This example runs speculation for real in llama.cpp. The flags are:

• --spec-type selects the method. It defaults to none, and the help lists none,draft-simple,draft-eagle3,draft-mtp,draft-dflash,draft-dspark,ngram-simple,ngram-map-k,ngram-map-k4v,ngram-mod,ngram-cache at the pinned commit 0c1e57098.
• -md (--spec-draft-model) loads a draft model.
• --spec-draft-n-max N sets the draft length k. The default is 3.

The runs use the course's tiny test model, which has random weights, as both target and draft. It writes gibberish, but it is small enough to run anywhere, and it exercises the same code paths as a real model. Tuning llama.cpp introduced these flags. This example reads the numbers more closely. The first command runs the standalone program llama-speculative-simple.

llama-speculative-simple -m tiny-random-qwen2vocab-f32.gguf -md tiny-random-qwen2vocab-f32.gguf \
  --spec-type draft-simple --spec-draft-n-max 4 -p "def add(a, b):" -n 32 --seed 1 -c 512 --temp 0 -t 2

Here are the selected lines from the pinned build (timestamps removed). Look at n_drafted, n_accept, and n_predict.

I common_speculative_init_result: loading draft model 'tiny-random-qwen2vocab-f32.gguf'
I n_draft   = 4
I n_predict = 37
I n_drafted = 29
I n_accept  = 29
I accept    = 100.000%

With greedy sampling and identical models, the target agreed with every guess: 29 of 29 were accepted. This is an unusual best case, because the draft and the target are the same model. n_predict counts every token added. Per round that is the accepted guesses plus the target's own token, so 37 tokens with 29 accepted guesses means 37 - 29 = 8 target passes. The program stops once n_predict exceeds -n 32, so it can overshoot by up to one round.

The server reports the same statistics for each request. The commands below start llama-server with the tiny model as its own draft, send one greedy request and one sampled request, and stop the server.

llama-server -m tiny-random-qwen2vocab-f32.gguf -md tiny-random-qwen2vocab-f32.gguf --spec-type draft-simple \
  --spec-draft-n-max 4 --host 127.0.0.1 --port "$PORT" -np 1 -c 1024 -t 2 &
curl -s "127.0.0.1:$PORT/completion" -d '{"prompt":"def add(a, b):","n_predict":40,"temperature":0}'
curl -s "127.0.0.1:$PORT/completion" -d '{"prompt":"def add(a, b):","n_predict":40,"temperature":0.8,"seed":1}'

The server log lines and the matching timings fields from the pinned build follow. Compare the greedy request and the sampled request.

I slot print_timing: id  0 | task 0 | draft acceptance = 1.00000 (   31 accepted /    31 generated), mean len =  4.88
I slot print_timing: id  0 | task 10 | draft acceptance = 0.00685 (    1 accepted /   146 generated), mean len =  1.03
{'predicted_n': 40, 'draft_n': 31, 'draft_n_accepted': 31}
{'predicted_n': 40, 'draft_n': 146, 'draft_n_accepted': 1}

The greedy request produced 40 tokens with 31 drafted and 31 accepted. The first token comes from the prompt pass, and the other 39 came from rounds: 39 = 31 accepted + 8 target tokens, so there were 8 rounds. Seven rounds drafted the full 4 tokens and the last drafted 3, because the server limits a draft to the remaining budget minus one (get_n_draft_max in tools/server/server-context.cpp): 7 × 4 + 3 = 31. Mean len is the mean acceptance length from Example 8: 1 + 31/8 = 4.875, printed as 4.88.

The sampled request at temperature 0.8 accepted 1 of 146 drafts, and the mean length fell to 1.03 (1 + 1/38, with 38 rounds for 39 tokens and one accepted draft). The reason is the match rule from Example 5. The draft proposes its most likely token, and the target samples from its own distribution, so a guess is accepted only when the sample happens to equal that token. A random-weight model over 151,936 tokens has an almost flat distribution, so its most likely token has a tiny probability. Trained models are far more peaked, and docs/speculative.md shows example statistics with acceptance rates of 0.576 and 0.703.

The draft-free method needs no -md. The next command uses ngram-simple instead.

llama-server -m tiny-random-qwen2vocab-f32.gguf --spec-type ngram-simple \
  --spec-ngram-simple-size-n 3 --spec-ngram-simple-size-m 8 --host 127.0.0.1 --port "$PORT" -np 1 -c 1024 -t 2

I slot print_timing: id  0 | task 0 | draft acceptance = 0.00000 (    0 accepted /     8 generated), mean len =  1.00

ngram-simple looks for the last 3 tokens earlier in the context (--spec-ngram-simple-size-n, default 12) and drafts up to 8 following tokens (--spec-ngram-simple-size-m, default 48). During the 64-token answer it found one match and drafted 8 tokens, and none were accepted. The random model does not copy its context. On a trained model rewriting a file, Example 6 shows the opposite.

Other flags from common/arg.cpp at this commit:

Speculation also appears in /metrics and in the timings object of every response (draft_n, draft_n_accepted), which a benchmark client can log for each request.

Example 11: vLLM speculative decoding configuration

vLLM is a serving engine for GPUs. In vLLM 0.30.0, every speculative setting is a field of SpeculativeConfig in vllm/config/speculative.py. You pass the settings as one JSON object with --speculative-config (short form -sc), or through the shortcut flags --spec-method, --spec-model, and --spec-tokens (vllm/engine/arg_utils.py). A shortcut and the same key in the JSON together raise an error.

The program has two parts. First, it builds four configurations with Jackson (a Java JSON library), one for each kind of draft. Second, it decodes a statistics line written in the format of vllm/v1/spec_decode/metrics.py, to show how to read the numbers. The numbers in the line are illustrative.

import com.fasterxml.jackson.databind.ObjectMapper;
import java.util.LinkedHashMap;
import java.util.Locale;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class VllmSpecConfig {
    public static void main(String[] args) throws Exception {
        ObjectMapper json = new ObjectMapper();
        Map<String, Map<String, Object>> configs = new LinkedHashMap<>();
        configs.put("n-gram", obj("method", "ngram", "num_speculative_tokens", 4, "prompt_lookup_max", 4));
        configs.put("draft model", obj("method", "draft_model", "model", "Qwen/Qwen3-0.6B", "num_speculative_tokens", 3));
        configs.put("EAGLE-3", obj("method", "eagle3", "model", "AngelSlim/Qwen3-8B_eagle3", "num_speculative_tokens", 3));
        configs.put("MTP", obj("method", "mtp", "num_speculative_tokens", 1));
        for (var e : configs.entrySet())
            System.out.printf("%-12s --speculative-config '%s'%n", e.getKey(), json.writeValueAsString(e.getValue()));

        // A metrics line in the format of vllm/v1/spec_decode/metrics.py (numbers are illustrative).
        String line = "SpecDecoding metrics: Mean acceptance length: 2.65, Accepted throughput: 82.50 tokens/s, "
                + "Drafted throughput: 150.00 tokens/s, Accepted: 1650 tokens, Drafted: 3000 tokens, "
                + "Per-position acceptance rate: 0.750, 0.530, 0.370, Avg Draft acceptance rate: 55.0%";
        int accepted = num(line, "Accepted: (\\d+) tokens"), drafted = num(line, "Drafted: (\\d+) tokens");
        String[] rates = find(line, "Per-position acceptance rate: ([0-9., ]+), Avg").split(", ");
        int k = rates.length, drafts = drafted / k;               // every draft had k tokens here
        double sumRates = 0;
        for (String r : rates) sumRates += Double.parseDouble(r);
        System.out.printf(Locale.ROOT, "k=%d, drafts=%d, accepted per draft=%.3f%n", k, drafts, (double) accepted / drafts);
        System.out.printf(Locale.ROOT, "mean acceptance length = 1 + %d/%d = %.2f%n", accepted, drafts, 1 + (double) accepted / drafts);
        System.out.printf(Locale.ROOT, "1 + sum of per-position rates = %.2f%n", 1 + sumRates);
        System.out.printf(Locale.ROOT, "draft acceptance rate = %d/%d = %.1f%%%n", accepted, drafted, 100.0 * accepted / drafted);
    }

    static Map<String, Object> obj(Object... kv) {               // keeps keys in the order given
        Map<String, Object> m = new LinkedHashMap<>();
        for (int i = 0; i < kv.length; i += 2) m.put((String) kv[i], kv[i + 1]);
        return m;
    }

    static String find(String s, String regex) {
        Matcher m = Pattern.compile(regex).matcher(s);
        if (!m.find()) throw new IllegalArgumentException(regex);
        return m.group(1);
    }

    static int num(String s, String regex) { return Integer.parseInt(find(s, regex)); }
}

n-gram       --speculative-config '{"method":"ngram","num_speculative_tokens":4,"prompt_lookup_max":4}'
draft model  --speculative-config '{"method":"draft_model","model":"Qwen/Qwen3-0.6B","num_speculative_tokens":3}'
EAGLE-3      --speculative-config '{"method":"eagle3","model":"AngelSlim/Qwen3-8B_eagle3","num_speculative_tokens":3}'
MTP          --speculative-config '{"method":"mtp","num_speculative_tokens":1}'
k=3, drafts=1000, accepted per draft=1.650
mean acceptance length = 1 + 1650/1000 = 2.65
1 + sum of per-position rates = 2.65
draft acceptance rate = 1650/3000 = 55.0%

The first four output lines are complete vllm serve arguments. In each, num_speculative_tokens is k.

• The n-gram configuration sets prompt_lookup_max to 4, the longest n-gram to match. When only the maximum is given, the source sets prompt_lookup_min to the same value, and when neither is given it sets both to 5.
• The draft-model configuration names a small model of the same family.
• The EAGLE-3 configuration names a head trained for Qwen3-8B (a repository listed in llama.cpp's docs/speculative.md).
• The MTP configuration has no model. For mtp, __post_init__ sets the draft model to the target model itself, because the MTP modules ship inside the target checkpoint.

When method is omitted, vLLM detects it from the model or falls back to draft_model.

The statistics line is logged periodically by the engine, and the program recovers the numbers from it step by step:

• 3,000 drafted tokens in drafts of 3 means 1,000 drafts.
• The mean acceptance length is 1 + accepted / drafts = 1 + 1650/1000 = 2.65. This is the definition in the source ("Conventionally, mean acceptance length includes the bonus token"), where the bonus token is the target's own token.
• The per-position rates 0.750, 0.530, 0.370 are the unconditional rates from Example 8, and 1 + 0.750 + 0.530 + 0.370 = 2.65 gives the same number from the other direction.
• The draft acceptance rate, 55.0%, is accepted tokens over drafted tokens, 1650 over 3000. It is the same kind of quantity as the α of Example 2.

The same counters exist as Prometheus metrics (a standard format for monitoring numbers): vllm:spec_decode_num_drafts, vllm:spec_decode_num_draft_tokens, vllm:spec_decode_num_accepted_tokens, and vllm:spec_decode_num_accepted_tokens_per_pos.

Other fields in SpeculativeConfig at 0.30.0 include:

• draft_tensor_parallel_size, which is 1 or the target's value.
• rejection_sample_method, which is standard, synthetic, or block.
• draft_sample_method. The default greedy treats draft probabilities as one-hot (all probability on one token). probabilistic keeps the full draft scores for the ratio test of Example 5.
• num_speculative_tokens_per_batch_size, a schedule that lowers k as the batch grows. That last field exists because of the effect in the next example.

Example 12: when speculation does not help

Speculation can also make decoding slower. Example 4 assumed that verifying k+1 positions costs as much as decoding one position. That holds only while a step is memory-bound. When many users share one GPU, each step handles many tokens, the arithmetic units become busy, and extra guesses stop being free.

The program applies the roofline model to an 8B FP16 model on one H100 SXM GPU. The figures are the ones used in the roofline lesson: 16 GB of weights, 3.35 TB/s of memory bandwidth, 16 GFLOPs of arithmetic per token, and 989 TFLOP/s of dense BF16 compute. A step takes as long as the slower of two times: the time to read the weights, and the time to do the arithmetic for all tokens in the step. The program serves batch users at once, each speculating with k = 4, and compares throughput with and without speculation.

import java.util.Locale;

public class WhenItHurts {
    // Roofline step time for one forward pass over `tokens` tokens of an 8B FP16 model on one H100 SXM.
    static final double WEIGHT_BYTES = 16e9, BANDWIDTH = 3.35e12;        // bytes, bytes/s
    static final double FLOPS_PER_TOKEN = 16e9, PEAK = 989e12;           // FLOPs, FLOP/s

    static double stepMs(int tokens) {
        double memory = WEIGHT_BYTES / BANDWIDTH, compute = tokens * FLOPS_PER_TOKEN / PEAK;
        return Math.max(memory, compute) * 1000;
    }

    static double expected(double alpha, int k) { return (1 - Math.pow(alpha, k + 1)) / (1 - alpha); }

    public static void main(String[] args) {
        int k = 4;
        double alpha = 0.7, draftCost = 0.05;                     // draft step = 5% of a target step
        System.out.println("batch  plain ms/step  spec ms/round  plain tok/s  spec tok/s  speedup");
        for (int batch : new int[] {1, 8, 32, 64, 128, 256}) {
            double plain = stepMs(batch);
            double round = stepMs(batch * (k + 1)) + k * draftCost * stepMs(batch);
            double plainRate = batch / plain * 1000;
            double specRate = batch * expected(alpha, k) / round * 1000;
            System.out.printf(Locale.ROOT, "%5d  %13.2f  %13.2f  %11.0f  %10.0f  %6.2fx%n",
                    batch, plain, round, plainRate, specRate, specRate / plainRate);
        }
        System.out.printf(Locale.ROOT, "compute-bound above %.0f tokens per step%n",
                WEIGHT_BYTES / BANDWIDTH * PEAK / FLOPS_PER_TOKEN);
        for (double a : new double[] {0.3, 0.1})
            System.out.printf(Locale.ROOT, "batch 1, alpha=%.1f: speedup %.2fx%n", a,
                    expected(a, k) / ((stepMs(k + 1) + k * draftCost * stepMs(1)) / stepMs(1)));
    }
}

batch  plain ms/step  spec ms/round  plain tok/s  spec tok/s  speedup
    1           4.78           5.73          209         484    2.31x
    8           4.78           5.73         1675        3871    2.31x
   32           4.78           5.73         6700       15483    2.31x
   64           4.78           6.13        13400       28942    2.16x
  128           4.78          11.31        26800       31387    1.17x
  256           4.78          21.66        53600       32771    0.61x
compute-bound above 295 tokens per step
batch 1, alpha=0.3: speedup 1.19x
batch 1, alpha=0.1: speedup 0.93x

At batch 1, a plain step reads 16 GB in 4.78 ms. A speculative round verifies 5 positions in the same 4.78 ms, because it is still memory-bound, and adds four draft steps at 5% each, 4 × 0.05 × 4.78 = 0.96 ms, for 5.73 ms in total. It yields 2.773 tokens (α = 0.7, k = 4), so throughput rises from 209 to 484 tokens per second, which is 2.31 times.

The line compute-bound above 295 tokens per step is the crossover point. Memory time is 16e9 / 3.35e12 seconds, and it equals the compute time 295 × 16e9 / 989e12 seconds. Below 295 tokens per step the GPU waits for memory and extra positions are free. Above it, every extra position costs real time. The table shows what happens as the batch grows:

• At batch 64, a speculative round verifies 64 × 5 = 320 positions, slightly past the crossover, and the gain drops to 2.16 times.
• At batch 128, the round verifies 640 positions and takes 11.31 ms, and the gain is only 1.17 times.
• At batch 256, the plain step still fits under the crossover (256 tokens). The speculative round computes 1,280 positions, many of them guesses that will be rejected, and throughput falls to 0.61 times plain.

A busy server already uses the arithmetic that speculation spends on guesses.

The last two lines vary acceptance at batch 1. At α = 0.3, a round yields 1.43 tokens and costs 1.2 step units, which is 1.19 times. At α = 0.1, it yields 1.11 tokens for the same cost, and speculation loses (0.93 times). Low acceptance comes from high sampling temperature (Example 10), from a draft trained on different data, or from text the draft cannot predict, such as a long list of new identifiers.

The conditions where speculation helps less or hurts, collected:

Interview points

• Speculative decoding uses spare compute during memory-bound decoding. The target verifies k guesses in one pass, which costs about the same as decoding one token, and every round adds at least one token.
• Greedy verification accepts the longest prefix of guesses that equals the target's most likely tokens, then appends the target's own token. The output is identical to plain greedy decoding.
• With acceptance probability α and draft length k, the expected tokens per pass is (1 - α^(k+1)) / (1 - α), which is bounded by 1 / (1 - α). The speedup divides this by 1 + k·c, where c is the draft cost relative to a target step.
• Speculative sampling accepts a token x with probability min(1, p(x)/q(x)) and otherwise resamples from the normalized max(0, p - q). The output distribution equals p, and the acceptance rate is Σ min(p, q).
• llama.cpp's server verification samples the target and accepts on equality. This keeps the target distribution but accepts less often than the ratio rule when sampling.
• Prompt lookup and n-gram drafting need no model and work well for code edits, where the output copies the input.
• A draft model must share the target's tokenizer. llama.cpp checks the vocabulary type, BOS and EOS, a size difference of at most 128, and token texts from id 5.
• EAGLE, Medusa, and MTP attach trained draft heads to the target. Tree verification checks several branches in one pass with an attention mask that lets each node see only its ancestors.
• In vLLM, --speculative-config takes JSON with method, model, and num_speculative_tokens. The mean acceptance length is 1 + accepted / drafts.
• At large batch sizes, verification becomes compute-bound and speculation can lower throughput. vLLM can shrink k as the batch grows.

Summary

• One speculative round drafts k tokens, runs one target pass over k+1 positions, accepts the agreeing prefix, and appends one target token.
• In the toy run, 26 tokens took 11 target passes instead of 26, with an acceptance rate of 0.341 and identical output.
• With α = 0.8 and k = 4, one pass yields 3.3616 tokens on average, and a 100,000-round simulation measured 3.3590.
• With α = 0.8 and c = 0.1, the best draft length is 6, for a 2.47 times speedup. With c = 1, no draft length helps.
• Rejection sampling with the p and q from the example reproduced p within 0.002 and accepted 69.85% of proposals against a predicted 70%.
• Prompt lookup rewrote a 30-token method in 8 target passes with no draft model.
• In llama.cpp, --spec-type defaults to none, --spec-draft-n-max defaults to 3, -md loads a draft model, and the n-gram types need no model.
• The tiny model as its own draft accepted 31 of 31 greedy drafts (mean len 4.88) and 1 of 146 at temperature 0.8.
• vLLM's SpeculativeConfig methods include ngram, draft_model, eagle, eagle3, medusa, mtp, and suffix. The mtp method uses the target checkpoint as the draft.
• vLLM logs the mean acceptance length, the per-position acceptance rates, and the draft acceptance rate, and exports vllm:spec_decode_* metrics.
• For an 8B FP16 model on an H100, decoding becomes compute-bound above about 295 tokens per step. Speculation with k = 4 drops from 2.31 times to 0.61 times as the batch grows from 1 to 256.