Precedence-Swap Moves: Sampling Who-Goes-First in Joint Traffic Forecasts

When two cars approach the same unsignalized intersection, the future almost always splits into two clean stories: A goes first, or B goes first. The in-between story, where both enter the conflict zone together, is a collision and has essentially zero probability. A model that predicts the joint future of every agent in the scene therefore faces a probability landscape with isolated peaks separated by deep valleys, one peak per "precedence ordering." With many coupled conflicts the number of peaks grows as a product of factorials. Samplers that improve a joint scene by small local steps cannot cross those valleys. This family includes gradient-guided diffusion, Langevin refinement, and collision-repulsion guidance. They can nudge colliding trajectories apart, but they cannot turn "A first" into "B first."

We propose to borrow a trick from lifted probabilistic inference, the line of work that speeds up Markov chain Monte Carlo (MCMC) by jumping between states that a symmetry maps onto each other. The two precedence stories are approximately mirror images: the same spatial paths, with the two agents' time slots at the conflict zone exchanged. We turn that exchange into an explicit proposal, a "precedence swap" that re-times two agents so they trade places in the conflict zone. A Metropolis-Hastings accept/reject step corrects for the fact that the swap is only an approximate symmetry. The sampler then moves freely among precedence orderings without ever listing them. In the language of the first research direction, it simulates a lumped chain over orderings while running on raw trajectories. In the language of the second, it directly targets the exponential blow-up of joint modes and the ghost collisions that current joint forecasters still produce.

Core Claim

In interactive traffic, the joint future distribution is approximately lumpable by precedence ordering at conflict zones. Symmetry-derived swap proposals, corrected by Metropolis-Hastings, can sample the correct distribution over orderings in dense scenes. They do this at a small fraction of the cost of enumerating orderings, and they avoid the stuck-in-one-ordering failure of local and guided samplers. The measurable consequences are three: more joint scene modes covered at fixed sample budget (lower scene miss rate), fewer collisions without relying on repulsion heuristics, and ordering frequencies that match ground truth on controlled scenes.

Why the obvious bridge is the wrong one

The tempting intersection is to add agent-permutation orbit jumps to a multi-agent diffusion model. This would copy Niepert's two-step local-move-plus-orbital-shuffle scheme (Markov Chains on Orbits of Permutation Groups; Lifted Probabilistic Inference: An MCMC Perspective) into samplers such as Optimizing Diffusion Models for Joint Trajectory Prediction and Controllable Generation or Joint Pedestrian Trajectory Prediction through Posterior Sampling. We think this is nearly empty. Agents in a forecasting scene are not exchangeable once you condition on their observed histories. Swapping the futures of two cars with different pasts produces a scene of vastly lower probability. The residual label symmetry is already absorbed by permutation-equivariant networks. Global rotation symmetry is already built into architectures such as PECCO (Probabilistic Symmetry for Multi-Agent Dynamics), which makes convolutions exactly rotation-equivariant but does no sampling across modes.

The symmetry that actually separates modes lives in time at conflict points, not in agent labels or global coordinates. It is also only approximate, because the two orderings differ in probability through right-of-way, speeds, and lane rules. That is exactly the setting of Lifted Metropolis-Hastings (Lifted Probabilistic Inference for Asymmetric Graphical Models), which uses approximate symmetries only as proposals and lets the accept/reject step remove bias. We carry that design into continuous trajectories.

Research Program

Target distribution. The method needs an unnormalized joint density to run Metropolis-Hastings, which diffusion models do not directly supply. We therefore build a scene energy with two parts. The first is per-agent log-likelihoods from a Gaussian-mixture marginal head in the style of MultiPath++. The second is a learned pairwise interaction energy. We train that energy by noise-contrastive discrimination between real joint scenes and scenes recombined from independent marginals. It is inspired by the interaction-energy view of MATE, but MATE uses energy only as a training regularizer, whereas we use it as the sampling target:

$$\pi(\tau_{1:N}\mid x) \propto \prod_{i} p_i(\tau_i \mid x)\,\exp\Big(-\sum_{i<j} E_\theta(\tau_i,\tau_j,x)\Big),$$

Here $\tau_i$ is agent $i$'s future trajectory, $x$ is the map and history context, $p_i$ is the marginal density, and $E_\theta$ is the learned pairwise energy.

Local moves. Metropolis-adjusted Langevin steps on all waypoints handle within-ordering refinement.

Precedence-swap moves. First, conflict zones are detected from lane-graph intersections or crossings of current sampled paths. For a pair $(i,j)$ sharing a zone with entry times $t_i<t_j$, the swap keeps both spatial paths. It applies smooth, speed-limited monotone time warps so that $j$ enters in $i$'s slot and $i$ in $j$'s. We construct the warp as a deterministic involution: applying it twice returns the original scene. The acceptance ratio is then $\min\{1, \pi(T\tau)\,|\det J_T|/\pi(\tau)\}$, where $T$ is the swap and $J_T$ its Jacobian. The Jacobian is computed by automatic differentiation over roughly a hundred waypoint coordinates.

Two ideas from the lumping literature shape the design. Following Exploiting Symmetries to Construct Efficient MCMC Algorithms With an Application to SLAM., which showed that factors invariant under a group move cancel from the acceptance ratio, we evaluate only the energy terms touching the swapped pair and their time-overlapping neighbours. Following CON-MCMC, which alternates rare context flips with cheap orbital moves inside a fixed context, we treat the lane-graph conflict structure as the context. It is recomputed only when paths change enough to alter which zones exist. Recomputing rarely, rather than at every step, is how we avoid the per-step automorphism-search cost that burdens Generating and Sampling Orbits for Lifted Probabilistic Inference.

Ego-conditioned extension. Treating the ego vehicle's candidate plan as the context variable gives action-conditioned joint samples. These can be fed to a contingency planner in the spirit of LookOut. This is secondary; the core evaluation is open-loop forecasting.

Analysis. We will measure how close the chain is to a true lumped chain. The measures are the swap acceptance rate, the switching rate of the ordering indicator, and its integrated autocorrelation, all as functions of how asymmetric the right-of-way is. We expect acceptance to fall as right-of-way becomes strongly asymmetric, since the swap then targets a low-probability ordering. We will also report where the move stops helping, because that boundary is the honest scope of the claim.

Baselines

The naive reference point is the same energy model sampled with Langevin steps only, at identical energy-evaluation budget. It isolates whether swap moves add anything beyond ordinary refinement. We also report the marginal-head samples recombined without any interaction energy, as a floor.

The strongest existing competitors on INTERACTION are THOMAS (THOMAS: Trajectory Heatmap Output with learned Multi-Agent Sampling) and FJMP (FJMP). THOMAS recombines marginal heatmap candidates with scene-level cross-attention, and it reports a 2.4% validation scene collision rate together with first place on the v1.2 multi-agent test leaderboard. FJMP decodes along a learned influencer-reactor acyclic graph and also reports first place on that leaderboard. The file gives no decimal minADE or minFDE for FJMP ("no reported result found on Lacuna for FJMP INTERACTION displacement errors"). FJMP is the most direct competitor because its graph direction is itself a precedence choice. However, it commits to one learned ordering per decode rather than sampling over orderings. We will retrain both on the same splits and backbone features where code permits, and quote leaderboard numbers otherwise. Beating them means a lower scene miss rate at equal $K$, with scene collision rate at or below 2.4% on validation, obtained without a hand-written collision repeller.

On Argoverse 2 multi-world forecasting, the reference is the Optimal Gaussian Diffusion sampler of Optimizing Diffusion Models for Joint Trajectory Prediction and Controllable Generation. It reports a fourth-place leaderboard ranking with 40 denoising steps. We match its wall-clock budget.

The key ablations are two. The first uses random time-warp proposals of the same magnitude, which are not swaps; this isolates the symmetry structure. The second applies swaps without the accept/reject step, the analogue of the over-symmetric approximations that Lifted Probabilistic Inference for Asymmetric Graphical Models showed produce permanent bias; this isolates the correction.

Why not just…?

Why not just draw more samples from a joint diffusion model? Brute force raises coverage only if the model already places mass on the rare ordering and $K$ is large enough to hit it. Tails of the ordering distribution shrink geometrically in the number of coupled conflicts. We test this directly by plotting scene miss rate against $K$ and against conflict count, for both the diffusion baseline and our sampler. If the curves coincide in dense scenes, the claim fails.

Why not just enumerate the orderings explicitly, conditioning an FJMP-style decoder on each flipped edge set? This is the real threat. For one or two conflicts, enumeration costs two to four decodes and will likely match or beat MCMC. We accept that, and restrict the claim to scenes with many coupled conflict pairs, where the number of orderings grows factorially. We will stratify all results by number of conflict pairs and report the crossover point. A hybrid that enumerates small conflict clusters and swaps within large ones is a legitimate outcome.

Why not just use collision-repulsion guidance, as GFTD does, or parallel tempering? Repulsion guidance is a local force, so it separates overlapping agents but cannot exchange their order. We expect it to reduce collisions while leaving miss rate on the unexplored ordering unchanged, and the stratified analysis will show whether that holds. Tempering is a generic way across energy valleys that needs no symmetry. We include it as a baseline at matched energy evaluations. If it matches swap moves in ordering-switch rate, the symmetry ingredient is not doing the work, and we will say so.

Proposed Experiments

The first experiment uses a synthetic multi-intersection simulator with rule-based drivers, where the true distribution over orderings is known by construction. Right-of-way asymmetry and the number of conflicts per scene are varied. Metrics are total-variation distance between sampled and true ordering frequencies, ordering-switch rate, swap acceptance, and wall-clock. The decisive check here is that our sampler reaches low total-variation distance at conflict counts where Langevin, repulsion, and tempering stall. It must also degrade gracefully, rather than collapse, as asymmetry grows.

The second experiment uses INTERACTION v1.2 multi-agent, the benchmark with roundabouts, merges, and unsignalized intersections. We report scene miss rate, scene collision rate, and joint minADE and minFDE against THOMAS and FJMP, stratified by conflict-pair count.

The third experiment uses the interactive split of the Waymo Open Motion Dataset and the Argoverse 2 multi-world track. These test transfer to larger scenes and a latency-matched comparison with diffusion. We report latency against THOMAS's 31 ms for 128 agents. We do not expect to match that number and frame the method for planning-time budgets.

The result that would falsify the proposal is the following: in the high-conflict stratum, enumeration or tempering matches our scene miss rate at equal compute, or uncorrected swaps perform as well as corrected ones.