acceptodds
Under review as a conference paper at ICLR 2027

Composition Discovery in Tool Worlds by Active Exploration

Abstract

Agents usually discover connections between tools, which we call handoffs, while solving a task, leaving the knowledge tied to specific trajectories. We investigate whether an agent can instead explore a tool world, a set of callable functions together with the data behind them, before any task, with the explicit goal of building reusable knowledge about its tools. Task-free exploration faces two bottle-necks: the combinatorial number of candidate handoffs, and the volatility of tool data. Because experiments require valid inputs from earlier calls, every change of the data invalidates the inputs collected so far. We introduce ICHNAEA, an explorer that maintains a Beta belief over candidate handoffs and selects the calls whose outcomes are expected to be most informative. To overcome data volatility, ICHNAEA stores each successful call as a recipe and, when the data change, re-executes its recipes to rebuild fresh inputs. We evaluate ICHNAEA on procedural tool worlds, where the true handoffs are known and names can be hidden, and on AppWorld, a benchmark of simulated everyday apps for language-model agents. In procedural worlds, ICHNAEA learns handoffs that complete every target workflow in unseen data, with no false handoff, while without rebuilding its inputs the explorer completes 0–73% depending on how much the names reveal. A language-model agent given these handoffs reaches every target, against 0–89% without them. On AppWorld, documentation alone already lets the agent reach nearly every goal, and some calls succeed only by coincidence. This points to two limits outside generated worlds: what exploration adds depends on how much of a suite’s composition its documentation leaves unstated, and without known true handoffs, discovery is hard to measure.

Primary area:
applications to robotics, autonomy, planning
Keywords:
tool-using agents, LLM agents, tool composition, composition discovery, API dependency discovery, active learning, Bayesian experimental design, task-free exploration, AppWorld

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_35LuOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies task-free discovery of parameter-level connections between tools. It proposes ICHNAEA, an explorer that maintains Beta beliefs over candidate connections, selects calls using predicted acceptance and information gain, and stores successful calls as recipes. When the environment's data change, these recipes are replayed to reconstruct valid inputs for further exploration. Experiments show improved graph reuse and downstream target-function reachability in procedural tool worlds. Results on AppWorld reveal limitations from coincidental argument acceptance and provide limited evidence of additional benefit over documentation alone.

Critical strengths
  1. Learning reusable tool connections before receiving a task is a useful problem. The distinction between persistent connection knowledge and transient input values is well motivated, and recipe replay provides a concrete mechanism for rebuilding inputs after data changes.

  2. The paper includes systematic component ablations and held-back-seed evaluations in its procedural environments. It also candidly reports negative results on AppWorld, including cases where replay reinforces coincidental connections.

Critical weaknesses
  1. The method does not adequately distinguish executable connections from semantically meaningful ones. Its claim rule relies on successful execution and an acceptance-probability threshold, which do not establish that an output serves the intended semantic role of the receiving parameter. The paper's example of a review rating being accepted as a song ID illustrates this directly. Replay can then reinforce the same coincidence and increase confidence in a spurious connection. Although specificity probes are collected, they do not affect the claim rule. This is a central unresolved limitation for a method intended to provide reusable tool-composition knowledge. The AppWorld results demonstrate its practical impact: with the fixed planner, adding reconstruction reduces expert-endorsed goal reach from 63% to 31% on Spotify while increasing unendorsed reach from 16% to 44%. Unendorsed routes are not necessarily all incorrect, but these results do not establish improved connection quality.

  2. The evaluation does not sufficiently establish benefits for realistic task completion. The strongest positive results come from an author-designed generator with a fixed chain structure, negligible identifier collisions, and explicit feedback identifying rejected arguments. These assumptions substantially simplify discovery and largely avoid the semantic ambiguity exposed by AppWorld. The downstream study uses only Gemini 3.5 Flash and evaluates successful invocation of target functions rather than completion of full user tasks. On AppWorld, documentation alone achieves 95/99 successful attempts, compared with 96/99 using the graph learned with reconstruction and transfer; the original AppWorld tasks are not evaluated. Thus, the synthetic improvements do not yet establish useful gains in realistic agent performance. Moreover, reduced downstream calls do not by themselves demonstrate overall efficiency once the upfront exploration budget is included, and there is no comparison against an LLM explorer under a comparable budget.

Questions for authors
  1. Additional evidence on connection validity: Can the authors evaluate a claim rule that incorporates the collected specificity probes or another semantic-consistency check, and show whether it reduces coincidental connections while preserving useful coverage on AppWorld? This would directly address the failure mode introduced by replay.

  2. Additional evidence on practical utility: Can the authors demonstrate improved end-to-end task success on a more realistic evaluation, using task-level correctness rather than target-function reachability? A comparison with documentation-only and LLM-based exploration baselines, accounting for both exploration and downstream costs over a stated number of tasks, would materially affect my assessment.

Reviewer_utt7OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Agents usually learn how tools connect (which output of one function can be passed as an input to another, called a "handoff") only while solving a task, so the knowledge is not reused. The paper proposes ICHNAEA, an explorer that calls tools before any task, keeps a Beta belief for each candidate handoff, and chooses calls by expected information. The main characteristic is, 1) not relying on llm-based agent so it is cheap; 2) exploration without relying on given task queries or curriculum. In synthetic worlds it completes every target workflow with no false handoff. On AppWorld, documentation alone already suffices, and coincidental successes limit the method.

Critical strengths
  • A careful and honest study. The paper reports its negative AppWorld result plainly, and the Limitations section says exactly which conclusions depend on the synthetic setup.
  • The idea is Novelty. Examine building a prior knowledge graph of tool chains without llm-agents and see if it helps downstream agent task is rarely studied.
  • Thorough ablations and controlled variables. Every combination of the mechanisms is tested in all three naming conditions (Table 1, Tables 4–6), and the main results are confirmed on ten held-back seeds (Table 2).
  • Reproducible. The supplementary materials are well prepared to reproduce key arguments of the paper.
Critical weaknesses

Major:

  • The evidence comes from a toy world built to fit the method. However, on the one real benchmark, the key mechanism hurts.
    • It doesn't consider large collision rates, or large data sharing between tools. It also doesn't consider encryption decryption of data. Which may make it far from difficulties of real world applications.
    • All positive results use one generated structure: 6 chains × 7 stages, huge unique identifiers, and error messages that name every bad argument.
    • Every value expires at once every 500 calls. This design choice creates the problem that replay solves: with no data changes, the plain explorer already reaches 100% (real names) and 77% (masked) of workflows (Table 1, last row).
    • Real tool suites rarely reset all their data at once, so it is unclear how common this bottleneck is.
  • Weak baselines.
    • The only baseline explorer picks calls uniformly at random and finds almost nothing (at most 6 handoffs), even with real names, although simple exact name matching already reaches every target in that condition (App. B).
    • Missing comparisons such as
      • a greedy explorer that tries the most-likely handoff first (the paper admits it has not separated the information term from the success prior);
      • producer–consumer inference as used by REST API testers such as RESTler;
      • an LLM agent exploring the same world, which the paper also admits is missing. Minor:
  • Writing and presentation can be further refined.
  • Beta beliefs with information-gain selection are established method. The main contribution is downstream task analysis.
Questions for authors
  1. How does ICHNAEA compare with a greedy explorer that always tries the handoff with the highest predicted success, and with an LLM agent that explores the same world under the same call budget?
  2. Can the specificity probes, which are already computed, be used in the claim rule? Would that recover AppWorld accuracy with replay on?
  3. Is there a real suite where documentation leaves many handoffs unstated, where the benefit could actually be measured?
Reviewer_g1VmOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies agentic settings and formalizes the dependencies between tools as handoffs. It asks whether an agent can explore these inter-tool relationships and acquire useful knowledge before encountering any downstream task. To this end, the authors introduce ICHNAEA, an explorer that maintains a Beta belief over candidate handoffs and selects the tool calls whose outcomes are expected to be most informative. The approach is evaluated in synthetic environments and on AppWorld, and the results demonstrate its effectiveness.

Critical strengths
  1. The paper addresses an interesting and relevant research problem: modeling the relationships between tools and the useful knowledge underlying these relationships. This perspective is valuable for real-world, complex, multi-step agentic tasks, where effective tool composition is often critical to success.
  2. The synthetic tool worlds constructed by a procedural generator provide a controllable and low-cost experimental testbed. This design makes systematic experimentation and analysis more feasible.
Critical weaknesses
  1. The paper requires major revision in terms of clarity. Many parts of the method and experimental sections are difficult to understand. Additional figures would help illustrate the approach. Furthermore, the text and tables are poorly aligned in both placement and content, which hinders readability.
  2. The empirical evidence relies mainly on synthetic tool worlds, which makes the conclusions less convincing. The AppWorld experiments, the only evaluation in a realistic setting, are very limited in scope and discussion. A more thorough real-world evaluation is needed to support the paper's claims.
Questions for authors

N/A

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.
Composition Discovery in Tool Worlds by Active Exploration | acceptodds