Sparse inputs and sparse convolution

Start with a number. Voxelize an outdoor LiDAR frame into a regular 3D grid and count how many cells hold at least one point. PointAcc (Lin et al., MICRO 2021) reports that outdoor point clouds usually have a density below 0.01 percent, while a conventional CNN takes in a 100 percent dense image. That is the ~0.01% written above the sparse column of the slide. Indoor scans and single objects sit below 1 percent. Even after ReLU, an ImageNet network still keeps about half of its activations nonzero, so an image is up to four orders of magnitude denser than a LiDAR scan.

The roadmap places this under activation sparsity, next to EIE and the M:N tensor cores, and that is correct as far as it goes: the zeros are in the data, not the weights. But the source is different in a way that changes everything downstream. ReLU zeros and pruned weight zeros land wherever the arithmetic puts them. Point-cloud zeros are the empty air between surfaces. PointAcc calls this sparsity "fundamentally different" because "the sparsity pattern is constrained by the physical objects in the real world", and draws the consequence that matters here: the nonzero points should never dilate during computation. In the vocabulary of part 07 it is still dynamic, since every frame has a new pattern, but it is a pattern with geometric meaning.

What a dense convolution does to empty space

Now apply an ordinary 3 x 3 convolution to a grid with a single active cell. The kernel window touches that cell from nine different positions, so nine outputs become nonzero. Apply a second layer and the nine become twenty-five. Graham, Engelcke and van der Maaten (CVPR 2018) state the rule in d dimensions: a single active site becomes 3^d active sites after one convolution and 5^d after two. In 3D that is 1, then 27, then 125. They name it the submanifold dilation problem, because a surface (a 2D submanifold in 3D space) thickens into a slab and the sparsity that made the input cheap is gone within a few layers.

The slide shows the same effect on a small grid you can check by eye. The input is 4 rows by 5 columns with four active cells at rows and columns (1, 1), (2, 2), (2, 4) and (3, 3). Each active cell activates every output its 3 x 3 window touches, clipped to the grid: nine for the first two points, six each for the two that sit against an edge. The union of those windows is 17 of 20 cells, exactly the orange region drawn on the conventional side. Only (0, 3), (0, 4) and (3, 0) stay empty, and a second layer would fill those too.

The fix: compute only where an input exists

Sparse convolution, in the submanifold form the deck uses, changes one rule. An output site is computed if and only if the input site at the same coordinate is active. Graham et al. define it exactly that way: the filter size is odd, the input is padded so the output keeps the input's size, and an output is active only when the central site of its receptive field is active. TorchSparse writes the same fact as a set equation, P_in = P_out, against the dense case where P_in is only a subset of P_out. On the slide grid the sparse side stays at four orange cells, and after a hundred layers it would still be four.

The pair of ring images at the bottom of the slide comes from two different figures of the Graham papers. The left ring is Figure 2 of the CVPR 2018 paper (Figure 1 of the 2017 arXiv version): a thin curve pushed through two ordinary 3 x 3 convolutions has smeared into a grey band. The right ring is Figure 3 of the CVPR 2018 paper: the submanifold receptive field centred on one active site, drawn in green, with the empty sites it ignores in red, so the ring stays a ring. That is the whole motivation in one picture: the operator must respect the geometry, or the geometry disappears.

Why a whole part on one operator? TorchSparse's introduction lists the stakes. All top five segmentation submissions on SemanticKITTI and nine of the top ten on nuScenes are built on sparse convolution, yet the operator is not supported by TensorRT or TVM, and the best library of the day ran MinkowskiNet at 8 FPS on a GTX 1080Ti, a desktop GPU far above anything on an embedded board. The gap between what the algorithm avoids and what the hardware delivers is the research territory of parts 12 and 13.

Follow the boxed point P0 at row 1, column 1 through a 3 x 3 convolution. A 3 x 3 kernel is not one weight; it is nine weight matrices, one per tap, each of shape C_in x C_out. TorchSparse writes them as W_δ for each offset δ in {-1, 0, 1}^2. The deck names them W_(dx,dy), with dx the row offset and dy the column offset, and the visual and simulator below use the same labels. Every time P0 lands in an output's window, exactly one of those nine matrices multiplies its feature vector, and which one depends only on where the output sits relative to P0.

The deck's convention, consistent across all nine slides, is that the input P sits at the output Q shifted by the offset: P = Q + (dx, dy) in (row, column). The first entry on the slide makes it concrete. Output Q0 is the top-left corner of P0's window at (0, 0), so P0 = Q0 + (1, 1) and the weight is W_(1,1). The centre entry, where Q4 is P0's own position, uses W_(0,0). The bottom-right corner at (2, 2) uses W_(-1,-1).

The map is the computation

Each such relation is one tuple, and the list of all of them is what the slides call the maps, written (In, Out, Wgt). TorchSparse defines the map for a layer as the set M = {(p_j, q_k, W_δ)} and describes the whole layer as one loop: iterate over the map and, for each entry, accumulate the input feature vector times the entry's weight matrix into the output feature vector. That is the update rule printed at the bottom-left of every slide in this run.

Read the indicator as the map-building test. For each output q_k and each offset δ, look up the coordinate s·q_k + δ. If an input point p_j sits there, the triple (p_j, q_k, W_δ) joins the map; if not, nothing is added and nothing is computed. TorchSparse's Algorithm 1 is exactly this double loop with a hash-table lookup on coordinates. The heading of the slides now reads correctly: a sparse convolution is a sparse set of dense matrix multiply-accumulates, and the sparsity lives entirely in which tuples exist.

Nine entries become two

Now compare the two columns of the slide for P0. The conventional column lists one entry per tap, nine in all, because every cell of P0's window is an output that a dense layer computes. The sparse column applies the submanifold rule from the previous concept: an output must itself be an input position. Inside P0's window only two cells qualify, P0's own position and (2, 2), where P1 sits. So the map keeps exactly two tuples and marks the other seven "No compute".

Costing the whole grid, not just P0

The slide follows one point, so extend it to all four. Conventionally each point contributes one entry per in-grid tap: 9 for P0, 9 for the point at (2, 2), 6 for (2, 4) against the right edge and 6 for (3, 3) against the bottom, 30 in total. The submanifold map has one centre entry per point plus one entry for every ordered pair of points within one step of each other. Three such pairs exist, (1, 1) with (2, 2), (2, 2) with (3, 3) and (2, 4) with (3, 3), each counted in both directions, giving 4 + 6 = 10 entries. Each entry is a (1 x C_in)(C_in x C_out) product, so with C_in = C_out = 64 an entry costs 4,096 MACs.

Two lessons hide in that table. Zero-skipping alone, the trick EIE relied on, already removes most of the work on this grid, but it still writes the dilated 17-cell output and so the next layer starts from 17 points instead of 4. The submanifold map is the only row whose cost stays proportional to the number of points layer after layer. On a real LiDAR frame with hundreds of thousands of points in a grid of billions of voxels, the fully dense row is not merely slow; it does not fit in memory.

Slide 95 closes the P0 story with a count, nine matrix multiplications against two, and slide 96 asks the practical question: how does a GPU run a list of tuples? Take its workload, a 5 x 5 grid with five points P0 at (1, 1), P1 at (2, 2), P2 at (2, 4), P3 at (3, 2) and P4 at (4, 3). Its map has eleven entries, and the box on the slide lists them not in point order but sorted by weight offset. That ordering is the whole idea.

Running the update rule one entry at a time means eleven vector-matrix products, each a single row of C_in values against a C_in x C_out matrix. TorchSparse notes that the utilization of matrix-vector multiplication is rather low on a GPU, whose tensor cores want tall matrices on both sides. The escape is to notice that entries sharing the same offset share the same matrix. Stack their input rows into one contiguous matrix, multiply it by that one W_δ, and you have turned several vector-matrix products into one matrix-matrix product. Grouping by output or by input would not work: entries with the same output use different weights, and so do entries with the same input.

Five of the nine offsets have entries, so this layer launches five matmuls with 2, 1, 5, 1 and 2 rows. The other four offsets have empty maps and launch nothing. Notice too that P2 at (2, 4) has no neighbour within one step, so it appears only in the W_(0,0) group: an isolated point costs exactly one entry.

Gather, matmul, scatter

The pipeline on slide 96 is the gather, matmul, scatter flow that every existing GPU implementation follows, written out for the highlighted offset W_(-1,-1). Its two entries are (P0, Q1) and (P3, Q4). Gather copies rows P0 and P3 out of the 5 x C_in input feature matrix into a 2 x C_in buffer. Matmul multiplies that buffer by the C_in x C_out weight to produce a 2 x C_out partial sum. Scatter adds row one into output Q1 and row two into Q4, which is the pair of equations under the figure: f1 = f1 + f0 x W_(-1,-1) and f4 = f4 + f3 x W_(-1,-1). Then the next offset takes its turn with its own rows.

The slide's heading calls this weight-stationary: the weight matrix for one offset stays put while the gathered rows stream through it, and a separate matmul runs for each different weight. TorchSparse's Algorithm 2 is literally a loop over offsets that performs gather, matmul and scatter for each. The rule book in Graham et al. is the same design described from the sparse-convolution side: for each row (j, k) in the rule for offset i, multiply row j of the input matrix by W^i and add it to row k of the output, which they note runs efficiently on a GPU precisely because it is a matrix-matrix multiply-add. SECOND (Yan et al., 2018) moved the rule generation itself from a CPU hash table to the GPU, since the CPU version was slow and required data transfer between CPU and GPU on every layer.

A symmetry you can check on the slide

Look at the row counts again: W_(-1,-1) and W_(1,1) both have two rows, W_(-1,0) and W_(1,0) both have one. That is not luck. If (P, Q, W_δ) is an entry, then P and Q are both points and Q = P + (-δ), so (Q, P, W_(-δ)) is also an entry. TorchSparse section 4.2.1 proves this one-to-one correspondence for any odd kernel at stride 1, and the (0, 0) map is special for a second reason: every point maps to itself, so it needs no gather and no scatter at all. Part 12 builds its first optimization on exactly this pairing, and the simulator above reports the check on every grid you draw.

• Entries: for stride 1 with an odd kernel, count(δ) = count(-δ), and the (0, 0) map has exactly one entry per point.
• Matmuls per layer: the number of offsets whose map is non-empty, at most K^D.
• MACs per layer: total entries times C_in x C_out, independent of how the entries are grouped. Grouping changes utilization and data movement, never the arithmetic count.