Gradient-Based Optimization on Gödel Logic as Discrete Local Search

Alessandro Daniele, Emile van Krieken · 2025

Read Gradient-Based Optimization on Gödel Logic as Discrete Local Search by Alessandro Daniele, Emile van Krieken (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-2503-01817.txt.

Introduction

Daniele and van Krieken show that optimizing over a certain fuzzy logic is secretly the same as running a classic discrete search. Neurosymbolic systems want gradient methods to tune logic, but soft relaxations often drift from true logic. Gödel semantics, they prove, maps cleanly onto Boolean values, so continuous tuning keeps one foot in exact logic.

Each gradient step, the analysis shows, flips exactly one variable inside one unsatisfied clause, mirroring a textbook satisfiability solver. Local optima are the main trap, so the authors add a stochastic reshaping trick to wander wider. Links to probability methods fall out along the way. Tests on satisfiability benchmarks and visual Sudoku back the theory. Their 2025 paper grounds differentiable logic search.

Catalog record

CREATORAlessandro Daniele, Emile van Krieken
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01817

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Gradient-Based Optimization on Gödel Logic as Discrete Local Search Alessandro Daniele, Emile van Krieken Abstract A fundamental challenge in neurosymbolic systems is applying continuous gradient-based optimization to discrete logical domains. While fuzzy relaxations provide differentiability, they often lack a formal structural alignment with classical logic. In this work, we show that Gödel semantics addresses this limitation through a homomorphism that maps its continuous interpretations to Boolean ones, allowing discrete variables to be encoded while maintaining full differentiability. Building on this foundation, we show that gradient-based optimization on Gödel logic instantiates a discrete local search for Boolean satisfiability. Our formal analysis proves that each optimization step identifies and modifies a single variable within an unsatisfied clause, precisely mimicking the steps of a discrete solver. We identify local optima as the primary limitation of such dynamics and introduce the Gödel Trick, a stochastic reparameterization technique designed to improve the exploration of the solution space. We further show a formal connection between this approach, probabilistic inference, and the Gumbel-Max trick. Experimental results on SAT benchmarks and the Visual Sudoku task validate our theoretical findings, demonstrating that our approach effectively navigates complex combinatorial landscapes and provides a solid foundation for differentiable discrete search 1 1 1 Code available at: https://github.com/DanieleAlessandro/Godel-Trick . Figure 1: The starting point of our work: there is a consistent mapping from Gödel to boolean interpretations. Example for formula \varphi=(A\lor B)\land\lnot B . (a) Gödel interpretation (active path highlighted in red); (b) the corresponding boolean interpretation; (c-d) plot of Gödel interpretation for \varphi (red) and the plane z=0 (gray): (c) side view, (d) top view; (e) truth table of \varphi in boolean logic. There is a one-to-one correspondence between the quadrants in (d) and the discrete values in (e). 1 Introduction Deep learning has revolutionized artificial intelligence, driven by the power of Gradient-Based Optimization ( GbO ) and its efficient implementation, that is the backpropagation [ 31 ] . While GbO excels in continuous domains, its integration into neurosymbolic (NeSy) systems remains a significant challenge due to the inherently discrete and combinatorial nature of symbolic reasoning [ 12 , 27 ] . The difficulty does not lie merely in rendering logical constraints differentiable, but in doing so without sacrificing the structural rigor of classical logic. A common strategy in the NeSy field is to employ fuzzy logics as continuous relaxations of Boolean operators [ 35 , 4 , 8 ] . By allowing truth values to range across the unit interval [0,1] , these “soft” logics provide a differentiable landscape suitable for GbO . However, this transition frequently leads to a semantic mismatch: as no fuzzy logic can satisfy all properties of classical logic [ 17 ] , the resulting continuous approximations often diverge from the intended logical behavior, failing to capture the discrete essence of symbolic tasks [ 35 ] . In this work, we demonstrate that Gödel logic is a remarkable exception to this trend. Rather than acting as a mere “soft” surrogate, we prove that Gödel semantics possesses unique algebraic properties that establish a structural bridge to Boolean logic. Specifically, we identify a homomorphism between Gödel and Boolean semantics that allows for a consistent mapping between the continuous and discrete worlds. Our central argument is that Gödel logic is “discrete in disguise”: we prove that its truth function produces sparse gradients, such that each optimization step identifies and modifies only a single variable and, when applied to a Conjunctive Normal Form (CNF) formula, it identifies and modifies only a single unsatisfied clause. This reveals that Gradient-based Optimization on Gödel logic ( GbOG ) does not simply approximate logic; it formally instantiates a discrete local search for Boolean satisfiability. By characterizing GbOG as a discrete Local Search Algorithm (LSA) for SAT, we can identify its primary theoretical limitation: similar to deterministic solvers like GSAT, it is prone to converging to local optima. To overcome this, we introduce the Gödel Trick (GT), a stochastic reparameterization technique that introduces noise into the optimization process to improve exploration. We show that the Gödel Trick is not merely a heuristic addition of noise, but provides a formal probabilistic grounding, acting as a Monte Carlo estimator for Weighted Model Counting (WMC). Our main theoretical contributions are threefold: (i) we prove the existence of a homomorphism between Gödel and classical logic semantics; (ii) we provide a formal proof of the sparsity of the Gödel gradient, demonstrating that gradient-based optimization on Gödel logic circuits behaves as a LSA; (iii) we identify local optima as the fundamental barrier to convergence in this framework and introduce the Gödel Trick ( GT ), a stochastic variant of Gödel optimization. Moreover, we establish its formal connection to probabilistic inference, showing it serves as an efficient Monte Carlo estimator for probabilistic interpretations and connecting it to the Gumbel-Max trick [ 16 , 19 ] . The remainder of the paper validates these theoretical findings through evaluation of GT on SAT benchmarks [ 18 ] and the Visual Sudoku task [ 3 ] . 2 Background and notation Propositional formulas are defined recursively as: \varphi::=p\mid\neg\varphi_{1}\mid(\varphi_{1}\land\varphi_{2})\mid(\varphi_{1}\lor\varphi_{2}), where p\in P is an atomic proposition, and \neg , \land , \lor denote negation, conjunction, and disjunction. We consider two semantics: classical (Boolean) logic and Gödel logic. In classical logic, formulas are assigned binary truth values in \{-1,1\} 2 2 2 Without loss of generality, we use 1 and -1 as true and false , respectively . Gödel logic generalises classical logic by allowing truth values to be real numbers in the range [0,1] , where 0 represents false, 1 represents true. In the remainder, we adopt truth values of formulas over the real number space \mathbb{R} instead of [0,1] 3 3 3 We consider logits in \mathbb{R} , that is, the outputs of a neural network before applying the sigmoid function. More details in the Supplementary Materials. . An interpretation is a function that maps formulas in truth values and is defined recursively as: Formula Boolean \mathcal{B}(\varphi) Gödel \mathcal{G}(\varphi) p_{i} \in\{-1,1\} \in\mathbb{R} \lnot\varphi -\mathcal{B}(\varphi) -\mathcal{G}(\varphi) \varphi_{1}\land\varphi_{2} \min(\mathcal{B}(\varphi_{1}),\mathcal{B}(\varphi_{2})) \min(\mathcal{G}(\varphi_{1}),\mathcal{G}(\varphi_{2})) \varphi_{1}\lor\varphi_{2} \max(\mathcal{B}(\varphi_{1}),\mathcal{B}(\varphi_{2})) \max(\mathcal{G}(\varphi_{1}),\mathcal{G}(\varphi_{2})) Note that the interpretation of any formula is recursively determined by the interpretation of atomic propositions. In the following, we sometimes represent an interpretation compactly using a vector of truth values over the atomic propositions: \boldsymbol{\mu}=\langle\mathcal{G}(p_{i})\rangle_{i=1}^{n} , and write \mathcal{G}(\varphi;\boldsymbol{\mu}) to denote the value of formula \varphi , assuming \mathcal{G}(p_{i})=\mu_{i} . This notation is particularly useful for Theorem 3 , as it allows us to treat the interpretation as a fixed function on vector \boldsymbol{\mu} . Similarly, we use \boldsymbol{\gamma}=\langle\mathcal{B}(p_{i})\rangle_{i=1}^{n} and \mathcal{B}(\varphi;\boldsymbol{\gamma}) for the boolean interpretation. 3 Related Work The neurosymbolic (NeSy) field focuses on incorporating logical knowledge into learning systems [ 32 , 23 , 38 ] . A prominent research direction investigates the continuous relaxation of logical constraints by adopting t-norm based fuzzy semantics. This framework enables the definition of differentiable logic layers, where logical formulas are translated into continuous functions suitable for gradient-based optimization. Logic Tensor Networks (LTN) [ 4 ] and Semantic-Based Regularization (SBR) [ 11 ] inject prior knowledge into neural networks by embedding fuzzy logic in loss functions. These methods allow for the choice of different fuzzy semantics that have been extensively analyzed and compared in terms of

Read the complete text