Evaluating the World Model Implicit in a Generative Model

Authors: keyon  vafa
justin y chen mit
jon  kleinberg
sendhil  mullainathan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:27:08

Abstract: Recent work suggests that large language models may implicitly learn world models. How should we assess this possibility? We formalize this question for the case where the underlying reality is governed by a deterministic finite automaton. This includes problems as diverse as simple logical reasoning, geographic navigation, game-playing, and chemistry. We propose new evaluation metrics for world model recovery inspired by the classic Myhill-Nerode theorem from language theory. We illustrate their utility in three domains: game playing, logic puzzles, and navigation. In all domains, the generative models we consider do well on existing diagnostics for assessing world models, but our evaluation metrics reveal their world models to be far less coherent than they appear. Such incoherence creates fragility: using a generative model to solve related but subtly different tasks can lead to failures. Building generative models that meaningfully capture the underlying logic of the domains they model would be immensely valuable; our results suggest new ways to assess how close a given model is to that goal.

Main paper: 
 introduction: 
 Large language models (LLMs) appear to have capacities that far exceed the next-token prediction task they were trained to perform (Kıcıman et al., 2023; Wei et al., 2022a; Suzgun et al., 2022) . Recent work suggests a reason: they are implicitly recovering high-fidelity representations of the underlying domains they are trained on (Abdou et al., 2021; Li et al., 2023) .An algorithm that recovers a "world model" from sequence data would be extremely valuable. As an example, consider how one might build a navigation tool today: meticulously map each street and intersection, and then use a search algorithm to provide directions. The success of language models suggests an alternative approach: collect turn-by-turn sequences from trips in a city (e.g. "East North...") and then train a sequence model on them. If the sequence model successfully recovers the world model, we would obtain a map of the city without ever mapping it and a routing algorithm simply by predicting the next turn. This example is not far-fetched: it is the reason language models are used in scientific domains such as protein generation, genetics and chemistry (Chowdhury et al., 2022; Lin et al., 2023; Benegas et al., 2023; Jablonka et al., 2024; Boiko et al., 2023) .All of this relies on the presumption that the sequence model has recovered the true world model; but how can we test whether it actually has? Answering this question requires first defining what we mean by the true world model. Toshniwal et al. (2022) and Li et al. (2023) proposed a concrete and influential approach: study whether sequence models trained on board game transcripts (e.g. chess and Othello) recover the underlying game rules. Inspired by this approach, we consider the case where the underlying world can be summarized by a finite collection of states and rules governing transitions between the states; this includes many domains such as logic (Li et al., 2021) , location tracking (Patel & Pavlick, 2021; Guan et al., 2023) , games (Toshniwal et al., 2022; Li et al., 2023) , and several of the scientific applications described above. As a result, the "world" in these domains can be modeled as a deterministic finite automaton (DFA).We show the difficulty in evaluating implicit world models. Consider an existing approach: for a given sequence, compare the next tokens outputted by the generative model to the set of valid next tokens for the state implied by that sequence (Toshniwal et al., 2022; Li et al., 2023) . Though intuitive, this approach can fail to diagnose severe problems, and we illustrate this concretely. The classic Myhill-Nerode theorem (Myhill, 1957; Nerode, 1958) provides intuition: every pair of distinct states can be distinguished by some sequence (admitted by one state but not the other). Unless those minimal distinguishing sequences are of length one, looking at the next single token outputted will not reliably assess whether the generative model has an accurate model of the underlying state.The logic of Myhill-Nerode suggests two metrics for measuring whether a generative model effectively captures underlying states and transitions. The first metric summarizes sequence compression: under the DFA, sequences that lead to the same state must have the same continuations; so one can test whether the generative model has similar sequences of outputs when started on these two sequences. The second metric summarizes sequence distinction: under the DFA, two sequences that lead to distinct states should have distinct continuations; so one can test whether the generative model matches these distinct outputs when started at these two sequences. We formally define these metrics and provide model-agnostic procedures for calculating them when given query access to the true DFA.To illustrate these ideas, we first take the stylized mapping example literally. We construct a turn-byturn sequence dataset of taxi rides in New York City. We then assess to what extent transformers successfully recover the true street map of Manhattan. By the usual metrics, the transformers do very well: their predicted next-direction is a valid turn nearly 100% of the time and their state representations even appear to encode the current location of the ride. Our evaluation methods reveal they are very far from recovering the true street map of New York City. As a visualization, we use graph reconstruction techniques to recover each model's implicit street map of New York City. The resulting map bears little resemblance to the actual streets of Manhattan, containing streets with impossible physical orientations and flyovers above other streets (see Figure 3 ). Because these transformers fail to recover the true street map of New York City, they are fragile for downstream tasks. While they sometimes have amazing route planning abilities, their performance breaks down when detours are introduced.These results are not unique to maps and navigation. For both Othello and logic puzzles, we use our evaluation metrics to show language models can perform remarkably well on some tasks despite being far from recovering the true world model. These results demonstrate the importance of using theoretically-grounded evaluation metrics if our goal is to build language models that capture accurate world models of the domains they are trained in. We release our benchmark dataset of taxi rides in New York City along with software implementing our evaluation metrics.1 Related work. Our paper builds on influential work studying whether generative models recover a world model in the context of games. Toshniwal et al. (2022) and Li et al. (2023) pioneered the study of games as a testbed for world model evaluation, studying tests for chess and Othello, respectively, which were further studied by Hazineh et al. (2023) and Kuo et al. (2023) . Our evaluation metrics apply to these games because they are DFAs. A common method for assessing whether a trained model has recovered a world model uses probes that assess whether a neural network's representation can recover some real-world state (Hewitt & Liang, 2019; Li et al., 2021; Abdou et al., 2021; Jin & Rinard, 2023; Li et al., 2023) . By contrast, our evaluation metrics are model-agnostic: they're based only on sequences. While the results from our evaluation metrics sometimes align with those used in existing work, they also reveal incoherence in world models that are not captured by existing diagnostics.We study whether a language model trained on sequences of directions recovers the true underlying map. This question relates to other state tracking and navigation problems studied in the language modeling literature (Schumann & Riezler, 2022; Schumann et al., 2024) . For example, Patel & Pavlick (2021) show that larger LLMs ground spatial concepts like cardinal directions to locations in a grid world and generalize to various grid layouts. Relatedly, Schumann & Riezler (2021) demonstrate that transformer-based models can generate navigation instructions in language from underlying graphs. Additionally, Guan et al. (2023) use LLMs to perform planning tasks from natural language descriptions. Our results suggest that LLMs can perform some of these tasks well (such as finding shortest paths between two points on a map) without having a coherent world model. Additionally, our evaluation metrics compare the language accepted by a sequence model to that of an underlying DFA. Existing work studies whether transformers and other sequence models are theoretically capable of recognizing languages in different complexity classes (Suzgun et al., 2018; Bhattamishra et al., 2020; Liu et al., 2022; Merrill & Sabharwal, 2023; Merrill et al., 2024) . Most relevant to our work, Liu et al. (2022) show that low-depth transformers can theoretically represent any finite state automata, and show that transformers trained explicitly to predict their labeled states are capable of doing so. In contrast, our paper doesn't aim to study whether models are theoretically capable of recovering underlying automata or whether they can do so when given state labels. Instead, we provide metrics for assessing how closely a given model recovers the underlying DFA. 
framework: 
 In this section, we lay out a framework to interface between generative sequence models and world models represented by deterministic finite automata. Both of these are built on the shared scaffolding of tokens, sequences (a.k.a. strings), and languages.Tokens and sequences. We consider a finite alphabet Σ with tokens 𝑎 ∈ Σ, and sequences 𝑠 = (𝑎 1 , 𝑎 2 , . . .). Let Σ * denote the collection of sequences on the alphabet. Generative models. A generative model 𝑚(•) : Σ * → Δ(Σ) is a probability distribution over next-tokens given an input sequence. That is, 𝑚(𝑠) ∈ Δ(Σ), and 𝑚(𝑎 | 𝑠) is the probability assigned to token 𝑎 ∈ Σ given an input sequence 𝑠. Starting at a sequence 𝑠, the set of non-empty sequences the model can generate with positive probability is:𝐿 𝑚 (𝑠) = {𝑎 1 𝑎 2 ...𝑎 𝑘 : ∀ 𝑗 < 𝑘, 𝑚(𝑎 𝑗+1 | 𝑠𝑎 1 ...𝑎 𝑗 ) > 0}.For simplicity, we write the equation above for next-tokens with nonzero probability, but in practice we set a minimum probability 𝜖 > 0 corresponding to next-tokens with non-negligible probability.We use standard notation for a deterministic finite state automaton 𝑊 = (𝑄, Σ, 𝛿, 𝑞 0 , 𝐹) (see Appendix C for a complete definition). As a simplifying assumption, we consider the case where there is a special state 𝑞 reject with no outgoing transitions and 𝐹 = 𝑄 \ {𝑞 reject } (i.e., the DFA accepts all valid states). An extended transition function δ takes a state and a sequence, and it inductively applies 𝛿 to each token of the sequence. A token or a sequence is valid if and only if the output of 𝛿 or δ respectively starting from 𝑞 0 is not 𝑞 reject .We define 𝐿 𝑊 (𝑞) to be the set of valid, non-empty sequences that are accepted by the DFA starting at state 𝑞. We also define 𝑞(𝑠) ∈ 𝐹 to be the state that sequence 𝑠 leads to in the DFA starting from 𝑞 0 and 𝑆(𝑞) ⊆ Σ * to be the collection of all sequences that lead from state 𝑞 0 to state 𝑞 in the DFA.Throughout this paper we assume that the ground-truth sequences used to train and test a generative model belong to the language of a deterministic finite state automaton 𝑊. This generalizes past work (e.g., on assuming sequences come from legal moves in a game (Toshniwal et al., 2022; Li et al., 2023) ) and allows us to formally define world recovery.Definition 2.1. A generative model 𝑚(•) recovers the DFA 𝑊 if ∀𝑞 ∈ 𝐹, ∀𝑠 ∈ 𝑆(𝑞) : 𝐿 𝑊 (𝑞) = 𝐿 𝑚 (𝑠).That is, recovery requires that a sequence can be generated with positive probability by the model 𝑚(•) if and only if the sequence is valid in the DFA 𝑊.Recovery is defined at the language level. However, generative models are often built and evaluated token-by-token. It turns out that exact next-token prediction is enough for recovery of the language of the world model. Proposition 2.3 (proof given in Appendix A) suggests a way to evaluate whether a generative model recovers the true DFA: assess the validity of next-token predictions. Existing world model diagnostics are motivated by this intuition; for example, one way that Toshniwal et al. (2022) and Li et al. (2023) assess world model recovery is by measuring the percent of top next-token predictions that are valid.Next-token prediction, however, is a limited evaluation metric. While exact next-token prediction implies perfect world model recovery, being very nearly correct on next-token prediction does not mean having very nearly recovered the world model. This can be illustrated by a simple example.Example: Cumulative Connect-4. Consider a vertical grid with 𝑛 rows and 7 columns. Two players take turns dropping a disk in a column, and they can choose any column that contains less than 𝑛 disks. When a disk is dropped in a column, it occupies the bottom-most position that isn't occupied by another disk, and it remains in that position for the full game. The game continues until the entire board is filled, for 7𝑛 moves, regardless of whether a player has achieved four in a row. Games are represented as sequences of moves, where each sequence has 7𝑛 tokens and each token is an integer between 1 and 7 indicating the column the disk is placed in. Here, Σ = {1, . . . , 7} denotes the columns and the state corresponds to the count in each column. A column is a valid move if that column is not already filled.Consider a generative model that outputs {1, . . . , 7} with uniform probability given any sequence, i.e. 𝑚(𝑎 | 𝑠) = 𝑚(𝑎 ′ | 𝑠 ′ ) = 1/7 for all 𝑎, 𝑎 ′ ∈ Σ and 𝑠, 𝑠 ′ ∈ Σ * . This model clearly encodes no information about the board. However, for any board where there are no columns filled, this model provides a valid next move (e.g., the right panel of Figure 1 ), and so it will be a near-perfect next-token predictor when 𝑛 is large. For example, when 𝑛 = 1000, it predicts a valid next move for more than 99% of all states. Metrics based on next-token prediction will imply this algorithm is close to recovering a world model.Cumulative Connect-4 points to a general fragility in next-token prediction as an evaluation metric that can be understood in the context of the Myhill-Nerode theorem (Myhill, 1957; Nerode, 1958) , a classic result from language theory. The Myhill-Nerode theorem states that the sets of sequences accepted by a minimal DFA starting at two distinct states are distinct (see Appendix C for a full statement). More formally, for states 𝑞 1 ≠ 𝑞 2 , we have 𝐿 𝑊 (𝑞 1 ) ≠ 𝐿 𝑊 (𝑞 2 ). However, while distinct, the two sets may exhibit a great deal of overlap. Cumulative Connect-4 exhibits this behavior; any board for which there are less than 𝑘 disks in each column will have the same set of valid moves for the next 𝑛 -𝑘 moves. This intuition motivates a pair of definitions: Definition 2.4. Given a DFA 𝑊, the Myhill-Nerode interior for the pair 𝑞 1 , 𝑞 2 ∈ 𝐹 is the set of sequences accepted when starting at both states:MNI 𝑊 (𝑞 1 , 𝑞 2 ) = {𝑠 ∈ Σ * | 𝑠 ∈ 𝐿 𝑊 (𝑞 1 ) ∩ 𝐿 𝑊 (𝑞 2 )}.The Myhill-Nerode boundary is the set of minimal suffixes accepted by a DFA at 𝑞 1 but not 𝑞 2 : Sequences on the interior are accepted by both states; it is only when we reach the boundary that these states will be distinguishable. Thus, models that pool together states with large interiors will perform well on next-token prediction tests; this is why the simple generative model succeeds in the cumulative Connect-4 example. To properly differentiate states, we must consider sequences that are long enough to be differentiated. In the remainder of the paper, we (i) use the Myhill-Nerode logic to develop new evaluation metrics and (ii) apply these to several applications.MNB 𝑊 (𝑞 1 , 𝑞 2 ) = {𝑠 = 𝑎 1 𝑎 2 ...𝑎 𝑘 | 𝑠 ∈ 𝐿 𝑊 (𝑞 1 ) \ 𝐿 𝑊 (𝑞 2 ) and ∀ 𝑗 < 𝑘 : 𝑎 1 ...𝑎 𝑗 ∈ MNI 𝑊 (𝑞 1 , 𝑞 2 )}.We propose metrics to evaluate a model's implicit world model by comparing the true Myhill-Nerode boundary to the one implied by the model. This is the set of minimal suffixes that are accepted by the model conditioned on 𝑠 1 but not 𝑠 2 . Since we now focus on the generative model rather than the DFA, the definition refers to pairs of sequences rather than to pairs of states.Our evaluation metrics summarize how well a generative model identifies sequences that distinguish a given pair of states. Given a pair of states 𝑞 1 and 𝑞 2 , the metric is formed by first sampling sequences that lead to each state, 𝑠 1 ∈ 𝑆(𝑞 1 ) and 𝑠 2 ∈ 𝑆(𝑞 2 ). We then calculate the true Myhill-Nerode boundary between the states and the model's boundary between the sequences. Our metrics then compare the resulting boundaries using two statistics as building blocks: Definition 2.6. The boundary recall of generative model 𝑚(•) with respect to a DFA 𝑊 is defined asEQUATIONand the boundary precision is defined asEQUATION)Notice that boundary recall and boundary precision are not affected by whether the Myhill-Nerode interior is large between the two states. Returning to cumulative Connect-4, the simple generative model that outputs {1, . . . , 7} with equal probability will perform poorly on these metrics; its recall will be 0 for all pairs of distinct states.Based on the building blocks of recall and precision, we construct evaluation metrics to summarize whether the generative model correctly compresses sequences that arrive at the same state under the DFA and correctly distinguishes sequences that arrive at different states under the DFA. These two metrics correspond to different methods of sampling state pairs.Sequence compression metric. To evaluate sequence compression, we sample equal state pairs 𝑞 1 = 𝑞 2 . Since a DFA provides multiple ways to arrive at the same state, this test assesses whether a generative model recognizes that two sequences correspond to the same state. For example, in cumulative Connect-4, there may be multiple sequences that arrive at the same board position. Recall is undefined for equal states because there is no true boundary, so our compression metric only reports precision, averaged over states sampled uniformly at random (we say a generative model's precision is 1 if its boundary is correctly empty).Sequence distinction metric. To evaluate sequence distinction, we sample distinct state pairs, i.e. 𝑞 1 ≠ 𝑞 2 . Here, there must be a true boundary, so we test how well a generative model recovers it. We report both precision and recall averaged over state pairs sampled uniformly at random.Both metrics are depicted in Figure 2 . Although we have defined a generative model as accepting all sequences it assigns positive probability to, in practice sequence models are regularized to assign all sequences nonzero probability. Our evaluation metrics therefore depend on an acceptance threshold parameter 𝜖 > 0. In practice, we explore sensitivity to different values of 𝜖 and other acceptance mechanisms. We present ablations and other details in more depth in Section 3 and Appendix E. 
illustration: do transformers recover the street map of new york city?: 
 To illustrate these metrics, we create a dataset consisting of taxi rides in New York City. We process each ride into sequences of turn-by-turn directions and train transformers to predict the next direction.We show that transformers trained on these sequences have surprising route planning abilities: they not only find valid routes between two intersections but usually find the shortest path.We then examine the underlying world model of the trained models. Despite the route planning capabilities of these models, our metrics reveal that their underlying world models are incoherent. Using a graph reconstruction technique, we show that each model's implicit street map of New York City bears little resemblance to the actual map. Finally, we demonstrate that the route planning capabilities of these models break down when detours are introduced, a consequence of their incoherent world models.We base our analysis on a dataset of taxi rides released by the NYC Taxi & Limousine Commission, containing the latitude and longitude of each ride's pickup and dropoff location in Manhattan. Each taxi ride obeys a true world model: the weighted graph corresponding to the system of intersections and streets in New York City. The graph is defined as 𝐺 = (𝑉, 𝐸, 𝑊), where 𝑉 is the set of intersections, 𝐸 the set of streets, and 𝑊 : 𝐸 → R + a weighting function containing the distance of each street.2 Each edge is labeled corresponding to its cardinal direction, represented as a function 𝐷 : 𝑉 × 𝑉 → {□, N, S, E, W, NE, NW, SE, SW} with □ indicating that the edge does not exist. Each intersection has at most one edge in each direction. The graph has 4580 nodes (i.e. intersections) and 9846 edges (i.e. streets).A traversal is a sequence of nodes where an edge exists between each consecutive node in the sequence. To study how the construction of traversals affects the resulting generative model, we consider three different approaches. Shortest paths constructs traversals by finding the shortest path between two nodes. Since these may not be reflective of real-world traversals due to traffic conditions, noisy shortest paths constructs multiple shortest paths by perturbing the magnitude of each edge weight in the underlying graph. Finally, random walks samples random traversals instead of approximating shortest paths. See Appendix F for details.We convert each traversal into a sequence of directions. Each sequence begins with the origin and destination, followed by the cardinal directions in the traversal, and concludes with a special end-of-sequence token. Figure 5 gives an example of a set directions and the corresponding path. Since this language corresponds to a DFA 𝑊 with |𝑉 | 2 + 1 accept states, corresponding to all combinations of current intersection/destination intersection pairs and an additional end state, we can apply the evaluation metrics in Section 2.4.We randomly split data into train and test splits, ensuring no origin-destination pair is in both train and test sets. We include all sequences containing less than 100 directions. Our training sets consistUntrained transformer 0.03 (0.00) 0.10 (0.00) 0.00 (0.00) 0.00 (0.00) 0.00 (0.00) Shortest paths 1.00 (0.00) 0.91 (0.00) 0.10 (0.01) 0.35 (0.02) 0.20 (0.01) Noisy shortest paths 1.00 (0.00) 0.92 (0.00) 0.05 (0.01) 0.37 (0.02) 0.24 (0.01) Random walks 1.00 (0.00) 0.99 (0.00) 0.50 (0.02) 0.99 (0.00) 1.00 (0.00) True world model 1.00 -1.00 1.00 1.00 Table 1 : Sequence compression and distinction metrics for world models compared to existing metrics (standard errors in parentheses). Models that do well on existing metrics can perform poorly on ours. of 2.9M sequences (120M tokens) for shortest paths; 31M sequences (1.7B tokens) for noisy shortest paths; and 91M sequences (4.7B tokens) for random walks. We train two types of transformers (Vaswani et al., 2017) from scratch using next-token prediction for each dataset: a 117M parameter model consisting of 12 layers, 768 hidden dimensions, and 12 heads; and a 1.6B parameter model consisting of 48 layers, 1600 hidden dimensions, and 25 heads. We follow the architecture of GPT-2 for each model (Radford et al., 2019) . We train models on 8 A100 GPUs. For each dataset, we analyze the model with the best held-out performance: the 117M parameter model for shortest paths, and the 1.6B parameter for noisy shortest paths and random walks.To assess their capabilities, we first assess whether the trained models can recover the shortest paths between unseen (origin, destination) pairs. We prompt each model with (origin, destination) pairs from the test set and use greedy decoding to generate a set of directions. All models consistently generate valid traversals -between 96% and 99%. Impressively, 97% of the sequences generated by the shortest paths model are the true shortest path, and 94% of the sequences generated by the model trained on noisy shortest paths find a shortest path for one of the noisy graphs used to generate data. Figure 5 provides an example of a shortest path traversal.To assess whether these capabilities correspond to coherent implicit world models, we first consider two existing diagnostics (Toshniwal et al., 2022; Li et al., 2023) . The next-token test assesses whether a model, when conditioned on each subsequence in the test set, predicts a legal turn for its top-1 predicted next-token. In our example, a directional move is legal if a street in the direction exists at the current intersection. Predicting the end token is only legal if the traversal implied by the sequence is at the listed destination. Meanwhile, the current-state probe trains a probe (Hewitt & Liang, 2019) from a transformer's representation to predict the current intersection implied by the directions so far. We train a linear probe on a transformer's last layer representation.To implement the sequence compression metric, we randomly sample states (i.e., [intersection, destination] pairs) and two distinct traversals (i.e. prefixes) that arrive at each state. We then assess whether a model correctly admits the same suffixes for each prefix. We average over pairs of prefixes to report a score for each state and average over states to report a final score. To implement the sequence distinction metrics, we sample pairs of distinct states and traversals (i.e. prefixes) that arrive at each state, comparing the model's approximate Myhill-Nerode boundary to the true one. We average over pairs of prefixes to report a score for each pair of states, and average over 1000 randomly sampled state pairs to report a final scores. Both metrics depend on a threshold parameter 𝜖: a prefix is only sampled or accepted if the model's assigned probability for each token is above 𝜖.Here, we consider 𝜖 = 0.01 for all models and metrics. We describe implementation details, provide parameter ablations, and consider other acceptance rules (e.g. top-p and top-k) in Appendix E.Table 1 summarizes our results. As references, we compare each trained transformer to a randomly initialized transformer baseline following Li et al. (2023) as well as to the true world model. The three trained transformers perform exceptionally well on existing diagnostics; nearly 100% of next-token predictions are valid and the probe recovers the true intersection for more than 90% of examples. 3Our evaluation metrics, however, reveal that these existing diagnostics are incomplete. All trained transformers perform poorly on sequence compression, frequently failing to recognize that two Edges exit nodes in their specified cardinal direction. In the zoomed-in images, edges belonging to the true graph are black and false edges added by the reconstruction algorithm are red. We host interactive reconstructed maps from transformers at the following links: shortest paths, noisy shortest paths, and random walks.prefixes leading to the same state should admit the same continuations. Even the transformer trained on random walks, which sees many distinct types of traversals during training, fails to compress prefixes for half the states. For the sequence distinction metrics, the transformers trained on shortest paths or noisy shortest paths perform poorly. In contrast, the transformer trained on random walks performs well on the sequence distinction metric. Both metrics are therefore valuable for evaluating world models; a model can perform well on one metric and poorly on the other. Here, a model that distinguishes separate states at a high rate fails to recognize that two prefixes that lead to the same state should have the same valid continuations.Our evaluation metrics point to deficiencies in recovering world models. We now show that these metrics reveal underlying incoherence. In the maps setting, the state structure of the true world model is easy to interpret and visualize: it is defined by the map itself. We attempt to "reconstruct" the map implied by sequences sampled from each generative model.Reconstruction is an open-ended problem: the generative model produces directions between an origin and destination that do not necessarily correspond to a fixed graph over the intersections in Manhattan.To narrow the scope, our goal is to produce a visually interpretable reconstructed map. To that end, we fix the reconstructed graph to have the same set of vertices as the true world model, corresponding to intersections in Manhattan, and ensure that the reconstruction algorithm returns a map consistent with the true model whenever it is run on valid sequences. Further, (a) we enforce each node has at most one outgoing edge of any direction, (b) we limit the maximum degree of each node, and (c) we limit the Euclidean distance spanned by any edge. Altogether, our reconstruction algorithm gives the generative model the benefit of the doubt, attempting to reconstruct edges belonging to the true map until forced to do otherwise in order to map a generated sequence. The algorithm is detailed in Appendix B.Figure 3 shows three reconstructed maps using sequences generated by the transformer trained on random walks. The sequences underlying each map are generated by randomly sampling 6400 (origin, destination) pairs and then sampling the model's traversal for each pair (Appendix G shows similar results for when the distribution of origin/destination pairs follows the sampling distribution used to train each model). On the left is the reconstructed map on only sequences which are valid under the true world model. On the right is the reconstructed map using the transformer's sequences. The transformer's underlying world model is incoherent; it recovers streets whose orientations are physically impossible (e.g. labeled NW but facing east) and require flyovers above other streets.To show that this map is not the product of a model that has the right world model but makes a few transcription errors, we artificially corrupt sequences drawn from the true model. With probability equal to the probability of an error for the random walks transformer, we randomly re-label an edge in a sequence consistent with the world model. The middle panel of Figure 3 shows the reconstructed graph. It is much closer to the true world model than the transformer (which makes errors at the same rate). While these results are for random walks and one setting of graph reconstruction, Appendix G shows maps for the other models and different reconstruction settings. All settings recover incoherent underlying maps.Does it matter that the transformer has an incoherent world model? After all, it does very well at the practical task of finding shortest paths. Here we look at a slightly adjacent task and consider a driver facing detours while driving; how well does the model re-route?Concretely, we feed each transformer an (origin, destination) pair from the test set and greedily decode a traversal. But with probability 𝑝 for each token, we add one of two kinds of detours: for "random detours", the model's proposed token is replaced with a randomly chosen (true) valid token; for "adversarial detours", it is replaced with the model's lowest ranked valid token. We always ensure a valid path to the destination exists (shorter than length 100) after each detour. Table 2 shows the fraction of valid traversals produced. While all models perform well initially, detours erode performance, illustrating how faulty world models can prove problematic. Notably, the transformer trained on random walks is more robust to detours than models trained on (noisy) shortest paths, mirroring its advantage on our proposed evaluation metrics. The similarity between model performance on these evaluation metrics and detour robustness illustrates the effectiveness of our proposed metrics for assessing world model recovery. 
other applications: othello and logic puzzles: 
 We apply our evaluation metrics to two other settings: sequence models trained on games of Othello and large language models prompted to solve logic puzzles. In both cases, our framework finds the same type of incoherence that we found in the previous section for maps.Othello. Li et al. (2023) study the question of evaluating world models in the context of Othello, a board game that consists of players placing tokens on an 8x8 board. They train transformers on game transcripts to predict the next move of each game. They show these models perform well on both the next-token test and current-state probe considered in Section 2.4. Since the true Othello game can be represented as a DFA, we can apply our world model evaluation metrics. The sequence compression metric assesses whether openings that lead to the same board position have the same predicted next moves, while the sequence distinction metrics assess whether the model can differentiate two distinct boards.We apply our metrics to the two Othello sequence models considered by Li et al. (2023) : one trained on real games from Othello championship tournaments and another trained on synthetic games. Table 3 in Appendix D reports the metrics in both settings. The model trained on real games performs poorly on both compression and distinction metrics, failing to group together most pairs of game openings that lead to the same board. In contrast, the model trained on synthetic games performs well on both metrics. This discernment is not captured by the existing metrics, which show both models performing similarly. We validate this discernment by performing a "detours" exercise for Othello in Table 4 in Appendix D; while the model trained on synthetic data produces near-perfect games regardless of detours, the model There are 3 individuals named A, B, and C, and there are 3 seats, positioned 1-3. We have the following statements:1. B is in seat 3 2. B is 1 seat away from A Based on this information, where is C seated? You can use chain-of-thought reasoning. Figure 4 : On the left, an example given to large language models to assess task capabilities. On the right, each model's average task performance along with their results on our proposed metrics. Models are very capable of solving logic puzzles despite not having a coherent world model.trained on championship data fails immediately. Similar to the navigation setting, we again find that models trained on random/synthetic data recover more structure than those trained on real-world data.Logic puzzles. We consider an additional application involving LLMs. Our metrics require that the ground truth language can be expressed as a DFA, so we consider a "seating arrangement" logic puzzle similar to those in Suzgun et al. (2022) . There are 𝑛 seats and 𝑛 individuals. The vocabulary consists of statements like "Person 'A' is sitting in seat 1" and "Person 'B' is two seats away from Person 'C". A state is the set of seating arrangements that are consistent with all of the statements so far, and a statement is valid if it doesn't contradict all arrangements in the given state.We analyze Llama 2 (70B) (Touvron et al., 2023) , Llama-3 (8B and 70B), Mixtral (8x22B Instruct) (Jiang et al., 2023) , Qwen 1.5 Chat (72B and 110B) (Bai et al., 2023) , GPT-3.5 turbo, and GPT-4. We consider 𝑛=3 individuals. We first assess whether the LLMs solve the logic puzzle task when the seating arrangement is fully specified by the statements. Figure 4 shows that most LLMs perform well at this task; GPT-4 is accurate on all examples. We then apply our metrics, assessing if each LLM compresses correctly (whether two sets of statements that lead to the same state lead to the same assessments) and has high recall for distinction (we do not compute precision for distinction because it is too expensive to approximate each LLM's Myhill-Nerode boundary). See Appendix E for further discussion.Figure 4 shows the results averaged over 100 samples. While most LLMs can solve the logic puzzle when it's fully specified, they perform poorly on the compression and distinction metrics: no model has a compression precision higher than 40%. More than half the time a model is conditioned on two sequences with the same set of viable states, it asserts that different continuations are allowed for each sequence; see Figure 8 for an example. No model has distinction recall higher than 0.60. These results bring up an interesting point: LLMs can perform well at some logic tasks (such as when the seating arrangement is fully specified) without having a coherent world model.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We describe implementation details and dataset construction details in depth to enable reproducibility. We also release code. 
conclusion: 
 In order to build high-fidelity algorithms that meaningfully capture the logic of the problems they model, we need ways to measure how close we are to that goal. This paper suggests theoretically grounded metrics for assessing the world models implicit inside generative models. Applications to maps, games, and logic puzzles suggest these metrics are both feasible to implement and insightful.Our results show that generative models can perform impressive tasks with incoherent world models (e.g. provide directions for taxi rides). But this incoherence makes them fragile for other tasks (e.g. providing directions when there are detours). This incoherence is also problematic when we hope to use a generative model to learn something latent about the world in scientific domains.Our primary limitation is the focus on DFAs. While it is suitable for many applications like games, logic, and state tracking, extending it would be quite valuable, e.g. to situations where the underlying world model is more complicated than a DFA or is unknown. We suspect that the core ideas related to sequence compression and sequence distinction generalize to these richer settings, but leave that to future work. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We release all code and our processed dataset of taxi rides. Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: We discuss the datasets, models, hyperparameters, and other experimental settings, at a high-level in the main text and in detail in the appendix. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: The paper reports standard errors for experimental results. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper does not release any data or models that pose a high risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We credit the original creators of baseline models we use and datasets we train on.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Proof of Proposition 2.3. We will first prove the forward direction that if a generative model 𝑚( In this section, we give more details on our reconstruction algorithm and display maps for sequences generated from models trained on shortest paths, noisy shortest paths, and random walks each for several parameter settings.Our reconstruction algorithm in Algorithm 1 takes a set of sequences from a generative model and attempts to reconstruct the underlying map implied by the sequences. The reconstructed map has the same set of vertices as the true world model (i.e. the intersections of Manhattan), and we visualize each intersection by placing them at their real-world latitude/longitude. The reconstruction algorithm thus attempts to recover the edges and edge directions implied by each set of sequences.For each sequence that is valid under the true map, the algorithm adds the true edges and edge directions implied by the sequence. In a sense, this algorithm gives the generative model the benefit of the doubt. However, sometimes the model errs, i.e. it produces a sequence which is only valid by adding an additional edge to the true map. In this case, our reconstruction algorithm adds a new edge at the first invalid step of the traversal. There are usually multiple possible edges to add that would make the traversal valid; the algorithm adds the edge that maximizes the number of subsequent steps that would be valid. In other words, the algorithm adds new edges only when there is a discrepancy between the transformer and the world model, choosing the edge which greedily maximizes the number of subsequent steps that accord with the true world model. The direction label for each added edge is thus the token at the corresponding invalid step of the traversal.Our algorithm may fail to reconstruct some of the input sequences as they cannot be made consistent with the partial graph we have reconstructed so far. Note that any reconstruction algorithm that satisfies the constraints in the main text of having a single edge with a given direction coming out of any intersection, a maximum degree, and a maximum edge distance will not be able to reconstruct every set of sequences. For example, two sequences [𝑣 1 , 𝑣 2 , E, end] and [𝑣 1 , 𝑣 3 , E, end] cannot be reconstructed without violating the first constraint.We include reconstructed maps built from 6400 transformer-generated sequences for transformers trained on shortest paths, noisy shortest paths (modeling traffic), and random walks in Manhattan. Each sequence is generated by randomly sampling an (origin, destination) pair and then sampling the model's traversal for each pair. Because the transformer never sees sequences of length more than 100 during training, we only sample pairs for which there exists a valid traversal in less than 100 moves. We note that this distribution of (origin, destination) pairs varies from the distributions used to train and evaluate each model, and the percent of traversals that are valid falls from >95% to 65-80%; however, Figure 12 shows similar maps when each map is constructed by sampling (origin, destination) pairs from the training/evaluation distributions. We vary the constrained maximum degree between 4 and 8 (the true map has maximum degree 4 and there are 8 possible cardinal directions), and the maximum edge distance between 1 /2 and 1 mile.Each map depicts the map of Manhattan implied by the graph reconstruction algorithm. Reconstructing maps involves adding edges between two intersections. We make sure the edges visually accord with the labels reconstructed by the algorithm. For example, if intersection 𝑣 1 is north of intersection 𝑣 2 in FAIL to construct sequence 18: return D the true map but the reconstruction algorithm recovers an edge from 𝑣 2 to 𝑣 1 labeled "South", we draw an edge that leaves 𝑣 2 facing south and loops back to 𝑣 1 . In the zoomed-in images, edges belonging to the true map are in black and false edges added by the reconstruction algorithm are in red.In each caption, we list the number of sequences the algorithm failed to reconstruct. In addition to the reconstructed map from all of the transformer's sequences, we plot the reconstructed map built only on sequences which are valid under the true world model as well as a reconstruction of those valid sequences with some artificial corruptions. For the artificial corruptions, each sequence is chosen to be corrupted with a fixed probability of 25% for shortest paths, 35% for noisy shortest paths, and 20% for random walks. These percentages correspond to the fraction of the transformer's sequences that are invalid, so the (b) and (c) subfigures of each plot have the same proportion of valid and invalid sequences.We note that the maps corresponding to the random walk model visually have more edges than, for instance, the maps built from shortest paths data. This is due to the fact that while the inputs to the reconstruction algorithm have the same number of sequences, the length of the sequences differ between the different generative models. The total number of directions contained in the shortest path sequences is 983,182, for noisy shortest paths is 1,140,487, and for random walks is 1,584,549.Recall that we use a standard parameterization of a DFA as 𝑊 = (𝑄, Σ, 𝛿, 𝑞 0 , 𝐹) (see Sipser ( 2013)) with 1. 𝑄 is a finite set of states, 2. Σ is a finite set of characters, 3. 𝛿 : 𝑄 × Σ → 𝑄 is the transition function mapping a state and character to the next state, 4. 𝑞 0 ∈ 𝑄 is the start state, 5. 𝐹 ⊆ 𝑄 is the set of accepting states.In the rest of this section, we state the Myhill-Nerode theorem, which is the conceptual basis for our world-model test.Untrained transformer 0.00 (0.00) 0.02 (0.00) 0.14 (0.01) Championship Othello 0.00 (0.00) 0.65 (0.01) 0.27 (0.01) Synthetic Othello 0.98 (0.00) 0.99 (0.00) 1.00 (0.00) True world model 1.00 1.00 1.00 Table 3 : The metrics from Section 2.4 applied to Othello sequence models. The championship and synthetic models refer to models trained on real-world tournament games and synthetic games, respectively.Definition C.1 (Equivalent sequences). Two sequences 𝑠 1 , 𝑠 2 ∈ Σ * are called equivalent under a language 𝐿 if for all suffixes 𝑥 ∈ Σ * , 𝑠 1 𝑥 ∈ 𝐿 ⇐⇒ 𝑠 2 𝑥 ∈ 𝐿. This equivalence relation can be used to partition all strings into equivalence classes.Theorem C.2 (Myhill (1957) ; Nerode (1958) ). A language 𝐿 is regular if and only if it has a finite number of equivalence classes. Then, the minimal DFA accepting 𝐿 has a number of states equal to the number of classes. In the minimal DFA, for every pair of distinct states 𝑞 1 ≠ 𝑞 2 , there exists a suffix 𝑥 such that exactly one of δ(𝑞 1 , 𝑥) or δ(𝑞 2 , 𝑥) is in the set of accepting states 𝐹.Figure 5 shows an example of sequences and traversals in our dataset. Each training sequences consists of an origin node, a destination node, and a set of directions followed by an end node. To evaluate, we condition on (origin, destination) pairs that are unseen during training and generate a traversal from the model.Figure 6 shows how our performance metrics vary as we consider different suffix lengths for approximating the Myhill-Nerode boundary. For compression precision, considering a boundary of size 𝑘 corresponds to sampling suffixes of length-𝑘 for each suffix and measuring whether prefixes with the same state have the same length-𝑘 suffixes. For distinction precision, we consider a boundary of size 𝑘 by only sampling 𝑘-length suffixes to approximate a model's Myhill-Nerode boundary. For distinction recall, we consider a boundary of size 𝑘 by only constructing the true Myhill-Nerode boundary based on 𝑘-length suffixes. The results in Figure 6 show the importance of considering larger boundaries as opposed to smaller ones (e.g. single next-tokens); for example, while the model trained on random walks scores 100% on compression precision when boundaries of length-1 are considered, its performance is 50% when the full Myhill-Nerode boundary is considered.We also performed some analysis to explore why the models uniformly performed badly on compression tests in the maps setting. We found a negative correlation between the number of two-way streets at an intersection and the compression precision; as the number of two-way streets at an intersection increases, the model's ability to recognize that two sequences that lead to the same intersection are indeed in the same state worsens. Figure 7 plots this relationship for the shortest paths model.Table 3 reports our metrics on models trained to play Othello. We use the transformer model checkpoints provided by Li et al. (2023) . We perform 1000 samples of each test. Our metrics find that while the model trained on synthetic data recovers the true world model, the model trained on championship data does not. In Table 4 , we perform a detour exercise analogous to the one performed for taxi rides in Section 3, where here a model's predicted move is replaced with another legal one. The detour results support the discernment between models found by our metrics; while the model trained on synthetic data produces near-perfect games regardless of detours, the model trained on championship data fails immediately.Here we provide implementation details and ablations for the test described in Section 2.4 and implemented in Section 3. We discuss how it's implemented in each of the three settings -maps, Othello, and logic puzzles -and then show ablations with different settings. 4 : The fraction of traversals that are valid when detours are introduced in Othello. For "random detours", a model's proposed token is replaced with a randomly chosen (true) valid token; for "adversarial detours", it is replaced with the model's lowest ranked valid token.Maps. For the compression test, we sample a state at random from all possible states, where each state is a (current intersection, destination intersection) tuple. We then sample two distinct sequences that lead to the same state. Because models are only trained on sequences of length 100 or less, we only sample sequences that are short enough to be possible to arrive at the destination in less than 100 moves. Among all possible sequences, we first sample a length 𝑙 uniformly at random, and then perform two random walks for 𝑙 steps in the reversed graph. This provides two distinct length-𝑙 prefixes that lead to the same state, 𝑠 1 and 𝑠 2 .Because the true world's Myhill-Nerode boundary is empty for the compression test, we only need to compute the model's boundary. However, computing the model's boundary is intractable; it involves evaluating a transformer on exponentially many outputs. However, we don't actually need to compute the full boundary; the precision is 0 any time there's one sequence accepted by one prefix and not the other. So we approximate precision by Monte-Carlo sampling. We sample 𝑀 complete sequences from the model conditioned 𝑠 1 , insuring that each token has higher than 𝜖 probability. We then check if each token in the sequence has higher than 𝜖 probability when the model is conditioned on 𝑠 2 . If there exists a single violating sample, it means that the model has failed to compress the two prefixes. Therefore, sampling results in an upper-bound on performance. In practice, we use 𝑀 = 30 samples. Below, we show that results are not very sensitive to the number of samples.For the distinction test, we sample two distinct states, 𝑞 1 and 𝑞 2 , uniformly at random, and sample sequences that lead to each state, 𝑠 1 and 𝑠 2 , as before. As before, computing full Myhill-Nerode boundaries is intractable, so we approximate them. To approximate the true world model's Myhill-Nerode boundary, we consider all continuations of length 𝑘, and find the set of minimal suffixes that are accepted after 𝑞 1 but not 𝑞 2 . To see which elements in the true boundary are distinguished by the model, we evaluate the model on each element in conditioned on 𝑠 1 vs 𝑠 2 . We use 𝑘 = 5, and find that results are robust across different 𝑘 ≥ 5. We again approximate the transformer's Myhill-Nerode boundary by taking 𝑀 = 30 Monte-Carlo samples. For each sequence that's accepted after 𝑠 1 but not 𝑠 2 , we find the minimal distinguishing suffix and include it in the boundary set. We then assess precision by calculating which elements in the model's boundary are acceptable after 𝑞 1 but not 𝑞 2 .For both tests, we get state-level scores by averaging the results over prefixes that lead to each state, and we report overall scores by averaging all sampled states.Othello. The compression test for Othello involves sampling a board and then two sequences that lead to the board. We approximate this sampling by simulating 1000 random games and sampling a board at random from the set of unique boards that are visited by at least two unique games. This sampling provides us with two different sequences, 𝑠 1 and 𝑠 2 , that lead to the same board, 𝑞. Like the above, we don't need to compute the model's full Myhill-Nerode boundary since the precision is 0 any time one sequence is accepted by 𝑠 1 and not 𝑠 2 . Therefore, we again approximate precision with 𝑀 = 30 Monte-Carlo samples, following the same method as performed for maps. For the distinction test, we sample two distinct states 𝑞 1 and 𝑞 2 from the set of sampled games with the same length. We sample prefixes 𝑠 1 and 𝑠 2 from the empirical distribution of observed games. We approximate the transformer's Myhill-Nerode boundary in the same way as we did for maps, by taking 𝑀 Monte-Carlo samples of complete game trajectories. We perform the analogous sampling There are 3 individuals named A, B, and C, and there are 3 seats, positioned 1-3. We have the following statements:1. B is 1 away from C 2. A is 1 away from BThere are 3 individuals named A, B, and C, and there are 3 seats, positioned 1-3. We have the following statements:1. C is 2 away from A Context 2Is the following statement possible in this scenario? "C is 1 away from B" technique for the true world model, sampling 𝑀 complete gameplay trajectories at random over the set of valid continuations. We use 𝑀 = 30 for both sampling procedures and a threshold of 𝜖 = 0.01.Performing our test on large language models presents a challenge that we do not have token-level probability access. Moreover, because we allow large language models to perform chain-of-thought reasoning, it's computationally intractable to sample long continuations by marginalizing over the possible chain-of-thoughts.Our test design is therefore based on prompting. See Figure 8 for an example. For the compression metric, we sample up to 2 statements uniformly at random from the set of possible statements to arrive at a state 𝑞. We then sample two prefixes 𝑠 1 and 𝑠 2 that lead to 𝑞 by repeatedly sampling the set of statements consistent with 𝑞 that don't narrow down the state space until the state implied by the statements is exactly that of 𝑞. The compression metric is failed for each state for which we can find a suffix that is accepted by the model prompted with one sequence but not the other. We sample 5 different possible continuation statements, half the time from the set of valid statements, half the time uniformly at random. We note that due to the nature of the compression metric, our reported metric is an overestimate of true capability. So the fact that no model performs above 0.35 with only 5 samples suggests heavy compression failure. We sample 100 states. See Figure 8 for an example of a compression error.For the distinction metric, we again sample states 𝑞 1 ≠ 𝑞 2 and sample sequences that lead to the states 𝑠 1 and 𝑠 2 using the same method as before. Because of the limited state space in our example, we can compute the true Myhill-Nerode boundary tractably. To test recall, we then only need to assess whether statements in the true boundary are accepted when the LLM is prompted by 𝑠 1 or 𝑠 2 .Although the true Myhill-Nerode boundary is tractable to compute, it is still expensive to query an LLM with each example. Instead, we perform Monte Carlo sampling using 𝑀 statements from the true boundary to prompt the model. We consider 𝑀 = 5 in our experiments.We use the OpenAI API to query the GPT models, and use the Together AI API for all other LLMs. We prompt LLMs to perform chain-of-thought reasoning (Wei et al., 2022b) for each query and automatically evaluate answers by prompting each model to output its response with the keyword "Answer:" followed by its answer. All queries are performed with greedy decoding.Our test involves a few parameters, such as 𝜖 (the probability threshold for each model), the maximum suffix length 𝑘 used to approximate the true Myhill-Nerode boundary, and the number of Monte Carlo samples 𝑚 used to approximate the model's Myhill-Nerode boundary.We begin by considering 𝜖, which dictates a tradeoff between precision and recall. In the main text, we consider 𝜖 = 0.01. we see the tradeoff between precision and recall as 𝜖 changes. However, the conclusions are stable: every model has an incoherent world model across values of 𝜖. For example, while the random walks model has high compression and distinction precision for 𝜖 = 10 -6 , it has a very low distinction recall, of 0.11. Meanwhile, while the distinction recall is bumped up to 1.00 for 𝜖 = 0.10, its compression precision falls to 0.16.The metrics introduced in Section 2.4 depend on defining what it means for a model to accept or reject a sequence. In the main text we consider acceptance based on a threshold parameter, which corresponds to an 𝜖-sampling decoding mechanism (Hewitt et al., 2022) . Here, we consider two alternative forms of acceptance based on other decoding strategies: top-𝑘 (Fan et al., 2018) and top-𝑝 (Holtzman et al., 2019) . For acceptance based on top-𝑘, a token is accepted if it's in the model's top-𝑘 ranked tokens for a sequence and rejected otherwise. For top-𝑝, a token is accepted if it's part of the the smallest set of highest-probability tokens whose cumulative probability is larger than 𝑝. Results are depicted in Table 6 and Table 7 and point to the same conclusion as the threshold-based metrics in Section 3; none of the models have recovered the world model, but the model trained on random walks performs best.Our test also relies on Monte-Carlo sampling the model's Myhill-Nerode boundary. The number of samples affects only the precision test. A prefix pair fails the compression test whenever there's one suffix that the model accepts for one prefix and not for the other, so performance should worsen as the number of samples increases. Here we describe the rides dataset construction in more detail. Our empirical studies are based on a dataset of taxi rides in New York from 2014, originally released by the NYC Taxi & Limousine Commission. We use a subset of 15 million rides that took place between January and March 2014, made available by Murray (2017) . We drop duplicate rides and subset the dataset to only include rides in Manhattan, resulting in 3,358,737 sequences. We use the OSMnx library (Boeing, 2024) to represent New York as a weighted graph. We match pickups and dropoffs to the closest intersection, measured in terms of latitude/longitude. The graph consists of 4,580 nodes, 9,846 edges, and each node has a median of 2 valid intersections. We convert bearings to one of 8 cardinal directions. We remove short traversals with two node or less. We also remove sequences with more than 100 tokens.The first approach creates traversals between two nodes by finding the shortest path between them. For each taxi ride in the dataset, we map the pickup latitude/longitude to the closest intersection and do the same for the dropoff location. We then perform Dĳkstra's algorithm to find the shortest path weighted by distance. After filtering out duplicated traversals, we have a training set of 2,932,675 sequences and 120,400,201 tokens, along with a validation set of 1,000 sequences and 41,641 tokens.Noisy shortest paths. Shortest path traversals may not be reflective of real-world traversals due to differences in traffic patterns. Moreover, shortest path traversals between two nodes are deterministic, potentially limiting a model's ability to pick up a world model. Therefore, we construct a noisy version of shortest-path traversals. We do this by modifying the weighting function, W (𝑖, 𝑗) = 𝑊 (𝑖, 𝑗) + 𝜖 𝑖 𝑗 , where 𝜖 𝑖 𝑗 ∼ Gamma(𝑊 (𝑖, 𝑗), 1); we can interpret this as artificially adding traffic to each edge that scales with the original length. We resample 50 different weighting functions. After filtering out duplicated traversals, we have a training set with 30,599,312 sequences and 1,677,587,216 tokens while our validation set consists of 1,000 sequences and 54,539 tokens Random walks. In the last setting, we sample random traversals rather than approximating shortest paths. We construct each sequence by sampling a node uniformly at random, sampling a sequence length uniformly between 3 and 100, and constructing traversals by sampling random edges uniformly at random for the prespecified sequence length. We create a training set of 90,646,864 sequences and 4,735,591,368 tokens, along with a validation set of 1,000 sequences and 52,360 tokens.We use the GPT-2 architecture (Radford et al., 2019) to train models on all datasets. We use the GPT-2 small architecture for the shortest paths model and the GPT-2 extra-large architecture for the noisy shortest paths and random walks models. For the shortest paths models, we train until we overfit and use the best validation checkpoint. For the two larger datasets, we train for a fixed number of epochs and use the last validation checkpoint; we use 5 epochs for the noisy shortest paths dataset and 1 epoch for the random walks dataset. We train all models on 8 A100 GPUs, using a batch size of 6 sequences per GPU. Training time ranges from about 12 hours for the shortest paths model to 48 hours for the random walks model. Justification: For our theoretical results, we state assumptions and provide proofs in the appendix.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.38th Conference on Neural Information Processing Systems (NeurIPS 2024).https://github.com/keyonvafa/world-model-evaluationA real-world intersection may be represented as multiple intersections here. For example, if a turn is only valid from one direction, it is represented as two different nodes.While the next-token test accuracy is rounded to 100%, no model performs perfectly.https://www.mlfoundry.com/ 


Decision: This paper created a robust discussion between authors and reviewers. After carefully reading the paper and the ensuing discussion, I recommend acceptance.

The problem of recovering world models from sequence data is important, and assessing whether or not an LLM has indeed captured such a model is a problem of significant interest in the community. This paper proposes a set of theoretically motivated tests that have more discriminative power than other model-agnostic tests; the authors demonstrate the power of these tests on several interesting problems.  As such, this paper provides an important contribution to the discussion on interpretability.  Furthermore, the paper is very well-written, and has a nice mix of theoretical ideas and practical experiments.

The discussion among the reviewers and the authors hinged on the theoretical underpinnings of these tests, and their properties.  On the theoretical side, the concern raised by the reviewers pointed out difficulties in interpretation of the tests and the essential "type error" between DFAs that accept sequences and generative models that produce things according to probabilities. While I share the type error concern to some extent, I find that the practical utility of the tests, combined with the clarity of the discussion and the issues that the paper raises, outweighs this concern.  It may very well be that these tests need more theoretical refinement, but I am confident that the community will engage these ideas and provide it.  Said another way: I do not believe anything about the proposed tests is /wrong/; I also find that the tests are intrinsically useful and motivated enough to stand independent of any interpretation we may choose to project upon them. The reviewers also had some concerns about the properties of these tests, and whether or not things like relative rankings are consistent.  While we can always demand more theory, more perfection, more power, and more utility, I find that the contribution as it stands is more than sufficient to warrant publication in NeurIPS.

Reviews: review: paper_summary: paper_summary: This paper proposes new evaluation metrics to assess whether a learnt world model is indeed learning the underlying dynamics or logical reasoning required to fully decipher a new domain. The paper sheds light into how world models should be evaluated, compared to what is being done in the literature currently and finds that current metrics can lead to instability or lacks enough evidence that a true underlying world model of the domain is indeed learnt.
strength_weakness: strength_weakness: My only comment would be that the paper should perhaps provide more background and intuition from automata theory, to justify the tools that are introduced to be able to fully understand this work. The core idea seems interesting but the experimental and contributions of the work, if it can be explianed more generally, would perhaps be more useful.
questions: questions: ...
limitations: limitations: ....
paper_summary: paper_summary: This article proposes an evaluation framework for understanding whether or not transformers have learned an implicit world model. Existing metrics focus on next-token prediction and state probes, while this article proposes metrics inspired by the Myhill-Nerode theorem: Whether the network treats two action sequences arriving at the same state as having the same continuations, and whether the network properly distinguishes whether two states differ in allowable subsequent action sequences. They find that across large models trained on taxi data, Othello moves, and logic puzzles, these new metrics reveal far more weaknesses than previous metrics.
strength_weakness: strength_weakness: I don't see real weaknesses. I have a couple minor suggestions for clarification:
- Figure 2 is a clever illustration but it could use some more detail in the caption, and I'm not sure I fully understand it. For the compression test, why are the only errors under the pink line, as opposed to covering other nodes in the graph on one side of the boundary? I have a similar question for the right hand side.
- Ideally the metrics in the tables, "Compression precision", "Distinction precision", "Distinction recall", would be more clearly defined somewhere in bold, like other terms in the article.
questions: questions: - I'm a little puzzled why the models have low distinction precision/recall. If the two states they are meant to distinguish are sampled randomly, why would the model confuse their continuations? Some more intuition here--especially providing example errors-- would be helpful.

- How much training was provided to the models?
limitations: limitations: I see no issues here.
paper_summary: paper_summary: This paper proposes a new metric to assess the implicit world model of generative models, such as neural LMs. Inspired by the Myhill-Nerode theorem, this metric evaluates whether a model can determine if pairs of sequences are equivalent in terms of their underlying state. The author presents two specific metrics: sequence compression (SC) and sequence distinction (SD). For a pair of sequences (e.g., natural text, destination trajectories, or game scripts) that correspond to the same state, SC measures whether neural LMs accept the same set of continuations. Conversely, SD assesses whether neural LMs can accurately distinguish between sets of continuations that are uniquely permissible for one sequence but not for the other.

The paper assumes that the model under test is a Deterministic Finite Automaton (DFA), and hence the model can directly determine whether a sequence is accepted. However, since neural LMs lack this capability, the author suggests using a token-level threshold as a proxy: $\forall t  P_\theta(x_t|x_{1:t-1})> \epsilon$.

Experiments conducted across three datasets with various neural LMs (small-scale Transformers & LLMs) indicate that these models score significantly lower on SC&SD compared to existing metrics. Based on these findings, the authors claims that SC&SD are more faithful.
strength_weakness: strength_weakness: 1. The authors inaccurately summarize existing work and consequently address a non-existent flaw.

>... Toshniwal et al. and Li et al. assess world models by measuring the percent of top model predictions that are valid in the underlying DFA. (L112-113)

This is not true. Li et al. [1] do not solely rely on the validity of the top model predictions to assess the implicit world model. Instead, they directly probe the internal world state from the model, which has been the common practice of existing work ([2], [3]). 

2. There are two fundamental flaws of the proposed metric
     * accountability issue: Poor performance according to the metric could stem from an bad transformation of actions from the world state, rather than a bad implicit world model.
     * It's challenging to ascertain whether a neural LM "accepts" a sequence, which makes it hard for the theoretical guarantees of SC and SD hold in practice. The proposed metric relies heavily on the deterministic nature of the DFA, which directly indicates sentence acceptance. In contrast, neural LMs model distributions over tokens or sentences without a clear mechanism for determining sentence acceptance. The author proposes using a token-level probability threshold as a workaround, yet this approach has several flaws:
       * A top-$k$ predicted sequence may include tokens with low likelihood.
       * Conversely, a sequence satisfying the criteria might not appear in the top-$k$ predictions.
       * Additional confounding variables can affect the metric's value. For example, LMs with higher entropy typically have a larger set of "accepted" sequences. This entropy can be influenced by the hyperparameters of decoding algorithms, training, and fine-tuning methods of the LMs, etc.

3. Lack of empirical evidence that proves the faithfulness of the proposed metric.
     * Considering the loose approximation of the DFA-style acceptance, I expect the author to provide empirical justification of the proposed metric, which is notably missing in the paper. The only evidence presented is the poor performance of existing LLMs on this metric. However, this is insufficient since the lower performance on the metric could be simply because the methods are unfairly penalized. 
    * Also, there is a concerning indication of the metric's questionable faithfulness: the conclusions drawn from the Othello experiments in this paper contradict those of Li et al. [1]. Li et al. convincingly probes Transformer's internal representation of the board state and demonstrates that it can causally influence the Transformers' predictions.

[1] Li, Kenneth, et al. "Emergent world representations: Exploring a sequence model trained on a synthetic task." ICLR 2022.

[2] Yun, Tian, et al. "Emergence of Abstract State Representations in Embodied Sequence Modeling." Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

[3] Karvonen, Adam. "Emergent world models and latent variable estimation in chess-playing language models." arXiv preprint arXiv:2403.15498 (2024).
questions: questions: 1. Did you try other acceptance criteria that go beyonds manipulation of threshold value, e.g. sequence-level probability/rank?
limitations: limitations: The author doesn't address the limitations discussed above in the paper.
paper_summary: paper_summary: This paper aims to develop new metrics for assessing a model’s ability to recover a world model. The key idea is to test coherence with respect to the world, guided by the Myhill-Nerode theorem for deterministic finite automata (DFA). Specifically, if the true world model is a DFA, the learned world model should meet two requirements: (1) sequences leading to the same DFA state must have the same continuations, and (2) sequences leading to distinct DFA states should have distinct continuations. Based on these principles, the authors proposed three new metrics: compression precision, distinction precision, and distinction recall.

To test these metrics, they trained a GPT model on New York City taxi rides, hoping the GPT would learn a map of NYC. They found that the trained transformer model performed nearly perfectly using classical methods for testing world models, such as next-token prediction and state probe. However, under their three proposed metrics, the trained model appeared not to learn the world model at all, suggesting that these new metrics might be a valuable alternative for evaluation.
strength_weakness: strength_weakness: 1. Generalizability of the proposed metrics

The main concern I have with the proposed metrics is their generalizability. The metrics are strictly applicable when the true world model is a DFA. While this might be suitable for the New York City map and the Othello game, it is not directly applicable to Logic Puzzles. The issue is that Logic Puzzles are prompted using natural language (see Fig. 22), and natural language texts cannot be accurately modeled as DFAs. Although one could argue that the same state is reached via different prompts at the latent concept level, language models do not operate directly on this latent concept space. Instead, they work on the token level, which cannot be represented as a DFA.

This limitation significantly restricts the scenarios in which the proposed metrics can be applied. In contrast, the two existing metrics (next-token prediction and state probe) are applicable regardless of the true world model. This fundamental limitation could impact the overall significance and applicability of the study.

2. Inter-metric consistency problem

Despite the limitations of the proposed metrics, they would still be valuable if they performed well under the DFA assumption in indicating world model recovery. However, there is a lack of inter-metric consistency. In Table 1 (Random Walks row), almost all metrics, except for the proposed Compression Precision metric, indicate that the model perfectly captures the world model. This inconsistency raises questions: What is the correct conclusion when two out of three metrics suggest the presence of a world model, while the other does not? How can these metrics be relied upon if there are substantial internal inconsistencies based on the statistics motivated by the Myhill-Nerode theorem?

Resolving this issue in practice may be challenging. It appears that the three proposed metrics have low false negatives (i.e., they perform well when the model does not learn the true world model, similar to existing metrics). However, they seem to have high false positives (i.e., the statistics struggle to detect if a model has actually learned the world model). Resolving this issue may be difficult because it likely requires substantial knowledge of the true world model to develop the appropriate statistical corrections for sampling two sequences that reach the same DFA state.
questions: questions: What was the context length for your GPT model? This is crucial, as a context length that is too short for the type of data presented to the model will negatively impact its performance.
limitations: limitations: The main text lacks an explicit section on Limitations and Future Research. However, the authors acknowledged in the Conclusion that their primary limitation was the focus on deterministic finite automata.

Minor comments:

Line 76: “our evaluation metrics are based sequences” —> “our evaluation metrics are based [on] sequences”

Comments: comment: Thank you for continuing to engage with our paper.

> _The findings they gain from these testbeds are their primary contributions. In contrast, the main contribution of your manuscript lies in the newly proposed metric_

Our paper not only proposes new metrics but also provides new findings about world models in testbed settings: we demonstrate that models previously thought to have correct world models, based on existing metrics, actually do not.

> _A useful metric should differentiate between relatively good and relatively bad models—common scenarios in real-world applications—instead of merely distinguishing between the extremes of obviously good (training & testing in the same domain) and obviously bad (serious exposure bias)._

We agree. We'd like to clarify a potential confusion: It's not true that our metrics can only be used to compare obviously good and obviously bad models. They are not arbitrary scores; they are grounded in a theoretically-based formulation of what it means to learn the structure of the world model. Consider the Random Walks model; it is good enough to pass the distinction test and performs better than the other models when detours are introduced, but still bad enough that its map is incoherent to us and it eventually fails when enough detours are added. Our metrics capture the difference between the Random Walks model and the other models trained on taxi data. 

Additionally, in addition to our experiments on models trained in synthetic testbeds, we devote empirical work to applying our metrics to 8 commonly used LLMs (Figure 4). 

> _If we only use the top-ranked prediction in practice, why should we be concerned with other "accepted" sequences?_

If the only way a practitioner generates from an LLM is by using its top-1 prediction, then you're absolutely correct that they should only use the top-1 mechanism for our metrics (as provided in the rebuttal). But in practice there are many different ways people can decode from LLMs, each of which provide different notions of acceptance and rejection (see e.g. [1] for common decoding strategies). Our paper considers these to capture the diversity of ways in which practitioners decode from LLMs.

[1] https://arxiv.org/abs/2402.06925
> Like other papers about world model metrics [1, 2], we validate our metrics on models trained on artificial data.

Their papers don't propose new metrics but rather use chess and Othello as testbeds to probe the implicit world models of Transformers. The findings they gain from these testbeds are their primary contributions. In contrast, the main contribution of your manuscript lies in the newly proposed metric. A useful metric should differentiate between relatively good and relatively bad models—common scenarios in real-world applications—instead of merely distinguishing between the extremes of obviously good (training & testing in the same domain) and obviously bad (serious exposure bias).

> These results are from Table 2 in [1]. The lowest probe error is 9.4% for Championship (layer 4 representation) and 1.7% for Synthetic (layer 7 representation). This corresponds to 90.6% accuracy for Championship and 98.3% for Synthetic.

Thanks for the clarification. It seems we're on the same page: their probing test has identified the difference between Synthetic and Championship, though with less magnitude than yours.

> We performed multiple top-k ablations because of your suggestion to consider top-k sampling. This was a great suggestion: Even if top-1 predictions are typically used for reasoning, it certainly isn't the only sampling mechanism, and our experiments show the robustness to sampling mechanisms.

This isn't quite my question. What I’m really asking is: if we only use the top-ranked prediction in practice, why should we be concerned with other "accepted" sequences? Especially since acceptance is defined post-hoc, rather than being an intrinsic characteristic of the models.
Thank you for continuing to engage with our paper. We appreciate the continued discussion. 

> _Could you direct me to the specific paragraph or section where this result is reported?_

These results are from Table 2 in [1]. The lowest probe error is 9.4% for Championship (layer 4 representation) and 1.7% for Synthetic (layer 7 representation). This corresponds to 90.6% accuracy for Championship and 98.3% for Synthetic. 

> _But nearly all models achieve their best metric scores in this setting. No?_

Most models have better precision metrics when k=4 than lower k because of the intuition described in the last response: as more sequences are accepted, a model will accept more suffixes, meaning that precision typically improves. Recall has the opposite intuition. Note these are not strict 1-1 mappings, e.g. the recall for the Random Walks model gets worse for k=4 but better for the Shortest Paths model. We implemented the top-k metrics thanks to your suggestion and think they're useful to include in the paper, but the sensitivity of top-k metrics to the number of legal moves is why we prefer epsilon-based and top-p sampling. 

> _I will reply to other responses later._

Thanks again for your engagement. Please let us know if you have any other questions. 

[1] https://arxiv.org/abs/2210.13382
Dear author,

I have some quick questions.

> *The best probe accuracy for the Championship model from Li et al. [1] is indeed lower than the best accuracy for the Synthetic model (90.6% vs 98.3%).*

Could you direct me to the specific paragraph or section where this result is reported?

> *While we included top-k with the k=4 ablation for completeness, it is not an especially useful decoding mechanism for navigation.*

But nearly all models achieve their best metric scores in this setting. No?

I will reply to other responses later.
> _However, since you're proposing evaluation metrics, they should be applicable to more realistic models, not just those trained artificially. What happens if two models are trained on the same dataset, and their performance gap is much smaller?_

Like other papers about world model metrics [1, 2], we validate our metrics on models trained on artificial data. It is theoretically possible for model performance to depend on the decoding mechanism. It could imply that the models are so close in the amount of world model structure they capture that their performance depends on the decoding mechanism. 

You're correct that noisy shortest paths would involve more random exploration during training compared to shortest paths. It's a good question why it performs worse. One possibility is that it reaches a middle ground between random and constrained exploration that means it can't reap the benefits of either extreme. While we focus on world model metrics, it's important for future work to assess _why_ some models have world models and others do not

> _Indeed the gap between Championship and Othello in terms of differentiating between invalid moves and very bad moves are captured by the probe tests in Li et al. (2022). As shown in their Table 2, the error rate with Synthetic is significantly lower than with Championship._

The best probe accuracy for the Championship model from Li et al. [1] is indeed lower than the best accuracy for the Synthetic model (90.6% vs 98.3%). However a challenge of probing tests is the difficulty of distinguishing between two high scores [3, 4, 5] (Li et al [1] make no difference in their conclusions for each model's world modeling capabilities). In contrast, our metrics clearly differentiate the two Othello models (e.g. 0.98 compression precision for Synthetic and 0.00 for Championship) which is validated on detours (e.g. 99% accuracy for Synthetic with 0.50 detours compared to 1% accuracy for Championship). 

> _Sequence generation models are typically trained to maximize the probability of ground-truth sequences, making the selection of the top-ranked prediction—essentially MAP estimation—consistent with their training_

Note that this is defining an acceptance criterion: top-k with k=1. Our metrics apply to this setting and we included experiments based on them. We also tested multiple ablations and two other sampling mechanisms to capture the diversity of ways in which it is possible to decode from LLMs. We believe it is important to consider various settings instead of constrain ourselves to a single one. 

> _Moreover, if the top-1 prediction is typically used for reasoning tasks that rely on underlying world models, why should we be concerned with the consistency of top-k predictions?_

We performed multiple top-k ablations because of your suggestion to consider top-k sampling. This was a great suggestion: Even if top-1 predictions are typically used for reasoning, it certainly isn't the only sampling mechanism, and our experiments show the robustness to sampling mechanisms. 

> _But when it comes to those hyperparameters and decoding algorithms, how exactly do they influence the metric values? For example, why does top-p decoding (p=0.999) result in a higher metric value for Random-walks compared to top-k decoding (k=4), yet performs worse for Shortest-path?_

There are patterns for how performance varies with threshold. For example, compression precision will typically increase as more sequences are accepted. This is because as more sequences are accepted, it is more likely that a model will accept a suffix for two prefixes that lead to the same state. While it's not an exact 1-1 mapping, we find this to be true for almost all models we consider. 

While we included top-k with the k=4 ablation for completeness, it is not an especially useful decoding mechanism for navigation. This is because there are only 8 possible cardinal directions, not all of which will be legal moves, and so decoding with top-k (k=4) can force the model to select sequences that aren't legal. 

[1] https://arxiv.org/abs/2210.13382  
[2] https://arxiv.org/abs/2102.13249  
[3] https://arxiv.org/abs/2102.12452   
[4] https://arxiv.org/abs/1805.01070   
[5] https://arxiv.org/abs/2004.03061
Thanks for continuing to engage with our paper. We appreciate your feedback and will clarify our paper. 

> _I believe the root cause is this: "our metrics assess whether a model has a world model by assessing the outputs of the model."_

We think a helpful comparison for our metrics is the next-token test performed by Li et al [1] and Toshniwal et al. [2]. Like our metrics, this test seeks to evaluate world models by the _behavior of their outputs_. Once we've established that a model behaves like it has the true world model, we can ask questions about the mechanism for why it behaves like that (e.g. via probing). For example, only after showing that OthelloGPT performs well on the next-token test do Li et al. [1] perform probing tests. The goal of our metrics is to test whether a model, when using common decoding schemes (we evaluate three different schemes), behaves like it has the true world model. For both our metrics and the next-token test, if a model's generations are influenced by factors like entropy, it would show up when practitioners decode from the model, and is therefore crucial for incorporating into metrics that assess world model behavior.

At a high level, we believe that metrics which evaluate a model in a black-box manner, just based on observing their generative behavior, are vitally important and qualitatively distinct from those which rely on a certain implementation and/or internal parameters (we agree these are also useful). Several of the benefits of black-box metrics are the following
 - They directly measure the quality of the actual thing we care about: the sequences generated by the model.  
 - They can be applied to any language generator, regardless of implementation. This also means that humans can be evaluated by the same measurements to get a baseline to compare models against.  
 - They provide a definition of what it means to have recovered a world model which is generic.  

We believe that the question “does a language model have an implicit world model?” can and should be evaluated by metrics that look only at the outputs of the model. Prior works [1, 2] introduced the ingenious idea of testing this question on rules-based systems (i.e. games and other types of DFAs) where we know the true world model. Our interpretation of having a world model corresponds to recovering the state space of the system. Automata theory tells us that this is the correct way of understanding these systems. **Recovering the true states of the world corresponds to an intuitive notion of capturing the world model.** The key idea is using this connection to automata theory to understand how well states are captured just by looking at sequences. We believe this connection as well as the extensive evaluation on new and standard tasks for interrogating world models contributes an important contribution to this line of work.

>_I agree. But I'm not sure the model performs poorly on detours/proposed metrics if and only if it's inconsistent with the true world model. Even if there is some inconsistency, it might be exaggerated—or maybe even minimized_

We're glad you agree that models whose outputs are consistent with the true world model will perform well on detours. Then we have the following:
- If a model performs poorly on detours it doesn't behave like the true world model   
- Models like Synthetic Othello perform poorly on detours   
- This means they don't behave like the true world models   
- Previously proposed metrics suggest that all models we consider (including Synthetic Othello) do behave like correct world models
- Our metrics correctly measure that they don't. 

This is a contribution of our work: we not only show that previously proposed metrics can lead to incorrect conclusions about world models, we also propose and validate new ones. We'd be happy to discuss any aspects of this further if you have questions or would like additional clarification.

We agree that while poor performance on detours implies an incorrect world model, an incorrect world model can still perform well on detours. This is why it's important to have metrics that fully measure world model structure, like the ones we propose. Our detours exercise serves as one-way validation, which is the direction of disagreement between our proposed metrics and existing ones.
Thank you for your follow-up response. It helped me sort out some disagreements between us.


I believe the root cause is this: "our metrics assess whether a model has a world model by assessing the outputs of the model. " While you state that you're evaluating the "implicit world model" of generative models, it seems to me that the outputs—and therefore the metrics—are influenced by various factors (such as the entropy of the learned distribution, decoding hyper-parameters, and algorithms) beyond just the implicit world model.

```
The detours exercise assesses the outputs of a model. A model whose output is consistent with the true world model will perform well on detours
```

I agree. But I'm not sure the model performs poorly on detours/proposed metrics if and only if it's inconsistent with the true world model. Even if there is some inconsistency, it might be exaggerated—or maybe even minimized; I'm not sure. The new results you presented earlier clearly confirm this concern.


```
And our results across thresholding parameters and sampling mechanisms point to the same final conclusions.
```

To be frank, I'm not sure I fully understand your point. If you're suggesting that the relative ranking of Random-walks > Shortest-paths > Noisy-shortest-paths is consistent across different decoding methods/hyperparameters, that's accurate. However, since you're proposing evaluation metrics, they should be applicable to more realistic models, not just those trained artificially. What happens if two models are trained on the same dataset, and their performance gap is much smaller? How can we ensure their relative ranking will still hold? This level of hyperparameter sensitivity raises concerns about the reliability of these metrics.

On a related note, I have another question: why does Shortest-paths outperform Noisy-shortest-paths? If I understood correctly, Noisy-shortest-paths should involve more random exploration during training compared to Shortest-paths.

```
Our hypothesis as to why the Championship Othello doesn't have the correct world model is similar to your intuition -- that the way it's trained prevents it from differentiating between invalid moves and very bad moves
```
Indeed the gap between Championship and Othello in terms of differentiating between invalid moves and very bad moves are captured by the probe tests in Li et al. (2022). As shown in their Table 2, the error rate with Synthetic is significantly lower than with Championship.


```
To implement these metrics, we need to define what it means for a model to accept or reject a sequence. This isn't unique to our setting; one way that Li et al [1] and Toshniwal et al. [2] test world models is by looking at whether the top-ranked prediction of a model is legal. 
```


Your setting is indeed unique. Sequence generation models are typically trained to maximize the probability of ground-truth sequences, making the selection of the top-ranked prediction—essentially MAP estimation—consistent with their training. While it's possible to use heuristics to sample multiple sequences from the distribution and argue that these sequences are "accepted" by the distribution (though what it means for a sample to be "accepted" by a distribution is unclear to me), this approach of inference differs from how the models are trained. This inconsistency arises due to the evaluation method, so it's questionable to blame the models if they don't perform well under these conditions. Moreover, if the top-1 prediction is typically used for reasoning tasks that rely on underlying world models, why should we be concerned with the consistency of top-$k$ predictions?

```
The dependence on a thresholding parameter is not a weakness; it's crucial for decomposing error into precision and recall and measuring AUC.
```

I'm not quite sure how those decoding hyperparameters function similarly to a classification threshold. With classification thresholds, it's easy to predict how adjusting them will affect precision and recall, making it a useful tool for balancing the precision-recall tradeoff. But when it comes to those hyperparameters and decoding algorithms, how exactly do they influence the metric values? For example, why does top-p decoding (p=0.999) result in a higher metric value for Random-walks compared to top-k decoding (k=4), yet performs worse for Shortest-path?
Thank you again for taking the time to review our paper. We appreciate your comments and believe the paper will be stronger because of them. 

We were wondering if you had any more questions our review didn’t address. Since the discussion period ends tomorrow we want to make sure we have time to address your points. If you don’t have any more questions, we hope you’d consider changing your score.
Thank you for engaging with our paper. See our responses below.

> _Summary of existing work_

Thank you for clarifying your initial comment: _“Li et al. [1] do not solely rely on the validity of the top model predictions to assess the implicit world model. Instead, they directly probe the internal world state from the model, which has been the common practice of existing work ([2], [3]).”_

We're glad it's clear that our paper not only describes the probe test of Li et al. [1] but also devotes empirical work to it. 

> _I find it somewhat unclear how detour performance serves as a valid indicator in this context. Specifically, how can we be certain that the performance is solely influenced by the world model?_

This is a good question. We'd like to clarify a potential confusion about our paper: our metrics assess whether a model has a world model by assessing the _outputs_ of the model. In contrast, tests like the probe test do not test world models via their outputs, only their mechanisms (e.g. whether a representation encodes state and/or how a model uses this representation). This is why we and Li et al [1] include both kinds of metrics.

The detours exercise assesses the outputs of a model. **A model whose output is consistent with the true world model will perform well on detours**; the detours exercise passes valid inputs to the model and sees if it can complete them successfully. In practice, we find that the detours exercise amplifies world model errors. The Championship Othello accuracy falls to 1% when detours are common, behavior that is not consistent with a model with the true world model. Our hypothesis as to why the Championship Othello doesn't have the correct world model is similar to your intuition -- that the way it's trained prevents it from differentiating between invalid moves and very bad moves. But our paper is focused on measuring whether a model behaves like the true world model rather than the reason as to why or why not. 

> _DFA are designed to accept or reject sequences through checking transition rules. In contrast, auto-regressive generative models don't have such mechanisms._

Our metrics test whether a model's behavior obeys ground-truth rules. To implement these metrics, we need to define what it means for a model to accept or reject a sequence. This isn't unique to our setting; one way that Li et al [1] and Toshniwal et al. [2] test world models is by looking at whether the top-ranked prediction of a model is legal. Of course, a model generates more than one top-ranked token, and our different metrics and ablations provide different specifications.

The results you point out are not contradictory. If a model has the true world model, all metrics (compression precision and distinction precision/recall) will score 100%. Conversely, if any metric is less than 100%, it won't have a perfect world model. As you note, once the metrics aren't perfect, their performance can differ and vary with a threshold parameter. To give a simple example: it's easy to ace compression (by saying every sequence has the same continuations) but then distinction suffers. 

This is similar to supervised learning: sensitivity and recall are all the same for a perfect classifier, but can differ for imperfect models in ways that vary with a thresholding parameter. The dependence on a thresholding parameter is not a weakness; it's crucial for decomposing error into precision and recall and measuring AUC. And our results across thresholding parameters and sampling mechanisms point to the same final conclusions. 

Thanks again for engaging with our paper. We'll update the paper in the revision to make these points more clear.

[1] https://arxiv.org/abs/2210.13382  
[2] https://arxiv.org/abs/2102.13249
Thank you for engaging with our paper. We're glad our rebuttal addressed some of your concerns. Here we attempt to answer your remaining questions:
- We want to clarify a potential confusion: while it's correct that any metric less than 100% implies there is no world model, the **metrics can also be directly compared to one another.** This is again similar to supervised learning: while there's a tradeoff between false positive rate and false negative rate, if one model always has a better false positive rate and false negative rate, it is doing better than another model, even if it's imperfect. Our metrics are not arbitrary scores; they are grounded in a theoretically-based formulation of what it means to learn the structure of a world model. We also validate this empirically: for each model (across maps and Othello), a model's ranking on our metric is exactly its ranking on the detours exercise (for all three metrics and both kinds of detour exercises).  
- Our results would still be interesting even if our metrics only captured whether there is a world model or not. This is because **prior metrics would lead us to conclude that all models we test across maps and Othello do have world models.** Our metrics are capturing something new, and this is not only motivated theoretically but also validated empirically on 1) map reconstruction and 2) detour exercises on Othello and maps.
Thank you for the rebuttal. While some of my concerns were addressed, I remain concerned about the applicability of the developed metric. It appears that this metric is effective primarily when the true world model has been fully learned. In cases where the world model is imperfectly learned, the metric may not be reliable, as it does not provide directly comparable scores among imperfect models. Although achieving 100% on all metrics indicates that the true DFA has been learned, scores below 100% only confirm that the model is imperfect, without offering a clear measure of the degree of imperfection.
Thank you for your rebuttal and the updated results. My responses are below.


## Summary of existing work

```
 Your review states that we ignore the probe test of Li et. al [1]. 
```

No, it doesn't.

My criticism that *"The authors inaccurately summarize existing work and consequently address a non-existent flaw"* is directly related to the specific statement I referenced from your manuscript: *"Toshniwal et al. and Li et al. assess world models by measuring…"*. Given that your proposed metrics are motivated by the shortcomings of existing work, it is essential to faithfully represent those work and to identify actual, rather than imagined, flaws.

Nonetheless, I consider this to be a relatively minor issue, one that can be addressed through some clarification, particularly when weighed against the validity of the proposed metrics.



## Validity of the metrics

```
We validated our metrics in the original submission by showing 1) they capture behavior other metrics don't and 2) they correlate with detour performance for the taxi exercise (Table 2). We now include additional validation for Othello using detours.
```

It's good to have multiple metrics, but it's also crucial that each one holds validity. I find it somewhat unclear how detour performance serves as a valid indicator in this context. Specifically, how can we be certain that the performance is solely influenced by the world model? For instance, could you clarify why $\text{Synthetic}$ appears to possess a near-perfect world model, whereas $\text{Championship}$ doesn't? To me, it's a typical phenomenon of exposure bias rather than a specific issue of implicit world model. $\text{Championship}$ is trained on expert data, where the prefix trajectories fall within a rather limited distribution. In contrast, $\text{Synthetic}$ is trained on randomly generated legal trajectories, which are distributed more evenly. As a result, the disparity between training and testing is significantly smaller for $\text{Synthetic}$ than for $\text{Championship}$.


```
Common decoding strategies do provide mechanisms for determining sequence acceptance, like top-k, top-p, and threshold-based sampling (i.e. epsilon sampling)
```

I respectfully disagree.  It seems there might be some conflation of concepts here. DFA are designed to accept or reject sequences through checking transition rules. In contrast, auto-regressive generative models don't have such mechanisms. All they have are token-level distributions and they are not trained to accept all "legal" sequences. Although it's possible to implement post-processing functions to pull an acceptance label out of it, such functions can influence metric scores, potentially weakening the soundness of the evaluation. Particularly, it's well known that the commonly used sampling-based decoding methods, e.g. top-p sampling, tend to select sequences that diverge significantly from the generative models' modes.

I'm looking at Table 2 (top-k sampling) in the new pdf. With k=1, the scores for $\text{Random walks}$ are 0.40, 0.69, and 0.30, respectively. However, when k=4, these values rise to 0.64, 0.98, and 0.51. The disparity is quite pronounced to me. 

When it comes to Table 3 (top-p sampling), the compression precision for $\text{Random walks}$ is  0.16 when p=0.9 but 0.73 when p=0.99. The results somehow confirm my concerns.
Thanks for your reply. I reaffirm my very positive assessment of the work!