# Gradient-Based Optimization on G"odel Logic as Discrete Local Search

arXiv: https://arxiv.org/abs/2503.01817 · HTML: https://mlsanity.com/paper/2503.01817/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 34 references that are in the map.
- First posted on arXiv 3 Mar 2025.

## Builds on (most cited first, 15 of 15)

- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts](https://mlsanity.com/paper/2402.12240/) (2024)
- [Deep Symbolic Learning: Discovering Symbols and Rules from Perceptions](https://mlsanity.com/paper/2208.11561/) (2022)
- [NSNet: A General Neural Probabilistic Framework for Satisfiability Problems](https://mlsanity.com/paper/2211.03880/) (2022)
- [On the Independence Assumption in Neurosymbolic Learning](https://mlsanity.com/paper/2404.08458/) (2024)
- [Logic of Differentiable Logics: Towards a Uniform Semantics of DL](https://mlsanity.com/paper/2303.10650/) (2023)
- [Mapping the Neuro-Symbolic AI Landscape by Architectures: A Handbook on Augmenting Deep Learning Through Symbolic Reasoning](https://mlsanity.com/paper/2410.22077/) (2024)
- [Refining neural network predictions using background knowledge](https://mlsanity.com/paper/2206.04976/) (2022)
- [Evaluating Relaxations of Logic for Neural Networks: A Comprehensive Study](https://mlsanity.com/paper/2107.13646/) (2021)
- [Comparing differentiable logics for learning with logical constraints](https://mlsanity.com/paper/2407.03847/) (2024)

## Built on by (most cited first, 2 of 2)

- [Logic of Hypotheses: from Zero to Full Knowledge in Neurosymbolic Integration](https://mlsanity.com/paper/2509.21663/) (2025)
- [Neurosymbolic Learning of Interpretable World Models](https://mlsanity.com/paper/2610.19955/) (2026)

## Abstract (arXiv)

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"odel 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"odel logic instantiates a discrete local search for Boolean satisfiability. Our formal analysis proves that each optimization step identifies and modifies a single variable within a 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"odel 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.