💬 NLP

LEDGER: Scaling Agentic Document Editing with Dependency-aware Graph Retrieval

The paper introduces LEDGER, a framework that employs dependency-aware graph retrieval to efficiently guide agentic document editing, significantly improving consistency and reducing token usage across various models by explicitly modeling document structure and dependencies.

Original authors: Mike Hang Wang, Utkarsh Garg, Reza Davari, Huitian Jiao, Hao Cheng, Baolin Peng, Tao Ge, Si-Qing Chen

Published 2026-06-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mike Hang Wang, Utkarsh Garg, Reza Davari, Huitian Jiao, Hao Cheng, Baolin Peng, Tao Ge, Si-Qing Chen

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

Imagine you are the editor-in-chief of a massive, 100-page instruction manual. Suddenly, your boss asks you to change a specific term in Chapter 3.

The Old Way (The "Full-Document" Problem):
In the past, to make that one small change, you had to read the entire 100-page book from start to finish every single time. Why? Because changing "Microsoft" to "MS" in Chapter 3 might accidentally break a reference in Chapter 80, or change the tone of a paragraph in Chapter 50 that you didn't even look at. It's slow, exhausting, and you might miss a tiny detail because you were overwhelmed by the sheer volume of text.

The New Way (LEDGER):
The paper introduces LEDGER, a smart system that acts like a super-organized librarian with a magical, living map of the document.

Here is how LEDGER works, using simple analogies:

1. The "Living Map" (Dependency Graph)

Instead of just seeing a pile of paper, LEDGER first builds a lightweight map of the document.

Nodes: Every paragraph, figure, and section is a "stop" on the map.
Edges (The Roads): LEDGER draws lines connecting these stops based on how they relate.
- Explicit Roads: "Figure 2" points directly to "The Linear Scaling Graph."
- Implicit Roads: "This result" points back to the experiment described three paragraphs ago.
- Semantic Roads: Two paragraphs discussing "climate change" are connected because they talk about the same topic, even if they don't mention each other directly.

This map is built once. It's like having a subway map of the document where you can instantly see which stops are connected, without having to read every station's announcement.

2. The "Smart Search" (Graph-Guided Retrieval)

When you ask the AI to "Update the tone of Section 4," LEDGER doesn't dump the whole 100-page book into the AI's brain.

The Old Way: The AI tries to hold the whole book in its head at once. It gets confused, wastes energy, and might forget the important parts.
The LEDGER Way: The system looks at the map. It sees that Section 4 is connected to Section 2 (because Section 4 references it) and Section 9 (because Section 9 depends on Section 4).
The Result: It only grabs the specific "stops" (paragraphs) on the map that are connected to Section 4. It ignores the rest of the book. This is like telling a taxi driver, "I only need to go to the three stops connected to my current location," rather than driving the whole city.

3. The "Safety Check" (Consistency Verification)

After the AI makes the edit, LEDGER doesn't just walk away. It acts like a quality control inspector.

It checks the map to make sure no "roads" are broken. Did the edit accidentally delete a reference? Did it change a word that makes a later paragraph confusing?
If something looks wrong, it fixes it before you ever see the final document.

Why is this a big deal?

The paper tested this on 1,900 different editing tasks using six different AI models. Here is what they found:

Better Accuracy: LEDGER kept the document consistent 76% of the time, compared to only 56% for the old method. It stopped the AI from making "silly mistakes" where it changed one thing and broke something else far away.
Faster & Cheaper: Because LEDGER only reads the necessary parts (about 10-15% of the document), it uses 85% fewer "tokens" (the currency AI uses to process text). It's like reading a summary of the relevant chapters instead of the whole library.
Smarter, Not Harder: Surprisingly, LEDGER worked so well that even a "dumb" AI (one with low reasoning effort) using the map performed better than a "smart" AI (high reasoning effort) trying to read the whole book. It proved that having a good map is often more important than having a super-brain.

The Bottom Line

LEDGER solves the problem of editing long documents by giving the AI a structured map of how everything connects. Instead of blindly guessing or reading the whole book, the AI knows exactly which pieces of the puzzle to look at, ensuring that when you change one piece, the whole picture stays perfect.

Note: The paper specifically mentions this works for structured documents like reports, manuals, and papers with clear sections. It notes that it might struggle with creative writing or messy, unformatted text where the "map" is hard to draw.

Technical Summary: LEDGER – Scaling Agentic Document Editing with Dependency-aware Graph Retrieval

Problem Statement

Agentic document editing represents a paradigm shift where users issue high-level natural language instructions (e.g., "revise the tone of Section 4" or "update terminology") to an AI agent, which then plans and executes concrete modifications. However, unlike code, natural language documents lack formal semantics, executable structures, or compiler-level guarantees. This creates a fundamental context engineering challenge: maintaining consistency across long, structured documents.

The core difficulty lies in "loose dependencies." A simple edit, such as renaming a term or changing a figure caption, often requires updating multiple surface forms, aligning stylistic choices in adjacent paragraphs, and correcting downstream references that lack explicit citations. Current approaches face a tension:

Full-document processing: Providing the entire document as context ensures consistency but incurs prohibitive token costs and latency, often distracting the model from relevant regions ("lost in the middle" phenomenon).
Retrieval-based editing: Selecting a subset of context improves efficiency but typically relies on topical similarity (embeddings), failing to capture critical structural dependencies like explicit cross-references, implicit pronoun dependencies, or downstream semantic impacts.

Methodology: The LEDGER Framework

LEDGER (Lightweight Explicit Dependency Graph for Efficient Retrieval) addresses this bottleneck by constructing a dependency-aware semantic graph that explicitly models document structure. The framework operates through three integrated components:

1. Semantic Graph Construction

The system converts a document $D$ into a graph $G=(V, E)$ where nodes represent document units (sections, paragraphs, figures, equations) and edges encode four specific dependency types:

CONTAINS ( $E_{CON}$ ): Hierarchical relationships derived directly from the DOM tree structure.
REFERENCES ( $E_{REF}$ ): Explicit citations (e.g., "Figure 2"). Extraction ensures minimality, unambiguity, and validation against existing identifiers.
DEPENDS ( $E_{DEP}$ ): Implicit dependencies where a unit relies on definitions, assumptions, or concepts introduced in another (e.g., "this result"). This is determined via counterfactual testing protocols to verify necessity and directionality.
RELATED ( $E_{REL}$ ): Semantic relationships between topically related content, identified via cosine similarity of embeddings (threshold $\theta=0.7$ ).

2. Dependency-Aware Context Retrieval

For a given edit request, LEDGER performs a graph traversal to retrieve a context $C_{context}$ that is $O(1)$ in size relative to the document length:

Target Identification: Locates the specific nodes to be edited.
Dependency Expansion: Traverses the graph to include upstream dependencies (what the target relies on) and downstream impacts (what depends on the target).
Priority Scoring: Nodes are prioritized based on edge criticality: REFERENCES > DEPENDS > CONTAINS > RELATED.
Budget-Constrained Packing: Nodes are selected greedily until a token budget is met, ensuring all critical dependencies are included while excluding irrelevant content.

3. Consistency Verification

After modifications are applied, the system validates structural invariants:

Reference Integrity: Ensures all outgoing references point to existing targets.
Terminology Consistency: Checks if key terms in modified nodes align with dependent nodes.
Semantic Coherence: Recomputes embeddings to detect significant semantic drift in related content.
The graph is then updated incrementally to reflect the new document state.

Key Contributions

Dependency-Aware Framework: A novel approach applying explicit semantic graphs to document editing, resolving the context engineering bottleneck through typed dependency extraction and graph-guided retrieval.
Curated Benchmark: A dataset of 1,900 test cases spanning six editing scenarios (local refinement, cross-reference updates, structural reorganization, content addition, iterative editing, and scalability tests) across diverse document types and complexity levels.
Reasoning Substitution Evidence: Empirical demonstration that explicit structural guidance can substitute for expensive internal reasoning, establishing a design principle for efficient agentic systems.

Experimental Results

The framework was evaluated on 1,900 test cases using six state-of-the-art models (Claude 4.5 Haiku/Sonnet/Opus, GPT-4.1/5/5.2).

Consistency Improvement: LEDGER improved consistency from a baseline of 56% to 76% across all models and scenarios. The overall pass rate increased from 41% to 78%.
Token Efficiency: LEDGER reduced token usage by approximately 85% compared to full-document regeneration, maintaining a constant average of ~1,500 tokens per edit regardless of document size (5K to 100K tokens).
Reasoning Substitution: Notably, LEDGER with low reasoning effort achieved performance (80% consistency) that matched or exceeded the baseline using high reasoning effort (57% consistency), while using fewer tokens. This suggests that explicit dependency representations can partially replace the need for costly internal deliberation.
Scalability: While baseline token usage scales linearly with document length, LEDGER maintains constant token usage, demonstrating $O(1)$ retrieval complexity relative to document size.
Ablation Studies: Removing dependency tracking reduced consistency by 14 percentage points, confirming that explicit structural edges are the primary driver of performance gains.

Significance and Claims

The paper claims that LEDGER establishes a new design principle for agentic systems operating on structured data: explicit dependency representations can substitute for expensive internal reasoning.

By shifting the burden of consistency from the model's internal reasoning capacity to an external, structured graph memory, LEDGER achieves:

Scalability: Enabling efficient editing of very long documents without linear token cost growth.
Robustness: Maintaining high consistency even with smaller models or lower reasoning settings.
Generalizability: The edge structure (references, dependencies, containment) maps naturally to other structured artifacts, suggesting potential extensions to code refactoring and software maintenance.

The authors position LEDGER not as a replacement for human editors but as an assistive tool that augments human oversight by handling the mechanical consistency checks that are currently a bottleneck in agentic document editing.