Understanding Vibe Proving

“What I cannot create, I don’t understand”
— attributed to R. Feynman

After Vibe Coding, we appear to have entered the (very area of interest, but much cooler) era of Vibe Proving: DeepMind wins gold on the International Mathematical Olympiad, Harmonic solves a non-trivial problem in number theory, and for the primary time in history AI systems look like doing serious mathematics.

At the identical time, we’re always reminded that LLMs hallucinate: it seems we’ve a paradox at hand. If LLMs can produce each garbage text (including math proofs) and proper reasoning (including math reasoning), how will we tell which model completions are good and which of them are hallucinations?

The short LinkedIn-length answer is that we use an LLM to mathematical reasoning, then we our trust to special software which verifies it. But this short answer raises in turn latest questions:

1. How does this “special software” work?
2. Why will we trust it?
3. How will we train an LLM to make use of it for proofs?

It’s tempting to put in writing articles on big ideas like “LLMs and math”, providing intuitive, non-rigorous answers in probably the most general setting possible. For example, that is how a brand new book tries to sell you on the entire “math and computers” story:

The “truth oracle” that thinkers have searched for centuries, a tool to definitively confirm or refute any mathematical or logical assertion. (…) [The book] offers a profound answer to a longstanding mystery: Can computers reveal universal truths?

. As an alternative of miracle-sounding words and analogies, we are going to construct a, with the goal of giving answers for scenarios: we gain in precision, trading some generality. As an alternative of big-picture arguments, we attempt for inspectable scripts which work on easy “proofs”. We break down our guide into two parts, which may be enjoyed independently:

• Part 1 (this one): understanding verifiers, and constructing a solid mental model of what makes math so special (why don’t we trust LLMs writing laws in the identical way we do with proofs?). It will answer questions 1 and a couple of above;
• Part 2 (coming soon): training an open-source LLM to supply proofs, using our verifier to supply a reward signal during reinforcement learning. It will answer 3.

In fact, one could piece together the fundamentals by reading papers on the frontier. Cutting-edge reports, nevertheless, typically use a special-purpose language and are stuffed with many other technical considerations, making it difficult to disentangle the essential components and construct an initial mental model of the issue space. 

By constructing an LLM-for-proofs, we get direct exposure to the fundamental ideas in order that further explorations needs to be easier: as we cannot answer all of the questions in-line, more advanced follow-ups are addressed within the FAQs at the tip.

Now, buckle up, clone the repo and code along.

What does it mean for a proof to be correct?

“Archimedes will probably be remembered when Aeschylus is forgotten,  because languages die and mathematical ideas don’t”

— G. H. Hardy

Proof checkers are software programs that take as input mathematical reasoning generated by an LLM and confirm that it’s correct. That is deceptively easy: understanding what “correct” means and the way it is feasible to ascertain correctness are the important thing to constructing a precise mental model of how LLMs might be so successful at math.

That computers can confirm math in may indeed be surprising, but all of us have familiarity with mechanical application of mathematical rules. In highschool we learn the rule to envision that 2x is the derivative of x² + 3 – crucially, we may not know what a derivative is, or what those symbols even mean, but so long as we apply the rule, we are able to confirm the claim. In a nutshell, what we’ll find today is that this phenomenon is rather more general than what we could suspect: mathematical reasoning might be codified in symbols, and treated algorithmically. 

Everybody knows the as a paradigmatic case of correct reasoning: “All men are mortal; Socrates is a person; Socrates is mortal”. The usual for correctness is logical consequence: a press release C is a logical consequence of (necessarily follows from) premises S₁, S₂ … Sₖ if it just isn’t possible for S₁, S₂ … Sₖ to be true and C to be false. In other words, .

In easy cases, it is simple to persuade ourselves that the conclusion follows from the premises, but what about more complex ones? Are you able to “see” immediately that infinite prime numbers are a logical consequence of basic multiplication and division? 

are a sequence of statements, starting with a number of premises, and ending with a conclusion, such that every statement necessarily follows from the premises and / or previous statements: the aim of a proof is to us exactly C follows from the premises, by proceeding step-by-step. For instance, we are able to indeed show that there are infinitely many primes:

• Suppose, for the sake of contradiction, that there are only finitely many primes. List all of them: p₁, p₂, …, pₖ.
• Consider a brand new number N = (p₁ × p₂ × … × pₖ) + 1. So N is either prime or composite;
• If N is prime, then we’ve found a main that just isn’t in the unique list, contradicting the belief that p₁, …, pₖ were all of the primes.
• If N is composite, it should have a main divisor q. But q can’t be amongst p₁, …, pₖ, because dividing N by any p leaves remainder 1. So again we’ve found a main not in the unique list, q.
• In each cases we contradict the belief that there have been only finitely many primes. Due to this fact, there have to be infinitely many primes.

So long as you might be comfortable with basic arithmetic and have a casual grasp on “negation” and “contradiction”, you’ll be able to follow this chain of deductions. The crucial insight is that coming up with a proof in the primary place may require a whole lot of (for lack of a greater word) , but checking one is a purely mechanical procedure: you don’t need to take my word for it, you’ll be able to check for yourself that my proof is correct. Indeed, a proof you can’t check is a proof: as Alonzo Church put it, if an auditor cannot check with “certain means” a sequence of formulas recommend as a proof, he may demand , and “until the supplementary proof is provided, he may refuse to be convinced” (and so forth, potentially perpetually).

To sum things up: a proof is a step-by-step checkable strategy to show that a conclusion follows from a set of premises. Since proofs are checkable by design, we are able to construct software that performs the mechanical checks at scale, and use it to differentiate garbage from correct proofs generated by LLMs.

Because the history of software shows, algorithms work well on formally defined languages, resembling Python or Rust. On our strategy to construct our own tiny verifier, we then need to select a strategy to represent proofs in order that a pc can easily check them.

A programming language for reasoning

“The virtue of formal texts is that their manipulations, with a view to be legitimate, must satisfy only a number of easy rules; they’re, once you come to consider it, an amazingly effective tool for ruling out all kinds of nonsense that, once we use our native tongues, are almost not possible to avoid.”
— E.W. Dijkstra

Vibe Coding may give us the illusion that we now “program in English”, but in the long run computers all the time execute instructions in a programming language. If we would like a pc to envision proofs, we’d like to precise them in a precise language: unambiguous to parse, easy to govern.

After dreaming about it for hundreds of years, mathematicians have discovered how one can use mathematics to model reasoning itself, a special , if you happen to will, to perform proofs in a rigorous way. Let’s take this trivial proof, which purports to indicate that 12 is even and divisible by 3 ranging from two self-evident premises:

1. S₁: 12 is bigger than 10 and 12 is even
2. S₂: 12 is divisible by 3
3. By line 1, we are able to see that 12 is even
4. By line 2, we are able to see that 12 is divisible by 3
5. C, by line 3 and 4: due to this fact, 12 is even and 12 is divisible by 3

We will use variables and boolean operations to represent sentences in symbols, analogously to abstracting strings into constants in Python: Q = “12 is bigger than 10”; R = “12 is even”; Z = “12 is divisible by 3”

1. Q AND R
2. Z
3. R (1)
4. Z (2)
5. R AND Z (3,4)

With dependencies between lines expressed in brackets, it is simple to see what mechanical rules might be used here: one rule (“AND elimination”) states that from (where are placeholders) we are able to eliminate AND and get one among the 2; one other rule (“AND introduction”) says to introduce provided that appear in some previous step. Unlike the English proof, this translation allows for mechanical manipulation: if you happen to wish for a coding analogy, an accurate proof is sort of a script that “compiles accurately”, as mechanically established by an algorithm (the compiler / verifier). 

In calculus, once we introduce trigonometric functions, we’d like latest derivative rules. In a similar way, when introduce more boolean operators (NOT, OR), we’d like latest rules. The reader can check the small print online (or directly within the repo), but the overall gist stays: a rule will re-arrange a number of lines right into a latest line, either eliminating existing operators or introducing them.

To sum things up: we are able to transform an English proof to symbols that might be easily manipulated, not unlike treating a parabola as an equation in order that we are able to get the derivative by some “re-arranging” of the terms. Checking the symbolic proof tells us whether the reasoning is correct and the mathematical conclusion might be trusted.

Nonetheless, there are infinitely many things we will want to prove: how will we know that in a very complex proof the principles won’t break down and pass a garbage proof for an accurate result? In other words, didn’t we just shift the burden from LLMs that hallucinate to rules that (plausibly fallible) mathematicians invented?

That is where the actual magic happens: since reasoning itself is now precisely stated, we go meta and prove things about our themselves!

A sound(ness) check

“I don’t consider in empirical science. I only consider in a priori truth.”
— attributed to K. Gödel

Even when an algorithm checks that the principles within the proof were applied accurately, we still don’t that the proof is verified; in spite of everything, programs have bugs on a regular basis! In other words, how will we know the manipulation rules themselves are correct? 

The insightful reader could have noticed our sleight of hand already. As humans, we care in regards to the : we would like to attract true conclusions from what we all know already. Nonetheless, machines care in regards to the sequence of symbols on a proof line, and the way a brand new line is created by mechanically rearranging those (remember: you’ll be able to get the derivative of x² + 3 by re-arranging the symbols, without knowing what a slope is!). What’s then the connection between symbols and truth? Ideally, these two perspectives should align: through the use of rules on true premises, I should . In other words, rules are truth-preserving: irrespective of how complex the proofs, no application of a rule will produce a false statement ranging from a real one. 

Once we ascend from investigating specific proofs to discussing what proofs should do, we go from logic to meta-logic. It’s meta-logic that answers our query, which known as the “soundness” of the system, i.e. a proof that, in sequence of manipulations leading from premises to a conclusion, the conclusion is necessarily true each time the premises are. As soundness proofs are tedious, we show how the proof works for under one rule, and take the possibility to introduce how the concept of is modeled in our language.

The above proof added as a brand new step ranging from appearing individually. Thus far, so good. To model , we define an , which is an task of truth values (1 = True,  0 = False) to our variables, with the usual recursive definition for complex sentences:

• ( AND ) = 1  () = 1 and () 1
• (NOT ) = 1  () = 0
• …

This definition would feel like a déjà vu for any coder that has ever done something like if boolean_var and boolean_other_var, and that’s because AND, OR, NOT in Python are modeled after the usual semantics of logical connectives (one among the numerous links between programming and logic!).

An interpretation function defines a possible state of the world by mapping variables to booleans: for instance, one world has true and false, one other world has each false, and so forth (within the coding case, the is finished within the script when initializing boolean_var and boolean_other_var). To finish the soundness check, . We use a truth table to search out out that, each time and are true, AND is true as well:

As we wanted, the rule indeed complies with our definition of logical consequence: (row 1). Is the converse true? As in, if a conclusion follows from some premises, is there all the time a proof of that? Only in some “programming languages” (like ours), the reply is yes: that is referred to as , and it’s the twin of soundness (also it’s more interesting, but much harder to prove!).

If we’re able (and we’re!) to ensure that each rule we use is truth-preserving, we gain the that irrespective of how complex a proof, irrespective of how far in the longer term, irrespective of if LLMs or humans are reasoning, the proof checking software won’t ever pass a garbage proof for proper reasoning.

Barring implementation bugs (that are after all unavoidable) and a faithful English-to-symbols translation, then, a verified proof is the final word standard for certainty: a precise, unambiguous type of reasoning which is mathematically sound and algorithmically checked. This just isn’t only necessary as a tenet when trusting LLMs with mathematical discovery, but in addition underscores how different mathematics is from anything: while we may get up someday and discover Newton was flawed (we did!), we are going to never get up someday and discover primes usually are not infinite. Once a proof is verified, it’s everlasting knowledge we are able to construct upon safely to realize latest knowledge:

See you, math cowboys!

“Talk is reasonable. Show me the code.”
— L. Torvalds

In this primary piece, we built a mental model to know why we must always even mathematical reasoning to be something that might be reliably verified by a pc. In answering our initial questions, we learned the distinctive, mechanical nature of proofs, and introduced the minimum ingredients we’d like to represent proofs as a program: a language and manipulation rules (mainly, a DSL!)

Within the companion repository, displays a sample of valid and invalid proofs that leverages a small Python class that implements our verification logic. The proof checker first verifies that a given series of steps is syntactically correct: like every programming language, we’d like symbols to be properly formatted! Then, it proceeds step-by-step, simulating a mathematician checking that indeed every latest line within the proof follows from previous ones. Our code achieves this in a rather unorthodox way in comparison with industry-strength provers, sacrificing performance (homework: are you able to guess why it’s computationally inefficient? How long will a table grow because the variety of variables increase?) for pedagogical purposes. When verifying step 4 on this sample proof:

1. S₁: …
2. S₂: ..
3. S₃: A AND B
4. A (3)
5. …

the checker will retrieve the justification (the premise on line 3), then construct a truth table with the required variables (A, B), with line 3 because the premise and the goal step (line 4) being the conclusion:

The savvy reader may already see where that is going: the proof step is taken into account correct if, , – the definition of logical consequence we began from!

In the subsequent piece, we are going to train an LLM to , and use the scaffolding built today to confirm those proofs. We’ll leverage closed-source LLMs and the checker to assist us create a dataset of verified proofs, then use Tinker to establish a reinforcement learning loop. We prompt a small open-source model to prove a conclusion from some premises, than pass the generated proof to the checker and reward the model whether it is correct.

While it’s unclear how much RL is “just” stressing existing capabilities or learning novel things, either way we hope that even a small model can prove easy facts in our “programming language”: see you, math cowboys!

FAQ

If you must go deeper, listed here are a number of common follow-ups:

1. Rules are truth-preserving, but how do I do know the are true in the primary place? Logically speaking, a consequence can follow from flawed premises, but a proof that starts from 2+2=5 will hardly be interesting. In most real-world cases, our premises are the outcomes of other theorems, so we all know them to be consequences of other, more fundamental facts; the bad news is that the buck should stop and no more premises might be invoked. It seems that the overwhelming majority of math might be backed by a number of statements, the axioms of set theory: since axioms are the premises you can’t prove, it’s interesting to ask ourselves what believing those in the primary place. Math axioms are nevertheless less debatable than, say, morality, which is why it’s way easier to consider in formalizing math (where everybody agrees on the premises, so we “just” check the reasoning), than doing the identical for legal arguments (where often the 2 parties start from different premises). The excellent news, though, is that a proof resembles a pc program in a couple of way: once we all know a theorem, we are able to now “import” it right into a larger proof in the same strategy to how we import pandas in our code.
2. If proof checking is fully algorithmic, can we also write an algorithm to prove all truths? In full generality, we cannot. The existence of truths we cannot prove is probably going probably the most profound mathematical facts of the last century: that is the essential take-away of Gödel’s Incompleteness Theorem. Furthermore, we don’t know if some statements are true or false as our greatest axiom system sometimes cannot determine (the Axiom of Selection being a famous example of something independent from set theory).
3. Can we interesting things in regards to the notion of proof itself? Yes! While the Church’s point is certainly a sound argument, on his strategy to proving his celebrated theorem, Gödel proved that the predicate is algorithmic. Plus, there’s a complete logic for provability!
4. Where can I read more? My favorite intro-to-intermediate text is Language, Proof and Logic, which is particularly geared towards non-math students; Computability and Logic is an intermediate text with a deal with the connection between logic, proof and computation.

Acknowledgements

Because of Patrick John Chia, Federico Bianchi, Ethan Rosenthal, Ryan Vilim, Davis Treybig for precious feedback over previous versions of this draft. If you happen to just like the intersection of genAI, reasoning about distributed systems and verification, you may as well take a look at our research at Bauplan.

AI coding assistants were used to put in writing the companion repository, but no assistant was used to put in writing the text (if not for proof-reading and typo correction).