Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

An Exponential Lower Bound on Embedding Dimension for Lemma Ranking

Abstract

Lean 4 tactics often take candidate lemmas from vector search by the inner product of goal and lemma embeddings. We show that no fixed embedding dimension suffices to rank lemmas exactly: already on an explicit family of rewrite lemmas whose patterns consist of \(m\) blocks of \(m^2\) differences, the required dimension grows exponentially in \(m\).

Keywords: premise selection, embeddings, automated theorem proving, Lean~4, lower bounds.

BibTeX
@article{IS-Khrulev2026,
  author  = {Khrulev, Ruslan Aleksandrovich},
  title   = {{An Exponential Lower Bound on Embedding Dimension for Lemma Ranking}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {437--440},
}
AMSBIB
\Bibitem{IS-Khrulev2026}
\by R.\,A.~Khrulev
\paper An Exponential Lower Bound on Embedding Dimension for Lemma Ranking
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 437--440
\lang In Russian
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover