Research map / Large language models / Agents, code and math
Evaluating the World Model Implicit in a Generative Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Myhill-Nerode-inspired compression and distinction metrics to evaluate whether generative sequence models recover the DFA world model behind them, showing models that pass existing next-token tests still have incoherent world models.
Problem
Existing diagnostics (next-token validity and linear probes) can say a sequence model has learned a world model even when its implicit state structure is incoherent; a principled model-agnostic test of world model recovery is needed for sequence models whose true world is a DFA.
Approach
Formalize world model recovery as language-level equivalence to a DFA and derive two sequence-based metrics from the Myhill-Nerode theorem: compression precision (sequences reaching the same state should share continuations) and distinction precision/recall (sequences reaching different states should have different continuations, measured via Myhill-Nerode boundaries).
Key results
- On Manhattan, transformers trained on shortest paths, noisy shortest paths, and random walks achieve over 90% on next-token test and probe, but compression precision is only 0.10, 0.05, and 0.50 respectively.
- Random-walk model achieves distinction precision 0.99 and recall 1.00, while shortest-path models get distinction recall of 0.20 and 0.24.
- For LLMs on the seating logic puzzle, no model exceeds 40% compression precision and no model exceeds 0.60 distinction recall, despite most solving fully specified puzzles.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train on random walks instead of shortest paths | Transformer world-model recovery on NYC taxi rides · NYC taxi rides | distinction recall: 0.20 (0.01) -> 1.00 (0.00) | Helped |
| train on random walks instead of noisy shortest paths | Transformer world-model recovery on NYC taxi rides · NYC taxi rides | compression precision: 0.05 (0.01) -> 0.50 (0.02) | Helped |
| train on synthetic games instead of championship games | Othello sequence model · Othello | compression precision: 0.00 (0.00) -> 0.98 (0.00) | Helped |
| train on synthetic games instead of championship games | Othello sequence model · Othello | distinction recall: 0.27 (0.01) -> 1.00 (0.00) | Helped |
| increase epsilon from 10^{-2} to 10^{-6} (ablation) | Random walks transformer · NYC taxi rides | compression precision: 0.46 (0.06) -> 0.99 (0.01) | Helped |
| increase epsilon from 10^{-2} to 10^{-6} (ablation) | Random walks transformer · NYC taxi rides | distinction recall: 1.00 (0.00) -> 0.11 (0.03) | Hurt |
| increase epsilon from 10^{-6} to 0.10 (ablation) | Random walks transformer · NYC taxi rides | distinction recall: 0.11 (0.03) -> 1.00 (0.00) | Helped |
| increase epsilon from 10^{-6} to 0.10 (ablation) | Random walks transformer · NYC taxi rides | compression precision: 0.99 (0.01) -> 0.16 (0.04) | Hurt |
Surprising findings
- Models scoring near 100% on next-token validity and linear probe accuracy can have compression precision as low as 0.05 on the taxi navigation task.
- A uniform random next-token generator scores near-perfect on next-token prediction in cumulative Connect-4 for large board heights, showing next-token metrics are fragile.
Limitations
- Focuses on deterministic finite automata; richer or unknown world models are not covered.
- LLM logic-puzzle compression metric relies on prompting rather than token probabilities and uses only 5 sampled continuations.
- Metrics depend on acceptance threshold epsilon, with precision/recall tradeoffs across values.
Experimental setup
Datasets: NYC Taxi & Limousine Commission taxi rides (Manhattan) Othello championship games Othello synthetic games
Benchmarks: next-token test current-state probe Manhattan route planning Othello world model metrics seating arrangement logic puzzle
Metrics: compression precision distinction precision distinction recall next-token validity valid traversal fraction under detours probe accuracy
Baselines: next-token test current-state probe untrained transformer Championship Othello Synthetic Othello
Builds on: Myhill-Nerode theorem Othello-GPT GPT-2
Closest papers by meaning
- Do LLMs Build World Representations? Probing Through the Lens of State Abstraction (NeurIPS 2024 · similarity 0.87)
- Improving Factuality and Reasoning in Language Models through Multiagent Debate (ICML 2024 · similarity 0.87)
- Monitoring Latent World States in Language Models with Propositional Probes (ICLR 2025 · similarity 0.87)
- LTD-Bench: Evaluating Large Language Models by Letting Them Draw (NeurIPS 2025 · similarity 0.86)
- Large Language Models Think Too Fast To Explore Effectively (NeurIPS 2025 · similarity 0.86)
- Scaling Laws for Pre-training Agents and World Models (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.