💬 NLP

A-MapReduce: Executing Wide Search via Agentic MapReduce

A-MapReduce is a novel multi-agent framework that leverages a MapReduce paradigm to transform wide search tasks into parallel, horizontally structured retrieval processes, achieving state-of-the-art performance and significant efficiency gains over existing sequential agentic systems.

Original authors: Mingju Chen, Guibin Zhang, Heng Chang, Yuchen Guo, Shiji Zhou

Published 2026-02-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mingju Chen, Guibin Zhang, Heng Chang, Yuchen Guo, Shiji Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Endless Hallway" vs. The "Library"

Imagine you have a very smart assistant (an AI agent) and you ask it a question that requires finding a lot of information.

Deep Search is like asking your assistant to solve a complex math problem. They think step-by-step, one after another, going deep into the logic. This works well.
Wide Search is like asking your assistant: "Find me the top 100 restaurants in Paris, their addresses, and their star ratings."

Current AI systems try to do this "Wide Search" the same way they do deep thinking: they walk down a long, single hallway, checking one restaurant, then the next, then the next.

The Problem: If the list is huge, the assistant gets lost. They forget what they found earlier, they visit the same restaurant twice, or they run out of time before they finish the list. It's like trying to clean a massive library by walking down one aisle at a time, getting tired, and forgetting which books you already checked.

The Solution: A-MapReduce (The "Assembly Line" Approach)

The authors propose a new framework called A-MapReduce. They take a concept from computer science (MapReduce) and apply it to AI agents.

Think of A-MapReduce not as a single person walking a hallway, but as a highly organized factory assembly line.

1. The "Map" Phase: Breaking it Down

Instead of one agent doing everything, the system acts like a Project Manager.

The Analogy: Imagine you need to pack 1,000 boxes for a move. Instead of one person carrying one box at a time, the Project Manager creates a list of all 1,000 boxes (the "Task Matrix").
What it does: The manager breaks the big question ("Find 100 restaurants") into 100 tiny, specific tasks ("Find info for Restaurant A," "Find info for Restaurant B").
The Magic: It doesn't just list them; it figures out the best way to group them. Maybe it groups them by neighborhood so the agents don't have to travel far. This is called Adaptive Batching.

2. The "Reduce" Phase: Putting it Together

The Analogy: Once the 100 boxes are packed by a team of 10 workers (search agents) working at the same time (in parallel), they all bring their boxes to a central station.
What it does: A "Reducer" agent takes all these separate pieces of information and snaps them together into one perfect, organized table. If a piece is missing, the system knows exactly which box to open and fix it, rather than starting over.

The Secret Sauce: The "Experience Memory"

The paper introduces a special feature called Experiential Memory. This is the system's way of "learning from its mistakes" without needing a human teacher.

The Analogy: Imagine a veteran chef who has cooked the same dish 100 times.
- Without Memory: Every time you ask for the dish, the chef starts from scratch, maybe burning the toast or forgetting a spice, because they don't remember what happened last time.
- With Memory: The chef has a "recipe notebook." Before they start cooking, they look at the notebook. It says: "Last time, we grouped the ingredients by color, and it saved 10 minutes. Also, we forgot to check the oven temperature, so let's fix that."
How it works in the paper:
- When the system finishes a task, it saves a note on what worked well and what didn't.
- The next time it gets a similar question, it pulls up these notes.
- It uses these notes to decide: "Should I send 10 workers or 50? Should I group by city or by price?"
- Over time, the system gets faster, cheaper, and more accurate because it is constantly refining its "assembly line" based on past experience.

Why This Matters (The Results)

The paper tested this system on five different benchmarks (like "WideSearch" and "DeepWideSearch") and compared it to other top AI systems.

It's Faster: Because it uses parallel workers (many agents working at once) instead of a slow line, it finished tasks 45.8% faster than other systems.
It's Cheaper: Because it doesn't waste time re-doing work or getting lost, it used less money (API costs) to get the same or better results.
It's Smarter: It got better scores on accuracy (F1 scores) because it kept track of the whole list better, ensuring no items were missed.

Summary in One Sentence

A-MapReduce turns a chaotic, slow search for massive amounts of information into a streamlined, parallel factory line that gets smarter and more efficient every time it completes a job by remembering what worked best in the past.

Technical Summary: A-MapReduce: Executing Wide Search via Agentic MapReduce

1. Problem Statement

Contemporary Large Language Model (LLM)-based multi-agent systems (MAS) have demonstrated significant success in "deep search" tasks, which rely on iterative, vertically structured reasoning. However, these systems struggle with wide search tasks—scenarios characterized by large-scale, breadth-oriented retrieval where the goal is to cover a massive set of weakly coupled entities and aggregate them into a structured output.

Existing agentic frameworks, designed around sequential, vertical reasoning, face two primary limitations when applied to wide search:

Target Management Dilemma: Most MAS rely on implicit dialogue history or free-form plans to manage retrieval targets. In long-horizon executions, this leads to missing entries, redundant retrieval, and misalignment of targets.
Execution Pattern Dilemma: Current systems typically re-plan execution pipelines for every query without abstracting or reusing structural patterns shared across similar queries. This prevents the accumulation of experience and the evolution of execution decisions.

The authors argue that wide search should be modeled not as a deep reasoning problem, but as a horizontally structured retrieval problem requiring the organization, allocation, tracking, and aggregation of large-scale retrieval targets.

2. Methodology: A-MapReduce

To address these challenges, the authors propose A-MapReduce, a multi-agent execution framework inspired by the MapReduce paradigm from database systems. It reconceptualizes wide search as a distributed computation process for structured retrieval, comprising three core components:

A. Agentic MapReduce Execution

The framework explicitly structures execution decisions as a triple $\Theta_q = (M_q, P_q, B_q)$ :

Task Matrix ( $M_q$ ): Encodes $N$ target entities with known attributes, serving as the explicit schema for the retrieval scope.
Template ( $P_q$ ): A query-specific string with placeholders aligned to the columns of $M_q$ .
Batching Strategy ( $B_q$ ): A discrete strategy (e.g., per-atom, attribute-wise, or adaptive) that partitions the atomic tasks into disjoint batches.

The execution follows a two-stage pipeline:

Mapping Stage: A manager agent ( $A_{manage}$ ) analyzes the query and accumulated observations to sample a high-level decision $\Theta_q$ . It instantiates atomic retrieval tasks by filling the template $P_q$ with rows from $M_q$ . These tasks are then partitioned into batches based on $B_q$ .
Reducing Stage: Independent search agents ( $A_{search}$ ) execute batches in parallel. The manager agent aggregates the partial results into a unified table, validates them against the schema, and triggers a lightweight "delta-patch" round if completeness is violated.

B. Experience-Based Evolution

A-MAPREDUCE introduces an experiential memory mechanism to drive the continual evolution of execution decisions. The memory $\mathcal{M}$ stores:

Record Set ( $D$ ): Historical task-level information including queries, realized decisions, execution traces, and utility feedback.
Hint Pool ( $H$ ): Distilled, reusable structural hints (e.g., optimal batching strategies or template constraints) derived from past successes.
Distillation Operator ( $F_\psi$ ): Consolidates records into cluster-level representative hints to prevent redundancy and semantic drift.

The Evolution Loop:

Memory Retrieval: For a new query, the system retrieves semantically similar positive (high utility) and negative (low utility) historical records.
Conditional Decision Sampling: The system constructs an experiential prior $\Delta_q$ by combining retrieved hints with exemplar records. This prior acts as a decision anchor, biasing the sampling of the execution decision $\Theta_q$ toward historically high-utility regions of the decision space.
Feedback Update: After execution, the system updates the memory with the new record and refines hint scores based on utility feedback, enabling progressive improvement in execution efficiency and robustness.

3. Key Contributions

The paper outlines three primary contributions:

Paradigm Reformulation: The introduction of A-MapReduce, an open-source framework that reformulates wide search as a controllable, MapReduce-style execution process. It enables persistent coverage tracking, parallelized mapping, and principled reduction into schema-consistent tables.
Practical Evolution: The development of an experience-based evolution mechanism that couples MapReduce execution with experiential memory. This allows the system to progressively refine query-conditioned decision distributions, leading to increasingly adaptive and cost-efficient execution.
Experimental Evaluation: Comprehensive evaluation across five agentic benchmarks demonstrating that A-MapReduce achieves state-of-the-art performance while significantly improving cost-effectiveness.

4. Experimental Results

The authors evaluated A-MapReduce on WideSearch, DeepWideSearch, and a constructed Agentic-Wide Subset derived from xBench, WebWalkerQA, and TaskCraft.

Performance: A-MapReduce achieved state-of-the-art results on WideSearch and DeepWideSearch.
- On WideSearch, it improved average Item F1 by 5.64% to 27.62% compared to strong baselines (including OpenAI o3 and Gemini 2.5 Pro backbones).
- On DeepWideSearch, it showed absolute gains of 3.52% to 19.09% in Core Entity Accuracy and 9.71% to 30.18% in Column-F1 compared to open-source multi-agent frameworks.
- It achieved a Success Rate of 4.43% on DeepWideSearch, significantly outperforming baselines that hovered near 0–2%.
Efficiency and Cost:
- A-MapReduce reduced running time by 45.8% compared to representative multi-agent baselines.
- It achieved superior cost-performance trade-offs, saving an average of $1.10 per task and reducing API costs by up to 47.5% while delivering higher quality outputs.
Ablation Studies: Removing the experiential memory resulted in a 5.15% drop in Item F1 and a 5.73% drop in Row F1, while increasing costs. Removing structural decisions (task matrix or batching strategy) caused even sharper declines in performance, confirming the necessity of the structured approach.

5. Significance and Claims

The paper claims that A-MapReduce addresses a critical gap in multi-agent systems by shifting the focus from vertical, deep reasoning to horizontal, structured retrieval. Its significance lies in:

Explicit State Management: By externalizing retrieval objectives into a schema-aligned task matrix, the framework makes execution states observable and correctable, mitigating common failure modes like coverage loss and fragmented evidence in long-horizon tasks.
Experience-Driven Optimization: The framework demonstrates that multi-agent systems can "learn how to plan" by distilling execution patterns from history, rather than merely retrieving more content. This leads to progressive improvements in efficiency and robustness without requiring retraining of the underlying LLMs.
Scalability: The MapReduce-inspired design allows for the parallel processing of massive retrieval targets, offering a scalable solution for wide-scope information seeking that existing sequential frameworks cannot efficiently handle.

The authors conclude that A-MapReduce provides a resource-efficient and reliable paradigm for wide-scope retrieval, potentially lowering the barrier to deploying agentic systems at scale for complex, data-heavy tasks.