Fast and Exact: Asymptotically Linear KL-Optimal Frequency Normalization

Kamila Szewczyk · 2026

Read Fast and Exact: Asymptotically Linear KL-Optimal Frequency Normalization by Kamila Szewczyk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00579.txt.

Introduction

Kamila Szewczyk speeds up a small, crucial step inside data compression. Fast range coders and asymmetric numeral systems replace slow division with bit shifts, which works only when symbol frequencies are normalized to sum to a power of two. Normalization always distorts the distribution slightly, costing compression ratio, measured as added Kullback-Leibler divergence. Szewczyk shows the methods in current use are suboptimal twice over, in both running time and distortion.

The proposed method runs in time linear in the number of symbols and achieves the smallest divergence any normalization can reach. It rests on solving a separable concave optimization problem, which Szewczyk notes may interest readers beyond compression. The result is a drop-in improvement to a primitive that sits underneath widely used entropy coders: same interface, provably best fidelity to the original frequencies, and a faster algorithm to compute it.

Catalog record

CREATORKamila Szewczyk
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.00579

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fast and Exact: Asymptotically Linear KL-Optimal Frequency Normalization Kamila Szewczyk Abstract Range coders and ANS replace empirical probabilities with integer frequencies summing to a fixed M M ; the resulting per-symbol code-length redundancy is exactly the KL divergence of the empirical distribution from the quantized one. Existing normalizers (Giesen, Bloom, Collet) are heuristic or only partially marginal-optimal. We give three provably KL-optimal algorithms: a bottom-up archetype, a bidirectional exchange repair of Bloom’s heap correction, and a top-down window method that runs in 𝒪 ⁡ ( r ) \mathcal{O}(r) , asymptotically optimal in r r , where r r is the number of positive-count symbols. I Introduction Arithmetic coding, range coding, and asymmetric numeral systems (ANS) all encode symbols using a probability model, but fast practical implementations usually replace real probabilities by integer frequencies. In range coders, choosing the total frequency to be a power of two permits divisions by the total to be implemented via bit shifts, accelerating both encoding and decoding substantially. In rANS [ 4 ] , the same power-of-two choice lets decoder divisions and modulo operations by the common frequency denominator be replaced by shifts and masks. Both range coding and rANS therefore lead naturally to the following fixed-denominator normalization problem. Let \mathcal{A} be a finite alphabet, let c_{a}\in\mathbb{Z}_{\geq 0} for a\in\mathcal{A} be empirical counts, and let N=\sum_{a\in\mathcal{A}}c_{a}>0 . The empirical distribution is p_{a}=c_{a}/N . Fix an integer target total M\geq 1 . In entropy-coder applications one usually has M=2^{k} , but the optimization problem and the algorithms developed below do not otherwise depend on the target being a power of two. Choose integer frequencies m_{a}\geq 0 with \sum_{a}m_{a}=M ; the quantized distribution is q_{a}=m_{a}/M . We adopt the standard convention 0\log(0/q)=0 for q\geq 0 , and require m_{a}>0 whenever c_{a}>0 , since otherwise the KL divergence is infinite. The Kullback-Leibler divergence [ 2 , 3 ] of p relative to q is D(p\,\|\,q)\;=\;\sum_{a\in\mathcal{A}}p_{a}\log\frac{p_{a}}{q_{a}}\;=\;\sum_{a\in\mathcal{A}}p_{a}\log\frac{p_{a}\,M}{m_{a}}, and the objective is to choose the integer frequencies that minimize it: \min_{\begin{subarray}{c}m_{a}\in\mathbb{Z}_{\geq 0}\\ \sum_{a}m_{a}=M\end{subarray}}\;D(p\,\|\,q). (1) Operationally, D(p\,\|\,q) is the expected per-symbol redundancy in nats (or bits, depending on the log base) incurred by coding samples from p with a code optimized for q : an ideal coder for the empirical source has expected length H(p) , while one using the integer model q has expected length H(p)+D(p\,\|\,q) . Throughout this paper \log denotes the natural logarithm; the algorithms developed below are invariant under the choice of base, since changing base scales the objective by a positive constant and therefore preserves the argmin. Writing S=\{a:c_{a}>0\} and r=|S| , the requirement m_{a}\geq 1 for a\in S forces M\geq r ; for M<r no finite-divergence solution exists, and we assume M\geq r throughout. Off-support frequencies are never useful in an optimum. If c_{b}=0 and m_{b}>0 , moving one unit from b to any symbol in S preserves the total and strictly decreases the KL divergence. We therefore set m_{b}=0 for b\notin S and work on the support-reduced feasible set m_{a}\in\mathbb{Z}_{\geq 1}\quad(a\in S),\qquad\sum_{a\in S}m_{a}=M. On this set, minimizing ( 1 ) is equivalent to maximizing \Phi(m)=\sum_{a\in S}c_{a}\log m_{a}, (2) since all remaining terms in the KL divergence are constant. We write s_{a}\;=\;Mp_{a}\;=\;\frac{Mc_{a}}{N} for the ideal scaled frequency. The algorithms below are driven by two marginal tickets : a ticket is the change in \Phi effected by a single unit move on one coordinate, evaluated at the current frequency of that coordinate, and serves as the elementary cost or benefit traded by the algorithms below. For j\geq 1 , the gain from increasing symbol a from j to j+1 is \Delta^{+}_{a}(j)=c_{a}\log\frac{j+1}{j}, (3) and, for j\geq 2 , the loss from decreasing it from j to j-1 is \Delta^{-}_{a}(j)=c_{a}\log\frac{j}{j-1}. (4) Both are strictly decreasing functions of j . A support-feasible vector is globally optimal exactly when it satisfies the marginal-exchange condition \min_{a\in S:\,m_{a}\geq 2}\Delta^{-}_{a}(m_{a})\;\geq\;\max_{b\in S}\Delta^{+}_{b}(m_{b}), (5) with the left side interpreted as +\infty when M=r . Lemma 1 . A support-feasible vector m maximizes ( 2 ) if and only if it satisfies ( 5 ). Proof. Moving one unit from a coordinate a with m_{a}\geq 2 to a coordinate b changes ( 2 ) by -\Delta^{-}_{a}(m_{a})+\Delta^{+}_{b}(m_{b}) . Thus a violation of ( 5 ) gives a strict improving unit transfer. Conversely, suppose ( 5 ) holds and let n be any other support-feasible vector. Transform m into n by moving units from coordinates with m_{a}>n_{a} to coordinates with m_{b}<n_{b} . Each successive removal from a fixed source has loss at least its first removal loss, because \Delta^{-}_{a}(j) increases as j is decreased. Each successive addition to a fixed destination has gain at most its first addition gain, because \Delta^{+}_{b}(j) decreases as j is increased. The exchange condition says that every first removal loss is at least every first addition gain, so every transfer in the transformation is non-improving. Hence \Phi(n)\leq\Phi(m) . ∎ The KL divergence is the unique objective whose minimum is the expected code-length redundancy; objectives based on absolute or cumulative rounding error optimize proxies, not the code-length loss itself. Problem ( 1 ) is a textbook separable concave integer allocation [ 5 , 6 ] ; brute force is exponential, the natural greedy takes \Theta(M) heap steps, and the question is not whether it admits a polynomial algorithm but whether it admits one fast enough to sit on an entropy coder’s hot path. Existing fast normalizers are heuristic, or contain a correct marginal step inside an algorithm whose initialization can rule out the true optimum. We close the gap with three exact algorithms, all driven by the same marginal-ticket principle: a bottom-up archetype (Section III-A ), a bidirectional exchange repair of Bloom’s heap correction (Section III-B ), and a top-down window method (Section III-C ) that runs in \mathcal{O}(r) time. Portable and AVX2 implementations (Section IV ) match the fastest deployed heuristic across the alphabet sizes tested while delivering the exact KL optimum. II Prior Art II-A Cumulative Rescaling (Giesen) Giesen’s reference rANS implementation [ 7 ] is widely used in practice: variants of it underlie, for example, the htscodecs library that powers the CRAM genomic file format [ 8 ] , so its normalization step is worth analyzing on its own. The procedure normalizes by rescaling the empirical cumulative distribution and differencing the result. After fixing an order a_{1},\ldots,a_{r} on the positive symbols, set C_{0}=0 , C_{i}=\sum_{j\leq i}c_{a_{j}} , U_{i}=\lfloor MC_{i}/N\rfloor , and m_{a_{i}}=U_{i}-U_{i-1}. (6) Because C_{r}=N implies U_{r}=M , the resulting frequencies automatically sum to M , and the procedure runs in \mathcal{O}(r) time using only a single forward pass with integer multiplications, divisions, and floors. The basic differencing in ( 6 ) has a degenerate case that the reference implementation patches in a separate pass. The increment m_{a_{i}}=U_{i}-U_{i-1} counts the integers in the half-open interval (MC_{i-1}/N,MC_{i}/N] , whose length is Mc_{a_{i}}/N . When the empirical mass c_{a_{i}}/N falls below the grid resolution 1/M (that is, when c_{a_{i}}<N/M ), the interval has length less than one and may contain no integer at all, in which case the two floor values agree and ( 6 ) yields m_{a_{i}}=0 . As a concrete witness, c=(1000,1,1) with N=1002 and M=256 produces U=(0,255,255,256) and hence m=(255,0,1) : the second singleton is hammered to zero. Such a zero

Read the complete text