gzip Predicts Data-dependent Scaling Laws — part 1/2

Cleaned-text code points [0, 15913). Bibliography omitted here; source.md includes it.

# gzip Predicts Data-dependent Scaling Laws

###### Abstract

Past work has established scaling laws that predict the performance of a neural language model (LM) as a function of its parameter count and the number of tokens it’s trained on, enabling optimal allocation of a fixed compute budget. Are these scaling laws agnostic to training data as some prior work suggests? We generate training datasets of varying complexities by modulating the syntactic properties of a PCFG, finding that 1) scaling laws are sensitive to differences in data complexity and that 2) gzip , a compression algorithm, is an effective predictor of how data complexity impacts scaling properties. We propose a new data-dependent scaling law for LM’s that accounts for the training data’s gzip -compressibility; its compute-optimal frontier increases in dataset size preference (over parameter count preference) as training data becomes harder to compress.

## 1 Introduction

A neural network’s performance generally increases as more compute is allocated for training. When scaling compute, one must decide whether to increase a model’s parameter count or increase the dataset’s size—these must trade-off within a fixed compute budget. Scaling laws can tell us what specific allocation (i.e. parameters v.s. data) will maximize performance given a compute budget. Much work has explored scaling laws for neural LM’s [ Kaplan et al., 2020 ] , generally concluding that parameter & training token count should be scaled 1-to-1 [ Hoffmann et al., 2022 ] .

However, most prior work on scaling laws for LM’s have been estimated from transformers trained on scraped web text. Of course, this is quite a specific data distribution, so we may naturally ask whether the scaling laws extrapolated from such web text datasets generalize to other distributions. Furthermore, it is generally understood that the art of training data mixture is the ‘secret sauce’ that enables frontier industry labs to continually deliver state-of-the-art LLMs [ Penedo et al., 2024 , Penedo et al., 2023 , Xie et al., 2024 ] . Considering that improving data quality can significantly raise LM performance [ Gunasekar et al., 2023 ] and that scaling laws in reinforcement learning have been shown to scale with game difficulty [ Jones, 2021 ] , we may hypothesize that current LM scaling laws (e.g. Chinchilla [ Hoffmann et al., 2022 ] ) are individual web-text-specific cases of a more general scaling law conditioned on properties of the training data.

Then, what properties of a training dataset of token sequences are neural scaling laws sensitive to? In other words, what can we measure about our data to more accurately predict the optimal compute allocation for training? Furthermore, is data-dependence of scaling laws only of theoretical interest, or can laws be considerably different for real-world datasets?

In order to study these questions, we seek a textual data setting where we can intuitively control its complexity as well as open avenues for information-theoretic understandings of why scaling laws are data-dependent. We therefore settle on probabilistic context-free grammars (PCFG) [ Chomsky, 1956 ] which are relatively naturalistic (can model natural language, code, etc.), controllable in syntactic complexity, and follow some well-understood information-theoretic principles [ Chi, 1999 ] .

We generate 6 datasets of varying complexity by modulating syntactic properties of a PCFG. For each of these datasets, we train LMs of 6 different sizes (4.4M to 1.4B parameters) and record results at 6 different train step counts (100K to 100M tokens). We then fit a scaling law for each dataset [ Muennighoff et al., 2023 ] , finding meaningful shifts in the law’s parameters as syntactic complexity increases. Following prior work on entropy of formal grammars [ Arora et al., 2022 ] , we use median compressibility of each token sequence in a dataset as a measure of complexity that is straightforward to compute with gzip [ Gailly and Adler, 1992 ] .

We find that as the training data becomes less compressible (more complex), the scaling law’s compute-optimal frontier gradually increases its preference for dataset size over parameter count. We then measure the compressibility of real-world code & natural language datasets, showing that the former is considerably more compressible and thus subject to a predictably different scaling law. With some napkin math, we estimate that we could reach the performance of StarCoder [ Li et al., 2023 ] with 24% fewer FLOPs ($278,000 in H100 hours) since our compute-optimal scaling adjusts for data complexity.

## 2 Related Work

### 2.1 Scaling Laws

Early work established that a neural network’s test error is a power law of training dataset size [ Cortes et al., 1993 ] , model parameter count [ Rosenfeld et al., 2019 ] , and that the relationship holds over many orders of magnitude [ Hestness et al., 2017 ] . Kaplan et al. [2020] applied scaling laws to transformer-based language models and identified a compute-optimal frontier along which parameter & dataset size should be scaled. Hoffmann et al. [2022] propose the Chinchilla scaling laws, finding that Kaplan et al. [2020] and Rae et al. [2021] overparameterized their models and that the compute-optimal frontier requires parameter & dataset size to be scaled equally (rather than parameters scaling at 3x the rate of data).

Sorscher et al. [2022] find that we can reach exponential (rather than power law) scaling on dataset size by pruning out redundant examples that do not provide much information to learn from. Liu and Tegmark [2023] identify a mechanistic explanation of why scaling follows a power law on model width.

Aghajanyan et al. [2023] extend the Chinchilla scaling laws to a variety of modalities such as speech, image-text, and code. Caballero et al. [2023] propose a novel functional form for scaling laws that better models complex non-monotonic behavior and also apply it to several modalities including code. Both these works and Hoffmann et al. [2022] (in Appendix C) find that scaling behavior for code is different than for natural language —code is easier to learn and its compute-optimal frontier prefers parameters slightly over data. Bi et al. [2024] cursorily investigate scaling laws across datasets of different qualities, finding that cleaner & higher quality data results in the “model scaling exponent increasing” because “high-quality data usually implies logical clarity and less predictive difficulty after sufficient training”. However, none of these works identify an underlying general principle that explains why scaling behavior varies across data modalities & complexities (or even just between code and natural language).

Meanwhile, Jones [2021] explores scaling laws in the context of board games, finding that “the compute required for a desired level of performance can be calculated directly from the board size”. If scaling laws smoothly scale with data complexity in the board game setting, do they also smoothly scale with textual data complexity? And how might we measure a text dataset’s complexity?

### 2.2 Syntax & Information Theory

A long history of work in linguistics has sought to apply information-theoretic measures to natural language [ Shannon, 1951 , Cherry et al., 1953 , Harris, 1991 , Piantadosi et al., 2011 ] . Specifically, entropy (a fairly abstract information-theoretic measure) can be operationalized in a number of concrete ways to measure the informational complexity of a linguistic distribution [ Arora et al., 2022 ] . One way to determine the ‘goodness’ of an entropy measure over sequences is whether it grows as the syntactic complexity of a language increases (e.g. more production rules, more non-terminals, longer right-hand sides). While entropy is straightforward to compute in closed-form on simple formal languages (i.e. Type 3 Chomskyan grammars, generated by Finite State Automata) [ Grenander, 1967 , Sánchez et al., 2018 ] , for Context-free (Type 2) grammars, we must estimate entropy from a set of generated samples [ Chi, 1999 , Corazza and Satta, 2007 ] .

Leveraging the widely-recognized relationship between entropy and compression [ Shannon, 1948 , Huffman, 1952 , Ziv and Lempel, 1977 ] , we can use gzip [ Gailly and Adler, 1992 ] , a lossless compression utility that implements DEFLATE [ Deutsch, 1996 ] (a combination of Huffman coding & the Lempel-Ziv algorithm) to estimate the entropy of sampled linguistic sequences.

Delétang et al. [2023] adapt language models as lossless compressors of token sequences and provide new insights on scaling laws from this compression perspective, finding that beyond a critical model size, the compression rate (accounting for parameter count) reverses its improvement. In a somewhat similar vein, Jiang et al. [2023] use gzip with k-Nearest-Neighbors to beat neural text embeddings. Importantly, they both brought to attention the effectiveness of compression algorithms for heuristically measuring the structure learned by language models [ Huang et al., 2024 ] . Another line of recent work investigates the learnability of different languages by LMs, finding that natural languages vary in their learnability [ Cotterell et al., 2018 ] and that LMs struggle to model syntactically ‘impossible’ languages [ Kallini et al., 2024 ] .

## 3 Modulating Data Complexity via Syntactic Properties of a PCFG

Probabilistic Context-Free Grammars (PCFGs) are a fundamental tool in computational linguistics for modeling the syntax of natural languages. A PCFG extends the concept of a standard Context-Free Grammar (CFG) by associating probabilities with its production rules, enabling the representation of language ambiguity and variability in a quantifiable manner. These grammars generate trees where each node represents a syntactic category, and the edges represent production rules applied to generate sentences. When generating sentences from a PCFG, we probabilistically sample sequences of production rules to apply until all leaves of the tree are terminals (actual vocab tokens).

We can control the syntactic properties of a PCFG to naturalistically modulate the complexity of a textual dataset that we sample from its generated sentences. Specifically, our PCFG creation function accepts arguments for the number of terminals, number of non-terminals, the maximum length of the right-hand side of a production rule, and the maximum number of production rules allowed for any non-terminal (i.e. if this is 1, a given non-terminal will always lead to the same right-hand side). Intuitively, as each of these values increase, the language’s syntactic complexity also increases.

To create a PCFG from the above arguments, for each non-terminal, we randomly choose its number of productions (RHS options), each of those production’s length, instantiate a production rule by randomly sampling from the terminals & non-terminals, and assign it a probability normalized by the total RHS options for the non-terminal. We then collect all the generated production rules for all the non-terminals and instantiate a grammar using the PCFG package [ Breydo, 2021 ] built on NLTK [ Bird and Loper, 2004 ] .

We can then use the grammar that we have randomly (within given constraints) created to probabilistically sample sentences to construct a dataset of token sequences. To make it easier later to compare training across grammars that produce sentences of different average lengths, we decide to sample sentences into documents of the same token count (our LM’s context length). We sample sentences from our grammar until we’ve filled up the context length, and if we overflow, we simply truncate the sequence.

Sentences are composed of terminals that are just integers and can thus be treated as token IDs for our LM; we concatenate sentences with the unused integer 0, effectively corresponding to a period in natural language. To clarify, we do not generate strings that ‘look’ like natural language and must be tokenized—the PCFG generates sequences of token IDs themselves. Now, we can generate 6 datasets of token sequences with varying complexities from just 6 sets of initial grammatical constraints.

### 3.1 gzip -compressibility Measures Syntactic Complexity

Now we must choose a metric to estimate the complexity of our datasets. While for our PCFG-generated data, we could use a trivial function of its syntactic properties (e.g. number of non-terminals plus median production rule length), we would only be able to apply this metric to datasets where we precisely know the grammar that generated the data. Instead, we need a measure of complexity that we can apply to real-world token sequence datasets so that we can see whether our data-sensitive scaling results on PCFGs generalize to real-world datasets. While one might try to use grammar induction to identify the underlying syntax of a real-world dataset and then compute complexity from its syntactic properties, this is computationally intensive and difficult with noisy web-text data.

Therefore, as explained in Sec. 2.2 , we choose to use a compression algorithm, gzip , to estimate the complexity of a dataset by virtue of considerable theoretical work establishing compressibility − 1 ∝ \text{compressibility}^{-1}\propto entropy [ Shannon, 1948 ] and entropy ∝ \propto syntactic complexity [ Chi, 1999 ] . Specifically, for each token sequence in a sample of 1000 from the dataset, we apply gzip and compute the ratio of the size (in bytes) of the compressed data to the original data. We then compute the median and standard deviation in compressibility, confirming that grammars with higher syntactic complexity result in datasets that are more difficult to compress.

In Tab. 1 , we list the syntactic parameters for each grammar and the compression ratio we measured of token sequences sampled from the grammar. Observe that as non-terminals (grammatical categories), terminals (tokens), right-hand side options, and right-hand side length increase, the gzip -compressibility also increases (i.e. it becomes harder to compress). We plot these datasets alongside natural language & code in Fig. 1 , showing how some PCFG datasets are more similar in complexity to code (the ones that are easier to compress) while others are more similar to natural language.

## 4 Are Scaling Laws Sensitive to Data Complexity?

To identify the scaling law for a dataset, we train a set of models of varying sizes (4.2M, 8.8M, 20.3M, 59.0M, 275.3M, 1.4B parameters; architectural specifics in Tab. 6 ) on varying size subsets of the data (100K, 1M, 5M, 20M, 50M, 100M tokens) and fit a power law on the resulting final losses of all training runs. Most experiments were run on a cluster of 4 Nvidia A100’s with 80 GB VRAM each using PyTorch FSDP [ Paszke et al., 2019 , Zhao et al., 2023 ] . We use a batch size of 32, single epoch training, the A ​ d ​ a ​ m ​ W AdamW optimizer [ Loshchilov and Hutter, 2017 ] , and a learning rate starting from 5 ​ e − 5 5\mathrm{e}{-5} and cosine decayed over the number of train steps [ Loshchilov and Hutter, 2016 ] .

As intuitively expected, the more compressible a dataset is (lower compressibility ratio), the faster that models regardless of size will converge (Fig. 2 ). While this shows that we need more compute to model more complex datasets (which is in and of itself notable), we need more evidence to determine if the compute-optimal frontier directionally shifts based on data complexity. To establish such a non-trivial sensitivity of scaling laws to data complexity, we need to compute the law for each dataset and examine its fitted parameters.

### 4.1 Computing Data-sensitive Scaling Laws from gzip -compressibility

The scaling law functional form proposed by Hoffmann et al. [2022] predicts training loss as a function of model & dataset size: