Theoria: Rewrite-Acceptability Verification over Informal Reasoning States

Source: arXiv:2607.01223 · Published 2026-07-01 · By Ben Slivinski, Michael Saldivar

TL;DR

Theoria addresses the critical problem of verifying AI system reasoning in informal, natural-language domains where formal proof assistants struggle and scalar LLM judges provide opaque, non-auditable scores. It introduces a novel verification architecture that rewrites candidate solutions into sequences of typed state transitions accompanied by explicit justifications (citations, computations, or problem-given facts). Each transition is independently auditable with a foundational completeness-of-change invariant ensuring every difference between states is accounted for, exposing hidden premises or unjustified steps as local, licensed change violations. Empirically, Theoria achieves 91.4% strict precision certifying 105 of 185 expert problems on the HLE-Verified Gold benchmark, producing human-readable proof traces. It surpasses holistic LLM judges on adversarially poisoned proofs by 11.5 percentage points, particularly excelling in catching hidden premises and fabricated citations, confirming theoretical predictions about error class advantages. On an out-of-distribution GPQA Diamond dataset, precision climbs to 97.1%. Theoria thus bridges the gap between brittle formal proof assistants and non-transparent LLM scorers by producing structured, auditable witnesses that support scalable oversight and abstention rather than opaque confidence scores.

Key findings

• Theoria certifies 105 out of 185 HLE-Verified Gold text-only problems with 91.4% strict precision (95% Wilson CI [84.5%, 95.4%]) and 100% favorable precision (disputed but defensible answers included).
• Coverage is 56.8%, with certified buckets ≈5× more likely to be correct than declined buckets (8.6% vs. 42.5% strict error rates).
• Compared to raw solver baseline (web-augmented LLM) at 83.8% accuracy, Theoria's certified answers reduce error from 16.2% overall to 8.6%, halving error rate at 57% coverage.
• At matched coverage (105 certified answers), Theoria's precision (91.4%) is comparable (within statistical insignificance) to holistic LLM judges: Claude Opus (92.4%) and Codex (93.3%) but Theoria's certified sets differ substantially in composition (Jaccard 0.14-0.36).
• On 95 adversarial poisoned proofs across 15 domains, structured judges catch 94.7% of errors, outperforming holistic judging at 83.2% (p=0.0017).
• The precision gain on adversarial inputs concentrates on hidden premises (90.6% vs. 62.5%, +28 points) and fabricated citations (100% vs. 90%), error classes predicted by the theoretical framework; no advantage on arithmetic or theorem misapplication errors.
• On GPQA Diamond dataset (n=65), Theoria achieves 97.1% certified precision (95% Wilson CI [85.1%, 99.5%]).
• Decline rate by Theoria is ~43%, enforcing an explicit abstain mechanism in contrast to holistic judges that decline far less (20%).

Threat model

The adversary is a natural-language reasoning solver that may produce answers with hidden, unstated premises, fabricated citations, unjustified computations, or semantic errors. The adversary cannot alter the problem statement, and the verification system has access to the full proposed proof witness, decomposed into typed steps with explicit justifications. The judges are strong LLM ensembles instructed adversarially to find errors but cannot detect errors that produce no observable mutation in the proof witness or subtle semantic shifts in problem interpretation. The system assumes no perfect oracle; the goal is to reduce exposure failures by converting global hidden assumptions into local licensed-change violations.

Methodology — deep read

Theoria’s methodology involves several key components and steps:

1. Threat Model and Assumptions: The adversary is an AI reasoner that produces informal proofs possibly containing hidden premises, fabricated citations, or unjustified computations. The system assumes the problem statements are correct, and focuses on detection of reasoning errors via local verification steps. The judge is a strong LLM ensemble acting adversarially (prompted to find errors, aware of hallucination).

2. Data: The main benchmark is HLE-Verified Gold, a curated set of 185 text-only expert problems spanning math, science, humanities, and other domains. The data includes problem statements, solver-generated answers, and human grading labels for correctness. GPQA Diamond (n=65) tests out-of-distribution generalization. 95 adversarially poisoned proofs in 15 domains simulate attack scenarios. Grading is done by multiple independent LLM graders with high inter-rater agreement (~99.46%).

3. Architecture and Algorithm: Theoria reformulates a solver’s answer as a sequence of typed state transitions. Each step is a tuple (Si, τi, ei) with Si the new state (an ordered list of derived facts/claims), τi a justification type (citation, computation, or problem given), and ei the evidence supporting the step. The core invariant is completeness-of-change: every semantic change between Si-1 and Si must be fully accounted for by the justification. A violation indicates hidden premises or unjustified assumptions.

States start at S0 containing only given facts; subsequent states add, remove or strengthen claims, each mutation checked against the justification license sets. There are specialized LLM-based judges: a computation judge redoes arithmetic and algebraic steps; a citation judge verifies existence and applicability of referenced theorems or laws; a problem-given judge checks consistency with problem statements; an initial state judge audits S0 separately. Judges operate in parallel on each step’s local diff and justification, focusing narrowly on error detection instead of global correctness likelihood.

4. Training Regime: Theoria’s core is a system pipeline that combines solver, formalizer, judges, pedantry filter, convention lift, and a certify-or-decline decision process with bounded repair attempts if evidence is rejected. The system itself does not train neural components end-to-end but uses pretrained LLMs with carefully engineered prompting (adversarial prompt design to detect hallucinations/errors).

5. Evaluation Protocol: Precision, coverage, and certified-versus-declined asymmetry are measured. Multiple baselines include raw solver accuracy, holistic judges scoring entire reasoning chains with scalar confidence, and adversarially poisoned proofs to test robustness. Both strict and favorable precision (allowing defensible variations) are reported with Wilson confidence intervals. Statistical significance tests such as McNemar and Fisher exact tests quantify differences. Error overlap analysis examines complementarity of structured vs holistic judgments.

6. Reproducibility: The authors provide a committed SQL audit database to reproduce all reported numbers. The system code and formalizer are open sourced at github.com/zaladbar/theoria. Datasets like HLE-Verified Gold and GPQA Diamond are referenced from recent public academic releases (HLE-Verified from Zhai et al., 2026, GPQA Diamond from prior work). Some problem sets are restricted but benchmark protocols are described in detail.

A concrete example: Given a math problem, the solver outputs a natural language solution. The formalizer decomposes it into an initial state S0 (stating known assumptions and the goal) and a sequence of states adding claims validated by citations (e.g., theorem references), computations (arithmetic simplifications), or problem givens. Each change is audited by specialized judges in parallel. If all pass, the answer is certified with a detailed proof trace exposing all premises and justifications. If any judge rejects, the system declines the answer or attempts bounded repair by prompting the formalizer or solver again. This structured verification pipeline converts opaque natural language reasoning into auditable, justifiable proof witnesses.

Technical innovations

• Introduction of a state-rewrite proof witness format over informal reasoning states enforcing a completeness-of-change invariant to expose hidden premises as unlicensed mutations.
• Typed justifications for each proof step limited to citation, computation, or problem-given fact, enabling specialized parallel LLM judges focused on local licensing questions instead of holistic scoring.
• Adversarial prompt design instructing judges to actively search for hallucinations and unjustified steps rather than assign global confidence, improving error detection precision.
• A pedantry filter and convention lift mechanism that distinguish substantive errors from overstrict formalism and allow domain-specific conventions to be explicitly introduced and audited.
• A certify-or-decline output paradigm producing human-readable proof traces with independently challengeable steps, enabling explicit abstention and trust calibration.

Datasets

• HLE-Verified Gold — 185 problems — expert-curated subset of Humanity’s Last Exam benchmark
• GPQA Diamond — 65 problems — out-of-distribution reasoning benchmark
• Adversarial poisoned proofs — 95 problems across 15 domains — crafted test for robustness

Baselines vs proposed

• Solver-only baseline: accuracy = 83.8% vs Theoria certified precision = 91.4% at 56.8% coverage
• Holistic judge Claude Opus (top 105): strict precision = 92.4% vs Theoria = 91.4%; statistically insignificant difference
• Holistic judge Codex (top 105): strict precision = 93.3% vs Theoria = 91.4%; statistically insignificant difference
• Holistic judge Opus with abstention: coverage = 80%, precision = 90.5%, errors shipped = 14 vs Theoria 9 errors at 56.8% coverage
• Adversarial poisoned proofs detection: structured judges 94.7% detection rate vs holistic judges 83.2% (p=0.0017)
• Error-class breakdown on adversarial poisoned proofs: hidden premises detected 90.6% vs 62.5%, fabricated citations 100% vs 90%, arithmetic and theorem misapplication equal

Limitations

• Coverage limited to 56.8% of problems; Theoria declines 43% of cases rather than certifying, so usable only when abstention is tolerable.
• Initial state S0 audit cannot guarantee detection of subtle misinterpretations or semantic shifts in problem understanding.
• Method relies heavily on LLMs as adjudicators, which remain imperfect and may share blind spots in judging complex justifications.
• No evaluation on fully formalized problems or comparison with state-of-the-art autoformalizers on formal verification tasks.
• Error detection advantage is limited to hidden premises and fabricated citations; no visibility improvement for arithmetic errors or theorem misapplication.
• Evaluation datasets are curated expert problems and artificially poisoned inputs; real-world distributions may differ.
• System depends on well-engineered prompt design and formalizer accuracy; introducing premise errors during rewrite could cause false declines.

Open questions / follow-ons

• How can Theoria’s witness format and verification pipeline integrate with and support downstream formal proof assistants for autoformalization?
• Can the approach extend to reasoning over multimodal or non-textual data beyond text-only math and science problems?
• How might training dedicated judge models or augmenting with symbolic verifiers reduce judge failure and further increase detection rates?
• What are the tradeoffs in coverage and precision when scaling Theoria to more ambiguous or noisy real-world natural-language tasks outside expert curated benchmarks?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, Theoria presents an innovative framework for verifiable reasoning over informal AI outputs that balances auditability with coverage. Unlike scalar confidence scores from holistic judgment models, Theoria’s approach produces structured, stepwise proof traces with explicit justifications, enabling fine-grained independent validation of each reasoning step. This architecture could inspire CAPTCHA challenge designs that require explicit, justifiable state transitions with well-defined licenses, making automation by bots requiring hidden assumptions easier to detect. The completeness-of-change invariant serves as a powerful principle to ensure that every transformation in an interactive CAPTCHA challenge is accounted for, preventing silent shortcuts or fake evidence. Moreover, Theoria’s certify-or-decline paradigm aligns well with abstention policies crucial in security-sensitive settings, where uncertain answers should trigger fallback or human intervention. Although Theoria targets complex reasoning verification, its principles could inform the design of CAPTCHA tasks that require transparent multi-step reasoning with verifiable premises and explicit citation of challenge context, increasing robustness against large language model assisted automation.

Cite

@article{arxiv2607_01223,
  title={ Theoria: Rewrite-Acceptability Verification over Informal Reasoning States },
  author={ Ben Slivinski and Michael Saldivar },
  journal={arXiv preprint arXiv:2607.01223},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.01223}
}

Read the full paper

• arXiv:2607.01223 (abstract)
• arXiv:2607.01223 (PDF)