Research map / Detection and segmentation / Open-set and few-shot detection
INFORMEDQX: Informed Conflict Detection for Over-Constrained Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes INFORMEDQX, a reuse-aware variant of QUICKXPLAIN that uses previously found conflict sets (stored in a BDD) to find preferred minimal conflicts in over-constrained CSP configuration problems faster.
Problem
Conflict detection for preferred minimal conflict sets in constraint-based configuration is repeatedly recomputed for the same or similar constraint sets, and existing algorithms like QUICKXPLAIN scale poorly on large knowledge bases.
Approach
Reuse a set of predetermined minimal conflicts (indexed in a binary decision diagram) to determine the currently preferred conflict, then prune the user-requirement set and invoke QUICKXPLAIN only when a more preferred conflict may still exist.
Key results
- INFORMEDQX reduced consistency checks versus QUICKXPLAIN in cases where reusable conflicts exist (e.g., |CS|=8: 0 checks and 9.07 s vs. 15.92 s for QUICKXPLAIN when Ncp equals the preferred conflict).
- In the worked smartwatch example, INFORMEDQX needed 6 consistency checks versus 9 for QUICKXPLAIN.
- When no conflicts of CR are in the reuse set, INFORMEDQX was slightly slower than QUICKXPLAIN (e.g., 3.64 s vs. 3.58 s for |CS|=2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use INFORMEDQX when no known conflict matches the requirements | INFORMEDQX · Linux-2.6.33.3, |CS|=2 | runtime (seconds): 3.58 -> 3.64 | Hurt |
| Use INFORMEDQX when no known conflict matches the requirements | INFORMEDQX · Linux-2.6.33.3, |CS|=4 | runtime (seconds): 7.47 -> 7.59 | Hurt |
| Use INFORMEDQX when no known conflict matches the requirements | INFORMEDQX · Linux-2.6.33.3, |CS|=8 | runtime (seconds): 15.92 -> 18.91 | Hurt |
| Reuse known conflicts and prune constraints when the known preferred conflict is not the answer | INFORMEDQX · Linux-2.6.33.3, |CS|=2 | runtime (seconds): 3.58 -> 2.57 | Helped |
| Reuse known conflicts and prune constraints when the known preferred conflict is not the answer | INFORMEDQX · Linux-2.6.33.3, |CS|=4 | runtime (seconds): 7.47 -> 6.21 | Helped |
| Reuse known conflicts and prune constraints when the known preferred conflict is not the answer | INFORMEDQX · Linux-2.6.33.3, |CS|=8 | runtime (seconds): 15.92 -> 12.60 | Helped |
| Reuse the known preferred conflict without activating QUICKXPLAIN | INFORMEDQX · Linux-2.6.33.3, |CS|=2 | runtime (seconds): 3.58 -> 1.97 | Helped |
| Reuse the known preferred conflict without activating QUICKXPLAIN | INFORMEDQX · Linux-2.6.33.3, |CS|=4 | runtime (seconds): 7.47 -> 4.20 | Helped |
| Reuse the known preferred conflict without activating QUICKXPLAIN | INFORMEDQX · Linux-2.6.33.3, |CS|=8 | runtime (seconds): 15.92 -> 9.07 | Helped |
Surprising findings
- When no reusable conflict matches the requirements, INFORMEDQX is slightly slower than QUICKXPLAIN due to the overhead of BDD queries.
Limitations
- Evaluated on a single configuration knowledge base (Linux) with 136 synthetic minimal conflicts.
- Requires an offline BDD construction over predetermined conflicts and is only beneficial when reusable conflicts match the requirements.
Experimental setup
Datasets: Linux-2.6.33.3 configuration knowledge base (Diverso Lab benchmark)
Benchmarks: Linux-2.6.33.3 configuration knowledge base
Metrics: solver calls reused conflict sets average runtime (s)
Baselines: QUICKXPLAIN
Builds on: QUICKXPLAIN binary decision diagram compression of conflicts
Closest papers by meaning
- Germane Conflicts: Desirable Properties for Localising Inconsistency (AAAI 2025 · similarity 0.82)
- $\texttt{ConflictBank}$: A Benchmark for Evaluating the Influence of Knowledge Conflicts in LLMs (NeurIPS 2024 · similarity 0.82)
- Automated Creation of Reusable and Diverse Toolsets for Enhancing LLM Reasoning (AAAI 2025 · similarity 0.81)
- RepoMirage: Probing Repository Context Reasoning in Code Agents with Perturbations (NeurIPS 2026 · similarity 0.81)
- Multi-SWE-bench: A Multilingual Benchmark for Issue Resolving (NeurIPS 2025 · similarity 0.81)
- Adaptive Chameleon or Stubborn Sloth: Revealing the Behavior of Large Language Models in Knowledge Conflicts (ICLR 2024 · similarity 0.81)
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.