acceptodds
Under review as a conference paper at ICLR 2027

A Second-Order Complexity Analysis of Attention and State-Space Models

Abstract

Standard analyses of sequence models characterize efficiency primarily in terms of sequence length, such as quadratic-time attention or linear-time state-space models. We show that sequence-length complexity alone does not determine the resources needed to evaluate a model at a prescribed accuracy. We develop a second-order complexity analysis of attention and selective state-space operators, explicitly accounting for approximation accuracy, input regularity, representation, and effective memory. For representative attention and selective state-space operators, we derive matching deterministic sampling bounds that distinguish the cost of resolving a signal from the amount of history required. Even a stable state-space operator requires exponentially many point queries in the requested accuracy bits on bounded Lipschitz inputs, while quantitative smoothness and stability certificates enable polynomial-time evaluation under fixed resource bounds. We introduce precision locality: the shortest recent context sufficient to recover the full-history output without a cached summary of earlier inputs. On arbitrary bounded token sequences, certified contractive selective scans admit context lengths logarithmic in inverse error at fixed contraction and magnitude bounds, whereas uniform attention requires nearly the entire sequence at high accuracy. We construct evaluators with certified context lengths and numerical precision budgets, including explicit conditions for Mamba’s selective recurrence. We further prove that approximating persistent statistics over growing horizons requires weaker contraction, larger state magnitudes, or stronger amplification. These results connect precision-dependent evaluation costs with long-range approximation limits and provide a mathematical basis for analyzing the balance between forgetting and persistent memory.

Primary area:
learning theory
Keywords:
Second-Order Complexity, Attention, State-Space Model, Precision Locality

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_pBNKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

A number of sequence processing primitives have been developed, such as self-attention and SSM layers. This paper studies the second-order sample complexity of these: each primitive is associated with a smooth operator that takes input sequences with an index set [0,T][0, T] rather than discrete sequences. For each of these operators, matching sample complexity upper bounds and lower bounds are identified on Gevrey-ss classes, representing the required number of input locations that need to be sampled. The four operators studied are uniform (simple averaging), softmax attention, SSMs, and selective SSMs. For the longer-range operators of attention and uniform, these bounds depend on TT, the context length, while the shorter-range operators from SSMs do not. This forms a separation between these operators.

Critical strengths

Using second-order analysis, with representative operators for various language modeling components, is a clean way to analyze differences between these components. It provides a handful of matching lower and upper bounds for sample complexity, depending on the smoothness of the input. These separate SSMs from attention, showing that attention requires more samples, adding to the memory complexity and computational complexity of evaluating attention.

Critical weaknesses

Second-order complexity seems to rely on continuous forms of smoothness, which may not hold in practice. While the theory for continuous inputs is quite insightful, translating this to models with discrete inputs, such as those processing natural language, may be challenging. This is especially true as many operations that attention and SSMs are expected to do, such as associative recall and selective copying, are not smooth and require careful long-range dependencies. The results for discrete data bound the error based on the certificates rather than establishing similar sample complexity bounds.

Questions for authors
  1. Notation in general is understandable, but could there be a consolidated table of most notation at the start of the appendix? It would be a very useful reference when reading.
  2. Does the term "certificate" come from prior work? The work and abstract reference certificates before they are defined at the beginning of Section 4, making understanding difficult on the first few reads.
  3. Is there some connection that can be made to settings with smooth inputs, possibly relating to time-series or something similar? If there is, that would motivate using second-order complexity.
Reviewer_xN9DOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the resources needed to approximate attention and selective state-space outputs to a certain degree of accuracy. Notably, it introduces the notion of precision locality (which is defined as the amount of recent context needed to reconstruct an output without a cached summary of earlier inputs). For simplified attention and SSMs, this work establishes how many samples and how much numerical precision are needed to achieve a given accuracy. It also derives context length bounds for various Mamba models and shows how strong forgetting limits their ability to capture long term statistics, such as the average of an entire sequence.

Critical strengths
  1. Strong and thorough theoretical results. The paper establishes matching upper and lower bounds on the number of samples needed to approximate certain attention and state-space operators. The analysis also accounts for numerical precision rather than just the number of operations.

  2. Analysis of memory and forgetting. The paper provides explicit bounds relating the strength of forgetting to the amount of context needed to reproduce a model's output, including results for Mamba variants which are particularly relevant in current research on sequence mixing.

Critical weaknesses
  1. Limited novelty in the architectural insights. The main observation that contractive recurrent models can be approximated using a short context is already established in prior work [1]. While the paper provides tighter theoretical bounds, much of the new analysis concerns simplified continuous operators, and it not clear what additional insight this provides into modern sequence architectures.

  2. Lack of empirical validation. The paper is entirely theoretical, with no experiments on trained models. In particular, the authors do not demonstrate whether their context length bounds for Mamba provide meaningful reductions in practice. Without such validation, it is difficult to assess the practical significance of the results.

[1] Sliding Window Recurrences for Sequence Models

Questions for authors
  1. Beyond providing tighter theoretical bounds, what new insights about sequence model design does this work offer compared with existing results on exponential forgetting?

  2. Can the authors evaluate their context length guarantees on trained Mamba models and compare the predicted context lengths with those actually needed to achieve a given approximation error?

  3. Can the authors demonstrate how these guarantees extend to a full multi-layer model, including how approximation errors accumulate across layers?

I will consider revising my score if some of the above questions/concerns are adequately addressed

Reviewer_G7pMOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper asks how much recent context, and how many input samples, are needed to evaluate one output of a fixed sequence operator to accuracy 2−n2^{-n} when no cached state is available, and it studies the question within Kawamura–Cook second-order complexity. Its central notion, precision locality (Definition 2.1), is the shortest suffix from which the full-history endpoint output can be recovered within 2−n2^{-n} for every admissible history. On Gevrey-ss input classes, Theorem 3.1 proves matching deterministic query bounds of Θ(Tns)\Theta(Tn^s) for uniform attention and a bounded-logit softmax witness, against Θ(nsmin⁡{T,n})\Theta(n^s\min\{T,n\}) for a stable filter and an input-selective SSM. Companion results cover Lipschitz inputs (Proposition 3.3), randomized evaluation of the uniform average (Theorem 3.4) and the exact cost of the decay margin, Θ(ns+1/γ)\Theta(n^{s+1}/\gamma) (Proposition 4.3). Section 4 builds certified finite-bit evaluators under regularity and stability certificates, and Theorem 5.1 shows that a contractive selective SSM can approximate the global mean to error βs/4\beta_s/4 only if γT≤2log⁡(4MKD/βs)\gamma T \le 2\log(4MKD/\beta_s). Section 6 carries the picture over to tokens. There, contractive scans need a suffix logarithmic in the inverse error, uniform attention needs ⌈(1−2−n)N⌉\lceil(1-2^{-n})N\rceil tokens, and explicit context certificates are derived for Mamba and Mamba-3. The paper is purely theoretical and contains no experiments.

Critical strengths
  • (S1) The question is clean and the decomposition is useful. The usual quadratic-versus-linear comparison mixes two resources, and the paper separates them: how far back evaluation must reach, and how densely the retained history must be sampled. The example in Section 1 makes this tangible. The mean of 10,000 values needs 9,900 of them for error 0.01, whereas the scan hi=0.9hi−1+0.1vih_i = 0.9h_{i-1}+0.1v_i needs only 44, and yet that 44-token suffix cannot distinguish global means near +1+1 and −1-1.

  • (S2) The bounds are sharp and the proofs are careful. The lower bounds of Theorem 3.1 hold against adaptive algorithms with exact point values. They rely on the periodic construction of Lemma B.2, which hides mass from any finite query set while staying analytic, so compact support is never needed.

  • (S3) The evaluators are constructive and the certificates reach real architectures. Every upper bound comes with a finite-bit algorithm whose error budget covers reset, coefficient approximation, Picard iteration and rounding. Eq. (26) turns accumulated contraction into an input-adaptive stopping rule for Mamba. Appendix D.6 derives the Mamba-3 certificate from parameter norms and handles rotations, two-token forcing, MIMO readouts and RMS normalization.

Critical weaknesses
  • (W1) The contribution is not separated from classical results, so the novelty is hard to judge. Firstly, the sharp laws for the uniform average and the stable filter (Theorem 3.1, Proposition 3.3, Theorem 3.4) are weighted-integration problems from point values. Their deterministic and randomized complexity on Lipschitz, smooth and analytic classes is a core topic of information-based complexity (Traub et al., 1988; Novak, 1988). The Θ(2n)\Theta(2^n) Lipschitz law is the classical Θ(1/ε)\Theta(1/\varepsilon) rate and the Θ(4n)\Theta(4^n) randomized law is the Monte Carlo rate Θ(ε−2)\Theta(\varepsilon^{-2}), yet neither body of work is cited. Secondly, Kawamura et al. (2015) already establish parameterized polynomial-time integration on Gevrey classes in the bit model. The paper cites only their 2012 preprint, uses it as background, and does not state what Theorem 3.1 and Corollary 3.2 add beyond explicit horizon dependence. Thirdly, the memory-side ingredients have precedents as well. Section 2 describes Definition 2.1 as the approximately-finite-memory window of Sandberg and of Hanson & Raginsky with the horizon made explicit. Corollary 6.1(i) is the truncation argument of Miller & Hardt (2019). Theorem 5.1 is close in spirit to the curse-of-memory analysis of Li et al. (2021), which is not cited. A short table pairing each result with its closest prior statement would let readers credit the genuinely new parts. In my reading, these are the horizon-uniform rates, the input-selective witness, Proposition 4.3 and the Mamba-3 certificate.

  • (W2) The theorems separate persistent from fading memory, while the title and abstract present this as a separation between attention and SSMs. Firstly, every attention lower bound relies on heads whose logits are bounded and do not depend on the values. The uniform head uses WQ=WK=0W_Q = W_K = 0, and A∗A_* takes its logits from a known positional channel (Eq. 7, Appendix D.3). Such heads give each past token weight at least e−2B/Ne^{-2B}/N, so they cannot be precision-local by construction, and Corollary 6.1(ii) assumes exactly this setting. The results therefore say nothing about content-dependent logits, which are what distinguish attention from fixed averaging. Secondly, the roles reverse once memory structure changes. An SSM with γ→0\gamma \to 0, such as the integrator in Section 5, is not precision-local. Attention with a recency bias, such as ALiBi (Press et al., 2022) or the Forgetting Transformer, is precision-local, as Section 5 itself acknowledges. A short calculation suggests a radius of order (n+B)/m(n+B)/m for an ALiBi slope mm, and adding such a result would let both rows of Table 1 be parameterized by the same decay quantity.

  • (W3) Nothing shows that the certificates are informative for trained models, and the guarantees stop at a single block. Firstly, the paper offers its certificates as a quantitative basis for selecting context (Sections 4, 6 and 7), but computes none for any checkpoint. The uniform bound is governed by the slowest channel and token through min⁡kakΔik\min_k a_k\Delta_{ik}, which can make it vacuous. Appendix D.6 proposes the enforced floor as the Mamba-3 certificate, and footnote 1 reports a default of afloor=10−4a_{\text{floor}} = 10^{-4}. Eq. (76) then gives ℓn≥nlog⁡2/(10−4δ)\ell_n \ge n\log 2/(10^{-4}\delta). That is about 69,000 tokens at n=10n = 10, even under the generous choices δ=1\delta = 1 and CoutD∗=1C_{\text{out}}D_* = 1. For any shorter sequence, the certified window is therefore the trivial NN. Secondly, this is structural rather than accidental. By Theorem 5.1 and Proposition 4.3, models that retain long-range information must have small margins, so the uniform certificate weakens exactly where it matters. The adaptive rule in Eqs. (26) and (75) may be far tighter, but its behavior on real inputs is unknown.

References

  • Joseph F. Traub, et al. Information-Based Complexity. Academic Press, 1988.

  • Erich Novak. Deterministic and Stochastic Error Bounds in Numerical Analysis. Lecture Notes in Mathematics, vol. 1349. Springer, 1988.

  • Akitoshi Kawamura, et al. Computational benefit of smoothness: Parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy. Journal of Complexity, 31(5):689–714, 2015.

  • Zhong Li, et al. On the curse of memory in recurrent neural networks: Approximation and optimization analysis. In International Conference on Learning Representations (ICLR), 2021.

  • Ofir Press, et al. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations (ICLR), 2022.

  • Samy Jelassi, et al. Repeat after me: Transformers are better than state space models at copying. In Proceedings of the 41st International Conference on Machine Learning (ICML), PMLR 235, pp. 21502–21521, 2024.

Questions for authors
  • (Q1) Theorem 5.1 is a necessary condition. Is it close to sufficient? For instance, does SγS_\gamma with γ\gamma of order 1/T1/T, or an integrator with bounded readout, reach error βs/4\beta_s/4 with MKDMKD of the same order? A two-sided statement would make the stability-memory tradeoff sharp and would raise my assessment of significance.

  • (Q2) Can Theorem 5.1 be extended from the global mean to retrieval-type targets, where the output is a token whose position is revealed only at the end? How would the resulting condition relate to the state-size lower bounds for copying and associative recall (Jelassi et al., 2024; Arora et al., 2024)? A clear connection would place the paper within the current attention-versus-SSM debate and would strengthen its significance.

  • (Q3) The continuous setting is motivated by neural operators, whose inputs are typically only Sobolev or Hölder regular. Under smoothness of order rr, does the separation become Tε−1/rT\varepsilon^{-1/r} against ε−1/rlog⁡(1/ε)\varepsilon^{-1/r}\log(1/\varepsilon), and what remains of the polynomial-time claims? If the qualitative picture survives finite smoothness, my concern about the restrictiveness of the Gevrey assumption would be resolved.

Reviewer_QuyiOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The main problem the paper is trying to address is how much of the recent sequence history is needed to approximately reproduce the model's output with full history given a prescribed accuracy. The authors compare attention mechanism with state-space models(SSM). Attention can depend on the full length of the sequence but SSM can forget older tokens while maintaining a summary of the inputs. They prove how many input samples are required to generate the full-history output for several simple models. They give context length guarantees for contractive scans including Mamba-style recurrences under stability assumptions. The authors also show that forgetting helps with recovering the output from a short suffix but can make it harder to preserve information such as full-length sequence average.

Critical strengths
  1. The paper addresses a clear research problem on how much of the history is needed to approximate a models full-sequence output within a chosen error.

  2. For the specific models studied in the paper, the authors provide precise bounds on how many input samples are enough and how many are necessary.

  3. The authors provide explicit bounds on how much past info is needed by a stable scan including Mamba-style models to reproduce its full-sequence output. They are also able to explain the trade-off between forgetting the past info and the fact that it makes early inputs harder to maintain.

Critical weaknesses
  1. The continuous input results depend on strong smoothness bounds. For the required number of samples to approximate the signal, the authors need to assume how quickly the signal changes and how all higher order derivatives behave. They do not show if the real world data can satisfy these conditions.

  2. The attention results are shown for specific attention setup. In theorem 3.1, the attention score only depend on the known z(t) part of the signal and are independent of the values x(u). The same setup is also assumed for discrete case. So, the authors show the sampling cost for the restricted attention case by sharp bounds but do not provide the same results for general transformers where the attention scores depend on the tokens.

  3. The paper provides no experiments on real models or simple models. It has not been shown whether the assumptions hold for trained models and data or the results can be verified through experiments. For example, adding experimental results on usefulness of the predicted context length can be helpful.

  4. The novelty is not clear and it can be mentioned more explicitly. A result by result comparison with the most related prior work can be helpful.

  5. In equation (1), Fx and G are not properly defined. From the context I understand the former is the output of the model with full length input and the latter is the output using suffix R_Hx. Defining them explicitly would improve readability.

Questions for authors
  1. Can you apply your results to a trained Mamba model? How realistic are the certificates required by corollary 6.1(i) for a trained Mamba model?

  2. Weakness 2: can you prove upper and lower bounds for a more general attention mechanism where the scores and value projection depend on the actual tokens? What additional assumptions would be needed?

  3. You assume no saved state or attention cache is available from the earlier sequence but in standard SSM and transformers that info is usually carried. Why is this necessary and how would the context length bounds change if the evaluator had that information?

  4. The paper studies both continuous signals and discrete token sequences. Transformers and Mamba models usually work with discrete token sequences. What does motivate considering continuous input setting and how do its result connect to discrete token based models such as transformers and Mambas?

1 comment
Reviewer_QuyiOpenReview ↗

Response to Authors

Thank you for the detailed response. The attention results and Mamba experiment address some of my concerns. The signal example also illustrates the assumption but it is not still clear whether the derivative bounds in assumption are realistic for measured signals. My main concern is the lack of synthetic and real data experiments for directly testing the theoretical results. Also, the new results are only in the rebuttal and there is no revised version of the paper available. Therefore, I will keep my current rating.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.