# (Four) Dual Plaquette 3D Ising Models

Desmond A. Johnston  School of Mathematical and Computer Sciences, Heriot-Watt
University, Riccarton, Edinburgh, EH14 4AS, Scotland  R. P. K. C. M.
Ranasinghe  Department of Mathematics, University of Sri Jayewardenepura,
Gangodawila, Nugegoda 10250, Sri Lanka.

###### Abstract

A characteristic feature of the $3d$ plaquette Ising model is its planar
subsystem symmetry. The quantum version of this model has been shown to be
related via a duality to the X-Cube model, which has been paradigmatic in the
new and rapidly developing field of fractons. The relation between the $3d$
plaquette Ising and the X-Cube model is similar to that between the $2d$
quantum transverse spin Ising model and the Toric Code. Gauging the global
symmetry in the case of the $2d$ Ising model and considering the gauge
invariant sector of the high temperature phase leads to the Toric Code,
whereas gauging the subsystem symmetry of the $3d$ quantum transverse spin
plaquette Ising model leads to the X-Cube model. A non-standard dual
formulation of the $3d$ plaquette Ising model which utilises three flavours of
spins has recently been discussed in the context of dualising the fracton-free
sector of the X-Cube model. In this paper we investigate the classical spin
version of this non-standard dual Hamiltonian and discuss its properties in
relation to the more familiar Ashkin–Teller-like dual and further related dual
formulations involving both link and vertex spins and non-Ising spins.

##  1 Introduction

The Kramers–Wannier dual [1] of the classical Ising Hamiltonian with nearest
neighbour $\langle ij\rangle$ couplings on a $3d$ cubic lattice

$H_{Ising}=-\sum_{\langle ij\rangle}\sigma_{i}\sigma_{j}$ (1)

is the $3d$ Ising gauge theory

$H_{Gauge}=-\sum_{\Box}UUUU$ (2)

where the sum runs over plaquettes $\Box$ and the gauge spins $U$ live on the
edges of the plaquettes. The coupling $\beta$ in the partition function
$Z(\beta)=\sum_{\\{\sigma\\}}\exp(-\beta H_{Ising})$ and its dual $\beta^{*}$
in $Z(\beta^{*})=\sum_{\\{U\\}}\exp(-\beta^{*}H_{Gauge})$ are related by
$\beta^{*}=-\frac{1}{2}\log[\tanh(\beta)]$. We use un-superscripted variables,
e.g., $U,\sigma_{i},\tau_{i},\mu_{i}$, to denote spins in classical
Hamiltonians and superscripted variables, e.g.,
$\sigma^{x,z}_{i},\tau^{x,z}_{i},\mu^{x,z}_{i}$, to denote the Pauli matrices
appearing in quantum Hamiltonians. The positional subscript indices
$i,j,k\ldots$ are occasionally omitted for brevity.

In this paper we will investigate the relation between four (apparently)
different formulations of the dual to the $3d$ plaquette Ising model, which
has also been dubbed the gonihedric Ising model [2, 3, 4, 5]

$H_{\kappa=0}=-\sum_{\Box}\sigma_{i}\sigma_{j}\sigma_{k}\sigma_{l}\;.$ (3)

This, like the $3d$ Ising gauge theory, has a plaquette $\Box$ interaction but
the spins now reside at the vertices of a $3d$ cubic lattice rather than on
its edges. The subscript $\kappa=0$ appears because this plaquette Hamiltonian
is a particular case of a one-parameter family of gonihedric Hamiltonians

$H_{gonihedric}=-4\kappa\sum_{\langle
ij\rangle}\sigma_{i}\sigma_{j}+\kappa\sum_{\langle\langle
ij\rangle\rangle}\sigma_{i}\sigma_{j}-(1-\kappa)\sum_{\Box}\sigma_{i}\sigma_{j}\sigma_{k}\sigma_{l}\;.$
(4)

defined by Savvidy and Wegner [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], where
the $\langle\langle ij\rangle\rangle$ are next-to-nearest neighbour spin
interactions. The weights of spin cluster boundaries in this Hamiltonian are
tuned to mimic a gas of worldsheets arising from a gonihedric string action.
When the gonihedric string worldsheets are discretized using triangulations,
their action may be written as

$S={1\over 2}\sum_{\langle
ij\rangle}|\vec{X}_{i}-\vec{X}_{j}|\;\theta(\alpha_{ij}),$ (5)

where $\theta(\alpha_{ij})=|\pi-\alpha_{ij}|$, $\alpha_{ij}$ is the dihedral
angle between the neighbouring triangles with a common edge $\langle
ij\rangle$ and $|\vec{X}_{i}-\vec{X}_{j}|$ are the lengths of the triangle
edges. The $\vec{X}_{i}$ give the embeddings of the vertices $i$ of the
worldsheet discretization in the ambient spacetime.

The word gonihedric was originally coined to reflect the properties of this
action, which weights edge lengths between non-coplanar triangles rather than
the triangle areas, which is the case with a discretization of the standard
Nambu–Goto/Polyakov string action. It combines the Greek words gonia for
angle, referring to the dihedral angle, and hedra for base or face, referring
to the adjacent triangles. $H_{gonihedric}$ is an appropriate cubic lattice
discretization for such an action because it too assigns zero weight to the
areas of spin cluster boundaries, weighting only edges and intersections [17].
This gives $H_{gonihedric}$ very different properties to $H_{Ising}$ where
only the areas of spin cluster boundaries are weighted.

The $3d$ plaquette Ising action $H_{\kappa=0}$ has been shown to possess an
exponentially (but sub-extensively) degenerate low-temperature phase and a
first order phase transition as well as interesting, possibly glassy,
dynamical properties [18, 19, 20, 21, 22, 23, 24]. A characteristic feature is
that it displays a planar subsystem symmetry in which planes of spins may be
flipped at zero energy cost, accounting for the degeneracy of the low
temperature phase. This can be seen by looking at single cubes with a flipped
face as in Figure 1 and using these to tile the lattice. Since multiple faces
can be flipped on the cube, intersecting planes of flipped spins are also
possible.

Figure 1: Flipping the value of the Ising spins on a face of a single cube in
the $3d$ plaquette Ising Hamiltonian $H_{\kappa=0}$ does not change its
contribution to the energy. The first cube configuration is the ferromagnetic
state with all spins $+$. The spins at the corners of the dark shaded faces on
the other three are $-$, the others $+$. All four of the single cube
configurations shown have the same energy.

The degeneracy affects the finite size scaling behaviour at the first order
transition [25, 26, 27, 28, 29], changing the universal $1/L^{3}$ finite size
scaling shift in estimates of a first order transition point on an $L^{3}$
lattice (with periodic boundary conditions) [30, 31] to $1/L^{2}$. For non-
zero $\kappa$ the planar subsystem symmetry appears to be broken at finite
temperature [32, 33] and the transition becomes second order. The
Kramers–Wannier dual to $H_{\kappa=0}$ takes the form of an anisotropic
Ashkin–Teller model [34]. It still possesses a planar subsystem symmetry and
degenerate low temperature phase, so the modified finite size scaling at the
first order transition is observed there also [25, 26, 27, 28, 29].

The subsystem symmetry in the quantum spin version of the $3d$ plaquette Ising
model has recently been shown to be closely linked to the properties of the
X-Cube model [35], which has become a paradigmatic model for the new and
rapidly developing field of fractons, which are quasiparticles with restricted
mobility in isolation. Some recent reviews of what is now a burgeoning fracton
literature can be found in [36, 37]. To see the role played by the subsystem
symmetry in constructing the X-Cube model, first consider gauging the global
$\mathbb{Z}_{2}$ symmetry in the case of the $2d$ quantum transverse spin
Ising model

$H=-\beta\sum_{\langle
ij\rangle}\sigma_{i}^{z}\sigma_{j}^{z}-h\sum_{i}\sigma_{i}^{x}\;.$ (6)

This can be done by introducing $\tau^{z}$ on the links and an additional
plaquette flux term to endow the link spins with dynamics, which gives a
gauge-invariant Ising (or $\mathbb{Z}_{2}$ gauge–Higgs [38, 39, 40]) model

$\displaystyle H$ $\displaystyle=$ $\displaystyle-\beta\sum_{\langle
ij\rangle}\sigma_{i}^{z}\tau^{z}\sigma_{j}^{z}-h\sum_{i}\sigma_{i}^{x}-\beta_{p}\sum_{\Box}\tau^{z}\tau^{z}\tau^{z}\tau^{z}$
(7)

where we have dropped the link indices on the $\tau^{z}$ for conciseness. The
gauge-invariant sector of the high temperature phase, $\beta\to 0$, of this
model, where $\sigma_{i}^{x}\prod_{k\in+,i}\tau_{k}^{x}=1$ and $k$ labels the
four edges ($+$) incident to vertex $i$, gives Kitaev’s Toric Code model [41,
42]

$\displaystyle H$ $\displaystyle=$
$\displaystyle-h\sum_{i}A_{i}-\beta_{p}\sum_{\Box}B_{\Box}\;.$ (8)

We use the gauge invariance to trade $\sigma_{i}^{x}$ for
$\prod_{k\in+,i}\tau_{k}^{x}$, leaving the mutually commuting terms

$A_{i}=\prod_{k\in+,i}\tau_{k}^{x},\;\;\;\;B_{\Box}=\prod_{i\in\Box}\tau_{i}^{z}\;.$
(9)

and customarily set $h=\beta_{p}=1$. The Toric code displays topological order
and has anyonic quasiparticle excitations.

On the other hand, gauging the subsystem symmetry of the $3d$ plaquette Ising
model in a similar manner leads to the X-Cube model [35]. In this case, when
we start with the quantum transverse spin $3d$ plaquette Ising model
Hamiltonian

$H=-\beta\sum_{\Box}\sigma_{i}^{z}\sigma_{j}^{z}\sigma_{k}^{z}\sigma_{l}^{z}-h\sum_{i}\sigma_{i}^{x}$
(10)

gauging the $\mathbb{Z}_{2}$ subsystem symmetry requires inserting a
$\tau^{z}$ which lives on the plaquettes

$\displaystyle H$ $\displaystyle=$
$\displaystyle-\beta\sum_{\Box}\tau^{z}\sigma_{i}^{z}\sigma_{j}^{z}\sigma_{k}^{z}\sigma_{l}^{z}-h\sum_{i}\sigma_{i}^{x}\;+\;\ldots$
(11)

The equivalent of the plaquette flux term in the Toric Code derivation is now
a set of three “X” terms as shown in Figure 2, one in each lattice plane
$B^{xy,yz,xz}_{i}=\prod_{j\in+,i}\tau_{j}^{z}$. If we again consider the gauge
invariant sector $\;\;\sigma_{i}^{x}\prod_{k\in\Box,i}\tau_{k}^{x}=1$, where
the $\tau_{k}^{x}$ live on the twelve incident plaquettes impacted by flipping
the single central spin at site $i$, the high temperature limit $\beta\to 0$
produces the X-Cube Hamiltonian

$\displaystyle H=-\sum
A-\sum_{i}B_{i}^{xy}-\sum_{i}B_{i}^{yz}-\sum_{i}B_{i}^{xz}$

where it is simpler to think of the $\tau^{x},\tau^{z}$’s residing on the
links of the dual lattice. The $A$ term is a product of all the $\tau^{x}$
around a cube and the $B$ terms are the three “crosses” of $\tau^{z}$ ’s shown
in Figure 2.

Figure 2: The terms contributing to the X-Cube Hamiltonian. The cube $A$ term
is a product of the twelve $\tau^{x}$ spins on the edges of the cube and the
three $B$ “X” terms composed of $\tau^{z}$ spins lie in each of the three
lattice planes as shown on the corner.

The remaining couplings have again been set to one. The quasiparticles arising
from defects in the $A$ terms are fractons and cannot move in isolation,
whereas the defects in the $B$ terms give lineons, which can only move in
straight lines. The order in the X-Cube model is not topological. It has an
exponential, but sub-extensive, ground state degeneracy inherited from the
plaquette Ising model as a consequence of the subsystem symmetry.

It was observed recently in [43] that the Hamiltonian for the fracton-free
subsector (where all the $A$ cube terms are $+1$) of the X-Cube model in a
transverse field

$H=-\sum_{i}B_{i}^{xy}-\sum_{i}B_{i}^{yz}-\sum_{i}B_{i}^{xz}-g^{\prime}\sum\tau^{x}$
(12)

could be written in terms of a dual Hamiltonian (at the risk of causing
confusion we have kept the notation of [35] for the $A$ and $B$ terms rather
than [43], which swaps $A$ and $B$, though we denote the edge Pauli matrices
by $\tau$ rather than $\sigma$ in distinction to both [35, 43]) with three
flavours of Ising spins $\sigma_{i},\tau_{i},\mu_{i}$ living on the vertices
of the cubic lattice rather than the links

$\displaystyle H=$ $\displaystyle-$ $\displaystyle g^{\prime}\sum_{\langle
ij\rangle}\sigma_{i}^{z}\sigma_{j}^{z}\mu_{i}^{z}\mu_{j}^{z}-g^{\prime}\sum_{\langle
ik\rangle}\tau_{i}^{z}\tau_{k}^{z}\mu_{i}^{z}\mu_{k}^{z}-g^{\prime}\sum_{\langle
jk\rangle}\sigma_{j}^{z}\sigma_{k}^{z}\tau_{j}^{z}\tau_{k}^{z}$
$\displaystyle-$
$\displaystyle\sum_{i}\left(\sigma_{i}^{x}\mu_{i}^{x}+\tau_{i}^{x}\mu_{i}^{x}+\sigma_{i}^{x}\tau_{i}^{x}\right)\;,$

where the nearest neighbour sums in the four spin terms each run along one of
the orthogonal axes, with $ij,ik$ and $jk$ representing the $z$, $y$ and $x$
axes respectively. The constraint on the $A$ terms is automatically resolved
by these spins.

In this paper we discuss the properties of the classical spin version of this
Hamiltonian,

$H_{dual2}=-\sum_{\langle
ij\rangle}\sigma_{i}\sigma_{j}\mu_{i}\mu_{j}-\sum_{\langle
ik\rangle}\tau_{i}\tau_{k}\mu_{i}\mu_{k}-\sum_{\langle
jk\rangle}\sigma_{j}\sigma_{k}\tau_{j}\tau_{k}\,,$ (14)

dubbed $H_{dual2}$ for reasons to be explained in the next section. We shall
see that it is closely related via a gauge-fixing to the Ashkin–Teller-like
[44] Hamiltonian, $H_{dual1}$, constructed using the classical Kramers–Wannier
duality from the $3d$ plaquette Ising model, as well as though a decoration
transformation to a third Hamiltonian, $H_{dual3}$, which mixes edge and
vertex spins. We find that the characteristic planar subsystem symmetry of the
$3d$ plaquette Ising model is still present in $H_{dual1,2,3}$ and also that
the interesting, possibly glassy, dynamical properties of the $3d$ plaquette
model are also apparent in the duals. The Hamiltonians $H_{dual2,3}$ are
already implicit in the discussion by Savvidy and Wegner in [45] in the
context of the general framework for dualities [46] in spin models.

##  2 Duals Galore

The Kramers–Wannier dual to $H_{\kappa=0}$ was initially constructed by
Savvidy et al. [34] by considering the high temperature expansion of the
plaquette Hamiltonian

$\displaystyle Z(\beta)$ $\displaystyle=$
$\displaystyle\sum_{\\{\sigma\\}}\exp(-\beta H_{\kappa=0})$ (15)
$\displaystyle=$
$\displaystyle\sum_{\\{\sigma\\}}\prod_{\Box}\cosh\left(\beta\right)\left[1+\tanh\left(\beta\right)(\sigma_{i}\sigma_{j}\sigma_{k}\sigma_{l})\right]$

which can be written as

$Z(\beta)=\left[2\cosh\left(\beta\right)\right]^{3L^{3}}\sum_{\\{S\\}}\left[\tanh\left(\beta\right)\right]^{n(S)}$
(16)

on an $L^{3}$ cubic lattice, where the sum runs over closed surfaces with an
even number of plaquettes at any vertex. In the summation $n(S)$ is the number
of plaquettes in a given surface. The low temperature expansion, i.e., high
temperature in the dual variable

$\beta^{*}=-(1/2)\log[\tanh(\beta)]$

of the following anisotropic Hamiltonian

$H_{dual0}=-\sum_{\langle ij\rangle}\sigma_{i}\sigma_{j}-\sum_{\langle
ik\rangle}\tau_{i}\tau_{k}-\sum_{\langle jk\rangle}\eta_{j}\eta_{k}$ (17)

produced the requisite diagrams. In $H_{dual0}$ the sums are one-dimensional
and run along the orthogonal axes, with $ij,ik$ and $jk$ again representing
the $z$, $y$ and $x$ axes respectively using our conventions. The spins are
non-Ising and live in the fourth order Abelian group, since the geometric
constraints on having an even number of plaquettes at each vertex mean that

$\displaystyle e\sigma$ $\displaystyle=$
$\displaystyle\sigma\;,\;\;e\tau=\tau\;,\;\;e\eta=\eta$
$\displaystyle\sigma^{2}$ $\displaystyle=$ $\displaystyle\tau^{2}=\eta^{2}=e$
(18) $\displaystyle\sigma\tau$ $\displaystyle=$
$\displaystyle\eta\,,\;\;\tau\eta=\sigma\;,\;\;\eta\sigma=\tau$

with $e$ being the identity element. They can be thought of as representing
differently oriented matchbox surfaces such as that shown in Figure 3, which
are combined by facewise multiplication.

Figure 3: One of the matchbox surfaces which satisfy the algebra of Equation
(2).

The shaded faces carry a negative sign and the associated spin variable lives
at the centre of the matchbox. Any spin cluster boundary in the model can be
constructed from such matchboxes while still satisfying the local constraint
on the number of incident plaquettes.

The spins may also be taken to be Ising ($\pm 1$) variables if we set
$\eta_{i}=\sigma_{i}\;\tau_{i}$, which is more convenient for simulations.
This modifies $H_{dual0}$ to an anisotropically coupled Ashkin–Teller
Hamiltonian [44]

$H_{dual1}=-\sum_{\langle ij\rangle}\sigma_{i}\sigma_{j}-\sum_{\langle
ik\rangle}\tau_{i}\tau_{k}-\sum_{\langle
jk\rangle}\sigma_{j}\sigma_{k}\tau_{j}\tau_{k}\,.$ (19)

This formulation of the dual model was first investigated numerically in [47]
and it was found that it displayed a first order phase transition and a
similar planar subsystem symmetry to that of $H_{\kappa=0}$. The continued
presence of the subsystem symmetry was a consequence of the anisotropic
couplings, which allowed a greater freedom in transforming the spin variables
than in the isotropically coupled version of Equation (19), which is just the
Ashkin–Teller model at its four-state Potts point.

It is possible to construct $H_{dual1}$ and its higher dimensional equivalents
[45] using the general framework for duality in Ising lattice spin models that
was first formulated by Wegner in [46]. Suprisingly, there are two further
possible ways to write the dual to $H_{\kappa=0}$ in three dimensions with
this machinery, using either the general formula for the dual of codimension
one surfaces or the formula for the dual of two dimensional surfaces in $d$
dimensions. If we temporarily use the notation of [45], the dual Hamiltonian
for a codimension one surface in $d$ dimensions is given there by

$\displaystyle H^{d}_{dual,codim1}$ $\displaystyle=$
$\displaystyle-\sum_{\alpha<\beta,\,\vec{r}}\prod_{\gamma}\Lambda_{\alpha,\beta\gamma}(\vec{r})\Lambda_{\alpha,\beta\gamma}(\vec{r}+\vec{e}_{\gamma})\Lambda_{\beta,\alpha\gamma}(\vec{r})\Lambda_{\beta,\alpha\gamma}(\vec{r}+\vec{e}_{\gamma})$

where the $\Lambda$ spins live on each of the $(d-3)$ dimensional
(hyper)vertices situated at the vertices $\vec{r}$ of the hypercubic lattice
and the indices $\alpha,\beta,\gamma$ run from $1$ to $d$. The unit vectors
$\vec{e}_{\gamma}$ point along the lattice axes. On the other hand, the dual
Hamiltonian for a two-dimensional gonihedric surface embedded in $d$
dimensions is of the form

$H^{d}_{dual,\,2d}=-\sum_{\vec{r}}\sum_{\beta\neq\gamma}\Lambda_{\beta\gamma}(\vec{r})\Gamma(\vec{r},\vec{r}+\vec{e}_{\gamma})\Lambda_{\beta\gamma}(\vec{r}+\vec{e}_{\gamma})$
(21)

where we now have $\Gamma$ spins on each (hyper)edge in addition to the
$\Lambda$ spins at each vertex.

If we specialize to two dimensional plaquette surfaces embedded in a cubic
lattice in three dimensions, which is the case for the dual of $H_{\kappa=0}$,
either formulation may be employed since this is both a codimension one
surface and a two-dimensional surface embedded in three dimensions. Returning
to our own notation, the codimension one Hamiltonian of Equation (2) in three
dimensions may be written as

$H_{dual2}=-\sum_{\langle
ij\rangle}\sigma_{i}\sigma_{j}\mu_{i}\mu_{j}-\sum_{\langle
ik\rangle}\tau_{i}\tau_{k}\mu_{i}\mu_{k}-\sum_{\langle
jk\rangle}\sigma_{j}\sigma_{k}\tau_{j}\tau_{k}\,,$

which is just the Hamiltonian of Equation (14) that appeared as the classical
spin limit of the dual to the fracton-free subspace of the X-Cube model. The
three flavours of spins living at each vertex display a local Ising gauge
symmetry
$\sigma_{i},\tau_{i},\mu_{i}\to\gamma_{i}\sigma_{i},\gamma_{i}\tau_{i},\gamma_{i}\mu_{i}$
in addition to the planar subsystem symmetry shared with $H_{\kappa=0}$ and
$H_{dual1}$, as we shall see presently.

Still within the general approach of Savvidy and Wegner [45, 46], in three
dimensions the Hamiltonian of Equation (21) for the two-dimensional surface
variant also contains three flavours of vertex spins
$\sigma_{i},\tau_{i},\mu_{i}$, but in addition there are gauge-like spin
variables $U_{ij}^{1,2,3}$ living on the lattice edges which couple in an
anisotropic manner to the vertex spins

$\displaystyle H_{dual3}$ $\displaystyle=$ $\displaystyle-\sum_{\langle
ij\rangle}\left(\sigma_{i}U^{1}_{ij}\sigma_{j}+\mu_{i}U^{1}_{ij}\mu_{j}\right)-\sum_{\langle
ik\rangle}\left(\tau_{i}U^{2}_{ik}\tau_{k}+\mu_{i}U^{2}_{ik}\mu_{k}\right)$
(22) $\displaystyle-$ $\displaystyle\sum_{\langle
jk\rangle}\left(\sigma_{j}U^{3}_{jk}\sigma_{k}+\tau_{j}U^{3}_{jk}\tau_{k}\right)\;.$

We thus have four different Hamiltonian formulations for the dual of the
plaquette Hamiltonian $H_{\kappa=0}$ in three dimensions:

  * •

$H_{dual0}$ in Equation (17) with non-Ising spins.

  * •

$H_{dual1}$ in Equation (19) with Ising spins, which is Ashkin–Teller in form.

  * •

$H_{dual2}$ in Equation (14) containing purely four spin interactions.

  * •

$H_{dual3}$ in Equation (22) containing both vertex spins and gauge-like edge
spins.

We have already seen that setting $\eta_{i}=\sigma_{i}\;\tau_{i}$ in
$H_{dual0}$ in equ. (17), with $\sigma_{i},\tau_{i}$ being Ising spins, keeps
the algebra of Equation (2) intact and gives the Ashkin–Teller Hamiltonian of
$H_{dual1}$ in Equation (19). In the next section we discuss the relation
between the four-spin Hamiltonian $H_{dual2}$ of Equation (14) and the gauge-
spin Hamiltonian $H_{dual3}$ of Equation (22), and thereafter that between
$H_{dual2}$ and $H_{dual1}$.

##  3 Decoration

The equivalence between $H_{dual3}$ and $H_{dual2}$ is a consequence of a
variation of the classical decoration transformation [48]. In the standard
transformation an edge with spins $\sigma_{1},\sigma_{2}$ at each vertex is
decorated with a link spin $s$ as in Figure 4.

Figure 4: The standard decoration transformation. Summing over the central
spin $s$ denoted by an open dot gives a new effective coupling
$\beta=\frac{1}{2}\log[\cosh(2\tilde{\beta})]$ between the spins on the end of
the link.

If the coupling between $s$ and $\sigma_{1}$ and $\sigma_{2}$ is
$\tilde{\beta}$, summing over the central spin $s$ gives rise to a new
effective coupling $\beta$ between the primary vertex spins
$\sigma_{1},\sigma_{2}$

$\sum_{s}\exp\left[\tilde{\beta}s(\sigma_{1}+\sigma_{2})\right]=A\,\exp(\beta\sigma_{1}\sigma_{2}).$
(23)

Both the prefactor $A$ and the coupling $\beta$ may be expressed in terms of
$\tilde{\beta}$ by enumerating possible spin configurations in Equation (23).
This gives

$\displaystyle A$ $\displaystyle=$ $\displaystyle
2\cosh(2\tilde{\beta})^{1/2}$ $\displaystyle\beta$ $\displaystyle=$
$\displaystyle\frac{1}{2}\log[\cosh(2\tilde{\beta})].$ (24)

We can repeat this procedure with the $U$ spins on each edge in $H_{dual3}$.
In this case each direction has two flavours of vertex spin and performing the
sum generates the four-spin couplings of $H_{dual2}$, for example

$\displaystyle\sum_{\\{U^{1}_{12}\\}}\exp\left[\tilde{\beta}\left(\sigma_{1}U^{1}_{12}\sigma_{2}+\mu_{1}U^{1}_{12}\mu_{2}\right)\right]=A\,\exp(\beta\sigma_{1}\sigma_{2}\mu_{1}\mu_{2}).$
(25)

where $A$ and the relation between $\beta,\tilde{\beta}$ are the same as in
Equation (24).

The sum over $U$ may be carried out globally over every edge which immediately
demonstrates equivalence of the partition functions for $H_{dual3}$ and
$H_{dual2}$

$\displaystyle Z$ $\displaystyle=$
$\displaystyle\sum_{\\{U,\sigma\\}}\exp[-\tilde{\beta}H_{dual3}]$
$\displaystyle=$
$\displaystyle\sum_{\\{U,\sigma\\}}\exp\left[\tilde{\beta}\sum_{\langle
ij\rangle}\left(\sigma_{i}U^{1}_{ij}\sigma_{j}+\mu_{i}U^{1}_{ij}\mu_{j}\right)+\tilde{\beta}\sum_{\langle
ik\rangle}\left(\tau_{i}U^{2}_{ik}\tau_{k}+\mu_{i}U^{2}_{ik}\mu_{k}\right)\right.$
$\displaystyle+$ $\displaystyle\left.\tilde{\beta}\sum_{\langle
jk\rangle}\left(\sigma_{j}U^{3}_{jk}\sigma_{k}+\tau_{j}U^{3}_{jk}\tau_{k}\right)\right]$
$\displaystyle=$ $\displaystyle
B\,\sum_{\\{\sigma\\}}\exp\left[\beta\left(\sum_{\langle
ij\rangle}\sigma_{i}\sigma_{j}\mu_{i}\mu_{j}+\sum_{\langle
ik\rangle}\tau_{i}\tau_{k}\mu_{i}\mu_{k}+\sum_{\langle
jk\rangle}\sigma_{j}\sigma_{k}\tau_{j}\tau_{k}\right)\right]$ $\displaystyle=$
$\displaystyle B\,\sum_{\\{\sigma\\}}\exp[-\beta H_{dual2}].$

The overall factor $B$ coming from a product of $A$’s on the individual links
is irrelevant for calculating physical quantities and the two couplings are
again related by the decoration relation,
$\beta=\frac{1}{2}\log[\cosh(2\tilde{\beta})]$.

##  4 Gauge Fixing and Subsystem Symmetry

The equivalence between $H_{dual2}$ and $H_{dual1}$, on the other hand, is a
consequence of a gauge symmetry which is present in $H_{dual2}$ [49]

$\sigma_{i},\,\tau_{i},\,\mu_{i}\,\to\,\gamma_{i}\sigma_{i},\,\gamma_{i}\tau_{i},\,\gamma_{i}\mu_{i}\,.$
(27)

We are at liberty to choose the Ising spin gauge transformation parameter
$\gamma_{i}$ to be equal to one of the spin values, say $\mu_{i}$, at each
site so the gauge transformation then becomes

$\sigma_{i},\,\tau_{i},\,\mu_{i}\,\to\,\mu_{i}\sigma_{i},\,\mu_{i}\tau_{i},\,1$
(28)

which, using the fact that the sum over the remaining spin variables
$\sigma_{i},\tau_{i}$ is invariant under the transformation, relates the
partition functions for the two Hamiltonians as

$\displaystyle Z$ $\displaystyle=$
$\displaystyle\sum_{\\{\sigma,\tau,\mu\\}}\exp\left[-\beta
H_{dual2}(\sigma,\tau,\mu)\right]$ $\displaystyle=$ $\displaystyle
2^{L^{3}}\sum_{\\{\sigma,\tau\\}}\exp\left[-\beta
H_{dual2}(\sigma,\tau,\mu=1)\right]$ $\displaystyle=$ $\displaystyle
2^{L^{3}}\sum_{\\{\sigma,\tau\\}}\exp\left[-\beta
H_{dual1}(\sigma,\tau)\right]\;.$

The coupling $\beta$ is not transformed in this case and we can, of course,
choose to eliminate any one of the three spins, which simply amounts to
relabelling the axes. From this perspective $H_{dual1}$ is simply a gauge-
fixed version of $H_{dual2}$. This can be confirmed by Monte-Carlo simulations
which measure the same energies (and energy distributions) and transition
points for the observed first order phase transitions [49].

The equivalence between $H_{dual3}$ and $H_{dual2}$ described in the preceding
section via the decoration transformation also sheds light on the presence of
this gauge symmetry in $H_{dual2}$. All the terms in $H_{dual3}$ are of the
gauge-matter coupling form $\sigma_{i}U_{ij}\sigma_{j}$, so this action
possesses a similar, standard gauge invariance to that seen in other gauge-
matter systems such as the gauge–Ising model of Equation (7), namely

$\displaystyle\sigma_{i}\to\gamma_{i}\sigma_{i}\;,\;\sigma_{j}\to\gamma_{j}\sigma_{j}\;,\;U_{ij}^{1,3}\to\gamma_{i}U_{ij}^{1,3}\gamma_{j}$
$\displaystyle\tau_{i}\to\gamma_{i}\tau_{i}\;,\;\tau_{j}\to\gamma_{j}\tau_{j}\;,\;U_{ij}^{2,3}\to\gamma_{i}U_{ij}^{2,3}\gamma_{j}$
(30)
$\displaystyle\mu_{i}\to\gamma_{i}\mu_{i}\;,\;\mu_{j}\to\gamma_{j}\mu_{j}\;,\;U_{ij}^{1,2}\to\gamma_{i}U_{ij}^{1,2}\gamma_{j}\;.$

When the $U$ spins are summed over to give $H_{dual2}$, the gauge symmetry of
the $\sigma,\tau$ and $\mu$ spins in Equation (27) remains as an echo of this
symmetry. In both cases if we look at a single site transformation all three
spins $\sigma_{i},\tau_{i}$ and $\mu_{i}$ must be transformed. In $H_{dual3}$
this is a consequence of the way in which the three edge spins
$U^{1,2,3}_{ij}$ couple to the vertex spins.

A characteristic feature of $H_{dual1}$ is the planar subsystem symmetry
intermediate between a gauge and a global symmetry, just as with the $3d$
plaquette Ising Hamiltonian. For $H_{dual2}$ the anisotropic couplings mean
that it is still possible to flip planes of one of the spins (the one which is
“missing” from the interactions in the direction perpendicular to the planes)
at zero energy cost as shown in Figure 5.

$\sigma\,\mu$$\sigma\,\tau$$\tau\,\mu$

$+-+$

$-++$

$++-$

Figure 5: Four Possible ground state spin configurations on a cube for
$H_{dual2}$. The initial cube again has all $+$ spins and the
$\sigma,\tau,\mu$ values are shown for the spins at the corners of the darker
shaded flipped faces, with the other spins being positive. The directions of
the anisotropic couplings in the Hamiltonian are indicated.

It is also possible to flip two or three orthogonal faces on the cube, so
tiling the entire lattice with such combinations we can see that in addition
to the purely ferromagnetic ground state we may have arbitrary (and possibly
intersecting) flipped planes of spins.

The ground state structure, and the mechanism of anisotropic couplings which
allows the plane spin flips, is thus identical to that in $H_{dual1}$, whose
possible ground states on a single cube we recall for comparison in Figure 6.

$\sigma$$\sigma\,\tau$$\tau$

$+-$

$-+$

$--$

Figure 6: Four possible ground state spin configurations on a cube for the
Ashkin–Teller formulation of the dual Hamiltonian, $H_{dual1}$. The
$\sigma,\tau$ values are shown for the darker shaded flipped planes. The
directions of the anisotropic couplings in the Hamiltonian are again
indicated.

Flipping the third spin $\mu$ in $H_{dual2}$, which is absent in $H_{dual1}$,
is replaced by flipping both the $\sigma$ and $\tau$ spins in $H_{dual1}$,
consistent with the gauge transformation relating the two Hamiltonians. In
summary, the ground state structure of $H_{dual2}$ shows an interesting
interplay between the gauge symmetry of Equation (27) and the subsystem
symmetry. The local gauge symmetry allows one to reduce the effective number
of degrees of freedom and recover the ground state structure of $H_{dual1}$.

$H_{dual3}$ is a similar case since the geometrical arrangement of the
couplings is similar in spite of the presence of the additional spins $U$ on
the links. Each of the $\sigma,\tau,\mu$ spins couple in two directions, which
define the lattice planes in which they can be flipped without affecting the
energy.

##  5 Indicative Monte-Carlo

Low precision Monte-Carlo simulations using simple Metropolis updates found a
first order phase transition in both $H_{dual2}$ and $H_{dual1}$ in the region
$\beta\simeq 1.3-1.4$ [47, 49]. Much higher precision simulations using
multicanonical methods were later carried out for the original $3d$ plaquette
Ising model $H_{\kappa=0}$ and the Ashkin–Teller dual $H_{dual1}$ in order to
accurately determine the transition point ($\beta^{\infty}=1.31328(12)$ in the
case of the dual model) and confirm the non-standard finite size scaling that
is a consequence of the exponential degeneracy of the low temperature phase
[25, 26, 27, 28, 29]. Even with the modest statistics and the use of a
Metropolis update in the simulations of [47, 49] a sharp drop in the energy,
as would be expected for a first order transition, is clearly visible in the
region of the transition point. A plot of the energy is shown for various
lattice sizes in Figure 7 for $H_{dual2}$ and the values for $H_{dual1}$ are
essentially identical.

Figure 7: The energy for $H_{dual2}$ on lattices ranging from $10^{3}$ to
$20^{3}$ from left to right. The lines joining the data points are drawn to
guide the eye. Data from $H_{dual1}$ is essentially identical.

The first order nature of the transition for $H_{dual2}$ and $H_{dual1}$ can
be further confirmed by observing a dual peak structure in the energy
histogram $P(E)$ near the transition point and a non-trivial value of Binder’s
energy cumulant

$U_{E}=1-\frac{\langle E^{4}\rangle}{3\langle E^{2}\rangle^{2}}$ (31)

as a consequence of the shape of $P(E)$ [25, 49].

Based on these observations, and allowing for a factor of $1/2$ in our
definitions of $H_{dual1}$ and $H_{dual2}$ in [47, 49], we would expect to see
a transition in $H_{dual3}$ at the the value of $\tilde{\beta}$ found by
inverting the decoration transformation, namely
$\frac{1}{2}\cosh^{-1}(\exp(1.3-1.4))=0.99-1.04$ in the thermodynamic limit.
To confirm this expectation, we carried out Monte-Carlo simulations using
$10^{3},12^{3},16^{3}$ and $18^{3}$ lattices with periodic boundary conditions
for all spins at various temperatures, again with a simple Metropolis update.
After an appropriate number of thermalization sweeps, $10^{7}$ measurement
sweeps were carried out at each lattice size for each temperature.

Looking at measurements of the energy from our simulations of $H_{dual3}$ in
Figure 8 we can see that a similar sharp drop in the energy consistent with a
first order transition is still present.

Figure 8: The energy for $H_{dual3}$ on lattices ranging from $10^{3}$ to
$18^{3}$ from left to right. The lines joining the data points are drawn to
guide the eye.

The observed finite size estimates for the transition temperatures
$\beta_{c}(L)$ agree with those calculated by transforming the values from
Figure 7 using the decoration relation, e.g., for $L=10$ we would expect
$\beta_{c}(10)\simeq\frac{1}{2}\cosh^{-1}[\exp(1.27)]\simeq 0.97$, as found
directly in the simulation shown in Figure 8. Further evidence for a first
order transition with $H_{dual3}$, as noted above for the other dual
Hamiltonians, can be garnered by looking at the energy histogram $P(E)$ to
discern a dual peak structure near the transition point. In Figure 9 $P(E)$ is
shown close to the estimated transition point for $L=10$ at $\beta\simeq 0.97$
and there is clear evidence of two peaks.

Figure 9: The energy histogram $P(E)$ for $H_{dual3}$ close to the estimated
transition point at $\beta\simeq 0.97$ on a $10^{3}$ lattice.

The relatively low statistics and the use of a Metropolis update for the data
presented here for $H_{dual2}$ and $H_{dual3}$ mean that a high accuracy
extrapolation using the correct $1/L^{2}$ finite size scaling for the
transition point is not feasible, which would require more extensive
multicanonical simulations along the lines of [25, 26, 29]. Nonetheless, the
agreement of the suitably transformed finite size lattice transition points in
the Monte-Carlo simulations confirm that $H_{dual3}$ and $H_{dual2}$ are
related by the decoration transformation and the first order nature of the
transition for $H_{dual3}$ is clear from the dual peak form of $P(E)$ near the
transition point in Figure 9.

##  6 Dynamics

Another interesting feature of the original plaquette Hamiltonian
$H_{\kappa=0}$ is its dynamical behaviour. It possesses a region of strong
metastability around the first order phase transition and displays glassy
characteristics at lower temperatures [18, 19, 20, 21, 22, 23, 24] with non-
trivial ageing properties. We found that the Ashkin–Teller dual Hamiltonian
$H_{dual1}$ also shares these characteristics since it failed to relax to the
equilibrium minimum energy of $E=-1.5$ when cooled quickly from a hot start
[47]. Note that in this case, since we are exploring the real time dynamics of
the system, simulations with a Metropolis update are preferable to more
sophisticated algorithms.

$H_{dual2}$ displays identical behaviour under cooling to $H_{dual1}$. We
consider $20^{3},60^{3}$ and $80^{3}$ lattices which are first equilibrated in
the high temperature phase at $T=3.0$ and then cooled at different rates to
zero temperature. The energy time series is recorded during this process. In
Figure 10 we can see that with a slow cooling rate of $\delta T=0.00001$ per
sweep, the model still relaxes to a ground state with $E=-1.5$ for all the
lattice sizes.

Figure 10: The time series of energy measurements obtained from cooling
$20^{3},60^{3}$ and $80^{3}$ lattices from a hot start at $T=3.0$ at a rate of
$\delta T=0.00001$ per sweep. The traces are effectively indistinguishable.

However, as can be seen in Figure 11 with a faster cooling rate of $\delta
T=0.001$ per sweep the model no longer relaxes to the ground state energy of
$E=-1.5$, but is trapped at a higher value, which is around $-1.415$ for the
larger two ($60^{3}$ and $80^{3}$) lattices.

Figure 11: The time series of energy measurements obtained from cooling
$20^{3},60^{3}$ and $80^{3}$ lattices from a hot start at a rate of $\delta
T=0.001$ per sweep.

Whether the observed behaviour under cooling is a sign of genuine glassiness
in $H_{\kappa=0}$ or not remains a matter of debate and similar considerations
would apply to the dual Hamiltonians discussed here.

##  7 Discussion

Motivated by recent work on the quantum X-Cube Hamiltonian and related dual
models [43] we revisit various formulations of classical spin Hamiltonians
dual to the $3d$ plaquette Ising model. We describe the following chain of
relations between these models

$\displaystyle H_{dual3}$ $\displaystyle=$ $\displaystyle-\sum_{\langle
ij\rangle}\left(\sigma_{i}U^{1}_{ij}\sigma_{j}+\mu_{i}U^{1}_{ij}\mu_{j}\right)-\sum_{\langle
ik\rangle}\left(\tau_{i}U^{2}_{ik}\tau_{k}+\mu_{i}U^{2}_{ik}\mu_{k}\right)$
$\displaystyle-$ $\displaystyle\sum_{\langle
jk\rangle}\left(\sigma_{j}U^{3}_{jk}\sigma_{k}+\tau_{j}U^{3}_{jk}\tau_{k}\right)$
$\displaystyle\longrightarrow\textrm{(Un)Decoration}\longrightarrow$
$\displaystyle H_{dual2}$ $\displaystyle=$ $\displaystyle-\sum_{\langle
ij\rangle}\sigma_{i}\sigma_{j}\mu_{i}\mu_{j}-\sum_{\langle
ik\rangle}\tau_{i}\tau_{k}\mu_{i}\mu_{k}-\sum_{\langle
jk\rangle}\sigma_{j}\sigma_{k}\tau_{j}\tau_{k}$ (32)
$\displaystyle\longrightarrow\textrm{Gauge-Fixing}\longrightarrow$
$\displaystyle H_{dual1}$ $\displaystyle=$ $\displaystyle-\sum_{\langle
ij\rangle}\sigma_{i}\sigma_{j}-\sum_{\langle
ik\rangle}\tau_{i}\tau_{k}-\sum_{\langle
jk\rangle}\sigma_{j}\sigma_{k}\tau_{j}\tau_{k}$
$\displaystyle\longrightarrow\textrm{Non-Ising variables}\longrightarrow$
$\displaystyle H_{dual0}$ $\displaystyle=$ $\displaystyle-\sum_{\langle
ij\rangle}\sigma_{i}\sigma_{j}-\sum_{\langle
ik\rangle}\tau_{i}\tau_{k}-\sum_{\langle jk\rangle}\eta_{j}\eta_{k}$
$\displaystyle\longrightarrow\textrm{Kramers--Wannier duality}\longrightarrow$
$\displaystyle H_{\kappa=0}$ $\displaystyle=$
$\displaystyle-\sum_{\Box}\sigma_{i}\sigma_{j}\sigma_{k}\sigma_{l}$

where we have indicated the operations relating the various Hamiltonians. A
variant of the decoration transformation in which edge spins are summed out
relates $H_{dual3}$ to $H_{dual2}$. In transforming $H_{dual3}$ to $H_{dual2}$
the coupling is therefore transformed as
$\beta=\frac{1}{2}\ln[\cosh(2\tilde{\beta})]$. The gauge-invariant nature of
$H_{dual3}$ due to the presence of both edge and vertex spins leaves an echo
in the vertex spin gauge symmetry of $H_{dual2}$, which in turn ensures the
equivalence of $H_{dual2}$ and $H_{dual1}$ via a gauge-fixing. Allowing non-
Ising spins gives a final equivalence between the dual models $H_{dual1}$ and
$H_{dual0}$ and a standard Kramers–Wannier duality transformation then takes
us back to the $3d$ plaquette Ising Hamiltonian of $H_{\kappa=0}$ where the
story began.

The planar subsystem symmetry of this $3d$ plaquette Ising Hamiltonian
$H_{\kappa=0}$ remains a feature of the various dual Hamiltonians and affects
the finite size scaling properties at the first order transition displayed by
these models, just as with $H_{\kappa=0}$. The nature of the order parameter
for the various duals, and indeed $H_{\kappa=0}$ itself, remains to be
satisfactorily clarified. An attempt at this has been made for $H_{\kappa=0}$
in [50] and indeed appeared to give sensible numerical results in [25, 26, 27,
28, 29]. This was based on the observation by Suzuki et al. [51, 52, 53] that
an anisotropic version of the $3d$ plaquette Ising model with open boundary
conditions could be transformed to an uncoupled stack of $2d$ Ising models and
suggested that a two spin correlator summed perpendicular to lattice planes
might still serve as an order parameter in the isotropically coupled case of
$H_{\kappa=0}$. It would be more satisfactory to have a less heuristic
approach to an order parameter based on a clearer understanding of the nature
of the low temperature order in the $3d$ plaquette Ising Hamiltonian. In this
respect a study of the order parameters in the various dual models might be
helpful.

In a similar vein, the principal interest in [43] was actually investigating
“odd” variants of fracton models, in which the signs of some of the terms in
the Hamiltonians were reversed, leading to frustrated models. The geometrical
nature of the order in such frustrated spin models would be of interest in the
classical case too. Finally, the dynamics of the various classical
Hamiltonians discussed here display glassy features. The question of whether
the glassy dynamics of the quasiparticle excitations in the quantum models
[54, 55] offers any insights into this behaviour may be worth pursuing.

##  8 Acknowledgements

The work of Ranasinghe P.K.C.M. Ranasinghe was supported by a Commonwealth
Academic Fellowship LKCF-2010-11 and would like to thank Heriot-Watt
University for hospitality when this work was initiated.

## References

  * [1] Kramers, H.A.; Wannier, G.H. Statistics of the two-dimensional ferromagnet: Part 1. Phys. Rev. 1941, 60, 252–262.
  * [2] Ambartzumian R.V.; Sukiasian G.S.; Savvidy G.K.; Savvidy, K.G. Alternative model of random surfaces. Phys. Lett. B 1992, 275, 99–102.
  * [3] Savvidy, G.K.; Savvidy, K.G. String fine-tuning. Int. J. Mod. Phys. A 1993, 8, 3393–4011.
  * [4] Savvidy, G.K.; Savvidy, K.G. Gonihedric string and asymptotic freedom. Mod. Phys. Lett. A 1993, 8, 2963–2971.
  * [5] Ambjørn, J.; Savvidy, G.K.; Savvidy, K.G. Alternative actions for quantum gravity and intrinsic rigidity of space-time. Nucl. Phys. B 1997, 486, 390–412.
  * [6] Savvidy, G.K.; Wegner, F.J. Geometrical string and spin systems. Nucl. Phys. B 1994, 413, 605–613.
  * [7] Savvidy, G.K.; Savvidy, K.G. Self-avoiding surfaces and spin systems. Phys. Lett. B 1994, 324, 72–77.
  * [8] Savvidy, G.K.; Savvidy, K.G. Interaction hierarchy. Phys. Lett. B 1994, 337, 333–339.
  * [9] Bathas, G.K.; Floratos, E.; Savvidy, G.K.; Savvidy, K.G. Two-and three-dimensional spin systems with gonihedric action. Mod. Phys. Lett. A 1995, 10, 2695–2701.
  * [10] Savvidy, G.K.; Savvidy, K.G. Interaction hierarchy: string and quantum gravity. Mod. Phys. Lett. A 1996, 11, 1379–1396.
  * [11] Koutsoumbas, G; Savvidy, G.K.; Savvidy, K.G. Phase structure of four-dimensional gonihedric spin system. Phys. Lett. B 1997, 410, 241–249.
  * [12] Ambjørn, J.; Koutsoumbas, G.; Savvidy, G.K. Four-dimensional gonihedric gauge spin system. Europhys. Lett. 1999, 46, 319–325.
  * [13] Koutsoumbas, G.; Savvidy, G.K. Three-dimensional gonihedric spin system. Mod. Phys. Lett. A 2002, 17, 751–761.
  * [14] Johnston, D.; Malmini, R.P.K.C. Gonihedric 3D Ising actions. Phys. Lett. B 1996, 378, 87–96.
  * [15] Baig, M.; Espriu, D.; Johnston, D.; Malmini, R.P.K.C. Evidence for a first-order transition in a plaquette three-dimensional Ising-like action. J. Phys. A 1997, 30, 405–412.
  * [16] Baig, M.; Espriu, D.; Johnston, D.; Malmini, R.P.K.C. String tension in gonihedric three-dimensional Ising models. J. Phys. A 1997, 30, 7695–7706.
  * [17] Cappi, A.; Colangelo, P.; Gonella, G.; Maritan, A. Ensemble of interacting random surfaces on a lattice. Nucl. Phys. B 1992, 370, 659–694.
  * [18] Lipowski, A. Glassy behaviour and semi-local invariance in Ising model with four-spin interaction. J. Phys. A 1997, 30, 7365–7373.
  * [19] Lipowski, A; Johnston, D. Metastability in a four-spin Ising model. J. Phys. A 2000, 33, 4451–4460.
  * [20] Lipowski, A; Johnston, D. Cooling-rate effects in a model of glasses. Phys. Rev. E 2000, 61, 6375–6382.
  * [21] Lipowski, A; Johnston, D.; Espriu, D. Slow dynamics of Ising models with energy barriers. Phys. Rev. E 2000, 62, 3404–3410.
  * [22] Swift, M.; Bokil, H.; Travasso, R.; Bray, A. Glassy behavior in a ferromagnetic p-spin model. Phys. Rev. B 2000, 62, 11494–11498.
  * [23] Cavagna, A.; Giardina, I.; Grigera, T.S. Glassy dynamics, metastability limit and crystal growth in a lattice spin model. Europhys. Lett. 2003, 61, 74–80.
  * [24] Davatolhagh, S.; Dariush, D.; Separdar, L. Nature of the glassy transition in simulations of the ferromagnetic plaquette Ising model. Phys. Rev. E 2010, 81, 031501.
  * [25] Mueller, M.; Janke, W.; Johnston, D.A. Nonstandard finite-size scaling at first-order phase transitions. Phys. Rev. Lett. 2014, 112, 200601.
  * [26] Mueller, M.; Johnston, D.A.; Janke, W. Multicanonical analysis of the plaquette-only gonihedric Ising model and its dual. Nucl. Phys. B 2014, 888, 214–235.
  * [27] Mueller, M.; Janke, W.; Johnston, D.A. Transmuted finite-size scaling at first-order phase transitions. Physics Procedia 2014, 57, 68–72.
  * [28] Janke, W.; Mueller, M.; Johnston, D.A. Finite-size scaling and latent heat at the gonihedric first-order phase transition. J. Phys.: Conf. Ser. 2015, 640, 012002
  * [29] Mueller, M.; Janke, W.; Johnston, D.A. Planar ordering in the plaquette-only gonihedric Ising model. Nucl. Phys. B 2015, 894, 1–14.
  * [30] Borgs, C.; Janke, W. New method to determine first-order transition points from finite-size data. Phys. Rev. Lett. 1992, 68, 1738–1741.
  * [31] Janke, W.; Villanova, R. Three-dimensional 3-state Potts model revisited with new techniques. Nucl. Phys. B[FS] 1997, 489, 679–696.
  * [32] Pietig, R.; Wegner, F.J. Phase transition in lattice surface systems with gonihedric action. Nucl. Phys. B 1996, 466, 513–526.
  * [33] Pietig, R.; Wegner, F.J. Low temperature expansion of the gonihedric Ising model. Nucl. Phys. B 1998, 525, 549–570.
  * [34] Savvidy, G.K.; Savvidy, K.G.; Savvidy, P.G. Dual statistical systems and geometrical string. Phys. Lett. A 1996, 221, 233–238.
  * [35] Vijay, S.; Haah, J.; Fu, L. Fracton topological order, generalized lattice gauge theory, and duality. Phys. Rev. B 2016, 94, 235157.
  * [36] Pretko, M.; Chen X.; You, Y. Fracton phases of matter. arXiv 2020, arXiv:2001.01722.
  * [37] Nandkishore, R. M.; Hermele, M. Fractons. Annu. Rev. Condens. Matter Phys. 2019, 10, 295–313.
  * [38] Creutz, M. Phase diagrams for coupled spin-gauge systems. Phys. Rev. D 1980, 21, 1006–1012.
  * [39] Bhanot G.; Creutz, M. Phase diagram of $Z(N)$ and $U(1)$ gauge theories in three dimensions. Phys. Rev. D 1980, 21, 2892–2902.
  * [40] Gliozzi, F.; Rago, A. Monopole clusters, center vortices, and confinement in a $Z_{2}$ gauge-Higgs system. Phys. Rev. D 2002, 66, 074511.
  * [41] Araujo de Resende, M.F. A pedagogical overview on 2D and 3D Toric Codes and the origin of their topological orders. Reviews in Mathematical Physics 2020, 32(02), 2030002.
  * [42] Kitaev, A.Yu. Fault-tolerant quantum computation by anyons. Ann. Phys. 2003, 303, 2–30.
  * [43] Pretko, M.; Parameswaran, S.A.; Hermele, M. Odd fracton theories, proximate orders, and parton constructions. arXiv 2020, arXiv:2004.14393.
  * [44] Ashkin, J.; Teller, E. Statistics of two-dimensional lattices with four components. Phys. Rev. 1943, 64, 178-184.
  * [45] Savvidy, G.K.; Savvidy, K.G.; Wegner, F.J. Geometrical string and dual spin systems. Nucl. Phys. B 1995, 443, 565–580.
  * [46] Wegner, F.J. Duality in generalized Ising models and phase transitions without local order parameters. J. Math. Phys. 1971, 12, 2259–2272.
  * [47] Johnston, D.; Ranasinghe, R.P.K.C.M. The dual gonihedric 3D Ising model. J. Phys. A 2011, 44, 295004.
  * [48] Syozi, I. Transformation of Ising models. In Phase Transitions and Critical Phenomena, vol 1; Domb, C., Green, M.S., Eds.; Academic Press: New York, USA, 1972; pp. 269–329.
  * [49] Johnston, D.; Ranasinghe, R.P.K.C.M. Another dual gonihedric 3D Ising model. arXiv 2011, arXiv:1106.0325.
  * [50] Johnston, D. Gonihedric (and fuki-nuke) order. J. Phys. A 2012, 45, 405001.
  * [51] Suzuki, M. Solution and critical behavior of some ”three-dimensional” Ising models with a four-spin interaction. Phys. Rev. Lett. 1972, 28, 507–510.
  * [52] Hashizume, Y.; Suzuki, M. New random ordered phase in isotropic models with many-body interactions. Int. J. Mod. Phys. B 2011, 25, 73–82.
  * [53] Hashizume,Y.; Suzuki, M. Controlled randomness and frustration of the many-body interactions. Int. J. Mod. Phys. B 2011, 25, 3529–3538.
  * [54] Prem, A.; Haah, J.; Nandkishore, R. Glassy quantum dynamics in translation invariant fracton models. Phys. Rev. B 2017, 95, 155133.
  * [55] Pai, S.; Pretko, M. Fractons from confinement in one dimension. Phys. Rev. Research 2020, 2, 013094.


# On the Efficacy of Eviction Policy for Key-Value Constrained Generative
Language Model Inference

Siyu Ren
Shanghai Jiao Tong University, China
<EMAIL_ADDRESS>
&Kenny Q. Zhu
University of Texas at Arlington, USA
<EMAIL_ADDRESS>
The corresponding author.

###### Abstract

Large language models (LLMs) are notably cost-prohibitive to deploy in
resource-constrained environments due to their excessive memory and
computational demands. In addition to model parameters, the key-value cache is
also stored in GPU memory, growing linearly with batch size and sequence
length. As a remedy, recent works have proposed various eviction policies for
maintaining the overhead of key-value cache under a given budget. This paper
embarks on the efficacy of existing eviction policies in terms of importance
score calculation and eviction scope construction. We identify the deficiency
of prior policies in these two aspects and introduce RoCo, a robust cache
omission policy based on temporal attention scores and robustness measures.
Extensive experimentation spanning prefilling and auto-regressive decoding
stages validates the superiority of RoCo. Finally, we release EasyKV, a
versatile software package dedicated to user-friendly key-value constrained
generative inference. Code available at https://github.com/DRSY/EasyKV.

##  1 Introduction

Recent advancements in Large Language Models (LLMs) have demonstrated
outstanding proficiency in a wide range of text generation scenarios Thoppilan
et al. (2022); Wei et al. (2022); Wang et al. (2023); Sun et al. (2023); Wu et
al. (2024). Nevertheless, deploying LLMs is a notably costly undertaking
considering their tremendous parameter size and quadratic cost of attention
layers. Accordingly, model compression Frantar and Alistarh (2023); Xia et al.
(2023) and memory-efficient attention Dao et al. (2022b); Dao (2023)
techniques have emerged to tackle these challenges and achieved substantial
outcomes.

Figure 1: Illustration of KV cache eviction inside one attention layer ($L$ in
total). In this example, a single pair of key-value vectors are deleted (red
hatched areas) before appending the next token’s. Different heads ($H$ in
total) at model layers may evict at different positions.

Owning to the auto-regressive nature of LLM inference Vaswani et al. (2017);
Radford et al. (2019), the intermediate attention key-value vectors are also
required to be stored in memory to avoid redundant key-value projection in
future steps. The size of key-value cache (KV cache) depends on the
configuration of the attention layer, batch size, and sequence length, which
poses challenges in both memory footprint, I/O cost, and computation burden
given the increasingly upsoaring model scale and user requests. Variants like
multi-query attention and grouped-query attention Shazeer (2019); Ainslie et
al. (2023) reduce the size of the KV cache with fewer attention heads, but
cannot be directly applied to pre-trained LLMs without re-training.

In pursuit of flexible and training-free control over KV cache during LLM
inference, recent works Liu et al. (2023b); Zhang et al. (2023); Xiao et al.
(2023b); Oren et al. (2024) have investigated implementing KV cache with
eviction policy, where the key-value vectors of certain tokens are
strategically deleted from memory (see Figure 1). In this way, the size of the
KV cache can be maintained under a specified budget, leading to decreased
memory and computational overhead. Despite the claimed and empirically
observed reduction in KV cache, there still lacks a comprehensive comparative
analysis of these methods. This study aims to fill this gap and embarks on the
efficacy of existing eviction policies from a unified framework, which
decomposes an eviction policy into two design dimensions: importance score
calculation and eviction scope construction. The former characterizes how
important a pair of key-value vectors is to future generations, while the
latter determines which tokens are readily allowed to be evicted from the
cache We categorize existing eviction policies according to these two
dimensions. Following our preliminary analysis, we discover that the way
current methods calculate importance scores utilizing local statistics can
only weakly approximate that derived from global statistics (full KV cache
without eviction). Moreover, prior methods commonly construct the eviction
scope by only incorporating tokens outside of a local window, which we show
endure high sensitivity to window size.

In this paper, we propose RoCo, a Robust Cache omission policy based on local
attention scores and robustness measures. Specifically, we compute the
importance score of each in-cache token using averaged attention probability
from future tokens, and formulate the eviction scope using tokens with the
lowest variance of attention. RoCo exhibits significantly better consistency
with full KV cache counterpart and robustness to eviction scope size.

To evaluate the effectiveness of RoCo in terms of preserving the LLM’s
downstream performance, we perform experiments across both prefilling and
auto-regressive decoding stages at which cache eviction happens, spanning
tasks of language modeling, text summarization, context reconstruction, and
instruction following. Experimental results at different levels of KV cache
budget demonstrates that RoCo results in significantly better generation
quality compared to current methods judged by both automatic metrics and LLM-
based evaluator.

Our contributions are summarized as follows:

  * •

We systematically analyze current cache eviction policies from the dimensions
of importance score calculation and eviction scope construction, shedding
light on their limitations.

  * •

Based on our analysis, we introduce a robust cache omission policy named RoCo
and conduct a comprehensive evaluation to verify its effectiveness on
downstream tasks.

  * •

We open-source EasyKV, a versatile software package that supports key-value
constrained generative LLM inference with flexible configuration on cache
budget and eviction policy.

##  2 Background

In this section, we present necessary background about Transformer as well as
existing literature on addressing the memory and computational bottleneck of
Transformer-based LLMs.

###  2.1 Transformer-based LLMs

The input to a Transformer-based LLM is a sequence of tokens
$\bm{x}=(x_{1},...,x_{T})$, which is further processed by the embedding layer,
followed by a series of Transformer blocks composed of an attention block and
a feedforward block. The attention block is the only submodule where tokens at
different positions exchange information, necessitating the need for a key-
value cache during inference.

##### Attention Block

At the $l$-th layer, the input hidden states
$\bm{H}^{l-1}\in\mathbb{R}^{T\times d}$ is multiplied with three matrices
$\bm{W}_{q}^{l},\bm{W}_{k}^{l}$, and $\bm{W}_{v}^{l}$, producing
$\bm{Q}^{l}=\bm{H}^{l-1}\bm{W}_{q}^{l},\bm{K}^{l}=\bm{H}^{l-1}\bm{W}_{k}^{l},\bm{V}^{l}=\bm{H}^{l-1}\bm{W}_{v}^{l}$.
Then the scaled dot-product attention is performed as follows:

$\displaystyle\text{Attn}_{i}$
$\displaystyle=\text{Softmax}(\frac{\bm{Q}^{l}_{i}\cdot(\bm{K}_{i}^{l})^{\top}}{\sqrt{d^{\prime}}})\cdot\bm{V}_{i}^{l}$
(1) SDPA
$\displaystyle=\text{Concat}(\text{Attn}_{1},...,\text{Attn}_{H})\cdot\bm{W}_{o}^{l}$
(2)

where $H$ is the number of attention heads, $d^{\prime}=\frac{d}{H}$ is the
head dimension, and $\bm{W}_{o}^{l}$ is the output matrix.

##### Key-Value Cache

LLM inference follows an autoregressive fashion. During training, it masks the
upper triangular part of the attention matrix such that each token only sees
itself and previous tokens. At inference time, the common practice is to cache
the key-value vectors computed so far and append the newly computed ones into
the cache. At time step $T$, the key-value cache can be written as a tensor of
shape $(L,2,B,H,T,d^{\prime})$, where $L$ is the number of model layers and
$B$ is the batch size. It is evident that the size of the KV cache grows
linearly with respect to sequence length, potentially leading to excessive
memory and latency issues when dealing with long input or output.

###  2.2 Efficient LLMs

Recent years have witnessed a surge of studies attempting to optimize the
inference cost of LLMs from different (often orthogonal) perspectives.

One line of work follows the conventional model compression paradigm, aiming
to identify and remove redundancy from billions of model parameters. These
include tensor decomposition Dao et al. (2022a), weight pruning Frantar and
Alistarh (2023); Xia et al. (2023); Ashkboos et al. (2024), and quantization
Dettmers et al. (2022); Frantar et al. (2022); Xiao et al. (2023a). These
methods reduce the KV cache footprint by reducing the model dimension, layers,
and data precision.

Another line of work focuses on architectural design, aiming at reducing model
complexity from the ground up. Representatives include sparse attention
Transformers Child et al. (2019); Zaheer et al. (2020), linear attention
Transformers Wang et al. (2020); Choromanski et al. (2020); Qin et al. (2022),
and simplified attention variants Shazeer (2019); Ainslie et al. (2023). These
methods either completely eschew the $O(T)$ space complexity of KV cache size
or reduce the number of attention heads in exchange for a larger context
length.

Some recent efforts Liu et al. (2023b); Zhang et al. (2023); Oren et al.
(2024) pay attention to methods that maintain the memory usage of the KV cache
under a fixed budget without finetuning or architectural modifications to the
model. The shared tenet of these approaches is the discernment and retention
of key-value vectors that exert a significant influence on future generations.
This work follows this line of research, dissects the efficacy of existing
eviction policies, and introduces an improved policy with more consistent
importance score and robust eviction scope construction.

##  3 Problem Formulation

##### Standard Inference

Denote the input prompt to the LLM as $\bm{x}=(x_{1},x_{2},...,x_{T})$, the
standard generative inference process consists of two consecutive stages:
prefilling and auto-regressive decoding. The prefilling stage encodes the
input prompt $\bm{x}$ and produces the corresponding attention key matrix
$\bm{K}_{T}\in\mathbb{R}^{L\times H\times T\times d^{\prime}}$ and value
matrix $\bm{V}_{T}\in\mathbb{R}^{L\times H\times T\times d^{\prime}}$, where
$L$, $H$, $d^{\prime}$ represent the number of model layers, number of
attention heads, and per-head dimension, respectively. Afterward, the LLM
samples one token from its output distribution at each step conditioned on all
key-value states computed so far. The key-value matrices are updated by
appending the key-value vectors of this new token:

$\displaystyle x_{T+1}$ $\displaystyle\sim\text{LLM}(\cdot|x_{<=T})$ (3)
$\displaystyle\bm{K}_{T+1}$ $\displaystyle=\text{Concat}(\bm{K}_{T},K_{T+1})$
(4) $\displaystyle\bm{V}_{T+1}$
$\displaystyle=\text{Concat}(\bm{V}_{T},V_{T+1})$ (5)

where $K_{T+1}\in\mathbb{R}^{L\times H\times 1\times d^{\prime}}$,
$V_{T+1}\in\mathbb{R}^{L\times H\times 1\times d^{\prime}}$ are the key and
value vectors of $x_{T+1}$. The above process is repeated until the end of
sequence token is generated. Let $\tilde{\bm{x}}=(\bm{x},\bm{x}_{o})$ denote
the complete token sequence composed of input prompt $\bm{x}$ and output
$\bm{x}_{o}$, where the output sequence contains $N$ tokens. The peak cache
size during standard inference is therefore determined by the key-value matrix
$\\{\bm{K}_{T+N},\bm{V}_{T+N}\\}\in\mathbb{R}^{L\times H\times(T+N)\times
d^{\prime}}$.

##### Key-Value Constrained Inference

LLMs are typically deployed on hardware with constrained memory resources.
However, during standard generative inference, the size of the key-value cache
increases linearly with the total length of the sequence, potentially leading
to out-of-memory issues and the associated latency incurred by reading and
writing between High Bandwidth Memory (HBM) and Static Random Access Memory
(SRAM) Dao et al. (2022b).

To this end, recent studies have shifted toward key-value-constrained
inference as a more controllable inference scheme. Denoting the fixed budget
for each attention head as $B$ tokens, key-value constrained inference is to
maintain the key-value matrices $\bm{K}_{t}$ and $\bm{V}_{t}$ such that
$\bm{K}_{t}$, $\bm{V}_{t}\in\mathbb{R}^{L\times H\times n\times d^{\prime}}$
and $n\leq B$ for any $t\in\\{1,...,T+N\\}$.

##  4 Eviction Policy for Key-Value Constrained Inference

In practice, $\bm{K}_{t}$ and $\bm{V}_{t}$ are stored in a fixed memory buffer
with a maximum token budget $B$. When the buffer is full, an eviction policy
is executed to remove stored but non-influential tokens from the cache.
Although various eviction policies have been proposed, there still lacks a
systematic comparison of their working mechanisms, design choices, and
downstream performance.

To fill this gap, we embark on the efficacy of existing eviction policies from
a unified framework. Concretely, we represent an eviction policy as the
composition of two components: importance score calculation and eviction scope
construction, which we elaborate on in the following sections.

###  4.1 Importance Score Calculation

Importance score calculation plays a vital role in eviction policy. It
determines the relative order by which tokens are evicted. We summarize
existing importance score calculation methods as follows:
Random Deletion As a naive baseline, one can randomly choose the key-value
vectors to evict. We incorporate this method into comparison and let it serve
as the lower bound.
Recency This method deems the farthest token as least important and evicts it
when the buffer is full. It is also referred to as window attention in prior
studies Ainslie et al. (2020); Beltagy et al. (2020); Xiao et al. (2023b).
Accumlative Attention Score (AAS) $\text{H}_{\text{2}}$O Zhang et al. (2023)
maintains a $B$-sized record array that stores the accumulative attention
score each in-cache token received from subsequent tokens.
Accumlative Quantized Attention Score (AQAS) ScissorHands Liu et al. (2023b)
adopts an apporach similar to $\text{H}_{\text{2}}$O. The exception is that
the attention score is quantized into a binary value, with 1 indicating above
average and 0 indicating below average.
Last Token Attention Score (LTAS) TOVA Oren et al. (2024) uses last token’s
attention score as importance indicator.

###  4.2 Eviction Scope Construction

Due to the auto-regressive nature of LLMs, recent tokens in the cache
participate in less attention computation than earlier tokens. Therefore,
their recorded importance scores for some attention-based methods can be
underestimated and thus get wrongly evicted. To this end, an eviction scope
should be constructed to carefully select tokens allowed to be evicted.

The dominant mean of constructing eviction scope is local window, which
assumes that tokens outside of a local window of size $r$ have accumulated
sufficient information on their importance.

###  4.3 Preliminary Experiments

In our controlled preliminary experiments, we are interested in how different
importance score calculation methods behave in terms of consistency with
respect to their full KV cache version. After that, we also explore another
way of constructing eviction scope in addition to local window.

Figure 2: Consistency of different importance calculation methods w.r.t their
full KV cache variant.

##### Setup

We examine the Jaccard similarity between the top-$B$ important tokens derived
by various importance score calculation methods and those derived when a full
KV cache is available. The higher the similarity, the more effectively the
importance calculation method harnesses local information to approximate the
global one. We evaluate all attention-based methods (i.e., AAS, AQAS, and
LTAS) listed in Section 4.1 and set the local window size $r$ to 0. More
specifically, we use LLaMa2-7B-Chat111We also conduct experiments upon other
LLMs like WizardLM-7B, and similar results are observed. as the LLM and take
the 805 instructions from AlpacaEval Li et al. (2023) as prompt, generating a
response for each instruction via greedy decoding. For KV cache budget from
$\\{0.3,0.4,0.5,0.6\\}$, we compute the Jaccard similarity at each token
position, averaged over sequence length, attention heads, and layers.

##### Results

The results are shown in Figure 2. AAS shows a clear advantage over AQAS
across all budget rates, indicating the importance of a full-precision
attention score when the relative importance of tokens cannot be distinguished
via binary value. LTAS has higher consistency than AAS, which we attribute to
the fact that LTAS does not suffer from the recency bias that AAS and AQAS
exhibit due to the accumulation operation. However, LTAS computes importance
score based on a single token, which might bear high variability. Based on the
above results, we advocate the use of Mean Attention Score (MAS) to gauge the
importance of each token. MAS divides each token’s accumulative attention
score by how many times that token is attended by future tokens. As shown in
Figure 2, MAS has remarkably higher consistency among all methods, achieving
over 0.9 Jaccard similarity even at 0.3 cache budget rate. This verifies that
MAS effectively alleviates recency bias and can better retain high-influential
tokens.

Figure 3: Illustration of persistence of attention robustness. We extract
attention scores and compute the standard deviation from LLaMa2-7B-Chat.

##### Is Local Window the Optimal Way to Construct Eviction Scope?

The local window approach has been widely used in conjunction with attention-
based importance calculation methods to prevent recent tokens from being
evicted. The underlying rationale is that the accumulated attention score is
not sufficiently indicative until a specified threshold, i.e., the window size
$r$ is reached.

Based on the commendable consistency of MAS discussed in the previous
paragraph, here we propose another way to construct the eviction scope which
exploits a phenomenon termed persistence of attention robustness that we find
ubiquitously exists in large language models. It states that the standard
deviation of the attention probabilities a token receives from future tokens
typically undergoes a brief ascending phase before settling into a stable
decline, regardless of the model layer and attention head. Figure 3 clearly
illustrates the phenomenon. We also observe that the ascending phase of a non-
trivial portion of tokens only takes a relatively small number of steps, i.e.,
$\leq 50$, suggesting it might be sub-optimal to only consider tokens at least
$r$ steps away for eviction scope construction.

To this end, we propose a new way to construct the eviction scope utilizing
the standard deviation of attention scores. Concretely, we maintain another
$B$-sized array for each attention head, keep track of the accumulative
squared attention score, and compute the standard deviation of each in-cache
token $x$ using
$\text{Std}(x)=\sqrt{\frac{\text{Acc}^{\text{square}}(x)}{\text{Count}(x)}-(\frac{\text{Acc}(x)}{\text{Count}(x)})^{2}}$.
In practice, Acc, Acc${}^{\text{sqaure}}$, and Count are all $B$-sized tensor
and the standard deviation of all in-cache tokens are computed in parallel.
Then, instead of the most recent $r$ tokens, we exclude tokens having top-$r$
standard deviation from eviction scope and remove the key-value vectors
corresponding to the token with the lowest mean attention score.

Figure 4: Results of MAS paired with local window and standard deviation on
text summarization.

We validate the effectiveness of both eviction scopes on a news summarization
task with LLaMa2-7B-Chat and CNN/Daily Mail See et al. (2017) dataset. Since
summarization is a typical long-input-short-output task, we only perform KV
eviction at the prefilling stage with a 0.5 compression rate and compare the
output against the full KV cache version. Figure 4 shows the geometric mean of
ROUGE-1/2/L Lin (2004) and METEOR Banerjee and Lavie (2005) for eviction
scopes of different sizes. Standard deviation yields outputs with considerably
higher quality while being less sensitive to the size of the eviction scope.

##### RoCo

Combining mean attention score for importance score calculation and standard
deviation for eviction scope construction, we introduce RoCo as a Robust Cache
omission policy for key-value constrained generative LLM inference.

##  5 Comprehensive Evaluation

The goal of the eviction policy is to control the memory usage of key-value
cache under a fixed budget while retaining the generation quality of LLMs as
much as possible. In this section, we perform an empirical evaluation of the
effectiveness of various eviction policies by taking the generated output with
a full KV cache as the reference and comparing KV-restricted generations
against it.

###  5.1 Experiment Setup

We describe the experimental setup used throughout our evaluation, including
evaluation tasks, metrics, datasets, and compared eviction policies.

####  5.1.1 Tasks and Metrics

To broadly cover real-world use cases, we evaluate using four different types
of tasks: language modeling, abstractive text summarization, original context
reconstruction, and instruction following.

##### Language Modeling

Language modeling task assesses the ability of LLMs to predict the next token
given the preceding context. In the key-value-constrained scenario, a
successful eviction policy should be able to detect and remove KV cache of
unimportant tokens. Following prior works Han et al. (2023); Xiao et al.
(2023b); Oren et al. (2024), we adopt perplexity as the evaluation metric.

##### Abstractive Text Summarization

Abstractive summarization requires extracting the most salient information
provided in the input and generating a concise summary for it. Since the
summary is usually much shorter compared to the input, we only perform cache
eviction during the prefilling stage. We report BLEU Papineni et al. (2002),
ROUGE Lin (2004), and METEOR Banerjee and Lavie (2005) scores as the
evaluation metrics.

##### Original Context Reconstruction

Given the constrained incomplete key-value cache of an input document, the
task of original context reconstruction measures how well the limited KV cache
retains the essential information from the original context. BLEU and ROUGE
scores are used as evaluation metrics.

##### Instruction Following

Instruction following Wei et al. (2021) requires an LLM to generate a proper
response for a given user instruction. We apply KV cache eviction at the auto-
regressive decoding stage since the model output tends to be more verbose. In
addition to BLEU and ROUGE scores, we also opt for a pairwise comparison
paradigm to evaluate the generated responses against those generated by text-
davincci-003.

####  5.1.2 Datasets

We use the following datasets as the testbed for tasks described in Section
5.1.1.

##### OpenWebText

OpenWebText is an open-source replication of the WebText dataset from OpenAI.
We randomly sample 200 documents to form the test set for the language
modeling task.

##### XSum

Xsum Narayan et al. (2018) comprises BBC articles from the years 2010 to 2017,
encompassing a broad spectrum of topics.

##### CNN/Daily Mail

CNN/Daily Mail See et al. (2017) contains articles from the CNN and the Daily
Mail newspapers, representing a different distribution from XSum. We use this
dataset for both summarization and original context reconstruction.

##### AlpacaEval

AlpacaEval Li et al. (2023) is a model-based automatic evaluation benchmark
for instruction-following LLMs. It comprises 805 instructions spanning a
diverse range of scenarios.

####  5.1.3 Models

Following prior works Zhang et al. (2023); Oren et al. (2024), we employ
LLaMa2-7B-base for language modeling and LLaMa2-7B-Chat for the remaining
tasks. We also include WizardLM-7B Xu et al. (2023) as another strong
instruction-tuned LLM for tasks except for language modeling.

####  5.1.4 Compared Eviction Policies

| Importance Score | Eviction Scope
---|---|---
Random | - | -
StreamLLM | - | local window
ScissorHands | AQAS | local window
H${}_{\text{2}}$O | AAS | local window
TOVA | LTAS | -
RoCo | MAS | standard deviation
Table 1: Eviction policies considered in this paper. The definition of importance score and eviction scope are introduced in Section 4.1 and Section 4.2, respectively. Models | Methods | XSum | CNN/DM
---|---|---|---
BLEU | Meteor | R-1 | R-2 | R-L | BLEU | Meteor | R-1 | R-2 | R-L
LLaMa2-7B${}_{\text{chat}}$ | Random | 16.7 | 35.1 | 41.8 | 22.8 | 33.3 | 15.4 | 30.8 | 39.0 | 19.9 | 26.2
StreamLLM | 11.9 | 35.5 | 42.7 | 17.6 | 31.3 | 19.2 | 40.0 | 49.5 | 24.3 | 30.7
ScissorHands | 29.3 | 50.4 | 56.5 | 35.6 | 46.5 | 27.8 | 46.4 | 57.7 | 33.4 | 40.7
H${}_{\text{2}}$O | 37.3 | 55.8 | 62.2 | 44.2 | 54.2 | 31.1 | 47.6 | 58.9 | 36.8 | 43.7
TOVA | 20.5 | 42.4 | 48.9 | 26.9 | 39.9 | 21.5 | 41.7 | 53.1 | 27.4 | 34.8
RoCo | 43.4 | 60.5 | 65.0 | 48.6 | 57.8 | 33.2 | 49.3 | 61.1 | 39.2 | 46.0
WizardLM-7B | Random | 12.6 | 30.0 | 36.3 | 19.1 | 28.0 | 12.4 | 27.8 | 39.6 | 17.0 | 23.9
StreamLLM | 7.1 | 27.3 | 36.2 | 13.4 | 25.6 | 8.8 | 25.9 | 39.0 | 14.4 | 23.8
ScissorHands | 29.8 | 48.6 | 57.2 | 38.5 | 47.7 | 24.6 | 41.2 | 54.3 | 29.1 | 35.7
H${}_{\text{2}}$O | 30.5 | 50.2 | 57.6 | 40.8 | 49.7 | 27.7 | 43.3 | 56.4 | 32.5 | 39.2
TOVA | 15.0 | 36.2 | 46.1 | 23.9 | 34.8 | 14.5 | 32.7 | 45.9 | 19.4 | 27.9
RoCo | 35.7 | 56.6 | 61.4 | 45.5 | 53.7 | 30.2 | 45.9 | 59.1 | 35.6 | 42.4
Table 2: Performance of different eviction policies on abstractive text
summarization tasks at 0.5 KV cache rate.

We consider the following baseline eviction policies, with their importance
score calculation methods and eviction scope listed in Table 1:

  * •

Random: evicting a randomly selected key-value pair from the cache.

  * •

StreamLLM Xiao et al. (2023b): evicting the key-value pair corresponding to
the first token after 4 initial attention sink tokens.

  * •

ScissorHands Liu et al. (2023b): evicting the key-value pair corresponding to
the token with the smallest accumulative quantized attention score outside the
local window of size $r$.

  * •

H${}_{\text{2}}$O Zhang et al. (2023): evicting the key-value pair
corresponding to the token with the smallest accumulative attention score
outside of the local window of size $r$.

  * •

TOVA Oren et al. (2024): evicting the key-value pair corresponding to the
token with the smallest last token attention score.

####  5.1.5 Other Details

Our implementation is based on Pytorch Paszke et al. (2019) and HuggingFace
Transformers Wolf et al. (2020). To improve the stability of outputs produced
by LLMs, we employ greedy decoding for all generative tasks. For prefilling
stage eviction, we set budget size $B$ by multiplying input token length with
a compression rate (e.g., 0.5) and directly specify $B$ as some integer for
decoding stage eviction because the output length is unknown. The size of the
local window is set to half of the KV cache budget following
H${}_{\text{2}}$O, i.e. $r=B/2$.

Figure 5: Performance of different eviction policies on language modeling task based on LLaMa2-7B. Models | Methods | CNN/DM
---|---|---
BLEU | R-1 | R-L
LLaMa2-7B${}_{\text{chat}}$ | Random | 4.9 | 26.7 | 18.1
StreamLLM | 15.1 | 37.6 | 28.5
ScissorHands | 16.9 | 45.9 | 33.7
H${}_{\text{2}}$O | 20.8 | 50.6 | 40.7
TOVA | 11.2 | 43.1 | 30.3
RoCo | 28.1 | 57.7 | 49.2
WizardLM-7B | Random | 6.3 | 30.3 | 19.6
StreamLLM | 5.3 | 24.7 | 16.3
ScissorHands | 17.4 | 48.3 | 33.0
H${}_{\text{2}}$O | 20.8 | 50.8 | 38.5
TOVA | 12.5 | 41.7 | 27.7
RoCo | 29.0 | 58.9 | 47.5
Table 3: Performance of different eviction policies on context reconstruction task at 0.5 KV cache rate. Models | Methods | AlpacaEval
---|---|---
BLEU | ROUGE-1 | ROUGE-2 | ROUGE-L
LLaMa2-7B${}_{\text{chat}}$ | Random | 45.6 | 66.6 | 49.7 | 56.1
StreamLLM | 47.3 | 66.6 | 51.1 | 57.1
ScissorHands | 62.1 | 76.5 | 63.9 | 68.8
H${}_{\text{2}}$O | 63.0 | 77.5 | 65.7 | 69.9
TOVA | 60.1 | 75.3 | 63.8 | 68.3
RoCo | 66.3 | 79.7 | 68.1 | 72.5
WizardLM-7B | Random | 40.6 | 62.9 | 45.6 | 52.8
StreamLLM | 43.0 | 63.9 | 47.8 | 54.5
ScissorHands | 57.2 | 73.3 | 60.9 | 65.3
H${}_{\text{2}}$O | 58.6 | 74.1 | 62.1 | 66.8
TOVA | 59.6 | 75.0 | 63.1 | 68.0
RoCo | 62.2 | 76.4 | 64.5 | 69.5
Table 4: Performance of different eviction policies on AlpacaEval at 250-token
KV cache budget.

###  5.2 Main Results

Budget | StreamLLM | H${}_{\text{2}}$O | RoCo
---|---|---|---
200 | 72.0(-3.6) | 74.5(-1.1) | 75.2(-0.4)
250 | 72.9(-2.7) | 74.8(-0.8) | 75.5(-0.1)
Table 5: AlpacaEval win rates against text-davincci-003 judged by GPT-4.
Numbers in the parenthesis denote the performance drop compared to full KV
cache (500 token output length on average with 75.6 win rate).

##### Overview

We report the results of RoCo alongside compared baseline eviction policies on
language modeling, text summarization, original context reconstruction, and
instruction following tasks in Figure 5, Table 2, Table 4, and Table 3. It can
be seen that RoCo consistently outperforms previous methods by significant
margins across all tasks and models. The advantage of Roco is particularly
more evident at a low KV cache budget rate. As demonstrated in Figure 5, the
gap between Roco and the second best method H${}_{\text{2}}$O reaches 0.2 at
0.15 budget rate. We also notice that Roco yields larger improvements on
generative inference tasks compared to language modeling. This is because, in
generative tasks, future token predictions are dependent on previous model
generations, where minor errors can accumulate and lead to large divergence.
on the AlpacaEval benchmark, RoCo not only delivers the best overall
performance in conventional metrics like BLEU and ROUGE, but also achieves
comparable win rates as judged by GPT-4 (Table 5). In contrast,
H${}_{\text{2}}$O shows notable quality declines, and the gap is even larger
for StreamLLM. Overall, the experiment results validate the effectiveness of
Roco in terms of retaining model performance during key-value-constrained
inference.

##### Attention Matters for KV Eviction

As the only two policies that do not utilize attention-related information,
Random and StreamLLM show significantly inferior performance compared to
attention-based methods on all tasks. This observation aligns with the role of
key-value vectors in attention computation, where the attention score serves
natural indicator of token importance.

###  5.3 Discussion

##### Extension to Grouped-Query Attention (GQA)

GQA, along with its extreme case Multi-Query Attention (MQA) has gained
increasing adoption in powerful LLMs like Mistral Jiang et al. (2023). We
extend the attention-based eviction policy to GQA and MQA by taking the group-
wise averaged attention score and using it to update the importance score
according to Section 4.1. The results of Zephyr-7B Tunstall et al. (2023) in
Appendix A validate the effectiveness of our extension.

##### Overhead

An ideal eviction policy should avoid introducing much extra overhead since
LLMs are already memory and computational-intensive. The memory overhead
induced by Roco is $L\times H\times B\times 3$, which is negligible given the
reduced KV cache footprint $L\times 2\times H\times(S-B)\times d^{\prime}$,
where $S$ is the non-evicted full sequence length. Moreover, different from
the auto-regressive decoding stage which is I/O-bounded, the prefilling stage
is computation-bounded. However, prior policies usually evict one token every
time the cache is full and encode the next token, turning the prefilling stage
into I/O-bounded. To accelerate key-value constrained prompt encoding, RoCo
allows for performing evict-and-encode in a block-wise manner. The block size
$b$ controls the number of tokens being freed and encoded within one eviction
step. We examine the effect of block-wise eviction using LLaMa2-7B-Chat on
XSum summarization task. Table 6 shows that such block-wise eviction greatly
speeds up prefilling while retaining similar output quality as token-wise
eviction. More results are deferred to Appendix B due to space limit.

Block Size | BLEU | ROUGE-2 | Speed up
---|---|---|---
1 | 41.2 | 46.2 | 1.0x
2 | 41.1 | 46.3 | 2.0x
4 | 41.1 | 46.2 | 4.0x
8 | 40.4 | 45.5 | 8.0x
16 | 40.2 | 45.4 | 16.0x
Table 6: Summarization results of block-wise eviction using RoCo.

##### Integrated Package

Finally, we open-source EasyKV, a software package dedicated to key-value
constrained inference accompanying this research. It is designed to be fully
compatible with existing LLMs with different attention variants and enables
flexible configuration of diverse eviction policies, cache budgets, and
application scenarios.

##  6 Conclusion

This paper studies key-value restricted language model inference. To shed
light on the effectiveness of existing eviction policies, we conduct
comprehensive comparative analysis by decomposing eviction policy into
importance score calculation and eviction scope construction. We identify the
inconsistency and instability of prior policie and introduce RoCo, a robust
cache omission policy with improved downstream performance. We also release
EasyKV, the accompanying library for versatile key-value constrained LLM
inference.

## References

  * Ainslie et al. (2023) Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sanghai. 2023.  GQA: Training generalized multi-query transformer models from multi-head checkpoints.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 4895–4901, Singapore. Association for Computational Linguistics.
  * Ainslie et al. (2020) Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. 2020.  Etc: Encoding long and structured inputs in transformers.  _arXiv preprint arXiv:2004.08483_.
  * An et al. (2023) Chenxin An, Shansan Gong, Ming Zhong, Mukai Li, Jun Zhang, Lingpeng Kong, and Xipeng Qiu. 2023.  L-eval: Instituting standardized evaluation for long context language models.  _arXiv preprint arXiv:2307.11088_.
  * Ashkboos et al. (2024) Saleh Ashkboos, Maximilian L Croci, Marcelo Gennari do Nascimento, Torsten Hoefler, and James Hensman. 2024.  Slicegpt: Compress large language models by deleting rows and columns.  _arXiv preprint arXiv:2401.15024_.
  * Bai et al. (2023) Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. 2023.  Longbench: A bilingual, multitask benchmark for long context understanding.  _arXiv preprint arXiv:2308.14508_.
  * Banerjee and Lavie (2005) Satanjeev Banerjee and Alon Lavie. 2005.  METEOR: An automatic metric for MT evaluation with improved correlation with human judgments.  In _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_ , pages 65–72, Ann Arbor, Michigan. Association for Computational Linguistics.
  * Beltagy et al. (2020) Iz Beltagy, Matthew E Peters, and Arman Cohan. 2020.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_.
  * Child et al. (2019) Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. 2019.  Generating long sequences with sparse transformers.  _arXiv preprint arXiv:1904.10509_.
  * Choromanski et al. (2020) Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. 2020.  Rethinking attention with performers.  _arXiv preprint arXiv:2009.14794_.
  * Dao (2023) Tri Dao. 2023.  Flashattention-2: Faster attention with better parallelism and work partitioning.  _arXiv preprint arXiv:2307.08691_.
  * Dao et al. (2022a) Tri Dao, Beidi Chen, Nimit S Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, and Christopher Ré. 2022a.  Monarch: Expressive structured matrices for efficient and accurate training.  In _International Conference on Machine Learning_ , pages 4690–4721. PMLR.
  * Dao et al. (2022b) Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022b.  Flashattention: Fast and memory-efficient exact attention with io-awareness.  _Advances in Neural Information Processing Systems_ , 35:16344–16359.
  * Dettmers et al. (2022) Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. 2022.  Llm. int8 (): 8-bit matrix multiplication for transformers at scale.  _arXiv preprint arXiv:2208.07339_.
  * Frantar and Alistarh (2023) Elias Frantar and Dan Alistarh. 2023.  Massive language models can be accurately pruned in one-shot.  _arXiv preprint arXiv:2301.00774_.
  * Frantar et al. (2022) Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. 2022.  Gptq: Accurate post-training quantization for generative pre-trained transformers.  _arXiv preprint arXiv:2210.17323_.
  * Han et al. (2023) Chi Han, Qifan Wang, Wenhan Xiong, Yu Chen, Heng Ji, and Sinong Wang. 2023.  Lm-infinite: Simple on-the-fly length generalization for large language models.  _arXiv preprint arXiv:2308.16137_.
  * Jiang et al. (2023) Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_.
  * Li et al. (2023) Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. 2023.  Alpacaeval: An automatic evaluator of instruction-following models.  https://github.com/tatsu-lab/alpaca_eval.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Liu et al. (2023a) Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. 2023a.  Lost in the middle: How language models use long contexts.  _arXiv preprint arXiv:2307.03172_.
  * Liu et al. (2023b) Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. 2023b.  Scissorhands: Exploiting the persistence of importance hypothesis for llm kv cache compression at test time.  _arXiv preprint arXiv:2305.17118_.
  * Narayan et al. (2018) Shashi Narayan, Shay B. Cohen, and Mirella Lapata. 2018.  Don’t give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization.  _ArXiv_ , abs/1808.08745.
  * Oren et al. (2024) Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz. 2024.  Transformers are multi-state rnns.  _arXiv preprint arXiv:2401.06104_.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32.
  * Qin et al. (2022) Zhen Qin, Xiaodong Han, Weixuan Sun, Dongxu Li, Lingpeng Kong, Nick Barnes, and Yiran Zhong. 2022.  The devil in linear transformer.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 7025–7041, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * See et al. (2017) Abigail See, Peter J. Liu, and Christopher D. Manning. 2017.  Get to the point: Summarization with pointer-generator networks.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1073–1083, Vancouver, Canada. Association for Computational Linguistics.
  * Shazeer (2019) Noam Shazeer. 2019.  Fast transformer decoding: One write-head is all you need.  _arXiv preprint arXiv:1911.02150_.
  * Sun et al. (2023) Qiushi Sun, Zhangyue Yin, Xiang Li, Zhiyong Wu, Xipeng Qiu, and Lingpeng Kong. 2023\.  Corex: Pushing the boundaries of complex reasoning through multi-model collaboration.  _arXiv preprint arXiv:2310.00280_.
  * Thoppilan et al. (2022) Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. 2022.  Lamda: Language models for dialog applications.  _arXiv preprint arXiv:2201.08239_.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_.
  * Tunstall et al. (2023) Lewis Tunstall, Edward Beeching, Nathan Lambert, Nazneen Rajani, Kashif Rasul, Younes Belkada, Shengyi Huang, Leandro von Werra, Clémentine Fourrier, Nathan Habib, et al. 2023.  Zephyr: Direct distillation of lm alignment.  _arXiv preprint arXiv:2310.16944_.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Wang et al. (2020) Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. 2020.  Linformer: Self-attention with linear complexity.  _arXiv preprint arXiv:2006.04768_.
  * Wang et al. (2023) Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi. 2023.  Self-instruct: Aligning language models with self-generated instructions.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 13484–13508, Toronto, Canada. Association for Computational Linguistics.
  * Wei et al. (2021) Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le. 2021.  Finetuned language models are zero-shot learners.  _arXiv preprint arXiv:2109.01652_.
  * Wei et al. (2022) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. 2022\.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Wu et al. (2024) Zhiyong Wu, Chengcheng Han, Zichen Ding, Zhenmin Weng, Zhoumianze Liu, Shunyu Yao, Tao Yu, and Lingpeng Kong. 2024.  Os-copilot: Towards generalist computer agents with self-improvement.  _arXiv preprint arXiv:2402.07456_.
  * Xia et al. (2023) Mengzhou Xia, Tianyu Gao, Zhiyuan Zeng, and Danqi Chen. 2023.  Sheared llama: Accelerating language model pre-training via structured pruning.  _arXiv preprint arXiv:2310.06694_.
  * Xiao et al. (2023a) Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. 2023a.  Smoothquant: Accurate and efficient post-training quantization for large language models.  In _International Conference on Machine Learning_ , pages 38087–38099. PMLR.
  * Xiao et al. (2023b) Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. 2023b.  Efficient streaming language models with attention sinks.  _arXiv preprint arXiv:2309.17453_.
  * Xu et al. (2023) Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang. 2023.  Wizardlm: Empowering large language models to follow complex instructions.  _arXiv preprint arXiv:2304.12244_.
  * Zaheer et al. (2020) Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. 2020.  Big bird: Transformers for longer sequences.  _Advances in neural information processing systems_ , 33:17283–17297.
  * Zhang et al. (2023) Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. 2023.  H $\\_2$ o: Heavy-hitter oracle for efficient generative inference of large language models.  _arXiv preprint arXiv:2306.14048_.

##  Appendix A More Experimental Results

##### Prompt Template

For instruction-tuned/aligned LLMs used in the main experiments, we strictly
follow their system prompt used during training. Specifically, we list the
prompt template used for LLaMa2-7B/13B-Chat, WizardLM-7B, and Zephyr-7B as
follows:

  * •

LLaMa2-7B/13B-Chat: [INST] <<SYS>> You are a helpful, respectful and honest
assistant. Always answer as helpfully as possible, while being safe. Your
answers should not include any harmful, unethical, racist, sexist, toxic,
dangerous, or illegal content. Please ensure that your responses are socially
unbiased and positive in nature. If a question does not make any sense, or is
not factually coherent, explain why instead of answering something not
correct. If you don’t know the answer to a question, please don’t share false
information. <</SYS>> {instruction}[/INST]

  * •

WizardLM-7B: Below is an instruction that describes a task. Write a response
that appropriately completes the request. Instruction: {instruction} Response:

  * •

Zephyr-7B: <|system|> You are a friendly chatbot who always responds in a
helpful and detailed manner to the user’s questions.</s> <|user|>
{instruction}</s> <|assistant|>

##### Extension to GQA/MQA

We extend existing attention-based eviction policies into GQA and MQA by
taking the group-wise averaged attention scores and using it to update the
importance score. To verify our extension, we conduct experiments using
Zephyr-7B Tunstall et al. (2023), an instruction-tuned and aligned version of
Mistral-7B Jiang et al. (2023) on the text summarization task. Specifically,
Zephyr-7B employs GQA and has 8 key-value heads and 32 query heads, rendering
a 4x replication for each key-value vector pair.

The results are shown in Table 7. We can see that, attention-based eviction
policies still exhibit better performance compared to Random and StreamLLM,
showing that the group-wise average operation can effectively reflect the
importance of each token across all query heads within its group.

##### Results on Larger LLMs

In addition to 7B-scale LLMs, we also examine the effectiveness of RoCo
alongside other eviction policies on 13B-scale LLMs. To this end, we conduct a
text summarization experiment using LLaMa2-13B-Chat Touvron et al. (2023) and
report the results in Table 8. We observe that, given the same KV cache
budget, LLaMa2-13B-Chat achieves higher BLEU and ROUGE scores than
LLaMa2-7B-Chat. It indicates that a larger model dimension may contain more
redundancy in some less informative intermediate activations. This observation
is inspiring because it implies that we can preserve more performance when
using more powerful LLMs.

Models | Methods | XSum | CNN/DM
---|---|---|---
BLEU | Meteor | R-1 | R-2 | R-L | BLEU | Meteor | R-1 | R-2 | R-L
Zephyr-7B | Random | 17.0 | 39.0 | 48.6 | 25.2 | 34.4 | 22.8 | 43.2 | 54.5 | 29.0 | 36.1
StreamLLM | 12.0 | 35.0 | 45.1 | 19.3 | 29.0 | 20.2 | 41.2 | 51.8 | 26.1 | 31.9
ScissorHands | 26.6 | 48.7 | 57.4 | 34.3 | 44.2 | 29.4 | 49.1 | 60.4 | 36.0 | 44.0
H${}_{\text{2}}$O | 29.6 | 49.9 | 58.9 | 38.3 | 47.2 | 34.9 | 52.3 | 63.6 | 41.3 | 48.4
TOVA | 16.8 | 40.7 | 50.5 | 24.6 | 34.9 | 25.5 | 45.8 | 57.5 | 32.2 | 38.6
RoCo | 33.6 | 54.9 | 62.6 | 42.4 | 50.4 | 36.6 | 53.8 | 64.6 | 42.6 | 50.0
Table 7: Performance of Zephyr-7B using different eviction policies on abstractive text summarization tasks at 0.5 KV cache rate. Models | Methods | XSum | CNN/DM
---|---|---|---
BLEU | Meteor | R-1 | R-2 | R-L | BLEU | Meteor | R-1 | R-2 | R-L
LLaMa2-13B${}_{\text{Chat}}$ | Random | 14.9 | 27.7 | 30.0 | 17.9 | 24.5 | 9.0 | 18.8 | 22.3 | 11.7 | 15.1
StreamLLM | 14.7 | 35.7 | 41.7 | 19.8 | 31.2 | 26.0 | 43.1 | 53.2 | 30.4 | 36.6
H${}_{\text{2}}$O | 38.3 | 55.9 | 61.0 | 44.5 | 53.4 | 38.4 | 52.5 | 62.3 | 42.6 | 48.6
RoCo | 45.8 | 62.2 | 66.6 | 51.5 | 59.3 | 41.4 | 54.1 | 65.1 | 47.0 | 53.0
Table 8: Performance of LLaMa2-13B-Chat using different eviction policies on abstractive text summarization tasks at 0.5 KV cache rate. Block Size | BLEU | ROUGE-2 | Speed up
---|---|---|---
1 | 26.5 | 35.4 | 1.0x
2 | 26.6 | 35.4 | 2.0x
4 | 26.5 | 35.4 | 4.0x
8 | 26.9 | 35.8 | 8.0x
16 | 26.4 | 35.4 | 16.0x
Table 9: Performance of Zephyr-7B on text summarization using RoCo. Larger
block size only leads to a slight performance decline while significantly
speed-up the prefilling stage.

##  Appendix B More Results on Block-wise Eviction

To accelerate key-value constrained prompt encoding, we extend the per-token
evict-and-encode scheme to a block-wise manner. We report results on text
summarization with various block sizes using Zephyr-7B in Table 9. With a
larger block size, more tokens are evicted with less reliable importance
scores, thereby resulting in some influential tokens being wrongly evicted.
Nevertheless, the performance drop is tolerable given the significant speedup
of prompt encoding, especially when confronted with long-context tasks Liu et
al. (2023a); Bai et al. (2023); An et al. (2023).

##  Appendix C Case Study

To obtain a straightforward impression on the generation quality when RoCo is
applied for key-value constrained inference, we present responses generated by
LLaMa2-7B-Chat given the instruction “What are the names of some famous actors
that started their careers on Broadway?”. The responses at different KV cache
budget are shown in Figure 6. At 0.3 KV cache budget rate, RoCo generates a
response containing the same actor/actress names as the one conditioned on a
full KV cache, demonstrating the commendable ability of RoCo to selectively
retain useful key-value states and maintain coherent generation.

Figure 6: Case study of LLaMa2-7B-Chat generated response given a specific
instruction. The response generated with 30% KV cache using RoCo retains
almost all content in the original response.