acceptodds
Desk rejected at ICLR 2027

Counterexample Return Index: Routing Prover Compute with Validation-Measured Witness Utility

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

An executable counterexample can expose the assignment, violated literal, and dependency that break a conjecture, but extracting and minimizing that witness consumes compute that could instead train the prover or extend proof search. We introduce WitnessBudget, which turns locally corrupted conjectures into checker-confirmed, attributed repair traces, and the Counterexample Return Index (CRI), which predicts their family-level return from validation-only witness yield, probe utility, timeout, cost, and compactness. In eight family-disjoint reruns of a joint three-ecosystem training protocol, all packages start from the same Llama-3.1-70B checkpoint and receive a 512 A100-hour reservation. WitnessBudget reaches 41.70.8 on miniF2F, 34.10.9 on a ProofNet-derived Isabelle/HOL evaluation, and 56.80.6 on DafnyBench, improving over bare counterexample augmentation and witness-free active selection by 1.5–3.1 percentage points with positive paired intervals throughout. Masking the witness narrows the advantage by 0.7–1.3 points, and permutation degrades further, localizing the gain to theorem-aligned witness content. Across 43 unique test families and 344 family–rerun cells, frozen CRI predictions rank solve-rate gain with Spearman 0.77 [0.72,0.81] and identify positive end-to-end efficiency with AUROC 0.88 [0.84,0.91]. Acting on those predictions reallocates 27.2 falsifier hours to search, raises solve rate by 0.6–1.0 points, and improves end-to-end throughput by 1.6–2.2%, while random, difficulty-only, and yield-only gates trail the joint index.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
foundational causal formal and efficient methods, Counterexample Return Index

Related papers

Discussion (0)

Sign in to comment.