- 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
-
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.
-
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
- 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.
- 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
- 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?
- 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
Thank you again for your thoughtful review. We wanted to follow up on the questions you raised.
- 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.
- 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.
- 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.
- 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.
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.
At B=4, 75 witness failures admit ordering repairs and 1,961 do not: the diagnosis extends beyond saturation. At B=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=4, the portfolio one, and ordinary witnesses cover all six at B=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=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=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(π)=∣X∣1∑x∈X[Tπ,C(x)−ΦC(x)]. Tπ,C is the uncapped proposal count to certify; ΦC is the minimum over legal orderings under protocol C. 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=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=8 give:
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=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).