Skip to content

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

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

SYMPHONY integrates a heterogeneous pool of LLMs into Monte Carlo Tree Search (MCTS), replacing repeated single-model sampling with structurally diverse multi-agent rollouts. UCB-based agent scheduling, entropy-modulated confidence scoring (EMCS), and pool-wise natural language memory sharing together improve both search diversity and planning efficiency. The framework achieves state-of-the-art results on HotpotQA, WebShop, and MBPP while requiring fewer MCTS node expansions than prior methods.

Problem

Existing LLM-MCTS planning systems query a single model repeatedly to simulate diverse action branches, but in practice outputs converge due to shared inductive biases—producing low-diversity rollout trees that suffer from local optima, excessive token consumption, and failure on compositional multi-step tasks.

Method

SYMPHONY maintains an agent pool M = {M₁, …, Mₙ} of heterogeneous LLMs (e.g., Qwen2.5-7B, Mistral-7B, Llama-3.1-8B for the small variant; GPT-4, Qwen-Max, DeepSeek-V3 for the large). At each MCTS expansion step, a UCB bandit selects which agent to invoke based on cumulative rollout reward and invocation frequency (Eq. 1), balancing exploitation of high-performing agents with exploration of underutilized ones. Node value estimates are produced by a scheduled agent and modulated by EMCS: R(s) = Z(s) · (1 − E(s)), where E(s) is the Bernoulli entropy of the agent's confidence score C(s) ∈ (0,1), suppressing uncertain evaluations. When a trajectory fails, a UCB-selected agent generates a natural-language reflection that is broadcast to all agents and stored in per-agent FIFO buffers, enabling prompt-level behavioral adaptation without parameter updates.

Key Contributions

  • Heterogeneous agent pool: structurally diverse LLMs with varied pretraining and reasoning styles replace the single-model assumption in MCTS rollouts.
  • UCB-based agent scheduling: formulates agent selection as a multi-armed bandit, dynamically allocating agents by historical effectiveness.
  • Entropy-Modulated Confidence Scoring (EMCS): uncertainty-aware node evaluation that down-weights ambiguous value estimates using Bernoulli entropy.
  • Pool-wise memory sharing: decentralized failure reflections broadcast across all agents, enabling continual adaptation via prompt injection without retraining.
  • Theoretical justification: proof that ensemble sampling with non-zero probability over all agents yields strictly lower expected error than deterministic single-agent selection.
  • Practical efficiency: achieves comparable or better results with K=10 rollouts vs. LATS K=50; GPT-4 used in only ~40% of calls in SYMPHONY-L.

Results

  • HotpotQA (Exact Match): SYMPHONY-S 0.59, SYMPHONY-L 0.79 vs. MASTER 0.76, LATS 0.71, RAP 0.60.
  • WebShop (Score / SR): SYMPHONY-S 0.82 / 0.56, SYMPHONY-L 0.88 / 0.72 vs. MASTER 0.80 / — , LATS 0.76 / 0.38, Human Expert 0.82 / 0.60.
  • MBPP Python Pass@1: SYMPHONY-S 0.927, SYMPHONY-L 0.965 vs. AgentCoder 0.918, MASTER 0.910.
  • MBPP Rust Pass@1: SYMPHONY-S 0.946, SYMPHONY-L 0.974 (most baselines do not report Rust).
  • Search efficiency (HotpotQA): SYMPHONY-S uses 16.39 avg. nodes, SYMPHONY-L 9.47, vs. LATS (K=50) 66.65 and ToT (K=50) 84.05.
  • Diversity: full three-model ensemble yields >80% 4-Unique branches on MBPP vs. <20% for single-agent; correlates with >30% accuracy gain on MBPP.
  • Ablation: removing scheduling, memory sharing, or EMCS each reduces HotpotQA EM by 8–14 pp and WebShop SR by 7–10 pp.

Limitations

  • Hyperparameters (UCB α, expansion width n, rollout budget K) require manual tuning and may not transfer across tasks.
  • Pool-wise FIFO memory has fixed capacity; scaling to very long-horizon tasks or large reflection libraries is unaddressed.
  • Evaluation is limited to three benchmark tasks; generalization to unstructured, noisy, or open-ended environments is left as future work.
  • Diversity benefits are characterized only via output uniqueness counting; semantic diversity is not measured.
  • All baselines use GPT-4 as the backbone (from MASTER/Gan et al. reproductions), potentially masking fair model-controlled comparisons for SYMPHONY-S.

Relevance to Agentic AI / LLM Agents

SYMPHONY directly advances LLM-based planning by demonstrating that model-level heterogeneity—not just prompt variation or temperature scaling—is a primary driver of effective tree search. This is immediately relevant to agent systems that rely on MCTS or beam-style deliberation (RAP, LATS, ToT), showing a principled drop-in upgrade via multi-model ensembling. The UCB scheduling and pool-wise reflection memory provide reusable design patterns for any multi-agent system requiring dynamic resource allocation and experience sharing without gradient-based adaptation. The finding that a heterogeneous small-model pool (three 7–8B models on consumer GPUs) can match or exceed single large-model baselines has direct practical implications for cost-effective agentic deployments.