cs.CLMar 12, 2026
SaveStrategic Navigation or Stochastic Search? How Agents and Humans Reason Over Document Collections
Abstract
Multimodal agents offer a promising path to automating complex document-intensive workflows. Yet, a critical question remains: do these agents demonstrate genuine strategic reasoning, or merely stochastic trial-and-error search? To address this, we introduce MADQA, a benchmark of 2,250 human-authored questions grounded in 800 heterogeneous PDF documents. Guided by Classical Test Theory, we design it to maximize discriminative power across varying levels of agentic abilities. To evaluate agentic behaviour, we introduce a novel evaluation protocol measuring the accuracy-effort trade-off. Using this framework, we show that while the best agents can match human searchers in raw accuracy, they succeed on largely different questions and rely on brute-force search to compensate for weak strategic planning. They fail to close the nearly 20% gap to oracle performance, persisting in unproductive loops. We release the dataset and evaluation harness to help facilitate the transition from brute-force retrieval to calibrated, efficient reasoning.
Figures & tables
Figure 1: Given a query over corpus , the system iteratively retrieves pages, reasons over visual and textual content, and aggregates evidence from multiple pages to produce a grounded answer with attribution. The process typically requires decomposing , iterative retrieval, and synthesizing across .
| Name and Reference | Input File(s) | Diversity | Human | Problem |
| (Domains / Layouts) | -annotated | Framing | ||
| DocVQA ( Mathew et al., 2021b ) | Single document image | medium / medium | ✓ | |
| InfographicVQA ( Mathew et al., 2021a ) | Single image | medium / high | ✓ | |
| TAT-DQA ( Zhu et al., 2022 ) | Mostly single-page PDF | low / low | ✓ | |
| DUDE ( Landeghem et al., 2023 ) | Multi-page PDF file | high / high | ✓ | |
| MP-DocVQA ( Tito et al., 2023 ) | Multi-page PDF | medium / medium | ✓ / ✗ |
Table 1: Comparing MADQA with existing benchmarks. Our work is distinguished by its focus on a collection of complex PDFs with fresh documents (not recycled from existing benchmarks) and fully human-authored questions , designed to test agentic reasoning. We denote diversity levels using high, medium, and low as coarse, relative categories (see Appendix J.1 for detailed assessment).
| # | Property | Definition |
| 1 | Extractive | Answer tokens must appear physically in the evidence set . |
| 2 | Multi-Hop | may span disjoint pages (cross-page) or documents (cross-doc). |
| 3 | Closed-World | Answer derived solely from ; no external parametric knowledge. |
| 4 | Grounded | must entail and be minimal (no superfluous pages). |
| 5 | Agentic | No single retrieval query may exist such that . |
| 6 | Visual | Answering may require non-textual information (layout, tables, figures) in . |
Figure 2: Layout element density across document domains in MADQA . The heatmap shows the standardized (z-scored) concentration of individual layout elements within each domain. Pink indicates above-average density, while cyan indicates below-average density. A detailed discussion is provided in Appendix B.2 .
| Domain | Docs | Pages | Pg/Doc | Qs | Q/Doc |
| Financial | 131 | 6,149 | 46.9 | 460 | 3.5 |
| Reports | 127 | 2,665 | 21.0 | 360 | 2.8 |
| Gov/Regulatory | 105 | 702 | 6.7 | 304 | 2.9 |
| Legal | 69 | 1,154 | 16.7 | 182 | 2.6 |
| HR/Employment | 68 | 813 | 12.0 | 159 | 2.3 |
| Reference | 62 | 1,292 | 20.8 | 218 | 3.5 |
Table 2: Constituents of MADQA . The corpus spans documents (median 5 pages, mean 23.3, max 859) totaling 12.2M tokens.
Figure 3: Sample question (X-Doc). No single document covers the full period. The agent must retrieve both the 2018 report (covering 2014–2018) and the 2019 report, then extract and sum the relevant values. More examples provided in Appendix C.3 .
Figure 4: Visual necessity in MADQA . 58% of the questions benefit from understanding Structured layouts, Tabular data, or Visual Artifacts (e.g., charts, stamps). The matrix highlights that multi-category dependencies (e.g., Structured + Artifacts ) are a significant driver of benchmark difficulty.
Figure 5: Principled dev/test set selection. We evaluate every question based on Difficulty (mean accuracy) and Discrimination (point-biserial correlation). The Sentinel Pool ( ) captures the hardest items to preserve headroom, regardless of discrimination scores. For the remaining budget, we stratify questions into difficulty bins and greedily select those with the highest discrimination signal ( ), discarding questions with lower predictive power ( ). Data on the plot are illustrative.
Figure 6: Illustration of the cumulative difference curve. Upward segments indicate above-average accuracy at low effort, while downward indicate below-average accuracy at higher effort. The Kuiper statistic measures the total range of this deviation.
| Model / Framework | Accuracy | X-Page | X-Doc | Page F1 | Doc F1 | Kuiper |
| Non-Agentic Systems | ||||||
| Gemini 3 Pro File Search | 78.6 2.2 | 74.1 3.6 | 75.0 3.6 | 70.1 2.0 | 94.2 1.0 | – |
| Gemini 2.5 Flash File Search | 71.8 2.4 | 61.3 4.1 | 73.0 3.7 | 52.2 2.2 | 80.9 1.8 | – |
| M3DocRAG | 61.6 2.6 | 31.0 3.9 | 35.0 4.0 | 68.2 2.1 | 82.6 1.7 | – |
| GPT-5.2 (2024-08) HEAVEN | 52.9 2.7 | 38.9 4.1 | 53.0 4.2 | 48.4 2.2 | 62.3 2.2 | – |
| GPT-5.2 (2025-12) File Search | 50.0 2.7 | 39.5 4.1 | 23.0 3.5 | 28.5 2.0 | 68.5 2.1 | – |
Table 3: Main evaluation results on MADQA . Agentic systems consistently outperform their static RAG counterparts, yet an 18% oracle gap reveals that retrieval—not reasoning—remains the primary bottleneck. We report aggregate Accuracy ( confidence intervals) alongside specific multi-hop reasoning subsets (X-Page and X-Doc). Attribution is measured via Page F1 and Doc F1 to assess grounding fidelity. The Kuiper statistic ( is better) quantifies effort calibration; it is excluded for Non-Agentic systems as they operate with fixed computational budgets. Pink indicates higher Kuiper values (worse; better). Blue indicates higher performance (better). Bold denotes the best performing model in Agentic and Non-Agentic systems for each subset.
Figure 7: Performance and cost of running test set inference. Leading models with Managed RAG, compared to employing them in BM25 MLLM Agent or RLM setup.
Figure 8: Error decomposition across all BM25 MLLM agents , ordered by accuracy. Each bar decomposes a system’s test predictions into correct (exact and verbose) and four error types. Weaker models are dominated by refusals and retrieval failures, while stronger models shift toward comprehension errors—suggesting that retrieval is largely solved for top systems and answer extraction remains the bottleneck.
Figure 9: Accuracy as a function of step limit ( ) for BM25 MLLM agents. While frontier agents eventually match human accuracy given a large budget ( ), they suffer from a severe “Cold Start” efficiency gap. Humans achieve 50% accuracy on their first query, whereas Gemini 3 Pro starts at only 12%, requiring an aggressive, high-cost recovery strategy to reach parity.
Figure 10: Kuiper calibration curves measuring effort-accuracy alignment. Human annotators remain well-calibrated across effort levels. RLM agents exhibit calibration closer to humans.
Appendix figures & tables34 assets
Supplementary material from the paper’s appendix.
Appendix
| Metric | Value |
| Total Questions | 2,250 |
| Total Documents | 800 (sourced from DocumentCloud) |
| Total Pages | 18,619 (median 5, mean 23.3, max 859 per doc) |
| Total Tokens | 12.2M (assuming Qwen3 tokenizer) |
| Multi-hop Questions | 17.3% (8.3% cross-page, 9.0% cross-document) |
| Visual Necessity | 58% require layout/table/artifact understanding |
Table 4: Summary of dataset statistics and splits.
| Axis | Choices in the Design Space | Our Decision in this Benchmark |
|---|---|---|
| Corpus modality & source | Single web pages; HTML dumps; synthetic PDFs; scanned documents only; born-digital only; mixture of images and text; private vs. public corpora. | Real-world, publicly hostable multi-page PDFs sourced from DocumentCloud; mixture of scanned and digital documents; benchmark definition is agnostic to whether systems use images, OCR, or layout-aware models. |
| Domain & layout diversity | Single domain (e.g., finance); few related domains; broad open-domain; homogeneous layouts (forms only); mixed narrative + tables; highly heterogeneous visual structure. | Broad coverage of real-world domains (financial, legal, government, commercial, personal) with heterogeneous layouts, as detailed in § B.1 . |
| Document granularity | Single isolated document; small set of thematically related documents; large corpus/collection per query; streaming documents. | Each query is posed over a collection of PDFs, encouraging cross-document and cross-page reasoning rather than single-document lookup. |
| Grounding assumptions | World-knowledge allowed; mixed (doc + world); purely corpus-grounded; open-ended generation without evidence requirement. | Strictly PDF-grounded: by construction, every question is answerable using the provided documents alone; use of external world knowledge is unnecessary and treated as a source of hallucination. |
| Question source & semantics | Fully human-authored; LLM-generated; human-edited LLM generations; templated questions; questions that can be answered from a single span vs. questions requiring multi-hop reasoning. | Fully human-authored questions created directly over the PDFs, with explicit control to ensure 20% multi-hop cases (cross-page or cross-document) and strict PDF-grounding. |
| Answer format | Free-form natural language; single spans; multiple spans; sets/lists; numeric or boolean values; open-ended rationales. | Short, concrete answers: spans, booleans, lists, and numeric values. Answers are represented as small sets of strings (possibly multi-element for list questions). No rationales are required in the official metric. |
Table 5: Design space for agentic document benchmark. We map the broader landscape of document evaluation choices (center) against the specific instantiation in our benchmark (right), emphasizing strict PDF-grounding, multi-hop reasoning, and efficiency-aware metrics.
| Category | Docs | Pages | Mean | Med. | Max |
|---|---|---|---|---|---|
| Annual Report | 30 | 1,754 | 58.5 | 33 | 222 |
| 990 Form | 20 | 1,890 | 94.5 | 36 | 697 |
| Verdict form | 20 | 143 | 7.2 | 3 | 46 |
| News, Journal | 20 | 446 | 22.3 | 10 | 80 |
| Expenses | 20 | 914 | 45.7 | 2 | 859 |
| Lesson plan | 20 | 247 | 12.3 | 10 | 46 |
Table 6: Detailed statistics per document category. Categories are sorted by document count. The corpus exhibits high variance in document length, from single-page posters to 859-page expense document.
Figure 11: Per-category layout element density. Cell values indicate average elements per page; colors show z-score normalized deviation from the element-type mean. (Continued on next page…)
Figure 12: Per-category layout element density (Continued). Categories such as Yearbook and News, Journal exhibit high picture density, while 990 Form and Budget show elevated table presence. Text-heavy categories like Settlement and Patent display high text block counts but minimal visual elements. This heterogeneity ensures the benchmark tests model robustness across diverse layout structures.
Figure 13: Main annotation interface. The question appears at the top (blue box), followed by the search bar. Search results display as interactive PDF pages with navigation controls. The sidebar shows progress, selected citations, and search history.
Which vehicles offer multiple upholstery designs? The agent must retrieve separate product brochures from a large collection and compare interior specification tables across documents to identify which vehicles list more than one upholstery option.
How many days was the sale of pianos at the New Virginia Hotel planned to last? The target information is buried within a dense, multi-column newspaper layout, likely surrounded by hundreds of unrelated articles and advertisements in the corpus. Standard chunking algorithms may fail to correctly segment the advertisement column from adjacent news stories.
How much was spent on Food and drinks at Bar 101 during the event? The model must first determine that this information is in one of the financial statements within the collection. Once retrieved, the task involves reading handwritten entries in a table to extract the correct monetary value.
| Rank | Provider | Model Name | Model ID | ANLS* |
| 1 | Gemini 3 Pro Preview | gemini-3-pro-preview | 0.688 | |
| 2 | Anthropic | Claude 4.5 Sonnet | claude-sonnet-4-5-20250929 | 0.681 |
| 3 | OpenAI | GPT-5 | gpt-5-2025-08-07 | 0.647 |
| 4 | Zhipu AI | GLM-4.6V | zai-org/GLM-4.6V | 0.616 |
| 5 | Anthropic | Claude 4.5 Haiku | claude-haiku-4-5-20251001 | 0.601 |
| 6 | Alibaba | Qwen3-VL-235B Thinking | Qwen/Qwen3-VL-235B-A22B-Thinking | 0.598 |
Table 7: Models used for Item Response Analysis (Sorted by Performance)
Figure 14: Distribution of item difficulties ( -values) in the Full Dataset vs. the Selected Test Subset. The selection strategy boosts the density of “Hard” and “Sentinel” items to preventing saturation.
| N-gram | Median Pages | Precision | Recall |
| Unigram | 4,125 | 0.03% | 99% |
| Bigram | 24 | 2.6% | 86% |
| Trigram | 1 | 1.9% | 51% |
Table 8: Lexical solvability analysis. Unigrams and bigrams match too many pages (low precision), while trigrams miss half the questions entirely (low recall). No n-gram size enables effective Ctrl+F-based retrieval.
| Model | Correct | Yes/No | Binary | Memorized | Random | Contam. |
| Claude Haiku 4.5 | 45 (9.1%) | 16 (35.6%) | 16 (35.6%) | 13 (28.9%) | 3.2% | 2.6% |
| Claude Sonnet 4.5 | 53 (10.7%) | 16 (30.2%) | 13 (24.5%) | 24 (45.3%) | 2.9% | 4.8% |
| Gemini 2.5 Flash | 48 (9.7%) | 13 (27.1%) | 14 (29.2%) | 21 (43.8%) | 2.7% | 4.2% |
| Gemini 2.5 Pro | 65 (13.1%) | 15 (23.1%) | 17 (26.2%) | 33 (50.8%) | 3.2% | 6.7% |
| GPT-5 | 75 (15.2%) | 19 (25.3%) | 15 (20.0%) | 41 (54.7%) | 3.4% | 8.3% |
| GPT-5 Mini | 47 (9.5%) | 14 (29.8%) | 13 (27.7%) | 20 (42.6%) | 2.7% | 4.0% |
Table 9: Answer guessability analysis across frontier models. “Correct” shows questions answered correctly without evidence. Categories show the breakdown of correct guesses by question type. “Random” estimates the expected contribution from 50% chance on yes/no and binary questions; “Contam.” shows pure memorization questions (facts, names, values) as percentage of test set.
| Category | Count | % |
| Free Text | 959 | 42.8 |
| Structured | 644 | 28.8 |
| Tabular | 471 | 21.0 |
| Artifacts | 150 | 6.7 |
| (of which: charts/diagrams) | 41 | 1.8 |
| (handwriting/signatures) | 92 | 4.1 |
Table 10: Visual modality requirements for answering MADQA questions. Categories are mutually exclusive for primary assignment; some questions have secondary categories when multiple modalities apply.
| System | Acc. | Steps vs Total | Steps vs Gen. | Total vs Gen. |
| BM25 GPT-5.2 | 67.8% | 0.76 | 0.95 | 0.78 |
| BM25 Claude Sonnet | 80.6% | 0.89 | 0.92 | 0.90 |
| BM25 GPT-4.1 | 60.0% | 0.79 | 0.85 | 0.72 |
| RLM GPT-5.2 | 64.2% | 0.83 | 0.74 | 0.80 |
| RLM Gemini-3-Pro | 73.8% | 0.84 | 0.93 | 0.87 |
| RLM Claude Sonnet | 70.5% | 0.91 | 0.85 | 0.89 |
Table 11: Spearman rank correlation ( ) between effort measures across systems. Higher values indicate more similar sample orderings.
| System | Acc. | Steps | Tokens (Total) | Tokens (Gen.) | Time |
| BM25 GPT-5.2 | 67.8% | 64.1 | 53.3 | 59.9 | – |
| BM25 Claude Sonnet | 80.6% | 35.4 | 36.4 | 37.8 | – |
| BM25 GPT-4.1 | 60.0% | 42.0 | 35.9 | 36.2 | – |
| RLM GPT-5.2 | 64.2% | 28.4 | 31.2 | 21.1 | 22.3 |
| RLM Gemini-3-Pro | 73.8% | 22.3 | 20.9 | 25.1 | 21.2 |
| RLM Claude Sonnet | 70.5% | 42.7 | 38.1 | 34.3 | 30.8 |
Table 12: Kuiper statistic under different effort definitions. Missing entries (–) indicate unavailable measurements.
| Parameter | Symbol | Value |
| Stage 1 candidates | 200 | |
| Final results | 5 | |
| VS-page reduction factor | 15 | |
| VS-page filter ratio | – | 0.5 |
| Query filter ratio | 0.25 | |
| Stage 1 weight | 0.1 |
Table 13: HEAVEN hyperparameters (paper defaults).
Figure 15: Same-document multi-hop accuracy by physical distance (page gap) and semantic distance (embedding cosine). Semantic distance is a stronger predictor of difficulty.
| Semantic Distance | Questions | Accuracy |
| 0.0–0.15 (similar) | 29 | 72.4% |
| 0.15–0.3 | 38 | 71.1% |
| 0.3–0.45 | 51 | 56.9% |
| 0.45–0.6 | 45 | 64.0% |
| 0.6+ (dissimilar) | 23 | 34.8% |
| Overall | 186 | 61.2% |
Table 14: Same-document multi-hop accuracy by semantic distance between evidence pages.
| Semantic Distance | Questions | Accuracy |
| 0.0–0.15 | 18 | 80.0% |
| 0.15–0.3 | 17 | 80.0% |
| 0.3–0.45 | 26 | 77.7% |
| 0.45–0.6 | 43 | 77.2% |
| 0.6+ | 82 | 72.4% |
| Overall | 186 | 75.7% |
Table 15: Cross-document multi-hop accuracy by semantic distance between evidence pages.
| Question | Error Type | Characterization of Mistake |
| What types of pants are not allowed at MTM? | Negation Blindness | The participant located the correct dress code section but overlooked the negation in the query, listing permitted items rather than prohibited ones. |
| Was the Sodium level detected […] within normal range? | Incomplete Evidence Retrieval | The participant found the specific sodium test result but failed to retrieve the separate page containing the reference “normal range” table required for verification. |
| Which Forensic Scientist approved the […] report? | Role Conflation | The participant provided the name of the Certifying Scientist who electronically signed the work order, confusing this role with the Forensic Scientist mentioned elsewhere in the document chain. |
| What water-related act did Pennsylvania introduce…? | Lexical Polysemy | The participant was misled by the polysemy of the word “act,” interpreting it as a physical deed (answering that they “opened a bridge”) rather than a legislative statute. |
| How long after public transportation started […] did deaths decrease? | Temporal Reasoning Failure | The question required calculating a duration (time delta). The participant identified the correct dates but answered with a specific calendar year instead of the elapsed time. |
| What is the largest penalty assessed in case 3AN-24-04508CI? | Ordinal Ranking Error | The participant located the correct legal document but reported the second-largest penalty listed, likely due to skimming or a failure to sort the values exhaustively. |
Table 16: Examples of human errors . Observed during baseline creation. These represent genuine misunderstandings rather than annotation noise, highlighting the reasoning challenges inherent in the benchmark.
| Error Type | Count | % |
| Retrieval (wrong document) | 1,167 | 35.7 |
| Comprehension (right page, wrong answer) | 941 | 28.8 |
| Navigation (right doc, wrong page) | 753 | 23.0 |
| No Answer / Refusal | 412 | 12.6 |
Table 17: Aggregate error distribution across all agent systems (N=3,273 incorrect predictions).
Figure 16: Error composition shifts with model capability. Systems ordered by increasing accuracy (left to right). Weaker models are dominated by refusals; stronger models shift toward retrieval and comprehension failures.
Figure 17: Retrieval vs. comprehension failure profiles. Each point is one system. Models in the bottom-left corner fail least on both dimensions. The dashed lines mark approximate cluster boundaries.
Figure 18: Error types by evidence complexity for top-4 systems. Cross-page (same document) questions are consistently hardest.
Figure 19: Error decomposition by document domain (top-4 systems aggregated). Media/Publishing and Financial domains are hardest; Events documents are easiest.
Figure 20: Error cascade: where do systems fail? Each horizontal bar decomposes a system’s predictions by error stage. Percentages indicate the share of predictions in each category.
Figure 21: Pairwise system agreement (Cohen’s ). Darker cells indicate higher agreement. The Human baseline shows low agreement with all agent systems despite comparable accuracy, revealing complementary error patterns.
Figure 22: Left: Distribution of item difficulty (mean model accuracy). Right: Difficulty vs. variance; high-variance items are the most discriminating. Only 5 anomalous items exist, confirming monotonic difficulty scaling.
Figure 23: Evidence found by iteration . Left: document retrieval. Right: page retrieval. Humans find evidence earlier, but top agents converge by iteration 5.
Figure 24: Recovery rate after initial query miss. Percentage of questions where the system eventually finds the gold document after failing on the first query. Labels show the number of questions requiring recovery ( ). Notably, the human baseline needs recovery for only 118 questions—far fewer than most agents (typically 250–380)—indicating that humans craft more precise initial queries. Among the cases that do require recovery, top agents match human recovery rates ( ); weaker models rarely recover.
Figure 25: Query reformulation magnitude by system. Higher drift indicates more aggressive query changes. Box shows IQR with median labeled. Systems sorted by median drift.
Figure 26: Left: Drift distribution for correct vs. incorrect predictions. Right: Per-system mean drift vs. accuracy on reformulated questions, showing a positive correlation between reformulation effort and success.
Figure 27: Taxonomy of document-based benchmarks. We structure our assessment of related works along three axes: (I) Domain Diversity, ranging from single-topic to open-domain; (II) Layout Diversity, evaluating visual structural complexity; and (III) Annotation Method, distinguishing between synthetic, hybrid, and fully human-curated pipelines.