Pith. sign in

REVIEW 1 major objections 4 minor 29 references

The paper proves that constant-depth small RNNs, state-space models, and masked linear-attention transformers cannot solve the indexing primitive when the index arrives last, while a single small softmax transformer layer can.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Causal-complexity bounds show RNNs, SSMs, and masked linear attention need ω(1) layers for right-hand indexing, while a one-layer softmax transformer solves it; when the index is first, a one-layer RNN suffices.

T0 review reviewed 2026-08-01 challenge →

load-bearing objection Solid and novel lower-bound machinery for indexing, with one external theorem that needs checking before the impossibility results for exp-based architectures are fully earned. the 1 major comments →

arxiv 2607.22361 v1 pith:BSUWFOJH submitted 2026-07-24 cs.LG cs.AI

Indexing: the Beginning and the End

Alexander Kozachinskiy , Vicente Opazo , Felipe Urrutia This is my paper
classification cs.LG cs.AI
keywords indexingcausal complexitytransformerslinear attentionstate-space modelsRNNsVC dimensionexpressivity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that a minimal retrieval task—reading the bit at a given index—separates sequence architectures into sharp capability tiers. It introduces causal complexity, which measures how much of the preceding input a masked layer can compress, and proves that any constant number of layers with n^{o(1)} causal complexity cannot solve right-hand indexing, where the index arrives last. This impossibility holds for infinite-precision real arithmetic and rules out constant-depth small RNNs, SSMs, and masked linear-attention transformers. In contrast, one softmax layer of constant size solves the task, and so do two full linear-attention layers. For left-hand indexing, where the index comes first, one RNN layer already suffices, while all other small architectures require two.

Core claim

The central discovery is that indexing is a lens that reveals an information bottleneck shared by masked recurrent and linear-attention architectures: when the query (the index) appears only at the end, the network must have effectively stored the entire bit string in its state, and the achievable compression is bounded by causal complexity. The authors prove that O(1) layers of causal complexity n^{o(1)} cannot perform right-hand indexing, using a VC-dimension argument: were such layers to succeed, the computation at the final position would define a concept class with n^{o(1)} parameters and arithmetic complexity whose VC dimension must be at least n, contradicting a quadratic VC bound for

What carries the argument

The central object is causal complexity: for a masked layer, the minimal s such that, at each position k, the k-th output is computed with arithmetic complexity t from a p-dimensional fingerprint of the first k−1 inputs together with the k-th input, with p+t ≤ s. The lower-bound proof combines this with a general VC-dimension bound for arithmetic programs—programs over the reals with exp, +, −, ×, /, and comparisons—showing that a low-causal-complexity solution of right-hand indexing would yield a concept class with small VC dimension yet the power to shatter n points. The positive constructions are carried by positional encodings that let attention localize the indexed position: trigonometr

Load-bearing premise

The impossibility theorems depend on a known VC-dimension bound for real arithmetic programs with exponentials and comparisons; if that bound does not hold for this operation set, the lower bounds lose their foundation.

What would settle it

Find a concept class defined using exp, +, −, ×, /, >, = with p parameters and arithmetic complexity t whose VC dimension grows faster than order t^2 p^2; alternatively, exhibit an explicit constant-depth, n^{o(1)}-parameter SSM or masked linear-attention network that provably solves right-hand indexing for all n.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • No constant number of small masked linear-attention, state-space, or RNN layers can perform right-hand indexing, even with infinite-precision arithmetic; only architectures with high causal complexity per layer escape this bound.
  • A single constant-size softmax transformer layer solves right-hand indexing, so softmax attention provides strictly more per-layer routing power than the other causal families studied.
  • Two full linear-attention layers with constant parameters solve right-hand indexing, which separates full linear attention from its masked variant.
  • For left-hand indexing, one constant-size RNN layer suffices, while every other small architecture considered needs at least two layers.
  • The separations are unconditional—they do not depend on training, precision, or finite-size effects—and the experiments show the predicted constructive/stress-test gap already at n=64.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The causal-complexity lower bound is stated for generic masked layers, so it likely transfers to other architectures that compress history into a fixed-size state—for example, chunked attention or recurrent linear-attention variants—suggesting a design principle: if the query arrives last, avoid aggressive state compression.
  • The asymmetry between left- and right-hand indexing implies that input ordering is a first-class design axis: for retrieval-heavy tasks, presenting the query first could make one-layer RNN/SSM solutions possible where none exist with a trailing query.
  • The strength of the impossibility results rests on the VC-dimension bound for programs with exponentials and comparisons; verifying or disproving that bound for this operation set is the most direct way to test the paper's foundation.
  • The Mamba/layernorm caveat hints at a boundary of the technique: operations outside the allowed program class (such as square roots) require separate Pfaffian-style VC bounds, so extending the results to normalized architectures is an open step rather than a corollary.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper studies two forms of the indexing primitive (left-hand and right-hand) and asks how many layers of small sequence architectures are needed to solve them. It introduces a notion of causal complexity for masked/causal layers and proves a generic impossibility result: no O(1) causal layers of causal complexity n^{o(1)} can solve right-hand indexing. From this it derives lower bounds for low-parameter RNNs, SSMs, and causal linear-attention transformers, since these architectures have low causal complexity. On the positive side, one O(1)-size softmax transformer layer and two O(1)-size full linear-attention layers solve right-hand indexing, separating full from masked linear attention. For left-hand indexing, one RNN layer suffices, while all other studied architectures need two layers. The proofs combine a VC-dimension argument (Theorem 3) with explicit constructions. Experiments for n up to 64 show that configurations with theoretical low-parameter solutions tend to learn, while stress-test configurations increasingly fail as n grows.

Significance. If the technical gaps below are fixed, this would be a valuable contribution: it provides some of the first multi-layer, infinite-precision lower bounds for SSMs and linear-attention transformers, introduces a reusable notion of causal complexity, and cleanly separates causal from full linear attention on a basic primitive. The paper is also commendable for shipping reproducible code and for being candid about the distinction between asymptotic lower bounds and finite-size training failures. The central VC-dimension technique is appealing and, modulo the Theorem 3 issue, the arguments are coherent and the positive constructions are plausible.

major comments (1)
  1. [§2.1 (Definition 1 and Theorem 3)] Theorem 3 is the sole engine behind the impossibility results: Theorem 12.a and the SSM/linear-attention parts of Theorem 14.b all construct concept classes with arithmetic complexity measured under Definition 1, which explicitly includes the exponential function, and then apply the cited Anthony–Bartlett bound VCdim=O(AC^2 p^2). In its standard formulation, Theorem 8.14 of Anthony and Bartlett is a semialgebraic bound for +,−,×,/ and comparisons; it does not by itself cover exp. The paper itself recognizes a related gap in the §2.3 LayerNorm discussion: sqrt is excluded from Definition 1, and the authors say Pfaffian bounds (Karpinski–Macintyre) would be needed, but no analogous qualification is made for exp. This matters concretely because the lower-bound concept classes for Mamba/SiLU φ and ELU-based causal linear attention evaluate exp inside the class. If the cited theorem does not
minor comments (4)
  1. [§3, Theorem 12.b proof] The sentence 'Repeating the same attention mechanism in the second layer gives this value to every token' is too terse. After the first layer, the dominant positional signal still points to the last token; the reader needs to see how the large marker at position i is used as a key in the second layer so that attention concentrates on i rather than on the last token. This is plausibly fixable, but the construction should be spelled out.
  2. [§4, Eq. (8)] The expression (α(i)+β(σ))/(γ(i)+ρ(σ)) should be written with an explicit numerator and denominator, since in the softmax case the numerator is vector-valued and the denominator is scalar. The current inline fraction is ambiguous.
  3. [§5.2, Table 2] The column headed 'Thm.' is empty in the table; either remove it or include the theorem numbers that certify each row's ✓/✗ classification.
  4. [§2.3, Mamba paragraph] The LayerNorm discussion is helpful, but it raises an immediate question: the same kind of qualification should be stated explicitly for exp in Definition 1. If the authors intend Theorem 3 to cover exp, that should be said and justified; if not, the affected lower bounds should be weakened.

Circularity Check

0 steps flagged

No significant circularity: the lower bounds are standard VC-dimension arguments over explicitly constructed concept classes and the one self-citation is methodological, not load-bearing.

full rationale

The derivation chain for Theorem 12.a is self-contained modulo the external Anthony-Bartlett bound (Theorem 3). Assuming a hypothetical O(1)-layer solution, the proof constructs a concept class whose parameters are the layer fingerprints (dimension n^{o(1)} by causal complexity) and whose labels reproduce the indexing task; shattering n index inputs forces VCdim at least n, while Theorem 3 gives n^{o(1)}, a contradiction. No stage of this argument defines causal complexity or the concept class in terms of the indexing outcome being proved, and no fitted parameter is later relabeled as a prediction. The upper bounds are explicit constructions, not fitted outputs. The same holds for Theorem 14.b's concept-class arguments. The only self-citation is Kozachinskiy et al. (2025), invoked as 'adapting the VC dimension technique ... beyond the transformers context'; the technique itself is re-derived locally using the external textbook theorem, so the citation is not load-bearing. The paper's own limitation statement about LayerNorm ('with layernorm, we no longer have good upper bounds on the VC dimension guaranteed by Theorem 3') is a genuine caveat, and the skeptic's worry that Theorem 3 may not cover exp-containing arithmetic circuits is a correctness risk about an external theorem, not evidence that a result equals its input by construction. Experiments are explicitly disclaimed as proof ('training failure is not evidence of impossibility'), so there is no fitted-input-called-prediction pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The theoretical claims are built from the layer formalism and a cited VC-dimension bound; no numbers are fitted to data in the derivations. The positive constructions use explicit but arbitrary 'large enough' constants, which are not free parameters since their exact values are irrelevant. No new physical entities are postulated; causal complexity is a definition, not an entity.

axioms (4)
  • standard math VC-dimension bound of Theorem 3 (O(AC^2 p^2)) holds for concept classes computed by arithmetic programs over the reals with exp, +, -, *, /, and comparisons.
    Cited from Anthony-Bartlett Theorem 8.14; used in Theorem 12(a) and Theorem 14(b) to bound VC dimension of all small layers. If the bound fails for exp/comparison programs, all infinite-precision lower bounds are unsupported.
  • domain assumption The layer + readout formalism (Definition 4) with input-position embeddings and an output matrix faithfully captures how these architectures solve sequence tasks.
    All upper and lower bounds are expressed in this formalism; it abstracts away training, normalization, and precision details.
  • domain assumption Small size (n^{o(1)} parameters) implies small dimension d and small arithmetic complexity of the non-polynomial components for the layers in Definitions 5–9.
    Used in Propositions 13 and Theorem 14(b) to conclude n^{o(1)} causal complexity / VC dimension for RNNs, SSMs, and linear attention.
  • ad hoc to paper ReLU MLPs of constant size can implement the needed threshold/marker functions (e.g., |k-i'|<0.01) exactly or to the required precision.
    Used in the positive constructions (Theorems 12b and 14c); no explicit construction is given.

reviewed 2026-08-01 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Indexing: the Beginning and the End." pith.science (2026). https://pith.science/paper/BSUWFOJH

@misc{pith2026260722361,
  author       = {Pith},
  title        = {Pith review of: Indexing: the Beginning and the End},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BSUWFOJH}},
  note         = {Machine review of arXiv:2607.22361}
}
Share X Bluesky LinkedIn Reddit HN
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 7 linked inside Pith

  1. [1]

    and Bartlett, P

    Anthony, M. and Bartlett, P. L. (2009). Neural network learning: Theoretical foundations . cambridge university press

    2009

  2. [2]

    L., Kiros, J

    Ba, J. L., Kiros, J. R., and Hinton, G. E. (2016). Layer normalization. arXiv preprint arXiv:1607.06450

    Pith/arXiv arXiv 2016

  3. [3]

    Barcelo, P., Kozachinskiy, A., and Steifer, T. (2025). Ehrenfeucht-haussler rank and chain of thought. In Forty-second International Conference on Machine Learning

    2025

  4. [4]

    Chen, L., Peng, B., and Wu, H. (2025). Theoretical limitations of multi-layer transformer. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2631--2653. IEEE

    2025

  5. [5]

    Chiang, D., Cholak, P., and Pillay, A. (2023). Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning , pages 5544--5562. PMLR

    2023

  6. [6]

    Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., et al. (2021). A mathematical framework for transformer circuits. Transformer Circuits Thread , 1(1):12

    2021

  7. [7]

    and Dao, T

    Gu, A. and Dao, T. (2023). Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752

    Pith/arXiv arXiv 2023

  8. [8]

    Guan, X., Liu, Y., Lin, H., Lu, Y., He, B., Han, X., and Sun, L. (2024). Mitigating large language model hallucinations via autonomous knowledge graph-based retrofitting. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 38, pages 18126--18134

    2024

  9. [9]

    Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics , 8:156--171

    2020

  10. [10]

    Jiang, H., Hahn, M., Zetzsche, G., and Lin, A. W. (2025). Softmax transformers are turing-complete. arXiv preprint arXiv:2511.20038

    arXiv 2025

  11. [11]

    and Macintyre, A

    Karpinski, M. and Macintyre, A. (1997). Polynomial bounds for vc dimension of sigmoidal and general pfaffian neural networks. Journal of Computer and System Sciences , 54(1):169--176

    1997

  12. [12]

    Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. (2020). Transformers are rnns: Fast autoregressive transformers with linear attention. In International conference on machine learning , pages 5156--5165. PMLR

    2020

  13. [13]

    Kozachinskiy, A., Urrutia, F., Orellana, H., Steifer, T., Pizarro, G., Fuentes, M., Meza Va \'a squez, F., Buc Calderon, C., and Rojas, C. (2025). Strassen attention, split vc dimension and compositionality in transformers. Advances in Neural Information Processing Systems , 38:9665--9696

    2025

  14. [14]

    Merrill, W., Li, Y., Romero, T., Svete, A., Costello, C., Dasigi, P., Groeneveld, D., Heineman, D., Kuehl, B., Lambert, N., et al. (2026). Olmo hybrid: From theory to practice and back. arXiv preprint arXiv:2604.03444

    Pith/arXiv arXiv 2026

  15. [15]

    Merrill, W., Petty, J., and Sabharwal, A. (2024). The illusion of state in state-space models. arXiv preprint arXiv:2404.08819

    Pith/arXiv arXiv 2024

  16. [16]

    and Sabharwal, A

    Merrill, W. and Sabharwal, A. (2024). The expressive power of transformers with chain of thought. In International Conference on Learning Representations , volume 2024, pages 7690--7706

    2024

  17. [17]

    Minsky, M. (1967). Computation: Finite and Infinite Machines . Prentice-Hall

    1967

  18. [18]

    Olsson, C., Elhage, N., Nanda, N., Joseph, N., DasSarma, N., Henighan, T., Mann, B., Askell, A., Bai, Y., Chen, A., et al. (2022). In-context learning and induction heads. arXiv preprint arXiv:2209.11895

    Pith/arXiv arXiv 2022

  19. [19]

    Peng, B., Narayanan, S., and Papadimitriou, C. (2024). On limitations of the transformer architecture. In First conference on language modeling

    2024

  20. [20]

    P \'e rez, J., Barcel \'o , P., and Marinkovic, J. (2021). Attention is turing-complete. Journal of Machine Learning Research , 22(75):1--35

    2021

  21. [21]

    Ramachandran, P., Zoph, B., and Le, Q. V. (2018). Searching for activation functions. In International Conference on Learning Representations

    2018

  22. [22]

    a lzer, M., K \

    S \"a lzer, M., K \"o cher, C., Kozachinskiy, A., Zetzsche, G., and Lin, A. W. (2025). The counting power of transformers. arXiv preprint arXiv:2505.11199

    arXiv 2025

  23. [23]

    Sanford, C., Hsu, D., and Telgarsky, M. (2024). One-layer transformers fail to solve the induction heads task. arXiv preprint arXiv:2408.14332

    Pith/arXiv arXiv 2024

  24. [24]

    Sarrof, Y., Veitsman, Y., and Hahn, M. (2024). The expressive capacity of state space models: A formal language perspective. Advances in Neural Information Processing Systems , 37:41202--41241

    2024

  25. [25]

    Shakerinava, M., Khavari, B., Ravanbakhsh, S., and Chandar, S. (2026). The expressive limits of diagonal ssms for state-tracking. arXiv preprint arXiv:2603.01959

    arXiv 2026

  26. [26]

    Siegelmann, H. T. and Sontag, E. D. (1994). Analog computation via neural networks. Theoretical Computer Science , 131(2):331--360

    1994

  27. [27]

    Strobl, L., Angluin, D., and Frank, R. (2025). Concise one-layer transformers can do function evaluation (sometimes). arXiv preprint arXiv:2503.22076

    Pith/arXiv arXiv 2025

  28. [28]

    Strobl, L., Merrill, W., Weiss, G., Chiang, D., and Angluin, D. (2024). What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics , 12:543--561

    2024

  29. [29]

    Yang, A., Chiang, D., and Angluin, D. (2024). Masked hard-attention transformers recognize exactly the star-free languages. Advances in Neural Information Processing Systems , 37:10202--10235

    2024

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.