M7.7 - Draft Sources, Dependent Heads, and Hardware-Aware Trees

M7.7 - Draft Sources, Dependent Heads, and Hardware-Aware Trees

0x00 Overview And Background

M7.1 derived exact draft-and-verify sampling. M7.2 built a tree from same-model prediction heads. M7.5 moved drafting into feature space, and M7.6 followed a causal MTP module chain.

Those mechanisms leave a broader systems question unanswered:

Which proposal source and candidate topology should a runtime use once draft latency, proposal dependence, tree verification, exactness, cache state, batch size, and the target hardware are all counted?

A speculative decoder has five separable design decisions:

proposal source:
    where candidate tokens, scores, and provisional state come from

candidate topology:
    sequence, one-position set, prefix tree, or metadata graph

probability contract:
    normalized conditional q, frequency, ranking score, or absent

target selection contract:
    greedy match, target-sample membership, rejection sampling,
    multi-candidate coupling, or another proved verifier

publication contract:
    which output tokens and target-computed state become authoritative

Changing the proposal source does not automatically change the target distribution. Changing the tree does not automatically improve wall-clock time. A larger acceptance length is useful only when the proposal, packing, verification, selection, and temporary-state costs remain below the target steps it replaces.

The proposer does not publish output. It emits typed evidence that a compatible target verifier may consume. Only the publication step advances the authoritative prefix and target cache.

Background knowledge: a proposal is not yet a decoded token

A proposed token is provisional. It may come from a small language model, a suffix match, an early layer, an auxiliary head, or a feature drafter. The target model still owns the output contract.

proposal quality decides:
    how often useful candidate paths exist

proposal topology decides:
    how many alternatives fit in one verification pass

verification decides:
    which output distribution is actually sampled

cache commit decides:
    which target-computed states survive into the next round

This distinction matters for retrieval. A retrieved continuation can be an excellent candidate without defining a normalized token distribution $q$. It can be verified by sampling from the target and testing tree membership, but it cannot be silently substituted into the one-draft $p/q$ acceptance formula.

Historical lineage and owner contract

The methods in this article did not appear as one architecture family. They answer different bottlenecks that became visible after basic speculative decoding existed:

This article owns the interfaces among those choices. M7.1 owns the one-sequence acceptance derivation; M7.2 owns tree attention; M7.5 and M7.6 own feature and integrated-MTP drafters; M7.8 owns multi-request scheduling, release, and rollback. M7.7 consumes those mechanisms without thinning or duplicating them.

0x01 Claim Status And Scope

This article owns proposal generation, candidate-shape compilation, verifier compatibility, and offline hardware-calibrated selection. M7.8 owns the online multi-request controller and production lifecycle.

0x02 A Common Proposal-System Interface

Let the committed prefix be $x_{\le t}$. A proposer returns a typed result, not merely a list of token ids:

$$\mathcal{G}_t = \operatorname{Propose}(x_{\le t}, S_{prop})$$

where $S_{prop}$ is proposal-side state: a draft KV cache, retrieval cursor, shallow-layer cache, head state, or feature-drafter state. The result has five classes of fields:

@dataclass(frozen=True)
class ProposalResult:
    nodes: list[ProposalNode]
    probability_semantics: Literal[
        "normalized_conditional", "score_only", "frequency", "absent"
    ]
    sampling_relation: Literal[
        "iid", "without_replacement", "beam", "deterministic_lookup"
    ]
    topology: Literal["sequence", "set", "tree", "metadata_graph"]
    state_handle: ProposalStateHandle
    manifest_hash: str

The graph contains nodes $v\in V$ with:

$$v= (\operatorname{token}(v),\operatorname{parent}(v),\operatorname{depth}(v), q_v,s_v,\operatorname{source}(v),\operatorname{state\_owner}(v))$$

$q_v$ is optional and $s_v$ is an optional ranking score. A parametric draft model can provide the conditional proposal probability for a node. Prompt lookup and exact-match retrieval may provide scores or frequencies that are useful for ranking but are not automatically the $q$ required by rejection sampling. Keeping q and score in separate fields prevents a convenient but invalid cast.

The runtime linearizes the graph into target inputs:

token_ids:       [N_nodes]
parent_index:    [N_nodes]
position_ids:    [N_nodes]
ancestor_mask:   [N_nodes, prefix_len + N_nodes]
proposal_prob:   [N_nodes] or absent
proposal_score:  [N_nodes] or absent
source_id:       [N_nodes]
state_owner:     [N_nodes]
origin_request:  [N_nodes]

The target computes one hidden/KV row for every candidate token under its ancestor path. The distribution that scores a candidate, however, comes from the parent coordinate:

$$p(\operatorname{token}(v)\mid x_{\le t},\operatorname{Ancestors}(v)) = \begin{cases} p_{frontier}(\operatorname{token}(v)), & \operatorname{parent}(v)=-1,\\ p_{\operatorname{parent}(v)}(\operatorname{token}(v)), & \text{otherwise.} \end{cases}$$

The row for $v$ processes token(v) and predicts its children. It does not predict itself. This one-row offset is a frequent implementation error because the tensors remain shape-correct.

0x02A Verifier capability negotiation

The runtime must reject an incompatible pair before target execution:

def bind_verifier(proposal, verifier):
    assert verifier.supports_probability(proposal.probability_semantics)
    assert verifier.supports_sampling_relation(proposal.sampling_relation)
    assert verifier.supports_topology(proposal.topology)
    return BoundRound(proposal=proposal, verifier=verifier)

A heterogeneous graph from Hydra and REST cannot invent one $q$ by attaching Hydra probabilities to some rows and retrieval frequencies to others. Either define and sample from a normalized mixture proposal, use a verifier such as target-sample membership that does not require $q$, or verify the subgraphs under separately proved contracts.

0x02B Immutable round manifest

Before the first proposal, freeze:

target checkpoint + tokenizer + output head
sampling policy, temperature, truncation, RNG policy
proposal checkpoint / index / skip pattern / head package
probability semantics and sampling relation
topology compiler version and node/depth limits
verifier algorithm and exact/heuristic mode
target and proposal cache generations
kernel/backend, dtype, batch regime, and hardware profile

The manifest is not administrative metadata. A tokenizer change alters retrieved token spans; a sampling-policy change alters acceptance statistics; a target-kernel change alters the measured tree optimum; and a cache-generation mismatch can turn valid ids into stale state.

0x02C Round Cost, Not Acceptance Alone

For candidate graph $\mathcal{G}$, define:

$$C_{round}(\mathcal{G}) = C_{prop} +C_{retrieve} +C_{pack} +C_T(|V|,\operatorname{shape}(\mathcal{G})) +C_{select} +C_{state}$$

If $N_{commit}$ target-valid output tokens are produced in the round, then:

$$\operatorname{time/token} = \frac{C_{round}(\mathcal{G})} {\mathbb{E}[N_{commit}]}$$

Relative to ordinary target decoding cost $C_{AR}$ per token:

$$\operatorname{speedup} \approx \frac{C_{AR}\,\mathbb{E}[N_{commit}]} {C_{round}(\mathcal{G})}$$

This equation explains why the highest-accuracy proposal can lose. A large draft model may increase $\mathbb{E}[N_{commit}]$ while increasing $C_{prop}$ even more. A wide tree may improve first-token coverage while moving $C_T$ into a less favorable kernel regime.

Renderer-safe ledger:

round_cost = proposal + retrieval + packing + target_verify
           + selection + temporary_state

time_per_committed_token = round_cost / E[committed_tokens]

speedup requires:
    E[committed_tokens] > round_cost / target_AR_step_cost

0x03 Draft-Source Taxonomy

No row dominates every workload. The source must be chosen with the target checkpoint, output policy, memory budget, batch regime, and request domain in view.

0x04 Non-Parametric Drafting: Prompt Lookup And REST

0x04A Prompt Lookup

Prompt lookup searches the existing prefix for an n-gram ending at the current position and copies the tokens that followed an earlier occurrence.

For prefix tokens:

[A, B, C, D, A, B, C]

the suffix [A,B,C] matches the earlier prefix, so D is a candidate next token. Longer continuations can be copied until the match ends or a configured candidate budget is reached.

def prompt_lookup(tokens, max_ngram, max_candidates):
    for n in range(min(max_ngram, len(tokens)), 0, -1):
        suffix = tokens[-n:]
        starts = find_previous_occurrences(tokens[:-n], suffix)
        if starts:
            start = starts[-1] + n
            return tokens[start : start + max_candidates]
    return []

The current Transformers assisted-decoding documentation exposes prompt lookup through prompt_lookup_num_tokens, with a maximum matching n-gram size. That is an implementation boundary, not a guarantee that all runtimes use the same index, tie-breaking, or cache path.

Prompt lookup has no standalone draft weights or draft KV cache. Its quality is highly workload-dependent: source code, templated text, and repeated documents create useful matches; unconstrained conversation may not.

0x04B REST: Move The Repetition Source Into A Datastore

REST builds a datastore of context-continuation pairs:

$$\mathcal{D}=\{(c_i,t_i)\}_{i=1}^{N}$$

At inference, it searches for contexts whose suffix matches the longest suffix of the current prefix. If no match exists at length $n$, it decrements $n$ until candidates appear.

$$S = \{t_i:(c_i,t_i)\in\operatorname{Retrieve}(\mathcal{D},x_{\le t})\}$$

The retrieved continuations are inserted into a trie. Every trie node stores a prefix frequency. REST prunes to a candidate-node budget and linearizes the remaining subtree for tree-attention verification.

Source: REST, Figure 1. Retrieval returns continuations after the longest matching suffix; duplicate prefixes accumulate frequency in a trie; pruning turns frequency into a finite candidate budget; tree attention verifies the surviving paths. None of those frequencies is automatically a calibrated draft probability.

def rest_propose(prefix, datastore, max_suffix, node_budget):
    matches = []
    for n in range(max_suffix, 0, -1):
        matches = datastore.exact_suffix(prefix[-n:])
        if matches:
            break

    trie = ContinuationTrie()
    for continuation in matches:
        trie.insert(continuation, increment_frequency=True)

    return trie.keep_high_frequency_nodes(node_budget)

REST avoids a parametric draft model, but does not avoid systems work:

offline:
    corpus selection -> tokenization -> context/continuation extraction
    -> suffix index construction -> versioning

online:
    suffix query -> retrieve continuations -> trie merge -> prune
    -> linearize -> build ancestry mask -> target verify

Its paper uses target-model sampling and accepts a retrieved child when it matches the target-sampled token. This preserves the target’s ordinary sampling path without pretending trie frequency is a calibrated draft probability.

0x04C Source-to-index trace and release lifecycle

Assume the tokenized corpus contains:

[4, 5, 6, 9, 4, 5, 6, 10, 11]

For query suffix [4,5,6], exact occurrences end before 9 and before 10,11. The retrieved continuation multiset is therefore:

[9, 4, 5, 6, 10, 11]
[10, 11]

The first continuation is long because retrieval reads forward in the corpus; the second reaches the corpus boundary. The two root children are tied: 9 starts one retrieved continuation and 10 starts one. The later 10 in the first continuation belongs to the separate full prefix [9,4,5,6,10]; it does not increment the root child [10].

root child [9]:             count 1
root child [10]:            count 1
full prefix [9,4,5,6,10]:   count 1  (a different trie node)
root-child order on a tie: [9, 10]

For this toy example, rank siblings by descending prefix count, then ascending token ID on ties. Thus 9 precedes 10 only because of the declared tie-break, not because either root is more frequent. This is a local illustrative rule, not a claim about the official implementation’s tie-breaking. It specifies sibling order, not a complete global node-budget pruning policy. Trie counts remain corpus statistics, not $q(10\mid x_{\le t})$.

The official REST implementation follows this shape: initialize target cache, search increasingly shorter suffixes, build tree buffers, assign a draft mask, run target tree decoding, evaluate the posterior, and update the target cache. That trace also exposes non-paper engineering choices such as batch-size-one assumptions and repository-specific empty-retrieval fallback behavior. Those choices are implementation-observed, not part of REST’s algorithmic contract.

An index release must bind at least:

corpus snapshot and license/governance policy
train/evaluation exclusion manifest
tokenizer files and normalization
context length and continuation length
suffix key encoding and endianness
frequency counter width
trie pruning and tie-breaking policy
index checksum and builder commit
target checkpoint family used for calibration

Evaluation leakage is a proposal-quality leak even when target verification keeps the output distribution valid. If benchmark answers occur in the datastore, acceptance and latency results no longer measure the intended generalization setting. Exactness is not a defense against contaminated evaluation.

0x04D Prompt Lookup Versus Retrieval

0x05 Self-Speculation: Reuse The Target Without Reusing All Its Work

0x05A Draft & Verify: A Fixed Skipped-Layer Path

Source: Draft & Verify, introductory self-speculation figure. The green path skips selected target layers while drafting; the blue path executes full verification. Accepted green tokens, rejected red tokens, and the extra blue target prediction make the output/state boundary visible.

Draft & Verify represents the draft architecture by a binary layer-skip vector:

$$z\in\{0,1\}^{L}$$

where one value denotes that a layer is bypassed during drafting. The full target path uses all layers.

The best skip vector is not the one with the highest acceptance rate. No skipped layers would maximize agreement but perform essentially the target computation. The paper instead minimizes average inference time per verified token on a development set:

$$z^* = \arg\min_{z\in\{0,1\}^{L}}f(z)$$

where $f(z)$ includes both draft and verification time divided by the verified-token count. The search space has $2^L$ patterns, so the paper uses Bayesian optimization rather than exhaustive enumeration for large models.

For development requests $r\in\mathcal{R}_{dev}$, a concrete objective is:

$$f(z) = \frac{\sum_{r\in\mathcal{R}_{dev}} \left(T_{draft}^{(r)}(z)+T_{verify}^{(r)}(z)+T_{state}^{(r)}(z)\right)} {\sum_{r\in\mathcal{R}_{dev}}N_{verified}^{(r)}(z)}.$$

The denominator explains why acceptance alone is insufficient. Setting $z=0$ makes the draft equal to the target and tends toward perfect agreement, but it also repeats target-priced work. Setting nearly every component of $z$ to “skip” minimizes draft layers but can collapse verified progress. The optimizer must observe both effects together.

too few skipped layers:
    high agreement, expensive draft

too many skipped layers:
    cheap draft, low acceptance, wasted suffixes

wrong skipped-layer pattern:
    can be worse than another pattern with the same number of layers

Draft length is also dynamic. If the current draft token confidence falls below threshold $\gamma$, drafting stops. The threshold is adjusted from a moving acceptance-rate estimate toward a target acceptance rate.

acceptance_ema = beta1 * acceptance_ema + (1 - beta1) * round_acceptance

if acceptance_ema <= target_acceptance:
    threshold_candidate = gamma + epsilon
else:
    threshold_candidate = gamma - epsilon

gamma = beta2 * gamma + (1 - beta2) * threshold_candidate

This control loop is heuristic policy, not part of speculative-sampling exactness. Exactness still comes from full-target verification.

0x05B Kangaroo: Shallow Shared Trunk, Adapter, Second Exit

Source: Kangaroo, framework figure. Frozen target layers and LM head are blue; the small trainable adapter is orange. The second exit stops low-confidence drafting, while retained shallow features feed the remaining target layers during verification.

Kangaroo avoids running an arbitrary skipped-layer network for each draft token. It reuses a fixed shallow target subnetwork $M_b[:l]$ and trains a small adapter $A$:

$$M_s=A\circ M_b[:l]$$

The adapter bridges shallow features to the target’s output space and reuses the target LM head. In the paper, the adapter contains attention and normalization without a full FFN-heavy draft model.

For a draft sequence of $K$ positions, the important shapes are:

shallow hidden:       F_l        [B, K, d]
adapter attention:    A(F_l)     [B, K, d]
shared LM logits:     Z_s        [B, K, V]
full upper layers:    M_b[l:](F) [B, K, d]
target logits:        Z_t        [B, K, V]

Kangaroo’s adapter is intentionally smaller than a copied Transformer block: one multi-head attention path plus two normalization operations, with no full FFN in the reported design. The target LM head maps both adapter output and full-target output into vocabulary space. Shared output weights do not imply shared hidden-state semantics.

The adapter is trained by distillation from the target distribution:

$$\mathcal{L}_{adapter} = -\sum_t\sum_{v\in\mathcal{V}} M_{b,v}(x_{\le t}) \log M_{s,v}(x_{\le t})$$

Drafting exits when top-1 confidence falls below $\eta$:

$$\max_v M_{s,v}(x_{\le t})\le\eta$$

Kangaroo also keeps the shallow feature for the stopped position so the remaining target layers can process a parallel unit during verification. This exposes an implementation advantage that an abstract “same model drafts itself” label hides: intermediate target features can be reused only when their provenance and layer boundary match the full verification path.

The adapter loss is a soft-target cross-entropy. If target logits are $z_t$ and shallow-adapter logits are $z_s$, with temperature $\tau$:

$$p_t^{(\tau)}=\operatorname{softmax}(z_t/\tau),\qquad p_s^{(\tau)}=\operatorname{softmax}(z_s/\tau),$$ $$\mathcal{L}_{KD} = -\tau^2\sum_{i,v}p_{t,i,v}^{(\tau)}\log p_{s,i,v}^{(\tau)}.$$

The frozen target owns the teacher distribution. Adapter parameters receive gradients; shallow target layers and the shared LM head remain frozen in the paper’s setup. This is a different training contract from Draft & Verify, which searches a skip pattern but trains no new network.

0x05C Self-Draft State Contract

authoritative state:
    committed target KV and output tokens

provisional state:
    shallow/skipped-path hidden rows
    draft logits
    candidate token ids
    draft confidence

verification state:
    full-path target rows for each candidate position

A runtime must never relabel skipped-path or shallow-adapter state as final target state merely because the token is later accepted. Reuse is valid only where the method proves that the cached tensor is exactly the tensor the target path needs.

After computational-path equivalence has been established, the following predicate is a necessary metadata check, not a proof that the tensors are equal. Matching these fields alone cannot make skipped-path activations equivalent to full-target activations:

def may_reuse(candidate_state, target_need):
    return (
        candidate_state.checkpoint == target_need.checkpoint
        and candidate_state.layer_boundary == target_need.layer_boundary
        and candidate_state.token_id == target_need.token_id
        and candidate_state.position == target_need.position
        and candidate_state.ancestry_hash == target_need.ancestry_hash
        and candidate_state.dtype == target_need.dtype
        and candidate_state.cache_generation == target_need.cache_generation
    )

Draft & Verify can reuse target-compatible portions of the common path only where path equivalence has been proved and that predicate is true. Kangaroo can pass a shallow feature into the remaining target layers because the architecture explicitly defines that boundary. Neither method may publish a skipped-path upper-layer KV row as if the full target had computed it.

0x06 Independent And Dependent Draft Heads

0x06A Why Independent Heads Lose Conditional Information

Let $h_t$ be the target hidden state at the current prefix. A bank of standard future-token heads predicts:

$$q_i(x_{t+i}\mid x_{\le t}) = \operatorname{softmax}(H_i(h_t))$$

Each head sees the same prefix representation. The joint proposal implied by independent heads is:

$$q_{ind}(x_{t+1:t+K}\mid x_{\le t}) = \prod_{i=1}^{K} q_i(x_{t+i}\mid x_{\le t})$$

The target’s causal factorization is instead:

$$p(x_{t+1:t+K}\mid x_{\le t}) = \prod_{i=1}^{K} p(x_{t+i}\mid x_{\le t},x_{t+1:t+i-1})$$

The missing condition is the earlier drafted continuation. Head 3 may predict a grammatically plausible third token that is inconsistent with the tokens chosen by heads 1 and 2.

0x06B Hydra: Condition On Earlier Drafted Embeddings

Source: Hydra, Figure 1. Standard draft heads receive only the base hidden state, so later heads do not know the tokens chosen by earlier heads. Hydra feeds earlier sampled-token embeddings into later heads. The orange dependency arrows improve conditional consistency but lengthen the proposal critical path.

Hydra parameterizes future head $i$ with the prefix hidden state and earlier drafted-token embeddings:

$$q_i^{Hydra} \left( \hat x_{t+i} \mid x_{\le t},\hat x_{t+1:t+i-1} \right) = f_i^{Hydra} \left( h_{t-1},E(x_t),E(\hat x_{t+1}),\ldots,E(\hat x_{t+i-1}) \right)$$

The basic paper architecture concatenates these vectors into an MLP input. This restores explicit sequential dependence, but the heads can no longer all finish at once.

Hydra++ compares additional design choices:

1. scale each head MLP to four layers;
2. distill the target distribution instead of only predicting hard ground-truth labels;
3. add a prefix-attention decoder layer that produces a richer draft input once per decoding round.

The target backbone remains frozen in the paper’s experiments. Basic Hydra/Medusa heads were trained for one epoch in that setup; Hydra++ heads were trained longer. Those are source-reported recipes, not universal hyperparameters.

Hydra source-to-tensor trace

Let the verified prefix end at token $x_t$, and let head $i$ predict $x_{t+i}$. Under teacher forcing its input is:

$$u_{t,i} = \operatorname{Concat} \left(h_{t-1},E(x_t),E(x_{t+1}),\ldots,E(x_{t+i-1})\right).$$

At runtime, ground-truth future embeddings are replaced by the selected earlier proposals. For batch size $B$ and hidden width $d$, basic head $i$ therefore receives [B, (i+1)d] if the base hidden and each token embedding have width $d$. Later heads are larger in their first projection and cannot complete before earlier tokens are selected.

The following zero-based teaching sketch requires an active predecessor in the same document occurrence. It skips the first token of each segment rather than inventing an initial hidden state. If BOS is needed, the caller includes an actual BOS token and its target hidden row inside that segment; the first content token can then use that row. Never wrap to hidden[-1], borrow a previous document’s row, or clamp the index to hidden[t].

def hydra_teacher_rows(tokens, hidden, max_future, *, segment_ids, valid):
    # hidden[j] is the target state AFTER tokens[j], computed segment-causally.
    # valid is input availability, not a loss-only supervision mask.
    n = len(tokens)
    if not (len(hidden) == len(segment_ids) == len(valid) == n):
        raise ValueError("unaligned packed inputs")
    if type(max_future) is not int or max_future < 0:
        raise ValueError("max_future must be a nonnegative integer")
    if any(type(flag) is not bool for flag in valid):
        raise ValueError("valid must contain booleans")

    rows = []
    for t in range(1, n):
        for i in range(1, min(max_future, n - t - 1) + 1):
            # Predecessor, all embeddings, and label must share one active run.
            if not all(valid[j] and segment_ids[j] == segment_ids[t]
                       for j in range(t - 1, t + i + 1)):
                continue
            conditioning = [hidden[t - 1]] + [
                embed(tokens[j]) for j in range(t, t + i)
            ]
            rows.append((i, concat(conditioning), tokens[t + i]))
    return rows

Here segment IDs identify document occurrences, and all arrays retain their original packed addresses. Hidden rows must already come from a target forward with segment-causal attention; row filtering cannot repair contaminated hidden states. Any additional loss-only mask is applied separately, without removing input context. For a segment of length L, head i has max(L - i - 1, 0) eligible rows before such supervision masking. Empty streams, one-token segments and max_future=0 yield no rows.

This is a local boundary convention for the article’s teacher-row sketch, not a claim about the upstream implementation’s BOS or packing policy. The last embedding is at t+i-1; the label at t+i is never an input.

The official Hydra implementation makes the shift mechanical with rolled token embeddings and expands selected paths one head at a time. Its PrefixMLP variant runs one additional decoder layer once per proposal round, then lets the depth-specific MLP heads reuse that prefix-aware state. The reported Hydra++ recipe combines four-layer heads, teacher-distribution loss, and this shared prefix layer. Those three changes are separable design choices, not consequences of dependence itself.

0x06C Clover: Regressive Attention Instead Of Concatenation Alone

Source: Clover, architecture overview. Clover carries a hidden draft state between depths, injects the preceding token embedding through an attention decoder, optionally augments the target representation, and reuses the target language-model head.

Clover propagates a hidden draft state and injects the previous drafted token embedding through an attention decoder:

$$Q_i=W_Q\operatorname{Norm}(h_{i-1}), \qquad K_i=W_KE(\hat x_{t+i-1}), \qquad V_i=W_VE(\hat x_{t+i-1})$$ $$h_i = h_{i-1} + \operatorname{Attention}(Q_i,K_i,V_i)$$

The updated $h_i$ is fed through the speculative predictor. Clover also studies an augmenting Transformer block on top of the target representation and reuses the target LM head across speculative depths.

The paper specifies this block at the Attention(Q_i,K_i,V_i) boundary; its architecture figure further depicts a lightweight gated interaction. The article does not replace that boundary with an invented universal attention formula, because the exact gate is implementation-specific. The important design difference is stable: basic Hydra widens a depth-specific MLP input by concatenating all prior embeddings, while Clover recurrently updates a fixed-width state. The latter avoids linearly growing input width, but adds a serial recurrent dependency and an attention-decoder parameterization.

Medusa:
    all heads parallel; weak continuation dependence

Hydra:
    prior drafted embeddings condition later heads

Hydra++:
    deeper heads + target distillation + prefix attention

Clover:
    recurrent draft state + previous-token attention + optional augmenting block

0x06D Latency Tradeoff

Let $C_h$ be one head-stage cost and $K$ the speculation depth.

Idealized independent-head critical path:

$$C_{independent}\approx C_h$$

Idealized dependent-head critical path:

$$C_{dependent}\approx K C_h$$

This does not imply dependent heads are slower end to end. If dependence increases accepted length enough to use a much smaller tree or fewer target rounds, the total ratio can improve:

$$\frac{C_{dependent}+C_T(N_{dep})}{\mathbb{E}[A_{dep}]} < \frac{C_{independent}+C_T(N_{ind})}{\mathbb{E}[A_{ind}]}$$

Clover explicitly motivates its design for smaller practical token trees and larger batch sizes, where an enormous independent Cartesian tree would become compute-bound.

0x07 Candidate Topologies

0x07A One Sequence

A depth-$D$ sequence contains $D$ proposal nodes. Its useful prefix disappears after the first rejected token.

0x07B Multiple Independent Sequences

With $W$ sequences of depth $D$, the unmerged budget is:

$$N_{raw}=WD$$

Shared prefixes should be merged; otherwise identical target activations and KV rows are recomputed.

0x07C Cartesian Future Heads

If depth $i$ keeps $b_i$ candidate tokens, a full Cartesian tree has:

$$N_{tree} = \sum_{i=1}^{D} \prod_{j=1}^{i}b_j$$

For $b=[3,2,2]$:

$$N_{tree}=3+6+12=21$$

The formula derives directly: depth 1 has $b_1$ nodes; each receives $b_2$ children; each depth-2 node receives $b_3$ children.

0x07D Prefix-Merged Tree And The DAG Boundary

If two proposal sources emit the same token under the same full ancestor path, they represent the same target computation and can share a node. Source-specific proposal probabilities still need careful handling by the verifier.

The full-prefix condition is necessary. Consider:

path 1: A -> B
path 2: X -> B

The two B nodes have the same token id and depth, but different causal histories. Their attention outputs, logits, and KV rows can differ. Merging them by token id would give one path the other’s state. The canonical key is:

$$\operatorname{node\_key}(v) = (\operatorname{token}(v_1),\ldots,\operatorname{token}(v)),$$

not (depth, token_id).

A proposal planner may use a DAG to share immutable metadata, source handles, or suffix descriptions. Before target execution, it must materialize parent-unique candidate rows unless it has proved complete state equivalence. For an ordinary causal decoder, merging identical full prefixes produces a trie, which is still a tree.

def merge_by_full_prefix(candidate_paths):
    rows_by_prefix = {}
    for path in candidate_paths:
        parent = -1
        prefix = ()
        for token in path.tokens:
            prefix = prefix + (token,)
            if prefix not in rows_by_prefix:
                rows_by_prefix[prefix] = CandidateRow(
                    row_id=len(rows_by_prefix),
                    token=token,
                    parent=parent,
                    sources=[],
                )
            row = rows_by_prefix[prefix]
            row.sources.append(path.source)
            parent = row.row_id
    return topological_rows(rows_by_prefix.values())

Tree flattening must preserve ancestry. Here candidate_roots contains the alternative first proposed tokens, not a committed-prefix or anchor row. It may contain one candidate or a forest of alternatives. Candidate depth starts at one; position stores that relative depth, while position_id is the absolute target-input position. The prefix-frontier logits already exist and are not appended to these candidate rows. This candidate-only convention is separate from Sequoia’s root-inclusive optimization score below.

The flattening and validation snippets use the same dictionary-row interface. build_ancestor_mask(rows, prefix_len) supplies the backend mask: all prefix columns are visible, followed by self/ancestor-only candidate columns.

PREFIX_FRONTIER = -1  # logits owned by the already processed prefix


def flatten_tree(candidate_roots, prefix_len):
    assert prefix_len >= 0
    rows = []
    queue = [(node, -1, 1, ()) for node in candidate_roots]

    while queue:
        node, parent_row, depth, parent_prefix = queue.pop(0)
        row = len(rows)
        full_prefix = parent_prefix + (node.token_id,)
        rows.append({
            "token_id": node.token_id,
            "parent": parent_row,
            "position": depth,
            "position_id": prefix_len + depth - 1,
            "predictor_row": PREFIX_FRONTIER if parent_row == -1 else parent_row,
            "full_prefix": full_prefix,
            "q": node.proposal_probability,
            "source": node.source_id,
        })
        for child in node.children:
            queue.append((child, row, depth + 1, full_prefix))

    mask = build_ancestor_mask(rows, prefix_len)
    return rows, mask

For node $u$ and candidate node $v$:

$$M_{u,v}=1 \iff v\in\operatorname{Ancestors}(u)\cup\{u\}$$

All candidate nodes may also attend to the committed prompt prefix. Sibling candidates must not attend to one another.

0x07E Candidate row, predictor row, and KV row

For a prefix of length $T$ and candidate row $r$ at depth $d_r\ge1$:

candidate input row r:
    token_ids[r] is processed at position T + d_r - 1

probability that verifies token_ids[r]:
    prefix-frontier logits, if parent[r] == -1
    logits[parent[r]], otherwise

KV written at row r:
    belongs to token_ids[r] under ancestry(parent[r])

logits produced at row r:
    predict children of r, not r itself

For rows [A, B, C, D] with parents [-1, 0, 1, 1], token A is scored by frontier logits, B by row A, and both C and D by row B. Rows C and D may share a predictor distribution while still owning different input/KV rows. This separation closes the common one-position shift bug.

0x08 Multiple Drafts Require A New Exactness Derivation

0x08A One Draft Is A Maximal Coupling

Let $X\sim q$ be one draft token and $Y\sim p$ the required target token. The one-draft speculative acceptance probability is:

$$\Pr(Y=X) = \sum_{x\in\mathcal{V}}\min(p(x),q(x)) = 1-d_{TV}(p,q)$$

This is maximal coupling under mismatch cost:

$$c(x,y)=\mathbf{1}[x\ne y]$$

The familiar accept/reject/correction rule implements that coupling.

0x08B Why Repeating It Over $k$ Candidates Is Wrong

Suppose every draft sample is 1, while the target is Bernoulli$(1/2)$. Testing each of $k$ copies independently with acceptance probability $1/2$ would output 1 with probability at least:

$$1-2^{-k}$$

For $k>1$, that is not $1/2$. More chances to accept the same token have duplicated its probability mass.

0x08C SpecTr: Membership-Cost Optimal Transport

For candidate vector $X=(X_1,\ldots,X_k)$, let $S(X)$ be the set of distinct proposed tokens. SpecTr changes the cost to:

$$c(X,Y) = \mathbf{1}[Y\notin S(X)]$$

A candidate vector has supply:

$$Q(X)=q^{\otimes k}(X)=\prod_{i=1}^{k}q(X_i).$$

A valid coupling $\pi(X,Y)$ must preserve both the candidate-vector supply and the target-token demand:

$$\sum_X\pi(X,Y)=p(Y), \qquad \sum_Y\pi(X,Y)=q^{\otimes k}(X)$$

The exact objective is:

$$\min_{\pi\ge 0} \sum_{X\in\mathcal{V}^{k}} \sum_{Y\in\mathcal{V}} \pi(X,Y)\mathbf{1}[Y\notin S(X)]$$

subject to those two marginal constraints. The zero-cost mass is the probability that the selected target token belongs to the proposed set; the remaining mass is rejection/correction. The exact discrete linear program has $|\mathcal{V}|^{k+1}$ transport variables, exponential in $k$. SpecTr derives an efficient valid selection procedure with a stated $(1-1/e)$ multiplicative approximation to optimal acceptance rather than solving this LP online.

Finite transport oracle

Take vocabulary {a,b,c}, draft distribution $q=(0.4,0.4,0.2)$, target $p=(0.5,0.3,0.2)$, and $k=2$. There are nine candidate vectors with supplies such as:

Q(a,a) = 0.16
Q(a,b) = 0.16
Q(a,c) = 0.08
...
Q(c,c) = 0.04

An exhaustive max-flow oracle connects candidate vector $X$ to token $y$ at zero cost only when $y\in S(X)$. It then checks:

for every candidate vector X:
    sum_y pi[X,y] == Q(X)

for every output token y:
    sum_X pi[X,y] == p(y)

For this toy instance all target demand can be assigned to a candidate vector that contains the demanded token, so the optimal membership acceptance is 1.0. That does not mean two arbitrary draft tokens are always accepted; it is a property of this finite coupling and these distributions.

One-position set versus multi-step tree

SpecTr’s derivation couples $k$ candidates for one next-token decision. A tree repeats a selection problem at successive accepted nodes, where every child distribution is conditional on a different prefix. Applying the one-position LP to all tree nodes at once without preserving those conditional histories is not justified. SpecInfer and Sequoia provide their own recursive residual contracts for that setting.

This is a useful design lesson:

candidate diversity:
    can increase the probability that a target-valid token is present

selection algorithm:
    must allocate target probability across the whole candidate set

independent p/q tests:
    do not automatically define a valid multi-candidate coupling

0x09 SpecInfer: Expand, Merge, Linearize, Verify

SpecInfer turns one or more small speculative models into a token tree in two ways.

Source: SpecInfer, Figure 2. Expansion branches one speculative model at selected positions; merge combines trees from several speculative models by shared token prefixes. Both paths then require linearization, ancestor-only target attention, subtree verification, and one committed path.

Expansion keeps multiple top candidates per step according to a configured width vector such as:

width by depth = [2, 2, 1]

Merge combines trees from multiple speculative models. Paths with identical full token prefixes share nodes. Equal suffix tokens under different parents remain separate target rows.

The target verifier then:

1. linearizes all tree nodes;
2. assigns topology-aware positions and an ancestor mask;
3. executes target attention for all nodes in one pass;
4. walks one accepted path;
5. commits only target-valid path state.

SpecInfer’s tree attention is defined so each node receives the same attention output it would receive if its root-to-node path were processed as an ordinary sequence. Topology-aware masking fuses these paths without allowing sibling leakage.

The compiled buffers must agree:

tree token row r       -> token_ids[r]
parent relation        -> parent_index[r]
causal coordinate      -> position_ids[r]
allowed context        -> ancestor_mask[r]
probability for row r  -> frontier logits or target_logits[parent_index[r]]
temporary target state -> branch_kv[r]

The paper’s expansion strategy branches one speculative model at selected positions. Its merge strategy combines trees from several speculative models. Both strategies terminate at the same target ABI; they differ in how proposal distributions and source ownership reach each child.

In the following integration sketch, merge_identical_prefixes returns a prefix container whose children are the first-token candidates. The container represents the already processed prefix; it is not itself a target-input row. An empty candidate forest falls back to the ordinary target step.

def tree_speculative_round(prefix, speculators):
    trees = [s.propose_tree(prefix) for s in speculators]
    merged = merge_identical_prefixes(trees)

    if not merged.children:
        return ordinary_target_step(prefix)
    rows, mask = flatten_tree(merged.children, len(prefix))
    validate_candidate_graph(rows, len(prefix))
    target = target_model.verify_tree(prefix, rows, mask)

    committed_path = verify_under_configured_policy(
        tree=merged,
        target_distributions=target.distributions,
        proposal_distributions=proposal_metadata(merged),
    )

    commit_target_kv(target.branch_cache, committed_path)
    discard_siblings(target.branch_cache, committed_path)
    return committed_path.tokens

SpecInfer describes both greedy verification and a multi-step stochastic verifier. Its stochastic correctness applies to the complete residual-update procedure. It should not be simplified to “pick any child that looks likely.”

0x09A Stochastic residual update

At one node, let $p^{(0)}=p$ be the target distribution and let proposal $X_i\sim q_i$ be the next child tested. At step $i$:

$$a_i = \min\left(1, \frac{p^{(i-1)}(X_i)}{q_i(X_i)} \right).$$

If $X_i$ is rejected, the remaining target mass becomes:

$$p^{(i)}(x) = \frac{[p^{(i-1)}(x)-q_i(x)]_+} {\sum_y[p^{(i-1)}(y)-q_i(y)]_+}.$$

This update is not optional cleanup. The accepted mass for token $x$ is $\min(p^{(i-1)}(x),q_i(x))$; the unaccepted target mass is exactly the positive residual. Therefore accepted mass plus rejected-branch residual reconstructs $p^{(i-1)}$. Induction over children preserves the original target marginal.

def verify_children(target_p, proposals):
    residual = target_p
    for token, q in proposals:
        accept = min(1.0, residual[token] / q[token])
        if uniform() < accept:
            return token
        residual = normalize(positive_part(residual - q))
    return sample(residual)

For target $p=(0.5,0.3,0.2)$ and two i.i.d. proposals from $q=(0.4,0.4,0.2)$, the repository oracle enumerates all nine proposal pairs, every accept/reject branch, and the final residual sample. The resulting output marginal is (0.5, 0.3, 0.2) to floating-point tolerance. Re-running each candidate against the original $p$ instead would fail this test.

0x09B Temporary KV Is Topology State

For homogeneous full K/V rows, $N$ candidate nodes, $L$ layers, $H_{kv}$ KV heads, head width $d_h$, and $b$ bytes per scalar, raw candidate code payload is:

$$M_{treeKV} \approx N\,L\,2H_{kv}d_hb$$

This is a dense payload example, not the generic admission cost of a quantized, MLA, sliding-window or shared-page cache. Use the actual per-layer retained segments and incremental union of physical allocations, including qparams, residual/sparse state, page rounding and sharing exactly once. Keep workspace disjoint. M8.6 owns quantized representation costs, M5.8 latent representation, and M5 cache retention/publication/lifetime. Cache schema, quantizer specification and allocation policy therefore belong in the measured profile identity.

The target verifier may write all candidate rows, but only one root-to-node path can become the committed autoregressive prefix. Parent indices and request ownership are therefore correctness metadata, not bookkeeping decoration.

0x0A Sequoia: Derive The Tree Objective

Sequoia separates two optimization problems:

Source: Sequoia, Figure 1. The left plot reports source-measured accepted-token growth as tree budget increases; the right compares a sequence, independent sequences, a full k-ary tree, and a DP-optimized topology. The vertical hardware markers motivate a second optimization: the tree maximizing expected accepted tokens need not maximize wall-clock speed.

1. choose a tree that converts a fixed node budget into a large expected generated-token count;
2. choose size and depth for the measured target/draft hardware costs.

0x0AA Positional Acceptance Model

Let $p_j$ be the probability that child position $j$ is selected, conditional on its parent having been reached. At most one sibling is selected, so these are mutually exclusive outcomes, not separate chances conditioned on testing each sibling. For the represented child slots:

$$0\le p_j\le 1,\qquad \sum_{j=1}^{B}p_j\le 1.$$

The remaining mass means no represented child is selected. Do not normalize it away: it accounts for stopping the accepted path at this parent. If calibration instead records $h_j$, the acceptance rate conditional on rejection of all earlier siblings, convert with the probability chain rule:

$$p_j=h_j\prod_{i<j}(1-h_i).$$

These conditional rates need not sum to one; the resulting selected-child probabilities must sum to at most one. This conversion does not assume independent sibling tests. For node $v$, let Path(v) be the child indices followed from the root, and set $f(\mathrm{root})=1$.

The probability of reaching $v$ is:

$$f(v) = \prod_{j\in\operatorname{Path}(v)}p_j$$

Let $I_v$ indicate that verification reaches node $v$. The generated-token count under the paper’s convention is:

$$G(T)=\sum_{v\in T}I_v$$

By linearity of expectation:

$$\mathbb{E}[G(T)] = \sum_{v\in T}\mathbb{E}[I_v] = \sum_{v\in T}\Pr(I_v=1) = \sum_{v\in T}f(v)$$

That is why the final tree score is a sum of path-probability products, not merely node count or maximum depth.

With the root counted as one node and depth measured in edges from that root, a verified path visits at most $\min(n,d+1)$ nodes. Consequently:

$$1\le\mathbb{E}[G(T)]\le\min(n,d+1).$$

This is an independent sanity check on the optimizer’s result. A depth-two tree cannot have expected progress greater than three under this convention, even if it contains many siblings.

0x0AB Sampling Without Replacement And Robustness

SpecInfer’s baseline stochastic construction may sample the same high-$q$ token more than once. Duplicates do not increase set coverage, and repeated rejection of one overconfident draft token is especially wasteful at low temperature. Sequoia changes the per-parent proposal process:

1. sample a child from the current draft distribution;
2. remove that token from future draws at the parent;
3. after rejection, update the target residual;
4. if all nonzero draft mass has been exhausted, use a uniform distribution over unsampled tokens as the proposal fallback.

Sampling without replacement changes the joint proposal law. It therefore cannot be paired with a verifier derived for i.i.d. samples by changing one flag. Sequoia proves its sampling and residual-verification procedure together. The article preserves that pair as one algorithmic contract.

0x0AC Depth-Indexed Dynamic-Programming Recurrence

The official Sequoia optimizer includes depth in the state. Define $T[n,d,b]$ as the maximum expected generated-token score for a tree with:

n: total node budget, including the root of this subproblem
d: maximum remaining depth
b: number of child slots already represented at this root

For one root-only tree:

$$T[1,d,0]=1.$$

With one child, the root contributes one and the child subtree is reached with probability $p_1$:

$$T[n,d,1] = 1+p_1\max_jT[n-1,d-1,j].$$

For branch slot $b>1$, split the node budget into:

left part:
    root plus the first b-1 child subtrees, using y nodes

right part:
    the b-th child subtree, using n-y nodes

The right part contributes only if child position $b$ is accepted. Therefore:

$$T[n,d,b] = \max_{y\in\mathcal{Y}(n,b)} \left( T[y,d,b-1] + p_b\max_jT[n-y,d-1,j] \right)$$

where $\mathcal{Y}(n,b)$ contains only splits that leave valid left and right subtrees. The first term preserves the root and previous branches; the second adds the expected score of branch $b$. A backpointer stores the maximizing split and the maximizing branch count of the right subtree, making topology reconstruction part of the algorithm rather than an omitted postprocess.

def validate_selected_child_probabilities(probabilities):
    from math import fsum, isfinite
    if not all(isfinite(p) and 0.0 <= p <= 1.0 for p in probabilities):
        raise ValueError("invalid selected-child probability")
    if fsum(probabilities) > 1.0 + 1e-12:
        raise ValueError("sibling probability mass exceeds one")


def optimize_tree(max_nodes, max_depth, acceptance):
    # acceptance[0] is an unused zero sentinel, not root reach probability.
    validate_selected_child_probabilities(acceptance[1:])
    B = len(acceptance) - 1
    score = full((max_nodes + 1, max_depth + 1, B + 1), -inf)
    backpointer = {}

    for depth in range(max_depth + 1):
        score[1, depth, 0] = 1.0

    for depth in range(1, max_depth + 1):
        for nodes in range(2, max_nodes + 1):
            score[nodes, depth, 1] = (
                1.0
                + acceptance[1]
                * max(score[nodes - 1, depth - 1, :])
            )
            backpointer[nodes, depth, 1] = (1, nodes - 1)

            for branches in range(2, min(B, nodes - 1) + 1):
                for left_nodes in valid_splits(nodes, branches):
                    right_nodes = nodes - left_nodes
                    candidate = (
                        score[left_nodes, depth, branches - 1]
                        + acceptance[branches]
                        * max(score[right_nodes, depth - 1, :])
                    )
                    if candidate > score[nodes, depth, branches]:
                        score[nodes, depth, branches] = candidate
                        backpointer[nodes, depth, branches] = (
                            left_nodes, right_nodes
                        )

    return reconstruct_tree(backpointer, score)

This model assumes acceptance depends on branch rank $b$. A richer calibration can estimate $p_{d,b}$ by depth and branch rank. That improves fit but increases sample requirements and makes the artifact more sensitive to workload drift.

0x0AD Hardware-Aware Objective

The tree with the highest $\mathbb{E}[G]$ is not necessarily the fastest tree. Let:

G(n,d): expected generated tokens for a tree of size n and depth d
t(n):   measured target time to verify n nodes / one-token target time
c:      measured draft time per depth step / one-token target time

Sequoia evaluates:

$$\operatorname{Speedup}(n,d) = \frac{G(n,d)}{t(n)+dc}$$

and searches over $(n,d)$. Verification shape is measured, not assumed linear. An offloaded target may prefer a much larger tree because every target round transfers or streams expensive weights. An on-device target may reach a compute-bound regime much earlier.

The corrected illustrative oracle explicitly chooses conditional sibling-test rates h = [0.82, 0.48, 0.24]. These are synthetic assumptions, not measured Sequoia calibration data. Converting them gives selected-child probabilities p = [0.82, 0.0864, 0.022464], whose sum is 0.928864; the remaining 0.071136 is the probability of selecting none of the three represented slots. Passing h directly as p would violate the sibling probability budget.

The toy search uses two to eight total nodes, maximum edge depth four, and synthetic normalized target costs t(2..8) = [1.00, 1.03, 1.08, 1.16, 1.28, 1.43, 1.62], with draft depth cost c=0.09. It selects a five-node chain at depth four. Its expected progress is:

$$G=1+0.82+0.82^2+0.82^3+0.82^4=3.49588976.$$

The normalized time per token is (1.16 + 4 * 0.09) / 3.49588976, about 0.4348. Here only the first child slot appears at each non-leaf, so the chain stops there with probability 1-0.82, including outcomes assigned to unrepresented later slots. The expected progress remains below the five-node path maximum. Independent enumeration of small ordered trees checks the DP scores and selected shape. These are deterministic teaching results, not measured latency or a hardware speedup claim.

0x0AE Acceptance Statistics Are Versioned Artifacts

The positional acceptance vector is estimated from data. Sequoia reports that optimal trees can change with model pair, temperature, dataset, and hardware. Therefore an optimized tree artifact needs provenance:

target checkpoint + tokenizer
proposal checkpoint/index/head version
sampling policy and temperature range
calibration dataset and date
batch-size regime
hardware and target kernel version
measured t(n) and c curves
chosen tree topology hash

Using an old tree is not generally a correctness failure if verification remains exact, but it can erase the speedup.

0x0B Training And Runtime Integration Matrix

The table is intentionally paper-by-contract rather than paper-by-speedup. Draft & Verify’s skip-vector search, Kangaroo’s adapter distillation, Hydra++‘s teacher loss, SpecInfer’s optional SSM improvement, and Sequoia’s offline tree calibration create different mutable artifacts. Treating them all as “a draft model” hides what must be trained, versioned, loaded, and rolled back.

0x0BA Training Labels Differ By Head Semantics

Independent head $i$ learns a future marginal from the same trunk state:

$$\mathcal{L}_{ind} = \sum_{i=1}^{K} \lambda_i\operatorname{CE}(H_i(h_t),x_{t+i})$$

Dependent heads need a conditioning policy during training:

teacher forcing:
    later head receives the ground-truth prior token

self-conditioning:
    later head receives a sampled/argmax earlier prediction

distillation:
    head matches the target distribution, not only the hard label

Teacher forcing is stable but can create exposure mismatch at inference. Self-conditioning better matches runtime state but introduces nondifferentiable selection or surrogate choices. Target distillation conveys probability mass beyond one label but requires target logits and storage/compute.

For Hydra-style hard labels:

$$\mathcal{L}_{hard} = \sum_{i=1}^{K}\lambda_i \operatorname{CE}(q_i(\cdot\mid h, x_{t:t+i-1}),x_{t+i}).$$

For Hydra++ target distillation:

$$\mathcal{L}_{teacher} = -\sum_{i=1}^{K}\lambda_i \sum_{v\in\mathcal{V}} p_T(v\mid x_{\le t+i-1})\log q_i(v\mid h,x_{t:t+i-1}).$$

The paper reports a frozen Vicuna backbone, one epoch for basic Hydra and Medusa heads, ten epochs for Hydra++, AdamW, and a cosine schedule. Those are source-reported experimental settings. They do not establish that every target model, dataset, or head depth should use the same schedule.

0x0C End-To-End Proposal Buffer Trace

Consider two sources:

Hydra:
    A -> B -> [C, D]

REST:
    A -> B -> E
    A -> F

another Hydra path:
    X -> B

After prefix merge:

root
  A
  |-- B
  |   |-- C
  |   |-- D
  |   `-- E
  `-- F

  X
  `-- B       # distinct B: different full prefix and target state

Flattened rows:

The runtime cannot feed this heterogeneous graph into an arbitrary $p/q$ verifier. It must choose a verifier compatible with the available proposal semantics, for example target-sample membership over the whole child set, or separate verified subtrees with a proved combination rule.

The target-coordinate compiler additionally returns:

Rows 1 and 7 contain the same token id but different parent rows, masks, and KV state. Rows 3 and 4 share predictor row 1 but not input/KV rows.

0x0CA Integrated selection oracle

def compile_speculative_round(prefix, proposal_results, manifest):
    assert all(result.manifest_hash == manifest.hash
               for result in proposal_results)

    paths = collect_paths(proposal_results)
    trie = merge_identical_full_prefixes(paths)
    rows = materialize_parent_unique_rows(trie)
    coords = compile_positions_masks_and_predictor_rows(rows, prefix)

    verifier = negotiate_verifier(
        probability_semantics=collect_probability_contract(rows),
        sampling_relation=collect_sampling_contract(rows),
        topology="tree",
        requested_mode=manifest.verifier_mode,
    )

    target = verify_target(rows, coords)
    selection = verifier.select(rows, target)
    publish_target_path(selection, target.branch_cache)
    return selection.tokens

The repository fixture compiles four paths into seven target rows, keeps the two history-distinct B rows separate, verifies every ancestor-mask entry, enumerates the SpecInfer output marginal, solves a finite membership-transport instance, runs the depth-indexed Sequoia DP, and hashes the resulting proposal artifact. This is a deterministic correctness oracle, not a latency claim.

0x0CB Cache Commit Trace

If target verification chooses A -> B -> D:

commit:
    target-computed KV rows for A, B, D

discard:
    C, E, F target branch rows

retain separately if policy needs it:
    proposal-side draft KV or retrieval cursor

never commit:
    proposal-model KV as target KV
    sibling target rows
    a correction-token row computed for a rejected token

This inherits M7.1’s correction-token rule: an emitted correction token needs target state computed for that actual token before a future decode step depends on its KV.

0x0D Evaluation: Measure The Whole Frontier

Proposal quality

acceptance by depth
accepted path length distribution
first-child coverage
distinct-candidate coverage
calibration of q where required
retrieval match length and miss rate

Proposal cost

draft latency by depth
retrieval/index latency
tree construction and pruning time
CPU-GPU transfer time
proposal weights and KV memory

Target verification

target time by node count and topology
mask/position construction time
temporary target KV bytes
kernel occupancy and graph-capture hit rate

Output and serving

time per committed token
inter-token latency distribution
throughput under batch sizes 1, 2, 4, 8, ...
exact output-distribution tests where claimed
quality tests for heuristic acceptance
fallback frequency

Benchmark claims in the source papers are configuration-specific. Hydra’s reported throughput gains, REST’s retrieval overhead, Clover’s larger-batch results, SpecTr’s speedups, SpecInfer’s distributed/offload results, and Sequoia’s large-tree offload gains should all remain source-reported rather than becoming universal expectations.

0x0E Failure Lab

0x0F Implementation Assertions

def validate_candidate_graph(rows, prefix_len):
    assert prefix_len >= 0
    for row_id, row in enumerate(rows):
        parent = row["parent"]
        assert -1 <= parent < row_id
        expected_depth = 1 if parent == -1 else rows[parent]["position"] + 1
        assert row["position"] == expected_depth
        assert row["position_id"] == prefix_len + expected_depth - 1
        parent_prefix = () if parent == -1 else rows[parent]["full_prefix"]
        assert row["full_prefix"] == parent_prefix + (row["token_id"],)

        if row["q"] is not None:
            assert 0.0 <= row["q"] <= 1.0

        expected_predictor = (
            PREFIX_FRONTIER if parent == -1 else parent
        )
        assert row["predictor_row"] == expected_predictor

    mask = build_ancestor_mask(rows, prefix_len)
    for u in range(len(rows)):
        assert all(bool(mask[u, p]) for p in range(prefix_len))
        for v in range(len(rows)):
            should_see = is_ancestor(rows, ancestor=v, node=u) or u == v
            assert bool(mask[u, prefix_len + v]) == should_see


def validate_commit(selected_rows, branch_cache, target_token_ids):
    assert forms_single_root_to_node_path(selected_rows)
    assert all(branch_cache[row].token_id == target_token_ids[row]
               for row in selected_rows)
    assert no_sibling_rows(selected_rows)

Additional release assertions:

tokenizer(target) == tokenizer(parametric_draft)
proposal checkpoint compatible with target version
retrieval corpus excludes protected evaluation material
probability semantics accepted by configured verifier
sampling relation accepted by configured verifier
tree node budget <= runtime temporary-state budget
verifier supports every proposal metadata type in the graph
exact mode never invokes heuristic acceptance
hardware profile matches deployed kernel/model/batch regime
proposal artifact hash binds topology + profile + policy

0x10 Design Decision Guide

Use prompt lookup when:

the workload contains repeated prompt material,
no additional model memory is acceptable,
and empty proposals can fall back cheaply.

Use REST-style retrieval when:

domain/code continuations repeat across requests,
a governed datastore is acceptable,
and CPU/index latency fits the target round.

Use a separate draft model when:

a well-aligned smaller checkpoint exists,
its weights and KV fit,
and native proposal probabilities simplify exact sampling.

Use self-speculation when:

duplicate model memory is the binding constraint,
the target exposes a useful shallow/skipped path,
and the runtime can keep provisional and authoritative state separate.

Use independent heads when:

parallel proposal latency matters most,
small sparse trees are sufficient,
and later-head consistency is acceptable.

Use dependent heads when:

later-depth proposal quality limits accepted length,
the added sequential head path is cheap,
and better paths permit a smaller verification tree.

Use hardware-aware trees when:

the proposer/verifier is stable enough to calibrate,
verification time is nonlinear in tree size,
and multiple candidate shapes can be compiled or captured.

0x11 Red Flags

"Draft source and verifier are interchangeable."
    No. Proposal metadata constrains which exact verifier is valid.

"Dependent heads are simply more accurate Medusa heads."
    They change the draft dependency graph and critical path.

"Retrieval is free because it has no neural model."
    It adds index memory, query, trie, packing, and governance costs.

"Tree attention makes all candidate shapes equally cheap."
    Node count, depth, topology, masks, kernels, and batch shape matter.

"Maximize acceptance length, then deploy the winner."
    Optimize time per committed token under the actual runtime.

"A tree calibrated once is optimal forever."
    Model, sampler, workload, kernel, batch, and hardware changes invalidate cost assumptions.

"The same token at the same depth is one reusable node."
    No. Target state belongs to the complete causal prefix.

"A proposal score can stand in for q."
    Only a normalized distribution generated under the verifier's assumed
    sampling law can fill that role.

"SpecTr solves tree verification once and for all."
    Its core transport problem selects among candidates at one target position;
    recursive trees need conditional per-node contracts.

Source and implementation manifest

Claims in this article use four evidence classes:

source-local:
    exposition and figures preserved from A30-A33

externally verified:
    equations, algorithms, and training contracts in primary papers

implementation-observed:
    data structures and runtime behavior in pinned official repositories

rewrite interpretation:
    common ABI, semantic row compiler, release manifest, and toy oracles

Repository observations are intentionally narrower than paper claims. The official REST code grounds suffix search and tree buffers; Kangaroo grounds the adapter/early-exit structure; Hydra grounds rolled embeddings and per-depth path expansion; FlexFlow grounds one SpecInfer systems realization; Sequoia’s repository grounds the three-dimensional DP and hardware selector; Transformers grounds one prompt-lookup API. None of those snapshots proves behavior for a different commit or runtime.

0x12 Publish Gate

• Proposal source, topology, and verifier are separated.
• Probability semantics and sampling relation are negotiated explicitly.
• Candidate rows, predictor rows, and KV rows use distinct coordinates.
• Retrieval and prompt lookup are not treated as calibrated draft distributions.
• Retrieval corpus, tokenizer, index, and split lifecycle are versioned.
• Independent and dependent head factorizations are derived.
• Hydra, Hydra++, and Clover training/architecture choices are compared.
• Self-speculative state reuse is provenance-qualified.
• Equal token ids under different parents are never merged as target state.
• Multi-candidate exactness is derived beyond repeated one-draft tests.
• SpecTr one-position coupling is separated from recursive tree verification.
• SpecInfer tree buffers and target-state ownership are explicit.
• SpecInfer residual updates reproduce the target marginal in an executable oracle.
• Sequoia’s expected-tree score, depth-indexed DP, and reconstruction are derived.
• Hardware-aware deployment optimization requires measured verification cost; the local teaching profile is explicitly synthetic.
• Sequoia selected-child probabilities satisfy the sibling-mass budget, and expected progress respects the path-length bound.
• Tensor, pseudocode, cache, and release invariants are included.
• Source-reported benchmark claims are not generalized.

0x13 What This Unlocks

M7 now has the algorithmic pieces required to reason about a proposal system:

M7.1:
    exact one-sequence draft/verify sampling

M7.2:
    same-model heads and tree attention

M7.3:
    Jacobi/lookahead proposal generation

M7.5-M7.6:
    feature drafting and integrated causal MTP modules

M7.7:
    source selection, dependent heads, multi-candidate selection,
    and tree optimization

The remaining question is operational: how these rounds coexist across many requests, how speculative state is budgeted and scheduled, and how a production system proves a speedup without compromising output or rollback safety. That is the owner question for M7.8.

References

1. Yaniv Leviathan, Matan Kalman, Yossi Matias. Fast Inference from Transformers via Speculative Decoding.
2. Xiaoxuan Liu et al. Draft & Verify: Lossless Large Language Model Acceleration via Self-Speculative Decoding.
3. Jiahao Liu et al. Kangaroo: Lossless Self-Speculative Decoding via Double Early Exiting.
4. He Zhu et al. REST: Retrieval-Based Speculative Decoding.
5. Tianle Cai et al. Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads.
6. Zachary Ankner et al. Hydra: Sequentially-Dependent Draft Heads for Medusa Decoding.
7. Yuhui Yang et al. Clover: Regressive Lightweight Speculative Decoding with Sequential Knowledge.
8. Xupeng Miao et al. SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification.
9. Ziyi Yang et al. SpecTr: Fast Speculative Decoding via Optimal Transport.
10. Benjamin Spector, Chris Re. Accelerating LLM Inference with Staged Speculative Decoding.
11. Zhuoming Chen et al. Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding.
12. Hugging Face. Assisted Decoding.
13. Immi’s Workshop. A30 - Decoding Speculation.
14. Immi’s Workshop. A31 - Medusa.
15. Immi’s Workshop. A32 - Lookahead Decoding.
16. Immi’s Workshop. A33 - DeepSeek MTP.
17. FasterDecoding. REST official implementation.
18. Equationliu. Kangaroo official implementation.
19. Zachary Ankner et al. Hydra official implementation.
20. FlexFlow. FlexFlow / SpecInfer implementation.
21. Infini-AI-Lab. Sequoia official implementation.
22. Hugging Face. Transformers pinned implementation.