Learned compressors for 3D point clouds now reach much smaller files than the MPEG standard codec. They do this by predicting each node of an octree (a tree that recursively splits space into eight cubes and records which cubes contain points) from a large context of previously decoded nodes. The cost is that the compressed file is a single sequential stream. To ask whether one voxel is occupied, you must decode the whole frame. Succinct trees take the opposite approach. They store a tree as a compact bit string with a small index on the side, and they answer parent and child queries in constant time without decompressing anything. Their space, however, is fixed by the tree's shape, with no statistical modeling at all. This note proposes a structure that sits between the two. It is an octree that a program can navigate in place, whose size approaches the rate of a learned context model. The note also proposes a way to measure exactly how many bits per node random access costs relative to the best sequential learned coder.
The central idea is simple. If a node's probability model is allowed to depend only on its ancestors and on nodes in its own small block, then any node can be decoded locally. Its ancestors are already known after a root-to-node walk. A sparse index of block offsets locates the bits. The question that matters is quantitative: how much compression is lost when context is restricted this way, compared with the full-context sequential models? The proposal splits that loss into separately measurable gaps, in the spirit of the three-gaps analysis of learned image quantization in Three Gaps for Quantisation in Learned Image Compression.
Core Claim
We claim that a block-coded octree with three ingredients can store LiDAR and volumetric point-cloud geometry within a small, explicitly bounded margin of a learned sequential coder's rate, while answering point and root-to-leaf queries in microseconds rather than seconds. The three ingredients are an ancestor-only context model, a fixed probability table distilled from a neural network, and an Elias-Fano index of block offsets. The resulting excess over the sequential coder decomposes into four parts:
- A context-restriction gap: ancestors and in-block nodes only, versus the wide neighborhood used by sequential models.
- A context-quantization gap: a finite table of distributions in place of a network.
- A coding gap from per-block entropy coding.
- An index gap from the offset directory.
Of these, only the first is fundamental to random access. The other three can be driven down with resources. The novelty is not entropy-compressed succinct trees in general. It is a navigable tree whose space tracks a learned conditional entropy rather than the fixed shape count. It is also a direct measurement of what navigability costs against the strongest learned octree coders.
Where the Two Directions Meet, and What Is Missing
Succinct trees supply the navigation method. LOUDS (level-order unary degree sequence), as used for n-gram tries in A Succinct N-gram Language Model and Succinct Data Structures for NLP-at-Scale, writes each node's child count in breadth-first order. It uses rank and select (counting set bits up to a position, and finding the position of the j-th set bit) to move between parents and children. That costs about two bits per node regardless of the data. For an octree, the natural analogue stores one 8-bit occupancy byte per internal node, plus a prefix count of set bits to locate children. Elias-Fano Compression for Space-Efficient Rank and Select Structures shows that the side index can be squeezed to 2.297% overhead, at the cost of 9–38% slower queries. We reuse its Elias-Fano technique for our block directory. These structures constrain our design in one way: they show the index is cheap, so any large gap we find must come from modeling.
The compression-limits side motivates the work. On Random Tree Structures, Their Entropy, and Compression derives the entropy of simply generated trees as $H_C/(1-\bar C)$, which is the entropy of the child-count distribution times the expected tree size. Its TreeExplorer coder approaches this entropy. It does so through Lempel-Ziv coding, though, and the authors name query-preserving compression as open. That bound is order-zero: every node is drawn from the same distribution. Real octrees are far from that.
The learned octree coders show how far. OctAttention conditions on over a thousand ancestor and sibling nodes. Efficient Hierarchical Entropy Model for Learned Point Cloud Compression (EHEM) makes that context hierarchical and windowed. Learning to Predict on Octree for Scalable Point Cloud Geometry Coding treats occupancy prediction as 3D denoising. All three produce one serial stream with no in-place access.
Two neural-network papers sit closest to the intersection. Universal and Succinct Source Coding of Deep Neural Networks runs inference over a compressed tree-structured representation. Its sequential arithmetic decoding makes MNIST inference take 2.30 s versus 0.06 s uncompressed, which illustrates the cost we must avoid. Succinct Compression puts wavelet trees inside a PyTorch runtime. It only addresses flat weight sequences, not hierarchical context models.
Our proposal differs from all of these in one specific respect. It keeps a learned conditional model but restricts its context so that decoding stays local. It then measures the resulting rate penalty directly.
Research Program
The structure stores the octree in breadth-first order, with nodes within each depth level sorted in Morton order. Morton order interleaves the bits of the x, y, z coordinates, so spatially nearby cubes land near each other in the sequence. Each internal node carries its 8-bit occupancy symbol.
Grouping into blocks. Consecutive nodes are grouped into blocks of $b$ nodes. Each block is entropy coded independently with rANS (a fast arithmetic-style coder) using a fixed, shared probability table. Two monotone sequences are stored with Elias-Fano so that a block's bits can be found: the bit offset of each block, and the running count of occupied children. Breadth-first order has a useful property here. The children of a contiguous run of parents form a contiguous run at the next level. The ancestors of any block therefore occupy a few contiguous blocks per level.
Decoding. On a root-to-node walk, each step decodes at most one new block, because the ancestors are already cached. A cold point query decodes at most one block per level. The context for a node is a quantized feature of its ancestors and its parent's siblings, together with already-decoded earlier nodes in its own block.
Distilling the model. The probability model is built in two steps. First, a neural "teacher" is trained on the restricted context. It is a small transformer over the ancestor chain, which is the context OctAttention uses minus the cross-block neighbors. Its cross-entropy on held-out frames gives the reference rate for ancestor-only coding. Second, the teacher is distilled into a table of $K$ distributions over the 256 occupancy symbols, indexed by a learned quantization of context into $K$ classes. Decoding then needs only table lookups and no network evaluation. This is what makes microsecond queries plausible.
Accounting for the overhead. The index cost per node follows from the standard Elias-Fano space bound. Storing $m$ increasing integers bounded by $U$ takes about $m(2+\log_2(U/m))$ bits. With $m=n/b$ blocks and $U \approx nh$ total bits at $h$ bits per node, the overhead per node is
$$\Delta_{\text{index}} \approx \frac{2+\log_2(bh)}{b},$$
which is roughly 0.14 bits per node at $b=64$, $h=2$. The total measured rate $R_{\text{ours}}$, in bits per occupied point, is written as
$$R_{\text{ours}} = R_{\text{seq}} + \Delta_{\text{ctx}} + \Delta_{\text{quant}} + \Delta_{\text{code}} + \Delta_{\text{index}}.$$
The five terms are measured as follows:
- $R_{\text{seq}}$ is EHEM's rate.
- $\Delta_{\text{ctx}}$ is the ancestor-only teacher's cross-entropy minus $R_{\text{seq}}$.
- $\Delta_{\text{quant}}$ is the $K$-class table's cross-entropy minus the teacher's.
- $\Delta_{\text{code}}$ is the per-block rANS flush and rounding overhead.
- $\Delta_{\text{index}}$ is measured directly.
Each term has its own knob ($K$, $b$, context depth). The research output is the curve of every term against these knobs, together with query latency.
A secondary analysis connects this to the order-zero theory. When $K=1$, the table rate should match the simply-generated-tree entropy fitted to the empirical child-count distribution. That reproduces the Farzaneh et al. bound in a navigable form and shows how much learned context buys beyond it.
Baselines
The naive reference is the plain succinct octree: one raw occupancy byte per internal node in breadth-first order, plus a rank index on the popcount sequence, using the Orzo-style layout from Elias-Fano Compression for Space-Efficient Rank and Select Structures. It is the zero-modeling, fully navigable point and sets the space ceiling. We beat it if we cut its size by well over half at comparable point-query latency.
The order-zero navigable baseline uses the same block layout with $K=1$. It isolates the value of learned context from the value of entropy coding alone.
The strongest compression competitor is EHEM. It reports a 28.89% bitrate reduction over MPEG G-PCC and a 19.47% reduction over OctAttention on SemanticKITTI. It decodes a 16-bit frame in roughly 1.9–3 s, against 708 s for OctAttention. On 8i sequences, Mao et al. report an average 32.1% lossless bitrate reduction over G-PCC. The file gives these only as relative reductions. We found no absolute bits-per-point figures on Lacuna for EHEM on SemanticKITTI, so we will retrain EHEM from its description and measure its absolute rate on identical frames and quantization depths. If the retrained model does not reproduce roughly the reported margin over G-PCC, which we will run ourselves, we will say so and report against G-PCC as the fixed anchor. Our teacher and table get the same training split, and a parameter count and training-step budget no larger than EHEM's.
We count as beating EHEM on the joint objective if our rate is within 10% of EHEM's while point queries are at least three orders of magnitude faster than EHEM's full-frame decode. We do not expect to beat it on rate alone. No reported result was found on Lacuna for random-access query latency of any learned octree coder, so that comparison is new measurement.
The key ablation removes the context restriction in a deliberately non-navigable way: the same table design, but with contexts allowed to use cross-block neighbors. This isolates $\Delta_{\text{ctx}}$ from the coding and index terms.
Why not just…?
Why not just split the frame into spatial tiles and code each tile independently with EHEM? This is the most serious alternative, and it may win for workloads that read whole regions. Tiling gives random access at tile granularity. However, each tile pays its own entropy-coder flush, and it loses the context of neighbors across tile borders. A point query also still runs the attention network over an entire tile. Our blocks share ancestor context across block boundaries, so shrinking $b$ costs only index bits and not context. The experiment settles the question by sweeping tile size for tiled EHEM and block size for our structure. We plot rate against cold point-query latency and against box-query latency. If tiled EHEM dominates our curve for box queries larger than a few tiles, we will report that our structure is the right choice only for point queries and sparse traversals.
Why not just entropy-code the occupancy bytes with one global distribution and sampled entry points? That is exactly our $K=1$ baseline. Farzaneh et al. show such order-zero coding reaches the simply-generated-tree entropy, so it is a correct but limited answer. The gap between $K=1$ and large $K$ measures whether learned context is worth carrying into a navigable structure. If that gap is small, roughly under 10%, the learned component is not justified and the simpler design should be preferred.
Why not just decode the EHEM stream once and keep a pointer-based or plain succinct octree in RAM? This works when one frame is queried heavily after loading. It fails when many frames must stay resident, or when queries arrive at stored data, because resident size reverts to the 8-bits-per-node naive reference. The pointer-overhead figures for tries in Pauls and Klein and Petri and Cohn show how quickly this dominates memory. We will report a break-even curve: the number of queries per frame at which decode-once beats in-place access in total time. We will also report resident memory for a fixed set of 1,000 frames.
Proposed Experiments
Data and training. Training uses the SemanticKITTI training sequences. Testing uses held-out sequences at 12-bit and 16-bit quantization, and 8i Longdress and Soldier frames, all with lossless geometry.
Rate measurements. For every configuration we report:
- bits per occupied point and bits per internal node;
- each gap term separately;
- the $K=1$ order-zero rate compared against the fitted simply-generated-tree entropy.
Latency measurements. We report cold point-query latency, cached root-to-leaf traversal latency, axis-aligned box-query latency, and full-frame decode time. All are measured single-threaded on the same CPU. EHEM decode is reported on both CPU and GPU for transparency.
Sweeps. The sweeps cover $b \in \{16, 64, 256, 1024\}$, $K \in \{1, 16, 256, 4096\}$, and ancestor context depth from one to eight levels.
Decisive checks. There are two. The first is whether $\Delta_{\text{ctx}}$, the only term that cannot be engineered away, stays below about 10% of EHEM's rate on SemanticKITTI. If it exceeds about 25%, the conclusion is that wide same-level context is essential to learned octree coding, and that in-place navigability at learned rates requires a different factorization. The second is whether the sum of the other three terms falls below 0.3 bits per node at $b=64$, as the Elias-Fano estimate predicts. Missing that target would point to the coding overhead, not the index, as the bottleneck.
Generalization check. Testing the SemanticKITTI-trained table on 8i shows whether a fixed distilled table generalizes across sensor types, or whether per-domain tables are needed.
References
- Three Gaps for Quantisation in Learned Image Compression
- A Succinct N-gram Language Model
- Succinct Data Structures for NLP-at-Scale
- Elias-Fano Compression for Space-Efficient Rank and Select Structures
- On Random Tree Structures, Their Entropy, and Compression
- OctAttention: Octree-Based Large-Scale Contexts Model for Point Cloud Compression
- Efficient Hierarchical Entropy Model for Learned Point Cloud Compression
- Learning to Predict on Octree for Scalable Point Cloud Geometry Coding
- Universal and Succinct Source Coding of Deep Neural Networks
- Succinct Compression: Lossless Compression for Fast and Memory-Efficient Deep Neural Network Inference
- Faster and Smaller N-Gram Language Models