DETR

The proposal/anchor paradigm and its accumulated complexity:

Every major object detector before DETR generates a massive number of candidate detections, then filters them down:

Faster R-CNN's proposal pipeline:

• Backbone produces features at 5 FPN levels (P2-P6)
• At each of ~200K spatial positions, 3 anchor ratios are evaluated
• RPN predicts objectness + box offsets for each of ~200K anchors
• NMS reduces to ~1000 proposals (IoU threshold 0.7)
• Stage 2 classifies and refines ~300 proposals
• Final NMS (IoU threshold 0.5) produces ~100 detections
• Hand-designed hyperparameters: anchor sizes (32, 64, 128, 256, 512), aspect ratios (0.5, 1.0, 2.0), NMS IoU thresholds (0.7 for RPN, 0.5 for final), positive/negative IoU thresholds (0.3/0.7), proposal counts (1000/300), score thresholds

Single-stage detectors (YOLO, SSD, RetinaNet):

• Dense anchors at every spatial position across multiple scales
• RetinaNet: 9 anchors per position x 5 levels = ~100K anchors for a 600x800 image
• Focal loss to handle extreme foreground/background imbalance (99.9% of anchors are background)
• NMS remains mandatory to remove duplicate detections

The fundamental problems:

1. NMS is non-differentiable: It is a hard selection operation that cannot be optimized during training. The model learns to produce overlapping detections, then relies on a separate heuristic to remove them.
2. Anchor design requires domain knowledge: The choice of anchor scales, ratios, and assignment thresholds significantly affects performance. RetinaNet's 9 anchor templates were tuned on COCO; different datasets may need different anchors.
3. No global reasoning about duplicate suppression: Each anchor/proposal is processed independently. The model has no mechanism to "know" that another anchor is already detecting the same object. NMS is a post-hoc fix for this lack of global coordination.
4. Two-stage overhead: RPN + NMS + RoIAlign + second-stage NMS adds both compute and engineering complexity. Each component has its own hyperparameters and failure modes.
5. Arbitrary prediction ordering: Detections are ordered by confidence score, which has no semantic meaning. There is no principled connection between the set of predicted objects and the set of ground-truth objects.

Object queries: N=100 learnable embeddings that directly produce the detection set:

DETR replaces the entire anchor/proposal/NMS pipeline with 100 learned vectors, each of dimension $d = 256$:

$Q = \{q_1, q_2, ..., q_{100}\} \in \mathbb{R}^{100 \times 256}$

These are randomly initialized and learned via backpropagation, just like any other network parameter. They are the only input to the decoder (besides the encoded image features).

How object queries work through the decoder:

Each of the 6 decoder layers performs three operations:

1. Self-attention among queries (queries reason about each other): $Q' = \text{MultiHeadSelfAttn}(Q + PE_q, Q + PE_q, Q)$

This is the key to NMS-free detection: queries can "see" what other queries are predicting and learn to avoid duplicates. If query 7 is already detecting a dog, query 23 learns (through self-attention) to detect a different object or output $\varnothing$.

2. Cross-attention to image features (queries look at the image): $Q'' = \text{MultiHeadCrossAttn}(Q' + PE_q, F_{enc} + PE_{2D}, F_{enc})$

where $F_{enc} \in \mathbb{R}^{HW \times 256}$ is the encoder output (850 tokens for a typical COCO image) and $PE_{2D}$ is the 2D positional encoding. Each query attends to all spatial positions and learns to focus on regions relevant to its predicted object.

3. FFN refinement (per-query feature refinement): $Q''' = \text{FFN}(Q'') = W_2 \cdot \text{ReLU}(W_1 \cdot Q'' + b_1) + b_2$

where the FFN has hidden dimension 2048 (8x expansion from $d = 256$).

After 6 decoder layers, each query $q_i$ produces a 256-dim output embedding that is fed to two parallel prediction heads:

$\hat{c}_i = \text{Linear}_{256 \rightarrow 92}(q_i^{(6)}) \quad \text{(class logits: 91 COCO classes + } \varnothing\text{)}$ $\hat{b}_i = \text{Sigmoid}(\text{MLP}_{256 \rightarrow 256 \rightarrow 256 \rightarrow 4}(q_i^{(6)})) \quad \text{(normalized box: } (x_c, y_c, w, h) \in [0,1]^4\text{)}$

Why N=100?

COCO images contain at most ~63 annotated objects (the maximum in the dataset). Setting N=100 provides comfortable headroom. The authors tested:

• N=50: 40.8 AP (some images with many objects lose detections)
• N=100: 42.0 AP (optimal)
• N=200: 41.8 AP (more unmatched queries provide weaker supervision signal per matched query)
• N=300: 41.5 AP (training becomes harder with many $\varnothing$ targets)

Query specialization (emergent behavior):

Despite having no explicit spatial initialization, trained queries develop clear specialization:

• Certain queries consistently detect objects in the bottom-left of images
• Other queries specialize in large objects (cars, buses) while others focus on small objects (bottles, cups)
• Some queries learn to detect specific object categories preferentially
• This specialization emerges purely from the set-based loss and cross-attention mechanism -- no hand-designed assignment rules

No NMS needed because:

1. Self-attention allows queries to coordinate and avoid duplicate detections
2. The Hungarian matching loss assigns each GT object to exactly one query, so the model is never rewarded for predicting the same object twice
3. Unmatched queries learn to output $\varnothing$ with high confidence, producing clean output without filtering

The assignment problem: connecting predictions to ground truth

With N=100 predictions and M ground-truth objects (typically M=5-15 for COCO images, always $M \leq N$):

• There are $N!/(N-M)!$ possible assignments of predictions to GT objects -- for N=100 and M=10, that is approximately $10^{20}$ possibilities
• Some predictions should match objects, the remaining N-M should predict "no object" ($\varnothing$)
• The loss function must automatically determine which prediction is responsible for which GT object
• Crucially: the assignment must be one-to-one (each GT matches exactly one prediction) to avoid duplicate detection

How traditional detectors handle assignment (and why it is suboptimal):

Faster R-CNN (IoU-threshold assignment):

• An anchor is "positive" if IoU with any GT > 0.7, "negative" if IoU with all GT < 0.3, ignored otherwise
• Problem: Multiple anchors match the same GT object (intentionally), creating redundant detections that NMS must later remove. The model is explicitly trained to produce duplicates.
• Problem: The 0.3/0.7 thresholds are hand-tuned on COCO. A different dataset with different object size distributions may need different thresholds.
• Problem: Assignment considers only spatial overlap (IoU), not class -- an anchor is positive even if its predicted class is wrong.

RetinaNet (similar IoU-based assignment):

• 9 anchors per position, positive if IoU > 0.5
• Focal loss helps with class imbalance but assignment is still many-to-one

DETR's requirement: We need a one-to-one assignment that is:

1. Optimal: minimizes total matching cost across all prediction-GT pairs
2. Joint: considers class, location, and size simultaneously (not just IoU)
3. Permutation-invariant: the loss should not depend on which output slot (query index) a prediction comes from
4. Compatible with backpropagation: the matching itself is not differentiable, but the loss computed on matched pairs must be

Bipartite matching via the Hungarian algorithm:

DETR formulates assignment as a bipartite matching problem solved in two steps:

Step 1: Compute the N x M cost matrix

For each prediction-GT pair $(i, j)$ where $i \in \{1,...,N\}$ and $j \in \{1,...,M\}$:

$C_{ij} = -\alpha_c \cdot \hat{p}_i(c_j) + \alpha_{L1} \cdot \|b_j - \hat{b}_i\|_1 + \alpha_{GIoU} \cdot (1 - \text{GIoU}(b_j, \hat{b}_i))$

where:

• $\hat{p}_i(c_j)$ = prediction $i$'s softmax probability for the GT class $c_j$ (higher is better, so negated)
• $\|b_j - \hat{b}_i\|_1$ = L1 distance between GT box $b_j$ and predicted box $\hat{b}_i$ in normalized coordinates (sum of absolute differences of $x_c, y_c, w, h$)
• $\text{GIoU}(b_j, \hat{b}_i)$ = Generalized IoU, which handles non-overlapping boxes better than standard IoU (range [-1, 1])
• Weights: $\alpha_c = 1$, $\alpha_{L1} = 5$, $\alpha_{GIoU} = 2$ (tuned on COCO val set)

Why both L1 and GIoU? L1 loss has equal magnitude regardless of box size: a 10-pixel offset on a 1000-pixel box is the same L1 as a 10-pixel offset on a 30-pixel box. GIoU is scale-invariant -- it penalizes relative misalignment. Together, they handle objects of all sizes.

Step 2: Hungarian algorithm finds the minimum-cost one-to-one matching

The Hungarian algorithm solves: $\hat{\sigma} = \arg\min_{\sigma \in \mathfrak{S}_N} \sum_{i=1}^{M} C_{i, \sigma(i)}$

where $\mathfrak{S}_N$ is the set of all permutations of $\{1, ..., N\}$. This finds the optimal assignment $\hat{\sigma}$ that minimizes the total matching cost.

• Time complexity: $O(N^3)$ -- for N=100, this takes ~0.5ms per image, negligible compared to the forward pass (~35ms)
• The algorithm is not differentiable -- but it does not need to be. It is run as a preprocessing step to determine the assignment, then gradients flow through the loss computed on matched pairs.

Step 3: Compute the loss on matched pairs

Once the optimal matching $\hat{\sigma}$ is found:

$\mathcal{L}_{\text{Hungarian}} = \sum_{i=1}^{N} \left[-\log \hat{p}_{\hat{\sigma}(i)}(c_i) + \mathbf{1}_{c_i \neq \varnothing}\left(\lambda_{L1}\|b_i - \hat{b}_{\hat{\sigma}(i)}\|_1 + \lambda_{GIoU}(1 - \text{GIoU}(b_i, \hat{b}_{\hat{\sigma}(i)}))\right)\right]$

where:

• For the M matched queries: $c_i$ is the GT class, and both classification and box losses apply
• For the N-M unmatched queries: $c_i = \varnothing$, and only classification loss applies (training them to predict "no object")
• Loss weights: $\lambda_{L1} = 5$, $\lambda_{GIoU} = 2$

Class imbalance handling: With N=100 and M~7 (COCO average), ~93% of predictions are trained on the $\varnothing$ class. The authors down-weight the $\varnothing$ class loss by a factor of 10 to prevent the model from trivially predicting $\varnothing$ for everything.

Auxiliary losses: The matching loss is applied at every decoder layer (not just the final one), using the same matching $\hat{\sigma}$. Prediction FFN heads at intermediate layers share weights with the final layer. This intermediate supervision significantly accelerates training and improves final performance by +1.2 AP.

Why this is fundamentally better than IoU-threshold assignment:

Property	IoU-Threshold (Faster R-CNN)	Hungarian (DETR)
Assignment	Many-to-one (multiple anchors per GT)	Strictly one-to-one
Optimality	Greedy (each anchor independently)	Globally optimal (min-cost)
Criteria	IoU only (spatial)	Class + L1 + GIoU (joint)
NMS needed?	Yes (to remove many-to-one duplicates)	No (one-to-one by construction)
Hyperparameters	IoU thresholds 0.3/0.7, NMS 0.5	None for assignment

Why CNNs alone are insufficient for set-based detection:

Object detection requires three capabilities:

1. Global context understanding (what objects are present and how they relate):

• A person next to a surfboard on sand strongly suggests a beach scene -- context disambiguates
• Two overlapping bounding boxes where one contains a person and another a backpack -- the backpack likely belongs to the person
• CNNs process local patches: a 3x3 conv at stride 16 sees only a 3x16=48 pixel region. Even deep ResNets have limited effective receptive fields (~100-200 pixels, far less than theoretical)
• Result: CNNs cannot reason about relationships between distant objects (e.g., a leash connecting a person and a dog 300 pixels apart)

2. Precise spatial localization (where exactly objects are):

• CNNs excel at this: hierarchical features with decreasing stride capture boundaries and positions
• ResNet-50 at stride 32 produces a 25x34 feature map for a 800x1066 image -- each cell encodes a 32x32 region with 2048-dimensional features

3. Set-level reasoning (predicting the right number of objects without duplicates):

• Traditional detectors produce ~100K candidate detections and filter with NMS -- a brute-force approach
• There is no mechanism in CNN architectures for one detection to "know about" another detection
• NMS is a hard, non-differentiable operation that approximates set prediction through greedy elimination

What a transformer adds:

Self-attention computes pairwise interactions between ALL positions in $O(N^2)$: $\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d}}\right)V$

For a 25x34 = 850 token sequence (typical COCO image at stride 32), each token directly attends to all 850 other positions. This global receptive field in a single layer is what enables:

• Long-range context (a person's face and their bag 500 pixels away are directly connected)
• Duplicate suppression (object queries can see what other queries are detecting)
• Global counting (the model can "count" objects by distributing them across queries)

However, transformers alone struggle with images:

• No built-in spatial inductive bias (translation equivariance)
• Require positional encodings to understand spatial layout
• Quadratic complexity makes processing raw pixels infeasible (800x1066 = 852K tokens -> ~726 billion attention entries)
• Need a CNN to reduce spatial resolution first

DETR's hybrid CNN-Transformer architecture (complete data flow with tensor shapes):

For a standard COCO image of size 800x1066 (H x W):

1. CNN Backbone (ResNet-50): Extracts a spatial feature map

$[1, 3, 800, 1066] \xrightarrow{\text{ResNet-50}} [1, 2048, 25, 34]$

The backbone reduces spatial dimensions by 32x (stride 32) while expanding channels to 2048. This is the standard ImageNet-pretrained ResNet-50 (23.5M parameters), optionally fine-tuned during DETR training with a 10x smaller learning rate.

2. Channel projection (1x1 Conv): Reduces channel dimension for the transformer

$[1, 2048, 25, 34] \xrightarrow{\text{Conv}_{1 \times 1}} [1, 256, 25, 34]$

This 1x1 convolution (2048 x 256 = 524K parameters) projects the high-dimensional CNN features to the transformer's model dimension $d = 256$.

3. Flatten + Positional Encoding: Convert 2D feature map to 1D sequence with spatial information

$[1, 256, 25, 34] \xrightarrow{\text{flatten}} [1, 850, 256] \xrightarrow{+ PE_{2D}} [1, 850, 256]$

The 2D feature map is flattened to a sequence of 850 tokens (25 x 34). Fixed 2D sine/cosine positional encodings are added (not concatenated) to inject spatial information, using 128 dimensions for x-position and 128 for y-position.

4. Transformer Encoder (6 layers): Global self-attention over all spatial positions

Each of the 6 encoder layers contains:

• Multi-head self-attention (8 heads, $d_k = d/8 = 32$ per head): Every token attends to all 850 tokens
• FFN (Linear(256, 2048) -> ReLU -> Linear(2048, 256)): Per-token feature transformation
• LayerNorm + residual connections on both sub-layers

$F_{enc} = \text{Encoder}_{6\text{-layer}}([1, 850, 256]) = [1, 850, 256]$

Encoder parameter count: 6 layers x (4 x 256 x 256 [attention Q/K/V/O projections] + 256 x 2048 + 2048 x 256 [FFN] + LayerNorm) = ~6.3M parameters

What the encoder does: Self-attention enables global reasoning. After encoding:

• Each token's representation incorporates information from all 850 spatial positions
• The model can represent relationships like "these two distant regions both contain parts of the same large object"
• Attention patterns in trained models show that the encoder separates objects from background and captures object boundaries

5. Transformer Decoder (6 layers): Transforms object queries into detections

Input: 100 learned object queries $Q \in \mathbb{R}^{100 \times 256}$ (randomly initialized, learned end-to-end).

Each of the 6 decoder layers contains:

• Self-attention among queries (100 queries attend to each other): Enables coordination to avoid duplicate predictions
• Cross-attention from queries to encoder output (100 queries attend to 850 encoded tokens): Each query "looks at" the image and focuses on relevant regions
• FFN (same architecture as encoder): Per-query refinement
• LayerNorm + residual connections on all three sub-layers

$Q^{(6)} = \text{Decoder}_{6\text{-layer}}(Q, F_{enc}) = [1, 100, 256]$

Decoder parameter count: 6 layers x (self-attention + cross-attention + FFN + LayerNorm) = ~6.3M parameters

6. FFN Prediction Heads: Two parallel heads per query

Class head (shared across all decoder layers for auxiliary loss): $\hat{c}_i = \text{Linear}_{256 \rightarrow 92}(q_i^{(6)}) \in \mathbb{R}^{92}$ Predicts 91 COCO classes + 1 "no object" ($\varnothing$) class. Softmax applied for loss computation.

Box head (3-layer MLP, also shared): $\hat{b}_i = \text{Sigmoid}(\text{Linear}(\text{ReLU}(\text{Linear}(\text{ReLU}(\text{Linear}_{256 \rightarrow 256}(q_i^{(6)}))))))$ $= (\hat{x}_c, \hat{y}_c, \hat{w}, \hat{h}) \in [0,1]^4$ Normalized center coordinates and size relative to the full image. Sigmoid ensures all values are in [0,1].

Head parameter count: ~0.9M (class: 256x92 = 24K, box MLP: 256x256 + 256x256 + 256x4 = ~131K, shared across 6 layers)

Total DETR parameter breakdown:

• ResNet-50 backbone: 23.5M (56%)
• 1x1 projection: 0.5M (1%)
• Transformer encoder: 6.3M (15%)
• Transformer decoder: 6.3M (15%)
• Prediction heads: 0.9M (2%)
• Object queries + positional encodings: ~0.05M (<1%)
• Total: ~41M parameters

Why this architecture excels at large objects:

The encoder's self-attention allows every spatial position to incorporate global context. For a large bus spanning 400 pixels, the feature map positions covering its front and back (separated by ~12 feature cells) directly communicate in the encoder, producing a unified representation. Traditional CNN detectors only connect these positions after multiple layers of local convolution, losing fine-grained spatial coordination.

DETR achieves 61.1 AP-L vs. Faster R-CNN's 54.0 AP-L (+7.1) -- a direct benefit of global attention.

Complete DETR data flow for 800x1066 COCO image:

Input: [1, 3, 800, 1066]

Backbone (ResNet-50):

• conv1 + pool: [1, 64, 200, 267]
• res2: [1, 256, 200, 267] -- stride 4
• res3: [1, 512, 100, 134] -- stride 8
• res4: [1, 1024, 50, 67] -- stride 16
• res5: [1, 2048, 25, 34] -- stride 32

Projection: Conv1x1(2048, 256) -> [1, 256, 25, 34]

Flatten: [1, 256, 25, 34] -> [1, 850, 256]

Add positional encoding: [1, 850, 256] (128-dim sine for x, 128-dim cosine for y)

Encoder (6 layers, each: self-attn(850x850, 8 heads) + FFN(256->2048->256)):

• Input: [1, 850, 256] -> Output: [1, 850, 256]

Decoder (6 layers, each: self-attn(100x100) + cross-attn(100x850) + FFN):

• Queries: [1, 100, 256] (learned parameters)
• Keys/Values from encoder: [1, 850, 256]
• Output: [1, 100, 256]

Prediction heads (per query, shared across decoder layers):

• Class: Linear(256, 92) -> [1, 100, 92] (softmax -> probabilities)
• Box: MLP(256, 256, 256, 4) + sigmoid -> [1, 100, 4] (normalized coords)

Hungarian matching + Loss (computed on all 100 outputs vs M GT objects)

The localization challenge: connecting abstract queries to spatial positions:

Object queries are 256-dimensional learned embeddings with no inherent spatial meaning. They are the same regardless of what image is being processed. Yet they must:

• Attend to specific image regions: Query 42 might need to detect a car in the top-left of one image and a person in the bottom-right of another
• Handle varying numbers of objects: If there are 7 objects, 7 queries should attend to object regions while 93 should attend "nowhere" (or broadly to predict $\varnothing$)
• Avoid overlapping with other queries: If query 15 is already detecting a dog, query 42 should not also detect that dog -- but they must coordinate through self-attention and cross-attention
• Localize precisely: DETR achieves 42.0 AP, which requires bounding boxes accurate to within ~5-10 pixels on average

The puzzle: How does a fixed embedding vector (query) that is the same across all images learn to look at different positions in different images?

The answer: Cross-attention weights are computed dynamically from the interaction between the query and the encoded image features. The query's learned representation defines what "pattern" to look for (e.g., large rectangular objects), while the image features determine where such patterns appear. The inner product $QK^T$ produces high values where the query's pattern matches the image content.

In traditional detectors, localization is handled explicitly:

• Anchors are placed at fixed spatial positions with fixed sizes
• RPN regresses offsets from these fixed anchors
• The spatial prior is hard-coded into the architecture

In DETR, localization emerges from learned attention -- no spatial priors are hand-designed.

Cross-attention: the mechanism that connects queries to image features

In each of the 6 decoder layers, cross-attention computes:

$\text{CrossAttn}(Q, K, V) = \text{softmax}\left(\frac{(Q + PE_q)(K + PE_{2D})^T}{\sqrt{d_k}}\right) \cdot V$

where:

• $Q \in \mathbb{R}^{100 \times 256}$ = object queries from the previous sub-layer (after self-attention)
• $K = V = F_{enc} \in \mathbb{R}^{850 \times 256}$ = encoded image features (keys and values are the same)
• $PE_q \in \mathbb{R}^{100 \times 256}$ = learned query positional embeddings (added to Q)
• $PE_{2D} \in \mathbb{R}^{850 \times 256}$ = 2D sine/cosine spatial encodings (added to K)
• $d_k = 32$ (head dimension for 8-head attention)

The attention matrix $A \in \mathbb{R}^{100 \times 850}$ has entry $A_{ij}$ representing how much query $i$ attends to spatial position $j$:

$A_{ij} = \frac{\exp\left((q_i + pe_q^i)^T(k_j + pe_{2D}^j)/\sqrt{d_k}\right)}{\sum_{j'=1}^{850}\exp\left((q_i + pe_q^i)^T(k_{j'} + pe_{2D}^{j'})/\sqrt{d_k}\right)}$

What trained attention maps reveal (key empirical finding):

The authors visualize decoder cross-attention maps (reshaped from 850-length vectors back to 25x34 spatial grids) and observe:

1. Object-focused attention: Queries that predict real objects attend tightly to those objects, not to the background. The attention is sparse -- most of the 850 positions receive near-zero weight.

2. Extremity attention: Queries tend to attend to the extremities (edges, endpoints) of objects rather than their centers. For a car, the query attends to the four corners and the front/rear edges. For a person, it attends to the head and feet. This makes sense: extremities define the bounding box.

3. Progressive refinement across layers: Early decoder layers produce broad, diffuse attention patterns (query "searching" for an object). Later layers produce sharp, focused patterns (query "locked on" to specific extremities). By layer 6, attention is highly concentrated on 5-10 spatial positions.

4. $\varnothing$-query attention: Queries that predict "no object" tend to have diffuse, unfocused attention patterns -- they attend broadly to the background without concentrating on any region.

5. Distinct per-query patterns: Different queries attending to the same image produce non-overlapping attention maps, confirming that self-attention among queries enables them to "divide up" the image.

Why cross-attention works better than spatial priors for large objects:

An anchor at position (100, 200) with size 128x128 can only detect objects near that spatial location at roughly that scale. If a bus spans from (50, 100) to (700, 300), no single anchor captures it well -- the detection relies on aggressive box regression from the nearest anchors.

In contrast, a DETR query can simultaneously attend to pixel (50, 100) and (700, 300), capturing both ends of the bus in a single attention operation. This is why DETR excels on large objects: 61.1 AP-L vs Faster R-CNN's 54.0 AP-L (+7.1 AP).

Multi-head attention splits the workload:

With 8 attention heads, each head can focus on different aspects:

• Head 1 might attend to the top-left extent of the object
• Head 2 might attend to the bottom-right extent
• Head 3 might attend to the object's center (for class identity)
• Other heads might capture context (nearby objects, scene type)

The 8 heads are projected together: $\text{MultiHead}(Q, K, V) = \text{Concat}(\text{head}_1, ..., \text{head}_8)W^O$ where $W^O \in \mathbb{R}^{256 \times 256}$.

Why detection should be set prediction:

Objects in an image have no natural ordering. Consider an image with a dog, a cat, and a bird:

• Is the "correct" order {dog, cat, bird}? Or {cat, bird, dog}? Or {bird, dog, cat}?
• There are $3! = 6$ equally valid orderings, yet a loss function that depends on order would penalize 5 of them

Traditional detectors impose artificial ordering:

Anchor-based (Faster R-CNN, RetinaNet):

• Predictions are ordered by their spatial anchor position (top-left to bottom-right, across FPN levels)
• This ordering is arbitrary: an object in the top-left is not inherently "first"
• The anchor assignment (which prediction is responsible for which GT) depends on spatial IoU, creating a fixed correspondence between positions and objects

Confidence-based (post-NMS output):

• Final detections are sorted by confidence score
• The highest-confidence detection is "first" -- but this has no semantic meaning
• Permuting the output would not change the detection quality, yet the evaluation implicitly depends on this ordering for AP computation

Autoregressive models (rare but theoretically possible):

• Predict objects one at a time, conditioned on previous predictions
• Imposes a sequential dependency that doesn't exist in the data
• Slower inference (can't parallelize) and error accumulation

What we need:

• A loss function where $L(\{\text{dog, cat, bird}\}) = L(\{\text{cat, bird, dog}\})$ -- truly permutation-invariant
• A prediction mechanism that does not impose ordering constraints
• A training procedure that can handle varying numbers of objects per image (M varies from 0 to ~63 in COCO)

Set-based prediction with Hungarian matching provides true permutation invariance:

DETR's formulation satisfies all three requirements:

1. Permutation-invariant loss via Hungarian matching:

The Hungarian algorithm finds the optimal assignment $\hat{\sigma}$ regardless of which output slot each object is predicted in:

$\hat{\sigma} = \arg\min_{\sigma \in \mathfrak{S}_N} \sum_{i=1}^{M} C_{i, \sigma(i)}$

If the model outputs {dog at slot 7, cat at slot 42, bird at slot 91}, the Hungarian algorithm will find this matching and compute the same loss as if the outputs were {dog at slot 1, cat at slot 2, bird at slot 3}. The loss value depends only on the quality of the predictions (class correctness and box accuracy), not on which slot they appear in.

Formal property: For any permutation $\pi$ of query indices: $\mathcal{L}(\{\hat{y}_{\pi(1)}, ..., \hat{y}_{\pi(N)}\}, Y_{GT}) = \mathcal{L}(\{\hat{y}_1, ..., \hat{y}_N\}, Y_{GT})$

2. Parallel (non-autoregressive) decoding:

All 100 object queries are processed simultaneously in the decoder:

• Self-attention: all 100 queries interact in parallel (not sequentially)
• Cross-attention: all 100 queries attend to the image in parallel
• FFN: applied independently to each query

This means inference produces all 100 predictions in a single forward pass with no sequential dependencies. Unlike autoregressive models (which predict token-by-token), DETR's predictions are conditionally independent given the encoder output and the self-attention interactions.

3. Variable-cardinality set prediction:

The model always outputs exactly N=100 predictions, but the number of "real" objects varies per image. The Hungarian matching handles this elegantly:

• If M=5 objects: 5 queries are matched to objects, 95 are supervised to predict $\varnothing$
• If M=40 objects: 40 matched, 60 predict $\varnothing$
• If M=0 objects (empty image): all 100 predict $\varnothing$

The model effectively learns to "count" objects by varying how many queries output real predictions vs. $\varnothing$.

Connection to set theory and combinatorics:

DETR's approach is deeply connected to the concept of sets in mathematics:

• A set is defined by its elements, not their order: $\{a, b, c\} = \{c, a, b\}$
• Set cardinality is variable: $|S|$ can be 0, 1, ..., N
• Set comparison requires solving an assignment problem when elements are not exactly equal (soft matching via the cost matrix)

The Hungarian algorithm (also known as the Kuhn-Munkres algorithm) was originally developed in 1955 for the assignment problem in operations research. DETR is the first work to apply it to neural network training for object detection, bridging combinatorial optimization and deep learning.

Comparison with other set prediction methods:

Method	Ordering	Assignment	Parallel	Used in
Sorted by confidence	Arbitrary	IoU threshold	Yes	Faster R-CNN
Autoregressive	Sequential	Greedy	No	Image captioning
Hungarian matching	None	Optimal	Yes	DETR

DETR's set prediction is the only approach that is simultaneously unordered, optimally assigned, and parallelizable.

The position-blindness problem in transformers:

Transformers are permutation-equivariant by design: if you shuffle the input tokens, the self-attention output shuffles in exactly the same way. This is mathematically elegant but catastrophic for images:

Problem 1: Image features lose spatial meaning

• After flattening the 25x34 feature map to 850 tokens, token 0 and token 849 are treated identically by the transformer
• But token 0 represents the top-left corner (position 0,0) and token 849 represents the bottom-right (position 24,33) -- they are 800 pixels apart!
• Without position info, the encoder's self-attention matrix $A$ would be identical regardless of whether we process the image normally or with all pixels randomly shuffled
• Detection requires knowing WHERE objects are, not just WHAT objects exist

Problem 2: Object queries lose identity

• The 100 object queries are processed symmetrically by the decoder
• Without unique identifiers, all queries would produce identical outputs (same class probabilities, same box coordinates) because they have no way to differentiate themselves
• We need each query to develop a unique "role" -- but this requires some asymmetry in the input

Problem 3: 2D structure of images

Natural language is 1D (token sequences), so standard 1D positional encodings work. Images are 2D with spatial structure along both axes:

• Horizontal neighbors share y-coordinates but differ in x
• The 2D spatial relationship between two positions matters (e.g., "directly above" vs. "diagonally adjacent")
• 1D positional encodings (treating the flattened sequence as text) would lose this 2D structure

Ablation showing the impact (from the paper):

• DETR without any positional encoding: ~32 AP (vs. 42.0 AP with encoding -- a 10 AP drop)
• With 1D (text-style) encoding: ~38 AP (better, but loses 2D structure)
• With learned 2D encoding: ~41.5 AP (good, but slightly overfits)
• With fixed 2D sine/cosine encoding: 42.0 AP (best, and generalizes to different image sizes)

Two types of positional encodings tailored for detection:

Type 1: Fixed 2D Sine/Cosine Encodings (for image features)

For each spatial position $(x, y)$ in the 25x34 feature grid, a 256-dimensional encoding is constructed:

$PE_x(x, 2i) = \sin\left(\frac{x}{10000^{2i/128}}\right), \quad PE_x(x, 2i+1) = \cos\left(\frac{x}{10000^{2i/128}}\right)$ $PE_y(y, 2i) = \sin\left(\frac{y}{10000^{2i/128}}\right), \quad PE_y(y, 2i+1) = \cos\left(\frac{y}{10000^{2i/128}}\right)$

$PE_{2D}(x, y) = \text{Concat}(PE_x(x), PE_y(y)) \in \mathbb{R}^{256}$

where $i \in \{0, 1, ..., 63\}$ (128 dimensions per axis, concatenated to 256 total).

Key properties of sine/cosine encodings:

• Fixed (not learned): No additional parameters, works for any image size
• Unique per position: Every (x, y) pair produces a unique 256-dim vector
• Encodes relative position: $PE(pos+k)$ can be expressed as a linear function of $PE(pos)$, meaning the model can learn to compute relative distances through linear projections in attention
• Multi-frequency: Low-frequency components ($i$ near 0, wavelength $\approx 2\pi$) encode coarse position; high-frequency components ($i$ near 63, wavelength $\approx 10000 \cdot 2\pi$) encode fine position
• Separable: The x and y encodings are independent, which is appropriate because horizontal and vertical positions have different semantics in images (vertical: objects at different scales, horizontal: left/right context)

Where they are applied:

The 2D positional encodings are added to Q and K (not V) in both the encoder self-attention and the decoder cross-attention:

$\text{Attn}(Q, K, V) = \text{softmax}\left(\frac{(Q + PE)(K + PE)^T}{\sqrt{d_k}}\right) \cdot V$

This means position influences which tokens attend to which (through Q and K) but does not directly modify the feature content (V remains position-free). This design choice allows the attention mechanism to learn position-dependent routing while keeping the value representations purely content-based.

Type 2: Learned Embeddings (for object queries)

The 100 object queries use learned positional embeddings:

$PE_q = \{pe_1, pe_2, ..., pe_{100}\} \in \mathbb{R}^{100 \times 256}$

These are randomly initialized and updated via backpropagation during training. They serve a dual purpose:

1. Query identity: Each query gets a unique $pe_i$ that differentiates it from all other queries, breaking the symmetry that would otherwise produce identical outputs
2. Spatial prior: After training, these embeddings develop spatial structure -- certain queries' embeddings encode a preference for particular image regions (e.g., query 42 might specialize in the center of images)

Why learned (not fixed) for queries?

Object queries have no natural spatial meaning (unlike image features, which correspond to specific pixel regions). Their "position" is abstract -- it represents a detection slot, not a spatial coordinate. Learned embeddings allow each query to develop its own specialization through training, which would not be possible with fixed encodings.

In the decoder, query positional embeddings are applied to:

• Self-attention: added to Q and K so queries can distinguish each other
• Cross-attention: added to Q so each query has a unique "search pattern" when attending to image features

Implementation detail: The same $PE_{2D}$ for image features is used in both encoder self-attention (token-to-token) and decoder cross-attention (query-to-token). The same $PE_q$ for object queries is used in both decoder self-attention (query-to-query) and decoder cross-attention (query side).

DETR's practical limitations in detail:

Despite its elegant formulation, DETR has three significant problems that prevent practical adoption:

Problem 1: Extremely slow convergence (500 epochs, 12 days on 8 V100s)

DETR requires 500 training epochs on COCO (118K images) to reach 42.0 AP. For comparison:

• Faster R-CNN: 36 epochs (12x fewer) for 42.0 AP
• RetinaNet: 12 epochs (40x fewer) for 39.1 AP

Why so slow? The cross-attention in the decoder must learn to focus on relevant image positions from scratch. Without spatial priors (anchors provide these for free in Faster R-CNN), the model starts with near-uniform attention over all 850 spatial positions and must gradually sharpen to object-specific patterns. This "attention learning" is the bottleneck -- box regression and classification converge much faster.

Empirical evidence: At epoch 50, DETR achieves only ~35 AP (vs. 42.0 at epoch 500). The attention maps are still diffuse and unfocused at this stage.

Problem 2: Quadratic memory/compute in encoder self-attention

The encoder self-attention computes an $HW \times HW$ attention matrix:

• For 800x1066 image at stride 32: $25 \times 34 = 850$ tokens -> $850^2 = 722,500$ attention entries per head
• For higher-resolution features (stride 16): $50 \times 67 = 3,350$ tokens -> $3,350^2 = 11.2M$ attention entries per head
• For multi-scale features (stride 8): $100 \times 134 = 13,400$ tokens -> $13,400^2 = 179.6M$ entries -- infeasible

This quadratic scaling prevents DETR from using high-resolution features, which are essential for small-object detection.

Problem 3: Poor small-object detection (20.5 AP-S vs. Faster R-CNN's 24.1 AP-S)

DETR uses only stride-32 features (the C5 output of ResNet). At this resolution:

• A 20x20 pixel object (COCO "small" category) occupies only 0.6 x 0.6 feature cells -- it is essentially invisible
• A 32x32 object occupies 1x1 cell -- barely detectable
• Faster R-CNN uses FPN with stride-4 features (P2), where a 20x20 object occupies 5x5 cells -- ample resolution

Adding multi-scale features to DETR would require processing 850 + 3,350 + 13,400 = 17,600 tokens through self-attention: $17,600^2 = 309M$ attention entries per head. This is prohibitively expensive.

Problem 4: High GPU memory usage

Storing the $850 \times 850$ attention matrix (float32) for 8 heads across 6 encoder layers requires: $850 \times 850 \times 8 \times 6 \times 4 = 139\text{MB}$ for attention alone. With multi-scale features, this would balloon to $17,600^2 \times 8 \times 6 \times 4 \approx 59\text{GB}$ -- exceeding any single GPU's memory.

Deformable DETR: sparse attention + multi-scale features

Core innovation: Deformable attention module

Instead of computing attention over ALL spatial positions (dense, $O(H^2W^2)$), deformable attention attends to only $K = 4$ learnable sampling points per query per attention head:

For each query $q$ and reference point $p_q$ (the center of its predicted box from the previous layer):

$\text{DeformAttn}(q, p_q, F) = \sum_{m=1}^{M}W_m\left[\sum_{k=1}^{K}A_{mqk} \cdot F(p_q + \Delta p_{mqk})\right]$

where:

• $M = 8$ attention heads
• $K = 4$ sampling points per head
• $\Delta p_{mqk} \in \mathbb{R}^2$: learnable 2D offset for head $m$, point $k$ (predicted by a linear layer from $q$)
• $A_{mqk} \in [0,1]$: attention weight for head $m$, point $k$ (predicted by a linear layer + softmax over $K$ points)
• $F(p_q + \Delta p_{mqk})$: feature value at the offset position, computed via bilinear interpolation (differentiable)

Key properties:

• Sparse: Each query attends to only $M \times K = 8 \times 4 = 32$ points total, instead of 850+ positions
• Learned sampling: The offsets $\Delta p$ are predicted from the query content, so they adapt to each image
• Differentiable: Bilinear interpolation at fractional positions allows gradients to flow through offsets
• Complexity: $O(HW \times MK)$ instead of $O(H^2W^2)$ -- linear in spatial resolution instead of quadratic

Multi-scale deformable attention (the critical addition):

With O(HWK) instead of O(H^2W^2) complexity, processing multi-scale features becomes feasible:

$\text{MSDeformAttn}(q, \hat{p}_q, \{F^l\}_{l=1}^{L}) = \sum_{m=1}^{M}W_m\left[\sum_{l=1}^{L}\sum_{k=1}^{K}A_{mlqk} \cdot F^l(\phi_l(\hat{p}_q) + \Delta p_{mlqk})\right]$

where $\{F^l\}$ are features from $L = 4$ FPN levels (P3 through P6 from ResNet-50-FPN):

• P3: stride 8, 100x134 = 13,400 tokens
• P4: stride 16, 50x67 = 3,350 tokens
• P5: stride 32, 25x34 = 850 tokens
• P6: stride 64, 13x17 = 221 tokens
• Total: 17,821 tokens

With dense attention: $17,821^2 \approx 317M$ entries per head -- infeasible. With deformable attention: $17,821 \times 4 \times 4 \approx 285K$ entries per head -- 3 orders of magnitude cheaper.

Iterative bounding box refinement:

Each decoder layer refines the predicted bounding box from the previous layer: $\hat{b}^{(l)} = \hat{b}^{(l-1)} + \Delta b^{(l)}$

The reference point $p_q$ for deformable attention is updated to the center of $\hat{b}^{(l-1)}$, so sampling points are concentrated around the current best estimate of the object location. This progressive refinement is much faster than DETR's approach of learning localization from scratch at every layer.

Two-stage variant:

Deformable DETR can optionally operate in a two-stage mode:

1. Stage 1: The encoder produces "region proposals" by predicting a box at every spatial position (similar to RPN but without anchors)
2. Stage 2: Top-scoring proposals become reference points for the decoder, replacing learned object queries

This further improves performance to 46.2 AP (vs. 43.8 for one-stage Deformable DETR).

Convergence comparison (COCO val):

Epochs	DETR AP	Deformable DETR AP
12	32.5	41.5
50	35.4	43.8
150	39.2	44.1
500	42.0	--

Deformable DETR at 50 epochs (43.8 AP) already surpasses DETR at 500 epochs (42.0 AP) -- 10x faster convergence AND +1.8 AP better.

Small-object detection improvement:

Model	AP-S	AP-M	AP-L
DETR	20.5	45.3	61.1
Deformable DETR	26.4	47.1	58.0

The +5.9 AP-S improvement comes directly from multi-scale features: stride-8 features give small objects 16x more feature cells than stride-32. The slight AP-L decrease (-3.1) is because deformable attention's sparse K=4 points are less effective than DETR's global attention for reasoning about very large objects.

Total parameter count: ~40M (comparable to DETR), with the deformable attention modules replacing standard attention with minimal parameter overhead.