PaperlayerView exact revision on arXiv

Source-linked AI summary

Hypergraph-Enhanced Evidence Selection for Long-Context Multimodal Document QA

Wenxin Zhao, Jiachuan Wang, Xinyi Zhu, Jiake Ge, Haoyang Li, Yongqi Zhang, Shuangyin Li, Lei Chen

arXiv:2610.35542v2cs.IRcs.DB

TL;DR

Long-context multimodal document QA requires selecting evidence spread across pages and modalities within limited VLM input budgets, while existing systems often use static selection over fixed-granularity units. HyperDoc builds a document hypergraph and performs query-aware, cost-aware hyperedge selection; experiments report that it outperforms state-of-the-art baselines across backbone settings on representative benchmarks.

  • Problem

    Long-context multimodal document QA must select evidence dispersed across pages and modalities within limited VLM input budgets, while existing pipelines often use static selection over fixed-granularity units.

    Source: §I · pp. 1–2

  • Method

    HyperDoc builds a document hypergraph that preserves structural and cross-page relations, then uses query-aware, cost-aware hyperedge selection to construct evidence under the input budget.

    Source: §I · p. 2, D. Cost-Aware Hyperedge Selection · pp. 6–7

  • Results

    Experiments report that HyperDoc outperforms state-of-the-art baselines across all backbone settings on representative benchmarks.

    Source: §I · p. 2

  • Takeaways & Limitations

    Across representative benchmarks, HyperDoc is reported to improve answer quality over diverse baselines with a favorable cost-latency trade-off.

    Source: §VII · p. 12

Abstract

from arXiv · show

Long-context multimodal document question answering (QA) has become an important yet challenging task for modern vision-language models (VLMs), as it requires reasoning over evidence dispersed across pages and modalities within limited input budgets. Current pipelines adopt retrieval-augmented generation (RAG) to select multimodal evidence for downstream VLMs. However, existing systems mainly rely on static selection rules over fixed-granularity retrieval units such as pages or blocks, resulting in information loss during retrieval and suboptimal performance in downstream reasoning. To alleviate these issues, we formulate the core task as budget-aware evidence selection over structured document evidence and propose HyperDoc, a document RAG framework that constructs compact yet sufficient evidence while preserving document relations. Specifically, HyperDoc constructs a document hypergraph to explicitly capture structural, logical, and cross-modal relationships among multimodal document elements. Over this structured evidence space, HyperDoc performs adaptive cost-aware hyperedge selection based on query intent and input budget. Extensive experiments on three representative benchmarks demonstrate that HyperDoc outperforms various types of state-of-the-art baselines.

I. INTRODUCTION

Long-context multimodal document QA must select evidence dispersed across pages and modalities within limited VLM input budgets. HyperDoc represents document relations in a hypergraph and selects query-aware evidence under a budget; experiments report improvements over state-of-the-art baselines.

I. INTRODUCTION

  • Evidence may span pages and modalities, while VLM context windows and long-document processing impose input, memory, and computation budgets.Relevant evidence can include text, layout, charts, tables, and images.Source: §I · p. 1
  • Page- or block-based retrieval can break document hierarchy and logical relations, fragmenting evidence needed for multi-page reasoning.Fixed top-K selection also trades higher input cost and noisy evidence against the risk of discarding evidence needed to answer.Source: §I · p. 2
  • Query needs range from document-wide retrieval to localized facts, but static, intent-agnostic selection does not adapt evidence granularity or scope.Retrieved units may also lack query-aligned organization.Source: §I · p. 2
  • HYPERDOC constructs a document hypergraph over multi-granular units to preserve structural containment and cross-page contextual associations, then selects and organizes query-aware evidence under a budget.The task is to construct compact VLM-ready textual and visual input whose cost stays within the model budget.Source: §I · p. 2, §II · p. 3
  • HYPERDOC formulates query-aware hyperedge selection as coverage maximization and uses a cost-aware greedy algorithm to adapt selection to each query under limited input budgets.The selection problem is described as NP-hard.Source: §I · p. 2
  • Experiments on representative benchmarks report that HYPERDOC outperforms state-of-the-art baselines across all backbone settings.The paper also reports efficiency evaluations, ablations, and parameter sensitivity analyses.Source: §I · p. 2

III. OFFLINE DOCUMENT HYPERGRAPH CONSTRUCTION

HyperDoc represents multimodal documents with multi-granular elements and relations, then groups visual anchors with relevant textual context in contextual hyperedges. This lets query-time retrieval select visual evidence together with its supporting context.

III. OFFLINE DOCUMENT HYPERGRAPH CONSTRUCTION

  • The construction addresses heterogeneous evidence granularity, contextual relations among elements, and document structure that can guide query-time selection.The paper treats layout-preserving parsing, contextual hyperedges, and selectable structural scopes as three representation challenges.Source: §III · p. 3

A. Multimodal Document Parsing

  • Pages are rendered as images and parsed into layout-aware blocks, retaining visual layout and textual content across multiple granularities.Visual or layout-dependent elements remain in original visual form because serialization alone may lose spatial layout, graphical marks, and tabular structure.Source: A. Multimodal Document Parsing · p. 3

B. Visual-Centered Contextual Hyperedge Extraction

  • Figures and tables serve as visual anchors linked to captions, section titles, and related text to form contextual hyperedges.Captions are selected using spatial proximity and layout alignment, section titles from preceding title blocks, and related text through multimodal similarity.Source: B. Visual-Centered Contextual… · p. 4

C. Structural Hyperedge Extraction

HyperDoc represents document structure and context through hyperedges that connect heterogeneous evidence at different granularities. Combining these relations produces a unified hypergraph for retrieving evidence across local and global scopes.

C. Structural Hyperedge Extraction

  • Hyperedges represent group-level relations, directly capturing page containment, section hierarchy, and cross-page continuity that pairwise edges represent indirectly.A single evidence element may participate in multiple structural groups.Source: C. Structural Hyperedge Extraction · p. 4
  • Page-containment hyperedges expose each page as a scope while retaining its visual anchors within the same physical boundary.The page node groups anchors located on that page.Source: C. Structural Hyperedge Extraction · p. 4
  • Section-containment hyperedges connect a section title to the visual anchors within its textual scope, preserving section-level context during selection.A section title node governs the anchors falling within its textual scope.Source: C. Structural Hyperedge Extraction · p. 4
  • The unified document hypergraph combines contextual and structural relations over parsed page and block elements.It organizes scattered evidence into interconnected representations rather than isolated pages or disjointed blocks.Source: C. Structural Hyperedge Extraction · p. 4

IV. ONLINE QUERY-AWARE HYPEREDGE SELECTION

HYPERDOC turns a query into a parsed intent, a candidate hyperedge pool, a selected evidence set, and finally a serialized VLM input. Its workflow comprises intent analysis, budget-aware candidate selection, and evidence integration.

A. Overall Workflow

  • The online selection section maps a query through parsed intent, candidate pool, selected evidence, and final serialized VLM input.The process operates in three progressive stages.Source: A. Overall Workflow · p. 4
  • VLM-based intent analysis predicts the query's intent type and target evidence scope, capturing cues such as entities, page ranges, sections, and figure or table identifiers.These cues guide subsequent candidate proposal.Source: A. Overall Workflow · p. 5
  • Intent-guided tools propose candidates over the document hypergraph; cost-aware selection chooses a compact subset, then reranking and block-level pruning serialize it as visual-textual context.The workflow describes this final context as input for downstream reasoning.Source: A. Overall Workflow · p. 5

B. Query Intent Analysis

Query intent analysis represents operation type, evidence scope, and constraints so retrieval can respond to heterogeneous query requirements. Candidate proposal then routes tools over the document hypergraph and combines retrieved and query-induced evidence groups.

B. Query Intent Analysis

  • Queries vary in operation and evidence scope, from localized anchoring to document-wide aggregation and cross-page reasoning.The text notes that without intent parsing, retrieval may over-select for localized queries or under-select complementary evidence for broader ones.Source: B. Query Intent Analysis · p. 5
  • The parsed intent state includes an intent type, a SINGLE, MULTI, or DOCUMENT-WIDE scope, and hard structural constraints distinct from soft semantic cues.Intent types include localization, counting, enumeration, comparison, and cross-evidence reasoning.Source: B. Query Intent Analysis · p. 5
  • Hard constraints specify structural locators such as pages, sections, or figure and table identifiers; soft constraints provide cues for keyword- or similarity-based matching.Together these form the query constraint set.Source: B. Query Intent Analysis · p. 5

C. Intent-Guided Candidate Proposal

  • The intent state routes candidate-proposal tools, while hard constraints restrict admissible search and soft constraints guide semantic recall expansion.Proposal tools are activated by routing signals, including structural locators, semantic cues, and document-wide COUNT or ENUMERATE intents.Source: B. Query Intent Analysis · p. 5, C. Intent-Guided Candidate Proposal · p. 5
  • Proposal outputs are deduplicated into an over-complete pool containing both pre-built document hyperedges and query-induced groups, including aggregation hyperedges for counting and enumeration.Hard and soft constraint sets also serve as execution inputs to the activated tools.Source: C. Intent-Guided Candidate Proposal · p. 6

D. Cost-Aware Hyperedge Selection

HYPERDOC selects hyperedges to satisfy explicit query constraints and maximize intent-conditioned semantic coverage under a VLM input budget. Its greedy procedure prioritizes structural admissibility, adds cost-effective semantic evidence, and refines the selected context through reranking and pruning.

D. Cost-Aware Hyperedge Selection

  • The cost-aware greedy selector ranks candidates by marginal coverage gain per input cost and stops when further evidence is not cost-effective.The problem is shown NP-hard by reduction from Maximum Coverage.Source: D. Cost-Aware Hyperedge Selection · pp. 6–7
  • Input cost estimates the rendered cost of deduplicated visual-textual evidence units, including page regions, crops, text blocks, and structural metadata.The unit cost reflects textual and visual tokens contributed after preprocessing.Source: D. Cost-Aware Hyperedge Selection · p. 6
  • The selection problem maximizes intent-conditioned semantic coverage while satisfying explicit constraints, with a budget-derived cardinality cap rather than a fixed retrieval target.The text states that the query-aware selection problem is NP-hard.Source: D. Cost-Aware Hyperedge Selection · p. 6
  • The strategy first retains candidates satisfying hard structural constraints, then augments with semantic evidence; its stopping threshold compares remaining candidate density with the first selected soft hyperedge's density.The budget-derived K is a feasibility cap, and the effective set size is determined adaptively.Source: D. Cost-Aware Hyperedge Selection · p. 7
  • Intent-conditioned coverage treats SINGLE queries as favoring direct soft matches and MULTI queries as favoring candidates that add new or stronger support.For MULTI queries, the gain counts improvement beyond the current selected set.Source: D. Cost-Aware Hyperedge Selection · p. 7
  • Constraint-aligned reranking organizes selected hyperedges by matched constraints, evidence scope, anchor entity, or sub-question; block-level pruning retains auxiliary blocks only when their coverage gain justifies their cost.Anchors and caption blocks serve as fixed structural seeds during pruning.Source: D. Cost-Aware Hyperedge Selection · pp. 7–8
  • The final context can retain page- or section-level evidence for document-wide queries or reduce to a few visual-centered contextual hyperedges for localized queries.The text characterizes this context as more coherent than disconnected OCR blocks and more compact than full-page retrieval.Source: D. Cost-Aware Hyperedge Selection · p. 8

V. EXPERIMENTS

The experiments evaluate HyperDoc against state-of-the-art baselines and include analyses of efficiency, ablations, parameter sensitivity, and a case study.

  • The evaluation covers overall QA performance, efficiency, ablations, parameter sensitivity, and a case study.Source: §V · p. 8

1) Datasets:

The evaluation uses three long-document QA benchmarks spanning varied domains and multimodal content. Their digital PDFs average 47.5–85.6 pages, targeting evidence construction beyond direct VLM inference.

  • MMLongBench-Doc, LongDocURL, and DocBench cover administrative files, tutorials, and research reports with charts, tables, and text.Source: 1) Datasets · p. 8
  • Their documents average 47.5–85.6 pages, requiring evidence construction beyond direct VLM inference.Source: 1) Datasets · p. 8
  • All benchmark documents are digital PDFs; scanned PDFs can use the same rendering, parsing, and hypergraph construction pipeline without modification.Source: 1) Datasets · p. 8
  • The main comparison excludes DocVXQA and DocVQA because they focus mainly on short documents or single-page QA.Source: 1) Datasets · p. 8

3) Baselines:

HyperDoc is evaluated against textual and multimodal retrieval baselines on several QA, retrieval, and efficiency measures. It outperforms the baselines across evaluated benchmarks, while intent-aware selection and intent classification are also examined.

3) Baselines:

  • Baselines include OCR- or structure-extracted text retrieval, page retrieval, multi-agent and graph retrieval, and MHier-RAG.Source: 3) Baselines · p. 8

4) Implementation Details:

  • The standardized evaluation uses Qwen-family VLMs on H100 GPUs, PaddleOCR for layout-aware blocks, and ColPali v1.3 for page retrieval.Source: 4) Implementation Details · p. 8

1) Overall Accuracy:

  • HyperDoc consistently outperforms all baselines across backbone settings and evaluated benchmarks.Table IV presents the overall comparison across backbone models.Source: 1) Overall Accuracy · p. 8, Table IV · p. 9
  • Fixed top-K retrieval yields limited gains in most settings when increasing from five to ten pages, and can perform worse with the 32B backbone.The authors attribute the latter partly to tighter input compression under the same serving constraints.Source: 1) Overall Accuracy · pp. 8–9

2) Retrieval Effectiveness:

  • On LDU, HyperDoc improves recall@budget across most query intents, with clear gains for document-scope COUNT and ENUMERATE queries.Figure 4(a) compares gains against ColPali v1.3 under a common budget.Source: 2) Retrieval Effectiveness · p. 9, Figure 4 · p. 9

3) Intent-Type Classification:

  • Intent-type classification reaches 86.5%, 86.0%, and 92.5% accuracy on MMLB-Doc, LDU, and DocBench, respectively, for Qwen3-VL 8B.Forcing COUNT to LOCATE reduces QA accuracy by 7.8 and 3.1 pp on MMLB-Doc and LDU, respectively.Source: 3) Intent-Type Classification · p. 9

4) Overall Efficiency:

HyperDoc balances token use and latency, while its ablations, parameter sweep, and case studies examine how structured evidence selection affects efficiency and evidence coverage.

4) Overall Efficiency:

  • Compared with MDocAgent, HyperDoc uses fewer tokens and responds faster; compared with M3DocRAG, it substantially reduces latency, though fine-grained textual evidence can increase token use.Figure 5 compares token usage and query latency across baselines; HyperDoc occupies a compact region across three benchmarks.Source: 4) Overall Efficiency · pp. 9–10
  • Hypergraph construction takes 4.9–5.6 s/document and the index occupies 22.3–58.6 MB per benchmark; the offline pipeline scales approximately linearly with document and page counts under fixed resources.Source: 4) Overall Efficiency · p. 10, Table V · p. 10

C. Ablation

  • Removing contextual or structural hyperedges lowers accuracy across three datasets, while removing hyperedge selection degrades efficiency and reduces answer quality on MMLB-Doc and LDU.The full model provides a favorable effectiveness-efficiency trade-off across the three benchmarks.Source: C. Ablation · p. 10, Table VI · p. 10

D. Parameter Sensitivity

  • Across the evaluated benchmarks, varying αρ yields a stable accuracy-efficiency trade-off; increasing it generally reduces input cost, while overly aggressive stopping may slightly degrade answer quality.The authors set αρ = 1.0 as the default.Source: D. Parameter Sensitivity · p. 10, Table VII · p. 10

E. Case Study

  • In case studies, HyperDoc binds localized evidence to structural cues, combines complementary evidence under shared comparison constraints, and uses document-scope selection to recover a correct chart count.The document-level case contrasts this with fixed-budget retrieval that covers only part of the relevant charts.Source: E. Case Study · pp. 10–11, Figure 6 · p. 11

VI. RELATED WORK

Prior document RAG work spans text/OCR and multimodal retrieval units, as well as structured indexes, but often does not select evidence over a structured hypergraph under query-specific budgets. HyperDoc uses adaptive cost-aware selection over a document hypergraph and reports improved answer quality with favorable cost-latency trade-offs across representative benchmarks.

A. Document RAG

  • Document RAG evolved from text/OCR to multimodal pages and chunks, but individual units can miss visual context, structural cues, cross-modal bindings, and evidence spanning multiple regions.Text- or OCR-based approaches can lose visual context important for figures, tables, charts, and layout-dependent questions.Source: A. Document RAG · p. 11
  • Structured document systems use hierarchy, query planning, knowledge graphs, or page-level traversal, whereas HYPERDOC selects hypergraph evidence under budgets with cost-aware greedy selection.Table VIII compares evidence construction and selection strategies in existing document RAG methods.Source: A. Document RAG · pp. 11–12, Table VIII · p. 12

B. Structured RAG

  • Ordinary graph indexes encode pairwise edges, while hypergraphs connect multiple nodes in a single higher-order relation for complex retrieval and reasoning.Prior work explores higher-order indexing for open-domain RAG, suggesting its potential for organizing multimodal evidence in long-context document QA.Source: B. Structured RAG · p. 12

VII. CONCLUSION

  • Across representative benchmarks, HYPERDOC improves answer quality over diverse baselines with a favorable cost-latency trade-off.It preserves structural containment and cross-modal relations while selecting evidence adaptively to each query’s demand.Source: §VII · p. 12

Related papers

Loading 2610.35542v2…