Telling Graph Inference from Memory in LLM Knowledge Graph Completion

Knowledge graphs store facts as (head, relation, tail) triples, such as (Paris, capital of, France). They are always missing many true facts. Knowledge graph completion is the task of predicting the missing ones from the graph that is given. Large language models now post strong completion numbers on the standard benchmarks. Those benchmarks, however, are built from Freebase, WordNet and Wikidata, and a model trained on the web has read the underlying facts many times. So a high score could mean the model reasoned over the graph it was shown, or it could mean the model remembered the answer. For a public encyclopedic graph the two are hard to separate. For a private biomedical or enterprise graph, or for any graph whose facts have changed since the model was trained, only the first kind of skill helps.

We propose a test that separates the two exactly. Take a benchmark graph and rename its entities with a single consistent shuffle that only swaps entities of the same type. Every training triple is rewritten under the same shuffle, so the new graph has the same shape as the original: the same edges in the same pattern, under different names. A method that reads only graph structure must score the same on the original and shuffled versions, up to random-seed noise. A method that leans on memory will be pulled toward the facts it remembers, which are now wrong in this graph. The difference in score measures how much a method relies on memory instead of the graph.

We then use this test to evaluate one specific design hypothesis. The hypothesis is that splitting the completion workflow into separate agents with deliberately restricted information can keep the benefit of world knowledge while staying robust when the graph contradicts that knowledge. The key restriction is a structural agent that never sees entity names. We also take seriously the possibility that a much simpler score-fusion model does just as well.

Core Claim

Our claim has two parts. The first is a measurement claim. Reported LLM gains on FB15k-237, WN18RR and CoDEx partly come from recalling world facts the model already knew, and a type-preserving entity shuffle measures that share without any access to the model's training data. The second is a method claim, and it is falsifiable. The robustness comes from two things together: a "context firewall" that keeps entity names away from a structural agent, and an explicit check of whether the given graph agrees with what the model remembers. Together these let a decomposed system match pure structural models on the shuffled graph while keeping LLM-level accuracy on the original graph and on entities that appeared after the model's training cutoff.

If a single model given the same consistency signal, or a learned blend of embedding and LLM scores, matches the decomposed system, then the second claim is wrong. In that case the paper becomes a paper about the signal rather than about agents. The experiments are designed so that this outcome is visible.

Why this gap is real

LLM-based completion methods supply the strongest numbers and leave this question untested. EGIT uses embedding models to retrieve candidate answers and fine-tunes an LLM to rerank them. It reports WN18RR MRR (mean reciprocal rank, the average of one over the rank of the true answer) of 0.674 and FB15k-237 Hits@1 of 0.341, compared with 0.271 for ComplEx. OMNIA proposes candidates by spreading known edges across clusters of similar entities, filters them with TransE, and validates them with an LLM, reporting F1 gains of up to 23 points on CoDEx-M. Both evaluate only on static public graphs whose entity names and facts are widely available online. Neither asks how much of the gain survives once memorized facts stop being correct.

Three lines of work motivate the worry. The contamination survey documents sharp drops on test items that postdate a model's training. DyVal shows that models strong on static reasoning benchmarks score near zero on freshly generated graph-structured problems. CoDEx shows that frequency shortcuts alone reach MRR 0.236 on FB15k-237 and 0.135 on CoDEx-M.

Two papers constrain the design. AntiLeakBench finds an "outdated knowledge trap": models given post-cutoff context stating new facts still answer with the old facts they memorized. This means that telling a model to trust the graph is unlikely to be enough, and our shuffled graph is a controlled, large-scale version of exactly that conflict. Rephrased-sample contamination and cross-lingual contamination show that memorization survives paraphrase and translation. For that reason we change which facts hold in the graph, not how they are worded.

The closest existing works each cover only part of this. CoreEval swaps the factual core of natural-language-understanding examples for fresh news facts. INVITE distorts DBpedia triples to create false-premise questions. Both apply fact substitution to question answering or classification, and neither keeps the graph's structure exactly intact, so neither yields a structure-invariant control. AgREE is the nearest completion system. It is a single iterative web-search agent for entities created after the model's cutoff, reporting 88.9% relation-aware Hits@1. It treats new facts as something to look up, not as something the graph supplies. It also relies on one agent checking its own work, which the multi-agent literature (Self-collaboration, LEGO) argues is prone to confirmation bias.

Research Program

The shuffled-graph protocol. For each benchmark, we draw a random one-to-one mapping $\pi$ from entities to entities that maps each entity to another of the same type. We use CoDEx entity types, WordNet part-of-speech groups for WN18RR, and Freebase types for FB15k-237. We apply $\pi$ to the training, validation and test triples alike. Because types are preserved, any schema rule restricting which types a relation may connect still holds. This lets us extend the protocol to the schema-annotated KG-SAF-DATA suite without creating logical inconsistencies. Each entity's name and description move with its new identity.

We evaluate every method under three conditions. The first is the original graph. The second is an anonymized graph, where names are replaced by meaningless identifiers, so memory can neither help nor hurt. The third is the shuffled graph, where memory actively misleads. For a method $m$, the memory-reliance gap is

$$\Delta_m = \mathrm{MRR}_m(\text{original}) - \mathrm{MRR}_m(\text{shuffled}),$$

where MRR is the filtered mean reciprocal rank of the true answer. For any purely structural model, $\Delta_m$ should be zero within seed variance, because the shuffled graph has the same structure as the original. This gives a built-in sanity check on the protocol. Comparing the original and anonymized conditions measures how much memory helps when it is correct. Comparing the anonymized and shuffled conditions measures how much it hurts when it is wrong.

The decomposed system. Four roles share one base LLM.

The structural proposer sees only the anonymized local subgraph and the top candidates from a TuckER model. It cannot be pulled toward memorized facts because it never sees a name. This is the context-firewall idea from the multi-agent survey and UrbanKGent, here aimed at parametric memory instead of at tools.

The semantic proposer sees names and descriptions and proposes candidates from world knowledge, as in OMNIA's validation stage.

The consistency critic compares the graph's neighborhood of the query entity with what the model believes about that entity's name. For example, it checks whether "Paris" in this graph has the neighbors the model associates with Paris. It outputs a disagreement score along with the specific edges that conflict.

The arbiter combines the two candidate lists. It shifts weight toward the structural proposer as disagreement rises, and it requires any semantic-only answer to come with supporting edges from the given graph.

Studying the mechanism. We vary which roles can see names, whether the critic is present, and whether the critic's signal goes to the arbiter or to a simple learned blend of scores. The purpose is to pin down which component produces the robustness, following the attribution concerns raised in Investigating Component Contributions in Multi-Agent ML Systems.

Baselines

The naive reference is the frequency baseline from CoDEx, which reports MRR 0.135 on CoDEx-M and 0.236 on FB15k-237. Any method falling to this level on the shuffled graph has learned nothing usable from the graph.

The structural reference is TuckER (TuckER; MRR 0.358 on FB15k-237), retrained on each condition with the same hyperparameter budget. It is the strongest competitor on the shuffled graph, since by construction memory cannot affect it. We beat it if we come within one MRR point of it on the shuffled graph while exceeding it on the original. No reported TuckER result on CoDEx-M was found on Lacuna for us to compare against, so we will measure it ourselves.

The strongest LLM methods are EGIT (WN18RR MRR 0.674 and FB15k-237 Hits@1 0.341, from EGIT) and OMNIA (CoDEx-M F1 gain of up to 23 points, recovering 70.65% of missing triples, from OMNIA). We rerun both with our base LLM on all three conditions. Our first expected finding is that both show a large memory-reliance gap. The decomposed system beats them if it has a substantially smaller gap and no more than a two-point loss on the original graph.

AgREE (AgREE; 88.9% relation-aware Hits@1 on Emerging-Entities) is the reference on entities that postdate the model's training. We run it with the same search tools, and here we only aim to match it.

The single-model control is chain-of-thought prompting with self-consistency (sampling several reasoning traces and taking the majority answer), using the same base LLM, the same total token budget as the full agent pipeline, and the same subgraph context. It is also explicitly instructed to prefer the graph when the graph and its memory disagree.

The learned-blend control is a logistic gate fit on validation data over TuckER scores, LLM scores, and the critic's disagreement score. Finally, three ablations isolate the ingredients: removing the firewall (the structural proposer sees names), removing the critic, and removing the arbiter in favor of the learned blend. All learned components share one validation set, and the original and shuffled conditions use identical tuning budgets.

Why not just…?

Why not just use TuckER or RotatE, which are immune by construction? On the shuffled graph they are the ceiling to match, and we say so. The reason not to stop there is that pure embedding models cannot represent entities that were absent from training (the cold-start case AgREE targets). They also trail hybrid systems on the original graph, where EGIT gains 7 Hits@1 points over ComplEx on FB15k-237. If our system cannot beat TuckER on the original graph and on Emerging-Entities, the recommendation is simply to use TuckER, and we would report that.

Why not just prompt one model to trust the graph? AntiLeakBench found that models given explicit post-cutoff context still fall back on memorized facts. DyVal found that 33.8% of GPT-4's failures on graph problems were unsupported conclusions. The token-matched self-consistency baseline tests this directly. If it closes the memory-reliance gap, the firewall is unnecessary.

Why not just anonymize the entities at test time? This removes memory reliance, but it also removes legitimately useful world knowledge. That knowledge matters most in sparse graph regions, where OMNIA itself reports that structural candidate generation runs out of candidates. Comparing the anonymized and original conditions on low-degree test entities measures exactly what is lost.

Why not just blend embedding and LLM scores with a learned gate? This is the serious threat. Given the critic's disagreement score as an input, a logistic gate might match the arbiter at a fraction of the cost. We run that exact comparison. If the gate ties the arbiter, we will report that the contribution lies in the firewalled structural channel and the consistency signal, not in multi-turn agent interaction, and that the cheaper system should be preferred.

Decisive Checks

The protocol is valid only if TuckER's MRR on the original and shuffled graphs agrees within seed variance on CoDEx-M, FB15k-237 and WN18RR. If it does not, the shuffle is leaking information through types or degrees and must be fixed before anything else.

The measurement claim holds if EGIT and OMNIA show a positive memory-reliance gap that is clearly larger than TuckER's, with the gap concentrated on well-known, high-degree entities.

The method claim holds if three things are true together. First, the full system's gap is close to TuckER's. Second, removing the firewall restores most of the gap. Third, the single-model control and the learned gate, at matched compute, both retain a larger gap or lose more accuracy on the original graph.

On Emerging-Entities, the system should match AgREE's 88.9%. Throughout, we report token cost per query so that any robustness gain can be weighed against the coordination overhead that multi-agent systems are known to carry.

References

  1. Mitigating Hallucinations in Knowledge Graph Completion via Embedding-Guided Instruction Tuning
  2. OMNIA: Closing the Loop by Leveraging LLMs for Knowledge Graph Completion
  3. Benchmark Data Contamination of Large Language Models: A Survey
  4. DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
  5. CoDEx: A Comprehensive Knowledge Graph Completion Benchmark
  6. AntiLeakBench: Preventing Data Contamination by Automatically Constructing Benchmarks with Updated Real-World Knowledge
  7. Rethinking Benchmark and Contamination for Language Models with Rephrased Samples
  8. Data Contamination Can Cross Language Barriers
  9. CoreEval: Automatically Building Contamination-Resilient Datasets with Real-World Knowledge toward Reliable LLM Evaluation
  10. INVITE: a Testbed of Automatically Generated Invalid Questions to Evaluate Large Language Models for Hallucinations
  11. AgREE: Agentic Reasoning for Knowledge Graph Completion on Emerging Entities
  12. Self-Collaboration Code Generation via ChatGPT
  13. LEGO: A Multi-agent Collaborative Framework with Role-playing and Iterative Feedback for Causality Explanation Generation
  14. Return of the Schema: Building Complete Datasets for Machine Learning and Reasoning on Knowledge Graphs
  15. A survey on LLM-based multi-agent systems: workflow, infrastructure, and challenges
  16. UrbanKGent: A Unified Large Language Model Agent Framework for Urban Knowledge Graph Construction
  17. Investigating Component Contributions in Multi-Agent ML Systems
  18. TuckER: Tensor Factorization for Knowledge Graph Completion