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

Reef Menaged, Gili Lior, Shauli Ravfogel, Roee Aharoni, Gabriel StanovskyarXiv 2026 · arXiv

TL;DR

This paper introduces agentic automata learning, a new framework to evaluate whether tool-calling LLM agents can infer the underlying "world models" of hidden environments through interaction. The authors find that while state-of-the-art reasoning models show non-trivial discovery skills on simple tasks, their performance plummets as environment complexity increases, leaving them far less robust and efficient than classic computer science algorithms.

What Problem Does This Paper Address?

As LLMs are increasingly deployed as autonomous agents in games, navigation, and software engineering, a fundamental question remains: Do these agents actually understand the underlying rules and structure of their environments (i.e., build an internal "world model"), or are they just exploiting local patterns and shallow heuristics?

Testing this requires a benchmark where the environment's hidden structure is perfectly known, its complexity can be precisely controlled, and the agent's step-by-step discovery process can be fully observed. The authors address this gap by adapting active automata learning—a classic problem from computational learning theory—into a rigorous testbed for LLM agents.

Methods

The authors recast active automata learning into a tool-calling setup. An LLM agent is tasked with uncovering a hidden Deterministic Finite Automaton (DFA) by interacting with an oracle using two primary tools:

  1. Membership Queries (MQ): The agent asks if a specific string belongs to the target language.
  2. Equivalence Queries (EQ): The agent proposes a candidate DFA hypothesis. The oracle either confirms it is correct (ending the game) or returns a counterexample string where the candidate and target DFAs disagree.
   [ LLM Agent ] --(Proposes Candidate DFA)--> [ Oracle ]
        ^                                           |
        |---------(Returns Counterexample)----------|

To understand why models fail, the authors also introduce a clever diagnostic method using classic passive learning algorithms (like RPNI and Blue-Fringe). By feeding the history of an LLM's queries into a passive learner, they can determine if the LLM failed because it didn't gather enough information (planning failure) or because it had the information but couldn't synthesize it into a correct model (reasoning failure).

Datasets

The authors procedurally generated an evaluation dataset of 80 task instances using Boltzmann sampling to ensure a uniform distribution of accessible, minimal DFAs over a binary alphabet. The dataset is evenly split into four complexity levels based on the number of states in the minimal DFA:

  • 2–3 states (Very Simple)
  • 4–5 states (Simple)
  • 6–7 states (Moderate)
  • 8–9 states (Complex)

Key Insights and Ideas

  • Reasoning Tokens are Mandatory: A massive performance chasm exists between models with explicit reasoning/thinking mechanisms (like Gemini 3.1 Pro) and those without (like GPT-5.4 without thinking or Llama-3.3-70B). Non-reasoning models completely flatlined (0% success) on any automaton with 4 or more states.
  • LLMs Aren't Just Mimicking Algorithms: Trajectory analysis proved that LLMs are not merely replaying memorized code for classic algorithms (like $L^*$ or TTT). LLMs frequently violated algorithmic properties like monotonicity (the tendency of algorithmic hypotheses to grow strictly larger/more complex over time) and heavily overused equivalence queries.
  • Context-Window Amnesia: As interactions grow longer (beyond ~60 steps), LLMs increasingly suffer from memory organization failures. They begin issuing "non-informative queries"—asking questions that were already answered or proposing hypotheses directly contradicted by previous evidence.

Key Results

  • The Complexity Cliff: On the simplest DFAs (2–3 states), most advanced models performed well. However, for complex automata (8–9 states), no LLM exceeded a 25% success rate, whereas classic algorithms solve 100% of them instantly.
  • Efficiency Gap: Even on successful runs, the best-performing model (Gemini 3.1 Pro) required 45.8% more tool calls than the classic TTT algorithm to find the correct DFA.
  • The 4-5 State Threshold: In the 4–5 state tier, Gemini 3.1 Pro achieved an impressive 85% success rate, while Gemini 3 Flash (which only reasons on some steps) dropped to 15%, and all non-reasoning models hit 0%.

Limitations and Future Work

The primary limitation of this evaluation framework is its high computational and monetary cost. Long interactive runs over hundreds of steps consume millions of tokens; the full evaluation suite of 480 runs cost roughly $1,200, with some individual complex runs taking up to 20 hours.

For future work, the authors suggest expanding the framework beyond deterministic, clean environments to include non-deterministic or stochastic environments, as well as introducing noisy or partial oracle feedback to better mimic messy, real-world agent deployments.

Summary updated

Abstract

We propose agentic automata learning to evaluate the extent to which tool-calling LLM agents can uncover hidden environments through interaction. 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?"). This yields a scalable testbed with controlled task complexity, measurable interaction efficiency, and strong baselines (classic automata-learning algorithms). Evaluating state-of-the-art LLMs, we find that performance drops sharply as DFA size increases. Reasoning models are markedly stronger than non-reasoning models, yet trajectory analyses reveal recurring failures in query planning, evidence integration, and hypothesis construction. Overall, our results show that current LLM agents can sometimes perform non-trivial interactive discovery, but remain far less robust and efficient than classic algorithms for the task.
BibTeX
@misc{menaged2026can,
  author = {Reef Menaged and Gili Lior and Shauli Ravfogel and Roee Aharoni and Gabriel Stanovsky},
  title = {{Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning}},
  year = {2026},
  eprint = {2606.16576},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.16576},
}

Loading related content...

Figure