acceptodds
Under review as a conference paper at ICLR 2027

When Cached Proofs Certify an Evidence Budget

Abstract

A cached proof can remain valid while failing to certify a new evidence budget: repricing may make its support unaffordable even when an omitted alternative still fits. We formalize reusable budget certification in finite signed-Horn theories with canonical acquisitions charged once. Complete minimal support frontiers answer exact residual-cost queries; exact whole-proof lookup under arbitrary positive prices requires every minimal support. Under bounded prices and evidence exclusions, cache distortion equals a constrained Hamming covering radius, giving storage bounds and separate thresholds for cost approximation and status coverage. Factored representations can preserve these alternatives compactly: a family with exponentially many minimal supports has a linear-size exact solver, while tree selection can incur a linearly growing cost ratio even after duplicate purchases are removed. On a fixed ProofWriter prefix, independent exhaustive closure verifies 1,864 resource queries and 5,592 budget decisions. Retaining initial infeasibility and minimum-cardinality information resolves 4,240 decisions left unresolved by a one-support cache with its original bounds. Yet 26 feasible budgets still require an affordable witness that the cache omitted. Reusable reasoning therefore requires preserving both the conclusions that certify rejection and the alternatives that enable acceptance after resource changes.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
formal reasoning, proof caching, knowledge compilation, evidence budgeting, provenance, AND/OR reasoning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_JJYbOpenReview ↗
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
  1. 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.

  2. 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
AuthorsOpenReview ↗

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 2k2^k minimal supports has a linear-size exact conditioned solver, while tree-selected proofs incur a cost ratio of k2/(k+1)k^2/(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))O(2^q(N+E)) preprocessing, where qq 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.

Reviewer_JJYbOpenReview ↗

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_mFCbOpenReview ↗
Rating
1(−1)
Confidence
3(+1)
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper is studying cached reasoning representations, and specifically what they must retain to certify evidence-budget decisions when acquisition or availablitiy changes. It shows that complete minimal support frontiers answer exact residual-cost queries in finite signed-Horn theories, while universally exact lookup over stored whole proofs requires every minimal support. Exclusions through a constrained Hamming covering radius are characterized along approximations under bounded prices for a structured family of goals. It is also demonstrated that compact factored representations can preserve exponentially many alternatives, as well as that deduplication of tree-selected proofs does not always repair suboptimal proof selection.

Critical strengths
  1. Theorem 4 provides a very clear and clean characterisation of the connection between price distrortion and status-constrained covering radius, which separates quality of approximation the whether the cached witness survives.
  2. Explicit separation of failure mechanisms support confidence in the reported results, and their validation is transparent and rational.
  3. The clear distinction between acceptance, rejection, and unresolved querires provides a good foundation. In general, the explanations are good, clear, and conscise, and terms are well defined and used without any confusion.
Critical weaknesses
  1. It seems like an incremental contribution that is rather modest relative to established foundations. Multiple parts (support semantics, conditioning, relative-regret corner formula) are cited as adaptions of prior work. The joint price characterisation seems to be the strongest additional contribution, but that only concerns a rather specific case, limiting the impact.
  2. The practical benefit of the work is unclear and not demonstrated. The constructions are informative, but not evaluated on for instance explicit frontiers on ProofWriter. It is not established when the alternative representations proposed are preferable in broader instances.
Questions for authors
  1. What is the principal new contribution, apart form the established prior works? Is Theorem 4 the intended focus and main contribution?
  2. How could the comparison change, if initialization retained a certificate of uniwue minimal support, whenever this could be established, and what initialization cost and additional retained informtaion would that require?
  3. Can you provide clear evidence of where the theoretical distinctions change a practical design choice?
1 comment
AuthorsOpenReview ↗

Reviewer mFCb

Your proposed uniqueness certificate changes how much the cache can decide without storing another proof. Retaining it resolves 355 additional budget decisions in that control. We replayed all 5,592 saved decisions with the initial uniqueness flag and the same stored support. The unresolved count falls from 409 to 54, and all 355 newly resolved cases are correct rejections against the exhaustive reference. The totals become 886 acceptances, 4,652 rejections and 54 unresolved cases, with zero errors among resolved decisions. The remaining cases comprise 26 feasible budgets and 28 infeasible budgets.

The certificate works because every support in a finite monotone theory contains a minimal support. If S0S_0 is certified as the unique minimal support, every support contains S0S_0. Whenever S0S_0 avoids forbidden acquisitions and its unacquired items remain available, the exact residual cost is ∑i∈S0∖Ici\sum_{i\in S_0\setminus I}c_i for nonnegative prices, where II is the set of already acquired items. Otherwise the goal is infeasible. The extra retained information is the uniqueness flag accompanying the existing support. The replay establishes the flag from the original complete initialization records, so the cost of obtaining the certificate belongs to initialization.

Regarding the main contribution, Theorem 4 is the principal quantitative result. For the complementary-pair family with no acquisitions already held, prices in [1,κ][1,\kappa], κ>1\kappa>1, and at most ss exclusions in distinct pairs give the exact identity

Γs(C)=1+κ−1kRs(C).\Gamma_s(C)=1+\frac{\kappa-1}{k}R_s(C).

Here Rs(C)R_s(C) measures the distance to a cached support that also satisfies the choices forced by exclusions. Finite distortion is equivalent to coverage of every assignment on every ss coordinates. The resulting storage thresholds show that a linear fraction of exclusions forces exponential whole-proof storage even before demanding a nontrivial price approximation. The established support semantics, conditioning methods and covering tools support this new price-and-status characterization.

These results change concrete retention choices. Preserving initial infeasibility and minimum cardinality already resolves 4,240 decisions without additional proofs, and the uniqueness control resolves another 355. The 26 remaining feasible budgets require an affordable alternative witness. Representation also changes the attainable cost. Section 2.6 gives a family with 2k2^k minimal supports and one shared acquisition, a linear-size exact conditioned solver, and a tree-selection cost ratio of k2/(k+1)k^2/(k+1) after deduplication. The theory identifies both the information worth retaining and the structural reason that explicit proof storage can be expensive.

Reviewer_GDqYOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies cached proofs, given what is called an 'evidence budget'.

I find the contribution to be rather incremental and specific.

The writing is extremely hard to follow, making it close to impossible for a non-expert to assess the work.

Critical strengths

None.

Critical weaknesses

The writing makes the paper impossible to understand and assess, at least for a non-expert.

Questions for authors

None

1 comment
AuthorsOpenReview ↗

Reviewer GDqY

To make the budget question concrete, suppose we store the cheapest proof of an answer. After evidence prices change, that stored proof costs 2, while an alternative proof costs 5/35/3. A budget of 11/611/6 can pay for the alternative. This is an observed case in Section 3 of the paper. The question is what a cache must retain so that it can still answer the later budget query correctly.

An affordable stored proof certifies acceptance. A rejection requires information ruling out every affordable proof. Keeping the alternatives can provide that information, and it raises a storage question. How many proofs must be retained to guarantee a given cost approximation when prices change and some evidence becomes unavailable?

Theorem 4 answers this question exactly for a family with two acquisition choices per requirement. Starting with no acquisitions held, prices lie in [1,κ][1,\kappa] for κ>1\kappa>1, and a status can exclude one choice in each of at most ss requirements. The worst cached-cost ratio is exactly 1+(κ−1)Rs(C)/k1+(\kappa-1)R_s(C)/k. The radius Rs(C)R_s(C) counts the largest unavoidable number of expensive choices after the cache has filtered out proofs using excluded evidence. The theorem then gives storage bounds, including an exponential requirement when exclusions affect a linear fraction of the requirements. Section 2.6 shows how shared structure can represent exponentially many alternatives compactly, and why tree-based selection can still lose an increasing cost factor after deduplication.

These are the specific new relationships on which our contribution rests. Your assessment calls the contribution incremental, so the price-and-status characterization and shared-structure separation are the relationships we would ask you to consider. Identifying an equivalent prior result or a particular step that follows directly from one would help us understand that assessment. A specific passage or definition that remains unclear would also allow us to address the presentation concern precisely.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.