LLM-gesteuerte Quantifizierte SMT-Lösung für Uninterpreted Functions

Quantifizierte Formeln mit uninterpretierten Funktionen (UFs) über nichtlineare reelle Arithmetik stellen SMT-Solver vor enorme Herausforderungen. Klassische Instanziationsmethoden fehlen die semantische Einsicht in UF-Beschränkungen und müssen daher in unbeschränkten Suchräumen ohne klare Orientierung suchen.

Mit dem neuen Framework AquaForte wird diese Lücke geschlossen: Große Sprachmodelle liefern semantisch fundierte Instanzkandidaten für Funktionsdefinitionen, die die gegebenen Constraints erfüllen. Dadurch wird der Suchraum drastisch verkleinert und die Komplexität für die Solver reduziert.

AquaForte arbeitet in drei Schritten: Zunächst werden die Formeln in unabhängige Constraint‑Gruppen zerlegt. Anschließend werden strukturierte Prompts an ein LLM gesendet, um mathematisches Denken zu extrahieren. Die daraus gewonnenen Instanzen werden dann adaptiv in die klassischen SMT‑Algorithmen integriert.

Die Korrektheit bleibt gewahrt: Wenn eine LLM‑gesteuerte Instanz SAT ergibt, löst sie das ursprüngliche Problem. Bei UNSAT‑Ergebnissen werden Ausschlussklauseln erzeugt, die den Suchraum weiter einschränken. Für Vollständigkeit greift AquaForte auf herkömmliche Solver zurück, die mit den erlernten Constraints erweitert werden.

In umfangreichen Tests auf SMT‑COMP‑Benchmarks konnte AquaForte zahlreiche Instanzen lösen, bei denen führende Solver wie Z3 und CVC5 aufgrund von Timeouts scheiterten – besonders bei erfüllbaren Formeln zeigte sich die hohe Effektivität.

Diese Arbeit demonstriert, dass große Sprachmodelle wertvolle mathematische Intuition für symbolische Problemlösung liefern können und eröffnet damit ein neues Paradigma im SMT‑Constraint‑Solving.