A-MapReduce: Executing Wide Search via Agentic MapReduce
Organizations: Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, School of Artificial Intelligence, Beihang University · National University of Singapore · Tsinghua University
Abstract
Contemporary large language model (LLM)-based multi-agent systems exhibit systematic advantages in deep research tasks, which emphasize iterative, vertically structured information seeking. However, when confronted with wide search tasks characterized by large-scale, breadth-oriented retrieval, existing agentic frameworks, primarily designed around sequential, vertically structured reasoning, remain stuck in expansive search objectives and inefficient long-horizon execution. To bridge this gap, we propose A-MapReduce, a MapReduce paradigm-inspired multi-agent execution framework that recasts wide search as a horizontally structured retrieval problem. Concretely, A-MapReduce implements parallel processing of massive retrieval targets through task-adaptive decomposition and structured result aggregation. Meanwhile, it leverages experiential memory to drive the continual evolution of query-conditioned task allocation and recomposition, enabling progressive improvement in large-scale wide-search regimes. Extensive experiments on five agentic benchmarks demonstrate that A-MapReduce is (i) high-performing, achieving state-of-the-art performance on WideSearch and DeepWideSearch, and delivering 5.11% - 17.50% average Item F1 improvements compared with strong baselines with OpenAI o3 or Gemini 2.5 Pro backbones; (ii) cost-effective and efficient, delivering superior cost-performance trade-offs and reducing running time by 45.8% compared to representative multi-agent baselines. The code is available at https://github.com/mingju-c/AMapReduce.
Figures & tables
| Model / System | Item F1(%) | Row F1(%) | Succ. Rate(%) | |||
| Avg@4 | Max@4 | Avg@4 | Max@4 | Avg@4 | Pass@4 | |
| Single Agent † | ||||||
| Claude Sonnet 4 (Thinking) | 57.89 | 66.73 | 31.69 | 41.90 | 2.25 | 5.00 |
| Gemini 2.5 Pro | 50.98 | 63.62 | 30.00 | 41.39 | 1.50 | 5.00 |
| OpenAI o3-high | 52.61 | 62.27 | 34.00 | 44.07 | 4.50 | 9.00 |
| Kimi K2 | 54.36 | 65.08 | 29.67 | 41.35 | 1.12 | 3.50 |
| Model / System | CE Acc. | Column F1 | Item F1 | Row F1 | Succ. Rate | |||||
| Avg@4 | Pass@4 | Avg@4 | Max@4 | Avg@4 | Max@4 | Avg@4 | Max@4 | Avg@4 | Pass@4 | |
| Closed-source LLMs † | ||||||||||
| OpenAI o3-mini | 61.59 | 69.55 | 27.36 | 35.68 | 13.59 | 16.85 | 3.35 | 4.55 | 0.00 | 0.00 |
| GPT-5 | 58.41 | 72.72 | 31.71 | 41.05 | 21.67 | 28.21 | 9.61 | 13.42 | 0.30 | 1.36 |
| Claude Sonnet 4 | 57.95 | 64.09 | 32.63 | 40.16 | 19.94 | 23.38 | 7.31 | 8.97 | 0.90 | 0.90 |
| Gemini 2.5 Pro | 73.98 | 81.82 | 45.27 | 52.86 | 32.06 | 37.10 | 15.42 | 18.96 | 0.90 | 1.82 |
| Method | Item F1 (%) | Row F1 (%) | Delay (s) |
| Smolagents | 51.31 | 23.04 | 2617.7 |
| Flash-Searcher | 54.99 | 34.42 | 1204.7 |
| A-MapReduce * | 64.64 | 41.62 | 1460.8 |
| A-MapReduce | 67.81 | 45.23 | 953.7 |
| Method | Item F1(%) | Row F1(%) | Cost($) |
| A-MapReduce | 70.12 | 43.65 | 0.60 |
| -w/o Exemplars | 68.76 ( 1.36) | 40.57 ( 3.08) | 0.64 |
| -w/o Hint | 66.47 ( 3.65) | 40.58 ( 3.07) | 0.62 |
| -w/o Memory | 64.97 ( 5.15) | 37.92 ( 5.73) | 1.05 |
| -w/o | 67.90 ( 2.22) | 37.85 ( 5.80) | 1.08 |
| -w/o | 65.95 ( 4.17) | 37.33 ( 6.32) | 0.68 |
Appendix figures & tables15 assets
Supplementary material from the paper’s appendix.
Appendix
| Source Benchmark | #Total | #Stage I Candidates | #Final Selected |
| xBench-DeepSearch | 100 | 54 | 31 |
| WebWalkerQA | 680 | 217 | 120 |
| TaskCraft | 5228 | 429 | 101 |
| Method | Item P(%) | Item R(%) | Item F1(%) | Row P(%) | Row R(%) | Row F1(%) | Succ.(%) | Delay(s) | Cost($) |
| SmolAgents | 66.84 | 47.54 | 51.31 | 30.67 | 21.37 | 23.04 | 4.00 | 2617.65 | 1.243 |
| Flash-Searcher | 67.57 | 52.16 | 54.99 | 41.08 | 33.00 | 34.42 | 6.40 | 1204.69 | 0.396 |
| A-MapReduce ∗ | 75.63 | 62.34 | 64.64 | 48.14 | 40.26 | 41.62 | 6.75 | 1460.80 | 1.080 |
| A-MapReduce | 78.99 | 65.48 | 67.81 | 51.60 | 43.83 | 45.23 | 7.50 | 953.66 | 0.763 |
| Item P(%) | Item R(%) | Item F1(%) | Row P(%) | Row R(%) | Row F1(%) | Succ.(%) | Delay(s) | Cost($) | |
| 1 | 80.22 | 64.24 | 67.19 | 48.02 | 39.34 | 41.20 | 4.17 | 1506.28 | 0.740 |
| 2 | 79.11 | 65.28 | 68.13 | 45.08 | 37.51 | 39.25 | 5.00 | 1050.53 | 0.648 |
| 3 | 82.07 | 66.62 | 70.12 | 51.18 | 41.41 | 43.65 | 6.67 | 824.49 | 0.602 |
| 4 | 77.73 | 64.15 | 66.98 | 45.42 | 37.77 | 39.48 | 3.33 | 1312.29 | 0.667 |
| Method | Item P(%) | Item R(%) | Item F1(%) | Row P(%) | Row R(%) | Row F1(%) | Succ.(%) | Cost($) |
| A-MapReduce | 82.07 | 66.62 | 70.12 | 51.18 | 41.41 | 43.65 | 6.67 | 0.60 |
| -w/o Few-shot | 81.31 ( 0.76) | 65.38 ( 1.24) | 68.76 ( 1.36) | 47.31 ( 3.87) | 38.61 ( 2.80) | 40.57 ( 3.08) | 5.83 ( 0.84) | 0.64 |
| -w/o Insights | 77.44 ( 4.63) | 63.44 ( 3.18) | 66.47 ( 3.65) | 47.37 ( 3.81) | 38.65 ( 2.76) | 40.58 ( 3.07) | 5.00 ( 1.67) | 0.62 |
| -w/o Memory | 75.12 ( 6.95) | 61.92 ( 4.70) | 64.97 ( 5.15) | 44.37 ( 6.81) | 35.89 ( 5.52) | 37.92 ( 5.73) | 4.16 ( 2.51) | 1.05 |
| -w/o | 77.54 ( 4.53) | 64.52 ( 2.10) | 67.90 ( 2.22) | 43.30 ( 7.88) | 35.96 ( 5.45) | 37.85 ( 5.80) | 3.33 ( 3.34) | 1.08 |
| -w/o | 77.95 ( 4.12) | 62.40 ( 4.22) | 65.95 ( 4.17) | 43.77 ( 7.41) | 35.17 ( 6.24) | 37.33 ( 6.32) | 4.17 ( 2.50) | 0.68 |
| Model | XBench Subset | WebWalkerQA Subset | TaskCraft Subset | ||||||
| Acc. (%) | Delay (s) | Cost ($) | Acc. (%) | Delay (s) | Cost ($) | Acc. (%) | Delay (s) | Cost ($) | |
| OWL | 45.16 | 1003.27 | 0.13 | 52.50 | 652.08 | 0.11 | 74.26 | 702.48 | 0.08 |
| SmolAgents | 51.61 | 1335.10 | 0.57 | 50.00 | 836.29 | 0.21 | 80.20 | 607.04 | 0.12 |
| Flash-Searcher | 67.74 | 679.30 | 0.25 | 59.17 | 326.42 | 0.07 | 87.13 | 275.90 | 0.06 |
| A-MapReduce | 74.19 | 707.32 | 0.35 | 62.50 | 297.48 | 0.08 | 90.10 | 384.07 | 0.09 |
| Setting | Item P(%) | Item R(%) | Item F1(%) | Row P(%) | Row R(%) | Row F1(%) | Succ.(%) | Delay(s) |
| Low | 79.53 | 65.12 | 69.17 | 49.68 | 42.72 | 44.39 | 5.00 | 1045.3 |
| Medium | 82.07 | 66.62 | 70.12 | 51.18 | 41.41 | 43.65 | 6.67 | 953.7 |
| High | 78.41 | 65.49 | 68.74 | 48.35 | 40.79 | 42.97 | 5.58 | 1140.5 |
| Framework | Evo. | Item P(%) | Item R(%) | Item F1(%) | Row P(%) | Row R(%) | Row F1(%) | Delay(s) | Cost($) |
| A-MapReduce | ✓ | 88.67 | 88.67 | 88.67 | 52.00 | 52.00 | 52.00 | 2065.21 | 1.41 |
| 57.33 | 57.33 | 57.33 | 0.00 | 0.00 | 0.00 | 3448.17 | 1.76 |
| Framework | Evo. | Item P(%) | Item R(%) | Item F1(%) | Row P(%) | Row R(%) | Row F1(%) | Delay(s) | Cost($) |
| A-MapReduce | ✓ | 96.19 | 96.19 | 96.19 | 73.33 | 73.33 | 73.33 | 897.60 | 0.36 |
| 78.10 | 78.10 | 78.10 | 0.00 | 0.00 | 0.00 | 962.40 | 0.68 |
| Framework | Evo. | Item P(%) | Item R(%) | Item F1(%) | Row P(%) | Row R(%) | Row F1(%) | Delay(s) | Cost($) |
| A-MapReduce | ✓ | 88.00 | 88.00 | 88.00 | 64.00 | 64.00 | 64.00 | 2221.80 | 2.58 |
| 44.67 | 44.67 | 44.67 | 16.00 | 16.00 | 16.00 | 3037.80 | 4.78 |
| Framework | Evo. | Item P(%) | Item R(%) | Item F1(%) | Row P(%) | Row R(%) | Row F1(%) | Delay(s) | Cost($) |
| A-MapReduce | ✓ | 79.20 | 79.20 | 79.20 | 58.33 | 58.33 | 58.33 | 1917.00 | 1.21 |
| 56.70 | 47.20 | 51.52 | 0.00 | 0.00 | 0.00 | 2341.20 | 1.56 |
| Notation | Definition | Notation | Definition |
| Wide-search query: a natural-language request plus an explicit schema. | Set of past records; is the set size. | ||
| Schema attributes (columns); is the number of requested fields. | Record: query, decision, trace, and utility feedback. | ||
| Latent target entities (rows) induced by ; is the number of entities. | Hint pool of reusable decision guidance (about ). | ||
| Structured table output; is the value space of cells. | A hint rule’s content used to bias planning/decision sampling. | ||
| High-level execution decision sampled by the MAS (controls decomposition/scheduling/execution). | Online hint score updated from utility feedback (higher implies more reliable guidance). | ||
| Query-conditioned decision distribution to be refined by experience-based evolution. | Hint provenance: supporting record indices in (for retrieval/voting). |
Multi-Agent LLM Systems
Multi-agent large language model systems coordinate multiple AI agents to solve tasks through communication, specialization, shared tools, and memory.
See all 1,032 papers