Multi-Agent Design: Optimizing Agents with Better Prompts and Topologies

We thank the reviewer for their insightful suggestions and acknowledging the undoubted merits of MASS-style optimization! We appreciate the reviewer pointing out the details in the paper that could be further clarified. We have provided further clarifications in this response and will update the final manuscript. We hope that our response sufficiently addresses the reviewer’s concerns, and the reviewer could consider improving their score.

Alternatives to the prompt optimizer.

We appreciate the reviewer for suggesting many insightful works that have advanced the field of prompt optimization and will certainly include all your referred literature in the related work. We’d like to recall that MASS is a plug-and-play framework with arbitrary prompt optimizers, and one of our primary contributions is identifying the influence of prompt optimization on the MAS. We integrate MIPRO as a representative prompt optimizer due to the importance of simultaneous instruction and exemplar optimization, which has been justified in [1, 2] that show superior performance over OPRO-style [3] instruction-only optimization methods. It is also worth noting that the MASS framework itself is agnostic to prompt optimizer, and thus any prospective better methods can only enhance the overall performance of MASS. Below, we additionally provide an ablation of common prompt optimizers, and we show MASS with exemplar optimization (+DSPy) also led to significant gains. In line with the reviewer, we have also considered extending the existing PO to feedback-based optimizers (e.g., ProTeGi or TextGrad) that may come with better sample efficiency, which we have included as a desirable future work (line 727).

[1] Opsahl-Ong, K., Ryan, M. J., Purtell, J., Broman, D., Potts, C., Zaharia, M., & Khattab, O. (2024). Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs. EMNLP 2024.

[2] Wan, X., Sun, R., Nakhost, H., & Arik, S. O. (2024). Teach Better or Show Smarter? On Instructions and Exemplars in Automatic Prompt Optimization. NeurIPS 2024.

[3] Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., & Chen, X. (2023). Large Language Models as Optimizers. ICLR 2024.

Details of parallelization in MASS.

We thank the reviewer for pointing out the parallelizable feature of our optimization. We will highlight in Algorithm 1, lines 5-8 & 12-13, to indicate phases that can be parallelized to improve the efficiency of MASS implementation.

Clarification on the “propose new workflow” in workflow-level topology optimization.

We thank the reviewer for suggesting to formulate the topology optimization more precisely. Given the configuration space per topology building block, as described in step 12, we conduct rejection sampling to sample workflow candidates. Formally, the workflow is randomly sampled from a pruned configuration space within a maximum budget, such that $a \sim \mathcal{A} \text{ s.t.} N(a) < Budget$, where $N(a)$ caps the overall number of agents; $\mathcal{A} = (N_{aggregate}, N_{reflect}, N_{debate}, N_{Tool}, …)$ is the configuration space as defined in Sec 2.2, and each search dimension will be weighted by the influence of that dimension and treated as deactivated if $\mathcal{Uniform}(0, 1) > p_{a_{i}}$. Followed by that, the workflow $W(a)=(a_i, a_i+1, …)$ is constructed in a predefined rule to arrange the order of agents (line 267). We included the specification of the detailed search space in the App. A, Table 3. Overall, we thank the reviewer and will update the algorithm 1, step 13 from one-line description to suggested mathematical formulations.

In formula 1, it is not clear why $a$ is a function of a single sample $x$ (referring to $a(x)$). Is the workflow of the configuration a singular version applied to all samples of the dataset.

In Equation 1, the optimization objective function is to maximize the expectation of a configuration $a$ over all samples. Therefore, it is expressed as $a(x)$ for a single sample but marginalized over the whole dataset $\mathcal{D}$.

There is no formal definition of a “block” in Section 2.

We thank the reviewer for the suggestion of providing a formal definition of “blocks” earlier. In Sec. 2, line 65, we refer to the topology of agents as building blocks. Formally, building blocks represent the minimum set of agents within a type of topology. It forms the final search space of MASS. We currently define it from Sec. 2.2 line 161 with visualization provided in Figure 8. We will move this part of the information earlier in light of your suggestion.

Line 307. It’s not clear what a “proper” prompt design means.

We appreciate the reviewer pointing this out. The “proper” prompt design actually refers to “prompt optimization”, and we will rephrase the sentence using “prompt optimization” instead for clarity.

We thank the reviewer for their insightful suggestions! Please see below for our detailed response, where we provide more details on the token consumption with further clarifications on optimizing the topology. We will include your valuable discussion in the manuscript. We hope that the reviewer could consider increasing the score if they feel the concerns have been sufficiently addressed.

The optimization process relies too much on a pre-defined dataset and the pipeline is somehow long, making it slow and resource-intensive for optimizing the workflow.

We agree with the reviewer that optimizing workflow requires a validation set. However, we would like to recall that all workflow optimization baselines require some form of labeled samples, and, as reflected in Figure 6, MASS is capable of exploiting in a more refined and effective search space, advancing multi-agent performance while being more computation-efficient than the state-of-the-art automatic agent design methods (ADAS and AFlow), and the 3-stage pipeline, while seemingly long, can be justified that each stage leads to concrete performance improvements (Fig 5 & Table 5). In future work, we expect the sample-efficiency of MASS could be further improved by researching more sample-efficient prompt optimizers (Line 727) and low-cost proxies as optimization objectives.

Critical algorithms are not described in detail, just scribbled over. For example, it is unclear how the authors optimize the topology.

We thank the reviewer for suggesting a better description of the topology optimization. Given the configuration space per topology building block, we conduct rejection sampling to sample workflow candidates. Formally, the workflow is randomly sampled from a pruned configuration space within a maximum budget, such that $a \sim \mathcal{A} \text{ s.t.} N(a) < Budget$, where $N(a)$ caps the overall number of agents; $\mathcal{A} = (N_{aggregate}, N_{reflect}, N_{debate}, N_{Tool}, …)$ is the configuration space as defined in Sec 2.2, and each search dimension will be weighted by the influence of that dimension, and rejected if $\mathcal{Uniform}(0, 1) > p_{a_{i}}$. Followed by that, the workflow $W(a)=(a_i, a_i+1, …)$ is constructed in a predefined rule to arrange the order of agents (line 267). We have included the specification of the detailed search space in the App. A, Table 3. Overall, we thank the reviewer and will update the algorithm 1, steps 12 & 13 with better mathematical formulations.

The comparisons on token consumption are not discussed. As the proposed method involves many steps that require token consumption, this part is critical.

We thank the reviewer for suggesting a token consumption report. Here, we include an additional table of the actual token cost compared to baselines. In accordance with Figure 6 in the paper, we show that the training cost of MASS is comparable to state-of-the-art automatic agent design baselines.

In Algorithm 1, how do you prune the design space based on the selection probability?

In sampling the valid configuration of agents at each iteration, we first prune each search dimension with the normalized selection probability that guarantees at least one dimension is kept activated. The target dimension will be rejected if $\mathcal{Uniform}(0, 1) > p_{a_{i}}$, where $a_{i}$ refers to the individual dimension in $\mathcal{A}$. For example, given the original search space $\mathcal{A}=(N_{aggregate}, N_{reflect}, N_{debate}, …)$, if $p_{reflect}$ is 0.8, in each iteration of sampling, this search space dimension will have a 20% chance pruned (i.e., turned off), and the rest dimensions will form the current search space, such that $\mathcal{A}$ becomes $(N_{aggregate}, N_{debate}, …)$. We hope this addresses your concerns.

We thank the reviewer for their insightful and positive comments, especially for many valuable suggestions on a deeper discussion on topology design space, impacts of actual configurations, and further extending MASS to real-world applications! We have included your suggestions in this response and will also incorporate them into the final manuscript. We hope that in light of the response, the reviewer could consider improving their score.

While the results are compelling, the generalization to larger-scale or more diverse real-world settings is not extensively explored.

Thank you for suggesting the exploration of larger-scale, real-world agent applications. The scale investigated in our work (roughly O(10) agents) aligns with current state-of-the-art agent design methodologies. Importantly, this scale is characteristic of numerous deployed real-world MAS applications where complex interactions within smaller teams are common [1]. Therefore, while we recognize the value of scaling further and consider it an important avenue for future research, our current focus addresses a highly relevant regime. Extending MASS to systems with substantially more agents remains a key area for future investigation.

[1] Xia, C. S., Deng, Y., Dunn, S., & Zhang, L. (2024). Agentless: Demystifying LLM-based Software Engineering Agents.

Why specific topologies are more effective than others is not deeply explored beyond empirical evidence? It would also be beneficial to include an ablation study evaluating the impact of different topology configurations.

We thank the reviewer for raising this very insightful question! The optimal topology does indicate certain patterns per task family, and there are topologies that demonstrate clear advantages over other topologies in particular tasks. By inspecting Figure 8, we notice that the “debating” topology brings significant gains to all multi-hop tasks that require factual knowledge: HotpotQA, MuSiQue, and 2WikiMQA, which is aligned with [2] that argues debating will elicit more truthful answers. Reasoning tasks: MATH and DROP benefit from more exploration, where SC becomes more effective. Lastly, the coding tasks share a common pattern of reflection with tool-using. However, even the best configuration in the same task family still shows differentiations, indicating the necessity of automatic optimization. Therefore, no matter the underlying complexity of the task-dependent topology, the unique advantage of MASS is being able to identify the most influential topology automatically for any customized search space. We will incorporate this discussion into a new ablation subsection.

[2] Khan, A., Hughes, J., Valentine, D., Ruis, L., Sachan, K., Radhakrishnan, A., ... & Perez, E. (2024). Debating with more persuasive LLMs leads to more truthful answers. ICML 2024.

Scalability considerations: The paper does not extensively discuss the computational cost of running MASS. How MASS scales with increasing agent complexity remains unclear. More details on runtime and computational overhead across different tasks would be useful.

We thank the reviewer for suggesting a token consumption report. Here, we include an additional table of the actual token cost for running MASS and how it is compared to baselines, where we show the training cost and the actual run-time of MASS is comparable to the training cost of auto-agent baselines.

Baseline comparisons & ablations: a deeper discussion of why MASS outperforms AFlow across different tasks would add value. While the paper provides strong empirical results, a discussion on limitations (e.g., cases where MASS underperforms) is missing.

We agree with the reviewer that a deeper discussion with AFlow can shed light and add value for future designs. We’ve provided a discussion in Lines 323-382 and Lines 431-434, and we are happy to further elaborate on that: the core differentiation between MASS and AFlow sits at the design of the optimization dimension (i.e., search space), and we observe that the importance of search space design outweighs the actual search algorithm, which have been reflected in many NAS literature. More precisely, MASS exploits a more effective prompt design space in conjunction with a general topology space, whereas AFlow conducts search in a more constrained set of operators with a very limited prompt space designed to be tailored to certain tasks. Therefore, the human-prior in defining these operators could provide implicit advantages for some tasks (e.g., 2WikiMQA in Table 1) where MASS shows lower but still comparable results.

We thank the reviewer for their constructive suggestions! We have included additional experimental results with open-source models, a graph optimization baseline, and provided clear comparisons on the token consumption. We hope in light of our response, the reviewer could consider improving their score.

Novelty of MASS

A key contribution of this work is highlighting critical, under-explored design dimensions in MAS: the significant impact of prompt engineering and the redundancy in conventional topology choices. Unlike prior approaches often using manual prompts or emphasizing scaling alone, we demonstrate that optimizing these elements yields substantial gains and interacts critically with other dimensions like agent scaling. We argue this insight is foundational for MAS—a developing field—as it clarifies the necessity for automated co-optimization, answering why methods like strong prompt optimization are essential.

Leveraging this understanding, we introduce MASS, a novel methodology for automated MAS design. While adaptable to various prompt optimizers (MIPRO was used here), MASS employs a distinctive three-stage, interleaved optimization strategy. This approach navigates the complex design space by sequentially refining the most influential components within pruned search space boundaries. Consequently, MASS achieves state-of-the-art performance, significantly outperforming existing automated design methods and the specialized prompt optimizer used in isolation (Fig 5, left).

Justification of topology design choices

While there are some manual design in deciding the search perimeter, our topology search space aligns with well-established topological designs, including SC, reflect, and debate, that have been shown generalizable and effective to a wide spectrum of tasks in the board literature and were also used in the search spaces of seminal previous works like ADAS and AFlow, which we also chose for a fair comparison and generality. However, the MASS framework on its own does not depend on a specific topology space, and we can easily extend it to customized topology choices. We leave experimental results with MASS on other involved topology search spaces to future work.

Open-source models

We extend experiments to Mistral-Nemo-12B, where the consistent gains prove the applicability of MASS even to small open-source models.

Graph optimization baseline

Following the reviewer’s suggestion, we report GPTSwarm and observe that the graph optimization is more effective in improving the inference efficiency from a fully-connected graph to a sparse graph rather than enhancing the task performance, whereas the prompt optimization component of MASS particularly led to more significant contributions.

Cost-efficiency of the method

We present the token consumption comparison of gemini-flash below, where it’s clear that MASS consumes comparable compute to ADAS and AFlow:

Q1: Generalization on prompt scalability

We’d like to refer to Table 5, Page 16 where it’s obvious that the gain from “Base” to “1PO”, which is the prompt optimization step, far exceeds, e.g., that from “1PO” to “2TO”, which is the topology search step, which aligns with the observation in Fig 2. We additionally show Claude results below, which demonstrate that the observation is not specific to Gemini models.

Q2: Fairness of comparisons

As mentioned in the cost comparison table above, we’d like to emphasize that we broadly controlled the cost, and all methods roughly consume the same token/dollar costs. We also provide detailed specifications of baselines in App. B.2 that all come with a fair number of token consumptions compared to MASS.

Regarding further scaling SC, firstly we note that SC is a part of the MASS search space, so MASS can naturally benefit from SC scaling. Second, as we have shown in Figure 2 & 9, even if SC brings significant benefits, SC still saturates earlier than MASS-optimized topologies, which show a better token-effectiveness. In other tasks in Table 1, even assigned with a large budget, SC only makes limited gains on multi-hop tasks, whereas the Debate topology substantially advances the performance. This observation further consolidates the necessity of automatic topology optimization in MASS.