Certified Visible Sets for Gaussian Splatting Scenes

A 3D Gaussian Splatting scene is a photoreal 3D model made of millions of small, semi-transparent blobs that are drawn front to back. Many of these blobs sit inside walls or behind furniture and never show up in any image. Current pruning methods find them by rendering the training views and discarding blobs that contribute little. That works on the training views. It says nothing about the view a robot or headset sees after moving 30 cm off the captured path, where a "hidden" blob can suddenly show through a gap. We propose to compute, for each region of camera positions, a certified visible set: a subset of blobs with a proof that, from every camera pose in that region, the image rendered from the subset differs from the full scene's image by at most a chosen per-pixel tolerance $\delta$.

The key observation is that this certificate is a formal-verification problem whose input is low-dimensional. The input is the camera pose, with six or fewer degrees of freedom, not a million-pixel image. Low-dimensional inputs are exactly where verification scales well, because the solver can split the input domain directly, as was shown for 5-dimensional collision-avoidance networks. Splitting camera space into cells, and the scene into blocks, therefore does two jobs at once. It is the "input slicing" that makes verification tractable, and it is the spatial partitioning that lets city-scale scenes be streamed cell by cell.

Core Claim

Removing primitives from an alpha-composited render introduces a per-pixel error that is bounded by a quantity we can check over a continuous region of poses. Suppose a pixel composites primitives in depth order with opacities $\alpha_i$ and colors $c_i \in [0,1]$. Let $R$ be the set of removed primitives and $T_k^{\text{ret}}$ the transmittance in front of primitive $k$ (the fraction of light that gets past everything in front of it), computed using only the retained primitives that are guaranteed to be in front of $k$. Then the color error from deleting all of $R$ satisfies

$$|C_{\text{full}} - C_{\text{pruned}}| \;\le\; \sum_{k \in R} \alpha_k \, T_k^{\text{ret}}.$$

The argument is a telescoping one. Deleting a single primitive $k$ changes the composite by $T_k \alpha_k (c_k - B)$, where $B \in [0,1]$ is the normalized composite of everything behind $k$. During any deletion sequence, $T_k$ never exceeds $T_k^{\text{ret}}$, because all retained occluders are still present.

The bound decouples the problem. We never need to bound the full sorted rasterizer, whose sorting permutations and products of opacities break standard bound propagation. Instead we need, per removed primitive and per pose cell, two things: an upper bound on its own opacity along any ray that hits its support, and an upper bound on the product of $(1-\alpha_j)$ over retained occluders that are provably in front of it. This mirrors how Certifying the Full YOLO Pipeline separated a neural backbone from discrete non-maximum suppression. Here the hard discrete part, the sort, is removed by a sound inequality rather than encoded in a mixed-integer solver.

Relation to Prior Work

Visibility-driven pruning already reasons about transmittance, but only on sampled views. Compressing Volumetric Radiance Fields to 1 MB and EAGLES score primitives by opacity weighted by accumulated transmittance over training rays. SafeguardGS shows that thresholding scene-wide scores can destroy scenes, and protects each ray's top contributor instead. HollowNeRF learns to hollow object interiors with a sparsity penalty. These papers motivate the proposal: they establish that most primitives are removable. We keep their goal and change the evidence, replacing "low score on observed views" with a proof over a continuous pose region.

Runtime culling methods attack the same waste differently. Proxy-GS culls with a proxy-mesh depth buffer, and CLoD-GS fades opacity with camera distance. Both are unverified, and neither reduces what must be stored or streamed for a region.

On the verification side, Pruning and Slicing Neural Networks using Formal Verification supplies the method. It proves neurons redundant within input slices, found 82.5% of neurons redundant within specific sub-domains, and showed that bounded errors from relaxed redundancies add rather than compound. Our bound is the rendering analogue of that additive-error lemma. Its "slices" become pose cells, and its 310-neuron networks become millions of explicit primitives.

DEEPSPLIT and GCP-CROWN show that the choice of where to split dominates branch-and-bound cost. DEEPSPLIT reports a roughly 20-fold explosion in branches without its indirect-effect heuristic. Both work on piecewise-linear networks, whereas our functions are Gaussian kernels under perspective projection, the "non-piecewise-linear" case the literature leaves open. We therefore borrow their branching philosophy, not their relaxations.

Two papers constrain the design. No Soundness in the Real World warns that real-arithmetic certificates can fail under floating-point execution, so we use outward-rounded interval arithmetic and report the deployed rasterizer's deviation separately. Moment-Based 3DGS replaces sorting with order-independent transmittance. Our bound assumes the standard sorted compositor, and extending it to moment-based compositing is left out of scope.

Research Program

The first component is a sound bounding routine for a single Gaussian over a pose cell. A pose cell is a box of camera positions together with the cone of ray directions that intersect the primitive's truncated ellipsoid. Over that cell, the routine produces an upper bound on the primitive's projected opacity and an interval for its sort depth. The 3DGS rasterizer uses an affine approximation of perspective projection, so opacity depends on camera position as well as on the ray. We bound the projected covariance and the exponent with interval arithmetic plus linear relaxations of the projection Jacobian.

The 3DGS rasterizer sorts per tile by center depth, so an occluder counts only if its depth interval lies entirely in front of the removed primitive's over the whole cell. Ambiguous cases are discarded conservatively.

The second component is branch-and-bound over pose space. Where the certificate is loose, we split the cell along the dimension with the largest bound gap, in the spirit of the input slicing above. This yields the region-of-poses guarantee without requiring a global Lipschitz constant.

The third component is what makes this scale spatially. The scene is partitioned into blocks, and each block gets a conservative aggregate occluder, for example the minimum accumulated opacity across the block along any ray through it. A wall-like block can then certify entire distant blocks invisible in one test. Occlusion is checked at block level first and refined to individual primitives only near the visibility frontier. Certification for different (pose cell, scene block) pairs runs in parallel on GPU. NICE-SLAM's frustum-only updates (NICE-SLAM) and Switch-NeRF's spatial experts (Switch-NeRF) show that partitioned scenes are the right unit for scale. We add occlusion along the ray, which frustum culling ignores.

The output is a per-cell visible set with an attached tolerance $\delta$. It can be streamed when a camera enters the cell, and the tolerance is a contract the renderer can check.

Baselines

The naive reference is the unpruned 3DGS scene, rendered for every pose in the region. It defines zero error, and its storage and frame rate are the costs to beat. On Mip-NeRF360, EAGLES reports vanilla 3DGS at 1042 MB.

The strongest published pruning method is SafeguardGS pixel-level rank pruning (SafeguardGS). It reports 27.07 dB PSNR on Mip-NeRF360 with 350k primitives versus the original 3159k. We also include EAGLES influence pruning, which reports 26.78 dB PSNR at 128 FPS and 100 MB on Mip-NeRF360. Both are run from the same trained scene, with no retraining after pruning for any method, to isolate the selection criterion.

The strongest competitor on this question is not either paper, though. It is our own dense-sampling baseline: render many poses sampled uniformly inside each cell, and keep every primitive whose maximum observed blending weight exceeds a threshold. The pose budget is matched to the wall-clock time our certifier uses. This baseline asks whether proof buys anything over brute-force coverage.

A Lipschitz-grid baseline certifies by sampling on a uniform grid and adding a global Lipschitz margin. It is sound, but it does not adapt to the scene.

Two ablations isolate our ingredients. The first disables pose-space splitting, certifying each region as one cell. The second disables block-level aggregate occluders, falling back to per-primitive checks only.

Beating the baselines means one of two outcomes. Either we match SafeguardGS-level primitive counts while keeping a certified worst-case error at or below $\delta$ (for example 1/255 or 4/255), where the heuristics show violations under adversarial pose search. Or, at equal certified worst-case error, we keep fewer primitives than the Lipschitz grid and take less time than dense sampling.

Why not just…?

Why not just sample poses densely inside each cell and prune heuristically? This is the real threat. At high sampling density it may match our primitive counts and our worst-case error in practice. We settle it empirically. For each pruned scene we run gradient-based and random-restart adversarial search over the cell, looking for the pose that maximizes per-pixel error. We then report the error distribution for sampled versus certified visible sets at matched compute. If sampling never violates $\delta$ at matched cost, our contribution narrows to the guarantee itself, which matters for robotics but not for compression. We will say so rather than claim compression gains.

Why not use a Lipschitz bound plus a grid, which is already a certificate? A global Lipschitz constant of a projected Gaussian's opacity with respect to camera position grows sharply as the camera approaches the primitive. A uniform grid therefore needs very fine spacing everywhere to cover the worst spots. The Lipschitz-grid baseline measures this directly. If adaptive splitting does not reduce certification cost substantially on Tanks and Temples and Deep Blending, the branch-and-bound component is unjustified.

Why not cull at runtime with a proxy depth buffer, as Proxy-GS does? Proxy-GS reports tripled frame rates. However, it still stores and streams every primitive, and correctness depends on the proxy mesh matching the splats. We compare streamed bytes per cell and worst-case error. These are complementary: certified sets could also be culled at runtime by Proxy-GS.

Why not feed the rasterizer to an off-the-shelf verifier such as α-CROWN or a MIP solver? The per-tile sort is a discrete permutation and the composite is a product of many opacities. Mixed-integer encodings of far smaller ReLU networks already time out, as DEEPSPLIT and GCP-CROWN document. Our additive bound avoids encoding the sort at all, so each check involves one primitive and its occluders.

Proposed Experiments

At room scale we use Mip-NeRF360, Tanks and Temples, and Deep Blending. Viewing regions are boxes around the test trajectories, expanded by radii of 0.1, 0.3, and 1.0 scene units, with orientation free within the field of view.

At large scale we use BungeeNeRF and Mill 19. The reference points there are CLoD-GS, which reports Amsterdam memory reduced from ~1592 MB to 445 MB, and Switch-NeRF, which reports 26.52 PSNR on Sci-Art. We report per-cell streamed size and certification time against scene size.

The metrics are PSNR, SSIM, and LPIPS on test views and on off-trajectory views, together with certified $\delta$ and adversarially found worst-case per-pixel error. We also report primitive fraction per cell, certification GPU-hours, and the deviation of the floating-point rasterizer from the certified real-arithmetic bound.

Three checks are decisive. The first is soundness: no adversarial pose may exceed $\delta$ beyond the measured floating-point deviation, and any such violation is a bug that invalidates the result. The second is the compression gap at equal certified error against the dense-sampling and Lipschitz-grid baselines. The third is scaling: certification time should grow roughly linearly with scene area because of block-level occluders. Without block occluders we expect much steeper growth, and the ablation will show whether the hierarchy is what makes city-scale certification feasible.