💻 computer science

Solving QBF with Counterexample Guided Refinement

Dit artikel introduceert twee nieuwe Counterexample-Guided Abstraction Refinement (CEGAR)-benaderingen voor het oplossen van Quantified Boolean Formula (QBF)—een recursief door CEGAR gedreven algoritme en een DPLL-gebaseerde leeroptimalisatie—die beide een verbeterde prestatie vertonen op specifieke probleemfamilies vergeleken met bestaande solvers.

Oorspronkelijke auteurs: Mikoláš Janota, William Klieber, Joao Marques-Silva, Edmund Clarke

Gepubliceerd 2026-08-17

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mikoláš Janota, William Klieber, Joao Marques-Silva, Edmund Clarke

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een detective bent die een enorme, gelaagde mysteries probeert op te lossen, waarbij de aanwijzingen verborgen liggen in een gigantische, verstrengelde bal van touw. Dit is niet zomaar een mysterie; het is een spel gespeeld tussen twee onzichtbare tegenstanders: één die wil bewijzen dat een stelling waar is, en een ander die wanhopig probeert te bewijzen dat deze onwaar is. In de wereld van de informatica wordt dit een Quantified Boolean Formula (QBF) genoemd. Denk aan deze puzzels als een super-opgeladen versie van een logische puzzel waarbij je moet uitzoeken of er een manier is om te winnen, ongeacht hoe je tegenstander speelt. Deze puzzels zijn ongelooflijk moeilijk; ze zijn zo moeilijk dat ze alles aansturen, van het controleren of de software van een zelfrijdende auto veilig is tot het plannen van complexe robotmissies. Decennialang hebben computers geprobeerd deze problemen op te lossen met een methode genaamd DPLL, wat is als een detective die elke deur in een landhuis één voor één probeert te controleren totdat hij de uitgang vindt. Het werkt, maar voor de grootste, meest verstrengelde mysteries raakt de detective verdwaald in de enorme hoeveelheid deuren en raakt hij zijn tijd en energie kwijt voordat hij het antwoord heeft gevonden.

Maak kennis met een nieuwe strategie genaamd CEGAR, wat staat voor Counterexample-Guided Abstraction Refinement. Als DPLL een detective is die elke deur controleert, dan is CEGAR een detective die begint met een ruwe schets van het landhuis. Ze raden een pad, en als hun tegenstander zegt: "Nee, je kunt daar niet heen omdat er hier een specifieke valstrik zit," geeft de detective niet op. In plaats daarvan gebruiken ze die specifieke valstrik (het "tegenvoorbeeld") om de schets bij te werken, waardoor deze nauwkeuriger wordt. Ze herhalen dit proces — raden, gecorrigeerd worden, de schets verfijnen — totdat de schets perfect genoeg is om het mysterie op te lossen zonder ooit elke deur te hoeven controleren.

Deze paper introduceert twee slimme manieren om deze "raad-en-verfijn"-truc toe te passen om deze logische puzzels sneller en slimmer op te lossen dan voorheen. De auteurs, een team van onderzoekers uit Portugal, Ierland en de VS, stellen twee verschillende manieren voor om deze CEGAR-magie naar de wereld van QBF-solvers te brengen. De eerste benadering is een gloednieuwe solver die ze RAReQS noemden. In plaats van te proberen de hele puzzel in één keer op te lossen of de hele bal van touw uit te rollen tot een enorme, onhandelbare bende (een probleem dat bekend staat als "memory blowup" en oudere methoden teistert), speelt RAReQS het spel in lagen. Het begint met het doen van een eenvoudige gok over de eerste laag variabelen. Vervolgens vraagt het een helper (een SAT-solver) of deze gok werkt. Als de helper een fout vindt — een specifieke manier waarop de tegenstander tegen deze gok zou kunnen winnen — gebruikt RAReQS deze fout om de regels voor de volgende gok aan te scherpen. Het is als het spelen van een videogame waarbij je niet de hele kaart hoeft te zien; je moet alleen weten waar de muren staan zodat je niet tegen ze aan loopt. Door alleen de delen van de puzzel uit te breiden die absoluut noodzakelijk zijn, vermijdt RAReQS de geheugenexplosie die andere solvers doet crashen.

De tweede benadering is meer een soort software-upgrade. De auteurs namen een bestaande, populaire solver genaamd GhostQ, die de traditionele "elke deur controleren" DPLL-methode gebruikt, en gaven deze een nieuw leermiddel. Ze leerden GhostQ om dezelfde "raad-en-verfijn"-logica te gebruiken. Wanneer GhostQ een pad vindt dat goed lijkt maar een doodlopend spoor blijkt te zijn, in plaats van alleen maar terug te keren (backtracking), leert het een krachtige les: "Neem dit pad nooit meer." Deze nieuwe leermethode stelt de solver in staat om de zoekruimte veel agressiever te snoeien, waardoor enorme stukken onmogelijke scenario's worden uitgesneden die de oude methode de tijd zouden laten verspillen.

Toen het team deze nieuwe methoden testte op een enorme collectie real-world logische puzzels (uit de QBF-LIB benchmark suite), waren de resultaten indrukwekkend. Hun nieuwe solver, RAReQS, loste aanzienlijk meer puzzels op dan de concurrentie — ongeveer 33% meer dan de op één na beste solver. Het blonk met name uit in families van problemen gerelateerd aan formele verificatie (controleren of hardware-ontwerpen correct zijn) en planning (bepalen hoe robots moeten bewegen). Voor specifieke soorten puzzels, zoals "incrementer-encoder" en "trafficlight-controller", loste RAReQS bijna alle instanties op, terwijl andere solvers worstelden of volledig faalden. De geüpgradede GhostQ liet ook verbeteringen zien en loste meer puzzels op dan de niet-geüpgradede versie, hoewel het soms een kleine prijs betaalde in snelheid of geheugengebruik.

De paper maakt duidelijk dat hoewel deze methoden krachtig zijn, ze geen toverstaf zijn die alles direct oplost. De auteurs merken op dat als een puzzel wel een volledige expansie van de draad vereist om op te lossen, RAReQS uiteindelijk hetzelfde werk zal verrichten als de oudere methoden, maar dan met een beetje extra overhead voor de verfijningsstappen. Echter, voor het overgrote deel van de praktische problemen die zij testten, was de "gedeeltelijke expansie"-strategie een game-changer. Het bewees dat je niet het hele plaatje hoeft te zien om het mysterie op te lossen; je moet alleen je begrip van de onderdelen die ertoe doen verfijnen, door de fouten die je maakt te gebruiken om je naar de waarheid te leiden. Dit opent twee opwindende nieuwe paden voor de toekomst: het bouwen van solvers die volledig vertrouwen op deze verfijningslus, en het leren van de klassieke solvers om op een geheel nieuwe manier van hun tegenvoorbeelden te leren.

Technische Samenvatting: Het oplossen van QBF met Counterexample-Guided Refinement

Probleemstelling
Quantified Boolean Formulas (QBF's) breiden het SAT-probleem uit naar PSPACE-volledige problemen, met toepassingen in formele verificatie en planning. Hoewel de DPLL-procedure domineert bij niet-random SAT-solving, is deze onvoldoende gebleken als universele oplossing voor QBF. Bestaande QBF-solvers vallen over het algemeen uiteen in twee categorieën: DPLL-gebaseerde benaderingen en expansie-gebaseerde benaderingen. Expansie-gebaseerde solvers (bijv. Quantor, Nenofex) elimineren kwantoren door de formule te expanderen naar een propositionele formule, maar dit leidt vaak tot een geheugenexplosie naarmate de omvang van de formule snel groeit. DPLL-gebaseerde solvers worstelen met de complexiteit van de zoekruimte in QBF. Dit artikel adresseert de behoefte aan efficiëntere QBF-oplossingstechnieken die de geheugengebruiksproblemen kunnen beperken terwijl de zoekruimte effectief wordt afgesneden.

Methodologie
De auteurs stellen twee verschillende benaderingen voor die gebruikmaken van het Counterexample-Guided Abstraction Refinement (CEGAR) paradigma:

RAReQS (Recursive CEGAR-based Algorithm):
- Kernconcept: RAReQS is een recursief algoritme dat QBF-solving behandelt als een spel tussen een universele speler en een existentiële speler. In plaats van de formule volledig te expanderen, bouwt het een gedeeltelijke expansie (abstractie) die wordt gedreven door tegenvoorbeelden (counterexamples).
- Mechanisme: Het algoritme probeert een "winnende zet" (een toewijzing aan een blok variabelen dat de formule bevredigt voor de existentiële speler of het falsifieert voor de universele speler) te vinden voor een abstractie van de formule.
  - Het begint met een lege verzameling tegenvoorbeelden ( $\omega = \emptyset$ ), wat een triviale abstractie vertegenwoordigt.
  - In elke iteratie lost het de huidige abstractie op om een kandidaat-winnende zet te vinden.
  - Vervolgens verifieert het of deze kandidaat een winnende zet is voor de oorspronkelijke formule. Deze verificatie omvat het oplossen van een sub-QBF.
  - Als de kandidaat de verificatie faalt, wordt een tegenvoorbeeld (een winnende zet voor de tegenstander) gegenereerd.
  - De abstractie wordt verfijnd door dit tegenvoorbeeld toe te voegen aan de verzameling $\omega$ , waardoor de abstractie effectief wordt versterkt om de gefaalde kandidaat uit te sluiten.
- Optimalisatie (Multi-games): Om het hoge geheugengebruik aan te pakken dat wordt veroorzaakt door de recursieve aard van het algoritme (waarbij de omvang van de abstractie exponentieel kan groeien met de recursiediepte), introduceren de auteurs het concept van "multi-games". Een multi-game stelt de solver in staat om meerdere subformules gelijktijdig te verwerken. De abstractie wordt onderhouden als een verzameling subgames, en verfijning voegt nieuwe subgames toe in plaats van blindelings de formulegrootte te vergroten. Dit stelt de solver in staat te termineren voordat een volledige expansie vereist is.
- Implementatie: Een prototype werd in C++ geïmplementeerd met de MiniSat 2.2 SAT-solver, met ondersteuning voor het QDIMACS-formaat. Het maakt gebruik van standaard QBF-preprocessing technieken zoals unit propagation en pure literal rules.
CEGAR als een Leermethode in DPLL:
- Kernconcept: Deze benadering integreert CEGAR als een aanvullend leermechanisme binnen een bestaande DPLL-gebaseerde solver (specifiek GhostQ).
- Mechanisme: Wanneer de DPLL-solver waarden toeweest aan variabelen zodanig dat de existentiële speler wint (de formule evalueert als waar), wordt de toewijzing gesplitst in een kandidaat-deel ( $\pi_{cand}$ ) en een tegenvoorbeeld-deel ( $\pi_{cex}$ ).
- Leren: De solver leert hiervan door de invoerformule aan te passen. Als het laatste beslissingslettertype eigendom was van de winnende speler, vervangt de solver de relevante gekwantificeerde subformule door een disjunctie (voor existentieel) of conjunctie (voor universeel) die de tegenvoorbeeld-toewijzing betreft. Specifiek wordt $\exists X. \Phi$ vervangen door $(\exists X. \Phi) \lor \Phi[\pi_{cex}]$ , wat ervoor zorgt dat de specifieke tegenvoorbeeld-toewijzing in toekomstige zoekopdrachten wordt vermeden.
- Trade-off: Deze techniek maakt agressiever afsnijden van de zoekruimte mogelijk dan standaard clausule-leren, maar brengt een hoger geheugengebruik met zich mee.

Belangrijkste Bijdragen

RAReQS Algoritme: De ontwikkeling van een nieuwe, recursieve, CEGAR-gestuurde QBF-solver die de geheugenexplosie voorkomt die inherent is aan traditionele expansie-gebaseerde solvers door zorgvuldige, tegenvoorbeeld-gestuurde gedeeltelijke expansies uit te voeren.
Multi-game Abstractie: De introductie van het multi-game concept om de complexiteit en het geheugengebruik van recursieve CEGAR te beheren, waardoor de solver formules met een willekeurig aantal kwantorniveaus efficiënt kan verwerken.
CEGAR Leren voor DPLL: De voorstel en implementatie van een nieuwe leermethode voor DPLL-gebaseerde QBF-solvers die tegenvoorbeelden gebruikt om het afsnijden van de zoekruimte te versterken.
Empirische Validatie: Uitgebreide experimentele evaluatie op de QBF-LIB benchmark suite, die aantoont dat CEGAR-gebaseerde technieken effectief zijn voor een breed scala aan probleemfamilies.

Experimentele Resultaten
De auteurs evalueerden de prototypes op 4.669 instanties van de QBF-LIB, met de focus op families uit formele verificatie en planning.

RAReQS Prestaties: RAReQS presteerde beter dan bestaande solvers (QuBE7.2, Quantor, Nenofex, GhostQ) op een aanzienlijk aantal families. Het loste ongeveer 33% meer instanties op dan de op één na beste solver (QuBE7.2). Opvallend genoeg loste RAReQS alle instanties op voor families zoals blackbox-01X-QBF en trafficlight-controller, en loste bijna alle instanties op voor incrementer-encoder en RobotsD2.
Geheugenefficiëntie: Van de 801 afgebroken runs waren er slechts 50 te wijten aan geheugentekort, wat aangeeft dat RAReQS succesvol de geheugenexplosie-problemen van expansie-gebaseerde solvers mitigeert.
DPLL Leren: De integratie van CEGAR-leren in GhostQ (GhostQ-CEGAR) verbeterde over het algemeen de prestaties, met name op families zoals irqlkeapclte (waar het de enige solver was die oplossingen vond) en incrementer-encoder. Echter, in sommige families verslechterde de extra geheugenoverhead de prestaties licht.

Betekenis en Claims
Het artikel claimt twee veelbelovende wegen te hebben geopend in QBF-solving:

CEGAR-gestuurde solvers als alternatief: RAReQS demonstreert dat een CEGAR-gestuurde benadering een levensvatbaar alternatief kan dienen voor bestaande DPLL- en volledige expansiemethoden, met name door de geheugenexplosie van expansie-gebaseerde solvers te vermijden terwijl de correctheid en volledigheid behouden blijven.
Nieuw leren in DPLL: Het artikel stelt vast dat CEGAR effectief kan worden ingezet als een aanvullende leermethode binnen DPLL-gebaseerde QBF-solvers, wat een krachtiger mechanisme biedt voor het afsnijden van de zoekruimte dan standaard clausule-leren, zij het met een geheugenkost.

De auteurs concluderen dat hoewel RAReQS overeenkomsten vertoont met expansie-gebaseerde solvers, de stap-voor-stap, tegenvoorbeeld-gestuurde expansie het mogelijk maakt om vroegtijdig te stoppen als er geen winnende zet wordt gevonden in de gedeeltelijke expansie, een cruciaal voordeel voor grote formules. Ze merken bescheiden op dat als een volledige expansie uiteindelijk toch vereist is, RAReQS dezelfde expansie uitvoert als traditionele solvers, maar dan met de overhead van tussenliggende tests. Toekomstig werk omvat het verfijnen van het DPLL-leren om de snelheidspenaliteiten te verminderen en het integreren van preprocessing-technieken van andere solvers in RAReQS.

Meer zoals dit