🤖 machine learning

Indexing: the Beginning and the End

This paper introduces the concept of causal complexity to demonstrate that masked deep-learning architectures like RNNs and linear-attention transformers are fundamentally limited in solving the indexing primitive when the index appears at the end of the input, whereas softmax and non-masked linear-attention transformers can solve it efficiently, a theoretical separation that is corroborated by empirical experiments.

Original authors: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

Published 2026-07-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a super-smart robot that can read a story and answer questions about it. This is the world of artificial intelligence, specifically a field called "deep learning," where computers learn patterns by looking at massive amounts of data. For a long time, the most popular robots for this job were called "Transformers." They are like brilliant librarians who can instantly flip through a whole book to find a specific fact. But there's a catch: as the book gets longer, the librarian gets slower and slower, and building them requires a lot of energy and money.

To fix this, scientists invented new types of robots, like "RNNs" (which read stories one word at a time, like a human) and "SSMs" (which try to read the whole story at once but in a very streamlined way). The big question everyone is asking is: "Are these new, faster robots just as smart as the old, slow ones, or do they have hidden blind spots?" To find the answer, researchers don't just guess; they give the robots tiny, tricky puzzles to solve. These puzzles are like the "math homework" of the AI world. If a robot can't solve a simple homework problem, it proves that the robot's brain has a fundamental limit, no matter how much you train it.

This paper, titled "Indexing: the Beginning and the End," takes a very specific, simple puzzle called "Indexing" and uses it to test the brains of these different robot architectures. The puzzle is deceptively easy: imagine you have a list of $n$ bits (a string of 0s and 1s) and a number $i$ that tells you which bit to pick. The goal is simply to output the value of that specific bit. It's like being handed a row of 64 light switches and a number, say "17," and being asked, "Is switch 17 on or off?"

The researchers, Alexander Kozachinskiy, Vicente Opazo, and Felipe Urrutia, discovered that the order in which the robot sees the information changes everything. They found that some robots are incredibly fast at this task, while others hit a wall that they simply cannot climb, no matter how many layers of "thinking" they have.

Here is the twist: The paper proves that for certain types of robots (specifically those that process information in a "causal" or "masked" way, meaning they can only look at what came before them and not what comes after), solving this puzzle is mathematically impossible if the list of bits is long and the index number appears at the very end. It's as if you handed a robot a long line of people, asked it to remember everyone's face, and then at the very end whispered, "Tell me the name of person number 42." The paper shows that robots like RNNs, Mamba, and masked linear-attention transformers have a "memory bottleneck." They can't compress all that information into a small enough package to remember the specific bit when the index finally arrives. The authors proved this using rigorous math that holds true even if the robots have infinite precision (meaning they don't get confused by rounding errors).

However, the story changes if you flip the script. If the index number appears at the beginning of the list (telling the robot "Remember person 42" before you even show them the line of people), the RNNs become the superheroes. They can solve this in a single step, while the other robots (including the famous Transformers) need at least two steps to figure it out.

The authors didn't just do the math; they also ran experiments with real models. They trained these robots on lists of up to 64 bits. The results were a perfect match for their theory. The robots that the math said should fail (the causal ones trying to find the bit at the end of a long list) consistently gave up as the lists got longer. Meanwhile, the robots that the math said should succeed learned the task easily.

So, what's the takeaway? It's not that one robot is "better" than the other in every way. Instead, the paper reveals that different architectures have different "superpowers" and different "kryptonite." The way a robot processes information—whether it reads left-to-right, looks at everything at once, or tries to summarize the past—determines exactly which puzzles it can solve and which ones will stump it forever. This helps scientists understand the fundamental limits of AI, ensuring that when we build the next generation of smart machines, we know exactly what they can and cannot do.

Technical Summary: Indexing: the Beginning and the End

Problem Statement

This paper investigates the expressivity and information bottlenecks of modern deep learning architectures—specifically Recurrent Neural Networks (RNNs), Softmax Transformers, Linear-Attention Transformers, and State-Space Models (SSMs)—through the lens of the indexing primitive.

The indexing task is defined as follows: given a sequence of $n$ bits $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ and an index $i \in \{1, \dots, n\}$ , the model must output the value of the $i$ -th bit, $\sigma_i$ . The authors analyze two specific variations of this task to probe different architectural limitations:

Right-Hand Indexing (RHI): The index $i$ appears at the end of the input sequence (after the bits). The model must retrieve $\sigma_i$ based on information processed from the preceding $n$ bits.
Left-Hand Indexing (LHI): The index $i$ appears at the beginning of the input sequence (before the bits). The model must carry the index information through the sequence to retrieve $\sigma_i$ at the end.

The study focuses on "small" architectures, defined as having $o(1)$ parameters (constant number of parameters relative to sequence length $n$ ) and potentially infinite-precision real arithmetic.

Methodology

The authors employ a theoretical framework based on causal complexity and VC dimension to derive unconditional lower bounds.

Causal Complexity

For causal (masked) architectures, where the output at position $k$ depends only on inputs $1$ through $k$ , the authors introduce the notion of causal complexity. This measures the minimal dimension $s$ to which the history of inputs ( $x_1, \dots, x_{k-1}$ ) can be compressed (via a "fingerprint" function) such that the $k$ -th output can be computed from this compressed representation and the current input $x_k$ with low arithmetic complexity.

Key Insight: If an architecture has low causal complexity (specifically $o(1)$ ), it cannot compress the necessary history to solve tasks requiring the retrieval of specific past information when that information is not immediately accessible.

Theoretical Tools

VC Dimension: The authors adapt the technique from Kozachinskiy et al. (2025) to show that if a model solves the indexing task, the associated concept class must have a VC dimension of at least $n$ .
Arithmetic Complexity: They utilize the arithmetic complexity of the functions computed by the layers (including exponentials, arithmetic operations, and conditionals) to bound the VC dimension.
Unconditional Bounds: Unlike previous works that relied on bounded-precision assumptions, these results hold even for models using infinite-precision real numbers.

Experimental Validation

The theoretical findings are validated through experiments on binary indexing tasks for sequence lengths $n \in \{8, 16, 32, 64\}$ . The authors compare:

Full and causal variants of Softmax and Linear-Attention Transformers.
RNNs (specifically GRUs).
SSMs (specifically Mamba).
All models are trained from scratch with fixed hyperparameters to observe learning dynamics as $n$ increases.

Key Contributions and Results

1. Right-Hand Indexing (Index at the End)

In this scenario, the model processes all $n$ bits before seeing the index. To solve the task, the model must compress the entire $n$ -bit string into a state small enough to be processed by the index token.

Impossibility for Low-Causal-Complexity Architectures: The authors prove that no constant number ( $O(1)$ $O (1)$ ) of layers with $o(1)$ $o (1)$ causal complexity can solve RHI.
- Affected Architectures: Small RNNs, SSMs (e.g., Mamba), and masked Linear-Attention Transformers all have $o(1)$ causal complexity. Consequently, they cannot solve RHI in a constant number of layers, even with infinite precision.
- Experimental Confirmation: Models in this category (1-layer and multi-layer causal linear-attention, GRUs, Mamba) consistently fail to learn RHI as $n$ grows, reaching 0% success at $n=64$ .
Possibility for High-Causal-Complexity Architectures:
- Softmax Transformers: A single layer with $O(1)$ parameters can solve RHI. This is attributed to their high causal complexity (via the softmax mechanism allowing global attention).
- Full Linear-Attention: Two layers with $O(1)$ parameters can solve RHI.
- Experimental Confirmation: These configurations learn the task easily, with high success rates even at $n=64$ .

2. Left-Hand Indexing (Index at the Beginning)

In this scenario, the index is processed first and must be carried through the sequence to the relevant bit position.

RNN Dominance: Small RNNs can solve LHI in a single layer with $O(1)$ parameters. They naturally maintain a hidden state that can carry the index $i$ and update a specific coordinate when the $i$ -th bit is encountered.
Limitations of Other Architectures:
- SSMs and Linear-Attention: Neither 1-layer SSMs nor 1-layer Linear-Attention (masked or full) can solve LHI with $o(1)$ parameters. The linearity of SSM updates prevents them from selectively "writing" the bit value to a specific position determined by the index without mixing information in a way that prevents retrieval.
- Softmax Transformers: 1-layer Softmax transformers also fail LHI with $o(1)$ parameters.
Resolution with Depth: All architectures (including SSMs, Linear-Attention, and Softmax Transformers) can solve LHI if given 2 layers with $O(1)$ parameters. The first layer can propagate the index, and the second can retrieve the bit.
Experimental Confirmation: 1-layer GRUs succeed at all lengths. 1-layer Mamba and Linear-Attention models fail for $n \ge 16$ . 2-layer versions of all architectures succeed.

Summary Table of Minimum Layers Required

Architecture	Left-Hand Indexing (LHI)	Right-Hand Indexing (RHI)
Full Softmax	2	1
Causal Softmax	2	1
Full Linear-Attention	2	2
Causal Linear-Attention	2	$\omega(1)$ (Impossible)
SSM (e.g., Mamba)	2	$\omega(1)$ (Impossible)
RNN	1	$\omega(1)$ (Impossible)

(Note: $\omega(1)$ indicates that the number of layers required is not bounded by a constant; i.e., it grows with $n$ .)

Significance and Claims

The paper claims to provide the first multi-layer, infinite-precision lower bounds for a class of architectures with low causal complexity, including SSMs, RNNs, and masked linear-attention transformers.

Architectural Separation: The indexing primitive reveals a fundamental separation between architectures. While Softmax Transformers and full Linear-Attention models can solve RHI efficiently, masked variants and SSMs cannot, highlighting the specific role of global attention mechanisms in overcoming information bottlenecks.
Role of Linearity: The results suggest that the linear update rules of SSMs, often touted for their efficiency, become a liability in LHI tasks where non-linear selective writing is required in a single step.
Theory-Practice Alignment: The experiments demonstrate that theoretical impossibility results (asymptotic lower bounds) manifest qualitatively in finite training settings. Configurations with theoretical solutions learn the task robustly, while those without struggle as sequence length increases, even if they succeed at small $n$ .
Modesty: The authors explicitly state that training failure is not proof of impossibility, nor does success at small $n$ contradict asymptotic lower bounds. However, the strong correlation between their theoretical bounds and empirical performance suggests that causal complexity is a robust predictor of learnability for retrieval tasks.

The work extends the analysis of transformer expressivity (previously focused on function composition and induction heads) to modern, efficient alternatives, providing rigorous mathematical justification for their limitations in specific information retrieval scenarios.