Unbiased Training of True 2D Linear Recurrences with Parallel Scans

Vision models built on linear recurrences, such as VMamba, are fast because they cut an image into one-dimensional pixel orders and run each order through a parallel scan. A parallel scan is a prefix-sum algorithm that computes all hidden states of a linear recurrence in logarithmic rather than linear depth. The cost is that none of these models actually uses a two-dimensional recurrence, where each pixel's state depends on both its left neighbor and its upper neighbor. That kind of recurrence goes back to multi-dimensional LSTMs and to Roesser's 2D state-space model. It has no known parallel scan, so it is either evaluated along anti-diagonal wavefronts in $H+W$ sequential steps or unrolled into a fixed FFT convolution that rules out input-dependent gates.

This note proposes computing a selective (input-gated) 2D linear recurrence as a short series of ordinary row and column scans, where each extra term adds back path interactions the separable scans miss. The recurrence then becomes a matter of how many terms to keep, and stopping early produces a biased gradient for the full model, much as truncated backpropagation through time does. The proposal treats that bias directly. We randomize the stopping point with reweighting so the gradient is unbiased for the full 2D recurrence. We also test a measurable criterion, borrowed from biased-SGD theory, that predicts when a cheap fixed truncation is good enough.

Core Claim

Consider a 2D linear recurrence with per-channel, input-dependent diagonal decays $a_1(x,y)$ and $a_2(x,y)$:

$$h_{x,y} = a_1 h_{x-1,y} + a_2 h_{x,y-1} + b\,u_{x,y},$$

where $u$ is the input feature map and $b$ is an input projection. Write the grid as a linear system $(I - A_1 S_x - A_2 S_y)h = Bu$, where $S_x$ and $S_y$ shift the map by one pixel horizontally and vertically. The separable operator $M = (I - A_1 S_x)(I - A_2 S_y)$ is inverted exactly by one column scan followed by one row scan, both parallel. It differs from the true operator only by a cross term $A_1 A_2 S_x S_y$, which corrects for path multiplicity. In the constant-coefficient case the true kernel weights each path by a binomial count, whereas the separable kernel counts each offset once.

Expanding gives

$$h = \sum_{k=0}^{\infty} \left(M^{-1} A_1 A_2 S_x S_y\right)^k M^{-1} B u.$$

Each term costs two parallel scans. The series is exact after at most $\min(H,W)$ terms because the diagonal shift is nilpotent. When decays are strong it converges quickly. When decays are weak, which is the regime that long-range tasks need, it converges slowly.

The central claim has two parts. The first is that a randomized-truncation estimator makes training of this full 2D selective recurrence unbiased at logarithmic scan depth per term. The estimator samples the number of terms $K$ and reweights term $k$ by $1/P(K\ge k)$, in the style of Unbiasing Truncated Backpropagation Through Time. The second is that the multiplicative bias condition $\|\mathbb{E}[g]-\nabla f\|\le C\|\nabla f\|$ with $C<1$, from XOR-SGD, can be measured during training. That measurement predicts whether fixed truncation is safe or will drift.

Relation to Prior Work

Several papers motivate the gap. VMamba runs four separate 1D selective scans (cross-scan). LocalMamba windows those scans to keep vertical neighbors close. Spatial-Mamba uses one scan and fuses states with dilated convolutions, and argues that how information is fused matters more than how many directions are scanned. None of the three has a state that genuinely depends on two predecessors.

A 2-Dimensional State Space Layer for Spatial Inductive Bias does have a true Roesser-style 2D state. It trains through FFT convolution, which forbids input-dependent coefficients, and its authors name the missing multi-dimensional parallel scanner as their main limitation. Our series supplies a scan-based route that keeps selectivity. It is the direct successor to that paper.

The older non-linear 2D recurrences are evidence that true 2D state helps but is slow. Multi-Dimensional Recurrent Neural Networks reports 6.8% versus 11.3% CNN error on warped MNIST. SCNN and the hGRU show the same pattern. All of them pay the sequential cost that Resurrecting Recurrent Neural Networks for Long Sequences removed in 1D by linearizing the recurrence. We reuse that paper's stable exponential decay parameterization and ring initialization.

Two papers supply the method on the optimization side. ARTBP gives the reweighted random-truncation trick, but it was validated only on 1D sequences. It also comes with a warning: on its influence-balancing task, fixed truncation diverged even at length 100. On Biased Stochastic Gradient Estimation cautions that unbiasedness can cost more variance than it is worth. That is why we treat the choice between fixed and randomized truncation as an empirical question governed by the measured bias ratio $C$, rather than assuming unbiasedness always wins.

Research Program

We first build the operator. A fused kernel performs the column-then-row scan for $M^{-1}$ with input-dependent decays, applies the diagonal correction, and repeats. Four corner orientations give an isotropic receptive field, as in the MDRNN. The forward pass uses $K$ terms. In training, $K$ is drawn from a truncated geometric distribution with mean $\bar K$, and terms are reweighted so that the expected output and gradient match the full series. At evaluation we either run to a tolerance or use the exact wavefront solver as a reference.

We then measure bias. On small grids we can compute exact gradients with the wavefront solver, which lets us track the bias ratio $C(t) = \|\mathbb{E}[g_K]-\nabla f\|/\|\nabla f\|$ for fixed-$K$ training throughout optimization. The hypothesis is that $C$ stays well below 1 on texture-dominated classification. On path-integration tasks, where learned decays drift toward 1 and the series converges slowly, $C$ should rise toward or past 1, and those are the runs where fixed-$K$ training should stall or diverge. The second open problem in the biased-SGD literature, extending such conditions to non-convex deep networks, is approached here empirically rather than claimed theoretically.

The last stage is a 2D analogue of ARTBP's influence-balancing task. It is a synthetic grid task in which a parameter has a small helpful effect along short, few-turn paths and a dominant harmful effect accumulated over many multi-turn paths. Fixed truncation should be provably misled on this task.

Baselines

The naive reference is the separable model alone ($K=0$): one column scan and one row scan per orientation, with no correction terms. It has the same cost profile as cross-scan and isolates whether the 2D correction matters at all.

The strongest existing method is VMamba-style cross-scan. The file reports VMamba-T at 82.6% top-1 on ImageNet-1K and 48.0% mIoU on ADE20K. Spatial-Mamba-T reports 83.5% top-1 (Spatial-Mamba). Full ImageNet-1K pretraining is outside our budget, so we will reimplement both at tiny scale on ImageNet-100 with identical stems, depth, width, FLOP budget within 5%, training recipe, and an equal hyperparameter sweep of the same size for every model. For the true-2D comparison on ImageNet-100, the reference number is DeiT-Tiny with the 2D-SSM layer at 81.16% (2D-SSM). We will insert our layer into the same DeiT-Tiny at the same position. On LRA CIFAR-10 grayscale the reference is MEGA with 2D-SSM at 91.31%, and on PathX the reference is LRU at 94.2% (LRU). For Pathfinder the hGRU reports parity with a 152-layer ResNet but no decimal accuracy, so no reported result was found on Lacuna for hGRU Pathfinder accuracy. We will retrain it ourselves.

The key ablation is fixed-$K$ truncation trained with exact gradients of the truncated model, compared against randomized-$K$ unbiased training at matched mean compute $\bar K$. Beating the baselines means two things. Randomized training must match or beat fixed-$K$ at equal compute on long-range tasks. Our layer must exceed cross-scan and the FFT-based 2D-SSM on Pathfinder-14, PathX, or warped-digit tasks while staying within one point of them on ImageNet-100, at comparable throughput.

Why not just…?

Why not just use cross-scan, which is already parallel and global? Four 1D scans give every pixel global context, but only along straight lines. Spatial-Mamba's own result that fusion beats more scan directions suggests straight-line scanning is the weak point. Still, cross-scan may simply be enough on ImageNet. The $K=0$ versus full-series comparison on Pathfinder-14 and PathX will settle whether true path integration adds anything. If it does not, the architectural claim fails, and we will report that.

Why not just define the model as the $K$-term truncation and train it exactly? This is the most serious threat, because a fixed-$K$ model has an exact gradient and no bias problem. The answer depends on whether useful long-range dependencies live in the slowly converging tail of the series. The tracked bias ratio $C$ and the 2D influence-balancing task test exactly this. If fixed-$K$ matches randomized training everywhere, we will adopt fixed-$K$ and recast the contribution as the parallel series operator plus a diagnostic for when truncation is safe.

Why not just use the exact wavefront solver or the FFT form? The wavefront solver is exact but needs $H+W$ sequential steps, which is the bottleneck SCNN already suffers from. The FFT form is fast but input-invariant. We will report wall-clock throughput against both at resolutions from 32 to 128, and accuracy against FFT 2D-SSM, to show where each loses.

Decisive Checks

Three results decide the proposal. The first is a gradient-bias study on 32×32 grids against exact wavefront gradients, showing $C(t)$ for fixed and randomized $K$, and showing that runs crossing $C\approx1$ are the ones that diverge. The second is the 2D influence-balancing task, where fixed $K$ should fail and randomized $K$ should converge, mirroring ARTBP's 1D finding. The third is matched-compute accuracy on Pathfinder, PathX and ImageNet-100 against cross-scan, Spatial-Mamba-style fusion, and FFT 2D-SSM, with throughput reported alongside.

If randomized truncation buys nothing over fixed truncation and the full series buys nothing over the separable model on the long-range tasks, the idea is wrong.