# FourierCSP: Differentiable Constraint Satisfaction Problem Solving by Walsh-Fourier Expansion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 51 references that are in the map.
- First posted on arXiv 6 Oct 2025.

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

- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Quantitative Verification of Neural Networks And its Security Applications](https://mlsanity.com/paper/1906.10395/) (2019)
- [FourierSAT: A Fourier Expansion-Based Algebraic Framework for Solving Hybrid Boolean Constraints](https://mlsanity.com/paper/1912.01032/) (2019)
- [Massively Parallel Continuous Local Search for Hybrid SAT Solving on GPUs](https://mlsanity.com/paper/2308.15020/) (2023)
- [Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming](https://mlsanity.com/paper/2401.17527/) (2024)
- [Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction](https://mlsanity.com/paper/2502.15794/) (2025)
- [On Continuous Local BDD-Based Search for Hybrid SAT Solving](https://mlsanity.com/paper/2012.07983/) (2020)
- [DeepSaDe: Learning Neural Networks that Guarantee Domain Constraint Satisfaction](https://mlsanity.com/paper/2303.01141/) (2023)
- [A Scalable Shannon Entropy Estimator](https://mlsanity.com/paper/2206.00921/) (2022)
- [Quantum-Inspired Perfect Matching under Vertex-Color Constraints](https://mlsanity.com/paper/2209.13063/) (2022)
- [Beyond Local Selection: Global Cut Selection for Enhanced Mixed-Integer Programming](https://mlsanity.com/paper/2503.15847/) (2025)
- [Learning Branching Heuristics from Graph Neural Networks](https://mlsanity.com/paper/2211.14405/) (2022)

## Abstract (arXiv)

The Constraint-satisfaction problem (CSP) is fundamental in mathematics, physics, and theoretical computer science. Continuous local search (CLS) solvers, as recent advancements, can achieve highly competitive results on certain classes of Boolean satisfiability (SAT) problems. Motivated by these advances, we extend the CLS framework from Boolean SAT to general CSP with finite-domain variables and expressive constraint formulations. We present FourierCSP, a continuous optimization framework that generalizes the Walsh-Fourier transform to CSP, allowing for transforming versatile constraints to compact multilinear polynomials, thereby avoiding the need for auxiliary variables and memory-intensive encodings. We employ projected subgradient and mirror descent algorithms with provable convergence guarantees, and further combine them to accelerate gradient-based optimization. Empirical results on benchmark suites demonstrate that FourierCSP is scalable and competitive, significantly broadening the class of problems that can be efficiently solved by differentiable CLS techniques and paving the way toward end-to-end neurosymbolic integration.