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 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ö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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2503.01817 [cs.LG] |
| (or arXiv:2503.01817v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2503.01817 arXiv-issued DOI via DataCite |
From: Alessandro Daniele [view email]
[v1]
Mon, 3 Mar 2025 18:42:13 UTC (386 KB)
[v2]
Thu, 30 Apr 2026 10:48:56 UTC (3,862 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。