Scanning Images Along Eigenvectors Without Trusting Their Signs

Vision state space models (SSMs) are sequence models such as Mamba adapted to images. They give each patch a view of the whole image at linear cost, which is one answer to the small receptive field of convolutional networks. The catch is that they must first flatten the 2D image into a 1D sequence of patches, so the order in which patches are read shapes what each patch can see. Spectral State Space Model for Rotation-Invariant Visual Representation Learning proposed a content-based order. It builds a graph over patches weighted by feature similarity, computes eigenvectors of that graph's Laplacian (the matrix whose low-frequency eigenvectors vary smoothly across well-connected regions), and reads patches in the order of their eigenvector values. The resulting order follows objects rather than pixel axes and survives rotation. This order, however, rests on an object that is not uniquely defined. An eigensolver may return $v$ or $-v$, and flipping the sign reverses the entire scan. When two eigenvalues are equal or nearly equal, the solver may also return any rotation of the pair. When objects are disconnected in the affinity graph, the solver may return any mixture of the per-object indicator vectors. The paper handles only the first problem, and only with a static rule ("make the first nonzero entry positive"). Related work shows that rules of this kind jump discontinuously under small perturbations.

The claim of this note is that every one of these ambiguities acts on the scan as a symmetry group. A recurrent scan layer can therefore be made exactly invariant to that group by averaging over the scans the group produces, rather than by picking one scan through a canonicalization rule. For sign ambiguity this averaging amounts to running the scan forward and backward and summing the results, which is the scan-level analogue of SignNet's even function. For near-degenerate eigenvalues it becomes a small random average over rotations inside the eigenspace, with the rotation spread shrinking smoothly as the eigenvalue gap grows. For disconnected objects it becomes separate scans per connected component, with state reset between components. The proposal is to build this layer, measure how often the degenerate cases actually occur in image patch graphs, and test whether handling them changes accuracy and stability. If they turn out to be rare, the method collapses to a bidirectional scan, and the note says in advance how that outcome would be recognized.

What exists and what is missing

The spectral-ambiguity literature supplies the method. The receptive-field literature supplies the application regime.

On the method side, three results matter. Sign and Basis Invariant Networks for Spectral Graph Representation Learning enforces sign invariance through $\phi(v)+\phi(-v)$ and basis invariance through projection matrices. It also shows that repeated eigenvalues are common, occurring in 64% of ZINC molecules. On the Stability of Expressive Positional Encodings for Graphs shows that hard partitioning into eigenspaces is unstable when eigengaps are small, and replaces it with soft, eigenvalue-dependent weighting (SPE). Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networks shows that static canonicalization is discontinuous. All three produce per-node features or encodings. None produces an ordering, and an ordering is what a scan consumes. Sorting is discontinuous even when the sorting key is invariant, so these methods cannot simply be plugged into a scan generator. This is the gap the proposal targets.

On the application side, Spectral State Space Model for Rotation-Invariant Visual Representation Learning is the direct predecessor. It reports 87.86% top-1 on miniImageNet for Spectral VMamba-Tiny against 86.25% for VMamba-T, and above 78% under 15° rotation increments where VMamba falls to nearly 50%. Its authors themselves flag disconnected components as unresolved. Two other lines constrain the design. EccoMamba documents that flattening images into sequences breaks spatial continuity, which is the same problem a flipped or scrambled spectral order causes. GIST shows a different route to invariance: its attention uses only inner products of spectral embeddings, which do not depend on the choice of basis. GIST shows large gains from gauge invariance under mesh-resolution transfer, with $R^2$ 0.840 against 0.526. It is an attention model, though, and it contains no scan. It serves here as a competing design rather than as a component.

Core construction

Let $V \in \mathbb{R}^{N\times k}$ hold the $k$ lowest nontrivial eigenvectors of the patch-graph Laplacian, with eigenvalues $\lambda_1 \le \dots \le \lambda_k$. Let $\mathrm{SSM}_\pi(x)$ denote a selective scan over patch features $x$ in the order $\pi$, with outputs returned to the original patch positions. The proposed layer draws a random rotation $Q = \exp(S)$, where $S$ is a skew-symmetric $k\times k$ matrix with independent entries $S_{ij} \sim \mathcal{N}(0, \sigma_{ij}^2)$ and spread $\sigma_{ij} = \pi\, e^{-|\lambda_i-\lambda_j|/\tau}$. The sorting key is the first column of $VQ$. The layer averages over both scan directions:

$$y = \mathbb{E}_Q \tfrac{1}{2}\big[\mathrm{SSM}_{\pi(VQ)}(x) + \mathrm{SSM}_{\mathrm{rev}\,\pi(VQ)}(x)\big],$$

Here $\pi(VQ)$ is the argsort of the key, $\mathrm{rev}$ reverses an order, and $\tau$ is a temperature set by validation.

The design behaves correctly at both extremes of the eigenvalue gap. When gaps are large, $\sigma_{ij}\approx 0$ and $Q$ reduces to a sign choice, and the forward/backward sum makes the output exactly invariant to $v \to -v$. When two eigenvalues coincide, the rotation spread covers the whole circle in their plane, so the expectation is invariant to the solver's arbitrary basis there. Because the spread varies smoothly with the gap, the transition between these two regimes is gradual. This is the ordering analogue of SPE's soft eigenspace weighting, and it is meant to avoid the discontinuity Huang et al. identified in hard partitioning. At training time the expectation is estimated with $m$ samples, and at inference with a fixed set of seeds. Disconnected components are handled before any of this. The zero-eigenvalue projection $P_0 = V_0V_0^\top$ is invariant to basis choice, so thresholding it recovers the components exactly. Each component is then scanned with its own Laplacian, the recurrent state is reset between components, and the order in which components are visited is averaged over in the same way. Whether this smoothing yields a continuous layer in expectation will be checked empirically, as described below. It is not assumed.

Research Program

The work begins with a measurement study, because the value of the proposal depends on it. On miniImageNet and ADE20K patch graphs, built the way Spectral VMamba builds them at each stage, we record three quantities. The first is the distribution of relative eigengaps among the scanned eigenvectors. The second is how often the patch graph splits into several components at the affinity thresholds used. The third is the flip rate: how often the static first-nonzero-positive rule reverses the scan under small, label-preserving perturbations such as Gaussian noise, a one-pixel shift, JPEG compression, or a 1° rotation. ZINC's 64% multiplicity rate concerns small, highly symmetric molecules and says nothing directly about natural images, so this study is needed before any claim of prevalence.

The second step builds the layer as a drop-in replacement for the Spectral Traversal Scan inside Spectral VMamba-Tiny and trains it under that paper's protocol. The third step analyzes stability directly. For a fixed image under a sequence of shrinking perturbations, we plot how much the layer output changes and compare this curve across the static rule, sign-only averaging, and the full layer. We expect jumps under the static rule and a smooth decay for the full layer.

Baselines

The naive reference point is VMamba-T with its standard four-direction grid scan (SS2D), trained with the same recipe. Its reported miniImageNet top-1 of 86.25%, collapsing to nearly 50% under some rotations, comes from Spectral State Space Model for Rotation-Invariant Visual Representation Learning. We will rerun it rather than quote it.

The strongest existing method is Spectral VMamba-Tiny itself, which uses static sign canonicalization and a rotational feature normalizer. It reports 87.86% top-1 on miniImageNet at 3.9G FLOPs and above 78% at non-canonical angles, in the same paper. It is the strongest competitor because it is the only method in the file that uses Laplacian eigenvectors to order a visual scan. It will be run from the same code with identical data, augmentation, schedule and hyperparameter search budget, and only the scan generator will be swapped. The file contains no reported ADE20K number for it, so that number will be produced here. CCNet's 45.76% ADE20K validation mIoU, reported in CCNet, comes from a different backbone and will be cited only as context.

Beating Spectral VMamba means one of two outcomes. The first is equal or better clean accuracy together with a clear improvement on the worst-angle rotation accuracy and on the perturbation-stability measures. The second is a statistically significant improvement on the image subset where the measurement study found small gaps or several components. Significance will be established over five seeds with paired tests, following the protocol in Vision Mamba for Classification of Breast Ultrasound Images.

The key ablation isolates each ingredient: sign averaging only, then with gap-dependent rotation averaging, then with per-component scanning. All three are matched in FLOPs by adjusting $m$ against model width, since averaging multiplies scan cost. A second ablation replaces the gap-dependent spread with a hard threshold, which tests the continuity argument directly.

Why not just…?

Why not just use a bidirectional scan, as Vim already does? This alternative is a real threat. A forward-plus-backward scan over the static spectral order already removes sign ambiguity exactly, and it is the first ablation arm. If the measurement study finds that near-degenerate gaps and disconnected components are rare in image patch graphs, and the rotation and component arms add nothing beyond this arm, then the honest conclusion is that a bidirectional spectral scan is sufficient. That result would still correct Spectral VMamba's discontinuous rule. The broader proposal survives only if the gains concentrate on the degenerate subset.

Why not just train with random sign flips, as SAN does? Rethinking Graph Transformers with Spectral Attention flips eigenvector signs with probability 0.5 during training. This teaches approximate invariance to $2^k$ sign patterns but offers no protection against continuous basis rotations. In the graph setting, SignNet's architectural invariance reaches 0.084 ZINC MAE against SAN's 0.139, as reported in Sign and Basis Invariant Networks. For scans the problem is worse, because a network would have to learn that a sequence and its reversal carry the same meaning. We include flip augmentation on top of Spectral VMamba as a baseline, run with the same budget.

Why not drop the scan and use a basis-invariant global mixer, such as a spectral filter $V g(\lambda) V^\top$ or GIST-style inner-product attention? Such mixers are invariant and continuous by construction, as the SPE and GIST results show. They also give up the property that makes SSMs attractive, namely input-dependent, order-sensitive recurrence at linear cost. We will test this directly by replacing the scan block with an SPE-style filter of matched FLOPs. If the filter matches our layer, the conclusion is that scan order does not matter once invariance is enforced, and that would be a useful negative result.

Why not just augment standard VMamba with rotations? Augmentation can repair rotation robustness without any spectral machinery. It does not address flip instability under noise, since grid scans have no eigenvectors. It will be run as a baseline on the rotation sweep only.

Proposed Experiments

Classification is evaluated on miniImageNet with clean top-1, accuracy at each 15° rotation, worst-angle accuracy, and cost in FLOPs and latency. Dense prediction is evaluated on ADE20K SceneParse150, reporting mIoU overall and on the images the measurement study flags as having several components. There, per-component scanning should matter most, because scenes with separated objects are common. A synthetic diagnostic set is built from rendered images containing one to four separated, rotationally symmetric shapes, so that multiplicity and disconnection can be controlled exactly. This follows the spirit of the grid-orientation benchmark in Adaptive Canonicalization.

Three checks decide the proposal. First, the output-change curve under shrinking perturbations should show jumps for the static rule and none for the full layer. Second, on the synthetic set, accuracy for the static rule should degrade as symmetry and object count increase, while the full layer's accuracy should stay flat. Third, on real data, any gain beyond bidirectional scanning should be concentrated in the small-gap and multi-component images. If the third check fails while the first two pass, we will report the mechanism as correct but practically irrelevant for natural images.