- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The authors assess if tool-calling LLM agent being told to learn/discover a hidden deterministic finite automaton (DFA) over the alphabet {a, b} . The agent can ask two kinds of questions: a membership query (MQ: is this word accepted?) and an equivalence query (EQ: here is my hypothesis DFA, is it equivalent to the hidden one, and if not give me a word on which they differ?). The agent is successful if if an EQ returns “equivalent” under a constrained budget. This is the setting for which classical learners exist and have been propose and for which efficiency proofs exist. In this way, the authors can compare an LLM against well-understood algorithms on the same instances. The authors ask whether frontier reasoning models can infer a hidden structure from interaction, how this depends on the structure’s size, and whether an explicit state-tracking scaffold helps.
Critical strengths
The paper proposes a novel idea, which is interesting albeit not groundbreaking. The authors propose a DFA learning as an agentic testbed and assess the LLM as a learner. The contribution of budgets derived from L* and TTT is also original. The contribution consists also in the combination of exact structural recovery, guaranteed solvability and an algorithmic yardstick. The paper is well written and contains well defined benchmarks, The formal task is well introduced and the authors relate to classical references , an explicit context-limit check. Additionally, they provide full prompts and comprehensive cost report.
Critical weaknesses
I could not understand why the chosen model is so simple. The paper investigates only single fixed (binary) alphabet and such the natural question arises if larger sized alphabets would also be suitable for the approach. The authors use uniformly sampled random DFAs over {a, b}. These DFAs have no real world equivalent and as such do not represent meaningful use cases. The reviewer can't imagine a real world application which can benefit from the proposed solution. The authors analyze only deterministic environments. Nondeterministic and/or probabilistic environments are mentioned as future work, but are more realistic.
Questions for authors
What is the maximum sized alphabet for which the proposed method works. Why have larger alphabets have not beed used ? Can the authors present a real world scenario for which the proposed solution works ? What happens if structured (non-random) DFAs and noisy or non-minimal counterexample policies are tested ? Who are the "target users" of the proposed approach ? Basically, which research community needs to leverage the solution ? Can the authors provide more information about OpenHands ? Most readers might not have heard about it.
4 comments
Q3: What happens if structured (non-random) DFAs and noisy or non-minimal counterexample policies are tested ?
The counterexamples that the oracle returns are not minimal – if the minimal counterexample is of size n, the oracle returns a counterexample of length between n to n+3 (Section 4, “Oracle counterexample selection strategy.”). However, a preliminary experiment we ran with Gemini 3.1 Pro over half of the dataset, had used minimal counterexample oracle strategy. In that setup we saw that the agent identifies that the returned counterexample is minimal and leverages this as some kind of a “shortcut”, which makes the agent converge to a correct solution quicker than in experiments described in the paper with non-minimal counterexamples, as shown in the table below. We will clarify our counterexample selection strategy in our revised manuscript, and add a discussion about how the agent leverages the signal in a setup where counterexamples are minimal.
Query efficiency results table – Δ queries from classic algorithms, lower is better, calculated over 20 DFAs in each row
| Number of states | Δ for Minimal counterexample | Δ for Non-minimal counterexample |
|---|---|---|
| 2–3 | -0.75 | 1.00 |
| 4–5 | -0.26 | 5.06 |
| 6–7 | 2.05 | 4.92 |
| 8–9 | 15.27 | 25.40 |
Q4: Who are the “target users” of the proposed approach ? Basically, which research community needs to leverage the solution ?
Our proposed evaluation framework is relevant to users who deploy agents to work in unknown or new environments, in which the tools given to the model can interact with the environment but never be exposed to the rules that are forming it. Our evaluation framework can shed light on the current limitation of agents’ planning, reasoning, and their ability to follow a plan over a long trajectory, as well as testing the effect of different harnesses on the performance. Due to the robustness of our DFA sampling method, as models will improve we can always refresh the data to remain unsaturated, by arbitrarily enlarging the number of states in the DFA, or as the reviewer suggested, extending the alphabet size, to increase the task difficulty. We will clarify this in the revised manuscript.
Q5: Can the authors provide more information about OpenHands?
OpenHands [1] is an open-source platform for AI software development agents that provides tools for writing, editing, and executing code. Each agent runs in a Docker-sandboxed environment that includes a bash shell, an interactive Python (IPython) server, file-editing tools, and a web browser (which we disabled in our experiments, as the agent had no Internet access). This is a popular approach used in many recent papers, for example to train software engineering agents on SWE-Gym [2] and to evaluate agents on real-world workplace tasks in TheAgentCompany [3]. We will include a detailed explanation of the OpenHands platform in the revised manuscript.
References
[1] X. Wang, B. Li, Y. Song, F. F. Xu, X. Tang, M. Zhuge, J. Pan, Y. Song, B. Li, J. Singh, H. H. Tran, F. Li, R. Ma, M. Zheng, B. Qian, Y. Shao, N. Muennighoff, Y. Zhang, B. Hui, J. Lin, R. Brennan, H. Peng, H. Ji, and G. Neubig, “OpenHands: An open platform for AI software developers as generalist agents,” in Proc. 13th Int. Conf. Learning Representations (ICLR), 2025.
[2] J. Pan, X. Wang, G. Neubig, N. Jaitly, H. Ji, A. Suhr, and Y. Zhang, “Training software engineering agents and verifiers with SWE-Gym,” in Proc. 42nd Int. Conf. Machine Learning (ICML), PMLR vol. 267, 2025, pp. 47717–47737.
[3] F. F. Xu, Y. Song, B. Li, Y. Tang, K. Jain, M. Bao, Z. Z. Wang, X. Zhou, Z. Guo, M. Cao, M. Yang, H. Y. Lu, A. Martin, Z. Su, L. Maben, R. Mehta, W. Chi, L. Jang, Y. Xie, S. Zhou, and G. Neubig, “TheAgentCompany: Benchmarking LLM agents on consequential real world tasks,” arXiv:2412.14161, 2024.
We would greatly appreciate it if you could take a moment to let us know whether our response has adequately addressed your concerns. If any questions or concerns remain, we would be happy to continue the conversation.
Thank you for your time and consideration!
As the rebuttal period is about to end, we would appreciate hearing your thoughts on our rebuttal.
We took your feedback about the simplicity of our environments into account and clarified that we focus on simple settings because they enable controlled evaluation while agents still struggle with them today, implying that they will fail on more complex real-world environments.
As agents improve, the same framework can support more complex, realistic environments by changing how the hidden structure is sampled or how the oracle behaves.
We hope this addresses your concerns and would welcome your updated assessment. Thank you very much for your time and effort!
We would like to thank the reviewer for their feedback. We are happy that the reviewer finds our idea novel and interesting, and appreciate them pointing out the contribution of our setup in terms of its structure, solvability, and algorithmic grounding.
Regarding the concern that our binary alphabet setup is simple, we agree with the reviewer that the alphabet size is an interesting difficulty knob that remained under explored in our current experiments, and following the reviewer’s comment we conducted a small-scale experiment with larger alphabet sizes, fixing the number of states (see Q1 below). We find that larger alphabets make the task harder for the agent: success drops from 100% on 4-state DFAs over 2 letters to 50% on 4-state DFAs over 8 letters. These results establish alphabet size as another meaningful difficulty knob, alongside the number of states, which is the focus of our work. The number of states corresponds to the number of “rules” of the induced language that the learner has to extract. As shown in the paper, the agent’s success rate drops as the number of states grows, which shows that the agent struggles to recover the environment even with a binary alphabet. In the revised manuscript, we will discuss the different difficulty knobs that affect this task and include the results of this small-scale experiment to support this.
Regarding the concerns about the applicability of our proposed solution/approach, we would like to clarify that the main contribution of our work is an evaluation framework. By leveraging the problem's established theoretical foundations and the existence of classic learning algorithms, our evaluation framework can be used to systematically evaluate agent behavior and identify current limitations in their reasoning and learning process. Moreover, we argue that our results do have practical importance, as if models fail in such scenarios, then this is an indication that they will fail in more complex, real-world ones, where for example noise is introduced and the vocabulary is large. We will add this point to the paper.
Below we answer specific questions raised by the reviewer.
Our sampling method allows us to generate DFAs with any finite number of states and any finite alphabet size, and to test any generated DFA in the active learning evaluation framework we propose in this work. To demonstrate this flexibility, we conducted a small-scale experiment with increasing alphabet sizes, fixing the number of DFA states to 4, and evaluated Gemini 3.1 Pro with our stateful scaffold on 32 task instances (8 per alphabet size). The results, presented in the table below, suggest that larger alphabets make the task harder. However, given the small sample size and the wide confidence intervals, more instances are needed to establish the precise trend and its statistical significance. More broadly, alphabet size is one of several difficulty factors, alongside DFA structure, sampling distribution, and counterexample policy. Our framework supports varying each of them, opening the door for future work to explore their effect on agent performance. We will include this experiment as an additional analysis in the revised manuscript, along with a discussion of other difficulty factors, and clarify that our framework allows generating DFAs with different alphabet sizes.
Success rate of Gemini 3.1 Pro on 4-state DFAs with varying alphabet sizes (bootstrapped 95% CIs):
As mentioned above, our main contribution is an evaluation framework, which is theoretically established and allows systematic analysis of agent behaviour. This hidden environment recovery task is motivated from real-world scenarios in which the agent needs to act in an unknown environment, where it can only interact with it via tools (e.g., API calls or function calling for coding agents), but is not aware of its underlying rules (e.g., it cannot access the source code). We will clarify this in the revised manuscript.
We address the remaining reviewer questions (Q3–Q5) in a follow-up response.