Formalizing mathematics is a battle against the "rigor gap." While a human mathematician might leap across a proof with a few lines of high-level intuition, an Interactive Theorem Prover (ITP) like Lean or Coq requires every logical step to be explicitly defined and verified. For Large Language Models (LLMs), generating these long, monolithic chains of formal code is prone to "hallucinations" and cascading failures.
The emerging solution across recent research is Recursive Subgoal Decomposition. Instead of attempting to bridge the gap between a theorem and its proof in one giant leap, these systems break the problem into a hierarchy of smaller, verifiable waypoints.
The Intuition: Divide, Conquer, and Verify
The core difficulty in formal proving is the astronomical search space. If a proof requires 50 steps and each step has 10 possible tactics, the search tree becomes impossible to navigate.
As Albert Q. Jiang and colleagues demonstrate in Draft, Sketch, and Prove: Guiding Formal Theorem Provers with Informal Proofs, we can use LLMs to generate a "formal sketch"—a structured outline where high-level steps are defined as unverified conjectures. This transforms a global search problem into a series of local, short-range verification tasks. If a symbolic solver can bridge the gap between Conjecture A and Conjecture B, that segment of the proof is "closed."
Hierarchical Planning and Tactical Execution
Modern frameworks often split the labor between two distinct roles: the Planner and the Tactician.
- Strategic Planning: A high-level model (often a general-purpose LLM) generates a natural language outline or a formal draft with placeholders. Qi Liu describes this in Bootstrapping Hierarchical Autoregressive Formal Reasoner with Chain-of-Proxy-Autoformalization as decoupling strategic drafting from low-level gap-filling.
- Tactical Refinement: A specialized model or automated reasoner then attempts to prove each individual subgoal. If a subgoal is still too complex, the system applies Recursive Decomposition. As seen in DeepSeek-Prover-V2 by Zhihong Shao, if a lemma fails to verify, it is broken down into even smaller, more manageable logical units until the entire chain is reachable.
This approach mimics human mathematical practice. In Computer Assisted Reasoning with MIZAR, Andrzej Trybulec pioneered the idea of treating proofs like structured programming, using hierarchical blocks to establish the skeleton before filling in the deductive details.
Learning from Failure and Intermediate States
One of the most powerful facets of this direction is how it handles failure. In traditional search, a failed proof attempt is a dead end. In a subgoal-based framework, a failure is a diagnostic tool.
Saketh Ram Kasibatla and the team behind Cobblestone: A Divide-and-Conquer Approach for Automating Formal Verification use LLMs to extract nearly-correct intermediate steps from failed attempts. These "cobblestones" are then treated as independent lemmas, allowing the system to salvage progress and focus its search on the specific gaps that remain.
This modularity also solves the "data bottleneck." By treating every intermediate state in a successful proof as a standalone theorem—a technique used by Jing Gao in Generating Millions Of Lean Theorems With Proofs By Exploring State Transition Graphs—researchers can exponentially expand training datasets. Instead of one training example per proof, they get dozens of "subgoal completion" tasks.
Why It Works: Managing Cognitive and Computational Load
Whether the "user" is a human student or an AI agent, the benefit of subgoals is the reduction of cognitive (or computational) load.
- For AI: It prevents the "long-horizon" problem where a model loses logical coherence over hundreds of lines of code. By verifying and caching subgoals as axioms, as suggested in Seed-Prover 1.5, the model only needs to "see" the immediate logical transition it is currently solving.
- For Humans: In educational settings, Sutapa Dey Tithi found that breaking complex proofs into data-driven subgoals reduces the psychological barrier for learners, providing a roadmap through an otherwise overwhelming problem space.
By shifting from "end-to-end generation" to "hierarchical decomposition," the field is moving toward a more robust, explainable, and scalable form of automated reasoning—one that bridges the gap between the fluid intuition of natural language and the rigid requirements of formal logic.