Satisfiability Modulo Extensional Constant Arrays  
by Mathias Preiner and Aina Niemetz, 26 Jul 2026  

Our paper Satisfiability Modulo Extensional Constant Arrays received a Distinguished Paper Award at CAV 2026 in Lisbon. It closes a long-standing gap in SMT solving: deciding problems with constant arrays, arrays that hold the same value at every index, when the index domain is finite, as it always is for machine integers. In this post we explain why that case is tricky and what our new procedure does about it.

Arrays, and arrays with a default value

Arrays are the natural model for memory in hardware and for array data structures in software and therefore ubiquitous in hardware and software verification. The SMT-LIB standard defines a theory of arrays with two operations: select reads the element at an index, and store writes an element at an index to produce a new array. The theory is extensional, meaning that two arrays are equal exactly when they agree at every index.

What the standard theory cannot express succinctly is an array initialized with a default value, for example, a zero-initialized block of memory. Without a dedicated construct, this is usually encoded by writing the default value explicitly to every relevant index with a long chain of stores. However, that is both imprecise (only the indices you explicitly wrote are covered) and inefficient (the store chains can get very deep).

Extending the standard theory with constant arrays closes this gap. A constant array \(\langle v \rangle\) stores the value \(v\) at every index, so reading it anywhere gives \(v\). SMT solvers that support this extension accept the constant array construct written as ((as const (Array I E)) v) in SMT-LIB.

Why finite index domains are hard

Previous decision procedures for extensional constant arrays all assume that the index domain is infinite, for example the mathematical integers. That assumption makes reasoning much easier. Two infinite constant arrays with different default values can never be made equal, since this would require infinitely many stores to change every index. Thus, equalities between constant arrays reduce to equalities between their default values.

With a finite index domain, such as the 8-bit bit-vectors, this reasoning breaks down. Two constant arrays with different defaults can become equal if enough stores overwrite every index. For example, with only two possible indices, the formula

\[ \langle v \rangle\langle i \triangleleft w \rangle\langle j \triangleleft w \rangle \approx \langle w \rangle \wedge v \not\approx w \]

is satisfiable: just choose \(i\) and \(j\) to be the two different indices. In general, a solver has to reason about whether the stores on both sides together cover the entire index domain. That is a counting argument, and it doesn’t fit naturally into existing array procedures.

The figure below illustrates a slightly larger example from the paper, with 2-bit bit-vectors as indices and Booleans as elements:

\[ \langle v \rangle\langle i_1 \triangleleft u_1 \rangle \approx a\langle j_1 \triangleleft u_2 \rangle \wedge a\langle i_2 \triangleleft u_3 \rangle \approx \langle w \rangle\langle j_2 \triangleleft u_4 \rangle \wedge v \not\approx w \]

Over an infinite index domain, this formula is unsatisfiable, since \(\langle v \rangle\) and \(\langle w \rangle\) differ at infinitely many indices. With only four indices, however, the stores can be arranged such that both equalities hold.

Diagram of an interpretation satisfying the formula, with each array drawn as four cells for indices 00, 01, 10 and 11: constant array v holds false everywhere and becomes true, false, false, false after storing true at index 00; array a holds true, false, true, false and becomes true, false, false, false after storing false at index 10, and true, true, true, false after storing true at index 01; constant array w holds true everywhere and becomes true, true, true, false after storing false at index 11. The arrays on both sides of each equality are thus equal.
An interpretation satisfying the formula, with indices 00, 01, 10, 11 from left to right. The four stores (highlighted) update four distinct indices, which makes both sides of each equality agree at every index. Figure 1 of the paper, licensed under CC BY 4.0.

This isn’t just a theoretical gap. Among the solvers we tested, cvc5 and the previous version of Bitwuzla reject these problems outright. Z3 and MathSAT5 accept them, but on our crafted benchmarks they returned wrong answers on dozens of instances, all involving extensionality over finite constant arrays.

Our approach

We first generalize the lemmas-on-demand procedure for extensional arrays from earlier work, which was specific to bit-vectors, to arbitrary index and element sorts. We present it as an abstract calculus that is independent of any particular solver architecture. The only requirement is a procedure that can supply a candidate model for the abstraction. We then extend this calculus with rules for constant arrays, including the finite case, and prove that the resulting calculus, CAEXT, is both refutationally and satisfiability sound.

The key ingredient for the finite case is a cardinality-style constraint. When the procedure detects a conflict between two constant arrays with different default values, it generates a lemma requiring that the indices written on the two sides cover at least as many distinct values as the index domain contains. We encode this with a new operator, \(\mathit{distinct}_N(n, t_1, \ldots, t_k)\), which holds when at least \(n\) of the terms \(t_1, \ldots, t_k\) take pairwise different values. This avoids quantifiers in the lemmas, which keeps them cheap for the underlying solver.

We implemented the procedure in the SMT solver Bitwuzla, replacing its previous array solver. The calculus itself also covers infinite index domains, and we plan to bring it to cvc5 as well.

Results

Constant arrays aren’t in the SMT-LIB benchmark library yet, so we evaluated the new procedure on several sources of problems:

For the full calculus, proofs, and experiments, see the paper or the extended version on arXiv. The artifact is available on Zenodo.