Flow algorithms apply learnable invertible transforms to make data easier to compress.
IDF [1]} and IDF++ [2]} that have only integer transforms are named as integer flows.
On the other hand, general flows such as LBB [3]} and iFlow [4]} use transforms in real numbers.
There is also one type in between called volume preserving flow, which is discovered in iVPF [5]}. Integer flows are the only type that do not require bits-back, hence the only one that supports single image decoding. But as the expressive power of a single layer is weaker, the model needs to be large, affecting the inference time. Besides, general flow models require one coding step for each layer, making data transfer another bottleneck.
<FIGURE>Entropy Coder.
A static entropy coder codes data from a fixed distribution. It is used by most commercial algorithms.
A dynamic entropy coder, on the other hand, can code many distributions. It is usually used to code one kind of distribution with parameters as input, such as a normal distribution with variable means and variances.
The most widely used entropy coders such as Huffman Code [6]}, Arithmetic Coder (AC) [7]}, [8]}, and Asymmetric Numerical System (ANS) [9]} all have both static and dynamic variants.
Dynamic entropy coders are much slower than static ones, as the density mass needs to be calculated on the fly, unlike the latter one, which can precalculate all of them beforehand.
For example, in a single-threaded setting, a static variant of ANS named FSE [10]} decodes faster than 300 MB/s, while another variant named rANS [9]} decodes at only about 1 MB/s with a distribution mixed by 10 logistic ones.
Despite this fact, a dynamic coder is required for an AI algorithm to do fine-grained density estimation, which is also a key point that makes AI outperform traditional methods.
Methods
In this section, we introduce PILC, a practical image lossless compression framework. The proposed framework consists of a generative model and a semi-dynamic entropy coder. The model is composed of Three-Way Auto-regressive module and VQ-VAE module. We demonstrate how the model interact with the coder to achieve high throughput.
Model Architecture
Overall Model.
Among all current algorithms, AE have the highest throughput but the lowest compression ratio.
As suggested by many previous works, AE models cannot capture local features very well, while a local AR model is capable of doing so [12]}, [13]}.
Therefore an intuitive idea would be to use a small AR to capture local features, and AE for more global ones.
Since AR model hurts the parallelism and affect the throughput heavily, it must be very small.
In this work, a Three-Way Auto-regressive (TWAR) model is designed, where each pixel is predicted with only 3 other ones, reserving the ability to decompress in parallel.
For the AE model, we replace it with VQ-VAE [14]}, which is proven to be successful in image generation [14]}, [16]}, [17]}, [18]}, while the inference time is still similar to AE.
As is shown in  fig:framework, TWAR predicts the original image and output image residual, then VQ-VAE estimates the distribution of the residual.
Distribution of values in the residual is much simpler than those of original images, making it easier to be predicted by VQ-VAE and coded with our entropy coder.
Compress: Given an image \(x\) , we use the Three-Way Auto-regressive module to predict the image, and get the reconstruction image \(\hat{x}\) , image residual \(r = x - \hat{x}\) .
Then we adopt VQ-VAE to estimate the residual distribution \(p(r|x)\) , which we model as a simple logistic distribution. With \(r\)  and \(p(r|x)\) , we could compress \(r\)  to bit stream with our proposed dynamic entropy coder. We also compress the vector index to bit stream using the coder.
Decompress: At decompress time, we decompress vector index from bit stream. Then we select corresponding vectors from the codebook \(Z\)  to formulate the latent feature \(z_q\) . The feature is fed to the decoder and outputs the residual distribution \(p(r|x)\) . The coder subsequently decode the residual \(r\)  using \(p(r|x)\) . The AR module then decodes the original image \(x\)  from the residual \(r\) .
Learning Residual with Three-Way Auto-regressive. Inspired by the Paeth filter which is utilized in the traditional lossless compression method PNG[19]} to transform the image to make it more efficiently compressible, we adopt a similar rule that utilizes three predicted points to predict the current one, which is shown in  fig:three-way. Our AR module is formulated by:
\(\hat{x}_{ruv} = W_{r}^T \cdot (x_{r(u - 1)(v - 1)}, x_{r(u - 1)v}, x_{ru(v - 1)} ) + b_r, \) 
\(\hat{x}_{guv} = W_{g}^T \cdot (x_{gu(v - 1)}, x_{ru(v-1)}, x_{ruv} ) + b_g, \) 
\(\hat{x}_{buv} = W_{b}^T \cdot (x_{bu(v - 1)}, x_{gu(v-1)}, x_{guv} ) + b_b, \) 
where \(r\) , \(g\) , \(b\)  denote image channel, \(u\) , \(v\)  denote the spatial location. We pad the input image with one row on the top and one column on the left to initiate the prediction.
For the red channel, the current point is predicted by its up, left, upper-left points like Paeth filter. Inspired by YCoCg-R color space which is shown successful in FLIF[20]} format and utilizes different channels to calculate the color space, for green and blue channel, we also use their previous channel to conduct the prediction.
Different from [21]}, our AR module models the pictures channel-wise, predict the mean only, and only has 12 parameters (with a bias in each channel), but it could still generate a high-quality prediction.
As shown in  fig:framework, \(\hat{x}\)  is quite close to \(x\) , which suggests the locality of natural images.
As explained in  sec:intro, auto-regressive models like PixelCNN [22]} fail in decompression speed due to their dependencies nature because it is hard to parallelize the inference process.
Fortunately, our AR module could be parallelized during inference. fig:aeparallel suggests one step in decoding. For the red channel, the current point is dependent on its up, left, upper-left points, so anti-diagonal points can be calculated in parallel.
Once the red channel is recovered, for the green channel, we could calculate column by column to recover this channel, and the blue channel is the same.
Thus, more points could be calculated at one time, which speeds up the inference process of the AR module. Because the padding rule is fixed, we could eventually losslessly recover the original image \(x\)  using the residual \(r\) .
Learning Distribution with VQ-VAE.
Vector quantization has been proved to be effective in lossy compression[23]}, [24]}.
Instead of designing a more sophisticated auto-encoder (AE) model, we utilize VQ-VAE[14]} to learn residual distribution. Intuitively, given a fixed storage space, for VQ-VAE, we could just store the vector index and when decoding, with the codebook we could utilize more diversity features. But for vanilla AE, we only have the fixed size features. Experiments in sub:modelablation suggest VQ-VAE's superiority over vanilla AE.
As the original image would contain much more spatial information, we choose to model the residual distribution given the original image, , \(p(r|x)\) .
As shown in fig:framework, given an image \(x \in \mathbb {R}^{H\times W\times 3}\) , we get its latent feature by:
\(\hat{z} = E(x) \in \mathbb {R}^{h\times w\times D},\) 
where \(E\)  is residual block based encoder, and \(D\)  is feature depth dimension. Then, with a codebook \(Z = \lbrace z_i\rbrace _{i=1}^K \in \mathbb {R}^D \) , we could conduct vector quantization on \(\hat{z}\) :
\(z_q = q(\hat{z}) := \left(\mathop {\arg \min }\limits _{z_i \in Z}\parallel \hat{z}_{uv} - z_i \parallel \right) \in \mathbb {R}^{h\times w\times D},\) 
where \(q\)  is the element-wise quantization for each \(\hat{z}_{uv} \in \mathbb {R}^D\)  to its closest code \(z_i\) , and \(u\) , \(v\)  is the spatial location. Finally, we output the residual distribution \(p(r|x)\)  which we model as a logistic distribution and is formulated by:
\((\mu , s) = D(z_q) \in \mathbb {R}^{H\times W\times 3 \times 2},\) 
where \(\mu \)  is the location parameter, \(s\)  is the scale parameter, and \(D\)  is residual block based decoder.
At compress time, the quantized vector index is encoded to bit stream by the coder. At decompress time, we could decode the index, select the corresponding vectors, and decode the distribution \(p(r|x)\) . In this way, we utilize the codebook \(Z\)  to memorize more information.
Since there is no real gradient defined for eq:vector quantization, the gradient back-propagation is achieved by straight-through estimator, which just copies the gradient from the decoder to encoder. The VQ loss is formulated by:
\(\mathcal {L}_{VQ} = {\parallel \mathtt {sg}[\hat{z}] - z_q \parallel }^2 + \beta {\parallel \hat{z} - \mathtt {sg}[z_q] \parallel }^2,\) 
where \(\mathtt {sg}\)  denotes the stop-gradient operator. The first term optimizes the codebook \(Z\)  and the second term is a commitment loss to make sure \(\hat{z}\)  commits to codebook and does not grow arbitrarily[14]}. \(\beta \)  is a weight parameter to balance the two terms.
<FIGURE>Loss Function.
During training, we could jointly optimize the AR module and VQ-VAE module by maximizing the negative log-likelihood of the residual \(r\) :
\(\mathcal {L}_{NLL} = \mathbb {E}_{x\sim p(x)} \left[ -\log p(r|x)\right],\) 
where \(p(x)\)  denotes the distribution of the training dataset. The lower the negative log-likelihood is, the fewer bits we need to compress the residual \(r\) . See  subsec:intermodelcoder for the more implement detail.
Thus, the total objective function to optimize our neural compression model can be formulated by:
\(\mathcal {L}_{total} = \mathcal {L}_{NLL} + \alpha \mathcal {L}_{VQ},\) 
where \(\alpha \)  balances the two terms.
Our lightweight model with the Three-Way Auto-regressive and VQ-VAE achieves a high inference speed, which plays an important role in our overall framework.

Coder Design
We design our entropy coder based on rANS [9]}, and save computation time by precalculating intermediate results.
Previous works such as tANS [9]} already adopt this idea. However, tANS can only code a fixed distribution, which is inappropriate for AI algorithms.
On the other hand, our proposed coder is more similar to dynamic ones, as it supports distributions with variable parameters.
The only difference is that the parameters need to be quantized, and probability mass needs to be calculated for all of them. Thus we call it a semi-dynamic entropy coder.
To code with rANS, one first needs to choose a constant \(M\) , then for each symbol \(x\) , quantize its probability mass function (denoted as \(P_x\) ), so that \(\sum _x P_x = 2^M\) . Let \(C_x\)  be the cumulative distribution function of \(x\) . It satisfies that \(C_x = \sum _{i<x} P_x\) . To encode pixels within range \([0,255]\) , \(M\)  is usually chosen in \([10, 15]\) .
In this work, we modify rANS slightly, and propose alg:ansencode and alg:ansdecode as the logic behind.
Modified rANS: Encode \(x\)
[1]
\(M\) , \(P_x, C_x\) , State \(S\) , stream
\(S \leftarrow S + 2^M\) 
\(S \ge P_x * 2\) 
\(\mathtt {push\_stream}(S\mod {2})\)  last bit of \(S\)  to stream
\(S \leftarrow \lfloor S \div 2 \rfloor \) 
\(S \leftarrow S - P_x + C_x\)

Modified rANS: Decode one symbol
[1]
\(M\) , \(P_x, C_x\)  for all \(x\) , State \(S\) , stream
\(x \leftarrow \mathtt {binary\_search}(S)\) : \( C_x \le S < C_x + P_x\) 
\(S \leftarrow S - C_x + P_x\) 
\(S < 2^M\) 
\(S \leftarrow S \times 2 + \mathtt {pop\_stream()}\)  last bit of stream
\(S \leftarrow S - 2^M\) 
\(x\)

Loops and binary search form the time-consuming steps for these algorithms, so tables are built to cache these results.
For encoding, one solution would be to create a table to store the number of bits to be pushed for each possible value of \(S\)  and \(P_x\) . Each value can be represented as a 16-bit unsigned integer, so the memory needed is \(2^{2M+1}\)  bytes.
In this work, we assume the number of distributions for different symbols is small. Denote the total number of distributions as \(D\) , and the distribution index \(d \in [0, D)\)  for each symbol can be calculated via the network, and let \(X\)  be the number of colors. Since \(S\)  is always in \([2^M, 2^{M+1})\)  after Step REF , so for a fixed \(d\) , the number of loops can differ only 1. So we build a table \(\delta \)  with dimension \(D \times X\)  such that
\(\frac{S}{2^{\lfloor (\delta [d, x] + S) / 2^M \rfloor }} \in [P_x, P_x * 2).\) 
To further simplify the algorithm, Step REF  is merged with Step REF  of next symbol in this work, and table \(\phi \)  is built such that \(\phi [d, x] = 2^M - P_x + C_x\) . \(S\)  needs to be initialized in \([2^M, 2^{M+1})\)  then. The encoding process now is shown in alg:tansencode. Both \(\delta \)  and \(\phi \)  use unsigned 16-bit integers, so the memory needed for tables are \(4 \times D \times X\)  bytes. As the total memory needed for all \(P_x\) 's and \(C_x\) 's are also \(4 \times D \times X\)  bytes, which is not needed any more, alg:tansencode does not cost any additional memory.


ANS-AI: Encode \(x\)
[1]
\(M\) , \(\delta \) , \(\phi \) , \(x\) , \(d\) , State \(S\) , stream
\(b = \lfloor (\delta [d, x] + S) / 2^M \rfloor \) 
\(\mathtt {push\_stream}(S, b)\)  last \(b\)  bits of S to stream
\(S \leftarrow \lfloor S / 2^b \rfloor + \phi [d, x]\)

In terms of decoding, for each distribution index \(d\)  and state \(S\) , we maintain a table \(\Theta \)  to store the symbol to be decoded, a table \(B\)  for number of bits to pop, and a table \(N\)  to merge Step REF  to REF . Since \(\Theta \)  and \(B\)  use 8-bit unsigned integers, and \(N\)  use a 16-bit unsigned one, the total memory consumed for these tables are \(D \times 2^{M+2}\)  bytes. One alternative is to replace \(N\)  and \(B\)  with \(\phi \)  and \(\delta \) , reducing the memory to \(D \times 2^M + 4 \times D \times X\) , but this will make the computation more complicated, and reduce the decoding speed by about 50% from our experiments.


ANS-AI: Decode one symbol
[1]
\(M\) , \(\Theta \) , \(B\) , \(N\) , \(d\) , State \(S\) , stream
\(x \leftarrow \Theta [d, S]\) 
\(S \leftarrow N[d,S] + \mathtt {pop\_stream}(B[d,S])\)  last \(B[d,S]\)  bits
\(x\)

Our proposed coder not only simplifies the computation, but also makes it possible to implement with a machine learning framework such as PyTorch by removing all the logical units.

Integration of Model and Coder
<FIGURE>To guarantee the effectiveness of the coder, the total number of distributions \(D\)  needs to be small.
In our model, each pixel of \(r\)  is predicted with a truncated logistic distribution with location parameter \(\mu \)  and scale parameter \(s\) , truncated between 0 and 255. Denote the distribution as \(r \sim L(\mu , s, 0, 255)\) . Since the number of means is required to be quantized to at least 256 values, \(D\)  would be over one thousand.
In this work, we predict \(r - \mu + 128\)  within uint8 space, , the prediction of \(r \sim L(\mu , s, 0, 255)\)  is approximated as \((r - \mu + 128) \bmod 256 \sim L(128, s, 0, 255)\) . To make it as accurate as possible, \(\mu \)  needs to be as close to 128 as possible. We apply the following two techniques for this:
In VQ-VAE module, instead of predicting residual \(r\)  directly, we predict \((r + 128)\bmod 256\) .

We add a sigmoid layer to predict the final value of \(\mu \)  in VQ-VAE module to make sure it is close to 128.
fig:klu and fig:predictedu show that this technique almost deals with no BPD loss.
Experiments
In this section, we evaluate the model and coder effectiveness with extensive experiments and we conduct experiments on both low resolution and high resolution images which demonstrate our framework obtains the fastest compression speed with a competitive compression ratio.
Experimental Settings
Implementation Details. The AR and VQ-VAE module are jointly trained. The AR module contains 12 parameters. In VQ-VAE, the codebook size \(K\)  is set to 256 and the codebook dimension \(D\)  is set to 32.
The encoder and decoder both have 4 residual blocks, all with 32 channels. The encoder downsampling ratio is 2, and pixel shuffle is used when upsampling in the decoder. Thus, an image \(x \)  with shape \(32 \times 32 \times 3\)  would be quantized to \(16 \times 16 \times 1\)  vectors.
\(\beta \)  in  eq: vq loss is set to 0.25 as in [14]}, and \(\alpha \)  in  eq:totalloss is set to 125.
We do all experiments in a Linux docker with Intel(R) Xeon(R) Gold 6151 CPU (3.0 GHz, 72 threads), and one NVIDIA Tesla V100 32GB.
For speed tests, we ignore the time for disk I/O, since it has nothing to do with compression algorithms.
But for fair comparison between AI and traditional methods, we do count the time for data transfer between CPU memory and GPU memory.
That means for all AI algorithms, timer starts when data is loaded into RAM and ends when compressed data is stored in RAM.
Different from previous AI compression works which focus on density estimation, this paper targets practical compression. Therefore, for BPD values reported in this paper, all storage required to recover the original image is counted, including meta data, Huffman tables, auxiliary bits, etc.. For AI algorithms, real BPD is reported instead of theoretical one unless specified otherwise, which means for each image, we calculate the number of bytes (instead of bits) needed for each image, then take the average.
<TABLE><TABLE>Datasets.
For low resolution experiments, we train and evaluate on CIFAR10, ImageNet32/64. For high resolution experiments, we train our model on 50000 images from Open Image Train Dataset[30]} which are randomly selected and preprocessed as [31]} to prevent overfitting on JPEG artifacts. Then, we evaluate on natural high resolution datasets, CLIC.mobile, CLIC.pro[32]} and DIV2K[33]} to test the model generalization ability. For
high resolution setting, we crop 32 \(\times \)  32 patches for evaluating.
<FIGURE>
Model Effectiveness
<TABLE>Effectiveness of model architecture. We analyze single and combinations of each component to evaluate the effectiveness of model architecture. In tab:archcomponents, the vanilla Auto-encoder (AE) contains the same encoder and decoder architecture as VQ-VAE with latent feature shape 16\(\times \) 16\(\times \) 1. In AE and VQ-VAE, we directly use the model to predict the distribution of the original image. In the single AR, we compress the residual with a static entropy coder to get the BPD. AR+AE follows the same process as AR+VQ-VAE. As shown in tab:archcomponents, VQ-VAE outperforms AE which demonstrates the effectiveness of the learned codebook \(Z\) . We could intuitively explain that 16\(\times \) 16\(\times \) 1 vector indexes would contain more diversity features than 16\(\times \) 16\(\times \) 1 numbers in AE's latent. Our proposed AR+VQ-VAE model achieves the best theoretical BPD on CIFAR10 which suggests the effectiveness of predicting residual.
Effectiveness of Three-Way AR and parallel mechanism. We compare different receptive fields of the AR model and the parallel mechanism. Experiments are conducted on red channel of CIFAR10 images. The receptive field of AR model means the current point is predicted by how many previous points. In our model, the receptive field is three. As shown in tab:arreceptivefield, as the receptive field increases, the BPD indeed descends, but the decline is very limited. With the parallel mechanism we designed in subsec:modelarchitecture, the Three-Way AR achieves a throughput of 382.5 MB/s when recovering original images from residual in decompression, and outperforms other settings which cannot be paralleled.

Coder Effectiveness
We implement the GPU coder based on alg:tansencode and alg:tansdecode. We test the coder on the randomly generated data (1000000 pieces, each with length 1000, and range 0-255). The signals have the same dimension with each value in 0-7. For each setting, we run 10 times and take the average speed. From fig:coderspeed, we see that GPU coder is slow for the small number of threads. Fortunately, the number of threads can easily reach one million with a V100 32G. Therefore, we can inference on million batches, and save the result in GPU. Then we can code all of the batches at once.
This is beneficial for the GPU coder, in the sense that the data transfer times and the amount is smaller for both compression and decompression.

Distribution Effectiveness
<FIGURE>We count the predicted location parameter \(\mu \)  for the distribution specified in subsec:intermodelcoder.
It can be shown in fig:predictedu that for all the three datasets, the predicted values nearly always fall in \([96, 160]\) . As stated in subsec:intermodelcoder, this cause almost no loss in BPD.

Compression performance
Compare with exists methods. We reproduce all methods in  tab:overallspeed on the same platform explained in subsec:expsettings for fair comparison. We use Python CV2 lib for PNG and JPEG2000. We adopt FLIF version 1.0.1 and use command `flif -e –effort=0' for fastest setting. For WebP, we use version 1.2.1 and the command `cwebp -lossless -z 0'. For L3C, we reproduce the results using the official model[34]} and we replace the original coder in L3C with ours to test the speed as the original coder is very slow. The throughput results are reported based on high resolution settings.  tab:overallspeed shows our framework achieves the fastest compress and decompress throughput. Also, the framework achieves a competitive compression ratio on low resolution images and we still outperform PNG, WebP and JPEG2000 on high resolution images.
End-to-end throughput. To fully use the GPU coder and make the measured speed more accurate, we duplicate the CIFAR10 validation set 100 times (1 million images).  tab:decomposition shows the details of the throughput and time taken for each step.
<TABLE>
Limitation Analysis
Our framework, although very light-weighted, requires an AI chip such as Tesla V100 to work efficiently, which is inaccessible for most end-users. For example, one image with 2K resolution compresses only about 1.3 MB/s in the CPU of our server machine. Therefore, our framework is only applicable to file/cloud servers.

Conclusion
In this work, we develop the first efficient end-to-end generative model based image lossless compression framework with throughput of about 200 MB/s, and compression ratio 30% better than PNG. To achieve this result, we develop a model that combines AR model and VQ-VAE, and a semi-dynamic coder that is computation efficient.
To further improve PILC, future works could focus on algorithms that are more friendly in everyday devices, such as a PC, or mobile phone. This requires a network with much less FLOPS than the current VQ-VAE one.

Coder Design
With the same notation as ours, the original rANS can be written as:
\(\text{Encoding: } S \leftarrow 2^M \times \lfloor S / P_x \rfloor + C_x + S \bmod P_x,\) 
\(\text{Decoding: } S \leftarrow P_x \times \lfloor S / 2^M \rfloor + S \bmod 2^M - C_x,\) 
where in decoding, same as the modified one, to get \(x\) , binary search is also needed to be applied on \(S \bmod 2^M\) .
Let \(n\)  be the message length, if applying eq:originalransencoding and eq:originalransdecoding directly, the time complexity is \(O(n^2)\) . So in real applications, \(S\)  is usually truncated to a range, such as \([2^{32}, 2^{64})\) , reducing the time complexity to \(O(n)\)  for encoding and \(O(n \log X)\)  for decoding, with minor reduction in compression ratio. However, it is still not efficient enough for real-time applications due to:
\(P_x\)  and \(C_x\)  need to be calculated online for each \(x\) .

One division operation and one modular operation are required for encoding.

Binary search is needed for decoding.
In this work, \(S\)  is truncated to \([2^M, 2^{M+1})\) , which boosts the efficiency, but affects the compression ratio more severely, and more memory is needed. In next subsections, we prove that the BPD loss and memory are both upper-bounded by an acceptable value.
BPD loss for ANS-AI
Lemma 1 BPD for the ANS-AI is at most \(2 - \log _2 e\)  worse than the original rANS.

As ANS-AI and the modified rANS are numerically equivalent, it suffices to prove the effectiveness of the latter.
Without loss of generality, assume quantization for pdf values does not introduce bias in density estimation, which means \(p(x=i) = P_i / 2^M\)  for all \(i\) , otherwise both original and modified ones are affected by the same way.
Also each symbol \(x\)  is independent of each other.
Unless specified otherwise, all \(\log \)  in this material means logarithm function with base 2. Then from Shannon's source coding theorem:
\(\begin{split}\mathtt {BPD(rANS)} & \ge \frac{\sum _i P_i \times \log 2^M / P_i}{2^M} \\& = M - \frac{\sum _i P_i \times \log P_i}{2^M}.\end{split}\) 
For the ANS-AI, BPD value equals to the expected number of bits to push to steam during encoding. The value \(S\)  before each encoding is uniform in \([2^M, 2^{M+1})\)  since \(P_i\)  is proportional to \(p(x=i)\) . Therefore:
\(\begin{split}\mathtt {BPD(ANS\_AI)} & = \sum _{j \in [2^M, 2^{M+1})}\frac{\sum _i P_i \times \lfloor \log (j/P_i) \rfloor / 2^M}{2^M} \\& \le \frac{\sum _{j \in [2^M, 2^{M+1})} \sum _i P_i \times \log (j/P_i)}{2^{2M}} \\& = \frac{\sum _{j \in [2^M, 2^{M+1})}\log j}{2^M} - \frac{\sum _i P_i \times \log P_i}{2^M} \\& \le \frac{\int _{2^M}^{2^{M+1}} \log j}{2^M} - \frac{\sum _i P_i \times \log P_i}{2^M} \\& = M + 2 - \log e - \frac{\sum _i P_i \times \log P_i}{2^M}.\end{split}\) 
Bring eq:bpdans and eq:bpdansai together, we get
\(\mathtt {BPD(ANS\_AI) - BPD(rANS) \le 2 - \log e}.\) 

Memory consumption for ANS-AI
Lemma 2 
In our frame work, when \(M \le 12\) , \(\delta \)  can be represented as an 16 bit unsigned integer.

Let \(k\)  be the integer such that \(P_x \times 2^k \in [2^M, 2^{M+1})\) . In our framework, it always satisfies that \(P_x \in [1, 2^{M-1})\) , thus \(k \in [2, M]\) . Therefore:
\(\lfloor \frac{\delta [d,x]+S}{2^M} \rfloor = {\left\lbrace \begin{array}{ll}k & S \in [P_x \times 2^k, 2^{M+1}) \\k - 1 & S \in [2^M, P_x \times 2^k)\end{array}\right.}\) 
Then it suffices to prove that when \(\delta [d,x] = k \times 2^M - P_x \times 2^k\) , both unsigned 16 bit constraint and eq:rangedelta are satisfied.

\(\delta [d,x] < k \times 2^M - 2^M < (M - 1) \times 2^M \le 11 \times 2^{12} < 2^{16}\) , and \(\delta [d,x] \ge 2 \times 2^M - P_x \times 2^k > 0\) . Therefore \(\delta [d,x]\)  is in range of unsigned 16 bit integer.

If \(S \in [P_x \times 2^k, 2^{M+1})\) , then \(\delta [d,x] + S \ge \delta [d,x] + P_x \times 2^k = k \times 2^M\) , and \(\delta [d,x] + S < k \times 2^M - P_x \times 2^k + 2^{M+1} \le k \times 2^M - 2^M + 2^{M+1} = (k+1)\times 2^M\) . Therefore, in this case, \(\lfloor \frac{\delta [d,x]+S}{2^M} \rfloor = k\) .

If \(S \in [2^M, P_x \times 2^k)\) , then \(\delta [d,x] + S < \delta [d,x] + P_x \times 2^k = k \times 2^M\) , and \(\delta [d,x] + S >= k \times 2^M - P_x \times 2^k + 2^M > k \times 2^M - 2^{M+1} + 2^M = (k-1) \times 2^M\) . Therefore, in this case, \(\lfloor \frac{\delta [d,x]+S}{2^M} \rfloor = k - 1\) .

Corollary 2.1 
In general, when \(M \le 11\) , \(\delta \)  can be represented as a 16 bit signed integer.

If one is using distributions different from us, then the range of \(P_x\)  may changed to \([1, 2^M)\) , which means the probability of one symbol may be at least \(0.5\) , then the condition is changed to the one shown in Corollary REF . The proof is almost the same with Lemma REF .
Corollary 2.2 When \(M \le 12\) , ANS-AI encoding requires \(4 \times D \times X\)  bytes of memory, and decoding requires \(D \times 2^{M+2}\)  bytes.


Speed comparison of rANS and ANS-AI
We compare the speed of rANS coder and ours in the same machine as stated in experiment section of the main body. For fair comparison, both coders are implemented using C++ with OpenMP, and run on CPU. As is shown in table:throughputransai, ANS-AI is 10 to 100 times faster than rANS.
<TABLE>
GPU Coder vs CPU Coder
We use the same algorithm we designed to create a CPU Coder. As shown in tab:cpucodergpucoder, we compare the composition throughput between CPU Coder and GPU Coder. The CPU Coder is set to 16 threads. We duplicate the CIFAR10 validation set for ten times for experiment.
Compress. In terms of compression time, the throughput of CPU and GPU coders is comparable because both require two RAM-GPU transfers. We notice that GPU to RAM time is different between the two Coder. Because the residual data, latent data, and distribution parameters must all be transferred from GPU to RAM for CPU Coder, but only compressed data must be transferred from GPU to RAM for GPU Coder, which takes less time.
<TABLE><TABLE>Decompress. The CPU Coder requires two additional RAM-GPU transfers during decompression because the Coder decoding is done on the CPU. The CPU Coder decodes latent vector indexes before sending them to the GPU. Then we need to transmit the distribution parameters to RAM after VQ-VAE decodes them. The residual is then decoded by the Coder and passed back to the GPU. The Three-Way Auto-regressive recovers original data from residual data. The GPU Coder, on the other hand, only requires two RAM-GPU transfers, and all Coder decoding is done on the GPU, which saves a lot of time.
<FIGURE><TABLE><TABLE>
Model architecture
We do further experiments to see how different codebook sizes and dimensions affect the results.
A large codebook size or codebook dimension favors the BPD but reduces performance, as seen in tab:resblockandcodebook. A tiny codebook size or codebook dimension does indeed produce substantially faster throughput, but it would contains relatively little information when applying our model to high resolution images. As a result, on codebook size/dimension, there is a trade-off between BPD and throughput. To balance the trade-off, we set the codebook size to 256 and the codebook dimension to 32 in our framework.
We investigate the impact of various model capacities. We modify the number of residual block and the mid channel dimension to change the model capacity. As shown in tab:resblockandcodebook, the larger model achieves lower BPD, but the throughput of the model drops even faster, which deviates from the 'practical' aim. As a result, we adjust our model to 4 residual blocks and 32 mid channel dimensions.

Receptive field rules of AR model
fig:receptivefield demonstrates the receptive field rules of the auto-regressive model on a single channel which we use in the ablation study. As the figure suggests, these receptive field settings cannot be parallelized using what we implement in Three-Way Auto-regressive.

Parallel vs No Parallel
We add the experiment result of Three-Way Auto-regressive without parallel. As shown in tab:w/oparallel, Three-Way Auto-regressive using our designed parallel mechanism achieves the fastest throughput with competitive compression ratio.

Why predict residual given original image?
We investigate the different input of VQ-VAE model. We use the original image, reconstruction image, residual, and original image concatenated with residual to predict the residual. As illustrated in tab:vqvaediffinputs, directly using residual to predict residual is not the best solution. As the original image has a lot of spatial information, we choose to model the residual given original image.
