Visual state-space models are image backbones that sweep a small running memory across the image instead of comparing every pair of pixels. They reach the whole image at a cost that grows only linearly with image size. Recent versions update each patch from its left and upper neighbours at once, and they subtract the diagonal neighbour so that the same information is not counted twice. The subtraction works in practice, but its authors call it a heuristic and say an unbiasedness analysis is missing (2D-CrossScan Mamba). This proposal supplies that analysis and then uses it to ask a sharper question.
Without the subtraction, the recursion weights each source pixel by the number of lattice paths that reach it. That count is a binomial random walk, which is the same mechanism that makes convolutional receptive fields collapse into a Gaussian. When the diagonal coefficient equals the product of the horizontal and vertical ones, the subtraction removes these path counts exactly, and the 2D recursion becomes identical to a horizontal 1D scan followed by a vertical 1D scan. Its gains may therefore come from cheap axial composition rather than from true 2D propagation. We treat the number of neighbour lags the recursion uses as a spatial Markov order $m$, in the sense of the information-theory results that finite-memory approximations converge to the true quantity as memory grows. We then prove and measure how fast receptive-field error falls with $m$ and with state size. That finite-order rate is exactly what the channel-capacity literature could not provide.
Core Claim
Consider the 2D-CrossScan update $h(x,y) = A_x h(x-1,y) + A_y h(x,y-1) - A_{xy} h(x-1,y-1) + B u(x,y)$. Here $h$ is the hidden state at patch $(x,y)$, $u$ is the input feature, and $A_x, A_y, A_{xy}, B$ are learned matrices. Writing $S_x, S_y$ for unit shifts along each axis, the update is $(I - A_x S_x - A_y S_y + A_{xy} S_x S_y)\,h = Bu$.
With no subtraction ($A_{xy}=0$), take scalar coefficients $a$ and $b$ for clarity (matrices behave the same up to ordering). The response at offset $(i,j)$ is
$$k_{\text{no-sub}}(i,j) = \binom{i+j}{i}\, a^i b^j,$$
so influence concentrates along the diagonal with random-walk multiplicity. This is the lattice-path analogue of the Central Limit Theorem argument by which Luo et al. showed that stacked convolutions yield Gaussian effective receptive fields growing only as the square root of depth.
If $A_x$ and $A_y$ commute and $A_{xy} = A_x A_y$, the operator factorizes as $(I - A_x S_x)(I - A_y S_y)$. The response becomes the separable $k(i,j) = A_x^i A_y^j B$, with no path multiplicity. This is exactly a row scan composed with a column scan.
The diagonal subtraction is therefore unbiased precisely on this separable manifold. When it is learned freely, it adds a non-separable component whose stability is not guaranteed. A stable non-separable system is the 2D analogue of a stable 1D filter: its total response stays bounded. We make three claims:
- This characterization, extended to input-dependent ("selective") coefficients where commutativity breaks, explains when 2D-CrossScan differs from axial scanning.
- A first-order separable recursion with state dimension $d$ can express only sums of $d$ separable exponential profiles. Raising $d$ or the Markov order $m$ (lags per axis) closes the gap to non-separable, roughly isotropic target kernels at a rate set by the target's decay.
- That rate gives a principled rule for choosing $m$ and $d$, which the current architectures set empirically.
Research Program
Theory. We first prove the factorization and stability statements for diagonal (input-independent) state matrices. We then bound the deviation from separability when $A_{xy}$ is free or the coefficients vary with position, in terms of the commutator norm and $\|A_{xy} - A_x A_y\|$.
Next we define the order-$m$ quarter-plane recursion. It is a 2D rational filter whose numerator and denominator are polynomials of degree $m$ in $S_x, S_y$. We study how well it approximates a target influence kernel $k^\ast$ restricted to a quadrant, combining four corner-initialized copies as in MDRNN. The quantity of interest is
$$\epsilon(m,d) = \min_{\text{order } m,\ \text{state } d} \sum_{i,j} |k(i,j) - k^\ast(i,j)|.$$
It plays the role that $C_\infty - C_m$ plays in Li and Tan. There, $C_m \to C$ was proved without a rate. Here, linearity of the spatial recursion lets us state a rate. The expectation is that $\epsilon$ decays geometrically in $m$ for exponentially decaying targets, because rational approximation of analytic transfer functions converges geometrically, and only polynomially for heavy-tailed targets.
The capacity papers (Li and Tan, McBain and Viterbo) motivate the question and the "finite order converges to the true quantity" framing. Their proofs are 1D and asymptotic, and we do not reuse them.
Empirical. We build a single scan module with four switchable modes:
- no subtraction;
- free subtraction, which is 2D-CrossScan;
- tied subtraction $A_{xy}=A_xA_y$;
- explicit sequential row-then-column 1D scans, which are parallelizable and much cheaper than a 2D wavefront.
Each mode can be run at Markov orders 1 to 3. In every trained model we measure the gradient-based effective receptive field using the protocol of Luo et al.. We also measure how far learned $A_{xy}$ drifts from $A_xA_y$, to test whether training discovers the separable solution on its own.
Baselines
The do-nothing reference is a plain ResNet backbone of matched parameter count. On classification it shows how much any global mixer adds.
The 1D-flattening reference is VMamba's four-direction selective scan (VMamba). It reports 80.86 AP for VMamba-T on PANDA (as quoted in 2D-CrossScan Mamba), 83.9% ImageNet-1K top-1 for the Base model, and 48.0% ADE20K mIoU for the Tiny model.
The strongest existing method on this question is 2D-CrossScan Mamba. It reports 82.80 AP on PANDA, 47.7 box AP on COCO, and 83.5% ImageNet-1K top-1. No ADE20K number was found on Lacuna for it.
A factorized-attention reference is CCNet's two-pass criss-cross attention (CCNet), which reports 45.76% ADE20K validation mIoU. It is also a Markov-step construction: a product of sparse transition matrices.
All variants share one backbone skeleton, training recipe, data, and epoch count, with an equal hyperparameter sweep per variant. Because we cannot match the original papers' compute, we retrain VMamba-T and 2D-CrossScan at Tiny scale in our own pipeline. We report the published numbers only as anchors.
The key ablation compares the four scan modes at identical cost budgets. Beating 2D-CrossScan has two meanings, depending on the outcome. If tied or sequential scans match free subtraction within seed variance (three seeds) at lower latency, we have shown the 2D wavefront is unnecessary. If free subtraction wins, the gain must track measured non-separability, which would confirm the theory's account of what the heuristic adds.
Why not just…?
Why not just keep the learned diagonal subtraction, since it already works? It works on benchmarks, but nobody knows whether it works because it is separable or despite it. If it is separable, it can be replaced by two cheap 1D scans. If it is non-separable, it may be unstable at gigapixel sizes. The mode ablation, together with the measured drift of $A_{xy}$ from $A_xA_y$, settles this directly.
Why not just use a global FFT filter or large-kernel convolution? This is a real threat. Spectral gating (Butterworth as Attention) reaches every pixel in $O(N\log N)$ and can represent non-separable kernels directly. No reported result for it was found on Lacuna for our benchmarks. We include an FFT global-filter variant at matched parameters. If it matches the order-$m$ recursion on ADE20K and PANDA, the contribution narrows to theory and order selection, and we will say so. Our argument for recursion rests on input-dependent coefficients, which a fixed spectral filter lacks. That is testable on the relational tasks below.
Why not just raise VMamba's state size? A larger state does not remove the 1D flattening gap: vertically adjacent patches remain far apart in the scan order. The cross-shaped receptive fields reported by 2D-CrossScan Mamba are the symptom. We sweep VMamba state size alongside $d$ in our module to show whether the gap closes.
Why not just stack deeper or dilated convolutions? Luo et al. show the effective receptive field stays Gaussian and that skip connections shrink it. Our no-subtraction mode reproduces this binomial mechanism inside a scan, so it serves as the controlled version of this alternative.
Proposed Experiments
Synthetic. First we fit each module, with a frozen linear readout, to known target kernels: separable exponential, isotropic exponential, and isotropic power-law. We plot $\epsilon(m,d)$ against the predicted rates. This is the decisive check of the theory: geometric decay for exponential targets and slower decay for heavy-tailed ones.
Long-range reasoning. Second, we train on CLEVR and Sort-of-CLEVR, where pixel-local models fail and the BCN/multiRN reference reaches 97.7% on CLEVR (BCN). We test whether the required Markov order predicted from measured object distances matches the order at which accuracy saturates.
Backbone scale. Third, at Tiny scale we compare the four modes on ImageNet-1K, ADE20K, and PANDA, reporting accuracy, mIoU, AP, throughput, and memory.
The proposal fails if sequential axial scans are both cheaper and no worse everywhere and the predicted rates do not appear in the synthetic study. It succeeds as theory if the rates hold. It succeeds as architecture if the order rule picks configurations that match 2D-CrossScan's 82.80 PANDA AP at lower latency.
References
- 2D-CrossScan Mamba: Enhancing State Space Models with Spatially Consistent Multi-Path 2D Information Propagation
- Understanding the Effective Receptive Field in Deep Convolutional Neural Networks
- Multi-dimensional Recurrent Neural Networks
- On the Capacity of Channels with Deletions and States
- On Noisy Duplication Channels with Markov Sources
- VMamba: Visual State Space Model
- CCNet: Criss-Cross Attention for Semantic Segmentation
- Butterworth as Attention: Anisotropic Spectral Gating for Pansharpening
- Broadcasting Convolutional Network for Visual Relational Reasoning