mlsanityData to 14 Oct 2026

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

arXiv 2610.19068 ↗First posted 13 Oct 2026cs.AI cs.IRcited by 0

On the map: LLM agents and tool use → Tool learning and function calling

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).

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.

Builds on

18 of 20 references.

Closest ancestors · 9

Same direction, newest first

  1. 2026Tool Retrieval Bridge: Aligning Vague Instructions with Retriever Preferences via Bridge Model9 Apr
  2. 2026ToolFlood: Beyond Selection -- Hiding Valid Tools from LLM Agents via Semantic Covering14 Mar
  3. 2026Beyond Single-Shot: Multi-step Tool Retrieval via Query Planning12 Jan
  4. 2024AnyTool: Self-Reflective, Hierarchical Agents for Large-Scale API Calls6 Feb
  5. 2023MetaTool Benchmark for Large Language Models: Deciding Whether to Use Tools and Which to Use4 Oct
  6. 2023ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs31 Jul
  7. 2023Large Language Models as Tool Makers26 May
  8. 2023Gorilla: Large Language Model Connected with Massive APIs24 May
  9. 2023Toolformer: Language Models Can Teach Themselves to Use Tools9 Feb

Other references · 9

  1. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  2. 2017Billion-scale similarity search with GPUscited by 2,497
  3. 2023HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Facecited by 1,190
  4. 2023Towards General Text Embeddings with Multi-stage Contrastive Learningcited by 723
  5. 2024Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexitycited by 451
  6. 2023TaskBench: Benchmarking Large Language Models for Task Automationcited by 144
  7. 2023CRAFT: Customizing LLMs by Creating and Retrieving from Specialized Toolsetscited by 129
  8. 2024Re-Invoke: Tool Invocation Rewriting for Zero-Shot Tool Retrievalcited by 52
  9. 2025Advancing Tool-Augmented Large Language Models via Meta-Verification and Reflection Learningcited by 24

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Lookahead-R: Budget-Aware Tool Retrieval via Execution-Centric Planning
  2. 2026SING: Synthetic Intention Graph for Scalable Active Tool Discovery in LLM Agents
  3. 2024Toolshed: Scale Tool-Equipped Agents with Advanced RAG-Tool Fusion and Tool Knowledge Bases
  4. 2025GRETEL: A Goal-driven Retrieval and Execution-based Trial Framework for LLM Tool Selection Enhancing
  5. 2026PlanBench-XL: Evaluating Long-Horizon Planning of LLM Tool-Use Agents in Large-Scale Tool Ecosystems
  6. 2026SchemaRouter: Field-Aware Tool Routing for Efficient Heterogeneous Agentic RAG
  7. 2026Semantic Tool Discovery for Large Language Models: A Vector-Based Approach to MCP Tool Selection
  8. 2025Dynamic Tool Dependency Retrieval for Lightweight Function Calling