- Rating
- 2
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 1(−1)
- Soundness
- 2
Read review
Paper summary
This paper studies when and how the cached proofs can still be reused after costs, budgets, or available evidence change. The paper shows: one proof can stop being feasible even though another proof still works, and keeping multiple minimal proof supports. They shows theoretical guarantees for when the cache remains exact and give a more compact way to store proofs. Experiments was only conducted on a quite small subset to support the theory, but the evaluation remain limited.
Critical strengths
-
A theory of when cached proofs stay reliable. Proposition 3 shows: fixed whole-proof library has to keep every minimal support, if it needs exact budget decisions under arbitrary positive prices. Theorem 4 links the approximation error to a constrained Hamming covering radius, separating the effects of price changes from evidence exclusions. They give concrete guarantees regarding the trade-off between cache size and how reliable the certification is.
-
The experiments separate missing rejection certificates from missing proof alternatives. Table 1 shows: the initial infeasibility and minimum-cardinality information sets previously unresolved 4,240 budget decisions. This is a meaingful distinction, as it shows a better proof cache is not only about storing more proofs.
Critical weaknesses
1. The experiments are narrow, not proofing the use in practice. The evaluation just uses the first 32 ProofWriter records, with 466 goals and 1,864 resource queries. More importantly, 338 of the 466 goals have no feasible proof at all, and only 11 have multiple minimal supports. My point is to keep alternative proofs around when resource constraints change, so a bigger test on problems are excepted.
2. It’s unclear if the representations scale. The paper shows that complete support frontiers can blow up exponentially. The factored approach is exponential in the number of shared nodes. But the experiments only test on small instances where you can simply enumerate. There’s no look at how compile time, memory, or query latency grow with the number of facts, rules, or alternative proofs.
3. The link to real LLM reasoning systems isn’t shown. The paper motivates itself with reusable reasoning and cached proofs, but the experiments are conducted entirely on given formal facts and rules. No test proof generation, natural-language parsing, or mistakes an LLM might make. Without an end-to-end evaluation, it’s hard to tell whether this certification framework would actually make practical LLM reasoning more reliable.
Questions for authors
See weakness
2 comments
response
Thank you for the detailed response. Since this topic is somewhat outside my main area of expertise, I do not feel confident making a strong judgment on all of the technical details.
The rebuttal helps clarify the intended scope of the paper and addresses some of my questions. However, my main concerns regarding the limited empirical evaluation and practical validation remain. I therefore plan to maintain my current score and confidence.
Reviewer JJYb
A stored proof can still be valid after prices change and yet be too expensive for the new budget. Our analysis asks what additional information is needed to answer that later budget query reliably. Theorem 4 gives an exact relationship between cache distortion, price changes and evidence exclusions, with explicit storage thresholds. The shared-acquisition construction in Section 2.6 establishes a complementary representation result. A family with 2k minimal supports has a linear-size exact conditioned solver, while tree-selected proofs incur a cost ratio of k2/(k+1) even after duplicate purchases are removed. These results explain why future budget decisions depend on both retained information and the structure used to represent alternatives.
The ProofWriter evaluation checks those mechanisms against exhaustive answers. Its 466 goals comprise 338 with no support, 117 with one minimal support and 11 with multiple supports. Retaining initial infeasibility and minimum-cardinality information resolves 4,240 additional decisions. The multi-support cases include 26 feasible budgets whose affordable witnesses were omitted by the initial one-proof cache. In response to the uniqueness question raised during review, retaining the certified unique-support flag resolves another 355 rejections and leaves 54 unresolved decisions. The flag comes from the original complete initialization records. This directly demonstrates the decision value of retaining initialization information.
Your scalability concern goes beyond the small exhaustive evaluation. The paper gives representation-dependent complexity bounds. Complete support frontiers can be exponential. The general shared-boundary method uses O(2q(N+E)) preprocessing, where q counts shared nodes, and the Section 2.6 construction has linear preprocessing because it has one shared acquisition. The factored representation makes its structural size and the number of shared nodes explicit in the preprocessing cost.
For an LLM reasoning pipeline, the certificate applies once facts, rules and acquisition identities have been supplied. It then determines whether an eligible proof fits the current budget, including changes in prices and availability. ProofWriter provides this formal interface; it does not evaluate proof generation or parsing in an end-to-end LLM system.