# Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning

arXiv: https://arxiv.org/abs/2606.16576 · HTML: https://mlsanity.com/paper/2606.16576/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in World models for language agents, one of 11 directions in World models.
- Builds on 14 of its 30 references that are in the map.
- First posted on arXiv 15 Jun 2026.

## Placed in

- World models / [World models for language agents](https://mlsanity.com/wm/world-models-for-language-agents/)
- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 14 of 14)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [OpenHands: An Open Platform for AI Software Developers as Generalist Agents](https://mlsanity.com/paper/2407.16741/) (2024)
- [Evaluating the World Model Implicit in a Generative Model](https://mlsanity.com/paper/2406.03689/) (2024)
- [In-Context Language Learning: Architectures and Algorithms](https://mlsanity.com/paper/2401.12973/) (2024)
- [LifelongAgentBench: Evaluating LLM Agents as Lifelong Learners](https://mlsanity.com/paper/2505.11942/) (2025)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [ProgramBench: Can Language Models Rebuild Programs From Scratch?](https://mlsanity.com/paper/2605.03546/) (2026)
- [Orak: A Foundational Benchmark for Training and Evaluating LLM Agents on Diverse Video Games](https://mlsanity.com/paper/2506.03610/) (2025)
- [AgencyBench: Benchmarking the Frontiers of Autonomous Agents in 1M-Token Real-World Contexts](https://mlsanity.com/paper/2601.11044/) (2026)
- [StateAct: Enhancing LLM Base Agents via Self-prompting and State-tracking](https://mlsanity.com/paper/2410.02810/) (2024)
- [What Teachers Should Know about the Bootstrap: Resampling in the Undergraduate Statistics Curriculum](https://mlsanity.com/paper/1411.5279/) (2014)
- [AQA-Bench: An Interactive Benchmark for Evaluating LLMs' Sequential Reasoning Ability](https://mlsanity.com/paper/2402.09404/) (2024)
- [LLMs as Probabilistic Minimally Adequate Teachers for DFA Learning](https://mlsanity.com/paper/2408.02999/) (2024)
- [L^*LM: Learning Automata from Examples using Natural Language Oracles](https://mlsanity.com/paper/2402.07051/) (2024)

## Built on by (most cited first, 1 of 1)

- [Tycho: Active Abstraction with Programmatic World Models for ARC-AGI-3](https://mlsanity.com/paper/2607.28287/) (2026)

## Abstract (arXiv)

We propose agentic automata learning to evaluate the extent to which tool-calling LLM agents can uncover hidden environments through interaction, a capability increasingly required in agentic tasks (e.g., reproducing an executable without access to its source code by interacting with it). In our setup, an agent should uncover a hidden deterministic finite automaton (DFA) by interacting with an oracle through (1) membership queries ("Does this string belong to the target language?'') and (2) equivalence queries ("Is this the target DFA?''). Agentic automata learning yields a scalable testbed with controlled task complexity, measurable interaction efficiency, and strong algorithms to compare against from the classic automata-learning literature. Evaluating state-of-the-art LLMs with a multi-turn agent scaffold, we find that while they are able to recover simple DFAs, their performance drops sharply as DFA size increases. Results improve with a more elaborate ReAct-style state-tracking scaffold, yet strong models still struggle with complex instances. Trajectory analyses reveal recurring failures in query planning, evidence integration, and hypothesis construction. These failures occur even though the models mention classic automata learning algorithms in their reasoning, and can implement and execute them when given access to a coding environment. Our results suggest that for state-of-the-art LLMs, identifying a solution to the problem is insufficient, and reliably executing the resulting plan still poses a distinct challenge.