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

1 Introduction

• Tool-augmented agents retrieve APIs under tight context constraints, and direct query embedding assumes user intent is close enough to API documentation for semantic search to bridge the gap.Prior work reports that this assumption often fails, motivating LLM-generated reformulations or plans before retrieval.Source: §1 · p. 1
• Prior work includes query rewriting, synthetic-query enrichment, decompose-then-select benchmarking, and efforts to treat stub hallucination as a bug (Ma et al., 2025).The paper instead reports that stub hallucination can be useful on complex queries.Source: §1 · p. 1
• The paper identifies a gap: prior work had not compared retrieval paradigms in a controlled large-registry setting or characterized how their trade-off changes with query complexity.The closest prior work, TOOLQP (Fang and Glass, 2026), uses trained, multiround query reformulations rather than zero-shot hypothetical function signatures.Source: §1 · p. 2
• The paper compares Retrieve-then-Plan (RtP) with Plan-then-Retrieve (PtR), which generates Abstract Tool Stubs as retrieval queries in a zero-shot call without training.It characterizes stub hallucination as a dual mechanism and reports a complexity-dependent crossover robust to retrieval budget, registry size, and model family.Source: §1 · p. 2

2.1 Architectures

• RtP retrieves top-k APIs by matching the embedded raw query to tool documentation, while PtR generates hypothetical tool stubs, retrieves and reranks their matched APIs, then plans with that set.Both use GTE-base embeddings, a FAISS flat index over 46,984 deduplicated ToolBench endpoints, and Gemini 2.5 Flash; retrieval budget is k=5.Source: §2.1 · pp. 2–3

2.2 Data and Metrics

• ToolBench evaluation uses G1 single-tool (n=200), G2 intra-category multi-tool (n=200), and G3 cross-category multi-tool (n=100) subsets, with retrieval measured against gold-trajectory APIs.Recall and precision are reported at k=5; PtR and pass rate are averaged over four runs, while deterministic RtP retrieval has no run-to-run variance.Source: §2.2 · p. 3
• The evaluation uses gold trajectories as a retrieval proxy because planners select from retrieved APIs at least 96% of the time, but it does not assess parameter correctness or final answer quality.An unfiltered baseline is infeasible because ToolBench categories include thousands of APIs and fixed-size truncation usually misses gold APIs.Source: §2.2 · p. 3, §2.1 · p. 3

3.1 Main Results

• G1 recall favors RtP (0.372 vs. 0.289±0.010), while G2 recall favors PtR (0.188±0.007 vs. 0.143); G3 recall favors PtR directionally (0.172±0.008 vs. 0.160).The G3 recall difference is not significant; G1 and G2 pass-rate results also favor RtP and PtR, respectively, while G3 pass rate favors PtR.Source: §3.1 · p. 4

3.2 Scaling Behavior

• PtR’s G2 recall advantage grows from +0.014 at k=1 to +0.066 at k=20, while the crossover holds across retrieval budgets and registry sizes from 1k to 47k APIs.Across registry sizes, recall degrades for both architectures but their G1 and G2 advantages persist; tool-selection divergence rises from 88% to 98%.Source: §3.1 · p. 4, §3.2 · p. 4

3.3 Agent Trajectory Divergence

• Trajectory fidelity is at least 96% across subsets, indicating that planners almost always select from retrieved tools; selected-tool Jaccard similarity falls from 0.40 on G1 to 0.28 on G3.On G3, PtR plans average 4.1 intended steps and 1.4 APIs named versus RtP’s 3.6 steps and 1.1 APIs; RtP refuses more often on G2 (47% vs. 27%).Source: §3.3 · pp. 4–5

4.1 Why the Crossover Occurs

• G2 recall advantage grows from +0.014 at k=1 to +0.066 at k=20 as PtR’s 2.4–2.5 stubs retrieve candidates for distinct functional sub-needs.G2 queries require a mean of 6.5 Ground-Truth APIs, compared with 5.2 on G1; at equal search width, RtP’s G2 recall is nearly identical, but its larger output halves precision.Source: §4.1 · p. 5

4.2 Stub Hallucination: The Mechanism

• PtR generates 79–99% unique stub names, and multi-stub coverage can favor G3 even though only 24.8% of G3 stubs match a relevant API.Correct and incorrect stub matches have virtually identical cosine similarity, such as 0.874 versus 0.872 on G1, leaving the embedding space unable to distinguish good routing from bad.Source: §4.2 · p. 5

4.3 Discovery as the Binding Constraint

• At least 96% trajectory fidelity shows planners almost always select retrieved APIs; on G3, PtR produces plans averaging 4.1 intended steps versus 3.6 for RtP.Figure 4 also tracks selection rate, plan complexity, cross-architecture Jaccard overlap, behavior after retrieval misses all Ground-Truth APIs, and trajectory fidelity.Source: §4.3 · p. 6, Figure 4 · p. 6
• PtR adds ∼75–104% token overhead and one sequential LLM round-trip; routing G1 to RtP and G2/G3 to PtR saves ∼16% of inference tokens without retrieval-quality loss.The discovery call changes recall by −0.072 on G1 and +0.042 on G2; for queries requiring 12+ APIs, iterative discovery may be necessary regardless of architecture.Source: §4.3 · pp. 6–7

5 Conclusion

• RtP wins on single-tool queries, while PtR leads on G2 recall by +0.045 (p<0.001, n=200) and directionally on G3 recall by +0.012 (n=100; not individually significant).The crossover holds across k=1–20 and registry sizes of 1k–47k APIs, and its directions replicate with gpt-oss-120b.Source: §5 · p. 7
• Stub hallucination can erase direct API-name signals on simple queries yet decompose multi-faceted intent on complex ones.The conclusion characterizes this as a double-edged effect of stub hallucination.Source: §5 · p. 7
• At least 96% trajectory fidelity makes retrieval the binding constraint, and complexity-adaptive routing reduces discovery-call overhead by ∼36% without retrieval-quality loss.The proposed routing sends single-tool queries to RtP and multi-tool queries to PtR.Source: §5 · p. 7

Limitations

• The comparison holds planner, embedding model, and benchmark fixed to Gemini 2.5 Flash, GTE-base, and ToolBench; generalization to differently named registries remains to be validated.An initial gpt-oss-120b replication confirms crossover directions across model families, not across registry types.Source: Limitations · p. 7
• ToolBench gold trajectories serve as a retrieval proxy, so parameter correctness and final-answer quality are not assessed; wall-clock latency depends on serving infrastructure.PtR’s sequential discovery and retrieval calls add one LLM round-trip before planning begins.Source: Limitations · pp. 7–8

A Full Retrieval Metrics Table

• RtP leads pass rate, retrieval precision, and retrieval recall on G1, while PtR leads all three metrics on G2 and G3.Pass rate is supplementary; the main text focuses on precision and recall as primary retrieval metrics.Source: A Full Retrieval Metrics Table · p. 10

B Stub Generation Statistics

• Stub names are 79–99% unique, while correct and incorrect matches have virtually identical cosine similarities of 0.874 and 0.872.The statistics indicate stubs are hallucinated from scratch and embeddings do not distinguish good routing from bad.Source: B Stub Generation Statistics · p. 10
• At k=5, PtR searches ∼2–2.5× more candidates than RtP before returning the top-k set to the planner.Table 5 defines PtR’s effective width as k×Stubs/q, using a deduplicated union; its caption also reports budget-equivalent RtP recall from Table 1.Source: B Stub Generation Statistics · p. 10, Table 5 · p. 10

C Trajectory Analysis Detail

• Trajectory divergence metrics are computed over paired queries with scorable responses from both architectures.Table 6 defines selection rate as the fraction of retrieved APIs used, Jaccard as overlap of selected API sets, and fidelity as selections drawn from the retrieved set.Source: C Trajectory Analysis Detail · p. 11, Table 6 · p. 11

• Divergence reaches 100% on G3, where the architectures retrieve entirely non-overlapping API sets for every query.Source: D Tool Selection Divergence · p. 11, Table 7 · p. 11
• On divergent G1 queries, RtP wins 63 to PtR’s 33, with mean recall 0.369 versus 0.294.Source: D Tool Selection Divergence · p. 11
• On divergent G2 queries, PtR wins 69 to RtP’s 30, with mean recall 0.184 versus 0.142.Source: D Tool Selection Divergence · p. 11

E Inference Cost Analysis

• PtR’s discovery call adds ∼175–200 output tokens per query; on G2, it yields +0.042 recall for +80% tokens, while G1 incurs higher cost and lower recall.Source: E Inference Cost Analysis · p. 11, Table 8 · p. 11

F Stub-Hallucination Examples

• On a G1 query containing a product brand, PtR’s stub abstracts away the name and gets zero recall while RtP gets perfect recall.Source: F Stub-Hallucination Examples · p. 12, Table 9 · p. 12

G PtR Win Examples (G1, G2, G3)

• For video-upload monitoring, two PtR stubs retrieve the correct APIs at recall 1.0, while RtP retrieves unrelated encoding tools at recall 0.0.Source: G PtR Win Examples (G1, G2, G3) · p. 12
• For a romantic proposal needing lines and Instagram media, PtR decomposes the request into two tools and reaches recall 1.0 versus RtP’s 0.5.Source: G PtR Win Examples (G1, G2, G3) · p. 12
• For a London trip spanning hotels, IP forensics, and currency, three PtR stubs reach recall 0.5 while RtP reaches 0.0.Source: G PtR Win Examples (G1, G2, G3) · p. 12
• For sharing a news article with a shortened URL, PtR covers three tools in the URL-shortening toolchain at recall 0.33, while RtP retrieves generic news APIs at 0.0.Source: G PtR Win Examples (G1, G2, G3) · p. 12

H G2/G3 RtP Win Examples

• For a Greece energy-news query, RtP matches “Greek” and “Energy” and reaches recall 0.5, while PtR’s general-news and football stubs reach 0.0.Source: H G2/G3 RtP Win Examples · p. 12

I Scaling Study Details

• The scaling study compares G1 and G2 recall across registry sizes; the RtP G1 and PtR G2 advantage holds at every tested size.Source: Table 10 · p. 13, I Scaling Study Details · p. 13

H G2/G3 RtP Win Examples

• For a New York craft-brewery query, RtP matches “brewery” and reaches recall 0.5, while PtR’s wrong decomposition reaches 0.0.Source: H G2/G3 RtP Win Examples · p. 13

J Model Generalization: gpt-oss-120b Replication

• With gpt-oss-120b, the G1 RtP and G2 PtR crossover replicates, while the small G3 recall gap reverses toward RtP.Source: Table 11 · p. 13, J Model Generalization: gpt-oss-120b… · p. 14

K Prompts

• The zero-shot discovery prompt elicits abstract tool stubs from the query alone; the planner prompt selects APIs from the retrieved set.Source: K Prompts · p. 14

L FAISS Index Configuration

• The index embeds each API’s tool name, API name, and description with 768-dimensional, L2-normalized GTE-base vectors for exact inner-product search.Source: L FAISS Index Configuration · p. 14