Multi-Hypothesis Window Attention for Fine-Grid Dense Matching

Dense image matching finds, for every pixel in one photo, the corresponding pixel in another photo of the same scene. The strongest current matchers do this without a keypoint detector (a module that picks out corners or edges). Instead they compare features laid out on a regular grid, so blank walls, sky, and repetitive tiles still get matched. The price is cost. A grid of $N$ cells makes all-pairs comparison between two images scale as $N^2$. Today's systems therefore do their reasoning on a coarse grid at 1/8 resolution and then fix up each match inside a small fixed window, or they replace exact attention with a cheaper "linear" approximation. Language-model research has shown that the linear approximation blurs exactly the sharp, single-location attention that matching needs.

We propose to make global, context-aware matching affordable at a finer grid (1/4 resolution) with a hybrid attention layer built for two-view correspondence. A cheap global stage proposes a few candidate locations in the other image for each pixel. Exact attention then runs only inside small windows around those candidates, alongside a compact linear-attention summary of the whole image for context. The bet is that keeping several hypotheses alive at a fine resolution fixes two failures together. Coarse-to-fine pipelines cannot recover from a wrong coarse match. Linear attention smears sharp correspondence peaks.

Core Claim

Cross-attention between two images is a retrieval problem. Each query pixel must put nearly all its attention on one location, or on a few locations when the texture repeats. Sequence-modeling work explains why the two cheap options fail. Simple linear attention language models balance the recall-throughput tradeoff and LoLCATs show that linear attention compresses context into a fixed-size state and cannot represent spiky attention, which hurts exact recall. A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention proves that block-sparse (purely local) attention is strictly weaker than full attention on global pairwise search. These papers constrain the design. Candidate generation must be genuinely global, and the final match must use exact softmax over a small set.

Our claim is that a layer built on these constraints can operate at 1/4 resolution with cost close to that of linear attention. It has three parts:

  1. Low-resolution full attention proposes the top-$k$ modes.
  2. Exact softmax attention runs over $k$ windows of $w \times w$ cells at the fine grid.
  3. A separately normalized linear global stream supplies context.

The claim is that this layer beats the standard alternative, full attention at 1/8 followed by single-window refinement, on pose accuracy and on recovering from coarse errors. The per-layer cost is roughly

$$C \approx N_c^2 + N\,k\,w^2 + N d^2,$$

where $N_c$ is the number of cells in the pooled coarse grid, $N$ the number of fine-grid cells, and $d$ the feature width. The last term is the linear stream. With $k$ and $w$ small, the fine-grid term grows linearly in $N$.

Relation to Prior Work

Three matchers motivate this design.

  • LoFTR applies linear-attention self- and cross-attention on a 1/8 grid. It then refines each coarse match by correlation in one fixed window at 1/2 resolution, with no attention at the fine level.
  • ASpanFormer centers one attention window on a predicted flow and widens it where uncertainty is high. Its own limitation is that an error in that single flow estimate cannot be corrected, and it keeps no persistent global state.
  • MatchFormer interleaves attention inside the backbone. It uses separate efficient-attention variants for indoor and outdoor scenes.

Our layer differs from all three in one way. It keeps $k>1$ spatially separate hypotheses through the fine-grid attention, so the true match only needs to be among the top-$k$ coarse modes rather than at the top-1.

Two papers supply methods we reuse.

  • Long-Short Transformer combines a sliding-window stream with a low-rank global stream inside one layer, and it introduces dual normalization (separate LayerNorms per stream) to stop local features from drowning out the global ones. It was tested on classification and language, never on two-view cross-attention.
  • Rope to Nope and Back Again warns that normalizing queries and keys flattens attention and hurts needle retrieval.

Together these define a tension we test directly: does dual normalization of the two streams flatten the correspondence peaks?

RoMa is the strongest matcher in the file and plays a different role. It handles multimodality with regression-by-classification over anchor grids, on top of frozen DINOv2 features and standard attention. Our layer is a candidate drop-in for its decoder attention, not a replacement for its backbone.

Research Program

We will build the layer and use it for both self- and cross-attention at a 1/4 grid. Self-attention uses a sliding window plus the linear global stream, in the style of BASED. Cross-attention uses the multi-hypothesis windows. Hypotheses come from full softmax cross-attention on a 1/16 pooled grid. We take the $k$ highest non-adjacent peaks after non-maximum suppression and sweep $k \in \{1,2,4,8\}$ and $w \in \{3,5,7\}$. A shared softmax over all $k$ windows produces the output, so mass can move between hypotheses. A regression-by-classification head over the union of windows, borrowed from RoMa, gives the final match.

Two diagnostics come out of the language-model literature.

  1. Coarse top-$k$ recall. This is the fraction of ground-truth correspondences whose true location falls inside one of the $k$ windows. It measures directly whether multiple hypotheses rescue coarse failures.
  2. Correspondence attention mass. This is the share of each query's cross-attention weight within $r$ cells of the true match. It is a dense-matching analogue of associative-recall probes, and it lets us check whether linear attention blurs peaks in vision as it does in language.

A secondary, low-cost ablation tests the positional-encoding split reported in Rope to Nope. It gives position information only to the window branch and none to the global branch.

Baselines

Naive reference. LoFTR as published, with linear attention at 1/8 and single-window refinement, retrained in our pipeline. It reports 22.06% AUC@5° on ScanNet, 52.8% AUC@5° on MegaDepth, and 65.9% AUC at 3px on HPatches. This shows how far the hypothesis-window layer moves a pipeline built on linear attention.

Strongest controlled baseline. The same backbone and decoder with exact full softmax attention at 1/8, computed with a memory-efficient attention kernel, followed by LoFTR-style fine refinement. This is the competitor a reviewer would actually propose, because at 1/8 on 640×480 inputs full attention is affordable. It shares our backbone, training data (MegaDepth and ScanNet), schedule, and hyperparameter search budget. Beating it means higher AUC@5° on both ScanNet and MegaDepth at equal or lower peak memory, plus a measurable gain on the subset of pairs where its coarse top-1 match is wrong.

Strongest published method in the same training regime. ASpanFormer, reported at 25.6% AUC@5° on ScanNet and 55.3% on MegaDepth, with 113.5 ms against LoFTR's 97.7 ms on a V100. We retrain it with our backbone and compute budget. Beating it requires exceeding both AUC numbers at latency no worse than its 113.5 ms.

Overall strongest matcher. RoMa, reported at 80.1 mAA on WxBS and 88.0 mAA on IMC2022. We do not claim to beat RoMa outright. Instead we swap our layer into RoMa's decoder at a finer anchor grid, keep its DINOv2 and VGG19 features and training recipe, and ask two questions. Does the swap raise WxBS mAA above the published 80.1? Does it reduce memory at matched resolution?

Downstream stress test. On AIMS, the EarthMatch pipeline with RoMa localizes 93% of localizable queries, and the Steerers model reaches 90.6%. We run EarthMatch with our variant swapped in.

Ablations isolating the key ingredient. Four ablations, each compared against the full layer:

  • $k=1$, which is effectively ASpanFormer-style single-window attention at the fine grid.
  • No linear global stream.
  • A single shared LayerNorm instead of dual normalization.
  • Pure linear attention at 1/4.

Why not just…?

Why not just use full attention at 1/8 and refine locally? This is the real threat. If coarse full attention already captures global context, the fine grid may add little. The open weakness is error propagation. ASpanFormer itself notes that fine precision depends entirely on the coarse match. Our coarse top-$k$ recall measurement settles the question. If top-1 recall at 1/8 is already close to top-4 recall, the multi-hypothesis mechanism has nothing to rescue. In that case we will report that coarse-to-fine refinement suffices and drop the claim.

Why not just use ASpanFormer's adaptive span? An adaptive span is still one window around one flow estimate. On repetitive textures the flow can lock onto the wrong repeat, and enlarging the span only dilutes attention. The $k=1$ ablation against $k=4$ on ScanNet, whose repetitive and textureless scenes are exactly this hard case, tests whether separate hypotheses beat one large adaptive window.

Why not just use linear attention everywhere at the finer grid? Language-model evidence says this loses recall. BASED reports a 10.36-point recall gap between its hybrid and pure Mamba at 1.3B scale. Whether the same holds for pixel correspondence is an empirical question. The pure-linear ablation and the attention-mass diagnostic test it directly. If linear attention concentrates mass as well as exact attention does, the hybrid is unnecessary.

Why not just use sparse keypoints with cheap exact attention? LoFTR's reported ScanNet gain over SuperGlue, 22.06% against 16.16% AUC@5°, shows that sparse detection fails exactly where dense matching matters. We do not revisit that comparison.

Decisive Checks

The proposal stands or falls on three results, all against the controlled full-attention-at-1/8 baseline.

  1. On ScanNet and MegaDepth, AUC@5° is higher at matched memory.
  2. The gain concentrates on pairs where the coarse top-1 match was wrong but the true match was in the top-$k$.
  3. Correspondence attention mass under our layer matches that of exact attention, while pure linear attention at 1/4 is measurably lower.

We will also report HPatches AUC at 3px, WxBS and IMC2022 mAA for the RoMa swap, AIMS localization rate, latency, and peak memory. If the first check fails, the result is still useful: it would show that hybrid local-global attention offers dense matching only an efficiency benefit, not an accuracy benefit.