💻 computer science

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

This paper presents a GPU-accelerated framework that encodes finite Kripke semantics as bitmasks to perform exhaustive modal formula evaluation and countermodel certification at massive scale, revealing tight bounds on refutability, synthesizing semantic mirages, and enabling graphics-supported semantic exploration.

Original authors: Faruk Alpay, Baris Basaran

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Faruk Alpay, Baris Basaran

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to figure out if two different sets of instructions (called "formulas") are actually the same thing. In the world of logic, sometimes two instructions look completely different but give the exact same result in every small situation you can think of. The big question is: How big does the situation have to get before you finally see a difference?

This paper is like a massive, high-speed experiment designed to answer that question using a super-fast computer chip (a GPU). Here is the breakdown of what they did and found, using simple analogies.

1. The Problem: The "Tiny World" Trap

In logic, there's a rule that says if an instruction is wrong, you can prove it wrong with a "counterexample"—a specific scenario where it fails. Usually, we know these scenarios exist, but the math says they could be impossibly huge (like a city with billions of houses).

The researchers asked: Do we really need a city to find a mistake, or can we find it in a small village? And more importantly: If two instructions look identical in a village, how big does the town need to be before they start acting differently?

2. The Tool: The "Bitmask" Super-Scanner

To test this, they built a special scanner. Instead of checking one scenario at a time (like a human reading a book), they turned the entire world of possibilities into integers (numbers).

The Analogy: Imagine a row of light switches. If a switch is "on," a condition is true; if "off," it's false.
The Trick: They packed thousands of these switches into a single number. Then, they used the computer's graphics card (the GPU) to flip these switches for millions of different "worlds" simultaneously.
The Result: They could check 163 trillion (1.63 × 10¹⁴) different scenarios in just 45 minutes. That's like checking every possible arrangement of a deck of cards in the time it takes to brew a cup of coffee.

3. Finding 1: Small Mistakes are Common

They tested thousands of simple logic formulas.

The Finding: Most formulas that are "wrong" (invalid) fail very quickly. In fact, for the vast majority of them, you only need a world with one or two "rooms" (worlds) to prove they are wrong.
The Metaphor: The old math books said, "To prove this is wrong, you might need a mansion with 128 rooms." The researchers found that in practice, you almost always only need a closet (1 or 2 rooms) to catch the error. The "mansion" estimate was way too pessimistic.

4. Finding 2: The "Semantic Mirage" (The Tricky Twins)

The most exciting part was finding two formulas that are indistinguishable for a long time.

The Analogy: Imagine two twins, Alpha-2 and Alpha-3. If you put them in a room with 1, 2, 3, 4, or even 5 people, they act exactly the same. You can't tell them apart.
The Breakthrough: The researchers found that these twins do finally act differently, but only when you put them in a room with 6 people.
The Proof: They didn't just guess this. They built a specific 6-person room (a "countermodel") and proved mathematically that this is the smallest possible room where the twins split. Before this, no one knew exactly where the line was drawn.

5. Finding 3: The "Map" vs. The "Search Engine"

They also tried to visualize these logic formulas on a 2D map (like a scatter plot) to see if humans could spot the differences just by looking at the picture.

The Result: The map was messy. It was like trying to find a specific needle in a haystack where 99% of the needles were piled on top of each other.
The Conclusion: The map is good for generating ideas (finding candidates), but it is not a discovery engine. You can't just look at the picture and say, "Ah, there's the difference!" You still need the super-fast computer to check the specific candidates the map suggests. The computer is the judge; the map is just a suggestion box.

6. The "Certificate" System

To make sure the super-fast computer didn't make a mistake (since it's so fast it might skip a step), they built a separate, slower, but very careful "referee" program.

How it works: The fast computer finds a potential error and hands it a "certificate" (a note saying: "Here is the formula, here is the world, here is the proof").
The Check: The slow referee reads the certificate and says, "Yes, this is correct."
Why it matters: This means the results are 100% trustworthy. They didn't just get a fast answer; they got a verified answer.

Summary

The paper is about using a super-fast graphics card to exhaustively test logic rules in tiny worlds. They discovered that:

Most logic errors are caught in very small worlds (1 or 2 rooms).
They found a specific pair of logic rules that look identical until you reach a 6-room world, and they proved this is the exact point where they split.
Visual maps help you find where to look, but you still need the computer to confirm what you see.

It's a story about using brute force (checking everything) combined with smart math to find the exact moment two things stop being the same.

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

Problem Statement
The paper addresses two fundamental questions regarding modal logic and finite model theory that are decidable but computationally expensive:

Minimal Countermodel Size: For invalid modal formulas, how large are the minimal countermodels in practice compared to the standard exponential bounds provided by the Finite Model Property (FMP) and filtration?
Bounded Indistinguishability: How large must a finite model be before it can distinguish between two formulas that appear equivalent on all smaller models? The authors define a pair of formulas as k-indistinguishable if they agree on all frames of size $\le k$ but diverge on a frame of size $k+1$ .

While standard techniques like BDD-based symbolic model checking compress large state spaces for single formulas, this work targets the opposite regime: a complete census of many formulas against many small frames simultaneously.

Methodology
The authors leverage the bitwise nature of finite Kripke evaluation to enable massive parallelism on GPUs.

Bitmask Encoding: Worlds are encoded as integers, and valuations as bitmasks. Boolean connectives map to bitwise operations, while modal operators ( $\Box$ and $\Diamond$ ) are reduced to containment and intersection tests on successor masks (Lemma 1). This eliminates the need to materialize the $(frame \times valuation)$ truth tensor.
Fused CUDA Kernel: A single kernel evaluates a whole corpus of formulas against all frames of a fixed size in one pass. Threads are assigned to frames, iterating through valuations via loop indices (avoiding valuation arrays) and reducing results using shared memory to minimize atomic contention.
Verification Architecture: The system employs a "fast search, slow check" paradigm. The GPU performs the exhaustive enumeration, while a separate, transparent recursive CPU evaluator (independent of the bitmask engine) verifies every reported countermodel. This ensures that the results are trustworthy regardless of the accelerator's implementation details.
Active Synthesis: Beyond passive enumeration, the authors use an active synthesis protocol to generate candidate formula pairs (e.g., $(\Box\Diamond)^m\top$ ) and search for "semantic mirages" (indistinguishable pairs) using adversarial frame generation (Erdős–Rényi, SCC bottlenecks, etc.) and SAT solvers for minimality proofs.
Representation-Guided Retrieval: The paper constructs a "semantic atlas" (a density matrix of failure profiles) and evaluates various dimensionality reduction techniques (PCA, UMAP, spectral) for candidate retrieval. Crucially, the visualizations are treated as candidate-generation interfaces, not standalone discovery engines; every candidate is re-verified via exhaustive search.

Key Contributions and Results

Correctness and Complexity: The authors provide a correctness proof for the bitmask evaluator (Theorem 1) and a complexity analysis showing that the approach avoids storing the truth tensor (Proposition 1). All 20,990 generated certificates were independently verified.
Small Minimal Countermodels: In a corpus of 5,624 constant-free formulas (up to 7 nodes, 2 variables), the study found that minimal countermodels are surprisingly small.
- Every refutable formula in the logic K is refuted on at most 2 worlds (Proposition 3).
- The standard filtration bound ( $2^{|Sub(\phi)|}$ ) is empirically loose; for 7-node formulas, the bound suggests up to 128 worlds, but the maximum observed was 2 (Corollary 1).
Synthesis of Bounded Indistinguishability: The authors successfully synthesized a certified 5-indistinguishable pair ( $\alpha_2 = (\Box\Diamond)^2\top$ $α_{2} = (□◊)^{2} ⊤$ and $\alpha_3 = (\Box\Diamond)^3\top$ $α_{3} = (□◊)^{3} ⊤$ ). These formulas agree on all frames of size $\le 5$ $\leq 5$ but are separated by a specific 6-world path (Proposition 5).
- This separation was confirmed by both exhaustive GPU enumeration and symbolic SAT proofs (Table 3).
- Adversarial frame synthesis produced 90 verified separations, 78 of which were non-template (i.e., not simple paths or cycles).
System Performance:
- The fused H100 implementation achieved a sustained rate of 60.2 billion evaluations per second (1.63 $\times$ 10 $^{14}$ total evaluations in 45 minutes).
- It was 47.1 $\times$ faster than a bit-parallel OpenMP CPU and 7.06 $\times$ faster than an explicit AVX-512 CPU baseline on matched workloads.
- Hardware calibration reached 18.87 source-level uint32 TOPS with 98.3% mean NVML busy time.
Representation and Retrieval:
- In a retrieval task over 5.4 million candidate pairs, raw high-dimensional features performed best at tight neighborhood budgets ( $k=16$ ), while a 2D PCA atlas performed best at broader budgets ( $k=1024$ ).
- However, the authors emphasize that 2D visualizations suffer from extreme clutter (98.6% of points sharing a bin at 100k scale) and are not standalone discovery tools. The pipeline relies on representation-guided proposal followed by exhaustive verification.
Correspondence Recovery: The engine successfully recovered first-order frame conditions for all Sahlqvist axioms (T, D, 4, 5, B, etc.) and correctly identified the McKinsey axiom as having no first-order correspondent in the tested library, validating the system against established theory.

Significance and Scope
The paper claims significance not as a new decision procedure for general modal logic (which remains PSPACE-complete), but as a reproducible protocol for exploring the "small-model regime" and the boundaries of indistinguishability.

Modesty of Claims: The authors explicitly state that their results are bounded. The census decides validity only for formulas where the FMP bound is within the searched size (up to 5 worlds). Claims about formulas surviving beyond this range are estimates or bounded survivors, not theorems.
Discovery vs. Verification: The paper distinguishes between generating candidates (via synthesis or visual atlases) and certifying them. The "discovery" of the 5-indistinguishable pair is a result of active synthesis and exhaustive verification, not merely visual inspection.
Complementarity: The work is presented as complementary to symbolic model checking (BDDs/SAT). While symbolic methods compress one large state space, this approach explicitly sweeps many small models against many formulas, a regime where symbolic methods may not be optimal.

In summary, the paper demonstrates that GPU-accelerated bitwise evaluation allows for the exhaustive census of small Kripke models, revealing that minimal countermodels are often much smaller than theoretical bounds suggest, and providing a rigorous framework for synthesizing and certifying bounded indistinguishability in modal logic.