# Spontaneous stochasticity in the presence of intermittency

André Luís Peixoto Considera  Instituto de Matemática Pura e Aplicada – IMPA,
22460-320 Rio de Janeiro, Brazil  SPEC, CEA, CNRS, Université Paris-Saclay,
CEA Saclay, Gif-sur-Yvette, France  Simon Thalabard  Institut de Physique de
Nice, Université Côte d’Azur CNRS - UMR 7010, 17 rue Julien Lauprêtre, 06200
Nice, France

###### Abstract

Spontaneous stochasticity is a modern paradigm for turbulent transport at
infinite Reynolds numbers. It suggests that tracer particles advected by rough
turbulent flows and subject to additional thermal noise, remain non-
deterministic in the limit where the random input, namely the thermal noise,
vanishes. Here, we investigate the fate of spontaneous stochasticity in the
presence of spatial intermittency, with multifractal scaling of the lognormal
type, as usually encountered in turbulence studies. In principle,
multifractality enhances the underlying roughness, and so should be the
spontaneous stochasticity. This letter exhibits a case with a lesser intuitive
interplay between spontaneous stochasticity and spatial intermittency. We
specifically address Lagrangian transport in uni-dimensional multifractal
random flows, obtained by decorating rough Markovian monofractal Gaussian
fields with frozen-in-time Gaussian multiplicative chaos. Combining systematic
Monte-Carlo simulations and formal stochastic calculations, we evidence a
transition between spontaneously stochastic and deterministic behaviors when
increasing the level of intermittency. While its key ingredient in the
Gaussian setting, here, surprisingly, roughness conspires against the
spontaneous stochasticity of trajectories.

### Introduction.

When transported by a sufficiently turbulent flow, puffs of fluid particles
are known to undergo a phase of algebraic inflation $R\sim t^{3/2}$,
independent from initial separation and now known as Richardson diffusion 1;
2; 3; 4; 5; 6; 7; 8; 9; 10. Beyond the law in itself, Richardson’s seminal
contribution is the intuition that turbulent transport requires some
probabilistic modeling: The modern interpretation involves the phenomenon of
spontaneous stochasticity11; 12; 13; 14; 15; 16, which involves tracers as
fluid particles advected by the fluid and subject to additional thermal noise
of amplitude $\kappa$ 17: In the vanishing viscosity limit, the multi-scale
nature of turbulent flows amplifies thermal noise in such a drastic fashion,
that initially coinciding particles may separate in finite time although they
formally solve the same initial value problem 18; 19; 20, hereby suggesting
intrinsic nature for the underlying randomness.
To date, the scenario of spontaneous stochasticity for Lagrangian separation
is fully substantiated within the theory of Kraichnan flows. Kraichnan flows
are minimal random ersatz of homogeneous isotropic turbulent fields 21; 22;
23; 19; 24; 17; They are defined as white-in-time Gaussian random fields,
whose spatial statistics are centered and prescribed by two-point correlation
with algebraic decay of the kind

$C_{\eta}^{(\xi)}(r)=1-|r|^{\xi}\text{ for $\eta\leq|r|\ll 1$},$ (1)

and vanishing at large scales $\gg 1$. $\eta$ is a scale under which the flow
is smooth, analogous to so-called Kolmogorov scale: The scales $\eta\leq|r|\ll
1$ define the so-called inertial range in turbulence theory. The Hurst
parameter $\xi\in]0;2[$ prescribes the roughness of the field, through
inertial-range scaling $\left\langle(v(x+r)-v(x))^{2}\right\rangle\sim
r^{\xi}$. In the limit $\eta\to 0$, this means that the lesser $\xi$, the
rougher $v$. In this stochastic setting, spontaneous stochasticity essentially
means that some random time accounting for the large-scale dispersion $O(1)$
of a puff of tracers with initial size $O(\eta)$ has probability 1 to be
finite in limits where $\eta,\kappa$ jointly vanish. The limit describes puffs
initially coalescing to a point in prescribed (quenched) space-time velocity
realizations 4; 20. For instance, explicitly considering the relative
separation ${\bf R}(t,{\bf r}_{0}):={\bf X}_{2}(t,{\bf x}_{0}+{\bf
r}_{0})-{\bf X}_{1}(t,{\bf x}_{0})$ between two tracers initiated at $\bf
x_{0},\bf x_{0}+{\bf r}_{0}$, a natural separation time is

$\tau_{1}(\eta,\kappa):=\inf_{\|{\bf r}_{0}\|=\eta}\left\\{t|\|{\bf R}(t,{\bf
r}_{0})\|\geq 1\right\\}.$ (2)

from which we interpret spontaneous stochasticity as the property

$\mathbb{P}\left[\tau_{1}<\infty\right]\to 1\text{ as $\eta,\kappa\to 0$}.$
(3)

Even at this essential level, the presence or the absence of spontaneous
stochasticity in Kraichnan flows depends on a subtle interplay between four
parameters: roughness, incompressibility, space-dimension, reflection rules
for colliding trajectories. To highlight the effect of roughness, we focus on
the uni-dimensional space, hence prescribing unit compressibility, with a
thermal noise $\kappa=\eta$ ensuring that colliding trajectories reflect upon
collision in the limit $\eta\to 0$. The only relevant parameter is then the
roughness exponent $\xi$: Spontaneous stochastic property (3) holds if and
only if $\xi<1$. For $\xi\geq 1$, particles wind up sticking together hence
producing apparent deterministic behavior 25; 17; 26: In short, Kraichan flows
suggest the mantra “The rougher, the more spontaneous stochastic”. In this
letter, we show that the mantra cannot be repeated in the presence of
multifractality, a feature which we later also refer to as spatial
intermittency.

### 1D multifractal Kraichnan flows.

We propose a multifractal uni-dimensional generalization of the Kraichnan
model, which prescribes the motion of $N$ tracers particles
$(X_{i},i\in[|1;N|])$ in terms of the advection-diffusion

$dX_{i}=u_{\eta}^{\xi,\gamma}\left(X_{i}(t),dt\right)+\sqrt{2\kappa}\;B_{i}(dt),$
(4)

where the $B_{i}$’s are independent Brownian motions and we set $\kappa=\eta$
for the thermal noise amplitude: This scaling ensures that close-by tracers
separated by at most $\eta$ diffuse away from each other. The smoothing scale
$\eta$ will ultimately be sent to $0$. The velocity $u_{\eta}^{\xi,\gamma}$
models turbulent advection in a rough multifractal field, prescribed by the
Hurst exponent $\xi\in]0;2[$ and the intermittency parameter $\gamma$. We use
the 1d Markovian version of the spatio-temporal fields constructed by
Chevillard & Reneuve 27

$\begin{split}&u^{\xi,\gamma}_{\eta}(x,dt)=\dfrac{1}{Z_{\eta}}\int_{\mathbb{R}}L^{(\xi)}_{\eta}(x-y)\,e^{\gamma
Y(y)}W_{1}(dy,dt),\\\
&\text{for}\;Y(y):=\int_{\mathbb{R}}L_{\eta}^{(0)}(y-z)W_{2}(dz),\;\;Z_{\eta}:=e^{\gamma^{2}\mathbb{E}\left({Y^{2}}\right)},\end{split}$
(5)

in terms of the mutually independent (1+1) dimensional Wiener processes
$W_{1}$ and Brownian motion $W_{2}$, also independent from the $B_{i}$’s. The
kernels $L^{(\xi)}_{\eta}$ prescribe the Hurst exponent of the velocity field
when $\gamma=0$; They are here defined as convolution square roots of the
correlation function

$C^{(\xi)}(r)=\begin{cases}&\left(1-r^{\xi}\right)\mathbf{1}_{r<1}\text{ for
}\xi>0\\\ &\left(\log\frac{1}{r}\right)\mathbf{1}_{r<1}\text{ for
}\xi=0\end{cases}.$ (6)

The $\eta$-subscript denotes a regularization over small-scale $\eta$, in
practice most easily defined using Fourier transforms 26. Please note that the
expressions (6) indeed represent correlation functions for $0<\xi\leq 1$ 28,
and we therefore restrict our analysis to this range. With this choice, Eq.
(1) are then exactly and not just asymptotically satisfied. Spatial
intermittency is modeled by the term $M_{\eta}^{(\gamma)}=e^{\gamma Y}W(dy)$,
namely the exponentiation of a regularized fractional Gaussian field $Y$ with
vanishing Hurst exponent. This non-trivial operation reguires to be suitably
normalized by the term
$Z_{\eta}=e^{\gamma^{2}\mathbb{E}(Y^{2})}\sim\eta^{-\gamma^{2}}$. When
$\gamma<\sqrt{2}/2\simeq 0.707$, the limit $\eta\to 0$ then produces a well-
defined and non-trivial multifractal random distribution called _Gaussian
multiplicative chaos_ 29; 30; 31; 32 (later referred to as GMC). The
mathematical expectation $\mathbb{E}$ denotes average over this random
environment. The multifractality prescribes the power-law scaling in the
inertial range $\eta\leq r\ll 1$
$S_{p}(\ell):=\left\langle|u(x+r)-u(x)|^{p}\right\rangle\sim
C_{p}|r|^{\zeta(p)}$ in the inertial range $\eta\leq r\ll 1$ with quadratic
variation of the structure function exponents as

$\begin{split}&\zeta(p)=p\left(\xi/2+\gamma^{2}\right)-\gamma^{2}p^{2}/2;\end{split}$
(7)

This a signature of log-normal multifractality – see Fig. 1 for a numerical
illustration using Monte-Carlo averaging with $\eta=2^{-20}$, and the power
law extending over almost 5 decades.

(a)(b)(c)(d)

Figure 1:  (a) Multifractal prediction given by Eq. (7) for $\gamma=0.2$.
Inset shows the correlation function with the power-law decay (1) for
$\xi=\zeta(2)$. (b) Compensated structure functions
$r^{-\xi}\left\langle|\delta u|^{p}\right\rangle^{2/p}\propto
r^{2\zeta(p)/p-\xi}$ for integer orders $1\leq p\leq 6$ (from bottom to top).
Points indicate Monte-Carlo averaging over $512$ samples using $N=2^{20}$
points and smoothing scale $\eta=4\pi/N$. The black shaded lines indicate the
multifractal prediction. (c) Random realizations of the spatial part of (5)
for $\xi=2/3$ and various $\gamma$ . (d) Effective roughess $\xi_{K}$ as a
function of $\gamma$ for various $\xi$. Inset illustrates Definition (8).

Here, the originality of the field (5) comes from its temporal dependence. The
Gaussian component is Markovian, and the random environment (5) is analogous
to a Kraichnan flow when we set the intermittency parameter $\gamma=0$. The
GMC component is random but frozen-in-time: This feature will allow the
spatial intermittency to play out in (4) even at the level of two-particle
dynamics.

### Two wrong intuitions on multi-scaling & spontaneous stochasticity.

Eq. (7) prescribes $\zeta(2)=\xi$, meaning that for the multifractal fields
(5), the two-point correlation (1) is prescribed by the Hurst exponent,
independently from the intermittency parameter $\gamma$. Still, our
multifractal fields are rougher than their mono-fractal counterpart. This is
seen qualitatively from the numerical realizations of Fig. 1 (c): Increasing
$\gamma$ also increases the spikiness of the signal. More quantitatively, the
spatial roughness $\xi_{K}$ of a single realization of the random field
$u^{\xi,\gamma}$ ties to its scaling exponents $\zeta(p)$ through the
classical Kolmogorov continuity theorem 33; 34 as

$\xi_{K}=2\sup_{p}\dfrac{\zeta(p)-1}{p}\leq\xi$ (8)

For $\gamma=0$, the mono-fractal behavior $\zeta(p)=\ p\xi/2$ holds for
arbitrarily large $p$’s, and as such the roughness $\xi_{K}$ identifies to the
Hurst exponent $\xi$. For $\gamma\neq 0$, though, this value is reached at
$p_{K}=\sqrt{2}/\gamma$, which prescribes $\xi_{K}<\xi$ – see Fig 1 (d). On
the one hand, because of this enhanced roughness, one could in principle
expect that tracers advected in the intermittent fields (4) be more likely to
exhibit non-deterministic behavior than in Kraichnan flows, following the
mantra “The rougher, the more spontaneous stochastic”. On the other hand, two-
particle separations in the monofractal Kraichnan flows depend only on
$\zeta(2)=\xi$ 26: One may as well expect that at least at the level of two-
particle separation, one should see no effect of intermittency. We now present
some formal and numerical results, to argue that none of the intuitions above
are in fact correct.

### From random fields to random potentials.

We focus on the dynamics of pair separations, obtained by considering $N=2$ in
Eq. (4). Similar to the Gaussian case 35; 36, tracers advected by Eq. (4) can
be interpreted in terms of particles interacting through a random pairwise
potential, and whose dynamics are prescribed through the stochastic
differential equation (SDE)

$\begin{split}&dX_{i}=\dfrac{1}{Z_{\eta}}\sum_{j=1,2}L_{ij}\left(|X_{1}-X_{2}|\right)e^{\gamma
Y(X_{j})}W_{j}(dt)\\\ &\hskip 113.81102pt+\sqrt{2\kappa}B_{i}(dt)\\\
&\text{with }L(r):=\begin{pmatrix}&1&0\\\
&1-r^{\xi}&\sqrt{1-(1-r^{\xi})^{2}}\\\ \end{pmatrix}\end{split}$ (9)

The matrix $L$ is a discrete analogue to the kernels $L_{\eta}^{(\xi)}$
featured in Eq. (5), except with the regularizing scale $\eta$. It corresponds
to an explicit Choleski decomposition of the correlation matrix
$C_{2}:=C(|X_{i}-X_{j}|)_{i,j=1,2}$ such that $LL^{T}=C_{2}$. As a SDE version
of the original dynamics (4), Eq. (9) comes with two advantages. _(i)_ At a
numerical level, it allows for Monte-Carlo sampling of trajectories without
the need to generate the fields of Eq. (5) at each time-step, similar to the
Gaussian setting 35; 36. _(ii)_ At a formal level, separation-time statistics
can be obtained by means of stochastic calculus and potential theory for
Markov processes, in other words Feynman-Kac like formulas. The word _formal_
is advisory, as the frozen-in-time GMC entering the dynamics could require
cautious mathematical handling31; 37; 38, but this goes way beyond the scope
of the present letter.

### The paradoxical interplay between intermittency and spontaneous
stochasticity.

Stochastic calculus suggests that for prescribed realization of the GMC, the
pair-separation time $T_{1}^{Y}(r)$ from scale $r$ to scale $1$ formally
solves the boundary-value problem

$\begin{split}&\mathcal{L}_{2}^{Y}T_{1}^{Y}=-1\;\;\;\\\ &\text{ with
}T_{1}^{Y}(1)=0\text{ and }\partial_{r}T^{Y}_{1}(\eta)=0,\end{split}$
($\gamma$-BVP)

involving the GMC-dependent operator

$\begin{split}&\mathcal{L}_{2}^{Y}(X_{1},r):=\dfrac{e^{2\gamma
Y(X_{1})}}{2Z_{\eta}^{2}}\left(r^{\xi}+e^{2\gamma\Delta
Y}\left(2-r^{\xi}\right)\right)r^{\xi}\partial_{rr},\end{split}$ (10)

which features the increment $\Delta
Y:=Y\left(X_{1}+r\right)-Y\left(X_{1}\right)$. For $\gamma\neq 0$,
($\gamma$-BVP) features a non-trivial coupling between the pair separation
time and the underlying GMC. Because of this coupling, ($\gamma$-BVP) is not
closed and one cannot a priori solve explicitly for $T_{1}^{Y}$. Setting
$\gamma=0$ retrieves the Gaussian setting and provides such statistical
decoupling17; 26: This makes Eq. ($\gamma$-BVP)-(10) solvable. For $\gamma\neq
0$, we define the annealed separation-time

$\tau_{1}:=\mathbb{E}\left(T_{1}^{Y}\right),$ (11)

where we recall that the expectation $\mathbb{E}\left(\cdot\right)$ denotes an
average over the GMC random environment. A non-trivial decoupling is then
obtained under the mean-field Ansatz

$\mathbb{E}\left(e^{\gamma\Delta
Y}T_{1}^{Y}\right)=\mathbb{E}\left(e^{\gamma\Delta Y}\right)\tau_{1}.$ (12)

For $\eta\ll 1$, ($\gamma$-BVP) under Anzatz (12) formally becomes

$\begin{split}&\mathcal{L}^{*}_{2}\tau_{1}=-1\;\;\;\text{ with
}\tau_{1}(1)=0\text{ and }\partial_{r}\tau_{1}(0)=0,\\\ &\text{ for
}\mathcal{L}_{2}^{*}(r):=\left(1-\dfrac{r^{\xi}}{2}\right)r^{\xi+4\gamma^{2}}\partial_{rr}.\end{split}$
(13)

We refer the reader to Supplemental Material 26 for details on derivations of
(10)-(13) . As for now, we observe that the term $(1-r^{\xi}/2)$ is bounded
and of order $O(1)$. Hence, the separation times behave as if the multifractal
random flows were Gaussian, yet with effective _driving_ Hurst parameter

$\xi_{\gamma}:=\xi+4\gamma^{2}>\xi>\xi_{K}.$ (14)

This Gaussian flow is smoother than the flow at $\gamma=0$ ! This calculation
evidences a highly paradoxical interplay between multifractality, roughness
and spontaneous stochasticity: Increasing $\gamma$ makes the flow rougher in
terms of the effective roughness $\xi_{K}$ deduced from Kolmogorov theorem,
but makes the flow smoother in terms of the spontaneous stochasticity of
tracers, driven by $\xi_{\gamma}$ given above. A practical consequence of Eq.
(14) is the presence of a phase transition driven by $\gamma$, and
characterized by $\xi_{\gamma}=1$. This prescribes the mean-field critical
curve

$\gamma_{c}=\dfrac{1}{2}\sqrt{1-\xi}:$ (15)

For $0<\xi<1$, tracers are spontaneously stochastic when $\gamma<\gamma_{c}$
and deterministic when $\gamma\geq\gamma_{c}$. For $\xi=1$, the Gaussian case
is deterministic, and the critical $\gamma_{c}$ is vanishing, as should be.
For $\xi=0$, this prescribes $\gamma_{c}=1/2$, less than the maximum value
$\sqrt{2}/2$ allowed for the GMC. The critical value $\gamma_{c}$ can
therefore in principle be achieved for any Hurst exponent $\xi\in]0,1]$,

### Numerics.

To illustrate the rationale of the prediction (14) and mean-field Ansatz (12),
we now report results of Monte-Carlo sampling of pair trajectories, obtained
from two different methods, and where we vary the levels of roughness $\xi$,
intermittency $\gamma$ and the regularization scale $\eta$. The first method
is field-based. It uses direct integration of the dynamics (4) with standard
Euler-Maruyama method, and requires to generate a new spatial realization of
the field (5) at each timestep. Tracers are then advected by smoothly
interpolating the velocity field at their current positions. The second method
is SDE-based. It uses the representation (9) in terms of interacting particles
and only requires to generate a single field, namely the frozen GMC, per pair
of trajectories. In the SDE setting, in order to enhance numerical stability,
we add a callback function ensuring exact reflecting boundary conditions for
particles reaching $\eta$.
Beyond the physical parameters $\xi,\gamma,\eta$, both methods require to set
values for the field resolutions $N$ , the number of trajectories $M$
timesteps $dt$ – Table 1 lists the essential numerical parameters. To ensure
finite-time completion of the numerical algorithms, we use a maximal time
$T_{max}$ over which the numerics are stopped, and as such strictly speaking,
our Monte-Carlo sampling therefore does not measure $\tau_{1}(\eta)$ but
rather the estimate $\tilde{\tau}_{1}=\left\langle T_{1}^{Y}\wedge
T_{max}\right\rangle$.

$\xi$ | $\gamma$ | $N$ | $\eta$ | $dt$ | $T_{max}$ | Realizations
---|---|---|---|---|---|---
$2/9$ to $1$ |  $0$ to $0.6$ |  $2^{7}$ to $2^{14}$ | $4\pi/N$ | $10^{-4}$ |  $8$ to $64$ | $10^{5}$
Table 1: Numerical parameters for Fig.2 and Fig. 3 for both methods. For SDE-
based numerics, realizations are independent while fhe field-based numerics,
we use minibatches of 100 trajectories to reach $10^{5}$ samples.

Fig. 2 and Fig. 3 summarize our numerical observations, and those prove
compatible with the mean-field predictions. As seen from Fig. 2, we monitor
two types of behaviors when prescribing $0<\xi<1$. Setting for instance
$\xi=2/3$ as in Panels (a,b), we observe that for small $\gamma$, the
estimates $\tilde{\tau}_{1}$ converge to finite value, independent from
$T_{max}$. Upon decreasing $\eta$, it is found that this value is compatible
with the mean-field prediction
$\tau_{1}^{mf}(\xi_{\gamma})=\left(2(1-\xi_{\gamma})(1-\xi_{\gamma}/2)\right)^{-1}$
involving the Kraichnan flow estimate with the driving Hurst exponent as input
26. This evidences the spontaneous stochastic nature of separations for small
$\gamma$. For large $\gamma$, the apparent convergence of $\tilde{\tau}_{1}$
when decreasing $\eta$ is a numerical artifact, as the limiting value grows
with $T_{max}$. This signals deterministic behavior, with the particles not
separating in the limit $\eta\to 0$. As such, for all the $\xi$ considered,
our numerics reflect the presence of a phase transition at finite value of
$\gamma$. This is in agreement with our mean-field argument, and substantiates
our claim that intermittency here favors deterministic behavior. The onset of
deterministic behavior when increasing $\gamma$ is found to be similar when
using either field-based or SDE-based numerics. Focusing on the cases
$\xi=1/3$ and $\xi=2/3$, we find good compatibility with the mean-field
prediction in the latter case and observe deviations in the former case (see
Panel c). As seen from Panel (d), the mean-field prediction accurately
captures the transition between deterministic and non-deterministic behaviors
for small values of the effective roughness, corresponding to the larger
$\xi$’s, and agreement seems to deteriorate for smaller $\xi$. This
discrepancy suggests that mean-field becomes inaccurate in that regime, but
one cannot rule out a defect of the numerics : As $\xi\to 0^{+}$, the paths
become very rough, and the Euler-Maruyama scheme may become unfit even when
combined with very low timestepping.

(a)(b)(c)(d)

Figure 2:  (a) Convergence with $\eta$ of the separation time at $\xi=2/3$ for
field-based numerics, using maximal simulation times
$T_{max}=8(\triangle),16(\square),32(\diamond),64(\circ)$, for $\gamma=0$
(orange) and $\gamma=0.6$ (green). Dashed line indicates the Kraichnan flow
value. (b) Same but for SDE-based numerics. (c) $\tau_{1}$ against $\gamma$ at
$\xi=1/3$ (red) and $2/3$ (blue) for field-based ($\circ$) and SDE-based
($\times$) numerics, using the smallest $\eta=10^{-3}$ and largest
$T_{max}=64$. (d) Colormap for the average separation time $\tau_{1}$ against
the roughness and intermittency parameters $\xi,\gamma$ from SDE-based
numerics. Data is normalized by $T_{max}=64$, and interpolated from that
measured at the white dots. Red (blue) rendering indicate values close to $0$
(1) hinting towards spontaneous stochastic (deterministic) behavior.

(a)(b)(c)(d)

Figure 3:  (a) 3 Random realizations of initially coalescing pair trajectories
until their separation times $T_{1}$ for driving Hurst parameter
$\xi_{\gamma}=2/3$ with $\xi=2/3,\gamma=0$. (b) Same but with
$\xi=1/3,\gamma=\sqrt{3}/6.$ Color indicates the magnitude of the underlying
GMC, whose profile is represented vertically in the negative axis. (c) PDF of
separation-times obtained from SDE-based numerics for $\xi=2/3,\gamma=0$.
Inset uses log-scale for the $y$-axis. (b) Same but for
$\xi=1/3,\gamma=\sqrt{3}/6$.

Fig. 3 shows the effect of non-Gaussianity playing out at fixed value of the
driving Hurst exponent $\xi_{\gamma}=2/3$ in the spontaneous stochastic
regime. As seen from Panel (a) and (b), the behaviors between Gaussian and
non-Gaussian settings are qualitatively different, although by construction,
both share the same mean-field average separation time. In the Gaussian case,
the GMC $\propto e^{\gamma Y}$ is unity, and the behavior of pairs is
statistically independent from their absolute position. In the non-Gaussian
case, the GMC is non-trivial and we observe dependence with the local values
of the magnitude $\gamma Y$. This is compatible with the fact that Eq. (10)
ruling the pair separations is not closed, unless one further averages over
the GMC realizations. This behavior reflects in the PDF of exit-times. At
large times, the Gaussian setting exhibits the exponential decay $\propto
e^{-t/\tau_{1}}$ predicted by the Kraichnan flow theory 26. The non-Gaussian
case deviates from the exponential behavior; it exhibits fat tails, likely
reflecting particles trapped in quiet “valleys” of the frozen-in-time GMC.
Understanding the details of this slow decay however requires tools more
refined than the present mean-field description and is a matter for future
studies.

### Concluding remarks.

We have proposed a non-trivial extension of the Kraichnan flow theory towards
a multifractal setting, that we obtained by decorating the original Markovian
Gaussian flows with a frozen-in-time Gaussian multiplicative chaos.
Multifractality makes the flow rougher in terms of the Kolmogorov roughness
$\xi_{K}$, but the spontaneous stochasticity of two-particle separation maps
to that of a smoother Gaussian environment, with Hurst exponent
$\xi_{\gamma}>\xi>\xi_{K}$. This paradoxical effect is all the less intuitive
as the second-order structure functions of our parametric family of fields are
characterized by constant $\zeta(2)=\xi$ independent from the level of the
intermittency. The availability of a SDE-based interpretation suggests a new
playground to build a thorough and fundamental understanding of transport in
multifractal environments. This includes, but is not limited to, exploring the
universality and irreversibility of transport, tackling higher-dimensions or
revisiting scalar intermittency. As a side comment on universality, the
specific value of the driving roughness $\xi_{\gamma}$ is clearly model-
dependent. For example, we can mention that using white-in-time versions of
the GMC (not shown here) rather yield $\xi_{\gamma}=\xi$, both from mean-field
and numerics, and this dependence upon time-correlation is reminiscent of that
observed in the Gaussian case 20. One could however expect that the feature
$\xi_{\gamma}\geq\zeta(2)$ is a robust feature of pair-dispersion in
multifractal environments, and this could prove crucial in assessing transport
in genuine turbulent environments. Roughness and intermittency levels measured
in 3D homogeneous isotropic turbulence corresponds to $\xi\simeq 0.69$ and
$\gamma\simeq 0.15$39; 32; 40. In our model, this choice of parameters results
in driving Hurst parameter $\xi_{\gamma}\simeq 0.77$. Transposing this
exponent to a deterministic setting would yield Richardson diffusion $R\sim
t^{1.62}$, significantly different from $t^{3/2}$. Naturally, while they
extend the Kraichnan flows to a more realistic setting, our uni-dimensional
multifractal environments remain caricatures of genuine turbulent fields, and
lack such essential ingredients as skewness, temporal correlations,
incompressiblity, etc. At a more mathematical level, our analysis suggests
that transport in multifractal random flows, be them Eq. (5) or variations
thereof, might prove solvable. Here, the use of a frozen-in-time GMC as a
random environment is strongly reminiscent of the parabolic Anderson model
used in condensed matter physics 41 and the Liouville Brownian motion entering
the construction of field theories in the context of 2d quantum gravity 38;
37. Exploiting those analogies may provide a path towards a rigorous treatment
of transport in multifractal turbulent-like random environments, and
quantitative modeling of turbulent transport in terms of random fields.

## Acknowledgments

We thank A. Barlet, A. Cheminet, B. Dubrulle & A. Mailybaev for continuing
discussions. ST thanks L. Chevillard for essential insights on multifractal
random fields, and acknowledges support from the French-Brazilian network in
Mathematics for visits at Impa in Southern summers 2022 & 2023, where this
work was initiated.

## References

  * [1] L.F. Richardson.  Atmospheric diffusion shown on a distance-neighbour graph.  Proc. Roy. Soc. Lond., 110(756):709–737, 1926.
  * [2] M.-C. Jullien, J. Paret, and P. Tabeling.  Richardson pair dispersion in two-dimensional turbulence.  Phys. Rev. lett., 82(14):2872, 1999.
  * [3] G. Boffetta and I. Sokolov.  Statistics of two-particle dispersion in two-dimensional turbulence.  Phys. Fluids, 14(9):3224–3232, 2002.
  * [4] G. Boffetta and I. Sokolov.  Relative dispersion in fully developed turbulence: the Richardson’s law and intermittency corrections.  Phys. Rev. Lett., 88(9):094501, 2002.
  * [5] R. Bitane, H. Homann, and J. Bec.  Time scales of turbulent relative dispersion.  Phys. Rev. E, 86(4):045302, 2012.
  * [6] S. Thalabard, G. Krstulovic, and J. Bec.  Turbulent pair dispersion as a continuous-time random walk.  J. Fluid Mech., 755:R4, 2014.
  * [7] M. Bourgoin.  Turbulent pair dispersion as a ballistic cascade phenomenology.  J. Fluid Mech., 772:678–704, 2015.
  * [8] D. Buaria, B. Sawford, and P-K. Yeung.  Characteristics of backward and forward two-particle relative dispersion in turbulence at different Reynolds numbers.  Phys. Fluids, 27(10):105101, 2015.
  * [9] S. Tan and R. Ni.  Universality and intermittency of pair dispersion in turbulence.  Phys. Rev. Lett., 128(11):114502, 2022.
  * [10] D. Buaria.  Comment on “Universality and intermittency of pair dispersion in turbulence”.  Phys. Rev. Lett., 130:029401, Jan 2023.
  * [11] E. Lorenz.  The predictability of a flow which possesses many scales of motion.  Tellus, 21(3):289–307, 1969.
  * [12] A. Mailybaev.  Spontaneously stochastic solutions in one-dimensional inviscid systems.  Nonlinearity, 29(8):2238, 2016.
  * [13] A. Mailybaev.  Spontaneous stochasticity of velocity in turbulence models.  Mult. Mod. & Sim., 14(1):96–112, 2016.
  * [14] S. Thalabard, J. Bec, and A. Mailybaev.  From the butterfly effect to spontaneous stochasticity in singular shear flows.  Comm. Phys., 3(1):1–8, 2020.
  * [15] A. Mailybaev and A. Raibekas.  Spontaneously stochastic Arnold’s cat.  Arnold Math. Jour., pages 1–19, 2022.
  * [16] A. Mailybaev and A. Raibekas.  Spontaneous stochasticity and renormalization group in discrete multi-scale dynamics.  arXiv preprint arXiv:2207.06158, 2022.
  * [17] K. Gawędzki.  Soluble models of turbulent transport.  In Non-equilibrium statistical mechanics and turbulence, number 355 in Lond. Math. Soc. Lect. edited by Nazarenko, S. and Zaboronski, O., chapter 2. Cambridge University Press, 2008.
  * [18] W. E and E. Vanden Eijnden.  Generalized flows, intrinsic stochasticity, and turbulent transport.  Proc. Nat. Acad. Sci. U.S.A., 97:8200–8205, 2000.
  * [19] A Kupiainen.  Nondeterministic dynamics and turbulent transport.  Ann. Henri Poincaré, 4(2):713–726, 2003.
  * [20] M. Chaves, K. Gawędzki, P. Horvai, A. Kupiainen, and M. Vergassola.  Lagrangian dispersion in Gaussian self-similar velocity ensembles.  J. Stat. Phys., 113(5):643–692, 2003.
  * [21] G. Falkovich, K. Gawedzki, and M. Vergassola.  Particles and fields in fluid turbulence.  Rev. Mod. Phys., 73(4):913, 2001.
  * [22] Y. Le Jan and O. Raimond.  Integration of Brownian vector fields.  Ann. Probab., 30(2):826–873, 2002.
  * [23] Y. Le Jan and O. Raimond.  Flows, coalescence and noise.  Ann. Probab., 32(2):1247–1315, 2004.
  * [24] K. Gawędzki.  Turbulent advection and breakdown of the Lagrangian flow.  In Intermittency in Turbulent Flows, Edited by Vassilicos, J.C., pages 86–104. Cambridge University Press, 2001.
  * [25] K. Gawędzki and M. Vergassola.  Phase transition in the passive scalar advection.  Phys. D: Nonlin. Phen., 138:63–90, 2000.
  * [26] See Supplemental Material for a short reminder on separation times in Kraichnan flow theory, together with explicit details on both the field-based numerics and mean-field calculations.
  * [27] J. Reneuve and L. Chevillard.  Flow of spatiotemporal turbulent-like random fields.  Phys. Rev. Lett., 125(1):014502, 2020.
  * [28] A. Yaglom.  Correlation Theory of Stationary and Related Random Functions, Volume I: Basic Results, volume 131.  Springer, 1987.
  * [29] L. Chevillard.  Une peinture aléatoire de la turbulence des fluides.  PhD thesis, ENS Lyon, 2015.
  * [30] R. Pereira, C. Garban, and L. Chevillard.  A dissipative random velocity field for fully developed fluid turbulence.  J. Fluid Mech., 794:369–408, 2016.
  * [31] R. Rhodes and V. Vargas.  Gaussian multiplicative chaos and applications: a review.  Probab. Surveys, 11:315–392, 2014.
  * [32] L. Chevillard, C. Garban, R. Rhodes, and V. Vargas.  On a skewed and multifractal unidimensional random field, as a probabilistic representation of Kolmogorov’s views on turbulence.  In Ann. H. Poin., volume 20, pages 3693–3741. Springer, 2019.
  * [33] J.-F. Le Gall.  Brownian motion, martingales, and stochastic calculus.  Springer, 2016.
  * [34] L. Evans.  An introduction to stochastic differential equations, volume 82.  Am. Math. Soc., 2012.
  * [35] U. Frisch, A. Mazzino, and M. Vergassola.  Intermittency in passive scalar advection.  Phys. Rev. Lett., 80(25):5532, 1998.
  * [36] O. Gat, I. Procaccia, and R. Zeitak.  Anomalous scaling in passive scalar advection: Monte-Carlo lagrangian trajectories.  Phys. Rev. Lett., 80(25):5536, 1998.
  * [37] C. Garban, R. Rhodes, and V. Vargas.  Liouville Brownian motion.  2016\.
  * [38] R. Rhodes and V. Vargas.  Lecture notes on Gaussian multiplicative chaos and Liouville quantum gravity.  arXiv preprint arXiv:1602.07323, 2016.
  * [39] B. Dubrulle.  Intermittency in fully developed turbulence: Log-Poisson statistics and generalized scale covariance.  Phys. Rev. lett., 73(7):959, 1994.
  * [40] A. Mailybaev and S. Thalabard.  Hidden scale invariance in Navier–Stokes intermittency.  Phil. Trans. Roy. Soc. A, 380(2218):20210098, 2022.
  * [41] Wolfgang König and Tilman Wolff.  The parabolic Anderson model.  Preprint. Available at www. wiasberlin. de/people/koenig, 2015.


#  From Symbolic Tasks to Code Generation: Diversification Yields Better Task
Performers

Dylan Zhang
University of Illinois
Urbana-Champaign
<EMAIL_ADDRESS>
&Justin Wang
University of Illinois
Urbana-Champaign
<EMAIL_ADDRESS>

&Francois Charton
Meta AI Research
<EMAIL_ADDRESS>

###### Abstract

Instruction tuning – tuning large language models on instruction-output pairs
– is a promising technique for making models better adapted to the real world.
Yet, the key factors driving the model’s capability to understand and follow
instructions not seen during training remain under-explored. Our investigation
begins with a series of synthetic experiments within the theoretical framework
of a Turing-complete algorithm called Markov algorithm, which allows fine-
grained control over the instruction-tuning data. Generalization and
robustness with respect to the training distribution emerge once a diverse
enough set of tasks is provided, even though very few examples are provided
for each task. We extend these initial results to a real-world application
scenario of code generation and find that a more diverse instruction set,
extending beyond code-related tasks, improves the performance of code
generation. Our observations suggest that a more diverse semantic space for
instruction-tuning sets greatly improves the model’s ability to follow
instructions and perform tasks.

##  1 Introduction

The rapid advance of large language models (LLMs) is one of the most exciting
recent developments in artificial intelligence. LLMs, pre-trained on large
text corpora, have demonstrated impressive generalizable reasoning
capabilities and can achieve remarkable performance across a broad set of
tasks, ranging from natural language comprehension [34] and generation [3] to
mathematical reasoning [10] and programming [6]. These models have shown
promise in performing real-world tasks in various applications and business
solutions. One fundamental pillar of such success lies in the capabilities of
these models to perform tasks through generalizable reasoning.

_Instruction tuning_ is a popular approach to unlock the capabilities of these
models originally trained on next-token-prediction objectives to understand
instructions and perform reasoning to complete tasks. By training models on
pairs of instructions and expected outcomes, instruction tuning teaches LLMs
to perform specific tasks, thus enabling them to address real-world problems
and seamlessly interact with humans. In practice, however, fine-tuning data is
limited, and instruction tuning can only focus on a limited set of tasks. Its
success is therefore critically dependent on the model’s ability to generalize
beyond its fine-tuning instructions to _unseen tasks_ not encountered during
training. Several factors influence this generalization: the size of the fine-
tuning sample, the diversity of the instruction sets, and the quality of the
annotations. Yet, there is little systematic research on their relative
impact.

Our work aims to fill this gap by proposing two contributions to the study of
generalization in instruction tuning. First, we propose a systematic analysis
of the impact of instruction diversity by focusing on a simple yet important
symbolic task: string rewrites. This basic setting enables us to exercise fine
control over the factors that may affect generalization and to demonstrate the
importance of instruction diversity. To highlight the broader applicability,
we describe this task in terms of a Markov algorithm, a classic Turing-
complete model, ensuring rigorous examination of string replacements. Second,
we extend this analysis to a real-world application: code generation, and show
that fine-tuning on an instruction set that extends beyond coding tasks
significantly improves performance.

Our main findings are:

  1. 1.

Instruction diversity is the main driver of generalization. Models trained on
a diverse set of instructions generalize better, even when the number of
examples per instruction is small.

  2. 2.

The semantic diversity of instructions matters, together with the number of
instructions.

  3. 3.

Instruction diversity improves model robustness and can compensate for the
adverse impact of non-uniform fine-tuning distributions.

We demonstrate that generalization and robustness with respect to the training
distribution emerge once a diverse enough set of tasks is provided, even
though very few examples are provided for each task. These initial results are
extended to a real-world application scenario of code generation, where we
find that a more diverse instruction set, extending beyond code-related tasks,
improves performance. Our observations suggest that a more diverse semantic
space for instruction-tuning sets greatly improves the model’s ability to
follow instructions and perform tasks.

##  2 Related works

Datasets for instruction-tuning. Many datasets for instruction-tuning have
been proposed. The best quality is achieved for sets collated by human
annotators [18, 42, 31, 38, 27, 11, 21], but their size is constrained by the
cost of annotation. Alternative methods, which use large language models to
generate instruction sets, have been proposed [37, 14, 32, 29, 8, 40, 20, 19].
They provide larger instruction sets, at the cost of reduced annotation
quality.

Data curation for instruction-tuning. It is widely recognized that the quality
of instruction-tuning datasets has a massive impact on the performance of
fine-tuned models. Previous works acknowledged the contributions of several
key factors. Most research on the subject insist on the importance of the size
and quality of the instruction sets [9, 17, 36]. Liang et al. [23] point out
the importance of consistent formats. Several recent works [43, 5] suggest
that models fine-tuned on carefully selected examples can achieve high
performance with small datasets.

Various strategies for data curation have been proposed, focusing on
instruction diversity, and the quality of answers [43, 5, 41, 22, 26]. Several
authors discuss the benefit of mixing tasks from different categories [27, 17,
4]. Closest to our work, Dong et al. [12] discuss the impact of mixing general
and domain-specific instructions, in order to achieve the best results with
the smallest dataset.

##  3 String replacements

Our first synthetic task is _string replacement_. The model is trained to
apply a replacement rule $R$ (a pair of string letters, like $aa\to bac$) to
some string of letters $I$ (e.g. $caaba$), resulting in an output string $O$
(e.g. $cbacba$). Rule $R$ is applied once only, to the leftmost occurrence of
the rule. If rule $R$ be applied, the models returns the initial string $I$.
For instance, applying rule $R:iss\to art$ to $I=mississipi$ yields
$O=martissipi$, and applying $R$ to $I=canada$ yields $O=canada$.

Despite its simplicity, string replacement play a central role in theoretical
computer science and formal logic. It is the basic operation in Markov
Algorithms [28], a Turing-complete model of computation. A Markov algorithm
processes sequences of letters on a fixed alphabet by means of an ordered set
of rewrite rules $R:(x_{i}\rightarrow y_{i})_{i\in\\{1,\dots,n\\}},$ with
$x_{i}$ and $y_{i}$ words over an extended alphabet.

(a) Our string-rewriting task set-up.

(b) Encrypted Re-writing. Similar to the re-writing experiment, but the model
needs to infer the rule of encryption based on the rule of shifting specified
in the instructions and compute the encrypted word.

Figure 1: Illustration of our symbolic tasks in this paper.

When processing a sequence $z_{0}$, the algorithms considers all rules in $R$
in order, finds the first one that applies to $z_{0}$ (say $x_{i}\to y_{i}$),
and produces $z_{1}$ by replacing the leftmost occurence of $x_{i}$ in $z_{0}$
by $y_{i}$. The algorithms is then applied to $z_{1}$, iteratively producing
$z_{2},z_{3},\dots z_{n}$, and terminates either when a special rule of the
form $x_{i}\to\cdot$ is encountered, causing the model to return $z_{n}$, its
last input string, or when no rules can be applied, in which case the
algorithm is said to be blocked (and produces no output). Appendix A provides
examples of Markov algorithms.

Although very simples, Markov algorithms can be show to be Turing-complete:
any finite computation can be implemented by a Markov Algorithm (this is
Markov’s thesis). As a result, a language model that can be trained to
implement string rewrites could in theory become a universal computation
machine (the practical difficulty, here, being the model capability to handle
large number of rules, and its reliability over large numbers of rewrites).

In this paper, we consider two tasks based on string rewrites:

  1. 1.

apply rule $x\to y$ to a sequence containing $x$,

  2. 2.

apply rule $x\to y$ when the sequence contains $x$, return the input sequence
when it does not.

Task $1$ is the base rewrite operation. Task $2$, referred to as “no-op”
involves an additional decision step, on whether the rule is applicable. It is
central to Markov algorithms, where the model must decide, at every step,
which rule to apply.

In our experiments, model inputs and outputs are sequences of the lowercase
letters $a\dots z$. Model inputs are triplets of strings, $(x,y,z)$ (separated
by a special token), representing the rule $x\to y$ and the input sequence
$z$. Model outputs are the strings $z^{\prime}$ obtained by replacing the
leftmost instance of $x$ by $y$, when $x$ is in $z$, or $z$ if $x$ is not in
$z$. Our models uses a very limited vocabulary of $29$ tokens ($26$ lowercase
letters, a special separator token, and beginning and end of sequence tokens).

##  4 Experiments with string replacements

In this first set of experiments, we train GPT-2 [30] models with 256
dimensions, $6$ layers, and $4$ attention heads. The model is trained from
scratch, and supervised, on a generated dataset of instruction/outcome pairs.
The training details can be found in Appendix B.

The training sets include $S\times I$ input sequences, featuring $I$ different
replacements rules (instructions), applied to $S$ different input sequences.
Trained models are then tested on $10^{5}$ examples, all featuring unseen
instructions. The goal of these experiments is to assess the relative impact
of $S$ and $I$ for generalization to unseen instructions (measured by the
accuracy of the trained model on the test set).

(a) Re-writing accuracy against the number of instructions with a fixed-size
training set.

(b) Rewriting with no-op situation included.

Figure 2: Generalization versus the number of instructions during training.

###  4.1 Instruction Diversity Is Decisive To Generalization

Figure 2(a) presents the generalization accuracy for models trained on a fixed
budget of $I\times S=10^{6}$ examples, as a function of the number $I$ of
different instructions in the training set. The number of examples per
instruction ($S$) decreases as $I$ increases. In these experiments, all input
sequences feature at least one instance of the replacement rule: we are
learning task 1.

The accuracy curve has a step shape. Models trained on less than $300$ rules
(instructions) never generalize to unseen instructions, no matter the number
of examples provided for each rule. On the other hand, models trained on
$1000$ rules or more always generalize, even when each rule is featured in a
handful of examples. A sharp phase transition happens around $400$
instructions. We conclude that the number of different rules in the training
set ($I$) is the key factor that allows the model to generalize to unseen
instructions.

###  4.2 Diversification Allows Generalization In Case-Based Reasoning Set-Up

In previous experiments, the model was trained to perform a specific task:
replacing a substring that was always present in the input sequence. We now
consider a more general and challenging setup involving a new task where some
rules may not apply. In such cases, the model returns the input sequence
unchanged. This new setup presents a two-step task: first, the model must
decide whether the rule applies; second, it must either perform the
replacement or copy the input.

This scenario represents a broader context for reasoning with LLMs. In LLM-
agent frameworks, No-Ops are akin to decision points in complex environments
where the agent must determine the relevance of actions based on the current
context [16, 35]..

To explore this, we introduce a third parameter in the training set: the
frequency of “No-Ops” (instructions that cannot be satisfied), which we vary
between 10% and 50%. The size of the training and test sets remains the same
as in previous experiments.

Figure 2(b) presents the generalization accuracies of trained models, as a
function of the number of instructions and the frequency of No-Ops. Accuracies
for Ops and No-Ops unseen instructions are measured separately (these are, in
fact, different tasks). Given the simplicity of No-Ops cases and their
predominance in the data111Consider a dataset containing 100,000 data points,
10% No-Ops, and 100 rules. No-Ops takes up 10,000 in total, $\sim$11$\times$
of any has-Ops., the model defaults to apply it when the number of
instructions are small. Has-Ops cases, on the other hand, display the same
patterns as in the previous experiments: the model exhibits full
generalization to unseen instructions once the training set features more than
a given number of different instructions (around 400, here), below this
number, the model performs the lazy operation of applying No-Ops to all
inputs. Interestingly, the proportion of No-Ops in the training set seems to
have little impact on generalization.

Overall, our conclusions remain consistent with previous experiments, albeit
with a slightly lower number of instructions needed for generalization (400
vs. 500). This demonstrates the effectiveness of diversification in more
complex scenarios involving case-based reasoning.

###  4.3 Imbalanced Distribution Is Still Effective In Driving Generalization

In previous experiments, instructions were evenly distributed between examples
in the training set: in a training set of $1$ million examples, with $500$
different instructions, every instruction would be featured $2000$ times. Such
a situation is unlikely to happen in real-world settings. In real-world
training sets, some tasks will be much more common than others (due to the
availability of fine-tuning data and the nature of the tasks).

(a) Effect of long-tail task distributions on model’s generalization ability.

(b) The sorted percentage of each instruction following power-law distribution
with different shape parameters. The y-axis is the percentage of the rules in
the training mixture. The x-axis is the ranked index (by proportion of
examples) of instructions.

Figure 3: Generalization versus number of instructions during training.

To investigate the impact of the distribution of instructions on
generalization to unseen tasks, we generate datasets of 1,000, 10,000 and
100,000 different instructions, and distribute the number of examples per
instruction according to a power law distribution with PMF $f(x)=\alpha
x^{\alpha-1}$ where $\alpha$ is the shape parameter. By varying the shape
parameter of the power law, we can generate a distribution of examples that
range from close to uniform, to extremely peaked as shown in Fig. 3(b).

Figure 3(a) presents model generalization as a function of the shape parameter
of the power law, for training sets of $1$ million examples with 1,000,
10,000, and 100,000 instructions. Models trained on 10,000 different
instructions or more prove to be robust with respect to the distribution of
examples per instruction. For models trained on $1000$ instructions,
generalization accuracy drop steeply when the shape parameter is larger than
$0.2$. This observation nicely matches the result of previous experiments. In
a training set of $1$ million examples, featuring $1000$ different
instructions distributed according to a power law, instructions with a
probability lower than $0.1\%$ are hardly visible. When the shape parameter
falls below $0.2$, more than half of the instructions are below that
threshold, and the model is effectively trained on less than $500$
instructions, the lower limit for generalization to unseen instructions.

###  4.4 Semantic Diversification Boosts Task Performance

So far, instruction diversity has only been measured in terms of the number of
instructions in the fine-tuning set. We now investigate the impact of semantic
diversity in the instruction set. In the string rewrite setting, we constrain
the semantic diversity of instructions by restraining the patterns that can
appear in the rule substrings. In a semantically diverse set of rules,
instructions would be randomly sampled from every possible sequence of
lowercase letters. In a constrained setting, rule substrings must obey certain
rules, like being composed of repeated letters, or repeated patterns, or
having a palindromic structure.

Specifically, we experiment with three sets of semantic constraints:

  * •

repeated: characters repeated $k$ times: $aaabbbccc$ for $k=3$,

  * •

periodic: patterns repeated $k$ times: $abcabc$ for $k=2$,

  * •

mirror: mirroring patterns repeated $k$ times: $abccbaabc$ for $k=3$,

and train models on sets of rules where both substrings obey the constraint
(e.g. $aaabbb\to bbbccc$). Note that all sets of constrains depend on a
parameter $k$, and that increasing $k$ makes the instruction set less diverse.
To measure the impact of semantic diversity, we train models on instruction
sets with large $k$, and test them on examples with low $k$.

First, we observe that models trained on one set of semantic constraints (e.g.
all instructions repeated, or periodic, or mirror) with high values of $k$,
never generalize to low values of $k$. Models “overfit” the high-$k$ semantic
pattern. Training on a mixture of repeated and periodic instruction (with high
$k$) bring no improvement: the model does not generalize to low $k$, for
either constraint.

Figure 4: Model’s performance on $k<3$ when trained on the three classes of
restricted semantics as in 4.4. Models trained on 500 or less instructions
never generalize to smaller k.

The situation changes when models are trained on a mixture of instructions
from the three constrained sets (Figure 4). Models trained on large $k$ ($k$
between $3$ and $6$ for all three constraints) do generalize to small $k$
($k<3$), and unconstrained instructions. As before the number of training
instructions improves generalization. Models trained on only $500$
instructions do not generalize at all. Models trained on $5000$ achieve high
accuracies. Finally, for a given number of instructions, training on more
constrained sets, i.e. with larger $k$, makes generalization harder.

These experiments prove that instruction diversity goes further than having
many different instructions in the fine-tuning dataset. Models trained on a
diverse set of semantically constrained rules –the string rewrite equivalent
of a diverse set of tasks – generalize to broad sets of less constrained
rules.

###  4.5 Generalization Across Input Semantics

In the previous section, we studied the impact on generalization of the
semantic diversity of instructions. In this section, we focus on the diversity
of the input sequences provided with the rules. Specifically, for a rule
$x_{i}\to y_{i}$, applied to a sequence $s_{i}$, we study the impact of the
distribution of $s_{i}$ in the training set, measured by the number
$\mathcal{O}$ of occurrences of $x_{i}$ in $s_{i}$ (always greater than $1$
for task $1$, this number of always larger than $1$).

Table 1 presents the acccuracy of models trained on instruction sets with
specific values of $\mathcal{O}$, on test sets with a uniform distribution o
$\mathcal{O}$ between $1$ and $20$. For models trained on one value of
$\mathcal{O}$, there is a marked decline in generalization accuracy. And
models with less than $500$ different instructions no longer learn to
satisfactory levels. A more diverse instruction set, featuring with a wider
range of $\mathcal{O}$ ($1,5,10,15$ and $20$) achieves much better
generalization accuracy.

| Number of instructions
---|---
Training set occurences $\mathcal{O}$ | 2000 | 1000 | 500 | 200
1 | 0.71 | 0.41 | 0.00 | 0.00
10 | 0.88 | 0.71 | 0.00 | 0.00
15 | 0.84 | 0.59 | 0.00 | 0.00
20 | 0.73 | 0.28 | 0.07 | 0.00
1,5,10,15,20 | 0.94 | 0.94 | 0.62 | 0.00
Table 1: Generalization across input semantics. $\mathcal{O}$ is the number of
occurrences of the rule substring in the training set. Accuracies are measures
on a test set with $\mathcal{O}$ uniformly distributed between 1 and 20

This concludes our experiments on string replacement. The key takeaway is the
undeniable importance of instruction diversity. To generalize to unseen rules,
models must be trained on large ($\geq 500$) number of different instructions,
featuring diverse rules and instructions.

###  4.6 String replacements with pre-trained models

Extending our results about string replacement to pre-trained models is not
straightforward. After pre-training most LLM can perform string replacements
with high accuracy, and it will be hard to tell whether their performance
after fine-tuning is due to instruction tuning, or to their initial pre-
training. To circumvent this, we introduce a more difficult task: encrypted
rewrites. As in the string replacement task, the model is presented with a
replacement rule $x\to y$ and a string to be replaced $s$, but the input also
contains an encryption key $k$, and the model must replace $x$ by $E(y,k)$,
the encrypted value of $y$ with key $k$: instead of replacing the string
$s=s_{1}xs_{2}$ by $s_{1}ys_{2}$, the model replaces it with
$s_{1}E(y,k)s_{2}$. The encryption algorithm used is the Caesar cipher.

This resembles the scenario of instruction-tuning a pre-trained language
model, where it already has the ability to replace strings, and rotate tokens,
but need to be supervised to capture the meaning of an instruction and follow
it correctly.

(a) Performance of Llama-2 model on the encrypted-rewriting task. We also
conducted uniform / non-uniform sub-samplings to half the total sample size at
9000 instructions. Uniform sub-sampling does not harm performance whereas non-
uniform subsampling impacts generalization.

(b) Effect of long-tail distribution on encrypted-rewriting experiments. As
the number of rules increase, the impact of imbalanced distribution
diminishes.

Figure 5: Generalization versus the number of instructions during training.

We keep two disjoint dictionaries for train and test sets and prompt
GPT-3.5-turbo to generate sentences containing words from the dictionary. If
the word is in the generated sentence, we randomly sample a replacement and
encrypt it with a random key. In no-ops cases, the input should be returned.
We generate training sets of $40,000$ sequences and test them on sets of
$5,000$ instances - each generated using a distinct word in the test
dictionary and again a randomly chosen key. Both sets contain $40\%$ no-ops
cases.

We fine-tuned the pre-trained language model (Llama2-7b) [33] with LoRA [15]
with rank 256 and $\alpha$ of 256 till convergence. Consistent with our
earlier observations, the diversity of instructions benefits the model’s
generalization. With a smaller number of instructions, the pre-trained LLM
also only solves no-op cases but cannot correctly perform the “replace-then-
encrypt” operation (Figure 5(a)). The impact of long-tailed distributions over
rules, in this case, also can be diluted by the diversification of rules
appearing in the dataset, as shown in Figure 5(b).

##  5 Effect of Diversification on Real-World Scenario: Code Generation

Our synthetic experiments suggest that curating datasets with a small number
of diversified instructions significantly enhances model performance for
instruction following. Diversifying instructions improves the model’s ability
to handle previously unseen instructions and benefits the model even if the
dataset does not cover the entire semantic space, provided the restrictions
are not too stringent. Additionally, the model gains from diversification even
in long-tailed distributions, where a few instruction classes dominate. This
highlights that proper diversification can boost specialized models.

(a) Semantic clustering of relevant datasets.

(b) OSS-Alpaca mixture and test instructions.

(c) OSS-COT-Alpaca mixture and test instructions.

Figure 6: Visualization of embedded instructions using OpenAI Embedding model.

This suggests that when constructing real-world instruction-tuning datasets
for some specific task, it may not be necessarily optimal to fine-tune the
model entirely on instruction-response pairs of that specific task. In other
words, given a fixed data budget, it might be better if a certain quantity of
data from a wider range of task domains is included in the instruction
following data, instead of exhausting the budget on the data from that single
domain. In addition, prior works [12] have found that the performance on
coding and math reasoning tasks consistently grows with data size. We
therefore conjecture that an optimal mixture might exist under each setting,
depending on the model, datasets, and number of instances.

###  5.1 Experiments

We demonstrate how the findings from our earlier investigation can potentially
lead to benefits in real-world instruction-following. We experimented with the
task of code generation, in which the model re-writes natural language
descriptions of a program into code. Besides, this task enjoys a relatively
subjective evaluation protocol based on functional correctness. By applying
our insights on instruction diversification to the domain of program
generation, we can effectively assess whether a diversified instruction set
enhances the models’ performance in handling unseen instructions.

We evaluate two popular code generation benchmarks, HumanEval [7] and MBPP
[1], as well as EvalPlus – a widely-adopted augmented version [25] of these
two datasets. We sample training instances from OSS-Instruct [39] dataset for
code generation training. OSS-Instruct is a synthetic dataset generated using
GPT-3.5-turbo and has gone through a sanitizing phase to eliminate data
contamination. We sample $20,000$ training instances from OSS-Instruct as our
baseline instruction-tuning dataset. Then we gradually remove code
instruction-tuning data and incorporate randomly sampled general-domain
instruction-tuning data. We used Alpaca [32], which is one of the most widely-
known instruction datasets for general domain instruction following,
diversified across different domains to spread across a wide semantic domain.
As shown in figure 6(a), its embedding space overlaps with coding, reasoning,
and mathematics domains.

We chose two well-performing pre-trained code LM base models - DeepSeek-
Coder-6.7B-Base [13] and CodeQwen-7B-Base [2].

###  5.2 Instruction Diversity Can Help, But There Is A Price To Pay

#### Inclusion of Non-Coding Data

As shown in tables 2 and 3, extending the semantics of instruction-tuning
data, at a price of even suppressing the number of code generation-specific
data points,

Figure 7: Trend of Pass@1 with data mixture. The baseline result is marked
with dotted lines.

consistently brings better overall performance for code-generation tasks,
which echos our previous findings from string-rewriting experiments. However,
by incorporating general-domain data, we pay a price of less diversification
within the code-generation domain. Our results show that the benefit of
introducing Alpaca data does not accumulate forever as we trade the diversity
within the code generation domain (which is the target domain) with that
across different domains.

This trade-off occurs because while general-domain data can improve the
model’s ability to understand and generate a wider variety of instructions, it
also dilutes the model’s specialization in the code-generation domain [24]. As
the proportion of general-domain data increases, the model’s focus on the
specific patterns and intricacies of code generation diminishes, leading to a
plateau or even a decline in performance on code-generation tasks. Therefore,
there exists the best mixture from which the model achieves optimal
performance for both models respectively, as shown in Figure 7.

| OSS
---
-Inst.
Alpaca | HumanEval | HE+ | MBPP | MBPP+ |  | Avg.
---
(Base)
| Avg.
---
(+)
Avg.
20K | 0 | 62.2 | 56.7 | 75.7 | 62.4 | 68.9 | 59.5 | 64.2
18K | 2K | 68.3 | 61.6 | 75.4 | 63.2 | 71.9 | 62.4 | 67.2
17K | 3K | 64.6 | 60.4 | 76.4 | 63.4 | 70.5 | 61.9 | 66.2
19K | 1K | 67.1 | 59.8 | 75.7 | 62.2 | 71.4 | 61.0 | 66.2
16K | 4K | 65.2 | 58.5 | 76.7 | 63.7 | 71.0 | 61.1 | 66.0
15K | 5K | 64.6 | 57.9 | 73.9 | 61.4 | 69.3 | 59.7 | 64.5
Table 2: Pass@1 on DeepSeek-Coder-6.7B. We highlighted the accuracies
surpassing baseline result with green and those falling below with red.

The results echo our earlier conjecture drawn from the string-rewriting
experiments. The inclusion of the Alpaca dataset highly diversifies the
distribution of SFT data.

| OSS
---
-Inst.
Alpaca | HumanEval | HE+ | MBPP | MBPP+ |  | Avg.
---
(Base)
| Avg.
---
(+)
Avg.
20K | 0 | 65.9 | 59.8 | 73.7 | 62.2 | 69.8 | 61.0 | 65.4
18K | 2K | 69.5 | 63.4 | 76.4 | 63.2 | 73.0 | 63.3 | 68.1
17K | 3K | 68.3 | 62.8 | 76.7 | 63.9 | 72.5 | 63.4 | 67.9
19K | 1K | 67.7 | 61.6 | 75.9 | 63.4 | 71.8 | 62.5 | 67.2
15K | 5K | 67.1 | 62.8 | 75.2 | 62.4 | 71.2 | 62.6 | 66.9
16K | 4K | 65.2 | 58.5 | 76.7 | 63.7 | 71.0 | 61.1 | 66.0
Table 3: Pass@1 with CodeQwen-7B. We highlighted the accuracies surpassing
baseline result with green and those falling below with red.

Although the majority of the training data still centers around the code
generation domain, the instructions in the Alpaca dataset span across a larger
semantic space. Also, although only a small number of instances are included
for each since the total number of instructions is large enough and the
semantics are diverse enough, the small number of data does play a part in
boosting the model’s code generation performance.

Data Mixture | Ratio | HumanEval | HE+ | MBPP | MBPP+ |  | Avg.
---
(Base)
| Avg.
---
(+)
Avg.
O | - | 65.9 | 59.8 | 73.7 | 62.2 | 69.8 | 61.0 | 65.4
O+A | 18:2 | 69.5 | 63.4 | 76.4 | 63.2 | 73.0 | 63.3 | 68.1
O+C+A | 18:1:1 | 68.9 | 63.4 | 77.4 | 64.2 | 73.2 | 63.8 | 68.5
O+A | 16:4 | 65.2 | 58.5 | 76.7 | 63.7 | 71.0 | 61.1 | 66.0
O+C+A | 16:2:2 | 68.3 | 61.6 | 77.2 | 63.7 | 72.8 | 62.7 | 67.7
O+A | 17:3 | 68.3 | 62.8 | 76.7 | 63.9 | 72.5 | 63.4 | 67.9
O+C+A | 17:1.5:1.5 | 68.3 | 61.6 | 75.4 | 62.9 | 71.9 | 62.3 | 67.1
Table 4: CodeQwen-7B-Base trained with mixture of OSS-Instruct, CoT Collection
and Alpaca.O stands for OSS-Instruct, C stands for CoT-Collection and A stands
for Alpaca. The best results for each ratio are boldfaced.

#### Diversification Across Domains

As found in Section 4.4, diversification across instruction semantics is yet
another important dimension. As illustrated in Figure 6(a) each instruction-
tuning dataset cluster around a specific subspace of semantics, a further
variety among instruction semantics could be obtained by further incorporating
other datasets that cover a different space. Since the Alpaca dataset was
mainly curated to build language model assistants that are optimized for
interaction with humans, we consider expanding the semantics domain further by
additionally incorporating data that requires more complex, multi-hop
reasoning from the CoT-Collection dataset [19] which contains reasoning
problems and chain-of-thought style responses.

As shown in Figure 4, we observe the CoT data indeed is complementary in its
semantics space to the OSS-Alpaca mixture. To investigate the effect of
diversification across semantics domains, we trained the models with various
OSS-Instruct v.s. non-coding ratios and benchmarked their performances against
previous results. The primary goal of this experiment is to explore the
benefits of further extending the semantics domain rather than finding the
optimal mixture. Therefore, we used equal numbers of instances from the Alpaca
and CoT-Collection datasets to rule out additional confounding factors.

The results obtained using CodeQwen are presented in Table 4. Consistent with
our findings from string replacement, the model trained on the optimal ratio
within the 3-way mixture outperforms the one trained on the optimal OSS-
Instruct + Alpaca mixture. This outcome reinforces the advantages of cross-
domain diversification in enhancing model performance. However, it is
important to note that this performance boost may not be consistent across all
splits. When comparing the mix ratios of $OSS:CoT=17:1.5:1.5$ and $OSS=17:3$,
we observe a performance decline when CoT data is included. We conjecture that
the effectiveness of diversification is influenced by the specific mix ratio
between the datasets used.

Mix | Ratio |  | Total
---
#Data
HE | HE+ | MBPP | MBPP+ |  | Avg
---
(Base)
| Avg
---
(+)
Avg | Rel.↑
O | - | 75K | 66.5 | 61.6 | 75.4 | 61.9 | 71.0 | 61.8 | 66.4 | -
O+A | 60:15 | 75K | 67.1 | 59.8 | 77.0 | 64.8 | 72.1 | 62.3 | 67.2 | 1.2
O+A | 67.5:7.5 | 75K | 68.9 | 61.6 | 76.2 | 63.8 | 72.6 | 62.7 | 67.6 | 1.9
O+A | 72.5:2.5 | 75K | 68.3 | 61.0 | 76.2 | 64.3 | 72.3 | 62.7 | 67.5 | 1.6
O+A | 74:1 | 75K | 69.5 | 62.2 | 76.2 | 64.3 | 72.9 | 63.3 | 68.1 | 2.5
O+C+A | 60:7.5:7.5 | 75K | 64.6 | 59.1 | 76.2 | 63.8 | 70.4 | 61.5 | 65.9 | -0.6
O+C+A | 67.5:3.25:3.25 | 75K | 66.5 | 62.2 | 76.2 | 64.3 | 71.4 | 63.3 | 67.3 | 1.4
O+C+A | 72.5:1.25:1.25 | 75K | 68.3 | 62.2 | 77.8 | 65.1 | 73.1 | 63.7 | 68.4 | 3.0
O+C+A | 74:0.5:0.5 | 75K | 66.5 | 61.0 | 76.5 | 63.2 | 71.5 | 62.1 | 66.8 | 0.7
Table 5: Comparison With MagiCoder-DS-6.7B [39]. We demonstrated that one
could achieve higher performances by means of diversification.

###  5.3 Beating Open Source Code-LMs With Its Own Data (+ Diversification)

As yet a further step to demonstrate the benefit of diversification, we train
a code language model by applying the same ideas of diversification to the
whole OSS-Instruct dataset and compare the performance against the model
trained on it: MagiCoder-DS-6.7B [39]. We train all the trainable weights
(instead of LoRA) in this set of experiments. As shown in Table 5, appropriate
diversification still leads to performance advantages. The observations are
also consistent with our earlier experiments for code generation and string
replacement, where a small fraction of non-coding data can drive performance
gain, and that diversifying across multiple domains can push the performance
even higher.

##  6 Conclusion and Limitations

Through our symbolic experiments, we have shown that language models only
generalize to instructions unseen during training when trained on a large and
diverse set of instructions. For a fixed data budget, instruction diversity
outweighs better illustration (i.e. more examples) for each instruction. These
observations apply not only to the number of different instructions in the
dataset but also to their semantic diversity. The negative effect of an
unbalanced distribution of examples can be counteracted by a larger number of
instructions in the training set. Putting all these together, this implies the
possibility of improving the model’s performance on some task by incorporating
a small portion of data from other task domains. We demonstrated that
diversity can bring benefits for real-world instruction following using the
example scenario of code generation, and provided insights into effective
diversification for better task performances.

#### Limitations

We did not propose an algorithm to find the best data mixture including
domains and ratios for task-specific instruction-tuning but differed the
methods to search for the optimal strategy of diversification for future work.

## Acknowledgement

We thank Chi Han, Jialiang Xu, Yifeng Ding and Yuchen Li for providing
suggestions and valuable feedback on this project.

## References

  * [1] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton.  Program synthesis with large language models, 2021.
  * [2] Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang, Shijie Wang, Wei Wang, Shengguang Wu, Benfeng Xu, Jin Xu, An Yang, Hao Yang, Jian Yang, Shusheng Yang, Yang Yao, Bowen Yu, Hongyi Yuan, Zheng Yuan, Jianwei Zhang, Xingxuan Zhang, Yichang Zhang, Zhenru Zhang, Chang Zhou, Jingren Zhou, Xiaohuan Zhou, and Tianhang Zhu.  Qwen technical report, 2023.
  * [3] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners, 2020.
  * [4] Alexander Bukharin and Tuo Zhao.  Data diversity matters for robust instruction tuning, 2024.
  * [5] Yihan Cao, Yanbin Kang, Chi Wang, and Lichao Sun.  Instruction mining: When data mining meets large language model finetuning, 2023.
  * [6] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba.  Evaluating large language models trained on code, 2021.
  * [7] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba.  Evaluating large language models trained on code, 2021.
  * [8] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023.
  * [9] Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Alex Castro-Ros, Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei.  Scaling instruction-finetuned language models, 2022.
  * [10] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems, 2021.
  * [11] Mike Conover, Matt Hayes, Ankit Mathur, Jianwei Xie, Jun Wan, Sam Shah, Ali Ghodsi, Patrick Wendell, Matei Zaharia, and Reynold Xin.  Free dolly: Introducing the world’s first truly open instruction-tuned llm, 2023.
  * [12] Guanting Dong, Hongyi Yuan, Keming Lu, Chengpeng Li, Mingfeng Xue, Dayiheng Liu, Wei Wang, Zheng Yuan, Chang Zhou, and Jingren Zhou.  How abilities in large language models are affected by supervised fine-tuning data composition, 2024.
  * [13] Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, Y. K. Li, Fuli Luo, Yingfei Xiong, and Wenfeng Liang.  Deepseek-coder: When the large language model meets programming – the rise of code intelligence, 2024.
  * [14] Or Honovich, Thomas Scialom, Omer Levy, and Timo Schick.  Unnatural instructions: Tuning language models with (almost) no human labor, 2022.
  * [15] Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen.  Lora: Low-rank adaptation of large language models, 2021.
  * [16] Xu Huang, Weiwen Liu, Xiaolong Chen, Xingmei Wang, Hao Wang, Defu Lian, Yasheng Wang, Ruiming Tang, and Enhong Chen.  Understanding the planning of llm agents: A survey, 2024.
  * [17] Srinivasan Iyer, Xi Victoria Lin, Ramakanth Pasunuru, Todor Mihaylov, Daniel Simig, Ping Yu, Kurt Shuster, Tianlu Wang, Qing Liu, Punit Singh Koura, et al.  Opt-iml: Scaling language model instruction meta learning through the lens of generalization.  arXiv preprint arXiv:2212.12017, 2022.
  * [18] Daniel Khashabi, Sewon Min, Tushar Khot, Ashish Sabharwal, Oyvind Tafjord, Peter Clark, and Hannaneh Hajishirzi.  UNIFIEDQA: Crossing format boundaries with a single QA system.  In Trevor Cohn, Yulan He, and Yang Liu, editors, Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1896–1907, Online, November 2020. Association for Computational Linguistics.
  * [19] Seungone Kim, Se June Joo, Doyoung Kim, Joel Jang, Seonghyeon Ye, Jamin Shin, and Minjoon Seo.  The cot collection: Improving zero-shot and few-shot learning of language models via chain-of-thought fine-tuning, 2023.
  * [20] Abdullatif Köksal, Timo Schick, Anna Korhonen, and Hinrich Schütze.  Longform: Optimizing instruction tuning for long text generation with corpus extraction, 2023.
  * [21] Andreas Köpf, Yannic Kilcher, Dimitri von Rütte, Sotiris Anagnostidis, Zhi-Rui Tam, Keith Stevens, Abdullah Barhoum, Nguyen Minh Duc, Oliver Stanley, Richárd Nagyfi, Shahul ES, Sameer Suri, David Glushkov, Arnav Dantuluri, Andrew Maguire, Christoph Schuhmann, Huu Nguyen, and Alexander Mattick.  Openassistant conversations – democratizing large language model alignment, 2023.
  * [22] Ming Li, Lichang Chen, Jiuhai Chen, Shwai He, Jiuxiang Gu, and Tianyi Zhou.  Selective reflection-tuning: Student-selected data recycling for llm instruction-tuning, 2024.
  * [23] Shihao Liang, Runchu Tian, Kunlun Zhu, Yujia Qin, Huadong Wang, Xin Cong, Zhiyuan Liu, Xiaojiang Liu, and Maosong Sun.  Exploring format consistency for instruction tuning, 2024.
  * [24] Chen Ling, Xujiang Zhao, Jiaying Lu, Chengyuan Deng, Can Zheng, Junxiang Wang, Tanmoy Chowdhury, Yun Li, Hejie Cui, Xuchao Zhang, Tianjiao Zhao, Amit Panalkar, Dhagash Mehta, Stefano Pasquali, Wei Cheng, Haoyu Wang, Yanchi Liu, Zhengzhang Chen, Haifeng Chen, Chris White, Quanquan Gu, Jian Pei, Carl Yang, and Liang Zhao.  Domain specialization as the key to make large language models disruptive: A comprehensive survey, 2024.
  * [25] Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang.  Is your code generated by chatgpt really correct? rigorous evaluation of large language models for code generation, 2023.
  * [26] Liangxin Liu, Xuebo Liu, Derek F. Wong, Dongfang Li, Ziyi Wang, Baotian Hu, and Min Zhang.  Selectit: Selective instruction tuning for large language models via uncertainty-aware self-reflection, 2024.
  * [27] Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoc V. Le, Barret Zoph, Jason Wei, and Adam Roberts.  The flan collection: Designing data and methods for effective instruction tuning, 2023.
  * [28] A. A. Markov.  The theory of algorithms, volume 42.  Acad. Sci. USSR, 1954.
  * [29] Baolin Peng, Chunyuan Li, Pengcheng He, Michel Galley, and Jianfeng Gao.  Instruction tuning with gpt-4, 2023.
  * [30] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners, 2019.
  * [31] Victor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, Manan Dey, M Saiful Bari, Canwen Xu, Urmish Thakker, Shanya Sharma Sharma, Eliza Szczechla, Taewoon Kim, Gunjan Chhablani, Nihal Nayak, Debajyoti Datta, Jonathan Chang, Mike Tian-Jian Jiang, Han Wang, Matteo Manica, Sheng Shen, Zheng Xin Yong, Harshit Pandey, Rachel Bawden, Thomas Wang, Trishala Neeraj, Jos Rozen, Abheesht Sharma, Andrea Santilli, Thibault Fevry, Jason Alan Fries, Ryan Teehan, Tali Bers, Stella Biderman, Leo Gao, Thomas Wolf, and Alexander M. Rush.  Multitask prompted training enables zero-shot task generalization, 2022.
  * [32] Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto.  Stanford alpaca: An instruction-following llama model.  https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * [33] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open foundation and fine-tuned chat models, 2023.
  * [34] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman.  Superglue: A stickier benchmark for general-purpose language understanding systems, 2020.
  * [35] Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, Wayne Xin Zhao, Zhewei Wei, and Jirong Wen.  A survey on large language model based autonomous agents.  Frontiers of Computer Science, 18(6), 2024.
  * [36] Yizhong Wang, Hamish Ivison, Pradeep Dasigi, Jack Hessel, Tushar Khot, Khyathi Raghavi Chandu, David Wadden, Kelsey MacMillan, Noah A. Smith, Iz Beltagy, and Hannaneh Hajishirzi.  How far can camels go? exploring the state of instruction tuning on open resources, 2023.
  * [37] Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi.  Self-instruct: Aligning language models with self-generated instructions, 2023.
  * [38] Yizhong Wang, Swaroop Mishra, Pegah Alipoormolabashi, Yeganeh Kordi, Amirreza Mirzaei, Anjana Arunkumar, Arjun Ashok, Arut Selvan Dhanasekaran, Atharva Naik, David Stap, Eshaan Pathak, Giannis Karamanolakis, Haizhi Gary Lai, Ishan Purohit, Ishani Mondal, Jacob Anderson, Kirby Kuznia, Krima Doshi, Maitreya Patel, Kuntal Kumar Pal, Mehrad Moradshahi, Mihir Parmar, Mirali Purohit, Neeraj Varshney, Phani Rohitha Kaza, Pulkit Verma, Ravsehaj Singh Puri, Rushang Karia, Shailaja Keyur Sampat, Savan Doshi, Siddhartha Mishra, Sujan Reddy, Sumanta Patro, Tanay Dixit, Xudong Shen, Chitta Baral, Yejin Choi, Noah A. Smith, Hannaneh Hajishirzi, and Daniel Khashabi.  Super-naturalinstructions: Generalization via declarative instructions on 1600+ nlp tasks, 2022.
  * [39] Yuxiang Wei, Zhe Wang, Jiawei Liu, Yifeng Ding, and Lingming Zhang.  Magicoder: Source code is all you need, 2023.
  * [40] Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang.  Wizardlm: Empowering large language models to follow complex instructions, 2023.
  * [41] Yang Xu, Yongqiang Yao, Yufan Huang, Mengnan Qi, Maoquan Wang, Bin Gu, and Neel Sundaresan.  Rethinking the instruction quality: Lift is what you need, 2023.
  * [42] Qinyuan Ye, Bill Yuchen Lin, and Xiang Ren.  Crossfit: A few-shot learning challenge for cross-task generalization in nlp, 2021.
  * [43] Chunting Zhou, Pengfei Liu, Puxin Xu, Srini Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, Lili Yu, Susan Zhang, Gargi Ghosh, Mike Lewis, Luke Zettlemoyer, and Omer Levy.  Lima: Less is more for alignment, 2023.

##  Appendix A Complement on Markov algorithms

Markov algorithms [28] are ordered sets of rewrite rules, operating on
sequences of symbols in a fixed alphabet $\mathcal{U}$. A sequence $S$ is
processed by applying the first rewrite applicable to $S$, at the leftmost
position if several exist: i.e. the rewrite rule $ss\to tr$ transforms the
sequence $S=mississipi$ into $S^{\prime}=mitrissipi$. The algorithm is then
applied to $S^{\prime}$, and the process is repeated until either no rules
apply, and the algorithm is said to be _blocked_ , or a special rule, called a
_stop rule_ is invoked, and the algorithm terminates and returns the final
rewritten sequence.

Specifically, the algorithm uses and alphabet $\mathcal{A}$, which includes
the alphabet $\mathcal{U}$ used buy the sequences to be processed (henceforth,
small case latin letters), a set of additional symbols (henceforth, the small
case greek letters $\\{\alpha,\beta\dots\\}$, and a special symbol $\cdot$
indicating a stop rule.

For instance, we could define the following algorithm, with
$\mathcal{U}=\\{a,b\\}$, and $\mathcal{A}=\\{a,b,\alpha,\beta,\cdot\\}$, and
the rules

$\displaystyle\alpha x$ $\displaystyle\to$ $\displaystyle x\alpha\beta x$ (1)
$\displaystyle\beta xy$ $\displaystyle\to$ $\displaystyle y\beta x$ (2)
$\displaystyle\alpha\beta x$ $\displaystyle\to$ $\displaystyle x\alpha$ (3)
$\displaystyle\alpha$ $\displaystyle\to$ $\displaystyle\cdot$ (4)
$\displaystyle\to$ $\displaystyle\alpha$ (5)

where $x$ and $y$ stand for any letter $a$ or $b$. This will transform any
sequence of $a$ and $b$ into a concatenation of the sequence and its reverse.
Applied on $abb$, the algorithm will perform the following rewrites:

$\displaystyle abb$ $\displaystyle\to\alpha abb$ $\displaystyle(\text{by }5)$
$\displaystyle\alpha abb$ $\displaystyle\to a\alpha\beta abb$
$\displaystyle(\text{by }1)$ $\displaystyle a\alpha\beta abb$
$\displaystyle\to a\alpha b\beta ab$ $\displaystyle(\text{by }2)$
$\displaystyle a\alpha b\beta ab$ $\displaystyle\to ab\alpha\beta b\beta ab$
$\displaystyle(\text{by }1)$ $\displaystyle ab\alpha b\beta b\beta ab$
$\displaystyle\to ab\alpha\beta bb\beta a$ $\displaystyle(\text{by }2)$
$\displaystyle ab\alpha\beta bb\beta a$ $\displaystyle\to ab\alpha b\beta
b\beta a$ $\displaystyle(\text{by }2)$ $\displaystyle ab\alpha b\beta b\beta
a$ $\displaystyle\to abb\alpha\beta b\beta b\beta a$ $\displaystyle(\text{by
}1)$ $\displaystyle abb\alpha\beta b\beta b\beta a$ $\displaystyle\to
abbb\alpha\beta b\beta a$ $\displaystyle(\text{by }3)$ $\displaystyle
abbb\alpha\beta b\beta a$ $\displaystyle\to abbbb\alpha\beta a$
$\displaystyle(\text{by }3)$ $\displaystyle abbbb\alpha\beta a$
$\displaystyle\to abbbba\alpha$ $\displaystyle(\text{by }3)$ $\displaystyle
abbbba\alpha$ $\displaystyle\to abbbba$ $\displaystyle(\text{by }4)$

Since rule $4$ is a stop rule, the algorithm terminates and returns $abbbba$.

Judicious introduction of additional (greek) letters allows one to compose
Markov algorithms, effectively writing complex programs. Any effective process
(i.e. finite computation) can be represented as a Markov algorithm (this is
Markov’s thesis).

##  Appendix B Experimental set-up

###  B.1 Model and Training

In rewrite experiments, we train GPT-2 models [30], a decoder-only
transformer-based architecture, with $6$ layers, $256$ dimensions and $4$
attention heads from scratch, on a generated instruction-tuning dataset using
standard supervised fine-tuning approach. We use the AdamW optimizer, a
learning rate of $10^{-3}$, and linear scheduling. All models are trained for
50 epochs. For the encrypted-rewriting task, we LoRA fine-tuned Llama-2 models
with a learning rate of 1e-5, batch size 64, gradient accumulation step 1, and
8-bit quantization. The model takes about 2000 steps to converge. For coding
experiments, we trained the model with a learning rate of 1e-5, batch size 4,
and gradient accumulation step 1, 8-bit quantization for 3 epochs with a
maximum length of 768. The models are trained and inferenced on 1 Nvidia A40
GPU. We used greedy decoding for all experiments.

###  B.2 Data Generation

#### Synthetic Experiment

Except for the diversity of semantics experiment, the results we reported in
the main paper are obtained from an input length of 50 and a pattern length of
20. To validate the generality of our findings, we conducted experiments on
various input sizes {50, 100, 200} and, correspondingly, pattern lengths
{20,40,50}.

In the diversity of semantics experiment, we used an input length of 500 and a
pattern length of 60. We strictly restricted the sub-strings to look for and
to replace them with both to be unseen during testing.

#### Code Generation

We downloaded the data from the official Huggingface Datasets Repos.