Lexinvariant Language Models
Authors: Qian Huang
Eric Zelikman
Sarah Li Chen
Yuhuai Wu
Gregory Valiant
Percy Liang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Large Language Model
in-context learning
pretraining
TL;DR: We study a language model without stable token embedding and show that it converges to standard language model given a sufficiently long context, implicitly performs in-context deciphering, and has better in-context reasoning performance.

Abstract: Token embeddings, a mapping from discrete lexical symbols to continuous vectors, are at the heart of any language model (LM). However, lexical symbol meanings can also be determined and even redefined by their structural role in a long context. In this paper, we ask: is it possible for a language model to be performant without \emph{any} fixed token embeddings? Such a language model would have to rely entirely on the co-occurence and repetition of tokens in the context rather than the \textit{a priori} identity of any token. To answer this, we study \textit{lexinvariant}language models that are invariant to lexical symbols and therefore do not need fixed token embeddings in practice. First, we prove that we can construct a lexinvariant LM to converge to the true language model at a uniform rate that is polynomial in terms of the context length, with a constant factor that is sublinear in the vocabulary size. Second, to build a lexinvariant LM, we simply encode tokens using random Gaussian vectors, such that each token maps to the same representation within each sequence but different representations across sequences. Empirically, we demonstrate that it can indeed attain perplexity comparable to that of a standard language model, given a sufficiently long context. We further explore two properties of the lexinvariant language models: First, given text generated from a substitution cipher of English, it implicitly implements Bayesian in-context deciphering and infers the mapping to the underlying real tokens with high accuracy. Second, it has on average 4X better accuracy over synthetic in-context reasoning tasks. Finally, we discuss regularizing standard language models towards lexinvariance and potential practical applications.

Lexinvariant Language Models
Qian Huang'
Eric Zelikman' ezelikman stanford. edu
Sarah Li Chen
qhwang@cs.c stanford. edu
sachen&stanfore edu
Yuhuai Wu
Gregory Valiant gvaliant@cs. stw.oord..taaado...oooomm edu
Percy Liang'
yuhuai@cs.
edu
pliang@os stanford. edu
Stanford University Google Research
Abstract
Token emheddings, a mapping from discrete lexical symbols to continuous vectors, are at the heart of any language model (LM). However, lexical symbol meanings can also be determined and even redefined by their structural role in a long context. In this paper, we ask: is possible for a language model to be performant without any fixed token embeddings? Such a language model would have to rely entirely on the co-occurence and repetition of tokens in the context rather than the priori identity of any token. To answer this, we study lexinvariant language models that are invariant to lexical symbols and therefore do need fixed token embeddings in practice. First, we prove that we can construct a lexinvariant LM to converge to the true language model a uniform rate that polynomial terms of the context length, with a constant factor that is sublinear in the vocabulary size. Second, to build lexinvariant. LM, we simply encode tokens using random Gaussian vectors, such that each token maps to the same representation within each sequence but different representations across sequences. Empirically, we demonstrate that it can indeed attain perplexity comparable to that of a standard language model, given suffi- ciently long context. We further explore two properties of the lexinvariant language models: First, given text generated from substitution cipher of English, it implicitly implements Bayesian in-context deciphering and infers the mapping to the under- lying real tokens with high accuracy. Second, it has average 4X better accuracy over synthetic in-context reasoning tasks. Finally, we discuss regularizing standard language models towards lexinvariance and potential practical applications.
Introduction
language processing systems rely on stable lexicon, which assumes that a token (a word or subword such as tree) has consistent contribution to the meaning of text (though of course this meaning mediated by context). In neural language models (LMs), this contribution the token embedding, which stably maps each token into continuous vector [21, 16, 17, 7, 6]. However, in real language, a token's 's contribution might be determined by its structural role; in math and code, novel variable names are arbitrarily defined to carry new meaning, and poems such as Jabberwocky exploit humans' lexical flexibility in interpreting novel words such as vorpal. Besides standard language understanding, this lexical flexibility also correlates with stronger in-context reasoning performance. For example, GPT-3 [6] and other large language models that demonstrate high lexical flexibility show strong performance tasks involving in-context reasoning
concepts and rules.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Transformer
P("a big banana") =
p cop c
p( lan lomomo")
C 1000-Co- cekek
(a) Lexinvariance
Random Gaussian Embedding
e cop
(b) Lexinvariant Language Model
Figure Definition (a) and construction (b) of lexinvariant language model
Motivated by the above, we ask whether we can push this flexibility to the extreme: can we build lan- guage model without any stable lexical mapping? To this end, we formulate and study such lexinvariant language models. We define lexinvariant language model as language model that assigns the same probability to all lexical permutations of sequence. Formally, we define a lexical permutation и to be a one-to-one mapping of set of lexical symbols onto itself. Then the lexinvariant language model is defined as language model over the symbol sequence un with the following property:
p(
VI
For example, a lexinvariant language model (whose vocabulary is letters and space) should assign the same probability to the phrase "a big banana" as "e cop cekeke" because the two are the same up the permutation = (a:e,b: c, :...:,..""" ..... (Figure la).
The central question is: how well can lexinvariant language models predict the next token given an increasingly long context? We find the answer is almost well as standard language models, both theoretically and empirically. This rather surprising given that lexinvariance seems like a strong limitation (a model doesní know what any individual symbol means!) However, the intuition is that given longer contexts, a lexinvariant model can both infer the latent permutation и (lazily) up to whatever ambiguity is present in the language model, and do the standard next word prediction task jointly.
Theoretically, we prove that constructed lexinvariant language model can converge to the true language model as the context length increases -tat is, the average L1 distance between the predictions of the two models decreases with a convergence rate of O (4)²). where T is the length of the context and is the vocabulary size, and where the big-O -O notation hides polylogarithmic factors of dl and T and an absolute constant that is independent of the language model.
Empirically, we train a lexinvariant LM by replacing standard embeddings in decoder-only Trans- former [24] with per-sequence random Gaussian vectors, such that the same symbols get the same embedding within each sequence but get different embedding across sequences (Figure 1b). We indeed see that the perplexity gap between the lexinvariant LM and the standard LM shrinks as context length increases, as shown Section 3.2. With a 150M parameters Transformer and small character-level vocabulary (130 tokens), the average perplexity gap shrinks from 9X to less than IX the average per- plexity of standard LM after observing 512 tokens over The Pile [9]. With larger 32K vocabulary, the gap also shrinks, especially on the more structured text like GitHub code, albeit at a much slower rate.
We then explore two additional properties of the lexinvariant LM: in-context deciphering and symbol manipulation. First, we show that given a ciphertext generated by applying substitution cipher to English text, the lexinvariant LM can be lexical permutation, i.e., cipher key, in-context. To show this empirically, we train a small MIP probe on top of a frozen pretrained lexinvariant L.M to predict the deciphered token corresponding the last
implicitly approximating Bayesian inference of the
We specifically consider lexical symbols tokens, not necessarily words other linguistic units.

---

seen cipher token. We can then read out the inferred cipher key with each prefix of the sequence. We show that the accuracy of this inferred cipher key quickly improves as context length grows, reaching 99. 99.6% average accuracy. We also show examples in Section 3.4 that visualize the uncertainties over different possible lexical mappings maintained by the lexinvariant L.M when the cipher key ambiguous and that the semantic meaning of symbol with very rare occurrence can be inferred efficiently relative to other common symbols context. Second, we show that lexinvariant models perform better than traditional models over synthetic pure in-context reasoning tasks that involve symbol manipulation. We observe significant 4X improvement over a standard language model.
While the primary motivation of this paper is scientific exploration of a new idea, lexinvariance, we were also curious to see if could help improve certain tasks, generalizing the performance gain we see on synthetic tasks. We stress that for most practical applications, I lexinvariance is far too strong, so these experiments are intended to illustrative rather than be recipe for improving state-of-the-art We discuss potential approaches to integrate the idea of lexinvariant L.M into standard language modeling as a form of regularization, such that the L.M assumes some form partially stable symbol representations. The resulting LM can improve upon standard language model over some BIG-bench tasks [23].
Lexinvariant Language Model
We define a language model as a probability distribution p(I1 over input token sequences TiuuTa E V", where V some vocabulary over symbols. language model lexinvariant if for all permutations ı: T + + and for all token sequences I1 In E V P(F1, For example, V (a.b), then the model should assign the same probability to aab and bba. One example that satisfies this could simply be
[1/2
x (aab,bba)
p(x)
0
otherwise
Can such lexinvariant language model predict language well, even though it can only make next token predictions based on the structure of co-occurence and repetition of input tokens in single context?
2.1 Convergence on Language Modeling Performance
We show that we construct lexinvariant LM (as shown in Figure 2) to model the true language distribution faithfully, given a long enough context. The lexinvariant language model can essentially infer back the latent permutation it observes more symbols.
X
X2
X5
Xn
TT(x,
TT(x;)
TT(x
Tx(x),
Figure 2: Probabilistic graphical model for the lexinvariant LM associated with the true language distribution p(z1,......).
As an intuitive example, suppose that V= {a and the true language only contains two sequences babbbb and ababob (and their prefixes) with even probability. When given only the first three letters. lexinvariant model can't I tell the latent permutation and can only assign the same probability to and for the next letter: Due to the lexinvariant property, it assigns the same probability to p(a (bb)) = =p(h bbbb) as well as to p(b) aba) ppaabab)) Further, p(a p(alaba) = p( bjbba) because the permutations to prefixes aba and bab are equally probable. In contrast, when considering the prefix abab, the fourth letter resolves the ambiguity in possible permutations (Since baba is not in the true language distribution, v cannot map a to b.) Therefore, the model can correctly predict that p(a (alaabb)) = and p(b)abul =0
Formally, for a given language model p. we define the associated lexinvariant language model p' (II.....TT as E [p(T (Z1))..., (I,,,,,,"(xx,))) (Ix))). Analyzing it, have the following theorem:
Theorem 2.1. Let Tn any loken sequence generated by an arbitrary language distribution p with alphabet of size d. Let p' (Ii,.., E, [p( (0(()>'(x1))))))))))))))<<<))> (x1), ...,T (..,,,-((,xx))))) (xx))]. Then, for any
3

---

0<c,ō<1/3
a 21 (t- u 11)1l
with probability greater than 6, when 72 & polylog(d, 1 2:3), where the polylogarithmic term hides absolute constant that is independent of
This theorem says that this associated lexinvariant language model converges to modeling the true language distribution fairly efficiently- with polynomial rate and near-linear dependence on vocabulary size d. Strikingly, this holds irrespective of the properties of the language distribution 2. In other words, a language model can indeed infer the operational meaning the tokens context based solely on the structure of the symbols!
We give complete proof of this theorem in Appendix A. At high level, this convergence happens because at most timesteps the new observation Ie either provides new information about the permutation x. or Ie has similar likelihood under the permutations that are likely given 21...,2-111 In the simplest casc, if the posterior P(TT] [f....,fx concentrates on the correct π,, then we converge to the standard LM. But even if doesn't. that means the uncertainty about should not matter for predicting the next token. We make this precise by interpreting p' (Iza multiplicative weights algorithm with the Hedge strategy of Freund and Schapire [8], and then relate the regret bounds to the average KL divergence between the predictions of and p', and ultimately the average L distance between these predictions.
as performing
2.2 In-context Bayesian Deciphering
We can see the associated lexinvariant language model as implicilly learning to approximate an in-context Bayesian deciphering process, i.c. inferring a probability distribution over possible lexical permutations based on seen tokens, with the language modeling prior:
p' (In+ (.1,.....)))
p(á (II)...,TT ( (In+1))
d!
(((I11..((t)))
p( "(x1)..... (In+1)) ( (x1) (xn))
p( (xx (..).... (In))
> p( p (an ( (z1)... I
P P(T -
(xx))
language modeling
inferring lexical permutation
As shown above, p' can be reduced two parts, where the first part is normal language modeling and the second part is the probability distribution of lexical permutations based on seen tokens. So the lexinvariant language model is implicitly learning model (Tr (......
We can make this approximate in-context Bayesian deciphering explicit by training small probe predict P(r|ai,,..,,2 given the internal representation of the lexinvariant language model. We will show that this indeed recovers reasonably accurately in the experiment section.
2.3 Constructing a Lexinvariant Language Model
We now consider how to construct lexinvariant LM in practice. A typical neural language model, such as Transformer, converts input tokens to continuous vectors using token embedding and then passes these vectors input to the rest of the neural network. Thus, the language model p it parameterizes depends on the token embedding E: D:V-RR' Rdd
- (FF()))).
To make neural LM lexinvariant, randomized E and take the expectation over E. Each token x E V has an independent embedding
replace the standard stable token embedding E with
"The convergence rate could be better depending on the language distribution, such as on math and code, where the symbols should have clear functional meaning context. We explore this empirically in the experiment section

---

B(x)~N((,,I)) and the language model becomes
p(.1,,-.,,,)) (
(5)
Since E _ Eoπ, the right-hand side is the same when 2; are applied with any permutation т,, i.e., for any 21 2p.
(6)
showing that the Transformer with random E is lexinvariant in Eq. 1. Now we can train this lexinvari- ant LM similarly to a standard LM. Concretely, we sample a new E' for each training sequence and mini- mize the standard language modeling loss in standard neural LM. Here we are stochastically optimiz- ing a variational lower bound of the standard language modeling loss with this randomized model by tak- ing the expectation to the outside of the loss over log likelihood. Effectively, the same token gets the same random embedding within each training sequence, but different embedding across training sequences.
In practice, we focus on training decoder-only Transformers with next token prediction objective in this work, where the model directly models p(z,+1 (0fn+1|21..--000 .....fa instead of the joint distribution. Our definitions and analysis above still hold in general. The only modification is that the final readout matrix also needs to be replaced with the same E, so that the Transformer can predict the embedding of the next token based on the embeddding of input tokens.
3 Experiments
3.1 Setup
Architecture. For all experiments, we use decoder-only Transformer architecture with T5 relative position bias [19]. We use models with 150M parameters, with 12 layers, 8 heads, head dimension 128, and MLP dimension 4096.
Training. We use the Adafactor optimizer [22], with a cosine decay learning rate schedule [13] from 0.01 to 0.001 based on preliminary experiments. We train the models from scratch for 250K steps on all the settings, with 512 sequence length and 64 batch size. We ran all of our experiments on 8 TPU cores. Our models are implemented in JAX [5].
Datasets,
For datasets, we mainly use the Pile [9]. a large open-source corpus that contains text collected from 22 diverse high-quality sources. We also experiments two additional datasets to explore their effects on the behavior of lexinvariant models: Wiki-40B [10], which contains high quality processed Wikipedia text in 40+ languages, and GitHub (subset of the Pile), which contains code from GitHub repositories with more than 100 stars and less than 1GB files.
3.2 Convergence to Standard Language Models
We first show empirically that lexinvariant LMs mostly recover the next token prediction performance of standard LMs after long enough context. As already discussed in section 1. the lexinvariant LM will theoretically converge a standard LM the context becomes long enough to resolve ambiguity. Here we verify this experimentally and show the variation of this convergence across corpora and tokenizations.
To show this, we train lexinvariant and standard LMs with both character-level vocabulary (128 ascii characters) and T5 default vocab (32k tokens) over the three datasets. For each model, we measure
Model Perplexity with Character-lever Vocabulary
Model Perplexity with T5 default vocab
40
standard
14000
standerd
lexhvarian
lexinvariant
12000
30
10000
Perplexity
Perpledit
8000
20
6000
4000
10
2000
0
100
200
300
400
0
100
200
300
400
Context Length
Context Length
Figure 3: Perplexity over the Pile with character-level vocabulary (left) and T5 default vocab (right).
5

---

the perplexity of each token in each sequence w.r.t context length, smoothed by moving average within each sequence, i.e. Plzi.....iiik (1,..,,. for context length i. We set the moving average window i == 100. We plot results over 100 sequences. As shown in figure 3, the perplexity gap between lexinvariant LM and standard LM gradually shrinks the prefix becomes longer and longer, albeit much more slowly with a larger vocabulary. This makes intuitive sense since a larger vocabulary has more possibilities of permutations and requires many more prefix tokens to disambiguate. For the 32K vocabulary, the 512 context length will only allow the model to see a very small number of tokens, let alone to see tokens more than once. Nonetheless, the model still manages show the trend of convergence, since even a small number of repetitions can form common patterns in grammar (such the usage of spaces, punctuation, articles, etc). For the character-level vocabulary, the perplexity gap shrinks from 9X to less than XX the average perplexity of the standard L.M. With context length 511, the lexinvariant LM converges to perplexity 3.38, almost comparable the perplexity of the standard LM of 2.00. Additionally, we observe that the gap shrinks significantly faster for models trained over Github than standard English text like Wiki-40B since code is more structured and is easier to decipher the token permutation. We show the comparison across different datasets in Figure 7 in Appendix.
3.3 Recovering Substitution Ciphers
Here we show that lexinvariant LM is implicitly performing Bayesian in-context deciphering by testing its ability recover cipher keys (e.g. Figure 4a) from character-level substitution ciphers, e.g. uC; kvR5W 4mfzd @f Svegn fw; m uCRmu; ;d ]%.} :fn.. For the lexinvariant LM, this cipher text perceived the same the quick brown fox jumps over thirteen lazy dogs, due the lexinvariant property. It will then proceed to complete the cipher text with %d: uC; @f with the same probability as will complete the normal text with and the fox.
Because of this, we cannot directly read out the distribution of possible cipher keys [ 1....nnn implicitly inferred by the lexinvariant LM. To do this, we train small two-layer MLP probe on top of a frozen trained lexinvariant LM. For each training sequence, we first embed the input sequence with a randomly sampled token embedding E' as described section 2.3 and obtain the hidden activation of the final layer generated by the frozen lexinvariant LM. Then, we pass this activation through the two-layer MLP probe. Finally, instead of decoding the output activations classification logits with the same E as in the lexinvariant LM, we instead use another learnable non-randomized token embedding matrix E' so that the probe can recover the deciphered token with stable token embeddings. Overall, we train the probe jointly with this embedding matrix E'' to predict the current token. Effectively, we are training the probe to decipher the current token using the representation provided by the lexinvariant LM. We train the probe over the same corpus as the original lexinvariant LM for 10k steps. With this probe, we can directly visualize P( -1 (Z,,) (T1,..,, inferred by the lexinvariant LM, which is effectively one row in the permutation matrix representing
Now we can use this probe to explicitly recover the cipher key. An example ground truth eipher key that we want to recover is shown in Figure 4a. Note that although the substitution cipher is only among lowercase letters, the character-level lexinvariant model we use assumes that all permutations among the 128 characters are possible, making the deciphering even more challenging.
1.0
Dicigger Actunicy
0.8
0.6
0.4
0.2
0.0
50
100
150
200
250
300
350
400
Context Length
(a) Ground truth
(b) Majority vote prediction
(c) Cipher key prediction accuracy
Figure 4: (a) (b): Cipher key matrix, where the vertical axis shows the cipher characters and the horizontal axis shows the deciphered letters. The highlighted entries show the correspondences between cipher characters and the actual letters, e.g. deciphers to 1. (c): Cipher key prediction accuracy, averaged across 1000 input sequences. Context length denotes the start index of the window.

---

Figure 5: Predicted cipher key for windows of size 50, at indices 0, 50, 100, 200, and 400. Generated using temperature =1
Concretely, we first input ciphertext through the frozen lexinvariant LM with the probe to produce deciphered sequence. We then select window of size 100 in the middle of the sequence and perform a majority vote over the corresponding deciphered tokens of each cipher token seen in this window. This essentially produces predicted cipher key matrix for each window, and we can measure its precision against the ground truth. As shown Figure 4c, such a cipher key prediction generally has increasingly higher precision as the window is selected later in the context, and it becomes near-perfect by the end of the sequence. Specifically, the cipher key matrix produced by the last window has an average precision of 99.6% over 1000 input sequences.
Finally, we aggregate over the last window of the 1000 sequences recover full eipher key, in case certain letters never appear in the last window of certain sequences. We again recover full cipher key via majority vote. In Figure 4b, we show the highly accurate predicted cipher key recovered from ciphertext produced using the example ground truth cipher key in Figure 4a.
To perform more detailed analysis showing the Bayesian deciphering process of the lexinvariant model, we use the logits of the probe to recover the predicted distribution of the cipher key P(T ((r
Instead of taking the majority vote of the predicted decipher tokens in the window,
we take the mean of logits predicted for each ciphered token. This essentially gives a locally averaged predicted distribution of cipher key matrices. Specifically, the cipher key matrices are generated across windows of 50 characters, and the probabilities are averaged over 1000 input sequences encoded using the same ground truth cipher. As shown in Figure 5, the predicted distribution of cipher key matrix becomes sharper as the prefix becomes longer.
3.4 In-context Bayesian Deciphering Examples
Here, we show several qualitative examples of in-context Bayesian deciphering. We first show how the lexinvariant LM maintains uncertainty over possible lexical permutations while iteratively updating them at each index, using examples from a character-level lexinvariant model. Then, we also show an example of semantic in-context deciphering with a 32K vocabulary lexinvariant model, where the meaning of novel word is inferred relative to common words in-context.
3.4.1 Uncertainty over Lexical Permutations
In Figure 6a, we input the following ciphered sequence to the frozen character-level lexinvariant LM with the probe: "I saw lots of people in town today, walking and talking around me. I greeted my friend Alice and my classmate Alex. I outside carrying a zat. Joe's zat was taken off zy wind. Today's wind was strong, Joe's zat flew zackward. Joe lost Joe' 's zat for good. Joe will miss Joe's s zat." " For each instance of z in the sequence, we display the predicted deciphering of that instance row of probabilities across non-cipher letters a-z.
guy, Joe, walking
The lexinvariant model starts off assuming uniform probability for all possible lcxical permutations т. After seeing more and more text, the lexinvariant model quickly realizes that z only has a few main plau- sible decipherings (b, h, c, m). Eventually, the lexinvariant model is able to narrow the possibilities down to maps to near the end of the sequence. The predicted probabilities shift with the seen context ac- cordingly, demonstrating an example of how the predicted cipher key is iteratively updated at each index.
Figure 6b shows another example with a similar set up. but with text: "I saw a man in the pazk with a zat. The man was walking with the zat zight beside him. I've nevez seen anything like that befoze." While context initially suggests that z may be deciphered as c, becomes clear that z must correspond to r after the appearance of "right". The disambiguation is reflected in the depicted probabilities.
7

---

In Figure 6c and 6d, we show two deciphering examples over code. We consider two code examples in which is initially ambiguous whether the character z deciphers The ambiguity is eventually resolved by the use of Python-like or Java-like syntax.
3.4.2 Semantic Deciphering
In addition to character-leved deciphering, we show examples of semantic deciphering with the larger vocabulary 32k. Although the lexinvariant LM could not possibly figure out the true lexical permutation among 32k tokens using small 512 context, it is possible to construct a simple context that repetitively
simple words that these words easier decipher. Then the lexinvariant LM can decipher the approximate semantics of the rare symbols relative to other easier-to-decipher words.
One example is the following: given the prompt 'crash!' 'aaah!' i looked up from my cup coffee. 'crash!' that was the cafe window. and 'aaah!" [... more text...] father
what one here is drink _ restaurants - music - coffee
2 the one here that drink is, where the word coffee, music, and father all only appear once before the question and restaurants appeared 4 times, the model is able to correctly answer
that coffee is drinkable. See the full example in the appendix.
3.5 Synthetic Reasoning Tasks
As discussed the introduction, lexical flexibility correlated with in-context reasoning performance, demonstrated by existing large LMs. Thus, we study whether the lexinvariant model also learns in-context reasoning capabilities through the challenging lexinvariant training.
Specifically, we measure the performance of lexinvariant models over two pure in-context symbol manipulation tasks: LookUp, where task is to predict the next token based on the given lookup table, e.g.
(should predict 4 here); and Permutation, where the task is to permute an arbitrary subsequence of the given sequence the same way as in the given few demonstrations, e.g. C->C A J4 D-> (should predict D 4 here). In each of the tasks, the symbols are randomly sampled from the vocabulary so that we measure the pure reasoning ability independent from any knowledge of specific words. We measure the model performance in terms of generated token accuracy over 1000 examples. The results are shown Table 1. As shown the table, the lexinvariant models achieve drastically higher accuracy, with an average of 4X improvement.
Table 1: Accuracy over synthetic reasoning tasks.
Dataset
Vocab
LookUp Acc
Permutation Acc
Standard
Standard
LI
char
48.50
91.80
27.66
59.35
Pile
32k
21.45
92.10
22.84
55.63
char
38.25
59.70
20.77
60.51
Wiki-40B
32k
8.75
59.35
9.94
50.91
char 32k
42.40
86.65
21.03
71.59
Github
4.25
80.20
8.59
67.39
Joe
was takio
..ttrrnng so 1005
wolll mas
2 abcde Mocdefgh.. iik imnoser 2
(c) True deciphering: "z" "[",T=
(a) True deciphering: "z"
-'=1
pack with
wa King with the
the ret
ab wighigh Imm opg www.aparrwwwwy......... (d) True deciphering: "z" ".7, T.
0
(b) True deciphering:
"T"TT=
Figure 6: Probe predictions for deciphering "z" at each occurrence of "2" in context.
8

---

3.6 Regularizing Language Models with Lexinvariance
Although lexinvariant LM has various interesting properties it not suitable for practical tasks since would require the context to be extremely long so that all required words and knowledge are defined in the context. Here, we explore how to construct more practical semi-lexinvarian LMs that maintain some properties of lexinvariant LMs via regularization. We emphasize that this exploration is intended to be illustrative rather than directly improving state-of-the-art.
Instead of using random Gaussian embedding matrices in place of a learned embedding matrix entirely, we can use random embeddings for only some of the tokens in each sequence, while others use the learned embedding. This means that the learned LM assumes that certain tokens have stable meanings but not others, which can be seen as a form of regularization towards lexinvariance. Specifically, we randomly select tokens randomize based on a Bernoulli distribution, which can essentially be seen as a form of dropout on token embeddings. On the BIG-bench tasks, we found that model with dropout rate p = 0.2 for randomization was 25% more likely to improve performance than to harm performance when evaluated with three shots, relative to a comparably-sizee sized LM, with improvements especially over retrieval type of tasks. See full details in the Appendix G.
More broadly, this regularization view could potentially bring the benefit of lexinvariant LMs to practical applications. For example, the regularization could improve 1) the robustness of LMs by making them less sensitive to adversarial attacks or noise in the input data, 2) generalization across different languages or domains by being less tied to specific lexical items and more prone to learn the shared language structure, and 3) reasoning over more realistic tasks as we have started to explore with BIG-Bench. These areas are promising directions for future work to explore.
4 Related Work
4.1 Symbol Grounding
Beyond a modeling choice, the main question of our paper (that being whether an LM can learn language without a stable token representation) also analogous to the symbol grounding problem: Can meaning be acquired when symbols are not even grounded stably, i.e. they can be mapped to completely random meanings in different sequences? has long been argued by the symbol grounding literature that symbolic representations must be grounded bottom-up in nonsymbolic representations [11], with famous arguments like Searle's s Chinese room: It describes a person in a room given a step-by-step set of instructions by which they can respond to Chinese text with reasonable-sounenn sounding Chinese text. To an outside observer, the person in the room appears to understand Chinese, but the individual does not know word of Chinese. This is widely used to argue that understanding language requires grounding the symbols in the real world. It leads to an ongoing debate on whether LMs can learn meaning purely from large amounts of text, without grounding any real-world objests [4]. Although intuitively, lexinvariant LMs appears one step further removed from physical grounding than standard LM, we find that given enough context they can still infer the meaning of symbols based on lexical structures within the context.
4.2 Group invariances and Data augmentation
Our implementation of lexinvariant LMs be seen performing form of very aggressive data augmentation, where we randomize the identity of each token in each sequence. From this perspective, it is somewhat similar the data recombination in [14, 2] and augmentation of named entities in [20], where certain parts of the sentence are swapped with other words while still maintaining the original grammatical structure. In contrast to these augmentations, the training for our lexinvariant LMS completely swaps out all parts of the input text.
4.3 Byte-level TS
There is existing work on absorbing tokenization completely into part of language modeling by using extremely small tokens, such as Byte-level T5 [25]. In the extreme, such a model would become closer and closer to lexinvariant LM, since bytes or bits have almost no stable meaning, so their embeddings are likely not used for prediction. In this paper, we study general lexinvariant LMs with the lexinvariant property baked in and without requiring specific tokenizers.

---

4.4 Deciphering Substitution Cipher using LMs
In general, solving substitution ciphers, where the cipher key is a permutation of the original alphabet, is NP-hard problem when only having access to LMs that can assign probabilities to sequences [18]. There have been several works focusing on solving substitution ciphers using LMs, including approaches from searching over the permutation space guided by LMs' scores [12] training seq-to-seq model directly to perform deciphering as translation [3]. Although our work does not focus specifically on the task of deciphering substitution ciphers, we show that our lexinvariant model can efficiently perform in mn-oonext deciphering as byproduct of language modeling.
4.5 Reasoning
It has been shown that large language models acquire surprising in-context reasoning capabilities [6, 15, 23]. Many of them are related lexical flexibility through training for purely next-token prediction, such as modified arithmetic, data reformatting, and redefining single word etc. However, LLMS also memorize an enormous amount of knowledge along the way, which often unnecessary. This work can also be seen knowledge and prioritize learning the diverse structural reasoning patterns language, therefore achieving the strong reasoning capability of LLMs with smaller model.
exploration of whether a (semi-)lexinvarian LM can discount
5 Conclusion
In this work, we define and study lexinvariant language models, which do not have stable embeddings and learn to infer the meaning of symbols in-context. We show several surprising properties of this model theoretically and empirically, including convergence to standard language modeling, in-context deciphering. and better reasoning capabilities. We also explore less extreme lexinvariance regularized language model and demonstrate its potential for solving more practical tasks efficiently.
Acknowledgments and Disclosure of Funding
We thank Sang Michael Xie and Steven Cao for discussions and for providing feedback on our manuscript. This project is supported by Open Philanthropy Project Award. Qian Huang is supported by Open Philanthropy Al fellowship.
10

---

References
[1] The multiplicatiie weights algorithm. https://www cs. cmu. ammu.dd/afs/caa cmu, edu/
pdf. Accessed: 2023-04-24.
[2] E. Akyürek, A. F. Akyurek, and J. Andreas. Learning to recombine and resample data for compositional generalization. ArXiv, abs/2010.03706, 2020.
[3] N. Aldarrab and J. May. Can sequence-to-sequeeece models crack substitution ciphers? In Annual Meeting of the Association for Computational Linguistics, 2020.
[4] E. M. Bender, Gebru, A. McMillan-Maan -Major. and Shmitchell. On the dangers of stochastic parrots: Can language models be too big? Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency. 2021.
[5] J. Bradbury, R. Frostig, P. Hawkins, M.J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q Zhang. JAX: composable transformations of Python+NumPy programs, 2018.
[6] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Hlerbert-Voss, G. Krueger, T. J. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray,
B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language models are few-shot learners. ArXiv, 1tts/2005.14155,,, 2020.
[7] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, ArXiv, abs/1810.048055, 2019.
[8] Y. Freund and R. F. Schapire. A theosion- generalization of on-line learning and an application to boosting. In European Conference on Computational Learning Theory, 1997.
[9] L. Gao, S. R. Biderman, S. Black, L. Golding, T. Hoppe, C. Foster, J. Phang, H. He, Thite, N. Nabeshima, S. Presser, and C. Leahy. The pile: An 800gb dataset of diverse text for language modeling. ArXiv, abs/2101.0000 000227. 2020.
[10] M. Guo, Z. Dai, D. Vrandecic, and R. Al-Rfou. Wiki-40b: Multilingual language model dataset. In LREC 2020, 2020.
[11] S. Harnad. Symbol grounding problem. Scholarpedia, 2:2373, 1990.
[12] B. Hauer, R. B. Hayward, and G. Kondrak. Solving substitution ciphers with combined language models. In International Conference on Computational Linguisticx, 2014.
[13] J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. de Las Casas,
L. A. Hendricks, J. Welbl, Clark, Hemnigan, E. Noland, K. Millican, van den Driessche, B. Damoc, A. Guy, S. Osindero, K. Simonyan, E. Elsen, J. W. Rae, O. Vinyals, and L. Sifre. 2022.
Training compute-optimal large language models. ArXiv, abs/2203. 15556 15556,
[14] Jia and P. Liang. Data recombination for neural semantic parsing. ArXiv, abs/ http//666.06662... 2016.
[15] P. Liang, R. Bommasani, T. Lee, D. Tsipras, D. Soylu, M. Yasunaga, Y. Zhang, D. Narayanan, Y. Wu, A. Kumar, B. Newman, B. Yuan, B. Yan, C. Zhang, C. Cosgrove, C. D. Manning, C. R e, D. Acosta-Navas, D. A. Hudson, E. Zelikman, E. Durmus, F. Ladhak, F. Rong, H. Ren, H. Yao,
J. Wang, K. Santhanam, I.. J. Orr, I.. Zheng, M. Yuksekgonul, M. Suzgun, N. Kim, N. Guha, S. Chatterji, O. Khattab, Henderson, Q. Huang, R. Chi, S. M. Xie, S. Santurkar, S. Ganguli, T. Hashimoto, T. F. Ieard, T. Zhang, V. Chaudhary, W. Wang, X. Li, Y. Mai, Y. Zhang, and 2022.
Y. Koreeda. Holistic evaluation of language models. ArXiv,
[16] T. Mikolov, K. Chen, G. S. Corrado, and J. Dean. Efficient estimation of word representations in vector space. In International Conference on Learning Representations, 2013.
[17] Mikolov, M. Karafiát, I.. Burget, J. Cernocký, and S. Khudanpur. Recurrent neural network based language model. In Interspeech, 2010.

---

[18] M. Nuhn and H. Ney. Decipherment complexity in 1:1 substitution ciphers. In Annual Meeting of the Association for Computational Linguistics, 2013.
[19] C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res., 21(1), jun 2022.
[20] Raiman and Miller. Globally normalized reader. In Conference on Empirical Methods in Natural Language Processing, 2017.
[21] H. Schüize. Part-of-speech induction from scratch. In s1 Annual Meeting of the Association for Computational Linguistics, pages 251-258, Columbus, Ohio, USA, June 1993. Association for Computational Linguistics.
[22] N. Shazeer and M. Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In J. G. Dy and A. Krause, editors, Proceedings the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmüssann Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 4603-4611, PMLR, 2018.
[23] A. Srivastava, A. Rastogi, A. Rao, A. A. M. Shoeb, A. Abid, A. Fisch, A. R. Brown, A. San- toro, A. Gupta, A. Garriga-Alonso, A. Kluska, A. Lewkowyzz A. Agarwal, A. Power, A. Ray, A. Warstadt, A. W. Kocurek, A. Safaya, A. Tazarv, A. Xiang, A. Parrish, A. Nie, A. Hussain, A. Askell, A. Dsouza, A. A. Rahane, A. S. Iyer, A. Andreassen, A. Santilli, A. Stuhlmuller, A. M. Dai, A. D. La, A. K. Lampinen, A. Zou, A. Jiang, A. Chen, A. Vuong, A. Gupta, A. Gottardi, N.ooeeli, A. Venkatesh, A. Gholamidavoodi, A. Tabassum, A. Menezes, A. Kirubarajan, A. Mul- lokandov, A. Sabharwal, A. Herrick, A. Efrat, A. Erdem, A. Karakacs, B. R. Roberts, B. S. Loe, B. Zoph, B. Bojanowski, B. Ozyurt, B. Hedayatnia, B. Neyshabur, B. Inden, B. Stein, B. Ekmekci, B. Y. Lin, B. S. Howald, C. Diao, C. Dour, C. Stinson, C. Argueta, C. F. Ram irez, C. Singh, C. Rathkopf, C. Meng. C. Baral, C. Wu, C. Callison-Burch, C. Waites, C. Voigt, C. D. Manning, C. Potts, C. T. Ramirez, C. Rivera, C. Siro, C. Raffel, C. Ashcraft, C. Garbacea, Sileo, D. H. Gar- rette, D. Hendrycks, D. Kilman, D. Roth, D. Freeman, D. Khashabi, D. Levy, D. Gonz' alez, D. Her- nandez, D. Chen, D. Ippolito. D. Gilboa, D. Dohan, D. Drakard, D. Jurgens, D. Datta, D. Ganguli, D. Emelin. D. Kleyko. D. Yuret, D. Chen, D. Tam, D. Hupkes, D. Misra, D. Buzan, D. C. Mollo, D. Yang. D. Lee, E. Shutova, E. D. Cubuk, E. Segal, E. Hagerman, E. Barnes, E. P. Donoway, E. Pavlick, F. Rodola, E. F. Lam, E. Chu, F. Tang, E. Erdem, E. Chang, F. A. Chi, E. Dyer, E. Jerzak, E. Kim, E. E. Manyasi, E. Zheltonozhski,, F. Xia, F. Siar, F. Mart Marr'inez-Plumed, F. Happ'e, Shollet,F.Rong. G. Mishra, G. I. Winata, G. de Melo, G. Kruszewski, G. Parascandolo, Mar- iani, G. Wang. G. Gaimoooiich
G. Betz, G. Gur-Ari, H. Galijasevic, H. S. Kim, H. Rashkin H. Hajishirzi, H. Mehta, H. Bogar, H. Shevlin, H. Schütze, H. Yakura, H. Zhang, H. Wong, I. A.S. Ng. I. Noble, J. Jumelet, J. Geissinger, J. Kernion, J. Hilton, J. Lee. J. F. Fisac, J. B. Simon, J. Koppel, J. Zheng, J. Zou, J. Koco" n, Thompson, J. Kaplan, J. Radom, J. N. Sohl-Dickstein, J. Phang. J. Wei, J. Yosinski. J. Novikova, J. Bosscher, J. Marsh. J. Kim, J. Taal. J. Engel. J. O. J. Xu, J. Song, J. Tang. J. W. Waweru, J. Burden, J. Miller, J. U. Balis, J. Berant, J. Frohberg, J. Rozen, J. feenándeez-Oaalo,, J. Boudeman, J. Jones, J. B. Tenenbaum, J. S. Rule, J. Chua, K. Kanclerz, K. Livescu, K. Krauth, K. Gopalakrishnan, K. Ignatyeva, K. Markert, K. D. Dhole, K. Gimpel, K. O. Omondi, K. W. Mathewson, K. Chiafullo, K. Shkaruta, K. Shridhar, K. Mc- Donell, K. Richardson, L. Reynolds. L. Gao, L. Zhang. L. Dugan, L. Qin, L. Contreras Coonterra-OCchaddo L.-P. Morency, L. Moschella, L. Lam, L. Noble, L. Schmidt, L. He, L. O. Col' on, L. Metz, L. K. cSenel, M. Bosma, M. Sap, M. ter Hoeve, M. Andrea, M. S. Farooqi, M. Faruqui, M. Mazeika, M. Baturan, M. Marelli, M. Maru, M. Quintana, M. Tolkiehn, M. Giulianelli, M. Lewis, M. Pot- thast, M. Leavitt, M. Hagen, M. Schubert, M. Baitemirova, M. Arnaud, M. A. McElrath, M. A. Yee, M. Cohen, M. Gu, M. I. Ivanitskiy, M. Starritt, M. Strube, M. Swkedrowski. M. Bevilacqua, M. Yasunaga, M. Kale, M. Cain, M. Xu, M. Suzgun, M. Tiwari, M. Bansal, M. Aminnaseri, M. Geva, M. Gheini, T. Mukund Varma. N. Peng, N. Chi, N. Lee, N. G.-A. Krakover, N. Cameron, N. Roberts, N. Doiron, N. Nangia, N. Deckers, N. Muennighoff, N. S. Keskar, N. Iyer, N. Con- stant, N. Fiedel, N. Wen. O. Zhang. O. Agha, O. Elbaghdadi, O. Levy, O. Evans, A. M. Casares, P. Doshi, P. Fung, P. P. Liang, P. Vicol, P. Alipoormlabbshhi. P. Liao, P. Liang, P. W. Chang, Eekersley, P. M. Htut, P.-.. Hwang. P. Milkowski, P. S. Patil, P. Pezeshkpour, P. Oli, Q. Mei, LYU, Q Chen, R. Banjade, R. F. Rudolph, R. Gabriel, R. Habacker, R. R. Delgado, R. Millière, R. Garg, R. Barnes, R. A. Saurous, R. Arakawa, R. Raymaekers, R. Frank, R. Sikand, R. Novak, R. Sitelew, R. L. Bras, R. Liu, R. Jacobs, R. Zhang, R. Salakhutdinov, R. Chi, R. Lee, R. Stovall,
12

---

R. Teehan, R. Yang, S.J. Singh, M. Mohammad, S. Anand, S. Dillavou, S. Shleifer, S. Wiseman, Gruetter, Bowman, S. Schoenholz, S. Han, S. Kwatra, A. Rous, S. Ghazarian, S. Ghosh, S. Casey, S. Bischoff, S. Gehrmann, S. Schuster, S. Sadeghi, S. Hamdan, S. 7hou, S. Srivastava, Shi, S. Singh, S. Asaadi, S. S. Gu, S. Pachchigar, Toshniwal, S. Upadhyay,
Debnath, S. Shakeri, S. Thormeyer, S. Melzi, S. Reddy, S. P. Makini, S. hwan Lee, S. B. Torene, S. Hatwar, Dehaene, S. Divic, Ermon, R. Biderman,
C. Lin, S. Prasad, S. T. Piantadosi, S. M. Shieber, S. Misherghi, S. Kiritchenko, S. Mishra, T. Linzen, T. Schuster, T. Li, T. Yu. T. A. Ali, Hashimoto, T.-L. Wu, T. Desbordes, T. Rothschild, T. Phan, T. Wang. Nkinyili, T. Schick, T. N. Kornev, T. Telleen-Lawton, T. Tunduny. T. Gerstenberg, T. Chang, T. Neeraj. T. Khot, T. O. Shultz, U. Shaham, V. Misra, V. Demberg, V. Nyamai, V. Raunak, V. Ramasesh, V. U. Prabhu, V. Padmakumar, V. Srikumar, W. Fedus, W. Saunders, W. Zhang, W. Vossen, X. Ren, X. F. Tong, X. Wu, X. Shen, Y. Yaghoobzadeh, Y. I Lakretz, Y. Song, Y. Bahri, J. Choi, Y. Yang. Y. Hao, Y. Chen, Y. Belinkov, Y. Hou, Y. Hou, Y. Bai, 7. Seid, Z. Xinran, Z. Zhao, 7. F. Wang. 7. J. Wang. Z. Wang, Z. Wu, S. Singh, and U. Shaham. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. ArXiv, abs/2206.04615, 2022.
[24] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, u. Kaiser, and I. Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[25] L. Xue, A. Barua, N. Constant, R. AI-Rfou, S. Narang, M. Kale, A. Roberts, and C. Raffel. Byt5: Towards token-free future with pre-trained byte-to-byte models. Transactions of the Association for Computational Linguistics, 10:291-306, 2021.
13

---

A Convergence Proof
Theorem A.1. Let 21 Fi...n en be any token sequence generated by an arbitrary language distribution
p with alphabet of size d. Let p' (1( (I1,..., [x<[p(x
(<)) ,,,,,,,)))) Then, for any
0 Sc,,011/2
Σ [10_ p1.
with probability greater than ō when T2 d 5 (d.
Proof. For any desired error 0 < 1/2 and failure rate 0 à < 1/2, we will first prove the analogous statement for KL divergence instead of L1 distance, and then relate bound on KL divergence back to L distance via Pinsker's inequality.
Throughout the rest of proof, will work with a parameter c' <'0 ((ogt///))) ) 2.2 and will bound our KL. divergence by c'.
To prove the bound in terms of KL divergence, it will be useful to ensure to work with a "smoothed" version of p. which we denote by p. for which every token has some nonzero probability, o/d, of de'
appearing at each timestep, for parameter o = de'/T::
p (T D1... 11)= (1. ST -1
(ZT(2) (xx,)) We use P denote the probabilities under this change. With probability at least 1 1-''2 1- S. the realized sequence 21 Ti,..,,T, drawn un- der can be regarded as being drawn from (as these distributions can be coupled with this probability).
Similarly, let p' (,),...,,,)=EEA
The key idea is then to show that p' (1(y4+al /1..). where y/2 = ==" (2,) for some ground truth unknown to y', is equivalent to using the multiplicative weights algorithm to predict W++1 with the Hedge strategy, with the experts being each possible permutation of the tokens and the cost incurred by each expert being the negative log likelihood of the prediction. We denote - (()))
and show this in Lemma A.2.
With this equivalence, can then bound the difference between the prediction of and p' the regret of the multiplicative weights algorithm. Concretely, we show in Lemma A.3 that the regret of p' to any expert is bounded
T
Pa (U 1ynat) 22e²
Σ log
T
8 (114111222))
for T (4log (gllog(())ooo (og (o'
We can see as the particular expert/permutation P,. And we can further only consider the special case that is also the identity permutation, then the same result holds over i, and with P, replaced by p. i.e.
M[I+1| 266
+
Σ log 7' (11+1
Now we want to convert this bound on regret in terms of log likelihood to KL, divergence, and eventually to L, distance. To convert it to KL divergence regret, we construct a martingale:
2 (21.)) 7'
Z,
(iz t=1
log
(I--I| 1
We verify that this is martingale in Lemma A.4, with differences bounded by 2log 1 and bound the probability that ZT exceeds log d (8T via Azuma's inequality Lemma A.6: with probability 1 1-6/2, we have that |Zr| 1155 b.
14

---

Therefore, we have that with probability at least 6/2
p( p(1++1/2111)
Z1
DKu
log
( (14)
p (mat)) log
Σ 1 (5+
+b
p7 (z (r1a))
Putting this all together, since + Et log 8( the following:
2 2 for T2 (4log ( (o)g(()) /e",, we have (024111011))
T E Da =e
We now convert our bound on KL divergence bound on L1 distance via Pinsker's inequality:
D
Further, at any given Z₁, the difference between the redistributed probability distribution ý and unmodified probability distribution p is at most o, so
[| (T.e) - p' (#1+1 x1:t)l 1 s (((
We are interested in the average L across time steps:
T
T
T
D Di..pporassaaalll/ooo/o.ollllll +2
T
T
T
where in the last inequality we applied Cauchy-Schward Hence for 72 (4log" Elog(u!)) /e",
T
T (2)2T+b)+20
p (x)..,.)) - (fe+1 (x.,
T
T
V
2
b
s / e2
+20.
2T
Simplifying this for b bog 8Tlog] T> (4log² (5) )og(dd)) /c4 and o = C8//T, we have
/ 2log
26'0
p( (2 (0 (
e²
E22
T
v Mlo((d)) (d!)
T
<E'( 25
2log 2 log(d!)
1+
T
2222V 2 3mm
<c(1+ 1+
2log 8
15

---

We can bound this average L1 error by e if we set 2v2(22og < 22 in which case our condition that T' 2 (4log" di )log(d)) /e" becomes T' (512log) log di log(d!)) /ct. The theorem now follows by simplifying this expression. Since log - 2log and log(d!) S (llo)()) we can relax the condition on 7 as
d T2 1024log Ju024lgg1og' log (5= )ogg (T))o(()) 1e== (T) d polylog( -.5)
To remove the log² from the right side, note that for any W > 10, if T 10 W log W, then T> WlogeT, yielding the further relaxed the condition on aas
d T
E polylog (d. -
Lemma A.2. Consider an arbitrary ground truth permutation x²_ For all time steps t E [1,n], ler y: (x,) Consider the online prediction game of predicting yt+1 at each time step given previous ob- servation aıa without knowing x" but knowing P. Then, y' (1h441/90 (/W1)))) is equivalent to the multiplicatiie weights algorithm's 's prediction of 41++ with the Hedge strategy of Freund and Schapire [8], where
Considers d experts corresponding to guessing each permutation n' is the ground truth permutation.
Maintains weight w for each expert at time step i, and the weights are initially as P(
Picks distribution across experts P- कti
(1)
w0
where 111) x10== =E,
Produces prediction of yt+1 Ex P PT (16+1l91=))
Receives cost vector of m (t) log? (y++1lb1a).
Updates the weights w, (t+1) = w. (t)
exepp-eenn ) and repeat
Proof. We can first see that - = P(m' w)r) by induction:
Base case: ( P((T) by assumption.
Inductive Case:
With the cost vector as m
- log w (xveenn Therefore, the probability over any particular expert x/ is
(t-1)
the update at step 1 is
w (1)
P
Pr. (velv)+e-1)
w
E,w, (
1), (1
(1:=--1)
(1-1) ()-1))(0 (1-1)) (We 1112-11
E,p, (11))-11 (t- -1) p) (111811-11
P (t-1) (v.
Σ, (t-1)) (pullaa()))))
This is equivalent to the update given by Bayes' rule when plugging in p = (T''lla))
P( ((r'l11a 11P (v.lite--)
P(ydyia-1)
16

---

So we can conclude that p -Pr''lt i.e. the process of updating the probability distribution across experts within the prediction game is equivalent to the process of the language model updating the probabilities P(x' (1.++1) across permutations n'. And this means that the algorithm'ss 's prediction P P(T' (yc-11 P (1a)== (y
Enp (1) (y (1.))= (Jt+1l31a))=
Lemma A.3. When using the Hedge strategy for the multiplicative weights algorithm, the average difference between the weighted distribution across experts and any particular expert is bounded as
1
P- (113)) 22
log
T
F' (M0+1l01.))
for S and and T (4log² ( (ogg
Proof. Consider an arbitrary expert I.
We first show that the cost vectors are bounded by = - log a: Recall we defined
m! 1 log (yc++1l1r)) By the definition of our redistributed probability distribution, at time step & [|.
s Pa (yc+1 $
d
log < logP+ x (1+++1 (1:t)) 50
0
0 0 (1) - - -lg
d
1
(((l) 0 05m - log
E d'
By corollary 16.3 in [1], if we have cost vectors m (1) E plpp,p] dd! then for time T2 (4))log(d))//²
where 1,
T T
T
m (t)
m (t) +2c.
S
T
Note that we can simplify T'2 (4log" We can now bound
log(d)))
1
(0) (mm(()) 2e
T
T
Pai m
(t)
- mm
2e
T
(1 1 1-1ogp=> (11t (wr+11lu)))
(-(ta))))-(oo (~1-oop- - (ve+alena))
Σ P( (on=))
22
T
-(i)))logge logP x. lyn
<2c
T
1 T
p. P2((++11111) <2e
E log
T
p (1/+1 191:t)
By Jensen's 's inequality, we also have that
1 T
P- (31411/11 <66²
log
T
E 711+1111100
Pn (Ve+ 266
Jog ( (y::e)
17

---

Lemma A.4. Let
Py P,
2i=)
Σ
Pl Pl (21a)
7g a martingale.
Proof. Consider
Pi (1 (xx:t)
E D1 = B wA,,
DKL Dxe((P((++)):::))(((e() -log P ( (2111)
Pi (x (2118) -
= E
DKL
-log
p(z1+1(21n1)
Observe that Z;-1 has no dependence on Ti+1-
Pi (244112211) 221 1111,11,)) 12:1= = E I> BRil1~ log P P(r 111))
Pi (
E i>
log
+ +Z--1
P P [14)
-Z=-1
Therefore, Zi is martingale.
Lemma A.5. Z.-Zze Zi-1/se, where c; 2
Proof. We have
p. (1,-1|01n5) (onn)) -log
P ( (m1.))
In our redistributed probability distribution P. we have g ( 1) < for any at any time Therefore,
log llog (1 <log
d p(x141/215)
Also, we can find an upper bound for the KL divergence by maximizing (1(4+11<)1)) to 1 and minimizing P(I+41/a1.) to y so that
Pr Pr P(x++ (11))
Σ Pr
2:-1
d
< log
We can maximize |2, Zi-1l by maximizing the first term and minimizing the second term, or vice versa. In the first case. 1Z, Z1-1| < loog log y 2) log L In the other case, - 11-
|l
Therefore, 12, - -Z,-1/1 where c, = 2|
Lemma A.6. By Azuma's inequality, with probability 8, we have that /r < where b 2log d 1
18

---

Proof. By Azuma's ss inequality, for all positive reals b,
6²
P(zr-Z120)<epp
2 k= C
216--2151/2-exp
2) 2) 2= kk
6²
21 expexp
8 x log 2d
We can rewrite in terms of ó exxp
k log 2d
50
7
b
log
logó
km 2
log
8Too
8
Therefore,
S b) 21-8
B Model Architecture Details
In addition, add learnable scaling and bias parameter the result of the embedding layer, that the model can still learn to scale it as needed.
C Convergence on other datasets
Figure shows the perplexity of lexinvariant LMs across the three different datasets. Note that Github converges significantly faster than standard Engish text like Wiki-40B, since code is more structured and easier to decipher the token permutation.
D Code Deciphering Full Examples
Java:
binary_search ()z
if (high low )z
mid = (high + low) 2; if (arr[mid] return mid: if (arr[mid] x)z
x)
high = mid - 1; return binary_search (); } elsez
low mid 1;
return binary_search ();
} elsez return -1;
}
void func2 z)z
19

---

10
10
pile,char
Perplexity
pile,32k
Wiki-40B, chaa
10
Wiki440B, 32kkk
github,cht char
github, 32k
10
10
100
200
300
400
Context Length
Figure 7: Smoothed Token Perplexity the Pile, Wiki-40B and Github, with character-level and T5 default vocab
Python:
()z
if (high >= low)
mid = (high low) 11
if (arr [mid] = x)z
return mid if ( (arr[mid)
x)z
high = mid 1
return Emarry_earceh ()
elsez
low mid return binary_searce ()
elsez
return -1 def (unc2()z
E Semantic Deciphering Full Example
'crash!' 'aaah!' i looked from my cup of coffee. 'crash!' that was the cafe window. and 'aaah!" that kate. people in the cafe shouted. kate and i ran to the window. there was no one there. then i turned to kate and put my arm around her. i think so.? "what is it?* some one shouted and a short red-faced man ran into the room. the man took my arm. 'matt! what are you doing kate?' he asked. 'nothing, papa,' kate replied. 'it wasn't him. it was from out red-faced man looked at the window and then at me.
you all right?' asked. 'yes," she said.
the street,' , turned to his daughter. 'are you ok, kate?' he asked. kate gave him a little smile. 'yes, think am, papa,' she said. then her father spoke to me. 'sorry, matt. i heard kate and i thought..." answered. was ok. you see, this soho, in centre london. in day it's famous for music and films. at night people come and eat and drink
'that's ok, paolo,' '
20

---

in the restaurants. expensive restaurants and cheap restaurants; italian restaurants and chinese restaurants. and day and night there are internet cafes like the web cafe. in soho you can buy any thing and any one. there are lots of nice people in soho. but there are also lots of people who are not very nice. i know because i live and work here. i often take a drink to a shop or cafe. i'm not rich and famous. and i don't know a lot. but do know soho. what one here is drink restaurants music coffee father the one here that drink is
Example prediction of the lexinvariant with 32k vocabulary train on the Pile:
coffee. and i
The probability (at temperature=1) of coffee being selected is 56%, substantially higher than the next-highest probability of restaurant at 27%, music at 12%, or father at 5%
F Synthetic Reasoning Task
Table 2 shows variant of the synthetic reasoning task results in Subsection 1, where the symbols are instead sampled proportion to the token frequencies. Although the improvement still generally holds, the standard LM with character-based vocabulary becomes significantly better. We believe that this is because the model can get a significant advantage by guessing among the most common letter.
Dataset
Vocab
LookUp Acc
Permutation Acc
Standard
LI
Standard
LI
char
72.80
90.95
40.63
60.47
Pile
32k
61.20
90.95
40.55
54.55
char
75.55
63.45
42.71
59.86
Wiki-40B
32k
41.05
57.95
26.81
51.86
char
66.00
86.75 78.45
36.62
70.77
Github
32k
59.25
37.46
65.04
Table 2: Synthetic Reasoning Tasks (adjusted for token frequencies)
G Language Models Regularized with Lexinvariance and BIG-bench Results
As described the main paper, we implement a lexinvariance regularized Model way similar to embedding dropout. Note that one problem in implementing! it naively by using random Gaussian embeddings and learned embedding in a mixture is that the two would become quickly distinguishable from each other during training since learned embeddings often have larger norms, allowing the model simply ignore the randomized tokens. So instead of using random Gaussian embedding matrices in place of a learned embedding matrix, we explored another approach for training lexinvariant regularized LM: training a standard LM with learnable embedding matrix over sequences partially applied with random token permutation (2), (21,,, where (x, (Ix)) with probability and B, (x;,7) x; with probability 1 p.p. Since each token can be remapped to any other token with equal chance, the produced model should ideally also be lexinvariant when p= though with no strict guarantees. In practice, we found the models trained this way behave very similarly models with random Gaussian embedding.
We evaluate our model over BIG-bench tasks where the language model performance scales well, and we prioritize evaluating generative tasks over multiple-choice tasks. Tasks evaluated on:
gre reading comprehension.me mul, linguistics puzzles.gen, linguistics puzzles.gen gen, rhyming-gee gen, fellmewhy.gen, simple arithmetic multiple targets json.gen, simple arithmetic json subtasks.get genn disfl qa.gen, arithmetic.gen. bridging anaphora resolution barqa.gen, matrixshapes.ge information gen, logical args. novel concepts. mul, code line description.mul unnatural in context learning-gee gen, unit interpretation.mut english proverbs. mull, general knowledge. mul, geometric shapes.gen gen, human organs senses.mul, contextual parametric knowledge confficts.go gen, crass ai.mul,
sufficient
21

---

auto categorization. gen, penguins in a table.gen, hindu knowledge.mun mul, english russian proverbs.ma mul, modified arithmetic. cryobiology spanish.mul, evaluating information essentiality.mm intent recognition.mut understanding fables.mul, figure of speech detection.muu empirical judgments. mull simple ethical questions. mul, swahili english proverbs.mug mull language identification.mu mull, phrase relat- edness.mul nonsense words grammar.mul, undo permutation.mul, object counting. gegen, identify odd metaphor.mui elementary math qa.mul, social iqa.mul, parsinlu qa.mul, metaphor understanding.mut timedial. mull, causal judgment. mul, list functions.gen. implicatures. mull date understanding mul, codenames.gen gen, fact checker. mul, physics mul, abstract narrative understanding .uul, emojis emotion prediction.mul mul. metaphor boolean mul, strategyqa. ascii word recognition, gen, auto debugging gegn,, cause and effect.mul, conlang translation. gen, cryptonite.gen cs algorithms.mul dyck languages. muul gender inclusive sentences german.gen gen, hindi question inswering-gen. international phonetic alphabet transliterate.gen gen, irony identification.mu mul, logical fallacy detection. mul, movie dialog same or different.mul, operators.gen, paragraph segmentation.ge
parsinlu reading comprehension.gee repeat copy logic.gen, rephrase.gen, simple arithmetic json.gen, simple arithmetic multiple targets json.gen, sports understanding. mull word unscrambling.ges hyperbaton.ma mul, linguistic mappings.gen anachro- nisms.mul indic cause and effe question selection. mul, hinglish toxicity.mul, snarks. mul, vitamine fact verification.ni mul, international phonetic alphabet nli.mul, logic grid puzzle.mul natural instructions, entailed polarity.mul, list functions. gen,, conceptual combinations. step wikihow.mul. logical deduction.mul, conlang translation.gen strange stories.mul mul. odd one out.mul, mult data wrangling.gen, temporal sequences.mul, analytic entailment.mul, disambiguation qa.mul, sentence ambiguity.mul. swedish to german proverbs. mul. logical sequence, mul, chess state tracking.ges gen, reasoning about colored objects.mut mul, implicit relations.mul. riddle mens physical intuition.mul simple arithmetic json multiple mul, geometric shapes.gen, gem.gen simp turing concept.gen gen, common morpheme.mul qa wikidata.gen international phonetic alphabet transliterate.gen, similarities abstraction. gen, rephrase.ge gerna emoji movie.gen, qa wikidata. gen, word sorting gen, emoji movie.gen, qa wikidata. periodic elements, gen, hindi question answering genn
goal
Bellow, we plot the net percentage of tasks improved/deproved in each of the BIG-bench categories, out of the tasks that are changed by at least a threshold amount.
H Compute
We use one TPU v3-8 for all our pretraining runs. It takes approximately hours for each pretraining run.
I Broader Impacts
Our work primarily provides a scientific exploration and understanding of the properties of lexinvariant language models. More broadly. these properties could potentially help improve the robustness, generalizability. and reasoning ability of LMs in the future works. In general we don't foresee more specific negative societal impacts from this work other than general misuse of language models.
22

---

Diccoed ef Zuca Calegur bxpeore eliao Thoosbod
Tolns
Decomd Zuck Catagres hxproed vicre 1+48% Choetaot Stutt
Decomd 2ack Catagury Ixprored eitae 48% Zhovebald Stute
tncoue Euck ixprond micke Dinabald stats
Figure 8: BIG-bench results with 0,1,2 and 3 shots.
23


Reviews:
[{"review_id": "d0dPP7Slvu", "reviewer": "Reviewer_xQSK", "summary": "The paper proposes a new language modelling approach, called *lexinvariance*,  where entries in vocabulary are permuted (with an unknown permutation). The paper proves that a lexinvariant language model can predict language well: it converges to a true language model with a polynomial rate in terms of context length. The paper presents empirical evidence to support that. Besides, lexinvariant LM can also infer unknown permutation (i.e. \"deciphering\"). It can also help improve LMs by being used as regularization (similar to dropout).  ", "questions": "* It's confusing when using p as invariant LM (line 84) and a standard LM (the rest of the paper). \n\n* How to derive eq 3 from the definition of p'?\n\n* Line 314, \"lexinvariant LM is one step further away from physical grounding.\" This work hardly supports the claim, because it shows convergence of lexi LM to standard LM rather than to grounded LM.\n\n", "limitations": "It is unclear about the work's application. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "* The work is original. The idea of lexinvariance is interesting, and more importantly, the paper proves its convergence to true language model. Using gaussians to construct a lexivariant LM is a nice idea to reuse the standard LM architecture.\n\n* In terms of quality and clarity, the paper has a good balance between theory and experiment. The theoretical claim is proved, and supported by empirical evidence. The paper also shows possible applications of lexinvariance (deciphering, regularising a LM).\n", "weaknesses": "The main weakness of the paper is that its application is limited. The most promising application is to use it to regularize a LM. However, it is unclear about the benefits of using lexivariant LM over using dropout. \n\nThe experimental setting for char-permutation maybe biased. We should also consider \"space\" as a char. Otherwise, the model would have some good hint for word tokenization.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the encouraging and thoughtful review! We’ve cleared up the notation you highlighted:\n\n> The experimental setting for char-permutation maybe biased. We should also consider \"space\" as a char. Otherwise, the model would have some good hint for word tokenization.\n\nIn the experiments, we do permute spaces and other whitespace. For the concrete examples we give in the paper, we didn't permute the spaces so that they are more readable/understandable. Sorry for the confusion, and we’ll note this in the paper.\n\n> It's confusing when using p as invariant LM (line 84) and a standard LM (the rest of the paper).\n\nGood point! We will update line 84.\n\n> How to derive eq 3 from the definition of p'?\n\nSorry—our notation is pretty confusing here, and we will fix that.  To derive this, note that $$p'(x_{n+1}|x_1,...,x_n) = \\frac{p'(x_1,...,x_{n+1})}{p'(x_1,...,x_n)}  = \\sum_{\\pi} \\frac{1}{C} \\cdot \\frac{p(\\pi^{-1}(x_1,...,x_{n+1}))}{p'(x_1,...,x_n)}$$ where C is the total number of permutations.   Now, multiplying and dividing by $p(\\pi^{-1}(x_1,..,x_n))$, we have that this expression is equal to the following:   $$ \\sum_{\\pi} \\frac{p(\\pi^{-1}(x_1,...,x_{n+1}))}{p(\\pi^{-1}(x_1,..,x_n))} \\cdot \\frac{(1/C)p(\\pi^{-1}(x_1,..,x_n))}{p'(x_1,...,x_n)}.$$  The first expression in the sum is just the conditional probability $p(\\pi^{-1}(x_{n+1})|\\pi^{-1}(x_1,\\ldots,x_n)).$  The numerator of the second expression in the sum is the probability that $p'$ samples $x_1,\\ldots,x_n$ \\emph{and} $\\pi$ is the permutation, and hence this second term is just the probability of $\\pi$ conditioned on $p'$ sampling $x_1,\\ldots,x_n$, as claimed.\n\n> Line 314, \"lexinvariant LM is one step further away from physical grounding.\" This work hardly supports the claim, because it shows convergence of lexi LM to standard LM rather than to grounded LM.\n\nBy one step further away, we mean that it is further removed from physical grounding, as you have suggested. We will rephrase this to be clearer: “Although intuitively, lexinvariant LM appears one step further removed from physical grounding, we find that given enough context they learn the same information.”\n\n> The main weakness of the paper is that its application is limited. The most promising application is to use it to regularize a LM. However, it is unclear about the benefits of using lexivariant LM over using dropout.\nIn the paper, we highlight some potentially interesting applications, especially of regularization towards lexinvariance. However, beyond applications alone, we hope to emphasize the conceptual and scientific value of exploring such a model. \n\nNote that our results on BIG-Bench highlight task types where semi-lexinvariance may benefit LM performance. More broadly, as mentioned in the paper, potential applications for (semi-)lexinvariant LMs could include improving robustness, generalizing across different languages or domains, reasoning over more realistic tasks, and enabling better understanding of LM in general. We believe these applications are promising directions for future work. Moreover, other real-world variations of semi-lexinvariance have appeared since our submission. For example, in [1], randomly re-initializing the embedding layer with some frequency, a variation on a semi-lexinvariant LMs, allows a language model to more easily learn new languages. We believe a deeper understanding of lexinvariance will benefit the community’s understanding of language model generalization.\n\n[1] “Improving Language Plasticity via Pretraining with Active Forgetting” (Chen et al. 2023)"}, {"review_id": "fUGdIl5GiD", "reviewer": "Reviewer_Kmx7", "summary": "The paper investigates the problem in which language model's tokens can be arbitrarily permuted (e.g., randomly interchanging two words $x$ and $y$ and stipulate that the new $x$ takes $y$'s meaning and vice versa -- such a process can happen over the entire vocabulary). The authors offer theoretical analysis and demonstrate that, to certain extent, it may be possible to train a language model invariant to permutations of the vocabulary.", "questions": "* In the proof in Appendix, A, line 482-483, can you elaborate why can we regard samples from $p$ and $\\tilde p$ as the same?", "limitations": "See weaknesses.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "- The paper provides a large set of interesting empirical experiments showcasing that\n- Despite the significant theoretical flaw (see below), the analysis provided in the paper is an interesting (though rather irrelevant) result with a novel proof idea. It is a pity that the derived result is not useful for the paper’s claim. The techniques used in the “proof” is quite creative as far as I can tell.", "weaknesses": "The paper has an important theoretical flaw, which is that the constructed lexinvariant LM *may not* be an LM. Let’s consider a concrete example:\n\nIn the paper, the authors claim that, given an arbitrary LM $p(\\dotsm)$, one can construct a lexinvariant “LM” (call it $p'$) that is “almost equivalent” to $p$. The specific construction offered by the authors is $p'(x_1,\\dots,x_n)=\\mathbb{E}_{\\pi}[p(\\pi^{-1}(x_1),\\dots,\\pi^{-1}(x_n))]$. However, problems arise upon closer inspection. By this definition, we first have\n\n$$\np'(X_1=x_1,X_2=x_2)=\\frac{1}{2}p(X_1=x_1,X_2=x_2)+\\frac{1}{2}p(X_1=x_2,X_2=x_1).\n$$\n\nOn the other hand,\n\n$$\np'(X_1=x_1,X_2=x_2,X_3=x_3)=\\frac{1}{6}\\sum_{\\pi\\in S_3}p(X_1=x_{\\pi^{-1}(1)},X_2=x_{\\pi^{-1}(2)},X_3=x_{\\pi^{-1}(3)}).\n$$\n\nWhen we marginalize the above over $X_3$, we get\n\n$$\np'(X_1=x_1,X_2=x_2)=\\frac{1}{6}\\Big(\np(X_1=x_1,X_2=x_2)+\np(X_1=x_1,X_3=x_1)+\np(X_1=x_2,X_2=x_1)+\np(X_1=x_2,X_3=x_1)+\np(X_2=x_1,X_3=x_2)+\np(X_2=x_2,X_3=x_1)\n\\Big).\n$$\n\nWe can clearly see that, for most LM’s, the above doesn’t agree with the first marginal (unless they satisfy very special conditions)! This shows that, the constructed lexinvariant “LM” isn’t in fact an “LM”. It’s a sequence of incompatible joint distributions. In other words, one cannot construct a stochastic process based on the definition of $p'$ by invoking Kolmogorov’s extension theorem, because the marginals are incompatible.\n\nBased on the this, the paper’s various premises and conclusions start to fall apart.\n\nFirst of all, Theorem 2.1 becomes a “correct” but irrelevant result (it is slightly incorect in the sense that $p'$ is no longer a languge model). At best, Theorem 2.1 can be interpreted as that for an arbitrary LM, there exists a sequence of (incomptaible) conditional distributions such that, when $x_{1:T}$ is sampled from $p$, w.h.p., the (incompatible) conditionals are close to conditionals of $p$ (this is what appears to be what the proof is proving, though I have not checked the 6-page proof in the appendix too closely and can’t speak to its correctness). Such an understanding of this result would significantly undermine various claims in the paper in the following ways:\n\n1. First, one cannot conclude from the paper that given an arbitrary LM, there exists a “symmetrized” (i.e., lexinvariant) approximation of it. Therefore, one cannot, at least in theory, conclude that as the context gets longer, the “distance” between some lexinvariant model to an arbitrary LM will approach 0. \n    1. It is also quite likely that there exists such counterexamples — an LM in which no symmetric LM is a good approximation of it over any context length. If the authors are trying to provide a proof in that direction in the future, they may want to make an attempt at finding such counterexamples.\n    2. Furthermore, the empirical evidence is inconclusive as to the question of whether the specific implementation of the lexinvariant LM approximates the true conditionals. One may also look at Figure 3 and 7 and say that the perplexity curves have flattened out and that there is a systemic bias between the lexinvariant model and the standard language model.\n2. Next, since $p'(\\dotsm)$ is a sequence of incompatible joints, it is unclear if sampling from such a sequence of conditionals will yield something that can be justified.\n\nIf the authors cannot repair this theoretical flaw, I cannot recommend the paper accepted as-is since the paper’s current narrative revolves around a “theoretical proof then empirical validation” narrative. If the theory turns out to be irreparable, the paper should be rephrased as a series of experiments without theoretical underpinnings.\n\nFinally, a minor detail is that the presentation frequently switches notation for unclear reasons, which is very confusing. Most notably, it is unclear why the paper sometimes use $p$ but then immediately switches to $\\mathcal{P}$ (e.g., in Eq.(3), $\\mathcal{P}$ appears without introduction; similar situation happens in line 481).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "This review seems to be based on a misunderstanding of the key concept behind our paper (Equation (1)): we are considering permuting the underlying alphabet/\"lexical symbols\" as in a  \"substitution cipher\", NOT changing the order of the tokens. For example, for a lexinvariant LM, p(“a a b”) = p(“b b a”) but p(“a a b”) $\\neq$ p(“a b a”)! The motivation for this is to consider a language model that only looks at the structure of repetitions of tokens, and does not have any prior understanding of the meaning or usage of different tokens. Indeed, if this was based on permuting the order of the words, then this would not be an LM.\n\nTo clarify and reiterate, from lines 36-37: “we define a lexical permutation to be a one-to-one mapping of a set of lexical symbols onto itself” and “$p(x_1,...,x_n)=p(\\pi(x_1),...,\\pi(x_n)) \\forall \\pi$”. This means that the symbols in the lexicon are permuted, not the token order. \n\nThe example on the line following Equation (1) in the paper further clarifies this: “For example, a lexinvariant language model (whose vocabulary is letters and space) should assign the same probability to the phrase “a big banana” as “e cop cekeke” because the two are the same up to the permutation $\\pi$={a->e, b->c, i->o, n->k, g->p,···}”. This would not be true if the language model were permuting the order.\n\nIf the above is not clear, please initiate a dialogue with us – we are more than willing to work collaboratively to resolve this.  We also hope that you revisit our paper with this new interpretation in mind, as this sort of permutation invariance is central to the motivation behind our paper.\n\nWe will revise the writing to reiterate that we are referring to permuting the alphabet as in a substitution cipher, as opposed to permuting the order of the tokens, to ensure that this sort of confusion does not happen.\n\n—Responses to other questions—\n\n> \"In the proof in Appendix, A, line 482-483, can you elaborate why can we regard samples from $p$ and $\\tilde{p}$  as the same?\"\n\nSure: First we give a high-level intuitive explanation, then a more technical one. Suppose you care about length T sequences.  If p is a distribution over length T sequences, we essentially define $\\tilde{p}$ as follows: with probability 0.99, draw a length T sequence from p.  With the remaining probability, draw a sequence according to p and for each $i=1,..,T$, replace the ith token with a uniformly random token with probability 1/T.   The total variation distance between length T sequences from $p$ and $\\tilde{p}$ is at most 0.01 and hence any property that holds for sequences from \\tilde{p} with probability c must also hold for sequences drawn from p with probability at least c - 0.01.  The reason for switching to \\tilde{p} is that for any given prefix $x_1,..,x_i$, there is a nonzero probability that $x_{i+1}$ takes each possible value. And, not only is this probability nonzero, but the logarithm of this probability is reasonably bounded. \n\nSlightly more formally, given the prefix $x_1,..,x_{n-1}, \\tilde{p}$ and $p$ have ALMOST the same distributions over $x_n$—specifically $\\tilde{p}$ assigns a convex combination of the distribution assigned by p, and the uniform distribution over tokens, where the uniform distribution has weight $\\sigma$. $\\sigma$ is chosen to be so small (namely << 1/T) such that the total variation distance between length T sequences from p and $\\tilde{p}$ is small, and hence these distributions can be coupled with all but small probability (which contributes to the delta failure probability in the analysis).  \n\n> \"it is unclear why the paper sometimes use p but then immediately switches to \\mathcal{P},  (e.g., in Eq.(3))\"\n\nYes, sorry – we will improve this confusing notation. $\\mathcal{P}(\\pi | x_1,x_2,..)$ refers to the probability of permutation pi, given that $x_1,x_2$,.. are drawn from p',  where p is referring to the original (non-lexinvariant) language model.  On line 114, the $p(\\pi|...)$ should have been $\\mathcal{P}$ and that typo makes it harder to parse Equation 3."}, {"review_id": "zuasanJpga", "reviewer": "Reviewer_zdSX", "summary": "This work explores neural language modelling without fixed token embeddings. Being invariant to symbols forces the model to rely on discovering patterns across sequences (e.g. co-occurrences, repeating symbols) that enable it to infer the underlying symbol sequence. For example, suppose the symbol-substituted sequence 123 123 145673 corresponds to “bye bye birdie”, the model can learn to predict the next symbol given enough training examples of different mappings of “bye bye” and, importantly, a sufficiently long context.\n\nThe authors start out by formally defining lexinvariance and proving its convergence to standard LMs. Their theorem establishes theoretically that lexinvariant LM performance converges to standard LM performance quite efficiently as context length grows. This paves the way to implement a lexinvariant LM. During training, each token is represented with random Gaussian embeddings. Identical tokens are mapped to the same embedding within a sequence but to different embeddings across different sequences. Results show that a character-level invariant LM converges to standard LM performance as context length grows, reflecting the convergence theorem empirically. It is also shown that the invariant LM is implicitly learning Bayesian deciphering over different potential symbol permutations, using probing to extract model ciphers. Finally, the authors introduce some potential practical uses of lexinvariance, such as improved performance on in-context symbol manipulation tasks and LM lexical regularisation. \n", "questions": "1. Include more examples of semantic deciphering. If possible, include demantic deciphering accuracy compared to a random multiple choice selection baseline. It’s clear from your current example that the model can figure out that has to copy one of the possible answers, but not clear if the correct prediction of “coffee” is down to anything other than chance.\n2. Could you please clarify the link you are making to ByT5?\n\n\n\n-- Typos --\n- Fix typo line 45 “doesn’t”.\n", "limitations": "NA", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "-- #1 --\n\nThe theoretical and empirical findings of the paper are valuable contributions to our knowledge about the capabilities of language models and neural sequence models more generally. Fixed token embeddings are one of the core building blocks of LLMs and this paper explores LM behavior in their absence, leading to findings that many in the deep learning research community would find interesting.\n\n-- #2 --\n\nThe sections on symbol deciphering and uncertainty provide a useful analysis of how invariant LMs work under the hood. The roles of Bayesian deciphering and context length are made clear. The authors have proposed a model and explained a good deal about how it works. This is a nice contribution to the NLP interpretability literature.\n\n-- #3 --\n\nThe potential practical value of lexinvariant LMs (symbol manipulation tasks and lexical regularisation) are promising and worth further investigation. I could see this work being taken up by future researchers.\n", "weaknesses": "-- #1 --\n\nThe probing experiments can be improved by discussing some potential pitfalls of the technique in this context and/or including more results. The main pitfall to consider is the fact that the probe could be responsible for learning part of the cipher, as opposed to the lexinvariant LM. How do we separate what the lexinvariant LM has learned from what the probe learns by itself? In the extreme case of the lexinvariant LM not learning any deciphering (not realistic, just to demonstrate) the probe might still be able to learn some deciphering based on the contextual information in the LM representations. In the more realistic case, suppose the lexinvariant learns the entire cipher except for a few token mappings. Then the probe could infer the remaining mappings during its training. This is unlikely given the task complexity of deciphering, but it could be worth discussing. The paper would be strengthened by adding results that separate model knowledge from probe knowledge e.g. including cipher probe accuracy for a randomly initialised model.  See section 4.1 of this paper https://direct.mit.edu/coli/article/48/1/207/107571/Probing-Classifiers-Promises-Shortcomings-and for an overview of potential control methods.\n\n-- #2 --\n\nThe related works section is slightly disjointed. I understand that this is a result of the novelty of your idea and the far-reaching influences of the work. However, you could consider grouping the related work a bit more coherently. 4.1 and 4.3 could be connected as symbol grounding / invariance as augmentation, while 4.4 and 4.5 could be connected as downstream tasks related to your idea.\n* The symbol grounding subsection is interesting but requires slightly more explanation or references to previous works to clarify the matter to those unfamiliar with the problem. For example, Searle’s Chinese room argument is mentioned only by name.\n* The connection to ByT5 is not clear to me. In the extreme ByT5 would not become lexinvariant, it would just operate on finer grained units. Lexinvariance could be applied to any sequence unit or tokenisation scheme. If I’m misunderstanding something, please clarify, or perhaps consider omitting the subsection on ByT5.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to express our appreciation for the comprehensive and encouraging feedback. We hope our response addresses any points of contention and believe the suggestions have already meaningfully strengthened the work. Thank you!\n\n> The probing experiments can be improved by discussing some potential pitfalls of the technique in this context and/or including more results… The paper would be strengthened by adding results that separate model knowledge from probe knowledge e.g. including cipher probe accuracy for a randomly initialised model. See section 4.1 of this paper https://direct.mit.edu/coli/article/48/1/207/107571/Probing-Classifiers-Promises-Shortcomings-and for an overview of potential control methods.\n\nThank you for the suggestion! Based on this we ran an additional experiment where we trained a probe on a randomly initialized model with the same hyperparameters as in the experiment discussed in the paragraph from lines 212-219. While the trained probe substantially improves over random chance performance (i.e., when the language model and probe are both randomly initialized, the average precision is 0.8%), the 5.9% precision we observe is significantly worse than the 99.6% precision with the trained lexinvariant LM. We will also include this in the paper.\n\n> The related works section is slightly disjointed. I understand that this is a result of the novelty of your idea and the far-reaching influences of the work. However, you could consider grouping the related work a bit more coherently. 4.1 and 4.3 could be connected as symbol grounding / invariance as augmentation, while 4.4 and 4.5 could be connected as downstream tasks related to your idea.\n\nThanks for raising this point! We agree that 4.4 and 4.5 can fairly naturally be combined. 4.1 is much more abstract than 4.3, so we believe it may be confusing to combine these, but we will move 4.3 earlier to immediately follow 4.1.\n\n> The symbol grounding subsection is interesting but requires slightly more explanation or references to previous works to clarify the matter to those unfamiliar with the problem. For example, Searle’s Chinese room argument is mentioned only by name.\n\nAbsolutely - we’d be happy to elaborate on these discussions and references. For example, we will clarify that the Chinese room argument describes a person in a room given a step-by-step set of instructions by which they can respond to Chinese text with reasonable-sounding Chinese text. To an outside observer, the person in the room appears to understand Chinese, but the individual does not know a word of Chinese. This is widely used to argue that understanding language requires grounding the symbols in the real world.\n\n> The connection to ByT5 is not clear to me. In the extreme ByT5 would not become lexinvariant, it would just operate on finer grained units. Lexinvariance could be applied to any sequence unit or tokenisation scheme. If I’m misunderstanding something, please clarify, or perhaps consider omitting the subsection on ByT5. … Could you please clarify the link you are making to ByT5?\n\nThanks for bringing this up - we agree that this subsection could be clearer. There are two relevant points. First, consider, in the extreme case, a language model trained only on a binary representation of text where the only tokens are 0 and 1. The embeddings of each individual bit would have virtually no independent meaning, and the model would only have to identify whether 0->0 or 0->1. Byte-level models are part of the way there, with a dramatically smaller and less semantically rich vocabulary than standard language models. Second, there's the question of whether lexinvariant models have a useful inductive bias, and this has to do with the meaningfulness of individual tokens. Words can be argued to be meaningful / have relatively stable meaning (the whole field of lexical semantics wouldn't exist otherwise), but bytes do not.\n\n> Include more examples of semantic deciphering. If possible, include demantic deciphering accuracy compared to a random multiple choice selection baseline. It’s clear from your current example that the model can figure out that has to copy one of the possible answers, but not clear if the correct prediction of “coffee” is down to anything other than chance.\n\nYour point that we should highlight the corresponding probabilities is well-taken: for this example, the probability (at temperature=1) of coffee being selected is 56%, substantially higher than the next-highest probability of restaurant at 27%, music at 12%, or father at 5%. Note that this particular example was originally intended as a visualization / case-study."}, {"review_id": "vLlZUsHJaX", "reviewer": "Reviewer_1RPb", "summary": "This paper presents “lexinvariant models” which eschew learning an embedding matrix for the symbols in the sequence and instead of modeling the identity of the symbols, they model the repetition and co-occurence patterns of the symbols in a sequence. Specifically, these symbols are interchangeable among all the items in the vocabulary and can be trained by drawing random vectors from a normal distribution to represent each symbol per sequence. This model is theoretically analyzed and it is shown that it can match with a standard autoregressive language model distribution as the context length increases. The models are mainly analyzed on symbol manipulation and decipherment tasks on synthetically generated data. A variant is also studied on natural language and code data.\n", "questions": "See above.", "limitations": "See above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "– This is an interesting class of models and an intriguing question that investigates how far could we go with just the surface patterns of symbols and without knowing the symbols.\n\n– The experiments on synthetic data show that  such models have strong implicit decipherment capabilities and perform well on symbol manipulation tasks. This raises a possibility to augment standard language models with ideas from this approach to make the standard models more robust and performant on symbol manipulation and variable binding tasks.\n\n– The ideas are novel and the synthetic experiments are well-designed to explore the various facets of the models. The related work section does a good job of linking the ideas in this paper to other related topics in language modeling and symbolic representation.\n", "weaknesses": "– The experiments are mostly on synthetic data and tasks. The performance on real world data lags behind the simple standard approach. While interesting, the practical utility of these models is still questionable and their applicability feels limited to controlled toyish scenarios.\n\n– The theoretical analysis seems to have fairly loose bounds. Especially, the distribution matching looks feasible only for impractical long context lengths and there might be a large gap for realistic context lengths that the models and data typically work with today. Also, \\delta less than 0.5 is fairly loose.\n\n– Figure 2 seems awkward in the sense it implies that the model is essentially mixture of first order HMMs which seems far removed from the neural autoregressive models actually used in the experiments.\n\n– Section 3.2: 100 sequences seem too few as is suggested by the large variance of the proposed approach. Although the standard model seems to have a much smaller variance across the 100 sequences. This shows a further potential drawback of the proposed approach.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the supportive and useful feedback! We’ve addressed your points below:\n\n> The theoretical analysis seems to have fairly loose bounds. Especially, the distribution matching looks feasible only for impractical long context lengths and there might be a large gap for realistic context lengths that the models and data typically work with today. Also, \\delta less than 0.5 is fairly loose.\n\nFirst, an important clarification: $\\delta$ is the probability of failure (not success)! Our theorem shows that this can be set to any arbitrarily small positive constant—if $\\delta$ is chosen as 0.001, then the probabilities assigned by the lexinvariant model will be within $\\varepsilon$ of the language model, with probability at least 99.9%, provided the sequence length is at least the claimed bound. Encouragingly, this bound scales only with a polylogarithmic dependence on $1/\\delta$, polynomial dependence on $1/\\epsilon$, and near-linear dependence on the alphabet size, $d$. The surprising conceptual punchline is that this sequence length is a function of only the accuracy/failure parameters, and the alphabet size, and does not depend on any properties of the language model beyond the alphabet size, such as the entropy rate, etc.\n\n> Figure 2 seems awkward in the sense it implies that the model is essentially mixture of first order HMMs which seems far removed from the neural autoregressive models actually used in the experiments.\n\nThe aim of Figure 2 is to help highlight the relationship between a standard LM and a lexinvariant LM: namely, as long as one can sample from a standard language model’s distribution and the permutation distribution, one can construct a lexinvariant LM. While we do not assume an HMM underlying the language, we believe that this is an intuitive way to convey this idea - however, we are, of course, open to any suggestions for how to make this clearer.\n\n> Section 3.2: 100 sequences seem too few as is suggested by the large variance of the proposed approach. Although the standard model seems to have a much smaller variance across the 100 sequences. This shows a further potential drawback of the proposed approach. \n\nThe comment on 100 sequences refers to Figure 3, where our main objective is to visualize the trends in the perplexity and variance w.r.t. context length, which are fairly stable. While it’s true that the convergence is slow w.r.t. context length, we would also like to highlight that, as longer context lengths become more common, not only do we expect the model to converge to a standard language model, but we also expect to be able to identify which components of the context a lexinvariant language model uses for its language modeling.\n\n> While interesting, the practical utility of these models is still questionable and their applicability feels limited to controlled toyish scenarios.\n\nOur primary goal was ultimately to understand the role and necessity of stable lexicons, both empirically and theoretically, as they underlie all modern language models. The overarching motivation, as discussed throughout the introduction, is the scientific exploration of a concept that is central to all currently existing language models. More broadly, as mentioned in the paper, potential applications for (semi-)lexinvariant LMs could include improving robustness, generalizing across different languages or domains, reasoning over more realistic tasks, and enabling better understanding of LM in general. We believe these applications are promising directions for future work. "}, {"review_id": "xs8YGMqir0", "reviewer": "Reviewer_gQ1h", "summary": "This paper introduces lexinvariant language models, where the probability of any sequence is equal up to permutation of the vocabulary (e.g. P(A A B C) = P(B B C A)). In practice, the token embeddings within a Transformer model are replaced by random Gaussian vectors, which are consistent across a single sequence, but not over different examples. The authors show that a lexinvariant language model converges to modeling the true language distribution, in part because it is possible to infer the permutation (given a long enough sequence). While lexinvariant language models are not practical for many tasks, the paper shows that they can obtain better performance on some synthetic reasoning tasks. The authors also briefly discuss regularizing models with lexinvariance.", "questions": "Is there a specific reason why spaces are not permuted for character-level examples? I would assume it's to simplify the presentation.\n\nHow long are the prompts for the synthetic reasoning tasks?\n\n[L45] Typo in doesnt", "limitations": "Yes, limitations are discussed in the introduction (and elsewhere in the paper).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To my knowledge, lexinvariance has not been explored before previously for natural language.\n\nThe experiments are pretty thorough, for example by demonstrating how lexinvariant models converge, exposing how to recover cipher permutations (with an additional probe), and showing superior performance on synthetic reasoning tasks where tokens have no predefined meaning.\n\nThe paper is generally clear and well-organized. It introduces the notion of lexinvariance, presents some theoretical properties (or characteristics) and describes how to construct a lexinvariant LM.\n\nThis paper challenges (to some degree) the notion that stable word/token embeddings are required for language modeling.", "weaknesses": "While the authors acknowledge the practical limitations of the approach, convergence can become quite slow as vocabulary size grows. \n\nGiven that the approach is mostly suitable for small vocabularies, a more thorough comparison with byte-level LMs (which also use a small vocabulary and tokens have limited semantics) could be helpful.\n\nWhile I find the paper interesting, the motivation behind the problem/approach is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful and thoughtful review!\n\n> While the authors acknowledge the practical limitations of the approach, convergence can become quite slow as vocabulary size grows.\n\nWhile a purely lexinvariant model may have practical limitations, we explore and discuss the potential benefits of regularization towards lexinvariance as a technique to improve language model performance in certain contexts and demonstrate improvements. We would also like to highlight that, as longer context lengths become more common, not only do we expect the model to converge to a standard language model, but we also expect to be able to identify which components of the context a lexinvariant language model uses for its language modeling.\n\n> Given that the approach is mostly suitable for small vocabularies, a more thorough comparison with byte-level LMs (which also use a small vocabulary and tokens have limited semantics) could be helpful.\n\nThis is a good suggestion, and one might expect there to be little gap between byte-level LMs and their lexinvariant analogs. This was the motivation for us to consider multiple vocabulary sizes. As expected, smaller vocabularies appear to result in faster convergence. \n\n> While I find the paper interesting, the motivation behind the problem/approach is unclear.\n\nThe overarching motivation, as discussed throughout the introduction, is the scientific exploration of a concept that is central to all currently existing language models. More broadly, as mentioned in the paper, potential applications for (semi-)lexinvariant LMs could include improving robustness, generalizing across different languages or domains, reasoning over more realistic tasks, and enabling better understanding of LM in general. We believe these applications are promising directions for future work. Moreover, other real-world variations of semi-lexinvariance have appeared since our submission. For example, in [1], randomly re-initializing the embedding layer with some frequency, a variation on a semi-lexinvariant LMs, allows a language model to more easily learn new languages. We believe a deeper understanding of lexinvariance will benefit the community’s understanding of language model generalization.\n\n[1] “Improving Language Plasticity via Pretraining with Active Forgetting” (Chen et al. 2023)\n\n> Is there a specific reason why spaces are not permuted for character-level examples? I would assume it's to simplify the presentation.\n\nYes, this is done to simplify the presentation. In the experiments, we do permute spaces and other whitespace. For the concrete examples we give in the paper, we didn't permute the spaces so that they are more readable/understandable. Sorry for the confusion, and we’ll note this in the paper.\n\n> How long are the prompts for the synthetic reasoning tasks?\n\nThe permutation examples include, at random, 1 to 4 context statements and a final query. The lookup examples include 3 to 7 context statements and a final query. "}]

Author rebuttal:
We would like to thank the reviewers for their thoughtful and encouraging comments. In particular, we appreciate each reviewer’s comments on the novelty of the notion of lexinvariance and the usefulness of the experiments. 

Aside from one review which appears to be predicated on a misunderstanding (The review from Kmzd appears to misinterpret lexinvariance as permuting the order of the tokens rather than as invariance to a substitution cipher), the feedback was quite positive.

However, we also acknowledge the reviewers’ questions regarding the practical usefulness of lexinvariant LMs, especially in connection with the real-world convergence rate. In general, we would like to emphasize that our current work focuses on understanding lexinvariant LMs from the perspective of scientific curiosity. 

In addition, multiple reviewers highlighted instances of unclear or confusing notation. We will clear these up.

Thank you again!

Meta-review: The paper proposes a language model that is invariant to the identity of lexical symbols. A number of experiments on language modelling and synthetic tasks are performed. The paper makes a valuable contribution towards studying the properties of language models, and could contribute towards better understanding of the interpretability and regularization of language models. While the reviews raised some concerns about the limited practical applicability of the model which could limit the impact of the paper, there is clear value in the paper as a scientific study of language models. The reviewer who thought that the theoretical basis of the paper is flawed never responded to the rebuttal, but I am satisfied with the authors' response.
Decision: Accept (spotlight)