Exact Graph Counterfactuals for Detecting Memorized Diagram Benchmarks

Vision-language models, which answer questions about images, are increasingly scored on benchmarks of node-link diagrams such as flowcharts, process maps, and knowledge graphs. These benchmarks are small, static, and public, so a model may have seen the test images during training. A high score can then mean that the model memorized the answers rather than learned to read the diagram. Contamination detectors for images exist, but they rely on diffusion models to repaint natural photos, and those repaints are approximate. Text-based detectors fail in a different way: they look for unusually low loss on test items, and reinforcement-learning post-training erases that signal.

Diagrams of graphs offer something photos do not. The picture and the thing it depicts can be changed separately and exactly. We can redraw the same graph with a different layout, which changes almost every pixel and leaves the answer unchanged. Or we can keep the drawing fixed and add, remove, or reroute a single edge, which changes almost no pixels and does change the answer. A model that reads the diagram should follow the graph in both cases. A model that memorized the benchmark should follow the picture: it should fail on the redrawn version and keep giving the old answer on the edited one. We propose this two-way test as a deterministic contamination audit for graph-diagram benchmarks. Scalable graph-drawing methods play a supporting role: they keep the redrawn and edited diagrams legible, so that failures cannot be blamed on visual clutter.

Core Claim

The most informative signal is answer stickiness. This is the rate at which a model returns the original benchmark answer when a minimal, legible edge edit has made that answer wrong while the image stays nearly identical. Our claim is that stickiness, combined with the accuracy drop under readability-matched re-layout, separates contaminated from clean models more reliably than either signal alone. It should also beat loss-based detectors, and it should keep working after reinforcement-learning post-training, which defeats those detectors.

The main confound is layout difficulty. A new layout may simply be harder to read, and edge density alone produces what ProcVQA calls a "density wall," an 18.5x increase in hallucinations for Gemini-2.5-Pro on dense charts. Any honest audit has to hold readability fixed. Graph-drawing scalability research supplies the tools for doing so.

Relation to Prior Work

The closest work is Contamination Detection for VLMs Using Multi-Modal Semantic Perturbations. It uses Flux with ControlNet edge guidance to synthesize counterfactual natural images that change the answer while preserving composition. Clean models gain accuracy on these variants (+31.5% on MMStar), while contaminated models fall by as much as 45%.

We borrow its logic of counterfactuals that flip the answer, and we change three things. First, our perturbations are exact graph edits with known ground truth, so there are no generation artifacts and no unverifiable answers. Second, we add a second axis, same graph with a new drawing, that the diffusion approach cannot produce precisely. Third, we target abstract relational diagrams, which that work explicitly leaves out.

Dynamic benchmarks attack contamination from the other direction, by producing new items at test time:

  • DyVal builds reasoning problems from randomly generated directed acyclic graphs and describes them in text.
  • DARG builds adaptive reasoning graphs for the same purpose.
  • KBE-DME evolves visual question-answering items through knowledge-graph subgraphs.

All three motivate our work, because they show contamination inflates static scores; DyVal reports phi-1.5 and WizardMath-13B falling to near zero on its generated tasks. But none of them answers the auditor's question: was this static benchmark leaked into this model? We answer that question per item and per model, on existing benchmarks.

On The Fragility of Benchmark Contamination Detection in Reasoning Models constrains our design. It shows that clipping in GRPO-style training shrinks the loss gap that detectors depend on. LiRA reaches 89.1% AUROC before reinforcement learning, loses about 14 points after one GRPO epoch, and many reference-free detectors approach 50%. This result predicts that likelihood-based signals are the wrong foundation. It does not rule out behavioral signals, and whether stickiness survives the same treatment is one of our tests.

The diagram benchmarks themselves provide the audit targets:

  • Advancement in Graph Understanding: 2,807 images spanning knowledge graphs, route maps, flowcharts, mind maps, and Gantt charts.
  • ProcVQA: 118 mined process diagrams with structure-type and density annotations.
  • GRAB: mathematical graphs, used as a secondary target.

Graph-drawing methods provide the means of controlling readability:

That metric's authors caution that k-means assumes round clusters, and that LinLog can score well by collapsing a cluster into a single point. For that reason we never use it as the only readability criterion.

Research Program

Recovering the graphs. For each benchmark item we first recover the underlying graph. Some benchmarks ship their source structure. Otherwise we transcribe the graph and verify it by re-rendering, and we drop items whose transcription cannot be verified.

Re-layout variants. Each graph is redrawn with several layout families: spring layout, sfdp, spectral, and, for graphs past roughly a hundred nodes, BC-tree or multilevel layouts. Styling, fonts, and labels are held as close to the original as possible.

Readability matching. A variant is kept only if it matches the original within tolerance on four measures: edge-crossing count, minimum node spacing, label overlap, and clustering quality. Because the metric has blind spots, variants must also pass a legibility check with a clean control model. We fine-tune that model only on disjoint diagram data and require it to answer the variant correctly about as often as the original.

Edit variants. Each item also gets a minimal edit. Using the original coordinates, we add, delete, or redirect one edge (or relabel one node) so that the answer to the question provably changes. We re-render with the original layout frozen and the new edge routed to avoid new crossings. Edits are restricted to regions that pass a local-density threshold, which again uses graph-drawing measures, so that an edit is never buried in a hairball.

Scores. For each item and model we compute two quantities:

  • the re-layout gap $\Delta_L$: accuracy on the original minus mean accuracy on its readability-matched redraws;
  • stickiness $S$: the fraction of edit variants on which the model outputs the original, now-incorrect answer.

The detector is a logistic combination of $\Delta_L$ and $S$. Its only fitted parameters are two weights and a bias, fitted on one benchmark and tested on the others. Aggregated over items, the same scores give a per-model contamination estimate.

Controlled contamination for ground truth. Following the dosage design of the semantic-perturbation paper, we fine-tune LLaVA-v1.5-7B and one more recent open vision-language model on the test splits of the diagram benchmarks. We contaminate half the items of each benchmark, at 0, 1, and 3 epochs. The uncontaminated half serves as a within-model clean reference. To test robustness to post-training, a third arm applies a GRPO stage after contamination, mirroring the Stage I protocol of the fragility paper. Only then do we apply the audit, as an exploratory step, to closed frontier models whose training data is unknown.

Baselines

The naive reference is to take raw benchmark accuracy at face value. Its score as a detector is the AUROC obtained by using per-item correctness itself as the contamination score. Any useful audit must clearly exceed it, because hard items that a clean model gets wrong look "clean" under this rule.

The strongest existing method is diffusion-based semantic perturbation from Contamination Detection for VLMs Using Multi-Modal Semantic Perturbations. It is the only published contamination detector built for vision-language models, and on natural images it separates clean from contaminated models sharply. The paper reports, for LLaVA-v1.5-7B on MMStar, that contamination raised original accuracy from about 38% to about 54% while perturbed accuracy fell from about 69% to about 38%. No reported result was found on Lacuna for that method on node-link diagram benchmarks.

We will run it with its own Flux and ControlNet pipeline on exactly the items, contaminated models, and seeds we use, and generate the same number of variants per item. We will use its published answer-verification step, and we will also report how often its generated diagrams have wrong or unverifiable answers. We beat it if, at matched variant count, our combined score achieves higher item-level AUROC with non-overlapping bootstrap intervals, and if it stays ahead in the post-GRPO arm.

Likelihood detectors, namely Min-K%, loss thresholding, and LiRA, are run on the answer tokens. They receive the same reference-model budget that the fragility study used. The fragility paper's 89.1% pre-RL AUROC for LiRA on text math sets the standard these detectors can reach before post-training. We expect them to fall toward chance after GRPO. Beating them means our AUROC holds within a few points across the GRPO stage while theirs does not.

Three ablations isolate the key ingredients:

  • re-layout gap alone, testing whether stickiness is needed;
  • stickiness alone, testing whether re-layout adds anything;
  • the full score with readability matching turned off, meaning unconstrained spring-layout redraws, testing whether the graph-drawing controls do real work.

If the unmatched version performs as well as the matched one, the scalability component is decoration, and we will report that.

Why not just…?

Why not just rotate or flip the original image? Rotation and flipping preserve the answer and cost nothing, which makes them the cheapest re-layout. But they preserve every relative position and every crossing, so a model that memorized visual structure may still recognize the image. They also produce no answer-flipping edit. We include rotation and flip as a re-layout family in the first ablation. If they match full re-layout, the geometric part of the audit reduces to this trivial operation, and stickiness remains the contribution.

Why not just replace the static benchmark with a dynamically generated rendered one, DyVal-style? For future evaluation, that is often the right choice, and generating fresh graphs with our layout pipeline is a natural by-product of this work. But fresh benchmarks do not tell anyone whether published scores on ProcVQA or the Ai et al. benchmark were inflated, and those are the scores people cite. DyVal's own near-zero results for phi-1.5 show that it can reveal a gap. It cannot say which items or which benchmark leaked. Our audit does exactly that.

Why not just use Min-K% or loss audits on the answer text? The fragility study shows these signals collapse under GRPO, to about 50% AUROC for many reference-free methods, and to 50–58% for reasoning models contaminated with chain-of-thought data. Whether a behavioral test survives the same treatment is an open question, not something we assume. The post-GRPO arm settles it directly. If stickiness also collapses there, that is a publishable negative result about behavioral auditing.

Why not just use the diffusion perturbation method as is? It is a real threat on easy, sparse diagrams, where a Canny-guided repaint may succeed. Diagrams, however, depend on thin lines, arrowheads, and text labels, and these are exactly where diffusion rendering is unreliable. A single wrong arrow makes a variant's ground truth wrong. The head-to-head comparison, together with the measured rate of broken diffusion variants, decides the matter.

Decisive Checks

The main experiment reports item-level and model-level AUROC across three conditions: contamination dose (0, 1, 3 epochs), benchmark (Ai et al., ProcVQA, GRAB-Lite), and post-training (none vs. GRPO). Detector weights are always fitted on a different benchmark from the one being tested.

We report results stratified by ProcVQA's density bins, to check that stickiness does not simply track density. The expected pattern is that clean models' stickiness stays low at all densities, while contaminated models' stickiness is high even on sparse diagrams.

Contamination should turn stickiness on. On the uncontaminated half of each benchmark, a contaminated model's stickiness should match the clean control's. A mismatch would mean stickiness measures a general reading bias rather than memorization.

For frontier models we report audit scores only as estimates. For reference, Gemini-2.5-Pro-Thinking's 76.6% multi-hop accuracy on ProcVQA is a published score that the audit could either support or flag, and we will state which without claiming certainty about training data.

The idea is falsified if either of two things happens: readability-matched re-layout alone causes clean models to fall as much as contaminated ones, or stickiness does no better than rotation/flip combined with likelihood detectors after GRPO.