Trap-Free Gradient Solvers for Lifted Multi-Object Tracking

Tracking many people through a crowded video means deciding, for every detected box in every frame, which person it belongs to. The best-performing formulations treat this as a single global puzzle over the whole video rather than a chain of frame-by-frame guesses. They also add long-range "lifted" links that reward keeping one identity across a gap of many frames. That puzzle is NP-hard. Exact integer-programming solvers take tens of minutes per sequence and cannot handle the densest benchmarks. The scalable alternative splits the problem into small pieces coordinated by prices, but it must then round its fractional answer back into actual tracks using a local-search heuristic that has no guarantees.

We propose a third route. Write tracking as a smooth energy over continuous edge variables in $[0,1]$ and minimize it with plain projected gradient descent on a GPU. The penalty terms are shaped so that every point where gradient descent can stop is a valid set of non-overlapping tracks. Per-constraint Lagrange multipliers, which act as prices that rise only where a constraint keeps being violated, keep those penalties small enough for float32 arithmetic. In two sentences: recent theory says quadratic penalties can be built so that every local minimum is binary and feasible, but only at huge static penalty weights and never for tracking graphs. We extend that construction to lifted disjoint paths and replace the huge static weights with small adaptive ones, giving a rounding-free solver whose only remaining failure mode is choosing a worse valid solution.

Core Claim

Local Minima in Quadratic-Penalty Relaxations of Binary Linear Programs proves three sufficient conditions under which every local minimizer of a penalized relaxation on $[0,1]^n$ is binary and feasible. The first, diagonal-free structure (C1), rewrites $x_i^2$ terms as $x_i$. The second, integer-valued penalty gradients (C2), rules out interior stationary points. The third, local repairability (C3), requires that any infeasible binary point has a single coordinate flip that lowers the penalty. The paper shows naive penalties often return 0% feasible solutions despite massive weights, while theory-guided ones reach 100% feasibility on mining, knapsack and TSP. Its thresholds can reach $10^{16}$, however, and it never touches tracking. This paper is the primary source of our method and also sets our main risk: precision.

Our claim has two parts. First, the lifted disjoint paths problem admits a penalty encoding that satisfies C1–C3. We encode it with auxiliary reachability variables $r_{uw}$, meaning "detection $w$ lies on the same track as detection $u$", restricted to the lifted time window, and tie them to base edges $y_{pw}$ by the recursion $r_{uw} = \sum_p r_{up}\, y_{pw}$. This sum is exactly a logical OR because each node has in-degree at most one. The recursion is quadratic, and making it diagonal-free and repairable is the non-trivial new theory. Second, per-constraint augmented Lagrangian updates, restricted to integer steps so that C2 survives, reach a locally correct regime at multiplier values far below the global worst-case threshold. The energy is

$$E(y,r) = c^\top y + \ell^\top r + \sum_k \Big[\lambda_k\, g_k(y,r) + \tfrac{\rho_k}{2}\, \widetilde{g_k^2}(y,r)\Big],$$

where $c$ and $\ell$ are base and lifted edge costs, $g_k$ is the $k$-th constraint residual (flow conservation, in/out-degree, reachability), and $\widetilde{g_k^2}$ is its square with diagonal terms cancelled. The multipliers are updated by the integer dual step $\lambda_k \leftarrow \lambda_k + \lceil \rho_k\, g_k \rceil$.

Two earlier results motivate the second part. A subgradient approach for constrained binary optimization via quantum adiabatic evolution found that dynamic multipliers settle 3x to 5x below theoretical static bounds, though only at $n=30$ and only on annealing hardware. Adiabatic Quantum Graph Matching with Permutation Matrix Constraints showed that giving each row its own penalty preserves landscape quality better than one global weight. We carry both ideas from small quantum instances to a GPU gradient solver on graphs with millions of edges.

Relation to Existing Solvers

The closest tracking work is Making Higher Order MOT Scalable (ApLift). ApLift uses Lagrangean decomposition into inflow, outflow, path and cut subproblems, solved by message passing with cutting planes, and it recovers tracks by min-cost flow followed by heuristic path splitting and merging. We share its reliance on prices but differ in where feasibility comes from. In ApLift it comes from post-hoc rounding. In our solver it is built into the landscape, so gradient descent terminates only at valid tracks.

Lifted Disjoint Paths with Application in Multiple Object Tracking supplies the problem and its exact Gurobi solution. We use it as the optimality reference. Target Identity-aware Network Flow relaxed mutual exclusion into $K$ shortest-path subproblems with hand-tuned overlap penalties and no lifted edges. It shows that price-based exclusion works for tracking, but it also shows the cost of hand-tuning, which our adaptive multipliers are meant to remove. Q-FW removes manual penalty tuning with an augmented-Lagrangian Frank-Wolfe on static matching problems, needing 200–1000 iterations. We borrow its augmented Lagrangian, but our inner solver is first-order gradient descent on a structured energy rather than a convex copositive lift.

Research Program

The first stage is theory. We will prove that the base disjoint-paths constraints satisfy C3; the key case is repairing a node with an in-edge but no out-edge by switching on its edge to the sink. We will then construct a diagonal-free reachability penalty and either prove C3 for it or identify the minimal extra auxiliary variables needed. We will also characterize the per-constraint multiplier threshold in terms of local edge costs. Our expectation is that the threshold scales with the largest cost incident to the constraint's variables rather than with global cost sums, since C3 needs only a local flip to dominate local objective changes. That would explain why small adaptive weights suffice.

The second stage is engineering. We will build a sparse GPU implementation with windowed reachability, projected Adam or PGD inner loops, and outer multiplier updates.

The third stage is empirical. We will verify local correctness on small graphs by running thousands of random initializations and counting terminations at infeasible or fractional points. We will then scale to MOT17 and MOT20.

Baselines

The naive reference is frame-to-frame Hungarian matching on the same detections and costs. It measures what the global lifted model buys in the first place. The LifT paper shows the value of lifted edges on MOT17: identity switches drop from 2072 to 1189 and IDF1 rises from 52.3 to 65.6.

The exact reference is the Gurobi solver from LifT. It reports MOTA 60.5 and IDF1 65.6 on MOT17 at 26.6 minutes per sequence. We will run it on MOT17 without a time limit to obtain optimal energies, and under matched wall-clock budgets to measure anytime quality.

The strongest competitor is ApLift. It is the only published scalable solver for exactly this objective. It reports MOT20 MOTA 58.9 and roughly 36 seconds versus more than 2800 seconds for exact LifT on a 200-frame sequence. We found no ApLift MOT17 accuracy figure on Lacuna. Fairness is the crux here. We will feed both solvers identical detections, identical base and lifted edge costs taken from ApLift's pipeline, and identical time windows, and compare them at equal wall-clock time on the same GPU/CPU node. That way any difference comes from the solver alone. Beating ApLift means reaching lower primal energy at equal time on MOT17 and MOT20, with MOTA and IDF1 at least matching 58.9 MOTA on MOT20. An energy improvement that yields no metric gain would still be reported, as a solver result rather than a tracking result.

Two ablations isolate the key ingredients. The first is our locally correct penalty with a static global weight at the theoretical threshold, run in float64 and in float32; this is exactly the method of Huang et al. applied to our encoding. The second is a naive, non-diagonal-free quadratic penalty with the same adaptive multipliers. The first ablation isolates the adaptive multipliers. The second isolates the penalty geometry.

Why not just…?

Why not just use ApLift? ApLift is a real threat. On MOT17-scale problems its rounding heuristic may already be near-optimal, and in that case our contribution shrinks to a GPU speedup. The paper evaluates only tracking accuracy and runtime, not the energy gap left by rounding. We will measure that gap directly against Gurobi optima on MOT17. If ApLift's gap is negligible, we will report that and reposition the work around float32 scalability on MOT20.

Why not just use Huang et al.'s static penalty in float64? This is the most dangerous alternative. If double precision makes $10^{16}$-scale weights harmless for tracking-sized costs, the adaptive multipliers are unnecessary. The ablation above settles it. We will also report whether large static weights flatten the objective enough to degrade solution quality, the effect described by Glos et al., even when feasibility holds. Even if this alternative matches ours on accuracy, the lifted-reachability encoding remains new, because Huang et al. give no tracking formulation.

Why not just use an end-to-end transformer tracker? Trackers like TransTrack (MOT20 MOTA 64.5%) and MeMOTR (MOT17 HOTA 58.8%) use different detectors, so their numbers are not solver comparisons. MeMOTR's authors note that dense scenes still bottleneck detection, and that newborn detection queries still conflict with existing track queries. We will run our solver on top of a transformer's detections as a secondary experiment. That tests whether explicit exclusion plus lifted consistency adds identity accuracy, but we do not claim to beat these systems end to end.

Why not just use random restarts or annealing on a naive penalty? Restarts at equal compute are included as a baseline. The evidence from Huang et al., where naive penalties often produced 0% feasible solutions, suggests that restarts cannot repair a broken landscape. They only resample it.

Proposed Experiments

The first decisive check is local correctness. On small synthetic track graphs and short MOT17 clips, at least 99.9% of gradient-descent runs from random starts should terminate binary and feasible under our encoding, versus near-zero under the naive penalty. A persistent class of infeasible terminations would falsify the C3 construction for reachability and send us back to the theory.

The second is precision. We will record the final multiplier magnitudes and check that float32 matches float64 energies. We expect the magnitudes to be orders of magnitude below the static threshold, following the direction of the 3x–5x result in Karimi & Ronagh.

The third is quality at equal time. We will plot energy gap to the Gurobi optimum against wall-clock time on MOT17 for our solver, ApLift, and time-limited Gurobi, then report MOTA, IDF1, HOTA and identity switches. On MOT20, where exact solutions are unavailable, we will compare energies and metrics against ApLift's 58.9 MOTA. Density on MOT20 averages 246 pedestrians per frame (MOT20), which is where GPU parallelism should matter most.

The fourth probes the remaining failure mode, poor feasible minima. We will measure how often multiplier updates move the solver out of one feasible basin into a lower-energy one, compared with restarts under the same budget.