---
title: "Plan or Retrieve First? A Scale Study of Tool Discovery Architectures"
description: "Tool-augmented LLM agents must discover relevant APIs from large registries before planning, but finite context windows prevent injecting all tool definitions into a single prompt. Two competing architectures are Retrieve-then-Plan (RtP), which embeds the query and retrieves similar tools via nearest-neighbor search, and Plan-then-Retrieve (PtR), which first generates abstract tool stubs as retrieval queries. Evaluating on ToolBench with 46,984 API endpoints across 50 categories reveals a clear complexity-dependent crossover: RtP outperforms PtR on single-tool queries while PtR outperforms RtP on multi-tool queries. PtR’s stub-hallucination failure mode acts as a double-edged sword—on simple queries it abstracts away proper-noun signals, yet on complex queries it decomposes multi-faceted intent into functional sub-needs. PtR roughly doubles inference cost, which pays off on multi-tool queries but hurts on single-tool ones, motivating complexity-adaptive routing driven by RtP’s top-1 retrieval score."
---

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

[Apple](https://yomu.fyi/company/apple) · Oct 15, 2026

**Type:** Benchmark

## Summary

Tool-augmented LLM agents must discover relevant APIs from large registries before planning, but finite context windows prevent injecting all tool definitions into a single prompt. Two competing architectures are Retrieve-then-Plan (RtP), which embeds the query and retrieves similar tools via nearest-neighbor search, and Plan-then-Retrieve (PtR), which first generates abstract tool stubs as retrieval queries. Evaluating on ToolBench with 46,984 API endpoints across 50 categories reveals a clear complexity-dependent crossover: RtP outperforms PtR on single-tool queries while PtR outperforms RtP on multi-tool queries. PtR’s stub-hallucination failure mode acts as a double-edged sword—on simple queries it abstracts away proper-noun signals, yet on complex queries it decomposes multi-faceted intent into functional sub-needs. PtR roughly doubles inference cost, which pays off on multi-tool queries but hurts on single-tool ones, motivating complexity-adaptive routing driven by RtP’s top-1 retrieval score.

## Approach / What changed

Plan-then-Retrieve (PtR): the LLM first generates Abstract Tool Stubs (hypothesized function signatures describing needed capabilities) which then serve as retrieval queries against the registry.

## Takeaways

- A complexity-dependent crossover exists: RtP outperforms PtR on single-tool queries, while PtR outperforms RtP on multi-tool queries, consistent across retrieval budgets, registry sizes, and model families.
- PtR’s stub-hallucination (inventing plausible but non-existent API names) is a double-edged sword: it abstracts away proper-noun signals on simple queries but decomposes multi-faceted intent on complex queries.
- PtR’s extra discovery call roughly doubles inference cost, beneficial for multi-tool queries but wasteful for single-tool ones, motivating complexity-adaptive routing using RtP’s top-1 retrieval score as a zero-cost signal.

## FAQ

### When does PtR outperform RtP?

PtR outperforms RtP on multi-tool queries (both intra-category and cross-category) because its abstract tool stubs decompose multi-faceted intent into functional sub-needs that retrieve more relevant APIs.

### What is stub-hallucination in PtR?

Stub-hallucination is when the LLM invents plausible but non-existent API names during stub generation. It acts as a double-edged sword: harmful on simple queries by abstracting away proper-noun signals, but helpful on complex queries by breaking down intent.

### How does PtR's inference cost compare to RtP?

PtR's extra discovery call roughly doubles inference cost compared to RtP. This trade-off pays off on multi-tool queries but is wasteful on single-tool queries, motivating a complexity-adaptive routing approach.

**Tags:** [Agents](https://yomu.fyi/topic/agents), [API](https://yomu.fyi/topic/api), [LLMs](https://yomu.fyi/topic/llm), [RAG](https://yomu.fyi/topic/rag), [Tool Calling](https://yomu.fyi/topic/tool-calling)

- Source: [Apple](https://machinelearning.apple.com/research/plan-retrieve-tool-discovery)
- Source URL: https://machinelearning.apple.com/research/plan-retrieve-tool-discovery
- Ingested by Yomu: 2026-10-15T21:00:14.606Z

[Read original post](https://machinelearning.apple.com/research/plan-retrieve-tool-discovery)