LLM×MapReduce: Simplified Long-Sequence Processing using Large Language Models

Conference: ACL 2025
arXiv: 2410.09342
Code: https://github.com/thunlp/LLMxMapReduce
Area: LLM/NLP
Keywords: Long-context processing, Divide-and-conquer strategy, MapReduce, Context extension, Training-free framework

TL;DR

LLM×MapReduce is proposed, a training-free divide-and-conquer framework that addresses inter-chunk dependency and inter-chunk conflict after chunking long texts using a structured information protocol and an in-context confidence calibration mechanism. This enables LLMs with an 8K context to effectively process long texts exceeding 100K or even 1280K tokens, outperforming long-context models such as GPT-4.

Background & Motivation

Background: LLMs exhibit excellent performance on tasks like question answering and code generation, but most models are constrained by limited context windows (e.g., 8K tokens). Methods for extending context windows are categorized into two types: training-based methods (e.g., RoPE frequency scaling, LongLoRA) require massive long-text data and computational resources; training-free methods (e.g., sliding window attention, divide-and-conquer) attempt to bypass length limits without modifying parameters.

Limitations of Prior Work: The core challenge of divide-and-conquer methods (such as LangChain's MapReduce, LongAgent, Chain-of-Agents) is that splitting long texts into short chunks destroys critical long-range information. This manifests as two main issues: (1) inter-chunk dependency, where evidence is scattered across different chunks and must be associated to derive the correct answer; and (2) inter-chunk conflict, where evidence in different chunks contradicts each other, requiring the model to determine which is more reliable.

Key Challenge: LongAgent aggregates answers by randomly selecting representatives, which easily loses key evidence; CoA processes sequentially and cannot explicitly resolve conflicts; LC-Boost relies on cumulative summarization and struggles to handle complex conflicts between historical and current information. Existing divide-and-conquer frameworks lack effective mechanisms for managing inter-chunk information.

Goal: To design an efficient divide-and-conquer framework for long-text processing that simultaneously addresses the core problems of inter-chunk dependency and inter-chunk conflict.

Key Insight: It is observed that the key to a divide-and-conquer framework lies in "what information" is passed from the map phase to the reduce phase. If the information is too simple, key details are lost, leading to dependency breakage; if it is too complex, noise and computational overhead are introduced. Furthermore, answers from different chunks require a unified and comparable confidence standard to resolve conflicts.

Core Idea: By standardizing the format of information transmission from map to reduce using a structured information protocol, coupled with in-context confidence calibration to make confidence scores across different chunks comparable, inter-chunk dependencies and conflicts can be efficiently resolved.

Method

Overall Architecture

LLM×MapReduce adopts a three-stage pipeline: Map \(\rightarrow\) Collapse \(\rightarrow\) Reduce. The input long text \(X\) is split into multiple short chunks \(\{x_1, x_2, \ldots, x_n\}\), where the length of each chunk does not exceed the model's effective context length \(L\). The Map phase extracts structured information from each chunk. The Collapse phase compresses intermediate results so that their total length does not exceed \(L\) (which can be executed iteratively). The Reduce phase aggregates all compressed results to generate the final answer. The entire process does not require tuning any model parameters and implements three functions solely through prompting.

Key Designs

1. Structured Information Protocol:

   • Function: Standardizes the format of the information output during the map phase, ensuring the reduce phase has sufficient information to handle inter-chunk dependencies.
   • Mechanism: The map output of each chunk contains four components: Extracted Information (key facts relevant to the query), Rationale (reasoning process to prevent hallucination in subsequent stages), Answer (intermediate answer, outputting "NO INFORMATION" when there is no information), and Confidence Score (a confidence score of 1-5). The output of the Collapse phase maintains the same structure.
   • Design Motivation: Methods such as LongAgent output oversimplified answers that lead to loss of detail, whereas the structured format of extracting key information and reasoning processes retains the context required for inter-chunk reasoning while keeping the amount of information from overloading.

2. In-Context Confidence Calibration:

   • Function: Makes confidence scores of different chunks comparable, assisting the reduce phase in resolving inter-chunk conflicts.
   • Mechanism: Provides confidence evaluation principles and typical examples of different levels through in-context learning—statements fully supported by the text receive high confidence, model inferences receive medium confidence, and text-unrelated statements receive low confidence. The model references these principles and examples to apply a consistent evaluation standard to each chunk.
   • Design Motivation: When different chunks are processed independently, the model might assign vastly different confidence levels to equally reliable content. The calibration mechanism unifies the scoring standard, making conflict resolution more reliable.

3. Collapse Stage Iterative Compression:

   • Function: Compresses map results within the model context limit when processing extremely long texts.
   • Mechanism: Groups \(N\) map results into \(K\) groups, and uses the LLM to compress each group into a structured output (maintaining the same four-component format as the map output). If the length still exceeds the limit after compression, the process is executed iteratively until the total length is within \(L\).
   • Design Motivation: For extremely long texts (e.g., 128K+ tokens), all intermediate results from the map phase may still exceed the context window, necessitating hierarchical compression.

Loss & Training

Training-free strategy—all three stages (map, collapse, reduce) are implemented on existing LLMs using meticulously designed prompts, requiring no parameter tuning or additional training data.

Key Experimental Results

Main Results

Evaluated on InfiniteBench (average input length exceeding 100K tokens):

Method	Re.Avg	En.Avg	Co.De	Ma.Fi	Overall Average
GPT-4	96.33	14.89	54.31	60.00	57.34
Qwen2-72B-I (128K)	76.33	25.54	45.43	59.71	54.74
L3-70B-I + LongAgent	88.99	15.00	24.11	79.14	53.81
L3-70B-I + CoA	8.24	8.88	18.27	44.57	15.97
L3-70B-I × MR	99.56	41.23	62.94	91.43	68.66

Ablation Study

Configuration	Re.Avg	En.Avg	Co.De	Ma.Fi
Full model	99.56	41.23	62.94	91.43
w/o Confidence Calibration	96.00	39.18	58.12	90.00
w/o Structured Protocol	97.14	25.93	46.45	56.00

Key Findings

• LLM×MapReduce (using Llama3-70B with an 8K context) achieves an overall average score of 68.66, outperforming GPT-4 (57.34) and Qwen2-72B (54.74) with a 128K context.
• The structured information protocol contributes significantly: removing it causes En.Avg to plunge from 41.23 to 25.93, and Ma.Fi to drop from 91.43 to 56.00.
• Successfully extends to 1280K tokens in the NIAH test, proving the extreme long-text processing capability of the framework.
• The inference latency is unexpectedly lower than standard decoding and other divide-and-conquer methods, as it avoids repeatedly processing text chunks to resolve conflicts.
• A significant advantage of the divide-and-conquer method: only 2 GPUs are needed to process 128K tokens, whereas standard decoding requires at least 4 GPUs.

Highlights & Insights

• Meticulous design of the structured information protocol: The four components (facts, reasoning, answer, confidence) not only meet the requirements of inter-chunk reasoning but also introduce Chain-of-Thought concepts through the Rationale component, reducing hallucinations.
• Confidence calibration is a crucial link: Achieving unified scoring standards via in-context learning instead of additional training is extremely low-cost yet highly effective.
• Generality of the framework: It is not bound to a specific LLM and is compatible with various models such as Llama3-70B and Qwen2-72B, functioning as a plug-and-play long-text processing layer.

Limitations & Future Work

• Divide-and-conquer methods are inherently challenged by tasks requiring global context (such as full-text style analysis), as structured information may fail to capture all types of global dependencies.
• Confidence calibration relies heavily on prompt design, and different tasks may require customized calibration rules.
• Information compression in the Collapse phase may lose key details in extreme scenarios.
• Future work could explore adaptive chunking strategies (chunking based on semantic structure of the text rather than fixed lengths) and multi-turn interactive reduce.

Related Work & Insights

• vs LongAgent: LongAgent employs a leader-member multi-agent architecture, but randomly selecting representatives easily loses key evidence. Ours uses structured information to retain the complete reasoning chain, achieving better results.
• vs Chain-of-Agents (CoA): CoA sequentially processes chunks and accumulates summaries without explicitly handling conflicts. Ours uses confidence calibration to explicitly resolve conflicts, outperforming CoA on almost all subtasks.
• vs LC-Boost: LC-Boost defines an action space for sequential processing, but struggles to fully resolve conflicts between historical and current information using only cumulative summaries.

Rating

• Novelty: ⭐⭐⭐⭐ The combined design of the structured information protocol and confidence calibration is ingenious, but the divide-and-conquer framework itself is not entirely novel.
• Experimental Thoroughness: ⭐⭐⭐⭐⭐ Incredibly comprehensive, featuring InfiniteBench + NIAH 1280K + latency analysis + ablation studies.
• Writing Quality: ⭐⭐⭐⭐⭐ The problem definition is clear, the method description is systematic, and the experimental comparisons are fair.
• Value: ⭐⭐⭐⭐ Provides a practical and efficient plug-and-play solution for limited-context LLMs to process long texts.

Related Papers

• [ACL 2025] Automated CAD Modeling Sequence Generation from Text Descriptions via Transformer-Based Large Language Models
• [ACL 2025] Internal and External Impacts of Natural Language Processing Papers
• [ACL 2025] LR²Bench: Evaluating Long-chain Reflective Reasoning Capabilities of Large Language Models via Constraint Satisfaction Problems
• [ACL 2025] Segment-Level Diffusion: A Framework for Controllable Long-Form Generation with Diffusion Language Models
• [ACL 2025] SCULPT: Systematic Tuning of Long Prompts