[Paper] Chow-Liu Ordering for Long-Context Reasoning in Chain-of-Agents

Source: arXiv - 2603.09835v1

Overview

The paper introduces Chow‑Liu Ordering, a simple yet powerful technique for improving long‑context reasoning in the Chain‑of‑Agents (CoA) framework. By re‑ordering document chunks based on learned statistical dependencies, the authors dramatically reduce the information loss that normally occurs when multiple LLM‑driven agents process a long input sequentially. The result is higher answer relevance and exact‑match accuracy on several demanding benchmarks.

Key Contributions

• Dependency‑aware chunk ordering: Leverages Chow‑Liu tree structures to capture pairwise statistical relationships between document chunks.
• Breadth‑first traversal strategy: Proposes a concrete ordering rule (BFS on the learned tree) that prioritizes strongly related chunks early in the processing pipeline.
• Empirical validation: Demonstrates consistent gains over naïve (original) ordering and semantic‑score based ordering across three long‑context reasoning benchmarks.
• Framework‑agnostic insight: Shows that the ordering improvement is orthogonal to the underlying LLM or memory‑management scheme, making it applicable to any CoA‑style system.

Methodology

1. Chunk the long document – The input is split into fixed‑size chunks that fit within the bounded shared memory of the CoA agents.
2. Estimate pairwise dependencies – Using a modest corpus of similar documents, the authors compute mutual information between every pair of chunks (e.g., via token‑level co‑occurrence statistics).
3. Build a Chow‑Liu tree – The mutual‑information matrix is fed to the Chow‑Liu algorithm, which constructs a maximum‑weight spanning tree that approximates the full joint distribution with a tree‑structured graphical model.
4. Derive processing order – Starting from the tree root (chosen as the chunk with highest marginal relevance), a breadth‑first search (BFS) visits neighboring chunks before moving deeper. This ordering ensures that when an agent processes a chunk, it already has access to the most strongly related context that has been stored in memory.
5. Integrate with CoA – The reordered chunks are fed to the standard CoA pipeline: each worker LLM reads the current chunk plus the bounded shared memory, updates the memory, and passes it to the next agent.

The approach requires only lightweight statistical preprocessing and does not modify the LLMs themselves.

Results & Findings

• Answer relevance (measured by ROUGE‑L) improved by 3–5 pts over the best baseline.
• The BFS ordering consistently reduced the information loss metric (a proxy for how much of the original joint distribution is retained) by ~12 % compared with the default ordering.
• Ablation experiments confirmed that the gains stem from the dependency‑aware ordering rather than simply processing “important” chunks earlier.

Practical Implications

• Better use of limited context windows: Developers building LLM‑powered agents (e.g., retrieval‑augmented QA, multi‑step planning) can plug the Chow‑Liu ordering step into their preprocessing pipeline to squeeze more reasoning power out of the same memory budget.
• Scalable multi‑agent pipelines: The method is computationally cheap (O(N²) for N chunks) and can be pre‑computed offline for static corpora, making it suitable for production systems that need deterministic latency.
• Improved downstream tools: Code assistants, legal document analyzers, and scientific literature summarizers that rely on long‑context reasoning can achieve higher fidelity answers without retraining or fine‑tuning the underlying LLM.
• Framework‑agnostic: Since the ordering is independent of the LLM architecture, it can be combined with emerging memory‑augmented models (e.g., Retrieval‑Augmented Generation, Retrieval‑Enhanced Transformers) for additional gains.

Limitations & Future Work

• Dependency estimation quality depends on the availability of a representative corpus; rare or highly domain‑specific documents may yield noisy mutual‑information estimates.
• The current approach assumes a single static ordering per document; dynamic re‑ordering during inference (e.g., based on intermediate agent outputs) could further reduce loss but is not explored.
• The study focuses on textual chunks; extending the method to multimodal inputs (images, tables) would require more sophisticated dependency metrics.
• Future work may investigate integrating the ordering step directly into the training objective of the agents, or learning the tree structure jointly with the LLM’s internal attention patterns.

Authors

• Naman Gupta
• Vaibhav Singh
• Arun Iyer
• Kirankumar Shiragur
• Pratham Grover
• Ramakrishna B. Bairi
• Ritabrata Maiti
• Sankarshan Damle
• Shachee Mishra Gupta
• Rishikesh Maurya
• Vageesh D. C

Paper Information

• arXiv ID: 2603.09835v1
• Categories: cs.CL
• Published: March 10, 2026
• PDF: Download PDF