Shadow-Priced Sparse Convolution: Hard Per-Frame Compute Budgets for LiDAR Detectors

A LiDAR detector (a network that finds cars and pedestrians in a laser scan of the street) spends almost all of its compute on empty road, walls, and vegetation. Current tricks for skipping that work keep a fixed fraction of the 3D grid cells at each layer. When the car drives from a quiet highway into a packed intersection, the compute a frame needs can change by a large factor, so the detector either misses its real-time deadline or throws away objects. We propose to treat the network's computation like a radio spectrum. Each occupied grid cell (a "voxel") at each layer is a small consumer that can be processed fully, passed through untouched, or grown into its empty neighbours. One global per-frame budget, on compute and on peak memory, couples all of these choices. Following the wireless literature, we price the budget with a Lagrange multiplier, a "shadow price" in compute units. Each voxel then decides for itself whether its expected contribution to the detection is worth the price. A tiny scalar search on the price makes each frame's total cost land on the budget.

The idea comes from Lagrange dual decomposition in wireless resource allocation. That field splits a hard mixed-integer problem, coupled through a shared power budget, into thousands of independent per-subcarrier decisions. The same field knows that with many subcarriers the relaxation loses almost nothing, a property called the time-sharing condition. A frame of LiDAR voxels has exactly this structure: tens of thousands of cheap binary decisions coupled by one or two shared budgets. What is new is not "pruning under a budget" in general. It is three specific things. First, a single price is shared across layers and across kinds of action (skip, process, dilate), so compute moves between network stages and scene regions automatically. Second, the budget is met on every frame at test time, not on average during training. Third, the price is carried from one frame to the next like a multiplier tracking a fading channel.

Core Claim

At a fixed, hard per-frame cost budget, allocating per-voxel, per-stage actions by one shared shadow price will do better than per-stage top-$k$ pruning. It should give higher detection accuracy at equal worst-case cost and near-zero deadline violations at equal accuracy. The gains should concentrate on dense scenes and on small classes, which is where fixed ratios either overspend or over-prune. We also expect the discrete allocation recovered from the price to be provably and empirically within a vanishing fraction of the relaxed optimum, a "spatial time-sharing" property.

Relation to Prior Work

Three sparse-convolution papers motivate the gap.

- Spatial Pruned Sparse Convolution (SPS-Conv) keeps the top-$k$ voxels per stage by channel-wise feature magnitude and sends the rest through an identity shortcut. It cuts GFLOPs by more than 50% with little loss. Its $k$ is a fixed per-stage hyperparameter, so cost still scales with scene size, and there is no mechanism that trades one stage's compute against another's. - Focal Sparse Convolutional Networks learns per-voxel importance that decides whether a voxel dilates (regular convolution) or stays fixed (submanifold convolution, which keeps the output voxel set identical to the input). Its decisions answer only to the task loss, so nothing bounds dilation in cluttered scenes. - Generative Sparse Detection Networks expands coordinates into empty object centres and prunes them with a fixed confidence threshold.

Our proposal reuses their action vocabulary: identity pass-through from SPS-Conv, and dilate versus submanifold from Focals Conv. It replaces their local rules with a price-coupled allocation.

A constraining result is Putting 3D Spatially Sparse Networks on a Diet. It shows that static weight pruning alone can remove 99% of parameters with a 2.15% mIoU drop. Any dynamic scheme must therefore be compared against a weight-pruned network, not only a dense one. That pruning is input-agnostic and cannot reduce the number of voxels each layer visits.

The wireless papers supply the method.

The graphical-model dual decomposition work, such as Alternating Directions Dual Decomposition, splits inference over discrete fields. It does not allocate compute inside a network.

Formulation

After the network's first stage (called the stem), a lightweight planning head predicts a utility $u_{i,l}(a)$ for each voxel $i$, each later stage $l$, and each action $a$ in {skip, submanifold, dilate}. The analytic cost $c_{i,l}(a)$ of that action is known from the stage's channel widths and kernel size. The cost is measured in FLOPs, and the voxels an action creates can be added to a memory counter. With binary indicators $z_{i,l}(a)$ choosing exactly one action per voxel and stage, and budgets $B_1$ (FLOPs) and $B_2$ (peak voxels), the frame's allocation problem is

$$\max_{z}\ \sum_{i,l,a} u_{i,l}(a)\, z_{i,l}(a) \quad \text{s.t.}\quad \sum_{i,l,a} c^{(r)}_{i,l}(a)\, z_{i,l}(a) \le B_r,\ \ r=1,2.$$

Pricing the two constraints with multipliers $\lambda_1,\lambda_2 \ge 0$ splits the problem into independent per-voxel choices. Each voxel and stage picks the action with the largest $u_{i,l}(a) - \lambda_1 c^{(1)}_{i,l}(a) - \lambda_2 c^{(2)}_{i,l}(a)$. The coordinator then updates the prices from the measured overshoot. The measurement uses the realised cost, which includes overlap when two dilating voxels create the same new neighbour. That overlap makes the true cost non-separable. The feedback loop absorbs it, but loses any exactness guarantee; we measure how much this matters.

The problem is a multiple-choice knapsack. A basic optimal solution of its linear relaxation has at most one fractional variable per constraint, here at most two. The integer solution recovered from the prices is therefore within two items' utility of the relaxed bound. Relative to a total built from $M \gg 10^4$ voxels, this gap shrinks as $O(1/M)$. This is the spatial analogue of the time-sharing condition, and it follows directly from linear-programming vertex structure rather than asymptotics. The dual problem has two variables, so bisection or a few projected subgradient steps over $M$ scalar comparisons cost microseconds on a GPU. We warm-start them from the previous frame's price.

Training samples a budget per batch. This teaches the utilities to act as calibrated marginal values across budgets instead of for one operating point. The discrete choices use a straight-through estimator, and utilities are supervised against the detection loss.

Research Program

We will build this on a CenterPoint-style sparse voxel backbone, using the architecture from Center-Based 3D Object Detection and Tracking, and write custom kernels for the three actions. The project analyses three things:

  • whether analytic FLOP and voxel costs predict wall-clock latency well enough to price. If they do not, we fit a per-action latency model and price that instead, since irregular memory access is a known reason FLOP savings fail to become speed;
  • how large the realised duality gap is, measured against an exact integer-programming solve on downsampled frames;
  • how the price behaves over time, for example whether it rises smoothly entering dense urban areas.

Baselines

The naive reference is the dense CenterPoint backbone. It reports 65.5 NDS on the nuScenes test set, 16 FPS on nuScenes, and 71.8 mAPH for vehicles on Waymo (Center-Based 3D Object Detection and Tracking). We retrain it with our pipeline on nuScenes validation so every method shares data, schedule, and hardware. Beating it means matching its NDS within 0.3 points at a hard budget below half its median per-frame GFLOPs.

The strongest efficiency competitor is SP-CenterPoint from Spatial Pruned Sparse Convolution. It reports "more than 50% reduction in GFLOPs" while staying "within 0.1-0.2%" of the full model on nuScenes, a 62.46% GFLOPs reduction on Waymo, and 52.4% on KITTI. The file gives no absolute NDS for it, so we reproduce it with the authors' per-stage ratios and the same training budget as our model. We then sweep its ratios to trace an accuracy–cost curve. Beating it means higher mAP and NDS at equal 99th-percentile per-frame cost, and fewer frames over budget at equal mean cost.

The strongest accuracy-oriented competitor is Focals Conv on CenterPoint (Focal Sparse Convolutional Networks). It reports +4.9% mAP over CenterPoint on nuScenes, and on KITTI a PV-RCNN runtime rising from 103ms to 112ms. We run it unchanged and also report its per-frame cost distribution. Our claim against it is budget compliance at a comparable share of its accuracy gain, not beating its unconstrained accuracy.

We also include a weight-pruned backbone in the style of Putting 3D Spatially Sparse Networks on a Diet, matched in mean FLOPs. Combining it with our method tests whether the two kinds of pruning add up.

The ablation that isolates the key ingredient is "scaled top-$k$". Each frame, it uses the same planning-head scores but keeps a uniform fraction per stage, set so that total cost equals the budget. It meets the same hard budget, but has no shared price across stages and actions. A second ablation removes the dilate action. A third replaces cross-frame warm-starting with a cold start.

Why not just…?

Why not just keep SPS-Conv's fixed top-$k$? A fixed ratio makes cost proportional to the number of input voxels, so it cannot bound worst-case latency. The SPS-Conv results report mean GFLOPs savings, not tail behaviour. Our per-frame 99th-percentile latency and violation-rate measurements, split by scene density, show directly whether that matters. If SPS-Conv's tail is already within the deadline on nuScenes and Waymo, the budget-compliance part of our claim collapses. The claim would then have to rest on accuracy at equal cost.

Why not just pick $k$ per frame so the total fits the budget? This is the real threat, because it is almost free. With one action type and uniform per-voxel cost, it is exactly our method with a single price, and sorting solves it optimally. Our method differs only when costs vary across stages and actions and when two resources bind. The scaled top-$k$ ablation settles this. If it comes within about 0.3 NDS of the priced version, we will report that the cross-stage price adds nothing. The contribution would then shrink to per-frame budgeting plus the gap analysis.

Why not just train a gating head with a compute penalty, Focals-style? A penalty fixed at training time sets average cost, not per-frame cost. It also cannot follow a budget that changes at deployment, for example a power mode switch. The Focals Conv results report nominal runtimes only. We evaluate it, and a variant trained with a FLOP regulariser, across held-out budgets and dense-scene subsets.

Why not just coarsen voxels or use bird's-eye pillars? Coarsening lowers cost uniformly and gives up exactly the small, thin objects where adaptive allocation should help. It still does not bound cost in dense scenes. We include a coarser-grid CenterPoint at matched mean cost and compare per-class pedestrian and cyclist accuracy.

Proposed Experiments

The primary benchmark is nuScenes. Its Boston and Singapore scenes and night subsets give natural variation in density and difficulty, and the file reports lidar mAP dropping 36% at night. Secondary benchmarks are Waymo, for long-range and dense urban frames, and KITTI, to compare against published GFLOPs reductions.

The metrics are:

  • mAP and NDS, overall and per class;
  • the distribution of per-frame GFLOPs, peak memory, and measured latency, reporting median and 99th percentile;
  • the fraction of frames exceeding the budget;
  • dual iterations per frame;
  • the realised duality gap against exact solves on subsampled frames.

We sweep budgets from 30% to 70% of dense median cost and train a single model covering all of them.

The decisive checks are three. First, on the top-density decile of nuScenes frames, the priced model must beat scaled top-$k$ and SPS-Conv in pedestrian and cyclist AP at equal hard budget. Second, it must hold the budget on at least 99.5% of frames, where SPS-Conv at equal mean cost does not. Third, the measured relative duality gap must fall as voxel count grows, consistent with the $O(1/M)$ bound. If the first check fails, the shared price is not worth its complexity. If the third fails, the time-sharing analogy is wrong for these problems, and that is worth reporting as a result.