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 is a multi-agent planning framework that replaces the single-LLM paradigm in Monte Carlo Tree Search (MCTS) with a heterogeneous pool of diverse language models. It introduces UCB-based agent scheduling, entropy-modulated confidence scoring, and pool-wise reflection memory sharing to improve rollout diversity and planning efficiency. It achieves state-of-the-art results on HotpotQA, WebShop, and MBPP across both small open-source and large API-based model configurations.

Problem

Existing MCTS-based LLM planners query a single model repeatedly, relying on sampling stochasticity to generate diverse action branches. In practice, outputs cluster around the model's dominant reasoning pattern, producing narrow, redundant search trajectories, susceptibility to local optima, and excessive token consumption—particularly on compositional or multi-step tasks.

Method

SYMPHONY maintains a heterogeneous agent pool \(\mathcal{M}^{(k)} = \{M_1^{(k)}, \ldots, M_n^{(k)}\}\) of LLMs with distinct pretraining sources and reasoning styles. Four core mechanisms integrate with standard MCTS (select → expand → simulate → backpropagate):

  1. UCB-based agent scheduling: Agent selection at each MCTS node is treated as a multi-armed bandit. Each agent \(M_i^{(k)}\) receives a score: $\(\text{UCB}(M_i^{(k)}) = \bar{Q}(M_i^{(k)}) + \alpha \sqrt{\frac{\ln N_{\text{total}}^{\mathcal{M}^{(k)}}}{N(M_i^{(k)}) + 1}}\)$ This balances exploitation of high-performing agents with exploration of underused ones.

  2. Pool-wise memory sharing: On trajectory failure, a UCB-selected agent generates a natural-language reflection \(R_k^i\), which is broadcast to all agents and incorporated via prompt-level FIFO memory buffers—enabling behavioral adaptation without parameter updates.

  3. Entropy-Modulated Confidence Scoring (EMCS): Node value estimates are down-weighted by the Bernoulli entropy of the agent's confidence \(C(s_t)\): $\(R(s_t) = Z(s_t) \cdot (1 - E(s_t)), \quad E(s_t) = -C(s_t)\ln C(s_t) - (1-C(s_t))\ln(1-C(s_t))\)$ This suppresses uncertain node evaluations and stabilizes backpropagation.

  4. Uniform interface: All agents share identical prompt templates for expansion, evaluation, and reflection phases, enabling modular addition/removal of models without altering the planner core.

Key Contributions

  • Heterogeneous multi-LLM pool replacing single-model MCTS; theoretically proven to yield strictly lower expected error than deterministic single-agent selection.
  • UCB-driven adaptive agent scheduling formulated as a structured multi-armed bandit problem embedded in MCTS rollout.
  • Pool-wise decentralized reflection memory enabling cross-agent knowledge transfer via prompt injection without fine-tuning.
  • EMCS: uncertainty-aware node evaluation using Bernoulli entropy to modulate value estimates in real time.
  • Empirical demonstration that model heterogeneity (not just count) drives branch diversity, with 4-Unique branch proportion exceeding 80% on MBPP under full trio vs. <20% single-agent.

Results

HotpotQA (exact match): - SYMPHONY-S: 0.59; SYMPHONY-L: 0.79 vs. MASTER (best prior): 0.76, LATS: 0.71

WebShop (score / success rate): - SYMPHONY-S: 0.82 / 0.56; SYMPHONY-L: 0.88 / 0.72 vs. MASTER: 0.80 / —, LATS: 0.76 / 0.38

MBPP Python Pass@1 / Rust Pass@1: - SYMPHONY-S: 0.927 / 0.946; SYMPHONY-L: 0.965 / 0.974 vs. AgentCoder: 0.918 / —, MASTER: 0.910 / —

SYMPHONY-L sets new SOTA on all three benchmarks; SYMPHONY-S is competitive with or exceeds prior structured search methods despite using only consumer-grade 7–8B models.

Limitations

  • Evaluation limited to three tasks; generalization to other domains (e.g., robotics, long-horizon planning) is unverified.
  • The paper does not report wall-clock latency or API cost comparisons—coordinating multiple API-based LLMs in SYMPHONY-L may incur substantial cost overhead.
  • Memory buffer uses a simple FIFO eviction policy; no analysis of memory quality or staleness effects.
  • Theoretical lower-error guarantee (Appendix B) assumes agents have non-zero independent error rates; no empirical validation of this assumption across models.
  • Baseline comparisons rely on results reproduced by a single prior paper (Gan et al. [12]), introducing potential confounds.

Relevance to Harnesses / Meta-Harnesses

SYMPHONY is directly relevant as a meta-harness architecture: it orchestrates a dynamically scheduled pool of heterogeneous LLM agents under a unified interface, with adaptive routing (UCB scheduling), shared state (pool-wise memory), and confidence-calibrated aggregation (EMCS)—all hallmarks of a meta-harness that wraps and coordinates subordinate agents. The pool-wise memory sharing mechanism is particularly notable as a lightweight, prompt-level alternative to centralized controller state, demonstrating how a harness can propagate cross-agent learning without modifying underlying models. For researchers building multi-agent harnesses, SYMPHONY provides concrete design patterns: bandit-based agent routing, entropy-gated value aggregation, and FIFO-windowed reflection propagation as composable primitives.