acceptodds
Withdrawn from ICLR 2027

Bounding What Lean Gets to See: Candidate Exposure in Proof-Action Ranking

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Tactic rankers determine which proof actions Lean gets to check. Trace matching measures recovery of one recorded action; candidate exposure measures whether the submitted list contains any action Lean accepts. We derive exposure guarantees for similarity retrieval with tactic-family priors. A soft prior of weight λ preserves within-family order and can reverse only comparisons within a similarity gap of λ. Counting these rivals gives a sufficient top-k retention condition under any family prediction; accounting for their shared probabilities gives the exact worst-case rank. Hard routing instead places entire families ahead of a candidate, regardless of similarity. Experiments use 3,723 proof steps from 1,702 theorems in a curated mathlib4 subset. Hard routing moves the first trace-family candidate from mean rank 41 to 531, while soft and unguided ranking have nearly identical trace exact@5 (0.170 and 0.169). Reanalysis of fixed top-five lists with corrected, target-excluding Lean outcomes on 497 matched states gives Accept@5 of 0.412 for unguided retrieval, 0.408 for the soft prior, and 0.342 for hard routing. The hard-minus-unguided difference is -7.04 percentage points (95% theorem-cluster interval [-11.80,-2.59]); the soft difference is -0.40 points ([-1.70,0.84]). Hard routing leads at the first candidate but falls behind by the third. For unguided retrieval, 139 of 205 accepted lists (67.8%) contain no trace hit. The checking cutoff is therefore part of the ranking objective: family predictions should preserve accepted alternatives at the list length the prover actually uses.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
automated theorem proving, Lean 4, formal reasoning, proof-action ranking, learning to rank, tactic retrieval, candidate exposure

Reviews

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

The paper studies a trade-off: prioritising a predicted tactic family can make the first suggestion more likely to succeed but the shortlist less useful. Rankers are judged by candidate exposure, meaning whether the top-k list contains any tactic Lean accepts, rather than by matching the recorded human tactic. Candidates are training records retrieved by TF–IDF cosine similarity. A logistic-regression family prediction enters either as a bounded additive bonus (soft prior) or as a strict family ordering (hard routing).

Contributions. A bonus of weight λ preserves within-family order and reverses only pairs whose similarities differ by at most λ. This gives a sufficient top-k retention condition under any family prediction (Thms 1–2, Cor. 3). Theorem 4 gives the exact worst-case rank over all family distributions. Under hard routing, a candidate is displaced by the full size of every family ranked ahead of it (Prop. 5).

Validation. On 3,723 steps from 1,702 mathlib4 theorems, hard routing halves trace exact@5 (0.169 → 0.082). The fixed top-5 lists were re-scored on 497 states with corrected Lean outcomes. Accept@5 is 0.412 (unguided), 0.408 (soft) and 0.342 (hard; −7.0 pp, 95% CI [−11.8, −2.6]). Hard routing leads at k = 1 but trails by k = 3.

Critical strengths

None

Critical weaknesses

Missing LLM baseline. The only policy is TF–IDF/cosine retrieval plus a logistic-regression family classifier. Similarity-based tactic selection has precedents (e.g., TacticToe’s k-NN) but is uncommon in contemporary provers. The classifier is also weak: Table 1’s hard-routing Family@5 of 0.13 implies its top prediction is right on at most 13% of states. An easy, ICLR-relevant baseline is missing: an LLM (an older open model would do) as the family predictor in Eq. (3), or as a reranker. Since the bounds hold for every prediction, this would show how far realistic behaviour sits from the worst case. The paper never measures that gap, because the retention conditions are not computed on data (App. G). Why is such a baseline absent, when App. G mentions later experiments with larger classifiers and proof search?

Limited theoretical novelty. The theory specialises known geometry for ranking with uncertain linear scoring functions, a literature the paper does not cite. The soft score is a weighted sum with weights (1, λp), so a rival overtakes a candidate only when the weights cross the pair’s switching hyperplane. Thm 2 and Cor. 3 parallel the stability radius of Soliman et al. (SIGMOD 2011). Bounding the worst-case rank by k asks whether the family simplex lies inside the record’s top-k region (Tang, Mouratidis & Yiu, SIGMOD 2017). Thm 1 and Props 5–6 follow directly from the definitions; only Thm 4’s closed form goes beyond this. The paper itself concedes that its invariance and local bounds apply to any bounded group-constant bonus (Sec. 6). Changing the domain to Lean may add empirical value, but it does not establish theoretical novelty.

Questions for authors

None

Reviewer_y8zPOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies how tactic-family priors affect which candidate actions reach Lean under a fixed checking budget. It extends Before Lean Checks: Candidate Exposure in Proof-Action Ranking with rank-retention guarantees, an exact worst-case rank under shared family probabilities, and corrected execution analyses. The central quantity is candidate exposure: whether the submitted top-k list contains at least one tactic that executes without error.

Critical strengths

The exact worst-case rank characterization is a concrete theoretical contribution. The corrections to the earlier checker outcomes are also valuable, and the paper clearly distinguishes trace recovery, acceptance, and immediate closure.

Critical weaknesses

My main concern is whether candidate exposure captures an important bottleneck in theorem proving. Showing that trace matching is incomplete does not establish exposure as the right alternative: the goal is to complete a valid proof within a budget, not merely expose an executable action. Acceptance includes unchanged states, and the interleaving result raises Accept@5 from 41.1% to 45.6% while lowering Close@5 from 15.5% to 12.4%. This does not imply worse eventual proving, but it leaves exposure’s connection to useful progress unresolved.

The fixed-corpus experiments also do not establish how often ranking removes productive actions, rather than failures arising from candidate availability or context transfer. Nor are the retention guarantees evaluated on complete candidate pools. I am not asking for a new state-of-the-art prover, but for evidence that the proposed analysis identifies a consequential failure mode or improves downstream decisions. Without this connection, the work remains a diagnostic study of a particular retrieval pipeline.

Questions for authors
  1. What evidence shows that loss of exposure is a significant bottleneck, rather than candidate availability, tactic transfer, or lack of progress after execution?
  2. Do the additional actions captured by higher Accept@ lead to better subsequent proof progress under a fixed budget? In particular, how should the interleaving acceptance/closure trade-off be interpreted?
  3. How often do the retention guarantees provide nontrivial information on actual proof states, and what practical decision should they guide?
Reviewer_vnANOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how tactic-family predictions affect which retrieved actions enter the top-k list for Lean. The authors derive retention guarantees for soft family priors, including a worst-case rank characterization, and analyze rank displacement under hard routing. Experiments on a mathlib4 subset compare different ranking methods using trace matching, acceptance, and goal closure.

Critical strengths
  1. The paper extends the previous candidate exposure method by providing a bound on rank changes in Theorem 2 and an exact worst-case rank characterization in Theorem 4 that considers the shared probability mass across tactic families.
  2. The experimental results show how the performance of different ranking methods depends on the top-k checking budget.
Critical weaknesses
  1. The formulation is based on a previous candidate exposure work, which is a reasonable topic to study in Lean. However, the practical value and contribution of this approach remain unclear. The experiments do not show consistent improvements over unguided ranking or if the ranking methods lead to more useful proof steps. For example, Table 4 shows that a higher Accept@5 does not necessarily lead to a higher Close@5, it is unclear if improving Accept@k helps overall proof success.
  2. The connection between the theoretical and experimental contributions is not strong enough, the results do not directly evaluate how useful the new theoretical bounds are, such as how much tighter the exact worst-case bound is than the simpler bound in practice.
Questions for authors
  1. Could the authors show how often the bounds in Theorems 2 and 4 guarantee an accepted action remains in the top-k list on the evaluated candidate pools? This would help clarify the connection between the theoretical contributions and the experimental results.

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

Related papers

Discussion (0)

Sign in to comment.