Technical Summary: How Many Tools Should an LLM Agent See? A Chance-Corrected Answer

1. Problem Statement

Large Language Model (LLM) agents require a retrieval system to select a shortlist of candidate tools from a registry before the model attempts to execute a task. A critical design choice is determining the search depth $K$ (the number of tools presented). Current systems typically employ a fixed $K$ (e.g., showing the top 5 or 10 tools) regardless of query difficulty. This approach faces two conflicting challenges:

• Too few tools: The correct tool may be excluded from the shortlist, leading to immediate failure.
• Too many tools: The model struggles to identify the correct tool among excessive distractors, and token costs increase significantly (approx. 20k tokens for 100 tools).

There is no standard metric to evaluate whether a chosen depth $K$ is appropriate for a specific query or registry. Existing retrieval metrics (like $nDCG@K$) are designed for document retrieval and do not account for the specific constraints of tool selection, where the pool size is small (50–500 tools) and random chance plays a significant role in success.

2. Methodology

2.1 The Bits-over-Random (BoR) Metric

The paper introduces the Bits-over-Random (BoR) metric as a chance-corrected evaluation tool for search depth. BoR measures the system's success rate relative to the probability of success via random selection at the same depth.

• Formula: $BoR = \log_2(P_{obs} / P_{rand})$
  • $P_{obs}$: The observed success rate (fraction of queries where the correct tool is in the top $K$).
  • $P_{rand}$: The probability of including at least one relevant item by chance, calculated using the hypergeometric distribution. For single-tool queries ($R_q=1$), $P_{rand} = K/N$, where $N$ is the registry size.
• Interpretation:
  • $BoR = 0$: Performance is equivalent to random chance.
  • $BoR > 0$: Performance exceeds random chance.
  • Self-Pruning Property: As $K$ increases, $P_{rand}$ increases. Consequently, the reward signal (BoR) naturally decreases as the shortlist grows, even if $P_{obs}$ remains constant. This creates an intrinsic penalty for unnecessary depth without requiring engineered depth penalties.

2.2 Reinforcement Learning (RL) Formulation

The authors frame the selection of $K$ as a Markov Decision Process (MDP) to test the utility of the BoR metric:

• State: The agent observes the similarity scores of tools examined so far, the current depth $k_t$, registry size $N$, and the BoR ceiling.
• Action: Binary decision: STOP (present the current shortlist to the LLM) or CONTINUE (examine the next candidate).
• Reward:
  • If the agent stops and the correct tool is present: Reward = $-\log_2(P_{rand})$.
  • If the correct tool is not present: Reward = 0.
  • A small step cost discourages unnecessary exploration but does not encode a specific depth preference.
• Agents: The study uses deliberately simple agents (DQNs and tabular Q-learning) to probe the metric's properties rather than proposing a production architecture.

2.3 Baselines

The BoR approach is compared against:

1. Fixed-$K$: Presenting the top $K$ tools for all queries.
2. F1 Ablation: An RL agent trained with an F1-based reward ($F1 = 2/(K+1)$ when recall=1) to test if depth awareness alone, without chance correction, induces adaptive behavior.

3. Key Results

The evaluation spans three benchmarks (BFCL, MetaTool, ToolBench), multiple scorers (BM25, MiniLM, BGE), and registry sizes ranging from 20 to 3,251 tools.

3.1 Adaptive Depth vs. Fixed Depth

• BFCL (370 tools): The BoR agent achieved 90.3% coverage with an average depth of $K=7.4$, nearly matching the coverage of a fixed depth of $K=50$ (90.8%) while presenting 7x fewer tools.
• ToolBench (3,251 tools): A fixed depth of $K=5$ achieved higher aggregate coverage (64.7%) than the BoR agent (61.9%). However, the fixed baseline failed completely on "hard" queries (where the correct tool was ranked 6th–20th). The BoR agent adapted its depth to $K=5.7$ on these hard queries, recovering 16.7% of cases that fixed-$K$ missed entirely.
• MetaTool: The BoR agent demonstrated sensitivity to registry size and scorer quality. With a weak BM25 scorer, it expanded depth significantly ($K=80.7$) to compensate for poor ranking, whereas the F1 baseline remained shallow regardless of scorer quality.

3.2 Scorer Quality and Adaptation

The BoR reward signal adapts to the quality of the underlying scorer:

• With strong embedding scorers (MiniLM), the agent stopped early ($K \approx 1.4$) because the correct tool appeared at the top.
• With weak scorers (BM25 on MetaTool), the agent expanded the search ($K \approx 80.7$) to maintain selectivity, whereas the F1 baseline failed to adapt, stopping early and missing the correct tool.

3.3 Downstream Tool-Choice Validation

Using Claude Sonnet 4.6 on BFCL, the authors validated whether shorter, adaptive lists improve the LLM's ability to select the correct tool from the presented set:

• Choice Accuracy: When the correct tool was present, Claude selected it 93.1% of the time with the BoR agent's short lists ($K=2.2$), compared to 87.1% with a fixed $K=5$.
• Medium Difficulty: On queries where the correct tool was ranked 2nd–5th, the BoR agent improved choice accuracy to 76.8% versus 60.9% for fixed $K=5$.
• Conclusion: Reducing the number of distractors (distractor load) improves the LLM's decision-making accuracy, even if the aggregate "found" rate is slightly lower than a high fixed-$K$ baseline.

4. Significance and Claims

The paper claims the following contributions and significance:

1. First Chance-Corrected Metric for Depth: It introduces BoR as the first metric specifically designed to evaluate search depth in tool selection by correcting for the probability of random success, a factor often ignored in standard retrieval metrics.
2. Self-Pruning Reward: It demonstrates that BoR naturally provides a reward signal that decreases with depth, allowing an RL agent to learn optimal stopping points without engineered depth penalties.
3. Adaptive Efficiency: The study shows that adaptive policies can achieve coverage comparable to large fixed shortlists while significantly reducing token consumption and model confusion.
4. Diagnostic Utility: The metric can identify broken or weak scorers (e.g., when an agent is forced to search the entire registry to find a tool, indicating the scorer is ineffective).
5. Downstream Impact: It provides evidence that adaptive depth not only retrieves tools more efficiently but also improves the LLM's downstream ability to choose the correct tool by reducing cognitive load.

Limitations Acknowledged:
The authors note that BoR optimizes for selectivity rather than maximum recall; therefore, fixed-$K$ baselines can sometimes achieve higher aggregate coverage if a uniform depth happens to suffice for most queries. The RL agents used are simple probes, not production systems, and the evaluation focuses on whether the tool is presented, not on the correctness of the tool's execution arguments.