PaperlayerView exact revision on arXiv

Source-linked AI summary

The Menu Is an Execution Prior: State-Path Tool Menus for Online Agents

Bo Yan, Weikai Lin, Song Wang

arXiv:2609.09395v1cs.AI

TL;DR

Practical tool-using agents must choose short menus from libraries with thousands of interfaces, but relevance alone can omit or misorder prerequisites. The paper learns state-path menus that cover executable routes and order producers before consumers, raising ToolBench success from 0.737 to 0.898 without changing the agent. The approach also shows gains across evaluators and executor families, while relying on informative schema fields and recurring path relations.

  • Problem

    Tool libraries contain thousands of interfaces, but relevance-based menus can expose a final action without the prerequisite tools or usable order needed for multi-step execution.

  • Method

    State-Path Tool Menu encodes state and tool dependencies, retrieves complementary route roles, and reranks them so producers precede consumers before execution.

  • Results

    0.737 to 0.898: State-Path raises ToolBench success while keeping the online agent and call budget unchanged, with gains across evaluators and executor families.

  • Takeaways & Limitations

    The menu can serve as an execution prior that exposes more complete, runnable routes within a bounded pre-execution interface.

  • Takeaways & Limitations

    The constructor fixes one menu before execution and depends on informative input-output fields and recurring path relations, with sparse or corrupted histories degrading performance.

Abstract

from arXiv · show

Language models act through tools, yet practical agents face libraries containing thousands of interfaces. We introduce the tool menu as the short, ordered subset of available tools shown to an agent before execution. The agent can call only tools in this menu. Multi-step tasks require the final action and the prerequisite tools that create its inputs in a usable order. Current constructors rank tools by request relevance, which can surface the final action while omitting or delaying less obvious producers. We introduce the state path, a pre-execution route from the observable request state to the desired outcome, and propose State-Path Tool Menu to learn it. Our framework treats the menu as an execution prior over these routes. Its encoder represents which tools can run from the current state, how their outputs satisfy later inputs, and which orders recur in training paths. A retriever covers an executable entry, the missing-input producers, and the final action. A reranker then places producers before consumers. On ToolBench, our menu raises online success from 0.737 to 0.898 and outperforms retrieval, reranking, generation, and routing baselines without changing the agent. The State-Path menu also covers more complete chains with 32 tools than the official list covers with 128, and its success gain persists across executor families with different model capacities. Our code is at https://github.com/Met2348/State-Path.

1 Introduction

The paper frames the pre-execution tool menu as an ordered execution prior: it must expose a complete, runnable state path rather than merely relevant tools. State-Path Tool Menu learns these paths and preserves the agent and call budget while improving route coverage and online success.

  • ToolBench exposes more than 16,000 APIs, making small pre-execution tool menus necessary for practical agents.
  • The method keeps the online agent, execution loop, and original call budget unchanged while constructing the menu.
  • Relevance-based menus can surface a final action before prerequisite tools produce its required inputs.For receipt requests, the route may require retrieving the order, creating the receipt, and recovering the recipient address first.
  • A state path runs from visible fields through missing-input producers to the requested outcome, making route completeness explicit.The menu thereby acts as an execution prior before the first call.
  • State-Path Tool Menu encodes state compatibility and tool dependencies, retrieves complementary path roles, and orders producers before consumers.Its encoder uses request state, schemas, and training paths; the retriever selects 32 tools and the reranker orders them.
  • State-Path improves end-task success, complete-chain coverage, and executable entry across tool libraries, evaluators, and executor families.The paper attributes these gains to route coverage and ordering within the same menu budget.

2 Related Work

Related work spans tool-use agents, retrieval and routing methods, coverage-oriented selection, and adaptive planning. State-Path differs by exposing a dependency-aware route once before execution while leaving online updates to the agent or a later planner.

  • Tool-use benchmarks vary in scale and structure, including library-scale, stateful-execution, and multi-step evaluation settings.
  • Retrieval, reranking, generation, and routing methods improve which tools are selected or represented for a request.
  • COLT targets broader coverage but leaves selected tools unordered, whereas State-Path requires prerequisites to be reachable and displayed before consumers.
  • KELP scores evidence paths for factual context, while State-Path uses state and schema direction to assemble executable call sequences.
  • Adaptive planners update tool selection during execution, whereas State-Path studies the route exposed once before the first call.The two decisions can be combined: pre-execution construction supplies initial coverage and online planning can revise it after observations.
  • Table 1 compares method families by selected object, decision time, dependency signal, and whether execution updates the choice.

3 Methodology

State-Path Tool Menu constructs a pre-execution route by selecting complementary tools and ordering producers before consumers. Its encoder, retriever, and reranker use state compatibility, schema flow, and path precedence while leaving the online agent unchanged.

  • 3 Methodology: The framework addresses coverage and order failures by learning which tools form a complete route and how they should be displayed before execution.Coverage can omit bridge tools that create required inputs, while order can place consumers before their producers.
  • 3 Methodology: A state path is a pre-execution hypothesis about an executable chain from the visible request state to the requested outcome.It includes an entry tool, bridge producers, a target, and optionally a terminal action.
  • 3 Methodology: For the receipt example, LOOKUPORDER provides the entry, CREATERECEIPT and GETCUSTOMEREMAIL provide SENDEMAILRECEIPT’s inputs, and the sending tool is both target and terminal.The example separates textual relevance from executability because bridge tools determine whether the final action can run.
  • 3 Methodology: The encoder represents state compatibility, schema flow, and recurring path precedence to distinguish runnable entries and producer-consumer dependencies.These signals identify tools that can run now, produce later inputs, or follow recurring orders in successful trajectories.
  • 3 Methodology: The retriever selects 32 tools using route membership, marginal coverage, and redundancy so complementary path roles remain represented.Its marginal decoder updates uncovered roles and fields after each selection, preserving bridge producers even when their names poorly match the request.
  • 3 Methodology: The reranker orders the selected tools with entry, slot, precedence, and prefix-state scores, filling an 8-tool executable prefix before retaining 24 backups.It adds predicted outputs to the prefix state so early producers can make later consumers executable; the resulting menu is passed unchanged to the online agent.

4 Experiments

Experiments evaluate whether State-Path improves online agents by constructing more complete, executable, and ordered tool routes without changing the agent. Across benchmarks, evaluators, ablations, documentation settings, and executor families, results associate gains with route coverage and producer-before-consumer ordering.

  • Main results: State-Path solves 273 of 304 ToolBench tasks, raising online success from 0.737 to 0.898 against the official menu.Among 51 disagreements, State-Path wins 50 and loses 1 under the same evaluator.
  • Route properties: Complete-chain coverage rises by 19.4 points, early-entry coverage by 11.8 points, and executable-prefix coverage by 3.8 points.The 32-tool State-Path menu also exceeds the official 128-tool list in complete-chain coverage.
  • Failure analysis: State-Path preserves 223 official successes, adds 50, and loses 1; 38 additions lack a complete official chain or early entry.The remaining 12 additions produce an accepted answer only with the State-Path menu.
  • Evaluator stability: All 3 evaluators rank State-Path first, including when GPT-5.5 scores every method lower and keeps State-Path 4 points ahead of the strongest external row.GPT-4o-mini agrees with released GPT-3.5-turbo-16k decisions on 91% of 400 outputs.
  • Ablations: The complete method reaches 0.898, versus 0.773 for changing only candidate order or using one fixed path template.Its 12.5-point gain over either partial variant supports jointly learning route membership and request-specific order.
  • Path length: The coverage advantage grows from 7.2 points on 3–4-tool paths to 26.2 points on paths with at least 7 tools.The comparison holds menu width fixed at 32 tools.
  • Tool documentation: Adding structured input and output fields improves dependency-edge accuracy by 4.8 points and path-replay success by 5.0 points.Full descriptions match the structured-field condition on both measures.
  • Executor families: Paired success gains across three executor families are 16.1, 12.8, and 6.9 points, and all are positive.The same ToolBench tasks and official and State-Path menus are used for all three executors.

5 Conclusion

The conclusion presents the short tool menu as the pre-execution route an online agent can see, and State-Path constructs that route from state and tool dependencies. On ToolBench, the menu alone raises success from 0.737 to 0.898, with chain, entry, and prefix measurements linking recoveries to the proposed mechanism.

  • 5 Conclusion: State-Path encodes observable state and tool dependencies, covers required path roles, and places producers before consumers.The menu is fixed before execution while the online agent remains unchanged.
  • 5 Conclusion: 0.898 success versus 0.737 results from changing only the menu, with 49 additional recovered tasks.Chain, entry, and prefix measurements connect these recoveries to route visibility.

6 Limitations

State-Path fixes one menu before execution, so it does not perform observation-conditioned menu updates. Its effectiveness also depends on informative input/output fields and recurring path relations, especially in sparse or corrupted histories.

  • 6 Limitations: State-Path fixes one menu before execution, leaving observation-conditioned updates open.Future work can add online updates while retaining initial route coverage.
  • 6 Limitations: The constructor relies on informative input and output fields and recurring path relations, with gradual degradation under sparse or corrupted histories.The limitation motivates learning relation evidence in new or lightly documented libraries.

7 Ethics Statement

The experiments use public benchmarks, licensed models, and synthetic API tasks without personal data. Because improved route visibility can make harmful tool sequences easier to execute, deployment requires safeguards for consequential actions.

  • 7 Ethics Statement: The experiments use public research benchmarks, licensed models, and synthetic API tasks containing no personal data.This describes the evaluated setting rather than real-world deployment.
  • 7 Ethics Statement: Improved route visibility can make harmful tool sequences easier to execute when requests or tool libraries are unsafe.The paper calls for permission checks, sandboxed execution, and human review for consequential actions.
  • 7 Ethics Statement: The main comparison contains 304 released ToolBench tasks, with the execution wrapper, call budget, and evaluator fixed across menus.Every row presents a different ordered menu to the same execution agent.

A.1 Training and Test Inputs

The evaluation constructs each 32-tool menu before execution using only information available from training or the final request state, while holding the execution setup fixed across constructors.

  • Final-menu construction uses the request, observable state, tool schemas, and training-derived statistics, but not the target trajectory or evaluator decisions.
  • All constructors share the same Qwen2.5-72B-AWQ agent, deterministic decoding, execution handling, and binary ToolEval success measure.
  • Baselines either construct candidate menus independently or reorder a shared candidate pool, with every external baseline producing an ordered 32-tool menu before execution.

B Worked Examples for Method Objects

The receipt example shows how State-Path Tool Menu converts a visible starting field into an ordered route by identifying an entry, recovering missing producers, and placing the terminal action last.

  • The receipt request begins with only the visible order field, so the menu must connect that state to the final sending action.
  • Training paths place LOOKUPORDER before bridge tools and SENDEMAILRECEIPT after them.
  • State fit selects the starting action, schema flow recovers missing producers, and path precedence organizes the resulting menu.

C State-Path Implementation Details

State-Path Tool Menu models executable routes by combining state compatibility, schema dependencies, training-path relations, set selection, and prefix-aware reranking.

  • A relation-aware Transformer predicts route coverage and executable order from candidate-tool context, and a decoder converts those predictions into the ordered menu.
  • The encoder uses semantic, state, schema-flow, transition, and tool-family features computed before execution.
  • Directional relations encode neutral, dependency, shared-name, and shared-family links, with training transitions or schema flow establishing dependencies.
  • The retriever expands high-scoring anchors with training-path neighbors and selects tools using membership, path coverage, missing-field coverage, and diversity.
  • The reranker places an executable leading prefix of 8 tools, while the remaining 24 tools retain retriever order as backups.

D Complete Cross-Benchmark Results

Across benchmark comparisons, State-Path is evaluated as a pre-execution menu constructor under shared interfaces and scorers, with results covering task success, chain coverage, and evidence routing.

  • The reported comparison spans ToolBench, AppWorld, TRAJECT-Bench, and UniToolCall/ToolHop measures, with Table 15 collecting task and path results.
  • ToolACE reaches 0.297 on ToolBench success in the reported comparison.
  • On 304 ToolBench tasks, AutoTool, Dynamic Tool Dependency Retrieval, and ToolTree achieve complete-chain coverage of 0.592, 0.388, and 0.609, respectively.
  • AssistantBench compares routing policies with the same web cache, page budget, answer generator, and official scorer, changing only the routing policy.
  • 42.9 accuracy versus 23.4 for RankGPT yields 15 wins, 3 losses, and 15 ties for State-Path.
Loading 2609.09395v1…