Strategic Navigation or Stochastic Search? How Agents and Humans Reason Over Document Collections

Łukasz Borchmann, Jordy Van Landeghem, Michał Turski, Shreyansh Padarha, Ryan Othniel Kearns, Adam Mahdi, Niels Rogge, Clémentine Fourrier, Siwei Han, Huaxiu Yao, Artemis Llabrés, Yiming Xu, Dimosthenis Karatzas, Hao Zhang, Anupam Datta

TL;DR

The researchers introduce MADQA, a new benchmark of 2,250 human-authored questions across 800 complex PDFs designed to test if AI agents can "think" strategically or if they just brute-force their way through documents. They find that while top agents can match human accuracy, they suffer from a massive "efficiency gap," often getting stuck in unproductive loops where humans would have pivoted to a new strategy.

What Problem Does This Paper Address?

We’ve all seen "Chat-with-PDF" tools, but real-world enterprise work is much harder. It involves "Agentic Document Collection VQA"—tasks where an agent must navigate a massive pile of heterogeneous documents (reports, forms, manuals), decide what to search for, and synthesize an answer across multiple pages.

The authors argue that current benchmarks are either too simple, rely on synthetic (AI-generated) questions that favor specific models, or use plain text that ignores the visual complexity of real documents (like tables and checkboxes). The core question is: Are agents actually reasoning strategically, or are they just performing a stochastic trial-and-error search?

Methods

The authors developed a rigorous evaluation framework based on several novel components:

  • Classical Test Theory (CTT): Instead of a random split, they used CTT to select a "Test Set" that maximizes "discriminative power"—meaning the questions are specifically chosen to tell the difference between a "lucky" model and a truly capable one.
  • The Kuiper Range Statistic: This is a clever way to measure calibration. It plots accuracy against effort (number of steps). A well-calibrated agent (like a human) knows when a query is failing and changes tactics. A poorly calibrated agent spends massive amounts of "compute" (steps/tokens) on questions it never actually solves.
  • Error Taxonomy: They broke down failures into four categories: Retrieval (wrong doc), Navigation (wrong page), Comprehension (right page, wrong answer), and Refusal.

Datasets

The paper introduces MADQA (Multimodal Agentic Document QA):

  • Scope: 2,250 human-authored questions grounded in 800 PDFs.
  • Diversity: Covers 13 domains (Financial, Legal, HR, etc.) with high layout diversity.
  • Complexity: 17.3% of questions are "multi-hop," requiring information from different pages or even different documents.
  • Visual Necessity: 58% of questions require visual understanding (tables, charts, or layout) and cannot be solved by text alone.

Key Insights and Ideas

  • The "Cold Start" Gap: Humans are incredibly efficient. On their very first search query, humans hit ~50% accuracy. The best agent (Gemini 3 Pro) starts at only ~12%, requiring many iterative steps to "catch up" to human performance.
  • Semantic vs. Physical Distance: For multi-hop questions, the physical distance between pages doesn't matter much. What kills performance is semantic distance—if the two pieces of evidence are conceptually different, agents struggle to bridge the gap.
  • The Brute-Force Trap: Agents often succeed by simply trying more things (brute force), whereas humans succeed by being strategic. When an agent fails, it tends to rephrase its query slightly; when a human fails, they pivot to a completely different search strategy.
  • Complementary Strengths: Interestingly, humans and agents fail on different questions. Humans suffer from "attention fatigue" on long, boring extractions, while agents fail on complex navigation. This suggests that the best future systems might be human-agent hybrids.

Key Results

  • Top Performers: Gemini 3 Pro (82.2% accuracy) and Claude 4.5 Sonnet (80.6%) are the current state-of-the-art agents.
  • The Oracle Gap: Even with "Oracle Retrieval" (being told exactly which page to look at), there is an 18% gap in performance, meaning retrieval isn't the only bottleneck—reasoning over the retrieved content is still hard.
  • Cost of Flexibility: "Recursive Language Models" (which can write code to process documents) are theoretically powerful but currently "catastrophically" expensive, with one model (Claude 4.5 RLM) costing $850 to run the test set while still underperforming its simpler agentic counterpart.

Limitations and Future Work

  • Geographic Bias: The corpus is currently limited to English-language, U.S.-centric documents.
  • Data Contamination: Since the documents are public, some models may have "memorized" facts during training. The authors estimate this "guessability" at around 11%.
  • Granularity: Evidence is currently tagged at the page level. Future work could move to "bounding box" or "token-level" grounding for even finer-grained analysis.
  • Proposed Fixes: The authors suggest that agents need episodic memory (to remember what they've already seen) and reinforcement learning from search tool feedback to improve their navigation policies.

Summary updated

Abstract

Multimodal agents offer a compelling path to automating complex document-intensive workflows, yet a critical question remains: do these architectures demonstrate genuine strategic reasoning, or simply conduct stochastic trial-and-error search? To address this, we introduce Agentic Document VQA, 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 and reliably differentiate between varying levels of agent capability. To rigorously assess agentic behavior, we introduce a novel evaluation protocol for measuring the accuracy-effort trade-off. Using this framework, we find that humans show strong metacognitive calibration, adapting or abandoning failed strategies, whereas frontier agents often persist in unproductive loops with diminishing returns. We release the dataset, evaluation harness, and leaderboard to help facilitate the transition from brute-force retrieval to calibrated, efficient reasoning.
BibTeX
@inproceedings{borchmann2026strategic,
  author = {Łukasz Borchmann and Jordy Van Landeghem and Michał Turski and Shreyansh Padarha and Ryan Othniel Kearns and Adam Mahdi and Niels Rogge and Clémentine Fourrier and Siwei Han and Huaxiu Yao and Artemis Llabrés and Yiming Xu and Dimosthenis Karatzas and Hao Zhang and Anupam Datta},
  title = {{Strategic Navigation or Stochastic Search? How Agents and Humans Reason Over Document Collections}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=ds3ZOevkwx},
}
Figure