Vision networks are good at local patterns and bad at relating things that are far apart in the image, such as a shadow and the roof that casts it, or a pole and the road it stands beside. The standard repair is a "relational module," a small block added to a pretrained network that lets every location look at every other location. Its cost grows with the square of the number of pixels, so in practice it runs on downsampled maps and gives up fine detail. Linear recurrences avoid that cost. These are models whose hidden state is updated by a linear rule, which lets the whole sequence be computed in parallel through a prefix-sum tree. Vision state-space models built this way flatten the image into a one-dimensional string, so pixels that touch vertically end up hundreds of steps apart. We propose to stop flattening. The parallel scan already computes over a balanced tree, so we make that tree the image's own multi-scale pyramid. One linear pass climbs from fine to coarse resolution and a second descends, and every pixel receives image-wide context after about $2\log_2 N$ steps with $O(N)$ total work.
The relational part sits in how the tree is built. Each fine-scale location does not belong to one fixed parent. It distributes its state over a small neighborhood of candidate parents, with weights set by appearance similarity and relative geometry, in the manner of the object relation module. Each location also has an input-dependent gate that decides how much it writes into and reads from the hierarchy. The block keeps the shape of its input and adds its output through a zero-initialized residual, so it can be dropped into a pretrained detector or segmenter the way a non-local block is. The core claim is that recurrence over a content-adaptive spatial hierarchy gives full-resolution global relational context at linear cost, without the serialization artifacts of one-dimensional scans or the detail loss of downsampled pairwise attention. A plug-in linear-attention block cannot test this claim, and neither can a plug-in flattened-scan block or a plain feature-pyramid top-down path.
What Prior Work Leaves Open
Relational modules motivate the design and also set its limits. Non-Local Neural Networks compute each output as an affinity-weighted sum over all positions, inside a residual whose output weight starts at zero, which makes the block safe to retrofit. They report a roughly one-point AP gain when a single block is added to Mask R-CNN on COCO. Relation Networks for Object Detection show that appearance alone is not enough. Their pairwise weights combine appearance with log-ratio box geometry, and they report a 2.3-point mAP gain on Faster R-CNN with ResNet-50. Both methods are quadratic, which is why dense users subsample. We reuse the zero-initialized residual from the first paper and the appearance-plus-geometry weighting from the second. We apply them only between a location and a handful of candidate parents, never between all pairs.
Vision state-space models supply the recurrence but not the topology. Resurrecting Recurrent Neural Networks for Long Sequences shows that linear recurrences computed by parallel scans match structured state-space models on long one-dimensional sequences. We borrow its principle: nonlinearity appears only in the gates, never in the state transition.
Several vision papers then fight the flattening problem in different ways.
- VMamba scans four directions.
- Multi-Scale VMamba finds that three of those four scans are nearly redundant. It moves them to downsampled maps, but still runs them as independent one-dimensional scans that are interpolated and added at the end.
- QuadMamba learns a quadtree to vary token density by region, then flattens the leaves into one sequence and discards the parent-child structure during the recurrent pass.
- UIS-Mamba routes the scan along a minimum spanning tree, but at a single resolution.
- DAMamba learns sampling offsets on a flat grid.
- Partial Ring Scan shows that raster scans are brittle under rotation, with drops of 1.5–2.0% at 60° where ring scans stay flat.
All of these are monolithic backbones that must be trained from scratch. In all of them the recurrence still walks a one-dimensional path. In ours the recurrence walks the pyramid itself.
The closest structural precedent comes from NLP. Tree-Structured Attention with Hierarchical Accumulation aggregates bottom-up over parse trees in parallel, but its trees come from an external parser and fixed linguistic structure. Our hierarchy is learned from pixels.
On the multi-scale side, two papers act as constraints rather than inspiration. EfficientViT gets global context in linear time through ReLU linear attention. Its authors concede that linear attention washes out local detail, and they add small depthwise convolutions to compensate. They also report weak single-point-prompt behavior in their SAM variant. SegNeXt argues that multi-scale strip convolutions make attention unnecessary, at the cost of a receptive field bounded by the kernel span. RRNet is the nearest combination of relations and scales. It runs a graph convolution on high-level encoder features and a separate multi-scale attention decoder, so relations and scales never meet in one operator.
Core Claim
Write $x^{(0)}$ for the feature map at the insertion point and $x^{(l)}$ for its average-pooled version at level $l$, each level halving resolution, up to a coarsest level $L \approx \log_2 \sqrt{N}$. The upward pass computes a state $u$ at every node of every level:
$$u_p^{(l+1)} = \sum_{c \in \mathcal{C}(p)} w_{cp}\,\big(a_c \odot u_c^{(l)}\big) + b_p \odot x_p^{(l+1)}$$
The terms are defined as follows.
- $\mathcal{C}(p)$ is the set of fine locations whose $3\times 3$ candidate-parent window contains $p$.
- $w_{cp}$ is a softmax over child $c$'s candidate parents. It scores the projected appearance of $c$ against $p$ and adds a learned function of their relative offset.
- $a_c$ and $b_p$ are input-dependent gates squashed to $(0,1)$, playing the role of a selective state-space model's step size.
The downward pass, $d_c^{(l)} = a'_c \odot \sum_{p} w_{cp}\, d_p^{(l+1)} + u_c^{(l)}$, sends context back to the leaves using the same weights. The block outputs $x^{(0)} + W_z d^{(0)}$, with $W_z$ initialized to zero.
The state update is linear, so all gradients flow through products of gates, as in a linear recurrent unit. Within a level every node updates in parallel. The sequential depth is therefore $2L$, and the work is a geometric series dominated by the finest level, which makes it $O(N)$.
Any two pixels communicate through a path of length about twice the log of their distance. In a raster scan the same path can be as long as $N$. Soft, content-driven parents keep two adjacent pixels on opposite sides of a coarse cell boundary from being forced to meet only near the root.
Research Program
The first phase builds the block. We will write a fused gather-scatter kernel for the $3\times 3$ soft-parent sums and verify that its memory and latency scale linearly with resolution up to full Cityscapes frames. A dense non-local block cannot run at that resolution.
The second phase is analytic and diagnostic. Hierarchies with fixed parents have a known failure: neighbors split by a coarse cell boundary are far apart in the tree. We will measure this directly by plotting segmentation accuracy against each pixel's distance to the nearest level-$l$ cell boundary. The prediction is a sawtooth for a fixed quadtree and a flat curve once parents are soft and relational.
We will also measure effective interaction range. For each method, we compute the gradient of an output pixel with respect to inputs at increasing distance and compare the decay curves of pyramid scan, flattened scans, and linear attention.
The third phase is the retrofit study. We insert the block into pretrained backbones on standard detection and segmentation pipelines, then run the full ablation and robustness program described below.
Baselines
The naive reference is the same pretrained backbone and head fine-tuned with the identical schedule and no added block. Every other number is reported as a gain over this one, because the relational-module literature reports its results the same way.
The strongest existing plug-in relational method is the non-local block of Non-Local Neural Networks. It is the direct competitor on the exact question: what is the best retrofit for global context in a pretrained network? We run it at the stage and subsampling factor the original paper uses, with the same insertion stages and fine-tuning schedule as our block. On COCO with Mask R-CNN its reported effect is a roughly one-point AP gain. Our block counts as beating it if its gain over the naive reference is larger at equal or lower FLOPs. A secondary win is that our block can also run at full resolution, where the non-local block runs out of memory.
For detection, Relation Networks for Object Detection report a 2.3-point mAP gain on Faster R-CNN with ResNet-50. We reproduce it in our codebase and also stack it with our block. The question is whether pixel-level and proposal-level relations add up or substitute for each other.
Two linear-cost plug-in baselines, both of which we construct ourselves, represent the simpler alternatives:
- Linear attention plug-in. A residual block of EfficientViT-style ReLU linear attention with its $3\times3$ and $5\times5$ token aggregation, following EfficientViT.
- Flattened-scan plug-in. A residual block containing an MS3 unit from Multi-Scale VMamba.
No reported result was found on Lacuna for either design used as a retrofit block in a pretrained detector or segmenter. Their numbers will therefore come only from our runs. Each baseline is matched to our block within 10% in parameters and FLOPs, inserted at the same stages, and given the same learning-rate sweep of a few values.
As context, not as a matched comparison, we cite backbone numbers trained from scratch:
| Model | ADE20K mIoU | COCO box AP |
|---|---|---|
| DAMamba-T | 50.3 | 48.5 |
| MSVMamba | 47.9 | 46.9 |
Our retrofit does not need to match these. It needs to beat the matched plug-ins.
The key ablations remove one ingredient at a time:
- Fixed parents: set $w_{cp}$ to the fixed quadtree parent.
- Constant gates: replace $a$, $b$, and $a'$ with learned constants. With both of these changes the block collapses to a gated pyramid-pooling path.
- No geometry: drop the geometry term from $w_{cp}$.
- Upward pass only: remove the downward pass.
Why not just…?
Why not just insert a linear-attention block, which is already global and linear-cost? This is the most serious threat. It may well match our block on mIoU. The evidence against it as a complete answer comes from its own authors: EfficientViT needs extra convolutions to recover local detail and reports weaker fine point-prompt behavior. The distinguishing tests are therefore boundary F-score and accuracy on thin classes such as poles and riders in Cityscapes. If linear attention ties us on those as well, our case rests only on the diagnostics, and we will say so.
Why not just insert an existing vision state-space block such as MS3 or a VMamba unit? Nothing stops a researcher from doing this. The comparison is exactly our flattened-scan plug-in baseline. The specific prediction is that flattened scans show directional bias: accuracy drops under rotation, as Partial Ring Scan documents, and the gradient-decay curves are anisotropic. A pyramid with soft parents has no preferred scan direction. We will run the 60° rotation stress test on all plug-ins.
Why not just use a feature-pyramid top-down path or pyramid pooling, since this looks like one? This is fair. With fixed parents and constant gates our block is essentially that. The constant-gate and fixed-parent ablations exist to settle the question. If they match the full block, the selective and relational parts are not earning their cost, and the honest conclusion becomes "a cheap pyramid path is a sufficient retrofit." The boundary-sawtooth diagnostic is the most direct test of whether soft parents matter.
Why not just use strip-convolution attention as in SegNeXt? SegNeXt is strong. It reports 82.6% Cityscapes mIoU with the full model, but its receptive field ends at the kernel span. We include an MSCA plug-in at matched cost. We expect any advantage of ours to appear on interactions longer than 21 feature cells. The gradient-decay probe and the large-object classes in ADE20K test this.
Proposed Experiments
The main study fine-tunes ImageNet-pretrained ResNet-50 models with and without each plug-in. We use Mask R-CNN on COCO 2017 and report box and mask AP, and segmentation on ADE20K and Cityscapes, reporting mIoU and boundary F-score. Each plug-in is inserted once in stage 3 and once in stage 4 of the backbone. Every configuration is run with three seeds and reported as mean and spread.
We will also profile memory and latency as input resolution grows from 512 to 2048 pixels per side. These curves are where we expect the non-local block to fail and ours to stay linear.
Two smaller settings test the relational claim in regimes chosen for extreme scale variation and long-range dependence:
- EORSSD saliency. Comparison point: RRNet, which reports an F-measure of 0.9119 and MAE of 0.0076.
- Sort-of-CLEVR relational questions. Comparison point: Associative Transformer, which reports 80.03% against 63.35% for ViT-Base.
The decisive checks are three. First, the full block must beat both matched linear-cost plug-ins on boundary-sensitive metrics, not only on mIoU. Second, the fixed-parent and constant-gate ablations must each lose measurably, and the fixed-parent model must show the predicted boundary sawtooth. Third, gains must survive rotation better than the flattened-scan plug-in.
If the first check fails while the other two hold, the block is a better-behaved but not more accurate retrofit. If the second check fails, the result is a simplicity finding about pyramid paths, and we will report it as such.
References
- Non-Local Neural Networks
- Relation Networks for Object Detection
- Resurrecting Recurrent Neural Networks for Long Sequences
- VMamba: Visual State Space Model
- Multi-Scale VMamba: Hierarchy in Hierarchy Visual State Space Model
- QuadMamba: Learning Quadtree-based Selective Scan for Visual State Space Model
- UIS-Mamba: Exploring Mamba for Underwater Instance Segmentation via Dynamic Tree Scan and Hidden State Weaken
- DAMamba: Vision State Space Model with Dynamic Adaptive Scan
- Partial Ring Scan: Revisiting Scan Order in Vision State Space Models
- Tree-Structured Attention with Hierarchical Accumulation
- EfficientViT: Multi-Scale Linear Attention for High-Resolution Dense Prediction
- SegNeXt: Rethinking Convolutional Attention Design for Semantic Segmentation
- RRNet: Relational Reasoning Network With Parallel Multiscale Attention for Salient Object Detection in Optical Remote Sensing Images
- Associative Transformer