WorksComputer Science
The QBF Gallery 2026
Abstract
The QBF Gallery 2026 is the latest evaluation event of (dependency) quantified Boolean formula (QBF) solving technology. Its goal is to assess the current state-of-the-art, enable the evaluation of novel solvers on newly curated benchmark instances and present the progress made since the previous competition. This report discusses the solvers, instances and tools submitted by the community and introduces new benchmark collections for evaluation. We evaluate solvers in three tracks, reflecting most common input formats in (dependency) QBF solving. In addition to those main evaluations, we investigate effects of preprocessing and include a track of new crafted benchmark families. The results are analyzed using various metrics and complementary statistics on solver similarities, different memory limitations and performance across formula families. Finally, the dedicated benchmarks for each track are made available as an artifact to support future research and reproducible evaluation.
Introduction
Quantified Boolean formulas (QBFs) arise in numerous practical applications including synthesis, bounded model checking and planning [63]. The corresponding decision problem is widely regarded as the canonical PSPACE-complete problem [66]. To assess the state-of-the-art in QBF solving, regular events such as the QBFEval and the QBF Gallery have been organized. This tradition began in 2003 and had its latest entry 2023, with numerous editions in between [5, 6, 34, 37, 44, 47, 50, 53, 54]. This paper reports on the organization and results of the QBF Gallery 2026.
The event itself was conducted virtually with the evaluations performed on a local compute cluster. The results were presented at the Federated Logic Conference (FLoC) 2026, as part of the FLoC Olympics, affiliated with the International Conference on Theory and Applications of Satisfiability Testing [1]. In addition to solvers and preprocessors, participants were invited to submit novel problem instances to different tracks covering different QBF formalisms and input formats. The results are analyzed not only to determine a winner for each track but also to identify the practical challenges currently faced by the field. By including instances and solvers from previous competitions, we aim to show the progress made over the last iterations. This paper is structured as follows: First, we describe the organizational aspects of the Gallery including the experimental setup and the individual tracks. We then present the benchmarks and solvers newly submitted and further the selected participants of this Gallery. Finally, we evaluate the results on their different performance metrics and provide a deeper analysis of the collected data.
Organization
The QBF Gallery 2026 featured five tracks, each based on different types of formulas. This section describes the experimental setup including resource limits and evaluation procedure as well as the input formats and semantic details of of each track.
Setup
All experiments were conducted on an Ubuntu 24.04.4 LTS compute cluster consisting of 20 nodes, each equipped with 64 dual-socket 16-core AMD EPYC [email protected] GHz CPUs. All tracks were evaluated on this setup with one allocated node per instance. A timeout of 900 s and a memory limit of 8 GB was set for each instance in every track. Additionally, some selected tracks were re-ran with an increased memory limit of 128 GB to evaluate the extent to which solver performance is constrained by memory limitation.
Tracks of the QBF Gallery 2026
In the following we present the Prenex Conjunctive Normal Form (PCNF), Prenex Non-Conjunctive Normal Form (PNCNF), Dependency Quantified Boolean Formula (DQBF), Crafted Instances and Preprocessor track. Submissions of both formulas and solvers were accepted for the first four tracks. In contrast, the Preprocessor track only accepted preprocessors while using the benchmarks submitted to the PCNF (resp. Non-PCNF) track. Solvers and formulas were allowed to be featured in multiple tracks, provided they satisfy the respective track requirements.
PCNF Track
A QBF in Prenex Conjunctive Normalform (PCNF) has the structure , where is a quantifier prefix with and is a propositional matrix in conjunctive normal form, i.e., a conjunction of clauses (disjunctions) of literals over pairwise
distinct propositional variables . The standardized input format for PCNFs—and consequently the required format of this track—is QDIMACS [56]. Figure 1 shows an example QDIMACS encoding of an exclusive-or formula eligible for the PCNF track.

Figure 1. Example of a QDIMACS representation of
PNCNF Track
In contrast to the PCNF track, the prenex non-CNF (PNCNF) track permits arbitrary propositional formulas as the matrix . The requirements regarding the quantifier prefix are the same as in the PCNF track. Input formulas for this track are accepted in the QCIR (Quantified CIRcuit) [23] format. The left side of Figure 2 shows an example of an QCIR-encoded QBF. A QCIR formula consists of a prefix as well as a sequence of gate definitions bound to Tseitin-like variables [69] called gate variables forming a directed acyclic graph (DAG). Supported gates include and, or, xor (exclusive-or), ite (if-then-else) as well as local quantifiers forall and exists. Consequently, QCIR formulas can represent non-prenex QBFs. To ensure that submitted formulas are in PNCNF, the Gallery imposes the following restrictions:

Figure 2. Example of a QCIR (left) representing and cleansed QCIR (right) instance representing
No free variables (closed prefix)
Only
andandorgates are permittedLocal quantifier gates are not permitted
Variables may use numeric names only
The resulting restricted format is commonly referred to as cleansed QCIR, of which an example is shown on the right side of Figure 2. The semantics of submitted formulas in this format were checked using dedicated tools during benchmark selection.
DQBF Track
Dependency QBF (DQBF) extends QBF by allowing a non-linear quantifier prefix . Instead of a variable being dependent on their predecessor in a linear list, variable dependencies are stated explicitly utilizing Henkin quantifiers [4]. This increased expressiveness also raises the complexity of the decision problem to solve them from PSPACE to NEXPTIME. The input format for this track is DQDIMACS [21], an extension of QDIMACS additionally supporting the definition of Henkin quantifiers and their associated dependencies. Figure 3 shows a DQDIMACS encoding of a false exclusive-or formula, which can be constructed by using explicit dependencies.

Figure 3. Example of a DQDIMACS representation of
Crafted Instances Track
Crafted instances are parameterized formula families originating from proof complexity, such as the Kleine Büning–Karpinski–Flögel (KBKF) formulas [12]. They are designed to assess the strength of the underlying proof systems of QBF solvers. Since the size of these instances can be adjusted, they enable the analysis of how solving effort increases with increasing instance parameter. This scalability analysis is the primary objective of the Crafted Instances track. As all submitted crafted instances are in PCNF format, this track features the corresponding solvers.
Preprocessor Tracks
The Preprocessor track is the only track that does not accept formulas or solvers for submission. Instead, it focuses on evaluating preprocessors. A preprocessor rewrites the input into an equivalent formula without the primary goal of solving it but rather making it (potentially) easier for a subsequent solver to handle. Although also widely employed in inprocessing, preprocessors are executed independently on the benchmarks of a track resulting in a set of novel instances to evaluate. This track features the formulas of the PCNF and PNCNF tracks. No preprocessor was submitted for the DQBF track.
Benchmarks
In the following section, we present the instances submitted to and selected for each track. In addition to describing their origins, we provide basic information about the problems they encode and their structural characteristics. The selection process for the instances was the same for all tracks. First, all newly submitted formulas were solved using the eligible solvers for the respective track. Each run in this smoke test was subject to a time limit of 300 s with four instances executed concurrently on a single node. Instances solved by every solver were removed from the selection pool. From the remaining formulas, we randomly chose a representative subset. To complete the benchmarks, we selected a subset of instances from the previous QBF Gallery 2023 [34]. For the DQBF track, we chose instances from the QBFEval 2020 [55], as the same set of formulas was used in 2023. Finally, we compared the results reported by the solvers to identify disagreements and thus potential unsoundness. The selected formulas of the tracks can be found in the artifact published on Zenodo [51].
PCNF Benchmarks (QDIMACS Format)
Table 1 provides an overview of the submitted and selected formulas for the PCNF track, while detailed statistical data of the selected formulas is summarized in Table 2. In total, we received 523 instances across five different submissions of which 218 were selected for the Gallery. Additionally, we took 88 instances from the QBF Gallery 2023 [34], resulting in a total of 306 instances for the PCNF dataset. In the following we describe the submitted formula families.
| Family | Author | Sub. (Sel.) | sat | unsat | unsolved |
| Bounded Synthesis | Slivovsky F. | 115 (40) | 41 (16) | 39 (12) | 35 (12) |
| Connect4 | Mayer-Eichberger V. et al | 170 (64) | 42 (13) | 101 (45) | 27 (6) |
| Feature Models | Heisinger S. | 20 (16) | 2 (2) | 9 (5) | 9 (9) |
| GDL-Games | He Y. et al. | 152 (68) | 42 (21) | 73 (38) | 37 (9) |
| Pasp2QBF | Mauá et al. | 66 (30) | 44 (23) | 22 (7) | 0 (0) |
| Total | 523 (218) | 171 (75) | 244 (107) | 108 (36) |
Table 1. Submitted (Selected) QDIMACS formulas of the PCNF track
| Dataset | Q. Alt. | Avg. Clauses | Avg. Vars | Avg. | Avg. | # |
| Bounded Synthesis | 2 | 219195 | 62034 | 5 | 62029 | 40 |
| Connect4: partial7x6 | 6-18 | 9043 | 2041 | 20 | 2020 | 30 |
| Connect4: fromEmpty | 10-24 | 9034 | 2010 | 26 | 1983 | 34 |
| Feature Models | 1 | 617841 | 428237 | 9995 | 418242 | 16 |
| GDL-Games: GB | 32-72 | 46326 | 13115 | 95 | 13020 | 17 |
| GDL-Games: GB (bloqqer) | 12-48 | 9205 | 15496 | 38 | 1026 | 15 |
| GDL-Games: GD | 24-72 | 56361 | 19068 | 99 | 18969 | 19 |
| GDL-Games: GD (bloqqer) | 10-34 | 14416 | 19301 | 37 | 1862 | 17 |
| Pasp2QBF | 1 | 6037 | 1644 | 139 | 1505 | 30 |
| Gallery23: Matrix Multiplication | 2 | 305902 | 44962 | 24 | 44938 | 1 |
| Gallery23: Grid Games | 12-20 | 4840 | 1671 | 53 | 1618 | 6 |
| Gallery23: QBFEval 2020 | 1-44 | 267796 | 83839 | 2123 | 62572 | 62 |
| Gallery23: Hex Games | 12 | 7577 | 1999 | 32 | 1968 | 4 |
| Gallery23: Organic Synthesis | 2 | 136281 | 38860 | 14 | 38846 | 4 |
| Gallery23: Pattern Finding | 2 | 14695 | 6232 | 83 | 6149 | 8 |
| Gallery23: Linear Domino | 11-12 | 6359 | 1115 | 140 | 975 | 3 |
Table 2. Statistics of the selected formulas in the PCNF track
The Bounded Synthesis instances encode the question of whether a Mealy machine of at most states realizes or falsifies a given LTL specification. The original encoding was introduced by Faymonville et al. [20].
The Connect4 instances [46] encode the popular Connect Four game as QBFs. Depending on the initial state of the game, the formulas are divided into two subfamilies. Partial7x6 instances begin from an ongoing game whereas fromEmpty instances assume an empty board. The QDIMACS instances were exported using Bule [39].
The Feature Models instances [32] encode feature-model differences as introduced by Heisinger et al. [31]. They include configurations ranging from bicycles to the Linux kernel. Initially, the problems were encoded in Unified Variability Language (UVL) [67] and afterwards exported by Booleguru [30].
The GDL-Games [27] instances are derived from a general Game Description Language (GDL) encoding. They express whether a player can achieve 100 points within steps, regardless of the actions of the other players. Details of the encoding were published by He et al. [26]. The benchmark set is divided into four sub-families: GB instances use a baseline encoding while GD instances use a dependency-based encoding. Both sets were additionally preprocessed using bloqqer [9], resulting in the GD (bloq) and GB (bloa) subfamilies.
The Pasp2QBF instances [45] encode probabilistic answer set programming (PASP) inference problems as 2QBF formulas [70]. The collection contains 12 sub-families representing different problems ranging from Sudoku puzzles to graph coloring. To generate the instances, the PASP problems were first encoded in WCNF formulas and subsequently rewritten as QBFs.
| Family | Author | Sub. (Sel.) | sat | unsat | unsolved |
| Feature Models | Heisinger S. | 20 (16) | 0 (0) | 6 (2) | 14 (14) |
| Functional Synthesis | Khalimov A. | 334 (25) | 311 (20) | 0 (0) | 23 (5) |
| Total | 554 (41) | 311 (20) | 6 (2) | 37 (19) |
| Family | Author | Sub. (Sel.) | sat | unsat | unsolved |
| Feature Models | Heisinger S. | 20 (16) | 0 (0) | 6 (2) | 14 (14) |
| Functional Synthesis | Khalimov A. | 334 (25) | 311 (20) | 0 (0) | 23 (5) |
| Total | 554 (41) | 311 (20) | 6 (2) | 37 (19) |
Table 3. Submitted (Selected) formulas of the PNCNF track
To complete the PCNF track, we also included instances from the QBF Gallery 2023 [33]. Detailed descriptions of the formula families can be found in the report of the Gallery 2023 [34].
PNCNF Benchmarks (QCIR Format)
Table 3 provides an overview of the submitted and selected formulas for the PNCNF track, while detailed statistical data of the selected formulas is shown in Table 4. In total, we received 554 instances across two submissions of which 41 were selected for the Gallery. Additionally, we took 335 instances from the QBF Gallery 2023 [34] resulting in a total of 376 instances for the PNCNF dataset. In the following, we describe the submitted formula families.
| Dataset | Q. Alt. | Avg. gates | Avg. vars | Avg. | Avg. | # |
| Feature Models | 1 | 50144 | 19990 | 9995 | 9995 | 16 |
| Functional Synthesis | 1 | 243962 | 193 | 186 | 7 | 25 |
| Gallery23: Grid Games | 10-20 | 1293 | 140 | 47 | 94 | 19 |
| Gallery23: Transitive Closure | 36-110 | 20310 | 4290 | 2884 | 1406 | 10 |
| Gallery23: Nested Counterfactuals | 7 | 904 | 187 | 96 | 91 | 6 |
| Gallery23: Generalized TTT | 6-14 | 847 | 67 | 21 | 46 | 28 |
| Gallery23: Hyper-Properties | 0-1 | 5071952 | 1460 | 592 | 868 | 20 |
| Gallery23: Matrix Multiplication | 2 | 15103 | 1864 | 25 | 1839 | 10 |
| Gallery23: Hadwiger Conjecture | 1 | 28849 | 196 | 118 | 78 | 21 |
| Gallery23: QBFEval 2020 | 1-7 | 41344 | 2141 | 1185 | 956 | 191 |
| Gallery23: Circuit Minimization | 1-2 | 14036 | 403 | 193 | 211 | 30 |
Table 4. Statistics of the selected formulas in the PNCNF track
The Feature Models instances are the same as described for the PCNF track, but exported from the original UVL into the QCIR format using the tool Booleguru [30].
The Functional Synthesis instances [40] encode the automatic synthesis of a system from a behavioral specification. The resulting instances are formulated as safety games.
To complete the PNCNF track, we also included instances from the QBF Gallery 2023 [33]. Detailed descriptions of the formula families can be found in the report of the QBF Gallery 2023 [34].
DQBF Benchmarks (DQDIMACS Format)
Table 5 provides an overview of the submitted and selected formulas for the DQBF track, while detailed statistical data of the selected formulas is shown in Table 6. In total, we received 980 instances across two submissions of which 139 were selected for the gallery. Additionally, we took 181 instances from the QBFEval 2020 [55] resulting in a total of 320 instances for the DQBF dataset. In the following we describe the submitted formula families.
The Bounded Synthesis instances follow the same encoding as its PCNF-track counterpart but additionally uses Henkin dependencies. Two subfamilies were submitted: the state-symbolic encoding has propositional inputs whereas the fully-symbolic encoding has universal inputs, making it the most concise of the variants.
| Family | Author | Sub. (Sel.) | sat | unsat | unsolved |
| Bounded Synthesis | Slivovsky F. | 386 (73) | 128 (16) | 87 (26) | 171 (31) |
| Ramsey | Cheng C. | 504 (44) | 241 (18) | 31 (6) | 232 (20) |
| Succinct Graph | Cheng C. | 90 (22) | 10 (5) | 42 (9) | 38 (8) |
| Total | 980 (139) | 379 (39) | 160 (41) | 441 (59) |
Table 5. Submitted (Selected) formulas of the DQBF track
| Dataset | Q. Alt. | Avg. clauses | Avg. vars | Avg. | Avg. | Avg. | # |
| Bounded Synthesis: Full | 1 | 2649624 | 100672 | 23 | 100636 | 14 | 36 |
| Bounded Synthesis: State | 1 | 2086759 | 581633 | 12 | 575400 | 6220 | 37 |
| Ramsey | 1 | 389 | 126 | 24 | 90 | 12 | 44 |
| Succinct Graph: Clique | 1 | 951 | 247 | 6 | 173 | 68 | 8 |
| Succinct Graph: Hamiltonian | 1 | 293 | 2108 | 17 | 2074 | 17 | 10 |
| Succinct Graph: Coloring | 1 | 172 | 61 | 24 | 32 | 5 | 4 |
| QBF Eval 2020 | 0-2 | 4105 | 921 | 89 | 747 | 85 | 181 |
Table 6. Statistics of the selected formulas in the DQBF track
The Ramsey and Succinct Graph instances [16] were submitted together with their generator by the same author as one single submission of two formula families. The Ramsey formulas check if a Ramsey number [2] is greater than some threshold. The Succinct Graph formulas encode graph problems from the three subcategories: Clique, Coloring and Hamiltonian.
To complete the DQBF track, we also included instances from the QBFEval 2020 [55].
Crafted Instances
Table 7 provides an overview of the submitted and selected formulas for the Crafted Instances track. We received one submission (QBFFamExt [62]) containing six new families all of which were selected for the track. Each family is parameterized by and some families provide additional parameters for further tuning. Using these parameters, we selected 16 instances across the six families. The details of this selection are shown in Table 8. In the following, we describe the selected formula families.
| Family | Abbr. | Author | result |
| Gadget-Family | GADGET | A. Schleitzer, O. Beyersdorff | unsat |
| All-Equal-SAT | AESAT | A. Schleitzer, O. Beyersdorff | unsat |
| Succinct-K-Radius | SUCCKRAD | A. Schleitzer, O. Beyersdorff | unsat |
| Clique Coloring | CLIQUECOL | A. Schleitzer, O. Beyersdorff | unsat |
| Generalised Subset Sum | SUBSETSUM | A. Schleitzer, O. Beyersdorff | unsat |
| Instance | range | # | |
| AESAT(n) | , 40,50,60,70 | 30 | |
| CLIQUECOL(n) | 4 | ||
| GADGET(n, base=ec, gadget=eq) | , 40,50,60,70 | 30 | |
| GADGET(n, base=ec, gadget=xor) | , 40,50,60,70 | 30 | |
| GADGET(n, base=ic, gadget=eq) | , 40,50,60,70 | 30 | |
| GADGET(n, base=ic, gadget=xor) | , 40,50,60,70 | 30 | |
| GADGET(n, base=sc, gadget=eq) | , 40,50,60,70 | 30 | |
| GADGET(n, base=sc, gadget=xor) | , 40,50,60,70 | 30 | |
| SUBSETSUM(n) | , 40,50,60,70 | 30 | |
| SUCCKRAD(n,k=3) | , 40,50,60,70 | 30 | |
| SUCCKRAD(n,k=5) | , 40,50,60,70 | 30 | |
| SUCCKRAD(n,k=7) | , 40,50,60,70 | 30 | |
| SUCCKRAD(n,k=10) | , 40,50,60,70 | 30 | |
| SUCCKRAD(n,k=15) | , 40,50,60,70 | 30 | |
| SUCCKRAD(n,k=20) | , 40,50,60,70 | 30 | |
| SUCCKRAD(n,k=30) | , 40,50,60,70 | 30 |
Table 7. New Crafted Instance formulas
The All-Equal-SAT family [61] encodes the following problem: Given a 3-CNF formula , where is a partition of , All-Equal--3SAT solves, whether there exists an assignment to the variables in such that for every assignment to the variables in , at least one clause contains either only true or only false literals. The parameter specifies the number of clauses in the generated formula.
The Clique Coloring family [61] encode the decision problem given a graph and , whether admits a -clique-coloring, i.e. a coloring of the vertices in such that no maximal clique in is monochromatic. The parameter specifies the family index of the Grötzsch graph induction.
The Gadget-Family [60] problems are obtained by connecting a propositional base formula with a gadget. Available base formulas are single clause (SC), implication chain (IC) and
equality chain (EC). The gadget can be chosen to be either equality (EQ) or exclusive-or (XOR) constraints. Both the base formula and the gadget are additional parameters of the construction. The parameter specifies either the number of variables for SC or the chain length for IC and EC.
The Generalized Subset Sum [61] family encodes the following problem: Given two integer vectors and with , and an integer , the formula encodes , where and are binary vectors with , . The parameter scales the lengths of and and determines the number of selector variables in the encoding.
The Succinct-K-Radius family encodes whether a Galperin-Widgerson representation of a directed graph has a radius of at most . The value is an additional parameter of the construction. The parameter specifies the grid height.
Solvers and Preprocessors
In the following, we introduce the solvers and preprocessors participating in each track. The participants include not only newly submitted tools but also solvers and preprocessors introduced in previous QBF Galleries. Some solvers appear in multiple tracks because of their support for different input formats.
PCNF Solvers
Table 9 lists the solvers participating in the PCNF track. Three newly submitted solvers, each with up to 8 different configurations, were included. The remaining solvers were selected from the previous QBF Gallery.
| solver | config. | Author | Sub./Sel. | type | ref. |
| caqe | -<br>bloqqer<br>hqspre | L. Tentrup, M. Rabe | selected | CEGAR (clausal abstraction) | [57] |
| DepQBF | -<br>no-nenofex | F. Lonsing | selected | QCDCL | [43] |
| DepQBF | cadical | M. Heisinger | selected | QCDCL | [29] |
| DynQBF | G. Charwat | selected | dynamic programming | [13] | |
| HybridQBF | caqe-v1<br>caqe-v2-m1<br>caqe-v2-m2<br>caqe-v3<br>hb-v0<br>hb-v1<br>hb-v2<br>hqsprebloqqer | L. Zhaohui | submitted | Combination of approaches | [42] |
| MiniQU | F. Slivovsky | selected | QCDCL | [65] | |
| Qute | ofo<br>plain<br>upure | F. Slivovsky | submitted | QCDCL | [49] |
| RAReQS | M. Janota | selected | CEGAR (expansion) | [38] |
Table 9. Participating solvers of the PCNF track
HybridQBF is based on DepQBF and incorporates additional solving techniques including WalkSAT [71] and glue clauses [3]. No accompanying paper or system description is available. The submitted versions utilize different configurations involving the solver caqe [57] as well as Bloqqer [9] and HQSPre [72] for pre- and inprocessing.
DepQBF-cadical [29] replaces the internal SAT solvers of the original DepQBF implementation, Minisat [19], for CaDiCaL [8].
Qute [49] was submitted in three different configurations: one using out-of-order (ofo) decisions [11], one implementing the (vpure) dependency scheme [17] and the (plain) standard configuration [49].
In the following we list the different solving paradigms applied by the PCNF solvers:
CEGAR (Counter Example Guided Abstraction Refinement) iteratively solves propositional abstractions of a QBF formula [18]. Candidate results obtained from an abstraction are validated against the original formula and refined. This process is repeated until the QBF is determined to be true or false. CEGAR is commonly seen as a two player game between the universal and existential player, trying to find a winning strategy for either player. The participating PCNF solvers utilize two flavours of CEGAR:
CEGAR with clausal abstraction decomposes the formula into an abstraction of a sequence of propositional formulas associated with the quantifier blocks [57].
CEGAR with expansion recursively1 expands quantified variables into propositional instances. (Counter)-models discovered during solving are then used to refine the expansion until a result is obtained [38].
Dynamic programming first partitions the CNF matrix into sub-problems using a tree decomposition approach and then processes this decomposition by dynamic programming [14], combining intermediate results from the subproblems. To account for dependencies induced by the quantifier prefix, dependency schemes are integrated into the solving process. This approach can be viewed as an expansion-based method as it combines local expansions of the subproblems.
QCDCL (Quantified Conflict Driven Clause learning) extends CDCL-based SAT solving by learning conflict clauses and solution cubes. Once an empty constraint can be learnt, the result is determined [7].
The following commands have been used for calling the solvers:
caqe <FILE>
caqe --preprocessor=bloqqer --qdo <FILE>
caqe --preprocessor=hqspre --qdo <FILE>
depqbf <FILE>
depqbf --qdo --no-dynamic-nenofex <FILE>
depqbf-cadical <FILE>
dynqbf -f <FILE>
HybridQBF_CAQE_V1 <FILE>
HybridQBF_CAQE_V2_M1 <FILE>
HybridQBF_CAQE_V2_M2 <FILE>
HybridQBF_CAQE_V3 <FILE>
HybridQBF_HB_V0 <FILE>
HybridQBF_HB_V1 <FILE>
HybridQBF_HB_V2 <FILE>
HybridQBF_HQSPre_Bloqqer <FILE>
miniQU <FILE>
qute --out-of-order-decisions all <FILE>
qute <FILE>
qute --depscheme upure <FILE>
rareqs <FILE>
PNCNF Solvers
Table 10 lists the solvers participating in the PNCNF track. Only Qute as described in the previous section was newly submitted to this track. The remaining solvers were selected from the previous QBF Gallery.
| solver | config. | Author | Sub./Sel. | type | ref. |
| cqesto | -<br>cadical | M. Janota | selected | propositional abstraction | [35] |
| GhostQ | -<br>cegar | W. Klieber | selected | QDPLL<br>QDPLL + CEGAR | [41] |
| MiniQU | F. Slivovsky | selected | QCDCL | [65] | |
| qfun | -<br>cadical | M. Janota | selected | expansion + ML | [36] |
| QuABS | L. Tentrup | selected | CEGAR (literal abstraction) | [28] | |
| Qute | ofo<br>plain<br>upure | F. Slivovsky | submitted | QCDCL | [49] |
Table 10. Participating solvers of the PNCNF track
In the following we list the different solving paradigms applied by the PNCNF solvers:
Expansion + ML utilizes machine learning to derive candidate strategies during expansion solving [36]. Rather than expanding the formula with individual assignments, learned strategies are incorporated. As further samples are collected, strategies as well as the expansion are iteratively refined until a result is obtained.
Literal abstraction is a CEGAR-based approach constructing propositional abstractions for quantifier blocks using literals to summarize the interaction between inner and outer blocks [68]. SAT solving provides candidate assignments and counterexamples, which are used to refine the abstractions recursively.
Propositional abstraction is a circuit-based extension of clausal abstraction. Rather than operating on a CNF matrix, the circuit representation of the propositional part of the QBF is preserved during solving. As in clausal abstraction, a propositional abstraction is constructed for each quantifier level and repeatedly solved and refined using SAT solving [35].
QDPLL (Davis-Putnam-Logemann-Loveland for QBFs) [25] is the foundation of modern QCDCL. The search algorithm assigns variables in prefix order while simplifying the formula under the current assignment. The algorithm can be utilized for non-clausal
representation and extended with different modalities of learning and propagation — including CEGAR learning as optionally applied in GhostQ [41].
QCDCL is the same paradigm as described for the PCNF solvers. PNCNF solvers using QCDCL commonly translate the input internally into a CNF representation by applying a Tseitin-style clausification [69].
The following commands have been used for calling the solvers:
cqesto <FILE>
cqesto-cadical <FILE>
qcir-to-gq.sh <FILE> | ghostq /dev/stdin -s-cnf -q2 -cegar 0
qcir-to-gq.sh <FILE> | ghostq /dev/stdin -s-cnf -q2 -cegar 1
miniQU <FILE>
qfun <FILE>
qfun-cadical <FILE>
quabs <FILE>
qute --out-of-order-decisions all <FILE>
qute <FILE>
qute --depscheme upure <FILE>
DQBF
Table 11 lists the solvers participating in the DQBF track. Three newly submitted solvers were included. The remaining solvers were selected from the previous QBF Gallery 2023 [34].
Pedant was submitted as the latest version of the established DQBF solver [59].
P3 is a simplified version of Pedant with optimized internal data-structure for Skolem functions.
Pedant-rewrite is a rewritten version of Pedant submitted in two configurations.
In the following we list the different solving paradigms applied by the DQBF solvers:
Quantifier elimination is a DQBF solving approach that eliminates variables responsible for the non-linear dependencies introduced by the Henkin quantifiers of the formula [24]. This transforms the input into a QBF with linearly ordered dependencies, which is then delegated to a QBF solver. This technique can also be applied to Binary decision diagram (BDD) like datastructures [64].
CEGIS (Counter Example Guided Inductive Synthesis) iteratively constructs Skolem functions of a QBF. If a candidate function is invalid for some assignment of the universal variables, the resulting counterexample is used for refinement by using interpolation based definitions. The process continues until correct Skolem functions are obtained or the QBF is proven to be false [59].
The following commands have been used for calling the solvers:
Table 11. Participating solvers of the DQBF track
Table 12. Preprocessors
dqbdd <FILE>
hqs2 <FILE>
p3 <FILE>
pedant <FILE>
pedant-rewrite <FILE>
pedant-rewrite <FILE> --max-resolutions 1
Preprocessors
Table 12 lists the preprocessors participating in the preprocessor track. Only one new preprocessor, PreProQ, was submitted. In addition, Bloqqer was selected for the PCNF track.
PreProQ (Pre-Processor for Q-circuits) is a PNCNF preprocessor that applies circuit-structure simplification techniques to exploit non-CNF properties [52].
The following parametrization has been used for the preprocessors.
bloqqer <FILE>
preproq <FILE>
Evaluation
This chapter presents the evaluation results of the QBF Gallery 2026. First we describe the methodology of the smoke test. Then we analyze the various metrics and results from our evaluation of each track.
Smoke Test
Before the evaluation, we tested all newly available formulas with a timeout of 300 s using the solvers participating in the complementing track. The smoke test served three purposes: ensuring that each formula can be parsed without errors, identifying potential solver issues early and gathering data necessary for the benchmark selection. A lack of consensus among the results of different solvers may indicates unsound behavior. In the following, we discuss the relevant incidents.
Failing instance:
PCNF/connect4/partial7x6/6_12_442317624273_-13_SAT.qdimacsThe following table provides an overview of the solver results on this instance:
| SAT | UNSAT |
| caqe | caqe-hqspre |
| caqe-bloqqer | HybridQBF-caqe-v2-m2 |
| DepQBF | HybridQBF-caqe-v1 |
| DepQBF-cadical | HybridQBF-hb-v0 |
| DepQBF-no-nenofex | HybridQBF-hb-v1 |
| HybridQBF-hb-v2 | HybridQBF-hqsprebloqqer |
| Qute-plain | |
| Qute-ofo | |
| RAReQS | |
| MiniQU | |
| HybridQBF-caqe-v3 | |
| Qute-upure | |
| HybridQBF-caqe-v2-m1 |
Table 8.
One submitted PCNF formula was reported to be unsatisfiable by six solvers, while the other 13 reported satisfiability. We used DepQBF with QRP certificate generation to verify the result and obtained a successful proof of satisfiability. Consequently, the six solvers that reported unsatisfiable were disqualified for producing an unsound result.2
Failing instance:
DQBF/ramsey/general_R_3_3_04_sat.dqdimacsThe following table provides an overview of the solver results on this instance:
| SAT | UNSAT |
| Pedant | DQBDD |
| P3 | HQS-2022 |
| Pedant-rewrite-no-res | |
| Pedant-rewrite |
Table 20.
In total, five formulas in the DQBF track showed discrepancies. The specified formula is one representative of them. In each case, the solvers DQBDD and HQS-2022 reporting different results. To resolve these cases, we used Pedant to extract models from for the respective formulas, which then could be verified using the provided toolchain (certifyModel.py). Consequently, the two solvers which disagreed with the verified results in multiple cases were disqualified.
After running the preprocessor track, an additional discrepancy was found for HybridQBF-hb-v2. The instance PCNF/bounded-synthesis/simple_arbiter_enc_6__system__b8.qdimacs was reported as unsatisfiable after preprocessing with Bloqqer. Consequently, this solver was also disqualified.2
PCNF Track
Table 13 presents the evaluation results for the PCNF track. For completeness, disqualified solvers are listed with an indicator whether their results are counted. In addition to the participating tools, also the Virtual Best Solver (VBS) is listed. VBS (all) shows the performance of the Virtual Best solver including the disqualified solvers. The solvers are sorted according to their PAR-2 score with a memory limit of 8 GB. The table additionally reports the number of solved formulas, the distribution of satisfiable and unsatisfiable formulas, uniquely solved instances and the number of error codes. Returning unknown (0) was not counted as an error but treated as a timeout receiving the usual PAR-2 penalty. For comparison, we also reported PAR-2 scores using a memory limit of 128 GB. The visualization of those results is shown in Figure 4.
Figure 4. Results of the PCNF track
| Solver | PAR-2 (8 GB) | PAR-2 (128 GB) | Solved | sat | unsat | Unique | Errors |
| VBS (all) | 701.75 | 703.88 | 197 | 82 | 115 | 8 | 0 |
| VBS | 746.99 | 747.04 | 188 | 79 | 109 | 10 | 0 |
| hybridqbf-hb-v1 | 873.23 | 869 | 166 | 71 | 95 | 0 | 0 |
| hybridqbf-hqsprebloqqer | 885.39 | 889.64 | 163 | 72 | 91 | 1 | 0 |
| hybridqbf-hb-v2 | 890.29 | 896.07 | 163 | 72 | 91 | 1 | 1 |
| hybridqbf-hb-v0 | 909.45 | 909.12 | 160 | 70 | 90 | 0 | 0 |
| caqe-bloqqer | 929.70 | 929.80 | 154 | 71 | 83 | 0 | 0 |
| hybridqbf-caqe-v2-m1 | 949.48 | 949.45 | 152 | 63 | 89 | 0 | 0 |
| hybridqbf-caqe-v3 | 960.35 | 960.45 | 151 | 66 | 85 | 3 | 0 |
| hybridqbf-caqe-v1 | 969.28 | 972.134 | 149 | 67 | 82 | 1 | 0 |
| caqe-hqspre | 994.75 | 988.924 | 143 | 65 | 78 | 0 | 2 |
| hybridqbf-caqe-v2-m2 | 1000.51 | 1000.51 | 142 | 64 | 78 | 0 | 0 |
| depqbf-no-nenofex | 1019.17 | 1016.41 | 140 | 57 | 83 | 0 | 0 |
| depqbf-cadical | 1022.40 | 1022.35 | 139 | 56 | 83 | 0 | 4 |
| depqbf | 1030.25 | 1030.40 | 138 | 56 | 82 | 0 | 0 |
| caqe | 1030.80 | 1030.89 | 138 | 57 | 81 | 0 | 0 |
| miniq | 1168.89 | 1168.76 | 114 | 48 | 66 | 0 | 0 |
| rareqs | 1392.47 | 1392.35 | 72 | 37 | 35 | 0 | 0 |
| qute-plain | 1399.05 | 1399.02 | 72 | 31 | 41 | 0 | 0 |
| qute-upure | 1402.54 | 1402.47 | 72 | 32 | 40 | 0 | 0 |
| qute-ofo | 1590.30 | 1590.22 | 37 | 20 | 17 | 0 | 0 |
| dynqbf | 1662.56 | 1660.16 | 25 | 16 | 9 | 2 | 0 |
Table 13. Evaluation data of the PCNF track. Red colored rows are disqualified.
The winner of the PCNF track is caqe with Bloqqer as its preprocessor. After accounting for disqualifications, HybridQBF achieved second place, while demonstrating considerable potential for improved results. Third place was taken by DepQBF. Although DynQBF is ranked last, it uniquely solved two formulas. Increasing the memory limit did not have a significant effect on the results.
PNCNF Track
Table 14 presents the evaluation results for the PNCNF track. As in the PCNF track, we report the usual statistics as well as the additional evaluation with a memory limit of 128 GB. The winner of this track is cqesto with an internal CaDiCaL SAT solver. Second place was achieved by QuABS, followed by qfun in third place. MiniQU is noteworthy for solving the largest number of formulas uniquely. Increasing the memory limit had a slightly positive effect on some solvers, with cqesto showing the biggest improvement.

Figure 5. Results of the PNCNF track
| Solver | PAR-2 (8 GB) | PAR-2 (128 GB) | Solved | sat | unsat | Unique | Errors |
| VBS | 415.62 | 415.58 | 297 | 168 | 129 | 22 | 0 |
| cqesto-cadical | 778.58 | 765.982 | 222 | 133 | 89 | 1 | 0 |
| quabs | 796.86 | 793.92 | 219 | 122 | 97 | 6 | 0 |
| cqesto | 815.30 | 805.217 | 220 | 123 | 97 | 0 | 0 |
| qfun-cadical | 957.02 | 947.965 | 185 | 102 | 83 | 5 | 0 |
| qfun | 972.42 | 969.904 | 186 | 101 | 85 | 2 | 0 |
| ghostq-cegar | 1019.11 | 1015.93 | 175 | 94 | 81 | 0 | 1 |
| miniq | 1037.80 | 1031.22 | 167 | 99 | 68 | 8 | 0 |
| ghostq | 1183.00 | 1180.29 | 137 | 83 | 54 | 0 | 1 |
| qute-plain | 1314.34 | 1314.35 | 110 | 60 | 50 | 0 | 0 |
| qute-ofo | 1463.49 | 1463.47 | 78 | 36 | 42 | 0 | 0 |
| qute-upure | 1495.57 | 1495.57 | 70 | 31 | 39 | 0 | 0 |
Table 14. Evaluation data of the PNCNF track

Figure 6. Results of the DQBF track
| Solver | PAR-2 (8 GB) | PAR-2 (128 GB) | Solved | sat | unsat | Unique | Errors |
| VBS (all) | 719.97 | 723.18 | 200 | 91 | 109 | 10 | 0 |
| VBS | 821.77 | 821.64 | 187 | 82 | 105 | 23 | 0 |
| p3 | 921.84 | 921.93 | 169 | 67 | 102 | 3 | 0 |
| pedant | 956.63 | 950.09 | 161 | 67 | 94 | 0 | 0 |
| hqs2022 | 1105.16 | 1105.62 | 129 | 61 | 68 | 6 | 1 |
| dqbdd | 1143.25 | 1143.19 | 120 | 44 | 76 | 1 | 6 |
| pedant-rewrite | 1247.71 | 1244.68 | 110 | 58 | 52 | 0 | 0 |
| pedant-rewrite-no-res | 1252.27 | 1252.27 | 110 | 59 | 51 | 0 | 0 |
Table 15. Evaluation data of the DQBF track
DQBF Track
Table 15 presents the evaluation for the DQBF track. As in the previous tracks, the table reports the usual statistics. Disqualified solvers are listed for completeness and the VBS (all) solver visualizes the Virtual Best Solver over all participants.
The winner of the DQBF track is P3. Second place was achieved by Pedant, followed by Pedant-rewrite. Even though DQBDD was disqualified, it is noteworthy for solving the most formulas uniquely.
Preprocessor Track
In this track, we evaluated PCNF and PNCNF tracks by placing a preprocessor before each solver. The reported runtimes include both preprocessing and solving time. Table 16 presents statistics for preprocessors run without an attached solver.
Table 17 presents the results obtained by running Bloqqer before the solvers in the PCNF track. We compare the number of formulas solved by each resulting pipeline with the corresponding original results from the PCNF track without preprocessing. Note that the PAR-2 score is computed only over the formulas not trivially solved by the preprocessor, whereas the number of solved formulas includes these 34 instances. It is further noticeable that some HybridQBF configurations suddenly produced a lot of errors. These errors originated in the parser, which reported that no input stream was available. They occurred only sporadically, with no apparent pattern. We were unable to determine their cause and hope that the authors of the solver can address this issue in future versions. The results for HybridQBF-hb-v2 were not processed further because of the inconsistency detected directly in this track. DepQBF-no-nenofex won this track solving 26 additional formulas. Second place went to caqe, which solved 25 additional instances followed by HybridQBF in third place despite three erroneous instances. Qute benefited the most from Bloqqer, solving 37 additional formulas.
Table 18 presents the results of running PreProQ before the solvers in the PNCNF track. Due to the clausification capabilities of this preprocessor, we additionally included the PCNF track winner caqe. The instance PNCNF/Gallery23/hyperprop/2.2.qcir caused PreProQ to exceed its 8 GB memory limit. This subsequently resulted in an error for the attached solver, explaining the single error reported for every solver in this track
| Proc. | Track | total | solved | out | Avg. time |
| Bloqqer | PCNF | 306 | 34 | 12 | 19.26 s |
| PreProQ | PNCNF | 376 | 0 | 1 | 211.62 ms |
Table 16. Results of the preprocessors on their corresponding track
| Solver (bloqqer+...) | PAR-2 | solved (incl. 34) | solved (PCNF) | sat | unsat | Unique | Errors |
| VBS (all) | 749.55 | 202 | 197 | 55 | 113 | 14 | 0 |
| VBS | 776.46 | 197 | 188 | 55 | 108 | 14 | 0 |
| depqbf-no-nenofex | 991.07 | 166 | 140 | 46 | 86 | 1 | 0 |
| caqe | 994.66 | 163 | 138 | 49 | 80 | 0 | 0 |
| caqe-bloqqer | 995.558 | 163 | 154 | 49 | 80 | 0 | 0 |
| hybridqbf-caqe-v2-m1 | 997.09 | 163 | 152 | 49 | 80 | 0 | 3 |
| depqbf-cadical | 1002.79 | 162 | 139 | 45 | 83 | 0 | 0 |
| depqbf | 1022.72 | 159 | 138 | 43 | 82 | 0 | 0 |
| hybridqbf-caqe-v1 | 1048.32 | 156 | 149 | 41 | 81 | 3 | 0 |
| hybridqbf-hb-v0 | 1049.27 | 156 | 160 | 42 | 80 | 1 | 40 |
| hybridqbf-hqsprebloqqer | 1055.68 | 153 | 163 | 42 | 77 | 0 | 36 |
| hybridqbf-hb-v1 | 1060.83 | 152 | 166 | 42 | 76 | 0 | 38 |
| caqe-hqspre | 1088.49 | 148 | 143 | 39 | 75 | 0 | 0 |
| hybridqbf-caqe-v3 | 1089.29 | 148 | 151 | 38 | 76 | 1 | 0 |
| hybridqbf-caqe-v2-m2 | 1092.09 | 147 | 142 | 38 | 75 | 0 | 3 |
| miniq | 1103.37 | 146 | 114 | 42 | 70 | 2 | 0 |
| qute-plain | 1329.66 | 109 | 72 | 32 | 43 | 1 | 0 |
| qute-upure | 1334.80 | 108 | 72 | 32 | 42 | 1 | 0 |
| rareqs | 1387.51 | 100 | 72 | 29 | 37 | 2 | 0 |
| qute-ofo | 1680.42 | 53 | 37 | 10 | 9 | 0 | 0 |
| dynqbf | 1729.95 | 36 | 25 | 7 | 5 | 2 | 0 |
Table 17. Results of Bloqqer with solvers on the PCNF track
| Solver (preproq+...) | PAR-2 | solved | solved (PNCNF) | sat | unsat | Unique | Errors |
| VBS | 415.22 | 297 | 297 | 167 | 130 | 20 | 1 |
| cqesto-cadical | 701.43 | 239 | 222 | 140 | 99 | 3 | 1 |
| quabs | 791.87 | 220 | 219 | 127 | 93 | 7 | 1 |
| cqesto | 841.08 | 213 | 220 | 118 | 95 | 0 | 1 |
| miniq | 962.52 | 181 | 167 | 105 | 76 | 7 | 1 |
| qfun-cadical | 969.99 | 184 | 185 | 103 | 81 | 2 | 1 |
| qfun | 1015.23 | 177 | 186 | 98 | 79 | 1 | 1 |
| ghostq-cegar | 1050.73 | 167 | 175 | 92 | 75 | 0 | 1 |
| ghostq | 1184.33 | 138 | 137 | 84 | 54 | 0 | 1 |
| qute-plain | 1253.48 | 122 | 110 | 63 | 59 | 0 | 1 |
| qute-ofo | 1354.45 | 98 | 78 | 49 | 49 | 0 | 1 |
| caqe | 1383.04 | 93 | - | 40 | 53 | 0 | 1 |
| qute-upure | 1407.87 | 89 | 70 | 36 | 53 | 0 | 1 |
Table 18. Results of PreProQ with solvers on the PNCNF track
The winner of this track is cqesto-cadical. Notably, the base version of cqesto did not benefit to the same extent. Second place was achieved by QuABS, followed by MiniQU in third place. The biggest benefit was observed for Qute-ofo, which solved 20 additional instances.
Crafted Instances Track
Table 19 presents the results of the Crafted Instances track. Due to space limitations, we assigned aliases to the instances. The following list gives the corresponding mappings:
| F0=AESAT() | F8=SUBSETSUM() |
| F1=CLIQUECOL() | F9=SUCCKRAD(, =3) |
| F2=GADGET(, base=ec, gadget=eq) | F10=SUCCKRAD(, =5) |
| F3=GADGET(, base=ec, gadget=xor) | F11=SUCCKRAD(, =7) |
| F4=GADGET(, base=ic, gadget=eq) | F12=SUCCKRAD(, =10) |
| F5=GADGET(, base=ic, gadget=xor) | F13=SUCCKRAD(, =15) |
| F6=GADGET(, base=sc, gadget=eq) | F14=SUCCKRAD(, =20) |
| F7=GADGET(, base=sc, gadget=xor) | F15=SUCCKRAD(, =30) |
with and .
In this track, the parameter is increased incrementally until either the time limit is reached or the final instance is solved. Each table entry denotes the largest solved successfully within the resource limitations. A ✓ indicates that all instances of the respective family were solved successfully.
| Solver | F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15 |
| caqe | 12 | 1 | 14 | 12 | 14 | 13 | 15 | 13 | 10 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| caqe-bloqqer | 13 | 3 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 16 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| caqe-hqspre | 12 | ✓ | 14 | 13 | 15 | 13 | 15 | 13 | 14 | ✓ | ✓ | ✓ | ✓ | 14 | ✓ | 30 |
| depqbf | 19 | 1 | 50 | 12 | ✓ | ✓ | ✓ | ✓ | 10 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| depqbf-cadical | 18 | 1 | 50 | 12 | ✓ | ✓ | ✓ | ✓ | 10 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| depqbf-no-nenofex | 21 | 1 | 20 | 12 | 24 | 12 | 24 | 12 | 10 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| dynqbf | ✓ | 1 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 30 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| hybridqbf-caqe-v1 | 13 | ✓ | 14 | 13 | 15 | 13 | 15 | 13 | 14 | ✓ | ✓ | ✓ | ✓ | 24 | ✓ | 0 |
| hybridqbf-caqe-v2-m1 | 13 | 3 | 14 | 12 | 14 | 13 | 15 | 13 | 10 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| hybridqbf-caqe-v2-m2 | 12 | ✓ | 14 | 13 | 15 | 13 | 15 | 13 | 14 | ✓ | ✓ | ✓ | ✓ | 40 | ✓ | 0 |
| hybridqbf-caqe-v3 | 14 | 3 | 14 | 13 | 15 | 13 | 15 | 13 | 15 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| hybridqbf-hb-v0 | 14 | 2 | 24 | 13 | 24 | 13 | 23 | 13 | 19 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| hybridqbf-hb-v1 | 14 | 2 | 24 | 13 | 24 | 13 | 23 | 13 | 19 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| hybridqbf-hb-v2 | 14 | 2 | 24 | 13 | 24 | 13 | 23 | 13 | 20 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| hybridqbf-hqsprebloqqer | 14 | 2 | 24 | 13 | 24 | 13 | 23 | 13 | 19 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| miniq | 22 | 1 | 24 | 12 | 23 | 12 | 24 | 12 | 11 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| qute-ofo | ✓ | 1 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 12 | ✓ | ✓ | 5 | 9 | 0 | 0 | 0 |
| qute-plain | ✓ | 1 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 12 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 23 |
| qute-upure | ✓ | 1 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 12 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 16 |
| rareqs | 11 | 1 | 14 | 12 | 14 | 11 | 14 | 11 | 10 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
Table 19. Crafted formulas
The CLIQUECOL instances were the most challenging in this track as they were the only family for which the range of had to be adjusted. Even on the range of , the fastest runtime was still above 500 s. In contrast, the SUCKRAD instances were the easiest to solve. No solver solved all SUBSETSUM instances up to . Overall, DynQBF performed the best in this track, successfully solving every family except CLIQUECOL and SUBSETSUM.
Beyond PAR-2 Scores
This section presents additional statistics for the three main tracks. In particular, we examine similarities between solvers and analyze the performance of each solver on the individual formula families. To this end we visualize solver similarities using heatmaps, following a concept introduced at the SAT Competition 2020 [22]. For each pair of solvers, we compute the Pearson correlation coefficient [48] of their runtimes over the individual instances. The resulting values are represented by a color gradient ranging from green (strong inverse correlation) to yellow (no correlation) to red (strong correlation). A solver compared with itself therefore appears in red on the diagonal of the heatmap. Furthermore, we provide histograms showing the results for each participating solver, segmented by the formula families.
PCNF Track
Figure 7 shows the similarities between the solvers in the PCNF track. The solvers least similar to the other participants were DynQBF and Qute with out-of-order decisions. HybridQBF and its hb variants were the most similar to one another. Overall, the track exhibited a moderate degree of variation between solver behaviors. Figure 8 shows the number of solved formulas for each solver, segmented by formula family. The Pasp2QBF family was solved the most frequently overall, whereas the solvers struggled the most with the Gallery 23: Pattern finding instances.

Figure 7. Solver similarities of the PCNF track visualized in a heatmap

Figure 8. Formula families solved by the solvers of the PCNF track
The Feature model family has by far the largest average number of clauses and variables, whereas Gallery23: Grid Games has the smallest averages for both measures. Both
Pasp2QBF and Feature model contain only one quantifier alternation, while GDL-Games: GB has the largest average number of quantifier alternations. The hard to solve Gallery23: Pattern finding family does not stand out in any of these metrics. Overall, no strong correlation between those statistics and the hardness of a formula was observed.
PNCNF Track
Figure 9 shows the similarities between the solvers in the PNCNF track. The variation among these solvers is substantially higher than in the PCNF track, indicating less similar solver behavior overall. The most similar solvers are primarily different configurations of the same solver. Figure 10 shows the number of solved formulas for each solver, segmented by formula family. The highest number of solved instances comes from the QBFEval2020, which unsurprising since this family accounts for approximately 50 % of the instances of the track. The most challenging families were the new Feature Models and the Gallery23: Transitive Closure.

Figure 9. Solver similarities of the PNCNF track visualized in a heatmap

Figure 10. Formula families solved by the solvers of the PNCNF track
The Gallery23: Hyper-Properties family has the largest average number of gates, while having a comparatively moderate average number of variables and the Feature Models family has the largest average number of variables. Generalized TTT has the smallest average numbers of both gates and variables. The difficult Gallery23: Transitive Closure family has the second-largest average number of variables. Overall, the results indicate a slight trend towards increased solving time for families with more variables.
DQBF Track
Figure 11 shows the similarities between the solvers of the DQBF track. Pedant-rewrite, DQBDD and HQS-2022 differ most from the remaining solvers in this track. Pedant and P3 are the most similar.

Figure 11. Solver similarities of the DQBF track visualized in a heatmap
Figure 12 shows the number of solved formulas for each solver, segmented by formula family. Most solved instances originated from the QBFEval2020 family, which accounts for more than half of the formulas in the track. The Succinct Graph: Coloring family was the most challenging overall.

Figure 12. Formula families solved by the solvers of the DQBF track
The Bounded Synthesis: Full family has by far the largest average numbers of clauses and variables, while also having the lowest proportion of variables quantified by Henkin quantifiers at only 0.014 %. The Succinct Graph: Coloring family has the smallest average numbers of both variables and clauses. In contrast, Succinct Graph: Clique has the highest average proportion of Henkin-quantified variables at 27.53 %. Overall, these metrics do not appear to correlate with formula hardness.
Conclusion
The QBF Gallery 2026 continued the traditional series of QBF evaluations. We evaluated a range of new formulas and solvers with a noticeable increase in interest in DQBF. All submitted instances and solvers were described, analyzed and tested before conducting the detailed evaluation.
In addition to the main tracks, we evaluated new crafted instances and investigated the effect of preprocessing. Beyond the usual PAR-2 scores, we also provided insights into solver similarities and performance on individual formula families. Finally, we released the new benchmarks in a dedicated artifact [51].
Results with disqualified solvers
Figure 13 and 14 show the results of the PCNF and DQBF track with the disqualified solvers.

Figure 13. Results of the PCNF track containing also the disqualified solvers

Figure 14. Results of the DQBF track containing also the disqualified solvers
References
- [1]SAT 2026. 29th International Conference on Theory and Applications of Satisfiability Testing, volume 377 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. URL: https://www.dagstuhl.de/dagpub/978-3-95977-431-4.
- [2]Miklós Ajtai, János Komlós, and Endre Szemerédi. A note on ramsey numbers. Journal of Combinatorial Theory, Series A, 29(3):354–360, 1980. doi:10.1016/0097-3165(80)90030-8.DOI
- [3]Gilles Audemard and Laurent Simon. Predicting learnt clauses quality in modern SAT solvers. In IJCAI 2009: Proceedings of the 21st International Joint Conference on Artificial Intelligence, pages 399–404, 2009. URL: http://ijcai.org/Proceedings/09/Papers/074.pdf.
- [4]Valeriy Balabanov, Hui-Ju Katherine Chiang, and Jie-Hong R. Jiang. Henkin quantifiers and boolean formulae: A certification perspective of dqbf. Theoretical Computer Science, 523:86–100, 2014. doi:10.1016/j.tcs.2013.12.020.DOI
- [5]Daniel Le Berre, Massimo Narizzano, Laurent Simon, and Armando Tacchella. The second QBF solvers comparative evaluation. In SAT 2004: 7th International Conference on Theory and Applications of Satisfiability Testing, volume 3542 of Lecture Notes in Computer Science, pages 376–392. Springer, 2004. doi:10.1007/11527695\_28.DOI
- [6]Daniel Le Berre, Laurent Simon, and Armando Tacchella. Challenges in the QBF arena: the sat’03 evaluation of QBF solvers. In SAT 2003: 6th International Conference on Theory and Applications of Satisfiability Testing, volume 2919 of Lecture Notes in Computer Science, pages 468–485. Springer, 2003. doi:10.1007/978-3-540-24605-3\_35.DOI
- [7]Olaf Beyersdorff, Mikoláš Janota, Florian Lonsing, and Martina Seidl. Quantified boolean formulas. In Handbook of Satisfiability - Second Edition, volume 336 of Frontiers in Artificial Intelligence and Applications, pages 1177–1221. IOS Press, 2021. doi:10.3233/FAIA201015.
- [8]Armin Biere, Tobias Faller, Katalin Fazekas, Mathias Fleury, Nils Froleyks, and Florian Pollitt. CaDiCaL 2.0. In CAV 2024: 36th International Conference on Computer Aided Verification, volume 14681 of Lecture Notes in Computer Science, pages 133–152. Springer, 2024. doi:10.1007/978-3-031-65627-9\_7.DOI
- [9]Armin Biere, Florian Lonsing, and Martina Seidl. Blocked clause elimination for QBF. In CADE 23: 23rd International Conference on Automated Deduction, volume 6803 of Lecture Notes in Computer Science, pages 101–115. Springer, 2011. doi:10.1007/978-3-642-22438-6\_10.DOI
- [10]Roderick Bloem, Nicolas Braud-Santoni, Vedad Hadzic, Uwe Egly, Florian Lonsing, and Martina Seidl. Expansion-based QBF solving without recursion. CoRR, abs/1807.08964, 2018. doi:10.48550/ARXIV.1807.08964.DOI
- [11]Benjamin Böhm, Tomás Peitl, and Olaf Beyersdorff. Should decisions in QCDCL follow prefix order? J. Autom. Reason., 68(1):5, 2024. doi:10.1007/S10817-024-09694-6.
- [12]Hans Kleine Büning, Marek Karpinski, and Andreas Flögel. Resolution for quantified boolean formulas. Information and computation, 117(1):12–18, 1995. doi:10.1006/inco.1995.1025.DOI
- [13]Günther Charwat and Stefan Woltran. Bdd-based dynamic programming on tree decompositions. Database and Artificial Intelligence Group, TU Wien, Tech. Rep. DBAI-TR-2016, 95, 2016. URL: http://hdl.handle.net/20.500.12708/78589.
- [14]Günther Charwat and Stefan Woltran. Dynamic programming-based qbf solving. In QBF@SAT, pages 27–40, 2016. URL: https://ceur-ws.org/Vol-1719/paper2.pdf.
- [15]Che Cheng, Long-Hin Fung, Jie-Hong R. Jiang, and Tony Tan. pedant-rewrite. Zenodo, 2026. doi:10.5281/zenodo.20265576.DOI
- [16]Che Cheng, Long-Hin Fung, Chi-Kit Ng, Chen-Ching Nieh, Jie-Hong R. Jiang, Friedrich Slivovsky, and Tony Tan. DQBF instances: Ramsey and succinct graph. Zenodo, 2026. URL: https://zenodo.org/records/20263590.
- [17]Leroy Chew and Tomás Peitl. Strong (D)QBF dependency schemes via pure paths with applications to proof checking. In SAT 2026: 29th International Conference on Theory and Applications of Satisfiability Testing, volume 377 of LIPICs, pages 11:1–11:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. doi:10.4230/LIPIcs.SAT.2026.11.
- [18]Edmund M. Clarke, Orna Grumberg, Somesh Jha, Yuan Lu, and Helmut Veith. Counterexample-guided abstraction refinement for symbolic model checking. J. ACM, 50(5):752–794, 2003. doi:10.1145/876638.876643.
- [19]Niklas Eén and Niklas Sörensson. Minisat. Github, 2013. URL: https://github.com/niklasso/minisat.
- [20]Peter Faymonville, Bernd Finkbeiner, Markus N. Rabe, and Leander Tentrup. Encodings of bounded synthesis. In TACAS 2017: 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, volume 10205 of Lecture Notes in Computer Science, pages 354–370, 2017. doi:10.1007/978-3-662-54577-5\_20.
- [21]Andreas Fröhlich, Gergely Kovásznai, Armin Biere, and Helmut Veith. idq: Instantiation-based dqbf solving. In POS-14: Fifth Pragmatics of SAT workshop, volume 27 of EPiC Series in Computing, pages 103–116. EasyChair, 2014. doi:10.29007/1s5k.
- [22]Nils Froleyks, Marijn Heule, Ashlin Isar, Matti Järvisalo, and Martin Suda. SAT competition 2020. Artificial Intelligence, 301:103572, 2021. doi:10.1016/J.ARTINT.2021.103572.
- [23]QBF Gallery, 2014. URL: https://qbf.pages.sai.jku.at/qcir.pdf.
- [24]Karina Gitina, Ralf Wimmer, Sven Reimer, Matthias Sauer, Christoph Scholl, and Bernd Becker. Solving DQBF through quantifier elimination. In DATE 2015: Proceedings of the 2015 Design, Automation and Test in Europe Conference, pages 1617–1622. ACM, 2015. URL: https://dl.acm.org/doi/10.5555/2755753.2757188.DOI
- [25]Alexandra Goultiaeva, Vicki Iverson, and Fahiem Bacchus. Beyond cnf: A circuit-based qbf solver. In International Conference on Theory and Applications of Satisfiability Testing, pages 412–426. Springer, 2009. doi:10.1007/978-3-642-02777-2_38.DOI
- [26]Yifan He, Abdallah Saïdine, and Michael Thielscher. Solving Two-player Games with QBF Solvers in General Game Playing. In AAMAS 2024: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 807–815. International Foundation for Autonomous Agents and Multiagent Systems, 2024. doi:10.5555/3635637.3662934.DOI
- [27]Yifan He, Abdallah Saïdine, and Michael Thielscher. PCNF instances: GDL-games. Github, 2026. URL: https://github.com/hharryf/gdl2qbf-general/tree/main/qbfgallery2026.
- [28]Jesko Hecking-Harbusch and Leander Tentrup. Solving QBF by abstraction. In GandALF 2018: Proceedings Ninth International Symposium on Games, Automata, Logics, and Formal Verification, volume 277 of EPTCS, pages 88–102, 2018. doi:10.4204/EPTCS.277.7.DOI
- [29]Maximilian Heisinger. dqbf-cadical. Gitlab, 2025. URL: https://gitlab.sai.jku.at/maximilian/deqbf-cadical.
- [30]Maximilian Heisinger, Simone Heisinger, and Martina Seidl. Booleguru, the propositional polyglot (short paper). In IJCAR 2024: 12th International Joint Conference on Automated Reasoning, volume 14739 of Lecture Notes in Computer Science, pages 315–324. Springer, 2024. doi:10.1007/978-3-031-63498-7\_19.DOI
- [31]Simone Heisinger, Maximilian Heisinger, and Martina Seidl. (semantic) feature model differences with (Q)SAT. In SLE 2025: 18th International Conference on Software Language Engineering, pages 189–198. ACM, 2025. doi:10.1145/3732771.3742723.DOI
- [32]Simone Heisinger, Maximilian Heisinger, and Martina Seidl. PCNF/PNCNF instances: Feature models. GitLab, 2026. URL: https://gitlab.sai.jku.at/monasan/fm-qbf.
- [33]Simone Heisinger, Luca Pulina, and Martina Seidl. Instances of the QBF gallery 2023. GitLab, 2023. URL: https://qbf23.pages.sai.jku.at/gallery/.
- [34]Simone Heisinger, Luca Pulina, and Martina Seidl. The qbf gallery 2023, 2026. URL: https://arxiv.org/abs/2604.16153, arXiv:2604.16153.
- [35]Mikolás Janota. Circuit-based search space pruning in QBF. In SAT 2018: 21st International Conference on Theory and Applications of Satisfiability Testing, volume 10929 of Lecture Notes in Computer Science, pages 187–198. Springer, 2018. doi:10.1007/978-3-319-94144-8\_12.DOI
- [36]Mikolás Janota. Towards generalization in QBF solving via machine learning. In AAAI 18: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, the 30th innovative Applications of Artificial Intelligence and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence, pages 6607–6614. AAAI Press, 2018. doi:10.1609/AAAI.V32I1.12208.DOI
- [37]Mikolás Janota, Charles Jordan, Will Klieber, Florian Lonsing, Martina Seidl, and Allen Van Gelder. The QBFGallery 2014: The QBF competition at the floc olympic games. J. Satisf. Boolean Model. Comput., 9(1):187–206, 2014. doi:10.3233/SAT190108.
- [38]Mikolás Janota, William Klieber, Joao Marques-Silva, and Edmund Clarke. Solving QBF with counterexample guided refinement. Artificial Intelligence, 234:1–25, 2016. doi:10.1016/j.artint.2016.01.004.DOI
- [39]Jean Christoph Jung, Valentin Mayer-Eichberger, and Abdallah Saffidine. QBF programming with the modeling language bule. In SAT 2022: 25th International Conference on Theory and Applications of Satisfiability Testing, volume 236 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SAT.2022.31.DOI
- [40]Ayrat Khalimov. PCNF instances: Functional synthesis. Github, 2026. URL: https://github.com/5nizza/relation-determinization.
- [41]William Klieber. Ghsto qbf solver system description, 2012. URL: https://www.wklieber.com/ghstoq/ghstoq-sys-desc.pdf.
- [42]Zhaohui Liu. Hybridqbf. Github, 2026. URL: https://github.com/LiuZH0001/QBFGallery26_HybridQBF_HQSPre_Bloqqer.
- [43]Florian Lonsing and Uwe Egly. DepQBF 6.0: A search-based QBF solver beyond traditional QCDCL. In CADE 26: 26th International Conference on Automated Deduction, volume 10395 of Lecture Notes in Computer Science, pages 371–384. Springer, 2017. doi:10.1007/978-3-319-63046-5\_23.
- [44]Florian Lonsing, Martina Seidl, and Allen Van Gelder. The QBF gallery: Behind the scenes. CoRR, abs/1508.01045, 2015. arXiv:1508.01045, doi:10.48550/ARXIV.1508.01045.DOI
- [45]Denis D. Mauá, Rahul Kapur, YooJung Choi, and Guy Van den Broeck. PCNF instances: PASP2QBF. Github, 2026. URL: https://github.com/Rkus990/pasp2qbf-benchmarks.
- [46]Valentin Mayer-Eichberger and Abdallah Saffidine. PCNF instances: Connect4. Github, 2026. URL: https://github.com/vale1410/connect4qbf.
- [47]Massimo Narizzano, Luca Pulina, and Armando Tacchella. Report of the third QBF solvers evaluation. J. Satisf. Boolean Model. Comput., 2(1-4):145–164, 2006. doi:10.3233/SAT190019.
- [48]Karl Pearson. Note on regression and inheritance in the case of two parents. proceedings of the royal society of London, 58:240–242, 1895. URL: https://www.jstor.org/stable/115794.
- [49]Tomás Peitl, Friedrich Slivovsky, and Stefan Szeider. Dependency learning for QBF. J. Artif. Intell. Res., 65:180–208, 2019. URL: https://doi.org/10.1613/jair.1.11529, doi: 10.1613/JAIR.1.11529.
- [50]Claudia Peschiera, Luca Pulina, Armando Tacchella, Uwe Bubeck, Oliver Kullmann, and Inês Lynce. The seventh QBF solvers evaluation (qbfeval’10). In SAT 2010: 13th International Conference on Theory and Applications of Satisfiability Testing, volume 6175 of Lecture Notes in Computer Science, pages 237–250. Springer, 2010. doi:10.1007/978-3-642-14186-7\_20.
- [51]Cynthia Peyrer, Luca Pulina, and Martina Seidl. Qbf gallery 2026, 2026. doi:10.5281/zenodo.22639316.arxiv.org/abs/2611.18169
- [52]Mark Peyrer. Reprocessing of Non-QCNF prenex formulas. 2024. URL: https://resolver.obvsg.at/urn:nbn:at:at-ubl:1-7273.
- [53]Luca Pulina. The ninth QBF solvers evaluation - preliminary report. In QBF 2016: Proceedings of the 4th International Workshop on Quantified Boolean Formulas, volume 1719 of CEUR Workshop Proceedings, pages 1–13. CEUR-WS.org, 2016. URL: https://ceur-ws.org/Vol-1719/paper0.pdf.
- [54]Luca Pulina and Martina Seidl. The 2016 and 2017 QBF solvers evaluations (QBFEVAL’16 and QBFEVAL’17). Artificial Intelligence, 274:224–248, 2019. doi:10.1016/J.ARTINT.2019.04.002.
- [55]Luca Pulina, Martina Seidl, and Ankit Shukla. Qbf evaluation 2020, 2020. URL: https://www.qbflib.org/event_page.php?year=2020.
- [56]QBFLib, 2005. URL: https://www.qbflib.org/qbflib.html.
- [57]Markus N. Rabe and Alexander Tentrup. CAQE: A certifying QBF solver. In FMCAD 2015: 15th Conference on Formal Methods in Computer-Aided Design, pages 136–143. IEEE, 2015. doi:10.1109/FMCAD.2015.7542263.DOI
- [58]Franz Reichl and Friedrich Slivovsky. P3. Github, 2025. URL: https://github.com/fxreichl/p3.
- [59]Franz-Xaver Reichl and Friedrich Slivovsky. Pedant: A certifying DQBF solver. In SAT 2022: 25th International Conference on Theory and Applications of Satisfiability Testing, volume 236 of LIPIcs, pages 201–210. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SAT.2022.20.
- [60]Agnes Schleitzer and Olaf Beyersdorff. Classes of hard formulas for qbf resolution. Journal of Artificial Intelligence Research, 77:1455–1487, 2023. doi:10.1613/jair.1.14710.DOI
- [61]Agnes Schleitzer and Olaf Beyersdorff. Computationally hard problems are hard for qbf proof systems too. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 11336–11344, 2025. doi:10.1609/aaai.v39i11.33233.
- [62]Agnes Schleitzer and Olaf Beyersdorff. Crafted instance generator. Github, 2026. URL: https://github.com/AgnesSchubert/qbffamExt.
- [63]Ankit Shukla, Armin Biere, Luca Pulina, and Martina Seidl. A survey on applications of quantified boolean formulas. In ICTAI 2019: 31st IEEE International Conference on Tools with Artificial Intelligence, pages 78–84. IEEE, 2019. doi:10.1109/ICTAI.2019.00020.DOI
- [64]Juraj Šíć and Jan Strejcek. DQBDD: an efficient bdd-based DQBF solver. In SAT 2021: 24th International Conference on Theory and Applications of Satisfiability Testing, volume 12831 of Lecture Notes in Computer Science, pages 535–544. Springer, 2021. doi:10.1007/978-3-030-80223-3\_36.DOI
- [65]Friedrich Slivovsky. Miniqu. Github, 2024. URL: https://github.com/fslivovsky/miniQU.
- [66]Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pages 1–9. ACM, 1973. doi:10.1145/800125.804029.DOI
- [67]Chico Sundermann, Kevin Feichtinger, Dominik Engelhardt, Rick Rabiser, and Thomas Thüm. Yet another textual variability language? a community effort towards a unified language. In SPLC 2021: Proceedings of the 25th ACM International Systems and Software Product Line Conference – Volume A, page 136–147. Association for Computing Machinery, 2021. doi:10.1145/3461001.3471145.
- [68]Leander Tentrup. Non-prenex QBF solving using abstraction. In International Conference on Theory and Applications of Satisfiability Testing, pages 393–401. Springer, 2016. doi:10.1007/978-3-319-40970-2_24.DOI
- [69]Grigorii S Tseitin. On the complexity of derivation in propositional calculus. In Automation of reasoning: 2: Classical papers on computational logic 1967–1970, pages 466–483. Springer, 1983. doi:10.1007/978-3-642-81955-1_28.DOI
- [70]Benjie Wang, Denis Deratani Mauá, Guy Van den Broeck, and YooJung Choi. A compositional atlas for algebraic circuits. In Advances in Neural Information Processing Systems, volume 37, pages 141318–141355. Curran Associates, Inc., 2024. doi:10.52202/079017–4488.arxiv.org/abs/2412.05481
- [71]Wei Wei, Jordan Eenrich, and Bart Selman. Towards efficient sampling: Exploiting random walk strategies. In Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, pages 670–676. AAAI Press / The MIT Press, 2004. URL: http://www.aaai.org/Library/AAAI/2004/aaai04-106.php.
- [72]Ralf Wimmer, Sven Reimer, Paolo Marin, and Bernd Becker. HQSpre - an effective preprocessor for QBF and DQBF. In TACAS 2017: 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, volume 10205 of Lecture Notes in Computer Science, pages 373–390, 2017. doi:10.1007/978-3-662-54577-5\_21.
