# A Graph-Theoretic Analysis of Distributed Replicator Dynamic

Prashant Bansode, Aniket Deshpande, Navdeep Singh Prashant Bansode is with
Department of Instrumentation Engineering, Ramrao Adik Institute of
Technology, Mumbai, 400706 India<EMAIL_ADDRESS>Deshpande
and Navdeep Singh are with Department of Electrical Engineering, Veermata
Jijabai Technological Institute, Mumbai, 400019 India.

###### Abstract

This paper attempts to develop a graph-theoretic multi-agent perspective of
population games to study the “truncation” behavior. The proposed method
considers fitness of the population as a dynamical system to address the issue
of restrictive description of this behavior which pertains to the underlying
population dynamic. The fitness dynamic resembles an agreement protocol that
enables comments on the steady-state characteristics of the graph that
represents the population structure. The structural attributes of the
underlying graph and the truncation behavior are emphasized by exploiting the
spectral properties of the associated Laplacian matrix. The asymptotic
stability of the fitness agreement protocol has been shown to be sufficient in
concluding the stability of population dynamics. Simulation results validating
the proposed hypothesis have been discussed.

##  I Introduction

Evolutionary game theory has emerged from behavioral ecology, a field that
formally analyzes the influence of ecological factors on the evolution of
different species or populations in their behavioral contexts. Their evolution
pertains to how they revise strategies under certain protocols. The central
idea of evolutionary games is to model the evolution of the Nash equilibrium
(NE) of strategic form games using a set of differential equations that define
the strategy revision protocol. The population games belong to a class of
evolutionary games which model strategic interactions among the populations
with a key assumption that these populations only occasionally receive
opportunities to revise their strategies. It is apropos to consider [1, 2, 3,
4, 5] for a comprehensive literature survey on game theory. The literature on
evolutionary games, population games and various revision protocols is spanned
over last four decades [6, 7, 8, 9, 10, 11]; surveying this literature is
beyond the scope of this paper.

###  I-A Relevant literature

Population games have lately inspired a wide range of the distributed
optimization problem-solving techniques in multi-agent systems. A decently
recent work on the application of these games to multi-agent systems includes
[12, 13, 14, 15, 16, 17, 18, 19, 20]. An application of population games to a
certain class of cooperative control problems is demonstrated in [12]. Most of
the distributed optimization problems in multi-agent systems can be pursued as
dynamic resource allocation problems. To this end, researchers have sought to
exploit the distributed version of a strategy revision protocol known as
distributed replicator dynamic (DRD) [13, 14, 15, 16, 17, 18, 19, 20]. The DRD
overcomes the drawback of classic replicator dynamic by considering only
local-level mutual interactions among the neighboring agents. To elaborate
further, [14] demonstrates the application of the DRD to control the luminance
of several lighting zones with electrical power as a resource under
consideration. A similar but more appealing approach is considered in [15] for
optimal dispatch of distributed generators in a microgrid.

###  I-B Motivation

Authors’ interest in the graph-theoretic analysis of population games is
motivated by observation of the “truncation” behavior of agents [15]. The
truncation behavior occurs when the population-share associated with the agent
has fitness below the average fitness at equilibrium. The fitness may be
regarded as the payoff an agent receives for playing a particular
strategy[21]. If one considers a graph that depicts the structure of a finite
population in the game, then as the population-shares associated with
different agents undergo strategy revisions, the interconnection structure of
the graph gets significantly influenced. For example, the population-share
associated with an agent, can render it fit or unfit for survival, based on
its strategy being profitable or nonprofitable as observed by the revision
protocol.[21]. This scenario is theoretically explained in [15]. However, it
appears that the subject still lacks a detailed mathematical analysis.

In population games, an agent may refer to a strategy shared by a subset of
the total population. However, in context of the reported work, it is referred
to as the fitness associated with the corresponding subset of the population.
The population dynamic (distributed replicator dynamic in this case) does not
describe the evolution of fitness of the agents. Hence it is insufficient for
understanding how the agents converge to the agreement value. It only uses the
fitness function as an argument and describes the evolution of the population
state. As truncation is the behavior an agent may exhibit at a steady-state,
it is more appropriate to define the fitness dynamic to understand how this
behavior emerges. The proposed dynamic describes the evolution of the fitness
values. The approach of the reported work provides a graph-theoretic
explanation to the truncation behavior of the agents with a few more
contributions stated below.

###  I-C Contributions

The main objective of this paper is to seek an analytical rationale of the
“truncation” behavior of the agents using spectral properties of the graph
theory. To the best of authors’ knowledge, no significant contribution is seen
towards analyzing this behavior in population games by exploiting rich
spectral properties of the interaction graph of the game. The contributions of
the present work as follows:

  1. 1.

The formulation of the fitness dynamic of the agents and its realization as a
linear parameter-varying dynamic agreement protocol that allows analyzing
these games from the perspective of the multi-agent systems.

  2. 2.

Analysis of truncation behavior of the agents using spectral properties of the
graph-Laplacian matrix.

  3. 3.

A graph-theoretic approach to ensure the stability of the Nash equilibrium of
the potential games from a graph-theoretic perspective.

###  I-D Organization of the paper

The rest of the paper is organized as follows: Some preliminaries on graph
theory and potential games are presented in Section II. Section III explains
the network model of the distributed replicator dynamic and the fitness
agreement protocol. The sufficient conditions for the existence of solutions
of the distributed replicator dynamic and the fitness dynamic are presented in
Subsection III-D. Subsection III-E and Subsection III-H elaborate on the
existence of Nash equilibrium and its stability, respectively. Section IV
presents the simulation examples while Section V concludes the paper.

##  II Preliminaries

###  II-A Graph theory

An (undirected) graph $\mathcal{G}$ is defined by the couple
$\mathcal{G}=(\mathcal{N},\mathcal{E})$ with $n$ nodes (or agents)
$\mathcal{N}=\\{1,2,\ldots,n\\}$ and a number of edges in the set
$\mathcal{E}\subseteq\mathcal{N}\times\mathcal{N}$. The neighbor set of the
$i^{\rm th}$ node is
$\mathcal{N}_{i}=\\{j\in\mathcal{N}|(j,i)\in\mathcal{E}\\}$, where
$i\in\\{1,2,\ldots,n\\}$. The number of nodes $n$ is the cardinality of the
graph.

###  II-B Population games

A population game is characterized by a continuous vector-valued payoff
function $f=(f_{1},\dots,f_{n}):\Re^{n}_{+}\rightarrow\Re^{n}$. The agents of
the population game choose their strategies from a pure strategy set
$\mathcal{S}=\\{1,2,\ldots,n\\}$ and their aggregate behavior is described as
a population state $p(t)=\\{p_{1}(t),\ldots,p_{n}(t)\\}$ that belongs to a
simplex $\bigtriangleup$ for all $t\geq 0$ such that

$\bigtriangleup=\\{p(t)\in\Re^{n}_{+}:\sum_{i=1}^{n}p_{i}(t)=P_{\mathrm{tot}}\\},$
(1)

where $P_{\mathrm{tot}}$ is the total population of the game[21]. For the sake
of notational simplicity, here onwards the dependence on $t$ is dropped
wherever it is obvious. The scalar $p_{i}$ denotes the number of agents
choosing the pure strategy $i$ and $f_{i}$ denotes the payoff to strategy $i$.

Given a population game $f$, a Nash equilibrium $p^{*}$ of $f$ is defined as
given below[20, 21]:

###### Definition II.1

Given a population game $f$, the set of Nash equilibria is defined as follows:

$\displaystyle\begin{split}NE(f)=\\{p\in\bigtriangleup:p_{i}>0\implies
f_{i}(p)\geq f_{j}(p),\\\ \leavevmode\nobreak\ \forall
i,j\in\mathcal{S}\\}.\end{split}$ (2)

Further, $f$ is a potential game if there exists a continuously differentiable
potential function $V:\Re^{n}_{+}\rightarrow\Re$ such that $f(p)=\nabla V(p)$.
It is assumed that $V(p)$ is strictly quadratic concave, i.e.
$V(p)=-p^{T}Hp+b^{T}p+c$ with $H>0$. We replace “payoff” by “fitness”
throughout.

##  III Problem Formulation

This section first introduces the classic and distributed versions of the
replicator dynamic and proceeds towards the problem formulation and main
results of the paper.

###  III-A Replicator dynamic

The replicator dynamic is a strategy revision protocol which describes the
aggregate behavior of the agents through the evolution of the population state
$p(t)$. Assuming that there exists a network of agents such that each agent
receives a certain share of the total population $p$, then the classic
replicator dynamic describes how the population-shares associated with these
agents vary with respect to time. It is given by

$\dot{p}_{i}(t)=p_{i}(t)\,[f_{i}(p(t))-\bar{f}(p(t))],$ (3)

where the average fitness of the population is

$\bar{f}(p)=\frac{1}{P_{\rm tot}}\sum_{j=1}^{n}p_{j}f_{j}(p_{j}).$ (4)

According to (3), the population-share associated with the agent whose fitness
is above the average fitness tends to increase, while the population-share
associated with the agent whose fitness is below the average fitness tends to
decrease. Thus the total population stays constant.

###  III-B Network model of distributed replicator dynamic

Figure 1: An example of the interaction graph
$\mathcal{G}(\mathcal{N},{\mathcal{E}})$ of a finite population of the
potential game $f$.

Let an undirected graph $\mathcal{G}=\\{\mathcal{N},{\mathcal{E}}\\}$ depict a
network of agents as shown in the example of Fig. 1 such that each agent has a
nonzero population-share at $t=0$, where $\mathcal{N}$ denotes the set of
agents and $\mathcal{E}$ denotes the set of edges of the graph. Each agent in
the network is characterized by the population-share associated with it, which
receives a certain fitness for choosing a certain strategy. Henceforth, we
allow the fitness scalar to represent the agent wherever necessary. The
distributed version of the replicator dynamic (3) for the agent is given
by[22, 20]

$\dot{p}_{i}=\sum_{j\in\mathcal{N}_{i}}p_{i}p_{j}[f_{i}(p)-f_{j}(p)],$ (5)

where the difference of fitness between adjacent agents enters into play.

Note that the simplex introduced in (1) remains invariant under (3) and (5).

Introducing the Laplacian matrix $L(p)$ of the graph, i.e.

$L(p)=\begin{cases}l_{i,j}=-p_{i}p_{j},\forall(i,j)\in\mathcal{E},\\\
l_{i,j}=0,\forall(i,j)\not\in\mathcal{E},\\\
l_{i,i}=-\sum_{j\in\mathcal{N}_{i}}l_{i,j},\end{cases}$ (6)

where $|l_{i,j}|$ is treated as the weight of the edge connecting
$i^{\mathrm{th}}$ and $j^{\mathrm{th}}$ agents on the graph $\mathcal{G}$.
Below we write the dynamic (5) in a stacked form as

$\displaystyle\dot{p}=L(p)f(p)$ (7)

which represents the replicator dynamic of the population state $p(t)$. In
view of its definition, the Laplacian $L(p)$ is a parameter-varying, real and
symmetric matrix which is differentiable and uniformly continuous in $p$. As a
consequence, the following holds.

###### Statement 1

There exists $\Lambda>0$ such that the spectral norm $\|L(p)\|<\Lambda,\forall
p\in\bigtriangleup,\forall t\geq 0$.

###### Statement 2

The gradient of $L(p)$ with respect to $p$ is bounded above by some scalar
$\eta$, $\left\|\nabla L(p)\right\|\leq\eta,p\in\bigtriangleup.$

###  III-C Fitness agreement protocol

The fitness dynamic of the population is derived from the dynamic (7) as shown
below,

$\displaystyle\dot{f}(p)$ $\displaystyle=\nabla f(p)\dot{p},$
$\displaystyle=\nabla^{2}V(p)\dot{p},$ $\displaystyle=-HL(p)f(p),$
$\displaystyle=-M(p)f(p),$ (8)

where $M(p)=HL(p)$ is a positive semidefinite matrix, i.e. $M(p)\geq 0$ [see
Theorem 2.2,[23]]. Notice that $L(p)\boldsymbol{1_{n}}=0$ which implies
$M(p)\boldsymbol{1_{n}}=0$, where $\boldsymbol{1_{n}}\in\Re^{n\times 1}$ is a
vector containing all ones. That being the case the dynamic (8) attains a
steady state exactly when all fitnesses are equal. Hence the fitness dynamic
(8) resembles an agreement protocol[24].

###  III-D Existence and uniqueness of solution to fitness agreement protocol

There exists a unique solution to the dynamic (7)[21]. The Hessian matrix $H$
is bounded because $V(p)$ is continuously differentiable and $L(p)$ is also
bounded. Consequently, the fitness agreement protocol (8) has a unique
solution.

###  III-E Convergence of the DRD to the NE

The definition (II.1) straightforwardly extends to potential games, however,
for such games the NE is unique seeing that the potential function $V(p)$ is
strictly quadratic concave.

The convergence of the population state $p(t)$ to the NE of the potential game
may also be described from the graph-theoretic perspectives. In what follows,
we provide our main results that link the graph theory with the population
games and show that the existence of the NE $p^{*}$ is strongly associated
with the connectedness of the interaction graph $\mathcal{G}$.

###  III-F Main results: Part A

###### Lemma III.1

In the potential game $f$, all agents receive equal fitness if and only if
$\lambda_{2}(L(p(t)))>0,\forall t\geq 0$.

###### Proof:

Since the edge-weights $|l_{i,j}|$ are dynamic, for the graph $\mathcal{G}$ to
stay connected, one must ensure that $l_{i,j}<0,\forall
i,j\in\mathcal{E},\forall t\geq 0$. This condition can also be stated directly
in terms of the second smallest eigenvalue of $L(p(t))$[24]. Assuming that
$\mathcal{G}$ is initially connected, the necessary and sufficient condition
for $\mathcal{G}$ to stay connected throughout the game play is that
$\lambda_{2}(L(p(t)))>0,\forall t\geq 0$. $\lambda_{2}(L(p(t)))>0,\forall
t\geq 0$ ensures that $\lambda_{2}(M(p(t)))>0,\forall t\geq 0$ since $H>0$.
Hence, $\lambda_{2}(L(p(t)))>0,\forall t\geq 0$ is necessary and sufficient to
prove that the agreement protocol (8) converges to the agreement value. ∎

In line with the previous Lemma III.1, we derive the next result on the
convergence of the dynamic given in (7) to the NE of the game.

###### Theorem III.2

If $\lambda_{2}(L(p(t)))>0,\forall t\geq 0$ then the fixed point of the
dynamic (7) coincides with the NE $p^{*}$.

###### Proof:

Note $\lambda_{2}(L(p(t)))>0,\forall t\geq 0$ implies that all edges have non-
zero weights for all time. Since $l_{i,j}=-p_{i}(t)p_{j}(t)$, it further
implies that the population-shares associated with all agents remain non-zero
(i.e $p_{i}(t)>0,\forall t>0$). Secondly, as a consequence of Lemma III.1 and
the fact that $M(p)\boldsymbol{1_{n}}=0$, the dynamic (7) reaches a fixed
point, say $p^{s}$ that qualifies to be the NE $p^{*}$ of the potential game,
as mentioned in Definition (II.1). Hence proved. ∎

Lemma III.1 and Theorem III.2 provide the next corollary.

###### Corollary III.3

The condition $\lambda_{2}(L(p(t)))>0,\forall t\geq 0$ is a sufficient
condition for the fixed point $p^{s}$ to be the NE $p^{*}$ of the potential
game $f$.

A direct consequence of Corollary III.3 provides the following result.

###### Theorem III.4

Let

$\sigma^{0}=\\{\lambda_{k}(L(p^{s}))=0,\forall k=2,\ldots,n\\}$

for $p^{s}\not=p^{*}$, then $\sigma^{0}\not=\emptyset$ indicates the existence
of singleton graphs.

###### Proof:

It is obvious that $|\sigma^{0}|+1$ is the algebraic multiplicity of the
eigenvalue $\lambda_{1}(p)=0$, which is equal to the number of connected
components in $\mathcal{G}$. If $\lim_{t\rightarrow\infty}l_{i,j}=0$ for some
$(i,j)\in\mathcal{E}$ then there must be either
$\lim_{t\rightarrow\infty}p_{i}=0$ or $\lim_{t\rightarrow\infty}p_{j}=0$, or
both; which indicates that the population-share associated with either agent
$i$ or agent $j$, or both $i^{\mathrm{th}}$ and $j^{\mathrm{th}}$ agents tend
to decline. Let $\mathcal{K}$ be a set of such agents then there must be
$|\mathcal{K}|\leq|\sigma^{0}|$ number of isolated agents in the graph
$\mathcal{G}$. These isolated agents represent singleton graphs. Hence proved.
∎

###  III-G Observations on truncation behavior of agents:

This subsection is in line with the truncation behavior discussed in [15].
Here we introduce the singleton graphs which lie at the center of the
truncation phenomenon. Let $\mathcal{G}^{c}\in\mathcal{K},\forall
c=1,\ldots,|\mathcal{K}|$ be singleton graphs as defined earlier. If
$f_{i}(p^{s})$ is a fitness corresponding to the population-share
$p^{s}_{i}=0$ for some $i\in\mathcal{N}$ then we have two following cases.

#### Case 3.1. When agent $f_{i}(p^{s})$ is an end-point of
$\mathcal{G}(\mathcal{N},{\mathcal{E}})$

The population-share $p^{s}_{i}=0$ implies that eventually $l_{i,j}=0,\forall
j\in\mathcal{N}_{i}$ or $\mathcal{N}_{i}=\emptyset$, following which
$\mathcal{G}_{c}=\\{f_{i}(p^{s})\\}$. Since $f_{i}(p^{s})$ is being the end-
point in $\mathcal{G}(\mathcal{N},{\mathcal{E}})$, its isolation renders the
connectedness of the remaining part of $\mathcal{G}$ unaffected i.e., as shown
in the example of Fig. 2.

Figure 2: Interaction graph $\mathcal{G}(\mathcal{N},\mathcal{E})$ from Fig. 1
depicting Case 3.1: Agent $f_{8}$ is an end-point. Figure 3: Interaction graph
$\mathcal{G}(\mathcal{N},\mathcal{E})$ from Fig. 1 depicting Case 3.2: Agent
$f_{4}$ is a cut-point.

#### Case 3.2. When agent $f_{i}(p^{s})$ is the cut-point of
$\mathcal{G}(\mathcal{N},{\mathcal{E}})$

This scenario is depicted in Fig. 3, if the agent $i$ holds the position in
$\mathcal{G}$ such that
$\mathcal{G}^{\prime}\cap\mathcal{G}^{\prime\prime}=\\{f_{i}(p^{s})\\}$ for
any two components, say $\mathcal{G^{\prime}}$, and
$\mathcal{G^{\prime\prime}}$ in $\mathcal{G}$; then the edges that have
isolated $f_{i}(p^{s})$ also separate $\mathcal{G^{\prime}}$ and
$\mathcal{G^{\prime\prime}}$ from each other.

###  III-H Stability analysis of dynamics (7) and (8)

Here we show that the stability of the fitness agreement protocol (8) and the
dynamic (7) share a common platform. Before proceeding further, it is worth
considering certain notions of the dynamic (7) [11] stated subsequently.

  1. 1.

Positive Correlation (PC):

$\dot{p}(t)\neq 0\implies\dot{p}(t)^{T}f(p)>0.$ (9)

  2. 2.

Nash Stationarity (NS):

$\dot{p}(t)=0\Longleftrightarrow p\in NE(f).$ (10)

Conditions (9) and (10) strongly imply that the potential function $V(p)$
attains the maximum at $p^{*}$. The asymptotic stability of the NE $p^{*}$ of
the potential game is bound by these conditions as stated in [11]. A similar
approach has been considered for the asymptotic stability of the distributed
replicator dynamic in [20]. The analysis considers that the graph is
connected. In essence, the stability analysis is restricted to only $p^{*}$.
However, it does not imply that the distributed replicator dynamic has an
unstable equilibrium state when the graph loses the connectivity. In this
scenario, it is more convincing to analyze the stability of the fitness
agreement protocol (8) instead of the dynamic (7). In what follows, we intend
to prove that the stability of the fitness agreement protocol (8) implies the
stability of the dynamic (7).

####  III-H1 Main results: Part B

###### Theorem III.5

Let $W(p):\Re^{n}\times\Re\rightarrow\Re_{\geq 0}$ be a candidate Lyapunov
function chosen such that $\dot{W}(p)\leq-\lambda_{2}(L(p))f^{T}(p)f(p)$ then
the fitness agreement protocol (8) is asymptotically stable.

###### Proof:

Since $H$ is a symmetric positive definite matrix, it is invertible. Let the
candidate Lyapunov function for the system (8) be,

$W(p)=\frac{1}{2}f^{T}(p)H^{-1}f(p).$ (11)

Differentiating (11) along the trajectories of the fitness vector yields,

$\displaystyle\dot{W}(p)=-f^{T}(p)L(p)f(p).$ (12a)

Now, if the graph $\mathcal{G}$ remains connected $\forall t\geq 0$, then we
have

$f^{T}(p)L(p)f(p)\geq\lambda_{2}(L(p))f^{T}(p)f(p).$

Using this inequality in (12a), we get

$\displaystyle\dot{W}(p)\leq-\lambda_{2}(L(p))f^{T}(p)f(p).$ (13)

Hence proved. ∎

###### Theorem III.6

The asymptotic stability of the fitness dynamic (8) implies the asymptotic
stability of the dynamic (7) and vice versa.

###### Proof:

The proof simply follows from the equation (12a). We have,

$\displaystyle\dot{W}(p)$ $\displaystyle=$
$\displaystyle-f^{T}(p)\\{L(p)f(p)\\},$ (14a) $\displaystyle=$
$\displaystyle-f^{T}(p)\dot{p},$ (14b) $\displaystyle\leq$ $\displaystyle 0.$
(14c)

Comparing the equation (14b) to the inequality (10), we assert that the
positive correlation holds between $f^{t}(p)$ and $\dot{p}$, and along with
the condition $\lambda_{2}(L(p(t)))>0,\forall t\geq 0$, the Nash stationarity
also holds. Hence, the dynamic (7) is also asymptotically stable. Hence
proved. ∎

###### Corollary III.7

Every connected component in $\mathcal{G}$ exhibits asymptotically stable
dynamics.

###### Proof:

If $p^{s}\not=p^{*}$ then there exist $|\sigma^{0}|$ connected components in
$\mathcal{G}$ and each connected component, i.e.
$\mathcal{G}_{q},\leavevmode\nobreak\ \forall q=1,\ldots,|\sigma^{0}|$ has an
associated Laplacian $L_{q}(p)$; owing to which the graph-Laplacian $L(p)$
assumes a block diagonal form:

$L(p)=\left(\begin{array}[]{ccccc}L_{1}(p)&\hfill\hfil&\hfill\hfil&\hfill\hfil&\hfill\hfil\\\
\hfill\hfil&L_{2}(p)&\hfill\hfil&\hfill\hfil&\hfill\hfil\\\
\hfill\hfil&\hfill\hfil&\ddots&\hfill\hfil&\hfill\hfil\\\
\hfill\hfil&\hfill\hfil&\hfill\hfil&L_{|\sigma^{0}|-1}(p)&\hfill\hfil\\\
\hfill\hfil&\hfill\hfil&\hfill\hfil&\hfill\hfil&L_{|\sigma^{0}|}(p)\\\
\end{array}\right).$ (15)

Apparently, each connected component has a $0$ eigenvalue of algebraic
multiplicity equal to 1. Also, each $\mathcal{G}$ has a subset of agents
having their population and fitness dynamics. In line with this, the stability
analyses discussed in Theorems III.5 and III.6 readily apply to the connected
components in $\mathcal{G}$. ∎

##  IV Simulation results

All simulations are performed using the MATLAB-SIMULINK software. The
population graphs are plotted using “wgPlot.m” and “gplotwl.m” matlab
routines. We first consider a population dynamic of 5 agents. A simple
nearest-neighbor interconnection is considered as shown in Fig. 4. Initially,
the total population is equally distributed among all agents
($p_{i}(0)=0.2,\forall i\in\mathcal{N}$), owing to which all the edges
initially have equal weights as indicated by the blue color associated with
them. The vertical color map indicates the weight associated with each agent
i.e., the value of the fitness scalar which is also correlated with the size
of its dot. Initially, the fitness scalar have been assigned different
weights. As fitness agreement protocol evolves, all fitness scalars except
$f_{5}$ converge to the agreement value as can be seen from Fig. 5. It is due
to the fact that the population state $p_{5}$ belonging to the
$5^{\mathrm{th}}$ agent tends to decline and eventually goes to 0 as shown in
Fig. 6. This results in removal of the edges $|l_{1,5}|$ and $|l_{4,5}|$ as
reflected in Fig. 8. As a consequence of the this, at a steady state, the
graph $\mathcal{G}$ comprises two connected components, i.e. the one that
retains the agents $f_{1}$ to $f_{4}$ and the other one being singleton graph
that contains $f_{5}$. Fig. 9 confirms the existence of 2 connected components
in $\mathcal{G}$. The population structure at the steady state is manifested
in Fig. 10 wherein the edge-weights are associated with specific color shades
on the horizontal color map whose numeric values are also indicated alongside
the respective edges. Fig. 7 verifies that the simplex (1) remains invariant.

In a similar way, we also consider a random network of 20 agents as shown in
Fig. 11. Initially, the total population is equally distributed among all
agents and the fitness scalars are calculated to have different values. The
connected components in $\mathcal{G}$ are highlighted by boxed regions in Fig.
12, the graph comprises 2 connected components and 9 isolated agents.

Figure 4: The graph $\mathcal{G}$ consisting 5 agents at time $t_{0}$. Figure
5: Evolution of fitness of the agents on the graph $\mathcal{G}$ from Fig. 4.
Figure 6: Evolution of population of the agents on the graph $\mathcal{G}$
from Fig. 4. Figure 7: Invariance of population of the agents on the graph
$\mathcal{G}$ from Fig. 4. Figure 8: Evolution of the edges of the graph
$\mathcal{G}$ from Fig. 4. Figure 9: Evolution of eigenvalues of the Laplacian
$L(p)$ of the graph $\mathcal{G}$ from Fig. 4. Figure 10: The graph
$\mathcal{G}$ from Fig. 4 at steady state. Figure 11: The graph $\mathcal{G}$
consisting 20 agents at time $t_{0}$. Figure 12: The graph $\mathcal{G}$ from
Fig. 11 at steady state.

##  V Conclusions

A macroscopic behavior of the distributed replicator dynamic is analyzed using
graph theory. The fitness dynamic is shown to resemble a linear parameter-
varying dynamic agreement protocol. A comprehensive analysis of truncation
behavior in the distributed replicator dynamic is put forth using spectral
graph theory. It is proved that the existence and asymptotic stability of the
Nash equilibrium of the population games are dependent on the eigenvalue
spectrum of the graph-Laplacian matrix of the underlying network. Also, it is
shown that with a right choice of a Lyapunov function for the fitness dynamic;
the asymptotic stability of the fitness dynamic implies the asymptotic
stability of the distributed replicator dynamic.

## References

  * [1] John Von Neumann and Oskar Morgenstern.  Theory of games and economic behavior (commemorative edition).  Princeton university press, 2007.
  * [2] John Nash.  Non-cooperative games.  Annals of mathematics, pages 286–295, 1951.
  * [3] Tamer Basar and Geert Jan Olsder.  Dynamic noncooperative game theory, volume 23.  Siam, 1999.
  * [4] Y Narahari.  Game Theory and Mechanism Design, volume 4.  World Scientific, 2014.
  * [5] Alain Haurie, Jacek B Krawczyk, and Georges Zaccour.  Games and dynamic games, volume 1.  World Scientific Publishing Company, 2012.
  * [6] J Maynard Smith.  The theory of games and the evolution of animal conflicts.  Journal of theoretical biology, 47(1):209–221, 1974.
  * [7] Peter D Taylor and Leo B Jonker.  Evolutionary stable strategies and game dynamics.  Mathematical biosciences, 40(1-2):145–156, 1978.
  * [8] Jörgen W Weibull.  Evolutionary game theory.  MIT press, 1997.
  * [9] Josef Hofbauer and Karl Sigmund.  Evolutionary game dynamics.  Bulletin of the American Mathematical Society, 40(4):479–519, 2003\.
  * [10] Josef Hofbauer and William H Sandholm.  Stable games and their dynamics.  Journal of Economic theory, 144(4):1665–1693, 2009.
  * [11] William H Sandholm et al.  Population games and deterministic evolutionary dynamics.  Handbook of game theory, 4:703–778, 2015.
  * [12] Jason R Marden, Gürdal Arslan, and Jeff S Shamma.  Cooperative control and potential games.  IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 39(6):1393–1407, 2009.
  * [13] Eduardo Ramirez-Llanos and Nicanor Quijano.  A population dynamics approach for the water distribution problem.  International Journal of Control, 83(9):1947–1964, 2010.
  * [14] Andrés Pantoja and Nicanor Quijano.  Distributed optimization using population dynamics with a local replicator equation.  In Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, pages 3790–3795. IEEE, 2012.
  * [15] Andrés Pantoja, Nicanor Quijano, and Kevin M Passino.  Dispatch of distributed generators using a local replicator equation.  In Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, pages 7494–7499. IEEE, 2011.
  * [16] Julian Barreiro-Gómez, Nicanor Quijano, and Carlos Ocampo-Martinez.  Constrained distributed optimization based on population dynamics.  In Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on, pages 4260–4265. IEEE, 2014.
  * [17] Eduardo Mojica-Nava, Carlos Andrés Macana, and Nicanor Quijano.  Dynamic population games for optimal dispatch on hierarchical microgrid control.  IEEE Transactions on Systems, Man, and Cybernetics: Systems, 44(3):306–317, 2014.
  * [18] German Obando, Andres Pantoja, and Nicanor Quijano.  Building temperature control based on population dynamics.  IEEE Transactions on Control Systems Technology, 22(1):404–412, 2014.
  * [19] A. Pashaie, L. Pavel, and C. J. Damaren.  Population dynamics approach for resource allocation problems.  In 2015 American Control Conference (ACC), pages 5231–5237, July 2015.
  * [20] Julian Barreiro-Gomez, Germán Obando, and Nicanor Quijano.  Distributed population dynamics: Optimization and control applications.  IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016\.
  * [21] William H Sandholm.  Population games and evolutionary dynamics.  MIT press, 2010.
  * [22] Germán Darío Obando Bravo.  Distributed methods for resource allocation: a passivity based approach.  PhD thesis, Ecole des Mines de Nantes, 2015.
  * [23] Pei Yuan Wu.  Products of positive semidefinite matrices.  Linear Algebra and Its Applications, 111:53–61, 1988.
  * [24] Mehran Mesbahi and Magnus Egerstedt.  Graph theoretic methods in multiagent networks.  Princeton University Press, 2010.


capbtabboxtable[][]

# How do Language Models Bind Entities in Context?

Jiahai Feng & Jacob Steinhardt
UC Berkeley Correspondence to<EMAIL_ADDRESS>
###### Abstract

To correctly use in-context information, language models (LMs) must bind
entities to their attributes. For example, given a context describing a “green
square” and a “blue circle”, LMs must bind the shapes to their respective
colors. We analyze LM representations and identify the binding ID mechanism: a
general mechanism for solving the binding problem, which we observe in every
sufficiently large model from the Pythia and LLaMA families. Using causal
interventions, we show that LMs’ internal activations represent binding
information by attaching binding ID vectors to corresponding entities and
attributes. We further show that binding ID vectors form a continuous
subspace, in which distances between binding ID vectors reflect their
discernability. Overall, our results uncover interpretable strategies in LMs
for representing symbolic knowledge in-context, providing a step towards
understanding general in-context reasoning in large-scale LMs.

##  1 Introduction

Modern language models (LMs) excel at many reasoning benchmarks, suggesting
that they can perform general purpose reasoning across many domains. However,
the mechanisms that underlie LM reasoning remain largely unknown (Räuker et
al., 2023). The deployment of LMs in society has led to calls to better
understand these mechanisms (Hendrycks et al., 2021), so as to know why they
work and when they fail (Mu & Andreas, 2020; Hernandez et al., 2021; Vig et
al., 2020b).

In this work, we seek to understand _binding_ , a foundational skill that
underlies reasoning. How humans solve binding, i.e. recognize features of an
object as bound to that object and not to others, is a fundamental problem in
psychology (Treisman, 1996). Here, we study binding in LMs.

Binding arises any time the LM has to reason about two or more objects of the
same kind. For example, consider the following passage involving two people
and two countries:

  * Context: Alice lives in the capital city of France. Bob lives in the capital city of Thailand.

Question: Which city does Bob live in? (1)

In this example the LM has to represent the associations lives(Alice, Paris)
and lives(Bob, Bangkok). We call this the _binding problem_ —for the predicate
lives, Alice is bound to Paris and Bob to Bangkok. Since predicates are bound
in-context, binding must occur in the activations, rather than in the weights
as with factual recall (Meng et al., 2022). This raises the question: how do
LMs represent binding information in the context such that they can be later
recalled?

Overall, our key technical contribution is the identification of a robust
general mechanism in LMs for solving the binding problem. The mechanism relies
on _binding IDs_ , which are abstract concepts that LMs use internally to mark
variables in the same predicate apart from variables in other predicates (Fig.
1). Using causal mediation analysis we empirically verify two key properties
of the binding ID mechanism (Section 3).

Turning to the structure of binding IDs, we find that binding IDs are
represented as vectors which are bound to variables by simple addition
(Section 4). Further, we show that binding IDs occupy a subspace, in the sense
that linear combinations of binding IDs are still valid binding IDs, even
though random vectors are not.

Lastly, we find that binding IDs are ubiquitous and transferable (Section 5).
They are used by every sufficiently large model in the LLaMA (Touvron et al.,
2023) and Pythia (Biderman et al., 2023) families, and their fidelity
increases with scale. They are used for a variety of synthetic binding tasks
with different surface forms, and binding vectors from one task transfer to
other tasks. Finally, we qualify our findings by showing that despite their
ubiquity, binding IDs are not universal: we exhibit a question-answering task
where an alternate mechanism, “direct binding”, is used instead.

Figure 1: The Binding ID mechanism. The LM learns abstract binding IDs (drawn
as triangles or squares) which distinguish between entity-attribute pairs.
Binding functions $\Gamma_{E}$ and $\Gamma_{A}$ bind entities and attributes
to their abstract binding ID, and store the results in the activations. To
answer queries, the LM identifies the attribute that shares the same binding
ID as the queried entity.

##  2 Preliminaries

In this section we define the binding task and explain causal mediation
analysis, our main experimental technique.

Binding task. Formally, the binding task consists of a set of entities
$\mathcal{E}$ and a set of attributes $\mathcal{A}$. An $n$-entity instance of
the binding task consists of a context that is constructed from $n$ entities
$e_{0},\dots,e_{n-1}\in\mathcal{E}$ and $n$ attributes
$a_{0},\dots,a_{n-1}\in\mathcal{A}$, and we denote the corresponding context
as $\mathbf{c}=\operatorname{ctxt}(e_{0}\leftrightarrow
a_{0},\dots,e_{n-1}\leftrightarrow a_{n-1})$. For a context $\mathbf{c}$, we
use $E_{k}(\mathbf{c})$ and $A_{k}(\mathbf{c})$ to denote the $k$-th entity
and the $k$-th attribute of the context $\mathbf{c}$, for $k\in[0,n-1]$. We
will drop the dependence on $\mathbf{c}$ for brevity when the choice of
$\mathbf{c}$ is clear from context.

In the capitals task, which is the main task we study for most of the paper,
$\mathcal{E}$ is a set of single-token names, and $\mathcal{A}$ is a set of
single-token countries. Quote 1 is an example instance of the capitals task
with context $\mathbf{c}=\operatorname{ctxt}(Alice\leftrightarrow
France,Bob\leftrightarrow Thailand)$. In this context, $E_{0}$ is $Alice$,
$A_{0}$ is $France$, etc.

Given a context $\mathbf{c}$, we are interested in the model’s behavior when
queried with each of the $n$ entities present in $\mathbf{c}$. For any
$k\in[0,n-1]$, when queried with the entity $E_{k}$ the model should place
high probability on the answer matching $A_{k}$. In our running example, the
model should predict “Paris” when queried with “Alice”, and “Bangkok” when
queried with “Bob”.

To evaluate a model’s behavior on a binding task, we sample $N=100$ contexts.
For each context $\mathbf{c}$, we query the LM with every entity mentioned in
the context, which returns a vector of log probabilities over every token in
the vocabulary. The mean log prob metric measures the mean of the log
probability assigned to the correct attribute token. Top-1 accuracy measures
the proportion of queries where the correct attribute token has the highest
log probability out of all attribute tokens. However, we will instead use the
median-calibrated accuracy (Zhao et al., 2021), which calibrates the log
probabilities with the median log probability before taking the top-1
accuracy. We discuss this choice in Appendix A.

Figure 2:  a) Causal diagram for autoregressive LMs. From input context
$\operatorname{ctxt}(e_{0}\leftrightarrow a_{0},e_{1}\leftrightarrow a_{1})$,
the LM constructs internal representations $Z_{\text{context}}$. We will
mainly study the components of $Z_{\text{context}}$ boxed in blue. b) A
secondary run of the LM on context $\operatorname{ctxt}(e_{2}\leftrightarrow
a_{2},e_{3}\leftrightarrow a_{3})$ to produce $Z_{\text{context}}^{\prime}$.
c) An example intervention where $Z_{\text{context}}$ is modified by replacing
$Z_{A_{0}}\rightarrow Z_{A_{0}}^{\prime}$ from $Z_{\text{context}}^{\prime}$.

Causality in autoregressive LMs. We utilize inherent causal structure in
autoregressive LMs. Let an LM have $n_{\text{layers}}$ transformer layers and
a $d_{\text{model}}$-dimensional activation space. For every token position
$p$, we use $Z_{p}\in\mathbb{R}^{n_{\text{layers}}\times d_{\text{model}}}$ to
denote the stacked set of internal activations111These are the pre-transformer
layer activations, sometimes referred to as the residual stream. at token $p$
(see Fig. 2a). We refer to the collective internal activations of the context
as $Z_{\text{context}}$. In addition, we denote the activations at the token
for the $k$-th entity as $Z_{E_{k}}$, and the $k$-th attribute as $Z_{A_{k}}$.
We sometimes write $Z_{A_{k}}(\mathbf{c}),Z_{\text{context}}(\mathbf{c})$,
etc. to make clear the dependence on the context $\mathbf{c}$.

Fig. 2a shows that $Z_{\text{context}}$ contains all the information about the
context that the LM uses. We thus study the structure of $Z_{\text{context}}$
using causal mediation analysis, a widely used tool for understanding neural
networks (Vig et al., 2020a; Geiger et al., 2021; Meng et al., 2022). Causal
mediation analysis involves substituting one set of activations in a network
for another, and we adopt the $/.$ notation (from Mathematica) to denote this.
For example, for activations $Z_{*}\in\mathbb{R}^{n_{\text{layers}}\times
d_{\text{model}}}$, and a token position $p$ in the context,
$Z_{\text{context}}/.\\{Z_{p}\rightarrow
Z_{*}\\}=[Z_{0},\dots,Z_{p-1},Z_{*},Z_{p+1},\dots]$. Similarly, for a context
$\mathbf{c}=\operatorname{ctxt}(e_{0}\leftrightarrow
a_{0},\dots,e_{n-1}\leftrightarrow a_{n-1})$, we have
$\mathbf{c}/.\\{E_{k}\rightarrow
e_{*}\\}=\operatorname{ctxt}(e_{0}\leftrightarrow
a_{0},\dots,e_{*}\leftrightarrow a_{k},\dots,e_{n-1}\leftrightarrow a_{n-1})$.

Given a causal graph, causal mediation analysis determines the role of an
intermediate node by experimentally intervening on the value of the node and
measuring the model’s output on various queries. For convenience, when the
model answers queries in accordance to a context $\mathbf{c}$, we say that the
model believes222We do not claim or assume that LMs actually have beliefs in
the sense that humans do. This is a purely notational choice to reduce
verbosity. $\mathbf{c}$. If there is no context consistent with the language
model’s behavior, then we say that the LM is confused.

As an example, suppose we are interested in the role of the activations
$Z_{A_{0}}$ in Fig. 2a. To apply causal mediation analysis, we would:

  1. 1.

Obtain $Z_{\text{context}}$ by running the model on the original context
$\mathbf{c}$ (which we also refer to as the _target_ context) (Fig. 2a)

  2. 2.

Obtain $Z_{\text{context}}^{\prime}$ by running the model on a different
context $\mathbf{c}^{\prime}$ (i.e.  _source_ context) (Fig. 2b)

  3. 3.

Modify $Z_{\text{context}}$ by replacing $Z_{A_{0}}$ from the target context
with $Z_{A_{0}}^{\prime}$ from the source context (Fig. 2c), while keeping all
other aspects of $Z_{\text{context}}$ the same, resulting in
$Z_{\text{context}}^{\text{intervened}}=Z_{\text{context}}/.\\{Z_{A_{0}}\rightarrow
Z_{A_{0}}^{\prime}\\}$

  4. 4.

Evaluate the model’s beliefs based on the new
$Z_{\text{context}}^{\text{intervened}}$

We can infer the causal role of $Z_{A_{0}}$ from how the intervention
$Z_{\text{context}}/.\\{Z_{A_{0}}\rightarrow Z_{A_{0}}^{\prime}\\}$ changes
the model’s beliefs. Intuitively, if the model retains its original beliefs
$\mathbf{c}$, then $Z_{A_{0}}$ has no causal role in the model’s behavior on
the binding task. On the other hand, if the model now believes the source
context $\mathbf{c}^{\prime}$, then $Z_{A_{0}}$ contains all the information
in the context. In reality both hypothetical extremes are implausible, and in
Section 3 we discuss a more realistic hypothesis.

A subtle point is that we study how different components of
$Z_{\text{context}}$ store information about the context (and thus influence
behavior), and not how $Z_{\text{context}}$ itself is constructed. We thus
suppress the causal influence that $Z_{A_{0}}$ has on downstream parts of
$Z_{\text{context}}$ (such as $Z_{E_{1}}$ and $Z_{A_{1}}$) by freezing the
values of $Z_{E_{1}}$ and $Z_{A_{1}}$ in
$Z_{\text{context}}^{\text{intervened}}$ instead of recomputing them based on
$Z_{A_{0}}^{\prime}$.

##  3 Existence of Binding IDs

In this section, we first describe our hypothesized binding ID mechanism.
Then, we identify two key predictions of the mechanism, factorizability and
position independence, and verify them experimentally. We provide an informal
argument in Appendix B for why this binding ID mechanism is the only mechanism
consistent with factorizability and position independence.

Binding ID mechanism. We claim that to bind attributes to entities, the LM
learns abstract binding IDs that it assigns to entities and attributes, so
that entities and attributes bound together have the same binding ID (Fig. 1).
In more detail, our informal description of the binding ID mechanism is:

  1. 1.

For entity $E_{k}$, encode both the entity $E_{k}$ and the binding ID $k$333In
Fig. 1 we used shapes to denote abstract binding IDs. In the text, we will
identify the abstract binding IDs with the integers $\\{0,1,\dots,n-1\\}$ so
that the $k$-th entity/attribute has the abstract binding ID $k$. in the
activations $Z_{E_{k}}$.

  2. 2.

For attribute $A_{k}$, encode both the attribute $A_{k}$ and the binding ID
$k$ in the activations $Z_{A_{k}}$.

  3. 3.

To answer a query for entity $E_{k}$, retrieve from $Z_{\text{context}}$ the
attribute that shares the same binding ID as $E_{k}$.

Further, for activations $Z_{E_{k}}$ and $Z_{A_{k}}$, the binding ID and the
entity/attribute are the only information they contain that affects the query
behavior.

More formally, there are binding functions $\Gamma_{E}(e,k)$ and
$\Gamma_{A}(a,k)$ that fully specify how $Z_{E}$ and $Z_{A}$ bind
entities/attributes with binding IDs. Specifically, if
$E_{k}=e\in\mathcal{E}$, then we can replace $Z_{E_{k}}$ with
$\Gamma_{E}(e,k)$ without changing the query behavior, and likewise for
$Z_{A}$.

More generally, given ${Z}_{\text{context}}$ with entity representations
$\Gamma_{E}(e_{0},0),\ldots,\Gamma_{E}(e_{n-1},n-1)$ and attribute
representations $\Gamma_{A}(a_{0},\pi(0)),\ldots,\Gamma_{A}(a_{n-1},\pi(n-1))$
for a permutation $\pi$, the LM should answer queries according to the context
$\mathbf{c}=\operatorname{ctxt}(e_{0}\leftrightarrow
a_{\pi^{-1}(0)},\ldots,e_{n-1}\leftrightarrow a_{\pi^{-1}(n-1)})$. This
implies two properties in particular, which we will test in the following
subsections:

  * •

Factorizability: if we replace $Z_{A_{k}}$ with $Z_{A_{k}^{\prime}}$, then the
model will bind $E_{k}$ to $A_{k}^{\prime}$ instead of $A_{k}$, i.e. it will
believe $\mathbf{c}./\\{A_{k}\rightarrow A_{k}^{\prime}\\}$. This is because
$Z_{A_{k}}^{\prime}$ encodes $\Gamma_{A}(A_{k}^{\prime},k)$ and $Z_{A_{k}}$
encodes $\Gamma_{A}(A_{k},k)$. Substituting $Z_{A_{k}}\rightarrow
Z_{A_{k}^{\prime}}$ will overwrite $\Gamma_{A}(A_{k},k)$ with
$\Gamma_{A}(A_{k}^{\prime},k)$, causing the model to bind $E_{k}$ to
$A_{k}^{\prime}$.

  * •

Position independence: if we e.g. swap $Z_{A_{0}}$ and $Z_{A_{1}}$, the model
still binds $A_{0}\leftrightarrow E_{0}$ and $A_{1}\leftrightarrow E_{1}$,
because it looks up attributes based on binding ID and not position in the
context.

In Section 4, we construct fine-grained modifications to the activation $Z$
that modify the binding ID but not the attributes, allowing us to test the
binding hypothesis more directly. In Section 5 we extend this further by
showing that binding IDs can be transplanted from entirely different tasks.

(a) Swapping entity/attribute for $(E_{0},A_{0})$

(b) Swapping entity/attribute for $(E_{1},A_{1})$

Figure 3: Factorizability results. Each row corresponds to querying for a
particular entity. Plotted are the mean log prob for all four attributes.
Highlighted squares are predicted by factorizability.

###  3.1 Factorizability of activations

The first property of $Z_{\text{context}}$ we test is factorizability. In our
claimed mechanism, information is highly localized—$Z_{A_{k}}$ contains all
relevant information about $A_{k}$, and likewise for $Z_{E_{k}}$. Therefore,
we expect LMs that implement this mechanism to have factorizable activations:
for any contexts $\mathbf{c},\mathbf{c}^{\prime}$, substituting
$Z_{E_{k}}\rightarrow Z_{E_{k}}(\mathbf{c}^{\prime})$ into
$Z_{\text{context}}(\mathbf{c})$ will cause the model to believe
$\mathbf{c}/.\\{E_{k}\rightarrow E_{k}^{\prime}\\}$, and substituting
$Z_{A_{k}}\rightarrow Z_{A_{k}}(\mathbf{c}^{\prime})$ cause the model to
believe $\mathbf{c}/.\\{A_{k}\rightarrow A_{k}^{\prime}\\}$.

To test this concretely, we considered the capitals task from Section 2 with
$n=2$ entity-attribute pairs. We computed representations for two contexts
$\mathbf{c}=\operatorname{ctxt}(e_{0}\leftrightarrow
a_{0},e_{1}\leftrightarrow a_{1})$ and
$\mathbf{c}^{\prime}=\operatorname{ctxt}(e_{0}^{\prime}\leftrightarrow
a_{0}^{\prime},e_{1}^{\prime}\leftrightarrow a_{1}^{\prime})$, and used causal
mediation analysis (Section 2) to swap representations from the source context
$\mathbf{c}^{\prime}$ into the target context $\mathbf{c}$. Specifically, we
fix $k\in\\{0,1\\}$ and intervene on either just the entity
($Z_{E_{K}}\rightarrow Z_{E_{k}}^{\prime}$), just the attribute, neither, or
both. We then measure the mean log probs for all possible queries
($E_{0},E_{1},E_{0}^{\prime},E_{1}^{\prime})$. For instance, swapping $A_{k}$
with $A_{k}^{\prime}$ in $Z_{\text{context}}$ should lead $A_{k}^{\prime}$
(and not $A_{k}$) to have high log-probability when $E_{k}$ is queried.

Results are shown in Fig. 3 and support the factorizability hypothesis. As an
example, consider Fig. 3(a). In the None setting (no intervention), we see
high log probs for $A_{0}$ when queried for $E_{0}$, and for $A_{1}$ when
queried for $E_{1}$. This indicates that the LM is able to solve this task.
Next, consider the Attribute intervention setting ($A_{0}\to A_{0}^{\prime}$):
querying for $E_{0}$ now gives high log probs for $A_{0}^{\prime}$, and
querying for $E_{1}$ gives $A_{1}$ as usual. Finally, in the Both setting
(where both entity and attribute are swapped), querying $E_{0}^{\prime}$
returns $A_{0}^{\prime}$ while querying $E_{0}$ leads to approximately uniform
predictions.

Experiment details. We use LLaMA 30-b here and elsewhere unless otherwise
stated. In practice, we found that activations for both the entity token and
the subsequent token encode the entity binding information. Thus for all
experiments in this paper, we expand the definition of $Z_{E_{k}}$ to include
the token activations immediately after $E_{k}$.

###  3.2 Position independence

Figure 4: Top: Mean log probs for entity interventions. Bottom: Mean log probs
for attributes. For brevity, let $Z_{k}$ refer to $Z_{E_{k}}$ or $Z_{A_{k}}$.
The grey and green vertical lines indicate the original positions for $Z_{0}$
and $Z_{1}$ respectively. The x-axis marks $x$, $Z_{0}$’s new position. Under
the position interventions $\\{X_{0}\rightarrow x,X_{1}\rightarrow
X_{1}-(x-X_{0})\\}$, the grey line is the control condition with no
interventions, and the green line is the swapped condition where $Z_{0}$ and
$Z_{1}$ have swapped positions.

We next turn to position independence, which is the other property we expect
LMs implementing the binding ID mechanism to have. This says that permuting
the order of the $Z_{E_{k}}$ and $Z_{A_{k}}$ should have no effect on the
output, because the LM looks only at the binding IDs and not the positions of
entities or attributes activations.

To apply causal interventions to the positions, we use the fact that
transformers use positional embeddings to encode the (relative) position of
each token in the input. We can thus intervene on these embeddings to “move”
one of the $Z_{k}$’s to another location $k^{\prime}$. Formally, we let
$X_{k}$ describe the position embedding for $Z_{k}$, and denote the position
intervention as $\\{X_{k}\rightarrow k^{\prime}\\}$. In Appendix C we describe
how to do this for rotary position embeddings (RoPE), which underlie all the
models we study. For now, we will assume this intervention as a primitive and
discuss experimental results.

For our experiments, we again consider the capitals task with $n=2$. Let
$X_{E_{0}}$ and $X_{E_{1}}$ denote the positions of the two entities. We apply
interventions of the form $\\{X_{E_{0}}\rightarrow x,X_{E_{1}}\rightarrow
X_{E_{1}}-(x-X_{E_{0}})\\}$, for
$x\in\\{X_{E_{0}},X_{E_{0}}+1,\ldots,X_{E_{1}}\\}$. This measures the effect
of gradually moving the two entity positions past each other: when
$x=X_{E_{0}}$, no intervention is performed (control condition), and when
$x=X_{E_{1}}$ the entity positions are swapped (swapped condition). We repeat
the same experiment with attribute activations and measure the mean log probs
in both cases.

Results are shown in Fig. 4. As predicted under position independence,
position interventions result in little change in model behavior. Consider the
swapped condition at the green line. Had the binding information been entirely
encoded in position, we expect a complete switch in beliefs compared to the
control condition. In reality, we observe almost no change in mean log probs
for entities and a small change in mean log probs for attributes that seems to
be part of an overall gradual trend.

We interpret this gradual trend as an artifact of position-dependent bias, and
not as evidence against position independence. We view it as a bias because it
affects all attributes regardless of how they are bound—attributes that are
shifted to later positions always have higher log probs. We provide further
discussion of this bias, as well as other experimental details, in Appendix C.

##  4 Structure of Binding ID

The earlier section shows evidence for the binding ID mechanism. Here, we
investigate two hypotheses on the structure of binding IDs and binding
functions. The first is that the binding functions $\Gamma_{A}$ and
$\Gamma_{E}$ are additive, which lets us think of binding IDs as binding
vectors. The second is contingent on the first, and asks if binding vectors
have a geometric relationship between each other.

###  4.1 Additivity of Binding Functions

Prior interpretability research has proposed that transformers represent
features linearly (Elhage et al., 2021). Therefore a natural hypothesis is
that both entity/attribute representations and abstract binding IDs are
vectors in activation space, and that the binding function simply adds the
vectors for entity/attribute and binding ID. We let the binding ID $k$ be
represented by the pair of vectors $[b_{E}(k),b_{A}(k)]$, and the
representations of entity $e$ and attribute $a$ be $f_{E}(e)$ and $f_{A}(a)$
respectively. Then, we hypothesize that the binding functions can be linearly
decomposed as:

$\Gamma_{A}(a,k)=f_{A}(a)+b_{A}(k),\quad\Gamma_{E}(e,k)=f_{E}(e)+b_{E}(k).$
(1)

Binding ID vectors seem intuitive and plausibly implementable by transformer
circuits. To experimentally test this, we seek to extract $b_{A}(k)$ and
$b_{E}(k)$ in order to perform vector arithmetic on them. We use (1) to
extract the differences $\Delta_{E}(k):=b_{E}(k)-b_{E}(0)$,
$\Delta_{A}(k):=b_{A}(k)-b_{A}(0)$. Rearranging (1), we obtain

$\Delta_{A}(k)=\Gamma_{A}(\alpha,k)-\Gamma_{A}(\alpha,0),\quad\Delta_{E}(k)=\Gamma_{E}(a,k)-\Gamma_{E}(a,0).$
(2)

We estimate $\Delta_{A}(k)$ by sampling
$\mathbb{E}_{\mathbf{c},\mathbf{c}^{\prime}}[Z_{A_{k}}(\mathbf{c})-Z_{A_{0}}(\mathbf{c}^{\prime})]$,
and likewise for $\Delta_{E}(k)$.

Test condition | Control | Attribute | Entity | Both  | Attribute | Entity | Both
---|---|---|---|---|---|---|---
Querying $E_{0}$ | 0.99 | 0.00 | 0.00 | 0.97  | 0.98 | 0.98 | 0.97
Querying $E_{1}$ | 1.00 | 0.03 | 0.01 | 0.99  | 1.00 | 1.00 | 1.00
Table 1: Left: Mean calibrated accuracies for mean interventions on four test
conditions. Columns are the test conditions, and rows are queries. Right: Mean
interventions with random vectors.

Mean interventions. With the difference vectors, we can modify binding IDs by
performing _mean interventions_ , and observe how model behavior changes. The
attribute mean intervention switches the binding ID vectors in $Z_{A_{0}}$ and
$Z_{A_{1}}$ with the interventions $Z_{A_{0}}\rightarrow
Z_{A_{0}}+\Delta_{A}(1),Z_{A_{1}}\rightarrow Z_{A_{1}}-\Delta_{A}(1)$. The
entity mean intervention similarly switches the binding ID vectors in
$Z_{E_{0}}$ and $Z_{E_{1}}$. Additivity predicts that performing either mean
intervention will reverse the model behavior: $E_{0}$ will be associated with
$A_{1}$, and $E_{1}$ with $A_{0}$.

Experiments. In our experiments, we fix $n=2$ and use 500 samples to estimate
$\Delta_{E}(1)$ and $\Delta_{A}(1)$. We then perform four tests, and evaluate
the model accuracy under the original belief. The Control test has no
interventions, and the accuracy reflects model’s base performance. The
Attribute and Entity tests perform the attribute and entity mean
interventions, which should lead to a complete switch in model beliefs so that
the accuracy is near 0. Table 1 shows agreement with additivity: the
accuracies are above $99\%$ for Control, and below $3\%$ for Attribute and
Entity.

As a further check, we perform both attribute and entity mean interventions
simultaneously, which should cancel out and thus restore accuracy. Indeed,
Table 1 shows that accuracy for Both is above $97\%$. Finally, to show that
the _specific_ directions obtained by the difference vectors matter, we sample
random vectors with the same magnitude but random directions, and perform the
same mean interventions with the random vectors. These random vectors have no
effect on the model behavior.

###  4.2 The Geometry of Binding ID Vectors

Figure 5: The plots show the mean median-calibrated accuracy when one pair of
binding ID, $v_{0}$, is fixed at the green circle, and the other, $v_{1}$, is
varied across the grid. The binding IDs $b(0)$, $b(1)$, and $b(2)$ are shown
as the origin of the arrows, the end of the horizontal arrow, and the end of
the diagonal arrow respectively. We use LLaMA-13b for computational reasons.

Section 4.1 shows that we can think of binding IDs as pairs of ID vectors, and
that randomly chosen vectors do not function as binding IDs. We next
investigate the geometric structure of valid binding vectors and find that
linear interpolations or extrapolations of binding vectors are often also
valid binding vectors. This suggests that binding vectors occupy a continuous
binding subspace. We find evidence of a metric structure in this space, such
that nearby binding vectors are hard for the model to distinguish, but far-
away vectors can be reliably distinguished and thus used for the binding task.

To perform our investigation, we apply variants of the mean interventions in
Section 4.1. As before, we start with an $n=2$ context, thus obtaining
representations $Z_{0}=(Z_{E_{0}},Z_{A_{0}})$ and
$Z_{1}=(Z_{E_{1}},Z_{A_{1}})$. We first erase the binding information by
subtracting $(\Delta_{E}(1),\Delta_{A}(1))$ from $Z_{1}$, which reduces
accuracy to chance. Next, we will add vectors $v_{0}=(v_{E_{0}},v_{A_{0}})$
and $v_{1}=(v_{E_{1}},v_{A_{1}})$ to the representations $Z$; if doing so
restores accuracy, then we view $(v_{E_{0}},v_{A_{0}})$ and
$(v_{E_{1}},v_{A_{1}})$ as valid binding pairs.

To generate different choices of $v$, we take linear combinations across a
two-dimensional space. The basis vectors for this space are
$(\Delta_{E}(1),\Delta_{A}(1))$ and $(\Delta_{E}(2),\Delta_{A}(2))$ obtained
by averaging across an $n=3$ context. Fig. 5 shows the result for several
different combinations, where the coordinates of $v_{0}$ are fixed and shown
in green while the coordinates of $v_{1}$ vary. When $v_{1}$ is close to
$v_{0}$, the LM gets close to 50% accuracy, which indicates confusion. Far
away from $v_{1}$, the network consistently achieves high accuracy,
demonstrating that linear combinations of binding IDs (even with negative
coefficients) are themselves valid binding IDs. See Appendix G for details.

The geometry of the binding subspace hints at circuits (Elhage et al., 2021)
in LMs that process binding vectors. For example, we speculate that certain
attention heads might be responsible for comparing binding ID vectors, since
the attention mechanism computes attention scores using a quadratic form which
could provide the metric over the binding subspace.

##  5 Generality and Limitations of Binding ID

The earlier sections investigate binding IDs for one particular task: the
capitals task. In this section, we evaluate their generality. We first show
that binding vectors are used for a variety of tasks and models. We then show
evidence that the binding vectors are task-agnostic: vectors from one task
transfer across many different tasks. However, we show that our mechanism is
not fully universal, by exhibiting a question-answering task that uses an
alternative binding mechanism.

Figure 6: Left: models in Pythia and LLaMA on capitals. LLaMA-65b not present
for computational reasons. Right: LLaMA-30b on binding tasks. Unlike others,
the bios task has attributes that are several tokens long.

Generality of binding ID vectors. We evaluate the generality of binding
vectors across models and tasks. For a (model, task) pair, we compute the
median-calibrated accuracy on the $n=3$ context under three conditions: (1)
the control condition in which no interventions are performed, and the (2)
entity and (3) attribute conditions in which entity or attribute mean
interventions (Section 4.1) are performed. We use the mean interventions to
permute binding pairs by a cyclic shift and measure accuracy according to this
shift (see Appendix F). As shown in Figure 6, the interventions induce the
expected behavior on most tasks; moreover, their effectiveness increases with
model scale, suggesting that larger models have more robust structured
representations.

Task | capitals | parallel | shapes | fruits | bios | Zeros | Random
---|---|---|---|---|---|---|---
Mean accuracy | 0.88 | 0.87 | 0.71 | 0.80 | 0.47 | 0.30 | 0.31
Mean log prob | -1.01 | -1.07 | -1.18 | -1.21 | -1.64 | -1.86 | -2.15
Table 2: The mean median-calibrated accuracy and mean log prob for mean
interventions on $n=3$ capitals using binding ID estimates from other tasks.
Random chance has $0.33$ mean accuracy.

Transfer across tasks. We next show that binding vectors often transfer across
tasks. Without access to the binding vectors $[b_{E}(k),b_{A}(k)]$, we instead
test if the difference vectors
$[\Delta^{\mathrm{src}}_{E}(k),\Delta^{\mathrm{src}}_{A}(k)]$ from a source
task, when applied to a target task, result in valid binding IDs. To do so, we
follow a similar procedure to Section 4.2: First, we erase binding information
by subtracting $[\Delta^{\mathrm{tar}}_{E}(k),\Delta^{\mathrm{tar}}_{A}(k)]$
for the target task from each target-task representation
$[Z_{E_{k}},Z_{A_{k}}]$, which results in near-chance accuracy. Then, we add
back in $[\Delta^{\mathrm{src}}_{E}(k),\Delta^{\mathrm{src}}_{A}(k)]$ computed
from the _source_ task with the hope of restoring performance.

Table 2 shows results for a variety of source tasks when using capitals as the
target task. Accuracy is consistently high, even when the target task has
limited surface similarity to the target task. For example, the shapes task
contains descriptions about geometrical shapes and their colors, and parallel
puts all entities before any attributes instead of interleaving them as in
capitals. We include two baselines for comparison: replacing
$\Delta^{\mathrm{src}}(k)$ with the zero vector (“Zeros”), or picking a
randomly oriented difference vector as in Table 1 (“Random”). Both lead to
chance accuracy. See Appendix D for more details on the tasks.

The fact that binding vectors transfer across tasks, together with the results
from Section 4, suggests that there could be a task-agnostic subspace in the
model’s activations reserved for binding vectors.

Figure 7: Direct binding in MCQ task. $O_{k}$ and $L_{k}$ denote options and
labels respectively. Under direct binding, $Z_{O_{0}}$ and $Z_{O_{1}}$ are
represented by a binding function $\Lambda_{O}$ that directly binds option and
label together, whereas $Z_{L_{0}}$ and $Z_{L_{1}}$ are causally irrelevant.

Direct binding in MCQ. While binding IDs are used for many tasks, they are not
universal. We briefly identify an alternate binding mechanism, the direct
binding mechanism, that is used for a multiple-choice question-answering task
(MCQ). In MCQ, each label (A or B) has to be bound to its associated option
text. In this task, instead of binding variables to an abstract binding ID,
the model directly binds the label to the option (Fig. 7). We provide the full
details of this task and further explanations in Appendix E.

##  6 Related work

Causal mediation analysis. In recent years, causal methods have gained
popularity in post hoc interpretability (Meng et al., 2022; Geiger et al.,
2021). Instead of relying on correlations, which could lead to spurious
features (Hewitt & Liang, 2019), causal mediation analysis (Vig et al., 2020a)
performs causal interventions on internal states of LMs to understand their
causal role on LM behavior. Our work shares the same causal perspective
adopted by many in this field.

Knowledge recall. A line of work studies recalling factual associations that
LMs learn from pretraining (Geva et al., 2020; Dai et al., 2021; Meng et al.,
2022; Geva et al., 2023; Hernandez et al., 2023b). This is spiritually related
to binding, as entities must be associated to facts about them. However, this
work studies factual relations learned from pretraining and how they are
recalled from model weights. In contrast, we study representations of
relations learned from context, and how they are recalled from model
activations.

More recently, Hernandez et al. (2023a) found a method to construct bound
representations by directly binding attribute representations to entity
representations. In contrast, our work investigates bound representations
constructed by the LM itself, and identifies that the binding ID mechanism
(and not direct binding) is the mechanism that LM representations
predominantly uses. An avenue for future work is to study how bound
representations constructed by Hernandez et al. (2023a) relates to the direct
binding mechanism we identified in the MCQ task.

Symbolic representations in connectionist systems. Many works have studied how
neural networks represent symbolic concepts in activation space (Mikolov et
al., 2013; Tenney et al., 2019; Belinkov & Glass, 2019; Rogers et al., 2021;
Patel & Pavlick, 2021). To gain deeper insights into how these representations
are used for reasoning, recent works have studied representations used for
specialized reasoning tasks (Nanda et al., 2023; Li et al., 2022; 2021). Our
work shares the motivation of uncovering how neural networks implement
structured representations that enable reasoning.

Mechanistic Interpretability. Mechanistic interpretability aims to uncover
circuits (Elhage et al., 2021; Wang et al., 2022; Wu et al., 2023), often
composed of attention heads, that are embedded in language models. In our
work, we study language model internals on a more coarse-grained level. We
identify structures in representations that have causal influences on model
behavior, but how circuits construct these representations or utilize them is
left as future work.

##  7 Conclusion

In this paper we identify and study the binding problem, a common and
fundamental reasoning subproblem. We find that pretrained LMs can solve the
binding task by binding entities and attributes to abstract binding IDs. Then,
we identify that the binding IDs are vectors from a binding subspace with a
notion of distance. Lastly, we find that the binding IDs are used broadly for
a variety of binding tasks and are present in all sufficiently large models
that we studied.

Taking a broader view, we see our work as a part of the endeavor to interpret
LM reasoning by decomposing it into primitive skills. In this work we
identified the binding skill, which is used in several settings and has a
simple and robust representation structure. An interesting direction of future
work would be to identify other primitive skills that support general purpose
reasoning and have similarly interpretable mechanisms.

Our work also suggests that ever-larger LMs may still have interpretable
representations. A common intuition is that larger models are more complex,
and hence more challenging to interpret. Our work provides a counterexample:
as LMs become larger, their representations can become _more_ structured and
interpretable, since only the larger models exhibited binding IDs (Fig. 6).

Speculating further, the fact that large enough models in two unrelated LM
families learn the same structured representation strategy points to a
convergence in representations with scale. This raises the philosophical
question: could there be an ultimate representation that these LMs are
converging towards? Perhaps the properties of natural language corpora and LM
inductive biases lead to the inevitable development of certain core
representation strategies that are invariant to changes in model
hyperparameters or exact dataset composition. This would encouragingly imply
that interpretability results can transfer across models—studying the core
representations of any sufficiently large model would yield insights into
other similarly large models because of their convergent core structure.

#### Acknowledgments

We thank Danny Halawi, Fred Zhang, Erik Jenner, Cassidy Laidlaw, Shawn Im,
Arthur Conmy, Shivam Singhal, and Olivia Watkins for their helpful feedback.
JF was supported by the Long-Term Future Fund. JS was supported by the
National Science Foundation under Grants No. 2031899 and 1804794. In addition,
we thank Open Philanthropy for its support of both JS and the Center for
Human-Compatible AI.

## References

  * Belinkov & Glass (2019) Yonatan Belinkov and James Glass.  Analysis methods in neural language processing: A survey.  _Transactions of the Association for Computational Linguistics_ , 7:49–72, 2019.  doi: 10.1162/tacl˙a˙00254.  URL https://aclanthology.org/Q19-1004.
  * Biderman et al. (2023) Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al.  Pythia: A suite for analyzing large language models across training and scaling.  In _International Conference on Machine Learning_ , pp. 2397–2430. PMLR, 2023.
  * Dai et al. (2021) Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, and Furu Wei.  Knowledge neurons in pretrained transformers.  _ArXiv_ , abs/2104.08696, 2021.  URL https://api.semanticscholar.org/CorpusID:233296761.
  * De-Arteaga et al. (2019) Maria De-Arteaga, Alexey Romanov, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexandra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, and Adam Tauman Kalai.  Bias in bios: A case study of semantic representation bias in a high-stakes setting.  In _proceedings of the Conference on Fairness, Accountability, and Transparency_ , pp. 120–128, 2019.
  * Elhage et al. (2021) Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_ , 2021.  https://transformer-circuits.pub/2021/framework/index.html.
  * Geiger et al. (2021) Atticus Geiger, Hanson Lu, Thomas Icard, and Christopher Potts.  Causal abstractions of neural networks.  _Advances in Neural Information Processing Systems_ , 34:9574–9586, 2021.
  * Geva et al. (2020) Mor Geva, R. Schuster, Jonathan Berant, and Omer Levy.  Transformer feed-forward layers are key-value memories.  _ArXiv_ , abs/2012.14913, 2020.  URL https://api.semanticscholar.org/CorpusID:229923720.
  * Geva et al. (2023) Mor Geva, Jasmijn Bastings, Katja Filippova, and Amir Globerson.  Dissecting recall of factual associations in auto-regressive language models.  _arXiv preprint arXiv:2304.14767_ , 2023.
  * Hendrycks et al. (2021) Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt.  Unsolved problems in ml safety.  _arXiv preprint arXiv:2109.13916_ , 2021.
  * Hernandez et al. (2021) Evan Hernandez, Sarah Schwettmann, David Bau, Teona Bagashvili, Antonio Torralba, and Jacob Andreas.  Natural language descriptions of deep visual features.  In _International Conference on Learning Representations_ , 2021.
  * Hernandez et al. (2023a) Evan Hernandez, Belinda Z Li, and Jacob Andreas.  Measuring and manipulating knowledge representations in language models.  _arXiv preprint arXiv:2304.00740_ , 2023a.
  * Hernandez et al. (2023b) Evan Hernandez, Arnab Sen Sharma, Tal Haklay, Kevin Meng, Martin Wattenberg, Jacob Andreas, Yonatan Belinkov, and David Bau.  Linearity of relation decoding in transformer language models.  _arXiv preprint arXiv:2308.09124_ , 2023b.
  * Hewitt & Liang (2019) John Hewitt and Percy Liang.  Designing and interpreting probes with control tasks.  _arXiv preprint arXiv:1909.03368_ , 2019.
  * Li et al. (2021) Belinda Z Li, Maxwell Nye, and Jacob Andreas.  Implicit representations of meaning in neural language models.  _arXiv preprint arXiv:2106.00737_ , 2021.
  * Li et al. (2022) Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Wattenberg.  Emergent world representations: Exploring a sequence model trained on a synthetic task.  _arXiv preprint arXiv:2210.13382_ , 2022.
  * Meng et al. (2022) Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov.  Locating and editing factual associations in gpt.  _Advances in Neural Information Processing Systems_ , 35:17359–17372, 2022.
  * Mikolov et al. (2013) Tomáš Mikolov, Wen-tau Yih, and Geoffrey Zweig.  Linguistic regularities in continuous space word representations.  In _Proceedings of the 2013 conference of the north american chapter of the association for computational linguistics: Human language technologies_ , pp. 746–751, 2013.
  * Mu & Andreas (2020) Jesse Mu and Jacob Andreas.  Compositional explanations of neurons.  _Advances in Neural Information Processing Systems_ , 33:17153–17163, 2020.
  * Nanda et al. (2023) Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt.  Progress measures for grokking via mechanistic interpretability.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=9XFSbDPmdW.
  * Patel & Pavlick (2021) Roma Patel and Ellie Pavlick.  Mapping language models to grounded conceptual spaces.  In _International Conference on Learning Representations_ , 2021.
  * Räuker et al. (2023) Tilman Räuker, Anson Ho, Stephen Casper, and Dylan Hadfield-Menell.  Toward transparent ai: A survey on interpreting the inner structures of deep neural networks.  In _2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)_ , pp. 464–483. IEEE, 2023.
  * Rogers et al. (2021) Anna Rogers, Olga Kovaleva, and Anna Rumshisky.  A primer in bertology: What we know about how bert works.  _Transactions of the Association for Computational Linguistics_ , 8:842–866, 2021.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pp. 1631–1642, Seattle, Washington, USA, October 2013. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/D13-1170.
  * Su et al. (2021) Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu.  Roformer: Enhanced transformer with rotary position embedding.  _arXiv preprint arXiv:2104.09864_ , 2021.
  * Tenney et al. (2019) Ian Tenney, Dipanjan Das, and Ellie Pavlick.  Bert rediscovers the classical nlp pipeline.  In _Association for Computational Linguistics_ , 2019.  URL https://arxiv.org/abs/1905.05950.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Treisman (1996) Anne Treisman.  The binding problem.  _Current opinion in neurobiology_ , 6(2):171–178, 1996.
  * Vig et al. (2020a) Jesse Vig, Sebastian Gehrmann, Yonatan Belinkov, Sharon Qian, Daniel Nevo, Yaron Singer, and Stuart Shieber.  Investigating gender bias in language models using causal mediation analysis.  _Advances in neural information processing systems_ , 33:12388–12401, 2020a.
  * Vig et al. (2020b) Jesse Vig, Sebastian Gehrmann, Yonatan Belinkov, Sharon Qian, Daniel Nevo, Yaron Singer, and Stuart Shieber.  Investigating gender bias in language models using causal mediation analysis.  _Advances in Neural Information Processing Systems_ , 33:12388–12401, 2020b.
  * Wang et al. (2022) Kevin Wang, Alexandre Variengien, Arthur Conmy, Buck Shlegeris, and Jacob Steinhardt.  Interpretability in the wild: A circuit for indirect object identification in gpt-2 small.  _arXiv preprint arXiv:2211.00593_ , 2022.
  * Wang et al. (2023) Yizhong Wang, Hamish Ivison, Pradeep Dasigi, Jack Hessel, Tushar Khot, Khyathi Raghavi Chandu, David Wadden, Kelsey MacMillan, Noah A Smith, Iz Beltagy, et al.  How far can camels go? exploring the state of instruction tuning on open resources.  _arXiv preprint arXiv:2306.04751_ , 2023.
  * Wu et al. (2023) Zhengxuan Wu, Atticus Geiger, Christopher Potts, and Noah D Goodman.  Interpretability at scale: Identifying causal mechanisms in alpaca.  _arXiv preprint arXiv:2305.08809_ , 2023.
  * Zhao et al. (2021) Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh.  Calibrate before use: Improving few-shot performance of language models.  In _International Conference on Machine Learning_ , pp. 12697–12706. PMLR, 2021.

##  Appendix A Evaluation details

In all of our evaluations, we sample $N=100$ instances of contexts from the
binding task, obtaining $\\{\mathbf{c}_{i}\\}_{i=1}^{N}$. For succinctness, we
write $E_{k}^{(i)}:=E_{k}(\mathbf{c}_{i})$ and
$A_{k}^{(i)}:=A_{k}(\mathbf{c}_{i})$. For the $i$-th context instance, we
query $E_{0}^{(i)}$ and $E_{1}^{(i)}$ which return log probabilities
$\Phi^{(i)}_{E_{0}}(t)$ and $\Phi^{(i)}_{E_{1}}(t)$ over tokens $t$ in the
vocabulary. However, we consider only the log probabilities for relevant
attributes $\Phi^{(i)}_{E_{k}}(A_{0}^{(i)})$ and
$\Phi^{(i)}_{E_{k}}(A_{1}^{(i)})$. We then compute the summary statistics
(described below) over the entire population of samples so that we get two
scalars, $\sigma_{E_{0}}$ and $\sigma_{E_{1}}$ describing the performance
under each query entity.

  * •

The mean log prob is given by
$\sigma_{E_{k}}=\frac{1}{N}\sum_{i=1}^{N}\Phi^{(i)}_{E_{k}}(A_{k}^{(i)})$.

  * •

The top-1 accuracy is
$\sigma_{E_{k}}=\frac{1}{N}\sum_{i=1}^{N}\mathbf{1}[k=\operatorname*{arg\,max}_{l}\Phi^{(i)}_{E_{k}}(A_{l}^{(i)})]$.

  * •

We adopt the median calibrated accuracy from Zhao et al. (2021). First, we
obtain a baseline by computing medians for every attribute
$m(A_{l}):=\operatorname{median}_{i,k}\\{\Phi^{(i)}_{E_{k}}(A_{l}^{(i)})\\}$.
Then, compute calibrated log probs
$\tilde{\Phi}_{E_{k}}^{(i)}(A_{l}):=\Phi_{E_{k}}^{(i)}(A_{l})-m(A_{l})$. The
median calibrated accuracy is then
$\sigma_{E_{k}}=\frac{1}{N}\sum_{i=1}^{N}\mathbf{1}[k=\operatorname*{arg\,max}_{l}\tilde{\Phi}^{(i)}(A_{l}^{(i)})]$.

Zhao et al. (2021) discusses motivations for the median calibrated accuracy.
In our case, the position dependent bias provides addition reasons, which we
discuss in Appendix C.

##  Appendix B Necessity of Binding ID mechanism

In this section, we provide one definition of the binding ID mechanism, and
argue informally that under this definition, factorizability and position
independence necessarily implies the binding ID mechanism.

First, let us define the binding ID mechanism. Fix $n=2$ for simplicity. There
are two claims:

  1. 1.

Representation. There exists a binding function $\Gamma_{E}$ such that for any
contexts $\mathbf{c}$, $Z_{E_{k}}$ is represented by $\Gamma_{E}(E_{k},k)$, in
the sense that for any $e\in\mathcal{E}$,
$\\{Z_{E_{k}}\rightarrow\Gamma_{E}(e,k)\\}$ leads to the belief
$\mathbf{c}/.\\{E_{k}\rightarrow e\\}$. Likewise, there exists a binding
function $\Gamma_{A}$ such that for any contexts $\mathbf{c}$, $Z_{A_{k}}$ is
represented by $\Gamma_{A}(A_{k},k)$, in the sense that for any
$a\in\mathcal{A}$, $\\{Z_{A_{k}}\rightarrow\Gamma_{A}(a,k)\\}$ leads to the
belief $\mathbf{c}/.\\{A_{k}\rightarrow a\\}$. These substitutions should also
compose appropriately.

  2. 2.

Query. Further, the binding functions $\Gamma_{A}$ and $\Gamma_{E}$ satisfy
the following property: Choose any 2 permutations $\pi_{E}(k)$ and
$\pi_{A}(k)$ over $\\{0,1\\}$, and consider a $Z_{\text{context}}$ containing
$[\Gamma_{E}(e_{0},\pi_{E}(0)),\Gamma_{A}(a_{0},\pi_{A}(0)),\Gamma_{E}(e_{1},\pi_{E}(1)),\Gamma_{A}(a_{1},\pi_{A}(1))]$
. The query system will then believe $e_{0}\leftrightarrow
a_{0},e_{1}\leftrightarrow a_{1}$ if $\pi_{E}=\pi_{A}$, and
$e_{0}\leftrightarrow a_{1},e_{1}\leftrightarrow a_{0}$ otherwise.

The first claim follows from factorizability. From factorizability, we can
construct the candidate binding functions simply by picking an arbitrary
context consistent with the parameters. For any $e\in\mathcal{E}$ and any
binding ID $k\in[0,n-1]$, pick any context $\mathbf{c}$ such that
$E_{k}(\mathbf{c})=e$. Then, let $\Gamma_{E}(e,k)=Z_{E_{k}}(\mathbf{c})$.
$\Gamma_{A}$ can be constructed similarly. Our factorizability results show
that the binding functions constructed this way satisfy the Representation
claim.

The second claim follows from Representation and position independence. Pick
an arbitrary context $\mathbf{c}$ to generate $Z_{\text{context}}$. Then, by
factorizability we can make the substitutions
$Z_{E_{k}}\rightarrow\Gamma_{E}(e_{\pi_{E}^{-1}(k)},k)$ and
$Z_{A_{k}}\rightarrow\Gamma_{A}(a_{\pi_{A}^{-1}(k)},k)$, to obtain

$[\Gamma_{E}(e_{\pi_{E}^{-1}(0)},0),\Gamma_{A}(a_{\pi_{A}^{-1}(0)},0),\Gamma_{E}(e_{\pi_{E}^{-1}(1)},1),\Gamma_{A}(a_{\pi_{A}^{-1}(0)},1)].$

Because of factorizability, the model believes $e_{0}\leftrightarrow
a_{0},e_{1}\leftrightarrow a_{1}$ if $\pi_{E}=\pi_{A}$, and
$e_{0}\leftrightarrow a_{1},e_{1}\leftrightarrow a_{0}$ otherwise. Now,
position independence lets us freely permute $\\{Z_{E_{0}},Z_{E_{1}}\\}$ and
$\\{Z_{A_{0}},Z_{A_{1}}\\}$ without changing beliefs, which achieves the
desired

$[\Gamma_{E}(e_{0},\pi_{E}(0)),\Gamma_{A}(a_{0},\pi_{A}(0)),\Gamma_{E}(e_{1},\pi_{E}(1)),\Gamma_{A}(a_{1},\pi_{A}(1))].$

##  Appendix C Details for Position Independence

RoPE Intervention. In Fig. 2a, the context activations $Z_{\text{context}}$ is
drawn in a line, suggesting a linear form:
$Z_{\text{context}}=[\dots,Z_{E_{0}},\dots,Z_{A_{0}},\dots,Z_{E_{1}},\dots,Z_{A_{1}},\dots]$.
We can equivalently think of $Z_{\text{context}}$ as a set of pairs:
$Z_{\text{context}}=\\{(p,Z_{p})\mid p~{}\text{is an index for a context
token}\\}$. LMs that use Rotary Position Embedding (RoPE) (Su et al., 2021),
such as those in the LLaMA and Pythia families, have architectures that allow
arbitrarily intervention on the apparent position of an activation
$(p,Z_{p})\rightarrow(p^{\prime},Z_{p})$, even if this results in overall
context activations that cannot be written down as a list of activations. This
is because position information is applied at every layer, and not injected
into the residual stream like in absolute position embeddings. Specifically,
equation 16 in Su et al. (2021) provides the definition of RoPE (recreated
verbatim as follows):

$q_{m}^{\intercal}k_{n}=(\mathbf{R}^{d}_{\Theta,m}\mathbf{W}_{q}x_{m})^{\intercal}(\mathbf{R}^{d}_{\Theta,n}\mathbf{W}_{k}x_{n})$
(3)

Then, making the intervention
$\mathbf{R}^{d}_{\Theta,n}\rightarrow\mathbf{R}^{d}_{\Theta,n^{*}}$ changes
the apparent position of the activations at position $n$ to the position at
$n^{*}$.

Is the position dependent bias just a bias? For the purposes of determining if
position encodes binding, the fact that the LM does not substantially change
its beliefs when we switch the positions of the attribute activations (or the
entity activations) suggests that position can only play a limited role.
However, calling the position dependency of attributes a “bias” implies that
it is an artifact that we should correct for. To what extent is this true?

The case for regarding it as a bias is two-fold. First, as discussed by Su et
al. (2021), RoPE exhibits long-term position decay, which systematically
lowers the attention paid to activations that are further away from the query
(i.e. earlier in the context). Plausibly, at some point when computing the
query mechanism, the LM has to make a decision whether to pay attention to the
first or the second attribute, and the presence of the long-term position
decay can bias this decision, leading to the position dependent bias in the
final prediction that we see.

The second reason is that there are systematic and unbiased ways of
calibrating the LM to recover the correct answer, in spite of the position
dependent bias. We discuss two strategies. Because the position dependent bias
modifies the log probs for $A_{0}$ (or $A_{1}$) regardless of which entity is
being queried, we can estimate this effect by averaging the log probs for
$A_{0}$ (or $A_{1}$) for both queries $E_{0}$ and $E_{1}$. Then, when making a
prediction, we can subtract this average from the log probs for $A_{0}$ (or
$A_{1}$). This corresponds to the median calibrated accuracy metric discussed
earlier. The second procedure to mitigate the position dependent bias is an
intervention to set all attribute activations to have the same position, which
limits the amount of bias position dependency can introduce.

These procedures do not require foreknowledge of what the ground truth
predicates are, and hence do not leak knowledge into the prediction process —
if the calibrated LM answers queries correctly, the information must have come
from the context activations and not from the calibration process.

Nonetheless, there are features about the position dependent bias that could
be interesting to study. For example, we might hope to predict the magnitudes
of the position dependent bias based on RoPE’s parameters. However, such an
investigation will most likely involve a deeper mechanistic understanding of
the query system, which we leave as future work.

##  Appendix D Binding Task Details

###  D.1 capitals

Construct a list of one-token names and a list of country-capital pairs that
are also each one-token wide. Then, apply the following template:

⬇

Answer the question based on the context below. Keep the answer short.

Context: {E_0} lives in the capital city of {A_0}.

{E_1} lives in the capital city of {A_1}.

Question: Which city does {qn_subject} live in?

Answer: {qn_subject} lives in the city of

The LM is expected to answer with the capital of the country that is bound to
the queried entity. Note that the LM is expected to simultaneously solve the
factual recall task of looking up the capital city of a country.

###  D.2 parallel

The parallel task uses the same country capital setup, but with the prompt
template:

⬇

Answer the question based on the context below. Keep the answer short.

Context: {E_0} and {E_1} live in the capital cities of {A_0} and {A_1}
respectively.

Question: Which city does {qn_subject} live in?

Answer: {qn_subject} lives in the city of

This prompt format breaks the confounder in the capitals task that entity
always appear in the same sentence as attributes, suggesting binding ID is not
merely a syntactic property.

###  D.3 fruits

The fruits task uses the same set of names, but for attributes it uses a set
of common fruits and food that are one-token wide. The prompt format is:

⬇

Answer the question based on the context below. Keep the answer short.

Context: {E_0} likes eating the {A_0}. {E_1} likes eating the {A_1}
respectively.

Question: What food does {qn_subject} like?

Answer: {qn_subject} likes the

###  D.4 shapes

The shapes tasks have entities which are one-token wide colors, and attributes
which are one-token wide shapes. The prompt looks like:

⬇

Answer the question based on the context below. Keep the answer short.

Context: The {A_0} is {E_0}. The {A_1} is {E_1}.

Question: Which shape is colored {qn_subject}?

Answer: The {qn_subject} shape is

This task inverts the assumption that entities have to be nouns, and
attributes are adjectives.

###  D.5 Bios

This task is adapted from the bias in bios dataset De-Arteaga et al. (2019),
with a prompt format following Hernandez et al. (2023a). The entities are the
set of one-token names, and the attributes are a set of biography descriptions
obtained using the procedure from Hernandez et al. (2023a). The LM is expected
to infer the occupation from this description. This time, the attributes are
typically one sentence long, and are no longer one-token wide. We thus do not
expect the mean interventions for attributes to work, although we may still
expect entity interventions to work. Just inferring the correct occupation is
also a much more challenging task than the other synthetic tasks.

The prompt format is:

⬇

Answer the question based on the context below. Keep the answer short.

Context:

About {E_0}: {A_0}

About {E_1}: {A_1}

Question: What occupation does {qn_subject} have?

Answer: {qn_subject} has the occupation of

##  Appendix E MCQ Task

Multiple choice questions (MCQs) can be formulated as a binding task if we put
the options before the question. This is to force the LM to represent the
binding between label and option text before it sees the questions. We study
the SST-2 task (Socher et al., 2013), which is a binary sentiment
classification task on movie reviews (either positive or negative). Then, the
attributes are single letter labels from A to E, and the entities are
“Positive” and “Negative”.

The prompt is as follows:

⬇

Classify the review using the following options:

{A_0}: {E_0}

{A_1}: {E_1}

Review: {question}

Answer:

Then, when prompted with a question with a certain sentiment, the LM is
expected to retrieve its corresponding label.

###  E.1 Experiments

It turns out that the reversed MCQ format is too out of distribution for
LLaMA-30b to solve. However, we find that the instruction finetuned tulu-13b
model (Wang et al., 2023) is able to solve this task.

We find that the activations for this task are not factorizable in the same
way. Consider the target context:

⬇

C: Negative

A: Positive

and the source context:

⬇

A: Negative

C: Positive

We denote the labels as $L_{0}$ and $L_{1}$, so that $L_{0}$ is A in the first
context and B in the second context. We denote the option texts as $O_{0}$ and
$O_{1}$.

We perform an experiment where we intervene by copying over a suffix of every
line from the source context into the target context, and plot the accuracy
based on whether the intervention successfully changes the belief (Fig. 8).
The right most point of the plot is the control condition where no
interventions are made. The accuracy is near zero because the model currently
believes in the original context. At the left most point, we intervene on the
entire statement, which is a substitution of the entire $Z_{\text{context}}$.
Thus, we observe a near perfect accuracy.

Interestingly, copying over the activations for the tokens corresponding to
“ative” and the whitespace following it suffices for almost completely
changing the belief, despite having a surface token form that is identical at
those two tokens (“ative $\langle$WS$\rangle$ ” for both source and target
contexts). This suggests that those activations captures the binding
information that contains both the label and the option text. This leads to
the conclusion that binding information is bound directly at those
activations, instead of indirectly via binding IDs.

In contrast, binding ID would have predicted that substituting these two
tokens would not have made a difference, because the option activations
$Z_{O}$ should contain only information about the option text and the binding
ID, which is identical for our choice of source and target contexts.

Figure 8: Substitutions for MCQ option suffix

##  Appendix F Generality details

Suppose $\pi$ is a cyclic shift, say $\pi(0)=1,\pi(1)=2,\pi(2)=0$. Then, we
can perform mean interventions based on the cyclic shift on entities as
follows:

$Z_{E_{k}}\rightarrow
Z_{E_{k}}+b_{E}(\pi(k))-b_{E}(k)=Z_{E_{k}}+\Delta_{E}(\pi(k))-\Delta_{E}(k).$

We then expect the belief to follow the same shift, so that the LM believes
$E_{k}\leftrightarrow A_{\pi(k)}$.

Similarly, we can perform mean interventions on attributes as follows:

$Z_{A_{k}}\rightarrow
Z_{A_{k}}+b_{A}(\pi(k))-b_{A}(k)=Z_{A_{k}}+\Delta_{A}(\pi(k))-\Delta_{A}(k).$

However, this time we expect the belief to follow the inverse shift, i.e.
$E_{k}\leftrightarrow A_{\pi^{-1}(k)}$, which is the same as
$E_{\pi(k)}\leftrightarrow A_{k}$.

As usual, we sample $\Delta$ using 500 samples. We perform the intervention
using both cyclic shifts over 3 elements, (i.e. $\pi$ and $\pi^{-1}$), and
report the mean results over these two shifts.

##  Appendix G Geometry details

An experimental challenge we face is that we do not have access to the binding
ID vectors $b_{A},b_{E}$ themselves, only differences between them,
$\Delta_{A},\Delta_{E}$. For clarity of exposition we first describe the
procedure we would perform if we had access to the binding ID vectors, before
describing the actual experiment.

In the ideal case, we would obtain two pairs of binding ID vectors,
$[b_{E}(0),b_{A}(0)],[b_{E}(1),b_{A}(1)]$. Then, we can construct two linear
combinations of these two binding ID vectors as candidate binding IDs,
$[v_{E_{0}},v_{A_{0}}]$ and $[v_{E_{1}},v_{A_{1}}]$. Now, we can take an $n=2$
context $\mathbf{c}$ and intervene on each of
$Z_{E_{0}},Z_{A_{0}},Z_{E_{1}},Z_{A_{1}}$ to change their binding IDs to our
candidate binding IDs. If the model retains its beliefs, then we infer that
the binding IDs are valid.

There two main problems with this procedure. The first is that we only have
access to $\Delta_{A}$ and $\Delta_{E}$ and not $b_{E},b_{A}$. Instead of
choosing $[b_{E}(0),b_{A}(0],[b_{E}(1),b_{A}(1)]$ as our basis vectors, we can
use contexts with $n=3$ to obtain
$[\Delta_{E}(1),\Delta_{A}(1)],[\Delta_{E}(2),\Delta_{A}(2)]$. These new basis
vectors are still linear combinations of binding IDs, and if binding ID
vectors do form a subspace, these would be part of the subspace too.

The second problem is that we cannot arbitrarily set the binding ID vector of
an activation to another binding ID vector. Instead, we can only add vectors
to activations. We thus perform two sets of interventions. We first perform
the mean interventions on the second binding ID pair to turn
$[b_{E}(1),b_{A}(1)]$ into $[b_{E}(0),b_{A}(0)]$. At this point, the LM sees
two entities with the same binding ID and two attributes with the same binding
ID, and is confused. Then, we can add candidate binding vector ID offsets to
these activations.

More precisely, let $\eta,\nu$ be coefficients for the linear combinations of
the basis vectors. Define now
$h_{A}(\eta,\nu)=\eta\Delta_{A}(1)+\nu\Delta_{A}(2)$ and
$h_{E}(\eta,\nu)=\eta\Delta_{E}(1)+\nu\Delta_{E}(2)$ as the candidate binding
vector ID offsets. Then, we add
$[h_{E}(\eta_{0},\nu_{0}),h_{A}(\eta_{0},\nu_{0})]$ and
$[h_{E}(\eta_{1},\nu_{1}),h_{A}(\eta_{1},\nu_{1})]$ to the respective two
pairs of binding IDs, and evaluate if the model has regained its beliefs.

Concretely, the intervention we apply is parameterized by
$(\eta_{0},\nu_{0},\eta_{1},\nu_{1})$ and are as follows:

$Z_{A_{0}}\rightarrow Z_{A_{0}}-\Delta_{A}(0)+h_{A}(\eta_{0},\nu_{0}),\quad
Z_{E_{0}}\rightarrow Z_{E_{0}}-\Delta_{E}(0)+h_{E}(\eta_{0},\nu_{0}),$
$Z_{A_{1}}\rightarrow Z_{A_{1}}-\Delta_{A}(1)+h_{A}(\eta_{1},\nu_{1}),\quad
Z_{E_{1}}\rightarrow Z_{E_{1}}-\Delta_{E}(1)+h_{E}(\eta_{1},\nu_{1}).$

We are now interested in the question: if we have coefficients
$(\eta_{0},\nu_{0})$ and $(\eta_{1},\nu_{1})$, are the binding vectors
constructed from those coefficients valid binding IDs?

In our experiments (Fig. 5), we fix the value of $\eta_{0}$ and $\nu_{0}$ at
varying positions (green circles), and vary $\eta_{1}$ and $\nu_{1}$. We plot
the mean median-calibrated accuracy. We find that near the green circle, the
model is completely confused, responding with near-chance accuracy. This
verifies that the erasure step works as intended. In addition, we find that
there appears to be a binding metric subspace in that as long as candidate
binding IDs are sufficiently far apart, the LM recovers its ability to
distinguish between the two, even when candidate binding IDs are outside of
the convex hull between the three binding IDs used to generate the basis
vectors.