Likelihood-based generative models often rate simple inputs as more probable than the data they were trained on. The fix introduced for images is to subtract the input's compressed size under a generic compressor, such as PNG, from the model's negative log-likelihood. What remains measures how much better the trained model explains the input than a generic compressor does. That fix does not carry over to unordered continuous data such as 3D point clouds. Generic compressors read points in whatever arbitrary order they are stored, so their file size mixes three things: the shape's intrinsic complexity, the cost of that arbitrary order, and the numerical precision at which coordinates were written. We propose to compute both terms of the correction as code lengths of the same object: the same unordered collection of points, rounded to the same grid width. The tool that makes this possible is bits-back coding, a technique that lets a compressor "get back" the bits it spent on an arbitrary choice such as the order of elements. With it, the model term and the complexity term become achievable code lengths for the identical set.
The work has two deliverables that depend on each other. The first is a lossless codec for continuous point sets that removes the order cost and handles the rounding (discretization) step explicitly. The second is a complexity-corrected out-of-distribution score for point-cloud flows, together with a test of whether that score stays stable when the number of points and the grid width change. The central measurement is the grid width, which we call the discretization width. It is the quantity that prior work either tuned by hand or left mismatched between the model and the reference compressor.
Core Claim
For a point set $X$ of $m$ points in $\mathbb{R}^3$, rounded to a grid of width $\delta$, the ideal lossless code length under an exchangeable density $p$ is
$$L_\delta(X) \approx -\sum_{i=1}^{m} \log_2 p(\bar x_i) \;-\; 3m\log_2\delta \;-\; \log_2\frac{m!}{\prod_k n_k!}.$$
Here "exchangeable" means the density does not care about point order. The symbol $\bar x_i$ is point $i$ after rounding, and $n_k$ is the number of points that land in grid cell $k$. The middle term is the familiar cost of rounding. The last term is the order discount: the $\log_2(m!)$ bits a sequential codec wastes on a meaningless order. The discount shrinks when points collide in the same cell.
The collision correction is where rounding and order interact, and no paper in our file analyses it. At coarse $\delta$, simple shapes produce many collisions and receive a smaller discount than noisy ones, and the size of this effect depends on the shape.
Our claim is that a complexity-corrected score $S_\delta(X) = L^{\text{model}}_\delta(X) - L^{\text{ref}}_\delta(X)$ is meaningful only when both terms are computed at the same $\delta$ and on the same multiset (a set that may contain repeated elements). Under that condition the rounding term and the order term cancel exactly, and what remains is a genuine likelihood ratio between the trained model and a generic, input-adaptive reference.
The image-based corrections do not meet this condition. Input Complexity and Out-of-distribution Detection with Likelihood-based Generative Models subtracts the size of a discrete raster codec from the likelihood of a continuous model trained with added noise. Understanding Likelihood of Normalizing Flow and Image Complexity through the Lens of Out-of-Distribution Detection feeds JPEG2000 size into a two-dimensional Gaussian mixture. Serrà et al. already see this mismatch surface as codec-specific failures, such as JPEG2000 on sparse MNIST digits. We predict that for point sets the failure will be sharper: the mismatched score should drift as $m$ and $\delta$ vary, and the matched score should not.
Research Program
The codec stacks three bits-back layers, each taken from a prior paper.
The model. The generative model is PointFlow, which draws a shape-level latent $z$ and then models each surface point independently through a continuous normalizing flow conditioned on $z$. A continuous normalizing flow is an invertible map from simple noise to data, defined by an ODE.
Layer 1: shape latent. The shape latent is coded with standard bits-back using PointFlow's encoder as the approximate posterior. The achieved length is therefore the model's variational bound, not the exact likelihood, and we report that gap.
Layer 2: per-point flow. Each point is coded with local bits-back coding. Ho et al. made continuous flows usable as lossless codecs through a local linear approximation and reported 3.118 bits/dim against a 3.116 bits/dim likelihood on CIFAR-10. Their method's main cost is the Jacobian, the matrix of partial derivatives of the flow. Because PointFlow's flow acts on single 3D points, that Jacobian is only $3\times3$, so this part of their machinery is cheap here. Their central open problem, the tradeoff between injected noise $\sigma$ and grid width $\delta$, remains our object of study.
Layer 3: order. The order is removed with multiset bits-back coding as in Your Dataset is a Multiset and You Should Compress it Like One and Compressing Multisets with Large Alphabets. This scheme samples the next element to encode, without replacement, by decoding from the existing bitstream, and keeps the elements in a binary search tree so each step costs $O(\log m)$. It handles repeated elements natively, which is what we need for grid collisions. Those papers stopped at discrete alphabets. On grayscale MNIST they fell back to a lossy WebP codec and saved only 1.5%, compared with 7.6% on binarized MNIST. We supply the continuous-density path they skipped.
The reference compressor. The reference is not a second deep network. It is an input-adaptive, three-part description-length code in the spirit of Causal Inference via Conditional Kolmogorov Complexity using MDL Binning. For each input we fit a Gaussian mixture in 3D and choose the number of components by minimising three costs: the cost of stating the mixture parameters, the cost of coding which component each point uses, and the residual cost of each point's position at width $\delta$. We then code the points through the same multiset bits-back wrapper.
This design makes the reference play the role PNG plays for images. It is a generic compressor that finds low-level regularity in a single input, and its output is an achievable code length, so it is a computable upper bound on algorithmic complexity. Goldfarb and Evans worked only on one-dimensional variables and paid the order cost. Our version works on 3D point sets and removes it. As a second reference we also run an adaptive octree occupancy coder at the same $\delta$; an octree recursively splits space into eight cubes and records which are occupied.
Analysis. We sweep $\delta$ and $m$ and measure three things: how much the order discount shrinks from collisions as a function of shape, how the score drifts when $\delta$ is mismatched, and whether the 3D analogue of Osada et al.'s density-concentration effect appears. That effect is their finding that flows pull simple inputs toward the high-density centre of the latent space. We test whether PointFlow assigns inflated likelihood to spheres, planes and heavily smoothed surfaces. This has not been shown yet, and it is the first falsifiable question.
Baselines
Uncorrected likelihood. The do-nothing reference is PointFlow's raw negative log-likelihood per point, used as an out-of-distribution score with no correction. For compression, the do-nothing reference is the float32 coordinate array compressed with gzip in its stored order. If raw likelihood already separates the out-of-distribution sets, the premise fails.
Serrà-style correction with an ordered codec. This is the direct transplant of Serrà et al.'s score. The complexity term is the size of the rounded, serialised coordinates under a general-purpose compressor, in stored order and after Morton sorting. Morton sorting orders points along a space-filling curve so that nearby points sit near each other in the sequence. Both variants are rounded at the codec's own precision, as in the original work. It is the strongest published recipe for this question. It uses the same trained PointFlow and the same test sets, and it needs no tuning beyond the rounding precision, which we pick on held-out in-distribution data.
Octree reference at matched width. An adaptive octree occupancy coder is run at the same $\delta$ as the model term, and its code length replaces our Gaussian-mixture reference. This is the strongest simple competitor. It is order-free by construction and matched in precision, so it isolates whether our specific reference adds anything.
Osada's joint model. Following Osada et al., we fit a two-dimensional Gaussian mixture over (latent likelihood, complexity), using each complexity term above. This checks whether a learned combination beats simple subtraction.
Ablations. The ablations isolate the key ingredient. We drop the order discount by using sequence code lengths. We mismatch $\delta$ between the model and reference terms. We ignore collisions by using $\log_2 m!$ in place of the multiset term.
Reported numbers for comparison. On Lacuna, the strongest reported numbers for complexity correction are image-only. Serrà et al. report AUROC 0.950 for CIFAR-10 versus SVHN with Glow, against 0.083 for raw likelihood. Osada et al. report 91.47% AUROC against 47.86% for the typicality test. We found no reported result on Lacuna for complexity-corrected out-of-distribution detection on point clouds, nor for lossless compression of ShapeNet point clouds.
Criteria for success. Beating the transplanted Serrà baseline requires three things: higher AUROC on the simplicity and noise out-of-distribution sets, AUROC that varies by less than a few points across $m \in \{512, 2048, 8192\}$ and a decade of $\delta$, and no loss on semantic out-of-distribution sets. We will not claim that the codec beats the matched-width octree reference unless the gap exceeds seed-to-seed variation.
Why not just…?
Why not just sort the points canonically and subtract a standard compressor's size? Sorting removes the order cost only if the compressor's probability model is restricted to sorted sequences, and off-the-shelf codecs are not. Severo et al. note this for multisets. Lexicographic sorting also separates spatial neighbours in the sequence. Morton sorting preserves locality better, so it is included as a baseline rather than dismissed. What it still lacks is precision matching: its size depends on the chosen float serialisation, not on the model's $\delta$. The $m$ and $\delta$ sweep measures exactly this dependence.
Why not just voxelize and use an octree occupancy coder as the reference? This is the real threat, because an octree at the model's $\delta$ is already order-free and precision-matched. We run it as a full reference, not a strawman. Two differences remain. An occupancy octree codes only which cells are filled, so it drops collision counts unless we extend it. It also has fixed spatial contexts, whereas the three-part Gaussian-mixture code adapts per input the way Goldfarb and Evans's binning does. If the octree matches our reference on detection, we will report that precision matching, not the reference model, is what matters. The bits-back codec's contribution would then narrow to the compression result.
Why not just compute ideal code lengths and skip building a codec? For the detection score alone, this is correct: the analytic expression above suffices, and we will verify that it gives the same AUROC. The codec matters for two other reasons. It shows that the bound on complexity is achievable once the variational gap of the shape latent and the start-up cost of bits-back are included. Ho et al.'s local bits-back and Practical Shuffle Coding both show that these costs are not negligible for single objects. It also yields a usable lossless point-cloud compressor. We keep the two claims separate.
Why not just use Osada's joint Gaussian mixture on top of any complexity term? It is run as a baseline. It learns how to combine the two scores, but it cannot repair a complexity term whose units drift with $m$ and $\delta$. Osada et al. also concede that it fails on semantic out-of-distribution data with matched complexity, and we expect the same limit for our score.
Proposed Experiments
Data and training. We train PointFlow separately on the ShapeNet airplane, chair and car categories from ShapeNet, following PointFlow's protocol of 2,048 points per shape.
Out-of-distribution test sets. There are three families. The first is a 3D complexity ladder modelled on Osada et al.'s pooling-noise sets: random surface displacement fields smoothed progressively, ending at spheres and planes. The second is semantic outliers from other ShapeNet categories and ModelNet40, as in 3D ShapeNets. The third is the same in-distribution shapes resampled at different $m$, which must not be flagged.
Metrics. We report AUROC for detection. For compression we report bits per point relative to the ideal length and relative to gzip on floats.
Sanity checks. Two replications come first. We reproduce Serrà et al.'s CIFAR-10 versus SVHN result, so that our subtraction pipeline is shown to match theirs before moving to 3D. We also reproduce the 7.6% order saving on binarized MNIST with our multiset implementation.
Decisive checks. These are three concrete outcomes. Out-of-distribution AUROC under a matched $\delta$ should stay flat across the $m$ and $\delta$ sweep, while the mismatched ablation drifts. The measured order discount should fall below $\log_2 m!$ at coarse $\delta$ by an amount that separates simple shapes from complex ones. Our codec should come within a small fraction of a bit per point of the ideal length. If raw PointFlow likelihood shows no preference for simple shapes, the out-of-distribution half of the proposal is refuted, and the work reduces to the codec and the discount analysis.
References
- Input Complexity and Out-of-distribution Detection with Likelihood-based Generative Models
- Understanding Likelihood of Normalizing Flow and Image Complexity through the Lens of Out-of-Distribution Detection
- PointFlow: 3D Point Cloud Generation with Continuous Normalizing Flows
- Compression with Flows via Local Bits-Back Coding
- Your Dataset is a Multiset and You Should Compress it Like One
- Compressing Multisets with Large Alphabets
- Causal Inference via Conditional Kolmogorov Complexity using MDL Binning
- ShapeNet: An Information-Rich 3D Model Repository
- 3D ShapeNets: A deep representation for volumetric shapes