# The Theory and Practice of MAP Inference over Non-Convex Constraints

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 70 references that are in the map.
- First posted on arXiv 9 Feb 2026.

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

- [Modeling Tabular data using Conditional GAN](https://mlsanity.com/paper/1907.00503/) (2019)
- [Learning Physical Models that Can Respect Conservation Laws](https://mlsanity.com/paper/2302.11002/) (2023)
- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Gradient-Free Generation for Hard-Constrained Systems](https://mlsanity.com/paper/2412.01786/) (2024)
- [Time Weaver: A Conditional Time Series Generation Model](https://mlsanity.com/paper/2403.02682/) (2024)
- [ROAD-R: The Autonomous Driving Dataset with Logical Requirements](https://mlsanity.com/paper/2210.01597/) (2022)
- [Neural Probabilistic Logic Programming in Discrete-Continuous Domains](https://mlsanity.com/paper/2303.04660/) (2023)
- [Sum of Squares Circuits](https://mlsanity.com/paper/2408.11778/) (2024)
- [A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts](https://mlsanity.com/paper/2406.10368/) (2024)
- [Beyond the convexity assumption: Realistic tabular data generation under quantifier-free real linear constraints](https://mlsanity.com/paper/2502.18237/) (2025)
- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [Efficient Search-Based Weighted Model Integration](https://mlsanity.com/paper/1903.05334/) (2019)
- [Scaling up Hybrid Probabilistic Inference with Logical and Arithmetic Constraints via Message Passing](https://mlsanity.com/paper/2003.00126/) (2020)
- [Taming the Sigmoid Bottleneck: Provably Argmaxable Sparse Multi-Label Classification](https://mlsanity.com/paper/2310.10443/) (2023)
- [A Probabilistic Neuro-symbolic Layer for Algebraic Constraint Satisfaction](https://mlsanity.com/paper/2503.19466/) (2025)
- [Symbol Grounding in Neuro-Symbolic AI: A Gentle Introduction to Reasoning Shortcuts](https://mlsanity.com/paper/2510.14538/) (2025)
- [Enhancing SMT-based Weighted Model Integration by Structure Awareness](https://mlsanity.com/paper/2302.06188/) (2023)
- [How to Square Tensor Networks and Circuits Without Squaring Them](https://mlsanity.com/paper/2512.17090/) (2025)
- [Optimization Modulo Theories with Linear Rational Costs](https://mlsanity.com/paper/1410.6039/) (2014)
- [SMT-based Weighted Model Integration with Structure Awareness](https://mlsanity.com/paper/2206.13856/) (2022)
- [On CNF Conversion for SAT and SMT Enumeration](https://mlsanity.com/paper/2303.14971/) (2023)
- [Probabilistic Circuits with Constraints via Convex Optimization](https://mlsanity.com/paper/2403.13125/) (2024)

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

- [Concise and Logically Consistent Conformal Sets for Neuro-Symbolic Concept-Based Models](https://mlsanity.com/paper/2605.18202/) (2026)

## Abstract (arXiv)

In many safety-critical settings, probabilistic ML systems have to make predictions subject to algebraic constraints, e.g., predicting the most likely trajectory that does not cross obstacles. These real-world constraints are rarely convex, nor the densities considered are (log-)concave. This makes computing this constrained maximum a posteriori (MAP) prediction efficiently and reliably extremely challenging. In this paper, we first investigate under which conditions we can perform constrained MAP inference over continuous variables exactly and efficiently and devise a scalable message-passing algorithm for this tractable fragment. Then, we devise a general constrained MAP strategy that interleaves partitioning the domain into convex feasible regions with numerical constrained optimization. We evaluate both methods on synthetic and real-world benchmarks, showing our approaches outperform constraint-agnostic baselines, and scale to complex densities intractable for SoTA exact solvers.