💬 NLP

Trace Only What You Need: Structure-Aware On-Demand Hypergraph Memory for Long-Document Question Answering

The paper introduces DocTrace, a multi-agent retrieval-augmented generation framework that enhances long-document question answering by combining document-structure-aware indexing, on-demand hypergraph memory for reasoning, and reusable experience graphs to achieve superior accuracy and efficiency compared to existing baselines.

Original authors: Xiangjun Zai, Xingyu Tan, Chen Chen, Xiaoyang Wang, Wenjie Zhang

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiangjun Zai, Xingyu Tan, Chen Chen, Xiaoyang Wang, Wenjie Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: Finding a Needle in a Haystack (That's Also a Maze)

Imagine you have a massive library containing thousands of books (long documents). A librarian (an AI) needs to answer a specific question, like "Who adopted the main character in Chapter 12, and what happened to them in Chapter 45?"

The Old Way (Traditional AI):
The librarian tries to read the entire library at once to find the answer. This is slow, expensive, and the librarian gets confused because there's too much information.

The "Retrieval" Way (Standard RAG):
The librarian uses a search engine to find a few pages that look relevant. But here's the catch: standard search engines treat the library like a pile of loose papers. They might find the right sentence, but they miss the context. They don't know that the sentence in Chapter 12 is connected to the sentence in Chapter 45, or that the order of events matters. It's like finding two puzzle pieces but not realizing they belong to the same picture.

The "Structured" Way (Previous Attempts):
Some researchers tried to organize the library by building a giant map or a summary tree before anyone asked a question.

The Flaw: This is like hiring a team to map out the entire library, room by room, even if no one ever asks about the "History Section." It takes forever, costs a lot of money, and much of the map is useless for the specific question being asked.

The Solution: DocTrace (The Smart Detective Agency)

The authors propose DocTrace, a new system that acts like a team of smart detectives. Instead of mapping the whole library beforehand, they only organize what they need, exactly when they need it.

Here is how the three main "superpowers" of DocTrace work:

1. The "On-Demand" Memory (The Hypergraph)

The Analogy: Imagine a detective working on a case. Instead of carrying a giant filing cabinet of every fact in the world, they pull out a whiteboard. As they investigate, they write down connections on the board. If they find a clue about "Who adopted the child," they draw a line to "Chapter 12." If they later find a clue about "Chapter 45," they draw a line connecting it to the first clue.
What DocTrace does: It builds a Hypergraph (a complex web of connections) only for the specific question being asked. It doesn't waste time organizing the whole document. It creates a "Working Memory" that links facts together dynamically, allowing the AI to see how different parts of the story connect, even if they are far apart.

2. The "Structure-Aware" Map (The Document Tree)

The Analogy: A normal search engine treats a book like a flat list of words. DocTrace treats the book like a family tree or a table of contents. It knows that "Chapter 3" is inside "Part 2," and that "Paragraph 5" comes right after "Paragraph 4."
What DocTrace does: It builds a lightweight Tree Index that respects the original structure of the document. When the AI looks for an answer, it doesn't just look for matching words; it looks at the location. If the answer requires understanding the flow of a story, the AI knows to look at the "neighborhood" of the text (the surrounding paragraphs) rather than just isolated sentences.

3. The "Experience" Notebook (The Graph Memory)

The Analogy: Imagine a detective who has solved 100 similar cases. When a new case comes in that looks like the 50th case they solved, they don't start from scratch. They open their notebook, see how they solved the previous one, and say, "Oh, I know this pattern! I'll start by checking the adoption records, then check the school records."
What DocTrace does: It stores successful "reasoning plans" (how it broke a question down into smaller steps) in a Graph-structured Experience Memory. If a new question is structurally similar to an old one, DocTrace reuses the old plan. This saves time and makes the AI smarter over time without needing to re-learn everything.

The Team: Orchestrator and Investigators

DocTrace uses a two-person team approach:

The Orchestrator (The Manager): This agent looks at the big picture. It breaks the big, scary question into smaller, manageable sub-questions. It decides which "detectives" to send where and checks if the plan is making sense.
The Investigators (The Field Agents): These agents go out and fetch the specific evidence for each small sub-question. They use the "On-Demand Memory" and the "Tree Map" to find the exact facts needed.

The Results: Faster and Smarter

The paper tested DocTrace on four different datasets involving long stories and reports.

Performance: It beat the current best systems (like ComoRAG) by a significant margin (up to 8.85% better accuracy in some tests).
Efficiency: Because it doesn't waste time building a giant map of the whole document first, it is 53% cheaper (in terms of computer processing power) to run.

Summary

DocTrace is like a detective agency that doesn't waste money mapping the whole city before a crime happens. Instead, it has a smart manager who breaks the case down, field agents who build a temporary map of just the relevant streets as they investigate, and a notebook of past cases to help them solve similar mysteries faster. It uses the structure of the document (like chapters and paragraphs) to make sure the story makes sense, not just the words.

Technical Summary: DocTrace – Structure-Aware On-Demand Hypergraph Memory for Long-Document QA

1. Problem Statement

Long-document Question Answering (QA) requires Large Language Models (LLMs) to reason over evidence scattered across lengthy texts, where answers often depend on event order, section-level context, and cross-part connections. While Retrieval-Augmented Generation (RAG) mitigates context limits by retrieving relevant evidence, existing approaches face three critical limitations:

Costly Query-Agnostic Organization: Current structured RAG methods (e.g., hierarchical summaries or knowledge graphs) often pre-index the entire document before a query is known. This incurs substantial upfront latency and token overhead, generating knowledge that may have limited utility for specific queries.
Insufficient Use of Document Structure: Many methods flatten documents into chunks, losing structural cues like section boundaries, paragraph order, and local neighborhood relations. This weakens the preservation of narrative flow and event progression essential for accurate reasoning.
No Reuse of Historical Reasoning: Existing systems typically treat each question as an isolated instance. Once a question is answered, the resulting reasoning trajectories are discarded, forcing the system to repeat similar exploration patterns for structurally similar future questions.

2. Methodology: The DocTrace Framework

DocTrace is a multi-agent RAG framework designed to address these limitations through query-triggered knowledge organization, document-structure-aware retrieval, and experience-guided reasoning. It employs an Orchestrator-Investigator architecture operating over three core components:

A. Orchestrator-Investigator Architecture

Orchestrator ( $\omega$ ): Manages the global reasoning process. It decomposes complex questions into interdependent subquestions, represented as Directed Acyclic Graphs (DAGs). It coordinates the planning, dispatches tasks to investigators, and synthesizes final answers.
Investigator Agents ( $\alpha_i$ ): Execute specific subquestions. They retrieve evidence, interact with the working memory, and generate intermediate answers.

B. Core Components

1. Document Structural Tree Index ( $T$ )

Instead of a flat list of chunks, DocTrace represents the document as a hierarchical tree ( $T$ ) with nodes at four levels: document, chapter, section, and paragraph.

Construction: Uses an LLM to infer heading patterns and parse the document, supplemented by Named Entity Recognition (NER).
Retrieval (TreePPR): When a subquestion arises, the system uses Personalized PageRank (TreePPR) over the tree. This propagates relevance scores from seed nodes while respecting the document's structural boundaries and sibling relationships, ensuring retrieved evidence maintains narrative flow and structural context.

2. Hypergraph-Structured Working Memory ( $M$ )

This is a query-triggered, agent-shared memory constructed on-demand during reasoning. It consists of two complementary views:

Abstraction View ( $M_A$ ): Organizes multi-level hierarchical summaries over selected tree nodes. It supports answering subquestions where evidence is too broad for direct reading, allowing agents to drill down from summaries to original text.
Relation View ( $M_R$ ): Stores $n$ -ary relations and entities extracted only from the relevant tree nodes selected for the current subquestion. This supports multi-hop relational reasoning without constructing a global knowledge graph.
Mechanism: $M$ is built incrementally based on the specific evidence needs of each subquestion, avoiding the cost of pre-indexing the entire document.

3. Graph-Structured Experience Memory ( $D_M$ )

To enable learning from past interactions, successful reasoning plans (DAGs) are stored in a heterogeneous graph memory.

Schema: Nodes include question skeletons, reasoning DAGs, signatures (topic entities, constraints), and reasoning motifs.
Retrieval & Reuse: When a new question arrives, the orchestrator retrieves structurally similar reasoning DAGs from $D_M$ . These retrieved plans serve as few-shot examples to initialize new reasoning paths, allowing the system to reuse successful decomposition patterns rather than starting from scratch.

3. Key Contributions

Query-Triggered Knowledge Organization: DocTrace eliminates the need for expensive pre-indexing by constructing a Hypergraph-structured Working Memory ( $M$ ) incrementally, driven by the specific evidence needs of each subquestion.
Document-Structure-Aware Retrieval: By utilizing a Document Structural Tree Index ( $T$ ) and TreePPR, the framework leverages structural cues (hierarchy, order) alongside semantic similarity to retrieve evidence that preserves the document's narrative flow.
Reusable Reasoning Experience: The system explicitly models and stores successful reasoning trajectories as DAGs in a Graph-structured Experience Memory ( $D_M$ ), enabling the reuse of reasoning patterns for structurally similar future questions.
Efficiency and Effectiveness: The framework achieves state-of-the-art performance while significantly reducing computational costs compared to hybrid structured baselines.

4. Experimental Results

Experiments were conducted on four long-document QA datasets: NarrativeQA, EN.QA, EN.MC, and DetectiveQA.

Performance: DocTrace achieved the best performance on three of the four datasets.
- On NarrativeQA, it surpassed the strongest baseline (ComoRAG) by 8.85% in F1 and 4.40% in Exact Match (EM).
- On EN.MC, it ranked second, outperforming ComoRAG by 1.82% in Accuracy (ACC) in the variant without online learning.
Efficiency: DocTrace reduced the overall computational cost by 53.32% compared to ComoRAG. This efficiency gain is attributed to avoiding full-document pre-indexing and the on-demand construction of memory.
Ablation Studies: Removing the orchestrator's planning capability or the working memory ( $M$ ) resulted in significant performance drops (e.g., a 5.11% drop in F1 on EN.QA without planning), confirming the necessity of structured decomposition and on-demand memory.
Backbone Robustness: DocTrace consistently outperformed direct In-Context Learning (IO) prompting across various LLM backbones (GPT-4o-mini, Qwen3, DeepSeek), with average gains of 23.59% in F1 and 35.37% in ACC.

5. Significance and Claims

The paper claims that DocTrace represents a shift from static, pre-computed knowledge structures to dynamic, on-demand reasoning systems. Its significance lies in demonstrating that:

High-quality long-document QA does not require expensive, query-agnostic pre-indexing of the entire document.
Preserving the original document hierarchy is critical for reasoning tasks involving event order and narrative flow.
Reusing historical reasoning trajectories can effectively guide the exploration of complex, multi-step questions, improving both accuracy and efficiency.

The authors note that the system is currently focused on text-based documents and relies on LLM calls for planning and generation. Future work is suggested to explore multimodal reasoning and more lightweight agent designs to further improve efficiency.