SYMPHONY: Synergistic Multi-agent Planning with Heterogeneous Language Model Assembly

AI summary

Overview

• Research area: Artificial intelligence / large language model (LLM) based autonomous agents; specifically LLM-guided Monte Carlo Tree Search (MCTS) planning and multi-agent collaboration.
• Technical level: Intermediate to Advanced. The paper assumes familiarity with MCTS, upper confidence bound (UCB) selection, Markov Decision Processes, and prompt-based LLM agents.
• Scope in one sentence: The paper introduces SYMPHONY, a multi-agent planning framework that replaces the single-LLM MCTS paradigm with a pool of heterogeneous language models coordinated by UCB scheduling, shared natural-language memory, and entropy-modulated confidence scoring, and evaluates it on HotpotQA, WebShop, and MBPP.

What This Paper Is About

Existing approaches that combine LLMs with Monte Carlo Tree Search generally rely on a single model, queried repeatedly with the same or slightly perturbed prompts, on the assumption that sampling variance alone will produce diverse search branches. In practice, the paper argues, those repeated calls produce highly similar outputs reflecting one dominant reasoning pattern, which narrows the search tree and pushes the planner toward local optima at high token cost. SYMPHONY addresses this by assembling several different language models into one planning system so that each search node is expanded by an agent with a different reasoning style, then coordinating those agents with adaptive scheduling, entropy-based value calibration, and shared failure reflections.

Key Contributions

1. A heterogeneous agent pool for MCTS. Rather than repeatedly querying one model, SYMPHONY maintains a collection of distinct language models M^(k) = {M_1^(k), ..., M_n^(k)} drawn from different pretraining sources and reasoning styles, assigning different agents to generate candidate actions at each search node to inject structural diversity into the search tree. The pool uses a uniform input-output interface P_φ(s_t, h_{t-1}) with φ in {expansion, evaluation, reflection}, so models can be added or removed without changing the core planning algorithm.
2. UCB-based adaptive agent scheduling. Agent selection at each rollout step is formulated as a structured multi-armed bandit problem using the canonical UCB expression UCB(M_i^(k)) = Q̄(M_i^(k)) + α · sqrt(ln N_total^(M^(k)) / (N(M_i^(k)) + 1)), where Q̄ is the cumulative average score and N the invocation count. This favors agents with either strong historical returns or low invocation frequency, balancing exploitation and exploration of reasoning modes.
3. Pool-wise memory sharing and entropy-modulated evaluation. When a trajectory fails, a UCB-selected agent produces a natural-language reflection R^k that is broadcast to the whole pool and inserted into every agent's prompt-level memory via Update(M^(k), R^k), with each agent keeping a fixed-size FIFO buffer. Node values are computed as R(s_t) = Z(s_t) · (1 − E(s_t)), where E(s_t) = −C(s_t) ln C(s_t) − (1 − C(s_t)) ln(1 − C(s_t)) is the Bernoulli entropy of the agent's confidence score C(s_t), treating confidence 0.5 as maximum uncertainty.
4. A theoretical and empirical case for model-level diversity. Theorem 1 ("Strict Improvement of Agent Pool Sampling") states that under correct coverage (at least one agent outputs the correct action at each step) and non-triviality (no single agent is correct on all steps), sampling agents with non-zero probabilities yields strictly lower expected error than any single deterministic agent.

Main Findings

• HotpotQA (multi-hop QA, exact match): SYMPHONY-L reaches 0.79 EM, above MASTER (0.76), Beam Retrieval (0.73), LATS (0.71), RAP (0.60), ToT (0.55), Reflexion (0.51), ReAct (0.39), CoT-SC (0.38), and CoT (0.34). SYMPHONY-S reaches 0.59, outperforming the linear-reasoning and feedback-driven baselines and performing comparably to RAP. The benchmark is described as containing approximately 113,000 question–answer pairs, evaluated under an oracle feedback setting.
• WebShop (sequential decision making): SYMPHONY-L scores 0.88 with a success rate of 0.72, above the Human Expert baseline reported at 0.82 score / 0.60 SR, and above MASTER (0.80), LATS (0.76 / 0.38), AgentKit (0.70), fine-tuning (0.68 / 0.45), Reflexion (0.64 / 0.35), IL+RL (0.62 / 0.29), IL (0.60 / 0.29), and ReAct (0.54 / 0.32). SYMPHONY-S scores 0.82 with SR 0.56. The environment is described as having over 1.18 million products and 12,000 natural language queries.
• MBPP (code generation, Pass@1): SYMPHONY-L achieves 0.965 in Python and 0.974 in Rust; SYMPHONY-S achieves 0.927 Python and 0.946 Rust. For comparison, AgentCoder is reported at 0.918 (Python), MASTER at 0.910, AgentVerse at 0.890, MetaGPT at 0.877, LATS at 0.811, GPT-4 at 0.800 (Python) / 0.710 (Rust), Reflexion at 0.771 / 0.754, RAP at 0.714, GPT-4(ReAct) at 0.710, and GPT-4(CoT) at 0.683.
• Branch diversity drives accuracy: With expansion width fixed at 4, increasing heterogeneity from single-agent to pairwise to full-trio configurations (e.g., Qwen + Mistral + Llama) substantially raises the share of 4-Unique expansions. On MBPP this proportion exceeds 80% under the full ensemble versus under 20% in the single-agent setting, and correlates with SYMPHONY outperforming single-agent baselines by over 30% on MBPP, with similar trends on HotpotQA and WebShop. Adversarial prompting and temperature scaling were tested as alternative diversity strategies and found to have only marginal effect.
• Search is more compact: On HotpotQA, SYMPHONY-S with K = 10 averages 16.39 node expansions and SYMPHONY-L averages 9.47, versus LATS at 28.42 (K = 10) and 66.65 (K = 50), RAP at 31.53 and 70.60, and ToT at 33.97 and 84.05. SYMPHONY uses K = 10 and n = 4, while LATS is described as using K = 50 and n = 5 on HotpotQA and WebShop.
• Cost reduction through heterogeneity: In SYMPHONY-L, GPT-4 is used in only 40% of calls, yet SYMPHONY-L still outperforms GPT-4-only baselines.
• Ablation confirms each component matters: Removing agent scheduling drops SYMPHONY-S from 0.59 to 0.51 on HotpotQA(EM), 0.56 to 0.48 on WebShop(SR), and 0.927 to 0.906 on MBPP(pass@1). Removing memory sharing causes the largest degradation: 0.45, 0.46, and 0.871 respectively. Removing EMCS gives 0.51, 0.49, and 0.892.
• Two deployment tiers behave as expected: SYMPHONY-S uses only open-source models runnable locally — Qwen2.5-7B-Instruct-1M, Mistral-7B-Instruct-v0.3, and Llama-3.1-8B-Instruct — while SYMPHONY-L uses GPT-4, Qwen-Max (2024-09-19), and DeepSeek-V3 (2025-03-24) through API endpoints. Each experiment was repeated 3 times on the same dataset and mean accuracy reported.

Methodology in Plain English

The researchers start from a standard planning setup in which an agent repeatedly picks actions, observes the result, and receives a reward, searching over possible action sequences with MCTS — a method that grows a search tree by trading off trying promising paths against trying unexplored ones. In prior LLM-based versions, one model supplies the candidate actions and the value estimates, so the tree tends to fill with near-duplicate branches.

SYMPHONY replaces that single model with a roster of different models. When the search reaches a node that needs expanding, a scheduler picks which model in the roster should act, choosing it with a UCB rule that rewards models that have historically produced good results and also gives airtime to models that have been used less. The chosen model proposes new candidate actions through an "expansion" prompt, and a similarly scheduled model scores the resulting node through an "evaluation" prompt, returning both a value estimate between 0 and 1 and a confidence score between 0 and 1. The confidence is converted into a Bernoulli entropy term, and the value is discounted by it — so a node the model is unsure about counts for less in the tree statistics.

When a full trajectory ends in failure, one scheduled model writes a natural-language reflection on what went wrong. That reflection is pushed into the prompt-level memory of every model in the pool, each of which keeps a fixed-size FIFO buffer of the most recent reflections. No model weights are updated; adaptation happens entirely through prompting. The authors also prove, under two stated assumptions, that sampling from the pool with non-zero probabilities has strictly lower expected error than deterministically using one model.

Evaluation covers three task types — multi-hop QA (HotpotQA), a simulated e-commerce environment (WebShop), and code generation (MBPP) — under a unified protocol with consistent prompt formats and fixed hyperparameters, and baselines reproduced by Gan et al. using GPT-4.

Why This Matters

Impact on research. The paper reframes rollout diversity as a model-level problem rather than a sampling-temperature problem, and provides both a proof sketch and a diversity measurement (the 4-Unique / 3-Unique / 2-Unique / 1-Unique categorization) linking heterogeneous model composition to accuracy. It also extends multi-agent LLM research away from rigid role-playing pipelines toward diversity-driven search, and it reports results in Rust, a language the paper notes previous work usually ignores.

Real-world applications:

• Customer-facing agents on consumer hardware: SYMPHONY-S shows that assembling several locally deployable open models can beat single-model baselines without cloud API spend.
• Cost-controlled deployments: Using GPT-4 in only 40% of calls in SYMPHONY-L while still beating GPT-4-only baselines points to a route for reducing inference bills on planning workloads.
• Code generation and repair: The MBPP Python and Rust results apply to automated programming assistants that must satisfy test suites.
• Web navigation and shopping assistants: The WebShop result applies to browser-operating agents that must satisfy multi-attribute user constraints across a large catalog.

Industry relevance. The cost and efficiency analysis — smaller search trees, fewer node expansions, and heterogeneous rather than uniform model usage — speaks directly to the economics of running LLM agents in production, and the modular agent-pool interface means models can be swapped as new ones become available.

Future Directions

• Extending SYMPHONY to unstructured or noisy environments, which the conclusion names as a primary next step.
• Reducing reliance on manually tuned hyperparameters, including the UCB exploration coefficient α and the MCTS parameters n and K, which the appendix sections G and H analyze.
• Integrating fairness and robustness considerations directly into the planning process.
• Developing more efficient memory architectures to support scalable, continual adaptation, building on the current fixed-size FIFO reflection buffers.

Target Audience

Researchers and engineers working on LLM-based agents, tree-search planning, or multi-agent orchestration who want a concrete design for replacing single-model rollouts with a coordinated heterogeneous pool. It is also relevant to practitioners who deploy planning agents under cost or hardware constraints, since the paper reports both a locally runnable configuration and an API-based configuration. Readers unfamiliar with MCTS, UCB, or the MDP formalism will need to consult the paper's Appendix C for the abbreviated MCTS description, as the main text assumes that background.

Authors’ abstract

Recent advancements have increasingly focused on leveraging large language models (LLMs) to construct autonomous agents for complex problem-solving tasks. However, existing approaches predominantly employ a single-agent framework to generate search branches and estimate rewards during Monte Carlo Tree Search (MCTS) planning. This single-agent paradigm inherently limits exploration capabilities, often resulting in insufficient diversity among generated branches and suboptimal planning performance. To overcome these limitations, we propose Synergistic Multi-agent Planning with Heterogeneous langauge model assembly (SYMPHONY), a novel multi-agent planning framework that integrates a pool of heterogeneous language model-based agents. By leveraging diverse reasoning patterns across agents, SYMPHONY enhances rollout diversity and facilitates more effective exploration. Empirical results across multiple benchmark tasks show that SYMPHONY achieves strong performance even when instantiated with open-source LLMs deployable on consumer-grade hardware. When enhanced with cloud-based LLMs accessible via API, SYMPHONY demonstrates further improvements, outperforming existing state-of-the-art baselines and underscoring the effectiveness of heterogeneous multi-agent coordination in planning tasks.