Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning
For researchers evaluating LLM agents' interactive reasoning and world-model inference capabilities, the paper provides a controlled benchmark revealing current limitations.
The paper proposes agentic automata learning to test whether LLM agents can infer hidden deterministic finite automata through interaction. Results show performance drops sharply with DFA size, and reasoning models outperform non-reasoning ones but still fall short of classic algorithms.
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.