SAI
← All ICML 2026 orals

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

OralReplication score 6%Paper PDFCode repoOpenReview

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

SAI replication review · Referee report

Summary

The paper introduces MADQA, a benchmark of 2,250 fully human-authored questions grounded in 800 fresh, heterogeneous PDF documents (18,619 pages, 63 fine-grained categories in 13 domains), and studies whether multimodal agents doing document-collection QA exhibit strategic navigation or fall back on brute-force search. The conceptual move I found most interesting is treating calibrated effort as a first-class evaluation axis alongside accuracy: the Kuiper statistic on the cumulative-difference curve of correctness sorted by effort formalizes the intuition that a well-calibrated agent should invest more compute only when it actually converts to accuracy. The paper combines this with a page-level attribution metric (Page F1 vs. Doc F1) to diagnose "last-mile" navigation failures, and derives a principled Test/Dev split via Classical Test Theory so the leaderboard preserves headroom without inflating evaluation cost. The most striking empirical finding is a complementarity result: humans with a BM25 search tool and Gemini 3 Pro's BM25 agent land at the same 82.2% accuracy, yet their pairwise Cohen's κ\kappa is only 0.24 — they succeed on largely disjoint subsets, with humans failing mostly on comprehension and models failing on retrieval. The oracle-retriever human number (99.4%) frames the residual ~17 pp gap as a retrieval bottleneck, and the accompanying error-taxonomy (retrieval/navigation/comprehension/refusal) is a useful diagnostic scaffold. The conceptual limitation I want to flag is that the paper's headline framing conflates two things: whether an agent knows when to stop (calibration) and how much wasteful compute it spends (efficiency). Kuiper as defined is a sign-agnostic range of the deviation curve, so the same value can encode very different failure modes, and the interpretive claims in §3.3 and §5 do not always distinguish these. The replication run could not test the paper's central Table 3 numbers end to end (see below), but nothing in what did execute contradicts the paper. Several load-bearing numbers (guessability arithmetic, cross-page error shares, Kuiper sensitivity ceilings, the 18%/17.2% oracle gap) do not fully line up between sections.

Strengths

  • Conceptual contribution. Framing calibrated effort as a distinct evaluation axis alongside correctness and attribution — and grounding it in a non-parametric cumulative-difference construction — is a clean, well-motivated move that pushes past the standard "more compute = better" reporting style.
  • Data provenance discipline. Documents are freshly curated from DocumentCloud in themed clusters (specifically to support cross-doc reasoning), questions are entirely human-authored, and §2.3 quantifies construct validity via lexical-overlap, dense-retrieval upper bound, and parametric-memory probes rather than asserting it.
  • Attribution granularity. Page-level (not just document-level) evidence annotation, combined with the Page F1 / Doc F1 pair, gives the community a concrete way to isolate the "last-mile" navigation failure that managed-RAG services exhibit (their high Doc F1 masks weak Page F1).
  • Human-vs-agent complementarity result. The κ=0.24\kappa = 0.24 finding — same accuracy, largely disjoint error sets, with humans failing on comprehension and agents on retrieval — is the paper's most useful empirical contribution and directly motivates hybrid pipelines rather than a single scaling story.
  • Principled split creation. Applying CTT with item difficulty and point-biserial discrimination, plus a Sentinel Pool of very hard items, is a substantially more defensible test-selection procedure than the ad-hoc slicing used in most contemporary QA benchmarks; the split sizes reproduce exactly from the released artifact.
  • LLM-judge honesty. The paper reports an adversarial stress test (Table 13) and per-answer-type calibration (Table 14) on the judge, notes its one-sided error profile (false rejections dominate false acceptances), and applies Rogan–Gladen bias correction rather than treating the judge as unbiased.

Weaknesses

  • Formal Property 5 (Agentic) is stated as a hard guarantee, then quietly relaxed. Property 5 reads as a definitional constraint ("no single retrieval query q′q' may exist such that RETRIEVE(q′)⊇E(q') \supseteq E"), but the next paragraph downgrades Properties 2, 5, 6 to "targeted by design (encouraged, not strictly enforced)." Every downstream claim that MADQA measures agentic reasoning inherits this softness; the paper needs to reconcile the formal statement with the empirical property.
  • Kuiper interpretation exceeds what a two-sided range identifies. The statistic is max⁡(Dk)−min⁡(Dk)\max(D_k) - \min(D_k); a large value can arise from over-performance at low effort or under-performance at high effort. §3.3 and §5 read a high KK as "wasted budget on hard queries," which is only one of the two failure modes. Reporting the signed decomposition (as in Kuiper's classical D+/D−D^+ / D^-) or a directional variant would restore what the interpretive claim needs.
  • "K is largely invariant" is only partly true. For GPT-5, Kuiper varies monotonically from 67.0 (kk=3) to 59.1 (kk=10) — a ~12% drift paired with monotonic accuracy increase. Table 19 also shows RLM GPT-5.2's Kuiper spanning 21.1–31.2 across effort measures, a ~48% spread that exceeds the "at most 20%" ceiling claimed in §3.3. The robustness argument overstates what the sensitivity tables actually show.
  • "At least 18% better" for oracle-retriever humans overstates the gap. Human Oracle 99.4% minus best-agent 82.2% is 17.2 pp — a number the very next sentence uses correctly. The two adjacent claims disagree, and Table 3 supports only the smaller number.
  • "70+ pp of genuine comprehension" is both arithmetically off and an inferential leap. The paper equates the gap between guessability (~11%) and headline model accuracy (~80%) with "genuine comprehension." Arithmetically, 80 − 11 ≈ 69, not "70+." Substantively, the identity ignores partial memorisation, the effect of the retrieval scaffold, and stylistic prompt effects.
  • Cross-page error rate mismatch. The prose reports X-Page error rising to ~35%, but Figure 16's tabulated top-4-system X-Page ratios (38/51, 37/51, 36/51, 40/51) imply 22–29%. The 35% figure is much closer to the X-Doc column. This propagates to the substantive claim that intra-document navigation is harder than cross-document retrieval.
  • Attribution of X-Page errors to "retrieval failure" conflicts with the cascade definition (Retrieval = Doc F1 = 0). By construction, X-Page questions share a single document, so a page miss inside that document is a Navigation Failure. The prose in H.3 swaps the two categories.
  • "Top performers reformulate more" is contradicted by the human baseline. Humans achieve 82.2% while sitting near the middle of Figure 23's reformulation-drift distribution (~0.23). The correct reading is that humans avoid the need for reformulation with better cold-start queries; drift is a compensation mechanism for weak first queries, not a strategy-quality signal.
  • Impact-Statement claim about Page F1 as a faithfulness metric. Page F1 measures citation-to-gold overlap; it does not verify that the answer is entailed by the cited pages. The Impact Statement's claim that MADQA "penalises answers not explicitly supported by the retrieved evidence" describes something Page F1 does not do.
  • Guessable items retained despite violating closed-world. The Closed-World property is called "enforced by construction," yet 9–15% of items are answerable from parametric memory. The three retention arguments in §E.3 are reasonable operationally but do not address the definitional tension; reporting a closed-world subset score alongside the headline would resolve it.
  • Cold-start comparison mixes different measurement units for humans and agents. The "50% vs. 12% on the first query" contrast treats a human's read/plan/type sequence as equivalent to an agent's single tool call. The 50% figure includes upstream cognitive planning that is not counted; the 12% does not.
  • Human baseline variance under-quantified. Five annotators each answer a disjoint 100-question slice, so per-annotator variance is entangled with per-item variance. The reported CI on the 82.2% headline treats the 500 items as i.i.d. without annotator-group adjustment, and no inter-annotator pairwise comparison exists on the full 500 items — only on a 50-item stratified subset.
  • Same-family LLM judge. Gemini 2.5 Flash is the judge, and Gemini-family systems occupy four of the top-eight rows. The adversarial stress test uses only Gemini 3 Pro predictions, so family favoritism cannot be diagnosed from the calibration protocol as reported.
  • Cross-family trigram-recall reading. Trigram matching yields ~1 page hit at 51% recall, which implies that for over half the questions a simple Ctrl+F strategy lands on approximately the right page. The lexical-overlap argument treats this as supportive, but it quietly bounds the difficulty floor from below.
  • Naming and small counting inconsistencies. Table 2 domain-Qs sum to 2,249 not 2,250; Figure 11 caption labels the full dataset as n=2311n=2311 vs N=2250N=2250 everywhere else; Table 12's Free-Text+Visual rows sum to 2,240; Artifacts sub-rows sum to 139 vs 150 parent; Retrieval Failure share appears as 35.7% (Table 24) but 39.1% (Appendix I); Gemini 2.5 Pro is discussed in §5.1 but absent from Table 3; GPT-5 vs GPT-5.2 usage varies across Tables 3, 17, 18, 19; "Structured + Other Visual" invokes a category not in the taxonomy. Individually minor, collectively they erode confidence in the reported figures.
  • Bigram precision/recall arithmetic does not reconcile. With ~24 matched pages at 2.6% precision, expected retrieved-gold-per-question is ~0.62, yet Table 9 reports bigram recall of 86% on a benchmark with ~1.3 gold pages per question. One of the two numbers appears mis-stated.
  • Semantic-distance signal aggregated over only five models. The 38-pp accuracy drop with semantic distance in Table 21 is aggregated over five of the 17+ BM25 configurations elsewhere in the paper; per-bin counts of 23–29 questions leave the tail highly sensitive to the panel choice.

Reproducibility & code

The veritas full-mode replication reconstructed and ran the code. Because the released repo blocks on corpus completeness against an explicit "proceed" instruction, only 2 of 10 planned steps executed and 29 of 32 claims — including all five headline claims (Table 3, the 82.2% BM25-vs-78.6% File-Search comparison, the 17.2 pp oracle gap, the Kuiper 14.6-vs-agents result, and the cold-start curve) — were graded not_attempted. That is a limitation of the replication run, not a refutation. Where evidence did land, it agrees with the paper. The distinct code-grounded findings are:

  • Benchmark composition reproduces exactly. The Table 2 aggregates check out cell-for-cell against a rebuilt corpus: 800 PDFs, 18,619 pages (median 5, mean 23.3, max 859), 2,250 questions across 13 domains. One PDF (23696095.pdf) is permanently 403, but the remaining 799 already sum to 18,619 pages, so the total is unaffected.
  • CTT split sizes and disjointness reproduce; the split's discriminative claims do not. Train 1,550 / Dev 200 / Test 500 with zero id or verbatim-question overlap. The Spearman ρ>0.85\rho > 0.85 vs. the full benchmark and the ~100-item Sentinel Pool cannot be recomputed from the release because the per-item scoring matrix over the 16 pinned models is not shipped and neither is the greedy CTT selector script. The split is auditable structurally but not psychometrically.
  • Judge calibration machinery runs; the κ=0.88\kappa = 0.88 headline does not reproduce. eval/metrics.py hard-codes sensitivity 0.980 and specificity 1.000; the Rogan–Gladen formula runs end-to-end and matches the paper. But the 200 human-labelled predictions used to derive those constants (plus the 100 adversarial cases from Table 13 and the 200 per-answer-type samples from Table 14) are not shipped, and no κ\kappa computation exists anywhere in the codebase. A load-bearing number in Table 3's every row cannot be re-derived from the public release.
  • Test-split labels are withheld. All 500 test rows in the released HuggingFace dataset have empty answer_variants, evidence, and domain. This is a deliberate leaderboard design, but its consequences — none of the Table 3 headline numbers are locally reproducible — are not flagged as a data-availability caveat.
  • Several tabulated baselines have no shipped implementation. BM25 MLLM Agent, RLM, HEAVEN, and the two Managed-RAG paths are present in baselines/. MDocAgent, M3DocRAG, ColBERTv2 + LLaMA, and Claude Agent + Semtools are reported in Table 3 but have no runnable implementation in the release; a reproducer would need to port them from the originals.
  • The Mistral-OCR markdown corpus documented for RLM is a dead reference. Both advertised paths (OxRML/pdfs-to-markdown-mistral-ocr and agentic-document-ai/pdfs-to-markdown-mistral-ocr) return 404 on HuggingFace, and neither the OxRML org nor the MADQA repo carries a mirror. Reproducing the RLM row therefore requires regenerating the OCR corpus from scratch.
  • Behavioural analyses depend on trajectory dumps that are not released. Kuiper curves, recovery-rate curves (Figure 22), reformulation drift (Figures 23–24), the error-cascade figures (13–15, 18), the first-query advantage (Figure 21), the 107-item human/model disagreement analysis, and the response-time correlation all require per-system per-question search trajectories. In the human case they additionally require the timestamped Streamlit interaction logs of §C.2. None are shipped.
  • Construct-validity analyses have no runnable code. Table 9 (n-gram overlap), Table 10 (dense-retrieval upper bound), Table 11 and Prompts 1–2 (guessability), Table 12 and Prompt 3 (modality classifier), and Tables 21–22 (multi-hop semantic-distance) are described in prose only; no runners or per-question outputs are shipped.
  • Effort logging is inconsistent across agents. evaluate.py reads only step counts; token counts and time are logged differently across the OpenAI, Anthropic, Gemini, and RLM variants, so Tables 18–19 (Spearman between effort measures; Kuiper across measures) cannot be regenerated without a unified logging schema.
  • BM25 agent silently degrades under DocumentCloud rate-limits. get_pdf_page_as_png returns nothing when the host is throttled, and the agent then reasons over zero images without raising — a correctness-changing silent failure.
  • OCR path depends on undocumented AWS Textract. The shipped OCR script (baselines/utils/ocr-documents/textract.py) requires AWS credentials; the paper does not mention this dependency, so a reproducer without AWS access must reimplement the interface.
  • Recursive-LM baseline has two silent bugs. AnthropicClient requires an explicit api_key with no env fallback, and structured-output formatting routes through OpenAI even under --backend anthropic. Both fail without an actionable error.
  • README default metric is ANLS, not the LLM-judge metric the paper reports.* eval/evaluate.py defaults to ANLS* >= 0.5, but every accuracy number in Table 3 is a Rogan–Gladen-adjusted LLM-judge score. A reproducer following the README will silently compute a different headline number.
  • Managed-RAG document-count discrepancy. Gemini File Search is documented as uploading 796 PDFs against an 800-PDF corpus, with no explanation for the four-document gap.

Recommended Changes

Essential.

  • Reconcile Property 5 with empirical treatment. Move Property 5 into the "targeted by design" group, or add an empirical construct-validity check (e.g., a §E.2-style dense-retrieval bound) quantifying what fraction of items actually satisfy it. Do not leave it as a definitional guarantee the annotation protocol did not enforce.
  • Report signed/directional Kuiper. Add max⁡(Dk)\max(D_k) and min⁡(Dk)\min(D_k) (or D+/D−D^+ / D^-) alongside KK in Table 3, so the interpretive claim "expending budget on complex queries it ultimately fails to solve" is actually licensed by the numbers. This addresses the sign-agnostic-interpretation weakness above.
  • Correct the Kuiper robustness ceiling. Restrict "at most 20%" to BM25 rows, or replace with the observed spread including the RLM GPT-5.2 case (~48%). Similarly, either drop "largely invariant to kk" for GPT-5 or add the caveat that the point-estimate has monotonic kk-dependence for at least one system.
  • Fix the "18% better" / 17.2 pp inconsistency and the "70+ pp" arithmetic. Choose one oracle-gap number and use it wherever the gap is quoted; the 17.2 pp value is the one Table 3 supports. Change "70+" to "nearly 70" or rederive the exact figure from the mean guessability.
  • Fix the cross-page vs cross-document error-rate attribution. Report the X-Page error rate consistent with Figure 16 (~22–29%, not ~35%), and correct the sentence attributing X-Page misses to "retrieval failure" — by the cascade's own definition these are Navigation Failures.
  • Reconcile Retrieval Failure share (35.7% vs 39.1%) and the Gemini 2.5 Pro reference. Update Appendix I to match Table 24, and either add the Gemini 2.5 Pro row to Table 3 or correct the model name in §5.1 and Figures 15/22. Also unify GPT-5 vs GPT-5.2 identifiers across Tables 3, 17, 18, 19.
  • Reframe the reformulation-drift finding. Present drift as a compensation mechanism for weak cold-start queries, not a strategy-quality signal — the human baseline breaks the monotonic reading. Adjust §5.1's "Query Reformulation Magnitude Predicts Success" accordingly.
  • Rephrase the Impact Statement's Page F1 claim. Describe citation coverage rather than "faithfulness," or introduce a separate entailment check that actually verifies answer-evidence support.
  • Report a closed-world subset score. Alongside headline accuracy, add per-model accuracy on the items each model cannot guess without evidence. This directly addresses the tension between the Closed-World property and the ~11% guessable items.
  • Release the per-system prediction JSONLs and anonymised human trajectory logs. Without these, the recovery-rate, reformulation-drift, error-cascade, and human/model disagreement analyses cannot be reproduced. Ship at least the Dev-split trajectories, since Test-split labels are hidden by design.
  • Ship analysis scripts for the construct-validity tables (n-gram overlap, dense-retrieval upper bound, guessability probe, modality classifier, multi-hop semantic-distance) under an analysis/ directory. If per-question outputs are already produced, release those as CSV/JSONL and cite them from the corresponding tables.
  • Ship the CTT split-creation code and the per-item scoring matrix over the 16 pinned models. Without either, no future leaderboard refresh can produce a comparable Test/Dev split.
  • Ship the 500 human-labelled judge-calibration predictions and the κ\kappa/sensitivity/specificity computation. Every accuracy number in Table 3 depends on a hard-coded pair of constants whose empirical support is not in the release.
  • Ship a runnable Semtools baseline and either ship or clearly cite ports of MDocAgent, M3DocRAG, and ColBERTv2 + LLaMA — the four missing rows of Table 3 currently have no artifact.
  • Fix the released OCR/RLM paths. Either publish the Mistral-OCR markdown corpus (both advertised HuggingFace paths currently return 404) or ship the regeneration script. Document the AWS Textract dependency in the OCR pipeline. Fix the two silent recursive-lm bugs (missing AnthropicClient env fallback; structured-output routing through OpenAI under --backend anthropic). Add a graceful error path when DocumentCloud rate-limiting empties the page-render buffer, and change evaluate.py's default metric from ANLS* to the LLM-judge score the paper reports.

Suggested.

  • Add per-annotator human accuracy (five numbers plus a between-annotator SD) and either adjust the CI for the annotator-slice grouping or replicate a subset with paired annotators.
  • Add a cross-family judge audit — evaluate Claude and GPT judges on a shared calibration slice, so the reader can see whether Gemini 2.5 Flash exhibits family favoritism on the four Gemini-family agents.
  • Address the trigram-recall reading. State explicitly that the 51% trigram recall does not translate into a 51% single-pass solvability floor (with a small experiment or citation), otherwise the lexical-overlap argument is weaker than it appears. Reconcile the bigram "24 pages @ 2.6% precision vs 86% recall" arithmetic in the same table.
  • Extend the semantic-distance analysis beyond five models to the same panel used in Table 3, so the 38-pp drop is not sensitive to which five configurations were chosen.
  • Soften "proves" language. Replace class-level claims ("MADQA remains unsolved for efficient agents") with descriptive statements about the tested systems.
  • Clarify the cold-start units. Explicitly note that a human "first query" includes read/plan/type steps not counted in the agent's step budget, and provide a token- or time-normalized variant of Figure 7 if possible.
  • Clarify the Managed-RAG 796 vs 800 document gap with a footnote in Appendix G.2.
  • Fix small counting/labeling issues — Table 2 domain-Qs sum, Figure 11 n=2311n=2311, Table 12 category sums, "Structured + Other Visual" naming — so the arithmetic is internally consistent.
  • Add a data-availability section that consolidates what the release contains (BM25/RLM/HEAVEN/File-Search code, metrics, Dev labels) vs what it does not (Test labels, human trajectories, several baselines, construct-validity scripts, CTT split code, judge calibration set, Mistral-OCR corpus).