{"id":"55d82164-6a2b-4942-9fac-2deccddc0a4a","arxiv_id":"2607.22361","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"The paper proves new expressivity limits for RNNs, state-space models, and masked linear-attention transformers on a simple indexing task, and shows softmax transformers and RNNs have advantages depending on where the query appears. The theory holds even for infinite-precision models, and small-scale experiments line up with the separations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's VC-dimension bound may not cover exp-containing arithmetic circuits; all impossibility results hinge on this unverified external assumption.","rationale":"I reviewed the proof of Theorem 12.a in detail. The construction of the combined fingerprint as a parameter vector is valid: for each sigma, the L layer-fingerprints are instantiated as parameters, and the output is computed from them and x_{n+1} in n^{o(1)} arithmetic operations, so the concept class has the stated p and AC. The only external step is the invocation of Theorem 3 for classes that may contain exp. Since the paper's own discussion of LayerNorm indicates awareness that Definition 1's operation set is not automatically covered by the cited theorem, the same scrutiny applies to exp. This is not an internal inconsistency but a missing justification in the central lower-bound chain. The reader's weakest assumption is the same one, and I agree it is load-bearing. The experimental appendix and positive constructions are plausible and do not affect this concern. Thus the verdict should remain conditional pending verification of the VC-dimension bound for exp-enabled arithmetic circuits.","tokens_in":16116,"tokens_out":22648,"duration_ms":197050,"concrete_test":"Consult the statement of Anthony and Bartlett (2009), Theorem 8.14, and verify whether the operation set it covers includes the exponential function. If it does not, take any lower-bound proof (e.g., Theorem 14.b, SSM case) and replace the output map phi with a ReLU MLP (no exp), leaving all other assumptions unchanged. If the proof still goes through, the exp issue is a scope limitation; if it does not go through, the claims about Mamba/SSM with exp-based nonlinearities are not supported. Alternatively, check whether a Pfaffian VC bound (Karpinski and Macintyre, 1997) provides a polynomial bound in AC and p for Definition 1's operation set; if yes, the contradiction still holds (n^{o(1)} VC dimension vs n), and the paper merely needs to update the citation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The impossibility theorems (12.a, 14.b) all build concept classes whose arithmetic complexity is measured under Definition 1, which explicitly includes the exponential function. They then apply Theorem 3 (Anthony & Bartlett, 2009, Thm 8.14) to bound VC dimension by O(AC(C)^2 p^2). If that theorem's operation set is limited to +, -, *, /, and comparisons (as is standard for arithmetic-circuit results), it does not justify the bound for classes that compute exp internally. This matters concretely: Mamba's output map phi uses SiLU (expressed via exp) and linear-attention kernels commonly use ELU (also exp). The paper itself flags a related gap for LayerNorm's square root and says Pfaffian bounds (Karpinski and Macintyre, 1997) would be needed; no analogous qualification is made for exp, although Definition 1 includes it. Consequently the 'unconditional' lower bounds for exp-based SSMs and masked linear-attention transformers are not actually established by the cited theorem. This is the single load-bearing assumption: if the bound fails (or is unproven) for exp, the central impossibility results collapse, because the n-versus-n^{o(1)} VC-dimension contradiction is the only mechanism producing them.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16431,"tokens_out":42097,"duration_ms":339969,"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":[{"comment":"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","section":"§2.1 (Definition 1 and Theorem 3)"}],"minor_comments":[{"comment":"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.","section":"§3, Theorem 12.b proof"},{"comment":"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.","section":"§4, Eq. (8)"},{"comment":"The column headed 'Thm.' is empty in the table; either remove it or include the theorem numbers that certify each row's ✓/✗ classification.","section":"§5.2, Table 2"},{"comment":"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.","section":"§2.3, Mamba paragraph"}],"recommendation":"major_revision","confidential_remarks":"The paper is potentially strong, but the single load-bearing external assumption—whether the cited VC-dimension bound covers the exponential function in Definition 1—must be resolved before the lower bounds are credible. This is a fixable issue: the authors can add a proof/citation for a Pfaffian VC bound or restrict the claims to semialgebraic classes. I would not reject on this basis, but the current version cannot be accepted as-is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read Kozachinskiy et al. on indexing. The core idea is good: they define causal complexity, show low causal complexity forces small VC dimension, and use that to get constant-depth infinite-precision lower bounds for RNNs, SSMs, and masked linear-attention transformers on right-hand indexing. The separation table—softmax in 1 layer, full linear attention in 2, RNNs winning left-hand indexing—is genuinely new and worth thinking about. The upper-bound constructions are sketched but plausible, and the experiments are honest: they distinguish constructive from stress-test configurations and don't overclaim training failure as proof.\n\nThe main thing to check before citing this as unconditional: Theorem 3 cites Anthony and Bartlett's Theorem 8.14 for concept classes that include exp in their arithmetic complexity. The standard arithmetic-circuit versions of that bound cover +, -, *, /, and comparisons, not exponentiation. The paper needs to either verify that A&B 8.14 includes exp, or replace the citation with a Pfaffian bound (Karpinski-Macintyre) that does. The authors show they're aware of the issue for LayerNorm's square root; they don't mention exp. This matters concretely: Mamba's SiLU and the common ELU kernel in linear attention both use exp. If Theorem 3 doesn't cover exp, the impossibility results for those architectures aren't established by the cited theorem. I suspect the gap is repairable—Pfaffian bounds give the same polynomial VC dimension—but as written, the abstract's 'unconditional' claim overreaches.\n\nA second, minor soft spot: the positive constructions in Theorem 12 rely on 'sufficiently large' constants and small-error arguments. They're believable, but a referee will want formal details. That's a revision, not a rejection.\n\nOverall, the causal-complexity framework is a real step forward for precision-independent lower bounds on non-transformer architectures. The paper deserves a serious referee. I'd ask the authors to nail down the VC-dimension citation for exp before publication. Once that's fixed, this is a paper I'd cite and bring to the reading group.","headline":"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.","tokens_in":16844,"tokens_out":8894,"would_cite":true,"duration_ms":76767,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["indexing","causal complexity","transformers","linear attention","state-space models","RNNs","VC dimension","expressivity"],"falsifier":"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.","tokens_in":16021,"feed_emoji":"🔍","tokens_out":8113,"duration_ms":58465,"temperature":0.7,"pith_summary":"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.","feed_headline":"Small masked models can't retrieve by index in constant depth","feed_subtitle":"A one-layer softmax transformer solves it; no constant-depth small RNN, SSM, or masked linear attention can.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Index at end defeats tiny RNNs, SSMs, masked attention","Softmax transformer solves indexing in one layer, masked can't","Masked linear attention fails indexing: constant depth barrier","Indexing bottleneck: causal complexity blocks masked models","Right-hand index impossible for constant-depth masked nets"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Index at end defeats tiny RNNs, SSMs, masked attention","Softmax transformer solves indexing in one layer, masked can't","Masked linear attention fails indexing: constant depth barrier","Indexing bottleneck: causal complexity blocks masked models","Right-hand index impossible for constant-depth masked nets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000164,"raw_usage":{"total_tokens":1099,"prompt_tokens":775,"completion_tokens":324,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":244}},"tokens_in":519,"tokens_out":324,"duration_ms":4066,"temperature":1.0,"reasoning_tokens":244,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T05:01:39.332466+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}