The Tool Menu as an Execution Prior: Teaching Agents the Right Order of Tool Calls

When Agents Face Thousands of Tools, Selection Matters More Than Capability

Large language models (LLMs) completing tasks by calling tools has become the core paradigm of modern agent systems. Yet real-world agents often face massive tool libraries containing thousands of APIs. How to filter out a genuinely useful subset from this enormous library before execution directly determines whether a task succeeds or fails.

A recent paper published on arXiv, "The Menu Is an Execution Prior: State-Path Tool Menus for Online Agents," introduces an insightful concept — the Tool Menu — and reframes it as an "Execution Prior." The results show that simply by optimizing how tool menus are constructed, online task success rates can be improved significantly from 0.737 to 0.898, without modifying the agent itself.

The Menu Is an Execution Prior paper diagram

A tool menu is a short, ordered subset of tools selected from the full available pool before the agent begins executing a task. The agent can only call tools that appear on this menu — much like giving a chef a streamlined ingredient list. Whatever isn't on the list simply can't be used.

Why Sorting by Request Relevance Isn't Enough

The dominant approach to menu construction today is sorting by request relevance: the system ranks tools by their semantic similarity to the user's request, placing the most relevant ones first.

This approach has a fatal blind spot. Multi-step tasks don't just need the tool that performs the "final action" — they also require a chain of prerequisite tools that produce the inputs for that final step, and those tools must appear in a usable order. For example, to "book a hotel in a given city," the final action is "place the reservation," but that first requires "look up the city ID" and "retrieve available hotel listings." Relevance ranking often surfaces the obvious "book" endpoint, but tends to miss or deprioritize the less conspicuous input producers, causing the execution chain to break.

The State-Path Framework: From Relevance Matching to Execution Path Planning

The Core Concept of a State Path

The paper introduces the concept of a state path — a route planned before execution begins, starting from an observable request state and arriving at a desired final outcome. This path describes which tools are needed, and in what order, to move from the current state to the goal state.

Building on this, the researchers propose the State-Path Tool Menu framework, whose core idea is to treat the menu itself as an "execution prior" over these execution routes. In other words, the menu is no longer just a collection of relevant tools — it encodes prior knowledge about how a task should be executed.

The Three Core Components of the Framework

The State-Path framework consists of three collaborating modules:

Encoder: Responsible for representing three types of critical information — which tools can run directly from the current state, how the outputs of those tools satisfy the input requirements of subsequent tools, and which call sequences recur across training paths. This gives the model an understanding of the "dependency graph" among tools.

Retriever: Ensures the menu covers three elements — an executable entry-point tool, producer tools that supply missing inputs, and the final-action tool. Rather than focusing solely on the end goal, it accounts for every link in the chain.

Reranker: Responsible for placing producers before consumers. This step is critical — inputs must be generated before they can be consumed, allowing the agent to execute the full chain successfully.

Experimental Results: 32 Tools Outperform 128

Significant Gains in Task Success Rate

On the widely used ToolBench benchmark, State-Path menus delivered impressive results:

Online task success rate improved from 0.737 to 0.898
Outperformed multiple baselines including retrieval, reranking, generation, and routing approaches
No modifications to the agent itself were required — gains came entirely from optimizing the menu

Efficiency Advantage: Fewer Tools, More Complete Coverage

Even more notable is the efficiency comparison: State-Path menus using just 32 tools achieved more complete execution chain coverage than the official tool list with 128 tools. This means the method dramatically reduces menu size while actually providing higher-quality execution support — a particularly significant advantage for agent systems constrained by context window limits or sensitive to API call costs.

Robust Generalization Across Models

Experiments also demonstrated that these success rate gains hold consistently across executor model families of varying capability and scale. This confirms that State-Path is not a model-specific trick, but rather a generalizable and transferable execution prior.

Practical Takeaways for Agent System Developers

The value of this research lies in its reframing of "tool selection" — a step typically treated as a retrieval problem — as an execution planning problem. Traditional relevance ranking is fundamentally static semantic matching, whereas State-Path introduces explicit modeling of tool dependencies and execution order, allowing the menu itself to carry knowledge about how to complete a task step by step.

For developers building complex agent systems, this insight is highly actionable: rather than simply expanding retrieval recall, it pays to more carefully model the input-output dependencies between tools. A "smarter" compact menu often outperforms a "more comprehensive" bloated one.

The research team has open-sourced their code at https://github.com/Met2348/State-Path — developers interested in the implementation details are encouraged to explore it further. As the agent tool ecosystem continues to grow, efficiently and accurately "stocking the pantry" for intelligent agents will be a decisive factor in real-world usability, and State-Path offers a direction well worth following.