Spending Monte Carlo Uncertainty Only Where the Safety Answer Can Change

A self-driving perception stack that wants honest uncertainty usually runs Monte Carlo dropout: it keeps dropout switched on at test time and runs the network $N$ times, reading disagreement between the runs as the model's ignorance. That multiplies latency by roughly $N$, and it does so for every object in every frame, including the parked car forty metres away that has looked the same for two seconds. The spatial-database community solved a structurally identical waste long ago. Continuous nearest-neighbour systems avoid recomputing a query answer at every tick by keeping a small set of "guard" objects whose relative distances certify that the answer has not changed. We propose to borrow that machinery for perception. A moving-object index decides which detected objects can actually affect the ego vehicle's safety query. It keeps each object's sampled uncertainty in a cache together with a validity certificate, and it re-runs stochastic passes only on objects whose certificate has failed and that sit in the query's guard set.

In two sentences: run the cheap deterministic detector every frame, but spend the expensive uncertainty sampling only on the few objects that could change who is near the ego vehicle, and only when their viewing conditions have changed enough that the old uncertainty estimate may be stale. The uncertainty also flows back into the index. Guard checks use distances widened by each object's sampled localisation spread, so detector jitter does not churn the index the way exact-coordinate structures do.

Core Claim

Under a fixed per-frame latency budget, assigning Monte Carlo passes to objects by query relevance and certificate failure will preserve almost all of the safety-relevant uncertainty information of full per-frame sampling, at a small fraction of the passes. It will also beat uniform, periodic, and ego-motion-triggered schedules that spend the same budget. The new ingredient is the coupling of two things. The guard-set structure from moving k-nearest-neighbour processing decides where stochastic compute is needed. A statistically calibrated staleness certificate decides when it is needed. Neither the uncertainty literature nor the indexing literature does either of these.

Relation to Prior Work

Three papers motivate the gap. Towards Safe Autonomous Driving: Capture Uncertainty in the Deep Neural Network For Lidar 3D Vehicle Detection runs Monte Carlo dropout on a bird's-eye-view lidar detector. It shows that epistemic uncertainty flags unusual geometry while aleatoric uncertainty, predicted by an extra output head, tracks range and beam sparsity. Its only reported gain is a 1–5% F1 improvement over the non-Bayesian detector on KITTI raw. It also treats each sweep independently and pays full sampling cost every frame. That is the cost we attack, and its observation that uncertainty is driven by range and sparsity is what makes a staleness certificate plausible. PIXOR (93 ms per frame) and Multi-Task Multi-Sensor Fusion (about 80 ms) are deterministic real-time detectors. They show that naively multiplying their cost by $N$ breaks real time, and PIXOR serves as our host detector. AdaNSP uses dropout variance to decide when a semantic parser should spend extra decoding steps. That is the principle of uncertainty-gated compute, applied to tokens rather than space. Our gating instead comes from spatial structure rather than from the uncertainty itself, which avoids paying for the sampling needed to decide whether to sample.

The method itself comes from spatial indexing. Processing Moving kNN Queries Using Influential Neighbor Sets and INSQ replace polygonal safe regions with a guard set, the union of the Voronoi neighbours of the current answer, which can be checked in $O(k)$. We reuse this to define which objects matter. Those papers assume exact coordinates, and we relax that assumption. Towards Efficient Maintenance of Continuous MaxRS Query for Trajectories shows that event-driven certificate maintenance beats periodic recomputation, which it reports at 8–14% error even at 1-second intervals in its own setting. It is our template for event-triggered rather than clocked recomputation. Its certificates are exact geometric facts, whereas ours are statistical, which is a real difference we address below. MOIST shows that shedding redundant updates (about 80% shed, about 80x speedup) is the main lever in moving-object indexing. The survey of safe-region techniques documents why exact order-$k$ Voronoi regions are too costly to maintain dynamically, and that is why we use guard sets instead.

One paper constrains the design. Selective Classification for Deep Neural Networks found that single-pass softmax confidence ranks errors about as well as Monte Carlo dropout on in-distribution ImageNet. If that held for lidar detection, the whole premise would collapse, so we test it directly. We also reuse that paper's calibration technique, a threshold chosen on held-out data to bound a risk at confidence $1-\delta$, to calibrate our certificates.

Research Program

The system has three parts.

The first is a track index. PIXOR runs once per frame with dropout off. Its detections are associated into tracks and stored in an ego-centric grid index. The ego vehicle maintains a continuous safety query: its $k$ nearest tracked objects, weighted by time to contact. Following the guard-set construction, we maintain the guard set $G(t)$, the current answer plus its Voronoi neighbours. Objects outside $G(t)$ cannot enter the answer before some guard does.

The second is an uncertainty cache with certificates. When a track is sampled, we store its epistemic summary (mutual information over class scores and the variance of the box regression across $N$ passes). We also store the viewing conditions at sampling time: range, bearing, lidar point count inside the box, and occlusion fraction by neighbours. The cached value for object $i$, sampled at time $t_0$, is declared valid while

$$ \lVert \phi_i(t) - \phi_i(t_0) \rVert_W \le \tau \quad\text{and}\quad |s_i(t) - s_i(t_0)| \le \sigma, $$

where $\phi_i$ is the vector of viewing conditions, $W$ is a learned diagonal weighting, $s_i$ is the deterministic detector's score, and $\tau, \sigma$ are thresholds. We choose $\tau$ and $\sigma$ on held-out drives so that the fraction of "missed flags" stays below a target $\delta$ with high confidence. A missed flag is a case where the cached uncertainty says low but fresh sampling says high. This is exactly the guaranteed-risk calibration of selective classification, applied to staleness rather than abstention. The certificate is therefore a calibrated statistical bound, not a geometric proof. We report its empirical miss rate under distribution shift to show where the bound breaks.

The third is budgeted resampling and uncertainty-widened guards. Each frame, the objects in $G(t)$ whose certificates have failed are ranked by time to contact. They receive Monte Carlo passes on bird's-eye-view crops around their boxes until a latency budget is spent. Objects outside $G(t)$ are resampled only on a slow background schedule. In the other direction, guard checks compare distances widened by each object's sampled box spread. The query answer and the index therefore change only when a change exceeds what the detector's own uncertainty explains, which targets the jitter-driven update thrash that exact-coordinate indexes suffer.

Baselines

The naive reference points are the deterministic detector alone, PIXOR with dropout off, at its reported 93 ms per frame, and full Monte Carlo dropout on every object in every frame. The latter is the quality ceiling and cost ceiling for our method. It reproduces the probabilistic lidar detector's setup, whose only reported number is a 1–5% F1 gain over the non-Bayesian detector on KITTI raw. We found no reported latency for Monte Carlo dropout in that paper on Lacuna, so we measure it ourselves on the same GPU. Every scheduled method is scored against this ceiling as ground truth for "what the uncertainty would have been."

The strongest existing competitor for the scheduling question is periodic resampling: full Monte Carlo every $m$ frames, with $m$ chosen so that average cost equals our budget. It is the schedule a practitioner would actually deploy, and the continuous-MaxRS work is the only cited evidence that event-driven maintenance beats it, in a different setting. A second strong competitor is an ego-motion trigger, which resamples everything when the ego vehicle has moved more than a distance $d$ or turned more than an angle $\theta$. It is the crudest possible "safe region," and if it matches us, the guard-set machinery is unnecessary. A third is head-only Monte Carlo dropout, which runs the backbone once and samples only the detection head across the whole frame. It attacks per-pass cost rather than pass count.

Fairness is enforced in three ways. All methods share the same PIXOR weights, the same dropout rate, and the same $N$. All methods receive the same per-frame latency budget, measured wall-clock on one GPU. Each method gets an equal hyperparameter sweep on the validation drives ($m$; $d$ and $\theta$; our $\tau$, $\sigma$ and $W$).

Two ablations isolate the key ingredient. The first gives certificate-triggered resampling to all objects (no guard set). The second gives guard-set allocation with clock-based staleness (no certificate). Beating the baselines means two things. At equal budget, we must achieve a lower missed-flag rate on safety-relevant objects, and higher agreement with full sampling on the top-uncertainty objects, than both periodic and ego-motion schedules. We must also show that removing either ablated component loses a measurable share of that gain.

Why not just…?

Why not just resample everything every few frames? Periodic schedules spend passes on static scenes and miss sudden changes, such as an occluded pedestrian appearing, between ticks. The continuous-MaxRS paper's 8–14% periodic error is suggestive, but it comes from aggregate spatial queries, not perception. The equal-budget comparison above settles this directly, and we additionally report missed flags restricted to frames where a new object enters the guard set, which is where we expect periodic schedules to fail.

Why not just use the single-pass softmax score or the aleatoric head and drop sampling altogether? This is the real threat. Selective classification found softmax competitive with Monte Carlo dropout in-distribution, while the probabilistic lidar paper reports that aleatoric uncertainty tracks range rather than unusual geometry. Pseudo-label filtering in UPS and the original dropout-as-Bayesian-approximation results show softmax failing badly off-distribution, but on classification tasks. We therefore measure, on KITTI and on held-out nuScenes conditions, how well each single-pass score ranks detection errors compared with sampled uncertainty. If single-pass scores match sampling on both splits, we would report that sampling is unnecessary for this detector and pivot to using the index only for the uncertainty-widened guard checks.

Why not just make each pass cheaper with head-only dropout and batching? This is complementary rather than competing, because it lowers per-pass cost while we lower pass count, and we run the combination. It becomes a threat only if head-only sampling over the full frame already fits the budget with uncertainty quality equal to full-network sampling. We measure both its latency and its agreement with full-network sampling. If it wins outright, our contribution narrows to the index-side jitter suppression, and we will say so.

Why not just smooth tracks with a motion filter to stop index churn? A filter suppresses jitter with a fixed noise model. Our widened guards use per-object sampled spread, which grows for distant or unusual objects. We compare spurious guard-set changes and index update counts under a constant-velocity filter with fixed noise against the same filter whose noise is set from the sampled spread.

Proposed Experiments

The primary benchmark is KITTI raw, using the 29-train / 6-test drive split from the probabilistic lidar paper so that full-sampling numbers are directly comparable. nuScenes (nuScenes) supplies longer tracked sequences and a shifted test condition, with certificates calibrated on one subset of locations and evaluated on others. We have no reported nuScenes numbers for any baseline, so all nuScenes results will be produced in-house.

Metrics fall into four groups:

  • Cost: Monte Carlo passes per frame and wall-clock latency.
  • Uncertainty fidelity: the missed-flag rate relative to full sampling, restricted to guard-set objects; rank correlation of mutual information with full sampling; and F1 compared with the full-sampling detector.
  • Safety-query correctness: accuracy of the k-nearest-object set against annotated ground truth.
  • Index load: update counts with and without widened guards.

The decisive check is a budget sweep, plotting missed flags against passes per frame for every schedule. The proposal succeeds if our curve dominates periodic and ego-motion schedules at every budget. It must also hold its calibrated miss rate within a small factor of $\delta$ on the shifted nuScenes split. If certificates calibrated on KITTI fail badly under shift, statistical staleness bounds are not transferable, and that is itself the finding we would report.