iFlow: Numerically Invertible Flows for Efficient Lossless Compression via a Uniform Coder
Authors: Shifeng Zhang
Ning Kang
Tom Ryder
Zhenguo Li
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: lossless compression
flow model
entropy coder
deep generative model

Abstract: It was estimated that the world produced $59 ZB$ ($5.9 \times 10^{13} GB$) of data in 2020, resulting in the enormous costs of both data storage and transmission. Fortunately, recent advances in deep generative models have spearheaded a new class of so-called "neural compression" algorithms, which significantly outperform traditional codecs in terms of compression ratio. Unfortunately, the application of neural compression garners little commercial interest due to its limited bandwidth; therefore, developing highly efficient frameworks is of critical practical importance. In this paper, we discuss lossless compression using normalizing flows which have demonstrated a great capacity for achieving high compression ratios. As such, we introduce iFlow, a new method for achieving efficient lossless compression. We first propose Modular Scale Transform (MST) and a novel family of numerically invertible flow transformations based on MST. Then we introduce the Uniform Base Conversion System (UBCS), a fast uniform-distribution codec incorporated into iFlow, enabling efficient compression. iFlow achieves state-of-the-art compression ratios and is $5 \times$ quicker than other high-performance schemes. Furthermore, the techniques presented in this paper can be used to accelerate coding time for a broad class of flow-based algorithms. 

iFlow: Numerically Invertible Flows for Efficient Lossless Compression via a Uniform Coder
Shifeng Zhang, Ning Kang, Tom Ryder, Zhenguo Huawei Noah's Ark Lab izhangshifeng4, kang. kanq.ninge ning2, tom. ryder1,, 11. zhenguo) huawei com
Abstract
It was estimated that the world produced 59ZB (5.9 x 10L of data in 2020, resulting in the enormous costs of both data storage and transmission. Fortunately, recent advances in deep generative models have spearheaded new class of so- called "neural compression" algorithms, which significantly outperform traditional codecs in terms of compression ratio. Unfortunately, the application of neural compression garners little commercial interest due to limited bandwidth; there- fore, developing highly efficient frameworks is of critical practical importance. In this paper, we discuss lossless compression using normalizing flows which have demonstrated great capacity for achieving high compression ratios. As such, we introduce iFlow, a new method for achieving efficient lossless compression. We first propose Modular Scale Transform (MST) and novel family of numerically invertible flow transformations based on MST. Then we introduce the Uniform Base Conversion System (UBCS), a fast into iFlow, enabling efficient compression. iFlow achieves state-of-the-art compres- sion ratios and is 5x quicker than other high-perfone perorreeformacc schemes. Furthermore, the techniques presented in this paper can be used to accelerate coding time for a broad class of flow-based algorithms.
codec incorporated
1 Introduction
The volume of data, measured in terms of IP traffic, is currently witnessing exponential year- on-year growth [13]. Consequently, the cost transmitting and storing data is rapidly becoming prohibitive for service providers, such as cloud and streaming platforms. These challenges increas- ingly necessitate the need for the development of high-performance lossless compression codecs.
One promising solution this problem has been the development of new class of so-called "neural compression" " algorithms 33
38 18 17
37 26
31 6, 41). These methods typically posit a deep
probabilistic model of the data distribution, which, combination with entropy coders, be used to compress data with the minimal codelength bounded by the negative log- log-likelihood (2)] However,
despite reliably improved compression performance compared to traditional codecs [14 33 9 34]
meaningful commercial applications have been limited by impractically slow coding speed.
In this paper, we focus developing approaches with deep probabilistic models based on normalizing flows [1] 32 27 28 23). A normalizing flow admits a learnable bijective mapping between input data and latent variable representation. In this paradigm, inputs can be compressed by first transforming data to latent variables, with the resulting output encoded by prior distribution. Compared to other classes of generative models, normalizing flows typically perform best in both tasks of probability density estimation (as compared with variational autoencoders [24] [5] 8) and inference speed (as compared with autoregressive factorizations compression with flows can jointly achieve high compression ratios along with fast coding times.
35 39 22 This suggests that
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(+F())) IPF
LBB
iF low (Proposed)
(o/
FiN)
Lencoding:
DirecoMAT
lencoding
730
iencoding
MST
D x =0==] = MAT: w-x [[==1) 1)
N00
Quantize
de/eeccdding
== x
Flow layer
Flow layer
IF low layer
MST
[1
Quantize
Hdelencoding
Flow layer
Flow layer
low layer
MST
idecoding Dequant
decoding
Dequant X
decoding
Dequant
X
X
Compression Compression bandwidth
Illustration of IDF(++), iVPF, LBB and the proposed iFlow method. Flow layers with darker color denote higher expressive power. The top-right of each model illustration shows the key procedure of exact bijections between č and x. The compression ratio and bandwidth are listed below.
Figure 1:
Unfortunately, lossless compression requires discrete data for entropy coding, and the continuous bijections of normalizing flows would not guarantee discrete latent variables. As such, transformations would require discretization, resulting in a loss of information 41 To resolve this issue, Integer Discrete Flows (IDF) 18 (Fig. left) proposed an invertible mapping between discrete data and latent variables. Similarly, iVPF [11] achieves discrete- space bijection using volume settum--rreeeving flows. However, the above models must introduce constraints on flow layers ensure a discrete- space bijection, which limits the expressivity of the transformation. Local Bits-Back Coding (LBB) 117 (Fig. 1 middle) was the first approach to succeed lossless coding with the flexible family of continuous flows. It resolves the information loss by coding numerical errors with the rANS coder [1]. However, the coder extraordinarily slow, making the method impractical.
In this paper, we introduce iFlow: a numerically invertible flow-based neural compression codec that bridges the gap between high-fidelity density estimators and practical coding speed. To achieve this we introduce two novelties: Modular Scale Transform (MST) and Uniform Base Conversion Systems (UBCS). MST presents flexible family bijections in discrete space, deriving an invertible class of flows suitable for lossless compression. UBCS, built on the uniform distribution, permits highly efficient entropy coding compatible with MST. The main ideas are illustrated in Fig. rightt. We test our approach across range of image datasets against both traditional and neural compression techniques. Experimentally we demonstrate that our method achieves state-of-the- compression ratios, with coding time 5x quicker than that of the next-best scheme, LBB.
2 Numerically Invertible Flows and Lossless Compression
Let : X + be our normalizing flow, which we build as composition of layers such that f ft ... o f2 fi. Defining d-dimensional yo x E X and yz z E Z, the latents can be computed as yı fi(y)-1), with px (x) calculated according to
logpx (x) logpz(z) + Σ log det Jj, (y(-)))
(1)
log to where Jj, (x) is the Jocabian matrix of the transformation fi at y1-1- In this paper, logxx px (x). denote base 2 logarithms. Training the flow should minimize the negative log-likelihood - log The inverse flow is defined as f-1 = f- .... fz such that f (z) x. There are many types of invertible bijections, fi- Popular choices include element- autoregressive (e.g. coupling layers) 41 and x convolution transformations [25].
To perform lossless compression with normalizing flows, the input data should be transformed to latent variables, which are then encoded with a prior distribution. As data and encoded bits should be in binary format, x and must be discrete, with bijection between discrete inputs and outputs

---

established. However, discussed, this operation is usually intractable with popular classes of transformations used in continuous flows due to the numerical errors induced by discretization.
In this section, we introduce a novel algorithm derived from continuous flows that allows us to achieve exact bijiective mapping between discrete and discrete z. We present the general idea of flow layer's numerical invertibility in discrete space in Sec. 2.1 We then introduce our flow layers in Sec. with their application to compression discussed in Sec. 2.4 and 2.5
2.2 and 2.3
2.1
Invertibility of Flows in Discrete Space
To discretize the data, we follow 41 and adopt k- k-precision quantization to assign floating points to discretization bins such that
2
2
where I.J the floor function. The associated quantization error bounded by | - x < 2- Any d-dimensional x can be quantized into bins with volume 8 2-kd then be approximated by P(x) p(8)ō, such that the theoretical codelength is log(p(X))),
kd The probability mass of x can
Denote our proposed numerically invertible flow (iFlow) according f fz ... f The input and output should be subject to k-precision quantization, where each layer should be appropriately invertible such that yi-1 = JT" (f(y)-1)) Denoting Yo = x and z = YL,
further expected that z = =x((x) and x f We will show in the following subsections that can be derived from any continuous flow in such way that the error between f(x) and fx) is negligible.
2.2 Numerically Invertible Element- Wise Flows
We begin by describing our approach for element-wise flows z f(x), where I is monotonic element-wise transformation. For notation simplicity, we assume that the flow contains just one layer. In most cases, does not present unique inverse in discrete space, such that f f- + In what follows, we introduce an approach to derive an invertible, discrete-space operation from any element-wise flow transformation, For simplicity, we denote the inputs and output pairs of continuous flow and f (x)); and we denote the k- k-precision quantized input-output pairs of iFlow as T and f(x).
2.2.1 Scale Flow
Algorithm Modular Scale Transform (MST); Numerically Invertible Scale Flow f(x) = R/S x.
Forward MST: = [(z).
Inverse MST: x (x).
1: & 2* :;:
+ 2* :2;
Decode ra using (0, R); ÿ rra
Decode r. using (O, S): +- S 2 re:
3: 2 + 19/S].r. + 8 mod S:
3: ă < [0/R]. ra + 9 mod H:
4: Encode Te using UO,, S);
4: Encode ra using (O, R);
5: return - 8/2².
return F + a/2
We begin with the scale transformation defined as = = fxx a H, (a > 0), from which we are able to build more complex flow layers. The input can be converted an integer with å = 2 . and the latent variable can be recovered from integer 2 by first approximate with a fractional such that z S'
Σ/2². Inspired by MAT in iVPF [41, we it where R, S E N. Denote ý = R à + where
ra is sampled uniformly from (0, 1,... 1). we can obtain with 10/S|, , and the remainder re = ú mod R can be encoded to eliminate the error. It is clear that (f, + + (2, re) are bijections.
Let (0, A) be the uniform distribution such that P(s) 1. & E (0, 1,.., A - 1}. The numerically invertible scale flow f is displayed in Alg. I As the modular operation is essential to Alg. 1 we name it the Modular Scale Transform (MST). Setting S and round(S aa) to be large, we observe that the following propositions hold.
Proposition
[4] |z f() 0SS-122-1)
Proposition 2. The codelength of MST is Lū log S log R log |a| log (z)
3

---

Proposition 1 esstablihhss that the error is small if S and k are large. Proposition 2 demonstrates that the codelength almost exactly the log-Jocabian of f. The above properties and the correctness of the algorithm are discussed in the Appendix. Further note that, with the exception of the usual encoding and decoding processes, MST's operations can be parallelized, resulting in minimal additional overhead. In contrast, MAT"s s operation in iVPF [41] only deals with volume-prest preserving affine transform and is performed sequentially along dimensions, limiting its usage and efficiency.
2.2.2 General Element-wise Flow
Algorithm 2 Numerically Invertible Element-wise Flows
Forward: = f()).
Inverse: x 2= f-).
I: Get Ht, By. &t, En, given ž. so that E [T,, F.):
Get Tt, In, 2t, En given 5, so that E E [Ex, En):
2: Set large S: get At with Eq. (4 +- f 2t:
2: Set large St get R with Eq. (4); < 2 At:
3: Get z' with forward MST in Alg. given input x'
3: Get ø' with inverse MST in Alg. [ given input x' and coefficients S; 4: return ā = F' Tt.
and coefficients R, St
4: return = 5' Et.
b 12, J-)-
E [,)))
For simplicity, we assume the non-linear f is monotonically increasing. For a monotonically decreasing f. we simply invert the sign: -f.
MST in Alg. D works with linear transformations, and is incompatible with non-linear functions. Motivated by linear interpolation, we can approximate the non-linear flow with piecewise linear function. In general, consider input E to be within an interval F E [āt, Zy. and ž f(ā)). The linear interpolation of f is then
f(īt), En
En
21
fimp(z)=
+ Zt.
(3)
It follows that can be derived from MST with input x 3, followed by adding &, Furthermore, and I can be recovered with the corresponding inverse transformation. To preserve monotonicity, must be within interval & [ž1, Zn). Denoting the invertible linear flow derived from fimp as ftop. it must hold that (āt) 2 Et, fiup (T 2 2-h *) S 2 2 As use MST in Alg. I we observe that when 2n-2i is approximated with R,S, the minimum possible value of ( is (when rd = 0 in Line Zn-2
>>}{ is [ (2,- - - 2 2- R- R--RRR(S 1)/(S)2*))))))) (+)-2*)++++ (when ra R in Line 2). Given large S, the largest possible value of R should be
2) and the maximum possible value of 7mp(3n - --
(2*
(2h
2,) 1) 1+1 2
R
(4)
(Tr
Fi.)
Another difficulty is in determining the correct interpolation interval [ .x)). One simple solution is to split the input domain into uniform intervals with length 2 such that [(2h /2/ .r, Tt + 2-h However, for the inverse computation given ž, it is not easy to recover the interpolation interval as (z) may not be within [āt, J.)) Instead, as E [ž,, E,), the interval [īt, .x)) can be
obtained via a binary search in which ž is obtained with V E [f)). f(x))) Another approach
is to split the co-domain into uniform intervals such that ž = [(2 2) žn = ă + 2-h, with Tt = (5), Ty fz)(... In this case, determining [ žn. during the inverse computation simple. While for the forward pass, [ 2x) should be determined with binary search such that T E ( (2), (z)() In practice, we have simpler tricks to determine the correct interval (7), T1). [1), 7x) for both the forward and inverse computation, which can be found in the Appendix.
The general idea of the non-linear flow adaptations are summarized in Alg. 2 Note that Alg. can be used in any element-wise flow including linear flow. In Alg. 2 Proposition holdd such that (ū 2) RtS) R log Σu-Ei & - log ((()). possible to arrive similar Ry, -
conclusion in Proposition I where the corresponding error is j f()) < O(S-1, 1-- 2-k 3- 2-b).
All intervals must partition the domain of

---

2.3 Practical Numerically Invertible Flow Layers
Whilst one can use many types of complex transformations to build richly expressive flow-based models, to ensure the existence and uniqueness of the inverse computation, these layers are generally constructed with element-wise transformations. In this subsection, we demonstrate the invertibility of discretized analogs to some of the most widely used flow layers using the operators as described in Sec. 2.2] Such flows include autoregressive flows [00] (including coupling flows [10] [6] and
1 x convolutional flows [25].
2.3.1 Autoregressive and Coupling Flows
Algorithm 3 Numerically Invertible Autoregressive Flow
Forward: 2 f(x).
Inverse: x= j-
I: for i =m,, .... do
1: for i = 1, 1,... m7 do
2:
end fx(,, with Alg.
(forward);
2:
Ji (2,, 8cs) with Alg. 2 (inverse);
end for
return = [.1...., Zmm
return 2 ?i,,..,, Rm]
Supposing that the inputs and outputs, x and z, are split into m parts x = [x], Xmm [e..... Zm the autoregressive flow z f(x) can be represented as z, fx(x;;Xx)) where xes) is the element-wise flow (discussed in Sec. 2.2). conditioned on X Now let f((:;ee)
denote the invertible element-wise flow transformation as discussed in Alg. Alg. then illustrates
the details of an invertible autoregressive flow
Propositions aad Manassttioonsnn2222 holld in discretized autoregressive transformation. In fact, the log-determinant of Jacobian is given by log det y Σ log det (xx; and the expected codelength is simply (x( 2) = Σ L 2,) ~ - log det (X;; = log det [-)
When 2 and (xi) = X1, the autoregressive flow is reduced to coupling flow, which is
widely used in flow-based models [10 [6). is therefore trivially clear that the coupling flow additionally compatible with Alg.
2.3.2 1 X Convolutional Flow
1 convolutional layers can be viewed as a matrix multiplication along a channel dimension [25] Let x, E' be imputs and outputs along channels, and W E geex the weights of our network. The objective is to obtain ž = f(x) where f(x) Wx.
We use the ideas of iVPF 41 to achieve numerically invertible x convolutional transformation. In particular, we begin by performing an LU decomposition such that W PLAU. then follows that the 1 x 1 convolution is performed with successive matrix multiplications with U, A, L and P. iVPF, the authors extensively discussed matrix multiplications with factors U, and P [T]. Meanwhile, one can view the matrix multiplication with A as scale transform, such that f(x)
& x, where @ an element-wise multiplication and X are the diagonal elements of A. MST in Alg. [ can then be applied. In such case, it is clear that Proposition and 2 hold for a x 1 convolutional flow. For Proposition 2 it is observed that L5 Z) Rs -sum(log A) =
[
log det A| log det W| log det J (x)].
2.4 Building Numerically Invertible Flows
Our flow model is constructed as composition of layers f fr. o.. f2 fi, where each layer is transformation of the type discussed in Sec. 2.2 and 2.3 Let us represent the resulting flow as = fr. o fi, where Ft is a discretized transformation derived from the corresponding continuous f. It is clear that the quantized input x(= Yo) and latent z(= yr) establish bijection with successive transformations between discrete inputs and outputs. For the forward pass, & is computed with y, 1(81-),, = 2, L; for the inverse pass, X is recovered with the inverse flow f-1 f fr, such that f fi (fr).
5

---

For our resultant flow model, we can draw similar conclusions as in Propositions 1 and 2 Firstly, the error of f(x) and z = fxx small. bounded by 2z z O
L2 L2 Secondly,
the codelength is approximately L z) - Σイ L = Ei log det J/. (y1-1))-
2.5 Lossless Compression with Flows via Bits-back Dequantization
Armed with our flow model f. performing lossless compression is straight-forward. For the encoding process, the latent is generated according to z = f(x). We then encode z with probability pz (z)6. For the decoding process, z is decoded with pz (2)),, and x is recovered with f (z). The expected codelength approximately - log(px (x)6) such that
= - -og(p=222222)) - L 1=1
log det Jn (yi-1)) == - log(px(())
(5)
However, we note that & is large. - waste of bits. For what follows, we adopt the bits-back trick in LBB [17] to reduce the codelength. In particular, consider coding with input data x E Zd, where a k-precision noise vector il E [o, 1) decoded with q ( xx) j and added to input data such that x = x + u. In this way, x is then encoded with our flow f. For the decoding process, x² is recovered by applying the inverse transformation. We name this coding process Bits-back Dequantization, which is summarized in Alg.
log kd and the codelengths will also be large, resulting in
Algorithm 4 Lossless Compression with iFlow.
Encode x".
Decode.
I: Decode ū using ((ū(x"))
1: Decode z using pz (Z)6;
2: 2 < f(x² u);
2: X +- f (Z). +- [x];
3: Encode using pz (z)6.
3: Encade
x using q x");;
return x".
In practice, q(u(x") is constructed with flow model such that u = g(E where p(E).
decoded by first decoding é with p(ε)ō, and then applying ú = g(E; x"). Thus decoding
involves log(g(ūlx")) bits. Overall, the expected codelength is exactly the dequantization lower
bound 19 such that
((x)) s0 Σ x ([lo))))0[(((((()))) - log(p(x + []))]
(6)
Eg | (()x)( - log - -u)]
2.6 Extensions
With novel modifications, flow models can be applied to the generation of various data types, obtaining superior performance 7 2 23). These models can be used for improved lossless compression. In general, given input data x", these models generate intermediate data with q(vix"), x"), and the density of v is modelled with flow model z = f(v). .. For generation, when v is generated with the inverse flow, is generated with p(x*lv) (v). It is clear that p(x) can be estimated with variational lower bound such that log p(x²) ) 2 E E P(x²lv) + log p(v) - log q( ((V (x) ]- For lossless compression, x" can be coded with bits-back coding, which is similar with Alg. 4 In the encoding process, we first decode v with (V) ) and then encode x" with Vv) (similar with Line in Alg. 4 Encodee. We then obtain the prior = f(v) (Line 2), before finally encoding Z with (2(2)8 (Line 3). In the decoding process, z is firstly decoded with pz (2)6 (similar to Line in Alg. Decode), and then recovered v and decoded x" with P(x* (v) (Line 2). Finally, we encode using v with q(v(x") [38
The expected codelength is approximately
log L(x²) x (Exgviee[logg((V - log -lgg
We introduce a selection of recent, state-of-the-at flow-based models modified according to the above. Each model corresponds certain coding algorithm.
VFlow 77. VFlow expands the input data dimension with variational data augmentation to resolve the bottleneck problem in the flow model. In VFlow, = [x + ru E [0, 1)"), where

---

(xr; u) (Eu, E, are priors). Then we have q(v)x)) = qu (u|x*) (q. (r|x² + u), P(x 1 (as v x)). Thus for the encoding process, Eu; E, are decoded. To construct v we have encoded with iFlow. For the decoding process, is decoded with the inverse iFlow, and then x", ii, F is recovered with v. Here ii, F is encoded and x the decoded output. As VFlow achieves better generation results compared with general flows, one would expect a better compression ratio with VFlow.
qu (u(upx), ), r (r(xxx² + +u), is modelled with flows Iu. Ir such that u = 9u (u(E,;
(x" +u)
u )= x²) Dr [r(;;;;" + n); and then
Categorical Normalizing Flow [28]. Categorical Normalizing Flows (CNF) succeed in mod- elling categorical data such as text, graphs, etc. Given categorical data x" [2] ....... Fnl: 24 E [Vi.... vnl represented with word embeddings such that q(V.
{1.2.... C)",
le ( o (z)),, in which could be a Gaussian or logistic distribution. Then P(r;/v;) =
Jove with p being the prior over categories. Thus ((v[x") -IT ((val1a), [(x*lv)
E p(o)atvlle)
I. Pizalvi), and x can be coded with Alg. 8 giiven q(vix9), P(x*Iv (v) and the iFlow.
3 Uniform Base Conversion Systems
Algorithm 5 Uniform Base Conversion Systems
ENCODE using (0, () < ). Input: symbol 8, state c, bit-stream bs. Output: new state and bit-stream bs.
DECODE with ( R) R) 2*).
Input: c, bit-stream bs.
Output: decoded 8, new state c and bit-stream bs.
I: e c- R-R+ c 2M then
if 2 R then
2: c c 2 w.t.bspppppp......... pack (): get last.
3: bs. aas-push_backe (c mod 2x;; b push K
K bits from bit-stream and pop them.
bits to bit-stream.
3: end if
4: c< 1;
4:
mod R:
end
e t- Le/R]:
6:
return c, bs.
6: return C, bs.
The previous section demonstrates that coding with a uniform distribution is central to our algorithm. Note that the distribution varies in each coding process, thus dynamic entropy coder expected. Compared to the Gaussian distribution used in LBB (17), uniform distribution is simpler, yielding improved coding speed. As follows, we introduce our Uniform Base Conversion Systems (UBCS), which is easy to implement and the coding bandwidth is much greater than that of rANS [12]
UBCS is implemented based on number-base conversion. The code state is represented as an integer. For coding some symbol s E 10.,, R - 1} with a uniform distribution (0, R), the new state e is obtained by converting an R-base digit s integer such that
è' = E(c s) c R
(8)
For decoding with UO, R), given state d', the symbol and state e are recovered by converting the integer an R-base digit such that
s d mod R, c D( =
We note, however, that will become large when more symbols are encoded, and computing Eq. ( with large c will be inefficient. Similar to rANS, we define a "normalized interval" which bounds the state such that M2 2 2K+M +M (K, .M are some integers values) after coding each symbol. For the encoding process, if c 2 2 +M the lower K bits are written to disk, and the remaining bits are reserved such that
| ş For the decoding process, if c < 2 Rr, the stored K bits should be read and appended to the state before decoding. In this way, the decoded state is contained within the interval [2 2 ). The initial state be set such that 2M We illustrate this idea in Alg. 5
The correctness of Alg. 5 is illustrated in the following theorem. demonstrates that the symbols can be correctly decoded with UBCS coder, with coding performed in a first-in-last-out (FIL.O) fashion. P2 shows that the codelength closely approximates the entropy of a uniform distribution, subject to large M and K. The proof of the theorem is in the Appendix.
7

---

Table 2: Coding performance of iFlow, LBB and iVPF on CIFARIO dataset. We use batch size 64.
flow
compression technique
encoding time (ms) inference
decoding time (ms) inference
arch.
nll
bpd
aux. bits
coding
coding
LBB 17
3.118
39.86
1 11621a
112
Flow++
3.116
16.2+03
32.4+02
iFlow (Ours)
3.118
34.28
21.0
37.7
IVPF []]
3.201
6,00
11.4402
13.5
iVPF
3.195
5.5
5.2
iFlow (Ours)
3.196
7.00
7.1
9.7102
Theorem 3. Consider coding symbols $1, with 8; ~ (i= n. R. 2*) using
Alg. 5 and then decode sn, sn.1...., 8 sequentially. Suppose (1) the initial state and bit-stream are
co 2M, bsn = empty respectively; (2) After coding the state is c; and the bit-streum is bss (3) After decoding 5'441 the state is d4 and the bit-stream is bs. We have
Pf: s c Ci, bs! = bs, for all i 0,...: n
P2: Denote by the codelength 1, [log Gi len (bs;) where len the total number of bits in the bit-stream. Then ln la 1- 1 2. E Rg ++1 (In 2 22222-11
In practice, set K 32 and M 4. Compared rANS [12 and Arithmetric Coding (AC) [40], UBCS is greater efficiency it necessitates fewer operations (more discussions are shown in the Appendix). UBCS can achieve greater computational efficiency via instantiating multiple UBCS coders in parallel with multi-threading. Table [T demonstrates that UBCS achieves coding bandwidths excess of giga-symbol/s - speed significantly greater than rANS.
Table 1: Coding bandwidth (M sym- bol/s) of UBCS and rANS coder on dif- ferent thread We the imple- mentations in [17) for evaluating rANS.
# thrd
rANS
UBCS
1
5.1403
380
Encoder
16
21.6111
2075:353
1
0.84am
66.2
Decoder
16
7.440s
552=50
4 Experiments
In this section, we perform number of experiments to establish the effectiveness of iFlow. We will investigate: (I) how closely the codelength matches the theoretical bound: (2) the efficiency of iFlow as compared with the LBB [17 baseline; (3) the compression performance of iFlow on a series low and high-resolution images.
4.1 Flow Architectures and Datasets
We adopt two types of flow architectures for evaluation: Flow++ [16] and iVPF [1] Flow++ is a state-of-the-an art model using complex non-lime non-linear coupling layers and variational dequantizations [19]. iVPF is derived from a volume- volume-preservvng flow in which numerically invertible discrete-space operations introduced. The models are re-implemented or directly taken from the corresponding authors. Unless specified, we use h = 12, k = 28 and set large $ around 216 which we analyse further in the Appendix. To reduce the auxiliary bits in the bits-back coding scheme, partition the d-dimensional data into b splits and perform MST (in Alg. [ [nd 2 for each split sequentially. In this case, the auxiliary bits can be reduced 1/6 in MST. We b 4 this experiment.
Following the lossless compression community [6 18 37 41, we perform evaluation using toy datasets CIFAR10. ImageNet32 and ImageNet64. Results for alternate methods are obtained via re- ee-iplementation or taken directly from the corresponding papers, where available. We further test the generalization capabilities of iFlow in which all toy datasets compressed with model trained on Im33eNet32. For benchmarking our performance on high-resolution images, we evaluate iFlow using CLIC.mobile, CLIC.pro and DIV2k [1. For this purpose,
adopt our ImageNet32/64 model for evaluation, and process an image in terms of 32 x 32 or 64 x 64 patches, respectively. The experiment is conducted with Py Torch framework with one Tesla P100 GPU.

---

Table 3: Compression performance in bpd on benchmarking datasets. denotes the generation performance in which the models are trained on ImageNet32 and tested on other datasets. denotes compression of high-resolution datasets with our ImageNet644trainee model.
ImageNei32
ImageNe164
CIFARIO
CLIC.mobile
CLIC.pro
DIV2K
PNG
6.39
5.71
5.87
3.90
4.00
3.09
FLIF 36
4.52
4.19
4.19
2.49
2.78
2.91
JPEG XL
6.39
5.74
5.89
2.36
2.63
2.79
L3C
4.76
4.42
2.64
2.94
3.09
RC 31
2.54
2.93
3.08
Bit-Swan 26
4.50
3,82
IDF [8]]
4.18
3,90
3.34
IDF+ 4
4.12
3.81
3.26
iVPF 41
4.03
3.75
3.20
LBB 17
3.70
3.12
iFlow (Ours)
3.88
3.70
3.12
HiLLoC [37]
4.20
3.90
3.56
IDF [8]
4.18
3.94
3.60
iVPFt 41
4.03
3.79
3.49
2.47/2.39
2.63/2.54
2.77/2.68
iFlow (Ours)
3.88
3.65
3.36
2.26/2.26*
2.45/2.44
2.60/2.57
4.2
Compression Performance
the evaluation protocols of codelength and compression bandwidth. The codelength is defined in terms of the average bits per dimension (bpd). For no compression, the bpd assumed be 8. The compression bandwidth evaluates coding efficiency, which we define in terms of symbols compressed per unit time.
For experiments,
Table 2 demonstrates the compression results on CIFARIO. Note that we only report the encoding time (results on decoding time are similar, and are available in the Appendix). For iVPF, we use settings almost identical to the original paper [41] such that 14.
Firstly, we observe that, when using both the Flow++ and iVPF architectures, iFlow achieves bpd very close to theoretically minimal codelength. When using Flow++, iFlow achieves identical performance as that of LBB. For the iVPF architecture, iFlow outperforms the underlying iVPF avoids the need to store 16 bits for each data sample.
Secondly, the coding latency highlights the main advantage of iFlow: we achieve encoding 5x faster than that of LBB and over 1.5x that of iVPF. In fact, the use of UBCS only represents 20% of the total coding time for all symbols (4.8ms in Flow++ and 1.6ms iVPF). In contrast, the rANS coder of LBB commands over 85% of the total coding latency, which is the principal cause of LBB's impracticality. Indeed, Table [ demonttrates that our UBCS coder achieves speed-up in excess of 50x that of rANS (which results in coder latency of 4.8ms in iFlow vs. 99.8ms in LBB).
Lastly, compared with LBB, iFlow necessitates fewer auxiliary bits. In fact, LBB requires crica 2k + log a bits per dimension (for = 2-* and small a in [7]). Meanwhile, iFlow requires approximately k + log S. and & log is usually small with large b.
4.3 Comparison with the State-of-the-Art
To further demonstrate the effectiveness of iFlow, we compare the compression performance on benchmarking datasets against a variety of neural compression techniques. These include, L3C [30] Bit-swap (6).. HilLoc [37]. and fow-based models IDF [18, IDF+ 4 ivPF 41 LBB [17]. We
additionally include number of conventional methods, such PNG [S. FLIF 36 and JPEG-XL 2
Experiments on Low Resolution Images. Compression results on our described selection of datasets are available in left three columns of Table 3 Here we observe that iFlow obtains improved compression performance over approaches with the exception of LBB on low-resolution images, for which achieve identical results.

---

Generalization. The last four rows in Table 3 demonstrate the peerature-standaane test of general- ization, in which ImageNet32 trained model are used for testing. From these results, is clear that iFlow achieves the best generalization performance in this test. It is worth noting that we obtain an improved performance on ImageNet64 when using our ImageNet32-trane
model.
Experiments on High Resolution Images. Finally, we test iFlow across a number of high-resolution image datasets. Here images are processed into non-overlapping 32 32 and 64 64 patches for our ImageNet32 and ImageNe164-trainee models. The right three columns in Table 3 display the results, which is observed that iFlow outperforms all compression methods across all available benchmarks. Note that as we crop patches for compression, the compression bandwidth is the same as that in small images like CIFAR10, i.e. times faster than LBB and 30% speedup compared with iVPF.
Related Work
Dynamic Entropy coders, such Arithmetic Coding (AC) [40] and Asymmetric Numerical Systems (ANS) [12]. form the basis of lossless compression. However, the binary search protocol required at decode time and their comparatively high number of numerical operations make them both relatively time-consuming. The term dynamic means that the data symbols are in different distributions, in this case, efficient entropy coders like Huffman coding [21] and tANS [22 incompatible. Our proposed UBCS is dynamic coder, which requires only two operations per symbol, producing an faster algorithm than AC and ANS.
In order to utilise entropy coders, one must estimate the data distribution. For this purpose, the wider community has employed a variety of density estimators. One of the most popular, autoregressive models (35), estimates the joint density with per- -ixel autoregressive factorizations. Whilst commonly achieving state-of-the- art compression ratios, the sequential pixel-by-pixel nature of encoding and/or decoding makes them impractically time-consume consuminn. Alternatively, variational autoencoders (VAEs) 24 26 37 maximise lower bound the marginal data likelihood (otherwise known the ELBBO). With the bits-back coding framework (38], the theoretical codelength is exactly equal to the ELBO. However, in most cases, VAE formulations typically produce inferior compression ratios there exists a gap between the ELBO and the true data likelihood.
As discussed, flow-based models 16 25 which admit exact likelihood computation, represent an alternative route for density estimation. IDF 18 and IDF++ 4 proposed the titular integer discrete flow to preserve the existence and uniqueness of invertible mapping between discrete data and latent variables. In a similar vein, iVPF [41] achieved mapping with volume- peenee--reeeriing flows. Here the remainders of division operation are stored as auxiliary states to eliminate the numerical error arising from discretizing latent variables. However, all of these models must introduce constraints on the underlying transform, limiting their representational power. LBB [17] based lossless compression approach to admit a broad class of invertible flows based on continuous transforms. LBB established this family of flexible bijections by introducing local bits-back coding techniques to encode numerical errors. However, LBB typical requires the coding of many such emrrr and does with the ANS scheme, posing obvious challenges computational efficiency.
the first flow-
Conclusions and Discussions
In this paper, we have proposed iFlow, numerically invertible flow-based model for achieving efficient lossless compression with state-of-the-art compression ratios. To achieve this, we have introduced the Modular Scale Transform and Uniform Base Conversion Systems, which jointly permit an efficient bijection between discrete data and latent variables. Experiments demonstrate that the codelength comes extremely close to the theoretically minimal value, with compression achieved much faster than the next-best high herhh-perfrrmance scheme. Moreover, iFlow is able to achieve state-of-the-at compression ratios on real-word image benchmarks.
We additionally consider the potential for extending iFlow. That is, recent advances in normalizing
flows have achieved improved generation performance across various data types [2] 7 23 We have discussed the possible extension to incorporate these advancements Sec. 2.6 and consider
its application as future work. We further recognise that compression aproaches, of which iFlow is one, present significant data privacy issues. That is, the generative model used for compression may induce data leakage; therefore, the codec should be treated carefully to observe data-privacy laws.
10

---

References
[1] Eirikur Agustsson and Radu Timofte. Núre 2017 challenge single image super-resolution: Dataset and study. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops. pages 126-135, 2017.
[2] Jyrki Alakuijala, Ruud van Asseldonk, Sami Boukortt, Martin Bruse, Iulia-Maria Comşa, Moritz Firsching. Thomas Fischbacher, Evgenii Kliuchnikov, Sebastian Gomez, Robert Obryk, et al. Jpeg xl next cext-generation image compression architecture and coding tools. In Applications of Digital Image Processing XIII, volume 11137, page 111370K. International Society for Optics and Photonics, 2019.
[3] Jens Behrmann, Paul Vicol, Kuan-Chich Wang, Roger Grosse, and Jörn- Hern-Herik Jacobsen. Understanding and mitigating exploding inverses in invertible neural networks. arXiv preprint arXiv:2006.000 09347, 2020.
[4] Rianne van den Berg, Alexey A Gritsenko, Mostafa Dehghani, Casper Kaae Sønderby, and Tim Sali- mans. Idf++ Analyzing and improving integer discrete flows for lossless compression. arXiv preprint arXiv:2006. 12459, 2020.
[5] Thomas Boutell and T Lane. Png (portable network graphies) specification version 1.0. Network Working Group, pages 1-102, 1997.
[6] Sheng Cao, Chao- Yuan Wu, and Philipp Krähenbühh. Lossless image compression through super-resolution. arXiv preprint arXiv:2004.02877 02872, 2020.
Jianfei Chen, Cheng Lu, Biqi Chenli, Jun Zhu, and Tian Tian. Vflow: More expressive generative flows with variational data augmentation. In International Conference on Machine Learning, pages 1660-1669. PMLR, 2020.
[8] Rewon Child. Very deep vaes generalize autoregressive models and can outperform them on images. arXiv preprint arXiv:201 I. 10650, 2020.
[9] Yann Collet and Chip Turner. Smaller and faster data compression with zstandard. Facebook Code [online 2016.
[10] Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components estimation. arXiv preprint 0rXiv:/410.885 2014.
[11] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv preprint arXiv:1605.000 160.00880., 2016.
[12] Jarek Duda. Asymmetric numeral systems: entropy coding combining speed of huffiman coding with compression rate of arithmetic coding, arXiv preprint arXiv:1311.2544 2013.
[13] GMDT Forecast. Cisco visual networking index: global mobile data traffic forecast update, 2018-2023. Update, 2018:2023, 2010.
[14] Philip Gage. new algorithm for data compression. C Users Journal, 12(2):23 38, 1994.
[15] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerehner. beta-vae: Learning basic visual concepts with constrained variational framework. 2016.
[16] Jonathan Ho, Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel. Flow++: Improving flow-based gen- erative models with variational dequantizatiin and architecture design. arXiv preprint arXiv:1902.000 1902.00255 2019.
[17] Jonathan Ho, Evan Lohn, and Pieter Abbeel. Compression with flows via local bits-back coding. In Advances in Neural Information Processing Systems, pages 3879-3888, 2019.
[18] Emiel Hoogeboom, Jom Peters, Rianne den Berg, and Max Welling. Integer discrete flows and lossless compression. Advances Neural Information Processing Systems, pages 22134-12144 2019.
[19] Emiel Hoogeboom, Taco Cohen, Jakub Tomezak. Learning discrete distributions by dequantization. arXiv preprint 200i:2001.112333 2020.
[20] Chin Chin-Wei Huang, David Krueger, Alexandre Lacoste, and Aaron Courville. Neural autoregressive flows. In Proceedings of the 35th International Conference on Machine Learning. volume 80, pages PMLR, 2018
11

---

[21] David A Huffiman. A method for the construction of minimun-redundanee codes. Proceedings of the IRE. 1019):1098-1100 1952.
[22] Heewoo Jun, Rewon Child, Mark Chen, John Schulman, Aditya Ramesh, Alec Radford, and Ilya Sutskever. Distribution augmentation for generative modeling. In International Conference on Machine Learning. pages 5006-5019, PMLR, 2020.
[23] Hyeongju Kim, Hyeonseung Lee, Woo Hyun Kang. Joun Yeop Lee, and Nam Soo Kim. Softflow: Probabilistte framework for normalizing flow on manifolds. Advances Neural Information Processing Systems, 33, 2020.
[24] Diederik Kingma and Max Welling, Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 2013.
[25] Durk Kingma and Prafulla Dhariwal. Glow: Advances in neural information processing systems, pages 10224- 2018.
Generative flow with invertible Ixl convolutions. In
[26] Friso Н Kingma, Pieter Abbeel, and Jonathan Ho. Bit-swap: Recursive bits-back coding for lossless compression with hierarchical latent variables. arXiv preprint 105.0:1905.06855, 2019.
[27] Manoj Kumar, Mohammad Babaeizadeh, Dumitru Erhan, Chelsea Finn, Sergey Levine, Laurent Dinh, and Durk Kingma. Videoflow: A flow-based generative model for video. arXiv preprint arXiv:1903.0144
(5), 2019.
[28] Phillip Lippe and Efstratios Gavves. Categorical normalizing flows via continuous transformations. arXiv preprint arXiv:2006. 09790, 2020.
[29] David JC MacKay and David JC Mac Kay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
[30] Fabian Mentzer, Firikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Practical full resolution learned lossless image compression. In Proceedings of the IEEE Conference on Computer Vision and Patiern Recognition, pages 10629-10638... 2019.
[31] Fabian Mentzer, Luc Van Gool, and Michael Tschannen. compression. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 6638 6647, 2020.
Learning better lossless compression using lossy
[32] Ryan Prenger, Rafael Valle, and Bryan Catanzaro. Waveglow: A flow-based generative network for speech synthesis. In ICASSP 2019-2019 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3617-3621, IEEE, 2019.
[33] Majid Rabbani. Jpeg2000; Image compression fundamentals, standards and practice. Journal of Electronic Imaging, (12))286, 2002.
[34] Greg Reelofs and Richard Koman. PNG: the definitive guide. O'Reilly Associates, Inc., 1999.
[35] Tim Salimans, Andrej Karpathy. Xi Chen, and Diederik P Kingma. Pixelenn++: Improving the pixelenn with discretized logistic mixture likelihood and other modifications. arXiv preprint arXiv:1701.05517.
2017.
[36] Jon Sneyers and Pieter Wuille. Flif: Free lossless image format based on maniac compression. 2016 IEEE International Conference on Image Processing (ICIP), pages 66-70. IEEE, 2016.
[37] James Townsend, Thomas Bird, Julius Kunze, and David Barber. Hilloc: Lossless image compression with hierarchical latent variable models. arXiv preprint 19Xiv:I912.0900 2019.
[38] James Townsend, Tom Bird, and David Barber. Practical lossless compression with latent variables using bits back coding. arXiv preprint 3XXX::9901.04866 2019.
[39] Aaron Van den Oord, Nal Kalchbrenner, Lasse Espeholt, Oriol Vinyals, Alex Graves, et al. Conditional image generation with pixelenn decoders. In Advances in neural information processing systems, pages 4790-4798. 4798, 2016.
[40] Ian H Witten, Radford M Neal, and John G Cleary. Arithmetic coding for data compression. Communica- tions of the ACM, 30(6):50--540, 1987.
[41] Shifeng Zhang, Chen Zhang, Ning Kang, and Zhenguo Li. ivpf: Numerical invertible volume preserving flow for efficient lossless compression. arXiv preprint arXiv:2103.16211, 2021.
2021.
12


Reviews:
[{"review_id": "zKiSf7Ay2W", "reviewer": "Reviewer_EPj6", "summary": "This paper proposes iFlow - a method to improve lossless compression using flow-based generative models. Specifically, the paper proposes two novel methods, the Modular Scale Transform (MST) and Uniform Base Conversion Systems (UBCS). MST is a method of obtaining a numerically invertible scale transform, to be used as a building block for flow layers. UBCS is a codec for uniformly distributed symbols, designed for speed.\n\nThe authors demonstrate that the MST results in superior bitrates when compared to similar techniques, and that UBCS is faster for coding uniform symbols than competing entropy codecs.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The results in this work appear to be quite interesting. There does appear to be an advance in coding rate and compression speed for lossless compression using flow models (or even any probabilistic generative model, since flow models are currently the SOTA). The realisation that the majority of the coding can be done via uniformly distributed symbols is neat, and then showing that a simple codec (UBCS) can code these close to the Shannon entropy much faster than a modern codec like rANS is I think an important realisation. This could potentially have important ramifications for the field of learned lossless compression as previous works have not utilised this. For example [1] uses a uniform codec for the latents since a Gaussian is discretised into buckets of uniform probability. They use rANS for the coding though, which appears not to be optimal in terms of speed.\n\nThis work is in general well-written and precise in its statements. Results are given clearly and theorems and motivations are well laid out.\n\nThe concern I have with this work is that it is extremely close in content to [2]. [2] is a recent paper but it is cited and clearly built upon in this work. One of the major contributions of this work is the MST, which the authors admit is inspired by MAT (just changing affine to scalar) from [2]. They look very similar to me, and although the schemes are clearly slightly different I can't quite work out why MST is superior, and it doesn't seem to be stated in this paper. Could the authors comment and make clear exactly why MST is an iteration over MAT?\n\nMuch like in [2], after describing the MST, time is then taken to show that various flow compression schemes can be implemented using these numerically invertible flows. It doesn't appear that much has changed between these derivations.\n\nUBCS is still a novelty, but it is in someways quite a simple revelation - we can code uniform symbols fast. The codec itself is straightforward. This is not a bad thing, but with the rest of the paper being very closely related to another work, it does detract from the overall novelty somewhat.\n\nIf the authors addressed exactly the motivation for MST over MAT then I consider upgrading my score.\n\nEdit: after response I am upgrading my score as per the above.\n\n[1] Practical Lossless Compression with Latent Variables using Bits Back Coding\nJames Townsend, Tom Bird, David Barber\nICLR 2019\n\n[2] iVPF: Numerical Invertible Volume Preserving Flow for Efficient Lossless Compression\nShifeng Zhang, Chen Zhang, Ning Kang, Zhenguo Li\nCVPR 2021\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have addressed the limitations. I don't see any negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't see any ethical concerns with this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "k7cAHstGwkI", "reviewer": "Reviewer_PoNo", "summary": "The paper performs lossless image compression with invertible flows. The authors propose a way to convert flows to be numerically invertible, and a coder for uniform distributions.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I'm reviewing this paper from a compression perspective. I know the invertible flow literature on a high level only. With that in mind, the idea that is used to convert flows makes sense, and is novel as far as I know. I like the formulation of the paper, it is concise but understandable.\n\nMy main concern is that I do not understand the point and/or novelty of the proposed \"Uniform Base Conversion System\". I have two concerns:\n- [Update: addressed by rebuttal] Are we using UBCS also to encoding the final $z$? It seems suboptimal to assume $z\\sim U$. Could you elaborate on the distribution used for z? If it's not uniform, what coder do you use?\n- [Update: addressed by rebuttal]  The goal is to compress symbols that are uniformly distributed according to $U(0, R)$. To me it seems many of the existing algorithms should be fast if adapted to this assumption. In particular, if there exists an $r$ such that $R=2^r$, you can write a simple algorithm in C that does not use any multiplication, just bitshifts and additions, that should be blazingly fast. For other $R$, I'm sure that the tabled variant of ANS, tANS, should also allow for very fast encoding and decodings, as it also does not use any multiplications -- in contrast to the presented algorithm. It seems unfair to compare to a particular implementation of rANS. Overall, this is maybe a nit-picky point, as the proposed variant is faster than the compared rANS, but it just seems that with a bit more tinkering, an even much faster variant could have been found. In light of what exists, claims of novelty should probably be toned down. Also, L293, \"... binary search protocol required at decode time ...\" seems unfair, as AC can trivially be adapted to use a lookup table for fixed uniform distributions.\n\nGiven the comments on improved/practical speed in the Introduction, I would have liked to see a table with runtimes on full-resolution datasets such as CLIC.pro.\n\nMinor comments:\n- L82: why is a triple equality used.\n- L85: Footnote could be inlined. \n- L185 could use a restatement of $\\delta$ and $-\\log \\delta = kd$", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper addresses this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Zqp9VmzvTwe", "reviewer": "Reviewer_hYZr", "summary": "The two key contributions in this work are:\n\n1) A construction method for low-error discretized approximations to a wide class of continuous normalizing flow layers\n2) An entropy coding method the discrete uniform distribution that the authors call Uniform Base Conversion Systems (UBCS) that is simple to implement and is very fast.\n\nThe authors combine these two contributions in their experiments and achieve state-of-the-art compression ratios on the standard lossless image compression benchmark datasets (ImageNet, Cifar10, CLIC, DIV2K), while also achieving large gains in terms of compression speed compared to other methods.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "# Strengths\nThere are several novel ideas presented in the paper. The modular scale transform (MST) is simple, easy to implement and the authors show using some results from [1] that it has desirable properties. Then, the authors show how MST can be used as the fundamental building block for discrete approximations of general elementwise flows which then leads to autoregressive and 1 x 1 convolutional flows, the correctness and efficiency of which is all guaranteed by the correctness and efficiency of MST.\n\nThe authors adopt some ideas from [2] to remove the overhead introduced by the quantization mesh and call it bits-back dequantization.\nThe authors introduce Uniform Base Conversion Systems (UBCS). While a very simple scheme, it is very fast and just the right entropy coding method to use in conjunction with the discrete flow approximation proposed by the authors.\n\nThe experimental method in this work is standard for learned lossless image compression, and the authors achieve very good results on all considered datasets. Concretely, they match or slightly improve the current state-of-the-art compression performance on all datasets, while achieving a large improvement in terms of run-time compared to other methods.\n\nThe paper is well-written with a logical and easy-to-follow layout. Nice submission overall.\n\n[1] Shifeng Zhang, Chen Zhang, Ning Kang, and Zhenguo Li. iVPF: Numerical invertible volume preserving flow for efficient lossless compression. arXiv 2021\n\n[2] Jonathan Ho, Evan Lohn, and Pieter Abbeel. Compression with flows via local bits-back coding. NeurIPS 2019\n\n# Weaknesses\nThere are no major weaknesses that I could spot. There are some minor issues, concretely:\n- In the abstract it says \"We first develop UBCS, ...\", but in fact it is developed after the introduction of iFlow.\n- On several occasions (e.g. in Algorithms 1 and 4) the authors mention \"decoding\" an object from a distribution.\n  I believe that the authors here refer to the fact that entropy coding methods can be viewed as \"invertible samplers\",\n  where \"decoding\" can be identified with sampling the probability distribution at hand using the currently available bit stream.\n  I don't think this is clarified anywhere in the main text, and I also don't think that this is common terminology in the wider community. Therefore I would suggest that the authors either clarify it or change their wording.\n- Footnote 2: I think the language used is imprecise, I think the authors mean that the intervals must _partition_ the domain of $f$.\n- Could the authors clarify what the relevance of Eq (4) is? Is it to show that $R$ in the MST implementation of Eq (3) will have the appropriate magnitude so that Prop (2) holds?\n- Line 59: \"Jacabian matrix\"\n- Line 115: subscript of $z$ in $\\bar{z}_l = f(\\bar{x}_h)$ should be $h$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "MywKJa6hZOR", "reviewer": "Reviewer_Z7Bx", "summary": "This paper proposes a lossless image compression method based on normalizing flows. In order for this class of flows to be useful for compression, they need to be working in the quantized domain, and (of course) have to be invertible. The authors present an extension to a much more general class of functions that can be used in the composition formulation of the flow, therefore being able to achieve higher rates of compression than what was possible before. Additional contributions include using a variant of bits-back coding to achieve higher compression rates, and a much faster entropy coding method that vastly outperforms rANS.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper could be the start of a many more papers using flows for compression. Thus far there are very few papers published in this area that use normalizing flows due to the very challenging nature of the problem. The key blocking factor that this paper addresses is how to use more general composable functions than what was possible before (which were very weak functions). This improvement might make this paper a turning point in utilization of this class of methods.\n\nWhile I did try to do my best to understand the entirety of the paper, I did not follow the proofs closely as I am not super-familiar with the vast amount of background knowledge needed to understand methods ranging from flows, which I am familiar with, to entropy coding and bits-back coding (which I am much less familiar with). I budgeted about 3 hours for this paper, and it was really not enough to get fully up to speed with everything needed here. \n\nWith that said, the main body of the paper was very clearly written, and I wish more papers were as well written as this one. The supplementary materials contain a vast amount of proofs, and I think this is very welcomed given the vast quantity of information presented in this work.\n\nThe results are state o the art, and the only criticism I can find is that the decoding/encoding time is only listed for toy problems. With that said, the number of baselines, including state of the art classical codecs is very impressive and very welcomed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This looks ok.", "review_text": "", "extra_scores": {"ethical_concerns": "No issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "F81JtsUpTIX", "reviewer": "Reviewer_BnZR", "summary": "The paper introduces a new normalizing flow method for lossless compression. The key innovation is a new family of techniques to convert a continuous flow into a discrete bijector, which can transform binary codes without information loss. The authors compare compression performance and encoding speed with a large family of state-of-the-art neural compression methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The authors introduce a method to convert normalizing flows into discrete bijectors that can be used for lossless compression. This allows for the use of a trained continuous flow for lossless compression without lossy quantization of the encoded latent code. Specifically, the authors introduce the \"modular scale transform\", which approximate element-wise scalar multiplications with integer multiplications and divisions plus a remainder that is encoded separately and follows a uniform distribution. \n\nI premise that my expertise in the area is limited. So said, the work seems to be solid and the theoretical results straightforward. The main innovation is the modular scale transform, which is a very simple trick. This simplicity however is not necessarily a problem as far as the innovation is original. In the following, I will list the main strengths and weaknesses of the paper. \n\nStrengths:\n- The main innovation is simple and elegant and has a wide applicability. The modular scale transform is used to approximate arbitrary monotonic transformation through locally-linear approximations and then complex normalizing flow layers using a similar approach.\n- The experiments are performed on a rather large number of datasets and comparison are made with a large number of relevant baselines.\n\nWeakness:\n- The main contribution is a very simple trick. Given that the field is young, I can image that it is original. However, it is possible that a very similar method is already in wide use in a related literature. Given my scarce familiarity with the compression literature, I trust the judgment of the other reviewers on this matter. \n- The experiments are difficult to interpret as the authors do not provide error bars on their result. I suggest to use a bootstrap technique in order to quantify the statistical variability of the performance.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and social impact are  discussed, albeit briefly.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main concerns by the reviewers were adequately addressed during the rebuttal and subsequent discussion between the authors and reviewers. The reviewers unanimously vote for accepting this paper. 

The metareviewer sincerely thanks the authors and reviewers for engaging into fruitful discussions.
Decision: Accept (Spotlight)