Bipartite matching for set-prediction losses

Overview

A model emits a fixed number of predictions in one pass, so its output is a set rather than a sequence. To train it, each ground-truth object must be paired with one prediction, and the loss is computed only on those pairs. The pairing is a minimum-cost one-to-one assignment, solved with the Hungarian algorithm. Every prediction that is left unpaired is trained toward "no object" 2005.12872 §3.1. The invariant all variants share is that a ground-truth object supervises exactly one prediction at a time. That is what removes anchors and non-maximum suppression (NMS) from the pipeline 2005.12872 §1.

Papers differ on what they match to: DETR-style models match object queries to boxes, TSP-style models match a short list of image locations 2011.10881 §4.1, and tracking matches predicted target states to detections 1604.03635 §Method. TrackFormer goes further and keeps identity out of the assignment for tracked objects: only new objects are matched by cost 2101.02702 §3.3. VisTR matches over time instead of over space: each slot is one instance sequence across all frames of a clip, and the cost is averaged over those frames 2011.14503 §3.2. Mask3D matches predicted instance masks against ground-truth masks, scored by Dice and BCE terms rather than by boxes 2210.03105 §3.1.

Variants

Original DETR: queries, Hungarian loss, full decoder

Object queries go through a transformer decoder. Matching cost combines class probability and an L1/GIoU box term, and the loss is applied after every decoder layer 2005.12872 §3.1 2005.12872 §3.2. The reported result is 42.0 AP on COCO val with ResNet-50 after 500 epochs 2005.12872 tab. 1. Card: End-to-End Object Detection with Transformers.

Faster convergence through query design

Conditional DETR keeps the same matching and loss and changes the decoder's cross-attention, with the spatial query predicted per object from a reference point. Matching is borrowed from Deformable DETR 2108.06152 §3.5. It reaches 40.9 AP after 50 epochs, against 34.9 for DETR at the same length 2108.06152 tab. 1. Card: Conditional DETR for Fast Training Convergence.

The same authors' diagnosis is that one-to-one matching is unstable early in training and that cross-attention is sparse. Their remedy is encoder-only prediction on 700 selected features, with matching restricted to locations inside an object 2011.10881 §4.1. Card: Rethinking Transformer-based Set Prediction for Object Detection.

Set losses in other domains

• Crowd localization. CLTR regresses head points with a Hungarian matcher whose cost adds a k-nearest-neighbour term (KMO). The paper's matching-cost ablation gives F1 80.02 with plain L1 plus confidence and 80.97 with KMO 2202.13065 tab. 8. Card: An End-to-End Transformer Model for Crowd Localization.

• 3D detection from cameras. DETR3D samples image features at 3D reference points projected into each camera, and trains one-to-one matching at every decoder layer 2110.06922 §3.3 2110.06922 §3.4. The matching cost is unweighted in the paper; the released code uses weights, as the DETR3D card's Paper vs code section records. Card: DETR3D.

• Fusion with a query head. BEVFusion's TransFusion-L head seeds 200 queries from a heatmap and matches them with the Hungarian method 2205.13790 §3.4. Card: BEVFusion.

• Lane topology. TopoMLP runs one-to-one matching for its lane and traffic detection losses, then reuses that assignment for its two topology losses 2310.06753 §3.5. In the code, queries that are not matched get no topology supervision at all topo_ll_head.py. Its reported OLS with ResNet-50 on OpenLane-V2 subset A is 38.2 2310.06753 tab. 1. Card: TopoMLP.

• Lane topology with fine-grained queries. TopoFG describes each lane with 11 ordered point queries and feeds only the first and last of them to a pairwise connectivity head 2511.12590 §3.3 2511.12590 §3.4. Lanes are matched one to one with the Hungarian method 2511.12590 §3.4. Its author-reported OLS on OpenLane-V2 subset_A is 48.0, against 44.1 for TopoLogic 2511.12590 tab. 1. Card: Fine-Grained Representation for Lane Topology Reasoning.

• Multi-object tracking. The RNN tracker matches predicted states to detections with a Hungarian step in its baseline, RNN_HA, and learns the association with an LSTM in RNN_LSTM 1604.03635 §Baseline comparison. Card: Online Multi-Target Tracking Using Recurrent Neural Networks.

• Oriented boxes. OrientedFormer uses one-to-one Hungarian matching with a focal loss and a rotated-IoU term 2409.19648 §3.6. Card: OrientedFormer.

• Generalist language-model decoder. VisionLLM's decoder writes boxes and masks as token sequences. For these set outputs it applies bipartite matching to align predicted sequences with the ground truth 2305.11175 §3.4 2305.11175 app. B. The matching cost and the tokenizer's query assignment are not stated 2305.11175 app. B. Its author-reported box AP is 44.6 with ResNet-50 and 60.2 with InternImage-H 2305.11175 tab. 1. Card: VisionLLM.

• 3D instance segmentation. Mask3D's 100 instance queries are matched to ground-truth instances with the Hungarian method. The matching cost is a weighted sum of Dice, BCE and class terms, with weights 2, 5 and 2 2210.03105 §3.1 2210.03105 eq. 4. The reported ScanNet validation mAP is 55.2, against 49.4 for the best listed baseline 2210.03105 tab. 1. Card: Mask3D.

• Video instance segmentation. VisTR assigns each instance sequence, the k-th slot of every frame in a clip of T = 36 frames, to one ground-truth instance with the Hungarian algorithm. The sequence cost combines class and box terms computed over all frames 2011.14503 §3.2 2011.14503 eq. 2. Its reported YouTube-VIS validation AP is 40.1 with ResNet-101 and 36.2 with ResNet-50 2011.14503 tab. 2. Card: End-to-End Video Instance Segmentation with Transformers.

• Vehicle-infrastructure fusion. UniV2X matches roadside agent queries to the vehicle's own agent queries with the Hungarian method, on the distance between their reference points after the roadside points are moved into the vehicle frame. Matched pairs are fused and unmatched roadside queries are appended 2404.00717 §Cross-view query matching. The released code adds a per-axis box gate and a cost cut-off; the paper states neither agent_fusion.py agent_fusion.py. Author-reported car mAP is 0.295 with fusion and 0.165 without 2404.00717 tab. 3. The reported ablations do not isolate the matcher. Card: End-to-End Autonomous Driving through V2X Cooperation.

• Object dependency graph. D3G matches its N object queries to ground-truth objects with the Hungarian method. It then trains a relation head on the matched sub-graph only, with binary cross-entropy over all ordered pairs 2409.02035 §4.3 2409.02035 eq. 8 2409.02035 eq. 9. Unmatched queries get no relation supervision in training, though relations are read for all queries at inference detr_graph.py. Author-reported synth-to-real AP_rel is 24.44 for DETR, against 13.36 for VMRN 2409.02035 tab. 3. The released relation loss is scaled differently from eq. 9 detr_graph.py. Card: A Modern Take on Visual Relationship Reasoning for Grasp Planning.

• Temporal action detection. TadTR's learned action queries each predict a segment (a normalised centre and length) and a class. The Hungarian algorithm matches them one to one to the ground-truth actions, with classification and segment terms in the cost 2106.10271 §III-B 2106.10271 eq. 6 2106.10271 eq. 7. Ground truth is padded with a no-action symbol to N_q targets 2106.10271 §III-B. The authors' default classification cost is cross-entropy, and focal loss is used in their improved setting 2106.10271 §III-B 2106.10271 §IV-A. Reported THUMOS14 average mAP is 49.3 for the default setting and 56.7 for the starred setting with focal loss and instance filtering 2106.10271 tab. 1. Card: End-to-end Temporal Action Detection with Transformer.

Tracking with track queries

TrackFormer uses a DETR-style decoder for tracking. Each active track is carried into the next frame as a track query, the previous frame's output embedding for that object, and learned object queries detect newcomers 2101.02702 §3.2. During training, track-query outputs are matched to ground truth by track identity, not by cost. Tracks that disappear become background. Only new objects go through the cost-based assignment, with the matching cost in eq. 2 and eq. 3 2101.02702 §3.3 2101.02702 eq. 2 2101.02702 eq. 3. The loss is then applied to all object and track predictions together 2101.02702 eq. 4. On the MOT17 training split, the authors' ablation gives 71.3 MOTA with track queries and 61.0 when they are replaced by greedy center matching 2101.02702 tab. 3. Card: TrackFormer.

Training-only one-to-many supervision

These variants keep one-to-one matching at inference and add extra positives during training only.

• H-DETR adds a second query group in which each ground truth is repeated K times (K = 6 for COCO detection), with masked self-attention keeping the two groups apart. Only the one-to-one group is used at inference 2207.13080 tab. 1. Card: DETRs with Hybrid Matching.
• Co-DETR trains auxiliary heads with classic one-to-many assigners (ATSS, Faster R-CNN and others) on the encoder output. Their positives become extra decoder query groups, and all auxiliary parts are dropped at inference 2211.12860 §3.1. Card: DETRs with Collaborative Hybrid Assignments Training.
• Lane detection in TopoMLP. The paper describes 300 one-to-one lane queries and no extra branch 2310.06753 §3.1 2310.06753 §4.2. The released code also trains 1500 one-to-many lane queries (k = 5) with an attention mask between the two groups, and the topology heads read only the one-to-one lanes topomlp_setA_r50_wo_yolov8.py. Card: TopoMLP.
• Fixed-target denoising in TopoFG. The authors argue that the topology supervision derived from matching changes between epochs. They therefore copy each ground-truth lane G = 5 times into noisy denoising queries, whose connectivity labels are the ground-truth matrix in block-diagonal form. These groups are used only in training 2511.12590 §3.4 2511.12590 §4.2. In their ablation, adding this denoised topology reasoning alone raises OLS from 45.8 to 47.3 2511.12590 tab. 6. Card: Fine-Grained Representation for Lane Topology Reasoning.

When to use which

The card for each paper has the numbers and the hardware they were measured on. Cross-paper numbers come from different schedules and augmentation; compare within a table only.

Implementation sketch

The common core is the matching step and the loss on matched pairs. Variants differ in the cost weights, in how candidate pairs are restricted, and in whether extra groups are added during training.

# Match N predictions to M ground-truth objects, M <= N   [arxiv:2005.12872 §3.1]
def match(pred_probs, pred_boxes, gt_classes, gt_boxes):
    # Cost matrix, rows = predictions, columns = objects
    # Class term uses probability, not log-probability
    cost_class = -pred_probs[:, gt_classes]              # (N, M)
    # Box term: L1 between predicted and ground-truth boxes
    cost_box = l1_cdist(pred_boxes, gt_boxes)            # (N, M)
    # Weights are not stated in the paper; set them and say which you used
    cost = w_class * cost_class + w_box * cost_box       # (N, M)
    # One-to-one assignment with minimum total cost   [arxiv:2005.12872 eq. 1]
    rows, cols = hungarian(cost)                         # M pairs
    return rows, cols


# Loss on matched pairs; unmatched predictions learn "no object"
# [arxiv:2005.12872 §3.1] [arxiv:2005.12872 eq. 2]
def set_loss(logits, pred_boxes, gt_classes, gt_boxes, rows, cols):
    target = full(N, NO_OBJECT)                          # (N,)
    target[rows] = gt_classes[cols]
    # No-object class is down-weighted (1/10 in DETR)
    cls_loss = cross_entropy(logits, target, no_object_weight=0.1)
    # Box loss only on matched pairs
    box_loss = l1(pred_boxes[rows], gt_boxes[cols])      # plus GIoU in DETR
    return cls_loss + box_loss

For one-to-many variants, match is run once more with each ground truth repeated K times, and that second group is trained with its own loss. Only the one-to-one group is kept for inference 2207.13080 tab. 1.

For fixed-target denoising, the labels of the noisy groups are the ground-truth matrix, so they are built directly from the annotations and not from match 2511.12590 §3.4.

Contradictions

• Is matching the bottleneck? 2011.10881 §3.1 reports that a matching distilled from a trained teacher helps only in the first epochs, and that the matching is unstable. 2011.10881 §3.2 puts the larger share on cross-attention sparsity. 2211.12860 §1 also reports unstable Hungarian matching, and adds that few positive queries leave the encoder and decoder cross-attention under-trained.

• Released code vs paper equations. 2011.10881 §4.1 defines the matching as a global minimum-cost permutation. The released TSP code takes the lowest-cost proposal for each object, which is a different rule. See the TSP card's Paper vs code section.

• Learned vs fixed association in tracking. 1604.03635 tab. 1 reports 24.0 MOTA for the Hungarian baseline (RNN_HA) and 22.3 for the learned LSTM association (RNN_LSTM) on the training set. The paper's test result uses RNN_LSTM, and it does not discuss the gap.

• Class term in the matching cost. Mask3D's paper writes the class term as cross-entropy 2210.03105 §3.1 2210.03105 eq. 4. The released matcher uses the negative softmax probability of the target class matcher.py. The Mask3D card's Paper vs code section records this. The mask and Dice terms match the paper.

• Matching cost: softmax vs sigmoid. TrackFormer's equations use a probability term and a cross-entropy loss 2101.02702 eq. 2 2101.02702 §3.3. The released deformable configs switch to sigmoid focal loss, and the matching cost switches to sigmoid as well. The TrackFormer card's Paper vs code section records this. Pick one path and state it.

• Classification term in TadTR's matching cost. The paper's default is cross-entropy 2106.10271 §III-B 2106.10271 §IV-A. The released matcher has only a focal-style cost, and the loss is focal only matcher.py tadtr.py. The TadTR card's Paper vs code section records this. The cross-entropy setting cannot be reproduced from the released code.

Papers

• End-to-End Object Detection with Transformers: introduces the Hungarian set loss for object queries and removes anchors and NMS.
• Rethinking Transformer-based Set Prediction for Object Detection: diagnoses slow DETR convergence and proposes TSP-FCOS and TSP-RCNN with restricted matching.
• Conditional DETR for Fast Training Convergence: conditional spatial query in cross-attention; matching is unchanged.
• DETR3D: one-to-one matching in 3D with queries projected into multi-view images.
• An End-to-End Transformer Model for Crowd Localization: crowd head points with a Hungarian matcher and a kNN-based cost term.
• BEVFusion: TransFusion-L head with Hungarian matching on fused bird's-eye-view features.
• DETRs with Hybrid Matching: training-only one-to-many query group on top of one-to-one matching.
• DETRs with Collaborative Hybrid Assignments Training: training-only one-to-many heads with classic assigners.
• OrientedFormer: DETR-style detector for rotated boxes, one-to-one Hungarian matching.
• End-to-End Video Instance Segmentation with Transformers: one-to-one matching of whole instance sequences across the frames of a clip.
• Online Multi-Target Tracking Using Recurrent Neural Networks: Hungarian association baseline and an LSTM association model for tracking.
• TrackFormer: Multi-Object Tracking with Transformers: track queries carry identity across frames; cost-based matching only for new objects.
• TopoMLP: A Simple yet Strong Pipeline for Driving Topology Reasoning: one-to-one lane and traffic matching, reused by lane-lane and lane-traffic topology heads.
• Fine-Grained Representation for Lane Topology Reasoning: per-point lane queries, Hungarian matching, and fixed-target denoising groups for lane connectivity.
• Mask3D: Mask Transformer for 3D Semantic Instance Segmentation: non-parametric queries over 3D point features, with Hungarian matching on mask and class costs.
• VisionLLM: Large Language Model is also an Open-Ended Decoder for Vision-Centric Tasks: an LLM decoder writes detection and mask outputs as tokens, with bipartite matching for set outputs.
• End-to-End Autonomous Driving through V2X Cooperation: roadside agent queries are Hungarian-matched into the vehicle's queries before planning.
• A Modern Take on Visual Relationship Reasoning for Grasp Planning: DETR-style detector with a dense graph transformer; relation loss on Hungarian-matched objects.
• End-to-end Temporal Action Detection with Transformer: one-to-one matching of learned action queries to action segments, with no anchors or NMS.