PaperlayerView exact revision on arXiv

Source-linked AI summary

Evaluating the World Model Implicit in a Generative Model

Keyon Vafa, Justin Y. Chen, Ashesh Rambachan, Jon Kleinberg, Sendhil Mullainathan

arXiv:2406.03689v3cs.CLcs.AI

TL;DR

Assessing whether generative models recover a domain’s underlying logic is difficult because strong next-token prediction need not imply accurate world-model recovery. This paper introduces Myhill–Nerode-inspired metrics and finds that models can perform well across navigation, games, and logic puzzles while their world models remain incoherent.

  • Problem

    Assessing whether models recover world models from sequence data matters because successful recovery could provide maps and routing without explicit mapping.

    Source: §1 · p. 1

  • Method

    The paper formalizes deterministic finite automata and introduces Myhill–Nerode-inspired sequence-compression and sequence-distinction metrics for assessing model recovery.

    Source: §1 · p. 2

  • Results

    Across navigation, Othello, and logic puzzles, generative models perform well on some tasks despite remaining far from recovering the true world models.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The findings support theoretically grounded metrics as feasible and insightful tools for assessing implicit world models across maps, games, and logic puzzles.

    Source: §5 · p. 10

    The paper focuses on deterministic finite automata, leaving extensions to more complex or unknown world models for future work.

    Source: §5 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether sequence models recover coherent world models, formalizing the question for deterministic finite automata and proposing Myhill–Nerode-inspired evaluation metrics. Across navigation, games, and logic puzzles, models can succeed on standard diagnostics while remaining far from the underlying world model.

1 Introduction

  • The motivating possibility is to infer a city map and routing behavior from trip sequences alone; the paper models finite-state domains including logic, location tracking, games, and scientific applications as DFAs.Source: §1 · p. 1
  • Next-token validity checks can miss severe state-model errors because distinct DFA states may require distinguishing sequences longer than one token.Source: §1 · p. 2
  • The proposed metrics test sequence compression for same-state inputs and sequence distinction for different-state inputs, with model-agnostic procedures using query access to the true DFA.Source: §1 · p. 2
  • Despite nearly 100% valid next-turn predictions and apparently location-encoding states, taxi-trained transformers reconstructed implausible Manhattan maps and failed when detours were introduced.The reconstructed maps included impossible street orientations and flyovers above other streets.Source: §1 · p. 2
  • Othello and logic-puzzle models likewise performed remarkably well on some tasks despite failing to recover the true world model; the paper releases a taxi-ride benchmark and evaluation software.Source: §1 · p. 2
  • Unlike representation probes used in prior work [11] [19] [1] [16] [20] or theoretical capability tests with state labels [22], these metrics assess how closely a trained model recovers the underlying DFA.Source: §1 · pp. 2–3

2 Framework

The framework formalizes world-model recovery for deterministic finite automata (DFAs) and introduces Myhill–Nerode boundary metrics to expose structural errors that next-token accuracy can conceal. It defines recovery at the language level and shows that exact next-token prediction is equivalent to recovering the DFA’s valid sequences.

2 Framework

  • The framework represents generative models as next-token distributions over sequences and DFAs as token-transition systems with a rejecting state; valid sequences avoid that state.It also defines the DFA state reached by a sequence and the sequences that lead to each state.Source: §2 · p. 3

2.1 Recovering world models

  • For a DFA, recovery means generating positive-probability sequences exactly when they are valid, and this holds if and only if the model makes exact next-token predictions.The framework assumes training and test sequences belong to the DFA’s language; this formalizes recovery beyond prior work on legal game moves [36] [20].Source: §2.1 · p. 3

2.2 Next-token prediction is a fragile metric for recovering structure

  • A uniform model with no board information predicts a valid next move in more than 99% of cumulative Connect-4 states when n=1000, illustrating next-token metrics’ fragility.For boards with no filled columns, every column is a valid move, so the uniform model can appear nearly correct despite encoding no board information.Source: §2.2 · p. 4

2.3 The Myhill-Nerode interior and boundary

  • Distinct DFA states have distinct accepted-suffix languages, but large shared interiors can hide their differences until minimal distinguishing suffixes on the Myhill–Nerode boundary.In cumulative Connect-4, boards with fewer than k disks in each column share valid next moves for the next n−k moves.Source: §2.3 · pp. 4–5

2.4 Compression and distinction metrics for evaluating world models

  • The proposed metrics compare model-implied and true Myhill–Nerode boundaries, assessing whether sequences reaching equal states are compressed and sequences reaching distinct states are distinguished.For equal-state pairs, compression reports boundary precision; for distinct-state pairs, distinction reports both precision and recall, averaged over uniformly sampled state pairs.Source: §2.4 · pp. 5–6
  • The uniform cumulative Connect-4 model has zero boundary recall for every pair of distinct states, although it can score highly on next-token validity.The boundary metrics are unaffected by the size of the shared interior between states.Source: §2.4 · p. 5

3 Illustration: Do Transformers Recover the Street Map of New York City?

Transformers trained on New York taxi-route directions can usually find valid, often shortest routes, yet the proposed metrics and map reconstructions expose incoherent implicit street maps. Their route-planning performance also deteriorates under detours.

3.1 Data and models

  • The analysis uses Manhattan taxi rides represented as a 4,580-node, 9,846-edge street graph and trains direction-sequence transformers on shortest paths, noisy shortest paths, or random walks.Training uses two GPT-2-style model sizes, selecting the best held-out model for each dataset.Source: §3.1 · pp. 6–7

3.2 Evaluating world models

  • Although next-token validity is nearly 100% and probes exceed 90%, all transformers compress poorly; random walks fail for half of states, while only random walks perform well on sequence distinction.Transformers trained on shortest paths or noisy shortest paths also perform poorly on sequence distinction, showing that compression and distinction reveal different weaknesses.Source: Table 1 · p. 7, §3.2 · pp. 7–8

3 Illustration: Do Transformers Recover the Street Map of New York City?

  • On unseen origin-destination pairs, all models generate valid traversals 96–99% of the time; the shortest-path model finds the true shortest path in 97% of sequences.The noisy-shortest-path model finds a shortest path for one of its training graphs in 94% of generated sequences.Source: §3.2 · p. 7

3.3 Reconstructing implicit maps

  • Reconstructed maps from random-walk model outputs contain physically impossible street orientations and implied flyovers, unlike maps reconstructed from true sequences corrupted at the same error rate.The reconstruction algorithm favors true-map edges subject to constraints; results across other models and reconstruction settings also yield incoherent maps.Source: Figure 3 · p. 8, §3.3 · p. 8

3.4 Implication of failing to recover the world model: detour fragility

  • Detours erode traversal validity for all models, but the random-walk model is more robust than models trained on (noisy) shortest paths, mirroring its advantage on the proposed metrics.Detours replace proposed tokens with either randomly chosen valid tokens or the model’s lowest-ranked valid token, while preserving a valid route to the destination.Source: Table 2 · p. 9, §3.4 · p. 9

4 Other Applications: Othello and Logic Puzzles

Across Othello and seating-arrangement puzzles, the proposed metrics reveal incoherent world models despite strong performance on existing diagnostics or fully specified tasks. Synthetic-data Othello models outperform real-game models on the proposed metrics and detour tests, while LLMs solve fully specified puzzles but perform poorly on compression and distinction.

Othello

  • For Othello, compression tests whether openings reaching the same board predict the same next moves, while distinction tests whether the model differentiates distinct boards.The game’s DFA representation allows these world-model metrics to be applied to sequence models.Source: §4 · p. 9
  • The real-game Othello model performed poorly on compression and distinction, while the synthetic-game model performed well, a contrast absent from existing metrics.Existing metrics showed the two models performing similarly.Source: §4 · p. 9
  • In Othello detour tests, the synthetic-data model produced near-perfect games regardless of detours, while the championship-data model failed immediately.This supports the finding that random or synthetic training data can recover more structure than real-world data.Source: §4 · p. 9

Logic puzzles

  • 40% was the highest compression precision and 0.60 the highest distinction recall among the LLMs, despite most solving fully specified puzzles.In more than half of same-state sequence pairs, models assigned different allowed continuations; results average 100 samples.Source: Figure 4 · p. 10, §4 · p. 10
  • The seating puzzle represents each state as the arrangements consistent with prior statements, with a statement valid if it does not contradict all arrangements in that state.The task uses statements about people’s assigned seats and relative positions.Source: §4 · p. 10
  • For three-person seating puzzles, the LLM evaluation tested compression and distinction recall; distinction precision was omitted because approximating each model’s Myhill-Nerode boundary was too expensive.Most models performed well when statements fully specified the arrangement, and GPT-4 was accurate on all examples.Source: §4 · p. 10

5 Conclusion

The paper proposes theoretically grounded metrics for assessing generative models’ implicit world models and finds that impressive task performance can coexist with incoherence that makes models fragile. Its primary limitation is the focus on deterministic finite automata (DFAs), with extension to richer or unknown world models left for future work.

5 Conclusion

  • The proposed metrics assess how closely generative models’ implicit world models capture domain logic, and applications to maps, games, and logic puzzles suggest they are feasible and insightful.The paper argues that measuring this closeness is needed to build high-fidelity algorithms that meaningfully capture the logic of modeled problems.Source: §5 · p. 10
  • Generative models can perform impressive tasks despite incoherent world models, but that incoherence makes them fragile on related tasks such as providing directions when there are detours.The paper also identifies incoherence as problematic when using generative models to learn latent information about the world in scientific domains.Source: §5 · p. 10
  • The primary limitation is the focus on DFAs; extending the approach to more complicated or unknown world models remains future work.The authors suspect that the core ideas of sequence compression and sequence distinction may generalize to richer settings.Source: §5 · p. 10

A Proof · B Reconstructed Maps · B.1 Algorithm

The proof establishes that recovering the world-model DFA is equivalent to exact next-token prediction. The reconstructed-map algorithm uses model-generated sequences to infer map edges, adding edges where sequences conflict with the true map.

A Proof

  • Recovering the world-model DFA is equivalent to achieving exact next-token prediction.The proof establishes both directions: recovery implies exact prediction, and exact prediction implies recovery.Source: A Proof · p. 13

B Reconstructed Maps

  • The appendix displays reconstructed maps for models trained on shortest paths, noisy shortest paths, and random walks across several parameter settings.Source: B Reconstructed Maps · p. 13

B.1 Algorithm

  • The algorithm represents Manhattan intersections as vertices positioned at their real-world coordinates and attempts to recover edges and directions from generated sequences.Source: §B.1 · p. 13
  • For valid sequences, the algorithm adds implied true edges; at the first invalid step, it greedily adds the edge maximizing subsequent agreement with the true map.The direction label of an added edge is the token at the invalid step.Source: §B.1 · pp. 13–14
  • Figure 6 plots performance metrics against maximum suffix length, while Figure 7 shows compression precision declining as current intersections have more two-way streets.Figure 7 reports results for the shortest-paths model.Source: Figure 6 · p. 14, Figure 7 · p. 14
  • Some sequence sets cannot be reconstructed under the constraints of one outgoing edge per direction per intersection, maximum degree, and maximum edge distance.For example, sequences [v1, v2, E, end] and [v1, v3, E, end] cannot both be reconstructed without violating the one-edge-per-direction constraint.Source: §B.1 · p. 14

B.2 Maps

Reconstructed Manhattan maps show more edges for random-walk outputs because their sequences are longer. The analysis also varies reconstruction constraints and checks whether maps change under alternative origin–destination sampling.

B.2 Maps

  • Maps were reconstructed from 6,400 transformer-generated sequences by sampling origin–destination pairs with at least one valid traversal under 100 moves; constrained maximum degree ranged from 4 to 8, and maximum edge distance from 1/2 to 1 mile.Source: §B.2 · p. 14
  • Under the altered origin–destination sampling, valid traversals fell from >95% to 65–80%, but Figure 12 showed similar maps using training or evaluation distributions.Source: §B.2 · p. 14
  • The reconstruction algorithm reuses true edges matching each direction, otherwise adding a nearby edge that maximizes continuation, subject to degree and distance constraints.It processes generated sequences from their source and discards sequences it cannot reconstruct or complete.Source: §B.2 · p. 15
  • Random-walk reconstructions visually contain more edges than shortest-path maps, reflecting longer sequences: shortest paths contain 983,182 directions, noisy shortest paths 1,140,487, and random walks 1,584,549.Source: §B.2 · p. 15

C Deterministic Finite Automata and Myhill-Nerode

The section grounds the world-model test in the Myhill-Nerode theorem, using the relationship between equivalent sequences and minimal DFA states to characterize regular languages.

C Deterministic Finite Automata and Myhill-Nerode

D Additional results · E Evaluation metric details and ablations

The additional results show that longer Myhill–Nerode boundaries expose weaknesses hidden by next-token tests, while map structure and training data distinguish model coherence. The section also outlines metric implementations and ablations across maps, Othello, and logic puzzles.

D Additional results

  • For navigation evaluation, models generate traversals conditioned on origin–destination pairs unseen during training.Training sequences contain an origin, destination, directions, and an end node.Source: D Additional results · p. 16
  • 100% compression precision at length-1 boundaries for the random-walk model falls to 50% with the full Myhill–Nerode boundary.The analyses vary suffix lengths to approximate the boundary, showing why longer boundaries matter beyond single next-tokens.Source: D Additional results · p. 16
  • In maps, more two-way streets at an intersection correlate negatively with compression precision, weakening recognition that routes to the same intersection share a state.Figure 7 plots this relationship for the shortest-paths model.Source: D Additional results · p. 16

E Evaluation metric details and ablations

  • Section E provides metric implementation details and ablations for maps, Othello, and logic puzzles.These details concern the test introduced in Section 2.4 and implemented in Section 3.Source: E Evaluation metric details and… · p. 16

D Additional results

  • Othello models trained on synthetic data recover the true world model and produce near-perfect games under detours, while championship-trained models fail immediately.The checkpoints were provided by Li et al. [20].Source: D Additional results · p. 16, Table 4 · p. 17

E Evaluation metric details and ablations

  • Othello detours replace a proposed move with either a random valid move or the model’s lowest-ranked valid move.Table 4 reports the fraction of valid traversals under these random and adversarial detours.Source: Table 4 · p. 17

E.1 Implementation details

The implementation approximates Myhill–Nerode compression and distinction tests differently for maps, Othello, and logic puzzles. Because LLM token probabilities and chain-of-thought marginalization are unavailable or intractable, the logic-puzzle tests use prompting and Monte Carlo sampling.

Maps

  • For maps, compression pairs two sampled length-limited paths to the same state, while distinction tests compare sampled prefixes for different states against minimal distinguishing suffixes.Both transformer boundaries are approximated with 30 Monte Carlo samples; the map distinction test uses continuations of length 5, with results robust for k ≥ 5.Source: §E.1 · p. 17

Othello

  • Othello compression samples boards reached by multiple games, while distinction samples equal-length-game states and prefixes; both transformer-boundary tests use 30 Monte Carlo samples.The distinction test also samples valid gameplay trajectories for the true world model, using a threshold of 0.01.Source: §E.1 · pp. 17–18

Logic puzzles

  • Logic-puzzle tests use prompting because token-level probabilities are unavailable and sampling long continuations while marginalizing over chain-of-thought is computationally intractable.Models are prompted to reason step by step, answer with the keyword “Answer:”, and are queried using greedy decoding.Source: §E.1 · p. 18
  • For logic-puzzle compression, models are tested on two prefixes leading to the same state and five candidate continuations; the reported metric overestimates true capability.The test samples 100 states, and no model scores above 0.35 with only five continuation samples, suggesting substantial compression failure.Source: §E.1 · p. 18
  • Logic-puzzle distinction samples statements from the tractable true boundary to test whether the model accepts them when prompted with prefixes for distinct states.The experiments use five boundary statements because querying the LLM for every example remains expensive.Source: §E.1 · p. 18

E.2 Ablations

The ablations show that the finding of incoherent world models is stable across acceptance rules and threshold values. They also clarify how threshold choice and Monte Carlo sample count affect the metrics.

E.2 Ablations

  • At ϵ=10^-6, random walks has high compression and distinction precision but distinction recall is 0.11; at ϵ=0.10, distinction recall is 1.00 while compression precision is 0.16.The tradeoff between precision and recall changes with ϵ, but every model remains incoherent across the tested values.Source: §E.2 · pp. 18–19, Table 5 · p. 19
  • Across threshold-, top-k-, and top-p-based acceptance, none of the models recovered the world model, though the random-walk model performed best.Top-k accepts tokens ranked among the model’s k highest; top-p accepts tokens in the smallest highest-probability set whose cumulative probability exceeds p.Source: Table 6 · p. 19, §E.2 · p. 19, Table 7 · p. 20
  • Monte Carlo sample count affects only precision: more samples should worsen compression precision because one discrepant suffix fails compression; the main metrics use M=30.A prefix pair fails the compression test if any suffix is accepted for one prefix but not the other.Source: §E.2 · p. 19, Table 8 · p. 20

F Rides data construction and training

The rides datasets represent Manhattan taxi trips as graph traversals, constructed using shortest paths, noisy shortest paths, or random walks. GPT-2 models were trained on each dataset using architecture and checkpoint choices tailored to dataset size.

Shortest paths

  • Manhattan taxi rides were mapped to a 4,580-node, 9,846-edge graph [5]; shortest-path traversals yielded 2,932,675 training sequences and 120,400,201 tokens.The source subset contained 3,358,737 rides from January–March 2014, made available by Murray.Source: F Rides data construction and training · p. 20

Noisy shortest paths

  • Noisy shortest paths add Gamma-distributed edge-weight noise and resample 50 weighting functions, producing 30,599,312 training sequences and 1,677,587,216 tokens.The added noise scales with each edge’s original length, approximating traffic variation.Source: F Rides data construction and training · p. 20

Random walks

  • Random walks sample a starting node and sequence length uniformly, then choose edges uniformly, yielding 90,646,864 training sequences and 4,735,591,368 tokens.Sequence lengths range from 3 to 100.Source: F Rides data construction and training · p. 20

Training

  • The shortest-path model used GPT-2 small, while noisy-shortest-path and random-walk models used GPT-2 extra-large; training ran for 5 and 1 epochs, respectively, on the larger datasets.The shortest-path model was trained until overfitting, selecting its best validation checkpoint; the larger-dataset models used their last validation checkpoint. All models used 8 A100 GPUs and batches of 6 sequences per GPU; training took about 12–48 hours.Source: F Rides data construction and training · pp. 20–21

G Additional maps

The additional map reconstructions cover transformers trained on shortest paths, noisy shortest paths, and random walks; despite trajectories being valid more than 95% of the time, reconstruction errors reveal incoherence.

Additional maps

  • Reconstructions using 50k sequences showed that trajectories were valid more than 95% of the time, yet errors revealed incoherence.The sequences used origin–destination pairs sampled from the training distribution, with maximum degree 4 and maximum edge length 1/2 mile.Source: Figure 12 · p. 25
  • Shortest-path reconstructions failed on 1513/6400 (degree 4, 1/2 mile), 1435/6400 (degree 8, 1/2 mile), 1334/6400 (degree 4, 1 mile), and 1174/6400 (degree 8, 1 mile) sequences.Source: Figure 13 · p. 25, Figure 14 · p. 25, Figure 15 · p. 26
  • Noisy-shortest-path reconstructions failed on 2213/6400 (degree 4, 1/2 mile), 1869/6400 (degree 8, 1/2 mile), 1935/6400 (degree 4, 1 mile), and 1702/6400 (degree 8, 1 mile) sequences.Source: Figure 17 · p. 26, Figure 18 · p. 27, Figure 19 · p. 27
  • Random-walk reconstructions failed on 1987/6400 (degree 4, 1/2 mile), 1491/6400 (degree 8, 1/2 mile), 1905/6400 (degree 4, 1 mile), and 1323/6400 (degree 8, 1 mile) sequences.Source: Figure 21 · p. 28, Figure 22 · p. 28, Figure 23 · p. 28
Loading 2406.03689v3…