WorksComputer Science
Apply All, Prove Once: Embedding Parameterized Lemmas in DRAT
Abstract
The deletion-resolution-asymmetric-tautology (DRAT) proof format is widely used to express unsatisfiability proofs of Boolean formulas. Our DRATL format extends DRAT with parameterized lemmas, allowing a single proof to succinctly capture the common case where multiple instances of a pattern occur in a formula, differing in the identities and phases of the variables. Proofs expressed in DRATL can be hierarchical, with the proof of one lemma containing instantiations of others. Our elaborator program expands a DRATL proof containing multiple, nested lemmas into a standard DRAT proof. Most significantly, the elaboration yields compact proofs, where a single sequencing of the proof steps for each lemma covers all of its instantiations. Several case studies demonstrate that lemmas can provide a powerful method to generate short proofs for challenging problems.
Introduction
Proof generation has had a profound impact on the progress and application of Boolean satisfiability (SAT) solvers over the past 25 years. Early developers discovered bugs in their solvers well after deployment, masked by the minimal output generated when the solver states that a formula is unsatisfiable [16, 31]. By requiring the solver to generate a detailed proof of unsatisfiability, such occurrences were readily detected. Even if the solver contains flaws, the successful generation and checking of a proof demonstrates that the particular formula being evaluated is indeed unsatisfiable.
Proof generation became a requirement for solvers in the main track of the annual SAT competition in 2016. Subsequent competitions have had more consistent judging, and the solvers have become noticeably more reliable. It is now rare for a participant to report an incorrect result, even when evaluating formulas never previously tested.
Over time, increasingly powerful proof frameworks have been devised, enabling solvers to handle more challenging problems [11, 20, 21]. A number of formally verified proof checking tools have been developed, providing strong guarantees that a particular execution of the solver can be fully trusted, even if the solver or some of the tools in the chain from the solver to the checker have flaws [11, 12, 19, 26]. The success of proof generation for SAT solvers has inspired similar efforts in other domains, including pseudo-Boolean reasoning [14], quantified Boolean formula (QBF) solvers [25], satisfiability-modulo-theory (SMT) solvers [3, 4], model counters [9, 13], knowledge compilers [7], and hardware model checking [30].
Despite the advances in solvers and proof frameworks, the generated proofs remain totally flat in their structure. They often contain many repetitions of a single pattern of clauses and reasoning steps, differing only in the identities and phases of the variables. As a consequence, the proofs are often very long, containing hundreds of millions of steps. The sheer size of the proofs causes challenges in their generation, storage, and checking. By contrast, a mathematical proof typically has a hierarchical structure, with nested sets of lemmas capturing core concepts. Each lemma need only be proved once, and then it can be applied many times. The hierarchical structure yields more compact proofs, leading to shorter checking times and more manageable storage requirements.
In this paper, we present a framework for adding parameterized lemmas to the widely used deletion resolution-asymmetric-tautology (DRAT) proof framework. Matching the clausal structure of DRAT, each lemma consists of a set of antecedent clauses, a set of consequent clauses, and a proof that the consequent can be derived from the antecedent by a sequence of (augmented) DRAT proof steps. These three components are expressed in terms of a set of parametric variables that do not occur in the input formula. A lemma can be instantiated multiple times, each with a substitution defining a mapping from the parametric variables to problem variables and their complements. An instantiation can also include a qualifier clause, with the negation of this clause defining the context under which the lemma should hold. Lemmas can be nested, with the proof of one lemma instantiating others. Such a structure can dramatically reduce proof size. We have developed the DRATL proof format to describe lemmas, their proofs, and their instantiations by adding a small set of commands to the standard DRAT file format [18].
Two important features of our work enable our approach to fit within existing proof-checking environments and to reduce the effort required for proof checking. First, a proof containing lemmas can be expanded into a standard DRAT proof. Our proof elaborator converts proofs in the DRATL format to ones in the DRAT format. This enables the proofs to be checked using a well-developed tool chain [29], including ones where the final step uses a formally verified checker. Second, the elaboration maintains the property that each lemma is proved only once, regardless of the number of instantiations. The compactness of the proofs carries over to the efficiency with which they can be checked.
The key idea behind our elaborator is captured in the phrase “Apply All, Prove Once.” The proof for a lemma occurs only after all of its instantiations have been identified. The elaborator introduces extension variables for the parametric variables encoding the substitutions for all of the instantiations. It adds a series of proof steps justifying each clause in the lemma antecedent in terms of the existing clauses via the different substitutions. These can include clauses appearing in the proofs of yet-to-be-proved lemmas in which the current lemma will be instantiated. The elaborator then adds the steps of the lemma proof, enabling the proof to be performed for all instantiations simultaneously. The elaborator follows the proof with steps adding instantiations of the consequent clauses.
In this paper we present our lemma framework and the process by which the elaborator can expand lemmas to cover all instantiations such that each proof is carried out only once. We present arguments for the correctness of our elaborator, although it is important to note that the soundness of the generated proof is guaranteed by the formally verified checker at the end of the verification tool chain.
We provide examples where lemmas lead to much more compact proofs than the flat proofs produced by other approaches. Although some of these problems already have known methods for generating compact proofs, our lemma framework provides a general and powerful mechanism for expressing succinct proofs.
In terms of related work, all existing clausal proof frameworks support lemmas consisting of single clauses and without parameters. That is, when a clause is added to the proof, it can be used in multiple inferences. The dependency structure of the proof forms a directed acyclic graph, rather than a tree. This capability is exploited by CDCL SAT solvers, where learned clauses enable the solver to ignore large regions of the solution space. Our ability to have parameters associated with the lemmas takes this capability to a much higher level, increasing their expressive power.
In most proof systems, parameterized lemmas are expressed in first-order logic using quantified variables to serve as the lemma parameters. The lemma can be proved once and then reused via multiple quantifier instantiations. Our approach follows a similar strategy, but without quantification. By first encoding all instantiations with a single set of extension variables, one sequencing of the proof steps suffices.
Background: The DRAT Proof System
Here we present our notation for Boolean formulas and clausal proofs based on the DRAT proof system.
Boolean Formulas. Boolean variable has literals and , the complement of . For literal , its associated variable is denoted . For literal with variable , we let when and when . A clause is a set of literals, representing their disjunction. A clause cannot contain both literals and for any variable . A Boolean formula in conjunctive normal form (CNF) is a set of clauses, representing their conjunction. We extend to clauses and formulas by saying that is the set of all variables associated with the literals in , and is the union of the sets of all variables associated with the clauses in . Moreover, given a set of variables , define . We write to mean . Lastly, given two sets of literals, and , a substitution is a mapping with the additional condition that . Following common convention, we use combinations of set notation and logical connectives in writing clauses and formulas. For example, the formula can also be written as .
For variables , a truth assignment maps every variable in to . It is extended to literals by defining when , and when . Clause is satisfied by when some literal has . Formula is satisfied by when every clause is satisfied by . Formula is satisfiable when it is satisfied by some assignment , and it is unsatisfiable otherwise. The empty clause having no literals is written . It cannot be satisfied. We also use to denote any formula containing the empty clause. In a similar fashion, we use to denote a formula with no clauses; it is trivially satisfied. Two formulas and are equisatisfiable when either both are satisfiable or both are unsatisfiable. Formula entails formula , written , when every satisfying assignment of also satisfies .
Clausal Proofs. Clause is said to be redundant with respect to when the formulas and are equisatisfiable. A proof rule is a pair of the form , or , where is a clause, and “a” denotes clause addition, while “d” denotes clause deletion. Addition rule is applicable for formula when is redundant with respect to . Its application yields the formula . Deletion rule is always applicable. It yields the formula . Observe that addition rules maintain equisatisfiability, but applying a deletion rule can turn an unsatisfiable formula into a satisfiable one.
For formula , a clausal proof consists of a sequence of proof steps , defining a sequence of formulas , where and each formula is the result of applying rule to for . Each addition step must be applicable. That is, for rule , clause must be redundant with respect to . For a clausal proof , and are defined analogously to their formula counterparts.
Proof rule in the sequence is said to be implication preserving when it preserves entailment, i.e., . This can be guaranteed for a deletion rule by prohibiting the deletion of clauses from the original formula . For a proof step adding clause , implication preservation can be guaranteed when .
A clausal proof of unsatisfiability for formula is a proof ending with the proof rule . Any formula having a clausal proof of unsatisfiability must be unsatisfiable.
For formula , a clausal derivation of from formula is a sequence of implication-preserving rules , such that applying these rules yields a formula with . Such a derivation guarantees the entailment .
The formula shown on the left side of Figure 1 will serve as an example in our presentation. A clausal derivation based on that formula is shown on the right. Each clause is numbered, starting with those in the input and continuing with those added by the proof. Each step of the derivation either adds or deletes a clause. The proof adds unit clauses with literals , , and , which we can write as the conjunction .

Figure 1. Boolean Formula and Clausal Derivation Examples
The proof also deletes the intermediate clause . We describe the column labeled “Dependencies” after we have presented the applicable proof rules.
Proof Rules. A unit clause consists of a single literal . It is only satisfied by an assignment having . The process of unit propagation iteratively simplifies a formula, where each iteration 1) identifies a unit clause consisting of literal , 2) removes all clauses containing , and 3) eliminates literal from every clause containing it. This process iterates until a (unique) fixed point is reached. We write when applying unit propagation to formula yields formula . We can see that unit propagation preserves implication. That is, any assignment satisfying will also satisfy when . Conversely, any formula for which must be unsatisfiable.
Clause satisfies the Reverse Unit Propagation (RUP) proof rule [28] with respect to formula , when the following process succeeds:
Formula is augmented by unit clauses consisting of the negated literals of :
Unit propagation yields the empty clause: .
Applying proof rule to when satisfies the RUP proof rule with respect to preserves implication: any assignment satisfying will also satisfy .
Returning to the example of Figure 1, we can now explain the field labeled “Dependencies.” For each clause addition, it shows the IDs of the clauses that reduce to unit clauses when performing unit propagation to validate a RUP clause addition, with the final clause yielding . For the deletion step, the dependency gives the ID of the deleted clause. We can see that the proof is implication preserving, since all additions used the RUP proof rule, and the only deletion was for a proof clause.
Clause satisfies the Resolution Asymmetric Tautology (RAT) proof rule [22] with respect to formula for pivot literal , where , when for every clause such that , the following process succeeds:
Form the set of literals .
Either: (a) contains literals and for some variable , or (b) satisfies the RUP rule with respect to .
Clause satisfies the RAT rule with respect to when it does so for some pivot . Applying proof rule when satisfies the RAT proof rule with respect to maintains equisatisfiability, but it may eliminate assignments that satisfy . That is, there may be an assignment that satisfies , but it fails to satisfy .
The RUP proof rule satisfies a monotonicity property such that if clause satisfies the RUP rule with respect to formula , then it also does so for any formula such that . Such is not the case for the RAT rule, since it can depend on the absence of a clause. As a consequence, the deletion rule is an important capability for DRAT proofs. By deleting some clauses that are no longer needed, it may be possible to perform RAT additions that would otherwise be prohibited.
A clause satisfying the RUP rule with respect to will also satisfy the RAT rule, with any literal serving as the pivot. Given its power, it can be helpful to highlight two special cases where clause satisfies the RAT rule with respect to formula for pivot : RUP: Clause satisfies the RUP rule with respect to
Blocked Clause: Every clause such that also contains a literal , such that .
The RAT rule enables a proof to add variables not found in the original formula . These are known as extension variables, and they provide the DRAT proof system with the capabilities of the powerful extended-resolution proof system [27]. Suppose formula has and step in clausal proof yields formula having . That is, is the set of extension variables in the proof clauses that have been added and not yet deleted. We say that assignment satisfies if there is an assignment that satisfies , such that for all . With this definition, it can be shown that any application of the RAT proof rule having a literal of an extension variable as its pivot preserves implication.
To summarize, a clausal derivation can contain any of the following proof steps:
A deletion step that does not delete a clause in the original formula .
An addition step based on the RUP proof rule.
An addition step based on the RAT proof rule, having the literal of an extension variable as the pivot.
Embedding Lemmas in DRAT
A lemma consists of a set of antecedent clauses , a set of consequent clauses , and a clausal derivation of from . These components are defined over a set of variables disjoint from those in the top-level formula . These variables are partitioned into variables that map, via substitutions, back to literals in and variables internal to the lemma proof. The auxiliary variables enable the lemma proof to employ extended resolution.
The instantiation of a lemma is based on a substitution and a set of qualifying literals , such that limits the context under which the lemma must hold. Our procedure derives the consequent, mapped back to literals in , for multiple instantiations and multiple sets of qualifying literals without needing to apply multiple times.
The Embedding Procedure
Based on the notation we have introduced, we assume that the sets of variables , , and obey the following:
Since is a clausal derivation, we require that any of its addition steps based on the RAT proof rule have pivot literal such that . Let the consequent consist of the clauses . In the following, we add a number of “fresh” variables, each being a previously unused extension variable.
Given applications of the lemma, let be the desired substitution and be the set of qualifying literals for the th instantiation. All of the clauses in must be RUP with respect to . For the construction, introduce fresh variable and fresh variables . For convenience define and . The clause guarded by is defined to be the clause . It behaves exactly like when is set to , and it is satisfied otherwise. Finally, let be the translation of consequent clause for instantiation . The procedure is presented in Figure 3 using the notation to represent the set . We now prove the correctness of the embedding.
Theorem 1 (Embedding Correctness). Suppose that , , , , , and satisfy the conditions above for all in and that all variables introduced are fresh. Then the procedure in Figure 3 is a valid DRAT derivation of .
Proof. To prove the theorem, we show that the additions and deletions of every step are valid and result in the desired formula at the end.
Prefixes The first step adds definitional clauses encoding . Added in order of increasing , these additions are valid via blocked clause addition.
Bindings This step adds two clauses for each problem variable and application. Fix an instantiation and a variable . The clause is RAT on . If , then it is added by blocked clause addition. If , every clause in the formula which contains the complement, , contains for some . Thus, the resulting set of literals in the RAT check will have both and . When negated, these units propagate down the chain and result in a conflict, satisfying the RAT condition. For the opposing clause, , the argument is the same except that the previously added clause contains and therefore gives RAT one additional check. The check succeeds because the resulting set of literals contains both and .
Antecedent The clauses for all are added via blocked clause addition. The clauses of the second set are all RAT on . For every , the only clauses that are relevant to the RAT check for are the guarded antecedent clauses. For each antecedent clause , the RAT condition requires that is RUP. Negating this clause results in the two units and establishing the bindings for . The bindings, along with the units , establish the units . Along with the units , this results in a conflict as is RUP from by assumption.
| Step | Clauses or operation | Rule |
| 1. Prefixes | For and such that : , | Blocked on |
| , for each | Blocked on | |
| 2. Bindings | For , increasing, and : | RAT on |
| RAT on | ||
| 3. Antecedent | With fresh : for all | Blocked on |
| for all | RAT on | |
| 4. Prove | For each step : if | RAT/RUP as in |
| Delete if | Deletion | |
| 5. Prefix Units | For : | RUP |
| 6. Consequent | For every and : | RUP |
| 7. Cleanup | Delete the added clauses other than the consequent preserving every clause of . | Deletion |
Table 3. The seven-step procedure to embed a lemma into DRAT. Tautologies are omitted.
Prove For each step of , if it is an addition , then is redundant via the same mechanism as in . There are two cases: is either RAT on an auxiliary variable or RUP. If it is RAT on an auxiliary variable, since that variable only occurs in , it is still RAT on that auxiliary variable. If it is RUP, on the other hand, then the addition of is RUP. The unit activates the antecedent clauses and the earlier guarded steps of , so is RUP exactly as it is in . If it is a deletion , then the clause is deleted.
Prefix Units Inductively, assume that all units through have been derived. Choose such that . Negating the unit propagates up the prefix chain established in step 1, yielding the unit . Since , is already derived, and therefore the bindings from step 2 activate, yielding for . Moreover, since is already derived, by the prefix clauses in step 1, negating also derives for some with . Since , the negation of provides the units in , which, along with and propagate . Finally, recognizing that and that the bindings are active, the units and conflict with the th consequent of step 4, .
Consequent After establishing all of the prefix units, the consequent clauses for and all follow immediately from the prefix clauses in the first step. Similarly, all of the are valid since negating each clause yields both and . The latter, along with the prefix units, propagates , which activates the guarded consequent clauses of step 4. In particular, and the active bindings conflict with the now active consequent .
Cleanup Clause deletions are unconditional in DRAT, so we can freely delete all of the scaffolding, yielding a DRAT derivation of as desired.
Embedding Example
As an example of the embedding, consider the formula consisting of the conjunction of the four blocks in Figure 2. These are three copies of the formula in Figure 1, replacing with , , and , and with blocks and under the qualifiers and respectively. It is augmented with a conflicting clause which makes the formula unsatisfiable. Our lemma will be the derivation of units , , and as in Figure 1. Once proven, we can then apply this lemma to the variables in each block, with the applications to blocks and under qualification, to derive units , , and , obtaining a contradiction.
Figure 2. An unsatisfiable formula. Each block, conditioned on the units from the previous, derives the three unit literals corresponding to , , and which falsify the final clause.
Prefixes The first step in the embedding procedure adds prefix clauses. Since there are applications, we need sets of prefix variables, each for deriving consequent clauses. To do this, the procedure adds clauses:
Variable is equivalent to the conjunction of the first instantiated consequent clauses. This gives the procedure access to “selectors” for application of the form which intuitively mean “we know the consequents of instantiations through are valid, but we don’t know about instantiation .”
Bindings The key insight of this construction is the introduction of bindings conditional on selectors. Throughout the proof, we want to maintain the invariant that lemma variables are bound to the earliest application that has not been checked. To do this, step 2 binds the parameters conditionally on the selectors. Antecedent Next, the procedure adds the lemma’s antecedent clauses. Since the previous step introduced the bindings, the antecedent clauses are neither RUP nor RAT, in general. Thus, step 3 adds guarded versions that can be activated later.
| ’s bindings |
Table 10a.
| ’s bindings |
Table 10b.
| ’s bindings |
Table 10c.
| Guarded Antecedent |
Table 10d.
| Activators |
Table 10e.
Prove Once Step 4 proves the lemma on the variables. It simply replays the proof, guarded by as follows:
| Proof Replay |
| delete |
Table 10f.
Prefix Units At this point, the prefix units follow in order, .
Consequent All that is left to do is derive the consequent clauses by reading them off:
| ’s consequent | ’s consequent | ’s consequent |
Table 10g.
With the consequents derived, the empty clause is RUP, showing that the formula is unsatisfiable.
proof ::= step*
step ::= clause add a clause (DRAT)
| d clause delete a clause (DRAT)
| lemma declare and prove a lemma
| apply apply a lemma
lemma ::= L id n x a m n parameters, x auxiliary variables
clause^a a antecedent clauses, over variables 1, ..., n
clause^m m consequent clauses, over variables 1, ..., n
step* proof of the lemma, over variables 1, ..., n + x
e id
apply ::= l id lit^n 0 [ lit* 0 ] arguments, optional qualifier
clause ::= lit* 0
The DRATL Format for Lemma-Based Proofs
DRATL extends DRAT to enable proofs structured as hierarchies of lemmas. DRATL adds two extensions to the DRAT format: lemma definitions and lemma instantiations. The full grammar can be seen in Figure 4. An example DRATL proof, replicating the one from § 3, is shown in Figure 5. The new components are as follows:

Figure 4. Grammar for the DRATL format
Lemma Definition A lemma is defined by first giving a header with a user-specified, unique numeric ID, as well as the number of parameters, auxiliary variables, antecedent clauses, and consequent clauses. Then the antecedent and consequent clauses are listed, followed by the proof of the consequent from the antecedent.
Lemma Application An application consists of a lemma ID and one literal per parameter, where the literal in position specifies the value of . The instantiation concludes with an optional list of literals forming the qualifying literals .
Elaboration
Our elaborator translates a DRATL proof into a DRAT proof following a variation of the procedure in Figure 3. All of the additional complexity arises from nested lemmas, where a lemma is instantiated as part of the proof of another lemma . In this section, we define what it means for a DRATL proof to be semantically valid, describe how we elaborate such files, and prove that the elaboration results in a valid DRAT proof.
A scope is defined to be either the top-level proof or the proof of a lemma. A scope’s formula is the set of clauses relative to which the proof is checked. At the top level, it is the original formula and within a lemma it is the antecedent. A scope’s proof and consequent are defined similarly. A scope’s proof can be divided into two parts: the preamble, consisting of all steps before any lemma is applied, and the body, consisting of the remainder of the proof steps. For a DRATL proof to be valid, we require the following:
For each lemma application, the conditions described in Figure 3 are met with respect to its enclosing scope’s formula and preamble.
| Action | Clause | Comment |
| L | 1 4 0 7 3 | 4 parameters, 0 auxiliaries, 7 antecedents, 3 consequents |
| antecedent | ||
| consequent | ||
| a | proof of the consequent | |
| a | ||
| d | ||
| a | ||
| a | ||
| e | 1 | end of lemma 1 |
| l | consequent | |
| l | consequent | |
| l | consequent | |
| a | RUP from the consequents and the conflicting clause |
Table 5. The DRATL proof of the formula in Figure 2 with the lemma of Figure 1. A qualifier is shown in brackets after the arguments. The presentation is stylized, using literal symbols instead of numbers.
If lemma is used in the proof of lemma , lemma is not used, directly or indirectly, in the proof of lemma .
In all scopes, the RAT steps in the proof’s body must be valid with respect to all instantiated consequents of all lemma applications in the scope.
Deletion steps are not allowed to delete instantiated consequent clauses.
Every scope’s proof is a valid derivation of its consequent from its formula when lemma applications, given by instantiation and qualifier , are interpreted as the instantiated consequent for .
Item 3 is required because DRAT is non-monotonic. While it appears restrictive, it did not hinder our ability to write compact DRATL proofs. Specifically, we found that only using RAT steps in a proof’s preamble was sufficiently expressive. Item 4 is required because lifting all consequent clauses to the top exposes them to premature deletion.
Given a valid DRATL proof, the elaboration algorithm follows a simple procedure. First, the elaborator emits the top level’s preamble. When the first lemma application is encountered, we topologically sort the lemmas by application. That is, if lemma is used in the proof of lemma , then comes before in this ordering. Then, it applies the steps of Figure 3 in two phases. The elaborator’s setup phase applies steps 1 through the preambles of step 4 on each lemma in reverse topological order. Then the conclusion phase applies the bodies of the proofs in step 4, as well as steps 5 through 7, on each lemma in topological order. Moreover, when a lemma is used in the proof of lemma , it is implicitly qualified by , the negated guard literal for lemma . Finally, the body of the top level’s proof is replayed.
This construction uses two phases to satisfy opposing dependency orders; a single one does not suffice. If lemma is used in the proof of lemma , then an instantiation of lemma , namely the one which is used in lemma , has antecedent clauses that are RUP from the antecedent and preamble of lemma . This would seem to require that lemma be elaborated before lemma . On the other hand, the consequent for lemma depends on the instantiated consequent from lemma . This would seem to require that lemma be elaborated before lemma . The two-phase approach resolves this tension. We now prove the correctness of this approach.
Theorem 2 (Elaboration Correctness). The elaboration of a valid DRATL proof results in a valid DRAT proof.
Proof. To show that the nested elaboration algorithm results in a valid DRAT proof, we argue that each of the justifications from Figure 3 still applies.
Fix a lemma which may be applied within lemma . Since the prefix, problem, auxiliary, and variables are disjoint for each lemma, steps 1 and 2 work as they did in Theorem 1. The only complexity in step 3 is due to the RAT check on possibly depending on the antecedent and preamble for lemma . By the reverse topological ordering of the setup phase, the antecedent and preamble for lemma have already been emitted, but their clauses are guarded by . However, during elaboration, the application of lemma inside lemma is implicitly qualified by , allowing the argument to follow exactly as in Theorem 1. The last step of the setup phase, the preamble, has no lemma instantiations, and is the same as before.
In the conclusion phase of lemma , the only clauses remaining that mention the variables of are from its own elaboration and the instantiated consequents of the lemmas applied in its proof. This is because the topological ordering of the conclusion phase guarantees that all lemmas used in the proof of lemma have already been elaborated and undergone cleanup, leaving only their instantiated consequents. Due to the restriction on deleting instantiated consequents, every clause available at a given step of the DRATL proof for lemma is also available, in guarded form, at the corresponding step of the elaborated proof. In this manner, RUP steps remain valid by monotonicity, while RAT steps remain valid by Item 3, allowing the body to be replayed. Steps 5 through 7 involve only the clauses of lemma and are therefore unchanged.
After all lemmas have been elaborated, at the top level, the remaining proof body is valid with respect to all of the instantiated consequents and is otherwise a valid DRAT proof. Therefore, the resulting elaborated DRAT proof is valid.
Experimental Results
Three case studies probe the approach from different sides. Using lemmas for the mutilated chessboard enables an effective strategy based on extended resolution to scale even further by reducing the overhead of adding formulas implementing modular arithmetic. On the queen graphs, a single lemma enables reducing many copies of a subformula describing a clique. Lemmas for the Mycielski graph follow its inductive structure, enabling a factorial reduction in size.
Mutilated Chessboard
The mutilated chessboard problem has long served as a challenge for automated reasoning tools [23]. The problem considers an chessboard, with the corners on the upper left and the lower right removed. It attempts to tile the board with dominoes, with each domino covering two squares. For even values of , both removed squares are white. Since each domino covers one white and one black square, no tiling is possible.
Labeling the squares of a chessboard as having rows 1 (upper) to (lower) and columns 1 (left) to (right), the standard Boolean encoding of the problem introduces two sets of variables describing the placement of horizontal and vertical dominoes, respectively. Variable for and encodes whether a domino is placed horizontally on row spanning columns and . Variable for and encodes whether a domino is placed vertically on column spanning rows and . The upper-left and lower-right corners are omitted via unit clauses , , , and . For every other square, there are 2–4 variables describing possible placements of dominoes on that square. For each square, 2–7 clauses constrain exactly one of these to be set to 1. It can be shown that any resolution proof of unsatisfiability for this encoding must be of exponential size [1]. The plot labeled kissat in Figure 6 demonstrates how difficult this problem is for CDCL solvers, showing the number of proof clauses as a function of . Even for , kissat generates a proof with over 65 million clauses.

Figure 6. Total number of clauses in formula and proofs of mutilated chessboard problems. Historical methods were limited to . Direct generation with mod-3 propagation scales beyond . Using lemmas (strips or tiled) greatly decreases the proof size for large values of , even becoming more compact than the formulas themselves.
Others have found ways to overcome exponential performance on this problem, such as by applying symmetry reduction via the propagation-redundancy (PR) proof system [20]. The PR proofs can then be translated into DRAT, with polynomial but significant overhead. The plots in Figure 6 labeled “PR proof” and “PR converted to DRAT” show their published results, reaching . Although it can be seen that the PR proofs, and their translation to DRAT, greatly improve on kissat, other approaches generally outperform the DRAT versions, and the results reported here even improve on the PR proof sizes.
More recent work using proof-generating binary decision diagram (BDD) packages demonstrated success for up to using two different approaches. One used a strategy inspired by symbolic model checking to scan from the left side of the board to the right, tracking the possible sets of assignments to the variables for as ranges from 1 to [6]. Their published results are shown in the plot “BDD, Column scan.” The second converted the problem into one involving pseudo-Boolean constraints, encoding the mismatch between the total number of white and black squares. They observed that the arithmetic could be computed modulo-3 and still capture the mismatch [5]. Their results are shown in the plot “BDD, Mod-3 equations.”
Rather than using BDDs as an intermediate step, we can combine the ideas of column scanning and mod-3 arithmetic directly into an extended resolution proof. That is, we set up formulas encoding mod-3 counters summing for , where . For , the sum will be 2. Each successive column will preserve the sum, and then a conflict will arise at the final column. The plot labeled “Mod-3 propagation, Flat” shows that this approach scales far better than any previous method. Whereas all the previously cited methods have DRAT proofs exceeding one million clauses for , the direct encoding reaches before hitting that limit.
Lemmas allow us to push the scaling of modular arithmetic even further, by reducing the number of clauses added to encode and reason about mod-3 counters. For a width where is a multiple of , we can divide the board into the left column, a series of strips columns wide, and the right column. A single lemma suffices to show that the count at the left boundary of a strip is preserved when scanning to its right boundary. By setting to around , we get balance between the number of mod-3 counters that connect the successive strips and the number of counters within the lemma between the columns of a single strip. When there are no suitable divisors of , we may need to add a second lemma for a width . These results are shown as the plot “Mod-3 propagation, Strips” in Figure 6. For large values of , we can see that the use of lemmas substantially reduces the proof size. These proofs scale to before reaching one million clauses. In keeping with the DRATL requirements, all of the mod-3 counters must be introduced as part of the preamble for the top-level proof. Remarkably, for large values of , these proofs become smaller than the input formula, with the crossover occurring around .
As a final optimization, we can subdivide the strips of width into columns of height and encode summations of both sets of variables and . As before, we may need to add an extra lemma for a smaller width, as well as lemmas for smaller heights. The exact setting of the parameters requires balancing many considerations, but we were able to train a regression model to select the parameters. These results are shown as the plot “Mod-3 propagation, Tiled” in Figure 6. As can be seen, it improves on the strips approach only for large values of , reaching one million clauses with . For , these proofs are smaller than the original input formula.
As these results show, mod-3 propagation alone enables compact proofs of the mutilated chessboard problem, but the use of lemmas greatly reduces the amount of overhead. At , the tiled proofs are over smaller than the flat ones.
The scaling of these proofs presents a challenge for checking with our verification toolchain, consisting of DRAT-TRIM [18], a tool for expanding a DRAT proof into a more detailed form, followed by the formally verified CAKE_LPR checker [26]. We can only validate the flat proofs for up to and the strips and tiled proofs for up to . The runtimes for DRAT-TRIM become impractical beyond that point, exceeding 30,000 seconds. Enabling more efficient checking is a clear priority for future work.
Queen Graph Coloring
The queen graph has the squares of an board as vertices, adjacent when a queen moves between them. is not -colorable for . The formula, even when extended with symmetry breaking (fixing the diagonal), is hard for CDCL solvers. Solvers cannot easily infer surjectivity on the maximum cliques: in an -coloring, every row, column, and long diagonal uses every color. This is a pigeonhole-style consequence with no short resolution proof. Deriving these clique hints for clique and color collapses the instances. For , is conjectured to be -colorable. Colorings are known for [10]. Clique hints also boost performance on satisfiable formulas.
We derive the clique hints using a single lemma with parameters representing the assignment of colors to vertices. Its antecedent clauses require each vertex to have at least one color and prohibit two vertices from sharing a color. Its consequent clauses state that every color occurs in the clique. The lemma uses the chain derivation of Grosof, Zhang, and Heule [17], with steps and all newly introduced variables treated as auxiliaries. We apply the lemma to each of the maximum cliques: the rows, columns, and two long diagonals. In each application, the instantiated antecedent consists of input clauses. Deriving all hints together allows them to share the same parameter bindings. An alternative lemma deriving a single clique hint would also require parameters. Applying it separately for each color would increase the number of binding clauses by a factor of .
The pipeline verifies end to end from the plain formula, within the substitution redundancy (SR) proof system [8], a generalization of DRAT. First, for symmetry breaking, SR steps fix the main diagonal to different colors, each witnessed by a color swap in the style of orbital fixing [2]. Second, the clique hints are derived via our lemma approach and turned into DRAT using the elaborator. Finally, CaDiCaL (version 3.0) produces that last part of the proof by solving the formula extended with the symmetry-breaking unit clauses and the clique hints. The concatenation is a single DSR proof of the original formula, checked by dsr-trim, whose annotated output is then checked by srcheck, the formally verified checker of [11], in under a dozen seconds per instance. With symmetry breaking, but without the hints, CaDiCaL takes 5.7 seconds at and 801 seconds at , and does not solve . With symmetry breaking and clique hints, all three instances are refuted in seconds (Table 1).
| clauses + sym. units | time w/o hints | lemma appl. | clique hints | time w/ hints | flat total | elaborated | end-to-end proof | check | |
| 8 | 7,680 + 8 | 5.7 s | 18 | 144 | 0.01 s | 134,352 | 5,126 | 8,017 | 0.1 s |
| 9 | 12,501 + 9 | 801 s | 20 | 180 | 0.26 s | 247,320 | 7,198 | 29,147 | 0.6 s |
| 10 | 19,300 + 10 | > 3600 s | 22 | 220 | 12.5 s | 427,240 | 9,773 | 403,613 | 11 s |
Table 1. Queen graphs: one hint lemma per size, proved once and applied to all maximum cliques. The first three columns show the size of the board and the number of clauses + symmetry-breaking units and the CDCL runtime without clique hints, respectively. The fourth column shows the number of lemma applications, followed by the number of added clique hints (consequent clauses). The last four columns show the size of deriving every hint by replaying the derivation once per hint (no lemmas), the sizes of the elaborated lemma proof and of the end-to-end proof, and the time to check the latter. The instance was not solved within an hour.
Mycielski Graphs
Mycielski’s construction takes a graph and returns a graph with the same clique number and chromatic number one higher [24]. Starting from , the iterates are triangle-free with . Refuting the -coloring of is a classic hard family. The textbook proof is an induction: consists of , a shadow vertex per vertex with adjacent to the neighbors of , and an additional vertex adjacent to all shadows. If has color , every shadow avoids , so recoloring each -colored to its shadow’s color turns a -coloring of into a -coloring of , which does not exist by the same argument one level down.
This induction is a tower of lemmas, and it exercises every distinctive feature of DRATL at once. Lemma has the coloring constraints of as its antecedent clauses and a single empty consequent: it states that the -coloring of is contradictory, and an application under qualifier concludes : a refutation made reusable by the qualifier alone. The proof of defines the recolorings and derives their coloring constraints (all RUP), then applies to each, under the qualifier ; each application concludes , and the empty clause follows from the at-least-one clause for . The lemmas require no bookkeeping parameters: an application inside a lemma’s proof is automatically qualified by that proof’s activation guard, so conclusions carry exactly one caller guard at any nesting depth.
Nesting allows a single proof of each lemma to serve all of its instantiations. Without sharing, each application of requires a separate copy of its proof, including the applications of . Recursively expanding these applications yields a proof whose size grows like , while the nested proof grows linearly in the formula size up to a factor (Table 2). Elaboration adds only about five percent for the largest instance, preserving the sharing expressed in the DRATL proof.
| graph | clauses | lemmas | DRATL | elaborated | flat | check |
| 71 | 2 | 385 | 463 | 463 | 0.03 s | |
| 307 | 3 | 2,324 | 2,680 | 3,761 | 0.05 s | |
| 1,227 | 4 | 11,925 | 13,221 | 28,171 | 0.26 s | |
| 4,625 | 5 | 55,048 | 59,190 | 211,033 | 2.8 s | |
| 16,711 | 6 | 236,189 | 248,343 | 1,653,905 | 32 s |
Table 2. Mycielski graphs: the nested lemma tower. The first three columns show the graph, number of clauses and number of lemmas, respectively. “DRATL” shows the lines of the proof as written, “elaborated” and “flat” the additions of the expanded proof and of the expansion without lemma sharing; “check” is the total checking time: dsr-trim on the elaborated proof, then the formally verified srcheck on its annotated output.
Conclusions
This paper demonstrates that hierarchy can be introduced into a clausal proof framework to yield more compact proofs than the flat proofs generated by existing solvers and preprocessors. The ability to efficiently elaborate hierarchical proofs into flat ones avoids the need for new proof frameworks or checking tools. Our results demonstrate the utility of this approach for several highly structured challenge problems.
A clear next step in this effort is to have the elaborator also generate the full proof details, yielding a proof in the LRAT extension of the DRAT format [12]. Such a capability should be straightforward — the lemma proofs are fully self-contained, and deriving the hints for the steps outlined in Figure 3 is mostly a matter of bookkeeping. This would enable a direct interface to multiple formally verified proof checkers [11, 19, 26].
The method of elaborating lemmas described in Figure 3 could also be incorporated into other proof systems that allow the introduction of extension variables. These include clausal proof systems that generalize DRAT [11, 20, 21], as well as the VeriPB proof framework for pseudo-Boolean reasoning [15]. As with the RAT rule, these other proof systems include non-monotonic proof rules. Some limitations may need to be imposed on how these rules are used within the proof of a lemma to ensure that no conflict arises with an instantiation.
Another direction for research is to incorporate lemma extraction into a CDCL SAT solver, either as part of a preprocessing or an inprocessing step. The solver could identify multiple instances of a common clausal pattern and introduce a lemma creating a more useful representation of that pattern, similar to our processing of clique constraints in the Queen graph coloring problem.
References
References
- [1]Aleknovich, M.: Mutilated chessboard problem is exponentially hard for resolution. Theoretical Computer Science 310(1–3), 513–525 (2004)DOI
- [2]Anders, M., Codel, C., Heule, M.J.H.: Simplify, order, break, repeat. In: Theory and Applications of Satisfiability Testing (SAT). LIPIcs (2026)DOI
- [3]Armand, M., Faure, G., Grégoire, B., Keller, C., Théry, L., Werner, B.: A modular integration of SAT/SMT solvers to Coq through proof witnesses. In: Certified Programs and Proofs. LNCS, vol. 7086 (2011)DOI
- [4]Barrett, C., de Moura, L., Fontaine, P.: Proofs in satisfiability modulo theories. In: Paleo, B.W., Dehayе, D. (eds.) All about Proofs, Proofs for All, Mathematical Logic and Foundations, vol. 55. Cambridge University Press (2015)
- [5]Bryant, R.E., Biere, A., Heule, M.J.H.: Clausal proofs for pseudo-Boolean reasoning. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS). LNCS, vol. 12651, pp. 76–93 (2022)DOI
- [6]Bryant, R.E., Heule, M.J.H.: Generating extended resolution proofs with a BDD-based SAT solver. ACM Transactions on Computational Logic 24(4), 1–28 (2023)
- [7]Bryant, R.E., Nawrocki, W., Avigad, J., Heule, M.J.H.: Certified knowledge compilation with application to formally verified model counting. Journal of Artificial Intelligence Research 82, 2057–2099 (2025)arxiv.org/abs/2501.12906
- [8]Buss, S., Thapen, N.: DRAT proofs, propagation redundancy, and extended resolution. In: Theory and Applications of Satisfiability Testing (SAT). LNCS, vol. 11628 (2019)DOI
- [9]Capelli, F., Lagniez, J.M., Marquis, P.: Certifying top-down decision-DNNF compilers. In: AAAI Conference on Artificial Intelligence (2021)
- [10]Chvátal, V.: Colouring the queen graphs. https://users.encs.concordia.ca/~chvatal/queengraphs.html, accessed 16 October 2026
- [11]Codel, C.R., Avigad, J., Heule, M.J.H.: Verified substitution redundancy checking. In: Formal Methods in Computer-Aided Design (FMCAD). pp. 186–196 (2024)DOI
- [12]Cruz-Filipe, L., Heule, M.J.H., Hunt, W.A., Kaufmann, M., Schneider-Kamp, P.: Efficient certified RAT verification. In: Conference on Automated Deduction (CADE). LNCS, vol. 10395, pp. 220–236 (2017)
- [13]Fichte, J.K., Hecher, M., Roland, V.: Proofs for propositional model counting. In: Theory and Applications of Satisfiability Testing (SAT). Schloss Dagstuhl (2022)
- [14]Gocht, S., McCreesh, C., Nordström, J.: VeriPB: The easy way to make your combinatorial search algorithm trustworthy. In: From Constraint Programming to Trustworthy AI (2020)
- [15]Gocht, S., Nordström, J.: Certifying parity reasoning efficiently using pseudo-Boolean proofs. In: AAAI Conference on Artificial Intelligence. pp. 3768–3777 (2021)
- [16]Goldberg, E.I., Novikov, Y.: Verification of proofs of unsatisfiability for CNF formulas. In: Design, Automation and Test in Europe (DATE). pp. 886–891 (2003)
- [17]Grosof, I., Zhang, N., Heule, M.J.H.: Towards the shortest DRAT proof of the pigeonhole principle. In: Proceedings of Pragmatics of SAT (PoS) (2022)arxiv.org/abs/2207.11284
- [18]Heule, M.J.H.: The DRAT format and DRAT-trim checker. CoRR abs/160.06229 (2016)arxiv.org/abs/1610.06229
- [19]Heule, M.J.H., Hunt, W.A., Kaufmann, M., Wetzler, N.D.: Efficient, verified checking of propositional proofs. In: Interactive Theorem Proving. LNCS, vol. 10499, pp. 269–284 (2017)DOI
- [20]Heule, M.J.H., Kiesl, B., Biere, A.: Clausal proofs of mutilated chessboards. In: NASA Formal Methods (NFM). LNCS, vol. 11460, pp. 204–210 (2019)DOI
- [21]Heule, M.J.H., Kiesl, B., Biere, A.: Strong extension-free proof systems. Journal of Automated Reasoning 64, 533–554 (2019)DOI
- [22]Järvisalo, M., Heule, M.J.H., Biere, A.: Inprocessing rules. In: International Joint Conference on Automated Reasoning (IJCAR). LNCS, vol. 7364, pp. 355–370 (2012)
- [23]McCarthy, J.: A tough nut for proof procedures. Tech. Rep. Memo 16, Stanford Artificial Intelligence Project (1964)
- [24]Mycielski, J.: Sur le coloriage des graphes. Colloquium Mathematicum 3, 161–162 (1955)DOI
- [25]Niemetz, A., Preiner, M., Lonsing, F., Seidl, M., Biere, A.: Resolution-based certificate extraction for QBF. In: Theory and Applications of Satisfiability Testing (SAT). LNCS, vol. 7317, pp. 430–435 (2012)DOI
- [26]Tan, Y.K., Heule, M.J.H., Myreen, M.O.: Verified propagation redundancy and compositional UNSAT checking in CakeML. International Journal of Software Tools for Technology Transfer 25, 167–184 (2023)DOI
- [27]Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Automation of Reasoning: 2: Classical Papers on Computational Logic 1967–1970. pp. 466–483. Springer (1983)
- [28]Van Gelder, A.: Verifying RUP proofs of propositional unsatisfiability. In: Artificial Intelligence and Mathematics (ISAIM) (2008)
- [29]Wetzler, N.D., Heule, M.J.H., Hunt Jr., W.A.: DRAT-trim: Efficient checking and trimming using expressive clausal proofs. In: Theory and Applications of Satisfiability Testing (SAT). LNCS, vol. 8561, pp. 422–429 (2014)DOI
- [30]Yu, E., Biere, A., Heljanko, K.: Progress in certifying hardware model checking results. In: Computer Aided Verification (CAV). LNCS, vol. 12760, pp. 363–386 (2021)DOI
- [31]Zhang, L., Malik, S.: Validating SAT solvers using an independent resolution-based checker: Practical implementations and other applications. In: Design, Automation and Test in Europe (DATE). pp. 880–885 (2003)
