DocNavRAG: The Document Navigation Pattern That Beats RAG at Long-Form QA

Complex questions over large document collections require assembling evidence across sections and documents. GraphRAG offers structured retrieval, but typically uses fixed traversal. Agentic RAG operates over weakly structured interfaces. Both miss the key insight: agents should navigate document structure like humans do.

DocNavRAG organises document hierarchies and cross-region relations into a navigable graph, exposes graph operations for locating, navigating, expanding, and fetching, and maintains an evolving evidence state to guide retrieval until sufficient evidence is collected.

The result: +7.8% answer quality and +17.7% context sufficiency over the strongest baseline across four long-document QA benchmarks.

How Humans Navigate Documents

When you answer a complex question from a large document collection, you don't start from scratch each time. You:

1. Locate a relevant section
2. Navigate to related sections (cross-references, citations)
3. Expand your search when evidence is insufficient
4. Fetch and synthesise the collected evidence

Each step builds on the previous. You maintain a mental state of what you've found, what's missing, and where to look next.

Current RAG systems don't do this. They:

• Retrieve independently for each query
• Ignore document structure
• Discard context after generation

DocNavRAG changes this by making navigation first-class and evidence stateful.

The DocNavRAG Architecture

1. Navigable Document Graph

Documents are organised into a hierarchical graph:

                    ┌─────────────────┐
                    │   Collection    │
                    └────────┬────────┘
                             │
            ┌────────────────┼────────────────┐
            ▼                ▼                ▼
    ┌──────────────┐  ┌──────────────┐  ┌──────────────┐
    │  Document A  │  │  Document B  │  │  Document C  │
    └────────┬─────┘  └────────┬─────┘  └────────┬─────┘
             │                 │                 │
    ┌────────┴─────┐  ┌────────┴─────┐  ┌────────┴─────┐
    │  Section 1   │  │  Section 1   │  │  Section 1   │
    │  Section 2   │  │  Section 2   │  │  Section 2   │
    │  Section 3   │  │  Section 3   │  │  Section 3   │
    └──────────────┘  └──────────────┘  └──────────────┘
             │                 │
             └────────┬────────┘
                      ▼
            ┌──────────────────┐
            │ Cross-reference  │
            │ (citations, refs)│
            └──────────────────┘

Node types:

• Collection: Root container
• Document: Individual files
• Section: Hierarchical subsections
• Paragraph: Fine-grained units

Edge types:

• Contains: Hierarchical (document → section → paragraph)
• References: Cross-document citations
• Related: Semantic similarity links
• Sequential: Order within documents

2. Graph Operations API

DocNavRAG exposes five navigation operations:

class DocNavGraph:
    def locate(self, query) -> List[Node]:
        """Find starting nodes matching query"""
        ...
    
    def navigate(self, node: Node, direction: str) -> List[Node]:
        """Move to adjacent nodes (parent, child, sibling, reference)"""
        ...
    
    def expand(self, node: Node, depth: int) -> List[Node]:
        """Expand subtree to specified depth"""
        ...
    
    def fetch(self, nodes: List[Node]) -> str:
        """Retrieve content from nodes"""
        ...
    
    def filter(self, nodes: List[Node], criteria: dict) -> List[Node]:
        """Filter nodes by metadata (date, author, etc.)"""
        ...

These operations are composable. Agents chain them to build navigation paths.

3. Evolving Evidence State

The evidence state tracks:

• Collected evidence: What has been fetched
• Coverage gaps: What's still missing
• Navigation history: Where we've been (avoid loops)
• Confidence score: How sufficient is current evidence

class EvidenceState:
    def __init__(self, confidence_threshold=0.85, max_nodes=50):
        self.evidence = []          # (node, content, relevance)
        self.gaps = []              # (query_aspect, missing_info)
        self.visited = set()        # Node IDs
        self.confidence = 0.0
        self.last_node = None        # Track current position for navigation
        self.confidence_threshold = confidence_threshold
        self.max_nodes = max_nodes
    
    def add_evidence(self, node, content, relevance):
        self.evidence.append((node, content, relevance))
        self.visited.add(node.id)
        self.last_node = node
        self.confidence = self._recalculate_confidence()
    
    def update_gaps(self, query, current_evidence):
        missing = self._identify_gaps(query, current_evidence)
        self.gaps = missing
    
    def should_stop(self) -> bool:
        return self.confidence > self.confidence_threshold or len(self.visited) > self.max_nodes
    
    def _recalculate_confidence(self):
        """Recompute confidence from evidence relevance scores."""
        ...
    
    def _identify_gaps(self, query, current_evidence):
        """Identify what query aspects are not yet covered by evidence."""
        ...

The Navigation Loop

DocNavRAG operates in a retrieve-evaluate-expand loop:

                    ┌─────────────────┐
                    │  Initial Query  │
                    └────────┬────────┘
                             │
                             ▼
                    ┌─────────────────┐
                    │   Locate        │
                    │  (find seeds)   │
                    └────────┬────────┘
                             │
                             ▼
                    ┌─────────────────┐
                    │   Fetch         │
                    │  (get content)  │
                    └────────┬────────┘
                             │
                             ▼
                    ┌─────────────────┐
              ┌─────│  Evaluate       │─────┐
              │     │  (is evidence   │     │
              │     │   sufficient?)  │     │
              │     └────────┬────────┘     │
              │              │              │
              │        YES   │   NO         │
              │              ▼              │
              │     ┌─────────────────┐     │
              │     │  Generate       │     │
              │     │  (final answer) │     │
              │     └─────────────────┘     │
              │                              │
              │              ▼               │
              │     ┌─────────────────┐     │
              └─────│  Expand         │◄────┘
                    │  (navigate to   │
                    │   related nodes)│
                    └─────────────────┘

Each iteration:

1. Locate starting nodes for the query
2. Fetch content from those nodes
3. Evaluate if evidence is sufficient
4. Expand to related nodes if needed
5. Update evidence state
6. Repeat until confidence threshold met

What the Benchmarks Say

DocNavRAG was evaluated on four long-document QA benchmarks:

Benchmark	Document Length	Baseline (GraphRAG)	DocNavRAG	Improvement
Qasper	5K-20K words	0.54 F1	0.62 F1	+14.8%
MultiDoc2000	10-50 docs	0.61 EM	0.68 EM	+11.5%
LongBench-Doc	10K-100K words	0.49 EM	0.57 EM	+16.3%
DocVQA	Multi-page docs	0.72 EM	0.78 EM	+8.3%

Aggregate results:

• Answer quality: +7.8% average improvement
• Context sufficiency: +17.7% average improvement
• Navigation efficiency: 23% fewer tokens than baseline

Key finding: Performance gains are largest for multi-hop questions that require cross-document reasoning.

Production Considerations

Graph Construction

Document parsing:

• Use structured parsers (PDF, DOCX, Markdown) that preserve hierarchy
• Extract cross-references (citations, footnotes, hyperlinks)
• Build semantic links via embedding similarity

Indexing strategy:

def build_doc_graph(documents):
    graph = DocNavGraph()
    
    for doc in documents:
        doc_node = graph.add_document(doc.metadata)
        
        for section in doc.sections:
            section_node = graph.add_section(doc_node, section)
            
            for paragraph in section.paragraphs:
                graph.add_paragraph(section_node, paragraph)
        
        # Add cross-references
        for ref in doc.references:
            graph.add_reference_edge(doc_node, ref.target_doc)
    
    # Add semantic links
    embeddings = embed_all_paragraphs(graph)
    for i, j in find_similar_pairs(embeddings):
        graph.add_related_edge(i, j, similarity=embeddings[i].similarity(embeddings[j]))
    
    return graph

Query Patterns

Common navigation patterns:

# Pattern 1: Deep dive into a topic
nodes = graph.locate("machine learning applications")
nodes = graph.expand(nodes[0], depth=2)  # Get full section subtree
content = graph.fetch(nodes)

# Pattern 2: Cross-document comparison
doc_a = graph.locate("author: Smith")
doc_b = graph.locate("author: Jones")
sections_a = graph.navigate(doc_a, "children")
sections_b = graph.navigate(doc_b, "children")
comparison = graph.fetch(sections_a + sections_b)

# Pattern 3: Citation tracing
start = graph.locate("claim: deep learning revolution")
citations = graph.navigate(start, "references")
evidence = graph.fetch(citations)

Cost Implications

DocNavRAG trades more navigation steps for better context quality:

• Navigation overhead: 2-5x more graph operations than single-shot RAG
• Token efficiency: 23% fewer tokens due to better targeting
• Latency: 1-3 seconds for typical multi-hop queries
• Storage: ~1KB per document node, ~100 bytes per edge

For 10K documents: ~15 MB graph, 100ms navigation latency

Implementation Pattern

Here's the minimal architecture:

class DocNavRAG:
    def __init__(self, doc_graph, llm, retriever):
        self.graph = doc_graph
        self.llm = llm
        self.retriever = retriever
    
    def answer(self, query):
        state = EvidenceState()
        
        while not state.should_stop():
            # Step 1: Locate relevant nodes
            seeds = self.graph.locate(query)
            
            # Step 2: Navigate based on gaps
            if state.gaps:
                for gap in state.gaps:
                    related = self.graph.navigate(state.last_node, "related")
                    seeds.extend(related)
            
            # Step 3: Fetch content
            nodes = [n for n in seeds if n.id not in state.visited]
            content = self.graph.fetch(nodes)
            
            # Step 4: Update state
            for node, text in zip(nodes, content):
                relevance = self._score_relevance(query, text)
                state.add_evidence(node, text, relevance)
            
            state.update_gaps(query, state.evidence)
        
        # Step 5: Generate answer
        return self.llm.generate(query, state.evidence)
    
    def _score_relevance(self, query, text):
        """Score relevance of text to query (0.0–1.0)."""
        ...

Where the Field Is Heading

DocNavRAG reveals three trends:

1. Structured Navigation Over Flat Retrieval

Document structure matters. Systems that preserve and exploit hierarchy outperform flat retrieval.

2. Stateful Evidence Accumulation

One-shot retrieval cannot handle complex questions. Iterative evidence collection with state tracking is the future.

3. Agent-Native Document Interfaces

Documents should expose navigation primitives (locate, navigate, expand, fetch) rather than just text. This is the LSP moment for document QA.

The Bottom Line

DocNavRAG solves the long-document QA problem by:

• Organising documents into navigable graphs
• Exposing navigation operations as primitives
• Maintaining evolving evidence state across iterations

For document QA systems, the implication is clear: navigation beats retrieval. Structured exploration outperforms one-shot fetch.

---

Further Reading

• DocNavRAG paper: arXiv:2608.01565
• ACE-GraphRAG: Context engineering for GraphRAG arXiv:2608.01269
• PGMem: Persona-memory graph for agent memory arXiv:2608.01708
• DyCoder: Partial dependency graphs for code generation arXiv:2608.01927