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

Mingfei Zhang; Amit Surana; Ziauddin Majid; Chenxi Wang; Michael Xu

cs.AIOct 13, 2026

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

Authors: Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, Michael Xu

Organizations: Apple

Abstract

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

Figures & tables

Figure 1: Comparison of the two discovery architectures. Left (RtP) : the user query is embedded directly and matched against the tool registry via vector search; the top- $k$ results are passed to the LLM planner. Right (PtR) : the LLM first generates a draft plan with imaginary tool stubs, whose embeddings are used to query the registry; the matched real tools are returned to the planner for final execution planning.

Figure 2: Complexity-dependent crossover. (a) Both recall (solid) and precision (dashed) flip from RtP-dominant on G1 to PtR-dominant on G2/G3. (b) Per-query recall win/loss counts: RtP wins more queries on G1 (63 vs. 33); PtR wins more on G2 (69 vs. 30).

	G1		G2		G3
$k$	RtP	PtR	RtP	PtR	RtP	PtR
1	$\mathbf{.161}$	$.127$	$.065$	$\mathbf{.079}$	$.054$	$\mathbf{.075}$
3	$\mathbf{.307}$	$.223$	$.110$	$\mathbf{.148}$	$.105$	$\mathbf{.139}$
5	$\mathbf{.372}$	$.279$	$.143$	$\mathbf{.184}$	$.160$	$\mathbf{.177}$
10	$\mathbf{.453}$	$.356$	$.186$	$\mathbf{.234}$	$.217$	$\mathbf{.229}$
20	$\mathbf{.524}$	$.444$	$.229$	$\mathbf{.295}$	$.288$	$\mathbf{.299}$

Table 1: Recall at varying retrieval budget

k

. Bold : better architecture. Crossover holds at every

k

. Statistical significance of the RtP–PtR difference at

k{=}5

is reported in Table 3 .

Figure 3: Recall and tool selection divergence vs. registry size. Shaded bands show

\pm

std across 5 random seeds; the full-registry point (46,984 APIs) uses a single deterministic run. G1 (RtP advantage) and G2 (PtR advantage) recall curves are both shown; divergence grows monotonically with registry size.

Figure 4: Agent trajectory divergence across subsets: (a) selection rate = fraction of retrieved APIs the planner uses; (b) plan complexity = mean intended steps and APIs named; (c) Jaccard overlap of planner-selected API sets across architectures; (d) planner behavior when retrieval completely misses all Ground-Truth APIs; (e) trajectory fidelity = fraction of planner selections drawn from the retrieved set.

Query	PtR Stub(s)	Ground-Truth API	PtR R	RtP R
RtP wins: query contains the API name directly
“latest news about crime in Germany”	news_article_search_api	German Police and Crime News Live	0.00	1.00
“programming memes from Reddit”	reddit_api_client	Programming Memes Reddit/Get All	0.00	1.00
“electricity bill PLN analysis”	get_postpaid_pln_bill_details	Cek ID PLN/Get Data Tagihan	0.00	1.00
“Testing out Sharing w/ Rachael”	api_specification_retriever	Testing out Sharing w/ Rachael	0.00	1.00
PtR wins: query describes a capability; stubs bridge the semantic gap

Table 2: Representative queries illustrating the dual role of stub hallucination. Top : RtP achieves perfect recall when the query contains the API name directly; PtR’s generic stub abstracts away this signal and retrieves the wrong API. Bottom : PtR achieves higher recall when the query describes a functional need; stubs decompose multi-faceted intent into targeted sub-queries that RtP’s single embedding cannot match. “Ground-Truth API” is the ToolBench gold API for that query.

		RtP		PtR
Subset	Metric	Mean	$\pm$ Std	Mean	$\pm$ Std	$p$
G1 ( $n{=}200$ )	Pass Rate	$\mathbf{0.884}$	$0.015$	$0.840$	$0.024$	$0.022^{*}$
	Precision	$\mathbf{0.274}$	$-$	$0.209$	$0.008$	${<}0.001^{***}$
	Recall	$\mathbf{0.372}$	$-$	$0.289$	$0.010$	$0.002^{**}$
G2 ( $n{=}200$ )	Pass Rate	$0.747$	$0.015$	$\mathbf{0.855}$	$0.020$	${<}0.001^{***}$
	Precision	$0.167$	$-$	$\mathbf{0.204}$	$0.007$	$0.039^{*}$

Table 3: Retrieval metrics by subset (4 independent runs each). RtP precision and recall are deterministic (no run-to-run variance; reported without std).

p

-values: one-sample

t

-test for precision/recall (PtR’s 4-run mean vs. deterministic RtP); two-sample

t

-test for pass rate. Bold : best mean per metric.

{}^{**}p{<}0.01

{}^{***}p{<}0.001

, n.s. = not significant.

Subset	Gen.%	Stubs/q	Unique%	Match%	Cos
G1	98.5%	2.1	98.6%	40.6%	0.874 (correct) / 0.872 (incorrect)
G2	99.5%	2.4	93.6%	38.3%	0.843 / 0.840
G3	100%	2.5	79.1%	24.8%	0.858 / 0.854

Table 4: Stub generation statistics by subset. Gen.% : fraction of queries generating stubs. Stubs/q : mean stubs per query. Unique% : fraction of stub names unique across queries. Match% : fraction of stubs whose top-1 matched API is in Ground-Truth. Cos : mean cosine similarity of stub to its top-1 match (virtually identical for correct vs. incorrect matches).

Subset	Stubs/q	PtR eff. width	RtP eff. width	Budget-equiv. $k$	RtP recall
G1	2.1	${\approx}10$	5	10	0.453
G2	2.4	${\approx}12$	5	10	0.186
G3	2.5	${\approx}13$	5	10	0.217

Table 5: Effective search width at

k{=}5

. RtP searches exactly

k

candidates; PtR searches

k{\times}

Stubs/q (union, deduped) then returns top-

k

. Budget-equivalent RtP recall from Table 1 .

Metric	Arch.	G1	G2	G3
Selection rate	PtR	28.6%	28.2%	26.8%
Selection rate	RtP	26.7%	21.2%	22.4%
Jaccard (selected)	both	0.40	0.29	0.28
Plan steps	PtR	3.8	3.9	4.1
Plan steps	RtP	3.5	3.7	3.6
Fidelity	PtR	98.8%	97.8%	98.5%

Table 6: Trajectory divergence metrics. Selection rate = fraction of retrieved APIs the planner uses. Jaccard = similarity of planner-selected API sets. Fidelity = fraction of planner selections drawn from the retrieved set.

Subset	$n$	Identical	Divergent
G1	200	2.5%	97.5%
G2	200	1.0%	99.0%
G3	100	0.0%	100.0%

Table 7: Tool selection divergence: fraction of queries where the two architectures retrieve different top-

k

API sets.

	RtP	PtR	Overhead	$\Delta$ R
G1	${\sim}226$	${\sim}396$	$+75\%$	$-0.072$
G2	${\sim}238$	${\sim}429$	$+80\%$	$+0.042$
G3	${\sim}221$	${\sim}450$	$+104\%$	$+0.017$

Table 8: Inference cost and recall benefit of PtR over RtP. The sign of

\Delta

R matches the crossover in Table 3 , where the G1 and G2 recall differences are statistically significant (

p{<}0.01

) and G3 is not.

Query	PtR Stub	RtP Retrieved (correct)
“crime news in Germany”	news_search_api	German Police and Crime News Live
“programming memes, Reddit”	reddit_api_client	Programming Memes Reddit/Get All Memes
“PLN electricity bill”	get_pln_bill_details	Cek ID PLN/Get Data Tagihan
“Testing out Sharing w/ Rachael”	api_spec_retriever	Testing out Sharing w/ Rachael/Input test

Table 9: Stub-hallucination examples: PtR’s over-generic stubs miss niche APIs that RtP matches directly.

	G1 Recall		G2 Recall
Registry size	RtP	PtR	RtP	PtR	Div%
1,000	$\mathbf{.646}{\pm}.001$	$.586{\pm}.004$	$.339{\pm}.000$	$\mathbf{.366}{\pm}.000$	$88.4{\pm}0.0$
2,000	$\mathbf{.603}{\pm}.004$	$.544{\pm}.009$	$.300{\pm}.006$	$\mathbf{.336}{\pm}.005$	$89.2{\pm}1.2$
5,000	$\mathbf{.536}{\pm}.008$	$.470{\pm}.012$	$.249{\pm}.003$	$\mathbf{.294}{\pm}.004$	$92.5{\pm}1.1$
10,000	$\mathbf{.484}{\pm}.002$	$.414{\pm}.008$	$.215{\pm}.005$	$\mathbf{.260}{\pm}.003$	$94.1{\pm}1.2$
20,000	$\mathbf{.430}{\pm}.002$	$.357{\pm}.003$	$.184{\pm}.003$	$\mathbf{.226}{\pm}.003$	$95.6{\pm}0.8$

Table 10: Scaling study: RtP vs. PtR recall by registry size for the G1 (RtP-advantage) and G2 (PtR-advantage) subsets, with G1 tool-selection divergence (

\pm

std across 5 random seeds; full registry has no randomness). Bold marks the better architecture per subset: the crossover (RtP

>

PtR on G1, PtR

>

RtP on G2) holds at every registry size. The full-registry recall gaps are statistically significant on both subsets (Table 3 ). G2’s Ground-Truth set (1,048 APIs) exceeds the 1k target, so the smallest G2 point is gold-only (no distractors, zero variance).

	Precision		Recall		Pass Rate
Subset	RtP	PtR	RtP	PtR	RtP	PtR
G1	0.274	$0.186{\pm}0.006^{***}$	0.372	$0.259{\pm}0.012^{***}$	$\mathbf{0.855{\pm}0.018}$	$0.786{\pm}0.024^{**}$
G2	0.168	$\mathbf{0.207{\pm}0.004}^{***}$	0.143	$\mathbf{0.194{\pm}0.003}^{***}$	$0.826{\pm}0.029$	$0.820{\pm}0.029^{\text{n.s.}}$
G3	0.135	$0.123{\pm}0.008^{\text{n.s.}}$	0.160	$0.146{\pm}0.008^{*}$	$0.790{\pm}0.008$	$\mathbf{0.805{\pm}0.013}^{\text{n.s.}}$

Table 11: gpt-oss-120b replication (mean

\,\pm\,

std, 4 runs). RtP precision and recall are deterministic. Bold : better architecture (by mean). Superscripts on PtR values denote significance of the PtR–RtP difference (one-sample

t

-test vs. deterministic RtP for precision/recall; two-sample for pass rate):

{}^{*}p{<}0.05

{}^{**}p{<}0.01

{}^{***}p{<}0.001

, n.s. = not significant. The G1 (RtP) and G2 (PtR) crossover replicates and is significant on precision and recall; on G3 the differences are small and the recall gap weakly reverses toward RtP, indicating G3 behavior is model-dependent.

Tool Discovery for LLM Agents

See all 16 papers

Lookahead-R: Budget-Aware Tool Retrieval via Execution-Centric Planning
Sep 20, 2026Zongze Wu, Yani Guo, Runnan LiLLM Tool Use Tool-Augmented Language Model Agents
Beijing University of Posts and Telecommunications Beijing, China
Harness Engineering in LLM Tool Use via Agent-Native Reusable Tool Primitives
Sep 1, 2026Haibo Jin, Suijin Wang, Xucheng Yu +2Tool-Augmented Language Model Agents LLM Agent Orchestration
School of Information Sciences University of Illinois at Urbana-Champaign Champaign, IL 61820 · Independent Researcher Starc Institute
LLM Agents Already Know When to Call Tools -- Even Without Reasoning
May 10, 2026Chung-En Sun, Linbo Liu, Ge Yan +2Tool-Augmented Language Model Agents AI Agent Benchmarks
University of California, San Diego

Sep 20, 2026J/K move · Enter open · S save

Lookahead-R: Budget-Aware Tool Retrieval via Execution-Centric Planning

Zongze Wu, Yani Guo, Runnan Li

Beijing University of Posts and Telecommunications Beijing, China

LLM Tool Use Tool-Augmented Language Model Agents Tool-Use Planning

Open paper AskPDF arXiv

Tool retrieval is a critical bottleneck for LLM-based agents operating over large, heterogeneous API ecosystems. Existing approaches face an inherent trade-off: semantic retrievers are fast but suffer from the semantic-functional gap, while execution-based validation improves precision at the cost of prohibitive latency. We propose Lookahead-R, a planning-based framework that reformulates tool retrieval as a resource-constrained sequential decision-making problem. At its core, Lookahead-R introduces a lightweight execution-aware surrogate world model that jointly predicts tool execution success, latency cost, and semantic utility---without invoking real APIs. This world model drives a cost-sensitive, uncertainty-guided Monte Carlo Tree Search that navigates the tool space under strict budget constraints. Evaluated on the large-scale ToolBench benchmark, Lookahead-R achieves a superior accuracy-efficiency trade-off across all test scenarios. On the most challenging I3 split, it attains an NDCG@5 of 91.40%, outperforming the state-of-the-art ToolGen (90.16%) by 1.24%. Ablation studies confirm that explicit latency modeling is the key discriminative signal for identifying high-quality tools under resource constraints.

Abstract

Tool Discovery for LLM Agents

Explore similar work

Lookahead-R: Budget-Aware Tool Retrieval via Execution-Centric Planning

Harness Engineering in LLM Tool Use via Agent-Native Reusable Tool Primitives

LLM Agents Already Know When to Call Tools -- Even Without Reasoning