--- kind: concept slug: bipartite-matching title: Bipartite matching for set-prediction losses summary: >- Trains a model that outputs an unordered set by pairing each ground-truth element with one prediction via a minimum-cost assignment (Hungarian algorithm), then applying the loss to those pairs; unmatched slots learn "no object". It replaces anchors and NMS in detection, at the price of slow convergence and a fixed cap on outputs. Variants add one-to-many supervision during training. tags: [object-detection, loss-function, set-prediction, training, tracking] papers: ["2005.12872", "2011.10881", "2011.14503", "2108.06152", "2110.06922", "2202.13065", "2205.13790", "2207.13080", "2211.12860", "2409.19648", "1604.03635", "2101.02702", "2310.06753", "2511.12590", "2305.11175", "2210.03105", "2404.00717", "2409.02035", "2106.10271"] related: [set-prediction, object-queries, label-assignment, object-detection, focal-loss, visual-object-tracking, recurrent-neural-network, instance-segmentation, multimodal-language-model, collaborative-perception, graph-transformer, scene-graph-generation, bev-representation] status: draft updated_at: 2026-11-01 --- ## 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" [arxiv: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 [arxiv: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 [arxiv:2011.10881 §4.1], and tracking matches predicted target states to detections [arxiv:1604.03635 §Method]. TrackFormer goes further and keeps identity out of the assignment for tracked objects: only new objects are matched by cost [arxiv: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 [arxiv:2011.14503 §3.2]. Mask3D matches predicted instance masks against ground-truth masks, scored by Dice and BCE terms rather than by boxes [arxiv: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 [arxiv:2005.12872 §3.1] [arxiv:2005.12872 §3.2]. The reported result is 42.0 AP on COCO val with ResNet-50 after 500 epochs [arxiv:2005.12872 tab. 1]. Card: [End-to-End Object Detection with Transformers](/papers/2005.12872). ### 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 [arxiv:2108.06152 §3.5]. It reaches 40.9 AP after 50 epochs, against 34.9 for DETR at the same length [arxiv:2108.06152 tab. 1]. Card: [Conditional DETR for Fast Training Convergence](/papers/2108.06152). 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 [arxiv:2011.10881 §4.1]. Card: [Rethinking Transformer-based Set Prediction for Object Detection](/papers/2011.10881). ### 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 [arxiv:2202.13065 tab. 8]. Card: [An End-to-End Transformer Model for Crowd Localization](/papers/2202.13065). - **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 [arxiv:2110.06922 §3.3] [arxiv: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](/papers/2110.06922). - **Fusion with a query head.** BEVFusion's TransFusion-L head seeds 200 queries from a heatmap and matches them with the Hungarian method [arxiv:2205.13790 §3.4]. Card: [BEVFusion](/papers/2205.13790). - **Lane topology.** TopoMLP runs one-to-one matching for its lane and traffic detection losses, then reuses that assignment for its two topology losses [arxiv:2310.06753 §3.5]. In the code, queries that are not matched get no topology supervision at all [code: projects/topomlp/models/heads/topo_ll_head.py#L143-L158]. Its reported OLS with ResNet-50 on OpenLane-V2 subset A is 38.2 [arxiv:2310.06753 tab. 1]. Card: [TopoMLP](/papers/2310.06753). - **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 [arxiv:2511.12590 §3.3] [arxiv:2511.12590 §3.4]. Lanes are matched one to one with the Hungarian method [arxiv:2511.12590 §3.4]. Its author-reported OLS on OpenLane-V2 subset_A is 48.0, against 44.1 for TopoLogic [arxiv:2511.12590 tab. 1]. Card: [Fine-Grained Representation for Lane Topology Reasoning](/papers/2511.12590). - **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 [arxiv:1604.03635 §Baseline comparison]. Card: [Online Multi-Target Tracking Using Recurrent Neural Networks](/papers/1604.03635). - **Oriented boxes.** OrientedFormer uses one-to-one Hungarian matching with a focal loss and a rotated-IoU term [arxiv:2409.19648 §3.6]. Card: [OrientedFormer](/papers/2409.19648). - **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 [arxiv:2305.11175 §3.4] [arxiv:2305.11175 app. B]. The matching cost and the tokenizer's query assignment are not stated [arxiv:2305.11175 app. B]. Its author-reported box AP is 44.6 with ResNet-50 and 60.2 with InternImage-H [arxiv:2305.11175 tab. 1]. Card: [VisionLLM](/papers/2305.11175). - **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 [arxiv:2210.03105 §3.1] [arxiv:2210.03105 eq. 4]. The reported ScanNet validation mAP is 55.2, against 49.4 for the best listed baseline [arxiv:2210.03105 tab. 1]. Card: [Mask3D](/papers/2210.03105). - **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 [arxiv:2011.14503 §3.2] [arxiv:2011.14503 eq. 2]. Its reported YouTube-VIS validation AP is 40.1 with ResNet-101 and 36.2 with ResNet-50 [arxiv:2011.14503 tab. 2]. Card: [End-to-End Video Instance Segmentation with Transformers](/papers/2011.14503). - **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 [arxiv:2404.00717 §Cross-view query matching]. The released code adds a per-axis box gate and a cost cut-off; the paper states neither [code: projects/mmdet3d_plugin/univ2x/fusion_modules/agent_fusion.py#L61-L66] [code: projects/mmdet3d_plugin/univ2x/fusion_modules/agent_fusion.py#L107]. Author-reported car mAP is 0.295 with fusion and 0.165 without [arxiv:2404.00717 tab. 3]. The reported ablations do not isolate the matcher. Card: [End-to-End Autonomous Driving through V2X Cooperation](/papers/2404.00717). - **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 [arxiv:2409.02035 §4.3] [arxiv:2409.02035 eq. 8] [arxiv:2409.02035 eq. 9]. Unmatched queries get no relation supervision in training, though relations are read for all queries at inference [code: models/detr_graph.py#L270-L300]. Author-reported synth-to-real AP_rel is 24.44 for DETR, against 13.36 for VMRN [arxiv:2409.02035 tab. 3]. The released relation loss is scaled differently from eq. 9 [code: models/detr_graph.py#L365-L374]. Card: [A Modern Take on Visual Relationship Reasoning for Grasp Planning](/papers/2409.02035). - **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 [arxiv:2106.10271 §III-B] [arxiv:2106.10271 eq. 6] [arxiv:2106.10271 eq. 7]. Ground truth is padded with a no-action symbol to N_q targets [arxiv:2106.10271 §III-B]. The authors' default classification cost is cross-entropy, and focal loss is used in their improved setting [arxiv:2106.10271 §III-B] [arxiv: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 [arxiv:2106.10271 tab. 1]. Card: [End-to-end Temporal Action Detection with Transformer](/papers/2106.10271). ### 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 [arxiv: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 [arxiv:2101.02702 §3.3] [arxiv:2101.02702 eq. 2] [arxiv:2101.02702 eq. 3]. The loss is then applied to all object and track predictions together [arxiv: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 [arxiv:2101.02702 tab. 3]. Card: [TrackFormer](/papers/2101.02702). ### 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 [arxiv:2207.13080 tab. 1]. Card: [DETRs with Hybrid Matching](/papers/2207.13080). - **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 [arxiv:2211.12860 §3.1]. Card: [DETRs with Collaborative Hybrid Assignments Training](/papers/2211.12860). - **Lane detection in TopoMLP.** The paper describes 300 one-to-one lane queries and no extra branch [arxiv:2310.06753 §3.1] [arxiv: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 [code: projects/configs/topomlp_setA_r50_wo_yolov8.py#L37-L40]. Card: [TopoMLP](/papers/2310.06753). - **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 [arxiv:2511.12590 §3.4] [arxiv:2511.12590 §4.2]. In their ablation, adding this denoised topology reasoning alone raises OLS from 45.8 to 47.3 [arxiv:2511.12590 tab. 6]. Card: [Fine-Grained Representation for Lane Topology Reasoning](/papers/2511.12590). ## When to use which | Situation | Use | Why | |---|---|---| | Need one output per object, no NMS, long training budget is fine | Original DETR matching | Reported 42.0 AP at 500 epochs [arxiv:2005.12872 tab. 1] | | Short training budget, same architecture | Conditional spatial query, or Deformable-DETR-style matching | 40.9 AP at 50 epochs vs 34.9 for DETR [arxiv:2108.06152 tab. 1] | | Encoder compute is the bottleneck | Restricted matching over a short proposal list | Authors report 43.1 AP at 36 epochs with 700 locations [arxiv:2011.10881 tab. 1] | | Few positives per object hurt convergence | Training-only one-to-many groups | Inference is one-to-one and unchanged [arxiv:2207.13080 tab. 1] | | Tracking with a fixed per-frame budget | Classical Hungarian step | The RNN_HA baseline scores 24.0 MOTA on the training set [arxiv:1604.03635 tab. 1] | | Tracking in one network, identities kept by the model | Track queries, with cost matching only for new objects | Authors' ablation: 71.3 vs 61.0 MOTA on the training split when track queries are removed [arxiv:2101.02702 tab. 3] | | Instance masks in a 3D point cloud, one query per object | Mask-level Hungarian matching with Dice and BCE costs | Author-reported 55.2 mAP on ScanNet validation against 49.4 for the best listed baseline [arxiv:2210.03105 tab. 1] | | Short video clip, one output per instance, no linking step | Sequence-level Hungarian matching over T frames | Authors report 40.1 AP with ResNet-101 on YouTube-VIS validation [arxiv:2011.14503 tab. 2]; the released inference script reads only the first 36 frames of a video [code: inference.py#L186-L189] | | Relations between detected instances (e.g. lane connectivity) on top of a set detector | Reuse the detection assignment for the relation losses | Relation losses then act only on matched queries [arxiv:2310.06753 §3.5] [code: projects/topomlp/models/heads/topo_ll_head.py#L143-L158]; authors report 38.2 OLS on subset A [arxiv:2310.06753 tab. 1] | | Pairwise relations must be trained on labels that do not move with the matching | Fixed-target denoising groups, training only | Authors report OLS 47.3 with denoised topology reasoning alone, against 45.8 without it [arxiv:2511.12590 tab. 6]; the paper reports no seeds or variance | | Several viewpoints each send a set of queries, and the planner needs one fused set | Hungarian matching on reference-point distance, then fuse matched pairs and append the rest | Author-reported car mAP 0.295 with fusion, 0.165 without [arxiv:2404.00717 tab. 3]; planning L2 is 3.48 m against 3.44 m with no fusion [arxiv:2404.00717 tab. 2], so the gain is in detection and collision rate, not L2 | | Object-to-object relations on a set detector, without per-pair crops | Relation head trained only on Hungarian-matched queries | Author-reported synth-to-real AP_rel 24.44 against 13.36 for VMRN [arxiv:2409.02035 tab. 3]; the paper calls OR and OP unstable there, with no validation set [arxiv:2409.02035 §6.3] | | Action segments in an untrimmed video, one output per action, no proposal or NMS stage | One-to-one Hungarian matching of learned action queries to segments | Author-reported HACS average mAP is 30.83 without NMS and 30.53 with NMS for the Transformer encoder [arxiv:2106.10271 tab. 5]; the released matcher has only a focal-style cost [code: models/matcher.py#L72-L77] | 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. ```pseudocode # 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 [arxiv: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` [arxiv:2511.12590 §3.4]. ## Contradictions - **Is matching the bottleneck?** [arxiv: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. [arxiv:2011.10881 §3.2] puts the larger share on cross-attention sparsity. [arxiv: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.** [arxiv: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.** [arxiv: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 [arxiv:2210.03105 §3.1] [arxiv:2210.03105 eq. 4]. The released matcher uses the negative softmax probability of the target class [code: models/matcher.py#L123]. 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 [arxiv:2101.02702 eq. 2] [arxiv: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 [arxiv:2106.10271 §III-B] [arxiv:2106.10271 §IV-A]. The released matcher has only a focal-style cost, and the loss is focal only [code: models/matcher.py#L72-L77] [code: models/tadtr.py#L277]. 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](/papers/2005.12872): introduces the Hungarian set loss for object queries and removes anchors and NMS. - [Rethinking Transformer-based Set Prediction for Object Detection](/papers/2011.10881): diagnoses slow DETR convergence and proposes TSP-FCOS and TSP-RCNN with restricted matching. - [Conditional DETR for Fast Training Convergence](/papers/2108.06152): conditional spatial query in cross-attention; matching is unchanged. - [DETR3D](/papers/2110.06922): one-to-one matching in 3D with queries projected into multi-view images. - [An End-to-End Transformer Model for Crowd Localization](/papers/2202.13065): crowd head points with a Hungarian matcher and a kNN-based cost term. - [BEVFusion](/papers/2205.13790): TransFusion-L head with Hungarian matching on fused bird's-eye-view features. - [DETRs with Hybrid Matching](/papers/2207.13080): training-only one-to-many query group on top of one-to-one matching. - [DETRs with Collaborative Hybrid Assignments Training](/papers/2211.12860): training-only one-to-many heads with classic assigners. - [OrientedFormer](/papers/2409.19648): DETR-style detector for rotated boxes, one-to-one Hungarian matching. - [End-to-End Video Instance Segmentation with Transformers](/papers/2011.14503): one-to-one matching of whole instance sequences across the frames of a clip. - [Online Multi-Target Tracking Using Recurrent Neural Networks](/papers/1604.03635): Hungarian association baseline and an LSTM association model for tracking. - [TrackFormer: Multi-Object Tracking with Transformers](/papers/2101.02702): track queries carry identity across frames; cost-based matching only for new objects. - [TopoMLP: A Simple yet Strong Pipeline for Driving Topology Reasoning](/papers/2310.06753): one-to-one lane and traffic matching, reused by lane-lane and lane-traffic topology heads. - [Fine-Grained Representation for Lane Topology Reasoning](/papers/2511.12590): per-point lane queries, Hungarian matching, and fixed-target denoising groups for lane connectivity. - [Mask3D: Mask Transformer for 3D Semantic Instance Segmentation](/papers/2210.03105): 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](/papers/2305.11175): an LLM decoder writes detection and mask outputs as tokens, with bipartite matching for set outputs. - [End-to-End Autonomous Driving through V2X Cooperation](/papers/2404.00717): roadside agent queries are Hungarian-matched into the vehicle's queries before planning. - [A Modern Take on Visual Relationship Reasoning for Grasp Planning](/papers/2409.02035): DETR-style detector with a dense graph transformer; relation loss on Hungarian-matched objects. - [End-to-end Temporal Action Detection with Transformer](/papers/2106.10271): one-to-one matching of learned action queries to action segments, with no anchors or NMS.