Chain of Agents: Large Language Models Collaborating on Long-Context Tasks

Thank you for the valuable suggestions. We provide answers to all your weakness points and questions below. We hope these resolve your concerns.

W1: Novelty and other baselines:

While chunking the input into multiple segments seems intuitive, the novelty of CoA lies in the chain communication of multiple agents using natural language on inputs, which is not explored by previous studies.

LongAgent [1] does not allow communication between workers, making it hard for each worker to understand what is happening at other agents, hurting the performance of tasks that need long dependency. Besides, the authors of LongAgent state that the decomposition of the question also is a limitation for LongAgents. The failure of decomposition multi-hop or complex questions would directly lead to wrong answers. Additionally, some of the structures of LongAgents are transferable to CoA, such as conflict resolution. In contrast, CoA concentrates on improving the long dependency reasoning (such as multi-hop question answering) and does not depend on the decomposition capability of the manager.

Regarding RecurrentGPT [2], although it uses a chain structure to do long story generation, the task and motivation are different. They focus on memorizing the context to have a better plan to generate a longer story. In contrast, CoA focuses on the long-dependency and complex reasoning of the source text rather than output.

We also compare the performance of CoA with RecurrentGPT and LongAgent, where COA outperforms LongAgent by 16% on NIAH tasks and outperforms RecurrentGPT by 20% on Hotpot QA . More results can be found in GR 2 and Figure 2 in PDF. The results are listed in the Table:

W2: Stronger baselines:

We believe the baselines used are already strong given the literature in this direction. We are open to benchmarking on any specific suggestions. We have considered other baselines that we modified as they were weaker. For example, WalkingMaze [5] also split the input into chunks; we found it did not work for our task (less than 40% on HotpotQA). Thus, we modify its structure and build a new baseline named Hierarchical which obtains a much stronger performance (50.62% on HotpotQA).

Also, as stated in W1, LongAgents and RecurrentGPT performances are much lower than CoA and thus weaker than the multiagent baseline we have used.

We have further added comparisons of CoA with the previous SOTA below, even including the ones requiring training (indicated with *). As can be seen, CoA achieves better or comparable results on all datasets, improving HotpotQA and RepoBench-p by a large margin. The performance on some datasets is lower than SOTA because the datasets are trained on some domain-specific models, such as Qasper

We will include WalkingMaze, LongAgents, RecurrentGPT, and other SOTA models in our final paper. Thank you for the great suggestions!

W3: More agent collaboration:

We aim to emphasize a simple yet effective framework with strong performance to create a higher impact. It is indeed helpful to include more analysis and another complex framework, we prefer to use this paper to demonstrate the potential of chain communication. As mentioned by Reviewer vGWD and FiRU, being simple and intuitive but effective are the first strengths of the proposed framework.

As described, we have experimented with fairly complex agent collaboration, including bi-directional, permutation, hieratical (multi-layers of information processing), WalkMaze, RecurrentGPT, etc, and the current CoA framework performs the best. In the future, we want to explore more directions, such as high efficiency in communication, complex communication schema, etc.

Q1 Chunking: Please refer to the Algorithm in pdf. While there is a small risk of chunking text in the middle, CoA is robust to chunking because the information of previous segments is sent to the next agent for processing, while other baselines such as LongAgents cannot communicate with siblings, losing the context if chunking in the middle.

Q2 Information loss: This happens in CoA occasionally and is neglectable. We have added an analysis to further probe the information loss, as described in W3 of Reviewer FiRU. It shows that COA ensures final results yielding negligible information loss (only 1%-4%).

Q3 Time complexity: It should be O(k^2) because auto-regressive LLMs such as GPT and LLaMA only pay attention to the left side of the input. Thus, each token generated will attend to $k$ tokens [6]. We will clarify this in our paper.

[1] Llm maybe longlm: Self-extend llm context window without tuning. ICML 2024.

[2] Scrolls: Standardized comparison over long language sequences. EMNLP 2022.

[3] Zeroscrolls: A zero-shot benchmark for long text understanding. EMNLP Findings 2023

[4] RST-LoRA: A Discourse-Aware Low-Rank Adaptation for Long Document Abstractive Summarization. NAACL 2024.

[5] Walking down the memory maze: Beyond context limit through interactive reading. arXiv, 2023.

[6] Improving language understanding by generative pre-training. arXiv, 2018.

Thanks so much for carefully reading our responses, and providing such insightful questions and thoughts! Below, we first re-state our novelty aspects more clearly and then comment on the raised concerns one by one, hoping to make our claims clearer to you and address your concerns!

CoA has a unique positioning in the multi-agent LLM literature. The table below illustrates the comparison of related work and their topologies (after carefully reading the survey [1], [2], and other literature). Broadly, prior work on multi-agent LLM systems for long input tasks has a centralized design, and existing decentralized designs do not extend effectively to long context tasks. To the best of our knowledge, CoA is the first to use a centralized structure on long input tasks and is more effective than baselines such as WalkMaze and RAG.

Besides, our contribution is not to claim a new topology for communication. The challenge of long dependency on long input tasks is well-known and remains under-explored (as illustrated with the sample in Part 2). Our target is to novelly mitigate challenging context dependency issues in long-context tasks particularly those requiring complex reasoning. Thus, it is better if we can find a simpler yet effective approach. To this end, we explored various structures (WalkMaze, Merge, Debate, Group Discussion, etc.) and found that a variant of decentralized well-existing chain communication and this simple approach can work more effectively than others. Our contribution is not to claim a new topology for communication but to mitigate a challenging issue (long dependency) with a simple intuitive approach (decentralized chain communication). In addition, CoA is not in conflict with existing work as it can be considered as a plugin for other multi-agent LLM systems (e.g. serve as an additional stage in LongAgent) to improve them.

Specifically, previous work for long input tasks, despite showing significant improvements, usually uses disentangling algorithms such as question decomposition, to address long dependency, and then they use centralized structure to answer the disentangled questions one by one. Different from them, CoA does not disentangle the question but leaves the entire question to the agents. Although chain communication is well-introduced in the literature, to the best of our knowledge, CoA is the first work to apply decentralized communication to long-term dependency challenges - please let us know if there is any paper we are missing on this. We show the high effectiveness of CoA in mitigating agent dependency issues for long inputs and we believe it would constitute a significant value add in the multi-agent system literature. We will better clarify these novelty points in the Introduction section of our paper.

Below are the detailed answers to specific points:

various communication mechanisms exist in multi-agent systems

Indeed, chain communication has been introduced as a very simple topology of communication. Our contribution is not to claim a new topology for communication but to mitigate the challenge of long dependency. We bring a novel perspective to the challenge with the simple chain communication mechanisms. Also, to the best of our knowledge, CoA is the first to use a decentralized structure on long input tasks (see table above). We note that no other multi-agent method in the literature has such results of outperforming RAG for long inputs.

the central agents in centralized communication essentially function as the communication units described in your paper.

Although they all accomplish the task of communication, we think these two types of communication, centralized communication (e.g., LongAgent) and decentralized communication (our CoA), differ in their approach to solving long context dependency issues. When a centralized approach faces a multi-hop question, it leverages question decomposition to disentangle the long dependency issue, while decentralized communication leverages the interleaved reading-processing. Below is an example:

Question: Who is the grandson of A?
Source: [1],[2],[3],[4] (chunks)
Evidence in each chunk: [1: A’s husband is D], [2:  A’s son is B], [3: No evidence], [4: B’s son is C]

Centralized communication (e.g., LongAgent):

Round 1: 
Manager: Who is the son of A?
Worker with [2]: It is B!  Others say unknown
Round 2: 
Manager: Who is the son of B?
Worker with [4]: It is C. Others say unknown
Final answer: It is C.

In this approach, a worker with [i] and a worker with [i+1] do not communicate. Thus, it is difficult to deal with the dependency when the answer to the question is split into the end of agent i and the start of the agent i+1.

Decentralized communication (Our CoA):
Manager: Who is the grandson of A?
Workers: [1]: A’s husband is D (topic exploration), [2]: A’s son is B (answer first hop), [3]: A’s son is B (forward previous evidence), [4]: A’s son is B, B’s son is C. Thus, A’s grandson is C. (complete reasoning)
Final answer: It is C

This exemplifies how adjacent workers communicating in CoA would differ from the centralized one as CoA agents receive previous evidence in addition to the question itself.

We want to emphasize that LongAgent and our work are solving the long context problem in different ways, and they are not in conflict with each other. They can be merged into a much stronger framework (e.g., adding our chain reference stage to mitigate context dependency issues before the stages in LongAgent).

Could you clarify how CoA addresses this issue? From my understanding, CoA does not involve the decomposition of the input question.

The key aspect of CoA decentralized communication is that workers can communicate so that the question does not need to be decomposed. Our experiments highlight the effectiveness of this design, especially when question decomposition is difficult. For instance, when the passage does not mention “A’s son” directly but mentions “A’s husband is D”, and mentions “D’s son is B”, the first question in the centralized approach should be “Who is A’s husband” rather than “Who is A’s son”, which is difficult to propose.

However, this further diminishes the novelty of the proposed method.

We acknowledge that chain communication is not first used in our work. But we are the first ones that use chain communication for long dependency in the input of long context tasks and we show its effectiveness on generic tasks. This approach is independent of RecurrentGPT, as RecurrentGPT solves long output. For the output, the issue they mitigate is memory and planning for story generation tasks. Combining CoA and RecurrentGPT to solve Long-Input-Long-Output generation could be promising as well and we leave that to future work.

many components of the proposal are common practices in multi-agent system design and long-content generation/processing.

We truly appreciate your thoughtful summary. We understand your concerns and would like to re-emphasize the value of our contributions: our work presents a novel and straightforward solution to the long-standing challenge of long context reasoning, and our results demonstrate significant effectiveness. We are hopeful that our findings will inspire further innovation in the research community, encouraging others to integrate our simple yet powerful components into their future work in multi-agent systems.

it should be comprehensively tested as a stronger baseline (e.g. LongAgent) across all benchmarks you tested.

Thanks for the suggestion. Indeed, LongAgent is an important work in this direction. We try to compare all datasets in our paper. However, they did not open source their code, making it difficult to reproduce and compare with them fully in this short-time rebuttal window. Since we found that CoA is 15% higher than that of LongAgent (97% vs. 82%) on NIAH PLUS (Figure 2 in pdf), we believe that given the strong improvement, the performance of CoA will be promising. We will include detailed comparisons across all datasets in the final version of our paper.

We hope our response has addressed your concerns and clarified the contributions of our work. We welcome any further questions you may have and would be happy to provide additional clarification if needed. We deeply appreciate the time and effort you've taken to provide feedback on our work.

Thank you for the valuable feedback. We appreciate your time and efforts spent on this paper. With your insightful suggestions, our paper can improve significantly.

Complexity in Implementation

Indeed, one of the design principles behind CoA is to propose a simple yet effective multi-agent system with multiple agents collaborating towards solving a complex task, unlike many other works on multi-agent system design. As can be inferred from the pseudocode in Algorithm 1 in the paper, the proposed approach is very straightforward to implement - with only O(100) lines of code for the end-to-end system. Also, due to its training-free nature, it is not necessary to prepare a training code for it, and the end-to-end system can be effectively operationalized in a highly controllable way. We will also release our code upon acceptance to further help the community implementing the approach. Besides, we compare the time complexity in GR 3, further demonstrating the practicality for deployment, for even scenarios with tight latency budgets.

Communication Overhead

We compare the time cost of full-context input and Chain-of Agents theoretically in a decoder-only setting. We assume the response generated by LLMs contains r tokens on average, the input has n tokens, and the context limit of LLM is k. The time complexity is shown in Table 2 (Appendix A). As can be seen, the encoding time of CoA is less than Full Context because $k << n$ in long context tasks, while they have the same decoding time. This demonstrates the efficiency of CoA compared with the Full-Context baseline.

We have also conducted an experiment of communication cost and latency tests. We run an analysis to show the practical time consumption of the proposed CoA on the HotpotQA dataset. We choose to use LLaMA-3-8b as the backbone model for preventing additional latency due to the network of API queries. As can be seen in the table, Vanilla consumes the least amount of tokens and generates the least of tokens as well. However, it truncates the input thus maintaining a low performance. Although RAG generates fewer tokens than CoA (by adding RAG and downstream input together), it needs to read the whole input by Retrieval models which is also time-consuming. Overall, RAG is faster than CoA by only ~30% in this example.

Parallel decoding analysis: For decoder-only LLMs, the agents can run in parallel. Before CUs are produced, agents can start to read their assigned paragraphs and wait for the CUs to come. Unfortunately, current APIs or models do not support such dynamic reading. Thus, we conduct an approximation by asking the model to generate one token for each sample. The output time is shown to be short and negligible, mimicking the encoding time of each sample. We have found that the running time of CoA can be reduced by 57.21% on average, leading to a 1.32-second running time for each sample, closing to the running time of the Vanilla baseline! We will integrate discussions on this speedup approach in the final version of the paper.

Evaluation Scope:

We have further conducted evaluations on the NIAH test. We follow the LongAgent [1] paper to run a NIAH PLUS test for evaluating the long context understanding capability of LLMs. Different from the original NeedleInAHaystack test, NIAH PLUS is more challenging because LLMs need to answer the questions rather than simply retrieve the information (needle). The results are shown as follows:

[1] Zhao J, Zu C, Xu H, et al. LongAgent: Scaling Language Models to 128k Context through Multi-Agent Collaboration[J]. arXiv preprint arXiv:2402.11550, 2024.

Q1 Performance on Smaller long context models: We have added experiments with Llama-3-8b on the NarrativeQA dataset, and the results are listed in the table below. As can be seen, the CoA framework on such LLMs can also boost the Vanilla performance a lot by 10.27% and surpass the RAG score by 5.9%! Noting that there is more space to improve since the prompt of LLama-3 is not even adjusted for this experiment.

Q2 Output Token Cost: Regarding output tokens, we compute the average token generated by the model in General Response 3. As shown in the table, CoA outputs more tokens than vanilla and RAG baselines because it needs to produce CUs and final results. We found that the relation between generated tokens and workers holds an almost linear correlation, showing that basically, each worker generates the same amount of tokens. Including one more agent will increase around 11.3 total generated tokens.

Q3 Full-200k Chunking: It is the same as Vanilla (8k). Please refer to the Algorithm in pdf. We first split the source into $n$ sentences, then we add $i$-th sentence to the input one by one so that the total length is less than the context window limit while $i+1$ sentences are longer than the total length.

Dear Reviewer,

Since we are approaching the end of the discussion period, we are wondering if you have had the chance to review our response to your feedback. We would like to kindly inquire about the extent to which we have successfully addressed the concerns outlined in your review. We greatly value your feedback and would appreciate any further questions or comments you might have. Thank you for your time and consideration.

Sincerely,

All Authors

We are glad to know our responses addressed your concerns! We would also like to thank you for your thoughtful questions and insightful discussion, and we will include all our discussion results in the final version.

Thank you so much for your detailed feedback and for acknowledging the comprehensiveness of our experimental studies. We address the questions and concerns raised below, one by one.

W1: Human motivation: To clarify this point, the motivation is that humans would not try to read the whole textbook and then start to do reasoning. Instead, it is better for them to learn one section and do exercises over it then move to the other one with the memory of the previous section because the human has limited working memory [1], similar to LLMs. This inspires proposing an approach based on interleaved reading, as one of the fundamental principles of CoA, rather than putting all information in one window and processing the information (read-then-process).

W2: BookSum results: Thanks for the great suggestion. Following the suggestion, we have run the BookSum dataset with Text-bison and Text-unicorn models. As shown in the table below, similar to the results with the LLMs that support longer contexts, CoA outperforms baselines by a significant margin. We will add these results and discussions to the paper.

W3: information loss: We have added an analysis to further probe the information loss. For each sample, we compute the highest score between the communication unit and the gold answer, and if this score is higher than the score of the final prediction, we compute the difference and refer this information loss, as formulated below:

$Loss = max(0, \max_{i=0}^{l} score(CU_i, Y) - score(\hat{Y}, Y))$

The estimated information loss results of various datasets of CoA withext-bison are as follows:

This table shows that if choosing the communication unit with the highest performance, around 1%-4% performance gain can be obtained, meaning that 1%-4% of the information is lost during the chain communication. While every method might have information loss, COA design ensures final results yielding negligible information loss.

However, although sometimes the information is lost, "it is still acceptable within the overall framework as we tested using all CUs as the input to the manager and observed a 5% performance drop (Page 4, footnote). We leave mechanisms to further mitigate information loss to future work of multi-agent communication.

W4: Handling complex reasoning: We do not give LLMs a predefined plan. When the CoA starts to process, the agents automatically explore the nodes and leave the processed information for the next agent. However, we indeed observed some patterns: 1) the first worker usually explores the most number of paths, including 3 or more topics because the agent is not sure about the result and willing to provide more information for the next ones. 2) The final worker usually narrows down to one answer with a much shorter CU, and 3) The speed of narrowing down will be faster for simpler samples, producing a small reasoning graph.

W5: Agent communication one directional or more: Thanks for pointing this out. We agree that we have agent-to-agent communication in one direction and the communication is critical for performance. We will clarify the definition in the next version, such as renaming it as a Unidirectional Communication Unit. Regarding the design choices, we used unidirectional rather than bi-directional (or more complex communication) because experiments show that the bi-directional (or more complex communication) communication of two agents sometimes brings more noise and hallucinations thus hurting the performance.

W6 Actual inference time: We further analyze the actual time cost of running samples. Please refer to GR 3 for more details.

W7 Related work discussion: Thanks. We will add the following papers and compare them with them in the next version.

[1] Cowan N. Working memory underpins cognitive development, learning, and education[J]. Educational psychology review, 2014, 26: 197-223.

Dear Reviewer,

Since we are approaching the end of the discussion period, we are wondering if you have had the chance to review our response to your feedback. We would like to kindly inquire about the extent to which we have successfully addressed the concerns outlined in your review. We greatly value your feedback and would appreciate any further questions or comments you might have. Thank you for your time and consideration.

Sincerely,

All Authors

We thank the reviewer for their insightful feedback that has helped us to improve our submission!

W1: Technique depth.

The depth of our work lies in that we propose Chain-of-Agents, a multi-agent LLM collaboration framework for solving long context tasks. It is a training free, task/length agnostic, interpretable, and cost-effective framework. CoA (1) can generalize to many tasks, (2) achieve considerable improvements, (3) while the framework is simple, including diverse communication patterns. Our experiments show that Chain-of-Agents outperforms commonly-used RAG and Long Context LLMs by a large margin despite its simple design.

W2 (1) Is summarization all that’s being done?

We would like to clarify that CoA’s applicability is not restricted to the summarization task. While the communicated results summarize the contents in the source, CoA agents play various roles beyond summarization, because they perform content selection, information aggregation, context utilization, and reasoning abilities to solve complex problems from diverse tasks. such as extracting and refining information through agent communication, and performing analysis and reasoning with them. Tables 11-13 exemplify CoA agents' capabilities to generate evidence for answering the query, a summary of chunks, and code comments and usages.

W2 (2) Naming as Chain of Agents:

We name it an \it{agent} for two reasons. First, chain-of-agents contain two different roles, including manager agent and worker agents. Worker agents analyze, aggregate, and digest segment information, whereas manager agents synthesize these contributions into a coherent final output worker. Second, we employ agents to emphasize “communication” between agents. We will clarify this.

W3: Comparison with SOTA:

We choose RAG and Full-context as baselines because they represent the commonly-used and solid approaches of input reduction and window extension. Thanks for your great advice. We have further added comparisons of CoA with the previous SOTA below, even including the ones requiring training (indicated with *). As can be seen, CoA achieves better or comparable results on all datasets, improving HotpotQA and RepoBench-p by a large margin. The performance on some datasets is much lower than SOTA because the datasets are trained on some domain-specific models, such as the Qasper dataset

W4 Clarification of Figure 1:

We have revised Figure 1 in pdf. The new figure clarifies the working flow and communication units. It is worth noting that the blue boxes on the left are CUs themselves.

Q1 Context window sizes:

We show that the CoA becomes stable when the context window is larger than 8k, We also find it can improve the baseline with various window sizes. As shown in Figure 6, the performance becomes stable when it is larger than 8k. We have further analyzed different agent lengths and reported the scores of text-bison on the NarrativeQA dataset in the following table. Our results show that it can improve the baseline with various window sizes. Thus, we choose 8k for short context models, such as text-bison.

Q2 Is RAG well-optimized?:

The specific RAG [5] implementation we use is indeed well-optimized. It is the SOTA model from the RAG MTEB leaderboard on Hugging Face, and we follow the recent approaches that combine RAG and LLM for the best prompting. Moreover, the RAG model is fine-tuned on the HotpotQA dataset, making it even better adapted for the tasks as the HotpotQA dataset is evaluated in this paper. Overall, CoA outperforming such an optimized RAG implementation highlights the effectiveness.

Q3 Time complexity analysis:

We agree that RAG can be more beneficial due to inference speed. However, it hurts the performance because semantic similarity cannot ensure retrieval of the needed information. It is difficult for RAG models to answer the question that needs multiple reasoning hops (such as multihop-QA) or entire input tokens (such as counting tokens in a passage). We compare the time complexity of RAG with CoA and will add the table in the final version. $k’$ is the chunk size of the RAG model, $k$ is the context window of downstream LLMs, $r$ is the average response length and $n$ is the input source length. We have also compared the time cost and show that RAG is around 30% faster than CoA. Moreover, CoA can be further improved by parallel reading. Please refer to GR 3 for details of inference speed analysis.

[1] Jin et al. Llm maybe longlm: Self-extend llm context window without tuning. ICML 2024.

[2] Shaham et al. Scrolls: Standardized comparison over long language sequences. EMNLP 2022.

[3] Shaham et al. Zeroscrolls: A zero-shot benchmark for long text understanding. EMNLP Findings 2023

[4] Pu D, Demberg V. RST-LoRA: A Discourse-Aware Low-Rank Adaptation for Long Document Abstractive Summarization. NAACL 2024.

[5] Xiao S, Liu Z, Zhang P, et al. C-pack: Packaged resources to advance general chinese embedding. SIGIR 2024.

Dear Reviewer,

Since we are approaching the end of the discussion period, we are wondering if you have had the chance to review our response to your feedback. We would like to kindly inquire about the extent to which we have successfully addressed the concerns outlined in your review. We greatly value your feedback and would appreciate any further questions or comments you might have. Thank you for your time and consideration.

Sincerely,

All Authors