Plan or Retrieve First? Apple's Study of How Agents Should Find Tools Among 47,000 APIs

How should an AI agent find the right tool when there are tens of thousands to choose from? Apple's new paper, Plan or Retrieve First? A Scale Study of Tool Discovery Architectures, tests the two obvious answers and finds that neither wins everywhere. Retrieving first is better for simple, single-tool requests. Planning first is better for requests that need several tools, but its extra call roughly doubles inference cost. The authors propose routing between the two by query complexity.

The paper is listed under EMNLP on Apple's research site and is on arXiv as 2610.19068. The page gives the direction of the results but no accuracy or recall figures, so the size of the crossover has to come from the paper. Here is what it says, why it matters for anyone wiring agents to MCP servers or large tool catalogs, and what to check.

Quick reference

Why tool discovery is now a real problem

A few years ago an agent had five tools and listed them all in the prompt. Now an agent can be connected to many MCP servers, each exposing a handful of tools, and registries run into the thousands. Stuffing every definition into context burns tokens and degrades choices. So most systems add a retrieval step: embed the user request, search an index of tool descriptions, and pass only the top matches to the model.

That is the dominant design, and Apple calls it Retrieve-then-Plan. It is cheap and fast, but it matches the user's words to tool descriptions. When a request is really several sub-tasks in one sentence, a single embedding of the whole query may not land near any of the tools needed. Our guide to what MCP is and the MCP roadmap show why registries are growing, and our list of the top open and closed-source MCP servers gives a sense of the catalog scale a single agent may face.

The two architectures

A hub with cables plugged into several tools, picturing an agent connecting to a registry of APIs

Retrieve-then-Plan (RtP). The query is embedded and approximate nearest-neighbor search returns the closest tools. The model then plans using only those. The advantage is that the user's own words, especially proper nouns such as product or service names, match tool descriptions directly.

Plan-then-Retrieve (PtR). The model first generates what the page calls Abstract Tool Stubs: hypothesized function signatures describing the capabilities it needs, without knowing whether they exist. Those stubs, not the raw query, are used to search the registry. This decomposes a complicated request into functional sub-needs, each of which can match a tool.

PtR has a known weakness: the model can invent plausible but non-existent API names. Apple finds that this cuts both ways, which is the heart of the result.

What Apple tested

The setup, per the page:

• Dataset: ToolBench, 46,984 unique API endpoints across 50 categories.
• Query types: single-tool (G1), intra-category multi-tool (G2) and cross-category multi-tool (G3).
• Retrieval budgets: k from 1 to 20 tools returned.
• Registry sizes: 1k to 47k APIs, so the study actually varies scale.
• Models: Gemini 2.5 Flash and gpt-oss-120b, one closed and one open-weight.

Varying the registry size is the useful part. Many tool-retrieval results are shown on a few hundred tools. Here the same question is asked as the haystack grows to 47,000.

The findings

A gripper choosing one tool from a tray, illustrating tool selection between retrieval and planning

A complexity-dependent crossover. RtP beats PtR on single-tool queries; PtR beats RtP on multi-tool queries. The authors report that this holds at every retrieval budget tested, across registry sizes, and for both model families. A result that survives all those axes is more believable than one tuned for a single setting.

Stub hallucination is a feature and a bug. On simple queries, stubs lose the proper-noun signals that RtP matches directly: if you ask for a named service, rewriting your request into a generic signature throws away the most useful clue. On complex queries, the same behavior is a benefit, because it splits a multi-faceted intent into separate functional needs.

The cost is real. PtR's extra discovery call roughly doubles inference cost. That is worth paying on multi-tool queries and wasteful on single-tool ones.

The proposal: route by complexity. The authors suggest complexity-adaptive routing, driven by RtP's top-1 retrieval score, which the pipeline already computes at no extra cost. The intuition is simple: if the best retrieved tool is a confident match, the request is probably simple and you can stop; if the top score is weak, the request is probably compound, and the planning step is worth its price.

What it means if you build agents

• Do not assume the default is right. If you run retrieval over a large tool or skill registry, test a planning-first variant on your multi-step tasks. The paper suggests you will see the biggest gains exactly where requests mention several things at once.
• Measure by query type. An average over all queries hides a crossover. Split your evaluation into single-tool and multi-tool slices before comparing architectures.
• Use the retrieval score as a cheap gate. A threshold on the top-1 similarity is a one-line router. Whether it works for your embedding model is something you would need to test; the page does not give a threshold.
• Watch cost, not just accuracy. A doubled inference bill is an architectural choice, and it should be spent only where it pays back.
• Security still applies. Dynamic tool discovery widens the surface that an attacker can poison: see our explainer on MCP rug pulls and tool poisoning for why a retrieved tool description should not be trusted blindly.

This is separate from, but complements, work on making each reasoning step cheaper. Another Apple paper from the same research site this month, selection-based structured reasoning, attacks per-turn cost; this one attacks the cost and accuracy of choosing tools. For tool-use robustness more broadly, see Agent Reflex on noisy MCP tool outputs. For how skills differ from tools, see what agent skills are.

A worked example (our illustration, not from the paper)

Imagine a registry with thousands of tools and two requests. The first: "What is the weather in Lisbon tomorrow?" The second: "Book me a train to Lisbon, find a hotel near the station, and tell me whether I need an umbrella."

For the first, retrieve-first is nearly perfect. The query embedding sits close to a weather tool description, the word "weather" and the city are both strong signals, and the model plans with one obvious tool in hand. Planning first would add a call that rewrites the request into a generic signature such as a forecast function taking a location and a date, throwing away nothing important here but paying double for no gain, and risking an invented name.

For the second, a single embedding of the whole sentence is a blend of train booking, hotels and weather. The nearest tools to that blend may be a travel aggregator that does none of these well. Planning first lets the model write three stubs, one per need, and retrieval then runs three focused searches. That is the decomposition benefit Apple describes. The stubs may still hallucinate a function that does not exist, but as search queries they only need to land near a real tool.

This is the intuition behind the crossover. It is also why the authors' proposed gate is sensible: a confident top-1 match signals the first kind of request; a weak one signals the second.

How to test this on your own agent

You can reproduce the spirit of the study without Apple's code:

1. Build an evaluation set with labels for which tools are needed, and tag each example as single-tool or multi-tool. Even 100 examples per slice is informative.
2. Implement both pipelines behind the same interface. For retrieval, use whatever embedding index you already have. For planning-first, prompt the model to emit a short list of hypothetical function signatures and search with each.
3. Sweep the retrieval budget from a handful to twenty and record whether the needed tools appear in the returned set.
4. Grow the registry. Add distractor tools until you are an order of magnitude past production size, because the winner can change with scale.
5. Log cost per query, including the extra model call, and compute accuracy per dollar for each slice, not just accuracy.
6. Try the router. Set a threshold on the top-1 similarity and send low-confidence queries to the planning path. Pick the threshold on a held-out split.

If your agents are mostly single-tool, the study suggests retrieval alone is a good default. If your users give compound instructions, expect planning-first to pay for itself, at roughly twice the model calls.

What the page does not say

• No recall or accuracy numbers, so the size of the crossover is unknown from the summary.
• No limitations section, and no code link.
• No threshold for the router, and no experiment of the router itself is described; it is presented as a direction.
• The evaluation uses ToolBench, whose APIs are a particular style of REST endpoint. Whether the crossover holds for MCP tools with richer schemas is an open question, in our reading.

Related reading

• Apple's selection-based structured reasoning for search agents
• What is MCP: the complete guide
• The new MCP roadmap
• Top 10 open and closed-source MCP servers
• MCP rug pulls and tool poisoning
• What are agent skills: the complete guide

Details are accurate as of October 15, 2026, based on Apple's research summary page. Read the arXiv paper for numbers.