Research map / Architectures and efficiency / RNNs and normalization
Accelerating Relative Entropy Coding with Space Partitioning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes relative entropy coding with space partitioning (search heuristic P' via per-bin reweighting) that cuts PFR/ORC runtime and improves bitrate on MNIST VAE and CIFAR-10 INR compression.
Problem
Relative entropy coding (REC) algorithms have encoding time around 2^{KL[Q||P]}, which is prohibitive; existing accelerations only work for 1D or very restricted distributions, and block-wise splitting adds overhead.
Approach
Partition the coding distribution's support into J equal-mass bins and sample bins from a categorical pi chosen from Q, so that the reweighted prior P' aligns better with Q; the scheme is equivalent to running standard PFR/ORC with P' and keeps the codelength bound with a small extra epsilon cost. Dimension-wise mutual information is used to allocate grid intervals per axis.
Key results
- On 5D Gaussian toys, space partitioning reduces PFR runtime by up to three orders of magnitude while maintaining codelength for exact samples.
- On MNIST VAE lossless compression, the method's codelength is about 2% worse than the theoretical optimum and about 6% better than GPRS.
- On CIFAR-10 with RECOMBINER, using 48-bit blocks reduces codelength by about 10% with fine-tuning and 15% without, relative to standard ORC with 16-bit blocks, and stays within 2% of the theoretical optimum.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use space partitioning with block size KL=48 bits instead of standard ORC with block size KL=16 bits | RECOMBINER · CIFAR-10 | codelength: approximately 10% with fine-tuning and 15% without | Helped |
| Use space partitioning with block size KL=48 bits instead of standard ORC with block size KL=16 bits | RECOMBINER · CIFAR-10 | codelength gap to theoretical optimum: within 2% | Helped |
| Use space partitioning for encoding latent embeddings | VAE · MNIST | codelength: about 6% better | Helped |
| Use space partitioning for encoding latent embeddings | VAE · MNIST | codelength gap to theoretical optimum: 2% worse | Hurt |
| Partition the search space | PFR · 5D synthetic Gaussian examples | runtime: up to three orders of magnitude | Helped |
| Partition the search space | ORC · 5D synthetic Gaussian examples | sample size for a given bias: much smaller sample size | Helped |
| Assign intervals to dimensions according to mutual information rather than only partitioning the collapsed dimension (ablation) | ORC · 5D Gaussian toy example | approximation error | Helped |
| Partition only the collapsed dimension (ablation) | ORC · 5D Gaussian toy example | approximation error | No clear effect |
| Assign intervals according to mutual information rather than randomly across dimensions (ablation) | Space-partitioned REC · 5D Gaussian toy example | runtime | Helped |
| Assign intervals according to mutual information rather than randomly across dimensions (ablation) | RECOMBINER · CIFAR-10 | rate-distortion | Helped |
| Remove dimensions with mutual information approximately 0 before randomly assigning intervals to the remaining dimensions (ablation) | RECOMBINER · CIFAR-10 | rate-distortion: only slightly worse | Hurt |
Surprising findings
- Partitioning only along an uninformative (zero-mutual-information) dimension yields almost the same results as standard ORC, so partition allocation across axes matters.
- For some distributions with mismatched variance, PFR runtime diverges and space partitioning can do little, since the allowed number of partitions J shrinks to 1.
Limitations
- In practice limited to axis-aligned grid partitions for factorized distributions.
- Requires mutual information to be factorized per dimension and shared between sender and receiver, restricting non-factorized or one-shot settings.
- Space partitioning gives little benefit when the KL divergence is small or PFR diverges (e.g., posterior variance approaching prior variance).
Experimental setup
Datasets: MNIST CIFAR-10
Benchmarks: MNIST CIFAR-10
Metrics: codelength / bitrate runtime (number of steps) maximum mean discrepancy rate-distortion
Baselines: standard PFR standard ORC GPRS RECOMBINER
Builds on: Poisson functional representation ordered random coding greedy Poisson rejection sampling RECOMBINER
Closest papers by meaning
- Optimal Neural Compressors for the Rate-Distortion-Perception Tradeoff (NeurIPS 2025 · similarity 0.86)
- Minimum Entropy Coupling with Bottleneck (NeurIPS 2024 · similarity 0.86)
- Approaching Rate-Distortion Limits in Neural Compression with Lattice Transform Coding (ICLR 2025 · similarity 0.85)
- Entropy Coding of Unordered Data Structures (ICLR 2024 · similarity 0.85)
- Debiased Distribution Compression (ICML 2024 · similarity 0.84)
- Laplacian-guided Entropy Model in Neural Codec with Blur-dissipated Synthesis (CVPR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.