UWThPh-2004-9

Fluctuations of quantum lattice systems under Boltzmann evolution

Heide Narnhofer ∗

Faculty for Physics

Vienna University

For quantum lattice systems a Boltzmann type time evolution arises according
to results of Hugenholtz in the limit of N-scaled time evolution together with
an interaction scaled as $N^{-1/2}$. According to Illner -Neunzert this
passage to an irreversible dynamic can only happen when the initial state
satisfies stronger assumptions than the evolved state. We show that the
initial state allows to control space clustering as it is the minimal
requirement for the construction of a fluctuation algebra in the sense of
Verbeure et al., whereas in the evolved state fluctuations only are defined in
an appropriate scaling local with respect to the time evolution but not on a
mesoscopic level.

Keywords: Boltzmann equation, Van Hove limit, fluctuation algebra, long range
correlations

∗ E–mail address<EMAIL_ADDRESS>
##  1 Introduction

The fact that in thermodynamics time evolution is irreversible is undoubted.
Also the fact that we should understand thermodynamics as resulting from
n-particle physics and its thermodynamic limit is taken for granted. An
important and extremely successful step is provided by the Boltzmann equation.
It combines particle physics and its scattering mechanism expressed by the
scattering cross section and statistics expressed by the density function.
Initially it was given as ansatz based on plausibility [8], but it is possible
to deduce it rigorously as a limit where the number of particles goes to
infinity though in a way that the particle density is small enough so that the
scattering process remains an individual process just between two particles
[2]. The mathematical control is still limited to essentially some finite
number of collision processes and this can be achieved by various assumptions
on the initial state. Still there are attempts to vary and reduce these
assumptions [3]. But in applications the Boltzmann equation is so successful
to describe the actually observed behaviour that there is good reason to
believe that the limitations in the proof are given by mathematical
difficulties and not by conceptual errors. Nevertheless from the very
beginning there were controversial considerations how the reversible time
evolution of n-particle physics can transform into the irreversible time
evolution given by the Boltzmann equation. This irreversibility is manifested
in the increase of entropy. However the monotonic behaviour of some function
with respect to time is not jet an appropriate characterisation of
irreversiblity, already for one particle the dilation
$x(t)p(t)=x(0)p(0)+p^{2}(0)t/2$ increases in time. In [4] this question of
irreversibility was investigated. On one hand the authors clarified in which
sense irreversibility has to be understood in order to be relevant for
thermodynamics. Next they inspected the proof for the derivation of the
Boltzmann equation and observed, that in the proof the demands on the
convergence of the density function for the starting state is stronger than
for the evolved states. Finally they showed that this is not only an
inconvenience due to the fact that we did not find the appropriate
mathematical arguments but it is essential: only if initial state and evolved
state are defined in different topologies the time evolution can undergo such
an essential qualitative change from reversibility to irreversibility.

Boltzmann equation is an evolution equation in the framework of classical
physics. [5] considered a corresponding approach in the frame work of quantum
mechanics. He studied Fermions on an infinite lattice where we have the
advantage that free evolution and also time evolution with interaction is well
defined as automorphisms on the corresponding $C^{*}$ algebra. In contrast to
the classical assumptions we do not consider a limit corresponding to an
increasing particle number. The thermodynamic limit is already given by
starting with the $C^{*}$ algebra. Therefore low density is no suitable
concept. But the idea that the scattering process is an individual process
between pairs can be adopted. Also in the classical situation we can think of
two time scales, one the time in which the scattering process is finished,
which is given by the size of the cross section which in the approach tends to
a point, and the time in which the particles change their location. In a
similar way [5] considered two time scales: the time scale necessary for the
scattering process being expressed only by the twopoint function, which
according to the velocity asks for a weak interaction, and a time scale so
that in spite of the weakness of the interaction the effects can summarize.
With the appropriate scaling the twopoint function, which in this setting is
just a function of momentum and not of space, evolves by a differential
equation very similar to the Boltzmann equation. Especially this evolution has
the same advantage that the entropy density increases and that the fixed point
of the evolution are equilibrium states of the free unperturbed evolution. The
essential steps will be given in section (2).

We are interested how in this approach the result of [4] can be observed. We
will notice that the difference in topology is given in the way in which the
twopoint function has to be interpreted. But in addition we can use an
additional concept to see in which sense information gets lost: a state cannot
only be interpreted as a state over the quasilocal $C^{*}$algebra. It can be
enlarged to define a state on mesoscopic observables, the fluctuation algebra
introduced in [6]. Its definition will be given in section (3). This is not
always possible but asks for strong spacial clustering properties that however
can be provided in appropriate states as for example equilibrium states [7].
This fluctuation algebra exists for the initial state satisfying the demands
in [5]. In section (4) we will concentrate on this fluctuation algebra, where
we have the additional option to define it in various ways corresponding to
the scaling in the evaluation of the Boltzmann equation. We will observe how
the control on long range spacial correlations though unobservable on the
quasilocal level but necessary for the construction of the fluctuation algebra
gets lost in the cause of time.

##  2  The approach of Hugenholtz

We repeat the definitions and relevant results of [5] as they are the basis
and ask only for minor generalisations for the fluctuation algebra.

We consider the Fermi-algebra on a lattice, built by creation and annihilation
operators $a(x),a(y)^{*}$ satisfying the anticommutation relations

$[a(x),a(y)]=0,\quad[a(x),a(y)^{*}]=\delta_{xy}$ (1)

and the corresponding operators $a(f)=\sum_{x}f(x)a(x)$ satisfying
$||a(f)||=\sum_{x}|f(x)|^{2}.$ In addition we will calculate with their
Fourier transform $a_{p}$ where we have to keep in mind that these are not
operators but unbounded forms well defined in appropriate representations. We
start from the very beginning with a quasifree state that is translation
invariant given by the twopoint function

$\omega(a(f)^{*}a(g))=\sum_{x,y}w(x-y)\bar{f(x)}g(y)).$ (2)

In [5] Hugenholtz started with more generality but showed that with
appropriate assumptions in the limit the truncated functions vanish. In the
following we will start from the very beginning with such states and work in
momentum space. We consider a quasifree evolution

$\tau_{0}(t)a(f)=a(e^{iht}f)=\int_{-\pi}^{\pi}dpe^{i\epsilon(p)}f(p)a_{p}$ (3)

and an interaction given in Fourier space by

$V=\int dkdldmdn[v(k-n)-v(k-m)]\delta(k+l-m-n)a_{k}^{*}a_{l}^{*}a_{m}a_{n}.$
(4)

For this interaction it is well known that its expression in x-space allows to
show by perturbation theory that also in combination with the quasifree
evolution it defines an automorphism group on the $C^{*}$ algebra. Summations
and integrations can be understood in various dimensions without effecting the
final result.

The Boltzmann evolution is obtained by considering the evolution $\tau(t)$
implemented by

$H_{\lambda,N}=\epsilon(p)a_{p}^{*}a_{p}+N^{-1/2}\lambda V$ (5)

and considering

$\omega_{t}(A)=\lim_{N\rightarrow\infty}\omega(\tau(tN)A)$ (6)

The interaction is treated on a perturbative level expanding in $\lambda$ with
multicommutators

$\tau^{0}_{-Nt}\tau^{\lambda}_{tN}A=\sum_{n}(i\lambda)^{n}\int_{0}^{tN}dt_{1}\int_{0}^{t_{1}}..[\tau^{0}_{t_{1}}(N^{-1/2}V),[\tau^{0}_{t_{2}}(N^{-1/2}V),...A]..$
(7)

To first order for our starting quasifree state we get a sum over expectation
values of operators such that the expectation value splits into products of
the expectation value of pairs of creation and annilhilation operators. Now
the invariance under space translations together with the symmetry relations
resulting from the commutators implies that to first order of $\lambda$
together with the scaling in $N$ this term vanishes, and the same remains true
for all contributions of odd order in $\lambda.$ For even contributions again
we concentrate on the twopoint contributions that contain a factor
$e^{i\epsilon(m)t_{r}-i\epsilon(l)t_{s}}$ or only $e^{i\epsilon(m)t_{r}}$.
Integration over $t_{r}$ let these terms vanish in the limit
$N\rightarrow\infty$ in combination with the scaling of the interaction.
Exceptions appear if for the integration with respect to $t_{r}$ and $t_{s}$
the time dependence in the exponent is opposite to one another so that we can
split into $dt_{r}-dt_{s}$ which gives a finite integral due to asymptotic
abelianess and the assumption on the clustering of the state and the integral
over $dt_{r}+dt_{s}$ which is of order $N$ and multiplied with the scaling of
the interaction also gives a finite term and therefore contributes to the
change of the state. This coincidence happens when the double commutant of the
interaction acts on the same annihilation respectively creation operator. We
refer to (4.9) in [5]. The various terms can be represented by diagrams that
show that the number of contributing terms is sufficiently small to guarantee
convergence of the perturbation theory. In addition only those terms
contribute where the contributions of creation and annihilation operators
defining the operator $A$ in (7) enter in the same combination as in the
starting state, though with different weight corresponding to the interaction.
Therefore the limit state is again quasifree but with a different twopoint
function. All details are given in [5].

With

$\omega_{t}(a(f)^{*}a(g)=\int dpw(p,t)\bar{f(p)}g(p)$ (8)

and concentrating on $t\rightarrow 0$ [5] obtained the differential equation
and extended it to $t>0$

$\frac{d}{dt}w(p,t)=\pi\int dkdldm|\langle
kl|V|mp\rangle|^{2}\delta(k+l-m-p)\delta(\epsilon_{k}+\epsilon_{l}-\epsilon_{m}-\epsilon_{p})$
(9) $(w(k,t)w(l,t)(1-w(m,t))(1-w(p,t))-w(p,t)w(m,t)(1-w(k,t))(1-w(l,t))).$

Notice that this extension from $t=0$ to arbitrary $t$ has to be justified
because according to the observation of [4] the state at a later time will not
satisfy the same assumption as those that are needed for $t=0.$

##  3 The fluctuation algebra

In [6] the fluctuation algebra was introduced as an additional algebra that
can be associated to the quasilocal algebra in states that are space
translation invariant and satisfy additional appropriate properties. We
consider with space translation $\alpha_{x}A=A_{x}$

$\lim_{K\rightarrow\infty}\omega(e^{iK^{-1/2}\sum_{x=1}^{K}\alpha_{x}A-iK^{1/2}\omega(A)})=\bar{\omega}(W(A))$
(10)

where $W(A)$ can be interpreted as a unitary operator depending on the local
operator $A$ with expectation value in the state $\bar{\omega}$. Restriction
to local operators is useful to insure that the limit can exist but can be
extended to quasilocal operators. In the same spirit we can extend the
construction to $\bar{\omega}(W(A)W(B))$ and observe that the operators
satisfy

$W(A)W(B)=e^{\omega([A,B])}W(B)W(A)$ (11)

so that the unitary operators $W(A)$ form a bosonic Weyl-algebra. The state
$\bar{\omega}$ can now be interpreted as a state on both the quasilocal
algebra and the corresponding Weyl-algebra, which is itself state dependent.
With

$\bar{\omega}(W(A)BW(-A))=\omega(B)$ (12)

whereas

$\bar{\omega}(W(A)W(B)W(-A))=e^{\omega([A,B])}\bar{\omega}(W(B)),$ (13)

obviously the same state on the quasilocal algebra can give rise to different
states on the fluctuation algebra, therefore some specification is needed, and
this specification will give the difference between the initial state for the
Boltzmann evolution and the evolved state.

The additional properties guaranteing the existence of the limit in (10)
together with the possibility to interpret is as the state over a fluctuation
algebra ask for good control on the spacial decay of the state on the
quasilocal algebra. That they can be satisfied can easily be seen on the
example of a product state $\omega(A_{x}B_{y})=\omega(A_{x})\omega(B_{x})$
where with $\omega(A_{x})=0$

$\bar{\omega}(W(A))=\lim_{K\rightarrow\infty}(1-\omega(A_{x}^{2})/K)^{K}=e^{-\omega(A_{x}^{2})}.$
(14)

In more generality it was proven in [7] that the limit (10) can be controlled
for KMS-states constructed from appropriate Hamiltonians. We are mainly
interested whether there are additional conditions for quasifree states for
the control of (10) and they can be seen best in momentum space: with

$W(a^{*}(f)a(f))=\lim_{K\rightarrow\infty}e^{i\sum_{x}e^{ix(p-q)}K^{-1/2}a^{*}_{p}a_{q}\bar{f(p)}f(q)dpdq}$
(15)

we observe that $w(p)$ has to be interpreted as a distribution and not just as
an $L_{1}$ function in the same way as it had to guarantee that contributions
of different momenta vanish in the intergration over time in (4.9) of [5] and
not only due to the smearing effect of the state.

##  4 The limit for the fluctuations

Evaluating the fluctuation algebra and its expectation value corresponding to
the state on the quasilocal algebra we concentrate on

$\frac{d}{d\alpha}\bar{\omega}(W(\alpha
A)|_{\alpha=0}=\lim_{K\rightarrow\infty}\omega(\sum_{0}^{K}K^{-1/2}\sigma_{x}A)-K^{1/2}\omega(A)$
(16)

and

$\frac{d^{2}}{d\alpha^{2}}\bar{\omega}(W(\alpha
A)|_{\alpha=0}=\lim_{K\rightarrow\infty}\omega(\sum_{0}^{K}K^{-1}\sigma_{x}A)\sum_{0}^{K}\sigma_{y}A)-\omega(A)^{2}$
(17)

and their evolution under the time evolution leading to the Boltzmann
evolution, i.e.

$\lim_{N\rightarrow\infty}\lim_{K\rightarrow\infty}\omega(\tau_{-Nt}^{0}\tau_{Nt}^{\lambda}K^{-1/2}\sum_{0}^{K}\sigma_{x}A)-K^{1/2}\omega_{t}(A)$
(18)

with

$\lim_{N\rightarrow\infty}\omega(\tau_{-Nt}^{0}\tau_{Nt}^{\lambda}A)=\omega_{t}(A)$
(19)

respectively

$\lim_{K\rightarrow\infty}\lim_{N\rightarrow\infty}\omega(\tau_{-Nt}^{0}\tau_{Nt}^{\lambda}K^{-1/2}\sum_{0}^{K}\sigma_{x}A)-K^{1/2}\omega_{t}(A).$
(20)

and especially

$\lim_{N\rightarrow\infty}\omega(\tau_{-Nt}^{0}\tau_{Nt}^{\lambda}N^{-1/2}\sum_{0}^{N}\sigma_{x}A)-N^{1/2}\omega_{t}(A).$
(21)

We follow the expansion of Hugenholtz expressed as an expansion in $\lambda.$
A typical $A$ including the translation in space has the form

$\sum_{z_{1},..u_{1},x}\int
dk_{1}..dl_{1}a^{*}(k_{1})..a^{*}(k_{r})..a(l_{1})exp(ik_{1}z_{1}+..-il_{1}u_{1})exp((ik_{1}+---il_{1})x)\bar{f(k_{1})}..g(l_{1}).$
(22)

We concentrate mostly on $r=1$, i.e. on a quadratic $A$. Inserting this into
(4.3) of [5] and starting from the very beginning with a quasifree state
invariant under the unperturbed time evolution from space invariance of the
state we keep the $\delta$-distribution for $(k_{1}-l_{1})$ and similarily for
all other terms expressing the contributions coming from the interaction in
the expansion. Independent in which order we take the limit in (18),(19) and
(20) it tends to $0,$ since in the approach of [5] the fact, that the limit
state is space translation invariant, remains unchanged.

However for the existence of the fluctuation algebra $W(\alpha A)$ is
interpreted as a unitary operator whose second derivative is well defined so
that (17) has to remain bounded. Therefore we have to take into account that
the combination of integration in $t_{r}$ and summation over $x$ gives rise to
additional contributions similar as the combination of integration in $t_{r}$
and $t_{s}$ was responsible for the Boltzmann evolution on the quasilocal
level. Whereas on the quasilocal level only contributions corresponding to

$\int dt_{r}dt_{s}[V(t_{r}),[V(t_{s})a^{*}(f)]..a$ (23)

had to be taken into account because only here the exponant in the $t_{r}$ and
$t_{s}$ integration are properly related, now also with the appropriate
scaling as it enters in (17)

$K/N\sum_{x}^{K}\int dt_{r}dt_{s}[V(t_{r}),a^{*}(f)][V(t_{s}),a(g_{x}))]$ (24)

contributes. Appropriate combinations of twopoint functions give

$\sum^{K}\int^{N}dt_{r}\int^{N}dt_{s}e^{i(\epsilon(l_{r})-\epsilon(m_{r}))(t_{r}-t_{s})}e^{i\epsilon(k_{1})t_{r}}e^{-i\epsilon(k_{2})t_{s})}e^{i(k_{1}-k_{2})x}.$
(25)

Summation over $x$ reduces to values in the integration over the momenta where
$k_{1}-k_{2}$ has to be of order $1/K.$ This effects the integration over
$t_{r}$ and $t_{s}$ only mildly as long as $K<<N$. However it is leading to
$e^{i\epsilon(k_{1})(t_{r}-t_{s})}$ up to negligible order if $K\geq N$ and is
therefore of the same type as the contributions leading to the Boltzmann
equation. Therefore the total integration and summation give additional terms
of order $K/N.$

If for the initial state the fluctuation algebra is well approximated already
for $K$ and the interaction is weak compared to $K$, i.e. $N>>K$ then also in
the scaled time intervall the fluctuations over the corresponding region
remain regular. If the interaction is comparable to $K$, $N=\gamma K$, then
the fluctuations evaluated in a region comparable to the spreading of the
particles remain finite but different from the value that is expected from the
state on the quasilocal algebra, depending on $\gamma$ and therefore also on
$t.$ If however we consider $K>>N$, which corresponds to the assumption that
in the initial state the fluctuation algebra exists as limit in $K$ then we
observe that in the evolved state the fluctuation algebra cannot be
constructed.

It remains to control at which level the construction of the fluctuation
algebra fails. Here we study

$\lim exp(i\sum_{x}^{K}K^{-1/2}\sigma_{x}A-iK^{1/2}\omega(A))=W(A)$ (26)

with selfadjoint $A$ and interpret the limiting operator as the exponential of
a Bosefield with Bosetype commutation relations with operators obtained in the
same limit process. This holds for $t=0$ according to [7] for our choice of
$\omega.$ In addition this Bose field is in a gauge invariant quasifree state
determined by the spacial correlation functions of the underlying quasilocal
state. First we stay in the region where the time evolution is not scaled and
can be interpreted as a time evolution on the Bosefield. Let us choose the
scaling of the interaction $N>>K$. With the scaling of the interaction the
commutator with the Bosefields vanish and the interaction has no effect . Of
interest is the area where $N$ and $K$ are of the same size. The Bose field is
obtained by averaging over a region of size $N$, whereas the interaction acts
everywhere and the free time evolution also shifts the Bosefield. Therefore we
have to consider the Bosefield to be a field on which space translations, now
scaled by the factor $N^{-1}$ act. For finite times

$\tau_{-t}^{0}\tau_{t}^{\lambda}W(G)=W(A)e^{i\int^{t}dt^{\prime}\omega([V(t^{\prime}),A])}.$
(27)

The commutator reduces to a c-number and the interaction has the effect of a
linear shift on the fluctuation algebra as long as $t$ remains small. If
however we increase the time evolution to $N^{1/2}t$, then as in [8] we have
to take into account that $A$ is shifted outside of the previous region. The
commutator with the time translated potential creates a finite contribution of
products of operators with a distance of order $N^{1/2}$ in the exponential
that are not controlled by the quasifree state on the quasilocal algebra. The
scaled space translation becomes effective in addition to the time evolution
and the Bosefield starts to change apart from a linear shift.

We have concentrated on the effect of the evolution on the fluctuation algebra
in space dimension $1$ because here the scaling of the interaction and the
scaling for the fluctuation algebra coincide. In higher dimensions the
appropriate scaling for the fluctuation algebra has to be adjusted to
$K^{\nu/2}$. The scaling for the time evolution remains the same, because it
is determined by the demand that the contribution in first order of the
perturbation in $\lambda$ has to vanish. This has the only consequence that
the relation between time and the area, where spacial correlations fail to
give rise to a fluctuation algebra changes.

There remains a last task: the evolution of the state on the quasilocal level
is expressed in [5] as a differential equation for the twopoint function.
However the form of this equation is only evaluated for $t=0$ and extrapolated
to $t$, though we have seen that $\omega_{t}$ does not satisfy the necessary
demands to justify the limit when considered as starting point. However we can
use for the quasilocal state and time ordered integration

$\frac{d}{dt}\omega_{t}(G)=N^{1/2}\omega(V(t){\cal T}\int
dt^{\prime}..[..(V(t^{\prime}),G)]]).$ (28)

Using that $\omega$ is quasifree and combining in the expansion in $\lambda$
all twopoint functions apart from those of $V(t)$ the combinatoric keeps its
form and the differential equation for the twopoint function remains as for
the initial state.

##  5 Conclusion

Following the strategy in [5] we have extended the rate of convergence to
operators that indicate the amount of spacial correlations as they are
necessary for the construction of the fluctuation algebra. This fluctuation
algebra allows to compare the range of spacial correlations with the time
scale leading to the Boltzmann evolution . Due to the scaling of the
interaction these spacial correlations remain unchanged for finite times. But
if we give the interaction enough time so that the scattering process between
a pair of particles can become effective, which is the inverse time scaling of
the scaling of the interaction, then already the spacial correlations change.
This change is too small to be observed on the local level, but can be
recognized if we pass to the mesoscopic observables of the fluctuation
algebra. With increasing time the fluctuation algebra cannot be constructed
any more and we loose information about mesoscopic observables. If however we
consider the fluctuation algebra in a scaling that is small compared to the
distance particles move then the averaging in the construction is sufficient
and the fluctuation algebra survives. Interpreting this observation in the
language of [4], the two point function of the initial state is given as a
continuous function in distributional sense whereas for the evolved state it
only makes sense as an $L_{\infty}$ function and is therefore defined in a
different, weaker topology. However the control on the possible scaling
together with the effect of averaging in space as it is offered by studying
the fluctuation algebra makes the change in the quality of the twopoint
function more precise.

We can compare the results with those in [8], [9] for a mean field Lindblad
evolution as an example, where the time evolution violates irreversibility and
nevertheless can be obtained in an appropriate setting as the limit of unitary
time evolutions or also for a mean field automorphic time evolution. Here the
evolutions created a change of the quasilocal state producing a map between
fluctuation algebras with different commutation relations, however the
construction of the fluctuation algebra was still possible though producing a
slightly different state for the fluctuation algebra. Therefore spacial
correlations preserved their character up to a small variation. Especially for
a state over the quasilocal algebra that remained constant under the mean
field time evolution the state for the fluctuation algebra the state changed
in time though the fluctuation algebra survived. Here the long range behaviour
of the interaction in its relation to the definition of the fluctuation
algebra was responsible for the different behaviour. Now the state on the
quasilocal level changes in an appropriate scaling. Depending how the
fluctuation algebra can be defined with respect to this scaling its state
changes or even the construction of the algebra fails. Spacial correlations
over mesoscopic distances i. e. distances over which particles move in order
to feel the effect of the interaction get out of control but only to a fine
tuning that cannot be observed on the microscopic level or under the
macroscopic level under a rough averaging.

## References

  * [1] L. Boltzmann: Lectures on Gas Theory, Englich addition
  * [2] O.E. Lanford III: On a Derivation of the Boltzmann Equation, in Nonequilibrium Phenomena I -The Boltzmann Equation, North Holland (1983)
  * [3] R.Illner, M. Pulvirenti: Global Validity of the Boltzmann Equation for a For a Two- and Three Dimensional Rare Gas in Vacuum,Commun.Math. Phys. 121,(1989)
  * [4] R. Illner, H. Neunzert: The Concept of Irreversibility in the Kinetic Theory of Gases, Transport Theory of Statistical Physics 16/1 89-112 (1987)
  * [5] N.M. Hugenholtz: Derivation of the Boltzmann Equation for a Fermi Gas, Journ Stat. Physics, 32/2 231-254 (1983)
  * [6] D. Goderis, A.Verbeure, P. Vets: Commun. Math. Phys. 128533549 (1990)
  * [7] T. Matsui: Rev. Math. Phys. 14675, (2002)
  * [8] F. Benatti, F. Carollo, R. Floreanini, H. Narnhofer: Quantum Fluctuations in Mesoscopic Systems J. Phys. A: Math. Theor 50423001 (2017)
  * [9] F. Benatti, F. Carollo, R. Floreanini, H. Narnhofer: Phys. Lett. A 326 187 (2014)


# The CLRS-Text Algorithmic Reasoning Language Benchmark

Larisa Markeeva  Sean McLeish  Borja Ibarz  Wilfried Bounsi  Olga Kozlova
Alex Vitvitskyi  Charles Blundell  Tom Goldstein  Avi Schwarzschild  Petar
Veličković

###### Abstract

Eliciting reasoning capabilities from language models (LMs) is a critical
direction on the path towards building intelligent systems. Most recent
studies dedicated to reasoning focus on out-of-distribution performance on
procedurally-generated synthetic benchmarks, bespoke-built to evaluate
specific skills only. This trend makes results hard to transfer across
publications, slowing down progress. Three years ago, a similar issue was
identified and rectified in the field of neural algorithmic reasoning, with
the advent of the _CLRS_ benchmark. CLRS is a _dataset generator_ comprising
graph execution traces of classical algorithms from the Introduction to
Algorithms textbook. Inspired by this, we propose CLRS-Text—a textual version
of these algorithmic traces. Out of the box, CLRS-Text is capable of
procedurally generating trace data for thirty diverse, challenging algorithmic
tasks across any desirable input distribution, while offering a standard
pipeline in which any additional algorithmic tasks may be created in the
benchmark. We fine-tune and evaluate various LMs as generalist executors on
this benchmark, validating prior work and revealing a novel, interesting
challenge for the LM reasoning community. Our code is available at
https://github.com/google-deepmind/clrs/tree/master/clrs/_src/clrs_text.

Neural Algorithmic Reasoning, Large Language Models, CLRS, Graph Neural
Networks

##  1 Introduction

In spite of the impressive performance of language models (LMs) in a variety
of scenarios (Google, 2024; OpenAI, 2023), they also exhibit some well-
documented failures, especially when it comes to _reasoning_ problems (Dziri
et al., 2024). Some examples of this relate to reverse concepts (Berglund et
al., 2023), elementary arithmetic (Shen et al., 2023; Zhou et al., 2024) and
geometry (Mouselinos et al., 2024), or recognising higher-order languages
(Delétang et al., 2022). Improving base LM performance on reasoning tasks is
important, as their present unreliability makes them unwieldy to use in
environments requiring robust behaviours, e.g. multi-step planning and
scientific problems.

Reasoning capabilities of LMs are often evaluated using static datasets
requiring mathematical reasoning (Cobbe et al., 2021; Hendrycks et al., 2021)
or QA (Liu et al., 2020; Rein et al., 2023), but it is well-understood that
hill-climbing on any _static_ dataset may result in an illusion of progress,
especially given vast quantities of data available in pre-training corpora.
Even resampling of values on these benchmarks can result in drastic
regressions—a phenomenon known as the _reasoning gap_ (Srivastava et al.,
2024).

To simulate how a model might adapt to unfamiliar situations, many studies
dedicated to improving reasoning in LMs will evaluate out-of-distribution
performance (typically _length generalisation_) on synthetic tasks (Anil et
al., 2022; Zhou et al., 2022, 2023; Ruoss et al., 2023; Zhou et al., 2024;
Sanford et al., 2024). Critically, each of these works constructs a bespoke
dataset, making it hard to evaluate the relative importance of various works.
We notice that, only three years ago, a very similar conundrum affected the
evaluation of algorithmic execution capabilities of graph neural networks (Xu
et al., 2019; Veličković et al., 2019; Tang et al., 2020). Therein, the issue
was successfully addressed with the advent of the _CLRS_ benchmark (Veličković
et al., 2022)—a dataset generator comprising execution traces of thirty
classical algorithms from the Introduction to Algorithms textbook (Cormen et
al., 2022), while allowing for a principled way to generate traces for novel
tasks, enabling several novel research directions (Ibarz et al., 2022;
Bevilacqua et al., 2023; Minder et al., 2023; Jürß et al., 2024).

Our aim is to _bring the benefits of CLRS into language modelling_ , yielding
the CLRS-Text benchmark. CLRS-Text is a procedural dataset generator based on
converting the graph-based traces within CLRS into textual form, making them
suitable for ingestion by language models—see Figure 1, with additional
examples given in Appendix A.

insertion_sort:
key: [5 2 4 3 1], initial_trace: [5 2 4 3 1]
trace | pred:
[2 5 4 3 1], [2 4 5 3 1], [2 3 4 5 1] | [1 2 3 4 5]

Figure 1: Top: The _graph_ algorithmic trace of insertion sorting a list
$[5,2,4,3,1]$ in graph form (reprinted from Veličković et al. (2022)). Bottom:
The same algorithmic trace, represented _textually_ , by using our provided
CLRS-Text generator. The model receives as _input_ (depicted in green) the
input array (key) and the initial value of the sorting trace (initial_trace),
using which it is prompted to predict the _trace_ (depicted in blue) of
gradually sorting the list, by inserting one element at a time into a
partially sorted list, from left to right. At the end, the model needs to
_output_ the final sorted array (depicted in red), and it is evaluated on
whether this array is predicted correctly.

##  2 Motivation

To clarify why we find CLRS-Text to be an important benchmark for evaluating
reasoning capabilities, we will first discuss our operational definition of
reasoning, along with the implications for what a dataset for evaluating this
kind of reasoning might look like.

To us, _reasoning is a robust procedure for solving instances of a problem_.
We impose no requirement for this procedure to be fully accurate: we consider
humans capable of reasoning, yet human reasoning is often approximate or
relies on partial information. Further, we do not require the model to
explicitly trace its computation using symbols—reasoning may be successfully
done in the latent space. The key factor, _robustness_ , implies the model
should behave _consistently_ across diverse problem instances111Or, at least,
the model should be able to give appropriate confidence estimates in its
answers—or even avoid answering altogether—if the input substantially escapes
the support of its training data. This is hard to reconcile with modern
practices of instruction tuning (Wei et al., 2021), which effectively teaches
a model to always attempt to provide answers.. Accordingly, we care about
_out-of-distribution_ generalisation in LMs. And as is already known, even for
relatively simple arithmetic operations such as multiplication, many present
frontier models fail even at modest length generalisation (Shen et al., 2023).

How can we evaluate out-of-distribution generalisation? Firstly, note that
full OOD is hard to encounter or even construct with modern pre-training
setups, wherein LMs are trained on Internet-scale data (though we will provide
results of pre-trained frontier LMs on CLRS-Text as an indication of their
immediate algorithmic reasoning capabilities). Because of this, we argue for
hand-crafting specialised data that we will finetune models on, and also
construct appropriate IID and OOD evaluation datasets for. This is standard
practice in several relevant prior works (Delétang et al., 2022; Ruoss et al.,
2023; Shen et al., 2023).

In order to be able to do this automatically, we need to focus our attention
on tasks that allow outputs to be generated (a) reliably, (b) efficiently, and
(c) for any valid input distribution of interest. These constraints, taken
together with the expectation that reasoning should be a robust procedure,
imply that we should train and evaluate our models on traces of polynomial-
time algorithms, which exactly correspond to robust, well-defined procedures
that perform their computations in a tractable manner.

This is exactly what the CLRS benchmark is designed to do—expose traces of
polynomial-time algorithms in a rigid, efficient and unified manner, for any
valid input distribution. And it is this observation that fuels our decision
to extend CLRS into the textual domain and train language models on its
traces. It is our hope that CLRS-text has the potential to become an important
benchmark for reasoning, precisely because it allows for easy generation of
bespoke trace data at various distributions, and simplifies setting up
comparisons across multiple papers that use it.

Lastly, and conveniently: since we evaluate our model on procedurally-
generated test data, we can constantly _resample_ the test datapoints,
ameliorating risks of reasoning gaps from hill-climbing static datasets
(Srivastava et al., 2024).

##  3 CLRS-Text construction

As already mentioned, CLRS-Text is entirely based on the representations
computed by the CLRS benchmark (Veličković et al., 2022). For a brief recap:
each algorithm in CLRS is specified by _inputs_ , _traces_ 222In the original
CLRS benchmark, the term “hints” is occasionally used instead of “traces”. and
_outputs_ , and by default, CLRS offers access to thirty classical algorithms
from Cormen et al. (2022), spanning sorting, searching, divide & conquer,
greedy algorithms, dynamic programming, graph algorithms, string algorithms
and geometric algorithms.

For each sample of every algorithm, it is assumed that inputs and outputs are
kept fixed, whereas the traces represent the trajectory of (internal) states
the algorithm goes through while computing the output. Since CLRS was
originally designed to train non-autoregressive models, it natively leverages
a _graph_ representation of this data.

In contrast, CLRS-Text converts the trace data to text. How should this
conversion be done? In general, this is something that users of CLRS-Text can
tweak to their needs, by modifying the default converters provided in
clrs_utils.py.

The default conversion function we provide (with outputs illustrated by Figure
1 and Appendix A) is designed with _limited context windows_ in mind. We would
like our traces to completely fit in context of current small-tier models such
as Gemma (Gemma Team et al., 2024), to allow for simplified training at a wide
range of parameter scales. This means that, especially for tasks including
information on edges of graphs ($O(n^{2})$ entries for problems of size $n$),
we cannot afford to print all parts of the algorithm’s trace, and instead we
focus on printing _exactly one variable_ ’s trace—the variable which
eventually converges to the output. In the concrete case of sorting
algorithms, the trace we print is the state of the input array after each step
of the algorithm.

The only algorithm in the thirty default algorithms of CLRS for which we do
not provide a trace is the segment intersection algorithm, as it has $O(1)$
time complexity and therefore does not have atomic steps that converge to the
final output.

Note that, because we do not print the entirety of the algorithm’s state at
every step, it is possible that the trace may remain _unchanged_ in certain
steps—for example, when insertion sorting an already-sorted array of $n$
elements, each of the $n$ steps of the trace will be identical. We argue that
it is _useful_ to encourage the model to produce such traces, as it explicitly
indicates to the model the likely “thinking time” needed for solving the task
through chain of thought (Wei et al., 2022). Further, recent results indicate
that the mere amount of chain of thought tokens may be correlated with the
relative increase in expressive power of Transformer-based language models
(Merrill & Sabharwal, 2023).

Lastly, while CLRS-Text provides the same thirty algorithms present in CLRS by
default, because of the strong synergy of the two benchmarks, adding new
algorithmic tasks to CLRS-Text’s generator requires no significant added
effort compared to adding them to CLRS.

The reader interested in adding new tasks may wish to consult Appendix A of
Veličković et al. (2022) for an overview of key ways to interact with
CLRS—these will apply for CLRS-Text as well. The only change necessary to make
in our default generator script for CLRS-Text is to indicate which part(s) of
the trace should be printed—and in which format—for the newly added algorithm.

##  4 Training and evaluation

Figure 2: Resampling test results of variants of Gemma 2B, and Gemini 1.5
Flash, on various problem sizes. Gemma 2B variants were explicitly trained on
CLRS-Text tasks—the training set sizes are denoted by red dots—and are
evaluated zero-shot. Gemini 1.5 Flash is a pre-trained general-purpose model,
evaluated in a two-shot manner. This plot only shows results on eight
representative algorithms due to space constraints—the detailed plots for all
thirty algorithms are available in Appendix C.

For the main part of our evaluation, we follow a rigorous out-of-distribution
setup, wherein we pre-train a Gemma 2B model (Gemma Team et al., 2024) using
the standard next-token prediction objective on specific problem sizes across
all thirty algorithms provided with CLRS by default. In the spirit of
foundation models (Bommasani et al., 2021), our pre-training follows the style
of a _generalist reasoner_ —building a single multi-task model capable of
executing all thirty algorithms from textual prompts simultaneously.

To demonstrate how CLRS-Text can help assert established results, we also pre-
train a variant of the Gemma 2B model which uses _randomised_ positional
embeddings (RPE)—already shown by Ruoss et al. (2023) to yield better length
generalisation for tasks along the Chomsky hierarchy.

This compares to relevant multi-task learning work on graph-based CLRS (Ibarz
et al., 2022; Georgiev et al., 2024; Bohde et al., 2024), with a
representational advantage in the language case: since the inputs and outputs
are just textual tokens in CLRS-Text, exactly the same language model
architecture can be used for all thirty tasks—whereas for the former papers,
different encoder and decoder functions were necessary due to data and shape
discrepancies.

Once trained, we evaluate our models zero-shot on randomly sampled CLRS-Text
instances for each of the thirty algorithms, at every problem size that would
fit in the model’s context window, up to a maximum size of $n=64$. For each
evaluation prompt, we extract the final array-like object that the language
model produced in its output, and compare it to the ground-truth prompt via
exact string match.

Note that resampling allows us to directly take into account the reasoning gap
across multiple runs (Srivastava et al., 2024), as we will never evaluate on
static test data. Note also that this will evaluate both generalisation on in-
distribution (training) problem sizes, interpolating out-of-distribution sizes
and extrapolating out-of-distribution sizes.

For all our experiments, tool use (in the style of Schick et al. (2024)), as
well as the usage of code interpreters, is explicitly _switched off_. This is
due to the fact we would like to evaluate and improve _base model_
capabilities, without any confounding effects stemming from the tool’s
capabilities.

These confounding effects could be particularly pronounced in the CLRS
context, as the tasks from Introduction to Algorithms are standard hallmark of
a computer science undergraduate degree—hence, their implementations are
omnipresent on GitHub, and it is very likely that most frontier models have
been trained on such source codes. We direct interested readers to McLeish et
al. (2024) for a detailed overview of the kinds of results achievable on a
CLRS-Text variant when using a model with access to a code interpreter.

##  5 Results and Discussion

CLRS-Text lends itself naturally to many different forms of language model
evaluation. We conduct one such evaluation, to provide an indication of how
difficult it is to reliably incorporate algorithmic operations within language
models.

We train two variants of the Gemma 2B model on all thirty tasks, using next-
token prediction, at various training sizes. The first variant is identical to
the original Gemma 2B, whereas the other employs randomised positional
embeddings (Ruoss et al., 2023) with $L=10,000$ (compared with Gemma’s context
length of $N=8,192$).

The training sizes (see Appendix B) are carefully chosen for each algorithm
such that we can evaluate generalisation in both the interpolation and
extrapolation regimes, taking into account Gemma 2B’s context length. Note
that only a single model is trained across all thirty tasks—mirroring the
multi-task setup of Ibarz et al. (2022) for the domain of text.

Evaluation is performed zero-shot, recording average accuracy across five
resampled test sets of $125$ samples for every problem size fitting in
context. Each example is assessed using exact string match on the final array
produced.

While general-purpose frontier models are not necessarily out-of-distribution
with respect to these problems or even these sizes, we believe it is useful to
report the performance of such models on our test sets, to be able to
internalise the gap these models have to cross before they will be capable to
solve CLRS-Text tasks reliably. For this purpose, we include two-shot
evaluation results for Gemini 1.5 Flash (Google, 2024), which is a distilled,
fast version of the frontier model Gemini 1.5 Pro.

We provide results for eight representative algorithms in Figure 2; see
Appendix C for all thirty plots. While our results indicate that the use of
randomised positional embeddings improves generalisation—as shown by Ruoss et
al. (2023)—their effects still taper off quickly in the extrapolation regime.
It is worth noting that, on the graph variant of CLRS, multi-task reasoners
easily generalise to $4\times$ the input sizes seen at training time (Ibarz et
al., 2022), whereas on CLRS-Text, language models barely extrapolate at all.
We suspect that the autoregressive nature of LLMs is to blame—for reasoning
problems, one can often predict multiple parts of the output at once rather
than having to predict them one token at a time, which GNNs can easily
exploit. We highlight this as an important future work direction.

In all cases, the pre-trained general-purpose model is not capable of
achieving comparable results to the fine-tuned Gemma, indicating there exists
a clear improvement in general-purpose algorithmic reasoning which is
attainable with smaller models, that we may manage to make available to our
frontier models in the future.

## References

  * Anil et al. (2022) Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B.  Exploring length generalization in large language models.  _Advances in Neural Information Processing Systems_ , 35:38546–38556, 2022.
  * Berglund et al. (2023) Berglund, L., Tong, M., Kaufmann, M., Balesni, M., Stickland, A. C., Korbak, T., and Evans, O.  The reversal curse: Llms trained on" a is b" fail to learn" b is a".  _arXiv preprint arXiv:2309.12288_ , 2023.
  * Bevilacqua et al. (2023) Bevilacqua, B., Nikiforou, K., Ibarz, B., Bica, I., Paganini, M., Blundell, C., Mitrovic, J., and Veličković, P.  Neural algorithmic reasoning with causal regularisation.  In _International Conference on Machine Learning_ , pp. 2272–2288. PMLR, 2023.
  * Bohde et al. (2024) Bohde, M., Liu, M., Saxton, A., and Ji, S.  On the markov property of neural algorithmic reasoning: Analyses and methods.  _arXiv preprint arXiv:2403.04929_ , 2024.
  * Bommasani et al. (2021) Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Cobbe et al. (2021) Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_ , 2021.
  * Cormen et al. (2022) Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C.  _Introduction to algorithms_.  MIT press, 2022.
  * Delétang et al. (2022) Delétang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wenliang, L. K., Catt, E., Cundy, C., Hutter, M., Legg, S., Veness, J., et al.  Neural networks and the chomsky hierarchy.  _arXiv preprint arXiv:2207.02098_ , 2022.
  * Dziri et al. (2024) Dziri, N., Lu, X., Sclar, M., Li, X. L., Jiang, L., Lin, B. Y., Welleck, S., West, P., Bhagavatula, C., Le Bras, R., et al.  Faith and fate: Limits of transformers on compositionality.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Gemma Team et al. (2024) Gemma Team, Mesnard, T., Hardin, C., Dadashi, R., Bhupatiraju, S., Pathak, S., Sifre, L., Rivière, M., Kale, M. S., Love, J., et al.  Gemma: Open models based on gemini research and technology.  _arXiv preprint arXiv:2403.08295_ , 2024.
  * Georgiev et al. (2024) Georgiev, D. G., Numeroso, D., Bacciu, D., and Liò, P.  Neural algorithmic reasoning for combinatorial optimisation.  In _Learning on Graphs Conference_ , pp. 28–1. PMLR, 2024.
  * Google (2024) Google.  Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context.  _arXiv preprint arXiv:2403.05530_ , 2024.
  * Hendrycks et al. (2021) Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J.  Measuring mathematical problem solving with the math dataset.  _arXiv preprint arXiv:2103.03874_ , 2021.
  * Ibarz et al. (2022) Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Bennani, M., Csordás, R., Dudzik, A. J., Bošnjak, M., Vitvitskyi, A., Rubanova, Y., et al.  A generalist neural algorithmic learner.  In _Learning on graphs conference_ , pp. 2–1. PMLR, 2022.
  * Jürß et al. (2024) Jürß, J., Jayalath, D. H., and Veličković, P.  Recursive algorithmic reasoning.  In _Learning on Graphs Conference_ , pp. 5–1. PMLR, 2024.
  * Liu et al. (2020) Liu, J., Cui, L., Liu, H., Huang, D., Wang, Y., and Zhang, Y.  Logiqa: A challenge dataset for machine reading comprehension with logical reasoning.  _arXiv preprint arXiv:2007.08124_ , 2020.
  * McLeish et al. (2024) McLeish, S., Schwarzschild, A., and Goldstein, T.  Benchmarking chatgpt on algorithmic reasoning.  _arXiv preprint arXiv:2404.03441_ , 2024.
  * Merrill & Sabharwal (2023) Merrill, W. and Sabharwal, A.  The expresssive power of transformers with chain of thought.  _arXiv preprint arXiv:2310.07923_ , 2023.
  * Minder et al. (2023) Minder, J., Grötschla, F., Mathys, J., and Wattenhofer, R.  Salsa-clrs: A sparse and scalable benchmark for algorithmic reasoning.  _arXiv preprint arXiv:2309.12253_ , 2023.
  * Mouselinos et al. (2024) Mouselinos, S., Michalewski, H., and Malinowski, M.  Beyond lines and circles: Unveiling the geometric reasoning gap in large language models.  _arXiv preprint arXiv:2402.03877_ , 2024.
  * OpenAI (2023) OpenAI.  GPT-4 technical report.  _arXiv preprint arXiv:2303.08774_ , 2023.
  * Rein et al. (2023) Rein, D., Hou, B. L., Stickland, A. C., Petty, J., Pang, R. Y., Dirani, J., Michael, J., and Bowman, S. R.  Gpqa: A graduate-level google-proof q&a benchmark.  _arXiv preprint arXiv:2311.12022_ , 2023.
  * Ruoss et al. (2023) Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J., Csordás, R., Bennani, M., Legg, S., and Veness, J.  Randomized positional encodings boost length generalization of transformers.  _arXiv preprint arXiv:2305.16843_ , 2023.
  * Sanford et al. (2024) Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B., and Mirrokni, V.  Understanding transformer reasoning capabilities via graph algorithms.  _arXiv preprint arXiv:2405.18512_ , 2024.
  * Schick et al. (2024) Schick, T., Dwivedi-Yu, J., Dessì, R., Raileanu, R., Lomeli, M., Hambro, E., Zettlemoyer, L., Cancedda, N., and Scialom, T.  Toolformer: Language models can teach themselves to use tools.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Shen et al. (2023) Shen, R., Bubeck, S., Eldan, R., Lee, Y. T., Li, Y., and Zhang, Y.  Positional description matters for transformers arithmetic.  _arXiv preprint arXiv:2311.14737_ , 2023.
  * Srivastava et al. (2024) Srivastava, S., PV, A., Menon, S., Sukumar, A., Philipose, A., Prince, S., Thomas, S., et al.  Functional benchmarks for robust evaluation of reasoning performance, and the reasoning gap.  _arXiv preprint arXiv:2402.19450_ , 2024.
  * Tang et al. (2020) Tang, H., Huang, Z., Gu, J., Lu, B.-L., and Su, H.  Towards scale-invariant graph-related problem solving by iterative homogeneous gnns.  _Advances in Neural Information Processing Systems_ , 33:15811–15822, 2020.
  * Veličković et al. (2019) Veličković, P., Ying, R., Padovano, M., Hadsell, R., and Blundell, C.  Neural execution of graph algorithms.  _arXiv preprint arXiv:1910.10593_ , 2019.
  * Veličković et al. (2022) Veličković, P., Badia, A. P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., and Blundell, C.  The CLRS Algorithmic Reasoning Benchmark.  In _International Conference on Machine Learning_ , pp. 22084–22102. PMLR, 2022.
  * Wei et al. (2021) Wei, J., Bosma, M., Zhao, V. Y., Guu, K., Yu, A. W., Lester, B., Du, N., Dai, A. M., and Le, Q. V.  Finetuned language models are zero-shot learners.  _arXiv preprint arXiv:2109.01652_ , 2021.
  * Wei et al. (2022) Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837, 2022.
  * Xu et al. (2019) Xu, K., Li, J., Zhang, M., Du, S. S., Kawarabayashi, K.-i., and Jegelka, S.  What can neural networks reason about?  _arXiv preprint arXiv:1905.13211_ , 2019.
  * Zhou et al. (2022) Zhou, H., Nova, A., Larochelle, H., Courville, A., Neyshabur, B., and Sedghi, H.  Teaching algorithmic reasoning via in-context learning.  _arXiv preprint arXiv:2211.09066_ , 2022.
  * Zhou et al. (2023) Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., and Nakkiran, P.  What algorithms can transformers learn? a study in length generalization.  _arXiv preprint arXiv:2310.16028_ , 2023.
  * Zhou et al. (2024) Zhou, Y., Alon, U., Chen, X., Wang, X., Agarwal, R., and Zhou, D.  Transformers can achieve length generalization but not robustly.  _arXiv preprint arXiv:2402.09371_ , 2024.

##  Appendix A Algorithmic trace visualisations

Following the examples from Veličković et al. (2022), we now provide
additional trajectory examples captured by CLRS-Text, for a representative
dynamic programming (Figure 3), graph (Figure 4) and string (Figure 5)
algorithm.

matrix_chain_order:
p: [10 30 5 60], initial_trace: [[0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0]]
trace | s:
[[0 0 0 0], [0 0 1 0], [0 0 0 2], [0 0 0 0]] | [[0 0 0 0], [0 0 1 3], [0 0 0 2], [0 0 0 0]]

Figure 3: Top: The _graph_ algorithmic trace of optimising the order of
multiplications in a chain of matrices, for multiplying matrices of size
$(10\times 30)(30\times 5)(5\times 60)$, assuming a $O(n^{3})$-time
multiplication algorithm (reprinted from Veličković et al. (2022)). Bottom:
The same algorithmic trace, represented _textually_ , by using our provided
CLRS-Text generator. The model receives the input matrix sizes (p) and the
initial value of the pointers (initial_trace), using which it is prompted to
predict the trace of gradually determining optimal orders of multiplying
various subchains of the original chain of matrices. Note that, in our default
data generator, we do not store intermediate numbers of operations—only the
pointers are preserved in the trace.

bellman_ford:
s: 0, A: [[0 1 2 0 0], [1 0 0 2 0], [2 0 0 2 3], [0 2 2 0 8], [0 0 3 8 0]],
initial_trace:[0 1 2 3 4]
trace | pi:
[0 0 0 3 4] | [0 0 0 1 2]

Figure 4: Top: The _graph_ algorithmic trace of finding single-source shortest
paths (from node zero) using the Bellman-Ford algorithm, for a given
undirected weighted graph (reprinted from Veličković et al. (2022)). Bottom:
The same algorithmic trace, represented _textually_ , by using our provided
CLRS-Text generator. The model receives the source node identity (s), the
weighted adjacency matrix (A) and the initial value of the predecessor
pointers (initial_trace), using which it is prompted to predict the trace of
gradually recomputing predecessor pointers until all single-source shortest
paths are found. Note that, in our default data generator, we do not store
intermediate path lengths—only the pointers are preserved in the trace.

naive_string_matcher:
string: [0 0 0 1 1], key: [0 0 1 0 1], initial_trace: 0
trace | s:
0, 1 | 1

Figure 5: Top: The _graph_ algorithmic trace of finding the first occurence of
the string ab inside the string aab (reprinted from Veličković et al. (2022)).
Bottom: The same algorithmic trace, represented _textually_ , by using our
provided CLRS-Text generator. The model receives the identifier of which
character belongs to which string (string), the value of each character (key)
and the initial value of the position at which the match is queried
(initial_trace). Using this information, the model is prompted to predict the
trace of gradually adjusting the querying position until a full match is
found.

##  Appendix B Training sizes chosen for Gemma 2B

In order to avoid overwhelming Gemma 2B’s context window and to allow for a
wide range of interpolation and extrapolation problem sizes at test time, we
carefully choose the problem sizes for each algorithm used to generate the
pre-training set for our Gemma 2B variants. Specifically, we leverage the
sizes outlined in Table 1.

The final pre-training set used by Gemma 2B in our experiments is constructed
by taking $10,000$ randomly-sampled prompts of each training size.

Algorithm | Training sizes
---|---
Articulation points | $[4,5,10,11,12,15,19]$
Activity selector | $[4,5,10,11,12,15,19,23,28,31]$
Bellman-Ford | $[4,5,10,11,12,15,19,23,28,31]$
Binary search | $[4,5,10,11,12,15,19,23,28,31]$
Breadth-first search | $[4,5,10,11,12,15,19,23,28,31]$
Bridges | $[4,5]$
Bubble sort | $[4,5,10]$
DAG shortest paths | $[4,5,10,11,12,15,19]$
Depth-first search | $[4,5,10,11,12,15,19,23]$
Dijkstra | $[4,5,10,11,12,15,19,23,28]$
Find Maximum Subarray | $[4,5,10,11,12,15,19,23,28,31]$
Floyd-Warshall | $[4,5,10]$
Graham scan | $[4,5,10,11,12,15,19,23,28,31]$
Heapsort | $[4,5,10]$
Insertion sort | $[4,5,10,11,12,15,19,23,28,31]$
Jarvis’ march | $[4,5,10,11,12]$
Kruskal’s algorithm | $[4,5,10]$
Knuth-Morris-Pratt | $[4,5,10,11,12,15,19,23,28,31]$
Longest common subsequence | $[4,5,10]$
Matrix chain multiplication | $[4,5,10]$
Minimum | $[4,5,10,11,12,15,19,23,28,31]$
Naïve string matcher | $[4,5,10,11,12,15,19,23,28,31]$
Optimal binary search tree | $[4,5,10]$
Prim’s algorithm | $[4,5,10,11,12,15,19,23,28]$
Quickselect | $[4,5,10,11,12,15,19,23,28,31]$
Quicksort | $[4,5,10]$
Segments intersect | $[4,5,10,11,12,15,19,23,28,31]$
Strongly connected components | $[4,5,10,11,12,15]$
Task scheduling | $[4,5,10,11,12,15,19,23,28,31]$
Topological sort | $[4,5,10,11,12,15,19,23]$
Table 1: The training sizes employed for generating the pre-training set used
for Gemma 2B models in our study. Note that, for Segments intersect, the size
parameter does not influence the generated prompt.

##  Appendix C Results on all thirty algorithms

For reasons of brevity, we were unable to show in the main paper the results
of our models on all thirty algorithms presently released in CLRS-Text.
Accordingly, these results—following identical conventions to Figure 2—may be
found in Figure 6.

Figure 6: Resampling test results of variants of Gemma 2B, and Gemini 1.5
Flash, on various problem sizes. Gemma 2B variants were explicitly trained on
CLRS-Text tasks—the training set sizes are denoted by red dots—and are
evaluated zero-shot. Gemini 1.5 Flash is a pre-trained general-purpose model,
evaluated in a two-shot manner.