acceptodds
Under review as a conference paper at ICLR 2027

ProofCover: Auditing Proof Replacement under Answer-Preserving Updates

Abstract

Evaluating rule-based reasoning by final-answer accuracy is standard practice, even when models also return the facts and rules supporting their predictions. However, after the rule world changes, the correct answer may remain the same while the submitted support becomes invalid, causing answer-centric evaluation to award full credit to an invalid certificate. Our key insight is that this is a structural observability gap: answer-only scoring cannot distinguish a valid current-world certificate from an invalid one when both predict the same correct label. Based on this observation, we introduce ProofCover, an evaluation framework and diagnostic benchmark that makes support validity under answer-preserving updates directly measurable. Instead of scoring only the final answer, ProofCover enumerates the complete set of minimal proofs for each query, uses this proof set to construct updates that preserve the correct answer while selectively invalidating the model's submitted certificate, and then applies a deterministic current-world verifier to check whether the model's new certificate remains valid in the updated world. On Formal-500, proof-set-aware construction achieves 100% success on Repair, compared with 16.6%–43.4% for three simple selection baselines. Under Fresh Adaptive Repair, false passes occur in all eight evaluated models: among outputs accepted by answer-only scoring, 15.3%–48.1% (median 27.1%) carry certificates that fail current-world verification. This pattern replicates on RuleTaker-MP, a RuleTaker-derived multi-proof benchmark constructed from official test data, where false-pass rates span 6.2%–22.0% across the same eight models. These results show that answer-only scoring can substantially overestimate support reliability in the evaluated update settings, while highlighting a certificate-validity gap that final-answer accuracy does not measure.

Primary area:
datasets and benchmarks
Keywords:
Rule-Based Reasoning, Proof Certificates, Answer-Preserving Updates, Knowledge Base Updates, Model Auditing, Benchmark and Evaluation, Faithfulness and Verification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_rvfEOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces ProofCover, an evaluation framework for testing whether a model can provide valid supporting evidence after the underlying rule environment changes while the correct answer remains the same. The framework enumerates minimal proofs and uses them to construct controlled updates. In the adaptive setting, it deletes a rule cited in the model’s previously valid certificate while ensuring that an alternative proof survives. The model is then evaluated on both its answer and the validity of its new certificate.

The experiments evaluate eight models on ProofWriter-derived instances and a RuleTaker-derived benchmark. They find that models often return the correct answer together with an invalid certificate. The paper also compares evaluation with and without explicit update history and examines the types of certificate errors.

Critical strengths

I like the basic evaluation question. If a system provides supporting evidence for its answer, it is reasonable to require that this evidence remain valid when the underlying information changes. Keeping the answer fixed while changing which support is valid gives a clean way to formulate this requirement.

The use of an exact symbolic verifier is a strength. The certificate has a precise meaning, and its validity can be checked directly. I also appreciate that the authors distinguish the submitted certificate from the model’s internal reasoning.

The evaluation covers several model families and a second benchmark source. The paper is generally careful about reporting model-specific eligibility and denominators, and about distinguishing successful replacement from refusal. In particular, it does not simply interpret a decrease in invalid certificates as an improvement when the model instead stops answering.

Critical weaknesses

There is an inconsistency in the certificate analysis that I could not reconcile. Adaptive Repair requires that the deleted rule belong to the model’s valid Original certificate. Table 29 defines “unchanged” as a certificate identical to that Original certificate. Therefore, an unchanged certificate must contain the deleted rule. However, Table 29 reports zero deleted-rule citations for every model, while reporting positive unchanged counts for seven models. For example, Qwen3-8B has six unchanged certificates and zero target citations. These statements cannot both hold under the stated definitions. This may be a mislabeled column or an error in how the records were compared, but it matters: the table is used to support the conclusion that failures arise from incomplete reconstruction rather than reuse of the original certificate. I would like this discrepancy resolved before relying on that interpretation. There is also a discrepancy in the judge results: Appendix A10 reports 90.9% stale recall for the Qwen3-32B certificate-aware judge, whereas Table 19 reports 45.5%. The experimental discussion and tables need to be reconciled.

Questions for authors
  1. What exactly does “unchanged” measure in Table 29, and how can its positive counts be reconciled with zero deleted-rule citations? Does correcting this discrepancy change the failure decomposition or any headline results?

  2. On the same eligible True instances, how does certificate validity change under an edit that preserves the original certificate, compared with the targeted deletion? This comparison would help clarify the interpretation of the main finding.

4 comments

We thank the reviewer for the careful examination of our results and the suggestions for strengthening the experimental evidence. We independently re-examined the reported statistics and conducted additional matched-control experiments to address the concerns.

W1 & Q1: Statistical consistency and reliability

Table 29 — Certificate reuse. Thank you for highlighting the ambiguity in the certificate-reuse statistics. The 37 cases were computed using nonempty certificate-set containment (Cnew⊆ColdC_{\mathrm{new}} \subseteq C_{\mathrm{old}}), rather than exact certificate equality.

Our independent re-examination confirms:

Certificate relationshipVerified cases
Exact reuse: Cnew=ColdC_{\mathrm{new}} = C_{\mathrm{old}}0
Partial reuse: ∅≠Cnew⊂Cold\varnothing \neq C_{\mathrm{new}} \subset C_{\mathrm{old}}37
Stale certificates citing the deleted target rule0

All 37 cases are strict subsets of the original certificates. This distinction helps characterize the failure mode: a model may reuse part of the previous evidence without constructing a complete valid replacement proof. Consequently, invalid certificates need not explicitly cite the deleted rule.

We have clarified the column name as Subset of Original Certificate and explicitly specified its criterion in the revised manuscript.

Reliability of the main results. To determine whether the certificate-reuse distinction affects the central findings, we independently rechecked all 821 eligible model–example evaluations against the stored predictions and certificates.

MetricOriginal resultsIndependent re-audit
Eligible evaluations821821
Success501501
Stale162162
Other158158
Models with reproduced outcome counts8/88/8
Missing evaluations—0

All per-model Success/Stale/Other counts and stale/accepted rates are reproduced exactly. Thus, the clarified certificate-reuse definition does not change the primary empirical finding that models can produce correct answers with invalid supporting certificates.

We have included the verified statistics and clarified the evaluation definitions in the revised manuscript.

Appendix A10 — Judge statistics. We further recomputed the judge metrics directly from the saved confusion matrices. Table 19 is consistent with the evaluation records; two certificate-judge values in the Appendix A10 prose require alignment with those calculations.

Model / judgeA10 reported stale recall / valid retentionVerified from Table 19
Qwen3-32B / Answer45.5% / 82.5%45.5% / 82.5%
Qwen3-32B / Certificate90.9% / 67.5%45.5% / 75.0%
Llama-3.3-70B / Answer41.2% / 50.9%41.2% / 50.9%
Llama-3.3-70B / Certificate88.2% / 70.2%58.8% / 56.1%

We have updated the Appendix A10 descriptions and the corresponding interpretation of judge performance using the verified values.

These judge-level revisions do not affect the primary benchmark outcomes, which are independently determined through certificate validation.

Q2: Does proof-targeted disruption explain the observed failures?

We conducted an additional matched preserve-versus-target experiment to distinguish the effect of proof disruption from general sensitivity to KB updates.

Both conditions share the same original KB, query, certificate, edit size, and oracle answer (True→True). Their distinction is whether the selected original proof remains valid.

ConditionOriginal proofAlternative proofOracle answer
PreserveRemains validAvailableTrue
TargetInvalidatedAvailableTrue

This design controls for answer changes and edit size while directly varying the impact on the original proof.

ModelMatched nPreserve S/St/OTarget S/St/OΔStale
Phi-4-mini4537/2/624/11/10+20.0 pp
Llama-3-8B5137/7/730/15/6+15.7 pp
Qwen3-8B8347/13/2340/19/24+7.2 pp
Qwen3-4B9361/15/1754/20/19+5.4 pp
Qwen3-32B6446/5/1329/8/27+4.7 pp
gpt-oss-20b177155/22/0145/28/4+3.4 pp
Total (6 models)513383/64/66322/101/90+7.2 pp

S/St/O denotes Success/Stale/Other; ΔStale is the difference in Stale outcomes divided by matched n.

Across the six reported models, targeted proof disruption consistently increases stale-certificate outcomes. Overall, Stale increases from 64/513 to 101/513 (+7.2 pp).

Since the correct answer remains unchanged and the update size is matched, these results provide direct evidence that disrupting the original proof increases the difficulty of producing valid replacement evidence, independently of answer changes.

Importantly, the full Success/Stale/Other distributions distinguish invalid supporting certificates from other output failures.

We have added this matched-control experiment, its construction protocol, and the corresponding analysis to the revised manuscript. The additional evidence strengthens the central conclusion of ProofCover: preserving a correct answer does not guarantee successful adaptation of its supporting proof after a knowledge update.

All revisions described above have been incorporated into the latest submitted PDF of our manuscript, with the corresponding changes highlighted in red for ease of review.

We sincerely thank the reviewer again for the constructive feedback. We would be happy to provide further clarification and discuss any remaining questions.

Dear Reviewer,

Thank you for your careful review. We have corrected the reported inconsistencies and added matched-control experiments to address your questions. We would appreciate any follow-up feedback on our clarifications.

Thank you for your time!

Dear Reviewer,

Thank you for your careful review. We would like to briefly highlight how we have addressed your concerns.

  1. Table 29 and judge-statistics inconsistencies (W1/Q1). We have corrected the certificate-reuse definition (37 partial, zero exact reuse) and the Appendix A10 judge statistics. We have independently verified all 821 evaluations, reproducing the original Success/Stale/Other counts.

  2. Does targeted proof disruption cause additional certificate failures? (Q2) We have added preserve-versus-target comparisons across 513 matched cases, showing an increase in stale certificates from 64 to 101 (+7.2 pp).

All corrections and additional experiments have been incorporated into the revised manuscript, with changes highlighted in red.

Thank you for your consideration.

Reviewer_uThgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces ProofCover, an evaluation framework for testing whether a model’s submitted proof certificate remains valid after a knowledge-base update that preserves the gold answer. The framework constructs updates that invalidate some proof support while retaining an alternative derivation, then checks model-submitted certificates against the updated world with a deterministic verifier. Across several models and rule-based benchmarks, answer-only scoring accepts a substantial fraction of outputs whose certificates fail current-world verification. The paper also compares fresh and stateful prompts, update constructions, and evaluator choices.

Critical strengths
  1. The paper precisely defines a failure mode that ordinary answer accuracy cannot observe. Its constructed updates preserve the oracle answer while altering the valid support, enabling a clean separation between label accuracy and certificate validity.
  2. The evaluator-side symbolic verification and cross-benchmark replication make the experimental claim auditable. The paper does not rely solely on a learned judge to determine whether a certificate proves the answer in the updated world.
Critical weaknesses
  1. First, it would be great to better understand how common this specific workflow is in practice. In the current setup,the evaluator ignores the certificate provided by the model (the "answer-only" condition), which naturally leads to scoring limitations. However, it is a bit unclear if real-world applications commonly use this approach when evidence validation is still required. To strengthen this point, could you provide some concrete examples, systems,or past benchmarks that rely on answer-only scoring after a KB update? If this setup is mostly theoretical, it might be helpful to gently narrow the claims about real-world deployment.
  2. Second, the motivation for "answer-preserving updates" could benefit from a bit more context. For instance, if an application only needs the final answer, it seems straightforward to just rerun the model on the updated KB.Alternatively, if auditable evidence is needed, the system could simply verify the certificate against the new KB. It would be very helpful if you could clarify what specific real-world constraints might prevent these standard approaches. Expanding on how ProofCover's setup compares to these alternatives would make the motivation much stronger.
Questions for authors
  1. Could you highlight any real-world systems or benchmarks where an evaluator only checks the answer after a KB update, even when the model's proof is important? It would be helpful to know how prevalent this workflow actually is.
  2. Could you elaborate on why a real-world evaluator might keep an old answer or proof instead of just rerunning the verification on the updated KB? Understanding the specific operational limits that make "answer-preserving updates" necessary would really help clarify the core problem.
6 comments

We thank the reviewer for the valuable questions about practical relevance and the distinction between ProofCover, re-inference, and symbolic reasoning. We have expanded the practical motivation and added experiments to clarify the need for update-aware evidence maintenance.

W1 & Q1: Why is answer-preserving proof replacement relevant to real-world systems?

ProofCover addresses a fundamental requirement of evolving knowledge systems: maintaining valid supporting evidence for previously established conclusions when the underlying knowledge changes.

A knowledge update may preserve the final answer while changing the rules, documents, or reasoning paths supporting it. This occurs in several practical settings:

ApplicationExisting systemAnswer-preserving update scenarioEvidence-maintenance requirement
Policy-based authorizationCedar, OPAA supporting policy is revised while another policy preserves the authorization decisionMaintain current supporting policies and auditable decision evidence
Enterprise knowledge assistantsAmazon Bedrock Knowledge BasesAn outdated document is replaced while its factual conclusion remains correctUpdate the evidence and citations supporting existing answers
Multi-step retrieval and agentic QAAzure AI SearchSupporting documents or intermediate retrieval paths change without changing the conclusionMaintain valid evidence across evolving knowledge sources
Evidence-lifecycle evaluationVera-Life-Eval, GroundLM 2026Previously supporting evidence becomes outdated or supersededEvaluate current evidence validity independently of answer correctness

These settings share an important requirement: the correctness of a conclusion and the validity of its current supporting evidence must be maintained separately.

Existing knowledge-editing benchmarks also demonstrate answer-level evaluation following updates:

BenchmarkPost-update evaluationAdditional dimension evaluated by ProofCover
RippleEdits, TACL 2024Factual correctness and preservation after knowledge editsValidity of supporting derivations
MQuAKE, EMNLP 2023Multi-hop answer correctness after knowledge updatesCurrent-version proof validity
ProofCoverAnswer-preserving KB updatesWhether the model provides valid updated supporting evidence

ProofCover connects post-update evaluation with the evidence-maintenance requirements of dynamic knowledge systems.

To examine this setting in naturally occurring updates, we have added a historical audit of real-world policy-rule revisions.

Historical update auditResult
Candidate update–query records381
Answer preserved, with complete derivations in both KB versions42 / 381 (11.0%)
Original derivation uses a rule modified by the update28 / 42 (66.7%)

Notably, 66.7% of the eligible real-world revisions modify rules used by the original derivation while preserving the final answer. This demonstrates that evolving knowledge bases can preserve conclusions while changing the reasoning paths on which their supporting proofs depend.

W2 & Q2: Why is re-inference insufficient for evidence maintenance?

Re-inference and evidence maintenance address fundamentally different tasks.

In our target setting, an answer and its supporting proof have already been generated. After a KB update, the requirement is to maintain valid evidence for that existing conclusion, rather than simply produce another answer.

Re-inferenceEvidence maintenance
Starting pointA queryAn existing answer and proof
ObjectiveGenerate a new answerMaintain valid support under the updated KB
Earlier supporting evidenceNot inherently examinedMust be audited
Relationship to the updateUses the updated KBIdentifies affected supporting dependencies
Required outcomeA new answer or proofValid current-version evidence for the retained conclusion

For example, consider a policy decision supported by r1r_1 under KB version K0K_0. After an update removes r1r_1, another rule r2r_2 may preserve the same decision under K1K_1.

Original KB K0K_0Updated KB K1K_1
Correct decisionAllowAllow
Supporting ruler1r_1r2r_2
Previously generated proofSupports the decisionRequires updated support
Answer-only evaluationCorrectCorrect
Evidence-aware evaluationValid supportCurrent-version support required

Obtaining the same answer again does not establish whether the previously generated proof remains applicable or how its evidence should be updated.

This distinction is important for versioned policy decisions, retained audit records, and knowledge-grounded applications where answers and their justifications persist across KB revisions.

Furthermore, localized KB updates need not affect every existing conclusion. Recomputing all retained queries after each update introduces redundant computation, motivating incremental maintenance approaches such as DBSP and Materialize.

ProofCover directly evaluates this update-aware evidence-maintenance requirement.

Does complete re-inference guarantee valid evidence?

Our Fresh baseline already reruns the model using the complete updated KB.

We have added a direct comparison of answer accuracy and certificate validity:

ModelCasesAnswer accuracyValid certificateGap
Qwen3-8B13470.9%50.7%20.1 pp
Llama-3-8B6085.0%56.7%28.3 pp
Qwen3-32B8262.2%48.8%13.4 pp
gpt-oss-20b20197.5%82.6%14.9 pp

Even after full re-inference, answer accuracy exceeds valid-certificate performance by 13.4–28.3 percentage points.

These results demonstrate that re-inference cannot substitute for explicit evidence auditing: recovering a correct conclusion and providing valid supporting evidence are empirically distinct capabilities.

Q2: Why are symbolic verification and proof generation insufficient as substitutes?

The approaches address different components of evidence maintenance:

ApproachPrimary capabilityEvidence-maintenance requirement
Full re-inferenceRecompute answers and candidate proofsEstablish current validity and continuity of existing evidence
Symbolic verificationCheck whether a proposed proof is validObtain valid replacement evidence when verification fails
Symbolic proof generationConstruct valid proofs from formalized knowledgeEvaluate whether an LLM can generate valid current-version evidence
ProofCoverAudit LLM-generated proofs under controlled KB updatesMeasure evidence-maintenance reliability directly

In a fully formalized Horn KB, symbolic proof generation provides an exact solution. ProofCover uses symbolic reasoning as an exact evaluation oracle, enabling rigorous assessment of LLM-generated evidence.

Its independent contribution is an update-aware auditing framework that isolates evidence-maintenance capability from answer-recovery capability.

Pure verification establishes whether a certificate is valid. Maintaining evidence additionally involves producing valid current-version support for a previously established conclusion.

To evaluate these capabilities, we have added verification and bounded repair baselines on the same 134 Qwen3-8B instances:

MethodValid (S)Invalid (St)Other (O)Valid yieldInvalid/accepted
Fresh inference68273950.7%28.4%
Verify and reject6806650.7%0.0%
Blind retry94172370.1%15.3%
Binary verifier feedback93182369.4%16.2%
Error-specific verifier feedback11015982.1%12.0%

Valid yield = valid certificates / all instances; invalid / accepted = invalid / (valid + invalid). Repair methods use at most two additional generation calls.

Verification-only filtering eliminates accepted invalid certificates, while error-specific verifier feedback additionally raises valid-certificate yield from 50.7% to 82.1%.

The improvement extends across all six evaluated models:

ModelFresh validGuided validImprovement
Qwen3-8B50.7%82.1%+31.3 pp
Llama-3-8B56.7%81.7%+25.0 pp
Gemma-3-4B41.2%61.8%+20.6 pp
Qwen3-4B57.1%74.6%+17.5 pp
Qwen3-32B48.8%58.5%+9.8 pp
Phi-4-mini58.1%67.4%+9.3 pp

All six models improve under bounded verifier-guided repair. These results establish ProofCover's ability to quantify evidence-generation reliability and assess strategies for improving it.

Reviewer_2kbEOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents ProofCover, an evaluation framework that checks whether a model’s cited support still proves its answer after the world changes while the final answer stays correct.

Critical strengths

The paper points to a pretty clear gap in evaluation

The construction is nicely controlled too.

Critical weaknesses

The approach depends on listing all complete minimal proofs and then computing hitting sets. That is likely to become expensive in larger or denser rule environments, and it also ties the method to positive Horn logic.

Treating Unknown as requiring an empty certificate is a fairly strict rule. It may work against models that express hesitation or cite context but still end with Unknown.

There is no runtime or complexity analysis for proof enumeration, hitting set computation, or the adaptive selection step, so the scalability of the approach is left unknown.

The models evaluated are general purpose instruction tuned LLMs. The claims would be stronger with direct comparisons to specialized neurosymbolic or proof producing systems, including multiPRover, LogicGraph, and LMLP/Natural Program, as baselines.

The realism of the updates is not cov in much depth. It remains unclear how often edits that preserve the answer but change the supporting evidence reflect actual KB evolution.

The majority vote and judge ablations are useful, but the paper could add stronger verifier assisted baselines, such as tool augmented repair prompting, to see whether models can be guided to succeed.

The exact certificate grammar and the rules for allowing certificates that are not minimal should be summarized more visibly. In particular, readers should be told whether supersets are accepted and how extra IDs affect validity.

Some appendices carry central material, such as the algorithms for the operators and the complexity ranges, and short summaries in the main text would help.

The paper cites many works, but it could connect more directly to auditing frameworks for grounded QA, such as FEVER style evidence checks, and to recent counterfactual audits of retrieval grounding, such as HERALD. That would make the conceptual overlaps and differences clearer.

A short direct comparison with proof producing baselines that already enumerate multiple proofs or enforce verifier constraints, such as multiPRover or LogicGraph style setups, would help show where the gains come from.

Questions for authors

Since the adaptive sets are model conditional, how should readers compare models? Can you report results on a shared eligible intersection or matched subsets across models?

Only one greedy decoding seed per model is used. Can you provide repeated runs or a variance estimate for the key false pass rates, at least on a subset?

The benchmarks are small positive Horn theories. What evidence suggests the findings transfer to multi rule edits, negation, inconsistency, or more naturalistic reasoning settings?

The paper shows majority voting and LLM judges do not close the gap. Beyond recommending deterministic verification, is there an inference or training intervention you tested that reduces stale certificates without mainly increasing refusals?

5 comments

We thank the reviewer for the constructive feedback. We have expanded the evaluation to address scalability, complex knowledge-base updates, specialized proof-producing systems, verifier-guided repair, and evaluation robustness.

W1/W3/W8 — Scalability, Computational Cost, and Algorithm Presentation

We evaluated proof enumeration, minimum-cut computation, and adaptive construction across increasingly complex Horn theories. All constructed updates were verified using an exact symbolic oracle.

Construction scalability (p95 latency, ms).

RulesMinimal proofsDepthEnumerationMin-cutAdaptiveValid edits
10–204–202–60.890.490.15100/100
20–4010–483–82.191.990.27100/100
20–5052–2004–107.542.930.62100/100

We further reproduced the construction comparisons on Formal-500:

MethodValid Repair edits
ProofCover500/500 (100.0%)
Single-proof217/500 (43.4%)
Random161/500 (32.2%)
Greedy coverage83/500 (16.6%)

These results demonstrate reliable construction up to 200 minimal proofs with millisecond-level runtime in the evaluated settings. Complete proof enumeration has exponential worst-case output complexity, while exact hitting-set computation is combinatorial; the experiments quantify their practical costs.

We have moved the core algorithms, proof-family definitions, computational complexity analysis, and scalability results into the main manuscript.

W5/Q3 — Complex Updates and Real-World KB Evolution

We extended the original single-rule protocol to simultaneous rule deletions and natural-language rule revisions. For each update size, we computed the oracle feasibility ceiling and independently verified the resulting proof-set transitions.

UpdateVerified / oracle-feasibleModels exhibiting false passes
Single-rule deletion500/5008/8
Two-rule deletion227/2276/7
Three-rule deletion107/1076/7
NL rule revision500/5007/7

The two-rule and three-rule feasibility ceilings correspond to 227/500 and 107/500 original worlds, respectively. The constructor reaches both ceilings. Natural-language revisions preserve the rule identifier while modifying its conclusion; independent proof-family reconstruction exactly verifies 489/500 cases and all corresponding 489 transitions.

Invalid-support certificates persist across these settings. For Qwen3-8B, FP/accepted is 23.8%, 12.5%, and 42.3% under two-rule deletion, three-rule deletion, and NL revision, respectively. All seven models exhibit false passes under NL revisions.

We additionally analyzed real policy-as-code evolution using historical revisions from the Gatekeeper policy library.

Historical-edit analysisCases
Screened revision–query candidates381
Answer-preserving revisions with valid derivations in both versions42
Original derivation traces involving modified rules28/42 (66.7%)
Original minimal supports intersecting modified rules24/42 (57.1%)

Direct replay of old minimal supports also identified two query cases in which the previous support became invalid while the answer remained derivable.

These observations establish that answer preservation does not imply preservation of the supporting derivation. This behavior is also documented in incremental Datalog maintenance (Motik et al., 2019) and dynamic knowledge-graph provenance (Gaur et al., 2020), where updates can invalidate individual derivations while alternative support preserves the result.

The formal construction guarantees apply to positive-Horn entailment, including negated natural-language predicates represented as distinct atoms. General nonmonotonic negation and inconsistent-theory entailment require their own certificate semantics.

We have incorporated the complex-update experiments, historical-edit analysis, and corresponding real-world motivation into the revised manuscript.

W4/W10 — Specialized Proof-Producing Baselines

We additionally evaluated multiPRover and Natural Program alongside proof-oriented and verifier-constrained methods. All methods were tested on the same answer-preserving updates and evaluated using the same exact certificate verifier.

Shared-update comparison (%; single-rule / two-rule).

MethodValid Certificate ↑FP/accepted ↓
Qwen3-8B37.5 / 35.035.7 / 33.3
gpt-oss-20b83.3 / 76.715.3 / 22.7
Multi-proof prompting74.2 / 77.519.1 / 16.2
multiPRover73.3 / 69.224.8 / 25.9
Natural Program38.3 / 52.541.8 / 26.7
Verifier-constrained81.7 / 78.318.3 / 21.0

LogicGraph provides a multi-path reasoning benchmark with exhaustive minimal-proof sets and symbolic verification, rather than a standalone prediction model; accordingly, it serves as a proof-family evaluation reference.

These results show that answer correctness and certificate validity remain distinct evaluation dimensions across different proof-producing methods. ProofCover provides a unified framework for measuring this gap under answer-preserving updates.

We have added these baseline comparisons and the corresponding evaluation protocol to the revised manuscript.

Q1/Q2 — Fair Comparison and Randomness

We added shared-world and matched-eligibility evaluations to ensure fair cross-model comparisons.

All models receive the same 120 answer-preserving update worlds. We additionally compare models on pairwise shared-eligible intersections:

Model pairMatched NFP/accepted: AFP/accepted: B
Qwen3-8B / Llama-3-8B4328.6%24.3%
Qwen3-8B / Qwen3-32B5525.0%14.3%
Qwen3-8B / gpt-oss-20b6632.6%12.3%

We further evaluated generation stability over five stochastic seeds at temperature 0.7, with cases, updates, and verification rules fixed.

FP/accepted across five seeds (mean ± SD, %).

ModelGreedyFive-seed sampling
Qwen3-8B28.427.3 ± 4.8
Llama-3-8B33.344.2 ± 6.0
Qwen3-32B21.619.0 ± 5.2
gpt-oss-20b15.327.2 ± 3.3
Qwen3-4B25.826.6 ± 0.7
Phi-4-mini30.650.5 ± 13.9
Gemma-3-4B48.150.8 ± 3.2

Invalid-support false passes persist across all seven models under stochastic generation. The shared-world, matched-eligibility, and multi-seed results have been incorporated into the revised evaluation.

W2/W7 — Certificate Semantics and Unknown Scoring

ProofCover accepts nonminimal certificates whenever the referenced rules exist in the updated knowledge base and jointly suffice to derive the answer. Redundant but valid supporting rules are permitted.

We additionally compared the original Unknown scoring rule with a context-tolerant protocol allowing existing rule IDs alongside an Unknown answer.

Rescoring the frozen outputs yields identical results under both protocols for all eight models. For example, Qwen3-8B obtains 320/320, Qwen3-32B 676/676, and gpt-oss-20b 836/836 under the two scoring conventions.

Thus, the reported answer–certificate gap is unaffected by the Unknown certificate convention. We have clarified the certificate acceptance conditions and scoring protocol in the main text.

W9 — Relation to Evidence Verification and Counterfactual Auditing

We have expanded the related-work discussion to distinguish ProofCover from existing evidence-verification frameworks.

FEVER-style evaluation examines whether retrieved textual evidence supports or refutes a factual claim. HERALD studies counterfactual vulnerabilities in retrieval-grounded reward and citation mechanisms.

ProofCover instead evaluates whether a submitted symbolic proof certificate remains valid after the knowledge base changes while the query answer is preserved. By constructing updates over alternative minimal proofs, it directly separates answer preservation from proof validity.

This provides a complementary evaluation task centered on proof replacement under knowledge-base evolution. We have clarified the distinction and incorporated the corresponding references into the revised manuscript.

[N1] Swarnadeep Saha, Prateek Yadav, and Mohit Bansal. multiPRover: Generating Multiple Proofs for Improved Interpretability in Rule Reasoning. Proceedings of NAACL-HLT, pp. 3662–3677, 2021.

[N2] Zhan Ling, Yunhao Fang, Xuanlin Li, Zhiao Huang, Mingu Lee, Roland Memisevic, and Hao Su. Deductive Verification of Chain-of-Thought Reasoning. Advances in Neural Information Processing Systems, 36, 2023.

[N3] Yanrui Wu, Lingling Zhang, Xinyu Zhang, Jiayu Chang, Pengyu Li, Xu Jiang, Jingtao Hu, and Jun Liu. LogicGraph: Benchmarking Multi-Path Logical Reasoning via Neuro-Symbolic Generation and Verification. Proceedings of EMNLP, pp. 15931–15959, 2026.

[N4] Boris Motik, Yavor Nenov, Robert Piro, and Ian Horrocks. Maintenance of Datalog Materialisations Revisited. Artificial Intelligence, 269:76–136, 2019.

[N5] Garima Gaur, Arnab Bhattacharya, and Srikanta Bedathur. How and Why is An Answer (Still) Correct? Maintaining Provenance in Dynamic Knowledge Graphs. Proceedings of CIKM, pp. 405–414, 2020.

[N6] James Thorne, Andreas Vlachos, Christos Christodoulopoulos, and Arpit Mittal. FEVER: a Large-scale Dataset for Fact Extraction and VERification. Proceedings of NAACL-HLT, pp. 809–819, 2018.

[N7] Zhuowen Liu, Bohan Cui, YinShang Guo, Yuting Wang, and Hao Li. HERALD: Counterfactual Audits and Minimal Repairs for Proof-of-Retrieval Rewards. arXiv preprint arXiv:2608.06012, 2026.

All revisions described above have been incorporated into the latest submitted PDF of our manuscript, with the corresponding changes highlighted in red for ease of review.

We sincerely thank the reviewer again for the constructive feedback. We would be happy to provide further clarification and discuss any remaining questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions During Rebuttal

Dear Program Chairs, Senior Area Chairs, Area Chairs, and Reviewers,

We sincerely thank the reviewers for their constructive feedback. During the rebuttal period, we have substantially revised ProofCover through additional experiments, stronger baselines, methodological clarifications, and independent verification. Below, we summarize the main improvements corresponding to each review.

Reviewer 2kbE

  • W1/W3/W8 — Scalability and complexity: We have added scalability experiments covering up to 200 minimal proofs and moved the core algorithms and complexity analysis into the main text.
  • W2/W7 — Certificate semantics: We have clarified certificate acceptance rules and verified that alternative Unknown scoring does not affect the reported results.
  • W4/W10 — Specialized baselines: We have added comparisons with multiPRover and Natural Program under shared evaluation settings.
  • W5/Q3 — Generalization and real-world relevance: We have extended the evaluation to multi-rule deletions, natural-language revisions, and historical policy updates, while clarifying the scope of negation and inconsistency.
  • W6/Q4 — Practical improvements: We have introduced verifier-guided repair, improving valid-certificate yield by 9.3–31.3 pp across six models.
  • W9/Q1/Q2 — Related work and reliability: We have expanded the related-work discussion and added matched-eligibility and five-seed robustness evaluations.

Reviewer uThg

  • W1/Q1 — Practical relevance: We have expanded the real-world motivation and analyzed historical policy updates, identifying 42 answer-preserving revisions, including 28 affecting original derivations.
  • W2/Q2 — Evidence maintenance versus re-inference: We have clarified this distinction and added experiments showing a 13.4–28.3 pp gap between answer accuracy and certificate validity after fresh inference. Verifier-guided repair further improves Qwen3-8B's valid-certificate yield from 50.7% to 82.1%.

Reviewer rvfE

  • W1/Q1 — Statistical consistency: We have corrected the Table 29 certificate-reuse definitions and Appendix A10 judge statistics. We have independently rechecked all 821 eligible evaluations, reproducing exactly 501 Success, 162 Stale, and 158 Other outcomes.
  • Q2 — Matched-control evidence: We have added preserve-versus-target experiments across 513 matched cases, showing an increase in stale certificates from 64 to 101 (+7.2 pp) under targeted proof disruption.

Overall Improvements

Together, these revisions have strengthened ProofCover's methodological reliability, empirical generalization, and practical relevance. The additional evidence supports the central finding that answer correctness does not guarantee valid supporting evidence under knowledge-base updates, while demonstrating that verifier-guided feedback can substantially improve valid proof replacement.

All corresponding changes have been incorporated into the revised manuscript, with modifications highlighted in red.

We sincerely appreciate the reviewers' feedback and the committee's time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.