Skip to main content

Set Prediction and Bipartite Matching

Learn how DETR assigns unordered object targets to prediction slots, why greedy choices can fail, and how matching differs from training loss and evaluation.

Object queries give DETR a fixed number of prediction slots. Each slot produces class scores and a box. An image, however, contains a variable number of labeled objects, with no natural first or second object. Before training can correct a prediction, it must decide which object that prediction should learn to describe.

Suppose an image contains a dog and a bicycle. Listing the dog first in the annotation file should not make slot 1 responsible for dogs. Reversing the file should not change what counts as a correct detection. Set prediction treats the objects as an unordered collection; matching finds a temporary correspondence for the current predictions.

From a set to a training target

Place the prediction slots on one side of a graph and the annotated objects on the other. Each possible slot–object pair has a cost describing how poorly they agree. The graph is bipartite because its edges connect these two different groups.

A valid assignment chooses one prediction for every real object, using each prediction at most once. With three slots and two objects, two slots receive real-object targets and the remaining slot receives the special no-object class. Its box has no real-object regression target. DETR normally uses many more slots than objects; if the image contains more objects than available slots, this one-to-one scheme cannot cover them all.

The assignment is recalculated from the current predictions during training. Slot 1 can match the dog in one image and the bicycle in another. Matching supplies supervision; it does not give slots permanent object identities across images or video frames.

Why the cheapest pair can be the wrong first choice

A greedy method can take the cheapest available pair, remove that slot and target, and repeat. The problem is that its first decision can consume the only good option for another target. Minimum-cost assignment compares the sum across the whole correspondence.

The explorer uses three slots, two named targets and six possible assignments. Start with Q2 → B at 9, then lower it to 1. Reverse the target order to check that the same objects still receive the same optimal slots when the optimum is unique.

Assign two targets to three slots
Target order
9

Authored pair costs; lower is better. These abstract numbers illustrate assignment, not recorded model outputs or computed box geometry.

Cost matrix
SlotTarget ATarget B
Q112 ✓
Q22 ✓9
Q398
Minimum total
4
Optimal pairs
A → Q2; B → Q1
No-object slot
Q3
Greedy total
9
Greedy pairs
A → Q1; B → Q3

All six possible one-to-one assignments

  1. A → Q2; B → Q14 (minimum)
  2. A → Q1; B → Q39
  3. A → Q1; B → Q210
  4. A → Q2; B → Q310
  5. A → Q3; B → Q111
  6. A → Q3; B → Q218

Exact small-example enumeration, not a Hungarian implementation. At cost 9, greedy takes Q1 → A first and pays 9 overall; reserving Q1 for B gives total 4. Reordering the target list preserves the optimal physical pairs. Ties may have several equally good pairings.

At the initial setting, the cheapest single pair is Q1 → A, costing 1. That leaves B with Q3 at cost 8, for a greedy total of 9. The joint solution chooses Q2 → A and Q1 → B, paying 2 + 2 = 4. Q3 is then supervised as no-object. No prediction is allowed to explain both targets.

The explorer checks every possibility because there are only 3×2=63 \times 2 = 6. This is exact enumeration for a small authored example, not an implementation of the Hungarian algorithm. The original DETR implementation calls a linear assignment solver to solve the larger problem efficiently. The objective is the same: minimize total pair cost subject to one-to-one constraints. Official matcher.

More formally, let MM be the number of real targets, N≥MN \ge M the number of slots, and σ(j)\sigma(j) the slot chosen for target jj. Then

σ^=arg⁡min⁡σ injective  ∑j=1MCσ(j),j.\hat{\sigma} = \underset{\sigma\ \mathrm{injective}}{\arg\min}\; \sum_{j=1}^{M} C_{\sigma(j),j}.

“Injective” simply means different targets must choose different slots. Reordering the target list changes the column order of the matrix, but preserves the achievable totals and the minimum value. When several assignments tie, a solver may choose a different equally optimal pairing after a reorder; permutation invariance does not imply a unique answer.

What makes a slot a good match?

The abstract matrix above isolates assignment. DETR builds its actual matrix from class agreement and box geometry. For slot ii and target jj, the original matcher uses

Cij=−λcls pi(cj)+λL1 ∥b^i−bj∥1−λGIoU GIoU⁡(b^i,bj).C_{ij} = -\lambda_{\mathrm{cls}}\,p_i(c_j) + \lambda_{L1}\,\lVert \hat{b}_i-b_j\rVert_1 - \lambda_{\mathrm{GIoU}}\,\operatorname{GIoU}(\hat{b}_i,b_j).

Here pi(cj)p_i(c_j) is the predicted probability of the target class. Higher probability lowers the cost. The L1 term sums absolute differences in box center, width and height, expressed as normalized (cx,cy,w,h)(c_x,c_y,w,h) coordinates. Generalized IoU compares the rectangles after conversion to corner coordinates; better geometric agreement also lowers the cost. The weights control how much these different signals influence assignment. Official matching-cost construction.

Class agreement alone can assign a confident prediction with a misplaced box. Geometry alone can assign a box that fits the right object while predicting the wrong class. Combining them makes the correspondence account for both what the object is and where it is. Changing their relative weights can change which correspondence wins.

The negative signs matter: matching minimizes a cost, so a high class probability or high GIoU should make a pair cheaper. The original matcher uses negative class probability, not negative log-probability. Replacing one with the other changes its tradeoff against box costs and can change the selected assignment. The explorer's positive integers are illustrative pair costs, not values calculated from this DETR formula.

Matching chooses responsibility; the loss teaches it

Once the correspondence is chosen, DETR builds training targets for the slots. Matched slots receive their assigned object classes and boxes. Unmatched slots receive no-object. Classification cross-entropy trains all slots, with the no-object class downweighted; L1 and GIoU box losses train only the matched slots. The matcher itself runs without gradient tracking. Gradients flow through the selected predictions in the subsequent losses, not through the discrete solver. Official loss implementation.

This separates two questions. Matching asks, “Which slot should be responsible for each object right now?” The loss asks, “How should those predictions change?” The classification loss uses log-probabilities even though the matching class cost uses probabilities. The box loss uses 1−GIoU⁡1-\operatorname{GIoU}, whereas the matching cost uses −GIoU⁡-\operatorname{GIoU}. Their difference is a constant per matched pair, so that particular change does not alter an assignment with a fixed number of pairs.

If two slots predict the same dog, only one can match its target. The other must either explain another object or learn no-object. This set supervision discourages duplicates and lets original DETR produce detections without a separate non-maximum suppression stage. It does not guarantee perfect uniqueness or correct detections after training. DETR paper, Section 3.1.

Training assignment is different from evaluation matching

The word “matching” also appears when evaluating a detector, but the purpose and rules differ. In common detection evaluation, predictions are ordered by confidence and matched to eligible ground-truth objects under class and IoU rules. Those choices determine true positives, false positives and recall. They do not assign differentiable training losses, and they are not DETR's joint class-and-box minimum-cost assignment. See object detection metrics for the evaluation procedure.

Non-maximum suppression is another separate operation: it filters competing predictions using their scores and overlap with each other, without ground-truth targets. A training matcher compares predictions with annotations to decide responsibility. An evaluation matcher measures performance against annotations. NMS filters predictions at inference time.

From correspondence to box geometry

Matching resolves which prediction should learn each object. Continue to modern object detection to place this set-based training objective in the complete architecture. For more detail on the box terms in the cost, the optional bounding-box regression and generalized IoU branch examines normalized coordinates, L1 distance and enclosure geometry.

If you found this explanation helpful, consider sharing it with others.

Mastodon