AI servingDive 03 of 06
Long context, from a million tokens to a fixed-size state
A million tokens can hold a codebase. Following one question through them reveals three different limits: attention work, growing caches, and what a compressed state can remember.
- Levels
- 9
- Reading
- 42 min
- Depth
- Idea to Machine
- Published
Two ways to carry the past · 16 tokens
Keep an address for every token.
Or update the same four numbers.
Attention reads a growing archive
Past key position · 1 to 16
- Pairs evaluated
- 136
- Retained KV
- 512 B
Shade = attention weight / row maximum, using scores −(query − key) / 4. The next token adds another cache entry.
Recurrence overwrites a fixed state
State coordinates · 1 to 4
- State updates
- 16
- Retained state
- 16 B
Shade = |state| / maximum shown; teal is positive, amber negative. Each update retains 0.8 of the previous state and adds input.
One question, a million tokens
You want a model to review a change in a large codebase. The bug starts in a configuration parser, crosses a wrapper, and becomes visible in a request handler a hundred files away. Send only the handler and the model misses the cause. Send the whole repository and it has the evidence, but reading that evidence becomes the expensive part of answering.
Keep that task in mind: find the path that bypasses configuration validation, then propose a fix. We will give the repository an illustrative size of 1,000,000 tokens. The corresponding line count depends on the tokenizer and the files. Include source, tests, documentation and the review conversation, and you can reach it without any single file being especially large. A book collection or a long agent session creates the same problem.
A context window is the amount of sequence a model can work with in one invocation. Making it larger is useful because you do not always know which evidence matters before you ask the question. A search system can retrieve files containing the parser's name. It is harder to retrieve the unanticipated wrapper that quietly changes its assumptions. A large window gives the model a chance to discover those relationships directly.
Three limits intervene. Dense attention compares more pairs as the sequence grows. The decode cache retains more keys and values. Positions move outside the distribution used in training. These are different problems. A faster kernel can help the first without changing the third. A smaller cache can help the second while leaving almost all the attention arithmetic intact. A model may accept the entire repository and still miss its crucial middle file.
Count the pairs before counting the chips
Let n be sequence length, L the number of layers, H the number of query heads, and dh the head width. Write d = H dh for the total query width. One multiply-add counts as two FLOPs. Computing both QKT and the weighted value sum costs 4n2d per layer for dense, unmasked attention when query/key and value head widths are equal. Softmax, projections and the MLP are additional work.
For a causal decoder, query i can read only positions through i. There are n(n + 1)/2 allowed pairs. An implementation that skips the masked triangle therefore needs 2n(n + 1)dL FLOPs for those two products across the model. At large n, doubling the input quadruples that work. A kernel may do some extra work in partially masked boundary tiles, so this is the ideal causal count.
The naive attention score or probability array occupies O(Hn2) memory per layer. At one million tokens, one dense head has a trillion entries. At two bytes per entry, that is 2 TB for one such matrix. Packing only the causal triangle would roughly halve it; keeping both scores and probabilities would increase it. This temporary matrix is distinct from the persistent KV cache.
32 layers · 32 query / 8 KV heads · head width 128 · MLP width 11008
- Causal attention products
- Gated MLP
- Tokens
- 32,768
- Attention products
- 281.48 TFLOP
- Gated MLP
- 283.67 TFLOP
- Q/K/V/output projections
- 87.96 TFLOP
- KV cache
- 4.29 GB · 4 GiB
- Compute-only prefill estimate
- 6.53 s
- Attention / MLP
- 0.99×
- Crossover n ≈ 3 × MLP width
- 33,024
One sequence; ideal causal triangle. Time = counted FLOPs / assumed sustained rate, with no communication or memory stalls.
The first preset uses 32 layers, 32 query heads of width 128, eight KV heads, and a gated MLP with intermediate width 11,008. Its model width is 4,096. We will carry this illustrative configuration through the page.
FlashAttention, by Dao and colleagues, removes the need to materialize the quadratic score matrix in accelerator memory. It streams tiles and accumulates the same softmax result, with working storage that scales linearly in sequence length at fixed widths. It reduces memory traffic as well. It still evaluates the dense pairs: the attention FLOPs remain quadratic. The inference dive explains attention, the KV cache and online softmax; here the important question is what happens when the sequence becomes enormous.
The alternatives change different parts of this accounting. Sparse attention removes pairs. Grouped queries and latent caches reduce retained bytes. Linear attention and state-space models replace the growing archive with a fixed-size state. Distribution spreads work across devices. None makes an arbitrary amount of useful evidence free to process, store and retrieve.
Long context has three budgets: pairs to compute, bytes to retain, and information the model can still use.
Fits in the window. Finds the answer?
The interface advertises a number: one million tokens. Your review task needs a behavior: identify the validation bypass, wherever its evidence sits. The first is a capacity limit. The second depends on the task, the model, the prompt and the evidence distribution. Calling both “context length” hides the distinction.
Before evaluating reasoning, check delivery. Count tokens with the relevant tokenizer. Check whether the advertised limit includes generated output. Verify how the application handles overflow: rejection, truncation, summarization or retrieval. A million-token model behind an application that silently keeps only the most recent messages is not receiving your million-token repository. Preserve file boundaries and paths so a retrieved statement can be tied to its source.
The length at which a model still meets a stated performance threshold on a stated task distribution. is an empirical measure. You must specify the task and the threshold. A model might retrieve a single identifier near the end, fail to compare three definitions in the middle, and summarize the overall subject reasonably well. There is no contradiction: those tasks ask different things of the retained evidence.
A needle is a useful beginning
In a needle-in-a-haystack test, an evaluator inserts a fact into a long distractor document and asks for that fact. Varying the insertion depth and document length tests access across the window. Greg Kamradt's public evaluation harness is a primary example of this style. Random passkeys and synthetic identifiers help avoid answers that a model could already know from training.
For our codebase, “the secret build marker is cedar-517” tests whether the model can find a marker. It does not test whether the wrapper and parser disagree about validation. Even perfect marker retrieval says little about comparing many similar definitions, following aliases or applying a rule correctly. Distractors matter too: unrelated prose is usually an easier haystack than twenty almost-correct implementations of the same API.
- 1Accept
Does the full input reach the model?
Length limits, output allowance, truncation - 2Locate
Where is the definition of parseConfig?
Needle retrieval at several depths - 3Connect
Which call path bypasses its validation?
Multiple facts, distractors, dependency chains - 4Use
Patch the bypass and justify the change.
End-task correctness, citations, regression checks
RULER, by Hsieh and colleagues, broadens synthetic evaluation beyond a single needle. It varies needle types and counts, adds multi-hop tracing, and includes aggregation. Its 2024 results show why a near-perfect simple retrieval score can coexist with a much smaller useful window on harder tasks. Use the same task suite to evaluate a checkpoint you plan to deploy.
Lost in the Middle, by Nelson F. Liu and colleagues, 2023, found that moving relevant evidence inside the input could substantially change performance. In the evaluated retrieval and question-answering settings, evidence at the beginning or end was often easier to use than evidence in the middle. Sweeping evidence position exposes weaknesses that one conveniently placed example can hide.
A practical evaluation for the review task can reuse the same repository while moving an otherwise identical relevant file between early, middle and late positions. Add near-miss definitions, require the answer to name the call chain, and check the proposed patch against a regression case. Keep the task answer stable while changing length or placement. Otherwise a longer prompt may also be a different problem, making the result hard to interpret.
A warm prefix changes latency, not evidence quality
Prompt caching is a product feature layered over model execution. If many questions share the same repository prefix, a server can reuse its precomputed internal state. A warm request can therefore reach its first answer token sooner than the first cold request. Measure both. Neither a lower bill nor a lower warm latency establishes that the model correctly connected two distant files.
Arrange stable material before frequently changing questions when the serving system supports exact prefix reuse. File ordering, chat templates and tokenization are part of the prefix. An edit near its beginning can invalidate everything after it. A conversational summary is a different operation: it changes the evidence itself. Ask whether a remembered statement is cached exactly, retained as text, retrieved later, or reconstructed from a summary. Those mechanisms can feel identical in a chat interface while having very different failure modes.
Stretching the ruler
Suppose the entire repository arrives intact. Attention still needs to distinguish “this token is next to me” from “this token is three hundred thousand positions away.” Extending the allowed array length does not teach that distinction. Position encoding is a representation of distance, and the model has learned to interpret it over a particular training distribution.
Rotary position embedding, introduced by Su and colleagues, rotates pairs of query and key coordinates. Pair i uses angular frequency θi = b−2i/dr, where b is the base and dr is the number of rotary dimensions. At position p the rotation angle is pθi. The dot product between rotated queries and keys then depends on relative position through their angle difference.
The RoPE lab in the inference dive develops that identity. Here, watch what happens when p moves beyond the range on which the model learned to combine the frequency bands. Fast bands have already completed many turns during training. Slow bands may have covered only a fraction of a turn. New long distances produce combinations of phases the model has not learned to interpret.
The angles remain mathematically valid. Sinusoids do not stop at the training boundary, and a single pair wrapping through 2π is normal. The problem is generalization of the learned function over all those phases. The base, the rotary width, the training length and the training data all affect the situation; there is no universal token position at which RoPE suddenly breaks.
Compress positions, or change the frequencies
Position Interpolation, Chen and colleagues, 2023, replaces p with p/s when extending by factor s. Equivalently, it divides every frequency by s. A long sequence is mapped into the position range the model saw before. The price is that nearby tokens become closer together in rotary space too. Fine-tuning helps the model adapt to that changed geometry.
NTK-aware scaling began as a 2023 community post by bloc97, rather than a peer-reviewed paper. Its static base-change version uses b′ = b sdr/(dr−2). The fastest band stays unchanged, while progressively slower bands are stretched more. This preserves some local positional resolution while extending the slowest wavelength. Later dynamic variants choose the scale based on the length; this lab uses the static version.
- Selected pair
- 15
- Frequency (rad / token)
- 0.01333521
- Wavelength (tokens / turn)
- 471.1724
- Unwrapped angle (rad)
- 109.2421
- Turns
- 17.386416
- Original rotations within training length
- 8.6932
- Pair scaling
- Unchanged
- Q and K multiplier √(1/t)
- 1
- Logit multiplier 1/t
- 1
- Attention temperature t
- 1
32 frequency pairs · fast on the left, slow on the right
Illustrative head: 64 rotary dimensions, base 10,000, training length 4,096. YaRN uses α = 1 and β = 32 rotations; the ramp follows the authors’ rounded dimension boundaries. Angles use radians and wavelengths use tokens.
A pair’s wavelength λi = 2π/θi is the number of token positions needed for a full turn. Within the original training length L, it completes ri = L/λi rotations. These quantities separate fast bands that repeatedly wrap inside the training window from slow bands that have covered less than a full cycle.
YaRN’s frequency policy, by Peng and colleagues, uses thresholds α = 1 and β = 32 for the Llama-family setting. Below one original rotation, interpolate the frequency to θi/s. Above 32 rotations, keep θi unchanged to preserve local resolution. Between the thresholds, blend the original and interpolated frequencies. The reference implementation converts these cutoffs to dimension indices, rounds the boundaries, and ramps linearly across those indices; the lab follows that implementation.
Inspect pair 15 at position 8,192 with extension factor 8. Static NTK-aware scaling gives an unwrapped angle of 39.9403 radians; the YaRN ramp gives 72.4779 radians. Their endpoint pairs happen to agree here, which is why an intermediate pair is useful. The selector exposes every pair’s frequency, wavelength, rotations and interpolation weight.
YaRN also rescales attention before softmax. Its fitted rule for Llama-family models is √(1/t) = 0.1 ln s + 1. Multiplying both Q and K by √(1/t) multiplies their dot product by 1/t. At s = 8, the Q/K multiplier is 1.2079 and the logit multiplier is 1.4591, equivalent to temperature t ≈ 0.6853. The lab reports both multipliers alongside the pair’s rotation.
Compare the first and last dials. Position Interpolation slows both by the same factor. Static NTK-aware scaling leaves the first unchanged and progressively slows the rest. The YaRN ramp preserves a band of fast frequencies before it blends toward interpolation. Each method allocates positional resolution differently. Full attention still visits every permitted key.
ALiBi, by Press, Smith and Lewis, takes another route. It adds a head-specific distance penalty to attention logits: scoreh(i, j) = qi·kj/√dh − mh(i − j), for j ≤ i. For a power-of-two head count H, the authors’ slope rule is mh = 2−8(h+1)/H, with zero-indexed head h. At H = 8, the slopes run from 1/2 to 1/256, giving heads different distance scales. There are no rotary phases to extrapolate. Distant tokens instead face an increasingly large negative bias, which changes what information the model prefers to read.
For the code review, these choices determine how the network represents a wrapper far from its parser. Training must also teach the network to follow a call chain across that distance. Extending positions and learning long-range behavior belong together: changing the ruler is useful only if the model can use the measurements it makes.
A longer position range is a representation change. Reliable long-range behavior still needs training and evaluation.
Choose which past to read
Position scaling leaves every dense attention pair in place. To reduce that arithmetic directly, decide that many pairs will never be evaluated. The simplest policy is a sliding window: a token reads itself and a bounded number of predecessors. If the window width is w including self, each query visits at most w keys. Prefill attention becomes O(nwdL), and a pure windowed decode cache can discard entries outside the window.
This is a change to the model's communication graph. A wrapper 100,000 tokens away cannot directly read the parser through a 4,000-token window in one layer. It may still receive information indirectly. Layer one mixes nearby positions; layer two reads neighbors that have themselves mixed earlier positions. With contiguous causal windows, ℓ layers give a maximum input span of 1 + ℓ(w − 1) tokens, clipped at the sequence boundary.
The span counts possible information paths. Along each path, the parser's details pass through several learned transformations. Each intermediate vector has finite width and performs a learned transformation. An indirect path through twenty layers is a different computational resource from one query selecting the original parser token. For a bug that depends on an exact identifier, that distinction can matter.
Longformer, by Beltagy, Peters and Cohan, combines local windows with selected global attention positions. Its encoder setting allows those global tokens to connect widely. Mistral 7B v0.1, by Jiang and colleagues, uses causal sliding-window attention and discusses receptive-field growth across layers. The lab below traces a small causal graph with optional retained prefix positions.
Input dependencies of the last token, by layer
2 layers reach 7 of 24 inputs: positions 17, 18, 19, 20, 21, 22, 23. Without sinks, the maximum span is 7 tokens, capped by sequence length.
- Reachable input
- Retained sink
- Outside reach
24 positions, causal windows. Reachability shows possible information paths, not successful recall.
Why retain the beginning?
Simply evicting old KV entries from a model trained with full attention can destabilize streaming generation. StreamingLLM, Xiao and colleagues, identifies attention sinks: initial positions attract attention even when their content is not semantically important. Retaining a few initial KV entries along with the recent window can recover stable behavior in their experiments. Softmax must distribute a unit of probability mass, and such positions can serve as an outlet for heads that have little useful content to retrieve.
A causal prefix token was computed before the later files arrived. It can act as an attention sink while those files are evicted. Its continued presence can stabilize attention without retaining the wrapper that has fallen out of the recent window. “Can process a stream indefinitely” and “can recall an arbitrary earlier token” are different properties.
More elaborate sparse patterns add strided, dilated or global connections. A good pattern can shorten routes between distant positions while keeping the number of edges much smaller than n2. The trade is structure: the chosen graph decides which interactions are cheap and which require multiple hops. A kernel also needs to exploit that structure. An irregular mask that still computes a dense matrix saves no arithmetic just because many outputs are later ignored.
For the repository review, a window can work well when definitions and uses are close, or when another component retrieves the necessary files together. Widely separated dependencies favor additional global access or explicit retrieval. Reordering files to improve locality can help one query while hurting another. Treat the document layout as part of the workload rather than assuming that a large theoretical receptive field solves every dependency.
Fewer bytes per remembered token
Removing attention edges changes which tokens can communicate. Another option keeps token-level access but stores fewer numbers for each token. The query side and the key/value side need not have the same number of heads. Multiple query heads can make different selections from a shared set of keys and values.
In ordinary multi-head attention, each of H query heads has its own key and value head. Multi-query attention, Shazeer, 2019, shares one KV head across all query heads. Grouped-query attention, Ainslie and colleagues, 2023, places several query heads in each sharing group. With Hkv KV heads, the cache shrinks by H/Hkv relative to the same-width multi-head design.
The attention output still has H query heads. Every query head still compares against every permitted position. GQA reduces KV projection work and cache storage, and can reduce memory traffic during decoding, but it does not divide the dense attention product FLOPs by the head-sharing factor. Implementations should reuse shared KV data rather than materialize repeated copies. Whether the resulting quality matches a multi-head model is a training and evaluation question.
For equal key/value head widths, cache bytes are exactly the product of the quantities below, before allocator padding, metadata and quantization scales. B is the number of equal-length sequences and s is bytes per stored number. For unequal lengths, replace Bn with the total number of retained tokens across sequences.
MKV = 2 B n L Hkv dh s
Our illustrative GQA configuration at one million tokens, batch one and 16-bit storage uses 2 × 1,000,000 × 32 × 8 × 128 × 2 = 131,072,000,000 bytes. That is 131.072 GB or about 122.07 GiB, before weights and other allocations. The MHA counterpart uses 524.288 GB. Changing the precision to eight bits halves raw payload storage, with accuracy and scale metadata to account for separately.
Cache a latent instead of expanded heads
Multi-head latent attention in DeepSeek-V2 compresses a token's joint key/value representation into a learned latent vector. Projection matrices reconstruct the head-specific content. During optimized decoding, parts of those projections can be absorbed into the query and output computations, so the cache can retain the latent rather than all expanded K/V vectors. A decoupled positional key handles the rotary component.
If the shared latent width is dc and the cached positional-key width is dR, the ideal payload is BnL(dc + dR)s bytes. There is no leading factor of two: this one latent jointly represents key and value content. The positional component is an additional cached vector. Exact layouts depend on the implementation; caching expanded heads would forfeit this storage advantage.
- GQA reduction vs MHA
- 4×
- MLA reduction vs MHA
- 14.22×
- MLA cached numbers / layer / token
- 576
Illustrative: 32 layers, head width 128, 16-bit cache, 1,000,000 tokens. MLA adds a shared 64-wide positional key. Valid GQA head counts divide 32.
With a 512-wide latent and a 64-wide positional key, this 32-layer example uses 36.864 GB.
MLA is still a growing token archive. The server retains one compressed entry per token, and a later query can score individual positions. That gives it a fundamentally different memory shape from a recurrent model whose state size is independent of n. Compression per token and compression across time can both save memory, but only the latter removes growth with sequence length.
The same DeepSeek-V2 paper also uses mixture-of-experts layers. That addresses a different cost: how much feed-forward computation is activated for each token. The mixture-of-experts dive follows that decision. KV storage still depends on the attention layers; MoE feed-forward costs depend on the activated experts.
GQA and MLA reduce the bytes attached to each token. They preserve a token-addressable archive that still grows with context.
Replace the archive with a state
Now change the memory contract. Instead of keeping the parser's key and value vectors available for a future query, update a state when you read the parser and carry only that state forward. This is recurrence. It trades an archive of past inputs for a learned running computation over them.
The connection to attention becomes clear if we replace the softmax kernel with a separable similarity function. Let φ map a query or key to r features. Use φ(q)Tφ(k) as the unnormalized weight. Positive features make normalization straightforward. The causal output is a weighted average of values at positions through the query, but the sums can now be regrouped.
yt = [φ(qt)T ∑j≤t φ(kj)vjT] / [φ(qt)T ∑j≤t φ(kj)]
Katharopoulos and colleagues' linear attention exploits this associativity. Maintain St = St−1 + φ(kt)vtT, an r × dv matrix, and zt = zt−1 + φ(kt), an r-vector. A query reads S and divides by its corresponding read from z. State size is independent of t. For fixed feature and value widths, total sequence work grows linearly with n.
That algebra is exact for a separable feature kernel. Softmax kernels can instead be approximated with finite features. Some methods approximate the softmax kernel with features; others train a model directly with a different kernel. Changing the similarity function changes the model. The sum can be reordered because the pairwise interaction has a specific separable form.
The tiny lab uses two positive key features and two value channels. The second value channel is always one, so its state column doubles as the normalizer z. We therefore carry four numbers total in this example. A general vector-valued layer normally needs its matrix state plus a separate normalizer. Step through and compare the first output channel with a direct sum over every earlier pair.
St = St−1 + φ(kt)vtT
Two features × two value channels
- Recurrent output, first channel
- 2
- Explicit pairwise output
- 2
- Absolute difference
- 0.00e+0
- State carried to next token
- 4 numbers
- Read token 1. Add its key–value outer product; compare the state readout with an explicit causal weighted sum.
- Read token 2. Add its key–value outer product; compare the state readout with an explicit causal weighted sum.
- Read token 3. Add its key–value outer product; compare the state readout with an explicit causal weighted sum.
- Read token 4. Add its key–value outer product; compare the state readout with an explicit causal weighted sum.
- Read token 5. Add its key–value outer product; compare the state readout with an explicit causal weighted sum.
- Read token 6. Add its key–value outer product; compare the state readout with an explicit causal weighted sum.
- Read token 7. Add its key–value outer product; compare the state readout with an explicit causal weighted sum.
- Read token 8. Add its key–value outer product; compare the state readout with an explicit causal weighted sum.
Positive features φ(ki) = [1 + (i mod 2), 1 + (i mod 3)], query [2, 1], values [2, −1, 3, 1, −2, 4, 0, 2]. The second value channel is always 1 and stores the normalizer.
A state-space model begins with dynamics
A linear state-space system describes how an input x(t) drives a hidden state h(t), which produces an output y(t). In continuous time, its equations are dh/dt = Ah + Bx and y = Ch + Dx. A governs how existing state evolves; B writes input; C reads state; D provides a direct input-to-output path. The state can represent several timescales through different decay modes.
To process tokens, choose a time step Δ and discretize. Under a zero-order hold, treating the input as constant during a step, Ā = exp(ΔA) and B̄ = ∫0Δ exp(τA)B dτ. Then ht = Āht−1 + B̄xt. The integral form also covers singular A; the familiar inverse-based expression assumes A is invertible. Other discretizations choose different discrete operators.
With constant parameters and zero initial state, unroll the recurrence. Each earlier input contributes CĀt−jB̄xj to the output. The weights depend only on lag, so the entire sequence is a causal convolution with kernel Kk = CĀkB̄, plus the direct Dx term. Sequential recurrence and convolution are two evaluations of the same system.
ht = a ht−1 + xt = ∑j=0t at−jxj
Maximum absolute difference: 0.00e+0. Both forms apply the same decaying input weights; floating-point summation order can change the last bit.
Scalar, constant-parameter SSM; initial state 0, input gain 1, output gain 1. The table is computed independently by recurrence and convolution.
S4, by Gu, Goel and Ré, makes long state-space sequence models practical using structured state matrices and efficient kernel computation. Its structured state matrix supports many memory timescales and efficient construction of the convolution kernel. Training can evaluate that convolution with FFTs, while decoding updates the recurrent state. The scalar lab isolates the same recurrence–convolution identity with one decay mode.
Move retention toward zero and only the newest input survives. Move it toward one and older inputs contribute for longer, but the state becomes a mixture of more history. Multiple state dimensions can carry multiple timescales and more complex signals. Their storage budget is still fixed by the state width.
Learn what survives
A constant decay treats an important parser definition and an irrelevant comment according to the same clock. Their contents change what gets written, but not how the system's parameters decide to retain and read it. Language needs more control: keep this variable binding, ignore that filler, reset when the document changes.
Mamba, Gu and Dao, 2023, makes selected state-space parameters depend on the current input. In its selective mechanism, the step size Δ and the write/read parameters B and C are input-dependent, while the base A is learned but input-independent. Discretization makes the effective transition depend on Δ. This gives the network content-dependent control over what enters and survives in the state.
Keep the binding, ignore the comment
Take the scalar continuous system dh/dt = −h + x, so A = −1 and B = 1. Zero-order-hold discretization gives ht = exp(−Δt)ht−1 + [1 − exp(−Δt)]xt. A small Δ nearly preserves the old state and barely writes the new input. A large Δ nearly replaces the old state with the new input. The same parameter therefore controls retention and writing.
Read a binding with value 7 and Δ = 8. From state zero, you get 6.997652. Now read two comments whose input value is zero. If their token type selects Δ = 0.01, the state after both is about 6.85909. If it selects Δ = 4, the state falls to about 0.002347. Finally, a query with Δ = 0 reads the surviving binding unchanged. Try both policies below.
at = e−Δt; ht = atht−1 + (1 − at)xt
One binding, two comments, one query
- Token
- Bind value 7
- Selected Δ
- 8
- Retention exp(−Δ)
- 0.000335
- Previous state
- 0
- Input gain 1 − exp(−Δ)
- 0.999665
- Updated state
- 6.997652
- Binding surviving after both comments
- 6.859089
- Bind value 7 with Δ = 8. The input gain 1 − exp(−8) writes almost the whole value.
- Read a comment with input 0. Its selected Δ decides how much of the existing binding survives.
- Read a second comment. Retention compounds: the binding is multiplied by exp(−2Δ).
- Read the binding with Δ = 0. The query carries the state forward unchanged.
Worked scalar zero-order-hold system: A = −1, B = C = 1, initial state 0. The input’s token type selects Δ; a trained Mamba learns its selection.
Making the parameters vary by token breaks the single stationary convolution kernel. An input at position j no longer contributes through a weight that depends only on t − j. Its path includes the transitions chosen at intervening positions. Efficient evaluation therefore needs a selective scan, along with kernels that avoid materializing every expanded state in accelerator memory.
Selection controls how a fixed-size state spends its memory budget. For the repository task, the model must decide what to preserve from the parser before seeing the final review question, unless that question is already supplied earlier in the prompt. Prompt order can change what a recurrent model has a chance to select.
Why exact associative recall is demanding
Imagine reading a list of arbitrary key–value assignments, followed by a query for one key. Full attention can retain a separate key/value entry for each assignment and select one after it sees the query. A fixed-size state must encode all useful assignments into the same bounded storage. As the list grows, unrelated bindings compete for that representation.
The toy below makes the competition literal. Each integer key maps to one feature bucket. Writing adds the value to that bucket and increments its count. Reading returns the bucket mean, exactly the normalized linear-attention result for those one-hot features. Before a collision, it retrieves the value perfectly. After a collision, it mixes multiple assignments. The full-attention comparison uses a hard exact-match mask over distinct keys, so its selected value remains available.
Σ 3
n 11
Σ 10
n 12
Σ 17
n 13
Σ 5
n 14
Σ 12
n 15
Σ 0
n 16
Σ 7
n 17
Σ 14
n 1
- Exact-match attention
- 3
- Compressed bucket readout
- 3
- Other keys in this bucket
- 0
- Stored scalars: state / full key–value list
- 16 / 16
Untrained collision toy: φ(key) is one-hot at key mod buckets. Full attention uses an exact-match mask. Values = (7 × key + 3) mod 19; the toy uses fixed, untrained features.
The collision threshold follows directly from the number of buckets in this toy. Learned models use distributed features, gates, nonlinearities and multiple layers to store richer associations. Their recall capacity depends on the learned representation and must be measured. The exact-match baseline here isolates the storage advantage of keeping each binding separate.
There is still a general constraint behind the example. A finite number of finite-precision state values provides finite storage. It cannot losslessly represent arbitrarily many independent random bindings. Natural text has redundancy and structure, so useful compression is possible. Exact recovery of a random earlier fact and good prediction of the next natural-language token can place very different demands on memory.
Attention and state spaces meet again
Mamba-2 and structured state-space duality, Dao and Gu, 2024, connect a structured recurrent model to an attention-like matrix. Write a discretized state update as ht = Ātht−1 + B̄txt, with output yt = Ctht. In the equations below, Bt denotes the discrete write vector B̄t. The direct input-to-output term can be added separately.
Mamba-1 uses diagonal state transitions with different decay rates across state coordinates. Mamba-2’s SSD layer restricts each head’s transition to a scalar times the identity: Āt = atI. All state coordinates within that head share the transition scalar, while the read and write vectors still vary with the input. Different heads can carry different scalar dynamics.
yt = ∑j≤t Mtjxj, Mtj = Ct (∏k=j+1t ak) Bj
Here Ct is a row read vector, Bj a column write vector, and the empty transition product at t = j is one. The input at j is written by Bj, carried through the intervening scalar decays, then read by Ct. In attention language, C supplies queries, B supplies keys, and the transition product supplies a structured causal mask. There is no softmax in this operator.
What semiseparable buys you
A causal matrix is N-semiseparable when its rectangular submatrices lying entirely in the causal triangle have rank at most N. The full sequence matrix can still have high rank. The useful constraint is on interactions across a cut between past inputs and future outputs.
Cut the sequence after position c. For j ≤ c < t, split the transition product at that boundary. Then Mtj = [Ct ∏k=c+1t ak] [∏k=j+1c ak Bj]. The first factor has N columns and the second N rows, so this entire off-diagonal block has rank at most N, the state dimension. All influence from before the cut passes through the same N-coordinate state. This factorization also works with general matrix transitions, with ordered products.
For scalar transitions alone, the causal decay mask is 1-semiseparable: its separated blocks have rank one. Combining that mask with the N-dimensional read/write inner products gives the SSD sequence operator its bounded block rank. This is the structural reason a compact recurrent state and an attention-like matrix multiplication can evaluate the same map.
Compute inside chunks, pass state between them
The SSD algorithm splits the sequence into fixed-length chunks. First, compute each chunk’s internal causal interactions with matrix multiplications, in parallel across chunks. Next, reduce each chunk’s inputs into its outgoing state contribution. Compose the chunk transitions to obtain the incoming state at every chunk boundary. Finally, multiply each incoming state by that chunk’s read factors and decays, then add this cross-chunk contribution to the internal outputs.
The dense operations are confined to small diagonal blocks; low-rank factors carry interactions between blocks. At fixed chunk and state sizes, total work grows linearly with sequence length. Most arithmetic becomes matrix multiplication suited to tensor cores, while the state propagation runs over the shorter sequence of chunk boundaries.
The original Jamba implementation, by Lieber and colleagues, grounds the hybrid approach in a concrete layout: four blocks of eight layers, each with one attention layer and seven Mamba layers. Every other layer uses MoE, selecting two of 16 experts per token. The attention layers retain direct access to earlier positions; Mamba layers carry recurrent states. In that 32-layer layout, four attention layers grow KV caches while 28 Mamba layers keep fixed-size recurrent states.
| Family | Carried forward | Read access | Memory shape |
|---|---|---|---|
| Dense attention | All previous K/V entries | Query can choose any retained token | Growing archive |
| Window + sinks | Recent K/V + selected prefix | Local access with indirect distant paths | Bounded archive |
| Linear attention / SSM | A running state | Read from a compressed history | Fixed-size summary |
| Hybrid | State + some attention caches | Use both memory mechanisms | Mixed memory |
A million-token request meets the server
Return to the million-token repository. The model has a suitable positional scheme and has been evaluated on the task. The server now has to make room for its state, perform prefill, and produce answer tokens while other requests compete for the same resources. The architecture determines the lower-level budget; the serving system decides how much of that budget is wasted or shared.
The illustrative GQA cache alone needs about 131 GB in 16-bit storage. Add weights, temporary buffers, activations, page tables and concurrent requests. Cache capacity can therefore limit batch size even when the weight matrices fit comfortably. A memory planner should count actual retained KV heads, layers and precision rather than multiply context length by total parameter count.
Prefill is a separate obstacle. For the illustrative configuration, one million tokens require about 262.144 PFLOP for ideal causal attention products. The gated MLP adds about 8.657 PFLOP, and Q/K/V plus output projections add about 2.684 PFLOP. At an assumed sustained 100 TFLOP/s for all these products, their sum alone corresponds to about 2,735 seconds, roughly 46 minutes. The assumed sustained rate sets this compute-only estimate.
At shorter lengths, the weight projections and MLP can dominate. At a million tokens, attention products dominate this dense configuration. Better kernels matter, but an order-of-magnitude increase in n eventually overwhelms a constant-factor speedup. A window changes the pair count; a faster dense kernel changes the cost per pair. That is why server optimization and architecture design remain separate levers.
Split the sequence across devices
Sequence and context parallelism divide sequence-related work across accelerators. Terminology varies by system: some schemes shard activations around otherwise tensor-parallel operations; others explicitly partition attention's query and KV sequences. Always ask what is sharded, which tensors move, and whether all devices together still evaluate the same dense pairs.
Ring Attention, Hao Liu, Zaharia and Abbeel, keeps local query blocks while passing key/value blocks around a device ring. Each device computes attention against successive blocks and accumulates an online softmax result. Communication can overlap block computation. Distributed storage makes a longer sequence fit, and more devices share the arithmetic, while the total dense pair count remains quadratic.
Each query needs three running quantities while KV tiles arrive: maximum score m, normalizer ℓ = ∑ exp(score − m), and value accumulator u = ∑ exp(score − m)v. A new tile computes its own mb, ℓb and ub. To merge them, choose m′ = max(m, mb) and rescale both summaries to that common maximum.
ℓ′ = em−m′ℓ + emb−m′ℓb
u′ = em−m′u + emb−m′ub; output = u′/ℓ′
Start with m = −∞, ℓ = 0 and u = 0. When a later tile contains a larger score, the old summary shrinks by exp(m − m′), preserving its contribution without overflow. For vector values, u is a vector and the same rescaling applies to every component. The scalar readout in the stepper computes these merges for one query; each device does the same operation for every query in its local block.
Device 0
Queries 0–3
Send KV to device 1
Device 1
Queries 4–7
Send KV to device 2
Device 2
Queries 8–11
Send KV to device 3
Device 3
Queries 12–15
Send KV to device 0
One query · arriving scores [1, 2]
- Running max m
- 2
- Normalizer ℓ
- 1.3679
- Accumulator u
- -0.2642
- Output u / ℓ
- -0.1932
One query · arriving scores [0, 3]
- Running max m
- 3
- Normalizer ℓ
- 1.5530
- Accumulator u
- 1.0522
- Output u / ℓ
- 0.6775
One query · arriving scores [2, 5]
- Running max m
- 5
- Normalizer ℓ
- 1.2600
- Accumulator u
- 4.0428
- Output u / ℓ
- 3.2087
One query · arriving scores [-1, 4]
- Running max m
- 5
- Normalizer ℓ
- 1.6303
- Accumulator u
- 4.7786
- Output u / ℓ
- 2.9311
Scalar value example, with tiles in arrival order: values [2, −1], [3, 1], [−2, 4], [0, 2]. Each round merges two more scores into the same query’s result.
- Each device keeps its query block and starts with its local KV block. This schedule shows dense all-pairs attention; a causal implementation masks future pairs.
- Pass each KV block one device clockwise. Compute the next query–key tile while the following block travels.
- Queries stay put. Running maxima, denominators and weighted sums combine the score tiles without storing a global score matrix.
- After four rounds, every query block has met all four KV blocks. The arithmetic is distributed across devices; the total pair count is unchanged.
The ring succeeds when local block computation is large enough to hide much of the KV transfer time. Small blocks, slow links or a poorly balanced causal schedule can expose communication. Causal masking creates uneven useful work if early queries and late queries are assigned naively: the latter read more past positions. Distributed kernels need both a correct reduction and an appropriate work partition.
Reuse what was already computed
For repeated reviews of an unchanged repository, exact prefix caching avoids recomputing the stable prefix on every request. Causal attention makes this possible: prefix K/V entries do not depend on a later question. Requests with different suffixes can reference the same immutable prefix blocks, with private storage for their own continuation.
Exact reuse requires more than matching visible prose. The token sequence, model weights, adapter state, positional treatment and relevant execution configuration must be compatible. Block-based caches typically reuse complete matching blocks. Moving one early token can invalidate a large suffix of reusable state. Changing a question after a stable repository prefix preserves much more reuse than inserting the question before it.
Three requests · identical 12-token prefix
Tokens 0–11 · compute once
Private suffix KV
Private suffix KV
Private suffix KV
Each suffix query still attends to the shared prefix. Reuse saves prefix computation and duplicate storage, while suffix work remains.
A suffix query still attends to the cached prefix. If an uncached suffix has m tokens after a cached prefix of n tokens, its attention includes roughly nm prefix–suffix pairs plus its own causal triangle. Decoding each additional answer token still reads the retained history. Prefix reuse can eliminate a large repeated prefill without turning the long context into a short one.
Offloading moves KV entries to host memory or another storage tier. It increases available capacity and can help park inactive sessions. If every dense decode step needs the offloaded entries, they must travel back over a slower link or be processed where they reside. Transfer latency and bandwidth then become part of every output token's cost. As a simple illustrative bound, moving 131.072 GB over a sustained 64 GB/s link takes about 2.05 seconds in one direction, before computation or protocol overhead.
Quantization reduces the bytes moved, while sparse access can avoid some transfers. These choices have different correctness implications: moving an exact cache changes its location; dropping entries changes the attention input; lowering precision changes stored numbers. Test them independently so that a quality regression can be tied to the mechanism that caused it.
For our review service, measure cold time to first token, warm time to first token, answer-token latency, and end-task correctness. Record the actual retained length and cache policy alongside those measurements. A system that quickly returns a plausible patch after losing the parser file has optimized the wrong outcome.
Distribution, prefix reuse and offloading change where work happens, when it happens, or where state lives. Track which arithmetic and information they preserve.
Parallel time, sequential memory
A recurrent model seems to require one step after another: ht depends on ht−1. That is true of a straightforward evaluation, but some recurrences have an associative summary operation. Once you find it, you can compute every prefix in a tree of parallel rounds. This is the bridge between sequential state updates and efficient training over whole sequences.
Take ht = atht−1 + bt. Each token describes an affine function, represented by the pair (at, bt). Applying the left function and then the right function gives another pair. The operation is associative because function composition is associative. It is generally not commutative: exchanging two tokens changes the result.
(aR, bR) ∘ (aL, bL) = (aRaL, aRbL + bR)
An inclusive parallel scan computes the composed map for every prefix. Apply each map to the initial state and you have every recurrent state. In the lab, the initial state is zero, so the b component of each prefix pair is already its output. For diagonal transitions, the same rule applies elementwise to vector states. General dense matrix transitions are also composable, but their composition cost can erase the benefit; practical models exploit structure.
The Hillis–Steele version starts with one map per token. In round one, every position combines with its immediate predecessor. In round two, it combines with the predecessor two positions away. Then four away, eight away, and so on. Each round must read the previous round, rather than partly updated neighbors. After ⌈log2 n⌉ rounds every position contains its full prefix.
Each cell represents h ↦ a × h + b
b 1
b 2
b 3
b 4
b 5
b 6
b 7
b 8
Round 0: each cell summarizes at most 1 consecutive maps. All updates read the previous round.
- Eight independent maps, each (a, b) = (0.5, token index + 1).
- Distance 1: compose each map with its left neighbor from the previous row.
- Distance 2: combine summaries spanning two tokens into four-token summaries.
- Distance 4: every cell holds its complete prefix. Apply to h = 0; the b entries are the recurrent states.
Hillis–Steele inclusive scan, using a separate previous row. Three parallel rounds for eight inputs; 17 compositions, compared with seven in a serial prefix calculation.
This schedule has O(log n) parallel depth and O(n log n) total work. A work-efficient tree scan such as Blelloch's uses an up-sweep and down-sweep to achieve O(n) work with O(log n) depth. Real GPU scans divide the input into blocks, scan locally, propagate block summaries and combine them. Synchronization, temporary storage and the cost of the summary operation all matter. For short scans, synchronization and launch costs can dominate.
Mamba's input-dependent parameters can be computed from token inputs before the selective state scan within a layer. Each token can therefore choose its transition before the state scan begins. The associative structure then lets the layer process a known input sequence in parallel. Autoregressive generation remains sequential across newly sampled tokens: you cannot scan future token inputs before you know what they are. The training dive follows the broader distinction between parallel training data and sequential generation.
The kernel must keep state close
A simple recurrent update can perform very little arithmetic per state element. Suppose it reads a, b and old h, computes a × h + b, then writes h. That is two FLOPs and four scalar memory operations. With two-byte operands and no reuse, the illustrative arithmetic intensity is 0.25 FLOP per byte. A fast arithmetic unit gains little if every update waits for off-chip memory.
Production kernels therefore fuse operations and keep state in registers or shared memory across useful work. Storing every expanded state after every token can destroy the memory advantage during training. Selective-scan implementations combine fusion, parallel decomposition and recomputation to avoid that traffic. The fixed-size decode state is persistent storage across tokens. Training additionally stores activations and backward-pass workspace.
Actual recurrence performance depends on batch size, state width, layout, fusion and occupancy. Some kernels can be limited by compute or synchronization instead. Low-intensity recurrence kernels tend to be memory-bound; higher-intensity formulations can use more of the chip's compute. Mamba-2's blockwise formulation creates larger matrix operations precisely to use the hardware more effectively. The GPU kernels dive explores how register pressure, tiling and data movement shape those choices.
When attention overtakes the MLP
Return once more to the cost calculator. A gated MLP has three dense matrices: gate, up and down. For model width d and intermediate width f, the forward products cost about 6ndfL FLOPs. Ideal causal attention products cost 2n(n + 1)dL. Equating them gives n + 1 = 3f, or approximately n = 3f. For our f = 11,008 example, the crossover is about 33,024 tokens.
This compares attention products with MLP products only, at equal layer counts. Q/K/V and output projections, softmax, activation functions and device communication add other costs. Noncausal dense attention has twice the leading attention work and therefore a different crossover. MoE, unequal value widths, sliding windows and recurrent blocks need their own formulas. The useful habit is to count the operations your actual architecture performs.
Our million-token review now has several possible implementations. Dense attention keeps all file tokens individually available and pays for global comparisons. Windows bound access and rely on local structure or extra routes. GQA and MLA make the archive cheaper per token. Recurrence reads the repository into a fixed-size state, with a learned choice about what survives. Hybrids reserve some capacity for both.
The right test is still the first question: can the model connect the parser to the wrapper and produce the correct fix? Measure that while changing length, placement, latency and memory policy. A million tokens is a capacity. Useful context is what the complete model and system can reliably do with them.
End of Long context · 9 levels, Idea to Machine
Where to next
Next in AI serving · 04 of 06
How a GPU runs a kernel, from threadIdx to DRAM
Follow a CUDA thread into a warp and onto an SM. Make branches diverge, scatter a memory request across sectors, and fix a transpose one bank conflict at a time.
Practical notes
Estimate KV-cache memory before loading a model
Compute GQA cache bytes from layer count, KV heads, head dimension and retained tokens. Use a separate latent-cache calculation for MLA models.