# Circuit complexity and functionality: a thermodynamic perspective

Claudio Chamon Boston University Andrei E. Ruckenstein∗ Eduardo R. Mucciolo
University of Central Florida Ran Canetti∗

Circuit complexity, defined as the minimum circuit size required for
implementing a particular Boolean computation, is a foundational concept in
computer science. Determining circuit complexity is believed to be itself a
hard problem [1]. Furthermore, placing general lower bounds on circuit
complexity would allow distinguishing computational classes, such as P and NP,
an unsolved problem [2]. Recently, in the context of black holes, circuit
complexity has been promoted to a physical property, wherein the growth of
complexity is reflected in the time evolution of the Einstein-Rosen bridge
(“wormhole”) connecting the two sides of an AdS “eternal” black hole [3]. Here
we explore another link between complexity and physics for circuits of given
functionality. Taking advantage of the connection between circuit counting
problems and the derivation of ensembles in statistical mechanics, we tie the
entropy of circuits of a given functionality and fixed number of gates to
circuit complexity. We use thermodynamic relations to connect the quantity
analogous to the equilibrium temperature to the exponent describing the
exponential growth of the number of distinct functionalities as a function of
complexity. This connection is intimately related to the finite
compressibility of typical circuits. Finally, we use the thermodynamic
approach to formulate a framework for the obfuscation of programs of arbitrary
length – an important problem in cryptography – as thermalization through
recursive mixing of neighboring sections of a circuit, which can viewed as the
mixing of two containers with “gases of gates”. This recursive process
equilibrates the average complexity and leads to the saturation of the circuit
entropy, while preserving functionality of the overall circuit. The
thermodynamic arguments hinge on ergodicity in the space of circuits which we
conjecture is limited to disconnected ergodic sectors due to fragmentation.
The notion of fragmentation has important implications for the problem of
circuit obfuscation as it implies that there are circuits with same size and
functionality that cannot be connected via local moves. Furthermore, we argue
that fragmentation is unavoidable unless the complexity classes NP and coNP
coincide, a statement that implies the collapse of the polynomial hierarchy of
complexity theory to its first level.

## Introduction

During the past decade a novel connection between physics and computer science
has emerged in the course of explorations of one of the most fundamental open
problems in physics, namely, the development of a theory of quantum gravity
that reconciles and unifies general relativity with quantum mechanics. In this
context, a bold proposal was made and developed by Susskind and collaborators
[3, 4, 5] whereby the formal computer science notion of complexity has
acquired specific physical reality, as it is conjectured that the growth of
computational complexity represents the growth of the Einstein-Rosen bridge
(the “wormhole”) of an AdS “eternal” black hole. It is argued that this growth
is linear in time and persists for a time scale that is exponential in the
physical black hole entropy. One way to formalize this connection is to use
heuristic models of black hole dynamics based on quantum circuits of $2$-qubit
gates [6], in which case one (i) defines “computational complexity” as the
minimum number of elementary gates needed to implement a particular unitary
operator; and (ii) introduces an intuitive notion of “circuit entropy”,
determined from the logarithm of the number of possible circuits of a given
complexity. Unlike the physical entropy, which saturates to a value linear in
the number of qubits, $n$, the circuit entropy, just as the circuit
complexity, grows to its saturation value of $O(4^{n})$. More precisely, Refs.
[3, 4, 5] argue that computational complexity is connected with the entropy of
an auxiliary ensemble of $2^{n}$ classical particles moving on a negatively
curved two-dimensional surface of large genus. In analogy with the second law
of thermodynamics in physical systems, this connection leads to the natural
description of the growth tendency of computational complexity as “the second
law of complexity” [5]. It is important to note that in deriving the linear
growth of complexity with number of gates, Refs. [4, 5] ignore the role of
“circuit collisions”, defined as different sequences of gates that lead to the
same unitary, i.e., circuits of the same “functionality.”

By contrast, here we focus on the development of a thermodynamic approach that
takes into account both complexity and functionality. Ultimately it is the
specific computation implemented by a given circuit that is the central object
of interested in most computational problems. Our framework is based on
reversible computing, which can be implemented either as permutations $P$
acting on the space of $2^{n}$ strings of $n$ bits, or as unitary
transformations $U$ acting on the $d^{n}$ dimensional Hilbert space of $n$
qudits with local Hilbert space dimension $d$. Below, we focus on the
permutations because the counting is discrete (and thus simpler), but the
results carry over to unitaries with minor modifications. We will establish
that there are exponentially many ways to express a given functionality – a
permutation $P$ – in terms of reversible gates. Our framework of circuit
thermodynamics allows us to connect the scaling of two seemingly unrelated
counting problems: (a) how many ${\cal N}$-gate circuits can one write for a
given functionality, and (b) how many distinct functionalities are there for
circuits with given complexity ${\cal K}$. The connection between these
quantities is tied to finite compressibility of typical circuits, e.g., those
with gates drawn randomly from a given gate set. This finite compressibility
highlights the importance of circuit collisions and also implies a linear
growth of complexity with number of gates (up to its maximum value exponential
in $n$) with a slope that is less than unity. As an application of the
framework, keeping track of functionality allows us to formulate a
thermodynamic approach to the problem of circuit obfuscation, i.e., a form of
program encryption that hides one among many circuit implementations of a
given functionality.

Below we also introduce the notion of ergodicity in the space of circuits of
equal size and functionality, which is implied by the assumption of the
uniform covering of the space of circuits assumed in formulating our
thermodynamic approach. The discussion of ergodicity requires defining a
dynamics in the space of circuits which enables transforming two circuits into
one another while preserving size and functionality. We define a set of
dynamical rules that we refer to as “$k$-local” dynamics according to which
one replaces $k$-gate subcircuits by equivalent subcircuits of equal size.
This dynamical rule conserves both the functionality and size of the original
circuit. We argue that, generically, such models lead to fragmentation of the
space of circuits into disconnected sectors. Thus, ergodicity holds and the
thermodynamic framework only applies within each sector. This conclusion
raises interesting questions about circuit obfuscation that are connected with
fundamental assumptions of complexity theory in computer science.

## Results

Counting circuits, entropy inequalities, and the thermodynamics of circuit
complexity: As noted above, there are multiple ways of writing the same
permutation $P$ using reversible gates; the number of ways depends on the gate
set $G$ used. We define the circuit entropy

$\displaystyle{\cal S}(P,{\cal N})=\log_{2}\Omega(P,{\cal N})\;,$ (1)

where $\Omega(P,{\cal N})$ is the number of circuits realizing permutation $P$
with exactly ${\cal N}$ gates. This definition immediately implies the sum-
rule $\sum_{P}\;\Omega(P,{\cal N})=|G|^{\cal N}$, where $|G|$ denotes the
cardinality of the gate set used in the implementation of $P$.

The above counting parallels that used in the formulation of the
microcanonical ensemble in statistical mechanics. In this setting, both ${\cal
N}$ and the circuit functionality, i.e., the permutation $P$ implemented by
the circuit, are “conserved quantities”. Furthermore, we assume that all
circuits implementing $P$ with ${\cal N}$ gates appear with equal weight in
the counting, a condition equivalent to the equal probability of microstates
in the microcanonical ensemble.

A number of inequalities follow from the definition of the circuit entropy in
Eq. (1). The simplest one,

$\displaystyle{\cal S}(P_{1},{\cal N}_{1})+{\cal S}(P_{2},{\cal
N}_{2})\leq{\cal S}(P_{1}P_{2},{\cal N}_{1}+{\cal N}_{2})\;,$ (2)

expresses the fact that there may be more ways of implementing the product
$P_{1}P_{2}$ than simply sequentially implementing $P_{1}$ and then $P_{2}$.
Using this inequality, we can immediately derive a lower bound on the entropy
${\cal S}(P,{\cal N})$ in terms of the circuit complexity ${\cal K}(P)$ of the
permutation $P$:

$\displaystyle{\cal S}(P,{\cal K}(P))+{\cal S}({1\\!\\!1},{\cal N}-{\cal
K}(P))\leq{\cal S}(P,{\cal N})\;,$ (3)

where ${1\\!\\!1}$ denotes the identity permutation, which has zero
complexity, i.e., it can be expressed without using any gate. The bound Eq.
(3) connects the microcanonical ensemble entropy to the circuit complexity,
and provide the foundation to what we refer to as the thermodynamics of
circuit complexity. (In analogy to statistical physics, by introducing weights
for different gates one could have also constructed a canonical ensemble for
circuits.) The two terms on the left hand side represent two types of
contributions to the circuit entropy: the first accounts for the number of
different ways of writing $P$ within the minimum possible size ${\cal K}(P)$,
and is independent of ${\cal N}$; the second term depends on the “free volume”
${\cal N}-{\cal K}(P)$, with the complexity ${\cal K}(P)$ acting as an
“excluded volume”. The ${\cal S}({1\\!\\!1},{\cal N}-{\cal K}(P))$
contribution depends on $P$ only through its complexity. We posit that (i) up
to subextensive corrections, ${\cal S}(P,{\cal K}(P))$ depends on $P$ only
through its complexity ${\cal K}(P)$; and that (ii) the entropy ${\cal
S}(P,{\cal N})$ also only depends on ${\cal N}$ and the complexity ${\cal
K}(P)$, namely,

$\displaystyle{\cal S}(P,{\cal N})\approx\bar{\cal S}({\cal K}(P),{\cal
N})\;.$ (4)

Note that, in parallel with the entropy inequality in Eq. (2), the circuit
complexity satisfies the opposite inequality,

$\displaystyle{\cal K}(P_{1})+{\cal K}(P_{2})\geq{\cal K}(P_{1}P_{2})\;,$ (5)

which reflects the obvious fact that there may be shorter circuits
implementing $P_{1}P_{2}$ than the concatenation of $P_{1}$ and $P_{2}$.

To exploit the implications of the above counting argument we introduce
another entropy function $\sigma({\cal K},{\cal N})=\log_{2}\omega({\cal
K},{\cal N})$. By contrast to $\Omega({\cal K}(P),{\cal N})$, which counts the
number of ${\cal N}$-gate circuits of fixed functionality with complexity
${\cal K}$, $\omega({\cal K},{\cal N})$ counts all ${\cal N}$-gate circuits of
fixed complexity, ${\cal K}$:

$\displaystyle\omega({\cal K},{\cal N})=\sum_{P}\delta_{{\cal K},{\cal
K}(P)}\;2^{{\cal S}(P,{\cal N})}\approx\sum_{P}\delta_{{\cal K},{\cal
K}(P)}\;2^{\bar{\cal S}({\cal K}(P),{\cal N})}=\nu({\cal K})\;2^{\bar{\cal
S}({\cal K},{\cal N})}\;,$ (6)

leading to

$\displaystyle\sigma({\cal K},{\cal N})$
$\displaystyle\approx\log_{2}\nu({\cal K})+\bar{\cal S}({\cal K},{\cal N})\ $
(7a) $\displaystyle\approx\alpha{\cal K}+\bar{\cal S}({\cal K},{\cal N})\ \;,$
(7b)

where $\nu({\cal K})=\sum_{P}\delta_{{\cal K},{\cal K}(P)}$ is a “density of
states” that counts the number of possible functionalities (i.e.,
permutations) implemented by circuits of a fixed complexity, ${\cal K}$. In
writing Eq. (7b) we assumed the extensitivity of both sides of Eq. (7a) which
implies that $\log_{2}\nu({\cal K})=\alpha{\cal K}$. The function
$\omega({\cal K},{\cal N})=2^{\sigma({\cal K},{\cal N})}$ defines, for
circuits of ${\cal N}$ gates, the circuit complexity weight distribution,
which peaks at the extremum of the function $\sigma({\cal K},{\cal N})$:

$\displaystyle\frac{\partial{\sigma({\cal K},{\cal N})}}{\partial{\cal
K}}{\biggr{\rvert}}_{{\cal N}}=0=\alpha+\frac{\partial\bar{\cal S}({\cal
K},{\cal N})}{\partial{\cal K}}{\biggr{\rvert}}_{{\cal N}}\;.$ (8)

Since the entropy decreases with complexity, we write ${\partial\bar{\cal
S}({\cal K},{\cal N})}/{\partial{\cal K}}|_{{\cal N}}=-\beta(\kappa)$ where
$\beta(\kappa)$ is a positive function of $\kappa={\cal K}/{\cal N}$. At the
extremum $\kappa=\kappa^{*}$, $\alpha=\beta(\kappa^{*})=\beta$, and Eq. (7b)
assumes the form,

$\displaystyle\sigma({\cal K}^{*},{\cal N})=\beta\;{\cal K}^{*}+\bar{\cal
S}({\cal K}^{*},{\cal N})\ \;.$ (9)

It is gratifying that Eq. (9) can be recast in a form familiar from the
thermodynamics of physical systems: if we interpret ${\cal K}$ as the negative
of the energy, $\mathcal{E}=-{\cal K}$ (or equivalently,
$\epsilon=\mathcal{E}/{\cal N}=-\kappa$) and $\beta=1/{T}$ as the inverse of
the temperature $T$, Eq. (9) can be rewritten in terms of the equilibrium free
energy $F(T,{\cal N})$,

$\displaystyle-{T}\;{\sigma_{e}}(\mathcal{E},{\cal N})\equiv F({T},{\cal
N})=\mathcal{E}-{T}\;{{\bar{\cal S}}_{e}}(\mathcal{E},{\cal N})\;,\;,$ (10)

where subscripts $e$ represent the respective $\sigma$ and $\bar{\cal S}$
functions evaluated at the corresponding negative energies. Within this
correspondence, the smallest (large negative) energy state - corresponding to
high complexity - would represent a low entropy crystal while the largest
(zero) energy state - corresponding to low complexity - would represent a high
entropy gas.

The direct analogy with statistical mechanics can be exploited further in the
calculation of the probability distribution of complexities for ${\cal
N}$-gate circuits:

$\displaystyle P_{{\cal N}}({\cal K})=\frac{\omega({\cal K},{\cal
N})}{\sum_{{\cal K}=0}^{{\cal N}}\omega({\cal K},{\cal N})}\;,$ (11)

where the form of $\omega({\cal K},{\cal N})$ can be obtained by expanding
$\sigma({\cal K},{\cal N})=\log_{2}\omega({\cal K},{\cal N})=\alpha{\cal
K}+\bar{\cal S}({\cal K},{\cal N})$ in Eq. (7b) to second order in
$\Delta{\cal K}=({\cal K}-{\cal K}^{*})$, the departure from the solution of
the extremum condition, $\beta(\kappa^{*})=\alpha$:

$\displaystyle\log_{2}\omega({\cal K},{\cal N})=\bar{\cal S}({\cal
K}^{*},{\cal N})+\alpha{\cal K}^{*}+\frac{1}{2}\;{\Delta{\cal
K}}^{2}\;\frac{\partial^{2}\bar{\cal S}({\cal K},{\cal N})}{\partial{\cal
K}^{2}}{\biggr{\rvert}}_{{\cal N},{\cal K}={\cal K}^{*}}+\cdots\ \;.$ (12)

Using the extensivity of the entropy in ${\cal K}$ and ${\cal N}$ we can write
$\bar{\cal S}({\cal K}^{*},{\cal N})=-\beta{\cal K}^{*}-\beta\mu{\cal
N}+\cdots$, where we have borrowed the statistical mechanics notation
involving the equilibrium “chemical potential” $\mu$. At the extremum, this
leads to the simplification of the first two terms in Eq. (12) to $\bar{\cal
S}({\cal K}^{*},{\cal N})+\alpha{\cal K}^{*}=-\beta\mu{\cal N}$ from which it
then follows that:

$\displaystyle\omega({\cal K},{\cal N})$ $\displaystyle=2^{-\frac{1}{2{\cal
N}T^{2}c_{{\cal N}}}{\Delta{\cal K}}^{2}}\;2^{-\beta\mu{\cal N}}\;.$ (13)

Thus, the probability distribution in Eq. (11) is a Gaussian peaked at
${\bar{\cal K}}={\cal K}^{*}=\kappa^{*}{\cal N}$ linear in ${\cal N}$ with a
width (root mean square deviation) $\Delta_{\rm rms}\propto\sqrt{{\cal
N}T^{2}c_{{\cal N}}}$, where $c_{{\cal N}}=-{\partial{\cal K}}/{\partial
T}{|}_{{\cal K}^{*},{\cal N}}$ is a positive intensive quantity analogous to
the specific heat in thermodynamics, which, in physical systems measures the
increase in energy induced by an increase in temperature and controls energy
fluctuations around the thermal equilibrium state at temperature $T$. In our
case, note the negative sign in the definition of $c_{{\cal N}}$: this
accounts for the fact that increasing temperature (i.e., increasing entropy)
implies a decrease in complexity. Moreover, Eq. (13) and the sum rule
$\sum_{P}\;\Omega(P,{\cal N})=\sum_{{\cal K}=0}^{{\cal N}}\omega({\cal
K},{\cal N})=|G|^{\cal N}$ determines the leading behavior of the chemical
potential, $\mu=-T\log_{2}|G|$.

It is important to stress that we expect that generic solutions of the
extremum condition $\alpha=\beta(\kappa^{*})$ for $\kappa^{*}$, which depend
on the gate set through the value of $\alpha$, are neither 0 nor 1 but lie in
between, $0<\kappa^{*}<1$. This expectation underscore two important
conclusions of our paper, which we conjecture will survive more rigorous
treatments: (a) generic circuits display a finite circuit compressibility with
a compression factor $\eta=(1-{\cal K}^{*}/{\cal N})$, with $0<\eta<1$; and
(b) the average complexity grows linearly with the depth of the circuit. We
stress that these results hinge on an important and non-trivial feature that
emerges from the thermodynamic arguments at the root of Eq. (8) and the
resulting condition $\alpha=\beta(\kappa)$, namely the balance between two
competing effects: the exponential increase in the density of states
$\nu({\cal K})\approx 2^{\alpha{\cal K}}$ and the decrease in the entropy
$\bar{\cal S}({\cal K},{\cal N})$ with increasing ${\cal K}$. We also note
that, while our extensivity assumption for $\log_{2}\nu({\cal K})$ and the
linear increase of the average complexity with circuit depth should hold up to
a maximum complexity exponential in $n$, $\mathcal{{\cal K}}_{\rm max}\sim
n\;2^{n}$, our focus is on polynomial (in $n$) size circuits with ${\cal
N}>>n$.

To further motivate the notion that generic circuits display a finite
compressibility with a compression factor $0<\eta<1$, we consider the
following scenario leading to a lower bound on $\eta$. Consider a random
circuit of 3-bit Toffoli gates and imagine “pushing” a gate through the
circuit until the gate encounters either (i) a gate with which it does not
commute, in which case we stop; or (ii) its inverse, in which case the pair
(the gate and its inverse) annihilate, decreasing the size of the circuit by
two gates (see Fig. 1). For a Toffoli gate, the probability that it does
commute with a gate on its path is of the order $1-{\cal O}(1/n)$, or
equivalently, a gate can be “pushed” through ${\cal O}(n)$ gates before either
stopping as in case (i) or annihilating as in case (ii). The overall
probability of annihilation is ${\cal O}(1/n^{2})$, accounting for the
probability ${\cal O}(1/n^{3})$ that the inverse is met in any of the ${\cal
O}(n)$ attempts before stopping. Hence, this process leads to a compression of
the circuit by a factor $(1-2\xi/n^{2})$ of its original size, where $\xi$ is
a constant of ${\cal O}(1)$. This implies that circuits with greater than
${\cal O}(n^{2})$ universal (Toffoli) gates are compressible with
$\eta=2\xi/n^{2}$, setting a lower bound for compressibility of random
circuits of universal gates. Indeed, since the probability of annihilation of
linear gates - NOTs and CNOTs - scales more favorably as $1/n$ and $1/n^{2}$
respectively, circuits comprised of gates from the universal set of Toffolis,
CNOTs, and NOTs are more compressible with a compression factor $\eta$ above
the Toffoli bound. [It is worth mentioning that since any linear circuit can
be implemented with ${\cal O}(n^{2})$ gates, purely linear circuits are highly
compressible, with $\eta\sim(1-n^{2}/{\cal N})$.]

Figure 1: An example of “pushing” a Toffoli gate $g$ past gates
$h_{1},h_{2},\dots,h_{p}$ so as to annihilate $g$ with its inverse $\tilde{g}$
(identical to $g$ for a Toffoli gate), thereby reducing the circuit size by
two gates. Typically, in a random circuit over $n$ bitlines, a Toffoli gate
can travel past ${\cal O}(n)$ gates with which it commutes before encountering
either a gate with which it does not commute or, with probability ${\cal
O}(1/n^{3})$, its inverse. The process depicted leads to a compression of the
circuit size by a factor $(1-2\xi/n^{2})$, where $\xi$ is a constant of ${\cal
O}(1)$.

Finally, we note that a compression factor $0<\eta<1$ also implies that
circuit collisions - i.e., multiple circuits implementing the same permutation
- are non-negligible. The importance of collisions can also be argued from a
lower bound for ${\cal S}(P,{\cal N})$,

$\displaystyle\left[{\cal N}-{\cal K}(P)\right]\;\log_{2}|G|^{1/2}\leq{\cal
S}(P,{\cal N})\;,$ (14)

which highlights the fact that there are exponentially many circuits that
realize any $P$. This result can be derived from a bound on ${\cal
S}({1\\!\\!1},{\cal N}-{\cal K}(P))$, which enters Eq. (3). In particular, we
proceed by placing bounds on the entropy of identities, ${\cal
S}({1\\!\\!1},{\cal N})$. By expressing ${\cal
N}=\sum_{\ell}a_{\ell}\;2^{\ell}$, where $a_{\ell}=0,1$ are the binary
coefficients in the expansion of ${\cal N}$ in base 2 (we shall assume that
${\cal N}$ is even), and then using Eq. (2) multiple times, it follows that
${\cal S}({1\\!\\!1},{\cal N})\geq\sum_{\ell}a_{\ell}\;{\cal
S}({1\\!\\!1},2^{\ell})\geq\sum_{\ell}a_{\ell}\;2^{\ell-1}{\cal
S}({1\\!\\!1},2)=\frac{{\cal N}}{2}{\cal S}({1\\!\\!1},2)=\frac{{\cal
N}}{2}\log_{2}|G|$, where we used that a two-gate identity can be written as
the product of any gate $g$ and its inverse $g^{-1}$. This bound on the
entropy of identities, together with Eq. (3), lead to Eq. (14).

Thermodynamic mixing of circuits: The thermodynamic approach presented above
relies on the microcanonical assumption, namely that all ${\cal N}$-gate
circuits of a given functionality $P$ appear with equal weight in the count
$\Omega(P,{\cal N})$. This assumption hinges on “ergodicity” in the space of
circuits of a given functionality, a concept which implies a “microscopic”
dynamical process and “equilibration” of collections of gates in a circuit,
analogous to the thermalization induced by microscopic collisions of atoms or
molecules in a gas. We shall return to the complex and interesting question of
microscopic dynamics below. Here we concentrate on a coarse-grained model for
thermodynamic mixing on a “macroscopic” scale by dividing the circuit into
smaller pieces, and assuming that thermalization occurs on a “mesoscopic”
scale. In particular, the equilibration of an arbitrary (polynomial size)
circuit is established by connecting a string of short $m$-gate
segments/subcircuits. These “mesoscopic” subcircuits are assumed to be large
enough to obey the laws of circuit thermodynamics introduced above but small
enough so that an appropriate set of “microscopic” dynamical rules leads to
rapid equilibration in a time $\tau_{eq}$.

More precisely, consider the situation depicted in Fig. 2, in which two
$m$-gate subcircuits of functionality $P_{1}$ and $P_{2}$, respectively, are
allowed to exchange gates and functionality via some dynamical rules.
Thermalization at the mesoscopic scale implies that, after a time scale
$\tau_{eq}$, (a) the counting of individual subcircuits (Fig. 2a) satisfy the
microcanonical assumption, and (b) the concatenated circuit with $2m$ gates
and functionality $P_{1}P_{2}$ satisfies the thermodynamic inequalities Eqs.
(2) and (5).

Figure 2: The elementary C-gate represents the equilibration between two
circuits of equal sizes ${\cal N}_{1}={\cal N}_{2}=m$. The two individual
$m$-gate circuits, depicted in (a), have functionalities $P_{1}$ and $P_{2}$,
respectively. In (b) they are brought into contact and exchange gates and
functionality, realizing a combined functionality $P_{1}P_{2}$, while
preserving the total number of gates ${\cal N}_{1}+{\cal N}_{2}=2m$. In (c),
following equilibration (symbolized by the red double-arrow in (b)) the
$2m$-gate circuit is split in the middle such that each of the partitions
contains $m$ gates and represents, respectively, functionalities
$P^{\prime}_{1}$ and $P^{\prime}_{2}$, with
$P^{\prime}_{1}\,P^{\prime}_{2}=P_{1}\,P_{2}$.

Given the mesoscopic thermalization assumption, we are now in position to
define a coarse-grained model for thermodynamic mixing that takes as input a
circuit $C$ that is split into $M$ subcircuits, each comprising of $m={\cal
N}/M$ gates: $C=c_{1}c_{2}...c_{M}$. A subcircuit $c_{i}$ ($i=1,\dots,M$) can
be thought of as a degree of freedom in a $d$-dimensional space with
$d=|G|^{m}$ states, i.e., a dit; and thus a circuit can be viewed as a string
of $M$ such dits. The coarse-grained mixing of the full circuit $C$ is
implemented as a circuit acting on dit-strings, i.e., a “circuit acting on
circuits” - hereafter referred to as a C-circuit - built out of gates acting
on dits, i.e., “gates acting on circuits” - referred to as C-gates. Fig. 3
depicts a brickwall C-circuit of C-gates acting on a pair of neighboring dits
$c_{i-1}(\tau)$ and $c_{i}(\tau)$ in layer $\tau$ and evolving them into
$c_{i-1}(\tau+1)$ and $c_{i}(\tau+1)$ after one “time” step, i.e., into layer
$\tau+1$ of the C-circuit. The brickwall C-circuit is a scrambler of circuits,
much as usual brickwall circuits of dit- or qudit-gates are scramblers of
states of dits or qudits (see for example Ref. [7] and references therein).

Figure 3: A brickwall C-circuit that progressively expands the “mesoscopic”
(local) equilibrium established between pairs of $m$-gate subcircuits
(depicted by the gray boxes) into a thermodynamically mixed equilibrium state
for the full circuit, while preserving the functionality of the original
concatenation of gates. Neighboring $m$-gate subcircuits are brought into
local thermal equilibrium via the exchange (depicted by the two-headed red
arrows) of gates and functionality (while preserving both the number of gates
and the combined functionality of the subcircuits). A subcircuit is paired
with either its neighbor to the left or to the right, alternating in each time
step (following the pattern of blue arrows).

The action of an individual C-gate, which takes place on a time scale longer
than $\tau_{eq}$, is based on the mesoscopic equilibration assumption, and is
implemented in three steps that parallel those depicted in Fig. 2, as follows:
(a) take $c_{i-1}(\tau)$ and $c_{i}(\tau)$, with functionalities
$P(c_{i-1}(\tau))$ and $P(c_{i}(\tau))$; (b) draw a circuit $c_{\rm aux}$
uniformly out of the $\Omega(P,2m)$ $2m$-gate circuits with functionality
$P=P(c_{i-1}(\tau))\,P(c_{i}(\tau))$; and (c) split the $2m$-gate circuit
$c_{\rm aux}$ into two $m$-gate circuits $c_{i-1}(\tau+1)$ and
$c_{i}(\tau+1)$. We note that the action of a C-gate on the two dits $c_{i-1}$
and $c_{i}$ preserves functionality of the product of the two associated sub-
circuits, a “conservation law” that maintains the functionality of the overall
circuit. (We also note that the stochastic process defined above could be
replaced by the action of a C-circuit built from deterministic C-gates with
given substitution truth tables chosen randomly.)

As alluded to above, the action of the brickwall C-circuit progressively
expands the “local” equilibrium within each of the $m$-gate subcircuits into
an thermodynamically mixed equilibrium state for a full circuit $C$ of any
size ${\cal N}$. The equilibration process induced via the C-circuit is
analogous to the equilibration of connected thermodynamic systems (e.g.,
containers of gas molecules) that were initially isolated from one another.
More specifically, this thermodynamic mixing of circuits reflects three
properties of the explicit C-circuit implementation: (i) the circuit entropy
after the application of each C-gate never decreases, but increases or remains
the same; (ii) through subsequent layers of the scrambling process,
functionalities of individual subcircuits change but the functionality of the
overall concatenated circuit is preserved; and, most importantly, (iii) the
thermalization in the space of dits defining the action of a stochastic C-gate
and the layer-by-layer evolution of the circuit leads to the branching into a
multitude of paths, which implies that memory of the initial circuit is lost,
i.e., the scrambling process is irreversible.

Given the one-dimensional brickwall arrangement of gates acting on $M$ dits,
such as the C-circuit in Fig. 3, the number of layers required for scrambling
the initial dit-string (in our case the initial circuit $C$) should scale as
$M^{\gamma}$. In random circuits acting on dits without conservation laws
$\gamma=1$ [6, 8, 9, 7] while in the presence of locally conserved quantities
we expect $\gamma\geq 2$ [10, 11, 12]. For the case of scrambling by
C-circuits, a C-gate acting on two subcircuits of functionalities $P_{1}$ and
$P_{2}$, respectively, may change $P_{1}$ and $P_{2}$ but preserves
$P_{1}P_{2}$. This more complicated “non-linear” conservation law has not yet
been analyzed in detail but we expect that both the saturation of the entropy
to its maximum attainable value and the state of uniform average complexity,
$\bar{{\cal K}_{i}}={\cal K}(P)/M$, for each of the $M$ subcircuits of a
C-circuit $C$ are reached within a time polynomial in $M$.

An application to Circuit Obfuscation: The C-circuit-based thermodynamic
mixing of circuits presented above provides a conceptual framework for circuit
obfuscation. Circuit obfuscation can be viewed as a gedanken experiment: take
two ${\cal N}$-gate circuits, $C_{1}$ and $C_{2}$, with the same functionality
$P$, and apply to each of them a functionality preserving scrambling procedure
that runs in polynomial time. As defined in Ref. [13], Indistinguishability
Obfuscation (IO) holds if at the end of the process an adversary with
polynomial resources cannot distinguish whether a given obfuscated circuit
originated from $C_{1}$ or $C_{2}$. Indeed, as we have seen from the
discussions above, a sufficiently large C-circuit is a good circuit obfuscator
since the scrambling process removes all information about initial circuits
and thus an adversary with polynomial resources would not be able to
distinguish which scrambled circuit originated from which initial circuit.

We note that the general line of reasoning presented so far makes certain
assumptions, some of which will be challenged below. In particular, the notion
of fragmentation of the space of circuits of a given size and functionality
into disconnected sectors, which we introduce shortly, will restrict the
thermodynamic framework to individual sectors. As discussed below,
fragmentation of circuit space has conceptual implications for the problem of
circuit obfuscation.

Microscopic dynamics of circuits: All thermodynamics-based arguments presented
thus far rely on the assumption of ergodicity, namely that some microscopic
dynamical rules that connect circuits of same size and functionality lead to a
uniform covering of the space of all such circuits. Moreover, we assumed that
equilibration across the space of circuits is achieved in polynomial time,
i.e., that, given the dynamical rules, connecting any two circuits can be
achieved with a number of steps that scales polynomially in the number of
gates, ${\cal N}$. This assumption raises a number of interesting and up to
now unexplored questions.

To begin with, by contrast to motion of molecules in a gas in the course of
collisions, which is governed by physical laws, there is no unique or natural
dynamics for moving/colliding gates in a circuit in ways that preserve
functionality. A naive notion of gate collisions, analogous to collisions of
gas particles, must take into account the non-commutative algebra of gates in
a universal set. If one defines a collision as an interchange of gates $g_{1}$
and $g_{2}$ acting on shared bitlines, then preserving functionality before
and after the collision implies, generically, a substitution
$g_{1}\,g_{2}\leftrightarrow g_{2}\,D\,g_{1}$, where $D$ is a “debris” gate
needed so that algebraically $g_{1}\,g_{2}=g_{2}\,D\,g_{1}$. An example of
such a collision is illustrated in Fig. 4a for two Toffoli gates. A
macroscopic number of such debris-generating collisions would inevitably lead
to an irreversible increase in the size of the circuit, violating the
constraint of a fixed number of gates.

Figure 4: (a) An example of a collision (the interchange)
$g_{1}\,g_{2}\leftrightarrow g_{2}\,D\,g_{1}$, where the debris gate $D$ is
needed to preserve the functionality of the initial two-gate segment of the
circuit. (b) An example of a substitution of a segment with $k=3$ gates,
$g_{1}\,g_{2}\,g_{3}\leftrightarrow
g^{\prime}_{1}\,g^{\prime}_{2}\,g^{\prime}_{3}$. The same arrangements in (b)
can be used as examples of two functionally equivalent circuits with ${\cal
N}=3$ that cannot be connected via a $k=2$ substitution rule.

A more fruitful direction is to define a dynamics in the space of circuits
based on gate-substitution rules that exchange a string of gates with an
alternate string with same size and functionality. One can view an ${\cal
N}$-gate circuit as a quasi-1D system, or a chain of ${\cal N}$ sites, in
which a gate $g_{i}$ (a non-Abelian group element) is placed at each site $i$.
Global functionality is determined by $P=g_{1}\;g_{2}\cdots g_{\cal N}$, and a
local microscopic dynamics must preserve this overall functionality. The
functionality-preserving local dynamical model we have in mind involves the
following substitution of a string of $k$ consecutive gates:

$\displaystyle\left(g^{\,}_{i},g^{\,}_{i+1},\dots,g^{\,}_{i+k}\right)$
$\displaystyle\longleftrightarrow\left(g^{\prime}_{i},g^{\prime}_{i+1},\dots,g^{\prime}_{i+k}\right)$
(15a) $\displaystyle g_{i}\,g_{i+1}\,\dots\,g_{i+k}$
$\displaystyle\;\;=\;\;g^{\prime}_{i}\,g^{\prime}_{i+1}\,\dots\,g^{\prime}_{i+k}\;.$
(15b)

An example of a $k=3$ circuit identity involving Toffoli and CNOT gates is
shown in Fig. 4b. Substitution rules for fixed (and small) $k$ can be built
from a catalog of strings of $k$ gates that multiply to the same permutation.
Transition probabilities among the $k$-length strings, in the case the catalog
is exhaustive, can be chosen to be

$\displaystyle
T_{\left(g^{\,}_{i},\dots,g^{\,}_{i+k}\right),\left(g^{\prime}_{i},\dots,g^{\prime}_{i+k}\right)}=\frac{1}{\Omega(g_{i}\,\dots\,g_{i+k},k)}\;\delta_{g_{i}\,\dots\,g_{i+k},g^{\prime}_{i}\,\dots\,g^{\prime}_{i+k}}\;.$
(16)

We note that the stochastic C-gate used above can be implemented via such a
transition matrix element with $k=2m$. Alternatively, one can dilute the
connectivity associated with the $T$-matrix so that not all pairs of
$k$-strings satisfying Eqs. (15) are connected via a matrix element. We note
that since the number of circuits with $k$ gates is $|G|^{k}$, enumerating the
equivalence rules for large $k$ becomes prohibitive.

While to our knowledge this type of dynamical model has not been discussed in
the literature and a detailed study of the model is outside the scope of this
paper, we can already point to a set of fundamental issues that have important
implications for the discussion of circuit thermodynamics. In particular, our
intuition suggests that the space of circuits with functionality
$P=g_{1}\;g_{2}\cdots g_{\cal N}$ evolving via $k$-range rules will
generically fragment into a number of disconnected sectors. A simple example
that supports the notion of fragmentation is to consider a functionality-
preserving dynamics that only connects 2-strings if and only if two
neighboring gates $g_{i}$ and $g_{i+1}$ commute, in which case we exchange
$(g_{i},g_{i+1})\leftrightarrow(g_{i+1},g_{i})$ with probability 1/2. This
dynamics allows a gate to move left and right through the list of gates in the
circuit by passing other gates with which it commutes, but not past those
gates with which it does not commute. This dynamics preserves the number of
gates of each type in the circuit and thus does not allow one to connect the
two equivalent circuits in Fig. 4b. A less restricted dynamics with $k=2$ in
this same example would still not allow the two sequences of three gates in
Fig. 4b to be connected.

Fragmentation implies that a particular dynamics is ergodic only within
individual sectors, and thus all the thermodynamic results would apply, but
only within each disconnected sector. Implicit in this statement is that,
within a given sector, ergodicity is reached within a number of steps defining
the particular dynamics that is polynomial in ${\cal N}$. In this case, the
finite compressibility of generic circuits is an example of a property that
survives in the fragmented system, where the compression factor should be
determined by some weighted average over fragments.

The above intuition concerning fragmentation and polynomial thermalization is
further supported by arguments from the theory of computational complexity.
According to these arguments, connecting any two circuits of the same
functionality and size via a polynomial number of local functionality
preserving dynamical moves would imply the equality NP = coNP of two
complexity classes, namely NP - decision problems for which polynomial time
solutions are not known but for which a YES solution can be checked in
polynomial time; and coNP - decision problems for which polynomial time
solutions are not known but for which a NO solution can be checked in
polynomial time. Even though it is widely believed that NP $\neq$ coNP,
rigorously justifying this belief (or its negation) is an open problem in
computer science. In order to understand the above claim consider the Circuit
Equivalence problem, the problem of deciding whether two (polynomial-sized)
circuits are equivalent. Circuit Equivalence is known to be a problem in coNP,
since a NO solution can be easily checked by comparing the outputs of the two
circuits on a given input. At the same time, if any two circuits could be
connected by a polynomial number of dynamical moves, even if difficult to
find, this set of moves can be used to verify a YES solution of the Circuit
Equivalence problem in polynomial time, placing Circuit Equivalence also in
NP. Similarly, a parallel set of arguments can be used to argue that Circuit
Inequivalence, i.e., the problem of deciding that two (polynomial-sized)
circuits are inequivalent, which is a problem in NP, is also in class coNP
since the connectivity of any two circuits via a polynomial number of moves
could be used to verify the NO solution of Circuit Inequivalence (i.e.,
equivalence) in polynomial time. Moreover, it is also well known that Circuit
Equivalence and Circuit Inequivalence are among the hardest problems in their
respective coNP and NP classes, i.e., they are in classes coNP-complete and
NP-complete, respectively. “Completeness” indicates that any problem in coNP
or NP can be reduced, respectively, to Circuit Equivalence or Circuit
Inequivalence in polynomial time. Given that a polynomial number of dynamical
moves placed Circuit Equivalence in NP and Circuit Inequivalence in coNP the
conclusions of the above line of argumentation are that: (i) all problems in
coNP are in NP (coNP $\subset$ NP); (ii) all problems in NP are in coNP (NP
$\subset$ coNP); and thus that (iii) NP = coNP. As already alluded to above,
this conclusion contradicts widely accepted beliefs in computational
complexity and implies that, in our context, fragmentation is unavoidable,
regardless of whether the polynomial sequence of moves connecting pairs of
circuits is easy or hard to find.

Clearly, fragmentation and the accompanying broken ergodicity significantly
alters the discussion of circuit obfuscation. For a system with multiple
sectors, the relevant question becomes: given two circuits $C_{1}$ and
$C_{2}$, can one decide in polynomial time whether they belong to the same
ergodic (thermalized) sector or not? Physical intuition based on the
scrambling of information, irreversibility, and chaos in closed systems with
large number of degrees of freedom leads to a natural conjecture that, for
non-trivial dynamical rules, this is a hard (NP) decision problem. If this is
the case, then the thermodynamic framework does in fact provide a path to
Indistinguishability Obfuscation of any two circuits, $C_{1}$ and $C_{2}$.
Otherwise the thermodynamic framework could only establish IO for circuits in
the same sector.

## Discussion and future directions

This paper presents a thermodynamic framework for describing course-grained
properties of large ${\cal N}$-gate reversible classical circuits with ${\cal
N}\gg n$ (with ${\cal N}$ polynomial in $n$, the number of bitlines of the
circuit) and a given functionality, defined by the permutation $P$ implemented
by the circuit. Our construction of circuit thermodynamics is based on three
assumptions that underpin the logical consistency of the approach: (i) the
functionality $P$ only appears through the circuit complexity ${\cal K}(P)$,
i.e., the minimum number of gates required for the implementation of the
permutation $P$; (ii) the entropy defined by counting of the number of
possible ${\cal N}$-gate circuits implementing $P$ is extensive in ${\cal N}$
and ${\cal K}(P)$; and (iii) ergodicity in the space of circuits, which as a
result of fragmentation can only occur in disconnected sectors, requires a
“time” (i.e., number of dynamical moves) that is polynomial in ${\cal N}$, the
size of the circuit.

The fragmentation of the space of circuits suggests a number of questions we
expect to address through more detailed analytical and computational studies:
(i) is there is a critical value $k_{c}$ such that if $k_{c}\leq k\leq{\cal
N}$ the space of circuits of size ${\cal N}$ and functionality $P$ becomes
fully connected, and how does this value scales with the number of bitlines
$n$? (ii) If the space is fragmented, how does the number of fragments scale
with $k$ and ${\cal N}$ and (possibly) the complexity of $P$? (iii) can one
make more precise statements about the hardness of deciding whether any two
circuits belong to the same or different sectors? We note that even though we
raise these questions in the context of the permutation group $S_{2^{n}}$, the
thermodynamic framework and the issues it raises can be generalized to other
groups.

In summary, the thermodynamic perspective to complexity and functionality of
circuits provides a framework that may stimulate new ways of thinking and new
problems at the interface between physics and computer science. In particular,
the issue of fragmentation, which is a topic of much current interest to the
physics communities working on classical and quantum dynamics [14, 15, 16, 17,
18], may raise new questions for the computer science community, which to our
knowledge have not been explored. Conversely, the question of the scaling of
information scrambling rates with system size for systems with
“multiplicative” rather than additive conservation laws (as is the case with
the functionality of circuits) may intrigue and inspire physicists interested
in classical and quantum dynamics.

## Acknowledgments

We are grateful to Alexsey Khudorozhkov and Guilherme Delfino for insightful
discussions. This work was supported in part by DOE Grant DE-FG02-06ER46316
(C.C.) and a Grant from the Mass Tech Collaborative Innovation Institute
(A.E.R.). R.C., C.C., and A.E.R. also acknowledge the Quantum Convergence
Focused Research Program, funded by the Rafik B. Hariri Institute at Boston
University.

## References

  * [1] Valentine Kabanets and Jin-Yi Cai.  Circuit minimization problem.  In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC ’00, page 73–79, New York, NY, USA, 2000. Association for Computing Machinery.
  * [2] Alexander A Razborov and Steven Rudich.  Natural proofs.  Journal of Computer and System Sciences, 55(1):24–35, 1997.
  * [3] Leonard Susskind.  Three lectures on complexity and black holes, 2018.
  * [4] Adam R. Brown, Leonard Susskind, and Ying Zhao.  Quantum complexity and negative curvature.  Phys. Rev. D, 95:045010, Feb 2017.
  * [5] Adam R. Brown and Leonard Susskind.  Second law of quantum complexity.  Phys. Rev. D, 97:086015, Apr 2018.
  * [6] Patrick Hayden and John Preskill.  Black holes as mirrors: quantum information in random subsystems.  Journal of High Energy Physics, 2007(09):120, sep 2007.
  * [7] Aram W. Harrow and Saeed Mehraban.  Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates.  Communications in Mathematical Physics, 401(2):1531–1626, May 2023\.
  * [8] Winton Brown and Omar Fawzi.  Scrambling speed of random quantum circuits, 2013.
  * [9] Winton Brown and Omar Fawzi.  Decoupling with random quantum circuits.  Communications in Mathematical Physics, 340(3):867–900, September 2015.
  * [10] Tibor Rakovszky, Frank Pollmann, and C. W. von Keyserlingk.  Diffusive hydrodynamics of out-of-time-ordered correlators with charge conservation.  Phys. Rev. X, 8:031058, Sep 2018.
  * [11] Vedika Khemani, Ashvin Vishwanath, and David A. Huse.  Operator spreading and the emergence of dissipative hydrodynamics under unitary evolution with conservation laws.  Phys. Rev. X, 8:031057, Sep 2018.
  * [12] Sumner N. Hearth, Michael O. Flynn, Anushya Chandran, and Chris R. Laumann.  Unitary k-designs from random number-conserving quantum circuits, 2023\.
  * [13] Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang.  On the (im)possibility of obfuscating programs.  In Joe Kilian, editor, Advances in Cryptology — CRYPTO 2001, pages 1–18, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
  * [14] F. Ritort and P. Sollich.  Glassy dynamics of kinetically constrained models.  Advances in Physics, 52(4):219–342, June 2003.
  * [15] Sanjay Moudgalya, B Andrei Bernevig, and Nicolas Regnault.  Quantum many-body scars and hilbert space fragmentation: a review of exact results.  Reports on Progress in Physics, 85(8):086501, July 2022.
  * [16] Vedika Khemani, Michael Hermele, and Rahul Nandkishore.  Localization from hilbert space shattering: From theory to physical realizations.  Phys. Rev. B, 101:174204, May 2020.
  * [17] Sanjay Moudgalya and Olexei I. Motrunich.  Hilbert space fragmentation and commutant algebras.  Phys. Rev. X, 12:011050, Mar 2022.
  * [18] Zhi-Cheng Yang, Fangli Liu, Alexey V. Gorshkov, and Thomas Iadecola.  Hilbert-space fragmentation from strict confinement.  Phys. Rev. Lett., 124:207602, May 2020.


# Prototypical Fine-tuning: Towards Robust Performance Under Varying Data
Sizes

Yiqiao Jin1, Xiting Wang2111Xiting Wang is the corresponding author., Yaru
Hao2, Yizhou Sun3, Xing Xie2 Work done during an internship at Microsoft
Research Asia.

###### Abstract

In this paper, we move towards combining large parametric models with non-
parametric prototypical networks. We propose prototypical fine-tuning, a novel
prototypical framework for fine-tuning pretrained language models (LM), which
automatically learns a bias to improve predictive performance for varying data
sizes, especially low-resource settings. Our prototypical fine-tuning approach
can automatically adjust the model capacity according to the number of data
points and the model’s inherent attributes. Moreover, we propose four
principles for effective prototype fine-tuning towards the optimal solution.
Experimental results across various datasets show that our work achieves
significant performance improvements under various low-resource settings, as
well as comparable and usually better performances in high-resource scenarios.

## Introduction

Pretrained language models (LM) have achieved substantial success on a variety
of NLP applications (Brown et al. 2020). Their high discriminative power is
partly attributed to a weak inductive bias, which poses little constraints on
the model expressivity, but leads to potential overfitting and local optimum,
especially in low-resource settings (McCoy, Pavlick, and Linzen 2019;
Belinkov, Henderson et al. 2021; Feldman 2020). On the other hand, non-
parametric models, such as prototypical networks (Snell, Swersky, and Zemel
2017; Yang et al. 2018; Shao et al. 2017), introduce strong inductive biases
and explicitly model the inter-class and intra-class relations within the
data, which is especially useful when training data is limited. These methods
are promising for improving generalization and increasing sample efficiency
(Snell, Swersky, and Zemel 2017; Allen et al. 2019). However, as strong
inductive biases restrict the hypothesis set of function approximators, these
models introduce false assumptions that may limit the expressivity of models
as the number of data points increases (Baxter 2000).

In this paper, we move towards combining large parametric models with non-
parametric prototypical networks so that we automatically learn a bias to
improve predictive performance on varying sizes of datasets, especially for
low-resource settings. Achieving this goal is non-trivial due to two major
challenges. First (_adaptation_), how to introduce prototype modeling into
large-scale language models to jointly ensure superior performances under low-
resource scenarios while mitigating the over-reliance of prototype learning on
strong inductive biases? Second (_capacity_), different datasets have diverse
levels of complexity, thus requires different volumes of prototypes and
parameters to properly represent the data distribution (Mettes, van der Pol,
and Snoek 2019). Choosing model capacity generally requires heuristics and
knowledge about the data distribution (Allen et al. 2019). How to determine
the number of prototypes automatically by jointly considering complexity of
the data distribution and the model’s inherent attributes to ensure robust
performances on datasets with varying sizes?

To solve these two challenges, we propose Prototypical Fine-tuning (PFit). Our
method represents the data within each class as a set of prototypes, each
modeled as a mixture component, while learning the number of components
automatically based on the model capacity and the complexity of data
distribution. At the initial stage of training, our method is equivalent to
ProtoNet (Snell, Swersky, and Zemel 2017), which ensures a high-quality
initialization of the prototypes and facilitates convergence towards a
globally optimal solution. As training proceeds, _PFit_ chooses from fitting
each new example with existing prototypes or initiating a new prototype based
on the data point, according to whether the example is in-distribution. We
allow the number of prototypes to grow and shrink dynamically with respect to
the data complexity. In all, our method ensures a hypothesis space large
enough for viable solutions to the tasks being learned (Baxter 2000), but
small enough for generalization. Thus, our method is well-suited for both
data-scarce and data-rich tasks, especially offering substantial performance
gain under low-resource scenarios. The contributions of this paper are
summarized as follows:

1) We propose _Prototypical Fine-tuning (PFit)_ , a novel prototypical method
for fine-tuning pretrained language models by integrating the strengths of
bayesian non-parametrics with parametric pretrained LMs, leading to superior
predictive performance under varying data sizes.

2) We propose four principles for effectively leveraging non-parametric
methods , which are mixture prototype initialization, infinite mixture
prototype creation, adaptive prototype refinement, and dynamic diversity
regularization, so that our method maintains a compact set of prototype
embeddings conducive to its decision-making;

3) We conduct extensive experiments and show that _PFit_ achieves considerable
performance improvements under varying data sizes, as well as comparable or
better performances for high-resource settings.

## Related Work

### Prototypical Learning

Prototypical Learning (Mettes, van der Pol, and Snoek 2019; Snell, Swersky,
and Zemel 2017; Oreshkin, Rodríguez López, and Lacoste 2018) is closely
related to metric learning (Goldberger et al. 2004; Oh Song et al. 2016) and
case-based reasoning (Li et al. 2018; Kim, Rudin, and Shah 2014; Kolodner
1992). It has been used for improving model interpretability (Li et al. 2018;
Chen et al. 2019) and few-shot classification (Snell, Swersky, and Zemel 2017;
Gao et al. 2019). Most existing works combine bayesian non-parametrics with
representation learning and learn a single prototype for each class (Vinyals
et al. 2016; Snell, Swersky, and Zemel 2017), based on the uni-modality
assumption of embedded class examples. As an extension, multi-modal methods
(Hjort et al. 2010; Rasmussen 1999; Mensink et al. 2013; Ackerman and Dasgupta
2014) assume an infinite number of mixtures, but only a finite number are used
to generate the data. In particular, infinite mixture prototype (IMP) (Allen
et al. 2019; Kulis and Jordan 2012) adaptively fits the data distribution
through a varied number of clusters for each class. Notably, existing works
lack an efficient mechanism to be dynamically scaled on datasets with varying
sizes.

### Low-Resource

Due to the cost of acquiring high-quality labeled data, researchers have been
working on improving model performances under low-resource settings. A special
case is few-shot learning (Wang et al. 2021; Tsimpoukelli et al. 2021; Perez,
Kiela, and Cho 2021) in which data is severely limited. Earlier works address
data sparsity through large unlabeled datasets (Gunel et al. 2020; Artetxe et
al. 2018), data augmentation (Salamon and Bello 2017; Fadaee, Bisazza, and
Monz 2017), or the removal of redundant information in the pretraining
representation (Belinkov, Henderson et al. 2021). These methods usually
introduce extra data or auxiliary models that increase the computational cost.
Moreover, these works are usually designed for specific low-resource settings,
but cannot robustly scale to larger datasets with performance guarantee
(Zaken, Ravfogel, and Goldberg 2021). In this work, we propose a non-
parametric method suited for both low- and high- resource scenarios that
achieves particularly superior performances under the former settings.

## Method

In this section, we first introduce the general workflow for fine-tuning
language models. Then, we present the proposed approach _PFit_ and show how it
achieves superior performances under varying data sizes.

Figure 1: Our proposed _PFit_ framework. During fine-tuning, the prediction of
each example $x_{i}$ is given by individual predictions of prototypes weighted
by their distance to $f_{\phi}(x_{i})$. _PFit_ is able to dynamically add or
prune prototypes, depending on whether existing prototypes can characterize
the distribution of data.

### Problem Statement

Input The input for fine-tuning is a labeled dataset
$\mathcal{D}=\\{(x_{i},y_{i})\\}_{i=1}^{N}$, where each example $x_{i}\in X$
is an input text sequence, and $y_{i}\in\\{1,\ldots,C\\}$ is the ground-truth
label.

Output The outputs consist of 1) $\mathbb{P}(y\mid x_{i})$, the prediction of
each example $x_{i}$; 2) the fine-tuned model
$f_{\phi}(\cdot):X\rightarrow\mathbb{R}^{C}$ that maps an input sequence to a
probability distribution over $C$ classes.

### Prototypical Fine-tuning

Pretrained language models are fine-tuned in a fully parametric way (Wu et al.
2022a). The inference is conducted in a case-by-case manner by computing
$\mathbb{P}(y\mid x_{i})$. This way, performances of LMs predominantly stem
from their large-scale parameters, whereas they do not explicitly leverage the
class distribution and instance-level similarity among training examples,
which is especially useful when data is limited.

To alleviate this problem, we explicitly model the inter-class and intra-class
relations by introducing _prototypes_ , which are embeddings in the same
metric space as $f_{\phi}({x}_{i})$ that abstracts the essential semantics of
multiple $x_{i}$’s (Snell, Swersky, and Zemel 2017). In our case, we learn a
compact set of prototypes $\mathbf{p}_{1\sim K}$ from $\mathcal{D}$ that
serves as references for model prediction. We split the inference into two
components: 1) prototype prediction of each $\mathbf{p}_{k}$ conditioned on
the entire training set $\mathcal{D}$; 2) prototype importance that measures
the compatibility between each $\mathbf{p}_{k}$ and $x_{i}$.

$\mathbb{P}(y\mid
x_{i},\mathcal{D})=\sum_{k=1}^{K}\underbrace{\mathbb{P}(y\mid\mathbf{p}_{k},\mathcal{D})}_{\begin{subarray}{c}\text{Prototype}\\\
\text{Prediction}\end{subarray}}\underbrace{\mathbb{P}(\mathbf{p}_{k}\mid
x_{i})}_{\begin{subarray}{c}\text{Prototype}\\\
\text{Importance}\end{subarray}}$ (1)

When infering on a new unclassified exemplar, prototypical networks calculates
joint prediction probability $\mathbb{P}(y\mid x_{i},\mathcal{D})$ and
efficiently adapts existing prototypes to the new data rather than deriving
answers from scratch. Under this formulation, prototypical networks focus on
critical aspects of the data distribution and filter irrelevant or noisy
features that are detrimental to their decision-making (Kolodner 1992) better
at finding a globally optimal solution.

#### Prototypical Network

Under the prototypical learning paradigm, each $x_{i}$ is encoded into a
$D$-dimensional feature vector $f_{\phi}(x_{i})\in\mathbb{R}^{D}$ and matched
against a set of prototypes $\mathbf{p}_{k}$ in a learned latent space
according to some distance metric $d(\cdot,\cdot)$. The importance of
prototype $\mathbf{p}_{k}$ with respect to $x_{i}$ is measured by:

$\mathbb{P}(\mathbf{p}_{k}\mid
x_{i})\propto\operatorname{exp}(-d(f_{\phi}(x_{i}),\mathbf{p}_{k}))$ (2)

where $d(\cdot,\cdot)$ is usually taken as the squared L2 distance.
Prototypical methods (Snell, Swersky, and Zemel 2017) calculate the prototype
of each class $c$ as the averaged embedding of
$\mathcal{D}_{c}\in\mathcal{D}$, or the support data within class $c$:

$\mathbf{p}_{c}=\frac{1}{\left|\mathcal{D}_{c}\right|}\sum_{\left(x_{i},y_{i}\right)\in\mathcal{D}_{c}}f_{\phi}(x_{i})$
(3)

Prediction is conducted by calculating the distance from $f_{\phi}(x_{i})$ to
each prototype vector.

$\mathbb{P}(y=c\mid
x_{i})=\frac{\exp(-d(f_{\phi}(x_{i}),\mathbf{p}_{c}))}{\sum_{c^{\prime}}\exp(-d(f_{\phi}(x_{i}),\mathbf{p}_{c^{\prime}}))}$
(4)

#### Our PFit Framework

Our goal is to learn a Prototypical Fine-tuning (PFit) network with robust
performances under both low- and high-resource settings. The training
procedure is detailed in Alg. 1. Compared with a transformer-based model, PFit
contains an additional prototype learning module $P$ that can flexibly adjust
the capacity of its prototype embeddings $\mathbf{p}_{k}$ according to the
data distribution. Our proposed PFit framework can be easily built on top of
any backbone pretrained LMs. It pursues 4 approaches for robustness and
expressivity under varying data sizes:

1) _Mixture Prototype Initialization._ We leverage the high-level semantic and
linguistic features in pretrained representations to initialize the prototypes
for faster convergence;

2) _Infinite Mixture Prototype Creation._ We extend infinite mixture prototype
(Allen et al. 2019) to flexibly capture the complexity of the distribution.
The prototype embeddings are fine-tuned along with the pretrained model in a
data-driven manner;

3) _Adaptive Prototype Simplification._ To improve generalization and
efficiency, we leverage simple inductive biases and maintain a compact set of
prototypes that sufficiently represent the data distribution.

4) _Dynamic Diversity Regularization._ We dynamically enforce diversity among
prototypes to ensure the expressivity and efficiency of our prototypical
framework.

#### Mixture Prototype Initialization

At the start of training, a simple yet strong inductive bias can ensure robust
generalization since the amount of data is relatively limited (Snell, Swersky,
and Zemel 2017). Previous studies have shown that transformer models encode
high-level semantic and linguistic features in their representations (Tenney,
Das, and Pavlick 2019; Jawahar, Sagot, and Seddah 2019; Hao et al. 2020; Guan
et al. 2019), leading to superior performances in various downstream tasks
(Yang et al. 2022b; Jin et al. 2022b; Yang et al. 2022c). Therefore, we
propose _mixture prototype initialization_ to leverage the rich semantics in
the sentence representations (Yang et al. 2022a). Before fine-tuning starts,
for each class $c$, we randomly sample a subset of $n$ examples with label
$c$, and aggregate their $f_{\phi}(x_{i})$ with $\phi$ frozen:

$\mathbf{p}_{c}=\operatorname{Aggr}([f_{\phi}({x}_{1}),\ldots,f_{\phi}({x}_{n})])$
(5)

In our case, we choose mean pooling as the aggregate function. We derive an
initial set of $C$ prototypes for all classes. Mixture prototype
initialization is analogous to ProtoNet (Snell, Swersky, and Zemel 2017) and
assumes that the classes form uni-modal clusters. Such initialization can
empower the prototypes with the semantics of transformer word representations
with little computational cost. Meanwhile, it does not require extra
parameters or training, only the intrinsic features of language models.

#### Infinite Mixture Prototype Creation

As the training proceeds, existing prototype embeddings become less capable of
assimilating new data points. Higher capacity is required to model the growing
data complexity. A straightforward remedy is to directly create a set of $K$
prototypes and automatically learn meaningful representations from the
training data. However, such method is largely subject to the choice of model
capacity, either underfitting or overfitting the data (Snell, Swersky, and
Zemel 2017; Ren et al. 2018). Second, in practice, this method usually yields
highly similar prototypes (Ming et al. 2019) which hampers the expressivity of
the prototype module and leads to sub-optimal convergence.

Motivated by (Allen et al. 2019), we seek informative samples from the
training data that contribute to the diversity of the prototypes and the
expressivity of the fine-tuned models. Let $P^{c}$ be the set of prototypes
under class $c$. For each example $x_{i}\in\mathcal{D}_{c}$, if the minimum
distance between $f_{\phi}(x_{i})$ and any prototypes in $P^{c}$ exceeds a
threshold $\lambda$, a new prototype is created based on $f_{\phi}(x_{i})$.
The threshold distance $\lambda$ is given by:

$\lambda=2\sigma\log\left(\frac{\alpha}{\left(1+\frac{\rho}{\sigma}\right)^{d/2}}\right)$
(6)

where $\sigma$ is the cluster variance that is learned jointly with $\phi$.
$\rho$ measures the standard deviation for the base distribution from which
the cluster means are sampled. $\alpha$ is a hyperparameter that controls the
concentration of clusters in the Chinese Restaurant Process (Wang and Blei
2009). This way, our approach can choose between fitting simple data
distribution with low capacity and complex distribution with high capacity. As
a further extension, we only allow the creation of prototypes after being
fine-tuned for a certain number of steps. This way, the initial $C$ prototypes
are sufficiently trained along with $\phi$ so that meaningful prototypes can
be created. For computational and storage efficiency, we restrict the size of
prototypical networks to $|P_{max}|$.

#### Prediction

During fine-tuning, language models classify new examples by applying an MLP
on the word representations. PFit instead directly learns a distribution over
all $C$ classes for each $\mathbf{p}_{k}$. During fine-tuning, PFit learns a
distribution over all $C$ classes for each $\mathbf{p}_{k}$. Specifically,
each $\mathbf{p}_{k}$ directly correlates with a learnable vector
$\mathbf{l}_{k}\in\mathbb{R}^{C}$, which gives a probability distribution over
all $C$ classes:

$\mathbb{P}(y=c\mid\mathbf{p}_{k},\mathcal{D})=\operatorname{softmax}_{c}(l_{kc});~{}~{}\mathbf{l}_{k}=[l_{k,1},\ldots,l_{k,C}]$
(7)

During initialization, for each newly created prototype $\mathbf{p}_{k}$,
$l_{k,y_{i}}$, the value in $\mathbf{l}_{k}$ that corresponds to the ground-
truth class $y_{i}$, is initialized to $\beta$, a positive real number. The
value for all other classes $l_{k,c},c\in\\{1,\ldots,C\\}\backslash y_{i}$ are
initialized to $-\beta$. During fine-tuning, $\mathbf{l}_{k}$ is optimized
together with its corresponding $\mathbf{p}_{k}$ in a data-driven manner. In
order to keep the predicted label constant, $l_{k,y_{i}}$, which corresponds
to the ground-truth class $y_{i}$, is constrained in $[0,+\infty)$.
Predictions for other classes are constrained in $(-\infty,0]$. Compared with
existing prototypical approaches which usually use a constant value for
prototype predictions, our method can achieve superior expressivity.

The prototype importance $z_{i,k}$ is given by the normalized Gaussian
density:

$\mathbb{P}(\mathbf{p}_{k}\mid
x_{i})=z_{i,k}=\frac{\mathcal{N}(f_{\phi}(x_{i});\mathbf{p}_{k},\sigma_{k})}{\sum_{k^{\prime}}\mathcal{N}(f_{\phi}(x_{i});\mathbf{p}_{k^{\prime}},\sigma_{k^{\prime}})}$
(8)

The joint probability of $\mathbf{p}_{k}$ predicting class $c$ is given by Eq.
1. Intuitively, our model is analogous to a retrieval system or an attention-
based model (Vaswani et al. 2017), in which a query example is mapped against
a set of key-value pairs. The weight assigned to each value is computed by a
compatibility function between the query and each key. The prediction result
is a linear combination of values weighed by the compatibility between the
query example $f_{\phi}(x_{i})$ and existing prototypes $\mathbf{p}_{k}\in P$.

Algorithm 1 Prototypical Fine-tuning

Input: $\mathcal{D}=(x_{i},y_{i})$, where each $y_{i}\in\\{1,\ldots,C\\}$

Output: prototypes $\mathbf{p}_{k}$ and the classification of each example
$\mathbb{P}(y\mid\mathbf{p}_{1\sim K},x_{i})$

1: Perform Mixture Prototype Initialization

2: for minibatch $B_{r}\in D$ do

3: Perform Infinite Mixture Prototype Creation and estimate $\lambda$
according to Eq. 6

4: for $x_{i}\in B_{r}$ do

5:

6: for $k\in\\{1,\ldots,K\\}$ do

7: {Compute the distance from $x_{i}$ to all existing prototypes}

8: Calculate $d_{i,k}=d(f_{\phi}(x_{i}),\mathbf{p}_{k})$ for
$\mathbf{p}_{k}\in P^{y_{i}}$, and $d_{i,k}=+\infty$ for $\mathbf{p}_{k}\notin
P^{y_{i}}$

9: end for

10: if $\operatorname{min}_{k}d_{i,k}>\lambda$ then

11: Create the $K+1$-th prototype $\mathbf{p}_{K+1}$ using $f_{\phi}(x_{i})$;
Increment $K$ by 1

12: end if

13: end for

14: if $\operatorname{min}_{k}d_{i,k}>\lambda$ then

15: Create the $K+1$-th prototype $\mathbf{p}_{K+1}$ using $f_{\phi}(x_{i})$;
Increment $K$ by 1

16: end if

17: end for

#### Adaptive Prototype Simplification

Simple inductive biases usually imply robust generalization to varying
datasets (Baxter 2000). To improve generalization and efficiency, we propose
_adaptive prototype simplification_ to ensure that a compact set of prototypes
sufficiently represent the data distribution. As prototypes are created with
examples that are sufficiently distinct from existing prototype embeddings, a
minority of prototypes may be created by outliers that are rarely observed in
the training data. These prototypes may fail to generalize to new data and are
likely to introduce noisy features or spurious correlations. To determine
unimportant prototypes, a simple way is to calculate the average prototype
importance $z_{i,k}$ in Eq. 8 between each $\mathbf{p}_{k}$ and
$f_{\phi}({x}_{i})$ in the training set. This leads to two potential issues:
1) acquiring $f_{\phi}(x_{i})$ and calculating $z_{i,k}$ among
$f_{\phi}(x_{i})$ and $\mathbf{p}_{k}$ (Eq. 8) requires $O(N|P_{max}|)$, both
of which are computationally expensive. 2) a direct remedy is to store all
$z_{i,k}$ calculated during training and use them during simplification.
However, the actual value of $z_{i,k}$ is constantly changing, as
$f_{\phi}(x_{i})$ and $\phi$ are continuously updating.

To solve the above two challenges, we introduce a sliding window of length
$\delta$, which records all $z_{i,k},i\in[T-\delta,T]$ at any training step
$T$. Upon prototype simplification, we prune prototypes with an average
prototype importance $\mathbb{P}(\mathbf{p}_{k}\mid x_{i})$ that fall below a
threshold $\varepsilon$:

$\frac{1}{\delta}\sum_{i}\omega(i,T,\delta)z_{i,k}<\varepsilon$ (9)

$\varepsilon$ is a hyperparameter controlling the minimum average importance
of $\mathbf{p}_{k}$ on all $f_{\phi}(x_{i}),i\in[T-\delta,T]$.
$\omega(i,T,\delta)=\frac{1}{\delta}(i-T+\delta)$ is a linear discount factor
that assigns higher importance to data points closer to $T$ in the sliding
window. Our method not only avoids storing and indexing the entire set of
representations, but also considers that, at any time step $T$,
$f_{\phi}(x_{i})$ that are computed closer to $T$ are more accurate. During
each training epoch, prototype simplification is performed for a small number
of $M$ times per epoch.

#### Comparison to Previous Works

Previous works in few-shot learning (Snell, Swersky, and Zemel 2017; Allen et
al. 2019) use an alternative way to ensure the efficiency of prototypes. They
compute a new prototype for each mixture component using the episode-end
cluster mean, whereas in our model fine-tuning scenario, constant re-
estimation of $\mathbf{p}_{k}$ will break the continuity of the model’s
learning, leading to poor convergence. In contrast, our approach carefully
considers the dynamically changing nature of example representation; global
information, the discount factor $\omega(i,T,\delta)$ also mitigates
overfitting a small batch.

#### Optimization & Extension

Dynamic Diversity Regularization We dynamically control the diversity among
the prototype embeddings by restricting the minimum pairwise distance among
$\mathbf{p}_{k}$’s to $\lambda$. As $P$ grows, $\lambda$ increases, enforcing
higher pairwise difference among prototypes so that PFit maintains a set of
meaningful prototypes out of $f_{\phi}(x_{i})$ that sufficiently adds to the
diversity of $P$ and avoids redundancy (Wu et al. 2022b) in the prototypes.

$\mathcal{L}_{div}=\sum_{j=1}^{K}\sum_{k=j+1}^{K}\max\left(0,\lambda-\left\|\mathbf{p}_{j}-\mathbf{p}_{k}\right\|_{2}\right)^{2}$
(10)

#### Extension to Regression

Our approach can be readily applied to regression tasks by partitioning the
range of $y_{i}$ into a number of $N_{reg}\in\mathbb{N}^{*}$ bins and sample
$n$ examples from each bin. Each prototype prediction $\mathbf{l}_{k}$ becomes
a real number computed as the averaged ground-truth $y_{i}$ in each bin. Upon
inference, we compute $\hat{y}_{i}$ as
$\hat{y}_{i}=\sum_{k}z_{i,k}\mathbf{l}_{k}$.

#### Optimization

We minimize cross-entropy loss for classification and mean squared error for
regression. The full objective $\mathcal{L}$ linearly combines
$\mathcal{L}_{0}$ and $\mathcal{L}_{div}$ using a hyperparameter $\rho_{d}$.

$\displaystyle\mathcal{L}_{0}$
$\displaystyle=\begin{cases}\frac{1}{N}\sum_{i=1}^{N}\sum_{k=1}^{K}-y_{i,k}\log(\hat{y}_{i,k})&\text{(classification)}\\\
\frac{1}{N}\sum_{i=1}^{N}(y_{i}-\hat{y}_{i})^{2}&\text{(regression)}\end{cases}$
$\displaystyle\mathcal{L}$
$\displaystyle=\mathcal{L}_{0}+\rho_{d}\mathcal{L}_{div}$

### Interpretability

There are 3 ways to interpret the prototype embeddings $\mathbf{p}_{k}$: 1)
jointly train a decoder that transforms $\mathbf{p}_{k}$ back to the input
space (Li et al. 2018); 2) project $\mathbf{p}_{k}$ onto the nearest sequence
in the input space (Ming et al. 2019); 3) project $\mathbf{p}_{k}$ onto
examples that are sufficiently close to the prototype within a threshold
$\tau$: $\\{x_{i}\mid\|\mathbf{p}_{k}-f_{\phi}(x_{i})\|_{2}<\tau\\}$.

## Experiment

Implementation Details We apply a batch size of 32 and use $n=8$ examples to
initialize each prototype. The sequence length is set to 128. We first conduct
a grid-search on $\alpha$ within $\\{1,0.5,0.1,0.05,0.01\\}$ , $\rho_{d}$ in
$\\{1e-4,1e-5,1e-6\\}$, and $\epsilon$ in $\\{1e-3,3e-3,1e-2\\}$ using a
subset of SST-2 with 1000 data points, and fix $\alpha=0.1$, $\rho_{d}=1e-5$,
and $\epsilon=1e-3$ to conduct all experiments without further tuning. We use
the Adam optimizer (Kingma and Ba 2015) without weight decay. For both PFit
and the baselines, we search the best learning rate from
$[1e-5,2e-5,3e-5,5e-5,1e-4]$. Other hyperparameters of the baselines are set
to their default values in their original papers. All experiments were run for
a maximum of 5 epochs with early stopping. For hardware usage, experiments are
run on servers with NVIDIA Tesla P100 (16GB GPU memory) or V100 (32GB GPU
memory).

### Robustness Across Varying Data Sizes

#### Experiment Setup

Our goal is to demonstrate the superior performances of PFit across a wide
range of data sizes, especially under low-resource scenarios. Thus, we
evaluate our model across a diverse spectrum of data sizes using 4
representative datasets from the General Language Understanding Evaluation
(GLUE) benchmark (Wang et al. 2019), including QNLI, MNLI-m, and MNLI-mm, 3
textual entailment datasets, as well as SST-2, a common benchmark for
sentiment analysis. The datasets are chosen following (Gunel et al. 2020) so
that both single sentence and sentence-pair classification datasets are
included. We report our results on MNLI-m/mm in Tab. 1 and SST-2/QNLI in Tab.
4. We validate the performances using a moderate-sized model BERT-Base (Devlin
et al. 2019) as our backbone model. We randomly sample 100 to 5000 examples
from the training set as our training set, taking into account the class
distribution of the full training set, and test our model on the full dev set.
We conduct experiments with 5 different seeds and report the accuracy and
standard deviation.

#### Baselines

We compare our PFit method against 6 baselines, including: 1) 4 non-parametric
networks built on top of the backbone language models, including DP-Means
(Kulis and Jordan 2012), ProtoNet (Snell, Swersky, and Zemel 2017), ProSeNet
(Ming et al. 2019), and IMP (Allen et al. 2019); 2) VIBERT, a network designed
for varying-resource fine-tuning (Belinkov, Henderson et al. 2021); 3) BSS, a
regularization approach to suppress untransferable spectral components and
improve fine-tuning (Wei, Xie, and Ma 2021) 4) the original LM.

MNLI-m | DPMeans | ProtoNet | ProSeNet | IMP | BSS | ViBERT | Raw | PFit | Impr. (b) %
---|---|---|---|---|---|---|---|---|---
100 | 38.6 $\pm$ 2.1 | 35.5 $\pm$ 0.6 | 36.3 $\pm$ 1.2 | 36.7 $\pm$ 0.7 | 36.5 $\pm$ 0.9 | 39.3 $\pm$ 1.1 | 33.4 $\pm$ 0.8 | 40.6 $\pm$ 2.2 | 3.2
200 | 39.1 $\pm$ 1.3 | 37.5 $\pm$ 1.6 | 38.6 $\pm$ 0.4 | 41.2 $\pm$ 1.3 | 40.0 $\pm$ 0.7 | 40.1 $\pm$ 0.4 | 35.3 $\pm$ 0.9 | 42.4 $\pm$ 1.9 | 2.8
500 | 41.4 $\pm$ 1.5 | 43.2 $\pm$ 0.5 | 44.7 $\pm$ 0.8 | 47.5 $\pm$ 0.8 | 50.1 $\pm$ 0.5 | 49.2 $\pm$ 0.7 | 38.5 $\pm$ 0.8 | 52.9 $\pm$ 1.8 | 5.6
1000 | 53.0 $\pm$ 1.0 | 50.5 $\pm$ 0.3 | 52.2 $\pm$ 0.4 | 55.3 $\pm$ 0.4 | 57.4 $\pm$ 0.4 | 57.1 $\pm$ 0.3 | 49.0 $\pm$ 0.7 | 58.5 $\pm$ 1.0 | 1.9
2000 | 62.5 $\pm$ 0.7 | 59.4 $\pm$ 0.7 | 59.0 $\pm$ 0.2 | 66.0 $\pm$ 0.3 | 65.6 $\pm$ 0.5 | 60.6 $\pm$ 0.3 | 59.6 $\pm$ 0.3 | 67.0 $\pm$ 0.7 | 1.5
5000 | 67.8 $\pm$ 0.5 | 67.4 $\pm$ 0.4 | 66.9 $\pm$ 0.1 | 71.1 $\pm$ 0.2 | 72.0 $\pm$ 0.1 | 71.4 $\pm$ 0.3 | 66.3 $\pm$ 0.1 | 72.3 $\pm$ 0.6 | 0.5
MNLI-mm |  |  |  |  |  |  |  |  |
100 | 38.8 $\pm$ 0.7 | 36.4 $\pm$ 0.4 | 36.8 $\pm$ 1.2 | 37.2 $\pm$ 1.1 | 35.2 $\pm$ 0.7 | 36.8 $\pm$ 1.8 | 34.1 $\pm$ 0.7 | 39.6 $\pm$ 2.1 | 1.8
200 | 39.5 $\pm$ 0.5 | 39.4 $\pm$ 1.2 | 38.6 $\pm$ 1.2 | 41.0 $\pm$ 0.2 | 41.5 $\pm$ 0.7 | 39.3 $\pm$ 0.8 | 35.7 $\pm$ 0.2 | 43.2 $\pm$ 1.8 | 4.0
500 | 46.4 $\pm$ 0.4 | 47.6 $\pm$ 1.1 | 40.7 $\pm$ 1.3 | 49.0 $\pm$ 2.2 | 49.5 $\pm$ 2.0 | 46.4 $\pm$ 1.4 | 45.9 $\pm$ 2.1 | 54.9 $\pm$ 1.0 | 11.1
1000 | 53.6 $\pm$ 0.6 | 55.4 $\pm$ 0.3 | 52.2 $\pm$ 0.4 | 54.8 $\pm$ 0.3 | 56.1 $\pm$ 0.2 | 48.6 $\pm$ 0.4 | 50.1 $\pm$ 0.3 | 61.5 $\pm$ 0.6 | 9.6
2000 | 64.3 $\pm$ 0.8 | 62.4 $\pm$ 0.3 | 61.0 $\pm$ 0.3 | 67.1 $\pm$ 0.2 | 64.5 $\pm$ 0.5 | 60.9 $\pm$ 0.3 | 58.6 $\pm$ 0.2 | 67.8 $\pm$ 0.2 | 1.1
5000 | 69.8 $\pm$ 0.3 | 70.0 $\pm$ 0.1 | 68.9 $\pm$ 0.2 | 71.5 $\pm$ 0.4 | 71.7 $\pm$ 0.3 | 68.3 $\pm$ 0.2 | 69.2 $\pm$ 0.3 | 71.9 $\pm$ 0.1 | 0.4
Table 1: Results on MNLI-m/mm with varying data sizes for BERT-Base. “Raw”
indicates the original language model. The leftmost column shows the number of
examples used in training. Impr.(b) indicates the improvement over the best
baseline

#### Model Performances

The definition of low-resource settings varies across data sets (Belinkov,
Henderson et al. 2021; Gao et al. 2018). We follow existing literature (Jin et
al. 2020; Belinkov, Henderson et al. 2021) to define low-resource settings as
datasets with $\leq$ 5000 data points. Compared with the baselines, our PFit
model consistently achieves the best performance among all datasets and data
sizes. For MNLI-m/mm, our method leads to a maximum of 5.6 and 11.1 percent
improvement (Tab. 1) compared to the best baseline models. For QNLI/SST-2, our
method leads to improvement of 5.1 and 3.8 percent (Tab. 4).

We also observe that the most significant improvement (Tab. 4) occurs with
smaller datasets (100-200 examples) on SST-2, compared with medium-sized
datasets (500-2000 examples) on QNLI and MNLI. This is potentially because
sentiment analysis has a larger reliance on lower-level phrasal information
and surface features, which are encoded in the pretrained word representations
(Jawahar, Sagot, and Seddah 2019) and can be directly leveraged in the
construction of prototypes. Our proposed mixture prototype initialization can
effectively leverage the rich phrasal and sentiment clues and assist PFit
towards achieving a globally optimal solution. For more complex tasks such as
textual entailment, larger data sizes are needed for modeling higher-level
complex semantic features and class relationships. For small-scale datasets,
models with simpler inductive biases like ProtoNet (Snell, Swersky, and Zemel
2017) may achieve slightly worse but more stable performances with less
parameters. On larger datasets, prototypical models with flexible capacity
(Allen et al. 2019; Kulis and Jordan 2012) generally outperform methods with
fixed capacity (Snell, Swersky, and Zemel 2017; Ming et al. 2019).

Figure 2: Results of variations of _PFit_ model on SST-2 (Left) and QNLI (Right) with 1000 data points. Runtime | SST-2 | QNLI | MNLI
---|---|---|---
IMP | 523 | 816 | 3139
raw | 18 | 28 | 105
PFit | 18 | 29 | 109
Table 2: Comparison of per-epoch runtime (in minutes) among the original
model, IMP (Allen et al. 2019), and PFit with batch size of 16.

SST-2 | DPMeans | ProtoNet | ProSeNet | IMP | BSS | ViBERT | Raw | PFit | Impr. (b) %
---|---|---|---|---|---|---|---|---|---
100 | 69.0 $\pm$ 0.7 | 74.9 $\pm$ 1.2 | 72.8 $\pm$ 0.9 | 74.7 $\pm$ 0.5 | 66.4 $\pm$ 0.7 | 67.5 $\pm$ 1.1 | 64.7 $\pm$ 0.9 | 78.7 $\pm$ 2.2 | 5.1
200 | 69.6 $\pm$ 2.5 | 72.9 $\pm$ 0.6 | 75.5 $\pm$ 1.2 | 80.0 $\pm$ 1.3 | 68.6 $\pm$ 0.4 | 68.7 $\pm$ 0.6 | 67.1 $\pm$ 1.2 | 81.9 $\pm$ 1.1 | 2.4
500 | 73.9 $\pm$ 0.6 | 80.7 $\pm$ 0.9 | 80.6 $\pm$ 0.6 | 82.3 $\pm$ 0.6 | 69.8 $\pm$ 0.7 | 74.4 $\pm$ 0.1 | 77.7 $\pm$ 0.6 | 84.6 $\pm$ 0.9 | 2.8
1000 | 84.6 $\pm$ 0.6 | 84.8$\pm$ 0.4 | 85.2 $\pm$ 0.6 | 84.8 $\pm$ 0.7 | 84.3 $\pm$ 0.6 | 85.6 $\pm$ 0.3 | 86.0 $\pm$ 0.3 | 86.4 $\pm$ 0.6 | 1.0
2000 | 87.2 $\pm$ 0.3 | 85.2 $\pm$ 0.4 | 86.8 $\pm$ 0.5 | 87.5 $\pm$ 0.4 | 87.9 $\pm$ 0.4 | 87.4 $\pm$ 0.1 | 87.9 $\pm$ 0.6 | 88.5 $\pm$ 0.2 | 0.6
5000 | 88.3 $\pm$ 0.5 | 87.0 $\pm$ 0.3 | 88.2 $\pm$ 0.1 | 89.6 $\pm$ 0.2 | 89.4 $\pm$ 0.1 | 89.1 $\pm$ 0.3 | 89.6 $\pm$ 0.2 | 90.7 $\pm$ 0.2 | 1.2
QNLI |  |  |  |  |  |  |  |  |
100 | 56.0 $\pm$ 2.7 | 64.8 $\pm$ 0.4 | 63.2 $\pm$ 1.7 | 61.2 $\pm$ 2.0 | 59.0 $\pm$ 1.3 | 60.3 $\pm$ 1.2 | 56.4 $\pm$ 1.4 | 67.0 $\pm$ 2.4 | 3.4
200 | 67.2 $\pm$ 0.4 | 67.4 $\pm$ 1.3 | 69.0 $\pm$ 1.5 | 71.0 $\pm$ 1.2 | 69.2 $\pm$ 0.5 | 69.2 $\pm$ 1.3 | 62.1 $\pm$ 1.6 | 73.7 $\pm$ 1.0 | 3.7
500 | 71.1 $\pm$ 0.2 | 76.6 $\pm$ 0.5 | 77.0 $\pm$ 1.1 | 77.0 $\pm$ 0.6 | 75.8 $\pm$ 0.5 | 72.7 $\pm$ 0.1 | 68.4 $\pm$ 0.2 | 78.1 $\pm$ 0.3 | 1.3
1000 | 78.6 $\pm$ 0.1 | 80.2 $\pm$ 0.4 | 78.3 $\pm$ 0.5 | 78.0 $\pm$ 0.2 | 77.6 $\pm$ 0.3 | 75.9 $\pm$ 0.2 | 73.3 $\pm$ 0.3 | 81.3 $\pm$ 0.2 | 3.8
2000 | 81.6 $\pm$ 0.2 | 80.7 $\pm$ 0.1 | 81.4 $\pm$ 0.1 | 81.3 $\pm$ 0.2 | 82.1 $\pm$ 0.2 | 80.9 $\pm$ 0.2 | 77.6 $\pm$ 0.1 | 82.6 $\pm$ 0.3 | 0.6
5000 | 82.7 $\pm$ 0.1 | 82.9 $\pm$ 0.2 | 84.3 $\pm$ 0.1 | 84.3 $\pm$ 0.3 | 84.5 $\pm$ 0.1 | 84.4 $\pm$ 0.2 | 82.5 $\pm$ 0.1 | 84.9 $\pm$ 0.3 | 0.4

Table 3: Results on QNLI/SST-2 with varying data sizes for BERT-Base.

Prototype A | Prototype B | Prototype C
---|---|---
| I had to look away - this
---
was god awful.
It’s of the quality of a lesser harrison ford movie | Bad.
| I have to say the star
---
and director are the
big problems here.
| I can take infantile humor … but this is the sort
---
of infantile that makes you wonder about
changing the director and …
Very bad.
| Eventually, every idea in
---
this film is flushed down
the latrine of heroism.
|  I am sorry that i was unable to get the full
---
brunt of the comedy .
Yes, dull …

Table 4: The top 3 closest examples of each learned prototype on SST-2. The
closest examples all have ground-truth labels of “negative.” However, each
prototype represents a group of semantically similar negative samples.

### Complexity & Runtime

The time complexity for PFit is $O(N|P_{max}|+NM)$. This consists of
$O(N|P_{max}|)$ for prototype creation and $O(NM)$ for prototype
simplification. While prototypical methods like IMP can achieve satisfying
performances, they may incur expensive computational costs. IMP takes
$O(N^{2}|P_{max}|)$ due to recomputing a collection of prototype vectors at
the end of each training step. For most data sizes, IMP (Allen et al. 2019)
outperforms other baselines and sometimes achieves comparable results as PFit.
However, IMP is computationally inefficient for a feature-learning setting as
it requires constant re-estimation of the prototypes. As shown in Tab. 2,
fine-tuning IMP requires 523 and 816 minutes per epoch on SST-2 and QNLI,
respectively. In contrast, PFit takes 18 and 29 minutes. Compared with the raw
model, PFit achieves significant improvement over the original language model
with only a marginal runtime increase.

### Ablation Study

To demonstrate the effectiveness of each major component, we evaluate 4
variations of PFit: 1) PF-I removes mixture prototype initialization and
randomly initializes $\mathbf{p}_{k}$; 2) PF-S disables _adaptive prototype
simplification_ ; 3) PF-D applies no diversity regularization
$\mathcal{L}_{div}$; 4) PF-F uses a fixed threshold for $\mathcal{L}_{div}$.
We observe that mixture prototype initialization benefits the training under
low-resource settings. The performance drops most significantly when we
disabled _adaptive prototype simplification_. We conjecture that some
prototypes were created from a minority of out-of-distribution samples, which
may overfit older training data but fail to generalize to new data.

Figure 3: Results for the original _PFit_ model and _PFit_ with skip
connection (PFit-SC).

### Interpreting the Prototypes

Besides performance improvements, prototypes can bring the extra advantage of
explainability (Lee et al. 2022; Gao et al. 2021; Chen et al. 2021). To
interpret the prototype vectors, we project each prototype to its closest 10
examples. We observe that 1) prototypes manifest inter-class distinction as
the classes are discriminable from the prototypes; and 2) prototypes
demonstrate intra-class distinction (Jin et al. 2022a) as there are clustering
emergent within the prototypes.

#### Inter-class Distinctions

If we project each prototype onto its nearest examples, each prototype shows
strong polarity towards one specific class. Here, for simplicity, we refer to
prototypes that predict positive class as “positive prototypes” and those
predicting negative as “negative prototypes”. On SST-2, the average percentage
of positive examples is 91% for positive prototypes, and that of negative
examples for negative prototypes is 87%.

#### Intra-class Distinctions

Tab. 4 is an example for the binary sentiment classification dataset SST-2.
The top 3 closest examples to each prototype are shown. The closest examples
all have ground-truth labels of “negative” However, each prototype represents
a group of negative samples that are semantically similar. Examples of
prototype A generally express stronger emotions (“awful”, “big problem”,
“latrine”). Examples of B express weaker emotions. Examples of C mainly focus
on succinct negative expressions. Methods such as ProtoNet (Snell, Swersky,
and Zemel 2017) only use one prototype for each class, which may not
sufficiently characterize such intra-class distinctions.

We experimented with connecting non-contextualized BERT (Devlin et al. 2019)
embeddings with contextualized representations using a residual network,
leading to performance improvements on SST-2 with 200 and 1000 examples, and
decreases in other settings. We believe that merging the contextualized
embeddings with non-contextualized signals without sacrificing performances
can potentially increase the explainability of our prototypical framework. We
will explore this method comprehensively in future works.

## Conclusion

We propose Prototypical Fine-tuning (PFit), a prototypical framework for
effectively fine-tuning pretrained language models. Extensive experiments
across various datasets show that our work offers significant performance
improvements for language models under varying data sizes, especially low
resource settings.

## References

  * Ackerman and Dasgupta (2014) Ackerman, M.; and Dasgupta, S. 2014.  Incremental clustering: The case for extra clusters.  In _NIPS_.
  * Allen et al. (2019) Allen, K.; Shelhamer, E.; Shin, H.; and Tenenbaum, J. 2019.  Infinite mixture prototypes for few-shot learning.  In _ICML_ , 232–241. PMLR.
  * Artetxe et al. (2018) Artetxe, M.; Labaka, G.; Agirre, E.; and Cho, K. 2018.  Unsupervised neural machine translation.  In _ICLR_.
  * Baxter (2000) Baxter, J. 2000.  A model of inductive bias learning.  _JAIR_ , 12: 149–198.
  * Belinkov, Henderson et al. (2021) Belinkov, Y.; Henderson, J.; et al. 2021.  Variational Information Bottleneck for Effective Low-Resource Fine-Tuning.  In _ICLR_.
  * Brown et al. (2020) Brown, T.; Mann, B.; Ryder, N.; Subbiah, M.; Kaplan, J. D.; Dhariwal, P.; Neelakantan, A.; Shyam, P.; Sastry, G.; Askell, A.; et al. 2020.  Language models are few-shot learners.  In _NIPS_.
  * Chen et al. (2019) Chen, C.; Li, O.; Tao, D.; Barnett, A.; Rudin, C.; and Su, J. K. 2019.  This looks like that: deep learning for interpretable image recognition.  In _NIPS_ , volume 32.
  * Chen et al. (2021) Chen, Z.; Wang, X.; Xie, X.; Parsana, M.; Soni, A.; Ao, X.; and Chen, E. 2021.  Towards explainable conversational recommendation.  In _IJCAI_ , 2994–3000.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _NAACL_ , 4171–4186.
  * Fadaee, Bisazza, and Monz (2017) Fadaee, M.; Bisazza, A.; and Monz, C. 2017.  Data Augmentation for Low-Resource Neural Machine Translation.  In _ACL_ , 567–573.
  * Feldman (2020) Feldman, V. 2020.  Does learning require memorization? a short tale about a long tail.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , 954–959.
  * Gao et al. (2018) Gao, H.; Shou, Z.; Zareian, A.; Zhang, H.; and Chang, S.-F. 2018.  Low-shot learning via covariance-preserving adversarial augmentation networks.  In _NIPS_ , volume 31.
  * Gao et al. (2021) Gao, J.; Wang, X.; Wang, Y.; Yan, Y.; and Xie, X. 2021.  Learning Groupwise Explanations for Black-Box Models.  In _IJCAI_ , 2396–2402.
  * Gao et al. (2019) Gao, T.; Han, X.; Liu, Z.; and Sun, M. 2019.  Hybrid attention-based prototypical networks for noisy few-shot relation classification.  In _AAAI_ , 6407–6414.
  * Goldberger et al. (2004) Goldberger, J.; Hinton, G. E.; Roweis, S.; and Salakhutdinov, R. R. 2004.  Neighbourhood components analysis.  In _NIPS_.
  * Guan et al. (2019) Guan, C.; Wang, X.; Zhang, Q.; Chen, R.; He, D.; and Xie, X. 2019.  Towards a deep and unified understanding of deep neural models in nlp.  In _International conference on machine learning_ , 2454–2463. PMLR.
  * Gunel et al. (2020) Gunel, B.; Du, J.; Conneau, A.; and Stoyanov, V. 2020.  Supervised Contrastive Learning for Pre-trained Language Model Fine-tuning.  In _ICLR_.
  * Hao et al. (2020) Hao, Y.; Dong, L.; Wei, F.; and Xu, K. 2020.  Investigating learning dynamics of BERT fine-tuning.  In _Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing_ , 87–92.
  * Hjort et al. (2010) Hjort, N. L.; Holmes, C.; Müller, P.; and Walker, S. G. 2010.  _Bayesian nonparametrics_ , volume 28.  Cambridge University Press.
  * Jawahar, Sagot, and Seddah (2019) Jawahar, G.; Sagot, B.; and Seddah, D. 2019.  What does BERT learn about the structure of language?  In _ACL_.
  * Jin et al. (2020) Jin, S.; Wiseman, S.; Stratos, K.; and Livescu, K. 2020.  Discrete Latent Variable Representations for Low-Resource Text Classification.  In _ACL_ , 4831–4842.
  * Jin et al. (2022a) Jin, Y.; Bai, Y.; Zhu, Y.; Sun, Y.; and Wang, W. 2022a.  Code Recommendation for Open Source Software Developers.  _arXiv preprint arXiv:2210.08332_.
  * Jin et al. (2022b) Jin, Y.; Wang, X.; Yang, R.; Sun, Y.; Wang, W.; Liao, H.; and Xie, X. 2022b.  Towards Fine-Grained Reasoning for Fake News Detection.  In _AAAI_.
  * Kim, Rudin, and Shah (2014) Kim, B.; Rudin, C.; and Shah, J. A. 2014.  The bayesian case model: A generative approach for case-based reasoning and prototype classification.  _NIPS_ , 27.
  * Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015.  Adam: A Method for Stochastic Optimization.  In _ICLR_.
  * Kolodner (1992) Kolodner, J. L. 1992.  An introduction to case-based reasoning.  _Artificial intelligence review_ , 6(1): 3–34.
  * Kulis and Jordan (2012) Kulis, B.; and Jordan, M. I. 2012.  Revisiting k-means: new algorithms via Bayesian nonparametrics.  In _ICML_ , 1131–1138.
  * Lee et al. (2022) Lee, S.; Wang, X.; Han, S.; Yi, X.; Xie, X.; and Cha, M. 2022.  Self-explaining deep models with logic rule reasoning.  In _36th Annual Conference on Neural Information Processing Systems (NeurIPS 2022)_. NIPS.
  * Li et al. (2018) Li, O.; Liu, H.; Chen, C.; and Rudin, C. 2018.  Deep learning for case-based reasoning through prototypes: A neural network that explains its predictions.  In _AAAI_.
  * McCoy, Pavlick, and Linzen (2019) McCoy, T.; Pavlick, E.; and Linzen, T. 2019.  Right for the Wrong Reasons: Diagnosing Syntactic Heuristics in Natural Language Inference.  In _ACL_ , 3428–3448.
  * Mensink et al. (2013) Mensink, T.; Verbeek, J.; Perronnin, F.; and Csurka, G. 2013.  Distance-based image classification: Generalizing to new classes at near-zero cost.  _PAMI_ , 35(11): 2624–2637.
  * Mettes, van der Pol, and Snoek (2019) Mettes, P.; van der Pol, E.; and Snoek, C. 2019.  Hyperspherical prototype networks.  _NIPS_ , 32.
  * Ming et al. (2019) Ming, Y.; Xu, P.; Qu, H.; and Ren, L. 2019.  Interpretable and steerable sequence learning via prototypes.  In _KDD_ , 903–913.
  * Oh Song et al. (2016) Oh Song, H.; Xiang, Y.; Jegelka, S.; and Savarese, S. 2016.  Deep metric learning via lifted structured feature embedding.  In _CVPR_ , 4004–4012.
  * Oreshkin, Rodríguez López, and Lacoste (2018) Oreshkin, B.; Rodríguez López, P.; and Lacoste, A. 2018.  Tadam: Task dependent adaptive metric for improved few-shot learning.  _NIPS_ , 31.
  * Perez, Kiela, and Cho (2021) Perez, E.; Kiela, D.; and Cho, K. 2021.  True few-shot learning with language models.  _NIPS_ , 34.
  * Rasmussen (1999) Rasmussen, C. 1999.  The infinite Gaussian mixture model.  _NIPS_ , 12.
  * Ren et al. (2018) Ren, M.; Triantafillou, E.; Ravi, S.; Snell, J.; Swersky, K.; Tenenbaum, J. B.; Larochelle, H.; and Zemel, R. S. 2018.  Meta-Learning for Semi-Supervised Few-Shot Classification.  In _ICLR_.
  * Salamon and Bello (2017) Salamon, J.; and Bello, J. P. 2017.  Deep convolutional neural networks and data augmentation for environmental sound classification.  _IEEE Signal processing letters_ , 24(3): 279–283.
  * Shao et al. (2017) Shao, J.; Huang, F.; Yang, Q.; and Luo, G. 2017.  Robust prototype-based learning on data streams.  _TKDE_ , 30(5): 978–991.
  * Snell, Swersky, and Zemel (2017) Snell, J.; Swersky, K.; and Zemel, R. 2017.  Prototypical networks for few-shot learning.  _NIPS_ , 30.
  * Tenney, Das, and Pavlick (2019) Tenney, I.; Das, D.; and Pavlick, E. 2019.  BERT Rediscovers the Classical NLP Pipeline.  In _ACL_ , 4593–4601.
  * Tsimpoukelli et al. (2021) Tsimpoukelli, M.; Menick, J. L.; Cabi, S.; Eslami, S.; Vinyals, O.; and Hill, F. 2021.  Multimodal few-shot learning with frozen language models.  _NIPS_ , 34: 200–212.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  In _NIPS_.
  * Vinyals et al. (2016) Vinyals, O.; Blundell, C.; Lillicrap, T.; Wierstra, D.; et al. 2016.  Matching networks for one shot learning.  In _NIPS_.
  * Wang et al. (2019) Wang, A.; Singh, A.; Michael, J.; Hill, F.; Levy, O.; and Bowman, S. R. 2019.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _ICLR_.
  * Wang and Blei (2009) Wang, C.; and Blei, D. 2009.  Variational inference for the nested Chinese restaurant process.  _NIPS_ , 22.
  * Wang et al. (2021) Wang, J.; Wang, K.-C.; Rudzicz, F.; and Brudno, M. 2021.  Grad2Task: Improved Few-shot Text Classification Using Gradients for Task Representation.  _NIPS_ , 34.
  * Wei, Xie, and Ma (2021) Wei, C.; Xie, S. M.; and Ma, T. 2021.  Why do pretrained language models help in downstream tasks? an analysis of head and prompt tuning.  _NIPS_ , 34: 16158–16170.
  * Wu et al. (2022a) Wu, C.; Wu, F.; Qi, T.; Huang, Y.; and Xie, X. 2022a.  NoisyTune: A Little Noise Can Help You Finetune Pretrained Language Models Better.  _arXiv preprint arXiv:2202.12024_.
  * Wu et al. (2022b) Wu, J.; Xu, W.; Liu, Q.; Wu, S.; and Wang, L. 2022b.  Adversarial Contrastive Learning for Evidence-aware Fake News Detection with Graph Neural Networks.  _arXiv preprint arXiv:2210.05498_.
  * Yang et al. (2018) Yang, H.-M.; Zhang, X.-Y.; Yin, F.; and Liu, C.-L. 2018.  Robust classification with convolutional prototype learning.  In _CVPR_ , 3474–3482.
  * Yang et al. (2022a) Yang, J.; Liu, Z.; Xiao, S.; Lian, J.; Wu, L.; Lian, D.; Sun, G.; and Xie, X. 2022a.  A Mutually Reinforced Framework for Pretrained Sentence Embeddings.  _arXiv preprint arXiv:2202.13802_.
  * Yang et al. (2022b) Yang, L.; Zhang, S.; Qin, L.; Li, Y.; Wang, Y.; Liu, H.; Wang, J.; Xie, X.; and Zhang, Y. 2022b.  GLUE-X: Evaluating Natural Language Understanding Models from an Out-of-distribution Generalization Perspective.  _arXiv preprint arXiv:2211.08073_.
  * Yang et al. (2022c) Yang, R.; Wang, X.; Jin, Y.; Li, C.; Lian, J.; and Xie, X. 2022c.  Reinforcement Subgraph Reasoning for Fake News Detection.  In _KDD_.
  * Zaken, Ravfogel, and Goldberg (2021) Zaken, E. B.; Ravfogel, S.; and Goldberg, Y. 2021.  Bitfit: Simple parameter-efficient fine-tuning for transformer-based masked language-models.  _arXiv preprint arXiv:2106.10199_.