Language models are now used as link predictors. A link predictor is a model that guesses which missing connections in a network are real, for example "which word is a hypernym of oak" in WordNet. Language models do this by reading graph neighborhoods written out as sentences. They report near-perfect scores on knowledge-graph benchmarks. Those scores come from two flattering conditions at once. First, the test sets pair each true link with one easy random non-link, even though real graphs contain millions of non-links for every true one. Second, the benchmarks (WordNet, Freebase, NELL) have almost certainly been read by these models during web pretraining. Nobody has separated the two effects, so it remains unknown whether the model is reasoning over the graph it is shown or recalling facts it already saw.
We propose a simple audit that separates them. Keep the graph's wiring exactly fixed and permute entity names among entities of the same type. A model that reasons from structure should be unaffected, because the task is identical up to relabeling. A model that leans on memorized world facts will be pulled toward the answer that is true in the world but wrong in the graph it is shown. We then measure this "memory pull" while making the negatives progressively harder, moving from random pairs to same-community pairs to full ranking over all entities. Our central prediction runs against the intuitive hope that realistic evaluation washes out contamination. We expect memorization to matter more when negatives are hard, because hard negatives are exactly the cases that local structure cannot separate and recall can.
Core Claim
The test is a counterfactual relabeling. For a knowledge graph, we partition entities into type strata, such as WordNet part of speech or Freebase entity type. Within each stratum we shuffle the human-readable names while leaving every edge attached to the same underlying node. The resulting graph is structurally isomorphic to the original. Any structure-only method (RotatE, Gelato, rule mining, common-neighbor heuristics) therefore produces identical rankings, which serves as a built-in sanity check. Read as text, however, most of its triples are now false in the world.
We run three conditions: true names, permuted names, and synthetic identifiers ("Node_419"). Together they decompose a language model's performance into three parts. The first is legitimate use of name semantics, which shows up as the gain of true names over synthetic IDs that does not come from conflicting recall. The second is reliance on memorized facts, which shows up as the per-query rate at which, under permutation, the model ranks the world-true tail above the structurally correct one. The third is structural reasoning, which is the synthetic-ID performance.
The claim has two parts. The first is a measurement instrument that attributes link-prediction skill to memory at the level of individual edges. The second is an empirical hypothesis: memory pull and the true-minus-synthetic gap both grow as the evaluation moves from balanced random negatives to community-partitioned hard negatives to full ranking.
Relation to Prior Work
Three papers motivate the gap. Knowledge Graph Large Language Model (KG-LLM) for Link Prediction fine-tunes Flan-T5, LLaMa2 and Gemma on multi-hop paths linearized into sentences. It reports 0.98 F1 on WN18RR with one in-context example. It runs no contamination audit and evaluates only as balanced classification. We reuse its training recipe exactly and change only the evaluation. Attribute-Enhanced Similarity Ranking for Sparse Link Prediction (Gelato) shows that balanced random negatives hide failures of graph neural networks. It supplies the method we borrow for hard negatives, which is sampling non-links from inside the same METIS graph partition as the query node. Gelato never considers pretrained models or pretraining leakage. Realistic Re-evaluation of Knowledge Graph Completion Methods shows that within-graph leakage through inverse relations and Cartesian-product patterns inflated FB15k and WN18. On the cleaned FB15k-237, ConvE's filtered mean reciprocal rank (MRR) falls from 0.698 to 0.305. That paper addresses leakage between training and test splits. Ours addresses leakage from pretraining corpora, which cleaned splits do not remove.
Three contamination papers constrain the design. On The Fragility of Benchmark Contamination Detection in Reasoning Models shows that likelihood-based detectors such as LiRA fall to roughly 50–58% AUROC once a model has been post-trained or contaminated with reasoning chains. KG-LLM's path prompts are such chains, so we avoid any detector that reads token likelihoods. Test of Time shows that rephrasing removes temporal decay and cuts influence attribution from 77.5% to 17.5% while the model keeps the benefit. This tells us that surface-form checks miss leakage, so our probe intervenes on what the model would have to know rather than on wording. PaCoST compares confidence on original versus rephrased items to flag contamination at the dataset level. We use it as a baseline. Our test differs in two ways: it works per edge, and it creates a direct conflict between memory and evidence rather than comparing confidences.
Research Program
We fine-tune Flan-T5-Large, LLaMa2-7B and Gemma-7B with KG-LLM's 4-bit LoRA recipe on WN18RR, FB15k-237, NELL-995 and YAGO3-10. Each model is trained separately under each naming condition. Training on permuted names lets the model learn the permuted graph, so any residual pull toward world-true answers comes from pretraining.
We use three tiers of negatives. The first is KG-LLM's 1:1 random protocol. The second uses 1,000 same-partition hard negatives per positive, chosen by METIS as in Gelato. The third is filtered ranking over all entities, made tractable by having a structural model shortlist the top 500 candidates and the language model rerank them. Because the shortlist could hide memory effects, we always place the world-true answer and the structurally correct answer inside it.
For ground truth, we continue pretraining a small open model (OLMo-scale) on text with a known random half of WN18RR test triples written out as sentences. We then run the identical pipeline. This tells us whether memory pull recovers which edges were planted, and it is the test that validates the instrument.
As a secondary question tied to the imbalance literature, we train each language model with binary cross-entropy and with Gelato's N-pair ranking loss. We ask whether the training objective chosen for imbalance changes how much the model leans on recall.
Baselines
The naive reference point is the score as currently reported: balanced 1:1 classification F1 from the KG-LLM recipe. The paper reports 0.98 F1 (Gemma-7B, one-shot, WN18RR) and 0.96 F1 (LLaMa2-7B, NELL-995) in KG-LLM. We reproduce it first. Our claim is undercut if this number stays near 0.98 under synthetic IDs, because that would mean no inflation from names.
The strongest structure-only competitors are RotatE and ConvE trained on the same splits. Their reported filtered MRR is 0.337 on WN18RR and 0.305 on FB15k-237 in Realistic Re-evaluation. We add AMIE rule mining. For the citation graphs (CORA, CITESEER, using paper titles as names) we use Gelato. Gelato's paper reports only relative Hits@1000 gains of 138% and 125%, and no absolute value was found on Lacuna, so we rerun it ourselves.
All baselines use identical splits, negatives and filtering, and receive the same hyperparameter search budget of 20 configurations each. Their invariance to name conditions is checked rather than assumed. A language model "beats" these baselines in a meaningful sense only if its synthetic-ID MRR on full ranking exceeds RotatE's. Name-dependent gains above that line are what the audit attributes.
The contamination baseline is PaCoST run per dataset, alongside a closed-book probe that asks the language model "is (h, r, t) true?" with no graph context. The key ablation separates permutation from anonymization. Synthetic IDs alone conflate lost semantics with lost memory. Permutation alone tests memory directly. The size of the difference between the two is the result.
Why not just…?
Why not just anonymize entity names and see if performance drops? A drop is ambiguous. WordNet names carry legitimate meaning: "oak" and "tree" sharing a hypernym edge is semantics, not leakage. Anonymization removes both semantics and memory together. Permutation keeps names that are type-plausible while making recalled facts point the wrong way, so it isolates reliance on memory. If permutation and anonymization give the same drop, the alternative suffices and we will say so.
Why not just run a closed-book probe of what the model knows? Knowing a fact is not the same as using it to predict links. A model could know WordNet yet follow the graph context when the two conflict. The closed-book probe is reported as a baseline. The relevant test is whether closed-book accuracy predicts memory pull edge by edge. A high correlation would make our instrument redundant, and that is a real possibility.
Why not just use PaCoST, LiRA or temporal splits? The Fragility results show likelihood detectors near chance after post-training and chain-of-thought contamination. Test of Time shows temporal cutoffs fail once questions are transformed, and graph benchmarks like WordNet have no meaningful cutoff in any case. The planted-triple experiment compares all of these against memory pull on the same known ground truth.
Why not just evaluate on cleaned splits like FB15k-237? Cleaning removes inverse-relation leakage inside the benchmark. It does not remove pretraining exposure to Freebase facts. Our named-versus-synthetic gap on FB15k-237 directly measures what cleaning leaves behind.
Decisive Checks
The instrument is valid if memory pull separates planted from unplanted triples in the controlled model with AUROC well above the PaCoST and LiRA baselines, while structure-only models show zero pull. The central hypothesis is supported if, across the three public language models, the true-name minus synthetic-ID gap in Hits@10 and MRR is larger under partition-based hard negatives and full ranking than under 1:1 random negatives. It is refuted if the gap shrinks toward zero as negatives harden, which would mean the haystack drowns memorized signal. Either outcome changes how language-model link predictors should be reported. The secondary result is whether the N-pair ranking loss raises or lowers memory pull relative to cross-entropy.
References
- Knowledge Graph Large Language Model (KG-LLM) for Link Prediction
- Attribute-Enhanced Similarity Ranking for Sparse Link Prediction
- Realistic Re-evaluation of Knowledge Graph Completion Methods: An Experimental Study
- On The Fragility of Benchmark Contamination Detection in Reasoning Models
- Test of Time: Rethinking Temporal Signal of Benchmark Contamination
- PaCoST: Paired Confidence Significance Testing for Benchmark Contamination Detection in Large Language Models