A benchmark score can be inflated in two ways. The model may have seen the answer key during training, which is contamination. Or the grading pipeline may be wrong: a mislabeled item, a buggy scorer, or a host whose private test set nobody can inspect. Formal verification has a standard remedy for the second problem, called minimizing the trusted computing base, meaning the small core of code that must be correct for a result to be believed. The heavy, untrusted machinery that searches for an answer must also emit a certificate, a piece of evidence that a tiny, independently verified checker can validate. This note proposes applying that discipline to LLM evaluation. The model no longer just says "unsatisfiable" or "the probability is at least 0.8". It must output a certificate for that claim, and a small verified checker grades it. The benchmark then has no answer key at all, so there is nothing to leak into a web crawl, and anyone can re-grade any submission.
The central empirical claim is testable. Contamination as it usually happens leaks answer labels, and certificate grading makes that kind of leakage worthless, while ordinary label grading rewards it fully. We will show this with controlled contamination experiments on open models, in two domains where compact certificates already exist. The first is Boolean satisfiability, where a claim of "no solution" is backed by a refutation checked by clause-level propagation. The second is reachability in Markov decision processes, where a claimed probability bound is backed by a vector of values that must satisfy Bellman inequalities. We will then measure how much of frontier models' reported accuracy on public reasoning items survives when certificates are required.
Core Claim
Current contamination-resistant benchmarks secure freshness: they make sure the model cannot have seen the items. They still grade answers against a label. This proposal secures what counts as a correct answer: credit requires evidence that a small checker accepts. The two properties are separable, and the second has been missing. It carries three consequences that freshness alone does not give. A leaked label cannot buy credit. A model that guesses by a surface heuristic gets no credit even when the guess happens to be right. And the evaluation's correctness depends only on the checker and the instance statement, not on the generator, the labeling solver, or the host.
Relation to Prior Work
The work that motivates this proposal found gaps on both sides. Can Large Language Models Reason? A Characterization via 3-SAT generates random 3-SAT formulas across the hardness phase transition. It finds GPT-4's search accuracy falls to roughly 10% near the critical constraint ratio, and that models are biased toward answering "Unsatisfiable" on longer prompts. That bias is exactly the kind of label-level shortcut a decision-only grader rewards half the time. DyVal generates reasoning instances from random graphs and reports that 33.8% of GPT-4's failures were "unsubstantiated responses", answers given without checkable deductions. A²RBench generates abstract-reasoning tasks whose validity is tested by running a forward and inverse Python function. It detects memorization through symbol remapping, a 17.7% drop, but its correctness rests on an unverified Python runtime and on inputs that were only sampled. All three secure freshness. All three still grade answers against labels produced by trusted but unverified code.
The closest work is P⁴Bench. It publishes SAT and discrete-log problems together with arithmetic circuits that check a solution, and the model provider proves in zero knowledge that it knows a satisfying witness. That is already answer-key-free for the "yes" side of a search problem, because a satisfying assignment is its own certificate. We differ in three ways. First, we require certificates for negative and quantitative claims: unsatisfiability, and upper and lower bounds on probabilities. These are the claims where label grading must trust a solver and where Hazra et al. found shortcut bias. Second, we use existing verified checkers rather than cryptographic circuits. Third, we do not attempt P⁴Bench's privacy goal; we target the contamination-accounting question it leaves unmeasured.
The certificate machinery itself comes from the verification literature. DRAT Proofs of Unsatisfiability for SAT Modulo Monotonic Theories translates theory reasoning into standard propositional refutations so that existing verified checkers such as drat-trim suffice, without new trusted code. We reuse that "don't grow the checker" principle. Fixed Point Certificates for Reachability and Expected Rewards in MDPs has model checkers emit Bellman-inequality certificates with ranking functions, checked by an Isabelle-verified checker. It covered 396 of 447 benchmark models and checked 100,000-state models in seconds. We reuse this certificate format directly as the answer format for LLMs.
Two papers constrain the design. miniF2F-Lean Revisited shows that the statement is also part of what must be trusted. Over half its problems leaked the answer into the theorem statement, and 16 were unprovable. An Auditable Harness for AI-Assisted Lean Formalization shows that a passing proof check can coexist with a tampered statement. So we generate instance statements deterministically from a seed, and the checker takes the statement from the seed, never from the model's output.
Research Program
We will build a small evaluation harness with three parts. The first part generates instances deterministically from a published seed: random 3-SAT formulas across the constraint-to-variable ratio, at sizes up to roughly 10 to 20 variables, and small random MDPs of 5 to 30 states with reachability thresholds. The second part is a prompt contract that asks the model for a verdict plus a certificate. For satisfiable formulas the certificate is an assignment. For unsatisfiable formulas it is a sequence of learned clauses, each derivable by unit propagation, ending in the empty clause. For MDPs it is a value vector and a ranking function that bound the probability from the claimed side. The third part is the checker: drat-trim for refutations and the Isabelle-extracted checker for MDP certificates. The instance-to-checker path is the only trusted code.
We will also write an explicit trust accounting for each competing evaluation pipeline. It lists which components must be correct for a reported score to be believed: generator, labeling solver, scorer, host, statement. For each component we report line counts where these can be measured.
The scientific core is a set of controlled contamination experiments. We take open models in the 7–8B range, as used in FOVER. We fine-tune them on a subset of instances at several repetition counts, under three leakage regimes: labels only, labels with worked certificates, and none. We then measure label accuracy and certified accuracy on the leaked items, on the same items after seeded variable renaming and clause shuffling, and on fresh items from the same distribution. For frontier API models, where we cannot control training, we compare public, previously released instance sets with freshly generated items from the same distribution. The quantity of interest is the gap between label accuracy and certified accuracy, and how that gap differs between the two sets.
Baselines
The naive reference point is answer-only evaluation with solver-computed labels on the same instances, which is the protocol of Hazra et al. For this setting the file reports GPT-4 SAT-Search accuracy of "roughly 10%" at the phase transition, and "nearly 100%" when GPT-4 translates the formula for MiniSAT to solve (Can Large Language Models Reason?). We will reproduce the label-graded numbers on our own freshly seeded instances with identical prompts, models, and sampling budgets, so that only the grading rule differs.
The strongest existing competitor is witness-checked grading in the style of P⁴Bench. It checks satisfying assignments exactly, but negative claims can only be graded against a solver label. The file reports Qwen 3.5 Plus at 99.6% SAT accuracy on P⁴Bench. We implement its grading rule without the zero-knowledge layer, which does not affect scores, on our instances. Certificate grading "beats" it if two things hold under label-only contamination. First, certificate grading keeps certified accuracy on leaked unsatisfiable and MDP-bound items within noise of the fresh-item level. Second, the witness-plus-label rule shows measurable inflation on those same items.
The strongest existing contamination probe is A²RBench-style symbol remapping, which reports a 17.7% drop. We apply it as a renaming condition to both graders, to test whether certificate grading gives the same contamination signal without needing a remapped copy.
Three ablations isolate the proposal's key ingredients. The first requests certificates in the prompt but grades only the verdict, which separates the effect of asking for evidence from the effect of checking it. The second replaces the verified checker with a hand-written Python checker. This isolates what the minimal trusted base contributes; we expect score parity on honest submissions, but we will adversarially fine-tune a model to emit malformed certificates and count how many the Python checker wrongly accepts. The third lets the model call a SAT solver. This measures how much of certified accuracy is tool-mediated, which the grader correctly cannot tell apart.
Why not just…?
Why not just generate fresh instances and grade against solver labels? This is the real threat, and for purely fresh items it may produce the same model rankings. Freshness removes memorized items, and a correct solver gives correct labels. Freshness does not remove label-level heuristics, though. Hazra et al.'s length-driven "Unsatisfiable" bias is credited on every item where it happens to be right. A statistical guessing correction assumes guesses are uniform, which that bias contradicts. Freshness also requires the host to keep generating, and it keeps the generator and solver in the trusted base. The experiment that settles this is the fresh-item comparison. If label and certified accuracy rank models identically, and the per-item disagreement is small, we will report that the gain on fresh data is auditability and not measurement. The contamination experiment on reusable, published items would then carry the claim.
Why not just detect contamination with perplexity or membership tests? Token-level surprise analyses (Studying and improving reasoning in humans and machines) and frequency correlations (Snoopy) flag suspected leakage but do not repair the score. They also need access to model internals that API models do not give. Certificate grading neutralizes label leakage without detecting it. We will run surprise-based detection on the fine-tuned open models as a comparison, to see whether it tracks the label-minus-certified gap.
Why not just have an LLM judge check the reasoning trace? On miniF2F-Lean Revisited, an LLM judge rated a translator at 97.5% where humans found 62.7%. HorizonMath needed an LLM compliance judge because models gamed its numerical checks, which puts unverified heuristics into the grading core. We include an LLM judge as a grader on the contaminated models and measure its false-accept rate against the verified checker.
Why not just keep the test set private? A private set moves trust to the host. P⁴Bench is motivated precisely by third parties being unable to audit private grading. An answer-key-free benchmark can be fully public, because what leaks is only statements, which were never the secret.
Proposed Experiments
The decisive experiment is the three-regime contamination study. The prediction is specific. Label-only leakage should push label accuracy on leaked items toward the repetition ceiling while leaving certified accuracy at the fresh-item level. Certificate leakage should inflate certified accuracy on exact leaked items but largely not on renamed variants. The claim is falsified if certified accuracy rises substantially under label-only leakage, which would mean models convert memorized labels into valid refutations, or if the renamed variants inflate as much as the exact items.
The second experiment reports label accuracy and certified accuracy for frontier models across the SAT phase transition and across MDP sizes. It separates satisfiable, unsatisfiable, and bound-claim items, and compares public released instance sets with fresh ones. It should show where decision-only accuracy is carried by unverifiable "no" answers.
The third experiment is the adversarial checker ablation. It reports the rate at which invalid certificates pass the unverified Python checker versus the verified checkers. For the Isabelle checker, the file reports verification on 396 of 447 standard models (Fixed Point Certificates); there is no reported LLM-generated-certificate result found on Lacuna, so that number will be new. Cost is reported throughout as certificate length and checking time per item. Refutation size grows quickly with variable count, and the usable size range is itself a finding.
References
- Can Large Language Models Reason? A Characterization via 3-SAT
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- A²RBench: An Automatic Paradigm for Formally Verifiable Abstract Reasoning Benchmark Generation
- $\text{P}^4$Bench: Contamination-Proof, Publicly Verifiable, and Privacy-Preserving LLM Evaluation via Zero-Knowledge Proofs
- DRAT Proofs of Unsatisfiability for SAT Modulo Monotonic Theories
- Fixed Point Certificates for Reachability and Expected Rewards in MDPs
- miniF2F-Lean Revisited: Reviewing Limitations and Charting a Path Forward
- An Auditable Harness for AI-Assisted Lean Formalization: Pilot Logs from Finite Differential Privacy
- Efficient PRM Training Data Synthesis via Formal Verification
- Studying and improving reasoning in humans and machines
- Snoopy: An Online Interface for Exploring the Effect of Pretraining Term Frequencies on Few-Shot LM Performance
- Measuring Progress in Reasoning Toward Mathematical Discovery with Automatic Verification