🤖 AI

Learning to Recommend Multi-Agent Subgraphs from Calling Trees

This paper addresses the challenge of selecting reliable and compatible agents in expanding multi-agent marketplaces by proposing a constrained recommendation framework that leverages historical calling trees to optimize both individual agent and team-level subgraph selections through retrieval and utility optimization.

Original authors: Xinyuan Song, Liang Zhao

Published 2026-02-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xinyuan Song, Liang Zhao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive orchestra, but instead of musicians, you have thousands of digital "agents" (software tools) available to help you solve a complex problem. Some agents are great at math, others at writing, and some are excellent at talking to each other.

The problem is: There are too many choices.

As the paper explains, simply searching for an agent that sounds like it fits the job isn't enough. You might find three agents that all claim to be "good at math," but one is slow, one crashes often, and one is terrible at working with the other tools you've already picked. If you pick the wrong one, the whole orchestra falls out of tune.

This paper proposes a new way to pick the right team of agents. Here is the breakdown using simple analogies:

1. The Problem: The "Too Many Choices" Trap

Think of the marketplace of agents like a giant, chaotic flea market with millions of items.

Old Way (Retrieval): You ask a librarian, "I need a hammer." The librarian hands you the first 10 hammers they see. This is fast, but it doesn't tell you which hammer is the best for your specific project, or which one will break if you hit a nail too hard.
The Reality: In multi-agent systems, agents have to work together. Picking a "good" hammer is useless if the screwdriver you picked earlier doesn't fit the screw. The paper argues that current AI systems are too good at finding relevant items but bad at picking the right combination of items that work together smoothly.

2. The Solution: The "Two-Stage" Strategy

The authors suggest a "Two-Stage" approach, like hiring a headhunter for a job:

Stage 1: The Resume Filter (Retrieval)
First, you don't interview everyone in the world. You use a quick filter to find a small, manageable list of candidates who might be qualified. In the paper, this is called building a "feasible set." It's like saying, "Okay, we need a coder who knows Python and has worked on finance apps. Let's narrow it down to these 20 people."
Stage 2: The Deep Interview (Ranking)
Now, you look closely at those 20 people. You ask: "Who has the best track record? Who gets along with the rest of our team? Who is reliable?" The paper uses a "learning" system to score these candidates based on historical calling trees.

3. The Secret Sauce: "Calling Trees" (The Family Tree of Tasks)

This is the most unique part of the paper.

Old Data: Most recommendation systems (like Netflix or Amazon) look at flat lists: "User bought X, then User bought Y."
New Data (Calling Trees): The authors look at how agents actually talk to each other in the past. Imagine a family tree, but instead of parents and children, it's "Agent A called Agent B, which then called Agent C."
- This tree shows the structure of the work. It reveals who cooperated well, who caused a crash, and which teams formed a "perfect squad" to solve a problem.
- By studying these "trees," the system learns not just what to pick, but how to pick a group that fits together like a puzzle.

4. Two Ways to Play the Game

The paper offers two ways to use this system:

Agent-Level (The Soloist): "Pick the single best tool for this specific step." (e.g., "Find the best calculator for this math problem.")
System-Level (The Band): "Pick a whole team of tools that work together." (e.g., "Find a team of three agents: one to research, one to write, and one to fact-check, that have successfully worked together before.")
- The paper finds that picking the whole "Band" (System-Level) often works better because it ensures the tools are compatible from the start.

5. The Results: A Better Orchestra

The authors tested this on eight different collections of data (like a library of past projects).

The Outcome: Their "Two-Stage" system consistently picked better agents and better teams than the old "just search and pick" methods.
Why? Because it didn't just look for keywords; it looked at the history of cooperation. It knew that Agent A and Agent B were a "power couple" that always succeeded, while Agent C was a "lone wolf" that often caused the system to crash.

Summary

In short, this paper teaches AI how to be a better team manager. Instead of just grabbing the first tool that looks useful, it looks at the "family tree" of past projects to find the specific tools (or teams of tools) that have a proven track record of working together reliably. It moves from "finding a needle in a haystack" to "building a perfect team from the haystack."

Technical Summary: Learning to Recommend Multi-Agent Subgraphs from Calling Trees

Problem Formulation
The paper addresses a critical gap in Multi-Agent Systems (MAS) as agent marketplaces expand to contain thousands of heterogeneous agents. While existing recommender systems excel at ranking individual items based on flat user-item logs (e.g., e-commerce), they fail to address the structured, sequential, and interaction-dependent nature of agent orchestration. In MAS, selecting an agent is not a terminal decision but an intervention that alters the system state, induces dependencies, and affects the compatibility of subsequent choices. The core challenge is that many agents are functionally overlapping; thus, selection cannot be treated as a pure retrieval problem. An orchestrator must choose agents that are not only relevant but also reliable, compatible with the current execution context, and capable of cooperating with other selected agents. The paper formulates this as a constrained decision problem where the goal is to recommend either a single agent (Agent-Level) or a connected team of agents (System-Level/Subgraph) to execute a subtask.

Methodology
The authors propose a generic two-stage constrained recommendation framework grounded in historical calling trees (execution traces capturing parent-child calls, branching dependencies, and local cooperation patterns) rather than flat logs. The framework operates in two phases:

Feasibility Construction (Retrieval): A retrieval module filters the massive agent pool to build a compact, semantically relevant candidate set ( $A_{feasible}$ for agents or $G_{feasible}$ for agent systems) conditioned on the current subtask and context. This stage relies on off-the-shelf retrieval mechanisms (e.g., embedding similarity or LLM-based tool calling) to reduce the search space.
Utility Optimization (Reranking): Within the feasible set, a learned scoring model performs utility optimization to select the best option. This stage accounts for relevance, reliability, and interaction effects.

The paper defines two specific instantiations of this framework:

SARL (Single-Agent Recommendation Learning): Selects the next single agent/tool. It uses a parametric scoring function $s_\theta(t, a)$ that incorporates task query encoding, agent capability, graph-structured relations, historical reliability, and list-aware contextual effects.
ASRL (Agent-System Recommendation Learning): Selects a small, connected agent team (subgraph). It generalizes the decision unit to a group, using a scoring function $s_\theta(t, g)$ that aggregates collective capabilities, internal cooperation patterns, and structural suitability within the global graph.

Both models are trained using historical orchestrator traces, minimizing a loss function (e.g., softmax cross-entropy) over observed execution outcomes, with constraints ensuring the selected agent or system belongs to the feasible set.

Key Contributions

Problem Formulation: The paper identifies and formalizes agent recommendation in MAS as a constrained decision problem, highlighting the limitations of traditional item-level independence assumptions in multi-agent settings.
Unified Framework: It introduces a two-stage "divide-and-conquer" framework that separates feasibility construction from utility optimization, supporting both agent-level and system-level (subgraph) recommendations.
Structured Data Benchmark: The authors construct a unified calling-tree benchmark by normalizing invocation logs from eight heterogeneous multi-agent corpora (including Agent-data-protocol, GTA, MCPToolBench++, etc.) into a shared structured representation, enabling consistent evaluation.
Empirical Validation: Extensive experiments demonstrate that the proposed approach consistently outperforms strong baseline strategies (direct retrieval, cosine-similarity ranking, and single-pass LLM selection) in terms of Top-1 accuracy, stability, and execution coherence.

Results

Single-Agent (SARL): On six moderate-scale datasets, SARL (LLM retrieval + reranking) achieved superior Top-1 accuracy compared to direct retrieval and cosine-similarity baselines (e.g., 79.85% vs. 40.0% on Agent-data-protocol). The results indicate that while retrieval provides a strong candidate set, supervised reranking is crucial for resolving ambiguity and selecting the most reliable agent.
System-Level (ASRL): The ASRL approach achieved near-perfect Top-1 accuracy (100% on most datasets) across all benchmarks. The paper notes that graph-level retrieval yields higher recall and reduces semantic ambiguity compared to single-agent selection, allowing the learned ranker to identify the correct subgraph more reliably.
Scalability: Token complexity analysis shows that the two-stage design matches the big-O token cost of direct retrieval while offering significant performance gains, making it viable for large-scale agent pools where direct LLM scoring is computationally prohibitive.

Significance and Claims
The paper claims that effective multi-agent orchestration requires moving beyond isolated agent selection to reasoning over full subgraphs and leveraging call-tree supervision. By grounding recommendations in historical execution structures, the proposed framework enables the construction of coherent and executable agent teams rather than just compatible lists of tools. The authors assert that this approach significantly improves the reliability, coordination, and end-to-end execution quality of large-scale MAS.

The paper also includes an impact statement acknowledging potential risks, such as the amplification of biases present in historical logs (e.g., popularity bias) and the potential for reduced marketplace diversity. It suggests that practical deployments must include explicit safety, budget, and policy constraints within the feasible set to mitigate these issues.