Certifiability Gaps as Ground Truth for Post-Hoc Rationalization

When a language model writes out step-by-step reasoning and then gives an answer, we usually cannot tell whether the reasoning produced the answer or was written afterward to justify it. Writing it afterward is called post-hoc rationalization. Every current test of faithfulness (whether the written reasoning actually drove the answer) is a heuristic. Researchers truncate the reasoning, corrupt a step, or ask another model to judge, and none of these has a ground-truth label to be checked against. We propose to build that ground truth from a field that has been asking a precise version of the question for decades. That field is lower bounds for semidefinite programming (SDP): optimization over matrices constrained to have no negative eigenvalues, which is the strongest general tool for proving bounds on hard combinatorial problems such as Max Cut, maximum independent set and 3-SAT. Its theory tells us exactly when a bound is true but cannot be proven by any short convex certificate. A certificate here means a short, checkable argument, such as a weighted sum of constraints or a set of cliques covering a graph. On small instances, standard solvers tell us the same thing directly.

The idea is to give a model small combinatorial instances whose true answer we know by brute force. We also compute, for each instance, whether a short certificate of that answer exists at each level of a hierarchy of proof systems. Instances are then paired so that they look statistically identical: same size, same edge or clause density, same degree profile. Within each pair, one instance has a short certificate for its correct answer and the other has none, even though the answer is still true. If the model's reasoning is load-bearing, its accuracy and confidence should drop on the uncertifiable twin, or its reasoning should visibly switch to a different strategy. If accuracy and confidence are unchanged while the written trace still presents a short proof, then the trace cannot be what produced the answer: the proof it claims to give does not exist. This gives instance-level labels for post-hoc rationalization that come from mathematics rather than human annotators.

Core Claim

Certifiability-matched pairs yield faithfulness labels that are exact relative to a stated proof system. With these labels we can measure three things that current methods cannot: how much of a model's accuracy on hard instances is unsupported by any derivation it could have written, whether existing faithfulness detectors actually flag these cases, and whether training against a certificate checker moves the model from asserting answers to declining to certify them.

The plan rests on three results from the SDP side. Lower bounds on the size of semidefinite programming relaxations shows that for constraint satisfaction problems, no SDP of polynomial size beats constant-degree sum-of-squares relaxations (a standard hierarchy of SDP proof systems). It also shows that Cut, TSP and Stable Set need SDPs of dimension at least $2^{n^\delta}$. This is why the gap instances are not an artifact of a certificate language we happened to pick: certifiability failures at low sum-of-squares degree are, asymptotically, failures for every small convex certificate. Extended Formulation Lower Bounds for Refuting Random CSPs proves that random 3-SAT has a regime where unsatisfiability is typical but convex refutation is impossible. In that regime, a model can be right about "unsatisfiable" only by guessing from density. Finally, Irreducible Infeasible Subsystems of Semidefinite Systems characterizes the minimal sets of constraints that already contradict each other, called irreducible infeasible subsystems. For linear systems these correspond exactly to extreme points of the dual "alternative" polyhedron, but for SDPs the correspondence holds in one direction only. We use this to define, for each refutable instance, its minimal reasons. A faithful trace should cite them.

These theorems are asymptotic, and at the small sizes we use everything could in principle be brute-forced. We therefore never rely on the theorems for labels. Labels come from explicit computation: exact optimum by solver, and certifiability by solving the linear relaxation and the degree-2 and degree-4 sum-of-squares relaxations. The theorems tell us which gap families exist and how to generate them at scale. Faithfulness is also only judged relative to a stated proof system with a length budget. A model that silently enumerates 2^20 assignments would be faithful to a different computation. That is exactly why we require a short checkable certificate in addition to free-form reasoning, and why we report results per proof-system level.

Research Program

The first component is a generator and labeler, which we call CertGap. It covers three problem families where certificates have readable combinatorial forms. For Max Cut upper bounds, certificates are packings of odd cycles, which fit the linear level, or the eigenvalue (Goemans–Williamson dual) bound, which fits the SDP level. For independent-set upper bounds, certificates are clique covers at the linear level or the Lovász theta function at the SDP level. For 3-SAT refutation, certificates are weighted clause combinations, or a cited minimal infeasible subsystem. Instances have 15 to 40 variables, so exact answers are cheap.

For each instance we record four things: the true value, the strongest bound each certificate level can prove, whether the claimed answer is certifiable at each level, and its minimal infeasible subsystems where they apply. Pairs are matched on surface statistics, and a classifier trained on surface features alone must perform at chance at telling the members of a pair apart. That classifier check is what makes "same appearance, different certifiability" an operational claim rather than an assumption.

The second component is the measurement protocol. Models answer each instance with free reasoning, a confidence score and a structured certificate, and a checker verifies the certificate. We then define a rationalization gap: answer accuracy minus the rate of valid certificates, computed separately on certifiable and uncertifiable members of the pairs.

The central label is "correct answer, trace presents a derivation, certificate invalid, instance uncertifiable at the trace's level." For refutations, we add a reason-overlap score: the overlap between the constraints the trace cites and the instance's minimal infeasible subsystems. This tests whether the model's stated reason matches the actual mathematical reason. We expect the GPT-4 paradox reported in On the Hardness of Faithful Chain-of-Thought Reasoning in Large Language Models and Measuring Faithfulness in Chain-of-Thought Reasoning to show up here in a specific form. Larger models should gain accuracy on uncertifiable instances, through better density priors, faster than they gain valid certificates. Their rationalization gap should therefore grow with scale.

The third component is an intervention. Following the reinforcement learning recipe of Large Language Models as End-to-end Combinatorial Optimization Solvers, which uses Group Relative Policy Optimization with a feasibility reward, we train a 7–8B model with a reward that pays for a checked certificate. It also pays for the explicit statement "true answer likely X, but I cannot certify it" on instances where no certificate exists at the allowed level. Unsupported assertions are penalized. The question is whether this lowers the rationalization gap without hurting accuracy on certifiable instances. Recall that the hardness paper reports accuracy drops of up to 20% on TruthfulQA from faithfulness steering.

Baselines

The naive reference point is a surface-statistics predictor: a logistic regression on size, density and degree statistics that predicts the answer. Its accuracy on uncertifiable instances is the accuracy the model's prior alone could reach. Any model accuracy near this level on gap instances, paired with confident derivation-style traces, is the signature we are looking for.

For detecting rationalization, the strongest existing method is the LLM-as-judge from FaithCoT-Bench, called Faithful-Judge. It reports F1 between 65 and 77 on the expert-annotated FINE-CoT set and beats logit-based probes, which often score below 50. We run it with the same judge model and prompt on CertGap traces and score it against our labels. Two behavioral detectors are run on identical traces with matched forward-pass budgets. The first is the early-answering area-over-curve measure of Measuring Faithfulness in Chain-of-Thought Reasoning, which truncates the reasoning at successive steps and checks whether the answer changes. The second is the step-corruption causal-importance score of FRIT, which replaces individual steps with distractors and checks whether the answer flips. We have no prior number for any of these detectors on certificate-grounded labels; no reported result found on Lacuna for detection on certifiability-matched instances. "Beating" a detector here does not mean beating it with a new detector. It means showing whether its F1 against our labels is far below its FINE-CoT figure. A large drop would indicate that judged faithfulness tracks how plausible a trace sounds rather than whether it is valid.

For the intervention, the baseline is the reinforcement learning pipeline of the combinatorial-optimization solver paper, which reports near 100% feasibility and optimality gaps of 1.03%–8.20% on its suite. We reuse its reward with answer correctness only and give it the same base model, data, rollout count and tuning budget. The key ablation keeps everything fixed but removes either the certificate reward or the "cannot certify" option, which separates the effect of checked derivations from the effect of abstention. Our intervention wins if it lowers the rationalization gap on uncertifiable instances by a clear margin while staying within two points of the baseline's accuracy on certifiable instances.

Why not just…?

Why not just inject a hint into the prompt and see whether the trace admits using it? Planted-cue designs do give ground truth, and they are the strongest alternative. But they measure rationalization of an external cue. The failure the literature worries about most is the model's own internal prior dominating its reasoning, as in the confirmation-bias findings of Unveiling Confirmation Bias in Chain-of-Thought Reasoning. We will run a hint-injection condition on the same instances. If detectors rank models the same way under both designs, the certifiability construction adds little, and we will say so.

Why not just verify the final answer with a solver? A solver tells us whether the answer is correct, not why the model gave it. The cases we care about are answers that are correct but whose derivation is impossible. Answer checking scores these as successes.

Why not just autoformalize the trace into Lean? FaithformBench shows autoformalizers quietly repairing invalid steps, with false-positive rates often above 40%, and inconclusive rates rising on hard problems. Our certificates are checked by exact arithmetic on a fixed format, with no translation step, so a broken step cannot be fixed in the course of formalizing it.

Why not just use FINE-CoT labels? They are human-annotated and cover open-domain questions, so detector errors and label errors cannot be told apart. Our labels are exact but domain-narrow. Running both lets us check whether detector rankings carry over from one to the other.

Decisive Checks

We evaluate Llama 3.1 8B, Qwen2.5-7B, Qwen3-8B and, through an API, the reasoning models examined in the combinatorial-optimization solver paper on roughly 5,000 matched pairs per problem family. The central result is a sign test within pairs. If accuracy and confidence are statistically indistinguishable between certifiable and uncertifiable twins while the valid-certificate rate collapses on the uncertifiable twins, the model's derivations are post-hoc on those instances. That conclusion can be stated with no faithfulness heuristic involved. The reverse outcome, where accuracy falls in step with certifiability, would be evidence that reasoning is load-bearing in this domain, and is equally publishable.

Three further checks follow. The first is whether the rationalization gap grows with model scale. The second is whether Faithful-Judge, early answering and FRIT scores rank uncertifiable-but-correct traces as faithful. The third is whether reason overlap with the minimal infeasible subsystems is high for certified refutations and near chance for uncertified ones. To show that the labels do not depend on the chosen proof system, we repeat all checks at the linear, degree-2 and degree-4 levels and require the qualitative pattern to hold at each.