Networks that segment LiDAR scans or reconstruct 3D shapes increasingly want to let each voxel exchange information with voxels it is not physically touching: the far side of a car, a pole three meters away, the matching part of a symmetric object. Learning which connections matter is called latent topology inference. It works well on small sensor networks, but on hundreds of thousands of voxels the learned graph must be sparse. The sparsity it produces is irregular and changes with every input. Modern GPUs gain almost nothing from that kind of scattered sparsity. They only speed up when every small block of four entries has exactly two nonzeros (so-called 2:4 sparsity), or when nonzeros fill whole rows inside fixed tiles. As a result, learned non-local graphs on 3D data either stay dense and slow, or become sparse on paper and stay slow on hardware.
We propose to sample the learned graph with a tool from approximation algorithms called dependent, or negatively correlated, rounding. Pivotal sampling is one such method: it turns fractional probabilities into 0/1 choices so that each edge is kept with exactly its learned probability, while the number kept in each group is fixed. Applied inside every block of $M$ candidate neighbors, it produces a graph that is exactly $N{:}M$ sparse by construction, so it can run on sparse tensor cores. Because the inclusion probabilities are known exactly, the sparse message sum can be reweighted into an unbiased estimate of the dense learned aggregation. Negative correlation also gives it lower variance than independent coin flips at the same edge budget. The setting where this matters most is adaptive voxel grids such as cylindrical LiDAR partitions and octrees. There, candidate density varies greatly with distance and scale, and independent sampling leaves sparse far-range voxels starved of messages.
Core Claim
Fixed-size sampling with exact marginals gives a per-input graph that is hardware-aligned, unbiased, and lower-variance. That combination lets a learned non-local graph over adaptive voxels train and run at $N{:}M$ sparsity without the gap between soft training edges and hard inference edges that afflicts relaxed sampling. In particular, we expect it to match the accuracy of the dense learned graph at roughly the cost of the sparse one.
The mechanism is simple to state. Let voxel $u$ have candidate neighbors $v$ with learned edge weights $w_{uv}$ and messages $m_v$. Let the sampler keep edge $uv$ with probability $p_{uv}$, with indicator $X_{uv}$, under the constraint that each block of $M$ candidates keeps exactly $N$. The aggregation is
$$\hat{h}_u = \sum_{v} \frac{X_{uv}}{p_{uv}} \, w_{uv} m_v ,$$
which equals the dense sum $\sum_v w_{uv} m_v$ in expectation. This is the Horvitz–Thompson form, and it is unbiased because $\mathbb{E}[X_{uv}] = p_{uv}$ exactly under pivotal sampling. Its variance is
$$\mathrm{Var}(\hat h_u) = \sum_v a_v^2 \frac{1-p_v}{p_v} + \sum_{v \neq v'} a_v a_{v'} \frac{\pi_{vv'} - p_v p_{v'}}{p_v p_{v'}},$$
where $a_v = w_{uv} m_v$ for a scalar feature and $\pi_{vv'}$ is the joint inclusion probability. Negative dependence makes the second term non-positive whenever contributions share a sign. When $p_v \propto |a_v|$ within a block, the fixed-size sum has zero variance, because every term contributes the same constant times $N$. Independent Bernoulli or Gumbel edge sampling, as in GTS, has $\pi_{vv'} = p_v p_{v'}$. It gets no such reduction and does not hit exact block counts, so its masks cannot use structured kernels.
The method contribution is new in a specific way. Pivotal sampling was used by New Philosopher Inequalities for Online Bayesian Matching to keep offline nodes from colliding or starving in online matching. Lift-and-round and iterative fair contention resolution used negative correlation to beat the 3/2 barrier for independent rounding in scheduling, reaching 1.488. None of these touch neural networks or hardware. We reuse their rounding primitive and change its job: from an analysis device for approximation ratios to a sampler whose output pattern is the hardware sparsity format.
The research file lists sequential coupling as a GPU obstacle for dependent rounding. That obstacle largely disappears here, because rounding happens inside independent blocks of size $M$ (4 or 8). Each block is a handful of scalar operations, run in parallel across millions of blocks.
Research Program
The base model is a cylindrical-voxel LiDAR segmenter in the style of Cylinder3D. Cylinder3D partitions space by radius, angle and height, which raises the share of non-empty cells from 61% to 89%. It then applies asymmetric 3D convolutions over physically adjacent cells.
We add one learned non-local layer at a coarse scale of the encoder. Each non-empty voxel draws a candidate set of $B \cdot M$ voxels: geometric near neighbors, plus a strided sample of farther voxels along range and azimuth. A small network scores each candidate, giving $w_{uv}$, in the spirit of GTS and GLCN. Those methods learn edges from task loss over flat node sets. We carry this to multi-scale voxels.
The sampling probabilities within each block come from projecting the edge-score magnitudes onto the simplex scaled to sum to $N$, capped at one. Pivotal sampling then draws exactly $N$ edges per block. The resulting row-wise $N{:}M$ adjacency is packed into the vendor 2:4 sparse format and multiplied against the dense voxel feature matrix. On pre-Ampere GPUs we use the analogous tile-wise layout of Tile-Wise Sparsity, which prunes whole rows inside GEMM tiles and runs them with dense instructions.
Gradients reach $w$ and $m$ through the reweighted sum. The probabilities $p$ are tied to $|w|$, so training also pushes the sampler toward the variance-minimizing allocation. No straight-through estimator or temperature schedule is needed.
There is a second, optional rounding stage aimed at adaptive voxel sizes. Distant cylindrical cells are large and few, so they appear as candidates for many rows. Near cells are small and many. The row-wise constraint does nothing to stop a few distant cells being chosen by everyone while others are never chosen. We therefore test a bipartite dependent-rounding variant, in the spirit of the lift-and-round papers, that also caps how often each source voxel is used within a tile. It answers whether column load-balancing helps far-range accuracy or only adds cost.
As a second setting, we test the same sampler on the dual graph of Dual Octree Graph Networks. That model links face-adjacent octree leaves across depths and runs convolutions as GEMMs, but its connectivity is fixed by geometry. Here we add learned cross-scale edges on ShapeNet using the released code. As a sanity setting where the latent graph is the whole model, we swap our sampler into GTS on METR-LA. This isolates the rounding question from 3D engineering.
Baselines
The naive reference point is the unchanged backbone with no learned non-local edges: Cylinder3D on SemanticKITTI and nuScenes, the dual octree network on ShapeNet, and GTS's own sampler on METR-LA. For SemanticKITTI the file reports 67.8% mIoU and 170 ms latency for Cylinder3D, and 76.1% mIoU on nuScenes (Cylinder3D). For ShapeNet, no reported number for the dual octree network was found on Lacuna; the file states only that it beat ConvONet and DeepMLS on Chamfer distance and IoU. We will therefore rerun it ourselves. For METR-LA, the reported 60-minute MAE is 2.99 for GTS, against 3.60 for DCRNN on the physical road graph (GTS).
The accuracy ceiling is the same backbone with the dense learned non-local layer, using all $B \cdot M$ candidates. It shows how much the learned topology helps at all. Every sparse variant is judged by how much of that gain it keeps.
The strongest competitor on the accuracy question is independent edge sampling with Gumbel-Softmax at the same expected edge count, as in GTS, executed with a generic sparse kernel. It shows what learned sparsity costs today.
The strongest competitor on the hardware question is deterministic top-$N$-per-block masking trained with a sparse-refined straight-through estimator, following SR-STE. There, 2:4 ResNet-50 reached 77.0% top-1 on ImageNet versus 77.3% dense, at a 2× theoretical speedup. Our version transfers that recipe from weights to the per-input adjacency.
A fourth competitor is Gumbel-top-$k$ within each block. It also yields exact $N{:}M$ masks, but its inclusion probabilities have no closed form, so it cannot be reweighted unbiasedly.
All variants share the backbone, candidate sets, edge budget, training schedule, random-seed count (three per setting), and hyperparameter search. Each method gets the same number of trials over learning rate and temperature, or the equivalent knob. Latency is measured on the same A100 for 2:4 kernels and V100 for tile-wise kernels, end to end, including the cost of sampling and packing masks.
Beating the field means two things on SemanticKITTI. First, mIoU within 0.5 points of the dense learned layer, and above independent Gumbel and top-$N$ STE at equal budget. Second, layer latency at most about 60% of the dense layer, the sort of saving tile-wise sparsity reports for BERT (1.95× on V100 tensor cores).
The key ablation keeps the identical $N{:}M$ mask distribution family but toggles three things in turn: pivotal versus systematic versus Gumbel-top-$k$ selection, Horvitz–Thompson reweighting on versus off, and column load-balancing on versus off.
Why not just…?
Why not just use Gumbel-top-$k$ inside each block, which already gives exact $N{:}M$ masks? This is the most serious alternative, and it may work nearly as well. It is cheap and differentiable with standard relaxations. What it lacks is known inclusion probabilities. Without them, the sparse sum is a biased estimate of the dense aggregation, and the bias grows when scores within a block are uneven. That is exactly what happens in adaptive grids, where near and far candidates differ sharply in relevance. The ablation that holds the mask family fixed and swaps only the selection rule settles this directly. We will also report the measured bias and variance of the layer output against the dense layer on held-out scans. If Gumbel-top-$k$ matches us on mIoU and bias, the honest conclusion is that exact cardinality, not negative correlation, is the active ingredient. The paper would then be reframed around that.
Why not just take the deterministic top-$N$ edges per block, as SR-STE does for weights? Deterministic masks have no sampling variance, and SR-STE shows they train well for fixed weights. But the adjacency here is recomputed for every input. A greedy mask never explores low-scoring candidates, so their scores receive no gradient. SR-STE itself reports mask instability (its sparse architecture divergence measure) even for static weights. We will track how often each candidate is selected over training, and measure accuracy on distant and rare classes. Our prediction is that top-$N$ collapses onto near neighbors and loses the far-range gains. If it does not, it is the simpler method and should win.
Why not just keep the fixed geometric neighborhood and skip learned edges entirely? The file supplies two pieces of evidence. On METR-LA a learned graph beat the physical road graph, 2.99 versus 3.60 MAE (GTS). And the dual octree network's connectivity is fixed purely by face adjacency. Neither result is on LiDAR, though. The dense-learned-layer baseline tests this directly: if it does not beat plain Cylinder3D, the premise fails and no sampler can rescue it.
Why not just prune with unstructured masks and use a generic sparse library? At the 75–90% sparsity typical here, scattered sparsity rarely yields wall-clock gains. Index handling and non-contiguous memory access outweigh the arithmetic saved, as documented by Wiedemann et al. and Grimaldi et al.. We include this as the latency floor to make that cost visible on our workload rather than assume it.
Proposed Experiments
The first decisive check is statistical and needs no training. We take a trained dense learned layer and replay its scores on SemanticKITTI validation scans under each sampler at matched budgets of 2:4, 2:8 and 1:4. For each, we measure the mean-squared error of the sparse aggregation against the dense one, broken down by radial distance band. We expect pivotal sampling with reweighting to have the lowest error, with the largest margin in far bands where cylindrical cells are coarse. Column balancing should help mainly there. If pivotal and Gumbel-top-$k$ errors coincide, the variance story is wrong.
The second check is end-to-end training on SemanticKITTI and nuScenes. We report mIoU overall, per distance band, and for moving classes; the SemanticKITTI paper notes moving classes often fall below 20% for simpler models (SemanticKITTI). We also report measured layer and full-model latency, and accuracy–latency curves across budgets. We further test the soft/hard gap by evaluating each model with its own training sampler versus a deterministic top-$N$ mask at inference. Our method should show the smallest gap, because it never trains on soft edges.
The third check tests transfer. On METR-LA, swapping the sampler into GTS should at least match its reported 2.99 MAE, with lower variance across seeds. On ShapeNet, adding learned cross-scale edges to the dual octree network should improve Chamfer distance and IoU relative to our rerun of the released model, without exceeding its inference time on complex scenes. The file reports 478 ms on a V100 for SceneNN-scale scenes.
A negative outcome on the LiDAR runs would still be informative. Dense learned edges might help while every sampled variant fails to keep the gain at 2:4. That would indicate that per-input hardware-aligned sparsity is too coarse for non-local 3D reasoning, and would point toward tile-wise layouts with larger budgets instead.
References
- Discrete Graph Structure Learning for Forecasting Multiple Time Series
- New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
- Lift-and-round to improve weighted completion time on unrelated machines
- Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
- Cylindrical and Asymmetrical 3D Convolution Networks for LiDAR Segmentation
- Semi-Supervised Learning With Graph Learning-Convolutional Networks
- Accelerating sparse DNN models without hardware-support via tile-wise sparsity
- Dual Octree Graph Networks for Learning Adaptive Volumetric Shape Representations
- Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch
- Dithered backprop: A sparse and quantized backpropagation algorithm for more efficient deep neural network training
- Accelerating Deep Neural Networks via Semi-Structured Activation Sparsity
- SemanticKITTI: A Dataset for Semantic Scene Understanding of LiDAR Sequences