Our paper Bitwuzla received a Distinguished Paper Award at CAV 2023 in Paris. It accompanies the first official release of Bitwuzla, our SMT solver for the quantified and quantifier-free theories of fixed-size bit-vectors, arrays, floating-point arithmetic, and uninterpreted functions. In this post we explain why we wrote a new solver from scratch, how it is organized, and how it performs.
From Boolector to Bitwuzla
Bit-precise reasoning, that is, reasoning about fixed-size bit-vectors, often in combination with arrays, uninterpreted functions and floating-point arithmetic, is at the heart of many applications in hardware and software verification, symbolic execution, and model checking. For years, our previous solver Boolector largely dominated the quantifier-free divisions with bit-vectors and arrays in the annual SMT competition (SMT-COMP). Boolector was originally published by Robert Brummayer and Armin Biere in 2009, and since 2012 we have been its main developers, extending it with support for uninterpreted functions and lambda terms, local search, and quantified bit-vector formulas.
Boolector, however, has several limitations that make it increasingly hard to maintain and extend. Its code base consists of largely monolithic C code with a rigid architecture built around a tight integration of bit-vectors and arrays. Users have to manage memory and reference counts manually, and terms and sorts are tied to a single solver instance. Further, all preprocessing techniques are destructive, which prevents incremental preprocessing, and incremental solving with quantifiers is not supported.
In 2018, we forked Boolector and entered an extended version of this fork in SMT-COMP 2020 under the name Bitwuzla, with support for floating-point arithmetic, ternary propagation-based local search, and unsat cores, and, since 2022, quantifiers. Architectural and structural limitations inherited from Boolector, however, remained. We thus decided to discard the existing code base and rewrite Bitwuzla from scratch in C++. Rather than reimplementing Boolector, we carefully dissected and reevaluated each of its parts to guide the design of the new solver. Its name, pronounced bitvootslah, is derived from an Austrian dialect expression that can be translated as someone who tinkers with bits.
Architecture
Bitwuzla consists of two main components: the Node Manager and the Solving Context.
The Node Manager constructs and maintains terms and sorts. Terms are represented as immutable, reference-counted nodes in a directed acyclic graph, and hash-consing maximizes the sharing of subterms. Nodes and types are stored globally (thread-local), which allows them to be shared between arbitrarily many solver instances within one thread. This is one of the key differences from Boolector, where terms and sorts are reference-counted manually and belong to a single solver instance.
A Solving Context is the internal equivalent of a solver instance. It determines the satisfiability of the current set of assertions, provides models and unsat cores, and supports incremental solving via push and pop and solving under assumptions. A Solving Context consists of three main components:
- The preprocessor applies a pipeline of satisfiability-preserving passes until fixed-point, for example, substitution of variables, skeleton preprocessing of the Boolean structure, elimination of embedded constraints, and normalization of arithmetic expressions. Preprocessing in Bitwuzla is fully incremental: simplifications derived from lower assertion levels are applied to all assertions on higher levels, including assumptions. Boolector, on the other hand, only preprocesses top-level assertions.
- The rewriter transforms terms into semantically equivalent normal forms, independently of the current set of assertions. Required rewrite rules reduce terms to a small base set of operators, while optional rules are grouped into two levels: rules that only consider the immediate children of a term, and rules that may consider multiple levels of children, which, if not implemented carefully, may destroy sharing of subterms.
- The solver engine is the central solving component, which manages the theory solvers and their interaction.
Every component except the rewriter depends on the current set of assertions. To take full advantage of incremental solving, Bitwuzla saves and restores the internal solver state on push and pop by means of backtrackable data structures, similar to the context-dependent data structures in cvc5. This allows the solver to reuse work from previous satisfiability checks and enables incremental preprocessing.
Bitwuzla provides a comprehensive C++ API as its main interface, with C and Python APIs built on top, and a command line interface that supports SMT-LIBv2 and BTOR2 as input languages.
Lemmas on demand with a bit-vector abstraction
Unlike SMT solvers such as cvc5 and Z3, which are based on the CDCL(T) framework, the solver engine implements the lazy, abstraction/refinement-based paradigm lemmas on demand. However, rather than using a propositional abstraction of the input formula, Bitwuzla works with a bit-vector abstraction, similar to Boolector. All propositional and bit-vector terms are handled by the bit-vector solver. Theory atoms that do not belong to the theory of bit-vectors are abstracted as Boolean constants, and bit-vector terms with operators from other theories are abstracted as bit-vector constants. For example, a read from an array with bit-vector elements is abstracted as a fresh bit-vector constant, and an equality between two arrays as a fresh Boolean constant.
If the bit-vector abstraction is satisfiable, the floating-point, array, uninterpreted function, and quantifier solvers check the resulting satisfying assignment for consistency with their theory axioms. If a theory solver finds an inconsistency, it sends a lemma that refines the abstraction and rules it out. This loop is repeated until either the abstraction is unsatisfiable, or none of the theory solvers report an inconsistency.
The theory solvers implement the following techniques:
- Bit-vectors. The bit-vector solver combines two orthogonal approaches. Bit-blasting translates the abstraction into an And-Inverter Graph (AIG), simplifies it with AIG-level rewriting, and converts it to CNF for the SAT solver back end, which can be CaDiCaL (the default), CryptoMiniSat, or Kissat. Ternary propagation-based local search propagates target values from outputs to inputs on the word level and can be run with a resource limit before falling back to bit-blasting. Since local search can only determine satisfiability, it is particularly effective in combination with (rather than instead of) bit-blasting.
- Arrays. The array solver extends the lemmas on demand procedure from Boolector with support for (equalities over) nested arrays and non-extensional constant arrays. Bitwuzla implements separate solvers for arrays and uninterpreted functions instead of generalizing arrays to lambda terms as Boolector does, which keeps the handling of extensionality simple.
- Floating-point arithmetic. Floating-point constraints are eagerly translated to equisatisfiable bit-vector constraints (word-blasting) via SymFPU, a C++ library of bit-vector encodings of floating-point operations.
- Uninterpreted functions. The UF solver implements dynamic Ackermannization, a lazy form of Ackermann’s reduction that checks the function congruence axiom against the current assignment and produces a lemma whenever it is violated.
- Quantifiers. Quantified formulas are handled by a dedicated module that implements model-based quantifier instantiation for all supported theories and their combinations. In contrast to Boolector, Bitwuzla supports quantifiers in combination with incremental solving and unsat cores.
Results
We evaluated Bitwuzla on all non-incremental and incremental benchmarks in SMT-LIB of all logics it supports, against Boolector, the SMT-COMP 2022 version of Bitwuzla (SC22, the Boolector-based fork), and the SMT-COMP 2022 versions of cvc5 and Z3, using a time limit of 1200 seconds.
- Non-incremental benchmarks (146,235 instances). Bitwuzla solved the most benchmarks overall (144,287), compared to 143,617 for SC22, 142,995 for cvc5, and 141,778 for Z3. It solved the most benchmarks in the quantified divisions, with over 600 more than SC22 and over 4,200 more than Boolector. It also took the lead in the quantifier-free divisions, with 44 more solved benchmarks than SC22 and over 650 more than cvc5. On the 140,438 commonly solved instances, Bitwuzla was the fastest solver, while cvc5 was 2.85× and Z3 5.1× slower.
- Incremental benchmarks (699,612 check-sat queries). Bitwuzla again solved the most queries overall (693,263) and in the quantifier-free divisions. In the quantified divisions, it solved the second largest number of queries after Z3, and over 3,700 more than SC22.
What’s next
The paper outlines several directions for future work. We plan to explore more interleaved combinations of local search and bit-blasting, possibly sharing information between the two procedures. For arrays, we plan to add dedicated operators for extended array operations such as memset and memcpy, as well as support for extensional constant arrays (which we have since added, see our post on the CAV 2026 paper). We further plan to support the upcoming SMT-LIB version 3 standard, once it is finalized.
Bitwuzla is available on GitHub under the MIT license, and its documentation is available at bitwuzla.github.io. It has been extensively tested for robustness and correctness with our API fuzzer Murxla, which is an integral part of its development workflow.
For all the details, see the paper. The artifact is available on Zenodo.