Multi-object trackers must decide, every frame, which new detection belongs to which existing track. Most frames are easy: targets are well separated and a single cheap matching step gets them right. A few moments are hard, such as two dancers in identical costumes crossing paths or a crowd briefly merging behind a pillar. A method that treats matching as a sampling problem can fix exactly these moments. It proposes swaps and reassignments over a short window of past frames and keeps the ones the data support. Deployed samplers of this kind, however, spend the same number of steps on every frame. They also cannot be stopped early without risking an unusable answer. This note proposes a tracker that runs a cheap matcher by default and hands only the tangled groups of targets to a sampler. The sampler can be interrupted at any moment and still return a valid answer. It divides a fixed per-frame time budget across those groups using signals the sampler already produces as a byproduct, so deciding where to spend time costs almost nothing.
The opportunity matters because the two usual responses each fail on one side. Fast trackers based on box overlap and motion reach high throughput but cannot revise an identity mistake once it is made. Global association solvers can revise mistakes but spend uniformly and break under hard deadlines. The metareasoning literature adds a third warning: a controller that decides how much to compute can itself eat the savings. The claim here is concrete. Chain-internal convergence signals, computed from two short parallel chains per ambiguous group, are enough to allocate sampling effort across groups and to stop early. The controller costs a negligible fraction of frame time and uses no learned difficulty predictor. Compared with uniform-budget sampling at equal wall-clock time, it should give better identity accuracy on crossing-heavy video.
Background and the gap
Markov chain Monte Carlo data association (MCMCDA) builds a random walk over possible assignments of measurements to tracks. It uses moves that split, merge, or swap track segments, so that frequently visited assignments approximate the posterior. The latent-property formulation of Tracking Many Objects with Many Sensors and the sliding-window distributed version in Distributed Multitarget Tracking and Identity Management establish that this avoids the combinatorial blowup of exhaustive multiple-hypothesis tracking. Both run a fixed number of steps over a fixed window, and that uniform budget is the design choice we change. Approximating the Permanent by Sampling from Adaptive Partitions makes each sample far more efficient, reporting lower error with 10x fewer samples in a tracking simulation. It is complementary rather than competing, because it says nothing about when to stop or where to spend. Joint Probabilistic Data Association Revisited shows that the top roughly 100 assignments carry almost all probability mass. It too uses the same $m$ for every frame, and its integer-programming search cannot be cut off mid-run with a guaranteed answer.
The allocation idea comes from language-model inference. Escape Sky-high Cost stops self-consistency sampling once a window of samples fully agrees, cutting samples by 33.8% on MATH and 80.1% on GSM8K at near-unchanged accuracy. Learning How Hard to Think trains a probe that predicts how much extra computation will help and matches best-of-$k$ with half the samples. We reuse the idea of a stopping rule computed from the samples themselves. We reject exact agreement as the criterion, because it contains a trap the input-adaptive literature already flags. A genuinely ambiguous crossing has a posterior with two real modes. An agreement rule would never fire on it and would pour the entire budget into an instance that more samples cannot resolve. Our rule instead asks whether the sampler's estimate has stopped changing, even if that estimate is uncertain.
The metareasoning work constrains the design. Ideal Partition of Resources for Metareasoning shows that deliberation pays off only when the cost of computing the allocation itself is negligible. When Does Bounded-Optimal Metareasoning Favor Few Cognitive Systems? shows that the cost of choosing among many strategies favors a small repertoire, typically two. Allocating Planning Effort When Actions Expire finds that exact deadline-aware scheduling is PSPACE-complete, while a greedy real-time rule balancing urgency and efficiency does best in practice. Together these fix our architecture: exactly two systems, a greedy scheduler, and a controller whose cost we measure rather than assume. Tempora supplies the evaluation lens. It shows that a method winning 10 of 15 corruptions offline lost in 87.9% of time-constrained evaluations. Deadline-free accuracy is therefore the wrong yardstick.
Core Claim
Split each frame's gating graph into connected components, meaning groups of tracks and detections that could plausibly be matched to one another. Solve every component with the cheap matcher used by a strong overlap-based tracker. Escalate a component to sampling only if the cheap solution is not clearly dominant. Concretely, escalation happens when the cost gap between the best and second-best assignment, which the matcher can report at trivial extra cost, falls below a threshold. Each escalated component runs two chains, both initialized from the cheap solution and differing only in random seed. Components are advanced in small step batches. After each batch the scheduler computes, per component, the total-variation distance $D_c$ between the two chains' windowed estimates of the per-track assignment marginals. It gives the next batch to the component with the largest recent rate of decrease in $D_c$, a greedy marginal-value rule in the spirit of Shperberg et al. A component retires when $D_c$ falls below a tolerance $\epsilon$. Running two chains lets the rule separate a sampler that has not mixed, where the chains disagree, from a posterior that is genuinely split, where the chains agree on uncertain marginals. A single-chain agreement rule cannot make this distinction.
Interruptibility comes from what the tracker outputs when the frame deadline hits. For each component it returns the highest-posterior assignment seen so far across both chains. Because both chains start at the cheap solution, this output is never worse than the cheap solution under the model posterior, whenever it is interrupted. Monotone improvement in model posterior is guaranteed. Improvement in benchmark metrics is the empirical question.
Research Program
We will build the tracker on top of OC-SORT's motion model and cost matrix, so the cheap system is literally OC-SORT and every gain is attributable to escalation. The sampler follows the move set of People Tracking with Anonymous and ID-Sensors and the swap moves of the latent-property work, run over a sliding window of $W$ frames. This lets it repair identity assignments made up to $W$ frames earlier, something frame-by-frame matching cannot do.
The analysis has three parts. The first is instrumentation. We will time the escalation test, the $D_c$ computation, and the scheduler separately from the sampling itself, and report their share of frame time as a direct measurement of the meta-meta cost Horvitz and Breese define. Our target is under 5%, and we will report the number whatever it turns out to be. The second is a calibration study on synthetic scenes small enough to enumerate the exact posterior. It will check whether $D_c$ tracks true error in the marginals, and whether retired components are actually converged or merely stuck in the same wrong mode in both chains. The third maps performance profiles: model posterior and identity accuracy versus steps, per component type. The file's anytime literature notes that combinatorial search often has flat, stepwise quality curves. If ours look like that, the greedy rate-of-decrease rule is at risk, and we would switch to allocating by current $D_c$ weighted by component size.
Baselines
The naive reference is OC-SORT itself with no escalation, using the same detections. On DanceTrack it is the strongest cited overlap-based tracker: Observation-Centric SORT reports 54.6 HOTA on DanceTrack and 62.1 HOTA on MOT20, at over 700 frames per second on one CPU. HOTA is a combined score of detection and association quality. We will rerun it with the public detections and configuration so the comparison uses the same detector. Beating it means a statistically reliable gain in association accuracy (AssA), identity F1 (IDF1), and identity switches on DanceTrack at a per-frame latency within the deadline budgets described below. HOTA gains alone would not suffice, since detection quality is held fixed. On MOT17 the relevant reference is ByteTrack, which reports MOTA above 80.3 at 30 frames per second on a V100. MOTA is an accuracy score dominated by missed and false detections. Because its two-stage low-confidence matching is orthogonal to our method, we will also test ByteTrack as the cheap system.
The strongest direct competitor is uniform-budget sliding-window MCMCDA in the style of Oh et al., run on the same components with the same move set and window. We give it the identical wall-clock budget, spent as a fixed number of steps per escalated component, and tune its step count on the DanceTrack validation split with the same search budget we give $\epsilon$ and the escalation threshold. The file has no reported DanceTrack or MOT17 number for this method, so we produce it ourselves. Beating it means higher AssA at equal time, or equal AssA at lower time. The same protocol applies to m-best JPDA with fixed $m$, whose file-reported figure is about 32 frames per second on MOTChallenge, with no reported result found on Lacuna for DanceTrack.
Four ablations isolate the key ingredient. The first is static escalation plus a fixed budget: our escalation test with uniform steps and no adaptive scheduler. The second is single-chain window agreement, in the style of Escape Sky-high Cost, which tests whether the two-chain marginal criterion matters on genuinely bimodal crossings. The third is a learned difficulty predictor in the style of Learning How Hard to Think: a small network trained on component features to predict the gain from sampling, with its inference time charged to the budget. The fourth is an oracle allocation, computed offline from ground truth, which bounds how much any allocator could gain.
Why not just…?
Why not just use OC-SORT or ByteTrack and skip sampling entirely? These trackers are very fast, and on MOT17 or MOT20, where most frames are unambiguous, they may leave little to gain. The DanceTrack benchmark reports that trackers scoring about 60 to 70 HOTA on MOT17 fall to about 40 to 50 on DanceTrack, and the drop is concentrated in association. That drop is the failure mode a sampler with a multi-frame window targets. We expect little or no gain on MOT17 and will say so. The claim stands or falls on DanceTrack AssA and identity switches.
Why not just escalate by a fixed rule and give every escalated group the same number of steps? This is the most serious threat. The escalation test probably captures most of the value, and adaptive scheduling might add little on top. The first ablation measures exactly this. If it matches the full method within noise, we will report that the contribution reduces to cheap gating plus the anytime output guarantee, which is still new relative to uniform MCMCDA. We would then drop the scheduler claim. The PROTEAN results in Computational Costs versus Benefits of Control Reasoning, where one static control strategy lost time while another saved 14%, show that the answer is domain-specific rather than settled.
Why not just learn a difficulty predictor, as in language-model inference? Learned probes work there because the model's hidden states already encode difficulty for free. A tracker has no such representation, so a predictor must be built and run separately, and its cost counts against the budget. The third ablation charges this cost honestly. We expect the learned predictor to allocate somewhat better than the chain signals but to lose on net under tight deadlines.
Why not just run a stronger fixed solver such as m-best JPDA? It spends uniformly across frames and cannot return a guaranteed answer when interrupted mid-search. Under the discrete-deadline protocol, its missed-deadline frames fall back to the cheap solution, and we measure how often that happens.
Proposed Experiments
We evaluate on DanceTrack as the primary benchmark, with MOT17 and MOT20 as controls, and on a synthetic crossing simulator with exact posteriors for calibration. Following Tempora, each method runs under three time regimes. In the hard-deadline regime, a frame that misses its budget outputs the cheap solution. In the degrading regime, accuracy is discounted with latency. In the fixed-compute regime, total time is capped over each sequence. Budgets range from 1 to 30 ms per frame on both a desktop CPU and a Raspberry Pi 5-class CPU, and interrupt times are drawn from the uniform, normal, and Poisson deadline families used by Shperberg et al.
The decisive checks are four. First, at equal wall-clock time, the full method must beat uniform MCMCDA on DanceTrack AssA and identity switches. Second, the controller's measured share of frame time must stay small enough that the gain survives charging it. Third, on synthetic bimodal crossings, two-chain stopping must retire components that single-chain agreement keeps sampling indefinitely, while achieving equal marginal error against the exact posterior. Fourth, the gap between the full method and static escalation must be measured with confidence intervals across sequences. That last result decides whether adaptive allocation earns its place or whether cheap gating was the whole story.
References
- Tracking Many Objects with Many Sensors
- Distributed Multitarget Tracking and Identity Management
- Approximating the Permanent by Sampling from Adaptive Partitions
- Joint Probabilistic Data Association Revisited
- Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation
- Ideal Partition of Resources for Metareasoning
- When Does Bounded-Optimal Metareasoning Favor Few Cognitive Systems?
- Allocating Planning Effort When Actions Expire
- Tempora: Characterising the Time-Contingent Utility of Online Test-Time Adaptation
- People Tracking with Anonymous and ID-Sensors Using Rao-Blackwellised Particle Filters
- Observation-Centric SORT: Rethinking SORT for Robust Multi-Object Tracking
- ByteTrack: Multi-object Tracking by Associating Every Detection Box
- DanceTrack: Multi-Object Tracking in Uniform Appearance and Diverse Motion
- Computational Costs versus Benefits of Control Reasoning