M7.3 - Lookahead Decoding: Jacobi Iterations, N-Gram Pools, and Parallel Verification

M7.3 - Lookahead Decoding: Jacobi Iterations, N-Gram Pools, and Parallel Verification

0x00 Overview And Background

Autoregressive decoding is not serial because a Transformer is unable to process many rows at once. It is serial because row t+1 needs a token selected from the distribution at row t, and that token normally does not exist until the target forward has finished. M7.1 introduced one way to manufacture those missing inputs: run a separate drafter. M7.2 introduced another: attach future-offset heads and compile their candidates into a tree.

Lookahead decoding starts from a different observation. A causal target model can be asked to update several guessed future positions in one forward. The complete guessed row is usually not ready to publish, but adjacent states along repeated updates contain short fragments that the same target model considered locally plausible. Preserve those fragments, retrieve them when their first token matches the live frontier, and verify them against the real prefix: the otherwise wasteful Jacobi trajectory becomes a target-generated proposal source.

The owner question is therefore:

How can one unchanged causal target model simultaneously
    update a rolling field of future guesses,
    harvest reusable n-grams from that trajectory,
    verify several disjoint continuations against one committed prefix,
and publish exactly the same greedy or sampled output distribution?

Its answer is not “Jacobi converges faster than autoregression.” Vanilla Jacobi usually does not. The answer is a four-stage state machine:

predict:    update W future positions from N-1 trajectory levels
collect:    turn adjacent trajectory states into keyed N-grams
verify:     test up to G matching suffixes under target conditionals
publish:    commit one validated path and repair every temporary state

That distinction matters. W, N, and G control a temporary computation graph, not three kinds of model context. The n-gram pool is generated state, not an external retrieval datastore. The lookahead rows are proposals, not committed history. The verification rows share one prefix but are disjoint paths. And “exact” names a decoding contract, not a promise that extra rows are free.

Historical path: from triangular decoding to trajectory reuse

The useful lineage is about which dependency is relaxed, not just publication dates:

Santilli et al.’s parallel decoding work formulated greedy Transformer decoding as a triangular nonlinear system and applied Jacobi and Gauss-Seidel-style iterations. The Lookahead paper then made a different engineering move: it stopped treating nonconverged trajectory values as pure waste and cached the N-grams that appear across adjacent iterations. This chronology supports the mechanism lineage; it does not by itself establish priority beyond the cited publications.

Source-local visual: A32 - Lookahead Decoding, adapting the parallel-decoding lineage. The encoder-decoder drawing is historical motivation; M7.3’s runtime contracts below are written for decoder-only causal LMs.

The paper’s key systems premise is also conditional. Low-batch autoregressive decode often leaves accelerator arithmetic underused while repeatedly streaming model state. Lookahead spends more token-row work per target call to reduce the number of calls. This can lower latency only while the enlarged call remains an efficient use of available compute and accepted progress grows faster than packing, attention, MLP, K/V, synchronization, and sampling costs. M4 owns the general hardware model; this article derives only Lookahead’s additional rows and state transitions.

Owner contract: what M7.3 owns and what it defers

M7.3 owns the full mechanism connecting five objects:

triangular target equations
    -> Jacobi trajectory window
    -> keyed N-gram pool
    -> packed lookahead/verification target call
    -> exact output and K/V publication transaction

It derives the coordinate system, reconstructs the released implementation at a pinned commit, and separates paper pseudocode from runtime-specific choices. It also compares greedy and exact sampling verification because Lookahead’s disjoint one-hot proposal proof is method-defining.

It deliberately defers:

The original A32 article remains the source-local implementation narrative. M7.3 does not replace it with a short summary: it turns its diagrams and code observations into derivations, immutable manifests, executable oracles, and failure checks.

Background knowledge: Jacobi iteration updates many dependent variables from an older state

Jacobi methods solve coupled systems by updating each variable in parallel from the previous iteration rather than immediately consuming newly updated neighbors. Applied to greedy decoding, future token positions can be initialized with guesses and repeatedly updated by the target model.

The intermediate rows are not automatically a valid final continuation, but they can contain reusable local fragments:

lookahead window:
    parallel future positions across recent Jacobi iterations

n-gram pool:
    fragments harvested from those trajectories

verification branch:
    checks promising fragments under exact autoregressive conditionals

window update:
    advances the iterative state after committed output

Lookahead decoding is consequently target-only candidate generation plus verification. Its speedup depends on useful fragment recurrence and verification efficiency, not on Jacobi convergence alone.

0x01 Claim Status And Scope

Exactness is scoped to the decoding policy and verification contract described by the Lookahead paper. Do not read it as “every stochastic sampling policy is distribution-preserved without an accept/reject correction rule.”

Evidence labels remain distinct throughout this article:

Source-local          reported by untouched A32
Primary paper         owned by the Jacobi or Lookahead paper
Pinned implementation observed at official commit eed010d...
Derived               algebra or tensor state checked by a local oracle
Synthetic             illustrative coordinate, never measured performance
Unmeasured            no local checkpoint/GPU quality or latency experiment

0x01A Immutable Round, Window, Pool, And Backend Manifest

Before deriving the algorithm, freeze one coordinate system. The paper presents a rectangular semantic window; the pinned Python implementation stores a ragged steady-state representation in which the live current-token row supplies one cell that is not duplicated in past_tokens. Mixing those two views produces off-by-one row, position, and K/V bugs.

Let:

The general n-gram definition admits N=2, but the pinned multilevel schedule illustrated here requires N >= 3, hence at least two trajectory levels. Both its first warmup branch and its steady window update access past_tokens[1]. Reject the unsupported one-level case before initializing or compiling a round; satisfying the row-count equation alone is not enough. This is a schedule-specific admission rule, not a restriction on every possible Lookahead variant. The source is the pinned warmup and update.

def pinned_suffix_length(N):
    if type(N) is not int or N < 3:
        raise ValueError("the illustrated pinned schedule requires integer N >= 3")
    return N - 1


S = R = pinned_suffix_length(N)  # validate before warmup or row compilation

Semantic paper window at round t:

$$\mathbf{W}_t \in \mathbb{N}^{R\times W}, \qquad R=N-1.$$

Pinned Python steady-state storage:

$$\operatorname{len}(past\_tokens) =R, \qquad (\ell_0,\ell_1,\ldots,\ell_{R-1}) =(W-1,W,\ldots,W).$$

The missing first-level cell is represented by the live current token. Therefore the appended lookahead-state rows are:

$$Q_{LA} =(W-1)+(R-1)W =W(N-1)-1.$$

With C_t retrieved suffixes, verification contributes:

$$Q_V=C_tS=C_t(N-1).$$

For the pinned steady call with I=1, the total uncached/current query rows are:

$$Q =I+Q_{LA}+Q_V =(W+C_t)(N-1).$$

This equality is a reconciliation check, not a universal allocation law. Warmup has ragged level sizes, prompt prefill has I>1, FlashAttention reorders lookahead rows, and distributed LP shards W and candidates. Every runtime must publish its actual level_sizes, row roles, logical positions, and K/V source map.

The pool is a typed map, not an unstructured list:

$$\mathcal{P}_t: \text{token id} \longrightarrow \operatorname{LRUList}_{\le G} \left((\text{token id})^{S}\right).$$

One round owns six state classes:

Dtype ownership is equally explicit:

token ids / logical positions: integer index dtype (pinned path: torch.long)
branch-role metadata:          integer/boolean host or device metadata
dense additive mask:           model-compatible floating dtype after expansion
hidden and K/V rows:           model execution dtype
LM-head logits:                promoted to float32 in the pinned LLaMA wrapper
sampling probabilities:        normalized floating state after logit warpers
pool/window storage:           host Python integer objects in the pinned path

Backend identity belongs in the manifest because it changes physical order:

The manifest is immutable for one compiled round. After publication, prefix length, window origin, pool recency, candidate count, and K/V length advance together and a new manifest is compiled. Mutating any one of them early makes the already-compiled positions, mask, or K/V source rows stale.

0x02 Jacobi Decoding Intuition

Ordinary autoregression solves positions sequentially:

y_1 = F_1(x)
y_2 = F_2(x, y_1)
y_3 = F_3(x, y_1, y_2)

Jacobi decoding treats the future tokens as variables and iteratively updates guesses:

$$y_i^{(r+1)} = F_i(x, y_{<i}^{(r)})$$

Renderer-safe fallback:

y_i^(r+1) = F_i(x, y_<i^(r))

The fixed point is the autoregressive result. The practical question is whether the iteration creates useful fragments before it fully converges.

The statement can be derived from an explicit residual system. With fixed prompt x, fixed model parameters, a deterministic greedy selector D (including a fixed tie-breaking rule), and desired output length m, define:

$$T_i(y_{<i};x) =D\!\left(p_\theta(\cdot\mid x,y_{<i})\right),$$ $$f_i(y_{1:i};x)=y_i-T_i(y_{<i};x).$$

The token subtraction is only formal notation for the root condition. The actual discrete equation is y_i = T_i(y_<i;x). Collecting the coordinates:

$$F(\mathbf y;x)= \begin{bmatrix} f_1(y_1;x)\\ f_2(y_1,y_2;x)\\ \vdots\\ f_m(y_{1:m};x) \end{bmatrix} =\mathbf 0.$$

Source-local visual: A32. The important property is triangular dependence: equation i reads coordinates <i, never future coordinates.

One Jacobi sweep applies the whole operator to the old vector:

$$\mathbf y^{(r+1)} =T(\mathbf y^{(r)};x), \qquad y_i^{(r+1)}=T_i(y_{<i}^{(r)};x).$$

Gauss-Seidel is a different schedule:

$$y_i^{(r+1)} =T_i\!\left(y_{<i}^{(r+1)};x\right).$$

It consumes newly updated earlier coordinates inside the same sweep. On a single device this can collapse back toward serial autoregression. Lookahead needs the Jacobi schedule because all future-position queries must be compilable before the target call starts. A kernel that accidentally lets a later lookahead row attend to a same-sweep updated predecessor silently changes the algorithm from Jacobi to a partially Gauss-Seidel graph.

0x02A Why Jacobi Reaches The Greedy Autoregressive Fixed Point

For a desired continuation of length m, define the triangular greedy system:

$$y_i = \operatorname*{argmax}_{v} p_\theta\left(v\mid x,y_{<i}\right), \qquad i=1,\ldots,m.$$

Jacobi uses the previous iteration’s guesses for every dependency:

$$y_i^{(r+1)} = \operatorname*{argmax}_{v} p_\theta\left(v\mid x,y_{<i}^{(r)}\right).$$

Let y^AR be the ordinary greedy continuation under the same selector and tie-break rule. The first coordinate has no guessed future dependency, so y_1^(1)=y_1^AR. Assume after sweep r the first r coordinates are correct:

$$y_{1:r}^{(r)} = y_{1:r}^{AR},$$

At sweep r+1, coordinate r+1 reads exactly that correct prefix from the old vector:

$$y_{r+1}^{(r+1)} =T_{r+1}(y_{1:r}^{(r)};x) =T_{r+1}(y_{1:r}^{AR};x) =y_{r+1}^{AR}.$$

Earlier correct coordinates remain correct because their dependencies are already correct. Therefore, a length-m greedy continuation converges in at most m iterations. This guarantee comes from causal triangular structure, not from a generic convergence theorem for arbitrary nonlinear systems.

The guarantee has four non-negotiable assumptions:

1. the prefix and target parameters do not change during the solve;
2. every sweep uses the same deterministic greedy selector and tie-break;
3. coordinate i sees only the previous sweep’s coordinates <i;
4. the requested finite horizon m is fixed.

It does not prove convergence for independently sampled coordinates. The released Lookahead path generates window proposals greedily even when final publication uses stochastic sampling; exactness then comes from the verifier in 0x05B, not from this fixed-point induction.

Jacobi alone is still unattractive: it can spend almost the same number of steps as autoregression, and useful tokens can appear at the wrong positions before the stable prefix reaches them. Lookahead’s contribution is to preserve meaningful n-grams formed along those trajectories and verify them when the real prefix reaches a compatible key.

0x02B Stop Conditions And Stable-State Semantics

Three conditions are easy to conflate:

Lookahead does not wait for the full window to become a fixed point. It harvests N-grams from intermediate trajectories and later verifies them under a different, live committed frontier. Conversely, equality between two arbitrary window rows is not permission to append them to output.

Source-local visual: A32, citing the Jacobi trajectory intuition. The frozen prefix in this figure is an analysis condition; M7.3’s publisher still requires the verification contract.

0x02C Jacobi Toy Table

Suppose the target greedy continuation is:

the cat sat

Jacobi decoding updates several future positions in parallel. A toy trajectory might look like:

The table is not meant to model all sampling behavior. It shows the useful property: while the whole row is not correct at first, fragments such as the and later cat sat can become reusable candidate n-grams. Exact stochastic sampling uses the separate verification algorithm in 0x05B; it does not follow from the greedy fixed-point argument alone.

The executable fixture in the evidence package makes the schedule visible. Its four-coordinate operator is deliberately small:

T1()         = 2
T2(y1)       = (y1 + 1) mod 10
T3(y1,y2)    = (y1 + y2) mod 10
T4(y1,y2,y3) = (y3 + 1) mod 10

Starting from [9,9,9,9], Jacobi needs four sweeps because each coordinate reads the previous vector. Gauss-Seidel reaches [2,3,5,6] in one sweep because it consumes updates immediately. Both can solve this triangular toy; only the Jacobi trace models one parallel future-position target call.

0x03 N-Gram Pool And 2D Window

Lookahead records fragments from Jacobi trajectories.

2D window:
    sequence dimension W
    iteration/history dimension N-1

n-gram pool:
    candidate fragments collected from prior trajectories

Source: Break the Sequential Dependency of LLM Inference Using Lookahead Decoding, Figure 1. The workflow separates Jacobi lookahead, verification, n-gram collection, and window update. (W), (N), and (G) are algorithmic work-shape parameters, not model context limits.

The released representation is keyed by the first token. For n-gram size N:

$$\mathcal{P}[k] = \left\{(g_2,\ldots,g_N): (k,g_2,\ldots,g_N) \text{ was observed on a trajectory}\right\}.$$

At decode time the current last token x_t is the lookup key, and the verification suffixes are:

$$\mathcal{G}_t = \mathcal{P}[x_t], \qquad |\mathcal{G}_t| \le G.$$

The pool is not a separate model. It is a cache of guesses produced by the target model’s own parallel iterations. Storing only the N-1 suffix avoids repeating the shared key token in every verification branch.

0x03A Window And Pool Lifecycle

Lookahead has a warmup problem. Before there are enough historical rows, the system cannot form the intended n-grams.

For W=4 and N=3:

W:
    four future positions tracked in the sequence dimension

N:
    three-token n-grams

trajectory rows involved:
    N - 1 prior/new update levels contribute to each suffix

Conceptually, the steady-state window retains N-1 trajectory levels across W future positions. The released code uses a longer first row during initialization so repeated shifts can fill later levels without shrinking the requested width. That storage detail should not be confused with the semantic knobs:

There are two useful initialization choices:

The official runtime exposes prompt-pool seeding as an option and otherwise seeds lookahead slots from prompt tokens. Random or copied seeds do not affect final correctness because they are only candidate-generation state, but they do affect early acceptance.

The pinned warmup layout explains the otherwise surprising W+N-3 initial row. For N=4, W=5, and R=N-1=3:

before first target call:  level sizes [6, None, None]
after first fill:          level sizes [5, 6, None]
after second fill:         level sizes [4, 5, 5]
steady state:              level sizes [W-1, W, W]

At fill stage r, the current deepest materialized level determines the number of inp_logits rows. Existing levels shift left by one; the newly created deeper level drops its first output where needed. The overlong first row is therefore temporary storage that lets the final ragged layout retain W extractable N-grams without shrinking later levels.

Prompt-pool seeding and trajectory warmup affect different state:

POOL_FROM_PROMPT:
    inserts observed prompt N-grams into the keyed pool
    does not eliminate the need to materialize window levels

trajectory warmup:
    constructs proposal rows needed for ongoing n-gram generation
    initially runs without a verification branch

An implementation may initialize proposal tokens randomly, copy prompt tokens, cycle through the prompt, or copy the last token. That choice can change early proposal quality but cannot change output correctness if proposal rows remain isolated and every publication passes target verification.

Steady-state lifecycle:

1. look up at most G suffixes under key x_t
2. pack the lookahead update rows and verification suffixes
3. run one target forward with branch-specific mask and position IDs
4. verify one output token plus zero or more candidate suffix tokens
5. commit only the selected verified output/KV path
6. extract new keyed n-grams from the Jacobi trajectory
7. update per-key LRU suffix lists
8. shift both sequence and trajectory dimensions of the window

0x03B N-Gram Pool Invariants

The official Python implementation uses a compact token map:

token_map[first_token] = [
    suffix_0 of length N-1,
    suffix_1 of length N-1,
    ...
]  # at most G entries, least-recently-used first

On reinsertion, an existing suffix is moved to the most-recent position. Once the per-key list is full, the oldest suffix for that key is evicted. This is different from a global top-score pool: a frequent key cannot consume every other key’s candidate budget.

def upsert_suffix_lru(token_map, key, suffix, G):
    bucket = token_map.setdefault(key, [])
    suffix = tuple(suffix)

    if suffix in bucket:
        bucket.remove(suffix)
    elif len(bucket) == G:
        bucket.pop(0)

    bucket.append(suffix)


def update_pool_from_trajectory(token_map, history_rows, new_row, N, W, G):
    for key, suffix in extract_keyed_ngrams(history_rows, new_row, N, W):
        assert len(suffix) == N - 1
        upsert_suffix_lru(token_map, key, suffix, G)

The extraction walks the trajectory geometry, not merely every contiguous slice of one row: a key from an older level is paired with tokens produced by later Jacobi levels and the new model output. This is how adjacent trajectory values become a candidate n-gram.

For steady past_tokens = [u^(0),u^(1),...,u^(R-1)] and new greedy lookahead outputs z[0:W], the pinned extractor emits exactly W keyed suffixes. At column zero:

$$k_0=x_t, \qquad s_0=(u_0^{(1)},u_0^{(2)},\ldots,u_0^{(R-1)},z_0).$$

For columns j=1,...,W-1:

$$k_j=u_{j-1}^{(0)}, \qquad s_j=(u_j^{(1)},u_j^{(2)},\ldots,u_j^{(R-1)},z_j).$$

Every s_j has R=N-1 tokens, so (k_j,s_j) reconstructs one full N-gram. The one-column offset between u^(0) and deeper levels is the physical consequence of using the live frontier as the missing first key.

Example with N=4, W=5:

live key x_t: 10
level 0:      [11, 12, 13, 14]
level 1:      [21, 22, 23, 24, 25]
level 2:      [31, 32, 33, 34, 35]
new row z:    [41, 42, 43, 44, 45]

extracted:
10 -> (21,31,41)
11 -> (22,32,42)
12 -> (23,33,43)
13 -> (24,34,44)
14 -> (25,35,45)

Source-local visual: A32, reproducing the paper’s lookahead, verification, collection, and update sequence. The executable trace above supplies the storage offsets omitted by the conceptual figure.

The bounded pool uses recency per key. For capacity G:

insert a new suffix into a non-full bucket: append as most recent
reinsert an existing suffix:               remove then append
insert into a full bucket:                 evict bucket[0], then append
retrieve:                                  use only bucket for current token key

This policy bounds each hot key independently but does not bound the number of distinct keys or total host-memory use. A production service needs a global pool budget, request lifetime policy, and telemetry; those serving policies belong to M7.8. M7.3 owns only the per-request algorithmic map used by the pinned implementation.

0x03C Window Advancement After Published Progress

With the pinned ALWAYS_FWD_ONE=True greedy path, proposal state advances one window column regardless of how many output tokens were published. For a fully warmed-up state, the shape-checked teaching helper is:

def advance_pinned_window(past_tokens, new_results, N, W):
    R = pinned_suffix_length(N)
    if type(W) is not int or W < 1:
        raise ValueError("window width must be a positive integer")
    if (len(past_tokens) != R or any(row is None for row in past_tokens)
            or [len(row) for row in past_tokens] != [W - 1] + [W] * (R - 1)):
        raise ValueError("expected fully warmed-up ragged levels")
    if len(new_results) != W:
        raise ValueError("expected W new lookahead outputs")
    return ([past_tokens[1][1:]]
            + [row[:] for row in past_tokens[2:]]
            + [new_results[:]])

The minimum admitted depth is N=3, with R=2: initialization at W=5 has sizes [5, None]; the first fill produces [4, 5]. A steady update maps [old_level_0, old_level_1] to [old_level_1[1:], new_results[:]], again with sizes [4, 5]. There is no intermediate-level copy in this boundary case. The existing N=4 trace still uses [4, 5, 5]. N=2 is rejected rather than passed into an update that would index a nonexistent second level.

This keeps the ragged shape [W-1,W,...,W]. The helper checks proposal storage, not all backend or distributed-runtime constraints. The sampling path contains an alternative ALWAYS_FWD_ONE=False schedule that slices by additional accepted tokens and then refills proposal slots. These schedules can generate different candidate pools while still preserving target output if verification and publication remain correct. They are design choices, not algebraically interchangeable state updates.

Window and pool mutations occur only after the current target output has been interpreted. Otherwise a newly inserted suffix could be selected by the same round that produced it, despite not being present when row metadata and target logits were compiled.

Compatibility screening is deliberately cheap:

verify_suffixes = token_map.get(current_last_token, [])[:G]

Matching the key does not prove that a suffix is correct under the current full prefix. It only makes the suffix promising enough to spend target verification work.

0x04 Two Branches In One Step

Each step carries two jobs:

The inference sequence is packed so the model can process both jobs together:

[current token / ordinary decode row]                    1 row
[flattened lookahead trajectory queries]                 Q_LA rows
[G candidate suffixes, each with N-1 token rows]         Q_V rows

The packed row number is not automatically the causal position. Each row needs branch-aware logical positions:

ordinary row:
    next committed sequence position

lookahead row:
    future position represented by its window column

verification suffix row:
    current prefix length + suffix offset
    repeated independently for each candidate

The mask must enforce two rules:

lookahead branch and verification branch do not see each other
each branch remains causally valid inside its own path

Packed mask sketch:

The zeros are the point. The lookahead branch is allowed to generate future n-grams, but the verification branch must not see those temporary guesses as if they were committed history.

The model wrapper must split the packed output back into three semantic views:

The released runtime uses these three roles explicitly. Flattening them into one generic outputs tensor hides the index contract needed for K/V compaction and n-gram extraction.

0x04A Pinned W=5,N=4,G=2 Row Compiler

For the steady dense reference path, level_sizes=[4,5,5], S=3, and two candidates produce 21 uncached rows. The compiler treats the current ordinary row plus level zero as one five-position base stripe:

All rows may attend the incoming committed K/V prefix. Among current rows, let b_j be base-stripe row j, u_(r,j) be trajectory level r>0 at column j, and v_(c,s) be candidate c at suffix offset s. The intended allowed edges are:

$$Vis(b_j)=\{b_k:0\le k\le j\},$$ $$Vis(u_{r,j}) =\{b_k:0\le k\le j\} \cup\{u_{q,j}:1\le q\le r\},$$ $$Vis(v_{c,s}) =\{b_0\} \cup\{v_{c,q}:0\le q\le s\}.$$

There are no edges from verification rows to lookahead rows b_1... or u, no edges from lookahead rows to verification rows, and no edges between different candidates. Logical position equality does not create visibility: two rows can both represent p+2 while belonging to isolated branches.

The mask compiler and position compiler must therefore consume the same row records:

Row(
    packed_index,
    role,               # ordinary | lookahead | verify
    trajectory_level,   # lookahead only
    window_column,      # lookahead only
    candidate_id,       # verify only
    suffix_offset,      # verify only
    logical_position,
    request_logit,
)

Building token IDs, positions, masks, and logit slices in separate loops without a shared record risks a shape-correct semantic mismatch.

The output-slice identities for the dense level-major path are:

$$out\_logits=Z[:,0,:],$$ $$inp\_logits=Z[:,10:15,:], \qquad guess\_logits=Z[:,15:21,:].$$

The indices are coordinate-specific. In the pinned wrapper they are derived from prefill_size, deepest-level width, and flattened guess length; the specialized FlashAttention path reorders lookahead rows and explicitly rearranges logits before exposing inp_logits.

The diagram follows the pinned runtime’s greedy pool generation. Its sampling note is implementation-specific; the conditional frozen-candidate generalization is separated in §0x05B below.

Source-local implementation visual: A32 - Lookahead Decoding, reproducing the llama.cpp layout comment. T separates prompt, lookahead, and verification row groups; Info names their semantic role; Pos carries logical positions; and Logits identifies rows whose distributions are needed. The lower dependency sketch is the mask contract encoded by those arrays.

The figure is valuable precisely because dimensions alone are insufficient. Two packed tensors can have the same row count while differing in role labels, position offsets, requested-logit rows, or visibility. Those metadata arrays must be versioned with the custom mask/kernel.

0x04B Ordinary Causal FlashAttention Is Not Enough

Lookahead’s mask is neither one lower-triangular matrix nor a standard padded batch. The paper’s implementation hardcodes the adjustable W/N/G pattern into a specialized FlashAttention path. Source-reported experiments found that this specialized path improved the straightforward PyTorch Lookahead implementation, but that result does not mean unmodified FlashAttention automatically supports the mask.

Runtime choices:

0x04C Pinned Python Source-To-Tensor Trace

The following trace is scoped to official Lookahead commit eed010d. It is evidence about that implementation, not a required API for every runtime.

Configuration first renames the paper knobs:

LEVEL         = N
WINDOW_SIZE   = W
GUESS_SET_SIZE= G
GUESS_SIZE    = LEVEL - 1 = S

The generation loop owns host proposal state and passes four groups into jforward_multilevel:

input_ids:        [1,I] current ordinary rows (steady I=1)
past_key_values:  L pairs, each [1,H_kv,K_in,d_h]
past_tokens:      R host lists with steady lengths [W-1,W,...,W]
guess_tokens:     flat host list of C_t*S suffix token ids or None

Inside the wrapper:

1. all_past flattens trajectory levels in level-major order for the dense backend. The Flash path transposes/interleaves later levels instead.
2. ids_list assigns logical positions from the current position_ids[-1], compensating for ragged level zero.
3. Candidate suffixes are appended after lookahead rows; every candidate reuses positions p+1 ... p+S.
4. The attention mask length is extended for every appended row, then j_make_causal_mask_multilevel converts row metadata into the branch mask.
5. The target produces hidden rows and K/V for all uncached rows.
6. The LM head scores every packed row and the wrapper promotes logits to float32 before slicing semantic outputs.

For the Loop 5 coordinate with K_in=128, I=1, Q=21, d=4096, and V=32000:

Two lengths serve different purposes:

$$kvcache\_len=K_{in}+I=129,$$ $$step\_len=K_{in}+Q=149.$$

kvcache_len is the destination frontier before additional accepted candidate rows. step_len reaches the physical end of the packed temporary K/V. Using one where the other is expected can copy a lookahead row or the wrong candidate into committed cache while every tensor shape still passes.

The pinned code also exposes implementation limits that prose must not generalize away: the wrapper asserts single-request batch, patches Hugging Face generation/model classes, scopes model adaptation to LLaMA, computes LM-head logits for all packed rows, and holds pool/window state as Python objects. These are current code properties, not theoretical requirements of Lookahead.

0x05 Verification And Speedup

The verification branch accepts the longest target-verified prefix:

$$A = \max\{a: \hat{y}_{t+1:t+a} = VerifyTarget(\hat{y}_{t+1:t+a})\}$$

Step cost sketch:

$$C_{lookahead\ step} = C_T(verification) + C_T(lookahead) + C_{mask/packing}$$

Lookahead helps when:

$$\frac{E[A]}{C_{lookahead\ step}/C_T} > 1$$

Renderer-safe fallback:

A = longest target-verified prefix
C_step = C_lookahead_branch + C_verify_branch + C_pack_mask
speedup condition: E[A] / (C_step / C_target_step) > 1

This is the same engineering shape as speculative decoding: accepted progress must exceed the extra work.

0x05A Greedy Verification

For greedy decoding, candidate checking is deterministic, but it is not a single equality over an already chosen suffix. The target first predicts the ordinary next token from out_logits. That token becomes the first member of the reference path. Each verification row then predicts the token after its candidate input under the same accepted prefix.

For candidate suffix

$$g^{(c)}=(g^{(c)}_1,\ldots,g^{(c)}_S),$$

define the target continuation along that packed branch as

$$z^{(c)}= \left( \arg\max out, \arg\max guess^{(c)}_1, \ldots, \arg\max guess^{(c)}_{S-1} \right).$$

The candidate hit length is the longest prefix for which

$$g^{(c)}_{1:a}=z^{(c)}_{1:a}.$$

The first element compares the first candidate token with the ordinary target prediction. The next comparison uses the target row whose input was the first candidate token, and so on. This one-position offset is easy to lose when flattened logits and candidate IDs have the same length.

An equivalent survivor view is:

target_token = argmax(out_logits)
survivors = all_candidates
emitted = [target_token]

for offset in range(candidate_suffix_length):
    survivors = [g for g in survivors if g[offset] == target_token]
    if not survivors:
        break

    # Every surviving path has the same accepted prefix. Its packed target
    # row must therefore expose the same next-token conditional.
    conditionals = target_rows_after_offset(survivors, offset)
    assert all_equal(conditionals)
    target_token = argmax(conditionals[0])
    emitted.append(target_token)

All candidates that disagree with an accepted token are removed. Candidates that share it remain because their later suffixes may differ. The target conditional at the next offset may be read from any survivor only because the branch mask gives every survivor the same visible prefix. If those rows differ, the mask, logical positions, or row-to-candidate map is already wrong.

There are two related output conventions in the literature and code. The paper can describe a fully matched length-$S$ proposal followed by one additional target token. The pinned Python path computes a hit count over its concrete guess_results slices and publishes according to that implementation’s max_hit convention. Loop 8 reconciles those output counts with physical K/V rows instead of assuming that paper pseudocode and released code share an off-by-one convention.

0x05B Exact Sampling With Disjoint One-Hot Proposals

The sampling path is more subtle than candidate == sampled_target_token. Lookahead stores token IDs, not a vocabulary-sized proposal distribution for every n-gram. The paper and pinned path generate lookahead proposals greedily and verify those token IDs as one-hot proposals. That describes the implemented generation policy; the conditional verifier proof and its scope are separated below.

At one output position, let p^{(0)} be the target sampling distribution and c_1,\ldots,c_m the candidate tokens offered by surviving n-grams. The proposal list may contain duplicates; the probability partition is over distinct token IDs, not candidate rows. For the next previously untested token c_r:

$$P(accept\ c_r\mid \text{reached }r)=p^{(r-1)}(c_r).$$

On rejection, remove that token’s mass and renormalize:

$$p^{(r)}(x)= \begin{cases} 0, & x=c_r,\\ \dfrac{p^{(r-1)}(x)} {1-p^{(r-1)}(c_r)}, & x\neq c_r. \end{cases}$$

If every distinct candidate is rejected, sample from the final residual distribution. This sequentially partitions the original target mass among candidate tokens and the residual vocabulary. For two distinct candidates:

P(output c1) = p(c1)

P(output c2)
  = P(reject c1) * p(c2)/(1-p(c1))
  = (1-p(c1)) * p(c2)/(1-p(c1))
  = p(c2)

all other tokens retain their original combined residual mass

The division is not merely suggestive. If the offered distinct set is $U=\{c_1,\ldots,c_u\}$, then every offered token recovers its target mass,

$$P(output=c_r) = \left(1-\sum_{j<r}p(c_j)\right) \frac{p(c_r)}{1-\sum_{j<r}p(c_j)} =p(c_r),$$

and a non-offered token $x\notin U$ recovers

$$P(output=x) = \left(1-\sum_{c\in U}p(c)\right) \frac{p(x)}{1-\sum_{c\in U}p(c)} =p(x).$$

Duplicate rows require a separate invariant. Once token A has been rejected, its residual mass is zero. Offering A again must either be skipped by deduplication or receive zero acceptance probability. Removing A twice and renormalizing twice is incorrect.

For the frozen audit coordinate,

target p              A=.20  B=.30  C=.10  D=.40
candidate rows        A, A, B
distinct test order   A, B

P(output A)           .20
P(output B)           (1-.20) * (.30/.80) = .30
residual after A,B    C=.20, D=.80 conditionally
P(output C)           .50 * .20 = .10
P(output D)           .50 * .80 = .40

reconstructed output  A=.20  B=.30  C=.10  D=.40 = target p

After accepting a candidate token, keep only n-grams that share that token at the current offset, move to the next suffix position, and use a target distribution computed under that same surviving prefix. For suffixes [A,C], [A,D], and [B,D], accepting A keeps the first two and accepting B keeps only the third. This is the disjoint-n-gram analogue of tree pruning. It is why the paper can preserve target sampling without storing q(x) vectors for the entire pool.

def sample_verify_position(target_probs, candidates_at_offset):
    residual = target_probs.clone()
    tested = set()

    for token in candidates_at_offset:
        if token in tested:
            continue
        tested.add(token)

        if uniform() < residual[token]:
            return token, "accepted_candidate"

        residual[token] = 0.0
        residual /= residual.sum()

    return multinomial(residual), "residual_target_sample"

A32’s sampling algorithm exposes the same control-flow distinction in source form: proposal acceptance, residual renormalization, and suffix filtering are three different state transitions, not one comparison.

The exactness contract therefore has four independent obligations:

1. one-hot proposal ownership: verification treats each tested token as a point mass; the pinned runtime generates its pool tokens greedily;
2. mass ownership: each distinct token consumes target mass at most once;
3. path ownership: acceptance filters suffixes before the next offset;
4. conditional ownership: the next target row was computed under the accepted prefix and not under a rejected or cross-candidate path.

The pinned runtime’s proposal-generation scope remains greedy. The residual proof above is conditional on a frozen candidate list and prefix, with fresh verifier randomness independent of how that list was generated. A randomly generated but independently frozen list can therefore also be tested as point masses: random origin alone does not invalidate the proof. This is a mathematical generalization, not a claim that the pinned runtime implements another sampling mode.

Do not conflate that conditional membership test with sampling from a proposal distribution q and applying a p/q acceptance rule. The latter needs M7.1’s actual proposal probabilities and correction machinery. Reusing proposal randomness for verification, changing the candidate list in response to that randomness, or scoring a different prefix invalidates the stated conditional argument.

0x05C Row And FLOP Ledger

Step compression and wall-clock speedup are different outputs. Start with the paper’s probability model, then add physical work.

Accepted-token expectation from survival probabilities

Suppose one proposal has length $\gamma$, and each successive proposed token passes with independent probability $\alpha$. Progress always includes the ordinary target token. Let $R_1$ be output tokens published in that round. The tail-sum identity gives

$$E[R_1] =\sum_{i=1}^{\gamma+1}P(R_1\ge i) =\sum_{j=0}^{\gamma}\alpha^j =\frac{1-\alpha^{\gamma+1}}{1-\alpha}.$$

For $b$ independent candidate suffixes, let $R_b$ be the maximum progress. To advance beyond the ordinary token by at least $i$ positions, at least one candidate must survive its first $i$ tokens:

$$P(R_b\ge i+1)=1-(1-\alpha^i)^b.$$

Therefore

$$E[R_b] =1+\sum_{i=1}^{\gamma}\left[1-(1-\alpha^i)^b\right] =(\gamma+1)-\sum_{i=1}^{\gamma}(1-\alpha^i)^b.$$

This is a model, not a measured acceptance process. Real candidate paths share the same prompt, token frequencies are nonuniform, pool entries are correlated, and per-depth acceptance is neither independent nor constant.

From one good pool hit to average step compression

If one round in every $f$ rounds has candidates matching the assumed distribution and the other $f-1$ rounds make one-token progress, then

$$\mathcal{S}_{steps} =\frac{f-1+E[R_b]}{f}.$$

The paper identifies $\gamma=N-1$ and, under its practical setting, $b=G=W$. It then studies how step compression changes as more parallel work is allocated. These assumptions must stay attached to the conclusion. Increasing W does not force the pool to contain more useful independent candidates; increasing G does not make duplicates independent; increasing N does not keep deep-prefix acceptance constant.

Exact packed-row ledger for the pinned layout

Let Q_{LA} be the lookahead query rows and Q_V the verification suffix rows:

$$Q_{LA}=W(N-1)-1, \qquad Q_V=C_t(N-1),$$

for the steady, non-transposed pinned Python layout, with $C_t\le G$ candidates actually found for the current key. Including its one ordinary row,

$$Q=1+Q_{LA}+Q_V=(W+C_t)(N-1).$$

The identity happens to match the paper’s rough token-work expression when $C_t=G$. Warmup, missing pool entries, distributed window shards, and specialized row transposes change physical layouts.

For the released teaching setting N=5, W=7, G=7 at full candidate occupancy:

lookahead rows                W*(N-1)-1 = 27
verification rows             G*(N-1)   = 28
ordinary row                  1
packed query rows             Q          = 56

The earlier 57-row upper-style intuition double-counted the ordinary row that is already embedded in the paper’s $(W+G)(N-1)$ approximation. The exact pinned steady formula closes that ambiguity.

A target round is more than transformer FLOPs

For a dense packed implementation, one round includes at least:

token-wise target work     projections, normalization, MLP over Q rows
attention work             only allowed (query,key) pairs if kernel exploits mask
LM-head work               pinned code projects every packed row to vocabulary
temporary K/V              Q rows per layer before compaction
mask/layout work           compiler, position IDs, possibly dense mask storage
host state                 keyed LRU lookup/update and candidate flattening
publication               acceptance, selected K/V copy or re-feed, truncation
distributed sync           if using worker shards / LP

For homogeneous full K/V rows, temporary code payload excluding metadata is

$$M_{KV,temp}=Q\cdot L\cdot2H_{kv}d_hb_{kv}.$$

Here $b_{kv}$ is bytes per scalar. This dense uniform-width example is not a generic quantized or MLA allocation estimate. Admission consumes the actual cache schema and per-layer retained segments, including qparams, residuals, sparse exceptions, page rounding and shared allocations counted once. Use the incremental allocation-union delta, with masks/logits/workspace charged separately. M8.6 owns quantized representation, M5.8 latent representation, and M5 cache retention/publication/lifetime; a kv_dtype label alone is insufficient.

The pinned full-row LM-head multiplication scales roughly as

$$F_{head}\approx2QdV,$$

which may become material when Q is large even if decode attention was originally bandwidth-bound. A backend that computes logits only for required output slices has a different cost contract.

The deployment metric is therefore

$$T_{token} = \frac{ T_{target}(Q,\mathcal{E}_{attn}) +T_{head}(Q) +T_{pack/mask/pool} +T_{publish/sync} }{ E[\text{emitted target tokens per round}] }.$$

Step compression exceeds one whenever average progress exceeds one. Wall-clock speedup additionally requires

$$T_{round}<E[R_{round}]\,T_{AR}.$$

A synthetic sensitivity coordinate makes the distinction concrete. The model below uses normalized T_AR=1, T_round=0.90+0.02Q; these constants are illustrative and are not measurements:

The first profile compresses target steps but still loses wall time because round overhead grows faster than useful progress. The third wins only under its strong synthetic acceptance and pool-hit assumptions.

0x06 Loop Pseudocode

S = R = pinned_suffix_length(N)  # reject unsupported depth before allocating state
token_map = initialize_keyed_pool(prompt, N=N, per_key_limit=G)
window = initialize_trajectory_window(prefix, W=W, N=N)

while not done:
    key = prefix[-1]
    verify_suffixes = token_map.get(key, [])[:G]  # each has N-1 tokens

    packed = pack_iteration(
        ordinary_token=key,
        lookahead_window=window,
        verification_suffixes=verify_suffixes,
    )
    mask, position_ids, slices = build_iteration_layout(packed, W, N, G)

    packed_output, temporary_kv = target_model(
        packed.tokens,
        past_key_values=prefix_kv,
        attention_mask=mask,
        position_ids=position_ids,
    )

    out_logits = packed_output[slices.ordinary]
    inp_logits = packed_output[slices.lookahead]
    guess_logits = packed_output[slices.verification]

    if sampling_policy == "greedy":
        emitted, chosen_rows = greedy_verify(
            out_logits, guess_logits, verify_suffixes
        )
    else:
        emitted, chosen_rows = exact_disjoint_sample_verify(
            out_logits, guess_logits, verify_suffixes
        )

    new_lookahead_row = argmax(inp_logits, dim=-1)
    plan = build_publication_plan(
        emitted=emitted,
        chosen_rows=chosen_rows,
        temporary_kv=temporary_kv,
        kvcache_len=packed_output.kvcache_len,
        step_len=packed_output.step_len,
    )
    validate_publication_plan(plan, packed, prefix_kv)
    publish_iteration(
        plan, prefix_kv, token_map, window, new_lookahead_row
    )

Helper sketches:

def build_lookahead_verification_mask(prefix_len, lookahead_layout, candidate_layout):
    total = prefix_len + lookahead_layout.rows + candidate_layout.rows
    mask = zeros([total, total], dtype=bool)

    prefix = range(0, prefix_len)
    lookahead = lookahead_layout.row_range_after(prefix)
    verify = candidate_layout.row_range_after(lookahead)

    allow_causal(mask, prefix, prefix)
    allow(mask, lookahead, prefix)
    allow_trajectory_dependencies(mask, lookahead_layout)
    allow(mask, verify, prefix)
    allow_each_suffix_causal_without_cross_candidate_leakage(
        mask, candidate_layout
    )

    return mask

No line in that helper allows lookahead queries to see verification candidates, or verification queries to see lookahead rows. The candidate block also needs separation between disjoint suffixes; a single triangular mask over all flattened candidates would let later candidates read earlier ones.

0x06A Prepare Next Iteration

Verification does not directly mutate serving state. It produces a publication plan with four coupled outputs:

output plan:
    target tokens released to input_ids / streamer

KV plan:
    ordinary input row already materialized by this call
    selected verification rows copied into the contiguous cache frontier
    all other packed rows discarded by truncation

trajectory plan:
    new argmax row and post-commit window shift

pool plan:
    n-grams extracted from the pre-shift trajectory
    optional generated-prefix insertion

These plans must agree on one accepted path before any becomes externally visible. The official Python implementation mutates these Python and tensor objects in a concrete order; the atomic transaction below is a stronger engineering contract, not a claim that the released loop provides exception rollback.

The paper-level order is visible in A32’s retained algorithm: run both branches, verify, append output, then update the n-gram pool. The runtime must additionally publish physical K/V rows.

0x06B The Output Frontier Is One Token Ahead Of K/V

An autoregressive cache stores rows for tokens already processed as inputs. The latest emitted token normally becomes the ordinary input of the next target call. Therefore output length and cache length are related, but their token labels are shifted.

Let:

K_in       incoming K/V rows
I          ordinary uncached input rows in this call (pinned path: 1)
h          pinned max_hit, the number of verification rows copied

Then the pinned single-worker path publishes

$$K_{out}=K_{in}+I+h, \qquad E_t=h+1,$$

where $E_t$ is the number of newly emitted target tokens. With $I=1$, $K_{out}-K_{in}=E_t$, but the new K/V rows are not K/V for all $E_t$ emitted tokens:

new K/V labels      [ordinary input u, emitted h0, ..., emitted h(h-1)]
new output labels   [h0, ..., emitted h(h)]

the final emitted token h(h) remains the next ordinary uncached input

That distinction prevents the same correction-token error discussed in M7.1: an output token can be valid before its own K/V row exists.

0x06C Pinned max_hit=2 Compaction Trace

Reuse the frozen Loop 6 coordinate:

K_in                       128
kvcache_len                129 = K_in + ordinary row
step_len                   149 = physical packed K/V end
candidate suffix size S    3
flattened candidate rows   6
winning candidate index    1
max_hit                    2

The pinned source computes the winning candidate’s physical start as

$$src_0 =step\_len-|guess\_tokens|+max\_hit\_idx\cdot S =149-6+1\cdot3 =146.$$

It copies exactly max_hit rows:

The cache is then truncated to row 131 exclusive. Candidate row 148, other candidate rows, and every lookahead row are discarded. Output publishes three tokens [h0,h1,h2]; h2 is the valid target prediction after the second copied row and becomes next round’s ordinary input.

def build_pinned_commit_plan(K_in, kvcache_len, step_len,
                             guess_token_count, suffix_size,
                             winner, max_hit, emitted):
    assert kvcache_len == K_in + 1
    assert len(emitted) == max_hit + 1

    src0 = step_len - guess_token_count + winner * suffix_size
    copies = [
        (src0 + j, kvcache_len + j)
        for j in range(max_hit)
    ]
    return {
        "copies": copies,
        "trim_exclusive": kvcache_len + max_hit,
        "next_uncached_token": emitted[-1],
    }

The source rows must belong to the winning candidate and correspond to accepted candidate inputs. Row 147 processes h1 and predicts h2: copying that row to destination 130 as K/V for h1 is required. Treating it as K/V for h2 would be wrong. A row’s K/V belongs to its input token, whereas its output logits predict the next token. Published h2 remains the uncached frontier; do not copy candidate row 148 merely because its input token might equal h2. The existing copy plan and trim boundary remain unchanged.

Window movement has two axes:

time/trajectory axis:
    drop the oldest Jacobi level
    promote newer levels
    append the new argmax row

sequence axis:
    drop positions consumed by committed output
    shift remaining future slots left
    refill vacated slots from the configured seed/reset source

The pinned ALWAYS_FWD_ONE path advances one trajectory column regardless of max_hit; its alternative slices each level by max_hit and refills the tail. That choice changes how much speculative trajectory state survives. It must not change the output/KV publication plan already validated for this round.

0x07 KV State

Lookahead’s cache has three physical regions during the target call:

stable prefix [0:K_in):
    K/V inherited from earlier target calls

ordinary frontier [K_in:kvcache_len):
    current uncached input, normally one row

packed workspace [kvcache_len:step_len):
    lookahead rows and candidate rows

Publication selects zero or more verification rows from the workspace, copies them immediately after kvcache_len, and truncates everything after the new frontier. The temporary work can affect memory and scheduling even though most of it never becomes user-visible state. In an M5-style serving engine, the scheduler must budget those rows during the model iteration.

Temporary-work ledger:

temporary positions =
    lookahead query rows
  + every verification suffix row

new persistent rows =
    ordinary input rows processed in this call
  + selected verified candidate-input rows

new output tokens =
    target token predicted by ordinary row
  + target tokens predicted by copied candidate rows

As with Medusa, packed temporary K/V must be gathered from the chosen verification suffix and compacted into contiguous request history. Lookahead-window K/V is iteration workspace, not prefix K/V. A row can contain a target-generated argmax useful for a future n-gram while still being invalid to commit at its current logical output position.

The publication order should be fail-closed:

def publish_iteration(plan, state):
    validate_sources_are_winning_candidate_rows(plan)
    validate_output_cache_frontiers(plan, state)
    validate_window_and_pool_versions(plan, state)

    staged_kv = compact_and_trim_without_publishing(state.kv, plan)
    staged_window = advance_window_copy(state.window, plan)
    staged_pool = update_pool_copy(state.pool, plan)
    staged_output = state.output + plan.emitted

    # One logical publication point. A production engine may use versioned
    # handles rather than copying all four structures.
    state.swap(staged_output, staged_kv, staged_window, staged_pool)

If validation or compaction fails, no output token should be streamed and no pool/window mutation should survive. Streaming before K/V publication turns an internal cache error into an externally irreversible response.

0x07A Implementation And Parallelism Variants

The mathematical dependency graph does not prescribe one physical schedule. Five implementations can compute the same target conditionals while making very different launch, mask, cache, and communication choices:

Separate forwards: the semantic oracle

The safest reference schedule runs the ordinary row, each lookahead trajectory, and each verification suffix as isolated causal forwards. It makes branch leakage structurally impossible and provides an excellent correctness oracle. It also repeatedly launches the target and rereads weights, forfeiting the memory-bandwidth amortization that motivates Lookahead. It is a testing design, not the expected production winner.

Dense packed mask: flexible but physically expensive

The dense path packs all rows once and applies the Loop 5 visibility matrix. Its advantage is auditability: arbitrary W/N/G, warmup raggedness, and branch roles can be compared directly with the separate-forward oracle. Its cost is not just allowed attention pairs; an explicit additive mask can scale with

$$M_{mask}=B\cdot H_m\cdot Q\cdot(K_{in}+Q)\cdot b_m,$$

where $H_m$ is 1 for a broadcast mask or the materialized head count. A logical sparse graph does not make a dense tensor physically sparse.

Specialized FlashAttention: pattern compiled into the kernel

Ordinary causal FlashAttention cannot express the Lookahead graph by passing a single causal flag. The paper reports hardcoding an adjustable W/N/G pattern into FlashAttention and a source-reported end-to-end improvement over its native PyTorch implementation. The pinned LLaMA path exposes this choice as use_flash and changes row layout with swap_axis_for_flash; it is therefore a different physical compiler target, not a drop-in flag over the same row order.

The source-reported gain is not a universal kernel constant. It depends on shape, model, hardware, branch occupancy, and whether packing, LM-head, Python, and K/V publication remain outside the optimized kernel.

Pinned distributed path: synchronize tokens, re-feed K/V

At commit eed010d, distributed workers shard candidate suffixes and pieces of the lookahead window, run the full model locally, and synchronize results after the forward:

verification decision    all_gather max_hit; broadcast winning hits
lookahead result          all_gather generated window slices
accepted K/V              not copied across workers
next model input          re-feed max_hit + 1 emitted tokens

When DIST_WORKERS > 1 and max_hit > 0, the code truncates local K/V to kvcache_len, sets guess_skip_dist=max_hit, and sends the last 1+max_hit output IDs through the next target call. This exchanges redundant target compute for avoiding remote candidate-K/V transfer. It is a concrete runtime policy, not an algorithmic requirement.

Lookahead Parallelism: replicated-model token parallelism

Lookahead Parallelism is not tensor parallelism. The paper assigns disjoint lookahead branches and independent verification candidates to devices while keeping a full model copy on each device. Shared prefix tokens are redundantly placed/computed; generated token results synchronize after the forward. This avoids model-shard collectives in the forward critical path, but it multiplies weight residency:

$$M_{weights,LP}=P\cdot M_{target\ weights}$$

for $P$ workers, before K/V and workspace. It is a latency-oriented strong-scaling design when every replica fits, not a way to serve a model that does not fit one worker.

The decision order is therefore:

1. prove dependency and logits against separate forwards;
2. prove packed dense mask and output slices against that oracle;
3. prove specialized-kernel row permutation against the dense compiler;
4. choose single-worker copy or distributed re-feed deliberately;
5. benchmark time per committed token under the actual serving load.

The official repository also patches model-specific generation and attention paths. “No auxiliary model” does not mean “no runtime integration”: a serving engine needs custom packing, positions, masks/kernels, K/V compaction, and sampling-state support.

0x07B Paper-By-Contract Comparison

Method names hide the contracts that actually determine correctness and integration. The bounded comparison below asks the same questions of each neighbor without reopening its owning article:

Three comparisons are especially easy to flatten incorrectly:

1. Jacobi is not yet Lookahead. Jacobi supplies trajectory tokens; Lookahead adds reusable n-gram collection and a target verification branch.
2. Disjoint suffixes are not a Medusa tree. They may share an accepted prefix semantically, but their packed candidate rows cannot attend across suffixes.
3. No auxiliary model is not no auxiliary state. Window rows, keyed pool, masks, logical positions, temporary K/V, acceptance state, and publication metadata remain runtime-owned.

0x08 Failure Lab

0x09 Boundary To M7.4–M7.6

Lookahead is runtime-only candidate generation.

The next owners separate training objectives from feature and module drafters:

M7.4 — general MTP:
    train future-token prediction objectives/modules

M7.5 — EAGLE/HASS:
    draft at feature level
    align training and decoding contexts for speculation

M7.6 — DeepSeek MTP:
    propagate state through sequential token-conditioned modules

M7.7 places Lookahead beside retrieval, prompt lookup, self-speculation, parametric drafters, and head/module proposers under one proposal-buffer contract. M7.8 owns temporary-row admission, dynamic speculative depth, and load-dependent serving evaluation.

0x0A Publish Gate

0xFF Reference

Local series and boundaries

• Transformer Series A32 - Lookahead Decoding - source-local mechanism, implementation walkthroughs, and retained visuals.
• M7.1 - Speculative Decoding - general p/q acceptance and correction lifecycle.
• M7.2 - Medusa - target-attached heads and tree verification.
• M7.4 - Multi-Token Prediction - general training-time supervision and independent heads.
• M7.5 - EAGLE Feature Drafting - feature drafters and EAGLE/HASS train-inference alignment.
• M7.6 - DeepSeek MTP - sequential token-conditioned MTP modules.
• M7.7 - Draft Sources and Hardware-Aware Trees - generalized proposal sources and topology.
• M7.8 - Speculative Serving - admission, scheduler, evaluation, release, and rollback.
• M4.3 - FlashAttention - generic online-softmax and I/O-aware kernel derivation.
• M5.1 - Autoregressive Serving State - generic K/V lifecycle and scheduler pressure.

Primary papers and implementation

• Parallel decoding via Jacobi iteration - triangular fixed-point lineage.
• Break the Sequential Dependency of LLM Inference Using Lookahead Decoding - Lookahead mechanism, exact sampling proof, scaling model, FlashAttention integration, LP, and source-reported evaluation.
• Official Lookahead Decoding implementation, pinned commit - Python row packing, masks, acceptance, K/V publication, and distributed path audited here.
• Lookahead Decoding project page - author/project explanation and diagrams; secondary to the paper and pinned source for contracts.