LLMs lack persistent state tracking
Kleinberg finds LLMs miscount objects in generated stories at 15-40% error rates Simons Institute for the Theory of ComputingTL;DW
- LLMs fail basic world model tasks like counting people in narratives (~15% error rate), yet solve identical arithmetic instantly when framed as math problems—suggesting errors stem from attention allocation, not capability.
- Order dependence in state tracking: describing budget categories from high-to-low causes systematic inflation across all categories, violating consistency expected from systems with genuine world models.
- Repeated revision attempts reach chemical equilibrium, not zero errors—models fix some errors but reintroduce new ones at matching rates, creating stable error floors impossible for humans to eliminate through iteration alone.
- Framing dramatically affects numerical accuracy: stories generate 15% errors, blog posts 9.5%, news articles 2.5%, and math problems ~0.2%—the same underlying capability behaves radically differently based on genre framing.
- Myhill-Nerode theorem applied to sequence-generating systems: states can be extracted as equivalence classes of sequences, enabling principled probing for world models in game-playing, navigation, and constraint-satisfaction tasks.
- Models maintain state propagation consistency (e.g., sports scores) even when starting from corrupted states (~80-94% transition accuracy), suggesting they represent implicit dynamics rather than absolute facts.
- Compass direction tracking shows models confabulate details (shadows always point toward sunset regardless of direction traveled), indicating they optimize for narrative plausibility over geometric consistency.
- Multi-model revision scheduling is solvable via Bellman equations: using cheap models early to reduce errors, then expensive models to grind out remaining errors, yields minimum-cost error-reduction strategies.
- Navigation descriptions achieve 20% error rate per location even with tool use enabled, catching some errors while generating others—same model identifies failures it cannot prevent.
- World models in LLMs may be fundamentally about our explanation of what's happening inside rather than the model's understanding of the world—making definition and measurement inherently observer-dependent.
TL;DW
- LLMs fail basic world model tasks like counting people in narratives (~15% error rate), yet solve identical arithmetic instantly when framed as math problems—suggesting errors stem from attention allocation, not capability.
- Order dependence in state tracking: describing budget categories from high-to-low causes systematic inflation across all categories, violating consistency expected from systems with genuine world models.
- Repeated revision attempts reach chemical equilibrium, not zero errors—models fix some errors but reintroduce new ones at matching rates, creating stable error floors impossible for humans to eliminate through iteration alone.
- Framing dramatically affects numerical accuracy: stories generate 15% errors, blog posts 9.5%, news articles 2.5%, and math problems ~0.2%—the same underlying capability behaves radically differently based on genre framing.
- Myhill-Nerode theorem applied to sequence-generating systems: states can be extracted as equivalence classes of sequences, enabling principled probing for world models in game-playing, navigation, and constraint-satisfaction tasks.
- Models maintain state propagation consistency (e.g., sports scores) even when starting from corrupted states (~80-94% transition accuracy), suggesting they represent implicit dynamics rather than absolute facts.
- Compass direction tracking shows models confabulate details (shadows always point toward sunset regardless of direction traveled), indicating they optimize for narrative plausibility over geometric consistency.
- Multi-model revision scheduling is solvable via Bellman equations: using cheap models early to reduce errors, then expensive models to grind out remaining errors, yields minimum-cost error-reduction strategies.
- Navigation descriptions achieve 20% error rate per location even with tool use enabled, catching some errors while generating others—same model identifies failures it cannot prevent.
- World models in LLMs may be fundamentally about our explanation of what's happening inside rather than the model's understanding of the world—making definition and measurement inherently observer-dependent.
Using Myhill-Nerode theorem analysis and navigation tasks, Cornell's Kleinberg shows LLMs lack persistent state maintenance during generation—models fail to track people and objects across narratives but catch the same errors when explicitly prompted, revealing a gap between language fluency and world-model coherence.