iFlow: Numerically Invertible Flows for Efficient Lossless Compression via a Uniform Coder
Year: 2022

Abstract:
It was estimated that the world produced 59ZB (5.9× 10GB) 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 socalled "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× 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.

heading: 1 Introduction
text: The volume of data, measured in terms of IP traffic, is currently witnessing an exponential yearon-year growth [13]. Consequently, the cost of transmitting and storing data is rapidly becoming prohibitive for service providers, such as cloud and streaming platforms. These challenges increasingly necessitate the need for the development of high-performance lossless compression codecs.
One promising solution to this problem has been the development of a new class of so-called “neural compression” algorithms [30, 38, 18, 4, 17, 37, 26, 31, 6, 41]. These methods typically posit a deep probabilistic model of the data distribution, which, in combination with entropy coders, can be used to compress data with the minimal codelength bounded by the negative log-likelihood [29]. 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 on developing approaches with deep probabilistic models based on normalizing flows [11, 25, 32, 27, 7, 28, 23]. A normalizing flow admits a learnable bijective mapping between input data and a latent variable representation. In this paradigm, inputs can be compressed by first transforming data to latent variables, with the resulting output encoded by a 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, 15, 8]) and inference speed (as compared with autoregressive factorizations [35, 39, 22]). This suggests that compression with flows can jointly achieve high compression ratios along with fast coding times.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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, 3]. To resolve this issue, Integer Discrete Flows (IDF) [18, 4] (Fig. 1, left) proposed an invertible mapping between discrete data and latent variables. Similarly, iVPF [41] achieves a discrete-space bijection using volume-preserving flows. However, the above models must introduce constraints on flow layers to ensure a discretespace bijection, which limits the expressivity of the transformation. Local Bits-Back Coding (LBB) [17] (Fig. 1, middle) was the first approach to succeed in lossless coding with the flexible family of continuous flows. It resolves the information loss by coding numerical errors with the rANS coder [12]. However, the coder is 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 a flexible family of bijections in discrete space, deriving an invertible class of flows suitable for lossless compression. UBCS, built on the uniform distribution, permits a highly efficient entropy coding compatible with MST. The main ideas are illustrated in Fig. 1(right). We test our approach across a range of image datasets against both traditional and neural compression techniques. Experimentally we demonstrate that our method achieves state-of-the-art compression ratios, with coding time 5× quicker than that of the next-best scheme, LBB.

heading: 2 Numerically Invertible Flows and Lossless Compression
text: Let f : X → Z be our normalizing flow, which we build as a composition of layers such that f = fL ◦ ... ◦ f2 ◦ f1. Defining d-dimensional y0 = x ∈ X and yL = z ∈ Z , the latents can be computed as yl = fl(yl−1), with pX(x) calculated according to
log pX(x) = log pZ(z) + L∑ l=1 log |det Jfl(yl−1)|, (1)
where Jfl(x) is the Jocabian matrix of the transformation fl at yl−1. In this paper, we use log to denote base 2 logarithms. Training the flow should minimize the negative log-likelihood− log pX(x). The inverse flow is defined as f−1 = f−11 ◦ ... ◦ f −1 L , such that f
−1(z) = x. There are many types of invertible bijections, fl. Popular choices include element-wise, autoregressive (e.g. coupling layers) [41] and 1× 1 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 z must be discrete, with a bijection between discrete inputs and outputs
established. However, as 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 an exact bijiective mapping between discrete x and discrete z. We present the general idea of a flow layer’s numerical invertibility in discrete space in Sec. 2.1. We then introduce our flow layers in Sec. 2.2 and 2.3, with their application to compression discussed in Sec. 2.4 and 2.5.

heading: 2.1 Invertibility of Flows in Discrete Space
text: To discretize the data, we follow [41] and adopt k-precision quantization to assign floating points to discretization bins such that
x̄ = b2k · xc
2k , (2)
where b·c is the floor function. The associated quantization error is bounded by |x̄− x| < 2−k. Any d-dimensional x can be quantized into bins with volume δ = 2−kd. The probability mass of x̄ can then be approximated by P (x̄) = p(x̄)δ, such that the theoretical codelength is − log(p(x̄)δ). Denote our proposed numerically invertible flow (iFlow) according to f̄ = f̄L ◦ ... ◦ f̄1. The input and output should be subject to k-precision quantization, where each layer should be appropriately invertible such that ȳl−1 ≡ f̄−1l (f̄l(ȳl−1)). Denoting ȳ0 = x and z̄ = ȳL, it is further expected that z̄ = f̄(x) and x ≡ f̄−1(z̄). We will show in the following subsections that f̄ can be derived from any continuous flow f in such a way that the error between f̄(x) and f(x) is negligible.

heading: 2.2 Numerically Invertible Element-Wise Flows
text: We begin by describing our approach for element-wise flows z = f(x), where f is a monotonic element-wise transformation. For notation simplicity, we assume that the flow contains just one layer. In most cases, f does not present a unique inverse in discrete space, such that f−1(z̄) 6= x. 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 a continuous flow as x and z = f(x); and we denote the k-precision quantized input-output pairs of iFlow as x̄ and z̄ = f̄(x̄).

heading: 2.2.1 Scale Flow
text: Algorithm 1 Modular Scale Transform (MST): Numerically Invertible Scale Flow f(x) = R/S · x. Forward MST: z̄ = f̄(x̄). 1: x̂← 2k · x̄; 2: Decode rd using U(0, R); ŷ ← R · x̂+ rd; 3: ẑ ← bŷ/Sc, re ← ŷ mod S; 4: Encode re using U(0, S); 5: return z̄ ← ẑ/2k. Inverse MST: x̄ = f̄−1(z̄). 1: ẑ ← 2k · z̄; 2: Decode re using U(0, S); ŷ ← S · ẑ + re; 3: x̂← bŷ/Rc, rd ← ŷ mod R; 4: Encode rd using U(0, R); 5: return x̄← x̂/2k.
We begin with the scale transformation defined as z = f(x) = a · x, (a > 0), from which we are able to build more complex flow layers. The input can be converted to an integer with x̂ = 2k · x̄, and the latent variable z̄ can be recovered from integer ẑ by z̄ = ẑ/2k. Inspired by MAT in iVPF [41], we first approximate a with a fractional such that a ≈ RS , where R,S ∈ N. Denote ŷ = R · x̂+ rd where rd is sampled uniformly from {0, 1, ..., R− 1}, we can obtain ẑ with ẑ = bŷ/Sc, and the remainder re = ŷ mod R can be encoded to eliminate the error. It is clear that (x̂, rd) ↔ ŷ ↔ (ẑ, re) are bijections.
Let U(0, A) be the uniform distribution such that P (s) = 1A , s ∈ {0, 1, ..., A− 1}. The numerically invertible scale flow f̄ is displayed in Alg. 1. As the modular operation is essential to Alg. 1, we name it the Modular Scale Transform (MST). Setting S andR = round(S ·a) to be large, we observe that the following propositions hold. Proposition 1. [41] |z̄ − f(x̄)| < O(S−1, 2−k). Proposition 2. The codelength of MST is Lf (x̄, z̄) = logS − logR ≈ − log |a| = − log |f ′(x̄)|.
Proposition 1 establishes that the error is small if S and k are large. Proposition 2 demonstrates that the codelength is 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 operation in iVPF [41] only deals with volume-preserving affine transform and is performed sequentially along dimensions, limiting its usage and efficiency.

heading: 2.2.2 General Element-wise Flow
text: Algorithm 2 Numerically Invertible Element-wise Flows
Forward: z̄ = f̄(x̄). 1: Get x̄l, x̄h, z̄l, z̄h given x̄, so that x̄ ∈ [x̄l, x̄h); 2: Set large S; get R with Eq. (4); x̄′ ← x̄− x̄l; 3: Get z̄′ with forward MST in Alg. 1, given input x̄′
and coefficients R,S; 4: return z̄ = z̄′ + z̄l. . z̄ ∈ [z̄l, z̄h).
Inverse: x̄ = f̄−1(z̄). 1: Get x̄l, x̄h, z̄l, z̄h given z̄, so that z̄ ∈ [z̄l, z̄h); 2: Set large S; get R with Eq. (4); z̄′ ← z̄ − z̄l; 3: Get x̄′ with inverse MST in Alg. 1, given input z̄′
and coefficients R,S; 4: return x̄ = x̄′ + x̄l. . x̄ ∈ [x̄l, x̄h).
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. 1 works with linear transformations, and is incompatible with non-linear functions. Motivated by linear interpolation, we can approximate the non-linear flow with a piecewise linear function. In general, consider input x̄ to be within an interval x̄ ∈ [x̄l, x̄h)1 and z̄l = f(x̄l), z̄h = f(x̄h). The linear interpolation of f is then
finp(x) = z̄h − z̄l x̄h − x̄l (x̄− x̄l) + z̄l. (3)
It follows that z̄ can be derived from MST with input x̄−x̄l followed by adding z̄l. Furthermore, z̄ and x̄ can be recovered with the corresponding inverse transformation. To preserve monotonicity, z̄ must be within interval z̄ ∈ [z̄l, z̄h). Denoting the invertible linear flow derived from finp as f̄inp, it must hold that f̄inp(x̄l) ≥ z̄l, f̄inp(x̄h−2−k) ≤ z̄h−2−k. As we use MST in Alg. 1, we observe that when z̄h−z̄l x̄h−x̄l is approximated withR/S, the minimum possible value of f̄inp(x̄l) is z̄l (when rd = 0 in Line 2) and the maximum possible value of f̄inp(x̄h−2−k) is b(R·2k(x̄h−x̄l−2−k)+R−1)/(S ·2k)c+z̄l (when rd = R− 1 in Line 2). Given large S, the largest possible value of R should be
R = ⌊ (2k · (z̄h − z̄l)− 1) · S + 1 2k · (x̄h − x̄l) ⌋ . (4)
Another difficulty is in determining the correct interpolation interval [x̄l, x̄h). One simple solution is to split the input domain into uniform intervals with length 2−h such that x̄l = b(2h · x̄)/2hc, x̄h = x̄l + 2
−h. However, for the inverse computation given z̄, it is not easy to recover the interpolation interval as f−1(z̄) may not be within [x̄l, x̄h). Instead, as z̄ ∈ [z̄h, z̄l), the interval [x̄l, x̄h) can be obtained via a binary search in which x̄l is obtained with z̄ ∈ [f(x̄l), f(x̄h)). Another approach is to split the co-domain into uniform intervals such that z̄l = b(2h · z̄)/2hc, z̄h = z̄l + 2−h, with x̄l = f−1(z̄l), x̄h = f−1(z̄h). In this case, determining [z̄l, z̄h) during the inverse computation is simple. While for the forward pass, [z̄l, z̄h) should be determined with a binary search such that x̄ ∈ [f−1(z̄l), f−1(z̄h)). In practice, we have simpler tricks to determine the correct interval [x̄l, x̄h), [z̄l, x̄h) 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. 2 can be used in any element-wise flow including linear flow. In Alg. 2, Proposition 2 holds such that Lf (x̄, z̄) = − log(R/S) ≈ − log z̄h−z̄lx̄h−x̄l ≈ − log |f
′(x̄)|. It is possible to arrive at a similar conclusion in Proposition 1 where the corresponding error is |z̄ − f(x̄)| < O(S−1, 2−k, 2−2h).
1All intervals must partition the domain of f .

heading: 2.3 Practical Numerically Invertible Flow Layers
text: 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 [20] (including coupling flows [10, 11, 16]) and 1× 1 convolutional flows [25].

heading: 2.3.1 Autoregressive and Coupling Flows
text: Algorithm 3 Numerically Invertible Autoregressive Flow
Forward: z̄ = f̄(x̄). 1: for i = m, ..., 1 do 2: z̄i ← f̄i(x̄i, x̄<i) with Alg. 2 (forward); 3: end for 4: return z̄ = [z̄1, ..., z̄m]>.
Inverse: x̄ = f̄−1(z̄). 1: for i = 1, ...,m do 2: x̄i ← f̄−1i (z̄i, x̄<i) with Alg. 2 (inverse); 3: end for 4: return z̄ = [z̄1, ..., z̄m]>.
Supposing that the inputs and outputs, x and z, are split into m parts x = [x1, ...,xm]>, z = [z1, ..., zm]
>, the autoregressive flow z = f(x) can be represented as zi = fi(xi; x<i), where fi(·; x<i) is the element-wise flow (discussed in Sec. 2.2), conditioned on x<i. Now let f̄i(·; x<i) denote the invertible element-wise flow transformation as discussed in Alg. 1-2. Alg. 3 then illustrates the details of an invertible autoregressive flow f̄ .
Propositions 1 and 2 hold in our discretized autoregressive transformation. In fact, the log-determinant of Jacobian is given by log |det Jf (x)| = ∑m i=1 log |det Jfi(xi; x<i)|, and the expected codelength
is simply Lf (x̄, z̄) = ∑m i=1 Lf (x̄i, z̄i) ≈ − ∑m
i=1 log |det Jfi(x̄i; x̄<i)| = − log |det Jf (x̄)|. When m = 2 and f1(x1) = x1, the autoregressive flow is reduced to a coupling flow, which is widely used in flow-based models [10, 11, 16]. It is therefore trivially clear that the coupling flow is additionally compatible with Alg. 3.

heading: 2.3.2 1× 1 Convolutional Flow
text: 1× 1 convolutional layers can be viewed as a matrix multiplication along a channel dimension [25]. Let x̄, z̄ ∈ Rc be inputs and outputs along channels, and W ∈ Rc×c the weights of our network. The objective is to obtain z̄ = f̄(x̄) where f(x) = Wx.
We use the ideas of iVPF [41] to achieve a numerically invertible 1× 1 convolutional transformation. In particular, we begin by performing an LU decomposition such that W = PLΛU. It then follows that the 1× 1 convolution is performed with successive matrix multiplications with U,Λ,L and P. In iVPF, the authors extensively discussed matrix multiplications with factors U,L and P [41]. Meanwhile, one can view the matrix multiplication with Λ as a scale transform, such that f(x) = λ x, where is an element-wise multiplication and λ are the diagonal elements of Λ. MST in Alg. 1 can then be applied. In such a case, it is clear that Proposition 1 and 2 hold for a 1 × 1 convolutional flow. For Proposition 2, it is observed that Lf (x̄, z̄) ≈ −sum(logλ) = − log |det Λ| = − log |det W| = − log |det Jf (x̄)|.

heading: 2.4 Building Numerically Invertible Flows
text: Our flow model is constructed as a composition of layers f = fL ◦ ... ◦ f2 ◦ f1, where each layer is a transformation of the type discussed in Sec. 2.2 and 2.3. Let us represent the resulting flow as f̄ = f̄L ◦ ... ◦ f̄1, where f̄l is a discretized transformation derived from the corresponding continuous f . It is clear that the quantized input x̄(= ȳ0) and latent z̄(= ȳL) establish a bijection with successive transformations between discrete inputs and outputs. For the forward pass, z̄ is computed with ȳl = f̄(ȳl−1), l = 1, 2, ..., L; for the inverse pass, x̄ is recovered with the inverse flow f̄−1 = f̄−11 ◦ ... ◦ f̄ −1 L such that ȳl−1 = f −1 l (ȳl).
For our resultant flow model, we can draw similar conclusions as in Propositions 1 and 2. Firstly, the error of z̄ = f̄(x̄) and z = f(x̄) is small, bounded by |z̄− z| < O(LS−1, L2−k, L2−2h). Secondly, the codelength is approximately Lf (x̄, z̄) = ∑L l=1 Lfl(ȳl−1, ȳl) ≈ − ∑L l=1 log |det Jfl(ȳl−1)|.

heading: 2.5 Lossless Compression with Flows via Bits-back Dequantization
text: 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̄)δ. For the decoding process, z̄ is decoded with pZ(z̄)δ, and x̄ is recovered with f̄−1(z̄). The expected codelength is approximately − log(pX(x̄)δ) such that
L(x̄) ≈ − log(pZ(z̄)δ)− L∑
l=1
log |det Jfl(ȳl−1)| ≈ − log(pX(x̄)δ). (5)
However, we note that if k is large, − log δ = kd and the codelengths will also be large, resulting in a 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◦ ∈ Zd, where a k-precision noise vector ū ∈ [0, 1)d is decoded with q(ū|x◦)δ 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. 4.
Algorithm 4 Lossless Compression with iFlow.
Encode x◦. 1: Decode ū using q(ū|x◦)δ; 2: z̄← f̄(x◦ + ū); 3: Encode z̄ using pZ(z̄)δ.
Decode. 1: Decode z̄ using pZ(z̄)δ; 2: x̄← f̄−1(z̄),x◦ ← bx̄c; 3: Encode ū = x̄− x◦ using q(ū|x◦)δ; 4: return x◦.
In practice, q(u|x◦) is constructed with a flow model such that u = g( ; x◦) where ∼ p( ). ū is decoded by first decoding ̄ with p(̄)δ, and then applying ū = ḡ(̄; x◦). Thus decoding ū involves − log(q(ū|x◦)δ) bits. Overall, the expected codelength is exactly the dequantization lower bound [19] such that
L(x◦) ≈ ∑ ū q(ū|x◦)δ[log(q(ū|x◦)δ)− log(p(x◦ + ū)δ)]
≈ Eq(ū|x◦)[log q(ū|x◦)− log p(x◦ + ū)]. (6)

heading: 2.6 Extensions
text: With novel modifications, flow models can be applied to the generation of various data types, obtaining superior performance [7, 28, 23]. These models can be used for improved lossless compression. In general, given input data x◦, these models generate intermediate data v with q(v|x◦), and the density of v is modelled with flow model z = f(v). For generation, when v is generated with the inverse flow, x is generated with p(x◦|v). It is clear that p(x) can be estimated with variational lower bound such that log p(x◦) ≥ Eq(v|x◦)[logP (x◦|v) + 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 q(v̄|x◦)δ and then encode x◦ with P (x◦|v̄) (similar with Line 1 in Alg. 4-Encode). We then obtain the prior z̄ = f̄(v̄) (Line 2), before finally encoding z̄ with pZ(z̄)δ (Line 3). In the decoding process, z̄ is firstly decoded with pZ(z̄)δ (similar to Line 1 in Alg. 4-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
L(x◦) ≈ Eq(v̄|x◦)[log q(v̄|x◦)− logP (x◦|v̄)− log p(v̄)]. (7)
We introduce a selection of recent, state-of-the-art flow-based models modified according to the above. Each model corresponds to a certain coding algorithm.
VFlow [7]. VFlow expands the input data dimension with variational data augmentation to resolve the bottleneck problem in the flow model. In VFlow, v = [x◦ + u, r](u ∈ [0, 1)d), where u ∼
qu(u|x◦), r ∼ qr(r|x◦+u), is modelled with flows gu, gr such that u = gu( u; x◦), r = gr( r; x◦+ u) ( u, r are priors). Then we have q(v|x◦) = qu(u|x◦)qr(r|x◦ + u), P (x◦|v) = 1 (as v → (x◦ + u) → x◦). Thus for the encoding process, ̄u, ̄r are decoded. To construct v̄ we have ū = ḡu(̄u; x ◦), r̄ = ḡr(̄r; x ◦ + ū); and then v̄ is encoded with iFlow. For the decoding process, v̄ is decoded with the inverse iFlow, and then x◦, ū, r̄ is recovered with v̄. Here ū, r̄ is encoded and x◦ is the decoded output. As VFlow achieves better generation results compared with general flows, one would expect a better compression ratio with VFlow.
Categorical Normalizing Flow [28]. Categorical Normalizing Flows (CNF) succeed in modelling categorical data such as text, graphs, etc. Given categorical data x◦ = [x1, ..., xn], xi ∈ {1, 2, ..., C}n, v = [v1, ...,vn] is represented with word embeddings such that q(vi|xi) = qe(vi|µ(xi),σ(xi)), in which qe could be a Gaussian or logistic distribution. Then P (xi|vi) = p̃(xi)q(vi|xi)∑C c=1 p̃(c)q(vi|c) with p̃ being the prior over categories. Thus q(v|x◦) = ∏n
i=1 q(vi|xi), P (x◦|v) =∏n i=1 P (xi|vi), and x◦ can be coded with Alg. 8 given q(v|x◦), P (x◦|v) and the iFlow.

heading: 3 Uniform Base Conversion Systems
text: Algorithm 5 Uniform Base Conversion Systems
ENCODE s using U(0, R)(R < 2K). Input: symbol s, state c, bit-stream bs. Output: new state c and bit-stream bs. 1: c← c ·R+ s; 2: if c ≥ 2M+K then 3: bs.push_back(c mod 2K); . push K
bits to bit-stream. 4: c← b c
2K c;
5: end if 6: return c, bs.
DECODE with U(0, R)(R < 2K). Input: state c, bit-stream bs. Output: decoded s, new state c and bit-stream bs. 1: if c < 2M ·R then 2: c ← 2K · c+bs.pop_back(); . get last
K bits from bit-stream and pop them. 3: end if 4: s← c mod R; 5: c← bc/Rc; 6: return s, 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 is expected. Compared to the Gaussian distribution used in LBB [17], a 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 a number-base conversion. The code state c is represented as an integer. For coding some symbol s ∈ {0, 1, ..., R− 1} with a uniform distribution U(0, R), the new state c′ is obtained by converting an R-base digit s to an integer such that
c′ = E(c, s) = c ·R+ s. (8)
For decoding with U(0, R), given state c′, the symbol s and state c are recovered by converting the integer to an R-base digit such that
s = c′ mod R, c = D(c′, s) = b c ′
R c. (9)
We note, however, that c will become large when more symbols are encoded, and computing Eq. (8-9) with large c will be inefficient. Similar to rANS, we define a “normalized interval” which bounds the state c such that c ∈ [2M , 2K+M ) (K,M are some integers values) after coding each symbol. For the encoding process, if c ≥ 2K+M , the lower K bits are written to disk, and the remaining bits are reserved such that c← b c
2K c. For the decoding process, if c < 2M ·R, 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 [2M , 2K+M ). The initial state can be set such that c = 2M . We illustrate this idea in Alg. 5.
The correctness of Alg. 5 is illustrated in the following theorem. P1 demonstrates that the symbols can be correctly decoded with a UBCS coder, with coding performed in a first-in-last-out (FILO) fashion. P2 shows that the codelength closely approximates the entropy of a uniform distribution, subject to a large M and K. The proof of the theorem is in the Appendix.
Theorem 3. Consider coding symbols s1, ...sn with si ∼ U(0, Ri), (i = 1, 2, ..., n,Ri < 2K) using Alg. 5, and then decode s′n, s ′ n−1, ..., s ′ 1 sequentially. Suppose (1) the initial state and bit-stream are c0 = 2 M ,bs0 = empty respectively; (2) After coding si, the state is ci and the bit-stream is bsi; (3) After decoding s′i+1, the state is c ′ i and the bit-stream is bs ′ i. We have
P1: s′i = si+1, c′i = ci,bs ′ i = bsi for all i = 0, ..., n− 1.
P2: Denote by the codelength li = dlog cie+ len(bsi) where len is the total number of bits in the bit-stream. Then ln − l0 < 11−1/(ln 2·2M ·K) [∑n i=1Ri + 1 + (ln 2 · 2M )−1 ] .
In practice, we set K = 32 and M = 4. Compared to rANS [12] and Arithmetric Coding (AC) [40], UBCS is of greater efficiency as 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 1 demonstrates that UBCS achieves coding bandwidths in excess of giga-symbol/s – speed significantly greater than rANS.

heading: 4 Experiments
text: In this section, we perform a number of experiments to establish the effectiveness of iFlow. We will investigate: (1) 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.

heading: 4.1 Flow Architectures and Datasets
text: We adopt two types of flow architectures for evaluation: Flow++ [16] and iVPF [41]. Flow++ is a state-of-the-art model using complex non-linear coupling layers and variational dequantizations [19]. iVPF is derived from a volume-preserving flow in which numerically invertible discrete-space operations are introduced. The models are re-implemented or directly taken from the corresponding authors. Unless specified, we use h = 12, k = 28 and set large S – around 216, which we analyse further in the Appendix. To reduce the auxiliary bits in the bits-back coding scheme, we partition the d-dimensional data into b splits and perform MST (in Alg. 1 and 2) for each split sequentially. In this case, the auxiliary bits can be reduced to 1/b in MST. We use b = 4 in this experiment.
Following the lossless compression community [16, 4, 18, 37, 41], we perform evaluation using toy datasets CIFAR10, ImageNet32 and ImageNet64. Results for alternate methods are obtained via re-implementation or taken directly from the corresponding papers, where available. We further test the generalization capabilities of iFlow in which all toy datasets are compressed with a model trained on ImageNet32. For benchmarking our performance on high-resolution images, we evaluate iFlow using CLIC.mobile, CLIC.pro2 and DIV2k [1]. For this purpose, we adopt our ImageNet32/64 model for evaluation, and process an image in terms of 32× 32 or 64× 64 patches, respectively. The experiment is conducted with PyTorch framework with one Tesla P100 GPU.
2https://www.compression.cc/challenge/

heading: 4.2 Compression Performance
text: For our experiments, we use 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 is assumed to be 8. The compression bandwidth evaluates coding efficiency, which we define in terms of symbols compressed per unit time.
Table 2 demonstrates the compression results on CIFAR10. 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 k = 14.
Firstly, we observe that, when using both the Flow++ and iVPF architectures, iFlow achieves a 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 as it avoids the need to store 16 bits for each data sample.
Secondly, the coding latency highlights the main advantage of iFlow: we achieve encoding 5× faster than that of LBB and over 1.5× 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 in 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 1 demonstrates that our UBCS coder achieves a speed-up in excess of 50× that of rANS (which results in a 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 σ bits per dimension (for δ = 2−k and small σ in [17]). Meanwhile, iFlow requires approximately k + 1b logS, and 1 b logS is usually small with large b.

heading: 4.3 Comparison with the State-of-the-Art
text: 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 [26], HilLoc [37], and flow-based models IDF [18], IDF++ [4], iVPF [41], LBB [17]. We additionally include a number of conventional methods, such as PNG [5], 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 all approaches with the exception of LBB on low-resolution images, for which we achieve identical results.
Generalization. The last four rows in Table 3 demonstrate the literature-standard test of generalization, in which ImageNet32 trained model are used for testing. From these results, it 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-trained 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 ImageNet64-trained 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., 5 times faster than LBB and 30% speedup compared with iVPF.

heading: 5 Related Work
text: Dynamic Entropy coders, such as 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 [12] are 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-pixel 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-consuming. Alternatively, variational autoencoders (VAEs) [24, 26, 37] maximise a lower bound on the marginal data likelihood (otherwise known as the ELBO). 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 as there exists a gap between the ELBO and the true data likelihood.
As discussed, flow-based models [16, 25, 11], 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 an invertible mapping between discrete data and latent variables. In a similar vein, iVPF [41] achieved a mapping with volume-preserving flows. Here the remainders of a 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] was the first flowbased 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 errors and does so with the ANS scheme, posing obvious challenges to computational efficiency.

heading: 6 Conclusions and Discussions
text: In this paper, we have proposed iFlow, a 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-performance scheme. Moreover, iFlow is able to achieve state-of-the-art 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 [28, 7, 23]. We have discussed the possible extension to incorporate these advancements in 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 as to observe data-privacy laws.

Review summaries:
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.  The 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.

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.

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.