Training LLMs over Neurally Compressed Text
Authors: Brian Lester
Jaehoon Lee
Alexander A Alemi
Jeffrey Pennington
Adam Roberts
Jascha Sohl-Dickstein
Noah Constant
Venue: Accepted by TMLR ()

Abstract: In this paper, we explore the idea of training large language models (LLMs) over highly compressed text. While standard subword tokenizers compress text by a small factor, neural text compressors can achieve much higher rates of compression. If it were possible to train LLMs directly over neurally compressed text, this would confer advantages in training and serving efficiency, as well as easier handling of long text spans. The main obstacle to this goal is that strong compression tends to produce opaque outputs that are not well-suited for learning. In particular, we find that text naïvely compressed via Arithmetic Coding is not readily learnable by LLMs. To overcome this, we propose Equal-Info Windows, a novel compression technique whereby text is segmented into blocks that each compress to the same bit length. Using this method, we demonstrate effective learning over neurally compressed text that improves with scale, and outperforms byte-level baselines by a wide margin on perplexity and inference speed benchmarks. While our method delivers worse perplexity than subword tokenizers for models trained with the same parameter count, it has the benefit of shorter sequence lengths. Shorter sequence lengths require fewer autoregressive generation steps, often reducing latency. Finally, we provide extensive analysis of the properties that contribute to learnability, and offer concrete suggestions for how to further improve the performance of high-compression tokenizers.

Published in Transactions on Machine Learning Research (12/2024)
Training LLMs over Neurally Compressed Text
Brian Lester
Jaehoon Lee Alex A
Jeffrey Pennington
Adam Roberts" Jascha Sohl-Dickstein" Noah Constant" "Google DeepMind "Anthropic
(brianlester, mconstant/@poggl..cmm
Reviewed on OpenReview: https: / openreview. net/ forum? id= PRRMMSS4888
Abstract
In this paper, we explore the idea of training large language models (LLMs) over highly compressed text. While standard subword tokenizers compress text by small factor, neural text compressors can achieve much higher rates of compression. If it were possible to train LLMs directly over neurally compressed text, this would confer advantages in training and serving efficiency, as well as easier handling of long text spans. The main obstacle to this goal that strong compression tends to produce opaque outputs that are not well-suited for learning. In particular, we find that text naively compressod via Arithmetic Coding is not readily learnable by LLMs. To overcome this, we propose Equal-Info Windows, novel compression technique whereby text is segmented into blocks that each compress to the same bit length. Using this method, demonstrate effective learning over neurally compressed text that improves with scale, and outperforms byte-level basclines by a wide margin on perplexity and inference speed benchmarks. While our method delivers worse perplexity than subword tokenizers for models trained with the same parameter count, it has the benefit of shorter sequence lengths. Shorter sequence lengths require fewer autoregressive generation steps, often reducing latency. Finally, we provide extensive analysis of the properties that contribute to learnability, and offer concrete suggestions for how to further improve the performance of high-comppresson tokenizers.
1 Introduction
Today's large language models (LLMs) are almost exclusively trained over subword tokens. The tokenizers used to produce these -foonn-often BPE (Gage 1994 Sennrich et al.] 2016) or Unigram (Kudo) 2018).
as implemented by the SentencePiece library (Kudo Richardson 2018
are compressors that typically
achieve -4x compression over natural language text (Xue et al.) 2022)
p While these tokenizers "hide" the
character-level makeup of each token from the LLM (Xue et al. 2022 Liu et al. 2023), this downside is widely seen outweighed by the significant benefits of compression. Compared to raw byte-level models, L.M trained over subword tokens sees ~4x more text per token, allowing it to model longer-distance dependencies, ingest more pretraining data, and predict more text at inference time, all without increasing compute
Given these advantages, raises the question, could we compress text further to achieve even greater gains? It is well known that autoregressive language models can be turned into lossless text compressors, and recent
"Work done while at Google DeepMind.
We refer here to "token-level" compression rate, i.e., the length reduction between raw UTF-8 byte sequence and the corresponding sequence of subword tokens. If instead subword compression typically delivers ~2x less compression, depending vocabulary size, which typically ranges from 32k to 256k. See Scction 3.4 for discussion.
the number of bits required to encode the two sequences,
2The increased of the input embedding and final softmax layers due increased vocabulary size negligible for all but. the smallest. models.
1

---

Published in Transactions on Machine Learning Research (12/2024)
next byte probabilities
M1 LM over bytes
NeuraL compr
e010
Neural compression can Lead to better LLM tokenizers
Compression Algorithm (e.g. Arithmetic Coding)
compressed text as bits
010000110001110001111111000 1000000001000000111111100
chunk into token IDs
|
compressed text as tokens
67 58
188
130 97 125
next token probabilities
M2 LM over compressed text
Figure An overview of our approach for training an LLM (M2) over neurally compressed text. First, M1 is trained as standard byte-level language model given leftward context, M1 assigns probability to each possible following byte. Next, corpus text is compressed into bitstream using M1 compressor. Specifically, the probabilities that M1 assigns at each text position are fed into a compression algorithm like Arithmetic Coding that supports using dynamic symbol probabilities. Finally, this bitstream is chunked into tokens (e.g., 8-bit chunks), and M2 trained as a language model over compressed text.
work has shown that LLMs can easily achieve 12x compression over English text (Delétang et al. 2024 Can we simply train an LLM over this neurally compressed text?
In this paper we explore various options for doing so, focusing primarily on the idea of using Arithmetic Coding (AC) (Witten al. 1987), which known to reach the near-optimal compression rate for a particular model that assigns probabilities to text continuations. Figure [ presents our high-level approach. First, a small language model "M1" is trained over raw byte sequences. Next, this frozen model is used to compress pretraining corpus text. by applying standard compression algorithm like AC. The resulting compressed bitstream is then chunked into tokens, which are used to train "M2", a language model that directly reads and writes neural-compressed text.
Given a perfect probabilistic model of the raw byte sequence, the compression step would output a fully- compressod bitstream that would be indistinguishable from random noise, and hence unlearnable by M2. In reality, M1 can never be perfect (Zvonkin & Levin 2007), so the M1-compressed output will still contain learnable patterns. We explore whether using compression powered by relatively small M1 is able to "remove" the simple structure that M1 understands from the input-oaa patterns of spelling, word frequency, and basic grammar while retaining any higher-level structure that MI fails to model e.g., patterns requiring "deeper" reasoning and long range coherence. larger M2 would then learn to model this higher-level structure,
SSpecifically, the authors show that Chincilla 70B 12x bit-level compression rate.
Hoffmann
2022 can compress 2048-byte subspans of enwikg
2

---

Published in Transactions on Machine Learning Research (12/2024)
without needing to relearn the low-level structure removed by M1 In theory, this process could be repeated by training an even-larger M3 model on text compressed by M2, and so on.
In practice, we find that text compressed via Arithmetic Coding is not readily learnable by a standard transformer-based LLM, with resulting models predicting tokens at chance. Interestingly, this result holds even when M1 is reduced a context-free unigram model, suggesting that the challenge of modeling AC- compressed text stems from the difficulty of learning the AC compression and decompression process itself. We verify this hypothesis by showing that even the sub-tasks of AC-compressing and AC-decompressing text are not learned well beyond few initial tokens.
To aid learnability, we propose compression via Equal-Info Windows, a simple technique that breaks text into contiguous windows and compresses them via Arithmetic Coding independently. Rather than splitting text into windows of equal text length, we track the number of bits output by the compressor, and close each window just before exceods a sct information threshold (c.g., 32 bits of information). This has the advantage that when chunking the subsequent bitstream into M2 tokens, there tokens to one window (e.g., four 8-bit tokens one 32- bit window). At each window boundary, we reset both AC algorithm and the MI model context. This ensures that each window may be mapped back onto raw text without any additional information.
stable mapping from N
Through ablations on window size and M2 vocabulary size, we find that Equal-Info Windows make learning of AC-compressed text possible across a range of settings. However, we also observe that learning progresses gradually, starting with tokens at the left edge of each window, and for longer windows, the model learns little about the tokens near the right edge. Our best-performing setting uses short 16-bit. windows that each correspond to single 16-bit M2 token. Despite resctting the compression algorithm every 16 bits, we still achieve -5.3x token-level compression overall, which exceeds standard subword tokenizers. Remarkably, our best M2 models outperform byte-level baselines on perplexity benchmarks bbtts//y for fixed computation budget (FL.Os/bytee). This shows that learning over neural-compressed text can be effective.
At the same time, our best M2 models underperform subword baselines. We suspect this due at least in part to the relatively unstable mappings our neural tokenizers induce between words and tokens. By contrast, standard subword tokenizers induce essentially stable word-to-token mappings, which likely makes the token sequences they output well-suited for LLM training. We illustrate this contrast through qualitative examples. Whether neural tokenizer can reach a high level of compression while maintaining high learnability for LLM training is an interesting question for future research.
Our main contributions are as follows: (1) Outline advantages and challenges of training over neurally compressed text. (2) Compare LLMs trained over different tokenizers along two axes: bits/byte and FLOPs/byte. (3) Show that standard LLMs can't learn to model vanilla AC-compressed text. (4) Show that
GZip-compressed text is learnable by standard LLMs, but not competitive. (5) Propose compression via Equal-Info Windows, and show that it enables learning over neurally compressed text.
2 Motivation and Background
2.1 Advantages of Training over Neurally Compressed Text
Training LLMs over compressed text is appealing for many reasons. We discuss three advantages in detail below.
The most straightforward advantage is efficiency. By compressing the same text into shorter token sequence, the model can process more text for the same computational cost. In particular, model trained over Cx compressed text will see C'x more text during training compared to model trained over raw text, given an equal compute budget. Increasing the amount of data seen in pretraining is often an effective means of improving performance (Kaplan et al. 2020: Hoffmann et al. 2022 I. Processing text more efficiently also confers benefits at inference time, reducing the serving cost for handling a request of a given prompt and continuation length. In addition to reducing the raw compute needed for inference, compression can also
Efficiency
Intuitively, training M2 could be seen as analogous to fitting the residuals of M1 FFreddmn 2001
3

---

Published in Transactions on Machine Learning Research (12/2024)
improve inference latency, since generating better-comprest output requires fewer sequential autoregressive steps.
Longer Context A second advantage is that working with compressed text allows modeling longer contextual dependencies. In vanilla transformer-bact -ased models, computation for the self-attention layer scales quadratically with the sequence length, Onn2d). This has limited the sequence lengths used by such models in practical settings to ~10 Lokens Ir, via compression, each loken represents (on average) C' byles of raw text, then the resulting LLM can model dependencies across Cx longer distances compared to a raw text model operating over the same token sequence length. While the benefits modeling longer context (beyond -1,000 bytes) are modest when viewed merely as perplexity gains (Press et al. 2022), the ability to condition long context is critical for many applications, such as retrieving content from document, or answering coding question provided documentation.
Distribution of Compute A third potential advantage of training over compressed text is that information will be spread more uniformly across the sequence. By the nature of compression, a lext span that is relatively predictable (e.g., boilerplate notice) will be more compressible than span with high perplexity (e.g., unique product scrial number). When an LLM is trained over well-compressed text, each token will represent roughly an equal amount of information. Since the LLM allocates equal compute to each token, this amounts to allocating more compute for "harder" text spans. This adaptivity is similar in spirit to "Adaptive Computation Time" (ACT) (Graves) 2017), which learns to allocate additional compute at some sequence positions in an end-to-end manner, but with the advantage that in our case the computation remains "ddenic=ideenicaal operations are applied at each position
2.2 Challenges of Training over Compressed Text
Learnability It is not at all obvious what types of compression are "transparent" enough to be learnable through a standard LLM training process. Strong compression can be seen as removing as much redundant or predictable information from a sequence as possible. Consequently, the bitstream output by a good compressor is inherently hard to distinguish from random noise. In this work, we explore the setting where M2-the model trained over compressed text-has a larger capacity than M1, the model used for compression. In principle, this setup should allow M2 to extract additional information from the signal even after M1 has compressed it. However, for strong enough M1 compression, the resulting bitstream may be too noisy to detect any signal.
As a prerequisite for M2 to effectively predict continuations of compressed lext, we anticipate that it is necessary for M2 to have the ability to decompress bits -> text and compress text - bits. These sub-tasks are challenging in their own right. First, M2 needs to accurately "simulate" M1 in order to know the probabilities it assigns to the text, which determine the output of compression Training models to mimic other models can be difficult (Lester et al.} 2022), and even in settings where models do learn to copy the behavior of another network (Hinton et al. 2015). this is often only when looking at which symbol was assigned the highest probability the actual probabilities assigned often differ (Stanton et al. 2021). Second, M2 needs to learn the compression procedure itself. In our case, this means tracking the Arithmetic Coding algorithm, which requires maintaining high-precision numerical state across long contexts. We investigate these sub-tasks
in detail in Section 5.2
A further learnability challenge is the high level of context sensitivity needed to interpret bitstream of compressed text. When chunked into tokens, particular bit subsequence (c.g., 10111001) can map onto the
'Exploring sub-quadratic attention mechanisms is an area of active research (Ainslic et al 2020 Wang et al. 2020 Kitacv
ct al. 2020 Zaheer et al. 2020 | Beltagy et al.] 2020 Child et al. 2019 et alia). However, regardless of the cost of attention,
compressing the input increases the effective context "for free".
oIt should be noted that ACT learns to allocate more compute where it is useful, as opposed to merely where the predictions hard. For example, ACT learns not waste compute on inherently unpredictable text spans. We expect that a heuristic, allocating more compute to perperrperlyextty text spans is valuable, but leave this to future work to verify.
Forr Arithmetic Coding, not only would M2 need to know the probabilities MI assigns to the observed text, but it would also need to know the probabilities assigned many anobserved symbols. This is because Arithmetic Coding operates over comulatine probabiiities, i.., the probability that the next symbol is or any alphabetically preceding symbol.
4

---

Published in Transactions on Machine Learning Research (12/2024)
same token despite having no stable "meaning" across occurrences. We show examples in Section 6.1 where token maps to many different underlying text forms, necessitating strong contextual understanding. While LLMs are robust to some level of polysemy, as highlighted by the success of Hash Embeddings (Tito Svenstrup ct al. 2017) where multiple unrelated words share a single token representation, we suspect this has its limits.
Numerical Stability An additional technical challenge is that compression methods can be sensitive to the precise model probabilities used. To achieve lossless compression in our setup, it is critical that the M1 probabilities match during compression and decompression. This can be hard to guarantce in practice, there are many sources of numerical noise in LLM inference, especially when running parallel hardware. An expanded discussion of numerical stability issues can be found in Section 3.7.
Multi-Model Inference Finally, a specific challenge of training over neurally compressed text is that multiple models need to be stored and run side-by-side in order to perform inference. We assume that if M1 is relatively small, this additional overhead is not a significant drawback compared to a standard tokenizer, which also a separate model that is needed to tokenize text input and detokenize LLM outputs. In evaluating our approach, we include M1 compute in our calculations of total inference cost (FLOPs/byle).
2.3 Compression
In this work, we focus on lossless compression, which aims to encode a sequence of input symbols, TO:N = fao, 21:..., E xIVI, into a bitstream while minimizing the expected length of the bitstream. Compression methods are often factored into a "modeling" component and a "coding" component (Mahoney) 2013). The input sequence can be viewed as sample from true distribution p, To.N ~ p, with a standard autoregressive decomposition, p(x0.N) = I[; p(a; ".o., Ii-)). The "modeling" component aims to approximate p with p. While some compression algorithms assume static probabilities for each symbol, stronger algorithms are "adaptive", mcaning that symbol probabilitios may change based on context. In this work, we use contexl-aware transformer-based language models to represent p.
The "coding" component of a compression algorithm converts the input sequence to a bitstream of length (( To maximize compression, we want a coding algorithm that minimizes the expected number of bits in the ream, L == xp [[( This is done by assigning shorter bit sequences to common symbols and longer sequences to less common ones The expected length is lower bounded by I, 2 H where (p) == Euo.--pl-- log2 p(x)] (Shannon 1948 This means that, given near-optimal coding algorithm, the achievable level of compression derives from how well the model á approximates p.
2.4 Arithmetic Coding
Arithmetic Coding [Rissanen 1976 Pasco 1977 uses a model P to compresses a sequence To.N to a bitstream, which is the binary expansion of float E 0. 1). The float. f is found by assigning successively smaller sub-intervals to each symbol x; E TO.N, with the final interval enclosing f. An interval is made of an upper and lower bound, I; = 14; u.) and its size is given by u; u;-4: 4. Starting with to = [0, 1), at each step of encoding, the interval for the symbol 24 is created by partitioning the interval 1,-1 based on the cumulative distribution of & given the previous context, Peat (.)). The size of this interval is given by size([;-1) * p(a.) Thus:
Ix(x:) = [4-1 + size(Ti-1) * Prety (w (ee), 4i-1 + size([i-.) * Peay (osl(e)),
where w E X is the symbol before x, in a strict ordering of X, i.e. w is the previous token in the vocabulary. Finally, the bitstream of minimal length that represents the binary expansion of a number inside the final interval f E IN (N is used as the compressed representation.
This process can result in extremely uncommon sequences becoming longer under compression, algorithu can compress all possible input strings (Mahoney 2013). practice, natural language inputs are highly compressible and these edge cases are inputs that one would not recognize as natural language.
5

---

Published in Transactions on Machine Learning Research (12/2024)
Equivalently, the binary expansion can be seen as maintaining bitstream prefix and creating successive intervals By (b, E {0, == buj) by partitioning the current interval in half. If the first interval is chosen, a 0 bit is appended to the bitstream prefix 6, while choosing the second interval appends a 1.
(b = [bl bl-- + Sizz((B-1)) * 0.5) (b 1) = [b + size Bj 1)) bu,-1)
Once the final interval In is computed, smaller and smaller bit intervals are created until reaching a bit interval (b( that is fully enclosed by IN. At this point, the corresponding bitstream b the final compressed representation.
The coding component of Arithmetic Coding is nearly optimal: the output bitstream will have length of - [xo:)( + bils when using infinile precision. In the finite precision setting using 3 bits, an extra O(N2 P) bits are added (Howard& & Vitter 1992). See Witten et al. (1987) for an example implementation. In our experiments, we use procision 3 = 14. The practical effect of using a finite precision implementation of Arithmetic Coding is that the model's cumulative distribution gets quantized to integers using / bits. This results a minimum probability of 2-9 being assigned to all tokens.
2.5 Related Work
Recent work has looked at using large language models for compression, but has not to our knowledge attempted to train subsoquent models over the resulting compressod output. Works like Delétang et al. (2024) use a transformer language model as the modeling component of Arithmetic Coding, but they do not train over compressed output nor do they make modifications to the compression algorithm to facilitate learnability by downstream models. Additionally, they focus the setting of compressing fixed-size sequences of bytes. By contrast, our models operate over input sequences of fixed token length. This allows for models with higher compression rales to leverage longer contexts, as more bytes are included in the input.
Valmeekam et al. (2023) proposes changes to Arithmetic Coding to make it more amenable to use with LLMs LLMs-namely, they rank sort the logits from the model before creating text intervals, [x This could help alleviate issues stemming from errors in M2's simulation of M1. However, they do not train models on top of their compressed output.
Some approaches to "token-free" (i.., purely character- or byte-level) language modeling down-sample the input sequence via convolutions (Clark et al.) 2022 Tay et al.] (022), which could be seen as form of end-to-end neural tokenization. However one important distinction that the resulting tokenization is "soft" outputting high--dimensional vectors and not implying a discrete segmentation in contrast to our tokenization that outputs discrete tokens.
Methods for learning discrete tokenization end-to-end have also been proposed (Chung al. 2017 Godey et al. 2022 In the case of MANTa (Godey et al.) 2022). the learned segmentation appears to be fairly semantic (i.e., respecting word and morpheme boundaries), which could be an advantage over our approach. However, they lack our bias towards encoding an equal amount of information per token.
In modeling audio, it is common practice to use learned tokenizers that compress the raw input signal to discrete tokens from fixed-size codebook (van den Oord et al. 2017 Baevski al. 2020 Chung et al. 2021 Borsos al. 2023 However, this compression is lossy, whereas we focus on lossless compression.
Other recent work focuses using the "modeling" component from well-known compressors to do other tasks. Jiang et al. (2022) uses the model from GZip to perform text classification. Vilnis et al. (2023) uses the Arithmetic Decoding algorithm with an LLM as the model to do diverse parallel sampling from that LLM. One could imagine that the "model" of our compressors (M1) is a teacher for M2, but unlike these other applications, the MI values are not used outside of compression.
Külekei (0011) also explores learning over compressed text, but with several key differences. First, they n-gram language models (Shannon 1948) while we LLMss. Second, their model is conditioned on
6

---

Published in Transactions on Machine Learning Research (12/2024)
compressed bitstreams but produces distribution over the raw, uncompressed, bytes while our M2 models predict directly in the compressed space. Additionalyy, they only consider static Huffman coding (Hulfman 1952) as the algorithm to compress model imputs. While this avoids the context sensitivity issues we outline in Section 2.2 it results in a far worse compression rate compared to the adaptive compression methods we use. One important distinction is that their equal-information windows are overlapping, and used as a sliding window to provide context their n-gram language model. By contrast our equal-information windows are non-overlapping, and used to segment text. into series of equal-lngth bitstrings that can be interpreted independently by M2, and whose boundaries are easily identifiable, as they map to a fixed number of M2 tokens.
Several previous works explore how a lokenizer's compression rate correlates with downstream model performance. Goldman et al. (0244) finds that tokenizers that compress better perform better, which generally aligns with our findings, particularly in the large vocabulary setting, see Fig. G However, we find that using the strongest compressors is detrimental to learnability, as seen by the AC line in Fig. 3
By contrast, Schmidt et al. 2024) and Dagan et al. (0024) observe weak trend in the opposite direction better downstream performance from tokenizers that compress less. This discrepancy may be due to the fact that Goldman et al. (2024) artificially weakens compression by undertraining the tokenizer, whereas Dagan
et al. (2024) compares existing popular tokenizers, and Schmidt et al. (2024) compares different subword algorithmss.
The divergences between these results and ours likely stem from major differences in tokenization strategy. These three works restricted subword compressors, whereas explore stronger compressors built LLMs and Arithmetic Coding. Among other differences, subword tokenizers output tokens in near-Zipfian distribution (Zipl 1935), whereas our compressors output near-uniform distribution, see Table 3 The
qualitative differences between these classes of tokenizer are explored more in Section 6.1
Rajaraman et al. 2024] and Makkuva et al. (2024) find that under some data generation paradigms, transformers fail to model the contextual generation process and instead learn the underlying stationary
distribution of the process. This similar to the failure case we observe where M2 models only output a uniform distribution after training compressed text. However, their synthetic data setting is quite different.
from our compressed data setting.
3 Methods
For each experiment, compress long contiguous sequences of training data using different methods. For several, use M1-a byte-level language model-as in the compression algorithm. We then chunk the compressed output into tokens and train M2 models over those tokens.
3.1 Training Data
All training data used is English web text from C4 (en 3.1.0) RRalel et al. 2020 After tokenization, each document in C4 has an <EOS> token appended to it. We concatenate 128 documents together to generate long sequence of text. Using UTF-8 byte-level tokenization, the average document length is 2,170 bytes, thus these long sequences have an average length of 277,760 bytes. Despite the document breaks, we consider these long sequences "continguous" for the training of language models. These sequences are then split into individual examples, which are shuffled using the deterministic dataset functionality from Seq1O (Roberts
et al. 2023
3.2 Training M1
The model used for compression is a decoder-only Transformer model (Vaswani el al. 2017). It uses the 3m size seen in Table | and a context length of 1,024. We use a batch size 128, an rsqrt decay learning rate schedule (1/vsteps) starting at 1.0 with 10,000 warmup steps, and a z-loss of 0.0001. The model is trained for 2,500,000 steps using the Adafactor (Shazeer & Stern 2018) optimizer. The feed-forwart layers use ReLU activations (Nair & Hinton 2010 Fukushimal
1975 and we use distinct learnable relative attention
7

---

Published in Transactions on Machine Learning Research (12/2024)
embeddings (Shaw et al. 2018) at each layer. We use deterministic SeqIO dataset and train using Jax (Bradbury et al. 2018). 8), Flax (Heek et al. 2020), and T5X (Roberts et al. 2023 The final validation performance of the MI model is 1.457 bits/ byte, a standard measure of perplexity, see Section 3.8 MI and M2 are both trained on the C4 training data, but the final validation data used to evaluate M2 is unseen during M1 training, therefore there is no information leakage. This is similar to how LLM tokenizers are often trained on same dataset that the LLM subsoquently trained on.
3.3 Compression Methods
When compressing C4 training data, we use an example length of 10,240 bytes and apply one of the following compression tochniques (sce Appendix B for more methods we considered). This results in compressed examples that are, on average, much longer than our larget sequence length of 512 M2 tokens. Thus, each example fills or nearly fills the model's context window with compressed sequence made from contiguous raw bytes. We compress 51,200,000 examples using each method, allowing us to train each M2 model for 200,000 steps without repeating data.
In this sctting, we use a docoder-only transformer langnage model to model P. that is, when creating the interval I((ro:)), the partitions for each possible character, f(ai)are)) are calculated using the probabilities for the next token output by the transformer.
Arithmetic Coding:
The compressor model is run over contiguous text sequences of 10,240 bytes. The generated logits are used as the model distribution for Arithmetic Coding. We use the Range Encoding (a finite- precision implementation atinn of Arithmetic Coding) implementation from TensorFlow Compression (Ballé et al.) 2024) with a precision of 14. The range encoding implementation uses integers with precision + bits. This is commonly used when encoding 16-bit float logits, so we do not expect it to cause numerical issues as our models are trained using b6.oat16. While the compressor model is only trained on sequences of length 1,024, it uses relative position embeddings in its attention layers. Thus, it can be applied to longer sequences. Some works observe decreased performance imputs are scaled to lengths beyond those seen in training (Varis & Bojar 2021 Press et al. 2022), but find that compression performance is similar in the two settings. Compressing sequences of length 1,024 yields compression ratio of 5.46 while compressing sequences of length 10,240 yields a ratio of 5.49. This suggests the performance drop from long sequences has minimal effect on compression, or that the increased contextual information makes up this difference.
We will see that text compressed in this straightforward manner is not readily learnable by M2. Thus, we explore alternative compression methods that modify the "modeling" and "coding" components for better learnability. Table [ shows how our different approaches affect the compression ratio.
One potential difficulty of learning over compressed text is that the "modeling" component of the compression algorithm is hard to learn-that is, the second language model (M2) has trouble learning to simulate the probabilities the compressor model (M1) assigns to bytes.
Static Logits Arithmetic Coding:
To weaken the compressor model, we replace the context-sensitive LM model with a static byte unigram model that is, the model's distribution over bytes is the same for each token in the input, i.e., p(z; (T))) (a;).. This distribution is estimated using the byte unigram statistics from the C4 training data.
Equal Information Windows: The difficulty in modeling compressed text could also be because the "coding" component of the compression algorithm is hard to learn. That is, the language model is not able to track the state variables used in Arithmetic Coding.
Our proposed method of weakening the coding component of Arithmetic Coding compression is to reset the AC encoder once it has output a set number of bits, creating windows of fixed size where each window is independently AC-compressed sequence. This process is illustrated in Fig. 2 Windows will represent a variable amount of text, but each window is created via compression, we expect roughly the same amount of information per window.
In addition to resetting the AC encoder, we also reset the M1 model's context This means that each W bits of output can be decoded independently, at the cost of a weaker M1 model due to the lack of context.
We investigate not resetting MI's context in Appendix A.2 and find that the resets are important for good performance.
8

---

Published in Transactions on Machine Learning Research (12/2024)
The The_
M1
AC
0011101011101000 e The_th
ree_ sererrtde_yliiinn_eeeedeeeeeeee -frrifffr.......
M1
AC 1100100011001001 @ ree_c
urrently_ http:_iiinnnngeiisessseee
poocceessreeee_ are: laaelas_arrr_ffiiiaa Liaiclss_aee_Arrcca__aaaaaa satrican_savanna..
M1
AC
1111000011100111 + urrently_1
The three caatreeuurrr_y___eeeeeeee liilllliiingggeeii sriving_sppcies are: Sariican_savanna
str ants, ffrsss_fcccaaacfost_ooooo wowpssstteeeepantsss.oeeeee and the htt.aanttt__ssiaeeeeeepaeaeee
011110111.eee1100000000111111110
Figure 2: Under "Equal-Info Windows", text is encoded into a series of N-bit windows. To determine each successive window, the remaining text is encoded byte-by-byte via Arithmetic Coding until no more bytes can be added without exceeding the target bit threshold, here 16 bits. Both M1 and the AC algorithm are reset at each step, so no information persists across windows.
As each window is fully self-contained, the model no longer has to learn to track Arithmetic Coding state variables over long distances.
In cases where "spare bits" are available at the end of window (but not enough to add an additional symbol of text), we pad with zeros, This complicates the decoding algorithm, but the compression scheme can remain lossless. See Appendix D.5 for further discussion, handling the end of the input sequence, and an alternative padding approach that gives similar results.
When compressing an additional character would result in bitstream that is greater than W bits long, i.., more than W binary expansions are needed to create interval that is enclosed by I++1 (Fus++),, the bitstream (padded to W bits necessary) representing the input up to and including character i is emitted. Then both the AC encoder and MI model are reset. That is, 4 (2441N) is calculated as if (=(0o)) = [0, 1); the bit interval is also reset to Bb "") = [o, 1). Similarly, M1 is only conditioned on inputs that are part of the current window, the inputs after i. That is, p(æ,l=<)) x= p(z,(zi...).
We use to denote the bits per window, and for the vocabulary size of M2. For example, EqualInfoAC(()iis=111 (v)ocob=256) represents AC encoding with 16-bit Equal Info Windows and 8-bit M2 tokens (vocabulary 256).
GZip: As a bascline, we also explore training over text compressed using GZip (Deutsch 1996) as implemented in the Python (Van Rossum & Drake 2009) zlib library using the default compression level. GZip uses the DEFLATE algorithm a combination Huffman Trees (Huffman) 1952) and LZ77 (Ziv Lempel 1977). First L,777 used to replace repeated substrings in the text with pointers back the original substring. Then a Huffman Tree is built for the current LZ77 compressed exxamle and used to compress it. Note that this setting dynamic, the Huffman tree, and hence the binary codes for each character, unique

---

Published in Transactions on Machine Learning Research (12/2024)
Table 1: "Token" vs, "bit" compression ratios. Larger vocabularies require more bits to store each token, and thus incur a cost terms of absolute compression. However, when trying to minimize the compute an LLM uses to process a given piece of text, token sequence length is what matters.
Method
Token Compression Ratio
Bit Compression Ratio
SentencePiece
4.28
2.28
AC|u=256]
5.49
5.49
10.98
5.49
to the example. These experiments explore setting where both the modeling and coding components of compression are different from Arithmetic Coding.
3.4 Tokenization of Compressed Text
Most compression methods output a bitstream, but training M2 directly over bits would not be ideal. As M1 was trained over UTF-8 bytes, the bit-level output of compression would result in M2 being applied to much longer sequences. Additionally, models are generally trained with vocabulary sizes much larger than two. Thus, we need method to segment the bitstream into tokens, creating more standard sequence for training language models.
We convert the bitstream into a token sequence by grouping every N bits into a token resulting in a vocabulary size of 2N. We explore scttings of N E (8, 16), resulting in vocabulary sizes of v=256 and 6-65,536. As the tokens are created from the compressed bitstream, we expect the distribution of tokens to be more uniform than the usual Zipfian Zipf 1935) distribution of word or subword tokens, allowing to use larger vocabularies without encountering issues of rare unattested tokens.
Following Rajaraman el al. 2024); ) our tokenization scheme can be described as the tuple T = (Dict, DS, dec())) Dict is the space of tokens created by segmenting the compressed bitstream in our case, a vocabulary of 256 or 65k. DS is the entire M1 model. The functions enc(-) and dec(-) perform encoding (compression) and decoding (decompression). In our case, these functions vary with (i) the M1 model, (ii) the compression algorithm (AC, EqualInfoAC, etc.), and (iii) the bitstream segmentation strategy.
Throughout this work, focus the "token compression ratio" LoT the ratio between the input and output token sequence lengths. It is important to note that the meaning of "token" can differ between the imput and output sequences. Generally, the input sequence is one byte per token, while output tokens represent multiple bytes. This is in contrast to the more standard "bit compression ratio" L Lob-tho ratio of input bits to output bits. As we aim reduce the computational overhead of running LLMs by training them on compressed input, we are more concerned with reducing the number of tokens that M2 consumes. This difference is chucidated in Table While SentencePicce results in a sequence length reduction of 4.28x, the larger vocabulary means that 15 bits are required to represent each token. As such, the bit compression ratio is only 2.28, which is much lower than our AC-based compressors. Similarly, creating 16-bit tokens from the output of Arithmetic Coding does not change the bit compression ratio the total number of bits is unchanged- but does reduce the number of tokens in the sequence, and thus the number of tokens the LLM must process. We compute compression ratios over the C4 dev set, which is unseen during M1 training.
To highlight the differences between the tokenization methods above, we measure the performance (as bits/byte on sample of the C4 validation set) of two trivial models for each tokenizer in Table 3 The "uniform" model naïvely assigns equal probability to each token, regardless of context. The "unigram" model also ignores context, but assigns probabilities based on the global token frequencics observed in the training data. With byte-level lokenization, each UTF-8 byte encodes to a single 8-bit token, so the uniform model achieves bits/byte. For more powerful tokenizers, the uniform model is stronger, indicating that the tokenizer itself has some language modcling ability. We observe that our compression-based tokenizers (AC, EqualInfoAC and GZip) output a near-uniform distribution of tokens across their vocabulary. This reflectod in the near-zero gain over "uniform" achieved by modeling unigram statisties.
10

---

Published in Transactions on Machine Learning Research (12/2024)
Table 2: Weakening the "model" or "coding" component of Arithmetic Coding reduces the compression rate. The reduction of M1 to static unigram distribution results in the worst compression ratio. When using EquallnfoAC, M1 is weaker, as it has less context, and coding is weaker, as padding is often required at the end of windows. The compression ratio improves with larger window sizes.
Method
Compression Ratio
AC[v=256]
5.49
StaticAC/p=256]
1.73
FqualTnffoA[//=16,; ==256
2.66
EquallnffAA(/b=32,, v-256
3.49
EqualInfoA[/0=61,, /- v-256
4.16
CqquallnfoAC(b=1111 v=256]
4.61
Table Bits/byte (4) performance of two trivial models across tokenizers. "Uniform" assigns equal probability to each token. "Unigram" assigns probabilities based on the empirical token frequencies. As the compression- based tokenizers output near-uniform distributions over tokens, there is little gain in modeling unigram statistics. Thus, learning over this data requires modeling longer contexts.
Uniform bits /byte
Unigram bits hits/byte
Method
A
Bytes
8.000
4.602
3.398
SentencePiece
3.497
2.443
1.054
AC[==256]
1.457
1.457
0.000
StaticAC[u=256]
4.624
4.624
0.000
EquallinfoAC(b=16,, 2=256
3.008
2.976
0.032
BqualllnfoAC(11-32,,,
2=256
2.292
2.285
0.007
EquallnfoAC((-66,,
v=256]
1.923
1.921
0.002
1qua, v-256]
1.735
1.735
0.000
GZip|u=256
3.587
3.586
0.001
3.5 Training M2 on Compressed Data
Each M2 model is trained for 200,000 steps with batch size of 256 and sequence length of 512. Thus each model trains on 26.2 billion tokens. Of these, the vast majority (over 98.9%) are non-padding tokens; see Appendix D.2 for details and Table 12 for the exact size of each dataset. As methods with higher compression ratios cover more raw text per token, we also include the total number of bytes in each dataset. Shuffling of training sets is seeded, and dataset state is checkpointed during training, so each training run results in the model seeing each example exactly once.
Models are trained at. four sizes, shown in Table 4 with 25m, 113m, 403m, and 2b parameters, excluding embedding parameters. When the compressed bitstream is chunked into 8-bit tokens, the M2 model has a vocabulary size of 256. With 16-bit tokens the vocabulary increases to 65,536. All M2 models have sequence length of 512 tokens. Thus, when training on 16-bit tokens, twice as many bytes are seen per example and in training overall, as compared to 8-bit tokens. All other hyperparameters match those used in MI.
3.6 Baselines
We compare our M2 models against baseline models trained with two standard tokenization methods, described below. All hyperparameters, including sequence length (512), match those used for our M2 training above.
Bytes: These basclines train directly over UTF-8 bytes, using the byte tokenizer from By (uue al. 2022). which simply encodes the input string as UTF-8 using Python s. encode (ecoodee"uffeee ("utf-8"). The models see
26.2 billion bytes total (see Table 12
11

---

Published in Transactions on Machine Learning Research (12/2024)
Table 4:
Model sizes used in our experiments, and corresponding hyperparameter settings. parameter counts exclude embedding table parameters.
Note, model
Parameter Count
Embedding Dim
#Heads
#Layers
Head Dim
MLP Dim
3m
256
1024
25m
512
2048
113m
768
12
12
64
3072
403m
1024
16
24
64
4096
2b
2048
32
24
64
8192
These baselines train text tokenized using the T5 (Raffel et al, 2020 vocabulary, which has 32,000 tokens, and was trained using the Unigram algorithm (Kudo) 2018) as implemented by the SentencePiece library aKudo & Richardson 2018). Unigram is one of several popular subword tokenization algorithms, with others including BPE (Sennrich et al.) 2016) and WordPiece (Schuster & Nakajima 2012 Wu et al. 2016), and each of these is implemented by multiple librarics, sometimes with minor differences.
SentencePiece:
We opt use the SentencePiece Unigram tokenizer as our subword baseline for few reasons. First, the performance of these competing subword tokenization algorithms is known to be very similar, with several
works finding statistically significant difference between them in many settings (Kudo 2018 Ali et al.
2024 Schmidt et al.) 2024). Second, where differences are reported (marginal or otherwise), Unigram has
been found to be preferred, at least. for English-only models (Kudo 2018 Bostrom & Durrett 2020 Ali
et al. 2024 Schmidt et al.) 2024). Finally, previous work indicates that the SentencePiece implementation of Unigram outperforms the HuggingFace implementation (Ali et al. 2024 Schmidt et al., 2024).
Our baseline models trained SentencePiege tokens 112 billion bytes total (see Table 12
3.7 Numerical Stability
Arithmetic Coding depends on the creation of "intorvals" that cover each symbol in the vocabulary based on the quantized cumulative distribution of a model's logits when predicting the next token. As such, a small change in the logits due to numerical noise can result in vastly different output bitstreams. This can make the practical of neural language models in compression difficult. Common sources of noise include changes in batch size, parallel computation, changes to compute infrastructure (CPU vs. GPU vs. TPU, different TPU topology, etc.), changes to inference (computing the logits for the whole sequence at once vs. computing logits for a single token at a time using KV caches), and changes to the longest sequence length in the batch.
Methods like the rank-sorted algorithm used in LLMZip /Valmeekam et al. 2023 may help alleviate these issues as only the order of tokens needs to match between settings. The development of alternate methods of LLM-based compression should keep numerical stability issues in mind and ideally alleviate these issues in the design of the algorithm. Increasing the level of quantization could also help reduce numerical noise issues, differences would mostly be lost in quantization, but this would have a negative impact the compression ratio.
3.8
Evaluation
As the tokenization scheme varies across the approaches we consider, models cannot be directly compared "per-token" metrics such negative log likelihood loss f. Rather, following previous work (Dai et al. 2019:
A1-Rfou et al.) 2019: Choe et al. 2019 Gao et al. 2020 et alia), we report perplexity in terms of
bits-per-bytee bbits/ byte] (LoT/ Lgg
(2), which scales the model's loss by the token-level compression
rale.
We also compare models on how much computation (FLOPs) is required to perform inference over given length of raw text (bytes). More specifically, we calculate M2's expected FLOPs/byte by scaling FLOPs/token approximated by 2 params (excluding embedding parameters) following Kaplan et. al. 2020 by the
12

---

Published in Transactions on Machine Learning Research (12/2024)
10
Bytes
SentencePiece
ArthmeticCCoingll=255]
Arthhmeticcoding//666//
StaticAC[v=256]
StaticAC[v=65k]
EqualinfoAC(b=16, v=256]
EqualinfoAC(o=11, v=
GZip[v=256]
GZip[v=65k]
5
bits/byte
1
107
10
109
Inference FLOPs/byte
Figure 3: Models trained over compressed text are compared against baseline models in terms of bits/byte (L) and inference FLOPs/byte (L). The ArithmeticCodin and StaticAC settings are essentially unlearnable, with models failing to outperform naïve baselines (dashed lines) that assign equal probability to all tokens. EqualInfoAC and GZip outperform naïve baselines and show improvement with scale. EqualInfoAC is the strongest the compression- based methods, with EquallnfoAA(b=16, v=65k] outperforming the Bytes baseline at all sizes. While SentencePiece performs the best, the gap between EqualInfoAC and SentencePiece narrows with scale. See Appendix D.9 for the exact values used in this and other graphs.
token-level compression rate (as tokens/byte), For methods using an MI model during compression, the FLOPs/byte cost of M1 is added 10 For more dotails on the evaluation metrics see Appendix D.4
We evaluate models on a sample of the C4 validation set. During evaluation, the model is run over 20 batches or -2.6 million tokens. These tokens represent different amounts of text based on the compression method, making it impractical to evaluation on the same sequence of bytes for all methods. To confirm that our validation samples are large enough to be representative, for each method, we train five 25m parameler models with different seeds. We find the final performance to be extremely stable, with the largest standard deviation in bits/byte being 0.0061. Thus, the variance introduced from sampling the validation set is negligible. See Appendix D.1 for more information about variance.
4 Results
Simple Methods of Training Over Neurally Compressed Text Fail As seen in Fig. 3 the most obvious approach compression using Arithmetic Coding with MI assigning next-loken probabilities fails learn anything. Regardless of scale, the model only learns output uniform distribution over tokens, the
While there computational running GZip over the input text, we ignore it is insubstantial compared the running M2 model inference.
13

---

Published in Transactions on Machine Learning Research (12/2024)
performance of which is denoted by the dashed line. As the Arithmetic Coding procedure is near optimal [Mahoney] 2013), the compression ratio is essentially determined by the loss of M1. Thus, even though the M2 model learns nothing useful, when scaled by the compression rate, this setting ends up with the same performance as the M1 model. Similarly, models trained over data compressed with StaticAC-wher M1 is replaced with a static unigram model fail to learn. This result suggests that the difficultly in learning stems from the complexity or brittleness of the Arithmetic Coding process itself, rather than from M2's inability to model M1. Note that the weak "modeling" component of this compression scheme results in much lower compression rate and thus worse bits/byte performance, despite the model also learning uniform distribution.
On the surface, M2's inability to learn seems to run counter to Yun et al. (2020), which finds that transformers are universal approximators of sequence-to-sed to-sequence functions. However, the fact that transformers can express a function does not yet imply the ability to learn that function via stochastic gradient descent from random initialization. Additionally, for the purpose of training LLMs, our interest in training a model that generalizes well to held-out, validation data, as opposed to one that overfits its training data. In practice, we find our M2 training procedure is sufficient to overfit to small subsets of our AC-compressed training data, when repeated over multiple epochs. However, this docs not satisfy our goal of finding compression scheme suitable for LLM training.
SentencePiece is a Strong Baseline Our SentencePiece baseline outperforms all other methods, including our Bytes basclinc, across all model sizes. On the surface, this result seems to run counter to the recent findings of Delétang et al. (2024), where their byte-level models outperformed subword (BPE) models at medium and large scales. The discrepancy is due to prioritizing different metrics. They report the model's bit compression rate on fixed-length (2,048 byte) sequences. While this is one type of "fair" comparison, it disadvantages subword models, as they are trained to model dependencies longer than 2,048 bytes (but never evaluated on this ability), and are allotted fewer inference FLOPs to process the same text, as compared to the byte-level models. Additionally, bit compression ratio penalizes subword models for having larger vocabulary sizes. By contrast, our evaluation tests what perplexity models achieve on sequences of the same length they were trained on, and compares models at matching FLOPs/byte cost. This aligns with our end goal, which is to train an LLM that achieves the best perplexity at whatever sequence length it can handle, given a fixed budget for training and inference.
Infal-Info Windows make AC Learnable Fig. 3 shows that EquallnfoAC/b=16, v=256] outperforms the byte-level baseline at most model sizes, with the gains increasing with scale. In addition to better bits/byte performance, training over compressed data has the advantage of using fewer FLOPs/byte for a given model size seen in the leftward shift of the EqualInfoAC(==16, 2=256] curve compared to the Bytes curve due to shorter sequence lengths.
Using 16-bit tokens (65k vocabulary) increases performance further. EqualInfoAC[b=16, v=65k] outperforms the Bytes baseline at all model sizes. It underperforns the SentencePiece baseline, but the gap diminishes with scale.
However, EqualInffAC/i=16, v-65k] outperforms the SentencePicce baseline in terms of tokens/byte Models using RqualTnfoAC(i=16,, v=65k] take fewer autoregressive steps to generate the same text than models using SentencePicce encoding. This has the potential to reduce gencration latency, at the cost of reduced compute efficiency. This is tradeoff that is often worth making in production. For instance, speculative decoding Leviathan et al. 2023 is popular approach that performs redundant computation in order to potentially accelerate ruto-regrossive steps.
It is noteworthy that the EqualInfoAC M2 models learn well despite being trained on data that has nearly uniform unigram statistics, as we saw in Table 3 In the best case, our billion parameter M2 model achieves 0.94 bits/byte. This a large gain over the naive uniform (3.01 bits/byto) and empirical unigram (2.98 bits/ bbyt)) models from Table 3 and approaches the performance of a parameter- matched SentencePiece model (0.87 bits/byte), despite using 23% fewer FL.OPs/byte.
14

---

Published in Transactions on Machine Learning Research (12/2024)
Bytes
SentencePiece
Arthmetticoddig(l=255]
StaticAC[v=256]
EqualinfoACIo=166.v2555
GZip[v=256]
Arthmetticcodigg/==65)
StaticAC[v=65k]
EqualinfooA(0=-16.V666 v=6kk
bits/byte
G5ip[v=65k]
bytes/step
Figure 4: Comparing models in terms of bits/byte ()) and bytes/step (t). As decoder steps can be practical bottleneck for system latency, a model with higher FLOPs/byte or worse bits/byte may be preferred in order to achieve shorter sequence lengths. The dashed line (-.) is an example Pareto frontier, showing how a practitioner might value the trade-off between bits/byte and bytes/step. Our 2 billion parameter AqualTnfoAC|l==6, e=65k] model is on this frontier.
It is apparent from Fig. 8 that if FLOPs/byte were held constant, SentencePiece would achieve slightly better bits/ /byte than EqualInfoAC. However there is another axis along which EqualInfoAC may still be preferred. Setting aside inference FLOPs, on average SentenceP'ece tokenization requires 23% longer sequences to encode the same text when compared to our best EqualInfoAC setting (b-16, 6-65k). This means that, regardless FLOPs used, the SentencePiece models will take more decoder steps at inference time. is up to the practitioner whether shorter sequences. In many serving scenarios, decoder steps are practical bottleneck for determining system latency, other aspects of model scale, such as width, can be mitigated with enough parallelism. There are cases where one may be willing to incur even more (parallelizable) inference costs to reduce latency, in "speculative decoding" [Leviathan et al. 2023). To this end, it may be advantagcous to use more compute resources to scale an EqualInfoAC/=116 v 65k] model (recovering bits/byle performance) while retaining the reduced latency due to the shorter sequence length. This can seen visually in Fig. 4
"worth it. to trade off some bits/ performance in order achieve
GZip Not Competitive Training over GZip-compressed lext is relatively inelfective. M2's performance when trained over GZip highlights innter-intuitive trend. While the GZip M2 models actually learn, it would still be preferable to train AC-compressed text-even though those models do not learn. This is due to the weak compression offered by GZip. The poor compression rate, coupled with weak learning, means that the GZip M2 models' bits/byte performance lags behind even the 3m parameter M1 model.
Short Windows are the Best We see a similar effect in Fig. 5 which ablates the EqualInfoAC window size. In terms bits/byte, the shortest 16-bit windows perform the best. However, the next-best setting is the longest 128-bit windows, despite the fact that these M2 models fail learn almost anything beyond the uniform distribution. This unintuitive trend stems from the fact that longer windows translate to better compression rates (see Table 2). If we remove the effect of compression rate by looking at bits-per-token
15

---

Published in Transactions on Machine Learning Research (12/2024)
2
bits/token
bits/byte
1.5
EqualinfooC(l-116.v226) v=26)
EqualinfooC(/==32.w-2555
EquallnfoAA(/0=64.--2235 v=256]
1
EqualinfoAC(b=128, v=256]
10
10
10
Inference FLOPs/byte
Inference FLOPs/token
(a) Controlling for Compression Ratio
(b) Ignoring Compression Ratio
Figure 5: Performance of EqualInfoAC across various window sizes, be {16, 32, 64, 128}. When evaluating bbts/ (left) control for compression ratio, we see an unintuitive trend where for most model sizes b 16 is best but b = 128 is second-best. This is due to the higher compression rate achieved by longer Equal Info Windows. When evaluating tokens/byte (right), monotonic trend emerges, showing that shorter windows are easier to learn.
(Fig. 5b we see a clearer monotonic trend increasing window length makes it harder learn, as we move closer to simply running Arithmetic Coding over the whole sequence. For 64 and 128-bit windows, performance improvements with scale are small, but present; see Table 16 for exact nunbers.
Larger M2 Vocabulary is Helpful Tokenizing compressod text using a larger 16-bit vocabulary (v=65k) results in 2x higher token compression rate, seen in the leftward shift of cach curve in Fig. Arithmetic Coding methods, larger vocabulary also improves bits/byte seen downward shift in the curves. However, for GZip, see the opposite trend. Arithmetic Coding and GZip differ the most in their coding component, which suggests that the reason for this difference could lic there. Note that the header and footer present in GZip-compressee data do not explain this difference, see Appendix A.4 For EquallnfoAC/b-10) moving from ==256 to v-65k results in each window corresponding to a single token, which increases the "stability" of the token + text mapping. This could be one reason for the performance gain; see Section 6.] for more discussion of "stability".
For
Emergence with Scale is Unlikely Given the recent findings of Schacffer et al. 2023) we anticipate that continuing to scale models beyond 2 billion parameters unlikely to deliver an "emergent." ability to learn over AC-compressed text, since the bits/by byte metric we use is smooth.
Results Persist Under "Scaling Laws" Paradigm When scaling models, Hoffmann et al. 2022
recommend that training tokens should be scaled linearly with model size. However, in our experiments above, all models see the same number of tokens, regardless of model size. Consequently, our largest models may be somewhat "undertrained" our results, we reevaluate our models at earlier checkpoints selected maintain a constant ratio of training data model size. We find that all core trends are unchanged in this setting. See Appendix D.3 for dotails.
To test whether following the "scaling laws" recommendation influences
The same trend holds for larger 64 and 128-bit windows, but the performance increase with scale is slight that omit them from the graph. See Table for the exact values. 12e undertraining of our 2b models also visible in their validation loss curves, which still have significant. decreasing slope 200,000 steps, showing the models have not yet converged.
16

---

Published in Transactions on Machine Learning Research (12/2024)
3
EqualinfoAC((=16,.v255
GZip[v=256]
EqualinfoAC(0=166.--66
EqualinfoAC11==22-==56
GZip[v=65k]
2
bits/byte
107
10a
10
Inference FLOPs/byte
Figure 6: Using larger vocabulary for Arithmetic Coding derived methods improves both perplexity (lower bits/byte) as well as token compression rate (lower FLOPs/byte). Among settings where the M2 model actually learns, training over GZip-compressed data is the only case where increasing vocabulary size to 65k does not help performance.
5 Additional Experiments
At this point, we have established that while the simplest approaches to training compressed text fail, there are alternate compression schemes that are learnable. In this section, we conduct additional experiments to shed light on which aspects of different compression methods are difficult to learn and what contributes to their Icarnability.
5.1 Bitstream Tokenization Not the Main Source of Difficulty
The compression algorithms consider output bitstream, which we later chunk into tokens of fixed bit depth (e.g., 8-bit. tokens). As such, it is common for the bits representing single character UTF-8 byte to be split across multiple tokens. Compounding this issue is that the value of these tokens are contextually determined and may differ depending on the surrounding bytes.
The fact that both 8-bit and 16-bit token chunking strategies work suggests that this not too much of an issuc for the model. To further investigate this, we train two models-one one 25m and one 403m the raw bitstream output by Arithmetic Compression, i.e., each token is either 1 has size of 2. We use the same hyperparameters as in Section 3 Working at the bit level means that the output sequence is now longer than the input sequence, which was UTF-8 bytes. As such, this setting is not practical in the real world.
and the vocabulary
When trained to convergence, the two models have cross entropy losses of 0.693 for the 25m parameter model and 0.6928 for the 403m model not meaningfully better than the naive uniform distribution, which yields a loss of 0.693. This failure mode is the same as in Fig. 3 which suggests that AC encoding itself the main source of difficulty, opposed to any issue around tokenization vocabulary size.
17

---

Published in Transactions on Machine Learning Research (12/2024)
M1
The three currently Living species...
Compress (AC EqualInfoAC)
15888 51481
104 101 116 104 114 181 181 32
Compressed Tokens (same as M2 input)
Text Bytes (UTF-8)
Task
Inputs
Targets
Compress
84 32 116
15980 51481
114
181 181 32 99
Decompress
15888 51481
84 101
32 116 104
114 101 181
32 99
Byte LM
<empty>
84 184 181 32 116 184
32
Figure 7: Arithmetic compression and decompression cast as sequence-to-sequees tasks. To account for the strong performance that is possible by modeling only the output bytes in the decompression task, we also train a Byte LM on just the targets.
Table 5: Transformers struggle to learn Arithmetic Coding. In the sequeencefo-seqquenee setting, a model that learns AC compression//eecopressii /ecompresionn should have an accuracy 100. Our models perform much worse. When lasked with decompression in a requence-lo-sequuene format, our transformer's improvement over pure language modeling of the targets was not statistically significant (p = 0.07). Thus, the model not able leverage the compressed input. Similarly, AC compression is only learned to 1.7% accuracy.
Compression
Task
Accuracy
Cross Entropy
AC[v=256]
Decompress
76.98
0.751 +'t 0.005
Byte Level LM
76.86
0.755 + 0.001
EquallnfoAC(b=16, v=256]
Decompress
95.30
0.141 + 0.002
Byte Level LM
76.83
0.756 + 0.001
AC|u=250
Compress
1.7
2.489
5.2 Transformers Struggle to Learn Arithmetic Coding
Arithmetic Coding sequential algorithm that involves tracking multiple state variables as the input (byte) sequence is consumed. Each token in the output sequence represents multiple transformations of these variables, e.g., 8 transformations when using 8-bit token chunking. Theoretically, only 10 transformer layers are needed to have a computational path through the model layers that can process a sequence of 1,024 tokens as a chain, where each token conditions on the previous one. While most of our transformers have the capacity to model these sequences only our 25m model has fewer layers we see in practice that the Arithmetic Coding algorithm is still difficult to learn.
To directly diagnose the ability to track Arithmetic Coding, we format AC compression and docompression as Seguencce-l-sequencee lasks, as shown in Fig. 7 The input provides the model with the true text, so expect. model that is able to learn Arithmetic Coding should achieve accuracy of 100. We compress sequences of 1,024 bytes using M1 and Arithmetic Coding 13 We concatenate the bytes and AC output tokens to create the compression lask. For the decompression lask, we simply flip the order AC output lokens first and then bytes. The target token IDs (bytes or tokens) are shifted by the input vocabulary size, ensuring that they
We shorter raw text sequences to keep the final sequence length of inputs targets manageable.
18

---

Published in Transactions on Machine Learning Research (12/2024)
have distinct values. We use decoder-only transformer model with a causal attention mask, ie., even during the input sequence, future tokens are hidden from the model. We train models with 113m parameters. Loss, gradients, and evaluation metrics are only computed on the target tokens.
In the decompression task, the target tokens are bytes. By ignoring the imputs and just modeling the outputs, the decompression model can achieve decent performance without actually leveraging the input data. To control for this, we also train a byte-level language model baseline on the same sequence-to-sequnec data, excluding the input tokens. If the decompression model is actually learning to decompress Arithmetic Coding, would expect stronger performance than the byte-level baseline. As we see in Table _ the baseline model, which does not see the input tokens, has the same performance as the docompression model Clearly, the models trained for decompression are not actually learning to do decompression. In contrast, we see that models trained on EquallnfoAC(b=16, 2=256] do appear to learn to perform decompression. An M2 model trained to decompression EqualInfoAC((==1,, x=256] compressed data quickly jumps to 90% accuracy, in 9K updates, and continues to improve to 95% over training. The model is still improving as training ends with clear signs of overfitting, suggesting the expected 100% accuracy should be achievable with more data "5 It clearly leverages the input as byte-level language model trained over the same target tokens only reaches an accuracy of 76.
The model trained for compression actually shows some signs of learning. Training a language model directly on the compressed output results in the model learning a uniform distribution over tokens, see Fig. 3 When the model able to attend to the input text, we see that the performance in Table 5 is better than the uniform distribution (which would have cross entropy loss of 5.545). While this method shows some hope for the learnability of Arithmetic Coding, the need to include the input sequence negates the main advantage of compression, i.e. applying the model to shorter sequence. Additionally, the compressor's performance is far from the 100 it should be able to achieve.
We also find training on these sequenco-to-<equenee datasets to be less stable than training on the language modeling datasets. In our experiments, large performance swings and divergence were relatively common.
5.3 Larger Vocabulary Helps Beyond Increasing the Compression Ratio
Our best results training over compressed text use EqualInfoCC with 16-bit windows and vocabulary size at either 65k (best) or 256 (second-best). One clear advantage of the v-65k model is that has a 2x better token compression rate, so sees twice as much raw text during training. To assess whether its performance gain is due entirely to this advantage, we train a 25m parameter M2 model over the same dataset, but reduce its sequence length from 512 - 256. This model trains on half as many tokens, but sees the same amount of underlying text as the 2=256 model 16
Table G shows that even in this setting, the model with larger vocabulary is stronger 17 In fact, most of the bits/byte gain (84% absolute) is due to the structural change in tokenization, as opposed to the additional text seen. One possible explanation for its strong performance that the v=65k model uses exactly one token to represent each equal-info window. We'll see in the next section that in EqualInfoAC settings with multiple tokens per window, any non-initial tokens highly context-dependent, and learning procoeds curriculum from the "easy" window-initial tokens to the "harder" window-fing final tokens.
6 Analysis
In this section we examine how neural compression based tokenizers differ from standard tokenizers, and conduct additional analysis on training dynamics and learnability of compressed data. This analysis leads us
The slight gain is statistically insignificant (p =p=00 0.07).
18th could also be explained by how the end of sequence is handled, see Appendix D.5
sample of 20 batches from validation set when each example is 256 tokens, we compute our evaluation metrics over 40 batches.
16To compensate for the smaller number of tokens
17 may be possible to achieve further gains by increasing the token bit depth further. However, most deep learning frameworks do support using unsigned data types for inputs, and the resulting large vocabulary can cause a computational bottleneck in the final softmax layer.
19

---

Published in Transactions on Machine Learning Research (12/2024)
Table 6: Most of the gain of increasing vocabulary from 256 to 65k remains even the "byte matched" setting, where the models train over the same number of raw bytes. Performance gains seen between settings are all statistically significant.
Tokenization
Comparison
Bits /Byt
EqualInffAAC|==16, 2=256
1.472 0.004
EquallnfoAC]bb16, v-65k]
byte matched
1.287 0.003
EqualInffAC v=65k]
token matched
1.251 = 0.003
SentencePiece
ArthhmelicCodingiv=255]
100000
EqualinfoAC(b=16, v=256]
80000
Sentence Pairs
600000
40000
20000
25
Levenshtein Distance
Figure Edit distance between tokenized sentence pairs that differ only by a single prefix word. With SentencePiece, changing the prefix has a minimal effect on tokenization, limited the prefix itself. AC has the largest. edit distances, the prefix affects the probabilities M1 assigns to all subsequent text. EqualInfoAC falls in the middle, many distinct prefixes lead to the same windowing of subsequent text, and each window is encoded in isolation.
to several recommendations for future work developing new compression schemne that aim to be learnable by transformer models while delivering stronger compression than subword tokenizers.
6.1 AC-Based Tokenizations are Less Stable and Less Semantic than SentencePiece
We observe that text tokenized by AC-based methods is not "stable" that is, the tokenization of similar input data often leads to vastly different tokens sequences. To quantify this stability, measure the effect of adding different prefixes to a fixed test sentence. We sample 500 words from list of 3,000 common English
words [8 and prepend cach to the example sentence in Table 7 We then tokenize these new sentences using SentencePiece, AC(x=256), and EqualInfoAC|b=16, v=256]. Finally, for each tokenizer, we calculate the Levenshtein edit distance (Levenshtein 1965) between all pairs of tokenized sentences.
Fig. g shows histogram of these distances. We observe that SentencePiece tokenized sentence pairs always have a low edit distance, as the effect of changing the prefix is limited to the prefix tokens. In contrast, the edit distance between AC-tokenized sentence pairs is consistently high. The presence of the prefix affects the probabilities M1 assigns throughout the enfire sequence, resulting in widely varying token outputs. Edit distance with EqualInfoAC falls in between these two extremes. The degree to which the tokens after the prefix "match" depends on how the prefix aligns with EqualInfo window boundaries, which in turn affects the windowing of the rest of the sentence. Since there are relatively small number of possible window
coon/aa/entn http:///wooo.oooaaao/e/////////n
20

---

Published in Transactions on Machine Learning Research (12/2024)
Table 7: Comparing tokenization under SentencePiece vs. EqualInfoAC. SentencePieee gives a fairly stable text - token mapping. For instance, each occurrence of "elephants" maps to the same two-token sequence: [ elephant] [s]. By contrast, EquallnffAClb=166, v=65k] is less stable and less semantic. Each occurrence of "elephants" maps different tokens, and most tokens fail to align with meaningful linguistic boundaries (e.g,, word or morpheme).
Input Text
The three currently living species are: African savanna elephants, African forest elephants, and the Asian elephants.
SentencePiece
[The] [ three] currently] living] [ species] [ are] [:] [ African] [ [s] [a] [v] [anna] [ elephant] [s] [,] African]
Tokens
[forest] elephant] [s] [.] [ and] [ the] [ Asian] [ elephant] [s]
[.]
EqualInfoAC [b=16, vb=kk,
[The th] [ree c] [urrently 1] [iving ] [species] [ are] [: A] [frica]
[n sav] [anna] ele] [pha] [nts, ] [Afr] [ican ] [forest ] [eleph] [ants, [and the ] [Asi] [an e] [lep] [hant] [s.]
Tokens
alignments, many sentence pairs have highly overlapping token sequences. As AC tokenization is so much less stable than the other scttings, we restrict further analysis SentencePiece and EqualInfoAC.
While the performance of our EqualInfoAC(-=16, v=65k] model approaches that of the SentencePiece baseline, our edit distances analysis suggests that the two tokenization schemes differ in many regards. To better understand these differences in qualitative terms, we compare the tokcnizations of a single sentence in Table 7
First, we observe that SentencePiece produces a stable text + token mapping. For example, "elephants" appears three times the sentence, and stably maps to the same two-token sequence in all cases: [ elephant] [s]. Similarly, both occurrences of "African" map to the same token: African]. In contrast, the EqualInfoAC tokenization is relatively unstable, with each occurrence of these words being segmented in a different way, and yielding different token sequences.
Second, we find that the SentencePiece tokenization is more "semantic", by which we mean that the segmentation it induces aligns better with meaningful linguistic units-words and morphemes. While there are some exceptions, c.g. "savanna" " being tokenized as [s] [a] [v] [anna], the more common case is that whole words are parsed as single tokens (e.g,, currently); or into meaningful morphemes (e.g., elephant-s). By comparison, EqualInfoAC tokenization appears to almost entirely disregard word and morpheme boundaries. As one example, we see "Asian elephants." " tokenized as [Asi] [an e] [lep] [hant] [s.].
Despite these differences, there is an important similarity between SentencePiece and EquallnfoAC/b=16, v=65k]: they are both stable in the token + text direction. That is, a given to- ken ID, e.g., token #500, will always map to the same output text. This "transparent decoding" property likely makes it casicr for a downstream model to learn over these tokens
When we move to versions of EqualInfoAC that contain mulliple tokens per window, such as EquallnfoAC/b=16, v=256], this transparency is destroyed for all non-initial tokens within a window. This is illustrated in Table 3 When the same token appears window-initially in different contexts, see the window text has a stable prefix-es e.g., token #151 always maps to the prefix "le-". However, when occurring as the second token within a two-token window, there are no apparent correspondences between window text. 20 As EqualInfoAC window length increases, the proportion of tokens that are stable decreases. This may explain the observed difficulty of learning over longer windows. The window text for all instances of these tokens can be seen Appendix D.8
Note that Table examines window - text, as opposed to token text correspondences. This is because for multi-token windows, the mapping from tokens to text is not well defined. More specifically, each
1Padddin to reach specific window size require extra computation to discern between padding and characters that compress to all zeros, however find Appendix D55 that it is not an issuc for M2 models. 20 A repeated text substring that happens he aligned with window multiple times is one of the few cases where the second token will represent the same
21

---

Published in Transactions on Machine Learning Research (12/2024)
Table 8: Window-initial tokens have stable token - text mappings, while non-initial tokens have contextual meaning and are thus unstable. We tokenize 20 documents with EqualInfoAClb-16, u=256] and show the full window text in random sample of cases where a specific token appears the first or second position within the window.
Window Position
Token
Window Text
151
1
[ew // [1ea]
[1ed] this
[1en] / [less]
[1ed] / [1s]] [lew
2
[thoug]
[ust]
[etti]
[mpo] / [thoug] / un] [imag]
185
1
[ord / [or k| (ery) may)
[ord] / |or fl / [or a1] / [or a | [ore i] [ora]
2
/ [cian] / [onte] [h de)
[cri] [opp] [ides]
[240, 243]
[145, 248]
[ [216, 68]
1111000011110011 1001000111111000
1 1101100001000100
The_ th ree__ wurrenlly__ll [ [ S aree| :_A
fricaa ii_______ sav lnna| | _ele| pha Ints, | Afr l/lliicnn_foorr | forest_ an_e| 1ep hant
|eleph lntts, larrs___aan_____lla
Figure 9: An illustration of the mapping between characters (bottom), bits (middle) and tokens (top) in the EqualInfoAC(/=16, 2=256] setting. Each equal-info window corresponds to 16 bits of AC output, which are chunked into two 8-bit M2 tokens from a vocabulary of 256. Colors indicate whether each character contributes the first token, second token, both tokens within a window. We note that window-initial characters not well compressed, so the initial 8-bit token tends to only cover one or two characters.
character maps to a particular subsequence of the compressed bitstream, but these may not align with token boundaries 21 Fig. g illustrates the mapping between characters, bits, and tokens. We find that many windows contain a character (shown in purple) whose bits are split across two 8-bit tokens.
Fig. g also highlights that window-initial characters are not being well compressed, with the window-initin token often only covering one two characters. This is due to our EqualInfoAC procedure fully resetting MI's context at every window boundary. With context, M1 cannot make confident predictions, leading to more bits being needed to represent the initial character. While this hurts the overall compression ratio, there is benefit for learnability in that each window can be decoded in isolation. In Appendix A.2 we experiment with maintaining M1 context across two or more windows, and find that the improvement in compression ratio does not justify the degradation in bits/byte.
6.2 AC Decoding is Learned Step-by-Step
As Arithmetic Coding is a sequential (left-to-right) and contextual algorithm, the text represented by a given token will differ based on the previous token. As such, a model should perform better on a token has a strong understanding of the token before When using EqualInfoAC compression, each window represents an independent Arithmetic Coding document. As we move deeper into the window, more and more AC decompression must be done to understand the token.
This can source instability, window-initial takens, Appendix
22

---

Published in Transactions on Machine Learning Research (12/2024)
8
Token
Accuracy Increase
Accuracy
6
6
4
2
20000
40000
60000
0
20000
40000
60000
Step
Step
(a) Accuracy per token position
(b) Increase over "trivial" accuracy per token position
Figure 10: Earlier tokens within the 8-token window of an EquallnfoAC(0-11,, t= model are learned earlier in training. As training progresses, the model "unlocks" the ability to model tokens deeper and deeper into the window. The plot on the right shows the increase over "trivial" accuracy accuracy-which which we define as the maximum accuracy achieved in the first 2,000 steps of training. (Note, window-final padding makes trivial accuracy higher for later positions.) For tokens #1-3, later tokens reach higher accuracy (3 > > 1), likely due to the benefit of local context. For tokens #4-8, accuracy deteriorates, indicating that the model has trouble tracking the AC algorithm for more than -32 bits.
To understand how a token's position within a window affects learning, we track the average accuracy each position within the 8-token windows of 403m parameter EquallnfoA((==61 v=256] mode during training. Fig. 10 shows both accuracy (left) well as the increase over "trivial" accuracy (right), which we define the maximum accuracy achieved in the first 2,000 steps of training. By that point in training, the model predictions no longer change drastically between updates, and trivial patterns, such as how padding generally reduces the number of possible tokens at the ends of windows, have already been learned. Looking at accuracy increase highlights the "sequential learning" trend by discounting any part of accuracy that is text independent. In particular, we nole that window-final tokens have a non-uniform distribution due the use of window-fing final padding bits (see our EqualInfoAC formulation in Section 3.3), which can be learned without any understanding of the text.
We observe two interesting trends. First, there is a clear ordering to when the model starts to make meaningful (non-trivial) progress on given position. The initial token (#1) is learned first, followed fairly quickly by #2 and then #3. Later tokens are only "unlocked" after 10,000 training steps, suggesting that the ability to model these tokens builds on a foundation of understanding the preceding tokens within the window.
The second trend concerns the accuracy reached each position. Here, we observe an increase in accuracy from #1 < #2 < #3, followed by decrease from #3 < #4 < #5 and so on 23 across the first three positions due to the benefit of extra leftward context
We interpret the increase 24 This is akin to the initial byte in a word being harder to predict than the following bytes. The decreasing performance at tokens #4 and beyond suggests the model is unable to track AC decompression indefinitely. While the model clearly learns to decompress longer sequences as training progresses, reliably decoding past 32 bits of AC output appears to be a challenge.
6.3 Learnable Distributions are Less Uniform
A well-known result in the compression literature is that there can be no recursive compression Maahonyy The compression algorithm removes information captured by its model, resulting in a uniform output
2013).
2he absolute accuracy of the EqualIntoAC(b=64, e=256] model is relatively poor, but its relatively long window provides the clearest illustration of these positional trends. We observe similar treuds for A e=256) which has smaller windows but much stronger performance.
The final token #8 also fits this trend when looking the increase non-trivial accuracy. The accuracy is higher than previous tokens, #4-7, due the skewed distribution induced by window-final padding.
24 While suggests that 24 bit windows could be effective, but in Appendix A.I we found it is not.
23

---

Published in Transactions on Machine Learning Research (12/2024)
1
10-1
KLfobserved || unifomm
10
KLoobserved uniform)
10-3
10-5
10
10
RNG
10
Arithmetiicoodinglv255]] StaticAQ[v=256]
10
10-9
GZip[v=256]
10-11
EquallnfoAC(b=16]
10-11
EqualInfoAC[b=64]
2
4
8
10
12
14
16
2
6
8
10
12
14
16
Bit N-grams
N-Bit Tokens
(a) bit n-grams counting all overlapping occurrences
(b) n-bit tokens following our M2 tokenization
Figure 11: As the bitstream is grouped into larger units, the empirical distribution moves away from uniform. We plot KL divergence of observed n-gram distributions from the uniform distribution, across various n- n-gram sizes. While AC compressed data would be difficult distinguish from random data, we find there are still patterns to capture when using other compression schemes, particularly for GZip and shorter EqualInfoAC windows. Compared to the left plot, find that the tokenized bitstream (sec Section 3.4 has more information for M2 to capture.
that appears random to the original model. However, our setting is not recursive compression. Instead, a separate and larger model trained on the compressod output, which should be able capture new patterns in the bitstream.
Despite this, the output of compression using M1 appears very uniform, evidenced by the minimal gains from modeling the unigram token distribution in Table B Therefore, it seems reasonable that this uniformity could make it hard for M2 to learn (as all patterns must be contextual). We investigate this by plotting the KL, divergence (Kullback & Leibler 1951 between the observed empirical distribution and a uniform distribution for different segmentations of the bitstream. If the underlying distribution of bits was truly random and independent, then the distribution of unigrams for some bitstream segmentation should remain uniform p(b....., b(+n)= = IT (p(b,)) and therefore the KL divergence should remain close to zero. On the other hand, if the distribution diverges from uniform, there is contextual information to be learned when training LLM to model p(b.|b.....,6 bi.n.1.).
We segment the bitstream either into bit n-grams, where successive n1 n-grams are allowed to overlap, or into n-bit tokens, following our M2 tokenization procedure see Section 3.4 We only plot tokenization into n-bits that are factors of 16, otherwise tokens would cross window boundaries the EquallnfoAC(b=116 setting,
As baseline, we used the cryptographic secrets package in Python generate bitstreams that should be truly random and independent. As such, the KI. divergence should remain at when segmented in the same way as the compressed data. The reason this does not hold in Fig, [ that the maximum likelihood estimate of entropy, H = Exe p(x) log, p(r), is negatively biased (Paninski 2003). In Fig. 17 we see that when using a Madow estimator MMiller 1955) to correct for this bias, the expected KL of 0 is well within sampling noise bounds. To account for noisc in the entropy estimation, we plot 90th percentile intervals of the KL, divergence between the observed entropy from 100 disjoint samples of the data and the uniform distribution
25 As the number of bits in segmentation grow, the vocabulary size increases exponentially, requiring many samples. Thus expect noise the cutropy estimate grow with This holds, but it obfuscated the scaling in Fig. [ In fact, the magnitude of the noise for settings such GZip and EqualInfoAC larger than for AC RNG. This noise behavior in Fig. See Appendix 166 more information on entropy estimation and bias correction.
24

---

Published in Transactions on Machine Learning Research (12/2024)
The AC and RNG lines in Fig. 11 are very similar and their sampling noise intervals have large overlaps. This suggests that the data generated by AC compression with M1 is difficult to distinguish from random data 26 This is a possible explanation for why M2 models trained on AC data only learn to output a uniform distribution, as seen in Fig. 3
In Fig. [1 we see that GZip is the least uniform, which is expected as it has the worst compression rate among these settings. However, the segmentation into tokens does not result in much extra information. This is again suggestive that the differences between the "coding" components of GZip and Arithmetic Coding are important for learnability. It is also possible explanation of why GZip is the one setting where using 16-bit tokens does not improve performance.
Similarly, Fig. 11 shows that EquallnfoAC(|=16] has the most information among the Arithmetic Coding approaches. Given that this is the most learnable setting, it suggests that non-uniformity of the bitstream may be important for learning. We also see a large increase when moving to 16-bit tokens, providing a further possible explanation for why larger vocabulary is helpful (see Section 5.3 Finally, we note that StaticAC has less information than EqualInfoAC(b=
suggesting that weakening the "coding" component of Arithmetic Coding is a more effective way to retain information and increase learnability for M2.
7 Conclusion
We have shown there is promisc in the idea of training LLMs over neurally compressed text. In the bost case, this will allow training over text that is better compressed than standard subword token sequences, while maintaining learnability. This an appealing prospect, as models that read and write more text per token are more efficient to train and serve, and can model longer dependencies.
While the "very simplest" approach does not work (training directly over tokenized AC-encoded bitstream), we showed that relatively simple mudiffeatton-comprssst us within striking distance of popular tokenizers. When measured in terms of perplexity achievable at fixed inference cost (FLOPs/byte)) we find that our method outperforms raw byte-level models, and comes increasingly close to the performance of SentencePiece tokenization as scale increases to 2 billion parameters.
via Equal Info Windows-alreadd brings
While bespoke compression methods have developed around different modalities (e.g., text, audio, images, video) and different applications (e-g., delta-of-delta for regular repeating timestamps (Pelkonen et. al. 2015 to our knowledge, no efficient compression methods have been designed specifically for use as LLM tokenizers. We are optimistic that future work will create such methods. Compared to today's subword tokenizers, we expect these hoth (i) will deliver higher compression rates, (ii) will come closer to equal information per token, thus allocating compute more effectively, and (iii) will give models a more direct view of the underlying raw text, thus helping on spelling and pronunciation tasks. As a tradeoff, we expect these neural tokenizers will be somewhat less stable in their text ++ token mapping, but perhaps not so unstable as our approach here. In particular, we think it is worth exploring methods under which a given word typically maps to relatively small number (tens not thousands) of relatable token sequences.
One direction we left unexplored is the idea of passing information between the compressing model (M1) and the LLM trained over compressed text (M2). Some additional signal of MI's internal state or output may be helpful for M2 to accurately simulate M1, which a prerequisite to flawlessly encoding and decoding M1-compressed text.
For hill-climbing in this space, we found it useful to iterate the sequence-to-sequeenc sub-tasks of compression and decompression, which should, in theory, be learnable with high accuracy. Specifically, if future work can devise strong (-10x) compressor that a transformer can be trained to accurately encode and decode, we expect that this will be an ideal candidate for tokenizing text for LLMs.
Fo >,2, 2, the AC entropy statistically significantly less than the RNG entropy, however, differences in the mean entropy only start appear after -8 decimal places.
25

---

Published in Transactions on Machine Learning Research (12/2024)
Acknowledgments
We would like to thank Ben Adlam, Grégoire Delétang, Rosanme Liu, and Colin Raffel for detailed comments on an earlier draft. We're also grateful to Peter Liu, both for helpful discussion, as well as for building some of the infrastructure that made our experiments easier to run. Finally, we thank Doug Eck, Noah Fiedel, and the PAGI team for ongoing guidance and feedback.
Bibliography
Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. ETC: Encoding Long and Structured Inputs in Transformers. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp- 268-22 284, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v112022.emmms emnnpp main.19. URL https://aclanthoology/ org 2020. emnlp-ma mapppmminn.... 19
Rami Al-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. Character-Level Language Modeling with Deeper Self-Attention Proceedings of the AAAI Conference on Artificial Intelligence, 33 (01):3159-314) Jul. 2019. doi: (0009/aaai..83111333011111 URL https://ojs. aaai. org/index. p
AMAT/artiicle/riew/11B3.
Mehdi Ali, Michael Fromm, Klaudia Thellmann, Richard Rutmann, Max Lübbering, Johannes Leveling, Katrin Klug, Jan Ebert, Niclas Doll, Jasper Buschhoff, Charvi Jain, Alexander Weber, Lena Jurkschat, Hammam Abdelwahab, Chelsea John, Pedro Ortiz Suarez, Malte Ostendorff, Samuel Weinbach, Rafet Sifa, Stefan Kesselheim, and Nicolas Flores-Herr. Tokenizer choice for LLM training: Negligible crucial? In Kevin Duh, Helena. Gomez, and Steven Bethard (eds.), Findings of the Associalion for Compulational Linguisties: NAACL 2024, pp. 3907-3924, Mexico City, Mexico, June 2024. Association for Computational Linguistics. doi: 10.18653 v1 /22/222244../// wwn.244..innngn-aaaa 247.. URL battps://aclantholl.e org/2024. f indinggs 247
Alexei Baevski, Henry Zhou, Abdelrahman Mohamed, and Michael Auli. wav2vec 2.0: A Framework for SelerSiue Learning of Speech Representations. In Proceedings of the 34th International Con- ference on Neural Information Processing Systems, NeurIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 97817138295466. URL https://prooceedings http://rooeddnaa.a.er........e/p ceeurippscc/papee/220000.. pdf
Johannes Ballé, Sung Jin Hwang, and Eirikur Agustsson. TensorFlow Compression: Learned Data Compres- sion, 2024. URL http:///ittuu..comm http://www......ee..oooooo///tta
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The Long- Document Transformer, December 2020. URL. http://arxiv.org org/ abs/ 2001/00000...1000
05150
Zalán Borsos, Raphaäl Marinicr, Damien Vincent, Eugene Kharitonov, Olivier Pictquin, Matt Sharifi, Dominik Roblek, Olivier Teboul, David Grangier, Marco Tagliasacchi, and Neil Zeghidour. AudioLM: A Language Modeling Approach to Audio Generation. IEFE/ ACM Transactions on Audio, Speech, and Language Processing, 31:2523 2533, 2023. doi: 2ttp:/TASLP2222....222
URL https: :/ta////avvi org/ aalaaba//222 /209
03143
Kaj Bostrom and Greg Durrett. Byte pair encoding is suboptimal for language model pretraining. In Trevor Cohn, Yulan He, and Yang Liu (eds.), Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 4617-4624, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v1 /1066/3//1//22000fdiigge/m//////
URL bttta://aaclatthooogy.oo/////// windiiig-nnnngnnnnnnn... emnlp.414
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milhe and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:/tthwb.cmmoo//////////
26

---

Published in Transactions on Machine Learning Research (12/2024)
Peter F. Brown, Vincent J. Della Pictra, Stephen A. Della Pietra, and Robert L. Mercer. The Mathematics of Statistical Machine Translation: Parameter Estimation. Compul. Länguist., 19(2):263-33 311, jun 1993. ISSN 0891-2017. URL
Rewon Child, Scott Gray, Alec Radford, and lyya Sutskever. Generating Long Sequences with Sparse Transformers, April 2019. URL http:://arxiw.org//aaee
Dokook Choe, Rami Al-Rfou, Mandy Guo, Heeyoung Lee, and Noah Constant. Bridging the Gap for Tokenizer- Free Language Models. CoRR, abs/1908.10322 2019. URL http://arxiv.org/ http///a/////./.. 10322
Junyoung Chung, Sungjin Ahn, and Yoshua Bengio. Hicrarchical Multiscale Recurrent Neural Networks. In International Conference on Learning Represenlations, 2017. URL https://openreviex wttpe/rreiieeeeeeeoruumllliii
Sid10sfg1
Yu-An Chung, Yu Zhang, Wei Han, Chang Chiu, James Qin, Ruoming Pang, and Yonghui Wu. w2v-BERT: Combining Contrastive Learning and Masked Language Modeling for Self-Supervised Speech Pre- Training In 2021 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), pp. doi: 10.1 B0/////SRSS500000.0 266.988853..... URL htt.::tts///// httpps://arrv..orr//bb//////// 22020
244-250, 2021.
Jonathan H. Clark, Dan Garrette, Tulia Turc, and John Wieting. Canine: Pre-training an Efficient. Tokenization- Free Encoder for Language Representation. Transactions of the Association for Computational Lònguistics, 10:73 91, 2022. doi: 10.1162/tacl a 00448. URL https://aclanthoooggy.yooo wtt.oogg////// 2022.2022.c22 tacl-1.5
Gautier Dagan, Gabriel Synnaeve, and Baptiste Rozière. Getting the Most Out of Your Tokenizer for Pre-training and Domain Adaptation. In Forty-first International Conference on Machine Learning, ICML, 2024. URL https::/oppnreviier wttprriwwwweeeeeeeeeee wett/Eoruun1dd22/Ba11....3
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoe Le, and Ruslan Salakhutdinov. Transformer- XL: Attentive Language Models beyond a Fixed-Length Context. In Proceedings of the 57th Annual Meeting of the Associalion for Compulational Linguisties, pp. 2978 2988, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18853/v1 / 1285. URL https://aclaattholog: wtwp:oooooyooog/11-110000 org/P19-1288
Simon DeDeo, Robert X. D. Hawkins, Sara Klingenstein, and Tim Hitchcock. Bootstrap Methods for the Empirical Study of Decision-Making and Information Flows in Social Systems. Entropy. An International and Interdisciplinary Journal of Entropy and Information Studies, 15(6):2246-2277 2013. ISSN 1099-4300. doi: 10.3390/e1506222 URL httph::////// //www mdpi www.m///10---00 401099444300/56//226666
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, Mareus Hutter, and Joel Veness. Language Modeling Is Compression. In ICLR, 2024. URL http:://aaxxvv.orrab/////// 10668
P Deutsch. GZIP file format specification. RFC 1952 May 1996. URL rfc1952.txt.
P Deutsch and J-L Gailly. ZLIB Compressod Data Format Specification. RFC 1950, May 1996. URL https://wwx httt:://www.rfceddteee
rfc-rdiciitiee tor. wwoo..rgg//cc/fcc15..oo. txt.
Jarek Duda. Asymmetric Numeral Systems: Entropy Coding Combining Speed of Huffman Coding with Compression Rate of Arithmetic Coding, January 2014. URL http://axxvvv..oraaa/// 0ttbs///11..2P 25400
B. Efron. Bootstrap Methods: Another Took at the Jackknife. The Annals of Slatistics, 7(1):1-20 1-6 1979. ISSN 00905364. URL http::/sww.jstox httpt//r..or//taae////eee/e/
Jerome H. Friedman. Greedy Function Approxiimaiooooonno: A Gradient Boosting Machine. The Annals of Statistics, 29(5):1189-1232 2001. doi: 10.1214/aas/1011220544 URL
Kunihiko Fukushima. Cognitron: A Self-Organizing Multilayered Neural Network. Biological Cybernetics 20:121-136, 1975. doi: B0.1007/BF000426333 URL
BF00342633
27

---

Published in Transactions on Machine Learning Research (12/2024)
Philip Gage. A New Algorithm for Data Compression. C Users Journal, 12(2):23-3) 38, 1994. URL www.com///oo//. http://///uaaeeee///////////////
http:
7/ 1/www.
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. The Pile: An 800GB Dataset of Diverse Text for Language Modeling, December 2020. URL http: /tttp://arxv..... org/ /bs///b1..0//2222222
Nathan Godey, Roman Castagné, Éric de Clergerie, and Benoît Sagot. MANTa: Efficient Gradient- Basod Tokenization for End-to-End Robust Language Modeling. In Findings of the Association for Compulalional Linguislics: EMNIP 2022, pp. 2859 2870, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguisties. doi: 10.18653/v1 /22/0222///2222222 fod.2...ninngeemml...22. URL https
aeclaanthooog..org/22000 http//222..idddins-emmmmmm 207
Omer Goldman, Avi Caciularu, Matan Eyal, Kris Cao, Idan Szpektor, and Reut Tsarfaty. Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performance, March 2024.
URL http::::://www.wo////aaaaaee/eee bbaprg/abs/44000 06265
Alex Graves. Adaptive Computation Time for Recurrent Neural Networks, February 2017. URL http:
Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Marc van Zee. Flax: A Neural Network Library and Ecosystem for JAX, 2020. URL http://github.com/
google/flax
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the Knowledge in Neural Network, March 2015. URL
02531
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katherine Millican, George den Driessche, Bogdan Damoe, Aurclia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack William Rae, and Laurent Sifre. Training Compute-Optinal Large Language Models. In Advances in Neural Information Processing Systems, 2022.
URL https:
7opennrvvie.. //openreriev.net/fforum//// wttp:///forrurno---BBBUUUOOO
Paul G. Howard and Jeffrey Scott Vitter. Analysis of Arithmetic Coding for Data Compression. Information Processing & Management, 28(6):749 763, 1992. ISSN 0306-4573. doi: 10.1016 (00111/0088000557722))900060
URL https:://ww http://ww..ccencccirrttt.t.oo wtt.a//wwcc.ccc..........o.aoaaa
David A. Huffmann Method for the Construction of Saaeiiimmmm-nnddannnn Codes. Proceedings of the
IRF, 4009): 1101, 1952. doi: T0.110//TRPROC..112222:2 URL
ieee. org/
document/405111
J. D. Hunter. Matplotlib: A 2D Graphics Environment. Computing in Science & Engineering, 93): 95, 2007. doi: 10.1109/M M000///.....00..5.... URL
Zhiying Jiang, Matthew Y. R. Yang, Mikhail Tsirlin, Raphael Tang, and Jimmy Lin. Less is More: Parameter- Free Text Classification with Gzip, December 2022. URL http::/arxiv.crt org/ hoog//bbe abs/ 2212 09410
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jelfrey Wu, and Dario Amodei. Scaling Laws for Neural Language Models, January 2020.
URL http://arxiv.co wrw/ 2////0000.0000 08361
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The Efficient Transformer. In International Conference on Learning Representations, 2020. URL http:////pppppoeeeeeeeeeee///ttp
Taku Kudo. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 56-75, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/11/P18-1007 URL http:/tccss///claaatoooo.ooooo
28

---

Published in Transactions on Machine Learning Research (12/2024)
Taku Kudo and John Richardson. SentencePiece: A Simple and Language Independent Subword Tokenizer and Detokenizer for Neural Text Processing. In Proceedinggs of the 2018 Conference on Empirioul Methods
in Natural Language Processing: System Demonstrations, pp. 66 71, Brussels, Belgium, November 2018. Association for Computational Linguistics. doi: 10.18653 /1/B///1//D111////1 URL https:///claattholggs org/D18-2012
S. Kullback and R. A. Leibler. On Information and Sufficiency. The Annals of Mathemalical Slatistics, 22(1): 79 86, 1951. doi:
URL https::/doi..rg// 1221////m//11772/99335339
M Oguzhan Külekei. Compressed Context Modeling for Text Compression. In 2011 Data Compression Con- ference, pp. 373 382, 2011. doi: M.1109/DCC.20111 URL 5749495
Brian Lester, Joshua Yurlsever, Siamak Shakeri, and Noah Constant. Reducing Retraining by Recycling Parameter-Ffficien Prompts. arXiv preprint 225::2208.05577,, aug 2022. URL htttps://arxiis org/ / 2208. 005777
Vladimir I. Levenshtein. Binary codes capable of correcting delctions, inscrtions, and reversals. Soviet physics. Doklady, 10:707 710, 1965. URL https: pettss:/api... www.sssicmmacalarr....eee.. oorraa/accccccoooooooooooo/ooopa :t0rrpu1::::002155: 60827152
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast Inference from Transformers via Speculative Decoding, In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 19274-19286. PMLR, 23-29 29 Jul 2023. URL https: //proceedings. caatinnsmmllrrr..l..... mlr. ppreass/202/levviahaan222 html
Rosanne Liu, Dan Garrette, Chitwan Saharia, William Chan, Adam Roberts, Sharan Narang, Irina Blok, Rj Mical, Mohammad Norouzi, and Noah Constant. Character-Aware Models Improve Visual Text Rendering. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 16270 16297, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 00//655311/2223... lon-long.9000 900. URL https://aclaatiiooog..oo/// -a-p://0oo0/022222111111111 .900 900
Matt Mahoney. Data Compression Explained. 2013. URL httpp://naattaaooeeyeee/////////
Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish, Alliot Nagle, Martin Jaggi, Hyeji Kim, and Michael Gastpar. Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chains. ArXie, 0bs/2440.04161,, 2024. URL
http://wwww...gg/ab////000000. 04161
George Miller Note on the Bias of Information Estimates. In Information Theory in Psychology: Prob- lems and Methods, pp. 95-100. Free Press, 1955. URL http:::/www..iiieeeppppeeeeeeeee com/ document?vid
Vinod Nair and Geoffrey E. Hinton. Rectified Linear Units Improve Restricted Boltzmann Machines. In Proceedings of the 27th International Conference on International Conference on Machine Learning,
ICML'10, 10, pp. 807-814, Madison, WI, USA, 2010. Omnipress. ISBN 978-1-60558-907-7. URL https
//www.cz www.oto.....t.oooo. perraat..euu./tttttt//aaaaaprere
Liam Paninski. Estimation of Entropy and Mutual Information. Neural Computation, 1561)1119111253 URL.
June 2003. ISSN 0899-7667.
doi:
089976603321180277
R. Pasco. Source Coding Algorithms for Fast Data Compression (Ph.D. Thesis Abstr.). IEEE Transcctons Information Theory, 23(4):548-54 1977. doi:
URL https://ieeexpplore
ieee. feee.org/dee htg//docmmmen/1055799
Tuomas Pelkonen, Scott Franklin, Justin Teller, Paul Cavallaro, Qi Huang, Justin Meza, and Kaushik Vocraraghavan. Gorilla: a Fast, Scalable, In-Memory Time Scries Database. Proc. VLDB Endow., 8(12): 1816-18277 aug 2015. ISSN 2050-8097. doi: 10.14778//2224032222220 URL htttps://dot http:::///iioo/////// 1.t..//////..//.................
2824032. 2824078
29

---

Published in Transactions on Machine Learning Research (12/2024)
Ofir Press, Noah Smith, and Mike Lewis. Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation. In International Conference on Learning Representations, 2022. URL
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the Limits of Transfer Learning with a Unified Text-lo-Text Transformer. org/
Journal of Machine Learning Research (JMLR 2020), 21(140):1-67 67, 2020. URL papers/v21/20 00t-0744.htt htmml
Nived Rajaraman, Jiantao Jiao, and Kannan Ramchandran. Toward Theory of Tokenization in LLMs. ArXiv, abs/2400.088335 2024. URL https://arxiv.orgg/ htwplv..rr//bbba wrgg/b/s//04..////
J. J. Rissanen. Generalized Kraft Inequality and Arithmetic Coding. IBM Journal of Research and Dewelopment, 20(3):198-2000 1976. doi: 10.1147/rd.203.011 URL htttps://seeexplore ieee. org/
document/5391119
Adam Roberts, Hyung Won Chung, Gaurav Mishra, Anselm Levskaya, James Bradbury, Daniel Andor, Sharan Narang, Brian Lester, Colin Gaffney Afroz Mohiuddin, Curtis Hawthorne, Aitor Lewkowyez, Alex Salciamu, Mare Zee, Jacob Austin, Sebastian Goodman, Livio Baldini Soares, Haitang Hu, Sasha Tsvyashchenko, Aakanksha Chowdhery, Jasmijn Bastings, Jannis Bulian, Xavier Garcia, Jianno Ni, Andrew Chen, Kathleen Kenealy, Kehang Han, Michelle Casbon, Jonathan H. Clark, Stephan Lee, Dan Garretle, James Lee-Thorp, Colin Raffel, Noam Shazeer, Marvin Ritter, Maarten Bosma, Alexandre Passos, Jeremy Maitin-Shepard, Noah Ficdel, Mark Omernick, Brennan Sacta, Ryan Sepassi, Alexander Spiridonov, Joshua Newlan, and Andrea Gesmundo. Scaling Up Models and Data with t5x and seqio Journal of Machine Learning Research, 24(377):1-8 8, 2023. URL http://jmlr org org httg//pper//2//2207775 html
Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are Emergent Abilities of Large Language Models Mirage? In Phirty-Sevenni Conference on Neural Information Processing Systems, 2023. URL https //arxiv.org/abat aataaab///44..4 2304 15004
Craig W. Schmidt,, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. Tokenization is more than compression, 2024. URL htttp::/arxxi... http:://aaxiv..o//bb////////// 18376
Mike Schuster and Kaisuke Nakajima. Japanese and Korean Voice Search. In International Conference on Acoustics, Speech and Signal Processing, pp. 5149 5152, 2012.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural Machine Translation of Rare Words with Subword Units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1715 1725, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 11111865111111 1162. URL http:psss//caaannooogggoooo/////
Claude Elwood Shannon. A Mathematical Theory of Communication. The Bell System Technical Journal, 27:379-4233 423, 1948. URL http::/pplan9.belll bell-labs....... com/ wwt.c///o///aaaaaeeeeeeeeee
pdd
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self- Aelennittntion with Relative Position Representations. In Proceedings of the 2018 Conference of the North American Chopter of the Association for Computational Linguistics: Human Language Techmologies, Volume (Short Papers); pp. 464-468, 4668 New Orleans, Louisiana, June 2018. Association for Computational Linguisties. doi: (0.18653/v1/N18-22 aclanthology org/N18-2074
URL https://
Noam Shazeer and Mitchell Stern. Adafactor: Adaptive Learning Rates with Sublinear Memory Cost. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4596 4604. PMLR, July 2018. URL httpps:/procceeding. mlr. press/
v80/shazeer18a html
Samuel Stanton, Pavel Izmailov, Polina Kirichenko, Alex Alemi, and Andrew Gordon Wilson. Does Knowledge Distillation Really Work? 2021. URL https: http:://arrvv.rrr/a////1111.1.. wttp:///b/b.bb.....11.....
30

---

URL Published in Transactions on Machine Learning Research (12/2024)
Yi Tay, Vinh Q. Tran, Sebastian Ruder, Jai Gupta, Hyung Won Chung, Dara Bahri, Zhen Qin, Simon Baumgartner, Cong Yu, and Donald Metzler. Charformer: Fast, Character Transformers via Gradient- based Subword Tokenization. In International Conference on Learning Representations, 2022. URL
Dan Tito Svenstrup, Jonas Hansen, and Ole Winther. Hash Embeddings for Efficient Word Representations. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL htttps://proceedingg.o f005041100004011332222aaa----203
wtwpapereppppppppppeepeee /ttpr/ppp..cpppppp..l/l///////// filess/papeee///7///e//
paf
Chandra Shekhara Kaushik Valmeekam, Krishna Narayanan, Dileep Kalathil, Crean-Francois Chamberland, and Srinivas Shakkottai. LLMZip: Lossless Text Compression using Large Language Models, June 2023.
URL http::/arxiv..rg//// httpg//bb/23306... 2306.04050
Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural Discrete Representation Learning. In Proceedings of the 31st International Conference on Neural Information Pro- cessing Systems, NeurIPS'17, pp. 6309-6318, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964. URL
http:/senerrri..ccccooo sapper.di:
Eilee//paper2011//flll/
Guido Van Rossum and Fred L. Drake. Python 3 Reference Manual. CreateSpace, Scotts Valley, CA, 2009. ISEN 1441412697.
Dusan Varis and Ondřej Bojar. Sequence Length is a Domain: Length-based Overfitting in Transformer Models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 8246-8257 Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. main.650. URL
doi: 10.18653/vvl /
org/ 20212 momlp-main... 650
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need. In Advonces in Newral Information Process- ing Systems 30, pp. 5998 6008 Curran Associates, Inc., 2017. URL. http::/ nips. cc/paper/ pdf
T1Bl-attenttoon----lll
Luke Vilnis, Yury Zemlyanskiy, Patrick Murray, Alexandre Tachard Passos, and Sumit Sanghai. Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. PMMLR, 23-29 Jul 2023. URL https://prooceednng. .ml. wtt.::/www.rrrres.eeeeee wtw.ppeesss/////eee http////2///v/viiieee/ html
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, J Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Tan Henriksen, F. A. Quintero, Charles R. Harris, Anne M. Archibald, António H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 00088//4159--09-0066 httpss:/scipy.. org/
Sinong Wang, Belinda. Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-Attention with Linear Complexity, 2020.
Michael L. Waskom. Seaborn: Statistical Data Visualization. Journal of Open Source Software, 6(60):3021, 2021. doi: 10.21105/foss.0002.. URL https://aoi.orgg/ 2111e//1s1sseee 03021
Bernard Lewis Welch. The Generalization of "Student's" Problem when Several Different Population Variances are Involved. Biometrika, 34(1/2):28-33 1947. ISSN 00063444. URL http:://ww. http://wwwwj.oorrrooo//o org/stable/ 2332510
31

---

Published in Transactions on Machine Learning Research (12/2024)
lan H. Witten, Radford M. Neal, and John G. Cleary. Arithmetic Coding for Data Compression. Commu- nicutions of The Acm, 30(6):520- June 1987. ISSN 0001-0782. doi: 10.1 10.1145/21470022144771. URL
https://doi.org/ 11111/01.111//177.2222222 214771
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Läu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macdulf Hughes, and Jelfrey Dean. Google's neural machine translation system: Bridging the gap between human and machine translation, 2016. URL https://arrae org/ httg/bb//16000 18194
Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel. ByT5: Towards Token-Free Future with Pre-trained Bytc-to-Byte Models. Transactions of the Association for Computational Linguistics, 10:291-306, 2022. doi: 10.1162/tad a 00461. URL https://aclanthology.oom
tac1-1.17
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiy Kumar. Are Transformers Universal Approximators of Sequence-to-Sequeece Functions? International Conference on Learning Representations, ICLR, 2020. URL http:///eppppeeeeeeeeeeerrrraaaa
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big Bird: Transformers for Longer Sequences. Advances in Neural Information Processing Systems, 33, 2020.
G. K. Zipf. The Esycho-Bioloyy of Language. Houghton Mifflin, 1935.
J. Ziv and A. Lempel. A Universal Algorithm for Sequential Data Compression. IEEE Transactions Information Theory, 23(3):337-343 1977. doi: 10.1109 10.1109/TTT.177.. TTT.//TTT..9977771111. URL https://courses.. duke. acuu/spring03/cps225550
ziv peppprrr/iw__eepel___. 11977_nnieerasee [tgr_umiverraalllgorttto algorithm.
A Zvonkin and L Levin. The Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms. Russian Mathematical Surveys, 25:83, 10 2007. doi: 10.107//IM11100//25556BBBBE1
URL htops::/www.. cs. bu. wdttffc//////dvii////// wtliddiii/LLeeepeeee pdf
A Additional Experiments
A.1 Iquo Windows with 24 bits
In Fig. 10 we saw that when trained on 64-bit Equal-Info windows, our model achieves the highest accuracy the third 8-bit token. All else being equal, expect to see higher accuracy later tokens, since the model should benefit from additional leftward context. Thus, the stark accuracy decrease from token #3 (>8%) to token #4 (<4%) likely indicates a difficulty in tracking the AC algorithm beyond 24 bits.
In this section, we explore training over 24-bit windows. First, we train a 403m M2 model over EquallnfoAC(0=244, v=256] compressed data, following the procedure from Section 3 We find this model achieves 1.394 bits/byte. This fits cleanly in the trend seen in Fig. 5 -hiie the model out- performs EquallnfoACllb=3 v-256] (which includes the problematic token #4), it still underperforms EqualInfoAC|b=16, ==256].
We also train model using EqualInfoAC(0-24 v-65k], and find it achieves 1.249 bits/byte, again fitting cleanly between the 16-bit and 32-bit settings. It is noteworthy that the model performs well despite the fact that the token bit-depth (16) is not a divisor of the window size (24). This results in M2 tokens that cross window boundaries.
EqualInfoAC b=24, 2=256] has a compression ratio of 3.15 and EqualInfoAC/6=24, v=65k] has compression ratio of 6.30.
32

---

Published in Transactions on Machine Learning Research (12/2024)
A.2 Resetting M1 Every Window is Beneficial
We saw in Section 6.1 that the initial characters within each equal-info window are especially costly to encode. This is due to our procedure of resetting the M1 model's context at every window boundary. In this section, we experiment with maintaining MI context over multiple windows. We expect this to improve the overall compression rate, but to negatively impact learnability, as window can no longer be decoded isolation.
As one extreme case, we consider never resetting M1. That is, we first use M1 assign probabilities to all tokens in the imput, and then use Equal-Info AC to compress the sequence into multiple fixed sized windows. In this setting we find that M2 does not learn beyond outputting uniform distribution over tokens 27
2
1.5
bits/byte
EquallnfoAC/b=16, v=256]
EquallnfoAC(b=11, v=65k]
Reset Every Window
1
Reset Every Other Window
Never Reset
10 Inference FLOPs/byte
10a
Figure 12: Resetting M1 with each Equal-Info window is beneficial. While reducing how often M1 is reset improves the compression ratio (see Table 9), bits/byte performance is much worse, as seen by these points being far above the scaling curves for our default settings.
the other extreme, we consider resetting M1 every other time an Equal-Info window is emitted. We train 403m parameter M2 models in each of these settings, and show the results Fig. 12 and Table g While reset- ting MI every other window does not yield as strong performance as our standard EqualInfAAC6=-6, v=65k] setting, it is notable that it is still learning at all. This suggests that M2 is able leverage context from compressed windows earlier in the sequence. While the improved compression ratio places this compres- sion scheme further to the right in Fig. 4 than EqualInfoAA//b=16, v=65k] or SentencePiece, the reduced performance means M2 must. be ex remely large to reach the Pareto frontier.
Exploring this compression scheme in a more traditional pre-training setting, where M2 is trained on trillions of tokens, would be interesting this model scems particularly under-fit. Similarly, exploring how many windows can be emitled before resetting M1 while remaining learnable for M2 would be of interest. as future work.
Consequently, models trained compressed data that used 8-bit 16-bit tokenization have the performance in the number of possible symbols in the vocabulary. This results in doubling
terms of bits/byte. 16-bit tokenization squares of the negative log likelihood loss when predicting the uniform distribution. This effectively cancels the doubling of the compression 16-bit bit. tokenization yields.
33

---

Published in Transactions on Machine Learning Research (12/2024)
Dataset
M1 Reset
Compression Ratio
bits/byte
EqualInfoAC(|=16, v=256]
every window
2.66
1.092
every other window never
3.40
1.748
5.33
1.501
EqualInfoAC//=16,, 0- 65kk
every window
5.31
1.015
every other window never
6.80
1.697
10.66
1.501
Table 9: Resetting M1 less often yields greater compression rate, but bits/byte performance degrades. We see that resetting M1 every other window results in more compressed, but still learnable data. However, M2 models trained on that data do not perform as well as when MI reset every Equal-Info window. As seen in Fig. 3 never resetting M1 scems have strong performance, but this is an artifact of its high compression rale; does not actually learn anything beyond uniform distribution.
A.3 Character Awareness and Spelling
Language models trained over subword tokens are not "character-awaree" that is, they lack direct access to the character-level makeup of their input text. As result, these models tend to perform poorly on tasks relating to spelling (Xue et al. 2022 Liu et al.) 2023). In this section, we explore whether our M2 models trained over neurally compressed text can offer an improvement in this regard.
We investigate spelling ability using an adapted version of the WikiSpell task (Liu et al.) 2023). When fed a word as input, the model is required to spell it by outputing the component characters separate tokens. We compare two of the 403m parameter models trained in Section 3 the EqualInfoAC[b=116 v=256) M2 model and the SentencePiece model. In each case, we fine-tune the model (which has been pre-trained for 200,000 steps on language modeling) on the WikiSpell task for 200 steps 5 epochs over the data. We continue the same lcarning rate schedule as pro-training.
For each model, we tokenize the WikiSpell input words with the same tokenizer used during pre-training. The choice of which token IDs to use for the output character sequence is less straightforward. For the M2 model, we use the ByT5 vocabulary (Xue et al., 2022), which overlaps in an arbitrary way with the 256 IDs used during pre-training. For the SentencePiece model, we consider two options. For more direct comparison, we map each output character to an arbitrary ID) shared with a non-character subword token in the vocabulary "SentencePiece (Shared)". As an alternative, we also consider mapping each output character to the ID of that character within the SentencePiece We expect this setting to perform better, as the model should already have some understanding of these characters and their relation larger subwords from pro-training.
"Sentenceeieeee (Characters).
Fig. 13 shows that a SentencePiece model leveraging its pre-trained character representations has the best. spelling performance held-out evaluation samples. It is also the first that reaches 100% training accuracy. The EqualInfoAC/(=166 v=256] model, which must share token meanings between the compressed input and the character output, outperforms a SentencePiece model with the same limitation on the evaluation set. Additionally, the model pre-trained over compressed text reaches 100% training accuracy before the analogous SentencePiece model. Interestingly, M2's inability to reach 100% accuracy suggests that the model may not actually be performing decompression internally while doing language modeling over compressed text
A.4 GZip Headers and Footers
GZip compressed documents have both a header-twe two bytes that identify the file type-and and footer two bytes representing the Adler-32 checksum (Deutsch & Gailly 1996) of the input. We train 25m M2 models versions of the dataset where the header/footer are removed, as well as versions where it kept. In
We note that only 0.18% of WikiSpell dev examples of 5,000) contain character that is during training. Thus, if the output character IDs chosen arbitrarily, a character-aware model should theory able to get nearly perfect performance.
34

---

Published in Transactions on Machine Learning Research (12/2024)
100
100
80
80
Accuracy
60
Accuracy
60
40
40
20
SentencePiece (Characters) SentencePiece (Shared)
SentencePiece (Characters) SentencePiece (Shared) @guallnfoAC(b-16, v=256]
EquallnfoAC(b=16, v=256]
0
25
75
100 Steps
125
150 175
200
25
100
125
150
175
200
Steps
(a) Spelling performance on held-out words
(b) Spelling performance on the training data
Figure 13: Reusing SentencePiece character representations yields the strongest. speller (and the fastest to train), but when forced to learn the output representations from scratch, pre-trained AqualInloAC||=16, v=256] model is better speller than SentencePiece based model.
Table 10 we see that including the header offers marginal improvement in bits/byte, at the cost of marginal decrease in compression ratio. These differences are not large enough to overcome GZip's poor performance compared to other compression methods. We opt to use versions GZip including the header /footer throughout.
Table 10: Removal of the GZip header and footer results in minimal performance differences.
Method
Compression Ratio
bits/byte
2.23
2.33
header /footer
2.24
2.35
[=6kk
4.46
2.91
Sreader/ooode footer
4.47
2.92
A.5 Avoiding End-of-Window Zeros
Our Equal-Info Windows algorithm described Section 3.3 involves compressing text until exceeding a specified number of bits (e.g., 16-bits per window), then backtracking one character, and padding with zero bits. As a character may encode to all zero bits, need to ensure there is ambiguity between padding bits and all-zero characters in order to achieve lossless compression. Our default solution, used in all experiments, is to greedily include the most characters possible in each window. Given the knowledge of greedy encoding, we can design a decoder that decodes windows unambiguously by using look-ahead, as detailed in Appendix D.5
An alternative resolution to the problem window-final all-zero characters simply avoid emitting these characters during compression instead, delaying their encoding until the next window. While this degrades the compression rate, it results in much simpler decoding algorithm. Specifically, with the knowledge that window includes the least number of characters that can result in the given bitstrcam, we can decode windows without any look-ahead.
To test whether this alternative scheme (Delay) improves learnability, we retrain EqualInfo M2 models following the procodure from Section 3. with the only difference being that generating M2's training data, we delay emission of window-final all-zero characters. Applying this "delayed" version of windowed compression, observe reduction in compression rate from 2.66 to 2.20.
35

---

Published in Transactions on Machine Learning Research (12/2024)
1.6
1.6
EqualintoAC(0=11.. v=256]
1.5
1.5
EqualinfoAC(0=16, v=266] (Delay)
1.4
EqualinfoAC/b=16, v-65k]
1.4
EqualinfoAC(==16, v=65k] (Delay)
1.3
bits/byte
bits/byte
1.2
1.2
1.1
1.1
1.0
1.0
10
10a
2
4
Inference FLOPs/byte
bytes/step
Comparison of our default "greedy" implementation of EqualInfoAC with a variant (Delay) where emission of window-final all-zero characters is delayed. For EqualInoAC[(=-66 v=256), the default. implementation performs better. For EqualInfoAC/616, v-65k], bits/byte performs improves slightly but at the cost of compression rate.
Figure 14:
Fig. 14 shows the results of training M2 models data compressed with each method. For EqualTnioAC(b- v=256), we find that our default implementation outperforms the delayed version along both axes. For EqualInfoAC/bb116, v=65k], the delayed implementation delivers slight improvement in terms of bits/byle. However, this gain is offset by the reduction in compression ratio, so the two performance curves largely overlap. Numerical values can found Table 17 Overall, our findings suggest that when trainod over data encoded with our default (greody) EqualInfo algorithm, M2 able distinguish trailing zeros that represent characters from those that represent padding. We opt use default implementation throughout, as it maximizes compression ratio.
B Other Compression Methods Considered
B.1 Equal-Text Windows
"Equal-Text" windows are a simpler alternative to Equal-Info windows. Rather than consuming a variable amount of text and outputting a fixed number bits, Equal-Text windows feed a fixed amount of text into the Arithmetic Coder, which compresses a variable number of bits.
We anticipate downside to Equal-Text windows is that it would be difficult for M2 decipher where window ends and another begins, this no longer aligns with fixed number of tokens, and the boundary may appear token-internally: We considered adding delimiter tokens between windows to overcome this difficulty. However, we expect this would degrade the compression rate too much, especially for the short AC compressed windows that we found most effective in Fig. 5
Further exploration of Equal-Text windows, especially see if the delimiters are actually required, would be interesting future work the Equal-Text Windows algorithm is much simpler than Equal-Info Windows.
B.2 Huffman Coding
We also considered using Huffman Coding Huffman 1952 as a baseline compression implementation. However, as most implementations use static probabilities for characters, the resulting compression rate would likely be too low to be competitive. With static Huffman Coding, there fixed mapping between bitstream subsequences and characters, which may improve learnability by M2 models. However, because the
36

---

Published in Transactions on Machine Learning Research (12/2024)
coding component assigns each character whole number of bits, the coding is less less optimal compared to Arithmetic Coding.
Huffiman Coding can be made adaptive by updating the induced codebook periodically, based on newer data. When considering bit-level compression, adaptive Huffman Coding performs similar to static Huffman Coding (Mahoney] 2013). However, when considering token-level compression, and the fact that the adaptive distribution will come from MI, not unigrams of the recent data, training M2 models on adaptive Huffman Coding could be interesting future work. As Huffman coding is part of the GZip algorithm, opted not to explore Huffman Coding on its own.
B.3 Asymmetric Numeral Systems
Another compression algorithm we considered was Asymmetric Numeral Systems (ANS) Duda, 2014 ANS has strong coding performance and is amenable to adaptive probabilities. The internal state is only a single natural number, which may be casier for an LLM to track than the two real numbers used in Arithmetic Coding (AC). However, unlike AC, the encoding and decoding algorithm are stack-like, where the encoder runs left-to-right and the decoder runs right-to-left. We thought this would make streaming inference, where single M2 token is generated and then decoded by M1 before another M2 token is generates, difficult. Thus we opted to explore AC over ANS in this work. However, the simpler state is appealing and using ANS for compression would be of interest as future work.
C Instability in the Initial Token of Multi-Token Windows
There are cases where the token -> text mapping for the initial token in a multi-token EqualInfoAC window can be unstable. When a character's bitstream crosses the token boundary the purple characters in Fig. g only some prefix of the bitstream contributes to the value of the initial token. It is possible that another character may produce different bitstream with shared prefix. If the token boundary comes before the difference in the bitstreams, then the two tokens will have the same value but represent different text. When this occurs the text. prefix will remain stable, i.e., any characters whose bitstreams are entirely contained within the initial token will match, but the final character may differ. Thus the notion of mapping a compressed token to exact characters not well defined, as there are often cases there a character is spread across two tokens. Note, this only occurs at loken boundaries; EqualInfoAC[0-16, v=65k] is stable as no characters cross windows. This is most likely a reason that EqualInfoAC[b=166 v=65k] outperforms EqualInfoAC|b= v=256] in our byte-controlled ablations (Section 5.3 Therefore, we consider EqualInfoAC stable enough to enable learnability by M2.
Interestingly, Külekei (201)) point out this same issue, where a fixed size view of a variable length stream can cause false equivalencies when prefixes match. Similar to our findings, they find the models do have some limited ability to deal with these situations.
Details for Reproducibility
D.1 Variance
Sampling from the validation set was scoded. For given sced, the same batches are sampled at cach evaluation step within a training run. Similarly, when models of different size are trained on the same compressed data, the same evaluation batches are sampled, allowing for fair comparison. As the Bytes and SentencoPiece basclines use deterministic datascts, the validation seed is not used. Instoad the "start_ step" is incremented by 20 to get a new sample of 20 batches.
Model initialization and the order of the training data is controlled by the training seed. This seed was also changed during variance testing. During training, the dataset is checkpointed and therefore each example is seen exactly once. The exact order of the training data determined by the seed. As the Bytes and SentencePiece baselines use deterministic datasets, the training order is fixed.
37

---

Published in Transactions on Machine Learning Research (12/2024)
Table 11: Variance in performance low. Even with maximum changes between runs different evaluation samples, different training orders, and different parameter initialization is very little variance final performance, Statisties were calculated over 5 different 25m parameter training runs for each method.
Method
Bytes
1.2899 + 0.0020
SentencePiece
1.1171 = 0.0006
AC[u=256]
1.4573 = 0.0001
StaticAC[c=256)
4.6936 + 0.0005
EquallnfoAC[b=16, e-256]
1.4724 = 0.0044
EqualInfoAC[11=32, bb=32, v=256
2.0457 + 0.0058
EqualInfoAC v=256]
1.8494 = 0.0052
EqualInfoAC
b=128, b=
2=256]
1.7121 0.0003
GZip[v-256]
2.3374 + 0.0061
5 models with 25m parameters were trained with different seeds (both validation and training) for each compression method and the two baselines. The mean and standard deviation can be found in Table [I The variance is so low that we only report single values for most other experimental settings, such as larger models.
Training models of size 403m and 2b over data compressed with EquallnffAA(/b664 v=256] and AquulInfoAC(0=128,, v=256], as well as 2b model with RqualTnfoAC(/=122,, v=65k), occasionally diverged, collapsing a simple model that just output the uniform distribution. The numbers for these settings exclude these divergent runs. This resulted in 7 re-runs in the most problematic case.
D.2 The Amount of Raw Text Bytes Seen by M2
Table 12 shows the number of tokens and bytes found in the training datasct for each compression method. During the data generation process, sequences of 10,240 generated by concatenating 128 C4 byte-tokenized documents together- are compressed. Some of these sequences, namely the final sequence created from the tail of the concatenated docs, are too short to be compressed to the target length of 512. Thus, the exact number of tokens in the dataset can vary slightly. With no padding, each dataset would have been trained on 4,0,000000000 tokens, we see all settings are close to this value, with the maximum deviation being AgguallnfoC[lb1111 same source sequences, thus the underlying byte sequences compressed by weaker methods are prefixes of the underlying sequences compressed by stronger methods.
v=65k] with 1.06% fewer tokens. All compression datasets created from the
D.3 Scaling Curves with Scaled Training Data
When scaling models, Hoffmann et al. (2022) argue that training data should be scaled linearly with model size. As such, when comparing scttings with constant training FLOPs, large part of the FLOPs budget should be used by adding more training data. We apply this technique to compensate for our 2b models being
by plotting the scaling curves in Fig, 15 where the smaller models are trained with less data, proportional to their size. Models with 25m parameters only train for 3k steps, 113m for 1 11k, 403m for 40k, and 2b for 200k steps. Otherwise, the settings match those in Fig. 3 Numerical values used in the graph can be found in Table 13
Scaling the training data adjusts the absolute slopes of the lines for all models that learn. Models that do not learn still only predict uniform distribution. The trends between settings are unchanged. Thus we opt to plot the versions where training data is held constant across model sizes.
38

---

Published in Transactions on Machine Learning Research (12/2024)
Table 12: Compression ratios (bytes tokens) achieved by various methods. For EqualInfoAC, the compression ratio increases with increased window size. Small differences in the number of non non-padding tokens are due noise in the data generation process some randomly selected documents are too short be compressed the target length of 512.
Compression Ratio
Method
Tokens
Bytes
Bytes
1.0
26,188,185,600
26,188,185,600
SentencePiece
4.28
26,112,163,88
111,728,726,63
AC[c=256]
5.49
26,083,328,00
143,197,470,722
StaticAC|c=256]
1.73
26,175,078,40
45,282,885,633
GZip[u=256]
2.23
26,175,209
24,370,424,,83
FqualTnfoAA[|i=16,, ==256
2.66
26,154,106,88)
69,569,924 ,214,001
EquallnnoAA(|b==32 v=256
3.49
26,109,542,400
21,122,,02,,77
EqualInfoA(/b=66,,, v=256
4.16
06,110,853,11
108,621,144 12,,,,,,,,,99 ,799
100 v=256)
4.61
26,078 26,078,085,12 120
120,219,97 972,403
AC[x=65k]
10.98
75.952,256,00
284,955, 770,8,77888
claticAC|==65k]
3.46
13,133,135,360
90,420, 90,420,648,346 648,346
GZip[c=65k]
4.47
26,122,649,600
116,768, 277,6,,,,3,12
AgualllnfoAA|b=166 v=
5.31
26,091,192,320
138,544,231,22
EqualInfoAC/b=332, b- v=65k
6.97
26,049,249,288
181,563,267,48
FqualInfoAC(1=<44, v-6k
8.33
66,000,6844,80
216,619,024,384
CqqullinfoAC(==2220 v=65k]
9.22
25,936,527,360
139,124,,82,,59
D.4 Evaluation Details
In our experiments, different settings have different vocabulary size, tokenization, and has a different amount of underlying text due to variations in compression rate. Thus, they are not directly comparable using "per- token" versions metrics like the cross-entropy, negative log likelihood loss, or perplexity. To address this, we convert our token-level negative log likelihood loss, E, to byte-level negative log likelihood loss by dividing the loss by that compression method's specific token-level compression rate, bayte (/(L.r LoT) E(LoT) LeT). Note that character when working with UTF-8 Unicode.
"per byte" metrics over "per character" metrics there is ambiguity to what counts
As is common in evaluation of work related to compression, instead of the negative log likelihood loss byyte (in the unit of "nats") per byte, we use bits/byte. This would require using log base two instcad of the natural log during the negative log likelihood calculation, but this conversion can be done after the fact, bits/byte = logz(e (ooo)) = fbyte/ In)... Note that this results the same conversion used in Gao et al. 2020 bits/bye bit//yte- /byte/ In(2) (LoT/ Ler)e/ In(2), when the input tokens represent bytes.
As one of the main advantages of an M2 model that processes compressed text is that it needs to be run over fewer tokens, we also compare models based on the amount of FLOPs required during inference. Different compression methods result in different sequence lengths for the M2 model to process. Therefore, we need to standardize our FLOPs measurement to the byte-level so that it is comparable across methods, We start with FT.OPsttoeen FT.OPs/token-approoiii et al. (2020) approximated by 2 num params (not including embedding parameters) following Kaplan divide it by that method's token-level compression rate to get the FLOPs/byter just like the bits/byte byte conversion. For methods that require running an M1 model over each byte, the FLOPs/byt cost of the M1 model is added. Note, while there is computational cost to running GZip over the input text, we ignore it as it is insubstantial compared to the cost of running model inference.
Evaluation of language models is often done by running the model on the entire validation set, moving the sliding window formed by the model's context window by a single token at each step. This yields stronger models by providing the most context possible when making predictions for a token. As we care about relative performances between methods, opposed to absolute performance, we opt evaluate the model on a sample of the C4 validation set. During evaluation, the model is over 20 batches, resulting in predictions
39

---

Published in Transactions on Machine Learning Research (12/2024)
10
Bytes
SentencePiece
Arthmetticcolingl==251
Artthmetticcoddngll==533
StaticAC[v=256]
StaticAC[v=65k]
EqualinfoAC|b=16,,.aa v=256]
EqualinfoACC/b=16, v=
GZip[v=256]
GZip[v=65k]
5
bits/byte
1
107
10 Inference FLOPs/byte
109
Figure 15: Training language models over compressed text while scaling training data with model size results in steeper slopes. When scaling model size, it has been found that the training data should be scaled proportionally (Hoffmann et al. 2022). We apply this scaling technique by plotting values for smaller models at earlier training steps. The trends are similar to Fig, 3 even down to things like where the EqualInfoAC(b=16, v=256] line crosses the Bytes bascline (between the 25m and 113m parameter models).
for 2,621,440 tokens. These tokens represent different amounts text based on the compression method, thus it would have been impossible to run evaluation on the same bytes for methods. We trained five 25m parameter models with different seeds and found that the final performance very stable. The largest standard deviation was 0.0061. Thus, the variance introduced from sampling the validation set negligible. See Appendix D.I for more information.
D.5 End of Window and End Input Sequence Handling
In the implementation of EqualIinoAA((l:W/ each output window must end up being W bits. Therefore, when the compression of an additional character would result in a bitstream of more than W bits, padding of the compressed bitstream without that additional character must be done.
In cases where the final character in the window only adds seros to the bitstream, it is unclear at first glance if that final character was included in the window, or if it was omitted and the trailing zeros are all padding. However, the compression scheme is still lossless if we are consistent in our encoding. By always including the most input characters possible in each window, we know that, during decoding, the addition of a final character (which is compressed to all zeros) still results in the same compressed bitstream, then that final character is part of that window. The decoding algorithm also knows when stop adding characters input-when the addition of new character would generate more than W bits when compressed
29r only exception is the end of the sequence, when the amount padding dictated by running of input characters the window. This can be solved by including end-of-imput, symbol.
instead running
40

---

Published in Transactions on Machine Learning Research (12/2024)
Table 13: Numerical values from Fig. Values for the uniform distribution and FLOPs/byte values can found in Table 15
Dataset
Size
Step
bits/byte
Byles
25m
3k
1.62
113m
11k
1.36
403m
40k
1.18
2b
200k
1.03
Sentence
25m
3k
1.35
113m
11k
1.15
403m
40k
1.00
200k
0.87
AC[u=256]
25m
3k
1.46
1 113m
11k
1.46
403m
40k
1.46
2b
200k
1.46
AC[u=65k]
25m
3k
1.46
113m
11k
1.46
403m
40k
1.46
200k
1.46
StaticAC[o=256]
25m
3k
4.62
113m
11k
4.62
403m
40k
4.62
2b
200k
4.62
StaticAC|u=65kk
25m
3k
4.62
113m
11k
4.62
403m
40k
4.61
2b
200k
4.61
EqualInfoAC(b=16,, 2=256]
25m
3k
1.86
113m
11k
1.50
403m
40k
1.21
2b
200k
0.99
EqualInfoAC(--16, v-65k]
25m
3k
1.62
113m
11k
1.31
403m
40k
1.10
2b
200k
0.94
GZip[e=250
25m
3k
2.95
113m
11k
2.48
403m
40k
1.97
2b
200k
1.56
GZip[u=65k]
25m
3k
3.30
113m
11k
3.08
403m
40k
2.72
2b
200k
2.26
This kind of padding is present in many Arithmetic Coding implementations and is generally solved by either giving the AC decoder the original input sequence length and the compressed message, by the AC decoder using a special termination character. These fixes are hard to apply in our setting. Passing the number of tokens present in a window to M2 would be possible during training, but it would make inference much more complex (requiring a solution such as M2 generating "fertility" scores that specify how many characters the generated tokens represent (Brown al., 1993)) In order include an end-of-input symbol for the AC decoder, the M1 model must be able assign reasonable probabilities that symbol. Therefore would need to appear at the end of each training example, hindering M1's ability to be applied to longer sequences.
41

---

Published in Transactions on Machine Learning Research (12/2024)
As such, achieve lossless compression within each window by allowing the AC decoder to be run multiple times, incrementing the sequence length until we find the sequence that, when compressed, no longer matches the compressed output and backtracking. As we do not include an AC decoder end-of-input symbol, when we reach the end of the input, there is some ambiguity in the number characters that are included in that window. However, as we compress extremely long sequences, over 10,000 characters, the final window a, trimmed, M2 example rarely correlates to the final input characters. Thus most sequences (99.4%) are decompressable using the approach above. In our validation data, just 0.0011% of windows represent the end of an imput sequence. Additionally, the standard deviations of the loss across validation tokens is similar for models trained over compressed input and models trained directly SentencePiece. Thus we believe that these ambiguous tokens do not effect our results.
D.6
Entropy Estimation
1e-5
1e-5
1.00
0.75
0.75
Nomaalized Entropy
0.50
Normalized Entropy
0.50
0.25
0.00
0.00
-0.25
RNG
00.55
Arithmeticcoddnn(v=255))
0.50
StaticAC[v=256]
-050
GZip[v=256]
-0.75
-0.75
EqualinfoAC(b=16]
-1.00
EqualInfoAC(b=64)
-1.00
10
14
8
12
16
Bit N-grams
N-Bit Tokens
(a) bit n-grams counting all overlapping occurrences
(b) n-bit tokens following our M2 tokenization
The amount of noise in the entropy estimate grows the length of bit segments grow. Larger segmentations of the bitstream result in larger vocabularies and therefore require larger sample sizes for accurate entropy estimates. For each setting, we plot the 5%, 50,, and 95% percentile intervals for the entropy, normalized by the average entropy across partitions. We see that the noise grows with n and that settings like EqualInfoAC|==16] are noisier than AC, despite this not being apparent in Fig. 11
Figure 16:
To account for noise the entropy estimation, we partition the data into 100 disjoint samples. This results in each partition being a sample of -2 billion symbols for n-grams and -130 million for tokens. We then calculate the entropy for each partition and the KL divergence between the entropy of the 0.5, 0.50, and 0.95 quantile points and uniform distribution. These quantiles then plotted Fig. T1 to illustrate sampling noise-909 of sampled entropies fall within these bounds. The log scaling of Fig. 11 hides some of the noise trends, namely that the noise grows with and that settings like GZip and EqualInfoAC are noisier than AC and RNG. These trends are seen in Fig. 16 where the entropy has been normalized based on the mean entropy calculated across the partitions.
The maximum likelihood, or plug-in, estimator of entropy, A - E.ex p(x) log, p(x), ; is negatively biased in fact, all entropy estimators are biased (Paninski 2003). The Miller-Madia Madow estimator attempts to correct for this bias by adding the approximate bias, caused by sampling, the plug-in estimator The Miller-Madow estimator is given by ÅL A 1 In this case, m is the size of the sample used to estimate entropy and [ is the estimated vocabulary size. In some applications, the vocabulary may need to be estimated for
Thre other methods for entropy bias correction such those used in DeDoo et al. 2013 based bootstrapping Efron 1979 however, with the size the C4 training data, the required resampling was not possible. Thus, we Miller-Madow this work.
42

---

Published in Transactions on Machine Learning Research (12/2024)
10-1
RNG
Artthmeticcodingll=255)
10-1
kLfobserved [| uniform)
10
StaticA([v=256]
KL(observed uniform)
GZip[v=256]
10
EqualinfoAC(==16
10-5
EqualinfoAC(b=64]
10-5
-0
10
10-9
10
6
12
14
2
10
12
14
16
Bit N-grams
N-Bit Tokens
(a) N-Grams
(b) Tokens
Figure 17: Bias corrected KL divergence between the observed and uniform distributions for different segmentations of the bitstream. This plot similar to Fig. [1 however, the KT. divergence calculations use the entropy of the observed distribution after applying the Miller-Madow bias correction. After applying bias correction, we see that the expected 0 KL divergence for the RNG bascline is now within the 90th percentile bounds. However, this can results in an, incorrect, negative KL divergence which is removed from the graph. Thus the RNG 50th percentile shown as a scatter plot rather than a broken line. In this setting it is clear that the 50th percentile for AC[u=65k|s above the 50th percentile RNG, however, hard to disentangle the two as their 5th percentile lines are similar.
example, to account for new words that are added to languages- but in this case our vocabulary size is always 2n where n is the size of the current segmentation.
When we plot the KL divergence between the Miller-Madow estimated entropy and the uniform distribution, that the percentile interval for the RNG baseline includes the KL divergence expect given the data was generated from random and independent bits. As bias correction is approximate, it is possible that, for given sample, the correction will result in entropy greater than the maximum entropy possible for given vocabulary size. Given that KL divergence between a distribution P and the uniform distribution U simplifics to the entropy U minus the entropy of P, KL(P[[U) = H(U] - [[[P] = log, V -fpp), this results a negalive KT. divergence, which is not allowed. These points get removed from the graph during log scaling and the resulting 50% percentile line for RNG data looks strange. Therefore, we only plot points with positive KL divergence in Fig. [7 The Miller-Madow estimation of entropy makes it clear that the 0.5 entropy quantile for AC compressed data is much higher than the 50% percentile for RNG data. Additionally, for > 2, the AC entropy is statistically significantly less than the RNG entropy; however, differences in the mean entropy only start to appear after --8 decimal places. This slight difference in mean, coupled with the fact that the 5% percentiles are similar, means we cannot. confidently assert the model will be able to easily distinguish the AC compressed data from random data. Given that we care about the differences between the entropy of data compressod with different methods-whide invariant bias-an the strange plots when values less than 0, we opt to plot the plug-in estimator in Fig. I instead of the Miller-Madow estimator.
D.7 Analysis Implementation
Matplolib Hunter 2007) and Seaborn (Waskom 2021 were used to make all the included graphs.
Statistical significance tests were done using Welch's t-test (Welch 1947) using the function scipy. stats tetetttttttett lecttiind_ff_ hnd__from_sste stats from SciPy (Virtanen al. 2020). We used p < 0.05 as the statistical significance threshold.
43

---

Published in Transactions on Machine Learning Research (12/2024)
D.8 Window Text Patterns and Token Positions
We lokenize 20 documents of length 1,024 with EqualInfoAC((=16, v=256] and find that all 256 possible token values occur multiple times, both as the first and as the second token within the window. When tokenized with EquallnffAC//=16, v=65k], 34.5% attested tokens appear more than once. Table 14 shows all the window text for repeated tokens.
Table 14: The deduplicated window text from all instances of tokens that appear multiple times when we tokenized 20 documents of longth 1,024 (20,480 compressed tokens) with EqualInfoAC|b-16, v=256].
Window Position
Token
Window Text
185
or // or
[rr ac] [or
[or all
[or cr)
or / or f
or h) [or se] [or, t
or hi or 1]
[or ma
[or pr
[or or s|
orr su or for to
oor
(or wha / or
or yo ord ord a] [oddrr]
[or-]
[or
[raa| [orc]
orce
[ore
a] [or e] [oe ev]
[ore
ore 1
2
4)
of F] records |/ Lo]
[A]t] [OI] |ase
} [at y]
[cian] [cri] [d. I] [rr]] [h de
[hen s) [ides] / [n ne
[oft] [om i] [onte] [opp]
[pir]
[rev] / [reve] [ may
[tion a)
y do]
ly t]
151
1
[e] [l
[e t|
le.
[ea
[ec] / [1ed] / [led
led t| [1g
[ege
[1h
1em / [eme] [1ems] / [1en]
[er] [es] / [less]
[1tt] / [ett [level] [lew 1/ [1ey] / [1f
2
all nut / this un [. w) [Ni (as
ceed
[choos] le Mi] / [e-1i] [etti]
[imag] [ion / a
ne
Ing up] [niversi] [пpo] [nt pr)
[pi] [rvices] / [s T [s your)
[s] [s0 (stag) [thou]
[thoug] [ust] [ust
D.9 Numerical Values
Table includes the specific values used create Fig. 3
Similarly, Table 16 includes the values used
create Fig. 5 The numerical values from Fig. [ can be found across Table 15 and Table [6] Table 17 includes
the numerical values from Fig. [4
44

---

Published in Transactions on Machine Learning Research (12/2024)
Table 15: Numerical values from Fig. Methods that use 16-bit tokens (v=65k) have the same uniform
distribution performance the 8-bit version (u=265). Note: One thousand million is used over one billion make comparison of PLOPs/byte values easier.
Dataset
Size
bits/byte
FLOPs/byte
Bytes
25m
1.29
50.00M
113m
1.16
226.00M
403m
1.08
806.00M
2b
1.03
4,000.00M
uniform
8.00
Sentence Piece
25m
1.12
11.69M
113m
1.01
52.82M
403m
0.94
188.37M
2b
0.87
934.84M
uniform
3.47
AC|u=256]
25m
1.46
15.11M
113m
1.46
47.17M
403m
1.46
152.81M
2b
1.46
734.60M
uniform
1.46
AC|u=65k]
25m
1.46
10.55M
113m
1.46
26.58M
403m
1.46
79.41M
2b
1.46
370.30M
StaticAC[u=256)
25m
4.61
28.90M
113m
4.61
130.64M
403m
4.61
165.90M
2b
4.61
2,310.00M
uniform
4.62
StaticAC[o=65kkk
25m
4.60
14.45M
113m
4.60
65.32M
403m
4.62
232.95M
2b
4.62
1,160.00M
EquallnfoAC6-=16, v=256]
25m
1.47
24.80M
113m
1.23
90.96M
403m
1.09
309.01M
2b
0.99
1,510.00M
uniform
3.01
EqualInfoAA/b=11e 6-65k]
25m
1.25
15.42M
113m
1.12
48.56M
403m
1.02
157.79M
2b
0.94
759.30M
GZip [26
25m
2.34
22.42M
113m
1.93
101.35M
403m
1.69
361.43M
2b
1.56
1,790.00M
uniform
3.59
GZip 656k
25m
2.92
11.19M
113m
2.69
50.56M
403m
2.48
180.31M
2b
2.26
894.85M
45

---

Published in Transactions on Machine Learning Research (12/2024)
Table 16; Numerical values from Fig. 5 Values for EquallnfoAC(l=1,, v=256] and EquallnfoAC/==6,, v=65k] can be found in Table 15 Note, EqualInfoAC[|b-22,, v=256] showed slight improvements beyond the significant digits shown here as the model scales.
Dataset
Size
bits /byte FLOPs/byte
13ua v=256]
25m
2.05
20.33M
113m
1.94
70.76M
403m
1.83
236.95M
2b
1.65
1,150.00M
Aqua,,nfoACl--32, v-65k]
25m
1.95
13.17M
1 113m
1.85
38.42M
403m
1.74
121.64M
2b
1.63
579.89M
EqualInfoA((/-64, v-266
25m
1.85
18.02M
1 113m
1.82
60.33M
403m
1.80
199.75M
2b
1.79
967.5 .44
EqualInfoAC(/=664, v=
25m
1.82
12.00M
113m
1.80
33.13M
403m
1.79
102.76M
2b
1.76
486.19M
EqualInfoAAC(--188, v=256
25m
1.71
16.85M
113m
1.71
55.02M
403m
1.71
180.84M
2b
1.71
873.68M
EqualInfoAC/i=1228, v-65k]
25m
1.70
11.42M
113m
1.69
30.51M
403m
1.68
93.42M
2b
1.67
439.84M
Table 17: Numerical values from Fig. comparing our standard implementation of EqualInfoAC versus implementation where window-fing final all-zero symbols are delayed.
Compression Ratio
Dataset
Size
FLOPs/bye
FqualInfoAC/0=16, v=256]
2.66
25m
1.47
24. 24.80M
113m
1.23
90.96M
403m
1.09
309.01M
2b
0.99
1,510.001
EqualInfoAClb=16, v-256] Delay
2.20
25m
1.50
78.73M
113m
1.25
108. 73M.
403m
1.11
372.36M
2b
1.00
1,820.00X
EqualInfoAClb-16, v-65k]
5.31
25m
1.25
15.42M
113m
1.12
48.56M
403m
1.02
157.79M
2b
0.94
789.30M
EqualInfoAC(=116, 65k5 Delay
4.40
25m
1.23
17.36M
113m
1.11
57.36M
403m
1.01
190.18M
2b
0.93
915.09M
46


Reviews:
[{"review_id": "1HyubBTOTB", "reviewer": "Reviewer_BCNv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. **Innovative Approach**: The paper introduces a novel use of neural compression - addressing efficiency in training and inference for LLMs. This integration highlights a unique direction for optimizing LLM performance.\n2. **Efficiency Gains**: By compressing text into shorter sequences, the proposed method shows significant improvements in inference speed and reduces computational costs, which is crucial for deploying LLMs in resource-constrained environments.\n3. **Equal-Info AC**: The introduction of Equal-Info AC is a good contribution that makes neural compression learnable. This technique ensures manageable bit-length segments and simplifies decoding, enhancing the model's ability to learn from compressed data.\n4. **Interesting Results**: Several interesting questions were asked and answered ranging from \"Can LLMs learn effectively from text compressed using Arithmetic Coding?\" to \"Do scaling laws persist?\"\n\n### Weaknesses\n\n1. **Perplexity Trade-offs**: While the method improves efficiency, the performance in terms of perplexity still lags behind traditional subword-based models. \n2. **Learnability Challenges**: The paper proposes a hypothesis which I understood to be: *\"The near-optimal compression of AC means that most predictable information has been removed, making it challenging for M2 to learn anything useful.\"* If this is true, this is a very crucial point and needs to be contextualized with prior works like [A]. If my understanding is incorrect, then the hypothesis must be made clearer in the writeup.\n3. **Tokenization Weaknesses**: The tokens as produced by EqualInfoAC are less semantic than SentencePiece. This also runs somewhat counter to traditional thinking of how attention operates in these sequences. Also, the tokenization produced by EqualInfoAC seems to be less stable. It would have been good to compare against tokenizations produced by standard AC and also stability of standard AC. There might be connections here to learnability, but it does not quite come out clearly from the text. Also, if possible, it would be contextualize the result with the prior works like [B]\n\n[A] Are Transformers universal approximators of sequence-to-sequence functions?, ICLR 2020  \n[B] Getting the most out of your tokenizer for pre-training and domain adaptation, ICML 2024", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces method to train Large Language Models (LLMs) on highly compressed text using neural compression techniques, aiming to improve efficiency by reducing sequence lengths and computational cost. Key contributions include:\n\n1. **Neural Compression Methods**: The paper explores using **Arithmetic Coding** in conjunction with a neural language model. This neural model assigns dynamic, context-aware probabilities to each byte of text, allowing Arithmetic Coding to achieve higher compression rates. The integration of neural networks transforms the compression into an adaptive process, hence the term \"neural compression.\" The authors analyze the challenges, such as difficulty in learning and numerical stability issues, that arise from this approach.\n2. **Equal-Info AC**: A novel approach that segments text into fixed-length bit blocks, improving learnability by resetting the AC compression algorithm and model context at each window.\n3. **Efficiency Gains**: Models trained on Equal-Info AC achieve shorter sequences, enhancing inference speed while underperforming in perplexity compared to traditional subword tokenizers.\n4. **Interesting Result**: Extensive ablation studies show that neural compression methods, while efficient, still require improvements in stability and semantic alignment.\n5. **Possible Extensions**: The paper suggests enhancements to compression-based tokenizers and calls for exploring alternative coding methods to boost learnability and performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The hypothesis regarding the impact of near-optimal compression by Arithmetic Coding (AC) on learnability is a pivotal part of the work. If the hypothesis is that AC removes too much predictable information, making M2's learning difficult, this needs to be clearly and explicitly stated. Additionally, contextualize this point with prior works like [A] which claim that transformers are universal approximators of sequence-to-sequence functions. If this hypothesis is incorrect or incomplete, the authors should provide a clearer explanation of why M2 struggles with learning from AC-compressed data.\n2. Provide additional analysis of the semantic and stability weaknesses of tokens produced by EqualInfoAC by compare these directly with standard Arithmetic Coding tokenizations. It would be good to explore how differences seen here might relate to learnability. Also, if possible, can it be contextualized with other works like [B].\n\n[A] Are Transformers universal approximators of sequence-to-sequence functions?, ICLR 2020  \n[B] Getting the most out of your tokenizer for pre-training and domain adaptation, ICML 2024", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ta1KekNHJm", "reviewer": "Reviewer_Kqn7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1) Address an important and interesting problem of compression & language modelling. I expect future works would extend on this paper for implementation on low resource devices.\n2) Develop a technique to address the challenge of learning on bit stream. \n3) Results are benchmarked and studied carefullly.\n\nWeakness:\n1) The paper can be a bit more concrete problem formulation. The components between input raw text and bit-stream is not formulated mathematically for future work development.\n\n2) (Suggestion Only) Some toy sequences, such as Markov chain [1,2], can perhaps help the reader understand more about the importance of context window N to the performance of the LLMs. \n\n[1] Rajaraman, N., Jiao, J. and Ramchandran, K., 2024. Toward a Theory of Tokenization in LLMs. arXiv preprint arXiv:2404.08335.\n\n[2] Makkuva, A.V., Bondaschi, M., Girish, A., Nagle, A., Jaggi, M., Kim, H. and Gastpar, M., 2024. Attention with markov: A framework for principled analysis of transformers via markov chains. arXiv preprint arXiv:2402.04161.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary: This is a good paper on the intersection between two topics: language modelling and compression. The motivation is that modern LLMs often train with tokenization to deal with the long sequence context/generation. From this point, the authors take a step further and combine the training with neural compression technique, hoping to achieve further compression rate and better generalization. While on the surface this idea looks simple, in fact it is very tricky since the the bit stream produced from the neural compressor can make it difficult for the language model to learn the prediction. As far as I understand, for example, using a naive arithmetic coding, a character 'a' can be mapped into two different bit-level representation, depends on the previous context and thus make it difficult for LLM to learn the representation. Furthermore, the bitstream also appears very randomly, as expected from the AC point of view, which makes the learning challenging. \n\nThe paper addressed this problem well by introducing a “Equal-Info Windows” method, i.e. divides the bitstream into series of N bits window, to address this problem and show competitive results compared to the current dictionary-based tokenization methods. While this may be a suboptimal as each window is compressed independently, I think this is a good direction towards this problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) This is a very good paper. I suggest the author to put the mathematical formulation/setup more concretely in the paper for future work development (both theory and practice).", "broader_impact_concerns": "This paper provides a good direction for sequence compression and modelling. No ethical concerns from my side.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7UExo7qi2k", "reviewer": "Reviewer_nNhF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "###  Strengths\n- The problem is well-formulated, interesting and timely. \n- The authors conduct extensive empirical experimentations and ablations supporting their findings throughout the paper. \n- The authors provide detailed justification for various possible corner cases in their experimental setup, such as effect of over-flowing or under-flowing during the finite-window truncation in their proposed scheme. They also try to explain differences with the related work when the findings are contradictory.\n- Details for reproducing the experiments are clearly provided.\n- For ML/LLM readers, the compression schemes are sufficiently introduced in the paper.\n- Results are presented clearly with experiments presented in a section and summarized in the title heading of the corresponding section.\n\n###  Weaknesses\n Summary of weaknesses is provided, for details please look at requested changes.\n- The paper is unclear in certain sections and the writing and/or presentation can be improved.\n- The conclusion around reduced latency might be true, but is not well supported via empirical findings like the rest of the results.\n- I wonder if authors could release the open-source code to their project, especially given the time spent in meticulously describing each experiment in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### Main exploration idea\nThe authors explore the effects of modifying tokenization in LLM training by replacing standard methods with alternative compression techniques. This problem is particularly intriguing due to the potential benefits of higher compression, such as increased context length during training and inference, along with reduced latency. However, the challenge is amplified by the authors’ unique, practically motivated setup, where the probability model used to compress the raw text is not shared with the downstream LLM, which remains unchanged. As a result, the LLM must either learn to decode the compressed input or directly extract meaningful patterns from it. Given that compression reduces statistical correlations, this makes the task of learning from the compressed tokens even more difficult.\n\n###  Experimental Setup summary\nIn particular, authors extensively study arithmetic coding (`AC`) for compressing the text. The experimental setup is to use a “weak” LLM (context-aware transformer, `M1`) as the probability model for arithmetic compression, followed by training another “stronger” LLM (another transformer, `M2`) on the tokenized compressed bytes. The performance and efficiency of the trained M2 model is compared across M1 compressors of various sizes as well as GZIP-compressed bitstream. The approach is also compared to standard byte-level tokenizer and SentencePiece (sub-word level tokenizer). The authors study three different metrics: \n\n- Perplexity metrics as a result of training M2 over tokens extracted from compressed text, measured in log-likelihood loss scaled for input bytes instead of tokens and converted to bits instead of nats, referred to as `bits/bytes`. This metric controls for the learning performance of the downstream LLM over compressed data.\n- Computation required to perform inference over a given length of raw text, referred to as `FLOPs/byte`. This metric provides insights into the computational efficiency gains of compressing the text: benefits corresponding to being able to process higher context length.\n- Number of bytes per text processed in one auto-regressive step, referred to as `bytes/step`. This metric mainly corresponds to the fact that higher compression implies fewer autoregressive steps during model decoding and therefore accounts for possible benefits for latency during serving. \n\n###  Main findings\nThe main findings of the paper can be summarized as:\n\n1. There is a tradeoff in the level of compression one might desire for optimal efficiency gains in terms of FLOPs/byte given a model performance in terms of bits/bytes. \n    1. Authors observe that naively using Arithmetic coding or gzip (DEFLATE) does not lead to this optimal tradeoff.\n    2. SentencePiece (sub-word) level tokenizers are optimal over the range of experimentation carried out by authors.\n    3. Suitable modified Arithmetic Coding, referred to as `EqualInfoAC` can beat byte-level tokenizers.\n2. Context-aware compression introduces two main challenges for the downstream M2 LLM for decoding the tokens obtained from compressed bit-stream — (i) Need to model the probability distributions as these are not shared from M1 to M2, and (ii) Need to model the context as now the same words/text might result in very different byte-stream given the past context, and hence the M2 model has to deal with the variability in input tokens during the learning phase. The authors show throw various ablations and experiments that modeling this variable context-generated tokens is extremely challenging for LLMs.\n3. Authors suggest a simple modified AC scheme, called `EqualInfoAC` which truncates AC-coded bitstream to a fixed bit-width, creating independently decompressible bit-streams with finite context size. This scheme reduces the compression rate, however, it enables the learning of these tokens via the downstream M2 model. \n4. Authors provide interesting analysis probing further what contributes vs what hurts the learnability of the downstream model, which seem to suggest challenges with increasing context length during compression as well as variability in the tokens generated because of variable context.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "###  Major \n- “Shorter sequence lengths require fewer autoregressive generation steps, and reduce latency”:\n    - This statement obviously depends on “per-step” computational latency as well.  One way to estimate this could be taking into account `inference FLOPs/byte` instead of `bytes/step`, if inference FLOPs were to be considered a measure of latency. Figure 3 already looks at it. Figure 4 sheds light on `bits/byte` vs `bytes/step` tradeoff and indeed seems to suggest that at certain bits/byte the claimed technical statement in the corresponding section is indeed true, however, it does not justify that we can get lower inference latency at iso-performance for a given task of equal input length.\n    - Similarly, in section “Equal-Info Windows make AC learnable” in Results, it is unclear where “all our SentencePiece models require 23% longer sequences to encode the same text” statement comes from. Is it just the compression ratio comparison between SentencePiece versus the compared compression scheme?\n- “Section 5.2 Transformers struggle to learn Arithmetic Coding”\n    - I think this experiment is very interesting and important to the major conclusions coming from the paper, but not presented clearly. I got the gist but was unable to follow the exact experimentation setup. I would strongly recommend re-writing this section with clear experimentation setup. In particular, inputs and outputs for each of the tasks — “compression”, “decompression”, and “Byte Level LM”, contrasted against the standard setup in the paper, should be clearly presented.\n- One of the main claims of the paper is that it `EqualInfoAC` beats the byte-level tokenizers. However, only one byte-level tokenizer is considered in the experiments (called `Bytes` referring to `ByT5` from Xue et al., 22). It would make the paper stronger if atleast one or few other byte level standard tokenizers are compared, e.g. WordPiece or just simple Byte-pair encoding.\n- `EqualInfoAC` is not exactly lossless compression scheme as explained in detail by authors in Section D.5. I agree with the author’s analysis that this does not affect any of the conclusions, however, it will still be useful to highlight this fact in the main text. Apologies if this already exists in the paper but atleast one reader missed it. \n\n###  Minor \nTechnical questions and/or suggestions, in no-particular order:\n- Which algorithm is used for SentencePiece — BPE or unigram? Section 3.6 is missing this detail. \n- Results Section “Equal-Info Windows make AC learnable“ states: “Using 16-bit tokens (65k vocabulary) increases performance further. EqualInfoAC[b=16, v=65k] outperforms the Bytes baseline at all model sizes. It underperforms the SentencePiece baseline, but the gap diminishes.” The closing gap between the two can be presented clearly. A log-plot would be useful to highlight this difference as it seems to be the case that we have standard diminishing returns in the shown plot.\n- Similarly, the above section can be written more clearly to clarify point 1 in the Major comment 1 above.\n- Overall results seem to suggest that being able to eliminate the token variability is extremely important for learning. For instance, the best performing EqualInfoAC is with the set of hyper-parameters when “the model uses exactly one token to represent each equal-info window”. Can authors shed some more light on this observation? This seems to suggest to me that beating standard tokenizers under the considered setup would always be hard as any good non-IID, lossless, compression scheme typically has two parts: prediction and entropy coding. AC, or related variants such as ANS, are known to perform extremely well entropy coding however, in most real-world data, predicting non-IID alphabets results in better compression which is mostly achieved by better predictions coming from exploiting the contexts.\n- In section 3.3: “with a precision of 14. The range encoding implementation uses integers with precision + 2 bits. This is enough to encode 16-bit float logits, so should not cause numerical issues as our models are trained using bfloat16.”: bfloat and fp16 have different bits assigned to exponent and hence even this case can indeed lead to numerical issues. I think this statement should be toned down.\n- I think Figure 7 is particularly illustrative in terms of the differences in approach. If it can be promoted-up before the results section, it can clarify a lot of the experimentation section for the reader.\n- In Figure 8: why is trivial accuracy defined as “maximum accuracy achieved in the first 2,000 steps of training.” In particular, in left-subplot, why does higher token position achieves a higher accuracy faster than lower token positions? Footnote 22 is unclear.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the ability to train LLMs over compressed language data. Essentially switching the tokenizer for a compressed format. This is interesting because it allows one to essentially stretch the context window.   It also improves the inference speed and reduces computational costs, which will be beneficial on mobile phones or any device that is resource-constrained. But this also has come at the cost of a slightly lower  resulting perplexity. The reviewers, who I selected independently, were all unanimously in favour of the paper, and all independently recognized the strengths of the paper, and all strongly recommend the paper appear in ICLR.
Decision: Accept (poster)