Can Large Language Models Learn Formal Logic? A Data-Driven Training and Evaluation Framework
Yuan Xia, Akanksha Atrey, Fadoua Khmaissia, Kedar S. Namjoshi · 2025
Read Can Large Language Models Learn Formal Logic? A Data-Driven Training and Evaluation Framework by Yuan Xia, Akanksha Atrey, Fadoua Khmaissia, Kedar S. Namjoshi (2025) 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-2504-20213.txt.
Introduction
Yuan Xia and co-authors published a research paper in 2025 on whether language models can truly learn formal logic, tested by making them write checkable proofs in Boolean logic. A model gets assumptions and a goal and must produce a proof a checker accepts. Real proofs are too scarce to train on, so the team synthesizes valid proofs with a randomized generator.
A template trick rewrites training proofs into varied shapes, teaching flexibility with complex expressions. Their tests judge reasoning rather than memorization. Models proved short arguments strongly, then faded as proofs grew. The augmentation helped even small models, suggesting reasoning habits can be trained, within limits the authors map carefully.
Catalog record
| CREATOR | Yuan Xia, Akanksha Atrey, Fadoua Khmaissia, Kedar S. Namjoshi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-20213
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Can Large Language Models Learn Formal Logic? A Data-Driven Training and Evaluation Framework Yuan Xia, Akanksha Atrey, Fadoua Khmaissia, Kedar S. Namjoshi Abstract This paper investigates the logical reasoning capabilities of large language models (LLMs). For a precisely defined yet tractable formulation, we choose the conceptually simple but technically complex task of constructing proofs in Boolean logic. A trained LLM receives as input a set of assumptions and a goal, and produces as output a proof that formally derives the goal from the assumptions. Incorrect proofs are caught by an automated proof checker. A critical obstacle for training is the scarcity of real-world proofs. We propose an efficient, randomized procedure for synthesizing valid proofs and introduce Template Transformation, a data augmentation technique that enhances the model’s ability to handle complex logical expressions. The central evaluation question is whether an LLM has indeed learned to reason. We propose tests to measure the reasoning ability of a black-box LLM. By these measures, experiments demonstrate strong reasoning capabilities for assertions with short proofs, which decline with proof complexity. Notably, template transformation improves accuracy even for smaller models, suggesting its effectiveness across model scales. 1 Introduction In July 2024, The New York Times published an article aptly titled “ A.I. Can Write Poetry, but It Struggles With Math. ” ( Lohr, 2024 ) . General Large Language Models (LLMs) are indeed excellent at manipulating text but can be poor at logical reasoning, which is at the heart of mathematics and computing. This work aims to investigate experimentally whether that is an inherent limitation. LLM-based reasoning falls into two broad categories. In neuro-symbolic systems such as AlphaProof ( AlphaProof & teams, 2024 ) , the LLM guides a conventional proof-search engine, replacing hard-coded heuristics or hints provided by humans. In the second category, which our work belongs to, are LLMs that search for proofs directly. Chain-of-Thought (CoT) ( Wei et al., 2022 ) is one such system. The thought-chain produced by a CoT method is expressed in natural language. While easier for humans to understand, a natural-language proof cannot be automatically validated precisely, due to ambiguities inherent in natural language. In order to systematically investigate the reasoning capabilities of LLMs, it is simpler and more effective to express input assertions and output proofs in formal language. A “reasoning” LLM (Fig. 1 ) receives as input a set of assumptions and a goal assertion, both expressed in a formal logic. As output, the LLM exhibits a formal proof that explains how the goal follows logically from the assumptions. That is, an LLM acts as a proof generator. There are good reasons to believe that LLMs can act as proof generators and good reasons to believe that they cannot. On the positive side, LLMs are Turing-complete, assuming infinite precision arithmetic ( Pérez et al., 2019 ; Bhattamishra et al., 2020 ; Pérez et al., 2021 ; Strobl et al., 2024 ) . An LLM scans its input and past output to determine its next output symbol, using attention mechanisms to focus on the relevant portions. This is similar to how, in constructing a mathematical proof, humans select and combine past deductions to form new conclusions. Few-shot learning suggests that LLMs can recognize patterns and follow general rules. On the negative side, Turing completeness relies on unbounded integers (to encode an unbounded Turing machine tape); but in reality, machine integers have bounded precision. LLMs have bounded context, no auxiliary memory, and no backtracking ability; hence, colloquially, LLMs may “forget” the distant past. This is an issue for proof construction, as an assumption may not be required until a late stage of proof. LLMs operate statistically and may thus hallucinate and produce incorrect proofs even if the claim is valid. Finally, logical reasoning has a inherently high worst-case complexity: it is co-NP-complete even for Boolean logic, with rapidly increasing difficulty (e.g., RE-complete for first-order logic). To precisely formulate and test reasoning ability, we focus on reasoning in Boolean logic. In our view, there are several factors that make this a good choice. Boolean logic is the basis for other logics (e.g., first order, modal, temporal, and the like). Therefore, if Boolean reasoning turns out to be a challenging task for LLMs, it is unlikely that LLMs can do better on more sophisticated reasoning. Boolean logic has a simple proof system that makes it easy to automatically validate proofs. Semantically, Boolean reasoning is non-trivial, being co-NP-complete. (The dual question of Boolean satisfiability is the canonical NP-complete problem.) In a strong sense, therefore, Boolean reasoning can be viewed as the C.elegans ( Brenner, 2002 ) of LLM reasoning: structurally simple, semantically non-trivial, and exhibiting ”in the small” the central difficulties of general reasoning. The central challenges are (1) a scarcity of real-world training data, i.e., valid proofs, and (2) a means of determining whether a black-box model is reasoning rather than memorizing or guessing. We address these critical questions (1) by giving an efficient randomized algorithm for generating a large and diverse corpus of logically valid proofs for training and testing, and (2) by designing meaningful, automated, black-box tests of reasoning ability. The precision of formal language and the ability to automatically validate candidate proofs simplifies both tasks, enabling them to be carried out fully automatically, efficiently, and at scale. Our experiments show that Llama models can be trained to reason well in Boolean logic through a combination of synthetic proof generation and proof augmentation. Using only 9000 synthetically generated proofs as training data, our fine-tuned Llama-8B model reaches 98% accuracy on depth-7 proofs, outperforming GPT-4o’s few-shot learning performance (70% accuracy), despite having far fewer parameters. Our ablation studies reveal two key findings: larger model capacity enables better generalization to deeper proofs, while proof augmentation enhances the models’ ability to handle complex instances, particularly benefiting the smaller Llama-1B model. In our view, this work makes several contributions. One is the recognition that training an LLM over a formal logic has distinct advantages: synthetic data can be generated at large scale and variety for training, and reasoning ability can be evaluated robustly with automated tests that are generated and run at scale. The second is the choice of Boolean logic to study reasoning ability. If LLMs fail at Boolean logic, it is unlikely that they will succeed at more complex reasoning. The third is a technical contribution of template proof transformations, which produces syntactically varied proofs that share a common structure. In training, this forces the LLM to focus on abstract proof patterns rather than on concrete tokens, improving its generalization ability. A fourth contribution is the variety of proposed tests that can be applied to determine whether a black-box LLM is actually reasoning vs. guessing or retrieving answers. 2 Background In this section, we define the syntax and semantics of Boolean logic, introduce the Hilbert proof system, and forward and backward proof-construction mechanisms. 2.1 Boolean Logic: Syntax and Semantics Boolean formulas (also called assertions or expressions) are formed by combining Boolean variables that represent atomic propositions using familiar combinators, such as “and” ( \,\wedge\, ), “or” ( \,\vee\,) , “not” ( \neg ), and “implies” ( \,\rightarrow\, ). The Boolean domain is denoted \mathbb{B} . Given a countable set X of