Can Agents Infer Environment from Interaction? Evidence from Agentic Automata Learning

We propose a benchmark to evaluate the extent to which LLMs 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 LLMs can sometimes perform non-trivial interactive discovery, but remain far less robust and efficient than classic algorithms for the task.

• Machine intelligence

• Natural language processing