📊 statistics

Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Provers

This paper demonstrates that hierarchical theorem provers achieve an exponential reduction in sample complexity compared to flat provers by learning reusable proof structures from teacher traces, thereby avoiding the redundant repetition of hard subproofs inherent in flattened representations.

Original authors: Sho Sonoda, Shunta Akiyama, Yuya Uezato

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sho Sonoda, Shunta Akiyama, Yuya Uezato

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a student how to solve a very complex puzzle, like a massive jigsaw or a difficult math problem. The goal is to get the student to find the solution as quickly and efficiently as possible, using a limited amount of time and effort.

This paper asks a simple question: Is it better to teach the student to solve the whole puzzle from scratch every single time, or to teach them to recognize and reuse smaller, solved pieces of the puzzle?

The authors argue that teaching the student to reuse pieces (a hierarchical approach) is exponentially more efficient than forcing them to re-solve every tiny step from scratch (a flat approach), even if the "pieces" themselves are hard to figure out.

Here is the breakdown using everyday analogies:

1. The Two Ways of Learning

The "Flat" Student (The Hard Worker)
Imagine a student who is given a recipe for a huge banquet. Every time the recipe says "make the sauce," the student has to start from zero: chop the onions, peel the garlic, simmer the tomatoes, and blend it all. Even if the recipe asks for the sauce ten times, this student makes ten separate batches of sauce, chopping the onions ten times.

In the paper: This is a "flat" prover. It sees the entire proof as one long, straight line of steps. If a specific logical argument (like a lemma) is needed five times, the student has to learn and execute those five steps five separate times.

The "Hierarchical" Student (The Smart Organizer)
Now imagine a smarter student. When they see "make the sauce," they realize, "I've done this before!" They write down a note: "Sauce Recipe: Chop, peel, simmer." Next time the recipe calls for sauce, they just say, "Use the Sauce Recipe," and they don't have to chop the onions again. They build a library of reusable "blocks" (lemmas).

In the paper: This is a "hierarchical" prover. It breaks the problem into a map (a DAG, or Directed Acyclic Graph) where shared parts are solved once and then referenced many times.

2. The Core Discovery: The "Exponential" Gap

The paper's main finding is about sample complexity. In simple terms, this means: "How many examples does the student need to study to become good at the task?"

The authors prove that if a problem requires reusing a difficult sub-step many times, the "Flat" student needs to see that difficult step repeated exponentially more times in their training data than the "Hierarchical" student.

The Analogy of the Library:

Flat Student: To learn how to write a book that quotes a famous poem 1,000 times, this student must read the entire book 1,000 times, memorizing the poem's 10 lines every single time. They need a massive library of books to learn this.
Hierarchical Student: This student reads the book once. They memorize the poem's 10 lines once and put them in a "Citation Box." When they need to quote it again, they just point to the box. They need a tiny library to learn the same thing.

The paper shows that if the "poem" (the hard sub-proof) is difficult, the Flat student might need millions of examples to learn it, while the Hierarchical student might only need dozens. The difference isn't just a little bit; it's an exponential gap.

3. Why Does This Happen?

The authors model this using a concept called an MDP (Markov Decision Process), which is just a fancy way of describing a game with rules, states, and moves.

The Teacher: A perfect solver that shows the student successful proofs.
The Data: The student learns by watching these successful proofs.
The Problem: If the teacher's proof uses a clever shortcut (a lemma) five times, the "Flat" view of the data looks like five separate, long, hard paths. The student has to learn five separate paths.
The Solution: The "Hierarchical" view sees that those five paths are actually just one path repeated. The student only needs to learn the one path.

The paper provides mathematical formulas (bounds) to prove that the number of training examples needed for the Hierarchical student stays small, while the number needed for the Flat student explodes as the problem gets deeper.

4. What This Means for AI Theorem Provers

The paper focuses on Agentic Theorem Provers—AI systems that try to prove mathematical theorems. These systems often try to break big problems into smaller "subgoals" or "lemmas."

The Skeptic's View: "Why bother breaking it down? Proving the small lemma is hard. Why waste time on it?"
The Paper's Answer: "Because if you don't break it down and reuse the solution, you will have to solve that same hard problem over and over again. The 'waste' of solving the lemma once is actually a massive saving compared to solving it a thousand times."

Summary

Think of it like building a house:

Flat Approach: You build the house by laying every single brick individually, even if you need to build the same wall pattern 100 times. You need a mountain of bricks and a lot of time.
Hierarchical Approach: You build a "wall module" once. Then, you just stack that pre-made module 100 times. You need far fewer raw materials and less time.

The paper proves mathematically that for complex problems, the "module" approach (hierarchical) requires exponentially fewer training examples to learn than the "brick-by-brick" approach (flat). This explains why modern AI theorem provers that use "lemmas" and "subgoals" are statistically more efficient than those that try to solve everything in one long, flat line.

Title: Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Provers

Authors: Sho Sonoda, Shunta Akiyama, Yuya Uezato
Affiliations: CyberAgent, RIKEN AIP
Date: May 7, 2026

1. Problem Statement

Recent agentic theorem provers often employ decomposition strategies—such as generating intermediate lemmas, proof sketches, or subgoal decompositions—before engaging in tactic-level search. While classical proof theory suggests that lemmas can shorten derivations, the statistical learning cost of discovering and proving these intermediate steps remains an open question. Specifically, if proving a lemma is itself difficult, why should a learned prover expend effort on it?

The paper addresses the statistical learning problem of whether learning a reusable proof structure (hierarchical) increases the probability of finding a verified proof within a fixed search budget compared to learning from fully inlined proof traces (flat). The authors focus on the data distribution induced by a "teacher" prover, consisting of initial theorem states and successful verified proof traces, rather than worst-case proof complexity over all formulas.

2. Methodology

The authors model theorem proving as a deterministic finite-horizon Markov Decision Process (MDP) where states are proof states and actions are tactics, inference rules, or high-level decomposition moves. They analyze offline imitation learning from successful teacher traces under three distinct settings:

Setting 1 (Flat): The teacher generates fully inlined low-level proof traces. The student imitates these traces without graph prediction or memoization. Repeated subproofs appear as distinct, copied occurrences in the training and test data.
Setting 2 (Hierarchical): The teacher constructs a high-level proof Directed Acyclic Graph (DAG) where nodes represent reusable proof blocks. The student learns a graph predictor and policies for high-level graph actions (selecting, expanding, reusing blocks) and low-level local solving. The training data consists of inlined traces, requiring the student to infer the latent proof DAG structure.
Setting 3 (Comparison): Both a flat student and a hierarchical student are trained on the same source data generated by the hierarchical teacher (inlined traces). The flat student discards the latent graph structure, while the hierarchical student infers it. This setting isolates the effect of representation on sample complexity.

The analysis relies on three key quantities:

$L$ (Average Length): The average number of decisions in a successful proof.
$\eta$ (Intrinsic Search Loss): The probability mass lost because the teacher's next action is not in the student's top- $k$ candidate list (local predictability).
$e$ (Imitation Error): The Kullback-Leibler (KL) divergence between the student's policy and the teacher's policy.

The authors assume a Tsybakov-type margin condition to convert imitation error into top-k omission probability and assume search completeness if the teacher's actions are contained within the student's top- $k$ list.

3. Key Contributions

Formalization: The paper formulates verifier-guided theorem proving as a finite-horizon MDP and defines "statistical provability" as the average probability of finding a verified proof within a budget over a distribution of initial states.
Success Guarantees: The authors derive finite-sample success bounds for both flat students (trained on inlined traces) and hierarchical students (trained to predict reusable DAGs). The bounds explicitly separate the number of decisions, intrinsic top-k loss, and learned ranking error.
Exponential Separation: The primary theoretical result is an exponential separation in sufficient sample complexity. When a reusable proof DAG is flattened into a tree, identical subproofs are duplicated exponentially many times. The paper proves that the sufficient-sample certificate for the hierarchical learner can be exponentially smaller than that of the flat learner, even when trained on the same data source.
Latent Graph Learning: The paper provides learning rates for a hierarchical student that must infer latent proof DAGs from inlined traces using an EM-style posterior-weighted approach, accounting for graph prediction errors and posterior mismatch.

4. Results

The core result is presented in Theorem 6, which compares the certified sufficient sample counts ( $\bar{N}$ ) required for the flat and hierarchical students to achieve a target failure level $\delta$ .

Flat Bound: $\bar{N}_{flat}(\delta) \propto (L_{flat}/\delta)^{1/(p\gamma)}$
Hierarchical Bound: $\bar{N}_{hier}(\delta) \propto \max(L_{hi}, L_{lo}/\delta)^{1/(p\gamma)}$

Where $L_{flat}$ is the length of the unfolded trace and $L_{hier} = L_{hi} + L_{lo}$ is the length of the hierarchical representation.

The paper demonstrates that for a family of theorems indexed by a size/depth parameter $D$ , if the flattening process causes the proof length to grow exponentially ( $L_{flat}/L_{hier} = \exp(\Omega(D))$ ), then the ratio of required samples also grows exponentially:
$\bar{N}_{flat}(\delta) / \bar{N}_{hier}(\delta) \geq \exp(\Omega(D))$

This separation arises because the flat learner must learn the same hard local argument independently for every occurrence, whereas the hierarchical learner learns the shared block once and reuses it. The paper uses a cut-elimination example (Appendix G) to illustrate how removing intermediate lemmas (flattening) can cause proof size to explode exponentially, thereby inflating the sample complexity for flat learners.

5. Significance and Claims

The paper claims to provide a concrete statistical mechanism explaining why hierarchical proving helps, distinct from worst-case proof complexity arguments. The significance lies in identifying that the benefit of decomposition is not merely about shortening the logical derivation, but about reducing the statistical burden on the learner.

Data Distribution Awareness: The result highlights that the efficiency of learning depends on the structure of the data distribution. If successful proofs reuse intermediate arguments, a hierarchical representation captures this sharing, while a flat representation destroys it, leading to redundant learning tasks.
Limitations: The authors are modest about their claims. They state that this is not a worst-case lower bound and does not rule out flat learners that might achieve perfect canonicalization (perfectly recognizing identical subproblems without explicit hierarchy). The separation holds specifically when flattening destroys reusable proof structure and the data distribution contains proofs where such sharing is prevalent.
Practical Implication: The findings suggest that for verifier-based theorem proving, learning to predict reusable proof structures (lemmas, subgoals) can exponentially reduce the sample complexity required to achieve a given success probability, provided the graph predictor can cover the teacher's certificate with high probability.

The paper concludes that the "expensive detour" of proving lemmas is statistically justified when those lemmas are reusable, as the cost of learning them once is far lower than the cost of rediscovering them repeatedly in a flat framework.