Learning Track Birth and Death Through a Truncated Interior-Point Flow Layer

Most multi-object trackers still decide when a track starts and when it ends with hand-set counters, such as "start a track after 3 consecutive detections, delete it after 5 missed frames." The counters survive even in trackers whose frame-to-frame matching is learned. A classical alternative writes tracking as a minimum-cost network flow: each object's trajectory is one unit of flow through a graph of detections, and entry and exit edges carry the cost of starting or ending a track. Those entry and exit costs are hand-tuned constants, and the exact solvers used on these graphs are discrete and give no gradient. We propose replacing the discrete solver with a few steps of an interior-point method. This is the continuous optimizer behind the recent sub-quadratic flow algorithms. It approaches the optimal flow from inside the feasible region, so it returns a smooth, fractional flow. A neural network then predicts the start, end, false-positive and skip costs for every detection, and the network is trained through the flow solution. Track lifecycle becomes a learned quantity that respects flow conservation, so no object can be in two places at once. It is not a counter.

What makes this cheap is a structural fact borrowed from the flow-theory literature. Each interior-point step, and the backward pass through the final iterate, amounts to solving one linear system in a weighted graph Laplacian, which is an "electrical flow" on the tracking graph. Tracking graphs are time-layered and sparse, so these solves are fast with preconditioned conjugate gradient on a GPU. Stopping at a moderate barrier strength rather than driving it to zero also sidesteps the ill-conditioning that makes full interior-point methods need high precision. The deliverable is not an almost-linear-time tracker. It is a differentiable, globally constrained lifecycle layer whose cost profile comes from that theory.

Core Claim

A sliding-window min-cost flow solved by a truncated log-barrier interior-point method can serve as a trainable association-and-lifecycle layer. The fractional flow through a detection's entry, exit and skip edges replaces count-based birth, death and suspension rules. Training end-to-end through this layer should beat two alternatives: the same graph with hand-tuned lifecycle costs solved exactly, and the same graph with costs learned edge-by-edge and then solved exactly. The gain should be largest on association accuracy under uniform appearance and long occlusions.

Concretely, over a window of $T$ frames we build the standard tracking graph. Each detection is split into an in-node and an out-node joined by a capacity-one edge, and the graph has transition edges across up to $T$ frames, source-to-detection (birth) edges, detection-to-sink (death) edges, and a zero-cost source-to-sink bypass so the number of tracks is free. With $x\in[0,1]^m$ the edge flows, $B$ the node-edge incidence matrix, $d$ the supply vector, and $c(\theta)$ the edge costs output by a network with parameters $\theta$, the layer returns

$$x^\star_\mu(\theta)=\arg\min_{Bx=d}\; c(\theta)^\top x-\mu\sum_{e}\big[\log x_e+\log(1-x_e)\big],$$

where $\mu>0$ is the barrier strength at which we stop. Implicit differentiation of the optimality conditions gives

$$\frac{\partial x^\star_\mu}{\partial c}=-\Big(H^{-1}-H^{-1}B^\top (BH^{-1}B^\top)^{-1}BH^{-1}\Big),$$

with $H$ the diagonal Hessian of the barrier at $x^\star_\mu$. The matrix $BH^{-1}B^\top$ is a weighted Laplacian of the tracking graph, so a backward pass costs one Laplacian solve, the same primitive as one Newton step forward. At inference, a track's state is read from flow values. A detection whose birth-edge flow is near one starts a track. A track whose flow mass is spread between a skip edge and a death edge stays "tentative" rather than being killed at frame 6. A single rounding step, using an exact solver on the final costs, produces the output identities.

Where This Sits in Prior Work

Several papers motivate the gap, and they show that the lifecycle is the stubborn heuristic. 3DMOTFormer learns track–detection association with an edge-augmented graph transformer, but its authors state that birth and death remain manual rules. Learnable Online Graph Representations for 3D Multi-Object Tracking runs neural message passing on a bipartite track–detection graph, which again learns edges but not lifecycle under global constraints. Automatic Topic Discovery for Multi-Object Tracking is cited for the failure of fixed counters under variable frame rates and long gaps. DanceTrack shows that appearance-reliant association collapses when targets look alike, which is exactly the regime where track continuity must come from global consistency rather than local similarity.

The flow-tracking line supplies the graph and the strongest exact solvers, and it constrains our claims. muSSP solves the tracking flow exactly and reports average speedups of 4,089x over successive shortest paths. FollowMe makes it online with a bounded sliding window that folds old trajectories into entry costs. An Approach for Multi-Object Tracking with Two-Stage Min-Cost Flow adds a second flow pass with confidence thresholds and an intersection mask. Lagrangian relaxation to min-cost flow adds higher-order constraints through repeated combinatorial solves. In all four, the costs, and thus the lifecycle, are engineered, and the solver gives no gradient. Because muSSP is already fast, we do not claim a speed win over it. Our claim is about what the costs can learn.

The optimization line supplies the method. Navigating Central Path with Electrical Flows and Computing Maximum Flow with Augmenting Electrical Flows show that interior-point steps for flow reduce to electrical flows, that is, Laplacian solves. Following the Path of Least Resistance gives weighted barriers that cut the iteration count to about $\sqrt{n}$, and we test whether its weighting helps at small iteration budgets. A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow exploits the stability of interior-point iterates across steps, and we reuse that idea only in a simple form, by warm-starting each window from the previous window's solution. We do not implement its expander and spanning-tree machinery, whose constants the file flags as impractical. An Integer Interior Point Method for Min-Cost Flow is a constraint: it documents that interior-point methods become numerically fragile as flows approach zero. That is part of our reason to stop at finite $\mu$, where $H$ stays well-conditioned in float32.

The in-context identity tracker MOTIP is the main contradicting evidence. It drops explicit matching entirely, learns newborn and continuing identities as classification, and is strongest on the file's uniform-appearance benchmarks. Our proposal has to beat or complement it, not ignore it. Our bet is that hard disjointness constraints over a multi-frame window add something that per-frame classification lacks. The experiments test that bet directly.

Research Program

The system has three parts. The first is a cost network. It takes per-detection features from a fixed detector and appearance/motion encoder, and pairwise features for transition edges. It outputs transition costs, a detection cost that lets the solver reject false positives, and per-detection birth, death and frame-skip costs. These lifecycle costs depend on context such as occlusion cues, image-border proximity and local density, rather than being global constants.

The second part is the flow layer. It runs a fixed small number of damped Newton steps on the barrier problem, each solved by Jacobi- or tree-preconditioned conjugate gradient on the Laplacian. It warm-starts from the shifted previous-window solution and stops at a chosen $\mu$. The backward pass uses the implicit formula above.

The third part is the training objective. Fractional flows are compared with ground-truth flows from annotated identities through a weighted squared error, plus a term on lifecycle edges so that births and deaths are not swamped by the many transition edges. The window is trained autoregressively on the model's own previous-window outputs, following the train–test mismatch argument made in 3DMOTFormer.

The analysis questions are concrete. How many Newton steps and which $\mu$ are needed before rounded outputs match the exact optimum of the same costs? Does Lee–Sidford-style edge weighting reduce that number? How does wall-clock time scale with detections per window compared with muSSP on the same graphs? Do learned lifecycle costs keep tracks alive through occlusions longer than any counter setting that is tuned on validation?

Baselines

The naive reference point is the same detector, features and window graph, with transition costs from the trained affinity network and hand-tuned constant birth, death and skip costs, solved exactly by muSSP. Its online variant uses the sliding window of FollowMe. The constants are grid-searched on the validation split with the same number of configurations we give our own hyperparameter search. muSSP reports speed rather than tracking accuracy, so no accuracy number for it exists on Lacuna. FollowMe reports MOTA 0.52 on KITTI-Car against 0.54 for batch SSP, which bounds how much a short window alone costs. Beating this baseline on HOTA and AssA with identical inputs is the minimum bar.

The strongest existing method on our main benchmark is MOTIP, which reports HOTA 69.6 on DanceTrack, 72.6 on SportsMOT and 70.5 on BFT. Its own tables list OC-SORT at 55.1 and MOTR at 54.2 HOTA on DanceTrack. We rerun MOTIP's released configuration with its Deformable DETR detector and feed our cost network the same detector outputs and backbone features, so the comparison isolates the association and lifecycle stage. Beating it means exceeding its rerun HOTA and AssA on DanceTrack test by more than seed-to-seed variation across three seeds, at no more than twice its per-frame latency. On 3D tracking the strongest method in the file is 3DMOTFormer, at AMOTA 68.2% and AMOTP 0.496 on nuScenes test, running at 54.7 Hz on a 2080Ti. Zaech et al. report 65.6% AMOTA. Here the fair test is surgical. We keep 3DMOTFormer's learned association and replace only its heuristic birth and death rules with our flow layer. Success is a reduction in identity switches without an AMOTA loss, at a frame rate that stays above 20 Hz.

Two ablations isolate the key ingredient. The first, a decoupled-learning ablation, trains the same cost network with per-edge supervised losses, birth and death included, and solves exactly with muSSP. Learned lifecycle costs are kept, but gradients through the global solution are removed. The second, a fixed-lifecycle ablation, trains end-to-end through the flow layer but freezes birth, death and skip costs to the tuned constants. Further sweeps cover $\mu$, Newton steps and window length $T$. TSMCF's reported MOTA of 79.2 on MOT17 is a reference point for heavily engineered flow pipelines. It uses a different detector, so we treat it as context rather than as a controlled comparison.

Why not just…?

Why not just use muSSP, which is already thousands of times faster than generic solvers? We do use it, for final rounding and as a baseline. Speed is not the claim. muSSP returns an exact discrete solution with no gradient, so any costs it consumes must be hand-tuned or learned through per-edge proxies. The decoupled-learning ablation is exactly "learned costs plus muSSP." If it matches the end-to-end layer, our central claim fails, and we will report that.

Why not just learn birth and death classifiers edge-by-edge and keep an exact solver? This is the most serious threat. Per-edge supervised learning is simpler and may capture most of the benefit. The argument against it is that a per-edge loss does not see how a cost error propagates through the conservation constraints. A slightly cheap death edge during a crossover can flip two identities, and that failure mode dominates on DanceTrack. The decoupled ablation settles this. We expect the gap to concentrate in AssA on crossover-heavy DanceTrack sequences, and we expect little gap on KITTI-Car, where motion is predictable.

Why not just use in-context identity prediction like MOTIP and skip flow entirely? MOTIP already learns newborn identities and is the number to beat. It does not, however, enforce that one detection carries one identity across a multi-frame window. Its authors also rely on injected occlusions and swaps during training to cope with error-contaminated history, and its fixed identity dictionary limits crowd size. A flow layer enforces disjointness by construction and has no dictionary size. MOTIP could nonetheless simply be better. Our test is head-to-head on shared detections, and we also report a hybrid in which MOTIP's identity logits become transition costs inside our layer. If the hybrid helps while our standalone tracker does not, then the contribution is the constraint layer rather than the whole tracker.

Why not just use a longer sliding window or a second cascaded flow pass? FollowMe's KITTI result shows that short windows lose little on vehicle motion. TSMCF shows that cascades with confidence splits raise MOTA. Both keep fixed thresholds, though, and neither learns from data when an occluded track should survive. The window-length sweep, run with the hand-tuned baseline at the same $T$, separates the effect of the longer horizon from the effect of learning lifecycle costs.

Proposed Experiments

The primary benchmark is DanceTrack, scored by HOTA, AssA and DetA, because uniform appearance makes global consistency matter most. SportsMOT and BFT serve as secondary checks against the MOTIP numbers above. MOT17 and MOT20 test transfer to crowded pedestrian scenes. MOT20 is also the stress test for window graphs with many simultaneous tracks, and on it we report solver time against muSSP as detections per window grow. nuScenes tests the lifecycle-swap experiment inside 3DMOTFormer. KITTI-Car connects us to the FollowMe numbers.

Four checks decide the outcome. First, the end-to-end layer must beat the decoupled-learning ablation on DanceTrack AssA. If it does not, gradients through the global flow are not worth having. Second, on DanceTrack validation sequences with annotated occlusions, we bin occlusion length. The learned lifecycle must reduce identity switches for gaps longer than the best-tuned counter, and the effect should rise with gap length. Third, rounded outputs from 10–20 warm-started Newton steps at the chosen $\mu$ should agree with the exact optimum of the same costs on nearly all edges, and float32 conjugate gradient should converge without the breakdowns that Becker et al. describe near the boundary. If agreement requires driving $\mu$ toward zero, the numerical argument fails. Fourth, swapping 3DMOTFormer's birth and death rules for the layer must cut identity switches on nuScenes without dropping below its reported AMOTA of 68.2%. A positive result on all four would show that the continuous machinery behind sub-quadratic flow algorithms is most useful in tracking as a way to learn the lifecycle rules that every current tracker still hand-writes, rather than as a faster solver.