Step-by-Step Teaching

Step 1: Understanding the Core Problem

Why Tool Discovery Matters

Modern LLM agents need to use external tools (APIs) to complete tasks. Imagine an agent that can access 47,000 different API endpoints — functions for weather, payments, databases, translations, and more.

The fundamental constraint:

LLM Context Window = LIMITED SPACE
Total API Definitions = ENORMOUS (47,000 endpoints)

Therefore: You CANNOT inject all tools into one prompt
Solution needed: Smart tool DISCOVERY before execution

Think of it like this:

A librarian cannot hand you every book in the library. They must first identify which books you need, then hand you only those.

---

Step 2: The Two Competing Architectures

Architecture 1: Retrieve-then-Plan (RtP)

The dominant/traditional approach

User Query
    ↓
[Embed query as vector]
    ↓
[Search tool registry via nearest-neighbor]
    ↓
Retrieved Tools → LLM Plans execution

How it works:

• Take the user's raw query
• Convert it to a numerical embedding (vector)
• Find the most similar tool definitions in the registry
• Feed those tools to the LLM for planning

Example:

User: "What's the weather in Paris?"
    ↓
Embed: [0.23, 0.87, 0.12, ...]
    ↓
Match: weather_api, forecast_tool, climate_data
    ↓
LLM uses weather_api to answer

---

Architecture 2: Plan-then-Retrieve (PtR)

The alternative approach studied in this paper

User Query
    ↓
[LLM generates Abstract Tool Stubs]
    ↓
[Stubs used as retrieval queries]
    ↓
Retrieved Tools → LLM Plans execution

Key new concept — Abstract Tool Stubs:

Hypothesized function signatures the LLM imagines it would need, before knowing what actually exists

Example:

User: "Book a flight and reserve a hotel in Rome for next week"
    ↓
LLM generates stubs:
  - search_flights(origin, destination, date) → FlightList
  - book_flight(flight_id, passenger_info) → Confirmation
  - search_hotels(city, checkin, checkout) → HotelList
  - reserve_hotel(hotel_id, guest_info) → Reservation
    ↓
Each stub searches the registry independently
    ↓
4 relevant real tools retrieved and used

---

Step 3: The Experimental Setup

ToolBench Dataset

The researchers tested on a real-world benchmark:

Three Query Complexity Levels

G1: Single-tool queries
    "Get the current Bitcoin price"
    → Needs 1 tool

G2: Intra-category multi-tool queries  
    "Compare flights and book the cheapest one"
    → Needs multiple tools FROM SAME category

G3: Cross-category multi-tool queries
    "Book a flight, reserve a hotel, and check weather"
    → Needs multiple tools FROM DIFFERENT categories

---

Step 4: The Key Finding — The Crossover Effect

The Central Result

Query Complexity:    Simple (G1)  →  Complex (G2, G3)
                         ↓                  ↓
Better Architecture:   RtP wins        PtR wins

This crossover holds across ALL tested conditions:

Visualizing the Crossover

Performance
    ↑
    |  RtP ────────\
    |               \──── RtP
    |                 \
    |          PtR ────\────── PtR
    |         /
    |────────/
    +─────────────────────────→
         G1          G2    G3
      (Simple)           (Complex)

---

Step 5: Understanding WHY — The Stub Hallucination Phenomenon

What is Stub Hallucination?

The LLM invents plausible but non-existent API names when generating stubs

Example of hallucination:

Real API exists:  "OpenWeatherMap_getCurrentWeather"
LLM stub invents: "get_current_weather(city, units)"
                   ↑ This doesn't exist, but sounds reasonable

The Double-Edged Sword

This hallucination is simultaneously a weakness AND a strength:

Why it HURTS on simple queries (G1):

User: "Search on TripAdvisor for Rome restaurants"
         ↑
    Proper noun signal: "TripAdvisor"

RtP embeds "TripAdvisor" → directly matches TripAdvisor API ✅

PtR generates stub: search_restaurants(city, cuisine)
    → Generic! Loses "TripAdvisor" signal
    → May retrieve wrong restaurant API ❌

Why it HELPS on complex queries (G2, G3):

User: "Plan a trip to Rome — flights, hotels, restaurants, weather"
         ↑
    Multi-faceted intent (4 different needs)

RtP embeds entire query → retrieves tools most similar to 
    the DOMINANT topic, misses others ❌

PtR generates 4 stubs:
  - find_flights(...)      → retrieves flight API ✅
  - search_hotels(...)     → retrieves hotel API ✅  
  - find_restaurants(...)  → retrieves restaurant API ✅
  - get_weather(...)       → retrieves weather API ✅

Key insight:

Stub hallucination decomposes complex multi-faceted intent into functional sub-needs — each sub-need can be matched independently

---

Step 6: Cost Analysis

Token Overhead

PtR requires an extra LLM call to generate stubs before retrieval:

RtP cost:  [1 retrieval call] + [1 planning call]
PtR cost:  [1 stub generation call] + [1 retrieval call] + [1 planning call]
                ↑
           Roughly DOUBLES inference cost

Cost-Benefit Analysis

---

Step 7: The Practical Solution — Complexity-Adaptive Routing

The Problem This Creates

Since neither architecture wins universally, what should a real system do?

The Proposed Solution: Adaptive Router

User Query
    ↓
[Complexity Detector]
    ↓              ↓
Simple?          Complex?
  ↓                ↓
Use RtP          Use PtR
(cheaper,        (more expensive,
 accurate)        but accurate)

The Zero-Cost Signal

Key practical insight from the paper:

RtP's top-1 retrieval score (already computed for free) can serve as the routing signal

High top-1 similarity score → Query is specific/simple → Stay with RtP
Low top-1 similarity score  → Query is vague/complex  → Switch to PtR

Why this is elegant:

• No additional computation needed
• The signal is already present in the pipeline
• Simple threshold decision

if RtP_top1_score > threshold:
    use RtP result  # Simple query, direct match found
else:
    invoke PtR      # Complex query, need decomposition

---

Step 8: Connecting to Related Work

How This Fits the Broader Landscape

Common thread across all:

Single-step retrieval with raw queries is insufficient for complex tasks — some form of query transformation or decomposition improves results

---

Summary: Complete Mental Model

┌─────────────────────────────────────────────────────┐
│           TOOL DISCOVERY DECISION FRAMEWORK          │
├─────────────────────────────────────────────────────┤
│                                                      │
│  Query arrives                                       │
│       ↓                                             │
│  [Check RtP top-1 score] ← zero cost signal        │
│       ↓                                             │
│  High score?          Low score?                    │
│  (Specific query)     (Vague/complex query)         │
│       ↓                    ↓                        │
│  Use RtP               Use PtR                      │
│  • Cheaper             • ~2x cost                   │
│  • Direct matching     • Stub decomposition         │
│  • Better for G1       • Better for G2/G3           │
│                                                      │
└─────────────────────────────────────────────────────┘

Five Core Takeaways

1. No single architecture wins universally — complexity determines the best approach
2. Stub hallucination is a feature, not just a bug — it enables intent decomposition
3. The crossover is robust — holds across models, registry sizes, and retrieval budgets
4. Cost scales with complexity — PtR's overhead only pays off on complex queries
5. Adaptive routing is the practical path forward — using existing signals, not new computation