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

Łukasz Borchmann, Jordy Van Landeghem, Michał Turski, Shreyansh Padarha, Ryan 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 MADQA benchmark introduces a rigorous way to test whether multimodal AI agents are truly "strategic" or just lucky. While the best agents can now match human accuracy on complex document tasks, they do so through inefficient brute-force searching rather than the targeted, calibrated reasoning that humans naturally exhibit.

What Problem Does This Paper Address?

As we move toward "agentic" AI, we expect models to handle complex workflows—like digging through hundreds of messy PDFs to find and aggregate specific data. However, current benchmarks often fall short: they use plain text instead of visual documents, rely on AI-generated questions that are too easy, or focus on single-page lookups.

The authors identify a critical "strategic gap." We don't just need agents that can find an answer eventually; we need agents that can plan their search, recognize when they are stuck, and navigate visual structures (like tables and forms) efficiently. The paper asks: Are these agents performing strategic navigation or just stochastic (random) search?

Methods

The researchers formalize the task of Agentic Document Collection VQA. To solve a query, an agent must iteratively retrieve pages, reason over visual/textual content, and synthesize evidence across multiple documents.

Key methodological innovations include:

  • The Accuracy-Effort Trade-off: Instead of just looking at the final score, they use the Kuiper statistic to measure "calibration." A well-calibrated agent (like a human) invests more effort only when it's likely to lead to success. A poorly calibrated agent persists in "unproductive loops," wasting compute on problems it can't solve.
  • Human-in-the-loop Baselines: They built a custom search interface for humans that mirrors the tools available to the AI agents, allowing for a true apples-to-apples comparison of search trajectories.
  • Classical Test Theory (CTT): They used CTT to select questions that maximize "discriminative power," ensuring the benchmark can clearly distinguish between a "lucky" model and a truly "capable" one.

Datasets

The paper introduces MADQA (Multimodal Agentic Document QA):

  • Scale: 2,250 human-authored questions grounded in 800 heterogeneous PDF documents.
  • Diversity: Covers 13 high-level domains (Financial, Legal, Technical, etc.) and 63 categories.
  • Complexity: 17.3% of questions are "multi-hop," requiring information from different pages or entirely different documents.
  • Visual Necessity: 58% of the questions cannot be answered by text alone; they require understanding layouts, checkboxes, or tabular structures.

Key Insights and Ideas

  • The "Cold Start" Disparity: Humans are remarkably efficient. On their very first search query, humans reach ~50% accuracy. The best AI agents start at a dismal ~12% and must "brute-force" their way up to human-level accuracy through multiple iterations.
  • Same Accuracy, Different Competencies: While top agents (like Gemini 3 Pro) and humans both hit ~82% accuracy, they succeed on different questions. Humans fail due to "attention fatigue" on tedious extractions, while agents fail due to retrieval bottlenecks and poor planning.
  • The Oracle Gap: Even with the best tools, there is a ~18% gap between the best agents and "Oracle" performance (where the correct page is handed to the solver). This suggests that retrieval, not just reasoning, remains the primary bottleneck for agentic systems.
  • Semantic vs. Physical Distance: For multi-hop questions, the physical distance between pages doesn't matter. What breaks the models is semantic distance—when the evidence spans conceptually dissimilar contexts, accuracy drops by 38 percentage points.

Key Results

  • Top Performers: The Gemini 3 Pro BM25 Agent achieved 82.2% accuracy, matching the human baseline (82.2%).
  • Efficiency Gap: Humans achieved a Kuiper statistic of 14.6 (lower is better, indicating better calibration), while agents ranged from 22.9 to 73.2. This confirms that agents are far less "rational" in how they spend their computational budget.
  • Agentic Advantage: Agentic systems (those that can iterate and plan) consistently outperformed "static" RAG systems by significant margins, proving that iterative loops are necessary for complex document sets.

Limitations and Future Work

The authors acknowledge several limitations:

  • Geographic Bias: The corpus is predominantly U.S.-centric and English-only.
  • Data Contamination: Since the documents are public, some models may have seen them during pre-training (though the authors measured "guessability" to bound this effect).
  • Granularity: Evaluation is currently at the page level. Future versions could require finer-grained grounding (e.g., specific bounding boxes).

Future Directions: The authors suggest that episodic memory (helping agents learn a corpus's specific terminology over time) and reinforcement learning from search tool feedback are the most promising paths to closing the strategic gap.

Summary updated

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.
BibTeX
@inproceedings{borchmann2026strategic,
  author = {Łukasz Borchmann and Jordy Van Landeghem and Michał Turski and Shreyansh Padarha and Ryan 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},
}

Loading related content...

Figure