Neurosymbolic systems lean on mathematical solvers to guarantee correctness, but a new paper argues that solvers cannot tell whether a formal translation is truly equivalent to its intended reference formalization. The authors call this failure mode Verdict-Preserving-Unfaithfulness (VPU): an incorrect encoding runs successfully and produces the expected verdict.
According to the paper, the problem is not merely empirical. The authors prove theoretically that structural, verdict-only verification heuristics are mathematically bounded to chance-level detection on these deceptively valid traces.
To address it, they introduce Generative Verification (GenV), which distills an offline Z3-equivalence oracle into a reference-free, continuous reference-equivalence score by repurposing the language model's native vocabulary space. Mechanistic analysis using decision-projected logit lenses and sparse autoencoders indicates the generative readout extracts precise spatial error coordinates without explicit localization training.
Empirically, the oracle-mined verifier (GenV+HN) reaches 0.961 AUROC in reference-equivalence verification, generalizes zero-shot across unseen translators and divergent formal styles, and delivers an 11.3-point downstream accuracy gain in agentic test-time compute allocation.