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

Summary

Language-model agents may have access to libraries containing thousands of tools, but showing too many tools or ranking them only by request relevance can leave out the tools needed to produce intermediate inputs. This paper defines a tool menu as a short, ordered subset of available tools that an agent may call before execution. It introduces the state path, a pre-execution route from the observable request state to the desired outcome, and uses it as an execution prior for learning menus. The encoder models which tools are runnable in the current state, how their outputs satisfy later inputs, and which tool orders recur in training paths. A retriever selects an executable entry, missing-input producers, and the final action, while a reranker places producers before the consumers that depend on them. On ToolBench, the method raises online success from 0.737 to 0.898 and outperforms retrieval, reranking, generation, and routing baselines without changing the agent. The resulting menu covers more complete chains with 32 tools than the official list covers with 128. The improvement also persists across executor families with different model capacities. The authors provide code through the State-Path repository.