Agent-Oriented Planning in Multi-Agent Systems

## Abstract

Abstract Through the collaboration of multiple agents possessing diverse expertise and tools, multi-agent systems achieve impressive progress in solving real-world problems. Given the user queries, the meta-agents, serving as the brain within these systems, are required to decompose the queries into multiple sub-tasks that can be allocated to suitable agents capable of solving them, so-called agent-oriented planning. In this study, we identify three critical design principles of agent-oriented planning, including solvability, completeness, and non-redundancy, to ensure that each sub-task is effectively resolved, leading to satisfactory responses to the original queries. These principles further inspire us to propose a novel framework for agent-oriented planning in multi-agent systems, leveraging a fast task decomposition and allocation process followed by an effective and efficient evaluation via a reward model. During the planning process, the meta-agent is also responsible for evaluating the performance of the expert agents, making timely adjustments to the sub-tasks and scheduling as necessary. Besides, we integrate a feedback loop into the proposed framework to further enhance the effectiveness and robustness of such a problem-solving process. Extensive experiments demonstrate the advancement of the proposed framework in solving real-world problems compared to both single-agent systems and existing planning strategies for multi-agent systems.

## 1 Introduction

In recent years, large language models (LLMs) (Achiam et al., ; Chowdhery et al., ; Touvron et al., ) have achieved impressive breakthroughs in natural language understanding and generation, marking a critical advancement in the exploration of artificial general intelligence (AGI).
As the capabilities of LLMs progress, LLM-empowered agents (Qin et al., ; Dong et al., ; Wang et al., ) emerge as key components for integrating expertise and tools to translate these advancements into practical applications effectively.
Advancing this paradigm, multi-agent systems (Shen et al., ; Chen et al., ; Wu et al., ), which involve multiple diverse agents, provide great flexibility and adaptability by leveraging and collaborating on the strengths of various agents, promoting comprehensive solutions to complex real-world problems.

Previous studies (Cai et al., ; Qian et al., ) propose to define suitable standard operating procedures (SOPs) based on the insights and experiences of human professionals for solving specific tasks, such as software development (Hong et al., ) and simulating personality traits (Serapio-García et al., ). In these scenarios, multiple agents are assigned to execute tasks following the predefined SOPs, resulting in remarkable successes. However, for multi-agent systems designed to tackle a diverse range of complex real-world problems, there is a critical need for a central entity that can automatically generate task-specific operating procedures and coordinate the activities of various agents (Wang et al., ).

This central entity, typically referred to as a meta-agent (a.k.a. a controller or planner), carries two primary responsibilities. Firstly, the meta-agent needs to comprehend user queries and decompose them into several sub-tasks, ensuring that each sub-task can be adequately addressed by a single agent. Secondly, the meta-agent is also expected to assign these sub-tasks to the appropriate agents for execution, enabling the solutions of these sub-tasks to collectively provide comprehensive answers to the original user query.

However, since the meta-agent cannot effectively associate sub-tasks based on the provided agent descriptions, the performance of task decomposition and allocations might be sub-optional. To tackle these challenges, we identify three design principles for an agent-oriented planning framework, including solvability, completeness, and non-redundancy, which further inspire us to propose a novel framework for multi-agent systems.

Specifically, to resolve a user query, the meta-agent first performs fast task decomposition and allocation, which serves as the intermediate results that can be further modified and revised. The proposed framework incorporates a reward model designed to efficiently evaluate the solvability of sub-tasks without requiring actual agent calls.
According to the evaluation results, some sub-tasks may be executed by the assigned agents, others may be recognized as inappropriate and be required to perform a replan, while the remaining sub-tasks would be further assessed through the representative works mechanism, which helps determine whether they should be planned in detail or re-described for better aligning the ability of agents.
A detector is utilized to identify the missing key information or redundant content in the decomposed sub-tasks, and to provide suggestions to the meta-agent for enhancing the completeness and non-redundancy.
Besides, a feedback loop is integrated into the proposed framework to promote ongoing enhancements for the meta-agent.

Extensive experiments are conducted based on a reasoning dataset that needs the collaboration of multiple agents. The comparisons between the proposed agent-oriented planning framework and baseline methods demonstrate the remarkable advancements achieved by the proposed framework.
Besides, we conduct an ablation study to confirm the contributions of the different components in the proposed framework, and provide discussions on the potential for further improvements in the performance of agent-oriented planning within multi-agent systems.

## 2 Preliminaries

#### Definition of Agent-Oriented Planning

In this study, a multi-agent system involves a series of LLM-empowered agents that possess diverse expertise and tools. These agents are designed to leverage their expertise and tools to resolve specific real-world tasks. For example, a search agent can utilize search engines to retrieve up-to-date information relevant to a given query, while a code agent is capable of generating code and executing the code via a code interpreter.
The collaboration among these agents is facilitated by a meta-agent, which serves as the brain of the multi-agent systems.
When a user query is submitted to the multi-agent system, the meta-agent sends the relevant requests to the appropriate agents, optimizing for both effectiveness and efficiency. The responses produced by these agents are finally aggregated and synthesized to generate a comprehensive answer to the original user query.

Formally, given a user query $Q$, a meta-agent $\mathcal{P}$ needs to select some appropriate agents from a total of $n$ agents, denoted as $\mathcal{A}=\{\mathcal{A}_{1},...,\mathcal{A}_{n}\}$. Each agent is associated with a description $d$ that outlines its capability. We denote the collection of all agent descriptions as $\mathcal{D}=\{d_{1},...,d_{n}\}$.
The user query $Q$ is decomposed into $m$ sub-tasks, with each sub-task assigned to a specific agent based on their descriptions:

$$ $\mathcal{P}(Q,\mathcal{D},\mathcal{A})=\{(q_{i},\mathcal{A}_{i}^{\prime})\ |\ i\in[m]\}.$ (1) $$

After that, each selected agent $i\in[m]$ produces a response to its assigned sub-task, denoted as $r_{i}=\mathcal{A}^{\prime}_{i}(q_{i})$. These responses are then utilized to generate the
final answer based on $R=\{r_{1},...,r_{m}\}$ to resolve the original query $Q$.
Such a process is called agent-oriented planning.

#### Challenges

The challenges of agent-oriented planning in multi-agent systems can be two-fold. Firstly, different from existing studies focused on task decomposition  or chain-of-thought reasoning , agent-oriented planning requires intentional decomposition of user queries to effectively associate sub-tasks with agents, which includes considerations of the description of sub-tasks, the granularity of decomposition, the format of the responses, and so on. An example is illustrated at the higher left of Figure 1. Given a user query “How much tin (kg) with 100 kg of copper can lower the mixture’s melting point to $800\ \tccentigrade$?”, a naive decomposition might suggest “determine the melting point of tin and copper.” followed by “calculate the amount of tin (kg) required to reduce the melting point of the mixture to $800\ \tccentigrade$ with 100 kg of copper.”. However, when the sub-task of determining the melting points is assigned to a search agent, it may not result in satisfied responses since the query involves two entities simultaneously. In the context of agent-oriented planning, it is important to consider the capabilities of a search agent. As a result, such a sub-task should be further decomposed into individual entity searches: first determine the melting point of tin and then determine the melting point of copper.

Secondly, assigning sub-tasks to appropriate agents is non-trivial, as the meta-agent can only rely on the agents’ descriptions to determine task allocation in most cases (Shen et al., ). However, a concise and highly generalized description that adequately illustrates an agent’s capabilities may not always be available, leading to suboptimal allocation.
For example, if the description of a commonsense agent does not specify the extent of its knowledge base, the meta-agent may struggle to ascertain whether it is suitable to assign the task of querying the melting points of tin and copper to that agent, as shown at the lower left of Figure 1.

Figure: Figure 1: Examples of agent-oriented planning in multi-agent systems, regarding two challenges (left side) and three design principles (right side).
Refer to caption: x1.png

#### Design Principles

We further identify three critical principles that guide the design of our framework for effective and efficient agent-oriented planning in multi-agent systems:

- •
Solvability. Each sub-task $q_{i}\ \forall i\in[m]$ should be independently and completely resolvable by at least one single agent within the multi-agent system, ensuring that the response for each sub-task can be reliable. If a sub-task does not satisfy solvability, the meta-agent is expected to take some modifications or further decomposition.
- •
Completeness. The array of sub-tasks $\{q_{1},...,q_{m}\}$ should include all necessary information from the original user query $Q$, which ensures that the aggregation of responses of these sub-tasks can effectively yield a comprehensive answer to the user query. If the decomposed sub-tasks fail to satisfy completeness, the decomposition process should be revisited by the meta-agent.
- •
Non-Redundancy. The array of sub-tasks $\{q_{1},...,q_{m}\}$ should not include redundant elements, avoiding those task executions that are either irrelevant to resolving $Q$, or duplicated. The principle of non-redundancy promotes that the sub-tasks form a minimal effective set necessary to address the user query, enhancing overall efficiency.

Several examples are provided on the right side in Figure 1 for a better understanding of these design principles.
In Section 3, we provide more details of the mechanisms in the proposed framework that are designed to fulfill the aforementioned principles.

## 3 Agent-Oriented Planning in Multi-Agent Systems

In this section, we introduce the details of the proposed agent-oriented planning framework.
The overall architecture is illustrated in Figure 2.

Figure: Figure 2: Overall architecture of the proposed agent-oriented planning framework.
Refer to caption: x2.png

### 3.1 Fast Decomposition and Allocation

First of all, following existing studies (Shen et al., ; Chen et al., ), we provide detailed instructions to the meta-agent to guide it in performing agent-oriented planning. Different from previous studies, the provided instructions incorporate the following requirements:
(i) Integration of user query $Q$ and all the agent descriptions $A$: We include both the user query and the descriptions of agents in the instructions, promoting the meta-agent to fully consider the capabilities of each agent and tailor the sub-tasks to align with these capabilities.
(ii) Suggestions for assigned agents: We require the meta-agent to provide suggestions for the agents assigned to each decomposed sub-task. Although we tend to separate task decomposition and assignment into two independent tasks performed sequentially, the experimental observations indicate that combining these two tasks enhances the effectiveness of agent-oriented planning.
(iii) Structured decomposition of tasks: The decomposed tasks are required to be structured in a sequential manner, specifying any dependencies that may exist between sub-tasks, which ensures that the execution of tasks follows a correct logical order.
The adopted prompt can be found in Appendix A.1.

The aforementioned process of agent-oriented planning, which is called fast decomposition and allocation in this study, heavily relies on the capabilities of the meta-agent and meticulously designed system prompts. While such an end-to-end approach can achieve high efficiency, its success rate, namely fulfilling the three design principles mentioned above and providing reliable answers to the original user query, and its stability, namely the meta-agent can follow instructions and produce formatted responses, might not be satisfactory.

Inspired by recent studies on scaling laws during inference (OpenAI, ), we propose to design mechanisms to guide the meta-agent toward more comprehensive reasoning processes. The results of fast decomposition and allocation should be viewed as intermediate outputs rather than final results, which need to be further evaluated to offer detailed revision suggestions for the meta-agent.
More details on this proposed approach are provided in the next section.

### 3.2 Is A Sub-Task Completely Resolved?

To determine whether a sub-task can be resolved by a single agent, i.e., satisfying the principle of solvability, a straightforward solution is to send the sub-task to every agent in the system. Each agent generates a response to the sub-task, allowing us to select the best answer and assess whether it completely resolves the sub-task.
However, this approach is often impractical due to the unaffordable overhead. For a user query decomposed into $m$ sub-tasks, a multi-agent system with $n$ agents would need to execute a total of $m\times n$ agent calls for just a single trial, making it an inefficient strategy in scenarios with a large number of agents and sub-tasks.

To tackle this, we propose a reward model designed to provide efficient evaluations of the solvability of sub-tasks, which aims to predict the quality of the agents’ responses to sub-tasks without necessitating actual agent calls.

Specifically, we first prepare a dataset for training the reward model.
For a given user query $Q$, we follow the fast decomposition and allocation process introduced in Section 3.1, requiring the meta-agent to decompose $Q$ into several sub-tasks and select $l$ agents for each sub-task based on the agents’ descriptions,
which can be formally given as follows:

$$ $\mathcal{P}(Q,\mathcal{D},\mathcal{A})=\{(q_{i},\mathcal{A}_{i,1},...,\mathcal {A}_{i,l})\ |\ i\in[m]\}.$ (2) $$

After that, we execute the plan, i.e., sending the sub-tasks to the assigned agents, and obtain all the responses from agents as:

$$ $\{r_{i,j}=\mathcal{A}_{i,j}(q_{i})\ |\ i\in[m],j\in[l]\},$ (3) $$

where the choice of $l$ can be a trade-off. A large $l$ leads to comprehensive responses from lots of agents for constructing the training dataset, while it might need more computation resources and affect the overall quality of the dataset. In this study, we set $l$ to be half the number of agents in the multi-agent systems.

We utilize a scorer $\mathcal{S}$ that evaluates agents’ responses to sub-tasks, i.e., $\mathcal{S}(q_{i},r_{i,j})=s_{i,j}$, which serves as annotations in the training dataset.
The scorer $\mathcal{S}$ provides evaluations from three key aspects: correctness, relevance, and completeness, and can be implemented using powerful LLMs (OpenAI, ) or human annotators.
We apply this scoring process across a diverse array of user queries $\mathcal{Q}=\{Q_{k}\}_{k=1}^{K}$ and collect the results to form the training dataset, denoted as $\mathcal{T}=\{(q_{k,i},d_{k,i,j},s_{k,i,j})\ |\ k\in[K],i\in[m_{k}],j\in[l]\}$.
More details on the construction of the dataset, such as the adopted prompts, are summarized in Appendix C.

The reward model, parameterized as $\theta$, consists of embedding layers followed by fully connected layers. We obtain embeddings for both the sub-task and the agent’s description separately, then concatenate these embeddings together and feed them into the fully connected layers for further processing.
To provide evaluations without making actual agent calls, we design a training objective aimed at minimizing the discrepancies between the model’s predictions and the annotations provided by the scorer, which can be formulated as follows:

$$ $L(\mathcal{T},\theta)=\frac{1}{K}\sum_{k=1}^{K}\frac{1}{m_{k}}\sum_{i=1}^{m_{k }}\frac{1}{l}\sum_{j=1}^{l}(s_{k,i,j}-\mathcal{M}_{\theta}(q_{k,i},d_{k,i,j})) ^{2}.$ (4) $$

With the well-trained reward model, the evaluation of the results produced by fast decomposition and allocation can be summarized as follows. For each suggestion provided by the meta-agent, stating the assignment of sub-task $q_{i}$ to agent $\mathcal{A}_{i}^{\prime}$, the reward model predicts a score denoted as $\mathcal{M}_{\theta}(q_{i},d_{i}^{\prime})$. A sufficiently high predicted score, which implies that $q_{i}$ can be completely resolved by agent $\mathcal{A}_{i}^{\prime}$, leads to the acceptance of this suggestion. Conversely, if the predicted score falls below a predefined threshold, which indicates that the assignment should be revisited by the meta-agent, the reward model provides a set of scores $\hat{s}_{i,j}=\mathcal{M}_{\theta}(q_{i},d_{j})$ for all the agents $\mathcal{A}_{j},j=1,...,n$. From these scores, the meta-agent reports the optimal solution as $j_{max}=\mathrm{argmax}_{j}\,\hat{s}_{i,j}$.

Note that there may be scenarios where the highest score $\hat{s}_{j_{max}}$ is still below the threshold, indicating that the sub-task $q_{i}$ does not satisfy the principle of solvability and that no single agent can resolve it independently. In these cases, the meta-agent $\mathcal{P}$ is required to perform a replan on $q_{i}$.
The prompt used for replan is detailed in Appendix A.2.

### 3.3 Sub-Task Modifications

In addition to the two scenarios mentioned in Section 3.2, where the assignment of sub-task $q_{i}$ to agent $\mathcal{A}_{i}^{\prime}$ is either predicted to be acceptable by the reward model or to be entirely inappropriate and requires a replan process, there also exists another situation where agent $\mathcal{A}_{i}^{\prime}$ might not provide a reliable response to sub-task $q_{i}$, even though the assignment seems reasonable according to the reward model.

We identify two intrinsic reasons for such a situation in agent-oriented planning.
First, the description of the sub-task may lack critical information necessary for solving the problem, such as the interpretation of contextually elements like pronouns or other ambiguous terms. In such cases, while the agent possesses the capability to resolve the sub-task, the missing information can hinder it to provide a satisfactory response.
Second, the sub-task $q_{i}$ might be too complex, therefore a single agent can only address parts of this sub-task based on its expertise and tools.
In this subsection, we design mechanisms to distinguish between these two cases and propose corresponding solutions.

To be specific, for each agent, we propose to construct a set of representative works that record the tasks it has completely resolved. We would initially bypass the construction and update for these representative works (refer to Section 3.5 for more details) and focus on how to utilize them to make sub-tasks modifications here.
Given a sub-task $q_{i}$, we calculate its similarity with a representative work $q_{t}$ following $cos(\mathcal{E}(q_{i}),\mathcal{E}(q_{t}))$, where $\mathcal{E}$ is the embedding part in $\mathcal{M}$ and $cos(u,v)=\frac{u\cdot v}{\left\|u\right\|_{2}\left\|v\right\|_{2}}$ calculates the cosine similarity. We define the similarity as follows:

$$ $sim(q_{i},\mathcal{Q}_{j})=\max\{cos(\mathcal{E}(q_{i}),\mathcal{E}(q_{t}))|q_ {t}\in\mathcal{Q}_{j}\},$ (5) $$

where it can be denoted as $sim_{i,j}$ for short.

A large $\max\{sim_{i,j}\ |\ j\in[n]\}$ indicates that the representative works of the agent corresponding to $\max\{sim_{i,j}\ |\ j\in[n]\}$ contain a sub-task similar to $q_{i}$. Such a case should be attributed to the first reason mentioned above, and we tend to request the meta-agent to perform re-describe on $q_{i}$ according to the similar representative work.

On the other hand, if the calculated similarity does not meet the threshold, we regarded $q_{i}$ as too complex for any single agent in the system to solve (corresponding to the second reason above). As a result, the meta-agent $\mathcal{P}$ is requested to perform plan-in-detail for further decomposing the sub-task into simple ones.
To avoid creating redundant sub-tasks, we provide $\mathcal{P}$ with all the sub-tasks and explicit instruction on avoiding overlapping sub-asks. The prompt used for sub-task modification can be found in Appendix A.3 and Appendix A.4.

### 3.4 Detector for Completeness and Non-Redundancy

Following the idea in fast decomposition and allocation, we attempt to enhance the proposed framework by incorporating detailed instructions to satisfy the principles of completeness and non-redundancy, such as “make sure all the important information of the original task such as nouns or numbers are included in the sub-tasks”. However, empirical observations reveal that these instructions do not mitigate these issues. In fact, more than 15% of user queries still exhibit such issues during decomposition.

To tackle these issues, we involve a detector, implemented with providing a role-play prompt to LLMs, to evaluate both the completeness and non-redundancy of the intermediate results provided by the meta-agent.
For the principle of completeness, the detector extracts all key elements and requirements from the original task, and then matches these elements against each sub-task, determining whether the sub-tasks collectively address all essential aspects of the original task.
Regarding the principle of non-redundancy, the detector checks for identical information and requirements across sub-tasks. The detector flags the redundancy if two sub-tasks include overlapping content.

When the provided results do not satisfy the principles of completeness or non-redundancy, the detector identifies the missing key information or redundant content, and offers recommendations for refining the plan, such as suggestions for supplementing missing details or removing overlapping sub-tasks.

The prompt used for the detector is provided in Appendix A.5.
From the experimental results shown in Section 2, we observe that the detector effectively mitigates the issues of task decomposition incompleteness and redundancy, leading to an effective and efficient agent-oriented planning process.

### 3.5 Feedback Loop

An automatic feedback loop is integrated into the proposed agent-oriented planning framework, promoting ongoing enhancement of the meta-agent.

As introduced in Section 3.2, the reward model can identify certain sub-tasks as being resolvable by specific agents.
These identified sub-tasks are then collected to form the representative works of the corresponding agents. The training data for the reward model, which includes the sub-tasks and the ground truth scores of responses provided by the agents, is utilized to initialize these representative works.

Note that the representative works are continuously updated. When a user query is completely resolved, the sub-tasks decomposed from that user query can be added to the representative works of the agents who are selected to provide response to these sub-tasks.
To prevent redundancy in the representative works, we implement a similarity threshold. This threshold ensures that only new and sufficiently distinct sub-tasks are incorporated into an agent’s representative works, maintaining the diversity and relevance of the tasks that each agent has previously resolved.

## 4 Experiments

In this section, we provide empirical comparisons between the proposed agent-oriented planning framework and the existing studies.

### 4.1 Settings

#### Datasets & Evaluations

We conduct experiments based on a numerical reasoning dataset (Kim et al., ), which necessitates the collaboration of multiple agents in resolving the queries. For example, a query can be “If Sarah wants to buy one BMW X5 and one Tesla Model 3, how much more would she need to pay to buy the BMW X5 compared to the Tesla Model 3?” To resolve this query, we first need to search for the prices of the BMW X5 and Tesla Model 3, and then calculate the price difference between them.
Following previous study (Kim et al., ), we construct a training dataset consisting of 1,440 queries, along with an annotated test dataset consisting of 292 queries. Note that the topics in the training dataset and test dataset may vary slightly.

For quantification comparisons, we provide instructions to GPT-4o (OpenAI, ) for assisting in judging whether the execution results align with the ground truth, and calculate the accuracy as the evaluation metrics. The prompt used for evaluation can be found in Appendix D.

#### Involving Agents

In the experiments, the multi-agent system includes a meta-agent and several diverse agents, including a code agent, math agent, search agent, and commonsense agent. The descriptions of these agents, which are similar to those in previous studies (Kim et al., ) for a fair comparison, are shown below:

- •
Code Agent: Generate code in Python for precise computations to solve the given task.
- •
Math Agent: Answer math questions by reasoning step-by-step.
- •
Search Agent: Call the Bing Search API to obtain information related to the given task.
- •
Commonsense Agent: Answer the given question using commonsense reasoning.

The meta-agent is tasked with decomposing user queries into sub-tasks and assigning the most suitable agents to execute those sub-tasks. We use GPT-4o as the employed LLM for all agents, and the used prompt are provided in Appendix B.

#### Reward Model

We adopt all-MiniLM-L6-v2 (Wang et al., ) as the embedding layers of the reward model, which maps text sentences or paragraphs into a 384-dimensional dense vector space. The embeddings for both the sub-task and the agent’s description are computed separately, and are concatenate together to form a 768-dimensional dense vector.
Following the embedding model, we add a three-layer multilayer perceptron (MLP) with output dimensions of 256,64, and 1, respectively.
We freeze the embedding layers and only finetune the parameters of the MLP, making the training process efficiently. The batch size are set to 32, the learning rate is 1e-3. We train the reward model for 50 epochs on one Tesla V100-SXM2-32GB GPU.

#### Baselines

For the single-agent systems, we utilize GPT-4o as a baseline method, providing user queries directly without any additional prompt engineering.
Besides, we provide GPT-4o with Chain-of-Thought (CoT) (Wei et al., ) prompt and Zero-Shot CoT (Kojima et al., ) prompt to guide LLMs to perform reasoning processes, resulting in two baselines denoted as CoT and Zero-Shot CoT.
Taking a further step, we instruct GPT-4o to serve as a meta-agent responsible for performing fast task decomposition and allocations. We implement two baselines, denoted as Meta-Agent and Meta-Agent: Traversal, respectively. Meta-Agent denotes that the LLM selects one agent for each sub-task, while Meta-Agent: Traversal denotes that GPT-4o iteratively queries all agents for each sub-task and selects the best response.

Regarding multi-agent systems, we compare the proposed framework with REACT (Yao et al., ) and HUSKY (Kim et al., ), which are representative methods involving task decomposition and sub-task execution.

**Table 1: Comparisons between the proposed agent-oriented planning framework and baselines.**
| Method | Accuracy (%) | Prompt Tokens (M) | Completion Tokens (M) | Time (s) |
| --- | --- | --- | --- | --- |
| GPT-4o | 33.3 | 0.02 | 0.09 | 1,968 |
| CoT | 35.6 | 0.07 | 0.08 | 1,375 |
| Zero-Shot CoT | 32.2 | 0.02 | 0.11 | 1,565 |
| Meta-Agent | 30.0 | 0.65 | 0.13 | 5,364 |
| Meta-Agent: Traversal | 35.2 | 3.07 | 0.69 | 23,175 |
| REACT | 37.6 | 2.47 | 0.19 | 11,510 |
| HUSKY | 39.6 | 0.83 | 0.15 | 10,394 |
| Ours | 43.7 | 1.12 | 0.38 | 11,869 |

### 4.2 Comparisons and Analysis

The comparisons between the proposed agent-oriented planning framework and the baseline methods are shown in Table 1. We adopt accuracy as the metric for comparing effectiveness, and use prompt tokens, completion token, and the execution time for comparing efficiency.

Overall, the experimental results demonstrate that the proposed agent-oriented planning framework achieves notable improvements compared to all baseline methods. To be specific, when comparing with single-agent systems including GPT-4o, CoT, and Zero-Shot CoT, the proposed agent-oriented planning framework outperforms these systems by 10.4%, 8.1%, and 11.5% in terms of accuracy, respectively. These improvements can be attributed to the collaboration among multiple diverse agents and the effective scheduling provided by the meta-agent. It is not surprising to observe that the proposed framework incurs higher resource costs and longer inference times compared to single-agent systems.
These additional costs during the inference phase, which includes task decomposition, allocation, and modifications carried out by the meta-agent, are affordable and can be worthwhile as long as they bring significant improvements in accuracy and stability when applying real-world applications.

Compared to systems that also involve a meta-agent for task decomposition and allocation, we can observe from the table that the proposed method achieves at least a 4.1% improvement in terms of accuracy while maintaining the same level of computation costs and inference times. The results of Meta-Agent and Meta-Agent: Iteration indicate that simply instructing GPT-4o to perform task decomposition and allocation does not always yield satisfactory responses, even though the capabilities of LLM are recognized as powerful.
Existing studies in task composition and allocation fail to consider the abilities and characteristics of the agents beyond their descriptions, and lack mechanisms for modifications and feedback within the multi-agent system, which can be hindered by the challenges as summarized in Section 2.
The proposed framework is built upon these identified design principles and incorporates novel mechanisms for automatically evaluating intermediate results, allowing timely modifications and revisions, which guides and leverages the strengths of LLMs within the multi-agent system for effectively resolving user queries and enhancing overall system performance.

### 4.3 Further Discussions

#### Ablation Study

We conducted an ablation study to confirm the contributions of different components in the proposed framework. Specifically, we disable the detector, the reward model, and the representatives of agents in separate experiments, with results reported in Table 2.
From these results, we can observe that the detector has a significant impact on execution accuracy, as indicated by a notable increase in the incompleteness rate during the meta-agent’s task decomposition phase.
Both the reward model and the representative works are necessary in ensuring the solvability of tasks and in selecting the most suitable agents for each sub-task.
Overall, these results demonstrate that all three components are indispensable, working together to ensure the feasibility of task decomposition and allocation, leading to satisfactory responses to the original user queries.

**Table 2: Experimental results of ablation study.**
| Method | Accuracy (%) | Prompt Tokens (M) | Completion Tokens (M) | Time (s) |
| --- | --- | --- | --- | --- |
| Ours | 43.7 | 1.12 | 0.38 | 11,869 |
| w/o Plan Detector | 36.6 | 1.05 | 0.29 | 9,504 |
| w/o Reward Model | 38.7 | 1.17 | 0.37 | 11,651 |
| w/o Representative Works | 41.1 | 1.14 | 0.36 | 11,178 |

#### Impact of Scorer and Reward Model

The training dataset is constructed based on annotations provided by the scorer, which in the previous experiments is implemented using LLMs. In this section, we shift to using human annotators to manually provide scores for the responses, evaluating whether a reward model trained on this manually labeled dataset would further enhance performance. This approach is denoted as Manual Scoring. More detailed information about the manual scoring process can be found in Appendix C.
Besides, based on the manually scored training dataset, we investigate the setting of updating the embedding layers of the reward model, denoted as Full Parameter Tuning.

The experimental results shown in Table 3 indicate that both manual scoring and full parameter tuning of the reward model lead to improved performance. These results suggest the potential for further improving the proposed agent-oriented planning framework by providing high-quality datasets for training robust reward models.

**Table 3: Experimental results on the impact of scorer and reward model**
| Method | Accuracy (%) | Prompt Tokens (M) | Completion Tokens (M) | Time (s) |
| --- | --- | --- | --- | --- |
| Ours | 43.7 | 1.12 | 0.38 | 11,869 |
| + Manual Scoring | 46.9 | 1.26 | 0.40 | 12,676 |
| + Full Parameter Tuning | 47.9 | 1.28 | 0.41 | 13,063 |

## 5 Related Work

The field of artificial general intelligence has witnessed a transformative development with the advent of large language models (LLMs), such as GPT-3 (Brown, ), GPT-4 (Achiam et al., ), PaLM (Chowdhery et al., ), LLaMa (Touvron et al., ) and so on (Devlin et al., ; Zhang et al., ; Chowdhery et al., ; Le Scao et al., ). LLMs have demonstrated remarkable capabilities in understanding and generating human language (Zhao et al., ), and solving tasks such as mathematical problems and commonsense reasoning (Imani et al., ; Ahn et al., ).
To further enhance the ability of LLMs in handling complex problems, some research focuses on improving the internal reasoning capabilities of LLMs, typically involves decomposing complex questions into sequential intermediate steps before generating the final answer, as exemplified by Chain-of-Thought (CoT) prompting (Wei et al., ) and its variants (Kojima et al., ; Wang et al., ; Zhou et al., ).
Some methods opt to generate a dozen possible paths to comprise the candidate plan set (Yao et al., ; Besta et al., ; Zhao et al., ; Hao et al., ) and select the optimal plan with strategies like heuristic search algorithms (Xiao & Wang, ).
In environments with complex constraints, such as generating permissible actions, several methods combine LLMs with external planners such as symbolic planners (Liu et al., ; Dagan et al., ; Guan et al., ) and neural planners (Yao et al., ; Lin et al., ).

Despite these advancements, LLMs still face challenges in addressing tasks that require extensive knowledge, such as avoiding hallucinations, integrating diverse domain knowledge, and executing long-horizon planning (Qin et al., ; Bubeck et al., ; Maynez et al., ). To address these issues, recent work has focused on multi-agent systems, which leverage the collective intelligence and specialized skills of multiple LLM-empowered agents to solve tasks. Compared with reinforcement learning, LLM-empowered agents have more comprehensive internal world knowledge, and can provide natural language interfaces to interact with humans, which is more flexible and explainable (Wang et al., ). Serving as the main controller or “brain” that manages the flow of operations, the meta-agent has gained the most significant attention.
The meta-agent is responsible for understanding the overall task, decomposing it into smaller ones, and coordinating the sub-tasks to the agents.
There are mainly two technical approaches in task decomposition: interleaved decomposition and decomposition-first. In the first kind of method, React (Yao et al., ) generates reasoning and action in an interleaved manner, where reasoning helps the meta-agent update action plans and action enables interaction with agents. Visual ChatGPT (Wu et al., ) meticulously designs a series of prompts to help inject the visual information into ChatGPT, designed to solve complex visual questions with diverse visual foundation models step-by-step. HUSKY (Kim et al., ) trains an action model to iterate between two stages: generating the next action to take and executing the action using expert models and updating the current solution state.

Regarding complex tasks, excessively long trajectories might bring hallucinations. Given that, HuggingGPT (Shen et al., ) carefully designs prompts to instruct ChatGPT to decompose tasks, selecting models in HuggingFace and summarizing the response. AutoAgents (Chen et al., ) dynamically generates multiple required agents based on task content and plans solutions for the current task based on the generated expert agents. Chameleon (Lu et al., ) prompts the meta-agent with tool descriptions and usage examples to infer a program composed of a sequence of tools to execute in order to generate the final response.

Although remarkable progress has been made, plans generated solely through prompt-based methods often fall short of meeting the principles of solvability, completeness, and non-redundancy—issues that have largely been overlooked in prior work. Besides, the meta-agent’s ability to make suitable schedules can be hindered when relying only on agents’ descriptions without considering their actual capabilities or past performance. To address these issues, we propose a novel framework to perform task decomposition and allocation satisfying the aforementioned three principles.

## 6 Conclusion

In this study, we propose a novel agent-oriented planning framework for multi-agent systems, following three critical design principles to ensure that the meta-agent can effectively decompose the user query into several sub-tasks for producing satisfactory responses.
The proposed framework utilizes a fast decomposition and allocation process, which relies on the ability of LLMs to generate an intermediate schedule efficiently. After that, a reward model and the representative work mechanism are employed to evaluate these intermediate results, routing three different paths for executing the sub-task or making necessary modifications to align the sub-task with agents, such as replan the sub-task, plan in detail, and re-describe.
Extensive experiments demonstrate that the proposed agent-oriented framework achieves significant improvements over both the existing single-agent and multi-agent baseline methods.
We provide discussions on the contributions of different components in the framework and the potential for improvements in agent-oriented planning.
We will release the source code to promote further research in the community.

## Appendix A Plan Generation and Modification

### A.1 Meta-agent Prompt

The one-shot prompt for meta-agent’s fast decomposition and allocation is shown in Figure 3.

Figure: Figure 3: One-shot prompt for the meta-agent.

### A.2 Replan

The prompt for replanning is shown in Figure 4.

Figure: Figure 4: Prompt for replanning.

### A.3 Plan in Detail

The prompt for planning in detail is shown in Figure 5.

Figure: Figure 5: Prompt for planning in detail.

### A.4 Re-describe

The prompt for re-describing the sub-task is shown in Figure 6.

Figure: Figure 6: Prompt for re-describing the sub-task.

### A.5 Detector

The prompt for the detector is shown in Figure 7.

Figure: Figure 7: Prompt for the detector.

## Appendix B Agents

The prompts for the code, math, search and commonsense agent are shown in Figure 8, 9, 10, 11 separately.

Figure: Figure 8: Prompt for the code agent.

Figure: Figure 9: Prompt for the math agent.

Figure: Figure 10: Prompt for the search agent.

Figure: Figure 11: Prompt for the commonsense agent.

## Appendix C Constructing Training Dataset

The prompt for the scorer is shown in 12. The criteria for manual scoring are consistent with the standards outlined in the prompt provided to the scorer.

Figure: Figure 12: Prompt for the scorer.

We design a mapping function that converts different combinations of correctness, relevance, and completeness values into a final score, which is shown in Figure 13. Then, a score of 7 or higher is considered sufficiently high, while a score of 1 or lower is considered sufficiently low.

Figure: Figure 13: Mapping function.

## Appendix D Evaluation

The prompt for comparing the response with the ground truth is shown in Figure 14.

Figure: Figure 14: Prompt for comparing the response with the ground truth.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: The results only have one dataset to my understanding. Can this be extended to more datasets?

I have concerns that the rewards model does not generalize outside of this dataset? Or would that simply require more training on bigger datasets?

The ordering of the sections, particularly the related work, and how it reads in context at the end, does not make sense, was this just compiled in the wrong place accidentally?

Are there cases where the scorers are human experts? It was a bit ambiguous as to whether this was in fact the case.
soundness: 2
strengths: The work shows three components which improve the ability of multi-agent LLM systems to improve the results of general LLM queries as compared to current methods.

All three components are shown to meaningfully add to the overall model, and directly tackle the presented critical principles for design.
summary: The paper describes a method for solving queries using a multi-agent system, with multiple agents which are experts in at different sub-tasks. A meta-agent is then required to decompose the queries into multiple sub-tasks that are then allocated to suitable agents for solving them. The authors identified three critical principles for task completion:

That is Solvability - Each sub-task should be solvable by at least one of the available agents. 

Completeness - The set of sub-tasks should include all necessary information from the original query. That is the aggregation of the sub-tasks should have a comprehensive answer to the original query.

Non-redundancy – The set of sub-tasks should not include duplicate or unnecessary elements.

For each of these requirements, should it fail any, the meta-agent is required to revisit the task decomposition and/or task allocation.

To determine if a sub-task is completely resolved you would need to check if any of the agents can solve a sub-task, but due to the overhead required, they create a training dataset for a reward model using the fast decomposition process and a scorer, which evaluates agent response. This reward model is used to reduce the overhead of agent calls. It is used to approximate whether a sub-task is resolved by an agent by check if its score is sufficiently high (above a certain threshold). In cases where this score is not high enough for any agent, the sub-task is deemed to not fit the solvability criteria and the meta-agent replans.

They then explore when sub-tasks are lacking information/ambiguous or are too complex, and use a similarity calculation over the embeddings of the subtasks. If it is too high, there are tasks similar to it and it should be re-described according to the similar representative  sub-task. If it does not meet a threshold then the sub-task is considered too complex and is modified.
A detector is added to check that all key elements of the original query exist in all the sub-tasks, and that no two sub-tasks resolve the same key elements. If either is failed a recommendation based on that key element is made to help remove overlapping subtasks or supplement missing details.
This is evaluated vs a number of baselines and experiments are done based on a numerical reasoning dataset. It is shown to outperform the baselines.

Ablations are done to show that each component adds meaningfully to the model.

The related work is only listed after all the results.
weaknesses: The work is difficult to follow at times, I believe it can be made much clearer, especially with regards to Figure 2. It is difficult to understand this diagram without enough direct context. There is no clear direction that it takes. The detector does not seem to lead to a replan as described.

The ordering of the sections, particularly the related work, and how it reads in context at the end, does not make sense, was this just compiled in the wrong place accidentally?

The results only have one dataset to my understanding. Can this be extended to more datasets?

I have concerns that the rewards model does not generalize outside of this dataset? Or would that simply require more training on bigger datasets?

I believe this work is good and novel, however it could be improved upon with clearer writing.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: * Why is it beneficial to use natural language over PDDL and other languages specifically designed for planning? There are papers on this already [2] so it would make sense to compare to such an approach.
* Similarly, why not represent the agent capabilities in terms of planning operators or some other well-defined formalism rather than (what I presume) is natural language descriptions?
* How do you formally verify that the generated plans are correct and solve the problem?

[2] Translating Natural Language to Planning Goals with Large-Language Models by Yaqi Xie et al.
soundness: 2
strengths: * The problem of multi-agent planning is highly important with high potential impact.
* How to decompose problems into sub-tasks based on the capabilities of the individual agents is often the key problem.
* Learning the capabilities of other agents is a hard and important challenge.
* The paper is easy to follow.
summary: The proposed system uses a LLM to generate a decomposition of a problem into an array of sub tasks that are then allocated to different agents. Then a reward model is used to improve the plan as it is being executed.
weaknesses: * The paper does not relate to the rich and long history of multi-agent planning. A starting point could be [1].
* The design principles seem a bit backwards. Normally, the set of problems that can be solved by a set of agents is defined as the union of the problems that each agent can solve, then you have to check whether the particular problem is within that set. Normally, it is a hard computational problem to determine what problems an agent can solve. If the set of sub-tasks contain redundancy it is either a problem with the planner or there is reason, such as a need to deal with non-deterministic outcomes of actions. To have it as a design principle seems strange.
* In the completeness principle it is mentioned "The array of sub-tasks [...] should include all necessary information" what does this mean? The first principled is defined in terms "resolvable" tasks. The second principle is defined in terms of "necessary information". What is the relation between "necessary information" and "resolvable"?
* It is well known that LLMs cannot generate plans in the sense used in the planning community as there are no guarantees that the plan is correct nor that it actually solves the problem. My impression is thus that the proposed solution is more about learning a model of different agents capabilities than on planning. 


[1] Cooperative Multi-Agent Planning: A Survey. Alejandro Torreño, Eva Onaindia, Antonín Komenda, Michal Štolba. ACM Computing Surveys (CSUR), Volume 50, Issue 6.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 3
questions: 1. In Table 1, in my understanding, the prompt tokens and completion tokens refer to the AVERAGE NUMBER of tokens for EACH task, is it correct? Probably it's better to clarify this in the paper.

2. Is this framework capable of collaborating with multiple agents with the same expertise and improving efficiency? For example, using multiple math agents to solve a complex math problem, while these agents run in parallel.

3. In my understanding, the four agents in the experiment are GPT-4o with different input prompts, are there any additional fine-tuning to improve the expertise of each agent?

4. The paper talks about solvability, completeness, and non-redundancy at the beginning of the paper. Are there any quantitative results showing that the proposed framework addressed these challenges?
soundness: 2
strengths: The paper is well-organized, presenting a detailed and thorough explanation of the proposed framework. A particularly compelling aspect is the approach of breaking down tasks into smaller components and assigning them to specialized agents according to their areas of expertise. This decomposition allows each agent to handle tasks within its domain, enhancing overall efficiency and precision. Additionally, the integration of a feedback system significantly boosts the framework’s performance by refining the agents’ actions and ensuring adaptive learning.
summary: The paper presents a multi-agent framework for problem-solving. In particular, the framework uses a meta-agent to decompose a task into subtasks and assign each subtask to downstream expert agents based on their expertise. Then, it uses a reward model to evaluate the performance of the expert agents and use the rewards as signals for re-planning. Additionally, the framework incorporates a feedback system to further improve the robustness and accuracy of problem-solving. Empirical analysis over a numerical reasoning dataset indicates how the proposed framework outperforms the benchmarks, such as direct query to GPT-4o and chain-of-thought. Additionally, a set of ablation studies necessitates each component, such as the plan detector and the reward model, within the framework.
weaknesses: There are several limitations of the work that the authors may consider to address:

1. Expert agents: the difference between each expert agent is their input prompts, but they are using the same underlying model (GPT-4o). It could be more interesting to replace each expert agent with the current state-of-the-art model in their domain. I believe there are plenty of works to fine-tune the language models for code generation, solving math problems, etc.

2. I don't see the significance of the commonsense agent. Feels like the meta agent is also doing some common sense reasoning (e.g., understanding and decomposing tasks). If possible, please provide some use cases where the commonsense agent is necessary.

3. The cost (time and number of tokens) is high compared to direct querying GPT-4o, given that over 5x cost for only a 10 percent improvement. This probably can be solved by optimizing the expert agents (see point 1).

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: -- See above
soundness: 2
strengths: -- See above
summary: This paper introduces a framework for agent-oriented planning in multi-agent systems, where a central "meta-agent" decomposes complex user queries into sub-tasks, assigns these sub-tasks to specific agents, and evaluates their performance. The authors focus on three key principles, namely, solvability, completeness, and non-redundancy, to guide efficient task decomposition and assignment. The framework also includes a feedback loop, enabling the meta-agent to refine its planning over time.

The framework’s emphasis on structured decomposition and task dependencies is well-suited for complex queries that involve multiple agents with diverse capabilities. By ensuring each sub-task aligns with an agent’s expertise, the system promotes both efficiency and reliability.

I have a few questions:
- Task dependencies are identified during decomposition, but dependencies may also emerge during execution. How does the framework adapt when unforeseen dependencies between sub-tasks arise? Could this affect the overall solvability or efficiency of the task set?

- The framework depends on structured task decomposition, yet real-world environments are often unpredictable and dynamic. How does this approach handle unexpected changes in agent availability or evolving task requirements without needing a complete re-plan?

- Non-redundancy is a key focus, yet redundancy can be valuable for fault tolerance. How does the framework balance efficiency with the potential need for redundancy, particularly in scenarios where backup solutions could be essential?

- The scalability of the approach isn’t clear to me. As the number of agents and interdependent tasks increase, how does the meta-agent manage complexity? Are there limitations on the scale or number of agents?

- The meta-agent requires detailed knowledge of each agent's abilities for effective task allocation. But it isn’t immediately clear to me, how are these capabilities/descriptions in D represented? Can you provide more details?

- Related to the comment above, can you discuss what representation is best suited for agent descriptions? Are these representations task dependent?

- Another follow-up on the above comment, can you discuss about the process/requirements if these representations need to be verified or even updated through the process? How can the approach be adapted to handle such cases?

- While the feedback loop allows for ongoing improvements, how does it prevent instability or oscillations in planning strategies? How would you introduce safeguards into the system or meta-agent to avoid fluctuating between different planning approaches?

Overall, I'm happy with the contributions made in this paper and vote for a weak accept. I'd be happy to raise my score given mine and my fellow reviewers' comments are adequately addressed. Thanks!
weaknesses: -- See above

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: Could you elaborate on how the principles of solvability, completeness, and non-redundancy are uniquely adapted for LLM-based multi-agent systems in this framework?

Could you clarify the unique aspects of your reward model and feedback loop in this framework? How do they differ from traditional surrogate models, and what specific contributions do they offer to agent-oriented planning in LLM-based systems?

What strategies or guidelines do you suggest for fine-tuning the system’s parameters for new datasets or applications? Are there ways to simplify or automate this tuning process to improve usability?
soundness: 3
strengths: This paper proposes an interesting framework for agent-oriented planning in multi-agent systems, including an integrated feedback loop and reward model, which appear to be novel.

This paper is well-structured, with a clear methodology and comprehensive experimental analysis.

This paper is clearly written and well-organized, making the complex concepts of agent-oriented planning accessible.

This paper addresses a crucial challenge in multi-agent systems—optimizing task decomposition and agent coordination, which has substantial implications for practical applications in artificial intelligence.
summary: This paper presents a new framework for multi-agent systems where meta-agents decompose user queries into sub-tasks, allocate these tasks to appropriate agents, and evaluate the results based on three key design principles: solvability, completeness, and non-redundancy. The meta-agent also uses a reward model to assess agent performance and includes a feedback loop for continuous improvement. The proposed framework demonstrates noticeable advancements in solving complex real-world problems by efficiently coordinating agents compared to existing methods.
weaknesses: While this paper explored a very important problem of agent-oriented planning, I do have a few questions/concerns regarding the reported research work:

1. The principles of solvability, completeness and non-redundancy appear to be very general in nature. They may not be entirely new to the field of multi-agent systems or task planning. The novelty may not lie in the principles themselves but in how they are implemented within the specific context of large language models (LLMs) and agent-oriented systems. While the paper integrates these principles into the implementation of a meta-agent, the principles alone may not represent a breakthrough. This paper could benefit from a more detailed discussion of how these principles are uniquely applied in the context of LLM based multi-agent systems. 

2. There seems to be a clear lack of technical details regarding how each agent is constructed, operates, and integrates with the meta-agent. While the paper describes agents such as the “search agent,” “math agent,” and “commonsense agent,” I don't quite understand their underlying architectures and decision-making processes (e.g., the underlying models used for each agent and their training processes). Additionally, the descriptions of agent capabilities seem to be vague. This lack of technical depth makes it difficult to assess the robustness, scalability, and adaptability of the agents, as well as their performance in diverse real-world applications. Without these technical details, the framework’s effectiveness remains partially speculative, relying more on theoretical design principles than on concrete, replicable methods.

3. The reward model developed in this paper operates like a surrogate to predict the performance of using any specific task agent to tackle any given sub-task. The general idea of predicting agents' performance is not new. The concrete design of the network architecture and the training algorithm for the reward model may be new. However, the corresponding technical contribution was not clearly highlighted and justified. The same concern also applies to the feedback loop, which is commonly used to update the surrogate models in the literature. Its novelty under the newly proposed framework may need to be better elucidated. Potentially, this paper may benefit by providing a more detailed comparison with existing surrogate models or a clearer explanation of how their approach differs from standard feedback loops in the literature.

4. This paper introduces multiple algorithm/system parameters, such as reward model thresholds, agent selection criteria, and similarity measures, which may be challenging to fine-tune. This complexity makes it potentially difficult to adapt the proposed multi-agent system to new datasets or applications, as optimal tuning may require deep domain-specific knowledge and extensive experimentation, further affecting the system’s usability. In line with this concern, it might be helpful for the authors to provide some concrete guidelines or heuristics for parameter tuning, or to discuss potential strategies for automating or simplifying this process for new datasets or applications.

5. The experimental evaluation in the paper appears to be limited in scope, as it primarily focuses on a single numerical reasoning dataset. It remains questionable whether the newly developed multi-agent system can generalize well across diverse real-world tasks or more complex, domain-specific applications. Hence, the authors may need to discuss potential challenges in applying their system to more diverse or complex tasks.

Meta-review: The paper concerns solving problems in a multi-agent context, with multiple agents that have different expertise. The authors propose to use an LLM meta agent that decomposes the queries into sub-tasks and allocates the subtasks to the agents. 

The reviewers agree that the paper has merit, in particular, appreciating the three meaningful and structured components for task completion.

Most of the weaknesses evolve around the writing, the related work on multi-agent planning, and how the method generalizes. Most of these concerns were mitigated during the discussion phase, and we recommend acceptance of this paper.

Decision: Accept (Poster)