An Exponential Lower Bound on Embedding Dimension for Lemma Ranking
Received: 23 Oct 2026 Revised: 24 Oct 2026 Accepted: 08 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 437–440
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)
RU