Accelerating Relative Entropy Coding with Space Partitioning
Authors: Jiajun He
Gergely Flamich
José Miguel Hernández-Lobato
Venue: NeurIPS 2024 poster (2024)
Keywords: Relative Entropy Coding; Neural Compression; Information Theory
Primary area: probabilistic_methods
TL;DR: We propose a new REC scheme utilizing space partitioning to reduce runtime in practical neural compression scenarios.

Abstract: Relative entropy coding (REC) algorithms encode a random sample following a target distribution $Q$, using a coding distribution $P$ shared between the sender and receiver. Sadly, general REC algorithms suffer from prohibitive encoding times, at least on the order of  $2^{D_{\text{KL}}[Q||P]}$, and faster algorithms are limited to very specific settings. This work addresses this issue by introducing a REC scheme utilizing space partitioning to reduce runtime in practical scenarios. We provide theoretical analyses of our method and demonstrate its effectiveness with both toy examples and practical applications. Notably, our method successfully handles REC tasks with $D_{\text{KL}}[Q||P]$ about three times greater than what previous methods can manage, and reduces the bitrate by approximately 5-15\% in VAE-based lossless compression on MNIST and INR-based lossy compression on CIFAR-10, compared to previous methods, significantly improving the practicality of REC for neural compression.

Accelerating Relative Entropy Coding with Space Partitioning
Jiajun He University of Cambridge jh23838cam ac
Gergely Flamich University of Cambridge gf3320cam. ac. uk
José Miguel Hernández-Lobato University of Cambridge jmh2330cam. ac
Abstract
Relative entropy coding (REC) algorithms encode random sample following a target distribution Q, using coding distribution P shared between the sender and receiver. Sadly, general REC algorithms suffer from prohibitive encoding times, at least on the order of 2 [211))) and faster algorithms are limited to very specific settings. This work addresses this issue by introducing a REC scheme utilizing space partitioning to reduce runtime in practical scenarios. We provide theoretical analyses of our method and demonstrate its effectiveness with both toy examples and practical applications. Notably, our method successfully handles REC tasks with DxL | about three times greater than what previous methods can manage, and reduces the bitrate by approximately 5-15% in VAE-based lossless compression MNIST and INR-based lossy compression on CIFAR-10 10, compared to previous methods, significantly improving the practicality REC for neural compression.
Introduction
Let's consider two-party communication problem where the sender wants transmit some data X to the receiver. A widely used approach is transform coding (Ballé et al., 2020), where X is first transformed to a discrete variable Z and entropy coded achieve an optimal codelength on average. However, directly finding discrete Z is difficult in many scenarios. For example, in lossy image compression, represents some image, and Z represents the latent embedding output by an encoder network in a model akin to the variational auto-encoder (Kingma and Welling, 2013). A common solution to obtain a discrete Z is to first learn continuous variable and quantize it (Ballé et al., 2017).
However, perhaps surprisingly, there is also a way to directly handle continuous Z in this pipeline. Specifically, instead of deterministic value, the sender transmits a random sample following posterior Z Qzix' These algorithms are referred to as relative entropy coding (REC. Flamich al., 2020), and also known channel simulation or reverse channel coding (Theis and Yosri, 2022).
Li and El Gamal (2018) showed that the codelength of such an algorithm is upper-bounded by the mutual information between X and Z plus some logarithmic and constant overhead:
[X; ZJ + 1og, [[[; ZJ 1) 0(1).
(I)
REC has clear advantage over quantization: quantization is non-differentiable operation, while REC directly works for continuous variables and eases the training of some neural compression models, which highly rely gradient descent. Also, Theis and Agustsson (2021) exemplified that stochastic encoders can be significantly better than their deterministic counterpart if we target realism.
TTo avoid notation overload, will use Q for the posterior, omitting its dependence on X unless needed. Throouhhot this paper, unless otherwise stated, we use log, to calculate the log density ratio, the Kullback- Leibler (KL) divergence DKL. the mutual information / and the Rényi-co divergence Dz.. We use upper-case letters (e.g., Q and P) to represent probability measures and lower-case letters (e.g., 9 and p) for their densities.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

However, the encoding time of REC algorithms is at least typically on the order of 2 PI, which is prohibitively long practice. While there are several works on accelerating REC (Flamich et al., 2022; Flamich and Theis, 2023; Flamich et al., 2024), so far they only work on highly limited problems. In fact, in practice, the common option to employ REC to segment into the concatenation of independent blocks, denoted as 2 = [Z Z...... Zk]. each block Zµ is approximately x bits. This strategy reduces the runtime to ( However, by Equation (I), the logarithmic and constant overhead only becomes negligible if [[x; Z,J is sufficiently large. For example, for the runtime to be feasible, k is set between 16 to 20 in Havasi et al. (2019); Guo al. (2024); He et al. (2023). In this case, the overhead will typically constitute 40% to 50% of the total mutual information, resulting in sub-optimal compression performance.
where the coding cost of
Our work's 's primary aim is to reduce the complexity of REC runtime for more practical settings. Specifically, our contributions are
We propose faster REC framework based on space partitioning. Equivalently, our method can be viewed as introducing a search heuristic to a standard REC algorithm, which can significantly reduce the algorithm's runtime when chosen appropriately. Furthermore, we provide theoretical analysis, showing that our method achieves a close codelength to Equation (1) with an extra cost that is negligible for some commonly used distributions in neural compression.
We show that, interestingly, using different space partitioning and different search heuristics only influences the runtime but not the (upper bound on) codelength. Following this, discuss two cases: 1) encoding exact samples from the target and 2) encoding approximate samples to further reduce the computational complexity.
We draw attention to a hitherto unused fact for designing fast, practical relative entropy coding schemes: when the sender wishes to communicate vector-valued random variate Z X to the receiver, we may assume that they share knowledge of the dimension wise mutual information I[2;; XJ for each dimension i, opposed to just the total Z[ XJ. Incorporating this information into our space partitioning scheme allows us to construct faster relative entropy coding algorithms.
We conduct experiments on synthetic examples and neural codecs, including a VAE-based lossless codec on MNIST (LeCun and Cortes, 1998) and INR- lossy codees on CIFAR- 10 (Krizhevsky et al., 2009). We demonstrate that our method can handle blocks with larger using much fewer samples and reduces the bitrate by approximately 5-15% compared to previous methods.
2 Preliminary
In this paper, we focus accelerating the Poisson functional representation (PFR; Li and El Gamal, 2018) and ordered random coding (ORC; Theis and Yosri, 2022), and hence we discuss these in detail below. However, note that our space partitioning scheme is also applicable other relative entropy coding (REC) algorithms (Flamich and Theis, 2023; Flamich et al., 2024; Flamich, 2024).
Relative entropy coding (REC). Consider a two-party communication problem, where the sender wants to transmit some data X to the receiver. However, instead of encoding X directly, the sender first transforms X into representation Z that they encode. In REC, we allow Z to be stochastic with ~ Qz Then, the goal of REC is to encode a single, random realization Z ~ Qz with the assumption that the sender and receiver share coding distribution P and have access to common randomness S. In practice, the latter can be achieved by a shared pseudo- random number generator (PRNG) and seed. Given these assumptions, the optimal coding cost is given by H| Z ST, as the code cannot depend on X since the receiver doesn't 't know it. Surprisingly, Z can be encoded very efficiently, as Li and El Gamal (2018) show that
[[: Z)
H
S1 < [[ + log, (1[x + + O(1)
(2)
Note that X[x: Z] and hence Z S can be finite even Z is continuous and H is infinite. Next, we describe a concrete scheme with which we can encode Z at such an efficiency.
Poisson functional representation (PFR). To encode a sample from the target distribution Q with density y using the coding distribution P with density p. PFR (Li and El Gamal, 2018) starts by
We note that REC's decoding is very fast, so in this paper, runtime will refer exclusively encoding time.

---

(a) Procedure of standard REC algorithm.
(b) Procedure of REC with space partitioning.
Figure 1: An illustrative comparison between the standard REC algorithm and REC with space partitioning. We illustrate the prior I's density in blue and Q's density orange. (a) In standard REC algorithm, we may draw numerous samples (colored in red) before identifying one that aligns well with Q (colored green). The majority of these samples not directly contribute the desired result. (b) In the method we propose, we first divide the search space into smaller grids and then reweight each grid. This amounts to adjusting the prior P search heuristic P', which can align better with Q. The samples from P' will thus be more relevant to Q, potentially reducing the runtime.
drawing a random sequence 1 Zz. from using the public random state S. Furthermore, the sender draws sequence of random times Ti, T2, ... follows:
To 0, T, - T ATH, AT, ~ Exp(1), 1,2.
Tn/r(Zn) for each sample and returns N < arg [T.). Using the theory Poisson processes, can shown that ZN= ~ Q as desired (Maddison, 2016). Additionally. while the minimum is taken over all positive integers, in practice, N* can be found in finite steps if bounded. In fact, in expectation, PFR will halt after 2Q P) steps (Maddison, 2016). We summarize this process in Algorithm
Next, letting = q/p be the density ratio, the sender calculates
Ordered random coding (ORC). Unfortunately. PFR's random runtime can be significant draw- back. In practice, may want to set limit the number of iterations to ensure consistent and manageable runtime at the cost of some bias in the encoded sample. To this end, Theis and Yosri (2022) proposed ordered random coding (ORC). Specifically, in ORC with N candidates, rather than calculating Tū by Equation (3), we first draw N i..d. sample from Exp(1), and sort them in ascending order Ti & T3 & & Tye We then set T, TV for each 1, 2, ... .N. In practice, instead of generating the Tn-s O(N log N) time by sorting, Theis and Yosri (2022) suggest an iterative procedure similar to Equation (3) with O(N) time complexity:
To 0, Tn ~ Tn-1 + N/IN - AT, AT, Exp(1),
n n= 1,1,2, 1,2,".,, N
(4)
3 Relative Entropy Coding with Space Partitioning
In this section, we describe our proposed algorithm and analyze its codelength. To motivate our method, recall that in PFR, the sender draws random sequence from P, and examines each sample's density ratio. We can interpret this process as a random search in P's support, aiming to find point that has a relatively high density ratio between and P. However, when Q concentrates only within small region of P's support, most of the search does not contribute to the final outcome. Thus, can we instead quickly navigate the search towards the region where Q concentrated?
For one-dimensional distributions Q and P, the answer is affirmative, as we can perform branch- and-bound search by partitioning the ID space on the fly (Maddison et al., 2014; Flamich al., 2022). Unfortunately, it is unclear how to generalize these adaptive partitioning strategies to spaces with dimension greater than one. Instead, in Section 3.1, we propose to partition the space in advance according to rule that the sender and receiver agree on such that we can carry out the search fast enough in practical problems and retain an efficient codelength.
3.1
Coding Scheme
Given a shared coding distribution P and a target Q, our algorithm proceeds as follows:
The sender and receiver agree on partition of P's support consisting of bins (B,,..., By) with equal probability mass, i.c. P(B,) 1/s for j 1,...,JJ J. As we will discuss later, these
3

---

Algorithm Encoding of standard PFR
Algorithm 2 PFR with Space Partitioning
Input:
Q, P and a random state S. Output: Sample index N*.
Input: Q. P. and random states (8
Output:
Bin index j", local sample index 1 # initialize:
# initialize:
00,40 t0
N 0.
T - 00,0,, 40 + 0, 0, - 0, 0, 0.
2(2)
Partition space in "bins,, s.t. P(B,) = 1/J.
Tmax sup2
M())
Select categorical distribution x.
2 0 for j = 1,2, 2..................... J
2 P(B,) pla G
max - max 1,-., SuppEn
# run PFR: for 1, do
run PFR:
for n = 2, do
Sample Atn Exp(1); in - 1--11 + Atn.
Sample At, Exp( 1): in + -n-11 Atn.
simulate a sample with PRNG:
simulate sample with PRNG:
In 12 - -2 +1.
2n - PRN
Zn - (PNG(P Sini
update 7*:
# update 7*:
Tn tn p(zz p(zn)/q(Zn)
Tn - J --JJT(ji (ja) tn p(zn)) (zm))
if Tn & 7 then
if Tn 7* - Tuy j - Jay n - Re...
7* then
7 Tu. N - n.
T
end if
end if
check stopping criterion:
# check stopping criterion:
if tn 4n/Tmax 7* then
if tt.//'m /mm 7 then
break end if
break end if end for
end for
bins can overlap. but to aid understanding for now, it may be helpful to imagine the space is partitioned by non-overlapping bins.
According the target distribution Q, the sender selects a categorical distribution for the bins, with event probabilities defined as T()) for j = 1, 2, .J. We can view this categorical distribution as reweighting of each bin to adjust the coding distribution P. The coding distribution adjusted by this reweighting can be better aligned with Q. We will discuss the choice of π later.
3. Then, the sender starts to draw and examine samples iteratively, similar to the PFR algorithm. However, instead of drawing samples directly from P, the sender first samples bin from æ and then draws a sample from the prior restricted to this bin. Specifically, at each iteration n:
(a) the sender first draws bin index, Jn. according to the distribution m
(b) the sender then draws sample Zn Pl This sample is generated with the random state Sj. associated with this bin. It's critical that each bin has a unique random state to ensure different bins have different random sample sequences. In practice, this can be easily achieved by setting the PRNG's seed of the bin B, to j. for j 1, 2.... J. Note that given these random states, the value of Zn is uniquely determined by the bin index In and its sample index within this bin, which we denote by îúj.. For the sake of clarity, we will call n the global sample index and n.j, the local sample index hereafter;
(c) the sender examines the sample by calculating Tn:
Tn - Tw/r', r' = q( Zw/)/'m P', ((.))(Z.))/(LL)
J- (Ja)) p(Z,), (5)
and keeps track of N arg min, 1,2, (7.). Here, T, is also obtained by Equation (3); (d) finally, the sender checks the following stopping criterion:
sup (2)
Tafri max > T
I'max
max 1-,,2.-..
(6)
zeB, p(z)x(j)
If the criterion is met, halt and return jNv and à N=: otherwise, proceed the next iteration.
'PRNG(P, S, n) means simulating the n-th sample in the random sequence from P PRNG with seed S.

---

We detail the above coding scheme in Algorithm 2. As a comparison, we describe the standard PFR algorithm in Algorithm 1, and highlight their difference in red. We also illustrate these two algorithms from high-level point of view in Figure 1. It is easy to verify that Algorithm 2 is equivalent to running standard PFR with an adjusted prior P', whose density is defined as
f/(z) Σ - 1(2 [)) T()p(z)) P(B,)
Therefore, the encoded sample is guaranteed to be Q-distributed. By choosing a sensible x, the adjusted prior P' can be more closely aligned with Q than the original P, potentially decreasing the runtime. From this point forward, we will refer to P' as the search heuristic.
Note that the receiver does not need to be aware of x to decode the sample. Instead, after receiving the bin index jN*, the receiver can construct the random sequence from PlB,,. with seed S Then, taking the á N -th sample in this sequence, the receiver successfully retrieves the desired sample.
3.2 Codelength of the two-part code
In our proposed algorithm, the sender needs to transmit two-part code that includes both the bin index and the local sample index. This is distinct from the standard PFR, where the sender transmits only the sample index, hence potentially raising concerns about the codelength. Indeed, we find the two-part code can introduce an extra cost, as outlined in the following theorem:
Theorem 3.1.
Let a pair of correlated random variables X, ~ Px.z be given. Assume we perform relative entropy coding using Algorithm& 2 and let j* denote the bin index and ń the local sample index returned by the algorithm. Then, the entropy of the two-part code is bounded by
H|j", π E 1[x: 2J + Ex|e] + (0 ZJ logg J + Ex[e] + +1)+1 +4,
(8)
max 0, logg J logg ((2)
where e Eg~QZIx
p(z)
We prove Theorem 3.1 in Appendix C.I. Note, that when /[x; Z] is sufficiently large, the term logg ( Z] log, J + Ex[{] + 1) + 4 will be negligible. However, without further information on Q and P, it is difficult to assert how small Ex [e] is. We can view as the extra cost introduced by the space partitioning algorithm. Fortunately, for commonly used distributions in neural compression, including Uniform and Gaussian, we have the following conclusion under reasonable assumptions:
Proposition 3.2 (Bound of for Uniform and Gaussian). Assume setting J & 2Pxl1 P] when running Algorithm 2 for each Qz|x- Then, for Uniform Q and P. if Q & P (i.e., Q is absolute 0; for factorized Gaussian Q and P, if Q has smaller variance than
continuous w.r.t P), we have P along each axis, we have & 0.849 DKL[Q P]. and Ex[c] & 0.849
We prove Proposition 3.2 in Appendix C.2. Also, we highlight that the conclusion for Gaussian in Proposition 3.2 derived by considering the worst case when P has the same variance as Q along all dimensions. In practice, this worst case can barely happen since in neural compression P represents the prior, and Q represents the posterior, which will be more concentrated than the prior. Empirically, we find this c-cost yields no visible influence on the codelength (e.g., Figure 2b in Section 5).
3.3 Generality of our Space Partitioning Algorithm
We highlight that the conclusions in Section 3.2 are independent of the partitioning strategy and т. This allows to use different without the need to revisit the bound of the codelength.
More interestingly, we do not need to partition the space with non-overlapping bins. This is because the density of P', as stated in Equation (7), can be directly interpreted as mixture of priors with J components, where T()) represents the mixture weights. There are no restrictions preventing this mixture model from having overlapping components. We provide more explanation and discussion on overlapping components in Appendix I. As an extreme case, we can even have entirely overlapping bins. Notably, this scenario coincides with the "parallel threads" version of REC proposed by Flamich (2024). Concretely, Flamich (2024) proposed to initiate several threads for a single REC task and run them in parallel on various machines, thereby decreasing the runtime.
5

---

Furthermore, the concept of space partitioning and its codelength, as stated in Theorem 3.1, extends beyond the scope of Poisson functional representation algorithms. Here, we state the codelength by applying our proposed space partitioning method to greedy Poisson rejection sampling (GPRS) (Flamich, 2024) and leave its application to other REC algorithms for future work.
Theorem 3.3. Let a pair of correlated random variables X, Z ~ Px,z be given, Assume we perform relative entropy coding using GPRS with space partitioning and let j denote the bin index and n the local sample index returned by the algorithm, and e be as in Equation (9). Then,
H[j n [[ + Ex[d] + log2(1[X; Z] - logg J + Exld + +)
(10)
We prove Theorem 3.3 in Appendix C.3. Additionally, since we can view the "parallel threads" version of GPRS as a special case of our proposed method, Theorem 3.3, and hence Proposition 3.2, offer alternative bounds for Theorem 3,5 in Flamich (2024).
4 Exemplifying the choice of Partitioning Strategy and π
In the above sections, we do not specify the partitioning strategy and æ. In this section, will exemplify their choices. To keep our discussion simple, we take the assumption that both Q and P fully-factorized distributions. This covers a majority of neural compression applications with relative entropy coding, including both VAE-based (Flamich et al., 2020) and INR-based codecs (Guo al., 2024; He et al., 2023). Under this assumption, we adopt a simple partitioning strategy to split space with axis-aligned grids, which allows us to draw samples and evaluate the density ratio easily.
Now, let's focus и. We consider two scenarios: 1) the sender aims to encode sample that exactly follows Q. and 2) the sender encodes a sample following Q approximately for a more manageable computational cost. As we will see, the optimal choice of ι differs in these cases.
We note that the latter garners more interest in practical neural compression. This is because we can always construct an example where the standard PFR algorithm does not terminate while the first sample from the prior already has little bias. As an example, take ((2) (==00.001, o²), and 1). When / (approaching I from below), the expected runtime for PFR diverges:
p(z) (=) 20x1Q11P] - cc. Unfortunately, our proposed space partitioning approach can do little in this case. This is because, for a small e-cost, as stated in Proposition 3.2, the number of partitions J should be less than 2Px Pl, which reduces to when 0 / 1. For minlti-dimeniionall (factorized) Q and P. this issue will occur whenever it arises in any single dimension. Making things even worse, this example is pervasive in neural compression due to numerical inaccuracies. Therefore, limiting the number of candidate samples is more practical than running the PFR algorithm until the stopping criterion is met. Consequently, we will mainly study the non-exact case in the following, but for the sake of completeness, first discuss the exact scenario.
4.1 Exact Sampler
When encoding sample following Q exactly, we hope minimize the expected runtime by adjusting the search heuristic P'. Since we can view our proposed algorithm as running standard PFR with P', its expected runtime is 2oo IP], Thus, we have the following constrained optimization problem:
sup ((2)
}
arg min
max 1- 1-1.2,n
BeB, p(z)=(j)
subject to T() = 1.
(11)
The solution turns out to be intuitive:
(Z)) p(z) sup g(z) B, p(z)
T()x sup B,
(12)
However, sampling from this л is generally challenging. Fortunately, if Q and P are both factorized and we partition the space with axis- aligned grids, then factorizes dimensionwise into a product of
categorical distributions. Also, this choice π simplifies the evaluation of the stopping criterion
in Equation (6). Specifically, T'mex simplifies to r'mmx = Z - J where Z = - T(ÿ) denotes the normalization constant. This constant is shared in both the maximum density ratio r'max and the density ratio for individual samples. We thus can omit when evaluating the stopping criterion. We
detail the procedure in Algorithm 3 in Appendix A.I.

---

4.2 Non-exact Sampler
If we only need encode a sample following Q approximately, we can apply our space partitioning strategy to ordered random coding (ORC), In this case, we hope to reduce the bias with the same sample size or reduce the sample size for the same bias. To determine the optimal choice of n, we state the following corollary on ORC's bias. This is a corollary of Theis and Yosri (2022, Lemma D.I) and Chatterjee and Diaconis (2018, Theorem 1.2). We present the proof in Appendix C.4.
Corollary 4.1 (Biasness of sample encoded by ORC). Given a target distribution Q and a prior distribution P. run ordered random coding (ORC) to encode sample. Let Q be the distribution of encoded samples. If the number of candidates is N 2Paa p]+t for some t 2 0, then
1/2
22-14+ (1(2-14 2 P log
((2) p(z)
> DKL p1+ 1 2))
Dr(2. Q1 <
(13)
Conversely, supposing that N = 2Dxll p]- for some t E 0, then
DivL Q] > 1 - 2-2 P (log g(2) p(z) & DKLIQ 11
P]
(14)
2
This corollary tells us that when running ORC with target Q and prior P. if the density ratio between Q and P well concentrated around its expectation, choosing N 2DkalQQ I P) candidates is both sufficient and necessary to encode a low-bias sample in terms of total variation (TV) distance. Recall that our proposed algorithm can be viewed as running ORC with the search heuristic P' as the prior. We, therefore, want to choose π to minimize the KL-divergence between the target Q and the search heuristic P', The optimal π turns out to be surprisingly simple:
T(i) = Q(B.).j = 1,2, JJ
(15)
This is because D P7 DKLIQ 11 11-1 -/=1 Q(B,) log, +(1)+ E log, P(B,).
and the cross-entropy (- Q(B,) log2 π (i)) takes its minimum when matches Q. In practice, Q and find the bin it belongs to. However, choosing π rij) = ((B,) complicates the calculation of r'max in Equation (6). Fortunately, in ORC, we do not need to check the stopping criterion, so this complication does not pose an issue. We formalize this new ORC algorithm in Algorithm 4 in Appendix A.2.
to sample from this categorical distribution, we can simply draw
Algorithm 4 still leaves three questions unanswered: first, we need to determine the number of parti- tions J. As finer partition allows better alignment between Q and p", we pick J = Dial PII, the maximum value for which Proposition 3.2 provides a bound on the extra coding cost e. Note that this will require the receiver to know [ || PJJ. As we will demonstrate in Section 5, in practice, we can achieve this by either encoding the KL using negligible bits (e.g.. in neural compression with VAE) or enforcing the KL budget during optimization (c.g., in neural compression with INRs).
Second, as we partition the space using axis axis-aligned grids, we need to determine the number of bins assigned to each axis. To explain why this choice matters, we consider an example where Q and P share the same marginal distribution along a specific axis, and the space is partitioned solely by dividing this axis; in this case, we have P' = P, leading to no improvement in runtime. Fortunately, in most neural compression applications, the sender and receiver can also have access an estimation of the mutual information La along each axis d from the training set. If the mutual information is non-zero along one axis, on average, Q and P will not have the same marginal distribution along this axis. Based on this observation, we suggest partitioning the d-th axis into approximately 2 intervals where n1 = D || P] Ta/ >i.- Ta: see Appendix B.2 for further discussion, including the derivation, a toy example illustration, and ablation studies on this.
Third, we determine how many candidate samples we need to draw from P' to ensure the encoded sample has low bias. Recall that our proposed algorithm can be viewed as running ORC with Pa as the prior, we thus require a sample size > PPrul (Q | P') according to Corollary 4.1. When the total
number of partitions = PPcc. Pl, we find DkI[Q P'] = - - Q(B,) log, Q(B,). We do not have an analytical form for this value, but we can estimate it by samples from Q. In fact, we empirically find small number of samples to be sufficient for an accurate estimator.
7

---

Why choose the TV distance as the measure of approximation error in Corollary 4.1? Indeed, TV distance not the only possible metric and the choice should align with the intended application. We choose total variation as it fits well with the task in our experiments: the one-shot nature of data compression for human consumption. We will explain this in two parts:
1. Control of the TV distance in the latent space implies control in data space: naturally, we wish to assess reconstruction quality data space, but we use REC only to encode latent variables from which we reconstruct the data. However, since the total variation satisfies the data processing and triangle inequalities, if our generative model approximates the true data distribution with ó total variation error and we use e-approximate REC algorithm, then encoding the latents incurs no more than e + ô total variation error in the data space (Flamich and Wells, 2024).
2. TV distance captures a reasonable notion of realism. Imagine two distributions Q (e.g., the ground truth data distribution) and Q (e.g.. the data distribution learned by our compressor). Let Xo Q, Q and let B Bern 1/2) be a fair coin toss. Then, the probability that any observer can correctly decide which distribution ZB was sampled from, i.c., correctly predict the value of B given B,, is at most 1/2 (1 + DrvLQ, Q]) (Nielsen, 2013; Blau and Michaeli, 20.8). Thus, in the context of approximate REC, the TV distance bounds the accuracy with which any observer can tell the compressed and reconstructed data apart from the original.
5 Experiments
We now verify our proposed algorithm with three different experiments, including synthetic toy examples, lossless compression MNIST with VAF, and lossy compression on CIFAR-10 with INRs. We include details of the experiment setups in Appendix D.
Toy Experiments. We explore the effectiveness of our algorithm on 5D synthetic Gaussian examples. We run PFR with space partitioning (Algorithm 3) to encode exact samples and ORC with space partitioning (Algorithm 4) for approximate samples. We show the results in Figure 2 and Figure 3, and also include standard PFR and ORC for comparison. We can see that our space partitioning algorithm reduces the runtime by up to three orders of magnitude while maintaining codelength when encoding exact samples, and requires a much smaller sample size to achieve a certain bias (quantified by maximum mean discrepancy (MMD, Smola et al., 2007)) when encoding approximate samples.
Lossless Compression on MNIST with VAE. As a further proof of concept, we apply our methods to losslessly compress MNIST images (LeCun and Cortes, 1998). We train VAE following Flamich et al. (2024), employ REC (specifically, ORC with our proposed space partitioning) to encode the latent embeddings, and intrropy-encode the image. The KL divergence of entire latent embeddings averages over 90 bits. Unfortunately, even after employing our proposed space partitioning algorithm, the new KL divergence D || P'1 exceeds our manageable size. We hence randomly divide the latent dimensions into smaller blocks. Recall that, in our proposed approach, the sender and receiver need to share [DKL[ || PI] so that they can partition the space into the same = 2 Pxall I r]] bins. However, this value varies across different images. Therefore, we estimate the distribution of [ || P1| for each block from the training set, and entropy code it for each test image.
We evaluate the performance achieved by {2, 4} blocks and different sample sizes in Table 1, with the theoretically optimal codelength and the results by GPRS. REC algorithm that is faster in ID space but incurs coding overhead dimension-wise (Flamich, 2024). Notably, our algorithm's codelength only 2% worse than the theoretically optimal result and about 6% better than GPRS's. We also investigate the reasons for overhead. Compared to the BLBO, our method incurs overhead in three ways: (a) the cost to encode [D || PI]: (b) the overhead from encoding the latent embeddings by REC; and (c) the overhead when encoding the target image, which arises from the bias in encoding the latent embeddings, as ORC encodes only approximate samples. We can see our algorithm achieves extremely low bias while maintaining relatively small overhead caused by (a) and (b).
Lossy Compression on CIFAR-10 with INRs. We apply our methods to a more practical setting: compressing CIFAR- 10 images with RECOMBINER (He et al., 2023), an implicit neural representa- tion (INR) codec. The authors of RECOMBINER originally encoded INR weights using a block size of DRt. P] 16 bits. We empirically find that our proposed method can handle
block size of DRt. Q Pj 48 bits while maintaining [ P'] within manageable range,
approximately 12-14 bits. To further reduce the bias of the encoded sample, we opt use 2G6 samples
8

---

Steps
10
10
Space partition PRR
Codelength
20
[[X; 2]
Space partition PFR
runtime (#samples)
400
HND -0003 0-012
HND N00.0
MND 0-0006
Standard ORC
10
200
Space D4/ti1 ORC
10*
2.5
5.0
7.5
10.0
2
D2[QUIP]
[X:2]
(a) Runtime P.]
(b) Codelength T[x: Z].
Figure 3: Comparing standard ORC and ORC with our pro- posed space partitioning algo- rithm toy examples.
Figure Comparing standard PFR and PFR with our proposed space partitioning algorithm on toy examples. Solid lines and the shadow areas represent the mean and IQR.
Lossless compression performance on MNIST test set with different REC settings. We include the theoretical results and the results by GPRS (Flamich, 2024) for reference. We repeat each setting times and report the mean and std. $: R represents the average KL divergence between target Q and the search heuristic pl We estimate it by MC estimator and average across all test images. We empirically find z 14 when using 2 blocks and R R 7 when using 4 blocks. t: Given that is relatively small, we can employ more than |2 samples further reduce the bias. We hence report the results achieved by | samples, which remains manageable in both cases.
Table I:
REC SETUPS
BITRATE
DETAILS OF THE OVERHEAD (TO ELBO)
#BLOCKS
RUNTIME (#SAMPLES/ / BLOCK)
BITS PER PIXEL
COST TO ENCODE KL
OVERHEAD
IN REC
OVERHEAD FROM BIAS
1.6139 + 0.0058
0 0.0222 t 0,0002
0.2472 = 0.0066
100
1.4045 + 0.0004
0.0158 = O. 0.0008
4
0.0217 t 0.0001
12R
1.4042 + 0.0010
0.0233 t 0.0011
0.0144 I 0.0024
2
1.4012 + 0.0006
0.0293 t 0.000S
0.0054 + O. 0.00008
1.6051 + 0.0060
0
0.2463 = 0.0063
100
1.4089 + 0.0005
0.0105 t 0.0001
0.0397 = O. 0,00066
0.0130
0.0001
12R
1.3905 + 0.0005
0.0259 t 0.0010
0.0059
0.0018
[2
1.3898 + 0.0007
0.0286 + 0.0008
0.0024 + 0.0010
Theoricul Optimum
1.3618 + 0.0006
0
0.0136 + 0.0001
GPRS (Flamich, 2024)
1.4810 + 0.0015
0.1320 0.0012
0.0012 0.0001
w/o finetuning
finetuning
32.5
35.0
PSNR (dB)
30.0
32.5
27.5
0.84d8
30.0
0.36dB
0:32 hpp
27.5
0.21 bpp
1.0
1.5
2.5
3.0
1.0
1.5
2.5
3.0
3.5
Bitrate (bit per pixel)
Bitrate (bit per pixel)
Space partition ORC (block size=48 bits)
Slandard ORC (block size=16 bits)
..... Theorical RD
Figure 4: Rate-distortion curve of RECOMBINER by our proposed algorithm and standard ORC. We also provide the theoretical RD curve for an ideal REC algorithm (i.e., assuming we can encode an exact sample single block, whose codelength is calculated by Equation (1)). Notably, our method's performance is already very close to this theoretical result.
for each block. Besides, unlike in the VAE case, where the KL for each block varies across different test images, here, we follow He et al. (2023) to enforce the KL of all blocks to be close to 48 bits when training the INR for each test image. This eliminates the need to encode [DkLlQ PJ].
Additionally, He al. (2023) enhanced their results by fine-tuning Q for the not-yet- not-yet-compressel weights after encoding each block, which can achieve a more complicated posterior distribution Q in an auto-regressive manner. However, effectiveness of fine-tuning is closely tied to the number of blocks. As we have reduced the number of blocks in our approach, fine-tuning becomes less effective. Therefore, we present results both with and without fine-tuning in Figure 4. We also present the theoretical RD curve (without fine-tuning) to evaluate how close we are to the theoretical bound.

---

As we can see, compared with standard ORC using a block size of D P| proposed algorithm with the block size of DRI.Q P] 48 bits reduces the codelength by approximately 10% with fine-tuning and 15% without. This gain is due to three reasons: 1) when the KI. of each block is larger, the 6-cost, the algorithmic and constant overhead in Equation (8) becomes negligible; 2) the - logg J term in Equation (8) also reduces the algorithmic overhead in our method's codelength comparing with Equation (I); and 3) as the new KL divergence DKL[Q PI is around 12-14 bits and we choose sample size of 2 we eliminate most of the bias in our encoded samples. Moreover, the algorithm's codelength remains within 2% of the theoretical optimal result. As further comparison, where we can see that our proposed algorithm makes RECOMBINER more competitive.
16 bits, our
present the performance of other compression baselines in Figure 12,
6 Related Works
There are several efforts accelerate REC algorithms. Flamich al. (2022, 2024); Flamich (2024) leveraged the idea of partitioning in ID space, achieving an impressive runtime in the order of O (D=[Q O (DkilQ PJ). However, these fast approaches only work for ID distributions. Besides, Flamich and Theis (2023) proposed bits- quantization (BBQ), which encodes a sample with time complexity linear dimensionality. However, BBQ assumes and Q to be uniform distributions in two hypercubes with their edges aligned, which may not be practical in many applications. The algorithm most similar to ours hybrid coding (Theis and Yosri, 2022), which employs dithered quantization followed by sampling procedure, an approach that resembles special case of our proposed algorithm. However, hybrid coding relies on the assumption that the support of Q is contained within hypercube, restricting its practical applicability.
Conclusions and Limitations
In this work, we propose relative entropy coding (REC) scheme based on space partitioning, which significantly reduces the runtime in practical settings. We provide both theoretical analysis and experimental evidence supporting our method. Being among the few successful attempts to accelerate REC for practical settings, we firmly believe that contributions will broaden the application of REC methods and inspire further research.
However, our proposed algorithm still faces several limitations at the current stage. First, although our method and conclusion apply to general partitions, in practice, we are largely limited to handling axis-aligned grids. Second, in experiments, per dimension and shared between the sender and receiver, which restricts our algorithm's 's utility, for example, in non-factorized cases (Theis et al., 2022) or one-shot REC tasks (Havasi et al., 2019). potential avenue for future research involves employing a mixture of priors to form "partitions" without hard boundaries as discussed in Section 3.3. Additionally, by considering the prior convolution of two distributions, we may potentially create infinitely many partitions. However, managing the codelength in such cases may raise new challenges.
require the mutual information be factorized
8 Acknowledgments
We would like to thank Zongyu Guo and Sergio Salvo-Ordoñez for their proofreading and insightful feedback on the manuscript. JH was supported by the University of Cambridge Harding Distinguished Postgraduate Scholars Programme. JMHI. and JH acknowledge support from Turing AI Fellowship under grant EP/VO23756/1; GF acknowledges funding from DeepMind.
References
J. Ballé, V. Laparra, and E. P. Simoncelli. End-to-end optimized image compression. In 5th International Conference on Learning Representations, ICLR 2017, 2017.
Ballé, D. Minnen, Singh, S. J. Hwang, and N. Johnston. Variational image compression with a scale hyperprior. In International Conference Learning Representations, 2018.
10

---

J. Ballé, P. A. Chou, D. Minnen, S. Singh, N. Johnston, E. Agustsson, S. J. Hwang, and G. Toderici. Nonlinear transform coding, 2020.
Bellard. BPG image format. https://bellard.org////
2014. Accessed: 2023-09-27.
Y. Blau and Michaeli. The inneepttoondistorttinn tradeoff. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6228-6237, 2018.
S. Chatterjee and P. Diaconis. The sample size required in importance sampling. The Annals of Applied Probability, 28(2):1099-113 1135, 2018.
Z. Cheng, Sun, M. Takeuchi, and Katto. Learned image compression with discretized gaussian mixture likelihoods and attention modules. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7939-79999 -948,,948888 2020.
E. Dupont, H. Loya, M. Alizadeh, A. Goliñski, Y. W. Teh, and Doucet. compression across modalities, 2022.
Coin++: Neural
G. Flamich. Greedy poisson rejection sampling. Advances in Neural Information Processing Systems, 36, 2024.
G. Flamich and L. Theis. Adaptive greedy rejection sampling. In 2023 IEEE International Symposium on Information Theory (ISIT), pages 454-459. IEEE, 2023.
G. Flamich and I.. Wells. Some notes on the sample complexity of approximate channel simulation. In First 'Learn to Compress' Workshop@ @ ISIT 2024, 2024.
G. Flamich, M. Havasi, and J. M. Hernández-Lobato. Compressing images by encoding their latent representations with relative entropy coding. Advances in Neural Information Processing Systems, 33:16131-16141, 2020.
G. Flamich, S. Markou, and M. Hernández-Lobato. Fast relative entropy coding with a coding. In International Conference on Machine Learning, pages 6548-6577. PMLR, 2022.
G. Flamich, S. Markou, and J. M. Hernández-Lobato. Faster relative entropy coding with greedy rejection coding. Advances in Neural Information Processing Systems, 36, 2024.
7. Guo, G. Flamich, J. He, 7. Chen, and J. M. Hernández-Lobato. Compression with bayesian implicit neural representations. Advances in Neural Information Processing Systems, 36, 2024.
M. Havasi, R. Peharz, and J. M. Hernández-Lobato. Minimal random code learning: Getting bits back from compressed model parameters. In International Conference Learning Representations, 2019.
He, G. Flamich, Z. Guo, and J. M. Heránndez-Lobato. Recombiner: Robust and enhanced compression with bayesian implicit neural representations. In The Twelfth International Conference on Learning Representations, 2023.
JVET. VVC offical test model. https:// //jeet. h/tt/hhittthtt....eee.e hhi fraunhofer de, 2020. Accessed: 2024-03- 05.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization, 2017.
D. P. Kingma and M. Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6111 2013.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny (200),
Y. LeCun and C. Cortes. The mnist database handwritten digits. 1998. URL http://yann. lecun. com/ hommexxb/mmiisee
C. T. Li and A. El Gamal. Strong functional representation lemma and applications to coding theorems. IEEE Transactions on Information Theory, 64611)6666776778 2018
C. J. Maddison. poisson process model for monte carlo. Perturbation, Optimization, and Statistics, pages 193-232, 2016.

---

C. J. Maddison, D. Tarlow, and T. Minka. A sampling. Advances in neural information processing systems, 27, 2014.
Mentzer, E. Agustsson, M. Tschannen, R. Timofte, and L. Van Gool. Practical full resolution learned lossless image compression. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2019.
Nielsen. Hypothesis testing, information divergence and computational geometry. In International Conference Geometric Science Information, pages 241-248. Springer, 2013.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
J. R. Schwarz, J. Tack, Y. W. Teh, J. Lee, and J. Shin. Modality-agnostic variational compression of implicit neural representations. In Proceedings of the 40th International Conference on Machine Learning, pages 30342-30364, 2023.
A. Smola, A. Gretton, L. Song, and B. Schölkopf. A hilbert space embedding for distributions. In International conference on algorithmic learning theory, pages 13-31. Springer, 2007.
L. Theis and E. Agustsson. On the advantages of stochastic encoders, 2021.
L. Theis and N. Yosri. Algorithms for the communication of samples. In International Conference on Machine Learning, pages 21308-21111 21328. PMLR, 2022.
Theis, T. Salimans, arXiv preprint arXiv:2206.08889 2022.
Hoffman, and F. Mentzer. Lossy compression with gaussian diffusion.
J. Townsend, T. Bird, and D. Barber. Practical lossless compression with latent variables using bits back coding. In 7th International Conference on Learning Representations, ICLR 2019, volume International Conference on Learning Representations (ICLR), 2019.
12

---

A Algorithms
A.1 Practical PER Algorithm with Space Partitioning
Algorithm Practical encoding procedure PFR with dimension wise
wise space partitioning
Input: Fulty-factorized target Q Q!1) Q x Q!?) shared and fully- fally-fcttorized coding distribution P p[1] x P[2] ... x PLD|, and shared random states Sj for each partition j. Output: Bin index j" local sample index n²
# initialize:
T - 00, to - 0, j - 0, n O.
Partition d-th dimension into J[4] intervals B|dd _ 2; < for j 1.2 J. T max 1.
Bld jod s.t., J - IT J(4]
t Note that we omit the normalization factor and J
ppe-procest for fast sampling along each dimension: for d = 1,2,... D do
for 1.2, JLul do
[d]
g (s) p1))
sup (d
end for
[4] [d]
Z Σ
1=
Define n [d]
Categorical (11"1/2, /2, " [2)
end for
# run PFR: for 1,
# sample time:
Sample Aln Exp(1).
I, < n- Al,
sample bin by sampling intervals per dimension:
In - 0.
In keeps track of the bin index.
Ln < 1.
t> En keeps track of the likelihood of the bin being sampled.
for d = 1,2. ....D.r do
to ~ r/d].
[d]
t, d = 0 then
la ak
Jn k.
else
Jn k + In lld-1]
end if
end for
# simulate sample with PRNG:
j. nj +
2, + PRNG P By, ,
~ by inverse transform sampling when both of the partitioning and P are axis-aligned.
# update r*: Tn ln tt (lm.p(z,)// p(z,n//(Zzn)
Note that we omit the normalization factor and
if Tn & 7" then
7* Jn Jny n jm-
end if
check stopping criterion:
if /T' > ,* then
break
end if
end for
13

---

A.2 Practical ORC Algorithm with Space Partitioning
Algorithm 4 Practical encoding procedure of ORC with Space Partitioning
Input:
Target Q, shared coding distribution P, number of candidate samples N, and shared random states Sj for each partition j.
Output: Bin index j", local sample index
initialize:
0, 0 0. Partition space in J "bins".
20,40 0, JM
T2 + for j = 1,2, ... J.
# run ORC:
for n = 1,2, .. .N do
# sample time:
Sample An Exp(1).
l 1- N-R+I Amn
b Note the difference from the PFR algorithm.
# simulate sample with PRNG:
z Q, and find Jn s.t. ZE Bj..
22 j. jn + +1.
Zn - PRNG
Sj., 22)))
by inverse transform sampling when both of the partitioning and P are axis-aligned.
# update 7*:
Tn J ((BBB.)) tn (h.pp(zn)) p(zz)//(zn).
if 7 then
T J Jay n j....
end if
end for
A.3 Decoding Algorithm
Algorithm 5 Dncoding procedure of PFR/ORC with Space Partitioning
Input: Bin index j*, local sample index Æ* and shared random states S, for each partition j.
Output: Sample z.
Partition space in J "bins". PRNG(P B, Sy+, #**.
B Additional Results and Discussions
B.1
Elucidating Non-overlapping Bins
As we discussed in the main text, the partitioning does not need to form non-overlapping grids. In fact, there are only two constraints for the partitions: (1) the density the distributions for all "bins", without being weighted by should sum to p(z) at each 2, and (2) integrating the density of in each "bin" should yield the same constant 1/J. As long as we follow these two constraints,
create any kind of partition, we explain this by viewing Equation (7) as a mixture model. In this section, we provide another explanation from an intuitive point of view.
matter whether they overlap not. In Section 3.3,
First, we assume the reader agrees that we can always create non-overlapping bins non-overlapped grids. Then, to create overlapping bins, we can add an auxiliary axis Zaux to the original space Q, forming an augmented space as Janx S2 We define the prior and target the auxiliary axis as P.mx and Qax.. and define the prior and target in the augmented space as Pang Pax x P. Q Qaix x Q. This augmentation will not influence the codelength since we can always ensure the augmented Pang and Qang to have identical marginal densities along the auxiliary axis. We illustrate this augmented
14

---

space in Figure 5a. We can view partitions in the original space non-overlapping ones in an augmented space, as illustrated Figures 5b 5d.
In this augmented space, the partitionn show follow these two constraints: (1) without considering и, if we marginalize bins to have the same probability under the prior Pag.. The second constraint comes from the first step in Section 3.1, which is necessary for the proof of the codelength later in Equation (38). If
the auxiliary axis, Pang should revert the original P: (2) require all
only consider the original space, these two constraints correspond to the ones aforementioned at the beginning of this section.
Ω
Paux qaux
Paug
qaug
Xaux
augmented space = Q Xaux
(a) The augmented space.
Palt tait
Paac daxt
Pass
MAKE
Pasz
Baaz
daep
Thas
augmented space Paor
sugmented space Fax
sugmenticl space
(b) Non-overlapping bins.
(c) Fully-overlapping bins.
(d) General partitions.
Figure 5: Elucidating the generality space partitioning. Ω represents the original space. We dashed lines to represent the boundaries of the partitions. (a) We can add auxiliary axis Taux the original space, forming an augmented space. We define the prior and target in the auxiliary axis as Paux and Qaux. and define the prior and target in the augmented space as Paug Paux P. Qang Qaux Q. We also require Paux and Qaux to
same, so that D [mmg] the same as the original KI. DKI[Q [ PJ. Dividing the augmented space into non-overlapping bins will lead to non-overlapping bins or overlapping bins in the original space. For example, as shown (b), dividing the augmented space into non-overlapping bins whose boundaries are parallel to the auxiliary axis results in the standard non-overlapping bins in the original space Q. As shown in (c), dividing the augmented space into non-overlapping bins whose boundaries are orthogonal to the auxiliary axis results in fully overlapping bins in the original space Q. Also, as in (d), the augmented space can be divided in arbitrary manner, leading generally overlapping bins in the original space Ω.
B.2 Choosing the Number of Intervals Assigned to Each Axis
First, we elaborate on why this question matters. We take the following example: Q and P are 2D Gaussians, and they have the same marginal distribution along the first dimension, denoted 21, but have different marginal distributions along the second dimension, denoted as 12.
Now, we partition the space to the axes. If we partition the space by solely dividing IT, we will find that the prior and the posterior have the same probability for each bin, i... P(B,) Q(B,), Vj. In this case, choosing
d2 by axis-aligned grids, i.e., the boundaries of grids are parallel
15

---

{(1) QBB,) as discussed in Section 4.2, we can write the density of P (Equation (7)) as
T (i)p(z)
p'(z) - Σ lIZE B₁}
(16)
P(B,)
E/= B)) Q())((z)
(17)
P(B,)
P(BrTp(z)
Ej-1 B,)
(18)
P(B2)
Liz Bz}p(z) p(z)
(19)
(20)
which means that the adjusted search heuristic P' is the same as the original prior P, and thus we will have no improvements in the runtime. Figure 6a visualize this example.
On the other hand, we partition the space by dividing T2, as shown in Figure 6b, the search heuristic Ie will align with Q better than P. and hence we can reduce the runtime. In practice, it is not always feasible to partition in this way. Instead, we may partition the space by dividing both æ and z2, as shown in Figure 6c. In this case, we will still have reduced runtime. This is because
DKL[Q PT] = PKL[Q 11 PJ
Σ Q(R,) log2 x (s) +
Σ j-1
Q(B)) log, P(B))
(21)
DKL P]
Q(B,) log2 Q(1) Σ Q(B,) logg P(B,)
(22)
5=1
We recognize the term (Σ/_1 Q(B,) log, Q() - Σ Q(B,) log, P(B,) as a KL diver- gence and hence will be non-negative. Whene there exists By, s.t. Q(B,) * P(By), the KL term (2)-11 Q(B,) log, Q(i) - Σ Q(B,) log, P(B)) will always be positive to ensure DKL[Q || P'] & DKL[Q || P] and hence guarantee a reduction the runtime.
(b)
(c)
Figure 6: An example to explain why the number of intervals assigned to each axis matters when we partition the space with axis-aliged grids. We use dashed lines to represent the boundaries the partitions. In this example, Q and P have the same marginal along 21- In (a), we partition the space by solely dividing x1. This will make the search heuristic p' equal to P. leading to no improvements in the runtime. In (b), we partition the space by dividing x2. This will make the search heuristic Pd align with Q better than P (i.c., [KL[Q]IPT] < <DR[[Q) p)). reducing the runtime. In (c), we partition the space by dividing both 22 and Z1. This will still reduce the runtime, but is not efficient as (b). Please note that while the plot looks similar to Figure 5, they represent different concepts.
From this example, we conclude that even when the total number of partitions is fixed, different partition strategies will lead to different runtime. What we want to avoid is the case in Figure 6a. Fortunately, in most neural compression applications, we have access to an estimation of the mutual information la along each axis d from the training set. For the reader who is not familiar with the term, we can view la as the average KL divergence along d-th axis. If the mutual information is non-zero along one axis, on average, Q and P will not have the same marginal distribution along this axis. Therefore, we can partition the d-th axis into approximately (Ta Diu(Q || P1/ T.) intervals avoid the worst case in Figure 6a.
16

---

B.2.1 Examples and Ablations on Choosing the Number of Intervals Assigned to Each Axis
Qualitative visualization. We first visualize the approximation error of using ORC with different partitioning strategies on a toy problem. Specifically, we create a 5D Gaussian target, and we set dimension I to have O mutual information (we call it collapsee/uninforratiee dimension). We compare three partition strategies: only partitioning the collapsed dimension, randomly assigning intervals to dimensions, and assigning intervals according mutual information (our proposed strategy). We also include standard ORC for reference. We run the four settings with the same number of samples (20) and repeat each setting 5000 times. We show the histogram of 5000 encoded results in Figure 7. As we can see, assigning intervals according to mutual information works best, whereas partitioning only the collapsed dimension yields almost the same results standard ORC. This verifies our discussion above.
StandardOOCC
Only partition collapsed dim
Ranceniy assign intervals per
Assign intervals according to (ours)
derslty
2
2
0
Emplrical density of the encoded samples (average acorss 5000 runs)
target density
Figure 7: Visualizing approximation
of standard ORC and proposed methods with different
partitioning strategies when executed with the same number of samples (20). We use the same setup the toy experiments in the main text (details in Appendix D.1), but here set dimension I to have zero mutual information (i.e., collapsed dimension).
Ablation study. We now provide ablation studies showing how partition strategies will influence performance. We run the ablation on the Gaussian toy example and the CIFAR-10 compression experiments. As we can see, our proposed partition strategy is always better than randomly assigning intervals per dim. For CIFAR-10, we also compare the results by first removing uninformative dimensions (mutual information 0), and then randomly assigning intervals to other dimensions. We find this is only slightly worse than our proposed partition strategy. This not only further verifies our discussion above Appendix B.2, but also indicates that our algorithm not very sensitive to how we construct the intervals long avoid partitioning along uninformative dimensions.
10F
350
Space Portitioning PFR lassign intervals according MI, surst Partiiinning trandomly intervais dim)
Space Parkkicning (FIi (assig intervals eccunding to Mi. curs) Space Parthionin PFR (randomly assign intervais perdim) Stae dand
10
300
2.5
10'
2.00
MXI 0.012
100
10'
10.
3.0
1.5
1.
0_10[IP]
D210
(a) PFR's runtime w.r. [=o[Q[IP]
(b) ORC's runtime for a certain bias w.r.t DRI. Dx.[QQ1] P]
Figure 8: Runtime (number of steps/simulated samples) of different partition strategies on toy Gaussian examples. We compare two partition strategies: randomly assigning intervals to dimensions and assigning intervals according to mutual information. We also include standard PFR and ORC for reference.
17

---

36
Splace pertition ORC (assign intervals according MI, ours)
Soace pertition ORC (randorn interval dim)
Spacee partition ORC (remove collapsed dim, then random assign interval per dim)
34
Standard ORC
Uheorical
PSNR (dB)
32
30
28
1.0
1.5
2,0
2.5
3.0
3.5
Bitrate (bit pixel)
Figure 9: Rate-distortion of RECOMBINER (on 100 CIFAR-10 test images) by our space- pareepparitioonin algorithm using different partition strategies: randomly assigning intervals dimensions; first removing axis with MI R 0 and then randomly assigning intervals; assigning intervals according to MI (our proposed strategy).
include standard ORC and theoretical RD for reference. Our proposed partition strategy is better than randomly assigning intervals per axis. Surprisingly, the results achieved by first removing uninformative dimensions (MI s 0) and then randomly assigning intervals to other dimensions are only slightly worse than our proposed partition strategy. This indicates that our algorithm is not very sensitive to how we construct the intervals, as long as we avoid partitioning along uninformative dimensions.
C Proofs and Derivations
C.1 Proof of Theorem 3.1
Restate Theorem 3.1 for easy reference:
Theorem 3.1. Let a pair of correlated random variables X, Z ~ Px.z be given. Assume we perform relative entropy coding using Algoritium 2 and let j* denote the bin index and ń the local sample index returned by the algorithm. Then, the entropy of the two-part code is bounded by:
& & I[x: Z Ex[c] + loooo (7[X;
A*
log, J + Ex[c + 11 4
(23)
((z)
where
Bx~Qzix
max 0, J logg
(24)
p(z)
Proof. The proof will be organized as follows: first, we will prove an upper bound of E X = x] for the one-shot case, i.e.. the expectation of π* given realization of the data X. Then, will take the expectation over X to achieve an upper bound for the average case E ă *1 Finally, we will consider encoding π using Zipf distribution to calculate the upper bound given in Theorem 3.1.
Derive E[ x]. Assume that the posterior distribution Z x Q. We run PFR with space partitioning according to Algorithm 2 using a coding distribution P to encode a sample from Q. As we discussed in the main text, we can view our proposed algorithm as running standard PFR with an adjusted prior p' whose density is defined
- 2'(2)= = Σ 1izE B₁) P(B,)
T()((z)
(25)
Therefore, follow similar arguments Li and El Gamal (2018) prove the codelength.
We first assume the minimal 7 is 7 the corresponding sample x* and the global sample index is n* WLG, let's assume the sample falls in bin j* and its local sample index in this bin is n
18

---

According to Li and El Gamal (2018), we have
7* Exp(1)
(26)
n 1 (oisson(A)
(27)
-* g(z") (***
(28)
Equation (28) is obtained from Appendix A in Li and El Gamal (2018) and replacing by p'.
Additionally, we have
á 1|n Binomial( - 1|n* - (())))))).
(29)
This is because: if we define "success" as a sample falling the bin j*, then the probability that sample in the bin je with global sample index nº has a local sample index n is equivalent to the probability that there are ni 1 success in the first n Bernoulli trials.
Therefore, according to the property of Poisson distribution, we have
Poisson (ooison(T(J*)) (T(**)))
(30)
Therefore, we have
logg2[1 x x] Eje
QQ1ss Bll
E,, Ean [log 1+ 1)]
(31)
Jensen's
E Qla Ele
E,e [loga Eg 2,7 (ri 1 1)]
(32)
eq. (30)
Ex Qla
B,* [log ④ (i*)A 1)]
(33)
eq. (28)
())" (xx*)
E, E, 218
E, loga
+1
(34)
(1(*))
Jensen's
((**)
Ejs Ex Q1B
log2
T))*)
(35)
p' p'(**)
IDJ+ 9( PP j+
eq. (2) (55 E, EzN 21B
loga
(36)
p(z*) TTl
q(2 q(2*)) P(BB))
Egz Q loga
(37)
p(2*)
9(z)
E loga
+
(38)
Jp(z)
The last line is because we require P(Bi) P(B2) ... P(By) = 1/J. We can see that
Equation (38) does not depend either the specific space partitioning strategy the choice of n. Based on Taylor expansion logz(1 + x)) at 0, +00, we have
log, (1+ Ø
< =)
I loga e,
(39)
log, (2) + a logz e,
otherwise
19

---

Therefore.
g(z)
E logglni*|X x] & 1 log2
+
(40)
Jp(z)
q(z)
g(2)
Ex-Q log2
1
1og2
(((z)
Jp(z)
((z)
g(z)
Jp(z)
Ex- Q log2
J
10g2
loga e
(41)
p(z)
Jp(z)
g(z)
q(z)
g(z)
)
E Q log2
1
log2 Jp(z)
((())
logz e. Ee a log2
((2)
J
9(2)
+ 1
q(2)
/
(Jp(z)
p(z)
Jp(z)
p(z))
g(()
(42)
((()
J
log2 ((2)
)
$ Ex- Q loga
1
+ logg e
(43)
pp(z)
Jp(z)
The last line is because
q(2)
g(z))
+ ((2)
JP(2)
] q(z)
E2 E log2
1
$
> /
(44)
p((z)
Jp(z)
p(z)
7(2)
(())
> J 1
< EEn log2
1
$
1 1
(45)
p(z)
p(z)
(46)
We can further simplify Equation (43) as follows:
loggl>i*|X x] & PKL[Q[[P] - llogg J + IBg 1 I 1108g log, p(z) logz
q(z)
logsd/ 1 [1082 J log2
q(z)
+ logg e
p (zz)
(47)
Dka[Q110 log2 + + logz e
(48)
where we denote
= Ex-Q
1 1 logg p(z) < loog //
(z))
logg
logg q(z)
(49)
p(z)
= Ez-q max logo J - log, (Z))
p(z) o0]
(50)
Derive [] Now, we consider the average case by taking the expectation over X. We have
F < Ex Pz] - log, J + Ex[e] + logg e
(51)
= / [ Zj
log2
Ex
log2
(52)
Derive entropy. Following the maximum entropy argument similar to Li and El Gamal (2018), we
have
H 1
&
[[; Z]
log, J + [x[c] + log, e logg(/[X;;
(T[x; Z] -og, J + Ex[c] + log, e + 1) + 1
(53)
[[;;
Z
log2 J + Ex[[e] + ( Z log, J + Ex[e] + 1) + 1+ loga + log, (log2 e 1)
(54)
[[; Z] log, J + Ex[e] + log, [[] Z] log, J Ex[e] 1) +
(55)
Finally, we need log, J bits to encode the index j* Therefore, the two-part code's codelength is upper-bounded by
H π2 *1 + logz J < Z| + Ex/d + log, (1[: Z] log2 J + Ex[d + 1) + 4
(56)
D
20

---

We also note that, if we do not take the expectation over X. we can also achieve similar bound for the one-shot channel simulation task targeting Q using coding distribution P:
||| i2 + logg J & Drr [] + + logg (xr (Dr P] logg J + + 1) + +
(57)
This ensures that the codelength is consistent for each realization of X and guarantees good encoding performance both on average and for each certain data observation in practice.
C.2 Proof of Proposition 3.2
To prove Proposition 3.2, we first prove the following Lemma:
Lemma C.1. The c-cost defined in Equation (9) monotonically increases w.r. J.
Proof. By setting r log2 q(xl//p(x) which is a new random variable, we rewrite the e-cost as
_ 1 1108s logg q(z)
& logg o (1083) J -log2 g(xr)
p(x) ]
(58)
p(z)
By [1 (r (J rr)
(59)
(T r)dr
(60)
where we also write J logg J. which is monotonically increasing function of J. Take derivative
w.r.t. J, we have
3 -. p(r) - r)dr p(J)(- 1 p(r)dr _ p(r)dr >
(61)
dJ
which finishes the proof.
Therefore, to prove Proposition 3.2, we only need to look at the worst case, where 12l P], We now prove for Uniform and Gaussian, respectively:
Uniform. For uniform distribution, WLG, assume P u(0, 1)", and Q (((A), where S
(0, 1)" In this case, we have P] = log, (A(A,, and ((x)
p(z) m(A): Vz E A, where is the
Lesbague measure. Therefore,
{ log2
((z)
10g2 u 1 log2 g(2) p(z) ]
E Ez-
< logz
(62)
p(z)
((2)
< DallQiepa (DallQ]1P] log, ((Z) p(z)
Ex
log
(63)
p(z)
(64)
the other hand, the indicator function ensures the integrand non-negative, and hence 6 > Therefore, O.
Factorized Gaussian. To prove for Gaussian, we first prove the following lemma:
Lemma C.2. When J = Pm[Q1IPP) the e-cost defined in Equation (9) is upper-bounded by
< 2
Var[r],
(65)
where r the RV defined by r = loga a(2)/p(x), 2 ~~6 Q.
Proof. First, we know
Dkl[Q|PP] log2 ((2) p(z)
Bx-Q
= 0
(66)
21

---

and we recognize
PKL1Q1P1] log2 ((2)
(67)
p(z)
((2) 1 1og2 p(z)
& DKL DKL PkulQ11P1 (DallQlee) - logg g(2)
p(z) 1
=
g(z) p(2) > Daleueii (DaulQ11P)- log2
p((z) }
((()
+ +Ez-
(68)
When J 2Pa.[Q1PP), we have
max 0. DKL. [Ql[[Q1PP] -log2 ((z)
p(z) |
= R
(69)
((2)
[xx[Q||PP -lgg ((2)
Ez~Q
1
log2
(70)
p(z)
p(z)
((2)
(1852 g(z)
Ex
1 log2
DxI[Q11P]
Dka[Q11P1)
(71)
p(z)
p(z)
Therefore, we have
g(2)
DDuIQ11i11 (Dxc[Q]/P] logg g(z)
]
2. = E
1 logg
1000
p(z)
p(z)
+ Ex-Q
[
{
log2 p(z)
((2)
DaalQ1111] (1082 p(z)
g(2)
Deu[Q[IP1]
(72)
((z)
Ex-Q
logg p(z)
D 1
(73)
Writing r log2 ((x)) x(xx//((x, we have
E, (r- [[r]]]
(74)
2
E, {v(r- - [[r])²]
(75)
2
Jensen's
1
$
v Er {(r -[r))
(76)
2
1
Varlr]
(77)
2
Lemma C.2 means that the e-cost is closely related to the variance of the log-density ratio between the target and the prior. We highlight that this conclusion holds generally and can be used to prove the bound of E for all distribution families. fammiisss But for now, we only focus on Gaussian, and leave more extensions to future exploration.
According to Lemma C.2, we want to bound e, we only need to bound Var[r]. To achieve this, we state the following Lemma:
Lemma C.3. For ID Gaussian Q and P, with density g NM og), p N(Hp; and og & op defining random variable r by r log, ((x))/((s) x Q, if Dxal [] is fixed to a constant, then Var [ monotonically increases w.r.f 0q.
Proof. WLG, let's assume p = NO, 1), Mg > 0, DKL [Q] P1 = 8. Denoting v = 0g. we have
My = 128 + log(o?) o + 1 28 log(u) e+
(78)
and thus
r=
((1 u)x² - -21r + 11 - v + 2nl + v²)
(79)
2v
1
(1 - -)(
pq }2 2
+ n2
+ unn + o²) x~ NM v)
(80)
20
1
22

---

Reparameterizating = =x 1 VU, we have
r 0(1
1 2v
r)1² o)11-))²²
+ - - 1 2p2 22 . ~ N M4
02
1)
(81)
1 1-2
V0
vo(1 - v)
The variance of r is given by
Varfr]
(1 01=
4
14
My
v) )
}²
+ 2
(82)
4
Vo
vo(1
( 1-u
(vv
2
= =(1- - 0)9k2z =11-0)22g
+ 2
(83)
1
Unn
- u)² /
(84)
2
1 (0² 1) + log(r) - - 1)
(85)
2
Taking derivative, we have dVVa[[r]
1
(o2 1)( 1
v22 + log(u) 4 1)
-1)
(86)
de
2
1
1
v28 + log(2) - + 1)
+
(v
+
0² 1)
(87)
2
1
> v225 + 2
-
v) +
(U
2 1)
(88)
2
5
1
3 2
2n8 +
U
(89)
2
2u
2
5
1
3
3
0²
(90)
2
2v
2
O(when
1)
(91)
In summary, Lemma C.2 tells us if want upper-hound 6, only need to upper-bound Var[r]: while Lemma C.3 further tells us we want to upper-bound Var[r]. we only need to look at the worst case, when and P share the same variance.
Following this, we can finally finish our prove:
WLG, assume the density of Q and P are given by
p(z) = I)
(92)
<22) .N |mi, (22(22) 1).. (...1))))..llllll.l.l. NNzalaa, 1)
(93)
where d is the dimensionality. In this case, we have
Dx1Q11P] log, Σ
1
(94)
2
1-1
and
log2 g(z) p(z)
n
log2
Mi22
N
logz
log
>
(95)
i=1
1=1
1=1
Therefore,
loga
V
VVVaa Var[r]
log
2
DKL [|] 0.849 Dxul
(96)
2
23

---

Finally, taking expectation over X, and by Jensen's 's Inequality, we have
Ex[e] 0.849Ex
V [RI[[Q]PP]
(97)
< 0.849 xx [ [Q]
(98)
0.849
XX Zj,
(99)
which finishes the proof for the Gaussian case Proposition 3.2.
C.3 Proof of Theorem 3.3
We first restate Theorem 3.3 for easy reference:
Theorem 3.3. Let a pair of correlated random variables X,Z Px,z be given. Assume we perform relative entropy coding using GPRS with space partitioning and j denote the bin index and n the local sample index returned by the algorithm, and e be as in Equation (9). Then,
H[j #1 = [[x z + Ex[q + log2( -
- log,
[x[c++))++
(100)
Proof. For those who are not familiar with GPRS, please note the notation used by Flamich (2024) slightly different from those defined in this paper. We define the sample we encode as z², while in GPRS paper, is denoted by X. We define the smallest (2024) name it the first arrival and denote by T. We define the global sample index of the encoded sample by n², while Flamich (2024) denote it by N. In the following proof, since we will mainly modify the proof of Flamich (2024), we follow their notations unless otherwise stated.
r*, while in GPRS paper, Flamich
We still follow the structure similar to the proof in Appendix C.I. Specifically, we first derive the upper bound of log, n * conditional on certain X x. Then, take expectation over X. Finally, we derive the entropy by the same maximum entropy argument.
Derive Eloog2 n2 X x]. Our proof starts from Equation (59) on Page 17 of the GPRS paper. It says that N follows Poisson distribution given 7 I, with mean:
(a())
(101)
where jú defined by Flamich (2024) as the average number points "under the graph" up to time (See Appendix A on Page 13 of the GPRS paper for a detailed definition).
WLG, assume the encoded sample X is in the -hhth bin. Then, according to the property of Poisson distribution, n² * is also Poisson-distributee, with mean (jj") ju(t)), where n is the local sample index the -*th bin.
Therefore, can modify Equation (133) on Page 21 of the GPRS paper as follows:
B[log, n "IT = t, X = I. By,, X x|
< log, [1[ 1)|T = t, X = 2, E B,+] + 1)
(102)
log, π (j+) (t (itt) + 1]
(103)
< loggl (j (t++t++ 1]
(104)
By Equation (132) on Page 21 of the GPRS paper, we have
q(x)
(105)
P(T x
where p' is the density of our adjusted prior, defined in Equation (25).
Therefore,
*(j*) x(}*)((z)
(106)
[(x) >
P
(107)
I Tpz) 1
g(x)
(108)
J. JJ > 1
24

---

Hence, we have
(()) J J. > {) +1
(109)
s(x1/(3 p(z))
(110)
PT 3 t
x(>)/(-ppo p(x)) +1
(111)
Taking this back to Equation (104), we have
<(x)/(J p(x)) + 1
El n= $IT t, X 2, BJ,, X x] & log2
(112)
PIT > t
q(x)
log2
+ 1
+ (i()) logg e,
(113)
J p((()
where the last follows the same principle as Equation (137) on Page 21 of the GPRS paper. Now, by the law of iterated expectations, we find
E loga
X
x] = E, B, 100
Ee
E Ellog
I =, t,
2, B
(114)
oq (113)
g(z)
Fx B
n E2 logz
+ ii(1) 1og2
(115)
J J.p(z)
By-Q
log2
q(x)
+ $1
+ logg Be(ā(()]
(116)
J. p(x))
According to Equation (64) on Page 17 of the GPRS paper, E, [t]](()] 1. Therefore, we have
g(x)
|
Bllog n = xx=x E
loga
+
+ log2 e
(117)
J. p(x)
Surprisingly, this coincide with Equation (40) in the proof for PFR up constant. Therefore, following exactly the proof for PFR, we have
Ellog, $ X x & D log2 J + 2 logg E
(118)
where is defined the same way as the PFR case.
Derive [loog ń *J. Following exactly the proof for PFR, we have
Eloog x1 & I[: Z log, Ex[q 2- log, e
(119)
where c is defined in the same way as the PFR case.
Derive entropy. Finally, following the same maximum entropy argument, have
& X[; Z
log, J + Ex[c] + 2 log, e + log, ([[: Z] - loog J + Ex + 2 log, e 1) +
(120)
[[x; Z
log2 J + Ex|E| + log (1[x; ZJ log, J + Ex + 1) + ++1+2 log, + loga (2 logg 1)
(121)
[X; ZJ
log, J + Ex|E] + log, [[[ Z] log, Ex[e] 1) 6
(122)
Do not forget we need log, // bits to encode the index j* Therefore, the two-part code's codelength upper-bounded by
H| + log, < [X; Z + Ex[e] + (1 log, + Ex|e] + 1) + 6
(123)
which finishes the proof.
25

---

C.4 Proof of Corollary 4.1
Corollary 4.1. Given a target distribution Q and a prior distribution running Ordered random coding (ORC) to encode a sample from Q. Let Q be the distribution of encoded samples. If the number of candidates is N 2Dx((11 for some t 0, then
1/2
((z) p(z)
1 DxllQ1PP1+
DrvQ2 Q] & 4
2 2-1/4 + 2 Fa-Q
log
(124)
Conversely, suppose that N = 20 for some t 2 O, then
Div 12 Q 2 2/2 P= log
((z) p(z)
DRL[Q PJ
1 2
(125)
Proof. Theis and Yosri (2022) prove Equation (124). Therefore, we focus on Equation (125).
First, we note that, as proved by Theis and Yosri (2022), the sample returned by ORC has the same distribution as the sample returned by Minimal random coding Havasi al. (2019) and hence inherits all the conclusions of importance sampler by Chatterjee and Diaconis (2018).
Then, define set A as
((z) p(z)
A
z log2
< D 2
(126)
also, define
[1 ZE A otherwise
f(z)
(127)
00
Note, that
[x[s(z)] Pl- A] Q(A). Assume given a random state S, the set of all candidate samples (z1...., 2N3 is uniquely determined. We therefore denote
(128)
ΣV f(z;)
g(a))
IN,
p(z.)
(129)
L gize)
p(z,)
According to Chatterjee and Diaconis (2018), we have
Es[i[IN, 1}] = P[ 1] 2-1122
(130)
[s 1}] P[IN.S 11
(131)
Therefore, we have
Q(1)- Egls]
(132)
Es[IN.s]
(133)
P[IN,S = 1|Es[ IN. P[TN. * I|Es[TN,s|IN.S * 1]
(134)
P[IN,S 1JEs[IN,s|INS, INN 1]
(135)
P[ = 1]
(136)
e - 2 21/22
(137)
on the other hand, have
Q(A) PP PanoQEE A] -Pa-Q
log q(z)
p(z) & Dx[[Q|1P] - 2
t
(138)
Therefore, we have
D (Â(A)) Q(A')
(139)
A
(Q(A)) Q(41)
(140)
> Q(A) -((4)
(141)
[log g(2) p(z)
& D ())
> 2 1/2 Pa-Q
(142)
26

---

D Experiment Details
D.1 Synthetic Gaussian Toy Examples
D.1.1 Generation of the toy examples
We explore the effectiveness of our proposed algorithm on 5D synthetic Gaussian toy examples. Specifically, assume p(x) (x diag( 2)) and q(zlx) [z(z),, diag(p")). The density of prior P is given by p(z) = (O, diag(o "o" + p²)). Therefore, for a certain realization of or P. we have the following REC task: transmitting sample following Q whose density is g(z)x) N(z|x, diag(p")) with the help of the prior P with density p(z) = N (0, diag(o" +p))). To generate
multiple toy examples, we randomly draw o. p U(0, 1) The dimension-wise mutual information [[X, Z) is
2 log2 ((o* ((=*+ +))))
D.1.2 Space partitioning details
In this toy example, we naively assume the receiver knows both the dimension wise mutual informa- tion and the entire KL divergence between Q and / (but dimension -wise KL is only available to the sender). In practice we can achieve this by either encoding the KL divergence using negligible bits (for VAE in Section 5) enforcing the KL. budget during optimization (for INRs in Section 5).
Pga P)
Then we partition the d-th axis into approximately 2 log2 (10] + r3)/2)) is the mutual information along d-th dimension. To achieve this, we adopt the following steps:
20 -0-1
intervals, where Ia
Initialize: we first initialize the number of intervals per dimension to i.e., JI4 1, 1,2, DD; and we also initialize a vector of mutual information [41, 12, La].
we iteratively increase the number of intervals by two in the dimension that currently has the highest mutual information. Specifically, we find d <- arg max (1, I2, Ta}, and set JId*1
Iterate:
1
Update and Repeat: after increasing J[a*), we decrement both the mutual information of that dimension and the total KL divergence by 1. We repeat this process until KL is exhausted.
D.1.3 Generation of the plots
After this, run PFR with space partitioning (Algorithm 3) to encode exact samples and ORC with space partitioning (Algorithm 4) for approximate samples. We show the results in Figure and Figure 3, and also include standard PFR and ORC for comparison. To plot Figure 2, sample 200 different o P pairs, and repeat the encoding procedure 50 times with different seeds for each realization of ar p. We calculate the negative log-likelihood of the 50 encoded indices using Zipf distribution P(N optimize the log- likeliieldoood of the 50 indices with scipy. optimize. minimize.. Finally, we average and find the IQR across these 50 repeats, and smooth the curves the end for better visualization. In real-world applications, one may raise the concern that we need to transmit this Ç, which may lead to another overhead in the codelength. However,
proxy of the codelength. To find the optimal value of Ç.
will see later in our VAE and INR cases, estimate the value of ( from the training set (or very small subset of the training set) and share between the sender and receiver.
To plot Figure 3, we first sample 200 different o P pairs. For each realization of or p. we run ORC with a range of sample sizes: 211.2.3.11.6677889..
and repeat the encoding procedure 500 times with different seeds for each sample size. Then we estimate maximum mean discrepancy (MMD, Smola et al., 2007) between the 500 encoded samples and real target samples with RBF kernel". Since different target Q can lead to different MMD scales, we normalize the Q to standard isotropic Gaussian (and also scale and shift the encoded samples correspondingly) before calculating MMD. Note, that the absolute value MMD means little here. What we should care about is the relative comparison. After this process, we achieve a scatter plot. Finally, for clear visualization, we fit
'We use the codes at https: / /ttp//gttttt.t//////////.t com/ wtw.tt/wbooooonnnnnnnnnggggggeee distance/ mmmd numpy numpy_sklesaae sww.arn.nnn...... py (MIT License)
27

---

Gaussian Process regressor with scikit-lese package (Pedregosa et al., 2011) to estimate the mean and IQR.
D.2
Lossless Compression on MNIST with VAE
D.2.1 VAE architecture and training details
We follow (Flamich et al., 2024; Townsend et al., 2019) for the VAE architecture. Specifically, both encoder and decoder are 2-layer MLP. We set the hidden size to 400 and the latent size to 100, with ReLU activation function. We use fully factorized Gaussian as the latent distribution and Beta-Binomial as the likelihood distribution. The encoder maps the input flattened image two 100-D vectors, corresponding to the mean and std in Gaussian distribution. We use softplus to ensure the standard deviation vector positive. The decoder maps the 100-D latent vector back to 784-D vectors, corresponding to two parameters in Beta-Binomin distribution. We also use softplus to positivity. We Adam (Kingma and Ba, 2017) with learning rate of 0.001 the optimizer, to train the VAE with batch size of 1,000 for 1,000 epochs.
D.2.2 Space partitioning details
We estimate the mutual information La along each dimension d the latent space (i.e., averaging over the KI. divergence across the entire training set), and then we partition the d-th axis into approximately
1Pg P|] Far intervals.
We use the same strategy as Appendix D.1.2, but also found simply
19 27-1 '
PJ]
rounding
to the nearest integer works very well. Here, we apply the floor function to the KL divergence since need transmit this value to the receiver.
To ensure our space partitioning strategy can reduce the runtime, need mutual information match well with the KI. divergence for each test image along all dimensions. We empirically check this in Figure 10. As we can see, the test image KI. divergence concentrated around mutual information. Also, if the mutual information is zero for some dimension, the test KI. divergence will also be zero.
14
divergences
0.06
Mutual Information
0.05
8
Density
0.04
0.03
4-
0.02
60
100
100
Dimension
divergence (floreed)
Figure 10: Dimension-wise mutual informa- tion and KL divergence for each test image along all dimensions. We can see the KL divergences concentrate around mutual infor- mation. And if the mutual information is zero for some dimension, the KL divergence will also be zero. This ensures our space par- titioning strategy can reduce the runtime.
The distribution of KL for each group, estimated from 60,000 training im- ages. Here, we take the case where we split the latent embeddings into blocks an ex- ample. Different colors represent different blocks. We note that the difference between these 2 blocks is solely due to randomness in the splitting.
Figure 11:
D.2.3 Encoding details
We losslessly encode test image with code with four components: (1) [Dr..Q P]] for each block; (2) the local sample index for each block; (3) the bin index for each block and (4) the image conditional on the encoded latent embedding. We discuss these components in the following:
28

---

For the first component, we estimate the distribution of | || PIl for each block from the training set, and use the negative log- likelihood as proxy for the codelength. To provide an intuition on the distribution of DxI.Q PIJ. we take the 2-block case as an example and visualize the histogram of [Dr.[ (2 Pl] for each block in Figure 11.
For the second component, we estimate the codelength by the negative log-likelihood of Zipf distribution P P(N)
We find the optimal ( value for each block from only 50 training images and find it generalizes very well to all test images. Note, that we find different Ç for each block. This is because, as we can see from Figure 11, the random splitting will not ensure the two blocks to have the same KI. divergence distribution and hence may lead to different optimal Ç.
The codelength for the bin index is simply [ |I PIJ for each block.
For the last component, we estimate the codelength by the negative log-likelihood of Reta-Binomal distribution with the parameters predicted by the decoder.
One concern is that using negative log-likelihood as a proxy may underestimate the codelength. However, since we use the same proxy across all settings, this doesn't 't raise an issue in comparison.
D.3 Lossy Compression CIFAR-10 with INRs
Following the methodology described by Hc et al. (2023), we model the latent weights and latent positional encodings (collectively denoted by h) with a fully factorized Gaussian distribution Qh- We also learn the prior ph using 15,000 images from the CIFAR-10 training set. During the testing and encoding stage, He al. (2023) suggested using 16-bit blocks. Specifically, He et al. (2023) split h into K blocks, h [hl ... .Iii], and trained @n for each test image x by optimizing the following 3-ELBO:
K
C =
Σ Bx DKL [9h1 [Ppta]] + Ee, Distortion(&,,.. x)]
(143)
&
where Xn, is the reconstructed image with parameter h, and 3a-s are adjusted dynamically to ensure DRi. [_][]][P]]]]]] * 16. In our experiments, we find that our proposed methods can safely accommodate larger block sizes of 48 bits. To ensure a fair comparison, we follow He et al. (2023)'s setting on CIFAR-10 exactly, except for the block sizes and the REC al- gorithm. Specifically, we modify the block sizes and the REC algorithm in codes at https: //github. www. homm/cambrddge mlwmmmlg///ae RRE/RRCCMMBBNE (MIT License), and keep other settings unchanged.
As for the theoretical RD curve in Figure 4, we do not split h into blocks, and directly optimize
L= DxL [9 [Pb]] + Egg [Distortion(E,, x)].
(144)
The 8 is set to the 8 obtained during training and kept the same for all test samples since we do not need to ensure any bit budget for theoretically ideal REC codec. Then we directly draw a sample from Ih to calculate PSNR, since we assume theoretically ideal REC codec can encode a sample from the target exactly. As for the rate, we average Dxi. [ph [1pb] across all test images to estimate
7[, X], and calculate the codelength by 7h,, X] + log2( (7[h, X + 1) 4.
D.3.1 Space partitioning details
To apply our proposed REC algorithm, we also need estimate the mutual information La along each dimension d in h. To achieve this, we randomly select 1 1,000 training images, and learn their posterior distributions Qh. by Equation (143). We also adjust 8& to ensure DKL. [p s 48 on these 1,000 training images. After this, we average their KL divergence per dimension as an estimation of the dimension-win mutual information. Having the estimation of La, we use the same strategy as Appendix D.1.2 to partition the space during test time.
D.3.2 Encoding details
During the encoding stage, we simply apply Algorithm 4 to encode each block. We use Zipf distribution (( to encode the local sample index, and then spend 48 bits to encode the bin index. We find the optimal Ç value from only 10 training images. Different from the VAE case, we find using the same ( value for all blocks works well. Also, to ensure a fair comparison with other codecs, we do not estimate the codelength by log- likelihood but encode the index using torchac package (Mentzer et al., 2019) and count the length of the obtained bitstream.
29

---

E Licenses
Datasets:
CIFAR-10 10 (Krizhevsky et al., 2009): MIT License
MNIST (LeCun and Cortes, 1998): BY-S 3.0 License
Codes and Packages:
Codes for RECOMBINER' (He et al., 2023): MIT License
Codes for calculating MMD": MIT License
torchac (Mentzer et al., 2019): GPL-3.0 license
numpy_sklearn.p http://hhhccclggggggc../////aa/a
hnttps://github..oml// com/fab- htt//fabbjjultoochhae
30

---

More Results
In Figure 12, we compare RECOMBINER (He et al., 2023) with our proposed algorithm with its original performance and also present the RD curves of other codecs for reference. Specifically, our baselines include classical codecs: (JVET, 2020), BPG (Bellard, 2014), JPEG2000; VAE-based codecs: Ballé al. (2018), Cheng al. (2020); and INR-based codecs: COIN+ (Dupont al., 2022), VC-INR (Schwarz et al., 2023) and COMBINER (Guo et al., 2024).
40
38
36
34
PSNR (dB)
32
30
28
26
24
0.0
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Bitrate (bit pixel)
BGP
COMBINER
JPEG2000
VC-INR
Cheng al. (2020)
VTM
Ballé al. (2018)
RECOMBINER (He et.al (2023), block size=16 bits)
COIN+
RECOMBINER (ours, block size=48 bits)
Figure 12:
Comparing RECOMBINER with our proposed space partitioning algorithm (w. fine- tuning) with other codecs on CIFAR-10, 10. We use solid lines to denote INR-based codecs, dotted lines to denote VAE-based codecs, and dashed lines to denote classical codecs.
31

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We propose a framework to accelerate REC algorithm. We clearly state our main contribution in the last part of the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discuss limitations in the last paragraph of the Section Conclusions and Limitations.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
32

---

Answer:
[Yes]
Justification:
We prove the theorems, corollaries, and propositions in Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We describe algorithm in details in Algorithm and Algorithm 4 and include how to reproduce the experiments in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
33

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: All data used is public. Our main contribution is the new REC algorithm and its algorithm to implement following the pseudo-codes.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/gun Saaps//CoSSSuuiiieeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: / wwtpppccpp///cccc.cccccccc..lttl caabbic/guiiesss SodeSuumisssiiieeooooo wwwiissisiiiccycoococomcmmsiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We briefly describe the experiments and discuss results Section 5. We include full experimental settings in Appendix D.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: For the toy example, we report IQRs. For lossless compression using VAE in Section 5, we include the standard deviation across multiple running. For lossy compression using INRs, we do not report the eтrоr bars. This is because all the baselines do not report this in the RD curve, and follow the convention. And since there 10,000 test images, the results should be relatively reliable already. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
34

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Our main contribution is the new REC algorithm, which can easily run on any CPU. We, in practice, run the scripts on many CPUs parallel get the error bar across multiple runs, but this is not needed.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https :ttp::///neuree http///nerrpp..pee cc cctpublic//eeeeeeccceecceeceeeee ctuih//ieeeciiiiieeleelleeeeee
Answer: [Yes]
Justification:
We do not believe our work has ethical concerns.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification:
We do believe our work has societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
35

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
We do not believe the paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: See Appendix E.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
36

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
37

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "qyQIYy2B7K", "reviewer": "Reviewer_tEuP", "summary": "The paper proposes a space partioning technique to speed up  relative entropy coding.\nIn entropy coding the sender first transforms X into a representation Z that they encode.\nThis particular step can done  by Poisson functional representation (PFR).\nUnfortunately, PFR’s random runtime can be a significant drawback.\n\nTo circumvent this issue,  the author propose a space partitioning scheme to reduce runtime in practical scenarios.\nThis can be seen (sic) as a search heuristic to a standard REC algorithm\n\nThe author then proceed to give a theoretical analysis of the method and support their improvement with numerical results.", "questions": "- it is unclear to the reviewer how the grid should be set.  \n-it is unclear to the reviewer how the choice of prior for the binning distribution influences the algorithm.\n-  the weakness section raises a question that I would like to see adressed:  how is the binning technique impacting the final result (besides codelength).\nI agree that the uniform distribution seems like a natural choice, but it would be good to discuss the choice of prior here\n\nI will happily increase my grade if those questions are properly adressed.", "limitations": "The authors recognize some clear limitations of their approach in the conclusion section.\nIn particular, the approach proposed by the authors is too limited and does not extend to all possible practical cases.\nThe reviewer agrees with those limitations, although still believes they should not be an obstacle for publication. as this work is a \"first step\" in this direction.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper adresses an important practical problem with many important application.\nThe algorithm and theoretical results are stated clearly.\nThe context and related work is clear to the reviewer (who is not an expert in the field).\nThe numerics show clearly the advantage/improvements  yielded by the technique.", "weaknesses": "Although the proposed technique is \"simple and efficient\", it lacks discussion whether the binning technique impacts the final result (besides codelength).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful for the reviewer's time and detailed review and are delighted that the reviewer found our paper clear and appreciated our technical and theoretical contributions. \nBelow, we respond to the reviewer’s questions. We are happy to discuss any further concerns the reviewer might have. \nShould we have addressed the reviewer’s concerns and questions, we kindly invite them to raise their score.\n\n\n1. > it is unclear to the reviewer how the grid should be set: \n\nWe discuss how we set the bins in our manuscript from line 241 to line 249; we will signpost this discussion better in the camera-ready version. \n\nIn short, in most neural compression applications, we can compute the mutual information per dimension $I_d$ from the training set. Specifically, for each training data $X$, we have access to its posterior $Q_{Z|X}$ during training, and we can calculate the KL divergence between $Q_{Z|X}$ and the prior $P_Z$ along each dimension. The dimension-wise MI $I_d$ is estimated by averaging the dimension-wise KL across all training data. \nKnowing the mutual information per dimension $I_d$, we partition the d-th axis into approximately $2^{n_d}$ intervals, where $n_d = D_{KL}[Q||P]\\cdot  I_d / \\sum_{d’} I_{d’}$. We discuss the motivation for this choice in Appendix B.2. We also provide the implementation details from line 621 to line 630 on Page 24.\n\n\n2. > how the binning technique impacts the final result (besides codelength):\n \nIn Appendix B.2, we discuss how different binning strategies influence the results. For a further illustration of the effect of the chosen grid on the efficiency of the algorithm, please see Figure 1 in the attached rebuttal PDF.\n\nEssentially, if we only partition the space by dividing the axes where the prior $P$ and the target $Q$ have the same marginal, we will not reduce the runtime. However, luckily, as we discussed above, in most neural compression applications, we can compute the mutual information per dimension $I_d$ on the training set. If $I_d> 0$, it tells us, on average, that the prior $P$ and the target $Q$ will not have the same marginal along the d-th axis. Therefore, we propose to partition the d-th axis into approximately $2^{n_d}$ intervals, where $n_d = D_{KL}[Q||P]\\cdot  I_d / \\sum_{d’} I_{d’}$.\n\nTo help the reviewer further understand this argument, we use a toy example for visualization in our attached rebuttal PDF. In Figure 1 in our rebuttal PDF, we create a toy 5D Gaussian target, and we set dimension 1 to have 0 mutual information (we call it a collapsed/uninformative dimension). We compare our proposed method with 3 different binning strategies: only partitioning the collapsed dimension; randomly assigning the number of intervals per dimension; and partitioning the d-th axis into approximately $2^{n_d}$ intervals, where $n_d = D_{KL}[Q||P] I_d / \\sum_{d’} I_{d’}$. We also include standard ORC for reference. \nWe run the 4 settings with the same number of samples (20) and repeat each setting 5000 times. The error can be seen from the histogram of 5000 encoded results.\nWe can see that partitioning according to mutual information yields the best results, whereas partitioning only the collapsed dimension yields almost the same results as standard ORC.\n\n\n3. > how the choice of prior for the binning distribution influences the algorithm: \n\nWe assume the reviewer is asking how the results will be influenced when each bin has different probabilities under the prior. We answer this question below, and we are happy to address any further questions if we have misunderstood the reviewer's question. \n\nSetting all bins to have the same probability mass under the prior is the basic requirement for our algorithm to adhere to the codelength outlined in Theorem 3.1 and Proposition 3.2. We note this in lines 104 and 414.  \n\nThis can be understood intuitively: under an ideal Bayesian treatment, the average Q_{Z|X} across all data X should equal the prior $P_Z$. Also, we note that the partitions are shared across all data X in the dataset. Therefore, ideally, we will expect the average probability (average is taken over all randomness and all X) that the encoded sample falls into any bin should be the same.   We can also see the reason from our proof of Theorem 3.1. Specifically, we replace all $P(B_j)$ in eq(37) by $1/J$ in eq(38), which simplifies the expression and is essential for the subsequent derivation.\n\n**In Summary:** our algorithm and theory require all bins to have the same probability under the prior.  Theorem 3.1 and Proposition 3.2 will hold for all binning strategies that satisfy this requirement.\nHowever, there are many (actually, infinitely many) binning strategies that satisfy this requirement. \nDifferent choices of binning strategies can have different runtimes or different biases given the same runtime budget. To this end, we propose to partition the d-th axis into approximately $2^{n_d}$ intervals, where $n_d = D_{KL}[Q||P] I_d / \\sum_{d’} I_{d’}$. We have discussed the motivation and implementation details in our manuscript and provided an additional visualization to aid understanding in our rebuttal PDF(Fig 1) in the global response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dBaw98FYPd", "reviewer": "Reviewer_we4Y", "summary": "**Global disclaimer:** I am very unfamiliar with the topic of the paper. I did my best to try and read the literature and understand as much as I could but my input may be very limited.\n\n**Summary:**\nThe paper focus on relative entropy coding (REC) algorithms and propose to circumvent a major pitfall which is the prohibitive encoding time. Indeed the commonly used PFR algorithm requires to sample points until finding a good enough alignment with the target distribution. Efficient algorithms only exist in dimension 1. The authors propose to refine the algorithm by partitioning the search space into bins that will better drive the sampling from the coding to the target distribution.\nThe author then theoretically prove that their approach by is founded (Theorem 3.1), and derive precise codelength bounds for the space partition algorithm. They also discuss a generic partitionning strategy.\nFinally, a benchmark highlight the benefits of the space partition approach for compression against the standard PFR algorithm on toy example and real datasets.", "questions": "- How the bounds from Theorem 3.1 do compare with the bound from [Li and El Gamal, 2018, Theorem 1] in the same setting, i.e. when $J=1$? More generally, could we recover a bound such as Proposition 3.2 but with a dependence in $J$.\n- The number of intervals for each axis is justified in Appendix B, but could the author give more details about how these interval are constructed?\n- The proposed approach to the construction of the bins follow depends on the chosen representation. Would it be possible to automatically find a transformation prior to the bining that would provide better results while keeping the same strategy?\n- Is there a way to update $\\pi$ along the algorithm, using e.g. the Gumbel trick and gradient based method?\n- It would be interesting to add an ablation study on the number of intervals per axis.\n- Table 1 shows some improvements in number of steps but it would be interesting to have the same thing in time. Could you elaborate about Figure 3, I do not understand what is meant by runtime here.", "limitations": "The approach is not fully generic and despite very good success on some examples, it could fail on other as clearly explained in Appendix B.\n\nTypos: the punctuation missing in the maths of the appendix\n\n**Proposed score:**\nMy rating is based on the fact that the paper is sound, the maths are correct but the scope of the idea is quite simple. I do believe that this work is well presented, interesting and worth publication. On the other hand I am not familiar with this field. As such, I propose a score of 5/10 (a weak accept) but I am very open to discussion with the authors and the other reviewers.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is very didactic, well written and is quite nice to read. The proposed approached is well structured and detailed (sections 3.1). The theory exposed in the paper is sound and the proof seem correct to me.\nThe benchmark is well made and honest.\nFinally the appendix is very helpful, I particularly appreciated appendix B that shed some light on the partition strategy.", "weaknesses": "The idea is finally quite elementary: dividing the space once for all into bins. The proofs are \"elementary\" (still technical) refinements from the classical PFR theory (starting point is often [Li and El Gamal, 2018] and [ Flamich, 2024]).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their dedicated time and constructive review, which we feel largely enhances the quality of our paper. While the reviewer may not be familiar with this field, we believe they understand most of our manuscript and method well. \n\nWe are delighted that the reviewer found our paper well-written and recognized its soundness. Below, we respond to the reviewer's concerns, and we are happy to discuss any further questions the reviewer might have. \nShould the reviewer find our answers satisfactory, we kindly invite them to consider raising their score.\n\n**Weakness: the idea and proofs are elementary**: While we agree that the main idea behind our method is simple, we respectfully disagree that it is a weakness on three grounds. (a) ideas that are simple and work well in practice have the largest potential to be impactful in the field as they are easy to understand and replicate. This is the case for our method: our ideas improved performance by many orders of magnitude in terms of the largest KL values that many future REC algorithms could consider.  (b) the theory justifying this idea required new insight; mainly around deriving the overhead term $\\epsilon$ that previous works did not deal with or consider. (c) the general insight that we can use the dimensionwise mutual information to devise schemes to improve compression speed is a significant contribution to the field, and we believe that any future scheme that does not use this additional information will be either limited in speed (as all previous schemes are) or codelength. \n\n**Regarding Questions:**\n\n1) > How Theorem 3.1 compare with the bound from [Li and El Gamal, 2018, Theorem 1] when $J=1$\n\nwhen $J=1$, our algorithm is equivalent to PFR, and therefore, we end up with the same bound as [Li and El Gamal, 2018, Theorem 1]. \nThis can be seen from eq(38) on page 17: when $J=1$, eq (38) becomes $E\\log_2[ \\frac{q(z)}{p(z)}+1]$. We can then follow the proof of [Li and El Gamal, 2018, Appendix p13].\n\n> Could we recover a bound with a dependence in $J$?\n\nPlease note that $\\epsilon$ in Theorem 3.1 already expresses a fine-grained dependence on $J$. Furthermore, Proposition 3.2 also depends on $J$ in the sense that it is derived by the extreme case $J = 2^{KL}$ and holds for all $J \\leq 2^{KL}$. It is an interesting question if there is a bound that interpolates $J=1$ and $J = 2^{KL}$. In our paper, we did not explore this because, for our method, we always want to set $J$ as large as possible to maximize the gain in speed. \n\n2) > Could the author give more details about how these intervals are constructed?\n\nAs we discussed in our manuscript from line 241 to line 249, we partition the d-th axis into approximately $2^{n_d}$ intervals, where $n_d = D_{KL}[Q||P] I_d / \\sum_{d’} I_{d’}$. We provide the implementation details of constructing these bins from line 621 to line 630.\n\nIn fact, we empirically found that the methods are NOT very sensitive to how we construct the intervals, as long as we avoid partitioning along uninformative dimensions. Please see the rebuttal PDF (Fig 3) for further empirical verification.\n\n3) > Would it be possible to automatically find a transformation prior to the binning that would provide better results while keeping the same strategy:\n\nIt is not possible to design such a transformation. Note that to avoid sending the transformation (which can be expensive), it should be shared across all data points X. Therefore, if we want to find a transformation to the prior, it is equivalent to asking if we can find a better prior that provides better results on average. \n\n4) > Is there a way to update $\\pi$ along the algorithm\n\nSince our algorithm will work for any $\\pi$, it is possible to update it. However, there is no point in doing so as the optimal form of $\\pi$ is already given in eq (12) and eq (15), which we can use at negligible computational cost.\n\n5) > It would be interesting to add an ablation study on the number of intervals per axis\n\nThank you for this suggestion. We added ablation studies on toy examples and INR experiments. Please find the results in the PDF we uploaded to global rebuttal. We will add these plots to our camera-ready version. We now explain these studies, and please also see the global rebuttal for a more detailed description:\n\n- We first provide a qualitative visualization in Figure 1 in our rebuttal comparing 3 different binning strategies: only partitioning the collapsed dimension; randomly assigning the number of intervals per axis; and assigning intervals per axis according to MI (our suggested strategy). We also include standard ORC for reference. As we can see, our suggested strategy works best, whereas partitioning only the collapsed dimension yields almost the same results as standard ORC. This verifies our discussion on how the partitioning strategies will influence the runtime in Appendix B.2 in our manuscript.\n\n- We then provide quantitive ablations on toy examples (Fig 2) and INR experiments (Fig 3). We can see our suggested partition strategy (partitioning according to MI) is always better than randomly assigning intervals per axis. Also, we found if we first remove uninformative dimensions (mutual information $\\approx$ 0), and then randomly assign intervals to other dimensions, the performance is only slightly worse than our proposed partition strategy. This indicates that our algorithm is not very sensitive to how we construct the intervals, as long as we avoid partitioning along uninformative dimensions.\n\n6) > it would be interesting to have Tab 1 in time\n\nThe sample size is linearly proportional to the runtime, so we only provide this in Fig 3 and Tab 1. The sample size is a better metric as it is implementation-agnostic, unlike wallclock time. \n\n> I do not understand what is meant by runtime in Fig 3\n\nThis figure shows ‘how many samples in ORC we need for a certain bias’. The y-axis shows the sample size to achieve a certain bias (measured by MMD).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9QnTNcllPL", "reviewer": "Reviewer_wyos", "summary": "The authors provide a formalization on how to introduce search heuristics for channel-simulation (sometimes called \"relative entropy coding\" in the ML literature). The encoder and decoder agree a priori on a binning scheme that divides the support of the prior/public distribution, which is used to control the search during encoding.\n\nDisclaimer: while I'm familiar with the basic literature (e.g. REC, PFRL, ORC), I haven't kept up with the literature since 2022.\n\nI'm more than willing to change my scores if the authors point out I missed something or didn't fully understand the contributions.", "questions": "- Line 66: Why is it important for the state $S$ to be random? I don't see this being used anywhere.\n\n- Line 213: The non-exactness here is with respect to $Q$. REC-like algorithms are usually formulated to be used in the latent space, i.e., the encoder wants to send a sample from $Q_{Z | X}$, but what we care a about from a practical standpoint is to transmit the data $X$ according to some rate-distortion trade-off. Shouldn't this discussion be formulated around the data space (maybe this is too hard of a problem?)?\n\n- Regarding the binning prior $\\pi$. The target distribution is a function of $X$, i.e., $Q_{Z | X}$. Isn't it hard to pick a good $\\pi$ given this distribution is constantly changing?", "limitations": "- Line 267: The results are computationally intensive, and thus impractical, even for MNIST. Requiring the value of mutual information to be known by encoder/decoder seems a bit much (the authors mention this in the limitations section).", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is nicely written. This is notably a complicated topic to understand and I feel the authors made quite a didactic effort.\n- The excess code-length is bounded for the distributions found in practice for NTC.", "weaknesses": "- Line 21: I feel this statement is misleading. In the first scenario (lines 14 to 20), the actual value taken on by the random variable is what is being transmitted. Meanwhile, in channel-simulation, all we care about is that the received quantity be distributed according to $Q_{Z | X}$. These are fundamentally different problems. The comparison would make some sense if, in the first scenario, the decoder is necessarily stochastic, as decoding can be seen as sampling from some posterior distribution over the data conditioned on the latent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and insightful review. We are delighted that the reviewer recognizes the difficulty of this task and appreciates the contribution of our work. Below, we respond to the reviewer's concerns and questions. Should the reviewer find our answers satisfactory, we kindly invite them to consider raising their score.\n\n**Weakness: Line 21 in the Introduction is misleading, quantization and REC are fundamentally different**\n\nWe thank the reviewer for raising this concern. Upon revisiting the paragraphs the reviewer mentions, we agree that our argument can easily appear as an apples-to-oranges comparison. Hence, to clarify: the point we wanted to make here is that quantization makes end-to-end learning difficult due to its non-differentiability. Hence, we advocate for REC, which swaps out quantization for some continuous perturbation as a means of limiting the latent representation’s information content, as the latter integrates well with end-to-end training thanks to the reparameterization trick. We will clarify the introduction in our camera-ready version based on this discussion.\n\nHowever, we’d also like to note that the difference between using 1) quantization + entropy coding or 2) relative entropy coding for lossy compression is not necessarily as big as the reviewer is claiming. The analysis of quantization often relies on treating the quantization error as uniform noise. This approximation has been remarkably successful in the study of quantization and in practice, as it is the foundation of Balle et al.’s neural compression methods as well. Furthermore, Agustsson and Theis (2020) show that quantization-based schemes can be turned into relative entropy coding-based schemes (with uniform target distributions) with a simple modification.  \n\n**Regarding Questions:**\n\n1) > Why is it important for the state $S$ to be random?\n\nThanks for raising this point. By random state $S$, we mean the common randomness between communication parties, a standard requirement by all channel simulation schemes. We will clarify our terminology in the camera-ready version of the paper. \n\n2) > Shouldn't this discussion be formulated around the data space?\n\nThis is a great question! While we do not discuss this in our paper, this concern is precisely why we use total variation to measure the approximation error, as bounding the error in latent space gives us an immediate guarantee in data space. More formally, denote the decoder by $f$, the true target distribution as $Q$ and the approximate target $\\tilde{Q}$. Furthermore, assume $D_{TV}[Q \\Vert \\tilde{Q}] \\leq \\epsilon$. By the data processing inequality, we have $D_{TV}[f_{\\*}Q  \\Vert f_{\\*}\\tilde{Q}] \\leq\\epsilon$, where $f_{\\*}Q$ denotes the pushforward measure. For more discussion on this topic, please Section III in Flamich and Wells (2024); we will update the camera-ready version to include this discussion. \n\n3) > Isn't it hard to pick a good $\\pi$ given this distribution is constantly changing?\n\nNo, thankfully is not difficult! \n- first, the partition is fixed across all data points, and hence, this operation is amortized and not expensive;\n\n- second, for ORC (Sec 4.2), to sample from eq (15), we only need to first sample from $Q$ and find the bin in which the sample lies. Therefore, we do not need extra operations for pre-processing; for PFR (Sec 4.1), we need to calculate $\\pi$ in eq(12) per dimension for each data point before sampling. But this is still much cheaper compared to sampling;\n\n- additionally, we highlight that the receiver does not need to be aware of $\\pi$ to reconstruct the sample. Therefore, while the $\\pi$ we use differs for different data points, there is no extra cost in transmitting.\n\n**Regarding Limitations:**\n\n> The results are computationally intensive, and thus impractical, even for MNIST.\n\n We do not necessarily agree that the VAE results are computationally intensive and impractical. We use $2^{16}$ samples to encode a block that requires around $2^{50}$ samples by previous methods. With our method, we have already largely reduced the computation cost and made REC more practical, though we definitely believe that this can be further improved. \n\n> Requiring the value of mutual information to be known by encoder/decoder seems a bit much.\n\nWe agree that this is not a totally general assumption. However, it is not too much for a practical neural compression application. In most neural compression applications, including data compression and (potentially) federated learning, we have access to training data on which we can easily estimate the dimensionwise mutual information. Also, compared with assumptions for previous faster methods (either assuming 1D or uniform/Gaussian with a known scale per dim), our assumption is already a lot more general.\n\n\n\n**References**\n\nAgustsson, E., & Theis, L. (2020). Universally quantized neural compression. Advances in neural information processing systems, 33, 12367-12376.\n\nFlamich, G., & Wells, L. (2024). Some Notes on the Sample Complexity of Approximate Channel Simulation. arXiv preprint arXiv:2405.04363.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We extend our gratitude to all the reviewers for their detailed and comprehensive reviews and for their time spent reviewing our manuscript. We are delighted that the reviewers found our paper easy to follow and recognized our method's technical and theoretical contributions. We addressed their concerns in our responses.

We also attach a PDF showing additional illustrative and ablation experiments for our method. Namely:

- **In Figure 1, we visualize the approximation error of using ORC with different partitioning strategies on a toy problem**.  we create a 5D Gaussian target, and we set dimension 1 to have 0 mutual information(we call it a collapsed/uninformative dimension). 
We compare three partition strategies: only partitioning the collapsed dimension; randomly assigning intervals to dimensions; and assigning intervals according to MI (our proposed strategy; specifically, we partition the d-th axis into approximately $2^{n_d}$ intervals, where $n_d = D_{KL}[Q||P]\cdot I_d / \sum_{d’} I_{d’}$). We also include standard ORC for reference. We run the four settings with the same number of samples (20) and repeat each setting 5000 times. We show the histogram of 5000 encoded results.
*As we can see, assigning intervals according to MI  works best, whereas partitioning only the collapsed dimension yields almost the same results as standard ORC. This verifies our discussion on how the partitioning strategies will influence the runtime and how we should choose the intervals in practice in Appendix B.2 in our manuscript.*



- **As suggested by the reviewers we4Y, we provide ablation studies showing how partition strategies will influence performance**.
We run the ablation on the Gaussian toy example (the experiment described in line 260 in our manuscript) and the CIFAR-10 compression experiments (the experiment described in line 286 in our manuscript).
The results are shown in Figures 2 and 3 in our rebuttal PDF. *As we can see, our proposed partition strategy (partitioning each dimension according to mutual information) is always better than randomly assigning intervals per dim*. For CIFAR-10, we also compare the results by first removing uninformative dimensions (mutual information $\approx$ 0), and then randomly assigning intervals to other dimensions. We find this is only slightly worse than our proposed partition strategy. *This not only further verifies our discussion in Appendix B.2, but also indicates that our algorithm is not very sensitive to how we construct the intervals, as long as we avoid partitioning along uninformative dimensions.*

Meta-review: This paper proposes an heuristic to improve relative entropy coding algorithms, and validates its method numerically.

The reviewers unanimously agreed that this well-written paper effectively addresses important questions: I recommend it for acceptance.
Decision: Accept (poster)