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

arXiv: https://arxiv.org/abs/2610.19068 · HTML: https://mlsanity.com/paper/2610.19068/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Tool learning and function calling, one of 16 directions in LLM agents and tool use.
- Builds on 18 of its 20 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Placed in

- LLM agents and tool use / [Tool learning and function calling](https://mlsanity.com/agents/tool-learning-and-function-calling/)

## Builds on (most cited first, 18 of 18)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [Towards General Text Embeddings with Multi-stage Contrastive Learning](https://mlsanity.com/paper/2308.03281/) (2023)
- [Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity](https://mlsanity.com/paper/2403.14403/) (2024)
- [Large Language Models as Tool Makers](https://mlsanity.com/paper/2305.17126/) (2023)
- [MetaTool Benchmark for Large Language Models: Deciding Whether to Use Tools and Which to Use](https://mlsanity.com/paper/2310.03128/) (2023)
- [TaskBench: Benchmarking Large Language Models for Task Automation](https://mlsanity.com/paper/2311.18760/) (2023)
- [CRAFT: Customizing LLMs by Creating and Retrieving from Specialized Toolsets](https://mlsanity.com/paper/2309.17428/) (2023)
- [AnyTool: Self-Reflective, Hierarchical Agents for Large-Scale API Calls](https://mlsanity.com/paper/2402.04253/) (2024)
- [Re-Invoke: Tool Invocation Rewriting for Zero-Shot Tool Retrieval](https://mlsanity.com/paper/2408.01875/) (2024)
- [Advancing Tool-Augmented Large Language Models via Meta-Verification and Reflection Learning](https://mlsanity.com/paper/2506.04625/) (2025)
- [Beyond Single-Shot: Multi-step Tool Retrieval via Query Planning](https://mlsanity.com/paper/2601.07782/) (2026)
- [Tool Retrieval Bridge: Aligning Vague Instructions with Retriever Preferences via Bridge Model](https://mlsanity.com/paper/2604.07816/) (2026)
- [ToolFlood: Beyond Selection -- Hiding Valid Tools from LLM Agents via Semantic Covering](https://mlsanity.com/paper/2603.13950/) (2026)

## Abstract (arXiv)

Tool-augmented LLM agents discover relevant APIs from large registries before planning execution, yet finite context windows prohibit injecting all tool definitions into a single prompt. The dominant approach, which we term Retrieve-then-Plan (RtP), embeds the user query and retrieves similar tools via approximate nearest-neighbor search. We study an alternative Plan-then-Retrieve (PtR) paradigm in which the LLM first generates Abstract Tool Stubs (hypothesized function signatures describing needed capabilities) which then serve as retrieval queries against the registry. Evaluating on ToolBench (46,984 unique API endpoints, 50 categories) across single-tool (G1), intra-category multi-tool (G2), and cross-category multi-tool (G3) query subsets, we find a clear complexity-dependent crossover: RtP outperforms PtR on single-tool queries while PtR outperforms RtP on multi-tool queries. This crossover holds at every retrieval budget (k=1 to 20), is robust across registry sizes from 1k to 47k APIs, and is consistent across model families (Gemini 2.5 Flash and gpt-oss-120b). We characterize a stub-hallucination failure mode (the LLM invents plausible but non-existent API names) that acts as a double-edged sword: on simple queries PtR's stubs abstract away proper-noun signals that RtP matches directly, yet on complex queries the same mechanism decomposes multi-faceted intent into functional sub-needs. We further analyze token overhead and show that PtR's extra discovery call roughly doubles inference cost, which pays off on multi-tool queries but hurts on single-tool ones, motivating complexity-adaptive routing as a practical direction, one that can be driven by a zero-cost signal already present in the pipeline (RtP's top-1 retrieval score).