💻 computer science

GPU-Accelerated Search and Certification of Bounded Indistinguishability in Finite Kripke Semantics

Dieses Paper präsentiert ein GPU-beschleunigtes Framework, das endliche Kripke-Semantik als Bitmasken kodiert, um eine erschöpfende Evaluation modaler Formeln sowie eine Gegenmodell-Zertifizierung in massivem Maßstab durchzuführen, wodurch enge Schranken der Widerlegbarkeit aufzeigt, semantische Trugbilder synthetisiert und eine grafikgestützte semantische Exploration ermöglicht.

Ursprüngliche Autoren: Faruk Alpay, Baris Basaran

Veröffentlicht 2026-06-16

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Faruk Alpay, Baris Basaran

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen herauszufinden, ob zwei verschiedene Anweisungen (genannt „Formeln“) eigentlich dasselbe sind. In der Welt der Logik gibt es manchmal Anweisungen, die völlig unterschiedlich aussehen, aber in jeder kleinen Situation, die man sich vorstellen kann, exakt das gleiche Ergebnis liefern. Die große Frage lautet: Wie groß muss die Situation werden, bevor man schließlich einen Unterschied sieht?

Dieses Paper ist wie ein massives, Hochgeschwindigkeits-Experiment, das darauf ausgelegt ist, diese Frage mithilfe eines superschnellen Computerchips (einer GPU) zu beantworten. Hier ist die Aufschlüsselung dessen, was sie getan und gefunden haben, unter Verwendung einfacher Analogien.

1. Das Problem: Die „Winzige-Welt“-Falle

In der Logik gibt es eine Regel, die besagt, dass, wenn eine Anweisung falsch ist, man sie mit einem „Gegenbeispiel“ widerlegen kann – einem spezifischen Szenario, in dem sie scheitert. Normalerweise wissen wir, dass diese Szenarien existieren, aber die Mathematik besagt, dass sie unvorstellbar groß sein könnten (wie eine Stadt mit Milliarden von Häusern).

Die Forscher fragten: Brauchen wir wirklich eine ganze Stadt, um einen Fehler zu finden, oder können wir ihn in einem kleinen Dorf finden? Und noch wichtiger: Wenn zwei Anweisungen in einem Dorf identisch aussehen, wie groß muss die Stadt werden, bevor sie anfangen, sich unterschiedlich zu verhalten?

2. Das Werkzeug: Der „Bitmasken“-Super-Scanner

Um dies zu testen, bauten sie einen speziellen Scanner. Anstatt ein Szenario nach dem anderen zu prüfen (wie ein Mensch, der ein Buch liest), verwandelten sie die gesamte Welt der Möglichkeiten in Integer (Ganzzahlen).

Die Analogie: Stellen Sie sich eine Reihe von Lichtschaltern vor. Wenn ein Schalter auf „an“ steht, ist eine Bedingung wahr; wenn er auf „aus“ steht, ist sie falsch.
Der Trick: Sie packten tausende dieser Schalter in eine einzige Zahl. Dann nutzten sie die Grafikkarte des Computers (die GPU), um diese Schalter für Millionen verschiedener „Welten“ gleichzeitig umzulegen.
Das Ergebnis: Sie konnten 163 Billionen (1,63 × 10¹⁴) verschiedene Szenarien in nur 45 Minuten prüfen. Das ist, als würde man jede mögliche Anordnung eines Kartendecks in der Zeit prüfen, die man braucht, um eine Tasse Kaffee aufzubrühen.

3. Fundstelle 1: Kleine Fehler sind häufig

Sie testeten tausende einfache Logikformeln.

Die Erkenntnis: Die meisten Formeln, die „falsch“ (ungültig) sind, scheitern sehr schnell. Tatsächlich brauchen Sie für die überwältigende Mehrheit von ihnen nur eine Welt mit einem oder zwei „Zimmern“ (Welten), um zu beweisen, dass sie falsch sind.
Die Metapher: Die alten Mathematikbücher sagten: „Um zu beweisen, dass dies falsch ist, benötigen Sie vielleicht ein Herrenhaus mit 128 Zimmern.“ Die Forscher fanden heraus, dass man in der Praxis fast immer nur einen Kleiderschrank (1 oder 2 Zimmer) braucht, um den Fehler zu entdecken. Die Schätzung des „Herrenhauses“ war viel zu pessimistisch.

4. Fundstelle 2: Die „Semantische Mirage“ (Die trügerischen Zwillinge)

Der aufregendste Teil war das Finden von zwei Formeln, die ununterscheidbar sind, und zwar über eine lange Zeit hinweg.

Die Analogie: Stellen Sie sich zwei Zwillinge vor, Alpha-2 und Alpha-3. Wenn Sie sie in einen Raum mit 1, 2, 3, 4 oder sogar 5 Personen setzen, verhalten sie sich exakt gleich. Man kann sie nicht voneinander unterscheiden.
Der Durchbruch: Die Forscher fanden heraus, dass diese Zwillinge schließlich doch unterschiedlich handeln, aber erst, wenn man sie in einen Raum mit 6 Personen setzt.
Der Beweis: Sie haben nicht nur geraten, dass dies so ist. Sie bauten ein spezifisches 6-Personen-Zimmer (ein „Gegenmodell“) und bewiesen mathematisch, dass dies das kleinste mögliche Zimmer ist, in dem die Zwillinge sich trennen. Vor diesem Zeitpunkt wusste niemand genau, wo die Linie gezogen war.

5. Fundstelle 3: Die „Karte“ vs. die „Suchmaschine“

Sie versuchten auch, diese Logikformeln auf einer 2D-Karte (wie einem Streudiagramm) zu visualisieren, um zu sehen, ob Menschen die Unterschiede allein durch das Betrachten des Bildes erkennen könnten.

Das Ergebnis: Die Karte war chaotisch. Es war, als würde man versuchen, eine bestimmte Nadel in einem Heuhaufen zu finden, in dem 99 % der Nadeln übereinandergestapelt sind.
Die Schlussfolgerung: Die Karte ist gut, um Ideen zu generieren (Kandidaten zu finden), aber sie ist keine Entdeckungsmaschine. Man kann nicht einfach auf das Bild schauen und sagen: „Ah, da ist der Unterschied!“ Man braucht immer noch den superschnellen Computer, um die spezifischen Kandidaten zu prüfen, die die Karte vorschlägt. Der Computer ist der Richter; die Karte ist nur ein Vorschlagskasten.

6. Das „Zertifikat“-System

Um sicherzustellen, dass der superschnelle Computer keinen Fehler macht (da er so schnell ist, dass er eventuell einen Schritt überspringt), bauten sie ein separates, langsameres, aber sehr sorgfältiges „Schiedsrichter“-Programm.

Wie es funktioniert: Der schnelle Computer findet einen potenziellen Fehler und übergibt ein „Zertifikat“ (eine Notiz mit dem Inhalt: „Hier ist die Formel, hier ist die Welt, hier ist der Beweis“).
Die Prüfung: Der langsame Schiedsrichter liest das Zertifikat und sagt: „Ja, das ist korrekt.“
Warum es wichtig ist: Das bedeutet, dass die Ergebnisse zu 100 % vertrauenswürdig sind. Sie haben nicht nur eine schnelle Antwort erhalten, sondern eine verifizierte Antwort.

Zusammenfassung

In diesem Paper geht es darum, eine superschnelle Grafikkarte einzusetzen, um Logikregeln in winzigen Welten erschöpfend zu testen. Sie entdeckten, dass:

Die meisten Logikfehler in sehr kleinen Welten (1 oder 2 Zimmer) entdeckt werden.
Sie ein spezifisches Paar von Logikregeln fanden, die identisch aussehen, bis man eine 6-Zimmer-Welt erreicht, und sie bewiesen, dass dies exakt der Punkt ist, an dem sie sich trennen.
Visuelle Karten helfen dabei, zu finden, wo man suchen muss, aber man braucht immer noch den Computer, um zu bestätigen, was man sieht.

Es ist eine Geschichte darüber, wie man rohe Gewalt (das Prüfen von allem) mit kluger Mathematik kombiniert, um den exakten Moment zu finden, in dem zwei Dinge aufhören, dasselbe zu sein.

Technisches Resümee: GPU-beschleunigte Suche und Zertifizierung von beschränkter Ununterscheidbarkeit in endlichen Kripke-Semantiken

Problemstellung
Die Arbeit adressiert zwei grundlegende Fragen der Modallogik und der endlichen Modelltheorie, die zwar entscheidbar, aber rechenintensiv sind:

Minimale Gegenmodellgröße: Wie groß sind die minimalen Gegenmodelle für ungültige Modallogik-Formeln in der Praxis im Vergleich zu den standardmäßigen exponentiellen Schranken, die durch die Endliche Modell-Eigenschaft (FMP) und Filtration bereitgestellt werden?
Beschränkte Ununterscheidbarkeit: Wie groß muss ein endliches Modell sein, bevor es in der Lage ist, zwei Formeln zu unterscheiden, die auf allen kleineren Modellen äquivalent erscheinen? Die Autoren definieren ein Paar von Formeln als k-unununterscheidbar, wenn sie auf allen Frames der Größe $\le k$ übereinstimmen, sich aber auf einem Frame der Größe $k+1$ unterscheiden.

Während standardmäßige Techniken wie BDD-basiertes symbolisches Model Checking große Zustandsräume für einzelne Formeln komprimieren, zielt diese Arbeit auf das entgegengesetzte Regime ab: eine vollständige Volkszählung vieler Formeln gegen viele kleine Frames gleichzeitig.

Methodik
Die Autoren nutzen die bitweise Natur der endlichen Kripke-Evaluation, um massive Parallelisierung auf GPUs zu ermöglichen.

Bitmasken-Kodierung: Welten werden als Ganzzahlen kodiert, und Valuierungen als Bitmasken. Boolesche Junktoren bilden auf bitweise Operationen ab, während modale Operatoren ( $\Box$ und $\Diamond$ ) auf Teilmengen- und Schnittmengenprüfungen von Nachfolger-Masken reduziert werden (Lemma 1). Dies eliminiert die Notwendigkeit, den $(frame \times valuation)$ Wahrheitstensor zu materialisieren.
Gefügter CUDA-Kernel: Ein einzelner Kernel evaluiert einen ganzen Korpus von Formeln gegen alle Frames einer festen Größe in einem Durchgang. Threads sind den Frames zugewiesen und iterieren über die Valuierungen mittels Schleifenindizes (Vermeidung von Valuierungs-Arrays) und reduzieren die Ergebnisse mittels Shared Memory, um die atomare Kontention zu minimieren.
Verifikationsarchitektur: Das System verwendet ein „Fast Search, Slow Check“-Paradigma. Die GPU führt die erschöpfende Enumeration durch, während ein separater, transparenter rekursiver CPU-Evaluator (unabhängig von der Bitmasken-Engine) jedes gemeldete Gegenmodell verifiziert. Dies stellt sicher, dass die Ergebnisse unabhängig von den Implementierungsdetails des Beschleunigers vertrauenswürdig sind.
Aktive Synthese: Über die passive Enumeration hinaus nutzen die Autoren ein aktives Syntheseprotokoll, um Kandidat-Formelpaare (z. B. $(\Box\Diamond)^m\top$ ) zu generieren und nach „semantischen Trugbildern“ (unununterscheidbaren Paaren) unter Verwendung von adversarieller Frame-Generierung (Erdős–Rényi, SCC-Engpässe usw.) sowie SAT-Solvern für Minimalitätsbeweise zu suchen.
Repräsentationsgesteuerte Abfrage: Die Autoren konstruieren einen „semantischen Atlas“ (eine Dichtematrix von Fehlermustern) und evaluieren verschiedene Techniken zur Dimensionsreduktion (PCA, UMAP, Spektral), um Kandidaten abzurufen. Entscheidend ist, dass die Visualisierungen als Schnittstellen zur Kandidatengenerierung betrachtet werden, nicht als eigenständige Entdeckungswerkzeuge; jeder Kandidat wird mittels erschöpfender Suche neu verifiziert.

Wesentliche Beiträge und Ergebnisse

Korrektheit und Komplexität: Die Autoren liefern einen Korrektheitsbeweis für den Bitmasken-Evaluator (Theorem 1) und eine Komplexitätsanalyse, die zeigt, dass der Ansatz vermeidet, den Wahrheitstensor zu speichern (Proposition 1). Alle 20.990 generierten Zertifikate wurden unabhängig verifiziert.
Kleine minimale Gegenmodelle: In einem Korpus von 5.624 konstantfreien Formeln (bis zu 7 Knoten, 2 Variablen) ergab die Studie, dass minimale Gegenmodelle überraschend klein sind.
- Jede widerlegbare Formel in der Logik K wird auf höchstens 2 Welten widerlegt (Proposition 3).
- Die Standard-Filtrationsschranke ( $2^{|Sub(\phi)|}$ ) ist empirisch zu locker; für 7-Knoten-Formeln legt die Schranke bis zu 128 Welten nahe, aber die maximal beobachtete Anzahl war 2 (Korollar 1).
Synthese von beschränkter Ununterscheidbarkeit: Die Autoren synthetisierten erfolgreich ein zertifiziertes 5-unununterscheidbares Paar ( $\alpha_2 = (\Box\Diamond)^2\top$ $α_{2} = (□◊)^{2} ⊤$ und $\alpha_3 = (\Box\Diamond)^3\top$ $α_{3} = (□◊)^{3} ⊤$ ). Diese Formeln stimmen auf allen Frames der Größe $\le 5$ $\leq 5$ überein, werden aber durch einen spezifischen 6-Welten-Pfad getrennt (Proposition 5).
- Diese Trennung wurde sowohl durch erschöpfende GPU-Enumeration als auch durch symbolische SAT-Beweise bestätigt (Tabelle 3).
- Die adversarielle Frame-Synthese produzierte 90 verifizierte Separationen, von denen 78 Nicht-Template-Typen waren (d. h. keine einfachen Pfade oder Zyklen).
Systemleistung:
- Die gefügte H100-Implementierung erreichte eine dauerhafte Rate von 60,2 Milliarden Evaluationen pro Sekunde ( $1,63 \times 10^{14}$ Gesamtevaluationen in 45 Minuten).
- Sie war 47,1-mal schneller als ein bitparalleler OpenMP-CPU-Ansatz und 7,06-mal schneller als eine explizite AVX-512-CPU-Baseline bei vergleichbaren Arbeitslasten.
- Die Hardware-Kalibrierung erreichte 18,87 Source-Level uint32 TOPS mit 98,3 % mittlerer NVML-Auslastung.
Repräsentation und Abfrage:
- Bei einer Abrichtaufgabe über 5,4 Millionen Kandidatenpaare schnitten Roh-Features in hoher Dimension am besten bei engen Nachbarschaftsbudgets ( $k=16$ ) ab, während ein 2D-PCA-Atlas bei breiteren Budgets ( $k=1024$ ) am besten abschnitt.
- Die Autoren betonen jedoch, dass 2D-Visualisierungen unter extremer Überfüllung leiden (98,6 % der Punkte teilen sich einen Bin bei einer Skala von 100k) und keine eigenständigen Entdeckungswerkzeuge sind. Die Pipeline beruht auf repräsentationsgesteuerter Proponierung gefolgt von erschöpfender Verifikation.
Wiederherstellung der Korrespondenz: Die Engine konnte die First-Order-Frame-Bedingungen für alle Sahlqvist-Axiome (T, D, 4, 5, B, etc.) wiederherstellen und korrekt identifizierte, dass das McKinsey-Axiom im getesteten Korpus keine First-Order-Korrespondenz besitzt, was das System gegen etablierte Theorie validiert.

Bedeutung und Umfang
Die Arbeit beansprucht ihre Bedeutung nicht als ein neues Entscheidungsverfahren für die allgemeine Modallogik (welches weiterhin PSPACE-vollständig bleibt), sondern als ein reproduzierbares Protokoll zur Untersuchung des „Small-Model-Regimes“ und der Grenzen der Ununterscheidbarkeit.

Bescheidenheit der Ansprüche: Die Autoren geben explizit an, dass ihre Ergebnisse begrenzt sind. Die Volkszählung entscheidet die Gültigkeit nur für Formeln, bei denen die FMP-Schranke innerhalb der untersuchten Größe liegt (bis zu 5 Welten). Behauptungen über Formeln, die über diesen Bereich hinaus überleben, sind Schätzungen oder beschränkte Überlebende, keine Theoreme.
Entdeckung vs. Verifikation: Das Papier unterscheidet zwischen dem Generieren von Kandidaten (via Synthese oder visuellen Atlanten) und dem Zertifizieren derselben. Die „Entdeckung“ des 5-unununterscheidbaren Paares ist ein Resultat aktiver Synthese und erschöpfender Verifikation, nicht bloßer visueller Inspektion.
Komplementarität: Die Arbeit wird als ergänzend zum symbolischen Model Checking (BDDs/SAT) präsentiert. Während symbolische Methoden einen großen Zustandsraum komprimieren, durchkämmt dieser Ansatz explizit viele kleine Modelle gegen viele Formeln – ein Regime, in dem symbolische Methoden möglicherweise nicht optimal sind.

Zusammenfassend zeigt die Arbeit, dass GPU-beschleunigte bitweise Evaluation eine erschöpfende Volkszählung kleiner Kripke-Modelle ermöglicht, was offenlegt, dass minimale Gegenmodelle oft viel kleiner sind, als theoretische Schranken vermuten lassen, und bietet einen rigorosen Rahmen für die Synthese und Zertifizierung beschränkter Ununterscheidbarkeit in der Modallogik.