Which Queries Need to See Each Other? Sub-Quadratic Query Interaction That Keeps One-to-One Matching Stable

Detectors in the DETR family, which predict a fixed-size set of boxes from learned "query" vectors and train by pairing each prediction with at most one ground-truth object through bipartite matching, have no hand-written duplicate removal step. Something inside the network has to learn that two queries looking at the same person should not both fire. The usual suspect is the self-attention among queries in the decoder: every query compares itself with every other query, which costs time and memory quadratic in the number of queries. That cost is negligible at 300 queries on COCO. It stops being negligible in crowded scenes and in the stabilization tricks that multiply query counts during training, and those are exactly the settings where the matching between predictions and targets is least stable. This note proposes to test a specific claim. The quadratic query-to-query comparison exists mainly to settle competition between queries that want the same target, so it can be replaced by sparse attention restricted to each query's likely competitors. Generic linear-time sequence mixers, by contrast, will damage duplicate suppression and show up as more matching flips during training.

The work has two parts. The first is a diagnostic. In a fixed detector, we swap the query-interaction operator among full softmax attention, linear attention, a state space model, a structured-matrix mixer, and spatially local attention, and measure assignment churn and duplicate rates directly. The second is a method. Each query attends to its top-$k$ competitors, ranked by the same pairwise cost the Hungarian matcher uses. This gives an $O(Mk)$ operator for $M$ queries, and we evaluate whether it lets dense-query, multi-group training scale on CrowdHuman without the instability that generic sub-quadratic replacements introduce.

Core Claim

Bipartite matching instability, meaning queries switching which target they are assigned to from one training step to the next, has been treated as a property of the label-assignment step. Query denoising (DN-DETR), group-wise one-to-many matching (Group DETR), collaborative auxiliary heads (Co-DETR), cross-stage label propagation (StageInteractor), and fractional transport plans (RTP-DETR) all modify supervision and leave the decoder's query interaction untouched.

Our claim is that instability also depends on how well queries can resolve competition among themselves. An operator that cannot represent sharp pairwise "you take this one, I back off" decisions forces the matcher to arbitrate between near-identical predictions. Arbitrating between near-ties is where small gradient updates flip assignments. Kernelized linear attention approximates the softmax comparison with a low-rank feature map. A state space model compresses all other queries into a fixed-size state along an arbitrary scan order. We hypothesize that both blur exactly these near-tie comparisons.

Competition is also sparse. A query can only duplicate another query whose predicted box and class are close in matching cost. So an operator that gives each query exact softmax attention over a small, cost-defined neighbor set should keep duplicate suppression intact at linear cost.

Concretely, at decoder layer $\ell$ we define the competitor set of query $i$ as

$$\mathcal{N}_\ell(i) = \text{top-}k_{\,j \neq i}\;\big[-\,C(\hat{y}_i^{\ell-1}, \hat{y}_j^{\ell-1})\big],$$

where $\hat{y}_i^{\ell-1}$ is query $i$'s box and class prediction from the previous layer. $C$ is the Hungarian matching cost evaluated between two predictions instead of between a prediction and a target, combining class-probability similarity, L1 box distance, and generalized IoU. Self-attention for query $i$ runs over $\mathcal{N}_\ell(i)$ plus a handful of shared global summary tokens for scene context. Candidate pairs come from a grid hash on box centers, so building the sets stays near-linear in $M$.

Relation to Prior Work

Three groups of papers frame the question.

The first group motivates the gap. It reduces quadratic cost in DETR-style models but never examines matching. Deformable DETR samples four points per query over multi-scale features. It linearizes cross-attention to image tokens but keeps full query self-attention and plain Hungarian matching. Lite DETR interleaves encoder updates to cut encoder cost by 62–78% and does not touch the decoder. DEST turns the 3D detection decoder into an interactive state space model over Hilbert-serialized points. MambaDETR uses Mamba for temporal query modeling. Both inherit their label assignment unchanged and never measure assignment churn. Our diagnostic asks the question these papers skipped: does linearizing the decoder change matching stability?

The second group supplies the method. DETR for Pedestrian Detection (PED) already uses local self-attention among dense queries to avoid memory blow-up on CrowdHuman, and restricts Kuhn-Munkres matching to nearby proposals. That is the closest existing design. We differ in three ways. Neighborhoods are defined in matching-cost space, which includes class and box shape, rather than by spatial proximity alone. Neighborhoods are recomputed per layer from the previous layer's predictions. And the question is explicitly whether the neighborhood definition affects instability, which PED does not measure. If cost-defined neighbors turn out no better than spatial ones, the result is a measured confirmation that PED's design choice was sound, and the contribution reduces to the diagnostic and the scaling study. We state that up front.

The third group constrains the design. Lee et al. show that Mamba matches Transformers on synthetic associative recall and in-context regression. That is a fair warning that state space models may handle query competition better than we expect. The diagnostic is built so that this outcome would be clearly visible. Deformable DETR's own observation that irregular memory access erodes wall-clock gains constrains us too. Gathering $k$ neighbors per query is also irregular access, so we report latency, not only FLOPs. Monarch Mixer offers the hardware-friendly alternative, a dense structured-matrix mixer at $O(n^{1.5})$. We include it as a competitor because, if it holds stability, it would be preferable on hardware grounds.

Research Program

Shared testbed. We build a single DN-Deformable-DETR codebase in which only the decoder's query-interaction block is swappable. Encoder, backbone, matching, losses and schedule stay fixed. Query denoising stays on throughout, so we test whether query interaction affects instability beyond what denoising already removes.

Instrumentation. Every few hundred iterations we log three quantities on a fixed probe set of training images:

  • the DN-DETR instability metric, which counts how many queries change their assigned target between consecutive checkpoints;
  • the same count across decoder layers within one forward pass, the oscillation StageInteractor targets;
  • a duplicate rate, defined as the number of same-class prediction pairs with IoU above 0.7 that both score above 0.3, per ground-truth object.

Analysis. The duplicate rate is the bridge between the two directions. Our hypothesis predicts that operators with higher duplicate rates show higher churn, and that the relationship should be strongest in crowded images. We test this by binning probe images by the number of ground-truth boxes with pairwise IoU above 0.5, using the overlap statistic CrowdHuman reports at 2.4 per image on average.

Method. We then implement competitor-routed attention and scale the query regime on CrowdHuman. Query counts go from 300 to roughly 3000, combined with Group DETR-style training groups. The scaling comparison is against full attention, which runs out of memory or slows sharply, and against the generic sub-quadratic mixers, which we predict lose matching stability. A secondary extension reuses the competitor graph to sparsify the matcher. Hungarian edges are restricted to each target's cost-nearest predictions, with a fallback to full matching whenever the sparse graph lacks a perfect matching. This avoids the early-training fragility of PED's fixed distance thresholds.

Baselines

Naive reference. The naive reference is DN-Deformable-DETR with unchanged full softmax query self-attention (DN-DETR), which reports 48.6 AP on COCO at 50 epochs. At standard query counts this is the accuracy and stability ceiling for any cheaper operator. A method "beats" it only in the dense regime: it must match its instability metric and AP within noise at 300 queries while using less memory at 3000 queries. Alongside it we run a deliberately weak floor, query self-attention removed entirely. This tells us how much duplicate suppression the attention actually provides in a modern denoised detector.

Strongest existing crowded-scene method. This is PED (DETR for Pedestrian Detection), which reports 89.54% AP and 45.57% $MR^{-2}$ on CrowdHuman, against 86.74% AP and 53.98% $MR^{-2}$ for Deformable DETR. We will rerun PED's local dense-query attention inside our testbed, with the same backbone, epochs, query count, and hyperparameter search budget of a fixed number of trials per method. That isolates the attention design from its other components, rectified attention fields and Fast-KM, which we also report separately. Beating PED means lower $MR^{-2}$ and a lower instability metric at equal memory, or equal accuracy at substantially lower memory at the highest query counts.

Generic sub-quadratic mixers. These are the direct competitors on the efficiency axis:

Each receives the same tuning budget. We found no reported matching-instability or CrowdHuman result on Lacuna for any of them used as a query mixer.

Stabilization reference. To show the effect is not simply something supervision fixes, we also run Group DETR-style group training (Group DETR) on top of every operator. Group DETR reports +3.9 mAP over DAB-DETR at 12 epochs.

Key-ingredient ablation. The ablation that isolates our contribution keeps everything identical except the neighbor definition. It compares cost-ranked neighbors, pure spatial $k$-nearest box centers, and random neighbors of the same $k$. The global summary tokens are ablated separately.

Why not just…?

Why not just keep full softmax query attention, since 300 queries are cheap? On COCO at standard query counts this is correct, and we do not claim an efficiency win there. There, the contribution is the diagnostic. The case for a cheaper operator rests entirely on the dense regime: thousands of queries for crowds, multiplied by training groups. The scaling curve of memory and latency against query count on CrowdHuman will show whether that regime actually hits a wall for full attention on our hardware. If it does not, the method part of the proposal is unnecessary and we will say so.

Why not just use PED's spatially local query attention? This is the real threat. Spatial locality may capture nearly all of the competition structure, because duplicates mostly overlap spatially. Our bet is that cost-space neighbors matter when objects of different classes or very different shapes overlap, and early in training when boxes are poorly localized. The neighbor-definition ablation, broken down by training epoch and by crowding bin, settles this directly. If spatial and cost neighbors tie, we adopt the simpler spatial version and report the tie.

Why not just drop in Mamba or linear attention, as DEST and MambaDETR did successfully? Those successes measured final accuracy, not assignment churn. Lee et al. suggest state space models can do associative matching well, so our hypothesis may be wrong. The diagnostic decides it. If the state space mixer shows churn and duplicate rates comparable to softmax attention in crowded images, generic sub-quadratic mixers are adequate and the routed operator is not needed.

Why not just add NMS after a cheap decoder? That gives up the end-to-end property that motivates DETR. It is still a useful probe, though. If NMS recovers most of the AP gap between linear mixers and full attention, the gap is caused by duplicates, which supports our mechanism even as it shows a non-end-to-end workaround exists.

Decisive Experiments

Diagnostic. On COCO 2017 with ResNet-50 and 12- and 50-epoch schedules, and on CrowdHuman, we run all query-interaction operators with denoising on. We report AP and $AP_S$ on COCO; AP and $MR^{-2}$ on CrowdHuman, plus heavy-occlusion $MR^{-2}$ on CityPersons; the instability metric over training; per-layer oscillation; and duplicate rate. The hypothesis is falsified if linear attention and the state space mixer show no increase in instability or duplicates relative to softmax attention in the most crowded bin.

Scaling. On CrowdHuman we sweep query count and group count, recording peak training memory, iteration time, and $MR^{-2}$. Competitor-routed attention must hold accuracy and stability where full attention becomes infeasible, and must beat the generic mixers on instability at equal memory.

Transfer. We check transfer to a different matching-heavy regime by applying the operator to the query decoder on ScanNet V2. There, DEST reports 67.9 $mAP_{50}$, and dense point inputs make query-scene cost dominant. This tests whether the competition argument holds outside 2D crowds.