# Unique Assembly Verification in Two-Handed Self-Assembly††thanks: This
research was supported in part by National Science Foundation Grant
CCF-1817602.

David Caballero  Timothy Gomez  Robert Schweller  Tim Wylie

###### Abstract

One of the most fundamental and well-studied problems in Tile Self-Assembly is
the Unique Assembly Verification (UAV) problem. This algorithmic problem asks
whether a given tile system uniquely assembles a specific assembly. The
complexity of this problem in the 2-Handed Assembly Model (2HAM) at a constant
temperature is a long-standing open problem since the model was introduced.
Previously, only membership in the class coNP was known and that the problem
is in P if the temperature is one ($\tau=1$). The problem is known to be hard
for many generalizations of the model, such as allowing one step into the
third dimension or allowing the temperature of the system to be a variable,
but the most fundamental version has remained open.

In this paper, we prove the UAV problem in the 2HAM is hard even with a small
constant temperature ($\tau=2$), and finally answer the complexity of this
problem (open since 2013). Further, this result proves that UAV in the staged
self-assembly model is coNP-complete with a single bin and stage (open since
2007), and that UAV in the q-tile model is also coNP-complete (open since
2004). We reduce from Monotone Planar 3-SAT with Neighboring Variable Pairs, a
special case of 3SAT recently proven to be NP-hard. We accompany this
reduction with a positive result showing that UAV is solvable in polynomial
time with the promise that the given target assembly will have a tree-shaped
bond graph, i.e., contains no cycles. We provide a $\mathcal{O}(n^{5})$
algorithm for UAV on tree-bonded assemblies when the temperature is fixed to
$2$, and a $\mathcal{O}(n^{5}\log\tau)$ time algorithm when the temperature is
part of the input.

Department of Computer Science

University of Texas Rio Grande Valley

Edinburg, TX 78539-2999, USA

{david.caballero01, timothy.gomez01, robert.schweller,
<EMAIL_ADDRESS>
##  1 Introduction

Since the inception of tile self-assembly [27], one of the most important
algorithmic questions has been determining if a given tile system uniquely
self-assembles into a specific assembly structure. This basic algorithmic
question, termed the Unique Assembly Verification (UAV) problem, is
fundamental for efficiently checking if a designed tile system acts as
intended, and is tantamount to the design of an efficient simulator for a tile
self-assembly model. Thus, UAV has been a central question for every self-
assembly model.

Although many different self-assembly models have been proposed in order to
simulate different laboratory or experimental setups, two premiere models have
emerged as the primary foci of study. First, is the seeded Abstract Tile
Assembly Model (aTAM) [27], in which singleton tiles attach one by one to a
growing seed if sufficient bonding strength exists based on glue types of
attaching tiles. This model has had many foundational results in recent years
showing the limits related to intrinsic universality and program-size
complexity [20, 19]. The second model is the hierarchical Two-Handed Tile
Assembly Model (2HAM) [8], where any two producible assemblies may be combined
(one in each of two hands) to create a new producible assembly provided there
is sufficient bonding strength between the two pieces. Many foundational
results that are known for the aTAM are still open for the 2HAM.

The 2HAM has been shown to be more powerful than the aTAM in its ability to
build infinite fractal patterns [10, 17], its program-size efficiency for
finite shapes [7], and its running-time efficiency for the self-assembly of
finite shapes [11]. While the aTAM has a polynomial time solution to the UAV
problem [1], allowing for the production of efficient simulators [28, 21, 16],
the complexity of UAV in the 2HAM has remained a long-standing open problem in
the field. The 2HAM appeared formally in 2013 [8], but was essentially defined
in staged self-assembly [12] (2007), and a seeded version of the 2HAM appears
as the _multiple tile_ model in [3] (2004). UAV has been open for all of these
models, and our coNP-complete result for UAV in the 2HAM proves that UAV with
a single bin and single stage in the staged model is coNP-complete, and that
UAV in the multiple tile model is also coNP-complete with polynomial-sized
pieces, thus answering both of these long-standing open questions. See [22,
29, 14, 30] for surveys and applications of self-assembly theory.

#### Previous work on UAV.

A number of results have pushed closer to resolving the complexity of UAV in
the 2HAM. One of the first results showed that the simpler problem of
determining if a given assembly was at least produced (i.e., built but
possibly along with other different assemblies) is polynomial time solvable
[15], which serves as a key step in showing that UAV resides within the class
coNP. Another result augmented the basic 2HAM model to 3 dimensions and showed
coNP-hardness for the 3D 2HAM [8]. A recent result focused on 2D, but allowed
the temperature threshold, a parameter that determines how much glue strength
is required for assemblies to stick together, to be a variable input to the
UAV problem (as opposed to a fixed constant value), and showed coNP-
completeness in this scenario [25].

Other approaches considered the allowance of initial assemblies consisting of
small prebuilt assemblies, as opposed to only initial singleton tiles, and
showed UAV becomes coNP${}^{\text{NP}}$-complete with this extension [5].
Alternately, the inclusion of a negative force glue, even without detachments,
has also been shown to imply coNP-completeness in the aTAM [9]. Another
generalization of the 2HAM allows for up to $k$ hands to create new
assemblies, instead of just two, causing the problem to become either coNP-
complete or PSPACE-complete, depending on the encoding of the variable $k$
[4]. An even more powerful generalization of the 2HAM is the _staged_ model
[12], in which multiple distinct stages of self-assembly are considered.
Within the staged model, UAV becomes coNP${}^{\text{NP}}$-hard after 3 stages,
and PSPACE-complete in general [26, 6]. Thus, for nearly every way in which
the 2HAM has been extended, a corresponding hardness reduction has been found.
Yet, the original question of UAV in the 2HAM has remained open.

Shape | Dimensions | Temperature | Complexity | Reference
---|---|---|---|---
General | $2$ | $1$ | $\mathcal{O}(|A||T|\log|T|)$ | [15]
General | $3$ | $2$ | coNP-complete | [8]
General | $2$ | $\tau$ | coNP-complete | [25]
General | 2 | 2 | coNP-complete | Thm. 3.4
Tree | 2 | $\tau$ | $\mathcal{O}(|A|^{5}\log\tau)$ | Thm. 4.5
Table 1: Known Results for the Unique Assembly Verification Problem in the
2HAM and the results presented in this paper. $|A|$ is the size of the target
assembly, $\tau$ is the temperature of the system, and $|T|$ is the number of
tile types in the system. Under the Temperature column, $\tau$ indicates that
the temperature may be included as part of the input.

#### Our Contributions.

We show that UAV in the 2HAM is coNP-complete within the original model
(2-dimensional, constant bounded temperature parameter, singleton tile initial
assemblies), thus resolving the long-standing open problem of UAV in the 2HAM.
Further, this proves that UAV in the staged model with a single bin and stage
is coNP-complete, and that UAV in the q-tile/multiple-tile model with
polynomial-sized pieces is coNP-complete. We augment this result with a
positive result for the special case of tree-shaped assemblies, providing a
$\mathcal{O}(|A|^{5}\log\tau)$ time solution for UAV in this case (where $|A|$
is the size of the assembly) even if $\tau$ is included as part of the input.

Our results are highlighted in Table 1 along with other known results for UAV
in the 2HAM. To show coNP-hardness for UAV we construct an explicit
polynomial-time reduction from Monotone Planar 3-SAT with Neighboring Variable
Pairs (MP-3SAT-NVP). This reduction takes inspiration from the recent break-
through proof that MP-3SAT-NVP is NP-hard and its use to prove that the
connected-assembly-partitioning problem with unit squares is NP-hard [2]. For
our tree UAV algorithm, we utilize a cycle decomposition approach over
possible produced assemblies combined with dynamic programming.

#### Overview.

The paper is structured as follows. Section 2 formally defines the model, the
UAV problem, important definitions, and some small examples. Section 3 has the
reduction proving UAV in the 2HAM is coNP-hard. Due to the numerous intricate
details related to the proof, the section is broken up into several
subsections explaining different aspects of the reduction. Section 4 then
gives the algorithms for solving UAV for tree-bonded assemblies. Section 5
then concludes the paper with a summary and future work.

##  2 Definitions

In this section we overview the basic definitions related to the two-handed
self-assembly model and the verification problems under consideration.

#### Tiles.

A _tile_ is a non-rotating unit square with each edge labeled with a _glue_
from a set $\Sigma$. Each pair of glues $g_{1},g_{2}\in\Sigma$ has a non-
negative integer _strength_ ${\rm str}(g_{1},g_{2})$.

#### Configurations.

A _configuration_ is a partial function $\tilde{A}:\mathbb{Z}^{2}\rightarrow
T$ for some set of tiles $T$, i.e. an arrangement of tiles on a square grid.
For a configuration $\tilde{A}$ and vector $\vec{u}=\langle
u_{x},u_{y}\rangle$ with $u_{x},u_{y}\in\mathbb{Z}^{2}$, $\tilde{A}+\vec{u}$
denotes the configuration $\tilde{A}\circ f$, where
$f(x,y)=(x+u_{x},y+u_{y})$. For two configurations $\tilde{A}$ and
$\tilde{B}$, $\tilde{B}$ is a _translation_ of $\tilde{A}$, written
$\tilde{B}\simeq\tilde{A}$, provided that $\tilde{B}=\tilde{A}+\vec{u}$ for
some vector $\vec{u}$.

#### Bond graphs, and stability.

For a given configuration $\tilde{A}$, define the _bond graph_ $G_{\tilde{A}}$
to be the weighted grid graph in which each element of ${\rm dom}(\tilde{A})$
is a vertex, and the weight of the edge between a pair of tiles is equal to
the strength of the coincident glue pair. A configuration is said to be
_$\tau$ -stable_ for a positive integer $\tau$ if $G_{\tilde{A}}$ is connected
and if every edge cut of $G_{\tilde{A}}$ has a weight of at least $\tau$. This
means that the sum of the glue strengths along each cut is greater or equal to
$\tau$. An example bond graph for a small assembly is shown in Figure 1(b).

(a) Cooperative Binding

(b) Bond Graph

(c) Geometric Blocking

Figure 1: (a) Example of an attachment that takes places using cooperative
binding at $\tau=2$. We denote a glue strength of 1 with a rectangle and a
glue of strength 2 with a solid line through the two tiles. Dotted lines
between glues indicate that these tiles may attach to each other with the
respective strength. Assume assemblies shown are $\tau$-stable unless stated
otherwise. (b) The bond graph of the assembly showing that it is
$\tau$-stable. (c) These two assemblies are not $\tau$-combinable since this
would place two tiles at the same location. We say this is due to geometric
blocking.

#### Assemblies.

For a configuration $\tilde{A}$, the _assembly_ of $\tilde{A}$ is the set
$A=\\{\tilde{B}:\tilde{B}\simeq\tilde{A}\\}$. Informally an assembly $A$ is a
set containing all translations of a configuration $\tilde{A}$. An assembly
$A$ is a _subassembly_ of an assembly $B$, denoted $A\sqsubseteq B$, provided
that there exists an $\tilde{A}\in A$ and $\tilde{B}\in B$ such that
$\tilde{A}\subseteq\tilde{B}$. We define $|A|$ to be the number of tiles in a
configuration of $A$.

An assembly is _$\tau$ -stable_ if the configurations it contains are
$\tau$-stable. Assemblies $A$ and $B$ are _$\tau$ -combinable_ into an
assembly $C$ if there exist $\tilde{A}\in A$, $\tilde{B}\in B$, and
$\tilde{C}\in C$ such that

  1. 1.

$\tilde{A}\cup\tilde{B}=\tilde{C}$.

  2. 2.

$\tilde{A}\cap\tilde{B}=\varnothing$.

  3. 3.

$\tilde{C}$ is $\tau$-stable.

Informally, two assemblies are $\tau$-combinable if there exists two
configurations of the assemblies that may be combined resulting in a
$\tau$-stable assembly without placing two tiles in the same location.

Two assemblies combining or binding together is called an attachment. An
attachment takes place using _cooperative binding_ if the two assemblies do
not share a $\tau$-strength glue and instead use multiple weaker glues summing
to $\tau$. An example of an attachment that takes place using cooperative
binding can be seen in Figure 1(a). If an attachment cannot take place because
the two tiles would be placed in the same position, it is _geometrically
blocked_. Two assemblies whose attachment is geometrically blocked is shown in
Figure 1(c).

#### Two-handed Assembly.

A two-handed assembly system (2HAM) is an ordered tuple $\Gamma=(T,\tau)$
where $T$ is a set of single tile assemblies and $\tau$ is a positive integer
parameter called the _temperature_. For a system $\Gamma$, the set of
_producible_ assemblies $P^{\prime}_{\Gamma}$ is defined recursively as
follows:

  1. 1.

$T\subseteq P^{\prime}_{\Gamma}$.

  2. 2.

If $A,B\in P^{\prime}_{\Gamma}$ are $\tau$-combinable into $C$, then $C\in
P^{\prime}_{\Gamma}$.

A producible assembly is _terminal_ provided it is not $\tau$-combinable with
any other producible assembly. Denote the set of all terminal assemblies of a
system $\Gamma$ as $P_{\Gamma}$. Intuitively, $P^{\prime}_{\Gamma}$ represents
the set of all possible assemblies that can self-assemble from the initial set
$T$, whereas $P_{\Gamma}$ represents only the set of assemblies that cannot
grow any further. Figure 2 shows a small 2HAM example with a single terminal
assembly.

An _Assembly Tree_ for a 2HAM system $\Gamma=(T,\tau)$ is any rooted binary
tree whose nodes are elements of $P^{\prime}_{\Gamma}$, the leaves are single-
tile assemblies from the set $T$, and the two children of any non-leaf node
are $\tau$-combinable into their parent. An assembly tree with root $A$ is
said to be an assembly tree for assembly $A$. A small example is shown in
Figure 2(c).

(a) UAV Instance

(b) Producible Assemblies

(c) Small Assembly Tree

Figure 2: (a) An example instance of the Unique Assembly verification problem.
The input is the 2HAM system (tile set and temperature) and the target
assembly. (b) The main producible assemblies of the 2HAM system (for clarity,
not all subassemblies are shown). The target assembly is producible and
terminal. However, there is also a produced assembly that is a rogue assembly
(highlighted) since it not a subassembly of our target and it is terminal. (c)
A small example of an assembly tree for one of the producibles.

#### Unique Assembly.

Intuitively, the unique assembly of $A$ means that any produced assembly can
continue to grow until it becomes $A$, thus making $A$ the _uniquely produced_
assembly if the process is provided sufficient time to assemble. This means
$A$ is the unique terminal assembly and all produced assemblies are
subassemblies of $A$. Formally we say a system $\Gamma$ uniquely produces an
assembly $A$ if the following are true,

  1. 1.

$P_{\Gamma}=\\{A\\}$

  2. 2.

For all $B\in P^{\prime}_{\Gamma}$, $B\sqsubseteq A$

######  Problem 2.1 (Unique Assembly Verification problem).

Input: A 2HAM system $\Gamma$, an assembly $A$.
Output: Does $\Gamma$ uniquely produce the assembly $A$?

The Unique Assembly Verification problem (UAV) is the computational problem
that asks to verify if an assembly is uniquely produced. A key concept used
throughout this paper is a _rogue assembly_. A rogue assembly is any
producible assembly that breaks one of the conditions of unique assembly and
serves as a proof that the instance of the UAV problem is false.

######  Definition 2.2 (Rogue Assembly).

Given an instance of UAV $(\Gamma,A)$, an assembly $R\sqsubseteq
P^{\prime}_{\Gamma}$ is a rogue assembly if $R\neq A$ and $R$ is not a
subassembly of $A$.

We prove the following Lemma, which is used in the hardness reduction and the
positive result. This lemma states that if the instance of UAV is false and
all the tiles in $\Gamma$ are used to build $A$, then we may find a rogue
assembly by only checking combinable subassemblies of $A$.

######  Lemma 2.3.

For an instance of UAV $(\Gamma,A)$ that is false, either there exist two
assemblies $B,C$ such that $B,C\sqsubseteq A$ and $B$ and $C$ are
$\tau$-combinable into a rogue assembly $R$, or there exists a single tile
assembly $t\in P^{\prime}_{\Gamma}$ that is not a subassembly of $A$.

###### Proof.

First since the instance of UAV is false we know there must exist some rogue
assembly $R$. If $R$ is a single tile assembly the Lemma is true. If $R$ is
not a single tile assembly we can walk through it’s assembly tree to find the
assemblies $B$ and $C$ which are both subassemblies of our target $A$.

Consider an assembly tree of $R$ $\Upsilon_{R}$. Start by viewing the root, if
it’s two children are both subassemblies of $A$ then the rogue assembly $R$
satisfies the Lemma. If either of the children is also a rogue assembly (not a
subassembly of our target) then we can follow that node and do the same thing.
If both are rogue assemblies it does not matter which we follow.

Since this is an assembly tree all the leaves represent single tile
assemblies. Since we know none of the single tile assemblies are rogue
assemblies (if it was the lemma would already be satisfied) we know at some
point we must reach a node representing a rogue assembly that can be build
from two subassemblies of our target $A$. ∎

##  3 Unique Assembly Verification Hardness

In this section, we show coNP-hardness of the Unique Assembly Verification
problem in the 2HAM with constant temperature by a reduction from Monotone
Planar 3-SAT with Neighboring Variable Pairs.

######  Problem 3.1 (Monotone Planar 3-SAT with Neighboring Variable Pairs
(MP-3SAT-NVP)).

Input: Boolean formula $\phi=C_{1}\land\dots\land C_{m}$ in 3-CNF form where
each clause only contains positive or negated literals from
$X=\\{x_{1},\dots,x_{n}\\}$. Further, any clause of $\phi$ with $3$ variables
is of the form $(x_{i},x_{i+1},x_{j})$ or $(\lnot x_{i}\lor\lnot
x_{i+1}\lor\lnot x_{j})$, i.e., at least two of the literals are neighbors.
Output: Does there exist a satisfying assignment to $\phi$?

Monotone Planar 3-SAT with Neighboring Variable Pairs was recently shown to be
NP-hard in [2]. We assume the instance of the problem is a rectilinear planar
embedding where each variable is represented by a unit height rectangle
arranged in the _variable row_. Any planar 3SAT formula has a rectilinear
encoding [18]. We also assume that every clause is a unit-height rectangle
with edges connecting the clauses and the contained variables. The monotone
property ensures that each clause contains either only positive or only
negative literals. Thus, the clauses may be separated with all positive
clauses above the variable row, and all the negative clauses below. The final
restriction is neighboring variable pairs, which states that for the three
variables in each clause, at least two of the variables are neighbors in the
variable row. An example instance is shown in Figure 3(a).

###  3.1 Overview

Given an instance of MP-3SAT-NVP $\phi$, we build an assembly $A$ and a 2HAM
system $\Gamma$ that uniquely assembles $A$ if and only if $\phi$ does not
have a satisfying assignment. An example instance is shown in Fig. 3(a) and
3(c). Alternatively, $\Gamma$ produces a rogue assembly if and only if there
exists a satisfying assignment to $\phi$.

The ability to place all positive clauses above the variables and negative
clauses below, along with the neighboring variable pairs, allows the clauses
to be built hierarchically from the variables up. These properties allow us to
require all nested clauses be evaluated and built before the outer clause is
built. Thus, we define _parent_ and _child_ clauses as well as _root_ clauses.
In Figure 3(a), dotted lines connect child clauses $c_{1}$ and $c_{2}$ with
their parent $c_{3}$. The root clauses are $c_{3}$ and $c_{5}$.111While a
formula may have multiple clauses without a parent, the authors of [2] show
that by adding additional variables, an instance may be constructed with only
a single root clause. For MP-3SAT-NVP, we need at least two clauses (one for
the positive and negative sides).

######  Definition 3.2 (Parent/Child/Root Clause).

Given a rectilinear encoding of Monotone Planer 3-SAT, a clause $C_{p}$ is a
_parent_ clause of _child_ clause $C_{c}$, if $C_{p}$ fully encloses $C_{c}$,
and any other clause that encloses $C_{c}$ also encloses $C_{p}$. A _root_
clause is a clause without a parent.

Since $\phi$ is monotone, the positive and negative clauses may be separated
across the variable row. The assembly $A$ is also separated by a horizontal
bar that splits the assembly in two. This bar partially extends downward to
prevent this assembly from attaching to itself. Above this bar is a
subassembly that encodes the positive clauses and below the bar is a
subassembly that encodes the negative clauses, which we call the positive and
negative circuit, respectively.

The target assembly is designed so that it must be built from the variables up
to the clauses. The clause gadgets can only be built if they are satisfied.
Thus, parent clauses require that their variables or child clauses be
satisfied to build the gadget. We will ensure this by using AND and OR gadgets
between the variable and clause gadgets. We cover the parts of the system and
gadgets in the order they must assemble:

  * •

Section 3.2: variable gadgets

  * •

Section 3.3: OR gates and non-parent clause gadgets

  * •

Section 3.4: AND gates and parent clauses

  * •

Section 3.5: the root clauses and the horizontal bar

  * •

Section 3.6: how a rogue assembly may form if and only if $\phi$ is
satisfiable

(a) MP-3SAT-NVP Instance

(b) Target Assembly Circuit

(c) 2HAM UAV Target Assembly

Figure 3: (a) Example instance of Monotone Rectilinear 3SAT with Neighboring
Variable Pairs. Dotted lines are drawn between parent and child clauses. In
this example $c_{3}$ and $c_{5}$ are the positive and negative root clauses
respectively. (b) A circuit view of our example instance with gates divided
into the clauses they compute. We add AND gates (shown in grey) between child
clauses that have the same variables. (c) Target assembly constructed from
instance on left. Each tile in the assembly is a unique tile type. Each glue
is unique except for the strength $1$ glues connecting the horizontal bar and
the arms of each circuit. The parts of the assembly that represent each clause
are boxed in.

###  3.2 Variable Gadget

For each variable gadget we use $(2+4d)$ subassemblies (Figure 4(a)) to build
the variable gadget where $d$ is the number of times the variable is used or
it’s outdegree. An example is shown in Figure 4(b) where $d=1$ and Figure 4(c)
where $d=2$. In the figures, the lines are strength-2 glues, and the rectangle
glues are all strength-1, thus requiring cooperative binding for the
subassemblies to attach in a specific build order. We draw our gadgets
separated into subassemblies but we construct our tile set using the single
tiles which will self-assemble into these subassemblies. Every variable gadget
is built as follows.

  * •

The Bar Assembly acts as a backbone (or separator) for the completed circuit
subassemblies to connect to each other.

  * •

The Bump is the first assembly to attach to the Bar Assembly. The Bump is a
height $2$ rectangle with an extra domino below it that is used for geometric
blocking and encoding the assignment to that variable. The position of this
domino is dependent on the position of the variable gadget on the opposite
(negative) side.

  * •

The Base Dominoes are used as part of the process of duplicating a variable
path to multiple clauses. For each clause a variable is in, we use four
subassemblies to connect to the next gadget. The first two gadgets are the
Base dominoes. Once the Bump attaches to the Bar Assembly, the Base Dominoes
can attach cooperatively to both. Once the first Base Domino attaches the next
can attach using the glue from the previous domino and the other from the
Bump.222Without these base dominoes, variable gadgets could build without the
full Bump due to backfilling or backwards growth. The dominoes ensure this can
not happen.

  * •

The Wires attach the variable gadgets to the clauses, and are the final two
subassemblies for connecting to the next gadget. The first wire attaches
cooperatively to the Bar Assembly and subsequent ones attach to the previous
wire. The wires in our system are all built from two assemblies. When both
halves of the wire are connected, the next gadget may attach. We call this a
completed wire.

Variable gadgets in the negative circuit are built symmetrically rotated $180$
degrees. We adjust the position of dominoes on the Bumps of the gadgets so
that variable gadgets on opposite circuits that represent the same variable
have their domino in the same column. We may generalize these gadgets to out
degree $d$ (the variable appears in $d$ clauses) by increasing the width of
the bump, and adding additional dominoes and wires.

(a) Subassemblies of a variable gadget

(b) A variable gadget with outdegree $1$

(c) A variable gadget with outdegree $2$

(d) Assignment to the example MP-3SAT-NVP instance

Figure 4: (a) The smaller assemblies used for building a variable gadget. (b)
A variable gadget for a variable that is used in a single clause. (c) A
variable gadget with outdegree 2. For each additional output more base
dominoes and wires are added. (d) A set of producible subassemblies
representing variables that satisfy the example instance. We will walk through
how these assemblies grow into a rogue assembly.

###  3.3 OR Gates and Clause Gadgets

In CNF form, every variable in a clause is separated by a logical OR, thus, as
part of our clause gadgets, we create OR gates to bring the variables together
to ensure that the clause only forms if there is at least one variable that
satisfies the clause.

(a) Build OR gate

(b) Wire backing filling

Figure 5: (a) The process of a variable gadget growing the OR gate used for
clauses. Glues used for attachment in the next step are denoted by arrows. If
one of the variable gadgets is constructed the $2\times 2$ square assembly may
attach. The output wires of the gate then attach cooperative with the wire
from the variable assembly and the square. Note that only one of the variable
assemblies needs to be constructed for the OR gate to build it’s output wire.
(b) Once the output wires of the OR gate have attached the wire for the other
variable may “Backfill” or grow backwards.

#### OR Gates.

An example of how the OR gate grows off of a variable gadget is shown in
Figure 5(a). The OR gate consists of a single $2\times 2$ square with
strength-$1$ glues on the west, north, and east facing tile edges. The west
and east glues each connect to the wires that input to the gate. The north
glues are used cooperatively with glues on the incoming wire gadgets to attach
another wire gadget going to the clause gadget. To complete the new wire
gadget it must also cooperatively use the other incoming wire. We note that
the wires from the other input can backfill, but that does not cause an issue
as the ‘backward’ growth stops after building the wire. Figure 5(b) shows an
example with only one variable used in the OR gate.

(a) Clause Gadget

(b) Parent Clause gadget

(c) Parent clause gadget with 3 literals

Figure 6: (a) A clause gadget with $2$ neighboring variables. (b) A clause
gadget with two variables and a child clause. (c) When a parent clause has $3$
literals we know two of them must be neighbors. Using an additional OR gate we
may use the same gadget as the clause with $2$ literals.

(a) Clause $c_{1}$

(b) Circuit for $c_{1}$

(c) Gadgets for $c_{1}$

Figure 7: (a) The clause $c_{1}$ in Figure 3(a) is satisfied by $x_{2}=1$. (b)
The OR gate grows off of $x_{2}$. The other wires on the variable gadget are
used to connect to other clause gadgets. (c) The gadget constructed for the
clause $c_{1}$. Note the other wire from the OR gate has backfilled.

(a) Clause $c_{2}$

(b) Circuit for $c_{2}$

(c) Gadgets $c_{3}$

Figure 8: (a) $c_{2}$ from our example. This clause has 3 variables and no
children. (b) The clause is computed using two OR gates. The gates are able to
grow from $x_{4}$. (c) $x_{4}$ variable gadget allows for the two OR gates to
attach.

#### Non-parent Clauses.

The first clause type we cover are clauses without children, or clauses at the
bottom of the circuit. The simplest type of this gadget are clauses with only
$2$ literals as in Figure 7(b). This gadget is fairly straightforward to
implement as we only need to use a single OR gate. An example of this type of
clause is in Figure 7(a), and its implementation is in Figure 7(c). Note that
both variables appear in other clauses so those variable gadgets have
additional wires. For non-parent clauses with $3$ literals (Figure 11(a)), we
use $2$ OR gates (Figure 8(c)).

###  3.4 AND Gates and Parent Clauses

Since every clause in CNF form is separated by a logical AND, we create AND
gates that compare clauses. Thus, we need to know which clauses are parent
clauses since they have child clauses underneath them with wires coming into
the gates. We also build a FANOUT gate for connecting clauses.

#### AND Gates.

The AND gate uses $2$ vertical dominoes that share a single strength-$1$ glue
between them. Figure 10(a) shows an example AND gate being constructed. Once a
wire that inputs to the gate is completed, one of the dominoes can
cooperatively attach. The domino has another strength-$1$ glue on its north
side that allows a horizontal domino to cooperatively attach using the glue
exposed on the wire.

Using the glues from the newly attached dominoes, the two halves of the gate
are able to attach to each other. This allows for the two glue on the
horizontal dominoes to be used to cooperative bind the white center domino.
From here, the two halves of the wire that outputs from the AND gate can
attach.

#### FANOUT Gates.

In order to build the parent clause, we also need a way to ‘fan-out’ and copy
the signal from an AND gate to two other gadgets. We do this by adding glues
to the north side of the center domino and having two wires grow off of the
gadget. This process is shown in Figure 10(b).

(a) Build AND gate

(b) Build FANOUT

(c) Attachment of an AND gate

Figure 10: (a) The process of an AND gadget assembling. The output wires can
only grow from the combined halves of the AND gate. (b) By modifying the
center domino, two wires may be output from a single AND gate, which works as
a FANOUT. (c) The two clauses $c_{1}$ and $c_{2}$ both have the same parent
clause so they are joined by an AND gate. Once the dominoes attach to the
output wire of the clauses the two assemblies may attach to each other.

#### Parent Clauses.

Consider a parent clause $C_{p}=(x_{1}\lor x_{4})$. Let $C_{c}$ be the child
clause. Since we want this gadget to build only if its own clause and its
child are both satisfied, we can view this statement as $(x_{1}\lor
x_{4})\land C_{c}$. However, we can modify the statement to be $(x_{1}\land
C_{c})\lor(C_{c}\land X_{4})$, which we can build since we have planar
circuits. An example of the circuit and gadgets are shown in Figure 6(b).

(a) Clause $c_{3}$

(b) Circuit for $c_{3}$

(c) Gadget for $c_{3}$

Figure 11:  (a) The root clause of the example instance. This clause has two
literals and two children. (b) Since the AND gate has built and $x_{4}$
satisfies $c_{3}$ the clause may grow. (c) The two child clause’s output are
connected by an AND gate and then used as the middle input to the gadget.

By the neighboring variable pairs restriction, we know that any clause with
three variables has at least a pair of them being neighbors. This means that
there cannot be any child clauses beneath that neighboring pair, so we may use
an OR gate between those two variables and then build the rest of the gadget
in the same way as the two literal version (Figure 6(c)).

In our example instance, the root clause of the positive circuit has two
children. For these cases we may use the AND gadget to verify that both child
clauses have been satisfied before allowing the parent clause to build. The
root clause of the negative circuit in our example instance (Figure 12(a)) has
three literals. The constructed gadget can be seen in Figure 12(a).

(a) Clause $c_{5}$

(b) Circuit for $c_{5}$

(c) Gadget for $c_{5}$

Figure 12: (a) In the example instance the negative circuit has $c_{5}$ which
is a parent clause with $3$ literals. (b) The negative circuit draw with
gates. The variables $x_{1}$ and $x_{3}$ being false satisfies all the
clauses. (c) The variable assemblies we selected at the beginning also grow
into a circuit with the root clause built.

###  3.5 Root Clauses and Horizontal Bar

#### Root Clauses and Arms.

The root clause is the outermost clause on either side of the variables.
Although it functions similar to the other clauses, instead of outputting a
wire, a horizontal $4\times 1$ rectangle can attach after it finishes
assembling. The arms may then cooperatively bind to the rectangle and the
wires of the root clause forming the top of the circuit. The glues on the ends
of these arms allow for the circuit to attach to the horizontal bar. A high-
level view of the root clauses and arms attached is shown in Figure 13(a) as
well as a detail of the assembly process of the root clause in Figure 13(b).

#### Horizontal Bar.

The horizontal bar (Figure 13(a)) is a width-$1$ assembly that extends the
width of both circuits with strength-$1$ glues on the north and south side of
the outer tiles. Since the arms must also be able to attach to each other to
form a rogue assembly the glues on the ends of the horizontal bar must be the
same. In order to prevent the horizontal bar from attaching to another
instance of itself, we extend the bar partially downward so it will
geometrically block copies from attaching.

(a) Horizontal Bar and Completed Circuits

(b) Glues on root clause and variable gadgets.

Figure 13: (a) The root clauses and arms joining the positive and negative
assemblies with the horizontal bar. The root clause allows a short wire to
attach where the arms can then attach. Each arm has a strength-1 glue at the
end. The horizontal bar separates the positive circuit from the negative
circuit. The small bump is so the bar can not attach to other horizontal bars.
(b) Each subassembly of the root clause cannot attach to each other without
being satisfied from the child clauses since each subassembly only shares a
strength-1 glue with adjacent assemblies.

###  3.6 Rogue Assemblies

For the construction of the target assembly, each piece is built from the
variables up to the root clause. However, the nondeterministic build order
means that not all parts of each circuit need to be built in order for the
root clause to be satisfied. For instance, if one of the variables in a clause
attaches, the OR gates will still allow the wires to attach. Thus, using a
variable constitutes setting it to true (and in the negative circuit using a
variable is setting the negation to true).

With root clauses satisfied and the arms attaching, a rogue assembly may occur
as shown in Figure 14(c). The corresponding circuit is shown in Figure 14(b).
This can occur because the arms can attach to each other without the
horizontal bar. Normally, the variable gadgets would overlap and prevent this
attachment if both the positive and the negative circuit used the same
variable (which is setting a variable to both true and false). Thus, the
positive and negative side each have their own set of variables that make all
clauses on their respective sides true. This rogue assembly can only happen if
there is a subset for each side that allows all clauses to be true, and thus
satisfies the original MP-3SAT-NVP formula.

For an MP-3SAT-NVP instance $\phi$ and an assignment $X_{s}$ to the variables
in $X$, let $A_{p}$ and $A_{n}$ be the positive and negative circuit
assemblies, respectively, created from $\phi$. We say an assembly
$A^{\prime}_{p}\sqsubseteq A_{p}$ represents the assignment $X_{s}$ if it has
attached variable gadgets for the variables in $X_{s}$ that equal $1$, and has
built its root clause. For negated circuits, it must have variable gadgets
attached for variables set to $0$ in $X_{s}$.

######  Lemma 3.3.

For a rectilinear encoding of Monotone Planar 3SAT $\phi$ with neighboring
variable pairs and 2HAM system $\Gamma_{\phi}$ as described above, there exist
two producible assemblies $A^{\prime}_{p}\sqsubseteq A_{p}$ and
$A^{\prime}_{n}\sqsubseteq A_{n}$ that both represent the same assignment
$X_{s}$ to the variables $X$, if and only if $X_{s}$ satisfies $\phi$.

###### Proof.

If there exists a satisfying assignment $X_{s}$ to $X$, we may build
$A^{\prime}_{p}$ by taking the variable gadgets for variables assigned to $1$
and grow the circuit off of them. Since we know all the clauses are satisfied,
each clause gadget (including the root clause) may grow resulting in an
assembly $A^{\prime}_{p}$ that represents $X_{s}$. By the same argument we
know $A^{\prime}_{n}$ is producible since $X_{s}$ satisfies $\phi$, which
includes the negated clauses.

We prove these assemblies are producible only if $X_{s}$ satisfies $\phi$ via
contradiction. Assume $X_{s}$ does not satisfy $\phi$, but both assemblies
$A^{\prime}_{p}$ and $A^{\prime}_{n}$ are producible. Since $X_{s}$ does not
satisfy $\phi$, there must exist at least one unsatisfied clause $c_{i}$.
W.L.O.G., assume $c_{i}$ is a positive clause. We show the assembly
$A^{\prime}_{p}$ cannot be produced.

Starting with the case that $c_{i}$ is the root clause, assume all of the
children of $c_{i}$ are satisfied. The center input of the clause is a
producible subassembly of $A^{\prime}_{p}$ since variable gadgets are allowed
that satisfy the clauses below it. We can see in Figure 13(b) the other
producible subassemblies of the gadgets only have a strength-$1$ glue between
them. This means none of the subassemblies are able to attach to each other on
their own. In order for the arms to attach to the output wire of the root
clause, at least one of the AND gates must be fully constructed. The AND gate
cannot assemble unless both halves of the gate have been constructed. The
middle input is built, but the other half of the AND gadget must grow off a
completed wire from the variable gadget. However, since $c_{i}$ is not
satisfied the variables gadgets which satisfy the formula have not attached so
the assembly $A^{\prime}_{p}$ cannot build the clause gadget.

If $c_{i}$ is another parent clause that is not the root. Let the clause
$c_{j}$ be the parent clause of $c_{i}$. If the clause gadget for $c_{i}$ is
not constructed then the gadget for $c_{j}$ is not buildable. Since the
gadgets used are the same as the root clause, the output wires of the clause
gadget for $c_{i}$ cannot be built without a variable gadget which satisfies
the formula. The middle input of clause gadget representing $c_{j}$ will not
be buildable since this would be the output wire of $c_{i}$. The middle input
goes to two AND gates that cannot construct unless both wires have been built.
Thus, the output wire of $c_{j}$ cannot be built without its children clauses
satisfying it. In the case $c_{j}$ has multiple children, the output wires of
all its children are joined by AND gates that will not construct without both
inputs.

Finally, consider the case where $c_{i}$ is a clause without children. In
order for the clause’s output wire to complete, it must be attached to an OR
gadget and the outer wire of the variable gadget. The OR gadget may only
attach to a completed wire from a variable gadget (or another OR). The
variable gadget cannot be completed without placing the bump, so we cannot
have built the outwire of $c_{i}$. By the same argument as the previous case,
this clause not being built results in its parent not being built.

If $c_{i}$ is not satisfied, the clause gadget for $c_{i}$ cannot be
constructed, which means the assembly $A^{\prime}_{p}$ is not producible. ∎

(a) Satisfying Assignment

(b) Rogue Assembly Circuit

(c) Rogue Assembly

Figure 14: (a) There exists a satisfying assignment for the example instance
with green blocks representing variables which equal $1$ and red blocks
representing $0$. (b) Rogue assembly drawn as a circuit with selected
variables. (c) The 2HAM system will produce a Rogue Assembly from the two
circuit assemblies which represent the satisfying assignment.

######  Theorem 3.4.

The Unique Assembly Verification problem in the 2HAM is coNP-Complete with
$\tau=2$.

###### Proof.

Given an instance of a rectilinear encoding of Monotone Planar 3SAT with
neighboring variable pairs $\phi$, we create a 2HAM system $\Gamma=(T,2)$ and
an assembly $A$ such that $\Gamma$ uniquely produces $A$ if and only if there
does not exist a satisfying assignment to $\phi$. We create the assembly $A$
by taking the rectilinear encoding of $\phi$, arranging the rectangles on a
grid graph, and replacing the rectangles with the given variable and clause
gadgets. We also add the arms and horizontal bar.

Assume there exists a satisfying assignment $X_{s}$ to the variables $X$, for
$\phi$. We know by Lemma 3.3, there exist two producible assemblies
$A^{\prime}_{p}$ and $A^{\prime}_{n}$ that both contain the arms and have
complementary bump positions333Having complimentary bump positions is
equivalent to both representing the same assignment. These two assemblies can
cooperatively bind to one another using the two glues on their arms, and thus
produce a rogue assembly as in Figure 14(c). This means a satisfying
assignment to $\phi$ implies $\Gamma$ does not uniquely construct $A$.

Now assume $\Gamma$ does not uniquely produce $A$, so there exists some rogue
assembly $B$. The only repeated glues in the tile set of $\Gamma$ are the
exposed glues on the arms. Any rogue assembly must use these two glues to
assemble, and they must be assembled from two subassemblies of the target by
Lemma 2.3. Let $B$ be producible by combining two assemblies $b$ and
$b^{\prime}$. Since both $b$ and $b^{\prime}$ are producible assemblies with
both their arms, and they can attach to each other, they are not geometrically
blocked. This implies they must represent the same assignment and by Lemma
3.3, this can only be true if the assignment satisfies $\phi$. By viewing
which variable gadgets are included in the two assemblies, we can identify the
satisfying assignment to $\phi$. Thus, $\Gamma$ will uniquely produce $A$ if
and only if there does not exist a satisfying assignment to $\phi$. ∎

##  4 Verification of Tree-Bonded Assemblies

In this section, we investigate the problem of Unique Assembly Verification
with the promise that the target assembly $A$ is _tree-bonded_ , meaning the
bond graph of the target assembly forms a tree. Figures 15(a) and 15(b) show
examples of tree-bonded assemblies. Figure 15(c) shows an assembly whose bond
graph contains a cycle and thus is not a tree-bonded assembly. We first
present a $\mathcal{O}(|A|^{5})$ algorithm for temperature $2$ systems, and
then extend this method to provide a $\mathcal{O}(|A|^{5}\log\tau)$ time
dynamic programming algorithm for the case where the temperature $\tau$ of the
system can be passed as a parameter. Before describing the algorithms, we
first introduce some required definitions and the problem formulations.

(a) Tree-bonded and Shaped

(b) Tree-bonded

(c) Not Tree-bonded

Figure 15: (a) Both the shape and bond graph of this assembly are trees. (b)
Even though the shape of this assembly is a square, its bond graph still does
not contain cycles and thus this assembly is tree-bonded. (c) This assembly is
not a tree-bonded graph due to there being a cycle in its bond graph.

#### Tree-Bonded Assemblies.

An assembly $A$ is a _tree-bonded assembly_ if and only if the induced bond
graph $\mathcal{G}_{A}$ is acyclic.

#### Binding Sites.

For two configurations $C_{1}$ and $C_{2}$, we say a _binding site_
$\mathcal{B}$ is a pair of points $(p_{a},p_{b})$, such that
$||p_{a}-p_{b}||_{2}=1$, and the tiles $C_{1}(p_{a})$ and $C_{2}(p_{b})$ have
nonzero glue strength between each other. The set of binding sites for two
configurations is the set of pairs of points that meet this requirement. We
also define an _inner binding site_. For two configurations, $C_{1}$ and
$C_{2}$, and a pair of binding sites
$a=(a_{1},a^{\prime}_{2}),b=(b_{1},b^{\prime}_{2})$, let $I(a,b)$ be the set
of binding sites that occur on the inside of the loop formed by $a,b$ (inner
binding sites). An example of the area enclosed by a loop is seen in Figure
16(c).

#### Simple Loops.

For two configurations, $C_{1}$ and $C_{2}$, and a pair of binding sites
$a=(a_{1},a^{\prime}_{2}),b=(b_{1},b^{\prime}_{2})$, we say the loop formed by
$a,b$ is a _simple loop_ if $|I(a,b)|=0$.

#### Origin Configuration

In discussing different configurations and assemblies, it is useful to anchor
a configuration to a fixed point. For an assembly $A$, the _origin
configuration_ $A_{0}$ is the translation of $A^{\prime}s$ configuration such
that the bottom left vertex of the bounding box of elements in $dom(A_{0})$ is
at the origin $(0,0)$.

######  Problem 4.1 (Temp2-Tree-UAV).

Input: A $\tau=2$ 2HAM system $\Gamma$ and a tree-bonded assembly $A$. Output:
Does $\Gamma$ unique produce the assembly $A$?

######  Problem 4.2 (Tree-UAV).

Input: A 2HAM system $\Gamma$ and a tree-bonded assembly $A$. Output: Does
$\Gamma$ uniquely produce the assembly $A$?

###  4.1 Overview

The high-level goal of this algorithm is to find a rogue assembly that acts as
a witness that the instance of UAV is false. We note that a given instance,
$P=(\Gamma,A)$, of Temp2-Tree-UAV, where $\Gamma=(T,\tau)$, can be broken down
into three possible cases. An example tree-bonded assembly is shown in Figure
16(a).

  1. 1.

The instance $P$ is false, and $\Gamma$ produces a tree-bonded rogue assembly.

  2. 2.

The instance $P$ is false, and the only rogue assemblies producible in
$\Gamma$ are non tree-bonded.

  3. 3.

The instance $P$ is true.

At a high level, the algorithm first checks if Case 1 is true and then checks
if Case 2 is true. If either are true, the algorithm rejects, otherwise it
accepts. Case 1 can be checked efficiently by modifying $\Gamma$ to function
as a noncooperative system $\Gamma^{\prime}$ and utilizing the algorithm for
temperature-$1$ UAV provided in [15]. To check the second case, Lemma 2.3
states that if the instance is false, it suffices to check pairs of
subassemblies of the target assembly $A$ in order to find a witness rogue
assembly. Thus, we take two copies of the target assembly and attempt to find
possible ways they may bond, even if the resulting assembly places two tiles
at the same position. We call the pairs of tiles that contribute glue strength
_binding sites_. Tiles that are in the same position are called
_intersections_. An example of both may be seen in Figure 16(b).

We first analyze the case of temperature-$2$ systems where only need two
binding sites that do not intersect are needed. We then generalize this
algorithm by using dynamic programming to find the set of binding sites to
maximize the binding strength between the assemblies without any
intersections.

(a) Tree-bonded Assembly

(b) Overlap Subassemblies

(c) Outer Loop

(d) Intersection loop

Figure 16: (a) An example tree-bonded target assembly. (b) One possible
overlap configuration formed by two subassemblies with $5$ binding sites that
are highlighted. (c) The loop formed by binding sites $A$ and $E$ is outlined
in green. Any binding site that occurs in the grey shaded area, such as $B$,
is in the set of inner binding sites for $(A,E)$. (d) The loop formed using
binding sites $(C,D)$ intersects itself and cannot be used.

###  4.2 Tree-Bonded Rogue Assemblies

The following algorithm checks if a system uniquely assembles a given shape
provided the system is restricted to behaving in a noncooperative manner. This
means that two assemblies can only attach if they share one or more
strength-$\tau$ glues between them. This system functions equivalently to a
temperature-$1$ system where all glues less than strength-$\tau$ are removed
and all glues greater than strength-$\tau$ are set to strength-$1$. We modify
the system in this way and then use the known polynomial time algorithm for
temperature-$1$ UAV [15].

Data: 2HAM System $\Gamma=(T,\tau)$, an assembly $A$

Result: Does $\Gamma$ uniquely assembly $A$ if it can only utilize strength
$\geq\tau$ glues?

Modify $T$ to create $T^{\prime}$ by removing all glues of strength less than
$\tau$, and setting the strength of all glues of strength $\geq\tau$ to $1$;

if  _Temp1-UAV $(\Gamma^{\prime}=(T^{\prime},\tau=1),A)$_ then accept;

else reject;

Algorithm 1 NonCoop-UAV$(\Gamma,A)$. The runtime of Temp1-UAV is
$\mathcal{O}(|A||T|\log|T|)$ [15].

######  Lemma 4.3.

For any 2HAM system $\Gamma=(\Sigma,\tau)$ and tree-bonded assembly $A$, if
NonCoop-UAV$(\Gamma,A)$ (Algorithm 1) is true, and $\Gamma$ does not uniquely
assemble $A$, then there exists assemblies $B,B_{1},B_{2}$, s.t.
$B\not\sqsubseteq A$, $B_{1},B_{2}\sqsubseteq A$, $B_{1}$ and $B_{2}$ combine
to form $B$ by utilizing cooperative binding.

###### Proof.

Since NonCoop-UAV$(\Gamma,A)$ is true, but $\Gamma$ does not uniquely assemble
$A$, there must exist a rogue assembly $B^{\prime}\not\sqsubseteq A$ since any
subassembly of $A$ would be tree-bonded. Consider an assembly tree
$\Upsilon_{B}^{\prime}$ for $B^{\prime}$. Since NonCoop-UAV$(\Gamma,A)$ is
true, the singleton tile leaves of $\Upsilon_{B}^{\prime}$ must be
subassemblies of $A$. We will show there exists a node
$B\in\Upsilon_{B}^{\prime}$, with children $B_{1}$ and $B_{2}$, respectively,
such that $B^{\prime}\not\sqsubseteq A$, and $B_{1},B_{2}\sqsubseteq A$.

Let the root node of the tree $\Upsilon_{B}$ be the candidate node $B$, and
let assemblies $B_{1}$ and $B_{2}$ be the two children of $B$. If $B_{1}$ and
$B_{2}$ are both subassemblies of $A$, then the conditions are met. Otherwise
w.l.o.g., assume $B_{1}\not\sqsubseteq A$. We now set the candidate node $B$
to $B_{1}$ and repeat the process. Since all leaves of $\Upsilon_{B}$
represent subassemblies of $A$, there must be a point in which the candidate
$B$ node is some assembly $B\not\sqsubseteq A$, and its children are
assemblies $B_{1},B_{2}\sqsubseteq A$. ∎

###  4.3 Temperature-$2$

With respect to the given instance of Temp2-Tree-UAV $P$, if $P$ is false, and
the algorithm for NonCoop-UAV$(\Gamma,A)$ returns ‘accept’, then Lemma 4.3
implies there exists two subassemblies of the target, $B_{1}$ and $B_{2}$,
that attach to each other using cooperative binding.

To find these two subassemblies, we start by taking two “copies” of the target
assembly and finding all $|A|^{2}$ possible ways to combine the two
assemblies, even if it results in intersections. If any way to combine these
assemblies results in at least two binding sites, we attempt to find
$2$-combinable subassemblies. Since we know these subassemblies are also tree-
bonded, there only exists one path between each pair of tiles- including the
binding sites. So for each pair of binding sites, we take the loop formed by
the two binding sites and check if it intersects itself. An example of a loop
that intersects itself is shown in Figure 16(d). If there ever exists a pair
of binding sites whose paths do not intersect, then those two subassemblies
will form a rogue assembly and we reject.

Data: 2HAM System $\Gamma=(\Sigma,\tau)$, Tree-Bonded Assembly $A$ with height
$h$ and width $w$

Result: Does $\Gamma$ uniquely produce $A$?

if  _NonCoop-UAV $(\Gamma,A)$ rejects_ then reject;

Let $A_{0}$ be the origin configuration of assembly $A$;

for  _$i\leftarrow-w$ to $w$ _ do

for  _$j\leftarrow-h$ to $h$_ do

$A^{\prime}\leftarrow A_{0}+\langle i,j\rangle$;

Let $\mathcal{B}$ be the set of binding sites between $A_{0}$ and
$A^{\prime}$;

for  _each pair of binding sites $a,b\in\mathcal{B}$_ do

if  _The loop formed using $a,b$ does not intersect itself_ then reject;

accept;

Algorithm 2 Algorithm to solve Temp2-Tree-UAV in $\mathcal{O}(|A|^{5})$ time.

######  Theorem 4.4.

There is a $\mathcal{O}(|A|^{5})$ time algorithm that decides Temp2-Tree-UAV.

###### Proof.

Correctness of Algorithm 2: Assume we are given an instance of Temp2-Tree-UAV,
$P=((\Gamma,\tau=2),A)$. The algorithm first checks if $P^{\prime}=$NonCoop-
UAV$(\Gamma,A)$ is true. If $P^{\prime}$ is true then it follows that $A$ is
producible in $\Gamma$.

The remainder of the algorithm searches for a rogue assembly by overlapping
the target with itself, and checking pairs of binding sites to see if a rogue
assembly can be built from the loop formed through them. Since the target is
tree-bonded, there only exists a single path between each pair of tiles,
including our binding sites. If the two paths formed between the bindings
sites do not intersect, or place two different tiles in the same location, the
loop formed by these two paths creates a rogue assembly.

We now argue that if a rogue assembly exists, then the overlapping method will
find some rogue assembly. By Lemma 4.3, if $P^{\prime}$ is true, but the
instance $P$ is false, there must be a producible rogue assembly $B$ built
using cooperative binding, which can be split into two subassemblies
$B_{1},B_{2}\sqsubseteq A$. Now consider two pairs of adjacent tile locations
where $B_{1}$ and $B_{2}$ share a strength-$1$ glue, and let tiles
$t_{1},t_{2}$ and $t^{\prime}_{1},t^{\prime}_{2}$ be the tiles at these
locations. Consider the assembly $B^{\prime}_{1}$ only composed of the path of
tiles from $t_{1}$ to $t^{\prime}_{1}$ in $B_{1}$, and a second assembly
$B_{2}$ that is the path of tiles from $t_{2}$ to $t^{\prime}_{2}$ in $B_{2}$.
$B^{\prime}_{1}$ and $B^{\prime}_{2}$ are combinable to build a rogue assembly
$B$.

$B^{\prime}_{1}$ and $B^{\prime}_{2}$ are both subassemblies of $A$, and there
is some overlapping of $A$ with an offset of itself in which $B_{1}$ and
$B_{2}$ are adjacent, and $t_{1},t_{2}$ and $t^{\prime}_{1},t^{\prime}_{2}$
are both in the set of binding sites of this overlap. Since the algorithm
checks all pairs of binding sites, it will eventually check that pair, and
will attempt to connect the two assemblies that are the simple paths between
them, which are $B^{\prime}_{1}$ and $B^{\prime}_{2}$. Therefore, the
algorithm will build the rogue assembly $B^{\prime}=B^{\prime}_{1}\cup
B^{\prime}_{2}$ and reject.

Runtime: First NonCoop-UAV$(\Gamma,A)$ runs in $\mathcal{O}(|A||T|\log|T|)$
time. While this part of the algorithm becomes the bottleneck if $|T|>|A|$,
this cannot be the case. If the size of the tile set is greater than the
number of tiles in the assembly, at least one tile can never grow into $A$ and
we may reject. Next, for each of the $\mathcal{O}(|A|^{2})$ ways to combine
$A$ with itself, the algorithm checks at most $\mathcal{O}(|A|^{2})$ pairs of
binding sites. For each of these pairs, it does a sequence of
$\mathcal{O}(|A|)$ time operations to verify the paths do not intersect. ∎

###  4.4 Variable Temperature

We now present an algorithm for Tree-UAV, a generalization of the previous
problem that allows the temperature of the system $\tau$ to be given as input.

This algorithm works in a similar way as the previous algorithm except it does
not suffice to only find a single loop since the temperature requirement for
assemblies to bind may be greater than $2$. We must find multiple loops
between binding sites that do not intersect. Once we have a way to combine the
assembly, we will view binding sites and loops in a hierarchical way using
inner binding sites. An example of an inner binding site can be seen in Figure
16(c). We recursively calculate the max binding strength when taking each pair
of binding sites as the outer loop.

After calling NonCoop-UAV$(\Gamma,A)$, we check each possible way to attach
$A$ to itself. For each of these ways, we build a $b\times b$ table where $b$
is the total number of induced binding sites. For each pair of binding sites
we calculate the maximum value recursively augmented with the table. This
allows us to only compute the maximum value once for each loop.

First, we check if the created loop intersects itself. If it does, we cannot
use that loop, so we set the value in the table to be $-1$. Next, we check if
the binding sites form a simple loop that does not contain inner binding
sites. In this case, the max value is the sum of the glue strength between the
binding sites. For loops that do contain inner binding sites, we perform a
_loop decomposition_ , which is the process of breaking a loop into two
smaller loops along one of the inner binding sites. An example of a loop being
decomposed into simple loops can be seen in Figure 17(a). To find the max
binding strength of the outer loop, we break the loop up along each inner
binding site and recursively get the max strength of the two resulting loops
(subtracted by the glue strength of the inner binding site since it would be
counted twice). If either of the smaller loops intersects itself, it will
return $-1$ and we know not to use that inner binding site. The max binding
strength of the outer loop is then the maximum of these computed values over
all choices of inner binding site. The recursive checks are implemented with a
dynamic programming/memorization table to eliminate repeated recursive calls.

(a) Loop Decomposition

(b) Invalid Loop Decomposition

Figure 17: (a) One possible way to decompose loops into simple loops based on
inner binding sites. (b) Decomposing the loop $(A,D)$ along binding site $C$
results in the loop $(C,D)$ which intersects itself. This means we cannot
decompose the loop $(A,D)$ along $C$.

Data: 2HAM System $\Gamma=(\Sigma,\tau)$, Tree-Bonded Assembly $A$ with height
$h$ and width $w$

Result: Does $\Gamma$ uniquely produce $A$?

if  _NonCoop-UAV $(\Gamma,A)$ rejects_ then reject;

Let $A_{0}$ be the origin configuration of assembly $A$;

for  _$x\leftarrow-w$ to $w$ _ do

for  _$y\leftarrow-h$ to $h$_ do

$A^{\prime}\leftarrow A_{0}+\langle x,y\rangle$;

Let $\mathcal{B}$ be the set of binding sites between $A_{0}$ and
$A^{\prime}$;

Let $b=|\mathcal{B}|$;

Create a $b\times b$ table $T_{\mathcal{B}}$ indexed by the elements of
$\mathcal{B}$ with all cells initialized to empty.;

for  _each pair of binding sites $b_{1},b_{2}\in\mathcal{B}$_ do

if  _$maxStr(C,T_{\mathcal{B}},b_{1},b_{2})\geq\tau$_ then reject;

accept;

Algorithm 3 Algorithm to solve Temp2-Tree-UAV in $\mathcal{O}(|A|^{5})$ time.

Data: Union of two assemblies $C$, Table $T_{B}$, and Binding sites
$b_{1},b_{2}$

Result: Does $\Gamma$ uniquely assembly $A$ if it can only utilize strength
$\geq\tau$ glues?

if  _$T_{\mathcal{B}}(b_{1},b_{2})$ is empty_ then

if  _The loop formed by $b_{1},b_{2}$ intersects itself _ then return $-1$;

if  _$|I(b_{1},b_{2})|=0$_ then return $glueStr(b_{1})+glueStr(b_{2})$;

Let $T_{B}(b_{1},b_{2})=0$;

for  _$b_{i}\in I(b_{1},b_{2})$_ do

if  _$maxStr(b_{1},b_{i})$ or $maxStr(b_{i},b_{2})=-1$_ then continue;

$s\leftarrow maxStr(b_{1},b_{i})+maxStr(b_{i},b_{2})-glueStr(b_{i})$;

if  _ $s>T_{\mathcal{B}}(b_{1},b_{2})$ _ then
$T_{\mathcal{B}}(b_{1},b_{2})\leftarrow s$;

return $T_{\mathcal{B}}(b_{1},b_{2})$;

Algorithm 4 $maxStr(T_{\mathcal{B}},b_{1},b_{2})$. The subroutine that
calculates the max strength when using two binding sites as the outer loop.
The method $glueStr(b)$ takes in a binding site and returns the strength of
the glue connecting the two tiles.

######  Theorem 4.5.

There is a $\mathcal{O}(|A|^{5}\log\tau)$ time algorithm that decides Tree-
UAV.

###### Proof.

Correctness: We know from Lemma 4.3, if NonCoop-UAV$(\Gamma,A)$ returns
‘reject’, but the system does not uniquely assemble $A$, there exists a rogue
assembly $B$ that may be assembled by two tree-bonded assemblies $B_{1}$ and
$B_{2}$, which are subassemblies of our target $A$. Using the same method from
the previous algorithm, we find the possible ways the target may bind to
itself. If any value in the table $T_{\mathcal{B}}$ is greater than $\tau$,
then there exists a set of non-intersecting loops whose union is a producible
rogue assembly. We take the union of each of the loops to find the rogue
assembly. We know the assembly is producible since none of the paths intersect
and the sum of the strength of the binding sites is greater than $\tau$.

Now assume there exists a rogue assembly $B^{\prime}$ that was not found by
NonCoop-UAV$(\Gamma,A)$. Let $B^{\prime}$ be a rogue assembly that satisfies
Lemma 4.3. We know the bond graph of $B^{\prime}$ must contain a loop. Let the
outermost loop of $B^{\prime}$ be the set of tiles along the outer path of the
bond graph, i.e., the loop that contains all other loops. Since we know
$B^{\prime}$ satisfies Lemma 4.3, it was built from two tree-bonded assemblies
that do not contain loops. This means the outer loop contains two binding
sites we will call $b_{1}$ and $b_{2}$. By filling out $T_{\mathcal{B}}$, we
calculate the max strength that can be obtained using each pair of binding
sites to construct the outer loop. Since $B^{\prime}$ is producible, the sum
of the strength of the binding sites must be greater than $\tau$. Thus, the
maximum binding strength using $b_{1}$ and $b_{2}$ as the outer loop will be
greater than $\tau$ as well.

Run Time: We check each of the $\mathcal{O}(|A|^{2})$ possible ways to combine
the target with itself and create a table if any binding sites are induced.
This table will be at most $\mathcal{O}(|A|^{2})$-size since we cannot have
more binding sites than the size of the assembly, although the number may be
substantially smaller. Computing each cell takes $\mathcal{O}(|A|\log\tau)$
time since we must perform integer addition for each pair of binding sites
where each integer is less than $\tau$. ∎

##  5 Conclusion

In this paper, we have addressed the long-standing open problem of the
complexity of verifying unique assembly within the 2-handed tile self-assembly
model and shown that the problem is coNP-complete even at temperature $\tau=2$
and in two dimensions. These are the smallest possible values for which this
problem can be hard, as both temperature-1 self-assembly and 1-dimensional
self-assembly have established polynomial time verification solutions. Given
this hardness, we explored a natural scenario where this problem might be more
tractable, and showed that restricting the input assemblies to tree-bonded
assemblies allows for an efficient $\mathcal{O}(|A|^{5}\log\tau)$-time unique
assembly verification algorithm.

#### Future Work.

While we have resolved the general question of unique assembly verification in
the 2HAM, as well as addressed a natural restricted case of tree-bonded
assemblies, there remain important directions for future research.

  * •

Our hardness reduction utilizes a tile set that is roughly the size of the
input assembly. In fact, all hardness results in the literature for the
2-handed self-assembly model have this property. Yet, the computational power
of tile self-assembly allows for the self-assembly of large assemblies with
much smaller tile sets, as seen in the efficient self-assembly of squares, or
the implementation of “Busy Beaver” Turing machines [23]. This leads to the
question of how hard unique assembly verification is when the focus is on
large assemblies, but substantially smaller tile sets. Does the hardness scale
with the larger assemblies, or is it tied to the size of the tile sets? Is
there some form of fixed-parameter tractability for the unique assembly
verification problem?

  * •

We proved that UAV for the multiple tile (or q-tile) model is coNP-complete
with polynomial-sized assemblies attaching. Is UAV polynomial in the multiple
tile model and the 2HAM in the case where every producible, except the one
that grows into the terminal assembly, is bounded by a constant?

  * •

A related question about UAV in the aTAM and the 2HAM is the number of two-
handed operations actually required to make the problem hard. If we allowed
all subassemblies to grow only by single tile attachments, how many two-handed
operations to combine those subassemblies are needed for UAV to remain hard?
Does the problem remain hard if only one two-handed operation is allowed? The
ability to more efficiently construct shapes by assembling parts separately
has been studied in other models as well [24].

  * •

Another direction initiated by our efficient tree assembly algorithm is the
consideration of other natural restricted classes of the UAV problem. For
example, trees yield efficient verification and have a genus-0 connectivity
graph, while our hardness reduction utilizes a high-genus assembly. How does
unique assembly verification scale with respect to the genus of an assembly’s
connectivity graph? A related question involves verification for _fully
connected_ assemblies, a previously-studied concept [13] in which assemblies
include positive bonds between all neighboring tiles. Is UAV still hard under
this restriction?

  * •

For tree-bonded shapes, does a more efficient and faster UAV algorithm exist?

## References

  * [1] Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, and Paul W. K. Rothemund, _Combinatorial optimization problems in self-assembly_ , Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 23–32.
  * [2] Pankaj K. Agarwal, Boris Aronov, Tzvika Geft, and Dan Halperin, _On two-handed planar assembly partitioning with connectivity constraints_ , Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 (Dániel Marx, ed.), SIAM, 2021, pp. 1740–1756.
  * [3] Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanes, and Robert T. Schweller, _Complexities for generalized models of self-assembly_ , SIAM Journal on Computing 34 (2005), no. 6, 1493–1515.
  * [4] David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie, _The complexity of multiple handed self-assembly_ , Unconventional Computation and Natural Computation (Cham) (Irina Kostitsyna and Pekka Orponen, eds.), Springer International Publishing, 2021, pp. 1–18.
  * [5] David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie, _Complexity of verification in self-assembly with prebuilt assemblies_ , Under Submission, 2021.
  * [6] , _Covert computation in staged self-assembly: Verification is pspace-complete_ , Proceedings of the 29th European Symposium on Algorithms, ESA’21, 2021.
  * [7] Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, David Furcy, Matthew J. Patitz, Robert Schweller, Scott M. Summers, and Andrew Winslow, _On the effects of hierarchical self-assembly for reducing program-size complexity_ , Theoretical Computer Science 894 (2021), 50–78.
  * [8] Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M Summers, and Andrew Winslow, _Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM_ , 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Leibniz International Proceedings in Informatics (LIPIcs), vol. 20, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2013, pp. 172–184.
  * [9] Angel A. Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie, _Covert Computation in Self-Assembled Circuits_ , Algorithmica 83 (2021), 531–552, arXiv:1908.06068.
  * [10] Cameron Chalk, Dominic Fernandez, Alejandro Huerta, Mario Maldonado, Robert Schweller, and Leslie Sweet, _Strict self-assembly of fractals using multiple hands_ , Algorithmica 76 (2014).
  * [11] Ho-Lin Chen and David Doty, _Parallelism and time in hierarchical self-assembly_ , SIAM Journal on Computing 46 (2017), no. 2, 661–709, Preliminary version appeared in SODA 2012.
  * [12] Erik D Demaine, Martin L Demaine, Sándor P Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T Schweller, and Diane L Souvaine, _Staged self-assembly: nanomanufacture of arbitrary shapes with o(1) glues_ , Natural Computing 7 (2008), no. 3, 347–370.
  * [13] Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, and Arne Schmidt, _New geometric algorithms for fully connected staged self-assembly_ , Theoretical Computer Science 671 (2017), 4–18.
  * [14] David Doty, _Theory of algorithmic self-assembly_ , Communications of the ACM 55 (2012), no. 12, 78–88.
  * [15] , _Producibility in hierarchical self-assembly_ , Unconventional Computation and Natural Computation (Cham) (Oscar H. Ibarra, Lila Kari, and Steffen Kopecki, eds.), Springer International Publishing, 2014, pp. 142–154.
  * [16] Algorithmic Self-Assembly Research Group, _VersaTile_ , https://github.com/asarg/VersaTile, 2014.
  * [17] Jacob Hendricks and Joseph Opseth, _Self-assembly of 4-sided fractals in the two-handed tile assembly model_ , Natural Computing 18 (2018), 75–92.
  * [18] Donald E. Knuth and Arvind Raghunathan, _The problem of compatible representatives_ , SIAM Journal on Discrete Mathematics 5 (1992), no. 3, 422–427.
  * [19] Pierre-’Etienne Meunier, , and Damien Woods, _The non-cooperative tile assembly model is not intrinsically universal or capable of bounded turing machine simulation_ , STOC: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Association for Computing Machinery, 2017, pp. 328–341.
  * [20] Pierre-’Etienne Meunier, Damien Regnault, and Damien Woods, _The program-size complexity of self-assembled paths_ , STOC: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Association for Computing Machinery, 2020, pp. 727–737.
  * [21] Matt Patitz, _Pytas_ , http://self-assembly.net/wiki/index.php?title=PyTAS.
  * [22] Matthew J. Patitz, _An introduction to tile-based self-assembly and a survey of recent results_ , Natural Computing 13 (2014), no. 2, 195–224.
  * [23] Paul WK Rothemund and Erik Winfree, _The program-size complexity of self-assembled squares_ , Proceedings of the thirty-second annual ACM symposium on Theory of computing, 2000, pp. 459–468.
  * [24] Arne Schmidt, Sheryl Manzoor, Li Huang, Aaron Becker, and Sándor P. Fekete, _Efficient parallel self-assembly under uniform control inputs_ , Robotics and Automation Letters 3 (2018), 3521–3528.
  * [25] Robert Schweller, Andrew Winslow, and Tim Wylie, _Complexities for high-temperature two-handed tile self-assembly_ , DNA Computing and Molecular Programming (Robert Brijder and Lulu Qian, eds.), Springer International Publishing, 2017, pp. 98–109.
  * [26] , _Verification in staged tile self-assembly_ , Natural Computing 18 (2019), no. 1, 107–117.
  * [27] Erik Winfree, _Algorithmic self-assembly of DNA_ , Ph.D. thesis, California Institute of Technology, June 1998.
  * [28] Erik Winfree, Rebecca Schulman, and Constantine Evans, _The xgrow simulator_ , https://www.dna.caltech.edu/Xgrow/.
  * [29] Damien Woods, _Intrinsic universality and the computational power of self-assembly_ , Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 373 (2015), no. 2046, 20140214.
  * [30] Damien Woods, David Doty, Cameron Myhrvold, Joy Hui, Felix Zhou, Peng Yin, and Erik Winfree, _Diverse and robust molecular algorithms using reprogrammable dna self-assembly_ , Nature 567 (2019), no. 7748, 366–372.


# Chain-of-Thought Hub: A Continuous Effort to
Measure Large Language Models’ Reasoning Performance

Yao Fu♠ Litu Ou♠ Mingyu Chen♠ Yuhao Wan  Hao Peng♣ Tushar Khot♣

###### Abstract

As large language models (LLMs) are continuously being developed, their
evaluation becomes increasingly important yet challenging. This work proposes
Chain-of-Thought Hub, an open-source evaluation suite on the multi-step
reasoning capabilities of large language models. We are interested in this
setting for two reasons: (1) from the behavior of GPT and PaLM model family,
we observe that complex reasoning is likely to be a key differentiator between
weaker and stronger LLMs; (2) we envisage large language models to become the
next-generation computational platform and foster an ecosystem of LLM-based
new applications, this naturally requires the foundation models to perform
complex tasks that often involve the composition of linguistic and logical
operations. Our approach is to compile a suite of challenging reasoning
benchmarks to track the progress of LLMs. Our current results show that: (1)
model scale clearly correlates with reasoning capabilities; (2) As of May
2023, Claude-v1.3 and PaLM-2 are the only two models that are comparable with
GPT-4, while open-sourced models still lag behind; (3) LLaMA-65B performs
closely to code-davinci-002, indicating that with successful further
development such as reinforcement learning from human feedback (RLHF), it has
great potential to be close to GPT-3.5-Turbo. Our results also suggest that
for the open-source efforts to catch up, the community may focus more on
building better base models and exploring RLHF.

Machine Learning, ICML

♠University of Edinburgh University of Washington ♣Allen Institute for AI
{yao.fu, s1970716<EMAIL_ADDRESS><EMAIL_ADDRESS>{haop,
<EMAIL_ADDRESS>https://github.com/FranxYao/chain-of-thought-hub

##  1 Introduction

Recently, the field of AI has been significantly impressed by the advances in
large language models. LLMs exhibit multi-dimensional capabilities, and their
evaluation is challenging. Generally, tuning a base language model into a
chatbot is relatively easy, as demonstrated by the large variety of LLaMA-
based (Touvron et al., 2023) models like Alpaca (Taori et al., 2023), Vicuna
(Chiang et al., 2023), Koala (Geng et al., 2023), Dolly (Databricks, 2023),
and so on. In a chitchat, all these models may perform superficially similarly
to GPT-3.5-Turbo (Gudibande et al., 2023). At the current stage, the community
is eager to know what are the key factors that clearly differentiate the
better-performing models from the underperforming ones.

In this work, we consider the evaluation of complex reasoning. As noted by
OpenAI (2023b), “In a casual conversation, the distinction between GPT-3.5 and
GPT-4 can be subtle. The difference comes out when the complexity of the task
reaches a sufficient threshold”. A similar observation is made by the Google
PaLM model family, as their developers discover that large models’ chain-of-
thought reasoning capability is clearly stronger than smaller models (Wei et
al., 2022b, a). These observations indicate that the ability to perform
complex tasks is a key metric.

The capability of performing complex reasoning is crucial for the models to
become the next-generation computation platform. One example initiative is
LangChain111https://github.com/hwchase17/langchain where developers build
applications powered by backend LLM engines, which generally require the model
to perform complex tasks. Here the vision of pushing LLMs as the foundation of
a new computational ecosystem also serves as a strong motivation to measure
the models’ reasoning performance.

To incentivize the research efforts in improving language models’ reasoning
performance, we propose the chain-of-thought hub (CoT Hub), a continuous open-
source effort that tracks LLMs’ reasoning capability using a carefully curated
evaluation suite. CoT Hub is the first comprehensive comparison of very large
LMs on reasoning benchmarks and currently consists of 19 major language
models’ (including the GPT, Claude, PaLM and LLaMA) performance on 6
benchmarks and more than 100 subtasks (including bi-lingual reasoning
capabilities in Chinese), and we are continuously adding new models and
datasets.

Observations made in CoT Hub shed light on many insights into LLM development:
(1) the reasoning performance of LLMs highly correlates with models’ scales;
(2) as of May 2023, PaLM and
Claude222https://www.anthropic.com/index/introducing-claude are the only two
model families that are comparable to (yet slightly worse than) the GPT model
family; (2) LLaMA 65B (Touvron et al., 2023) the strongest open LLM to date,
performs closely to code-davinci-002, the base model of GPT-3.5
family333https://platform.openai.com/docs/model-index-for-researchers. This
indicates that if aligned properly (by doing supervised finetuning (SFT) and
reinforcement learning from human feedback (RLHF) right) LLaMA 65B can
potentially improve further and perform on par with ChatGPT-3.5. We hope our
work gives meaningful guidance to the community’s development of deployable
LLMs.

##  2 Method

In this section we discuss the construction of Chain-of-Thought Hub. We first
discuss our method for test data collection, then we discuss how we obtain the
model performance on our test suite. Our main goal is to curate a high-quality
collection of datasets that (1) is closely related to the actual usage of
LLMs; (2) clearly differentiate the performance of stronger and weaker
language models. We consider the following datasets:

GSM8k

A widely used math reasoning datasets consisting of 8k problems that jointly
test models’ ability of arithmetic reasoning and composing math steps using
language (Cobbe et al., 2021).

MATH

A suite of challenging datasets consisting of 12k problems within 7 categories
testing the models’ advanced math and science reasoning. The problems in this
dataset are very hard because they come from mathematics competitions written
in Latex. Even GPT-4 has only 42.5% performance (Hendrycks et al., 2021).

MMLU

An evaluation suite of 15k problems within 57 subjects testing model’s high-
school and college-level knowledge and reasoning (Hendrycks et al., 2020).

BigBench Hard

A suite of language and symbolic reasoning tasks consisting 6.5k problems
within 23 subsets that are particularly suitable for testing chain-of-thought
prompting (Suzgun et al., 2022).

HumanEval

A handwritten dataset of 164 Python programming problems with text comments
and docstrings testing the models’ coding ability (Chen et al., 2021).

C-Eval

A Chinese evaluation suite for foundation models consisting of 13k multi-
choice questions spanning 52 diverse disciplines and four difficulty levels
(Huang et al., 2023).

We note that most of these datasets are already used in the evaluation of
leading large language models, such as GPT-4 (OpenAI, 2023a) and PaLM-2 (Anil
et al., 2023).

Few-Shot Chain-of-thought Prompting We use few-shot chain-of-thought prompting
to evaluate LLMs. This marks a clear difference between our evaluation and the
majority of other concurrent evaluations like HeLM (Liang et al., 2022), as
most of them use answer-only prompting. We also emphasize that we use few-
shot, rather than zero-shot prompting, because few-shot is a capability that
exist in both pretrained and instruction-tuned checkpoints, v.s., zero-shot is
more suitable for instruction-tuned checkpoints and may under-estimate the
pretrained checkpoints.

Comparison to existing and concurrent work There are many great existing
evaluation suites for large language models, such as HeLM, Chatbot
Arena444https://leaderboard.lmsys.org/, and Open LLM
Leaderboard555https://huggingface.co/spaces/HuggingFaceH4/open_llm_leaderboard.
The major difference between this work and these works are: (1) HeLM evaluates
a significantly wider spectrum of tasks while we focus on evaluating
reasoning. Most of the results from this work use chain-of-thought prompting
(hence the name “Chain-of-Thought Hub”) whereas HeLM mainly uses answer-only
prompting (without CoT). (2) Chatbot Arena evaluate the dialog user preference
we evaluate reasoning. (3) Open LLM Leaderboard focus on open-sourced LLMs, we
jointly consider major LLMs, either open-sourced or not.

Using final answer accuracy as a proxy for reasoning capability Most of the
datasets we consider share one pattern: to reach the final answer (either a
number for math problems, a choice for multi-choice problems, or a fixed
output for coding), the model needs to figure out the intermediate steps
toward that answer. When evaluating, we only use the final answer accuracy but
do not consider the correctness of intermediate steps. This is because
empirically, the correctness of intermediate steps is strongly correlated with
the final accuracy. If the intermediate steps are very wrong, the model is
less likely to reach the final answer. If the final answer is correct, the
intermediate steps are generally good enough (Wei et al., 2022b; Lewkowycz et
al., 2022).

##  3 Experiments

Table 1:  Overall model performance on Chain-of-Thought Hub. Numbers with an asterisk* are from our test scripts. For model types, base means the model checkpoint after pretraining, SIFT means supervised instruction finetuning. Others are from their corresponding papers. We observe: (1) there exist a gap between leading LLMs (GPT, Claude and PaLM) and open-source (LLaMA and FlanT5); (2) most leading LLMs are after RLHF, indicating the opportunity of improving open-sourced models using this technique; (3). model performance is generally correlated with model scale, indicating further opportunities in scaling, especially for open-source models. We further highlight that among open-sourced models, LLaMA 65B performs close to code-davinci-002, the base model of ChatGPT. This suggests that if RLHF is done right on LLaMA 65B, it may become close to ChatGPT.  Model | #Params | Type | GSM8k | MATH | MMLU | BBH | HumanEval | C-Eval
---|---|---|---|---|---|---|---|---
GPT-4 | ? | RLHF | 92.0 | 42.5 | 86.4 | - | 67.0 | 68.7*
claude-v1.3 | ? | RLHF | 81.8* | - | 74.8* | 67.3* | - | 54.2*
PaLM-2 | ? | Base | 80.7 | 34.3 | 78.3 | 78.1 | - | -
gpt-3.5-turbo | ? | RLHF | 74.9* | - | 67.3* | 70.1* | 48.1 | 54.4*
claude-instant-v1.0 | ? | RLHF | 70.8* | - | - | 66.9* | - | 54.9*
text-davinci-003 | ? | RLHF | - | - | 64.6 | 70.7 | - | -
code-davinci-002 | ? | Base | 66.6 | 19.1 | 64.5 | 73.7 | 47.0 | -
Minerva | 540B | SIFT | 58.8 | 33.6 | - | - | - | -
Flan-PaLM | 540B | SIFT | - | - | 70.9 | 66.3 | - | -
Flan-U-PaLM | 540B | SIFT | - | - | 69.8 | 64.9 | - | -
PaLM | 540B | Base | 56.9 | 8.8 | 62.9 | 62.0 | 26.2 | -
text-davinci-002 | ? | SIFT | 55.4 | - | 60.0 | 67.2 | - | -
PaLM | 64B | Base | 52.4 | 4.4 | 49.0 | 42.3 | - | -
LLaMA | 65B | Base | 50.9 | 10.6 | 63.4 | - | 23.7 | 38.8*
LLaMA | 33B | Base | 35.6 | 7.1 | 57.8 | - | 21.7 | -
LLaMA | 13B | Base | 17.8 | 3.9 | 46.9 | - | 15.8 | -
Flan-T5 | 11B | SIFT | 16.1* | - | 48.6 | 41.4 | - | -
LLaMA | 7B | Base | 11.0 | 2.9 | 35.1 | - | 10.5 | -
Flan-T5 | 3B | SIFT | 13.5* | - | 45.5 | 35.2 | - | -
Figure 1:  X-axis means the log of the model scale measured in billion
parameters. We observe that model performance is generally correlated with
scale, approximately showing a log-linear trend. Models without disclosing
their scale generally perform better than models disclosing scale information.
Our observations also indicate that the open-source community may still needs
to explore/ figure out “the moat” about the scaling and RLHF for further
improvements.

First we discuss the model families we consider. We focus on the popular
models in production, including GPT, Claude, PaLM, LLaMA, and T5 model
families, specifically:

OpenAI GPT

including GPT-4 (currently strongest), GPT-3.5-Turbo (faster but less
capable), text-davinci-003, text-davinci-002, and code-davinci-002 (important
previous versions before Turbo). See Fu & Khot (2022) for a comprehensive
discussion.

Anthropic Claude

including claude-v1.3 (slower but more capable) and claude-instant-v1.0
(faster but less capable)666https://console.anthropic.com/docs/api/reference.
Strong competitor’s GPT models.

Google PaLM

including PaLM, PaLM-2, and their instruction-tuned versions (FLan-PaLM and
Flan-U-PaLM). Strong base and instruction-tuned models.

Meta LLaMA

including the 7B, 13B, 33B and 65B variants. Important open-sourced base
models.

Google FlanT5

instruction-tuned T5 models demonstrating strong performance in the smaller
model regime.

We report these models’ performance on our CoT Hub suite. We note that due to
the wide spectrum of the tasks and models we consider, the evaluation is
nontrivial and even running inference takes effort. In addition, there are
models that do not offer public access (such as PaLM), such that evaluating
them is difficult. For these reasons, we report numbers using the following
strategy: if the performance of a model is already reported in a paper, we
refer to that paper; otherwise, we test them by ourselves. Note that this
strategy is not comprehensive, as we still have a fraction of untested non-
public models on some datasets. This is partly the reason we view our CoT Hub
as a continuous effort.

Table 1 shows the overall results. We rank the models using GSM8k performance
because it is a classical benchmark testing models’ reasoning capabilities.
Numbers marked by an asterisk are tested by ourselves, others are from the
following sources: GPT-4 and PaLM-2 results are from their technical report
(OpenAI, 2023a; Anil et al., 2023) respectively; GPT-3.5-Turbo’s performance
on HumanEval is also from OpenAI (2023a). Text-davinci-003, code-davinci-002
and text-davinci-002 performance are from the appendix in Chung et al. (2022)
and from Fu et al. (2022). Minerva’s performance is from Lewkowycz et al.
(2022). PaLM’s performance is from Chowdhery et al. (2022). Flan-PaLM and
FlanT5 performance are from Chung et al. (2022). LLaMA’s performance is from
Touvron et al. (2023).

The gap between open-source and leading LLMs In general, we observe a
performance discrepancy between open-sourced models (like LLaMA and FlanT5)
and close-sourced models (GPT, Claude and PaLM). Importantly, the performance
of open-sourced models seems to be upper bounded by LLaMA 65B.

Leading LLMs are after RLHF We observe that except for PaLM-2, the top 6
models on the leaderboard are after reinforcement learning from human
feedback. This strongly indicates the effectiveness of RLHF. Given that RLHF
is still an underexplored area, we strongly encourage the community to study
more on this topic.

Correlation between model scale and reasoning We further study the
relationship between model scale and models’ reasoning performance by
visualizing model performance against model scale. Results are shown in Fig.
1. We see that: (1) generally, model performance is correlated with model
scale, showing approximately a log-linear trend; (2) models that do not
disclose their scale generally perform better than models that do, indicating
that there is still a gap between open-source and close-source.

On the potential of LLaMA-65B Finally, we would like to highlight the
impressive performance of LLaMA 65B. On MMLU it is close to code-davinci-002,
the base model of GPT-3.5 series. On GSM8k, it is worse (presumably because it
is not trained on code) but close and much better than other open-sourced
models (presumably because it is trained to Chinchilla-optimal Hoffmann et
al., 2022). Combining this observation with the fact that GPT-3.5-Turbo
(ChatGPT) is an RLHF model based on code-davinci-002, it may be possible to
reproduce ChatGPT based on LLaMA 65B by applying the RLHF techniques discussed
in DeepMind Sparrow (Glaese et al., 2022) and Anthropic Claude (Askell et al.,
2021; Bai et al., 2022a, b).

##  4 Conclusion and Future Work

In this work, we propose Chain-of-Thought Hub, an open-source, continuous
effort to measure the reasoning capability of very large language models. Our
results clearly show the performance differences between smaller and larger
models, and between close-source and open-source models.

After carefully examining the results, we show two important directions for
further improving open-sourced models: building better base models and
exploring RLHF. We also point out the great potential of LLaMA 65B: if aligned
properly by better SFT and RLHF, it could be possible to perform on par with
ChatGPT-3.5.

In the future, we plan to further extend CoT Hub by: (1) including more
carefully chozen reasoning datasets, especially datasets measuring commonsense
reasoning, math theorem proving, and the ability to call outside APIs; (2)
including more language models, such as LLaMA-based, instruction-finetuned
models like Vicuna777https://lmsys.org/blog/2023-03-30-vicuna/ and models
through API access like Cohere888https://cohere.com/generate and PaLM-2 chat-
bison-001999https://cloud.google.com/vertex-ai. (3) exploring methods for
solving MATH, the probably most challenging datasets (recall that it consists
of math- ematics competitions written in Latex), by calling APIs that compute
symbolic and numerical calculus (like Wolfram
Alpha101010https://www.wolframalpha.com/). In summary, we believe our work
serves as an evaluation platform that guides the development of open-source
large language models.

## References

  * Anil et al. (2023) Anil, R., Dai, A. M., Firat, O., Johnson, M., Lepikhin, D., Passos, A., Shakeri, S., Taropa, E., Bailey, P., Chen, Z., et al.  Palm 2 technical report.  _arXiv preprint arXiv:2305.10403_ , 2023.
  * Askell et al. (2021) Askell, A., Bai, Y., Chen, A., Drain, D., Ganguli, D., Henighan, T., Jones, A., Joseph, N., Mann, B., DasSarma, N., et al.  A general language assistant as a laboratory for alignment.  _arXiv preprint arXiv:2112.00861_ , 2021.
  * Bai et al. (2022a) Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_ , 2022a.
  * Bai et al. (2022b) Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKinnon, C., et al.  Constitutional ai: Harmlessness from ai feedback.  _arXiv preprint arXiv:2212.08073_ , 2022b.
  * Chen et al. (2021) Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ , 2021.
  * Chiang et al. (2023) Chiang, W.-L., Li, Z., Lin, Z., Sheng, Y., Wu, Z., Zhang, H., Zheng, L., Zhuang, S., Zhuang, Y., Gonzalez, J. E., Stoica, I., and Xing, E. P.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023.  URL https://lmsys.org/blog/2023-03-30-vicuna/.
  * Chowdhery et al. (2022) Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_ , 2022.
  * Chung et al. (2022) Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, E., Wang, X., Dehghani, M., Brahma, S., et al.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv:2210.11416_ , 2022.
  * Cobbe et al. (2021) Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_ , 2021.
  * Databricks (2023) Databricks.  Free dolly: Introducing the world’s first truly open instruction-tuned llm.  Blog post, April 2023.  URL https://www.databricks.com/blog/2023/04/12/dolly-first-open-commercially-viable-instruction-tuned-llm.
  * Fu & Khot (2022) Fu, Yao; Peng, H. and Khot, T.  How does gpt obtain its ability? tracing emergent abilities of language models to their sources.  _Yao Fu’s Notion_ , Dec 2022.  URL https://yaofu.notion.site/How-does-GPT-Obtain-its-Ability-Tracing-Emergent-Abilities-of-Language-Models-to-their-Sources-b9a57ac0fcf74f30a1ab9e3e36fa1dc1.
  * Fu et al. (2022) Fu, Y., Peng, H., Sabharwal, A., Clark, P., and Khot, T.  Complexity-based prompting for multi-step reasoning.  _arXiv preprint arXiv:2210.00720_ , 2022.
  * Geng et al. (2023) Geng, X., Gudibande, A., Liu, H., Wallace, E., Abbeel, P., Levine, S., and Song, D.  Koala: A dialogue model for academic research.  Blog post, April 2023.  URL https://bair.berkeley.edu/blog/2023/04/03/koala/.
  * Glaese et al. (2022) Glaese, A., McAleese, N., Trebacz, M., Aslanides, J., Firoiu, V., Ewalds, T., Rauh, M., Weidinger, L., Chadwick, M., Thacker, P., et al.  Improving alignment of dialogue agents via targeted human judgements.  _arXiv preprint arXiv:2209.14375_ , 2022.
  * Gudibande et al. (2023) Gudibande, A., Wallace, E., Snell, C., Geng, X., Liu, H., Abbeel, P., Levine, S., and Song, D.  The false promise of imitating proprietary llms.  _arXiv preprint arXiv:2305.15717_ , 2023.
  * Hendrycks et al. (2020) Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J.  Measuring massive multitask language understanding.  _arXiv preprint arXiv:2009.03300_ , 2020.
  * Hendrycks et al. (2021) Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J.  Measuring mathematical problem solving with the math dataset.  _NeurIPS_ , 2021.
  * Hoffmann et al. (2022) Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al.  Training compute-optimal large language models.  _arXiv preprint arXiv:2203.15556_ , 2022.
  * Huang et al. (2023) Huang, Y., Bai, Y., Zhu, Z., Zhang, J., Zhang, J., Su, T., Liu, J., Lv, C., Zhang, Y., Lei, J., et al.  C-eval: A multi-level multi-discipline chinese evaluation suite for foundation models.  _arXiv preprint arXiv:2305.08322_ , 2023.
  * Lewkowycz et al. (2022) Lewkowycz, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V., Slone, A., Anil, C., Schlag, I., Gutman-Solo, T., et al.  Solving quantitative reasoning problems with language models.  _arXiv preprint arXiv:2206.14858_ , 2022.
  * Liang et al. (2022) Liang, P., Bommasani, R., Lee, T., Tsipras, D., Soylu, D., Yasunaga, M., Zhang, Y., Narayanan, D., Wu, Y., Kumar, A., et al.  Holistic evaluation of language models.  _arXiv preprint arXiv:2211.09110_ , 2022.
  * OpenAI (2023a) OpenAI.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_ , 2023a.
  * OpenAI (2023b) OpenAI.  Gpt-4, 2023b.  URL https://openai.com/research/gpt-4.
  * Suzgun et al. (2022) Suzgun, M., Scales, N., Schärli, N., Gehrmann, S., Tay, Y., Chung, H. W., Chowdhery, A., Le, Q. V., Chi, E. H., Zhou, D., et al.  Challenging big-bench tasks and whether chain-of-thought can solve them.  _arXiv preprint arXiv:2210.09261_ , 2022.
  * Taori et al. (2023) Taori, R., Gulrajani, I., Zhang, T., Dubois, Y., Li, X., Guestrin, C., Liang, P., and Hashimoto, T. B.  Stanford alpaca: An instruction-following llama model.  https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * Touvron et al. (2023) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Wei et al. (2022a) Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et al.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_ , 2022a.
  * Wei et al. (2022b) Wei, J., Wang, X., Schuurmans, D., Bosma, M., Chi, E., Le, Q., and Zhou, D.  Chain of thought prompting elicits reasoning in large language models.  _arXiv preprint arXiv:2201.11903_ , 2022b.