acceptodds
Under review as a conference paper at ICLR 2027

Is It a Ranking Failure? A Same-Budget Action-Ordering Audit for Verifier-Guided Logical Reasoning

Abstract

When a verifier-guided reasoning system fails within a fixed budget, can changing only the order of its actions certify the correct answer? We introduce a same-budget audit that answers this question while holding the rules, available actions, verifier, and stopping rule fixed. For finite grounded Horn-style forward chaining, shortest certifying distances define the fraction of instances with some successful ordering within budget. Offline search and saturation-cost arguments determine this ceiling, with explicit bounds when resource-capped search leaves cases unresolved. On 21,677 instances from a restricted ProofWriter test subset and generated PrOntoQA partitions, all 4,988 selected-policy failures at an eight-proposal budget require saturation: the stopping rule waits until every derivable fact has been obtained. Their exact costs are 9–19 proposals, so reordering cannot repair any of these failures: the selected policies attain the ceiling. Lower-budget audits also identify repairable failures, including one ProofWriter instance missed by all thirteen tested policies. Broader data scope, changed rule order, and alternative stopping rules reveal the limits of the zero-gap finding. The audit distinguishes failures caused by action ordering from those constrained by the fixed certification protocol, providing a basis for deciding which component to improve.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Logical Reasoning, Verifier-Guided Reasoning, Budgeted Proof Search, Action Ordering, Failure Diagnosis

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_5nj5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces a same-budget audit to determine whether failures in verifier-guided logical reasoning can be repaired by changing action ordering while holding the rules. For finite grounded Horn-style forward chaining, it defines an ordering ceiling using shortest certifying paths and provides bounds when resource-capped search remains inconclusive. On 21,677 instances from a restricted ProofWriter subset and generated PrOntoQA partitions, all 4,988 selected-policy failures at an eight-proposal budget require 9–19 proposals for saturation and therefore cannot be repaired by reordering. Lower-budget experiments identify repairable failures, including one missed by all thirteen tested configurations. Additional evaluations establish the conditions and limitations of the zero-gap finding.

Critical strengths
  1. The audit asks whether any alternative action ordering can succeed under the same budget and protocol, rather than inferring repairability from a finite policy comparison. Shortest-path certificates and saturation costs make this distinction rigorous.

  2. This paper supplements its eight-proposal zero-gap result with lower-budget controls, expanded data, rule-order perturbations, and alternative stopping rules. These tests expose repairable failures and demonstrate protocol dependence.

Critical weaknesses
  1. The central guarantees are largely direct consequences of the formulation: if the shortest certifying path exceeds the budget, no action-selection policy can succeed; if certification requires saturation and each accepted action adds one novel fact, the cost equals the number of derivable new facts. These observations provide a coherent diagnostic framework, but the paper does not establish a substantially new theoretical result or algorithmic advance.
  2. The experiments assume complete agendas of legal actions, exact verification, and unit-cost transitions. Moreover, matching proposal counts does not match total computation because lookahead and beam policies can perform uncharged internal planning. Without validation beyond this idealized symbolic setting, it remains unclear whether the audit yields useful diagnoses for practical LLM reasoning systems.
Questions for authors
  1. All primary eight-proposal failures require saturation under the chosen stopping rules. What independently motivates the original stopping protocol, and what conclusion about ranking quality remains robust across reasonable certification protocols? Is there a complementary measure that distinguishes ranking quality from the cost imposed by the stopping rule?
  2. Exact search identifies only one repairable instance beyond the thirteen-configuration portfolio at four proposals. Is there any evidence shows that the audit changes intervention decisions or improves outcomes enough to justify its computational cost relative to policy comparisons and failure-class analysis? Given that setting screening used evaluation data and the primary ProofWriter subset arose from a parsing error, which findings remain supported without those selection choices?
2 comments

We thank the reviewer for the constructive comments and questions.

W1 and Q2: Contribution and budget dependence

Our empirical finding is that ordering headroom differs across evaluated budgets, while changing certification can increase success with ranking unchanged. The audit makes these distinctions checkable using standard distance and saturation results.

ProofWriter depths 1/2/3/full 5 give 61,898 questions per budget, excluding the nested historical depth-5 subset. Policies are selected separately at each budget; questions repeat across rows.

BudgetWitness: repairableWitness: nonrepairableSaturation: nonrepairable
1013,81823,242
207,62118,922
4751,96112,734
8603,848
160044

At B=4B=4, 75 witness failures admit ordering repairs and 1,961 do not: the diagnosis extends beyond saturation. At B=8B=8, all six witness failures are repairable. Pooling budgets would hide this distinction. This is not a fixed-policy causal budget comparison.

Strong ordinary controls cover the repairs: relevance/backward construction finds 74 at B=4B=4, the portfolio one, and ordinary witnesses cover all six at B=8B=8. Backward construction also finds all 54 historical repairs, including the one missed by thirteen configurations. Final threshold search adds two infeasibility certificates at B=2B=2, no repair witness. This separates audit evidence from search increment (Section 4.3).

Q1 and Q2: Protocol, ranking quality, and selection

Our original saturation-based negative certification follows a closed-world convention: "not yet derived" does not establish non-derivability. It is not a benchmark requirement; early opposite certification is also valid on these verified instances.

At B=8B=8, freezing ranking while changing stopping increases PrOntoQA successes from 4,559 to 6,320 out of 6,817. These 1,761 successes reflect the changed certification criterion, not better ranking. Under the fixed alternative protocol, target-matched ranking reaches 6,817, repairing the remaining 497 failures. Thus protocol-induced gains and ordering corrections must be separated.

Mean excess proposals isolates avoidable ordering overhead: EC(π)=1∣X∣∑x∈X[Tπ,C(x)−ΦC(x)].E_C(\pi)=\frac{1}{|X|}\sum_{x\in X}[T_{\pi,C}(x)-\Phi_C(x)]. Tπ,CT_{\pi,C} is the uncapped proposal count to certify; ΦC\Phi_C is the minimum over legal orderings under protocol CC. On all 6,817 instances under alternative stopping, fixed query-only relevance averages 1.9139, versus zero for matched relevance. It subtracts optimal certification cost but remains protocol-relative and excludes internal planning.

On these single-premise inputs, with complete agendas and unit-cost fact additions, matched relevance reaches each tested protocol's own ceiling; the original selected policies need not remain optimal across protocols.

Parser correction restores 5,170 questions to full depth-5 ProofWriter (20,030); all nine screened settings are reported. At B=8B=8, full ProofWriter has six repairs and the omitted one-hop PrOntoQA setting has two under its new selected policy. These support conditional diagnostic conclusions, not a universal zero gap. Expanded reporting does not erase evaluation-based screening (Sections 3.4, 4.1–4.4).

W2 and Q2: Diagnostic value and computational cost

The audit provides checkable constraints on interventions. Failure labels and unsuccessful policy trials alone cannot generally rule out every legal ordering; an infeasibility certificate can. For such a case, a successful remedy must change the budget or a fixed system component. Established proof-analysis methods supply most certificates.

Complete agendas, exact verification, and unit costs isolate ordering; candidate omissions and verifier errors require additional modeling. Equal proposals do not imply equal computation. Complete trajectories, including internal planning, on the same 18,127 validation questions at B=8B=8 give:

PolicySuccessesAggregate seconds
Query relevance17,1834.071
One-step query lookahead17,1166.381
Width-four query beam17,14926.984

These shared-host timings are not compute-matched and exclude audit preprocessing and certificate construction.

On 19,269 new world-split questions with original stopping and initial B=8B=8, cheap-check-guided and full-diagnostic menus both solve all questions: 10.22 s each in accounted standalone selection-plus-inference time, versus 100.08 s for direct menu comparison and 5.38 s for fixed budget doubling. Full diagnosis adds no observed gain over cheap checks. These are not joint-run savings or same-budget ordering gains.

Learning and native-task studies show no stable advantage over strong controls. The established result is certified failure attribution, not verified downstream benefit (Sections 4.5–4.6; Appendices I.5–I.6).

Thank you again for your thoughtful review. We wanted to follow up on the questions you raised.

  1. Contribution and budget dependence (W1, Q2). At a budget of four proposals, we identified 75 ProofWriter witness-type failures that reordering could repair and 1,961 for which no legal ordering could succeed. We also reported which cases required exact search.
  2. Certification and ranking quality (Q1). With ranking held fixed, changing the stopping rule yielded 1,761 additional successes. Under the revised rule, matching the ranking to the certification targets resolved the remaining 497 failures. We also reported mean excess proposals as a measure of ranking quality.
  3. Computational cost and practical value (W2, Q2). We reported policy runtimes including internal planning. In the intervention comparison, simple checks and the full audit achieved the same success rate at the same accounted cost.
  4. Data coverage and selection (Q2). We reported results for all nine screened settings and the corrected full depth-5 ProofWriter split, where six failures were repairable at a budget of eight proposals.

We would welcome any further questions. If these results change your assessment, we would appreciate an update to your evaluation.

Reviewer_t7ieOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a framework for determining whether failures in verifier-guided logical reasoning can be repaired solely by changing the order in which available reasoning actions are executed, while keeping the inference budget and all other system components fixed. The authors focus on finite, grounded Horn-style forward chaining. Each state consists of a set of derived facts, and each accepted action adds one previously unknown literal. A local verifier checks whether an action is legal, while a separate stopping rule determines whether the correct answer has been certified. The key quantity is the shortest certifying distance, Φx(F0)\Phi_x(F_0), defined as the minimum number of accepted proposals required to reach a state that certifies the correct answer. This induces a same-budget action-ordering ceiling:

CABord⋆(X)=1∣X∣∑x∈X1[Φx(F0)≤B]CA^{ord \star}_{B}(X) = \frac{1}{|X|}\sum_{x\in X}\boldsymbol{1}[\Phi_x(F_0) \le B]

A failure is ranker-repairable if the selected policy fails within budget BB, but some alternative action ordering succeeds within that budget. For answers that can only be certified after complete saturation, the authors show that the minimum certification cost equals the number of newly derivable facts: Φx(F0)=∣∣Clx(F0)∖F0∣\Phi_x(F_0) = ||Cl_x(F_0)\setminus F_0|. For other cases, the authors use exhaustive shortest-path search, with explicit uncertainty bounds when computation is capped. The framework is evaluated on 21,677 instances from a restricted ProofWriter test subset and generated PrOntoQA partitions, comparing thirteen policy configurations across several proposal budgets. The main experimental findings are:

  1. At B=8B=8, the selected policies achieve 76.99% certified accuracy, matching the exact ordering ceiling. All 4,988 failures require saturation costs of 9–19 proposals and therefore cannot be repaired by action reordering.
  2. At B=4B=4, 54 ProofWriter failures are repairable, including one that none of the thirteen evaluated policy configurations can solve.
  3. At lower budgets, query-relevance-first ordering improves PrOntoQA certified accuracy by approximately 50 percentage points over breadth-first saturation, demonstrating that action ordering can matter when early positive certification is possible.
  4. Expanding ProofWriter to its full test split, perturbing rule order, or changing the PrOntoQA negative-answer stopping rule produces nonzero repairability gaps. The authors conclude that reasoning failures should be diagnosed before being attributed to poor action ranking, because some failures are fundamentally constrained by the certification protocol.
Critical strengths
  1. Clear and practically relevant diagnostic question. The paper asks a useful question that is often overlooked in research on learned search guidance: whether a stronger ranker could theoretically repair a failure under the same inference budget. This separates limitations of the action-selection policy from limitations imposed by the underlying reasoning system. Such a distinction could inform where to invest development effort—improving ranking, modifying termination criteria, expanding the action space, or increasing computation.
  2. Well-defined formal framework. The paper clearly specifies which components remain fixed during the audit, including the rule set, candidate agenda, verifier, transitions, stopping criterion, and budget. The distinction between local action validity and progress toward certification is particularly valuable. Proposition 1 formalizes the connection between shortest certifying distances and the best achievable performance under action reordering.
  3. Rigorous handling of incomplete exhaustive search. A notable strength is the explicit treatment of resource-capped searches. Rather than treating unfinished searches as failures or assigning approximate distances, the authors derive deterministic lower and upper bounds on the ordering ceiling and repairability gap. The distinction between search incompleteness and actual non-repairability is important for the correctness of the analysis.
  4. Multiple controlled experiments examining the limits of the main finding. The authors do not rely exclusively on the zero-gap result. They examine different budgets, a broader ProofWriter population, rule-index permutations, alternative stopping criteria, and additional PrOntoQA generation seeds. These experiments reveal when action ordering matters and when the fixed certification protocol dominates performance.
  5. Concrete evidence that finite policy comparisons can miss repairable failures. The four-proposal ProofWriter example is particularly informative. The exhaustive audit identifies a successful trajectory that none of the thirteen tested policies discovers. This provides a concrete demonstration of the distinction between the performance of a finite policy portfolio and the theoretical ceiling over all valid action orderings.
Critical weaknesses
  1. The primary zero-gap finding is largely determined by the stopping protocol. The central experimental conclusion is that none of the 4,988 selected-policy failures at B=8B=8 can be repaired through action reordering. However, all these failures correspond to answers that require complete saturation under the chosen stopping rules. Given the unit-cost assumption that every accepted action adds exactly one new literal, the number of proposals required for saturation is necessarily invariant to ordering. Thus, once the failure composition is established, the zero-gap result follows directly from the certification protocol and the closure-size identity. This raises a question about the empirical significance of the headline result. It demonstrates that the selected policies are optimal under the specified protocol, but it provides limited evidence about the effectiveness of their ranking strategies. The stopping-rule sensitivity experiment further illustrates this concern. When PrOntoQA is allowed to certify negative answers upon deriving the explicit opposite of the query, the ordering ceiling increases substantially and 497 failures become repairable.
  2. Limited methodological novelty beyond established shortest-path and fixed-point reasoning. The proposed ordering ceiling is fundamentally based on shortest-path reachability in a finite state graph, while the saturation-cost result follows from classical Horn-clause fixed-point semantics under unit-cost fact addition. The main contribution is therefore the diagnostic formulation and its empirical application, rather than a new search algorithm or a substantially new theoretical technique. This is a legitimate contribution, but the paper would benefit from demonstrating more clearly what additional insight the audit provides beyond straightforward analyses of proof length, closure size, and existing search-policy failures.
  3. Limited applicability to realistic verifier-guided reasoning systems. The framework assumes that the complete set of legal actions is available, that verification is exact, and that every accepted proposal adds exactly one new literal. These assumptions exclude several central challenges in contemporary LLM-based reasoning systems, including incomplete candidate generation, hallucinated reasoning steps, noisy verification, repeated actions, variable computational costs, and nonmonotonic revisions. Furthermore, all evaluated policies select only legal actions, so every proposal is accepted. This eliminates the cost of invalid proposals, which is often a major source of inefficiency in actual verifier-guided reasoning. Consequently, the paper's conclusions may not transfer directly to the systems used to motivate the study.
  4. The primary experimental conclusion is sensitive to evaluation design. The authors acknowledge that the zero-gap finding applies to a restricted ProofWriter subset, a particular rule ordering, a specific stopping protocol, and B=8B=8. Importantly, restoring the excluded ProofWriter questions introduces six repairable failures at the same budget, while several rule-index permutations also introduce repairable failures. The evaluation settings were additionally selected through a screening process that included evaluation examples, although the final repairability gap was not used for selection. These factors limit the representativeness of the primary result and make it difficult to determine how frequently ranker-repairable failures occur in broader reasoning tasks.
  5. The paper does not demonstrate that the audit improves a reasoning system. Although the audit can identify repairable failures and provide successful trajectories, the authors do not train a new ranker, use the audit to improve an existing policy, or measure subsequent gains. This leaves an important gap between the proposed diagnostic capability and its practical value. For example, it remains unclear whether shortest-path witnesses can be converted into useful training signals or whether the resulting policy would generalize to unseen problems.
  6. Computational scalability and budget accounting remain concerns. The exhaustive distance computation can be exponential in the number of derivable facts. The experiments therefore impose limits on recursive state visits and runtime. The paper also measures inference budgets in terms of action proposals, without accounting for internal planning costs. Some evaluated policies use lookahead or beam search, but this additional computation is not charged against the proposal budget. While this is consistent with the paper's ordering-only objective, it weakens comparisons of practical inference efficiency. A more detailed characterization of audit runtime, memory consumption, and scalability would be valuable.
  7. The positive-control results are less informative than their magnitude suggests. The approximately 50-percentage-point improvements from query-relevance-first ordering are striking. However, these experiments compare against a breadth-first policy that certifies no instances at the selected lower budgets, while the query-directed policy certifies all positive instances and no negative instances. The improvements therefore largely reflect whether the policy prioritizes a short positive proof over unrelated deductions. These experiments establish that ordering can matter, but they do not demonstrate that the proposed audit produces better action-selection policies or discovers a previously unknown reasoning strategy.
Questions for authors

Q1. What is the main insight of the zero-gap result beyond saturation-cost invariance? Since all 4,988 residual failures require complete saturation, and saturation cost is invariant to action ordering under the paper's assumptions, the zero-gap conclusion follows directly once these failures are classified. Could the authors clarify what additional information the exhaustive action-ordering audit provides in this setting beyond inspecting the answer classes and computing closure sizes? Q2. Why is the saturation-only negative stopping rule the primary evaluation protocol for PrOntoQA? The paper shows that all 3,377 original PrOntoQA negative instances have a derivable explicit opposite of the query. Allowing this opposite to certify a negative answer increases the number of successful instances at B=8B=8 from 4,559 to 6,320, with an ordering ceiling of 6,817. Given this substantial difference, what motivates using saturation-only negative certification as the primary protocol? Would early negative certification be more representative of practical logical reasoning systems? Q3. How can the framework be extended to incomplete or imperfect action generation? Realistic verifier-guided reasoning systems often generate only a subset of possible actions, and some proposed actions are invalid. Could the authors discuss how the ordering ceiling would change when candidate generation is incomplete, or when different policies produce different candidate sets? In particular, can the proposed diagnosis distinguish failures caused by poor ranking from failures caused by missing candidate actions? Q4. Can the audit be used to improve a learned ranking policy? The paper identifies shortest successful trajectories and demonstrates that exhaustive search can discover solutions missed by the tested policy portfolio. Could these trajectories be used as supervision for training a ranker, for example by labeling distance-decreasing actions as preferred decisions? Even a small experiment showing improved held-out certified accuracy would help establish the practical usefulness of the framework. Q5. How does the repairability gap behave across a broader range of budgets and problem difficulties? At B=8B=8, the selected policies attain the ceiling, whereas at B=4B=4, 54 ProofWriter failures are repairable. Could the authors provide a more systematic analysis of the repairability gap as a function of budget, proof depth, closure size, and branching factor? This would help determine whether the zero-gap result reflects a general property of the tested policies or a particular operating point. Q6. How scalable is the exact audit? What are the distributions of runtime, memory usage, and explored states across the evaluated instances? How do these quantities scale with the number of derivable facts and available actions? Since the method relies on exhaustive search for witness-certification cases, it would be useful to identify the practical problem sizes at which the audit becomes infeasible. Q7. How should computational budgets be compared when policies perform different amounts of internal planning? The paper charges one unit per proposed action but does not charge for internal lookahead or beam search. Could the authors provide a supplementary comparison using total computational cost or wall-clock time? This would clarify whether policies that achieve better proposal efficiency also provide practical inference-time improvements. Q8. How representative are the selected evaluation settings? The paper acknowledges that setting selection involved screening evaluation pools and that the PrOntoQA splits guarantee identifier-level rather than template-level disjointness. Could the authors report repairability statistics across all screened settings, rather than only those retained for the primary audit? This would help assess whether the observed patterns generalize beyond the selected case studies.

3 comments

We thank the reviewer for the constructive comments and questions. We find little same-budget ordering headroom under the reported original protocols; changing certification can expose repairable target mismatches. References are to the revised manuscript.

1. Q1, W1 (main result), W2: What does the audit add?

For the original B=8 result, successes and saturation costs suffice: all 4,988 failures require 9–19 proposals. Exhaustive search is unnecessary here. For witness certification, however, closure size generally does not determine minimum cost, and failed finite policy trials cannot rule out successful alternatives. The audit separates verified repairs, certified nonrepairability, and unresolved cases.

Across expanded ProofWriter, 23,481 witness failures comprise 81 repairable and 23,400 certified nonrepairable records, including two certified by threshold search. These are instance–budget records over five budgets, excluding the nested historical d5 cohort. A strengthened backward constructor finds all 54 historical repairs; exact search adds no successful witness in these comparisons. Our contribution is the same-budget counterfactual framework and evidence accounting using established methods, rather than a new shortest-path algorithm. (§4.3, Table 3; Appendix I.2.)

2. Q2, W1 (stopping): Why use saturation as the original protocol?

Saturation follows the evaluator's closed-world convention, but this alone does not justify privileging it. All 3,377 original negative instances have opposite witnesses; verified query/opposite consistency supports early certification on this cohort. We therefore report both protocols. On the same 6,817 instances at B=8:

Protocol / rankingSuccessesCertified ceilingRepairable
Original4,5594,5590
Early opposite / frozen ranking6,3206,817497
Early opposite / dual-target QRF6,8176,8170

The stop-only comparison was in the submission. Added dual-target QRF repairs all 497 cases without regressions. These cases already used QRF, so changing its targets suffices. Changing certification alters the ceiling; correcting ranking realizes the opportunity within that fixed protocol. (§4.2; Appendix I.1.)

3. Q3, W3: Incomplete candidates and applicability

Let Φ\Phi be the minimum certification cost with the complete legal agenda and Φg\Phi^g the cost under a fixed, policy-independent candidate restriction. With the same initial state, retained transition effects/costs, and an unchanged sound certification rule, Φg≥Φ\Phi^g\ge\Phi. For an observed failure:

  • Φ>B\Phi>B: no full-agenda ordering can succeed.
  • Φ≤B<Φg\Phi\le B<\Phi^g: candidate restriction removes every budget-feasible path.
  • Φg≤B\Phi^g\le B: repair remains possible within the restricted candidates.

Diagnosis requires verifiable witnesses/bounds and candidate behavior at counterfactual states; failed rollouts are insufficient. An empty restricted agenda does not establish logical saturation. Policy-dependent generation changes the action system and requires explicit history/randomness. Rejected attempts must retain their costs; the reported symbolic policies propose only legal actions. Variable costs, nonmonotonic transitions, and noisy verification require weighted paths, revised states, and independent correctness checks, respectively. These are conditional extensions, not experimentally validated guarantees for general LLM systems. (§5; Appendix I.7.)

4. Q4, W5, W7: Learning and practical value

We tested diagnostic state selection for ranker continuation and, separately, budget-feasibility action supervision without existing teacher fields. Neither establishes stable incremental gains. Budget-feasible actions need not decrease shortest distance. Three of five primary contrasts from the later study follow (Qwen2.5-1.5B, five seeds, 4,096 held-out questions, B=4, full resource window):

Diagnostic supervision minusSuccess difference (pp)99.5% CI
Strengthened ordinary feedback-0.1123[-0.8154, +0.6616]
Additional ordinary search+0.0098[-0.4492, +0.4859]
Integer optimization+0.0049[-0.4712, +0.4737]

All five primary intervals include zero. Diagnostic, additional-search, and integer-optimization labels agree on all 27,974 training states, limiting the demonstrated supervision advantage; costs and training exposure can differ. For W5, Response 2 demonstrates effective correction, but simple target matching does not establish incremental audit value over direct target inspection. For W7, the approximately 50 pp positive control demonstrates short-positive-proof prioritization, not an audit-derived or learned gain. Stable downstream advantage over strong controls remains unestablished. (§4.6; Appendix I.6 reports both studies and all comparisons.)

The continuation addresses coverage and computational cost.

Continuing our response, we address Q5–Q8, W4, and W6. Responses 1–4 above cover the diagnostic contribution, stopping protocol, applicability, and intervention/learning evidence.

5. Q5, Q8, W4: Budget coverage, structure, and representativeness

We report all nine screened settings at B=1,2,4,8,16. The full ProofWriter d5 evaluation also restores 5,170 adapter-excluded instances. Counts of repairable failures under the original stopping protocol are:

SettingInstancesB=1B=2B=4B=8B=16
ProofWriter d313,03400700
Historical ProofWriter d514,860005400
Full ProofWriter d520,030006860
PrOntoQA h11,25200020

ProofWriter d1/d2 and PrOntoQA h2–h5 have zero repairable failures at all five budgets. Historical policy choices remain frozen; added settings use validation-only selection. Full d5 contains the historical cohort and is not an independent sample; other ProofWriter depths retain the original filter. Across the nine screened settings and five budgets, the largest gap is 0.3634 pp. A zero gap at low budgets can mean that no ordering can succeed, rather than that the task is easy.

For full d5 at B=4, closure-growth bins ≤8\le8, (8,16](8,16], (16,32](16,32] contain 45/10,892, 22/8,878, and 1/260 repairable instances. Mean-branching bins ≤4\le4, (4,8](4,8], (8,16](8,16] contain 65/17,033, 3/2,890, and 0/107. These descriptive strata show no consistent increasing pattern. Closure growth counts newly derived facts; branching is measured along a fixed QRF trajectory. Official dataset depth is not exact certification length.

Reporting every screened setting addresses missing coverage, but does not undo the original evaluation-pool behavior/accuracy screening, even though the final gap was not a screening criterion. Rule-order sensitivity also remains: four of ten permutations each yield one B=8 repair. Stopping sensitivity is quantified in Response 2. Thus, small gaps are a measured result at the reported settings and budgets; template independence and broader representativeness remain unestablished. (§§4.1, 4.4; Appendix I.4.)

6. Q6, Q7, W6: Proposal budgets, policy runtime, and audit cost

We separate the number of proposals from policy runtime, which includes internal planning, and the additional cost of certification.

Complete historical audits. The ProofWriter audit covers 14,860 questions and takes 228.58 s, with per-question cumulative evaluator P95 of 42.01 ms. The four PrOntoQA validation-plus-evaluation pools each contain 1,715–2,000 questions; whole-audit times range from 72.31–283.84 s and cumulative evaluator P95 from 22.42–27.88 ms. These are per-pool ranges, not pooled totals. (Appendix B.)

State and memory measurements. Across 213 isolated descriptive samples, median/P95 recorded search states are 19/19 and process memory is 19.83/20.12 MB, including interpreter/import overhead. Of these samples, 210 are already cheaply resolved controls forced through B=4 search; they are not a population-weighted audit profile.

Stress tests. At B=16 with a one-million-state/10 s search cap, 216 grid points yield 87 exact distances, 30 budget-infeasibility certificates, and 99 unresolved search outcomes. Unresolved counts per 54 points are 0/6/42/51 with 0/8/32/128 distractors. Corresponding raw-search median times are 0.000292/0.0564/8.355/5.902 s, including capped runs; state-cap termination affects these timings. Maximum process memory is 249.2 MB. Existing structural bounds or witnesses resolve all 216 budget queries. This demonstrates raw-search limits but does not establish the combined audit's failure boundary or an end-to-end speedup. Capped searches remain unresolved unless other evidence certifies the answer.

Policy runtime. On the same 18,127 validation questions at B=8:

PolicySuccessesTotal runtime (s)
QRF17,1834.071
Query lookahead17,1166.381
Query beam, width 417,14926.984

These timings include in-memory setup, internal planning, state updates, and successful-path replay, but exclude offline audit preparation. They provide the wall-clock comparison requested in Q7 and expose planning overhead hidden by proposal counts. They are shared-host measurements, not equal-total-compute accuracy comparisons or stable deployment-latency estimates. Our evidence supports offline audit feasibility on these symbolic workloads, with explicit abstention when certification is unavailable; it does not establish general scalability. (§4.5; Appendix I.5.)

Thank you again for your thoughtful review. We wanted to follow up briefly on our two responses to the questions you raised.

  1. Audit and stopping rule (W1, W2, Q1, Q2). We clarified what the audit can establish beyond testing a finite set of policies. Under early negative certification, changing the ranking target to include both the query and its opposite repaired all 497 remaining failures.
  2. Applicability and learning (W3, W5, W7, Q3, Q4). We discussed how incomplete candidate generation affects the diagnosis and reported two studies testing whether audit feedback improves ranking on held-out questions.
  3. Evaluation coverage (W4, Q5, Q8). We reported results for all nine screened settings across five budgets, including analyses by closure size and branching. We also reported results for the full ProofWriter depth-five split.
  4. Computational cost (W6, Q6, Q7). We reported audit runtime, memory use, and stress-test results, alongside policy timings that include internal planning.

We hope these responses are helpful. If there is anything you would like us to clarify or discuss further, we would be happy to do so.

Reviewer_JXTmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper asks whether a failed verifier-guided reasoning trajectory could have succeeded within the same proposal budget by changing only its action order. It studies finite grounded Horn-style forward chaining with a complete agenda, exact verification, and a fixed stopping rule. The shortest certifying distance determines whether an instance can succeed within budget; aggregating these tests gives the action-ordering accuracy ceiling. Successful trajectories, saturation costs, and exhaustive search establish budget feasibility, with explicit uncertainty when search is capped. On the primary cohort of 21,677 ProofWriter and PrOntoQA instances at eight proposals, all 4,988 failures require saturation beyond the budget, so the selected policies attain the ceiling. Lower budgets and changes to data scope, rule order, and stopping rules reveal repairable failures and delimit this result.

Critical strengths
  1. The counterfactual is carefully specified. A policy comparison can establish that a particular failure is repairable, but cannot establish that every alternative ordering would fail. The paper makes this distinction precise and keeps the verifier, available actions, transitions, stopping rule, and budget fixed. Its treatment of unfinished searches is also sound: a cap hit is not interpreted as non-reachability, and an observed successful trajectory remains a valid witness even if exhaustive search does not finish. I found no substantive problem with the shortest-path characterization or the saturation-cost argument under the stated assumptions.

  2. The sensitivity studies make the empirical claim substantially more credible. The authors do not present the zero gap as a general property of either benchmark. Restoring the excluded explicit-negative premises produces six repairable ProofWriter failures at eight proposals, and some rule permutations also introduce nonzero gaps. More importantly, allowing an explicit-opposite certificate changes the PrOntoQA result considerably: successes increase from 4,559 to 6,320, and all 497 remaining failures become repairable under the new protocol. Holding action choices fixed in that experiment is appropriate for isolating the stopping-rule effect. The four-proposal ProofWriter example missed by every tested configuration also gives a concrete illustration of information that a finite policy comparison cannot supply.

Critical weaknesses
  1. The main empirical finding has limited explanatory reach beyond the chosen certification protocol. Once all residual failures require full saturation, their invariance to ordering follows directly from counting the new literals, since every accepted action adds exactly one. The empirical observation is therefore that the selected policies have already solved every instance admitting an early witness under the original stopping rules within eight proposals in this cohort. This is a legitimate finding, but offers fairly limited evidence about ranking failures in verifier-guided reasoning more broadly.

    The PrOntoQA stopping rule is particularly consequential: every original negative instance has a derivable explicit opposite, yet the primary protocol requires saturation. The alternative-certificate experiment correctly exposes this dependence. Together with screening settings using the evaluation pools and the initial restriction of ProofWriter, it makes the zero-gap result a conditional case study. The paper acknowledges these qualifications clearly. My concern is that the resulting scientific insight is still narrow relative to the breadth of the motivating question, rather than that the reported zero gap is incorrect.

  2. The additional practical value of the exact audit is not yet well established. The policy bound is an elementary shortest-path observation, and the primary conclusion can be obtained from successful rollouts and closure counts without computing shortest witness proofs. At four proposals on ProofWriter, the finite portfolio finds 53 of the 54 repairable selected-policy failures; exhaustive analysis identifies one further case. That case is useful, but the paper does not show whether the audit reliably uncovers substantial opportunities missed by inexpensive diagnostics, or whether its witnesses help improve a ranking policy.

    This matters because exhaustive search can be exponential, while the studied policies operate over complete symbolic agendas and never propose invalid actions. There is no learned ranker here, and the paper supplies no systematic runtime or memory profile for the offline audit. A focused evaluation on a more varied set of witness-certification failures, even within the same Horn framework, could make a stronger case: it could establish how often exact auditing changes the diagnosis and at what cost. I do not think a new application domain is necessary, but the present evidence leaves the method's useful operating range unclear.

I lean toward weak rejection. The paper is careful about correctness and unusually explicit about what its experiments establish. My reservation is the size of the contribution: the central theory is straightforward, and most of the empirical diagnosis follows from the stopping convention and the observed answer classes. A stronger demonstration that the audit changes a useful modeling or search decision would materially improve my assessment.

Questions for authors
  1. The paper already explains the unnecessary detour in the four-step witness missed by the portfolio. Across the 54 repairable four-proposal ProofWriter failures, are there recurring dependency structures or ranking errors that distinguish them from instances where the selected policy already uses the minimum budget? A systematic account would help establish whether the audit offers guidance beyond individual existence witnesses.

  2. Under the alternative PrOntoQA stopping rule, how many of the 497 repairable failures disappear if query relevance targets both the query and its explicit opposite, or if the existing policy configurations are reselected on validation data? The current frozen-policy control is well designed; this separate experiment would clarify whether the remaining gap mainly reflects the original targeting convention or a harder ordering problem.

  3. Could you provide procedures that regenerate the seed, rule-permutation, and alternative-stopping studies, rather than only their archived results, as described in Table 17? For the exact witness searches, a runtime and explored-state profile as problem size grows would also help establish when the audit is feasible.

4 comments

Thank you for recognizing the controlled counterfactual and sensitivity studies.

W1:

We agree that the zero gap is conditional on the stopping rules, restricted cohort and evaluation-pool screening. Expanded results cover all nine screened settings and the full 20,030-question ProofWriter split, where B=8B=8 has six repairable failures. The contribution is a certificate-based diagnosis of whether reordering can help under a fixed protocol, supported by recurring failure analysis, a tested target correction, and a measured comparison with cheap diagnostics.

Q1 / W2: Recurring structure and local repair

We analyzed all 54 repairable ProofWriter failures in the original cohort at B=4B=4. QRF's static distance ignores joint premise requirements. We flagged an action when every shortest static chain from its conclusion requires a co-premise that is underivable or derivable only after a certification target is reached. Controls are successes of the same QRF policy whose trajectories attain the minimum certification length, matched by answer and exact initial distance.

Flagged structureFailuresMatched successes
First selected action45/541/54
Any initial legal candidate47/541/54

The 54 pairs reuse 43 controls. Source family is unmatched and candidate pools differ, so this comparison is descriptive. The successful exception uses the flagged action in a minimum-length proof: a blocked static shortcut does not make the action useless.

To establish consequences for the budget, we fixed each observed prefix just before the first action that destroys feasibility and checked every legal alternative. In 38 cases, all minimum-score actions preclude completion within the remaining budget, but a lower-priority action permits it; in 16, a feasible alternative exists within the tied minimum-score set. This identifies when changing the current priority is necessary and when a feasible choice exists within ties; subsequent actions may also need to change.

Q2 / W1-W2: A concrete target correction

Keeping the alternative stopping rule and B=8B=8 fixed:

InterventionRepairedRemainingRegressions
Query-only validation reselection854120
Fixed QRF targeting qq and its opposite49700

Repairs/residuals concern the original 497 failures; regressions concern previously successful instances. All 497 occur in the five-hop subset, where the original selected policy is QRF. Changing only its targets raises successes from 1,287/1,784 to 1,784/1,784. Reselection uses validation data; constructing the opposite uses no gold answers.

The original frozen-policy experiment isolates the stopping-rule effect. This separate control shows that target matching suffices to eliminate the residual gap under the alternative protocol, providing a specific policy correction.

Q3 / W2: Reproduction, cost and added diagnosis

The revised supplement includes regeneration drivers, original inputs, frozen selections, commands and the generator commit for all three studies (REPRODUCE.md). Historical validation regenerated 1,200 seed records and replayed permutation seed 0 over 21,677 instances (106,840 policy-budget-condition outcomes; zero mismatches). This does not establish a fresh ten-seed replay or clean-install validation.

For 54 base configurations at each distractor count (216 cases), B=16B=16, raw search was capped at 10610^6 states or 10 s:

DistractorsMedian sMedian statesCappedMax RSS MB
00.00029226.50/5422.3
80.05644,7596/54100.2
328.3551,000,00042/54224.9
1285.9021,000,00051/54249.2

Times include capped runs; caps leave search unresolved. States count unique discoveries, including queued states; RSS is whole-process peak memory. The lower time at 128 distractors reflects state-cap termination. Bounds and backward witnesses settle all 216 cases.

Across ProofWriter depths 1-3 and full depth 5, B=1,2,4,8,16B=1,2,4,8,16, excluding the nested historical subset, 23,481 witness-failure instance-budget records yield 81 records certified repairable by witness controls and 23,398 infeasibility certificates from structural analysis. Exact search adds two budget-infeasibility certificates and no new repair witnesses (B=2B=2; 10/18 states; 0.195/0.483 ms). Stronger backward controls also cover all original 54 failures.

These results support using verified witnesses and structural bounds first, reserving exact search for unresolved cases. Q1 identifies local repair conditions, Q2 validates a target correction, and Q3 measures exact search's small extra coverage and its costs under the tested stress conditions. This supports a bounded diagnostic use, while general policy improvement remains unestablished.

Thank you again for your thoughtful review. We wanted to briefly follow up on the main findings in our response.

  1. Scope (W1). We reported results for all nine screened settings and found six repairable failures at B=8 on the full 20,030-question ProofWriter depth-5 split.
  2. Recurring ranking errors (Q1, W2). At B=4, a blocked shortcut appeared in the first action in 45/54 failures versus 1/54 matched minimum-length successes, and the local audit showed that 38 failures required a lower-priority action at the critical step while 16 had a feasible alternative within the tie.
  3. Target correction (Q2, W1–W2). Under the alternative PrOntoQA stopping rule at B=8, targeting both the query and its opposite repaired all 497 failures, while validation-based reselection repaired 85, with no regressions in either case.
  4. Reproducibility, cost, and added value (Q3, W2). We provided reproduction procedures, profiled search costs across 216 synthetic cases, and showed that exact search added two infeasibility proofs and no new repair witnesses beyond inexpensive diagnostics on ProofWriter.

We welcome any further questions. If these additions address your concerns, we would be grateful if you would consider updating your rating.

Targeting both the query and its opposite repairs all 497 remaining PrOntoQA failures under the alternative stopping rule. That settles my question about why the gap appeared there. On ProofWriter, I found the split among the 54 repairable failures particularly informative. At the critical step, 16 had a feasible choice tied for first, while 38 required taking a lower-ranked action. Those suggest different fixes to the ranker.

What still limits my assessment is how often exact search changes the diagnosis. In the expanded ProofWriter study, the cheaper checks identified every repairable case among the 23,481 witness-failure instance–budget pairs. Exact search settled two additional cases, both infeasible. There is value in being able to certify those last two. On these benchmarks, though, the cheaper checks already tell us nearly everything about where reordering can help. That’s why I’m staying at 2 (weak rejection).

Thank you for encouraging us to examine what exact search adds. Your comment prompted two further checks on the 54 ProofWriter failures. Starting from each trajectory’s initial state, inexpensive checks alone identified the first loss of budget feasibility in all 54 cases. They also matched the exact results for all 169 candidate actions at those steps, recovering the distinction you highlighted: 38 cases required a lower-ranked action, while 16 had a feasible choice tied for first.

We appreciate your careful reading and will report both comparisons in the revision. We hope you will also consider what the audit framework contributes here: even when inexpensive checks suffice, the evidence can pinpoint where a trajectory loses feasibility and which ranking choice could have preserved it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.