- Rating
- 3
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studied how Transformers perform in-context learning on multidimensional cellular automata. The authors observed that flattening a spatial grid into a one-dimensional token sequence breaks the contiguity assumption behind standard induction heads: spatial neighbors end up scattered across distant positions. To address this, they proposed spatial induction heads, a two-layer gather-and-match circuit. The first layer gathers the relevant spatial neighborhood, and the second layer matches the resulting configuration against earlier occurrences to predict the next state. They provided two explicit gather constructions and show that the positional width needed for spatial routing depends only on the local neighborhood and spatial dimension, not on grid size or trajectory length. They further showed that the matching layer implements Bayesian counting, approximating the Bayes-optimal predictor for stochastic rules and predicting exactly for deterministic rules. Experiments on 1D and 2D cellular automata showed generalization to unseen rules, with attention patterns, ablations, and linear probes supporting the proposed circuit.
Critical strengths
- The paper identified an important gap that existing induction head method assumes a contiguous context, which fails for flattened spatial data.
- The paper presented a clean and promising theoretical framework with the proposed two-layer gather-and-match circuit.
Critical weaknesses
- The presentation is only friendly to a narrow range of readers who happen to work on the same task. The significance of the work is not conceivable for general machine learning researchers.
- The paper does not directly analyze whether the learned positional embeddings reflect the theoretical constructions. For stochastic rules, the reported KL is against the k-gram estimate rather than the Bayes posterior.
Questions for authors
- Do the learned positional embeddings show any structure resembling the constructions used in the proofs, such as Fourier-like patterns or colorings?
- Can the authors report the divergence between the model's predictions and the Bayes posterior directly, rather than only against the k-gram estimate?
- How much does performance drop if the coverage filter is removed, so that some scored queries involve unseen configurations?
- Are there path patching or causal tracing experiments that directly show information flowing from the first-layer routing cells to the second-layer matching head?
- How does the model compare with a Transformer that uses explicit 2D positional encodings or a convolutional inductive bias, under similar parameter counts?
9 comments
W2 & Q1 (continue)
Fourier structure. The routing also relies on a few spatial frequencies, as in the construction. Removing the 4 strongest frequency groups of the learned table drops accuracy to at most 0.62, far more than removing 4 random groups (Table B3).
Table B3. TF cell accuracy after Fourier ablation of the learned positional table (main-text models).
| Setting | Architecture | Chance | Keep top 4 | Remove top 4 | Remove 4 random |
|---|---|---|---|---|---|
| 1D | Shared-head | 0.5000 | 0.9901 | 0.5894 | 0.6460 |
| 1D | Dedicated-heads | 0.5000 | 0.9818 | 0.6165 | 0.9401 |
| 1D | Shared-head | 0.3333 | 0.5939 | 0.4086 | 0.7688 |
| 1D | Dedicated-heads | 0.3333 | 0.7902 | 0.4689 | 0.9195 |
| 2D VN | Shared-head | 0.5000 | 0.5863 | 0.5730 | 0.7611 |
| 2D VN | Dedicated-heads | 0.5000 | 0.9966 | 0.5735 | 0.8122 |
W2 & Q2: KL to the Bayes posterior
We clarify that for the stochastic reference, the add-one-smoothed -gram predictor is exactly the Bayes posterior for , the experimental prior (Theorem 3; Appendix I.3). The reported KL is therefore already against that posterior.
Q3: Removing the coverage filter
Unseen configurations () are a limit of induction itself. For unseen configurations, without prior occurrences, the model has no evidence about their rule-specific behavior. Under our prior, the Bayes-optimal predictor therefore defaults to the prior mean (Lemma D.2), which our construction implements exactly (Proposition 8).
Our experiments evaluate only resolvable queries (), since predictions at measure the model's ability to recover the prior rather than learn the rule in context.
Removing the filter barely changes performance: deterministic accuracy drops by at most 0.0003, and the stochastic KL is unchanged (Table B4). On the unseen configurations themselves, models trained on stochastic rules predict a nearly uniform distribution (), matching the Bayes-optimal answer (Table B5).
Table B4. Filtered vs. unfiltered test sets. Deterministic: TF cell accuracy. Stochastic: TF . Filtered values are from paper Tables 1 and 14.
| Setting | Rules | Arch. | Filtered | Unfiltered |
|---|---|---|---|---|
| 1D | Det. | Shared-head | 1.0000 | 0.9999 |
| 1D | Det. | Dedicated-heads | 1.0000 | 0.9999 |
| 1D | Det. | Shared-head | 1.0000 | 0.9998 |
| 1D | Det. | Dedicated-heads | 1.0000 | 0.9998 |
| 2D VN | Det. | Shared-head | 1.0000 | 0.9997 |
| 2D VN | Det. | Dedicated-heads | 1.0000 | 0.9997 |
| 1D | Stoch. | Shared-head | 0.0020 | 0.0020 |
| 1D | Stoch. | Dedicated-heads | 0.0046 | 0.0046 |
| 1D | Stoch. | Shared-head | 0.0026 | 0.0026 |
| 1D | Stoch. | Dedicated-heads | 0.0004 | 0.0004 |
| 2D VN | Stoch. | Shared-head | 0.0014 | 0.0014 |
| 2D VN | Stoch. | Dedicated-heads | 0.0033 | 0.0033 |
Table B5. Stochastic rules: unseen configurations (), unfiltered test sets. means the prediction is uniform.
| Setting | Arch. | KL$(U|q)$ | |
|---|---|---|---|
| 1D | Shared-head | 0.0116 | 0.9841 |
| 1D | Dedicated-heads | 0.0041 | 0.9946 |
| 1D | Shared-head | 0.0017 | 0.9984 |
| 1D | Dedicated-heads | 0.0002 | 0.9998 |
| 2D VN | Shared-head | 0.0010 | 0.9986 |
| 2D VN | Dedicated-heads | 0.0007 | 0.9990 |
Thank you for the detailed rebuttal and the additional experiments. I find the new analyses of positional embeddings particularly informative. The clarifications regarding the Bayesian posterior and the coverage filter satisfactorily address my corresponding questions.
My main remaining concern is the accessibility and broader significance of the work. While I appreciate the connections to previous studies of induction heads and spatial Transformers, I would still encourage the authors to explain more clearly what general insights this framework provides beyond the specific cellular automata setting, as well as its limitations.
Overall, the rebuttal has strengthened my confidence in the technical contributions. I am inclined to maintain my positive assessment.
We thank the reviewer for recognizing the gap we address in existing induction-head theory and the clarity and promise of our gather-and-match framework. We appreciate their thoughtful feedback and address their concerns below.
W1: Accessibility and broader significance
Our work extends an established line of theory on in-context learning of Markov chains [1, 2, 4, 6, 11], published at ICLR and NeurIPS, including a NeurIPS 2025 spotlight [2]. These works advance our understanding of induction heads, one of the best-understood mechanisms of in-context learning in language models. Transformers also routinely process spatial data, such as images and video, as flattened sequences, yet how they recover spatial structure remains poorly understood. Our goal is to extend this mechanistic understanding to multidimensional data through the proposed gather-and-match circuit. The importance of learning spatial rules from limited examples is further reflected in benchmarks such as ARC-AGI [8]. We agree that the paper should make these broader connections clearer and be more accessible to general machine learning researchers, and will improve the exposition accordingly.
W2 & Q1: Structure of the learned positional embeddings
We ran additional experiments at the positional widths given by Theorem 7 (5 in 1D and 7 in 2D), using both random initialization and initialization with the construction's Fourier positional features. At these widths, models initialized with the Fourier construction achieve near-perfect sequence accuracy, matching the free-table models that use 128 and 1024 dimensions (Table B1). This confirms that the theoretical widths suffice in the trained architecture. In contrast, random initialization at the same widths does not reach comparable accuracy under the training configurations tested, indicating that gradient descent does not reliably discover the compact solution. The free-table models have substantially higher effective ranks (102.6 in 1D and 195.1 in 2D), suggesting that gradient descent uses a higher-dimensional representation when given the flexibility, whereas the Fourier construction reaches the same accuracy with only 5 and 7 dimensions (effective rank 4.9 and 6.1).
Table B1. Positional width, effective rank, and accuracy.
Although the free tables do not recover the construction's parameters, they share its structure. We group Layer-1 attention logits according to the query–key grid displacement (temporal difference and spatial offset on the torus) and measure the explained variance R2, compared with grouping by sequence displacement and random labels. Across both 1D and 2D settings, with either freely learned positional tables or the theory-prescribed positional dimension dp, spatial displacement explains more variance than sequence displacement, suggesting that learned scores reflect spatial structure more strongly than sequential structure (Table B2).
Table B2. Explained variance of Layer-1 positional scores. Grid (keys at t−1) considers only previous-step keys. Sequence groups pairs by token-stream distance. Random uses random groups as a control.