Structured Hints for Sample-Efficient Lean Theorem Proving
Zac Burton · 2026
Read Structured Hints for Sample-Efficient Lean Theorem Proving by Zac Burton (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16172.txt.
Introduction
Zac Burton tests if plain hints help top proof models find Lean proofs. His 2026 preprint deals with neural proof tools. Top tools like DeepSeek Prover join language models with trial based learning. They score well through long and rich training. Burton asks if such trained tools still gain from plain form hints at use time.
He gives each tool a fixed prompt with form cues. He then checks proof scores with and sans the hint. Gains would show that cheap hints still count at the top. No gains would show training has soaked up that help. The test is light, cheap and easy to rerun.
Catalog record
| CREATOR | Zac Burton |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-16172
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Structured Hints for Sample-Efficient Lean Theorem Proving Zac Burton Abstract State-of-the-art neural theorem provers like DeepSeek-Prover-V1.5 combine large language models with reinforcement learning, achieving impressive results through sophisticated training. We ask: do these highly-trained models still benefit from simple structural guidance at inference time? We evaluate a lightweight intervention—a fixed prompt schedule over 15 common tactic skeletons—on the miniF2F benchmark. This simple approach yields 21.7% pass@16 compared to 15.2% for standard sampling from the same model, a 43% relative improvement using the same number of samples ( k = 16 k=16 ) and same maximum generation length (1024 tokens). Our results suggest that even capable RL-trained provers underutilize structural priors available in the tactic language, and that simple inference-time guidance remains a cheap, complementary boost. 1 Introduction Recent advances in neural theorem proving have demonstrated remarkable success by combining Large Language Models (LLMs) with formal verification environments like Lean. Systems leveraging reinforcement learning (RL) and massive tree searches have achieved strong results on formal proof benchmarks [ 6 , 2 , 5 ] . The prevailing paradigm often assumes that with sufficient RL training and inference-time compute, models will implicitly internalize the necessary structural and tactic-level priors required for formal proofs. However, despite these capabilities, neural provers remain surprisingly brittle. Even RL-trained models frequently fail due to low-level structural errors—generating invalid syntax, hallucinating identifiers, or getting “lost” in the proof state space—rather than a lack of mathematical insight. This disconnect raises a critical question for resource-constrained settings: Has RL actually solved the structural problem, or can lightweight, fixed-schedule guidance still yield significant gains? In this work, we investigate whether enforcing structural priors at inference time improves performance under the same inference budget. Unlike recent approaches that rely on expensive stochastic search or massive sampling (e.g., k=1024 ), we propose a lightweight Intermediate Representation (IR) with a fixed prompt schedule. By guiding the model with structural skeletons, we probe the behavioral limits of current RL-trained provers. Our results on the miniF2F benchmark show that this simple structural guidance yields a 43% relative improvement over the baseline (15.16% \to 21.72%) under a fixed, low-inference budget ( k=16 ). Our paired analysis shows strong asymmetry (19 wins vs. 3 losses), indicating that tactic skeletons provide a robust boost rather than merely trading off between problem types. 1.1 Contributions Our primary contributions are as follows: • We introduce a Lean-aware Intermediate Representation (IR) with a fixed prompt schedule that provides structural guidance at inference time. • We demonstrate that this lightweight intervention significantly outperforms standard sampling on miniF2F under identical inference budgets ( k=16 , 1024 tokens). • We provide a failure-mode analysis showing that error distributions are similar between methods; gains appear to come from a higher hit-rate on successful completions rather than systematic avoidance of particular error types. 2 Related Work Neural Theorem Proving The integration of Language Models with formal proof assistants has evolved rapidly. Early systems like GPT-f [ 4 ] and PACT [ 3 ] demonstrated that transformers could generate tactic scripts. More recent efforts, such as LeanDojo and its associated ReProver model [ 7 ] , introduced retrieval-augmented generation to handle the vast library of Lean premises. The current state-of-the-art is dominated by models trained with massive Reinforcement Learning (RL) pipelines, notably DeepSeek-Prover-V1.5 [ 6 ] for Lean tactic generation and AlphaGeometry [ 5 ] for geometry-specific formal reasoning, which rely on iterative self-improvement and synthetic data generation to achieve strong performance on formal benchmarks. Neuro-Symbolic Reasoning Recent work has moved towards hybrid systems that interleave natural language reasoning with formal verification. Aristotle [ 1 ] achieved state-of-the-art results on IMO problems by generating and formalizing semantic lemmas (intermediate mathematical statements) to bridge the gap between informal reasoning and formal proof. Our work targets a complementary, lower-level efficiency constraint. Rather than generating new mathematical lemmas (which requires heavy reasoning), we focus on syntactic skeletons —enforcing valid tactic structures (e.g., induction , cases ) at the start of generation, serving as a hint for the LLM’s approach to the problem. We demonstrate that this lightweight structural guidance captures significant performance gains in resource-constrained environments where full lemma synthesis is too costly. 3 Method To evaluate the impact of structural guidance under strict inference constraints, we introduce an Intermediate Representation (IR) with a fixed prompt schedule. Unlike standard autoregressive generation which conditions solely on the theorem statement, our approach conditions the model on a structural tuple that explicitly separates proof planning from tactic execution. 3.1 Structured Intermediate Representation Formally, let \mathcal{T} be the space of theorem statements in Lean, and \mathcal{P} be the space of valid tactic sequences. We define a Structured Query q as a tuple: q=(x,s) (1) where: • x\in\mathcal{T} is the formal theorem statement (the goal). • s\in\mathcal{S} is a tactic skeleton (a prefix of tactics representing the high-level proof strategy, e.g., simp , intro , constructor ). The generation process is modeled as P_{\theta}(y\mid x,s) , where the model \theta is constrained to complete the proof y given the enforced structural start s . This effectively “locks” the model into a specific proof strategy before inference begins, reducing the search space of valid next tokens. 3.2 Fixed Prompt Schedule Instead of relying on stochastic temperature sampling alone, we enforce diversity through a fixed prompt schedule. For a given theorem x , we generate a set of k=16 distinct queries Q_{x}=\{q_{1},\dots,q_{16}\} by iterating over a fixed set of 15 tactic skeletons (including the empty skeleton; full list in Appendix A ). The 16th attempt reuses the empty skeleton, yielding one duplicate in the schedule. 1 1 1 Our implementation also supports optional natural-language goal hints; for this paper we set all hints to \emptyset except attempt 16, which includes a generic hint. Ablations isolating skeleton vs. hint contributions are left for future work. This schedule ensures that the model attempts a diverse range of proof strategies regardless of the model’s internal probability distribution, which might otherwise collapse to a single, incorrect mode. Note that while the prompt schedule is fixed, the model still samples stochastically (temperature =0.6 ) to generate the proof completion. 3.3 Experimental Setup & Constraints To strictly evaluate the model’s structural efficiency without the confounding factor of massive search, we enforce strict computational constraints on all evaluations. Specifically, we limit generation to a maximum of 1024 tokens and restrict sampling to k=16 attempts per theorem. While recent benchmarks often utilize significantly larger budgets (e.g., k=1024 , extended context windows), these approaches are computationally prohibitive for many practical applications. Our experimental design explicitly targets this resource-constrained regime to evaluate whether structural guidance can recover performance lost to limited compute. As such, our baseline results reflect this strict cutoff and should be interpreted as a low-latency performance floor , rather than a ceiling of model capability. 3.4 Evaluation Protocol We evaluate on miniF2F-test (Lean 4 split; 244 theorems) using DeepSeek-Prover-V1.5-RL 2 2 2 deepseek-ai/DeepSeek-Prover-V1.5-RL from HuggingFace in completion-style prompting. For each theorem, we run up to k=16 attempts with a maximum of 1024 generated tokens per attempt under fixed decoding parameters (temperature =0.6 , top- p=0.95 ; see Appendix A for the full prompt template). Each attempt is assembled into a Lean 4 file containing import