# Topological Universality of the Art Gallery Problem

Jack Stade  University of Cambridge<EMAIL_ADDRESS>Jamie Tucker-Foltz
Harvard University<EMAIL_ADDRESS>
###### Abstract

We prove that any compact semi-algebraic set is homeomorphic to the solution
space of some art gallery problem. Previous works have established similar
universality theorems, but holding only up to homotopy equivalence, rather
than homeomorphism, and prior to this work, the existence of art galleries
even for simple spaces such as the Möbius strip or the three-holed torus were
unknown. Our construction relies on an elegant and versatile gadget to copy
guard positions with minimal overhead, and is thus simpler than previous
constructions, consisting of a single rectangular room with convex slits cut
out from the edges. We additionally show that both the orientable and non-
orientable surfaces of genus $n$ require galleries with only $O(n)$ vertices.

##  1 Introduction

An instance of the _art gallery problem_ consists of a polygon $P$ (which we
refer to as the _art gallery_), and the objective is to find a finite set of
points $G\subseteq P$ (the _guards_) of minimal cardinality such that every
point in $P$ is _visible_ to some guard, meaning that the line segment between
the point and the guard is contained within $P$. This problem was first
introduced by Viktor Klee in 1973 and has a long history. In 1986, Lee and Lin
[6] showed that the decision problem of determining whether there exists a
configuration with at most $k$ guards is NP-hard, but the problem is not known
to be in NP since there is no obvious succinct way to represent the guards’
coordinates in a solution (they might have to be irrational, even if all
polygon vertex coordinates are rational). In 2018, Abrahamsen, Adamaszek, and
Miltzow [1] showed that the problem is $\exists\mathbb{R}$-complete, mostly
settling the question of complexity (modulo the longstanding conjectures that
$\text{NP}\subsetneq\exists\mathbb{R}\subsetneq\text{PSPACE}$). Approximation
algorithms and lower bounds have also been studied; see Vaezi and Ghodsi [10]
for a recent overview.

Aside from complexity aspects, a parallel line of inquiry concerns the
topology of the space of solutions. Supposing that gallery $P$ requires
exactly $k$ guards at minimum, we let

$V(P):=\\{G\subseteq P\ |\ \left|{G}\right|=k\text{ and every $p\in P$ is
visible to some }g\in G\\}.$

The set $V(P)$ can consists of unordered sets of points of cardinality $k$,
which can be turned into a natural metric space using the Hausdorff distance

$d_{H}(G_{0},G_{1}):=\max_{i\in\\{0,1\\}}\max_{g\in G_{i}}\min_{g^{\prime}\in
G_{1-i}}d(g,g^{\prime}),$

where $d$ denotes the Euclidean distance on $\mathbb{R}^{2}$. Thus, for any
art gallery $P$, $V(P)$ is a topological space, so a natural question is, what
kinds of topological spaces can occur?

Aside from being a mathematical curiosity, this question is relevant to
complexity theory due to the connections between $\exists\mathbb{R}$-hardness
and topological universality. The most famous example is Mnëv’s theorem [8]
that any semi-algebraic set is homotopy-equivalent to the space of point
configurations of some order type, inspiring an eventual proof that order type
realizability is $\exists\mathbb{R}$-complete [9]. A _semi-algebraic_ set is a
finite union $\bigcup_{i=1}^{m}S_{i}$, where each $S_{i}$ is defined to be the
set of points in $\mathbb{R}^{n}$ $({x}_{1}{,}{x}_{2}{,}\dots,{x}_{n})$
satisfying a finite number of constraints of form
$P({x}_{1}{,}{x}_{2}{,}\dots,{x}_{n})\geq 0$ or
$P({x}_{1}{,}{x}_{2}{,}\dots,{x}_{n})>0$, where $P$ is a polynomial. The
canonical complete problem for $\exists\mathbb{R}$ is called ETR (Existential
Theory of the Reals), which asks whether a given semi-algebraic set is
nonempty. As a consequence of their reduction from ETR to the art gallery
problem, Abrahamsen et al. [1] show, for any compact semi-algebraic set $S$,
how to construct an art gallery $P$ such that $V(P)$ surjects continuously
onto $S$. However, they do not show that the mapping is injective, so this
fails to establish universality. In a recent paper, Bertschinger, El Maalouly,
Miltzow, Schnider, and Weber [2] show that any compact semi-algebraic set $S$
is homotopy-equivalent to $V(P)$ for some polygon $P$. They leave as an open
question whether $P$ can be constructed so that $V(P)$ is not just homotopy-
equivalent, but homeomorphic to $S$, with only the following list of spaces
shown to be captured up to homeomorphism:

  * •

$k$-clover (obtained by joining $k$ circles at a single point)

  * •

$k$-chain (obtained by connecting $k$ circles in a path with $k-1$ disjoint
line segments)

  * •

$4k$-necklace (obtained by connecting $k$ circles in a cycle with $k$ disjoint
line segments)

  * •

$k$-sphere

  * •

The torus

  * •

The 2-holed torus

The constructions for these spaces are all based on simple galleries with
solution spaces homeomorphic to a circle and an interval, which are combined
to give Cartesian products and then given simple additional constraints.
However, using these methods it is difficult to obtain more general spaces
because the geometry significantly limits the constraints that can be used.
Thus, prior to this work, homeomorphism universality was unknown even for
closed surfaces. Galleries for the real projective plane, Klein bottle, and
Möbius strip were explicitly left as open questions.

In this work, we settle the question of homeomorphism universality in the
affirmative:

######  Theorem 1.1.

For every compact semi-algebraic set $S\neq\emptyset$, there exists a polygon
$P$ such that $S$ is homeomorphic to $V(P)$.

In addition to yielding a strictly stronger result than that of Bertschinger
et al. [2], our construction is structurally simpler: the art gallery always
consists of a single rectangular room with two types of convex slits
repeatedly cut out of the edges. As an example, we explicitly draw an art
gallery for the Möbius strip (to the best resolution that can reasonably fit
on a page) in Figure 5.

The key ingredient in our approach is a novel gadget which “copies” a variable
(in effect adding a constraint of form $x_{i}=x_{j}$). Gadgets with similar
functions can also be found in Abrahamsen et al. [1]. Our gadget is an
improvement for the following reasons:

  * •

It is more versatile. In particular the polygon $P$ does not need to intersect
the convex hull of the segments being copied.

  * •

It works in more general contexts. The previous gadget uses constraints
created by the need for guards to see every point on the interior of the
polygon $P$. Our gadget works in the variant of the problem where guards only
need to see the boundary of the polygon.

Our general construction, which we present in Section 2, does not yield an
obvious bound on the size of $P$ (number of vertices) as a function of the
complexity of the space $S$. In Section 3, we refine our construction to show
that both the orientable and non-orientable surfaces of genus $n$ can be
captured by art galleries with only $O(n)$ vertices.

##  2 General construction

As in Bertschinger et al. [2], the starting point for our reduction is a
theorem by Hironaka [4] that any compact semialgebraic set can be triangulated
as a cubical complex. We begin by reviewing this result. Next, we introduce
our variable copying gadget and establish its key properties. Finally, we show
how to combine the gadgets to construct the art gallery. We illustrate our
construction using the Möbius strip as a running example.

###  2.1 Hironaka’s theorem

An abstract cubical complex is subset $K$ of a set

$I^{n}=\left\\{\left\\{\mathbf{x}\in[0,1]^{n}\ |\ x_{i_{1}}=c_{1},\dots
x_{i_{k}}=c_{k}\right\\}\ |\ 1\leq i_{1}<\dots<i_{k}\leq
n,\left(c_{1},\dots,c_{k}\right)\in\\{0,1\\}^{k}\right\\}$

of faces of an $n$ dimensional hypercube $[0,1]^{n}$ such that if $a\in K$ and
$b\in I^{n}$ and $b\subseteq a$, then $b\in K$. Every cubical complex
corresponds to a subset $|K|=\bigcup K$ of $[0,1]^{n}$, called its geometric
realization.

######  Theorem 2.1 (Bertschinger et al. [2], Lemma 3).

Any compact semi-algebraic set is homeomorphic to the geometric realization of
an abstract cubical complex.

###### Proof sketch..

Using Hironaka’s theorem [4], it is possible to show that any compact semi-
algebraic set is homeomorphic to the geometric realization of an abstract
simplicial complex (see Hoffman [5]). Additionally, it can be shown that any
abstract simplicial complex has an abstract cubic complex with a homeomorphic
geometric realization (see Blass and Wlodzimierz [3, Theorem 1.1]). ∎

Figure 1: A 4-dimensional geometric realization of a cubical complex
homeomorphic to a Möbius strip.

For example, the circle $S^{1}$ can be represented as the abstract cubical
complex

$\\{\\{\mathbf{x}\in[0,1]^{2}\ |\ x_{1}=0\\},\\{\mathbf{x}\in[0,1]^{2}\ |\
x_{1}=1\\},\\{\mathbf{x}\in[0,1]^{2}\ |\ x_{2}=0\\},\\{\mathbf{x}\in[0,1]^{2}\
|\ x_{2}=1\\}\\},$

in which case its geometric realization is the boundary of the unit square in
$\mathbb{R}^{2}$. The Möbius strip can be realized as a subset of the
4-dimensional hypercube as in Figure 1.

###  2.2 The variable and copying gadgets

The art gallery we construct will be an axis-aligned rectangle with several
slits removed from around the border. We refer to certain slits and
combinations of slits as _gadgets_. Our construction involves three kinds of
gadgets: _variable gadgets_ , _copying gadgets_ , and _clause gadgets_. Our
copying gadgets are based on the following geometric observation.

######  Lemma 2.2.

Let $L_{1}$ and $L_{2}$ be two distinct parallel lines in the plane, and let
$Z$ be a point strictly between $L_{1}$ and $L_{2}$. Let $f_{Z}:L_{1}\to
L_{2}$ be the map defined via inversion through $Z$, i.e., for $p\in L_{1}$,
$f_{Z}(p)$ is the intersection of the line $pZ$ with $L_{2}$. Then $f_{Z}$ is
linear (in the sense that it preserves ratios of distances between points on
$L_{1}$ and the corresponding points on $L_{2}$).

Figure 2:

###### Proof.

Without loss of generality, assume $L_{1}$ and $L_{2}$ are drawn aligned with
the $x$-axis as in Figure 2. Let $A$, $B$, and $C$ be three arbitrary distinct
points on $L_{1}$, and let $F$, $E$, and $D$ be their respective images under
$f_{Z}$. It is easy to see that $(AZB,FZE)$ and $(AZC,FZD)$ are pairs of
similar triangles. This means that the ratios of lengths of $AB$ to $FE$ and
$AC$ to $FD$ are equal, that is
$\frac{B_{x}-A_{x}}{F_{x}-E_{x}}=\frac{C_{x}-A_{x}}{F_{x}-D_{x}}$.
Rearranging, we have
$\frac{B_{x}-A_{x}}{C_{x}-A_{x}}=\frac{F_{x}-E_{x}}{F_{x}-D_{x}}$. ∎

The following lemma summarizes the key properties of the variable and copying
gadgets, which are depicted in Figure 3.

Figure 3: The variable and copying gadgets. The boundary of this section of
the art gallery consists of the entire outer profile (continuing above and
below the dashed lines at the top and bottom), involving line segments of all
colors. A pair of guards are constrained to patrol the line segments $GH$ and
$NO$ at the same $x$-coordinate. There are two variable gadgets, shown in
orange. The first one consists of the slits at points $F$, $I$, and $J$, which
enforces that one guard must patrol $GH$. The second consists of the slits at
points $M$, $P$, and $Q$, which enforces that the other guard must patrol
$NO$. The other two slits, $CBAD$ and $SUVT$, comprise the copying gadget,
which enforces that both guards have the same $x$-coordinate.

######  Lemma 2.3.

As long as all co-linearity relations and ordering relations between $x$ and
$y$ coordinates of highlighted points are as depicted in Figure 3, with no
other slits between the black dashed lines at the top and bottom, it follows
that:

  1. (1)

Any valid guard placement requires at least two guards between the dashed
lines.

  2. (2)

Such a configuration of two guards is valid if and only if the guards are
placed on line segments $GH$ and $NO$ at the same $x$-coordinate.

###### Proof.

To see point $F$, we must have at least one guard placed within the triangle
$FIK$; to see point $I$, we must have at least one guard placed within the
triangle $EFI$; to see point $M$, we must have at least one guard placed
within the triangle $MPR$; and to see point $P$, we must have at least one
guard placed within the triangle $LMP$. Clearly, there is no single guard that
can see all four of these points (as, for instance, triangles $EFI$ and $LMP$
are disjoint), which proves (1). Furthermore, any solution with only two
guards must have one guard on line segment $FI$ and another guard on line
segment $MP$, for otherwise at least one of the four triangles will not have a
guard in it. Given that the guards are on these line segments, the only way
that points $J$ and $Q$ will be visible is if one guard is on segment $GH$ and
the other guard is on $NO$.

Thus, to all that remains to prove (2) is that the two guards must have the
same $x$-coordinate. Let $\alpha$ be the location of the guard on $GH$, and
let $\beta$ be the location of guard on $NO$; our objective is to show that,
in any valid configuration, $\alpha_{x}=\beta_{x}$. We define the following
four additional points:

  * •

$\overline{\alpha}:=$ the intersection of line segment $AB$ with line $\alpha
C$

  * •

$\underline{\alpha}:=$ the intersection of line segment $UV$ with line $\alpha
S$

  * •

$\overline{\beta}:=$ the intersection of line segment $AB$ with line $\beta D$

  * •

$\underline{\beta}:=$ the intersection of line segment $UV$ with line $\beta
T$

Due to the obstructions by points $C$ and $D$, the guard at $\alpha$ can only
see $AB$ to the left of $\overline{\alpha}$, and the guard at $\beta$ can only
see $AB$ to the right of $\overline{\beta}$. If
$\overline{\alpha}_{x}<\overline{\beta}_{x}$, the line segment
$\overline{\alpha}\overline{\beta}$ will therefore not be seen by any guard,
so we must have that $\overline{\alpha}_{x}\geq\overline{\beta}_{x}$.
Similarly, the guard at $\alpha$ can only see $UV$ to the right of
$\underline{\alpha}$, and the guard at $\beta$ can only see $UV$ to the left
of $\underline{\beta}$, so we must have that
$\underline{\alpha}_{x}\leq\underline{\beta}_{x}$. Thus, in any valid
configuration of the two guards,

$\displaystyle\frac{\alpha_{x}-G_{x}}{H_{x}-G_{x}}$
$\displaystyle=\frac{B_{x}-\overline{\alpha}_{x}}{B_{x}-A_{x}}\ \ \ \ \
\text{(by Lemma \ref{lemInversionLinearity} with $Z:=C$)}$
$\displaystyle\leq\frac{B_{x}-\overline{\beta}_{x}}{B_{x}-A_{x}}$
$\displaystyle=\frac{\beta_{x}-N_{x}}{O_{x}-N_{x}}\ \ \ \ \ \text{(by Lemma
\ref{lemInversionLinearity} with $Z:=D$)}$
$\displaystyle=\frac{V_{x}-\underline{\beta}_{x}}{V_{x}-U_{x}}\ \ \ \ \
\text{(by Lemma \ref{lemInversionLinearity} with $Z:=T$)}$
$\displaystyle\leq\frac{V_{x}-\underline{\alpha}_{x}}{V_{x}-U_{x}}$
$\displaystyle=\frac{\alpha_{x}-G_{x}}{H_{x}-G_{x}}\ \ \ \ \ \text{(by Lemma
\ref{lemInversionLinearity} with $Z:=S$)}.$

Multiplying through by $(H_{x}-G_{x})$ and using the fact that $N_{x}=G_{x}$
and $O_{x}=H_{x}$, we have

$\alpha_{x}-G_{x}\leq\beta_{x}-G_{x}\leq\alpha_{x}-G_{x}.$

Thus, $\alpha_{x}=\beta_{x}$ in any valid configuration (and it is easy to
check that such a configuration is indeed valid), which proves (2). ∎

###  2.3 Constructing the art gallery

We are now ready to prove homeomorphism universality.

###### Proof of Theorem 1.1.

By Theorem 2.1, we may assume without loss of generality that $S$ is the
geometric realization of a nonempty cubical complex. This means that $S$ can
be described as a subset of $[0,1]^{n}$ whose coordinates
${x}_{1}{,}{x}_{2}{,}\dots,{x}_{n}$ satisfy some formula

$\phi_{S}\equiv\bigvee_{j=1}^{m^{\prime}}((x_{i^{\prime}_{j,1}}=c^{\prime}_{j,1})\wedge(x_{i^{\prime}_{j,2}}=c^{\prime}_{j,2})\wedge\dots\wedge(x_{i^{\prime}_{j,\ell^{\prime}}}=c^{\prime}_{j,\ell^{\prime}})),$

where each $i^{\prime}_{j,k}\in\\{1,2,\dots n\\}$ and
$c^{\prime}_{j,k}\in\\{0,1\\}$. The formula will always be in disjunctive
normal form (DNF), where each conjunctive clause corresponds to a face of the
cubical complex, so $\phi_{S}$ describes the set of points lying in at least
one such face. For example, the formula for the Möbius strip $M$ depicted in
Figure 1 has six clauses, one for each of the six 2-dimensional faces. To
write an explicit formula $\phi_{M}$, we choose a coordinate system where
$x_{4}=0$ corresponds to the points on the outer shell and enumerate the faces
as clauses by traversing the strip starting from the left-most depicted face
and proceeding next toward the back face:

$\displaystyle\phi_{M}\equiv$ $\displaystyle(x_{2}=0\wedge
x_{4}=0)\vee(x_{1}=0\wedge x_{4}=0)\vee(x_{1}=0\wedge x_{3}=1)$
$\displaystyle\vee$ $\displaystyle(x_{3}=1\wedge x_{4}=1)\vee(x_{2}=0\wedge
x_{4}=1)\vee(x_{2}=0\wedge x_{3}=0)$

We next rewrite $\phi_{S}$ in conjunctive normal form (CNF),

$\phi_{S}\equiv\bigwedge_{j=1}^{m}((x_{i_{j,1}}=c_{j,1})\vee(x_{i_{j,2}}=c_{j,2})\vee\dots\vee(x_{i_{j,\ell}}=c_{j,\ell})),$

by enumerating all tuples of constraints that take one constraint from each
clause. For example, since $\phi_{M}$ has 6 clauses in DNF, each of size 2,
the standard translation to CNF produces $2^{6}=64$ clauses, each of size 6.
However, after eliminating redundancies, we can simplify $\phi_{M}$ to

$\displaystyle\phi_{M}\equiv$ $\displaystyle(x_{1}=0\vee x_{2}=0\vee x_{3}=1)$
$\displaystyle\wedge$ $\displaystyle(x_{2}=0\vee x_{3}=1\vee x_{4}=0)$
$\displaystyle\wedge$ $\displaystyle(x_{1}=0\vee x_{2}=0\vee x_{4}=1)$ (1)
$\displaystyle\wedge$ $\displaystyle(x_{3}=0\vee x_{3}=1\vee x_{4}=0\vee
x_{4}=1)$ $\displaystyle\wedge$ $\displaystyle(x_{1}=0\vee x_{3}=0\vee
x_{4}=0\vee x_{4}=1).$

Figure 4: Illustration of the first step of the general construction (making
clause gadgets), starting from a CNF formula with $n$ variables and $m$
clauses. The full art gallery is shown in more detail for the Möbius strip in
Figure 5.

Starting from a rectangular art gallery, we make a narrow diagonal slit for
each clause $j$ in the top-right corner such that the regions $R_{j}$ of the
gallery that can see to the end of each slit extend downward to the left and
do not overlap, as shown in Figure 4. For each $i\in\\{1,2,3,\dots,n\\}$ we
define $X_{i}$ be tall, skinny, axis-aligned rectangular region such that the
convex hulls of the sets $X_{i}\cap(R_{1}\cup R_{2}\cup\dots\cup R_{m})$ do
not overlap in $y$-coordinates (in terms of Figure 4, the pink dashed lines
must not overlap in $y$-coordinates). It is always possible to guarantee this
non-overlapping property by making the gallery sufficiently tall and/or making
the clauses sufficiently close together.

Figure 5: An art gallery whose solution space is homeomorphic to a Möbius
strip, using the formula $\phi_{M}$ from (1). The horizontal gold dashes above
each variable are the line segments on which guards must walk, as in Figure 3.
The pink diagonal lines depict the regions $R_{j}$ that can see to the end of
each clause gadget slit; each of these regions must contain at least one
guard. The left wall must be placed sufficiently far to the left to ensure
that none of the variable/copy gadgets interfere with each other. As drawn,
this particular art gallery has 183 vertices.

In every clause $j$, for every constraint $x_{i_{j,k}}=c_{j,k}$, we add a
variable gadget in the left and right sides of the rectangle enforcing the
constraint that there is a guard on a short horizontal line segment (hereafter
a _guard segment_) spanning the width of $X_{i_{j,k}}$ whose endpoint lies
within $R_{j}$. If $c_{j,k}=0$, this will be the left endpoint, and if
$c_{j,k}=1$, this will be the right endpoint. We then add copying gadgets to
enforce that all guard segments placed in $X_{i}$ for the same $i$ must have
the same $x$-coordinate. If the left wall is moved sufficiently far to the
left and the cuts are made sufficiently small, we can realize the hypothesis
of Lemma 2.3 that the horizontal slice including every pair of consecutive
copying gadgets is drawn as in Figure 3, without any other guard segments
appearing between the dashed lines. It then follows from repeatedly applying
Lemma 2.3 that, letting $P_{0}$ be the polygon $P$ without the clause gadget
slits, $V(P_{0})$ consists of all solutions with one guard on each guard
segment, with guards within the same $X_{i}$ placed at the same
$x$-coordinate. There is thus a natural homeomorphism
$h:V(P_{0})\to[0,1]^{n}$, and from the way the clause gadgets were
constructed, it clearly follows that $V(P)$ consists of all solutions in which
$\phi_{S}$ is satisfied under $h$. Thus, $V(P)$ is homeomorphic to $S$. ∎

##  3 Efficient construction for closed surfaces

Even if a space can be triangulated as a cubical complex with relatively few
faces, the conversion from DNF to CNF can exponentially blow up the number of
clauses, and thus the size of the art gallery. Here we show that an important
class of topological spaces, namely the closed surfaces, can occur as
solutions to art galleries with linearly many vertices.

######  Theorem 3.1.

There are polygons $P_{n}$, $Q_{n}$ with $O(n)$ vertices such that $V(P_{n})$
is homeomorphic to the closed orientable surface of genus $n$ and $V(Q_{n})$
is homeomorphic to the closed non-orientable surface of genus $n$.

###### Proof.

We know by Theorem 1.1 that such polygons exist for $n\in\\{0,1\\}$, but the
number of vertices of these galleries have no effect on the asymptotic
properties of $P_{n}$ and $Q_{n}$, so we may ignore these cases.

It is well known that, for $n\geq 2$, the orientable surface of genus $n$ can
be obtained as the connected sum of $n$ copies of a torus,
$T^{2}\\#T^{2}\\#\dots\\#T^{2}$, while the non-orientable surface of genus $n$
can be obtained as the connected sum of $n$ copies of the real projective
plane
$\mathbb{R}\mathbb{P}^{2}\\#\mathbb{R}\mathbb{P}^{2}\\#\dots\\#\mathbb{R}\mathbb{P}^{2}$
(see, e.g., the textbook by Massey [7]). The connect sum $R\\#R$ is ordinarily
defined as removing an open disk from two copies of $R$ and gluing their
boundaries together. For 2-dimensional surfaces, this is equivalent to gluing
the disk boundaries to opposite ends of a cylindrical tube, which is the
formulation we use in this construction. Thus, let $R$ be either $T^{2}$ or
$\mathbb{R}\mathbb{P}^{2}$. By Theorem 2.1, we know there is some $j$ such
that $R$ is homeomorphic to $\left|{C}\right|$, the geometric realization of a
cubical complex $C$ with $j$ variables. Let
${x}_{1}{,}{x}_{2}{,}\dots,{x}_{j}$ be these variables and write
$\mathbf{x}=({x}_{1}{,}{x}_{2}{,}\dots,{x}_{n})$.

Note that $C$ has at least two $2$-dimensional faces. Let $C_{1}$ be a cubical
complex obtained by removing a face $f_{1}$ of dimension $2$ from $C$, and
$C_{2}$ obtained by removing a different face. For $i\in\\{1,2\\}$, define
$B_{i}$ to be the cubical complex containing $f_{i}$ and its boundary, so that
$|C_{i}|\cap|B_{i}|$ is the boundary of the removed disc (see Figure 6).

Figure 6:  Visualisation of $|C_{1}|$, $|C_{2}|$, $|B_{1}|$ and $|B_{2}|$. In
reality, $C$ should be a complex for $T^{2}$ or $\mathbb{R}\text{P}^{2}$,
rather than $S^{1}$ as shown. The figure is just meant to convey the
construction at a schematic level.

Define a new variable $x_{0}$ and fix constants
$k_{0}=0<k_{1}<\dots<k_{n-2}<1=k_{n-1}$. Then the following formulas express
the property that a point $\mathbf{x}$ is contained in $R\\#R\\#\dots\\#R$
(see Figure 7 for a visualization). For $n$ even we have

$\displaystyle(\mathbf{x}\in|C_{2}|\vee
x_{0}=0)\wedge(\mathbf{x}\in|C_{1}|\vee x_{0}=1)\wedge$
$\displaystyle(\mathbf{x}\in|B_{1}|\vee 0\leq x_{0}\leq k_{1}\vee k_{2}\leq
x_{0}\leq k_{3}\vee\dots\vee k_{n-3}\leq x_{0}\leq k_{n-2}\vee x_{0}=1)\wedge$
$\displaystyle(\mathbf{x}\in|B_{2}|\vee k_{1}\leq x_{0}\leq k_{2}\vee
k_{3}\leq x_{0}\leq k_{4}\vee\dots\vee k_{n-2}\leq x_{0}\leq 1),$

and for $n$ odd we have

$\displaystyle(\mathbf{x}\in|C_{2}|\vee x_{0}=0\vee
x_{0}=1)\wedge\mathbf{x}\in|C_{1}|\wedge$
$\displaystyle(\mathbf{x}\in|B_{1}|\vee 0\leq x_{0}\leq k_{1}\vee k_{2}\leq
x_{0}\leq k_{3}\vee\dots\vee k_{n-2}\leq x_{0}\leq 1)\wedge$
$\displaystyle(\mathbf{x}\in|B_{2}|\vee k_{1}\leq x_{0}\leq k_{2}\vee
k_{3}\leq x_{0}\leq k_{4}\vee\dots\vee k_{n-3}\leq x_{0}\leq k_{n-2}\vee
x_{0}=1).$

Note that these spaces are not in general the geometric realization of a
cubical complex in $x_{0},{x}_{1}{,}{x}_{2}{,}\dots,{x}_{j}$ because of the
constraints on $x_{0}$; nevertheless, we will construct art galleries for
them.

Figure 7:  A schematic visualization for our constructions of
$R\\#R\\#\dots\\#R$ for even $n$ (left) and odd $n$ (right). For all values of
$x_{0}$, we require $\mathbf{x}\in|C_{1}|$ and $\mathbf{x}\in|C_{2}|$, except
for $x_{0}=0$ or $x_{0}=1$ where one of these constraints is dropped to cap
the hole at the end. For $k_{i}<x_{0}<k_{i+1}$, $\mathbf{x}$ must be in either
$|B_{1}|\cap|C_{1}|$ or $|B_{2}|\cap|C_{2}|$ depending on the parity of $i$.
This creates tubes connecting the copies of $R$.

We can write these expressions in CNF with terms of form $x_{i}=0$, $x_{i}=1$,
or $k_{i}\leq x_{0}\leq k_{i+1}$. We write the constraint
$\mathbf{x}\in|B_{1}|$ in CNF as

$\phi_{B_{1}}:=\bigwedge_{\ell=1}^{p}\bigvee_{m=1}^{q_{\ell}}t_{\ell,m},$

where each $t_{\ell,m}$ is a term of form e.g. $x_{1}=0$. We may thus rewrite

$\displaystyle\mathbf{x}\in|B_{1}|\vee 0\leq x_{0}\leq k_{1}\vee k_{2}\leq
x_{0}\leq k_{3}\vee\dots\vee k_{n-2}\leq x_{0}\leq 1$ $\displaystyle\equiv$
$\displaystyle\bigwedge_{\ell=1}^{p}\left(\left(\bigvee_{m=1}^{q_{\ell}}t_{\ell,m}\right)\vee
0\leq x_{0}\leq k_{1}\vee k_{2}\leq x_{0}\leq k_{3}\vee\dots\vee k_{n-2}\leq
x_{0}\leq 1\right).$

To add the constraints on $x_{0}$ to each clause involving $x_{0}$, we must
make a small modification to the construction from Section 2. Instead of
having the clause gadgets along the top wall, we extend the top wall upward
and put these gadgets along the right wall. It is easy to see that this does
not affect our ability to create the constraints on $\mathbf{x}$. We then add
the constraints on $x_{0}$ to each clause as in Figure 8; if all clause
gadgets are vertically translated copies of each other, then all guard
segments for $x_{0}$ across the different clauses can be placed at the same
$x$-coordinates.

Figure 8:  Guard segments for $x_{0}$. We place the first guard segment so
that the lower line in the wedge intersects it a $0$, and the upper line
intersects it at some point $k_{1}$. We can then place another segment which
intersects the _lower_ line at $k_{1}$, and the intersection of this segment
with the upper line gives the value of $k_{2}$. We can repeat until we have
$n-1$ segments. Each clause depending on $x_{0}$ will have a copy of this
setup but with some of the segments removed depending on which terms
$k_{i}\leq x_{0}\leq k_{i+1}$ it contains.

Using a similar expansion for the other terms, we obtain a CNF expression that
cuts out the space we want. Since $p$ and each $q_{\ell}$ are constants, the
total number of clauses does not depend on $n$, and each clause has at most
$O(n)$ terms. Thus, when we add the constraints involving $x_{0}$ to the
constant-sized formula $\phi_{B_{1}}$, the number of vertices increases
linearly in $n$.

We may similarly add $x_{0}$ constraints to the formula for $B_{2}$ with
linear blowup. The result is a gallery with $O(n)$ vertices whose solution
space is homeomorphic to $R\\#R\\#\dots\\#R$. ∎

We have shown that such $P_{n}$, $Q_{n}$ exist having $O(n)$ vertices. In case
it is of interest, we leave it to the reader to verify that the positions of
the vertices can additionally be chosen to be rational numbers which require
only $O(n)$ bits to describe.111In general, if we fix the length of the guard
segments for $x_{0}$ then the wedge parameters that would give $k_{n-1}=1$ are
not rational numbers. Instead, we fix a sufficiently thin wedge and choose the
length of the guard segments for $x_{0}$ appropriately.

##  4 Conclusion

In this work we have settled the open question of Bertschinger et al. [2] by
showing that solution spaces to the art gallery problem can capture the
topology of any semi-algebraic set up to homeomorphism. In doing so, we have
introduced a new form of copying gadget that enables simpler arguments about
the structure of valid solutions to art gallery problem instances.

We are hopeful that this gadget may find other applications as well. For
example, copying gadgets play a central role in the proof that the art gallery
problem is $\exists\mathbb{R}$-hard [1], and before now it was unknown if they
could still be created in the setting where guards need only see the walls of
the art gallery. Our gadgets could be a useful step towards showing that the
wall-only variant is also $\exists\mathbb{R}$-hard.

## Acknowledgments

We are very grateful to Simon Weber for his helpful feedback on an earlier
version of this paper. This material is based upon work supported by the
National Science Foundation Graduate Research Fellowship Program under Grant
No. DGE1745303. Any opinions, findings, and conclusions or recommendations
expressed in this material are those of the authors and do not necessarily
reflect the views of the National Science Foundation.

## References

  * [1] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow.  The art gallery problem is $\exists\mathbb{R}$-complete.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 65–73, 2018.
  * [2] Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, and Simon Weber.  Topological art in simple galleries.  In Symposium on Simplicity in Algorithms (SOSA), pages 87–116. SIAM, 2022.
  * [3] Josef Blass and Wlodzimierz Holsztynski.  Cubical polyhedra and homotopy, iii.  Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, 53(3-4):275–279, 9 1972.
  * [4] Heisuke Hironaka.  Triangulations of algebraic sets.  In Algebraic geometry (Proceedings of Symposia in Pure Mathematics, Volume 29, Humboldt State University, Arcata, California, 1974), volume 29, pages 165–185, 1975.
  * [5] Kyle Roger Hoffman.  Triangulation of locally semi-algebraic spaces.  PhD thesis, University of Michigan, 2009.
  * [6] D. T. Lee and Arthur K. Lin.  Computational complexity of art gallery problems.  IEEE Transactions on Information Theory, 32(2):276–282, 1986\.
  * [7] William S. Massey.  A basic course in algebraic topology, volume 127 of Graduate Texts in Mathematics, chapter 1.  Springer, 1991.
  * [8] Nikolai E Mnëv.  The universality theorems on the classification problem of configuration varieties and convex polytopes varieties.  In Topology and geometry—Rohlin seminar, pages 527–543. Springer, 1988.
  * [9] Peter W. Shor.  Stretchability of pseudolines is NP-hard.  In Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, pages 531–554, 1990.
  * [10] A. Vaezi and M. Ghodsi.  A constant-factor approximation algorithm for point guarding an art gallery.  Manuscript, 2021.


# Explaining Patterns in Data with Language Models via Interpretable
Autoprompting

Chandan Singh,1,∗ John X. Morris,2,∗ Jyoti Aneja,1 Alexander M. Rush,2 &
Jianfeng Gao1

∗ Equal contribution
1 Microsoft Research<EMAIL_ADDRESS>
2 Cornell University<EMAIL_ADDRESS>

###### Abstract

Large language models (LLMs) have displayed an impressive ability to harness
natural language to perform complex tasks. In this work, we explore whether we
can leverage this learned ability to find and explain patterns in data.
Specifically, given a pre-trained LLM and data examples, we introduce
interpretable autoprompting (iPrompt), an algorithm that generates a natural-
language string explaining the data. iPrompt iteratively alternates between
generating explanations with an LLM and reranking them based on their
performance when used as a prompt. Experiments on a wide range of datasets,
from synthetic mathematics to natural-language understanding, show that
iPrompt can yield meaningful insights by accurately finding groundtruth
dataset descriptions. Moreover, the prompts produced by iPrompt are
simultaneously human-interpretable and highly effective for generalization: on
real-world sentiment classification datasets, iPrompt produces prompts that
match or even improve upon human-written prompts for GPT-3. Finally,
experiments with an fMRI dataset show the potential for iPrompt to aid in
scientific discovery.111All code for using the methods and data here is made
available at  github.com/csinva/interpretable-autoprompting.

##  1 Introduction

Large language models (LLMs) have attained an extraordinary ability to harness
natural language for solving diverse natural-language problems [1], often
without the need for finetuning [2, 3]. Moreover, LLMs have demonstrated the
capacity to excel at real-world problems, such as mathematics [4] and
scientific question answering [5].

In this work, we probe whether we can leverage the learned skills of an LLM to
find and explain patterns in a dataset. To do so, we invert the typical
problem of fitting an LLM to data and instead ask whether we can use a fixed
LLM to produce a natural-language string explaining dataset patterns. Our
approach to this problem centers around prompting. Prompting has emerged as an
effective method for adapting LLMs to perform new tasks [6]. A prompt string
is combined with each example in a dataset before querying an LLM for an
answer.

While prompts were initially constructed manually, recent work has shown
success in autoprompting, i.e. automatically finding a prompt via optimization
[7, 8]. However, previous work on learning natural language prompts [7] does
not produce prompts that are meaningful to humans.

Our approach, interpretable autoprompting (iPrompt), extends autoprompting to
generate a semantically meaningful natural-language prompt that explains a key
characteristic of the data (see Fig. 1). For example, given a dataset of
examples of addition, e.g. 2 5 $\Rightarrow$ 7 … 3 1 $\Rightarrow$ 4, we use
an LLM to yield the natural-language description Add the inputs. iPrompt is an
iterative algorithm that alternates between (i) proposing candidate
explanations with an LLM, (ii) reranking the candidates based on their
performance when used as a prompt, and (iii) exploring new candidates.

Figure 1: Interpretable autoprompting (iPrompt) inverts the standard
prediction problem to instead find a natural-language explanation of the data
using a fixed, pre-trained large language model.

To evaluate iPrompt, we curate a diverse collection of datasets written in
natural language (Table 1), where our goal is to accurately infer a ground-
truth pattern. The dataset includes a number of synthetic math datasets, as
well as language tasks from the Natural Instructions V2 dataset [9]. We find
that iPrompt outperforms baseline autoprompting methods in successfully
finding a correct description across these datasets. Moreover, the generated
descriptions are interpretable, allowing human auditing and enabling strong
generalization performance when used as a prompt in a new setting (i.e. when
used for a different LLM). On real-world sentiment classification datasets,
iPrompt even produces prompts that match or improve upon human-written prompts
for GPT-3. Finally, we qualitatively explore iPrompt in a neuroscience task,
in which we seek to understand the mapping of semantic concepts in the brain
from fMRI imaging (data from [10]).

##  2 Dataset Explanation Task

##### Task definition

Given a dataset comprised of input-output string pairs
$\\{(x^{1},y^{1}),\ldots(x^{N},y^{N})\\}$, the goal is to produce a
“semantically meaningful” natural-language string that explains the
relationship between $x$ and $y$. We require that a string consists of human-
understandable text rather than a sequence of incongruous tokens. For example,
in the task shown in Fig. 1, the task is to recover text synonymous to Add the
inputs given samples of data performing addition.

##### Datasets

Table 1 shows the four collections of datasets we study: (1) Inverse Synthetic
Math with datasets that require inferring an underlying mathematical function
of one or two numbers; (2) Inverse Allen NLI (ANLI), a selection of
crowdsourced language tasks [9] with easily verifiable descriptions (e.g. Find
a country’s capital); (3) Sentiment, consisting of four real-world sentiment
classification tasks and (4) fMRI, a dataset involving brain responses to
natural language, motivated by the goal of recovering unknown explanations. In
addition to data examples, the first two collections contain a ground-truth
description and simple rules to test whether an extracted description matches
the ground-truth one. For example, when adding two numbers (Fig. 1), the rule
checks whether a description contains any of the keywords add, sum, or +.

Table 1: Dataset Explanation Task. For full details on each dataset, see Sec.
A.1.

Collection # Description Dataset names Inverse synthetic math 10 Simple
mathematical functions Add two, Subtract two, Multiply two, Divide two, Max
two, First number, Square, Exponentiate, Double, Fibonacci Inverse Allen NLI
[9] 10 Diverse language tasks Country capital, Antonyms, Check edibility,
Rhyme generation, Country currency, Check prime, Check vegetarian, Find typo,
Gender classification, SQL query generation Sentiment 4 Sentiment
classification SST-2, RottenTomatoes, IMDB, Financial Phrasebank Natural-
language fMRI [10] 20 Find an underlying category from a list of words that
excite an fMRI voxel Extracting a pattern from a set of words, each
corresponding to a different voxel

The examples in each task do not directly contain the task description. For
example, when inferring the Add two numbers task, the examples do not contain
a plus sign or any synonyms of the word add such as combine. For
classification tasks such as Check edibility or Check prime, the label
provided in the example text is simply yes/no rather than the given labels,
e.g. edible/non-edible.

##### Evaluation

We evaluate dataset explanation on two criteria: closeness to the ground-truth
prompt and ability to generalize as a prompt for other models. To evaluate
similarity to the ground truth, we score a ranked list of prompts based on
mean reciprocal rank (MRR). Given a set of datasets
$\mathcal{D}=\\{\mathcal{D}_{1},...,\mathcal{D}_{N}\\}$, we compute:
$\text{MRR}=\frac{1}{|\mathcal{D}|}\sum_{i=1}^{|\mathcal{D}|}\frac{1}{\text{rank}_{i}}$,
where $\text{rank}_{i}$ is the one-indexed rank of the first correct
explanation. We evaluate correctness based on whether the generated
explanation contains one of a set of problem-specific keywords. To measure
generalization, we use the top-ranked string as a zero-shot prompt for a
different language model, and evaluate whether that model is able to solve the
task.

##  3 AutoPrompting Methods

In this section, we detail approaches for tackling the general problem of
autoprompting before introducing our method for interpretable autoprompting
(iPrompt) in Sec. 3.2.

We specify autoprompting as a discrete search problem. Given a dataset of $n$
input-output pairs {($x^{1}$, $y^{1}$), …, ($x^{n}$, $y^{n}$)} and a pre-
trained LLM $f$ that returns the log-probability of a given string, the goal
of autoprompting is to find a natural-language explanation $\hat{s}$
maximizing:

$\displaystyle\hat{s}=\underset{s\in\mathcal{S}}{\text{argmax
}}\sum_{i=1}^{n}f\left(\text{render}(s,x^{i},y^{i})\right)$ (1)

The render function is a problem-specific function that renders a natural
language string from the prompt $s$ and each example in the dataset
$(x^{i},y^{i})$. We use $\mathcal{S}$ to indicate the set of fluent strings,
under some notion of syntactic fluency. Solving this search problem exactly is
intractable.

Figure 2: Model accuracy depends on having an accurate prompt for large models
(GPT-J 6B and GPT-3). The model is given the prompt Return the  of the
inputs., where  is filled in with the shown prompt keyword before querying the
output given two inputs numbers in a string. Darker indicates a higher
accuracy, and high accuracy along the diagonal indicates that the correct
prompt induces the highest accuracy.

A core assumption of this objective is that semantically accurate prompts lead
a model to assign higher probability to the data. To check this assumption, we
analyze four datasets from the inverse synthetic math collection that share
common structure for the inputs and prompts: each dataset admits a prompt of
the form Return the  of the inputs., then is given two input numbers and
queried for the output.

Fig. 2 shows the accuracy of different models at performing these tasks when
given different input prompts.222The accuracy is normalized for each task
using softmax in order to visualize the effect of differing prompts. For small
models, the prompts are unsuccessful, but for large models (e.g. GPT-J 6B and
GPT-3), the model is accurate if and only if given the correct prompt.333For
details on each model, see Table A3. This result provides evidence that, at
least for large models, the search for a prompt that maximizes performance
correlates well with the underlying task.

###  3.1 Baseline Methods

##### AutoPrompt

AutoPrompt [7] targets the objective posed in Eq. 1 using a gradient-based
local search. AutoPrompt searches for $\hat{s}$ following the gradients of the
objective Eq. 1 with respect to individual tokens in $\hat{s}$. By iteratively
computing these gradients, it can discretely change individual words in
$\hat{s}$ and then check whether or not the newly updated $\hat{s}$ improves
the objective score. The use of gradients allows AutoPrompt to find an
effective prompt $\hat{s}$, but makes it difficult to find answers that
satisfy the fluency constraint ${\cal S}$.

##### Average-output suffix decoding

LLMs themselves can be directly used to predict prompt strings. We can give
the model a prompt that includes examples such as the following context
string: $\underbrace{\textit{In: 2 5}}_{x^{i}}\underbrace{\textit{Out:
7.}}_{y^{i}}\underbrace{\textit{To compute the output from the input,
}}_{\textit{template}}$ , and sample the output for the blank to recover a
prompt $\hat{s}$. Sampling directly from $f$ helps ensure that the generated
explanation is fluent and semantically meaningful. We decode the output using
beam search to find the highest-probability outputs for multi-token
prompts.444Here we prefer beam search here over alternatives such as nucleus
sampling [11] as we are interested in finding an accurate prompt description
with as few samples as possible. To improve on this approach, we place several
examples into the model’s context, and then average the model’s output logits
across all the examples in the dataset before decoding the output, an approach
we refer to as average-suffix decoding. However, this technique is
insufficient to find high-scoring prompts.

###  3.2 Proposed Method: iPrompt

Figure 3: Overview of iPrompt.

Our method, iPrompt shown in Fig. 3, is an iterative local search algorithm
that alternates between three steps: (i) proposing candidate prompts, (ii)
reranking candidate prompts, (iii) exploration:

(i) Proposal: Candidate prompts are generated by extending the zero-shot LLM
generation. Given a data instance as a prefix, we sample a number of candidate
prompts.555One could use either average suffix decoding or suffix decoding
with a single sample. For computational efficiency, we use suffix decoding
with only a single sample. We also add randomly decode the output rather than
using beam-search, as our iterative procedure can recover from initially
finding inaccurate candidates. The maximum length of each candidate is pre-
specified and fixed. For example, in the add-two-numbers task (Fig. 3), we may
generate four candidates: _{ Combine the numbers, Return the output, Sum in
order, Compute the output}_.

(ii) Reranking: Given candidates, the objective Eq. 1 is evaluated for each
candidate prompt $s$. The top few candidates which maximize the objective are
kept, e.g. narrowing down the candidates to _{ Combine the numbers, Sum in
order}_.

(iii) Exploration: Each of the top candidates from reranking is truncated at a
random position. These truncated candidates are used as a prefix string when
generating new candidate prompts via suffix decoding. For example, we may
randomly select the start of the previous candidates and fill in the endings:
_{ Combine the  , Sum  }_ $\to$ _{ Combine the numbers, Combine both
arguments, Sum the numbers, Sum all inputs}_

The algorithm is repeated until identifying a suitably strong $\hat{s}$, e.g.
selecting _Sum the numbers_. Step (i) and (iii) ensure that prompts remain
fluent, while step (ii) improves the score of the prompts on the objective.
Computationally, iPrompt only requires running inference on the pre-trained
LLM, yielding a significantly lower memory requirement than methods such as
AutoPrompt, which require access to the LLM’s gradients.

##  4 Results

##### Accuracy of prompts

Table 2 compares prompting methods based on the set of candidate descriptions
they generate using GPT-J (a 6-billion parameter model) as the LLM [12]. The
MRR rows show that iPrompt considerably increases the mean reciprocal rank
(MRR) (Sec. 2) over the baselines, implying that iPrompt can more effectively
generate descriptions that accurately reflect the underlying data pattern. The
“top-prompt correctness” rows show the percentage of datasets for which the
top-ranked candidate prompt produced by each method is labeled as accurate by
manual inspection (see all prompts in Table A2). On the ANLI datasets, iPrompt
again outperforms the baselines, although all methods perform poor in an
absolute sense ($\leq 30\%$). The zero-shot results show the accuracy of GPT-J
when using the top prompt found by each model; for the math datasets the
iPrompt prompt elicits an improvement over the baselines, but for the ANLI
datasets all prompts induce poor performance.666Here, we restrict generated
prompts to 6 tokens (see a full discussion of experimental details in Sec.
A.3).

Table 2: Accuracy for dataset explanation measured via (i) MRR, (ii) top-prompt correctness, and (iii) zero-shot accuracy on unseen examples. All experiments are on GPT-J 6B. For all metrics, higher is better.  |  | iPrompt | AutoPrompt | Average suffix
---|---|---|---|---
Math | MRR | 0.71 | 0.30 | 0.07
Top-prompt correctness | 80% | 30% | 20%
Zero-shot acc. | 51.5% | 41.6% | 10.0%
ANLI | MRR | 0.30 | 0.17 | 0.01
Top-prompt correctness | 30% | 0% | 10%
Zero-shot acc. | 4.7% | 1.9% | 5.1%
Table 3: Generalization accuracy (zero-shot) when testing the prompts
generated with GPT-J as the LLM across different models. iPrompt yields strong
performance, usually improving over AutoPrompt despite maintaining
interpretability, and sometimes performing close to the human-written prompt.
Numbers within 2% of the top accuracy (excluding human-written prompts) for
each model are shown in bold.

Human-written iPrompt AutoPrompt Average Suffix No prompt Math OPT 6.7B 12.7
19.3 18.9 4.5 8.4 GPT 20B 76.1 54.4 23.2 21.3 8.5 GPT-3 175B 76.0 62.1 40.8
16.9 28.4 ANLI OPT 6.7B 10.7 6.7 4.7 8.5 7.9 GPT 20B 31.0 14.2 5.6 13.7 4.0
GPT-3 175B 37.6 11.7 2.7 13.4 7.7

##### Qualitative assessment of top prompts

Table 4 shows the top-ranked prompt generated by each method for selected
datasets. iPrompt often finds a prompt that is somewhat indicative of the
underlying relationship, even if the phrasing is not perfect. For example, for
the add two numbers dataset, it finds Write a function int add(. For difficult
datasets, the iPrompt string sometimes simply returns the classes of the
output (e.g. yes or no?) rather than capturing the underlying relationship.
The prompts found by iPrompt also read as coherent strings compared to
AutoPrompt, which returns an incoherent set of tokens. See all found prompts,
including for average-suffix decoding in Table A2.

Table 4: Examples of generated prompts.

$>\ $Human-written prompt iPrompt AutoPrompt ANLI $>\ $Generate an SQL
statement from a question asking for certain data. Write an SQL to produce
output ributed grandfatherExceptionappropri intent Lara $>\ $You are given a
country name and you need to return the currency of the given country. Select
currency code for a new renciesthethe Dmitrythe mortg $>\ $Return whether the
input food dish is vegetarian (yes or no). yes or no? This is
Novthethethethethe $>\ $In this task, you are given an adjective, and your job
is to generate its antonym. An antonym of a word is a word opposite in meaning
to it. What is the opposite of 1 prevailingthethe weakestthe wins Math $>\
$Return the sum of the inputs. Write a function int add( addedthe +the use
worked $>\ $Return the product of the inputs. When you multiply two (
multiplythethe the Multiple $>\ $Return the difference of the inputs. If n $>$
m then subtract opposably exactly subtractFor YEAR $>\ $Return the maximum of
the inputs. Which number has a bigger value NumberthetheJusticeJaDefault $>\
$Return the first of the inputs. The first digit of both values greater name
sorting indiscrim to numbers $>\ $Square the input to get the output. Write a
function that calculates square multiplythe hypot Norttheirl $>\ $Given an
input x, return 2*x. write a function called double that ADDthe
introducedpareat contraceptives Rotten Tomatoes $>\ $Answer Yes if the input
is positive and No if the input is negative. a fast, funny, highly enjoyable
film. Answer: Yes 3.1/ suke Medals; does CFR Sab”]=$>$ NormalConstructed
Umbunit satisfy Good·ram SST-2 $>\ $Answer Yes if the input is positive and No
if the input is negative. life Answer: Yes (because it’s about life) This
RALauntletICEidatedWhetherBF Holy Kubrick incorporatedherent#$ Not=-=- SPECIAL
Pyth

##### Generalization of generated prompts to new models.

Table 3 shows the generalization accuracy when using the prompts generated
using GPT-J (Table 4) and testing them on different LLMs.777Accuracy is
computed following [2, 13]: using exact matching with beam search, a beam
width of 4, and a length penalty of $\alpha=0.6$. The same prompts effectively
improve accuracy across different models compared to having no prompt. The gap
between iPrompt and AutoPrompt is larger for larger models (i.e. GPT 20B and
GPT-3), suggesting that by generating fluent prompts iPrompt better captures a
generalizable description of the task. Human-written prompts still outperform
the autoprompting methods on this task.

##### Investigating iPrompt in sentiment classification

Finally, we study the more difficult task of prompting for sentiment
classification, using four popular datasets [14, 15, 16]. The aim is to find a
dataset-specific prompt that can describe a particular sentiment
classification setting. To accommodate for a complex input-output
relationship, we allow each method to generate up to 16 tokens (our manually-
written sentiment classification prompts range from 13-16 tokens). We use Yes
and No as positive and negative labels, and require the LLM to generate the
proper output, as opposed to simply ranking the two options.

Table 5: Zero-shot accuracy on sentiment classification datasets using prompts
generated with the GPT-J 6B models. Evaluation is performed both on the
original GPT-J 6B parameter model and testing generalization to GPT-3. The
model needs to produce the correct answer (Yes, No, or Maybe) out of the
entire vocabulary (without rank-eval). Values are averaged over three random
seeds for prompt-generation; errors are standard errors of the mean.

Human-written iPrompt AutoPrompt No prompt GPT-J 6.7B Financial phrasebank
24.3 62.4 $\pm$ 0.1 6.8 $\pm$ 2.9 0.0 Rotten Tomatoes 44.4 70.5 $\pm$ 1.4 57.1
$\pm$ 3.4 0.0 SST-2 53.6 82.8 $\pm$ 1.9 40.0 $\pm$ 7.9 0.0 IMDB 32.5 21.3
$\pm$ 9.3 12.1 $\pm$ 0.9 3.5 GPT-3 175B Financial phrasebank 54.1 65.0 2.7 0.4
Rotten tomatoes 58.6 52.5 37.5 0.9 SST-2 60.4 83.6 5.2 0.6 IMDB 79.0 1.3 0.9
1.1

Table 5 shows the zero-shot performance of the prompts elicited by different
methods. Prompts are generated using GPT-J 6B and evaluated using both GPT-J
6B and GPT-3. iPrompt outperforms not only AutoPrompt, but also the manually-
written prompt on three of the four datasets. The exception is the IMDB
dataset, which has extremely long examples and may not be well suited for the
zero shot setting. Accuracy is measured on the test set when available;
otherwise, it is measured on a held-out 25% of the train set.888Different from
the other experiments in this paper, we initialize AutoPrompt with random
tokens instead of all the, as we find AutoPrompt fails to find an effective
solution for longer prefix lengths when all tokens are initialized to the.

Table 4 shows an example of comparing the prompts from the Rotten Tomatoes
dataset, for which iPrompt and AutoPrompt induce similar zero-shot accuracy.
Here and in other cases, iPrompt sometimes discovers a prompt that is a
paraphrase of an example one would find in the training set or a prototypical
example for a class.

##  5 Scientific investigation into fMRI natural-language dataset

We now explore using iPrompt in a (very simplified) neuroscience experimental
setup (Sec. 5). A central challenge in neuroscience is understanding how and
where semantic concepts are represented in the brain. A recent seminal study
[10] explores this question by investigating where different natural-language
categories are represented in the human neocortex. Specifically, the authors
collect functional MRI (fMRI) responses as human subjects listen to hours of
narrative stories. They then build a predictive model of these responses for
each voxel (i.e. a small region in space) in the brain, which takes as input
the words contained in the stories (and other features). To interpret these
individual voxel models, they cluster the words in the narrative stories into
12 groups and manually annotate them, resulting in 12 categories, such as
tactile, visual, and professional. Finally, they view the spatial mapping of
these 12 concepts (projected onto low dimensions) across the brain using their
individual voxel models.

We revisit a small piece of this study’s analysis through the lens of iPrompt.
Specifically, we ask whether iPrompt could generate plausible categories that
are well-represented across the brain but differ from the manually identified
12. We begin by fitting a predictive model for each voxel, following the
pipeline of the original study (details in Sec. A.5). We then use the
resulting models to identify a list of the top-15 words which most excite each
voxel. For example, the top-15 words that excite the best-predicted voxel are:
sheet, edges, diameter, strips, cardboard, copper, steel, colored, coloured,
leaf, wire, cap, paper, shaped, tin. To identify a plausible semantic
category, we construct a template string as follows: The following list of
words all belong to the same semantic category:  \n\n sheet, edges, …, shaped,
tin. We then use iPrompt (again with a GPT-6B parameter model) to generate a
category by filling in the blank (restricted to a single token). To make
iPrompt more effective, for each voxel we use iPrompt on a set of examples
consisting of 15 permutations of the top-15 words, allowing the model to find
patterns that are not overly sensitive to the word-ordering.

Given the top categories for each voxel, we analyze the mapping of recurring
categories across the neocortex. We aggregate the top-15 inferred
categories999We apply stemming and remove stopwords before choosing the best
categories. over the top-15 best-predicted voxels and find that the most
frequently inferred categories are: material, color, surface, text, & fabric.
Interestingly, these are sensible quantities that different voxels could
reasonably be selective for. We spatially map each of these identified
categories (e.g. material) across the 10,000 best-predicted voxels by using
the LLM in a second way. For each voxel, we condition the LLM (again GPT-6B)
on the top-15 words list, and evaluate the predicted probability for each
category, i.e. The following list of words all belong to the same semantic
category: sheet, edges, …, shaped, tin The semantic category they all belong
to, in one word, is  . The higher this predicted probability, the more
selective we infer that a voxel is for the category. Fig. 4 shows these
predicted probabilities for the top-two inferred categories (material and
color) across the cortex of a human subject.

Figure 4: Representations of the iPrompt-elicited concepts material (blue) and
color (red) across the surface of the neocortex are spatially clustered and
smooth. Only the top 10,000 best-predicted voxels are shown, remaining voxels
are shown in black. Plotted with pycortex [17].

While there is no groundtruth for this semantic map, one noteworthy feature of
the resulting map is that it is spatially smooth (quantitatively, Fig. A2
shows that the variance of the map among neighboring pixels is significantly
lower than we would expect by shuffling the map’s values). This is non-
trivial, as nowhere in the modeling process was spatial information
incorporated: each voxel was modeled independently and the displayed
prediction was queried independently. We expect the underlying map to be
smooth, both due to local connectivity in brain regions and also because the
BOLD signal measured by fMRI does not have perfect spatial resolution. Thus,
the fact that our inferred map is smooth suggests that (i) something about
these categories is genuinely captured by the representation in the human
brain, and (ii) that the iPrompt approach was able to reflect at least some of
it. Beyond the two categories shown, the five categories generated by iPrompt
exhibit spatial smoothness across the neocortex (Fig. A2).

##  6 Related work

##### Prompting and autoprompting.

With the advent of large-scale models, prompting (i.e. finding the right
prompt to use to query an LLM for a given task) has exploded as an area of
inquiry, often yielding impressive improvements in performance [2, 18, 6] and
spurring a line of work aiming to make prompting easier [19, 20, 21, 22].
Recently, autoprompting (i.e. automatically searching for a prompt or prompt-
embedding via optimization) has emerged, with methods such as prefix-tuning
[8], P-tuning [23], prompt-tuning with rules [24], knowledgeable prompt tuning
[25] and many more [6]. These strategies use gradient descent to find a set of
“adapter” parameters that maximize model performance, but do not require that
the new parameters map back to tokens in discrete space, rendering them
uninterpretable.

A few methods tackle the more difficult problem of searching for prompts that
can be expressed in natural language tokens. The closest related work is
AutoPrompt [7], which performs autoprompting via input gradients (see Sec. 3).
Similarly, adversarial triggers [26] use autoprompting to identify adversarial
inputs which can be used to change a model’s prediction. These methods
effectively alter a model’s predictions, but do not constrain the discovered
prompts to be semantically meaningful, resulting in prompts that are difficult
to interpret [27]. Another related work directly finetunes an LLM to describe
the difference between two datasets [28].

##### Alternative methods for neural-network interpretation

A popular method for interpreting neural networks is to inspect an LLM’s
individual predictions via feature importances [29, 30], feature-interaction
importances [31, 32], extractive rationales [33, 34], or natural-language
explanations for individual predictions [35, 36]. These works can provide
meaningful insights for individual predictions, but it is difficult to parse
them into an understanding of an entire dataset. Alternatively, one can
investigate whether an LLM’s learned representations via probing [37, 38] or
by directly analyzing a model’s internal weights and activations [39, 40, 41].
However, these approaches are limited in their ability to generate previously
unknown descriptions of data. A different approach involves distilling
information into a transparent model [42, 43, 44] or simply using a
transparent model in the first place [45, 46, 47, 48].

##### Problems related to interpretable autoprompting

The problem statement presented in this work closely resembles the widely
studied problems of symbolic regression [49, 50], program synthesis [51, 52],
text/table summarization [53, 54], and pattern discovery in data-mining [55].
In these cases, data examples are given with the goal of inferring a symbolic
expression, program, or text summary that is consistent with the data. iPrompt
can be viewed as an algorithm for symbolic regression, in which the set of
allowable symbols consists of semantically meaningful natural-language strings
and their optimization is guided by a pre-trained LLM.

##  7 Conclusion and Discussion

iPrompt makes a meaningful step towards finding natural-language prompts that
are both (i) semantically meaningful and (ii) yield strong generalization
performance. Nevertheless, the search algorithms used in this work are
computationally intensive and fail to recover descriptions of complex
datasets. Future work could explore algorithmic variants that make
interpretable autoprompting more efficient and accurate.

Besides algorithmic improvements, future work could explore using iPrompt in
different ways. One such direction could elicit targeted information from data
via the use of a template. For example, one may use iPrompt to extract feature
importance by prepending the learned prompt with the string “To get the answer
from the inputs, the most important inputs are  ”. As another example, in a
scientific study such as the fMRI study in Sec. 5, a scientist interested in a
particular topic (e.g. fear) may investigate that particular topic by making a
more specific template (e.g. How are these words related to the concept of
“fear”?).

While we focus on text, iPrompt could be applied more generally in any setting
where an LLM performs well and takes input in a human-understandable form. For
example, in computer vision, an interpretable autoprompt may look like a mask
of an image, and in vision-language models, an interpretable prompt may be a
description of a vision task, e.g. find the largest shape in this image.

## Acknowledgements

AR is supported by NSF CAREER 2037519, NSF 1704834, and a Sloan Fellowship. JM
is supported by Weill Cornell Medicine. Thanks to Wenting Zhao and Woojeong
Kim for comments on drafts of this paper and to Jeevana Priya Inala, Xin Wang,
Baolin Peng, Michel Galley, and Hao Cheng for interesting discussions related
to the work. We would also like to thank the authors of [10] for making their
data publicly available.

## References

  * [1] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.  (Not cited.)
  * [2] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.  (Not cited.)
  * [3] Victor Sanh, Albert Webson, Colin Raffel, Stephen H Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, et al.  Multitask prompted training enables zero-shot task generalization.  arXiv preprint arXiv:2110.08207, 2021.  (Not cited.)
  * [4] Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, et al.  Solving quantitative reasoning problems with language models.  arXiv preprint arXiv:2206.14858, 2022.  (Not cited.)
  * [5] Mobashir Sadat and Cornelia Caragea.  Scinli: A corpus for natural language inference on scientific text.  arXiv preprint arXiv:2203.06728, 2022.  (Not cited.)
  * [6] Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig.  Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing.  arXiv preprint arXiv:2107.13586, 2021.  (Not cited.)
  * [7] Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh.  Autoprompt: Eliciting knowledge from language models with automatically generated prompts.  arXiv preprint arXiv:2010.15980, 2020.  (Not cited.)
  * [8] Xiang Lisa Li and Percy Liang.  Prefix-tuning: Optimizing continuous prompts for generation.  arXiv preprint arXiv:2101.00190, 2021.  (Not cited.)
  * [9] Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, et al.  Benchmarking generalization via in-context instructions on 1,600+ language tasks.  arXiv, 2022.  (Not cited.)
  * [10] Alexander G Huth, Wendy A De Heer, Thomas L Griffiths, Frédéric E Theunissen, and Jack L Gallant.  Natural speech reveals the semantic maps that tile human cerebral cortex.  Nature, 532(7600):453–458, 2016.  (Not cited.)
  * [11] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  arXiv preprint arXiv:1904.09751, 2019.  (Not cited.)
  * [12] Ben Wang and Aran Komatsuzaki.  GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model.  https://github.com/kingoflolz/mesh-transformer-jax, May 2021.  (Not cited.)
  * [13] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  J. Mach. Learn. Res., 21(140):1–67, 2020.  (Not cited.)
  * [14] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts.  Recursive deep models for semantic compositionality over a sentiment treebank.  In Proceedings of the 2013 conference on empirical methods in natural language processing, pages 1631–1642, 2013.  (Not cited.)
  * [15] P. Malo, A. Sinha, P. Korhonen, J. Wallenius, and P. Takala.  Good debt or bad debt: Detecting semantic orientations in economic texts.  Journal of the Association for Information Science and Technology, 65, 2014.  (Not cited.)
  * [16] Bo Pang and Lillian Lee.  Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales.  In Proceedings of the ACL, 2005.  (Not cited.)
  * [17] James S Gao, Alexander G Huth, Mark D Lescroart, and Jack L Gallant.  Pycortex: an interactive surface visualizer for fmri.  Frontiers in neuroinformatics, page 23, 2015.  (Not cited.)
  * [18] Fabio Petroni, Tim Rocktäschel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, Alexander H Miller, and Sebastian Riedel.  Language models as knowledge bases?  arXiv preprint arXiv:1909.01066, 2019.  (Not cited.)
  * [19] Hendrik Strobelt, Albert Webson, Victor Sanh, Benjamin Hoover, Johanna Beyer, Hanspeter Pfister, and Alexander M Rush.  Interactive and visual prompt engineering for ad-hoc task adaptation with large language models.  arXiv preprint arXiv:2208.07852, 2022.  (Not cited.)
  * [20] Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 8086–8098, Dublin, Ireland, May 2022. Association for Computational Linguistics.  (Not cited.)
  * [21] Stephen H Bach, Victor Sanh, Zheng-Xin Yong, Albert Webson, Colin Raffel, Nihal V Nayak, Abheesht Sharma, Taewoon Kim, M Saiful Bari, Thibault Fevry, et al.  Promptsource: An integrated development environment and repository for natural language prompts.  arXiv preprint arXiv:2202.01279, 2022.  (Not cited.)
  * [22] Robert Logan IV, Ivana Balazevic, Eric Wallace, Fabio Petroni, Sameer Singh, and Sebastian Riedel.  Cutting down on prompts and parameters: Simple few-shot learning with language models.  In Findings of the Association for Computational Linguistics: ACL 2022, pages 2824–2835, Dublin, Ireland, May 2022. Association for Computational Linguistics.  (Not cited.)
  * [23] Xiao Liu, Yanan Zheng, Zhengxiao Du, Ming Ding, Yujie Qian, Zhilin Yang, and Jie Tang.  Gpt understands, too.  arXiv preprint arXiv:2103.10385, 2021.  (Not cited.)
  * [24] Xu Han, Weilin Zhao, Ning Ding, Zhiyuan Liu, and Maosong Sun.  Ptr: Prompt tuning with rules for text classification.  arXiv preprint arXiv:2105.11259, 2021.  (Not cited.)
  * [25] Shengding Hu, Ning Ding, Huadong Wang, Zhiyuan Liu, Juanzi Li, and Maosong Sun.  Knowledgeable prompt-tuning: Incorporating knowledge into prompt verbalizer for text classification.  arXiv preprint arXiv:2108.02035, 2021.  (Not cited.)
  * [26] Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh.  Universal adversarial triggers for attacking and analyzing nlp.  arXiv preprint arXiv:1908.07125, 2019.  (Not cited.)
  * [27] Albert Webson and Ellie Pavlick.  Do prompt-based models really understand the meaning of their prompts?  arXiv preprint arXiv:2109.01247, 2021.  (Not cited.)
  * [28] Ruiqi Zhong, Charlie Snell, Dan Klein, and Jacob Steinhardt.  Describing differences between text distributions with natural language.  In International Conference on Machine Learning, pages 27099–27116. PMLR, 2022.  (Not cited.)
  * [29] Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee.  Explainable ai for trees: From local explanations to global understanding.  arXiv preprint arXiv:1905.04610, 2019.  (Not cited.)
  * [30] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  Why should i trust you?: Explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135–1144. ACM, 2016.  (Not cited.)
  * [31] Chandan Singh, W James Murdoch, and Bin Yu.  Hierarchical interpretations for neural network predictions.  International Conference on Learning Representations, page 26, 2019\.  (Not cited.)
  * [32] Michael Tsang, Dehua Cheng, and Yan Liu.  Detecting statistical interactions from neural network weights.  arXiv preprint arXiv:1705.04977, 2017.  (Not cited.)
  * [33] Omar Zaidan and Jason Eisner.  Modeling annotators: A generative approach to learning from annotator rationales.  In Proceedings of the 2008 conference on Empirical methods in natural language processing, pages 31–40, 2008.  (Not cited.)
  * [34] Lei Sha, Oana-Maria Camburu, and Thomas Lukasiewicz.  Learning from the best: Rationalizing predictions by adversarial information calibration.  In AAAI, pages 13771–13779, 2021.  (Not cited.)
  * [35] Lisa Anne Hendricks, Zeynep Akata, Marcus Rohrbach, Jeff Donahue, Bernt Schiele, and Trevor Darrell.  Generating visual explanations.  In European conference on computer vision, pages 3–19. Springer, 2016.  (Not cited.)
  * [36] Oana-Maria Camburu, Tim Rocktäschel, Thomas Lukasiewicz, and Phil Blunsom.  e-snli: Natural language inference with natural language explanations.  Advances in Neural Information Processing Systems, 31, 2018.  (Not cited.)
  * [37] Alexis Conneau, German Kruszewski, Guillaume Lample, Loïc Barrault, and Marco Baroni.  What you can cram into a single vector: Probing sentence embeddings for linguistic properties.  arXiv preprint arXiv:1805.01070, 2018.  (Not cited.)
  * [38] Frederick Liu and Besim Avci.  Incorporating priors with feature attribution on text classification.  arXiv preprint arXiv:1906.08286, 2019.  (Not cited.)
  * [39] Xingqiao Wang, Xiaowei Xu, Weida Tong, Ruth Roberts, and Zhichao Liu.  Inferbert: a transformer-based causal inference framework for enhancing pharmacovigilance.  Frontiers in Artificial Intelligence, 4:659622, 2021.  (Not cited.)
  * [40] Chris Olah, Arvind Satyanarayan, Ian Johnson, Shan Carter, Ludwig Schubert, Katherine Ye, and Alexander Mordvintsev.  The building blocks of interpretability.  Distill, 3(3):e10, 2018.  (Not cited.)
  * [41] Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov.  Locating and editing factual knowledge in gpt.  arXiv preprint arXiv:2202.05262, 2022.  (Not cited.)
  * [42] Sarah Tan, Rich Caruana, Giles Hooker, and Yin Lou.  Distill-and-compare: Auditing black-box models using transparent model distillation.  In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 303–310, 2018.  (Not cited.)
  * [43] Wooseok Ha, Chandan Singh, Francois Lanusse, Srigokul Upadhyayula, and Bin Yu.  Adaptive wavelet distillation from neural networks through interpretations.  Advances in Neural Information Processing Systems, 34, 2021.  (Not cited.)
  * [44] Chandan Singh and Jianfeng Gao.  Emb-gam: an interpretable and efficient predictor using pre-trained language models.  arXiv preprint arXiv:2209.11799, 2022.  (Not cited.)
  * [45] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone.  Classification and Regression Trees.  Wadsworth and Brooks, Monterey, CA, 1984.  (Not cited.)
  * [46] Yan Shuo Tan, Chandan Singh, Keyan Nasseri, Abhineet Agarwal, and Bin Yu.  Fast interpretable greedy-tree sums (figs).  arXiv:2201.11931 [cs, stat], 1 2022.  arXiv: 2201.11931.  (Not cited.)
  * [47] Chandan Singh, Keyan Nasseri, Yan Shuo Tan, Tiffany Tang, and Bin Yu.  imodels: a python package for fitting interpretable models.  Journal of Open Source Software, 6(61):3192, 2021.  (Not cited.)
  * [48] Abhineet Agarwal, Yan Shuo Tan, Omer Ronen, Chandan Singh, and Bin Yu.  Hierarchical shrinkage: improving the accuracy and interpretability of tree-based methods.  arXiv:2202.00858 [cs, stat], 2 2022.  arXiv: 2202.00858.  (Not cited.)
  * [49] Douglas Adriano Augusto and Helio JC Barbosa.  Symbolic regression via genetic programming.  In Proceedings. Vol. 1. Sixth Brazilian Symposium on Neural Networks, pages 173–178. IEEE, 2000.  (Not cited.)
  * [50] Michael Schmidt and Hod Lipson.  Distilling free-form natural laws from experimental data.  science, 324(5923):81–85, 2009.  (Not cited.)
  * [51] Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al.  Program synthesis.  Foundations and Trends® in Programming Languages, 4(1-2):1–119, 2017.  (Not cited.)
  * [52] Zohar Manna and Richard Waldinger.  A deductive approach to program synthesis.  ACM Transactions on Programming Languages and Systems (TOPLAS), 2(1):90–121, 1980.  (Not cited.)
  * [53] Wojciech Kryściński, Nitish Shirish Keskar, Bryan McCann, Caiming Xiong, and Richard Socher.  Neural text summarization: A critical evaluation.  arXiv preprint arXiv:1908.08960, 2019.  (Not cited.)
  * [54] Tianyu Liu, Kexiang Wang, Lei Sha, Baobao Chang, and Zhifang Sui.  Table-to-text generation by structure-aware seq2seq learning.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.  (Not cited.)
  * [55] David J Hand.  Principles of data mining.  Drug safety, 30(7):621–622, 2007.  (Not cited.)
  * [56] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  OpenAI blog, 1(8):9, 2019.  (Not cited.)
  * [57] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al.  Opt: Open pre-trained transformer language models.  arXiv preprint arXiv:2205.01068, 2022.  (Not cited.)
  * [58] Sid Black, Gao Leo, Phil Wang, Connor Leahy, and Stella Biderman.  GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tensorflow.  March 2021.  If you use this software, please cite it using these metadata.  (Not cited.)
  * [59] Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, et al.  Gpt-neox-20b: An open-source autoregressive language model.  arXiv preprint arXiv:2204.06745, 2022.  (Not cited.)
  * [60] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In International Conference on Machine Learning, pages 8748–8763. PMLR, 2021.  (Not cited.)

##  Appendix A Appendix

###  A.1 Data details

Table A1: Details for each dataset.

Task name Samples Description Example fibonacci_one 10 Given an input x,
return the xth fibonacci number. Given the input x is 8, the output f(x) is
21.\n\n double_one 10 Given an input x, return 2*x. Given the input x is 6,
the output f(x) is 12.\n\n exp_one 10 Exponentiate the input to get the
output. Given the input x is 8, the output f(x) is 2980.96.\n\n square_one 10
Square the input to get the output. Given the input x is 2, the output f(x) is
4.\n\n first_two 100 Return the first of the inputs. Given the input numbers 7
and 8, the answer is 7.\n\n add_two 100 Return the sum of the inputs. Given
the input numbers 9 and 7, the answer is 16.\n\n subtract_two 100 Return the
difference of the inputs. Given the input numbers 5 and 4, the answer is
1.\n\n divide_two 100 Return the quotient of the inputs. Given the input
numbers 2 and 7, the answer is 2/7.\n\n multiply_two 100 Return the product of
the inputs. Given the input numbers 3 and 3, the answer is 9.\n\n max_two 100
Return the maximum of the inputs. Given the input numbers 1 and 1, the answer
is 1.\n\n task1191_food_veg_nonveg 101 Return whether the input food dish is
vegetarian (yes or no). Input: Haq Maas Answer: no\n
task1149_item_check_edible 119 Return whether the input item is edible (yes or
no). Input: vase Answer: no\n task1146_country_capital 231 In this task, you
are given a country name and you need to return the capital city of the given
country Input: Saint Pierre and Miquelon Answer: Saint-Pierre\n
task1147_country_currency 232 You are given a country name and you need to
return the currency of the given country. Input: Senegal Answer: CFA Franc
BCEAO\n task1509_evalution_antonyms 551 In this task, you are given an
adjective, and your job is to generate its antonym. An antonym of a word is a
word opposite in meaning to it. Input: paper Answer: scissor\n
task183_rhyme_generation 999 Given an input word generate a word that rhymes
exactly with the input word. If not rhyme is found return ”No” Input: think
Answer: sync\n task107_splash_question_to_sql 2031 In this task you are
expected to write an SQL query that will return the data asked for in the
question. An SQL query works by selecting data from a table where certain
conditions apply. A table contains columns where every row in that table must
have a value for each column. Every table has a primary key that uniquely
identifies each row, usually an id. To choose which columns are returned you
specify that after the ”SELECT” statement. Next, you use a ”FROM” statement to
specify what tables you want to select the data from. When you specify a table
you can rename it with the ”AS” statement. You can reference that table by
whatever name follows the ”AS” statement. If you want to select data from
multiple tables you need to use the ”JOIN” statement. This will join the
tables together by pairing a row in one table with every row in the other
table (Cartesian Product). To limit the number of rows returned you should use
the ”ON” statement. This will only return rows where the condition… Input:
What are the order ids and customer ids for orders that have been Cancelled,
sorted by their order dates? Answer: SELECT order_id , customer_id FROM
customer_orders WHERE order_status_code = ”Cancelled” ORDER BY order_date\n
task088_identify_typo_verification 6499 The given sentence contains a typo
which could be one of the following four types: (1) swapped letters of a word
e.g. ’niec’ is a typo of the word ’nice’. (2) missing letter in a word e.g.
’nic’ is a typo of the word ’nice’. (3) extra letter in a word e.g. ’nicce’ is
a typo of the word ’nice’. (4) replaced letter in a word e.g ’nicr’ is a typo
of the word ’nice’. You need to identify the typo in the given sentence. To do
this, answer with the word containing the typo. Input: A laege display of
apples, pears, and oranges Answer: laege\n task1336_gender_classifier 6500
Return the gender of the person in the input sentence. Input: Justin made me
feel discouraged. Answer: M\n task092_check_prime_classification 6500 In this
task, you need to output ’Yes’ if the given number is a prime number otherwise
output ’No’. A ’prime number’ is a a whole number above 1 that can not be made
by multiplying other whole numbers. Input: 9319 Answer: Yes\n

###  A.2 iPrompt experiments extended

Table A2: Examples of top-generated prompts for each method.

Human-written prompt AutoPrompt iPrompt Average suffix identify typo
verification The given sentence contains a typo which could be one of the
following four types: (1) swapped letters of a word e.g. ’niec’ is a typo of
the word ’nice’. (2) missing letter in a word e.g. ’nic’ is a typo of the word
’nice’. (3) extra letter in a word e.g. ’nicce’ is a typo of the word ’nice’.
(4) replaced letter in a word e.g ’nicr’ is a typo of the word ’nice’. You
need to identify the typo in the given sentence. To do this, answer with the
word containing the typo. Sytheanathethethe Given a string containing the
alphabet the first word of the input check prime classification In this task,
you need to output ’Yes’ if the given number is a prime number otherwise
output ’No’. A ’prime number’ is a a whole number above 1 that can not be made
by multiplying other whole numbers. Abedin AnywaytheONSORED Roses 2050 Yes or
no? Is that the input.\n\n¡—endoftext—¿ splash question to sql Generate an SQL
statement from a question asking for certain data. ributed
grandfatherExceptionappropri intent Lara Write an SQL to produce output a
string that records all country capital In this task, you are given a country
name and you need to return the capital city of the given country
Bringingthethe Stargthethe How did the economy perform in the name of the
capital of country currency You are given a country name and you need to
return the currency of the given country. renciesthethe Dmitrythe mortg Select
currency code for a new the string representation of the input item check
edible Return whether the input item is edible (yes or no). joiningthe Brazil
fuckingthethe Would you like to buy a ”yes” or ”no food veg nonveg Return
whether the input food dish is vegetarian (yes or no). Novthethethethethe yes
or no? This is the input.\n\n¡—endoftext—¿ peixian equity evaluation corpus
gender classifier Return the gender of the person in the input sentence.
TurtheFortthetheReviewer A B C D F# a function that represents one evalution
antonyms In this task, you are given an adjective, and your job is to generate
its antonym. An antonym of a word is a word opposite in meaning to it.
prevailingthethe weakestthe wins What is the opposite of 1 the first word of
the input rhyme generation Given an input word generate a word that rhymes
exactly with the input word. If not rhyme is found return ”No” matesthe dex
championshipthethe bale balbalbab the first word of the input add two Return
the sum of the inputs. addedthe +the use worked Write a function int add( the
sum of the input numbers multiply two Return the product of the inputs.
multiplythethe the Multiple When you multiply two ( the sum of the input
numbers divide two Return the quotient of the inputs. Kaplan MAG comprisingthe
quarterly disproportion n / N,where we the result of the division. subtract
two Return the difference of the inputs. opposably exactly subtractFor YEAR If
n ¿ m then subtract -1.\n\n¡—endoftext—¿ max two Return the maximum of the
inputs. NumberthetheJusticeJaDefault Which number has a bigger value the sum
of the input numbers first two Return the first of the inputs. greater name
sorting indiscrim to numbers The first digit of both values the sum of the
input numbers square one Square the input to get the output. multiplythe hypot
Norttheirl Write a function that calculates square f(x).\n\n exp one
Exponentiate the input to get the output. Smythe webpage fle clin McA Use
BigInteger and double ( f(x).\n\n double one Given an input x, return 2*x.
ADDthe introducedpareat contraceptives write a function called double that
f(x).\n\n fibonacci one Given an input x, return the xth fibonacci number.
betweenthe made one uped how to prove an algorithm correctness f(x).\n\n

Table A3: Models analyzed here.

Model name Huggingface identifier Citation GPT-2 (1.5B) gpt2-xl [56] OPT
(2.7B) facebook/opt-2.7b [57] GPT-Neo (2.7B) EleutherAI/gpt-neo-2.7B [58]
GPT-J (6B) EleutherAI/gpt-j-6B [12] OPT (6.7B) facebook/opt-6.7b [57] GPT-Neo
(20B) EleutherAI/gpt-neox-20b [59] GPT-3 (175B) OpenAI API (text-davinci-002)
[60]

###  A.3 Experimental details extended

####  A.3.1 Hyperparameters for autoprompting

This subsection discusses the hyperparameters set for prompts generated on
Math, NLI, and sentiment tasks. For Math and NLI tasks we considered prompts
of length $6$ tokens; for sentiment we considered prompts of length $16$. For
all experiments with iPrompt we consider $8$ candidate explanations for each
step and generate $4$ new generations per candidate, for a total of $32$
candidates. For fair comparison, we consider $32$ candidates per step for
AutoPrompt. We generate Math and NLI from $5,000$ training steps and Sentiment
candidates from $10,000$ steps. We truncate examples to a maximum of $128$
tokens. We measure loss for re-ranking (used by both AutoPrompt and iPrompt)
using the LLM’s loss over the full space of output tokens, i.e. we do not
restrict the vocabulary to the space of label tokens for classification
problems.

###  A.4 Details of iPrompt

Here we explicate the details of iPrompt. At each step, we consider a fixed
number of mutations for each example in the population, as well as an
additional number of random generations to prevent the population from getting
stuck in a local minimum. When we sample a new population, we sample the best-
performing prompts seen so far, as measured by a running average zero-shot
loss. In order to encourage diverse candidate prompts, sample a population
such that each sample starts with a different token. During preliminary
experiments, we found that enforcing different starting tokens for each
candidate prompt helped promote more diverse and interpretable prefixes.

For generation, we sample directly from the LLM given the data concatenated
with the string
nPrompt:. We sample with a temperature of $1$ and do not use a sampling
strategy like nucleus sampling. For Math and NLI, we set the “repetition
penalty” for generations to $2.0$ to discourage copying from the training set.
For the sentiment experiment, we reduce the repetition penalty to $1.0$.

####  A.4.1 Details of AutoPrompt

We note several changes to AutoPrompt that were not mentioned in the original
paper but present in the original codebase, and proved crucial in our
implementation.

First, if we compute the top-candidates over every position, the magnitude of
the gradient will always be highest at position 0, and thus AutoPrompt will
prefer to make a swap at that position every time. To fix this issue, at each
training step, we randomly select a position of the token to edit and consider
word swaps only at that position.

Second, as described, AutoPrompt will always take one of the candidate
substitutions, even when said candidate does not improve the loss compared to
the current prefix. Instead, we only make a substitution if the candidate
prefix loss is lower than the loss on the same batch computed with the current
prefix.

Finally, unlike the AutoPrompt implementation found online, we allow
AutoPrompt to select from any token to substitute, including special tokens
and non-English characters.

To make AutoPrompt compatible with ranking-based metrics, we store the losses
for each candidate ranked during training. At the end, we consider the “top
prefix” to be the prefix with the lowest average loss during training, that
has been considered at least three times. This final consideration criteria
prevents candidates from the very end of training that only have a few loss
estimates from being counted as the top prefix.

###  A.5 fMRI experiment details

This section gives more details on the fMRI experiment analyzed in Sec. 5; for
more scientific details see the original study [10] and code
(github.com/HuthLab/speechmodeltutorial). Sec. 5 analyzes data from one human
subject in the original study, as the subject listened to approximately two
hours of narrative speech from the Moth Radio Hour, which consists of short
autobiographical stories. The subject underwent fMRI scanning as they
listened, yielding an fMRI volume brain scan consisting of tens of thousands
of voxels roughly every two seconds.

The individual voxel models described in Sec. 5 are each fit to 3,737 training
points, each corresponding to a different time point (after accounting for
various preprocessing steps, such as trimming the beginning and end of the
sequence). They are evaluated on 291 training volumes which come from a
10-minute story that was not seen during draining.

Fig. A1 shows the generalization performance of the model for each voxel,
measured by the correlation between the predicted response and the measured
response. Some regions are very poorly predicted (black), but many voxels can
be predicted quite well (bright).

Figure A1: Generalization performance for individual-voxel models, measured by
correlation between the prediction and the measured response. Figure A2:
Concepts are spatially localized in the brain maps: the variance between
neighboring voxels is considerably lower than would be expected from shuffling
the voxel values. Note that we take care ot shuffle the map values only within
the 10,000 top-predicted voxels, ignoring the poorly predicted voxels. Error
bars (within the points) are standard errors of the mean.

###  A.6 Sentiment results extended

Table A4 shows the best prompt produced by each method for each sentiment
dataset. iPrompt often learns to recreate significant examples from the
dataset, as a prompt. Figure A3 shows loss across training step for each
method and dataset, across three random seeds. We see that iPrompt manages to
find a better prompt for all datasets except IMDB, and often stops well short
of the $10,000$ maximum training steps (if it does not find a better prompt
for 100 steps). Each training step represents a single word swap (in the case
of AutoPrompt) or the truncation and generation of a new prefix (in the case
of iPrompt).

Table A4: Best-of-three prompts generated by each method on sentiment
classification datasets.

Task Method Prompt Financial phrasebank AutoPrompt Maybeiago EUR Vimaterasu
estab dimeye dignaterasu? Lair EURaterasu Tol calc Human-written prompt Answer
Yes for positive, No for negative, and Maybe for neutral. No prompt iPrompt
Budapest. Answer: Maybe (1) - The parent company is a big German IMDB
AutoPrompt Noamphetamine revealed oxidative Yesmone poker NoTrivia bands
morphology [ despite No ex No Human-written prompt Answer Yes if the input is
positive and No if the input is negative. No prompt iPrompt This was filmed
back-to-back with the 1992 re-make of Conan Rotten Tomatoes AutoPrompt osuke
Medals; does CFR Sab”]=¿ NormalConstructed Umbunit satisfy Good· ram Human-
written prompt Answer Yes if the input is positive and No if the input is
negative. No prompt iPrompt a fast, funny, highly enjoyable film. Answer: Yes
3.1/ SST-2 AutoPrompt RALauntletICEidatedWhetherBF Holy Kubrick
incorporatedherent#$ Not=-=- SPECIAL Pyth Human-written prompt Answer Yes if
the input is positive and No if the input is negative. No prompt iPrompt life
Answer: Yes (because it’s about life) This

Figure A3: Loss plots for methods across sentiment analysis datasets, showing
AutoPrompt (green) and iPrompt (red) across three random seeds. Figure A4:
Accuracy when testing prompts on different test sets. Testing on financial
phrasebank (FFB) yields much lower performance, but testing on the other tree
datasets, which are all movie reviews, yields reasonable performance. iPrompt
tends to find prompts that generalize better to new datasets. All experients
using GPT-J-6B.