Systems that answer questions by retrieving pieces of a knowledge graph and pasting them into a language model's prompt (graph retrieval-augmented generation, or graph RAG) usually treat the graph as a frozen snapshot. Real interaction graphs are not frozen. People email, follow, and reply at specific times, so a chain of contacts A→B→C can carry information only if the A→B contact happened before the B→C contact. A static retriever ignores this. It will return chains where each link is real and correctly dated, but where the links happen in an order that makes the chain impossible as a route for information. We propose that these temporally impossible paths are a distinct and especially harmful kind of prompt noise. They look coherent, every fact in them is true, and they point to a confident wrong answer. That combination is exactly the profile that the contextual-distraction literature identifies as most damaging to language models.
The claim is narrow and testable. For questions about propagation and reachability over evolving interaction graphs ("could Z have learned X from A before date d?", "which account could have been the earliest source?"), we predict three things. First, time-invalid paths lower accuracy more per token than unrelated text of the same length. Second, the two cheap fixes, filtering to a single time snapshot and writing timestamps into the text, do not remove the damage. Third, retrieving only time-respecting journeys removes most of it. A time-respecting journey is a path whose edge timestamps never decrease, a standard notion in the dynamic-network literature. We also ask whether a reader trained to resist noise makes structural filtering unnecessary. Prior work disagrees on that question, and our design is built to settle it for this case.
What is already done, and what is not
Temporal graph RAG exists and is strong. DyG-RAG anchors facts to timestamps as event units, retrieves with joint semantic and time embeddings, and enforces chronology with time-aware chain-of-thought. STAR-RAG compresses a temporal knowledge graph into a rule graph that drops order-violating edges and cuts tokens by 97%. KG-IRAG checks interval consistency with a verifier agent. All three are built for fact-state questions, of the form "who held office at time t?". In that setting the noise is a fact that was true at the wrong time, and filtering by a validity window at query time handles most of it.
Our target is different. We study path-composition questions, where every individual edge is valid but the answer depends on whether the edges can be chained in time order. None of the three systems evaluates this. None of them measures how this noise acts inside the reader compared with ordinary distractors.
On the other side, static graph RAG systems prune noise but assume a frozen topology. These include GRAG (k-hop ego-graphs with learned soft pruning), GNN-RAG, MIXRAG, and DA-RAG, which removes "free-riders": nodes that are structurally central but irrelevant to the query. Our hypothesis is that, in an evolving graph, the most dangerous free-riders are nodes that are reachable only through time-invalid chains. RAG4DyG works on the same dynamic interaction graphs we will use, but it predicts links. It does not generate language.
Two lines of work motivate the distractor hypothesis. Breaking Focus shows that semantically coherent distractors cut accuracy by about 45%, and that telling a model to "ignore irrelevant information" does not help. The diffusion literature shows that treating a changing graph as static badly corrupts inference about cascades and sources (DANI; source localization).
Two results constrain the design. When Silence Is Golden reports that supplying knowledge-graph context helped less than explicit reasoning supervision with reinforcement learning. Ext2Gen finds that separate pre-compression modules lose to joint extract-then-generate training. Either result could mean that structural filtering is the wrong lever, so we test that directly instead of assuming it.
Research Program
Benchmark: TRAP (Temporal Reachability And Propagation questions). We will build TRAP from timestamped interaction graphs: Enron, UCI messages, Reddit, and Wikipedia (the dynamic-graph datasets used by RAG4DyG), plus ICEWS event streams (the source of MultiTQ). Edges are rendered as short text facts ("On 2001-03-04, Lay emailed Skilling about…"). Questions fall into four types: temporal reachability, earliest possible source, a deadline-bounded influence set, and unanswerable variants where no valid journey exists and the correct output is to abstain.
Because the ground truth is computed by earliest-arrival search over the timestamped edge stream, labels are exact and need no annotation. Earliest-arrival search is a single pass that runs in time roughly linear in the number of edges. For each question we also mine impossible-path distractors: chains that connect the query endpoints in the static union graph but break time order. We choose these to match valid journeys in hop count and token length.
Controlled distraction study. Holding the gold evidence fixed, we inject a measured number of tokens drawn from one of three sources: unrelated edges from the same graph, valid-but-irrelevant journeys, or impossible paths. This gives a dose-response curve of accuracy against injected tokens for each distractor type. On open-weight readers we also record how much attention falls on the gold-journey tokens versus the injected tokens. This tests whether impossible paths take attention away from the gold evidence more than length-matched unrelated text does, which would be a mechanism-level version of the dilution account.
Intervention. Journey retrieval runs earliest-arrival search from the query anchor, with the query's deadline as an upper bound. It keeps only edges that lie on some time-respecting journey and then ranks them by semantic relevance under a fixed token budget. Because the token budget is fixed, any gain must come from which edges are kept, not from showing the model fewer tokens.
We will also run a streaming variant. New edges arrive in time order and only extend earliest-arrival labels, so maintenance under insertions is cheap. Deletions and late-arriving edges are harder: the Dynamic influence maximization lower bound for fully dynamic updates warns that cheap exact maintenance may be impossible there. We will measure update cost rather than claim it is low.
Baselines
The naive reference points are the reader with no retrieval, and the reader given the full timestamped edge list around the query endpoints, truncated to the context limit. These show how far the problem sits from both extremes.
The strongest static competitor is GRAG-style k-hop ego-graph retrieval with learned soft pruning (GRAG). It represents the best structural noise removal that assumes a frozen graph. GRAG reports WebQSP Hit@1 of 0.7236, but that is a static benchmark. On TRAP, no reported result was found on Lacuna. We will retrain its pruning module on TRAP training questions using the same reader and token budget.
The strongest temporal competitor is a STAR-RAG-style pipeline: order-violation edge pruning plus seeded Personalized PageRank. Its paper reports 44.4% Hit@1 on MultiTQ against 23.8% for the best temporal baseline (STAR-RAG). We will also report DyG-RAG with time-aware chain-of-thought, which reports 58.78% accuracy on TimeQA (DyG-RAG). Both will be run on our MultiTQ-derived split and on TRAP, with matched reader, token budget, and number of LLM calls where the method permits it, and with LLM calls reported where it does not.
We will also include a snapshot filter, which keeps only edges valid at the query time, and a timestamp-annotation baseline, which puts every edge in the prompt with its date.
The reader-side competitor is an Ext2Gen-trained reader (Ext2Gen), which reports an average score of 0.557 against 0.473 for the default Llama3.1-8b-instruct. Alongside it we will include an abstention-RL reader in the style of When Silence Is Golden. Both will be trained on TRAP training data with the same compute as any reader training we do.
The key ablation removes, at a matched token budget, the same number of edges as journey retrieval but chooses them at random or by semantic score. This isolates the time-respecting constraint itself. We count journey retrieval as beating the baselines if it improves accuracy and abstention F1 on path-composition questions over the best temporal competitor by a margin outside seed variance, while staying within noise of that competitor on fact-state questions.
Why not just…?
Why not just filter edges to the query-time snapshot? For "current state" questions, this handles deleted edges and may work as well as anything we propose; we expect it to. It fails by construction on journey questions. An edge valid at time 3 and another valid at time 1 can both survive a snapshot that spans the query window, yet the chain built from them is impossible. The impossible-path versus snapshot comparison on TRAP will show the size of that gap. If the gap is small on real data, because impossible paths turn out to be rare, the proposal reduces to a benchmark finding, and we will report it that way.
Why not just write the timestamps into the text and let a long-context model check the order? This is the most serious threat. DyG-RAG shows that retrievers ignore temporal modifiers. Breaking Focus and UDA show that readers struggle when the relevant details are buried in long, coherent text. Still, checking order on a dated chain is a simple local comparison that a strong model might manage. The timestamp-annotation arm, run as a dose-response across chain length and number of distractors, decides this. If annotated readers stay flat as distractors increase, structural retrieval is not needed.
Why not just train the reader to be robust, as Ext2Gen or abstention RL do? When Silence Is Golden suggests that reasoning supervision beats cleaner context. However, it also reports gaps in cross-domain generalization. We cross retrieval type (static versus journey) with reader type (base versus trained), train on the Enron and UCI graphs, and test on Reddit and ICEWS. If a trained reader with static retrieval matches journey retrieval out of domain, the reader is the right lever. We expect the two to be complementary instead.
Why not just periodically re-index a static graph? Re-indexing refreshes which edges exist. It still stores no ordering among them, so impossible paths survive any re-index frequency. The snapshot arm already gives an upper bound on what re-indexing can achieve.
Decisive Checks
The thesis holds if three things are true. Impossible paths produce a steeper dose-response than length-matched unrelated edges. Journey retrieval at a matched token budget beats the snapshot, timestamp-annotation, and STAR-RAG-style arms on path-composition questions, with the gain carried by the random-removal ablation's failure to reproduce it. And this advantage persists against trained readers on held-out graphs.
The thesis fails if annotated or trained readers make the impossible-path curve flat. In that case the right conclusion is that temporal order is a reader-side skill, not a retrieval problem, and that would also be worth reporting.
References
- DyG-RAG: Dynamic Graph Retrieval-Augmented Generation with Event-Centric Reasoning
- Right Answer at the Right Time — Temporal Retrieval-Augmented Generation via Graph Summarization
- KG-IRAG: A Knowledge Graph-Based Iterative Retrieval-Augmented Generation Framework for Temporal Reasoning
- GRAG: Graph Retrieval-Augmented Generation
- GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning
- MIXRAG : Mixture-of-Experts Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering
- DA-RAG: Dynamic Attributed Community Search for Retrieval-Augmented Generation
- Retrieval Augmented Generation for Dynamic Graph Modeling
- Breaking Focus: Contextual Distraction Curse in Large Language Models
- DANI: fast diffusion aware network inference with preserving topological structure property
- A Probabilistic Graph Diffusion Model for Source Localization (Student Abstract)
- When Silence Is Golden: Can LLMs Learn to Abstain in Temporal QA and Beyond?
- Aligning Extraction and Generation for Robust Retrieval-Augmented Generation
- Dynamic influence maximization
- UDA: A Benchmark Suite for Retrieval Augmented Generation in Real-World Document Analysis