Research map / Probabilistic and scientific modeling / Variational and generative sampling
Streamlining Variational Inference for Constraint Satisfaction Problems
Aditya Grover, Tudor Achim, Stefano Ermon
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace single-variable decimation with disjunction streamlining constraints | Survey propagation solver · Random 3-SAT | algorithmic threshold: 4.25 to 4.255 | Improved |
| Replace single-variable decimation with disjunction streamlining constraints | Survey propagation solver · Random 4-SAT | algorithmic threshold: 9.775 to 9.8 | Improved |
| Replace single-variable decimation with disjunction streamlining constraints | Survey propagation solver · Random 5-SAT | algorithmic threshold: 20.1 to 20.3 | Improved |
| Replace single-variable decimation with disjunction streamlining constraints | Survey propagation solver · Random 6-SAT | algorithmic threshold: 39 to 39.5 | Improved |
| Use streamlining constraints instead of decimation | Survey propagation solver on random k-SAT · Random k-SAT | gap between algorithmic thresholds and theoretical satisfiability limits: 16.3% | Improved |
| Use streamlining constraints instead of decimation | Survey propagation solver on satisfiable random k-SAT instances · Random k-SAT | local search timeout failures (%): 36% to 24% | Improved |
| Preprocess with streamlining constraints before Dimetheus | Dimetheus · Random 3-SAT and 4-SAT | solver success rate | No clear effect |
| Preprocess with streamlining constraints before Dimetheus | Dimetheus · Random 5-SAT and 6-SAT | solver success rate | Improved |
| Add streamlining constraints | Survey propagation solver · 2-XORSAT | solver performance | Improved |
| Pair highest-magnetization candidates with lowest-magnetization candidates (ablation) | Survey inspired streamlining · Random CSPs | solver performance | Improved |
Closest papers by meaning
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.86)
- Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction (ICML 2025 · similarity 0.85)
- Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces (NeurIPS 2026 · similarity 0.85)
- Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.85)
- Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems (NeurIPS 2026 · similarity 0.84)
- On the Modelling of Constraints with Tractable Logical Operators (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
