💻 computer science

Can Graphs Help Vision SSMs See Better?

The paper introduces GraphScan, a graph-induced dynamic scanning operator that enhances Vision State Space Models by replacing geometric serialization with feature-conditioned semantic routing, achieving state-of-the-art performance across various vision tasks while maintaining linear computational scaling.

Original authors: Dhruv Parikh, Anvitha Ramachandran, Haoyang Fan, Mustafa Munir, Rajgopal Kannan, Viktor Prasanna

Published 2026-05-13

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Dhruv Parikh, Anvitha Ramachandran, Haoyang Fan, Mustafa Munir, Rajgopal Kannan, Viktor Prasanna

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a complex picture, like a painting of a busy city street. You have a very fast, efficient brain (called a Vision State Space Model or Vision SSM) that is great at processing information in a straight line, one piece at a time.

However, there's a problem: the picture is two-dimensional (it has height and width), but your brain only understands a one-dimensional list (like a sentence). To make the picture fit, you have to flatten it into a long line of tiny squares (tokens), like unrolling a carpet.

The Old Way: The "Mow the Lawn" Problem

Traditionally, to turn the picture into a line, researchers used a fixed scanning pattern.

The Raster Scan: Imagine a lawnmower going back and forth across a lawn. It moves left-to-right, drops down, moves right-to-left, and so on.
The Issue: In a picture, a square right next to another square might be far apart in the "mowed" line. If you are looking at a cat's ear and its nose, a fixed scanner might put them miles apart in the list. The brain has to wait a long time to connect them, or it might miss the connection entirely because it's just following a rigid path.

Some newer methods tried to fix this by deforming the path. Imagine the lawnmower driver getting smart and saying, "Hey, that patch of grass looks like a flower, so I'll jump over here to cut it first." This is called coordinate-offset scanning. It's better, but it's still mostly about geometry (moving to a new coordinate) rather than meaning (understanding what the patch actually is).

The New Idea: GraphScan (The "Smart Neighborhood" Approach)

The authors of this paper asked a simple question: "What if, before we feed the picture to the brain, we let the squares talk to their neighbors based on what they look like, not just where they are?"

They introduced GraphScan. Here is how it works using a simple analogy:

The Neighborhood Meeting: Instead of just moving a lawnmower, imagine every square in the picture holds a tiny neighborhood meeting.
Semantic Chat: Each square looks at the squares immediately around it. But instead of just saying, "You are to my left," they ask, "Do we look similar? Are we part of the same object?"
- If a square is part of a "dog's fur," it will strongly connect with other "fur" squares nearby, even if the geometry is tricky.
- If a square is part of a "sky," it connects with other "sky" squares.
The Message: The square gathers the best information from this chat, mixes it together, and updates its own "opinion" of what it is.
The Handoff: Now that every square has a better, more informed understanding of its local neighborhood, it gets passed to the fast brain (the Vision SSM) to be processed in the long line.

Why This is a Big Deal

The paper claims that this simple change makes the AI "see" much better.

It's not a replacement: They didn't replace the fast brain with a slow, complicated graph machine. They just added a "preparation step" right before the brain starts working.
It's local and smart: It doesn't look at the whole picture at once (which is slow). It only looks at a small, bounded neighborhood (like a 3x3 or 5x5 grid), but it decides who to listen to based on the content (semantics), not just the grid position.
The Result: When they tested this new "GraphScan-Mamba" on standard tasks like:
- Identifying images (ImageNet): It got higher scores than previous models.
- Finding objects (COCO detection): It found cars, people, and animals more accurately.
- Segmenting scenes (ADE20K): It did a better job of coloring in the exact shape of objects.

The Takeaway

The paper concludes that we shouldn't just think about scanning an image as a geometric puzzle (how do I arrange these tiles in a line?). Instead, we should treat it as a semantic routing problem (how do I let these tiles share information about what they are before they get organized?).

By letting the image patches "chat" with their neighbors to build a better local understanding, the Vision SSM gets a much clearer, more meaningful list to process, leading to smarter and more accurate computer vision.

Technical Summary: GraphScan for Vision State Space Models

1. Problem Statement

Vision State Space Models (SSMs), particularly those based on the Mamba architecture, offer efficient long-range modeling with linear complexity. However, their performance critically depends on how two-dimensional visual feature maps are serialized into one-dimensional token sequences for processing.

Existing scanning operators in Vision SSMs generally fall into two categories:

Fixed Geometric Traversals: Predefined paths (e.g., raster, bidirectional, fractal) that serialize the 2D lattice into a 1D sequence. These expose the model to fixed orderings that may not align with semantic content.
Dynamic Coordinate-Based Scans: Methods that predict offsets or sampling locations and reroute tokens via interpolation (e.g., bilinear interpolation). While adaptive, these primarily adjust where to sample based on geometry rather than explicitly modeling which local patches should exchange information based on semantic relevance before global mixing.

The authors identify a gap: current mechanisms adapt paths or sampling coordinates but do not explicitly model local semantic neighborhoods to precondition tokens before they enter the selective state-space mixer. The central question posed is whether graph-based routing can help Vision SSMs "see better" by establishing semantic connections before global propagation.

2. Methodology: GraphScan

The paper introduces GraphScan, a graph-induced dynamic scanning operator designed to precede the selective SSM. Unlike methods that replace the SSM with a Graph Neural Network (GNN), GraphScan acts as a lightweight, input-adaptive preconditioner that enriches tokens with local semantic context.

Core Mechanism

For each token $x_i$ in the feature map:

Local Graph Construction: A spatially bounded local candidate set $S_r(i)$ is defined around the token's lattice coordinate, with a fixed radius $r$ .
Feature-Conditioned Affinities: Instead of geometric interpolation, GraphScan computes attention-like affinities between the query token and its neighbors based on feature similarity and relative positional bias.
- Query, Key, and Value projections are computed: $q_i, k_j, v_j$ .
- Affinity scores $s_{ij}$ are calculated using dot products and a learnable relative positional bias $b_{rel}(g_j - g_i)$ .
- Softmax normalization yields weights $\alpha_{ij}$ .
One-Step Message Passing: The output token $x'_i$ is generated by aggregating value features from the semantic neighborhood and adding a residual connection:
$x'_i = x_i + \left( \sum_{j \in S_r(i)} \alpha_{ij} v_j \right) W_o$
This replaces the isolated patch representation with a semantic mixture of nearby visual evidence.

Integration into Backbone

GraphScan is integrated into a hierarchical Vision Mamba backbone (GraphScan-Mamba) as a pre-SSM routing layer.

Architecture: The backbone follows a standard four-stage design with overlapping convolutional stems and stage-wise downsampling.
Placement: Within each block, the flow is: Depthwise Conv (Fixed Local) $\to$ GraphScan (Learned Local) $\to$ Selective SSM (Global).
Adaptivity: The graph radius $r$ increases with stage depth (e.g., $r=1$ in early stages, $r=3$ in later stages), allowing the receptive field to grow from local to effectively global while maintaining linear scaling.

Theoretical Implications

The authors analyze GraphScan as a sparse, input-adaptive preconditioner. By modifying the token sequence $X$ to $X'$ before the SSM, GraphScan influences the SSM in two ways:

Value Injection: It changes the values written into the recurrent state.
Parameter Modulation: Since Mamba-style SSMs generate recurrence parameters ( $\Delta, B, C$ ) from the current token, changing the token also changes the selective parameters governing state propagation and readout.
This creates a "local-global kernel" where a source patch influences the output through a local semantic affinity $\alpha_{ij}$ and a global selective propagation factor $K'_{t,i}$ .

3. Key Contributions

GraphScan Operator: A novel scanning mechanism that treats scanning as "learned local semantic routing" rather than geometric serialization or coordinate selection. It preserves token count and linear scaling while introducing semantic awareness.
GraphScan-Mamba Backbone: A hierarchical implementation of GraphScan that achieves state-of-the-art (SOTA) performance among Vision SSMs across multiple tasks without altering the core SSM recurrence logic.
Orthogonality: The method is shown to be orthogonal to recurrence-side improvements (e.g., SSD, non-causal formulations), offering a complementary design lever for Vision SSMs.
Interpretability: The method induces interpretable displacement fields over the token lattice, visualizing how the model routes information based on semantic content rather than fixed geometry.

4. Experimental Results

The authors evaluate GraphScan-Mamba on three standard benchmarks, comparing against ConvNets, Transformers, and existing Vision SSMs (e.g., VMamba, DAMamba, Spatial-Mamba) at comparable parameter and FLOP budgets.

ImageNet-1K Classification:
- GraphScan-Mamba-B achieves 86.5% top-1 accuracy, outperforming the strongest Vision SSM baseline (Spatial-Mamba-B at 85.3%) by +1.2% and VMamba-B by +2.6%.
- It also surpasses strong ConvNet and Transformer backbones (e.g., ConvNeXt-B, Swin-B) at similar scales.
COCO Object Detection & Instance Segmentation (Mask R-CNN):
- Under the 1x schedule, GraphScan-Mamba-B reaches 51.9 box mAP and 46.0 mask mAP, leading all Vision SSM baselines.
- Gains transfer effectively to dense prediction tasks, indicating the learned tokens are robust to detection-scale spatial structures.
ADE20K Semantic Segmentation (UperNet):
- GraphScan-Mamba-B achieves 53.2% mIoU (single-scale), surpassing the best Vision SSM baseline (DAMamba-B at 51.9%) by +1.3%.
- Multi-scale results show consistent improvements (53.6% vs 52.3%).

Ablation Studies:

Placement: Pre-SSM placement is critical; moving GraphScan post-SSM results in a 0.7% drop in accuracy.
Radius Schedule: A growing radius schedule $(1, 1, 2, 3)$ offers the best Pareto front between compute and accuracy.
Relative Position Bias: Including a learnable relative positional bias provides a consistent, albeit small, gain.

5. Significance and Claims

The paper concludes that graphs do help Vision SSMs see better. The significance of this work lies in shifting the design paradigm for Vision SSMs:

From Geometry to Semantics: Scanning should not be treated merely as geometric serialization (choosing a path or coordinate) but as learned local semantic routing before global state-space modeling.
Input-Side Complement: GraphScan provides an input-side solution that complements recurrence-side advances. It ensures that the tokens entering the selective mixer are already locally grounded and semantically aware, improving the conditioning of the global sequence without changing the SSM's internal dynamics.
Generalizability: The approach is orthogonal to the specific SSM core (e.g., Mamba-1/S6), suggesting it can be applied to future SSM variants.

The authors modestly claim that while GraphScan improves performance and interpretability, it does not guarantee generalization in a formal control-theoretic sense without further assumptions, but it provides a structural mechanism for richer local semantic inputs.