Paper deep dive
Spatial Induction Heads: In-Context Learning of Multidimensional Cellular Automata
Kimia Kazemian, Menghan Xu, John Thickstun, Sarah Dean
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/8/2026, 6:55:44 AM
Summary
This paper introduces 'spatial induction heads,' a mechanistic framework explaining how two-layer transformers perform in-context learning on multidimensional cellular automata. Unlike standard induction heads that assume contiguous context, spatial induction heads handle serialized 2D/3D data by using a first layer to 'gather' scattered spatial neighbors via learned positional embeddings and a second layer to 'match' these configurations against past occurrences to predict future states. The authors provide theoretical proofs that this circuit can approximate Bayesian posteriors for stochastic rules and predict exactly for deterministic rules, supported by empirical evidence from trained models on Wolfram Rule 110 and Stavskaya rules.
Entities (8)
Relation Signals (8)
Spatial Induction Head → appliesto → Cellular Automata
confidence 98% · We study how transformers overcome this routing problem in multidimensional stochastic and deterministic cellular automata
Spatial Induction Head → implements → Gather-and-Match Circuit
confidence 95% · We introduce spatial induction heads, two-layer gather-and-match circuits...
Stavskaya Rule → istype → Stochastic Rule
confidence 95% · Stavskaya, a stochastic CA with p=0.29
Wolfram Rule 110 → istype → Deterministic Rule
confidence 95% · Wolfram Rule 110, a Turing-complete deterministic ECA.
Spatial Induction Head → approximates → Bayesian Posterior
confidence 93% · The end-to-end circuit can approximate the Bayesian posterior arbitrarily closely for stochastic rules
Matching Layer → implements → Bayesian Counting
confidence 92% · We further construct a matching layer which implements Bayesian counting.
Spatial Induction Head → solves → Routing Problem
confidence 90% · We study how transformers overcome this routing problem in multidimensional... cellular automata... We introduce spatial induction heads
Transformer → uses → Learned Positional Embeddings
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Induction heads provide a mechanistic account of in-context learning in sequential data, but existing theory largely assumes that the context relevant to a prediction forms a contiguous block. In multidimensional data, serialization breaks this assumption by scattering spatial neighbors across distant positions in the token sequence. We study how transformers overcome this routing problem in multidimensional stochastic and deterministic cellular automata, where each trajectory is generated by an unknown local rule and presented as a flattened sequence without an explicit coordinate-based spatial inductive bias. We introduce spatial induction heads, two-layer gather-and-match circuits in which the first layer reconstructs the relevant spatial neighborhood and the second matches the resulting configuration against earlier occurrences. We give two explicit realizations of the gather and show that the positional dimension required for spatial routing depends only on the local neighborhood and spatial dimension, not on grid volume or trajectory horizon. We further construct a matching layer which implements Bayesian counting. The end-to-end circuit can approximate the Bayesian posterior arbitrarily closely for stochastic rules and can predict exactly for deterministic rules. Empirically, trained two-layer transformers generalize to unseen rules in one and two dimensional settings, achieving near-perfect deterministic rollouts and less than 0.005 nats KL from the Bayes-optimal predictor on stochastic rules. Attention patterns and layerwise probes align with the predicted gather-and-match computation, providing mechanistic evidence for spatial induction in trained transformers.
Tags
Links
- Source: https://arxiv.org/abs/2610.09124v1
- Canonical: https://arxiv.org/abs/2610.09124v1
Trouble viewing inline? Open PDF directly →
Full Text
261,558 characters extracted from source content.
Expand or collapse full text
Spatial Induction Heads: In-Context Learning of Multidimensional Cellular AutomataThanks: Project page: https://kimzemian.github.io/spatial-induction-heads/ Kimia Kazemian †thanks: Equal contribution. Affiliation: Cornell University Email: k983@cornell.edu Menghan Xu †thanks: Equal contribution. Affiliation: Cornell University Email: mx253@cornell.edu John Thickstun Affiliation: Cornell University Email: jthickstun@cornell.edu Sarah Dean Affiliation: Cornell University Email: sdean@cornell.edu Abstract Induction heads provide a mechanistic account of in-context learning in sequential data, but existing theory largely assumes that the context relevant to a prediction forms a contiguous block. In multidimensional data, serialization breaks this assumption by scattering spatial neighbors across distant positions in the token sequence. We study how transformers overcome this routing problem in multi-dimensional stochastic and deterministic cellular automata, where each trajectory is generated by an unknown local rule and presented as a flattened sequence without an explicit coordinate-based spatial inductive bias. We introduce spatial induction heads, two-layer gather-and-match circuits in which the first layer reconstructs the relevant spatial neighborhood and the second matches the resulting configuration against earlier occurrences. We give two explicit realizations of the gather and show that the positional dimension required for spatial routing depends only on the local neighborhood and spatial dimension, not on grid volume or trajectory horizon. We further construct a matching layer which implements Bayesian counting. The end-to-end circuit can approximate the Bayesian posterior arbitrarily closely for stochastic rules and can predict exactly for deterministic rules. Empirically, trained two-layer transformers generalize to unseen rules in one and two dimensional settings, achieving near-perfect deterministic rollouts and less than 0.0050.005 nats KL from the Bayes-optimal predictor on stochastic rules. Attention patterns and layerwise probes align with the predicted gather-and-match computation, providing mechanistic evidence for spatial induction in trained transformers. 1 Introduction Figure 1: Trained-model predictions on two held-out rules. Top row: Wolfram Rule 110, a Turing-complete deterministic ECA. Bottom row: Stavskaya, a stochastic CA with p=0.29p=0.29; predictions are colored by the probability the model assigns to state 1. Teacher-forced predictions (middle column) condition on the ground-truth history at every step; autoregressive predictions (right column) are rolled out from the context alone, conditioning on the sample from the previous timestep. The induction head provides one of the best-understood mechanistic accounts of in-context learning (Elhage et al., 2021; Olsson et al., 2022). This two-layer circuit predicts novel sequences by completing patterns from precedent: the first layer records preceding tokens, while the second layer matches the current context to past records and copies the subsequent tokens. Induction heads have been used to explain the in-context behavior of large language models (Brown et al., 2020; Wei et al., 2022), and their theoretical foundations have been rigorously established for Markov chains (Bietti et al., 2023; Edelman et al., 2024). In this setting, the statistical induction head attends to the preceding k tokens to retrieve the empirical transition law (Ekbote et al., 2025). However, this theory relies on a rarely emphasized assumption: the context block is a contiguous sequence immediately preceding the query, reachable by a single attention layer using relative position. When transformers are applied to multidimensional spatiotemporal data, this assumption breaks down. Serializing a spatial grid into a one-dimensional token stream destroys local adjacency, scattering immediate neighbors across distant intervals in the sequence. The original Vision Transformer (Dosovitskiy et al., 2021) uses learned 1D absolute positional embeddings and shows that these embeddings recover aspects of the underlying 2D grid structure. Learned absolute positional embeddings also appear in recent image generators (Li et al., 2024; Yu et al., 2025; Bachmann et al., 2025). Their success motivates studying how Transformers learn structural relationships from token sequences without explicit geometric inductive biases on their positional embeddings. Despite this empirical success, there is no mechanistic understanding of how a transformer leverages a learned positional table to gather a neighborhood fractured by serialization, nor how it performs spatial in-context learning. Existing theories for k-order Markov chains assume contiguous context (Edelman et al., 2024), offering no analogue for sequential-to-spatial routing. This raises two fundamental questions: How does a transformer address and assemble scattered tokens to reconstruct a spatial neighborhood? And once assembled, how does it optimally infer the underlying dynamical rule without any coordinate-based spatial inductive bias? We address these questions by studying transformers on multidimensional stochastic cellular automata, which are historically viewed as systems of locally interacting Markov chains evolving on a multidimensional grid (Fernández et al., 2018). A stochastic cellular automaton consists of a grid of finite-state cells updated in parallel via a local kernel, mapping a cell’s neighborhood at one step to a state distribution at the next (Definition 1). In our study, the kernel is sampled afresh for each trajectory from a Dirichlet prior and hidden from the model, requiring pure in-context inference. This provides an ideal testbed: simple local rules generate essentially unbounded complexity (Langton, 1990), and the dependence structure is a spatial analogue to the Markov setting. We train two-layer transformers on this task. Figure 1 shows them continuing a trajectory from a short context on two held-out rules, the deterministic Wolfram Rule 110 and the stochastic Stavskaya rule at p=0.29p=0.29. Contributions. We formalize spatial in-context learning as a problem where serialization hides the geometry that the model must exploit. Our contributions are as follows: • Task & Theoretical Framework: We consider multidimensional cellular automata and derive the closed-form Bayes-optimal predictor (Theorem 3). We then introduce the spatial induction head (Definition 5), a two-layer circuit whose first layer gathers the spatial dependencies needed at each token, and whose second matches the resulting configuration against precedent. • Mechanistic Constructions: We give two explicit realizations of the gather, one using a head per offset and one using a single content-routed head with a separating MLP (Theorem 7, parts (I) and (I)). Both route scattered spatial neighbors with a compact set of positional frequencies whose number is independent of grid volume and horizon (Lemma 6). • Bayesian Matching: We show the matching layer performs Bayesian counting: once the gathered representation is available, a single Layer-2 head computes the posterior exactly under hard attention (Proposition 8) and arbitrarily closely otherwise (Theorem 9). • Empirical Verification: We validate the theory on 1D and 2D cellular automata. Two-layer transformers generalize to held-out rules (Figure 1), surpassing prior ICL results on cellular automata (Section 2), while attention maps (Figures 2 and 3) and layerwise probes (Figure 4) give strong evidence for the predicted gather-and-match computation. 2 Related work Transformers for automata and dynamical systems. Transformers have been studied on discrete automata both as diagnostic tasks and as synthetic sequence models. Vafa et al. (2024) use deterministic finite automata to probe limitations of large models, while Liu et al. (2022); Berkovich et al. (2025); Burtsev (2024) train smaller transformers on cellular automata. Only Burtsev (2024) studies in-context generalization to unseen rules; Liu et al. (2022) train per automaton and Berkovich et al. (2025) provide the rule in the prompt. Related work finds in-context prediction in discretized chaotic systems and hidden Markov processes (Liu et al., 2024; Dai et al., 2025), but does not identify a circuit for recovering spatially scattered dependencies. Induction heads and Markov-chain ICL. Induction heads originate in mechanistic studies of language models (Elhage et al., 2021; Olsson et al., 2022; Conmy et al., 2023). Theory has since characterized their operation on k-order Markov chains (Bietti et al., 2023; Makkuva et al., 2024a; Makkuva et al., 2024b; Nichani et al., 2024; Rajaraman et al., 2024), including statistical induction heads (Edelman et al., 2024) and a two-layer construction for general k (Ekbote et al., 2025). Our setting extends this line: probabilistic cellular automata are precisely systems of locally interacting Markov chains (Fernández et al., 2018). Serialization scatters the k relevant neighbors through the token stream, so the model must first gather them before performing the usual induction head computation. Bayesian and algorithmic views of in-context learning. A complementary account interprets ICL as approximate posterior inference under a prior induced by pretraining (Xie et al., 2021; Müller et al., 2021). In our stochastic cellular-automaton setting, the Bayes predictor is a smoothed count, and we show that the matching head represents it. Another line shows that transformers can implement optimization procedures such as gradient descent and higher-order variants (Von Oswald et al., 2023; Zhang et al., 2024; Ahn et al., 2023; Giannou et al., 2024); Cole et al. (2025) extends this view to linear dynamical systems. These works characterize an implemented learning algorithm, without considering spatial structure, whereas we characterize a circuit and the estimator it computes. Spatial structure in transformers. Architectures for grid-structured data often supply geometry explicitly, as in weather models using coordinate-dependent attention or mesh graphs (Bi et al., 2023; Lam et al., 2023). Vision transformers instead flatten patches and can use learned one-dimensional absolute position embeddings, with learned embeddings recovering row–column structure (Dosovitskiy et al., 2021). We adopt this geometry-free setting and ask how a standard transformer uses learned positions to route a scattered neighborhood and perform spatial in-context inference. 3 The task and the routing problem In this section, we cover four key pieces of background. First, we need well specified geometric data, so we consider the setting of stochastic cellular automata (§3.1). Then, we describe how we flatten the grid into a one-dimensional token stream, and we identify the set of offsets each prediction must reach (§3.2). Furthermore, we describe the two-layer transformer we study, which is given no geometric prior beyond a learned absolute positional table (§3.3). Finally, we identify the queries on which spatial in-context learning is well posed, and give the Bayes-optimal predictor for them (§3.4). 3.1 Cellular automata Definition 1 (Stochastic cellular automaton). Fix a torus =[W1]×⋯×[Wd]G=[W_1]×·s×[W_d], writing [n]≔0,…,n−1[n] \0,…,n-1\, of volume ||≔∏j=1dWj _j=1^dW_j, with Wj≥2W_j≥ 2. Cells of G are written z=(z1,…,zd)z=(z_1,…,z_d). Let =[V]S=[V] (V≥2V≥ 2) be a state set and δ1,…,δk∈ℤd _1,…, _k ^d a neighborhood of k≥1k≥ 1 offsets, distinct modulo (W1,…,Wd)(W_1,…,W_d). A local kernel f:k→ΔV−1f:S^k→ ^V-1, with ΔV−1 ^V-1 the probability simplex on S, defines a trajectory over horizon T≥2T≥ 2 from initial states (x0,z)z∈(x_0,z)_z , drawn i.i.d. uniformly on S, via transitions for t∈1,…,T−1t∈\1,…,T-1\, conditionally independent across z given step t−1t-1: xt,z∼f(⋅∣Pt,z),Pt,z≔(xt−1,z+δ1,…,xt−1,z+δk)∈k,x_t,z\; \;f(\,· P_t,z), P_t,z\; \; (x_t-1,\,z+ _1,\,…,\,x_t-1,\,z+ _k ) ^k, where addition is modulo (W1,…,Wd)(W_1,…,W_d). We write (t,z)(t,z) for the cell z at step t. Pt,zP_t,z is its parent configuration, whose entries are ordered by δ1,…,δk _1,…, _k, and we write DK≔δ1,…,δkD_K \ _1,…, _k\ for the set of key offsets, so |DK|=k D_K =k. The kernel f is drawn from the prior ⨂c∈kDir(αV) _c ^kDir( 1_V) with α>0α>0 and V1_V the all-ones vector, so the rows f(⋅∣c)f(· c), one per configuration c, are independent. This is a standard probabilistic cellular automaton on a torus (Fernández et al., 2018). The neighborhood DKD_K is fixed, and we ask whether the model can recover it. The kernel f is drawn afresh for every trajectory and is never shown to the model, whose parameters are fixed at test time. It observes only the flattened trajectory, and must infer f from earlier occurrences of the same neighborhood configuration within that one trajectory. We also study purely deterministic rules, which are the α→0α→ 0 limit of the prior, where every row f(⋅∣c)f(· c) is a point mass. Example. The classical elementary cellular automata (Wolfram, 1983) have d=1d=1, V=2V=2 and k=3k=3, with offsets (−1,0,1)(-1,0,1). In d=2d=2 the von Neumann neighborhood has k=5k=5, the offsets (0,0)(0,0), (±1,0)(± 1,0) and (0,±1)(0,± 1), while the Moore neighborhood used in Conway’s Game of Life (Gardner, 1970) has k=9k=9, the offsets (a,b)(a,b) with a,b∈−1,0,1a,b∈\-1,0,1\. A neighborhood of size k over V states admits VkV^k configurations and therefore V(Vk)V^(V^k) deterministic rules, which is 256256 in the elementary case, 2322^32 for von Neumann and 25122^512 for Moore. Stochastic rules assign a distribution over S, so they form a continuum of dimension Vk(V−1)V^k(V-1). 3.2 Sequence flattening and spatial routing A trajectory is presented to the model as a single token stream. Within a time step the cells are emitted in row-major order, with the last coordinate varying fastest, and a ROW_SEP closes each innermost row, except that the last row of a step is closed by a TIME_SEP in place of its ROW_SEP. One step therefore reads || cell tokens and ||/Wd /W_d separators: xt,(0,0),…,xt,(0,Wd−1)⏟row 0,ROW_SEP,…,xt,(m,0),…,xt,(m,Wd−1)⏟row m=||/Wd−1,TIME_SEP, x_t,(0,0),\,…,\,x_t,(0,W_d-1)_row 0,\; ROW\_SEP,\;…,\; x_t,(m,0),\,…,\,x_t,(m,W_d-1)_row m= /W_d-1,\; TIME\_SEP, for t=0,…,T−1t=0,…,T-1 in order, so the stream has length N=T(||+||/Wd)N=T( + /W_d). In d=1d=1 each time step is a single row, so the only separator is the TIME_SEP. The layout is an order-preserving injection ρ:[T]×→[N]ρ:[T]×G→[N], and we give the stream indexing in full in Appendix C. The flattening preserves adjacency along the innermost axis while obscuring adjacency along the others; the k tokens in the parent configuration need not form a contiguous block. In the transformer architecture, the cell token (t,z)(t,z) predicts the cell that follows it in the stream, one step along the row. We call such a token a query cell and the cell it predicts its target cell. We write u^d u_d for this step and call it the successor offset; it is the d-th coordinate vector of the torus G. A token therefore plays two roles. To make its current prediction, it must access the k parents of its target cell z+u^dz+ u_d, which lie at offsets DK+u^dD_K+ u_d from z. To serve as a precedent for later predictions, it must also represent its own k parents, which lie at offsets DKD_K. We denote the former set by DQD_Q. Definition 2 (Routing set). For a query cell (t,z)(t,z), with target cell z+u^dz+ u_d, the query offsets are DQ≔DK+u^dD_Q D_K+ u_d, and the routing set is ≔DK∪DQ=DK∪(DK+u^d)⊆U\; \;D_K∪ D_Q\;=\;D_K∪(D_K+ u_d)\; \;G. Example. On grids large enough to avoid wraparound, the elementary 11D neighborhood has DK=−1,0,1D_K=\-1,0,1\ and k=3k=3, so DQ=0,1,2D_Q=\0,1,2\ and =−1,0,1,2U=\-1,0,1,2\, with ||=4 =4. The 22D von Neumann neighborhood has k=5k=5 and ||=8 =8; the 22D Moore neighborhood has k=9k=9 and =−1,0,1×−1,0,1,2U=\-1,0,1\×\-1,0,1,2\, with ||=12 =12. Generally, k≤||≤min(2k,||)k≤ ≤ (2k, ). Figure 2 shows both offset sets in a trained model. In these examples DKD_K is symmetric but U is not, because DQD_Q is shifted by u^d u_d. Along the innermost axis, U extends one step further in the positive direction than DKD_K, but is the same along other axes. 3.3 The model We employ a two-layer causal decoder-only transformer (Vaswani et al., 2017) with learned absolute positional embeddings. Position n of the token stream has residual-stream vector xn(0)=WEen+WPpn∈ℝdmodelx^(0)_n=W_Ee_n+W_Pp_n ^d_model, where ene_n is the one-hot of the token at position n and WPW_P embeds the learned absolute position pn∈ℝdpp_n ^d_p (column n of P∈ℝdp×NP ^d_p× N) into the residual stream. Attention weights αn,n′(l)=softmaxn′≤n(⟨WQ(l)xn(l−1),WK(l)xn′(l−1)⟩).α^(l)_n,n \;=\;softmax_n ≤ n\! ( W^(l)_Qx^(l-1)_n,\;W^(l)_Kx^(l-1)_n ). at layer l∈1,2l∈\1,2\ determine the output ∑n′≤nαn,n′(l)WV(l)xn′(l−1) _n ≤ nα^(l)_n,n W^(l)_Vx^(l-1)_n which is projected back into the stream (optionally followed by a two-layer ReLU MLP of hidden width dMLPd_MLP). For simplicity of exposition, we absorb scaling factors into WQW_Q and WKW_K. Our analysis focuses on the learned positional table P, such as the one used in the original Vision Transformer (Dosovitskiy et al., 2021). Its columns are free parameters and supply no geometry of their own, so any spatial structure in a trained model must have been inferred from data. Appendix C.3 compares alternative positional embedding schemes. 3.4 Resolvable queries and the Bayes target The kernel is drawn from the Dirichlet prior of Definition 1, so the best possible prediction at a token is based on the posterior, given everything earlier in the stream. It has a closed form: count the earlier occurrences of the query configuration, and how often each state followed them. Denote Figure 2: Layer 1 gathers the routing cells; Layer 2 retrieves matching precedents. Attention weights from the shared-head model on 1D V=2,k=3V=2,k=3 (elementary cellular automata), Wolfram Rule 110. The query cell at z predicts the target cell at z+u^dz+ u_d (marked “?”). Layer 1 (left) concentrates on the four routing cells in the previous timestep, at offsets =DK∪DQU=D_K∪ D_Q relative to z, where DQ=DK+u^dD_Q=D_K+ u_d gives the target cell’s parent offsets. Layer 2 (right) concentrates on matching precedents: earlier cells whose parent configurations (at offsets DKD_K) match the query configuration (at offsets DQD_Q). Their states are used to predict the target cell. nc≔#(t′,z′):t′≥1,ρ(t′,z′)≤ρ(t,z),Pt′,z′=c,nc,y≔#those with xt′,z′=y.n_c \#\(t ,z ):t ≥ 1,\ ρ(t ,z )≤ρ(t,z),\ P_t ,z =c\, n_c,y \#\those with x_t ,z =y\. Theorem 3 (Bayes posterior predictive). For the Dirichlet prior and serialization (§3.2), the optimal predictive distribution at a token with query configuration c, given all earlier observations, is P^α(y∣c)=nc,y+αnc+Vα,y∈. P_α(y c)\;=\; n_c,y+αn_c+Vα, y . The proof and further discussion are provided in Appendix D. Definition 4 (Resolvable query, coverage). Configuration c∈kc ^k is covered at (t,z)(t,z) if Pt′,z′=cP_t ,z =c for some (t′,z′)(t ,z ) satisfying ρ(t′,z′)≤ρ(t,z)ρ(t ,z )≤ρ(t,z), i.e. if nc>0n_c>0. A query cell (t,z)(t,z) defines the query configuration Qt,z≔Pt,z+u^dQ_t,z P_t,\,z+ u_d, the parent configuration of its target cell, which determines the target state distribution f(⋅∣Qt,z)f(· Q_t,z). A query is resolvable if Qt,zQ_t,z is covered (Appendix D.1). If a query configuration c has not occurred earlier in the stream, then nc=0n_c=0 and P^α(⋅∣c) P_α(· c) reduces to the prior mean 1/V1/V, since there are no observations on f(⋅∣c)f(· c). In other words, the context only determines the target distribution if resolvability holds. In Section 4, we focus on resolvable queries. 4 Spatial Induction Heads: Construction and Optimality 4.1 The spatial induction head For spatial data, the model must construct the relevant neighborhood at the query cell before matching. We call the resulting two-stage circuit a spatial induction head. Definition 5 (Spatial induction head). A two-layer circuit is a spatial induction head, if at every resolvable query, it predicts in two stages: (i) The gather. Layer 1 assembles the spatial neighborhood information needed at the query cell. (i) The match. Layer 2 compares the resulting configuration against earlier configurations in the context and averages over matching precedents to predict the next state. In our cellular-automaton setting, the gather makes the states of all || routing cells, at offsets =DK∪DQU=D_K∪ D_Q, available at the query cell. These states serve two roles in Layer 2: the query reads the offsets DQD_Q, which form the query configuration, the parent configuration of the target cell, while the key at an earlier token reads the offsets DKD_K, which form that token’s own parent configuration. Layer 2 then performs the induction-style matching operation: the query configuration is compared against earlier parent configurations. Those that agree with it are the matching configurations, the cells carrying them are the matching precedents, and the states that followed those precedents are aggregated to form the prediction. Figure 2 shows the gather and match stages in a trained model. 4.2 Two constructions of the gather A standard transformer can realize the gather in two ways: it can use one attention head per routed offset, so that attention itself keeps the gathered states separate, or it can gather all offsets with a single head and use an MLP to separate them afterward. Both constructions rely on positional addressing to locate the required cells using learned absolute positional embeddings. Lemma 6 (Addressing). For any nonempty target offset set ⊆N , a Layer-1 positional score which ranks the previous-step cells at offsets N from the query above all other visible cells can be realized with dp=dS+2d_p=d_S+2, where the spatial addressing width is dS=O(||dlog||)d_S=O(|N|\,d |N|) in general or dS=2d_S=2d when ||=1|N|=1. The positional dimension is therefore independent of || and T. The two gather constructions use this addressing primitive differently: Construction I applies it separately to each singleton offset δ\δ\, while Construction I applies it once to the full routing set U. Theorem 7 (Spatial gather constructions). The Layer-1 gather of U has two realizations, both at widths independent of || and T: (I) Dedicated-heads construction. || heads, one per offset, and no Layer-1 MLP, with dp=2d+3d_p=2d+3 and dmodel=(||+2)V+2d+6d_model=( +2)V+2d+6. It recovers each routed state to any accuracy. (I) Shared-head construction. One head and an MLP which separates the routed states by offset, with dMLP≤2(V−1)||3+3d_MLP≤ 2(V-1) ^3+3 and dp≤O(||dlog||)+||3+3d_p≤ O( \,d )+ ^3+3. It recovers them exactly. A related head/nonlinearity tradeoff appears for sequential k-gram induction (Ekbote et al., 2025); here, the additional difficulty is preserving the identities of spatially separated offsets after routing. Proof sketch. In Construction I, head δ spatially addresses the cell at offset δ∈δ and writes its state directly into a dedicated V-dimensional block of the residual stream. Since the heads write into disjoint blocks, the offsets are already separated after attention and no Layer-1 MLP is needed. Construction I uses nonlinear capacity instead of separate heads. A single head attends jointly to the cells at all offsets in U. The cell state is encoded in the attention weight, while the value carries a positional label identifying the routing cell. A single global labeling guarantees these || routing cells remain mutually distinguishable at any query. Finally, the Layer-1 MLP uses the query’s positional information to decode the aggregate into one state block per offset. The Fourier construction underlying the addressing bound, the positional labeling scheme for the shared-head construction, and the exact transformer parameter constructions are given in Appendices E, F, and G. 4.3 Matching and Bayes-optimal prediction The gathered routing set feeds into a Layer-2 matching head. The query selects the gathered blocks indexed by DQD_Q, while each earlier key selects the blocks indexed by DKD_K. Their inner product, scaled by β>0β>0, measures agreement between the query configuration and an earlier parent configuration. Proposition 8 (Hard-attention matching as Bayesian counting). Suppose a single Layer-2 attention head assigns the same score a to every precedent whose parent configuration matches the current query, and −∞-∞ to all other positions. With no Layer-2 MLP, the head outputs the empirical conditional transition law (nc,y/nc)y∈(n_c,y/n_c)_y . Augmenting the context with a single prior token, of value 1V 1V1 and score a+log(Vα)a+ (Vα), makes the output exactly P^α(y∣c)=nc,y+αnc+Vα P_α(y c)= n_c,y+αn_c+Vα, the posterior of Theorem 3. Proof sketch. For one-hot state blocks, the query–key inner product counts matching offsets, so an exact configuration match attains the maximal score. If all matches receive the same score and nonmatches are excluded, softmax is uniform over the ncn_c matching precedents. Since each value carries the state that followed its configuration, their average is exactly the empirical conditional transition law. The prior token contributes total unnormalized weight VαVα with uniform value 1V 1V1, adding α to every state count and recovering the posterior of Theorem 3. ∎ A finite softmax need not realize this ideal matching exactly: nonmatching positions retain some attention mass, and approximation error from Layer 1 can make the scores of matching positions slightly unequal. The end-to-end result below controls both effects. Theorem 9 (End-to-end spatial induction; formally Theorem H.9). Let the Layer-1 gather construction have per-block error ϵ¯ ε, let β denote the Layer-2 query–key scale, and write Δ≔β(1−(2k+2)ϵ¯) β (1-(2k+2) ε ) for the resulting match–nonmatch separation. Suppose the Layer-2 head also discounts separators and initial-step cells. At every resolvable query with ncn_c matching precedents: (i) Stochastic rules. Fix κ∈(0,1]κ∈(0,1], assume N≥VαN≥ Vα, and include the prior token of Proposition 8. If Δ≥log(4N/((nc+Vα)κ)) ≥ (4N/((n_c+Vα)κ) ) and ϵ¯≤κ/(16kΔ) ε≤κ/(16k ), then the Layer-2 attention output p, read directly as a distribution, satisfies DKL(P^α(⋅∣c)∥p)≤κD_KL ( P_α(· c)\, \|\,p )≤κ. (i) Deterministic rules. In the deterministic limit α→0α→ 0, if ϵ¯<1/(2k+2) ε<1/(2k+2) and Δ>log(22(N−nc)/nc) > (2 2\,(N-n_c)/n_c ), then the predicted next state is exactly correct. The two cases place different demands on the matching scores. For a deterministic rule, every matching precedent has the same next state, so a sufficient gap between matches and nonmatches guarantees the correct prediction. For a stochastic rule, the relative weights among matching precedents also matter: their uniform average is what recovers the transition counts. Layer-1 error perturbs these matched scores by at most 2βkϵ¯2β k ε, so β must be large enough to suppress nonmatches without amplifying this dispersion too much. The two conditions in Theorem 9 balance these effects. 5 Experiments Table 1: Test-set prediction accuracy on held-out rules. Deterministic metrics use the ground-truth history (teacher forcing, TF) or greedy autoregressive (AR) rollout. Stochastic AR cell accuracy is reported for the model and the k-gram sampling baseline. Stochastic AR KL is DKL(qkgram∥qmodel)D_KL(q_kgram\|q_model) between the k-gram and model predictive distributions on the model’s rollout. Deterministic Stochastic Task Arch. TF cell acc AR cell acc AR cell acc (k-gram) AR KL 1D V=2,k=3V=2,\;k=3 Shared-head 1.0000 0.9999 0.5496 (0.5485) 0.0019 Dedicated-heads 1.0000 1.0000 0.5488 (0.5485) 0.0044 1D V=3,k=3V=3,\;k=3 Shared-head 1.0000 1.0000 0.3476 (0.3475) 0.0026 Dedicated-heads 1.0000 1.0000 0.3475 (0.3475) 0.0004 2D VN V=2,k=5V=2,\;k=5 Shared-head 1.0000 1.0000 0.5201 (0.5197) 0.0013 Dedicated-heads 1.0000 0.9999 0.5191 (0.5197) 0.0038 5.1 Experimental setup We train two layer transformers, then evaluate them on rules held out from training to measure their ability for spatial in-context learning. We also examine whether the learned internal representations are consistent with the two-stage structure of the theoretical constructions. We use three settings: 1D V=2,k=3V=2,k=3 (elementary cellular automata), 1D V=3,k=3V=3,k=3, and 2D von Neumann (VN) V=2,k=5V=2,k=5. The model receives only the first T0T_0 time steps of a trajectory generated under an unknown rule (not the rule table), and its weights are frozen at test time. Predictions are scored on cells from time step t=T0t=T_0 through t=T−1t=T-1. Every evaluation trajectory is rejection-sampled so that all VkV^k neighborhood configurations appear in the T0T_0 context rows, so every scored query is resolvable. Full details of data generation, training, and evaluation are in Appendix I. Rules. (1) Deterministic: each trajectory draws one rule uniformly from the corresponding split’s rule pool; training, validation, and test pools are mutually disjoint, so every val or test trajectory is generated by a rule the model has never seen during training. (2) Stochastic: each trajectory draws a fresh rule by independently sampling a Dirichlet(1,…,1)Dirichlet(1,…,1) transition row for every neighborhood configuration; because the Dirichlet is continuous, no two trajectories share the same rule. Architectures. We instantiate the two gather constructions of Theorem 7: the Dedicated-heads construction (|||U| L1 attention heads with no L1 MLP) and the Shared-head construction (one L1 attention head with L1 MLP). Both share a single L2 attention head and a two-layer L2 MLP. Metrics. For deterministic rules, we report TF cell accuracy (each predicted cell conditioned on the ground-truth history) and AR cell accuracy (greedy autoregressive rollout scored against the ground-truth trajectory). For stochastic rules, AR cell accuracy is the fraction of cells in a temperature-1 rollout that match the ground truth. The ceiling is well below 1; we also report a posterior-predictive sampling baseline, an independent rollout which samples each cell from the add-one-smoothed k-gram posterior predictive (its mode maximizes expected one-step accuracy). We additionally report AR DKL(qkgram∥qmodel)D_KL(q_kgram\|q_model), computed at each cell during autoregressive generation between the model’s predictive distribution and the causal k-gram distribution on the model’s own rollout. 5.2 Results Can the model recover unseen rules? Table 1 reports test-set performance across three settings and both architectures. On deterministic rules, all models reach near-perfect cell accuracy under both teacher forcing and autoregressive rollout. On stochastic rules, both architectures match the k-gram baseline in AR cell accuracy, and all AR KL values fall below 0.0050.005 nats. Both architectures thus perform accurate in-context prediction for previously unseen rules across all three settings. Figure 3: Attention alignment and ablation. Left: Mean attention mass on the positions predicted by each construction: L1 routing cells at offsets =DK∪DQU=D_K∪ D_Q, and L2 matching precedents, earlier cells whose parent configurations match the query configuration. Right: Cell accuracy when attention to the L1 routing cells or L2 matching precedents is masked at evaluation time, compared with no ablation and controls that mask attention to the same number of randomly selected cells. Do attention heads attend where each construction predicts? We next ask whether the model recovers the rule using the constructed two stage gather-and-match. We first examine the attention mass. Figure 3 (left) reports the mean attention mass on the construction-predicted positions. Both architectures place substantial mass on these positions across all three settings. To further test whether internal model computations rely on these positions, we examine what happens when we mask attention to these cells. For both Shared-head and Dedicated-heads models, we mask L1 attention to routing cells or L2 attention to matching precedents at evaluation time, using an equal number of randomly selected cells as controls (Figure 3, right). Across all three settings, masking attention to the theory-predicted cells reduces cell accuracy, while the random controls have little effect. This supports the role of both the routing and matching stages in the trained models’ predictions. Do trained models exhibit the predicted layerwise structure? We train linear probes on frozen post-residual representations after embedding, L1 attention, L1 MLP, L2 attention, and L2 MLP. For two targets: (1) the neighborhood configuration, the k-cell neighborhood that determines the next cell value; (2) the k-gram predictive distribution, the conditional distribution over the next cell value computed from causal k-gram counts in the trajectory prefix with add-one smoothing (the probe minimizes DKL(qkgram∥qprobe)D_KL(q_kgram\|q_probe)). Probe training, validation, and test rules are disjoint. The constructions make the configuration linearly readable after the L1 MLP in Shared-head models and after L1 attention in Dedicated-heads models, and the predictive distribution after L2 attention in both via the simplex readout. Our logistic probes are an empirical diagnostic of this structure, and both architectures match it across all three settings (Figure 4). Figure 5 visualizes the layerwise structure identified by probes, using t-SNE on the Shared-head model on deterministic 1D V=2,k=3V=2,k=3. After L1 MLP, representations cluster by neighborhood configuration; after L2 attention, by output value. Figure 4: Linear probe results. Higher is better. The configuration probe measures classification accuracy for the k-cell neighborhood; the k-gram predictive probe measures 1−DKL(qkgram∥qprobe)¯/DKL(qkgram∥Uniform)1- D_KL(q_kgram\|q_probe)\,/\,D_KL(q_kgram\|Uniform), which the axis label abbreviates as 1−KLprobe/KLuniform1-KL_probe/KL_uniform. Solid lines: deterministic; dashed: stochastic. Vertical lines mark the stage at which the theoretical construction places each target. Figure 5: t-SNE visualization of frozen representations from the Shared-head model on deterministic 1D V=2,k=3V=2,k=3. Top row (colored by neighborhood configuration): configurations cluster after the L1 MLP. Bottom row (colored by output value): outputs cluster after L2 attention. 6 Conclusion We studied how transformers perform in-context learning when the dependencies required for prediction are spatial. We introduced the spatial induction head, a two-layer gather-and-match circuit in which the first layer assembles the relevant spatial context from a serialized sequence and the second matches that context against precedent to predict the next state. We gave two explicit realizations of the gather and showed that the positional width required for spatial routing depends only on the local neighborhood and spatial dimension, not on the total grid volume or trajectory horizon. We further showed that the matching computation realizes Bayesian counting: the end-to-end circuit can approach the Bayes posterior predictive arbitrarily closely for stochastic rules and predicts exactly for deterministic rules. Experiments on 1D and 2D cellular automata demonstrate generalization to held-out rules and provide mechanistic evidence consistent with the gather-and-match computation. Our analysis focuses on cellular automata, whose finite-state local dynamics provide a particularly tractable setting for isolating spatial induction. More broadly, by separating spatial routing from precedent matching, our construction provides a framework for understanding induction mechanisms in more general types of data with spatial structure. Acknowledgments We thank Kilian Weinberger for his support. S.D. was partly supported by NSF CCF-2312774, NSF OAC-2311521, NSF IIS-2442137, and an AI2050 Early Career Fellowship program at Schmidt Sciences. This work was also supported by the National Science Foundation (NSF) through the AI Research Institutes program Award No. DMR-2433348. References Ahn et al. (2023) Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to implement preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36:45614–45650, 2023. Bachmann et al. (2025) Roman Bachmann, Jesse Allardice, David Mizrahi, Enrico Fini, Oğuzhan Fatih Kar, Elmira Amirloo, Alaaeldin El-Nouby, Amir Zamir, and Afshin Dehghan. FlexTok: Resampling images into 1D token sequences of flexible length. In Forty-second International Conference on Machine Learning, 2025. Berkovich et al. (2025) Jaime A Berkovich, Noah S David, and Markus J Buehler. AutomataGPT: Forecasting and ruleset inference for two-dimensional cellular automata. arXiv preprint arXiv:2506.17333, 2025. Bi et al. (2023) Kaifeng Bi, Lingxi Xie, Hengheng Zhang, Xin Chen, Xiaotao Gu, and Qi Tian. Accurate medium-range global weather forecasting with 3D neural networks. Nature, 619(7970):533–538, 2023. Bietti et al. (2023) Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of a transformer: A memory viewpoint. Advances in Neural Information Processing Systems, 36:1560–1588, 2023. Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020. Burtsev (2024) Mikhail Burtsev. Learning elementary cellular automata with transformers. arXiv preprint arXiv:2412.01417, 2024. Cole et al. (2025) Frank Cole, Yulong Lu, Tianhao Zhang, and Yuxuan Zhao. In-context learning of linear dynamical systems with transformers: Error bounds and depth-separation. arXiv preprint arXiv:2502.08136, 3(7), 2025. Conmy et al. (2023) Arthur Conmy, Augustine Mavor-Parker, Aengus Lynch, Stefan Heimersheim, and Adrià Garriga-Alonso. Towards automated circuit discovery for mechanistic interpretability. Advances in Neural Information Processing Systems, 36:16318–16352, 2023. Dai et al. (2025) Yijia Dai, Zhaolin Gao, Yahya Sattar, Sarah Dean, and Jennifer Sun. Pre-trained large language models learn to predict hidden Markov models in-context. Advances in Neural Information Processing Systems, 38:28877–28923, 2025. Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. Edelman et al. (2024) Ezra Edelman, Nikolaos Tsilivis, Benjamin L Edelman, Eran Malach, and Surbhi Goel. The evolution of statistical induction heads: In-context learning Markov chains. Advances in neural information processing systems, 37:64273–64311, 2024. Ekbote et al. (2025) Chanakya Ekbote, Ashok Vardhan Makkuva, Marco Bondaschi, Nived Rajaraman, Michael Gastpar, Jason Lee, and Paul Liang. What one cannot, two can: Two-layer transformers provably represent induction heads on any-order Markov chains. Advances in Neural Information Processing Systems, 38:37523–37603, 2025. Elhage et al. (2021) Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. A mathematical framework for transformer circuits. Transformer Circuits Thread, 1(1):12, 2021. Fernández et al. (2018) Roberto Fernández, Pierre-Yves Louis, and Francesca R Nardi. Overview: PCA models and issues. Probabilistic Cellular Automata: theory, applications and future perspectives, p. 1–30, 2018. Gardner (1970) Martin Gardner. Mathematical games: The fantastic combinations of John Conway’s new solitaire game “life”. Scientific American, 223(4):120–123, 1970. Giannou et al. (2024) Angeliki Giannou, Liu Yang, Tianhao Wang, Dimitris Papailiopoulos, and Jason D Lee. How well can transformers emulate in-context Newton’s method? arXiv preprint arXiv:2403.03183, 2024. Hajnal (1970) András Hajnal. Proof of a conjecture of P. Erdős. Combin. Theory Appl., 2:601, 1970. Lam et al. (2023) Remi Lam, Alvaro Sanchez-Gonzalez, Matthew Willson, Peter Wirnsberger, Meire Fortunato, Ferran Alet, Suman Ravuri, Timo Ewalds, Zach Eaton-Rosen, Weihua Hu, et al. Learning skillful medium-range global weather forecasting. Science, 382(6677):1416–1421, 2023. Langton (1990) Chris G Langton. Computation at the edge of chaos: Phase transitions and emergent computation. Physica D: nonlinear phenomena, 42(1-3):12–37, 1990. Li et al. (2024) Tianhong Li, Yonglong Tian, He Li, Mingyang Deng, and Kaiming He. Autoregressive image generation without vector quantization. Advances in Neural Information Processing Systems, 37:56424–56445, 2024. Liu et al. (2022) Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022. Liu et al. (2024) Toni JB Liu, Nicolas Boullé, Raphaël Sarfati, and Christopher Earls. LLMs learn governing principles of dynamical systems, revealing an in-context neural scaling law. In Proceedings of the 2024 conference on empirical methods in natural language processing, p. 15097–15117, 2024. Makkuva et al. (2024a) Ashok V Makkuva, Marco Bondaschi, Chanakya Ekbote, Adway Girish, Alliot Nagle, Hyeji Kim, and Michael Gastpar. Local to global: Learning dynamics and effect of initialization for transformers. Advances in Neural Information Processing Systems, 37:86243–86308, 2024a. Makkuva et al. (2024b) Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish, Alliot Nagle, Martin Jaggi, Hyeji Kim, and Michael Gastpar. Attention with Markov: A framework for principled analysis of transformers via Markov chains. arXiv preprint arXiv:2402.04161, 2024b. Müller et al. (2021) Samuel Müller, Noah Hollmann, Sebastian Pineda Arango, Josif Grabocka, and Frank Hutter. Transformers can do Bayesian inference. arXiv preprint arXiv:2112.10510, 2021. Nichani et al. (2024) Eshaan Nichani, Alex Damian, and Jason D Lee. How transformers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14735, 2024. Olsson et al. (2022) Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209.11895, 2022. Press et al. (2021) Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108.12409, 2021. Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1–67, 2020. Rajaraman et al. (2024) Nived Rajaraman, Marco Bondaschi, Kannan Ramchandran, Michael Gastpar, and Ashok V Makkuva. Transformers on Markov data: Constant depth suffices. Advances in Neural Information Processing Systems, 37:137521–137556, 2024. Su et al. (2024) Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. RoFormer: Enhanced transformer with rotary position embedding. Neurocomputing, 568:127063, 2024. Terras (1999) Audrey Terras. Fourier analysis on finite groups and applications. Number 43 in London Mathematical Society Student Texts. Cambridge University Press, 1999. Vafa et al. (2024) Keyon Vafa, Justin Y Chen, Ashesh Rambachan, Jon Kleinberg, and Sendhil Mullainathan. Evaluating the world model implicit in a generative model. Advances in Neural Information Processing Systems, 37:26941–26975, 2024. Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. Von Oswald et al. (2023) Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, Joao Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, p. 35151–35174. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/v202/von-oswald23a.html. Wei et al. (2022) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682, 2022. Wolfram (1983) Stephen Wolfram. Statistical mechanics of cellular automata. Rev. Mod. Phys., 55:601–644, Jul 1983. doi: 10.1103/RevModPhys.55.601. URL https://link.aps.org/doi/10.1103/RevModPhys.55.601. Xie et al. (2021) Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit Bayesian inference. arXiv preprint arXiv:2111.02080, 2021. Yu et al. (2025) Qihang Yu, Ju He, Xueqing Deng, Xiaohui Shen, and Liang-Chieh Chen. Randomized autoregressive visual generation. In 2025 IEEE/CVF International Conference on Computer Vision (ICCV), p. 18431–18441. IEEE, 2025. Zhang et al. (2024) Ruiqi Zhang, Spencer Frei, and Peter L Bartlett. Trained transformers learn linear models in-context. Journal of Machine Learning Research, 25(49):1–55, 2024. Appendix contents 1 Introduction 2 Related work 3 The task and the routing problem 3.1 Cellular automata 3.2 Sequence flattening and spatial routing 3.3 The model 3.4 Resolvable queries and the Bayes target 4 Spatial Induction Heads: Construction and Optimality 4.1 The spatial induction head 4.2 Two constructions of the gather 4.3 Matching and Bayes-optimal prediction 5 Experiments 5.1 Experimental setup 5.2 Results 6 Conclusion References A Roadmap and reading paths B Notation and conventions B.1 Conventions B.2 Symbols B.3 Overloaded notation B.4 The experimental settings C Serialization and limits of sequence-relative routing C.1 Formal serialization and indexing C.2 Boundary and separator queries C.3 Limits of displacement-only positional biases D Coverage and Bayes-optimal prediction D.1 Coverage and resolvable queries D.2 Bayes-optimal posterior prediction E Spatial addressing with grid-independent width E.1 Fourier representation of spatial attention scores E.2 Isolating a set of offsets E.3 Attention concentration from a score gap E.4 Selecting spatial offsets in the preceding time step E.5 Example: addressing the 2D von Neumann routing set F Colorings for Shared-head decoding F.1 Admissible colorings and the Cayley graph F.2 Bounds on the number of colors F.3 Colorings for the experimental grids F.4 Coloring interface for Shared-head decoding G Layer 1: spatial gather constructions G.1 Target representation and residual-stream layout G.2 Separator gating and finite-softmax error G.3 Construction I: One head per offset G.4 Construction I: A shared head with MLP decoding G.5 The spatial gather interface G.6 Construction sizes for the experimental settings H Layer 2: Bayesian matching and end-to-end guarantees H.1 The configuration-matching head H.2 Exact counting and Dirichlet smoothing H.3 Separation of matches from non-matches H.4 Matched-score dispersion and predictive error H.5 The key-validity gate H.6 End-to-end spatial induction H.7 Choosing finite parameters I Experimental methods and additional results I.1 Data generation and rule splits I.2 Models and training I.3 Evaluation protocol and metrics I.4 Full predictive results I.5 Attention-alignment analysis I.6 Attention ablation I.7 Layerwise probe protocol I.8 Representation visualizations with t-SNE I.9 Qualitative rollout setup for Figure Appendix A Roadmap and reading paths The appendices are organized thematically. Part I formalizes the task, detailing grid serialization, prediction correctness, and the limitations of standard positional schemes. Part I establishes grid-based mathematical foundations, yielding two interface corollaries. Parts I and IV describe Layers 1 and 2 of the architecture, respectively. Part V outlines experimental methods. • Notation (Appendix B). Symbol reference and running example. • Serialization and limits of sequence-relative routing (Appendix C), Part I. Formalizes flattening (Section 3.2) and separator functions. Proves that sequence-relative biases (Definition C.5) cannot route local neighborhoods on a torus in a single layer, motivating the spatial addressing in Part I. • Coverage and Bayes-optimal prediction (Appendix D), Part I. Defines resolvable queries and the optimal predictor for empirical accuracy. • Spatial addressing with grid-independent width (Appendix E), Part I. Demonstrates that O(||dlog||)O( d ) coordinates suffice to score routing cells at offsets U above other visible keys, independent of grid size. • Colorings for Shared-head decoding (Appendix F), Part I. Formulates an injective grid labeling scheme for translates z+z+U, corresponding to a Cayley graph proper coloring. • Layer 1: spatial gather constructions (Appendix G), Part I. Details the forward pass, residual stream, and weights. Gathers are performed using either || Dedicated-heads or a single Shared-head with a separating MLP. • Layer 2: Bayesian matching and end-to-end guarantees (Appendix H), Part IV. Constructs the matching mechanism. Shows that softmax over an equally scored set implements a counter, yielding the Bayes predictive distribution. Bounds the required separation Δ against Layer 1’s dispersion error η. • Experimental methods and additional results (Appendix I), Part V. Details data generation, training, and evaluation protocols, including complete metric tables and mechanistic analyses. Table 2: Dependencies between construction stages. Stage result Downstream usage Corollary E.6 Positional features for offset selection in previous time steps Corollary F.5 Distinct color slots and storage costs (Construction I) Corollary G.12 State blocks (approximate or exact) per routed offset Theorem H.2 Equal-weight matching for empirical counts and Dirichlet smoothing Lemmas H.3, H.5, H.6 Bounds on separation, dispersion, and predictive cost Theorem H.9 Finite-parameter prediction guarantee Reading paths. The shortest sequence comprising the main result involves six statements. Read the Appendix G introduction, followed by the two gather theorems (Theorems G.9 and G.10) and their Layer 2 interface (Corollary G.12). Continue to the Appendix H introduction, the counting identity (Theorem H.2), and the end-to-end guarantee (Theorem H.9). Two prerequisites are referenced on demand: Corollary E.6 (positional addressing) and Corollary F.5 (colorings for Theorem G.10). Suggested reading paths by topic: • Circuit construction: Appendices G and H (Parts I and IV). • Mathematical foundations: Part I. • Formal problem setting: Part I. • Symbol reference: Appendix B. Appendix B Notation and conventions This section catalogs symbols defined throughout the text; Table 3 provides their definitions and points of introduction. Section B.3 clarifies overloaded symbols, and Section B.4 instantiates task parameters for the three experimental settings. B.1 Conventions Coordinates, states, time steps, sequence positions, and residual blocks (B0,…,B4B_0,…,B_4) are 00-indexed; dimensions, offsets, and heads are 11-indexed. Let [n]≔0,…,n−1[n] \0,…,n-1\. Grid coordinate arithmetic is modulo the respective side length, making G a torus such that z+δz+δ always identifies a valid cell. Grid side lengths are denoted W1,…,WdW_1,…,W_d, and its volume is ||=∏jWj = _jW_j. A row designates an innermost-axis grid row, comprising the WdW_d cells followed by a ROW_SEP. A time step t corresponds to one automaton layer; a query at step t accesses step t−1t-1. The term row strictly retains its spatial meaning. Vectors are column vectors. The notation |⋅| · denotes set cardinality or the distance to 00 for group elements. The one-hot vector for coordinate v is eve_v; for a state x, this is written e(x)e(x) to distinguish it from the dual-group generators e1,…,ede_1,…,e_d. B.2 Symbols Table 3: Symbols, and where each is fixed. symbol meaning fixed at Grid and dual group d number of spatial dimensions Def. 1 WjW_j side length of axis j Def. 1 WmaxW_ largest side length, maxjWj _jW_j Lem. E.3 G, || the torus [W1]×⋯×[Wd][W_1]×·s×[W_d]; its volume ∏jWj _jW_j Def. 1 z, zjz_j, δ a cell of G; its j-th coordinate; an offset Def. 1 G dual group, the characters of G App. E.1 ω, eje_j a character; the j-th generator of G App. E.1 φω _ω, χω _ω phase 2π∑jωjδj/Wj2π _j _j _j/W_j; the character eiφωe^i _ω App. E.1 suppg^supp g spectrum of g, the ω with g^(ω)≠0 g(ω)≠ 0 App. E.1 States, rules and the prior S, V state set [V][V], and its size Def. 1 T, t horizon; a time step Def. 1 T0T_0 context length, the number of time steps shown before scoring begins §5 (t,z)(t,z) the cell z at step t Def. 1 xt,zx_t,z state of cell z at step t Def. 1 f the local kernel k→ΔV−1S^k→ ^V-1 Def. 1 α Dirichlet concentration of the prior on f Def. 1 Pt,zP_t,z parent configuration of (t,z)(t,z) Def. 1 Qt,zQ_t,z query configuration, Pt,z+u^dP_t,z+ u_d Def. 4 c a matching configuration: an earlier Pt′,z′P_t ,z equal to Qt,zQ_t,z; its cell is a matching precedent Def. 4 P^α P_α Bayes posterior predictive Thm. 3 Neighborhood and routing (δ1,…,δkCLOSE( _1,…, _k), k the neighborhood, a list of distinct offsets, and its size Def. 1 DKD_K, DQD_Q key offsets; query offsets DK+u^dD_K+ u_d Def. 1, 2 u^d u_d successor offset, the d-th coordinate vector Def. C.1 U routing set DK∪DQD_K∪ D_Q; the cells at these offsets are the routing cells Def. 2 N a generic set of offsets to be isolated Thm. E.4 Serialization ρ _G, r(z)r(z) row-major index of z; its row Def. C.1 ρ(t,z)ρ(t,z) sequence position of the cell (t,z)(t,z) Def. C.1 N stream length T(||+||/Wd)T( + /W_d) Def. C.1 n, n′n a query position; a key position §3.3 τ(n)τ(n), κ(n)κ(n) virtual time step and virtual cell of position n App. C.1 query cell a cell token which poses a query Def. 2 target cell the cell κ(n)+u^dκ(n)+ u_d which n predicts Lem. C.2 ROW_SEP separator closing an innermost row Def. C.1 TIME_SEP separator closing a time step Def. C.1 The model WEW_E, ene_n, P, pnp_n token embedding; one-hot of the token at n; positional table; its column n §3.3 WQ(l),WK(l),WV(l)W_Q^(l),W_K^(l),W_V^(l) query, key and value projections at layer l §3.3 g, γ the positional kernel on G; its isolation margin Def. E.2 Λ Layer-1 logit scale Cor. E.5 Γ1 _1 Layer-1 separator gate strength Prop. G.6 Γ2 _2 Layer-2 key-validity gate strength Prop. H.7 νn _n key-validity indicator sn+ζns_n+ _n Def. H.1 β Layer-2 query scaling Def. H.1 Widths dmodeld_model residual-stream width §3.3 dpd_p width of the positional table, dS+3d_S+3 for Construction I Def. G.2 dSd_S addressing dimension, |suppg^∖0| g \0\ §E.1 dMLPd_MLP hidden width of the Layer-1 MLP §3.3 Residual blocks and projections B0B_0 separator indicator, auxiliary-token marker, and the constant 11 Def. G.2 μn _n auxiliary-token marker [n=⋆]1[n= ], a coordinate of B0B_0 Def. G.2 σ⋆ _ Layer-2 score of the auxiliary token ⋆ Def. H.1 B1B_1 own state one-hot e(xt,z)e(x_t,z) Def. G.2 B2B_2 positional table entry pt,zp_t,z Def. G.2 ζn _n initial-step indicator [τ(n)=0]1[τ(n)=0], a coordinate of B2B_2 Def. G.2 B2colB_2^col own-color block of B2B_2, zero at separators Def. G.2 B3B_3 pattern scratch, B3pat⊕B3aggB_3^pat B_3^agg Def. G.2 B4B_4 output slot, written by Layer 2 Def. G.2 ΠBr _B_r projection onto block BrB_r Def. G.2 ιδ _δ embedding of ℝVR^V into block δ of B3patB_3^pat Thm. G.9 ΣQ _Q, ΣK _K Layer-2 selection projections onto ℝkVR^kV Def. H.1 Coloring c a coloring →[M]G→[M] Def. F.1 M number of colors used Def. F.1 M⋆M chromatic number of Γ _U Def. F.1 Γ _U Cayley graph on (−)∖0(U-U) \0\ Def. F.1 χ, K, MKM_K periodic coloring; its subgroup; its color count |/K| /K Def. F.1, Lem. F.2 nmaxn_ most visible cells sharing one color Thm. G.10 Budgets, gaps and counts ε¯ per-block error, the routing budget Def. G.1; discharged by Lem. G.8 εret _ret retrieval error at score gap Δ Cor. H.4 Δ Layer-2 separation β(1−(2k+2)ε¯)β(1-(2k+2) ), the gap between matching and non-matching keys Lem. H.3 η dispersion within the matched set, 2βkε¯2β k Lem. H.5 κ divergence budget of the main theorem Thm. H.9 DKLD_KL Kullback–Leibler divergence Thm. 9 ncn_c, nc,yn_c,y times c has been seen; times it was followed by y Def. 4 ℳt,zM_t,z the matched set §H.1 B.3 Overloaded notation This work integrates harmonic analysis on finite abelian groups, graph coloring, and transformer architectures. To adhere to established conventions in these fields, eight symbols are overloaded. The surrounding context unambiguously determines the active definition, and no single equation mixes distinct definitions of the same symbol. symbol readings c a configuration in kS^k (Def. 4); a coloring →[M]G→[M] (Def. F.1). κ the virtual cell index κ(n)κ(n), always applied to a position (App. C.1); the divergence budget κ∈(0,1]κ∈(0,1], always bare (Thm. H.9). B a residual block B0,…,B4B_0,…,B_4, always subscripted (Def. G.2); the bounding box of a target set (Lem. E.3); the MLP gate constant Bδ=GδB_δ=G_δ of (40), subscripted by an offset. P the positional table (§3.3); the parent configuration Pt,zP_t,z (Def. 1); the axis factor PjP_j of a box kernel (Lem. E.3). Q the bilinear form realizing a kernel (Lem. E.1); the box kernel Q=∑jPjQ= _jP_j (Lem. E.3); the query configuration Qt,zQ_t,z (Def. 4). M the number of colors of an admissible coloring (Def. F.1), subscripted MKM_K for a periodic one and starred M⋆M for the chromatic number; the score matrix in the proof of Lem. E.1, in an appendix which never colors anything; the matched set ℳt,zM_t,z, calligraphic and subscripted (§H.1). Δ the logit separation (Lem. H.3); the simplex ΔV−1 ^V-1, always superscripted (Def. 1); the maximum degree in the Hajnal–Szemerédi bound (proof of Lem. F.3). G the spatiotemporal kernel G(δ,s)G(δ,s), always applied to an offset and a step displacement (proof of Cor. E.6, Stage 6); the grid G and the Cayley graph Γ _U, both distinguished by font; the MLP gain GδG_δ, always subscripted (proof of Thm. G.10). Additionally, α denotes the Dirichlet concentration (Definition 1), except when written as αn,n′(l)α^(l)_n,n , where it represents the attention weight (§3.3) with a layer superscript and positional subscripts. B.4 The experimental settings The experiments (Appendix I) cover three neighborhood types: binary 11D (V=2,k=3V=2,k=3), ternary 11D (V=3,k=3V=3,k=3), and binary 22D von Neumann (V=2,k=5V=2,k=5). Table 4 specifies the deterministic instances considered below, on ℤ16Z_16, ℤ32Z_32, and ℤ62Z_6^2, respectively. The stochastic experiments use the same neighborhood types but have different task parameters where indicated in Table 10; in particular, the stochastic ternary 11D setting uses ℤ16Z_16. Table 6 gives the colorings for the instances in Table 4 alongside the bounds from Appendix F. Table 8 (Appendix G) details the widths and scales required by the two constructions. Table 4: The three experimental settings as tasks. 1D, V=2V=2 1D, V=3V=3 2D von Neumann G ℤ16Z_16 ℤ32Z_32 ℤ62Z_6^2 d, WmaxW_ , || 11, 1616, 1616 11, 3232, 3232 22, 66, 3636 V, T 22, 1010 33, 1212 22, 1212 DKD_K, k −1,0,1\-1,0,1\, 33 −1,0,1\-1,0,1\, 33 von Neumann, 55 u^d u_d, || 11, 44 11, 44 (0,1)(0,1), 88 tokens per step, N 1717, 170170 3333, 396396 4242, 504504 Part I — The task Appendix C Serialization and limits of sequence-relative routing This section comprises three parts. Section C.1 specifies the mapping from cells to sequence positions, extending it to separators via a virtual cell index. Section C.2 addresses boundary conditions introduced by row separators. Section C.3 proves that sequence-relative positional biases cannot strictly isolate required routing cells. Appendix E constructs an absolute positional table for spatial addressing. C.1 Formal serialization and indexing Definition C.1 (Row-terminated serialization). Cells are emitted in row-major order: ρ(z)≔∑j=1dzj∏l>jWl∈[||],r(z)≔⌊ρ(z)/Wd⌋∈[||/Wd]. _G(z)\; \; _j=1^dz_j _l>jW_l\;∈\;[ ], r(z)\; \; _G(z)/W_d \;∈\;[ /W_d]. Here, ρ(z) _G(z) is the flattened grid index of cell z, and r(z)r(z) is the global index of the innermost row containing z, such that ρ(z)=r(z)Wd+zd _G(z)=r(z)W_d+z_d. Let u^d≔(0,…,0,1)∈ u_d\; \;(0,…,0,1) denote the successor offset, which corresponds to advancing one position within a row. Every innermost row concludes with a separator: a TIME_SEP for the final row of a time step, and a ROW_SEP otherwise. Letting (r,c)(r,c) denote the cell in row r with last coordinate c, one time step is serialized as: xt,(0,0),…,xt,(0,Wd−1)⏟row 0,ROW_SEP,…,xt,(m,0),…,xt,(m,Wd−1)⏟row m=||/Wd−1,TIME_SEP⏟||+||/Wd tokens. x_t,(0,0),\,…,\,x_t,(0,W_d-1)_row 0,\; ROW\_SEP,\;…,\; x_t,(m,0),\,…,\,x_t,(m,W_d-1)_row m= /W_d-1,\; TIME\_SEP_ + /W_d tokens. (1) The complete stream comprises (1) for t=0,…,T−1t=0,…,T-1, with total length N≔T(||+||/Wd).N\; \;T( + /W_d). The cell (t,z)(t,z) occupies sequence position ρ(t,z)=t(||+||/Wd)+ρ(z)+r(z),ρ(t,z)\;=\;t( + /W_d)+ _G(z)+r(z), (2) where the terms represent tokens in prior time steps, preceding cells in the current step, and preceding row separators. The map ρ:[T]×→[N]ρ:[T]×G→[N] is thus an order-preserving injection. Example (One dimension). In d=1d=1, each time step is one row, so r(z)=0r(z)=0 and ||/Wd=1 /W_d=1. Writing W=W1W=W_1, one time step is W cell tokens followed by one TIME_SEP, and u^d=1,ρ(t,z)=(W+1)t+z. u_d=1, ρ(t,z)=(W+1)t+z. Example (Two dimensions). In d=2d=2, with grid dimensions W1×W2W_1× W_2, the innermost row length is W2W_2. For a cell at z=(z1,z2)z=(z_1,z_2): ρ(z)=z1W2+z2,r(z)=z1. _G(z)=z_1W_2+z_2, r(z)=z_1. Here, r(z)r(z) extracts the row coordinate z1z_1. One time step contains W1W_1 rows of length W2W_2, requiring W1W_1 separators. The sequence position is therefore: ρ(t,z)=t(W1W2+W1)+(z1W2+z2)+z1.ρ(t,z)=t(W_1W_2+W_1)+(z_1W_2+z_2)+z_1. Causal masking. The model employs a standard causal mask; a query at sequence position n attends only to positions n′≤n ≤ n. For cell tokens, (t′,z′)(t ,z ) is visible to (t,z)(t,z) if and only if ρ(t′,z′)≤ρ(t,z)ρ(t ,z )≤ρ(t,z). Virtual cell index. We assign a virtual spatial index and time step to every sequence position except the final TIME_SEP. For a cell token n=ρ(t,z)n=ρ(t,z), define (τ(n),κ(n))≔(t,z).(τ(n),κ(n)) (t,z). For a separator n whose successor cell at n+1n+1 is (t′,z′)(t ,z ), define (τ(n),κ(n))≔(t′,z′−u^d).(τ(n),κ(n)) (t ,z - u_d). Thus, a ROW_SEP inherits its row’s time step, while a TIME_SEP assumes the subsequent time step. The final TIME_SEP, at n=N−1n=N-1, has no successor cell, so τ(N−1)τ(N-1) and κ(N−1)κ(N-1) are left undefined. It poses no query, and as the last position it is visible as a key only to itself. We therefore exclude it from every requirement below which quantifies over virtual addresses, including the gather, and give its column of the positional table arbitrary features; no scored prediction depends on it. Lemma C.2 (Constant successor offset). Under Definition C.1, a cell token (t,z)(t,z) is followed by a cell token exactly when zd<Wd−1z_d<W_d-1, in which case that successor is (t,z+u^d)(t,z+ u_d). Every separator other than the final TIME_SEP is also followed by a cell token. Whenever position n is followed by a cell token, that token, which we call the target cell of n, is (τ(n),κ(n)+u^d).(τ(n),κ(n)+ u_d). Hence every position which predicts a cell does so at the same spatial offset u^d u_d from its virtual cell index. Proof. Within an innermost row, a non-final cell z is followed by z+u^dz+ u_d, and a row-final cell by its separator. Non-final separators are followed by the first cell of the subsequent row or time step. For a separator with successor (t′,z′)(t ,z ), the virtual index yields τ(n)=t′τ(n)=t and κ(n)=z′−u^dκ(n)=z - u_d; its target remains κ(n)+u^d=z′κ(n)+ u_d=z . ∎ Remark (Size of the routing set). Because =DK∪(DK+u^d)U=D_K∪(D_K+ u_d) is a union of two sets of size k, and because the offsets are distinct modulo (W1,…,Wd)(W_1,…,W_d) by Definition 1, k≤||≤min(2k,||),k\;≤\; \;≤\; (2k, ), which is the bound quoted in §3.2. The lower bound is attained exactly when DK+u^d=DKD_K+ u_d=D_K, in which case =DKU=D_K. This degenerate case is possible: on ℤ32Z_3^2 with DK=(0,0),(0,1),(0,2)D_K=\(0,0),(0,1),(0,2)\ and u^d=(0,1) u_d=(0,1), translation by u^d u_d permutes DKD_K, so k=||=3k= =3. It requires DKD_K to be a union of cosets of ⟨u^d⟩ u_d , and so to wrap the innermost axis completely; every neighborhood we consider has ||≥k+1 ≥ k+1. C.2 Boundary and separator queries Serialization introduces two boundary cases: a row-final cell (zd=Wd−1z_d=W_d-1) predicts a separator, and a separator predicts the first cell of the next row. These cases, fixed by emission order, are summarized in Table 5. Table 5: Prediction duties under Definition C.1. For a non-row-final cell and for a separator, the predicted token is a cell and its spatial location is expressed through the constant successor offset u^d u_d. A row-final cell instead predicts a separator whose identity is fixed by position. token predicts spatial target cell (t,z)(t,z), zd<Wd−1z_d<W_d-1 cell (t,z+u^d)(t,z+ u_d) z+u^dz+ u_d cell (t,z)(t,z), zd=Wd−1z_d=W_d-1 a separator none separator first cell of the next row κ(n)+u^dκ(n)+ u_d Lemma C.3 (Row-final targets are fixed by position). Let n=ρ(t,z)n=ρ(t,z) hold a cell token with zd=Wd−1z_d=W_d-1 and n<N−1n<N-1. Then the token at n+1n+1 is a TIME_SEP if r(z)=||/Wd−1r(z)= /W_d-1 and a ROW_SEP otherwise. In particular, conditioned on the position n, the next token is deterministic and independent of the cellular-automaton kernel f. Proof. The emission order is fixed before any cell state is drawn. Every innermost row is followed by exactly one separator, and the separator is a TIME_SEP exactly for the last row of a time step. Equation (2) therefore determines the next token type from n alone. ∎ The experimental evaluation (Section 5) scores cell-value targets, excluding separators. Scored predictions include both non-row-final cell queries and separator queries targeting the prediction region. Row-final cell tokens (fraction 1/Wd1/W_d) predict separators whose identities are positionally fixed and independent of the rule f. However, they remain valid keys for Layer 2, as their states are valid observations of f (Remark G.5). The remaining case is a separator followed by a cell. We chose the virtual index so that this case has the same spatial target convention as an ordinary query. Lemma C.4 (Separator queries). Let n hold a separator with n<N−1n<N-1, and let (t′,z′)(t ,z ) be the cell token at n+1n+1. (i) If n is a ROW_SEP closing row r of time step t, then t′=t =t, r(z′)=r+1r(z )=r+1, and zd′=0z _d=0. If n is a TIME_SEP closing time step t, then (t′,z′)=(t+1,0)(t ,z )=(t+1,0). In either case, τ(n)=t′,κ(n)=z′−u^d,κ(n)+u^d=z′.τ(n)=t , κ(n)=z - u_d, κ(n)+ u_d=z . (i) If t′≥1t ≥ 1, then every cell in time step t′−1=τ(n)−1t -1=τ(n)-1 precedes n in the stream. Hence all k parents of the target cell z′z are causally visible when the separator predicts it. (i) If t′≥1t ≥ 1, the parents of z′z occur at offsets DKD_K from z′z , equivalently at offsets DK+u^d=DQ⊆D_K+ u_d=D_Q from the virtual index κ(n)κ(n). Thus separator queries whose targets are CA-generated cells require no spatial offsets beyond the routing set already defined in Definition 2. Proof. For part (i), the token following the separator of row r is the first cell of row r+1r+1, while the token following a TIME_SEP is the first cell of the next time step. The identities involving (τ,κ)(τ,κ) then follow from the definition of the virtual index. For part (i), if n is a ROW_SEP, then t′=t =t, and all of time step t−1t-1 occurs before every token of time step t. If n is a TIME_SEP, then t′=t+1t =t+1, and every cell of time step t appears before its closing separator. The condition t′≥1t ≥ 1 excludes separators inside the initial condition, whose successor cells have no CA parents. For part (i), when t′≥1t ≥ 1, the parent set of the target z′=κ(n)+u^dz =κ(n)+ u_d is z′+DK=κ(n)+(DK+u^d)=κ(n)+DQz +D_K=κ(n)+(D_K+ u_d)=κ(n)+D_Q. ∎ The two separator types differ only in how their stream position relates to the target time step: a ROW_SEP predicts a cell in its own time step (reading parents from t−1t-1), whereas a TIME_SEP predicts the first cell of the next step (reading parents from t). Indexing by τ unifies these cases. Initial-condition separators predicting initial states fall outside the transition-prediction task. The transformer constructions (Appendix G) use separators as queries when predicting CA cells, gating them out as keys via token content; this requires no extra spatial offsets or positional coordinates. C.3 Limits of displacement-only positional biases In this section, we bound what a positional bias depending only on sequence displacement can do. No fixed scalar bias scores every desired routing cell strictly above all other causally visible cells at every query position; periodic wraparound prevents this one-layer isolation (Theorem C.6). The absolute positional table (Section 3.3) lacks an explicit coordinate system, requiring spatial structure to be learned from data. A simpler alternative is a scalar additive bias depending solely on sequence displacement (Raffel et al., 2020; Press et al., 2021). On an open grid, a fixed spatial offset yields a constant sequence displacement between any two valid cells, provided no boundary truncation or padding changes the row length. On a torus, wraparound disrupts this consistency. Theorem C.6 identifies two queries where conflicting displacements prevent any fixed displacement-only bias from isolating the desired cells. For the formulas below, write R≔Wd+1,S≔(||/Wd)R,r(z)≔∑j<dzj∏j<l<dWl.R W_d+1, S ( /W_d)R, r(z) _j<dz_j _j<l<dW_l. Here R is the row stride, S is the time-step stride, and r(z)r(z) agrees with Definition C.1. Equation (2) becomes ρ(t,z)=tS+r(z)R+zd.ρ(t,z)=tS+r(z)R+z_d. (3) Definition C.5 (Sequence-relative bias). A sequence-relative bias is a function b:0,…,N−1→ℝb:\0,…,N-1\ whose contribution to the attention score between a query at position n and a key at position n′≤n ≤ n depends only on the displacement n−n′n-n . Separator keys may additionally be gated out by token content. For the isolation property below, ordinary cell keys are ranked solely by the positional score b(n−n′)b(n-n ). For a non-row-final cell query (t,z)(t,z) with 1≤t<T1≤ t<T and zd<Wd−1z_d<W_d-1, such a bias isolates an offset set H⊆H if every desired cell (t−1,z+δ)(t-1,z+δ) with δ∈Hδ∈ H receives a strictly larger positional score than every causally visible cell outside this desired set. Allowing separator keys to be gated only strengthens the class in Definition C.5. The witnesses below compare cell tokens with cell tokens and never use a separator as a competing key. Example (The elementary one-dimensional contradiction). For the elementary neighborhood, DK=−1,0,1D_K=\-1,0,1\ and =−1,0,1,2U=\-1,0,1,2\. Let W≥4W≥ 4. At the query (2,0)(2,0), the desired cell at offset −1-1 wraps to the right edge of the previous time step and lies at sequence displacement 22. The cell at displacement 2W−12W-1 is visible but lies two time steps back, so correct isolation requires b(2)>b(2W−1).b(2)>b(2W-1). At the query (t,W−2)(t,W-2), the desired cell at offset 22 wraps to the left edge of the previous time step and lies at displacement 2W−12W-1, while displacement 22 points to a visible cell in the current time step. Correct isolation now requires b(2W−1)>b(2).b(2W-1)>b(2). The two inequalities are incompatible. Theorem C.6 generalizes this argument. Remark (What the theorem does not cover). A bias which may also read the query position modulo the row stride is already grid-indexed: nmodR=zdn R=z_d on cell tokens, which exposes exactly the boundary information used by the contradiction. Standard one-dimensional rotary embeddings (Su et al., 2024) enter the logits through a position-dependent bilinear form, so they too fall outside Definition C.5 and the theorem. We do not analyze either class here. Theorem C.6 (Sequence-relative obstruction). Fix the serialization of Definition C.1 with T≥3T≥ 3. (i) Suppose d=1d=1, W≥4W≥ 4, and U contains some negative offset −m-m with 1≤m≤W−31≤ m≤ W-3 and some positive offset p with 2≤p≤W−22≤ p≤ W-2. Then no single sequence-relative bias isolates U for every query cell z<W−1z<W-1. (i) Suppose d≥2d≥ 2, Wd≥2W_d≥ 2, and some δ∈DKδ∈ D_K has a nonzero component modulo the corresponding side length on an outer axis; that is, δj≢0(modWj) _j ≡ 0 W_j for some j<dj<d. Then no partition =H1⊔⋯⊔HhU=H_1 ·s H_h together with sequence-relative biases b1,…,bhb_1,…,b_h can make each bab_a isolate HaH_a at every query. In particular, no single sequence-relative bias isolates U. Part (i) includes the elementary neighborhood by taking m=1m=1 and p=2p=2. Part (i) applies whenever the neighborhood is not confined to one innermost row, including the usual von Neumann and Moore neighborhoods in dimension at least two. The result concerns one-layer isolation in the sense of Definition C.5; it does not rule out a model which assembles the routing set through several layers or which is supplied with additional spatial information. Proof. Part (i). Write W=W1W=W_1. Then R=S=W+1R=S=W+1 and ρ(t,z)=(W+1)t+zρ(t,z)=(W+1)t+z. For a query (t,z)(t,z), the displacement to the desired cell (t−1,z+δ)(t-1,z+δ) is ρ(t,z)−ρ(t−1,z+δ)=(W+1)−δ,0≤z+δ<W,(2W+1)−δ,z+δ≥W,1−δ,z+δ<0,ρ(t,z)-ρ(t-1,z+δ)= cases(W+1)-δ,&0≤ z+δ<W,\\ (2W+1)-δ,&z+δ≥ W,\\ 1-δ,&z+δ<0, cases where the last two cases use toroidal wraparound. Take first the query (2,0)(2,0), which T≥3T≥ 3 and W≥4W≥ 4 make a non-row-final cell query in the sense of Definition C.5. The desired cell at offset −m-m wraps below and therefore lies at displacement m+1m+1. The position at displacement 2W+1−p2W+1-p is ρ(2,0)−(2W+1−p)=p+1,ρ(2,0)-(2W+1-p)=p+1, which is the visible cell (0,p+1)(0,p+1) because p≤W−2p≤ W-2. It lies in time step 00, not in the desired parent step 11, so it is not one of the routed cells. Isolation therefore requires b(m+1)>b(2W+1−p).b(m+1)>b(2W+1-p). (4) Now take the query (t,W−2)(t,W-2) for any 1≤t<T1≤ t<T, which is a non-row-final cell query because W≥4W≥ 4. The desired cell at offset p wraps above and lies at displacement 2W+1−p2W+1-p. The position at displacement m+1m+1 is ρ(t,W−2)−(m+1)=ρ(t,W−3−m),ρ(t,W-2)-(m+1)=ρ(t,W-3-m), which is a cell in the current time step because m≤W−3m≤ W-3. It precedes the query and is therefore visible, but it does not belong to the previous time step. Hence isolation requires b(2W+1−p)>b(m+1),b(2W+1-p)>b(m+1), (5) contradicting (4). This proves part (i). Part (i). Let Mrow≔||/WdM_row /W_d be the number of rows in one time step, so S=MrowRS=M_rowR, and write Pj≔∏j<l<dWl,r(z)=∑j<dzjPj.P_j _j<l<dW_l, r(z)= _j<dz_jP_j. Choose δ∈DKδ∈ D_K such that δj≢0(modWj) _j ≡ 0 W_j for some j<dj<d, and represent each coordinate by its residue δj∈0,…,Wj−1 _j∈\0,…,W_j-1\. Let i<di<d be the smallest index with δi≠0 _i≠ 0, and define C≔∑j<dδjPj,C′≔∑i<j<dδjPj,G≔WiPiR,A≔S−CR−δd.C _j<d _jP_j, C _i<j<d _jP_j, G W_iP_iR, A S-CR- _d. Because i is the first nonzero outer coordinate, mixed-radix bounds give C′<PiC <P_i and hence Pi≤C<WiPi≤Mrow.P_i≤ C<W_iP_i≤ M_row. Consider first the query (2,0)(2,0), which T≥3T≥ 3 and Wd≥2W_d≥ 2 make a non-row-final cell query. The desired routed cell at offset δ is (1,δ)(1,δ), whose sequence displacement is ρ(2,0)−ρ(1,δ)=2S−(S+CR+δd)=A.ρ(2,0)-ρ(1,δ)=2S-(S+CR+ _d)=A. The position at displacement A+GA+G is 2S−A−G=S+(C−WiPi)R+δd=(Mrow+C−WiPi)R+δd.2S-A-G=S+(C-W_iP_i)R+ _d=(M_row+C-W_iP_i)R+ _d. Since 0≤Mrow+C−WiPi<Mrow0≤ M_row+C-W_iP_i<M_row, this is a cell in time step 00. It is visible, but all desired routed cells for the query lie in time step 11, so it is not a desired key. Therefore the bias assigned to any part containing δ must satisfy b(A)>b(A+G).b(A)>b(A+G). (6) For the reverse inequality, take z∗≔(W1−1,…,Wi−1−1,Wi−δi, 0,…,0)z (W_1-1,…,W_i-1-1,\,W_i- _i,\,0,…,0) at time t=1t=1. Since zd∗=0z_d =0 and Wd≥2W_d≥ 2, this is a non-row-final cell query. Since ∑j<i(Wj−1)Pj=Mrow−WiPi, _j<i(W_j-1)P_j=M_row-W_iP_i, we have r(z∗)=Mrow−δiPir(z )=M_row- _iP_i. Adding δ wraps coordinate i to zero and gives r(z∗+δ)=Mrow−WiPi+C′.r(z +δ)=M_row-W_iP_i+C . Thus the desired cell (0,z∗+δ)(0,z +δ) lies at displacement ρ(1,z∗)−ρ(0,z∗+δ) ρ(1,z )-ρ(0,z +δ) =S+(WiPi−δiPi−C′)R−δd =S+ (W_iP_i- _iP_i-C )R- _d =A+G. =A+G. By contrast, the position at displacement A is ρ(1,z∗)−A=S+C′R+δd,ρ(1,z )-A=S+C R+ _d, a cell in time step 11, in row C′C and column δd _d. It precedes the query because C′R+δd<(C′+1)R≤PiR≤(Mrow−δiPi)R,C R+ _d<(C +1)R≤ P_iR≤(M_row- _iP_i)R, and it is not a desired routed cell because the desired cells lie in time step 00. Hence the same bias must satisfy b(A+G)>b(A),b(A+G)>b(A), (7) contradicting (6). This contradiction applies to whichever partition part contains δ. Therefore no family of sequence-relative biases, one per part of a partition of U, can isolate all parts. This proves part (i). ∎ Spatial relative positions and learned routing. A spatial relative-position bias in d dimensions, augmented with temporal displacement, can avoid this obstruction. For ordinary cell tokens, such a bias can take the form bsp(t−t′,z′−z),b_sp(t-t ,\,z -z), where z′−z∈z -z is computed coordinatewise modulo (W1,…,Wd)(W_1,…,W_d). Assigning a higher score when t−t′=1t-t =1 and z′−z∈z -z than otherwise isolates the desired routing cells. The same spatial offset therefore remains identifiable across periodic boundaries. This parameterization explicitly supplies the mapping from sequence positions to spatial and temporal coordinates, together with the periodic boundary structure, even when the bias values themselves are learned. Our experimental models instead use freely learned absolute position embeddings indexed only by sequence position, without an explicit coordinate-based parameterization. The serialization and separators supply structural cues, but the model must learn how to use them for spatial routing. Our constructions establish that such routing can be represented, and our experiments provide evidence that gradient-based training learns routing behavior consistent with these constructions. Appendix D Coverage and Bayes-optimal prediction All distributional guarantees apply to resolvable queries and are measured against the Bayes-optimal predictor. Section D.1 characterizes coverage and specifies the queries excluded by resolvability, where optimal prediction relies solely on position and the prior. Section D.2 derives the Bayes-optimal predictor (Theorem 3). These results rely exclusively on Definition 1 and the serialization from Appendix C, without reference to transformer architectures. D.1 Coverage and resolvable queries We adapt Definition 4 to the serialized stream to address two issues: the parent configuration Pt,zP_t,z (Definition 1) is defined only for t≥1t≥ 1 (as the initial step is drawn independently), and the first cell of every row is predicted at a separator token (Lemma C.4), which is scored alongside interior cells (Section 5). Querying positions. A position n poses a query when it has a target cell in the sense of Lemma C.2 and that target cell lies in a time step τ(n)≥1τ(n)≥ 1. Two families qualify, and they are the first and third rows of Table 5: (a) a cell token (t,z)(t,z) with t≥1t≥ 1 and zd<Wd−1z_d<W_d-1, whose target cell is z+u^dz+ u_d in its own time step; (b) a separator at n<N−1n<N-1 with τ(n)≥1τ(n)≥ 1, whose target cell is κ(n)+u^dκ(n)+ u_d, the first cell of the next row, again in step τ(n)τ(n). In both cases the query configuration is Qn≔Pτ(n),κ(n)+u^d,Q_n\; \;P_τ(n),\,κ(n)+ u_d, which is defined because τ(n)≥1τ(n)≥ 1, and the target is a draw from f(⋅∣Qn)f(· Q_n). For a cell token this is the Qt,zQ_t,z of Definition 4. Theorem H.9 gives the separator case of the guarantee, under the same definition. Counting positions. The counts range over the cells generated by f: nc≔#(t′,z′):t′≥1,ρ(t′,z′)≤n,Pt′,z′=c,nc,y≔#those with xt′,z′=y.n_c\; \;\# \(t ,z )\;:\;t ≥ 1,\ ρ(t ,z )≤ n,\ P_t ,z =c \, n_c,y\; \;\#\those with x_t ,z =y\. (8) Above, c∈kc ^k is a configuration and n is the sequence position posing the query. We need the restriction t′≥1t ≥ 1 for two reasons: P0,z′P_0,z is undefined, and x0,z′x_0,z is an initial state, so it says nothing about the kernel. A configuration c is covered at n when nc≥1n_c≥ 1, and the query at n is resolvable when its configuration QnQ_n is covered. Coverage is a property of the stream alone, and it is monotone in position. Lemma D.1 (Coverage is monotone). Fix a trajectory and a configuration c∈kc ^k. (i) ncn_c, evaluated at (t,z)(t,z), is non-decreasing in ρ(t,z)ρ(t,z). (i) If a query posing c is resolvable at (t,z)(t,z), then every query posing c at a position (t′,z′)(t ,z ) with ρ(t′,z′)≥ρ(t,z)ρ(t ,z )≥ρ(t,z) is resolvable. (i) A query is resolvable if and only if nc≥1n_c≥ 1 for its own configuration c=Qt,zc=Q_t,z. Proof. Since ρ is an order-preserving injection (Definition C.1), the sets A(n)≔(t′,z′):t′≥1,ρ(t′,z′)≤nA(n) \(t ,z ):t ≥ 1,\ ρ(t ,z )≤ n\ form a chain under inclusion. The condition t′≥1t ≥ 1 excludes the initial time step uniformly, preserving the chain structure. Because ncn_c at (t,z)(t,z) counts elements of A(ρ(t,z))A(ρ(t,z)) with parent configuration c, it is non-decreasing along this chain, proving (i). Statement (i) follows from (i) and (i). For (i), c is covered at (t,z)(t,z) if and only if A(ρ(t,z))A(ρ(t,z)) contains an element with parent configuration c, meaning nc≥1n_c≥ 1. ∎ Part (i) gives a nonempty matched set. Both the deterministic and the stochastic analysis divide by ncn_c, so both need resolvability. Evaluating only on resolvable queries excludes three classes of cell token. Lemma D.2 (What resolvability excludes). A cell token either poses a resolvable query or falls into exactly one of the following three classes, tested in this order. (i) Initial-step cells, those with t=0t=0. Their target is a separator when zd=Wd−1z_d=W_d-1 and an initial state otherwise. The separator is determined by the position n, and the initial state is drawn from the initial-state distribution of Definition 1, so neither depends on f. (i) Row-final cells, those with t≥1t≥ 1 and zd=Wd−1z_d=W_d-1. Their target is a separator, determined by the position n alone, so its conditional law given everything observed is a point mass and carries zero mutual information with f. (i) Novel configurations, those with t≥1t≥ 1 and zd<Wd−1z_d<W_d-1 whose query configuration has nc=0n_c=0. There the Bayes posterior predictive of Theorem D.3 is the uniform distribution P^α(y∣c)=1/V P_α(y c)=1/V for every y, whatever f is. In all three classes the optimal prediction depends on the position and the prior alone, and the trajectory adds nothing. Proof. Tokens with t=0t=0 fall into class (i); those with t≥1t≥ 1 and zd=Wd−1z_d=W_d-1 into class (i); and those with t≥1t≥ 1, zd<Wd−1z_d<W_d-1, and an uncovered configuration into class (i) (Lemma D.1(i)). The three tests are applied in that order, so the classes are disjoint, and all other cell tokens pose resolvable queries. For (i), an initial-step row-final cell predicts a positionally fixed separator (Lemma C.3) and every other initial-step cell predicts an initial state, drawn independently of f. For (i), a row-final cell predicts a deterministically positioned separator (Lemma C.3), conveying zero mutual information about f. For (i), substituting nc=nc,y=0n_c=n_c,y=0 into Theorem D.3 yields P^α(y∣c)=1/V P_α(y c)=1/V, the mean of the Dir(αV)Dir( 1_V) prior, independent of the trajectory. ∎ Remark. The excluded classes differ in frequency and rationale. Initial-step cells (fraction 1/T1/T) and novel configurations are excluded because their Bayes-optimal prediction is uninformative about the inferred rule, scoring at 1/V1/V. Row-final cells (fraction 1/Wd1/W_d) are universally excluded because they deterministically predict a separator; scoring them would artificially inflate accuracy. The novel configurations become rare as T grows. Once an uncovered configuration is queried, its target is observed and becomes a precedent, and by Lemma D.1(i) it stays covered. Each of the VkV^k configurations therefore yields at most one uncovered query in the whole stream, so for fixed V, k and G their number is bounded independently of T and their fraction vanishes. Consequently, we rejection-sample evaluation trajectories to ensure every scored query is resolvable (Appendix I.3). D.2 Bayes-optimal posterior prediction Under the prior of Definition 1, no predictor attains lower expected log loss than the posterior predictive, which relies on counts (Theorem D.3). We measure divergences against this Bayes-optimal predictor, and Theorem 9 bounds the circuit’s divergence from it. For next-cell accuracy the Bayes act is the argmax of the posterior predictive. Sampling from it is a different predictor: at predictive distribution (0.9,0.1)(0.9,0.1), a sample matches the target with probability 0.820.82, while the mode matches with probability 0.90.9. Theorem D.3 (Bayes posterior predictive; Theorem 3 of the body). Let f be drawn as in Definition 1 and let a trajectory be serialized as in Appendix C. For every token with resolvable query c and every y∈y , the posterior predictive distribution of the target given everything observed up to that token is exactly P^α(y∣c)=nc,y+αnc+Vα, P_α(y c)\;=\; n_c,y+αn_c+Vα, and no predictor attains smaller expected log-loss. Proof. By Definition 1, cells at t≥1t≥ 1 are conditionally independent across z given the previous step, and the initial time step is drawn independently of f. The trajectory likelihood factorizes into an initial-step term and one multinomial factor per configuration c, with counts nc,yn_c,y. The initial-step factor p(x0,⋅)p(x_0,·) is independent of f and cancels from the posterior. The independent Dirichlet prior is conjugate, yielding the posterior ⨂cDir(α+nc,⋅) _cDir( 1+n_c,·). The mean of a Dir(β)Dir(β) distribution is βy/∑vβv _y/ _v _v, producing the stated formula. Under log-loss, the Bayes act is exactly the posterior predictive. ∎ Remark. The proof does not use resolvability, and the formula remains valid at nc=0n_c=0, where Lemma D.2(i) shows it returns the prior mean. We state resolvability in the theorem because it is the regime where the formula is informative, and because every later result which uses this predictor divides by ncn_c. Corollary D.4 (Empirical-frequency limit and deterministic lookup). As α→0α→ 0 the predictor of Theorem D.3 tends to the empirical frequency nc,y/ncn_c,y/n_c. If in addition every f(⋅∣c)f(· c) is a point mass, meaning the deterministic corner of Definition 1, then a single observation of c determines its image, so the predictor is the lookup table and is exact on every resolvable query. Proof. The limit is immediate from the displayed formula. Under a point mass f(⋅∣c)=y⋆f(· c)=1_y every observation of c has target y⋆y , so nc,y/nc=[y=y⋆]n_c,y/n_c=1[y=y ] as soon as nc≥1n_c≥ 1, which Lemma D.1(i) supplies at a resolvable query. ∎ Remark. Corollary D.4 characterizes the predictor. In the deterministic setting the Bayes-optimal predictor is exact, so exact-match accuracy is a meaningful metric and 100%100\% is attainable. Theorem H.9(i) characterizes the circuit, and it shows that the two-layer construction attains that floor once the score gap is large enough. Outside the deterministic regime the Bayes-optimal predictor sits strictly below 100%100\% accuracy, because the query configuration determines only a distribution over the target. Table 1 therefore reports the Kullback–Leibler divergence from the k-gram estimate of P^α P_α, and Theorem 9 bounds the divergence from P^α P_α itself. A predictor which matches the Bayes-optimal predictor still errs on a strictly positive fraction of stochastic queries. Part I — Spatial routing primitives Appendix E Spatial addressing with grid-independent width Appendix C demonstrates that a sequence-relative additive bias (Definition C.5) cannot route a toroidal neighborhood. Consequently, the Layer-1 positional table is indexed spatially. This section derives the required table width. Lemma 6 establishes that a positional bias can isolate any target offset set using a grid-independent number of frequencies; the table width is this frequency count plus two. The section is structured as follows. Section E.1 shows the coordinate dimension of a translation-invariant bias equals its Fourier spectral support size. Section E.2 bounds this support for isolating kernels, which strictly order a target set above its complement. Section E.3 translates this ordering into an attention mass bound. Finally, Section E.4 constructs the positional table and its projections, establishing the interface for Appendix G, while Section E.5 provides a numerical example. E.1 Fourier representation of spatial attention scores We apply harmonic analysis on finite abelian groups (see Terras, 1999, §1.2 and §1.10) without proof. The grid =[W1]×⋯×[Wd]G=[W_1]×·s×[W_d] is the product of the cyclic groups ℤW1,…,ℤWdZ_W_1,…,Z_W_d under coordinatewise addition, and has order ||=∏jWj = _jW_j. Its dual G is the group of characters, indexed by the same set: for ω∈^ω∈ G and δ∈δ put φω(δ)≔ 2π∑j=1dωjδjWj,χω(δ)≔eiφω(δ). _ω(δ)\; \;2π _j=1^d _j _jW_j, _ω(δ)\; \;e^i _ω(δ). (9) Two consequences of (9) are frequently used. First, the phase is additive, φω(δ+δ′)≡φω(δ)+φω(δ′)(mod2π),equivalentlyχω(δ+δ′)=χω(δ)χω(δ′), _ω(δ+δ )\;≡\; _ω(δ)+ _ω(δ ) 2π, _ω(δ+δ )\;=\; _ω(δ)\, _ω(δ ), (10) meaning a displacement in the argument rotates the value. The congruence is needed because δ+δ′δ+δ is reduced modulo the side lengths; the character identity, and every sine and cosine computed from it, hold exactly. Second, characters are orthonormal: ω∼Unif(^)χω(y)=1||∑ω∈^χω(y)=1y=0,0y≠0,y∈. E_ω ( G)\; _ω(y)\;=\; 1 _ω∈ G _ω(y)\;=\; cases1&y=0,\\ 0&y≠ 0, cases y . (11) Since the characters form an orthonormal basis of ℂC^G, every g:→ℂg:G has a unique expansion g=∑ωg^(ω)χωg= _ω g(ω) _ω. The spectrum of g is suppg^≔ω:g^(ω)≠0supp g \ω: g(ω)≠ 0\, and it is conjugate-symmetric, g^(−ω)=g^(ω)¯ g(-ω)= g(ω), when g is real. We write e1,…,ede_1,…,e_d for the standard generators of G, and dS≔|suppg^∖0|d_S\; \; g \0\ for the number of nontrivial characters in the spectrum, the addressing dimension of g. A displacement-dependent positional bias z−z′z-z induces a G-circulant score matrix. Lemma E.1 establishes its minimal rank factorization, with transformer implications discussed in §E.4. Lemma E.1 (Realization of translation-invariant spatial biases). Let g:→ℝg:G and Ω≔suppg g. The least n for which there exist p:→ℝnp:G ^n and Q∈ℝn×nQ ^n× n with pz⊤Qpz′=g(z−z′)for all z,z′∈p_z Q\,p_z \;=\;g(z-z ) all z,z is exactly |Ω| . A Q attaining it may be taken block diagonal with blocks of size 11 and 22, the 2×22× 2 blocks being scaled rotations. Proof. The score matrix and its eigenvalues. Let M be the matrix indexed by ×G×G with entries Mz,z′≔g(z−z′)M_z,z g(z-z ). It is constant along the orbits of the diagonal action of G on itself, making it a G-circulant matrix, the d-dimensional analogue of a circulant. Every character is an eigenvector of M: substituting y≔z−z′y z-z and using (10), (Mχω)(z)=∑z′∈g(z−z′)χω(z′)=∑y∈g(y)χω(z−y)=χω(z)∑y∈g(y)χω(y)¯=||g^(ω)χω(z). split(M _ω)(z)&\;=\; _z g(z-z )\, _ω(z )\;=\; _y g(y)\, _ω(z-y)\\[2.0pt] &\;=\; _ω(z) _y g(y)\, _ω(y)\;=\; \, g(ω)\, _ω(z). split (12) The || characters are a basis, so (12) diagonalizes M and its eigenvalues are ||g^(ω)ω∈^\ g(ω)\_ω∈ G. Exactly |Ω| of them are nonzero, so rankM=|Ω|rankM= . Lower bound. Suppose p and Q are as in the statement and let P be the n×||n× matrix whose columns are the vectors pzp_z. Then M=P⊤QPM=P QP, so |Ω|=rankM≤rankQ≤n. \;=\;rankM\;≤\;rankQ\;≤\;n. Construction. For the converse, partition Ω into orbits of the involution ω↦−ω -ω. Because g is real its spectrum is conjugate-symmetric, so collecting each orbit into a single real term gives g(δ)=∑orbits ω,−ω[αωcosφω(δ)+βωsinφω(δ)],g(δ)\;=\; _orbits \ω,-ω\ [ _ω _ω(δ)+ _ω _ω(δ) ], (13) with αω,βω∈ℝ _ω, _ω . An orbit is self-paired when ω=−ω=-ω, that is 2ω=02ω=0; there φω _ω takes values in 0,π\0,π\, so sinφω≡0 _ω≡ 0 and βω=0 _ω=0. Assign coordinates as follows: a self-paired orbit, which contributes one element to Ω , receives the single coordinate cosφω(z) _ω(z); a conjugate pair, which contributes two, receives the two coordinates eω(z)≔[cosφω(z)sinφω(z)]∈ℝ2.e_ω(z)\; \; bmatrix _ω(z)\\[2.0pt] _ω(z) bmatrix\;∈\;R^2. (14) The total is |Ω| coordinates. Take Q block diagonal with the blocks [αω]on a self-paired orbit,Mω≔[αω−βωβωαω]on a conjugate pair. [\, _ω\, ] a self-paired orbit, M_ω\; \; bmatrix _ω&- _ω\\[2.0pt] _ω& - _ω bmatrix a conjugate pair. (15) It remains to check that each block contributes its term of (13). Write A≔φω(z)A _ω(z) and B≔φω(z′)B _ω(z ). Expanding the quadratic form and applying the angle-difference identities cos(A−B)=cosAcosB+sinAsinB (A-B)= A B+ A B and sin(A−B)=sinAcosB−cosAsinB (A-B)= A B- A B, eω(z)⊤Mωeω(z′) e_ω(z) M_ω\,e_ω(z ) =[cosAsinA][αω−βωβωαω][cosBsinB] = bmatrix A& A bmatrix bmatrix _ω&- _ω\\ _ω& - _ω bmatrix bmatrix B\\ B bmatrix =αω(cosAcosB+sinAsinB)+βω(sinAcosB−cosAsinB) = _ω ( A B+ A B )+ _ω ( A B- A B ) =αωcos(A−B)+βωsin(A−B). = _ω (A-B)+ _ω (A-B). (16) By (10), A−B=φω(z)−φω(z′)=φω(z−z′)A-B= _ω(z)- _ω(z )= _ω(z-z ), so (16) is exactly the ω-term of (13) evaluated at z−z′z-z . The self-paired blocks reduce to the same computation with the sine coordinate absent. Summing over the orbits gives pz⊤Qpz′=g(z−z′)p_z Q\,p_z =g(z-z ). Finally, Mω=rωR(θω)M_ω=r_ωR( _ω) with rω=αω2+βω2r_ω= _ω^2+ _ω^2, θω=atan2(βω,αω) _ω=atan2( _ω, _ω) and R(θ)R(θ) the rotation by θ, so the 2×22× 2 blocks are scaled rotations, as claimed. ∎ Remark. The lower bound establishes the addressing dimension dSd_S (§E.1) as an intrinsic property of the positional bias. In §E.4, the scaled-rotation construction (15) allows an attention head to select its routing offset via a linear map applied to a shared positional table, minimizing parameter count. E.2 Isolating a set of offsets Definition E.2 (Isolation). Let ∅≠⊊ and γ>0γ>0. A function g:→ℝg:G isolates N with margin γ if minδ∈g(δ)−maxδ∉g(δ)≥γ. _δ g(δ)\;-\; _δ g(δ)\;≥\;γ. Isolation is an ordering condition. Since additive constants leave the softmax invariant, g isolates N if and only if g+constg+const does. We therefore discard the trivial character ω=0ω=0 and report counts for suppg^∖0supp g \0\. The elementary construction multiplies one factor per value the target set assumes on each axis. It vanishes exactly on the bounding box of N and is strictly positive elsewhere, reducing the problem to the box. When the box coincides with the target set, it yields an exact solution (e.g., Construction I in Appendix G). Lemma E.3 (Box kernels). Let ∅≠⊆ , let Vj≔uj:u∈V_j \u_j:u \ be the projection of N to axis j, and put Pj(x)≔∏v∈Vj(1−cos(2π(xj−v)/Wj)),Q≔∑j=1dPj,B≔V1×⋯×Vd.P_j(x)\; \; _v∈ V_j (1- (2π(x_j-v)/W_j ) ), Q\; \; _j=1^dP_j, B\; \;V_1×…× V_d. Then Q≥0Q≥ 0 vanishes exactly on B, which contains N and satisfies |B|≤||d B ≤ ^d, and suppQ^∖0⊆cej:j≤d, 1≤|c|≤||,supp Q \0\\; \;\c\,e_j:j≤ d,\;1≤ c ≤ \, at most 2d||2d characters. Consequently: (i) if B=≠B=N , then −Q-Q isolates N with margin ε≔minx∉BQ(x)>0 _x∉ BQ(x)>0 at no more than 2d||2d nontrivial frequencies; (i) a single offset, =δN=\δ\, is that case: B=δB=\δ\, Q(x)=∑j(1−cos(2π(xj−δj)/Wj))Q(x)= _j (1- (2π(x_j- _j)/W_j) ) is of degree one on each axis, and δ\δ\ is isolated at at most 2d2d frequencies, the pair (cos,sin)( , ) on each axis, with margin 1−cos(2π/Wmax)1- (2π/W_ ), where Wmax≔maxjWjW_ _jW_j is the largest side length. The count is exactly 2d2d when every Wj≥3W_j≥ 3; an axis with Wj=2W_j=2 contributes one character instead of two, since there ej=−eje_j=-e_j and the orbit is self-paired. Proof. Non-negativity and the zero set. Each factor of PjP_j has the form 1−cosθ∈[0,2]1- θ∈[0,2] and vanishes exactly when θ∈2πℤθ∈ 2 , that is when xj=vx_j=v in ℤWjZ_W_j. So Pj≥0P_j≥ 0, and Pj(x)=0P_j(x)=0 if and only if xj∈Vjx_j∈ V_j. A sum of non-negative terms vanishes only where every term does, so Q≥0Q≥ 0 and Q(x)=0⟺xj∈Vj for every j⟺x∈B.Q(x)=0 x_j∈ V_j for every j x∈ B. The box contains the target set, and is not much larger. If u∈u then uj∈Vju_j∈ V_j for every j by the definition of VjV_j, so ⊆BN B. Each VjV_j is the image of N under a coordinate projection, so |Vj|≤|| V_j ≤ and |B|=∏j|Vj|≤||d B = _j V_j ≤ ^d. The spectrum. Fix j. Each factor of PjP_j is a function of xjx_j alone whose spectrum lies in 0,±ej\0,± e_j\, a trigonometric polynomial of degree 11 in xjx_j. The product-to-sum identity cos(a)cos(b)=12[cos(a−b)+cos(a+b)] (a) (b)\;=\; 12 [ (a-b)+ (a+b) ] and its two companions show that multiplying a trigonometric polynomial of degree m by one of degree 11 yields one of degree at most m+1m+1. By induction on the |Vj| V_j factors, PjP_j is a trigonometric polynomial in xjx_j of degree at most |Vj|≤|| V_j ≤ , so suppP^j⊆cej:|c|≤||.supp P_j\; \;\c\,e_j: c ≤ \. Summing over j gives the stated inclusion for Q. Discarding ω=0ω=0, each axis contributes at most the 2||2 characters ±ej,±2ej,…,±||ej± e_j,± 2e_j,…,± e_j, for at most 2d||2d in all. Part (i). Suppose B=B=N. Then Q vanishes on N, and off N it is positive; since G is finite, ε=minx∉BQ(x) = _x∉ BQ(x) is a minimum over a finite set on which Q does not vanish, hence ε>0 >0. Therefore −Q(x)=0(x∈),−Q(x)≤−ε(x∉),-Q(x)=0 (x ), -Q(x)≤- (x ), which is isolation with margin ε . The frequency count is the one just established, and negation does not change a spectrum. Part (i). Let =δN=\δ\. Then Vj=δjV_j=\ _j\ is a single value for each j, so each PjP_j consists of one factor, B=V1×⋯×Vd=δB=V_1×·s× V_d=\δ\, and Q(x)=∑j=1d(1−cos(2π(xj−δj)/Wj)).Q(x)\;=\; _j=1^d (1- (2π(x_j- _j)/W_j ) ). Each summand has spectrum 0,±ej\0,± e_j\, so suppQ^∖0supp Q \0\ is contained in ±ejj≤d\± e_j\_j≤ d, one (cos,sin)( , ) pair per axis and hence at most 2d2d elements. The containment is an equality when every Wj≥3W_j≥ 3. If Wj=2W_j=2 then 2ej=02e_j=0 in G, so eje_j and −ej-e_j are the same character, φej _e_j takes values in 0,π\0,π\, and that axis contributes a single self-paired character, so the count drops by one. Lemma E.1 then assigns that axis one coordinate, so the realized width matches the reduced count. Padding to 2d2d recovers a single uniform formula where one is preferred. Since B=B=N, part (i) applies, and it remains to bound ε from below. Let x≠δx≠δ. Then xj≠δjx_j≠ _j for some axis j, so xj−δjx_j- _j is a nonzero residue modulo WjW_j and its phase 2π(xj−δj)/Wj2π(x_j- _j)/W_j is at angular distance at least 2π/Wj2π/W_j from 00. Cosine is decreasing in the distance to 00 on [0,π][0,π], so that summand is at least 1−cos(2π/Wj)1- (2π/W_j), and the remaining summands are non-negative: Q(x)≥ 1−cos(2π/Wj)≥ 1−cos(2π/Wmax),Q(x)\;≥\;1- (2π/W_j )\;≥\;1- (2π/W_ ), the second inequality because Wj≤WmaxW_j≤ W_ makes the angle 2π/Wj2π/W_j no smaller than 2π/Wmax2π/W_ , both lying in (0,π](0,π] whenever Wj≥2W_j≥ 2. Hence ε≥1−cos(2π/Wmax) ≥ 1- (2π/W_ ). ∎ Example. Lemma E.3 provides a worst-case upper bound. Numerical optimization yields much tighter results for standard neighborhoods. For example, on ℤ62Z_6^2, the von Neumann, Moore, and eight-offset routing sets U can each be isolated using only four characters ±e1,±e2\± e_1,± e_2\, significantly below the guaranteed 3232 characters. This setting is analyzed thoroughly in §E.5. If the bounding box strictly contains the target set, the box kernel constitutes the first stage of a two-stage probabilistic construction. Theorem E.4 (Grid-independent spatial isolation). Let ∅≠⊊ and γ>0γ>0. There is a g:→ℝg:G isolating N with margin γ and |suppg^∖0|≤ 2d||+ 2ν,ν≔⌈40||(dln||+1)⌉, g \0\ \;≤\;2d\, \;+\;2ν, ν\; \; 40\, \,(d +1) , that is O(||dlog||)O ( \,d ) frequencies. The count is independent of T and || . Proof. Stage 1: a box around the target set. Let Q and B be the box kernel and box of Lemma E.3. Then Q≥0Q≥ 0 vanishes exactly on B, we have ⊆BN B and |B|≤||d B ≤ ^d, and Q has at most 2d||2d nontrivial characters. It remains to separate N from B∖B , a set of at most ||d ^d points; this is the only step at which the size of the grid could have entered, and Stage 3 is where it is kept out. Stage 2: one random character. Fix x∈Bx∈ B, let ω be uniform on G, and put Z(ω)≔∑u∈cosφω(x−u)=ℜ∑u∈χω(x−u).Z(ω)\; \; _u _ω(x-u)\;=\; _u _ω(x-u). (17) By (11) the term indexed by u has expectation 11 if x=ux=u and 00 otherwise, so Z=|u∈:u=x|=1x∈,0x∈B∖.EZ\;=\; \u :u=x\ \;=\; cases1&x ,\\ 0&x∈ B . cases (18) The two cases differ by 11, and the rest of the proof turns that gap into a deterministic one. For the second moment, apply the product-to-sum identity cosacosb=12[cos(a−b)+cos(a+b)] a b= 12[ (a-b)+ (a+b)] to each pair of terms of (17) and use φω(x−u)±φω(x−v)=φω((x−u)±(x−v)) _ω(x-u)± _ω(x-v)= _ω ((x-u)±(x-v) ) from (10): [Z2]=12∑u,v∈cosφω(v−u)+12∑u,v∈cosφω(2x−u−v).E[Z^2]\;=\; 12 _u,v E _ω(v-u)\;+\; 12 _u,v E _ω(2x-u-v). (19) Each expectation in (19) is 11 or 00, again by (11). In the first sum the surviving pairs are those with v=uv=u, of which there are || . In the second the surviving pairs are those with u+v=2xu+v=2x; here u determines v, so at most || pairs survive. Hence VarZ≤[Z2]≤12||+12||=||.VarZ\;≤\;E[Z^2]\;≤\; 12 + 12 \;=\; . (20) Finally |Z|≤|| Z ≤ termwise, so with (18), |Z−Z|≤||+1≤ 2||. Z-EZ \;≤\; +1\;≤\;2 . (21) Stage 3: sampling, and why the grid does not enter. Draw ω(1),…,ω(ν)ω^(1),…,ω^(ν) independent and uniform on G and put R≔ν−1∑i≤νZ(ω(i))R ν^-1 _i≤νZ(ω^(i)). Bernstein’s inequality for independent, mean-zero summands with variance proxy σ2σ^2 and range bound M reads ℙ(|R−R|≥t)≤ 2exp(−νt22(σ2+Mt/3)).P ( R-ER ≥ t )\;≤\;2 \! (- ν t^22 (σ^2+Mt/3 ) ). Substituting σ2=||σ^2= from (20), M=2||M=2 from (21) and t=14t= 14, ℙ(|R−R|≥14)≤ 2exp(−ν/162(||+||/6))= 2exp(−ν/1673||)= 2exp(−3ν112||). splitP ( R-ER ≥ 14 )&\;≤\;2 \! (- ν/162 ( + /6 ) )\;=\;2 \! (- ν/16 73 )\\[4.0pt] &\;=\;2 \! (- 3ν112\, ). split (22) This bound holds for each fixed x∈Bx∈ B. Taking a union bound over the at most ||d ^d points of B, the probability that |R−R|≥14 R-ER ≥ 14 somewhere on B is less than 11 as soon as 2||dexp(−3ν112||)<1⟺ν>1123||(dln||+ln2).2\, ^d \! (- 3ν112 )<1 ν\;>\; 1123\, (d + 2 ). The ν of the statement satisfies this, since 40>112/3=37.33…40>112/3=37.33… and 1>ln21> 2. The grid enters neither (22), whose constants come from (20) and (21) alone, nor the union bound, which ranges over B alone; the final count is therefore independent of W1,…,WdW_1,…,W_d. Some realization of ω(1),…,ω(ν)ω^(1),…,ω^(ν) therefore has R≥34 on ,R≤14 on B∖,R≥ 34 on N, R≤ 14 on B , (23) by (18); fix it. Being an average of the real functions (17), R is real, and suppR^∖0supp R \0\ has at most 2ν2ν elements: the sampled frequencies and their conjugates. Termwise, |R|≤|| R ≤ everywhere on G. Stage 4: synthesis. Let ε≔minx∉BQ(x)>0 _x∉ BQ(x)>0, a minimum over a finite set on which Q does not vanish, and put g0≔R−||εQ−12.g_0\; \;R\;-\; \,Q\;-\; 12. (24) The three regions of G are handled in turn. (a) x∈x . Then Q(x)=0Q(x)=0 because ⊆BN B, so g0(x)=R(x)−12≥34−12=14g_0(x)=R(x)- 12≥ 34- 12= 14 by (23). (b) x∈B∖x∈ B . Again Q(x)=0Q(x)=0, so g0(x)=R(x)−12≤14−12=−14g_0(x)=R(x)- 12≤ 14- 12=- 14. (c) x∉Bx∉ B. Then Q(x)≥εQ(x)≥ , so (||/ε)Q(x)≥||( / )Q(x)≥ , while R(x)≤||R(x)≤ ; hence g0(x)≤||−||−12=−12<−14g_0(x)≤ - - 12=- 12<- 14. So g0≥14g_0≥ 14 on N and g0≤−14g_0≤- 14 off it, and g≔4γg0g 4γ\,g_0 isolates N with margin 4γ(14+14)=2γ≥γ4γ( 14+ 14)=2γ≥γ. Its spectrum is contained in suppR^∪suppQ^∪0supp R Q∪\0\, so |suppg^∖0|≤2ν+2d|| g \0\ ≤ 2ν+2d , which is the stated count. Two degenerate cases are worth recording. If B=B=G, case (c) is vacuous, no x lies outside B, and any ε>0 >0 serves in (24). If B=B=N, case (b) is vacuous and the random part is unnecessary altogether: Lemma E.3(i) already isolates N, at 2d||2d frequencies and with no ν term. ∎ Remark. Because spectral support cannot exceed || , Theorem E.4 is informative when ||dlog||≪|| \,d , the regime where grid independence is critical. The theorem establishes a grid-independent scaling law irrespective of offset topology. E.3 Attention concentration from a score gap While isolation strictly orders target offsets above others, securing a quantitative guarantee on attention mass requires scaling. This is the only point in the analysis where the absolute scale of the positional kernel matters; previous results depend solely on the Fourier spectral support. Corollary E.5 (Softmax concentration). Let a softmax be taken over a finite set of keys scored Λg g, where Λ>0 >0 and g isolates a target subset of the keys with margin γ. Suppose at least one target key is present and at most N≠N_≠ non-target keys are. Then the attention mass placed off the target subset is at most N≠e−ΛγN_≠e^- γ, and is therefore at most ε as soon as Λγ≥log(N≠/ε),equivalentlyΛ≥γ−1log(N≠/ε). γ\;≥\; (N_≠/ ), \;≥\;γ^-1 (N_≠/ ). (25) Proof. Write s⋆≔mintargetgs_ _targetg and s≠≔maxnon-targetgs_≠ _non-targetg, so that isolation reads s⋆−s≠≥γs_ -s_≠≥γ and, after scaling, Λs⋆−Λs≠≥Λγ s_ - s_≠≥ γ. Split the partition function into its target and non-target parts, A≔∑target keyseΛg,B≔∑non-target keyseΛg.A\; \; _target keyse g, B\; \; _non-target keyse g. At least one target key is present, so A≥eΛs⋆A≥ e s_ . Every non-target key contributes at most eΛs≠e s_≠, and there are at most N≠N_≠ of them, so B B ≤N≠eΛs≠=N≠eΛs⋆e−Λ(s⋆−s≠) ≤\;N_≠e s_≠\;=\;N_≠e s_ e^- (s_ -s_≠) ≤N≠e−ΛγeΛs⋆≤N≠e−ΛγA. ≤\;N_≠e^- γ\,e s_ \;≤\;N_≠e^- γA. The mass off the target subset is B/(A+B)B/(A+B), and since A,B≥0A,B≥ 0, BA+B≤BA≤N≠e−Λγ. BA+B\;≤\; BA\;≤\;N_≠e^- γ. This is at most ε exactly when eΛγ≥N≠/εe γ≥ N_≠/ , which is (25). ∎ E.4 Selecting spatial offsets in the preceding time step This section details the spatial positional block B2B_2 (Definition G.2), establishing the interface for Appendix G. Lemma E.1 connects spectral counts to table width. A translation-invariant positional bias yields a score matrix P⊤WQ(1)⊤WK(1)P W_Q^(1) W_K^(1)P (where P is the positional table). Setting Q=WQ(1)⊤WK(1)Q=W_Q^(1) W_K^(1) confirms the table requires exactly |suppg^| g coordinates. Discarding the trivial character, this is the addressing dimension dSd_S. An attention head selects its routed offset by rotating the 2×22× 2 blocks in (15). Corollary E.6 (Spatiotemporal addressing interface). Let ∅≠⊆ be a set of offsets and let a Layer-1 head be required to score, from its query’s own cell κ(n)κ(n), the cells at κ(n)+δκ(n)+δ for δ∈δ , in the time step before the target cell’s, strictly above every other causally visible cell key. There is a positional table pn∈ℝdpp_n ^d_p, indexed by sequence position, and projections WQ,WKW_Q,W_K whose pre-softmax score does so with a margin γ>0γ>0, where dp=dS+2,dS≤ 2d||+2ν=O(||dlog||),d_p\;=\;d_S+2, d_S\;≤\;2d +2ν\;=\;O ( \,d ), and dS=2d_S=2d when N is a single offset. The width is independent of the volume and of the horizon. The two temporal coordinates carry a scale λ, which must satisfy λ≥R+γT,R≔maxδ∈g(δ)−minδ∈u^d−g(δ)≥ 0,γT≔ 1−cos(2π/T), gatheredλ\;≥\; R+γ _T,\\[4.0pt] R\; \; _δ g(δ)- _δ∈ u_d-Ng(δ)\;≥\;0, _T\; \;1- (2π/T), gathered (26) where g is the spatial kernel. The scale λ enters no width. Proof. Stage 1: the group and the target set. A query at sequence position n has virtual time step τ(n)τ(n) and virtual cell κ(n)κ(n), both defined in Appendix C.1, and its target cell is κ(n)+u^dκ(n)+ u_d (Lemma C.2). It must score the keys n′n with κ(n′)−κ(n)∈andτ(n)−τ(n′)=1κ(n )-κ(n) τ(n)-τ(n )=1 above all others. Stage 5 realizes the spatial score in the target-minus-key variable δ≔κ(n)+u^d−κ(n′),δ\; \;κ(n)+ u_d-κ(n ), and a key at κ(n′)=κ(n)+δ′κ(n )=κ(n)+δ has δ=u^d−δ′δ= u_d-δ , so the first condition reads δ∈u^d−δ∈ u_d-N. Above, u^d−≔u^d−δ′:δ′∈ u_d-N \ u_d-δ :δ \, and δ′↦u^d−δ′δ u_d-δ is a bijection of G, so |u^d−|=|| u_d-N = and every width bound of the statement, which is stated in || , is unaffected. Each condition constrains a difference, so the ambient group is ×ℤTG×Z_T and the target set is (u^d−)×1( u_d-N)×\1\. We build a kernel on that product, one block per factor. Stage 2: the spatial block. Let g isolate u^d− u_d-N in G with margin γ, by Theorem E.4, and let Ω≔suppg^∖0 g \0\ with |Ω|=dS =d_S. Removing the trivial character replaces g by the centered kernel g−g^(0)g- g(0), which isolates the same set with the same margin (Definition E.2); we write g for it from here on. Let Ω+⊆Ω _+ contain one representative of each orbit ω,−ω\ω,-ω\. Write g in the real form (13) with coefficients αω,βω _ω, _ω, and take the coordinates and blocks Lemma E.1 supplies, indexed by the representatives: ϕ(z)≔(eω(z))ω∈Ω+=(cosφω(z),sinφω(z))ω∈Ω+∈ℝdS,Mω=[αω−βωβωαω],φ(z)\; \; (e_ω(z) )_ω∈ _+\;=\; ( _ω(z),\; _ω(z) )_ω∈ _+\;∈\;R^d_S, M_ω\;=\; bmatrix _ω&- _ω\\[2.0pt] _ω& - _ω bmatrix, (27) with the sine coordinate omitted for a self-paired representative. This gives one 2×22× 2 block per conjugate pair and one 1×11× 1 block per self-paired character, for |Ω|=dS =d_S coordinates in total. By (16), ϕ(z)⊤blkdiag(Mω)ωϕ(z′)=g(z−z′)φ(z) blkdiag(M_ω)_ω\,φ(z )=g(z-z ). Stage 3: the temporal block. Step selection is isolation of the single displacement 11 in ℤTZ_T, which Lemma E.3(i) covers with d=1d=1, W1=TW_1=T and =1N=\1\. Discarding the constant term, which Definition E.2 permits, the kernel is h(s)≔cos(2π(s−1)/T),h(1)=1,h(s)≤cos(2π/T)=1−γT(s≠1),h(s)\; \; (2π(s-1)/T ), h(1)=1, h(s)≤ (2π/T)=1- _T\ \ (s≠ 1), (28) so h isolates 1\1\ with margin γT=1−cos(2π/T)>0 _T=1- (2π/T)>0, whatever T≥2T≥ 2 is. Its spectrum is ±1⊆ℤT^\± 1\ Z_T, at most two characters (one when T=2T=2, where 1=−11=-1), so Lemma E.1 realizes it in at most two coordinates. We always use two, padding with the identically zero sine coordinate when T=2T=2: ψ(τ)≔[cos(2πτ/T)sin(2πτ/T)]∈ℝ2,Mtime≔[cos(2π/T)−sin(2π/T)sin(2π/T)cos(2π/T)]=R(2π/T),ψ(τ)\; \; bmatrix (2πτ/T)\\[2.0pt] (2πτ/T) bmatrix ^2, M_time\; \; bmatrix (2π/T)&- (2π/T)\\[2.0pt] (2π/T)& - (2π/T) bmatrix\;=\;R(2π/T), (29) the rotation by one time step: reading (16) with αω=cos(2π/T) _ω= (2π/T) and βω=sin(2π/T) _ω= (2π/T) gives ψ(τ)⊤Mtimeψ(τ′)=cos(2π(τ−τ′−1)/T)=h(τ−τ′)ψ(τ) M_timeψ(τ )= (2π(τ-τ -1)/T )=h(τ-τ ). Stage 4: the table and the bilinear form. Concatenate the two blocks. The table entry at sequence position n is pn≔[ψ(τ(n))ϕ(κ(n))]∈ℝdS+2,WQ⊤WK≔blkdiag(λMtime,(Mω)ω∈Ω+),p_n\; \; bmatrixψ(τ(n))\\[2.0pt] φ(κ(n)) bmatrix\;∈\;R^d_S+2, W_Q W_K\; \;blkdiag (λ M_time,\,(M_ω)_ω∈ _+ ), (30) evaluated at the virtual time step and virtual cell of the position, which Appendix C.1 defines for cell tokens and separators alike. Because WQ⊤WKW_Q W_K is block diagonal with the blocks aligned to the blocks of pnp_n, the quadratic form is the sum of the per-block forms of Stages 2 and 3: pn⊤(WQ⊤WK)pn′=λψ(τ(n))⊤Mtimeψ(τ(n′))+∑ω∈Ω+eω(κ(n))⊤Mωeω(κ(n′))=g(κ(n)−κ(n′))+λh(τ(n)−τ(n′)). splitp_n (W_Q W_K )p_n &\;=\;λ\,ψ(τ(n)) M_time\,ψ(τ(n ))\;+\; _ω∈ _+e_ω(κ(n)) M_ω\,e_ω(κ(n ))\\[4.0pt] &\;=\;g (κ(n)-κ(n ) )\;+\;λ\,h (τ(n)-τ(n ) ). split (31) This is the form Appendix C.2 quotes as pn=(ϕ(κ(n)),ψ(τ(n)))p_n=(φ(κ(n)),ψ(τ(n))). Stage 5: the successor shift costs no coordinate. The spatial argument used in Stage 1 is κ(n)+u^d−κ(n′)κ(n)+ u_d-κ(n ), whereas (31) delivers g(κ(n)−κ(n′))g(κ(n)-κ(n )). The discrepancy is the constant u^d u_d, and by (10) a constant displacement is a fixed rotation of every character: χω(z+u^d)=χω(u^d)χω(z),that isφω(z+u^d)=φω(z)+θω,θω≔φω(u^d). _ω(z+ u_d)\;=\; _ω( u_d)\, _ω(z), is _ω(z+ u_d)= _ω(z)+ _ω, _ω _ω( u_d). The product MωR(−θω)M_ωR(- _ω) is again a scaled rotation, by the last paragraph of the proof of Lemma E.1. Replacing each block MωM_ω of (30) by it turns (16) into αωcos(A−B+θω)+βωsin(A−B+θω) _ω (A-B+ _ω)+ _ω (A-B+ _ω), so the spatial term of (31) becomes g(κ(n)+u^d−κ(n′))g(κ(n)+ u_d-κ(n )) as required. The table itself is unchanged and no coordinate is added. By Lemma C.2 the offset is the same constant u^d u_d for every position which has a target cell, separators included, so one choice of blocks serves all of them; the separator case is recorded after this proof. Stage 6: the margin. Write the score of key n′n at query n as ΛG(δ,s) \,G(δ,s) with δ≔κ(n)+u^d−κ(n′)δ κ(n)+ u_d-κ(n ), s≔τ(n)−τ(n′)s τ(n)-τ(n ) and G(δ,s)≔g(δ)+λh(s),G(δ,s)\; \;g(δ)\;+\;λ\,h(s), which Stages 4 and 5 realize. Put m≔minδ∈u^d−g(δ)m _δ∈ u_d-Ng(δ), so that maxδ∉u^d−g≤m−γ _δ∉ u_d-Ng≤ m-γ by isolation and maxδ∈g=m+R _δ g=m+R by the definition of R in (26). Three cases exhaust the keys. (a) Target keys, δ∈u^d−δ∈ u_d-N and s=1s=1. Then h(s)=1h(s)=1 and G≥m+λG≥ m+λ. (b) Right step, wrong offset, δ∉u^d−δ∉ u_d-N and s=1s=1. Then G≤(m−γ)+λG≤(m-γ)+λ, which is below case (a) by γ. (c) Wrong step, s≠1s≠ 1. Then h(s)≤1−γTh(s)≤ 1- _T by (28) and g(δ)≤m+Rg(δ)≤ m+R, so G≤m+R+λ(1−γT)=m+λ+(R−λγT)≤m+λ−γ,G\;≤\;m+R+λ(1- _T)\;=\;m+λ+ (R-λ _T )\;≤\;m+λ-γ, the last step by the choice (26) of λ, which is exactly λγT≥R+γλ _T≥ R+γ. Again this is below case (a) by γ. So G isolates (u^d−)×1( u_d-N)×\1\ with margin γ, and the pre-softmax score ΛG G isolates it with margin Λγ γ. Case (c) is the one which forces the scaling: with λ=1λ=1 the bound there is m+1+R−γTm+1+R- _T, which exceeds the target floor m+1m+1 whenever R>γTR> _T, that is, whenever the spatial kernel varies across u^d− u_d-N by more than one time step is worth. The causal mask is not needed for any of this, since h orders the whole of ℤTZ_T, visible part included. Widths. The two blocks of (30) occupy orthogonal coordinates, so their ranks add and dp=dS+2d_p=d_S+2. The count dS≤2d||+2νd_S≤ 2d +2ν is Theorem E.4, and dS=2d_S=2d for a single offset is Lemma E.3(i) on G. Neither count involves the volume or the horizon: the grid is absent from Theorem E.4 by Stage 3 of its proof, and the horizon is absent because the temporal block has two coordinates for every T. The scale λ of (26) multiplies a block; it does not widen one. ∎ Remark E.7 (Separator keys). The guarantee above is stated over cell keys. A separator carries the virtual address of the cell one step before its successor (Lemma C.4(i)), so a separator key can hold the same (τ,κ)(τ,κ) as a target cell, and a score built from τ and κ alone cannot order it below. Proposition G.6 adds a rank-one gate of strength Γ1 _1 which places every separator key Λγ γ below the target floor, extending the corollary to all causally visible keys at no positional width. Remark (Boundary cases of the interface). We clarify three assumptions used above: Horizon. Stage 3 requires T≥2T≥ 2 so that γT=1−cos(2π/T)>0 _T=1- (2π/T)>0, ensuring the temporal kernel has a nonempty complement. Definition 1 imposes T≥2T≥ 2; at T=1T=1, the prediction task is empty. Full target set. While Definition E.2 and Theorem E.4 require ⊊N , the case =N=G is covered by setting g≡0g≡ 0 (so dS=0d_S=0 and dp=2d_p=2). The temporal block alone correctly identifies all keys in the previous time step with margin γ=λγTγ=λ _T, making the interface total in N. Degenerate axes. If Wj=2W_j=2, Lemma E.3(i) contributes one character instead of two on that axis, giving dS≤2d_S≤ 2d without increasing any stated width. On the query side, the positional table accommodates separator positions. By Lemma C.4, a separator at n carries virtual indices κ(n)κ(n) and τ(n)τ(n), targets κ(n)+u^dκ(n)+ u_d, and causally accesses all parents in step τ(n)−1τ(n)-1. Because the proof depends on the query solely through κ and τ, (30) applies verbatim to separator queries without additional coordinates, maintaining the margin γ. Remark E.7 covers the key side. Subsequent sections depend on the spatial kernel g, its isolation margin γ, the positional table width dp=dS+2d_p=d_S+2, and the separator gate of Proposition G.6. Corollary E.5 converts this margin and logit scale into an attention mass bound. A caller simply specifies the desired offsets N relative to the query; Stage 1 of the proof handles the translation to the kernel’s variable. E.5 Example: addressing the 2D von Neumann routing set The preceding bounds are worst-case over all subsets N. Here, we instantiate the derivation for a specific experimental setting with explicit numerical constants. Example E.8 (The routing set on ℤ62Z_6^2). Let =ℤ62G=Z_6^2, let DKD_K be the von Neumann neighborhood, let u^d=(0,1) u_d=(0,1) and let T=12T=12, so that the routing set =DK∪(DK+u^d)U=D_K∪(D_K+ u_d) of Definition 2 has the ||=8 =8 elements =(0,0),(0,1),(0,2),(0,5),(1,0),(1,1),(5,0),(5,1).U\;=\;\(0,0),\,(0,1),\,(0,2),\,(0,5),\,(1,0),\,(1,1),\,(5,0),\,(5,1)\. Then the anisotropic, half-shifted degree-one kernel g(δ)=32cos(2πδ1/6)+cos(2π(δ2−12)/6)g(δ)\;=\; 32 (2π _1/6 )\;+\; (2π( _2- 12)/6 ) (32) isolates U with margin γ=34γ= 34 at the four characters Ω=±e1,±e2 =\± e_1,± e_2\. Here u^d−= u_d-U=U, so this is also the set Stage 2 of Corollary E.6 asks g to isolate when the corollary is invoked with =N=U. Thus dS= 4,dp= 6,d_S\;=\;4, d_p\;=\;6, and Corollary E.6 holds at these widths with temporal scale λ=13λ=13. At the stream length N=504N=504 of this setting, a logit scale Λ=12 =12 places mass at least 1−1121- 112 on U. Proof. The spectrum and the blocks. Expanding the half-step shift by the angle-difference identity, with 2π⋅12/6=π/62π· 12/6=π/6, cos(2π(δ2−12)/6) (2π( _2- 12)/6 ) =cos(φe2(δ)−π6) =\; ( _e_2(δ)- π6 ) =cosπ6cosφe2(δ)+sinπ6sinφe2(δ), =\; π6\, _e_2(δ)\;+\; π6\, _e_2(δ), so (32) is in the real form (13) with αe1=32,βe1=0,αe2=32,βe2=12. _e_1= 32, _e_1=0, _e_2= 32, _e_2= 12. Both coefficients are nonzero, so suppg^∖0=±e1,±e2supp g \0\=\± e_1,± e_2\ and dS=|Ω|=4d_S= =4: one conjugate pair per axis, hence the two 2×22× 2 blocks of (15), Me1=[320032]=32I2,Me2=[32−121232]=R(π/6).M_e_1\;=\; bmatrix 32&0\\[2.0pt] 0& 32 bmatrix\;=\; 32\,I_2, M_e_2\;=\; bmatrix 32&- 12\\[4.0pt] 12& - 32 bmatrix\;=\;R(π/6). The shift costs no coordinate: it is absorbed into the rotation angle of the second block, as Lemma E.1 shows in general. With the two temporal coordinates of Stage 3 of Corollary E.6, dp=dS+2=6d_p=d_S+2=6. The margin. On ℤ6Z_6 the cosine takes the four values 1,12,−12,−11, 12,- 12,-1, so g takes finitely many values which can be listed. On U it takes three: g(0,0)=g(0,1)=32+32,g(0,2)=g(0,5)=32,g(1,0)=g(1,1)=g(5,0)=g(5,1)=34+32, gatheredg(0,0)=g(0,1)= 32+ 32, g(0,2)=g(0,5)= 32,\\[4.0pt] g(1,0)=g(1,1)=g(5,0)=g(5,1)= 34+ 32, gathered so ming=32 _Ug= 32. Off U the largest value is maxδ∉g=34 _δ g= 34, attained at the four offsets (±1,2)(± 1,2) and (±1,5)(± 1,5). Hence γ=ming−max∉g=32−34=34.γ\;=\; _Ug- _ g\;=\; 32- 34\;=\; 34. The half-step shift makes this work. U is asymmetric along the innermost axis, containing (0,2)(0,2) but not (0,4)(0,4), and an unshifted kernel, being even in δ2 _2, scores those two offsets alike and cannot separate them. The temporal scale. The largest value of g on the whole grid is maxg=32+32 _Gg= 32+ 32, attained at (0,0)∈(0,0) , so R=maxg−ming=32≈ 0.866,γT= 1−cos(2π/12)= 1−32≈ 0.134,R\;=\; _Gg- _Ug\;=\; 32\;≈\;0.866, _T\;=\;1- (2π/12)\;=\;1- 32\;≈\;0.134, and (26) requires λ≥R+γT=32+341−32≈ 12.06,λ\;≥\; R+γ _T\;=\; 32+ 341- 32\;≈\;12.06, so λ=13λ=13 suffices. The gap between γ=34γ= 34 and γT≈0.134 _T≈ 0.134 makes the scaling necessary here: an unscaled sum of the two kernels would score a key in the wrong step at up to 32+32+cos(π/6)≈3.23 32+ 32+ (π/6)≈ 3.23, above the target floor 32+1=52 32+1= 52. The logit scale. The stream length for this setting is N=T(||+||/W2)=12(36+6)=504N=T( + /W_2)=12\,(36+6)=504 (Definition C.1). Corollary E.5 with N≠≤N_≠≤ N and off-target mass ε=112 = 112 gives Λ≥γ−1log(N/ε)=43log(6048)≈ 11.61, \;≥\;γ^-1 (N/ )\;=\; 43 (6048)\;≈\;11.61, so Λ=12 =12 places all but 112 112 of the attention mass on U. We chose ε=112 = 112 to make the arithmetic concrete. This =N=U addressing serves Construction I, which decodes each block exactly and so requires (36) of Λ instead. At V=2V=2, M=12M=12 colors and nmax≤T⌈||/M⌉=36n_ ≤ T /M =36, that condition reads Λγ≥log(2V(nmax−1))=log140≈ 4.94, γ\;≥\; (2V(n_ -1) )\;=\; 140\;≈\;4.94, so Λ≥6.59 ≥ 6.59 and the same Λ=12 =12 satisfies it. ∎ Remark. Two comparisons relate this example to the general statements. First, compared to Lemma E.3: the same four characters isolate the von Neumann and Moore neighborhoods on this grid (margin 12 12) via the isotropic unshifted kernel g(δ)=cosφe1(δ)+cosφe2(δ)g(δ)= _e_1(δ)+ _e_2(δ) (Me1=Me2=I2M_e_1=M_e_2=I_2). Second, the theorem becomes informative only when ||dlog|| d is much less than the volume, the regime where grid independence is critical. For the small grids in Table 4, explicit numerical search provides tighter bounds. In 11D, no search is required: the bounding box equals the set itself, so Lemma E.3(i) applies directly, avoiding Theorem E.4’s probabilistic bounds, and yielding dS≤2d||=8d_S≤ 2d =8. Appendix F Colorings for Shared-head decoding Construction I (Appendix G) employs a shared Layer-1 head. A key at cell z′z projects a one-hot color code φ(z′)=ec(z′)∈ℝM (z )=e_c(z ) ^M via a map c:→[M]c:G→[M]. The head’s output at query z is a vector a∈ℝM+1a ^M+1 (comprising M color coordinates and one reference coordinate) which superposes all || gathered cells. The cell at offset δ writes to coordinate c(z+δ)c(z+δ) with a state-dependent weight. For the MLP to recover this cell, no other gathered cell may occupy the same coordinate, requiring: δ⟼c(z+δ)is injective on , for every z∈.δ\; \;c(z+δ) injective on U, for every z . This condition defines an admissible coloring (Definition F.1). This section characterizes these maps and bounds the required number of colors M as a function of G and U. A cell’s color is a function of its position, so the key and the query each read it from the positional table. The key reads the color of its own cell, and the query reads the color it expects at each routed offset. The two uses occupy separate coordinates, which Corollary F.5 counts in parts (e) and (b). Appendix G assigns those coordinates to residual blocks and wires them into the value projection and the MLP. F.1 Admissible colorings and the Cayley graph Definition F.1 (Admissible coloring). A coloring is a map c:→[M]c:G→[M], and it is admissible for U if it is injective on every translate z+z+U. Equivalently, c is a proper coloring of the Cayley graph Γ≔Cay(,(−)∖0), _U\; \;Cay (G,\;(U-U) \0\ ), whose vertices are the cells and whose edges join cells differing by a nonzero element of −U-U. We write M⋆M for the least M admitting an admissible coloring, that is, for the chromatic number of Γ _U. A coloring is periodic if it is the quotient map χ:→/Kχ:G /K by a subgroup K≤K , composed with any bijection /K≅[MK]G/K [M_K], equivalently if its color classes are exactly the cosets of K, and its number of colors is then MK≔|/K|M_K /K . The choice of bijection is immaterial: relabeling preserves both admissibility and the number of colors. Because a query gathers uniquely labeled cells, two cells may share a label only if their nonzero difference lies outside −U-U, reducing the problem to graph coloring. Periodic colorings are easily constructed, and their admissibility reduces to an algebraic condition: Lemma F.2 (When a periodic coloring is admissible). A periodic coloring χ:→/Kχ:G /K is admissible for U if and only if K∩(−)=0K∩(U-U)=\0\. Proof. The equality χ(z+δ)=χ(z+δ′)χ(z+δ)=χ(z+δ ) holds exactly when δ−δ′∈Kδ-δ ∈ K. As δ,δ′δ,δ range over U, injectivity on every translate z+z+U fails if and only if a nonzero element of −U-U lies in K. ∎ §F.3 uses this criterion to construct admissible colorings for our experimental grids; these are significantly smaller than the worst-case bound below. F.2 Bounds on the number of colors Lemma F.3 (Bounds on the number of colors). ||≤M⋆≤|(−)∖0|+1≤||2−||+1, \;≤\;M \;≤\; (U-U) \0\ +1\;≤\; ^2- +1, and M⋆≤MKM ≤ M_K for every periodic admissible coloring. Moreover an admissible coloring with |(−)∖0|+1 (U-U) \0\ +1 colors may be taken equitable, its color classes differing in size by at most one. The outermost bound ||2−||+1 ^2- +1 does not mention the grid. Remark F.4 (Which bounds are grid-independent). The middle quantity |(−)∖0| (U-U) \0\ , the degree of Γ _U, evaluates differences on the torus and thus depends on side lengths (distinct differences in ℤdZ^d can collide modulo WjW_j, strictly decreasing the count). Evaluating this expression in ℤdZ^d yields a grid-independent upper bound; the figures 77, 2323, and 3535 below derive from this grid-independent evaluation. For the von Neumann routing set, the ℤ2Z^2 count is |(−)∖0|=22 (U-U) \0\ =22 (degree bound 2323). On ℤ62Z_6^2, offsets +3+3 and −3-3 are identified, dropping the exact count to 2121 (degree bound 2222). While both bounds validly majorize M⋆M , only the ℤdZ^d bound is grid-independent. Grid independence is a statement about widths. The loads and logit scales of Corollary F.5(c) and (36) do depend on the volume and the horizon. Proof. The lower bound holds because U forms a clique in Γ _U. Γ _U is regular of degree Δ=|(−)∖0| = (U-U) \0\ ; a greedy coloring uses at most Δ+1 +1 labels. Every nonzero difference comes from one of the ||(||−1) ( -1) ordered pairs of distinct offsets, so Δ≤||2−|| ≤ ^2- . Equitability at Δ+1 +1 colors follows from the Hajnal–Szemerédi theorem (Hajnal, 1970). Lemma F.2 confirms that a periodic admissible coloring is proper for Γ _U, so M⋆≤MKM ≤ M_K. ∎ Remark. The upper bound depends only on local neighborhood geometry. Evaluated in ℤdZ^d (Remark F.4), it requires at most 77 colors for the elementary neighborhood, 2323 for von Neumann, and 3535 for Moore, independent of grid side length. Theorem G.10 leverages this grid-independent bound. F.3 Colorings for the experimental grids Lemma F.2 supplies admissible colorings for the three experimental settings of Appendix B.4, and each uses far fewer colors than the degree bound on the same line. Table 6 records them. Table 6: The coloring Construction I uses in each experimental setting. Every one is admissible by Lemma F.2, and every one is far below the degree bound on the same line. 1D, V=2V=2 1D, V=3V=3 2D von Neumann |(−)∖0| (U-U) \0\ 66 66 2121 degree bound on M⋆M 77 77 2222 subgroup K 4ℤ164Z_16 4ℤ324Z_32 ⟨(2,2)⟩ (2,2) colors M=MKM=M_K 44 44 1212 Each coloring is the quotient by a subgroup intersecting −U-U only at 00 (Lemma F.2). For d=1d=1, =−1,0,1,2U=\-1,0,1,2\ yields (−)∖0=±1,±2,±3(U-U) \0\=\± 1,± 2,± 3\. Because this lacks nonzero multiples of 44, reduction modulo 44 is admissible on any ℤWZ_W where 4|W4 W, yielding an optimal M=4M=4 (Lemma F.3 requires M⋆≥4M ≥ 4). For d=2d=2, coordinatewise reduction requires MK=18M_K=18, while the diagonal subgroup ⟨(2,2)⟩=(0,0),(2,2),(4,4) (2,2) =\(0,0),(2,2),(4,4)\ avoids −U-U to achieve MK=12M_K=12. The degree row in Table 6 counts |(−)∖0| (U-U) \0\ on the torus, yielding 2121 on ℤ62Z_6^2. Evaluating differences in ℤdZ^d yields the grid-independent count of 2323 (Lemma F.3, Table 7). This discrepancy arises from identifying +3+3 and −3-3 on the torus (Remark F.4). Table 7 contextualizes these grids. Table 7: Colorings across grids, for reference. MKM_K is the least number of colors over periodic admissible colorings and is arithmetic in the side length. The degree bound |(−)∖0|+1 (U-U) \0\ +1 of Lemma F.3 is evaluated with the differences taken in ℤdZ^d, so it is the same for every grid and bounds M⋆M from above; the exact torus count can be smaller, as Remark F.4 shows on ℤ62Z_6^2. The bound never degenerates and MKM_K sometimes does: on ℤ52Z_5^2 and ℤ72Z_7^2 every nontrivial subgroup has a nonzero intersection with −U-U, so MK=||M_K= and every cell takes a color of its own. neighborhood grid || least periodic MKM_K degree bound || elementary ℤ5Z_5 4 5 7 5 elementary ℤ16Z_16 4 4 7 16 elementary ℤ32Z_32 4 4 7 32 von Neumann ℤ52Z_5^2 8 25 23 25 von Neumann ℤ62Z_6^2 8 12 23 36 von Neumann ℤ72Z_7^2 8 49 23 49 von Neumann ℤ82Z_8^2 8 8 23 64 Moore ℤ62Z_6^2 12 18 35 36 Moore ℤ82Z_8^2 12 16 35 64 Moore ℤ122Z_12^2 12 12 35 144 Remark. For grids in Table 7 (excluding ℤ52Z_5^2 and ℤ72Z_7^2), periodic coloring requires fewer colors and is preferred in practice. The degree bound ensures grid independence (Theorem G.10). F.4 Coloring interface for Shared-head decoding The Shared-head construction relies on the following five guarantees. They fix the properties and the coordinate counts; Appendix G assigns the coordinates to residual blocks. Corollary F.5 (Coloring interface for the Shared-head construction). Let c be an admissible coloring of G for U with M colors. Then (a) Distinct slots. For every z, the || cells z+δz+δ, δ∈δ , carry pairwise distinct colors. (b) Address width. For every z the family of addresses (ec(z+δ))δ∈ℝ||M (e_c(z+δ) )_δ M is the image, under one fixed affine map independent of z, of ||(M−1)+1 (M-1)+1 positional coordinates: one width-M address per offset, each a one-hot and so determined by M−1M-1 of its coordinates given a shared constant. (c) Load. The number nmaxn_ of causally visible cells sharing one color, over a trajectory of at most T time steps, satisfies nmax≤Tmaxs∈[M]|c−1(s)|.n_ \;≤\;T _s∈[M] c^-1(s) . If c is equitable, then maxs|c−1(s)|≤⌈||/M⌉ _s c^-1(s) ≤ /M , and consequently nmax≤T⌈||M⌉.n_ \;≤\;T M . (d) Existence. An equitable admissible c exists on every grid with M≤|(−)∖0|+1≤||2−||+1M≤ (U-U) \0\ +1≤ ^2- +1, where the differences may be taken in ℤdZ^d, so that the final bound depends on U and on nothing else. (e) Own-color block. For every z the own-color address ec(z)∈ℝMe_c(z) ^M is a function of position alone and is carried by M positional coordinates, which may be set to zero at separator positions. Proof. (a) is admissibility, which is injectivity on z+z+U. For (b), the offset δ is fixed, so z↦ec(z+δ)z e_c(z+δ) depends on position alone and the family is carried by || width-M positional blocks. A one-hot of width M has coordinates summing to 11, so it lies in an affine subspace of dimension M−1M-1 and M−1M-1 coordinates determine it given the constant; the || addresses therefore take ||(M−1) (M-1) coordinates together with one constant coordinate. For (c), a causally visible prefix contains at most T copies of the grid, one per time step, and within a single time step the cells of color s number at most |c−1(s)| c^-1(s) ; summing over steps gives the general bound. If c is equitable, the M color classes of G differ in size by at most one, so none exceeds ⌈||/M⌉ /M . (d) restates Lemma F.3. For (e), z↦ec(z)z e_c(z) depends on position alone, and the positional table is indexed by sequence position, so its entries at separator positions may be prescribed independently of its entries at cell positions. ∎ Remark. Condition (a) ensures correctness. Conditions (b), (c), and (d) provide quantitative bounds on width, logit scale, and grid independence. One can verify Appendix G treating M symbolically; substituting the colorings of §F.3 (used in Section 5) yields concrete widths. Part I — Layer 1: the spatial gather Appendix G Layer 1: spatial gather constructions This section proves the gather component of Theorem 7 by constructing the Layer-1 weights. At any position n with virtual time step τ(n)≥1τ(n)≥ 1, Layer 1 must recover the preceding states xτ(n)−1,κ(n)+δ:δ∈ \x_τ(n)-1,\;κ(n)+δ:δ \ and track their offsets δ. Localizing these states in separate residual blocks allows Layer 2 to read DQD_Q at the current token and DKD_K at an earlier token. Formulating this requirement via (τ(n),κ(n))(τ(n),κ(n)) ensures it covers both cells and separators, and retains cells with unresolved queries as necessary keys (Remark G.5). Two challenges arise: routing the cells in U to the query token, and preserving their spatial identities. We provide two constructions resolving both: (I) Dedicated-heads. Each offset δ∈δ receives its own attention head. The head directly writes the state at offset δ into a dedicated residual block, so attention performs both routing and separation by itself. (I) Shared-head. A single head attends jointly to all offsets in U. Since the head returns only one weighted sum, the routed states would normally be mixed together. We avoid this by encoding the cell state in the attention weight and the routed-cell identity as a distinct basis vector in the value projection using a positional coloring. A one-hidden-layer MLP then separates the aggregate and reconstructs one state block per offset. Both constructions rely on the spatial-temporal addressing primitive developed above; Construction I also requires the coloring primitive. We first recall the necessary properties. Throughout, G denotes the d-dimensional torus of volume || (Definition 1), evaluated for T time steps. For a stream position n, κ(n)κ(n) and τ(n)τ(n) denote its virtual cell and virtual time step (Appendix C), and u^d u_d denotes the successor offset. See Table 3 for further notation. Spatial-temporal addressing. For any set of offsets N, Corollary E.6 provides a positional table pn∈ℝdpp_n ^d_p and projections WQ(1),WK(1)W_Q^(1),W_K^(1) which, at unit logit scale, score the keys at cells κ(n)+δκ(n)+δ, δ∈δ , in the previous time step strictly above every other causally visible cell key, with a margin γ>0γ>0. Separator keys are covered by the gate of §G.2. Its positional score is ⟨WQ(1)pn,WK(1)pn′⟩=g(κ(n)+u^d−κ(n′))+λh(τ(n)−τ(n′)), W_Q^(1)p_n,\;W_K^(1)p_n =g (κ(n)+ u_d-κ(n ) )+λ h (τ(n)-τ(n ) ), where g favors the requested spatial offsets and h selects temporal displacement 11. The spatial width is dS=2d_S=2d for a single offset and dS=O(||dlog||)d_S=O(|N|\,d |N|) in general, and it is independent of the grid volume and the horizon. After multiplying the logits by Λ>0 >0, Corollary E.5 bounds the attention mass outside the target set by N≠e−ΛγN_≠e^- γ, where N≠N_≠ is the number of visible non-target keys. Positional colors. Construction I must additionally preserve the identities of the cells routed by the Shared-head. Corollary F.5 provides a coloring c of G which is injective on every translate z+z+U, so the routing cells z+δ:δ∈\z+δ:δ \ carry pairwise distinct colors at every query location z. Writing M for the number of colors, such a coloring exists with M≤|(−)∖0|+1≤||2−||+1,M≤ |(U-U) \0\ |+1≤|U|^2-|U|+1, a bound depending on U and on nothing else. The same corollary provides the positional storage for the query-side color addresses ec(z+δ)e_c(z+δ), the key-side own-color block, and a bound on how many causally visible cells share one color. Construction I uses all four in §G.4. G.1 Target representation and residual-stream layout Both Layer-1 constructions produce the same output: |||U| state blocks. For each δ∈δ , the δ-th block should represent the state of cell (t−1,z+δ)(t-1,z+δ). Because finite softmax attention may leave mass on non-target keys, we first formalize how a block approximates the desired state. Definition G.1 (ε¯ -approximate one-hot). For ε¯∈[0,1) ∈[0,1) and s∈s , a width-V block P is an ε¯ -approximate one-hot for e(s)e(s) if it is a sub-probability vector, meaning that it is non-negative and has total mass at most 11, and it places mass at least 1−ε¯1- on coordinate s. Consequently, at most ε¯ mass lies on the remaining V−1V-1 coordinates. We call ε¯ the per-block error. Definition G.2 (Stream layout). Both constructions use a residual stream xn=[B0;B1;B2;B3;B4]x_n=[\,B_0;B_1;B_2;B_3;B_4\,] with the following orthogonal blocks. • B0∈ℝ3B_0 ^3 is the gate block. It stores the separator indicator sns_n, the auxiliary-token marker μn≔[n=⋆] _n 1[n= ], and a constant 11. • B1∈ℝVB_1 ^V stores the token’s own state one-hot and is used as the value source for state retrieval. • B2∈ℝdpB_2 ^d_p stores the positional features. Besides the dS+2d_S+2 spatial-temporal addressing coordinates of Corollary E.6, it carries the initial-step indicator ζn≔[τ(n)=0], _n 1 [τ(n)=0 ], (33) one coordinate, used by the Layer-2 key-validity gate of Definition H.1. Construction I augments these with the query-side color addresses and the own-color block (34). • B3B_3 is the Layer-1 scratch space. It contains B3pat=⨁δ∈ℝV,B_3^pat= _δ R^V, whose δ-th block will hold the state routed from offset δ. Construction I writes these blocks directly and uses no additional scratch. Construction I also uses B3agg∈ℝM+1B_3^agg ^M+1 for the Shared-head aggregate; its MLP decodes this aggregate into B3patB_3^pat and then clears B3aggB_3^agg. • B4∈ℝVB_4 ^V is reserved for the Layer-2 output and is initialized to zero on ordinary tokens. For an ordinary cell token at (t,z)(t,z), B0=(0,0,1),B1=e(xt,z),B_0=(0,0,1), B_1=e(x_t,z), while a separator has B0=(1,0,1),B1=0.B_0=(1,0,1), B_1=0. Blocks B3B_3 and B4B_4 are initialized to zero. When the auxiliary token ⋆ of §G.2 is present, it has B0=(0,1,1),B1=0,B2=0,B3=0,B4=0,B_0=(0,1,1), B_1=0, B_2=0, B_3=0, B_4=0, so that s⋆=ζ⋆=0s_ = _ =0. All other tokens are ordinary and have μn=0 _n=0. Remark G.3 (The initial-step indicator). While the positional table carries the temporal pair ψ(τ)=(cos2πτ/T,sin2πτ/T)ψ(τ)=( 2πτ/T, 2πτ/T) (Eq. 29), the indicator ζn=[τ(n)=0] _n=1[τ(n)=0] is not a linear functional of it for T≥3T≥ 3, necessitating a dedicated coordinate. Like all positional features, it depends solely on sequence position and is readily learned. This indicator resolves a role asymmetry: an initial-step cell carries x0,zx_0,z (needed by Layer 1 for queries at t=1t=1) but lacks a parent configuration (excluding it as a Layer-2 key, consistent with t′≥1t ≥ 1 in Eq. 8). Consequently, Layer 1 gates only separators, whereas Layer 2 gates both separators and initial-step cells (§H.5). Accounting for B2B_2. Construction I stores only the addressing coordinates, so dp=dS+3,dS=2d,||=1,O(||dlog||),in general,d_p=d_S+3, d_S= cases2d,&|N|=1,\\ O (|N|\,d |N| ),&in general, cases independently of the grid volume and the horizon. Two of the three non-spectral coordinates are the temporal pair of Corollary E.6; the third is the initial-step indicator ζn _n of (33), which Layer 2 needs and which we account for here so that one positional width serves the whole circuit. Construction I adds two color blocks. For every offset δ∈δ the table stores the query-side address ec(z+δ)e_c(z+δ) of the routed cell, which Corollary F.5(b) carries in at most ||(M−1)+1|U|(M-1)+1 coordinates; these addresses let the Layer-1 MLP identify which coordinate of the Shared-head aggregate belongs to each offset. Separately, the Shared-head needs the key-side color of the key’s own cell, because its value projection emits exactly that. By Corollary F.5(e) the table carries it as a dedicated width-M block B2col≔(1−sn)ec(κ(n))∈ℝM,B_2^col (1-s_n)\,e_c(κ(n)) ^M, (34) the own-color one-hot at cell positions and the zero vector at separator positions. We store this block separately from the δ=0δ=0 address. Separate storage makes the construction independent of whether 0∈0 , and it makes a separator’s Layer-1 value exactly zero, so no separator color can enter the Shared-head aggregate. This block does not admit the “M−1M-1 coordinates plus a shared constant” compression used for the query addresses, because the reconstructed coordinate would read 11, not 00, at a separator; it therefore costs a full M coordinates. We can now state our goal as an interface condition on B3patB_3^pat. Definition G.4 (Spatial induction head, quantitatively). Fix ε¯∈[0,1) ∈[0,1). A two-layer circuit with the stream layout of Definition G.2 is a spatial induction head at per-block error ε¯ if: (i) The gather. At every position n with τ(n)≥1τ(n)≥ 1, after Layer 1 the pattern scratch ΠB3patxn _B_3^patx_n consists of |||U| width-V blocks indexed by δ∈δ , and the δ-th block is an ε¯ -approximate one-hot for e(xτ(n)−1,κ(n)+δ).e (x_τ(n)-1,\;κ(n)+δ ). At positions with τ(n)=0τ(n)=0 only the weaker property of Lemma G.13 is claimed. (i) The match. Layer 2 compares the k blocks indexed by DQD_Q at the current query with the k blocks indexed by DKD_K at earlier tokens, and averages the states carried by the matching precedents themselves, that is their own B1B_1 entries, into B4B_4. Remark G.5 (The gather covers more positions than the prediction). Condition (i) quantifies over all positions with τ(n)≥1τ(n)≥ 1, a superset of the resolvable queries. Layer 2 reads DKD_K-blocks at every valid earlier key, requiring only that the cell records an observed transition. This key set properly contains the query set via two additions: • Row-final cells (zd=Wd−1,t≥1z_d=W_d-1,t≥ 1) pose no cell query (their successor is a separator, Lemma C.3), but supply a valid observation xt,z∼f(⋅∣Pt,z)x_t,z f(· P_t,z) and must be retained as keys. • Cells with unresolved queries provide valid precedents Pt,zP_t,z regardless of whether their own query Qt,zQ_t,z is resolvable. Conversely, initial-step cells are excluded from both sets, an exclusion the circuit explicitly implements (Remark G.3). Resolvability restricts the downstream prediction (Appendix H), not the representation derived here. In this section, we prove condition (i). In Appendix H, we use only this interface and construct the common Layer-2 match. G.2 Separator gating and finite-softmax error Before giving the two constructions, we isolate two issues common to both. First, separators must be excluded from Layer-1 attention. Second, when a head is intended to select a single routing cell, finite softmax leaves a small amount of mass elsewhere. Separators need excluding because their addresses duplicate cells’. By Lemma C.4(i) a separator carries the virtual index of the cell one step before its successor. A ROW_SEP closing row r of time step t has (τ(n),κ(n))=(t,(r+1,Wd−1)), (τ(n),κ(n) )= (t,\;(r+1,\,W_d-1) ), the last-column cell of the following row, and a TIME_SEP closing step t has (τ(n),κ(n))=(t+1,(0,…,0,Wd−1))(τ(n),κ(n))=(t+1,\,(0,…,0,W_d-1)), the last-column cell of the first row of the following step. In either case the separator shares its virtual spatial-temporal address with an ordinary cell, and both are visible to any sufficiently late query, so a purely positional score cannot tell them apart. Without a gate, a query addressing that cell splits its mass with the duplicate separator. Proposition G.6 (The Layer-1 separator gate). Add −Γ1sn′- _1s_n to the Layer-1 score, implemented by a rank-one term from the constant query coordinate in B0B_0 to the separator indicator in the key. If Γ1≥Λ(R+γ),R≔maxδ∈g(δ)−minδ∈u^d−g(δ)≥ 0, _1\;≥\; \,(R+γ), R _δ g(δ)- _δ∈ u_d-Ng(δ)\;≥\;0, (35) with R the quantity already fixed in (26), then every separator key scores at least Λγ γ below every target key. Separators are then absorbed into the same off-target bound N≠e−ΛγN_≠e^- γ of Corollary E.5 as the remaining non-target keys. Proof. Write the ungated score as ΛG(δ,s) G(δ,s) in the notation of Stage 6 of Corollary E.6, and put m≔minδ∈u^d−g(δ)m _δ∈ u_d-Ng(δ), so that the target floor of case (a) of that stage is Λ(m+λ) (m+λ). A separator key attains at most ΛG≤Λ(m+R+λ) G\;≤\; (m+R+λ ) before the gate: its spatial term is at most maxg=m+R _Gg=m+R by the definition of R, and its temporal term is at most λ, attained when h=1h=1. After subtracting Γ1≥Λ(R+γ) _1≥ (R+γ) its score is at most Λ(m+R+λ)−Λ(R+γ)=Λ(m+λ)−Λγ, (m+R+λ)- (R+γ)\;=\; (m+λ)- γ, which is at least Λγ γ below the target floor. Separators therefore satisfy the same isolation inequality as the non-target cell keys, and Corollary E.5 applies with N≠N_≠ counting both. ∎ Remark. The gate multiplies a token-embedding coordinate which is already present in B0B_0, so it adds no positional coordinate and does not alter the width bounds of the addressing construction. It is query independent and provides no additional spatial resolution. The bound (35) is loose: it charges every separator the worst spatial score on the whole grid. We do not gate initial-step cells here; see Remark G.3. Remark. The weaker choice Γ1=Λ _1= does not support the stated bound. A separator whose address coincides with a target cell’s may also score the target floor Λ(m+λ) (m+λ) of the proof above, so subtracting Λ leaves it only Λ below that floor, for relative weight e−Λe^- , against the e−Λγe^- γ claimed downstream. The two agree only at γ=1γ=1, and γ>1γ>1 occurs on small grids: on the three-cell torus with T=3T=3 the singleton spatial kernel of Lemma E.3(i) has γ=1−cos(2π/3)=3/2γ=1- (2π/3)=3/2, and at Λ=10 =10 and N=12N=12 the true block error e−10≈4.54×10−5e^-10≈ 4.54× 10^-5 exceeds the claimed Ne−Λγ≈3.67×10−6Ne^- γ≈ 3.67× 10^-6. The auxiliary token. Construction I always, and Construction I when a Dirichlet prior is used, prepend the auxiliary token ⋆ of Definition G.2 at position 00. Every term involving ⋆ is either a rank-one product of the query constant 1∈B01∈ B_0 with the key marker μn′ _n , or a value term reading μn′ _n . Since μ vanishes at ordinary tokens, these terms leave every ordinary score and value unchanged. Prepending ⋆ shifts every ordinary position by one, so the layout becomes ρ⋆(t,z)=ρ(t,z)+1 _ (t,z)=ρ(t,z)+1 and the stream length becomes N⋆=N+1N_ =N+1. Each ordinary token keeps the positional features it had before the shift, now stored at column ρ⋆ _ of the table, so the virtual indices κ and τ and every ordinary score are unchanged. When ⋆ is present, every bound below that involves N is read with N⋆N_ in its place. Lemma G.7 (Layer-1 role of ⋆ ). At the key ⋆ , the positional score vanishes because B2=0B_2=0, the content score vanishes because B1=0B_1=0, and the separator gate vanishes because s⋆=0s_ =0. Hence: (a) Construction I. The term Λg⋆⋅1⋅μn′ g_ · 1· _n in WQ(1)⊤WK(1)W_Q^(1) W_K^(1) gives ⋆ the logit Λg⋆ g_ at every query. The value term e⋆μn′e_ _n , with e⋆e_ the last coordinate of B3agg∈ℝM+1B_3^agg ^M+1, gives ⋆ the value e⋆e_ ; ordinary keys contribute nothing to that coordinate. (b) Construction I. Let Λ(mδ+λ) (m_δ+λ) be the target floor of head δ (Stage 6 of Corollary E.6 at =δN=\δ\). The term Λ(mδ+λ−γ)⋅1⋅μn′ (m_δ+λ-γ)· 1· _n in head δ places ⋆ exactly Λγ γ below the target, and its value ιδΠB1x⋆ _δ _B_1x_ is zero. Thus ⋆ is a non-target key covered by Corollary E.5. (c) As a query, ⋆ attends only to itself, and its pattern scratch B3patB_3^pat is zero after Layer 1: in Construction I every head returns ιδΠB1x⋆=0 _δ _B_1x_ =0, and in Construction I this is shown in Step 5 of the proof of Theorem G.10. Lemma G.8 (Per-block error of a single head). Suppose a Layer-1 head places attention mass at least 1−ε¯1- on the routing cell (t−1,z+δ)(t-1,z+δ) and reads values from B1B_1 into one width-V block of B3patB_3^pat. Then that block is an ε¯ -approximate one-hot for e(xt−1,z+δ)e(x_t-1,z+δ). In particular, Corollary E.5 guarantees ε¯≤Ne−Λγ, ≤ Ne^- γ, and hence any prescribed ε¯>0 >0 is achieved whenever Λ≥γ−1log(N/ε¯). ≥γ^-1 (N/ ). Proof. The written block is a non-negative weighted sum of the state one-hots carried by visible cell tokens. The addressed routing cell contributes mass at least 1−ε¯1- to its correct state coordinate, while all remaining attention mass is at most ε¯ , so the block places at most ε¯ on the other V−1V-1 coordinates. Three kinds of key make up that remaining mass, and all are covered. Ordinary cell keys at non-target offsets are Λγ γ below the target by isolation. Separator keys are Λγ γ below it by Proposition G.6, and in addition contribute the zero vector, since a separator has B1=0B_1=0; they can only lower the block’s total mass, never move it to a wrong coordinate. The key ⋆ , when present, is Λγ γ below the target and contributes the zero vector by Lemma G.7(b). The block is therefore non-negative with total mass at most 11, so Definition G.1 asks only for a sub-probability vector. For the scale bound, apply Corollary E.5 with the target set the single addressed cell. Every other visible position is a non-target key, so N≠≤N−1≤N_≠≤ N-1≤ N, giving ε¯≤Ne−Λγ ≤ Ne^- γ and hence the stated condition on Λ . ∎ G.3 Construction I: One head per offset In the first construction, head δ addresses one offset and writes its state into the block reserved for that same offset, so routing and separation happen together. Theorem G.9 (Dedicated-heads gather). Build Layer 1 with h=||h=|U| heads, one head for each δ∈δ , and no MLP, incorporating the separator gate of Proposition G.6. At logit scale Λ , this realizes condition (i) of Definition G.4 with ε¯≤Ne−Λγ, ≤ Ne^- γ, and with dMLP=0,dmodel=(||+2)V+2d+6,dp=2d+3.d_MLP=0, d_model=(|U|+2)V+2d+6, d_p=2d+3. The same holds with the auxiliary token ⋆ configured as in Lemma G.7(b). Proof. Fix δ∈δ . Head δ must reach the key at cell κ(n)+δκ(n)+δ, so it applies Corollary E.6 to the singleton offset set δ≔δ.N_δ \δ\. For a singleton the spatial addressing width is dS=2d_S=2d by Lemma E.3(i), independently of which singleton it is, so all |||U| heads share one spatial table of width 2d2d and differ only through their query-key projections, which rotate the 2×22× 2 blocks (15) by the angle belonging to their own offset. With the two temporal coordinates and the indicator ζn _n of (33), the positional width is 2d+32d+3. At a position n with τ(n)≥1τ(n)≥ 1, head δ therefore places all but at most Ne−ΛγNe^- γ of its attention mass on the cell (τ(n)−1,κ(n)+δ)(τ(n)-1,\;κ(n)+δ), using Proposition G.6 to cover separator keys. Its value projection is WV(1),δ=ιδ∘ΠB1,W_V^(1),δ= _δ _B_1, where ιδ _δ embeds ℝVR^V into the δ-indexed block of B3patB_3^pat. By Lemma G.8, that block is an ε¯ -approximate one-hot for e(xτ(n)−1,κ(n)+δ)e(x_τ(n)-1,\,κ(n)+δ) with ε¯≤Ne−Λγ ≤ Ne^- γ. This argument depends on the query solely through κ(n)κ(n) and τ(n)τ(n), applying to every position with τ(n)≥1τ(n)≥ 1 (both cells and separators) as required by Definition G.4(i). The addressed cells are causally visible in all cases: step t−1t-1 strictly precedes any cell token at step t≥1t≥ 1 (since ρ is order-preserving), and Lemma C.4(i) establishes the same for separators. This guarantees coverage for row-final cells and cells with unresolved queries, both necessary for Layer 2 (Remark G.5). Repeating this independently for every δ∈δ produces all required blocks. Because the heads write to disjoint blocks, no Layer-1 MLP is needed. The residual width is therefore 3⏟B0+V⏟B1+(2d+3)⏟B2+||V⏟B3+V⏟B4=(||+2)V+2d+6. 3_B_0+ V_B_1+ (2d+3)_B_2+ |U|V_B_3+ V_B_4=(|U|+2)V+2d+6. Thus condition (i) of Definition G.4 holds. ∎ G.4 Construction I: A shared head with MLP decoding Construction I uses a single Layer-1 head to serve all offsets in U. Since an attention head outputs a single weighted sum, attending to all routed cells simultaneously would normally destroy their spatial identities. The construction resolves this by splitting the information across weights and values. The state of a routed cell controls its scalar attention weight, while its positional color determines the direction of its value vector. Because the routing cells have distinct colors, they occupy distinct coordinates of the Shared-head aggregate. A fixed reference token carries a known weight through the same softmax, so the MLP can cancel the shared normalization, and the query stores the color expected at each offset. The MLP can therefore select the coordinate belonging to a given offset and recover its discrete state by threshold comparisons. The construction critically relies on the discrete state alphabet. Consecutive states differ by 11, so a half-integer threshold is separated by 1/21/2 from any valid state. The MLP recovers the exact state provided contamination from non-routing cells remains strictly below this margin, alleviating the need for perfectly sparse attention. Layer-1 reference token. Construction I uses the auxiliary token ⋆ of Lemma G.7(a) as a Layer-1 reference for the shared softmax normalization: its logit Λg⋆ g_ is set by the marker term and so carries no temporal factor, and its value is the dedicated coordinate e⋆e_ . Its Layer-2 role is fixed in Appendix H. Theorem G.10 (Shared-head gather). Let Layer 1 have a single head whose value is the own-color block (34), for a coloring c admissible for U with M colors in the sense of Definition F.1; in particular an ordinary cell z′z emits ec(z′)e_c(z ) and a separator emits 00. Let γ be the isolation margin of Corollary E.6 for =N=U, and let nmaxn_ be the largest number of causally visible cells carrying one color. By Corollary F.5(c), nmax≤Tmaxs|c−1(s)|n_ ≤ T _s c^-1(s) , and nmax≤T⌈||/M⌉n_ ≤ T /M if c is equitable. If Λγ≥log(2V(nmax−1)), γ≥ (2V(n_ -1) ), (36) then a one-hidden-layer ReLU MLP of width dMLP≤2||M(V−1)+M+2d_MLP≤ 2|U|M(V-1)+M+2 recovers e(xτ(n)−1,κ(n)+δ)e(x_τ(n)-1,\,κ(n)+δ) for every δ∈δ , at every position with τ(n)≥1τ(n)≥ 1. Hence condition (i) of Definition G.4 holds exactly, with ε¯=0 =0. The positional and residual widths are dp≤dS+3⏟addressing,ζ+||(M−1)+1⏟query addresses+M⏟B2col,dS=O(||dlog||),d_p≤ d_S+3_addressing,\ ζ+ |U|(M-1)+1_query addresses+ M_B_2^col, d_S=O (|U|\,d |U| ), and dmodel=(||+2)V+dp+M+4.d_model=(|U|+2)V+d_p+M+4. Proof. The computation is implemented in five sequential stages. Throughout, write z≔κ(n)z κ(n) and t≔τ(n)t τ(n) for the query’s virtual cell and time step, so that the argument applies verbatim at separator queries as well as at cell tokens. 1. Encode the state in the attention weight. At the query n, the Layer-1 logit of a causally visible key n′n is ℓ(n,n′)=Λ[g(z+u^d−κ(n′))+λh(t−τ(n′))]−Γ1sn′⏟positional+⟨w,ΠB1xn′⟩⏟content,wv=log(v+1). (n,n )= [g (z+ u_d-κ(n ) )+λ\,h (t-τ(n ) ) ]- _1s_n _positional+ w, _B_1x_n _content, w_v= (v+1). (37) The positional part is the spatiotemporal score of Corollary E.6 at =N=U, which is large exactly on the routing cells κ(n′)=z+δκ(n )=z+δ, δ∈δ , in step t−1t-1, together with the separator gate of Proposition G.6. The content part is linear in the one-hot state, equal to log(xτ(n′),κ(n′)+1) (x_τ(n ),κ(n )+1) at a cell key, which is log(xt−1,κ(n′)+1) (x_t-1,κ(n )+1) at a routed cell, and to 00 at a separator, so block-diagonal query-key projections realize (37) without mixing positional and state coordinates. Write wn′w_n for the exponentiated positional part of (37). Every key in step t−1t-1 has h=1h=1 and so carries the same temporal factor eΛλe λ; for a routing cell at offset δ∈δ we absorb that factor into wδ≔eΛ(g(u^d−δ)+λ),w_δ e (g( u_d-δ)+λ ), (38) the positional weight the kernel assigns to the key at offset δ. Let Z denote the softmax partition function over all causally visible keys. The attention weight assigned to the routed cell at offset δ is then (xt−1,z+δ+1)wδZ, (x_t-1,z+δ+1)w_δZ, so the state has been encoded as a scalar factor in the attention weight. Two bookkeeping points carry through the remaining steps. Each wδw_δ is a fixed constant per offset, known when the weights are set, and it carries eΛλe λ inside it; Steps 3 and 4 use wδw_δ only through the ratios wδ/w⋆w_δ/w_ against the reference weight and Zmax/wδZ_ /w_δ, both fixed at the same time. The partition function Z is the one quantity here which the weights cannot know, and the reference coordinate of Step 3 removes it. 2. Encode routed-cell identity in the value. The value projection reads the own-color block (34), WV(1)=ΠB2col,W_V^(1)= _B_2^col, so an ordinary cell z′z outputs its color code ec(z′)∈ℝMe_c(z ) ^M and a separator outputs the zero vector, the block being (1−sn′)ec(κ(n′))(1-s_n )e_c(κ(n )). Separator keys therefore contribute nothing to the aggregate, so this construction attains ε¯=0 =0 exactly, with no separator residue. The reference token outputs an additional basis vector e⋆e_ , so the Shared-head aggregate is a∈ℝM+1.a ^M+1. Because the routed cells z+δz+δ, δ∈δ , have distinct colors, the contribution of each routed cell lands in a different coordinate: a[c(z+δ)]=(xt−1,z+δ+1)wδZ+rδ,a[⋆]=w⋆Z,a[c(z+δ)]= (x_t-1,z+δ+1)w_δZ+r_δ, a[ ]= w_ Z, where w⋆≔eΛg⋆w_ e g_ and rδr_δ is the total contribution from non-routing cells which happen to share the color c(z+δ)c(z+δ). Ignoring rδr_δ for the moment, the desired state is already present in the scalar a[c(z+δ)]a[c(z+δ)]. Two obstacles remain: the common normalization Z is unknown to the MLP, and the MLP must select the color coordinate corresponding to offset δ. 3. Bound contamination and cancel the unknown normalization. Admissibility guarantees distinct colors only among the routing cells, so non-routing cells may still contribute to the same color coordinate; separators cannot, by Step 2. At most nmax−1n_ -1 visible non-routing cells share any given color, where nmaxn_ is the bound of Corollary F.5(c). Each such cell contributes a content factor at most V. Its positional weight wn′w_n is smaller than every routing cell’s by at least e−Λγe^- γ. This is Stage 6 of the proof of Corollary E.6, which puts all three kinds of non-routing key at least Λγ γ below the target floor Λ(m+λ) (m+λ), where m≔minδ∈g(u^d−δ)m _δ g( u_d-δ): a key in step t−1t-1 at an offset outside U by the spatial margin γ, a key in any other time step by the temporal margin, since λγT≥R+γλ _T≥ R+γ by (26), and a separator key by Proposition G.6. Excluding the wrong-time keys is the temporal term’s duty, and (38) carries that term. Writing wmin≔minδ∈wδ=eΛ(m+λ)w_ _δ w_δ=e (m+λ), every non-routing key has wn′≤e−Λγwminw_n ≤ e^- γw_ , and hence wn′≤e−Λγwδw_n ≤ e^- γw_δ for every δ∈δ . Summing over the sharing cells, Zrδ≤V(nmax−1)e−Λγwδ.Zr_δ≤ V(n_ -1)e^- γw_δ. Under (36), Zrδ≤12wδ.Zr_δ≤ 12w_δ. (39) The reference coordinate removes the unknown partition function. For an offset δ, color slot s, and threshold v∈1,…,V−1v∈\1,…,V-1\, define Cδ,s,v≔a[s]−(v+12)wδw⋆a[⋆].C_δ,s,v a[s]- (v+ 12 ) w_δw_ a[ ]. At the target color s=c(z+δ)s=c(z+δ), Cδ,c(z+δ),v=wδZ(xt−1,z+δ−v+12)+rδ.C_δ,c(z+δ),v= w_δZ (x_t-1,z+δ-v+ 12 )+r_δ. Thus, apart from the controlled contamination rδr_δ, the sign of Cδ,c(z+δ),vC_δ,c(z+δ),v tells us whether xt−1,z+δ≥vx_t-1,z+δ≥ v. 4. Use the query’s color address to select the correct slot and threshold it. The query token stores gδ(z)=ec(z+δ)g_δ(z)=e_c(z+δ) in its positional block B2B_2; thus gδ(z)[s]=1g_δ(z)[s]=1 exactly at the color slot for offset δ. Selecting the slot and thresholding its scalar are nonlinear operations. Since the architecture (§3.3) possesses only a single hidden ReLU layer, we implement both within the same hidden units. Letting Zmax≥Z_ ≥ Z be a strict upper bound on the partition function, we define Pδ,s,v≔GδCδ,s,v−Bδ(1−gδ(z)[s]),Gδ≔4Zmaxwδ,Bδ≔Gδ.P_δ,s,v G_δC_δ,s,v-B_δ (1-g_δ(z)[s] ), G_δ 4Z_ w_δ, B_δ G_δ. (40) Use the pair of hidden units ReLU(Pδ,s,v),ReLU(Pδ,s,v−1),ReLU(P_δ,s,v), (P_δ,s,v-1), whose difference is the clamp χδ,s,v=min1,max0,Pδ,s,v. _δ,s,v= \1, \0,P_δ,s,v\\. We claim that ∑s=1Mχδ,s,v=[xt−1,z+δ≥v]. _s=1^M _δ,s,v=1[x_t-1,z+δ≥ v]. First consider a wrong color slot, for which gδ(z)[s]=0g_δ(z)[s]=0. Since a[s]≤1a[s]≤ 1, we have Cδ,s,v≤1C_δ,s,v≤ 1, so Pδ,s,v≤Gδ−Bδ=0.P_δ,s,v≤ G_δ-B_δ=0. Thus every wrong slot contributes zero. At the target slot, the penalty term vanishes. If xt−1,z+δ≥vx_t-1,z+δ≥ v, then xt−1,z+δ−v+12≥12,x_t-1,z+δ-v+ 12≥ 12, and rδ≥0r_δ≥ 0, so Pδ,c(z+δ),v≥4Zmaxwδwδ2Z=2ZmaxZ≥2.P_δ,c(z+δ),v≥ 4Z_ w_δ w_δ2Z=2 Z_ Z≥ 2. The clamp therefore equals 11. If xt−1,z+δ<vx_t-1,z+δ<v, then xt−1,z+δ−v+12≤−12.x_t-1,z+δ-v+ 12≤- 12. Using (39), Cδ,c(z+δ),v≤−wδ2Z+rδ≤0,C_δ,c(z+δ),v≤- w_δ2Z+r_δ≤ 0, so the clamp evaluates to 00. Thus, the MLP recovers every threshold indicator exactly. 5. Recover the one-hot state and clear the temporary aggregate. Threshold indicators determine the discrete state. With the convention χδ,s,V≔0 _δ,s,V 0, coordinate v∈1,…,V−1v∈\1,…,V-1\ of the δ-th pattern block receives ∑s=1M(χδ,s,v−χδ,s,v+1), _s=1^M ( _δ,s,v- _δ,s,v+1 ), while coordinate 00 receives 1−∑s=1Mχδ,s,1.1- _s=1^M _δ,s,1. These are exactly the coordinates of e(xt−1,z+δ)=e(xτ(n)−1,κ(n)+δ)e(x_t-1,z+δ)=e(x_τ(n)-1,\,κ(n)+δ). The constant is supplied by the hidden unit ReLU(1−μn)ReLU(1- _n), which reads the constant and marker coordinates of B0B_0; it equals 11 at ordinary tokens and 00 at ⋆ . At ⋆ the pattern scratch is zero. Since B2=0B_2=0 there, the shared constant of Corollary F.5(b) vanishes and gδ(⋆)=0g_δ( )=0. Since ⋆ attends only to itself, a=e⋆a=e_ , so Cδ,s,v=−(v+12)wδ/w⋆<0C_δ,s,v=-(v+ 12)w_δ/w_ <0 and Pδ,s,v<0P_δ,s,v<0 for all δ,s,vδ,s,v. Every threshold unit and the constant unit therefore vanish at ⋆ . Because z and t denote the query’s virtual cell and time step, recovery holds at every position with τ(n)≥1τ(n)≥ 1 (both cells and separators). Routed cells reside in step τ(n)−1τ(n)-1 and are causally visible due to ρ’s order preservation (t≥1t≥ 1) and Lemma C.4(i) (separators). This fulfills Definition G.4(i) and Remark G.5 entirely. The Shared-head aggregate a is temporary. As a is non-negative, M+1M+1 additional hidden units pass its coordinates unchanged through ReLU and write −a-a back to B3aggB_3^agg. The residual connection clears B3aggB_3^agg, leaving the exact state one-hots in B3patB_3^pat. Finally, the threshold bank uses 2||M(V−1)2|U|M(V-1) hidden units, aggregate cancellation uses M+1M+1, and the constant uses one, giving dMLP≤2||M(V−1)+M+2.d_MLP≤ 2|U|M(V-1)+M+2. The positional table consists of the dS+2d_S+2 spatial-temporal coordinates, the initial-step indicator ζn _n of (33), the ||(M−1)+1|U|(M-1)+1 query-side color-address coordinates, and the width-M own-color block (34), so dp≤dS+3+||(M−1)+1+M.d_p≤ d_S+3+|U|(M-1)+1+M. The residual stream contains 3+V+dp+(||V+M+1)+V3+V+d_p+ (|U|V+M+1 )+V coordinates, yielding dmodel=(||+2)V+dp+M+4.d_model=(|U|+2)V+d_p+M+4. Thus all |||U| pattern blocks are recovered exactly and condition (i) of Definition G.4 holds with ε¯=0 =0. ∎ Remark. The factor M in the one-hidden-layer width stems from performing color selection and state thresholding within a single nonlinear stage. A two-hidden-layer architecture could decouple these (selecting the color first, then thresholding), reducing the width to ||(M+2V−2).|U|(M+2V-2). We present the wider one-hidden-layer construction to match the architecture in §3.3. Corollary G.11 (Grid-independent width bounds). Take c to be the equitable degree-bound coloring supplied by Corollary F.5(d), so that M≤||2−||+1andnmax≤T⌈||/M⌉.M≤|U|^2-|U|+1 n_ ≤ T /M . Then Theorem G.10 holds with dMLP≤2||(||2−||+1)(V−1)+||2−||+3,d_MLP≤ 2|U| (|U|^2-|U|+1 )(V-1)+|U|^2-|U|+3, and, writing m≔||m |U|, dp≤dS+m3−m+5,d_p≤ d_S+m^3-m+5, where dS=O(||dlog||).d_S=O (|U|\,d |U| ). Thus, both widths depend solely on |||U|, V, and d. For the three experimental grids, the periodic colorings of Table 6 yield smaller values than this degree bound; Theorem G.10 holds with those tighter M values. Proof. We obtain the MLP bound by substituting M≤m2−m+1M≤ m^2-m+1 into Theorem G.10. For the positional bound, the color coordinates of Theorem G.10 total m(M−1)+M=(m+1)M−m(M-1)+M=(m+1)M-m, which is increasing in M, so at M=m2−m+1M=m^2-m+1 the sum-of-cubes identity (m+1)(m2−m+1)=m3+1(m+1)(m^2-m+1)=m^3+1 gives (m+1)M−m≤m3+1−m.(m+1)M-m\;≤\;m^3+1-m. Adding the dS+3d_S+3 addressing and indicator coordinates and the single shared constant already counted in m(M−1)+1m(M-1)+1 yields dp≤dS+m3−m+5d_p≤ d_S+m^3-m+5. ∎ Remark. We state the bound m3−m+5m^3-m+5 for precision: since m≥2m≥ 2, m3−m+5≤m3+3m^3-m+5≤ m^3+3 (equality at m=2m=2). Here m≥2m≥ 2 follows from Wd≥2W_d≥ 2 in Definition 1: either ⊋DKU D_K, or DK+u^d=DKD_K+ u_d=D_K, in which case =DKU=D_K is a union of cosets of ⟨u^d⟩ u_d , each of size Wd≥2W_d≥ 2. The own-color and indicator coordinates are therefore absorbed by the grid-independent form in Theorem 7((I)). G.5 The spatial gather interface The two constructions differ only in how they produce the same Layer-1 representation. In Appendix H, we therefore treat them through the following common interface. Corollary G.12 (Spatial gather interface). Either Layer-1 construction realizes condition (i) of Definition G.4, at every position n with τ(n)≥1τ(n)≥ 1 and for every δ∈δ : • Construction I uses |||U| heads and no MLP, with ε¯≤Ne−Λγ, ≤ Ne^- γ, at the widths of Theorem G.9. • Construction I uses one head and a one-hidden-layer separating MLP, with ε¯=0, =0, at the widths of Theorem G.10 and the grid-independent bounds of Corollary G.11. Proof. Immediate from Theorems G.9 and G.10. ∎ Layer 2 also reads the pattern scratch of invalid keys, including positions with τ(n)=0τ(n)=0, where condition (i) makes no claim. The Layer-2 gate requires only the following weaker property there. Lemma G.13 (Pattern scratch at every position). Under either construction, at every ordinary position n other than the final TIME_SEP, including those with τ(n)=0τ(n)=0, every width-V block of B3patB_3^pat is a sub-probability vector. At ⋆ , B3pat=0B_3^pat=0. Proof. The claim at ⋆ is Lemma G.7(c). Construction I. Block δ is ∑n′πn′ΠB1xn′ _n _n _B_1x_n with softmax weights πn′≥0 _n ≥ 0 summing to 11, and each ΠB1xn′ _B_1x_n is a one-hot or zero. Construction I. Fix δ. The wrong-slot bound Pδ,s,v≤0P_δ,s,v≤ 0 of Step 4 uses only a[s]≤1a[s]≤ 1 and so holds at every position. By Corollary F.5(b), gδ(z)g_δ(z) is a one-hot at every ordinary position, so at most one slot sδs_δ has χδ,s,v≠0 _δ,s,v≠ 0; write χv≔χδ,sδ,v _v _δ,s_δ,v and χV≔0 _V 0. Since a[⋆]=w⋆/Z>0a[ ]=w_ /Z>0 and wδ/w⋆>0w_δ/w_ >0, Cδ,sδ,vC_δ,s_δ,v is nonincreasing in v; P is increasing in C and the clamp is nondecreasing, so 1≥χ1≥χ2≥⋯≥χV=01≥ _1≥ _2≥…≥ _V=0. Hence coordinate v≥1v≥ 1 of the block, χv−χv+1 _v- _v+1, is non-negative; coordinate 00, 1−χ11- _1, is non-negative; and the coordinates telescope to (1−χ1)+(χ1−χV)=1(1- _1)+( _1- _V)=1. The block is therefore a probability vector. ∎ G.6 Construction sizes for the experimental settings Table 8 evaluates the two constructions on the three experimental settings of Appendix B.4, at the colorings of Table 6. Three entries need comment. First, the addressing dimension for Construction I is omitted because the bound of Theorem E.4 is vacuous on these grids: at ||=8 =8 and d=2d=2 it exceeds |^|=36 G =36. Four characters suffice to isolate U on ℤ62Z_6^2 (§E.5), and the general bound is useful when ||dlog|| \,d is much smaller than the volume. For d=1d=1 the bounding box equals the routing set, so Lemma E.3(i) applies directly and yields dS≤2d||=8d_S≤ 2d =8 without randomization. Second, the dMLPd_MLP row reports the one-hidden-layer width 2||M(V−1)+M+22 M(V-1)+M+2 of Theorem G.10. The two-hidden-layer alternative of the remark after that theorem would give ||(M+2V−2) (M+2V-2) instead, which is 2424 against 3838 for 1D V=2V=2, 3232 against 7070 for 1D V=3V=3, and 112112 against 206206 for 2D von Neumann. Third, the margin γ and the logit scale Λ belong to Construction I, whose heads address one offset each. There Lemma E.3(i) gives γ=1−cos(2π/Wmax)γ=1- (2π/W_ ), and Lemma G.8 at the block-error threshold on the line above gives Λ≥γ−1log((2k+2)N) ≥γ^-1 ((2k+2)N ). Construction I addresses all of U with a single head, so it has a different margin and asks for (36) instead; Example E.8 works that case out on ℤ62Z_6^2. Table 8: What the two constructions require on the three experimental settings, at the colorings of Table 6. 1D, V=2V=2 1D, V=3V=3 2D von Neumann Construction I (Thm. G.9) heads, dMLPd_MLP 44, 00 44, 00 88, 00 dS=2d_S=2d, dp=dS+3d_p=d_S+3 22, 55 22, 55 44, 77 width of B3=||VB_3= V 88 1212 1616 residual dmodeld_model 2020 2626 3030 block-error threshold 1/(2k+2)1/(2k+2) 1/81/8 1/81/8 1/121/12 margin γ 0.0760.076 0.0190.019 0.50.5 logit scale Λ≥ ≥ 9595 420420 1818 Construction I (Thm. G.10) colors M 44 44 1212 dMLP≤2||M(V−1)+M+2d_MLP≤ 2 M(V-1)+M+2 3838 7070 206206 width of B3agg=M+1B_3^agg=M+1 55 55 1313 Part IV — Layer 2 and end-to-end guarantees Appendix H Layer 2: Bayesian matching and end-to-end guarantees Per Appendix G, Layer 1 endows each query token with one width-V pattern block per offset δ∈δ . Layer 2 then compares the query configuration at the current token against the parent configuration at every preceding token, retrieving the states that follow matching precedents. With exact one-hot pattern blocks, this comparison is immediate: the inner product between two aligned k-block configurations equals the number of agreeing offsets. An exact match attains score k; every non-match scores at most k−1k-1. If the softmax isolates exact matches, equal scores compel it to average their state one-hots, yielding the empirical conditional frequency. An additional token injects the Dirichlet pseudocount, transforming this frequency into the posterior predictive. Finite Layer-1 error perturbs this ideal in two ways: it narrows the score gap between matches and non-matches, and it disperses the scores among true matches, preventing uniform softmax averaging. The Layer-2 scale β amplifies both effects: increasing β suppresses non-matches but exacerbates dispersion within the matched set. This section is structured in six parts. First, we formalize the matching head (§H.1). Second, we prove the exact counting and Dirichlet smoothing identity in the zero-error limit (§H.2). Third, we bound the two finite-error perturbations: the loss of separation (§H.3) and the dispersion among matched scores with its predictive cost (§H.4). Fourth, we configure the key-validity gate based on these bounds (§H.5). Fifth, we balance the perturbations to establish the end-to-end spatial induction theorem (§H.6). Finally, we detail the recipe for setting the finite parameters (§H.7). H.1 The configuration-matching head While the Layer-1 representation stores all offsets in U, the Layer-2 query and key require distinct subsets: the current token exposes the parent configuration of its successor (indexed by DQ=DK+u^dD_Q=D_K+ u_d), whereas an earlier token exposes its own parent configuration (indexed by DKD_K). Definition H.1 (The Layer-2 head). Define the selection projections on B3patB_3^pat ΣQ≔(block u^d+δ)δ∈DK,ΣK≔(block δ)δ∈DK. _Q (block u_d+δ )_δ∈ D_K, _K (block δ )_δ∈ D_K. Thus ΣQxt,z _Qx_t,z and ΣKxt′,z′ _Kx_t ,z are both concatenations of k width-V blocks in the same offset order: the former represents the query configuration of the target z+u^dz+ u_d, and the latter represents the earlier token’s parent configuration. A position n′n is a valid key if it is a cell token with τ(n′)≥1τ(n )≥ 1; otherwise, it is an invalid key. Invalid keys (separators and initial-step cells) record no transitions of f: separators carry no state, while initial-step cells lack a defined parent configuration P0,z′P_0,z and their states are not drawn from f. This matches the restriction t′≥1t ≥ 1 on the counts (8). Write νn′≔sn′+ζn′∈0,1,2, _n s_n + _n \;∈\;\0,1,2\, (41) which is 00 at a valid key and at least 11 at an invalid one; both summands are already present in the stream, s in B0B_0 and ζ in B2B_2 (Definition G.2). For query scale β>0β>0 and key-validity gate Γ2>0 _2>0, define WQ(2)=βΣQ⊕ΠB0,,WK(2)=ΣK⊕(σ⋆Πμ−Γ2Πν), W_Q^(2)=β\, _Q _B_0,1, W_K^(2)= _K ( _ _μ- _2 _ν ), WV(2)=ΠB1+1V⋅(ΠB0,sep+ΠB0,μ). W_V^(2)= _B_1+ 1V1· ( _B_0,sep+ _B_0,μ ). For a valid key (t′,z′)(t ,z ), the score is β⟨ΣQxt,z,ΣKxt′,z′⟩,β _Qx_t,z, _Kx_t ,z , and the value is its state one-hot e(xt′,z′)e(x_t ,z ). For an invalid key, Γ2νn′≥Γ2 _2 _n ≥ _2 is subtracted from this score (Proposition H.7 bounds Γ2 _2). The rank-one term in WV(2)W_V^(2) assigns separators and ⋆ the value V−1V^-11 rather than zero, ensuring the head outputs a probability vector (the readout convention of §H.2). The auxiliary token ⋆ is neither a valid nor an invalid key: its pattern scratch is zero (Lemma G.13) and ν⋆=0 _ =0, so its score is σ⋆ _ at every query. The output is written to B4B_4, without a Layer-2 MLP. The projections ΣQ _Q and ΣK _K do not create new residual coordinates: they only select and reorder blocks already present in B3patB_3^pat. Neither does the gate, since ν is the sum of two coordinates the stream already carries; and neither does the value term, which is rank one. For a fixed query configuration c=Qt,zc=Q_t,z, let ℳt,zM_t,z denote the set of earlier valid keys, that is cell-token positions (t′,z′)(t ,z ) with t′≥1t ≥ 1, whose parent configuration equals c. Its cardinality is ncn_c, matching (8) exactly, and nc,sn_c,s denotes the number of those precedents whose own state is s∈s . The score when Layer 1 is exact. If all selected blocks are exact one-hots, the inner product ⟨ΣQxt,z,ΣKxt′,z′⟩ _Qx_t,z, _Kx_t ,z counts the agreeing offsets in DKD_K. Thus, members of ℳt,zM_t,z score βkβ k, while non-members score at most β(k−1)β(k-1). This integer combinatorial margin persists (albeit degraded) even when Layer-1 blocks are approximate. The gate strength Γ2 _2 is set in §H.5, once the matched-score floor and the separation are available. H.2 Exact counting and Dirichlet smoothing We first analyze the ideal computation, where exact matches receive equal scores and all other positions are excluded. In this limit, the attention head acts as a counter. The following identity governs the hard-attention limit and requires three hypotheses, which an exact gather alone cannot guarantee. While an exact gather ensures the first (equal one-hot configurations yield equal inner products), a finite softmax retains mass everywhere (making the second a strict limit), and the third necessitates a sink token. Theorem H.9 establishes the finite-parameter counterpart, offering an approximation with explicit error bounds. Theorem H.2 (Exact Bayesian matching in the hard-attention limit; Proposition 8). Suppose the Layer-2 head of Definition H.1 satisfies: (H1) it assigns a common score a to all ncn_c matching precedents in ℳt,zM_t,z; (H2) it assigns score −∞-∞ to every other position, non-matching valid keys and invalid keys alike; (H3) for part (i), the sink carries the prescribed value and score. Then: (i) Empirical counting. With value e(xt′,z′)e(x_t ,z ) at precedent (t′,z′)(t ,z ), the head output is 1nc∑(t′,z′)∈ℳt,ze(xt′,z′)=(nc,snc)s∈. 1n_c _(t ,z ) _t,ze(x_t ,z )= ( n_c,sn_c )_s . (i) Dirichlet smoothing. Fix α>0α>0. Add one auxiliary token ⋆ with value 1V 1V1 and score a+log(Vα).a+ (Vα). Then the head output is exactly (nc,s+αnc+Vα)s∈=P^α(⋅∣Qt,z), ( n_c,s+αn_c+Vα )_s = P_α(· Q_t,z), the posterior predictive distribution of Theorem 3. No Layer-2 MLP is required. Proof. For part (i), equal scores induce a uniform softmax over the ncn_c matching precedents; averaging their state one-hots yields the normalized state counts. For part (i), every matching precedent has unnormalized weight eae^a, while ⋆ has weight ea+log(Vα)=Vαea.e^a+ (Vα)=Vα e^a. The total unnormalized mass is therefore (nc+Vα)ea(n_c+Vα)e^a. In coordinate s, the matching precedents contribute nc,sean_c,se^a, while the auxiliary token contributes Vαea⋅(1/V)=αeaVα e^a·(1/V)=α e^a. Hence nc,sea+αea(nc+Vα)ea=nc,s+αnc+Vα. n_c,se^a+α e^a(n_c+Vα)e^a= n_c,s+αn_c+Vα. ∎ The auxiliary token. The Dirichlet sink is the token ⋆ of Lemma G.7. By Definition H.1, its Layer-2 score is σ⋆ _ at every query and its value is V−1V^-11. For α>0α>0 we set σ⋆=a+log(Vα) _ =a+ (Vα). In the deterministic limit α→0α→ 0 the Dirichlet role vanishes, but in Construction I the Layer-1 reference role of Lemma G.7(a) does not, so ⋆ is retained; we then set σ⋆≤a−Δ _ ≤ a- , and ⋆ enters Theorem H.9(i) as an extraneous position. Construction I includes ⋆ only when α>0α>0, with the Layer-1 score of Lemma G.7(b). In either case N counts ⋆ when it is present, and the Layer-1 guarantees are unchanged by Lemma G.7. Readout convention. Every value used by Layer 2 is a probability vector, by construction. Cell keys, valid or not, carry state one-hots; the sink ⋆ carries the uniform vector V−1V^-11; and separators carry V−1V^-11 as well, by the rank-one term added to WV(2)W_V^(2) in Definition H.1. Had separators kept the value 00 that their empty B1B_1 would otherwise supply, the retrieved vector would have had total mass 1−εsep<11- _sep<1 at every finite gate strength, since a finite softmax places positive weight on every unmasked position, and it could not have been read as a distribution without an explicit renormalization. As constructed, the vector written to B4B_4 is a convex combination of probability vectors and so lies exactly in the probability simplex. For stochastic claims we take ΠB4xn(2) _B_4x_n^(2) directly as the predictive distribution; we refer to this as the simplex readout. A standard language-model head softmax(WUxn(2))softmax(W_Ux_n^(2)) preserves the predicted state for WU=ΠB4W_U= _B_4 (since softmax is monotonic), but generally distorts the full distribution. Consequently, our exact distributional bounds invoke the simplex readout, while deterministic argmax statements hold for either. Theorem H.2 identifies the ideal computation. With finite weights, two departures from that ideal remain: leakage from non-matching positions, and score dispersion among the matches. We bound them separately. H.3 Separation of matches from non-matches The first question is whether approximate pattern blocks still leave a positive score gap between true matches and non-matches. Lemma H.3 (Separation of matching configurations). Let P=(P1,…,Pk),P′=(P1′,…,Pk′)∈ℝkV,P=(P_1,…,P_k), P =(P _1,…,P _k) ^kV, where each PhP_h is an ε¯ -approximate one-hot for e(yh)e(y_h) and each Ph′P _h is an ε¯ -approximate one-hot for e(yh′)e(y _h) in the sense of Definition G.1. Write y=(y1,…,yk),y′=(y1′,…,yk′).y=(y_1,…,y_k), y =(y _1,…,y _k). Then ⟨P,P′⟩≥k−2kε¯if y=y′, P,P ≥ k-2k y=y , while ⟨P,P′⟩≤(k−1)+2ε¯if y≠y′. P,P ≤(k-1)+2 y≠ y . Hence the two score ranges are disjoint whenever ε¯<12k+2. < 12k+2. Under the Layer-2 scale β, every matching position then outscores every non-matching position by at least Δ≔β(1−(2k+2)ε¯). β (1-(2k+2) ). Proof. We use two elementary blockwise bounds. First, every block inner product is at most 11. Indeed, since PhP_h has total mass at most 11 and every coordinate of Ph′P _h lies in [0,1][0,1], ⟨Ph,Ph′⟩≤(maxvPh′[v])∑vPh[v]≤1. P_h,P _h ≤ ( _vP _h[v] ) _vP_h[v]≤ 1. (42) Now suppose the two blocks represent the same state, yh=yh′y_h=y _h. Keeping only their common target coordinate gives ⟨Ph,Ph′⟩≥Ph[yh]Ph′[yh]≥(1−ε¯)2≥1−2ε¯. P_h,P _h ≥ P_h[y_h]P _h[y_h]≥(1- )^2≥ 1-2 . If y=y′y=y , summing this bound over all k blocks yields ⟨P,P′⟩≥k−2kε¯. P,P ≥ k-2k . Next suppose yh≠yh′y_h≠ y _h for at least one block h. Since yhy_h is an off-target coordinate for Ph′P _h, Ph′[yh]≤ε¯.P _h[y_h]≤ . Therefore ⟨Ph,Ph′⟩ P_h,P _h =Ph[yh]Ph′[yh]+∑v≠yhPh[v]Ph′[v] =P_h[y_h]P _h[y_h]+ _v≠ y_hP_h[v]P _h[v] ≤ε¯+∑v≠yhPh[v] ≤ + _v≠ y_hP_h[v] ≤2ε¯, ≤ 2 , because PhP_h places at most ε¯ total mass away from its own target coordinate. The remaining k−1k-1 blocks contribute at most 11 each by (42), so ⟨P,P′⟩≤(k−1)+2ε¯. P,P ≤(k-1)+2 . The ranges are disjoint exactly when k−2kε¯>(k−1)+2ε¯,k-2k >(k-1)+2 , equivalently ε¯<1/(2k+2) <1/(2k+2). Multiplying the difference by β gives the stated gap Δ . ∎ For deterministic rules, this gap is all we need: every matching precedent carries the same correct next-state value. Corollary H.4 (Deterministic matching). Let the rule be deterministic, let there be nc≥1n_c≥ 1 matching precedents among at most N visible positions, and let Δ be the gap of Lemma H.3. Assume every other visible position scores at least Δ below every matching precedent, whether it is a non-matching valid key, a separator, an initial-step cell, or ⋆ . Lemma H.3 supplies this for non-matching valid keys; Proposition H.7 of §H.5 supplies it for the invalid keys, and the choice σ⋆≤a−Δ _ ≤ a- for ⋆ ; until then the assumption is carried as a hypothesis. Then the Layer-2 head places mass at least 1−εret1- _ret on the matching precedents, where εret≔(N−nc)e−Δnc+(N−nc)e−Δ. _ret (N-n_c)e^- n_c+(N-n_c)e^- . If u⋆=e(f(Qt,z))u =e(f(Q_t,z)) is their common value, the output y y obeys ‖y^−u⋆‖2≤2εret.\| y-u \|_2≤ 2 _ret. In particular, if Δ>log(22(N−nc)/nc), > (2 2\,(N-n_c)/n_c ), then the predicted state is exactly correct. Proof. Let rmin+r^+_ be the smallest matched score. By hypothesis every other visible position scores at most rmin+−Δr^+_ - , so the total mass w on the matching set satisfies w≥ncermin+ncermin++(N−nc)ermin+−Δ=1−εret.w≥ n_ce^r^+_ n_ce^r^+_ +(N-n_c)e^r^+_ - =1- _ret. All matching precedents carry the same value u⋆u , so the head output can be written y^=wu⋆+(1−w)ρ y=wu +(1-w)ρ for some probability vector ρ. Hence ‖y^−u⋆‖2=(1−w)‖ρ−u⋆‖2≤2(1−w)≤2εret.\| y-u \|_2=(1-w)\|ρ-u \|_2≤ 2(1-w)≤ 2 _ret. The stated condition makes this perturbation smaller than the distance from u⋆u to any decision boundary between two basis vectors, and therefore preserves its argmax . ∎ Remark. The displayed threshold is only a sufficient condition and is not tight. Its role is to provide a finite explicit scale compatible with the statement of Theorem H.9(i). H.4 Matched-score dispersion and predictive error For stochastic rules, mere separation is insufficient. Since matching precedents may carry distinct next states, recovering the true counts requires the softmax to remain nearly uniform within the matched set. Approximate Layer-1 blocks perturb these matched scores. Lemma H.5 (Score dispersion among matches). In the setting of Lemma H.3, define a≔β(k−2kε¯).a β(k-2k ). Every matched score can be written a+ηj,0≤ηj≤η,η≔2βkε¯,a+ _j, 0≤ _j≤η, η 2β k , and every non-matching score is at most a−Δ,Δ=β(1−(2k+2)ε¯).a- , =β (1-(2k+2) ). Proof. For a matching pair, Lemma H.3 gives the lower bound k−2kε¯k-2k , while (42) gives the upper bound k. Hence the matched Layer-2 scores lie in [β(k−2kε¯),βk], [β(k-2k ),β k ], an interval of width 2βkε¯2β k . Taking the lower endpoint as a gives the claimed representation a+ηja+ _j. For a non-match, Lemma H.3 gives score at most β((k−1)+2ε¯)=β(k−2kε¯)−β(1−(2k+2)ε¯)=a−Δ.β ((k-1)+2 )=β(k-2k )-β (1-(2k+2) )=a- . ∎ Layer-1 error thus introduces a tradeoff between: Δ=β(1−(2k+2)ε¯),η=2βkε¯. =β (1-(2k+2) ), η=2β k . A large Δ suppresses non-matches, while a small η maintains uniform weighting among matches. Increasing β scales both simultaneously. We next quantify the cost of the second effect. Lemma H.6 (KL error from matched-score dispersion). In the setting of Theorem H.2(i), suppose the matching scores are a+ηja+ _j with |ηj|≤η| _j|≤η, while the sink remains at a+log(Vα)a+ (Vα). Let pηp_η denote the output after restricting attention to the matching precedents and sink. Then, for every s∈s , pη(s)≥e−2ηP^α(s∣Qt,z),p_η(s)≥ e^-2η P_α(s Q_t,z), and therefore DKL(P^α(⋅∣Qt,z)∥pη)≤2η.D_KL\! ( P_α(· Q_t,z)\, \|\,p_η )≤ 2η. No small-η assumption is required. Proof. The s-th coordinate of the dispersed matched-plus-sink output is pη(s)=∑j:xj=seηj+α∑jeηj+Vα.p_η(s)= _j:x_j=se _j+α _je _j+Vα. Because e−η≤eηj≤eηe^-η≤ e _j≤ e^η and e−η≤1≤eηe^-η≤ 1≤ e^η, the numerator lies in [e−η(nc,s+α),eη(nc,s+α)], [e^-η(n_c,s+α),\;e^η(n_c,s+α) ], while the denominator lies in [e−η(nc+Vα),eη(nc+Vα)]. [e^-η(n_c+Vα),\;e^η(n_c+Vα) ]. Thus pη(s)≥e−2ηnc,s+αnc+Vα=e−2ηP^α(s∣Qt,z).p_η(s)≥ e^-2η n_c,s+αn_c+Vα=e^-2η P_α(s Q_t,z). Taking logarithms and averaging under P^α P_α gives the KL bound. ∎ Remark. Lemma H.5 actually gives ηj≥0 _j≥ 0, in which case the constant can be improved. We keep the symmetric 2η2η form because it makes the perturbation lemma independent of how the matched-score interval is anchored and matches the statement used below. H.5 The key-validity gate With the matched-score floor a and the separation Δ now fixed, we can set the gate strength Γ2 _2 which puts every invalid key under the same ceiling as a non-matching valid key. Proposition H.7 (The Layer-2 key-validity gate). In the notation of Lemma H.5, let a≔β(k−2kε¯)a β(k-2k ) be the matched-score floor and Δ the separation. If Γ2≥βk−a+Δ= 2βkε¯+Δ, _2\;≥\;β k-a+ \;=\;2β k + , (43) then every invalid key scores at most a−Δa- , the same ceiling that Lemma H.5 gives for non-matching valid keys. Moreover every key’s Layer-2 value is a probability vector. Proof. The gate. An invalid key may carry nonzero pattern scratch, meaning its ungated score is not necessarily small (separators inherit virtual cells and receive Layer-1 gathers, while initial-step cells assemble gathers from the cells they can see). However, (42) bounds the score: every block of B3patB_3^pat is a sub-probability vector at every ordinary position, including those with τ(n′)=0τ(n )=0 (Lemma G.13), so each of the k inner products is at most 11, yielding β⟨ΣQxt,z,ΣKxn′⟩≤βk≕Smaxβ _Qx_t,z, _Kx_n \;≤\;β k S_ for every key, valid or not. Since νn′≥1 _n ≥ 1 at an invalid key, its gated score is at most Smax−Γ2≤a−ΔS_ - _2≤ a- by (43). The values. A valid key has sn′=0s_n =0, so its value is ΠB1xn′=e(xt′,z′) _B_1x_n =e(x_t ,z ), a one-hot. A separator has sn′=1s_n =1 and ΠB1xn′=0 _B_1x_n =0, so its value is V−1V^-11. An initial-step cell has sn′=0s_n =0 and carries its own state one-hot e(x0,z′)e(x_0,z ). The token ⋆ has μ⋆=1 _ =1 and ΠB1x⋆=0 _B_1x_ =0, so its value is V−1V^-11. All four are probability vectors. ∎ Remark. Two consequences simplify the remainder of this appendix. First, invalid keys require no separate error budget. Gated below a−Δa- , they become indistinguishable from non-matching valid keys and are absorbed into the N visible positions. Theorem H.9 bounds their mass collectively, eliminating separate εsep _sep bookkeeping. Second, because all values are probability vectors, the head output (a convex combination) lies exactly in the simplex. The readout convention of §H.2 dictates why separators cannot retain the value 00. Like the Layer-1 gate, this mechanism uses a rank-one term over existing stream coordinates, avoiding any width increase. Remark H.8 (The initial-step half of the gate is not optional). Gating separators alone falsifies the end-to-end theorem. Take DK=−1,0,1D_K=\-1,0,1\, =−1,0,1,2U=\-1,0,1,2\, V=2V=2, eight cells, and the constant rule f≡0f≡ 0, on the trajectory x0=11111111x_0=11111111, x1=x2=00000000x_1=x_2=00000000. Query the first cell of x1x_1: its query configuration is 111111, the transition 111↦0111 0 has been observed, so the query is resolvable with nc=1n_c=1 and the answer is 00. Every causally visible cell of the initial time step has state 11, so every Layer-1 head returns e(1)e(1) there, and each of the eight initial-step tokens presents the spurious parent configuration 111111 while carrying its own state 11. Layer 2 sees eight spurious matches valued 11 against one genuine match valued 00, all at the same score, and returns p(1)=8/9p(1)=8/9. This survives at finite parameters meeting every other condition: at Λ=100 =100 and β=20β=20 one has ε¯≤5.15×10−12 ≤ 5.15× 10^-12 and Δ≈20 ≈ 20, far above the threshold log(22(N−nc)/nc)≈4.30 (2 2(N-n_c)/n_c)≈ 4.30 of Theorem H.9(i). The ζ half of ν in (41) removes the eight spurious keys. H.6 End-to-end spatial induction We now have all the pieces of the finite-parameter argument; Layer 1 fixes the per-block error ε¯ , which in turn sets the separation gap Δ between matches and non-matches and the dispersion η within the matched set. The sink token supplies the Dirichlet smoothing. It remains to choose one scale β which suppresses the non-matching mass and bounds the matched-set dispersion at the same time. Theorem H.9 (End-to-end spatial induction; Theorem 9 of the body). Let Layer 1 be either construction of Corollary G.12, at per-block error ε¯ , with the separator gate of Proposition G.6 at strength Γ1≥Λ(R+γ) _1≥ (R+γ). Let Layer 2 be the head of Definition H.1 with scale β and key-validity gate Γ2≥2βkε¯+Δ _2≥ 2β k + , as in Proposition H.7. Write Δ≔β(1−(2k+2)ε¯),a≔β(k−2kε¯), β (1-(2k+2) ), a β(k-2k ), and, whenever ⋆ is present, let it be configured as in Lemma G.7 with Layer-2 score σ⋆ _ . (i) Stochastic rules. Fix κ∈(0,1]κ∈(0,1] and α>0α>0, assume N≥VαN≥ Vα, and include ⋆ with σ⋆=a+log(Vα) _ =a+ (Vα). If Δ≥log4N(nc+Vα)κandε¯≤κ16kΔ, ≥ 4N(n_c+Vα)κ ≤ κ16k , then at every resolvable query, cell token or separator, under the simplex readout, the Layer-2 output p satisfies DKL(P^α(⋅∣Qn)∥p)≤κ.D_KL\! ( P_α(· Q_n)\, \|\,p )≤κ. (i) Deterministic rules. Let the rule be deterministic and take α→0α→ 0, with σ⋆≤a−Δ _ ≤ a- whenever ⋆ is present (always in Construction I). If ε¯<12k+2 < 12k+2 and Δ>log(22(N−nc)/nc), > (2 2\,(N-n_c)/n_c ), then at every resolvable query, cell token or separator, the predicted state is exactly correct. This conclusion holds for either the simplex readout or the standard softmax readout. Remark. Both gate hypotheses are indispensable. Dropping Γ1 _1 to the weaker choice Γ1=Λ _1= breaks the per-block error bound whenever γ>1γ>1; dropping the ζ half of Γ2 _2 makes part (i) outright false, by Remark H.8. Proof. Throughout, call a visible position extraneous if it is neither a matching precedent nor the sink. Three kinds of position are extraneous: non-matching valid keys, separators, and initial-step cells; in part (i), where ⋆ plays no Dirichlet role, ⋆ is extraneous as well. We treat them together, and the gate hypotheses enter only here. Part (i). We separate the error into two terms: bias within the matched-plus-sink set and contamination from the extraneous positions. By Lemma H.5, the matched scores have the form a+ηj,a=β(k−2kε¯),0≤ηj≤η≤2βkε¯,a+ _j, a=β(k-2k ), 0≤ _j≤η≤ 2β k , while every non-matching valid key scores at most a−Δa- . By Proposition H.7, the choice of Γ2 _2 puts every invalid key under the same ceiling a−Δa- . Hence every extraneous position scores at most a−Δa- , and every one of them carries a probability vector as its value. Place the sink at a+log(Vα).a+ (Vα). First remove the extraneous positions and renormalize. Let pηp_η denote the resulting matched-plus-sink output. By Lemma H.6, pη≥e−2ηP^αp_η≥ e^-2η P_α coordinatewise. Now restore them. Let w be their total attention mass and let R be the normalized average of their value vectors, which is a probability vector because each of those values is one. Then p=(1−w)pη+wR≥(1−w)e−2ηP^α.p=(1-w)p_η+wR≥(1-w)e^-2η P_α. Therefore DKL(P^α∥p)≤2η−log(1−w).D_KL\! ( P_α\, \|\,p )≤ 2η- (1-w). (44) We bound the two terms separately. With at most N visible positions in total, the unnormalized mass of extraneous positions cannot exceed Nea−ΔNe^a- . Gating invalid keys proves crucial here: separators and initial-step cells (already counted in N) are forced below this ea−Δe^a- ceiling. Meanwhile, the ncn_c matching keys each carry weight at least eae^a, and the sink carries VαeaVα e^a. w≤Ne−Δnc+Vα≤κ4w≤ Ne^- n_c+Vα≤ κ4 by the first hypothesis. Since κ≤1κ≤ 1, we have w≤1/4w≤ 1/4 and therefore −log(1−w)≤2w≤κ2.- (1-w)≤ 2w≤ κ2. For the dispersion term, β=Δ1−(2k+2)ε¯.β= 1-(2k+2) . The hypotheses imply ε¯≤1/(4k+4) ≤ 1/(4k+4), so the denominator is at least 1/21/2 and therefore β≤2Δβ≤ 2 . Consequently η≤2βkε¯≤4kΔε¯≤κ4,η≤ 2β k ≤ 4k ≤ κ4, using the second hypothesis. Thus 2η≤κ/22η≤κ/2. Substituting the two bounds into (44) gives the claim. For completeness, the implication ε¯≤1/(4k+4) ≤ 1/(4k+4) follows from the stated assumptions. Since nc≤Nn_c≤ N, Vα≤NVα≤ N, and κ≤1κ≤ 1, the first hypothesis gives Δ≥log2 ≥ 2. Hence ε¯≤116kΔ≤116klog2≤14k+4. ≤ 116k ≤ 116k 2≤ 14k+4. Part (i). Resolvability gives nc≥1n_c≥ 1, and by the previous paragraphs every extraneous position, invalid keys included, scores at most a−Δa- ; so does ⋆ , since σ⋆≤a−Δ _ ≤ a- , and its value V−1V^-11 is a probability vector. So Corollary H.4 applies directly with the gap Δ , with its N−ncN-n_c non-matching positions read as the extraneous ones, and returns the correct argmax . For Construction I, choosing the Layer-1 logit scale so that Λγ>log((2k+2)N) γ> ((2k+2)N ) ensures ε¯<1/(2k+2) <1/(2k+2); Construction I has ε¯=0 =0 exactly. ∎ Separator queries. The theorem covers separator queries under the same hypotheses. Two conditions are needed. On the query side, Definition G.4(i) requires the gather at every position with τ(n)≥1τ(n)≥ 1, separators included, and Corollary G.12 discharges it for both constructions; the underlying facts are Lemma C.4(i)–(i), which place the separator’s target cell at κ(n)+u^dκ(n)+ u_d, its k parents in step τ(n)−1τ(n)-1, and those parents at offsets DQ⊆D_Q from κ(n)κ(n). On the query side, Layer 2 reads only the DQD_Q blocks and never the query token’s own state, so a separator query needs nothing further, while a separator key is gated by ν (41) and enters the theorem as an extraneous position. A separator is therefore a legitimate query and an illegitimate key, and the single gate ν separates the two roles. This is the separator entry of Table 5: the same successor rule, positional table and attention heads predict the first cell of a row, so no separate routing construction is required. H.7 Choosing finite parameters The hypotheses of Theorem H.9 couple ε¯ , Δ and β, and one order of choice satisfies them all. Fix the divergence budget κ∈(0,1]κ∈(0,1] and the pseudocount α>0α>0. (1) Take Δ=log(4N/((nc+Vα)κ)) = (4N/((n_c+Vα)κ) ), the smallest value the first hypothesis allows. It depends on the stream length N, the smoothing VαVα, the budget κ and the match count ncn_c; the paragraph on one circuit below removes the dependence on ncn_c. (2) Take ε¯=κ/(16kΔ) =κ/(16k ), the largest per-block error the second hypothesis allows at that Δ . (3) Take β=Δ/(1−(2k+2)ε¯)β= /(1-(2k+2) ), which realizes the prescribed Δ and, by the proof above, satisfies β≤2Δβ≤ 2 , so the dispersion obeys η≤κ/4η≤κ/4. (4) Take Γ1≥Λ(R+γ) _1≥ (R+γ) by Proposition G.6 and Γ2≥2βkε¯+Δ _2≥ 2β k + by Proposition H.7, and σ⋆=a+log(Vα) _ =a+ (Vα). The Layer-1 logit scale comes last, and it is where the two constructions differ. Construction I attains ε¯=0 =0 exactly, so η=0η=0, step (2) is vacuous, the dispersion term drops out of (44), and only the leakage term −log(1−w)- (1-w) survives; any Λ meeting (36) serves. Construction I attains ε¯≤Ne−Λγ ≤ Ne^- γ, so step (2) becomes a condition on Λ , namely Λ≥γ−1log(16kNΔ/κ) ≥γ^-1 (16kN /κ ) by Lemma G.8. For deterministic rules, take α→0α→ 0 and replace step (1) by Δ>log(22(N−nc)/nc) > (2 2(N-n_c)/n_c ), step (2) by ε¯<1/(2k+2) <1/(2k+2), and σ⋆ _ by any value at most a−Δa- ; Construction I then needs Λγ>log((2k+2)N) γ> ((2k+2)N ), as in part (i) of the proof. One query, or one circuit. The recipe above reads ncn_c as the count at the query being bounded, and step (1) gives the smallest Δ meeting the first hypothesis at that query. The weights of a circuit cannot depend on ncn_c, which is a property of the context and is observed at run time. For one fixed circuit which works uniformly over every resolvable query, run the same recipe at the worst case resolvability permits, nc≥1n_c≥ 1. Step (1) becomes Δ=log4N(1+Vα)κ, = 4N(1+Vα)κ, and the deterministic replacement becomes Δ>log(22(N−1)) > (2 2\,(N-1) ); steps (2)–(4) and the Layer-1 logit scale then follow from that Δ unchanged. The count enters only the first hypothesis, and it enters decreasingly, so meeting that hypothesis at nc=1n_c=1 meets it at every resolvable query. No parameter of the model changes with the observed count. Remark. The stochastic inequality characterizes a tradeoff between routing and retrieval. Increasing β widens both the separation gap Δ and the matched-score dispersion η. Consequently, we cannot lower the softmax temperature arbitrarily. For stochastic rules, an excessive logit scale concentrates mass on a strict subset of matching precedents, destroying the uniform weighting required for empirical counting. Part V — Experiments Appendix I Experimental methods and additional results I.1 Data generation and rule splits Trajectory generation. Each trajectory fixes one rule table across all T time steps. Initial cells (t=0t=0) are drawn i.i.d. from 0,…,V−1\0,…,V-1\, and all spatial axes use periodic boundary conditions. The neighborhood configuration (left–center–right for 1D; north–west–center–east–south for 2D von Neumann) is base-V encoded to index the rule table. Deterministic rules return the next cell value directly, whereas stochastic rules return a categorical distribution for sampling. Serialization and masks. In 1D, each time step contributes || cell tokens followed by a TIME_SEP token (omitting the final separator). In 2D, the grid is serialized row by row, with ROW_SEP tokens separating rows and TIME_SEP tokens separating time steps. This stream length is one token shorter than N (Definition C.1), but this final omission affects no query cell. Neither the rule table nor rule ID is provided in the input. Training loss spans the full next-token sequence. Validation and test masks isolate the prediction region (t=T0,…,T−1t=T_0,…,T-1), and reported metrics evaluate only cell-value targets, excluding separators. Coverage filtering. Select evaluation splits apply a trajectory-level coverage filter: candidate trajectories are rejection-sampled until all VkV^k configurations appear within the T0−1T_0-1 observed transitions of the context (t=0,…,T0−2t=0,…,T_0-2). This inclusion criterion guarantees that every scored configuration has been observed in context. Table 9 details filter usage across splits. Table 9: Trajectory coverage filter by split. “Yes” means the split rejection-samples trajectories until all VkV^k neighborhood configurations appear in the context; “No” means no filter. Deterministic runs use five splits (train, val-in without filter, val-in with filter, val-out, test); stochastic runs use three (train, validation, test). The main-text deterministic validation refers to val-out; val-in is diagnostic only and not used for checkpoint selection. Dataset type Train Val-in (no filter) Val-in (filter) Val-out / Val Test Deterministic No No Yes Yes Yes Stochastic No — — Yes Yes Deterministic rule pools. Each deterministic trajectory draws one rule uniformly at random (with replacement across trajectories) from the corresponding split’s rule pool. Training, validation-out, and test rule pools are disjoint at the canonical-rule level. The split is drawn on canonical rules first, then each canonical rule is expanded through its symmetry orbit, so equivalent rules never appear in different splits. ECA V=2,k=3V=2,k=3. The 256256 elementary rules form 8888 canonical classes under reflection, complementation, and their composition. Rules are stratified by Wolfram behavioral classes I–IV before splitting. The canonical-level split is 70/9/970/9/9 (train / val-out / test); expanding each class through its symmetry orbit gives 203/28/25203/28/25 element rules. The val-in split draws rules from the training pool with new initial conditions; the val-in-filter variant restricts to training rules that can generate a full-coverage context. 1D V=3,k=3V=3,k=3. The rule space has 327≈7.6×10123^27≈ 7.6× 10^12 entries and cannot be enumerated. The equivalence relation uses S3S_3 state permutations; a canonical rule is the lexicographically smallest of its six state-permutation variants. Rules are stratified by sorted output histogram, and the entropy of each histogram defines an entropy bin. Rules are sampled to make the resulting canonical set approximately uniform over discrete entropy values. Pool sizes: 3,621,300 training / 122,640 val-out / 122,640 test rules. For low-entropy strata that rarely admit full-coverage contexts, the val-out and test rules are drawn symmetrically from the coverage-feasible subset; the three canonical pools remain disjoint. 2D von Neumann V=2,k=5V=2,k=5. The rule space has 232≈4.3×1092^32≈ 4.3× 10^9 entries. The equivalence relation uses state complementation only. Rules are stratified by folded Langton λ-strata (indexed by min(#1,32−#1) (\#1,32-\#1)). Small strata are enumerated; large strata are sampled at fixed number-of-ones per rule. The canonical pools for training, val-out, and test are disjoint. Near-constant strata contribute val-out and test rules symmetrically from the coverage-feasible subset. After orbit expansion and deduplication, the pools contain 315,859 training / 10,904 val-out / 10,904 test rules. Stochastic rule sampling. Each stochastic trajectory uses a fresh rule table fixed across all T steps. For each configuration c∈[V]kc∈[V]^k, the next-cell categorical distribution pcp_c is drawn independently from Dirichlet(1,…,1)Dirichlet(1,…,1) over [V][V]. As the Dirichlet distribution is continuous, independent tables coincide with probability zero. Consequently, trajectories almost surely use distinct rules, ensuring validation and test trajectories present rules unobserved during training. Rule-table shapes are 8×28× 2 (1D V=2,k=3V=2,k=3), 27×327× 3 (1D V=3,k=3V=3,k=3), and 32×232× 2 (2D VN V=2,k=5V=2,k=5). Dataset sizes. All settings use 50M training trajectories, 500k validation, and 500k test trajectories. The same counts apply to both deterministic and stochastic datasets. Table 10 summarizes the grid, horizon, and context length for each setting. Table 10: Grid and trajectory parameters for each experimental setting. Values shown as “det / stoch” when they differ between the two regimes. Task Rule type Grid G T T0T_0 VkV^k configs 1D V=2,k=3V=2,\;k=3 det / stoch 16 10 / 20 4 / 10 8 1D V=3,k=3V=3,\;k=3 det / stoch 32 / 16 12 / 20 8 / 10 27 2D VN V=2,k=5V=2,\;k=5 det / stoch 6×66× 6 12 / 20 8 / 10 32 I.2 Models and training Tables 11 and 12 give the architecture and training hyperparameters for each setting. All models use a two-layer transformer with learned absolute positional embeddings (n.Embedding). The main text refers to the two first-layer designs as Shared-head (heads=[1,1]=[1,1], mlp=[1,1]=[1,1]) and Dedicated-heads (heads=[H,1]=[H,1], mlp=[0,1]=[0,1]). Table 11: Architecture and training hyperparameters: deterministic settings. Task Arch. heads mlp dmodeld_model dffnd_ffn lr wd β2 _2 ep 1D V=2,k=3V=2,k=3 Shared-head [1,1][1,1] [1,1][1,1] 128 512 10−310^-3 0.2 0.999 3 Dedicated-heads [4,1][4,1] [0,1][0,1] 128 512 10−310^-3 0.2 0.999 3 1D V=3,k=3V=3,k=3 Shared-head [1,1][1,1] [1,1][1,1] 256 1024 5×10−45×10^-4 0.2 0.95 8 Dedicated-heads [4,1][4,1] [0,1][0,1] 256 1024 5×10−45×10^-4 0.2 0.95 8 2D VN V=2,k=5V=2,k=5 Shared-head [1,1][1,1] [1,1][1,1] 1024 4096 10−310^-3 0.2 0.95 5 Dedicated-heads [8,1][8,1] [0,1][0,1] 1024 4096 10−310^-3 0.2 0.95 5 Table 12: Architecture and training hyperparameters: stochastic settings. Task Arch. heads mlp dmodeld_model dffnd_ffn lr wd β2 _2 ep 1D V=2,k=3V=2,k=3 Shared-head [1,1][1,1] [1,1][1,1] 256 1024 10−310^-3 0.2 0.999 15 Dedicated-heads [4,1][4,1] [0,1][0,1] 128 512 10−310^-3 0.2 0.999 8 1D V=3,k=3V=3,k=3 Shared-head [1,1][1,1] [1,1][1,1] 256 1024 5×10−45×10^-4 0.2 0.95 8 Dedicated-heads [4,1][4,1] [0,1][0,1] 256 1024 5×10−45×10^-4 0.2 0.95 8 2D VN V=2,k=5V=2,k=5 Shared-head [1,1][1,1] [1,1][1,1] 1024 4096 5×10−45×10^-4 0.2 0.95 10 Dedicated-heads [8,1][8,1] [0,1][0,1] 512 2048 10−310^-3 0.2 0.95 5 Optimizer and schedule. All models are trained with AdamW (β1=0.9 _1=0.9; β2 _2 as listed). The learning-rate schedule is cosine decay with a linear warmup over 0.4% of total steps. Gradient norms are clipped to 1.0 at every step. Precision and hardware. Training uses bfloat16 automatic mixed precision on 1–4 GPUs; wall-clock time per run ranges from a few hours to about a day. Training objective. The training loss is the average cross-entropy of the next-token prediction over all sequence positions: ℒ=∑b,jmb,j[−logqθ(yb,j∣xb,≤j)]∑b,jmb,j.L\;=\; _b,jm_b,j [- q_θ(y_b,j x_b,≤ j) ] _b,jm_b,j. The targets yb,jy_b,j include both cell-state tokens (0,…,V−1\0,…,V-1\) and row/time separators; the model’s softmax qθq_θ is taken over the full vocabulary. The loss mask mb,j∈0,1m_b,j∈\0,1\ is supplied by the dataset and equals 1 at every position on the training split, so no token is excluded. On the filtered evaluation splits (val-in-filter, val-out, test) the mask is 1 only at positions belonging to the prediction time steps (t≥T0t≥ T_0) and 0 elsewhere, restricting the monitored loss to the region on which the model is scored. Checkpoint selection. Deterministic checkpoints are selected on val-out sequence accuracy (maximized); stochastic checkpoints are selected on DKL(qtrue∥qmodel)D_KL(q_true\|q_model) evaluated on the val split (minimized). Early stopping uses patience 999 and min_delta 0.0005. The best checkpoint is the one where the selection metric last improved by at least min_delta. I.3 Evaluation protocol and metrics All evaluation metrics are computed only over cell-value targets at scored time steps; separator targets are excluded. Deterministic teacher-forced (TF) cell accuracy. At each cell position from t=T0t=T_0 through t=T−1t=T-1, the model predicts the next cell value conditioned on the ground-truth history up to that point. TF cell accuracy is the fraction of correctly predicted cells (argmax of the model’s output versus the ground-truth value). Deterministic teacher-forced (TF) sequence accuracy. The fraction of trajectories in which every scored cell is predicted correctly, under the same teacher forcing as TF cell accuracy. A trajectory counts only if it has no error at any scored position. Deterministic autoregressive (AR) cell accuracy. Starting from the ground-truth context (time steps 00 through T0−1T_0-1), the model predicts each subsequent cell via greedy decoding. Each predicted cell is fed back as input for subsequent predictions. AR cell accuracy is the fraction of generated cells that match the ground-truth trajectory. Stochastic AR cell accuracy. The model generates a single sampled rollout from step T0T_0 onward at temperature 1 (unscaled softmax); cell accuracy is the fraction of sampled cells matching the stored ground-truth trajectory. The ground truth is one realization of a stochastic process, so a correct predictive distribution does not yield accuracy 1. The parenthesized k-gram baseline accuracy comes from an independent posterior-predictive sampling rollout. It matches the sampling procedure of the model’s rollout, and it does not maximize accuracy (Appendix D.2). The k-gram predictor starts from the same T0T_0-step ground-truth prefix and samples each cell from the empirical conditional distribution given by causal k-gram counts with add-one smoothing. Both rollouts are scored against the same stored ground-truth trajectory. Stochastic AR DKL(qkgram∥qmodel)D_KL(q_kgram\|q_model). At each cell in the model’s own autoregressive rollout, before sampling that cell’s value: (1) qmodelq_model is the softmax over the first V output logits, corresponding to the cell states; (2) qkgramq_kgram is computed from causal counts in the model-generated history up to that point, with add-one smoothing. The KL divergence is micro-averaged over all scored cells and trajectories. This k-gram reference is conditioned on the model’s own history and is not taken from the independent k-gram rollout. Taking the softmax over the first V logits is equivalent to taking the full-vocabulary softmax and renormalizing its cell-state probabilities. During autoregressive generation, separator tokens are inserted deterministically at their prescribed positions rather than sampled from the model. Stochastic TF cell accuracy. Teacher-forced cell accuracy for stochastic rules uses argmax of the model’s softmax over the first V logits, compared against the ground-truth cell value. It is reported with the k-gram baseline in parentheses. Stochastic TF DKLD_KL. Two divergences are reported under teacher forcing, both micro-averaged over scored cells. DKL(qkgram∥qmodel)D_KL(q_kgram\|q_model) measures how closely the model’s distribution matches the k-gram estimate when both are conditioned on the ground-truth history. DKL(qtrue∥qmodel)D_KL(q_true\|q_model) compares the model against the conditional distribution of the rule which generated the trajectory. Seeds and rollouts. All evaluations use random seed 42. One AR rollout is generated per trajectory (both for the model and for the k-gram baseline). The reported values are micro-averages over 500k test trajectories. I.4 Full predictive results Tables 13 and 14 expand the compact main-text Table 1 with additional metrics. Table 13: Deterministic evaluation: full metrics on held-out test rules. Task Arch. TF seq acc TF cell acc AR cell acc 1D V=2,k=3V=2,\;k=3 Shared-head 0.9990 1.0000 0.9999 Dedicated-heads 0.9994 1.0000 1.0000 1D V=3,k=3V=3,\;k=3 Shared-head 0.9994 1.0000 1.0000 Dedicated-heads 0.9989 1.0000 1.0000 2D VN V=2,k=5V=2,\;k=5 Shared-head 1.0000 1.0000 1.0000 Dedicated-heads 0.9989 1.0000 0.9999 Table 14: Stochastic evaluation: full metrics on held-out test trajectories. TF KL columns report teacher-forced divergence against the k-gram and true-rule baselines. TF KL TF cell acc AR Task Arch. kg∥\|m true∥\|m (kgram) cell acc (kgram) KL kg∥\|m 1D V=2,k=3V=2,k=3 Shared-head 0.0020 0.0185 0.7491 (0.7499) 0.5496 (0.5485) 0.0019 Dedicated-heads 0.0046 0.0211 0.7469 (0.7499) 0.5488 (0.5485) 0.0044 1D V=3,k=3V=3,k=3 Shared-head 0.0026 0.0881 0.5669 (0.5674) 0.3476 (0.3475) 0.0026 Dedicated-heads 0.0004 0.0859 0.5675 (0.5674) 0.3475 (0.3475) 0.0004 2D VN V=2,k=5V=2,k=5 Shared-head 0.0014 0.0300 0.7345 (0.7351) 0.5201 (0.5197) 0.0013 Dedicated-heads 0.0033 0.0319 0.7333 (0.7351) 0.5191 (0.5197) 0.0038 All deterministic models exceed 0.998 TF sequence accuracy. Among the stochastic metrics, the gap between DKL(qkgram∥qmodel)D_KL(q_kgram\|q_model) and DKL(qtrue∥qmodel)D_KL(q_true\|q_model) reflects the estimation error of the k-gram approximation: the first measures the model against an estimate built from the same context the model sees, the second against the rule which generated it. I.5 Attention-alignment analysis For each scored query cell, we measure the fraction of attention mass assigned to the positions predicted by the corresponding construction. For L1, the target set consists of the routing cells that carry the query configuration. For L2, the target set consists of the matching precedents, the earlier cells whose own parent configuration is a matching configuration for the query. Aggregation. For a single query, the L1 score is computed per head as the sum of attention weights over the target positions, and the per-head scores are then averaged across heads. The L2 layer uses a single head, so the L2 score is the sum of attention weights over the target positions. The reported values are micro-averages of these per-query scores across all scored queries and trajectories. Trajectories. Attention weights are extracted under teacher forcing from 20,000 test trajectories sampled uniformly without replacement from the test split. I.6 Attention ablation We test whether the routing cells and matched precedents identified by the construction are functionally used by the model. For each scored query, we intervene on one attention row and measure the effect on next-token prediction. Four intervention conditions are compared against the unablated (No ablation) baseline: (1) L1 routing cells: the attention weights of the L1 head at the query’s routing cells are set to zero and the row is renormalized; (2) L1 random: the same number of L1 attention weights are zeroed at random positions in the same time step, as a matched control; (3) L2 matched precedents: the L2 attention weights at earlier cells with a matching parent configuration are zeroed and the row is renormalized; (4) L2 random: the same number of L2 attention weights are zeroed at random non-matching completed cells. For architectures with multiple L1 heads, the L1 intervention is applied per head. Random controls are averaged over three seeds; queries for which a disjoint random set cannot be formed are left unmodified. Interventions are applied on the same 20,000 test trajectories as the alignment analysis, and we report TF cell accuracy under each condition. I.7 Layerwise probe protocol Probe targets. We train linear probes on frozen post-residual representations to test what information is linearly accessible at each network stage. Two targets are probed: 1. Neighborhood configuration: a classification target. For a scored target cell xt,zx_t,z at serialized position m, we extract the representation at the preceding query position n=m−1n=m-1 and pair it with the target cell’s parent configuration Pt,zP_t,z. For a first-column target, the query position is the preceding separator. There are VkV^k possible configurations. The probe is a linear classifier (logistic regression) and we report balanced accuracy (macro-averaged over configurations). 2. k-gram predictive distribution: a distributional target. The target distribution over the next cell value is computed from causal k-gram counts in the trajectory prefix with add-one smoothing. The probe is a multinomial logistic regression trained to minimize DKL(qkgram∥qprobe)D_KL(q_kgram\|q_probe). The plotted metric is 1−DKL(qkgram∥qprobe)/DKL(qkgram∥Uniform([V]))1-D_KL(q_kgram\|q_probe)/D_KL(q_kgram\|Uniform([V])): a score of 0 means the probe predicts no better than uniform; 1 means exact recovery of qkgramq_kgram. Extraction points. Representations are extracted at five post-residual stages: after embedding, after L1 attention, after L1 MLP, after L2 attention, and after L2 MLP. Each extraction is the full residual stream after the corresponding sub-layer (after the residual connection). Probe model and training. The configuration probe uses sklearn.linear_model.LogisticRegression with hard configuration labels and L2 regularization, solved by L-BFGS. The predictive-distribution probe uses a custom multinomial logistic regression fit with PyTorch L-BFGS, soft-label cross-entropy, and L2 regularization; its data-fit term minimizes DKL(qkgram∥qprobe)D_KL(q_kgram\|q_probe) up to a constant independent of the probe. For both probes, the regularization strength C is selected on the probe validation fold from a grid search. The maximum iteration count is 500 for hyperparameter search and 2500 for the final refit; convergence is determined by the L-BFGS tolerance. ECA probe split (rotating 5-fold). The ECA test rule pool contains 25 expanded rules from 9 canonical Wolfram classes. A fixed 60/20/20 split would place only 5 rules in the probe test fold, and the reported probe score would depend heavily on which 5 rules are picked. To eliminate this rule-level nuisance variability, ECA uses a rotating 5-fold split: the 25 test rules are partitioned into 5 groups of 5, and each fold uses 15 rules for training, 5 for validation, and 5 for testing. Every rule appears once as a test rule and once as a validation rule across the 5 folds. Reported scores are averaged across folds. Other deterministic settings (V=3, 2D VN). The 1D V=3,k=3V=3,k=3 and 2D VN test pools contain thousands of rules, so a single fixed 60/20/20 rule-level split is already well-averaged and no rotation is used. Stochastic probe splits. Because each stochastic trajectory has a unique rule, the probe split is a fixed 60/20/20 split over trajectories. The rule table bytes are hashed to assign a rule ID per trajectory, and the same splitting logic as for deterministic probes is applied. Balancing. For deterministic probes, cells are balanced across neighborhood configurations by per-label stratified subsampling. For stochastic probes, the target is the causal k-gram predictive distribution on the trajectory prefix. I.8 Representation visualizations with t-SNE Figure 5 shows t-SNE embeddings of frozen residual-stream representations from the Shared-head model on deterministic 1D V=2,k=3V=2,k=3 (checkpoint from Table 11: heads [1,1][1,1], mlp [1,1][1,1], dmodel=128d_model=128). Activation collection. Representations are extracted from 6000 test-split trajectories on the ECA test-rule pool. For each of the five post-residual stages (embedding, L1 attention, L1 MLP, L2 attention, L2 MLP), we retain 800 points per neighborhood configuration, giving 8×800=64008× 800=6400 points per stage. Within each configuration, points are stratified by target value (400 per configuration × target). Sampling uses seed 42. Embedding. Each stage is embedded independently. The (6400,128)(6400,128) activation matrix for a stage is first reduced to 50 dimensions by PCA, then to 2 dimensions by t-SNE with perplexity 30, PCA initialization, automatic learning rate, 1000 iterations, and random seed 42; other t-SNE options are the scikit-learn defaults (Euclidean metric, Barnes–Hut, angle 0.5, early exaggeration 12). Figure layout. Each of the five stages occupies one column of a 2×52× 5 panel grid; the top row colors points by neighborhood configuration and the bottom row colors by output value. Point plotting order is shuffled with a separate seed to avoid systematic overplotting. Additional t-SNE plots. We extend the main-text t-SNE to three further settings that cover the axes not shown in the body: Dedicated-heads deterministic 1D (architecture comparison, Figure 6), Shared-head stochastic 1D (stochastic regime, Figure 7), and Shared-head 2D VN (multidimensional regime, Figure 8). These t-SNE plots are intended as qualitative visualizations. Each stage is projected from a high-dimensional representation into two dimensions, so visible distances and clusters need not faithfully reflect the original representation. In particular, a lack of clear clusters does not imply that the relevant information is absent. We rely on the linear probes for quantitative evidence that the configuration and predictive distribution are decodable at each stage. Figure 6: t-SNE of frozen residual-stream representations from the Dedicated-heads model on deterministic 1D V=2,k=3V=2,k=3. Top row: colored by neighborhood configuration. Bottom row: colored by the ground-truth output value. Under the Dedicated-heads construction, the configuration should become accessible after L1 attention rather than after the L1 MLP. Figure 7: t-SNE of frozen representations from the Shared-head model on stochastic 1D V=2,k=3V=2,k=3. Top row: colored by neighborhood configuration. Bottom row: colored by the model’s predicted P(y=1)P(y=1) at the corresponding query position. Because rules are drawn from a continuous Dirichlet prior, the output value at a fixed configuration is a sample from the true conditional distribution, so the model’s predictive distribution varies continuously across queries with the same configuration. Figure 8: t-SNE of frozen representations from the Shared-head model on deterministic 2D von Neumann V=2,k=5V=2,k=5. Top row: colored by neighborhood configuration. Bottom row: colored by the ground-truth output value. The larger neighborhood (k=5k=5, Vk=32V^k=32 configurations) is harder to display in two dimensions than the ECA case; per-configuration clusters are correspondingly less separated. I.9 Qualitative rollout setup for Figure 1 Figure 1 uses two checkpoints trained separately for visualization purposes, one on the deterministic 1D V=2,k=3V=2,k=3 setting and one on the stochastic 1D V=2,k=3V=2,k=3 setting. Both checkpoints are trained on longer trajectories and a wider grid than the main-text models in order to display long rollouts at a legible scale. Wolfram Rule 110 and the Stavskaya rule are excluded from the training rule pools of the two respective checkpoints, so the trajectories shown in Figure 1 come from rules the models have never seen. These checkpoints are used only for Figure 1: none of the predictive results in Table 1, the attention-alignment analysis, or the linear-probe experiments use them. Table 15 reports their training and evaluation configurations. Table 15: Configuration of the visualization checkpoints used for Figure 1. The deterministic panel uses greedy decoding; the stochastic panel uses temperature-1 sampling, and the displayed values are per-cell probabilities of state 1. Deterministic (Rule 110) Stochastic (Stavskaya) Task 1D V=2,k=3V=2,k=3 1D V=2,k=3V=2,k=3 Training ||,T,T0 ,T,T_0 64,64,1264,64,12 64,64,1264,64,12 Plotted ||,T,T0 ,T,T_0 64,64,1264,64,12 64,64,1264,64,12 heads / mlp [4,1]/[0,1][4,1]/[0,1] [1,1]/[1,1][1,1]/[1,1] dmodeld_model / dffnd_ffn 512/2048512/2048 512/2048512/2048 lr, wd, epochs 5×10−45×10^-4, 0.2, 10 10−310^-3, 0.2, 8 Batch (gbs), hardware 1024, 2×A6000 DDP 1024, 2×B300 DDP Checkpoint selection val-out seq acc (max) DKL(qtrue∥qmodel)D_KL(q_true\|q_model) (min) Decoding at plotted step greedy argmax Bernoulli sampling at temperature 1 Interpreting the stochastic panel. The Ground Truth column displays one sampled trajectory. The Autoregressive prediction column conditions on the model’s own sampled history, precluding exact per-cell reproduction even for a Bayes-optimal predictor. The Teacher-forced prediction column conditions on the ground-truth history, plotting the predictive probabilities against which the reference trajectory can be evaluated.