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

A June 15, 2026 arXiv paper introduces agentic automata learning, a testbed in which tool-calling LLM agents must uncover a hidden deterministic finite automaton (DFA) through membership and equivalence queries to an oracle. Evaluating state-of-the-art LLMs, the authors find performance drops sharply as DFA size increases, with reasoning models markedly stronger than non-reasoning models but still far less robust and efficient than classic automata-learning algorithms. Trajectory analyses attribute recurring failures to query planning, evidence integration, and hypothesis construction.

Computer Science Computation and Language Submitted on 15 Jun 2026 Title:Can LLM Agents Infer World Models? Evidence from Agentic Automata Learning View PDF /pdf/2606.16576 HTML experimental https://arxiv.org/html/2606.16576v1 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. References & Citations Loading... Bibliographic and Citation Tools Bibliographic Explorer What is the Explorer? https://info.arxiv.org/labs/showcase.html arxiv-bibliographic-explorer Connected Papers What is Connected Papers? https://www.connectedpapers.com/about Litmaps What is Litmaps? https://www.litmaps.co/ scite Smart Citations What are Smart Citations? https://www.scite.ai/ Code, Data and Media Associated with this Article alphaXiv What is alphaXiv? https://alphaxiv.org/ CatalyzeX Code Finder for Papers What is CatalyzeX? https://www.catalyzex.com DagsHub What is DagsHub? https://dagshub.com/ Gotit.pub What is GotitPub? http://gotit.pub/faq Hugging Face What is Huggingface? https://huggingface.co/huggingface ScienceCast What is ScienceCast? https://sciencecast.org/welcome Demos Recommenders and Search Tools Influence Flower What are Influence Flowers? https://influencemap.cmlab.dev/ CORE Recommender What is CORE? https://core.ac.uk/services/recommender arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs https://info.arxiv.org/labs/index.html .