Representing Rule-based Chatbots with Transformers (2025)

Abstract: What kind of internal mechanisms might Transformers use to conduct fluid, natural-sounding conversations? Prior work has illustrated by construction how Transformers can solve various synthetic tasks, such as sorting a list or recognizing formal languages, but it remains unclear how to extend this approach to a conversational setting. In this work, we propose using ELIZA, a classic rule-based chatbot, as a setting for formal, mechanistic analysis of Transformer-based chatbots. ELIZA allows us to formally model key aspects of conversation, including local pattern matching and long-term dialogue state tracking. We first present a theoretical construction of a Transformer that implements the ELIZA chatbot. Building on prior constructions, particularly those for simulating finite-state automata, we show how simpler mechanisms can be composed and extended to produce more sophisticated behavior. Next, we conduct a set of empirical analyses of Transformers trained on synthetically generated ELIZA conversations. Our analysis illustrates the kinds of mechanisms these models tend to prefer—for example, models favor an induction head mechanism over a more precise, position-based copying mechanism; and using intermediate generations to simulate recurrent data structures, akin to an implicit scratchpad or Chain-of-Thought.Overall, by drawing an explicit connection between neural chatbots and interpretable, symbolic mechanisms, our results provide a new framework for the mechanistic analysis of conversational agents.

## introduction one approach to understanding transformers @xcite is to identify explicit mechanisms that a transformer could theoretically use to solve a particular task. this bottom-up approach has been used to characterize the expres-sivity of the transformer architecture for a variety of synthetic and formal language tasks, including regular languages @xcite , dyck languages @xcite , and pcfgs @xcite . however, this line of work has focused mainly on simple algorithmic tasks applied to single-sentence inputs, and it remains an open question whether we can extend these approaches to understand how transformers could conduct natural-sounding conversations. in this work, we propose to use rule-based chatbots for formal and mechanistic analysis of neural conversational agents. we first present theoretical constructions of how a transformer can implement a classic rule-based chatbot algorithm, and then we use these constructions to guide a series of empirical investigations into how transformers learn to solve such tasks when they are trained on synthetic conversation data. in particular, we focus on eliza @xcite , one of the first artificial chatbots. the eliza algorithm is simple but exhibits a number of sophisticated conversational behaviors (fig. 1 ). the majority of eliza's behavior is based on local pattern/transformation rules: eliza compares the user's input to a set of templates, and responds by reassembling the input according to an associated transformation rule. however, eliza also employs several mechanisms that make use of the full conversational history, including a mechanism for varying its responses between successive turns, and a memory queue to refer to turns from the beginning of the conversation. eliza therefore offers a natural next step from simpler, sentence-level settings, comprising both local pattern matching and long-distance dialogue state tracking. first, we describe how a decoder-only transformer could implement the eliza program (fig. 2 ). we start by showing how we can use constructions from prior work as modular building blocks-in particular, by decomposing the task into figure 1 : an example eliza conversation, adapted from @xcite (left) and the corresponding parts of the eliza program (right). eliza uses both local pattern matching and two long-term memory mechanisms (cycling through responses, and a memory queue). at each turn, eliza compares the most recent input to a set of decomposition templates and applies one of the associated reassembly rules. the 0 symbols in the decomposition template are wildcards, which are used to decompose the user's input into segments. a response is generated by replacing each numeral in the reassembly rule with corresponding segment of the user's input. if a template is matched more than once in a conversation, eliza cycles through a list of possible reassembly rules. if the input contains a special keyword ("my"), eliza stores it in a memory queue; later, if an input does not match any of the templates, eliza reads the first memory from the queue. a cascade of finite state automata @xcite , along with a copying mechanism for generating responses. this decomposition attests to the usefulness of algebraic automata as building blocks for characterizing complex behavior in transformers. on the other hand, we also identify alternative constructions for key subtasks, including a more robust copying mechanism (sec. 3.2) and memory mechanisms (sec. 3.3) that make use of intermediate eliza outputs-akin to a scratchpad @xcite or chain-of-thought @xcite . these alternative constructions inform our empirical investigations later on. incidentally, the eliza framework happens to be turing complete @xcite ; our results therefore lead to a simple, alternative construction for a transformer that simulates a turing machine, which we discuss in appendix b.4. next, we generate a dataset of eliza transcripts and train transformers to simulate the eliza algorithm (sec. 4). we investigate which aspects of the task are difficult for the models to learn, and find that models struggle the most with precise copying and with the memory queue mechanism-which requires the composition of several distinct mechanisms. we further study which of our hypothesized constructions better match what the models learn, and how the result varies according to the data distribution. for copying, we find that models have a strong bias for an induction head mechanism @xcite , leading to worse performance on sequences with a high degree of internal repetition. for the memory components, we find that models make use of intermediate outputs to simulate the relevant data structures, which underscores the importance of considering intermediate computation in understanding transformers, even without an explicit scratchpad or chain-of-thought. together, our results illustrate that eliza offers a rich setting for mechanistic analysis of learning dynamics, allowing us to decompose the task into subtasks, conduct fine-grained behavioral analysis, and connect this analysis to predictions about the model's mechanisms. by drawing an explicit connection between neural chatbots and interpretable, symbolic mechanisms, our results offer a new setting for an algorithm-level understanding of conversational agents. we conclude by discussing the broader implications of our results for future work on interpretability and the science of language models. ## background: eliza we start by describing the eliza algorithm @xcite , following the presentation of @xcite . the eliza algorithm can be decomposed into two types of behavior: local pattern matching and long-term memory, illustrated in fig. 1 . we discuss eliza in more detail in appendix a. ## constructions now we present our constructions for implementing the eliza program with a transformer decoder. we build the construction modularly by composing constructions for each subtask in eliza (fig. 2 ). for the key subtasks, we identify multiple possible mechanisms a transformer could use, some building on prior constructions-in particular, for simulating finite state automata-and others drawing on intuitions from methods like chainof-thought @xcite . in section 4, we will investigate empirically which of these options are a better match for what the models learn. we describe the constructions at a high level in this section and defer the details to appendix b. ## experiments now we investigate how transformers learn the eliza program in practice when we train them on conversation transcripts. we focus on investigating how the model solves the subtasks for which we identified more than one possible construction. ## conclusion in this work, we constructed a transformer that implements the classic eliza chatbot algorithm. we then trained transformers on eliza conversation transcripts and examined how well the models matched our construction. our constructions and dataset raise a number of possibilities for future research, including as a benchmark for automated interpretability methods, and as a setting for mechanistic analysis of learning dynamics. limitations our constructions illustrate some of the ways that transformers could implement eliza, but they are not exhaustive, and they might not correspond to the solutions that transformers actually learn. characterizing the mechanisms that models learn empirically is a key challenge for future work on interpretability. second, we conduct some analysis of the mechanisms that models learn, but we do not conduct an exhaustive mechanistic analysis; future work could conduct further analysis using other interpretability techniques, such as causal methods (e.g. @xcite @xcite , to understand how the mechanisms are encoded in the model's weights. third, we do not investigate whether open-source conversational models use similar mechanisms to the ones we considered here. it is not straightforward to evaluate open-source conversational models on our synthetic task, because it is difficult to teach a model to follow the eliza algorithm and rules without further fine-tuning. one possible direction for future work is to prompt an instructiontuned model to follow the eliza rules and investigate which mechanisms it uses. more generally, while eliza offers a setting for investigating a number of aspects of conversations, there is a substantial gap between eliza and real-world chatbots. for example, eliza is a deterministic program, whereas most real-world chatbots are trained on data with more stochasticity. one possible path for future research is to gradually extend the rule-based chatbot framework to include more of the key phenomena observed in modern language models, with the goal of understanding how these behaviors can be implemented with interpretable transformer mechanisms. these include more sophisticated pattern matching (for example, extending from regular expressions to semantic parsing); in-context learning; and explicit chain-of-thought reasoning. hattie zhou, arwen bradley, etai littwin, noam razin, omid saremi, josh susskind, samy bengio, and preetum nakkiran. 2024. what algorithms can transformers learn? a study in length generalization. in international conference on learning representations (iclr).