leanprover / leanprover/lean4

mepo: score function over-rewards tiny generic theorems

Open
#13,749 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

P-medium
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

For a goal like a + b = b + a : Int, mepoSelector ranks Int.add_comm around position 36 (and around 67 without applying the wasOriginallyTheorem filter that the other selectors in this directory already use). The top 30 are score-1.0 entries like Eq.symm, Eq.trans, proof_irrel, congrArg, funext, Eq.subst, congr.

These are real theorems, so the wasOriginallyTheorem filter doesn't help them. They score 1.0 because

score = M / (M + R')
  where  R  = relevant ∩ candidate
         R' = |candidate \ relevant|
         M  = Σ weight(n)  for n in R

A one-symbol theorem like Eq.symm (symbol set {Eq}) whose lone symbol is in relevant scores M/M = 1 no matter what M is, since R' = 0. The formula rewards fraction of overlap, not amount.

Two candidate fixes I'd like opinions on, both of which compose with the lexicographic-by-(iteration, score) ordering we likely want anyway (cf. lean#13747 and Xavier's report):

(1) Additive damping in the denominator. Replace M / (M + R') with M / (M + R' + γ) for some γ > 0. A theorem with M = 1 then scores 1/(1+γ) instead of 1, while one with M = 8 scores 8/(8+γ) — still close to 1. One tunable knob. Changes threshold semantics (every score drops), so the p = 0.6 schedule would need retuning.

(2) Tiebreak within an iteration by |R|. Keep the score formula and threshold. Sort within each iteration by (score desc, |R| desc) instead of just score desc. A theorem matching 8 of the goal's symbols then ranks above one matching 1, even when both score 1.0.

(1) changes which premises clear the threshold. (2) only changes their order — never changes the accepted set.

cc @xgenereux — opening this rather than picking one because either direction wants benchmarks before tuning, and I'd like your read first.

🤖 Prepared with Claude Code

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by locating mepoSelector and comparing its scoring, filtering, and ordering with the other selectors in that directory; review lean#13747 and Xavier's report for the intended ordering. Add or run benchmarks for both damping and |R| tie-breaking, and document which approach preserves the desired threshold and ranking behavior.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.