Research map / Reinforcement learning / Imitation learning
Boolean Satisfiability via Imitation Learning
Zewei Zhang, Huan Liu, YUANHAO YU, Jun Chen, Xiangyu Xu
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 |
|---|---|---|---|
| add variable permutation augmentation (ablation) | ImitSAT · Random 3-SAT 5-15 | MRPP / W1%: MRPP 1.00 -> 0.75; W1% 0.28 -> 0.64 | Improved |
| add staged curriculum (5-15 then 16-30) vs 16-30 only at matched 130k steps (ablation) | ImitSAT · Random 3-SAT 5-15 | MRPP: 1.00 -> 0.75 | Improved |
| curriculum vs training from scratch at fully matched 430k steps (ablation) | ImitSAT · Random 3-SAT 16-30 | MRPP: 0.80 (w/o stage*) vs 0.83 (w/ stage) | No clear effect |
| replace CNF tokens with GNN embeddings (ablation) | ImitSAT · Random 3-SAT 5-15 | MRPP: 0.75 -> 1.00 | Hurt |
| query model at first decision instead of after 3 VSIDS decisions (single call) (ablation) | ImitSAT · Random 3-SAT 5-15 | MRPP / W1%: 1.00 -> 0.91; 0.27 -> 0.55 | Improved |
| spend 3 calls at first decision vs 1 per 3 VSIDS decisions (ablation) | ImitSAT · Random 3-SAT 100 vars | MRPP: 0.95 -> 0.76 | Improved |
| increase query budget beyond 3 calls (ablation) | ImitSAT · Random 3-SAT 5-15 | MRPP / W1% | No clear effect |
| Top-K masking of illegal literals instead of VSIDS fallback (ablation) | ImitSAT · JNH and AIM | MRPP | Hurt |
| train only on random 3-SAT, test on structured SATLIB families without tuning | ImitSAT · SATLIB families | MRPP: JNH 1.00-0.85, PARITY 0.30 | Improved |
| retrain Graph-Q-SAT on same dataset (GQSAT*) | Graph-Q-SAT · Random 3-SAT test sets | MRPP: e.g. 5-15: 1.00 -> 1.38 | Hurt |
| use ImitSAT with 5 calls instead of 3 | ImitSAT · Random 3-SAT 100 vars | MRPP: 0.76 -> 0.83 | Hurt |
Closest papers by meaning
- A Cardinal Improvement to Pseudo-Boolean Solving (AAAI 2020 · similarity 0.90)
- Learning Local Search Heuristics for Boolean Satisfiability (NeurIPS 2019 · similarity 0.89)
- Guiding CDCL SAT Search via Random Exploration amid Conflict Depression (AAAI 2020 · similarity 0.87)
- Learning Better Representations From Less Data For Propositional Satisfiability (NeurIPS 2024 · similarity 0.86)
- SAT-Based Tree Decomposition with Iterative Cascading Policy Selection (AAAI 2024 · similarity 0.86)
- Learning How to Cube (NeurIPS 2026 · similarity 0.85)
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.
