PaperlayerView exact revision on arXiv

Source-linked AI summary

Spatial Induction Heads: In-Context Learning of Multidimensional Cellular Automata

Kimia Kazemian, Menghan Xu, John Thickstun, Sarah Dean

arXiv:2610.09124v1cs.LGcs.AI

TL;DR

Existing induction-head theory assumes relevant context is contiguous, whereas serialization scatters spatial neighbors. This paper introduces a gather-and-match circuit for learning hidden cellular-automaton rules from flattened trajectories. Trained two-layer transformers generalize to unseen rules, with near-perfect deterministic accuracy and stochastic KL below 0.005 nats.

  • Problem

    Induction-head theory assumes contiguous context, leaving open how transformers gather spatially scattered neighbors and infer rules without coordinate-based spatial bias.

    Source: §1 · pp. 1–2

  • Method

    The paper studies two-layer transformers on flattened cellular-automaton trajectories and introduces a circuit that gathers spatial dependencies before matching configurations against precedent.

    Source: §1 · p. 2

  • Results

    Across three settings, models generalize to held-out rules: deterministic rules reach near-perfect cell accuracy under teacher forcing and autoregressive rollout, while stochastic autoregressive KL values are below 0.005 nats.

    Source: §5.2 · p. 8

  • Takeaways & Limitations

    Separating spatial routing from precedent matching provides a framework for understanding induction mechanisms in data with spatial structure.

    Source: §6 · p. 9

    The analysis focuses on cellular automata with finite-state local dynamics, and its theoretical analysis focuses on resolvable queries.

    Source: §3.4 · p. 5, §6 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

Induction-head theory assumes a contiguous context, but serialization scatters spatial neighbors across a token stream. The paper studies how transformers gather those neighbors and infer unknown cellular-automaton rules from flattened trajectories.

1 INTRODUCTION

  • Existing induction-head accounts retrieve a contiguous context, leaving unexplained how transformers assemble spatial neighborhoods scattered by serialization.The paper frames this as two questions: how to gather the scattered tokens and how to infer the rule without coordinate-based spatial bias.Source: §1 · pp. 1–2
  • The study uses multidimensional stochastic cellular automata whose hidden local kernel is resampled for each trajectory, requiring in-context inference.Two-layer transformers are evaluated on flattened trajectories, including held-out deterministic Rule 110 and stochastic Stavskaya.Source: §1 · p. 2
  • The spatial induction head gathers required spatial dependencies in Layer 1, then matches the resulting configuration against precedent in Layer 2.The paper also derives a closed-form Bayes-optimal predictor for the task.Source: §1 · p. 2
  • Two gather constructions use positional frequencies independent of grid volume and trajectory horizon, while the matching layer implements Bayesian counting.The paper reports that the circuit can approximate the Bayesian posterior for stochastic rules and predict exactly for deterministic rules.Source: §1 · p. 2
  • Experiments on 1D and 2D cellular automata show generalization to held-out rules, with attention maps and probes supporting the proposed gather-and-match computation.The paper also reports that the models surpass prior cellular-automaton in-context-learning results.Source: §1 · p. 2

2 RELATED WORK

Related work connects the paper to transformer studies of automata, induction heads and Bayesian accounts of in-context learning, while distinguishing its focus on spatially scattered dependencies.

Transformers for automata and dynamical systems

  • Prior cellular-automaton studies differ in whether they test unseen-rule generalization: Burtsev (2024) does, while Liu et al. (2022) train per automaton and Berkovich et al. (2025) provide the rule in the prompt.Other work studies deterministic finite automata, discretized chaotic systems and hidden Markov processes without identifying a circuit for spatially scattered dependencies.Source: §2 · p. 3

Induction heads and Markov-chain ICL

  • Induction-head theory covers k-order Markov chains, but serialized cellular automata scatter relevant neighbors, requiring gathering before the usual induction computation.The paper relates probabilistic cellular automata to locally interacting Markov chains.Source: §2 · p. 3

Bayesian and algorithmic views of in-context learning

  • Bayesian accounts frame in-context learning as approximate posterior inference, while algorithmic accounts characterize implemented learning procedures; this paper addresses spatial structure and the estimator computed.In its stochastic cellular-automaton setting, the Bayes predictor is a smoothed count represented by the matching head.Source: §2 · p. 3

Spatial structure in transformers

  • Unlike grid architectures that supply geometry explicitly, the paper studies flattened inputs and learned one-dimensional positions without explicit geometric structure.Prior vision-transformer work reports that learned embeddings recover row–column structure.Source: §2 · p. 3

3 THE TASK AND THE ROUTING PROBLEM

The section defines a flattened cellular-automaton prediction task and the routing problem it creates, then specifies the transformer and Bayes target used to study it.

3.1 CELLULAR AUTOMATA

  • Each trajectory evolves on a finite-state torus under a local kernel that maps a neighborhood configuration to a next-state distribution; the kernel is drawn anew from a Dirichlet prior and hidden from the model.The model must infer the kernel from earlier occurrences within the trajectory; deterministic rules are also considered as the prior’s α → 0 limit.Source: §3.1 · pp. 3–4

3.2 SEQUENCE FLATTENING AND SPATIAL ROUTING

  • Row-major serialization flattens each trajectory into one token stream, preserving innermost-axis adjacency while scattering other neighbors; each query must reach both target-parent offsets DQ and precedent-parent offsets DK.The required routing set is U = DK ∪ DQ, with DQ = DK + successor offset.Source: §3.2 · p. 4

3.3 THE MODEL

  • The studied model is a two-layer causal decoder-only transformer with learned absolute positional embeddings and no geometric structure supplied by its positional table.Figure 2 depicts Layer 1 gathering routing cells and Layer 2 retrieving earlier cells with matching parent configurations.Source: §3.3 · pp. 4–5, Figure 2 · p. 5

3.4 RESOLVABLE QUERIES AND THE BAYES TARGET

  • For a query configuration, the Bayes-optimal predictive distribution depends on earlier matching configurations and their successor-state counts; Section 4 focuses on queries whose configuration has occurred before.An uncovered configuration has no observations for its kernel row, so its posterior predictive reduces to the prior mean 1/V.Source: §3.4 · p. 5

4 SPATIAL INDUCTION HEADS: CONSTRUCTION AND OPTIMALITY

Spatial induction separates spatial routing from precedent matching: one layer assembles the relevant neighborhood, and another compares it with earlier configurations. The circuit’s matching stage implements Bayesian counting, while two gather constructions route spatial context with positional width independent of grid volume and trajectory horizon.

4.1 THE SPATIAL INDUCTION HEAD

  • A spatial induction head gathers the query’s neighborhood in Layer 1, then matches it against earlier configurations and aggregates their successors in Layer 2.The query reads offsets DQ, while earlier keys read offsets DK.Source: §4.1 · pp. 5–6

4.2 TWO CONSTRUCTIONS OF THE GATHER

  • Two gather constructions route the required spatial cells with positional width independent of grid volume and trajectory horizon.Dedicated heads keep offset states separate directly; a shared head uses an MLP to separate them after joint routing.Source: §4.2 · p. 6

4.3 MATCHING AND BAYES-OPTIMAL PREDICTION

  • Hard-attention matching averages the successors of matching precedents to recover empirical transition counts, and a prior token yields the Dirichlet posterior.The prior token adds α to each state count.Source: §4.3 · pp. 6–7
  • The end-to-end circuit can approximate the Bayes posterior arbitrarily closely for stochastic rules and predict exactly for deterministic rules.The finite-softmax analysis accounts for nonmatching attention mass and errors in the gathered blocks.Source: §4.3 · p. 7

5 EXPERIMENTS

Two-layer transformers trained on cellular-automaton trajectories generalize to held-out rules across three one- and two-dimensional settings. Attention ablations and layerwise probes provide evidence consistent with the predicted gather-and-match computation.

5.1 EXPERIMENTAL SETUP

  • Models receive flattened trajectories generated by unknown rules and are evaluated on held-out rules in three settings, with every scored query made resolvable by rejection sampling.The settings are 1D V=2, k=3; 1D V=3, k=3; and 2D von Neumann V=2, k=5.Source: §5.1 · pp. 7–8

5.2 RESULTS

  • Deterministic models reach near-perfect cell accuracy, while stochastic models match the k-gram baseline in AR cell accuracy and all AR KL values are below 0.005 nats.These held-out-rule results hold across all three settings and both architectures.Source: Table 1 · p. 7, §5.2 · p. 8
  • Masking attention to theory-predicted routing cells or matching precedents reduces cell accuracy across all three settings, while random-cell controls have little effect.Both architectures also place substantial attention mass on the predicted positions.Source: §5.2 · p. 8, Figure 3 · p. 8
  • Linear probes match the predicted layerwise structure: configurations become readable after the gather stage, and predictive distributions after Layer-2 attention.The configuration target is readable after the L1 MLP in Shared-head models and after L1 attention in Dedicated-heads models.Source: §5.2 · pp. 8–9, Figure 4 · p. 9

6 CONCLUSION

The paper presents spatial induction as a gather-and-match account of in-context learning for spatial dependencies, with theoretical constructions and experiments on cellular automata. Its analysis is confined to finite-state local dynamics, while broader spatial-data applications are framed as a possible framework.

6 CONCLUSION

  • Experiments on 1D and 2D cellular automata generalize to held-out rules and provide mechanistic evidence consistent with gather-and-match computation.In a deterministic 1D visualization, representations cluster by neighborhood configuration after the L1 MLP and by output value after L2 attention.Source: §6 · p. 9, Figure 5 · p. 9
  • The analysis focuses on finite-state cellular automata as a tractable setting for isolating spatial induction.The authors frame the routing-and-matching construction as a framework for understanding induction mechanisms in more general spatial data.Source: §6 · p. 9

A ROADMAP AND READING PATHS

The appendices provide topic-based reading paths and organize the formal setup, constructions, experiments, and notation. The notation sections establish conventions, list symbols and their points of introduction, and flag overloaded symbols.

A ROADMAP AND READING PATHS

  • The roadmap divides the appendices among task formalization, mathematical foundations, the two architecture layers, and experimental methods.Appendix E covers grid-independent spatial addressing, F shared-head colorings, G spatial gathering, and H Bayesian matching and guarantees.Source: A ROADMAP AND READING PATHS · p. 14
  • The shortest path through the main result runs from the gather theorems and Layer 2 interface to Bayesian counting and the end-to-end guarantee.The appendices also offer topic-based paths for circuit construction, mathematical foundations, and the formal problem setting.Source: A ROADMAP AND READING PATHS · pp. 14–15

B.2 SYMBOLS

  • Table 3 collects symbols and where they are defined; the conventions section also directs readers to symbol references and task-specific parameter settings.The listed symbols cover serialization, routing, model components, widths, and coloring notation.Source: B NOTATION AND CONVENTIONS · p. 15, Table 3 · p. 15, §B.2 · p. 16

B.1 CONVENTIONS

  • Coordinates, states, time steps, sequence positions, and residual blocks are 0-indexed, while dimensions, offsets, and heads are 1-indexed.Grid arithmetic is modulo each side length, so the grid is a torus.Source: §B.1 · p. 15

B.3 OVERLOADED NOTATION

  • Several symbols are overloaded, with the surrounding context distinguishing their meanings; no single equation mixes distinct definitions of the same symbol.The appendix notes, for example, that c can denote a configuration or a coloring, and κ can denote a virtual cell or a divergence budget.Source: §B.3 · p. 17

B.4 THE EXPERIMENTAL SETTINGS

The appendix specifies three cellular-automaton task settings and formalizes how their grids become causal token streams. Virtual indexing handles separator queries within the same spatial-target convention as ordinary queries.

B.4 THE EXPERIMENTAL SETTINGS

  • The experiments cover binary 1D, ternary 1D, and binary 2D von Neumann neighborhoods.The stochastic experiments use the same neighborhood types as the deterministic experiments, with task parameters specified separately.Source: §B.4 · p. 18

C.1 FORMAL SERIALIZATION AND INDEXING

  • Cells are serialized in row-major order with a separator after each innermost row, giving a stream length of N = T(|G| + |G|/Wd).The mapping from cells to sequence positions preserves their order.Source: §C.1 · pp. 18–19

C.2 BOUNDARY AND SEPARATOR QUERIES

  • Virtual indices assign a separator the time step and cell index needed to treat its following cell as the prediction target.A row separator predicts a cell in its own time step, while a time separator predicts the first cell of the next step.Source: §C.1 · p. 19, §C.2 · pp. 20–21
  • Separator queries for CA-generated cells have causally visible parents and require no spatial offsets beyond the routing set already defined.Initial-condition separators are excluded because their successor cells have no CA parents.Source: §C.2 · p. 20

C.3 LIMITS OF DISPLACEMENT-ONLY POSITIONAL BIASES

On a torus, wraparound makes spatially desired cells appear at inconsistent sequence displacements. Consequently, displacement-only positional biases cannot strictly isolate the routing set at every query under the theorem’s stated conditions.

C.3 LIMITS OF DISPLACEMENT-ONLY POSITIONAL BIASES

  • Periodic wraparound can force incompatible score rankings, preventing a fixed displacement-only bias from isolating desired routing cells at every query.The theorem treats strict one-layer isolation; it does not rule out models using additional spatial information or multiple layers.Source: §C.3 · pp. 21–22
  • In one dimension, the obstruction applies when the routing set contains specified negative and positive offsets; in dimensions of at least two, it applies when a parent offset moves along an outer axis.The theorem’s stated conditions include W ≥ 4 in the one-dimensional case and Wd ≥ 2 in the multidimensional case.Source: §C.3 · p. 22
  • Spatial relative-position biases that include temporal displacement can identify the same spatial offset across periodic boundaries.The proposed scoring gives higher scores to previous-step cells whose offsets belong to the routing set.Source: §C.3 · p. 23
  • The paper’s experiments instead use learned absolute positional embeddings without explicit coordinate-based parameterization, leaving spatial routing to be learned.The constructions establish that this routing can be represented, while the experiments examine whether training learns consistent routing behavior.Source: §C.3 · p. 23

D.1 COVERAGE AND RESOLVABLE QUERIES

A query is resolvable when its configuration has appeared as a precedent in the stream. Resolvability is monotone, while initial-step, row-final, and novel-configuration queries have optimal predictions that do not use trajectory evidence about the rule.

D.1 COVERAGE AND RESOLVABLE QUERIES

  • A query is resolvable exactly when its own configuration has at least one precedent, and coverage is non-decreasing along the stream.Once a configuration is covered, later queries posing it remain resolvable.Source: §D.1 · p. 24
  • Initial-step cells, row-final cells, and novel configurations are the three excluded query classes; their optimal predictions depend on position and the prior alone.Initial states are drawn independently of the rule, row-final cells predict positionally determined separators, and uncovered configurations receive the prior predictive.Source: §D.1 · p. 25
  • Row-final cells are excluded because they deterministically predict separators and would otherwise inflate accuracy without measuring rule inference.Their targets carry zero mutual information about the cellular-automaton rule.Source: §D.1 · p. 25
  • For a novel configuration, the Bayes posterior predictive is uniform over states because its precedent count is zero.The uniform prediction is the mean of the Dirichlet prior and does not depend on the trajectory.Source: §D.1 · p. 25

D.2 BAYES-OPTIMAL POSTERIOR PREDICTION

For resolvable queries, the Bayes-optimal next-state distribution is determined by target counts for each configuration, and becomes empirical-frequency prediction as α approaches zero. The section also relates the minimum dimension for translation-invariant spatial scores to their Fourier spectral support and gives a grid-independent bound for spatial addressing.

D.2 BAYES-OPTIMAL POSTERIOR PREDICTION

  • For a resolvable query c, the posterior predictive is the Bayes-optimal next-state distribution under expected log-loss.Source: §D.2 · p. 25
  • Dirichlet conjugacy yields the predictive formula from per-configuration target counts.The posterior factorizes by configuration, with counts n_c,y determining the predictive distribution.Source: §D.2 · p. 25
  • As α→0, the predictor tends to empirical target frequencies; for deterministic rules, one observation makes lookup exact on resolvable queries.Source: §D.2 · p. 26
  • For stochastic rules, even the Bayes-optimal predictor remains below 100% accuracy because a configuration determines a distribution over targets.Source: §D.2 · p. 26

E SPATIAL ADDRESSING WITH GRID-INDEPENDENT WIDTH

  • Sequence-relative additive bias cannot route toroidal neighborhoods, so the positional table is indexed spatially; its width is the isolating-frequency count plus two.Source: E SPATIAL ADDRESSING WITH… · p. 26

E.1 FOURIER REPRESENTATION OF SPATIAL ATTENTION SCORES

  • For translation-invariant spatial scores, the minimum positional dimension equals the Fourier spectral support size |Ω|.Source: §E.1 · p. 27
  • An optimal realization uses a block-diagonal Q with 1×1 blocks and scaled-rotation 2×2 blocks.Source: §E.1 · p. 27

E.2 ISOLATING A SET OF OFFSETS

This section develops positional routing for spatial offsets, bounding the complexity and width needed to isolate offset sets and address preceding-step cells, independently of grid volume and trajectory horizon. It also gives a concrete 2D routing example and frames shared-head decoding as an admissible-coloring problem, including how isolation margins support softmax concentration.

E.2 ISOLATING A SET OF OFFSETS

  • The box kernel vanishes exactly on the bounding box B and uses at most 2d|N| nontrivial frequencies; when B = N, it isolates N.The box satisfies N ⊆ B and |B| ≤ |N|^d.Source: §E.2 · p. 28
  • A single offset is isolated with at most 2d frequencies and margin 1 − cos(2π/Wmax), with exactly 2d frequencies when every side length is at least 3.An axis of length 2 contributes one character instead of two.Source: §E.2 · p. 28
  • Numerical optimization isolates the von Neumann, Moore, and eight-offset routing sets on Z2^6 using four characters, versus the guaranteed 32.The four characters are {±e1, ±e2}.Source: §E.2 · p. 29
  • 40 |N| (d ln |N| + 1) frequencies suffice to isolate any nonempty proper offset set with arbitrary positive margin, independently of grid size and trajectory horizon.The scaling law is informative when |N| d log|N| ≪ |G| and holds irrespective of offset topology.Source: §E.2 · pp. 29, 31

E.3 ATTENTION CONCENTRATION FROM A SCORE GAP

  • Scaling scores by Λ places at most N̸ e^(-Λγ) softmax mass off the target subset when at least one target and at most N̸ non-target keys are present.Thus the off-target mass is at most ε once Λ is large enough to satisfy the stated concentration condition.Source: §E.3 · p. 31

E.4 SELECTING SPATIAL OFFSETS IN THE PRECEDING TIME STEP

  • The addressing interface scores preceding-step cells at offsets in N above other causally visible keys with margin γ; spatial width dS is 2d for one offset and independent of grid volume and horizon.The spatial width is determined by the spectral support of the isolating kernel.Source: §E.4 · p. 32
  • The positional width is dp=dS+2 with dS≤2d|N|+2ν, independent of grid volume and trajectory horizon; temporal scaling is needed when spatial-kernel variation can exceed the temporal margin.The wrong-time-step case forces scaling when R>γT; the causal mask is not needed for the isolation argument.Source: §E.4 · p. 33
  • Separator queries use the same positional coordinates, while separator keys require a rank-one gate to place them below the target floor.The gate extends the guarantee to causally visible keys without adding positional width.Source: §E.4 · p. 34

E.5 EXAMPLE: ADDRESSING THE 2D VON NEUMANN ROUTING SET

  • For the 2D Z_6 von Neumann routing set, dS=4 and dp=6; at stream length 504, logit scale Λ=12 puts all but 1/12 of attention mass on U.Construction II’s stated condition is Λ≥6.59, which the same Λ=12 satisfies.Source: §E.5 · pp. 34–35
  • The 2D example uses a half-step shift to distinguish the asymmetric routing set; the general width theorem is most informative when |N|d log|N| is much less than the volume.Without the shift, an even kernel in the second coordinate cannot distinguish (0, 2) from (0, 4); for small grids, explicit numerical search can give tighter bounds.Source: §E.5 · p. 35

F COLORINGS FOR SHARED-HEAD DECODING

  • Construction II’s shared Layer-1 head superposes gathered cells into color coordinates, so decoding requires an admissible coloring with no collisions within the gathered set.The section characterizes these colorings and bounds the required number of colors M as a function of G and U.Source: F COLORINGS FOR SHARED-HEAD DECODING · p. 35

F.1 ADMISSIBLE COLORINGS AND THE CAYLEY GRAPH

  • A coloring is admissible for U exactly when it is injective on every translate z+U, equivalently a proper coloring of the Cayley graph with differences U−U; a periodic coloring is admissible iff K∩(U−U)={0}.The Cayley graph’s vertices are cells, with edges between cells whose difference is a nonzero element of U−U.Source: §F.1 · p. 36

F.2 BOUNDS ON THE NUMBER OF COLORS

This section bounds the colors needed for admissible spatial routing and separator interference in finite-softmax routing, and gives Layer-1 constructions for gathering prior neighborhood states using either shared-head decoding with positional colors or one dedicated head per neighborhood offset.

F.2 BOUNDS ON THE NUMBER OF COLORS

  • The grid-independent degree bound requires at most 7, 23, and 35 colors for the elementary, von Neumann, and Moore neighborhoods, respectively.The upper bound depends only on local neighborhood geometry; an equitable admissible coloring is available with at most |(U −U) \ {0}| + 1 colors, bounded by |U|^2 −|U| + 1.Source: §F.2 · pp. 36–37

F.3 COLORINGS FOR THE EXPERIMENTAL GRIDS

  • For the one-dimensional experimental neighborhood, reduction modulo 4 is admissible and optimal; in two dimensions, a diagonal subgroup achieves MK = 12 versus 18 for coordinatewise reduction.The one-dimensional result applies on grids whose side length is divisible by 4.Source: §F.3 · p. 37

F.4 COLORING INTERFACE FOR SHARED-HEAD DECODING

  • An admissible coloring gives distinct colors to every neighborhood’s cells and supports positional addresses; an equitable coloring also limits each color class to at most ⌈|G|/M⌉ cells.The address representation uses |U|(M −1) + 1 coordinates, and a grid-independent coloring exists with M bounded using differences evaluated in Zd.Source: §F.4 · pp. 37–38

G LAYER 1: SPATIAL GATHER CONSTRUCTIONS

  • Dedicated-heads route each offset into its own residual block, while a shared head uses positional colors and an MLP to separate its aggregate into offset-specific state blocks.The shared-head encodes cell state in attention weights and routed-cell identity as a basis vector in the value projection.Source: G LAYER 1: SPATIAL GATHER CONSTRUCTIONS · pp. 38–39

G.1 TARGET REPRESENTATION AND RESIDUAL-STREAM LAYOUT

  • Layer 1 produces |U| blocks for states at (t −1, z + δ), and Layer 2 matches selected query and precedent blocks before averaging the matching precedents’ own states.The gather is specified as an approximate one-hot per block at positions with virtual time step at least 1; initial-step positions have only a weaker guarantee.Source: §G.1 · pp. 39, 41

G.2 SEPARATOR GATING AND FINITE-SOFTMAX ERROR

  • Separators must be excluded from Layer-1 attention because they can share a spatial-temporal address with an ordinary cell, splitting attention mass without a gate.Finite softmax can also leave some attention mass on non-target keys.Source: §G.2 · p. 41
  • Subtracting Γ1 ≥ Λ(R + γ) from separator scores places every separator at least Λγ below every target, allowing separators into the non-target error bound.The gate uses an existing embedding coordinate, adds no positional coordinate, and does not change the addressing construction’s width bound.Source: §G.2 · pp. 41–42
  • The weaker gate Γ1 = Λ does not guarantee the claimed e^−Λγ error when γ > 1; a three-cell torus example has γ = 3/2.At Λ = 10 and N = 12, the example’s true block error is about 4.54 × 10^−5, exceeding the claimed bound of about 3.67 × 10^−6.Source: §G.2 · p. 42
  • A routed block is an ε̄-approximate one-hot for the addressed state, with ε̄ ≤ N e^−Λγ when other keys, separators, and the auxiliary token are included.Separators and the auxiliary token contribute zero to the state block, so their attention mass can reduce its total mass but cannot add weight to an incorrect state coordinate.Source: §G.2 · pp. 42–43

G.3 CONSTRUCTION I: ONE HEAD PER OFFSET

  • With h = |U| heads, the dedicated-head gather writes each offset’s previous-step state into its own block using d_model = (|U| + 2)V + 2d + 6 and d_p = 2d + 3.The construction needs no Layer-1 MLP; each head addresses a singleton offset, and all heads share a spatial table of width 2d.Source: §G.3 · p. 43

G.4 CONSTRUCTION II: A SHARED HEAD WITH MLP DECODING

Construction II uses a shared attention head and MLP to gather routed neighbors into exact pattern blocks, then feeds these representations to Layer 2 for matching and Bayesian posterior prediction. Exact Layer-1 representations separate true matches from non-matches, while finite representation error narrows that margin and disperses matched scores, producing a trade-off with Layer-2 scale.

G.4 CONSTRUCTION II: A SHARED HEAD WITH MLP DECODING

  • One shared head plus a one-hidden-layer MLP recovers every routed state exactly at positions with τ(n) ≥1, using color-coded values, state-dependent attention weights, and reference-token normalization cancellation.Threshold comparisons recover discrete states when non-routing contamination stays below the half-integer margin; the reference coordinate removes the unknown softmax partition function.Source: §G.4 · pp. 43, 44, 47
  • With an equitable coloring, Construction II’s positional and residual widths depend only on |U|, V, and spatial dimension d, not on grid volume or trajectory horizon.The coloring has M ≤ |U|^2 − |U| + 1 colors, yielding the stated grid-independent width bounds.Source: §G.4 · p. 47

G.5 THE SPATIAL GATHER INTERFACE

  • Either Layer-1 construction yields one width-V pattern block per offset at every position with τ(n) ≥1; Construction I uses |U| heads, while Construction II uses one head and a separating MLP.The interface lets Layer 2 read the same gathered representation regardless of which construction produced it.Source: §G.5 · p. 48

G.6 CONSTRUCTION SIZES FOR THE EXPERIMENTAL SETTINGS

  • For the experimental settings, the two-hidden-layer MLP alternative uses 24 vs 38 units for 1D V=2, 32 vs 70 for 1D V=3, and 112 vs 206 for 2D von Neumann.Table 8 evaluates construction requirements on three experimental settings; Construction II’s addressing dimension is omitted because its general bound is vacuous on the cited grids.Source: §G.6 · p. 48, Table 8 · p. 49

H LAYER 2: BAYESIAN MATCHING AND END-TO-END GUARANTEES

  • With exact one-hot pattern blocks, Layer 2 scores exact configuration matches above non-matches, averages the following states over matches, and adds a Dirichlet pseudocount for posterior prediction.Aligned k-offset configurations score k on an exact match and at most k−1 otherwise; isolating exact matches makes the average their empirical conditional frequency.Source: H LAYER 2: BAYESIAN MATCHING AND… · p. 49
  • Finite Layer-1 error narrows match separation and disperses scores among true matches; increasing β suppresses non-matches but worsens that dispersion.Source: H LAYER 2: BAYESIAN MATCHING AND… · p. 49

H.1 THE CONFIGURATION-MATCHING HEAD

  • With exact Layer-1 one-hots, true matches score βk and non-matches at most β(k −1), while only valid earlier cell tokens represent transitions of f.The query represents the target cell’s parent configuration; earlier keys represent their own parent configurations, and separators and initial-step cells are excluded.Source: §H.1 · pp. 49–50

H.2 EXACT COUNTING AND DIRICHLET SMOOTHING

This section establishes exact Bayesian matching in the hard-attention limit and gives finite-parameter conditions for separating matches, controlling extraneous attention, and producing correct or smoothed predictions. It also describes parameter choices for end-to-end matching across resolvable queries and a routing–retrieval tradeoff in stochastic counting.

H.2 EXACT COUNTING AND DIRICHLET SMOOTHING

  • In the hard-attention limit, equal scoring of matching precedents yields empirical state counts, while a sink token with a prescribed score and value implements Dirichlet-smoothed posterior prediction.The theorem requires non-matches to receive score −∞; the sink supplies the prescribed value and score for smoothing.Source: §H.2 · pp. 50–51

H.3 SEPARATION OF MATCHES FROM NON-MATCHES

  • Approximate pattern blocks preserve a score gap between matching and non-matching configurations when their per-block error is sufficiently small, enabling deterministic matching.The deterministic result assumes all other visible positions, including invalid keys and any extraneous sink, fall below matching scores by the required gap; its threshold is sufficient, not tight.Source: §H.3 · pp. 52–53

H.4 MATCHED-SCORE DISPERSION AND PREDICTIVE ERROR

  • For stochastic rules, separation alone does not recover counts: approximate Layer-1 blocks disperse matched scores, so the analysis bounds the resulting predictive KL error.Matched-score deviations are bounded by η, and the stated KL bound requires no small-η assumption.Source: §H.4 · p. 53, Every matched score can be written · p. 54

H.5 THE KEY-VALIDITY GATE

  • The key-validity gate lowers every invalid key to the same score ceiling as a non-matching valid key, and assigns probability-vector values to keys.Gating initial-step cells as well as separators is necessary: otherwise spurious initial-step matches can dominate a genuine match.Source: §H.5 · pp. 54–55

H.6 END-TO-END SPATIAL INDUCTION

  • Theorem H.9 combines the Layer-1 and Layer-2 gates with sink configuration to guarantee exact predictions for deterministic rules and a bounded stochastic predictive output at resolvable queries.The stochastic guarantee uses the simplex readout; the deterministic guarantee also holds with the standard softmax readout.Source: §H.6 · p. 55
  • The section’s finite-parameter argument treats extraneous positions collectively, using the gates to suppress their attention mass while controlling dispersion among matching scores.The stochastic error is decomposed into bias within the matched-plus-sink set and contamination from extraneous positions.Source: §H.6 · p. 56
  • Gating invalid keys keeps extraneous-position mass bounded relative to matching keys and the sink.The bound counts separators and initial-step cells among visible positions, but forces their scores below the stated ceiling.Source: §H.6 · p. 56
  • For deterministic rules, the score gap yields the correct argmax at every resolvable query; Construction II has zero per-block error.Construction I instead requires a Layer-1 logit scale that makes the per-block error sufficiently small.Source: §H.6 · p. 56
  • A separator can be a query but not a key, and the existing routing predicts the first cell of a row without a separate construction.Layer 2 reads the relevant parent blocks rather than the query token’s own state, while a single gate excludes separator keys.Source: §H.6 · p. 57

H.7 CHOOSING FINITE PARAMETERS

  • The finite-parameter recipe sets the gap, per-block error, dispersion, and attention scales in sequence, with different Layer-1 requirements for the two constructions.Construction II has zero gather error and dispersion, whereas Construction I imposes a logit-scale condition to control gather error.Source: §H.7 · p. 57
  • A single circuit works uniformly over resolvable queries by choosing parameters for the worst case, nc = 1; no parameter depends on the observed match count.Because the first condition becomes easier as the match count increases, satisfying it at one match suffices for all resolvable queries.Source: §H.7 · p. 57
  • For stochastic rules, increasing β widens both the separation gap and matched-score dispersion, while excessive logit scale can undermine empirical counting.Concentrating attention on only a strict subset of matching precedents breaks the uniform weighting required for counting.Source: §H.7 · p. 57

I.1 DATA GENERATION AND RULE SPLITS

Each trajectory uses a fixed cellular-automaton rule over time, with initial states sampled independently and spatial axes treated periodically. The data vary deterministic and stochastic rule pools, serialization, and context coverage across experimental settings.

I.1 DATA GENERATION AND RULE SPLITS

  • A trajectory keeps one rule fixed across its time steps; initial cells are sampled from the state set, and spatial axes use periodic boundaries.Deterministic rules return the next state directly, while stochastic rules sample from a categorical distribution.Source: §I.1 · p. 58
  • Sequences flatten grid cells with row and time separators, while withholding the rule table and rule ID from the model input.Evaluation masks restrict scoring to prediction-region cell values, excluding separators.Source: §I.1 · p. 58
  • Selected evaluation splits rejection-sample trajectories until every neighborhood configuration appears in the observed context.The coverage filter guarantees that each scored configuration has been observed; Table 9 reports its use by split.Source: §I.1 · p. 58, Table 9 · p. 58
  • For deterministic rules, canonical rule pools are split disjointly before symmetry-orbit expansion, preventing equivalent rules from crossing splits.For binary 1D elementary cellular automata, 256 rules form 88 canonical classes, stratified by Wolfram class before splitting.Source: §I.1 · p. 58
  • The ternary 1D rule space is sampled by canonical rules stratified by output-histogram entropy, with disjoint training, validation-out, and test pools.Coverage-feasible subsets are used symmetrically for low-entropy strata that rarely yield full-coverage contexts.Source: §I.1 · p. 58
  • The binary 2D von Neumann rule space is stratified by folded Langton λ, and its canonical training, validation-out, and test pools are disjoint.Near-constant strata use coverage-feasible subsets symmetrically; the pool sizes are specified after orbit expansion and deduplication.Source: §I.1 · pp. 58–59
  • Stochastic trajectories draw independent Dirichlet rule tables, so validation and test almost surely use rules unseen during training.All settings use 50M training, 500k validation, and 500k test trajectories; Table 10 summarizes grid, horizon, and context lengths.Source: §I.1 · p. 59, Table 10 · p. 59

I.2 MODELS AND TRAINING

The experiments train two-layer transformers with learned absolute positional embeddings and evaluate deterministic and stochastic prediction under teacher-forced and autoregressive protocols. Checkpoints and metrics are selected or computed using task-specific criteria over scored cell values.

I.2 MODELS AND TRAINING

  • All models use two-layer transformers with learned absolute positional embeddings, comparing Shared-head and Dedicated-heads first-layer designs.The main text identifies the designs by their head and MLP configurations.Source: §I.2 · p. 59, Table 11 · p. 59, Table 12 · p. 59
  • Training uses AdamW with cosine learning-rate decay, linear warmup, gradient clipping, and bfloat16 mixed precision on one to four GPUs.Run time ranges from a few hours to about a day.Source: §I.2 · pp. 59–60
  • The training objective averages next-token cross-entropy over all sequence positions, while filtered evaluation masks restrict monitored loss to prediction-time positions.Deterministic checkpoints are selected by val-out sequence accuracy; stochastic checkpoints are selected by validation DKL(qtrue∥qmodel).Source: §I.2 · p. 60

I.3 EVALUATION PROTOCOL AND METRICS

  • Evaluation metrics cover only cell-value targets at scored time steps, excluding separators.Deterministic teacher-forced metrics assess cells or whole-sequence correctness; autoregressive accuracy scores greedy rollouts against the ground-truth trajectory.Source: §I.3 · p. 60
  • Stochastic evaluation reports sampled-rollout accuracy and teacher-forced accuracy or KL divergences against k-gram references and the true rule distribution.The autoregressive k-gram baseline uses add-one-smoothed causal counts, and its accuracy is from an independently sampled rollout.Source: §I.3 · pp. 60–61
  • Evaluations use random seed 42 and one autoregressive rollout per trajectory, with reported values micro-averaged over 500k test trajectories.Source: §I.3 · p. 61

I.4 FULL PREDICTIVE RESULTS

The supplied full-results and analysis passages report above-0.998 deterministic teacher-forced sequence accuracy and define diagnostics using attention alignment, ablations, probes, and visualizations.

I.4 FULL PREDICTIVE RESULTS

  • All deterministic models exceed 0.998 TF sequence accuracy; the DKL(qkgram∥qmodel)–DKL(qtrue∥qmodel) gap reflects k-gram estimation error.The first divergence compares against an estimate built from the same context the model sees; the second compares against the generating rule.Source: Table 13 · p. 61, §I.4 · p. 61, Table 14 · p. 61

I.5 ATTENTION-ALIGNMENT ANALYSIS

  • L1 alignment scores measure attention on routing cells carrying the query configuration, while L2 scores measure attention on matching precedents.Scores are micro-averaged across queries and trajectories under teacher forcing on 20,000 test trajectories.Source: §I.5 · pp. 61–62

I.6 ATTENTION ABLATION

  • Ablations zero L1 routing-cell or L2 matching-precedent attention, with same-count random-position controls, and evaluate teacher-forced cell accuracy.The random controls are averaged over three seeds; queries without a disjoint random set remain unmodified.Source: §I.6 · p. 62

I.7 LAYERWISE PROBE PROTOCOL

  • Linear probes test neighborhood-configuration classification and k-gram predictive-distribution recovery at five post-residual stages.Configuration performance uses balanced accuracy; predictive-distribution performance is scored relative to a uniform predictor.Source: §I.7 · p. 62

I.8 REPRESENTATION VISUALIZATIONS WITH T-SNE

  • The t-SNE panels color five-stage representations by neighborhood configuration above and output value below, but their two-dimensional geometry is qualitative.The appendix relies on linear probes for quantitative evidence of decodability because visible clusters may not faithfully reflect the original representations.Source: §I.8 · p. 63

I.9 QUALITATIVE ROLLOUT SETUP FOR FIGURE 1

  • Figure 1 uses separate visualization checkpoints on unseen rules; stochastic autoregressive samples need not reproduce individual cells, unlike teacher-forced probability predictions evaluated against ground-truth histories.The checkpoints use longer trajectories and wider grids than the main-text models and are not used for predictive results, attention alignment, or linear probes; the deterministic panel uses greedy decoding and the stochastic panel uses temperature-1 sampling.Source: §I.9 · p. 63, Table 15 · p. 64
Loading 2610.09124v1…