Indexing: the Beginning and the End

• URL: http://arxiv.org/abs/2607.22361v1
• Date: Fri, 24 Jul 2026 14:42:44 GMT
• Title: Indexing: the Beginning and the End
• Abstract summary: We study information bottlenecks in modern deep-learning architectures through the lens of the indexing primitive.<n>In this primitive, the input consists of $n$ bits and one integer $i$ from $1$ to $n$ called the index.<n>We show that architectures with low causal complexity cannot solve the indexing primitive in any constant number of layers when the index appears.
• Score: 45.94629852512322
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
  Implicit Chain-of-Thought (ICoT) trains models to internalize intermediate steps within their hidden states.<n>Log-ICoT removes thinking tokens one at a time, reducing the number of stages from linear in $k$ to logarithmic.<n>Experiments on multi-layer transformers confirm the theory and visualize how reasoning is progressively absorbed into deeper layers.
  arXiv  Detail & Related papers  (2026-05-27T15:17:06Z)
• InfoFlow: A Framework for Multi-Layer Transformer Analysis [28.731784494689276]
  Multi-layer Transformers possess fundamentally different approximation capabilities from single-layer ones.<n>We propose InfoFlow, a framework for multi-layer Transformers.
  arXiv  Detail & Related papers  (2026-05-18T06:38:39Z)
• When Attention Beats Fourier: Multi-Scale Transformers for PDE Solving on Irregular Domains [0.0]
  msat achieves state-the-art generalization on complex geometry problems.<n>textbfMulti-Scale Attention Transformer (msat) encodes solution histories as token sequences and trains end-to-end.
  arXiv  Detail & Related papers  (2026-05-08T15:23:13Z)
• Provably Learning Attention with Queries [15.606567893781367]
  We study the problem of learning Transformer-based sequence models with black-box access to their outputs.<n>In this setting, a learner may adaptively query the oracle with any sequence of vectors and observe the corresponding real-valued output.
  arXiv  Detail & Related papers  (2026-01-23T16:28:22Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  We study how a two-attention-layer transformer is trained to perform ICL on $n$-gram Markov chain data. We prove that the gradient flow with respect to a cross-entropy ICL loss converges to a limiting model.
  arXiv  Detail & Related papers  (2024-09-09T18:10:26Z)
• Separations in the Representational Capabilities of Transformers and Recurrent Architectures [27.783705012503237]
  We analyze the differences in the representational capabilities of Transformers and RNNs across several tasks of practical relevance. We show that a one-layer Transformer of logarithmic width can perform index lookup, whereas an RNN requires a hidden state of linear size. We also show that a log-size two-layer Transformer can implement the nearest neighbor algorithm in its forward pass.
  arXiv  Detail & Related papers  (2024-06-13T17:31:30Z)
• Transformers as Support Vector Machines [54.642793677472724]
  We establish a formal equivalence between the optimization geometry of self-attention and a hard-margin SVM problem. We characterize the implicit bias of 1-layer transformers optimized with gradient descent. We believe these findings inspire the interpretation of transformers as a hierarchy of SVMs that separates and selects optimal tokens.
  arXiv  Detail & Related papers  (2023-08-31T17:57:50Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  We find that a low-depth Transformer can represent the computations of any finite-state automaton. We show that a Transformer with $O(log T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We further investigate the brittleness of these solutions and propose potential mitigations.
  arXiv  Detail & Related papers  (2022-10-19T17:45:48Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  We show that sparse Transformers with only $O(n)$ connections per attention layer can approximate the same function class as the dense model with $n2$ connections. We also present experiments comparing different patterns/levels of sparsity on standard NLP tasks.
  arXiv  Detail & Related papers  (2020-06-08T18:30:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.