Training Tracker Association Costs at Near-Hard Matching in Dense Crowds

Multi-object trackers decide at every frame which new detection belongs to which existing track. When the scoring function behind that decision (the "association cost") is learned end to end, a trick is needed, because hard one-to-one matching has zero gradient almost everywhere. Prior work smooths the matching problem, for example with entropy (the Sinkhorn algorithm) or a quadratic penalty. It then backpropagates through the smoothed solution using implicit differentiation: the gradient is computed from the optimality conditions at the solution, without replaying the solver's iterations. The catch is that at test time the tracker still uses hard matching. In a sparse scene, the smooth training-time matching and the hard test-time matching nearly agree. In a dense crowd, many candidates sit within a few pixels of each other, and the two can disagree badly. The costs are then tuned for a problem the tracker never solves.

We propose to train association costs with the smoothing turned down almost to zero, so that training sees the same near-hard matching that inference uses. This is currently impractical because the linear system inside the implicit gradient becomes severely ill-conditioned as smoothing vanishes and as the number of targets grows. Unrolled solvers, meanwhile, need a number of iterations, and therefore memory, that grows as smoothing shrinks. Our method exploits the fact that in tracking the matching problem is spatially sparse. After gating by predicted motion, each track has only a handful of plausible detections. At low smoothing the problem therefore splits into many small, nearly independent pieces. Solving and stabilizing the gradient system piece by piece makes both the cost and the conditioning depend on local crowd structure rather than on the total number of people in the frame. The hypothesis is testable: the benefit of learned costs over hand-designed ones should grow with crowd density, but only when training uses low smoothing.

Core Claim

In dense multi-target tracking, the useful quantity is the mismatch between the training relaxation and the test-time matcher, not the choice of relaxation. We expect three results. First, the rate at which the smoothed plan's row-wise argmax disagrees with the Hungarian solution (the standard exact algorithm for one-to-one matching) grows with crowd density at any fixed smoothing level. Second, costs trained at large smoothing lose most of their advantage over hand-crafted motion costs on MOT20 and DanceTrack. Third, stabilized, sparsity-exploiting implicit differentiation makes near-zero smoothing trainable at MOT20 densities, and training there recovers the advantage.

The new part is the regime, reached through a specific numerical construction. Implicit differentiation through a smoothed matcher for tracking is not new in itself.

Relation to Prior Work

Two tracking papers supply the template we build on. Deep Network Flow for Multi-object Tracking casts association as min-cost flow, smooths it with log-barriers, and learns edge costs through implicit differentiation. It reports KITTI MOTA of 74.19% against 73.75% for hand-crafted costs, but it can only run over short sliding windows. Learning of Global Objective for Network Flow in Multi-Object Tracking (LPT) replaces the barrier with quadratic Tikhonov damping and differentiates the Karush-Kuhn-Tucker conditions, the optimality conditions of a constrained problem. Its central finding motivates us directly: costs trained on local frame pairs are mismatched to a global solver used at test time. LPT fixes a mismatch in temporal scope. We target a second mismatch it leaves open, in smoothing level. LPT itself notes that its damping strength is tuned empirically and that its KKT system becomes expensive at crowd scale. Both papers also build costs mainly from appearance features.

That design choice runs into a constraint. DanceTrack shows that appearance re-identification features become entangled when targets look alike: trackers fall from roughly 60–70 HOTA on MOT17 to roughly 40–50 on DanceTrack. OC-SORT reaches 54.6 HOTA on DanceTrack and 62.1 on MOT20 using purely geometric, observation-centric motion cues. We therefore build our costs mainly from motion and geometry, with appearance entering only through a learned gate.

Two optimal-transport papers supply the numerical method. Re-basin via implicit Sinkhorn differentiation differentiates the Sinkhorn fixed point implicitly, but only for static weight-permutation matching at moderate smoothing. Robust First- and Second-Order Differentiation for Regularized Optimal Transport shows that the implicit-gradient matrix becomes ill-conditioned as smoothing goes to zero or sample size grows. It reports a 97% failure rate for naive implicit differentiation in singular cases, and it stabilizes the solve with truncated singular value decomposition, which discards the smallest singular directions. We reuse that stabilization, but apply it per connected component of a sparse gated graph rather than to one dense system. This is what makes it affordable at MOT20 scale, where the benchmark averages 246 pedestrians per frame (MOT20).

SoDA offers a different route: soft attention over a temporal window, with an occlusion token. It is differentiable by construction but does not enforce one-to-one matching.

Research Program

The association layer works as follows at each frame. It matches $n$ predicted tracks to $m$ detections, and is augmented with one dummy row and one dummy column that absorb births, deaths, and missed detections. The costs $C_\theta$ come from a small network whose inputs are observation-centric motion residuals in the style of OC-SORT, generalized intersection-over-union, detection score (so that the low-score boxes that ByteTrack shows are often occluded people can be used), and a gated appearance distance. The layer returns

$$P_\varepsilon = \arg\min_{P \ge 0,\; P\mathbf{1}=a,\; P^\top\mathbf{1}=b} \langle C_\theta, P\rangle - \varepsilon \sum_{ij} P_{ij}(\log P_{ij}-1),$$

where $P$ is the soft assignment plan, $a$ and $b$ are the row and column masses including the dummies, and $\varepsilon$ is the smoothing strength. Entries outside a motion gate are fixed to zero, so $P$ is supported on a sparse bipartite graph.

The implicit gradient requires solving a linear system in the dual potentials, the Lagrange multipliers for the row and column constraints. The system matrix is

$$H = \frac{1}{\varepsilon}\begin{pmatrix}\mathrm{diag}(P\mathbf{1}) & P\\ P^\top & \mathrm{diag}(P^\top\mathbf{1})\end{pmatrix},$$

whose condition number grows as $\varepsilon \to 0$. This matches the ill-conditioning analyzed in the regularized-optimal-transport paper. The method rests on one observation. As $\varepsilon$ shrinks, entries of $P$ below a threshold $\tau$ become numerically negligible. $H$ then becomes block-diagonal over the connected components of the thresholded support graph, and in crowds these components are small clusters of mutually confusable people. We solve each block exactly with truncated singular value decomposition, at a cost cubic in the size of that block. Components that stay large are handled with a conjugate-gradient solver on the sparse matrix, preconditioned by the diagonal. The system has a known null direction, from the constant shift between the two potentials, which is removed explicitly.

The backward cost then scales with the number of gated edges and the sizes of the largest components, not with $(n+m)^3$. Memory does not depend on the number of Sinkhorn iterations. That number grows roughly like $1/\varepsilon$ in the forward pass, which is precisely what makes unrolling expensive at low smoothing.

Training rolls the tracker forward over clips of $T$ frames. The soft plan updates track states, so gradients flow through the short state recursion and through the per-frame implicit solves. The loss is a row-wise cross-entropy of $P_\varepsilon$ against ground-truth identities, summed over the clip. The value of $\varepsilon$ follows a schedule from large to a target $\varepsilon_{\min}$. We sweep $\varepsilon_{\min}$ as the main experimental variable. At test time the layer is replaced by the Hungarian algorithm on $C_\theta$, and track management follows OC-SORT, so that only the costs differ from the baseline.

Alongside the method, we will run a diagnostic study that needs no training. For fixed hand-crafted costs, we measure the disagreement rate between $\arg\max$ of $P_\varepsilon$ and the Hungarian solution as a function of $\varepsilon$ and of local crowd density (people per unit image area). The data come from MOT17, MOT20, and DanceTrack. If disagreement does not rise with density, the premise fails and we stop.

Baselines

The do-nothing reference is OC-SORT run on exactly our detections, with its hand-designed intersection-over-union and momentum costs and its standard Hungarian association. It is the strongest cheap competitor: it reports 62.1 HOTA on MOT20 and 54.6 HOTA on DanceTrack in Observation-Centric SORT, without any learning. Because detector quality dominates these numbers, we will re-run it rather than quote it. Beating it means a statistically reliable gain in HOTA and association accuracy on MOT20 and DanceTrack with the same detector and the same track-management logic. A gain concentrated in the densest sequences would be the telling pattern. MOT20-08, where the benchmark's own Faster R-CNN baseline reports only 20.76 MOTA in MOT20, is the natural stress case.

ByteTrack's two-stage association, which uses low-score boxes, is a second heuristic reference (ByteTrack; MOTA over 80.3 reported on MOT17). It will be re-run on the same detections.

The strongest learned competitor is LPT's approach: a Tikhonov-damped quadratic program differentiated through its KKT conditions (Learning of Global Objective for Network Flow in Multi-Object Tracking). It reports 57.3 MOTA and 57.7 IDF1 on MOT17 with public detections. We found no reported MOT20 numbers for it on Lacuna; the file states only that it ranked second in MOTA and IDF1 among its comparisons. We will reimplement its damped layer on our cost network, features, detections, and clip lengths, and give its damping strength the same tuning budget as our $\varepsilon_{\min}$.

The key ablation isolates the smoothing level. It uses our exact pipeline trained at a fixed large $\varepsilon$, which is the regime where the dense implicit solve is well conditioned and which matches how Sinkhorn implicit differentiation is used in Re-basin via implicit Sinkhorn differentiation. A second ablation keeps small $\varepsilon$ but replaces the per-component solve with naive dense implicit differentiation. It measures how often training diverges or yields gradients that disagree with finite differences, a failure the regularized-optimal-transport paper quantifies at 97% in singular cases. A third ablation trains the same cost network with local binary cross-entropy on frame pairs, which LPT found inferior on MOT17.

Why not just…?

Why not just use OC-SORT or ByteTrack and skip learning entirely? This is the most serious threat. The evidence for learned costs over hand-crafted ones is thin: DNF gains under half a MOTA point on KITTI (Deep Network Flow for Multi-object Tracking). OC-SORT is strong exactly where appearance fails. Our design concedes this by building costs from OC-SORT's own motion features, so learning only has to reweight and combine cues that heuristics already use. The density-stratified comparison settles it. If learned costs at small $\varepsilon$ do not beat OC-SORT in the densest strata of MOT20 and DanceTrack, the proposal's practical case fails, and we will report it that way.

Why not just unroll log-domain Sinkhorn at small smoothing? Unrolling stores every iteration. The survey Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective and Constraint-based graph network simulator both identify this memory cost as what caps solver depth. At low $\varepsilon$, convergence needs many iterations per frame, multiplied by frames per clip. Truncating the iterations instead yields an unconverged plan, reintroducing a training–test mismatch. We will measure peak memory, step time, and gradient error against finite differences for unrolled Sinkhorn with 10–200 iterations, alongside our solver, across the $\varepsilon$ sweep. Unrolling is competitive only if it reaches equal HOTA within the same GPU memory.

Why not just train soft attention, as SoDA does? SoDA shows real gains on Waymo, including a 30.8% reduction in identity switches over Tracktor. However, its attention does not stop two tracks from claiming the same detection, and it was reported as less dominant on MOT17. Duplicate claims are exactly the failure we expect to multiply in dense crowds. We will count duplicate and hallucinated assignments per frame, stratified by density, for a SoDA-style attention association head trained on our features.

Why not just train pairwise with binary cross-entropy and apply Hungarian matching at test time? LPT tested this on MOT17 and found that globally trained costs outperform it. Our pairwise ablation re-checks that finding on MOT20 and DanceTrack under motion-dominant features, where it has not been tested.

Proposed Experiments

Training uses the MOT17, MOT20, and DanceTrack training splits with one fixed public-quality detector shared by all methods, validated on held-out training sequences. Final numbers come from the test servers. KITTI tracking serves as a lower-density control, where we predict little difference across $\varepsilon$. Reported metrics are HOTA, association accuracy, IDF1, identity switches, and MOTA. We also report training memory and step time, backward-pass time as a function of crowd size, the gradient's relative error against finite differences, and the training–test assignment disagreement rate.

The decisive checks come in three steps. First, the training-free diagnostic must show disagreement between the soft and hard plans rising with density. Second, across the $\varepsilon_{\min}$ sweep, the HOTA gain of learned costs over OC-SORT should increase as $\varepsilon_{\min}$ falls on MOT20 and DanceTrack, while staying flat on KITTI. Dense naive implicit differentiation should fail in the same small-$\varepsilon$ region where our component-wise solver remains accurate. Third, backward time should track the size of the largest connected component, not the total detection count. This will be measured on MOT20 frames with up to several hundred people, and it is also the test that separates the association layer's cost from the other sources of the slowdown reported by FasterVideo.

If the second check fails, meaning low smoothing gives no gain even though it is trainable, then the mismatch hypothesis is wrong. The method would reduce to a faster implicit solver, still useful but a much smaller claim.