# Approximate Boltzmann Distributions for Nonreversible
Markov Chains

Jacob Calvert<EMAIL_ADDRESS>School of Computer Science, Georgia Institute
of Technology  Dana Randall<EMAIL_ADDRESS>School of Computer Science,
Georgia Institute of Technology

###### Abstract

While powerful theories for the analysis of reversible Markov chains have
enabled significant mathematical advances, nonequilibrium phenomena dominate
the sciences and nonequilibrium chains do not enjoy the same formal
foundations. For instance, the stationary distributions of reversible chains
are fundamentally simpler than those of nonreversible chains because they are
Boltzmann distributions—they can be expressed in terms of a purely local “free
energy” landscape, in analogy with equilibrium statistical physics. In
general, it is impossible to similarly represent the steady states of
nonequilibrium physical systems in a purely local way. However, a series of
recent works on rattling theory (e.g., Chvykov et al., Science (2021))
provides strong evidence that a broad class of such systems nevertheless
exhibit “approximate Boltzmann distributions,” which allow some aspects of the
global distributions to be inferred, at least approximately, from local
information.

We formalize the main claims of this physical theory to identify its hidden
assumptions and demonstrate its basis in the theory of continuous-time Markov
chains. To do so, we decompose an arbitrary stationary distribution $\pi$ into
its “local” part—the exit rates $q$ out of each state—and its “global”
part—the stationary distribution $\psi$ of the embedded “jump” chain. We
explain a variety of experimental results by showing that, for a random state,
$\log\pi$ and $-\\!\log q$ are correlated to the extent that $\log\psi$ and
$-\\!\log q$ are correlated or the ratio of their variances is small. In
particular, the predictions of rattling theory apply when the global part of
$\pi$ varies over fewer scales than its local part. We use this fact to
demonstrate classes of nonreversible chains with stationary distributions that
are exactly of Boltzmann type.

##  1 Introduction

Powerful theories for the analysis of Markov chains primarily apply to
reversible chains. For example, the spectral theory of mixing times relies on
the fact that the transition kernel of a reversible Markov chain is a self-
adjoint linear operator on an appropriate Hilbert space, which is not true of
a nonreversible chain [Cho20]. Similarly, the fundamental component of
electric network theory is a resistor that, by virtue of its symmetry, cannot
model transitions that violate detailed balance [DS84]. The extension of these
and other theories to nonreversible chains is the subject of more recent work,
including a generalization of the spectral gap to nonreversible chains
[Cha23], and an extension of electric networks to the nonreversible case,
using a new component [BF16]. Like these contributions, ours provides a tool
for thinking about nonreversible chains. However, our contribution is not an
extension of an existing theory for reversible chains, rather, it is a
principle that applies to all chains, including nonreversible ones.

Nonreversible chains are worthy of study in part because they converge to
stationarity more quickly than reversible counterparts, which makes them
useful for sampling [DHN00, SSG10, CH13, Bie16, DLP16, RS16]. Additionally,
they model nonequilibrium phenomena across domains, with countless examples in
stochastic thermodynamics [Sch76, Jar97, Cro99, Cro00, Sei12, Eng13, Eng15,
PME16, GHPE16, OGH20] and biochemistry [Hop74, GK81, Qia07, MHL12, OH23]. In
these contexts, “nonreversible” and “nonequilibrium” are synonymous, and the
challenges of studying nonreversible Markov chains are the challenges of
nonequilibrium statistical physics [Eng22]. For example, in analogy with
equilibrium statistical physics, the stationary distribution $\pi$ of a
reversible chain can be expressed as a Boltzmann distribution, i.e., as
proportional to $e^{-\beta E}$ for an “inverse temperature” $\beta$ and an
“energy” function $E$ on the states [OGH20]. This is valuable because $E$ is
“local” in the sense that it is largely independent of the rates that connect
the states, while $\pi$ is “global” because it generally depends on all of the
rates. It is impossible to express the stationary distribution $\pi$ of a
general nonreversible chain in purely local terms, which corresponds to the
defining challenge of nonequilibrium statistical physics [Lan75]. Our main
results identify exceptions to this rule: classes of nonreversible Markov
chains with Boltzmann-type stationary distributions.

Typically, theories that apply arbitrarily “far” from equilibrium can do so
because their statements feature measures of this distance. For example,
nonequilibrium fluctuation–dissipation theorems are statements about the
extent of nonreversibility along a path of states, as quantified by the
product of the ratios of the forward and reverse rates along this path [Cro98,
Cro99, Sei12]. Similarly, bounds on the sensitivity of nonequilibrium steady
states to rate perturbations are phrased in terms of “cycle forces,” which are
sums of log-ratios of the forward and reverse rates around a cycle [GHPE16,
OGH20, OH23]. In this context, our results are surprising because they apply
to nonreversible Markov chains—including chains that fail to be
“microscopically reversible”—despite making no reference to the extent of
their nonreversibility.

###  1.1 Rattling theory as evidence for approximate Boltzmann distributions

Even though the steady-state distribution of a nonequilibrium system cannot in
general be expressed in local terms, rattling theory argues that, for a broad
class of such systems, a local quantity called “rattling” is highly
anticorrelated with the logarithm of this distribution. Hence, the rattling of
a state in a nonequilibrium system is akin to the energy of a state in an
equilibrium system [CE18, CBV+21, JW21, Gol21, Eng22, YBB+22]. According to
rattling theory, if the dynamics of a system are “so complex, nonlinear, and
high-dimensional that no global symmetry or constraint can be found for its
simplification,” then the dynamics amounts to diffusion in an abstract,
continuous state space [CBV+21]. The rattling $R$ of a state $\sigma$ reflects
the diffusivity of the dynamics in the vicinity of $\sigma$. Specifically,
[CBV+21] defines rattling in terms of an estimator $C(\sigma)$ of the local
diffusion tensor as

$R(\sigma)=\frac{1}{2}\log\det C(\sigma),$

and argues that the steady-state probability $\pi$ of a configuration $\sigma$
satisfies

$\pi(\sigma)\propto\exp(-\gamma R(\sigma)),$ (1)

in some approximate sense, for a system-specific constant $\gamma$.

This prediction is supported by experiments with swarms of robots [CBV+21] and
collectives of active microparticles [YBB+22]; simulations of mechanical
networks [CE18] and spin glasses [Gol21]; and a numerical study of the Lorenz
equations [JW21]. Moreover, it has been used to design swarms of robots with
useful emergent behaviors [TBM22].

Rattling is a continuous-space analogue of the exit rate $q$ of a Markov
chain. In this context, the principal claim of rattling theory (1) is a
quantitative version of: “Markov chains spend more time in states that they
exit slowly” [CBV+21]. This claim may seem trivial at first, but it is
not—$\pi$ is global, while $q$ is local—and it cannot be true in general.
Specifically, the Markov chain analogue of (1) is

$\pi_{i}=\frac{1}{Z}q_{i}^{-\gamma},$ (2)

where $\pi_{i}$ is the stationary probability of a discrete state $i$, $Z$ is
a normalization constant, and $\gamma$ is a system-specific constant.

The authors of [CBV+21] attempt to justify the main claim of rattling theory
(1) through a heuristic mathematical treatment of equation (2) for a Markov
chain with random rates. In this model, i.i.d. directed rates connect every
pair of chain’s $N$ states. On the basis of an expansion of the stationary
distribution in reciprocal powers of $N$ and the CLT, they conclude that, when
$N$ is large, $\pi_{i}$ is approximately uniform. Since the exit rates $q_{i}$
from states are roughly the same, $\pi_{i}$ is roughly $q_{i}^{-1}/Z,$ for a
normalization constant $Z$.

There are several issues with this explanation. First, it is based on an
“unrealistic” model. Indeed, [CBV+21] explains that:

> [R]andom transition rates produce only small fluctuations in the steady-
> state distribution on top of a dominant uniform background. This is in sharp
> contrast to what we see for the [robot swarm], where steady-state
> probability piles up almost entirely in certain stable states. …To address
> this, make our model more realistic, and specifically, more like the self-
> organizing systems we are interested in, we can allow the transition rates
> to vary over a wide range of magnitudes.

Second, their derivation fails in the more realistic scenario of heavy-tailed
transition rates, because the CLT is no longer applicable. Despite this, their
numerical studies show that the accuracy of approximating $\pi_{i}$ by
$q_{i}^{-1}/Z$ improves in this case. Third, their explanation predicts that
the accuracy of equation (2) improves as $N\to\infty$ and when the exit rates
are corrected by a quantity involving the corresponding entrance rates.
However, increasing $N$ does not appear to improve the accuracy of equation
(2) in their numerical studies, nor does the correction to the exit rates for
the more realistic scenario.

Our main results explain these observations and, in fact, go beyond the claims
of rattling theory concerning the extent to which nonequilibrium steady states
can approximate Boltzmann distributions. Specifically, we identify conditions
under which the stationary distribution of a Markov chain is exactly a
Boltzmann distribution. Strikingly, these conditions are independent of the
number of states of the chain and apply equally well to reversible and
nonreversible chains.

###  1.2 Main results

Consider a continuous-time Markov chain on a finite state space $S$,
determined by rates $(q_{ij})_{i,j\in S}$ that make the chain irreducible and
produce a stationary distribution $\pi$. These rates also determine the total
exit rate $q_{i}=\sum_{k}q_{ik}$ from a state $i$. We state our results in
terms of the linear correlation coefficient $\rho$ of $\log\pi_{I}$ and
$-\\!\log q_{I}$, for a random state $I\in S$, defined as follows:

$\rho:=\operatorname{\mathbf{Corr}}(-\log
q_{I},\log\pi_{I})=\frac{\operatorname{\mathbf{Cov}}(-\log
q_{I},\log\pi_{I})}{\sqrt{\operatorname{\mathbf{Var}}(\log
q_{I})\operatorname{\mathbf{Var}}(\log\pi_{I})}}.$ (3)

For $\rho$ to be defined, we assume throughout that $q_{I}$ and $\pi_{I}$ are
not constant. Perhaps surprisingly, the specific distribution of $I$ generally
makes no difference to our proofs. Hence, for simplicity, we assume that $I$
is a uniformly random state of $S$.

Heuristically, if $\rho$ is close to $1$, then there is an $L^{2}$ sense in
which $\log\pi_{I}$ is close to $-\gamma\log q_{I}$ for some constant
$\gamma$, hence $\pi_{I}$ is approximately proportional to $q_{I}^{-\gamma}$.
We want to understand what the circumstances that cause $\log\pi$ and $\log q$
to be strongly anticorrelated. As the following example shows, perhaps
unintuitively, a lack of reversibility is not a limitation in this respect.

######  Example 1.1.

Consider the four-state chains $Q_{1}$ and $Q_{2}$ explicitly defined by

$Q_{1}=\begin{pmatrix}[r]{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-4}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}&1&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}\\\
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}&{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-8}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}4}&2\\\
4&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}&{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-16}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}8}\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}16}&8&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}8}&{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-32}\end{pmatrix}\quad\text{and}\quad
Q_{2}=\begin{pmatrix}[r]{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-6}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}&3&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}\\\
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3}&{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-6}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}&1\\\
3&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}&{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-6}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}&3&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}&{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>(4)

For $Q_{1}$ and $Q_{2}$, the product of the rates along the cycle $1\to 2\to
3\to 4\to 1$ (blue) does not equal the product of the rates in the reverse
direction (red), which shows that both chains are nonreversible. For $Q_{1}$,
$\log\pi_{I}$ and $\log q_{I}$ are perfectly anticorrelated for any
(nondegenerate) random state $I$, because both $\pi_{i}$ and $1/q_{i}$ are
proportional to $2^{-i}$. In particular, $\pi_{i}=\frac{1}{Z}q_{i}^{-1}$ for a
normalization constant $Z$. For $Q_{2}$, however, the correlation between
$\log\pi_{I}$ and $\log q_{I}$ is undefined because $q_{I}$ is constant.

It will be convenient to use the notion of a “jump” chain to explain why
$Q_{1}$, but not $Q_{2}$, has a stationary distribution of the form
$\frac{1}{Z}q_{i}^{-1}$. For a continuous-time Markov chain with rates
$(q_{ij})_{i,j\in S}$, the corresponding jump chain is a discrete-time Markov
chain on $S$ with transition probabilities $(p_{ij})_{i,j\in S}$ given by

$p_{ij}=\frac{q_{ij}}{q_{i}}.$

The jump chain also has a stationary distribution, which we denote by $\psi$.

We interpret $\psi$ and $q$ as the “global” and “local” parts of $\pi$. Our
first result expresses the correlation $\rho$ in terms of the correlation
between the scales of the global and local parts of $\pi$, and the ratio of
their variances. We define these quantities as

$\widetilde{\rho}:=\operatorname{\mathbf{Corr}}(-\log
q_{I},\log\psi_{I})\quad\text{and}\quad
r^{2}:=\frac{\operatorname{\mathbf{Var}}(\log\psi_{I})}{\operatorname{\mathbf{Var}}(\log
q_{I})}.$ (5)

In fact, if $\psi$ is constant, then we define $\widetilde{\rho}$ to be $0$
instead of undefined. The correlation $\rho$ is an explicit function of
$\widetilde{\rho}$ and $r$.

######  Theorem 1.

The correlation coefficient $\rho$ satisfies

$\rho=\frac{1+\widetilde{\rho}r}{\sqrt{1+2\widetilde{\rho}r+r^{2}}}.$ (6)

The next result identifies conditions under which $\pi$ is exactly a Boltzmann
distribution. It applies equally well to reversible and nonreversible Markov
chains.

######  Theorem 2.

If $\rho=1$ or $\widetilde{\rho}=1$, then $\pi$ is a Boltzmann distribution
given by

$\pi_{i}=\frac{1}{Z}q_{i}^{-(1+\widetilde{\rho}r)}.$ (7)

One implication of Theorem 2 is that, if $\rho=1$ or $\widetilde{\rho}=1$,
then ratios of stationary probabilities are simple functions of the
corresponding exit rates:

$\frac{\pi_{i}}{\pi_{j}}=\left(\frac{q_{j}}{q_{i}}\right)^{(1+\widetilde{\rho}r)}.$

These ratios have a variety of uses in the context of Markov chain samplers.
For example, they can be used to construct rate perturbations that improve the
speed of convergence and reduce asymptotic variance [LM08, RS16].

An immediate consequence of Theorems 1 and 2 is that $\pi$ has a Boltzmann
distribution if $r=0$.

######  Corollary 1.2.

If $r=0$, then $\pi_{i}=q_{i}^{-1}/Z$.

Corollary 1.2 explains why the chain determined by $Q_{1}$ in Example 1.1 has
a Boltzmann stationary distribution. Namely, the transition probability matrix
$P_{1}$ of the corresponding jump chain is

$P_{1}=\begin{pmatrix}0&\frac{1}{2}&\frac{1}{4}&\frac{1}{4}\\\\[2.0pt]
\frac{1}{4}&0&\frac{1}{2}&\frac{1}{4}\\\\[2.0pt]
\frac{1}{4}&\frac{1}{4}&0&\frac{1}{2}\\\\[2.0pt]
\frac{1}{2}&\frac{1}{4}&\frac{1}{4}&0\end{pmatrix}.$

Since $P_{1}$ is doubly stochastic, it has a uniform stationary distribution
$\psi$, hence $r=0$.

Our third main result shows that Theorem 2 is robust, in the sense that if
$\rho$ or $\widetilde{\rho}$ is nearly $1$, then $\pi$ is approximately a
Boltzmann distribution of the form (7). We make this precise with the
following definition.

######  Definition 1.3.

We say that $\pi$ is $k$-Boltzmann for a number $k\geq 1$ if

$\forall i\in S,\quad\pi_{i}\cdot
Zq_{i}^{(1+\widetilde{\rho}r)}\in\left[k^{-1},k\right].$

In particular, if $\pi$ is $1$-Boltzmann, then
$\pi_{i}=q_{i}^{-(1+\widetilde{\rho}r)}/Z$.

######  Theorem 3.

Let $k=\exp(4\sqrt{|S|\mathcal{E}})$, in terms of

$\mathcal{E}=(1-\rho^{2})\operatorname{\mathbf{Var}}(\log\pi_{I})=r^{2}(1-\widetilde{\rho}^{2})\operatorname{\mathbf{Var}}(\log
q_{I}).$

Then, $\pi$ is $k$-Boltzmann.

According to Theorem 3, the extent to which a stationary distribution
approximates a Boltzmann distribution is determined by $\rho$ or
$\widetilde{\rho}$ and $r^{2}$. Note that the equality of the two expressions
for $\mathcal{E}$ follows from the formula for $\rho$ (Theorem 1). We include
them both to make it clear that Theorem 3 implies Theorem 2.

In the next section, we explain how a stationary distribution can be
decomposed into its local and global parts. In particular, we obtain a formula
for $\log\pi_{i}$ in terms of $\log q_{i}$ and $\log\psi_{i}$, which
facilitates the proof of Theorem 1.

##  2 The local and global parts of a stationary distribution

We prove Theorem 1 in this section. We begin by exploring the relationship
between a continuous-time Markov chain and its jump chain. The following fact
is standard; we include its proof for completeness.

######  Proposition 2.1.

The stationary distributions of a Markov chain $\pi$ and its jump chain $\psi$
satisfy

$\pi_{i}=\frac{\psi_{i}/q_{i}}{\sum_{k}\psi_{k}/q_{k}}.$

###### Proof.

The stationary distribution $\psi$ satisfies

$\psi_{i}=\sum_{j\neq i}\psi_{j}p_{ji}=\sum_{j\neq
i}\psi_{j}\frac{q_{ji}}{q_{j}}.$

The first equality holds because $\psi$ is the stationary distribution of $P$;
the second holds by definition of the jump chain transition probabilities
$p_{ji}=q_{ji}/q_{j}$. This implies that ${\psi}/{q}$ is invariant under $Q$:

$\frac{\psi_{i}}{q_{i}}q_{i}=\sum_{j\neq i}\frac{\psi_{j}}{q_{j}}q_{ji}.$

Normalizing ${\psi}/{q}$ therefore gives the stationary distribution $\pi$ of
$Q$. ∎

The next result follows from simply taking the logarithm of both sides of
equation 2.1. We state it separately because we will use it several times.

######  Proposition 2.2.

The stationary distribution $\pi$ satisfies

$\log\pi_{i}=-\log
q_{i}+\log\psi_{i}-\log\Big{(}\sum_{k}\psi_{k}/q_{k}\Big{)}.$ (8)

Note that $\sum_{k}\psi_{k}/q_{k}$ is a constant, so it does not affect the
correlation in equation (3).

We now prove Theorem 1, which states that $\rho$ satisfies

$\rho=\frac{1+\widetilde{\rho}r}{\sqrt{1+2\widetilde{\rho}r+r^{2}}}.$

The proof is a straightforward consequence of equation (8).

###### Proof of Theorem 1.

Assume that $\psi$ is not constant, as Equation 6 clearly holds otherwise. By
equation (8) and because $\log(\sum_{k}\psi_{k}/q_{k})$ is a constant which
does not affect the correlation, $\rho$ satisfies

$\rho\stackrel{{\scriptstyle\eqref{log
pi}}}{{=}}\operatorname{\mathbf{Corr}}\left(-\log q_{I},-\log
q_{I}+\log\psi_{I}-\log\Big{(}\sum_{k}\psi_{k}/q_{k}\Big{)}\right)=\operatorname{\mathbf{Corr}}(-\log
q_{I},-\log q_{I}+\log\psi_{I}).$ (9)

For any two random variables $X$ and $Y$ with positive, finite variances, the
correlation coefficient of $X$ and $X+Y$ satisfies

$\operatorname{\mathbf{Corr}}(X,X+Y)=\frac{\operatorname{\mathbf{Var}}(X)+\operatorname{\mathbf{Cov}}(X,Y)}{\sqrt{\operatorname{\mathbf{Var}}(X)\left(\operatorname{\mathbf{Var}}(X)+2\operatorname{\mathbf{Cov}}(X,Y)+\operatorname{\mathbf{Var}}(Y)\right)}}.$

With some algebra, we can rewrite this equation in terms of
$s=\operatorname{\mathbf{Corr}}(X,Y)$ and
$t^{2}=\frac{\operatorname{\mathbf{Var}}(Y)}{\operatorname{\mathbf{Var}}(X)}$
as

$\operatorname{\mathbf{Corr}}(X,X+Y)=\frac{1+st}{\sqrt{1+2st+t^{2}}}.$

To conclude the proof, we apply this fact to equation (9) with $X=-\log q_{I}$
and $Y=\log\psi_{I}$, hence $s=\widetilde{\rho}$ and $t=r$. ∎

Figure 1 visualizes the contours of $\rho$ as a function of $r^{2}$ and
$\widetilde{\rho}$. When $r^{2}$ is close to $0$, the contours of $\rho$ are
nearly vertical lines, which reflects the fact that $\rho=1-O(r^{2})$ as
$r^{2}\to 0$ with $\widetilde{\rho}$ held constant. As $r^{2}\to\infty$ is
large, the contours become horizontal lines, which reflects the fact that
$\rho=\widetilde{\rho}+O(r^{-1})$ as $r^{2}\to\infty$ with $\widetilde{\rho}$
held constant. Both of these features are apparent from equation (6).

Figure 1: Contours of $\rho$ in the $(r^{2},\widetilde{\rho})$ strip, a subset
of $[0,\infty)\times[-1,1]$. The quantity $r^{2}$ is the ratio of the number
of exponential scales over which the global and local parts of $\pi$ vary,
while $\widetilde{\rho}$ is the linear correlation coefficient of these scales
(5). Loosely speaking, the predictions of rattling theory hold in the gold-
shaded region.

We note that there is a simple lower bound of $\rho$ that does not feature
$\widetilde{\rho}$, which is useful for demonstrating examples in which
$\rho=1$.

######  Corollary 2.3.

If $r^{2}<1$, then

$\rho\geq\frac{1-r}{1+r}.$ (10)

###### Proof.

By Theorem 1,

$\rho=\frac{1+\widetilde{\rho}r}{\sqrt{1+2\widetilde{\rho}r+r^{2}}}.$

The numerator $1+\widetilde{\rho}r$ is strictly positive when $r^{2}<1$. To
bound below $\rho$, it therefore suffices to use the fact that
$|\widetilde{\rho}|\leq 1$ to bound below the numerator by $1-r$ and above the
denominator by $\sqrt{1+2r+r^{2}}=1+r$. ∎

##  3 Exact and approximate Boltzmann distributions

In this section, we prove Theorems 2 and 3 which quantify when we have
Boltzmann or approximate Boltzmann distributions. We restate both results here
for convenience.

######  Theorem 2.

If $\rho=1$ or $\widetilde{\rho}=1$, then $\pi$ is a Boltzmann distribution
given by

$\pi_{i}=\frac{1}{Z}q_{i}^{-(1+\widetilde{\rho}r)}.$

Theorem 2 is a consequence of Theorem 3, but we briefly mention how to prove
part of the former result directly. Specifically, we can use Proposition 8 and
Theorem 1 to prove the $\rho=1$ case of Theorem 2, as follows. Note that, if
$\rho=1$, then every pair $(-\log q_{i},\log\pi_{i})$ must fall on a line with
a slope of
$\sqrt{\frac{\operatorname{\mathbf{Var}}(\log\pi_{I})}{\operatorname{\mathbf{Var}}(\log
q_{I})}}$. A short calculation using Proposition 8 shows that this slope
equals $\sqrt{1+2\widetilde{\rho}r+r^{2}}$, hence

$\pi_{i}=\frac{1}{Z}q_{i}^{-\sqrt{1+2\widetilde{\rho}r+r^{2}}}\stackrel{{\scriptstyle\eqref{main
est}}}{{=}}\frac{1}{Z}q_{i}^{-(1+\widetilde{\rho}r)}.$

The second equality is due to Theorem 1 and the assumption that $\rho=1$.

While the preceding argument settles the $\rho=1$ case of Theorem 2, instead
of separately proving the $\widetilde{\rho}=1$ case, we will simply use
Theorem 3, restated below. Recall that $\pi$ is $k$-Boltzmann if, for every
$i\in S$, $\pi_{i}$ is within a factor of $k$ of
$q_{i}^{-(1+\widetilde{\rho}r)}/Z$.

######  Theorem 3.

Let $k=\exp(4\sqrt{|S|\mathcal{E}})$, in terms of

$\mathcal{E}=(1-\rho^{2})\operatorname{\mathbf{Var}}(\log\pi_{I})=r^{2}(1-\widetilde{\rho}^{2})\operatorname{\mathbf{Var}}(\log
q_{I}).$

Then, $\pi$ is $k$-Boltzmann.

Theorem 3 implies Theorem 2.

###### Proof of Theorem 2.

If $\rho=1$ or $\widetilde{\rho}=1$, then $\mathcal{E}=0$, in which case $\pi$
is $1$-Boltzmann by Theorem 3. ∎

Next, to prove Theorem 3, we consider the linear function of $-\log q_{I}$
that minimizes the “error”

$\mathcal{E}(m,b):=\mathbf{E}\left((\log\pi_{I}-(-m\log q_{I}-b))^{2}\right).$

We choose a squared error because we intend to relate it to the correlation
coefficient $\rho$. Denote the minimizer of $\mathcal{E}(m,b)$ by
$(m_{\ast},b_{\ast}):=\arg\min_{(m,b)\in\mathbb{R}^{2}}\mathcal{E}(m,b)$ and
the least error by $\mathcal{E}:=\mathcal{E}(m_{\ast},b_{\ast})$.

######  Proposition 3.1.

The least error $\mathcal{E}$ satisfies

$\mathcal{E}=r^{2}(1-\widetilde{\rho}^{2})\operatorname{\mathbf{Var}}(\log
q_{I})=(1-\rho^{2})\operatorname{\mathbf{Var}}(\log\pi_{I}),$

where $m_{\ast}=(1+\widetilde{\rho}r)$.

###### Proof.

For random variables $X$ and $Y$, the linear function
$f:\mathbb{R}\to\mathbb{R}$ that minimizes $\mathbf{E}((Y-f(X))^{2})$ is

$f_{\ast}(x)=\frac{\operatorname{\mathbf{Cov}}(X,Y)}{\operatorname{\mathbf{Var}}(X)}(x-\mathbf{E}(X))+\mathbf{E}(Y),$
(11)

while a short calculation shows that

$\mathbf{E}\left((Y-f_{\ast}(X))^{2}\right)=\operatorname{\mathbf{Var}}\left(Y-\frac{\operatorname{\mathbf{Cov}}(X,Y)}{\operatorname{\mathbf{Var}}(X)}X\right).$
(12)

If $X=-\log q_{I}$ and $Y=\log\pi_{I}$, then the slope of $f_{\ast}$ equals

$\frac{\operatorname{\mathbf{Cov}}(X,Y)}{\operatorname{\mathbf{Var}}(X)}\stackrel{{\scriptstyle\eqref{log
pi}}}{{=}}\frac{\operatorname{\mathbf{Var}}(\log
q_{I})+\operatorname{\mathbf{Cov}}(-\log
q_{I},\log\psi_{I})}{\operatorname{\mathbf{Var}}(\log
q_{I})}=1+\widetilde{\rho}r.$ (13)

Equations (11) and (13) imply that $m_{\ast}=(1+\widetilde{\rho}r)$, while
$\mathcal{E}$ satisfies

$\mathcal{E}\stackrel{{\scriptstyle\eqref{best
mse}}}{{=}}\operatorname{\mathbf{Var}}\left(Y-\frac{\operatorname{\mathbf{Cov}}(X,Y)}{\operatorname{\mathbf{Var}}(X)}X\right)\stackrel{{\scriptstyle\eqref{astar}}}{{=}}\operatorname{\mathbf{Var}}\left(\log\pi_{I}+(1+\widetilde{\rho}r)\log
q_{I}\right)\stackrel{{\scriptstyle\eqref{log
pi}}}{{=}}\operatorname{\mathbf{Var}}\left(\log\psi_{I}+\widetilde{\rho}r\log
q_{I}\right).$

To conclude the calculation of the error, recall that
$\widetilde{\rho}r=\frac{\operatorname{\mathbf{Cov}}(-\log
q_{I},\log\psi_{I})}{\operatorname{\mathbf{Var}}(\log q_{I})}$, hence

$\displaystyle\operatorname{\mathbf{Var}}\left(\log\psi_{I}+\widetilde{\rho}r\log
q_{I}\right)$
$\displaystyle=\operatorname{\mathbf{Var}}(\log\psi_{I})+2\widetilde{\rho}r\operatorname{\mathbf{Cov}}(\log
q_{I},\log\psi_{I})+(\widetilde{\rho}r)^{2}\operatorname{\mathbf{Var}}(\log
q_{I})$
$\displaystyle=r^{2}(1-\widetilde{\rho}^{2})\operatorname{\mathbf{Var}}(\log
q_{I}).$

Lastly, note that
$r^{2}(1-\widetilde{\rho}^{2})\operatorname{\mathbf{Var}}(\log
q_{I})=(1-\rho^{2})\operatorname{\mathbf{Var}}(\log\pi_{I})$ by Theorem 1. ∎

We now bound absolute differences of the form
$|\log\pi_{i}-(-(1+\widetilde{\rho}r)\log q_{i}-b_{\ast})|$ in terms of
$\mathcal{E}$.

######  Proposition 3.2.

Denote $\nu_{i}=\frac{1}{Z}q_{i}^{-(1+\widetilde{\rho}r)}$. Then,

$\max\left\\{\frac{\pi_{i}}{\pi_{j}}\cdot\frac{\nu_{j}}{\nu_{i}},\frac{\pi_{j}}{\pi_{i}}\cdot\frac{\nu_{i}}{\nu_{j}}\right\\}\leq\exp\left(2\sqrt{|S|\mathcal{E}}\right).$

###### Proof.

The ratio $\pi_{i}/\nu_{i}$ satisfies

$\frac{\pi_{i}}{\nu_{i}}=Zq_{i}^{(1+\widetilde{\rho}r)}\pi_{i}=Z\exp\left(\log\pi_{i}+(1+\widetilde{\rho}r)\log
q_{i}\right).$

Using this fact twice gives

$\frac{\pi_{i}}{\pi_{j}}\cdot\frac{\nu_{j}}{\nu_{i}}=\exp\left(\log\pi_{i}+(1+\widetilde{\rho}r)\log
q_{i}+b_{\ast}-(\log\pi_{j}+(1+\widetilde{\rho}r)\log q_{j}+b_{\ast})\right).$

For brevity, denote the quantity $\log\pi_{i}+(1+\widetilde{\rho}r)\log
q_{i}+b_{\ast}$ by $x_{i}$. The preceding equation implies that

$\max\left\\{\frac{\pi_{i}}{\pi_{j}}\cdot\frac{\nu_{j}}{\nu_{i}},\frac{\pi_{j}}{\pi_{i}}\cdot\frac{\nu_{i}}{\nu_{j}}\right\\}=\exp\left(|x_{i}-x_{j}|\right).$

We bound above $|x_{i}-x_{j}|$ using the triangle inequality and the fact that
$\|y\|_{\infty}\leq\|y\|_{2}$ for every $y\in\mathbb{R}^{|S|}$:

$|x_{i}-x_{j}|\leq 2\|x\|_{\infty}\leq 2\|x\|_{2}.$

Because $I$ is uniformly random in $S$, $\mathcal{E}$ satisfies
$\|x\|_{2}=\sqrt{|S|\mathcal{E}}$, which implies the claimed bound. ∎

We use Proposition 3.2 to prove Theorem 3, which states that $\pi$ is
$k$-Boltzmann for $k=\exp(4\sqrt{|S|\mathcal{E}})$. We continue to denote
$\nu_{i}=\frac{1}{Z}q_{i}^{-(1+\widetilde{\rho}r)}$.

###### Proof of Theorem 3.

Fix a state $i\in S$. Proposition 3.2 implies that, if
$k=\exp(2\sqrt{|S|\mathcal{E}})$, then

$\forall j\in
S,\quad\pi_{j}\in\left[k^{-1}\frac{\pi_{i}}{\nu_{i}}\nu_{j},k\frac{\pi_{i}}{\nu_{i}}\nu_{j}\right].$

A second application of Proposition 3.2 shows that

$\frac{\pi_{i}}{\nu_{i}}=\sum_{j}\left(\frac{\nu_{j}}{\nu_{i}}\cdot\frac{\pi_{i}}{\pi_{j}}\right)\pi_{j}\in\left[k^{-1},k\right].$

We conclude that

$\forall j\in S,\quad\pi_{j}\in\left[k^{-2}\nu_{j},k^{2}\nu_{j}\right],$

so $\pi$ is $k^{2}$-Boltzmann according to Definition 1.3.

∎

##  4 Perfect correlation in a nonreversible chain

As we highlighted in Section 1, Theorem 2 is surprising in the context of
results about nonequilibrium systems, because it makes no reference to the
extent of a Markov chain’s nonreversibility. We can use Corollary 1.2 to
identify classes of Markov chains with stationary distributions that are
exactly of Boltzmann type. This section generalizes Example 1.1 to show that
it is possible for a nonreversible chain to exhibit perfect correlation (i.e.,
$\rho=1$), even when the chain has arbitrarily large “cycle forces,” defined
below. By Theorem 2, perfect correlation implies that
$\pi_{i}=\frac{1}{Z}q_{i}^{-(1+\widetilde{\rho}r)}$.

Recall that a continuous-time Markov chain on a finite state space satisfies
detailed balance if and only if, for every sequence of states
$i_{1},i_{2},\dots,i_{n}$,

$q_{i_{1}i_{2}}q_{i_{2}i_{3}}\cdots
q_{i_{n-1}i_{n}}q_{i_{n}i_{1}}=q_{i_{2}i_{1}}q_{i_{3}i_{2}}\cdots
q_{i_{n}i_{n-1}}q_{i_{1}i_{n}}.$

Accordingly, we can measure the extent of the failure of detailed balance in
terms of cycle forces of the form

$\log\left(\frac{q_{i_{1}i_{2}}q_{i_{2}i_{3}}\cdots
q_{i_{n-1}i_{n}}q_{i_{n}i_{1}}}{q_{i_{2}i_{1}}q_{i_{3}i_{2}}\cdots
q_{i_{n}i_{n-1}}q_{i_{1}i_{n}}}\right),$

for various choices of cycle $i_{1}\to i_{2}\to\cdots i_{n}\to i_{1}$, where
$i_{1}$ through $i_{n}$ are distinct states. To ensure that cycle forces are
defined, we consider them only in the context of Markov chains that satisfy
“microscopic reversibility,” i.e., $q_{ij}>0$ if and only if $q_{ji}>0$. We
can define cycle forces analogously for the corresponding jump chain,
replacing $q_{ij}$ with $p_{ij}$.

The next result states that the correlation can be perfect despite the
spectacular failure of detailed balance.

######  Proposition 4.1.

For every $n\geq 3$, there exists a continuous-time Markov chain on
$\\{1,\dots,n\\}$ such that $\rho=1$, even though $1\to 2\to\cdots\to n\to 1$
has a cycle force of $n(n-3)\log 2$.

The idea of the proof is to find a transition probability matrix $P$ that is
doubly stochastic and has a cycle force that grows with the number of states,
to serve as the jump chain for a rate matrix $Q$. If we define $Q$ according
to $q_{ij}=p_{ij}q_{i}$ for some choice of $q_{i}$, then $P$ and $Q$ have the
same cycle forces because

$\log\left(\frac{q_{i_{1}i_{2}}q_{i_{2}i_{3}}\cdots
q_{i_{n-1}i_{n}}q_{i_{n}i_{1}}}{q_{i_{2}i_{1}}q_{i_{3}i_{2}}\cdots
q_{i_{n}i_{n-1}}q_{i_{1}i_{n}}}\right)=\log\left(\frac{p_{i_{1}i_{2}}p_{i_{2}i_{3}}\cdots
p_{i_{n-1}i_{n}}p_{i_{n}i_{1}}}{p_{i_{2}i_{1}}p_{i_{3}i_{2}}\cdots
p_{i_{n}i_{n-1}}p_{i_{1}i_{n}}}\right),$ (14)

for every sequence of distinct states $i_{1},\cdots,i_{n}$. Moreover, since
$P$ is doubly stochastic, $\psi$ is uniform, hence $r^{2}=0$ and Corollary 1.2
implies that $\rho=1$.

The transition matrix that we use specializes to the following ones when there
are three, four, or five states:

$P_{3}=\begin{pmatrix}0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{2}}\\\\[2.0pt]
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{2}}&0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}\\\\[2.0pt]
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{2}}&0\end{pmatrix},\quad
P_{4}=\begin{pmatrix}0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&\frac{1}{4}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{4}}\\\\[2.0pt]
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{4}}&0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&\frac{1}{4}\\\\[2.0pt]
\frac{1}{4}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{4}}&0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}\\\\[2.0pt]
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&\frac{1}{4}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{4}}&0\end{pmatrix},\quad
P_{5}=\begin{pmatrix}0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&\frac{1}{4}&\frac{1}{8}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{8}}\\\\[2.0pt]
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{8}}&0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&\frac{1}{4}&\frac{1}{8}\\\\[2.0pt]
\frac{1}{8}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{8}}&0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&\frac{1}{4}\\\\[2.0pt]
\frac{1}{4}&\frac{1}{8}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{8}}&0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}\\\\[2.0pt]
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\frac{1}{2}}&\frac{1}{4}&\frac{1}{8}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\frac{1}{8}}&0\end{pmatrix}.$
(15)

The rates colored blue follow the cycle $1\to 2\to\cdots\to n\to 1$ in the
forward direction, while the rates colored red follow it in the reverse
direction. The ratio of the product of the blue rates to the product of the
red rates equals $2^{n-3}$.

###### Proof of Proposition 4.1.

Consider the transition probability matrix

$P_{n}=\begin{pmatrix}0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}}&a_{2}&\cdots&a_{n-2}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a_{n-1}}\\\
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a_{n-1}}&0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}}&\cdots&a_{n-3}&a_{n-2}\\\
a_{n-2}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a_{n-1}}&0&\cdots&a_{n-4}&a_{n-3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
a_{2}&a_{3}&a_{4}&\cdots&0&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}}\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}}&a_{2}&a_{3}&\cdots&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a_{n-1}}&0\end{pmatrix},$
(16)

defined in terms of

$a_{i}=\begin{cases}2^{-i}&1\leq i\leq n-2\\\ 2^{-n+2}&i=n-1.\end{cases}$ (17)

The matrix $P_{n}$ is doubly stochastic because its row sums and column sums
equal $\sum_{i=1}^{n-1}a_{i}=1$. Moreover, denoting $i_{j}=j$ for $1\leq j\leq
n$, the cycle force satisfies

$\log\left(\frac{p_{i_{1}i_{2}}p_{i_{2}i_{3}}\cdots
p_{i_{n-1}i_{n}}p_{i_{n}i_{1}}}{p_{i_{2}i_{1}}p_{i_{3}i_{2}}\cdots
p_{i_{n}i_{n-1}}p_{i_{1}i_{n}}}\right)\stackrel{{\scriptstyle\eqref{four state
P}}}{{=}}\log\left(\frac{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a_{1}}^{n}}{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a_{n-1}}^{n}}\right)\stackrel{{\scriptstyle\eqref{a
seq}}}{{=}}n(n-3)\log 2.$

By equation (14), this is also the cycle force under $Q$ for any rates
$q_{ij}$ obtained as $p_{ij}q_{i}$ for some choice of exit rates $q$. By
Corollary 1.2, so long as $q$ is not constant, then $\rho=1$. ∎

##  5 Conclusion and directions for future work

Theorems 2 and 3 show that, for the stationary distribution $\pi$ of a Markov
chain to be exactly or approximately equal to a particular Boltzmann
distribution, it suffices for one of the correlations, $\rho$ or
$\widetilde{\rho}$, to be equal to or close to $1$, respectively. This is
significant because these conditions apply equally well to reversible and
nonreversible chains, and they make no reference to the extent of
nonreversibility, in contrast with results typical of stochastic
thermodynamics. Beyond this, our results explain the numerical and
experimental results associated with rattling theory, and they may be valuable
to the design of Markov chain samplers.

Theorem 1 explains why, among the many possible ways to quantify dependence,
the linear correlation coefficient is a natural choice: it has a simple
formula in terms of the local and global parts of $\pi$. This choice leads us,
in the proof of Theorem 3, to use an $L^{2}$ error to quantify the discrepancy
between $\log\pi_{i}$ and $-(1+\widetilde{\rho}r)\log q_{i}$, so that this
error is a function of $\rho$ and $\widetilde{\rho}$. However, we ultimately
apply it to bound an $L^{\infty}$ discrepancy, which introduces a factor of
$\sqrt{|S|}$ into the conclusion of Theorem 3. An alternative approach is to
quantify the extent to which $\pi$ and $\frac{1}{Z}q_{i}^{-\gamma}$ differ,
using one of the many measures of statistical distance between two probability
distributions on a finite set (e.g., total variation, relative entropy, chi-
squared divergence). In the special case when $\gamma=1$, regardless of the
choice of statistical distance, the difference between $\pi$ and
$\frac{1}{Z}q_{i}^{-1}$ reduces to some notion of non-uniformity for $\psi$.
This is no surprise in the context of Proposition 2.1.

A promising direction for future work is the extension of Theorems 2 and 3
using perturbation bounds for the stationary distributions of Markov chains,
like those of [CM00, CM01] for discrete-time chains and those of [Liu12,
OGH20] for continuous-time ones. For example, if the jump chain associated
with a Markov chain is a small perturbation of a doubly-stochastic chain, then
these results can be used to bound the non-uniformity of $\psi$, hence the
ratio $r^{2}$ which appears in the statement of Theorem 3. The bound of [CM00]
in particular would result in an estimate of $r^{2}$ involving the hitting
times of the doubly stochastic chain. More broadly, future work could relate
the quality of being close to a Boltzmann distribution to other, familiar
properties of a chain. Lastly, future work could consider the analogues of our
results for discrete-time chains.

## Acknowledgements

We thank Thomas Berrueta for helpful discussions regarding the content of
[CBV+21]. The authors are supported by the National Science Foundation (NSF)
award CCF-2106687 and by U.S. Army Research Office (ARO) award MURI
W911NF-19-1-0233. Part of this work was completed while the second author was
visiting the Simons Laufer Mathematical Sciences Institute (formerly the
Mathematical Sciences Research Institute) in Berkeley, CA, in Fall 2023.

## References

  * [BF16] Márton Balázs and Áron Folly.  An electric network for nonreversible Markov chains.  The American Mathematical Monthly, 123(7):657–682, 2016.
  * [Bie16] Joris Bierkens.  Non-reversible Metropolis-Hastings.  Statistics and Computing, 26(6):1213–1228, 2016.
  * [CBV+21] Pavel Chvykov, Thomas A. Berrueta, Akash Vardhan, William Savoie, Alexander Samland, Todd D. Murphey, Kurt Wiesenfeld, Daniel I. Goldman, and Jeremy L. England.  Low rattling: A predictive principle for self-organization in active collectives.  Science, 371(6524):90–95, 2021.
  * [CE18] Pavel Chvykov and Jeremy England.  Least-rattling feedback from strong time-scale separation.  Phys. Rev. E, 97:032115, Mar 2018.
  * [CH13] Ting-Li Chen and Chii-Ruey Hwang.  Accelerating reversible Markov chains.  Statistics & Probability Letters, 83(9):1956–1962, 2013.
  * [Cha23] Sourav Chatterjee.  Spectral gap of nonreversible Markov chains.  arXiv preprint arXiv:2310.10876, 2023.
  * [Cho20] Michael C.H. Choi.  Metropolis–Hastings reversiblizations of non-reversible Markov chains.  Stochastic Processes and their Applications, 130(2):1041–1073, 2020\.
  * [CM00] Grace E. Cho and Carl D. Meyer.  Markov chain sensitivity measured by mean first passage times.  volume 316, pages 21–28. 2000.  Conference Celebrating the 60th Birthday of Robert J. Plemmons (Winston-Salem, NC, 1999).
  * [CM01] Grace E. Cho and Carl D. Meyer.  Comparison of perturbation bounds for the stationary distribution of a Markov chain.  Linear Algebra Appl., 335:137–150, 2001.
  * [Cro98] Gavin E. Crooks.  Nonequilibrium measurements of free energy differences for microscopically reversible Markovian systems.  Journal of Statistical Physics, 90(5):1481–1487, 1998.
  * [Cro99] Gavin E. Crooks.  Entropy production fluctuation theorem and the nonequilibrium work relation for free energy differences.  Phys. Rev. E, 60:2721–2726, Sep 1999.
  * [Cro00] Gavin E. Crooks.  Path-ensemble averages in systems driven far from equilibrium.  Phys. Rev. E, 61:2361–2366, Mar 2000.
  * [DHN00] Persi Diaconis, Susan Holmes, and Radford M. Neal.  Analysis of a nonreversible Markov chain sampler.  The Annals of Applied Probability, 10(3):726 – 752, 2000.
  * [DLP16] A. B. Duncan, T. Lelièvre, and G. A. Pavliotis.  Variance reduction using nonreversible Langevin samplers.  Journal of Statistical Physics, 163(3):457–491, 2016.
  * [DS84] Peter G. Doyle and J. Laurie Snell.  Random walks and electric networks, volume 22 of Carus Mathematical Monographs.  Mathematical Association of America, Washington, DC, 1984.
  * [Eng13] Jeremy L. England.  Statistical physics of self-replication.  The Journal of Chemical Physics, 139(12):121923, 08 2013.
  * [Eng15] Jeremy L. England.  Dissipative adaptation in driven self-assembly.  Nature Nanotechnology, 10(11):919–923, 2015.
  * [Eng22] Jeremy L. England.  Self-organized computation in the far-from-equilibrium cell.  Biophysics Reviews, 3(4):041303, 12 2022.
  * [GHPE16] Todd R. Gingrich, Jordan M. Horowitz, Nikolay Perunov, and Jeremy L. England.  Dissipation bounds all steady-state current fluctuations.  Phys. Rev. Lett., 116:120601, Mar 2016.
  * [GK81] A Goldbeter and D E Koshland.  An amplified sensitivity arising from covalent modification in biological systems.  Proceedings of the National Academy of Sciences, 78(11):6840–6844, 1981.
  * [Gol21] Jacob Gold.  Self-organized fine-tuned response in a driven spin glass.  PhD thesis, Massachusetts Institute of Technology, February 2021.
  * [Hop74] J. J. Hopfield.  Kinetic proofreading: A new mechanism for reducing errors in biosynthetic processes requiring high specificity.  Proceedings of the National Academy of Sciences, 71(10):4135–4139, 1974.
  * [Jar97] C. Jarzynski.  Nonequilibrium equality for free energy differences.  Phys. Rev. Lett., 78:2690–2693, Apr 1997.
  * [JW21] Zachary Jackson and Kurt Wiesenfeld.  Emergent, linked traits of fluctuation feedback systems.  Phys. Rev. E, 104:064216, Dec 2021.
  * [Lan75] Rolf Landauer.  Inadequacy of entropy and entropy derivatives in characterizing the steady state.  Phys. Rev. A, 12:636–638, Aug 1975.
  * [Liu12] Yuanyuan Liu.  Perturbation bounds for the stationary distributions of Markov chains.  SIAM J. Matrix Anal. Appl., 33(4):1057–1074, 2012.
  * [LM08] Fabrizio Leisen and Antonietta Mira.  An extension of Peskun and Tierney orderings to continuous time Markov chains.  Statist. Sinica, 18(4):1641–1651, 2008.
  * [MHL12] Arvind Murugan, David A. Huse, and Stanislas Leibler.  Speed, dissipation, and error in kinetic proofreading.  Proceedings of the National Academy of Sciences, 109(30):12034–12039, 2012.
  * [OGH20] Jeremy A. Owen, Todd R. Gingrich, and Jordan M. Horowitz.  Universal thermodynamic bounds on nonequilibrium response with biochemical applications.  Phys. Rev. X, 10:011066, Mar 2020.
  * [OH23] Jeremy A. Owen and Jordan M. Horowitz.  Size limits the sensitivity of kinetic schemes.  Nature Communications, 14(1):1280, 2023.
  * [PME16] Nikolay Perunov, Robert A. Marsland, and Jeremy L. England.  Statistical physics of adaptation.  Phys. Rev. X, 6:021036, Jun 2016.
  * [Qia07] Hong Qian.  Phosphorylation energy hypothesis: Open chemical systems and their biological functions.  Annual Review of Physical Chemistry, 58(1):113–142, 2007.  PMID: 17059360.
  * [RS16] Luc Rey-Bellet and Konstantinos Spiliopoulos.  Improving the convergence of reversible samplers.  Journal of Statistical Physics, 164(3):472–494, 2016.
  * [Sch76] J. Schnakenberg.  Network theory of microscopic and macroscopic behavior of master equation systems.  Rev. Mod. Phys., 48:571–585, Oct 1976.
  * [Sei12] Udo Seifert.  Stochastic thermodynamics, fluctuation theorems and molecular machines.  Reports on Progress in Physics, 75(12):126001, nov 2012.
  * [SSG10] Yi Sun, Jürgen Schmidhuber, and Faustino Gomez.  Improving the asymptotic performance of Markov chain Monte-Carlo by inserting vortices.  In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
  * [TBM22] Annalisa T Taylor, Thomas A Berrueta, and Todd D Murphey.  Emergent mechanism design via robot swarms.  Robotics: Science and Systems, July 2022.
  * [YBB+22] Jing Fan Yang, Thomas A. Berrueta, Allan M. Brooks, Albert Tianxiang Liu, Ge Zhang, David Gonzalez-Medrano, Sungyun Yang, Volodymyr B. Koman, Pavel Chvykov, Lexy N. LeMar, Marc Z. Miskin, Todd D. Murphey, and Michael S. Strano.  Emergent microrobotic oscillators via asymmetry-induced order.  Nature Communications, 13(1):5734, 2022.


#  Efficient 3D Instance Mapping and Localization with Neural Fields
https://gtangg12.github.io/iML

George Tang Krishna Murthy Jatavallabhula Antonio Torralba
Massachusetts Institute of Technology

###### Abstract

We tackle the problem of learning an implicit scene representation for 3D
instance segmentation from a sequence of posed RGB images. Towards this, we
introduce 3DIML, a novel framework that efficiently learns a _label field_
that may be rendered from novel viewpoints to produce view-consistent instance
segmentation masks. 3DIML significantly improves upon training and inference
runtimes of existing implicit scene representation based methods. Opposed to
prior art that optimizes a neural field in a self-supervised manner, requiring
complicated training procedures and loss function design, 3DIML leverages a
two-phase process. The first phase, InstanceMap, takes as input 2D
segmentation masks of the image sequence generated by a frontend instance
segmentation model, and associates corresponding masks across images to 3D
labels. These almost view-consistent pseudolabel masks are then used in the
second phase, InstanceLift, to supervise the training of a neural label field,
which interpolates regions missed by InstanceMap and resolves ambiguities.
Additionally, we introduce InstanceLoc, which enables near realtime
localization of instance masks given a trained label field and an off-the-
shelf image segmentation model by fusing outputs from both. We evaluate 3DIML
on sequences from the Replica and ScanNet datasets and demonstrate 3DIML’s
effectiveness under mild assumptions for the image sequences. We achieve a
large practical speedup over existing implicit scene representation methods
with comparable quality, showcasing its potential to facilitate faster and
more effective 3D scene understanding.

##  I Introduction

Intelligent agents require scene understanding at the object level to
effectively carry out context-specific actions such as navigation and
manipulation. While segmenting objects from images has seen remarkable
progress with scalable models trained on internet-scale datasets [1, 2],
extending such capabilites to the 3D setting remains challenging.

In this work, we tackle the problem of learning a 3D scene representation from
posed 2D images that factorizes the underlying scene into its set of
constituent objects. Existing approaches to tackle this problem have focused
on training class-agnostic 3D segmentation models [3, 4], requiring large
amounts of annotated 3D data, and operating directly over explicit 3D scene
representations (e.g., pointclouds). An alternate class of approaches [5, 6]
has instead proposed to directly lift segmentation masks from off-the-shelf
instance segmentation models into implicit 3D representations, such as neural
radiance fields (NeRF) [7], enabling them to render 3D-consistent instance
masks from novel viewpoints.

However, the neural field-based approaches have remained notoriously difficult
to optimize, with [5] and [6] taking several hours to optimize for low-to-mid
resolution images (e.g., $300\times 640$). In particular, Panoptic Lifting [5]
scales cubicly with the number of objects in the scene preventing it from
being applied to scenes with hundreds of objects, while Contrastively Lifting
[6] requires a complicated, multi-stage training procedure, hindering
practicality for use in robotics applications.

To this end, we propose 3DIML, an efficient technique to learn 3D-consistent
instance segmentation from posed RGB images. 3DIML comprises two phases:
InstanceMap and InstanceLift. Given view-inconsistent 2D instance masks
extracted from the RGB sequence using a frontend instance segmentation model
[2], InstanceMap produces a sequence of view-consistent instance masks. To do
so, we first associate masks across frames using keypoint matches between
similar pairs of images. We then use these potentially noisy associations to
supervise a neural label field, InstanceLift, which exploits 3D structure to
interpolate missing labels and resolve ambiguities. Unlike prior work, which
requires multistage training and additional loss function engineering, we use
a single rendering loss for instance label supervision, enabling the training
process to converge significantly faster. The total runtime of 3DIML,
including InstanceMap, takes 10-20 minutes, as opposed to 3-6 hours for prior
art.

In addition, we devise InstaLoc, a fast localization pipeline that takes in a
novel view and localizes all instances segmented in that image (using a fast
instance segmentation model [8]) by sparsely querying the label field and
fusing the label predictions with extracted image regions. Finally, 3DIML is
extremely modular, and we can easily swap components of our method for more
performant ones as they become available.

To summarize, our contributions are:

  * •

An efficient neural field learning approach that factorizes a 3D scene into
its constituent objects

  * •

A fast instance localization algorithm that fuses sparse queries to the
trained label field with performant image instance segmentation models to
generate 3D-consistent instance segmentation masks

  * •

An overall practical runtime improvement of 14-24$\times$ over prior art
benchmarked on a single GPU (NVIDIA RTX 3090)

##  II Background

Figure 2: Overview of 3DIML. A sequence of color images is segmented into
object instances by an image segmentation backbone. The resulting masks
produced are fed into InstanceMap, which produces instance masks consistent
over all frames. These pseudo instance masks and their respective camera poses
are used to supervise an instance label NeRF, which further improves
consistency and resolves ambiguity present in the InstanceMap outputs. The
_feature extraction_ and _global data association_ blocks together form
InstanceMap.

2D segmentation: The prevalence of vision transformer architecture and the
increasing scale of image datasets have resulted in a series of state-of-the-
art image segmentation models. Panoptic and Contrastive Lifting both lift
panoptic segmentation masks produced by Mask2Former [1] to 3D by learning a
neural field. Towards open-set segmentation, segment anything (SAM) [2]
achieves unprecedented performance by training on a billion masks over 11
million images. HQ-SAM [9] improves upon SAM for fine-grained masks. FastSAM
[8] distills SAM into a CNN architecture and achieves similar performance
while being orders of magnitude faster. In this work, we use GroundedSAM [10,
11], which refines SAM to produce object-level, as opposed to part-level
segmentation masks.

Neural fields for 3D instance segmentation: NeRFs are implicit scene
representations that can accurately encode complex geometry, semantics, and
other modalities, as well as resolve viewpoint inconsistent supervision [12].
Panoptic lifting [5] constructs semantics and instances branches on an
efficient variant of NeRF, TensoRF [13], utilizing a Hungarian matching loss
function to assign learned instance masks to surrogate object IDs given
reference view-inconsistent masks. This scales poorly with increasing number
of objects (owing to the cubic complexity of Hungarian matching). Contrastive
lifting [6] addresses this by instead employing contrastive learning on scene
features, with positive and negative relations determined by whether or not
they project onto the same mask. In addition, contrastive lifting requires a
slow-fast clustering-based loss for stable training, leading to faster
performance than panoptic lifting but requires multiple stages of training,
leading to slow convergence. Concurrently to us, Instance-NeRF [14] directly
learn a label field, but they based their mask association on utilizing NeRF-
RPN [15] to detect objects in a NeRF. Our approach, on the contrary, allows
scaling to very high image resolutions while requiring only a small number
(40-60) of neural field queries to render segmentation masks.

Structure from Motion: During mask association in InstanceMap, we take
inspiration from scalable 3D reconstruction pipelines such as hLoc [16],
including the use of visual descriptors for matching image viewpoints first,
then applying keypoint matching as a preliminary for mask association. We
utilize LoFTR [17] for keypoint extraction and matching.

##  III Method

Given a sequence of $N$ posed RGB images, $(I_{i},T_{i})$ where $I$ denotes
the image and $T$ pose, we first extract view-inconsistent instance masks
$M_{i}$ using a generic instance segmentation model such as Mask2Former or
SAM.

###  III-A Mask Association

We first generate pseudolabel masks with InstanceMap. Formally, define
$\phi(M,r)$ to map a mask $M$ and region $r$ to a consistent label for the
same 3D object across different masks and regions. We extend the popular hLoc
[16] framework for scalable 3D reconstruction to mask association as follows:

Correspondence Generation: For each image $I_{i}$ in the input sequence, we
compute NetVLAD [16] feature descriptors. We then compute the cosine
similarity among all pairs of images using these descriptors, defining a
visual match as a similarity above a threshold of $\tau_{\text{global}}$. For
each visual pair, we extract dense correspondences (i.e. set of keypoints in
both images and a correspondence mapping from one set to the other) using
LoFTR [17] Since LoFTR computes keypoints independently per image pair, we
aggregated keypoints from all pairs. Denote image $I_{i}$’s keypoints $k_{i}$
and matches between $I_{i},I_{j}$ as $m_{ij}$. These correspondences are used
in the next step to associate masks.

Since NetVLAD and LoFTR don’t have 3D information, 3DIML only performs well if
each image in the scan sequence contains enough context for these models. We
observe empirically a good rule of thumb is to have at least one other
recognizable landmark for frames containing near-identical objects.

Mask Association Graph: Insofar, our approach produces instance masks and
dense pixel correspondences among images that share a visual overlap. However,
segmentation models such as SAM [2] suffer multiple issues: (a) segmentations
of the same object need not be consistent across images, owing to viewpoint
and appearance variations; and (b) owing to over-segmentation of objects,
there isn’t usually a one-one correspondence among masks.

To associate instance masks across the entire scene, we construct an _mask
association graph_ , where the nodes are all instances detected across all
images in the sequence. We then proceed to populate edges in this graph,
corresponding to each pair of object instances that may be deemed a potential
match. For each visual pair $(i,j)$, for all regions in $M_{i}$, we find a
best-match region in $M_{j}$ if one exists. Let $r_{u},r_{v}$ denote regions
in $M_{i},M_{j}$, $k_{i}(r_{u})$, $k_{j}(r_{v})$ to be the keypoints of
$I_{i},I_{j}$ contained in regions $r_{u},r_{v}$, respectively, and
$m_{ij}(r_{u},r_{v})$ be the matches between the regions. An edge with weight
matching score is added for $r_{u},r_{v}$ if the matching score exceeds some
threshold

$\min\left(\frac{m_{ij}(r_{u},r_{v})}{|k_{i}(r_{u})|},\frac{m_{ij}(r_{u},r_{v})}{|k_{j}(r_{v})|)}\right)>\tau_{\text{local}}$

Community Detection: Given this association graph, to remove noisy edges, we
run community detection, specifically igraph’s implementation of the Leiden
Algorithm with resolution parameter 0, over this graph and merge all masks in
the same community (determined by threshold size $\tau_{\text{community}}$;
the remaining masks are discarded). We also filter out all labels that do not
feature in a minimum number of frames, as there are insufficient observations
to accurately associate them across views. To account for potentially
overlapping instances, a common occurrence due to perspective image formation,
we compute the average mask area across all frames an instance exists in,
which serves as a rasterization order for InstanceLift (instance masks with
the largest area averaged over all frames are rasterized first). Example
outputs are shown in Fig. LABEL:fig:splash.

###  III-B Mask Refinement

$\phi(M,r)$ is inherently noisy due to varying segmentation hierarchies for
different instance masks due to differing viewpoints as well as design
specifics. To address this, in InstanceLift we feed the pseudolabel masks to a
label NeRF, which resolves some ambiguities. Still, NeRF cannot handle extreme
cases of label ambiguity, to which we devise a fast post-processing method
that determines and merges colliding labels based on random renders from the
label NeRF. The few remaining, if any, ambiguities can be corrected via sparse
human annotation.

Neural Label Field Our label field represents the scene as a function
$\Phi(x,d)$ that maps each point $\mathbf{x}\in\mathbb{R}^{3}$ and view-
direction directions $\mathbf{d}\in\mathbb{S}^{2}$ to a corresponding density
$\sigma(\mathbf{x})$ and other modalities $f(\textbf{x},\textbf{d})$. These
neural fields are queried via volumetric rendering by sampling per pixel rays
across images, sampling points on rays, and estimating the volume rendering
integral along those sampled points (see [7] for more details). We base our
NeRF on the off-the-shelf Nerfacto architecture [18]. We add a multiresolution
hashgrid [19] for instance labels in addition to one for color and geometry as
well as an instance prediction MLP to render instance segmentation logits,
which we supervise with cross entropy using the pseudolabel masks from
InstanceMap. As in [5], [14], we block gradient flow from the label grid to
the geometry grid. We train our model to learn volume density, color, and
instance labels simultaneously.

Label Merging: Once the label NeRF is trained, we build a redundancy graph
where the nodes, $v$ denote labels and the number of edges, $|e|$ between
nodes correlate with how likely the labels refer to the same object.
Specifically, we randomly render $K$ views and compare the rendered instance
mask with some mask generated on the fly by FastSAM. For each region of
FastSAM, we add pairwise edges between all labels that occupy greater than
$\tau_{area}$ fraction of the region. Post graph construction, we merge labels
$a,b$ if

$\frac{2|e_{ab}|}{\deg(v_{a})+\deg(v_{b})}>\tau_{merge}$

Since we only need coarse information i.e. instance mask noise, we render
images downsampled by a factor of 2.

###  III-C Fast Instance Localization and Rendering

Figure 3: InstanceLoc enables 3D-consistent instance segmentation for novel
views of the scene unobserved by the InstanceMap pipeline. We leverage off-
the-shelf instance segmentation models to first produce 3D-inconsistent
instance labels for a new input image. We then query the label field over a
sparse set of points on the image and use this to localize each 2D instance
mask i.e., assign a 3D-consistent label to each mask.

Training a label field enables us to predict 3D-consistent instance labels for
novel viewpoints without rerunning 3DIML. However, rendering every pixel is
slow, and rendering from a novel viewpoint is often noisy. We propose a _fast
localization_ approach that instead precomputes instance masks for the input
image using an instance segmentation model (here FastSAM [8]). Given this
instance mask, for each instance region, we sample the corresponding pixelwise
3D object labels from the label NeRF and take the majority label. Another
benefit is that the input instance masks can be constructed using prompts and
edited before localization.

##  IV Experiments

We benchmark our method against Panoptic and Contrastive Lifting using the
same Mask2Former frontend. For fairness, we render semantics as in [5], [6]
using the same multiresolution hashgrid for semantics and instances. For other
experiments, we utilize GroundedSAM as our frontend and FastSAM for runtime
performance critical tasks such as label merging and InstanceLoc.

###  IV-A Datasets

We evaluate our methods on a challenging subset of scans from Replica and
ScanNet, which provide ground truth annotations. Since our methods are based
on structure from motion techniques, we utilize the Replica-vMap [20]
sequences, which is more indicative of real-world collected image sequences.
For Replica and ScanNet, we avoid scans with various incompatibilities with
our method (multi-room, low visibility, Nerfacto doesn’t converge) as well as
those containing many close-up views of identical objects that easily confuse
NetVLAD and LoFTR.

###  IV-B Metrics

For lifting panoptic segmentation, we utilize Scene Level Panoptic Quality
[5], defined as the Panoptic Quality for the concatenated sequence of images.
For Grounded SAM, especially with instance masks for smaller objects, there is
a divergence in alignment with ground truth annotations. As such, we report
mIoU for predicted, reference masks that have IoU $>0.5$ over all frames (TP
in Scene Level Panoptic Quality) as well as the number of such matched masks
and the total number of reference masks.

###  IV-C Implementation Details

For comparison with Panoptic and Contrastive Lifting, we follow their
evaluation framework and map the Mask2Former outputs and ground truth semantic
labels to 21 reduced ScanNet classes, considering only the ”thing” subset of
those classes. We train Panoptic and Contrastive Lifting using the code
provided by [6]. We use the default parameterizations as their Replica
experiment, which scales the number of iterations (128000) with the number of
images. We build 3DIML on top of the popular framework Nerfstudio [18] with
tinycudann enabled [19]. We train until convergence for 5000 iterations for
Replica-vMap (both Mask2Former and GroundedSAM) and 10000 iterations for
ScanNet. For our panoptic experiments, we use
$\left(\tau_{\text{global}},\tau_{\text{local}},\tau_{\text{community}},\tau_{\text{area}},\tau_{\text{merge}}\right)=$
(0.25, 0.8, 2, 0.15,0.75). For GroundedSAM, we use (0.25, 0.75, 3, 0.3, 0.6)
for Replica-vMap and (0.4, 0.75, 3, 0.25, 0.75) for ScanNet.

###  IV-D Results

Comparison with Panoptic and Contrastive Lifting: Table II shows the Scene
Level Panoptic Quality for 3DIML and other methods on Replica-vMap sequences
subsampled by 10 (200 frames). We observe 3DIML approaches Panoptic Lifting in
performance while achieving a much larger practical runtime (considering
implementation) than Panoptic and Contrastive Lifting. Intuitively, this is
achieved by efficiently relying on implicit scene representation methods only
at critical junctions i.e. post InstanceMap, greatly reducing the number of
training iterations of the neural field (25x less). Figure 4 compares the
instances identified by Panoptic Lifting to 3DIML.

We benchmark all runtimes using a single RTX 3090 post-mask generation.
Specifically, comparing their implementation to ours, Panoptic Lifting
requires 5.7 hours of training over all scans, with a min and max of 3.6 and
6.6 hours, respectively, since its runtime depends on the number of objects.
Contrastive Lifting takes around 3.5 hours on average while 3DIML runs under
20 minutes (14.5 minutes on average) for all scans. Note several components of
3DIML can be easily parallelized, such as dense descriptors extraction using
LoFTR and label merging. The runtime of our method is dependent on the number
of correspondences produced by LofTR, which doesn’t change for different
frontend segmentation models, and we observe similar runtimes for other
experiments.

Figure 4: Comparison between Panoptic Lifting and 3DIML for room0 from
Replica-vMap

Scene office0 office2 office3 office4 room0 room1 Average Panoptic Lifting [5]
39.1 52.8 60.0 65.6 63.7 94.8 62.6 Contrastive Lift [6] 11.4 19.4 17.2 20.4
37.2 94.8 33.4 InstanceMap (ours) 34.9 26.1 41.3 27.3 63.1 52.5 40.8
InstanceLift (ours) 39.7 28.1 55.2 46.4 68.8 87.4 54.2

TABLE I: Quantitative comparison between pannoptic lifting [5], contrastive
lift [6], and our framework components, InstanceMap and InstanceLift. We
measure the scene level panoptic quality metric (higher value indicates better
performance). Our approach offers competitive performance while being far more
efficient to train. Best performing numbers for each scene are in bold, while
the second-best numbers are shaded yellow.

Method Time Panoptic lifting [5] 5.7 hours Contrastive lift [6] 3.6 hours
InstanceMap (LoFTR) 6.2 minutes InstanceMap 2.1 minutes InstanceLift (train)
5.6 minutes InstanceLift (refine) 33.2 seconds 3DIML (total) 14.5 minutes

TABLE II: Runtime in minutes benchmarked on a single RTX 3090 of Panoptic
Lifting, Contrastive Lifting, and 3DIML Figure 5:  InstanceLift is able to
fill in labels missed by InstanceMap as well as correct ambiguities. Here we
show comparisons between them for office0 and room0 from Replica-vMap.

Grounded SAM Table III shows our results for lifting GroundedSAM masks for
Replica-vMap. From Figure 5 we see that InstanceLift is effective at
interpolating labels missed by InstanceMap and resolving ambiguities produced
by GroundedSAM 111GroundedSAM produces lower quality frontend masks than SAM
due to prompting using bounding boxes instead of a point grid.. Figure 7 shows
that InstanceMap and 3DIML are robust to large viewpoint changes and as well
as duplicate objects, assuming nice scans, that is enough context for NetVLAD
and LoFTR to somewhat distinguish between them. Table IV and Fig. 6 illustrate
our performance on ScanNet [21].

Figure 6:  Some results for scans 0144_01, 0050_02, and 0300_01 from ScanNet
[21] (one scene per row, top to bottom), showcasing how 3DIML accurately and
consistently delineates instances in 3D.  Figure 7:  Qualitative results on
office3 and room1 from the Replica-vMap split [20]. Both InstanceMap and
InstanceLift are able to maintain quality and consistency over the image
sequence despite duplicate objects due to sufficient image context overlap
across the sequence.

Scene office0 office2 office3 office4 room0 room1 Average InstanceMap 0.740 /
14 0.753 / 27 0.769 / 30 0.758 / 22 0.825 / 34 0.729 / 25 0.762 InstanceLift
0.785 / 18 0.780 / 30 0.799 / 36 0.794 / 26 0.851 / 38 0.769 / 25 0.796

TABLE III:  Quantitative (mIoU, TP) results for GroundedSAM frontend on
Replica-vMap. The average number of reference instances for all Replica scenes
we evaluated on is $67$.

Scene 0050_02 0144_01 0221_01 0300_01 0389_00 0494_00 0693_00 Average
InstanceMap 0.675 / 12 0.646 / 14 0.667 / 12 0.726 / 13 0.704 / 13 0.716 / 6
0.700 / 14 0.691 InstanceLift 0.657 / 14 0.664 / 14 0.621 / 10 0.754 / 14
0.745 / 12 0.712 / 8 0.782 / 16 0.705

TABLE IV:  Quantitative (mIoU, TP) results for GroundedSAM frontend on
ScanNet. The average number of reference instances for all ScanNet scenes we
evaluated on is $32$.

Novel View Rendering and InstanceLoc Table V shows the performance if 3DIML on
the second track provided in Replica-vMap. We observe that InstanceLift is
effective at rendering new views, and therefore InstanceLoc performs well. For
Replica-vMap and FastSAM, InstanceLoc takes on average 0.16s per localized
image (6.2 frames per second). In addition, InstanceLoc can be applied as a
post-processing step to the renders of the input sequence as a denoising
operation.

Scene office0 office2 office3 office4 room0 room1 Average InstanceLift 0.822 /
16 0.787 / 29 0.762 / 35 0.769 / 30 0.849 / 39 0.768 / 28 0.793 InstanceLoc
0.845 / 15 0.842 / 30 0.799 / 37 0.812 / 30 0.877 / 41 0.800 / 28 0.829

TABLE V:  Quantitative (mIoU, TP) results for InstanceLift and InstanceLoc on
novel views over the Replica-vMap split [20].  Figure 8:  InstanceLoc is able
to correct for noise rendered by InstanceLift.

###  IV-E Limitations and Future Work

In extreme viewpoint changes, our method sometimes produced discontinuous 3D
instance labels. For example, on the worst performing scene, office2, we see
that since the scan images only the front of a chair facing the back of the
room and the back of a chair facing the front of the room for many frames,
InstanceMap is not able to conclude these labels refer to the same object, and
InstanceLift was unable to fix it, as NeRF’s correction performance rapidly
degrades with increasing label inconsistency [12]. However, there are very few
of these left per scene post 3DIML, and they can be easily fixed via sparse
human annotation.

Figure 9:  Our methods do not perform well in cases where the scan sequence
contains only images of the different sides of an object (chair) or surface
(floor) from differing directions without any smooth transitions in between,
which occurs for office2 from Replica (vMap split [20]).

##  V Conclusion

In this paper, we present 3DIML, which addresses the problem of 3D instance
segmentation in a class-agnostic and computationally efficient manner. By
employing a novel approach that utilizes InstanceMap and InstanceLift for
generating and refining view-consistent pseudo instance masks from a sequence
of posed RGB images, we circumvent the complexities associated with previous
methods that only optimize a neural field. Furthermore, the introduction of
InstanceLoc allows rapid localization of instances in unseen views by
combining fast segmentation models and a refined neural label field. Our
evaluations across Replica and ScanNet and different frontend segmentation
models showcase 3DIML’s speed and effectiveness. It offers a promising avenue
for real-world applications requiring efficient and accurate scene analysis.

## References

  * [1] B. Cheng, I. Misra, A. G. Schwing, A. Kirillov, and R. Girdhar, “Masked-attention mask transformer for universal image segmentation,” _CoRR_ , vol. abs/2112.01527, 2021. [Online]. Available: https://arxiv.org/abs/2112.01527
  * [2] A. Kirillov, E. Mintun, N. Ravi, H. Mao, C. Rolland, L. Gustafson, T. Xiao, S. Whitehead, A. C. Berg, W.-Y. Lo _et al._ , “Segment anything,” _arXiv preprint arXiv:2304.02643_ , 2023.
  * [3] J. Schult, F. Engelmann, A. Hermans, O. Litany, S. Tang, and B. Leibe, “Mask3d: Mask transformer for 3d semantic instance segmentation,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 8216–8223.
  * [4] A. Takmaz, E. Fedele, R. W. Sumner, M. Pollefeys, F. Tombari, and F. Engelmann, “Openmask3d: Open-vocabulary 3d instance segmentation,” _arXiv preprint arXiv:2306.13631_ , 2023.
  * [5] Y. Siddiqui, L. Porzi, S. R. Bulò, N. Müller, M. Nießner, A. Dai, and P. Kontschieder, “Panoptic lifting for 3d scene understanding with neural fields,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 9043–9052.
  * [6] Y. Bhalgat, I. Laina, J. F. Henriques, A. Zisserman, and A. Vedaldi, “Contrastive lift: 3d object instance segmentation by slow-fast contrastive fusion,” 2023.
  * [7] B. Mildenhall, P. P. Srinivasan, M. Tancik, J. T. Barron, R. Ramamoorthi, and R. Ng, “Nerf: Representing scenes as neural radiance fields for view synthesis,” _Communications of the ACM_ , vol. 65, no. 1, pp. 99–106, 2021\.
  * [8] X. Zhao, W. Ding, Y. An, Y. Du, T. Yu, M. Li, M. Tang, and J. Wang, “Fast segment anything,” _arXiv preprint arXiv:2306.12156_ , 2023.
  * [9] L. Ke, M. Ye, M. Danelljan, Y. Liu, Y.-W. Tai, C.-K. Tang, and F. Yu, “Segment anything in high quality,” _arXiv preprint arXiv:2306.01567_ , 2023.
  * [10] Y. Zhang, X. Huang, J. Ma, Z. Li, Z. Luo, Y. Xie, Y. Qin, T. Luo, Y. Li, S. Liu, Y. Guo, and L. Zhang, “Recognize anything: A strong image tagging model,” 2023.
  * [11] S. Liu, Z. Zeng, T. Ren, F. Li, H. Zhang, J. Yang, C. Li, J. Yang, H. Su, J. Zhu, and L. Zhang, “Grounding dino: Marrying dino with grounded pre-training for open-set object detection,” 2023.
  * [12] S. Zhi, T. Laidlow, S. Leutenegger, and A. J. Davison, “In-place scene labelling and understanding with implicit scene representation,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 15 838–15 847.
  * [13] A. Chen, Z. Xu, A. Geiger, J. Yu, and H. Su, “Tensorf: Tensorial radiance fields,” in _European Conference on Computer Vision (ECCV)_ , 2022.
  * [14] B. Hu, J. Huang, Y. Liu, Y.-W. Tai, and C.-K. Tang, “Instance neural radiance field,” _arXiv preprint arXiv:2304.04395_ , 2023.
  * [15] ——, “Nerf-rpn: A general framework for object detection in nerfs,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 23 528–23 538.
  * [16] P.-E. Sarlin, C. Cadena, R. Siegwart, and M. Dymczyk, “From coarse to fine: Robust hierarchical localization at large scale,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 12 716–12 725.
  * [17] J. Sun, Z. Shen, Y. Wang, H. Bao, and X. Zhou, “Loftr: Detector-free local feature matching with transformers,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2021, pp. 8922–8931.
  * [18] M. Tancik, E. Weber, E. Ng, R. Li, B. Yi, T. Wang, A. Kristoffersen, J. Austin, K. Salahi, A. Ahuja _et al._ , “Nerfstudio: A modular framework for neural radiance field development,” in _ACM SIGGRAPH 2023 Conference Proceedings_ , 2023, pp. 1–12.
  * [19] T. Müller, A. Evans, C. Schied, and A. Keller, “Instant neural graphics primitives with a multiresolution hash encoding,” _ACM Transactions on Graphics_ , vol. 41, no. 4, p. 1–15, Jul. 2022. [Online]. Available: http://dx.doi.org/10.1145/3528223.3530127
  * [20] X. Kong, S. Liu, M. Taher, and A. J. Davison, “vmap: Vectorised object mapping for neural field slam,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 952–961.
  * [21] A. Dai, A. X. Chang, M. Savva, M. Halber, T. Funkhouser, and M. Nießner, “Scannet: Richly-annotated 3d reconstructions of indoor scenes,” in _Proc. Computer Vision and Pattern Recognition (CVPR), IEEE_ , 2017.