Dynamic Tool Discovery: A Systematic Evaluation of 8 Search Strategies for AI Agents

The proliferation of tools in AI agent systems creates a context bloat problem: providing an agent with 51 tools consumes 18,492 tokens per query. This study presents a comparison of 8 tool discovery strategies for dynamic tool discovery. We evaluated keyword-based methods (regex, BM25), semantic approaches (RAG with Pinecone, Milvus, cross-encoder), and hybrid fusion (BM25+RAG with RRF) across 100 queries in both one-shot and multi-turn conversation modes using GPT-4o-mini. For tools following recommended naming conventions, keyword methods (94% accuracy) matched or outperformed semantic search (93%) and hybrid approaches (90.5%). The best-performing dynamic strategy (regex) achieved 95% accuracy with 73% token reduction compared to the all-tools baseline (99% accuracy). Our results align with Anthropic's guidance on tool design: when tools follow recommended naming conventions (service-prefixed, action-suffixed), the naming itself provides sufficient signal for discovery, reducing the need for semantic understanding.

The Context Bloat Problem #

Modern AI agent systems increasingly rely on external tools to extend their capabilities beyond pure language modeling. Production systems now commonly integrate dozens to hundreds of tools spanning messaging (Slack), productivity (Calendar, Email), code management (GitHub, Jira), entertainment (Spotify), and more. However, this capability expansion creates a fundamental scalability challenge: context bloat.

In our experimental setup, providing an agent with 51 tool definitions consumes 18,492 tokens per query on average. At scale, this represents a three-fold problem:

1. Cost: At GPT-4o-mini pricing ($0.15/1M input tokens), processing 10,000 queries with all tools costs $28.35 versus $8.03 with optimized retrieval-a 3.5x cost multiplier.
2. Context competition: Tool definitions compete with actual conversation content, user instructions, and retrieved documents for limited context window space.
3. Cognitive load: LangChain's benchmarking found "a significant decrease in performance with increased context-size, even if that context was irrelevant to the target task."

This problem is not theoretical. Anthropic's production systems have encountered token budgets exceeding 134,000 tokens when managing extensive MCP (Model Context Protocol) tool collections.

Research Questions

This study addresses four research questions:

• RQ1: How do different retrieval strategies compare for tool discovery in terms of accuracy and token efficiency?
• RQ2: Does semantic search outperform keyword-based methods for tool retrieval?
• RQ3: Do hybrid approaches that combine lexical and semantic signals achieve better results than either method alone?
• RQ4: How does conversation context (multi-turn dialogues) affect retrieval performance?

Contributions

This work makes the following contributions:

1. Systematic comparison: The first rigorous evaluation of 8 retrieval strategies specifically for tool discovery, spanning keyword, semantic, and hybrid approaches.
2. Counter-intuitive evidence: Empirical demonstration that keyword-based methods outperform semantic search for tool retrieval, contradicting common assumptions in the RAG literature.
3. Hybrid paradox analysis: Investigation of why hybrid fusion underperforms its component methods, contrary to expectations from document retrieval research.
4. Practical recommendations: Decision framework mapping use cases to optimize strategies, grounded in quantitative trade-off analysis.

Related Works #

Tool Search in Production

Anthropic has introduced the Tool Search Tool pattern for managing large tool collections, reporting:

"This represents an 85% reduction in token usage while maintaining access to your full tool library. […] Opus 4 improved from 49% to 74%." – Anthropic

Their approach uses an LLM-in-the-loop architecture where the model itself generates search queries to discover relevant tools. This pattern inspired our investigation but differs from our focus on comparing retrieval algorithms.

Warnings Against RAG for Tools

Phil Schmid explicitly cautions against semantic retrieval for tool definitions:

"Fetching tool definitions dynamically per step based on semantic similarity often fails. It creates a shifting context that breaks the KV cache and confuses the model with 'hallucinated' tools that were present in turn 1 but disappeared in turn 2." – Phil Schmid

This warning informed our hypothesis that semantic approaches might underperform keyword methods for the structured, nomenclature-dense domain of tool definitions.

Multi-Agent Comparisons

LangChain's benchmarking of multi-agent architectures found that single-agent performance degrades significantly with increasing tool count, particularly when "distractor domains" introduce unrelated tools. Their findings suggest tool discovery is a critical bottleneck, though they did not systematically compare retrieval strategies.

Vstorm’s Methodology #

Experimental Setup

Experiment Configuration

All tools were mock implementations with realistic signatures and docstrings, simulating a production assistant with capabilities across Slack, Spotify, Calendar, Weather, GitHub, Jira, Email, Shopping, Contacts, Files, Documents, Notes, Reminders, Timezone, Translation, and Calculator domains.

Query dataset construction: 100 test queries were manually authored based on the available tool definitions. For each tool, we crafted example queries that a user might realistically give to an assistant, ranging from single-tool requests (e.g., " Check the weather in New York ") to multi-tool compositions requiring 2–3 tools in sequence (e.g., " Find the email about Q4 Planning, mark it as read, and reply "). Each query was annotated with expected tool(s) and a reference answer.

Search Strategies

We evaluated 8 strategies spanning three categories:

Strategy Implementations

Search Strategy Characteristics

Metrics

Primary metrics:

• Accuracy: Binary classification-did the agent call at least one expected tool?
• Total tokens: Sum of input and output tokens per query

Secondary metrics:

• Duration (seconds)
• API requests count
• Tool calls count

Statistical tests:

• Two-sample t-test for mean comparisons
• Mann-Whitney U test for non-parametric validation
• Cohen's d for effect size quantification

Tool Categories

The 51 tools were distributed across 16 categories:

Results #

Accuracy Analysis

One-Shot Accuracy Rankings

Key observations:

1. The baseline ( all_tools) achieved near-perfect accuracy (99%), establishing an upper bound.
2. Dynamic strategies ranged from 89% to 95% accuracy-a 4-10 percentage point gap from baseline.
3. Hybrid approaches ranked last among dynamic strategies, contradicting expectations that combining signals would improve results. Our hybrid implementation uses Reciprocal Rank Fusion (RRF): both BM25 and semantic search independently retrieve top_k × 3 candidates, then their rankings are merged using weighted 1/(k + rank) scoring with equal 50/50 weights. When the two rankers disagree—e.g., keyword correctly ranks documents_share first while semantic surfaces files_share —RRF averages the conflicting ranks, potentially demoting the correct tool below the top-k cutoff. We analyze this effect in detail in Section 5.2.
4. The simplest keyword method ( regex) tied for best dynamic performance despite minimal computational overhead.

Grouped bar chart comparing accuracy across one-shot and conversation modes for all strategies.

Token Efficiency

Token Usage Comparison

All dynamic strategies achieved 60-73% token reduction compared to baseline. The regex strategy was most efficient, using 3.7x fewer tokens than all_tools.

Stacked bar chart showing input/output token breakdown per strategy.

Statistical significance: The difference between all_tools and all dynamic strategies was highly significant (p < 0.001, Cohen's d > 1.3 "Large" effect size for all comparisons).

Statistical Significance (Token Comparison)

Strategy Type Comparison

Aggregating by strategy type reveals clear patterns:

Performance by Strategy Type (One-Shot)

Finding: Keyword (94.0%) > Semantic (93.0%) > Hybrid (90.5%)

This contradicts the assumption that semantic understanding of query intent would improve tool matching. Keyword methods' advantage likely stems from tool naming conventions that embed functional keywords directly in identifiers.

Side-by-side comparison of strategy types showing accuracy and token usage for one-shot vs conversation modes.

Scatter plot showing accuracy vs token cost trade-off, identifying the Pareto frontier.

Conversation Mode Impact #

We evaluated multi-turn conversations where context accumulates across 5 messages.

Context Growth Rate (Message 1 → Message 5)

Key insight: While dynamic strategies have higher relative growth rates, the absolute token counts remain substantially lower than baseline throughout the conversation. Growth is linear, not exponential.

Line chart showing cumulative token usage across conversation turns.

Accuracy by Message Position (Conversation Mode)

Line chart showing accuracy changes across conversation turns.

Accuracy Delta (Conversation – One-Shot)

Conversation mode had mixed effects: some strategies improved (milvus, regex) while others degraded (pinecone, hybrid_milvus). This suggests conversation context can either help (by providing disambiguation cues) or hurt (by introducing noise).

Waterfall chart showing accuracy changes between one-shot and conversation modes.

Horizontal bar chart comparing token overhead between modes.

Failure Analysis

Accuracy by Tool Category

Hardest Categories (Aggregated Across All Strategies)

Key insight on documents category : While overall accuracy is 81.2%, semantic methods (pinecone, milvus) achieve 100% accuracy compared to 75% for all other strategies. The critical difference appears on queries with naming ambiguity-for example, "Find the 'Design Mockups.fig' file" requires documents_list but non-semantic methods match files_search due to the word "file" in the query. This demonstrates that for categories with naming overlap (documents vs files), semantic understanding provides measurable benefit.

Implication: Tool naming conventions matter more than search algorithm choice. When tool names are unambiguous (e.g., slack_*, calendar_*), all strategies achieve near-perfect accuracy. The performance gap emerges only when semantic boundaries do not align with lexical signals.

Accuracy by Query Complexity

Performance vs Expected Tools Count

Multi-tool queries showed higher variance. The hybrid strategies degraded most severely on 3-tool queries (78.6%), while regex and cross_encoder maintained 100% accuracy.

Grouped bar chart showing accuracy breakdown by query complexity (1, 2, 3 expected tools).

Tool Discovery Rate

Full Discovery Rate by Strategy

False Positive Analysis

False Positive Rates by Strategy

Dynamic strategies consistently retrieved ~1.5 irrelevant tools per query (from top-k=5), but this did not significantly impact accuracy – the LLM correctly ignored irrelevant tools.

Most Frequently Retrieved False Positives:

The search_tools meta-tool dominates false positives (695 calls across all strategies), confirming that dynamic agents actively utilize the search capability ~7 searches per query across all strategies on average.

Worst-Performing Queries

Analysis of queries that failed across multiple strategies reveals systematic failure patterns:

Hardest Queries (Sorted by Failure Count)

Key failure patterns:

1. Naming collision: Queries containing "file" when documents_* tools are expected
2. Multi-tool complexity: 3+ tool queries have higher variance
3. Mock patterns: Non-standard workarounds (e.g. using notes_create to simulate shuffle) confuse retrieval

Strategic implications:

• all_tools baseline passes most edge cases (7/8 strategies failed → all_tools passed)
• Semantic methods (pinecone, milvus) uniquely pass the documents queries where keyword fails
• Cross-encoder shows robustness on complex Spotify queries despite being semantic

Discussion #

Why Keyword Beats Semantic

Three factors explain the counter-intuitive superiority of keyword methods:

1. Tools are designed artifacts with explicit nomenclature.

Unlike natural documents where concepts may be expressed in varied ways, tool names and descriptions are deliberately crafted with discoverable keywords: slack_send_message, calendar_schedule_meeting, spotify_play_track. These explicit signals favor exact matching.

2. Semantic similarity ≠ functional equivalence.

A query about "documents" is semantically similar to "files" and "notes," but these map to distinct tools with different capabilities. Semantic embeddings capture topical relatedness rather than functional boundaries, leading to cross-category confusion.

3. The "shifting context" problem applies to all dynamic strategies.

Phil Schmid warns about "shifting context" where "tools present in turn 1 disappear in turn 2," confusing the model. While he attributes this to semantic retrieval specifically, our data suggests this is inherent to any dynamic tool selection—keyword methods included. In conversation mode, bm25 degraded by -2pp and pinecone by -3pp, showing that both sparse and dense retrieval suffer when the available toolset shifts between turns. The fundamental issue is not the retrieval algorithm but the dynamic nature of the toolset itself.

The Hybrid Paradox

Hybrid approaches were expected to combine the precision of keyword matching with the recall of semantic search. Reality proved otherwise:

Observed: Hybrid (90.5%) < Semantic (93.0%) < Keyword (94.0%)

However, the paradox is nuanced. Per-query analysis reveals asymmetric behavior:

hybrid_milvus slightly outperforms milvus overall (92% vs 90%), likely because it wins more of the disagreement cases.

Hypothesis: Error amplification via RRF (applies primarily to hybrid_pinecone)

RRF assumes both rankers contribute complementary signals. However, when both rankers err in different directions, fusion produces a compromised ranking that inherits errors from both. In tool retrieval, where correct matches require high precision, this error blending is particularly harmful. Notably, RRF is rank-based and discards the original retrieval scores entirely—a different fusion method that incorporates score normalization or adaptive weighting could yield different results (see alternative architectures below).

Consider a query "share the budget document with Alice":

• Keyword search correctly ranks documents_share high
• Semantic search surfaces files_share and email_send (semantically related to "sharing")
• RRF fusion averages the ranks, potentially demoting the correct tool

Revised recommendation: For Milvus users, hybrid_milvus may be preferable to pure milvus despite lower aggregate accuracy, as it wins on more individual queries.

Alternative architectures to explore:

1. Learned weighting: Replace fixed 50/50 weighting with query-dependent weights learned from training data.
2. Cascade architecture: Use keyword search first, falling back to semantic only when keyword retrieval returns low-confidence results.
3. Query routing: Classify queries upstream and route to appropriate retriever based on query type (action-oriented → keyword, conceptual → semantic).

Practical Recommendations

Strategy Selection Guide

Cost Analysis at Scale:

Note on Embedding Costs: Pinecone/Milvus strategies incur additional OpenAI embedding API costs (~$0.13/1M tokens for text-embedding-3-large). At ~50 tokens per search query, this adds ~$0.0065 per 100 queries -negligible compared to LLM inference costs. However, for fully offline deployments, consider bm25 or cross_encoder which require no external APIs.

Cross-Model Cost Comparison:

The cost savings from dynamic tool discovery become even more significant with larger, more expensive models. Below we compare costs per 100 queries across four frontier models:

Model Pricing

Cost per 100 Queries by Model and Strategy

Savings from regex vs all_tools by Model

Cost Projection at Scale (1M Queries)

The savings scale linearly with model cost. For production deployments using Claude 3.5 Sonnet at 1 million queries, dynamic tool discovery saves approximately $40,700-making the optimization not just beneficial but essential for cost management.

Bar chart showing cost projection at scale (100 to 1M queries).

Normalized heatmap showing multi-metric performance profile.

Tool Design Guidelines

Our category accuracy analysis reveals that tool naming conventions impact retrieval accuracy more than algorithm choice. Categories with unambiguous names achieve 100% accuracy across all strategies, while ambiguous names ( documents, notes, files) cause systematic failures.

Recommended naming practices:

1. Use distinctive prefixes : Avoid semantic overlap between categories Bad: documents_list , files_list , notes_list (confusable)
2. Good: gdocs_list, dropbox_files_list, notion_notes_list (distinctive)
3. Embed action verbs in function names : Bad: get_user_info (vague)
4. Good: slack_lookup_user_profile (specific)
5. Include expected query keywords in descriptions:

def spotify_play_track(track_name: str): """ Play a song, music, or audio track on Spotify. Use this for: play music, start song, listen to track, queue audio """ ... Avoid synonyms across tool boundaries : If files_share exists, don't create documents_share Consolidate or use explicit disambiguation: files_share_link vs docs_grant_access When NOT to use dynamic tool search:

Limitations & Future Work #

Limitations

1. Mock tools: Our 51 tools were simulations with realistic signatures but no production API integrations. Real-world tool descriptions may vary in quality and consistency.
2. Single LLM: All experiments used GPT-4o-mini. Results may differ for Claude, Llama, or other models with different tool-calling behaviors.
3. Fixed top-k=5: We did not optimize the retrieval depth. Larger top-k might benefit semantic methods at the cost of more tokens.
4. English only: Tool names, descriptions, and queries were exclusively in English. Performance in multilingual settings is unknown.
5. Binary evaluation metric: Accuracy (any expected tool called) may not capture partial success in multi-tool scenarios where 2/3 required tools were correctly invoked.

Future Work

1. Adaptive retrieval: Dynamically adjust top-k based on query complexity or retrieval confidence scores.
2. Query expansion: Augment user queries with synonyms or LLM-generated paraphrases before retrieval.
3. Tool design study: Quantify the impact of naming conventions on retrieval accuracy. Does send_slack_dm outperform dm_user? What is the optimal description length?
4. Multi-model evaluation: Replicate experiments across Claude 3.5/4, Llama 3, Mistral, and other capable models.
5. Hybrid architecture variants: Evaluate cascade, routing, and learned-weighting alternatives to RRF fusion.
6. Confidence-based fallback: Detect low-confidence retrieval and automatically fall back to all_tools for specific queries.

Conclusion #

This study presents the first systematic comparison of retrieval strategies for tool discovery in AI agent systems. Our key findings:

1. Keyword methods outperform semantic search: regex/BM25 (94% avg) > RAG/Milvus/cross-encoder (93% avg) for tool retrieval—a result that may seem counter-intuitive given the general trend toward semantic approaches in information retrieval.
2. Hybrid fusion underperforms components: RRF-based hybrid (90.5%) ranked last among dynamic strategies, suggesting error amplification rather than complementary gains.
3. regex achieves optimal trade-off: 95% accuracy with 73% token reduction ($0.08 vs $0.28 per 100 queries).
4. Tool design matters more than search sophistication: Categories with naming ambiguity (e.g., documents vs files) showed the largest performance gaps between strategies, highlighting that clear tool naming conventions matter more than retrieval algorithm choice.

Practical advice: Start with keyword matching. Invest engineering effort in tool naming conventions rather than sophisticated retrieval pipelines. For most production systems, regex provides the best accuracy-cost trade-off while remaining trivially simple to implement and debug.