The power of modern SMT solvers comes from the DPLL(T) framework, a sophisticated extension of the core DPLL algorithm used in SAT solving. Instead of operating on simple propositional variables, DPLL(T) integrates a dedicated theory solver (a T-solver) to handle predicates from specific first-order theories. The architecture splits the problem neatly into two parts: a Boolean skeleton and the theory-specific constraints.

The main engine is a Conflict-Driven Clause Learning (CDCL) SAT solver that works on an abstraction of the SMT formula. In this abstraction, each theory atom, like $x+y \leq 5$ or $read(arr, i) = z$, is replaced by a fresh Boolean variable. The SAT solver then proposes a partial assignment of truth values to these variables. This assignment is passed to the T-solver.

The T-solver's job is to check if the set of theory literals corresponding to the SAT solver's assignment is consistent. If it is, the process continues. If it's not, the T-solver generates a conflict clause, a logical explanation for why the assignment is impossible. This clause is learned by the SAT solver, which then backtracks and explores a different part of the search space. This tight integration, where the SAT solver guides the search and the T-solver provides domain-specific semantics, is the core of the framework.

SMT solvers support various theories, each with its own specialized solver. Common examples include:

• Linear Arithmetic: Handles constraints over real or integer variables, like $2x - 3y > 7$.
• Bit-Vectors: Models machine-level integers with fixed-width representations, including operations like bitwise AND, OR, and shifts.
• Arrays: Provides an axiomatization for memory or data structures via read and write operations, governed by the classic McCarthy axioms.
• Uninterpreted Functions (EUF): Treats functions as black boxes, enforcing only the axiom of congruence: if the inputs are equal, the outputs must be equal. $x_1 = y_1 \land ... \land x_n = y_n \implies f(x_1, ..., x_n) = f(y_1, ..., y_n)$.

A crucial optimization is theory propagation. The T-solver can do more than just check for conflicts. Given a partial assignment from the SAT solver, it can deduce new facts. For example, if the T-solver for linear arithmetic receives the assignments $x > 2$ and $x < 4$, and knows that $x$ must be an integer, it can propagate the literal $x=3$ back to the SAT solver. This significantly prunes the search space, as the SAT solver doesn't need to guess a value for $x$.

Real-world verification problems often involve multiple theories at once. A formula might mix array operations with arithmetic indices, like $a[i+1] = a[j] \land i-j=1 \land b[i] \neq b[j]$. To handle this, SMT solvers need a way to combine decision procedures for different theories. The classic method for this is the Nelson-Oppen combination procedure.

The Nelson-Oppen method works for stably-infinite and disjoint theories. Each theory solver receives only the literals relevant to it. The solvers then communicate by propagating any deduced equalities between shared variables. For instance, in the formula $f(x) \neq f(y) \land x = y$, the uninterpreted functions solver gets $f(x) \neq f(y)$ and the arithmetic solver gets $x=y$. The arithmetic solver propagates the equality $x=y$ to a central coordinator, which shares it with the EUF solver. The EUF solver, using its congruence rule, sees that $x=y$ implies $f(x)=f(y)$, which contradicts its known literal $f(x) \neq f(y)$. A conflict is reported.

When using an SMT solver for verification, a key design choice is the encoding strategy: lazy or eager.

Eager encoding translates the entire problem into a single, massive SMT formula upfront. For example, bit-vector operations can be "bit-blasted" into propositional logic. This approach leverages the raw power of the underlying SAT solver but can lead to an explosion in formula size for complex operations or large data paths. The solver has the full context from the beginning.

Lazy encoding, in contrast, abstracts parts of the problem away. The solver starts with a simplified formula and only adds constraints as needed. This is common in software verification, where loops or function calls are unrolled incrementally. The solver adds a new layer of constraints only when a potential counterexample is found to be spurious due to the abstraction.

The choice between them is a performance trade-off. Eager approaches are often used in hardware verification where the system is finite but large. Lazy approaches excel in software verification where paths can be unbounded.

These mechanisms, from the core DPLL(T) loop to theory combination and encoding strategies, form the foundation of modern automated reasoning and system verification.