🤖 AI

Theoria: Rewrite-Acceptability Verification over Informal Reasoning States

The paper introduces Theoria, a verification architecture that enhances AI answer trustworthiness by rewriting solutions into auditable, typed state transitions with explicit justifications, thereby outperforming holistic LLM judges in detecting hidden premises and fabricated citations while maintaining high precision on expert-level problems.

Original authors: Ben Slivinski, Michael Saldivar

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ben Slivinski, Michael Saldivar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are hiring a brilliant but sometimes overconfident architect to design a bridge. You don't just want the final blueprint; you need to know why every beam is placed where it is. If the architect says, "This beam goes here because it feels right," you can't trust the bridge. But if they say, "This beam goes here because of Law X, and here is the calculation proving it," you can check the math.

This is the problem Theoria solves for Artificial Intelligence.

The Problem: Two Flawed Ways to Trust AI

Currently, we have two main ways to check if an AI's answer is good, and both have holes:

The "Mathematician" Approach (Formal Proof Assistants): This is like hiring a robot that speaks only in strict, unbreakable mathematical code. It's perfect, but it can only understand problems that have already been translated into that code. Most real-world problems (like legal arguments or scientific theories) are messy and informal, so the robot can't read them.
The "Gut Feeling" Approach (Scalar Judges): This is like asking a human to read the AI's essay and give it a score from 1 to 10. It covers a lot of ground, but the score is a black box. You don't know why it got a 7. Did it miss a hidden assumption? Did it fake a citation? You just get a number, and you can't audit it later.

The Solution: The "State Rewriting" Detective

Theoria introduces a third way. Instead of asking the AI to write a long essay or translate everything into math code, Theoria forces the AI to rewrite its answer as a step-by-step state change log.

Think of it like a video game save file or a version control system (like Git) for reasoning.

The Setup: The AI starts with a "State 0" (the problem statement).
The Move: To get to the answer, the AI must make a move to "State 1," then "State 2," and so on.
The Rule: For every single move, the AI must provide a ticket (a justification). The ticket can only be one of three types:
1. A Citation: "I'm using Theorem X."
2. A Computation: "I did the math: 2+2=4."
3. A Given Fact: "The problem told me this."

The Magic Trick: "Completeness of Change"

Here is the secret sauce. Theoria has a strict rule: Every single change between State A and State B must be explained by the ticket.

If the AI tries to sneak in a hidden assumption (like "Assume the bridge is made of gold") without a ticket, the system catches it. The "change" (adding the gold assumption) appears in the log, but the ticket (the justification) doesn't cover it. The system screams, "Wait! You changed the state, but you didn't show us the receipt!"

This forces the AI to be honest. It can't hide a lie in a long paragraph of text; it has to show the exact moment the lie entered the conversation.

How It Works in Practice

The Solver: An AI tries to solve a problem.
The Formalizer: A second AI rewrites that solution into the "State Change Log" described above. If the solver made a jump in logic, the formalizer has to write it down as a specific step.
The Judges: Specialized AI auditors check each step.
- A "Math Judge" checks the calculations.
- A "Citation Judge" checks if the referenced theorem actually exists and applies.
- A "Fact Judge" checks if the fact was actually in the original problem.
The Verdict: If every step has a valid ticket, the answer is Certified. If even one step is missing a ticket or has a fake ticket, the answer is Declined.

What the Paper Found

The authors tested this on hard problems (like those found in expert exams) and found:

High Trust: When Theoria says an answer is correct, it is correct 91.4% of the time.
Better at Catching Sneaky Lies: When the AI tries to hide a premise (a hidden assumption) or fake a citation, Theoria catches it 90.6% of the time. A standard "gut feeling" judge only catches it 62.5% of the time.
Not Magic on Math Errors: If the AI just does simple math wrong (like saying 2+2=5), both Theoria and the standard judge catch it about the same amount of time. The special advantage of Theoria is specifically for catching hidden logic and fake sources.
Complementary: Theoria and standard judges fail on different problems. If you use both, you can catch almost all errors.

The Bottom Line

Theoria doesn't try to make the AI smarter; it tries to make the AI's reasoning auditable.

It turns a vague, untrustworthy essay into a transparent ledger of changes. It doesn't promise that every answer will be right (it declines about 43% of answers because it can't verify them), but for the answers it does approve, you can look at the receipt, check the math, and know exactly why it's safe to trust.

In a world where AI might hallucinate facts, Theoria is the system that says: "Show me the receipt for every single step, or I won't sign off on this."

Technical Summary: Theoria – Rewrite-Acceptability Verification over Informal Reasoning States

1. Problem Statement

The paper addresses the "trust problem" in AI reasoning: distinguishing when an AI-generated answer should create justified reliance, particularly in safety-critical fields (science, law, finance, medicine). Current approaches face a dichotomy:

Formal Proof Assistants (e.g., Lean, Coq): Offer mathematical certainty but fail to cover most problem distributions due to the high cost and semantic fragility of autoformalizing informal, natural-language requirements.
Scalar LLM Judges: Offer broad coverage but produce opaque scores that cannot be audited, inherit the coherence issues of LLMs, and fail to identify why a proof is flawed (e.g., hidden premises, fabricated citations).

The core challenge is to verify informal reasoning without requiring full formalization, while ensuring that errors—specifically unstated assumptions and logical leaps—are visible and auditable.

2. Methodology: The Theoria Architecture

Theoria introduces a verification architecture that rewrites a solver's natural-language answer into a proof witness: a sequence of typed state transitions.

2.1 The Rewrite Framing

Instead of treating a proof as a block of prose, Theoria decomposes it into a trajectory of states $(S_0, S_1, \dots, S_n)$ .

State ( $S_i$ ): An ordered list of strings representing established facts and the current goal.
Transition: A step from $S_{i-1}$ $S_{i - 1}$ to $S_i$ $S_{i}$ is licensed by a specific justification type:
1. Citation: A theorem, definition, or rule of inference.
2. Computation: Arithmetic or symbolic manipulation.
3. Problem Given: Facts explicitly stated in the problem text.
The Completeness-of-Change Invariant: Every semantic difference between $S_{i-1}$ and $S_i$ must be accounted for by the stated justification. If a premise is required to derive the new state but is not present in the previous state or the justification, it constitutes an unlicensed mutation.

2.2 Verification Pipeline

The system operates in a loop: Solve $\to$ Formalize $\to$ Judge $\to$ Filter $\to$ Repair.

Solver: Proposes a natural-language solution (tool-augmented, e.g., web search).
Formalizer: Rewrites the solution into the state-transition witness. It enforces that premises must be explicit before use.
Parallel Specialized Judging:
- Computation Judges: Recompute steps from scratch.
- Citation Judges: Verify the existence and applicability of cited theorems against the specific state diff.
- Problem-Given Judges: Check facts against the original text.
- Initial-State Judge: Audits $S_0$ to ensure no unjustified premises are introduced at the start.
- All judges are adversarially prompted to find errors rather than confirm plausibility.
Pedantry Filter: Distinguishes between substantive errors and over-strictness regarding informal notation or compression.
Convention Lift: Allows the system to accept a step if a standard, citable domain convention resolves a rejection, provided the assumption is explicitly recorded.
Certify-or-Decline: The system outputs a binary decision. If all steps pass (or are resolved via convention lift), the answer is Certified. If any step fails and cannot be repaired within bounds, the answer is Declined.

3. Key Contributions

The paper's primary contribution is not the use of multiple models or step-checking (which are common), but the specific witness format and its theoretical guarantees:

Exposure Guarantee (Proposition 4.4): The completeness-of-change invariant converts hidden premises (global reasoning gaps) into local, observable unlicensed mutations. A hidden premise must either appear as a new element in the state (triggering a license check) or violate the invariant. This forces errors to the surface where they can be detected by local judges.
Error-Class Predictions (Proposition 4.5): The format predicts that verification advantages will concentrate in:
- Hidden Premises: Exposed as unlicensed mutations.
- Fabricated Citations: Exposed because the evidence is explicitly typed and checked against the diff.
- No Advantage: Arithmetic errors and theorem misapplications (where the theorem exists but is misapplied) receive no structural exposure advantage over prose, as the error is semantic rather than structural.
Decomposition of Failure: The paper distinguishes between Exposure Failure (the format hides the error) and Judge Failure (the judge misses an exposed error). Theoria aims to minimize the former, leaving the latter to be addressed empirically.

4. Empirical Results

Evaluation was conducted on HLE-Verified Gold (185 expert problems) and GPQA Diamond (65 graduate-level science problems).

4.1 Performance on HLE-Verified Gold

Certified Precision: 91.4% (96/105 correct) with a 95% Wilson CI of [84.5%, 95.4%].
Coverage: 56.8% (105/185 problems certified).
Asymmetry: Declined answers were ~5.0 $\times$ more likely to be wrong than certified answers (42.5% vs. 8.6% error rate).
Comparison to Solver-Only: A web-augmented solver achieved 83.8% accuracy at 100% coverage. Theoria's pipeline filtered out a significant portion of errors, reducing the error rate in the certified bucket to 8.6%.
Comparison to Holistic Judges: Holistic LLM judges (assigning a single confidence score) achieved comparable precision (92.4–93.3%) at matched coverage. However, they failed on different problems (Jaccard index 0.14–0.36), indicating complementary error coverage.

4.2 Adversarial Robustness

On a benchmark of 95 poisoned proofs (injecting specific error types):

Overall Detection: Theoria caught 94.7% (90/95) vs. 83.2% (79/95) for holistic judging ( $p = 0.0017$ ).
Error Class Specifics:
- Hidden Premises: Theoria 90.6% vs. Holistic 62.5% (28 pp gap).
- Fabricated Citations: Theoria 100% vs. Holistic 90%.
- Arithmetic/Misapplied Theorems: Performance was identical (~95% and ~93% respectively), confirming the theoretical prediction that the format offers no structural advantage for these error types.

4.3 Out-of-Distribution (GPQA Diamond)

Certified Precision: 97.1% (33/34).
Coverage: 52.3%.
The high precision on a different benchmark suggests the "certify-or-decline" boundary is driven by the formalizability of the reasoning rather than benchmark-specific calibration.

4.4 Ensemble Potential

Because Theoria and holistic judges fail on disjoint sets of problems, ensemble strategies (e.g., majority vote) achieved 93.6% precision at 58.9% coverage, outperforming any single method.

5. Significance and Claims

The paper claims that Theoria provides a scalable oversight mechanism that bridges the gap between raw LLM output and formal verification.

Auditability: Unlike scalar scores, Theoria produces a human-readable proof trace where every step can be independently challenged.
Structural Advantage: The system does not rely on the judge reconstructing a proof from prose. Instead, it reduces the verification task to a local question: "Does this justification license this specific state change?"
Complementarity: The paper argues that Theoria is not a replacement for holistic judges but a complementary approach. The low Jaccard overlap in errors suggests that combining structurally different verification architectures yields higher reliability.
Limitations: The authors acknowledge that Theoria cannot detect errors that produce no observable state mutation (e.g., subtle misinterpretations of the problem statement in $S_0$ ) and that it currently relies on LLM judges rather than formal backends (like Lean or SMT solvers), though it is designed to be compatible with them.

In summary, Theoria demonstrates that by enforcing a completeness-of-change invariant on informal reasoning, it is possible to surface hidden assumptions and fabricated evidence that standard holistic evaluation misses, providing a rigorous, auditable boundary for trust in AI-generated reasoning.