Recovering Knowledge by Hardening Language Models

The authors propose a method of converting an LSTM or GPT LM trained on a regular language to a deterministic finite automaton (DFA) that approximates the LM. They test their method on 5 regular languages belonging to two different circuit complexity classes (AC0 and TC0). The languages also have different "context complexity", in that some only require a local, finite suffix of a string to correctly recognize, and some require global context. They define a regex/DFA for each language and use it to sample datasets of positive examples. They train neural LMs on it from scratch. Afterwards, they extract the hidden representations for each prefix of each string in the dataset. They apply k-means clustering and denoising to convert them to states of a DFA. They find that the extracted DFA often has higher precision than the original LM, and that neural LM accuracy depends mostly on context complexity.

TL;DR: A deeply misguided, inconsistent, and confused text further burdened by its poor comprehension of the subfield's literature and self-congratulatory overselling.

The paper presents LaMFA, a method for constructing finite automata from hidden states of language models. The design decisions comprising LaMFA outnumber the automata samples/experimental setups (a grand total of 5) by a factor of 2, thus making the first doubts of the interpretability of the results. The method presented, LaMFA, is an apparent simplification of the Louvain method heavily tailored toward the carefully chosen experimental automata.

Somewhat grandiosely, he paper claims to "shed light on the internal mechanism of language models" (L053), "investigate how linguistic knowledge is encoded and compressed" (L098), "draw new insights on the interplay between architectures and language complexity" (L103), "yield significant insights into the behavior of LMs" (L415), and "mark a significant advancement in model interpretability and generalization" (L521). None of these claims about the contents of the paper are true, as most of these have no experimental counterpart in the text, and virtually every conclusion about the nature of language models that is drawn can be traced back to a design decision.

As a brief example of the prevalence of these issues: A claim is made that "the LaMFA-DFA of LSTM is exactly equivalent to the ground-truth regex" (L482). However, this is only a consequence of Algorithm 2 merging the previously disjoint cluster states. Okay, a counter-claim can be made that this is the intended function of Algorithm 2. But why then does "the DFA of GPT-tiny contain an extra state" (L483) even after the Algorithm 2 merge that was supposed to collapse it? You can't have it both ways; the successful recovery and unsuccessful recovery of a DFA cannot both be findings simultaneously. This would perhaps be acceptable if we had more samples and could draw statistical conclusions, but 5 languages are not nearly enough to do so -- a statistically significant sample should be considered instead and evaluated in an automated fashion (see Weakness 7 for more guidance on this). By the way, the DFA alter-GPT-tiny is incorrect as it also accepts the string "1" which is not in the alter language. All in all, the immediately-following claim that "these observations suggest that larger models may learn more nuanced representations of language" is a deliberate obfuscation of the contradictions arising in L480-L485. The use of nuanced is nothing less than a disconcerting, blatant attempt to pass "it worked once and it did not work once" for a finding.

While I touch on more issues with the paper in the weaknesses, it is important to note that this work is also flawed conceptually. In a surprising omission of related work, the text appears to be utterly oblivious to the results of H. Siegelmann from the late 90s giving constructive proofs to the Turing-completeness of RNN-based architectures including GRU/LSTM (rather surprisingly, however, the text goes into great lengths to cite the likes of Kleene, Rabin, Chomsky, or McNaughton&Yamada). Many of the (non-)findings of Sections 5.2.1-5.2.2 are focusing on the artifacts of arguably improper gradient-based training schedule of the selected architectures, as each of the 5 regular languages considered can be realized as RNNs following the construction of the seminal proof. Since both LSTMs (dated work, Siegelmann) and Transformers (contemporary work, Svete) can be constructed by hand to recognize simple finite automata, the insights the paper sets out to provide are already familiar from theory, and its contribution is reduced to a tedious construction and an entirely unconvincing experimentation. See also Weakness 6.

It is my recommendation that the work is not published. It should be instead revisited from the very beginning, refocused on the contribution of LaMFA, supported by further experimentation vouching for its utility and advantages over the omitted previous work on state merging, and only then submitted for review.

This paper introduces a method for extracting finite-state automata (FSAs) from trained language models, called LaMFA. The approach clusters string prefix representations in the model’s representation space and builds FSAs based on these clusters. The authors add a new denoising step to make clustering more stable and accurate. They apply LaMFA to both transformer and LSTM language models trained on five regular languages and compare the extracted FSAs to the actual FSAs for these languages. They find that the extracted automata are usually not identical to the original ones—they’re often larger—but they tend to generalize better than the models from which they were extracted.

This paper studies how language models learn regular languages. It proposes an algorithm LaMFA that can recover the finite state automaton corresponding to the regular language from the neural language model trained on the same language.

LaMFA first constructs the states in DFA by clustering the features generated in language models and then estimates the transition function by looking at strings with and without the last token.

They found that LaMFA-extracted DFAs can recover the full knowledge of the regular language and perform better than neural language models in out-of-distribution scenarios.

Dear Reviewers,

We would like to express our sincere gratitude for the time and effort you have dedicated to reviewing our submission. After careful consideration, we have decided to withdraw our paper from the review process.

We agree that this work is not suitable for ICLR in its current stage and greatly value your insightful feedback. We will revise the paper according to your suggestions to improve its quality. Thank you for your efforts in making this research area better through your thoughtful reviews.

Best regards, Submission14201 Authors