Research map / Learning theory and algorithms / Combinatorial and search optimization
Using Certifying Constraint Solvers for Generating Step-wise Explanations
Ignace Bleukx, Maarten Flippo, Bart Bogaerts, Emir Demirović, Tias Guns
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 |
|---|---|---|---|
| generate the step-wise explanation from a solver proof (Trim) instead of SimplifyGreedy | step-wise explanation generation · Sudoku and Job-shop runtime | runtime: about 100x faster | Improved |
| use proof-based approach instead of SimplifyGreedy on Modeling examples | step-wise explanation generation · Modeling examples (102 instances) | instances solved within 1h: SimplifyGreedy fails on 29 of 102 instances | Improved |
| slowest proof-based variant (Min. glob + Min. loc) versus SimplifyGreedy | step-wise explanation generation · all benchmarks | runtime: at least 10 times faster | Improved |
| add global minimization at end of pipeline to Trim (ablation) | Trim · Sudoku | average max step size: 7.5 -> 3.4 | Improved |
| add local minimization at end of pipeline to Trim (ablation) | Trim · Job-shop | average max step size: 2.7 -> 1.0 | Improved |
| add local minimization at end of pipeline to Trim (ablation) | Trim · Modeling examples | average max step size: 3.5 -> 2.1 | Improved |
| add global minimization at end of pipeline to Trim (ablation) | Trim · Sudoku | average sequence length: 85.9 -> 62.6 | Improved |
| use global instead of local minimization (ablation) | Trim + Min. · Sudoku | runtime: Trim + Min. loc around 5-10 times faster than Trim + Min. glob | Hurt |
| use global instead of local minimization (ablation) | Trim + Min. · Sudoku | average max step size: 4.2 -> 3.4 | Improved |
| minimize after simplification to domain reductions instead of before (ablation) | proof minimization pipeline · Job-shop, Sudoku | runtime | Improved |
| use local minimization instead of simple trimming (ablation) | proof pipeline · all benchmarks | explanation quality | Improved |
| use proof-based Trim + Min. glob versus SimplifyGreedy | step-wise explanation generation · Sudoku and Modeling examples | average max step size: 3.4 vs 1.2 (Sudoku), 2.0 vs 1.4 (Modeling) | Hurt |
Closest papers by meaning
- ImProver: Agent-Based Automated Proof Optimization (ICLR 2025 · similarity 0.86)
- MPS-Prover: Advancing Stepwise Theorem Proving by Multi-Perspective Search and Data Curation (NeurIPS 2025 · similarity 0.86)
- MUSTARD: Mastering Uniform Synthesis of Theorem and Proof Data (ICLR 2024 · similarity 0.85)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.85)
- Paths, Proofs, and Perfection: Developing a Human-Interpretable Proof System for Constrained Shortest Paths (AAAI 2024 · similarity 0.85)
- FaithSieve: Fine-Grained Evaluation of Math Proofs with Faithful Formal Evidence (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.
