First Passage Attention

# First Passage Attention
Source: [https://arxiv.org/html/2610.22714](https://arxiv.org/html/2610.22714)
Yuxuan LiuAffiliation:Department of Mathematics, University of Bergen, Bergen, NorwayEmail:[yuxuan\.liu@uib\.no](mailto:)

October 2026

###### Abstract

Augmenting softmax attention with forget gates typically relies on summing decay contributions along the key–query path\. Because such accumulation is monotonic, these mechanisms cannot selectively erase intermediate context while preserving older, structurally relevant tokens\. We propose First Passage Attention \(FPA\), which shifts from path summation to path extrema by lowering a key’s logit proportionally to the deepest dip of a learned scalar field below that key’s level over the intervening span\. FPA encompasses the Forgetting Transformer \(FoX\) as a special case, and when the field and levels follow a shared learned walk, the alive keys with unpenalised logits naturally form a stack\. We show that a constant\-dimension FPA head realises any subset of keys left alive by subsequent dips, whereas softmax heads with positional biases or token\-level forget gates require a head dimension linear in the number of keys\. In synthetic experiments, one\-layer FPA heads converge to these target sets while comparable softmax and FoX baselines fail on every seed\. Scaling to a 110M\-parameter language model, FPA matches FoX in perplexity and uniquely achieves perfect passkey retrieval at8×8\\timesthe training length, even with its key–value cache compressed to about25%25\\%\.

\(a\) Softmax attention ℓt​s=qt⊤​ks\\ell\_\{ts\}=q\_\{t\}^\{\\top\}k\_\{s\}The deletedtkeeps its weight\.\(b\) Forgetting Transformer ℓt​s=qt⊤​ks\+∑s<u≤tlog⁡fu\\ell\_\{ts\}=q\_\{t\}^\{\\top\}k\_\{s\}\+\\sum\_\{s<u\\leq t\}\\log f\_\{u\}Removingtalso removescanda\.\(c\) First Passage Attention ℓt​s=qt⊤​ks\+β​min⁡\(0,mins<u≤t⁡ϕu−ψs\)\\ell\_\{ts\}=q\_\{t\}^\{\\top\}k\_\{s\}\+\\beta\\min\\bigl\(0,\\min\_\{s<u\\leq t\}\\phi\_\{u\}\-\\psi\_\{s\}\\bigr\)Onlytis removed\.The bias of keyssdepends on \(a\) nothing afterss\(b\) every forget gate afterss\(c\) only the deepest dip of the field below the level ofss

Figure 1:Three heads read the same typed word\.A user typesc,aandt, deletestwith the backspace key \(←\\leftarrow\) and typesr, so the query?should attend toc,aandr\. Every character has the content scoreqt⊤​ks=2q\_\{t\}^\{\\top\}k\_\{s\}=2and every other token−2\-2\. \(a\) Softmax attention has no term that a later token can change\. \(b\) The Forgetting Transformer \(FoX\) can removetonly through a small forget gatefuf\_\{u\}at←\\leftarrow, and that gate lowerscandaas well\. \(c\) First Passage Attention \(FPA\) in its stack form uses the walkWWas the fieldϕ\\phiand as the levelψ\\psi, with strengthβ=4\\beta=4\. Onlythas a level above the lowest later value ofWW, so onlytloses its weight\.## 1Introduction

Transformers power most modern large language models, with softmax attention serving as their central operation\([Vaswani et al\., 2017](https://arxiv.org/html/2610.22714#bib.bib1);[Jiang et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib64)\)\. Standard attention scores each earlier token by matching its key against the current query, typically incorporating relative positional encodings such as rotary embeddings or distance penalties\([Press et al\., 2022](https://arxiv.org/html/2610.22714#bib.bib3);[Su et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib2)\)\. Intervening tokens between a key and a query do not directly enter this score\. In many sequences, however, a subsequent event renders earlier information obsolete\. A backspace deletes the last typed character, a closing bracket terminates an enclosed scope, and a reassignment overwrites a variable’s value\. Crucially, such events often invalidate a newer key while leaving older keys intact\.

Several recent mechanisms modulate attention logits via sums, products, or transformations accumulated along the key–query path\([Csordás et al\., 2022](https://arxiv.org/html/2610.22714#bib.bib24);[Golovneva et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib25);[Tan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib5);[Yang et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib26);[Zhang et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib12)\)\. The Forgetting Transformer \(FoX\) integrates recurrent forget gates into softmax attention to improve long\-context modelling and length extrapolation\([Lin et al\., 2025a](https://arxiv.org/html/2610.22714#bib.bib4)\)\. Selective Attention allows tokens to mark earlier keys as obsolete\([Leviathan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib6)\), and Dynamic Context Pruning \(DCP\) drops keys to reduce inference memory\([Anagnostidis et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib7)\)\. However, because these mechanisms aggregate path contributions via summation or multiplication, they face two structural limitations\. First, token\-level forget gates \(as in FoX\) attenuate keys monotonically with age, which makes it impossible to erase a recent token without simultaneously suppressing all older ones\. Second, pairwise accumulation \(as in Selective Attention and DCP\) causes suppression to grow with the number of intervening steps \(confounding the*depth*of an event with its*duration*\) while incurring pairwise computation overhead\.

We introduceFirst Passage Attention \(FPA\), which aggregates the key–query path by its*minimum*rather than its sum\. Each head computes a scalar field at every position and a scalar level for every key\. A key’s logit remains unattenuated \(the key is alive\) as long as the subsequent field stays at or above its level\. Otherwise, FPA lowers the logit in proportion to the depth of the deepest dip below that level, regardless of how long that dip lasts\. We show that a single linear parameterisation encompasses FoX, a bottleneck bias, and learned expiry\([Sukhbaatar et al\., 2021](https://arxiv.org/html/2610.22714#bib.bib11)\)as special cases\. Most notably, when the field and levels share a learned walk \(a prefix sum of per\-token increments\), any drop in the walk selectively eliminates only those alive keys whose levels lie above the new value\. The alive keys naturally evolve as a stack, which allows a later token to erase a newer key while preserving older ones \([Figure1](https://arxiv.org/html/2610.22714#S0.F1)\)\.

We prove that in one layer a single constant\-dimension FPA head realises every dip\-induced alive set, whereas softmax heads with positional biases or token\-level forget gates need a head dimension linear in the number of keys\. We also prove that range extrema uniquely achieve duration\-invariant suppression, so FPA fits variable\-duration dips where additive selection fails, and that head\-specific fields overcome the dimension bottleneck of layer\-shared masks\. We implement FPA in a deterministic Triton kernel that runs about as fast as PyTorch’s scaled dot\-product attention \(SDPA\) in training\. In preregistered one\-layer probes, FPA learns our theoretical target families on most seeds, whereas the baselines that our lower bounds cover fail on every seed\. We train a 110M\-parameter FPA language model that matches FoX in perplexity and uniquely achieves100%100\\%passkey retrieval at4×4\\timesand8×8\\timesits training length, even with about a quarter of its key–value cache\.

## 2First Passage Attention

In this section we define the bias and its parameterisation, list its special cases and properties, and describe how we train and compute it\.

#### Definition\.

Let a causal head of dimensionddhave queriesqtq\_\{t\}, keysksk\_\{s\}and valuesvsv\_\{s\}, a scalar fieldϕu\\phi\_\{u\}at every position and a scalar levelψs\\psi\_\{s\}for every key\. FPA outputs∑s≤twt​s​vs\\sum\_\{s\\leq t\}w\_\{ts\}v\_\{s\}with the softmax weightswt​s∝eℓt​sw\_\{ts\}\\propto e^\{\\ell\_\{ts\}\}of the logitsℓt​s=qt⊤​ks/d\+bt​s\\ell\_\{ts\}=q\_\{t\}^\{\\top\}k\_\{s\}/\\sqrt\{d\}\+b\_\{ts\}, where the first\-passage bias is

bt​s=β​min⁡\(0,mins<u≤t⁡ϕu−ψs\)b\_\{ts\}=\\beta\\min\\Bigl\(0,\\ \\min\_\{s<u\\leq t\}\\phi\_\{u\}\-\\psi\_\{s\}\\Bigr\)\(1\)with a learned strengthβ\>0\\beta\>0, andbt​t=0b\_\{tt\}=0\. We writeϕ¯t​s=mins<u≤t⁡ϕu\\bar\{\\phi\}\_\{ts\}=\\min\_\{s<u\\leq t\}\\phi\_\{u\}for the range minimum of the field after keyss\.

###### Definition 2\.1\(Alive and dead keys\)\.

Keys≤ts\\leq tis alive at timettifbt​s=0b\_\{ts\}=0, that is ifs=ts=torϕ¯t​s≥ψs\\bar\{\\phi\}\_\{ts\}\\geq\\psi\_\{s\}, and dead otherwise\. The alive keys at timettform the alive set, and a dip is a decrease of the field below the level of an earlier key\.

Asβ→∞\\beta\\to\\infty, the bias of a dead key tends to−∞\-\\inftyand its weight to zero\. For a finite strength the bias of a dead keyssis−β\-\\betatimes the depthψs−ϕ¯t​s\\psi\_\{s\}\-\\bar\{\\phi\}\_\{ts\}of its deepest dip\.

#### Walk, field and level\.

Each head computes three scalars at every position from the inputxtx\_\{t\}of the layer by linear maps, an incrementδt\\delta\_\{t\}and two offsetsgtg\_\{t\}andhth\_\{t\}\. With the walkWt=∑u≤tδuW\_\{t\}=\\sum\_\{u\\leq t\}\\delta\_\{u\}, the field and the level are

ϕt=Wt\+gt,ψt=Wt\+ht,\\phi\_\{t\}=W\_\{t\}\+g\_\{t\},\\qquad\\psi\_\{t\}=W\_\{t\}\+h\_\{t\},\(2\)and the strengthβ\\betais a learned positive scalar per head\. A token can thus move the reference of every later comparison throughδ\\delta, and it can dip or set a level without moving it throughggandhh\. A layer of widthDDwithHHheads gains3​H​\(D\+1\)\+H3H\(D\+1\)\+Hparameters, 332 thousand in our 110M language model\.

###### Proposition 2\.2\(Special cases\)\.

Under \([2](https://arxiv.org/html/2610.22714#S2.E2)\) the following hold\.

1. \(a\)Ifg=h=0g=h=0, thenbt​s=−β​Lt​sb\_\{ts\}=\-\\beta L\_\{ts\}withLt​s=max⁡\(0,maxs<u≤t⁡\(Ws−Wu\)\)L\_\{ts\}=\\max\\bigl\(0,\\max\_\{s<u\\leq t\}\(W\_\{s\}\-W\_\{u\}\)\\bigr\), the regulator of a queue that starts empty at timessand receives the net inputδu\\delta\_\{u\}at stepuu\.
2. \(b\)If in additionδu≤0\\delta\_\{u\}\\leq 0for alluu, thenbt​s=∑s<u≤tlog⁡fub\_\{ts\}=\\sum\_\{s<u\\leq t\}\\log f\_\{u\}withfu=eβ​δu∈\(0,1\]f\_\{u\}=e^\{\\beta\\delta\_\{u\}\}\\in\(0,1\], the bias of FoX with forget gatesfuf\_\{u\}\.
3. \(c\)Ifδ=0\\delta=0,h=0h=0,g≤0g\\leq 0andβ=1\\beta=1, thenbt​s=mins<u≤t⁡gub\_\{ts\}=\\min\_\{s<u\\leq t\}g\_\{u\}, a bottleneck bias\.
4. \(d\)Ifδu=−1\\delta\_\{u\}=\-1,g=0g=0andhs=−esh\_\{s\}=\-e\_\{s\}withes≥0e\_\{s\}\\geq 0, thenbt​s=β​min⁡\(0,es−\(t−s\)\)b\_\{ts\}=\\beta\\min\\bigl\(0,e\_\{s\}\-\(t\-s\)\\bigr\), so keyssis alive exactly whilet−s≤est\-s\\leq e\_\{s\}\.

We call the caseg=h=0g=h=0the stack form, for a reason that[Proposition2\.3](https://arxiv.org/html/2610.22714#S2.Thmtheorem3)gives\. Part \(b\) makes FoX the stack form with a walk that never rises\. A rising walk lets FPA keep an old key while it removes newer ones, which no forget gate can do \([Figure1](https://arxiv.org/html/2610.22714#S0.F1)\)\. Part \(a\) reads the stack form as a queue\([Lindley, 1952](https://arxiv.org/html/2610.22714#bib.bib8);[Skorokhod, 1961](https://arxiv.org/html/2610.22714#bib.bib9)\), and the strengths of the Neural Stack follow the same closed form\([Grefenstette et al\., 2015](https://arxiv.org/html/2610.22714#bib.bib10)\)\. We use this reading only as an interpretation\. Part \(d\) has the expiry rule of Expire\-Span\([Sukhbaatar et al\., 2021](https://arxiv.org/html/2610.22714#bib.bib11)\), and part \(b\) is not the only way to contain FoX in a larger family\([Zhang et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib12)\)\.

###### Proposition 2\.3\(Death is permanent, and the stack form gives a stack\)\.

\(a\) For alls<t<t′s<t<t^\{\\prime\},bt′​s≤bt​sb\_\{t^\{\\prime\}s\}\\leq b\_\{ts\}, so a dead key stays dead\. \(b\) Ifϕ=ψ=W\\phi=\\psi=W, the levelsWsW\_\{s\}of the keys alive at timettdo not decrease withss, and the keys that stepuukills form a suffix in time of the keys alive atu−1u\-1\. The alive set therefore evolves as a stack\.

Selective Attention and DCP share the property of part \(a\), which both papers state\([Anagnostidis et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib7);[Leviathan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib6)\)\. The weights of the alive keys still change when other keys die, because the softmax renormalises over the keys that remain\.

#### Training\.

The bias is piecewise linear in the field and the levels\. On the closed side of the outer minimum it passes no gradient to the field, and in our pilot runs this minimum could close for every key of a head early in training and stay closed\. We train FPA with a straight\-through estimator for this reason\. The forward pass uses the range minimum, and the backward pass uses in its place the gradient of the soft minimum−τlog∑s<u≤te−ϕu/τ\-\\tau\\log\\sum\_\{s<u\\leq t\}e^\{\-\\phi\_\{u\}/\\tau\}withτ=1\\tau=1\. The outer minimum acts on the hard value, and evaluation uses the bias of \([1](https://arxiv.org/html/2610.22714#S2.E1)\) unchanged\.

###### Proposition 2\.4\(Cost\)\.

\(a\) In a blocked computation with block sizeBB, the bias between a query blockIIand an earlier key blockJJdepends on the field only through three quantities\. They are the suffix minima ofϕ\\phiwithinJJ, the minimum ofϕ\\phiover the blocks strictly betweenJJandII, and the prefix minima ofϕ\\phiwithinII\. It costsO⁡\(B2\)O\(B^\{2\}\)operations per pair of blocks, as an element\-wise bias such as that of FoX does, together withO⁡\(T/B\)O\(T/B\)block minima for a sequence of lengthTT\. \(b\) In autoregressive decoding,ϕ¯t​s=min⁡\(ϕ¯t−1,s,ϕt\)\\bar\{\\phi\}\_\{ts\}=\\min\(\\bar\{\\phi\}\_\{t\-1,s\},\\phi\_\{t\}\)fors<t−1s<t\-1andϕ¯t,t−1=ϕt\\bar\{\\phi\}\_\{t,t\-1\}=\\phi\_\{t\}, so each step updates the bias row inO⁡\(t\)O\(t\)operations and stores two scalars per cached key and head\.

The decomposition of part \(a\) is the standard blocked range minimum\([Bender and Farach\-Colton, 2000](https://arxiv.org/html/2610.22714#bib.bib13)\)\. Our Triton kernel fuses it with the attention, which it computes in blocks with an online softmax as fused attention kernels do\. In the backward pass it computes the soft\-minimum gradient for the positions in the key block, in the query block, in the blocks between and in the diagonal block\. It adds nothing atomically, so its gradients are deterministic \([AppendixE](https://arxiv.org/html/2610.22714#A5)\)\. The kernel needs the range minimum only for a finite strength\. In the hard limit every key is visible on one interval of queries, which mask formats such as that of FlashMask already represent\([Wang et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib14)\)\. Selective Attention and DCP, by contrast, accumulate a score for every pair of a later token and a key\. Their bias for a pair of blocks depends on the score of every token in between with every key of the block\.[Section4\.3](https://arxiv.org/html/2610.22714#S4.SS3)compares the cost of FPA and Selective Attention\.

## 3Theory

In this section we compare FPA with other heads on three properties of the alive set\. All proofs are in[AppendixA](https://arxiv.org/html/2610.22714#A1), and each argument is short\.

### 3\.1Alive sets chosen by later dips

Fixr≥3r\\geq 3\. The ladder familyℱr\\mathcal\{F\}\_\{r\}consists of2r−12^\{r\-1\}sequences of length3​r3r\([SectionA\.1](https://arxiv.org/html/2610.22714#A1.SS1)\)\. Every sequence starts with⟨s⟩\\langle\\mathrm\{s\}\\rangle, places the same key tokenKat the positionsσj=3​j−2\\sigma\_\{j\}=3j\-2forj=1,…,rj=1,\\dots,r, and ends with the query token?\. Between keyjjand keyj\+1j\+1it places eitherUDorDU, and the tokensK,UandDhave the walk increments11,12\\tfrac\{1\}\{2\}and−12\-\\tfrac\{1\}\{2\}\. In the stack form, keyj<rj<ris alive at the final query exactly whenUDfollows it, so the alive sets of the family are all2r−12^\{r\-1\}subsets of the firstr−1r\-1keys, each with the last key\. We say that a head realises an alive setAAwith toleranceε\\varepsilonwhen, at the final query, every key inAAhas weight at least\(1−ε\)/\|A\|\(1\-\\varepsilon\)/\|A\|and the other keys have total weight at mostε\\varepsilon\.

###### Theorem 3\.1\(Positional biases\)\.

Let a head have logits⟨qt,ks⟩\+ρ⁡\(t,s\)\+ct\\langle q\_\{t\},k\_\{s\}\\rangle\+\\rho\(t,s\)\+c\_\{t\}\. Hereks∈ℝdk\_\{s\}\\in\\mathbb\{R\}^\{d\}depends only on the token and the position ofss,ρ\\rhois any fixed function of the two positions, andqtq\_\{t\}andctc\_\{t\}may depend arbitrarily on the prefix up tott\. If on every sequence ofℱr\\mathcal\{F\}\_\{r\}every alive key receives more weight than every dead key at the final query, thend≥r−2d\\geq r\-2\. The bound still holds when the head adds a path term∑s<u≤tλ⁡\(xu\)\\sum\_\{s<u\\leq t\}\\lambda\(x\_\{u\}\)in whichλ\\lambdadepends only on the tokenxux\_\{u\}and may take either sign\.

The path term covers a FoX head whose forget gates depend only on the token, as in the first layer of a model without positional embeddings\. The condition on the weights holds whenever the head realises the alive sets with toleranceε<1/\(r\+1\)\\varepsilon<1/\(r\+1\)\. In the first layer every key depends only on its token and position\. Deeper keys may read their prefix, and[Theorem3\.2](https://arxiv.org/html/2610.22714#S3.Thmtheorem2)bounds such heads by their precision\.

###### Theorem 3\.2\(Keys fixed when written\)\.

Let a head have logits⟨qt,ks⟩\+ρ⁡\(t,s\)\+ct\\langle q\_\{t\},k\_\{s\}\\rangle\+\\rho\(t,s\)\+c\_\{t\}withqt,ks∈ℝdq\_\{t\},k\_\{s\}\\in\\mathbb\{R\}^\{d\}\. Letksk\_\{s\}depend only on the prefix up toss, letqtq\_\{t\}andctc\_\{t\}depend on the prefix up tott, and letρ\\rhobe a fixed function of the two positions\. Let every coordinate ofqtq\_\{t\}take one of at most2p2^\{p\}values from a set that does not depend on the input, with logits and weights evaluated exactly\. If the head realises the alive set of every sequence ofℱr\\mathcal\{F\}\_\{r\}with tolerance0<ε≤1/\(2​r\+2\)0<\\varepsilon\\leq 1/\(2r\+2\), thend​p≥r−2dp\\geq r\-2\.

###### Proposition 3\.3\(One FPA head\)\.

Let a head use the stack form onℱr\\mathcal\{F\}\_\{r\}and add to its bias a one\-dimensional dot product, whose query is the constant−M\-Mand whose key is11at the tokens other thanKand00atK\. Ifβ≥2​log⁡\(2​\(r−1\)/ε\)\\beta\\geq 2\\log\(2\(r\-1\)/\\varepsilon\)andM≥log⁡\(4​r/ε\)M\\geq\\log\(4r/\\varepsilon\), this head realises the alive set of every sequence ofℱr\\mathcal\{F\}\_\{r\}with toleranceε\\varepsilon, and its walk takes at most2​r\+12r\+1values\.

Atε=1/\(2​r\+2\)\\varepsilon=1/\(2r\+2\)one FPA head thus uses scalars ofO⁡\(log⁡r\)O\(\\log r\)bits and constantsβ\\betaandMMof orderlog⁡r\\log r, whereas the heads of[Theorems3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2610.22714#S3.Thmtheorem2)needr−2r\-2dimensions orr−2r\-2bits of query in total\. The proof of[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)bounds how many sign patterns affine functions can take on fixed points, a classical argument\([Cover, 1965](https://arxiv.org/html/2610.22714#bib.bib15);[Dudley, 1978](https://arxiv.org/html/2610.22714#bib.bib16)\)that earlier lower bounds for attention also use\([Sanford et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib18);[Weller et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib19)\)\. In the proof of[Theorem3\.2](https://arxiv.org/html/2610.22714#S3.Thmtheorem2)we instead count the values that the query must take\. What is new is the family of alive sets that later dips create, and the comparison with a single range minimum\.

The results of this subsection do not cover biases in which a later token acts on each key separately\. Selective Attention, DCP and keys that later tokens update\([Song et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib20)\)realise the same alive sets in the hard limit, so FPA is not more expressive than they are in that limit\. FPA differs from Selective Attention and DCP in that its bias depends only on scalars of single positions \([Proposition2\.4](https://arxiv.org/html/2610.22714#S2.Thmtheorem4)\), and from Selective Attention in its dependence on depth rather than duration \([Section3\.2](https://arxiv.org/html/2610.22714#S3.SS2)\)\. The results also say nothing about deeper models, because a few layers of softmax attention can compute bracket depth\([Yao et al\., 2021](https://arxiv.org/html/2610.22714#bib.bib21);[Hayakawa and Sato, 2025](https://arxiv.org/html/2610.22714#bib.bib22)\)\. Without a bound on precision no lower bound onddholds for the ordering condition of[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1), since keys that read their prefix can encode the alive set in one coordinate \([AppendixA](https://arxiv.org/html/2610.22714#A1)\)\. Finally, the theorems constrain the weights of one head and not the function of a layer, since one attention layer with low\-rank weights and feed\-forward layers already approximates every continuous permutation\-equivariant function\([Kajitsuka and Sato, 2024](https://arxiv.org/html/2610.22714#bib.bib23)\)\.

### 3\.2Depth, not duration

LetDt​smax=maxs<u≤t⁡\(ψs−ϕu\)\+D^\{\\max\}\_\{ts\}=\\max\_\{s<u\\leq t\}\(\\psi\_\{s\}\-\\phi\_\{u\}\)\_\{\+\}denote the deepest dip after keyssandDt​ssum=∑s<u<t\(ψs−ϕu\)\+D^\{\\mathrm\{sum\}\}\_\{ts\}=\\sum\_\{s<u<t\}\(\\psi\_\{s\}\-\\phi\_\{u\}\)\_\{\+\}the sum of its dips, where\(x\)\+=max⁡\(0,x\)\(x\)\_\{\+\}=\\max\(0,x\)\. Selective Attention subtracts from the logit of keyssthe selectionFt​sF\_\{ts\}that the tokens betweenssandttassign to it\([Leviathan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib6)\)\.

###### Proposition 3\.4\(Depth, not duration\)\.

The first\-passage bias isbt​s=−β​Dt​smaxb\_\{ts\}=\-\\beta D^\{\\max\}\_\{ts\}, whereas Selective Attention with a selection head of the formω⁡\(ψs−ϕu\)\\omega\(\\psi\_\{s\}\-\\phi\_\{u\}\),ω\>0\\omega\>0, subtractsFt​s=ω​Dt​ssumF\_\{ts\}=\\omega D^\{\\mathrm\{sum\}\}\_\{ts\}for every key after the first token\.

1. \(i\)Inserting into\(s,t\)\(s,t\)steps whose dips belowψs\\psi\_\{s\}are at mostDt​smaxD^\{\\max\}\_\{ts\}, while every other position keeps its values, leavesbt​sb\_\{ts\}unchanged\. For a key after the first token it increasesFt​sF\_\{ts\}byω\\omegatimes the sum of the inserted dips\.
2. \(ii\)For every depthη\>0\\eta\>0and everym≥1m\\geq 1there are inputs withDt​smax=ηD^\{\\max\}\_\{ts\}=\\etaandDt​ssum=m​ηD^\{\\mathrm\{sum\}\}\_\{ts\}=m\\eta\.
3. \(iii\)LetΓ\\Gammamap every finite non\-empty multiset of non\-negative reals to a real number\. IfΓ\\Gammadoes not change when any value at most the maximum is added, thenΓ\\Gammadepends only on the maximum, and every function of the maximum has this property\.

Part \(iii\) makes functions of the maximum the only aggregations of dips that do not change when a dip no deeper than the deepest is added or held longer\. When the durations of the dips vary within the training data, the difference matters already for fitting it, not only for generalising\.

###### Proposition 3\.5\(Durations that vary in training\)\.

Let a sequence containr≥2r\\geq 2keys at increasing levels at least five apart, each followed with positive probability by a dip of depthη∈\{1,2,3,4\}\\eta\\in\\\{1,2,3,4\\\}\. The dip consists of three steps at the depthsη\\eta,η−1\\eta\-1and00in any order, and its deepest step is held for one or two steps\. Every combination of the level of the first key, depth, order and duration occurs with positive probability\. Let the target weight of keyjjat the query be proportional toe−κ​ηje^\{\-\\kappa\\eta\_\{j\}\}withκ\>0\\kappa\>0, whereηj=0\\eta\_\{j\}=0without a dip\. \(a\) No head whose logit for keyssisμ⁡\(xs\)−∑s<u<tχ⁡\(xu,xs\)\\mu\(x\_\{s\}\)\-\\sum\_\{s<u<t\}\\chi\(x\_\{u\},x\_\{s\}\), whereμ\\muandχ≥0\\chi\\geq 0read only the tokens, realises the targets exactly on the keys of all such sequences\. \(b\) One FPA head realises them exactly, and its bias does not change when a step is held longer or a further dip of a key, no deeper than its own, is inserted before the next key\.

The class of part \(a\) contains Selective Attention whose queries and keys depend only on the token, and it contains FoX whose gates, queries and keys read only the token\. The proposition concerns exact fits, and we have not bounded what the class reaches within a tolerance\.

### 3\.3One field per head

Selective Attention computes one mask per layer from the selection of one head and subtracts it from every head, and DCP also adds one mask per layer\([Anagnostidis et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib7);[Leviathan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib6)\)\. The two\-walk family𝒢r\\mathcal\{G\}\_\{r\}interleaves two walks in the same tokens \([AppendixA](https://arxiv.org/html/2610.22714#A1)\)\. Every key token raises both walks by one, and the two tokens after keyjjfollow patternPj\(1\)P^\{\(1\)\}\_\{j\}for the first walk andPj\(2\)P^\{\(2\)\}\_\{j\}for the second, as inℱr\\mathcal\{F\}\_\{r\}\. In its complementary part,P\(2\)P^\{\(2\)\}is the complement ofP\(1\)P^\{\(1\)\}, so every key except the last is alive under exactly one walk\.

###### Proposition 3\.6\(A shared mask\)\.

Let two headsh∈\{1,2\}h\\in\\\{1,2\\\}have the logits⟨qh,ksh⟩\+ρh​\(t,s\)\+ch−Fs\\langle q^\{h\},k^\{h\}\_\{s\}\\rangle\+\\rho^\{h\}\(t,s\)\+c^\{h\}\-F\_\{s\}at the final query\. Hereksh∈ℝdk^\{h\}\_\{s\}\\in\\mathbb\{R\}^\{d\}depends only on the token and the position ofss,ρh\\rho^\{h\}is fixed,qhq^\{h\}andchc^\{h\}depend arbitrarily on the sequence, and the maskFsF\_\{s\}is the same for both heads\. Let headhhfollow walkhhon every sequence\. \(a\) At mostN⁡\(r,d\)=∑i≤2​d\+1\(r−1i\)N\(r,d\)=\\sum\_\{i\\leq 2d\+1\}\\binom\{r\-1\}\{i\}sequences of the complementary part have each head rank its alive keys above its dead keys, so all2r−12^\{r\-1\}require2​d≥r−22d\\geq r\-2\. \(b\) With tolerance0<ε≤1/\(2​r\+2\)0<\\varepsilon\\leq 1/\(2r\+2\), at mostN′​\(r,d\)=∑i≤2​d\(r−1i\)N^\{\\prime\}\(r,d\)=\\sum\_\{i\\leq 2d\}\\binom\{r\-1\}\{i\}of them have each head realise its alive set, so all require2​d≥r−12d\\geq r\-1\.

FPA with one walk per head realises both alive sets on every sequence with one\-dimensional dot products \(by the proof of[Proposition3\.3](https://arxiv.org/html/2610.22714#S3.Thmtheorem3)\)\. A shared mask therefore at most halves the dimension that[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)demands, and it does not remove the dependence onrr\. Forr=14r=14andd=2d=2the bounds are 2,380 and 1,093 of the 8,192 sequences\. The bound concerns the shared mask, a design choice of Selective Attention and DCP, and Selective Attention with one mask per head lies outside it\.

## 4Experiments

We ran three groups of experiments, namely one\-layer probes of the results in[Section3](https://arxiv.org/html/2610.22714#S3), language models, and measurements of cost\. We preregistered every experiment except those that we mark as exploratory, and[AppendicesB](https://arxiv.org/html/2610.22714#A2),[C](https://arxiv.org/html/2610.22714#A3),[D](https://arxiv.org/html/2610.22714#A4)and[E](https://arxiv.org/html/2610.22714#A5)give the full protocols, the records of the hyperparameter searches and the amendments\.

### 4\.1One\-layer probes

Table 1:Seeds out of 15 that succeeded in the one\-layer probes\.The alive\-set columns use the ladder family with head dimensiond=4d=4, where positional heads realise all alive sets only forr≤6r\\leq 6\. The varied durations hold the deepest step of each dip for one or two steps in training, the two walks are the complementary part of the two\-walk family \(r=14r=14,d=2d=2per head\), and the stack column uses push and pop sequences\. A dash marks a pair that we did not run\. Withd=r\+2d=r\+2every positional head and FoX succeeded on all seeds\. Selective Attention∗lies outside the class of[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)\. FPA, First Passage Attention\. RoPE, rotary position embedding\. NoPE, no positional encoding\. ALiBi, attention with linear biases\. FoX, Forgetting Transformer\. DCP, Dynamic Context Pruning\.Each probe was one attention layer whose weights at the final query we supervised directly \([AppendixB](https://arxiv.org/html/2610.22714#A2)\)\. On the alive\-set, two\-walk and stack families we counted a seed as a success when the head ranked every alive key above every dead key on at least 90% of the test sequences\. On the varied\-duration family we required the weights on the keys to lie within total variation0\.050\.05of the target on at least 90% of the sequences, for both durations\. We tuned each competitor on a matched positive control, and every setting ran on 15 seeds\. In the probes we trained the selection of Selective Attention with a softplus straight\-through gradient, which keeps its selection from closing early, whereas the language model used the gradient of its paper\. We compared FPA with each competitor by a one\-sided exact McNemar test on the seeds that succeeded, at levelα=0\.05/7\\alpha=0\.05/7, and a hypothesis held only when all its comparisons rejected\.

#### Alive sets\.

Withd=4d=4,[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)lets a positional head realise every alive set only forr≤6r\\leq 6\. We tested softmax heads with rotary position embedding \(RoPE\), without positional encoding \(NoPE\) and with linear biases \(ALiBi\), and FoX heads whose gates read only the token\. They succeeded atr=6r=6on 14 or 15 seeds and failed on every seed forr=10r=10, 14 and 18 \([Tables1](https://arxiv.org/html/2610.22714#S4.T1)and[5](https://arxiv.org/html/2610.22714#A2.T5)\)\. The same heads withd=r\+2d=r\+2succeeded on all seeds, so the failures do not come from training\. FPA heads succeeded on 11, 12 and 13 seeds, and all twelve comparisons rejected \(p=0\.00049p=0\.00049\)\. Selective Attention, whose bias depends on later tokens, lies outside the theorem and succeeded as well\. Four\-layer softmax and FoX models learned the task forr=14r=14andr=18r=18, as[Section3\.1](https://arxiv.org/html/2610.22714#S3.SS1)anticipates for deeper models\.

#### Durations\.

When the deepest step of each dip lasted one or two steps in training \([Proposition3\.5](https://arxiv.org/html/2610.22714#S3.Thmtheorem5)\), FPA succeeded on 13 seeds\. Selective Attention and FPA with the sum of dips in place of the minimum succeeded on none \(p=0\.00012p=0\.00012for both\)\. Both competitors fitted the same family with fixed durations on all 15 seeds, so they failed only when the durations varied\.

#### Two walks\.

With two heads of dimension 2 on the complementary part of the two\-walk family, FPA succeeded on 11 seeds, and Selective Attention and DCP, whose heads share one mask, on none \(p=0\.00049p=0\.00049each\)\. Both learned identical walks with one mask \(15 and 13 seeds\), and Selective Attention with one mask per head learned the complementary part on 13 seeds\. We thus attribute the failures to the shared mask, and no run exceeded the bounds of[Proposition3\.6](https://arxiv.org/html/2610.22714#S3.Thmtheorem6)\.

#### Stack and retrieval\.

On push and pop sequences FPA succeeded on 14 seeds and FPA with the sum of dips on 11, while one\-layer FoX, softmax and Selective Attention heads succeeded on none\. A further task asked for the occurrences of a name among the alive keys, so it needs both a level per key and retrieval by content \([SectionB\.6](https://arxiv.org/html/2610.22714#A2.SS6)\)\. FPA succeeded on all 15 seeds, and variants without the level of the key, with the level of the query instead, or without retrieval by content succeeded on none, as did FoX, stick\-breaking attention and softmax attention\. Selective Attention succeeded on 13 seeds\.

#### Tasks from earlier work\.

On six published tasks with small decoders \([SectionB\.7](https://arxiv.org/html/2610.22714#A2.SS7)\), FPA succeeded on every seed in flip\-flop language modelling, copying and counting, and on 9 of 15 in variable assignment, where FoX succeeded on all\. In multi\-query repeated associative recall no model succeeded on more than 4 seeds\. In multi\-query associative recall FPA failed on every seed, where softmax attention succeeded on all\. In our diagnosis, the bias of the first layer suppressed the attention from each value to its own key early in training, so the first step of the recall circuit never formed\. An FPA model without a bias in its first layer succeeded on all 15 seeds, and in an exploratory check three\- and four\-layer FPA models failed as the two\-layer one did\.

### 4\.2Language models

We trained four decoders with 12 layers of width 768 and 12 heads of dimension 64 on 2\.7B tokens of SlimPajama\([Soboleva et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib62)\), following the 125M recipe of FoX\([Lin et al\., 2025a](https://arxiv.org/html/2610.22714#bib.bib4)\)with the 32k\-token vocabulary of Mistral 7B\([Jiang et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib64)\)\. The models differed only in attention, namely FPA and FoX without positional encoding, Selective Attention with RoPE, and softmax attention with RoPE\. We trained all of them with context 2048, one seed and mixed precision \([AppendixC](https://arxiv.org/html/2610.22714#A3)\)\. We tested two hypotheses of FPA against FoX, each at level0\.05/70\.05/7\. The first asked whether the test loss of FPA is worse by no more thanln⁡1\.01\\ln 1\.01, that is 1% in perplexity\. The second asked whether FPA has a lower loss beyond the training length on PG\-19\([Rae et al\., 2020](https://arxiv.org/html/2610.22714#bib.bib65)\)or retrieves more passkeys placed beyond it\([Mohtashami and Jaggi, 2023](https://arxiv.org/html/2610.22714#bib.bib57)\)\.

Table 2:Language models with 110M parameters, one seed each\.Losses are in nats per token on the SlimPajama test set, on WikiText\-103\([Merity et al\., 2017](https://arxiv.org/html/2610.22714#bib.bib66)\)and on PG\-19 positions 2048 to 4095 in windows of 4096 tokens\. Passkey accuracy averages 50 items at each of two lengths, and RULER averages 13 tasks at length 8192\. The models were trained with context 2048\. Bold marks the best value in each column\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\.#### Perplexity and extrapolation\.

Both tests supported FPA \([Table2](https://arxiv.org/html/2610.22714#S4.T2)\)\. On the SlimPajama test set the loss of FPA was 0\.0192 nats below that of FoX, and the upper confidence bound of the difference,−0\.0186\-0\.0186, lay inside the margin of0\.009950\.00995\. On 99 PG\-19 test books its loss at positions 2048 to 4095 was 0\.034 nats lower, with upper bound−0\.028\-0\.028\. It retrieved all 100 passkeys at lengths 3072 and 4096, against 73 for FoX \(p=7\.5×10−9p=7\.5\\times 10^\{\-9\}\)\.

#### Longer contexts and other evaluations\.

In windows of 16,384 tokens FPA and FoX kept a flat loss far beyond the training length, while Selective Attention and softmax attention with RoPE did not \([Figure2](https://arxiv.org/html/2610.22714#S4.F2)\)\. FPA was 0\.02 to 0\.03 nats below FoX up to position 8192 but0\.0260\.026nats above it from 8192 to 16,384 \(95% interval\[0\.019,0\.032\]\[0\.019,0\.032\]\)\. FPA retrieved every passkey at lengths 8192 and 16,384, where FoX retrieved 20% \([Figure3](https://arxiv.org/html/2610.22714#S4.F3)\)\. On RULER\([Hsieh et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib60)\)FPA scored 0\.202 at length 8192 against 0\.117 for FoX, but slightly below FoX at 4096 and 16,384, and no model reached 0\.09 on BABILong\([Kuratov et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib59)\)\. Zero\-shot accuracies on six downstream tasks were close to those of FoX, and most 95% intervals of the differences contained zero \([AppendixC](https://arxiv.org/html/2610.22714#A3)\)\.

Figure 2:Loss far beyond the training length\.Mean loss of the four language models on 94 PG\-19 test books read in windows of 16,384 tokens, in bins of 256 positions\. The models were trained with context 2048 \(vertical line\)\. The vertical axis is logarithmic in the loss minus 3\.1 nats, which spreads out the lowest losses\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\.Figure 3:Passkey accuracy by length of the prompt\.Each point averages 50 items, ten passkeys at each of five depths\. Lengths up to 4096 come from the preregistered evaluation and the two longer ones from the descriptive one\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\.
#### What the trained model does\.

In an observational analysis of the FPA model on SlimPajama test windows, most heads left few keys alive \([SectionC\.6](https://arxiv.org/html/2610.22714#A3.SS6)\)\. At queries beyond position 1024 the median head left 0\.3% of the keys with a bias of at least−1\-1\. In 19 of the 144 heads more than 10% of the alive sets were not suffixes, which no forget gate can produce\. The share of deaths at the document boundaries⟨s⟩\\langle\\mathrm\{s\}\\rangleand⟨/s⟩\\langle/\\mathrm\{s\}\\ranglewas 6\.6 times their share of the tokens, in the median head\. In 56 heads the walk moved in opposite directions at opening and closing brackets and its correlation with bracket depth lay outside a familywise 99% band of shifted controls \([Figure4](https://arxiv.org/html/2610.22714#S4.F4)\)\. The correlations were small \(largest0\.250\.25\), so we read them as a description, not as evidence that the model tracks brackets\.

Figure 4:Steps of the walk at brackets in the FPA language model\.\(a\) Incrementsδt\\delta\_\{t\}of layer 1, head 5 at positions 447 to 846 of one test window, with the bracket depth shaded and the mean increments where the depth rises and falls in the whole window\. A fixed seed chose the window before the analysis, and the head contrasts the two kinds of bracket most in it\. \(b\) Mean increments at opening and at closing brackets of all 144 heads over 256 test windows\. Filled markers show the 56 heads with increments of opposite signs and a familywise significant correlation with the bracket depth\. FPA, First Passage Attention\.

### 4\.3Cost

Table 3:Cost on one 12 GB partition of a Turing GPU in half precision\.One attention layer has 12 heads of dimension 64 at batch 4 and length 2048 \(medians of 20 rounds\)\. Model throughput is in training tokens per second of the 110M models in the benchmark\. Decoding uses batch size 1 at length 8192, and bytes per position count the keys, values and per\-key state of 12 layers in single precision\. The lower rows switch off parts of the FPA kernel\. SDPA, the scaled dot\-product attention of PyTorch, with its memory\-efficient kernel on this GPU\. FPA, First Passage Attention\. FoX, Forgetting Transformer\.We measured the cost of the kernels and models \([Table3](https://arxiv.org/html/2610.22714#S4.T3),[AppendixE](https://arxiv.org/html/2610.22714#A5)\)\. For the forward and backward pass, one FPA layer took 0\.97 times as long as SDPA and 1\.50 times as long as FoX, whose bias needs no range minimum\. On this GPU SDPA runs its memory\-efficient kernel\. Over five shapes from16×51216\\times 512to1×81921\\times 8192these ratios ranged from 0\.95 to 1\.08 and from 1\.42 to 1\.56\. Selective Attention took 2\.4 times as long as FPA, and 2\.0 to 2\.5 times over the five shapes\. The forward pass of FPA alone took 1\.03 to 1\.07 times as long as that of FoX\. Within one kernel, the range minimum added 14% to the time of the bias of FoX and the gradient of the field another 26%\. In the benchmark of[Table3](https://arxiv.org/html/2610.22714#S4.T3), the whole FPA model trained at 0\.914 times the throughput of FoX, 1\.103 times that of softmax attention and 1\.47 times that of Selective Attention\. At batch size 1 and length 8192, decoding with FPA took 22\.0 ms per token, against 20\.2 ms for FoX and 23\.9 ms for softmax attention\. These times did not grow from 1024 to 16,384 tokens, so fixed overheads dominate them at this size\. The state of FPA enlarged the cache by 1\.56% over keys and values\.

The bias of a key never rises again \([Proposition2\.3](https://arxiv.org/html/2610.22714#S2.Thmtheorem3)\), so a decoder can drop a key once its bias falls below a threshold\. When we dropped every key whose bias fell below−10\-10, the loss of FPA rose by 0\.00044 nats at length 2048 and by 0\.00047 at 8192, while the model kept 34% and 26% of the keys\. With between 24% and 27% of its cache the model still retrieved every passkey at 8192 and 16,384\. The same rule cost FoX 0\.0195 to 0\.0227 nats while it kept 15% and 7% of the keys, and a sliding window of the same mean size cost softmax attention 0\.115 nats at 2048\.

## 5Related Work

#### Path\-dependent biases\.

FoX adds a sum of log forget gates\([Lin et al\., 2025a](https://arxiv.org/html/2610.22714#bib.bib4)\), and it is the stack form of FPA with a walk that never rises\. Its bias falls with the age of a key, so its visible sets are suffixes\. Stick\-breaking attention\([Tan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib5)\), the geometric attention of the Neural Data Router\([Csordás et al\., 2022](https://arxiv.org/html/2610.22714#bib.bib24)\), contextual position encoding\([Golovneva et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib25)\), PaTH\([Yang et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib26)\)and GRAPE\([Zhang et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib12)\)change logits through products, sums or transformations along the path\. GRAPE contains FoX and ALiBi as special cases\. Selective Attention\([Leviathan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib6)\)and DCP\([Anagnostidis et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib7)\)let later tokens remove a key, and in the hard limit they realise the same alive sets as FPA\. Their bias accumulates a score for every pair of a later token and a key, whereas the bias of FPA depends only on scalars of single positions and costs less to compute than that of Selective Attention \([Section4\.3](https://arxiv.org/html/2610.22714#S4.SS3)\)\. The suppression of Selective Attention also adds up over the path, so it depends on the duration of a dip \([Proposition3\.4](https://arxiv.org/html/2610.22714#S3.Thmtheorem4)\), and in both methods one mask serves all heads of a layer \([Proposition3\.6](https://arxiv.org/html/2610.22714#S3.Thmtheorem6)\)\. The concurrent Universal Attention also accumulates a pairwise sum along the path and evicts keys whose bias passes a threshold\([Wertheimer et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib27)\)\.

#### Range extremes and stacks\.

StructFormer compares a maximum over a range with a level through a sigmoid, the smooth form of the same comparison\([Shen et al\., 2021](https://arxiv.org/html/2610.22714#bib.bib28)\)\. Its level belongs to the token that attends, however, so a fixed token sees a contiguous span, and the comparison feeds a parser that the whole layer shares in a masked language model\. PRPN\([Shen et al\., 2018](https://arxiv.org/html/2610.22714#bib.bib29)\)and syntax\-guided local attention\([Hou et al\., 2022](https://arxiv.org/html/2610.22714#bib.bib30)\)also gate by a range extreme against a threshold of the query, and our variant of FPA with the level of the query learned only suffixes \([AppendixB](https://arxiv.org/html/2610.22714#A2)\)\. The strengths of the Neural Stack have the first\-passage form as a closed form, in an external memory of a recurrent network that reads only its top\([Grefenstette et al\., 2015](https://arxiv.org/html/2610.22714#bib.bib10)\)\. Ordered Neurons\([Shen et al\., 2019b](https://arxiv.org/html/2610.22714#bib.bib31)\), Ordered Memory\([Shen et al\., 2019a](https://arxiv.org/html/2610.22714#bib.bib32)\), Stack Attention\([DuSell and Chiang, 2024](https://arxiv.org/html/2610.22714#bib.bib33);[Li et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib34)\), Pushdown Layers\([Murty et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib35)\), Transformer Grammars\([Sartran et al\., 2022](https://arxiv.org/html/2610.22714#bib.bib36)\)and DeltaStack\([Nguyen et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib37)\)build stacks or syntax into recurrent or attention models, several with supervision of the structure\. FPA learns its walk without such supervision\. Expire\-Span\([Sukhbaatar et al\., 2021](https://arxiv.org/html/2610.22714#bib.bib11)\)and adaptive attention spans\([Sukhbaatar et al\., 2019](https://arxiv.org/html/2610.22714#bib.bib38)\)learn when keys expire, which FPA contains as the case of a clock as field\. Preisach Attention studies extremum stacks as a sequence memory, without a learned level per key or scores between queries and keys\([Frydrych, 2026](https://arxiv.org/html/2610.22714#bib.bib39)\)\. Tropical Attention takes max\-plus extremes over keys rather than over the path between key and query\([Hashemi et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib40)\)\.

#### Expressivity\.

Lower bounds on head dimension, rank or precision\([Bhojanapalli et al\., 2020](https://arxiv.org/html/2610.22714#bib.bib17);[Sanford et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib18);[Amsel et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib41);[Kozachinskiy et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib42);[Weller et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib19)\)rest on rank, Vapnik–Chervonenkis \(VC\) dimension or sign\-rank arguments of the kind that[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)uses, and our contribution is the family of alive sets that later dips create\. One layer needs linear size for bounded Dyck languages\([Bhattamishra et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib43)\), while a few layers suffice\([Yao et al\., 2021](https://arxiv.org/html/2610.22714#bib.bib21);[Hayakawa and Sato, 2025](https://arxiv.org/html/2610.22714#bib.bib22)\), which is why we state the separation for one layer\. Soft attention simulates hard attention when its temperature scales with the margin\([Yang et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib44)\), as[Proposition3\.3](https://arxiv.org/html/2610.22714#S3.Thmtheorem3)does with its strength\. Non\-negative gates limit state tracking in linear recurrences\([Sarrof et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib45);[Grazzi et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib46)\), and the walk of FPA may rise as well as fall\.

#### Eviction\.

H2O\([Zhang et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib58)\)and attention sinks\([Xiao et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib61)\)drop cached keys by heuristics, and adaptive computation pruning skips the blocks that the bias of FoX makes negligible\([Lin et al\., 2025b](https://arxiv.org/html/2610.22714#bib.bib47)\)\. The bias of an FPA key never rises again, so a decoder can drop a key once its bias falls below a threshold, and in the hard limit it drops exactly the dead keys\.

## 6Limitations and Conclusion

#### Limitations\.

Our language models had 110M parameters and one seed each, and they trained on 2\.7B tokens on one 12 GB partition of a Turing GPU, so the comparison may change at larger scale\.

#### Conclusion\.

We have introduced First Passage Attention, which lowers the logit of a key by the deepest later dip of a learned field below the level of the key\. One parameterisation contains the Forgetting Transformer, a stack, a bottleneck bias and learned expiry\. In one layer a single FPA head realises alive sets for which positional heads and forget\-gate heads with token\-level gates needr−2r\-2dimensions\. Without positional information, no head that subtracts a sum of non\-negative scores of token pairs fits exactly the targets of dips whose durations vary, while one FPA head does\. Preregistered probes agreed with these predictions\. A 110M\-parameter FPA language model was not worse than FoX in perplexity, had a lower loss on PG\-19 at positions 2048 to 4095 and retrieved every passkey at lengths up to 16,384\.

#### Use of large language models\.

We used large language models to assist with code, literature search, proof checking and editing, and we take full responsibility for the content of the paper\.

## References

- N\. Amsel, G\. Yehudai, and J\. BrunaQuality over quantity in attention layers: when adding more heads hurts\.InInternational Conference on Learning Representations,pp\. 62431–62483\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Anagnostidiset al\.\(2023\)S\. Anagnostidis, D\. Pavllo, L\. Biggio, L\. Noci, A\. Lucchi, and T\. HofmannDynamic context pruning for efficient and interpretable autoregressive transformers\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 65202–65223\.External Links:[Document](https://dx.doi.org/10.52202/075280-2845)Cited by:[§A\.6](https://arxiv.org/html/2610.22714#A1.SS6.p5.1),[§1](https://arxiv.org/html/2610.22714#S1.p2.1),[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px2.p3.1),[§3\.3](https://arxiv.org/html/2610.22714#S3.SS3.p1.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Aroraet al\.\(2024\)S\. Arora, S\. Eyuboglu, A\. Timalsina, I\. Johnson, M\. Poli, J\. Y\. Zou, A\. Rudra, and C\. RéZoology: measuring and improving recall in efficient language models\.InInternational Conference on Learning Representations,pp\. 15664–15730\.Cited by:[§B\.7](https://arxiv.org/html/2610.22714#A2.SS7.p1.1)\.
- Bender and Farach\-Colton \(2000\)M\. A\. Bender and M\. Farach\-ColtonThe LCA problem revisited\.InLATIN 2000: Theoretical Informatics,Lecture Notes in Computer Science,pp\. 88–94\.External Links:[Document](https://dx.doi.org/10.1007/10719839%5F9)Cited by:[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px3.p2.1)\.
- Bhattamishraet al\.\(2024\)S\. Bhattamishra, M\. Hahn, P\. Blunsom, and V\. KanadeSeparations in the representational capabilities of transformers and recurrent architectures\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 36002–36045\.External Links:[Document](https://dx.doi.org/10.52202/079017-1135)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Bhojanapalliet al\.\(2020\)S\. Bhojanapalli, C\. Yun, A\. S\. Rawat, S\. Reddi, and S\. KumarLow\-rank bottleneck in multi\-head attention models\.InProceedings of the 37th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.119,pp\. 864–873\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Bisket al\.\(2020\)Y\. Bisk, R\. Zellers, R\. Le Bras, J\. Gao, and Y\. ChoiPIQA: reasoning about physical commonsense in natural language\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,pp\. 7432–7439\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v34i05.6239)Cited by:[§C\.4](https://arxiv.org/html/2610.22714#A3.SS4.p1.1)\.
- Clarket al\.\(2018\)P\. Clark, I\. Cowhey, O\. Etzioni, T\. Khot, A\. Sabharwal, C\. Schoenick, and O\. TafjordThink you have solved question answering? Try ARC, the AI2 reasoning challenge\.arXiv preprint arXiv:1803\.05457\.Cited by:[§C\.4](https://arxiv.org/html/2610.22714#A3.SS4.p1.1)\.
- Cover \(1965\)T\. M\. CoverGeometrical and statistical properties of systems of linear inequalities with applications in pattern recognition\.IEEE Transactions on Electronic ComputersEC\-14\(3\),pp\. 326–334\.External Links:[Document](https://dx.doi.org/10.1109/PGEC.1965.264137)Cited by:[§A\.5](https://arxiv.org/html/2610.22714#A1.SS5.p4.1),[§3\.1](https://arxiv.org/html/2610.22714#S3.SS1.p3.1)\.
- Csordáset al\.\(2022\)R\. Csordás, K\. Irie, and J\. SchmidhuberThe neural data router: adaptive control flow in transformers improves systematic generalization\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p2.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Dudley \(1978\)R\. M\. DudleyCentral limit theorems for empirical measures\.The Annals of Probability6\(6\),pp\. 899–929\.External Links:[Document](https://dx.doi.org/10.1214/aop/1176995384)Cited by:[§A\.5](https://arxiv.org/html/2610.22714#A1.SS5.p4.1),[§3\.1](https://arxiv.org/html/2610.22714#S3.SS1.p3.1)\.
- DuSell and Chiang \(2024\)B\. DuSell and D\. ChiangStack attention: improving the ability of transformers to model hierarchical patterns\.InInternational Conference on Learning Representations,pp\. 7411–7430\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Frydrych \(2026\)P\. FrydrychPreisach attention: a hysteretic model of sequential memory\.arXiv preprint arXiv:2605\.23603\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Gaoet al\.\(2024\)L\. Gao, J\. Tow, B\. Abbasi, S\. Biderman, S\. Black, A\. DiPofi, C\. Foster, L\. Golding, J\. Hsu, A\. Le Noac’h, H\. Li, K\. McDonell, N\. Muennighoff, C\. Ociepa, J\. Phang, L\. Reynolds, H\. Schoelkopf, A\. Skowron, L\. Sutawika, E\. Tang, A\. Thite, B\. Wang, K\. Wang, and A\. ZouA framework for few\-shot language model evaluation\.Note:Zenodo, version v0\.4\.3External Links:[Document](https://dx.doi.org/10.5281/zenodo.12608602)Cited by:[Table 10](https://arxiv.org/html/2610.22714#A3.T10)\.
- Golovnevaet al\.\(2024\)O\. Golovneva, T\. Wang, J\. Weston, and S\. SukhbaatarContextual position encoding: learning to count what’s important\.arXiv preprint arXiv:2405\.18719\.Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p2.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Grazziet al\.\(2025\)R\. Grazzi, J\. Siems, A\. Zela, J\. Franke, F\. Hutter, and M\. PontilUnlocking state\-tracking in linear RNNs through negative eigenvalues\.InInternational Conference on Learning Representations,pp\. 36565–36597\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Grefenstetteet al\.\(2015\)E\. Grefenstette, K\. M\. Hermann, M\. Suleyman, and P\. BlunsomLearning to transduce with unbounded memory\.InAdvances in Neural Information Processing Systems,Vol\.28\.Cited by:[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Hashemiet al\.\(2025\)B\. Hashemi, K\. Pasque, C\. Teska, and R\. YoshidaTropical attention: neural algorithmic reasoning for combinatorial algorithms\.InAdvances in Neural Information Processing Systems,Vol\.38,pp\. 98631–98656\.External Links:[Document](https://dx.doi.org/10.52202/085713-3295)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Hayakawa and Sato \(2025\)D\. Hayakawa and I\. SatoTheoretical analysis of hierarchical language recognition and generation by transformers without positional encoding\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 30777–30834\.External Links:[Document](https://dx.doi.org/10.18653/v1/2025.acl-long.1488)Cited by:[§3\.1](https://arxiv.org/html/2610.22714#S3.SS1.p4.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Houet al\.\(2022\)S\. Hou, J\. Kai, H\. Xue, B\. Zhu, B\. Yuan, L\. Huang, X\. Wang, and Z\. LinSyntax\-guided localized self\-attention by constituency syntactic distance\.InFindings of the Association for Computational Linguistics: EMNLP 2022,pp\. 2334–2341\.External Links:[Document](https://dx.doi.org/10.18653/v1/2022.findings-emnlp.173)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Hsiehet al\.\(2024\)C\. Hsieh, S\. Sun, S\. Kriman, S\. Acharya, D\. Rekesh, F\. Jia, and B\. GinsburgRULER: what’s the real context size of your long\-context language models?\.InFirst Conference on Language Modeling,Cited by:[§4\.2](https://arxiv.org/html/2610.22714#S4.SS2.SSS0.Px2.p1.1)\.
- Jianget al\.\(2023\)A\. Q\. Jiang, A\. Sablayrolles, A\. Mensch, C\. Bamford, D\. S\. Chaplot, D\. de las Casas, F\. Bressand, G\. Lengyel, G\. Lample, L\. Saulnier, L\. R\. Lavaud, M\. Lachaux, P\. Stock, T\. Le Scao, T\. Lavril, T\. Wang, T\. Lacroix, and W\. El SayedMistral 7B\.arXiv preprint arXiv:2310\.06825\.Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p1.1),[§4\.2](https://arxiv.org/html/2610.22714#S4.SS2.p1.1)\.
- Kajitsuka and Sato \(2024\)T\. Kajitsuka and I\. SatoAre transformers with one layer self\-attention using low\-rank weight matrices universal approximators?\.InInternational Conference on Learning Representations,pp\. 35177–35205\.Cited by:[§3\.1](https://arxiv.org/html/2610.22714#S3.SS1.p4.1)\.
- Kozachinskiyet al\.\(2025\)A\. Kozachinskiy, F\. Urrutia, H\. Orellana, T\. Steifer, G\. Pizarro, M\. Fuentes, F\. Meza Vásquez, C\. Buc Calderon, and C\. RojasStrassen attention, split VC dimension and compositionality in transformers\.InAdvances in Neural Information Processing Systems,Vol\.38,pp\. 9665–9696\.External Links:[Document](https://dx.doi.org/10.52202/085713-0327)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Kuratovet al\.\(2024\)Y\. Kuratov, A\. Bulatov, P\. Anokhin, I\. Rodkin, D\. Sorokin, A\. Sorokin, and M\. BurtsevBABILong: testing the limits of LLMs with long context reasoning\-in\-a\-haystack\.InAdvances in Neural Information Processing Systems, Datasets and Benchmarks Track,Vol\.37,pp\. 106519–106554\.External Links:[Document](https://dx.doi.org/10.52202/079017-3381)Cited by:[§4\.2](https://arxiv.org/html/2610.22714#S4.SS2.SSS0.Px2.p1.1)\.
- Leviathanet al\.\(2025\)Y\. Leviathan, M\. Kalman, and Y\. MatiasSelective attention improves transformer\.InInternational Conference on Learning Representations,pp\. 4389–4414\.Cited by:[§A\.6](https://arxiv.org/html/2610.22714#A1.SS6.p5.1),[§A\.8](https://arxiv.org/html/2610.22714#A1.SS8.p1.1),[§1](https://arxiv.org/html/2610.22714#S1.p2.1),[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px2.p3.1),[§3\.2](https://arxiv.org/html/2610.22714#S3.SS2.p1.1),[§3\.3](https://arxiv.org/html/2610.22714#S3.SS3.p1.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Liet al\.\(2024\)J\. Li, J\. White, M\. Sachan, and R\. CotterellA transformer with stack attention\.InFindings of the Association for Computational Linguistics: NAACL 2024,pp\. 4318–4335\.External Links:[Document](https://dx.doi.org/10.18653/v1/2024.findings-naacl.269)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Linet al\.\(2025a\)Z\. Lin, E\. Nikishin, X\. He, and A\. CourvilleForgetting transformer: softmax attention with a forget gate\.InInternational Conference on Learning Representations,pp\. 69704–69738\.Cited by:[§C\.1](https://arxiv.org/html/2610.22714#A3.SS1.p1.1),[§1](https://arxiv.org/html/2610.22714#S1.p2.1),[§4\.2](https://arxiv.org/html/2610.22714#S4.SS2.p1.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Linet al\.\(2025b\)Z\. Lin, J\. Obando\-Ceron, X\. O\. He, and A\. CourvilleAdaptive computation pruning for the forgetting transformer\.InSecond Conference on Language Modeling,Cited by:[Table 23](https://arxiv.org/html/2610.22714#A5.T23),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px4.p1.1)\.
- Lindley \(1952\)D\. V\. LindleyThe theory of queues with a single server\.Mathematical Proceedings of the Cambridge Philosophical Society48\(2\),pp\. 277–289\.External Links:[Document](https://dx.doi.org/10.1017/S0305004100027638)Cited by:[§A\.2](https://arxiv.org/html/2610.22714#A1.SS2.p1.1),[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px2.p2.1)\.
- Liuet al\.\(2023\)B\. Liu, J\. Ash, S\. Goel, A\. Krishnamurthy, and C\. ZhangExposing attention glitches with flip\-flop language modeling\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 25549–25583\.External Links:[Document](https://dx.doi.org/10.52202/075280-1112)Cited by:[§B\.7](https://arxiv.org/html/2610.22714#A2.SS7.p1.1)\.
- Merityet al\.\(2017\)S\. Merity, C\. Xiong, J\. Bradbury, and R\. SocherPointer sentinel mixture models\.InInternational Conference on Learning Representations,Cited by:[§C\.2](https://arxiv.org/html/2610.22714#A3.SS2.p1.1),[Table 2](https://arxiv.org/html/2610.22714#S4.T2)\.
- Mohtashami and Jaggi \(2023\)A\. Mohtashami and M\. JaggiRandom\-access infinite context length for transformers\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 54567–54585\.External Links:[Document](https://dx.doi.org/10.52202/075280-2378)Cited by:[§C\.2](https://arxiv.org/html/2610.22714#A3.SS2.p1.1),[§4\.2](https://arxiv.org/html/2610.22714#S4.SS2.p1.1)\.
- Murtyet al\.\(2023\)S\. Murty, P\. Sharma, J\. Andreas, and C\. D\. ManningPushdown layers: encoding recursive structure in transformer language models\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,pp\. 3233–3247\.External Links:[Document](https://dx.doi.org/10.18653/v1/2023.emnlp-main.195)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Nguyenet al\.\(2026\)A\. T\. Nguyen, S\. Momeni, A\. Chaubey, C\. Xiao, and B\. LiuPush, pop, parallelize: stack\-augmented linear attention via the delta rule\.InProceedings of the 43rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.306,pp\. 92579–92592\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Papernoet al\.\(2016\)D\. Paperno, G\. Kruszewski, A\. Lazaridou, N\. Q\. Pham, R\. Bernardi, S\. Pezzelle, M\. Baroni, G\. Boleda, and R\. FernándezThe LAMBADA dataset: word prediction requiring a broad discourse context\.InProceedings of the 54th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 1525–1534\.External Links:[Document](https://dx.doi.org/10.18653/v1/P16-1144)Cited by:[§C\.4](https://arxiv.org/html/2610.22714#A3.SS4.p1.1)\.
- Presset al\.\(2022\)O\. Press, N\. Smith, and M\. LewisTrain short, test long: attention with linear biases enables input length extrapolation\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p1.1)\.
- Raeet al\.\(2020\)J\. W\. Rae, A\. Potapenko, S\. M\. Jayakumar, C\. Hillier, and T\. P\. LillicrapCompressive transformers for long\-range sequence modelling\.InInternational Conference on Learning Representations,Cited by:[§4\.2](https://arxiv.org/html/2610.22714#S4.SS2.p1.1)\.
- Sakaguchiet al\.\(2020\)K\. Sakaguchi, R\. Le Bras, C\. Bhagavatula, and Y\. ChoiWinoGrande: an adversarial Winograd schema challenge at scale\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,pp\. 8732–8740\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v34i05.6399)Cited by:[§C\.4](https://arxiv.org/html/2610.22714#A3.SS4.p1.1)\.
- Sanfordet al\.\(2023\)C\. Sanford, D\. J\. Hsu, and M\. TelgarskyRepresentational strengths and limitations of transformers\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 36677–36707\.External Links:[Document](https://dx.doi.org/10.52202/075280-1596)Cited by:[§3\.1](https://arxiv.org/html/2610.22714#S3.SS1.p3.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Sarrofet al\.\(2024\)Y\. Sarrof, Y\. Veitsman, and M\. HahnThe expressive capacity of state space models: a formal language perspective\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 41202–41241\.External Links:[Document](https://dx.doi.org/10.52202/079017-1304)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Sartranet al\.\(2022\)L\. Sartran, S\. Barrett, A\. Kuncoro, M\. Stanojević, P\. Blunsom, and C\. DyerTransformer grammars: augmenting transformer language models with syntactic inductive biases at scale\.Transactions of the Association for Computational Linguistics10,pp\. 1423–1439\.External Links:[Document](https://dx.doi.org/10.1162/tacl%5Fa%5F00526)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Sauer \(1972\)N\. SauerOn the density of families of sets\.Journal of Combinatorial Theory, Series A13\(1\),pp\. 145–147\.External Links:[Document](https://dx.doi.org/10.1016/0097-3165%2872%2990019-2)Cited by:[§A\.10](https://arxiv.org/html/2610.22714#A1.SS10.p5.1),[§A\.5](https://arxiv.org/html/2610.22714#A1.SS5.p4.1)\.
- Shelah \(1972\)S\. ShelahA combinatorial problem; stability and order for models and theories in infinitary languages\.Pacific Journal of Mathematics41\(1\),pp\. 247–261\.External Links:[Document](https://dx.doi.org/10.2140/pjm.1972.41.247)Cited by:[§A\.10](https://arxiv.org/html/2610.22714#A1.SS10.p5.1),[§A\.5](https://arxiv.org/html/2610.22714#A1.SS5.p4.1)\.
- Shenet al\.\(2018\)Y\. Shen, Z\. Lin, C\. Huang, and A\. CourvilleNeural language modeling by jointly learning syntax and lexicon\.InInternational Conference on Learning Representations,Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Shenet al\.\(2019a\)Y\. Shen, S\. Tan, A\. Hosseini, Z\. Lin, A\. Sordoni, and A\. CourvilleOrdered memory\.InAdvances in Neural Information Processing Systems,Vol\.32\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Shenet al\.\(2019b\)Y\. Shen, S\. Tan, A\. Sordoni, and A\. CourvilleOrdered neurons: integrating tree structures into recurrent neural networks\.InInternational Conference on Learning Representations,Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Shenet al\.\(2021\)Y\. Shen, Y\. Tay, C\. Zheng, D\. Bahri, D\. Metzler, and A\. CourvilleStructFormer: joint unsupervised induction of dependency and constituency structure from masked language modeling\.InProceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing \(Volume 1: Long Papers\),pp\. 7196–7209\.External Links:[Document](https://dx.doi.org/10.18653/v1/2021.acl-long.559)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Skorokhod \(1961\)A\. V\. SkorokhodStochastic equations for diffusion processes in a bounded region\.Theory of Probability and Its Applications6\(3\),pp\. 264–274\.External Links:[Document](https://dx.doi.org/10.1137/1106035)Cited by:[§A\.2](https://arxiv.org/html/2610.22714#A1.SS2.p1.1),[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px2.p2.1)\.
- Sobolevaet al\.\(2023\)D\. Soboleva, F\. Al\-Khateeb, R\. Myers, J\. R\. Steeves, J\. Hestness, and N\. DeySlimPajama: a 627B token cleaned and deduplicated version of RedPajama\.Note:Cerebras blogCited by:[§C\.1](https://arxiv.org/html/2610.22714#A3.SS1.p2.1),[§4\.2](https://arxiv.org/html/2610.22714#S4.SS2.p1.1)\.
- Songet al\.\(2026\)Z\. Song, P\. Sun, H\. Yuan, and Q\. GuCausal attention with lookahead keys\.InProceedings of the 43rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.306,pp\. 115068–115107\.Cited by:[§A\.6](https://arxiv.org/html/2610.22714#A1.SS6.p5.1),[§3\.1](https://arxiv.org/html/2610.22714#S3.SS1.p4.1)\.
- Suet al\.\(2024\)J\. Su, M\. Ahmed, Y\. Lu, S\. Pan, W\. Bo, and Y\. LiuRoFormer: enhanced transformer with rotary position embedding\.Neurocomputing568,pp\. 127063\.External Links:[Document](https://dx.doi.org/10.1016/j.neucom.2023.127063)Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p1.1)\.
- Sukhbaataret al\.\(2019\)S\. Sukhbaatar, É\. Grave, P\. Bojanowski, and A\. JoulinAdaptive attention span in transformers\.InProceedings of the 57th Annual Meeting of the Association for Computational Linguistics,pp\. 331–335\.External Links:[Document](https://dx.doi.org/10.18653/v1/P19-1032)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Sukhbaataret al\.\(2021\)S\. Sukhbaatar, D\. Ju, S\. Poff, S\. Roller, A\. Szlam, J\. Weston, and A\. FanNot all memories are created equal: learning to forget by expiring\.InProceedings of the 38th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.139,pp\. 9902–9912\.Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p3.1),[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px2.p1.1)\.
- Tanet al\.\(2025\)S\. Tan, S\. Yang, A\. Courville, R\. Panda, and Y\. ShenScaling stick\-breaking attention: an efficient implementation and in\-depth study\.InInternational Conference on Learning Representations,pp\. 4030–4046\.Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p2.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Vaswaniet al\.\(2017\)A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, Ł\. Kaiser, and I\. PolosukhinAttention is all you need\.InAdvances in Neural Information Processing Systems,Vol\.30\.Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p1.1)\.
- Wanget al\.\(2025\)G\. Wang, J\. Zeng, X\. Xiao, S\. Wu, J\. Yang, L\. Zheng, Z\. Chen, J\. Bian, D\. Yu, and H\. WangFlashMask: efficient and rich mask extension of FlashAttention\.InInternational Conference on Learning Representations,pp\. 27641–27661\.Cited by:[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px3.p2.1)\.
- Welleret al\.\(2026\)O\. Weller, M\. Boratko, I\. Naim, and J\. LeeOn the theoretical limitations of embedding\-based retrieval\.InInternational Conference on Learning Representations,pp\. 11202–11216\.Cited by:[§3\.1](https://arxiv.org/html/2610.22714#S3.SS1.p3.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Wertheimeret al\.\(2026\)D\. Wertheimer, H\. Shen, A\. Gupta, D\. Liu, Y\. C\. F\. Lim, M\. Srivatsa, R\. K\. Ganti, M\. Zhang, and N\. WangA self\-pruning transformer: extreme KV\-cache compression with universal attention\.arXiv preprint arXiv:2610\.09051\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Xiaoet al\.\(2024\)G\. Xiao, Y\. Tian, B\. Chen, S\. Han, and M\. LewisEfficient streaming language models with attention sinks\.InInternational Conference on Learning Representations,pp\. 21875–21895\.Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px4.p1.1)\.
- Yanget al\.\(2026\)A\. Yang, L\. Strobl, D\. Chiang, and D\. AngluinSimulating hard attention using soft attention\.Transactions of the Association for Computational Linguistics14,pp\. 147–166\.External Links:[Document](https://dx.doi.org/10.1162/tacl.a.597)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Yanget al\.\(2025\)S\. Yang, Y\. Shen, K\. Wen, S\. Tan, M\. Mishra, L\. Ren, R\. Panda, and Y\. KimPaTH attention: position encoding via accumulating Householder transformations\.InAdvances in Neural Information Processing Systems,Vol\.38,pp\. 62220–62247\.External Links:[Document](https://dx.doi.org/10.52202/085713-2080)Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p2.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Yaoet al\.\(2021\)S\. Yao, B\. Peng, C\. Papadimitriou, and K\. NarasimhanSelf\-attention networks can process bounded hierarchical languages\.InProceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing \(Volume 1: Long Papers\),pp\. 3770–3785\.External Links:[Document](https://dx.doi.org/10.18653/v1/2021.acl-long.292)Cited by:[§3\.1](https://arxiv.org/html/2610.22714#S3.SS1.p4.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px3.p1.1)\.
- Zellerset al\.\(2019\)R\. Zellers, A\. Holtzman, Y\. Bisk, A\. Farhadi, and Y\. ChoiHellaSwag: can a machine really finish your sentence?\.InProceedings of the 57th Annual Meeting of the Association for Computational Linguistics,pp\. 4791–4800\.External Links:[Document](https://dx.doi.org/10.18653/v1/P19-1472)Cited by:[§C\.4](https://arxiv.org/html/2610.22714#A3.SS4.p1.1)\.
- Zhanget al\.\(2026\)Y\. Zhang, Z\. Chen, Y\. Liu, Z\. Qin, H\. Yuan, K\. Xu, Y\. Yuan, Q\. Gu, and A\. C\. YaoGroup representational position encoding\.InInternational Conference on Learning Representations,pp\. 56496–56519\.Cited by:[§1](https://arxiv.org/html/2610.22714#S1.p2.1),[§2](https://arxiv.org/html/2610.22714#S2.SS0.SSS0.Px2.p2.1),[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px1.p1.1)\.
- Zhanget al\.\(2023\)Z\. Zhang, Y\. Sheng, T\. Zhou, T\. Chen, L\. Zheng, R\. Cai, Z\. Song, Y\. Tian, C\. Ré, C\. Barrett, Z\. Wang, and B\. ChenH2O: heavy\-hitter oracle for efficient generative inference of large language models\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 34661–34710\.External Links:[Document](https://dx.doi.org/10.52202/075280-1506)Cited by:[§5](https://arxiv.org/html/2610.22714#S5.SS0.SSS0.Px4.p1.1)\.

## Appendix AProofs

Throughout, a head gives keyssat queryttthe weightwt​s=eℓt​s/∑u≤teℓt​uw\_\{ts\}=e^\{\\ell\_\{ts\}\}/\\sum\_\{u\\leq t\}e^\{\\ell\_\{tu\}\}, so weight ratios depend only on logit differences,wt​s/wt​s′=eℓt​s−ℓt​s′w\_\{ts\}/w\_\{ts^\{\\prime\}\}=e^\{\\ell\_\{ts\}\-\\ell\_\{ts^\{\\prime\}\}\}\. All logits are finite unless a statement says otherwise, and all arithmetic is exact\. The fieldϕu\\phi\_\{u\}and the levelψs\\psi\_\{s\}do not change once their positions are written\.

### A\.1The ladder family

Fixr≥3r\\geq 3\. The tokens are⟨s⟩\\langle\\mathrm\{s\}\\rangle, the key tokenK, the tokensDandU, and the query token?, with walk incrementsδ⁡\(⟨s⟩\)=δ⁡\(?\)=0\\delta\(\\langle\\mathrm\{s\}\\rangle\)=\\delta\(\\texttt\{?\}\)=0,δ⁡\(K\)=1\\delta\(\\texttt\{K\}\)=1,δ⁡\(D\)=−12\\delta\(\\texttt\{D\}\)=\-\\tfrac\{1\}\{2\}andδ⁡\(U\)=12\\delta\(\\texttt\{U\}\)=\\tfrac\{1\}\{2\}\. For a patternP=\(P1,…,Pr−1\)∈\{0,1\}r−1P=\(P\_\{1\},\\dots,P\_\{r\-1\}\)\\in\\\{0,1\\\}^\{r\-1\}the sequencexPx^\{P\}is

⟨s⟩,K,π1,K,π2,…,K,πr−1,K,?,\\langle\\mathrm\{s\}\\rangle,\\ \\texttt\{K\},\\ \\pi\_\{1\},\\ \\texttt\{K\},\\ \\pi\_\{2\},\\ \\dots,\\ \\texttt\{K\},\\ \\pi\_\{r\-1\},\\ \\texttt\{K\},\\ \\texttt\{?\},where the blockπi\\pi\_\{i\}isUDifPi=1P\_\{i\}=1andDUifPi=0P\_\{i\}=0\. With positions numbered from 0, every sequence has length3​r3r, keyjjsits atσj=3​j−2\\sigma\_\{j\}=3j\-2and the query att=3​r−1t=3r\-1\. The familyℱr\\mathcal\{F\}\_\{r\}has the following four properties, which we also checked by computation forrrup to 10\.

1. 1\.*Alive sets\.*In the stack form, keyj<rj<ris alive at the final query exactly whenPj=1P\_\{j\}=1, and keyrris always alive\. IndeedWσj=jW\_\{\\sigma\_\{j\}\}=j, and within blockπj\\pi\_\{j\}the walk visitsj\+12j\+\\tfrac\{1\}\{2\}\(patternUD\) orj−12j\-\\tfrac\{1\}\{2\}\(patternDU\) and returns tojj\. Every later block starts at least atj\+1j\+1and dips by at most12\\tfrac\{1\}\{2\}, so the alive key set isAP=\{j<r:Pj=1\}∪\{r\}A^\{P\}=\\\{j<r:P\_\{j\}=1\\\}\\cup\\\{r\\\}\.
2. 2\.*Prefixes\.*The prefix ofxPx^\{P\}up to positionσj\\sigma\_\{j\}depends only onP1,…,Pj−1P\_\{1\},\\dots,P\_\{j\-1\}\.
3. 3\.*Alive positions\.*In the stack form each block with its key holds exactly one position that is dead at the final query, namely keyjjifPj=0P\_\{j\}=0and theUof the block ifPj=1P\_\{j\}=1\. With⟨s⟩\\langle\\mathrm\{s\}\\rangle, keyrrand the query alive, there arer−1r\-1dead positions and2​r\+12r\+1alive ones\.
4. 4\.*Equal multisets\.*The blocksUDandDUare orderings of one multiset\. So for any functionλ\\lambdaof a token,∑s<u≤tλ⁡\(xu\)\\sum\_\{s<u\\leq t\}\\lambda\(x\_\{u\}\)withssa key position andttthe final query takes the same value for every pattern\. In the stack form every dip lies at least12\\tfrac\{1\}\{2\}below the level of every position it kills\.

### A\.2Proof of[Proposition2\.2](https://arxiv.org/html/2610.22714#S2.Thmtheorem2)

\(a\) Withg=h=0g=h=0,min⁡\(0,ϕ¯t​s−ψs\)=min⁡\(0,mins<u≤t⁡\(Wu−Ws\)\)=−max⁡\(0,maxs<u≤t⁡\(Ws−Wu\)\)=−Lt​s\\min\\bigl\(0,\\bar\{\\phi\}\_\{ts\}\-\\psi\_\{s\}\\bigr\)=\\min\\bigl\(0,\\min\_\{s<u\\leq t\}\(W\_\{u\}\-W\_\{s\}\)\\bigr\)=\-\\max\\bigl\(0,\\max\_\{s<u\\leq t\}\(W\_\{s\}\-W\_\{u\}\)\\bigr\)=\-L\_\{ts\}\. A queue that starts empty at timessand receives the net inputδu\\delta\_\{u\}at stepuuhas the contentRs=0R\_\{s\}=0andRu=max⁡\(0,Ru−1\+δu\)R\_\{u\}=\\max\(0,R\_\{u\-1\}\+\\delta\_\{u\}\)\([Lindley, 1952](https://arxiv.org/html/2610.22714#bib.bib8)\)\. Unrolling the recursion givesRt=Wt−mins≤v≤t⁡Wv=\(Wt−Ws\)\+Lt​sR\_\{t\}=W\_\{t\}\-\\min\_\{s\\leq v\\leq t\}W\_\{v\}=\(W\_\{t\}\-W\_\{s\}\)\+L\_\{ts\}, soLt​sL\_\{ts\}is the total amount by which the reflection at zero has pushed the walkW−WsW\-W\_\{s\}up\([Skorokhod, 1961](https://arxiv.org/html/2610.22714#bib.bib9)\)\. The proposition uses this reading only as a name forLt​sL\_\{ts\}\.

\(b\) Ifδ≤0\\delta\\leq 0, the walk does not increase, soϕ¯t​s=Wt≤Ws\\bar\{\\phi\}\_\{ts\}=W\_\{t\}\\leq W\_\{s\}andbt​s=β⁡\(Wt−Ws\)=∑s<u≤tβ​δu=∑s<u≤tlog⁡fub\_\{ts\}=\\beta\(W\_\{t\}\-W\_\{s\}\)=\\sum\_\{s<u\\leq t\}\\beta\\delta\_\{u\}=\\sum\_\{s<u\\leq t\}\\log f\_\{u\}\.

\(c\) HereW=0W=0andψ=0\\psi=0, sobt​s=min⁡\(0,mins<u≤t⁡gu\)=mins<u≤t⁡gub\_\{ts\}=\\min\\bigl\(0,\\min\_\{s<u\\leq t\}g\_\{u\}\\bigr\)=\\min\_\{s<u\\leq t\}g\_\{u\}becauseg≤0g\\leq 0\.

\(d\) The walk isWu=W0−uW\_\{u\}=W\_\{0\}\-u, soϕ=W\\phi=Wandψs=Ws−es\\psi\_\{s\}=W\_\{s\}\-e\_\{s\}\. The minimum of the decreasing walk over\(s,t\]\(s,t\]isWtW\_\{t\}, soϕ¯t​s−ψs=Wt−Ws\+es=es−\(t−s\)\\bar\{\\phi\}\_\{ts\}\-\\psi\_\{s\}=W\_\{t\}\-W\_\{s\}\+e\_\{s\}=e\_\{s\}\-\(t\-s\), which gives the stated bias\. Keyssis alive, for everyβ\\beta, exactly whenes≥t−se\_\{s\}\\geq t\-s\.□\\square

### A\.3Proof of[Proposition2\.3](https://arxiv.org/html/2610.22714#S2.Thmtheorem3)

\(a\) Since\(s,t\]⊂\(s,t′\]\(s,t\]\\subset\(s,t^\{\\prime\}\],ϕ¯t′​s≤ϕ¯t​s\\bar\{\\phi\}\_\{t^\{\\prime\}s\}\\leq\\bar\{\\phi\}\_\{ts\}, andx↦β​min⁡\(0,x−ψs\)x\\mapsto\\beta\\min\(0,x\-\\psi\_\{s\}\)does not decrease\. Sobt′​s≤bt​sb\_\{t^\{\\prime\}s\}\\leq b\_\{ts\}, andbt​s<0b\_\{ts\}<0givesbt′​s<0b\_\{t^\{\\prime\}s\}<0\.

\(b\) Lets<s′s<s^\{\\prime\}both be alive at timett\. Sinces′∈\(s,t\]s^\{\\prime\}\\in\(s,t\],Ws′≥ϕ¯t​s≥WsW\_\{s^\{\\prime\}\}\\geq\\bar\{\\phi\}\_\{ts\}\\geq W\_\{s\}, so the levels of the alive keys do not decrease with the time of writing\. Stepuukills a keys<u−1s<u\-1that is alive atu−1u\-1exactly whenWu<WsW\_\{u\}<W\_\{s\}, and it kills the key written atu−1u\-1under the same condition\. Since the levels of the keys alive atu−1u\-1do not decrease inss, the keys withWs\>WuW\_\{s\}\>W\_\{u\}among them form a suffix in time\. Every key alive atu−1u\-1hasWs≤Wu−1W\_\{s\}\\leq W\_\{u\-1\}, so a step that does not decrease the walk kills nothing\. Every key alive atuuhas a level of at mostWuW\_\{u\}, so the key written atuujoins at the top\. The alive keys therefore evolve as a stack\.□\\square

### A\.4Proof of[Proposition2\.4](https://arxiv.org/html/2610.22714#S2.Thmtheorem4)

\(a\) Lets∈Js\\in Jandt∈It\\in IwithJJbeforeII\. The range\(s,t\]\(s,t\]is the disjoint union of the rest ofJJafterss, the full blocks strictly betweenJJandII, and the part ofIIup tott\. Soϕ¯t​s\\bar\{\\phi\}\_\{ts\}is the minimum of the suffix minimum ofJJafterss, the minimum over the blocks in between, and the prefix minimum ofIIup tott\. Suffix and prefix minima of a block takeO⁡\(B\)O\(B\)operations, and theO⁡\(T/B\)O\(T/B\)block minima takeO⁡\(T\)O\(T\)for the whole sequence\. The minimum over the blocks in between costsO⁡\(1\)O\(1\)per pair of blocks when it runs back alongJJfrom the block beforeII\. The bias of a pair of blocks is then an element\-wise expression in these minima,ψ\\psiandβ\\beta\. On a diagonal block the range lies inside the block, and the running minimumϕ¯t​s=min⁡\(ϕ¯t−1,s,ϕt\)\\bar\{\\phi\}\_\{ts\}=\\min\(\\bar\{\\phi\}\_\{t\-1,s\},\\phi\_\{t\}\)gives all range minima withB⁡\(B−1\)/2B\(B\-1\)/2updates\.

\(b\) Since\(s,t\]=\(s,t−1\]∪\{t\}\(s,t\]=\(s,t\-1\]\\cup\\\{t\\\},ϕ¯t​s=min⁡\(ϕ¯t−1,s,ϕt\)\\bar\{\\phi\}\_\{ts\}=\\min\(\\bar\{\\phi\}\_\{t\-1,s\},\\phi\_\{t\}\), and the bias needs onlyϕ¯t​s\\bar\{\\phi\}\_\{ts\}andψs\\psi\_\{s\}for each cached key\. Sinceϕ¯t​s\\bar\{\\phi\}\_\{ts\}does not increase intt, a key withϕ¯t​s<ψs\\bar\{\\phi\}\_\{ts\}<\\psi\_\{s\}stays dead\.□\\square

### A\.5Proof of[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)

At the final queryt=3​r−1t=3r\-1the token and position of keyjjare the same in every sequence, sokj:=kσjk\_\{j\}:=k\_\{\\sigma\_\{j\}\}andρj:=ρ⁡\(t,σj\)\\rho\_\{j\}:=\\rho\(t,\\sigma\_\{j\}\)do not depend on the pattern\. Fix a patternPPand letq=qPq=q^\{P\}\. All weights at the query share one denominator, so the hypothesis orders the logits of the keys, andmina∈AP⁡ℓσa\>maxx∉AP⁡ℓσx\\min\_\{a\\in A^\{P\}\}\\ell\_\{\\sigma\_\{a\}\}\>\\max\_\{x\\notin A^\{P\}\}\\ell\_\{\\sigma\_\{x\}\}, where the maximum over an empty set is−∞\-\\infty\. Pickθ0\\theta\_\{0\}strictly in between and setθ=θ0−cP\\theta=\\theta\_\{0\}\-c^\{P\}\. The functionf⁡\(j\)=⟨q,kj⟩\+ρj−θf\(j\)=\\langle q,k\_\{j\}\\rangle\+\\rho\_\{j\}\-\\thetais then positive on the alive keys and negative on the dead keys amongj=1,…,r−1j=1,\\dots,r\-1\. So the class𝒞=\{j↦⟨q,kj⟩\+ρj−θ:q∈ℝd,θ∈ℝ\}\\mathcal\{C\}=\\\{j\\mapsto\\langle q,k\_\{j\}\\rangle\+\\rho\_\{j\}\-\\theta:q\\in\\mathbb\{R\}^\{d\},\\theta\\in\\mathbb\{R\}\\\}realises every sign pattern on\{1,…,r−1\}\\\{1,\\dots,r\-1\\\}\.

Suppose thatr−1≥d\+2r\-1\\geq d\+2\. Ther−1r\-1vectors\(kj,1\)∈ℝd\+1\(k\_\{j\},1\)\\in\\mathbb\{R\}^\{d\+1\}are then linearly dependent,∑j<raj​\(kj,1\)=0\\sum\_\{j<r\}a\_\{j\}\(k\_\{j\},1\)=0witha≠0a\\neq 0, and the last coordinate gives∑jaj=0\\sum\_\{j\}a\_\{j\}=0, so bothJ\+=\{j:aj\>0\}J\_\{\+\}=\\\{j:a\_\{j\}\>0\\\}andJ−=\{j:aj<0\}J\_\{\-\}=\\\{j:a\_\{j\}<0\\\}are non\-empty\. Everyf∈𝒞f\\in\\mathcal\{C\}satisfies∑j<raj​f​\(j\)=∑j<raj​ρj=:C\\sum\_\{j<r\}a\_\{j\}f\(j\)=\\sum\_\{j<r\}a\_\{j\}\\rho\_\{j\}=:C, a constant\. IfC≤0C\\leq 0, a function positive exactly onJ\+J\_\{\+\}would make the sum positive, and ifC\>0C\>0, a function positive exactly onJ−J\_\{\-\}would make it negative\. In both cases some pattern of the family is not realised, a contradiction, sor−1≤d\+1r\-1\\leq d\+1\.

For the path term, the range\(σj,t\]\(\\sigma\_\{j\},t\]consists of the blocksπj,…,πr−1\\pi\_\{j\},\\dots,\\pi\_\{r\-1\}, the keysj\+1,…,rj\+1,\\dots,rand the query\. By the fourth property ofℱr\\mathcal\{F\}\_\{r\},Λj=∑σj<u≤tλ⁡\(xu\)\\Lambda\_\{j\}=\\sum\_\{\\sigma\_\{j\}<u\\leq t\}\\lambda\(x\_\{u\}\)is the same for every pattern\. The proof usesρ\\rhoonly through the numbersρj\\rho\_\{j\}, which must not depend on the pattern, and replacing them byρj\+Λj\\rho\_\{j\}\+\\Lambda\_\{j\}keeps that property\.□\\square

This is the classical bound on the VC dimension of the positivity sets of a fixed function plus a\(d\+1\)\(d\+1\)\-dimensional space of functions\([Cover, 1965](https://arxiv.org/html/2610.22714#bib.bib15);[Dudley, 1978](https://arxiv.org/html/2610.22714#bib.bib16)\)\. By the Sauer–Shelah lemma\([Sauer, 1972](https://arxiv.org/html/2610.22714#bib.bib55);[Shelah, 1972](https://arxiv.org/html/2610.22714#bib.bib56)\)such a head orders at most∑i≤d\+1\(r−1i\)\\sum\_\{i\\leq d\+1\}\\binom\{r\-1\}\{i\}of the2r−12^\{r\-1\}sequences, fewer than 90% ford=4d=4andr≥9r\\geq 9\. Withd=r−2d=r\-2the bound is attained by the keyskσj=ejk\_\{\\sigma\_\{j\}\}=e\_\{j\}forj≤r−2j\\leq r\-2andkσr−1=kσr=0k\_\{\\sigma\_\{r\-1\}\}=k\_\{\\sigma\_\{r\}\}=0\. The positional bias is zero on the keysj<rj<r, large on the last key and large and negative on the positions without a key, and the query has the coordinateLLor−L\-Lby the fate of each key\. The path term must depend on the token alone\. If it may also read the position, a head withd=0d=0already orders every sequence ofℱr\\mathcal\{F\}\_\{r\}\.

### A\.6Proof of[Theorem3\.2](https://arxiv.org/html/2610.22714#S3.Thmtheorem2)

LetqPq^\{P\},cPc^\{P\},ksPk^\{P\}\_\{s\}andℓsP\\ell^\{P\}\_\{s\}denote the query, the offset, the keys and the logits at the final query ofxPx^\{P\}\.

###### Lemma A\.1\(Gap\)\.

Let0<ε≤1/\(2​r\+2\)0<\\varepsilon\\leq 1/\(2r\+2\)and let the head realiseAPA^\{P\}with toleranceε\\varepsilononxPx^\{P\}\. Then for all alive keysa,a′a,a^\{\\prime\}and every dead keyxx,

\|ℓσaP−ℓσa′P\|≤γA=log⁡1\+\(r−1\)​ε1−ε,ℓσaP−ℓσxP≥γD=log⁡1−εr​ε,\|\\ell^\{P\}\_\{\\sigma\_\{a\}\}\-\\ell^\{P\}\_\{\\sigma\_\{a^\{\\prime\}\}\}\|\\leq\\gamma\_\{\\mathrm\{A\}\}=\\log\\frac\{1\+\(r\-1\)\\varepsilon\}\{1\-\\varepsilon\},\\qquad\\ell^\{P\}\_\{\\sigma\_\{a\}\}\-\\ell^\{P\}\_\{\\sigma\_\{x\}\}\\geq\\gamma\_\{\\mathrm\{D\}\}=\\log\\frac\{1\-\\varepsilon\}\{r\\varepsilon\},andγD\>γA\\gamma\_\{\\mathrm\{D\}\}\>\\gamma\_\{\\mathrm\{A\}\}\.

###### Proof\.

Letm=\|AP\|m=\|A^\{P\}\|\. Every alive key haswa≥\(1−ε\)/mw\_\{a\}\\geq\(1\-\\varepsilon\)/m, and the weights of all positions sum to one, so another alive key haswa′≤1−\(m−1\)​\(1−ε\)/mw\_\{a^\{\\prime\}\}\\leq 1\-\(m\-1\)\(1\-\\varepsilon\)/mandwa′/wa≤\(1\+\(m−1\)​ε\)/\(1−ε\)w\_\{a^\{\\prime\}\}/w\_\{a\}\\leq\(1\+\(m\-1\)\\varepsilon\)/\(1\-\\varepsilon\)\. A dead key haswx≤εw\_\{x\}\\leq\\varepsilon, sowa/wx≥\(1−ε\)/\(r​ε\)w\_\{a\}/w\_\{x\}\\geq\(1\-\\varepsilon\)/\(r\\varepsilon\)\. The inequalityγD\>γA\\gamma\_\{\\mathrm\{D\}\}\>\\gamma\_\{\\mathrm\{A\}\}is equivalent to\(1−ε\)2\>r​ε​\(1\+\(r−1\)​ε\)\(1\-\\varepsilon\)^\{2\}\>r\\varepsilon\(1\+\(r\-1\)\\varepsilon\), whose left side decreases and whose right side increases inε\\varepsilon\. Atε=1/\(2​r\+2\)\\varepsilon=1/\(2r\+2\)it reads\(2​r\+1\)2\>r⁡\(3​r\+1\)\(2r\+1\)^\{2\}\>r\(3r\+1\), that isr2\+3​r\+1\>0r^\{2\}\+3r\+1\>0\. ∎

###### Lemma A\.2\(One pattern per query\)\.

Under the hypothesis of[Theorem3\.2](https://arxiv.org/html/2610.22714#S3.Thmtheorem2), ifP≠P′P\\neq P^\{\\prime\}andP1=P1′=1P\_\{1\}=P^\{\\prime\}\_\{1\}=1, thenqP≠qP′q^\{P\}\\neq q^\{P^\{\\prime\}\}\.

###### Proof\.

Suppose thatqP=qP′=qq^\{P\}=q^\{P^\{\\prime\}\}=q, and letjjbe the smallest index withPj≠Pj′P\_\{j\}\\neq P^\{\\prime\}\_\{j\}, so that2≤j≤r−12\\leq j\\leq r\-1, and assumePj=1P\_\{j\}=1andPj′=0P^\{\\prime\}\_\{j\}=0\. The prefixes ofxPx^\{P\}andxP′x^\{P^\{\\prime\}\}up toσj\\sigma\_\{j\}coincide by the second property ofℱr\\mathcal\{F\}\_\{r\}, so the keys atσ1\\sigma\_\{1\}andσj\\sigma\_\{j\}coincide as well\. With the common query and positional bias the offset cancels, andΔ=ℓσjP−ℓσ1P=ℓσjP′−ℓσ1P′\\Delta=\\ell^\{P\}\_\{\\sigma\_\{j\}\}\-\\ell^\{P\}\_\{\\sigma\_\{1\}\}=\\ell^\{P^\{\\prime\}\}\_\{\\sigma\_\{j\}\}\-\\ell^\{P^\{\\prime\}\}\_\{\\sigma\_\{1\}\}\. InxPx^\{P\}keys 1 andjjare both alive, soΔ≥−γA\\Delta\\geq\-\\gamma\_\{\\mathrm\{A\}\}, and inxP′x^\{P^\{\\prime\}\}key 1 is alive and keyjjdead, soΔ≤−γD<−γA\\Delta\\leq\-\\gamma\_\{\\mathrm\{D\}\}<\-\\gamma\_\{\\mathrm\{A\}\}, a contradiction\. ∎

There are2r−22^\{r\-2\}patterns withP1=1P\_\{1\}=1, and by[LemmaA\.2](https://arxiv.org/html/2610.22714#A1.Thmtheorem2)they have pairwise different queries\. Each of theddcoordinates of a query takes at most2p2^\{p\}values, so2r−2≤2d​p2^\{r\-2\}\\leq 2^\{dp\}, that isd​p≥r−2dp\\geq r\-2\.□\\square

The proof uses four facts\. All sequences share the length and the key positions, the prefix up to keyjjdepends only on the fates of the earlier keys, key 1 is alive in2r−22^\{r\-2\}patterns, and the tolerance givesγD\>γA\\gamma\_\{\\mathrm\{D\}\}\>\\gamma\_\{\\mathrm\{A\}\}\. Without a bound on the values of the query no lower bound onddalone follows\. Keys built from the prefix with a one\-coordinate midpoint code separate the alive keys from the dead ones by a single threshold at every time in exact arithmetic, so evend=1d=1meets the ordering condition of[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)with such keys\. The argument does not apply to biases in which a later token acts on each key separately, as in Selective Attention, DCP and causal attention with lookahead keys\([Anagnostidis et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib7);[Leviathan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib6);[Song et al\., 2026](https://arxiv.org/html/2610.22714#bib.bib20)\)\. The contribution of such a bias for keyjjis not a function of the prefix up toσj\\sigma\_\{j\}\.

### A\.7Proof of[Proposition3\.3](https://arxiv.org/html/2610.22714#S3.Thmtheorem3)

Fix a sequence ofℱr\\mathcal\{F\}\_\{r\}and its final query\. In the stack form the walk lives on the half\-integer grid, so a dead position hasϕ¯t​s≤Ws−12\\bar\{\\phi\}\_\{ts\}\\leq W\_\{s\}\-\\tfrac\{1\}\{2\}and bias at most−β/2\-\\beta/2, and an alive position has bias zero\. The logit of a key position is its bias, and the logit of every other position, the query included, is its bias minusMM\. So the alive keys have logit 0, the dead keys at most−β/2\-\\beta/2and the other positions at most−M\-M\. WithZ=\|A\|\+RZ=\|A\|\+R, at mostr−1r\-1dead keys and exactly2​r2rother positions,

R=∑dead keysebt​s\+∑otherebt​s−M≤\(r−1\)e−β/2\+2re−M≤ε2\+ε2=ε\.R=\\sum\_\{\\text\{dead keys\}\}e^\{b\_\{ts\}\}\+\\sum\_\{\\text\{other\}\}e^\{b\_\{ts\}\-M\}\\leq\(r\-1\)e^\{\-\\beta/2\}\+2re^\{\-M\}\\leq\\tfrac\{\\varepsilon\}\{2\}\+\\tfrac\{\\varepsilon\}\{2\}=\\varepsilon\.Keyrris always alive, so\|A\|≥1\|A\|\\geq 1\. All positions other than the alive keys then have total weightR/Z≤εR/Z\\leq\\varepsilon, and each alive key has weight1/Z≥1/\(\|A\|\+ε\)≥\(1−ε\)/\|A\|1/Z\\geq 1/\(\|A\|\+\\varepsilon\)\\geq\(1\-\\varepsilon\)/\|A\|\. The increments are multiples of12\\tfrac\{1\}\{2\}and0≤W≤r0\\leq W\\leq r, so the walk takes at most2​r\+12r\+1values\.□\\square

Without the dot product the query position keeps the bias zero, the largest possible, so the field alone cannot meet the tolerance onceε≤1/\(\|A\|\+1\)\\varepsilon\\leq 1/\(\|A\|\+1\)\.

### A\.8Proof of[Proposition3\.4](https://arxiv.org/html/2610.22714#S3.Thmtheorem4)

First,bt​s=β​min⁡\(0,minu⁡\(ϕu−ψs\)\)=−β​max⁡\(0,maxu⁡\(ψs−ϕu\)\)=−β​Dt​smaxb\_\{ts\}=\\beta\\min\\bigl\(0,\\min\_\{u\}\(\\phi\_\{u\}\-\\psi\_\{s\}\)\\bigr\)=\-\\beta\\max\\bigl\(0,\\max\_\{u\}\(\\psi\_\{s\}\-\\phi\_\{u\}\)\\bigr\)=\-\\beta D^\{\\max\}\_\{ts\}\. In Selective Attention the selection of tokenuufor keysspasses through a ReLU and is summed over the positions strictly beforett, and the first token and the key itself are not masked\([Leviathan et al\., 2025](https://arxiv.org/html/2610.22714#bib.bib6)\)\. With a selection head of the formω⁡\(ψs−ϕu\)\\omega\(\\psi\_\{s\}\-\\phi\_\{u\}\)andω\>0\\omega\>0, the mask is thereforeFt​s=∑s<u<trelu⁡\(ω⁡\(ψs−ϕu\)\)=ω​Dt​ssumF\_\{ts\}=\\sum\_\{s<u<t\}\\mathrm\{relu\}\(\\omega\(\\psi\_\{s\}\-\\phi\_\{u\}\)\)=\\omega D^\{\\mathrm\{sum\}\}\_\{ts\}\.

\(i\) An inserted step adds an element of at mostDt​smaxD^\{\\max\}\_\{ts\}to the set whose maximum isDt​smaxD^\{\\max\}\_\{ts\}, so the maximum and the bias do not change, whileDt​ssumD^\{\\mathrm\{sum\}\}\_\{ts\}grows by the inserted dip\. For tokens under \([2](https://arxiv.org/html/2610.22714#S2.E2)\) this is not automatic, since the increment of a token shifts every later level\. Ifδ\\delta,ggandhhdepend on the token alone, a block of tokens whose increments sum to zero and whose dips stay at mostDt​smaxD^\{\\max\}\_\{ts\}preserves the values of all other positions\.

\(ii\) Setψs=0\\psi\_\{s\}=0andt=s\+m\+1t=s\+m\+1, and let every otherϕv\\phi\_\{v\}withs<v≤ts<v\\leq tbe at least zero\. One stepu∈\(s,t\)u\\in\(s,t\)withϕu=−η\\phi\_\{u\}=\-\\etagivesDt​smax=Dt​ssum=ηD^\{\\max\}\_\{ts\}=D^\{\\mathrm\{sum\}\}\_\{ts\}=\\eta, andmmsuch steps giveDt​smax=ηD^\{\\max\}\_\{ts\}=\\etaandDt​ssum=m​ηD^\{\\mathrm\{sum\}\}\_\{ts\}=m\\eta\.

\(iii\) Let a multiset have maximumx∗x^\{\\ast\}and other elementsx1,…,xkx\_\{1\},\\dots,x\_\{k\}\. Starting from\{x∗\}\\\{x^\{\\ast\}\\\}and insertingx1,…,xkx\_\{1\},\\dots,x\_\{k\}one at a time never changesΓ\\Gamma, because each inserted element is at most the maximum, which staysx∗x^\{\\ast\}\. SoΓ\\Gammaof the multiset equalsΓ⁡\(\{x∗\}\)\\Gamma\(\\\{x^\{\\ast\}\\\}\)\.□\\square

### A\.9Proof of[Proposition3\.5](https://arxiv.org/html/2610.22714#S3.Thmtheorem5)

The family is the graded\-depth family of[SectionB\.3](https://arxiv.org/html/2610.22714#A2.SS3)\. Keyjjhas levelLjL\_\{j\}, withLj−Lj−1∈\{5,6,7\}L\_\{j\}\-L\_\{j\-1\}\\in\\\{5,6,7\\\}, and a dip of depthη\\etaconsists of the dip tokens at levelsLj−xL\_\{j\}\-xforx∈\{η,η−1,0\}x\\in\\\{\\eta,\\eta\-1,0\\\}\(forη=1\\eta=1the depths are\{1,0,0\}\\\{1,0,0\\\}\), its deepest token repeatedmj∈\{1,2\}m\_\{j\}\\in\\\{1,2\\\}times\. A head realises the target exactly on the keys whenℓs\+κ​ηs\\ell\_\{s\}\+\\kappa\\eta\_\{s\}is the same for every keyssof the sequence\.

\(a\) Fix the levelLLof the first key and a head of the class that realises the target exactly on every sequence whose first key has levelLL\. Letfx=χ⁡\(D​⟨L−x⟩,K​⟨L⟩\)≥0f\_\{x\}=\\chi\(\\texttt\{D\}\\langle L\-x\\rangle,\\texttt\{K\}\\langle L\\rangle\)\\geq 0denote the contribution of the dip token at depthxx\. Let two sequences differ only in the duration of the first key’s dip of depthxx, which is held once in one and twice in the other\. The second has one more copy of the deepest token between key 1 and the query, so the logit of key 1 is lower byfxf\_\{x\}, while every later key keeps its logit and no target changes\. Key 2 shows that the common value ofℓs\+κ​ηs\\ell\_\{s\}\+\\kappa\\eta\_\{s\}is the same in both sequences, and key 1 then givesfx=0f\_\{x\}=0, forx=1,2,3,4x=1,2,3,4\. Next let two sequences differ only in the first key’s dip, of depth 2 in one and depth 3 in the other\. By the first step the dip tokens contributef0f\_\{0\}to key 1 in both, every other token after key 1 is the same, and every later key keeps its logit\. Exact realisation then requiresℓ1\+2​κ=ℓ1\+3​κ\\ell\_\{1\}\+2\\kappa=\\ell\_\{1\}\+3\\kappa, which contradictsκ\>0\\kappa\>0\.

\(b\) Letϕu\\phi\_\{u\}be the level of the token for dip and key tokens and a value above every level for all other tokens\. Letψs\\psi\_\{s\}be the level of keyssandβ=κ\\beta=\\kappa, and let the score between query and key be the same for every key\. The tokens after keyssare its own dip, whose minimum level isLs−ηsL\_\{s\}\-\\eta\_\{s\}, other tokens above every level, and later blocks at levels of at leastLs\+1L\_\{s\}\+1\. So the bias of keyssis−κ​ηs\-\\kappa\\eta\_\{s\}and the target is met exactly\. Holding a step repeats a value already in the range, and an inserted dip of keyssthat is no deeper adds values of at leastLs−ηsL\_\{s\}\-\\eta\_\{s\}after it and above every earlier level, so no range minimum changes\. In \([2](https://arxiv.org/html/2610.22714#S2.E2)\) this isδ=0\\delta=0with token\-dependent offsetsggandhh\.□\\square

Part \(a\) uses only sequences in which key 1 has a dip and a later key follows it\. With fixed durations the class fits the targets exactly, with contributions\(0,1,1,2,2\)​κ\(0,1,1,2,2\)\\,\\kappaof a dip token at depths 0 to 4, so only durations that vary for dips of the same depth separate the two\.

### A\.10Proof of[Proposition3\.6](https://arxiv.org/html/2610.22714#S3.Thmtheorem6)

In the two\-walk family𝒢r\\mathcal\{G\}\_\{r\}every token carries one step for each of two walks\. The key token has the steps\(1,1\)\(1,1\), the four block tokens carry\(±12,±12\)\(\\pm\\tfrac\{1\}\{2\},\\pm\\tfrac\{1\}\{2\}\), and⟨s⟩\\langle\\mathrm\{s\}\\rangleand?carry\(0,0\)\(0,0\)\. The sequencexP\(1\),P\(2\)x^\{P^\{\(1\)\},P^\{\(2\)\}\}has the shape of a ladder sequence, and blockiiconsists of two tokens whose first steps followPi\(1\)P^\{\(1\)\}\_\{i\}and whose second steps followPi\(2\)P^\{\(2\)\}\_\{i\}as inℱr\\mathcal\{F\}\_\{r\}\. The alive key sets at the final query are thereforeA\(h\)=\{j<r:Pj\(h\)=1\}∪\{r\}A^\{\(h\)\}=\\\{j<r:P^\{\(h\)\}\_\{j\}=1\\\}\\cup\\\{r\\\}forh=1,2h=1,2, and the complementary part hasP\(2\)=¬P\(1\)P^\{\(2\)\}=\\lnot P^\{\(1\)\}\.

Letkjhk^\{h\}\_\{j\}andρjh\\rho^\{h\}\_\{j\}denote the key and the positional bias of headhhat keyjj, which do not depend on the sequence\. Letzj=\(kj2,−kj1\)∈ℝ2​dz\_\{j\}=\(k^\{2\}\_\{j\},\-k^\{1\}\_\{j\}\)\\in\\mathbb\{R\}^\{2d\}andνj=ρj2−ρj1\\nu\_\{j\}=\\rho^\{2\}\_\{j\}\-\\rho^\{1\}\_\{j\}\. Both heads subtract the sameFσjF\_\{\\sigma\_\{j\}\}, so withQ=\(q2,q1\)Q=\(q^\{2\},q^\{1\}\)the difference of the heads is

ℓσj2−ℓσj1=⟨Q,zj⟩\+νj\+\(c2−c1\),j=1,…,r\.\\ell^\{2\}\_\{\\sigma\_\{j\}\}\-\\ell^\{1\}\_\{\\sigma\_\{j\}\}=\\langle Q,z\_\{j\}\\rangle\+\\nu\_\{j\}\+\(c^\{2\}\-c^\{1\}\),\\qquad j=1,\\dots,r\.
\(a\) On an ordered sequence of the complementary part, letx<rx<rbe alive under walk 2 and dead under walk 1, andy<ry<rthe reverse\. Head 2 givesℓσx2\>ℓσy2\\ell^\{2\}\_\{\\sigma\_\{x\}\}\>\\ell^\{2\}\_\{\\sigma\_\{y\}\}and head 1 givesℓσy1\>ℓσx1\\ell^\{1\}\_\{\\sigma\_\{y\}\}\>\\ell^\{1\}\_\{\\sigma\_\{x\}\}, so the difference is larger atxxthan atyy\. A threshold between the two groups then makes a function of𝒞=\{j↦⟨Q,zj⟩\+νj−θ\}\\mathcal\{C\}=\\\{j\\mapsto\\langle Q,z\_\{j\}\\rangle\+\\nu\_\{j\}\-\\theta\\\}positive exactly on\{j<r:Pj\(1\)=0\}\\\{j<r:P^\{\(1\)\}\_\{j\}=0\\\}\.

\(b\) With toleranceε≤1/\(2​r\+2\)\\varepsilon\\leq 1/\(2r\+2\),[LemmaA\.1](https://arxiv.org/html/2610.22714#A1.Thmtheorem1)applies to each head with its own alive set\. Keyrris alive under both walks\. Forx<rx<ralive under walk 2 and dead under walk 1 the difference atxxexceeds that atrrby at leastγD−γA\>0\\gamma\_\{\\mathrm\{D\}\}\-\\gamma\_\{\\mathrm\{A\}\}\>0\. Fory<ry<ralive under walk 1 the difference atrrexceeds that atyyby the same amount\. Soj↦⟨Q,zj−zr⟩\+νj−νrj\\mapsto\\langle Q,z\_\{j\}\-z\_\{r\}\\rangle\+\\nu\_\{j\}\-\\nu\_\{r\}, in which the offsets cancel, is positive exactly on\{j<r:Pj\(1\)=0\}\\\{j<r:P^\{\(1\)\}\_\{j\}=0\\\}\.

In both parts distinct sequences give distinct sign patterns on\{1,…,r−1\}\\\{1,\\dots,r\-1\\\}\. The class of part \(a\) shatters no2​d\+22d\+2points, because the vectors\(zj,1\)∈ℝ2​d\+1\(z\_\{j\},1\)\\in\\mathbb\{R\}^\{2d\+1\}of any2​d\+22d\+2points are linearly dependent and the argument of[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)applies\. The class of part \(b\) shatters no2​d\+12d\+1points for the same reason with the vectorszj−zr∈ℝ2​dz\_\{j\}\-z\_\{r\}\\in\\mathbb\{R\}^\{2d\}\. By the Sauer–Shelah lemma\([Sauer, 1972](https://arxiv.org/html/2610.22714#bib.bib55);[Shelah, 1972](https://arxiv.org/html/2610.22714#bib.bib56)\)the classes have at mostN⁡\(r,d\)N\(r,d\)andN′​\(r,d\)N^\{\\prime\}\(r,d\)sign patterns onr−1r\-1points\.□\\square

The proof uses only that both heads subtract the same mask, which may depend arbitrarily on the sequence, and that the pair of heads is fixed in advance\. It covers Selective Attention whose keys depend only on the token and the position, including RoPE at a common final query, and in part \(a\) a fixed positive scale of the mask in one head\. It also covers the masks of DCP, which may remove a key completely\. Every key that a counted sequence needs has a finite mask, because it is alive under one of the walks\. In part \(a\) the two sequences in which one walk keeps every key are the exception, and the class𝒞\\mathcal\{C\}already contains their patterns\. For keys and positional biases in general position and a mask chosen freely the countsN⁡\(r,d\)N\(r,d\)andN′​\(r,d\)N^\{\\prime\}\(r,d\)are attained, the second once the biases are large enough for the tolerance\.

## Appendix BOne\-layer probes

### B\.1Common setup

Every probe was a single attention layer on token embeddings of width 64, supervised at the final query, and[AppendixD](https://arxiv.org/html/2610.22714#A4)lists the settings of every probe\. The values were fixed one\-hot vectors of the key positions and the readout was the identity, so the output of the head was its weight on each key\. The loss was the cross\-entropy of these weights against the target\. The deeper models of[Table5](https://arxiv.org/html/2610.22714#A2.T5)addL−1L\-1pre\-norm blocks of width 64 with 4 heads and a feed\-forward width of 256 in front of the supervised head\. We trained with AdamW \(0\.9, 0\.98\), weight decay 0\.01, batch 64, a warm\-up of 200 steps followed by cosine decay to zero, gradient clipping at 1\.0 and single precision, and we drew fresh training data at every step\. Training lasted 4000 steps, and 16,000 steps on the graded\-depth families\. The seeds of the main runs were 1801 to 1815, and the sampled test sets used seeds that no tuning run had used\.

We declared the same search of 24 tuning runs for every method on the alive\-set, graded\-depth and two\-walk families\. FPA, FoX, Selective Attention and DCP crossed three learning rates in\{10−3,3×10−3,10−2\}\\\{10^\{\-3\},3\\times 10^\{\-3\},10^\{\-2\}\\\}and two tuning seeds with four values of one more setting\. This setting was the definition of the minimum for FPA, the initial gate bias for FoX, the selection scale for Selective Attention and the initial bias of the interaction scores for DCP\. The methods without such a setting searched twelve learning rates from10−410^\{\-4\}to10−110^\{\-1\}\. A grid whose end was selected was extended once by a decade\. Each competitor was tuned on its positive control and FPA on the setting where it can succeed, and we froze the chosen configurations with a hash before the main runs\. After the pilots we fixed the definition of FPA as the straight\-through minimum of[Section2](https://arxiv.org/html/2610.22714#S2)with a learned strength per head, and we selected its learning rate again\.

The search departed from the declaration in four ways\. Grid extensions, remedies for positive controls and the second selection for FPA raised the number of tuning runs above 24 \([Table4](https://arxiv.org/html/2610.22714#A2.T4)\)\. The configurations on the graded\-depth families and that of Selective Attention with one mask per head came from exploratory runs instead of the declared search\. These runs compared only the selection scales 1 and1/31/3for Selective Attention on the graded depths\. The learning rates of Selective Attention on the graded depths and of the variant with one mask per head lay at the upper end of their grids, which we did not extend\. The sum of dips on the graded depths took the learning rate of FPA without a search of its own\. Selective Attention with a shared mask used the scale1/31/3, which tuning chose on the positive control of the two walks, on the two\-walk and retrieval families\. Unlike on the alive sets, no main run on these families used the scale 1 of its paper\. After its one extension the selected learning rate still lay at an end of the grid in four cases\. These were FPA and FPA with the sum of dips on the stack family, stick\-breaking attention in retrieval and softmax attention with RoPE in variable assignment\.

Table 4:Tuning runs and GPU minutes of the search in the pilotson the two families whose comparisons rest on a declared search\. A dagger marks a search that took more than 1\.25 times the GPU time of the cheapest compared search of its family\. We estimated the GPU minutes of runs that shared the GPU from a calibration of throughput\. The configuration of Selective Attention with one mask per head came from later exploratory runs\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. ALiBi, attention with linear biases\. NoPE, no positional encoding\. RoPE, rotary position embedding\. DCP, Dynamic Context Pruning\.FamilyMethodRunsGPU minAlive setsFPA†4846\.3FoX†4028\.9Selective Attention†4030\.2Softmax \+ ALiBi2816\.6Softmax \+ NoPE2816\.3Softmax \+ RoPE2415\.8Stick\-breaking2416\.5Two walksFPA3632\.5Selective Attention, shared mask4432\.6Selective Attention, one mask per head4030\.0DCP†4466\.7For every component we ran a one\-sided exact McNemar test of FPA against the competitor on the per\-seed successes, and a hypothesis was supported only when all its components rejected atα=0\.05/7\\alpha=0\.05/7\. The seven tests are the three tests of[Section4\.1](https://arxiv.org/html/2610.22714#S4.SS1)and two tests of each of the two language\-model hypotheses, of which we ran one each\. At the tested settings of the alive\-set and two\-walk families, the counts of[AppendixA](https://arxiv.org/html/2610.22714#A1)rule out every success of the compared competitors\. Each test on these families then depends only on the successes of FPA, withp=2−kp=2^\{\-k\}forkkof them\. The preregistered refutation of each probe hypothesis was a one\-sided 99% Clopper–Pearson upper bound below0\.50\.5on the success rate of FPA\. On the alive\-set and two\-walk families a competitor run beyond these counts would also have refuted the hypothesis, unless an implementation error or, for two walks, a model outside the assumptions of[Proposition3\.6](https://arxiv.org/html/2610.22714#S3.Thmtheorem6)explained it\. No run went beyond them, and no hypothesis was refuted\. In these probes we trained the selection of Selective Attention with the gradient of a softplus in place of that of its ReLU, while the forward pass kept the ReLU of the paper\. With the ReLU gradient the selections of several pilot heads closed at the start of training and never reopened\. We checked the forward pass of our implementation element by element against a line\-by\-line transcription of the sketch in Figure 2 of the paper of Selective Attention\.

### B\.2Alive sets

The ladder families of[SectionA\.1](https://arxiv.org/html/2610.22714#A1.SS1)withr∈\{6,10,14,18\}r\\in\\\{6,10,14,18\\\}used the full set of2r−12^\{r\-1\}sequences as their test set\. The query at the final position came from a network that read the one\-hot vectors of all tokens through a hidden layer of width 256 with the Gaussian error linear unit and an output of sizeH​dHd\. The query could thus depend arbitrarily on the prefix, as[Theorem3\.1](https://arxiv.org/html/2610.22714#S3.Thmtheorem1)allows\. Every key had a learned offset per position and head, and FPA, FoX, Selective Attention and softmax attention also used RoPE\. ALiBi added the fixed slope2−82^\{\-8\}of a single head, and NoPE and stick\-breaking attention, which followed its paper, used the offsets alone\. The deeper models of[Table5](https://arxiv.org/html/2610.22714#A2.T5)had neither this query network nor these offsets\. The field of FPA and the gates of FoX read only the token embedding\. A test of the rank of the key logits confirmed that each competitor stayed in the class of the theorem\. The positive controls withd=r\+2d=r\+2admit a construction in the class, keys equal to one\-hot vectors of the key positions and queries equal to the indicator of the alive set\.

Table 5:Every cell of the alive\-set family, as seeds out of 15 that ordered the alive keys above the dead keys on at least 90% of the sequences\. Selective Attention appears with the selection scale 10 chosen in tuning and with the scale 1 of its paper\. The last rows compare the level of the key with the level of the query, whose alive sets are always suffixes\. A dash marks a cell that the design did not include\. FPA, First Passage Attention\. RoPE, rotary position embedding\. NoPE, no positional encoding\. ALiBi, attention with linear biases\. FoX, Forgetting Transformer\.The four competitors in the class succeeded atr=6r=6, whered=r−2d=r\-2allows every pattern, and failed on every seed at largerrr, while their positive controls succeeded on every seed\. Two\-layer softmax and FoX models learned the family atr=14r=14on every seed, atr=18r=18the two\-layer softmax models failed on every seed and the two\-layer FoX models succeeded on 8, and four\-layer models learned both\. A field\-only FPA head with a dot product of dimension 1 learned the family on 12 seeds atr=10r=10and on 10 atr=14r=14\. With the level of the query in place of the level of the key, as in StructFormer and PRPN, the same head succeeded on no seed, although it learned a family restricted to suffixes on 12 seeds\.

### B\.3Graded depths and varied durations

Each sequence of the graded\-depth family starts with⟨s⟩\\langle\\mathrm\{s\}\\rangleand holds six keys whose tokens carry their levels, with consecutive levels 5, 6 or 7 apart\. After each key come zero to three filler tokens, with probability 0\.75 a dip, and zero to three fillers again, and the sequence ends with the query?\. A dip of depthη∈\{1,2,3,4\}\\eta\\in\\\{1,2,3,4\\\}consists of three dip tokens whose levels lieη\\eta,η−1\\eta\-1and00below the key, in random order, and the target weight of keyjjis proportional toe−ηje^\{\-\\eta\_\{j\}\}\. The model had no positional information, its query came from the token?alone, its keys came from their tokens alone, and its head dimension was 8\. A seed fitted a test set when the weights on the keys, renormalised over the keys, were within total variation 0\.05 of the target on at least 90% of the 2000 sequences\. With fixed durations every deepest step lasted one step, and with varied durations each lasted one or two steps, drawn per dip\. We drew the spacings of the levels, the fillers, the dips and their depths, orders and durations independently\.

Table 6:Graded depths with fixed and with varied durations, as seeds out of 15 that fitted the training distribution\. The sum of dips replaces the minimum of FPA and keeps the same field\. FPA, First Passage Attention\.The secondary test measured, on the seeds that fitted fixed durations, the change of the total variation when a deepest step was held two or three steps or a dip no deeper was inserted\. The rule required both methods to fit fixed durations on 80% of the seeds, which FPA reached on only 9\. After the pilots and before the main runs we decided that the deviation counts only the keys after the first one\. The dip of the first key lies in the range of no other key, and the learned walks read its depth by summing increments\. A separate family in which the levels follow the walk, built to check invariance on the side of FPA, was fitted by FPA and by its sum of dips on all 15 seeds\. With every dip held 0 or 16 steps at its bottom instead of 4 to 8, the share of ordered sequences fell by at most 0\.1 on 14 seeds of FPA and 10 of the sum of dips\. Only FPA reached the preregistered line of 12 such seeds\.

### B\.4Two walks

The two\-walk family of[AppendixA](https://arxiv.org/html/2610.22714#A1)withr=14r=14has 8192 sequences in its complementary part, all of which formed the test set\. The queries and keys had learned offsets per position and head, the final query came from the network of the alive\-set family, and the fields of FPA read only the token embedding\. The training data mixed uniform pairs of patterns \(one half\), complementary pairs \(one quarter\) and pairs in which one walk keeps every key \(one eighth each\)\. DCP used an interaction dimension of 2 and anα\\alpha\-sigmoid whose exponent rose from 1 to 2 during training\. Its step function at inference can remove an alive key completely, so in the training loss only, we replaced a log\-probability of exactly−∞\-\\inftyby−50\-50\.

Table 7:Two walks with two heads of dimension 2, as seeds out of 15 that ordered the keys of both walks on at least 90% of the sequences\. One mask per head is our variant of Selective Attention, in which every head computes its own selection\. FPA, First Passage Attention\. DCP, Dynamic Context Pruning\.No run of a shared mask on the complementary part ordered more than 2,380 sequences or met the tolerance1/301/30on more than 1,093, the bounds of[Proposition3\.6](https://arxiv.org/html/2610.22714#S3.Thmtheorem6)\.

### B\.5Stack

The stack family consists of random legal sequences of 40 operations, pushes of eight symbols and pops, with a stack depth of at most six\. The target at the final query is uniform over the pushed items still on the stack, and the head dimension was 8\. FPA succeeded on 14 seeds and FPA with the sum of dips on 11, and one\-layer FoX, softmax attention with RoPE and Selective Attention succeeded on none\. These competitors used the learning rates of an earlier check, and FoX used the default initialisation of its gates\. We have no proof that they cannot learn the family in one layer, so we draw no comparison from them\.

### B\.6Retrieval among alive keys

This task needs both parts of FPA at once\. A sequence holds 16 slots and ends with a query for one name\. Each slot is a key with a name in\{0,…,5\}\\\{0,\\dots,5\\\}and a level in\{1,…,8\}\\\{1,\\dots,8\\\}with probability 0\.6 and a dip at a level otherwise, and zero or one filler follows it\. A key is alive when no later dip falls below its level, and the queried name occurs four or five times with at least two alive occurrences whose margins differ\. At least one dead occurrence precedes the first alive one and at least one lies between two alive ones, so neither a cut by position nor a choice by level alone solves the task\. The target is uniform over the alive occurrences of the queried name\. A seed succeeded when the head realised it with tolerance0\.10\.1on at least 90% of the sequences, a rule that we chose after the pilots and before the main runs\. Before any run we fitted strategies of each ablation in the hard limit on a sample of 8000 sequences\. On a second sample of 2000 sequences from the same generator, separate from the test set of the main runs, the best that we found for any ablation reached0\.49050\.4905, below the preregistered line of0\.60\.6\. By that rule the results read as evidence that both the level of the key and retrieval by content are needed among these variants\.

Table 8:Retrieval among alive keys, as seeds out of 15 that succeeded\. FPA, First Passage Attention\. FoX, Forgetting Transformer\.
### B\.7Tasks from earlier work

We ran six published tasks at a smaller scale than their papers, so our numbers do not compare with theirs\. Variable assignment follows Selective Attention \(three variables, 1000 values, 32 assignments\), and multi\-query repeated associative recall \(MQRAR\) follows stick\-breaking attention \(64 keys, 256 key and value symbols\)\. Flip\-flop language modelling uses length 256 and a probability of 0\.8 for the ignore instruction\([Liu et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib48)\), and copying follows Selective Attention\. Counting asks at every position how often its token occurred so far, and multi\-query associative recall \(MQAR\) uses 16 pairs in sequences of 128\([Arora et al\., 2024](https://arxiv.org/html/2610.22714#bib.bib49)\)\. The models were two\-layer decoders of width 128 with two heads and a feed\-forward width of 512, and a one\-layer decoder of width 64 for flip\-flop\. FPA, FoX and Selective Attention used RoPE in addition to their mechanisms, although FoX uses none by default in its paper, and stick\-breaking attention used no positional encoding, as in its paper\. In variable assignment the other attention models used learned absolute positions in place of RoPE, as the paper of Selective Attention does\. A long short\-term memory network \(LSTM\) of the same depth and width served as a recurrent reference\. Training lasted 4000 steps, and 8000 for MQAR, with a warm\-up over the first 10% of the steps and weight decay on all parameters, although the papers of FoX and stick\-breaking attention exempt the biases\. A seed succeeded when its main accuracy reached0\.990\.99, or for flip\-flop when its error stayed at most0\.010\.01\.

Table 9:Tasks from earlier work, as seeds out of 15 that succeeded\. In variable assignment the softmax column used learned absolute positions in place of RoPE\. MQRAR, multi\-query repeated associative recall\. MQAR, multi\-query associative recall\. FPA, First Passage Attention\. RoPE, rotary position embedding\. FoX, Forgetting Transformer\. Sel\. Att\., Selective Attention\. Stick\-br\., stick\-breaking attention\. LSTM, long short\-term memory network\.In pilot runs of two\-layer FPA models on MQAR, the first layer learned to suppress the attention from each value to its own key\. The previous\-token head that starts the recall circuit therefore never formed\. An exploratory inspection of the FPA language model found its previous\-token heads in the second and third of its 12 layers\. In these heads a large strength turned the bias into a narrow window, and the model copied as well as FoX did \([AppendixC](https://arxiv.org/html/2610.22714#A3)\)\. Two exploratory checks, outside the preregistration, support this reading\. Three\- and four\-layer FPA models failed MQAR on each of 4 seeds, and the same models without a bias in their first layer succeeded on each of 2 seeds\. We also ran Selective Attention with the ReLU gradient of its paper in exploratory runs\. It succeeded on 1, 3, 15, 15, 15 and 15 seeds of the six tasks in the order of[Table9](https://arxiv.org/html/2610.22714#A2.T9), close to its results with the softplus gradient\.

## Appendix CLanguage models

### C\.1Models, data and training

All four models are pre\-norm decoders with RMSNorm, a SwiGLU feed\-forward network of width 2048, no biases and tied embeddings, with 12 layers of width 768 and 12 heads of dimension 64, following the 125M configuration of FoX\([Lin et al\., 2025a](https://arxiv.org/html/2610.22714#bib.bib4)\)\.[Figures22](https://arxiv.org/html/2610.22714#A4.F22),[15](https://arxiv.org/html/2610.22714#A4.T15)and[16](https://arxiv.org/html/2610.22714#A4.T16)give the architecture and every setting\. The vocabulary of 32,000 tokens gives 109\.5M parameters for softmax attention and Selective Attention and 109\.9M for FPA\. FPA computes its field projection in single precision, uses no positional encoding and learns one strength per head\. FoX uses the kernel of its authors without positional encoding and initialises its gate biases at zero, as its paper does for data\-dependent gates\. Selective Attention uses RoPE, and its selection has the ReLU gradient of its paper\. Softmax attention uses RoPE with base 10,000\.

The training data was a chunk of SlimPajama\([Soboleva et al\., 2023](https://arxiv.org/html/2610.22714#bib.bib62)\)with every document wrapped in⟨s⟩\\langle\\mathrm\{s\}\\rangleand⟨/s⟩\\langle/\\mathrm\{s\}\\rangle, and the validation and test sets were the first 20M tokens of its validation and test splits\. The sources of SlimPajama come with their own terms of use and may include copyrighted text\. We cut the training stream into non\-overlapping windows of 2049 tokens, visited them in one fixed order for all four models and used each window at most once\. Training ran 5,150 steps of 524,288 tokens, 2\.70B tokens in total, with AdamW \(0\.9, 0\.95\), learning rate2×10−32\\times 10^\{\-3\}after 512 warm\-up steps and cosine decay to zero, weight decay 0\.1 on the matrices, gradient clipping at 1\.0 and half\-precision autocast with loss scaling\. All runs used one 12 GB partition of an NVIDIA Turing GPU \(compute capability 7\.5, without native bfloat16\)\. Training took 23\.8 hours for FPA, 21\.5 for FoX, 38\.9 for Selective Attention and 26\.3 for softmax attention \([Table15](https://arxiv.org/html/2610.22714#A4.T15)\)\. The evaluated model trained with an earlier version of the kernel of[Section4\.3](https://arxiv.org/html/2610.22714#S4.SS3), which computes the same function \([AppendixE](https://arxiv.org/html/2610.22714#A5)\)\. To time that kernel, we trained a second FPA model in an exploratory run of the same configuration with seed 2202, outside the preregistration\.

[Figure5](https://arxiv.org/html/2610.22714#A3.F5)shows how the four models trained\. FPA started more slowly than FoX and Selective Attention and had a higher validation loss at step 250\. From step 500 on it had the lowest validation loss of the four at every evaluation\. At the end its validation loss lay 0\.020 nats below that of FoX, 0\.006 below that of Selective Attention and 0\.027 below that of softmax attention\.

Figure 5:Training of the four language models\.\(a\) Training loss, averaged over 50 steps of 524,288 tokens, on a vertical axis that is logarithmic in the loss minus 2\.75 nats\. \(b\) Validation loss of each baseline minus that of FPA, on 1024 validation windows every 250 steps, so that positive values favour FPA\. The triangles mark values beyond the axis, which were−0\.16\-0\.16for FoX at step 250 and\+0\.46\+0\.46and\+0\.25\+0\.25for softmax attention at steps 250 and 500\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\.
### C\.2Evaluation and tests

The test loss averaged the cross\-entropy over the 20M test tokens in windows of 2048\. WikiText\-103\([Merity et al\., 2017](https://arxiv.org/html/2610.22714#bib.bib66)\)used its test set, and PG\-19 used up to four windows of 4096 tokens per test book and averaged the loss at positions 2048 to 4095 over 99 books\. The passkey items hide a five\-digit number in repeated filler text\([Mohtashami and Jaggi, 2023](https://arxiv.org/html/2610.22714#bib.bib57)\), ten numbers at each of five depths, so 50 items at each of 1024, 2048, 3072 and 4096 tokens\. The non\-inferiority test resampled documents 10,000 times and compared the upper1−α1\-\\alphaquantile of the difference in test loss withln⁡1\.01\\ln 1\.01\. The extrapolation test resampled books and asked for an upper1−α/21\-\\alpha/2quantile below zero, and the passkey test was an exact one\-sided McNemar test atα/2\\alpha/2on the items at 3072 and 4096\. Evaluating in single precision changed the difference of the first test by less than10−610^\{\-6\}\.

### C\.3Amendments

Three amendments changed the preregistration during the runs, and each was frozen before the result it affects existed\. The first round of training, with a reference implementation of FPA at context 512, stopped before its first checkpoint, and the round reported here replaced it\. The PG\-19 evaluation first kept the carriage returns of the books, a token that the training data never contained, so we amended the extrapolation test to Unix newlines\. We had seen the PG\-19 losses of FPA and softmax attention at that point, but FoX, the comparator of the test, had not yet been evaluated\. With carriage returns the test would also have supported FPA, with a difference of−0\.250\-0\.250nats\. The carriage returns raised the loss of every model, by 1\.34 to 1\.97 nats on average in windows of 2048 tokens and most for softmax attention\. Under both conventions FPA had the lowest loss beyond the training length \([Figure6](https://arxiv.org/html/2610.22714#A3.F6)\)\. Selective Attention first trained with the softplus gradient of the probes\. A preregistered check after 1000 steps favoured the ReLU gradient of its paper, and the reported model continued the run of that check, so it trained with the ReLU gradient from the start\. Its mask and attention ran through a fused Triton kernel that we wrote for it, with a micro\-batch of 2 instead of 4 and the same tokens per step\.

Figure 6:Loss by position on the PG\-19 test books\.Mean loss per bin of 64 positions in windows of 2048 and of 4096 tokens, up to four windows per book from 100 and 99 books\. The top panels use Unix newlines, as the amended extrapolation test does, and the bottom panels keep the carriage returns of the books\. The extrapolation test compared the positions 2048 to 4095 of panel \(b\)\. The vertical axes are logarithmic in the loss minus 3\.1 nats in the top panels and 4\.4 nats in the bottom panels, which spreads out the lowest losses\. The models were trained with context 2048\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\.
### C\.4Descriptive evaluations

Table 10:FPA minus each baselineon the descriptive evaluations, with 95% bootstrap intervals in brackets\. PG\-19 losses come from windows of 16,384 tokens, passkey and NIAH \(needle in a haystack\) are accuracies on 50 items, and the downstream rows are zero\-shot accuracies or log\-likelihoods from the evaluation harness of[Gao et al\. \(2024\)](https://arxiv.org/html/2610.22714#bib.bib63)\. Negative losses and positive accuracies favour FPA\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\.Each needle\-in\-a\-haystack item hides one or four sentences of the form “The pass key of*name*is*number*\.” at random sentence boundaries in a passage of a PG\-19 test book\. The item then asks for the key of one name, and there were 50 items for each length and number of needles\. The downstream tasks were LAMBADA\([Paperno et al\., 2016](https://arxiv.org/html/2610.22714#bib.bib50)\), HellaSwag\([Zellers et al\., 2019](https://arxiv.org/html/2610.22714#bib.bib51)\), PIQA\([Bisk et al\., 2020](https://arxiv.org/html/2610.22714#bib.bib52)\), ARC\([Clark et al\., 2018](https://arxiv.org/html/2610.22714#bib.bib53)\)and WinoGrande\([Sakaguchi et al\., 2020](https://arxiv.org/html/2610.22714#bib.bib54)\)\. At this scale all four models stayed close to chance on most of them, and most differences had intervals that contained zero\. On the SlimPajama test set FPA had a lower loss than FoX at every position bucket of the window, by 0\.008 to 0\.022 nats\. FPA retrieved every passkey at all six lengths, from 1024 to 16,384 tokens \([Figure3](https://arxiv.org/html/2610.22714#S4.F3)\)\. FoX fell from 1\.00 at 2048 tokens to 0\.58 at 4096 and 0\.20 beyond, and Selective Attention retrieved 0\.80 at 2048 tokens and almost none beyond 3072\. Softmax attention retrieved about half of the passkeys even within its training length\. A probe during training measured the greedy accuracy on the second copy of a span every 1000 steps \([Figure7](https://arxiv.org/html/2610.22714#A3.F7)\)\. At the end the four models copied 0\.91 to 0\.93 of the tokens at a gap of 0 tokens, 0\.83 to 0\.85 at 128 and 0\.68 to 0\.71 at 320, with softmax attention highest at every gap\.

Figure 7:Copying during training\.Greedy accuracy on the second copy of a span of text at gaps of 0, 128 and 320 tokens between the two copies, every 1000 steps and at the last step\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\.Table 11:RULER and BABILong, mean accuracy over the 13 tasks of RULER and the five tasks qa1 to qa5 of BABILong, at the context lengths of the columns\. All models were trained with context 2048\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\.
### C\.5A demonstration without a usable task

We preregistered a zero\-shot demonstration in generated text with five worlds, on scopes in Python code, on who saw which hidden object, on branches in a version history, on stop\-loss orders and on a parenthetical remark about a novel\. Each world had 200 items and two kinds of control items that any model with the needed reading skill should answer\. One kind asks for the most recent mention of a candidate, and the other for an older mention that its content identifies\. The preregistered rule made a world usable when at least two models answered both kinds above chance by an exact lower bound\. No model did so in any world \([Table12](https://arxiv.org/html/2610.22714#A3.T12)\), so no world was usable and we ran no test\. Several models answered one kind of control item well and the other below chance\.

Table 12:Control items of the zero\-shot demonstration, as accuracy over 200 items without inserted filler sentences\. The recent items ask for the most recent mention and the older items for an older mention that its content identifies\. Chance is 0\.5, and bold marks an exact lower 95% bound above chance\. A world needed two models with both kinds in bold\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. Sel\. Att\., Selective Attention\.We report the design for completeness and draw no conclusion from it\.

### C\.6Observational analysis

A preregistered analysis read the final FPA checkpoint on the SlimPajama test stream, on the CPU and without changing the model\. For the alive sets it used the first 256 windows of 2048 tokens and the queries at positions from 1024 on\. A key counted as dead when its bias was below−10\-10and as alive when its bias was at least−1\-1\. For the brackets it used the first 256 windows inside one document with at least 32 bracket tokens, and it compared the walk with the bracket depth by a Spearman correlation after removing a linear trend in position from both\. A null distribution came from 1000 cyclic shifts of the depth within each window, and the familywise test took the maximum over the 144 heads\.

The median head marked 96\.5% of the keys as dead and 0\.3% as alive\. In 19 heads more than 10% of the alive sets were not suffixes, and in two heads of the first layer almost all were, with most of the attention on alive keys older than the newest dead key\. In 60 heads the mean increment at opening brackets and at closing brackets had opposite signs\. In 103 heads the median correlation lay outside the band of their own null distribution, against 1\.44 expected by chance, and 82 heads passed the familywise test at0\.010\.01, 81 of them with a positive correlation\. The correlations were small, with a median absolute value of 0\.032 over heads and a maximum of 0\.248, and their significance comes from their consistency over 256 windows\. The detrended correlation mixes the level of the depth with the order of positions within a level, so we read these numbers as descriptions, not as evidence that the model tracks brackets\.

Figure 8:The three preregistered windows of the observational analysis\.Each column shows one window with the head that the preregistered rule chose for it, with layers and heads counted from 1\. The top panels show the walkWWof that head, with the bracket depth shaded\. The middle and bottom panels show the bias and the attention weight of every key at the last query of the window, with the alive keys marked, among them the query itself\. Attention weights below10−710^\{\-7\}are drawn at that value\. The walks of all three heads fall almost linearly, so their biases resemble that of FoX\. FoX, Forgetting Transformer\.[Figure8](https://arxiv.org/html/2610.22714#A3.F8)shows the three windows that a fixed seed chose before the analysis, each with the head of the largest standardised contrast between opening and closing brackets in that window\. The preregistration also placed the first window in the main text, and we moved it here for space\. In window 268 the only alive key at the last query is the query itself, which receives 0\.90 of the attention\.

[Figure4](https://arxiv.org/html/2610.22714#S4.F4)looks at the steps of the walk instead of the walk itself\. In window 268 the chosen head stepped up by 4\.70 on average where the depth rose and down by 5\.51 where it fell, against−0\.29\-0\.29at the other tokens\. Over all 256 windows, 56 heads had increments of opposite signs at opening and closing brackets together with a familywise significant correlation\.[Figure9](https://arxiv.org/html/2610.22714#A3.F9)shows the same alignment in the two other windows, with steps about ten times smaller\.

Figure 9:Steps of the walk at brackets in the two other preregistered windows\.Incrementsδt\\delta\_\{t\}of layer 1, head 6, the head that the rule chose for both windows, along the whole window, with the bracket depth shaded and darker where brackets nest\. The steps are about ten times smaller than in[Figure4](https://arxiv.org/html/2610.22714#S4.F4)but keep their signs, with means of\+0\.41\+0\.41and\+0\.38\+0\.38where the depth rises and−0\.50\-0\.50and−0\.51\-0\.51where it falls\.[Figure10](https://arxiv.org/html/2610.22714#A3.F10)shows the share of alive keys for every head of the final model\. Most heads keep a few keys alive, and a few heads keep nearly all of them\. The 19 heads whose alive sets are often not suffixes lie in nine of the twelve layers, and their shares of alive keys range from 0\.3% to 92%\.[Figure11](https://arxiv.org/html/2610.22714#A3.F11)counts where keys die\. In the median head the share of deaths at⟨s⟩\\langle\\mathrm\{s\}\\rangleand⟨/s⟩\\langle/\\mathrm\{s\}\\ranglewas 6\.6 times their share of the tokens\. We took as local the 95 heads with a share of alive keys below 0\.03\. On the 12 windows of the exploratory checks of[SectionC\.7](https://arxiv.org/html/2610.22714#A3.SS7), this threshold agrees with a median alive span below 64 tokens for 138 of the 144 heads of the final model\. Averaged over these heads, a token killed 0\.98 keys per occurrence, about one for each new token\. The end\-of\-document token killed 15 keys, and capitalised words without a space before them killed 4\.5 to 8\.2\.

![Refer to caption](https://arxiv.org/html/2610.22714v1/fig10.png)Figure 10:Alive keys of every head in the final FPA model\.Each cell gives the percentage of keys with a bias of at least−1\-1over the queries from position 1024 on in 256 test windows, with layers and heads counted from 1\. Dots mark the 19 heads whose alive sets are not suffixes at more than 10% of the queries\. FPA, First Passage Attention\.Figure 11:Where keys die in the final FPA model\.Keys killed per occurrence of a token, averaged over the 95 local heads, for the 15 tokens with the highest rate among those occurring at least 30 times in 256 test windows\. A visible space marks a token that starts with a space, and the dashed line is the mean over all tokens\. FPA, First Passage Attention\.
### C\.7Exploratory checks at three checkpoints

We inspected the FPA model at steps 1500 and 3250 of 5150 during training and at its final checkpoint, always on the same 12 validation windows of 2048 tokens\. These checks were exploratory and outside every preregistered test\. They used the reference implementation in single precision on the CPU and the thresholds of[SectionC\.6](https://arxiv.org/html/2610.22714#A3.SS6), and the figures redraw the numbers recorded at the time\. The figures show the final checkpoint and add the two earlier steps where training changed the result\.[Table13](https://arxiv.org/html/2610.22714#A3.T13)summarises the three checks\.

Table 13:Three checks of the FPA language model, at steps 1500 and 3250 of 5150 and at the final step, on the same 12 validation windows of 2048 tokens\. Local, middle and global heads have median alive spans below 64 tokens, from 64 to 1023 tokens and from 1024 on\. Alive sets count as often not suffixes when at least 20% of the queries have an alive key older than a dead one\. Document heads keep at least 80% of the keys within a document and at most 5% across documents\. The copying items differ from those of[Figure7](https://arxiv.org/html/2610.22714#A3.F7)\. FPA, First Passage Attention\.Step 1500Step 3250Step 5150Mean loss over the 12 windows3\.1622\.9172\.821Mean loss with the bias of every layer removed6\.5917\.3357\.828Loss increase with alive sets forced into suffixes\+\+0\.032\+\+0\.031\+\+0\.032windows with a positive increase12 of 1212 of 1212 of 12Local, middle and global heads90, 22, 3290, 20, 3490, 20, 34Heads whose alive sets are often not suffixes211514Heads whose walk is not monotone106109112Document heads799Copying accuracy, gap of 0 tokens0\.890\.930\.93Copying accuracy, gap of 320 tokens0\.780\.820\.84Copying accuracy, gap of 1000 tokens0\.610\.630\.65Removing the bias of every layer raised the loss on the 12 windows by 3\.43, 4\.42 and 5\.01 nats at the three steps\. On the first four windows the first layer carried most of this increase, and its part grew from 1\.49 to 2\.67 and 3\.48 nats \([Figure12](https://arxiv.org/html/2610.22714#A3.F12)\)\. At the final step the loss without the bias rose with position from 6\.1 to 8\.7 nats, while with the bias it fell from 3\.9 to 2\.9 \([Figure13](https://arxiv.org/html/2610.22714#A3.F13)\)\. Forcing the alive sets into suffixes, the sets that a forget gate can express, raised the loss on all 12 windows at every step, by 0\.032, 0\.031 and 0\.032 nats on average \([Figure14](https://arxiv.org/html/2610.22714#A3.F14)\)\.

Figure 12:The bias removed at three checkpoints of the FPA model\.Loss increase on the first four validation windows when the bias of all layers or of one layer is set to zero, at steps 1500, 3250 and 5150, the last step of training, on a logarithmic axis\. FPA, First Passage Attention\.Figure 13:Loss by position at three checkpoints\.\(a\) Loss per bin of 64 positions over the 12 validation windows, with the bias and with the bias of every layer removed\. \(b\) Loss increase when the alive sets of every head are forced into suffixes, the sets that a forget gate can express\.Figure 14:Alive sets forced into suffixes, per validation window\.Loss increase on each of the 12 windows at steps 1500, 3250 and 5150, with the means of 0\.032, 0\.031 and 0\.032 nats as dashed lines\.[Figure15](https://arxiv.org/html/2610.22714#A3.F15)shows the median alive span of every head of the final model\. Of the 144 heads, 90 kept keys alive for fewer than 64 positions, 20 for 64 to 1023 and 34 for longer, the same counts as at step 3250\. Between steps 1500 and 3250 the spans of 17 heads changed by a factor of two or more, and between step 3250 and the end only those of two heads did\. Averaged over the local heads, a token killed about one key per occurrence at every step, 0\.99, 0\.98 and 0\.98 \([Figure16](https://arxiv.org/html/2610.22714#A3.F16)\)\. The six tokens that killed most were the same at all three steps, and their rates grew during training, from 1\.90 to 2\.55 for a newline and from 3\.17 to 3\.84 for the tokenThewithout a space before it\.

![Refer to caption](https://arxiv.org/html/2610.22714v1/fig15.png)Figure 15:Median alive span of every head in the final FPA model\.Spans over the queries 1024 to 2047 of the 12 validation windows, with layers and heads counted from 1\. Triangles mark the 21 heads whose span grew or shrank by a factor of two or more since step 1500\. FPA, First Passage Attention\.Figure 16:Where keys die at three checkpoints\.Keys killed per occurrence of a token, averaged over the 90 local heads of each step, those with a median alive span below 64 tokens\. The bars give the final step for its 15 tokens with the highest rate among those occurring at least 30 times in the 12 validation windows\. Markers give steps 1500 and 3250 where the token was among the 15 highest at that step\. A visible space marks a token that starts with a space,\\nis the newline, and the dashed line is the mean over all tokens at the final step\.In every layer of the final model the attention that queries paid to earlier documents stayed between 0\.002 and 0\.10 with the bias \([Figure17](https://arxiv.org/html/2610.22714#A3.F17)\)\. Without the bias it rose to 0\.10 to 0\.21, against 0\.42 for weights spread evenly over the visible keys\.[Figure18](https://arxiv.org/html/2610.22714#A3.F18)shows, for heads that we selected by inspection, the share of keys of each token class that stayed alive 256 positions later\. Layer 1, head 10 kept capitalised words \(0\.93\) and word continuations \(0\.83\) but no digits\. Its alive keys therefore do not form a suffix, which no forget gate can produce\. The document heads kept nearly every key within a document and none across a document boundary\.

Figure 17:Attention on earlier documents at three checkpoints\.Attention that queries pay to the keys of earlier documents, averaged over the heads of each layer, with the bias and with the bias of every layer removed\. The dotted line is the share that weights spread evenly over the visible keys would give\.![Refer to caption](https://arxiv.org/html/2610.22714v1/fig18.png)Figure 18:Retention by token class in the final FPA model\.Share of the keys of each class that are still alive 256 positions later, for pairs of key and query in one document, and in the last column for pairs across a document boundary\. Content heads lie above the line and the document heads of step 3250 below it, with layers and heads counted from 1\. By the final step layer 9, head 5 kept only 76% of the keys within a document and no longer counted as a document head\. FPA, First Passage Attention\.[Figures19](https://arxiv.org/html/2610.22714#A3.F19),[20](https://arxiv.org/html/2610.22714#A3.F20)and[21](https://arxiv.org/html/2610.22714#A3.F21)show the bias of three heads of the final model on stretches of 64 tokens\. Layer 1, head 1 let groups of keys stop being alive at the end of a statement and at newlines, dots and underscores in C\+\+ code\. Layer 1, head 10 let articles, prepositions and punctuation lose their weight at the next token in a news report and kept content words\. Layer 4, head 9 removed the previous document at its end\-of\-document token\. Copying improved during training \([Table13](https://arxiv.org/html/2610.22714#A3.T13)\)\. The ablations show that the trained FPA model relies on these structures, not that a model trained with FoX could not reach the same function in another way\.

![Refer to caption](https://arxiv.org/html/2610.22714v1/fig19.png)Figure 19:The bias of layer 1, head 1 on C\+\+ code in the final FPA model\.Weight factorebt​se^\{b\_\{ts\}\}of every keyssfor every queryttat positions 1100 to 1163 of validation window 0, with factors below 0\.02 left white\. A key is alive while its factor is at leaste−1e^\{\-1\}\. Groups of keys stop being alive at once, nine at the end of a statement and three to six at newlines, dots and underscores\. FPA, First Passage Attention\.![Refer to caption](https://arxiv.org/html/2610.22714v1/fig20.png)Figure 20:The bias of layer 1, head 10 on a news report in the final FPA model\.Weight factorebt​se^\{b\_\{ts\}\}at positions 1100 to 1163 of validation window 680, with factors below 0\.02 left white\. Articles, prepositions, punctuation and newlines stop being alive at the next token, while content words such as*said*and*page*stay alive to the end of the stretch\. FPA, First Passage Attention\.![Refer to caption](https://arxiv.org/html/2610.22714v1/fig21.png)Figure 21:The bias of layer 4, head 9 at a document boundary in the final FPA model\.Weight factorebt​se^\{b\_\{ts\}\}at positions 233 to 296 of validation window 680, with factors below 0\.02 left white\. At the end\-of\-document token 36 of the 39 earlier keys of the stretch stop being alive, and at the start\-of\-document token the others do\. No key of the stretch before the boundary stays alive in the next document\. FPA, First Passage Attention\.

## Appendix DArchitectures and training configurations

This appendix collects the architectures, the hyperparameters and the searches of all experiments in one place, with every value read from the records of the runs\.

### D\.1Architecture

All our models are causal decoders with pre\-norm blocks, and the methods differ only in the bias that each attention layer adds to its logits \([Table14](https://arxiv.org/html/2610.22714#A4.T14)\)\.[Figure22](https://arxiv.org/html/2610.22714#A4.F22)shows the FPA model down to the operations of one head\. FPA computes its three scalars per head with one linear map from the same normalised input as the queries, keys and values\. The walk sums the increments over positions, the range minimum runs over the positions after each key, and the strength turns the depth of the deepest dip into the bias\. The bias enters every head of every layer before the softmax, and FPA uses no other positional information\. In training the forward pass takes the hard minimum and the backward pass the gradient of a soft minimum withτ=1\\tau=1\([Section2](https://arxiv.org/html/2610.22714#S2)\)\. Our kernel computes the range minimum in blocks of 64 positions without a matrix of sizeT×TT\\times T\([AppendixE](https://arxiv.org/html/2610.22714#A5)\)\.

\(a\)InputsTokenEmbeddingL×L\\timesRMSNormMulti\-HeadAttention\+\+RMSNormSwiGLUFeed Forward\+\+RMSNormLinearSoftmaxOutput Probabilities\(b\)xxLinearLinearLinearLinearFirst PassageAttentionHHVVKKQQδ,g,h\\delta,g,hConcatLinear\(c\)VVQQKKggδ\\deltahhMatMulScale\+\+MaskSoftMaxMatMulCumSum\+\+RangeMin\+\+Submin⁡\(0,⋅\)\\min\(0,\\cdot\)×\\timesβ\\betaWWϕ\\phiϕ¯\\bar\{\\phi\}ψ\\psiBB

Figure 22:Architecture of the FPA language model\.\(a\) Pre\-norm decoder withL=12L=12blocks of width 768\. \(b\) Multi\-head attention withH=12H=12heads of dimensiond=64d=64, in which a fourth linear map gives every head its incrementsδ\\deltaand offsetsggandhh\. \(c\) One head, in which the biasBBwith the entriesbt​sb\_\{ts\}joins the scaled scores before the causal mask\. RangeMin returnsϕ¯t​s=mins<u≤t⁡ϕu\\bar\{\\phi\}\_\{ts\}=\\min\_\{s<u\\leq t\}\\phi\_\{u\}for every queryttand keyss, and Sub returnsϕ¯t​s−ψs\\bar\{\\phi\}\_\{ts\}\-\\psi\_\{s\}\. The parts of FPA are orange, and the one\-layer probes use the attention of panel \(b\) alone on token embeddings\. FPA, First Passage Attention\. RMSNorm, root mean square normalisation\. SwiGLU, gated linear unit with the Swish activation\.Table 14:Bias that each method adds to the logitqt⊤​ks/dq\_\{t\}^\{\\top\}k\_\{s\}/\\sqrt\{d\}of keyssat querytt, with the parameters that it adds to a layer of widthD=768D=768withH=12H=12heads and its positional encoding in the language models\. FoX has one gatefuf\_\{u\}per head with a weight vectorww, a biasccand the logistic functionσ\\sigma\. Selective Attention takesq\(1\)q^\{\(1\)\}andk\(1\)k^\{\(1\)\}from its first head, shares the bias among all heads and never masks the start token\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. Sel\. Att\., Selective Attention\. RoPE, rotary position embedding\.
### D\.2Language models

[Table15](https://arxiv.org/html/2610.22714#A4.T15)describes the four language models and[Table16](https://arxiv.org/html/2610.22714#A4.T16)their common training\. All four used the same data in the same order, the same schedule and the hyperparameters of the 125M recipe of FoX, without a search\. They differ in the attention, its positional encoding, its kernel and the split of each batch into micro\-batches, which changes the gradient only through rounding\.

Table 15:The four language models\.Parameters count the tied embeddings once\. Throughput and time cover the whole run of 5150 steps with its validations and checkpoints on the GPU of[AppendixC](https://arxiv.org/html/2610.22714#A3)\. For FPA, throughput, time and memory come from an exploratory run of the same configuration with seed 2202 and the kernel of[Section4\.3](https://arxiv.org/html/2610.22714#S4.SS3), outside the preregistration\.[Table3](https://arxiv.org/html/2610.22714#S4.T3)instead gives the throughput that we measured in the benchmark over 12 training steps after 8 steps of warm\-up\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. Sel\. Att\., Selective Attention\. MLP, multilayer perceptron\. SwiGLU, gated linear unit with the Swish activation\. RMSNorm, root mean square normalisation\. RoPE, rotary position embedding\. SDPA, the scaled dot\-product attention of PyTorch\. GPU, graphics processing unit\. GiB, gibibyte\.Table 16:Training of the language models, the same for all four\. FPA, First Passage Attention\. Sel\. Att\., Selective Attention\. FoX, Forgetting Transformer\. ReLU, rectified linear unit\.
### D\.3Software and compute

All runs used PyTorch 2\.5\.1 with CUDA 12\.1 and Triton 3\.1\.0 under Python 3\.12 on the GPU of[AppendixC](https://arxiv.org/html/2610.22714#A3)\. The preregistered batch of probes and tasks had 1,815 runs, 15 seeds in each of 121 settings, which took 73\.5 hours summed over the runs\. Training the four language models with the kernels of[Table15](https://arxiv.org/html/2610.22714#A4.T15)took 110\.5 hours\.

### D\.4One\-layer probes and tasks from earlier work

[Table17](https://arxiv.org/html/2610.22714#A4.T17)gives the training of the probes of[AppendixB](https://arxiv.org/html/2610.22714#A2)and of the small decoders of[SectionB\.7](https://arxiv.org/html/2610.22714#A2.SS7), and[Tables18](https://arxiv.org/html/2610.22714#A4.T18)and[19](https://arxiv.org/html/2610.22714#A4.T19)give their models\.[Table20](https://arxiv.org/html/2610.22714#A4.T20)gives the declared search, and[Table21](https://arxiv.org/html/2610.22714#A4.T21)the configurations of the reported runs\. The pilots selected these configurations by the rules of[AppendixB](https://arxiv.org/html/2610.22714#A2), and a file with a hash froze them before the reported runs\.

Table 17:Training of the one\-layer probes and of the tasks from earlier work\.FPA, First Passage Attention\. MQAR, multi\-query associative recall\.Table 18:Models of the one\-layer probes, with one supervised attention layer on token embeddings of width 64 and the head dimensiondd\. On the alive sets every key has a learned offset per position and head, FPA, FoX, Selective Attention and softmax attention add RoPE, ALiBi adds its fixed slope, and NoPE and stick\-breaking attention use the offsets alone\. The positive controls of the alive sets used=r\+2d=r\+2, and the field\-only FPA of[Table5](https://arxiv.org/html/2610.22714#A2.T5)usesd=1d=1without positional information\. The two\- and four\-layer models put one or three pre\-norm blocks with 4 heads and an MLP of width 256 before the supervised layer\. On the alive sets and the two walks an MLP of the one\-hot sequence with a hidden layer of width 256 gives the final query\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. RoPE, rotary position embedding\. ALiBi, attention with linear biases\. NoPE, no positional encoding\. MLP, multilayer perceptron\.Table 19:Models of the tasks from earlier work, decoders with LayerNorm before each sublayer, an MLP with the Gaussian error linear unit, tied embeddings initialised as𝒩⁡\(0,0\.022\)\\mathcal\{N\}\(0,0\.02^\{2\}\)and the head dimensiondd\. The last three columns give the parameters of FPA, of softmax attention with RoPE and of an LSTM of the same depth and width\. In variable assignment the attention models use learned absolute positions, elsewhere RoPE, and stick\-breaking attention uses none\. Variable assignment also has 2000 test sequences with only two values, and flip\-flop 10,000 sparse and 2000 dense ones\. MLP, multilayer perceptron\. MQRAR, multi\-query repeated associative recall\. MQAR, multi\-query associative recall\. FPA, First Passage Attention\. RoPE, rotary position embedding\. LSTM, long short\-term memory network\.Table 20:Declared search of the probes and of the tasks from earlier work\.Each configuration ran with two tuning seeds, later four, and a grid whose end was selected was extended once by a decade \([Table4](https://arxiv.org/html/2610.22714#A2.T4)counts the runs\)\. The 12 learning rates are equally spaced on a logarithmic scale and served softmax attention with RoPE, NoPE or ALiBi and stick\-breaking attention on the alive sets\. After the pilots the straight\-through minimum replaced the four definitions of FPA, and its learning rate was selected again\. On retrieval FoX and Selective Attention kept the settings selected on the alive sets and the two walks, on the stack they used the default initialisation of PyTorch and the scale 1, and on the tasks from earlier work the gate bias 0 and the scale 1\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. Sel\. Att\., Selective Attention\. DCP, Dynamic Context Pruning\. RoPE, rotary position embedding\. NoPE, no positional encoding\. ALiBi, attention with linear biases\.MethodSecond settingValuesLearning ratesRuns*Alive sets, graded depths and two walks, per method and family*FPAdefinition of the minimumhard, soft withτ=1\\tau=1, annealed, soft then hard\{1,3,10\}×10−3\\\{1,3,10\\\}\\times 10^\{\-3\}24FoXinitial bias of the gates0, 2, 4, 6\{1,3,10\}×10−3\\\{1,3,10\\\}\\times 10^\{\-3\}24Sel\. Att\.selection scaleω\\omega1, 1/3, 3, 10\{1,3,10\}×10−3\\\{1,3,10\\\}\\times 10^\{\-3\}24DCPinitial interaction bias2, 0, 4, 8\{1,3,10\}×10−3\\\{1,3,10\\\}\\times 10^\{\-3\}24Softmax, stick\-breakingnone12 from10−410^\{\-4\}to10−110^\{\-1\}24*Stack, retrieval, ablations and deeper models, per method and family*Every methodfixed\{1,3,10\}×10−3\\\{1,3,10\\\}\\times 10^\{\-3\}6*Tasks from earlier work, per method and task*Every methodfixed\{1,3,10\}×10−3\\\{1,3,10\\\}\\times 10^\{\-3\}6Table 21:Learning rates of the reported runs, with the second setting in brackets, namely the initial gate bias of FoX, the selection scale of Selective Attention and the initial bias of the interaction scores of DCP\. The alive sets used one configuration for everyrrand, for the competitors, for their positive controls\. Selective Attention with the scale 1 of its paper used10−310^\{\-3\}on the alive sets, and with one mask per head the scale 3 and3×10−23\\times 10^\{\-2\}on the two walks\. The two\- and four\-layer models of FoX and of softmax attention used3×10−33\\times 10^\{\-3\}and10−210^\{\-2\}\. FPA used3×10−33\\times 10^\{\-3\}with the field only and10−210^\{\-2\}with the level of the query on the alive sets\. On retrieval it used3×10−33\\times 10^\{\-3\}without the level of the key,3×10−23\\times 10^\{\-2\}with the level of the query and10−310^\{\-3\}without content, and on MQAR10−310^\{\-3\}without a bias in its first layer\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. Sel\. Att\., Selective Attention\. DCP, Dynamic Context Pruning\. RoPE, rotary position embedding\. NoPE, no positional encoding\. ALiBi, attention with linear biases\. MQRAR, multi\-query repeated associative recall\. MQAR, multi\-query associative recall\. LSTM, long short\-term memory network\.Alive setsGraded depthsTwo walksStackRetrievalFPA0\.030\.0030\.0010\.10\.01FPA, sum of dips0\.0030\.1FoX0\.03 \(6\)0\.0030\.03 \(6\)Sel\. Att\.0\.03 \(10\)0\.03 \(1\)0\.03 \(1/3\)0\.001 \(1\)0\.03 \(1/3\)DCP0\.01 \(0\)Softmax with RoPE0\.05340\.001Softmax with NoPE0\.01520\.003ALiBi0\.00433Stick\-breaking0\.01520\.1Variable assignmentMQRARFlip\-flopCopyingCountingMQARFPA0\.0010\.0010\.010\.0030\.010\.0003FoX0\.001 \(0\)0\.003 \(0\)0\.01 \(0\)0\.003 \(0\)0\.01 \(0\)0\.001 \(0\)Sel\. Att\.0\.003 \(1\)0\.001 \(1\)0\.001 \(1\)0\.003 \(1\)0\.01 \(1\)0\.003 \(1\)Softmax with RoPE0\.00010\.0010\.0010\.010\.010\.001Stick\-breaking0\.0010\.0010\.010\.010\.0010\.003LSTM0\.010\.0030\.010\.010\.010\.003

## Appendix EKernel and cost

Our kernel computes FPA with its straight\-through minimum in fused Triton kernels on a grid of blocks of 64 positions shared by queries and keys\. For a query block and an earlier key block the forward pass forms the range minimum from the suffix minima of the key block, the minimum over the blocks in between and the prefix minima of the query block\. It runs the longest query blocks first\. The backward pass needs the gradient of the soft minimum, whose normaliser has the same three parts\. It computes the gradient of the field in four parts, for the positions in the key block, in the query block, in the blocks in between and in the diagonal block\. All exponentials are powers of two of quantities in the log\-two domain, the key side works on transposed tiles, and no value is added atomically, so the gradients are deterministic\. The evaluated FPA language model trained with an earlier version of this kernel\. Against a reference implementation in double precision, that version had relative errors of at most5\.1×10−45\.1\\times 10^\{\-4\}on the GPU, except3\.3×10−33\.3\\times 10^\{\-3\}in the gradient of the strength for tied values of the field\. In exploratory checks the current version had the same largest errors, and at most6\.7×10−46\.7\\times 10^\{\-4\}in backward passes over 4096 and 8192 positions\. In 200 exploratory training steps the two versions differed less than one version did under a different order of summing its micro\-batches\.

The benchmark ran on the GPU of[AppendixC](https://arxiv.org/html/2610.22714#A3)in half precision, with every method timed in the same process and a probe for contention before and after each part\.[Table22](https://arxiv.org/html/2610.22714#A5.T22)lists one attention layer at five shapes, and[Table23](https://arxiv.org/html/2610.22714#A5.T23)the eviction of keys whose bias fell below a threshold\. The bias of FoX inside our kernel took 1\.05 times as long as the kernel of FoX, so the extra time of FPA in[Table3](https://arxiv.org/html/2610.22714#S4.T3)comes from the operations that FPA adds\. The decoding times of[Table3](https://arxiv.org/html/2610.22714#S4.T3)hardly changed with the length of the prompt, from 1024 to 16,384 tokens, because fixed costs dominate at batch size 1\. Our decoding code for Selective Attention also keeps a single\-precision copy of the selection key, which raises its measured cache to 76,848 bytes per position, whereas[Table3](https://arxiv.org/html/2610.22714#S4.T3)counts the 73,776 bytes that its definition needs\.

Table 22:One attention layerwith 12 heads of dimension 64 at batch×\\timeslength, in milliseconds \(medians of 20 rounds\)\. The ratios in[Section4\.3](https://arxiv.org/html/2610.22714#S4.SS3)are medians over the rounds of the ratio within each round\. SDPA, the scaled dot\-product attention of PyTorch, with its memory\-efficient kernel on this GPU\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. Sel\. Att\., Selective Attention\.Table 23:Evictionof the keys whose bias fell below−θ\-\\theta\(FPA and FoX\) or whose mask rose aboveθ\\theta\(Selective Attention\), with the loss change in nats per token and the share of keys kept on SlimPajama test windows\. Softmax attention used a sliding window of the mean size that FPA keeps\. Block skipping is the pruning of[Lin et al\. \(2025b\)](https://arxiv.org/html/2610.22714#bib.bib47)\. FPA, First Passage Attention\. FoX, Forgetting Transformer\. Sel\. Att\., Selective Attention\.Beyond the training length, softmax attention without eviction diverged, so its sliding windows lowered its loss at length 8192\. FPA retrieved every passkey at 8192 and 16,384 tokens under every threshold, with 24% to 27% of its cache, whereas the windows of softmax attention retrieved at most 20%\.