Beyond Retrieval: Structuring Evolving and Inconsistent External Knowledge with Proposition Relations for RAG¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/norikinishida/kapipe
Area: Information Retrieval & RAG
Keywords: Retrieval-Augmented Generation, Temporal QA, Proposition Graph, Knowledge Evolution, Contradiction Resolution
TL;DR¶
To tackle evolving external knowledge bases contaminated with outdated statements and factual conflicts, ProStruct-RAG shifts the burden of knowledge integration from inference-time reasoning to pre-retrieval structuring: it extracts timestamped propositions, mines directed updates, contradicts, and supports relations to build a global proposition graph, and retrieves relation-aware subgraphs via one-hop neighborhood expansion, substantially outperforming baselines that do not model inter-proposition relations.
Background & Motivation¶
Large language models relying strictly on parametric memory inevitably struggle with temporal knowledge obsolescence and hallucinations. While continual fine-tuning and localized parameter editing have been actively explored to update internal parameters, repeatedly modifying network weights induces catastrophic forgetting and jeopardizes long-term factual consistency across the model. Consequently, Retrieval-Augmented Generation (RAG)โwhich dynamically grounds answers in external document collections at inference timeโhas become the standard paradigm. However, real-world external knowledge bases are seldom static and coherent. As documents accumulate organically over time, they gather temporally superseded facts, mutually conflicting claims, and misleading rumors.
Faced with such incoherent contexts, recent approaches in long-context modeling and reasoning-centric LLM agents attempt to delegate all evidence reconciliation and contradiction resolution entirely to inference-time reasoning. Yet empirical studies demonstrate that expanding context windows frequently degrades reasoning performance: LLMs are prone to getting lost, distracted, or misled when confronted with a mixture of temporal updates, contradictions, and noise. Existing pre-retrieval structuring strategies either merely arrange facts along a timeline, assign independent factuality scores to individual propositions, or construct knowledge graphs at the entity level. However, state transitions (updates), mutual incompatibilities (contradicts), and evidential justifications (supports) inherently occur between specific factual propositions rather than abstract entities. Isolated propositions and standalone timestamps cannot explicitly tell the model whether a newer report supersedes an older claim, rejects a competing assertion, or provides corroborating evidence.
The core motivation of this paper is to rebalance the computational division of labor: rather than burdening the LLM with resolving intricate temporal and logical conflicts during generation, external knowledge should be structured relationally before retrieval. Core idea: decompose evolving documents into self-contained, timestamped propositions and construct a persistent proposition graph connected by directed updates, contradicts, and supports relations; at inference time, retrieve query-relevant anchor propositions along with their one-hop relational neighborhoods to supply structured, linearized evidence for robust temporal generation.
Method¶
Overall Architecture¶
ProStruct-RAG structures dynamic external knowledge into a persistent graph before retrieval, enabling the QA model to interpret evidence within its proper temporal and relational context. The pipeline consists of four main stages: โ Proposition Extraction, which parses raw documents into decontextualized, atomic factual statements labeled with source publication timestamps; โก Inter-Proposition Relation Extraction, which retrieves semantically related candidate pairs and applies a two-stage LLM classification pipeline (batch initial screening and stronger-model refinement) to discover directed updates, contradicts, and supports edges; โข Subgraph Retrieval, which performs dense retrieval to identify top-k anchor propositions matching the query and expands them via one-hop incoming and outgoing edges into a query-specific subgraph; and โฃ Answer Generation, which deterministically linearizes the induced subgraph into a chronological, direction-aware textual context and prompts the QA model to generate a grounded rationale followed by the final answer. The first two stages run offline during indexing, whereas retrieval and generation run online during inference.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input Document Collection<br/>with publication dates YYYY-MM-DD"] --> B["1. Proposition Extraction<br/>LLM extracts decontextualized facts with timestamps"]
B --> C["2. Inter-Proposition Relation Extraction<br/>Dense candidate retrieval + 2-stage updates/contradicts/supports"]
C --> D[("Persistent Proposition Graph G=(V,E)<br/>nodes: propositions, edges: directed relations")]
E["User Temporal Question q + Target Date"] --> F["3. Subgraph Retrieval<br/>Contriever retrieves top-k anchors + 1-hop in/out neighborhood expansion"]
D --> F
F --> G["4. Structured Context Construction & Answer Generation<br/>Chronological relation linearization + rationale-guided QA generation"]
G --> H["Output Final Answer a"]
Key Designs¶
1. Proposition Extraction: Decontextualized atomic factual units
Standard RAG systems typically operate over fixed-length text chunks, which frequently contain pronoun ambiguities, discourse connectives, and unrelated peripheral facts that introduce severe noise into temporal comparison. ProStruct-RAG adopts propositions as the minimal, atomic knowledge unit. Using few-shot guided LLM prompting (with GPT-4o-mini), complex sentences within each document are broken down into concise, standalone factual statements. Context-dependent elements such as pronouns ("he", "she", "the company") are explicitly resolved to their full entity names so that each statement can be evaluated independently without access to surrounding text. Each proposition inherits the publication date of its source document in YYYY-MM-DD format. While the reporting date may differ slightly from the real-world occurrence date, publication timestamps can be obtained reliably from raw documents without temporal invariant ambiguities, serving as a dependable anchor.
2. Inter-Proposition Relation Extraction: Two-stage candidate filtering and relation refinement
Evaluating all possible proposition pairs across a corpus would incur an intractable quadratic computational cost (\(O(|V|^2)\)). To make relation extraction scalable, the authors design a "dense candidate retrieval + batch classification + refinement" pipeline. For each proposition treated as the Subject, a dense retriever (supervised Contriever) retrieves the top-20 most semantically similar propositions from the same or earlier timestamps as candidate Objects. Constraining edges to point from newer (or contemporary) statements to older (or contemporary) ones naturally models temporal causality and knowledge revision. Candidate pairs sharing the same Subject are batched into a single prompt for GPT-4o-mini to predict one of four directed relation labels:
- updates: the Subject provides a revised or newer state for the exact same attribute/entity, partially or fully superseding the Object;
- contradicts: the Subject and Object make incompatible claims about the same state or timeframe, such that both cannot simultaneously be true;
- supports: the Subject provides concrete evidence, a causal rationale, or a premise that confirms the Object's claim;
- NOREL: no direct logical relation exists, or the pair represents mere paraphrasing/redundancy.
To eliminate false positives from initial extraction, candidate pairs labeled with a relation undergo a second-stage verification step using a stronger model (GPT-4o). The refinement model discards spurious edges and rectifies noisy classifications. Empirical statistics show that only 11%โ19% of candidate pairs pass initial screening, and 10%โ14% survive refinement, substantially reducing graph density while ensuring edge precision.
3. Subgraph Retrieval: One-hop in/out neighborhood expansion
Standard similarity-based retrieval exhibits a fundamental limitation in temporal settings: a user question often has high lexical and semantic overlap with an outdated historical statement, while the subsequent revision or debunking statement may use different vocabulary and fall outside the top-k retrieved list. ProStruct-RAG resolves this blind spot through graph-driven expansion. First, Contriever retrieves the top-\(k\) proposition nodes most relevant to question \(q\), designated as anchor nodes \(A_q\). Next, the system traverses all incoming and outgoing edges connected to each anchor in \(G\), pulling in propositions that the anchor updates, contradicts, or supports, as well as newer propositions that update, contradict, or support the anchor. Merging anchors and their one-hop neighbors yields the query node set \(V_q\) and the corresponding induced edge set \(E_q\), establishing a compact, relation-rich subgraph \(G_q=(V_q, E_q)\).
4. Structured Context Construction & Answer Generation: Chronological and direction-aware linearization
Because downstream QA models cannot natively consume graph topology, \(G_q\) is converted into an interpretable, structured textual context \(C_q\). At the macro level, all retrieved propositions are arranged chronologically by timestamp and assigned sequential proposition identifiers (e.g., [P122]), explicitly visualizing how knowledge evolved over time. At the micro level, each entry displays its identifier, publication date, textual statement, and its directional relations to other retrieved propositions (e.g., "This statement updates the following earlier propositions: P104", "This statement is updated by the following later propositions: P151", "This statement is supported by the following later propositions: P513"). The QA prompt directs the model to interpret incoming cues, reason across updates and contradictions relative to the question's target date, write a reasoning rationale, and then select the final answer option.
Key Experimental Results¶
Main Results¶
The framework was evaluated on three open-book temporal QA benchmarks: CLARK-News (real web news where answers change at least three times), StreamingQA (news spanning a 14-year period), and Asteria (a newly created 180-instance fictional benchmark crafted to eliminate pretraining contamination). Evaluation follows a multiple-choice formulation using Accuracy (%), tested across GPT-4o, o3, and Llama-3.1-70B-Instruct.
| Dataset | Retrieval Size k | No Context | Chunk RAG | Prop RAG | Prop RAG + Time | ProStruct-RAG (Ours) | + Neighborhoods (Full Ours) |
|---|---|---|---|---|---|---|---|
| CLARK-News (GPT-4o) | k=10 | 34.7 | 54.9 | 44.6 | 58.5 | 54.9 | 70.5 |
| CLARK-News (GPT-4o) | k=100 | 34.7 | 53.9 | 54.4 | 84.5 | 85.0 | 85.0 |
| CLARK-News (GPT-4o) | k=1000 | 34.7 | 49.2 | 47.7 | 76.2 | 82.4 | * (exceeded) |
| StreamingQA (GPT-4o) | k=10 | 74.0 | 79.5 | 84.0 | 84.0 | 84.5 | 85.0 |
| StreamingQA (GPT-4o) | k=100 | 74.0 | 89.0 | 86.5 | 89.0 | 89.5 | 90.0 |
| StreamingQA (GPT-4o) | k=1000 | 74.0 | 86.0 | 87.5 | 88.0 | 88.5 | * (exceeded) |
| Asteria (GPT-4o) | k=10 | 36.7 | - | 37.8 | 74.4 | 82.8 | 87.2 |
| Asteria (GPT-4o) | k=100 | 36.7 | - | 36.1 | 65.6 | 88.3 | 89.4 |
| Asteria (GPT-4o) | k=400 (all) | 36.7 | - | 41.1 | 58.9 | 86.1 | 86.1 |
| Overall Average (GPT-4o Avg.) | - | 48.5 | 68.8 | 57.7 | 75.5 | 82.4 | 84.7 |
| Overall Average (o3 Avg.) | - | 62.7 | 83.3 | 64.1 | 82.9 | 85.0 | 86.2 |
| Overall Average (Llama-3.1-70B Avg.) | - | 44.9 | 51.3 | 52.7 | 70.2 | 76.1 | 79.1 |
Ablation Study¶
Ablations were conducted on the contamination-free Asteria benchmark with full retrieval (\(k=400\)) using GPT-4o, isolating the impact of relation refinement, semantic labels, and each individual relation category.
| Config | Accuracy (%) | Gain / Drop | Note |
|---|---|---|---|
| ProStruct-RAG (Full) | 86.1 | - | complete proposed model |
| w/o Refinement (Section 3.2) | 83.8 | -2.3% | unrefined relations introduce edge noise into the context |
| w/o Relation Labels | 82.2 | -3.9% | topology alone without semantic labels fails to disambiguate |
| w/o updates Relations | 81.7 | -4.4% | missing state transition cues impairs tracking of revisions |
| w/o contradicts Relations | 83.3 | -2.8% | inability to flag mutually exclusive claims harms falsehood filtering |
| w/o supports Relations | 80.6 | -5.5% | largest drop; removing evidence grounding impairs verification |
Key Findings¶
- Proposition decomposition alone is insufficient; timestamps and relation links are critical: Comparing Chunk RAG against Prop RAG reveals that atomizing text without temporal anchors degrades accuracy (on CLARK-News \(k=10\), dropping from 54.9% to 44.6%). Introducing timestamps (Prop RAG + Time) yields major gains (84.5% at \(k=100\)). Crucially, adding explicit inter-proposition relations pushes average accuracy further from 75.5% to 82.4% (and 84.7% with neighborhood expansion), demonstrating that temporal coordinates alone cannot clarify whether an event superseded, contradicted, or corroborated previous knowledge.
- Relational neighborhood expansion overcomes semantic retrieval bottlenecks: Under constrained retrieval budgets (\(k=10\)), neighborhood expansion (+ Neighborhoods) delivers massive improvements, boosting CLARK-News from 54.9% to 70.5% (+15.6%) and Asteria from 82.8% to 87.2%. This validates that semantically similar anchors frequently miss complementary correction or update evidence that graph neighbors reliably surface.
- Robustness against long-context degradation: While baseline methods experience catastrophic performance decay as context length increases (e.g., Llama-3.1-70B on CLARK-News plunges from 77.7% at \(k=100\) to 49.2% at \(k=1000\) under Prop RAG + Time), ProStruct-RAG maintains a steady 75.1% accuracy. Pre-structuring knowledge buffers the model against distraction in long, noisy contexts.
- Diagnostic tracking of fake claims: In Asteria, 57.6% of intentionally injected fake propositions are successfully connected via incoming updates or contradicts edges. Furthermore, fake propositions are predominantly targeted by contradicts relations, whereas regular facts are connected by updates relations, confirming that the extracted graph naturally isolates misinformation.
Highlights & Insights¶
- Pre-retrieval relational organization shifts the cognitive burden: Instead of expecting the LLM to dynamically reconcile conflicting facts across dozens of retrieved passages during decoding, ProStruct-RAG precomputes temporal state changes and contradictions offline, providing clean relational cues that lower reasoning latency and hallucination risks.
- Fact-level vs. entity-level knowledge structures: While traditional knowledge graphs connect entities via static relation triples, real-world knowledge updates and refutations operate between entire factual assertions; modeling relations at the proposition granularity precisely captures the mechanics of temporal knowledge revision.
- Lightweight one-hop expansion bridges causal chains: Combining off-the-shelf dense retrieval with one-hop graph traversal provides an elegant solution to the classic failure mode where revised facts use lexical forms dissimilar from user queries.
Limitations & Future Work¶
- Domain coverage centered on news-style corpora: Evaluations were conducted on real news and news-like fictional universes with clear event timelines; performance on specialized corpora with dense technical conventions, such as clinical trial literature or enterprise software specifications, remains to be verified.
- Textual linearization vs. graph-native reasoning: The pipeline flattens subgraphs into structured natural language rather than executing native graph traversal or multi-hop path reasoning; expanding beyond one-hop neighbors currently causes context overflow, pointing to the need for graph-guided reasoning agents (e.g., Graph-CoT).
- Offline indexing overhead: Extracting propositions and classifying candidate pairs for thousands of documents requires substantial LLM calls during indexing (taking over 10 hours on StreamingQA), making it best suited for read-heavy environments rather than write-intensive, low-latency streaming platforms.
Related Work & Insights¶
- vs Chunk-based Long-Context RAG (Li et al., 2024; Du et al., 2025): While long-context models attempt to ingest uncurated historical logs, factual contradictions in sprawling contexts cause severe attention distraction; ProStruct-RAG demonstrates that relational structuring is far more effective than brute-force window expansion.
- vs Proposition Retrieval & Factuality Scoring (Chen et al., 2024; Li et al., 2025): Dense X treats propositions as independent retrieval targets, and CLARK-News assigns static truthfulness labels; ProStruct-RAG shows that truthfulness is relative and dynamic, requiring explicit inter-proposition updates, contradicts, and supports links.
- vs GraphRAG (Edge et al., 2024; Nishida et al., 2026): Entity-centric GraphRAG builds community summaries across entity co-occurrences, whereas ProStruct-RAG targets fine-grained proposition-level conflict resolution and temporal state transitions.
Rating¶
- Novelty: โญโญโญโญโ (Pioneering framework that models updates, contradicts, and supports relations at the proposition level for temporal RAG)
- Experimental Thoroughness: โญโญโญโญโญ (Evaluated across real-world news and unpolluted synthetic benchmarks, covering multiple retrieval scales, three distinct LLMs, and thorough ablations)
- Writing Quality: โญโญโญโญโญ (Exceptionally well-structured, clear architectural diagrams, and disciplined empirical analysis)
- Value: โญโญโญโญโ (Offers direct architectural guidance for enterprise knowledge bases and time-sensitive agentic RAG systems)