Do LLM Judges of Link-Prediction Explanations Survive a Rephrased Prompt?

Knowledge-graph embedding models predict missing facts, such as "drug X treats disease Y", by scoring triples in a learned vector space. They give no reason for a prediction, so a growing set of methods extracts the supporting training facts after the fact. Judging which of these explanation methods is best has no ground truth. The most scalable current answer is to ask a large language model (LLM) to play a human auditor: show it the query, with and without an explanation, and check whether the explanation helps it guess what the black-box model predicted. This proposal tests whether that judge is measuring the explanation or the wording of its own prompt. Prompted LLMs are known to flip answers when instructions are paraphrased, options are reordered, or a polite phrase is appended. If the judge is brittle in the same way, rankings of explanation methods could be artifacts of one hand-written template.

The proposal has two parts. First, it audits LLM-based explanation evaluation across a controlled family of meaning-preserving prompt variants. Second, it proposes a metric that scores an explanation by two things: how much it improves the judge's ability to predict the black box's output, and how much it makes that guess stable across rewordings. The second term rests on a testable claim. An explanation that really captures why the model made a prediction should anchor the judge, while one that merely looks relevant should not. This differs from simply averaging over prompts. To keep the claim honest, the stability term is compared against plain prompt-averaging and against format-matched placebo explanations.

Core Claim

The closest existing work is LP-DIXIT. It uses frozen LLMs to compute Forward Simulatability Variation (FSV), defined as the judge's accuracy at predicting the black-box model's top answer with an explanation minus its accuracy without one. LP-DIXIT compares explainers including Criage, Kelpie, Data Poisoning and GEnI on six knowledge graphs. It reports that Llama-3.1-70B matches high-scoring human-rated explanations 65% of the time on FR200K, and that single-triple explanations beat GEnI's subgraphs. The research file notes three things LP-DIXIT leaves open. Its scores come from fixed engineered prompts and their sensitivity to rewording is never quantified. Its target is a binary hit or miss rather than a rank. And the judge can answer from memorized world knowledge instead of from the explanation.

We claim that a single-template FSV mixes three things together: explanation quality, prompt artifacts, and judge leakage. We further claim that the reduction in prompt sensitivity an explanation induces is a separate and informative signal of explanation quality. Two lines of evidence motivate this. ProSA shows that an instance is stable under prompt variation when the model's next-token distribution is sharply peaked, and that adding one demonstration is the strongest single stabilizer. Chen et al. show that sensitivity under perturbation is negatively correlated with accuracy (Pearson $r$ up to $-0.40$) and is more informative than raw softmax confidence once label bias is removed. Neither paper touches relational data or explanation evaluation. We carry their measurement apparatus into that setting and use it as a property of the explanation rather than of the instance.

Research Program

For a query $(s, r, ?)$, the black-box model predicts an answer $y$. Let $P$ be a family of $K$ prompts that are meant to mean the same thing. Under prompt $p$ and explanation $e$, the judge produces a ranking over candidate answers, and we write the reciprocal rank it assigns to $y$ as $\mathrm{RR}_p(e)$. Using a rank, rather than a single guess, addresses LP-DIXIT's binary-target limitation. The empty explanation is written $\varnothing$. We define the stable simulatability gain as

$$\mathrm{SSG}(e) = \big[\overline{\mathrm{RR}}(e) - \overline{\mathrm{RR}}(\varnothing)\big] + \lambda\,\big[\mathrm{PSS}(\varnothing) - \mathrm{PSS}(e)\big].$$

Here $\overline{\mathrm{RR}}$ is the mean reciprocal rank over $P$. $\mathrm{PSS}$ is ProSA's PromptSensiScore, the average disagreement in the judge's top answer across pairs of prompts in $P$. The weight $\lambda$ is fixed on a held-out human-rated split and never tuned on test data. Setting $\lambda = 0$ gives prompt-averaged FSV, which is the key ablation.

The prompt family $P$ is built from six perturbation types, each grounded in the file:

  1. Instruction paraphrases.
  2. Shuffled candidate order and swapped option symbols, which moved leaderboards by up to eight positions in When Benchmarks are Targets.
  3. Synonymous relation verbalizations, analogous to the synonym effects reported in Exploring Social Biases of Large Language Models.
  4. Alternative triple serializations, such as tuple form versus KG-LLM-style sentences (KG-LLM).
  5. Trivial surface edits of the kind in The Butterfly Effect of Altering Prompts.
  6. Reordered demonstrations in the few-shot condition, following SENSEL's demonstration-reordering variant.

All candidate scores are corrected with Prototypical Calibration, following Chen et al., so that the judge's built-in preference for certain answer labels does not hide its real sensitivity. A separate entity-anonymized condition replaces entity names with opaque identifiers. This lets us measure how much of any FSV gain survives when the judge cannot fall back on world knowledge.

Baselines

The naive reference point has two parts. The first is the no-explanation judge: the $\varnothing$ terms above, reported as absolute accuracy and PSS. The second is a random-triple explanation, which tells us how much FSV any injected text produces.

The strongest existing method is LP-DIXIT itself. We run its candidate-filtered and few-shot prompt variants with its original templates, the same judge models (Llama-3.1-8B and 70B), the same explainers, and the same graphs. The only reported number found for it is the 65% match with high-scoring human ratings on FR200K for Llama-3.1-70B. We first reproduce that figure with the original template. Beating LP-DIXIT means two things. On FR200K, FTREE and FRUNI, SSG must agree more closely with human explanation ratings than single-template FSV does, measured as match rate and rank correlation, with the same number of judge calls per prompt and compute matched by giving single-template FSV $K$ times as many sampled queries. And the gap must hold for both judge sizes.

The second baseline is prompt-averaged FSV ($\lambda = 0$). This is the obvious repair a reviewer would apply, and it receives the identical prompt family. A third baseline replaces perturbation-based stability with the change in the judge's calibrated maximum probability on a single prompt. A fourth baseline is the removal-based fidelity used by explainers themselves: $\delta$MRR from eXpath and remove-and-retrain probability drop from ExamplE. It is computed on the same queries so that we can ask which judge-based metric tracks real faithfulness.

The ablation that isolates the key ingredient is a placebo explanation matched in length and format. It consists of neighborhood triples drawn around the query entity but not selected by any explainer. If placebos reduce PSS as much as real explanations do, then the stability term is only rewarding the generic anchoring that ProSA documents, and the claim fails.

Why not just…?

Why not just average FSV over several prompts? This is the real threat, and it is exactly the $\lambda = 0$ ablation. If prompt-averaged FSV matches SSG's human agreement and its agreement with $\delta$MRR, then the contribution reduces to the audit plus a recommendation to average. We would report it that way. SSG is justified only if the stability term adds agreement beyond averaging and real explanations beat placebos on that term.

Why not just read the judge's confidence from one prompt? Chen et al. found that on GPT-J-6B, perturbation-based sensitivity beat maximum-probability and entropy baselines by an average of 4.1 points of area under the F1-coverage curve across ten classification datasets. ProSA's observation that strong models can be accurate yet unstable suggests single-prompt confidence misses instance-level fragility. Neither result is on knowledge graphs, so the calibrated-confidence baseline is run head to head rather than dismissed.

Why not skip LLM judges and use removal-based fidelity? $\delta$MRR and remove-and-retrain measure whether the model depends on the facts. They do not measure whether a reader can use them, which is why LP-DIXIT and human studies such as KGExplainer's exist. These metrics are also confounded by the recovery phenomenon ExamplE reports, in which a retrained model regains confidence through redundant facts. We keep them as a reference axis instead of replacing them.

Proposed Experiments

We use FB15k-237, WN18RR, YAGO3-10 and DB50K, following LP-DIXIT. Black-box models are TransE, ComplEx and ConvE. Explainers are Criage, Kelpie, Data Poisoning and GEnI, plus ExamplE and eXpath where code allows. Judges are Llama-3.1-8B and 70B and one Qwen model, run zero-shot and one-shot. Human-rated evaluation uses FR200K, FTREE and FRUNI.

The first decisive check is ranking stability. For each perturbation type we compute Kendall's $\tau$ between explainer rankings under single templates. If $\tau$ stays near 1, LP-DIXIT's rankings are robust and the audit's answer is negative, which is still worth publishing. If $\tau$ drops sharply for some perturbation type, we also test whether LP-DIXIT's headline finding, that single triples beat subgraphs, survives.

The second check is human agreement: SSG versus prompt-averaged FSV versus single-template FSV versus calibrated confidence. The third is the placebo test. The fourth measures how much each metric's explainer ranking changes under entity anonymization, which quantifies judge leakage.

We will also test one specific prediction suggested by KGExplainer's finding that usefulness rises and then falls as more paths are included. The prediction is that PSS reaches its lowest point at an intermediate explanation size. If the minimum instead falls at the largest size, the stability signal is tracking the amount of text rather than explanatory content.