🤖 AI

PriorProof: A Point-in-Time Measure of Technique Novelty for Formal Proofs

The paper introduces PriorProof, an automated, ontology-free method for quantifying the novelty of formal proof techniques in Lean by measuring the surprisal of their dependency footprints against a time-anchored prior, demonstrating moderate agreement with human experts and serving as a decomposable, interpretable signal rather than a replacement for expert judgment.

Original authors: Neel Somani

Published 2026-07-21

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Neel Somani

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 walking through a massive, ever-expanding library of mathematical ideas. In this library, every new book (a proof) must cite the older books it used to build its arguments. Usually, when a mathematician writes a new proof, they try to use the most common, well-worn tools available at that moment. But sometimes, they take a wild, unexpected path, using a strange combination of old tools that no one thought to mix together before. The big question is: how do we know, just by looking at the list of books they used, if their path was truly surprising or just a routine detour? This is the puzzle of "novelty" in formal mathematics. While humans can argue about whether a proof is "elegant" or "original," computers struggle with these fuzzy feelings. They need a hard, mechanical way to measure if a proof took a route that was unlikely to happen given what was known at the time. This is where the idea of "surprisal" comes in—think of it as a measure of how much a proof makes the library say, "Wait, I didn't expect you to use that specific tool for this job!"

Enter PriorProof, a new tool designed to act like a time-traveling librarian. Instead of asking a human, "Was this proof clever?", PriorProof asks a cold, hard question: "If we froze the library at the exact moment this proof was written, how surprising would the list of tools used be?" The researchers built a system that looks at a formal proof (written in a language called Lean), strips away the fancy formatting, and creates a "footprint" of the specific mathematical machinery used. Then, it goes back in time to a snapshot of the library from before that proof existed. It asks, "Based on other proofs with similar goals from that earlier time, how likely was it that someone would use these specific tools?" If the answer is "very unlikely," the proof gets a high "novelty score." The study found that this mechanical score often agrees with human experts about which proofs took the more unusual route, especially when the difference in scores is large. However, the authors are careful to say this isn't a magic wand that solves everything; it's a helpful signal that works best when the gap between two proofs is obvious, and it doesn't measure the "beauty" or "importance" of the math, just how unexpected the path was.

The Time-Traveling Librarian

Imagine you are a detective trying to figure out if a thief used a secret, never-before-seen method to crack a safe. You can't ask the thief what they were thinking, but you can look at the tools they left behind. PriorProof is that detective, but for mathematical proofs. It doesn't care about the thief's motive or how cool the heist looked; it only cares about the tools (the mathematical constants and lemmas) used to solve the problem and whether those tools were a weird choice for the time period.

Here is how the magic trick works, step-by-step:

The Footprint: When a mathematician writes a proof in Lean (a computer language for math), the computer turns it into a long, detailed list of every single tool it used. PriorProof takes this list and cleans it up, grouping similar tools into "families" (like grouping all hammers together, or all screwdrivers). This is the "footprint."
The Time Machine: The system then travels back in time. It grabs a snapshot of the entire math library from before the proof was written. It looks at all the other proofs written around that time that were trying to solve similar problems.
The Prediction: Using a smart computer model (a language model), it predicts: "If I were writing a proof for this problem back then, what tools would I probably use?" It builds a "prior" expectation, like a weather forecast for mathematical tools.
The Surprise Score: Finally, it compares the actual tools used in the new proof against the forecast. If the proof used tools that the forecast said were very unlikely (low probability), the system gives it a high "surprisal" score. A high score means, "Wow, that was a weird route to take!"

What the Detective Found

The researchers tested this system on a specific section of the math library called Topology (which deals with shapes and spaces). They didn't just guess; they set up a blind test. They took 100 pairs of proofs and showed them to three human math experts. The experts had to pick which proof in each pair took the "less standard" (more surprising) route. They didn't see the scores; they just used their brains.

Then, they compared the human experts' choices with what PriorProof predicted. Here is the result:

Out of 76 unique pairs of proofs (some were shown multiple times to check for consistency), PriorProof agreed with the majority of the human experts on 53 of them. That's about 69.7%.
For the 12 pairs that were specifically chosen because they were obvious "textbook examples" of surprising vs. standard proofs, PriorProof got it right 11 times (about 91.7%).
For the other 64 pairs, which were a bit trickier, it got 42 right (about 65.6%).

The authors also looked at the "score gap"—the difference between the surprise score of the two proofs in a pair. They found a neat pattern: when the gap was huge (meaning one proof was much more surprising than the other), the system was very reliable, agreeing with humans 84.2% of the time. But when the gap was small (the two proofs were similarly surprising), the system was less sure, agreeing only 63.2% of the time. This suggests the tool is great for spotting the "big surprises" but gets fuzzy when the differences are subtle.

What It Is NOT (and What It Rules Out)

It is crucial to understand what PriorProof is not claiming to be. The authors are very clear about this:

It is not a measure of "Originality" or "Genius": A high score doesn't mean the mathematician was a genius. It just means they used a weird combination of tools. Sometimes, a weird route is just a clumsy detour, not a brilliant insight.
It is not a measure of "Importance": A proof can be incredibly important to the world of math but use very standard, boring tools. PriorProof would give it a low score, even if it changed history.
It is not a "Plagiarism Detector": The system doesn't care if someone copied a proof. It only cares about the statistical likelihood of the tools used.
It is not a "Perfect" Judge: The authors explicitly state that their method is not a "solved problem." In fact, when they compared PriorProof to a powerful AI language model (GPT-5-mini), the AI actually agreed with the human experts slightly more often (about 78.9% vs. 69.7%). However, the difference wasn't statistically significant enough to say one was definitely better than the other. The real value of PriorProof isn't that it beats the AI, but that it is transparent. You can look at the score and see exactly which tool caused the surprise, whereas the AI is a "black box" that just gives an answer.

The Bottom Line

PriorProof is a new, mechanical way to measure how "nonstandard" a mathematical proof is by looking at how surprising its tool choices were at the time it was written. It works well enough to agree with human experts about two-thirds of the time, and it gets even better when the difference between two proofs is obvious. It doesn't tell us if a proof is beautiful, important, or brilliant, but it does give us a reliable, time-stamped signal that says, "Hey, this path was unexpected." It's a tool for researchers to find interesting cases to study, not a final judge of mathematical greatness. The authors suggest that in the future, we might use this to help spot interesting machine-generated proofs or to study how mathematical libraries evolve, but for now, it's just a very clever, very specific way to measure surprise.

Technical Summary: PriorProof

Problem Statement

Formal proof libraries, such as Lean's Mathlib, offer a unique record of mathematical development: the elaborated proof term explicitly lists the constants used, and version control identifies exactly which declarations existed at the time of writing. This allows for a mechanical investigation into time-relative proof-route nonstandardness: determining how "surprising" or nonstandard a proof's route was relative to the techniques available when it was written.

While existing evaluations of learned theorem provers focus on whether a theorem is proved, the search cost, or transferability, they do not directly measure whether a successful proof follows a route that the earlier library would have made likely. Philosophers and mathematicians have long analyzed proof virtues like explanation, purity, and elegance, but these are difficult to operationalize mechanically. PriorProof addresses a narrower construct: route novelty defined as the deviation of a proof's dependency footprint from the expected distribution of dependencies for similar statements in the library's prior state.

Methodology

PriorProof is a quarterly, point-in-time measure for Lean 4/Mathlib proofs. The pipeline operates on a theorem declaration $D$ written at time $t$ through three primary stages:

1. Dependency Footprint Extraction

The system extracts a weighted "dependency family footprint" from the elaborated proof term $p_D$ :

Extraction: It uses Lean's getUsedConstants to identify constants actually referenced by the proof term, excluding mere file imports.
Filtering: A deterministic filter removes generated recursors, coercions, routine typeclass plumbing, and tactic boilerplate.
Frontier Traversal: Dependencies are recursively replaced by older dependencies they rest upon until the traversal reaches declarations established in the library snapshot prior to $t$ . Establishment is defined by a pre-bin reuse-count threshold to prevent co-introduced declarations from appearing established.
Family Backoff: Each surviving constant maps to the finest "dependency family" (namespace, module, or library area) with at least five pre-bin occurrences. This reduces accidental novelty from rare names without requiring a hand-built ontology.
Result: A weighted set $\Phi_t(D) = \{(f_i, w_i)\}$ representing the observed dependency families.

2. Statement-Conditioned Prior Construction

To determine what was "expected," the system retrieves similar theorem statements from a library snapshot strictly earlier than the target's quarter ( $L_{<b(t)}$ ):

Retrieval: A sentence-transformer encoder (fine-tuned on pre-bin contrastive pairs) retrieves the $k=32$ nearest neighbor statements based on cosine similarity.
Smoothing: A hierarchically smoothed prior $q_t(f|D)$ $q_{t} (f ∣ D)$ is constructed as a mixture of empirical family distributions from:
- Retrieved neighbors ( $q_{r,t}$ )
- Target namespace ( $q_{n,t}$ )
- Target module ( $q_{m,t}$ )
- The full pre-bin library ( $q_{g,t}$ )
Optimization: Mixture weights and smoothing parameters are selected by maximizing the chronological log-likelihood of observed families in earlier proofs, ensuring the prior is predictive rather than tuned to the human study.

3. Scoring

The PriorProof score $S_t(D)$ is the weighted surprisal of the observed footprint under the constructed prior:
$S_t(D) = \sum_{i=1}^{m_D} w_i [-\log q_t(f_i | D)]$
A high score indicates the proof uses dependency families that were improbable for earlier theorems with similar statements. For pairwise comparisons, the metric selects the proof with the higher score, using the absolute score gap $\Delta(A, B)$ as an internal confidence signal.

Key Contributions

Mechanical Definition: A definition of time-relative proof-route nonstandardness as dependency-footprint surprisal, requiring no hand-built technique ontology or human labels.
Temporal Discipline: A rigorous leakage discipline where retrieval, family support, reuse counts, and encoder fine-tuning are strictly restricted to pre-bin data.
Empirical Study: A blinded study on Mathlib topology involving mechanical validation, a three-rater comparison, and a language-model baseline.
Endpoint-Calibration Evidence: Empirical evidence that the absolute score gap serves as a candidate reliability indicator, where larger gaps correlate with higher agreement with human raters, though the relationship is not a resolved monotonic staircase.

Results

The study evaluated 100 blinded presentations (collapsing to 76 distinct underlying proof pairs) against three retained domain raters and language model baselines (gpt-5/gpt-5-mini).

Agreement with Raters: PriorProof agreed with the three-rater majority on 53/76 pairs (69.7%).
- Canonical Pairs: 11/12 (91.7%) on 12 hand-selected canonical contrasts.
- Stratified Pairs: 42/64 (65.6%) on the broader set.
Language Model Baseline: The best language-model condition agreed on 60/76 pairs (78.9%). A McNemar test comparing PriorProof and the model yielded $p=0.210$ , indicating the difference is not statistically established at this sample size.
Score Gap Calibration:
- In the smallest score-gap bin, agreement was 12/19 (63.2%), statistically compatible with chance.
- In the largest score-gap bin, agreement was 16/19 (84.2%).
- The interior bins were nonmonotone, and confidence intervals were wide. The paper concludes this supports an endpoint-calibration tendency (high gaps are more reliable) rather than a resolved, universal calibration curve.
Mechanical Validation: Observed footprints received significantly higher chronological probability than random alternatives. Ablation studies confirmed that retrieval and smoothing components contribute meaningfully to the score, while redundancy checks found no "live" hits in the curated corpus (though the nested path was dormant due to backend limitations).

Significance and Claims

The paper presents PriorProof not as a replacement for expert or model judgment, nor as a complete theory of mathematical novelty. Instead, it is positioned as a decomposable, time-anchored signal.

Scope: The metric specifically targets whether a proof route uses unexpectedly distributed prior machinery. It is blind to definitional novelty, explanatory value, elegance, or authorship credit.
Reliability Indicator: The primary utility identified is the score gap. The results suggest that when the score gap between two proofs is large, the metric's preference is more likely to align with human judgment. When the gap is small, the metric is less reliable.
Limitations: The authors explicitly note that the metric can be gamed by adding irrelevant rare machinery, and that the current implementation lacks subterm-aware normalization (nested redundancy detection is inactive). The statistical scope is limited to one mathematical domain (topology) and a specific sample size.
Future Utility: The metric is intended as a research instrument for analyzing checked formal proofs, prioritizing cases for expert review, and studying machine-generated proofs to see if they reproduce expected patterns or discover routes meriting human attention. It is a hypothesis generator, not an arbiter of originality.