Critiques That Must Carry a Counterexample: Auditing and Constraining Rationalization in Formal Specification Repair

Language models are now routinely used to turn plain-English requirements into formal specifications. These include planning domains written in PDDL (the Planning Domain Definition Language, which classical planners read) and pre- and postcondition contracts in the Lean 4 theorem prover. A checker then runs on the result: VAL for PDDL, the Lean compiler for contracts. The best systems do not stop after one attempt. They loop. A "critic" model reads the checker's error and writes a natural-language diagnosis, and a "learner" model rewrites the specification based on it. The strongest PDDL results come from this design. The unexamined problem is that the diagnosis is exactly the kind of text that research on post-hoc rationalization, meaning explanations written after the fact that do not reflect what actually drove a model's output, shows to be unreliable. When the checker only confirms that a specification compiles and is solvable, a plausible but wrong diagnosis can steer the loop toward a specification that passes by quietly dropping what the user asked for.

We propose to measure this failure and then close it with one rule. A critique may reach the learner only if it comes with a concrete witness, a specific input and output pair or a specific state and action sequence, together with a claim about what the current specification does with that witness. The checker executes the claim before the learner sees it. The diagnosis thus becomes two separate parts. One is a statement about the specification's behavior, which the machine checks. The other is a judgment about intent on a single concrete example, which is much easier for a model than an abstract judgment about whether a whole specification is correct. Critiques whose claim about behavior is false are discarded.

Core Claim

In iterative formal translation, much of the plateau and "thrashing" (repeated edits that make no progress) comes from critiques whose stated cause of failure is false. Relatedly, some loops converge on specifications that are vacuous, or satisfied too easily, rather than faithful to the requirements. Requiring every critique to include a witness the checker can verify should raise final semantic correctness at equal token budget. It should also reduce the drift toward weakened specifications.

The claim is falsifiable in two ways. The measurement could show that critiques are mostly faithful already. Alternatively, the constraint could turn out to be no better than spending the same compute on independent samples.

Grounding in Prior Work

Several papers supply the loop we study. Generating Symbolic World Models via Test-time Scaling of Large Language Models generates PDDL domains with best-of-N sampling and then refines them. Its optimizer model writes "verbalized gradients," natural-language critiques that a second model uses to repair the domain. It reaches 85.2% on NL2Domain with Qwen2.5-Coder-7B. The authors state that VAL cannot confirm the domain matches the user's intent, and they never audit whether the critiques are true.

VERINA: Benchmarking Verifiable Code Generation provides the Lean benchmark (dataset, code). It also constrains our expectations. Sixty-four rounds of compiler feedback lift proof success only to about 20%, with models looping and hallucinating lemmas. That is direct evidence that more rounds of unstructured feedback do not fix the problem.

Intent-aligned Formal Specification Synthesis via Traceable Refinement (VERISPECGEN) is the closest existing method. It splits requirements into atomic clauses, generates tests for each clause, and traces failures back to individual clauses, reaching 86.6% on VERINA SpecGen with Claude Opus 4.5. Its tests, however, are labeled by an executable reference implementation. In the 11.6% of cases where Lean's automated check times out, it falls back to an unverified model-as-judge. Our proposal needs no reference implementation. It verifies the critic's own claims rather than tests derived from an oracle.

The motivation comes from the rationalization literature. How Likely Do LLMs with CoT Mimic Human Reasoning? swaps reasoning steps for counterfactual ones and finds that answers often do not depend on the stated reasoning. GPT-4 is correct despite wrong steps 74.4% of the time in 6-digit addition. On the Hardness of Faithful Chain-of-Thought Reasoning in Large Language Models measures faithfulness by "early answering," checking how the answer probability changes as reasoning is cut short. It finds that stronger models are often less faithful, and that interventions to enforce faithfulness can cost up to 20% accuracy. Can Aha Moments Be Fake? Identifying True and Decorative Thinking Steps in Chain-of-Thought finds that most reasoning steps are decorative. None of these studies looks at critiques inside a feedback loop, where an unfaithful explanation is passed to a second model and acted on.

The accuracy penalty reported by Tanneru et al. is a constraint on our design. It is why we do not retrain the critic to be faithful. Instead we filter its outputs with a symbolic check, which leaves the model's weights untouched.

FaiRR: Faithful and Robust Deductive Reasoning over Natural Language shows that restricting a generator's input to selected premises makes each step causal by design. The idea of forcing a step to depend on something checkable comes from there. FaiRR, however, handles only Horn-clause deduction (simple if-then rules) and has no execution feedback. SlopCodeBench: Measuring Code Erosion Under Iterative Specification Refinement shows that iterative agent edits erode code structure even while tests pass, with structural erosion rising in 77% of trajectories. Our drift measurement is the formal-logic counterpart: specifications that remain valid while becoming weaker.

Research Program

The work has three stages.

Stage 1: audit the critiques. On VERINA SpecGen and NL2Domain, we run a reimplemented critic and learner loop and log every critique. Each critique is parsed into a blamed element (a Lean clause or a PDDL action's precondition or effect) and an asserted defect.

We then run two causal tests.

The first test asks whether the diagnosis is true. We apply the minimal edit the critique implies to the blamed element and check whether the checker's verdict, or the result of VERINA's ground-truth equivalence and property tests, changes as the critique predicts. A critique counts as true only if its predicted effect occurs.

The second test asks whether the learner actually uses the critique. Following the counterfactual-substitution approach of Bao et al., we replace each critique with a critique taken from a different failure, with the raw error alone, or with nothing. We then estimate the average treatment effect on repair success, that is, the difference in success with and without the real critique.

Crossing the two tests gives four categories of loop step:

Learner follows the critique Learner ignores the critique
Critique is true Useful Wasted
Critique is false Harmful Decorative

We test whether the share of harmful steps predicts thrashing and plateaus.

Stage 2: measure drift. For every iteration, we measure how strict the specification is against VERINA's ground-truth tests. On negative tests, a faithful spec should reject wrong input-output pairs, so we track how many of those it wrongly accepts. On positive tests, it should accept correct pairs, so we track how many of those it wrongly rejects.

For PDDL, we check two things. First, whether generated plans remain valid in the reference domain. Second, whether the generated domain permits plans that the reference forbids.

A trajectory counts as vacuous drift if it passes the checker while the rate of wrongly accepted negative tests rises from an earlier iteration.

Stage 3: witness-backed critiques. The critic must now output three things:

  1. A witness. In Lean this is a concrete input and output. In PDDL it is a state and an action sequence.
  2. A behavioral claim, such as "the current postcondition rejects this pair" or "this sequence is executable in the current domain."
  3. An intent verdict, stating whether the witness should be accepted according to the English requirement.

The behavioral claim is checked mechanically. For Lean, we evaluate the decidable precondition and postcondition on the concrete values. For PDDL, we simulate the sequence with VAL. Critiques with false claims are dropped, and the critic is asked again, within a fixed budget.

Accepted witnesses are kept in a growing regression suite. A later repair is rejected if it flips the verdict on any earlier accepted witness. This is our guard against drift, and it needs no reference implementation.

The intent verdict remains a model judgment, so its accuracy is itself something we measure. On VERINA we can score it against the ground truth.

Baselines

The first reference point is doing nothing. This means one-shot translation, and separately raw error re-prompting with no critic. For the raw re-prompting condition, the learner sees only the checker's output for the same number of rounds. VERINA reports that on SpecGen, o3 reaches 52.3% pass@1 with single-shot generation. That is the no-refinement reference, and we will rerun it with our own models.

The second baseline is critique-driven refinement as in Generating Symbolic World Models via Test-time Scaling of Large Language Models. We reimplement best-of-N initialization plus verbalized-gradient refinement with the same critic and learner models as our method. It is the strongest competitor on PDDL, reported at 85.2% success on NL2Domain with Qwen2.5-Coder-7B. Beating it means higher semantic correctness against the reference domains, not just higher VAL pass rate, at a matched token budget.

The third baseline is VERISPECGEN (Intent-aligned Formal Specification Synthesis via Traceable Refinement). It is the strongest competitor on Lean, reported at 86.6% on VERINA SpecGen with Claude Opus 4.5. We will likely not match that model. We will therefore run VERISPECGEN and our method on the same open-weight model (the Qwen3-30B class the paper reports large gains for) under identical budgets. We run it in two settings. In the first, VERISPECGEN keeps its reference implementation. In the second, oracle-free setting, its tests must be labeled by the model itself. Beating it in the oracle-free setting is the main target. Matching it in the oracle setting without using the oracle would also be a meaningful result.

We also run two ablations to isolate the key ingredient. In the first, the critic outputs witnesses but no checker filtering is applied. This separates the effect of simply asking for a concrete example from the effect of verifying the claim. In the second, filtering is applied but the regression suite is removed. This isolates the drift guard.

All conditions share the same models, prompts where applicable, total generated-token cap, and number of repair rounds. Each condition gets the same small tuning budget on a held-out split.

Why not just…?

Why not just spend the budget on more independent samples? Best-of-N is cheap, and the PDDL paper already shows it helps. If filtered critiques only work by discarding bad attempts, matched-compute best-of-N should equal them. We will run best-of-N at the exact token cost of our method. If it matches us on semantic correctness, the claim that critique faithfulness matters is refuted, and we would report that.

Why not just use VERISPECGEN's traceability? This is a real threat whenever a reference implementation exists. Traceable tests already localize failures well, and our method may add little on top of them. Our case rests on the oracle-free setting and on the 11.6% of cases that time out and fall back to an unverified judge. The two-setting comparison above settles this question directly, and we will state the result either way.

Why not just ask an LLM judge whether the final spec matches intent? A judge is another explainer of the same type the rationalization literature distrusts. Stronger models are, if anything, less faithful (On the Hardness of Faithful Chain-of-Thought Reasoning in Large Language Models). We include a judge-gated variant, which accepts a repair only when the judge approves. We score it against ground truth to show whether a judgment on a whole specification is less reliable than a judgment on a single concrete witness.

Why not just fine-tune the critic to be faithful, as FRIT does? FRIT: Using Causal Importance to Improve Chain-of-Thought Faithfulness trains on pairs of faithful and unfaithful steps and gains accuracy on GSM8K. But Tanneru et al. report accuracy losses from faithfulness training. Formal-language training data is also scarce. Filtering at inference time avoids both problems. We treat FRIT-style training on our audited critiques as a follow-up, not as a competitor we can dismiss.

Proposed Experiments

The benchmarks are VERINA SpecGen (189 Lean tasks) and NL2Domain together with the IPC domains Barman, Tyreworld, and Termes. The primary metrics are three: semantic correctness (VERINA's equivalence and property tests; plan validity against the reference domain), the vacuous-drift rate, and tokens spent until success.

The first decisive check is the Stage 1 correlation. If harmful steps, meaning false critiques that the learner follows, account for little of the failed trajectories, then the premise is wrong and Stage 3 is unmotivated.

The second is the matched-compute comparison between witness-backed critiques and best-of-N.

The third is drift. Under the plain critique loop, we expect the rate of wrongly accepted negative tests to rise over iterations in a noticeable fraction of trajectories that pass the checker. We expect the regression suite to suppress this rise.

The fourth is a transfer check on Termes, where direct planning with o1-preview reportedly scored 5%. This tests whether witness filtering still helps when the domain is complex enough that the critic's intent verdicts themselves become unreliable. We will measure that reliability directly against the reference domain.