CCMamba: Rank-Aware State-Space Modeling from Causal Scans to Incidence-Structured Mixing on Combinatorial Complexes

Selective state space models (SSMs) rely on ordered scans, whereas combinatorial complexes, a general framework encompassing graphs, hypergraphs, simplicial complexes, and cellular complexes, have no canonical ordering of their cells. Imposing a linearization, as in existing Graph Mamba approaches, can introduce order dependence because causal selective scans induce position-dependent, block lower-triangular mixing. We study this mismatch by separating the support of a mixing operator from its factorized content-dependent interactions, and introduce Combinatorial Complex Mamba (CCMamba), a rank-aware framework that combines incidence-based cross-rank lifting with two complementary structured mixers. CCMamba-S preserves bidirectional selective SSM scans and efficient fused sequence processing, while remaining sensitive to the chosen within-rank ordering. CCMamba-K instead replaces causal sequence support with incidence-supported, index-free structural gating and factorized kernel mixing, providing permutation-equivariant mixing without requiring a cell linearization. We characterize the order sensitivity of causal scans, establish the permutation equivariance and structural factorization of CCMamba-K, and give a conditional characterization of its expressive power under explicit assumptions. Experiments across graph, hypergraph, simplicial-complex, and cellular-complex benchmarks show that CCMamba achieves competitive predictive performance, with memory and runtime advantages over the evaluated attention-based baselines in several higher-order settings. Code: https://anonymous.4open.science/r/CCMamba .