Twee 2.7

Nick Smallbone
Chalmers University of Technology, Sweden

Architecture

Twee 2.7 [Sma21] is a theorem prover for unit equality problems based on unfailing completion [BDP89]. It implements a DISCOUNT loop, where the active set contains rewrite rules (and unorientable equations) and the passive set contains critical pairs. The basic calculus is not goal-directed, but Twee implements a transformation which improves goal direction for many problems.

Twee features ground joinability testing [MN90] and a connectedness test [BD88], which together eliminate many redundant inferences in the presence of unorientable equations. The ground joinability test performs case splits on the order of variables, in the style of [MN90], and discharges individual cases by rewriting modulo a variable ordering.

This year's version adds preliminary support for discovering interesting term patterns during proof search [AJS26].

Strategies

Twee's strategy is simple and it does not tune its heuristics or strategy based on the input problem. The term ordering is always KBO; by default, functions are ordered by number of occurrences and have weight 1. The proof loop repeats the following steps:

Select and normalise the lowest-scored critical pair, and if it is not redundant, add it as a rewrite rule to the active set.
Normalise the active rules with respect to each other.
Normalise the goal with respect to the active rules.

Each critical pair is scored using a weighted sum of the weight of both of its terms. Terms are treated as DAGs when computing weights, i.e., duplicate subterms are only counted once per term.

For CASC, to take advantage of multiple cores, several versions of Twee run in parallel using different parameters (e.g., with the goal-directed transformation on or off).

Implementation

Twee is written in Haskell. Terms are represented as array-based flatterms for efficient unification and matching. Rewriting uses a perfect discrimination tree.

The passive set is represented compactly (12 bytes per critical pair) by only storing the information needed to reconstruct the critical pair, not the critical pair itself. Because of this, Twee can run for an hour or more without exhausting memory.

Twee uses an LCF-style kernel: all rules in the active set come with a certified proof object which traces back to the input axioms. When a conjecture is proved, the proof object is transformed into a human-readable proof. Proof construction does not harm efficiency because the proof kernel is invoked only when a new rule is accepted. In particular, reasoning about the passive set does not invoke the kernel.

Twee can be downloaded as open source from:

https://twee.smallbone.se

Expected Competition Performance

Competing with the top provers.

References

Sma21: Smallbone, N. (2021), Twee: An Equational Theorem Prover (System Description), Platzer, A., Sutcliffe, G., Proceeedings of the 28th International Conference on Automated Deduction, Lecture Notes in Computer Science 12699, Springer.
BDP89: Bachmair L., Dershowitz N., Plaisted D.A. (1989), Completion Without Failure, Ait-Kaci H., Nivat M., Resolution of Equations in Algebraic Structures, pp.1-30, Academic Press.
MN90: Martin U., Nipkow T. (1990), Ordered Rewriting and Confluence, Stickel M.E., 10th International Conference on Automated Deduction (Kaiserslautern, Germany), pp.366-380, Lecture Notes in Computer Science 449, Springer.
BD88: Bachmair L., Dershowitz N. (1988), Critical Pair Criteria for Completion, Journal of Symbolic Computation 6(1), pp.1-18, Elsevier.
AJS26: Axelrod G., Johansson M., Smallbone N. (2026), Twitch: Learning Abstractions for Equational Theorem Proving, Biere, A. et al. 13th International Joint Conference on Automated Reasoning, Lecture Notes in Artificial Intelligence 16688, Springer.