Synchronizing Probabilities in Model-Driven Lossless Compression
Authors: Aviv Adler
Jennifer Tang
Venue: ICLR 2026 Poster (2026)
Keywords: data compression
model-driven prediction
non-determinism
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: It is well-known in the field of lossless data compression that probabilistic next-symbol prediction can be used to compress sequences of symbols. Deep neural networks are able to capture rich dependencies in data, offering a powerful means of estimating these probabilities and hence an avenue towards more effective compression algorithms. However, both compressor and decompressor must have exactly matching predictions; even small differences from non-determinism (which often happen with learned models due to hardware, software, or computation order) can lead to cascading decoding failures. In this paper, we formalize the problem of prediction mismatch in model-driven compression, and introduce Probability Matching Interval Coding (PMATIC), a model-agnostic algorithm that tolerates bounded prediction mismatch with low overhead. PMATIC works with the predicted probabilities, making it compatible as a drop-in replacement for the arithmetic encoder in model-driven compression tools. We show theoretical correctness and performance bounds for PMATIC, and validate these results on text data. These results confirm that, when paired an advanced prediction model, PMATIC is robust to prediction mismatch while achieving compression rates that out-perform standard modern compression tools.

SYNCHRONIZING PROBABILITIES IN MODEL-DRIVEN LOSSLESS COMPRESSION
Aviv Adler
Jennifer Tang
Analog Garage Analog Devices, Inc. Boston, MA 02110, USA Aviv.Adler@anme aallo.@nnaloooom
Department of Mathematics & Computer Science
College of the Holy Cross Worcester, MA 01610, USA jtang @ holycross.edu
ABSTRACT
It is well-known in the field of lossless data compression that probabilistic next- symbol prediction can be used compress sequences of symbols. Deep neural networks are able to capture rich dependencies in data, offering powerful means of estimating these probabilities and hence an avenue towards more effective com- pression algorithms. However, both compressor and decompressor must have ex- actly matching predictions; even small differences from non-determinism (which often happen with learned models due to hardware, software, computation order) can lead to cascading decoding failures. In this paper, we formalize the problem of prediction mismatch in model-driven compression, and introduce Probability Matching Interval Coding (PMATIC), a model-agnostic algorithm that tolerates bounded prediction mismatch with low overhead. PMATIC works with the pre- dicted probabilities, making it compatible as a drop-in replacement for the arith- metic encoder in model-driven compression tools. We show theoretical correct- ness and performance bounds for PMATIC, and validate these results on text data. These results confirm that, when paired an advanced prediction model, PMATIC robust to prediction mismatch while achieving compression rates that out-perform standard modern compression tools.
1 INTRODUCTION
1.1 MODEI-DRIVEN LOSSLESS COMPRESSION
key task in modern information systems data compression, the process reducing the size of text, images, video, other data so it can be stored and transmitted more efficiently. In lossless com- pression, the data is encoded into a compact representation from which the original can be decoded exactly, in contrast lossy compression, which only permits approximate reconstruction. Compres- sion is generally formalized as the problem of encoding a string of discrete symbols drawn from finite alphabet. In deep learning contexts, these symbols are often referred as tokens. The choice of symbols is domain- dependent: for text, tokens are typically subword units or characters; for im- ages, they may correspond to pixel intensities, color values, or transformed coefficients; and for other domains, analogous discrete representations are used.
Lossless compression works by exploiting regularities the data: common patterns are assigned shorter codes, while rare patterns receive longer ones. These regularities may reflect simple statistics, such as symbol frequencies, or more complex and context-dependent structure and even semantic in- formation. From this perspective, any lossless compression method implicitly defines a probabilistic model of the data source, with compression effectiveness depending on how well the model matches the true distribution. Some algorithms make this explicit, using predictive models that estimate the probability of each symbol given its context (Cleary & Witten (1984)) in order to generate the code; model-drived Others, such Lempel-Ziv-War (LZZW), ZIP,
refer to such algorithms bzip2, achieve their gains through bigtionary-building or transforms, but nonetheless rely on an im- plicit statistical model of the domain
'Thyy can be used create explicit predictive models Delétang et al. (024

---

In model-driven compression, the message is encoded sequentially, and for each symbol the model makes a probabilisticc prediction based on the context of the prior symbols to help the encoder ef- ficiently allocate bits to potential outcomes. To convert the predictive model into a compression algorithm the standard technique is to pair the model with arithmetic coding [Pascq (1976);; Ris- sanen (1976); Guazzo (1980)). Arithmetic coding represents an entire message as subinterval of (0,1), successively narrowing the interval according to the predicted probabilities of each symbol. More probable symbols shrink the interval less and thus yield shorter average descriptions. while less probable symbols shrink it more and thus require more bits. Unlike Huffman coding [Huffman (1952)] (another commonly used technique), arithmetic coding adapts particularly well changing and context-dependent probabilities for each symbol. If the model closely reflects the true distribu- tion of the data, arithmetic coding yields compression rates approaching the intrmmtioontheoreee limit. However, it is extremely sensitive numerically and vulnerable to cascading errors.
Model-driven lossless compression has long history, arguably going back to Shannon (1 (1948), where Shannon tallies frequencies of characters in English, building first, second, and third order Markov model preddeerreessss..... The arithmetic coding approach for model-driven compression was discussed by Cleary& & Witten (1984) and further developed with number of statistical or learned predic- tive models across many domains. Many of these models focus on deriving the prediction model from only the previously seen encoded symbols. In Schmidhuber & Heil (1996). it is clarified that "offline" models are those trained on a separate files and model parametens are shared among all machines responsible for encoding and decoding, In contrast "online" models use the current file to update predictions. Schmidbuber & Heil (1996) use offline.neural networks and get competitive compression ratios, Many other works since, Knoil (2025); Cox (2016); Goyal et al (2018); Bellardd (2019); Liu et al. (2019) have used LSTMss and other recurrent neural networks as predictiye models. Transformers were used as the predictive model in Bellard (2019; 2021): Mao al, (2022).
This general arithmetic coding- coding-based lossless compression technique, particularly when paired with modern neural network-driven predictive models, has been shown to have significant promise in numerous domains beyond text compression. These domains include lossless image compression Toderici et al, (2016); Schiopu et al. (2018); Mentzer et al. (2019); Rhee et al, (2022); Chen et al.
(2024), compression of large numerical datasets such as time-series power data Ma et al. (022)) and neural network checkpoints Kim & Belyaev (2025).
The incredible success of modern neural networks, particularly transformers, for natural language processing has led to increased interest in using the model-driven approach to create more powerful and context-adaptive codes for natural language compression. Recent work by Delétang et al. (2024) shows that off model-driven compression using modern models such as Llama or Chinchilla with arithmetic coding can deliver significant improvement over state-of-the-art lossless compression
algorithms across domains including text, .nd vision. Concurrently. M-d-iriyen text compression
tools such as LLMZip [VValmekkam al. (2023)) and llamazzip [Buzanis (2024)) were introduced to take advantage of the capabilities of these advanced models.
1.2 LLM NON-DETERMINISM AND PREDICTION MISMATCH
Despite its promise, LLM- compression faces serious practical obstacles. For instance, the LLM inference pipeline must run for each token during the encoding and decoding steps, which can make the process prohibitively slow, since large language models are often computationally expensive to execute. This also requires the model, which may contain many gigabytes of parameters, to be stored, thus adding a large overhead cost in memory as well. Recent work has also been done to address concerns about the computational performance of LLM-driven compression, such as Mittu et al. (2024) improving speeds for LLMZip.
Another significant challenge, which we call prediction mismatch, arises when compressed data is transmitted between encoder and decoder running on different machines. As noted in Witten et al. (1987), arithmetic coding with adaptive probability models, "It must be possible for the decoder to produce exactly the same probability distribution in the same context". Achieving this is difficult with modern machine learning models due to non-determinism.
-on-determinism in the setting of machine learning and scientific computing means that multiple runs of the same program with identical inputs (and identical random seeds) can produce different outputs [Cooper et al. (2022); Semmelrock et al. (2025)). One source of non-determinism occurs
2

---

in GPU hardware: floating point operations which are performed in different order may result in different outcomes due to rounding. These small numerical deviations, in a full inference pipeline run, can cascade into large differences in what model predicts [Shanmugavelu et al (2025); Chen et al. (2022)). GPU libraries, like CUDA and cuDNN, state specifically in their documentation that they do not guarantee determinism or reproducibility in many circumstances, such when different versions or architectures are used INVIDIA Corporation (2025arb)) The effects of non-determinism in CUDA is studied in Eryilmaz al (2024) where they note that non-determiiism is likely remain in CUDA because of the runtime benefits CUDA gains through using parallelisp Non-determinism
GPUs have also been examined and explored by Morin & Willetts (2020). Coakley et al. (2022)
and Atil et al. (2025) examined the issue of non-determinism experimentally, finding significant variability, and Schlögl et al, (2023) study its causes.
Applying arithmetic coding directly under these conditions is usually immediately fatal: even subtle differences the encoder and decoder probability distributions can result in an incorrectly decoded token, which then cascades to the rest of the message as it changes the context of subsequent tokens.
the mismatch between the encoder and decoder distributions arbitrary, recovery impossible, as the decoder predictions yield no information about the encoder predictions. However, if the mismatch known to be small, the encoder and decoder can exploit this closeness to reach exact agreement on third probability distribution. This robustness incurs cost in compression efficiency: the encoder will generally have to send extra information to ensure agreement, and the agreed probability distri- bution may be less accurate than the original predictions. We refer the problem of constructing shared distribution while minimizing the cost as probability matching.
Concurrent work (Hu & Tang (2026)) addresses closely related variant of mismatch-toleran coding by proposing an alternative algorithm based on Huffman coding-like approach.
Recent work has also explored the possibilityy of addressing non-determinism its source by de- signing deterministic neural network backends, motivated by the need for researchers to share repro- ducible results [[e & Lab (2025). Yuan et al, (2025)], though cost in performance. Mitigation of non-determinism can be complementary with our approach by reducing mismatches so that they fall within the tolerance limits of robust coding algorithm.
1.3 CONTRIBUTIONS
This work introduces the problem of robust coding for prediction mismatch in model-driven lossless compression and proposes PMATIC Probability-Matchhr Interval Coding) to address it. PMATIC is designed to convert any predictive model into compression algorithm which is robust to bounded prediction mismatch, and be a drop-in replacement for arithmetic coding in model-driven compres- sion. This work also shows the following results:
Theory:
We prove that PMATIC guarantees correct decoding under a simple and general model of bounded prediction mismatch (Section 2.1). 1), and give theoretical bounds on the cost incurred to ensure this robustness.
Practice:
We demonstrate experimentally that LLM-driven compression using PMATIC achieves compression ratios significantly better than current standard methods, while re- maining robust to prediction mismatch.
In Section R we validate our approach by applying PMATIC on text data the presence of both real and synthetic prediction mismatch, and give the first proof of concept that non-determinism in model-driven compression can addressed via robust coding algorithms.
2 PROBLEM STATEMENT
Consider the case where an encoder and decoder are using the same model (such specific LLM with the same weights) to compute next-token probabilities over an input string = x(1)x((2 ... x(n) whose entries (r) are taken from a finite alphabet of possible symbols. We use the following notation: the é-symbol prefix of x is denoted as x¹ = 2(1) ... x0)); the set of all finite strings drawn
from the alphabet A is denoted as A" Up20 A'
3

---

Typically, an LLM computes its next-token probabilities by computing a real-valued (or, rather, floating-point valued) weight, called a logit, for each outcome and then applying the softmax function to the vector of logits. 8 Let functions E M : AA" - R take string of symbols (the context) and return a logit value for each symbol the alphabet, representing what happens when the model is run for inference at the encoder and decoder ends, respectively. We denote the predictions of E M for token as logit vectors
u(i)= == ( and v(2) == M Dec (a*
(1)
which respectively induce probability vectors p(i) softmax and q(i) softmax(u(i)). i.e. for any i E [n] and & E A.
eulOu
cd(s)e
p()) = softmax(u(1)) (u))) = Ejen ent)y and q(i) = softmax(v(1)) k = Eyc en(o)
(2)
When the token number é fixed, we may drop it from the notation for clarity, so that the encoder and decoder return logit vectors which induce probability distributions p, respectively.
We denote the encoding and decoding algorithms (also called compressing and decompressing, re- spectively) as functions whose operation depends on an LLM model (M and M respectively) as well as on more traditional inputs. Specifically, the encoder takes LLM M Fin and input token string x and returns bitstring which the encoded input. Then, the decoder takes b and its own LLM Dee and returns a decoded string f:
Enc(M (0e
and Dec(M bb 5.
Given a constraint on the difference between M lin and M Dects s outputs on any given context, we say that the algorithm is mismatch-toleraant with respect to that constraint if, for all n _M Dee that satisfy the constraint: Dec(MDse, Dec Enc(M Bne, z)) for all x. The goal is to design algorithms which can tolerate given amount of mismatch between the encoder and decoder probability distributions while minimizing the cost in compression efficiency.
2.1 THE BOUNDED PREDICTION MISMATCH SETTING
Since the encoder and decoder are using the same LLM on the same inputs, it reasonable to assume that they obtain logits whose difference is bounded by some reasonably small > 0. A natural choice for this is to assume that their difference has bounded Lx norm (i.e. elementwise): |u ofloc := m [ug uyll S We first define measure of difference between two probability distributions:
Definition The conditional total variation distance (dew) between two probability distributions p. on an alphabet A is defined as the maximum total variation distance (dmy) of and after conditioning on some (nonempty) C A, i.e.
d g) = max (c.(p(-1))
(4)
449CA
where pl11S) and q(-1S) are, respectively, and conditioned on the outcome being in S.
Note that there is no divide-by-zero issue with conditioning on any (nonempty) S since all probabil-
ities are induced via the softmax function and hence strictly positive. Bounded prediction mismatch then bounds conditional TV distance:
Proposition uf v induce probability distributions p softmax(u) and q softmax(u) over A. and Iu ol < E, then (p. g) S
Proof. Using the definition of TV distance, the conditional TV distance can rewritten
(p. = max
(p(S*IS) - (())
(5)
04SCA
S'CS
max (p. = max 1 Se
max (p(S*1S) ((55)))
(6)
la-ol Se
BASCA S'S
max
Ip(S*
g(S+1S)
BASCA
| Se
S'C8
Foor simplicity the standard softmax with 'temperature' parameter of 1.
4

---

So, if max Se
(1S*(S)-(($179 S for all S C S C A, then max (p S-
In other words, the conditional TV distance between p. induced by |u-ell>o I can be bounded by first fixing S S S A and then bounding [p(5* q( (S]])) over all p, q whose logits are within
e of each other in Lo distance. We assume WLOG that the u, v maximizing (p(S*(S) - ((50 (5)5) 5) has
q(S*) (S) > p(S*(S) (otherwise S can be changed into S*,5", so the goal is to maximize (5 S)
(S)* given the logit - bound. This is achieved by letting
Uk uk + for k E 5 and
" for l E 5
(8)
Let = p(5 and q² = (SS)))) which are both scalars in [0, 1]. Then, given
Exesi ex
e5p'
q' Ekes et Ekesrgg ex eFp' + te t pr)
(9)
q p' < max |-E|U,1]
eepp + + (1) -p') = tanh
epp'
(8) c
2 5
(10)
Tracing this bound back the conditional TV distance concludes the proof
THE PMATIC ALGORITHM
The Probability Matching Interval Coding (PMATIC) algorithm addresses prediction mismatch by ensuring that the encoder and decoder use a common probability distribution for each token. The first step of PMATIC each token with a length l = [log, (1 A () bitstring; we call this bitstring the token's longforme and each bit in is token bit. PMATIC encodes these tokens bits with arithmetic coding using next-bit conditional probabilities derived from the token's 's encoder prediction vector. At each step, the next- bit prediction a scalar in [0, 1] giving the probability that the token bit equals The key idea is to divide the interval [0, 1] into a set of bins (disjoint equal-length intervals which cover [0. 1)). Then, instead of using their exact predictions, the encoder and decoder use either the center of the bin their predictions fall into or the nearest boundary between two bins; which one to use is decided by the encoder and communicated to the decoder by use of auxiliary 'helper' bits, which are also sent via arithmetic coding. This procedure can be viewed quantizing the probability of each token bit
convert the input token string into bitstring using dictionary that associates
For any token F, in the message, we denote its longform by b, = b,(1) (2) and define the following parameters and notation:
5 > O, which represents the amount of prediction mismatch (per bit) which the algorithm can tolerate, as measured by conditional TV distance.
0 is the radius of the quantization bins (so the width of bin is 2r); r will be chosen to maximize performance given 6. We will assume that r 1/(2m) for some integer m; in practice this entails rounding r or down slightly to the nearest such value. We also require the constraint that > 28.
Let h((p) p log (5) + (1 p) log ( be the binary entropy function (the entropy of Bernoulli random variable with probability p). and H (p) be the more general entropy function for probability vector p over finite set.
Let dz. (plg)= p log (?) (1 p) log (1-)) be the binary Kullback Liebler divergence (the divergence between Bernoulli random variables with probabilities p, 4)
. Let S {a E 10, a-1 o/-1 1 } be the longforms whose first j bits match 6,
FFor a full explanation the maximization step in (10). see Appendix A. "This term also used in Hu & Tang (2026) to describe a similar construction.
'Note that when say that bit is encoded or decoded using probability value mean that the corresponding arithmetic coding step performed using the probability distribution (1-p.
P. p) set the intervals.
5

---

0.125
probubility not near edge
0.01
helper bit =00 quintaze original binning
0.25
10
probabilzyy helper bie 1
spamisee altematioe bimning
0.0
0.25
0.50
0.75
1.0
Examples of PMATIC helper-bit bit and quantization logic for two cases, one where the helper bit and one where the helper bit
Figure 1:
3.1 THE PMATIC ENCODER
Consider encoding the jith bit, 6,()), of token z₃. Let the encoder and decoder prediction vectors and q(z) == softmax(M" (x²-1)) The
for token be, respectively, p(i) = (attmaxM"""(""" predictions for the jth bit b, (j) for the encoder and decoder, conditional on the prior bits in 6,. are
() P. p()) (i) 1 [ and q,(5) P 10 (b) 1 1|
(11)
These can be computed directly using p(i) (or (())) by setting all values outside of / to 0 and renormalizing to get the conditional probability distribution.
The interval [0, 1] is then split into radius-r intervals, which we call bins, 1,, li. Im where m
1 1/(2r) (which, as assumed above, is an integer) and 4 = [2r(k= 1), 2rk]. The center of bin J is therefore Cg == 2r(k 1) + r. and we denote the ō-interior of Ig (the set of points in Ig at least away from any point outside I by
2r 8)
if kk= = if m
1
[2r(m 1) + 8,
(12)
[2r(k: - 1) + 8, 6,2rk-- 8]
k & 1, m
15, Jo get special definition as they each have an edge next to the edge of [0, 1].
Note that if (J( E Iğ and (f) - 4, (j)l < 6, then (,()) E Ig. and that if p;(1) $ for all k then there is instead unique integer k + 1, m for which [2rk pe(i) < 6.
In addition to the token bit (j), PMATIC encodes (prior to the token bit) helper bit
bf E 1 for some
(13)
otherwise
This is encoded with arithmetic coding using probabilities p' == 5/r for the helper bit and
P.()) = Cx = 2r(k - 1)
if (2)() E I 2rk for the integer ks s.t. 12rk - p,(i) < 8 otherwise
(14)
for the token bit. The probability p, (j) is intended as the common probability of token bit j that both the encoder and decoder agree
See Figure for example.
The intuition for the helper bits is that when pj( E Tg. the encoder knows that the decoder's prob- ability 9) I (the same bin), so the encoder quantizes to the bin center and tells the decoder to do the same by sending the helper bit b((r) O. If p;(i)) is not in the ś-interior of its bin, the encoder no longer knows that the decoder probability lies in the same bin. However, in this case both probabilities must be near the same boundary point between two bins, so the encoder quantizes to the nearest boundary point and tells the decoder do the same by sending the helper bit bg 1. In either case, they agrec on the probability to use for encoding and decoding. The probability of being the 5-interior of bin is R 8/r, which is very small if >> This gives the helper bits low entropy and hence makes them also highly compressible via arithmetic coding.
To summarize, given a token 2; and context i-1, the PMATIC encoder does the following:
1. Computes p(i) = softmax Boftmax(MMnmg (M (I² 1)), gets the longform b, corresponding to x,, and computes the conditional next-bit probabilities p,)1),.. P, (f) E [0. 1).

---

2. Computes for each b, ()) the helper bit bf(5) and quantized probability P,(1)
13 (14)..
3. Encodes the bitstring (1),,, (1) ... (()),(()) using arithmetic coding, where the encoding probability for helper bit b(())
o/r and for token bit (,( is (t()).
An example of the encoding process for one token is given in Appendix A.2
3.2 THE PMATIC DECODER
The PMATIC decoder takes the encoded message y and decodes it sequentially in pairs of bits. Each pair consists of a helper bit and a token bit; the helper bit is decoded first using p' = 5/r as the probability (since helper bits are always encoded using this probability), and determines the quantized probability to use. Analogous to the encoder next-bit prediction, let the decoder next-bit prediction for bit j of token be denoted 9,()). Then the decoder decodes the token bit using the quantized probability:
[Cp for k s.t. q,()) E lk 22k for k E {I,..., 1 s.t. 12rk 9,(iيl minimized
if if(()) 0
a,(5)
(15)
64())
After decoding all the bits, the helper bits are discarded and the token bits are converted back into the token using the longform dictionary. The token is then added to the context of the predictive model and predictions are generated for the next token. PMATIC is successful when q (j) the always the same as (j). This is discussed in greater detail in the next section.
4 ANALYSIS
We wish to: (i) show PMATIC ensures correctness the conditional TV distance between the encoder and decoder token predictions is at most ö; (ii) show (expected) theoretical performance bounds. Since we compress in bits, logarithms are base-2 unless noted otherwise.
4.1 CORRECTNESS
Theorem 1. If dew (ee() q(1) < 8, then q.(3) Pa(3) for all (i.e. the encoder and decoder will agree on the quantized probabilities for all bits corresponding to token x,))
Proof. Consider bit of token without loss of generality we assume that all previous bits in i and all previous tokens were decoded correctly (since, if any bits are incorrectly decoded, there must be a first one). Since (p(i, q()) d, we know that (p; q,(i) < ô (since P,(i), q, (i) derived by conditioning p(i), (()) on the set S -)
First, the decoder will decode the helper bit B(()) using the probability 5/r. Since 8/r fixed and used for all helper bits, the encoder and decoder probabilities match and the helper bit is decoded correctly. Now we consider two cases: b(() = O. and (((i)= =
If ((()) = 0, this means that computed encoder next-bit predictor P.()) falls the 8-interior Iğ of some bin; since (p,(5) q. (j) S 8, this means q, (j) Tn (not necessarily the 5-interior, just the bin itself). Thus, since both the encoder and decoder quantize to the center eg of the bin, we have
(. (,( C and the token bit is encoded correctly.
If (G)) = then there is some is the boundary between two bins). Then, since we set 26 and bins have width 2r:
{1,... m - 1} such that (p,()) 2rk| S (note that 2rk here
(p,(s) krk| < = 1q,(5) - 2rk < 28
(16)
(q,(5) 2rk | 2 2r 26 26 for any integer k' + k
(17)
7,(5) 2n = P.().
(18)
Thus, in either case, the encoder and decoder agree on the next-bit probability for by(j) and the decoder will decode the bit and update the arithmetic code interval correctly.
O
Note that, by Theorem and Proposition | if the LLM has logits that differ by at most between the encoder and decoder, then PMATIC using ő = e/2 guarantees correctness.
7

---

4.2
COMPRESSION Loss
For the compression performance analysis, we make the following simplifying assumptions:
The encoder's next-token probabilities are the true probabilities. so the expected length in- crease per bit b; (j) is d (P,( (Cover & Thomas, 2006, Thm 5.4.3).
Within each individual bin, the encoder next-bit probability is roughly uniformly distributed, so probability of being within d of a bin boundary is x 6/r (this is an approximation since we ignore the fact that the first and last bins have only one relevant boundary each). This is a woosst-case non- adversveraliall assumption: next-bit bit probabilities do not disproportionately cluster near bin boundaries, but we otherwise know nothing about them.
We consider the compression loss of PMATIC over traditional coding, i.e. the extra message length incurred by PMATIC in order to tolerate conditional TV distance bound of 5 with a bin width of r. This loss comes from two sources:
han--mssmacch-toleerae arithmetic
1. Helper bit encoding: Since helper bits are assumed be Bernoulli with parameter 5/r, the expected extra encoding length per helper bit is the binary entropy h(6/r) y
log (g) +
(-A) log log (--x) If >> 6, the first term dominates and the entropy is = A log (
2. Quantization loss: The quantized probability p,()) is different than the true probability P, P,()). incurring quantization loss of dg. (p))
Since < ()( 1- and (j) P,O' < r. this de (ilا,() log(e)r,
since KL. divergence is bounded above by x² divergence (Polyanskiy & Wu, 2025, Ch. 7):
(p,(5) - p,(1))² S 2 log(eer P,0)(1 - --,(0)
(p (PIP,))) < log(e)
(19)
since the numerator is 22 and the denominator is 2 (1/2)r.
Note that these losses respond opposite directions when the bin radius r increased: larger bins mean lower helper bit entropy but a bigger difference between the true probability and the quantized probability. This means that setting r to balance the loss terms gives an approximate minimizer of the objective function: any other r" a will make one of the loss terms larger, so balancing the loss terms incurs a total loss of at most 2 times the optimal. This is achieved (approximately) with
5 log (7²
8 log
2 2log(e)r
= = r
(20)
and yields a total loss on the order of O 1og
5 EXPERIMENTS
We test PMATIC in model-driven text compression algorithms driven by: LLaMA 3.1 8B (4-bit
quantized) |Grattafiori et al. (2024)), Mistral 7B v0.1 (3-bit quantized) and Qwen 2.5 Instruct 7B (3-
bit quantized), whose alphabets have respective sizes of 128, 256 tokens, 32, 000 tokens, and 151, 643
tokens. We test PMATIC with three robustness settings ó, with bin width r chosen according to (00). rounded to nearby reciprocal of an integer (in order to get fully uniform bin sizes): (i) 5 0.00001
and = 0.005; (ii) 5 = 0.001 and r 0.05; and (iii) 8 = 0.1 and r = 0.125.
We compare PMATIC against (i) non-robust model-driven text compression (with the same models) using standard arithmetic coding, and (ii) set of traditional or modern text compression algorithms, including gzip (widely used in practice) and CMIX (known for achieving state-of of-thheart compres- sion ratios). Comparing PMATIC against standard arithmetic coding within the same model-driven compression pipelines shows the 'robustness overhead' cost from PMATIC (how much additional information is sent to ensure robustness of the chosen level' while the comparisons to traditional
While there are existing benchmarks for model-driven compression [almeekam et al (202)). Mittu et al. (0244). the effectiveness of dodel-driven compression depends heavily on the model and setting used. Thus, to isolate the rohustness-effciine tradeoff produced by PMATIC, we compare PMATIC with standard arithmetic coding within auherwise-identicl pipelines.
8

---

text compression algorithms validates the effectiveness of the model-driven compression pipeline even with the additional overhead from ensuring robustness.
We run our experiment several datasets: (i) the first (nearly) 10 MB of the enwik8 benchmark Hutter (2006), a collection of Wikipedia articles from 2006; (ii) 1000 randomly selected articles from Wikipedia; (iii) Hamlet by Shakespeare and (iv) Emma by Austen, in English; (v) Candide by Voltaire in French; and (iv) Dream of the Red Chamber (21 by Cao Xuewin, Chinese.
Additional implementation details are in Appendix A.3
5.1 RESULTS: COMPRESSION RATIO
Candide French
Enwik8
Wikipedia
Hamlet
Emma
Chinexe
LLM--asse compression (with and without PMATIC)
no PMATIC
0.0780
0.0700
0.0878
0.0606
0.1024
Meta
6 10-5,
0.005
0.0847
0.0878
0.0952
0.0660
0.1102
LLaMA 3.1
6 10-3.r 0.05
0.1353
0.1330
0.1514
0.1099
0.1683
6 10-2,r 0.125
0.2492
0.2085
0.2772
0.2113
0.2971
PMATIC
0.0867
0.0737
0,1501
0.1066
8 10-5,r 0.005
0.0940
0.0794
0.1587
0.1134
Mistral 7B
6 10 r = 0.05
0.1481
0.1198
0.2167
0.1595
6 10 10-2,r 0.125
0.2699
0.2106
0.3447
0.2610
no PMATIC
0.0881
0.0824
0.1102
0.1183
0.1150
0.1268
Qwen2.5 7B
8 10-5, , 0.005
0.0951
0,0880
0.1177
0.1253
0.1231
0.1345
Instruct
8 10-3, 0.05
0.1501
0.1315
0.1755
0.1738
0.1831
0.1879
6 = 10 2, = 0.125
0.2751
0.2297
0.3067
0.2825
0.3171
0.3073
Standard baselines
emix
0,3558
0,3644
0.3865
0.3797
0.3709
0.3824
brotli
level 11
0,3524
0,3546
0.4361
0.3918
0,4442
0.4733
bzip2
level 9
0.4537
0,4605
0.4636
0.4539
0.4494
0.4727
level 9
0.4647
0.4904
0.5111
0.4973
0.4866
0.5192
gzip
level
0.4601
0.4759
0.5007
0,4852
0.4768
0,5305
zstd
level 22
0,4676
0.4773
0.5034
0.4882
0.4851
0.5544
Table 1: Compression ratio compressed size
uncompressed file size" lower is better) across different models, PMATIC pa-
rameters, and datasets. PMATIC overhead (cost of gaining mismatch robustness through PMATIC) for each parameter setting can computed by subtracting the corresponding 'no PMATIC' com- pression ratio from the PMATIC compression ratio corresponding to that robustness setting.
Compression efficiency results are given in Table (where compression ratios are given as compressed file size incompressed size" following the convention of Delétang et al. (024))) and show that PMATIC pro- vides robustness numerical deviations while keeping favorable compression ratios traditional algorithms, across the models and settings we tested. Even in the most robust setting, compression with PMATIC still achieves significantly better compression rates than traditional compression.
We also studied whether the 'worst-case non-adversarial assumption that the next-bit probabilities have 0/r chance of falling within 8 of bin boundary (and thus setting the corresponding helper bit to 1) was accurate. Table g compares the expected fraction of helper bits set to 1 (under the uniformity assumption) to the actual fraction. The last column gives the fraction of the size of the compressed files dedicated to helper bits under each robustness setting, showing how much improve- ment might be obtained by improving the compression of the helper bits alone. The results show that helper bits are considerably less likely to be 1 in practice than the uniformity assumption indi- cates. This is because the next bit is often essentially certain (probability close to or 1, which do not fall near bin boundaries), particularly when earlier bits have narrowed down possible next token. Because PMATIC relies on low helper-bit bit entropy to efficiently communicate them, a lower fraction of helper bits being 1 is better; in implementation. the helper bits were encoded with arithmetic coding using the uniformity-ase infformity-assumption probability of 6/r, but these results indicate that using more accurate helper bit probabilities can yield significant improvement.

---

Parameter settings
Expected helper fraction
Measured helper fraction
Helper bit cost
no PMATIC
8 10- r r= 0.005
0.002
0.00051
0.04594
8= 10-3 r= 0.05
0.02
0.00368
0.18947
= 10
0.125
0.08
0.01145
0.34073
Table 2: Helper bit behavior averaged across different PMATIC robustness parameter settings, Ex- pected helper 1 fraction is ö/r, approximately the fraction of helper bits which would be set to if next-bit probabilities are uniformly distributed; Measured helper 1 fraction is the actual fraction of helper bits that were 1, across all models and datasets; and Helper bit cost is the fraction of the size of the compressed files dedicated to storing helper bits. The results indicate that in practice, next-bit probabilities are much less likely to fall within ō of bin boundary than the uniformity assumption implies, and that accounting for this could make PMATIC considerably more efficient.
5.2 RESULTS: ROBUSTNESS TO SYNTHETIC AND REAL NON- DET-RRINSEMMM
To test the theoretical correctness of PMATIC (Theorem D. we added IID symthetic noise from [-26, 26] (conforming to the theoretical guarantee in Proposition to each predicted logit before decoding. As expected, all files were decoded successfully.
We also smaller number of tests PMATIC under real non-determinism resulting from coding and decoding the output on two different machines using Meta Llama 3.1. In these tests, the encoding and decoding were performed on two different Apple laptops (MacBook Pro) using, respectively, the Apple M2 Pro chipset with a 16 core GPU and the Apple M4 Max chipset with 32 core GPU. This test was conducted split into 50 files each with size 5 KB (both are subset of the files used in the compression ratio tests). No files were correctly decoded when using arithmetic coding (no PMATIC) or PMATIC with 5 = 0.001. However, when tested with parameter setting 5 = 0.01, all files were correctly decoded. This matched preliminary explorations indicating that 8 = 0.01 a reasonable estimate for the upper bound on the discrepancy in Llama 3.1 outputs between the two laptops. See Appendix A.4 for more.
100 Wikipedia articles and the first 250 KB of Emma,
6 FUTURE WORK
While this work has focused on the initial implementation and validation of PMATIC using text models and datasets, we view the application of PMATIC to compression in other domains, such as images, to be a natural extension.
Furthermore, PMATIC is designed for the bounded prediction mismatch setting; however, logit mis- matches arising from non-determinism may obey stochastic bounds rather than strict upper bounds, as suggested by our own observations (see Appendix A.44.. While this could be largely dealt with by increasing the robustness far enough that the likelihood of mismatches exceeding it are vanishingly unlikely, this comes with significant inefficiency and cost, and is likely to not take full advantage of the structure of the stochastic mismatch. Therefore, it would be interesting and useful to extend mismatch models, which could he identified through a
PMATIC for relevant stochastically-bouus more detailed investigation of the statistical properties of model non-determinism.
Our results also indicate that PMATIC could be significantly improved with better helper-bit prob- ability estimation (see Table 2). rather than relying on the uniformity assumption that s ó/r of the helper bits will be 1, warranting further investigation of how to best do so and how much improve- ment can be achieved. On the other side, the fundamental limits of model-driven compression under prediction mismatch (that is, how much additional message length is mathematically required to cor- rect a given amount of potential mismatch) remain unknown, and further work on the mathematical and information-theores properties of the problem will be needed to address this.
Finally, model non-determinism remains a significant challenge several contexts outside of model- driven compression, such as ensuring reproducibility of experimental results in machine learning. It may be interesting to explore whether PMATIC might offer helpful tools for these contexts.
10

---

ACKNOWLEDGEMENTS
We thank Cordelia Hu for her assistance in dataset preparation and configuring the experimental pipeline used this work. We also thank Ali Jadbabaie for his advice on this project.
REFERENCES
Berk Atil, Sarp Aykent, Alexa Chittams, Lisheng Fu, Rebecca J. Passonneau, Evan Radcliffe, Guru Rajan Rajagopal, Adam Sloan, Tomasz Tudrej, Ferhan Ture, Zhe Wu, Lixinyu Xu, and Breck Baldwin, Non-determinism of "deterministic" Ilm settings, 2025. URL https///arxiv.org/bbbs.. 08.04667.
Fabrice Bellard. Lossless data compression with neural networks. URL: htts://bellard org/nncphn- ncp. pdf. 2019.
Fabrice Bellard. Nnep v2: Lossless data compression with transformer. Preprint at Fabrice Bellard https://bellard. org/nncp/ncc__V2 pdf. 2021.
Alexander Buzanis. Ilama-zip: An Ilm-powered lossless compression tool. https://github.comm/lle
xBuz/Ilama-zip, 2024. Commit main branch; accessed 2025-05-19.
Boyuan Chen, Mingzhi Wen, Yong Shi, Dayi Lin, Gopi Krishnan Rajbahadur, and Zhen Ming (Jack) Jiang. Towards training reproducible deep learning models. In Proceedings of the 44th Interna- lional Conference on Software Engineering, ICSE 22. pp. 2202-2214, ACM, May 2022. doi: JCSE 10.1145/35100033351006 URL http://ddx.doi.or//100 10. 145111110//3533335
Kecheng Chen, Pingping Zhang, Hui Liu, Jie Liu, Yibing Liu, Jiaxin Huang, Shiqi Wang, Hong Yan, and Haoliang Li. Large language models for lossless image compression: Next-pixel prediction in language space is all you need. arXiv preprint arXiv:2411.1244. 2024.
J. Cleary and I. Witten. Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications, 32(4):396-400 1984, doi: 10.1109TTCO..I 198..99994.0000090
Kevin Coakley, Christine R. Kirkpatrick, and Odd Erik Gundersen. Examining the effect of imple- mentation factors on deep learning reproducibility. In 2022 IEEE 18th International Conference on e-Science (e-Science) pp. 397-398. JEEE. October 2022. doi: 10. 10.110/9esiieme5557..2222. 0056. URL
A. Feder Cooper, Jonathan Frankle, and Christopher De Sa. Non-determinism and the lawlessness of machine learning code. In Proceedings of the 2022 Symposium Computer Science and URL
Law, Law. CSLAW 22, pp. 1-8, ACM, November 2022. doi: 16.1144//511225.355555 http://dx.doi.org/// 10tp:/001111110 wtw.a//.....r/11111111151161661. 15t.11144//511155555000
T.M. Cover and J.A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications
and Signal Processing). Wiley-Intersciennee, USA, 2006. ISBN 0471241955
David Cox. Syntactically informed text compression with recurrent neural networks. arXiv preprint wrXiv:168..02893 2016.
Grégoire Delétang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hut- ter. and Joel Veness. Language modeling is compression, 2024. URL http://anniv.orr//bb/2309 _10668.
Bahadir Eryilmaz, Osman Alperen Koras, Jorg Schlotterer, and Christin Seifert. Investigating the Impact of Randomness Reproducibility in Computer Vision: A Study on Applications in Civil Engineering and Medicine In 2024 IEEE 6th International Conference on Cognitive Machine Intelligence (CogMI), pp. 265-274, Los Alamitos, USA. October 2024. IEEE Computer So- cicty. doi: 10. 19990/992M2222262202222 000002446.224000444 URL http:://loliccccooputttsscceyrry 1rrg://0.tttto/100011111 10.1 MCCooMM162246.2224.000
11

---

Mohit Goyal, Kedar Tatwawadi, Shubham Chandak, and Idoia Ochoa. Deepzip: Lossless data com- pression using recurrent neural networks. CoRR, abs/1811.08162, 2018. URL http://arxiv.orgg $/1811.08162.
Aaron Crrattaaiorri Dubey, Abhinav Jauhri, et al. The llama 3 herd of models, 2024. URL
https:/4arii..orraa//440....7
M. Guazzo. A general minimum-redundane source-coding algorithm. IEEE Transactions on Infor- mation Theory, 26(1):15-25, 1980. doi: 10. 109//1// 1980. 1056143.
Horace He and Thinking Machines Lab.
Defeating nondeterminism in Ilm inference. Thinking Machines Lab: Connectionism, 2025. doi: 10. 00.64434/mm1.222509 O.
Cordelia Hu and Jennifer Tang A model-driven compression algorithm resistant to mis- match, 2026. URL hupps//arriv.oorgaab22261111.
David A. Huffman, A method for the construction of minimum-reduudamee redundancy codes. Proceedings of the IRE, 1099:1008--101, 1952. doi: 10.1 1AA.1///RRRRO..92222725555
Marcus Hutter. The hutter prize for lossless compression of human knowledge. http://prize.hutterl net/, 2006. Accessed: 2025-09-11.
Yuriy Kim and Evgeny Belyaev. An efficient compression of deep neural network checkpoints based on prediction and context modeling, 2025. URL bttps://arriv.orr/aa/225566...
Byron Knoll. cmix: A data compression program. https:/www..byyookoooloo./oo///m 2025. Accessed: 2025-09-23.
Qian Liu, Yiling Xu, and Zhu Li. Deemac: A deep context model for high efficiency arithmetic coding. In 2019 International Conference on Artificial Intelligence in Information and Communi- cation (ICANI)), pp. 438 443. IEEE, 2019.
Zhoujun Ma, Hong Zhu, Zhuohao He, Yue Lu, and Fuyuan Song. Deep lossless compression algo- rithm based arithmetic coding for power data. Sensors. 22(14). 2022, ISSN 1424-8220. doi: 10.3390/:22153331 URL https://www http://wwwwpccoo//////o cttp:/44-mm////m/m--///1 014448220/22211//333
Yu Mao, Yufei Cui, Tei-Wei Kuo, and Chun Jason Xue. Trace: fast transformer-based general- purpose lossless compressor. In Proceedings of the ACM Web Conference 2022, pp. 1829-1838, 2022.
Fabian Mentzer, Eirikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Practical full resolution learned lossless image compression. Proceedings of the IEEF/CVF conference computer vision and pattern recognition, pp. 10629-10638, 2019.
Fazal Mittu, Yihuan Bu, Akshat Gupta, Ashok Devireddy, Alp Eren Ozdarendeli, Anant Singh, and Gopala Anumanchipalli, Finezip: Pushing the limits of large language models for practical lossless text compression. arXiv preprint arXiv:2409. 17141, 2024.
Miguel Morin and Matthew Willetts. Non-determinism tensorflow resnets, 2020. URL https: Surziv.org/abs/001111339
NVIDIA Corporaton.. NVIDIA cuBLAS Library Documentation, 2025a. URL https://docs.nniida. com/cuda/cublas// Version: CUDA cuBLAS.
NVIDIA Corporation. NVIDIA cuDNN Backend Odd: and Ends (Determinism and Repro- ducibility), 2025b. URL
http://www..oooooooeoeeecooooaad hisc.html, cuDNN Developer Documentation.
Richard Clark Pasco. Source coding algorithms for fast data compression. PhD thesis, Stanford University CA, 1976.
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2025.
12

---

Albert Reuther, Jeremy Kepner, Chansup Byun, Siddharth Samsi, William Arcand, David Bestor, Bill Bergeron, Vijay Gadepally, Michael Houle, Matthew Hubbell, Michael Jones, Anna Klein, Lauren Milechin, Julia Mullen, Andrew Prout, Antonio Rosa, Charles Yee, and Peter Michaleas. Interactive supercomputing on 40,000 cores for machine learning and data analysis. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pp. 1-6. IEEE, 2018.
Hochang Rhee, Yeong Il Jang, Seyun Kim, and Nam Ik Cho. Le-fdnet: Learned lossless image compression with frequency decomposition network. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 6033-6042, 2022.
Jorma Rissanen. Generalized kraft inequality and arithmetic coding. IBM Journal of research and development, 20(3):198-200 203, 1976.
Ionut Schiopu, Yu Liu, and Adrian Munteanu. Cnn-based prediction for lossless coding of photo- graphic images. In 2018 Picture Coding Symposium (PCS), pp. 16-20. IEEE, 2018.
Alex Schlögl, Nora Hofer, and Rainer Böhme. Causes and effects of unanticipated numerical devia- tions in neural network inference frameworks. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36. pp. 3p055-005-6007 CurraannnCCunnn.ommmo Curran Associates, Inc., 2023, URL httpppss//pooocceeiggs..mm wttp::ssserrrrrrpesesseee http://eeeeeetcccooooooooooaaaed hwtp00/0e7....cccooooo---o--eeee
J. Schmidhuber and S. Heil. Sequential neural text compression. IEEE Transactions Neural Networks, 7(1):142-146, 1996. doi: 10. 109/72.478398.
Harald Semmelrock, Tony Ross-Hellauer, Simone Kopeinik, Dieter Theiler, Armin Haberl, Stefan Thalmann, and Dominik Kowald, Reproducibility in machine learning-basee research: Overview, barriers and drivers, 2025. URL https://arxii..o
https://arxivoorr//bb///400 wwtpwrg/////.....////// 14325.
Sanjif Shanmugavelu, Mathieu Taillefumier, Christopher Culver, Oscar Hernandez, Mark Coletti, and Ada Sedova. Impacts of Moottnng-poin -on-associativity on reproducibility for hpc and deep learning applications. In Proceedings of the SC '24 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis, SC-W '24, pp. 170-179. IEEE Press. 2025. ISBN 9798350355543. doi: 10. 1111999$CW632222244000000 URL https://doi.org/ 10.109//CCW632002222400000
C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27 (3):379-423, 1948. doi: 10.1002//. 1538-73033 1994 (948..111338.
George Toderici, Damien Vincent, Nick Johnston, Sung Jin Hwang, David Minnen, Joel Shor, and Michele Covell. Full resolution image compression with recurrent neural networks. CoRR, abs/1608.05 2016. URL http:///arxiv.org/bbba wwtp//os//////oo (etp://aab/1000515555
Chandra Shekhara Kaushik Valmeekam, Krishna Narayanan, Dileep Kalathil, Jean-Francois Cham- berland, and Srinivas wwt..o/b/bbb//000000000000 2023. URL httpps///axxv..org/////o/
Lossless text compression using large language models,
lan H. Witten, Radford M. Neal, and John G. G. mun. ACM, 30:520-540, 1987. URL Cleary Arithmetic coding for data compression. Com- http:///w......oosoooooooooooaaa
Jiay Yuan, Hao Li, Xinheng Ding, Wenya Xie, Yu-Jhe Li, Wentian Zhao, Kun Wan, Jing Shi, Xia Hu, and Zirui Liu. Understanding and mitigating numerical sources of nondeterminism in Ilm inference, 2025. URL https://ariv..rrg/b///5........
13

---

le + al A APPENDIX
A.1
FULL PROOF OF LAST STEP OF PROPOSITION
In this section give the full proof of the last step of the proof of Proposition 1 maximization step in (10). We recall that the assertion is that:
particularly the
D' exp +e e 10-==11--
-p') tanh (e)
(21)
(1-pp)
2
We first note that if 0 or = 1, then
Epp eppp + t (1 1 (1-
p" =0
(22)
and since E > 0 (so et > F) when p" 1/2, then
epp' ev' +
e + 1/2
(23)
Thus, neither 0 nor can be the maximizing value and we know that the maximizing value of p" (if exists) is in (0, 1). Thus, we can represent p" a for some a E R, and maximize over a instead. Then we get
ppp'
c esta + e-te+a
te
(24)
ppp + e 1 (1-p')
e 40
te
ea
eatt
so we are trying to maximize (over a E R) the expression
epp' pppp e p²)
e+a
a
(25)
eEto + e-6taa
eat t
e²
f(s + a) f(a) for f(z) e² +
(26)
Incidentally, f(2) is the logistic function with input scaled by 2. Finally, note that
f( e=(e" +) (E ")
(27)
(e* +6=22²
(E +6
which is maximized at 2 O, satisfies f'()) = f'()= for all z, and decreases as |a| increases. Thus,
aa) { > f'(a) when a < -E/2 since |a|
(28)
(a) when > -e/2 since
|a||
< |s + al
and hence f(e + a) - f(a) is function that is increasing when a < -e/2 and is decreasing when -e/2, making a -E/2 the maximizing value.
Then, plugging in a - yields
Epp
e
6pp' + (1 (1-p") -p)) ]'
max
(29)
ecta + (e+aa)
@ t
6//2
e e/22
(30)
e +
-/2 + 6
e/2 _ -/2
(31)
e t/
tanh (e/2)
(32)
Finally, it is well-known fact that tanh(z) for 2 which completes the proof.
14

---

Next-token probabilities
PMATIC processing send token "F" (bitstring representation 130);
Token
Bitstring
Prob
Bi Probability the first bit is 0.206 + 0.047 0.200 + 0.029 0.482
010
0.097
0 01355 under PMATICC
8 0.01
B
000
0.249
101
0.206
Encode helper 0 using probability distribation (0.92, 0,08), then token using (0.625, 0.375)
111
0.047
2it:; Probability the second bit is 1 (conditioned on the pecvious bit being
0.047 + 0.029
E
010
0.045
0.206 + 0.047 + 0.200 + 0.029 0.157
100
0.200
C.157... 0.125 under PMLNTC
Helper
011
0.127
H
110
0.029
Lincode helper 0 using probability distribation (0.92, 0,08,, then token bit using (0.875, 0.125)
Rir:;: Probabilitt the chird bit is (conditioned on the previous bits being 10)
8= 0.01 and = 0.125
0.206
0.507
Helper bits are encoded with aridhmetic encoding using, the probability distribution from the "uniformitt" assumption:
0,206 + 0.200
A
mape
PMICIIC
Helpe
(1 8/r, 8/r) (0.92, 0.08)
Encode helper using probability distribation (0.92, 0,08,, then token bit asing (0.500, 0.500)
Illustration of PMATIC encoding for token 'F'. The table in the figure shows the corre- sponding longform and model-computed probability for each token (the model-computed probability depends context).
Figure 2:
A.2 PMATIC EXCODING FULL TOKEN EXAMPLE
Illustrated here is an example of PMATIC encoding when there are 8 total tokens (each token can be described by 3-bit longform). PMATIC has parameter settings of 8 0.01 and 0.125 (so there are four quantization bins total).
The example shown in Figure concerns the encoding process for single token in simplified setting with a token alphabet of size 8 (with tokens denoted by characters A through H). Each token's associated longform (of length and the probability assigned in the table at the left of the diagram. To the right, the encoding process is depicted graphically: the [0, interval is divided into bins, whose centers are denoted by green stars; radius of around each boundary point between two bins is shown in red.
by the predictive model are given
Then, the encoding process for token F given the model's predictions shown. Each bit in F's long- form (in this case, 1 0 0) is encoded sequentially. In each step, the probability of the next bit being 1, defined by the model's predictions and conditioned on the values of the previously shown as the pink dot on the [0, 1] interval: if it falls sufficiently far from the nearest bin boundary (outside the red regions), is quantized to the corresponding bin center and corresponding helper bit with value 0 is generated; if it falls close to the nearest bin boundary (inside red region) it is quantized to the boundary point and a corresponding helper bit with value 1 is generated. Then, the helper bit and the token bit encoded using arithmetic coding, using probability 5/r for the helper bit and the quantized probability for the token bit.
bits,
A.3 ADDITIONAL. IMPLEMENTATION DETAILS
Since PMATIC requires each token be assigned a unique fixed-length, bitttlenntt (its longform), we assign a random /-bit representation (where & depends on the model used") for each token and convert the file to a bitstring. The same longform dictionary used across all files in each setting.
Our PMATIC implementation is based on the arithmetic coding implementation from Ilama-zip Buzzani (2024)).
'Specifically, [log, IA where [A] the token alphabet size.
15

---

Logit Differences Histogram
5000
4000
3000
2000
1000
-0.04
0.00
0.02
0.04
logit
Figure 3: Histogram giving the difference token logits when running the same LLM on the same prompt on two different devices.
For our datasets used, the Wikipedia articles tests were randomly selected and pulled September 2025. These text files have non-ASCII characters removed before encoding (no limitations were put on the possible outputs of files). These files varied in length, from being very short to being long. Other text files from novels were split into several files of size 5 KB.
Compression ratio and synthetic non-determinism experiments were run on the MIT Supercloud [Reuther et al (2018)), bigh-performance computing system with Xeon CPU nodes and Volta GPUs, while experiments exploring performance on real -en-eeterminism were run using two different dif- ferent Apple laptops. To speed up the inference steps required to compress the inputs, we use rolling context window of maximum size 512 which resets every 2556 tokens via truncation: each time the context length reaches 512, we drop the oldest 256 tokens.
A.4 A SAMPLE OF REAL NON-DETERMINEN ON REAL DATA
A Sample of the Amount of Non-Determinism For our tests of PMATIC under real non- determinism, we estimated that PMATIC using 8 0.01 could reasonably result in correct decoding of the text files. One indication of this is given in Figure & which gives a histogram of the logit differences. Here, the first logit is given by running the L.LM (Llama 3.1) on the device doing the encoding (Apple M2 Pro chipset with 16 core GPU). The second logit is computed on the decoding device (Apple M4 Max chipset with 32 core GPU). The prompt used is text from a book which resulted in 810 tokens (the context length is 512 tokens).
Setting& 5 0.01 would tolerate logit differences of around e = 0.02, which, according the results in Figure would suffice for most of the tokens in the tested prompt. However, it is clear that = 0.001 would be insufficient for the majority of tokens.
Additional exploration preformed to see if logit differences correlate with how probable token was (for instance, perhaps more probable tokens have more logit difference). We did not find any significant relationships and it seems logit differences generally distributed randomly.
A Sample of the Decoder Outputs For illustration, we give some samples of outputs from our experiments using real non-determinism between the two devices. We compare the final output text file with no PMATIC (baseline LLM compression with arithmetic coding method), PMATIC with 5 = 0.001 and PMATIC with ó = 0.01. In this setting, there no guarantee any of the algorithms will produce correct output, since the bounded mismatch assumption does not always
*We remark that while computational efficiency and latency is major concern for model-driven compres- sion, this arises primarily from performing L.M inference order to encnde and decode each token, and that the computational burden of the PMATIC algorithm is likely to be very slight in comparison.
Note also that mismatch exceeding the hounds does not always result in a decoding error, just in the loss of PMATIC's guarantee of correctness.
16

---

hold. However, experimentally, find that when 5 = 0.01, mistakes occurred in small set of test cases. When no PMATIC is used or when ò = 0.001, not a single file was decoded correctly and the results were not close. For brevity, choose shorter samples to display.
Sample
Input
Crush (Russian: is a 2009 Russian romance film directed by Pyotr Buslov, Aleksey German Jr., Kirill Serebrennikov, Ivan Vyrypaev and Boris [ Plo((cd) The film tells five different love stories.[4] Cast[edit] References[edit External links[edit]
Output for standard arithmetic coding (no PMATIC)
Crushers, Breakers and Grinding Mills; Vertical Mill for Cement China; maintenance and repairing &#; crude oil refining plant sell by the company. the maintenance and operation of All equipment is either OEM or equivalent in quality and will be odor crusher with dust briquette plant animated High quality Free Quote. price of building a plant crush plant Gold Ore Grinder small,pre design jaw crusher waste disposal project report; crusher plant project in india components
cement mill maintenance and maintenance cement mill. VRM Head Nidec Industrial Solutions (SI) drive. and operation maintenance activities of an industry. VRM jebel alluway crusher plant tonga.
Output for PMATIC with å = 0.001
Question: Explore the diversity in qualities like Stri Dhanraj -Decorum. A) 7213 B) 2319 C) 1321 D) 7291 E) 9123 Answer: Stri Dhanraj -Decorum Stri means goal and Dhanraj stands for helpful achieving that. Decorum means manners. Answer
Output for PMATIC with å = 0.01
Crush (Russian: a 2009 Russian romance film directed by Pyotr Buslov, Aleksey German Jr., Kirill Serebrennikov, Ivan Vyrypaev and Boris (hlebnikov.[1]22) Plot[edit] The film tells five different love stories.[4) Cast[edit] References/edit) External links(edit]
Sample
Input
Gymnagnostus is genus of trilobites in the order Agnostida, which existed in what is now Oaxaca, Mexico. It was described by Robison and Pantoja-Alor, in 1968, and the type species is Gymnagnostus gongros.[1 References[edit]
This trilobite-related article a stub. You can help Wikipedia by expanding it.
Output for standard arithmetic coding (no PMATIC)
G अनाननिितााा (AGRA), प उमल रिरोपन कोप पी अोटीमीीिि सिीब सिकरर के लिं कपिकलर बोपिशास रेार कातीी हा @ अपादी àे लिर Y होना हेस अीर सबा पमर उनत غ, अे 1000 की अशििका कापनकापा की परा करत ह a काकारटी भोर मशांररी की अलंदे समोगकान पब किाा मयीि अपसा रेनर की गड हे G à उमं बानिकाम àे रिर पहर रहिकाल यममम अाममा よ
17

---

Output for PMATIC with á 0.001
# Πetaa ЗаjмиСки
Πeтap weakyA () aл) Petro Zaismiski (KocoBo none, & 39; 41; B0] НИ 192Careful 1943) lße био Cpn ROOT, Bojrpan, воетики Wacamn wiil Mаанoсте; 1990e başInda note ce 2-Hüğaun! erika
во "");
He wa была preventove politika, the 11. Kaca sek 1993 влета; inko μк' dûe ве4и no покапно управыа üße frank, slabo yпpавiêñe!
1. 12. 4. 2. Wikipedia contributors. net homeowner insurance quotes несaтслииттурии" Редакリи paмoy 24. Kaко paGram, Φарпизадии агодтактика комраjитeхнииа проддии 1 ...... ................................ H ................................
... strirryi илыка aCTOOM .....r.. извините :( Aecuá (Practice,)
.... ,pa4yH .... ................................ acTPOMи
Output for PMATIC with d 0.01
Gymnagnostus a genus of trilobites in the order Agnostida, which existed what is now Oaxaca, Mexico. It was described by Robison and Pantoja-Alor, in 1968, and the type species is Gymnagnostus gongros.[ Referencce{edit] This trilobite-related article a stub. You can help Wikipedia by expanding it.
The other trials follow similar pattern to the ones above. Outputs from encoding and decoding without PMATIC, or with PMATIC with å too small, diverge wildly almost immediately, generally containing nonsensical content unrelated to the original input.
Interestingly, we found that while both standard arithmetic coding and PMATIC with 0.001 fail to correctly compress and decode any of the files tested, standard arithmetic coding generally produced one or two correct tokens at the very start before diverging, while PMATIC with ó = 0.001 did not. We hypothesize that this occurs because mismatch relatively small, the shrinking arithmetic coding interval is 'almost correct' for the first handful of bits, allowing the first token be decoded correctly before the errors compound too much; on the other hand, when mismatch exceeds the bounds of PMATIC, the probability used by the decoder jumps to the next quantization bin, resulting an immediate large discrepancy between the encoder and decoder probabilities.
A.S
LLM USAGE
We used LLMs (specifically GPT-5) assistant for the background literature search, writing, and coding. This entailed asking the LLM to: search for and summarize related papers; write sample paragraphs, which we could then explain any terms we came across which we were unsure of. We also used the LLM to assist us with paper formatting and general typesetting issues.
guideline for
writing take phrases from; and
For the code for our experiments, we consulted L.LMs several different ways. A major design choice to credit to LLMs is the idea of using a rolling context window of some maximum size when getting the next token probabilities, which it suggested when asked about reducing runtime. We also asked LLMs write various small parts of the code which are standard operations, for instance, script to aggregate statistics for the experiments to be printed on the screen, function that changes byte arrays to bitstrings, some helper functions to setup arithmetic coding when running without PMATIC, and even a one line function to compute entropy. LLMs were also consulted for help on syntax or determining which functions to call in many places, for Linux command help and for debugging. In the carlier iterations of our code, we used LLM generated code to setup the Llama model. but later many of those critical parts were replaced. The key components of the PMATIC algorithm were typed without the use of LLMs.
18


Reviews:
[{"review_id": "TLF5EXkgGC", "reviewer": "Reviewer_ADbL", "summary": "The paper proposes a method to address the problem of practical usage of LLMs in data compression. A novel algorithm is presented for compression with uncertainty in probability predictions based on arithmetic coding. Furthermore mathematical analysis is presented showing compression bounds under a given uncertainty. Experiments denote successful demonstration with synthetically generated noise.", "questions": "Please see weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This is a very relevant problem, I believe this would allow the community to actually make practical compressors with the proposed algorithm. \n2. Article is original and a novel algorithm is proposed. Paper is quite easy to read.", "weaknesses": "1. The only weakness I would say is some analysis on what delta's would we expect by changing hardware or going from GPUs to CPUs. Also there is relevant research addressing uncertainty in LLM prediction which should be added to related work (https://thinkingmachines.ai/blog/defeating-nondeterminism-in-llm-inference/).\n2. Please add comparison with some more compressors, especially CMIX. Also include latency because that is where traditional compressors win by a huge margin.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KnlGuDd5wT", "reviewer": "Reviewer_nkTr", "summary": "The authors propose an algorithm to quantize / bin the probability distributions to account for possible deviations of the predicted CDFs between the encoder and decoder. The motivation is due to the non-determinism of LLMs, which can result in small differences in floating point numbers even when run on the same hardware.", "questions": "- Do the authors have a good sense of how large the mismatches are in practice (see box above)?\n- Can the authors provide more experiments across data modalities, and possibly varying other variables that could impact the degree of mismatch (see box above)?\n- Can the authors add figures to explain the binning better?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 4, "strengths": "- The method is reasonably simple to apply to existing LLMs, without needing to retrain.\n- The authors provide some guarantees on the added bit length due to binning.\n- This is a very important, and realistic problem, that needs to be solved to have next-gen AI codecs, and I appreciate the authors pushing on real world problems.", "weaknesses": "- The experiments are significantly lacking in breadth. If the method is general, the authors could provide further experiments with different data modalities.\n\n- The following is hard, but would significantly improve the paper: can the authors estimate what are typical deviations present in relevant scenarios where AI codecs could be applied? For example, take any open source model, and apply the encoder and decoder using 1) a different version of CUDA, 2) different models, and other variables that might vary in practice. This would significantly improve the contribution and ground the paper in real world applications.\n\n- Adding figures explaining the binning procedure would significantly improve the exposition of the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HufQwKsSSN", "reviewer": "Reviewer_iuaJ", "summary": "We theoretically formulated the problem of \"non-determinism\" that arises in lossless compression using large-scale language models (LLMs), and proposed a new compression coding method, PMATIC (Probability-Matched Interval Coding), to overcome this problem.\nLLM outputs a probability distribution $P(x_t|x_{<t})$, but even for the same input, it may produce slightly different probabilities due to different GPUs, different libraries, or differences in parallel order. Conventional arithmetic coding breaks down if the probability distributions of the encoder and decoder do not match perfectly. However, if the probability mismatch is sufficiently small (bounded mismatch), accurate decoding is possible if both agree on an \"intermediate common distribution\", which is the Probability Matching problem.\nPMATIC is a method that extends existing arithmetic coding with probability quantization, ensuring consistent coding even if the encoder and decoder make slightly different probability predictions.\nFor PMATIC, this paper theoretically evaluates its correctness and compression loss.", "questions": "There has been discussion about static performance, such as the achievable compression performance. However, how much better is it compared to existing methods in terms of the amount of computation required for compression and decoding?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: This paper is the first to mathematically formalize the problem of \"probabilistic model-driven compression\" $\\times$ \"LLM nondeterminism\".\nQuality: Not only is there a mathematical discussion of performance analysis, but the usefulness of the proposed method is also verified through numerical experiments, making the paper of high quality.\nClarity: The problem to be addressed is clearly stated, the algorithm is given in detail, and the argument is clear enough.\nSignificance:  This paper is one of the first to formulate the problems that are encountered when actually applying LLM as lossless compression, and is expected to make an important contribution to related research.", "weaknesses": "As mentioned in 6. Future work, if LLM is actually used for lossless compression, the size of the models required to implement the compressor and decoder will be a major problem. This issue has not been discussed in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Dstbox4pD", "reviewer": "Reviewer_YPjH", "summary": "This paper tackles a practically critical but underexplored problem in model-driven lossless compression: the instability caused by prediction mismatch between encoder and decoder due to LLM non-determinism. The authors formalize this as the probability matching problem and propose PMATIC (Probability-Matched Interval Coding), a theoretically grounded and model-agnostic alternative to arithmetic coding that tolerates bounded prediction mismatch. Theoretical guarantees on decodability and compression efficiency are presented, and experiments on Wikipedia and Enwik8 datasets validate correctness and reasonable efficiency loss under synthetic noise.", "questions": "- How large is the helper-bit overhead in practice, and how does it vary with δ?\n\n- What is the computational impact, such as encoding/decoding latency compared to standard arithmetic coding?\n\n- The paper mentions the potential extension to stochastically bounded mismatch. Could the authors elaborate on whether PMATIC can be adapted to probabilistic mismatch distributions observed in real inference pipelines?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The work highlights a key yet overlooked obstacle in deploying LLM-based compression systems: non-deterministic inference, bridging the gap between theory and practical system reliability.\n\n- The formalization of bounded prediction mismatch and the introduction of a matching interval coding mechanism are conceptually clean and mathematically sound. The paper also provides provable correctness and upper bounds on the additional code length, demonstrating an informed trade-off between robustness and compression efficiency.\n\n- PMATIC is model-agnostic and can be seamlessly integrated as a drop-in replacement for arithmetic coding, showing potential broad applicability beyond text compression.", "weaknesses": "- Experiments are confined to synthetic perturbations on a single model (Llama-3.1) and small text corpora. This does not convincingly capture the stochastic, architecture- or library-dependent non-determinism that motivates the problem. I'd like to see more experiments. \n\n- There already exist benchmarks for model-driven or LLM-assisted compression [1,2,3]. These could provide a valuable performance baseline.\n\n- Runtime, helper-bit statistics, and computational overhead are not reported. It is unclear how PMATIC scales when applied to larger models or real-time compression.\n\n- Although the paper derives an analytical bound on the extra bit cost, it does not verify whether the empirical losses follow this bound.\n\n- Some related works are missing [4,5,6]\n\n- In all, I think this paper addresses an important and practical problem, but the experimental section is insufficient. If the authors can provide comprehensive and convincing experimental results during the rebuttal period, I will raising my score.\n\n[1] Valmeekam C S K, Narayanan K, Kalathil D, et al. Llmzip: Lossless text compression using large language models[J]. arXiv preprint arXiv:2306.04050, 2023.\n[2] Mao Y, Pirk H, Xue C J. Lossless Compression of Large Language Model-Generated Text via Next-Token Prediction[J]. arXiv preprint arXiv:2505.06297, 2025.\n[3] Mittu F, Bu Y, Gupta A, et al. Finezip: Pushing the limits of large language models for practical lossless text compression[J]. arXiv preprint arXiv:2409.17141, 2024.\n[4] Mao Y, Li J, Cui Y, et al. Faster and stronger lossless compression with optimized autoregressive framework[C]//2023 60th ACM/IEEE Design Automation Conference (DAC). IEEE, 2023: 1-6.\n[5] Mao Y, Cui Y, Kuo T W, et al. Accelerating general-purpose lossless compression via simple and scalable parameterization[C]//Proceedings of the 30th ACM International Conference on Multimedia. 2022: 3205-3213.\n[6] Goyal M, Tatwawadi K, Chandak S, et al. DZip: Improved general-purpose loss less compression based on novel neural network modeling[C]//2021 data compression conference (DCC). IEEE, 2021: 153-162.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)