Relations between Schoenberg Coefficients on Real and Complex Spheres

Relations between Schoenberg Coefficients
on Real and Complex Spheres of Different Dimensions

Pier Giovanni BISSIRI †, Valdir A. MENEGATTO ‡ and Emilio PORCU †§

P.G. Bissiri, V.A. Menegatto and E. Porcu

† School of Mathematics $\&$ Statistics, Newcastle University,
† Newcastle Upon Tyne, NE1 7RU, UK<EMAIL_ADDRESS><EMAIL_ADDRESS>
‡ Instituto de Ciências Matemáticas e de Computação, Universidade de São
Paulo,
‡ Caixa Postal 668, 13560-970, São Carlos - SP, Brazil<EMAIL_ADDRESS>
§ Department of Mathematics, University of Atacama, Copiapó, Chile

Received July 25, 2018, in final form January 18, 2019; Published online
January 23, 2019

Positive definite functions on spheres have received an increasing interest in
many branches of mathematics and statistics. In particular, the Schoenberg
sequences in the spectral representation of positive definite functions have
been studied by several mathematicians in the last years. This paper provides
a set of relations between Schoenberg sequences defined over real as well as
complex spheres of different dimensions. We illustrate our findings describing
an application to strict positive definiteness.

positive definite; Schoenberg pair; spheres; strictly positive definite

33C45; 42A16; 42A82; 42C10

##  1 Introduction

Positive definite functions on real and complex spheres have a long history,
that starts with the seminal paper by Schoenberg [41]. Positive definiteness
is crucial to many branches of mathematical analysis [4, 5, 9, 17, 21, 22, 23,
24, 33, 34, 36, 41] and statistics [3, 7, 10, 11, 12, 13, 14, 18, 25, 26, 27,
28, 29, 30, 31, 38, 40]. Recent reviews on positive definite functions on
either spheres or product spaces involving spheres can be found in [19] and in
[39] as well.

Fourier analysis on spheres is related to the so called Schoenberg sequences
(also called sequences of Schoenberg coefficients in [15]) that are related to
the dimension where any positive definite function on real or complex spheres
is defined. There has been a recent interest on Schoenberg sequences,
especially after the list of research problems in [19] and in [39]. Recursive
relations between Schoenberg coefficients on $d$-dimensional spheres have been
first proposed by [19]. Fiedler [16] has then solved an open problem in [19],
related to other types of recursions involving Schoenberg coefficients. Ziegel
[44] has used Schoenberg sequences to find the convolution roots of positive
definite functions on spheres and illustrated the differentiability properties
of positive definite functions on spheres through their Schoenberg sequences
in [42]. Recently, Arafat et al. [2] have solved Gneiting’s research problem
number 3 making extensive use of Schoenberg sequences. Projections from
Hilbert into finite-dimensional spheres have been considered in [38]. Finally,
Schoenberg sequences have been shown to be central to the study of geometric
properties of Gaussian fields on spheres [29] or spheres cross time [14].

Literature on complex spheres has been sparse. After the tour de force in [35]
there has been a recent interest on complex spheres as reported from [6] and
in [32].

This paper is about Schoenberg sequences on spheres of $\mathbb{R}^{d}$ and
$\mathbb{C}^{q}$, respectively. Specifically, we show recursive relations that
have been lacking from the previously mentioned literature. Section 2 deals
with real-valued $d$-dimensional spheres. Section 3 is instead related to
complex spheres. Some implications in terms of strict positive definiteness
are provided in Section 4. The paper ends with a discussion.

##  2 Schoenberg sequences on real spheres

###  2.1 Background and notation

For a positive integer $d$, let
$\mathbb{S}^{d}=\big{\\{}\mathbf{x}\in\mathbb{R}^{d+1},\,\|\mathbf{x}\|=1\big{\\}}$
denote the $d$-dimensional unit sphere embedded in $\mathbb{R}^{d+1}$, with
$\|\cdot\|$ being the Euclidean norm. We define the great-circle distance
$\theta\colon\mathbb{S}^{d}\times\mathbb{S}^{d}\to[0,\pi]$ as the continuous
mapping defined through

$\displaystyle\theta(\mathbf{x}_{1},\mathbf{x}_{2})=\arccos\big{(}\mathbf{x}_{1}^{\top}\mathbf{x}_{2}\big{)}\in[0,\pi],$

for $\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{S}^{d}$, where $\top$ is the
transpose operator. A mapping
$C\colon\mathbb{S}^{d}\times\mathbb{S}^{d}\to\mathbb{R}$ that satisfies

$\displaystyle\sum_{i,j=1}^{n}c_{i}c_{j}C(\mathbf{x}_{i},\mathbf{x}_{j})\geq
0$

for all $n\geq 1$, distinct points
$\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}$ on $\mathbb{S}^{d}$ and
real numbers $c_{1},\ldots,c_{n}$, is called positive definite. Further, if
the inequality is strict, unless the vector $(c_{1},\dots,c_{n})^{\top}$ is
the zero vector, then it is called strictly positive definite (see [8] and
references therein). If, in addition,

$\displaystyle
C(\mathbf{x}_{1},\mathbf{x}_{2})=\psi(\theta(\mathbf{x}_{1},\mathbf{x}_{2})),\qquad\mathbf{x}_{i}\in\mathbb{S}^{d},\qquad
i=1,2,$ (2.1)

for some mapping $\psi\colon[0,\pi]\rightarrow\mathbb{R}$, then $C$ is called
a geodesically isotropic covariance by [39]. With no loss of generality, we
assume through the paper that the function $\psi$ is continuous along with the
normalization $\psi(0)=1$.

Gneiting [19] calls $\Psi_{d}$ the class of continuous functions
$\psi\colon[0,\pi]\to\mathbb{R}$ with $\psi(0)=1$ such that the function $C$
in equation (2.1) is positive definite. The inclusions
$\Psi_{d}\supset\Psi_{d+1}$, $d\geq 1$, are known to be strict. Following
[41], for every continuous function $\psi\colon[0,\pi]\to\mathbb{R}$ with
$\psi(0)=1$, and every integer $d\geq 2$, define

$\displaystyle
b_{n,d}=\kappa(n,d)\int_{0}^{\pi}\psi(\theta)C_{n}^{(d-1)/2}(\cos\theta)\left(\sin\theta\right)^{d-1}{\rm
d}\theta,$ (2.2)

where, for any $\lambda>0$, $C_{n}^{\lambda}$ denotes the $n$-th Gegenbauer
polynomial of order $\lambda$ [1], and

$\displaystyle\kappa(n,d)=\frac{(2n+d-1)(\Gamma((d-1)/2)^{2}}{2^{3-d}\pi\Gamma(d-1)}.$
(2.3)

Moreover, we define

$\displaystyle b_{0,1}=\frac{1}{\pi}\int_{0}^{\pi}\psi(\theta){\rm
d}\theta,\qquad
b_{n,1}=\frac{2}{\pi}\int_{0}^{\pi}\cos(n\theta)\psi(\theta){\rm
d}\theta,\qquad n\geq 1.$ (2.4)

Note that in the cases $d=1$ (the circle) and $d=2$ (the unit sphere of
$\mathbb{R}^{3}$), Gegenbauer polynomials simplify to Chebyshev and Legendre
polynomials [1], respectively.

The coefficient sequences $\\{b_{n,d}\\}_{n=0}^{\infty}$ play a crucial role
in the spectral representations for positive definite functions on spheres,
which are the equivalent of Bochner and Schoenberg’s theorems in Euclidean
spaces (see [15] with the references therein) and are provided by [41], who
shows that a mapping $\psi\colon[0,\pi]\rightarrow\mathbb{R}$ belongs to the
class $\Psi_{d}$ if and only if it can be uniquely written as

$\displaystyle\psi(\theta)=\sum_{n=0}^{\infty}b_{n,d}c_{n}^{(d-1)/2}(\cos\theta),\qquad\theta\in[0,\pi],$
(2.5)

where $c_{n}^{\lambda}$ denotes the normalized $\lambda$-Gegenbauer polynomial
of degree $n$, namely,

$\displaystyle
c_{n}^{\lambda}(u)=\frac{C_{n}^{\lambda}(u)}{C_{n}^{\lambda}(1)},\qquad
u\in[-1,1],$

and $\\{b_{n,d}\\}_{n=0}^{\infty}$ is a probability mass sequence. The series
(2.5) is known to be uniformly convergent. We follow [15] when calling the
sequence $\\{b_{n,d}\\}_{n=0}^{\infty}$ in (2.5) the $d$-Schoenberg sequence
of coefficients, to emphasize the dependence on the index $d$ in the class
$\Psi_{d}$. Accordingly, we say that $(\psi,\\{b_{n,d}\\})$ is a uniquely
determined $d$-Schoenberg pair if $\psi$ belongs to the class $\Psi_{d}$ and
admits the expansion (2.5) with $d$-Schoenberg sequence
$\\{b_{n,d}\\}_{n=0}^{\infty}$.

The following recursive relations among the coefficients $b_{n,d}$ and
$b_{n,d+2}$ attached to a $d$-Schoenberg pair $(\psi,\\{b_{n,d+2}\\})$ (see
[19, Corollary 1])

$\displaystyle b_{0,3}=b_{0,1}-\frac{1}{2}b_{2,1},$ (2.6) $\displaystyle
b_{n,3}=\frac{1}{2}(n+1)(b_{n,1}-b_{n+2,1}),\qquad n\geq 1,$ (2.7)
$\displaystyle
b_{n,d+2}=\frac{(n+d-1)(n+d)}{d(2n+d-1)}b_{n,d}-\frac{(n+1)(n+2)}{d(2n+d+3)}b_{n+2,d},\qquad
d\geq 2,\qquad n\geq 0,$ (2.8)

have actually opened for challenging questions. Fiedler [16] has shown
relationships between sequences $\\{b_{n,2d+1}\\}_{n=0}^{\infty}$ and
$\\{b_{n,1}\\}_{n=0}^{\infty}$, on the one hand, and sequences
$\\{b_{n,2d}\\}_{n=0}^{\infty}$ and $\\{b_{n,2}\\}_{n=0}^{\infty}$, on the
other. Proposition 1 in [2] encompasses Fiedler’s result and provides a
relation between the sequences $\\{b_{n,d}\\}_{n=0}^{\infty}$, $d>1$, and
$\\{b_{n,1}\\}_{n=0}^{\infty}$. A projection operator relating Schoenberg
sequences on Hilbert spheres with $d$-Schoenberg sequences has been proposed
by [38]. Yet, there are some relations that have not been discovered and these
will be illustrated throughout.

###  2.2 Results

We start with a very simple result, that we report formally for the
convenience of the reader.

######  Proposition 2.1.

Let $d$, $d^{\prime}$ be positive integers, with $d>d^{\prime}$. If
$(\psi,\\{b_{n,d}\\})$ is a $d$-Schoenberg pair, then the
$d^{\prime}$-Schoenberg sequence of coefficients of $\psi$ is uniquely
determined as follows.

  1. $(i)$

For $d^{\prime}\geq 2$,

$\displaystyle
b_{n,d^{\prime}}=\frac{\kappa(n,d^{\prime})}{C_{n}^{(d-1)/2}(1)}\sum_{n=0}^{\infty}b_{n,d}\int_{0}^{\pi}C_{n}^{(d-1)/2}(\cos\theta)C_{n}^{(d^{\prime}-1)/2}(\cos\theta){\rm
d}\theta,$ (2.9)

with $\kappa(n,d)$ as defined in (2.3).

  2. $(ii)$

For $d^{\prime}=1$,

$\displaystyle
b_{0,1}=\frac{1}{\pi}\sum_{n=0}^{\infty}b_{n,d}\int_{0}^{\pi}c_{n}^{(d-1)/2}(\cos\theta){\rm
d}\theta,$ $\displaystyle
b_{n,1}=\frac{2}{\pi}\sum_{n=0}^{\infty}b_{n,d}\int_{0}^{\pi}c_{n}^{(d-1)/2}(\cos\theta)\cos(n\theta){\rm
d}\theta,\qquad n\geq 1.$ (2.10)

###### Proof.

The identity (2.9) is obtained substituting (2.5) into (2.2), whereas the
identities (2.10) are obtained substituting (2.5) into (2.4). In both cases,
exchanging integral and series is allowed owing to both bounded and uniform
convergence of the series (2.5). ∎

We are not aware of any closed-form expression for the integrals appearing in
(2.10) and (2.9), and therefore of the relationships between the sequences
$\\{b_{n,d}\\}_{n=0}^{\infty}$ and $\\{b_{n,d^{\prime}}\\}_{n=0}^{\infty}$
attached to a $d^{\prime}$-Schoenberg pair $(\psi,b_{n,d^{\prime}})$, apart
from the specific case where $d^{\prime}=d+2$. Indeed, [19] provides a closed-
form expression for $\\{b_{n,d+2}\\}_{n=0}^{\infty}$ as a function of
$\\{b_{n,d}\\}_{n=0}^{\infty}$ that is given by (2.6)–(2.8). Our first main
results provide an explicit expression for the inverse function

######  Theorem 2.2.

If $(\psi,\\{b_{n,3}\\})$ is a $3$-Schoenberg pair, then the $1$-Schoenberg
sequence of coefficients of $\psi$ is given by

$\displaystyle b_{0,1}=\sum_{j=0}^{\infty}\frac{1}{2j+1}b_{2j,3},$ (2.11)
$\displaystyle b_{n,1}=\sum_{j=0}^{\infty}\frac{2}{n+2j+1}b_{n+2j,3},\qquad
n\geq 1.$ (2.12)

###### Proof.

From identity (2.7), if $(\psi,\\{b_{n,3}\\})$ is a $3$-Schoenberg pair, we
have that

$\displaystyle\frac{2}{n+1}b_{n,3}=b_{n,1}-b_{n+2,1},\qquad n\geq 1.$

Hence, for every nonnegative integer $j$, and for any positive integer $n$,

$\displaystyle\frac{2}{n+2j+1}b_{n+2j,3}=b_{n+2j,1}-b_{n+2j+2,1}.$ (2.13)

Summing up both sides of (2.13) from $0$ to $m$, we obtain

$\displaystyle\sum_{j=0}^{m}\frac{2}{n+2j+1}b_{n+2j,3}=\sum_{j=0}^{m}\big{(}b_{n+2j,1}-b_{n+2j+2,1}\big{)},\qquad
m\geq 1.$ (2.14)

We now use the fact that the right-hand side in equation (2.13) is telescopic.
Hence, (2.14) can be written as

$\displaystyle\sum_{j=0}^{m}\frac{2}{n+2j+1}b_{n+2j,3}=b_{n,1}-b_{n+2m+2,1},\qquad
m\geq 1.$ (2.15)

Since $\psi$ belongs to $\Psi_{1}$, the series
$\sum\limits_{n=0}^{\infty}b_{n,1}$ converges to $1$ and, therefore, the
sequence $\\{b_{n,1}\\}_{n=0}^{\infty}$ converges to zero. We can thus take
the limit for $m\to\infty$ in equation (2.15) and this will provide (2.12). In
particular, we now take $n=2$ to deduce that
$b_{2,1}=2\sum\limits_{j=1}^{\infty}b_{2j,3}/\\{1+2j\\}$ which combined with
(2.6) yields (2.11). ∎

We are now able to provide an extension of Theorem 2.2 for $d>3$. For a
positive integer $m$ and $x>0$, $(x)^{m}$ will denote the standard rising
factorial (Pochhammer symbol).

######  Theorem 2.3.

Let $d\geq 2$ be a positive integer. If $(\psi,\\{b_{n,d+2}\\})$ is a
$(d+2)$-Schoenberg pair, then the $d$-Schoenberg sequence of coefficients
$\\{b_{n,d}\\}_{n=0}^{\infty}$ of $\psi$ is given by

$\displaystyle b_{n,d}=\sum_{j=0}^{\infty}w_{j,n,d}b_{n+2j,d+2},\qquad n\geq
1,$

where

$\displaystyle w_{0,n,d}$ $\displaystyle=\frac{d(2n+d-1)}{(n+d-1)(n+d)},$
$\displaystyle w_{j,n,d}$
$\displaystyle=d(2n+d-1)\frac{(n/2+1/2)^{(j)}(n/2+1)^{(j)}}{(n/2+(d-1)/2)^{(j+1)}(n/2+d/2)^{(j+1)}},\qquad
j\geq 1.$

###### Proof.

We give a constructive proof. Define

$\displaystyle a_{n,d}:=\frac{d(2n+d-1)}{(n+d-1)(n+d)},\qquad
u_{n,d}:=2n+d-1,\qquad v_{n,d}:=\frac{(n+1)(n+2)}{(n+d-1)(n+d)}.$

We can now rewrite equation (2.8) as

$\displaystyle
a_{n,d}b_{n,d+2}=b_{n,d}-\frac{u_{n,d}}{u_{n+2,d}}v_{n,d}b_{n+2,d},\qquad
n\geq 0.$ (2.16)

Identity (2.16) shows that for every pair of nonnegative integers $(j,n)$, it
is true that

$\displaystyle
a_{n+2j,d}b_{n+2j,d+2}=b_{n+2j,d}-\frac{u_{n+2j,d}}{u_{n+2j+2,d}}v_{n+2j,d}b_{n+2j+2,d}.$
(2.17)

Multiplying each side of (2.17) by
$(u_{n,d}/u_{n+2j,d})\prod\limits_{l=0}^{j-1}v_{n+2l,d}$ and summing up both
sides from $0$ to $m$, we obtain

$\displaystyle\sum_{j=0}^{m}\left(\prod_{l=0}^{j-1}v_{n+2l,d}\right)\frac{u_{n,d}}{u_{n+2j,d}}a_{n+2j,d}b_{n+2j,d+2}$
$\displaystyle\qquad{}=u_{n,d}\sum_{j=0}^{m}\left(\prod_{l=0}^{j-1}v_{n+2l,d}\right)\left(\frac{b_{n+2j,d}}{u_{n+2j,d}}-\frac{b_{n+2j+2,d}}{u_{n+2j+2,d}}v_{n+2j,d}\right).$

Since the sum in the right-hand side is telescopic, we are left with

$\displaystyle\sum_{j=0}^{m}\left(\prod_{l=0}^{j-1}v_{n+2l,d}\right)\frac{u_{n,d}}{u_{n+2j,d}}a_{n+2j,d}b_{n+2j,d+2}$
$\displaystyle\qquad{}=b_{n,d}-\frac{u_{n,d}}{u_{n+2m+2,d}}\left(\prod_{l=0}^{m}v_{n+2l,d}\right)b_{n+2j+2,d}.$
(2.18)

At this stage, note that

$\displaystyle
v_{n,d}-1=-(d-2)\frac{2n+d+1}{(n+d-1)(n+d)}\leq-(d-2)\frac{1}{n+d-1},\qquad
n\geq 0.$ (2.19)

We can now show that $\prod\limits_{l=0}^{\infty}v_{n+2l,d}\in\\{0,1\\}$.
Indeed, if $d=2$, then $v_{n,d}=1$ for each $n\geq 0$ and, therefore,
$\prod\limits_{l=0}^{\infty}v_{n+2l,2}=1$. If $d>2$, then by (2.19)

$\displaystyle\prod_{l=0}^{m}v_{n+2l,d}=\exp\left[\sum_{l=0}^{m}\log(v_{n+2l,d})\right]$
$\displaystyle\hphantom{\prod_{l=0}^{m}v_{n+2l,d}}{}\leq\exp\left[\sum_{l=0}^{m}(v_{n+2l,d}-1)\right]\leq\exp\left[-(d-2)\sum_{l=0}^{m}\frac{1}{n+2l+d-1}\right],$

and, therefore, $\prod\limits_{l=0}^{\infty}v_{n+2l,d}=0$. Since
$\psi\in\Psi_{d}$, the sequence $\\{b_{n,d}\\}_{n=0}^{\infty}$ converges to
zero, while

$\displaystyle\lim_{m\to\infty}\frac{u_{n,d}}{u_{n+2m+2,d}}=0,\qquad n\geq 0.$

So, letting $m\to\infty$ in (2.2) yields

$\displaystyle
b_{n,d}=\sum_{j=0}^{\infty}\left(\prod_{l=0}^{j-1}v_{n+2l,d}\right)\frac{u_{n,d}}{u_{n+2j,d}}a_{n+2j,d}b_{n+2j,d+2},\qquad
n\geq 0.$

Finally, direct computation shows that for $n\geq 0$ and $j\geq 1$,

$\displaystyle\prod_{l=0}^{j-1}v_{n+2l,d}=\frac{(n/2+1/2)^{(j)}(n/2+1)^{(j)}}{(n/2+(d-1)/2)^{(j)}(n/2+d/2)^{(j)}},$

and

$\displaystyle\frac{u_{n,d}}{u_{n+2j,d}}a_{n+2j,d}=\frac{d(2n+d-1)}{(n+2j+d-1)(n+2j+d)}.$

The proof is completed. ∎

##  3 Schoenberg sequences on complex spheres

In analogy with the results obtained in Section 2, we consider similar results
on complex spheres.

###  3.1 Background and notation

For a positive integer $q$, denote by $\Omega_{2q}$ the unit sphere in
$\mathbb{C}^{q}$. A mapping $C\colon\Omega_{2d}\times\Omega_{2q}\to\mathbb{C}$
is positive definite if

$\displaystyle\sum_{i,j=1}^{n}c_{i}\bar{c}_{j}C(\mathbf{z}_{i},\mathbf{z}_{j})\geq
0.$

for all $n\geq 1$, distinct points $\mathbf{z}_{1},\dots,\mathbf{z}_{n}$ of
$\Omega_{2q}$ and complex numbers $c_{1},\ldots,c_{n}$. Let “$\cdot$” denote
the usual inner product in $\mathbb{C}^{q}$. If $q\geq 2$ and
$B[0,1]=\\{z\in\mathbb{C}\colon z\cdot z\leq 1\\}$, the function $C$ is called
isotropic if

$\displaystyle
C(\mathbf{z}_{1},\mathbf{z}_{2})=\varphi(\mathbf{z}_{1}\cdot\mathbf{z}_{2}),\qquad\mathbf{z}_{1},\mathbf{z}_{2}\in\Omega_{2q},$
(3.1)

for some function $\varphi\colon B[0,1]\to\mathbb{C}$. This nomenclature is
not universal but it is quite adequate in our setting. Observe that in the
case $q=1$, if $z,w\in\Omega_{2}$, then $z\cdot z\in\Omega_{2}$. Hence, the
previous definition becomes an extreme case once the domain of $\varphi$ needs
to be $\Omega_{2}$ itself.

Keeping the analogy with the previous section, for $q\geq 2$, we call
$\Upsilon_{2q}$ the class of continuous functions $\varphi$, with
$\varphi(1)=1$ such that $C$ in (3.1) is positive definite. We also denote by
$\Upsilon_{2q}^{+}$ the class of functions $\varphi$ belonging to
$\Upsilon_{2q}$ such that $C$ in (3.1) is strictly positive definite. Both
classes $\Upsilon_{2q}$ and $\Upsilon_{2q}^{+}$ are nested, that is, if $q\leq
q^{\prime}$, then $\Upsilon_{2q^{\prime}}\subset\Upsilon_{2q}$ and
$\Upsilon_{2q^{\prime}}^{+}\subset\Upsilon_{2q}^{+}$.

To present the characterization of the class $\Upsilon_{2q}$ described in
[37], we denote by $R^{q-2}_{m,n}$ the disk polynomial of bi-degree $(m,n)$
with respect to the nonnegative integer $q-2$. The set $\\{R^{q-2}_{m,n}\colon
m,n=0,1,\ldots\\}$ is a complete orthogonal system in
$L^{2}(B[0,1],\nu_{q-2})$, with

$\displaystyle{\rm
d}\nu_{q-2}(z)=\frac{q-1}{\pi}\big{(}1-|z|^{2}\big{)}^{q-2}{\rm d}x{\rm
d}y,\qquad z=x+\mathsf{i}y\in B[0,1].$ (3.2)

In particular,

$\displaystyle\int_{B[0,1]}R^{q-2}_{m,n}(z)\overline{R^{q-2}_{k,l}(z)}{\rm
d}\nu_{q-2}(z)=\frac{\delta_{mk}\delta_{nl}}{h^{q-2}_{m,n}},$ (3.3)

where

$\displaystyle
h^{q-2}_{m,n}=\frac{m+n+q-1}{q-1}\binom{m+q-2}{q-2}\binom{n+q-2}{q-2}.$ (3.4)

Expressions and main properties of disk polynomials can be found in [43] and
in references quoted there. We recall the following recursion satisfied for
every $z$ in $B[0,1]$, $m\geq 1$ and $n\geq 0$ [35]:

$\displaystyle\big{(}1-|z|^{2}\big{)}R^{q-1}_{m-1,n}(z)=\frac{q-1}{m+n+q-1}\big{[}R^{q-2}_{m-1,n}(z)-R^{q-2}_{m,n+1}(z)\big{]}.$
(3.5)

For every continuous function $\varphi\colon B[0,1]\to\mathbb{C}$ and every
triplet $(m,n,q)$ of nonnegative integers, we can define

$\displaystyle
a^{q-2}_{m,n}:=h^{q-2}_{m,n}\int_{B[0,1]}\varphi(z)\overline{R^{q-2}_{m,n}(z)}{\rm
d}\nu_{q-2}(z).$ (3.6)

The functions belonging to the class $\Upsilon_{2q}$ are uniquely
characterized through the expansion [37]

$\displaystyle\varphi(z)=\sum_{m,n=0}^{\infty}a^{q-2}_{m,n}R^{q-2}_{m,n}(z),\qquad
z\in B[0,1],$ (3.7)

where $a^{q-2}_{m,n}\geq 0$, $m,n\in\mathbb{Z}_{+}$ and
$\sum\limits_{m,n=0}^{\infty}a^{q-2}_{m,n}=1$. Following Section 2, we finally
define a $2q$-Schoenberg pair
$\big{(}\varphi,\big{\\{}a_{m,n}^{q-2}\big{\\}}\big{)}$ any function belonging
to the class $\Upsilon_{2q}$ with expansion defined according to (3.7). In
this case, the double sequence
$\big{\\{}a_{m,n}^{q-2}\big{\\}}_{m,n=0}^{\infty}$ will be called the
$2q$-Schoenberg sequence of coefficients of $\varphi$.

###  3.2 Results

Since the classes $\Upsilon_{2q}$ are nested, here we prove a recursive
relation among the coefficients $a_{m,n}^{q-1}$ and $a_{m,n}^{q-2}$ attached
to a $2(q+1)$ Schoenberg pair
$\big{(}\varphi,\big{\\{}a_{m,n}^{q-1}\big{\\}}\big{)}$ that resembles (2.8).

######  Proposition 3.1.

If $\big{(}\varphi,\big{\\{}a_{m,n}^{q-1}\big{\\}}\big{)}$ is a
$2(q+1)$-Schoenberg pair, then for $m-1,n\geq 0$,

$\displaystyle
a^{q-1}_{m-1,n}=\frac{(m+q-2)(n+q-1)}{(q-1)(m+n+q-2)}a^{q-2}_{m-1,n}-\frac{m(n+1)}{(q-1)(m+n+q)}a^{q-2}_{m,n+1}.$
(3.8)

###### Proof.

Equation (3.4) shows that

$\displaystyle
h^{q-2}_{m-1,n}=\frac{(m+n+q-2)m(n+1)}{(m+n+q)(m+q-2)(n+q-1)}h^{q-2}_{m,n+1},\qquad
m-1,n\geq 0,$ (3.9) $\displaystyle
h^{q-2}_{m-1,n}=\frac{(m+n+q-2)q(q-1)^{2}}{(m+n+q-1)q(m+q-2)(n+q-1)}h^{q-1}_{m-1,n},\qquad
m-1,n\geq 0.$ (3.10)

We now multiply both sides of (3.5) by $h^{q-2}_{m-1,n}\varphi(z)$ and
integrate with respect to the measure $\nu_{\alpha}$ defined in (3.3). After
we use (3.6) and (3.9), we obtain

$\displaystyle
h^{q-2}_{m-1,n}\int_{B[0,1]}\big{(}1-|z|^{2}\big{)}R^{q-1}_{m-1,n}(z)f\varphi(z){\rm
d}\nu_{q-2}(z)$
$\displaystyle\qquad{}=\frac{q-1}{m+n+q-1}\left[a^{q-2}_{m-1,n}-\frac{(m+n+q-2)m(n+1)}{(m+n+q)(m+q-2)(n+q-1)}a^{q-2}_{m,n+1}\right].$
(3.11)

However, equation (3.2) yields the equality

$\displaystyle\big{(}1-|z|^{2}\big{)}d\nu_{q-2}=\frac{q-1}{q}d\nu_{q-1}.$

Therefore, by (3.10) and (3.6), the left-hand side of (3.11) is equal to

$\displaystyle\frac{(m+n+q-2)(q-1)^{2}}{(m+n+q-1)(m+q-2)(n+q-1)}a^{q-1}_{m-1,n},$

so that (3.11) becomes

$\displaystyle\frac{(m+n+q-2)(q-1)}{(m+q-2)(n+q-1)}a^{q-1}_{m-1,n}=a^{q-2}_{m-1,n}-\frac{(m+n+q-2)m(n+1)}{(m+n+q)(m+q-2)(n+q-1)}a^{q-2}_{m,n+1}.$

This yields (3.8). ∎

Here is the main result of the section.

######  Theorem 3.2.

If $\big{(}\varphi,\big{\\{}a_{m,n}^{q-1}\big{\\}}\big{)}$ is a
$2(q+1)$-Schoenberg pair, then the $2q$-Schoenberg sequence of coefficients
$\big{\\{}a^{q-2}_{m,n}\big{\\}}_{m,n=0}^{\infty}$ of $\varphi$ is given by

$\displaystyle
a^{q-2}_{m,n}=\sum_{j=0}^{\infty}v^{q-2}_{j,m+1,n}a^{q-1}_{m+j,n+j},\qquad
m,n\geq 0,$

where

$\displaystyle
v^{q-2}_{j,m,n}:=\frac{m^{(j)}(n+1)^{(j)}(m+n+q-2)}{(m+q-2)^{(j)}(n+q-1)^{(j)}(m+n+2j+q-2)},\qquad
j\geq 0.$

###### Proof.

First of all we introduce the following notations:

$\displaystyle u^{q-2}_{m,n}:=\frac{(q-1)(m+n+q-2)}{(m+q-2)(n+q-1)},\qquad
m,n\geq 0,$ $\displaystyle
w^{q-2}_{m,n}:=\frac{(m+n+q-2)m(n+1)}{(m+q-2)(n+q-1)(m+n+q)},\qquad m,n\geq
0.$ (3.12)

In this way, (3.8) becomes

$\displaystyle
u^{q-2}_{m,n}a^{q-1}_{m-1,n}=a^{q-2}_{m-1,n}-w^{q-2}_{m,n}a^{q-2}_{m,n+1},\qquad
m-1,n\geq 0.$ (3.13)

By (3.13), we have that for every triplet $(j,m,n)$ of nonnegative integers,

$\displaystyle
u^{q-2}_{m+j,n+j}a^{q-1}_{m+j-1,n+j}=a^{q-2}_{m+j-1,n+j}-w^{q-2}_{m+j,n+j}a^{q-2}_{m+j,n+j+1}.$
(3.14)

Now, we can multiply each side of (3.14) by the product
$\prod\limits_{l=1}^{j}w^{q-2}_{m+l-1,n+l-1}$ and sum up each side from $0$ to
$k$, obtaining that

$\displaystyle\begin{split}&\sum_{j=0}^{k}\left(\prod_{l=1}^{j}w^{q-2}_{m+l-1,n+l-1}\right)u^{q-2}_{m+j,n+j}a^{q-1}_{m+j-1,n+j}\\\
&\qquad{}=\sum_{j=0}^{k}\left(\prod_{l=1}^{j}w^{q-2}_{m+l-1,n+l-1}\right)\left(a^{q-2}_{m+j-1,n+j}-w^{q-2}_{m+j,n+j}a^{q-2}_{m+j,n+j+1}\right).\end{split}$

Since the sum in the right-hand side is telescopic, we are reduced to

$\displaystyle\sum_{j=0}^{k}\left(\prod_{l=1}^{j}w^{q-2}_{m+l-1,n+l-1}\right)u^{q-2}_{m+j,n+j}a^{q-1}_{m+j-1,n+j}$
$\displaystyle\qquad{}=a^{q-2}_{m-1,n}-\left(\prod_{j=0}^{k}w^{q-2}_{m+j,n+j}\right)a^{q-2}_{m+k,n+k+1}.$
(3.15)

Since

$\displaystyle\prod_{j=0}^{k}w^{q-2}_{m+j,n+j}$
$\displaystyle\qquad{}\leq\exp\left[-\sum_{j=0}^{k}\left(\frac{q-2}{m+j+q-2}+\frac{q-2}{n+j+q-1}+\frac{2}{m+n+2j+q}\right)\right],\qquad
k\geq 0,$

we end up with

$\displaystyle\prod_{j=0}^{\infty}w^{q-2}_{m+j,n+j}=0.$

Moreover, since

$\displaystyle\sum_{k=0}^{\infty}a^{q-2}_{l+k,j+k+1}\leq\sum_{m,n=0}^{\infty}a^{q-2}_{m,n}<\infty,\qquad
j,l\geq 0,$

we have that $\lim\limits_{k\to\infty}a^{q-2}_{l+k,j+k+1}=0$, for $j,l\geq 0$.
Therefore, letting $k\to\infty$, (3.15) leads to

$\displaystyle
a^{q-2}_{m-1,n}=\sum_{j=0}^{\infty}\left(\prod_{l=1}^{j}w^{q-2}_{m+l-1,n+l-1}\right)u^{q-2}_{m+j,n+j}a^{q-1}_{m+j-1,n+j},\qquad
m-1,n\geq 0,$

which in turn by (3.12) yields the desired result. ∎

##  4 Applications involving the classes $\boldsymbol{\Psi_{d}^{+}}$ and
$\boldsymbol{\Upsilon_{2q}^{+}}$

In this section, we present applications of the previous results involving the
classes $\Psi_{d}^{+}$ and $\Upsilon_{2q}^{+}$.

######  Theorem 4.1.

Let $q,q^{\prime}\geq 2$ be integers. The following assertions hold:

  1. $(i)$

If a function $\varphi$ belongs to
$\Upsilon_{2q}^{+}\cap\Upsilon_{2q^{\prime}}$, then $\varphi$ belongs to
$\Upsilon_{2q^{\prime}}^{+}$.

  2. $(ii)$

If a function $\varphi$ belongs to
$(\Upsilon_{2q}\setminus\Upsilon_{2q}^{+})\cap\Upsilon_{2q^{\prime}}$, then
$\varphi$ belongs to
$\Upsilon_{2q^{\prime}}\setminus\Upsilon_{2q^{\prime}}^{+}$.

###### Proof.

$(i)$ If $q\geq q^{\prime}$, the assertion follows from the inclusion
$\Upsilon_{2q}^{+}\subset\Upsilon_{2q^{\prime}}^{+}$. So, we may assume that
$q<q^{\prime}$. If $\varphi\in\Upsilon_{2q}^{+}$, Theorem 1.1 in [20] reveals
that the $2q$-Schoenberg sequence of coefficients
$\big{\\{}a_{m,n}^{q-2}\big{\\}}_{m,n=0}^{\infty}$ of $\varphi$ has the
following property: $\big{\\{}m-n\colon a_{m,n}^{q-2}>0\big{\\}}$ intersects
every arithmetic progression of $\mathbb{Z}$. Taking into account that
$\varphi\in\Upsilon_{2(q+1)}$ and the fact that $v^{q^{\prime}-2}_{j,m+1,n}>0$
for all $j$, Theorem 3.2 shows that $a_{m,n}^{q-2}>0$ if and only if
$a_{m+j,n+j}^{q-1}>0$, for at least one $j\geq 0$. In particular, the set
$\big{\\{}m-n\colon a_{m,n}^{q-1}>0\big{\\}}$ intersects every arithmetic
progression of $\mathbb{Z}$ as well. In other words,
$\varphi\in\Upsilon_{2(q+1)}^{+}$, due to Theorem 1.1 in [20] once again. If
$q+1=q^{\prime}$, $\varphi\in\Upsilon_{2q^{\prime}}^{+}$ and we are done.
Otherwise, we iterate this procedure until we reach the desired conclusion.

$(ii)$ Assume
$\varphi\in(\Upsilon_{2q}\setminus\Upsilon_{2q}^{+})\cap\Upsilon_{2q^{\prime}}$.
If $\varphi\in\Upsilon_{2q^{\prime}}^{+}$, then
$\varphi\in\Upsilon_{2q^{\prime}}^{+}\cap\Upsilon_{2q}$ and $(i)$ would imply
that $\varphi\in\Upsilon_{2q}^{+}$, a contradiction. ∎

A similar result holds for real spheres with a similar proof. In particular,
if $\psi$ belongs to $\Psi_{d}\cap\Psi_{d^{\prime}}^{+}$, then $\psi$ belongs
to $\Psi_{d}^{+}$. However, this result was proved earlier in [19, Corollary
1] via a slightly different argument.

Theorem 4.1 allows the following obvious consequences. If $\varphi$ is a
function in $\Upsilon_{2q}$, we write $\varphi_{r}$ to indicate the
restriction of $\varphi$ to $[-1,1]$.

######  Corollary 4.2.

For $d\geq 1$ and $q\geq 2$, the following assertions hold:

  1. $(i)$

If a function $\varphi$ belongs to $\Upsilon_{2q}$ and $\varphi_{r}\circ\cos$
belongs to $\Psi_{d}^{+}$, then $\varphi_{r}\circ\cos$ belongs to
$\Psi_{2q-1}^{+}$.

  2. $(ii)$

If a function $\varphi$ belongs to $\Upsilon_{2q}^{+}$ and
$\varphi_{r}\circ\cos$ belongs to $\Psi_{d}$, then $\varphi_{r}\circ\cos$
belongs to $\Psi_{d}^{+}$.

###### Proof.

It suffices to observe that if $\varphi\in\Upsilon_{2q}$ (respectively,
$\Upsilon_{2q}^{+}$), then $f_{r}\circ\cos\in\Psi_{2q-1}$ (respectively,
$\Psi_{2q-1}^{+}$) and to apply the remark in the paragraph preceding the
theorem. ∎

##  5 Discussion

This paper contributes to the literature about the classes $\Psi_{d}$,
$\Upsilon_{2q}$ and $\Upsilon_{2q}^{+}$ in terms of their Schoenberg
sequences. Yet, there are many challenges that involve Schoenberg sequences,
for instance in product spaces. Berg and Porcu [7] consider the analogue of
Schoenberg pairs introduced in this paper, but on the product space
$\mathbb{S}^{d}\times G$, for $G$ a locally compact group. Generalizations of
the results in [7] have been provided by [22]. It would be very interesting to
inspect whether the results provided in this paper can be generalized to these
cases. Another important challenge would be to inspect the Schoenberg pairs
related to matrix-valued kernels (see open problem 2 in [39]).

### Acknowledgements

The authors are grateful to the Associate Editor and to the referees for their
comments that allowed for an improved version of the manuscript. Research of
Valdir A. Menegatto was partially supported by FAPESP, grant 2016/09906-0.
Emilio Porcu is partially supported by grant FONDECYT 1130647 from Chilean
Ministry of Education, and by Millennium Science Initiative of the Ministry of
Economy, Development, and Tourism, grant “Millenium Nucleus Center for the
Discovery of Structures in Complex Data”.

## References

  * [1] Abramowitz M., Stegun I.A., Handbook of mathematical functions, with formulas, graphs, and mathematical tables, Dover Publications, Inc., New York, 1966.
  * [2] Arafat A., Gregori P., Porcu E., Schoenberg coefficients and curvature at the origin of continuous isotropic positive definite kernels on spheres, arXiv:1807.02363.
  * [3] Baldi P., Marinucci D., Some characterizations of the spherical harmonics coefficients for isotropic random fields, Statist. Probab. Lett. 77 (2007), 490–496, math.PR/0606709.
  * [4] Barbosa V.S., Menegatto V.A., Strict positive definiteness on products of compact two-point homogeneous spaces, Integral Transforms Spec. Funct. 28 (2017), 56–73, arXiv:1605.07071.
  * [5] Beatson R.K., zu Castell W., Xu Y., A Pólya criterion for (strict) positive-definiteness on the sphere, IMA J. Numer. Anal. 34 (2014), 550–568, arXiv:1110.2437.
  * [6] Berg C., Peron A.P., Porcu E., Schoenberg’s theorem for real and complex Hilbert spheres revisited, J. Approx. Theory 228 (2018), 58–78, arXiv:1701.07214.
  * [7] Berg C., Porcu E., From Schoenberg coefficients to Schoenberg functions, Constr. Approx. 45 (2017), 217–241, arXiv:1505.05682.
  * [8] Bingham N.H., Positive definite functions on spheres, Proc. Cambridge Philos. Soc. 73 (1973), 145–156.
  * [9] Chen D., Menegatto V.A., Sun X., A necessary and sufficient condition for strictly positive definite functions on spheres, Proc. Amer. Math. Soc. 131 (2003), 2733–2740.
  * [10] Christakos G., On certain classes of spatiotemporal random fields with applications to space-time data processing, IEEE Trans. Systems Man Cybernet. 21 (1991), 861–875.
  * [11] Christakos G., Modern spatiotemporal geostatistics, Oxford University Press, Inc., New York, 2000.
  * [12] Christakos G., Hristopulos D.T., Bogaert P., On the physical geometry hypotheses at the basis of spatiotemporal analysis of hydrologic geostatistics, Adv. Water Resources 23 (2000), 799–810.
  * [13] Christakos G., Papanicolaou V., Norm-dependent covariance permissibility of weakly homogeneous spatial random fields, Stoch. Environ. Res. Risk Assess. 14 (2000), 471–478.
  * [14] Clarke De la Cerda J., Alegría A., Porcu E., Regularity properties and simulations of Gaussian random fields on the sphere cross time, Electron. J. Stat. 12 (2018), 399–426, arXiv:1611.02851.
  * [15] Daley D.J., Porcu E., Dimension walks and Schoenberg spectral measures, Proc. Amer. Math. Soc. 142 (2014), 1813–1824.
  * [16] Fiedler J., From Fourier to Gegenbauer: dimension walks on spheres, arXiv:1303.6856.
  * [17] Gangolli R., Positive definite kernels on homogeneous spaces and certain stochastic processes related to Lévy’s Brownian motion of several parameters, Ann. Inst. H. Poincaré Sect. B (N.S.) 3 (1967), 121–226.
  * [18] Gerber F., Mösinger L., Furrer R., Extending R packages to support 64-bit compiled code: an illustration with spam64 and GIMMS NDVI3g data, Comput. Geosci. 104 (2017), 109–119.
  * [19] Gneiting T., Strictly and non-strictly positive definite functions on spheres, Bernoulli 19 (2013), 1327–1349, arXiv:1111.7077.
  * [20] Guella J.C., Menegatto V.A., Unitarily invariant strictly positive definite kernels on spheres, Positivity 22 (2018), 91–103.
  * [21] Guella J.C., Menegatto V.A., Peron A.P., An extension of a theorem of Schoenberg to products of spheres, Banach J. Math. Anal. 10 (2016), 671–685, arXiv:1503.08174.
  * [22] Guella J.C., Menegatto V.A., Peron A.P., Strictly positive definite kernels on a product of circles, Positivity 21 (2017), 329–342, arXiv:1505.01169.
  * [23] Guella J.C., Menegatto V.A., Peron A.P., Strictly positive definite kernels on a product of spheres II, SIGMA 12 (2016), 103, 15 pages, arXiv:1605.09775.
  * [24] Hannan E.J., Multiple time series, John Wiley and Sons, Inc., New York – London – Sydney, 1970.
  * [25] Hansen L.V., Thorarinsdottir T.L., Ovcharov E., Gneiting T., Richards D., Gaussian random particles with flexible Hausdorff dimension, Adv. in Appl. Probab. 47 (2015), 307–327, arXiv:1502.01750.
  * [26] Hitczenko M., Stein M.L., Some theory for anisotropic processes on the sphere, Stat. Methodol. 9 (2012), 211–227.
  * [27] Huang C., Zhang H., Robeson S.M., A simplified representation of the covariance structure of axially symmetric processes on the sphere, Statist. Probab. Lett. 82 (2012), 1346–1351.
  * [28] Istas J., Spherical and hyperbolic fractional Brownian motion, Electron. Comm. Probab. 10 (2005), 254–262.
  * [29] Lang A., Schwab C., Isotropic Gaussian random fields on the sphere: regularity, fast simulation and stochastic partial differential equations, Ann. Appl. Probab. 25 (2015), 3047–3094, arXiv:1305.1170.
  * [30] Leonenko N., Sakhno L., On spectral representations of tensor random fields on the sphere, Stoch. Anal. Appl. 30 (2012), 44–66, arXiv:0912.3389.
  * [31] Malyarenko A., Invariant random fields on spaces with a group action, Probability and its Applications (New York), Springer, Heidelberg, 2013.
  * [32] Massa E., Peron A.P., Porcu E., Positive definite functions on complex spheres and their walks through dimensions, SIGMA 13 (2017), 088, 16 pages, arXiv:1704.01237.
  * [33] Menegatto V.A., Strictly positive definite kernels on the Hilbert sphere, Appl. Anal. 55 (1994), 91–101.
  * [34] Menegatto V.A., Strictly positive definite kernels on the circle, Rocky Mountain J. Math. 25 (1995), 1149–1163.
  * [35] Menegatto V.A., Differentiability of bizonal positive definite kernels on complex spheres, J. Math. Anal. Appl. 412 (2014), 189–199.
  * [36] Menegatto V.A., Oliveira C.P., Peron A.P., Strictly positive definite kernels on subsets of the complex plane, Comput. Math. Appl. 51 (2006), 1233–1250.
  * [37] Menegatto V.A., Peron A.P., Positive definite kernels on complex spheres, J. Math. Anal. Appl. 254 (2001), 219–232.
  * [38] Møller J., Nielsen M., Porcu E., Rubak E., Determinantal point process models on the sphere, Bernoulli 24 (2018), 1171–1201, arXiv:1607.03675.
  * [39] Porcu E., Alegria A., Furrer R., Modelling temporally evolving and spatially globally dependent data, Int. Stat. Rev. 86 (2018), 344–377, arXiv:1706.09233.
  * [40] Porcu E., Bevilacqua M., Genton M.G., Spatio-temporal covariance and cross-covariance functions of the great circle distance on a sphere, J. Amer. Statist. Assoc. 111 (2016), 888–898.
  * [41] Schoenberg I.J., Positive definite functions on spheres, Duke Math. J. 9 (1942), 96–108.
  * [42] Trübner M., Ziegel J.F., Derivatives of isotropic positive definite functions on spheres, Proc. Amer. Math. Soc. 145 (2017), 3017–3031, arXiv:1603.06727.
  * [43] Wünsche A., Generalized Zernike or disc polynomials, J. Comput. Appl. Math. 174 (2005), 135–163.
  * [44] Ziegel J., Convolution roots and differentiability of isotropic positive definite functions on spheres, Proc. Amer. Math. Soc. 142 (2014), 2063–2077, arXiv:1201.5833.


# Data Engineering for Scaling Language Models to 128K Context

###### Abstract

We study the continual pretraining recipe for scaling language models’ context
lengths to 128K, with a focus on data engineering. We hypothesize that long
context modeling, in particular the ability to utilize information at
arbitrary input locations, is a capability that is mostly already acquired
through large-scale pretraining, and that this capability can be readily
extended to contexts substantially longer than seen during training (e.g., 4K
to 128K) through lightweight continual pretraining on appropriate data
mixture. We investigate the quantity and quality of the data for continual
pretraining: (1) for quantity, we show that 500 million to 5 billion tokens
are enough to enable the model to retrieve information anywhere within the
128K context; (2) for quality, our results equally emphasize domain balance
and length upsampling. Concretely, we find that naïvely upsampling longer data
on certain domains like books, a common practice of existing work, gives
suboptimal performance, and that a balanced domain mixture is important. We
demonstrate that continual pretraining of the full model on 1B-5B tokens of
such data is an effective and affordable strategy for scaling the context
length of language models to 128K. Our recipe outperforms strong open-source
long-context models and closes the gap to frontier models like GPT-4 128K.

Machine Learning, ICML

Yao Fu${}^{\text{\textkappa}}$ Rameswar Panda${}^{\text{\texteta}}$ Xinyao
Niu${}^{\text{\textmu}}$ Xiang Yue${}^{\text{\textpi}}$ Hannaneh
Hajishirzi${}^{\text{\textsigma}}$ Yoon Kim${}^{\text{\textlambda}}$ Hao
Peng${}^{\text{\textdelta}}$
${}^{\text{\textkappa}}$University of Edinburgh ${}^{\text{\texteta}}$MIT-IBM
Watson AI Lab ${}^{\text{\textmu}}$University of Melbourne
${}^{\text{\textpi}}$ Ohio State University

${}^{\text{\textsigma}}$University of Washington ${}^{\text{\textlambda}}$MIT
${}^{\text{\textdelta}}$UIUC

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
https://github.com/FranxYao/Long-Context-Data-Engineering

##  1 Introduction

Figure 1:  Needle-in-a-Haystack test (Kamradt, 2023) performance comparison.
The x-axis denotes the length of the document (the “haystack”); the y-axis
indicates the position that the “needle” (a short sentence) is located within
the document, from 1K to 128K tokens. For example, 50% indicates that the
needle is placed in the middle of the document. A red cell means the the
language model cannot recite the information in the needle, and a green cell
means the model can. A white dashed line means models’ continual pretraining
(or finetuning for instruction-tuned models) context length; thus the area to
its right indicates length generalization. Most existing open-source models
make mistakes when the document is long. Our post-training recipe demonstrates
strong performance up to about 100K length.

A context window of 128K tokens enables large language models to perform tasks
that significantly beyond existing paradigm, such as multi-document question
answering (Caciularu et al., 2023), repository-level code understanding (Bairi
et al., 2023), long-history dialog modeling (Mazumder & Liu, 2024), and
language model-powered autonomous agents (Weng, 2023). A popular testbed for
whether models can actually utilize long context length is the recent Needle-
in-a-Haystack test (Kamradt, 2023), which asks the model to precisely recite
the information in a given sentence where the sentence (the “needle”) is
placed in an arbitrary location of a 128K long document (the “haystack”). In
the open-source space, although works like LongLoRA (Chen et al., 2023b) and
YaRN-Mistral (Peng et al., 2023) theoretically support 100K context, they are
not able to pass this test at such context lengths, as shown in Fig. 1.
Currently, only closed-source frontier models like GPT-4 128K have
demonstrated strong performance on the Needle-in-a-Haystack test.

This work investigates data engineering methods for scaling language models’
context lengths. Our objective is to continue pretraining the language model
on appropriate data mixtures such that it can pass the Needle-in-a-Haystack
test at 128K length. Given that most existing models are trained on less than
4K context length (Touvron et al., 2023a) and that attention has quadratic
complexity, continual pretraining with full attention on much longer context
lengths (we train on 64K-80K context lengths) may seem prohibitively costly at
a first glance. However, we show that this is feasible under academic-level
resources (see Table 2). We use LLaMA-2 7B and 13B as our base models. We do
not make any significant change to model architecture other than adjusting the
base of RoPE, as in Xiong et al. (2023). Our major focus is the data recipe:
what and how much data is able to well-adapt a model to pass the Needle-in-a-
Haystack test at 128K context length.

We hypothesize that the capability to utilize information at arbitrary
locations within long context length is (mostly) already acquired during
pretraining, even for models pretrained on substantially shorter 4K contexts.
This hypothesis is in contrast to existing works like Xiong et al. (2023);
XVerse (2024), which perform continual pretraining on a large amount of data
(400B tokens) to inject long-context-modeling capabilities; in this strategy,
the cost can be as high as pre-training from scratch. In this work we show
that continual pretraining on a small amount of long-context data, in our
case, 1-5B tokens, can “unlock” a 7B model’s capability of precise retrieval
over much longer context lengths than seen in original pretraining.

We further show that upsampling long sequences while retaining the domain
mixture of the pretraining corpora is crucial for context scaling, yet
overlooked by existing works (Table 1). Most existing works are based on the
following intuition: to model long-range dependencies one needs long sequence
data, which domains like books provide; therefore, it is necessary to upsample
domains containing long sequences in the data mixture, as done by LongChat 32K
(Li et al., 2023a) and YaRN Mistral 128K (Peng et al., 2023). However, we show
that this intuitive solution is suboptimal because, as we observe, this
results in perplexiy degradations in other domains (Table 5). Instead, a data
mixture that keeps the domain mixture ratio the same as the pretraining
mixture, and then upsampling long sequences within each domain gives the most
stable performance gain. We give evidence that this is the primary reason our
solution improves long context tasks while maintaining short context
performance, compared with strong baselines like YaRN-Mistral 128K (Peng et
al., 2023) and LongLoRA 100K (Chen et al., 2023b).

In summary, we propose a concrete data recipe for scaling language model
context length to 128K, specifically, which involves continual pretrain the
full-attention model on 1-5B tokens of per-source-length upsampled data. We
show that our recipe results in 7B and 13B LLaMA-2 of strong long-context
performance, substantially closing the gap to frontier models like GPT-4 128K
on the Needle-in-a-Haystack test, opening future possibilities of studying
long-context modeling under academic budgets.

##  2 Background

Table 1:  Major differences between our method v.s. existing work from a data perspective, which we view as critical for extending context length. Our data mixture differs from previous work in three ways: (1) length of continual pretraining data: we use 80K compared to Together’s 32K, which does not generalizes beyond 32K; (2) data mixture: we use SlimPajama which has balanced domains compared to YaRN, which uses book-only PG19; (3) length upsampling: we upsample long sequences compared to LongLoRA, which does not. Despite the subtlety of these details (e.g., many of these details are just mentioned as a single line in previous works), we find that these details are crucial for performance on long-range retrieval.  | Existing data solution | Our solution
---|---|---
Together LLaMA-2 32K | Train on 32K length | Train on 80K length
LongChat v1.5 32K | Train on 32K length dialog data | Train on 80K length-upsampled SlimPajama
YaRN Mistral 7B 128K | Train on PG19 book-only | Trained on length-upsampled SlimPajama
LongLoRA 100K | Train on Redpajama no length upsampling | With length upsampling

Frontier language models feature extremely long context lengths, such as
OpenAI’s GPT-4 Turbo 128K (Nov 2023) and Anthropic’s Claude-100K (May 2023).
In the regime of 100K, a wide array of new applications emerge, such as repo-
level code understanding (Bairi et al., 2023), long-history dialog modeling
(Mazumder & Liu, 2024), and language model-powered autonomous agents (Weng,
2023). A recent testbed for long-range capabilities is the Needle-in-a-
Haystack benchmark, first proposed by Kamradt (2023) in Nov 2023. This
benchmark asks the language model to recite the information in a “needle”
sentence (“The best thing to do in San Francisco is eat a sandwich and sit in
Dolores Park on a sunny day”) that is randomly inserted at an arbitrary
location in a long essay. Since its release, it has become a popular sandbox
for testing whether models can utilize 100K+ context lengths, as it
differentiates models that can precisely recite the given information at
arbitrary input location versus those models that cannot. So far there is
neither public knowledge nor open-source work about achieving precise
retrieval anywhere at this scale to the best of our knowledge.

This work improves the long-context capability over strong open-source
baselines, and closes the gap to GPT-4 on the Needle-in-a-Haystack benchmark,
as demonstrated in Fig. 1. Our baselines here include LMSys’ LongChat v1.5 32K
(Li et al., 2023a), Together Compute’s LLaMA-2 32K (Together, 2023), YaRN
Mistral 128K (Peng et al., 2023), and LongLoRA (Chen et al., 2023b), which are
so far the top open-source long-context language models. These works focus on
different aspects of long-context language modeling. For example, YaRN (Peng
et al., 2023) focuses on positional embeddings, LongLoRA (Chen et al., 2023b)
focuses on efficient attention, and Together (Together, 2023) focuses on a
full-stack solution. Our work focuses on data-engineering, and identifies
critical data aspects for extending language models’ long-term dependency
modeling to much longer contexts than seen during regular pretraining.

The major differences between this work and existing work are listed on Table
1. Together’s LLaMA-2 is trained on 32K, but only generalizes to about 40K
length. YaRN Mistral is trained on book-only data; later in Table 5 we will
show that improvements on one domain has limited transfer to other domains,
indicating that one should consider a balanced mixture of different domains.
LongLoRA does not upsample long sequences; later in Fig. 4 we will show that
upsampling long sequences is critical for precise retrieval. These details are
relatively hard to notice, yet we believe that they are the important for
improved performance. Before the Needle-in-a-Haystack test, most existing
works use test negative log-likelihood as evaluation, effectively concealing
the underlying differences beyond low loss. We show that, similar test loss
could result in substantially different behavior when performing precise
retrieval (Fig. 4).

Another important related work is the previous LLaMA Long (Xiong et al., 2023)
work and the concurrent XVERSE (XVerse, 2024) work, which continue pretraining
the model on 32K sequences for about 500 billion tokens. These works are
implicitly motivated by the view that long-context modeling is a new
capability that must be “injected” through large-scale training. We instead
hypothesize that the base model has mostly already acquired this capability
through large-scale pretraining, and thus a lightweight continual pretraining
on relatively small data (e.g., 5B tokens) is enough to extend these
capabilities to much longer context lengths (Fig. 3).

##  3 Long Context Data Composition

Figure 2:  Length and domain distributions of the various data mixture
strategies. We use SlimPajama (Soboleva et al., 2023), an open-source
reproduction of LLaMA (Touvron et al., 2023a) pretraining data mixture, as the
source dataset. The original data mixture has about 30% of documents that are
naturally longer than 4K. Cutting documents at 4K, the common practice of
pretraining like Touvron et al. (2023a), breaks such long-range dependencies.
Cutting documents at 128K retains the naturally-existing long-range
dependencies. Global upsampling longer sequences slightly changes the data
mixture. Per-source upsampling longer sequences increases the portion of long
sequences while keeping the domain mixture the same. Upsampling Arxiv / Book /
Github data simultaneously changes domain and length distributions.

We use the SlimPajama (Soboleva et al., 2023) dataset for continual
pretraining. This dataset is an open-source reproduction of the LLaMA (Touvron
et al., 2023a) pretraining data mixture, consisting of 82% web data (67% from
CommonCrawl and 15% from C4), 4.5% code (Github), 4.5% Wikipedia, 4.5% books,
2.5% Arxiv, and 2.0% StackExchange. Since this dataset closely mirrors that
used to pretrain the LLaMA models, there is less concern of distribution shift
during continual pretraining; it is therefore used by many recent works like
Fuzhao Xue & You (2023).

The documents’ lengths and their source domains are two closely related
confounding factors in data engineering because long data usually come from
particular sources. Our examination shows books and Github code are the
longest sources, followed by Arxiv. Webpages like C4 and StackExchange tend to
be shorter. Directly upsampling long data changes the domain mixture, e.g.,
upsampling sequences longer than 100K will increase the portion of the books
domain. Likewise, changes in the domain mixture will result in shifts of the
length distribution. Our guideline is to decompose these two factors step by
step, as is shown in Fig. 2. We consider the following methods:

Cut at 4K: This truncates documents into 4K-length chunks. This approach
inherits the original data mixture and is used by most pretraining works, such
as (Touvron et al., 2023a; Hoffmann et al., 2022). Since there are about 30%
documents that are naturally longer than 4K, this approach breaks such
naturally-existing long-range dependencies.

Cut at 128K: This preserves most of the naturally-existing long-range
dependencies without changing the domain mixture. LongLoRA (Chen et al.,
2023b) follows this approach. However, we will show later that only using the
naturally-existing long dependencies is inadequate (Fig. 4).

Per-source Upsampling: This retains the domain mixture, then upsamples long
documents within each domain. This approach upsamples long documents without
changing the domain mixture. We recommend this approach as our experiments
suggest that this gives the most balanced performance gain.

Global Upsampling:  This upsamples long documents while ignoring their source
domains, and consequently slightly changes the domain mixture. Together (2023)
uses this approach.

Upsample Arxiv/ Book/ Github: This intentionally upsamples Arxiv/Book/Github
data, assuming that these domains are more likely to contain naturally-
occurring long documents. For example, YaRN Mistral (Peng et al., 2023) and
MPT-storyteller (Team, 2023) upsamples books. This approach changes both the
domain and length distributions.

The above approaches generally cover most data recipes used in prior works
discussed in section 2. In our experiments, we will show that: (1) using the
original mixture cutting at 128K is insufficient for precise retrieval over
long-context (Fig. 4), and one need to upsample long sequences; (2) improved
performance in one domain may not transfer and could even hurt another domain
(Table 5), showing that one needs to balance the mixture ratio of different
domains.

##  4 Infrastructure and Engineering

We continue pretraining the model on the data mixture yielded by the ”Per-
source Upsampling” strategy as introduced in section 3, where we train with a
80K sequence length for 7B models, and 64K for 13B models. A “brute force”
training on 80K context may seem impractical at first glance given the
quadratic complexity of attention. However, in our initial tests, we found
this to be feasible, and the actual wallclock time was far from quadratic.
This is due to the fact that most of the time is spent on data transfer from
CPU to GPU (since we use offloading), from one GPU to another GPU via NVLink
(since we use Zero3, see Rajbhandari et al., 2020) and from GPU High-Bandwidth
Memory (HBM) to Streaming Multiprocessors (SM) (as in FlashAttention, see Dao,
2023). These IO operations are all constant or linear in sequence length. The
actual quadratic attention computation, when performed on SM, is highly
parallelized, and thus largely hidden by the linear IO cost. Consequently,
training on 80K is only 3x slower than training on 4K.

Our specific configuration is listed on Table 2. We note that this
configuration is substantially cheaper than previous work (Xiong et al.,
2023), as they continue pretraining the model on more than 400B tokens.
However this configuration seems to be the limit of Huggingface-DeepSpeed
framework, and setting even longer context leads to memory overflow. Since
Zero Optimizer is data parallel, increasing number of GPUs cannot further
increase context length, and most of the GPU memory is taken by the KV cache.
We refer the reader to more advanced sequence parallelism techniques in (Li et
al., 2021; Jacobs et al., 2023) for training on even longer sequences (e.g.,
200K), and we leave the exploration of training on 200K context for future
work.

For training, we use a constant learning rate 2e-5. We modify the base of RoPE
positional encoding to adjust it to longer context, as in Xiong et al. (2023).
We pack all data to 80K chunks regardless of the document boundary, following
common practice (Raffel et al., 2020; Touvron et al., 2023a). We set the batch
size to be 4M tokens. Note that this batch size is the same as training on 4K
context length, as we increase the length of a chunk but decrease the number
of chunks in a batch. We train the model on 5B tokens, which translates to 5B
(size of data) / 4M (batch size) = 2000 optimization steps.

Table 2: We show that long context continual pretraining is feasible under academic-level resources. Our configuration on 8$\times$80G A100s, as listed below, takes 5 days, which is about 1% budget than existing works such as Xiong et al. (2023), which trains on 400B tokens.  Framework | Huggingface Transformers
---|---
| \+ DeepSpeed Zero 3
| \+ FlashAttention 2
| \+ Gradient Checkpointing
| \+ CPU Offloading
Hardware | 8 $\times$ 80G A100
LLaMA 2 7B | Ctx. 4K 3 days / 10B tokens
| Ctx. 80K 10 days / 10B tokens
LLaMA 2 13B | Ctx. 4K 5 days / 10B tokens
| Ctx. 64K 13 days / 10B tokens
Hardware | 2 $\times$ 8 $\times$ 80G A100
LLaMA 2 7B | Ctx. 4K 2 days / 10B tokens
| Ctx. 80K 7 days / 10B tokens
LLaMA 2 13B | Ctx. 4K 4 days / 10B tokens
| Ctx. 64K 10 days / 10B tokens

##  5 Experimental Results

We continue pretraining the base LLaMA 2 7B/ 13B models on data produced by
our ”Per-source Upsampling” strategy (Sec. 5.3). The number of training tokens
is 5B. We first show that our method outperforms strong open-source baselines
like YaRN Mistral 7B 128K (Peng et al., 2023) and LongLoRA 7B 100K (Chen et
al., 2023b), and closes the gap to GPT-4 Turbo 128K. Then we dissect the
ingredients of our data recipe. In section 5.2, we discuss data sufficiency
(the 5B part) and show that as we increase the amount of data from 100M to 1B,
the model gradually surfaces the ability to precisely retrieve given
information at arbitrary locations within 128K documents. In section 5.3, we
discuss the data mixture (the per-source length upsampled part), and show that
the original mixture of SlimPajama is insufficient (although it has about 30%
data longer than 4K), and one needs to upsample long sequences for the model
to acquire the long context capability. We also show that the improvements on
one upsampled domain (e.g., Books), have limited transfer to others, and can
even hurt them. The Book and Code domains are a particular example that
improvements on one come with detrimental impact on the other.

Existing work heavily uses validation loss as the primary evaluation (Chen et
al., 2023a, b; Xiao et al., 2023; Peng et al., 2023). We show that using only
the validation loss is insufficient because two data recipes that result in
similar loss may have substantially different retrieval capabilities, as we
show in Fig. 4. In addition to Needle-in-a-Haystack, we use a real-world book-
long question answering benchmark (Zhang et al., 2023) for our evaluation.
There are earlier long context benchmarks such as Zeroscrolls (Shaham et al.,
2023), longbench (Bai et al., 2023b) and L-Eval (An et al., 2023). We do not
evaluate on them because their lengths are mostly around 10K, which were
considered long at their release time, but substantially shorter than the 128K
regime, which is the focus of the present work.

###  5.1 Overall Performance

Table 3:  Our method achieves better long context task performance (Needle. performance) without compromising short context performance (MMLU).  | Ctx. | Needle. | MMLU
---|---|---|---
Non-LLaMA Models
GPT-4-Turbo | 128K | 87.1 | 86.4
GPT-3.5-Turbo | 16K | - | 67.3
YaRN Mistral 7B | 128K | 57.4 | 59.4
LLaMA-2 7B Based Models
Together LLaMA-2 7B | 32K | 27.9 | 44.8
LongChat v1.5 7B | 32K | 18.0 | 42.3
LongLoRA 7B | 100K | 70.0 | 37.9
Ours LLaMA-2 7B | 80K | 88.0 | 43.3
LLaMA-2 13B Based Models
LongLoRA 13B | 64K | 54.1 | 50.1
Ours LLaMA-2 13B | 64K | 90.0 | 52.4

Figure 1 compares our method with Together AI’s LLaMA-2 32K (Together, 2023),
LMSys’ LongChat v1.5 32K (Li et al., 2023a), YaRN Mistral 7B 128K (Peng et
al., 2023), and LongLoRA 100K (Chen et al., 2023b). We choose these models as
our baseline because they are so far the top open-source long-context language
models (as evidenced by thousands of GitHub stars). LongChat v1.5 32K does not
perform well even for sequence length 16K-32K, and we hypothesize that this is
because the model has not gone through enough continual pretraining, but
directly goes to finetuning. Together AI’s LLaMA-2 7B’s data mixture is
similar to ours, which we believe to be the reason that they perform well
within 32K. Yet their model does not generalize beyond 32K, while ours
generalizes from 80K to 128K. For LongLoRA, we believe the two major problems
are that they use sparse attention and that they do not upsample long sequence
data, which we show is problematic in Fig. 4. For YaRN Mistral, we hypothesize
that its underperformance is due to its being only trained on PG19 book (Rae
et al., 2019); we show that it is important to use a balanced domain mixture
in Table 5.

Figure 3:  As we increase the number of trained tokens, the model’s retrieval
performance increases with converged validation loss. We further note two
observations with regard to data quantity: (1) 500M tokens are enough to
unlock most of the retrieval accuracy. Since we are not explicitly training
the model to perform retrieval, this potentially suggests that the model
already has the precise retrieval capability, and that we are simply extending
this capability with lightweight continual pretraining; (2) the model’s
retrieval performance saturates at about 5B tokens, and further scaling to 10B
tokens does not improve length generalization.

In Table 3 we show that our method not only improves precise retrieval, but
maintains short context performance, evidenced by strong MMLU (Hendrycks et
al., 2020) score, which is a widely-accepted benchmark for testing the general
capabilities (within short context) of language models, and is used by
Chinchilla (Hoffmann et al., 2022), LLama (Touvron et al., 2023a, b), Mistral
(Jiang et al., 2023), QWen (Bai et al., 2023a), and Baichuan (Yang et al.,
2023a).

Table 4 further compares 128K context language models on a book-long question
answering benchmark recently proposed by Zhang et al. (2023). This task
conditions language models on a book and then asks questions about the plot.
Our method outperforms LongLoRA and Yarn Mistral (even though Mistral 7B is a
stronger base model than LLaMA 2 7B we use). Our 13B model performance closes
the gap to GPT-4 128K, and we anticipate that future scaling and instruction
tuning will further improve performance. While there are other long-context
benchmarks in InfiniBench (Zhang et al., 2023), in our initial experiments we
found that models often had trouble understanding the instruction (because
they are not instruction tuned). Hence we focus on the BookQA benchmark where
base LLMs performed reasonably without instruction tuning.

###  5.2 Data Quantity

Table 4:  The performaince gain shown in Needle-in-a-Haystack further translates to improvements on downstream BookQA. We report the results on 128K length InfiniBench long book question answering task (Zhang et al., 2023). Our method outperforms top open-source models and closes the gap to GPT-4.  Model / Train Len | Test Len | BookQA
---|---|---
GPT-4-Turbo 128K | 128K | 37.4
LongLoRA 7B 100K | 128K | 24.3
Ours LLaMA-2 7B 80K | 128K | 27.4
LongLoRA 13B 64K | 128K | 24.6
YaRN Mistral 7B 128K | 128K | 26.3
Ours LLaMA-2 13B 64K | 128K | 31.1
Table 5:  How different data engineering methods improves (or does not improve) the original data mixture, where we show results from continual pretraining of a 7B LLaMA-2 on 5B tokens packed to 80K length. We consider how changing the original data mixture to long-context upsampled data mixture results in different loss across domains, and report the loss differences to the original data mixture (e.g., the loss of per-source length upsampling minus the loss of original mixture). We view a loss difference larger than 0.01 significant, marked by a red shade indicating performance decrease of larger than +0.01 loss; or a green shade indicating performance improvements of smaller than -0.01 loss, or a grey shade indicating no significant differences. Although upsampling book / code / arxiv improves in-domain performance for both short and long context, such improvements do not transfer to all domains. Instead, upsampling one domain, e.g., code, may even harm another domain, e.g., book. Per-source length upsampling is the most balanced mixture with almost no significant increase of loss across domains.  | C4 | CC | Stack | Arxiv | Wiki | Book | Github
---|---|---|---|---|---|---|---
0 - 4K Context Length
Original | 2.038 | 1.760 | 1.519 | 1.660 | 1.424 | 2.085 | 0.907
v.s. Per-source | \+ .002 | \+ .008 | – .001 | – .008 | – .040 | – .065 | – .008
v.s. Global | \+ .008 | \+ .010 | \+ .015 | – .020 | – .020 | – .140 | \+ .015
v.s. Code$\uparrow$ | \+ .010 | \+ .016 | \+ .010 | \+ .006 | – .026 | \+ .030 | – .023
v.s. Book$\uparrow$ | \+ .010 | \+ .016 | \+ .021 | \+ .000 | – .010 | – .175 | \+ .029
v.s. Arxiv$\uparrow$ | \+ .006 | \+ .016 | \+ .013 | – .060 | – .030 | \+ .040 | \+ .025
4K - 128K Context Length
Original | 1.560 | 1.650 | 0.786 | 1.075 | 1.313 | 1.852 | 0.447
v.s. Per-source | – .010 | – .010 | – .006 | – .011 | – .044 | – .014 | \+ .002
v.s. Global | – .010 | – .006 | – .001 | – .016 | – .040 | – .018 | – .007
v.s. Code$\uparrow$ | – .008 | – .002 | – .003 | – .007 | – .042 | – .010 | – .029
v.s. Book$\uparrow$ | – .010 | – .006 | \+ .001 | – .007 | – .037 | – 0.30 | \+ .000
v.s. Arxiv$\uparrow$ | – .008 | – .002 | \+ .002 | – .036 | – .039 | – .010 | – .004

Now we consider data quantity, i.e., how much data enables the language model
to utilize the information at arbitrary locations within 128K context. Our
hypothesis is that precise retreival over long-range context is an intrinsic
capability obtained by large-scale pretraining, even when the pretraining
context length is substantially shorter (4K in many cases). If this hypothesis
is true, then lightweight continual pretraining should be enough to extend
this capability to much longer context lengths than see in training. That is,
we would not need data-intensive continual pretraining as used by Xiong et al.
(2023) and XVerse (2024).

Fig. 3 shows how data scaling gradually unlocks the model’s retrieval
capability. When the model is continually pretrained on 100M to 300M tokens,
the model’s loss gradually decreases, but it has not converged yet. At 500M to
1B tokens, the model achieves relatively good performance within its
continually pretrained 80K context, but does not generalize to 80K-128K range.
After 5B tokens, the model performs well on 0-80K, and can generalize to
unseen lengths 80K-128K. At 10B token, the model seems to overfit on its 80K
training range, and the length generalization starts to decrease. Along this
process, we see a gradual decrease in loss, which correlates with the increase
in the retrieval performance. This result provides more evidence for our
hypothesis, as only 500M tokens are required to enable a model’s retrieval
capability with 80K context.

Continually pretraining a 7B LLaMA-2 takes about 5 days on 8$\times$80G A100
GPUs, and the cost is reasonable compared to large-scale pretraining (which
requires months of compute on thousands of GPUs). Our results suggest that for
supervised finetuning, since training on long-context is substantially cheaper
than previously thought, future work may dive deeper on the solutions for 100K
length finetuning and reasoning, which so far has almost no open-source work
to our knowledge. For pretraining research, currently there is no definite
answer as to whether long-context continual pretraining should be combined
with other capabilities, such as math (Azerbayev et al., 2023) and code (Chen
et al., 2021), which typically require hundreds of billions of tokens. Our
results suggest that long-context continual pretraining could be a separate
stage after code and math pretraining.

###  5.3 Data Mixture

Figure 4: The importance of length upsampling. The validation loss, a common
measure for long-context language modeling used in Xiong et al. (2023); Chen
et al. (2023b), cannot reveal long-context retreival capability, but Needle-
in-a-Haystack can. The original data mixture, i.e. without length upsampling,
despite giving very close loss, performs badly on precise retrieval. Per-
source length upsampling significantly improves precise retrieval.

Now we discuss why per-source length upsampling is necessary when constructing
the data mixture. Recall that this strategy keeps the mixture ratio of the
data sources the same as the original data, i.e., 67% CommonCrawl (CC), 15%
C4, 4.5% Github, 4.5% Wikipedia, 4.5% books, 2.5% Arxiv and 2.0% StackExchange
for SlimPajama. Then in each of the domains, we upsample sequences longer than
4K from about 30% to about 70%. Doing this enables us to keep the domain
mixture ratio fixed, only changing the length distribution of the training
documents. In contrast, globally upsampling long sequences (without
considering their domain), or intentionally upsampling code/ book/ Arxiv
(since they are long) changes both the domain mixture and the length
distribution.

We compare all the data mixtures with the original one packed to 80K / 64K for
the continual pretraining of the 7B / 13B LLaMA-2. This baseline approach
effectively never changes the original data, but keeps the naturally existing
long sequence that would otherwise been cut to 4K (recall Sec. 3). If a data
mixture is effective, it should be at least better than this baseline “do
nothing” approach.

Table 5 compares the per-domain loss differences of all the data mixture
against the baseline original mixture. We report the differences of the
validation loss, where a more than 0.01 loss change is considered significant,
following common pretraining practice (Kaplan et al., 2020; Peng et al., 2023;
Hoffmann et al., 2022). We observe: (1) for 0-4K short context data, most of
the data mixtures have a negative impact on webpages (C4, CC and
StackExchange), except for the per-source approach; (2) performance
improvements from domains like Book may not transfer to others, and even hurt
code performance; (3) per-source length upsampling is the most balanced
mixture that improves 4K-128K context losses without much sacrificing short-
context losses, whereas all other methods show more or less performance
tradeoff across domains. Combining these observations, we recommend the per-
source length-upsampling strategy.

Since per-source length upsampling keeps the domain mixture ratio while
increasing tokens from long sequences, its major difference to the original
data mixture is the distribution of sequence length. Fig. 4 makes a close
comparison between the two data strategies. Specifically, we train two LLaMA-2
7B models with a 80K context length using original / per-source upsampled data
mixture, and report their per-length validation loss and Needle-in-a-Haystack
performance. Note that LongLoRA (Chen et al., 2023b) uses the original data
mixture without length upsampling, so our results also explains why we achieve
better performance than LongLoRA (Fig. 1). We see that the original data
mixture without length upsampling, despite achieving a very close loss,
underperforms on precise retrieval. Per-source length upsampling significantly
improves precise retrieval. This observation also serves as strong evidence
why only using test loss, the evaluation used in most prior work (Chen et al.,
2023a; Peng et al., 2023; Chen et al., 2023b; Xiao et al., 2023; Anthropic,
2023), may conceal the underlying model differences. The necessity of length
upsampling is demonstrated by the Needle-in-a-Haystack test.

##  6 Discussion

We attribute our improvements over strong open-source baselines, as is
detailed in section 5, to our careful treatments of data engineering. Our
results echo the recent wisdom that in large language model research, data
engineering is equally important as modeling and algorithmic innovations
(Kaplan et al., 2020; Hoffmann et al., 2022; Brown et al., 2020). As we list
in Table 1, many of the data details are crucial for strong long-context
performance, yet may be easily overlooked. We also acknowledge that our
research is made possible through utilizing the latest innovations in machine
learning systems research, particularly FlashAttention (Dao, 2023) as it
reduces the memory usage of the attention mechanism from quadratic to linear.
Incorporating further work on sequence parallelism (Li et al., 2021; Jacobs et
al., 2023) could enable brute force training of even longer context (e.g.,
200K) models.

The Transformer’s use of position embeddings makes it difficult to generalize
significantly beyond contexts seen during training even with relative
positional encodings (Press et al., 2021; Sun et al., 2022; Li et al., 2023b),
thus necessitating (at least a little bit of) continual pretraining. There has
much recent work on RNN-like architectures, which implicitly encode positional
information through their hidden states, that perform competitively with
Transformers (Sun et al., 2023; Qin et al., 2023; Gu & Dao, 2023; Yang et al.,
2023b). It would be interesting to test whether such models can generalize
zero-shot to longer contexts than seen during training on the Needle-in-a-
Haystack benchmark.

Long-context language model research at the 100K-level is still a developing
research area. This work only studies continual pretraining, and research on
instruction finetuning language models on tasks of 100K context length (e.g.,
repo-level code understanding) is still limited. So far there seems to no
open-source instruction-finetuned 100K context language models. We hope our
work serve as a basis for future work on 100K-level long context superivsed
finetuning.

##  7 Conclusion

This work studies a continual pretraining recipe for scaling language models’
context length to 128K tokens. We demonstrate that the ability to utilize
information at arbitrary locations within the 128K input is already mostly
acquired by large-scale pretraining, even for models pretrained on
substantially shorter 4K context. We show that continual pretraining of the
full model on 1-5 billion tokens from per-source length-upsampled data gives
the most balanced performance improvements. Our work closes the gap to
frontier models like GPT-4 128K on the retrieval task and serves as the
foundation for future long-context instruction finetuning research.

## References

  * An et al. (2023) An, C., Gong, S., Zhong, M., Li, M., Zhang, J., Kong, L., and Qiu, X.  L-eval: Instituting standardized evaluation for long context language models.  _arXiv preprint arXiv:2307.11088_ , 2023.
  * Anthropic (2023) Anthropic.  Model card and evaluations for claude models, July 2023.  URL https://www.anthropic.com/product.
  * Azerbayev et al. (2023) Azerbayev, Z., Schoelkopf, H., Paster, K., Santos, M. D., McAleer, S., Jiang, A. Q., Deng, J., Biderman, S., and Welleck, S.  Llemma: An open language model for mathematics.  _arXiv preprint arXiv:2310.10631_ , 2023.
  * Bai et al. (2023a) Bai, J., Bai, S., Chu, Y., Cui, Z., Dang, K., Deng, X., Fan, Y., Ge, W., Han, Y., Huang, F., et al.  Qwen technical report.  _arXiv preprint arXiv:2309.16609_ , 2023a.
  * Bai et al. (2023b) Bai, Y., Lv, X., Zhang, J., Lyu, H., Tang, J., Huang, Z., Du, Z., Liu, X., Zeng, A., Hou, L., et al.  Longbench: A bilingual, multitask benchmark for long context understanding.  _arXiv preprint arXiv:2308.14508_ , 2023b.
  * Bairi et al. (2023) Bairi, R., Sonwane, A., Kanade, A., Iyer, A., Parthasarathy, S., Rajamani, S., Ashok, B., Shet, S., et al.  Codeplan: Repository-level coding using llms and planning.  _arXiv preprint arXiv:2309.12499_ , 2023.
  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Caciularu et al. (2023) Caciularu, A., Peters, M. E., Goldberger, J., Dagan, I., and Cohan, A.  Peek across: Improving multi-document modeling via cross-document question-answering.  _arXiv preprint arXiv:2305.15387_ , 2023.
  * Chen et al. (2021) Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ , 2021.
  * Chen et al. (2023a) Chen, S., Wong, S., Chen, L., and Tian, Y.  Extending context window of large language models via positional interpolation.  _arXiv preprint arXiv:2306.15595_ , 2023a.
  * Chen et al. (2023b) Chen, Y., Qian, S., Tang, H., Lai, X., Liu, Z., Han, S., and Jia, J.  Longlora: Efficient fine-tuning of long-context large language models.  _arXiv preprint arXiv:2309.12307_ , 2023b.
  * Dao (2023) Dao, T.  Flashattention-2: Faster attention with better parallelism and work partitioning.  _arXiv preprint arXiv:2307.08691_ , 2023.
  * Fuzhao Xue & You (2023) Fuzhao Xue, Zian Zheng, Y. F. J. N. Z. Z. W. Z. and You, Y.  Openmoe: Open mixture-of-experts language models.  https://github.com/XueFuzhao/OpenMoE, 2023.
  * Gu & Dao (2023) Gu, A. and Dao, T.  Mamba: Linear-time sequence modeling with selective state spaces.  2023\.  URL https://api.semanticscholar.org/CorpusID:265551773.
  * Hendrycks et al. (2020) Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J.  Measuring massive multitask language understanding.  _arXiv preprint arXiv:2009.03300_ , 2020.
  * Hoffmann et al. (2022) Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al.  Training compute-optimal large language models.  _arXiv preprint arXiv:2203.15556_ , 2022.
  * Jacobs et al. (2023) Jacobs, S. A., Tanaka, M., Zhang, C., Zhang, M., Song, L., Rajbhandari, S., and He, Y.  Deepspeed ulysses: System optimizations for enabling training of extreme long sequence transformer models.  _arXiv preprint arXiv:2309.14509_ , 2023.
  * Jiang et al. (2023) Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, D. S., Casas, D. d. l., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., et al.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_ , 2023.
  * Kamradt (2023) Kamradt, G.  Needle in a haystack - pressure testing llms.  https://github.com/gkamradt/LLMTest_NeedleInAHaystack, 2023.
  * Kaplan et al. (2020) Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Li et al. (2023a) Li, D., Shao, R., Xie, A., Sheng, Y., Zheng, L., Gonzalez, J. E., Stoica, I., Ma, X., and Zhang, H.  How long can open-source llms truly promise on context length?, June 2023a.  URL https://lmsys.org/blog/2023-06-29-longchat.
  * Li et al. (2021) Li, S., Xue, F., Baranwal, C., Li, Y., and You, Y.  Sequence parallelism: Long sequence training from system perspective.  _arXiv preprint arXiv:2105.13120_ , 2021.
  * Li et al. (2023b) Li, S., You, C., Guruganesh, G., Ainslie, J., Ontanon, S., Zaheer, M., Sanghai, S., Yang, Y., Kumar, S., and Bhojanapalli, S.  Functional interpolation for relative positions improves long context transformers.  _arXiv preprint arXiv:2310.04418_ , 2023b.
  * Mazumder & Liu (2024) Mazumder, S. and Liu, B.  _Lifelong and Continual Learning Dialogue Systems_.  Springer Nature, 2024.
  * Peng et al. (2023) Peng, B., Quesnelle, J., Fan, H., and Shippole, E.  Yarn: Efficient context window extension of large language models, 2023\.
  * Press et al. (2021) Press, O., Smith, N. A., and Lewis, M.  Train short, test long: Attention with linear biases enables input length extrapolation.  _arXiv preprint arXiv:2108.12409_ , 2021.
  * Qin et al. (2023) Qin, Z., Yang, S., and Zhong, Y.  Hierarchically gated recurrent neural network for sequence modeling.  _CoRR_ , abs/2311.04823, 2023.  doi: 10.48550/ARXIV.2311.04823.  URL https://doi.org/10.48550/arXiv.2311.04823.
  * Rae et al. (2019) Rae, J. W., Potapenko, A., Jayakumar, S. M., Hillier, C., and Lillicrap, T. P.  Compressive transformers for long-range sequence modelling.  _arXiv preprint_ , 2019.  URL https://arxiv.org/abs/1911.05507.
  * Raffel et al. (2020) Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ , 21(1):5485–5551, 2020.
  * Rajbhandari et al. (2020) Rajbhandari, S., Rasley, J., Ruwase, O., and He, Y.  Zero: Memory optimizations toward training trillion parameter models.  In _SC20: International Conference for High Performance Computing, Networking, Storage and Analysis_ , pp. 1–16. IEEE, 2020.
  * Shaham et al. (2023) Shaham, U., Ivgi, M., Efrat, A., Berant, J., and Levy, O.  Zeroscrolls: A zero-shot benchmark for long text understanding, 2023.
  * Soboleva et al. (2023) Soboleva, D., Al-Khateeb, F., Myers, R., Steeves, J. R., Hestness, J., and Dey, N.  SlimPajama: A 627B token cleaned and deduplicated version of RedPajama.  https://www.cerebras.net/blog/slimpajama-a-627b-token-cleaned-and-deduplicated-version-of-redpajama, 2023\.  URL https://huggingface.co/datasets/cerebras/SlimPajama-627B.
  * Sun et al. (2022) Sun, Y., Dong, L., Patra, B., Ma, S., Huang, S., Benhaim, A., Chaudhary, V., Song, X., and Wei, F.  A length-extrapolatable transformer.  _arXiv preprint arXiv:2212.10554_ , 2022.
  * Sun et al. (2023) Sun, Y., Dong, L., Huang, S., Ma, S., Xia, Y., Xue, J., Wang, J., and Wei, F.  Retentive network: A successor to transformer for large language models.  _arXiv preprint arXiv:2307.08621_ , 2023.
  * Team (2023) Team, M. N.  Introducing mpt-7b: A new standard for open-source, commercially usable llms, 2023.  URL www.mosaicml.com/blog/mpt-7b.  Accessed: 2023-03-28.
  * Together (2023) Together.  Llama-2-7b-32k-instruct — and fine-tuning for llama-2 models with together api, August 2023.  URL https://www.together.ai/blog/llama-2-7b-32k-instruct.
  * Touvron et al. (2023a) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023a.
  * Touvron et al. (2023b) Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023b.
  * Weng (2023) Weng, L.  Llm-powered autonomous agents.  _lilianweng.github.io_ , Jun 2023.  URL https://lilianweng.github.io/posts/2023-06-23-agent/.
  * Xiao et al. (2023) Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M.  Efficient streaming language models with attention sinks.  _arXiv preprint arXiv:2309.17453_ , 2023.
  * Xiong et al. (2023) Xiong, W., Liu, J., Molybog, I., Zhang, H., Bhargava, P., Hou, R., Martin, L., Rungta, R., Sankararaman, K. A., Oguz, B., et al.  Effective long-context scaling of foundation models.  _arXiv preprint arXiv:2309.16039_ , 2023.
  * XVerse (2024) XVerse.  Xverse-13b, January 2024.  URL https://github.com/xverse-ai/XVERSE-13B/blob/main/README_EN.md.
  * Yang et al. (2023a) Yang, A., Xiao, B., Wang, B., Zhang, B., Bian, C., Yin, C., Lv, C., Pan, D., Wang, D., Yan, D., et al.  Baichuan 2: Open large-scale language models.  _arXiv preprint arXiv:2309.10305_ , 2023a.
  * Yang et al. (2023b) Yang, S., Wang, B., Shen, Y., Panda, R., and Kim, Y.  Gated linear attention transformers with hardware-efficient training.  _arXiv preprint arXiv:2312.06635_ , 2023b.
  * Zhang et al. (2023) Zhang, X., Chen, Y., Hu, S., Wu, Q., Chen, J., Xu, Z., Dai, Z., Han, X., Wang, S., Liu, Z., and Sun, M.  Infinitebench: 128k long-context benchmark for language models, 2023.