acceptodds
Under review as a conference paper at ICLR 2027

A Comparative Analysis of Attention versus State-Space Models for In-Context Learning

Abstract

Transformers and state-space models (SSMs) are two prominent sequential learning architectures, yet their comparison remains largely empirical and existing theoretical analyses are typically task-specific or architecturally restricted. In this paper, we develop *belief geometry*, a unified analytical framework for comparing the representational capabilities of broad classes of attention and SSMs. Starting from a generalized formulation of in-context linear regression and using cumulative Bayes regret as our measure, we abstract three capabilities required by many sequential learning problems in our belief geometry: evidence assembly, belief maintenance, and addressing. We then study three cases of our formulation that isolate these capabilities and yield sharp architectural lessons: For belief maintenance, SSMs attain the optimal regret over stationary aggregation kernels; for positional assembly, SSMs have a memory advantage; and for content addressing, softmax attention has an exponential width advantage over sigmoid-selective SSMs. Experiments with LLaMA-type Transformers and Mamba-2 show that these architectural insights extend beyond our analytically tractable classes and linear-regression testbed.

Primary area:
learning theory
Keywords:
in-context learning, transformers, attention, state-space models, representational analysis, belief geometry, cumulative regret, comparative analysis, sequential learning

Reviews

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

The paper introduces belief geometry to compare attention architectures and state-space models (SSMs) in sequential in-context learning. Using Bayesian linear regression with routed observations and cumulative Bayes regret, it studies three capabilities: belief maintenance, evidence assembly, and content addressing.

The results favor SSMs for stationary belief maintenance and memory-efficient assembly of positionally separated evidence. For content-dependent routing, fixed-depth linear attention and affine-transition SSMs incur linear regret, while softmax attention achieves sublinear regret with logarithmic key dimension; sigmoid-selective SSMs require nearly linear state dimension.

Synthetic filtering and contextual bandit experiments, including LLaMA-type Transformers and Mamba-2, qualitatively support these architectural trade-offs.

Critical strengths

Strength 1: A unified framework linking architecture to statistical performance

Belief geometry decomposes sequential Bayesian prediction into evidence assembly, belief maintenance, and content addressing, providing a common framework for comparing attention and SSMs through cumulative regret.

The framework yields concrete regret lower bounds, constructive upper bounds, and resource comparisons across three increasingly demanding settings. By identifying the operations behind architectural differences, it may also inform analyses beyond the regression setting studied.

Strength 2: Quantitative separations supported by targeted experiments

Key results include the optimal stationary-kernel comparison, SSMs’ memory advantage under positional routing, and the nearly linear recurrent-state requirement for selective SSMs under content addressing. The last result is particularly notable for bounding real-valued state dimension without finite-precision assumptions.

Experiments with practical architectures and nonlinear tasks provide complementary support. Despite empirical limitations, the combination of lower bounds, constructions, and targeted evaluations strengthens the contribution.

Critical weaknesses

Weakness 1: The theoretical conclusions are less general than some of the architectural interpretations suggest

Although the paper presents belief geometry as a general framework, its strongest comparative conclusions depend on restricted architecture classes and specific routing constructions.

For example, the stationary-kernel comparison applies to one-layer linear attention and fixed-transition SSMs, whereas richer architectures can overcome the corresponding stationary regret floor. Similarly, the content-addressing lower bounds are established for particular classes of linear attention and affine or sigmoid-selective transitions at fixed depth. They do not directly characterize arbitrary practical Transformers or nonlinear recurrent architectures.

This distinction is consequential because the principal motivation is to explain the relative capabilities of modern attention and SSM architectures. The experiments offer supporting evidence, but they cannot by themselves close the theoretical gap.

I would view this limitation as less concerning if the paper more consistently distinguished properties of the analyzed architecture classes from broader architectural conclusions.

Weakness 2: The experimental evidence does not conclusively establish the claimed scaling advantages for practical architectures

The practical experiments are carefully designed to investigate particular mechanisms, but their quantitative interpretation is complicated by architecture-specific optimization choices and limited scaling regimes.

For instance, the content-routing experiments use different training schedules and numbers of random seeds for Transformers and Mamba-2. The authors also select the best validation-performing runs from hyperparameter searches. These choices may be appropriate for demonstrating achievable performance, but make it difficult to separate representational limitations from optimization effects.

More importantly, the content-routing width-scaling experiment fixes the horizon at T=256T=256 while increasing the codebook size to R=128R=128. This does not satisfy the asymptotic regime R=o(Tρ)R=o(\sqrt{T_\rho}) used in the corresponding theoretical comparisons. The observed scaling therefore provides suggestive finite-sample evidence, but does not directly validate the asymptotic width separation.

This matters because the practical implications of the paper rely substantially on demonstrating that the predicted resource trade-offs persist beyond the restricted theoretical classes.

Questions for authors
  1. Scope of the content-addressing separation. Theorem 3 applies to restricted fixed-depth architectures. Which nonlinear mechanisms in practical Mamba-2 fall outside its assumptions, and does the state-dimension lower bound extend to nonlinear writes or reads? Appendix D.1.4 finds little performance loss from fixing transitions while retaining nonlinear writes. How does this affect the interpretation of transition selectivity as the mechanism behind the separation?

  2. Interpretation of resource scaling. Figure 6 increases codebook size at fixed T=256T=256, while the theory requires R=o(Tρ)R=o(\sqrt{T_\rho}). Does the observed width scaling persist in that regime? Jointly varying TT and RR, or clarifying which conclusions hold independently of the asymptotic theory, would help resolve this gap.

  3. Optimization versus capacity. The architectures use different alignment durations, parameter-freezing strategies, and hyperparameter searches. How do the authors distinguish representational limits from optimization difficulties? Could additional training or changes to Mamba-2’s optimization substantially alter the observed width-scaling trend?

5 comments
AuthorsOpenReview ↗

Response to Reviewer LCKz (1/3)

We thank the reviewer for the thorough review and for recognizing belief geometry as a unified framework linking architecture to statistical performance. The points raised have led to revisions that strengthen the paper throughout, and we address each point in turn below.

(W1) Theoretical scope and practical evidence. The reviewer is correct that the architectural separation results we derive in this paper are proved for the analyzed classes of §2.1. To make this unmistakable, the revision now consistently distinguishes between these results and our practical evidence, from the abstract to the conclusion (changes listed below). Our analysis is designed to isolate the core mechanisms behind these separations, and our experiments support exactly this: the predicted trade-offs still emerge in practical models. This indicates that our theory remains consequential beyond the classes for which its results are proved.

In LLaMA-type Transformers and Mamba-2, these trade-offs emerge in all three cases: the kernel preferences of Case 1 as inductive biases (§3, Fig. 2), the positional-assembly mechanisms and memory advantage of Case 2.a (§4.1, Fig. 4), and the content-addressing mechanisms and width separation of Case 2.b (§4.2, Figs. 5–6). These mechanisms also surface on real benchmarks: Arora et al. (2023) trace most of the language-modeling gap between attention and gated-convolution models to the recall of earlier context (App. A), precisely the content-addressing operation in which our results give attention its exponential width advantage (Thm. 3(c) and Prop. 4). Although practical models differ from our analyzed classes, this evidence suggests that our analysis captures the essence of what separates the two families in practice.

Finally, we want to make sure the reach of the two results the reviewer cites is not understated. First, Case 1's stationary-kernel comparison deliberately starts with the simplest classes of both families to isolate their core belief-maintenance mechanisms, which still matter in practical models (Fig. 2). Our paper also proves sharp regret rates for richer architectures that escape the stationary floor (App. E.2, Props. 6–7). Second, the content-addressing lower bounds hold at every fixed depth for SSMs whose first layer can use any of four different selective transitions drawn from practical architectures, including those of Mamba-2, Gated DeltaNet, and RWKV-7 (§2.1, App. C.1). More broadly, belief geometry itself is general: its regret decomposition (Eq. 2) and two-factor floor (Thm. 2) hold for every predictor, not only for the analyzed classes.

Changes in the revision.

  • Abstract: "yield sharp architectural lessons:" →\to "yield sharp architectural lessons within the analyzed classes:"
  • Abstract (and likewise the introduction, with a matching new sentence in the conclusion): "show that these architectural insights extend beyond our analytically tractable classes" →\to "show that the predicted trade-offs also emerge beyond our analytically tractable classes"
  • Introduction, new sentence directly after the three lessons: "Each lesson rests on lower bounds and constructions proved for the analyzed architecture classes of §2.1."
  • §2.1, new first sentence of "Practical counterparts": "Our main-text experiments go beyond our analyzed classes to test whether the trade-offs our theory predicts carry over to practical models, while App. D.3 validates our results directly within these classes."
  • §4.1, "Practical validation": "App. D.2 confirms these architectural lessons for the practical models" →\to "App. D.2 shows that the same trade-offs emerge in the practical models"
AuthorsOpenReview ↗

Response to Reviewer LCKz (2/3)

(Q1) Scope of the content-addressing separation. As the reviewer notes, practical Mamba-2 goes beyond the class of Thm. 3(c): the mechanisms outside its assumptions are selectivity beyond the first layer, nonlinear writes, and nonlinear reads. Since our proof does not directly extend to these mechanisms (App. F.3.3, "Scope of the selective-SSM bound"), we complement our theory with targeted ablations that test them (App. D.1.4, Fig. 7). Our theory and both ablations point to the interpretation our paper gives: the mechanism behind the separation is sharp selection (§4.2, App. D.1.4), and transition selectivity is one route to it.

Our floors (Thm. 3(a)–(b)) identify sharp selection as necessary. The SSM construction of Prop. 4 shows that selective transitions are one way to achieve it. Our ablations show that nonlinear writes also achieve it, as in the Fixed-transitions variant the reviewer notes, but nonlinear reads alone do not. Ablated Mamba-2, which has the fixed transitions and bilinear writes of our classes but keeps nonlinear reads, stays near baseline in every tested configuration (Figs. 5 and 7). Full Mamba-2 has both routes, yet its smallest successful width still grows rapidly with the codebook size, while the Transformer's stays small (Fig. 6). As in our answer to W1, this suggests that the width separation, our theory's central prediction for content addressing, remains consequential in practice.

Changes in the revision. Section 2.1 now explicitly states that Mamba-2's transitions are selective "in every layer", and the existing "Scope of the selective-SSM bound" paragraph in App. F.3.3 now explicitly names nonlinear writes and reads.

AuthorsOpenReview ↗

Response to Reviewer LCKz (3/3)

(W2, Q2) Width separation and horizon condition. We thank the reviewer for this important catch: our original wording could indeed suggest that the width separation depends on the horizon condition R=o(Tρ)R=o(\sqrt{T_\rho}), but it does not. The revision now makes this explicit: the condition only lets attention's construction reuse its Case 1 optimal window.

The SSM's addressing-capacity bound holds at every prediction time, with no coupling between RR and TT (Thm. 3(c); App. F.3.4, Eq. (97)), and attention addresses content with O(log⁡R)O(\log R) width whenever its window is long enough (L≥2RL\geq2R) to reach each key's previous occurrence (App. F.3.5, Eq. (102)). The condition's sole purpose is to make the Case 1 optimal window L⋆(Tρ)=Θ(Tρ)L^\star(T_\rho)=\Theta(\sqrt{T_\rho}), which Prop. 4 reuses for belief maintenance, satisfy L≥2RL\geq2R (App. F.3.5, after Eq. (105)). Our width-scaling experiment (Fig. 6) meets this requirement directly, with L=256≥2RL=256\geq2R at every tested codebook size. Hence, its sweep over the codebook size measures the width needed for content addressing without relying on the horizon condition.

Changes in the revision. Section 4.2 ("Architectural lessons") now explicitly states that the width separation does not depend on the horizon condition and what the condition provides, App. F.3.4 and F.3.5 now state that the proofs use the condition only for attention's window, and the width-scaling experiment setup in App. D.1.4 now states that L=256≥2RL=256\geq2R provides the required reach at every tested codebook size.

(W2, Q3) Optimization versus capacity. We agree that representational limits must be distinguished from optimization difficulties, and this is precisely why our training is architecture-specific: a single shared protocol would favor whichever architecture it happens to suit, so failures could be due to the training protocol rather than to capacity. The different alignment durations and freezing strategies that the reviewer notes come from our pilot experiments: the Transformer trained best with short alignment followed by joint training, and Mamba-2 with longer alignment whose layers then stay frozen (App. D.1.4). Likewise, we select the best validation-performing run from each search, since an average over runs would let optimization failures mask what an architecture can represent. Its reported score comes from independent test episodes, so the selection cannot inflate it. A success then demonstrates a capability, and a failure despite these measures is stronger evidence of a representational limit (App. D.1.2, "Capability focus and training aids").

While further optimization could lower individual widths of both models in Fig. 6, we do not expect it to substantially alter the trend, since we have devoted extensive effort to minimizing optimization difficulties. Beyond the architecture-specific protocols, we search at least 24 combinations of random seed and learning rate for every configuration of both families. Following our pilots, we search more learning rates for the Transformer and more seeds for Mamba-2, whose training was more seed-sensitive. Only Mamba-2 cells receive larger searches, which, if anything, lower Mamba-2's widths and narrow the gap we report. App. D.1.4 ("Optimization effects") also examines where optimization, rather than capacity, affects individual results.

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

This paper extends the canonical In-Context Linear Regression (ICLR) task to include a routing map from sequence positions to regressors. It then uses this setting to study the resulting optimal regret achievable by a one- or two-layer Transformer vs. one- or two-layer State-Space Models (SSMs). The authors then use these results to try to characterize regimes in which SSMs might outperform Transformers, and vice versa. This paper provides rigorous results that allow a theoretical comparison between these two families.

Critical strengths
  1. The authors derive rigorous bounds on the different variations of their task. This allows them to find results that hold for all versions of the SSM and Transformer architectures, subject to the restrictions of the theorems. This makes it possible to characterize a fundamental difference between the two architecture families, rather than a comparison that may depend on the specific architecture implemented.

  2. The authors use a single setting to probe different regimes of the SSM vs. Transformer comparison. This allows them to prove theorems about the effect of non-linearity in attention (Thm 3 and Prop 4), the effect of convolutional lag vs. context window size (Corr 1 and Prop 2), and the role of discounting evidence in SSMs in Prop 1.

Critical weaknesses
  1. The paper could be made significantly more useful to the community if the authors provide a clear, unifying takeaway. Case 1 identifies a regret advantage, Case 2a a memory advantage, Case 2b identifies a non-linearity advantage within transformers and a memory advantage for SSMs. The authors could help the community to understand the significance of these theorems by either using their work to suggest practically relevant regimes where one architecture would outperform the other, or unifying the comparison presented here across different families of attention and SSM models.

  2. It is difficult to verify the correctness of the theorems and propositions proved here. The presented results in Figs 4,5 do not directly test the comparison proved in Props 2-4, Thms 2-3. The architectural assumptions of the theorems and the implementation shown in the main text are different and the theory bounds are not shown to be satisfied. This makes it difficult to verify the results without reviewing the details of each proof. Appendix D.3 is helpful, and I would suggest including an explicit comparison of the architecture and bound for each claim, and link to it in the main text.

  3. Some minor notational suggestions: a. The authors could adopt the standard transformer notation of Elhage et al. 2021 in the main text. b. The authors could also reference where the propositions and theorems in their main text are proved in the appendix.

Questions for authors
  1. Could the authors clarify the connection to RoPE attention? In Sec 2.1 it appears that the paper uses Additive Relative Positional Embeddings (ARPE), rather than RoPE which is conventionally added as a rotation to QK matrices. Why are ARPE results taken to be indicative of RoPE results? Could the authors provide a comparison between ARPE results and RoPE results?

  2. Are the authors able to unify their results to identify regimes of the routing process under which SSMs outperform Transformers (or vice versa) under matched compute FLOPs?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 9Vvz (1/2)

We thank the reviewer for highlighting that our rigorous bounds characterize a fundamental difference between the two architecture families. Following the reviewer's suggestions, we have added a unifying takeaway and pointers to proofs and experiments, which have made the paper clearer. We address each point below.

(W1) Unifying takeaway. The reviewer's suggestion motivated us to state our three architectural lessons even more succinctly, as one unifying takeaway, which, as the reviewer anticipated, makes the paper more useful to the community. The takeaway is that a task favors SSMs or attention depending on when it reveals what part of history matters. When time or position fixes this in advance (Cases 1 and 2.a), SSMs prevail by compressing history into a recurrent state as it arrives. When content reveals it only at prediction time (Case 2.b), a recurrent state must preserve every candidate, so softmax attention prevails by selecting among retained past tokens.

This principle also identifies practically relevant regimes, as the reviewer suggests: SSMs for long-horizon aggregation and fixed-lag structure, and softmax attention for retrieval by content among many candidates. This divide also shows up in practice: in language modeling, Arora et al. (2023) trace most of the gap between attention and gated-convolution models to the recall of earlier context (App. A), precisely the regime in which our results give attention its exponential width advantage (Thm. 3(c) and Prop. 4). We hope the community will use belief-geometry tools to analyze and guide the design of richer architectures, including hybrids.

Our analysis also delivers the reviewer's second suggestion, a comparison that covers different families of attention and SSM models: we built our classes to span many families on both sides, at any depth and with multiple heads. The attention class covers softmax and linear attention with full or sliding-window context, and the SSM class covers the transition mechanisms of S4, RetNet, Mamba, Mamba-2, GLA, DeltaNet, Gated DeltaNet, and RWKV-7 (§2.1, App. C.1). Our content-addressing lower bounds, for instance, hold across all these transition mechanisms.

Changes in the revision. New text in the introduction, after the three lessons, and in the conclusion, after its first sentence.

(W2) Connecting theorems and experiments. We agree that the submitted version made the connection between our theorems and experiments hard to follow, and the reviewer's suggestions helped us fix this. We do test our theorems in their exact setting (App. D.3), and the revision now makes this connection explicit, along with the link from each main-text result to its proof.

We have two complementary types of experiments: App. D.3, which the reviewer finds helpful, tests exactly the analyzed architecture classes and tasks of our theorems, and thus directly checks the comparison and bounds the reviewer mentions. Our main-text experiments, including Figs. 4–5, and their Beta–Bernoulli counterparts in App. D.2 test whether the same mechanisms govern practical LLaMA-type Transformers and Mamba-2 on richer tasks.

Following the reviewer's suggestion, our summary of theoretical results (Table 1 in the appendix) now lists the architecture and bound for each claim together with the experiments that test it. The introduction points to this table, but we would be glad to move it into the main text if the reviewer prefers. In addition, each experiment in App. D.3.2–D.3.3 now explicitly names the result it tests, and the main-text Case 2.b experiments point to App. D.3.3, where we validate Thm. 3 and Prop. 4 directly. To make the proofs easier to verify, the "Guide to the proofs" diagram at the start of the appendix maps every proof and its dependencies. Each main-text result now also points to the appendix section that proves it (W3b).

Changes in the revision. Table 1 now has an "Experiments" row for each case, and each experiment in App. D.3.2–D.3.3 names the result it tests. The Case 2.b "Practical validation" paragraph (§4.2) now points to App. D.3.3, as §3 and §4.1 already do for App. D.3.1 and D.3.2.

AuthorsOpenReview ↗

Response to Reviewer 9Vvz (2/2)

(W3a) Notation. Our main-text notation for attention (§2.1) adopts the core of Elhage et al. (2021): per-head WQW_Q, WKW_K, WVW_V, WOW_O projections of the same shapes, writing into a residual stream. It departs only in a few symbols, deliberately. The residual stream is ete_t because xx denotes regressors. Elhage et al.'s dimension names, such as dmodeld_{\mathrm{model}} and dheadd_{\mathrm{head}}, are tailored to transformers, while our comparison needs symbols that serve both families. Our short symbols DD, HH, dd, and ded_e (depth, head count, per-head width, and residual-stream width) denote the same quantities in attention and SSMs, so that their resources are directly comparable. For instance, dd is both attention's query/key/value width and an SSM head's recurrent-state width, a match that a separate dstated_{\mathrm{state}} would hide. Short symbols also keep expressions compact, such as the class Fatt(D,d,H,L)\mathcal F_{\mathrm{att}}(D,d,H,L) and the per-layer width HdHd. We hope these reasons explain our choice, and we would welcome any specific change the reviewer feels would further improve clarity.

(W3b) Pointers to proofs. Following the reviewer's suggestion, each theorem, proposition, and corollary in the main text now references the appendix section where it is proved, complementing the "Guide to the proofs" diagram at the start of the appendix.

(Q1) ARPE and RoPE. The reviewer is correct that our analyzed classes use ARPE (§2.1), while our practical experiments use RoPE, following the LLaMA architecture (Touvron et al., 2023). We chose ARPE as the analyzable counterpart of RoPE because it keeps the core of RoPE: both make attention scores depend on the relative position between tokens rather than on their absolute positions. RoPE does this through rotations of the query and key features, and ARPE through an additive lag-dependent bias. ARPE's additive form keeps this dependence analytically tractable (App. C.1).

Our experiments cover both encodings and provide the comparison the reviewer asks for. With either encoding, attention shows the same behavior that Cor. 1 and Prop. 2 predict for Case 2.a, the case where positional encoding is central: one-layer attention fails at every context length, and two-layer attention improves only once its first layer can span the lag. We observe this experimentally with ARPE in the analyzed classes and tasks (App. D.3.2, Fig. 13), and with RoPE in LLaMA-type Transformers, on both the main-text task (§4.1, Fig. 4) and a Beta–Bernoulli bandit (App. D.2, Fig. 8). This indicates that ARPE captures the essence of RoPE for our results, so our theory remains consequential for practical RoPE models.

(Q2) Comparison under matched compute. Our results already provide an answer to this question for positional routing (Case 2.a), where SSMs have a compute advantage. Fixed-depth softmax attention needs a context of length L=Ω(Tρ)L=\Omega(\sqrt{T_\rho}) to reach the optimal regret rate (Prop. 3), so each token attends over Ω(Tρ)\Omega(\sqrt{T_\rho}) past positions and its per-token compute grows with the horizon. By contrast, the SSM attains this rate with horizon-independent per-token compute (Prop. 2).

A full matched-FLOP comparison across routing regimes additionally requires a model of computational cost, which is delicate to specify because the comparison hinges on at least three implementation choices. First, an SSM whose transitions are linear in the state can run as a sequential recurrence or as a parallel scan (Cirone et al., 2024), trading extra FLOPs for parallel speed. Second, during inference, attention can recompute the keys and values of its context window for every new token or cache them, trading FLOPs against memory. Third, matrix multiplications can run in full or reduced precision, which leaves the FLOP count unchanged but trades numerical accuracy for speed.

That said, once a cost model fixes these choices, belief geometry provides a framework for comparing the regret each configuration can attain within a common budget. Our positional-routing result above already does this with the simplest such model, per-token compute.

Thanks, the new Table 1 with the experiment for each result is really helpful, I was having a hard time figuring out what tested what before. I'm still a bit unsure about the unifying takeaway, and will be keeping at 3.

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

This paper proposed belief geometry, a framework for comparing attention and SSMs on three generalized in-context linear regression settings. The paper defined three capabilities required: evidence assembly, belief maintenance and addressing. The paper found SSMs excel at belief maintenance and positional assembly, while attention edges on content addressing.

Critical strengths
  1. The paper addresses one important question: what can softmax/linear attention do that SSMs can’t, and vice versa. The paper also gives a clear conclusion to the question which can facilitate the structural design of hybrid models.
  2. The experiment designed successfully isolate three capabilities required for in-context learning with a well-motivated evaluation metric.
Critical weaknesses
  1. Case 1 only applies to one layer linear attention and fixed-transition SSMs.
  2. The conclusion for this paper encourages analysis for hybrid models: does combining attention and SSM layers combine both the advantages and achieve the best results? The paper should analyze this.
Questions for authors
  1. Is it possible to incorporate real benchmarks to strengthen the findings?
  2. It seems like a missed opportunity to not test hybrid models in your setting, for example a SSM layer followed by an attention layer.
3 comments

We thank the reviewer for recognizing that our paper answers an important question with a clear conclusion that can facilitate the design of hybrid models. We address each point in turn below.

(W1) Case 1 beyond the simplest classes. This is a valuable point, and it allows us to clarify how far our Case 1 results reach. Beyond one-layer linear attention and fixed-transition SSMs, our paper also proves sharp regret rates for richer architectural classes in Case 1 (App. E.2, Props. 6–7): adding normalization gives both families Θ(log⁡T)\Theta(\log T) regret, and adding a second layer reduces it to Θ(1)\Theta(1). In the main text, we deliberately start with the simplest classes of both families to isolate their core belief-maintenance mechanisms: window averaging versus recurrent discounting. We then demonstrate in Fig. 2 why this core comparison, although simple, remains consequential: experiments with LLaMA-type Transformers and Mamba-2 show that the kernel preferences of one-layer models emerge as inductive biases in richer practical models.

(W2, Q2) Hybrid architectures. We agree that hybrids are a promising direction, and this paper lays the foundation for analyzing them by introducing the framework of belief geometry, developing its tools, and using them to compare attention and SSMs, the two families that hybrids combine. As the reviewer notes, our results already suggest how a hybrid can combine both advantages: SSM layers for belief maintenance and positional assembly, and softmax-attention layers for content addressing. Indeed, adding attention to recurrent models improves retrieval in hybrids such as Griffin (De et al., 2024) and Jamba (Lieber et al., 2024), both discussed in our related work (App. A).

A full analysis of hybrids, however, deserves its own follow-up work rather than a cursory treatment in this paper. It requires new function classes that specify how layers of the two families are composed, new lower bounds for these mixed classes, and constructions that assign each capability to the layers best suited to it. We see this analysis as important future work, together with systematic empirical tests of hybrids such as the SSM-then-attention design the reviewer suggests.

This paper gives this follow-up work a principled starting point in both theory and experiments. Belief geometry's regret decomposition (Eq. 2) and two-factor floor (Thm. 2) hold for every predictor, so the same tools apply to any hybrid and can address whether it combines the advantages of both families. More broadly, they apply to any architecture, including fundamentally new designs that go beyond mixing layers of the two families. Our experimental setups are also well suited to testing hybrids, and the new theory can guide which designs to test and what each should achieve, just as our theory guides the experiments in this paper.

Changes in the revision. The conclusion now names hybrid architectures among the settings where we expect belief geometry to aid analysis.

(Q1) Real benchmarks. Independent evidence from real benchmarks supports the relevance of our targeted experiments: Arora et al. (2023) trace most of the language-modeling gap between attention and gated-convolution models to the recall of earlier context (App. A), which is precisely the content-addressing operation in which our results give attention its exponential width advantage (Thm. 3(c) and Prop. 4). Our theory first predicts how each mechanism separates the two families, and testing these predictions properly requires experiments that isolate one mechanism at a time. As the reviewer notes, our experiments are designed to do exactly this, in LLaMA-type Transformers and Mamba-2. If the reviewer has a particular benchmark in mind for a targeted test, we would welcome the suggestion.

Thank you for your response. The reviewer understand that adding experiments on hybrid models are beyond the scope of rebuttal period. However, without such analysis the paper feels incomplete. The reviewer therefore would like to keep the score of 3.

We thank the reviewer for the follow-up and for their constructive review.

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

When feedback arrives late, a model has to work out which past input produced it before updating its estimate. The authors use Bayesian linear regression to separate this matching step from estimating the parameter and retrieving the input needed for the next prediction. They derive regret bounds for attention and state-space models, then study how the predicted differences show up in Transformers and Mamba-2.

Critical strengths
  1. On the task without delay, the optimal stationary kernel gives both architectures a common point of comparison. One sufficiently wide recurrent layer attains the optimal leading regret constant by setting a decay rate for each eigendirection. One layer of unnormalized linear attention shares a window across directions and has a larger constant even at its optimal window length.
  2. The keyed-retrieval lower bound counts real-valued state coordinates, so it still holds at unlimited precision. At fixed regression dimension and with R=o(n)R=o(\sqrt{n}) keys, the two-layer recurrent class with selective transitions only in its first layer needs Ω(R/log⁡R)\Omega(R/\log R) coordinates for sublinear regret. The construction uses O(R)O(R) to reach O(n)O(\sqrt{n}) regret. Softmax attention reaches that rate with logarithmic head width by retaining a growing window of past tokens.
Critical weaknesses
  1. The bandit used for the width comparison leaves out one of the two lookups. The model still has to match an arriving reward to a past arm, but the arm whose reward it must predict is already visible. In the theorem, the next key determines which past input the prediction concerns. The resulting width comparison tells us more about matching feedback than about retrieving the input for a prediction.
  2. The width sweep gives Mamba-2 more storage per head without giving it more independent gates. From 32 keys onward, every configuration has 16 heads per layer. Coordinates within a head share a transition gate, whereas the theoretical construction can reset individual key slots. The reported width requirement may therefore depend on how the state is divided among heads.
Questions for authors
  1. Can the practical models switch their prediction when only the next key changes? At one codebook size, train both models to predict the reward due from the arm and context seen at the key’s previous occurrence. For a fixed test history, choose two possible next keys with different Bayes reward probabilities. Compare each model’s change in predicted probability with the Bayes difference.
  2. At 32 keys, does the allocation of state across heads affect reward prediction? Take one Mamba-2 configuration near the reported threshold. Keep the expanded width and total recurrent state size fixed, halve the head dimension and double the head count. How do the two configurations compare on the same reward-prediction task?
1 comment

We thank the reviewer for the careful review and for highlighting that our keyed-retrieval lower bound holds even at unlimited precision. We ran both requested experiments, which are valuable additions to the revised paper, and report their results below.

(W1, Q1) Switching the next key. In the suggested key-switch experiment, both models can switch their prediction accordingly when only the next key changes, and the width separation becomes even larger, consistent with Thm. 3 and Prop. 4.

We also want to highlight what our existing experiments show about the two lookups. The lookup our main-text experiment targets, matching feedback, itself requires sharp selection: linear attention and Ablated Mamba-2 fail in every tested configuration (Fig. 5). The theorem's full setting, with both lookups, is already validated with the analyzed classes in App. D.3.3 (Fig. 14), matching Thm. 3 and Prop. 4: softmax attention succeeds at small widths, whereas the SSM needs both selective transitions and large width. The new experiment further strengthens this evidence.

For this experiment, we set R=32R=32 and include the next key in each token, so each prediction additionally requires retrieving the arm and context seen at that key's previous occurrence. After training both models on this task (eight training seeds per width, selecting the one that scores best on validation, as in Fig. 6), we took 2,048 fixed test histories and changed only the next key. The table compares each model's change in predicted probability with the Bayes difference:

ModelWidth (HdHd)Test scoreSame direction as BayesMean change (Bayes: 0.91)
Transformer120.0050%0.00
160.96100%0.85
240.97100%0.86
320.97100%0.87
Mamba-21,0240.0761%0.07
2,0480.1874%0.16
4,0960.6699.9%0.68
8,1920.8799.9%0.80

Both models learn to switch their prediction as the Bayes predictor does, but at very different widths. Compared with Fig. 6, the Transformer's smallest successful width grows only from 12 to 16, whereas Mamba-2's grows eightfold, from 1,024 to 8,192. Both widths are robust across seeds: seven of eight seeds succeed at each, and none at a smaller width. Retrieving the input for a prediction therefore widens the separation further, in line with Thm. 3 and Prop. 4.

Changes in the revision. App. D.1.4 now reports this experiment ("Switching the next key").

(W2, Q2) Allocation of state across heads. We also ran the suggested comparison, doubling Mamba-2's head count at fixed recurrent state. Its smallest successful width is unchanged, so the width requirement does not depend on how the state is divided among heads.

This agrees with our theory. As the reviewer notes, the SSM construction of Prop. 4 gates each key slot independently, unlike Mamba-2. But independent gates do not remove the width requirement: the selective SSM class covered by our lower bound (Thm. 3(c)) allows any of four different selective transitions in its first layer, including a separate gate for every recurrent-state coordinate (§2.1), and sublinear regret still requires Ω~(R)\widetilde\Omega(R) recurrent-state dimensions.

For the requested comparison, we set R=32R=32 and tested the two sizes on either side of the reported threshold: 512 and 1,024 recurrent-state coordinates per layer. Keeping everything else fixed, we doubled the head count and halved the head dimension (16×8→32×416\times8\to32\times4). At both sizes, the two allocations reach very similar test scores, and the threshold is unchanged: 512 still falls below 0.8, and 1,024 still exceeds it.

Heads ×\times head dimension512 coordinates1,024 coordinates
16×816\times8 (original)0.6910.889
32×432\times40.7090.870

The reported width requirement is therefore robust to how the state is divided among heads.

Changes in the revision. App. D.1.4 now reports this comparison ("Allocation of recurrent state across heads").

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of revisions

We thank the reviewers for their thoughtful feedback and suggestions, which have made the paper both stronger and clearer. We are particularly glad to see the reviewers agree that belief geometry provides a unified framework for comparing attention and SSMs, and they highlight the paper's rigorous lower bounds, matching constructions, and targeted experiments. Our individual responses address every point raised, and the revised PDF marks all changes in blue:

  • New experiments (Reviewer 5iSL). App. D.1.4 now reports two new experiments. Switching the next key: we let the next key determine each prediction and switch that key to test whether both models' predictions follow it. They do, and the width separation grows (smallest successful width at R=32R=32 versus Fig. 6: Transformer 12→1612\to16, Mamba-2 1,024→8,1921{,}024\to8{,}192). Allocation of state across heads: we double Mamba-2's head count at fixed recurrent state to test whether its width requirement depends on how the state is divided among heads. It does not: the smallest successful width is unchanged.
  • Unifying takeaway (Reviewer 9Vvz). The introduction and conclusion now state the unifying principle behind all three cases: a task favors SSMs or attention depending on when it reveals what part of history matters. When time or position fixes this in advance (Cases 1 and 2.a), SSMs prevail by compressing history into a recurrent state as it arrives. When content reveals it only at prediction time (Case 2.b), softmax attention prevails by selecting among retained past tokens.
  • Theoretical scope and Case 2.b horizon condition (Reviewer LCKz). The revision now consistently distinguishes between results proved for the analyzed classes and evidence in practical models, from the abstract to the conclusion (changes listed in our response to Reviewer LCKz). Section 4.2 now also makes explicit that the Case 2.b width separation does not depend on the horizon condition R=o(Tρ)R=o(\sqrt{T_\rho}).
  • Pointers to proofs and experiments (Reviewer 9Vvz). Table 1 now also lists the experiments that test each claim, and each experiment in App. D.3.2–D.3.3 names the result it tests. In the main text, each result now points to its proof, and the Case 2.b experiments also point to App. D.3.3, where we validate Thm. 3 and Prop. 4 directly.

The authors have posted their responses to the reviews. Could I please encourage the reviewers to read these responses and reply to the authors (if they have not already done so as with one reviewer).

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.