# Indexing: the Beginning and the End

arXiv: https://arxiv.org/abs/2607.22361 · HTML: https://mlsanity.com/paper/2607.22361/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 30 references that are in the map.
- First posted on arXiv 24 Jul 2026.

## Builds on (most cited first, 19 of 19)

- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Mitigating Large Language Model Hallucinations via Autonomous Knowledge Graph-based Retrofitting](https://mlsanity.com/paper/2311.13314/) (2023)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [The Expressive Capacity of State Space Models: A Formal Language Perspective](https://mlsanity.com/paper/2405.17394/) (2024)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [One-layer transformers fail to solve the induction heads task](https://mlsanity.com/paper/2408.14332/) (2024)
- [Olmo Hybrid: From Theory to Practice and Back](https://mlsanity.com/paper/2604.03444/) (2026)
- [Strassen Attention, Split VC Dimension and Compositionality in Transformers](https://mlsanity.com/paper/2501.19215/) (2025)
- [The Counting Power of Transformers](https://mlsanity.com/paper/2505.11199/) (2025)
- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [The Expressive Limits of Diagonal SSMs for State-Tracking](https://mlsanity.com/paper/2603.01959/) (2026)
- [Ehrenfeucht-Haussler Rank and Chain of Thought](https://mlsanity.com/paper/2501.12997/) (2025)
- [Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)](https://mlsanity.com/paper/2503.22076/) (2025)

## Built on by (most cited first, 2 of 2)

- [VC Dimension and Expressivity of Real-Valued Transformers](https://mlsanity.com/paper/2609.31999/) (2026)
- [Exact-Solution Volume and Length Generalization in Transformers](https://mlsanity.com/paper/2610.07676/) (2026)

## Abstract (arXiv)

We study information bottlenecks in modern deep-learning architectures -- RNNs, softmax transformers, linear-attention transformers and state-space models -- through the lens of the indexing primitive. In this primitive, the input consists of n bits and one integer i from 1 to n called the index, and the output equals the value of the i-th bit. We introduce causal complexity for masked architectures. We show that architectures with low causal complexity cannot solve the indexing primitive in any constant number of layers when the index appears at the end of the input. In particular, this limitation applies to low-parameter RNNs, SSMs and masked linear-attention transformers. In contrast, small softmax transformers can solve it in one layer, while non-masked linear-attention transformers can solve it in 2, which separates them from their masked counterparts. In turn, when the index appears at the beginning, we show that small RNNs are capable of solving this task in 1 layer, while all the other architectures require 2. All our impossibility results are unconditional and apply even to models that employ infinite-precision real arithmetic. Moreover, experiments for up to n=64 qualitatively align with our theory: configurations with low-parameter theoretical solutions learn the indexing task easily, while configurations that do not admit such theoretical solutions struggle to learn as the sequence length grows.