Efficiency of ANS Entropy Encoders
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Efficiency of ANS Entropy Encoders".
Title and authors: Tom: So, to recap, this paper "Efficiency of ANS Entropy Encoders" by Kosolobov and his team is focusing on finding the tightest possible bounds for redundancy in tabled ANS.
Jane: That means they aren't just guessing at how much extra data you need; they are giving us concrete mathematical limits on that trade-off.
Lu: They start by looking at the basic setup: a sequence of symbols from an alphabet of size sigma, where each symbol appears some number of times, and n is twice r.
Meng: So, the core idea here is to show that for this most popular variant, we can establish both an upper bound and a lower bound on the redundancy.
Lalam: The paper claims they prove the redundancy is at most O of sigma n bits per symbol when using Duda’s precise initialization for filling those tables.
Tom: But there’s an extra bit term they mention, which is r bits, which seems to be an artifact of the encoder itself that we have to account for.
Jane: So if we add that r bit term in, the upper bound for the total redundancy across all symbols becomes sigma log e plus r bits over all symbols.
Lu: And they show this isn't just an upper limit; they provide examples where a lower bound of sigma minus one over four plus r minus two bits is actually achievable when sigma is about n divided by three.
The paper's summary: Tom: So, to summarize the main finding of "Efficiency of ANS Entropy Encoders," they prove the redundancy for tabled ANS is O of sigma n bits per symbol.
Jane: That’s a big step because it directly refutes Duda’s earlier conjecture that the redundancy could be as high as O of sigma n squared bits per symbol.
Lu: They do this by establishing worst-case bounds based on empirical entropy, without needing any assumptions about how the source data was generated.
Meng: That lack of randomized assumption is important because it means these bounds apply to any sequence we feed into the encoder, not just some idealized random input.
Lalam: They also introduce a different variant called rANS with fixed accuracy k, which they analyze and bound by n squared over k minus one log e plus r plus k.
Tom: That fixed accuracy thing sounds interesting because it’s aimed at making the division operations faster in practice, avoiding slow explicit division.
Jane: And they show that for this specific variant, the redundancy bound is that n squared over k minus one log e plus r plus k bits over all symbols.
The paper's improvements: Tom: So, what are these proposed improvements from the authors? They seem to focus on making the practical implementations of these ANS methods better.
Lu: One improvement they highlight is using Duda’s precise initialization or its simplified variant from Algorithm one because it leads to that tighter upper bound of O of sigma plus r redundant bits per symbol for tabled ANS.
Meng: From a deployment standpoint, that O of sigma plus r term is what matters when you're thinking about how much overhead the encoder adds to a real system.
Jane: Then there’s the modification to rANS with fixed accuracy k, which they suggest can be faster than standard rANS because it avoids slow explicit division operations by ensuring the result of that floor division stays within a specific range.
Lalam: That range constraint is key; it guarantees the division operation can be done using simpler instructions like bit operations in branchless code for speed enhancement.
Tom: So, they’re not just proving a theoretical limit; they’re also giving us practical tips on how to make these algorithms run quicker on hardware.
Conclusion: Jane: So, to wrap up "Efficiency of ANS Entropy Encoders," the paper establishes tight asymptotic upper and lower bounds for both tabled ANS and the modified rANS variant.
Tom: The main implication is that we can finally understand exactly how much redundancy we are dealing with in these common entropy encoding methods.
Lu: They’re essentially saying that the redundancy isn't as bad as people thought, refuting the O of sigma n squared bound for tANS.
Meng: For those of us shipping models, knowing that the overhead is closer to O of sigma plus r per symbol helps us budget our memory and processing time better than if we just used a loose theoretical estimate.
Lalam: And they point out that while these bounds are tight asymptotically, finding the exact constant in those bounds for tabled ANS is still an open problem.
Tom: Yeah, so it’s a huge step in understanding the fundamental performance characteristics of ANS encoders. We should keep an eye on how they build on this for real-world deployment challenges next.
Dmitry Kosolobov
St. Petersburg State University · Ural Federal University
cs.IT, cs.DS, math.IT
Submitted: 2022-01-07
Updated: 2026-11-17
Comments: 27 pages, 5 figures, 1 table, 2 listings
Code: https://github.com/dkosolobov/rans_with_fixed_accuracy
License: http://creativecommons.org/licenses/by/4.0/
The gist: Asymmetric Numeral Systems (ANS) are studied for their efficiency as entropy encoders, and this paper obtains asymptotically tight bounds for the redundancy of tabled ANS (tANS)…
Key concepts
- Asymmetric Numeral Systems (ANS)
- ANS are a class of entropy encoders that replaced arithmetic and Huffman coding. They use tables to map input symbols to bit strings, offering compression rates comparable to arithmetic coding while being fast enough for Huffman-like performance.
- Tabled ANS (tANS)
- tANS is the most popular variant of ANS, which uses pre-computed tables based on symbol frequencies. The paper analyzes its redundancy using worst-case bounds based on empirical entropy, showing it performs better than previously thought.
- Redundancy Bounds
- This refers to the difference between the actual number of bits produced by an encoder and the theoretical minimum information required (entropy). The paper finds that for tANS, this redundancy is asymptotically O(σn) bits per symbol, which is much better than the conjectured O(σn^2).
- rANS with fixed accuracy
- This is a novel variant of range ANS parameterized by k. It aims to speed up encoding by avoiding slow explicit division operations through specific constraints on the result range, potentially making it faster than standard rANS under certain conditions.
Terminology
Summary
Asymmetric Numeral Systems (ANS) are studied for their efficiency as entropy encoders, and this paper obtains asymptotically tight bounds for the redundancy of tabled ANS (tANS), which is important because it refutes Duda’s conjecture that the redundancy is O(σn 2) bits per symbol
Redundancy Bounds for tANS
The paper establishes tight asymptotic upper and lower bounds on the redundancy of tabled ANS (tANS), which is the most popular ANS variant The analysis of the redundancy does not impose any randomized assumptions on the source that produced the input for the encoder; instead, we establish worst-case bounds in terms of the so-called empirical entropy In this paper we prove that the redundancy for tANS is O(σn) bits per symbol We complement this upper bound by a series of examples showing that it is asymptotically tight when σ > n/3 After uncovering the constant under the big-O and including this r-bit term, the upper bound for the tANS redundancy that we establish can be expressed as σ log e+r bits over all symbols (not per symbol) Our lower bound examples show that a redundancy of σ−1/4 +r − 2 bits is attainable, for σ ≈ n/3
Analysis of the Range ANS Variants
The paper introduces and analyzes a novel variant of the range ANS (rANS), called rANS with fixed accuracy, parameterized by k ≥ 1 that in certain conditions might be faster than the standard rANS because it avoids slow explicit division operations We bound the redundancy for our rANS variant by n 2/k−1 log e+r+k The new rANS takes as a regulated parameter an integer k ≥ 1. It is guaranteed that the division can be performed only in cases when its result belongs to the range [2k/2k+1) We upperbound the redundancy for the rANS with fixed accuracy k by n 2/k−1 log e+r+k
Performance of Tabled ANS
The analysis of the tANS encoder shows that using [simplified] Duda’s precise initialization transforms this sequence into a bit string of length X a∈[0,σ) fa · log n fa + O(σ + r) Theorem 1 states that given a sequence a1, a2,..., an of symbols from an alphabet [0,σ) such that each symbol a occurs in it fa times and n = 2r for an integer r, the ANS encoder using [simplified] Duda’s precise initialization transforms this sequence into a bit string of length X a∈[0,σ) fa · log n fa + O(σ + r), where the O(σ + r) term can be bounded by σ log e + r Theorem 3 proves that for arbitrarily large n = 2r with even r, there exists an alphabet [0,σ), where σ > n/3, and a sequence a1, a2,. p. 0 , a
n of symbols from an alphabet
{
0
,
1, . , σ
−
1
} such that each symbol
a occurs in it
f
a times and
n = 2
r
,
the tANS encoder using Duda’s “precise initialization” to fill tANS tables
transforms this sequence into a bit string of the following length (the frequencies are not included in the encoding): Pa∈[0.Where the paper says it
Conclusion and Open Problems
Theorems 1 and 3 describe the tight asymptotic behaviour of the redundancy for the tANS We believe that Theorem 4, albeit not complemented with a lower bound, is asymptotically tight too The main remaining open problem concerning ANS encoders, as we see it, is to construct a genuine FIFO encoder with the same performance characteristics as tANS or rANS Duda’s precise initialization and its simplified variant from Algorithm 1 are not particularly suitable for practice due to the overhead incurred by operations on the priority queue and by floating point operations The constants in our lower and upper bounds in Theorems 1 and 3 do not coincide and it remains open to find a tight constant for the tANS redundancy term
Implementation Details for rANS
The rANS with fixed accuracy k = 3 encodes faster than the classical rANS with explicit divisions but slower than the faster rANS implementation The key feature that allows the speed boost in encoding is that the operation of division ⌊x/fa⌋ in (11) guarantees that its result is in the range [2k/2k+1) The code, however, turns out to be quite cumbersome, which noticeably diminishes positive effects of the division-free branchless loop
Frequency Table Encoding
The encoding of the table of frequencies is rarely in the focus of theoretical research It seems that further investigations in this direction are needed Ideally, such an encoder should take into account the entropy of the data to be able to relax some frequencies in order to make the total encoding size smaller, if necessary, thus never being worse than the Huffman encoders (see [17] and references in [45]) The authors note that it is not an exceptional case: for instance, the Huffman encoder is consistently superior to arithmetic or ANS when encoding literals in LZ77 compressors
Acknowledgments
I wish to thank the anonymous referees whose detailed reviews and suggestions helped to improve the paper The work is supported by the Russian Science Foundation (RSF), project 24-71-00062 The references listed are [1] J. Duda. Asymmetric numeral systems, [2] J. p. 0 E-mail: dkosolobov@mail. p. 0 2Ural Federal University, Ekaterinburg, Russia. E-mail: dkosolobov@mail. E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. redundancy can be observed for any adequate algorithm that generates the
tANS tables using only the known frequencies of symbols without processing
the sequence itself (however, methods that analyze the sequence might avoid
this effect [17, 28]; these methods are usually infeasible in practice due to their
relatively slow performance). We note that an analogous upper bound of O(
1
2w )
bits per symbol is known for practical variants of the arithmetic coding that use
w-bit machine words [29]. E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. Keywords: Asymmetric numeral systems, ANS, finite state entropy,
FSE, arithmetic coding, redundancy
1 Introduction
Asymmetric numeral systems (ANS) is a class of entropy encoders invented by
Duda in 2009 [1–3]. These encoders had a huge impact on the data compression
by providing the same rates of compression as the arithmetic coding [4–8] while
being as fast as the Huffman coding [9] (and even faster in some scenarios). E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. Collet [10], several high performance compressors based on ANS appeared [11–
13] and it was integrated in some modern media formats [14,15]. The theoretical
community also contributed to the study of ANS in a series of works [16–20,20–
22], though less actively than practitioners [13, 23–25]. E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. These encoders had a huge impact on the data compression
by providing the same rates of compression as the arithmetic coding [4–8] while
being as fast as the Huffman coding [9] (and even faster in some scenarios). Since the invention of ANS and the emergence of its efficient implementation by 1
arXiv:2201. We
bound the redundancy for our rANS variant by
n
2
k
−
1
log
e
+
r
+
k
. Keywords: Asymmetric numeral systems, ANS, finite state entropy,
FSE, arithmetic coding, redundancy
1 Introduction
Asymmetric numeral systems (ANS) is a class of entropy encoders invented by
Duda in 2009 [1–3]. E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. We
bound the redundancy for our rANS variant by
n
2
k
−
1
log
e
+
r
+
k
. Keywords: Asymmetric numeral systems, ANS, finite state entropy,
FSE, arithmetic coding, redundancy
1 Introduction
Asymmetric numeral systems (ANS) is a class of entropy encoders invented by
Duda in 2009 [1–3]. E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. Collet [10], several high performance compressors based on ANS appeared [11–
13] and it was integrated in some modern media formats [14,15]. The theoretical
community also contributed to the study of ANS in a series of works [16–20,20–
22], though less actively than practitioners [13, 23–25]. E-mail: dkosolobov@mail. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- Page 1 ---
Efficiency of ANS Entropy Encoders Dmitri Kosolobov1,2 1St. Petersburg State University, St. p. 0 Efficiency of ANS Entropy Encoders
Dmitry Kosolobov1,2
1St. Petersburg State University, St. Petersburg State University, St. Petersburg, Russia. Petersburg, Russia. 2Ural Federal University, Ekaterinburg, Russia. ORCID: 0000-0002-2909-2952
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders
that had an immense impact on the data compression, substituting arithmetic and Huffman coding. It was studied by different authors but
the precise asymptotics of its redundancy (in relation to the entropy)
was not completely understood. Given a sequence
a
1, a
2, . , a
n of symbols from an alphabet
{
0
,
1, .Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- Page 2 ---
Introduction Asymmetric numeral systems (ANS) is a class of entropy encoders invented by Duda in 2009 [1–3] These encoders had a huge impact on the data compression by providing the same rates of compression as the arithmetic coding [4–8] while being as fast as the Huffman coding [9] (and even faster in some scenarios) Since the invention of ANS and the emergence of its efficient implementation by 1 arXiv:2201.02514v3 [cs. p. 0 Since the invention of ANS and the emergence of its efficient implementation by 1
arXiv:2201. 02514v3 [cs.Where the paper says it
--- Page 3 ---
Collet [10], several high performance compressors based on ANS appeared [11–] Collet [10], several high performance compressors based on ANS appeared and it was integrated in some modern media formats [14,15] The theoretical community also contributed to the study of ANS in a series of works [16–20,20–22] though less actively than practitioners [13, 23–25]
--- Page 4 ---
The primary focus of the theoretical analysis for entropy encoders is in the estimation of the redundancy, the difference between the number of bits produced by the encoder and the information theoretic entropy lower bound The main result of the present paper is a tight asymptotic upper and lower bound on the redundancy of the most popular variant of ANS, called tabled ANS (tANS) or, sometimes, the Finite State Entropy (FSE) Our analysis of the redundancy does not impose any randomized assumptions on the source that produced the input for the encoder; instead, we establish worst-case bounds in terms of the so-called empirical entropy [26, 27] (the definitions follow)
--- Page 5 ---
An entropy encoder receives as its input a sequence of n numbers from a set [0, σ−1] and transforms it into a bit string Duda analyzed his tANS encoder and found that its redundancy is O(σn log n) bits per symbol1 provided an appropriate initialization is used for tANS tables (details are explained in the sequel); see Equation (40) in [1] His estimation, however, seems somewhat nonrigorous and in a different (more classical) setting: he considers a memoryless source generating the input at random and he estimates the expected length of the output encoding Based on experimental evaluations, Duda conjectured that a tight bound for the redundancy is O(σn 2) bits per symbol [2] Yokoo and Dubé [22] investigated the same problem in more rigorous terms closer to our setting and showed that the redundancy per symbol vanishes as the length n tends to infinity while σ is fixed (yet, they have some questionable assumptions in their derivations) Another analysis of the expected output length for the memoryless source was conducted in [20]: their bounds, however, are incomplete in a sense and, thus, cannot be easily compared to other results In contrast, our analysis establishes upper bounds in the worst case without probabilistic assumptions.
--- Page 6 ---
In this paper we prove that the redundancy for tANS is O(σn) bits per symbol We complement this upper bound by a series of examples showing that it is asymptotically tight when σ > n/3 As in the works cited above, here we did not include in this bound the r redundant bits that are always produced by ANS encoders in the worst case (it is an artifact of the initial state of the encoder) After uncovering the constant under the big-O and including this r-bit term, the upper bound for the tANS redundancy that we establish can be expressed as σ log e+r bits over all symbols (not per symbol) Our lower bound examples show that a redundancy of σ−1/4 +r − 2 bits is attainable, for σ ≈ n/3
--- Page 7 ---
An important part of tANS is the initialization of its internal tables, which has a significant impact on the compression performance The lower bound examples work for a wide class of initialization algorithms so that the same 1 redundancy can be observed for any adequate algorithm that generates the tANS tables using only the known frequencies of symbols without processing the sequence itself (however, methods that analyze the sequence might avoid this effect [17, 28]; these methods are usually infeasible in practice due to their relatively slow performance)
--- Page 8 ---
The second contribution of the present paper is a modification of the range ANS (rANS) The rANS is another variant of ANS invented by Duda.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Adaptive encoding capability: The rANS variant can be applied for adaptive mode by first performing one left-to-right pass on a sequence to collect individual statistics per symbol adaptively and then encoding from right to left using these statistics, allowing the decoder to compute statistics adaptively.
-
Faster division operations: The rANS with fixed accuracy k allows the division operation floor x/fa in formula (11) to be performed by simpler instructions like arithmetic and bit operations, which can be implemented in a branchless code for speed enhancement.
-
Reduced redundancy through initialization: Duda’s precise initialization algorithm, or its simplified variant from Algorithm 1, provides a specific structure for the symbol distribution that leads to an upper bound of O(sigma + r) redundant bits per symbol when using the tabled ANS (tANS).
-
Optimized frequency table encoding: For practical applications where sequences are not homogeneous but consist of chunks from different distributions, systems can be designed to split the sequence into blocks and encode each block separately with its own frequency table, potentially relaxing frequencies to minimize total encoding size.
Abstract
Asymmetric Numeral Systems (ANS) is a class of entropy encoders that had an immense impact on the data compression, substituting arithmetic and Huffman coding. It was studied by different authors but the precise asymptotics of its redundancy (in relation to the entropy) was not completely understood. We obtain optimal bounds for the redundancy of the tabled ANS (tANS), the most popular ANS variant. Given a sequence a 1,a 2,,a n of symbols from an alphabet 0,1,,σ-1 such that each symbol a occurs in it f a times and n=2 r, the tANS encoder using Duda's ``precise initialization'' to fill tANS tables transforms this sequence into a bit string of the following length (the frequencies are not included in the encoding): sum a in[0..σ)f a times n over f a+O(σ+r), where O(σ+r) can be bounded by σ e+r. The r-bit term is an artifact indispensable to ANS; the rest incurs a redundancy of O(σ n) bits per symbol. We complement this by examples showing that an Ω(σ+r) redundancy is necessary. We argue that similar examples exist for most adequate initialization methods for tANS. Thus, we refute Duda's conjecture that the redundancy is O(σ n 2) bits per symbol. We also propose a variant of the range ANS (rANS), called rANS with fixed accuracy, parameterized by k at least 1 that in certain conditions might be faster than the standard rANS because it avoids slow explicit division operations. We bound the redundancy for our rANS variant by n over 2 k-1 e+r+k.
Sources
- Asymmetric numeral systems
- Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding
- Interleaved entropy coders
- Encoding of probability distributions for Asymmetric Numeral Systems
- Encoding and Decoding Algorithms of ANS Variants and Evaluation of Their Average Code Lengths
- A tutorial on the range variant of asymmetric numeral systems
Related papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound
- Second-Order Image Characterization with Distortion and Secrecy