Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs

• URL: http://arxiv.org/abs/2508.07395v1
• Date: Sun, 10 Aug 2025 15:49:44 GMT
• Title: Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs
• Authors: Behnoush Khavari, Mehran Shakerinava, Jayesh Khullar, Jerry Huang, François Rivest, Siamak Ravanbakhsh, Sarath Chandar,
• Abstract summary: We investigate whether combining input-independent and non-negative SSMs could solve simple state-tracking tasks, such as parity, regardless of depth.<n>Our experiments support this conclusion by analyzing an SSM model that combines S4D and Mamba layers.
• Score: 24.139438264302882
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work has shown that LRNN models such as S4D, Mamba, and DeltaNet lack state-tracking capability due to either time-invariant transition matrices or restricted eigenvalue ranges. To address this, input-dependent transition matrices, particularly those that are complex or non-triangular, have been proposed to enhance SSM performance on such tasks. While existing theorems demonstrate that both input-independent and non-negative SSMs are incapable of solving simple state-tracking tasks, such as parity, regardless of depth, they do not explore whether combining these two types in a multilayer SSM could help. We investigate this question for efficient SSMs with diagonal transition matrices and show that such combinations still fail to solve parity. This implies that a recurrence layer must both be input-dependent and include negative eigenvalues. Our experiments support this conclusion by analyzing an SSM model that combines S4D and Mamba layers.

Related papers

• Routing Mamba: Scaling State Space Models with Mixture-of-Experts Projection [88.47928738482719]
  Linear State Space Models (SSMs) offer remarkable performance gains in sequence modeling.<n>Recent advances, such as Mamba, further enhance SSMs with input-dependent gating and hardware-aware implementations.<n>We introduce Routing Mamba (RoM), a novel approach that scales SSM parameters using sparse mixtures of linear projection experts.
  arXiv  Detail & Related papers  (2025-06-22T19:26:55Z)
• Benchmarking Multi-modal Semantic Segmentation under Sensor Failures: Missing and Noisy Modality Robustness [61.87055159919641]
  Multi-modal semantic segmentation (MMSS) addresses the limitations of single-modality data by integrating complementary information across modalities.<n>Despite notable progress, a significant gap persists between research and real-world deployment due to variability and uncertainty in multi-modal data quality.<n>We introduce a robustness benchmark that evaluates MMSS models under three scenarios: Entire-Missing Modality (EMM), Random-Missing Modality (RMM), and Noisy Modality (NM)
  arXiv  Detail & Related papers  (2025-03-24T08:46:52Z)
• Understanding and Mitigating Bottlenecks of State Space Models through the Lens of Recency and Over-smoothing [56.66469232740998]
  We show that Structured State Space Models (SSMs) are inherently limited by strong recency bias.<n>This bias impairs the models' ability to recall distant information and introduces robustness issues.<n>We propose to polarize two channels of the state transition matrices in SSMs, setting them to zero and one, respectively, simultaneously addressing recency bias and over-smoothing.
  arXiv  Detail & Related papers  (2024-12-31T22:06:39Z)
• Provable Benefits of Complex Parameterizations for Structured State Space Models [51.90574950170374]
  Structured state space models (SSMs) are linear dynamical systems adhering to a specified structure. In contrast to typical neural network modules, whose parameterizations are real, SSMs often use complex parameterizations. This paper takes a step towards explaining the benefits of complex parameterizations for SSMs by establishing formal gaps between real and complex diagonal SSMs.
  arXiv  Detail & Related papers  (2024-10-17T22:35:50Z)
• GroupMamba: Efficient Group-Based Visual State Space Model [66.35608254724566]
  State-space models (SSMs) have recently shown promise in capturing long-range dependencies with subquadratic computational complexity.<n>However, purely SSM-based models face critical challenges related to stability and achieving state-of-the-art performance in computer vision tasks.<n>Our paper addresses the challenges of scaling SSM-based models for computer vision, particularly the instability and inefficiency of large model sizes.
  arXiv  Detail & Related papers  (2024-07-18T17:59:58Z)
• State Space Models are Provably Comparable to Transformers in Dynamic Token Selection [41.617269918948686]
  Deep neural networks based on state space models (SSMs) are attracting significant attention in sequence modeling.<n>We show that SSMs are comparable to Transformers in extracting the essential tokens depending on the input.
  arXiv  Detail & Related papers  (2024-05-29T12:23:48Z)
• SMR: State Memory Replay for Long Sequence Modeling [19.755738298836526]
  This paper proposes a novel non-recursive non-uniform sample processing strategy to overcome compatibility limitations in parallel convolutional computation. We introduce State Memory Replay (SMR), which utilizes learnable memories to adjust the current state with multi-step information for generalization at sampling points different from those in the training data. Experiments on long-range modeling tasks in autoregressive language modeling and Long Range Arena demonstrate the general effectiveness of the SMR mechanism for a series of SSM models.
  arXiv  Detail & Related papers  (2024-05-27T17:53:32Z)
• The Expressive Capacity of State Space Models: A Formal Language Perspective [0.8948475969696075]
  recurrent models based on linear state space models (SSMs) have shown promising performance in language modeling (LM), competititve with transformers. We present a comprehensive theoretical study of the capacity of such SSMs as it compares to that of transformers and traditional RNNs.
  arXiv  Detail & Related papers  (2024-05-27T17:46:57Z)
• Low-Rank Multitask Learning based on Tensorized SVMs and LSSVMs [65.42104819071444]
  Multitask learning (MTL) leverages task-relatedness to enhance performance. We employ high-order tensors, with each mode corresponding to a task index, to naturally represent tasks referenced by multiple indices. We propose a general framework of low-rank MTL methods with tensorized support vector machines (SVMs) and least square support vector machines (LSSVMs)
  arXiv  Detail & Related papers  (2023-08-30T14:28:26Z)
• Multi-constrained Symmetric Nonnegative Latent Factor Analysis for Accurately Representing Large-scale Undirected Weighted Networks [2.1797442801107056]
  An Undirected Weighted Network (UWN) is frequently encountered in a big-data-related application. An analysis model should carefully consider its symmetric-topology for describing an UWN's intrinsic symmetry. This paper proposes a Multi-constrained Symmetric Nonnegative Latent-factor-analysis model with two-fold ideas.
  arXiv  Detail & Related papers  (2023-06-06T14:13:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.