Dynamic Tool Dependency Retrieval for Efficient Function Calling

The paper proposes Dynamic Tool Dependency Retrieval (DTDR), a lightweight method that leverages both initial queries and evolving execution contexts to model tool dependencies, significantly improving function calling success rates and efficiency compared to existing static retrieval approaches.

The Gist

Imagine you have a super-smart robot assistant (a Large Language Model, or LLM) that can help you do things on your phone, like "Send an email to my boss about the project" or "Book a flight to Tokyo."

To do this, the robot needs to know which "tools" (apps or functions) to use. But your phone might have thousands of tools installed. If you give the robot a list of all 5,000 tools every time you ask a question, it gets overwhelmed, confused, and slow. It's like trying to find a specific needle in a haystack the size of a mountain.

The Problem: The "Static" Librarian
Previously, researchers tried to solve this by giving the robot a "static" list of tools.

• The Old Way: You ask, "Book a flight." The robot looks at the list of all tools and picks the ones that sound like "flight" or "travel."
• The Flaw: This is like a librarian who only knows the book titles. If you ask for "a book about flying," they might give you a book about birds or a book about airplane engines, but miss the actual travel guide because the title didn't match perfectly.
• The Missing Context: The old methods didn't understand the story of what you were doing. If you just booked a flight, the next logical step is usually to "book a hotel." The old robot didn't know this connection; it just saw "hotel" as a random word.

The Solution: The "Dynamic" Detective (DTDR)
The authors of this paper propose a new method called Dynamic Tool Dependency Retrieval (DTDR). Think of this as upgrading the robot's librarian to a detective who follows the clues.

Here is how it works, using a simple analogy:

1. The Two-Clue System

Instead of just looking at your question (the "Query"), the new system looks at two things:

1. Your Question: "I need to book a flight."
2. What You Just Did: "I just searched for flights."

The detective knows that if you just searched for flights, the next tool you likely need is "booking," not "checking the weather." It builds a map of how tools depend on each other.

2. The "Smart Filter"

Imagine you are cooking a complex meal.

• The Old Way: The chef is handed a giant box containing every spice, vegetable, and utensil in the world. They have to dig through it every time they need salt.
• The DTDR Way: The chef has a smart tray.
  • If the recipe says "chop onions," the tray only slides out the knife and the cutting board.
  • If the next step is "sauté," the tray swaps the knife for a pan and oil.
  • The tray changes dynamically based on exactly what step you are on.

This is what DTDR does. It doesn't just show the robot a list of tools; it shows it a tiny, curated list of tools that are actually relevant right now, based on what you asked and what you've already done.

3. Why This Matters for Your Phone

The paper emphasizes that this needs to happen on your device (like your iPhone or Android), not in the cloud.

• Speed: Your phone has limited memory. Sending a list of 5,000 tools to the brain of the robot takes too much space and time. DTDR shrinks that list down to just 5 or 6 relevant tools.
• Accuracy: Because the robot isn't distracted by irrelevant tools (like "send a text" when you are trying to "book a flight"), it makes fewer mistakes.
• Efficiency: The paper found that this method made the robot 23% to 104% better at getting the job done compared to older methods.

The Two "Detective" Styles

The authors built two versions of this system to prove it works:

1. The Clustering Detective (DTDR-C): This one groups similar tasks together. If you ask about "travel," it looks at a group of past travel examples to see what tools were used next. It's like saying, "People who do this usually do that next."
2. The Linear Detective (DTDR-L): This one is a trained math model that learns the direct connection between "Question + History" and "Next Tool." It's like a super-fast pattern matcher.

The Bottom Line

This paper introduces a way to make AI assistants on your phone smarter, faster, and more accurate by teaching them to look at the whole story of what you are doing, not just the first sentence.

Instead of throwing the whole toolbox at the robot and hoping it picks the right hammer, DTDR hands the robot only the hammer it needs for the nail it's currently hitting. This saves battery, saves time, and gets the job done right the first time.

Technical Summary

1. Problem Statement

Large Language Models (LLMs) augmented with tool use (function calling) are increasingly used to automate complex tasks. However, deploying these agents on on-device environments (e.g., mobile phones) faces two critical constraints:

1. Efficiency: Strict memory and latency budgets require lightweight solutions.
2. Effectiveness: Agents must select the correct tools from large, heterogeneous sets without being overwhelmed by irrelevant options.

Current Limitations:
Existing retrieval methods for selecting tools suffer from two main issues:

• Static Inputs: Many rely solely on semantic similarity between the user query and tool descriptions (e.g., BM-25, embedding-based similarity). This ignores the dynamic context of the task execution.
• Limited Context: Others use static tool-dependency graphs based only on the immediately preceding tool call. This fails to capture multi-step dependencies and evolving task contexts, often leading to the retrieval of irrelevant tools or biasing the agent toward frequently called functions (e.g., repeatedly calling "get email address" when only one is needed).

These limitations introduce irrelevant tools into the prompt, degrading accuracy and increasing computational costs.

2. Methodology: Dynamic Tool Dependency Retrieval (DTDR)

The authors propose DTDR, a lightweight retrieval framework that conditions the tool selection process on both the initial user query ($q$) and the evolving execution history ($f_{0:t-1}$) of the plan.

Core Concept

Instead of retrieving tools based on a static snapshot, DTDR dynamically identifies a minimal, task-specific dependency subgraph. It models tool dependencies learned from demonstration trajectories to predict the most likely next tools given the current state of the plan.

Two Variants

The paper introduces two lightweight implementations of the retriever module $\omega(q, f_{0:t-1})$:

1. DTDR-C (Clustering-based, Unsupervised):

   • Uses a pre-trained embedding model to map queries to a K-Means clustering space.
   • For each cluster, it constructs a weighted tool dependency graph (an N-order Markov Chain) based on demonstration data.
   • Given a test query and history, it identifies the relevant cluster and traverses the graph to predict the next tools.
   • Parameters: Only depends on embedding size and number of clusters ($K$).

2. DTDR-L (Linear, Supervised):

   • Trains a simple 1-layer linear classifier on top of a frozen embedding model.
   • The input is the concatenation of the query and the function history.
   • It learns to predict the probability distribution of the next function directly.
   • Parameters: Depends on embedding size and the number of tools ($|F|$).

Prompt Encoding Strategies

To integrate the retrieved tools efficiently, the authors evaluate several In-Context Learning (ICL) strategies:

• Hard Masking: Completely removes irrelevant tools from the prompt, reducing token count significantly.
• Soft Masking: Keeps all tools but emphasizes the retrieved subset.
• Weighted Variants: Includes probability scores in the prompt.
• Finding: Weighted Hard Masking generally performs best, offering the best trade-off between accuracy and prompt efficiency, especially for smaller models.

3. Key Contributions

1. Novel Framework: Introduction of DTDR, the first method to explicitly condition tool retrieval on both the user query and the full history of tool calls, capturing multi-step dependencies.
2. Comprehensive Evaluation: A systematic benchmark against 5 categories of baselines (Random, Term-based, Embedding-based, Static Dependency, Learned Retriever) across four datasets (TinyAgent, TaskBench DailyLife, HuggingFace, Multimedia) and seven LLM backbones (Qwen 3 family, Gorilla-V2, GPT-4o).
3. Efficiency Analysis: Demonstration that DTDR significantly reduces prompt length (up to 72% reduction in variable tokens) while improving accuracy, making it ideal for on-device deployment.
4. Prompt Engineering Insights: Identification of Weighted Hard Masking as the superior encoding strategy for balancing reasoning capability and context window constraints.

4. Experimental Results

The authors evaluated DTDR against state-of-the-art baselines using Function Selection Accuracy (FSA) and End-to-End Success Rate (FCA).

• Retrieval Performance:

  • DTDR-L achieved the highest retrieval metrics (MRR: 0.93, F1: 0.55 on TinyAgent), outperforming static dependency retrievers by 50–100%.
  • DTDR-C also showed significant gains (MRR: 0.78) over static counterparts.
  • Static methods (like ToolNet or simple embedding similarity) failed to capture the dynamic nature of multi-step tasks.

• Downstream Task Accuracy:

  • Function Selection: DTDR-L improved FSA by 23% to 104% compared to the best static retrieval baselines.
  • End-to-End Success: On datasets with tool dependencies, DTDR improved end-to-end success rates by 300% to 600% compared to baselines without ICL, and 23% to 104% compared to the best retrieval baselines.
  • Small Models: On the Qwen 3 4B model, DTDR-L achieved performance comparable to or better than the No-ICL baseline on the massive Qwen 3 14B and GPT-4o models, effectively "bridging the gap" between edge and cloud models.

• Efficiency:

  • DTDR reduced total prompt length by up to 51% and the variable portion by 72% compared to methods using raw demonstrations or full tool sets.
  • This reduction is critical for on-device inference where prefill speed and memory are constrained.

5. Significance and Impact

• On-Device Viability: DTDR provides a mathematically grounded, lightweight solution for running complex agentic workflows on mobile devices without relying on cloud APIs.
• Dynamic Context Awareness: The paper proves that static tool graphs are insufficient for complex, multi-step tasks. Dynamic conditioning on history is essential for accurate function calling.
• Scalability: The method scales effectively across model sizes, allowing smaller, cheaper models to perform tasks previously reserved for large, expensive cloud models.
• Future Directions: The framework is adaptable to imperfect demonstrations, multimodal tasks (robotics), and evolving tool sets, positioning it as a foundational approach for next-generation on-device AI agents.

In summary, DTDR solves the "needle in a haystack" problem for on-device agents by dynamically narrowing the search space to only the most relevant tools based on the current task state, thereby drastically improving both accuracy and efficiency.