Evaluating the World Model Implicit in a Generative Model
Authors: Keyon Vafa
Justin Y. Chen
Ashesh Rambachan
Jon Kleinberg
Sendhil Mullainathan
Venue: NeurIPS 2024 spotlight (2024)
Keywords: world models
large language models
evaluation
Primary area: evaluation
TL;DR: We develop new evaluation metrics for world model recovery based on formal results in language theory, revealing that generative models often harbor inconsistent world models despite performing well on standard tests across various domains

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.

Evaluating the World Model Implicit in a Generative Model
Keyon Vafa Harvard University
Justin Y. Chen MIT
Ashesh Rambachan MIT
Jon Kleinberg Cornell University
Sendhil Mullainathan
MIT
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 metries 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 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 given model is to that goal.
Introduction
Large language models (LLMs) appear to have capacities that far exceed the next-token prediction
task they were trained to perform [17, 39, 35]. Recent work suggests reason: they are implicitly recovering high- figh-fiielity representations of the underlying domains they are trained on [1, 20].
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 search algorithm to provide directions. The success of language models suggests an alternative approach: collect turn-by-turn sequences from trips in city (e.g. "East North...") and then train sequence model on them. If the sequence model successfully recovers the world model, we would obtain map of the city without ever mapping 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 [7, 21, 3, 14, 6].
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. [36] and Li et al. [20] 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 [19], location tracking [28, 9], games [36, 20), and several of the scientific applications described above. As result, the "world" these domains can be modeled deterministic finite automaton (DFA).
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

We show the difficulty in evaluating implicit world models. Consider an existing approach: for 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 [36, 20]. Though intuitive, this approach can fail to diagnose severe problems, and we illustrate this concretely. The classic Myhill-Nerode theorem [26, 27] 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--erood 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-by- turn 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 valid turn nearly 100% of the time and their state
very well: their predicted next-direction 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 '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 pooreticalllyggoundde
evaluation metries 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.'
Related work. Our paper builds on influential work studying whether generative models recover a world model in the context of games. Toshniwal et al. [36] and Li al. [20] pioneered the study of games as testbed for world model evaluation, studying tests for chess and Othello, respectively, which were further studied by Hazineh et al. [10] and Kuo et al. [18]. 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 neural network's 's representation can recover some
state [11, 19, 1, 16, 20]. 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 lit- erature [31, 32]. For example, Patel & Pavlick [28] show that larger LLMs ground spatial concepts like cardinal directions to locations in a grid world and generalize to various grid layouts. Relatedly, Schu- mann Riezler [30] demonstrate that transformer-basee in language from underlying graphs. Additionally, Guan et al. [9] use LLMs to perform planning tasks from natural language descriptions. Our results suggest that LLMSs can perform some of these tasks well (such as finding shortest paths between two points on map) without having coherent world model.
models can generate navigation instructions
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 [34, 4. 22. 23, 24]. ealllllaaaabbbl

---

Most relevant to our work, Liu et al. [22] show that low-depth transformers can theoretically represent any finite state automata, and show that transformers trained explicitly 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 given model recovers the underlying DFA.
2 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 a E Σ, and sequences s (a), .2......... Let '' denote the collection of sequences on the alphabet.
generative model m(.): E' A(E) is a probability distribution over next-tokens given imput sequence. That is, m(s) A(E), and m(a is the probability assigned to token a E Σ given an input sequence s. Starting at sequence s, the set of non-empty sequences the model can generate with positive probability is:
Generative models.
L'
(s) = {aiaz..ax Vj < k, m(aj+1 saa...ay) > 03.
For simplicity, we write the equation above for next-tokens with nonzero probability, but in practice we set a minimum probability > O corresponding to next-tokens with negliiiiie probability.
Deterministic finite automata (DFA). We use standard notation for a deterministic finite state automaton W (Q, Σ, 6, qu. F) (see Appendix C for complete definition). As simplifying assumption, we consider the case where there a special state Qreject with no outgoing transitions and F= Q {grejott (i.e., the DFA accepts all valid states). An extended transition function å takes state and a sequence, and inductively applies to each token of the sequence. A token or sequence is valid if and only if the output of 5 or respectively starting from qo is not Qreject-
We define I. W (q) to be the set of valid, non-empty sequences that are accepted by the DFA starting at state q. We also define (s)) E F to be the state that sequence leads in the DFA starting from go and (g) C E to be the collection of all sequences that lead from state go to state in the DFA.
2.1 Recovering world models
Throughout this paper assume that the ground-truth sequences used to train and test generative model belong to the language of a deterministic finite state automaton W. This generalizes past work (e.g., assuming sequences come from legal moves in game [36, 20]) and allows to formally define world recovery.
Definition 2.1. generative model m(-) recovers the DFA W if
Vq E F.Ys E S(q): L (q) (s)
That is, recovery requires that a sequence can be generated with positive probability by the model m(-) if and only if the sequence is valid in the DFA W.
Recovery is defined at the language level. However, generative models often built and evaluated token-by- by-tkenn- turns out that exact next-token prediction is enough for recovery of the language of the world model.
Definition 2.2. A generative model m(-) satisfies exact next-token prediction under the DFA W if
Vq F, Vs S(q), Va E Σ: m(a 5) > 0 = 8(g. a) 9reject-
Proposition 2.3. generative model m(-) recovers the DFA W if and only if it satisfies exact next-token prediction under the DFA W.
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 al. [36] and Li et al. [20] assess world model recovery is by measuring the percent of top next-token predictions that are valid.
3

---

Myhill-Nerode Boundary
Interior
Valid for
State State 2 Nelther
Figure 1: On the left, visual depiction of Myhill-Nerode boundary and interior. On the right, examples The shortest sequence
of for cumulative Connect-4. Both states have the same of valid the Myhill-Nerode houndary has length 4, the boundary contains sequences up length 30. The interior contains approximately 8.8 1o sequences of length 29 that do not distinguish the two boards.
2.2 Next-token prediction a fragile metric for recovering structure
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 simple example.
Example: Cumulative Connect-4. Consider vertical grid with n rows and columns. Two players take turns dropping disk in column, and they can choose any column that contains less than disks. When disk 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 7n moves, regardless whether a player has achieved four in a row. Games are represented sequences of moves, where each sequence has 7n tokens and each token is an integer between and 7 indicating the column the disk is placed in. Here, Σ = { .l..... 7} denotes the columns and the state corresponds to the count in each column. A column a valid move if that column is not already filled.
Consider generative model that outputs {1,.... 7} with uniform probability given any sequence, i.e. m(a 5) m(a' (a' ss)) = 1/7 for all a, a' E Σ and s, s' E E' 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 near-perfect next-token predictor when is large. For example, when n 1000, predicts valid next move for more than 99% of all states. Metrics based on next-token prediction will imply this algorithm is close to recovering world model.
2.3 The Myhill-Nerode interior and boundary
Cumulative Connect-4 points general fragility in next-token prediction as an evaluation metric that can be understood in the context of the Myhill-Nerode theorem [26, 27], classic result from language theory. The Myhill-Nerode theorem states that the sets of sequences accepted by minimal DFA starting at two distinct states are distinct (see Appendix C. for full statement). More formally, for states 41 # q2, we have L. (q1) # L. W. (q2). However, while distinct, the two sets may exhibit great deal of overlap. Cumulative Connect-4 exhibits this behavior; any board for which there are less than & disks each column will have the same set valid moves for the next n k moves. This intuition motivates pair of definitions:
Definition 2.4. Given DFA W, the Myhill-Nerode interior for the pair qı, 42 E F is the set of sequences accepted when starting at both states:
"N (q). q2) = (se s (L())(9)))
The Myhill--erode boundary is the set of minimal suffixes accepted by DFA 91 but not 92:
MNB" (q1. = (s aja2...a s L (q1) L (q2) and vj k aq...aj E MNI (q1. 42)).
Figure depicts example Myhill-Nerode interior and boundary for cumulative Connect 4. 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

---

Compression Metric
Distinction Metric
Valid for
m
41 92 Neither
Q1
Boundary
Truth
$2
92
Generative Model
Boundary Errors
Distinction Errors
Compression Errors
Figure visual depiction our two evaluation metrics. compression error a model failing to recognize that two sequences that result in the same state should accept the failing find the right distinguishing suffixes for two sequenees that lead to different states. Our metries measure errors at the boundary, which are visually depicted above.
same suffxess. A distinction error is model
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 metries and (ii) apply these to several applications.
2.4 Compression and distinction metries for evaluating world models
We propose metrics to evaluate a model's 's implicit world model by comparing the true Myhill-Nerode boundary to the one implied by the model.
Definition 2.5. For two sequences $1, s2, the Myhill-Nerode boundary implied by model m(-) is
MNB" (s), = {xx = Xi... (s) (L") and j < k :x.... (s))) (I)
This is the of minimal suffixes that accepted by the model conditioned on sı but not 82. Since we now focus on the generative model rather than the DFA, the definition refers to pairs of sequences rather than pairs of states.
Our evaluation metrics summarize how well a generative model identifies sequences that distinguish a given pair of states. Given pair of states qı and q2, the metric is formed by first sampling sequences that lead to each state, 81 E S(q1) and $2 E S(q2). 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 m(-) with respect to a DFA W is defined as
MNB (2) O (s) (s2()))
[MNB (91.
and the boundary precision is defined as
MNB (SI, 52) JMNB (s).
n (L (q1) \ L L (92))
(3)
Notice that boundary recall and boundary precision 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 7) with equal probability will perform poorly these metries; 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 41 42- Since a DFA provides multiple ways to arrive at the same state, this test assesses whether generative model recognizes that two sequences correspond to the same state. For example, in cumulative Connect-4, there may multiple sequences that arrive the same board position. Recall undefined for equal states because there is no true boundary, our compression metric only reports
5

---

precision, averaged over states sampled uniformly at random (we say a generative model's 's precision if its boundary correctly empty).
Sequence distinction metric. To evaluate sequence distinction, we sample distinct state pairs, i.e. q1 42- Here, there must be true boundary, we test how well 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 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 metries therefore depend on acceptance threshold parameter e > O. In practice, we explore sensitivity to different values of e and other acceptance mechanisms. We present ablations and other details in more depth in Section 3 and Appendix E.
3 Illustration: Do Transformers Recover the Street Map of New York City?
To illustrate these metrics, we create 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 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.
3.1 Data and 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 intersections and streets in New York City. The graph is defined as G (V, E, W), where V is the set of intersections, the set of streets, and W E - R+ a weighting function containing the distance of each street.² Each edge is labeled corresponding to its cardinal direction, represented as a function D V x V - (o. N, S, E, W. NE, NW, SE, SW} with O 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).
traversal is 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 special und-of-sequence token. Figure 5 gives an example of a set directions and the corresponding path. Since this language corresponds to DFA W with [V/2 accept states, corresponding all combinations of current intersection/destinatie apply the evaluation metrics in Section 2.4.
intersection pairs and an additional end state, we can
We randomly split data into train and test splits, ensuring no originndestnnation pair is in both train and test sets. We include all sequences containing less than 100 directions. Our training sets consist of 2.9M sequences (120M tokens) for shortest paths; 3 31M sequences (1.7B tokens) for noisy shortest paths; and 91M sequences (4. (4.7B tokens) for random walks. We train two types of transformers [38] from scratch using next-token prediction for each dataset: an 89.3M parameter model consisting of 12 layers, 768 hidden dimensions, and 12 heads; and a 1.5B parameter model consisting of 48 layers, 1600 hidden dimensions, and 25 heads. We follow the architecture of GPT-2 for each model [29]. We train models on
A 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.

---

Existing metrics
Proposed metrics
Next-token
Current state
Compression
Distinction
Distinction recall
test
probe
precision
precision
Untrained 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.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 enrors in parentheses). Models that do well on existing metrics can perform poorly on ours.
A10 GPUs. For each dataset, we analyze the model with the best held-out performance: the 89.3M parameter model for shortest paths, and the 1.5B parameter for noisy shortest paths and random walks.
3.2 Evaluating world models
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 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 [36, 20]. 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 [1 J] from a transformer's 's representation to predict the current intersection implied by the directions far. We train linear probe transformer's 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 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 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 e = 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 summarizes our results. As references, we compare each trained transformer to a randomly initialized transformer baseline following Li et al. [20] 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.'
Our evaluation metrics, however, reveal that these existing diagnostics are incomplete. All trained transformers perform poorly on sequence compression, frequently failing to recognize that two 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; model can perform well on one metric and poorly on the other. Here, a model that
While the tokt-token test accuracy is rounded to 100%, no model performs perfectly.
7

---

(a) World model
(b) World model with noise
(c) Transformer
Figure 3: Reconstructed maps of Manhattan from sequenees produced by three models: the true world model (left), the true world model corrupted with noise (middle), and a transformer trained on random walks (right). Edges exit nodes in their specified cardinal direction. the zoomed-in images, edges belonging the true graph are black false edges added by reconstruction algorithm are red. host interactive reconstructed maps from transformers at the following links: shortest paths, noisy shortest paths, and random walks.
distinguishes separate states at a high rate fails recognize that two prefixes that lead to the same state should have the same valid continuations.
3.3 Reconstructing implicit maps
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 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 origin and destination that do not necessarily correspond to fixed graph over the intersections Manhattan. To narrow the scope, our goal is to produce 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 map consistent with the true model whenever run on valid sequences. Further, (a) we enforce each node at most one outgoing edge of any direction, (b) we limit the maximum degree of cach 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 truc map until forced to do otherwise in order to map 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 distribution of origin/destination pairs follows the sampling distribution used to train each model). On the left is the reconstructed map 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 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 model that has the right world model but makes few tran- scription 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 sequence consistent with world model. The middle panel of Figure 3 shows reconstructed graph. 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.

---

Probability of detour
0%
1%
10%
50%
75%
Shortest paths
0.99 (0.01)
0.69 (0.05)
0.08 (0.03)
0.00 (0.00)
0.00 (0.00)
Random detours
Noisy shortest paths
0.96 (0.02)
0.52 (0.05)
0.03 (0.02)
0.00 (0.00)
0.00 (0.00)
Random walks
0.99 (0.01)
0.99 (0.01)
1.00 (0.00)
0.97 (0.02)
0.74 (0.04)
True world model
1.00
1.00
1.00
1.00
1.00
Shortest paths
0.99 (0,01)
0,66 (0.05)
0.06 (0.02)
0.00 (0.00)
0.00 (0.00)
Adversarial detours
Noisy shortest paths
0.96 (0.02)
0.64 (0.05)
0.04 (0.02)
(0.00)
0.00 (0.00)
Random walks
0.99 (0.01)
1.00 (0.00)
1.00 (0.00)
0.93 (0.03)
0.51 (0.05)
True world model
1.00
1.00
1.00
1.00
1.00
Table 2: The fraction of traversals that are valid when detours are introduced
(standarr (standard errors in parentheses).
3.4 Implication of failing to recover the world model: detour fragility
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 slightly adjacent task and consider 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 traversal. But with probability p 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 our proposed evaluation metrics. The similarity between model performance on these evaluation metrics and detour robustness illustrates the effectiveness of our proposed metries for assessing world model recovery.
4 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 logie puzzles. In both cases, framework finds the same type of incoherence that we found in the previous section for maps.
Othello. Li et al. [20] study the question of evaluating world models in the context of Othello, 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 Section 2.4. Since the truc Othello game can be rep- resented as DFA, we 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 [20]: one trained on real games from Othello championship tournaments and another trained on synthetic games. Table 3 in Appendix 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 in Appendix D; while the model trained on synthetic data produces near-perfect games regardless of detours, the model trained on championship data fails immediately. Similar to the navigation setting, we again find that models trained on random/synthetic data recover structure than those trained 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. [35]. There are n seats and individuals. The vocabulary consists of statements like "Person 'A' is sitting in seat 1" and "Person 'B' is two seats away from

---

Capabilities
Proposed metries
Task accuracy
Compression
Distinction
Example task prompt
precision
recall
There individuals named B,
Llama-2 (70B)
0.77 (0.03)
0.08 (0.03)
0.42 (0.04)
C, and there are seats, positioned 1-3.
Llama-3 (8B)
0.85 (0.02)
0.18 (0.04)
0.23 (0.03)
We have the following statements:
Llama-3 (70B)
0.98 (0.00)
0.25 (0.04)
0.57 (0.04)
1. B is seat 3
2. B is 1 seat away from A
Mixtral-8x22B
0.88 (0.01)
0.35 (0.05)
0.57 (0.05)
Based this information, where C seated? You can use chainn-f-thought reasoning.
Qwen 1.5 (72B)
0.88 (0.02)
0.21 (0.04)
0.56 (0.03)
Qwen 1.5 (110B)
0.98 (0.00)
0.53 (0.05)
0.53 (0.04)
GPT-3.5 (turbo)
0.83 (0.02)
0.33 (0.05)
0.18 (0.03)
GPT-4
1.00 (0.00)
0.21 (0.04)
0.56 (0.03)
True world model
1.00
1.00
1.00
Figure 4:
On the left, an example given to large language models to assess task capabilities. On the right, each model's is average task performance along with their results on our proposed metrics. Models are very capable of solving logic puzzles despite not having coherent world model.
Person 'C". A state is the set of seating arrangements that are consistent with all of the statements so far, and statement is valid if doesn't 't contradict all arrangements the given state.
We analyze Llama 2 (70B) [37], Llama-3 (8B and 70B), Mixtral (8x22B Instruct) [15], Qwen 1.5 Chat (72B and 1 100B) [2]. 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 this task; GPT-4 is accurate 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 s Myhill-Nerode boundary). See Appendix E for further discussion.
Figure shows the results averaged over 100 samples. While most LLMs can solve the logic puzzle when it's fully specified, they perform poorly 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 when the seating arrangement is fully specified) without having a coherent world model.
5 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 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 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 prohlematic when we hope to use a generative model to learn something latent about the world scientific domains.
Our primary limitation is the focus on DFAs. While is suitable for many applications like games, logic, and state tracking, extending would be quite valuable, e.g. situations where the underlying world model is more complicated than a DFA or unknown. We suspect that the core ideas related to sequence compression and sequence distinction generalize these richer settings, but leave that to future work.
Acknowledgements
Keyon Vafa is supported by the Harvard Data Science Initiative. Justin Chen is supported by an NSF Graduate Research Fellowship under Grant No. 174530. Jon Kleinberg is supported in part by Vannevar Bush Faculty Fellowship, a Simons Collaboration grant, and a grant from the MacArthur Foundation. We thank the Chicago Booth School of Business for generous support. We thank
10

---

Foundry' for providing the compute required to conduct this research. We also thank Sarah Bentley, Juan Carlos Perdomo, and Neekon Vafa for helpful comments and feedback.
References
[1] Abdou, M., Kulmizev, A., Hershcovich, D., Frank, S., Pavlick, E., and Søgaard, A. Can language models encode perceptual structure without grounding? A case study in color. arXiv preprint arXin:2109006/29 2699 2021.
[2] Bai, J., Bai, S., Chu, Y., Cui, Z., Dang, K., Deng, X.,, Fan, Y. Ge, W., Han, Y., Huang, F,, et al. Qwen technical report. arXiv preprint arXiv:2309, 16609, 2023.
[3] Benegas, G., Batra, S. S., and Song, Y. S. DNA language models are powerful predictors of genome-wide variant effects. Proceedings of the National Academy of Sciences, 120(44): e231 2023.
[4] Bhattamishra, S., Ahuja, K., and Goyal, N. On the ability and limitations of transformers to recognize formal languages. arXiv preprint arXiv:2009. / /264, 2020.
[5] Bocing, G. Modeling and analyzing urban networks and amenities with OSMMx. 2024.
[6]
Boiko, D. A., MacKnight, R., Kline, B., and Gomes, G. Autonomous chemical research with large language models. Nature, 624(7992):570-577 2023.
[7] Chowdhury, R., Bouatta, N., Biswas, S., Floristean, C., Kharkar, A., Roy, K., Rochereau, C., Ahdritz, G., Zhang, J., Church, G. M., Sorger, P. K., and AlQuraishi, M. Single-sequence protein structure prediction using a language model and deep learning. Nature Biotechnology. 40(11): 1617-1623, 2022.
[8] Fan, A., Lewis, M., and Dauphin, Y. Hierarchical neural story generation. arXiv preprint 18050088 2018.
[9] Guan, L., Valmeekam, K., Sreedharan, S., and Kambhampati, S. Leveraging pre-trained large language models construct and utilize world models for model-based task planning. Advances in Neural Information Processing Systems, 36:79081-79094, 2023.
[10] Hazineh, D. S., Zhang. Z.,, and Chiu, J. Linear latent world models in simple transformers: A case study on Othello-GPT arXiv preprint arXiv:2330.00758, 2023.
[11] Hewitt, J. and Liang, P. Designing and interpreting probes with control tasks. arXiv preprint 1rXiv:/909.000 03368, 2019.
[12] Hewitt, J., Manning, C. D., and Liang, P. Truncation sampling as language model desmoothing. arXiv preprint arXiv:2210. 151911 2022.
[13] Holtzman, A., Buys, J., Du, L., Forbes, M., and Choi, Y. The curious case of neural text degeneration. arXiv preprint 1r04.v:904.099 2019.
[14] Jablonka, K. M., Schwaller, P., Ortega-Guerrero A., and Smit, B. Leveraging large language models for predictive chemistry. Nature Machine Intelligence, pp. 1-9, 2024.
[15] Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, D. d. I., Bressand, F. Lengyel, G., Lample, G., Saulnier, L., et al. Mistral 7b. arXiv preprint 23X.v:2310.0682, 2023.
[16] Jin, C. and Rinard, M. Evidence of meaning in language models trained on programs. arXiv preprint 230.. 2023.
[17] Kıcıman, E., Ness, R., Sharma, A., and Tan, C. Causal reasoning and large language models: Opening a new frontier for causality. arXiv preprint arXiv:2305.00051 2023.
[18) Kuo, M.-T,, Hsueh, C.-C., and Tsai, R. T.-H. Large language models on the chessboard: A study on ChatGPT's formal language comprehension and complex reasoning skills. arXiv preprint arXiv:2308.1111 15118, 2023.
[19] Li, B. 7., Nye, M., and Andreas, J. Implicit representations of meaning in neural language models, arXiv preprint arXiv:2 007377 2021.
phttpss///wee ml fommdry.comm/

---

[20] Li, K., Hopkins, A. K. Bau, D., Viégas, F., Pfister, H., and Wattenberg, M. Emergent world representations: Exploring a sequence model trained on synthetic task. In International Conference on Learning Representations, 2023.
[21] Lin, Z., Akin, H., Rao, R., Hie, B., Zhu, Z., Lu, W., Smetanin, N., Verkuil, R., Kabeli, O., Shmueli, Y., dos Santos Costa, A., Fazel-Zarandi, M., Sercu, T., Candido, S., and Rives, A. Evolutionary-scale prediction of atomic-level protein structure with language model. Science, 11966637)1113311333 2023.
[22] Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. arXiv preprint arXiv:22100 10. 10749, 2022.
[23] Merrill, and Sabharwal, A. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023.
[24] Merrill, W., Petty, J., and Sabharwal, A. The illusion of state in state-space models. arXiv preprint arXiv:2404. 08889, 2024.
[25] Murray, K. W. 2014 New York City taxi trips. https://www, kaggle. com/datasets/ kentonnlp/2011 ---t----ooo---tt--ttaaaa texistrris, 2017. Accessed: 2024-10-24.
[26] Myhill, J. Finite automata and the representation of events. WADD Technical Report, 57: 112-137, 1957.
[27] Nerode, A. Linear automaton transformations. Proceedings of the American Mathematical Society, 9(4::541-544, 1958.
[28] Patel, R. and Pavlick, E. Mapping language models to grounded conceptual spaces. In International Conference on Learning Representations, 2021.
[29] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenA/ blog, 1(8):9, 2019.
[30] Schumann, R. and Riezler, S. Generating landmark navigation instructions from maps graph-to-text problem. Association for Computational Linguistics, 2021.
[31] Schumann, R. and Riezler, S. Analyzing generalization of vision and language navigation unseen outdoor areas. Association for Computational Linguistics, 2022.
[32] Schumann, R., Zhu, W., Feng, W., Fu, T.-.., Riezler, S., and Wang, VELMA: Verbalization embodiment of L.IM agents for vision and language navigation in street view. In AAAI Conference on Artificial Intelligence, 2024.
[33] Sipser, M. Introduction the Theory of Computation, Third Edition. Cengage Learning, 2013.
[34] Suzgun, M., Belinkov, Y., and Shieber, S. M. On evaluating the generalization of LSTM models in formal languages. arXiv preprint arXiv: 1.01001, 2018.
[35] Suzgun, M., Scales, N., Schärli, N., Gehrmann, S., Tay, Y., Chung, H. W., Chowdhery, A., Le,
Q. V., Chi. E. H., Zhou, D.. et al. Challenging BIG-bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.09261 2022.
[36] Toshniwal, S., Wiseman, S., Livescu, K., and Gimpel, K. Chess as a testbed for language model state tracking. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 11385-11393, 2022.
[37] Touvron, H., Martin, I.,, Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307. 09288, 2023.
[38] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention all you need. In Neural Information Processing Systems, 2017.
[39] Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., Chi, E. H., Hashimoto, T., Vinyals, O., Liang, P., Dean, J., and Fedus, W.
Emergent abilities of large language models. arXiv preprint arXiv:2206 222.22222272222.. 2022.
[40] Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., al. -hain-of-thought prompting elicits reasoning in large language models. Neural Information Processing Systems, 35:24824-24837, 2022.
12

---

Training sequences
Model generates:
820 210 NEEE SE W W SE N and
450 E EEENEEEE
Contasts
110 244
850 820
301
Figure Examples of and traversals. On left are examples sequences seen during training and contexts used for evaluation. On the right is an example traversal generated by transformer trained on shortest paths data
A Proof
Proof of Proposition 2.3. We will first prove the forward direction that if generative model m(-) recovers the world model DFA W, then m(.) satisfies exact next-token prediction. By assumption. L (q) (s) Consider any state q F and sequence reaching that state S(q). This implies that for any sequence sa for any character a E Σ,
ö(g.4) a) # Qreject
m(a (s) O.
which is the definition of next-token prediction.
Now, we will prove the backwards direction that mi(-) achieves exact next-token prediction, recovers W. Fix any state and sequence E S(g). Consider any sequence aja2._ag E" and let q' = 8(q. aia)..ag) ) be the state reached by following the sequence from q. Note that by definition of Project not having any outgoing transitions,
d' * Qreject -
(Vj <) : òlg. a102..a))) # qreject-
By assumption,
m(ax a1d2.
= q Greject.
aiaz...a L (q),, then q' Qreject- It then must be the case that m(a,laıaz.aaj-)) > 0 for all j < k, implying that a1a2...4g (s)()).
Conversely, if aiaz...uk I. W.W (q), then q' Qreject- It follows that m(ax(1)a2..4)))) 0, and thus aja2...ax (s).
B Reconstructed Maps
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.
B.1 Algorithm
Our reconstruction algorithm in Algorithm I takes 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 the true world model (i.c. the intersections of Manhattan), and we visualize each intersection by placing them at their real-world latitude/longitude. The reconstruction algorithm thus attempts 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. produces a sequence which is only valid by adding an additional edge to the true map. In this case, our reconstruction algorithm adds new edge 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
13

---

Shortest paths
Noisy shortest paths
Random walks
Compression (Precision)
Distinction (Precision)
Distinction (Recall)
1.00
0.75
0.8
Score
0.50
0.6
0.25
0.4
0.4
0.00
50
100
4
4
Boundary Size
Boundary Size
Boundary Size
Figure 6: Performance metrics as function of the maximum suffix length used to approximate the Nehiol-Nerode boundary.
0.30
Compression precision
0.25
0.20
0.15
0.10
2
Number two way-intersections
Figure Compression precision worsens as there are more two-way streets at current intersection. Plotted results are the shortest paths model.
that would be valid. In other words, the algorithm adds edges only when there is 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 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 single edge with given direction coming out of any intersection, maximum degree, and maximum edge distance will not be able to reconstruct every of sequences. For example, sequences [VI, V2, E, end] and [vi, v3, E, end] cannot be reconstructed without violating the first constraint.
B.2 Maps
We include reconstructed maps built from 6400 transformer -ennerrrte-ee 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 sss traversal for each pair. Because the transformer never sees sequences of length more than 100 during training, we only sample pairs for which there cxists 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 (the true map has maximum degree 4 and there are 8 possible cardinal directions), and the maximum edge distance between 1/2 and 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 is north of intersection in
14

---

Algorithm Graph Reconstruction from Sequences
Input: A of sequences { 1-1 each consisting of source, destination, cardinal directions, and end
token; a true graph described by vertices R² and edges D VxV {o, S, E, W, NE, NW, SE, SW); maximum degree deg: and maximum distance dist.
Output: Reconstructed edges D.
Initialize D(u, v) 2: for i E [n] do
for all v,
3: j is an index into the list of directions
4: и s;[0] is the current node, starting at the source
5: while s:Li] # end do
6:
if Av E V s.t. D(u, ) = s; s;li] then
7:
Kv E V: D(u, v) # OH 2 deg then FAIL to reconstruct sequence and continue to line 2 else 3v s.t. D(u, v) N; [i] then
8:
I/ No room for new edges
9:
10:
D(u, v) [i]]
I/ Add edge from the real graph
11:
else
12:
N(u) - (v V within Euclidean distance dist)
13:
V' - arg max ((c) (n) reaching lines or 13
of steps through the while loop Du, v) = s:Li] before
14:
Du, - s:li]
Add new edge that gives longest continuation
15:
j+j+1 if u # st[1] then
16:
FAIL construct sequence
18: return
the true map but the reconstruction algorithm recovers edge from V2 vi labeled "South", we draw an edge that leaves v2 facing south and loops back to v1. In the zoomed-in images, edges belonging to the true map are in black and false edges added by the reconstruction algorithm in red.
In each caption, we list the number of sequences the algorithm failed to reconstruct. In addition the reconstructed map from all of the transformer's sequences, 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 25% for shortest paths, 35% for noisy shortest paths, and 20% for random walks. These percentages correspond to the fraction of the transformer's 's sequences that are invalid, so the (b) and (c) subfigures each plot have the same proportion 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 182, for noisy shortest paths is 1,044,87 and for random walks 1,584,549.
C Deterministic Finite Automata and Myhill-Nerode
Recall that we use a standard parameterization of a DFA as W = (Q. 40. F) (see (33]) with
1. @ a finite set of states,
2. Σ is finite set of characters,
@ is the transition function mapping a state and character to the next state, 4. E Q is the start state,
3. 8 0
5. F s Q is the set of accepting states.
In the rest this section, we state the Mehill-Nerode theorem, which is the conceptual basis for our world-model test.
15

---

Compression precision
Distinction precision
Distinction recall
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 models trained on real-world tournament games and synthetic games, respectively.
Definition C.1 (Equivalent sequences). Two sequences $1, E E" are called equivalent under a language L if for all suffixes E Σ", 81x E L = 52x L. This equivalence relation be used to partition all strings into equivalence classes.
Theorem C.2 (126, 27J). language L is regular if and only if has a finite number of equivalence classes. Then, the minimal DFA accepting L. has a number of states equal to the number of classes. In the minimal DFA. for every pair of distinct states qı * q2. there exists a suffix x such that exactly one of x(q1,x) or 8(q2,x) is in the set of accepting states F.
D Additional results
Figure 5 shows an example sequences and traversals in our dataset. Each training sequences consists of an origin node, destination node, and set of directions followed by 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 metries vary as we consider different suffix lengths for approximating the Myhill-Nerodd boundary. For compression precision, considering a boundary of size & corresponds to sampling suffixes of length-k for each suffix and measuring whether prefixes with the same state have the same length-k suffixes. For distinction precision, we consider a boundary of size by only sampling k-length suffixes approximate a model's Myhill-Nerode boundary. For distinction recall, we consider a boundary of size k by only constructing the true Myhill-Nerode boundary based on k-length suffixes. The results in Figure show the importance of considering larger boundaries opposed smaller ones (e.g. single next-tokens); for example, while the model trained on random walks scores 100% on compression precision when boundaries 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 s ability to recognize that two sequences that lead to the same intersection are indeed in the same state worsens. Figure 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. [20]. 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. Table we perform detour exercise analogous the one performed for taxi rides in Section 3, where here a model's 's predicted move is replaced with another legal one. The detour results support the discernment between models found by our metries; while the model trained on synthetic data produces near-pent hear-perfect games regardless of detours, the model trained on championship data fails immediately.
E Evaluation metric details and ablations
Here we provide implementation details and ablations for the test described in Section 2.4 and implemented Section We discuss how it's implemented each of the three settings - maps, Othello, and logic puzzles and then show ablations with different settings.
16

---

Probability of detour
0%
1%
10%
25%
50%
Random detours
Championship Othello
1.00 (0.00)
0.66 (0.05)
0.05 (0.02)
0.01 (0.01)
0.01 (0.01)
Synthetic Othello True world model
1.00 (0.00)
0.99 (0.01)
0.97 (0.02)
0.97 (0.02)
0.99 (0.01)
1.00
1.00
1.00
1.00
1.00
Adversarial
Championship Othello
1.00 (0.00)
0.70 (0.05)
0.01 (0.01)
0.01 (0.01)
0.00 (0.00)
detours
Synthetic Othello
1.00 (0.00)
0.98 (0.01)
0.99 (0.01)
0.96 (0.02)
0.97 (0.02)
True world model
1.00
1.00
1.00
1.00
1.00
Table 4: The fraction of traversals that valid when detours introduced in Othello. For "random detours".
a model's proposed token is replaced with a randomly chosen (true) valid token; for "adversarial detours", it replaced with the model's lowest ranked valid token.
E.1 Implementation details
Maps. For the compression test, we sample a state at random from all possible states, where each state is (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 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, 5 and 52.
Because the true world's ' Myhill-Nerode boundary is empty for the compression test, 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 compute the full boundary; the precision is O any time there's ' one sequence accepted by one prefix and not the other. So we approximate precision by Monte-Carlo sampling. We sample M complete sequences from the model conditioned s1, insuring that each token has higher than e probability. We then check if each token in the sequence has higher than e probability when the model conditioned on s2. 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-bount on performance. In practice, we use M 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, Qı and q2, uniformly at random, and sample sequences that lead to each state, S and $2, as before. As before, computing full Mehill-Nerode boundaries is intractable, Nerode boundary, we consider all continuations of length k, and find the set of minimal suffixes that accepted after q1 but not 42- To which elements in the true boundary are distinguished by the model, we evaluate the model on each element in conditioned on S vs $2. We use k = 5, and find that results are robust across different k 2 5. We again approximate the transformer's 's Mehill-eerode boundary by taking M = 30 Monte-Carlo samples. For each sequence that's 's accepted after s but not s2, we find the minimal distinguishing suffix and include in the boundary set. We then assess precision by calculating which elements in the model's boundary are acceptable after qı but not 42-
we approximate them. To approximate the true world model's Myhill-
For both tests, get state-level scores by averaging the results over prefixes that lead 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, 3j and s2, that lead to the same board, 9. Like the above, we don't It need to compute the model's full Nerool boundary since the precision is O any time one sequence is accepted by si and not $2. Therefore, we again approximate precision with M 30 Monte-Carlo samples, following the same method performed for maps.
For the distinction test, we sample two distinct states 9i and 42 from the set of sampled games with the same length. We sample prefixes 5 and s2 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 M Monte-Carlo samples of complete game trajectories. We perform the analogous sampling
17

---

Context
Context
There are individuals named and and there are seats, positioned 1-3, We have the following statements:
There 3 individuals named A, B, and C, and there are seats, positioned 1-3. We have the following statements: 1. C is away from A
1. B is 1 away from C
2. A away from
Query
Is the fallowing statement possible in this scenario?
"C is away from B"
Response for Context
Response for Context 2
Yes
Figure 8: example of a compression error for GPT-4 the logic puzzle The model is prompted with statements that correspond to the same underlying state and a sample continuation. assesses that the continuation is valid for one state yet invalid for the other.
technique for the true world model, sampling M complete gameplay trajectories at random over the set of valid continuations. We use M 30 for both sampling procedures and threshold of e 0.01.
Logic puzzles. Performing our test on large language models presents a challenge that we do not have token-level probability access. Moreover, because allow large language models to perform chain-of- th-thuugh reasoning, it's computationally intractable to sample long continuations by marginalizing over the possible -hain-of-thoughts.
Our test design is therefore based on prompting. See Figure for an example. For the compression metric, sample up to 2 statements uniformly at random from the set of possible statements to arrive at a state q. We then sample two prefixes $1 and 32 that lead to q by repeatedly sampling the set of statements consistent with 9 that don't fon't narrow down the state space until the state implied by the statements is exactly that of q. The compression metric failed for each state for which we can find 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 the nature of the compression metric,
reported metric 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, again sample states 91 # q2 and sample sequences that lead to the states $j and 82 using the same method as before. Because the limited state space in our example, we can compute the true Myhill-Nerods boundary tractably. To test recall, then only need to assess whether statements in the true boundary are accepted when the LLM is prompted by $s 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 M statements from the true boundary prompt the model. We consider M 5 in our experiments.
We use the OpenAl API to query the GPT models, and use the Together API for all other LLMss. We prompt LLMS to perform chain-of-thouu answers by prompting each model to output its response with the keyword "Answer:" followed by its answer. All queries are performed with greedy decoding.
reasoning [40] for each query and automatically evaluate
E.2 Ablations
Our test involves few parameters, such (the probability threshold for each model), the maximum suffix length & used to approximate the true Myhill-Nerode boundary, and the number Monte Carlo samples used to approximate the model's Myhill-Nerode boundary.
We begin by considering e, which dictates tradeoff between precision and recall. In the main text, we consider = 0.01. Table 5 reports results for other values of on the maps metrics. Empirically
18

---

Compression precision
Distinction precision
Distinction recall
Shortest paths
0.08 (0.03)
0.30 (0.05)
0.16 (0.03)
== 0.10
Noisy shortest paths
0.04 (0.02)
0.36 (0.05)
0.20 (0.03)
Random walks
0.16 (0.04)
1.00 (0.00)
1.00 (0.00)
Shortest paths
0.10 (0.03)
0.38 (0.05)
0.18 (0.03)
10-2
Noisy shortest paths
0.08 (0.03)
0.38 (0.05)
0.26 (0.03)
Random walks
0.46 (0.06)
1.00 (0.00)
1.00 (0.00)
Shortest paths
0.36 (0.05)
0.29 (0.05)
0.29 (0.04)
<= 10-4
Noisy shortest paths
0.29 (0.05)
0.35 (0.05)
0.34 (0.04)
Random walks
0.79 (0.05)
1.00 (0.00)
0.97 (0.02)
Shortest paths
0.70 (0.05)
0.29 (0.05)
0.29 (0.04)
<= 10-6
Noisy shortest paths
0.70 (0.05)
0.48 (0.05)
0.23 (0.04)
Random walks
0.99 (0.01)
0.99 (0.01)
0.11 (0.03)
Table 5: Compression and distinction test results for different values of for models trained on map data.
Compression precision
Distinction precision
Distinction recall
Shortest paths
0.14 (0.04)
0.33 (0.05)
0.17 (0.03)
k=1
Noisy shortest paths
0.06 (0.04)
0.35 (0.07)
0.11 (0.03)
Random walks
0.40 (0.08)
0.69 (0.06)
0.30 (0.04)
Shortest paths
0.21 (0.05)
0.32 (0.05)
0.17 (0.03)
k 2
Noisy shortest paths
0.07 (0.04)
0.31 (0.07)
0.23 (0.05)
Random walks
0.21 (0.07)
0.93 (0.03)
0.73 (0.05)
Shortest paths Noisy shortest paths
0.49 (0.06)
0.41 (0.05)
0.30 (0.03)
==
0.44 (0.08)
0.22 (0.06)
0.33 (0.06)
Random walks
0.64 (0.08)
0.98 (0.02)
0.51 (0.06)
Table 6: Compression and distinction metrics for maps data where token acceptance is based on the top-k decoding mechanism. We consider values from & 1 & 4 because there are only 8 valid cardinal directions.
we see the tradeoff between precision and recall as changes. However, the conclusions are stable: every model has incoherent world model across values of For example, while the random walks model has high compression and distinction precision for e = 10-6, it has a very low distinction recall, of 0.111. Meanwhile, while the distinction recall is bumped up 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 sequence. In the main text we consider acceptance based on a threshold parameter, which corresponds to an e-sampling decoding mechanism [12]. Here, we consider two alternative forms of acceptance based on other decoding strategies: top-k [8] and top-p [13]. For acceptance based on top-k, a token is accepted if it's in the model's 's top-k ranked tokens for a sequence and rejected otherwise. For top-p, a token is accepted if it's part the the smallest set of highess-probability tokens whose cumulative probability is larger than p. Results are depicted in Table 6 and Table 7 and point to the same conclusion as the threshold-ban 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 '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. Table 8 shows how the precision scores vary as function of the number samples for the shortest paths model. We use M 30 Monte Carlo samples for our main reported metrics.
19

---

Compression precision
Distinction precision
Distinction recall
Shortest paths
0.05 (0.02)
0.33 (0.05)
0.17 (0.03)
p = 0.90
Noisy shortest paths
0.08 (0.04)
0.34 (0.07)
0.20 (0.05)
Random walks
0.16 (0.06)
0.96 (0.04)
0.94 (0.03)
Shortest paths
0.22 (0.05)
0.39 (0.05)
0.21 (0.03)
0.99
Noisy shortest paths
0.03 (0.03)
0.39 (0.07)
0.24 (0.05)
Random walks
0.54 (0.08)
1.00 (0.00)
1.00 (0.00)
Shortest paths
0.31 (0.05)
0.35 (0.05)
0.22 (0.04)
p = 0.999
Noisy shortest paths
0.15 (0.06)
0.46 (0.07)
0.31 (0.05)
Random walks
0.73 (0.07)
1.00 (0.00)
1.00 (0.00)
Table Compression and distinction metries for maps data where token acceptance is based on the top-p
decoding mechanism.
Number of samples
Compression precision
Distinction precision
10
0.14 (0.04)
0.35 (0.05)
20
0.12 (0.04)
0.35 (0.05)
30
0.10 (0.03)
0.30 (0.04)
Table 8: Precision performance function of the number of Monte Carlo samples used approximate
model's Myhill-Nerode boundary. Results are for the shortest paths map model.
F Rides data construction and training
Here we describe the rides dataset construction in more detail. Our empirical studies are based on 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 [25]. We drop duplicate rides and subset the dataset only include rides in Manhattan, resulting in 3,358,737 sequences. We use the OSMrx library [5] to represent New York as a weighted graph. We match pickups and dropoffs to the closest intersection, measured in terms of latitude/ latitude/longitude. The graph consists of 4,580 nodes, 9,846 edges, and each node has median of 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.
Shortest paths. The first approach creates traversals between 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 Dijkstra's '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 world model. Therefore, we construct noisy version of shortest-path traversals. We do this by modifying the weighting function, W(i. j) = (i. f) + éij- where 6ij Gamma (i, 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.313 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, 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 [29] 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
20

---

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 fixed number of epochs and use the last validation checkpoint; we use 5 epochs for the noisy shortest paths dataset and epoch for the random walks dataset. We train all models on A 100 GPUs, using a batch size of sequences per GPU. Training time ranges from about 12 hours for the shortest paths model to 48 hours for the random walks model.
G Additional maps
21

---

Edgenatel
Guttenberg
Manha
West New York
park Auyruu
New
Cueen
Oueens
Street
495
Maniaran
Mannattan Bridge
Figure 9: Reconstructed map from transformer trained shortest paths. In the zoomed-in images. edges belonging the true graph black and false edges added by the reconstruction algorithm red with a darkening gradient indicating the directionality the edge. Interactive map available http://mmaaaaataaaeeeentrrreeeee wwwrtiionssootttt...o betortss..eeelff..... netlify. app/.
22

---

Edgewarert
Guttenberg
Manna
West NowkYork
Payk Awerue
Centrol
Park
wedded Sart
Quer
ven
Oueens
495
Bruadway
Mamattan
Bridge
Figure 10: Reconstructed map from transformer trained on noisy shortest paths. Edges nodes their specified cardinal direction, Interactive map available at netlify. app/.
23

---

Edgovateh
Park
Guttenberg
West New New-York York
park Avemuu
Ouien
Mamantan
Mannattan
BBridge
Figure 11: Reconstructed map from transformer trained random walks. Interactive map available https: htt.://aaaaaatttmmrccoortrttiana www.or.ettooo....oommmomm
24

---

(a) Shortest paths
(b) Noisy shortest paths
(c) Random walks
Reconstructed maps from transformers trained shortest paths, noisy shortest paths, and random walks constructed using (origin, destination) pairs sampled from the same distribution used for training. While trajectories are valid more than 95% of the time, the errors reveal incoherence. Reconstruction uses 50k sequences with maximum degree 4 and maximum edge length 1/2 mile.
Figure 12:
(a) World model sequences
(b) Artificially corrupted model sequences
world
(c) Transformer sequences
Figure Reconstructed maps Manhattan from sequences produced by the generative model trained on shortest paths with maximum degree and the maximum edge length 1/2 mile. The reconstruction process failed on 1513/6400 sequences.
(a) World model sequences
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure 14: Reconstructed maps of Manhattan from sequences produced by the generative model trained on shortest paths with maximum degree and the maximum edge length 1/2 mile. The reconstruction process failed on 1435/6400 sequences.
25

---

(a) World model sequences
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure 15: Reconstructed maps of Manhattan from sequences produced by the generative model trained on shortest paths with maximum degree 4 and the maximum edge length mile. The reconstruction process failed on 1334/6400 sequences.
(a) World model sequences
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure Reconstructed maps Manhattan from sequences produced by the generative model trained on shortest paths with maximum degree and the maximum edge length mile. The reconstruction process failed on 1174/6400 sequences.
(a) World model sequences
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure 17: Reconstructed maps of Manhattan from sequences produced by the generative model trained on noisy shortest paths with maximum degree and the maximum edge length 1/2 mile. The reconstruction process failed 2213/6400 sequences.
26

---

(a) World model sequenees
(b) Artificially corrupted model sequences
world
(c) Transformer sequences
Figure 18: Reconstructed maps of Manhattan from sequences produced by the generative model trained on noisy shortest paths with maximum degree 8 and the maximum edge length 1/2 mile. The reconstruction process failed 1869/6400 sequences.
(a) World model sequences
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure Reconstructed maps Manhattan from sequences produced by the generative model trained on noisy shortest paths with maximum degree 4 and the maximum edge length mile. The reconstruction process failed on 1935/6400 sequences.
(a) World model sequences
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure 20: Reconstructed maps of Manhattan from sequences produced by the generative model trained on noisy shortest paths with maximum degree 8 and the maximum edge length mile. The reconstruction process failed 1702/6400 sequences.
27

---

(a) World model sequenees
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure 21; (Copy of Figure 3) Reconstructed maps of Manhattan from sequences produced by the generative model trained on random walks with maximum degree 4 and the maximum edge length 1/2 mile. The reconstruction process failed on 1987/6400 sequences.
(a) World model sequences
(b) Artificially corrupted model sequences
world
(c) Transformer sequences
Figure Reconstructed maps Manhattan from sequences produced by the generative model trained on random walks with maximum degree and the maximum edge length 1/2 mile. The reconstruction process failed on 1491 /6400 sequences.
(a) World model sequences
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure 23: Reconstructed maps of Manhattan from sequences produced by the generative model trained on random walks with maximum degree 4 and the maximum edge length mile. The reconstruction process failed on 1905/6400 sequences.
28

---

(a) World model sequences
(b) Artificially corrupted world model sequences
(c) Transformer sequences
Figure Reconstructed maps Manhattan from sequences produced by the generative model trained on random walks with maximum degree 8 and the maximum edge length mile. The reconstruction process failed on 1323/6400 sequences.
29

---

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

---

For our theoretical results, we state assumptions and provide proofs in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced 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 short proof sketch to provide intuition.
Inversely, any informal proof provided 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.
4. Experimental Result Reproducibility
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 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.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, 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 accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that 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. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
31

---

Question: Does the paper provide open access to the data and code. with sufficient instructions 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 NeurlPS code and data submission guidelines (https://nips cc/ public/ Bttee//udde//edeubbeeeeeee Stw.ooddeeuiiisssooooooooooo www.iissssooooiioooooo for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips
wwwpllllluiieeeeeeeeeoppoppbe gewgggd/oeeeeeeeeeeeeeeeee SondeSuubissiioPPP
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and details (e.g., data splits, hyper- parameters, 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, 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.
7. 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, 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.)
32

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Ye]]
Justification:
We describe the compute and GPU type the model is trained on.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / //nurrip.////p/p//.// cttpssccccppbb//p httppppsiicettccsuuiieeeeeeeeeee
Answer: [Yes]
Justification:
Our research conforms with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Our paper provides evaluation metrics, and we don't foresee societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
33

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 being used 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. 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, scraped datasets)?
Answer: [NA]
Justification:
The paper does not release any data or models that pose 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 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 dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papersw thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
34

---

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


Reviews:
[{"review_id": "c5QQ0TzYh8", "reviewer": "Reviewer_YkFb", "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.", "questions": "...", "limitations": "....", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The core idea of the work seems interesting; but unfortunately as a review I do not have the necessary background to fully or properly assess this work. \n\nThis work tries to address an important question for how current world models should be evaluated, and uses literature from automation theory to propose new metrics to see if the underlying logic of the domain can indeed be learnt by the world model. \n\nMy assessment of the work is rather high level with not enough technical background to assess the core contributions of this work; however, if this wiork is technically sound and can be made addressable with enough intuitions to general audience not familiar with automata theory, this work can indeed be quite significant and important to the community.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful and insightful review of our paper. We're glad that you think the paper is addressing an important question and that it has the potential to be \"quite significant and important to the community\". \n\n\n> _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 explained more generally, would perhaps be more useful._\n\nYou bring up a great point. We'll use the extra space available to us in the camera-ready revision to move the definition of DFAs from the appendix to the main text. We'll also provide the following high-level explainer:\n\nAt a high level, a DFA is a collection of states and a set of rules that govern how states are related to each other. For example, consider the game of Othello. This is a DFA where each state is essentially a different board position. The rules are similar to the rules of Othello; they tell you not only which moves are legal, but also how playing a particular move at a given board takes you to a new board. While we use Othello here as an illustrative example, DFAs are general: for example, navigation is a DFA (where the true state is which intersection you're at). They're common in other application areas, such as search engines, control systems, and genetics. \n\nDFAs are commonly used to study world models because they let us compare a model's predictions to the true rules [1, 2, 3, 4]. One popular method is the next-token test: given a sequence that corresponds to a true state, is the model's top-predicted next token valid under the rules of the DFA at that state? For example, given a sequence of Othello moves (encoded as tiles, e.g. \"34 12 30 23 26\"), is a transformer's prediction of the next tile a legal move? \n\nOur paper shows this next-token test can be misleading; models that are very far from having the true world model can perform very well at this test. A classic result -- the Myhill Nerode theorem -- provides intuition as to why: states aren't only defined by which individual next actions are legal, but rather by which (potentially long) sequences of actions are legal. For example, there are many Othello boards that have the same set of legal next moves, but the _sequences_ of legal moves differ when we consider longer sequences. As a result, testing whether the true world model has been recovered requires going beyond next-token tests.\n\nThis motivates two new properties a model must satisfy if it has recovered the true world model recovery:\n- **Sequence compression:** if two sequences lead to the same state, a model shouldn't distinguish them.  \n- **Sequence distinction:** if two sequences lead to distinct states, a model should distinguish them.  \n\nOur metrics directly measure these properties. Sequence compression is evaluated by sampling two sequence prefixes that lead to the same state and making sure a model's predicted continuations of those sequences are similar. For Othello, this corresponds to checking whether a model's outputs are similar for two move sequences that result in the same board. Our measure of sequence distinction is similar: it's evaluated by sampling two sequence prefixes that lead to different states and making sure that a model's predicted continuations reflect the differences in the continuations. In other words, this metric tests how well a model captures how different board positions are different.\n\nEmpirically, these metrics capture important aspects of world model recovery that other metrics do not. In the taxi example, prior metrics for assessing world models would lead us to conclude that transformers trained on taxi rides have world models. But our metrics come to a different conclusion: these models are far from recovering the true world model. We validate this by recovering the implicit map of NYC and showing it's nonsensical, along with showing that each model's navigation performance breaks down when detours are introduced. Our metrics also discern between two different types of Othello models: the model trained on Synthetic games has a world model, while the model trained on Championship games does not by our metrics. We validate this with a similar detours exercise (see the PDF for more details), where the Synthetic model produces near-perfect games regardless of detours and the Championship model fails immediately. There is a clear distinction between Championship and Synthetic models, but this is only captured by our metrics; existing metrics would lead us to conclude that both have world models. \n \nWe hope this is helpful. We've also included more motivation for including DFAs in our response to Reviewer S5LR. Please let us know if anything is unclear. If these comments have addressed your concerns, we hope you'd consider raising your score. \n\n[1] https://arxiv.org/abs/2106.00737  \n[2] https://arxiv.org/abs/2210.13382  \n[3] https://arxiv.org/abs/2102.13249  \n[4] https://arxiv.org/abs/2310.07582", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tIdidvg6bl", "reviewer": "Reviewer_7KXV", "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.", "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.\n\n- How much training was provided to the models?", "limitations": "I see no issues here.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a brilliant article. Given the influence of LLMs, the question of whether strong next-token prediction leads to neural networks with emergent, implicit world models is open and very important. In my view, this article is the most convincing evidence yet with regards to this question. I can see this article having major impact.\n\nParticular strengths include\n- Excellent writing and presentation\n- Choice of Taxi example\n- Extensions to Othello and Logic puzzle domains\n- Overwhelmingly clear results", "weaknesses": "I don't see real weaknesses. I have a couple minor suggestions for clarification:\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and insightful review of our paper. We appreciate your enthusiasm for the work and your remarks on the quality and significance of our paper. \n\n> _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._\n\nThis is a good point. We apologize for the confusion. The figure was intended to illustrate boundary errors, but you're right that examples to the side of the boundary are also errors. We've updated the figure and caption to make more clear that we're just showing boundary errors and we've also made a few stylistic updates as well (see the shared PDF response). \n\n> _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._\n\nThank you for the suggestion. We'll add these definitions in bold in the main text. \n\n> _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._\n\nThis is a good question. Your intuition for the distinction metric is right. An important point is that the distinction metric tests both whether the states are correctly distinguished and whether a model produces the correct difference in continuations. In other words, to perform well at the distinction test, a model needs to know the exact set of continuations that are legal in one state but not the other. One reason this could be hard is if the Myhill-Nerode boundary between states is large; then models need to correctly differentiate potentially long-range and complex continuations.\n\nIn the navigation setting, we found two kinds of interpretable distinction errors. One is that intersections that are geographically close to each other are confused for one another. Another is that intersections on streets with the same traffic patterns (e.g. the intersecting streets are one-way in the same directions) are also confused for each other. We found other kinds of distinction errors as well that were harder to interpret; an interesting research question is understanding why models fail to distinguish states that humans can distinguish easily. We'll add qualitative examples to our updated revision and we thank you for suggesting them -- they'll make the paper stronger. \n\n > _How much training was provided to the models?_\n\nTraining sizes:\n- Shortest paths: 2.9M sequences (120M tokens)  \n- Noisy shortest paths: 31M sequences (1.7B tokens)  \n- Random walks: 91M sequences (4.7B tokens)  \n\nWe trained models until the validation loss increased or stopped improving. This ranged from ~12 hours for the smallest models and datasets (shortest paths) and 48 hours for the largest models (random walks) on 8 A100 GPUs. We'll update the paper to make these training details more clear.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5mks29Rzpl", "reviewer": "Reviewer_RjHx", "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.\n\nThe 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$.\n\nExperiments 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.", "questions": "1. Did you try other acceptance criteria that go beyonds manipulation of threshold value, e.g. sequence-level probability/rank?", "limitations": "The author doesn't address the limitations discussed above in the paper.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This work proposes a new metric that measures the coherence of the implicit world model of neural LMs, which is novel perspective in this field.\n2. The paper is overall well-written and easy to follow.\n3. The authors conduct extensive evaluation on a wide range of base models (LLMs & Transformers) and three datasets, and the results are consistent.", "weaknesses": "1. The authors inaccurately summarize existing work and consequently address a non-existent flaw.\n\n>... 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)\n\nThis 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]). \n\n2. There are two fundamental flaws of the proposed metric\n     * 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.\n     * 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:\n       * A top-$k$ predicted sequence may include tokens with low likelihood.\n       * Conversely, a sequence satisfying the criteria might not appear in the top-$k$ predictions.\n       * 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.\n\n3. Lack of empirical evidence that proves the faithfulness of the proposed metric.\n     * 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. \n    * 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.\n\n[1] Li, Kenneth, et al. \"Emergent world representations: Exploring a sequence model trained on a synthetic task.\" ICLR 2022.\n\n[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.\n\n[3] Karvonen, Adam. \"Emergent world models and latent variable estimation in chess-playing language models.\" arXiv preprint arXiv:2403.15498 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Your review makes several helpful points that will improve our paper. However our rebuttal clarifies a couple of important points of your review: one involving an incorrect statement of what is in our paper (we do describe and empirically test probes), and another is a clarification of the value of having multiple metrics. We'll make these more clear in our revision. \n\n> _The authors inaccurately summarize existing work... Li et al. [1] do not solely rely on the validity of the top model predictions_\n\nYour review states that we ignore the probe test of Li et. al [1]. We agree probes are important and this paper would be incomplete without them. However, we not only describe the state probe in the Li et al. paper and the larger literature in the related work section (lines 74-78) but also perform probing experiments for our maps setting (Table 1 and lines 240-242). We agree that the sentence you point out could do more to foreshadow these results/discussion, so we'll update it in the revision and cite the two additional papers you mention. \n\n> _The conclusions drawn from the Othello experiments in this paper contradict those of Li et al._\n\nOur tests measure different outcomes than Li et al [1]. If a model's world model is perfect, all metrics will score 100%. Conversely, if any metric is less than 100%, it won't have a world model. This is similar to supervised learning: AUC, accuracy, F1, etc. are all the same for perfect classifiers. But having multiple metrics tells us _how_ an imperfect model is failing.\n\nWe 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. \n\nResults from [1] imply that both OthelloGPT models (\"Championship\" and \"Synthetic\") are close to having true world models. Our metrics reveal a more complex picture: while Synthetic recovers the true world model, Championship fails by our metrics. \n\nCrucially, we can validate this differentiation. We do this with an additional \"detour\" exercise: with probability p, we replace a model's top predicted move with another valid move and assess whether it completes the game validly. While the Synthetic model produces near-perfect games regardless of detours, the Championship model fails immediately. There is a clear distinction between Championship and Synthetic models, but this is only captured by our metrics; existing metrics would lead us to conclude that both have world models. \n\n**Random detours**\n|Model|0%|1%|10%|25%|50%| \n|-|-|-|-|-|-|\n|Championship|1.00|0.66|0.05|0.01|0.01|\n|Synthetic|1.00|0.99|0.97|0.97|0.99|\n\nSee the PDF for similar results on adversarial detours. \n\n> _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._\n\nOur metrics test a model's outputs while probes test a model's internal state. Both metrics are important because they measure different things: our metrics find inconsistencies not revealed by probes (see Tables 1, 2, 6, and the Othello detours above).\n\nFurther, the reliability of probes is far from settled. Ongoing debate [2] includes issues like proper baselines [3, 4], classifier complexity [5, 6], and faithfulness [7, 8]. Even for OthelloGPT, probes are sensitive to specification: linear and nonlinear probes have very different error rates [1], and different encodings reach different conclusions [9]. Moreover, should probe labels reflect each tile individually (as [1] considers) or the full board (all 64 tiles)? The championship Othello probe has 91% accuracy for each tile individually [1], but accuracy falls to 0.2% when the label is the full board. We think probes are valuable tools, but they don't yet provide conclusive results given these open questions. \n\n> _Neural LMs model distributions over tokens or sentences without a clear mechanism for determining sentence acceptance._\n\nWe agree that focusing on a single threshold alone provides an incomplete picture. This is why we include ablations across multiple thresholds (Table 3). All thresholds result in incorrect world models. \n\nCommon decoding strategies _do_ provide mechanisms for determining sequence acceptance, like top-k, top-p, and threshold-based sampling (i.e. epsilon sampling) [10, 11, 12]. While our paper focuses on epsilon sampling [12], different choices can easily be made within our framework. Below we include additional results for top-p and top-k sampling (more ablations in the PDF), which are very similar to the original results. The paper will be stronger thanks to your suggestion to add these.\n\n**Top-p (p=0.99)**\n|Model|Compression precision|Distinction precision|Distinction recall|\n|-|-|-|-|\n|Shortest paths|0.22|0.39|0.21|\n|Noisy shortest paths|0.03|0.39|0.24|\n|Random walks|0.54|1.00|1.00|\n\n**Top-k (k=2)**\n|Model|Compression precision|Distinction precision|Distinction recall|\n|-|-|-|-|\n|Shortest paths|0.21|0.32|0.17|\n|Noisy shortest paths|0.07|0.31|0.23|\n|Random walks|0.21|0.93|0.73|\n\nThanks again for your review. We think these edits will make the paper stronger. If we have addressed your comments, we hope you'd consider raising your score.\n\n[1] https://arxiv.org/abs/2210.13382  \n[2] https://arxiv.org/abs/2102.12452  \n[3] https://arxiv.org/abs/1805.01070  \n[4] https://arxiv.org/abs/2004.03061  \n[5] https://arxiv.org/abs/1610.01644  \n[6] https://arxiv.org/abs/2104.03514  \n[7] https://arxiv.org/abs/1812.08951  \n[8] https://arxiv.org/abs/2004.14975  \n[9] https://arxiv.org/abs/2309.00941  \n[10] https://arxiv.org/abs/1904.09751  \n[11] https://arxiv.org/abs/1805.04833  \n[12] https://arxiv.org/abs/2210.15191", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cVj9P19oLT", "reviewer": "Reviewer_S5LR", "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.\n\nTo 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.", "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": "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.\n\nMinor comments:\n\nLine 76: “our evaluation metrics are based sequences” —> “our evaluation metrics are based [on] sequences”", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This work is well-motivated and well-written. The proposed metrics are interesting, and the authors have supplemented the study with detailed ablation studies on the training data, which is commendable.", "weaknesses": "1. Generalizability of the proposed metrics\n\nThe 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.\n\nThis 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.\n\n2. Inter-metric consistency problem\n\nDespite 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?\n\nResolving 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful review. We're glad you found our proposed metrics interesting and ablation studies compelling. We appreciate your comments on the clarity of our paper.\n\n> _Inter-metric consistency problem... What is the correct conclusion when two out of three metrics suggest the presence of a world model, while the other does not?_\n\nYou raise a great question. If a model has the true world model, all metrics 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, some can be worse than others. This is similar to supervised learning: AUC, accuracy, F1, etc. are all the same when we have a perfect classifier. It's only when we have an imperfect model that these metrics reach different conclusions. This is why having multiple metrics is important: they tell you where a model is failing. \n\nFor example, Table 1 shows that while the random walks model is able to differentiate between states, this comes at the expense of failing to capture that the same state can be reached by different sequences. There is a tradeoff between metrics: it's easy to ace compression (by saying every sequence has the same continuations) but then distinction suffers. \n\n> _It appears that the three proposed metrics have low false negatives [and]... high false positives_\n\nThis fantastic comment helped us clarify the discernment properties of our proposed metrics. A model with the true world model will not fail when detours are introduced to sequences. In our original submission, we used detours to validate our metrics on the navigation exercise; detour performance correlated with our metrics (Table 2). We perform the same exercise below to validate our metrics' discernment of Othello models:\n\nExisting metrics imply that both OthelloGPT models from [1] (\"Championship\" and \"Synthetic\") are close to having the true world model. Our metrics reveal a more complex picture: while Synthetic recovers the true world model, Championship fails by our metrics. \n\nCrucially, we can validate this discernment with an additional \"detour\" exercise: with probability p, we replace a model's top predicted move with another valid move and assess whether it completes the game validly. While the Synthetic model produces near-perfect games regardless of detours, the Championship model fails immediately. A model that recovers the true world model will succeed regardless of detours. There is a clear distinction between Championship and Synthetic models, but this is only captured by our metrics; existing metrics would lead us to conclude that both have world models. \n\n**Random detours**\n|Model|0%|1%|10%|25%|50%| \n|-|-|-|-|-|-|\n|Championship|1.00 (0.00)|0.66 (0.05)|0.05 (0.02)|0.01 (0.01)|0.01 (0.01)|\n|Synthetic|1.00 (0.00)|0.99 (0.01)|0.97 (0.02)|0.97 (0.02)|0.99 (0.01)|\n\n**Adversarial detours**\n|Model|0%|1%|10%|25%|50%| \n|-|-|-|-|-|-|\n|Championship|1.00 (0.00)|0.70 (0.05)|0.01 (0.01)|0.01 (0.01)|0.00 (0.00)|\n|Synthetic|1.00 (0.00)|0.98 (0.01)|0.99 (0.01)|0.96 (0.02)|0.97 (0.02)|\n\n> _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_\n\nYou bring up an important point to clarify on logic puzzles. Constant-sized logic puzzles are canonical examples of DFAs [2]. Because each puzzle corresponds to a true state, we can assess the different ways state is reflected by a model; this is why [3] use logic puzzles to probe a model's representations for state, and it's why we can study token-level outcomes to assess whether a model's behavior is consistent with state. While it may seem like the model is performing badly on our test because we're translating logic into natural language that can confuse LLMs, the input space of possible sequences is relatively simple (21 possible statements). LLMs perform poorly on our metrics despite this simplicity. We agree that adding richer language would create more realism; still if a model performs poorly with the simple language, it's informative for their understanding of more complex problems. \n\nGenerally, we focus on DFAs because they're common in real-world phenomena: we focus on game-playing, logic, and navigation, and they also arise in search engines, control systems, and genetics [3]. Papers that study world model recovery have also focused on DFAs, even if they don't explicitly mention it [4, 5, 6]. DFAs are also important to study as testbed problems: What can we say about an LLM’s world model if it can’t recover a map?\n\nFinally, the requirements for our evaluation metrics fall in line with existing metrics in this literature: sampling from a model, seeing its predictions, and comparing them to the set of allowed predictions. These are the same requirements as the next-token test, and are similar to the probe test, which additionally requires access to a model's internal representations. \n\n> _What was the context length for your GPT model?_\n\nThe maximum navigation length during training was 100 tokens so we used a context length of 100. Across all tests, we were careful to only evaluate models using the context length they were trained on, e.g. when we sample sequences for navigating from A to B we made sure there was a valid route with at most 100 moves (see lines 299-300 and 508-510). We did the same thing for Othello (which was trained on up to 60 tokens since games have <=60 moves).\n\nThanks again for your review. If we've addressed your comments, we hope you'd consider raising your score.\n\n[1] https://arxiv.org/abs/2210.13382  \n[2] https://link.springer.com/chapter/10.1007/978-3-642-59126-6_7  \n[3] https://www.cs.ucdavis.edu/~rogaway/classes/120/spring13/eric-dfa.pdf  \n[4] https://arxiv.org/abs/2106.00737  \n[5] https://arxiv.org/abs/2210.13382  \n[6] https://arxiv.org/abs/2102.13249", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their careful evaluation and feedback. We're glad you found our paper "brilliant" (7KXV) and offering a "novel perspective" (RjHx), with the potential to be "quite significant and important to the community" (YkfB) and to have "major impact" (7KXV). Moreover we appreciated your comments on the strength of the empirical evidence (7KXV, RjHx, S5LR) and quality of the writing (7KXV, RjHX, S5LR). 

In response to the reviewers’ suggestions, we've included updated results in the attached PDF with:

- **Additional validation results:** Our original submission validated our metrics empirically using maps and detours for the navigation data. We now include a similar empirical validation for Othello. In our original submission, we showed that while existing metrics conclude that both Synthetic and Championship Othello models recover the true world models, our metrics find that only the Synthetic model recovers the true world. We include an additional "detour" exercise  (where a model's predicted move is replaced with another legal one) to validate this discernment for Othello. While the Synthetic model produces near-perfect games regardless of detours, the Championship model fails immediately. A model that recovers the true world model will succeed regardless of detours. There is a clear distinction between Championship and Synthetic models, but this is only captured by our metrics; existing metrics would lead us to conclude that both have world models. 

- **Additional acceptance criteria:** While our submission considered fixed probability thresholds to define transformer acceptance, an advantage of our framework is that it can be implemented with different acceptance criteria. In response to Reviewer RjHx's suggestion, we've also added results for top-p and top-k sampling (along with ablations of p and k). These come to the same conclusions as our original criterion, which, along with the ablations in Table 3 of our submission, show the robustness of our metrics to acceptance criteria. 

- **Updated figure:** In response to Reviewer 7KXV's suggestion, we've updated Figure 2 from our original submission to make the interpretation more clear. 

These results will make the paper stronger, and we thank you for suggesting them. We’ve also included more details about these results in our individual responses to each reviewer.

Meta-review: 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.
Decision: Accept (spotlight)