acceptodds
Under review as a conference paper at ICLR 2027

Beyond Laplace: How Mamba In-Context Learns Constrained Switching Markov Chains — Estimation Gaps Close, Statistical Limits Do Not

Abstract

Recent work showed that Mamba exactly represents, and learns in training, the Laplacian smoothing estimator for unconstrained Markov chains. We study switching Markov chains whose transition kernels share one stationary distribution and whose switches are hidden from the predictor. This setting poses two distinct problems, estimating the constrained kernel and identifying the kernel currently in effect. For estimation, the stationarity constraint couples the kernel rows in the posterior, so Laplacian smoothing is strictly suboptimal for any number of states. We show that the difference between the constrained Bayes predictor and Laplacian smoothing lies in the readout rather than in the state. Readouts that use only the current row's counts cannot reach this predictor, whereas a log-linear softmax readout on the same count state represents it exactly for two states, with a width that grows linearly in the sequence length and a lower bound of the same order. Probes show that trained Mamba stores the transition counts linearly in its hidden state and combines counts across rows at the readout, closing most of the estimation gap. For identification, even the optimal filter with infinite memory incurs a strictly positive residual loss for any number of states and any order, and a Wald-type lower bound shows that switches cannot be detected instantly. Trained Mamba and Transformer models approach this statistical limit but do not exceed it. Provable unpredictability against well-trained sequence models must therefore rest on the statistical limit created by hidden switching rather than on the difficulty of estimation.

Primary area:
learning theory
Keywords:
in-context learning, Mamba, switching Markov chains, stationarity constraint, Bayesian prediction, hidden Markov models, sequential detection

Reviews

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

The paper studies Markov chains whose transition kernels share one stationary distribution and switch hidden among a finite set of such kernels. It splits the problem into estimating the constrained kernel and identifying the active one. It shows that Laplacian smoothing is strictly suboptimal under the constraint, gives a closed form of the constrained Bayes predictor for two states, and shows that the difference lies in the readout rather than the count state. It reports that trained Mamba models close most of the estimation gap, and that the optimal filter keeps a strictly positive residual loss that trained models approach but do not beat. It concludes that provable unpredictability against trained sequence models must rest on hidden switching rather than on estimation difficulty.

Critical strengths
  1. Clean, correct theory. The two-state closed form and the strict suboptimality for any number of states are correct, and the constructive Gauss–Jacobi readout and its width lower bound are consistent with each other.
  2. Careful probe design. The three-state probe fixes sequence length and current-row counts, and the state-patching test has untrained-model and orthogonal-direction controls whose weaker results are reported.
  3. Candid limitations. Conjectures are labeled, the exact-representation result is proved only for two states, and the appendix points out that the two-state experiments cannot separate a cross-row readout from a within-row readout with position.
Critical weaknesses

W1. The design implication ignores an i.i.d. baseline. The kernel whose rows all equal π∗\pi^{\ast} belongs to C(π∗)C(\pi^{\ast}), and every predictor has expected log loss at least H(π∗)H(\pi^{\ast}) on it. Under any stationary process, predicting π∗\pi^{\ast} while ignoring history already achieves H(π∗)H(\pi^{\ast}), so the optimal filter under hidden switching has loss L∗≤H(π∗)L^{\ast} \le H(\pi^{\ast}). With the E3 parameters (r=0.6r=0.6) I get H(π∗)=0.662H(\pi^{\ast})=0.662 nats against L∗=0.556L^{\ast}=0.556–0.5750.575 (my own simulation). Within the paper's model, an i.i.d. kernel is therefore at least as hard to predict as any hidden-switching scheme, and the claim that provable unpredictability "must rest on" hidden switching does not follow. The graph-topology constraint in App. C.7 might change this, but it enters no theorem, and (A2) and Proposition 2 exclude sparse supports. The authors should report H(π∗)H(\pi^{\ast}) as a reference and either model the constraint that rules out i.i.d. kernels or present the defense angle only as motivation.

W2. The residual loss does not isolate identification. The oracle knows Zt+1Z_{t+1}, so HwithinH_{\text{within}} already includes whether a switch occurs at the next step. The proof of Theorem 7 only uses that the predicted belief has full support, which also holds for a predictor that knows ZtZ_t exactly, so ρ<1\rho<1 alone does not show a limit on identification. In my simulation of the E3 setting (two kernels, p∈{0.15,0.6}p\in\{0.15,0.6\}, r=0.6r=0.6), the optimal filter has ρ=0.33/0.20/0.11/0.08\rho = 0.33/0.20/0.11/0.08 at pswitch=0.05/0.1/0.15/0.2p_{\text{switch}}=0.05/0.1/0.15/0.2, in line with Figs. 5–6, while a predictor that knows ZtZ_t has ρ=0.80/0.64/0.46/0.35\rho=0.80/0.64/0.46/0.35. Roughly 30% to 70% of the residual loss thus comes from switch-time unpredictability rather than detection delay. The remark after Theorem 7 mentions both sources, but the abstract and Sec. 2.2 call the residual an identification limit. A known-ZtZ_t benchmark would let the paper split the residual and place the trained models.

W3. The estimation and identification halves are studied in different settings. The switching analysis of the estimation gap (Theorem 3, Sec. 3.3) assumes the counts restart at each switch, which App. C.6 describes as "known switching times", whereas hidden switching is the premise of the paper. The identification half (Sec. 5, E3) assumes PP and AA are known, so the trained models need the strategy kernels in their weights if the strategy set is fixed across sequences, and E3 then contains no estimation problem. No theorem or experiment covers unknown constrained kernels with hidden switches, yet the abstract and conclusion merge the two halves. The paper should state what is resampled per sequence in E3, that Theorem 3 applies to visible switches, and either add a joint experiment or split the conclusion.

W4. The evidence for "closing the estimation gap" and a cross-row readout is mostly at two states. At n=2n=2 the gap is 0.0125 nats (0.5273 for add-β vs. about 0.5148 for f∗f^{\ast}, Fig. 3(a)), 2.4% of the loss. The upper bound for readouts that use the current row's counts plus position is about 98% (Fig. 4(a)), above every trained model, and App. C.3 itself says the closed fraction cannot tell the two readouts apart. For n≥3n\ge3, App. C.5 reports that trained models at d=16d=16 are worse than add-β and that n=5n=5 is only slightly above zero at d=32d=32. The cross-row probes use one model family (full Mamba, d=32d=32, one length-12 family, five seeds; patching slope 0.86 with 95% interval 0.64–1.08, and orthogonal perturbations have effects of similar size). The paper should report, for n=3,4n=3,4, the trained models' loss relative to the best within-row-plus-position predictor and to f∗f^{\ast} with seed intervals, include Gated M-2 in the probes, and scope the abstract to the settings tested.

Questions for authors
  1. Were the four architectures given comparable tuning? They use different optimizers, learning rates and widths under one 8000-step budget, and the Transformer is still improving at the end of training (Fig. 3(b)), so it is unclear whether the differences between them (e.g., 95% vs. 40% closed) reflect architecture or training.
  2. The appendix numbering is inconsistent (Theorem B.1 appears as Theorem B.2 in later references, and Corollary B.2 is used twice). Which statements are intended by each label?
  3. Should the Limitations paragraph state that the switching analysis assumes known PP and AA and, for the estimation gap, visible switches?
11 comments
AuthorsOpenReview ↗

Response to Reviewer ocx3 (1/4)

A1.1 (response to Q1, part 1)

Thank you for raising this question. The four architectures were not given comparable tuning in the initial submission, and a considerable part of the difference between 95% and 40% came from training. In the revised version, we have retrained the four architectures under a unified training protocol (new Appendix C.7 and Figure C.10). The results show that the lower closed fractions of full Mamba and the Transformer in the initial submission came mainly from the training settings, whereas the shortfall of the MambaZero variant comes from its architecture.

Original training settings of E2 in the initial submission. In the initial submission, E2 used a separate setting for each architecture (Appendix D.2). The MambaZero variant and Gated M-2 used d=8d = 8 and Adam with a constant learning rate. Full Mamba used d=8d = 8 and the Transformer used d=16d = 16, and both used AdamW with learning rate 10−310^{-3} and cosine decay. All four architectures were trained for only 8000 steps, and their learning rates were not selected on a common grid.

Unified training protocol added in the revised version. The four architectures use the same optimizer and learning-rate schedule, namely AdamW with a cosine schedule decaying to 0, and batch size 64. The learning rate is selected from a common grid by the mean validation loss over 10 seeds on a separate validation set, and further values outside the grid are tried when the selected value lies at an endpoint. The training budgets are 8000, 16000, 32000, 64000 and 128000 steps, and each budget is trained from scratch with 10 seeds. The widths are matched in two ways. In the equal-width group all four architectures use d=16d = 16, and in the equal-parameter group the parameter counts of the architectures lie between 8266 and 8608. The evaluation set is the same as in the original E2.

Results under the unified training protocol. At the same 8000 steps, the closed fraction of the Transformer rises from 41.1% under the original setting to 75.2%, and that of full Mamba rises from 86.7% to 98.9% (equal-width group). The learning rate selected for both is then 3×10−33 \times 10^{-3}, higher than the 10−310^{-3} of the original setting. The closed fractions of Gated M-2 and full Mamba exceed 97% at every training budget. The closed fraction of the Transformer keeps rising with the number of training steps and reaches 98.6% at 128000 steps, within about 1 percentage point of Gated M-2 and full Mamba. In both groups and at every training budget, the MambaZero variant stays at 47.1% to 54.3%, between the two upper bounds for within-row readouts in Theorem 4, fF1f_{\mathcal{F}_1} (42.2%) and fF2f_{\mathcal{F}_2} (97.2%).

AuthorsOpenReview ↗

Response to Reviewer ocx3 (2/4)

A1.2 (response to Q1, part 2)

Comparison between architectures. At 128000 steps, we computed paired bootstrap intervals for the differences in closed fraction between the six pairs of architectures in each group. This gives 12 intervals over the two groups, each taken at the 99.58% level by the Bonferroni correction. The difference between Gated M-2 and full Mamba is not significant in either group. Gated M-2 is about 1.2 percentage points higher than the Transformer, and the intervals in both groups exclude zero. The difference between full Mamba and the Transformer is not significant in the equal-width group, and in the equal-parameter group the lower end of its interval is slightly above zero. The MambaZero variant is 44 to 47 percentage points below the other three architectures. Therefore, with sufficient training, Gated M-2, full Mamba and the Transformer differ by only about 1 percentage point, whereas the shortfall of the MambaZero variant does not disappear with training.

Cross-row readout. At 128000 steps, the 95% intervals of the closed fractions of Gated M-2, full Mamba and the Transformer all lie above the upper bound fF2f_{\mathcal{F}_2} for within-row readouts with position, which indicates that the readouts of these three architectures use cross-row information. Appendix C.3 of the initial submission notes that, with two states, the closed fraction cannot distinguish a cross-row readout from a within-row readout with position. The evidence that ruled out the positional explanation therefore came only from Probes 4 and 5 with three states (Section 4.1). The results under the unified training protocol add two-state evidence for this conclusion. The MambaZero variant stays between the two bounds, consistent with the capability of its normalized readout.

Effect on the conclusions. Theorems 1 to 7 and Propositions 1 and 2 concern the Bayes-optimal predictor, the representational capacity of readouts and the statistical limits. They do not involve training and are not affected by the training settings. The training settings affect only the interpretation of the differences between architectures in E2. Under the unified training protocol the Transformer also closes most of the estimation gap, which strengthens our conclusion that sufficiently trained models can close the estimation gap.

Revision. Section 3.4 has been revised to state that this difference partly comes from training and to give the results under the unified training protocol. Section 3.4 and Figure 3 still report the E2 results under the original settings. The new Appendix C.7 and Figure C.10 report all results under the unified training protocol and the comparison between architectures, and the settings of this protocol have been added to Appendix D.2. The statement on the two-state closed fraction in Appendix C.3 has been revised accordingly. These changes are shown in red in the revised version.

AuthorsOpenReview ↗

Response to Reviewer ocx3 (3/4)

A2 (response to Q2)

Thank you for your careful reading. The numbering in Appendices B.2 and A.12 of the initial submission is indeed wrong. We have thoroughly checked the whole paper and standardized the format of the appendices. In the revised version, the statements in the appendices have been renumbered by subsection, each proof is preceded by the corresponding statement, and labels, statements and proofs are in one-to-one correspondence.

Statements intended by each label in the initial submission. In the initial submission, Appendix B.2 contains one theorem and two corollaries, which are, in order, Theorem B.1, Corollary B.1 and Corollary B.2. “Theorem B.2” occurs in five places, namely the statements of Corollaries B.1 and B.2, the heading of Appendix A.12, the label of the proof of the theorem and the proof of Corollary B.2. All five refer to Theorem B.1. Appendix A.12 gives the proofs of the three statements in order. The first “Corollary B.2” in its heading refers to Corollary B.1, and the second refers to Corollary B.2. Likewise, the first proof labeled “Corollary B.2” is the proof of Corollary B.1, and the second is the proof of Corollary B.2.

Other numbering errors. While checking the labels, we also found problems in the initial submission such as Proposition B.1 being called Proposition B.6 elsewhere.

Revision. In the revised version, the statements in the appendices have been renumbered by subsection, consecutively within each subsection. For example, the three statements of Appendix B.2 have been renumbered as Theorem B.2.1, Corollary B.2.2 and Corollary B.2.3. The proofs of the results in Appendix B have been moved from Appendix A to the corresponding subsections of Appendix B. Each label in the revised appendices refers to exactly one statement, and every reference to these labels has been checked. The table below lists, for each label in the appendices of the initial submission, the corresponding label in the revised version.

Initial submissionTitleRevised version
Theorem B.1Suffix-class decompositionTheorem B.2.1
Corollary B.1Class-wise closed formCorollary B.2.2
Corollary B.2Strict suboptimality of order-kk add-β\beta for n=2n = 2Corollary B.2.3
Proposition B.1Sufficiency of cross-row readoutsProposition B.5.1
Lemma A.0.1Loss decompositionLemma A.0.1
Lemma A.0.2One-dimensional likelihood-ratio order, strict versionLemma A.0.2
Lemma A.2.1Maximum and properties of the maximizerLemma A.1.1
Corollary A.2.2Quantitative inclusionCorollary A.1.2
Lemma A.2.3Posterior concentrationLemma A.1.3
Reviewer_YramOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors study how Mamba performs in-context learning on random Markov chains whose transition matrices share a fixed stationary distribution and may switch over time without observable change points. The authors prove that the stationary constraint couples the transition probabilities across rows, making the classical predictor that is optimal in the unconstrained case (Laplacian smoothing) to be suboptimal. The authors derives the optimal Bayesian estimator in the constrained case and show how a Mamba-like architecture can represent it via recurrent transition counts and a softmax readout. The paper also analyzes hidden switching between Markov kernels, establishing an irreducible prediction loss for the optimal filter. Experiments via mechanistic probes suggest how trained Mamba models encode transition counts and exploit cross-row information to approach optimality.

Critical strengths

The paper extends Bondaschi et al. (2026) in two directions: (i) it constrains the random Markov kernels to have the same fixed stationary distribution; (ii) it allows the Markov kernel to randomly change along the sequences. I think that both directions are interesting from a theoretical point of view. The paper's results are not complex but they are elegant and well explained. The paper is generally well written. The experiments give interesting insights on how Mamba models learn to implement the proposed predictors in practice.

Critical weaknesses

In my opinion, the main limit of the paper is that it is essentially of only theoretical interest. There is no clear insight or take-away that goes beyond the toy model toward more real-world scenarios. A second limitation is that the experiments, while suggestive, do not prove that Mamba models actually learn the precise theoretical construction proposed in the paper. A third limitation is that the two directions (i) and (ii) described above are studied mostly independently, under different assumptions, -- (i) samples kernels from the whole (constrained) simplex, while (ii) focuses on a fixed number KK of known kernels, -- and their interaction is not explored.

Questions for authors

I would like to ask the authors the following clarification questions:

  1. The proof of Proposition 2 appears to assume that, after a switch, subsequent observations continue to be generated by the same kernel until detection. This is not necessarily true, as multiple switches might occur before the first one is detected. Am I correct, or did I misunderstand the proof?
  2. Theorem 5 uses a softmax-weighted average of quadrature nodes to represent the optimal constrained predictor. How does this relate to the standard Mamba architecture? That is, can the standard Mamba architecture studied experimentally implement such a construction, either exactly or approximately?
  3. The paper studies directions (i) and (ii) separately, without discussing their interaction. That is, it does not directly analyze the situation in which the predictor must simultaneously estimate the Markov kernels and the switch positions. Do you have any theoretical or experimental insight about this?
7 comments
AuthorsOpenReview ↗

Response to Reviewer Yram (1/4)

A1 (response to Q1)

Thank you for your careful reading. Your understanding is correct. The proof in Appendix A.10 of the initial submission treats all post-switch observations as generated by the post-switch strategy, that is, it assumes that no further switch occurs before detection is completed. Reviewer S9Xw raised the same question (see our response to their Q2). The conclusion of Proposition 2 does not depend on this assumption, and we have removed it in the revised version.

Only observations within the dwell interval are informative. Suppose the strategy switches from aa to bb, and let τdw\tau_{\mathrm{dw}} be the dwell length of bb. The strategy process evolves according to the switching matrix AA and does not depend on the state, so τdw\tau_{\mathrm{dw}} is independent of the state chain. Observations after the next switch are generated by another strategy kernel and cannot distinguish whether aa or bb was active in the dwell interval. Revealing the switching path outside the interval to the identification procedure can only make identification easier, so a lower bound derived in this setting also holds for the original problem. An identification procedure that is not told the switching path can do no better. When the strategy set contains only the two strategies aa and bb, the next switch can only return to aa. The subsequent observations are generated by aa, and for such a procedure they decrease, on average at every step, its accumulated log-likelihood ratio in favor of bb. Continued switching therefore does not shorten the detection delay.

The bound under continued switching. The argument of the original proof holds equally for the stopping time min⁡(τdet⁡,τdw)\min(\tau_{\det}, \tau_{\mathrm{dw}}) and gives the same lower bound as Proposition 2. Since τdet⁡≥min⁡(τdet⁡,τdw)\tau_{\det} \ge \min(\tau_{\det}, \tau_{\mathrm{dw}}), the lower bound of Proposition 2 still holds under continued switching. Since also τdw≥min⁡(τdet⁡,τdw)\tau_{\mathrm{dw}} \ge \min(\tau_{\det}, \tau_{\mathrm{dw}}), a necessary condition for identifying this switch with a given error probability is that the mean dwell length 1/(1−Abb)1/(1-A_{bb}) is no smaller than the same bound. When the mean dwell length is shorter, the next switch occurs before this one has been identified, which is exactly the situation you describe.

Relation to the main result. The proof of Theorem 7 (ρ<1\rho < 1) does not use Proposition 2. Proposition 2 only gives the time scale of the loss difference in Theorem 7, so this revision does not affect the statistical-limit result.

Revision. In the revised version, Proposition 2 has been restated under continued switching, the necessary condition on the mean dwell length has been added, and the dwell-interval argument has been added to its proof (Appendix A.10 of the initial submission, A.9 of the revised version). All modified and newly added content in the revised version is shown in red.

AuthorsOpenReview ↗

Response to Reviewer Yram (2/4)

A2 (response to Q2)

This is a very insightful comment. The standard Mamba studied in our experiments is the Full Mamba of the paper. The construction of Theorem 5 consists of a state layer and a readout layer. The standard Mamba can implement the state layer exactly. Its readout layer does not contain the readout of Theorem 5. Proposition B.5.1 of the revised version shows that a two-layer feedforward readout on the transition counts approximates f∗f^{\ast} to any accuracy.

The state layer can be implemented exactly. The state layer of Theorem 5 is the construction in Theorem 1 of Bondaschi et al. (2026). A convolution with window 2 supplies the previous symbol, and a recurrence with decay coefficient 1 accumulates the transition counts Nt\mathbf{N}_t exactly in the hidden state. The standard Mamba contains both components, and its decay coefficient can be set to 1, so it can implement this state layer exactly. Training raises the decay coefficient of the Full Mamba above 0.93, and the four transition counts can be linearly decoded from its hidden state with a coefficient of determination of at least 0.95 for t=20t=20 to t=119t=119 (Probe 2, Figure C.2).

The readout layers differ. From the hidden state to the prediction, the standard Mamba applies in turn a linear readout, output gating, a residual connection, a gated MLP, a linear layer and a softmax over the vocabulary. None of these operations takes a softmax-weighted average over quadrature nodes, so the standard Mamba cannot implement the construction of Theorem 5 exactly. Theorem 5 is a representation result for a class of readouts that share the state layer with Mamba, and the width lower bound of Theorem 6 also applies only to this readout class. The exact representation of Bondaschi et al. (2026) is similar in this respect. Their Theorem 1 concerns the simplified model MambaZero, which removes the gating and the MLP and replaces the softmax with ℓ1\ell_1 normalization.

Approximate implementation. Proposition B.5.1 of the revised version (Proposition B.1 in Appendix B.6 of the initial submission) shows that, when the hidden state linearly maintains the four transition counts, a two-layer feedforward readout can approximate f∗f^{\ast} uniformly on {0,…,T}4\lbrace 0,\ldots,T\rbrace^4 to any accuracy. In the standard Mamba this position is occupied by the gated MLP and the linear layer. The experiments are consistent with such an approximation. The Full Mamba closes about 87% of the estimation gap (Figure 4(a)), and on a held-out sequence its predictions at the positions with xt=0x_t=0 are close to f∗f^{\ast} (Figure 3(c)). In the three-state setting with the length and the current-row counts fixed, its prediction varies with the counts of the other rows in the same direction as f∗f^{\ast} (Probe 4 of the revised version, Figure 4(b)). Patching the hidden state along the encoding direction of the other-row counts reproduces this change, with a magnitude of about 0.86 times the change in f∗f^{\ast} (Probe 5 of the revised version, Figure C.4).

Role of Theorems 5 and 6. The approximation argument does not give the required readout width. For the class of softmax readouts whose logits are affine in the counts, Theorems 5 and 6 give an explicit exact construction and a width lower bound of the same order. They show that f∗f^{\ast} and add-β\beta can be read out from the same count state and differ only in the readout layer, and that the width required to represent f∗f^{\ast} exactly within this readout class is Θ(T)\Theta(T).

Revision. In the revised version, a clarification has been added to the remark after Theorem 5 (Section 4.2 and Appendix A.6), stating that the readout of the Full Mamba does not contain this weighted average and that Proposition B.5.1 gives the approximation of f∗f^{\ast} by a two-layer feedforward readout on the counts.

AuthorsOpenReview ↗

Response to Reviewer Yram (3/4)

A3.1 (response to Q3, part 1)

This is a valuable question. To answer it better, we first introduce the adversarial background of this paper.

The setting of this paper originates from the adversarial patrolling problem. The nodes of the Markov chain represent the locations to be patrolled and monitored, and the edges represent the paths between locations. The target stationary distribution π∗\pi^{\ast} specifies the long-run frequency with which each location is patrolled. It allocates patrol resources according to the importance and vulnerability of the targets, so that targets of high value that require a short time to attack receive higher patrol frequencies. The defender's patrol strategy is encoded in its transition kernel. The adversary continuously observes and records the defender's history of positions, estimates the defender's transition kernel from it, and then chooses the optimal time and location of an attack. The state sequences generated by the Markov chain in this paper correspond to the state-transition sequences of the defender's movement. Mamba predicts the defender's next position from these sequences and can therefore be regarded as a neural adversary.

Most existing studies assume that the defender uses a single transition kernel and model the adversary by statistical methods. Two works (Alvarenga et al., 2019; Wang et al., 2026a) use time-varying Markov chains, but their adversaries are still statistical methods and their conclusions rest mainly on experimental validation. This paper analyzes the capability of neural adversaries theoretically. Direction (i) corresponds to a single transition kernel, where the adversary has to estimate the unknown kernel (Sections 3 and 4).

Direction (ii) corresponds to multiple transition kernels. Here we assume that the adversary knows the strategy set P\mathcal{P} and the switching matrix AA. This is the worst-case assumption commonly made in adversarial settings, namely that the adversary fully knows the defender's strategy, as if the strategy information had been leaked. The adversary then knows every transition kernel exactly, so there is no estimation problem, and only the identification of the switching times remains. What we examine is precisely whether the adversary can identify the switching times accurately in this worst case. Even the optimal filter that knows P\mathcal{P} and AA cannot identify them accurately (Theorem 7), and trained Mamba can only approach this limit (Section 5.3). The unpredictability created by switching therefore holds even in the worst case, which is why time-varying Markov chains are worth studying. The defender can accordingly design P\mathcal{P} and AA to make the switching times harder for the adversary to identify, and thereby improve the protection provided by patrolling (Appendix E.2 of the revised version).

This paper deliberately studies the two problems separately (Section 2.2), so that each type of loss can be attributed to a single source. A more realistic situation is that the adversary knows neither P\mathcal{P} nor AA, which is exactly the situation you point out. The adversary then faces the joint problem of estimation and identification. It has to identify the switching times and estimate the transition kernels at the same time, and the two depend on each other. Estimating a transition kernel requires knowing the boundaries of the dwell intervals, while detecting a switch relies on an estimate of the current transition kernel.

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

This paper extends the line of research on how Mamba learns Laplacian smoothing in context to a new setting. Unlike conventional settings in which the rows of the transition matrix are sampled independently, the authors require the transition matrix to have a known stationary distribution, meaning that the long-run visitation frequencies of the states are fixed. The paper further investigates sequence prediction when the transition kernel switches invisibly among multiple strategies. The paper divides the problem into two parts: (1) Estimation of a fixed but unknown transition matrix. The authors prove that the stationarity constraint introduces coupling between different rows of the transition matrix in the Bayesian posterior, making independent row-wise Laplacian smoothing strictly suboptimal. They also derive the posterior and a closed-form predictor for the two-state case, analyze the asymptotic benefits arising from the reduction in parameter dimensionality, and show that the complete transition counts remain sufficient statistics. Furthermore, the paper proves that a readout relying only on the transition counts of the current row cannot achieve the constrained Bayes-optimal predictor, whereas a log-linear softmax readout using all transition counts can exactly represent the two-state optimal predictor for finite sequence lengths, with the required width growing linearly with sequence length. (2) Identification of the hidden current strategy among multiple known transition matrices. Using the HMM forward filter, the authors prove that the optimal predictor still incurs a strictly positive residual loss relative to an oracle that knows the current strategy. They also establish a Wald-type lower bound on detection delay. The validation includes numerical computations on synthetic data, training experiments with four small-scale architectures, linear decoding of transition counts, readout ablations, fixed-length behavioral probes in the three-state setting, and state patching experiments. In the main two-state estimation experiment, Gated M-2 closes approximately 95% of the estimation gap. In the switching experiments, full Mamba and Gated M-2 approach the optimal filter with known parameters. Extensions to larger state spaces, however, reveal noticeable capacity limitations.

Critical strengths

(1) A clear mechanistic connection between statistical estimation and architectural expressivity. Theorem 2 shows that the stationarity constraint introduces cross-row posterior coupling, making conventional independent row-wise smoothing suboptimal.Theorem 4 further establishes that a readout relying only on the transition counts of the current row cannot achieve the constrained Bayes-optimal predictor, highlighting the importance of utilizing cross-row information to close the estimation gap. (2) Mutual support between theoretical analysis and mechanistic experiments, with a relatively rigorous experimental design. The paper uses the constrained Bayes-optimal predictor, add-β\beta, and the optimal HMM filter as interpretable references, distinguishing the estimation gap that models can potentially close from the irreducible loss caused by hidden switching.

Critical weaknesses

(1) Certain inconsistencies between theoretical definitions and the hidden-switching analysis affect the rigor of the core conclusions. Section 2.2 defines excess risk as the loss difference relative to the Bayes-optimal predictor. However, Proposition 1 assigns a nonzero cumulative excess risk to the Bayes-optimal predictor itself, effectively mixing Bayesian excess prediction risk with coding redundancy relative to the true parameter. Similarly, the proof of Proposition 2 is based on a sequential hypothesis test in which the post-switch strategy remains fixed, and therefore does not directly extend to a continuously switching stochastic process. These issues do not necessarily invalidate the main theoretical results, but the relevant assumptions, risk baselines, and ranges of applicability need to be clarified. (2) The mechanistic interpretation and generalization claims are not yet sufficiently supported by experimental evidence. Although the theoretical results establish that the same transition-count state can achieve Bayes-optimal prediction through different readouts, this representational existence result does not imply that trained Mamba models modify only their readout mechanisms. The existing linear probes and state interventions provide fairly strong evidence that the models utilize cross-row information, but they are insufficient to fully characterize the underlying internal computations. In addition, E2 considers only a fixed but unknown transition kernel, whereas E3 assumes that the candidate transition kernels and switching matrix are known. Consequently, the paper has not directly validated the models' capabilities when unknown transition kernels and hidden switching occur simultaneously.

Questions for authors

Q1. Regarding the definition of excess risk in Proposition 1: Section 2.2 defines excess risk as the loss difference relative to the Bayes-optimal predictor, but Proposition 1 assigns a nonzero cumulative excess risk to that same predictor, while Appendix A.4 appears to use a predictor with knowledge of the true transition matrix as the reference. Could the authors clarify whether different risk definitions are being used and explicitly identify the reference predictor underlying the asymptotic results in Proposition 1? Q2. Regarding the applicability of Proposition 2: Section 2.1 allows the hidden strategy to switch continuously according to a stochastic transition matrix, whereas the proof in Appendix A.10 appears to assume that the post-switch strategy remains fixed. Does Proposition 2 implicitly assume that no additional switch occurs before detection is completed? If not, how does the detection-delay lower bound apply to situations in which another switch may occur before the previous one has been detected? Q3. Regarding count resets after switching: Does the analysis in Section 3.3 and Appendix B.3 use the true switching times to reset transition counts? If so, please explicitly distinguish this analytical setting from the information actually available to a predictor under hidden switching, and clarify the scope of applicability of the corresponding conclusions.

5 comments
AuthorsOpenReview ↗

Response to Reviewer S9Xw (1/3)

A1 (response to Q1)

Thank you for your careful reading. You are right. Section 2.2 and Proposition 1 use the term “excess risk” for two different quantities. We have separated them in the revised version, and the conclusion of Proposition 1 on the gap is not affected.

Two quantities. The excess risk excesst(f)\mathrm{excess}_t(f) of Section 2.2 takes the Bayes-optimal predictor as the reference, and its expectation is taken jointly over the kernel drawn from the prior and the state sequence. In the single-strategy setting the Bayes-optimal predictor is f∗f^{\ast}, so excesst(f∗)=0\mathrm{excess}_t(f^{\ast})=0 by definition. The two log⁡T\log T expansions in Proposition 1(i) concern a different quantity. They hold for a fixed true kernel P∘P^\circ in the relative interior of the constraint set. With the predictor that knows P∘P^\circ as the reference, they measure the cumulative expected KL divergence between the true transition row and the prediction. Appendix A.4 of the initial submission calls this quantity the cumulative KL redundancy. The results of Clarke & Barron (1990), Csiszár & Shields (2004) and Barron et al. (1998) cited there concern exactly this quantity.

Reference predictor. The reference predictor underlying Proposition 1 is the oracle predictor of the single-strategy setting. It knows P∘P^\circ and predicts with the current row of P∘P^\circ. The initial state follows π∗\pi^{\ast}, and π∗\pi^{\ast} is stationary for P∘P^\circ. The loss of this predictor therefore equals the entropy rate of P∘P^\circ at every step.

The gap does not depend on the reference. When the KL redundancies of add-β and f∗f^{\ast} are subtracted, the loss of the oracle cancels. The difference is the log-loss difference of the two predictors under the true kernel P∘P^\circ. Averaging it over the prior gives exactly the excess risk of add-β in the sense of Section 2.2. The cumulative gap n−12log⁡T\frac{n-1}{2}\log T in Proposition 1 is therefore consistent with the definition in Section 2.2.

Scope. Proposition 1 holds for each fixed P∘P^\circ. Figure 2(d) reports prior-averaged values, and they agree numerically with the leading term.

Revision. We have defined the KL redundancy at step tt, denoted redt(f;P∘)\mathrm{red}_t(f;P^\circ), in Section 2.2 and added it to the symbol table. Proposition 1 has been restated in terms of this quantity, and its statement has been extended to name the reference predictor and the distribution under which the expectation is taken. The remark after Proposition 1, its proof (Appendix A.4 of the initial submission, A.3 of the revised version) and Appendix B.3 of the initial submission (B.4 of the revised version) have been changed to use the term KL redundancy throughout. In Theorem 3 the difference of expected excess risks equals gstructg_{\text{struct}} under both references, because the entropy terms cancel at zero counts. Its wording has also been aligned with the new definition. All modified and newly added content in the revised version is shown in red.

AuthorsOpenReview ↗

Response to Reviewer S9Xw (2/3)

A2 (response to Q2)

This is a very insightful comment. The proof in Appendix A.10 of the initial submission treats all post-switch observations as generated by strategy bb, that is, it assumes that no further switch occurs before detection is completed. We have removed this assumption in the revised version, and Proposition 2 has been restated under continued switching.

Update. This response has been updated to reflect the second revision and supersedes its earlier version. The changes to Proposition 2 in the second revision were made in response to the follow-up comment of Reviewer Yram.

Only observations within the dwell interval are informative. Let τdw\tau_{\mathrm{dw}} be the dwell length of bb. The strategy process evolves according to the switching matrix AA and does not depend on the state, and τdw\tau_{\mathrm{dw}} has mean 1/(1−Abb)1/(1-A_{bb}). Observations after the next switch are generated by another kernel. Given the last state of the interval and the switching path outside the interval, these observations have the same distribution under the hypothesis that aa is active in the interval and under the hypothesis that bb is active, so they cannot distinguish the two. Revealing the switching path outside the interval can only make identification easier, so a lower bound derived in this setting also holds for the original problem. A procedure that is not told the switching path can do no better. With two strategies, the next switch returns to the pre-switch strategy aa, and for such a procedure the subsequent observations decrease its accumulated log-likelihood ratio of bb against aa by Dˉab\bar D_{ab} per step on average (Dˉba\bar D_{ba} with aa and bb exchanged). Continued switching therefore does not shorten the detection delay.

The bound under continued switching. Let α\alpha denote the larger of the false-alarm probability and the missed-detection probability of an identification procedure. The revised proof (Appendix A.9) applies the argument of the initial submission to the stopping time min⁡(τdet⁡,τdw)\min(\tau_{\det}, \tau_{\mathrm{dw}}). For every identification procedure with α<1/2\alpha < 1/2, it gives

(1−2α)log⁡1−αα−(max⁡ih(i)−min⁡ih(i))≤DˉbaEb[min⁡(τdet⁡,τdw)]≤Dˉba1−Abb,(1-2\alpha)\log\frac{1-\alpha}{\alpha} - \Big(\max_i h(i) - \min_i h(i)\Big) \le \bar D_{ba} \mathbb{E}_b\left[\min(\tau_{\det}, \tau_{\mathrm{dw}})\right] \le \frac{\bar D_{ba}}{1-A_{bb}},

where Eb\mathbb{E}_b is the expectation when strategy bb is in effect during the dwell interval and hh is the solution of a Poisson equation determined by P(a)P^{(a)} and P(b)P^{(b)}. The quantity min⁡(τdet⁡,τdw)\min(\tau_{\det}, \tau_{\mathrm{dw}}) is the number of steps from the switch to the completion of detection or the end of the dwell interval, whichever comes first, so the statement covers the case in which another switch occurs before the previous one has been detected. Since τdet⁡≥min⁡(τdet⁡,τdw)\tau_{\det} \ge \min(\tau_{\det}, \tau_{\mathrm{dw}}), the first inequality also holds for Eb[τdet⁡]\mathbb{E}_b\left[\tau_{\det}\right], so the lower bound on the detection delay holds under continued switching. The second inequality holds because min⁡(τdet⁡,τdw)≤τdw\min(\tau_{\det}, \tau_{\mathrm{dw}}) \le \tau_{\mathrm{dw}}. Together, the two inequalities show that the mean dwell length 1/(1−Abb)1/(1-A_{bb}) limits the attainable α\alpha. In addition, every identification procedure satisfies

α≥12(1−Abb)∑iπi∗∑jmin⁡{P(b)(j∣i),P(a)(j∣i)},\alpha \ge \frac{1}{2}(1-A_{bb})\sum_i \pi_i^{\ast} \sum_j \min\lbrace P^{(b)}(j\mid i), P^{(a)}(j\mid i)\rbrace,

because, with probability 1−Abb1-A_{bb}, the dwell interval consists of a single transition, whose distributions under the two strategies overlap. When the mean dwell length is small, the two statements bound α\alpha from below, so the new strategy cannot be identified reliably within the dwell interval. This is the regime discussed in Appendix B.5 of the initial submission (B.6 of the revised version).

Relation to the main result. The proof of Theorem 7 (ρ<1\rho < 1) (Appendix A.9 of the initial submission, A.8 of the revised version) does not use Proposition 2, so this revision does not affect the statistical-limit result.

Revision. In the revised version, Proposition 2 has been restated under continued switching in the non-asymptotic form above, and the lower bound on the error probability has been added. Its proof (Appendix A.10 of the initial submission, A.9 of the revised version) has been extended with the dwell-interval argument. The order-kk extension (Appendix A.11 of the initial submission, A.10 of the revised version) and Appendix B.6 of the revised version have been revised accordingly. The changes made to these parts in the second revision are shown in blue, and the red marks of the first revision are retained.

AuthorsOpenReview ↗

Response to Reviewer S9Xw (3/3)

A3 (response to Q3)

This is a careful observation. We have checked the whole paper and all of the code, and the answer is yes. The analysis in Section 3.3 and Appendix B.3 of the initial submission resets the transition counts at the true switching times, and the values in Figure B.1(a) and the n=3n=3 simulation are computed in this way. The caption of Figure B.1 calls this setting hidden switching, which is inaccurate. We have explicitly distinguished this analytical setting from hidden switching in the revised version and added numerical results in which the predictors infer the switches themselves.

Two settings. In the analysis of Section 3.3 both predictors are told the switching times. At each switch the counts are reset, and each predictor estimates the kernel only from the transitions in the current dwell interval. This setting separates the estimation gap from the problem of inferring the switches. Under hidden switching a predictor observes only the state sequence and has to infer the switches from it. The generative model of Section 3.3 redraws the kernel from the prior at each switch. For this model the Bayes-optimal predictor mixes the segment predictions with weights given by the posterior of the run length. The run length is the number of transitions since the last switch, and this procedure is the online change-point detection of Adams & MacKay (2007). The training experiment E3 in Section 5 is in the hidden setting. The models are trained on the observations only, and the optimal filter does not know the switching times either.

Scope. Theorem 3 concerns the two predictors at zero counts and does not depend on whether the switching times are known. The statement that zero-count steps make up a fraction pswitchp_{\text{switch}} of all steps relies on known switching times. So does the decomposition of the gap in Appendix B.3 of the initial submission (B.4 of the revised version) into the structural component and the posterior coupling component. Both hold only in the analytical setting. As pswitch→1p_{\text{switch}} \to 1 every step starts a new dwell interval, so the limit is the same in both settings. The statistical limit of Section 5 (Theorem 7, Proposition 2) is stated under hidden switching and is not affected.

Numerical results under hidden switching. To test whether the conclusions of Section 3.3 hold under hidden switching, we recomputed the gap on the same sequences as Figure B.1(a), for its four values of rr and eight switching rates (32 combinations). Both predictors use only the observations, and each infers the switches by online change-point detection with the known switching probability. The predictor that uses f∗f^{\ast} as its segment predictor is the Bayes-optimal predictor for this generative model. The results are shown in the new Figure B.2. Figure B.2(a) shows the gap under hidden switching. It is positive in all 32 combinations and approaches gstructg_{\text{struct}} as pswitch→1p_{\text{switch}} \to 1. The conclusion of Section 3.3 that the gap does not vanish over time therefore also holds under hidden switching. Figure B.2(b) shows the ratio of the gap under hidden switching to the gap with known switching times. It ranges from 0.32 to 0.999 and tends to 1 as pswitch→1p_{\text{switch}} \to 1. The gap with known switching times also approaches gstructg_{\text{struct}} as pswitch→1p_{\text{switch}} \to 1 (Figure B.1(a)).

Revision. The paragraph on strategy switching in Section 3.3 and the remark after Theorem 3 have been revised to state that the counts are reset at the true switching times and to distinguish this setting from hidden switching. Appendix B.3 of the initial submission (B.4 of the revised version) and Figure B.1 have been marked as the setting with known switching times, and the caption of Figure B.1 has been corrected accordingly. The results under hidden switching and Figure B.2 have been added to Appendix B.4.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.