Evaluating the World Model Implicit in a Generative Model — part 4/5

Cleaned-text code points [46051, 61663). Bibliography omitted here; source.md includes it.

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 v 1 v_{1} is north of intersection v 2 v_{2} in the true map but the reconstruction algorithm recovers an edge from v 2 v_{2} to v 1 v_{1} labeled “South”, we draw an edge that leaves v 2 v_{2} facing south and loops back to v 1 v_{1} . In the zoomed-in images, edges belonging to the true map are in black and false edges added by the reconstruction algorithm are in red.

In each caption, we list the number of sequences the algorithm failed to reconstruct. In addition to the reconstructed map from all of the transformer’s sequences, we plot the reconstructed map built only on sequences which are valid under the true world model as well as a reconstruction of those valid sequences with some artificial corruptions. For the artificial corruptions, each sequence is chosen to be corrupted with a fixed probability of 25 % 25\% for shortest paths, 35 % 35\% for noisy shortest paths, and 20 % 20\% for random walks. These percentages correspond to the fraction of the transformer’s sequences that are invalid, so the (b) and (c) subfigures of each plot have the same proportion of valid and invalid sequences.

We note that the maps corresponding to the random walk model visually have more edges than, for instance, the maps built from shortest paths data. This is due to the fact that while the inputs to the reconstruction algorithm have the same number of sequences, the length of the sequences differ between the different generative models. The total number of directions contained in the shortest path sequences is 983 ​ t ​ r ​ u ​ e ​ 182 983true182 , for noisy shortest paths is 1 ​ t ​ r ​ u ​ e ​ 140 ​ t ​ r ​ u ​ e ​ 487 1true140true487 , and for random walks is 1 ​ t ​ r ​ u ​ e ​ 584 ​ t ​ r ​ u ​ e ​ 549 1true584true549 .

## Appendix C Deterministic Finite Automata and Myhill-Nerode

Recall that we use a standard parameterization of a DFA as W = ( Q , Σ , δ , q 0 , F ) W=(Q,\Sigma,\delta,q_{0},F) (see [ 33 ] ) with 1. Q Q is a finite set of states,

2. Σ \Sigma is a finite set of characters,

3. δ : Q × Σ → Q \delta:Q\times\Sigma\to Q is the transition function mapping a state and character to the next state,

4. q 0 ∈ Q q_{0}\in Q is the start state,

5. F ⊆ Q F\subseteq Q is the set of accepting states.

In the rest of this section, we state the Myhill-Nerode theorem, which is the conceptual basis for our world-model test.

###### Definition C.1 (Equivalent sequences) .

Two sequences s 1 , s 2 ∈ Σ ∗ s_{1},s_{2}\in\Sigma^{*} are called equivalent under a language L L if for all suffixes x ∈ Σ ∗ x\in\Sigma^{*} , s 1 ​ x ∈ L ⇔ s 2 ​ x ∈ L s_{1}x\in L\iff s_{2}x\in L . This equivalence relation can be used to partition all strings into equivalence classes.

###### Theorem C.2 ( [ 26 , 27 ] ) .

A language L L is regular if and only if it has a finite number of equivalence classes. Then, the minimal DFA accepting L L has a number of states equal to the number of classes. In the minimal DFA, for every pair of distinct states q 1 ≠ q 2 q_{1}\neq q_{2} , there exists a suffix x x such that exactly one of δ ^ ​ ( q 1 , x ) \hat{\delta}(q_{1},x) or δ ^ ​ ( q 2 , x ) \hat{\delta}(q_{2},x) is in the set of accepting states F F .

## Appendix D Additional results

Figure 5 shows an example of sequences and traversals in our dataset. Each training sequences consists of an origin node, a destination node, and a set of directions followed by an end node. To evaluate, we condition on (origin, destination) pairs that are unseen during training and generate a traversal from the model.

Figure 6 shows how our performance metrics vary as we consider different suffix lengths for approximating the Myhill-Nerode boundary. For compression precision, considering a boundary of size k k corresponds to sampling suffixes of length- k k for each suffix and measuring whether prefixes with the same state have the same length- k k suffixes. For distinction precision, we consider a boundary of size k k by only sampling k k -length suffixes to approximate a model’s Myhill-Nerode boundary. For distinction recall, we consider a boundary of size k k by only constructing the true Myhill-Nerode boundary based on k k -length suffixes. The results in Figure 6 show the importance of considering larger boundaries as opposed to smaller ones (e.g. single next-tokens); for example, while the model trained on random walks scores 100% on compression precision when boundaries of length-1 are considered, its performance is 50% when the full Myhill-Nerode boundary is considered.

We also performed some analysis to explore why the models uniformly performed badly on compression tests in the maps setting. We found a negative correlation between the number of two-way streets at an intersection and the compression precision; as the number of two-way streets at an intersection increases, the model’s ability to recognize that two sequences that lead to the same intersection are indeed in the same state worsens. Figure 7 plots this relationship for the shortest paths model.

Table 3 reports our metrics on models trained to play Othello. We use the transformer model checkpoints provided by Li et al. [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. In Table 4 , we perform a detour exercise analogous to the one performed for taxi rides in Section 3 , where here a model’s predicted move is replaced with another legal one. The detour results support the discernment between models found by our metrics; while the model trained on synthetic data produces near-perfect games regardless of detours, the model trained on championship data fails immediately.

## Appendix E Evaluation metric details and ablations

Here we provide implementation details and ablations for the test described in Section 2.4 and implemented in Section 3 . We discuss how it’s implemented in each of the three settings — maps, Othello, and logic puzzles — and then show ablations with different settings.

### E.1 Implementation details

Maps. For the compression test, we sample a state at random from all possible states, where each state is a (current intersection, destination intersection) tuple. We then sample two distinct sequences that lead to the same state. Because models are only trained on sequences of length 100 or less, we only sample sequences that are short enough to be possible to arrive at the destination in less than 100 moves. Among all possible sequences, we first sample a length l l uniformly at random, and then perform two random walks for l l steps in the reversed graph. This provides two distinct length- l l prefixes that lead to the same state, s 1 s_{1} and s 2 s_{2} .

Because the true world’s Myhill-Nerode boundary is empty for the compression test, we only need to compute the model’s boundary. However, computing the model’s boundary is intractable; it involves evaluating a transformer on exponentially many outputs. However, we don’t actually need to compute the full boundary; the precision is 0 any time there’s one sequence accepted by one prefix and not the other. So we approximate precision by Monte-Carlo sampling. We sample M M complete sequences from the model conditioned s 1 s_{1} , insuring that each token has higher than ϵ \epsilon probability. We then check if each token in the sequence has higher than ϵ \epsilon probability when the model is conditioned on s 2 s_{2} . If there exists a single violating sample, it means that the model has failed to compress the two prefixes. Therefore, sampling results in an upper-bound on performance. In practice, we use M = 30 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 1 q_{1} and q 2 q_{2} , uniformly at random, and sample sequences that lead to each state, s 1 s_{1} and s 2 s_{2} , as before. As before, computing full Myhill-Nerode boundaries is intractable, so we approximate them. To approximate the true world model’s Myhill-Nerode boundary, we consider all continuations of length k k , and find the set of minimal suffixes that are accepted after q 1 q_{1} but not q 2 q_{2} . To see which elements in the true boundary are distinguished by the model, we evaluate the model on each element in conditioned on s 1 s_{1} vs s 2 s_{2} . We use k = 5 k=5 , and find that results are robust across different k ≥ 5 k\geq 5 . We again approximate the transformer’s Myhill-Nerode boundary by taking M = 30 M=30 Monte-Carlo samples. For each sequence that’s accepted after s 1 s_{1} but not s 2 s_{2} , we find the minimal distinguishing suffix and include it in the boundary set. We then assess precision by calculating which elements in the model’s boundary are acceptable after q 1 q_{1} but not q 2 q_{2} .

For both tests, we get state-level scores by averaging the results over prefixes that lead to each state, and we report overall scores by averaging all sampled states.

Othello. The compression test for Othello involves sampling a board and then two sequences that lead to the board. We approximate this sampling by simulating 1000 random games and sampling a board at random from the set of unique boards that are visited by at least two unique games. This sampling provides us with two different sequences, s 1 s_{1} and s 2 s_{2} , that lead to the same board, q q . Like the above, we don’t need to compute the model’s full Myhill-Nerode boundary since the precision is 0 any time one sequence is accepted by s 1 s_{1} and not s 2 s_{2} . Therefore, we again approximate precision with M = 30 M=30 Monte-Carlo samples, following the same method as performed for maps.

For the distinction test, we sample two distinct states q 1 q_{1} and q 2 q_{2} from the set of sampled games with the same length. We sample prefixes s 1 s_{1} and s 2 s_{2} from the empirical distribution of observed games. We approximate the transformer’s Myhill-Nerode boundary in the same way as we did for maps, by taking M M Monte-Carlo samples of complete game trajectories. We perform the analogous sampling technique for the true world model, sampling M M complete gameplay trajectories at random over the set of valid continuations. We use M = 30 M=30 for both sampling procedures and a threshold of ϵ = 0.01 \epsilon=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 we allow large language models to perform chain-of-thought reasoning, it’s computationally intractable to sample long continuations by marginalizing over the possible chain-of-thoughts.

Our test design is therefore based on prompting. See Figure 8 for an example. For the compression metric, we sample up to 2 statements uniformly at random from the set of possible statements to arrive at a state q q . We then sample two prefixes s 1 s_{1} and s 2 s_{2} that lead to q q by repeatedly sampling the set of statements consistent with q q that don’t narrow down the state space until the state implied by the statements is exactly that of q q . The compression metric is failed for each state for which we can find a suffix that is accepted by the model prompted with one sequence but not the other. We sample 5 different possible continuation statements, half the time from the set of valid statements, half the time uniformly at random. We note that due to the nature of the compression metric, our reported metric is an overestimate of true capability. So the fact that no model performs above 0.35 0.35 with only 5 samples suggests heavy compression failure. We sample 100 states. See Figure 8 for an example of a compression error.

For the distinction metric, we again sample states q 1 ≠ q 2 q_{1}\neq q_{2} and sample sequences that lead to the states s 1 s_{1} and s 2 s_{2} using the same method as before. Because of the limited state space in our example, we can compute the true Myhill-Nerode boundary tractably. To test recall, we then only need to assess whether statements in the true boundary are accepted when the LLM is prompted by s 1 s_{1} or s 2 s_{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 M statements from the true boundary to prompt the model. We consider M = 5 M=5 in our experiments.

We use the OpenAI API to query the GPT models, and use the Together AI API for all other LLMs. We prompt LLMs to perform chain-of-thought reasoning [ 40 ] for each query and automatically evaluate answers by prompting each model to output its response with the keyword “Answer:” followed by its answer. All queries are performed with greedy decoding.

### E.2 Ablations

Our test involves a few parameters, such as ϵ \epsilon (the probability threshold for each model), the maximum suffix length k k used to approximate the true Myhill-Nerode boundary, and the number of Monte Carlo samples m m used to approximate the model’s Myhill-Nerode boundary.

We begin by considering ϵ \epsilon , which dictates a tradeoff between precision and recall. In the main text, we consider ϵ = 0.01 \epsilon=0.01 . Table 5 reports results for other values of ϵ \epsilon on the maps metrics. Empirically we see the tradeoff between precision and recall as ϵ \epsilon changes. However, the conclusions are stable: every model has an incoherent world model across values of ϵ \epsilon . For example, while the random walks model has high compression and distinction precision for ϵ = 10 − 6 \epsilon=10^{-6} , it has a very low distinction recall, of 0.11 0.11 . Meanwhile, while the distinction recall is bumped up to 1.00 1.00 for ϵ = 0.10 \epsilon=0.10 , its compression precision falls to 0.16 0.16 .

The metrics introduced in Section 2.4 depend on defining what it means for a model to accept or reject a sequence. In the main text we consider acceptance based on a threshold parameter, which corresponds to an ϵ \epsilon -sampling decoding mechanism [ 12 ] . Here, we consider two alternative forms of acceptance based on other decoding strategies: top- k k [ 8 ] and top- p p [ 13 ] . For acceptance based on top- k k , a token is accepted if it’s in the model’s top- k k ranked tokens for a sequence and rejected otherwise. For top- p p , a token is accepted if it’s part of the the smallest set of highest-probability tokens whose cumulative probability is larger than p p . Results are depicted in Table 6 and Table 7 and point to the same conclusion as the threshold-based metrics in Section 3 ; none of the models have recovered the world model, but the model trained on random walks performs best.

Our test also relies on Monte-Carlo sampling the model’s Myhill-Nerode boundary. The number of samples affects only the precision test. A prefix pair fails the compression test whenever there’s one suffix that the model accepts for one prefix and not for the other, so performance should worsen as the number of samples increases. Table 8 shows how the precision scores vary as a function of the number of samples for the shortest paths model. We use M = 30 M=30 Monte Carlo samples for our main reported metrics.

## Appendix F Rides data construction and training