The failure mode: one missing tool kills the run

Tool-using agents fail in a specific way: if a multi-step task needs N tools and you expose N−1, the workflow quietly degrades or stalls.

The paper “Tool Recommendation for Multi-Step Agents: Finding Every Tool a Task Needs” studies this at realistic scale: a platform with about 8,200 tools whose definitions, taken together, exceed the context window of any model they evaluate 1. You literally cannot shove “all available tools” into the prompt.

Most production stacks today do one of:

  • Hard-code a small fixed tool list per agent / skill.
  • Expose a few dozen tools via a protocol server (e.g., an MCP-style catalog).
  • Offer a search endpoint backed by lexical ranking like BM25.

At 8k+ tools, all three break down:

  • Hard-coding loses coverage and requires constant manual curation.
  • A static MCP catalog for each agent leaks context window on just the docs.
  • Pure lexical search misses semantically relevant tools and is brittle to phrasing.

The authors’ core observation: for multi-step agents, tool recall at the *session* level is the constraint. A single miss on any required tool can cause failure, so you need a way to reliably find *all* tools a task might need, not just a best-guess shortlist.

What they build: a tool gateway with three calls

The paper introduces a deployed “Tool Recommendation” system designed as a gateway between agent and tools 1.

Rather than exposing thousands of tools directly to the agent, it exposes a fixed interface of three tools. Through that small surface, the agent can in principle reach the entire 8,200-tool catalog:

“a deployed system that gives an agent all of them, hundreds of times more than a typical MCP server exposes, through a fixed interface of three tools” 1.

Mechanically, the gateway:

  • Runs at the boundary between the agent and the backing services.
  • Executes each tool call under the end user’s own credentials.
  • Checks each call against:
  • the user’s consent for each service, and
  • the tools the agent is allowed to use 1.

That means the agent is no longer directly wired to “every tool”. It only talks to the recommender and whatever two other gateway tools are exposed; the gateway is responsible for:

  • Deciding which concrete tools are candidates for a given step.
  • Enforcing access control and consent.
  • Actually launching the selected tools on the user’s behalf.

Architecturally, this cleanly separates:

  • Reasoning: plan steps, decide “I need something that can do X”.
  • Tool discovery: resolve “X” into specific tools that exist now.
  • Execution + governance: run them with correct identity and policy.

Because the same three-tool interface works for all tasks, you avoid blowing up the prompt as your tool catalog grows.

How it behaves in a workflow

The paper does not spell out the exact signatures of the three gateway tools, but it does document the observable behavior of the system and how it is evaluated.

You can reason about usage in a typical multi-step agent loop like this:

  1. User issues a complex task

The agent starts a multi-step plan requiring several specialized tools scattered across the 8,200-tool catalog.

  1. Agent queries the gateway’s recommendation interface

Instead of having all tools baked into the prompt, the agent calls the recommender (one of the three gateway tools) with a description of the needed operation.

  1. Gateway searches across all tools

Internally, the gateway ranks tools and returns a candidate set. Tool definitions live *behind* the gateway; the agent does not see them all at once, only the subset it requested.

  1. Agent selects and calls specific tools

For each selected tool, the agent issues a call through the gateway. The gateway runs it under the end user’s credentials and enforces service-level consent 1.

  1. Session proceeds across multiple steps

Each new step that needs a new capability repeats the pattern: describe need → gateway recommends → agent chooses → gateway executes and checks consent.

The key behavior: the gateway can surface “hundreds of times more than a typical MCP server exposes” without changing the agent’s interface or exploding context 1.

For builders, the take-home is to treat “tool discovery” as a *service* in its own right, not just an initial hard-coded list embedded in the agent.

Evaluation: recall, cost, and token footprint

The authors evaluate Tool Recommendation both as a retrieval system and as part of end-to-end multi-step workflows 1.

1. Retrieval quality: ToolRet benchmark

On ToolRet, a public retrieval benchmark for tools, they report:

  • Tool Recommendation places every tool a query needs in the top 10, and
  • It does so 57% more often than BM25, described as “a lexical ranking that commercial tool search offers” 1.

They also note that Tool Recommendation “compares favorably with published systems up to nine times its size” 1. The paper does not detail the architecture of those baselines, only that they are larger as systems.

For your stack design, the performance implication is:

  • If you are currently doing off-the-shelf BM25 or similar keyword search over tool names and descriptions, you should expect systematically missing required tools for a chunk of queries; at least on ToolRet, a more specialized recommender recovers those missing tools significantly more often.

2. Multi-step workflows: Codex sessions

They test the impact on actual agents by pairing Tool Recommendation with Codex-based multi-step workflows:

  • In these workflows, the first recommendation from Tool Recommendation already covered every required tool in 93% of Codex sessions 1.

This statistic is crucial: the agent doesn’t need multiple recommendation iterations most of the time; it gets a complete tool set for the task in one shot. That directly reduces:

  • Number of back-and-forths between agent and tool catalog.
  • Latency and complexity in your orchestration.

3. Token and cost savings vs fixed tool lists

They also measure input token and cost savings versus a baseline where the agent gets a fixed list of 100 tools:

  • Against that 100-tool list, Tool Recommendation:
  • Cut input tokens by 17% with Codex, and
  • By 40% with Claude Code 1.
  • Across 14 runs, Tool Recommendation reduced the total bill in all 14, by up to 40%, with no change in task completion 1.

This matters operationally: trimming 17–40% of input tokens and up to 40% in end-to-end cost without hurting completion means:

  • You can expand your tool surface area dramatically without paying a proportional tax in prompt size or cost.
  • The gateway helps on both axes: better tool recall and lower usage bill.

From a production perspective, the message is blunt:

  • Static large tool menus are expensive and do not scale.
  • A recommender that yields a focused, per-task subset is enough to keep success rates and cuts costs measurably.

Where it fits in an agent stack

The paper positions Tool Recommendation as a gateway layer 1. In stack terms:

  • Above:
  • Planners, hybrid reasoning agents, or plain LLM tools that decide *what kind of operation* they need next.
  • Gateway:
  • Tool Recommendation plus two other gateway tools, acting as a single, fixed interface for tools.
  • User identity and consent enforcement.
  • Below:
  • Thousands of concrete tools—APIs, services, workflows—shielded behind the gateway.

If you already use an MCP-like server as a catalog, you can think of this as:

  • Leave the raw registry behind a boundary.
  • Expose only a compact “recommend and execute” API to the agent.
  • Let the gateway translate agent-level needs into registry-level tool selections.

This design also meshes with hybrid or latent reasoning architectures. Hybrid Reasoning Agents (HybridAgents), for instance, keep an internal latent reasoning mode while still “act[ing] through text” and preserving tool-integrated capabilities 2. Those agents report 35.5–54.7% token reduction and 2.7–3.7x cost savings through internal reasoning optimizations 2. Tool Recommendation hits a complementary bottleneck: the external action surface. You can:

  • Let the agent think more efficiently internally (Hybrid-style), and
  • Let it discover and access tools efficiently via a gateway (Tool Recommendation),
  • Without needing the agent to “know” about thousands of tools directly.

Design implications and trade-offs for builders

Even with limited implementation details, the reported behavior suggests concrete design moves for anyone building large-tool-surface agents.

1. Treat tools as a dynamic, searchable corpus

The core quantified insight is that you can’t fit all tool definitions in-context once you reach thousands of tools 1. That implies:

  • Tool definitions live *outside* the LLM context.
  • Tool discovery is retrieval, not prompt templating.

So, rather than:

system: You have access to the following 100 tools: ...

You move to:

agent: I need a tool that can do X with Y constraints.
gateway: Here are the 5 most relevant tools and how to call them.

With Tool Recommendation-like behavior, you then aim to:

  • Maximize the probability that all required tools are in the top-K (e.g., top-10) for the session, as they do on ToolRet 1.
  • Keep K small enough not to blow up context.

2. Centralize consent and execution at the boundary

The paper explicitly calls out that Tool Recommendation:

  • Executes every call under the end user’s own credentials, and
  • Checks each call against both user consent for each service and the tools the agent may use 1.

Design-wise, that means:

  • Your LLM never holds raw credentials for downstream services.
  • Policies about which tools are allowed for which users, teams or contexts live in one place: the gateway.
  • Auditing and logging are naturally centralized at this boundary.

For multi-tenant or compliance-sensitive environments, this is often the only viable pattern to scale tool counts safely.

3. Avoid static “kitchen sink” tool menus

The experiments comparing Tool Recommendation to a fixed 100-tool list show:

  • 17–40% fewer input tokens and up to 40% cheaper sessions with no change in completion 1.

Static large lists:

  • Waste tokens repeatedly describing irrelevant tools.
  • Create more room for the model to pick suboptimal or unauthorized tools.

Instead:

  • Keep the agent’s visible tool set lean and per-task via recommendation.
  • Shadow the full registry behind the gateway; let it expand unbounded without touching agent prompts.

4. Design for “first recommendation completeness”

In Codex multi-step workflows, the first recommendation from the system covered every required tool in 93% of sessions 1.

For your own gateway designs, you want the same property:

  • The first call to your recommender should almost always deliver a *complete* set of tools for the task.

Operational benefits:

  • Fewer recommendation-again loops.
  • Less fragility from the agent trying to “fix” missing tools mid-run.
  • Easier latency budgeting for user-facing flows.

You can structure your agent policies accordingly:

  • Early in the run, plan the whole workflow and call the gateway to get all needed tools at once, rather than discovering them step-wise.
  • Cache the returned subset and reuse their signatures across steps.

Why this matters now

As tool catalogs grow from tens to thousands, you run into three limits simultaneously:

  • Context window: you can’t describe everything in context 1.
  • Human curation: no team can hand-manage tool lists for every agent and tenant at that scale.
  • Governance: credential and consent management gets intractable if every agent holds direct keys to every service.

The Tool Recommendation work shows:

  • You can push all three concerns into a dedicated gateway recommender, keep your agent interface simple, and still get strong recall and cost behavior.

For builders shipping agentic systems today, this is less an algorithm novelty and more a systems blueprint:

  • Separate planning from tool discovery.
  • Separate discovery from execution and policy.
  • Use retrieval to bridge from the agent’s task language to the tool catalog.

What is not documented

From the available abstract and metadata, the paper does not document:

  • The exact API signatures or semantics of the three gateway tools.
  • The specific retrieval and ranking methods (e.g., embeddings, rerankers, model architectures) used inside Tool Recommendation.
  • Engineering details of the deployment (latency numbers, throughput, infra stack, failure handling).
  • How the 8,200 tools are organized, versioned, or updated over time.
  • Any safety or abuse-mitigation techniques beyond credential usage and consent checks.
  • How Tool Recommendation interacts with different agent frameworks beyond the reported Codex and Claude Code experiments.