Plan or Retrieve First? A Scale Study of Tool Discovery Architectures

Who Should Read

Backend developer building agents that must pick tools from thousands of APIs and struggling with poor tool retrieval

Core Mechanics

• The winner depends on query complexity
  • Direct query retrieval (RtP) won on single-tool queries (G1).
  • Plan-first stub retrieval (PtR) won on multi-tool queries (G2, G3).
  • The direction held across k=1–20, registries from 1k to 47k, and two models (Gemini 2.5 Flash, gpt-oss-120b).
• PtR searches with fake tool stubs
  • The LLM sees no tool definitions and writes needed function names and reasons as JSON (Abstract Tool Stubs).
  • Each stub is embedded and searched against the real registry, then results go to the planner.
  • It needs no training, just one prompt call.
• Hallucination hurts simple queries and helps complex ones
  • When a query contains the API name or brand, the stub generalizes it away and misses.
  • For functional, multi-part queries, stubs split the intent into sub-needs that are each retrieved.
• PtR roughly doubles cost and adds latency
  • The discovery call adds 75–104% tokens.

Evidence

• RtP led on G1
  • On ToolBench G1 (n=200), recall was 0.372 for RtP vs 0.289±0.010 for PtR (p=0.002).
  • Pass rate was 0.884±0.015 vs 0.840±0.024 (p=0.022).
• PtR led on G2
  • On G2 (n=200), recall was 0.188±0.007 for PtR vs 0.143 for RtP (p<0.001).
  • Pass rate was 0.855±0.020 vs 0.747±0.015 (p<0.001).
  • Per-query wins were PtR 69 vs RtP 30.
• G3 recall was not significant
  • On G3 (n=100), recall was 0.172±0.008 for PtR vs 0.160 for RtP, not significant.
  • Pass rate was 0.820±0.014 vs 0.732±0.010 (p<0.001).
  • With gpt-oss-120b, G3 recall reversed toward RtP (0.160 vs 0.146, p=0.035).
• Routing cut discovery overhead
  • Sending G1 to RtP and G2/G3 to PtR cut PtR discovery-call overhead by about 36% and total inference tokens by about 16%.
  • On G2, PtR gave +0.042 recall for +80% tokens; on G1, -0.072 recall for +75% tokens.

How to Apply

• Split your tool queries into single-tool and multi-tool
  • Pull 50 queries from today's logs and label them by hand.
  • Mark whether the current top-5 results contain the correct tool.
  • Check the miss rate on multi-tool queries.
• Add a stub step only for multi-tool queries
  • Use the paper's discovery prompt to generate JSON stubs and embed each one separately.
  • Deduplicate, re-rank, and pass the top-k to the planner.
  • Compare recall against your current RtP.
• Route on RtP's top-1 similarity threshold
  • Log the top-1 cosine score and compare its distribution for single-tool and multi-tool queries.
  • Send high scores to RtP and low scores to PtR.
  • The paper did not validate this, so tune the threshold on your data.
• Keep proper nouns in stubs
  • Add an instruction to your stub prompt to preserve brand and API names from the query.

Try It

# Paste into Claude or ChatGPT: simplified version of the paper's PtR discovery prompt

You are a tool discovery assistant. Given a user query, identify what tools or APIs would be needed to answer it. You do NOT have access to any tool registry — instead, describe the tools you think are needed based on the query alone.
Respond ONLY with a JSON array:
[
{"tool_name": "hypothetical_tool_name", "reasoning": "why this tool is needed"}
]
Be specific about tool functionality. Use snake_case for tool names.

User query: {{query}}

Next step: use each tool_name as an embedding search query and compare against direct query retrieval.

Terminology

Related Papers

• Same Simulation, Different Evidence: Where Retrieved Tool Output Costs LLM Agents Accuracy

  Saving long tool output to files cut GPT-5.1 accuracy by 11.3 points; naming the authoritative file restored it.

• Fake News, Real Crashes: Information Injection Attacks on LLM Financial Trading Agents

  Fake headlines hijacked LLM trading agents 62% of the time versus 14% for prompt injection.

• Harness Engineering 101: The LLM is the brain, the harness is the body

  An agent is a loop managing a JSON array; 16 chapters build one from scratch

• Harness2 by Google Research – Recursive Agent Harnessing

  Recursively refining the harness with fixed model weights raised benchmark scores by up to 11.8 points.

• Ousted Savannah police officer gave ICE agent husband access to Flock system

  A police officer shared her Flock login with her ICE-agent husband; an audit found 983 searches and she was fired

• Tmux and Claude Code: Sessions, Send-Keys, and the Ceiling

  Running Claude Code agents in tmux works well, but limits appear around four agents.