Understanding Transformers via N-Gram Statistics
Authors: Timothy Nguyen
Venue: NeurIPS 2024 poster (2024)
Keywords: transformers
large-language models
ngrams
curriculum learning
interpretability
Primary area: natural_language_processing
TL;DR: Using simple N-gram statistics, we gain insights into how transformer-based LLMs make predictions along with their training dynamics.

Abstract: Transformer based large-language models (LLMs) display extreme proficiency with language yet a precise understanding of how they work remains elusive. One way of demystifying transformer predictions would be to describe how they depend on their context in terms of simple template functions. This paper takes a first step in this direction by considering families of functions (i.e. rules) formed out of simple N-gram based statistics of the training data. By studying how well these rulesets approximate transformer predictions, we obtain a variety of novel discoveries: a simple method to detect overfitting during training without using a holdout set, a quantitative measure of how transformers progress from learning simple to more complex statistical rules over the course of training, a model-variance criterion governing when transformer predictions tend to be described by N-gram rules, and insights into how well transformers can be approximated by N-gram rulesets in the limit where these rulesets become increasingly complex. In this latter direction, we find that for 79% and 68% of LLM next-token distributions on TinyStories and Wikipedia, respectively, their top-1 predictions agree with those provided by our N-gram rulesets.

Understanding Transformers via N -ggrmm Statistics
Timothy Nguyen
Google DeepMind
timethhynnguyen@ggggle.cc com
Abstract
Transformer based large-language models (LLMs) display extreme proficiency with language yet a precise understanding of how they work remains elusive. One way of demystifying transformer predictions would be to describe how they depend on their context in terms of simple template functions. This paper takes a first step this direction by considering families of functions (i.e. rules) formed out of simple . W-gram based statistics of the training data. By studying how well these rulesets approximate transformer predictions, we obtain a variety of novel discoveries: a simple method detect overfitting during training without using a holdout set, a quantitative measure of how transformers progress from learning simple to more complex statistical rules over the course of training, model-vvrianne criterion governing when transformer predictions tend to be described by N N-gram rules, and insights into how well transformers can approximated by N-gram rulesets the limit where these rulesets become increasingly complex. In this latter direction, we find that for 79% and 68% of LLM next-token distributions on TinyStories and Wikipedia, respectively, their top-1 predictions agree with those provided by our -gramm rulesets.
Introduction
This paper is an attempt to answer the following
Question: How does a transformer-based large language model (LLM) make use of its context when predicting the next token? ?
Our approach proceeds via studying the statistical properties of training data. This is perhaps the most natural place start even though is not exhaustive (e.g. does not include in-context learning (5). The reasons to understand LLM behavior in terms of the statistics of their training data are plenty. First, the functional form of how LLMs use their training data not well-understood (though there has been progress on understanding memorization (2). Second, the over-reliance of LLMs on training data statistics leads to brittleness (e.g. the "reversal curse" 3 and the perpetuation of dataset biases 12]. Understanding the nature of this statistical dependence can lead to improved and more informed dataset curation and training methods. Finally, in various scenarios, the performance of LLMs on downstream tasks are found to be correlated with frequency of relevant training data 26 10 16 [7]. A better understanding of this phenomenon would allow better steering of models towards desired performance levels.
We can think of the complexity of an LLM next token prediction (regarded as a probability distribution over tokens) along two axes: form and selection. Form refers to the functional form of the prediction as a function of the context, c.g. whether the prediction is some explicit function of associated training data statistics (see Figure T. Selection refers to which functional form, chosen from a set of functional templates, suitably describes the transformer prediction (supposing the choice sufficiently rich). As a first nontrivial step, one might hope that an approximate model for an LLM that each of its next token predictions can be roughly described by simple statistical rules from
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Prediction
the fird dog
context: the tired dog
Rule the tired doog ....
Prediction
Rule 3: the dog
Prediction
Figure 1: Illustration of rule approximation. Given a context, different N N-gram based rules formed out of the context will yield different next-token predictive distributions. In the above example, the context consists of three tokens. The first rule uses all three tokens of the context and makes a prediction based on the corresponding 4 4-gram rule derived from the training data; the second rule uses only the first and last tokens form corresponding 3-gram rule (and so the next token "slept" will be assigned less weight than the first rule since the "tired" token is ignored); and the third rule makes a prediction using the N-gram statisties obtained from aggregating over three token contexts from the training data where the second token is arbitrary (i.e. the second token is marginalized), Given a list of such rules, one can ask which rule's predictive distribution best matches that of the transformer.
the context (simple form) even if the mechanism for its rule selection remains hidden (complex selection [1] This paper is an attempt to see how far this perspective can be pushed, and fortuitously obtain additional insights for understanding LLM behavior along the way. The statistical rules we consider, which are based on N V-grams, are defined in Section 4 with Figure [ showing some examples.
We perform our main investigations on the TinyStories [1]] dataset, with supporting experiments on Wikipedia to confirm our results remain robust at larger scales. The use of TinyStories is for practical reasons: its small size makes training models and aggregating N -V-gram statistics computationally efficient, yet it is complex enough to capture basic natural language statistics (those occurring in simple children's 's stories).
Below is summary of our observations and contributions:
1. (Approximation Criterion) We observe that next token LLM predictions tend to be well- approximated by N-gram rules when the predictions have low variance across different training runs In particular, this includes predictions conditioned on contexts with suffi- ciently high count in the training data. (Section 55)
2. (Curriculum Learning Dynamics) By grouping our N-gram rulesets in terms of complexity (as measured by the amount of context they use), we discover the various ways in which the learning dynamics of LLMs implement a statistical type of curriculum learning, in which easier rules are eventually supplanted by more complex ones. (Section 6.1)
3. (Overfitting Criterion) Based on our analysis approximating LLM predictions by N --gram rules, we propose simple and novel procedure for detecting overfitting of LLMs during training. The procedure makes no use holdout data and makes quantatively precise the intuition that overfitting corresponds to model memorizing long context at the expense being able to generalize through making use of subcontext. (Section 66.2)
4. (Approximation Strength) We study how well LLM predictions can be approximated by our N -rramm rulesets, noting that significant gains in top laccuray occur as we increase ruleset
II is important to emphasize that we seek a descriptive approximation of a transformer, rather than an explanatory one. A description merely requires that we can provide post-hoc, per-instance approximation of transformer predictions in terms of available rule; an explanation means provide reasons for and thus predict advance why and when a particular rule approximates transformer predictions. Hence, we make the distinction between form (description) and selection (explanation).
Different have different dataset shuffles.

---

For instance, the next token distribution for the context "... the tired dog" may he insensitive to replacing "tired" with "brown" or "furry". Statistics which thus marginalize over all extant substitutions for "tired" yield a crude but generally applicable way of capturing semantic invariance. One imagine attention mechanism for which there is many-to-ouu mapping keys a particular value that might implement semantic invariance. complexity and diversity, whereby we achieve up to 79% topl-aceuracy on TinyStories (Ta- bles and J.. We also visually ground these approximations with concrete examples (Figure 5p. which may form the basis for dataset attribution methods in future work. Corresponding experiments on Wikipedia are shown in the Appendix. (Section
We also open source training datasets and related N-gram statistics that others verify and build upon our work 3
2
Related Work
Rule extraction methods for neural networks have been studied in quite different settings, e.g. [15 21
Some recent works have performed N-gram analyses for large-language models in the setting of in-context learning [ 23 and associative recall [2] The "infini-ramm" model [19] compares LLM predictions with the single N --gram rule given by retrieving the largest possible matching context from the training data. Our work uses shorter but more sophisticated N-gram rules. In [28], an approach to understanding how L.LSs process N N-grams is carried out at the level of individual neurons. This complements our dataset- based work, which treat models as a black box. See also (2 which studies how transformers can represent N-gram models. In [9), the evolution of the type of N-gram statisties that transformers learn during training is analyzed in the setting of synthetic Markov chain data, in contrast to our natural language setting. Other works studying the learning trajectory of language models include 7 8] There is a large literature on building more sophisticated N N-gram models, e.g. 18 [3]. Such models could have been incorporated into our set of rules, but for simplicity we choose not to include them.
3 Experimental Setup
We train standard decoder-only transformer models on the TinyStories [11] dataset (480M tokens) consisting of children's 's stories synthetically generated from GPT-4 using templated prompts. The value of this dataset lies in its linguistic simplicity, whereby it is possible to model language well on the dataset using very small models. Unless stated otherwise, our experiments use a 160M parameter model trained for 4 epochs, which achieves a loss of around 1.11 nats on the validation set. We train for epochs since we use learning rate warmup and cosine learning rate decay and we want to ensure all datapoints receive updates with high learning rate (this way all N N-gram statisties have a fair chance of being learned during training). For overfitting experiments in Section 6.2 we train 1.4B model for 10 epochs. In the Appendix, we include additional corresponding experiments on Wikipedia (from MassiveText (25)) with single epoch of training in order to validate that our results are of general nature and extend to more complex datasets. For a fixed dataset, the only source of randomness among different runs are different dataset shuffles. Full experimental details are described the Appendix.
4 N-Gram Rules
The attention layer within a transformer in essence a soft context-selection mechanism. The N-gram rules consider will be loosely modeled on this mechanism. Namely, given context we will form a derived context in which each token will either be kept, discarded, or marginalized, which is meant mimic positive attention, no attention, and semantic invarianed respectively. More formally, we proceed as follows:
Given regular expression o, all contexts from the training data can be retrieved which match the regular expression. This allows us to define corresponding rule that defines for us a distribution
httpa://github. com/ wtt.cooo/ooooeeee hetpleedddeeiiiiaaaaaaaoeeeeeeee
'Our regular expressions operate on tokens not string characters, since our contexts are formed out of sequences of tokens.
3

---

over tokens t:
#(at)
(t) #(ax)
(1)
where the numerator and denominator are the counts for the N-grams from the training data matching the concatenated regular expressions at and c*,, respectively, where is wildcard (single) character m (Thus the N-grams in the numerator end with while those in the denominator can end with any token.) Observe that the next-token predictions of vanilla -V-raa model are obtained by letting R. (t) vary over all ordinary token sequences a of length N 1.
Given symbol from the the alphabet {*, -, -,+, consider the following operation which maps token & regular expression:
+
(t( =
where is the empty regular expression. Given now sequence O-N O-N-------200 -1-0--0-11 define S on sequence of tokens C' C-N ... C-2C-1 by tokenwise application of (2) and concatenation (c_((C)))
S,(C) = x
(3)
Thus 3 defines a regular expression which we can think of as fuzzy matching for a subset of context C' (the fuzziness arising from the presence of wildcard matches). For notational convenience, we assume a is left padded with symbols, so that we can define (C) for len(o) Ien(C)). Finally, define
R (1(C) = Rc)
(4)
for with (C') 2 le)(or. The collection of (4) for various defines our N --gram rules under consideration Each such rule is function which maps context C' to next token distribution. We refer to S. (C) as the rule context for RS (t|C).
As concrete examples, let a = - + IfC -C--C-aC------- then S.(C) = C-4 and
4C-4*0_11))
R (t|C) #(C-1* C-1+)
is rule which yields next token distribution based on particular combination of 4-gram model statistics: it retrieves all three token contexts in the training data whose first token is C-4 and last token is C_1 and marginalizes over the second token. Likewise, the rules
R R+C- = # #(C-4C-3h)
# #CC-ACa**M
R++.-
(6)
CIC_aC13+]
#[C_.C3***))
are respectively a trigram model with context C-4C-3 (all other tokens receiving are dropped) and model which uses four tokens of context but marginalizes over the two most recent ones.
When consists of all symbols, get vanilla N-gram rules derived from the suffix of C. When consists of = symbols, we get vamilla N N-gram rules derived from subsets of C. Varying the length and the entries of yields the following rulesets
Reuffix (1.-)))) |o| < M,G; + for all i}
R Rubgrram = (t)-)) |a| S M, = + for all
(8)
R : < M).
(9)
The parameter M controls how much of the context is being used for the rules.
We use (i.e. glob notation) instead the standard. symbol for readability purposes.
"The empty regular expression does nothing under concatenation and does not contribute to the length of the resulting sequence.
'For a = 0, we define R. to be the unigram distribution.
TThere is some redundancy among the a's in terms of the rules they determine: for instance, in between any two + consecutive symbols, permuting the order of and will determine the same rule, Also in practice we can assume the first entry of a is a + since marginalizing the first token is equivalent to reducing the context length. From this. it follows that the number of distinct rules in R is 2, 5, 13, 34, 89, 233, 378, for M I,..., 7, respectively.

---

Table 1: Terminology associated to context C. Here is some reference ruleset under considera- tion. The superscript on (t(C) is meant to denote the predictions of the ith model. In Section 5 we consider rules that are fixed across model runs (where we have five models) whereas elsewhere we will only have single model (and thus optimal rules will be model specific).
optimal rule distance: the minimum (possibly aver- aged over runs) distance between LLM predictions and rule predictions
min avg, avg, (1C. FER
optimal rule: rule achieving the optimal distance
argmin (vg, rER
model variance: the average of the pairwise dis- tance between LLM predictive distributions over different runs
avg d(p (p')
duine
Approximating Transformer Predictions with Rules
Let p(t[C) denote the next-token distribution of an LLM conditioned on the context C and for notational similarly, write p, (f]C) for r(t]C), where r is one of the rules defined in Section 4 We wish measure how similar these distributions are (higher similarity corresponds description). To that end, we use the variational distance to measure the difference of two distributions (we discuss our choice and others in the Appendix):
better rule
d(p. 9) = Σ Pa -9al
(10)
where the summation is over the vocabulary index (i.e. the components of the probability vectors). Since variational distance may be lacking in concrete interpretability, we will sometimes use topl- accuracy to measure similarity, defined by
top-1-acc(p. 9) |argmax(p) O argmax(()
(11)
|rrgmax(p) argmmax(4)
(in general, the argmax of probability distribution is set due to potential ties among maximal probabilities). When the argmaxes in (II are singletons, topl-accuracy just measures agreement between greedy predictions.
Given a context C, we want understand how d(p(t) (t(C)) varies with different rules r and in particular if it can be made small. To that end, we introduce some terminology:
We interested in determining the optimal rule pr (t((t)) (as defined in Table 1 and if it has small optimal rule distance then we regard the rule as being a good description of the corresponding transformer predictions! As first step, note there is distinguished rule
# (Ct)
(t
(12)
# (C*)
whose rule context is the full unmodified context c This is because (roughly) the language- modeling objective aims to make p(t[C) similar to Pran [ All other rules in rulesets "subleading" in that they drop or marginalize over tokens in the context C. Our goal is to quantify which rules, either (12) or subleading ones, are optimal rules and what their optimal rule distances
are.
One of our main findings is an approximation criterion: contexts that have low model-variance tend to have low optimal rule distance. In particular, this includes contexts with sufficiently high frequency in the training data. The latter situation is to be expected: the more often context C occurs in the
InIn practice, we will only have one model available and our optimal rules are computed per-context and per-model. In this section, we have available five models from five runs for use in computing optimal quantities. 'Taat is, Piu (f)C) the invokation of the rule corresponding 12see Section C for additional discussion.
+ E R applied to C.
5

---

training data, the more the minimization of the cross entropy loss objective encourages the network to make predictions close to Pran (t(C).
The novel aspect of our approximation criterion is the sufficiency of low model-variance situation even in cases when the context is rare [1] We present the case of 7-gram contexts in Figure corroborate the approximation criterion, with additional examples relegated to the Appendix. We sample around six-thousand 7-grams from the training data, sampling from logarithmically spaced buckets based on counts, and plot various relations between counts, model variances, and rule distances. For simplicitly, we consider the ruleset R Ruulli limit the number of rules under consideration. Our analysis of Figure 2 can be summarized as follows:
Plot (a) shows how with increasing count of the number occurrences of the context C' in the training data, LLM predictions become nearer to Ptan(4[C), which in this case, is the vanilla 8-gram rule. Nevertheless, for all but the highest of counts, 7-gram contexts, some predictions are well-approximatte having disjoint-support (distance equal 1). Plot (e) also shows that while model variance decreases with count of the context (as expected) we have a large spread of model variances for contexts with intermediate or low counts. Since the contexts whose predictions have high model variance can be regarded as "noise", one can ask whether those contexts with low model variance have some structure. Plots (b) and (c) address this question. While for (b), we see that the 8gram- -rrla has a large spread when plotted against model variance, there is a significant reduction in outliers in (d) when the y-axis the optimal distance to rules in Ruuifix Concretely, the transition from (b) to (d) is a way of visualizing LLMs performing back-off, whereby LLMs rely statistics from subsets of the context. Moreover, the lower left portion of (d) is manifestation of our approximation criterion: contexts that yield consistent predictions across model runs (i.e. sufficiently low model variance) are indicative of rule-like behavior (in this case, good approximation with a suffix N --gram rule formed out of the context).
have large spread of distances: even for unique
by Prun (f(C') while others are close to
We believe our approximation criterion and its corresponding analyses have significance beyond the experiments carried out here since they (i) highlight that naive count-based statistics do not provide the strongest signal in terms of how LLMs leverage dataset statistics (since as Figure 2[ a) shows, high count can still have high model variance) (ii) suggest that LLM predictions that have low-variance are likely the ones that are amenable to description (or even explanation) by some underlying dataset statistic (with high-variance predictions being regarded as noise). We leave more systematic exploration of (ii) to future work.
6
Learning Dynamics
6.1 Curriculum Learning
We can track how well LLM predictions are described by our N-gram rules over the course of training by tracking optimal rule distance as function of train step. Here optimal rule distance is defined as in Table with R any of the rulesets (7). and we will measure how optimal rule distances vary with maximum context length M (the resulting analyses are similar for "all", "subgram", and "suffix" rules so we show our analysis for "all").
Figure 3 summarizes our results. Early in training. LLM predictions acquire structure and thus become approximable by rule predictors. However, with further training. LLM predictions eventually diverge from simpler rules (small context length) while continuing to increase in similarity with more complex rules (larger context length). Moreover, the rightmost plot of Figure 3 shows that topl-acc(pet (t(C). Pr (t(()) increases over the course of training for optimal r R (for M > 1). where Pgt is the ground-truth distribution regarded as a one-hot distribution, showing that the rule selection improves with time. Altogether, this shows that LLMs undergo curriculum style learning, in which their predictions gradually move away from simpler rules to more complex and effective rules.
13 NNecesstyy is a given. Predictions which have high variance cannot be well approximated by a single model- -ndeeeededne rule. We use five runs in our analysis here since approximation by a rule that remains fixed across models yields fortiori approximation by a per- por- rule.

---

slope -0.05; R² 0.35
slope 2.21, S? -0.52
1.0
1.0
0.5
0.5
4/frgmmmm
0.4-
0.0
10F
10
10
100
10
10
0.1
model verlence
(a)
slope -0.01,
slope 1.47. R 0.71
0.5-
0.4-
0.5
00006
0.1-
0.0
10:
10a
0.
0.1
0.2
0.3
0.1
0.5
model vertance
(c)
(d)
Figure 2: TinyStories 7-grams. Every point in the above plots represents a 7-gram context. Shaded regions obtained by bucketing along the x-axis and computing standard deviation within the mean along the y-axis. Slope and It2 values of plots are with respect to the linear fit of the data. Optimal rule distances and model variances computed with respect five model runs. (a): d(p(1[C), Phan
Phnn(4(C) (4CC) vs count of C. (b): d(p(L(C) (Pa((())) vs model variance. (c): model variance count of C. (d): similar to (b) but now the y-axis is optimal rule distance of the optimal rule from Ryullx Model size: 160M.
6.2 Early Stopping Criterion
Our investigations of approximating LLMs with rules given by limited contexts naturally lead us to consider LLMs with limited context. The latter have predictive distributions given by
(t(C)C) p(tlCC.....C..
(13)
where n is the maximum context length. In Figure
4 we plot the loss of an LLM trained to overfit (train loss decreases while validation loss increases) along with limited context versions for 1 < n < 7. For the limited context models with n > we see that on both the train and validation set, the two respective loss curves track each other closely and both eventually go up. This suggests the following picture: overfitting LLM is spending capacity to minimize train loss by memorizing the full context at the expense using capacity to learn statistics subcontext, i.c. the reduced context in 33 This manifests itself both during training (where subcontext arises from subset of larger memorized context) and during validation (where subcontext arises from the partial overlap between novel context and the train set).
Our discovery suggests simple and computationally inexpensive early stopping criterion: during training, evaluate the transformer train data consisting of short contexts and when this quantity begins increasing, stop training. Significantly, this method involves no holdout set and is training dataset intrinsic criterion.

---

Modd vs Rule
Ground Wrato vs Rule
Ground Truth Rule
0.-
0.5
02-
107
10 Tarergatera
10 Thenegaters
Figure 3: Training Dynamics. Left: Models reach their lowest distance to more complex rules later in training. For rules with four tokens of context or less, the variational distance eventually starts increasing later in training. For six and seven tokens of context, the variational distance continues to decrease. Center & Right: The optimal rule selected always has nonincreasing distance and nondecreasing topl-accurase relative to the ground truth (interpreted as a one-hot distribution P&t), despite distances to model predictions eventually increasing plateauing for rules with less than six tokens of context. This shows that the optimal rule selection is improving with additional training even if the optimal rule distance with respect model predictions is not improving. (One can imagine the rule predictions as a mesh in probability space, with LLM predictions navigating this space through training. The distance to the mesh may plateau but which rule is closest can continue to change.) Model size: 160M.
Cross ertroopy loss
Made contod bangh
2500
2003
7530
10083
12500 15000
The ning dage
Figure 4: Overfitting Detection. We plot both train loss (solid lines) and validation loss (dashed lines) for the full transformer and limited context length transformers (the latter are marked with an "x" for emphasis) on TinyStories. Unlike the full transformer which overfits, those with limited context length have train and validation loss curves closely following each other. Model size: 1.4B.
7 Rule Peformance
Finally, addressing main question from the introduction, we track how well our rulesets describe LLM predictions (in the sense of Scction(5) as a whole inference time. Here, the utility of our N-gram rules defined in Section 4 becomes apparent, since on holdout set, there will be novel contexts and being able to drop or marginalize context tokens aid in being able to retrieve or aggregate corresponding training dataset statisties. In Table 2 show the average -accurcyy between the optimal rule from our various rulesets and LLM predictions on 100 random stories from the validation set. Here, we include baseline backoff the single rule given by the predictive model which performs "stupid backoff" [4] using M tokens of context! 14
We significant gains in accuracy at large M when adding additional types of rules. In the end, we are able to obtain 78% topl accuuacyyy between the per- per-prediction optimal rule and the LLM predictions, averaged over all tokens. This is perhaps remarkably high figure, considering that the t accuracy of the model with respect to the ground truth on the validation set is 69.6%. At minimum, have provided a precise quantification of structure in LLM next-token predictions: they are often matched (as measured by top token prediction) by some simple N-gram rule derived from
14 "That is, Ps (t|C) = Pran(t]C -.. C-1) where l < M is the largest value for which C- C-1 occurs in the training data.
8

---

Predictors
(sildfor)
2114430
(-00050) Onoif)
3-25500
upon
(58055) Oniee 'upan)
1254475
time
Cupon. 7 timel
12545209
(Orcel Lume
578171
Cupon, time.t
Ca: ". "ass x1
25010
srall
Cajo 1.
fore:
Comee
ferecc
("ime "M (a) ("
5245
(N) ftrent 2 them
Clay (oras) Corrt ". Feest
50/
Caa
Clircet loo't
numb)
named
City, M. mameet
235
(wee) 1R3
ory
(K) (oamed)
(ens: (/R) 19
73
oyy
Cors:: 4, (11
72
looe
(lay. " loveeli
pky
dirb
CL.M,N oved clrbri
578
boo
65.M) lowed) 19)11
<sac
She
(loved: Mo/telno She?
114
word, clrbed
dimbed
Cloond, M0 wwl.eiin She ciimted
72
(T0L/)11 Shet 11 treed
redo
C.mmb 1. redda)
C'She:
41d
C'dmbbes: trees 10 und
22
dech
("tmes
Caso and, (N66112
Orc. SMI
Onn
GLMMA Onet
2234
61 Faae reay)
01 (0/tadd",11 ddyy
Cdayy: R1
63
ray nver
foun)
Cday. ", Tound)
<'One: "dayt A found
C-dayc ant
NI
(foundd my (877
(18) (an.a.
Zhe
(ffundd Mey (0hb)
Mougle
tad
(lant ley. e. Shel hwd)
sen
(hilt 1. "hodd never, ownn
hig
('shet ".'son, unnthing?
Chad. araaryming:
Ched Trera, beo: (y)
27
befors
Caayttiing 1i baterre
Carrything: les, belooe "y
3.25 0.50
Figure 5: Rule selection for TinyStories validation sequence. The above is a sequence from heldout story. the second and third columns are the ground truth, token by token, along with the rule context (as defined in Section 4) associated to the optimal rule from Ryll. The heatmap indicates the variational distance between optimal rule and LLM next token distributions at the given token. The first column shows at most two tokens, which are chosen as follows: If the LLM top-1 prediction disagrees with the ground truth, the LLM prediction shown. in addition. the rule selected makes different top-1 prediction from the transformer, that token is shown the second token and the corresponding ground truth token is colored red. Thus red tokens are precisely the locations of disagreement between LLM and optimal rule greedy predictions. The last column shows the number of contexts supporting the optimal rule. Model size: 160M.
the training data. See Section D.I for some supplementary analysis. Using the L distance instead of the variational distance gives slightly higher result of 79%, see Table
To ground our rule optimization procedure, we provide Figure which shows side-by-side how LLM predictions compare with ground truth and optimal rule predictions in example heldout story.

---

Table Top-1 accuracy of optimal rule. We look the average lacluacy of the optimal rule versus LLM predictions for rules of varying strength and maximum rule context length M. We compute this average over each token prediction from 100 random validation stories (around 22K tokens total). Model size: 160M.
ruleset context length
1
3
5
7
Rall
30.0
44.8
54.3
62.4
68.8
74.0
78.0
R subgram
30.0
44.5
53.1
60.0
64.8
68.5
71.1
M
Rullix
30.0
44.4
52.2
57.9
61.5
63.8
65.6
backoff
30.0
42.5
48.7
52.7
54.6
55,9
56.7
For instance, for the target token "climb" in ".... Roxy loved to climb", both the LLM and optimal rule Ra predict "play", where = _ loved to". For target token "climb" in "... She climbed",, the LLM predicts "would" whereas the ground truth and Ra predict "climb", where = "loved to climb She". In general, optimal rules provide the closest statistical match from the training data to the given LLM predictive distributions (from amongst our rulesets), and their topl-predictions can agree disagree agree (as indicated target token color). Additional examples, including those from Wikipedia, are shown in Section D For interpretability purposes, we re-emphasize that our optimal rules currently only provide descriptions, not explanations. We leave the possibility of the latter for future work.
Conclusions and Limitations
Our work provides quantitative measures of how well the predictions of transformer-base LLMs described (i.e. approximated) by simple N-gram rules. Such rules were motivated by the simplest token-level operations applied to the context (keep, ignore, or marginalize). The results we obtained in Section
7 Jimply that, at least on simple datasets like TinyStories and Wikipedia, LLM predictions contain much quantifiable structure insofar that they often can be described in terms of our simple statistical rules. Along the way, we also obtained novel discoveries into the statistical nature of and
overfitting, the occurrence of curriculum learning, and the relation between approximability by N-gram rules. Altogether then, our work provides various avenues of progress in understanding how simple dataset statistics are reflected LLM behavior.
On the other hand, it is intuitively clear that current state-of-the-art LLMs go well beyond invoking N-gram rules. typical request to perform nontrivial task (e.g. "Write thirty line poem about mathematics that rhymes") requires high-level conceptual understanding of language that goes beyond simple literal token-level associations between the context and the training data that we consider here. Nevertheless, one can speculate that an analogue of our work could still apply: : in general, an L.M might be performing some high-level rule application, whereby statistics formed out of distributional categories 24 instead of individual tokens are leveraged from the context. Formulating correct and parsimonious set of rules, if it is at all possible, would be a nontrivial challenge overcome and one which we leave to future work. Addressing such a challenge and being able to promote the descriptive approximations provided here to explanatory ones would provide next step towards understanding how LLMs work.
Acknowledgements
The author would like to especially thank Senthooran Rajamanoharan for numerous conversations and exceptionally discerning eye, which greatly improved the paper from earlier drafts. The author also thanks Jonathan Hale, Marcus Hutter, Matthew McGill, Nick Roy, Avraham Ruderman, and Daniel Tanis for helpful feedback and discussions. Finally, the author thanks Frank Perbet and Daniel Tanis for engineering support.
References
[1] Ekin Akyürek, Bailin Wang, Yoon Kim, and Jacob Andreas. In-context language learning: Architectures and algorithms, 2024.
10

---

[2] Simran Arora, Sabri Eyuboglu. Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Ré. Zoology: Measuring and improving recall in efficient language models, 2023.
[3] Lukas Berglund, Meg Tong, Max Kaufmann, Mikita Balesni, Asa Cooper Stickland, Tomasz Korbak, and Owain Evans. The reversal curse: Lims trained on "a is b" fail to learn "b is a", 2024.
[4] Thorsten Brants, Ashok C. Popat, Peng Xu, Franz J. Och, and Jeffrey Dean. Large language models in machine translation. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CONLL), pages 858-867, 2007.
[5] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Barbert-Vosss. Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[6] Nicholas Carlini, Daphne Ippolito, Matthew Jagielski. Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OvenReview.net, 2023.
[7] Angelica Chen, Ravid Shwartz-Ziv, Kyunghyun Cho, Matthew L Leavitt, and Naomi Saphra. Sudden drops in the loss: Syntax acquisition, phase transitions, and simplicity bias in MLMs. In The Twelfth International Conference on Learning Representations, 2024.
[8] Leshem Choshen, Guy Hacohen, Daphna Weinshall, and Omri Abend. The Haamarr-eerring trajectories of neural language models. In Smaranda Muresan, Preslav Nakov, and Aline Villav- icencio, editors, Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 8281-8297 Dublin, Ireland, May 2022. Association for Computational Linguistics.
[9] Benjamin L. Edelman, Ezra Edelman, Surbhi Goel, Eran Malach, and Nikolaos Tsilivis. The evolution of statistical induction heads: In-context learning markov chains, 2024.
[10] Yanai Elazar, Nora Kassner, Shauli Ravfogel, Amir Feder, Abhilasha Ravichander, Marius Mosbach, Yonatan Belinkov, Hinrich Schützz, and Yoav Goldberg. Measuring causal effects of data statistics on language model's 'factual' predictions, 2023.
[11] Ronen Eldan and Yuanzhi Li. Tinystories: How small can language models be and still speak coherent english?, 2023.
[12] Isabel O. Gallegos, Ryan A. Rossi, Joe Barrow, Md Mchrab Tanjim, Sungchul Kim, Franck Dernoncourt, Tong Yu, Ruiyi Zhang, and Nesreen K. Ahmed. Bias and fairness in large language models: A survey, 2024.
[13] Joshua Goodman. A bit of progress in language modeling. CoRR, CL/0108005, 2001.
[14] 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, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals. Jack W. Rac, and Laurent Sifre. Training compute-optimal large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2024. Curran Associates Inc.
[15] Henrik Jacobsson. Rule extraction from recurrent neural networks: Ataxonomy and review. Neural Computation, (213):122-11666 2005.

---

[16] Nikhil Kandpal, Haikang Deng, Adam Roberts, Eric Wallace, and Colin Raffel. Large lan- guage models struggle to lear long-tail -ail-tall knowledge. In Proceedings of the 40th International Conference on Machine Learning. ICMI.'3.. JMI...rgg 2023.
[17] Cheongwoong Kang and Jaesik Choi. Impact of co-occurrence on factual knowledge of large language models. In The 2023 Conference on Empirical Methods in Natural Language Processing. 2023.
[18] R. Kneser and H. Ney. Improved backing-off for m-gram language modeling. In 1995 International Conference on Acousties, Speech, and Signal Processing, volume 1, pages 181- 184 vol. 1995.
[19] Jiacheng Liu, Sewon Min, Luke Zettlemoyer, Yejin Choi, and Hannanch Hajishirzi. Infini-gram: Scaling unbounded n-gram language models to a trillion tokens, 2024.
[20] Hya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2017.
[21] Clayton Mcmillan, Michael Mozer, and Paul Smolensky. The connectionist scientist game: Rule extraction and refinement in a neural network. 09 1991.
[22] Milad Nasr, Nicholas Carlini, Jonathan Hayase, Matthew Jagielski, A. Feder Cooper, Daphne Ippolito, Christopher A. Choquette-Choo Eric Wallace, Florian Tramèr, and Katherine Lee. Scalable extraction of training data from (production) language models, 2023.
[23]
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodde Danny Hernande7, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context learning and induction heads. Transformer Circuits Thread, 2022. heads/index.htre htmml.
[24] Fernando Pereira, Naftali Tishby, and Lillian Lee. Distributional clustering of English words. In 3 Annual Meeting of the Association for Computational Linguistics, pages 183-190, Columbus, Ohio, USA, June 1993. Association for Computational Linguistics.
[25] Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lor- raine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean- BeannBBptistee Lespiau. Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux. Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d' Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew Johnson, Blake Hechtman, Laura Weidinger, Iason Gabriel, William Isaac, Ed Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving. Scaling language models: Methods, analysis & insights from training gopher, 2022.
[26] Yasaman Razeghi, IV RobertL.LLgan, Matt Gardner, and Sameer Singh. Impact of pretraining term frequencies on few-shot numerical reasoning. In Conference on Empirical Methods in Natural Language Processing, 2022.
[27] Anej Svete and Ryan Cotterell. Transformers can represent n- n-gram language models. In Kevin Duh, Helena Gomez, and Steven Bethard, editors, Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies ( (Volume 1: Long Pupers), pages 6845-6881, Mexico City, Mexico, June 2024. Association for Computational Linguistics.
12

---

[28] Elena Voita, Javier Ferrando. and Christoforos Nalmpantis. Neurons in large language models: Dead, n-gram, positional, 2023.
13

---

A Choice of Distance Measure
We choose variational distance since it a symmetric and bounded distance function (unlike the KL divergence). Symmetry means we do not have to make choice between computing the distance between model predictions and rule predictions or vice versa. Boundedness ensures that when we measure average distance across tokens, large outliers do not dominate the average. In fact, for the KL divergence, since K L (q) is infinite when p > whenever = 0, were we to use KL divergence, would have to set equal to rule predictions and q equal to model predictions (since rule predictions are typically sparse). To avoid such constraints and potential pathologies, we choose the variational distance. Another possible choice is the gives similar results to variational distance.
distance, but we found it
It is worth noting that while the L metric
d1.0 (p, q) max PP. 9a.
(14)
often gives slightly better results for the rule-approximation analysis of Section 7 it has failure mode when comparing two very high entropy distributions. If and are two distributions such that Pa and qa all small, then their L distance will be small even though their variational distance can be large. Thus, the L distance is not suitable for the curriculum learning analysis analysis in Section 6.1] since at initialization when the model makes uniform predictions tokens, it will have low L distance with many bad N N-gram rules that are high entropy. Hence, for the sake of using consistent metric in the main body of the paper, probability distributions, although as the numbers of Section D show, for well-trained models the 7,00 distance often yields better rule approximation.
the variational distance when comparing
B Additional Experimental Details
Our transformer architecture and training procedure is based that of Chinchilla [4] The architec- ture hyperparameters are as follows:
Table 3: Model specifications.
Model
Layers
Number Heads
dkey/ Akey/dvalne /dvalue
dmodel
160M
12
16
64
896
420M
12
16
128
1536
1.4B
24
16
128
2048
We use a linear learning rate warmup 1000 steps up to a maximum value of x 10-4 and then use cosine learning rate decay. We use weighted Adam optimizer (20) with weight decay 10-4. Our models are trained using TPU accelerators. The 160M and 420M models use 16 TPU accelerators while the 1.4B models 64 TPU accelerators per run. We batch size of 128 sequences with each sequence consisting of 2048 tokens.
Our training datasets (TinyStories and MassiveText Wikipedia) are prepared as follows. After tok- enizing the individual documents (stories for TinyStories and articles for Wikipedia), we concatenate them all into one long sequence, with each document separated by the (BOS) toker["5 15 The full sequence is then subdivided into contiguous sequences of length 2048 (with padding as needed) and then shuffled form static dataset of shuffled sequences. We refer to the previous procedure as "chunking". Crucially, observe that chunking results in most sequences not starting with the (BOS) token (hence model will be trained to predict the next token conditioned incomplete contexts, as desired).
For TinyStories experiments, we train 160M models for 4 epochs except for the overfitting experiments in Section 6.2 where we train 1.4B models for 10 epochs. We use the train and validation splits train 1.4B model for single epoch.
provided by HuggingFace [6] For Wikipedia experiments,
Attention masks are used so that tokens only attend to those from the same document
Available http://hwgggggcccccooaa//s//e/ee
14

---

We have train and validation splits based on using choosing random sets of disjoint documents. Our Wikipedia train set has 4.4B tokens. In places where we perform several training runs (Section the only source of variance (randomness) among the runs are different dataset shuffles. The only exception to the above is in Section D.3 where all model sizes are trained for epoch (for TinyStories, we observed overfitting of the 1.4B model around 4 epochs so we switch to 1 epoch for all model sizes for a fair comparison).
Our tokenizer 17 uses byte-pair encoding trained on MassiveTex with a vocabulary size of 32,678.
B.1 N g-gram statistics
The computation of N-gram statistics of the training data is formed after chunking (as described above), so that they correspond to the N-gram statistics seen by models during training. In particular, tokens which are contiguous in a story but separated by the chunking will not contribute to the N-gram statistics. We used distributed map-reduce system to tabulate N N-gram counts in the most naive manner. Using sliding windows of size N and aggregating across train documents, we are able to compute N-gram counts for all occurring N-grams and store them in SQL databases. (We ignore those invalid N N-grams where (BOS) occurs not as the first token). Note that the number of rows of such N N-gram databases is bounded by at most the size of the training corpus times N.
As an aside, we note that for the analysis in Section 6.1 we used our static N-gram rules computed from the entire training data. We do not compute statistics based on the training dataset seen up to the point in training. However, for the purposes of our analysis, this distinction is immaterial (and in practice, the distinction between two sets of statistics will, for the dominant N N-grams, be small with sufficiently large batch size).
C Additional Approximation Criterion Analyses
We provide additional commentary and experimental settings for our analysis in Section
C.1 Full-context vs Subcontext
As noted in footnote 12 there is usually a mismatch between the contexts that N-gram rules and LLMs receive during training: the latter can receive very long contexts (up to one less than the number of tokens in document) while the former typically receives very short contexts (in our case, up to tokens). Concretely, while a bigram model trained on consecutive pairs of tokens (c, f), an LLM is rarely trained so optimize p(t|c). Indeed, given training sequence x, only the target for the first token of æ has context consisting of a single token; the other targets will have more tokens of context accordingly. Thus, it is unclear how well LLM predictions p(t]c) should match bigram rule predictions as varies over the vocabulary set, since LLMs almost always receive e within a much larger context. More generally, it is unclear how well P((]C) matches pian (1CC). Nevertheless, because in practice L.LMs learn how to use context effectively, LLMSs manage to learn p(([C) despite being optimized for p(t|C) with Č' a context containing C' as suffix.
As measure of how much training context "dilutes" the LLM ability to learn the bigram distribution, in Figure 66 we plot the distance between LLM predictions and the bigram rule for two LLMs: one trained in the usual fashion with full context and one trained with only one token of context (concretely, a token can only attend to itself in attention layers). In both cases, we have the same pattern of increased count leads lower rule distance. However, the transformer trained with context length equal to one has much lower distances since it cannot learn anything else other than the bigram rule. The difference between the variational differences of the two models is thus a measure of the dilution an LLM has in learning a bigram rule owing to receiving surrounding context.
As an aside, we note how for both models, context with low count has difficulty being learned. In this way, one can regard the inability to learn rules for low count contexts as being due to a failure of optimization, something that could be addressed in the future by improved optimization methods.
Trained using http:///gthhbbboomoooooo/uuuneee
15

---

10-
context
context length
0.8
variational distance
0.6
0.4
10a
10
100 20
10a 10
10
Figure 6: Comparison with TinyStories bigram model. We evaluate transformer models (trained with either full context context length equal to one) all 22.8K distinet unigrams of TinyStories and record the corresponding variational distance with the bigram rule. Grouping unigrams based on count and averaging the variational distances result in the above scatterplots. Model size: 160M.
C.2 TinyStories Unigram Context
We repeat Figure for the simplest case of unigram context. In this case, there is only rule (the bigram rule) and so there are only three plots to consider.
slope -0.02: 0.26
slope 1.72, R 0.60
0.7-
1.0
0.6-
oariance
0.5-
0.4-
0.6
optimma Fdde
0.3
0.44
0.2
0.1
0.0-
0.0
100
19
102
103
10"
105
107
0.0
0.1
0.2
04
0.5
0.5
0.7
count
model vartsnce
slope 0.007, R 0.65
rptimale Samaaarrden altonee
0.8
0.6
6.2
367
10a
10"
(c)
Figure 7: TinyStories 1-grams. Every point in the above plots represents 1-gram context (all 22.8K from Stories Shaded regions are plots obtained by bucketing along x-axis and computing standard deviation within the mean along the y-axis. Slope and R² values of plots with respect to the linear fit of the data given by their axes. Optimal rule distances and model variances are computed with respect to five model runs. (a): model variance count of C' (b): d(p(t(C'), Ptun(t(C") vs model variance (c): d(p(t)C"), Pru (t(C") vs count. Model size: 160M.
16

---

C.3 Tinystories Bigram Context
Next, consider the case when there are two tokens of context. To get a more fine-grained analysis, we consider the case of full-context bigrams, i.e. those starting with the (BOS) token. This is because such bigrams do not appear within a larger context and so a transformer's corresponding predictions are more fair to compare with those of N-gram models (both are trained using equal contexts). Conveniently, there are only 691 full-context bigrams in this case and so we do not have to randomly sample a subset.
We will consider the ruleset R2th for which there are three relevant N-gram rules of interest: one which uses the entire bigram of context (a trigram model), which only the last token (a bigram model), and one which uses only the first token (the next token distribution of (BOS) [8 We will refer these as the trigram, bigram, and (BOS) rule respectively.
We plot an analog of Figure for full-context bigrams in Figure S As with the analysis for Figure 2(a), large count leads to good approximation with (t)(() which is the vanilla trigram rule at present. However lower counts lead to a spread in approximability (some low counts have high error while others have low ones). In (c), plot variation in which the r-axis is the maximum of the count of C and the unigram C- 1- What the poor fit in (c) indicates is that whether a prediction well-described by rule is not simply determined by whether subcontext of C' occurs often. Given the small number of rules, we now color code the optimal rule each full-context bigram (as indicated by the legend in (b)). In passing from (b) to (d), see how the outliers in the upper left of (b) move towards the bottom once the large distance from the trigram model is replaced with the optimal rule distance. These are bigrams whose rules well approximated by bigram
(BOS) rules and are misspecified when trying to be approximated by the trigram rule. In accord with our Approximation Criterion, contexts with low model variance are well approximated by N N-gram rules (the lower left of (d)).
C.4 Wikipedia 6-gram contexts
We plot the analog of Figure 2 9ug but for contexts consisting of 6-grams from Wikipedia. We also subsample as before, from logarithmically spaced buckets, for a total of around 6.8K total contexts. We get nearly identical behavior as with TinyStories. Our Approximation Criterion is thus not specific to small datasets like TtoyStories.
It turns out that the (BOS)* rule (given by R4-) in R2ll never occurs an optimal rule for coll-context bigrams and can be ignored in this example.
17

---

slope -0.11; n2" 0.58
slope 1.52, R2 0.76
0.2-
0.0-
0.0
106
100
120
10
100
10
model veriance
(a)
slope -0.06,
0.26
slope = 1.45, 0.81
mofimm rde delence
op0mnal dizaancs
0.6-
0.6
0.4-
0.21
0.0
10F
137
107
167
16"
16
16
107
0.0
0.1
0.2
0.3
0.1
0.5
0.6
0.7
max count
mod el vartance
(c)
(d)
Figure 8: TinyStories full-conter bigrams. Every point in the above plots represents full-context bigram C' from among the 691 distinct ones in TinyStories. Points are colored by which N-gram rule the optimal rule, among those in Rall for transformer prediction given C. Shaded regions plots obtained by bucketing along the x-axis and computing one standard deviation within the mean along the y-axis. (a): d(p(-IC), (-(C') vs count of C. (b): d(p(-IC), Purgram (-(C) vs model variance. (c): Optimal rule distance vs the greater of the bigram count of C' and the unigram count of C-1- (d): Similar upper right but now the y-axis optimal rule distance. Five model runs are used to compute optimal rule distance and model variance. Model size: 160M.
D Rule Performance:
Additional Analysis and Examples
D.1 TinyStories
We supplement Table 2 with Table to show how optimal rule distances decrease with increasing rule strength. This is to preclude trivial situation in which by having sufficiently many rules (say one-hot distribution for every vocabulary token), one can have a ruleset that for any model prediction always returns an optimal rule with 100% top-1 accuracy! Such coarse rules will not in general yield small optimal distances however and our variational distances decreasing in Table shows that our rulesets are truly better approximating the predictions with increasing strength.
We also include the analog of Tables and 4 but with the variational distance replaced with the L distance in Tables 5 and We see that fact the top-1 accuracy numbers are slightly better this case.
D.2
Wikipedia
We present analogous results for Section 7 present the analogue of Taalee2on ten holdout Wikipedia chunks (a total of 10 x 2048 tokens). The
using 1.4B model trained Wikipedia. In Table 7 we
Both the variational and L distances between a one-hot distribution and distribution which is uniform on tokens are at least 1 Thus, whenever an LLM has at least two roughly valid options, we expect one one-hot distribution be at least of distance 0.5 from the LLM prediction.
18

---

slope -0.06; R² 0.45
slope 1.81, 12a 0.53
1.0
0.8
0.6
0.6-
0.4-
0.2-
0.0
0.0
106
110
"T>
'10
20+
model varience
(i)
stope = 00.02, 0.21
slope 1.27, 0.77
0.7
0.6-
0.8
modgivarrnnic
0.5-
ogstmme ahowaee
0.5
8.4-
10c
10
10a
16+ 10
0.0
6.1
0.2
6.3
0.4
0.5
0.6
0.7
varience
(c)
(d)
Figure 9: Wikipedia 6-grams. Every point in the above plots represents 6-gram context. Shaded regions are plots obtained by bucketing along the x-axis and computing one standard deviation within the mean along the y-axis. Slope and Re² values of plots given by their axes. Optimal rule distances and model variances are computed with respect to five model runs. (a): d(p(1 C)2 Pean (f(C)) vs count of C. (b): d(p(t) ((),,, Phan (6 C)) model variance.
with respect the linear fit of the data
(c): model variance vs count of C. (d): similar to (b) but now the y-axis is optimal rule distance of Model size: 160M.
the optimal rule from R. Rumffix
Table 4: Optimal rule distance (TinyStories, variational distance). We look at the average optimal rule distance with LLM predictions for rules of varying strength and maximum context length M. We compute this average over each token prediction from 100 random TinyStories validation stories (around 22K tokens total). Model size: 160M.
ruleset context length
2
3
4
5
6
7
Ral
0.738
0.597
0.507
0.434
0.37
0.316
0.274
M
subgram
0.738
0.598
0.513
0.449
0.399
0.362
0.335
Riuffi backoffMr
0.738
0.598
0.519
0.465
0.425
0.399
0.381
0.738
0.606
0.539
0.503
0.482
0.472
0.466
top-1 accuracy when using optimal rules from Rell and the L distance for rule selection is 67.7%. As with TinyStories, we see significant gains in accuracy when we increase rule strength. Achieving the number 67.7% (versus the corresponding 78.9% number for TinyStories from Table perhaps a surprisingly a high score, the result of two competing factors: on the one-hand. Wikipedia is more complex dataset (which makes prediction harder), while on the other hand, the training data has more --grams and thus more rules. Our model achieves 54.9% top-1 accuracy on the 10 holdout Wikipedia chunks (Table I2 which is substantially lower than the top-1 accuracy of the optimal rule.
19

---

Table 5: Top-1 accuracy of optimal rule (TimyStories, - distance). The analogue of Table but
with L distance instead of variational distance for selecting the optimal rule. Model size: 160M.
ruleset / context length
2
4
6
R.
30.0
45.1
55.0
63.2
69.6
75.0
78.9
R Subbram
30.0
44.7
53.5
60.4
65.1
68.5
71.2
R Raulix
30.0
44.5
52.6
58.0
61.4
63.6
65.2
backoff M
30.0
42.5
48.7
52.7
54.6
55.9
56.7
Table Optimal rule distance (TinyStories, L distance).
The analogue of Table but with 7
distance instead of variational distance. Model size: 160M.
ruleset / context length
Rall
0.557
0.443
0.371
0.309
0.253
0.207
0.170
Rubhgrm
0.557
0.444
0.376
0.322
0.28
0.248
0.225
Raulli
0.557
0.446
0.383
0.338
0.305
0,282
0.267
backoff M
0.557
0.456
0.407
0.385
0.378
0.379
0.382
D.3 Model Scaling
In this section, present results about how rule approximation changes with model size. For both TinyStories and Wikipedia, we train models of size 160M, 420M, and 1.4B for one epoct 20
In Tables 11 and 12] there is clear trend towards improved model performance with scale: we obtain lower cross entropy loss, higher top-1 accuracy, and lower model distance to the ground truth distribution regarded as one-hot distribution 21 Note that for the latter, distance from model predictions to the ground truth distribution the same with respect to the variational or - distance and is given by p where p is the probability assigned by the model to the ground truth.
On the other hand, entries in Tables 20 are much more modest (i.e. are more stable) by comparison. They also show mixed results, with d results worsening but some variational distance results slightly improving with scale (for large context length rules). We leave more thorough investigation of how model scale affects approximability by N N-gram nules to future work.
20 measuring the changes rule approximation with scale
Sinne the 1.4B starts showing signs of overfitting around 4 epochs on TinyStories, we train models for 1 epoch in this section unlike epochs elsewhere.
"I would be more proper to aggregate statistics over the holdout set to compute ground truth distribution that takes into the account the relative frequencies of the next token given the context. However, since most contexts will be unique, this more refined computation will not affect the corresponding result much.
20

---

Table 7: Top-1 accuracy of optimal rule (Wikipedia, - distance). We look at the average top-1 accuracy between optimal rule and LLM predictions for rules of varying strength and maximum context length. We compute this average over each token prediction from 10 holdout Wikipedia sequences each consisting of 2048 tokens. Model size: 1.4B.
ruleset / context length
1
2
3
4
5
6
7
24.3
39.7
49.8
55.5
60.3
64.3
67.7
M
R subgram
24.3
39.2
48.3
52.7
55.5
57.6
59.0
M
MM
24.3
38.8
47.1
50.3
51.5
52.3
52.7
backoff
24.3
36.8
42.9
43.9
43.7
43.8
43.9
Table Optimal rule distance (Wikipedia, L distance). We look at the average L distance
between optimal rule and LLM predictions for rules of varying strength and maximum context length. We compute this average over each token prediction from 10 holdout Wikipedia sequences each consisting of 2048 tokens. Model size: 1.4B.
ruleset context length
5
6
7
RM
0.48
0.369
0.29
0.237
0.202
0.173
0.150
RM
subbrram
0.48
0.371
0.295
0.249
0.226
0.209
0.198
Rafffi
0.48
0.375
0.303
0.265
0.250
0.242
0.238
backoff
0.48
0.394
0.359
0.368
0.387
0.398
0.405
Table 9: Top-1 accuracy of optimal rule (Wikipedia, variational distance). We look the average top-1 accuracy between optimal rule and LLM predictions for rules of varying strength and maximum context length. We compute this average over each token prediction from 10 holdout Wikipedia sequences each consisting of 2048 tokens. Model size: 1.4B.
ruleset / context length
2
4
6
Ra
24.3
39.2
48.8
54.4
58.5
61.9
65.0
Rubgrrm
24.3
39.0
47.9
52.3
54.9
56.8
58.3
Rafffix
24.3
38.7
46.9
50.3
51.5
52.4
52.8
backoff
24.3
36.8
42.9
43.9
43.7
43.8
43.9
Table 10: Optimal rule distance (Wikipedia, variational distance). We look at the average varia- tional distance between optimal rule and LLM predictions for rules of varying strength and maximum context length. We compute this average over each token prediction from 10 holdout Wikipedia sequences each consisting of 2048 tokens. Model size: 1.4B.
ruleset context length
2
3
4
5
6
7
0.768
0.635
0.543
0.484
0.446
0.413
0.388
M
R
subgram
M
0.768
0.636
0.549
0.498
0.472
0.453
0.440
R
0.768
0.638
0.556
0.513
0.497
0,488
0,483
M
backoff b
0.768
0.656
0.609
0.597
0.598
0.599
0.600
Table 11: TinyStories metrics. How average cross entropy loss, top-1 accuracy, and model distance the ground truth scale with model size holdout set of 100 stories.
model size
eval loss
eval acc
eval distance
160M
1.43
63.2
0.485
420M
1,28
65.9
0.452
1.4B
1.22
66.9
0.439
21

---

Table Wikipedia metrics. How average cross entropy loss, top-1 accuracy, and model distance to the ground truth scale with model size on holdout set of 10 Wikipedia chunks.
model size
eval loss
eval acc
eval distance
160M
2.63
50.0
0.617
420M
2.43
52.3
0.590
1.4B
2.26
54.9
0.562
Table 13: Top-1 accuracy of optimal rule with model scale (TinyStories, variational distance). How top-1 accuracy the optimal rule varies with model size and rule context length. Optimal rule from is selected from R2 using variational distance.
model size confext length
2
4
6
160M
31.4
47.1
56.7
64.3
69.8
74.5
77.9
420M
30.7
45,9
55.5
63.3
69.2
74.1
77.9
1.4B
30.5
45.9
55.3
63.4
69.6
74.3
78.2
Table 14: Optimal rule distance with model scale (TinyStories, variational distance). How optimal rule distance varies with model size and rule context length. Optimal rule is selected from Ry using variational distance.
model size context length
2
3
4
5
160M
0.692
0.545
0.46
0.398
0.347
0.306
0.275
420M
0.711
0.566
0.479
0.411
0.355
0.310
0.274
1.4B
0.718
0.574
0.486
0.417
0.359
0.311
0.274
Table 15: Top-1 accuracy of optimal rule with model scale (TinyStories, L distance). How top-1 accuracy of the optimal rule varies with model size and rule context length. Optimal rule is selected from Ry using _ distance.
model size context length
2
4
6
160M
31.4
47.5
57.5
65.2
71.4
76.1
79.6
420M
30.7
46.3
56.3
64.2
70.5
75.3
79.2
1,4B
30.5
46.2
56.0
64.1
70.5
75.3
79.3
Table 16: Optimal rule distance with model scale (TinyStories, L distance), How optimal rule distance varies with model size and rule context length. Optimal rule is selected from R2 using L distance.
model size
context length
2
3
4
5
7
160M
0.482
0.368
0.301
0.248
0.204
0.169
0.141
420M
0.511
0.398
0.329
0.272
0.223
0.184
0.153
1.4B
0.522
0.408
0.338
0,280
0.230
0.189
0.157
Table 17: Top-1 accuracy of optimal rule with model scale (Wikipedia, variational distance). How top-1 accuracy of the optimal rule varies with model size and rule context length. Optimal rule selected from Rilll using variational distance.
model size / context length
2
4
5
6
160M
25.9
40.8
49.5
54.2
57.7
61.0
63.8
420M
24.7
39.8
49.0
54.2
58.1
61.6
64.3
1.4B
24.3
39.2
48.8
54.4
58.5
61.9
65.0
22

---

Table 18: Optimal rule distance with model scale (Wikipedia, variational distance). How opti- mal rule distance varies with model size and rule context length. Optimal rule is selected from Ry using variational distance.
model size context length
2
3
4
5
160M
0.737
0,606
0.527
0.477
0.445
0.418
0.397
420M
0.753
0.621
0.534
0.480
0.445
0.414
0.391
1.4B
0.768
0.635
0.543
0.484
0,446
0.413
0.388
Table 19: Top-1 accuracy of optimal rule with model scale (Wikipedia, _ distance). How top-1 accuracy of the optimal rule varies with model size and rule context length. Optimal rule is selected from Rill using - distance.
model size / context length
2
4
6
160M
25.9
41.2
50.4
55.9
60.4
64.4
67.8
420M
24.7
40.3
50.0
55.7
60.4
64.3
67.7
1.4B
24.3
39.7
49.8
55.5
60.3
64.3
67.7
Table 20: Optimal rule distance with model scale (Wikipedia, - distance). How optimal rule distance varies with model size and rule context length. Optimal rule is selected from R using L distance.
model size context length
2
3
5
160M
0.429
0.321
0.253
0.208
0.179
0.154
0.135
420M
0.455
0.346
0.271
0.222
0.190
0.163
0.143
1.4B
0.480
0.369
0.290
0.237
0.202
0.173
0.150
23

---

Predictions
(tranformmr rule)
Ground bruth Rule distance
Rulc context
count
<805>
(=B0S=1)
2118436
Once
(<8055>) (Once)))
1426581
upon
[KB05H:: "Once; upon")
1258475
upar",
time
P'uport. a, time?
1258881
('Oncet upent, timee 1)
976045
there
('upont as "time:
30487
Paat timel (1)
29050
big
Paa: Uime 15 at a. big')
7021
('tmmet 5.
bigg rorest)
(ttme::
there
(' "forest. 11/ "there')
2725
('igg "forett, 1V there: (ived)
966
('alg:" "frrett
Ittle
(.big -M)
251
(. (e
9748
'int
named namedd
(h Ten Toc. ernst named")
236
Deroad mnmeed
emy
Ponmmed: toxy!1
Perost (namee))
237
(o
Poay: meyy)
Wa2 loved
Pory "loved")
to
('lowed; hel
546806
(llovdd dlmbb)
tees She
('loved); tot. dimb) 1. (She")
111
would, climbed
climbed
('loved) 'tot dimbi Shee. dimbedf
('clmmr, "Shee ciimbed
rokks
P'llmer, V. Sheel" climbed trese)
('She,, "llmbed "rocks)
('trees: rocket
137
ovch
hill
Io- (hlls)
('twwed 11.1 and NNI,
One St11
P52 aand, Hille 15, "Onee' day's
DT. On.," day!
717085
en R.
('day' 'RI
any over
('day'. RR, rwey!!
was
founn
Poay' (oondd))
2
foundd (er)
14301
unusual, old
foonnd
pand,
hill
founet lani ley. (hil)
She.
thought. was never
Dleyl" Shel, hedf!
(had: nevert
71695
(HB. she, 'nevert" smen)
nnverr anyyhingg
like
(hadd seeni anything" (ka))
('She, hadt, 'never; seen, (t))
567
Paayyhhing,
Laaythingg lBke'. beforu.
0.25 0:50
Figure 10: Rule selection for a TinyStories heldout sequence using R Raubgram Analogous to Figure but with optimal rule chosen from R, suhgram instead of R. Model size: 160M.
D.4 Rule Selection
Here we supplement our example in Figure 5 by showing how the smaller rulesets Riuhhrrmm and R.sultix compare Figures and expected, the top1 accuracy between transformer predictions and optimal rule predictions decrease with smaller rulesets.
24

---

Predictions
(transformer rull)
Ground truth Rule distance
Rule context
count
<805>
(<B06=1)
2110438
Drcee
(=B055a) "Oncw))
1426581
upon
(x805-1 "Once) upon!)
time
C Cupoon a. 3immm
1258881
('Ocee// upeny lat timel
970069
there
Cupoon au 2ittime:
C...: timel
29850
smalll
bi
Paa:: Lime) 15
big)
7021
(immet -itt"tt bigt forest)
2623
there
C ('gg:
"frget forest, W. there?
2725
lived
C Hig formet W. theow, lived!
Cagg: "foret, W
lived, 80
C lieed 1at (h1)
41
In
0 (irr
9748
livedd aat, loc. forad")
41
nameed
feri fec. lemost nameet!
236
(wroa) "nameed R))
93
nay
nnmmed"."
nameet""" R. R.
11
Conyt 11' R9
nxy
Cony teyy))
WGS
leved
lovedt)
to
C loved:: 'holt
546806
looved: Mtal dlibb)
2524
1e84s
One.
She
lovedd: 'tol." diimb 11 She")
111
climbed
llveed: 'tol'" climbt 12 Shel. climeed)
32
15,
C'climbi, 11, 'Shee climbed trems
19
C Cclimbed;; Trees; V. rocks)
57
C'rcess W. rocks. 11
("rress rockss and
Nil
aalaand; (Nis
29
CNNIX !1)
2355
One
0.2/ard; HIWS (nne, day')
0.:1One, day! 1/3
717085
xhe
(U/R)
any, emy
O'day', V. /nay')
17
S5W
found
Cony: found")
found,
14301
arusaal, old
found:
pord
hill
C found:: lan, lky. (hil))
0.3
32885210
She.
thought, was
C. Shhr hadd)
97
never
C had, never!
71696
seur
C C. Shat had, "never, awan)
anything
had, seen: anything")
like
C (Shee hadt, 'nover""" seen; anything". lkke
1621
Shhee hadt, 'neveri ssenn, anything!." like
1453
anything. aayyhhnng (Bke'." it. befond, :*)
3577
0.25
Figure 11: Rule selection for TinyStories heldout sequence using Rzuffix, Analogous to Figure
5 but with optimal rule chosen from Reuffi instead of Rall. Model size: 160M.
We also ground our rule approximation on Wikipedia by providing two concrete examples in Figures 12 and [3]
25

---

Predictions trrmeroormer// rule]
Ground distaanc
context
count
front
9208196
of
51, and, tthe" 'front' "*]
Candd 1* "toes, "are")
long
61 andd toes' aare. (e)
web
Joined
(andd "" me, pertially".
1516
wt
Othel (") m. aaree (joined;
384
the
f'aret, my "jolned, "1, tthe
470
base
t'aret, ant "base]
706
basee 1 partially
32190
Mu (P)
29
3007
toon
Cbaase, Wy 'ten')
10
species
basse', Wy Tten', 'spocies')
have
(teent, species". have?
151
been
Cteen', "speciess have', +*]
151
recorded
(teent, "", recordedd)
150
Spapccss "econdedd; ()
South, Guyana
Spepccess
Guyana)
speciess boon: 19,
lin.
Guyanna 10 191.
The
recondedd 14,
(Bluet
headed, W
(Blue', 14 'and)
(hrr, "uueel
(white
71413
col. swallow
C-) * * swallow]
143
('swallow,,) 1:3
2449
Owhite', swallow, (M,
36
('hiiee, swallow, 1e (1)
36
(ssallow: m1 loct
48
hel
swallow: *1), loc),
48
PPy. lal. loct 18, (1)
32
on
C1 14 '9t. 1M Hy (Id, ton))
27
cyan
Py: (sl. m. ldd
35
Con', ryann (ole))
Uc
Con'. cyan? (tu, luet
22
O'eyant *1/a0
Colel, luct
3662
O'eyant, Mi BBlac?
Cceaant (n,,
and
(Ulack)
lared: swallow! swalloow ",
(Black, * laredt "swlloww
swalloww m,
C1 Py: loc!
27
0.2
Figure 12: Rule selection for a Wikipedia heldout sequence. Analogous Figure but with optimal rule chosen from R.ll and with variational distance replaced with the L metric for measuring distances between probability distributions. Model size: 1.4B.
26

---

Predictions (tranuformer rule]
Ground Rule
context
count
[
viido'))
game
( wes!
relcased
(
"drected;; by)
the
Michael
wast MMichael))
Michael,
wast, " by: !", Sal, 'oman')
wasi, 'directdd; ".
'and")
produced
Comon' prem/)
lered
[ Michaef, 1*: 10, prem:; (X)
18
(' anddd premm, (4)
7480
( and'd 'on,"CC
334
MT October
C' oni; CC) (M7)
720
(leredt M. "r/"/mm on]]
150
February
C' promt, (4) 14, (4, 1r, ont February) (llored 'ont, February, (*) ( oni; "February;" 1.
226
1429
51089
(MT) "1, February, "7,
C rebruary' '1"
C ont, "Fabnuar" "1 '1.
C February', 15),
(1) "", 121
(1)
5n
aga .
(0) (AC)
(MCC) cutt)
thh')
video
anding
(6) *: 'AC, (*)
011 AC) we mu of)
2
the
[ G. 'AC) 19, "the')
61
video
( the), eendnngg !", the (P)
2003
( cut) thhe, "" but))
25
because
C video", (e) because!!
93
C' out,; 'because," of)
689
C' oft ( videot "., lts't
19
suggestive
(' because', of', suggestivee)
18
nature
language
C' because", *, iistt language")
C Keith!!
1262
C' because"
his
C "uggesstvve,
audience.
( Kalth", ballss, "1. (0)
to
audience" 11
referring
( 1", referring)
( bellst, w.
the
referiing, him)
35
shooting
referring: 'him,,
( shooting:: 'the'l
25.70
video
video
( him')
114486
C tol, him'. aas)
6703
0.2
0.4
Figure 13: Rule selection for a Wikipedia heldout sequence. Analogous Figure but with optimal rule chosen from Rlll and with variational distance replaced with the L metric for measuring distances between probability distributions. Model size: 1.4B.
27

---

E
Broader Impacts
Large language-models are having significant impacts on society, due their use suestion-answer tools and natural language generators. A better understanding of such language models will only serve to improve their capabilities. Our work here presents steps towards fundamental understanding of language models, albeit in a small-scale regime far removed from those relevant for production systems. Given how far removed our work is from realistic datasets and use cases, we do not anticipate any direct negative broader impacts of our work.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims explicitly mentioned in abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations in the introduction (description vs explanation) and conclusion (N- (N-gram rules are certainly not the whole story).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA].

---

Justification:
We have no theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: YYs]
Justification: Yes, the experimental setup (architecture, training setup, dataset preparation) are described in detail in the main body and appendix.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
30

---

Answer: [No]
Justification: We do not release the code used to run our experiments (though there is nothing proprietary or novel about the model the training procedure, and both are described in detail). The datasets we use are publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc)
httpl//guuides/ooeeuubiieeeeee wot.ssubissiiooooooroooroo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips httpsscccpbblcc/gcccccooo /ttp//ddddee//eeubmiiimm SoreddeubmissionPPee Policy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
Yes, experimental settings are explained by dedicated sections in the main
paper and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [es]] (Partially)
Justification: Our Section 5 provides error bars and R² values. In other sections, only individual model runs are given.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
31

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Explained Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://arrr..cccoooooccccaaaaaaa
Answer: [Yes]
Justification:
Our experiments use small, public datasets and involve no sensitive material or
topics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We include a brief discussion in the Appendix of how our work contains no direct societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
32

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes, datasets used are referenced.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
33

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "m12zsZlYX4", "reviewer": "Reviewer_GxTz", "summary": "The authors use 160M parameter models trained on the TinyStories dataset (artificially generated short stories, 480M tokens, made up of \"vocabulary consisting of about 1500 basic words\") to study transformers by comparing their predictions to the predictions of n-gram models. \n\nThis leads to a few observations [quoted from the paper here]: \n1. (Approximation-Variance Tradeoff) We observe an “approximation-variance tradeoff\",\nwhich roughly states that next token LLM predictions that have low variance (across\ndifferent training runs) tend to be well-approximated by N-gram rules. (Section 5)\n2. (Curriculum Learning Dynamics) By grouping our N-gram rulesets in terms of complexity\n(as measured by the amount of context they use), we discover the various ways in which the\nlearning dynamics of LLMs implement a statistical type of curriculum learning, in which\neasier rules are eventually supplanted by more complex ones. (Section 6.1)\n3. (Overfitting Criterion) Based on our analysis of approximating LLM predictions by N-gram\nrules, we propose a simple and novel procedure for detecting overfitting of LLMs during\ntraining. The procedure makes no use of holdout data and it makes quantatively precise the\nintuition that overfitting corresponds to a model memorizing long context at the expense\nbeing able to generalize through making use of subcontext. (Section 6.2)\n4. (Approximation Strength) We study how well LLM predictions can be approximated by our\nN-gram rulesets, noting that significant gains in top1-accuracy occur as we increase ruleset\ncomplexity and diversity. We also visually ground these approximations with concrete\nexamples (Figure 5), which may form the basis for dataset attribution methods in future\nwork. (Section 7)", "questions": "1. is the Approximation-Variance Tradeoff true also for predictions that have low entropy?", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "LMs are everywhere but we don't really know how they work and how the learn. Figuring this out might lead to stronger, more efficient models. \nI usually don't like interpretability research because most methods employed just don't make sense-  but I *love* the approach taken by this paper of using n-gram models to analyze transformer models. These results seem straightforward but I'm pretty sure that this paper is the first to ever present them.", "weaknesses": "There's a huge weakness in this paper- they analyze extremely small (160M param) models trained on a total toy dataset (TinyStories). TinyStories is a very small dataset made up of short stories that were generated by an LM. The vocabulary in this dataset is limited to 1.5k basic words. \n\nAll of these things together mean that none of these results might transfer towards bigger, realistic LMs like LLaMA 3 70B. If this paper would have been written with LLaMA 3 70B as the model being used I would have argued for a strong accept, but because the models used here are so tiny I'm less excited about this contribution. \n\nSecond thing- the authors put out a lot of what seems like 'intermediate analysis'- observations they noticed, but they don't explain what the conclusion from that observation is or why it's interesting. For example fig 2. \n\nThird- why is the 'Overfitting Criterion' interesting? Is anyone overfitting their LMs? Would anyone need this in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time in reviewing our work and appreciating its novelty.\n\n*Scale*\n\nThe reviewer noted we only trained a small 160M model on TinyStories. Perhaps the reviewer overlooked that we also trained on Wikipedia using 1.4B models?\n\nLLaMa 3 70B would not have been an appropriate model to study for several reasons. First, the underlying training data is not public, so it is impossible to perform the n-gram analysis of our paper. Second, SOTA LLMs involve both a pretraining phase and various additional training steps on top. Our paper only focuses on the single pre-training step for an initial controlled study. Finally, our new results (see below) suggests scaling past to 70B might not be so informative given the current context length available for our n-grams.\n\nTinyStories under our tokenizer has 23K distinct unigrams (Fig 7) and so is not as trivial a dataset as suggested. Moreover, the simplicity of TinyStories can be regarded as a feature not a bug: we want a dataset whose “effective” context length is small when being probed by n-gram statistics (with n small due to computational limitations). A children’s story will intuitively have less context dependence than a Wikipedia article, since the latter may rely on facts much earlier in an article. The two extremes given by simplistic language for TinyStories on the one hand and high-quality language via Wikipedia on the other hand, we believe, are the appropriate extremes to consider for the initial validation of our work.\n\nThe reviewer’s question about scale prompted us to look into past experiments we did long ago on various model sizes which we can include in the paper revision (actual numbers will differ slightly since these older experiments had different train settings).\n\nExperiment 1: TinyStories \n\n| Model Size | Top-1 Acc (Ground Truth) | Top-1 Acc (Optimal Rule from $R_7$) | Optimal Distance (from $R_7$) |\n|---|---|---|---|\n| 160M | 68.5 | 79.0 | 0.164 | \n| 420M | 69.4 | 79.1 | 0.169 |\n| 1.4B | 70.3 | 79.2 | 0.170 |\n\nExperiment 2: Wikipedia\n\n| Model Size | Top-1 Acc (Ground Truth) | Top-1 Acc (Optimal Rule from $R_6$) | Optimal Distance (from $R_6$) |\n|---|---|---|---|\n| 160M | 51.5 | 63.6 | 0.163 |\n| 420M | 53.7 |63.9 | 0.171 |\n| 1.4B | 55.8 | 63.6 | 0.181 |\n\nThese results show larger models improve in performance (ground truth acc increasing on validation set), but they slowly depart in approximation from our n-gram rules (the distance to the rules slowly increases while the top-1 acc of the optimal rule plateaus). We conjecture this is happening because larger models are better able to make use of longer context when appropriate: this leads to noted increase in distance of predictions from rules using 6-7 tokens of context without impacting the top-1 acc between the rules too much. \n\nNevertheless, the stability of our n-gram results when scaling up the model size suggests that our results hold at scale and that we expect to see similar results across a wide range of models on large datasets.\n\n*Overfitting*\n\nWhether overfitting occurs in practice is, we believe, the incorrect perspective to take since it would, e.g., dismiss phenomena such as grokking. The significance of our overfitting criterion is the insight it gives into understanding generalization vs memorization (just like with grokking), which is a subject often discussed with informal intuitions instead of precise quantification. The fact that our overfitting criterion quantifies generalization vs memorization in a way that only uses the training set and has a simple explanation in terms of n-gram statistics is, in our opinion, a novel discovery.\n\n*Approximation-Variance (AV) for Low Entropy*\n\nThe AV phenomenon is also true for predictions that have low entropy! In particular, consider n-gram contexts that occur only once in the training data (so zero entropy for next-token distribution). We replot Fig 8(a,c), using only unique full-context (those starting with BOS) bigram contexts as Fig1(a,b) in the Author Rebuttal. Fig 1(a) shows how for such contexts, aside from some outliers, those with low model variance (x-axis) will have good rule approximation (low y-value) and vice versa. On the other hand Fig 1(b) shows that a frequency based analysis of which contexts lead to low model variance (needed for good n-gram approximation) leads to a poor fit. (Here the only nontrivial count available is the number of occurrences of the last token of the context and it can be very large and still lead to high model variance.)\n\nTo summarize, one significance of our AV result is that an n-gram context being rare (even unique) is not predictive of the model prediction deviating from the associated n+1-gram rule. Rather it’s the variance of the predictive distribution associated to the n-gram context which is correlated with approximation by the n+1-gram rule (and this variance can surprisingly be low even for count = 1). This is quite surprising and future work would be to understand what makes some unique n-grams have low model variance while others have high ones. This can be emphasized in the paper revision.\n\n*Intermediate Analysis*\n\nThe reviewer noted that there is “intermediate analysis” whose significance is not clear (e.g. Fig 2). We hope our answer to the reviewer’s question above partially addresses this concern. To summarize, Fig 2 and the AV results of Section 5 is meant to answer the question “When does a context result in an LLM prediction well-approximated by n-gram rules?” (Answer: Often those with low variance. Simple count based statistics will be much less predictive since rare contexts can be approximated while common ones may not well-approximated alike) whereas Sec 7 measures how often this occurs (78% on TinyStories). Sec 6 provides additional insights into how n-gram rules are being used during training / overfitting. We hope this makes the structure of the paper more clear and will make these points more explicit in the paper revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j0iH8Ckv36", "reviewer": "Reviewer_H4bx", "summary": "The authors use n-gram statistics and regular expression templates to study how well they describe the predictions of Transformers-based models. They craft rules that vary in context length and/or the number of marginalised context variables to predict the next word. They use their framework to study overfitting (and memorisation) of increasingly complex template rules. They discover a counter-intuitive phenomenon: longer n-gram rules can be less predictive of a model's behaviour than shorter; an insight they name model-variance trade-off.", "questions": "In order of importance:\n(major) Can you give a clear definition of model-variance in terms of predictive capabilities of the model and when compared to an n-gram rule?\n\n(major) Have you checked if there is a large drop in the variance of 7 vs. 8 grams in your dataset? I suspect that causes the 7-gram rules to be optimal and not the model-variance trade-off. In other words, the variance of 8-grams in your dataset is so large (because you don't have enough data), that the architecture you use cannot approximate it.\n\n(minor) What if the optimal rule you find only correlates with a model's behaviour (e.g., due to the size of the dataset)? Can you give some evidence that a model is actually using n-gram rules to predict the next token?\n\n(minor) Eq. 10: what is i? Is p(t=v_i | C), with v_i the i-th token in the vocabulary, or the i-th run of the model?\n\n(minor) Line 111, the expression +-*+ should produce C_{-5}*C_{-1} and not C_{-4}*C_{-1}, or am I missing something in your notation? Is it for the left padding you mention earlier?\n\n(minor) Eq. 6 (left hand side): why don’t you have C_{-4} at the denominator?", "limitations": "See previous points.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The idea of defining templates that apply both to the data distribution and the model's generation is good and sound.\nI appreciate the idea of having a mathematical methodology as it states clearly what is the objective and how rules are defined (despite a few things I do not fully understand and I reckon may be wrong; see next sections).\nFindings are noticeable: 7-gram rules better approximate a model's behaviour than 8-grams (but please refer to the next section for. a caveat on this finding).\nThe model-variance explanation of why some rules are better than others is intriguing (but see weaknesses).", "weaknesses": "I am concerned about the evaluation, in particular Eq. 10. You measure how closely the dataset adheres to the template rules and compare it to your model’s behaviour. With such a small dataset, the fact 7-gram rules better approximate the distribution of data may be caused by a considerable drop in the overall frequency (and thus, variance) of 8-grams (vs. 7-grams). See a question about that.\nIn summary, my biggest concern is whether the best-rule is identified by the model-variance trade-off or the intrinsic larger variance of 8- vs. 7-gram rules (i.e., 8-grams are more difficult to predict because you don't have enough data, so the 7-gram is optimal). With larger datasets and different models, results can vary.\n\nIn fact, another major concern is that you only have two datasets and one model to prove your hypothesis.\nFurthermore, it is not clear if you take inspiration from Chinchilla's architecture (it seems to me you do not use a pre-trained model). Otherwise, it would be nice to test this hypothesis with smaller, purely next-word-prediction trained models (even gpt-2 or Pythia would be good).\n\nOther concerns (in descending order of importance):\nFigure 2: low R-squared may mean the regression failed and not lack of \"correlation\". Furthermore, you mention 7-grams but some plots are for 8grams (see y-axis of figs (a,b)). While I understand why, the plot is named 7-grams, so I was a bit confused at the beginning. It's better to show less in this case or make it clear also in the caption that the top-plots refer to 8grams.\n\n(minor) Equation 10 seems to me wrong: p and q are distributions, you can’t subtract them (unless i stands for p(t=v_i |C), but that has to be clarified).\nIf not, probably you want to say something like Divergence(p || q). On a side note, I think this is one of the cases where an asymmetric rule makes sense. You want to measure the amount of “information” a model lacks to turn p (its prediction) into q (the ground truth).\n\n(minor) I am a bit confused by the notation in Section 4 (see questions, though the general idea is clear enough).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time in reviewing our work and appreciating the soundness of using n-gram statistics to understand LLMs.\n\nRegarding the 8-gram model vs rules $R_7^{suffix}$ or more generally $R_7$ using up to 7 tokens of context: We are not entirely sure we fully understand the reviewers concern, but we provide some details which we hope addresses our interpretation of them:\n\na) Note that the 8-gram model (which uses all 7 of the most recent tokens of context, when they occur in the training data) is one rule among the many in the ruleset $R_7^{suffix}$. Hence by definition, $R_7^{suffix}$ outperforms an 8-gram model because it has many more templates with which to optimize when comparing with an LLM next-token prediction.\n\nb) For our Figure 2 involving 7 tokens of context, we believe the reviewer is asking whether there is some simple phenomenon like having high count k-grams in the context that is “causing” the LLM to rely on such k-grams (k < 8) instead of the 8-gram model when the count of corresponding 8-grams is low.\n\nThis is certainly not the case! Please see Fig 2 in the Author Rebuttal pdf. Especially in Fig 2(b) we see that across all settings in which the optimal rule is a k-gram rule 2 <= k <= 8, there are always 7-grams in which the corresponding 8-gram model has several thousand instances (all 7 curves in Fig(b) have maximum value at least several thousand). Likewise Fig 2(a) suggests there isn't a simple count-based reason for when the 8-gram rule is optimal versus the 7-gram rule is optimal (the corresponding pink/brown curves are qualitatively similar, showing that the associated n-gram distributions are similar for both cases, 2 <=n <= 8).\n\nIn fact, the point of our Approximation-Variance relation is that we failed to find any simple count-based method of selecting optimal n-gram rules (of the type the reviewer is suggesting). The lesson is that knowing *which* rule is selected is hard, but that knowing *some* good rule exists can be more easily guaranteed (by Approximation-Variance, when the context has model prediction with low variance). This important finding can be emphasized in the revision. (See also Section C.3 and Figure 8 for related insights.)\n\n“Can you give a clear definition of model-variance in terms of predictive capabilities of the model and when compared to an n-gram rule?”\n\nIf the question is whether we know of a way to characterize model variance other than its definition, then the answer is we do not know - it is a genuine mystery! Contexts which occur only once (so next token distribution has zero entropy) can have both high and low model variance (see the large vertical spread in Fig 2(c) at count = 1). It is an open problem to be able to explain such wide-ranging behavior. (See also comments in general Author Rebuttal.)\n\nThis question/puzzle can be emphasized as a future direction of work. \n\nRegarding choice of models, observe that GPT-2 is 1.5B and does not have a public dataset (rendering n-gram analysis unavailable). While Pythia's dataset is available, it is very large for our current n-gram analysis. Our model sizes range from 160M to 1.4B (within the range of the smaller Pythia family). Thus our models are within the \"smaller models\" range the reviewer suggested?\n\n*Minor questions / notation*:\n\nFig 2: The y-axis is correctly labeled 8-gram because we are comparing the *8-gram rule* prediction with the transformer prediction on a *7-gram context*. (This is a constant off-by-one source of headache with n-grams: the n-gram rule uses n-1 tokens of context)\n\n“What if the optimal rule you find only correlates with a model's behavior (e.g., due to the size of the dataset)? Can you give some evidence that a model is actually using n-gram rules to predict the next token?”\n\nCould the reviewer please clarify what is meant by “only correlates with a model’s behavior” mean? A rule can describe a model’s behavior in that it provides a predictive probability distribution that is close to the model’s predictive probability distribution. \n\nFor the second question, as noted, we only use rules to describe predictions, not explain them. Our analysis is a black-box analysis studying the “form” of prediction, not one that uses model internals to confirm that they “use” (i.e. “select”) such rules (this is the “form vs selection” distinction in the paper introduction). It is analogous to a Chinese Room Argument situation: we are able to describe the form of the outputs but have no claim on the inner workings. We believe followup work using mechanistic interpretability tools could address the problem of rule usage/selection. Nevertheless, we want to stress that part of the our novelty results is to be describe predictions in terms of n-gram rules as often as we can (78% in a certain sense on TinyStories).\n\n“Eq. 10: what is i? Is p(t=v_i | C), with v_i the i-th token in the vocabulary, or the i-th run of the model?”\n\nIt is p(t=v_i | C), with v_i the i-th token in the vocabulary. The definition of variational distance in Eq. 10 involves the distance between two probability distributions regarded as vectors indexed by i. So for probability vectors arising from language models, i indexes the vocabulary. And so yes, we can subtract probability distributions (because they are vectors and we can subtract vectors).\n\n“Line 111, the expression +-*+ should produce C_{-5}*C_{-1} and not C_{-4}*C_{-1}, or am I missing something in your notation? Is it for the left padding you mention earlier?”\n\nThe line there is correct. Parsing +-*+ from right to left, the “+” keeps C_{-1}, the * yields a *, the - drops the C_{-3}, and the final + keeps the C_{-4}. Padding means we drop all remaining tokens to the left (hence we drop C_{-5}).\n\n“q. 6 (left hand side): why don’t you have C_{-4} at the denominator?”\n\nApologies, this was a bad typo! There should absolutely be a C_{-4} in the denominator (just like on the right hand side).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qKZQf3338o", "reviewer": "Reviewer_BciX", "summary": "The paper studies how transformer-based large language models (LLMs) use context when predicting the next token by approximating these predictions with N-gram-based statistical rules. The authors propose a method to describe transformer predictions using simple N-gram rules and study how well these rules approximate the predictions. They claim their key findings include a new method to detect overfitting without a holdout set, insights into the progression from simple to complex statistical rules during training, a criterion for when transformer predictions align with N-gram rules, and an understanding of how well transformers can be approximated by increasingly complex N-gram rulesets. The experiments (primarily carried out on the TinyStories dataset and validated on Wikipedia data) seem provide possible insights into the statistical nature of LLM behavior.", "questions": "- How do you plan to address the computational complexity associated with selecting the optimal N-gram rule for each context?\n- Do you have any plans to transition from descriptive approximations to more explanatory models that can predict why certain rules work?\n- Have you considered additional evaluation metrics that might capture other aspects of model performance and approximation quality?", "limitations": "- The computational overhead required to apply and test the N-gram rule sets at inference time could be significant.\n- The proposed methods might not easily adapt to new or evolving datasets without substantial re-calibration or re-training, limiting their long-term applicability in dynamic environments\n- While N-gram rules provide a way to approximate transformer behavior, the results might not always be easily interpretable by humans.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed method for detecting overfitting without needing a holdout set is new and interesting for optimization applications.\n- The paper includes visualizations and concrete examples.\n- Although focused on specific datasets, the methods and insights could potentially be scaled to other domains.", "weaknesses": "- The study provides descriptive approximations without offering explanations into why certain rules work, not going deep enough in understanding the transformer behavior.\n- The paper doesn't properly explore how fine-tuning on different datasets might affect the effectiveness of the proposed methods.\n- The study mainly considers context lengths of up to seven tokens, which may not fully capture the long-range dependencies that transformers are capable of handling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and concerns.\n\n*Weaknesses*\n\n1. “The study provides descriptive approximations without offering explanations into why certain rules work, not going deep enough in understanding the transformer behavior.”\n\nWhile it is true we do not provide explanations (as explicitly mentioned in the paper), we believe our work provides a novel complement to such efforts. For instance, there is a growing body of work to explain very particular LLM functions, say using circuits (e.g. Indirect-Object-Identification or copying). It may be difficult, if not impossible, to try to explain the myriad of heterogeneous behaviors arising from n-gram templates, each with their own mechanisms, within the scope of a single paper. Rather the perspective of our paper is to give a broad analysis in terms of description (what we call “form” in the introduction) that later can be used to guide research into explanation (what we call “selection” in the introduction).\n\nIn other words, before looking for explanations, it is useful to have a rich set of descriptions (as much as is feasible) first. Example: it may be useful to describe the possible different weather patterns before developing the underlying physics that explains the different weather patterns. \n\n2. “The paper doesn't properly explore how fine-tuning on different datasets might affect the effectiveness of the proposed methods.”\n\nThis is true but we believe that is the scope for followup work. It would muddy the waters of n-gram analysis to have multiple datasets and sequential training, since there would be ambiguity about how to combine n-gram statistics from multiple datasets. In fact, we think a very interesting followup paper would be precisely to explore such questions (e.g. when fine-tuning, are n-gram statistics of the new dataset used to override old ones or is some mixture of statistics happening?). But for laying groundwork analysis, it is most appropriate to focus on a single dataset.\n\n3. “The study mainly considers context lengths of up to seven tokens, which may not fully capture the long-range dependencies that transformers are capable of handling.”\n\nWith more engineering and compute it is true we could tabulate n-grams with larger n. And by definition, we could get better approximation because we have more n-grams available. But we believe we already have shown good approximation by n-grams rules for up 7 tokens of context: is there anything the reviewer wishes to see beyond guaranteed improved approximation? \n\n*Questions* \n\n1. “How do you plan to address the computational complexity associated with selecting the optimal N-gram rule for each context?”\n\nFor suffix based N-gram rules, we discovered after setting up our N-gram database that there is a suffix array structure which makes querying N-grams very fast and scalable, e.g. an N-gram querying API is available for datasets of order 10^8-10^9 tokens (https://huggingface.co/spaces/liujch1998/infini-gram). This data structure can be used to scalably find optimal N-gram rules for the suffix rules. For subgram rules and marginal rules, some other clever data structure may enable quick N-gram querying but we have not invested effort into this direction yet.\n\n2. “Do you have any plans to transition from descriptive approximations to more explanatory models that can predict why certain rules work?”\n\nYes but that is not within the scope of the present paper. The situation is analogous to the Chinese Room Argument: we are able to describe the form of the outputs but have no claim on the inner workings. We believe followup work using mechanistic interpretability tools could address the problem of rule usage/selection. Nevertheless, we want to stress that one of our remarkable results is to be describe predictions in terms of n-gram rules as often as we can (78% in a certain sense on TinyStories).\n\n3. “Have you considered additional evaluation metrics that might capture other aspects of model performance and approximation quality?” \n\nAs this is a very open-ended question which we are uncertain how to answer, but we provide two details here which might be useful to the reviewer:\n\nWe varied the choice of metric to choose the optimal rule by choosing the $L^\\infty$-norm for Wikipedia. The same qualitative picture emerges and we saw no drastic change in the numbers. \n\nWe also tried forming some simple predictive models using the rules (e.g. using simple statistics to decide which to use) but were not successful. This is why we limit ourselves to “descriptions” since selection/”explanation” is difficult. Nevertheless, prior to our work, it was not even clear or quantified to what extent n-gram rules describe/approximate LLM predictions. \n\n*Limitations*\n\n1. “The computational overhead required to apply and test the N-gram rule sets at inference time could be significant.”\n\nYes, though for suffix rules, the method is known to be scalable, see above. \n\n2. “The proposed methods might not easily adapt to new or evolving datasets without substantial re-calibration or re-training, limiting their long-term applicability in dynamic environments”. \n\nWe’re unsure what the baseline here. Isn’t the above a weakness for nearly the whole of supervised learning? When a new dataset arrives, one almost always has to retrain or do some kind of adaptation accordingly.\n\n3. “While N-gram rules provide a way to approximate transformer behavior, the results might not always be easily interpretable by humans.”\n\nN-gram models are among the simplest, interpretable models (since they are based on simple frequency-based statistics). Does the reviewer not find the descriptions provided in the “Rule context” column in figures such as Figure 5 rather interpretable?", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their valuable feedback. Attached is a pdf of Figures 1 and 2 relevant to the individual author rebuttals. Some high level comments to reiterate some overlapping feedback:

1) We have substantial evidence that our results hold with scale. This is justified via additional experiments noted in the response to Reviewer #1.
2) A key message from our Approximation-Variance result is that simple count/entropy-based criteria for which contexts lead to LLM predictions being well-approximated by n-gram rules do *not* seem to be readily available (this is what Fig 1 and 2 in the rebuttal pdf show along with the responses to Reviewer #1 and #2, in addition to Fig 2 and 8 of the main paper). Indeed after much tinkering, the main correlation we identified for being well-approximated by n-gram rules (as measured by low optimal distance to rules) was having low model variance. It is an interesting open question as to whether this latter property has some simpler characterization and we will leave this to future work. (This is intuitively a difficult problem to address, and is closely related to other works that study which training examples are hard or end up being memorized/forgotten by neural networks, e.g. [1] and [2]. To the author's knowledge, there is no systematic understanding of which training examples are hard / easily memorized.). To reiterate, such difficulties is why our paper takes a descriptive approach to n-gram rules rather than explanatory one, because simple hand crafted features (like counts, entropy) which would provide simple explanations do not seem to go very far.

[1] Toneva et al. An Empirical Study of Example Forgetting during Deep Neural Network Learning. ICLR 2019. 

[2] Carlini et al. Quantifying Memorization Across Neural Language Models. ICLR 2023.

Meta-review: SUMMARY

How well do n-gram rules from statistical language models approximate the predictions of transformer-based neural language models when they are built/trained off the same dataset? The paper shows that high-confidence LLM predictions tend to be well-approximated by n-gram rules and that LLMs learn simple n-gram rules before they learn more complex ones. They further use their methods to detect when an LLM has overfitted to the training data.

REASONS TO ACCEPT

Reviewers really like how the authors use classical methods from NLP  to try and understand modern LLMs' behaviours. The results are intriguing, and there are natural extensions for impactful future work. 

REASONS TO REJECT

The "LLM" used by the paper is actually tiny: 160M parameters. It is unclear whether the results will be the same/different if the methods were evaluated on a much larger language model trained on a much larger dataset. It is also unclear how the methods in the paper could be efficiently scaled up to this more realistic "large" setting.

CONCLUSION

Overall, the ideas in this paper are worth sharing at NeurIPS, and I look forward to future work which addresses the scaling challenge.
Decision: Accept (poster)