Strategic Navigation or Stochastic Search? What MADQA Reveals About How Agents Reason Over Documents

When we deploy a multimodal agent against a corpus of business documents and watch it produce the correct answer, we tend to assume it found that answer the way a competent analyst would: by forming a hypothesis, locating the right document, and synthesizing evidence across pages. The paper "Strategic Navigation or Stochastic Search? How Agents and Humans Reason Over Document Collections" asks whether that assumption holds. Its answer is sobering. Agents can hit the same accuracy numbers as human searchers while arriving there through an entirely different process, one that looks less like reasoning and more like exhaustive trial and error.

This distinction between matching an outcome and matching a method is the conceptual core of the work, and it deserves a closer look than a leaderboard number can provide.

The Benchmark: MADQA and Why Its Construction Matters

The authors introduce MADQA (Multimodal Agentic Document QA), a benchmark of 2,250 human-authored questions grounded in 800 heterogeneous PDF documents. What separates it from the crowded field of document QA and retrieval benchmarks is not just scale but methodological discipline. The paper situates MADQA against more than twenty prior benchmarks (DocVQA, MMLongBench-Doc, ViDoRe v3, DocBench, BRIGHT, and others) and identifies three recurring weaknesses it sets out to address.

• Format. Many agentic research benchmarks (Researchy Questions, BRIGHT) operate on HTML or plain text, ignoring the visual structure (tables, figures, layout) that defines real documents.
• Scope. Visually rich PDF benchmarks often restrict themselves to narrow verticals like finance, or evaluate with single-step retrieval metrics that cannot capture iterative planning.
• Data integrity. Several benchmarks generate their own questions with MLLMs, which biases evaluation toward models similar to the teacher and conflates retrieval quality with the generator's writing ability. Others recycle documents from older datasets, inviting contamination.

MADQA tries to close all three gaps simultaneously: fresh PDFs with high layout diversity, broad domain coverage requiring multi-step reasoning, and questions written entirely by humans. The authors invoke Classical Test Theory to design questions that maximize discriminative power, meaning the items are calibrated to separate weak agents from strong ones rather than clustering near the floor or ceiling. This is an underused idea in benchmark design. Most benchmarks are built for coverage; few are built explicitly to discriminate across ability levels, and the difference shows up in how informative the resulting scores are.

The task definition is also tighter than usual. The six properties the authors enforce or target (extractive answers, multi-hop evidence, closed-world reasoning, grounded and minimal evidence sets, an agentic property, and a visual property) are worth dwelling on. The agentic property is the cleverest: a question qualifies only if no single retrieval query can surface all the required evidence. This is a structural guarantee that the task cannot be solved by one good embedding lookup. It forces decomposition and iteration by construction, which is exactly what you need if you want to measure planning rather than retrieval luck.

The Central Finding: Same Accuracy, Different Process

The headline result is that the best agents match human searchers in raw accuracy. If you stopped reading there, you would conclude that agents have reached parity. The paper's contribution is to show that this parity is an illusion of aggregate metrics.

Three observations break the illusion:

1. Agents and humans succeed on largely different questions. Even when overall accuracy is comparable, the per-item success patterns diverge. This is the most telling result, because it means the two systems are not interchangeable; they have different competence profiles. A composite system or an evaluation that only reports a single accuracy figure would miss this entirely.

2. Agents rely on brute-force search to compensate for weak strategic planning. Rather than decomposing a query, identifying the right document, and navigating to the relevant page, agents issue many retrievals and let volume substitute for precision. This is where the paper's accuracy-effort trade-off protocol earns its keep. By measuring not just whether an agent answered correctly but how much retrieval effort it expended, the authors expose the hidden cost behind matched accuracy.

3. Both agents and humans leave a roughly 20% gap to oracle performance, and agents in particular get stuck in unproductive loops, repeating retrievals that do not move them closer to the evidence.

The framing as strategic navigation versus stochastic search is apt. A strategic navigator forms a plan and prunes the search space; a stochastic searcher samples broadly and hopes coverage compensates for the lack of a plan. The data suggest current agents lean heavily toward the latter.

My Take: The Missing Capability Is Calibrated Stopping

What I find most interesting is what the unproductive loops imply about the agents' internal models of their own progress. An agent that loops is one that cannot tell the difference between "I have not found the evidence yet" and "the evidence is not reachable with my current strategy." It lacks a reliable signal for when to stop, when to replan, and when to declare failure.

This connects to a broader theme in agent research: calibration of effort is a distinct capability from accuracy of reasoning. We have spent the last few years optimizing models to be correct when they answer. We have spent comparatively little effort teaching them to estimate the marginal value of an additional retrieval step. The MADQA results suggest these are separable skills, and that the second one is currently the bottleneck.

There is also a subtle methodological point worth emphasizing. The finding that agents and humans win on different questions undermines a common shortcut in evaluation, namely treating human performance as the target distribution. If an agent matches the human aggregate but on a disjoint set of items, then "human-level" is not a meaningful description of its behavior. It is a coincidence of marginals. For high-stakes enterprise workflows, the failure modes are what matter, and disjoint failure sets mean agent errors will be distributed differently and therefore harder to anticipate from human intuition.

The brute-force pattern also raises an efficiency and cost concern that the leaderboard view obscures. In production, retrieval volume translates directly into latency and compute spend. An agent that achieves human accuracy by issuing five times the retrievals is not equivalent to a human; it is a more expensive substitute whose cost scales poorly with corpus size.

Limitations and Open Questions

The paper is candid that the agentic property is targeted by design rather than perfectly enforced, and the diversity levels in the benchmark comparison table are coarse relative categories. Those are reasonable concessions, but they mean the agentic difficulty of any individual question is partly an estimate. I would also want to see how the accuracy-effort curves behave as corpus size scales, since the cost of brute-force search grows with the document collection and the gap between strategy and search may widen.

A deeper open question is whether the planning deficit is a training problem or an architectural one. Can better prompting and reward shaping for efficient termination close the gap, or do agents need an explicit world model of the corpus and their own search state? My inference is that prompting alone will not suffice; the loops suggest a representational gap, not just a behavioral one.

Conclusion

MADQA reframes a question we thought we had answered. Raw accuracy parity between agents and human searchers does not mean agents reason like humans. They compensate for weak planning with search volume, succeed on different questions, and leave a meaningful gap to oracle performance. The next frontier, as the authors and the accompanying summary both note, is not more retrieval. It is calibrated effort: agents that know what to look for, where to look, and crucially, when to stop. Building benchmarks that measure the process and not only the outcome, as MADQA does, is a prerequisite for getting there.