Natural Language to First-Order Logic LLM-based Autoformalization¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Autoformalization, First-Order Logic, Ontology Extraction, Logical Translation, Neurosymbolic Reasoning
TL;DR¶
Addressing the lack of unified task formulations and systematic surveys in natural language to First-Order Logic (FOL) autoformalization, this paper formalizes the problem as an ontology-relative tuple decoupling Ontology Extraction (OE) from Logical Translation (LT), while providing a comprehensive survey of benchmark datasets, syntactic/semantic evaluation metrics, and LLM enhancement techniques across fine-tuning, prompting, and verification-refinement loops.
Background & Motivation¶
Natural language (NL) provides an expressive, flexible, and human-friendly medium for everyday communication, yet its intrinsic vagueness, contextual entanglement, and syntactic ambiguity make it ill-suited for interaction with formal automated reasoning tools (such as automated theorem provers and SMT solvers). Autoformalization bridges this semantic gap by automatically translating natural language sentences into rigorous specifications within a target formal semantic framework. In recent years, Large Language Models (LLMs) have substantially revitalized autoformalization research, exhibiting remarkable general-purpose linguistic fluency and in-context adaptation. In multi-step logical reasoning, formal verification, AI safety guarantees, legal informatics, and argument mining, combining LLM-based autoformalization with symbolic backend solvers has consistently outperformed pure end-to-end prompting, with First-Order Logic (FOL) emerging as the sweet spot between expressive representation and algorithmic tractability.
Despite this surging interest, the field of FOL-based autoformalization has been hobbled by the lack of a standardized task formulation and cross-study evaluation consistency. Existing literature predominantly conceptualizes autoformalization through an informal, monolithic black-box lens: mapping a natural language sentence \(p\) directly into a first-order logic formula \(\varphi\). This oversimplified formulation obscures the fundamental role of ontological commitments. A single NL sentence naturally admits multiple valid formalizations depending on representational granularity. For example, given "Every student passed some exam," one could formalize the passing event as a binary relation \(Passed(x, y)\), compress both the exam and the passing action into a unary predicate \(PassedSomeExam(x)\), or introduce explicit reified objects \(Grade(x, y, g)\) and quality attributes \(Sufficient(g)\). All three candidates represent legitimate translations, yet they commit to drastically different vocabularies, natural language meaning labels, and implicit background theories. Evaluating systems by comparing generated formulas directly against references—without explicit account of their presupposed ontologies—inevitably conflates disparate ontological choices with genuine translation inaccuracies.
To establish a solid scientific foundation, this paper formalizes the autoformalization task from an ontological perspective. The authors represent the formalization outcome not as a raw formula \(\varphi\), but as a joint pair \(\langle \varphi, \Omega \rangle\), where the formal ontology \(\Omega = \langle \sigma, L, T \rangle\) explicitly specifies the signature \(\sigma\), the natural language semantic labelling function \(L\), and the background theory \(T\). Core idea: mathematically reframe natural language to first-order logic autoformalization as an ontology-relative task decomposing into Ontology Extraction (OE) and Logical Translation (LT), establishing a rigorous taxonomy of benchmarks, SMT-based logical equivalence metrics, and neurosymbolic verification loops.
Method¶
Overall Architecture¶
The framework proposed in this paper establishes a systematic, modular methodology that unifies theoretical formulation, evaluation protocols, and performance enhancement paradigms for FOL autoformalization. Taking a natural language sentence \(p\) accompanied by optional contextual knowledge \(K\) as input, the system targets the generation of an explicit logical formula \(\varphi\) alongside its grounding ontology \(\Omega = \langle \sigma, L, T \rangle\), systematically orchestrating generation, validation, and iterative repair.
The pipeline operates across three foundational pillars: first, Ontology-Aware Task Decomposition separates the unconstrained conversion into Ontology Extraction (OE), which identifies domain predicates, constants, arities, and meanings from text, and Logical Translation (LT), which focuses purely on structural and quantified translation under a fixed ontology; second, Two-Stage Semantic Evaluation bypasses surface syntactic mismatch by establishing signature alignment followed by SMT-based logical equivalence checking; third, Neurosymbolic Verification & Refinement Loops integrate theorem provers and SMT engines to detect syntax violations and generate counterexamples, prompting LLMs to iteratively self-correct.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input Text p + Context K"] --> B["Ontology-Aware Task Decomposition<br/>Decouple OE & LT via Formal Ontology Ω"]
B --> C["Two-Stage Semantic Evaluation<br/>Signature Alignment + SMT Equivalence"]
C --> D["Neurosymbolic Verification & Refinement<br/>Prover Feedback + SMT Counterexamples"]
D --> E["Faithful Formula φ and Grounded Ontology Ω"]
Key Designs¶
1. Ontology-Aware Task Decomposition: Resolving Raw Translation Ambiguity -> Decoupling OE from LT -> Grounding Formal Semantics
Conventional formulations frame autoformalization as \(p \mapsto \varphi\), which leaves the underlying signature vocabulary and semantic grounding implicit, causing cross-model evaluations to conflate legitimate differences in conceptual granularity with translation failures. To resolve this ambiguity, this work formally defines an ontology as a triple \(\Omega = \langle \sigma, L, T \rangle\), where signature \(\sigma = (V, C, F, R)\) defines the non-logical symbols and arities, labelling function \(L: \sigma \to \text{NL}\) maps each symbol to an explicit natural language meaning specification, and theory \(T\) specifies background domain axioms (e.g., \(\forall x (\text{Cube}(x) \to \neg \text{Tet}(x))\)). The task is then defined as producing \(\langle \varphi, \Omega \rangle\) such that \(\varphi\) holds if and only if \(p\) is true under the interpretations of \(L\) and constraints of \(T\). This formalization decouples the overarching problem into Ontology Extraction (OE), which constructs the reusable conceptual ontology \(\langle p, K \rangle \mapsto \Omega\), and Logical Translation (LT), which performs constraint-guided semantic parsing \(\langle p, \Omega \rangle \mapsto \varphi\). This modularization guarantees that translation accuracy can be evaluated without noise from vocabulary mismatch.
2. Two-Stage Semantic Evaluation: Eliminating Lexical Fragility -> Symbol Matching and SMT Equivalence -> Rigorous Equivalence Guarantee
Evaluating FOL formulas using downstream proxy tasks (such as Natural Language Inference) introduces severe false-positive vulnerabilities where flawed premises and conclusions accidentally derive matching truth values. Conversely, direct syntactic metrics (Exact Match, BLEU, Tree Edit Distance) fail entirely when encountering predicate renamings or quantifier order swaps, while continuous relaxations like the LE score discard quantifier prefixes via propositional reduction. To overcome these limitations, the paper establishes a two-stage direct semantic evaluation protocol. In the Symbol Matching stage, rather than relying on brittle surface string distance metrics (e.g., Levenshtein distance), the protocol leverages the LT setup where the labelled signature is supplied upfront, resolving symbol anchoring by construction. In the Formula Closeness stage, automated theorem provers and SMT solvers (such as Z3 or CVC5) determine semantic identity: candidate formula \(\varphi\) is logically equivalent to ground truth \(\hat{\varphi}\) if and only if the negation of their equivalence, \(\neg(\varphi \leftrightarrow \hat{\varphi})\), is unsatisfiable (UNSAT). This provides an absolute, model-theoretic proof of translation fidelity.
3. Neurosymbolic Verification & Refinement Loops: Mitigating Generation Hallucinations -> Automated Solver Diagnostics & Counterexamples -> Closed-Loop Repair
LLM generation of first-order formulas frequently suffers from syntactic malformations (mismatched parentheses, unbound free variables, illegal arities) and subtle semantic inversions. Pure neural self-reflection often falls into repetitive loops or trivial modifications without resolving root errors. This work categorizes and formalizes neurosymbolic closed-loop refinement mechanisms. In Syntactic Verification, generated formulas pass through automated logic parsers or provers; diagnostic execution traces and parser errors are reflected into iterative prompts, or decoding is dynamically restricted via Grammar-Constrained Decoding. In Semantic Verification, SMT solvers extract Unsatisfiable Cores (unsat cores) from conflicting axiom sets to pinpoint faulty subformulas, or synthesize explicit counterexample interpretations when candidate formulas diverge. These concrete counterexamples are formatted into natural language prompts, directing the LLM to resolve precise quantifier scope and implication misalignments.
A Worked Example¶
Consider the sentence: "Every student passed some exam."
- Ontology Extraction (OE Stage):
- Extracted Signature: \(\sigma = \{\text{Student}/1, \text{Exam}/1, \text{Passed}/2\}\);
- Labelling: \(L(\text{Student}) = \text{"x is a student"}\), \(L(\text{Exam}) = \text{"x is an exam"}\), \(L(\text{Passed}) = \text{"x passed y"}\);
- Theory: \(T = \emptyset\).
- Logical Translation (LT Stage):
- Target formula: \(\hat{\varphi} = \forall x (\text{Student}(x) \to \exists y (\text{Exam}(y) \land \text{Passed}(x, y)))\).
- Suppose the model erroneously outputs an inverted quantifier formula: \(\hat{\varphi}_{\text{err}} = \exists y (\text{Exam}(y) \land \forall x (\text{Student}(x) \to \text{Passed}(x, y)))\) ("There exists a single specific exam that all students passed").
- Verification & Refinement (SMT Stage):
- The SMT solver checks the satisfiability of \(\neg(\hat{\varphi} \leftrightarrow \hat{\varphi}_{\text{err}})\).
- The solver returns SAT and synthesizes a concrete model: a domain containing students \(s_1, s_2\) and exams \(e_1, e_2\), where \(s_1\) passes only \(e_1\) and \(s_2\) passes only \(e_2\). Under this structure, \(\hat{\varphi}\) evaluates to True while \(\hat{\varphi}_{\text{err}}\) evaluates to False.
- The counterexample is transformed into natural language feedback, enabling the LLM to diagnose its quantifier scope error and immediately correct the output to \(\hat{\varphi}\).
Loss & Training¶
Model fine-tuning strategies span Supervised Fine-Tuning (SFT), Reinforcement Learning (RL), and preference optimization. LogicLLaMA utilizes an RL reward combining lexical matching and propositional logical equivalence: $\(R(\hat{\varphi}, \varphi) = \alpha \cdot \text{BLEU}(\hat{\varphi}, \varphi) + (1-\alpha) \cdot \text{LE}(\hat{\varphi}, \varphi)\)$ where the \(\text{LE}\) score calculates the proportion of agreeing truth assignments over propositionalized variables. In preference optimization, Direct Preference Optimization (DPO) optimizes generation policies over ranked pairs: $\(\mathcal{L}_{\text{DPO}}(\theta) = -\mathbb{E}_{(p, \varphi_w, \varphi_l)} \left[ \log \sigma \left( \beta \log \frac{\pi_\theta(\varphi_w \mid p)}{\pi_{\text{ref}}(\varphi_w \mid p)} - \beta \log \frac{\pi_\theta(\varphi_l \mid p)}{\pi_{\text{ref}}(\varphi_l \mid p)} \right) \right]\)$ Empirical studies reveal that combining SFT pre-training with preference optimization (KTO or quality-weighted DPO) effectively mitigates structural quantifier inversions.
Key Experimental Results¶
Main Results: Comprehensive Overview of NL-FOL Datasets¶
The survey categorizes and contrasts all major datasets pairing natural language with first-order logic formulas, highlighting their generation mechanisms, validation rigor, and structural trade-offs.
| Dataset | NL Source | FOL Source | No. of Pairs | Construction & Validation Pipeline | Key Strengths & Documented Caveats |
|---|---|---|---|---|---|
| FOLIO (Han et al., 2024) | Human Experts | Human Experts (*) | ~3,800 (~500 stories, 2.4k premises, 1.4k conclusions) | Experts author stories and formalize FOL; provers verify NLI entailment label consistency | Premier human benchmark; independent audits uncover ~10-15% ambiguous or erroneous annotations (Brunello et al., 2026a) |
| GGC (Barker-Plummer et al., 2011a) | Human Students | Human Students (*) | ~280 | Student submissions from Tarski's World exercises in Language, Proof and Logic | High syntactic and semantic consistency enforced by automated grading; limited domain and scale |
| MALLS (Yang et al., 2024) | LLM (GPT-4) | LLM (GPT-4) | ~28,000 | Dual GPT-4 generation using dynamic n-gram counters to diversify logic patterns | Human review of 1K subset informs rule-based noise filtering; machine alignment noise still persists |
| ProverQA (Qi et al., 2025) | LLM (*) (GPT-4) | Rule-based | ~17,000 | Symbolic engine generates valid FOL graphs; LLM back-translates into human-readable NL stories | Guarantees rigorous formal syntax and semantics by construction; linguistic patterns lack natural variation |
| Willow (Deveci, 2024) | LLM (GPT-4) | LLM (GPT-4) | ~16,000 | GPT-4 expands ~300 verified human seed pairs; discards grammar check failures | Large scale, but semantic NL-FOL alignment is only partially validated |
| PROOFFOL (Thatikonda et al., 2024) | Human Written | LLM (*) (GPT-4o) | ~10,000 | GPT-4o formalizes ProofWriter text; filters by theorem prover verdict matching ground-truth | Solver consistency ensures high structural fidelity; constrained by ProofWriter template grammar |
| Text2log (Levkovskyi & Li, 2021) | Rule-based | Rule-based (*) | ~100,000 | CCG-based semantic parser maps template NL sentences directly into FOL formulas | Completely sound and correct by construction; restricted expressiveness and templated phrasing |
Ablation Study: Comparison of FOL Evaluation Metrics¶
The survey analyzes the operational trade-offs across syntactic metrics, semantic distances, and proxy evaluation paradigms.
| Evaluation Metric / Paradigm | Evaluation Level | Core Mechanism & Formulation | Output Range | Theoretical Merit | Vulnerability & Failure Mode |
|---|---|---|---|---|---|
| Exact Match (EM) | Syntactic | Normalized string comparison: \(\mathbb{I}[\text{norm}(\varphi) == \text{norm}(\hat{\varphi})]\) | Binary | Fast, lightweight, zero external solver dependencies | Penalizes valid logical variations, variable alpha-renaming, and commutative conjunction reordering |
| Tree Edit Distance (TED) | Syntactic | Minimum-cost AST node transformations | Continuous \([0, \infty)\) | Reflects hierarchical structural similarity | Purely syntactic; semantically identical formulas with different tree forms receive high penalties |
| BLEU Score | Syntactic | n-gram precision over specialized FOL tokenization | Continuous \([0, 1]\) | Differentiable proxy for reinforcement learning rewards | Blind to scope bindings; assigns high scores to formulas with fatal quantifier flips |
| LogicSim | Syntactic | Aggregates symbol differences and IoU: \(pd + tp + ld + IoU\) | Continuous \([0, \infty)\) | Captures symbol count and operator overlap | Heuristic weight combination lacking model-theoretic foundation |
| LE Score (Yang et al.) | Semantic | Proportion of agreeing truth assignments: $\frac{ | {v \mid v(\varphi) = v(\hat{\varphi})} | }{2^n}$ | Continuous \([0, 1]\) |
| SMT Equivalence | Semantic | Dual entailment unsatisfiability: \(\text{UNSAT}(\neg(\varphi \leftrightarrow \hat{\varphi}))\) | Binary | Fully rigorous, model-theoretic gold standard | Binary output provides no training gradient; requires pre-aligned signature \(\sigma\) |
| NLI Entailment (Proxy) | Proxy Task | Theorem prover check: \(\{\varphi_i\} \vdash \psi \iff \{p_i\} \models c\) | Binary | Bypasses the need for expensive ground-truth formulas | Prone to false positives from canceling errors; cannot isolate single-sentence errors |
Key Findings¶
- Benchmark Annotation Noise Distorts Model Comparisons: Independent validation reveals non-negligible error rates in widely used splits of FOLIO and MALLS. These annotation flaws significantly skew reported model rankings, underscoring the urgent necessity of deploying verified, human-curated benchmarks.
- Frontier Models Excel at Logical Translation (LT) but Falter at Ontology Extraction (OE): When supplied with explicit signatures and semantic labels, modern reasoning LLMs (e.g., o1, GPT-4o with CoT) achieve strong logical translation accuracy. However, in unconstrained autoformalization where models must infer the signature independently, performance degrades sharply due to inconsistent ontology design.
- Neurosymbolic Feedback Yields the Best Efficiency-Performance Trade-off: Rather than costly full-parameter fine-tuning, coupling moderately sized models with lightweight syntax checkers and SMT-guided counterexample feedback delivers near-SOTA formalization accuracy while preserving interpretability.
Highlights & Insights¶
- Decoupling OE and LT as a Formal Paradigm Shift: Introducing the ontology tuple \(\Omega = \langle \sigma, L, T \rangle\) provides a mathematically rigorous formulation that separates vocabulary conceptualization from logical deduction, resolving years of ambiguous evaluation in autoformalization.
- SMT-Driven Counterexample Feedback as a Generalizable Engine: Using SMT solvers to synthesize concrete counterexamples from \(\neg(\varphi \leftrightarrow \hat{\varphi})\) establishes a bidirectional bridge between symbolic reasoning and neural reflection, a technique directly applicable to software specification and agent planning.
Limitations & Future Work¶
- Authors' Acknowledged Limitations: Due to the severe lack of standardized evaluation protocols and the prevalence of benchmark annotation noise, the survey deliberately refrains from presenting unified leaderboard rankings across disparate enhancement strategies.
- Identified Limitations: The survey focuses predominantly on static First-Order Logic, omitting dynamic and temporal extensions (e.g., LTL, CTL), modal logic, or non-monotonic default reasoning. Furthermore, it leaves the algorithmic connection to formal Semantic Web ontology learning unaddressed.
- Future Directions: Key avenues include developing dedicated benchmarks for standalone Ontology Extraction, exploring structured intermediate representations, and integrating formal autoformalization pipelines into end-to-end industrial verification and AI safety frameworks.
Related Work & Insights¶
- vs. LINC (Olausson et al., 2023) / Logic-LM (Pan et al., 2023): These works deploy FOL autoformalization purely as an engineering module for question answering, overlooking ontology preservation and formalization quality; this paper elevates autoformalization into a standalone scientific discipline.
- vs. LogicLLaMA (Yang et al., 2024): LogicLLaMA relies on the propositional LE score for reinforcement learning, obscuring quantifier errors; this work proves that SMT-based logical equivalence under aligned signatures is the only reliable ground-truth metric.
- vs. LTRAG (Hu et al., 2025) / FOVER (Pei et al., 2025): While these approaches employ heuristic multi-stage prompting, this paper establishes the overarching theoretical and model-theoretic foundation for the OE/LT decomposition.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ Establishes the first principled ontological definition of FOL autoformalization and systematically unifies the OE/LT decomposition.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Provides an exhaustive, critical analysis of all existing FOL datasets, evaluation metrics, and LLM enhancement techniques.
- Writing Quality: ⭐⭐⭐⭐⭐ Exceptionally rigorous mathematical formulations, clear taxonomy, and compelling conceptual clarity.
- Value: ⭐⭐⭐⭐⭐ Serves as the definitive reference guide and foundational roadmap for neurosymbolic reasoning and formal logic autoformalization in the LLM era.