LLM2SMT: Building an SMT Solver with Zero Human-Written Code
Mikoláš Janota, Mirek Olšák · 2026
Read LLM2SMT: Building an SMT Solver with Zero Human-Written Code by Mikoláš Janota, Mirek Olšák (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-2603-06931.txt.
Introduction
Janota and Olšák present a case study where an LLM coding agent builds a complete SMT solver with zero human-written code. People debate whether LLMs can reason or code, but whether they can build software that itself reasons is largely unexplored. Their solver follows the DPLL(T) style for QF_UF, implements Nieuwenhuis-Oliveras congruence closure, includes preprocessing, and emits Lean proofs when instances are unsatisfiable. They describe the build process and key challenges, and show the solver competes on SMT-LIB benchmarks.
Catalog record
| CREATOR | Mikoláš Janota, Mirek Olšák |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21280 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.06931
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
LLM2SMT: Building an SMT Solver with Zero Human-Written Code Mikoláš Janota, Mirek Olšák Abstract Whether LLMs can reason or write software is widely debated, but whether they can write software that itself reasons is largely unexplored. We present a case study in which an LLM coding agent builds a complete DPLL(T)-style SMT solver for QF_UF with zero human-written code. The solver implements the Nieuwenhuis-Oliveras congruence closure algorithm, includes preprocessing, and emits Lean proofs for unsatisfiable instances. We describe the development process and key challenges, and show that the resulting solver is competitive on SMT-LIB benchmarks. While full proof emission for unsatisfiable instances appears to be beyond the capabilities of the LLM, the solver achieves competitive performance and passes correctness tests. Czech Technical University, Czechia and https://people.ciirc.cvut.cz/~janotmik/ [email protected]://orcid.org/0000-0003-3487-784XThe research was supported by the MEYS within the dedicated program ERC CZ under the project POSTMAN no. LL1902, and by the European Union under the project ROBOPROX (reg. no. CZ.02.01.01/00/22_008/0004590). This article is part of the RICAIP project that has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 857306. Czech Technical University, Czechia and https://www.olsak.net/ [email protected]://orcid.org/0000-0002-9361-1921The author acknowledges the support of National Recovery Plan funded project MPO 60273/24/21300/21000 CEDMO 2.0 NPO. ccs Theory of computation Automated reasoning keywords LLM, SMT, automated reasoning, proofs † † runningauthor: M. Janota and M. Olšák † † copyright: Mikoláš Janota and Mirek Olšák † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction LLM-powered coding agents are now so widely used that some believe software engineers in their traditional role will disappear [ 27 ] . LLMs—directly or via coding agents—have also been used for auto-formalization and for developing novel proofs [ 18 , 3 , 31 , 16 ] . The question we ask is: Can LLMs develop automated reasoning tools? The appeal is clear: rapid feature integration, experimentation with new techniques, and importing methods from recent publications. Skepticism is warranted, however—small mistakes can propagate into subtle, hard-to-detect errors. Correctness is paramount: do LLMs understand the underlying logic well enough to write reliable SMT solvers? We develop a basic DPLL(T)-style [ 25 ] SMT solver with zero code written by a human, focusing on the theory of uninterpreted functions without quantifiers (QF_UF)—an important theory underlying most functionality in DPLL(T). The solver uses CaDiCaL [ 8 ] via the IPASIR-UP interface [ 15 ] , emits proofs in Lean [ 21 ] (under some limitations), implements the Nieuwenhuis–Oliveras congruence closure algorithm [ 24 ] , and integrates several preprocessing techniques. The code is available as a GitHub repository 1 1 1 https://github.com/MikolasJanota/llm2smt . 2 Background We assume that the reader is familiar with classical first-order logic with equality [ 29 ] . Satisfiability Modulo Theories (SMT) solving is a well-established research area encompassing a wide range of logical theories, applications, and algorithmic techniques. Most SMT solvers reduce the input formula to propositional satisfiability (SAT), either eagerly [ 26 ] , where theory reasoning is encoded directly into a propositional (Boolean) problem, or lazily [ 10 ] , where Boolean reasoning is interleaved with theory-specific checks. These checks result in theory lemmas , which strengthen the propositional problem. Most modern solvers are based on the DPLL (T) framework [ 25 , 17 , 28 ] . In this architecture, theory atoms are abstracted as Boolean variables and handled using conventional SAT-solving techniques [ 19 ] . Candidate assignments produced by the SAT solver are subsequently validated by dedicated theory solvers , which are required only to check conjunctions of theory literals. If a conjunction is inconsistent in the underlying theory, the theory solver provides conflict information to refine the Boolean search. The process iterates until the SAT solver determines the formula to be unsatisfiable or a theory-consistent assignment is obtained. During the search, the solver might employ theory propagation , forcing certain literals to specific values under the current partial assignment. This paper focuses on the theory of equality with uninterpreted functions (QF-EUF), which is the basis of equality reasoning; in particular, it is instrumental in the Nelson-Oppen closure [ 22 , 11 ] , which enables cooperation between separate theory solvers under appropriate assumptions. In the context of SMT, quantifiers are handled by quantifier instantiation , cf. [ 14 , 20 ] . Therefore, solving problems without quantifiers (ground problems) is necessary for solving quantified problems. Lean [ 21 ] is a popular modern interactive theorem prover (ITP) and programming language for formalizing mathematics and verifying software. It is based on dependent type theory, providing a unified framework for programs, proofs, and mathematical objects. Its main library, mathlib , contains a bevy of formalized theorems spanning broad areas of mathematics. 3 Case Study The entire study was conducted within Claude Code using the Sonnet 4.6 model [ 2 ] . No code was written by a human, and the code was only minimally inspected. A human performed more extensive evaluation on a separate server. The project was started with a minimal description giving the LLM a reference for the congruence closure algorithm [ 24 ] . Start a project that implements an SMT solver. We need a parser, a SAT solver, for which we will use the ipasir-up interface hash-consing of formulas. Then theory specific things, like arbitrary precision library. Setup build by using cmake. The solver will be written in c++20. Use antlr for parsing (the grammar is here https://github.com/julianthome/smtlibv2-grammar). Set up the directory structure also testing. cmake should download the necessary dependencies as needed. We will start with QF-EUF theory solver implementing the congruence closure as described in Fast congruence closure and extensions by Robert Nieuwenhuis and Albert Oliveras (the pdf is in the folder for convenience). This quickly proved too naive. Despite correctly describing SMT solving at a high level, the LLM did not implement a correct solver from the start. Most strikingly, the solver did not handle Boolean connectives at all. This was quickly remedied by pointing the LLM to the core theory specification 2 2 2 https://smt-lib.org/theories-Core.shtml . Only after some time did we notice that xor was not implemented as n-ary, which required an explicit prompt to fix. Despite being prompted to use CaDiCaL, the agent instead wrote its own rudimentary SAT solver. We subsequently gave an explicit prompt to integrate CaDiCaL via the IPASIR-UP interface [ 15 ] , which the agent accomplished without difficulty. Notably, the agent ran the solver without a timeout, leaving long-running processes unnoticed in the background. We therefore added to the permanent instructions of the LLM to always run the solver under the timeout command. 3 3 3 Claude Code permits inserting such instructions into CLAUDE.md . 3.1 Bugs and Debugging Initial development required numerous bug fixes in the congruence closure algorithm and parsing. The agent fixed bugs autonomously, once presented with an input file where the solver gave a wrong answer. Several issues stemmed from the fact that in