Search papers, labs, and topics across Lattice.
This study introduces agentic automata learning to assess the ability of tool-calling LLM agents to infer hidden environments through interaction with an oracle using membership and equivalence queries. The findings reveal that while reasoning models outperform non-reasoning models, LLM performance significantly declines with increasing DFA complexity, highlighting critical failures in query planning and hypothesis construction. Ultimately, the research indicates that current LLM agents can engage in interactive discovery but are less efficient and robust compared to traditional automata-learning algorithms.
LLM agents struggle to uncover hidden environments, with performance plummeting as task complexity increases, revealing fundamental limitations in their interactive reasoning capabilities.
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.
Google Research