# Analysing The Impact of Sequence Composition
on Language Model Pre-Training

Yu Zhao † ✉ Yuanbin Qu ‡ Konrad Staniszewski § Szymon Tworkowski §
Wei Liu ‡ Piotr Miłoś § Yuxiang Wu ¶ Pasquale Minervini † ✉
† University of Edinburgh ‡ Xiaomi AI Lab § University of Warsaw ¶ Weco AI
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Most language model pre-training frameworks concatenate multiple documents
into fixed-length sequences and use _causal masking_ to compute the likelihood
of each token given its context; this strategy is widely adopted due to its
simplicity and efficiency. However, to this day, the influence of the pre-
training sequence composition strategy on the generalisation properties of the
model remains under-explored. In this work, we find that applying causal
masking can lead to the inclusion of distracting information from previous
documents during pre-training, which negatively impacts the performance of the
models on language modelling and downstream tasks. In _intra-document causal
masking_ , the likelihood of each token is only conditioned on the previous
tokens in the same document, eliminating potential distracting information
from previous documents and significantly improving performance. Furthermore,
we find that concatenating related documents can reduce some potential
distractions during pre-training, and our proposed efficient retrieval-based
sequence construction method, Bm25Chunk, can improve in-context learning
(+11.6%), knowledge memorisation (+9.8%), and context utilisation (+7.2%)
abilities of language models without sacrificing efficiency. 00footnotetext:
https://github.com/yuzhaouoe/pretraining-data-packing

Analysing The Impact of Sequence Composition
on Language Model Pre-Training

Yu Zhao † ✉ Yuanbin Qu ‡ Konrad Staniszewski § Szymon Tworkowski § Wei Liu ‡
Piotr Miłoś § Yuxiang Wu ¶ Pasquale Minervini † ✉ † University of Edinburgh ‡
Xiaomi AI Lab § University of Warsaw ¶ Weco AI<EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Large Language Models (LLMs) are pre-trained on large amounts of documents by
optimising a language modelling objective and show an intriguing ability to
solve a variety of downstream NLP tasks (Brown et al., 2020; Biderman et al.,
2023; Touvron et al., 2023; Jiang et al., 2023). Previous works emphasise the
importance of pre-training data quality (e.g., Gunasekar et al., 2023; Lee et
al., 2022; Tirumala et al., 2023; Soboleva et al., 2023) and diversity (e.g.,
Xie et al., 2023; Gao et al., 2021; Kaddour, 2023) to improve the
generalisation properties of language models. However, the influence of the
pre-training sequence composition strategy remains largely under-explored.

For most decoder-only language model pre-training pipelines (e.g., Shoeybi et
al., 2019; Ott et al., 2019; Brown et al., 2020; Biderman et al., 2023; Geng,
2023; Liu et al., 2023b; Zhang et al., 2024), constructing a pre-training
instance involves _packing_ , which refers to the process of combining
randomly sampled documents into a _chunk_ that matches the size of the context
window; and _causal masking_ , which refers to predicting the next token
conditioned on all previous tokens, including those from different documents
in the chunk. An alternative to causal masking is _intra-document causal
masking_ , where the likelihood of each token is conditioned on the previous
tokens from the same document; intra-document causal masking is not commonly
used in existing open-source pre-training frameworks as it is argued to
adversely impact pre-training efficiency (Brown et al., 2020; Pagliardini et
al., 2023). However, to the best of our knowledge, there is no systematic
analysis in the literature on how causal masking affects the generalisation
properties of models despite its role in improving efficiency.

To analyse the impact of the packing and masking strategies on pre-training,
we pre-train language models using intra-document causal masking (referred to
as IntraDoc, Section 2.2) and compare them with models pre-trained via causal
masking with several _packing_ strategies by varying the relatedness of the
documents in the pre-training chunks. Specifically, we analyse the results
produced by a commonly used baseline method that randomly samples and packs
documents (MixChunk); a method that samples and packs documents from the same
source based on their meta-information (UniChunk); and our proposed efficient
retrieval-based packing method, which retrieves and packs related documents
(Bm25Chunk, Section 2.1).

Our experimental results indicate that using causal masking without
considering the boundaries of documents can lead to the inclusion of
distracting information from previous documents during pre-training (Section 3
and Section 5.1), negatively impacting the performance of the models in
downstream tasks (Section 4). We observe that intra-document causal masking,
which eliminates the potential distractions from irrelevant documents during
pre-training, can significantly improve the performance of the model while
increasing its runtime ($+4\%$ in our implementation, see Appendix A).

We also find that improving the relatedness of the documents in pre-training
chunks can reduce some potential distractions from previous documents (e.g.,
UniChunk avoids packing documents from different distributions, such as code
and news text), which can improve the performance of causal masking models on
a wide array of downstream tasks. Finally, we show that our proposed efficient
retrieval-based packing method, Bm25Chunk, can improve a model’s language
modelling (+$6.8\%$), in-context learning (+$11.6\%$), knowledge memorisation
(+$9.8\%$), and context utilisation (+$7.2\%$) abilities using causal masking
and thus without sacrificing pre-training efficiency.

Our main contributions and findings can be summarised as follows:

  * •

We systematically analyse and compare the models pre-trained using causal
masking and intra-document causal masking; our experimental results reveal
that using causal masking without considering the boundaries of documents can
result in significant performance degradation (Section 3 and Section 4).

  * •

We find that improving the relatedness of the documents in each pre-training
chunk benefits causal masking models, and our proposed efficient retrieval-
based packing method (Bm25Chunk, Section 2.1) can improve the performance of
language models significantly.

  * •

We quantitatively analyse the attention distribution of the models during
language modelling (Section 5.1), and investigate the burstiness property of
pre-training chunks (Section 5.2); our findings indicate that models can be
more robust to irrelevant contexts and obtain better performance when
improving the relatedness of documents in pre-training chunks.

##  2 Packing and Masking Strategies for Pre-Training Sequence Composition

In this section, we formally introduce the pre-training data packing
strategies, causal masking, and intra-document causal masking.

###  2.1 Packing Strategies

Let $\mathcal{D}_{i}$ represent a corpus, such as Wikipedia, C4, or GitHub,
and let $\mathcal{D}=\bigcup_{s}\mathcal{D}_{s}$ denote the dataset resulting
from the union of such corpora. Furthermore, each corpus $\mathcal{D}_{s}$ is
defined as a set of documents
$\mathcal{D}_{s}=\\{d_{1},\ldots,d_{|\mathcal{D}_{s}|}\\}$ , where each
document $d_{i}$ is defined as a sequence of tokens
$d_{i}=\left(x_{1},\ldots,x_{|d_{i}|}\right)$.

A _packing strategy_ involves first selecting a set of documents
$\\{d_{i}\\}_{i=1}^{n}$ from $\mathcal{D}$, and then packing them into a chunk
$C$ with a fixed length $|C|=L$. Following Brown et al. (2020), we concatenate
the documents $\\{d_{i}\\}_{i=1}^{n}$ by interleaving them with end-of-
sentence ([eos]) tokens to construct a chunk. A _packed sequence_ (or _chunk_)
$C$ is denoted as:

$C=(d_{1}\textsc{[eos]}d_{2}\textsc{[eos]}\ldots\textsc{Split}(d_{n})),$ (1)

where $[\textsc{eos}]$ is the end-of-sentence token, $\textsc{Split}()$
truncates the last document such that $|C|=L$, and the content of the chunk
$C$ will be removed from the dataset $\mathcal{D}$ to avoid sampling the same
documents multiple times.

In the following, we introduce three strategies to sample the documents
$\\{d_{i}\\}_{i=1}^{n}$ from the dataset $\mathcal{D}$ for composing each pre-
training chunk, namely MixChunk, UniChunk, and Bm25Chunk.

####  MixChunk

In MixChunk (baseline), documents $d_{i}\in\mathcal{D}$ are sampled uniformly
at random from the entire pre-training corpus $\mathcal{D}$:

$d_{i}\sim\text{Uniform}(\mathcal{D}).$

As a result, in MixChunk, a chunk can contain documents from different source
datasets, e.g., Wikipedia and GitHub, as shown in Figure 1(1(a)).

####  UniChunk

In UniChunk, each chunk is composed of documents from a single source corpus
$\mathcal{D}_{s}$:

$d_{i}\sim\text{Uniform}(\mathcal{D}_{s}),\quad\text{with
}\mathcal{D}_{s}\subseteq\mathcal{D}.$

This helps to avoid packing documents from different distributions (such as
code and news text) together. To construct a training batch, we sample
sequences from each corpus $\mathcal{D}_{s}$ in proportion to the number of
tokens in $\mathcal{D}_{s}$.

####  Bm25Chunk

(a)  MixChunk randomly samples documents from all corpora to construct pre-
training sequences, which can pack documents from different sources. UniChunk
randomly samples documents from a single source to construct a sequence.

(b) The sequence construction process in Bm25Chunk. The left part represents a
document buffer that caches a set of documents randomly sampled from the
corpus.

Figure 1: Packing strategies for pre-training chunks construction. (a)
illustrates the compositions of MixChunk and UniChunk; (b) presents the
sequence construction process of Bm25Chunk.

To improve the relevance of documents in pre-training chunks, we employ a
BM25-based retriever to construct pre-training chunks, referred to as
Bm25Chunk. Specifically, given a document $d_{i}\in\mathcal{D}_{s}$, we
retrieve a sequence of documents $\\{d_{i}\\}_{i=1}^{n}$ by
$d_{i+1}=\textsc{Retrieve}(d_{i},\mathcal{D}_{s})$; here,
$\textsc{Retrieve}(d_{i},\mathcal{D}_{s})$ retrieves the most similar
documents to $d_{i}$ from $\mathcal{D}_{s}$ based on BM25 scoring.

However, this retrieval process can be computationally inefficient due to the
size of the pre-training corpus $\mathcal{D}_{s}$. To improve the efficiency
of the retrieval step, we restrict the retrieval scope to a subset
$\mathcal{B}_{s}\subseteq\mathcal{D}_{s}$ of the corpus $\mathcal{D}_{s}$,
reducing the computational complexity of retrieval; the proposed approach is
outlined in Figure 1(1(b)). More formally, we introduce a document buffer
$\mathcal{B}_{s}\subseteq\mathcal{D}_{s}$ that contains $k$ documents
uniformly sampled from $\mathcal{D}_{s}$, which serves as the retrieval source
for constructing pre-training chunks:

$d_{1}\sim\text{Uniform}(\mathcal{B}_{s}),\quad
d_{i+1}=\textsc{Retrieve}(d_{i},\mathcal{B}_{s}).$

After retrieving a sequence of documents $\\{d_{i}\\}_{i=1}^{n}$ from the
buffer $\mathcal{B}_{s}$ for constructing a chunk, we refill the buffer by
sampling new documents from $\mathcal{D}_{s}$. The time complexity analysis
and more details are presented in Appendix C.

###  2.2 Masking Strategies

Another core element of LLM pre-training is the _masking_ strategy, which
determines how next-token prediction distributions are conditioned on other
tokens in the sequence.

#### Causal Masking

In causal masking, each token in a sequence is predicted solely based on all
preceding tokens in the sequence. More formally, given a chunk
$C=(x_{1},\ldots,x_{|C|})$ defined as in Equation 1, the likelihood of $C$ is
given by:

$P(C)=\prod_{i=1}^{|C|}P(x_{i}\mid x_{1},\ldots,x_{i-1}),$

where $P(x_{i}\mid x_{1},\ldots,x_{i-1})$ denotes the probability of the token
$x_{i}$ given all preceding tokens $x_{1},\ldots,x_{i-1}$ in the chunk. During
pre-training, _causal masking_ implies that, given a chunk $C$, the
probability of each token in $C$ will be conditioned on all preceding tokens,
including those belonging to different documents. Causal masking is the
_standard practice_ when pre-training decoder-only LLMs (e.g., Shoeybi et al.,
2019; Brown et al., 2020; Zhang et al., 2022; Biderman et al., 2023; Geng,
2023; Liu et al., 2023b; Zhang et al., 2024).

#### Intra-Document Causal Masking

In intra-document causal masking, on the other hand, the probability of each
token is conditioned on the previous tokens within the same document. More
formally, given a chunk $C$ defined as in Equation 1, the probability of each
token $d_{ij}$ belonging to document $d_{i}$ is only conditioned on the
preceding tokens within $d_{i}$:

$P(C)=\prod_{i=1}^{n}\prod_{j}^{|d_{i}|}P\left(d_{ij}\mid
d_{i1},\ldots,d_{i(j-1)}\right).$

We refer to models trained using intra-document causal masking as IntraDoc.
The details of implementation are available in Appendix A.

##  3 Language Model Pre-Training

$L$ | Model | CommonCrawl | C4 | Wikipedia | GitHub | StackExchange | Book | ArXiv | Avg.
---|---|---|---|---|---|---|---|---|---
2K |  MixChunk | $13.284$ | $13.884$ | $6.811$ | $5.531$ | $8.051$ | $11.623$ | $5.203$ | $9.172$
UniChunk | $11.805$ | $\underline{13.650}$ | $6.546$ | $5.518$ | $7.839$ | $11.353$ | $5.106$ | $8.831_{\downarrow 0.341}$
Bm25Chunk | 11.418 | $13.677$ | $\underline{6.237}$ | $\underline{4.585}$ | $\underline{7.623}$ | $\underline{11.253}$ | $\underline{5.059}$ | $\underline{8.550}_{\downarrow 0.622}$
IntraDoc | $\underline{11.631}$ | 13.197 | 6.084 | 4.252 | 7.535 | 11.130 | 5.030 | $\textbf{8.410}_{\downarrow 0.883}$
8K |  MixChunk | $9.645$ | $14.424$ | $7.010$ | $7.496$ | $8.634$ | $11.337$ | $4.911$ | $9.065$
UniChunk | $9.478$ | $14.190$ | $6.897$ | $7.006$ | $8.456$ | $11.117$ | $4.812$ | $8.851_{\downarrow 0.214}$
Bm25Chunk | $\underline{9.144}$ | $\underline{13.579}$ | $\underline{6.287}$ | $\underline{5.463}$ | $\underline{8.022}$ | $\underline{10.810}$ | $\underline{4.715}$ | $\underline{8.289}_{\downarrow 0.776}$
IntraDoc | 8.994 | 13.173 | 6.073 | 5.010 | 7.894 | 10.701 | 4.705 | $\textbf{8.079}_{\downarrow 0.986}$

Table 1: Evaluation of perplexity on SlimPajama’s test set. The best score is
highlighted in bold, and the second best is highlighted with an underline. $L$
is the maximum length of the sequence for pre-training. Subscript ↓ presents
the PPL improvement over the _baseline_ method MixChunk. We report the results
of next-token accuracy in Appendix F.

###  3.1 Settings

#### Pre-Training Corpora

In this work, we use SlimPajama (Soboleva et al., 2023) as the pre-training
corpus, which consists of seven sub-corpora, including CommonCrawl, C4,
Wikipedia, GitHub, StackExchange, ArXiv, and Book. This allows us to
investigate packing strategies in a mixed corpora setting. We sample documents
with $150$B tokens from SlimPajama as the pre-training corpus and ensure each
subset maintains the same proportion of tokens as in the original dataset.

#### Pre-Training Models

The model implementation is based on the LLaMA (Touvron et al., 2023)
architecture with minor modifications to support intra-document causal
masking. We pre-train 1.3B parameters models using context windows of 2,048
(referred to as 2K) and 8,192 (8K) tokens. We use the same set of documents
with the difference in pre-training sequence composition to pre-train models,
including causal masking models, i.e., MixChunk, UniChunk, and Bm25Chunk, and
intra-document causal masking models IntraDoc. More details are available in
Appendix B.

Previous works (Brown et al., 2020; Pagliardini et al., 2023) argued that
dynamic sequence-specific sparse masking reduces training efficiency. Compared
to causal masking, we observe a $4.0\%$ efficiency degradation on intra-
document causal masking in our implementation, and the discussion on
implementation is presented in Appendix A.

###  3.2 Results

For evaluating LLMs trained under different packing strategies, in this work,
we compute the perplexity (PPL) of a held-out set of documents where each
document is treated independently. The results are summarised in Table 1.

We can see that Bm25Chunk achieves the lowest PPL among the three causal
masking models, yielding a lower average PPL compared to MixChunk in the 2K
($-0.62$) and 8K ($-0.78$) settings. Furthermore, UniChunk also yields a lower
average PPL than the baseline MixChunk ($-0.34$ and $-0.21$). These results
indicate that increasing the relatedness of documents in a sequence can
improve the language modelling ability of models.

When considering models trained via intra-document causal masking, we can see
that IntraDoc achieves the lowest PPL compared to all models trained via
causal masking. This indicates eliminating the potential distracting
information from irrelevant documents during pre-training benefits the
language modelling ability of models. Specifically, we observe that both
Bm25Chunk and IntraDoc obtain significantly lower PPLs on GitHub, where
IntraDoc improves over UniChunk in both the 2K ($-1.3$ PPL) and 8K ($-2.0$)
models. For UniChunk, though we avoided packing web text and code, its
improvement over MixChunk on GitHub is slight. This phenomenon could imply
that _code pre-training is more adversely affected by the distraction of
unrelated context_ , and both intra-document causal masking and retrieval-
based sequence construction strategy can alleviate this issue.

##  4 Experiments on Downstream Tasks

In the following, we evaluate the in-context learning, knowledge memorisation,
and context utilisation abilities of the models.

###  4.1 In-Context Learning

Following Shi et al. (2023), we evaluate in-context learning abilities of the
models using seven text classification datasets, namely SST2 (Socher et al.,
2013), Amazon (Zhang et al., 2015), Yelp (Zhang et al., 2015), DBpedia
(Lehmann et al., 2015), AGNews (Zhang et al., 2015), and TweetEval
hate/offensive tweet detection tasks (Barbieri et al., 2020).

In Table 2, we report the in-context learning accuracy values of the models in
few-shots learning settings, using $20$ and $48$ demonstrations for 2K and 8K
models, respectively. We truncate the input sequences to fit within their
respective context windows. For models pre-trained using causal masking, we
can see that UniChunk produces more accurate results than MixChunk, while
Bm25Chunk yields a higher average accuracy than MixChunk for 2K ($+11.6\%$)
and 8K ($+11.3\%$) models. These results indicate that _increasing relatedness
of the documents in pre-training chunks can improve the in-context learning
abilities of the models_.

$L$ | Model | SST2 | Amazon | DBpedia | AGNews | Yelp | Hate | Offensive | Avg.
---|---|---|---|---|---|---|---|---|---
2K |  MixChunk | $71.53_{\pm 13.8}$ | $81.57_{\pm 15.7}$ | $40.87_{\pm 3.34}$ | $\underline{74.98}_{\pm 0.99}$ | $86.89_{\pm 4.81}$ | $47.10_{\pm 7.51}$ | $41.82_{\pm 20.46}$ | $63.54$
UniChunk | $\underline{77.61}_{\pm 10.05}$ | $\underline{90.88}_{\pm 1.13}$ | $36.61_{\pm 2.15}$ | $70.39_{\pm 2.23}$ | $91.16_{\pm 0.35}$ | $46.20_{\pm 5.67}$ | $42.30_{\pm 14.92}$ | $65.02$
Bm25Chunk | $\textbf{83.73}_{\pm 8.17}$ | $\textbf{90.90}_{\pm 3.20}$ | $\textbf{50.16}_{\pm 2.61}$ | $\textbf{75.98}_{\pm 2.73}$ | $\underline{91.67}_{\pm 3.68}$ | $\underline{48.58}_{\pm 5.26}$ | $\underline{55.36}_{\pm 15.10}$ | 70.91
IntraDoc | $73.65_{\pm 13.61}$ | $84.06_{\pm 12.68}$ | $\underline{46.82}_{\pm 1.82}$ | $72.32_{\pm 2.66}$ | $\textbf{91.91}_{\pm 0.97}$ | $\textbf{55.72}_{\pm 3.47}$ | $\textbf{69.14}_{\pm 5.37}$ | $\underline{70.52}$
8K |  MixChunk | $76.01_{\pm 8.14}$ | $87.32_{\pm 3.08}$ | $45.94_{\pm 3.70}$ | $68.21_{\pm 6.21}$ | $79.06_{\pm 9.99}$ | $42.85_{\pm 1.19}$ | $37.03_{\pm 14.28}$ | $62.43$
UniChunk | $\textbf{81.61}_{\pm 8.63}$ | $88.30_{\pm 2.68}$ | $52.84_{\pm 2.36}$ | $63.16_{\pm 9.25}$ | $83.45_{\pm 6.41}$ | $45.50_{\pm 3.00}$ | $46.84_{\pm 16.78}$ | $65.96$
Bm25Chunk | $\underline{80.87}_{\pm 6.16}$ | $\underline{91.39}_{\pm 1.30}$ | $\underline{56.57}_{\pm 2.33}$ | $\textbf{74.79}_{\pm 2.89}$ | $\underline{85.19}_{\pm 6.93}$ | $\textbf{49.12}_{\pm 5.17}$ | $\underline{48.33}_{\pm 15.88}$ | $\underline{69.47}$
IntraDoc | $72.38_{\pm 3.97}$ | $\textbf{93.25}_{\pm 0.91}$ | $\textbf{61.85}_{\pm 6.89}$ | $\underline{72.49}_{\pm 4.72}$ | $\textbf{92.83}_{\pm 1.38}$ | $\underline{46.20}_{\pm 3.26}$ | $\textbf{59.59}_{\pm 9.88}$ | 71.23

Table 2: In-context learning performance evaluated by text classification
accuracy across seven datasets. Accuracy and deviation (subscript) are
calculated using different sets of demonstrations sampled by $16$ random
seeds.  Figure 2: Average in-context learning accuracy using different numbers
of few-shot demonstrations – the left and right figures show the results of 2K
and 8K models.

In Figure 2, we present the average accuracy using different numbers of few-
shot demonstrations. We observe that Bm25Chunk has an on-par accuracy with
IntraDoc on the 2K setting; however, IntraDoc obtains a significantly higher
accuracy compared to Bm25Chunk on the 8K setting. It may imply that using a
longer context window size can result in increased distractions for causal
masking pre-training; meanwhile, constrained by the performance of the
retrieval method, Bm25Chunk decreases the accuracy on the 8K setting. For 8K
models, MixChunk and UniChunk obtain similar results to their corresponding 2K
models, and they do not improve the accuracy when increasing the number of
demonstrations. It might be due to the similar levels of distraction in both
2K and 8K settings using random packing strategies.

###  4.2 Knowledge Memorisation

$L$ | Model | NQ | TQA | Avg.
---|---|---|---|---
2K | MixChunk | $6.19_{\pm 0.24}$ | $14.47_{\pm 0.75}$ | $10.33$
UniChunk | $6.70_{\pm 0.26}$ | $15.53_{\pm 0.74}$ | $11.12$
Bm25Chunk | $\underline{7.10}_{\pm 0.27}$ | $\underline{15.57}_{\pm 0.65}$ | $\underline{11.34}$
IntraDoc | $\textbf{7.17}_{\pm 0.33}$ | $\textbf{16.04}_{\pm 0.35}$ | 11.60
8K | MixChunk | $5.08_{\pm 0.14}$ | $10.90_{\pm 1.34}$ | $7.99$
UniChunk | $5.25_{\pm 0.37}$ | $10.59_{\pm 1.10}$ | $7.92$
Bm25Chunk | $\underline{5.37}_{\pm 0.43}$ | $\underline{11.09}_{\pm 0.67}$ | $\underline{8.23}$
IntraDoc | $\textbf{6.89}_{\pm 0.08}$ | $\textbf{15.09}_{\pm 0.79}$ | 10.99
Table 3: Exact Match scores on closed-book closed-book QA tasks.

We use two open-domain question-answering (ODQA) datasets, namely
NaturalQuestions (NQ, Kwiatkowski et al., 2019) and TriviaQA (TQA, Joshi et
al., 2017), to evaluate the knowledge memorisation properties of the models.
We use $12$ demonstrations for the 2K models and $48$ demonstrations for the
8K models. In Table 3, we show the mean Exact Match (EM) scores calculated
based on $5$ different sets of demonstrations.

For models trained with causal masking, we can see that _increasing the
relatedness of documents in pre-training chunks can improve the knowledge
memorisation ability of models_. Compared to the baseline MixChunk, Bm25Chunk
obtains $+9.8\%$ and $+3.0\%$ EM improvements on 2K and 8K models,
respectively. We also note that intra-document causal masking significantly
improves the knowledge memorisation ability, especially for 8K models, where
IntraDoc improves EM by $+12.3\%$ and $+37.5\%$ over MixChunk for 2K and 8K
models, respectively. These results support our hypothesis that reducing the
distractions deriving from concatenating multiple, potentially unrelated
documents in pre-training chunks can improve the knowledge memorisation
ability of the models.

###  4.3 Reading Comprehension and Retrieval-Augmented Generation

$L$ | Model | RACE-h | RACE-m | SQuAD | HotpotQA | NQ-open | TQA-open | Avg.
---|---|---|---|---|---|---|---|---
2K |  MixChunk | $32.34_{\pm 0.43}$ | $42.77_{\pm 0.69}$ | $36.70_{\pm 1.79}$ | $7.32_{\pm 1.31}$ | $20.00_{\pm 0.46}$ | $42.72_{\pm 1.37}$ | $30.31$
UniChunk | $\underline{34.01}_{\pm 0.52}$ | $43.52_{\pm 0.44}$ | $37.33_{\pm 2.31}$ | $7.12_{\pm 1.35}$ | $21.16_{\pm 0.96}$ | $42.32_{\pm 1.10}$ | $30.91$
Bm25Chunk | $33.17_{\pm 0.36}$ | $\underline{44.92}_{\pm 0.46}$ | $\underline{37.91}_{\pm 1.84}$ | $\textbf{10.30}_{\pm 0.42}$ | $\textbf{22.10}_{\pm 0.91}$ | $\textbf{46.24}_{\pm 0.63}$ | $\underline{32.42}$
IntraDoc | $\textbf{34.49}_{\pm 0.56}$ | $\textbf{44.96}_{\pm 0.59}$ | $\textbf{39.91}_{\pm 1.48}$ | $\underline{8.29}_{\pm 1.27}$ | $\underline{21.66}_{\pm 0.85}$ | $\underline{45.67}_{\pm 1.02}$ | 32.49
8K |  MixChunk | $31.66_{\pm 0.47}$ | $41.57_{\pm 0.44}$ | $32.79_{\pm 1.56}$ | $10.53_{\pm 0.70}$ | $20.53_{\pm 0.58}$ | $40.53_{\pm 1.03}$ | $29.60$
UniChunk | $31.68_{\pm 0.94}$ | $41.64_{\pm 0.55}$ | $34.94_{\pm 1.84}$ | $10.57_{\pm 1.13}$ | $21.76_{\pm 0.80}$ | $39.60_{\pm 1.77}$ | $30.03$
Bm25Chunk | $\underline{32.63}_{\pm 0.68}$ | $\underline{44.14}_{\pm 0.48}$ | $\underline{39.45}_{\pm 1.05}$ | $\textbf{14.46}_{\pm 0.93}$ | $\underline{22.17}_{\pm 1.02}$ | $\underline{43.40}_{\pm 0.38}$ | 34.54
IntraDoc | $\textbf{33.17}_{\pm 0.37}$ | $\textbf{45.56}_{\pm 0.38}$ | $\textbf{41.32}_{\pm 2.28}$ | $\underline{12.60}_{\pm 1.49}$ | $\textbf{22.25}_{\pm 0.13}$ | $\textbf{44.19}_{\pm 0.60}$ | $\underline{33.18}$

Table 4: Evaluation results of machine reading comprehension and retrieval-
augmented generation tasks.

We evaluate the pre-trained models on a set of reading comprehension tasks,
namely RACE (Lai et al., 2017), SQuAD (Rajpurkar et al., 2016), HotpotQA (Yang
et al., 2018), and the following retrieval-augmented generation (RAG) tasks:
NQ, TQA, and Multi-Document Question-Answering (MDQA, Liu et al., 2023a). For
NQ and TQA, we use the top two passages retrieved by the dense retriever
(Karpukhin et al., 2020; Izacard and Grave, 2021), denoted as NQ-open and TQA-
open. Our results for RACE, SQuAD, and RAG tasks are summarised in Table 4,
while the results on MDQA are available in Figure 3.

We can see that Bm25Chunk produces more accurate results than MixChunk and
UniChunk in all tasks and obtains the best average accuracy, showing that
_increasing the relatedness of documents in pre-training chunks can improve
the context utilisation ability_. Specifically, Bm25Chunk obtains a
significantly better accuracy on multi-hop QA task HotpotQA, showing it can
better utilise multiple relevant information from the context.

IntraDoc obtains the best average accuracy in the 2K models and obtains the
best scores in 5 of 6 tasks in the 8K models. It indicates that eliminating
potential distractions from unrelated documents and _learning each document
independently can improve context utilisation ability_. This finding is
different from the ideas in previous works, which suggested that pre-training
with multiple documents in one context (Shi et al., 2023) and adding
distraction in context during pre-training (Tworkowski et al., 2023) benefit
context utilisation ability.

Figure 3: Accuracy on Multi-Document Question-Answering (MDQA). The $x$-axis
represents the position of the document that contains the answer. The $y$-axis
presents the accuracy for a position.

In MDQA, for each question, there are $30$ documents provided in the context,
where only one of them contains the answer to the question — MDQA is used to
evaluate the ability of models to filter out irrelevant information and
identify the relevant parts of a long context. This task has been used to
analyse the _lost-in-the-middle_ phenomenon in LLMs where they struggle to
retrieve information stored in the middle of long contexts Liu et al. (2023a).
In the following, we analyse how the accuracy of models varies with the
position of relevant information in the context. In these experiments, we
focus on 8K models due to their ability to handle long contexts. The zero-shot
results on MDQA are outlined in Figure 3. We observe that both Bm25Chunk and
IntraDoc tend to produce more accurate predictions than MixChunk and UniChunk
when the relevant passage is located at the beginning or middle of the
context. These results show that Bm25Chunk and IntraDoc _can better filter
irrelevant context and locate relevant information_ ; these results are
further corroborated by our experiments in Section 5.1 where we analyse the
attention distribution of the models during the language modelling process.

(a) The distraction proportion of the _first layer_ ; different documents are
separated by [eos].

(b) The distraction proportion of the _last layer_ ; different documents are
separated by [eos].

(c) The average distraction proportion over layers; different documents are
separated by [eos].

(d) The average distraction proportion over layers; different documents are
separated by "$\backslash\text{n}$"

Figure 4: Distracted attention proportions of models. The $x$-axis presents
the token position of the second document; the $y$-axis presents the
distraction proportion calculated by Equation 2. Figures (a) and (b) show the
distraction proportion of the first and last layers. Figures (c) and (d) are
the average distraction proportion over layers. In Figure (d), we separate
documents by a newline token ("$\backslash\text{n}$") and present the
distraction proportion of IntraDoc. The results are averaged from $4096$
examples. More analysis is presented in Appendix E.

##  5 Discussion and Analysis

###  5.1 Can Models Ignore Irrelevant Contexts Before the End-of-Sequence
Token?

In the following, we analyse whether models can filter irrelevant context
during language modelling by examining the attention score distributions over
the context. Specifically, we concatenate two randomly sampled documents from
the SlimPajama validation set, separate them by an end-of-sequence token
[eos], and check to which extent the attention distributions of the model
focus on the irrelevant document in the sequence. More formally, we define the
_distraction proportion_ of the token in position $p$ in the current document
at layer $l$ as:

$\textsc{DistrProp}(l,p)=\sum_{i=1}^{|C_{d}|}a_{p,i}^{l}$ (2)

where $|C_{d}|$ denotes the number of tokens in the irrelevant document,
$a_{p,i}^{l}$ is the average multi-head attention scores to the $i$-th token
in the irrelevant document $C_{d}$ at layer $l$, and
$\sum_{i=1}^{|C_{d}|+p}a_{p,i}^{l}=1$. In our experiments, we set
$|C_{d}|=256$, and the results are outlined in Figure 4.

We can see that the latter positions have lower distraction proportions but
remain $45\%$-$52\%$ average distraction proportion until the $256$th token of
the second document, as shown in Figure 4(4(c)). We find that models trained
via Bm25Chunk (green line) tend to have lower distraction proportions than
other causal masking models, showing that they can better recognise relevant
information in the context, matching the results in Figure 3. The above
analysis also demonstrates that during the pre-training, causal masking models
can be distracted by unrelated documents in context, and the models can be
more robust to irrelevant contexts when reducing distractions in pre-training
sequences.

Furthermore, in Figure 4(4(d)), we compare IntraDoc and causal masking models
using "$\backslash\text{n}$" as the separator instead of [eos], because [eos]
can only appear at the end of sequences during pre-training using intra-
document causal masking. The results indicate that IntraDoc has the lowest
distraction proportion compared to causal masking models; meanwhile, Bm25Chunk
consistently has a lower distraction proportion than MixChunk and UniChunk
using "$\backslash\text{n}$" as the separator. These results match the finding
in Section 4.3, where IntraDoc and Bm25Chunk can better recognise relevant
information in the context.

###  5.2 Burstiness Property of Sequences

Chan et al. (2022); Han et al. (2023) found a positive correlation between the
model’s in-context learning ability and _burstiness_ property of the training
sequences. Here, burstiness refers to the phenomenon where certain types of
tokens occur in clusters or bursts rather than being uniformly distributed
across all documents. Burstiness is an inherent property of text; for example,
a specific medical term might be frequently used in medical articles and
rarely appear in general texts. Higher burstiness results in a lower Zipf’s
coefficient of token frequency _within a sequence_ (Han et al., 2023).

Following Han et al. (2023), we use Zipf’s coefficient to measure the
burstiness property of pre-training sequences. Formally, let $r$ denote the
rank of a token in a sequence, and $f$ is a frequency function that maps the
rank $r$ to the frequency of that token in the sequence. Then, according to
Zipf’s law, we have that $f(r;\alpha)\propto\frac{1}{r^{\alpha}}$, where
$\alpha\in\mathbb{R}^{+}$ is the Zipf’s coefficient; a lower $\alpha$ presents
an increased burstiness property within the sequence.

In Table 5, we show the Zipf’s coefficients $\alpha$ on different pre-training
sequences. Our results show that, for causal masking approaches that use the
same chunk size, a lower Zipf’s coefficient, which denotes increased
burstiness property, often results in more accurate results. However, IntraDoc
can obtain significantly better results than UniChunk with the same Zipf’s
coefficient. The above results indicate that, for causal masking approaches,
_the correlation between higher burstiness and better performance could derive
from reduced distractions in pre-training chunks_. We report additional
evidence for the burstiness property in Appendix D.

Note that duplication in pre-training sequences can also result in increased
burstiness property, which may negatively impact the performance of language
models. We analyse the distinct n-gram phrases of pre-training sequences in
Appendix D and will investigate the impact of duplication using different pre-
training corpora in future work.

$L$ | Method |  Zipf’s Coeffeicient ($\alpha$) |  In-Context Learning (Acc.) |  Knowledge Memorisation (EM)
---|---|---|---|---
2K |  MixChunk | $2.122$ | $63.54$ | $10.33$
UniChunk | $2.119$ | $65.02$ | $11.12$
Bm25Chunk | $2.107$ | $70.91$ | $11.34$
8K |  MixChunk | $1.976$ | $62.43$ | $7.99$
UniChunk | $1.951$ | $65.96$ | $7.92$
Bm25Chunk | $1.925$ | $69.47$ | $8.23$
2K |  IntraDoc | $2.119$ | $70.52$ | $11.60$
8K |  IntraDoc | $1.952$ | $71.23$ | $10.99$

Table 5: Zipf’s coefficients of token frequency in different data. In-context
learning and knowledge memorisation abilities are evaluated in Section 4.

##  6 Related Works

#### Instance-Level Pre-training Data Composition

GPT-3 (Brown et al., 2020) was pre-trained by packed documents with causal
masking, with the idea that not adopting any dynamic masking can improve pre-
training efficiency. Current open-source pre-training frameworks, such as
MegatronLM (Shoeybi et al., 2019), fairseq (Ott et al., 2019), EasyLM (Geng,
2023), LLM360 (Liu et al., 2023b), also follow this strategy for pre-training.
In Levine et al. (2022), authors pair similar sentences within the same
sequence, while Gu et al. (2023) propose packing documents that contain
similar intrinsic tasks for continual pre-training, improving the in-context
learning ability of models. Recently, Shi et al. (2023) emphasise that packing
relevant documents can enhance language models’ in-context learning and
context utilisation; however, our findings indicate that packing documents can
adversely affect performance, and learning each document independently using
intra-document causal masking can reduce the distraction and improve the
performance.

#### Distribution Properties of Pre-Training Data

Chan et al. (2022) shows several data distribution properties can drive in-
context learning ability, e.g., large numbers of long-tail classes, dynamic
meanings of inputs, and Zipf’s distribution of class frequency. Han et al.
(2023) used a gradient-guided method to select small-scale data for continual
pre-training, showing data exhibiting burstiness properties can enhance in-
context learning performance.

#### Pre-training Data Quality

Gunasekar et al. (2023) selected high-quality data to pre-train a small-size
coding model, achieving comparable performance with larger models. Shin et al.
(2022); Gao et al. (2021) emphasised the importance of pre-training data
diversity. Lee et al. (2022); Tirumala et al. (2023); Soboleva et al. (2023);
Abbas et al. (2023) showed the importance of data de-duplication on models’
generalisation. In our work, we use a diverse and high-quality pre-training
dataset, namely SlimPajama (Soboleva et al., 2023), to highlight the
importance of the sequence composition strategy on language model pre-
training.

##  7 Conclusion

In this work, we investigate the impact of pre-training sequence composition
by pre-training models from scratch. First, we find causal masking can result
in unrelated documents distracting language modelling pre-training and hurting
the performance on downstream tasks; we show that intra-document causal
masking can significantly improve the performance while decreasing the pre-
training efficiency. Second, we find improving the relatedness of documents in
pre-training chunks for causal masking pre-training can reduce some potential
distractions in chunks; our proposed efficient retrieval-based packing method
Bm25Chunk can significantly improve the performance of language models without
reducing pre-training efficiency.

## Limitations

#### Efficiency of Intra-Document Causal Masking

We show that intra-document causal masking is an effective method to improve
the performance while decreasing the pre-training efficiency. We use
FlashAttention2 (Dao, 2023) to implement intra-document causal masking masking
without sacrificing too much efficiency (discussed in Appendix A). Still, we
do not propose a method to solve this efficiency issue completely.

#### Objective of Sequences Construction.

We discuss sequence construction methods, showing the importance of sequence
compositions on the performance of models, but these methods lack an objective
during sequence construction. Since specific data distribution properties may
be related to models’ performance, we will explore using indicators of
distributional properties to guide sequence construction in future works.

#### Scaling The Size of Language Models.

Limited by the computation resources, we cannot conduct experiments on larger
models with more pre-training steps, and different results might be drawn when
increasing the models at a specific scale. However, this work could be
directly valuable for investigating pre-training relatively small models that
aim at facilitating the use of language models under resource-constrained
conditions.

## Acknowledgements

PM was partially funded by ELIAI (The Edinburgh Laboratory for Integrated
Artificial Intelligence), EPSRC (grant no. EP/W002876/1), an industry grant
from Cisco, and a donation from Accenture LLP; and is grateful to NVIDIA for
the GPU donations. This work was supported by the Edinburgh International Data
Facility (EIDF) and the Data-Driven Innovation Programme at the University of
Edinburgh. The authors extend their gratitude to Xiaomi AI Lab for their GPU
donations and assistance; as well as to Tri Dao, Piotr Nawrot, Giwon Hong,
Xiaotang Du, and Aryo Gema for their help and feedback.

## References

  * Abbas et al. (2023) Amro Abbas, Kushal Tirumala, Daniel Simig, Surya Ganguli, and Ari S. Morcos. 2023.  Semdedup: Data-efficient learning at web-scale through semantic deduplication.  _CoRR_ , abs/2303.09540.
  * Barbieri et al. (2020) Francesco Barbieri, José Camacho-Collados, Luis Espinosa Anke, and Leonardo Neves. 2020.  Tweeteval: Unified benchmark and comparative evaluation for tweet classification.  In _Findings of the Association for Computational Linguistics: EMNLP 2020, Online Event, 16-20 November 2020_ , volume EMNLP 2020 of _Findings of ACL_ , pages 1644–1650. Association for Computational Linguistics.
  * Biderman et al. (2023) Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal. 2023.  Pythia: A suite for analyzing large language models across training and scaling.  _CoRR_ , abs/2304.01373.
  * Brown et al. (2020) 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. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_.
  * Chan et al. (2022) Stephanie Chan, Adam Santoro, Andrew K. Lampinen, Jane Wang, Aaditya Singh, Pierre H. Richemond, James L. McClelland, and Felix Hill. 2022.  Data distributional properties drive emergent in-context learning in transformers.  In _NeurIPS_.
  * Dao (2023) Tri Dao. 2023.  Flashattention-2: Faster attention with better parallelism and work partitioning.  _CoRR_ , abs/2307.08691.
  * Gao et al. (2021) Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. 2021.  The pile: An 800gb dataset of diverse text for language modeling.  _CoRR_ , abs/2101.00027.
  * Geng (2023) Xinyang Geng. 2023.  Easylm: A simple and scalable training framework for large language models.
  * Gu et al. (2023) Yuxian Gu, Li Dong, Furu Wei, and Minlie Huang. 2023.  Pre-training to learn in context.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2023, Toronto, Canada, July 9-14, 2023_ , pages 4849–4870. Association for Computational Linguistics.
  * Gunasekar et al. (2023) Suriya Gunasekar, Yi Zhang, Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi, Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, Adil Salim, Shital Shah, Harkirat Singh Behl, Xin Wang, Sébastien Bubeck, Ronen Eldan, Adam Tauman Kalai, Yin Tat Lee, and Yuanzhi Li. 2023.  Textbooks are all you need.  _CoRR_ , abs/2306.11644.
  * Han et al. (2023) Xiaochuang Han, Daniel Simig, Todor Mihaylov, Yulia Tsvetkov, Asli Celikyilmaz, and Tianlu Wang. 2023.  Understanding in-context learning via supportive pretraining data.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2023, Toronto, Canada, July 9-14, 2023_ , pages 12660–12673. Association for Computational Linguistics.
  * Hoffmann et al. (2022) Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. 2022.  Training compute-optimal large language models.  _CoRR_ , abs/2203.15556.
  * Izacard et al. (2022) Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. 2022.  Unsupervised dense information retrieval with contrastive learning.  _Trans. Mach. Learn. Res._ , 2022.
  * Izacard and Grave (2021) Gautier Izacard and Edouard Grave. 2021.  Leveraging passage retrieval with generative models for open domain question answering.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, EACL 2021, Online, April 19 - 23, 2021_ , pages 874–880. Association for Computational Linguistics.
  * Jiang et al. (2023) Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019.  Billion-scale similarity search with GPUs.  _IEEE Transactions on Big Data_ , 7(3):535–547.
  * Joshi et al. (2017) Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer. 2017.  TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1601–1611, Vancouver, Canada. Association for Computational Linguistics.
  * Kaddour (2023) Jean Kaddour. 2023.  The minipile challenge for data-efficient language models.  _CoRR_ , abs/2304.08442.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6769–6781, Online. Association for Computational Linguistics.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019.  Natural questions: A benchmark for question answering research.  _Transactions of the Association for Computational Linguistics_ , 7:452–466.
  * Lai et al. (2017) Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard H. Hovy. 2017.  RACE: large-scale reading comprehension dataset from examinations.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017, Copenhagen, Denmark, September 9-11, 2017_ , pages 785–794. Association for Computational Linguistics.
  * Lee et al. (2022) Katherine Lee, Daphne Ippolito, Andrew Nystrom, Chiyuan Zhang, Douglas Eck, Chris Callison-Burch, and Nicholas Carlini. 2022.  Deduplicating training data makes language models better.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022, Dublin, Ireland, May 22-27, 2022_ , pages 8424–8445. Association for Computational Linguistics.
  * Lefaudeux et al. (2022) Benjamin Lefaudeux, Francisco Massa, Diana Liskovich, Wenhan Xiong, Vittorio Caggiano, Sean Naren, Min Xu, Jieru Hu, Marta Tintore, Susan Zhang, Patrick Labatut, and Daniel Haziza. 2022.  xformers: A modular and hackable transformer modelling library.  https://github.com/facebookresearch/xformers.
  * Lehmann et al. (2015) Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. 2015.  Dbpedia - A large-scale, multilingual knowledge base extracted from wikipedia.  _Semantic Web_ , 6(2):167–195.
  * Levine et al. (2022) Yoav Levine, Noam Wies, Daniel Jannai, Dan Navon, Yedid Hoshen, and Amnon Shashua. 2022.  The inductive bias of in-context learning: Rethinking pretraining example design.  In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.
  * Liu et al. (2023a) Nelson F. Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. 2023a.  Lost in the middle: How language models use long contexts.
  * Liu et al. (2023b) Zhengzhong Liu, Aurick Qiao, Willie Neiswanger, Hongyi Wang, Bowen Tan, Tianhua Tao, Junbo Li, Yuqi Wang, Suqi Sun, Omkar Pangarkar, et al. 2023b.  Llm360: Towards fully transparent open-source llms.  _arXiv preprint arXiv:2312.06550_.
  * Ott et al. (2019) Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019.  fairseq: A fast, extensible toolkit for sequence modeling.  In _Proceedings of NAACL-HLT 2019: Demonstrations_.
  * Pagliardini et al. (2023) Matteo Pagliardini, Daniele Paliotta, Martin Jaggi, and François Fleuret. 2023.  Faster causal attention over large sequences through sparse flash attention.  _CoRR_ , abs/2306.01160.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100, 000+ questions for machine comprehension of text.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016_ , pages 2383–2392. The Association for Computational Linguistics.
  * Shi et al. (2023) Weijia Shi, Sewon Min, Maria Lomeli, Chunting Zhou, Margaret Li, Victoria Lin, Noah A Smith, Luke Zettlemoyer, Scott Yih, and Mike Lewis. 2023.  In-context pretraining: Language modeling beyond document boundaries.  _arXiv preprint arXiv:2310.10638_.
  * Shin et al. (2022) Seongjin Shin, Sang-Woo Lee, Hwijeen Ahn, Sungdong Kim, HyoungSeok Kim, Boseop Kim, Kyunghyun Cho, Gichang Lee, Woo-Myoung Park, Jung-Woo Ha, and Nako Sung. 2022.  On the effect of pretraining corpora on in-context learning by a large-scale language model.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022_ , pages 5168–5186. Association for Computational Linguistics.
  * Shoeybi et al. (2019) Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. 2019.  Megatron-lm: Training multi-billion parameter language models using model parallelism.  _CoRR_ , abs/1909.08053.
  * Soboleva et al. (2023) Daria Soboleva, Faisal Al-Khateeb, Robert Myers, Jacob R Steeves, Joel Hestness, and Nolan Dey. 2023.  SlimPajama: A 627B token cleaned and deduplicated version of RedPajama.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. 2013.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, EMNLP 2013, 18-21 October 2013, Grand Hyatt Seattle, Seattle, Washington, USA, A meeting of SIGDAT, a Special Interest Group of the ACL_ , pages 1631–1642. ACL.
  * Tirumala et al. (2023) Kushal Tirumala, Daniel Simig, Armen Aghajanyan, and Ari S. Morcos. 2023.  D4: improving LLM pretraining via document de-duplication and diversification.  _CoRR_ , abs/2308.12284.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023.  Llama: Open and efficient foundation language models.  _CoRR_ , abs/2302.13971.
  * Tworkowski et al. (2023) Szymon Tworkowski, Konrad Staniszewski, Mikolaj Pacek, Yuhuai Wu, Henryk Michalewski, and Piotr Milos. 2023.  Focused transformer: Contrastive training for context scaling.  _CoRR_ , abs/2307.03170.
  * Xie et al. (2023) Sang Michael Xie, Hieu Pham, Xuanyi Dong, Nan Du, Hanxiao Liu, Yifeng Lu, Percy Liang, Quoc V. Le, Tengyu Ma, and Adams Wei Yu. 2023.  Doremi: Optimizing data mixtures speeds up language model pretraining.  _CoRR_ , abs/2305.10429.
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018.  Hotpotqa: A dataset for diverse, explainable multi-hop question answering.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018_ , pages 2369–2380. Association for Computational Linguistics.
  * Zhang et al. (2024) Peiyuan Zhang, Guangtao Zeng, Tianduo Wang, and Wei Lu. 2024.  Tinyllama: An open-source small language model.  _arXiv preprint arXiv:2401.02385_.
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona T. Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. 2022.  OPT: open pre-trained transformer language models.  _CoRR_ , abs/2205.01068.
  * Zhang et al. (2015) Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. 2015.  Character-level convolutional networks for text classification.  In _Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_ , pages 649–657.

##  Appendix A Implementation of Intra-Document Masking

We use FlashAttention2 (Dao, 2023) to implement intra-document causal masking.
The pseudo-code is presented as follows:

Pseudo-code for intra-document causal masking

⬇

# qkv_states: query, key and value

# max_seqlen: max length of documents

# cu_seqlens: boundaries of documents

qkv_states = qkv_project(hidden_states)

qkv_states = qkv_states.view(batch_size, seq_len, 3, num_heads, head_dim)

qkv_states = rotary_embed(qkv_states)

qkv_states = qkv_states.view(batch_size * seq_len, 3, num_heads, head_dim)

attn = flash_attn_var_len_qkvpacked_func(qkv_states, cu_seqlens, max_seqlen,
causal=True)

attn = attn.view(batch_size, seq_len, num_heads * head_dim)

attn = output_project(attn)

In this implementation of intra-document causal masking, we first apply the
rotary position embedding to the hidden states, ensuring IntraDoc uses the
same position information that is used in causal masking for each document.

We observe a $4\%$ pre-training speed decrease in our implementation compared
to causal masking pre-training, testing on 128 80G A100 GPUs. Another choice
to implement intra-document causal masking is using a binary attention bias
matrix for masking tokens that belong to other documents. Compared to causal
masking using FlashAttention2, we observe that it reduces efficiency by $32\%$
in xFormers (Lefaudeux et al., 2022) when applying the attention bias;
besides, it reduces efficiency by $52\%$ using the standard PyTorch
implementation.

##  Appendix B Pre-Training Details

#### Hyperparameters

In our experiments, we use the $1.3$B model, which has $24$ layers, a hidden
size of $2048$, and $16$ attention heads. We use a batch size of $4$ million
tokens for both the models with 2K and 8K context window sizes and pre-train
models using $150$B tokens with $38400$ steps, which costs $40$ hours to pre-
training a causal masking model using 128 80G A100 GPUs. We use Adam optimiser
with $\beta_{1}=0.90$, $\beta_{2}=0.95$, a weight decay of $0.1$, and a cosine
learning rate scheduler. The peak learning rate is $3\times 10^{-4}$,
decreasing to $3\times 10^{-5}$ at the end.

#### Pre-Training Corpus

We sample documents with $150$B tokens sampled from SlimPajama for pre-
training. All models are pre-trained using the same set of documents. In Table
6, we present the number of documents and the token proportions for each
subset.

Subset |  `#` documents | Token proportion
---|---|---
CommonCrawl | $42960927$ | $52.2\%$
C4 | $76520211$ | $26.7\%$
GitHub | 5233374 | $5.2\%$
Books | 47848 | $4.2\%$
ArXiv | 383058 | $4.6\%$
Wikipedia | 7044397 | $3.8\%$
StackExchange | 7265708 | $3.3\%$
Table 6: Pre-training corpus.

##  Appendix C Analysis of BM25Chunk

###  C.1 Time Complexity Analysis

In BM25, the similarity score between a query and a document is based on
sparse representations, where each query and document is represented by the
terms it contains; such sparse representations are stored in _inverted
indices_ , which map terms to the documents that contain them, along with
necessary statistics such as the term frequency and the document frequency.
The time complexity of computing similarities between a query and documents in
BM25 using an inverted index is $\mathcal{O}(Q\times K)$, where $Q$ denotes
the number of tokens in the query, and $K$ represents the number of total
documents.

To improve efficiency, we restrict Bm25Chunk’s retrieval process within a
document buffer rather than entire large-scale corpora. The buffer caches $k$
documents, which enables similarity calculations between a term and documents
to be at most $k$ times. Since each query is a document, it could contain a
large number of tokens; we remove the stop words and randomly sample $q$
tokens to reduce the length. Therefore, the time complexity of sequence
construction in Bm25Chunk is reduced to $O(q\times k)$. In Figure 5, we test
the sequence construction speed using different $q$ and $k$.

###  C.2 Implementation Details

We randomly group documents in batches of 5000K and build indexes within each
group. The BM25 indexes of pre-training corpora with $150$B tokens require
$244$GB storage memory. For both 2K and 8K settings, the document buffer size
$k$ is $3072$, and the maximum length of query $q$ is $500$. The data
construction speed is $50.0$K tokens per second using $16$ CPU cores, and
speeds using different settings are presented in Figure 5.

Figure 5: Pre-training sequence construction speeds using different buffer
sizes $k$ and maximum query lengths $q$. Test on $16$ CPU cores.

###  C.3 Ablation Studies

#### Effectiveness of Document Buffer

Bm25Chunk conducts retrieval within a document buffer, which may result in
retrieving less relevant documents, so we conduct experiments on different
document buffer sizes to investigate its effectiveness. We conduct ablation
experiments using $0.3$B models with a context window of $2048$, trained with
13B tokens, the compute-optimal number of tokens according to Hoffmann et al.
(2022). We present the PPL improvement over UniChunk on the validation set of
SlimPajama in Table 7. The results show that retrieving from different sizes
of document buffers can improve PPL, indicating the effectiveness of
retrieving from a small-scale document set. Bm25Chunk with a buffer size of
$4096$ achieves the best result, while increasing the size to $8192$ does not
improve the PPL.

Model (0.3B) |  Document Buffer Size | Valid. PPL
---|---|---
MixChunk | - | $15.474$
IntraDoc | - | $12.443_{\downarrow 3.031}$
Bm25Chunk | 2048 | $13.657_{\downarrow 1.817}$
4096 | $\textbf{12.528}_{\downarrow 2.946}$
8192 | $12.684_{\downarrow 2.790}$
Bm25Chunk |  |
w/o multi-hop retrieval | 4096 | $13.497_{\downarrow 1.977}$
w/o retrieval | 4096 | $14.241_{\downarrow 1.233}$
ContrieverChunk | - | $13.720_{\downarrow 1.654}$

Table 7: PPL on the validation set of SlimPajama. Subscript↓ is the PPL
improvement over MixChunk. The label “w/o multi-hop retrieval” means
retrieving multiple documents at once to construct the sequence; “w/o
retrieval” represents random sampling from document buffers, which is
equivalent to UniChunk.

#### Effectiveness of Retrieval

Bm25Chunk conducts multi-hop retrieval to retrieve a sequence of documents,
which could potentially help models learn long-distance relationships across
documents, and this benefit has been revealed by its high accuracy on
HotpotQA, a multi-hop QA task, as shown in Section 4.3. An alternative choice
is retrieving multiple documents at once to fill a pre-training chunk, and we
present such one-hop retrieval in Table 7. The result indicates that Bm25Chunk
with multi-hop retrieval can improve the PPL more effectively. Besides, we
experiment with random sampling documents from the buffers without retrieval;
the result shows the effectiveness of retrieval.

#### Dense Retrieval Method

An alternative retrieval method to BM25 is dense retrieval. We use Contreiver
(Izacard et al., 2022) as the dense retriever and compare it with BM25.
Following Shi et al. (2023), we embed pre-training documents to dense vectors
using Contriever and use FAISS (Johnson et al., 2019) to accelerate the
retrieval process instead of using the document buffer. Then, we construct
pre-training chunks using the same process introduced in Bm25Chunk. We present
the result produced by the dense retrieval method in the last line of Table 7.
We observe that the improvement of the dense retrieval method is less than
BM25.

##  Appendix D Analysis of Data Distribution Properties

Figure 6:  Chunk frequency. The $x$-axis indicates the frequency rank of
tokens; the $y$-axis presents the number of chunks containing a specific
token.

#### Chunk Frequency

In addition to Zipf’s coefficient, we analyse the burstiness property through
the chunk frequency of tokens. Specifically, chunk frequency refers to the
number of chunks where a specific token appears. Given a corpus, if a specific
token appears in fewer chunks, it indicates more concentrated occurrences in
chunks containing the token, demonstrating a higher burstiness property. In
Figure 6, we can see that low-frequency tokens appear in fewer chunks in
Bm25Chunk compared to MixChunk and UniChunk, indicating these low-frequency
tokens are gathered through the retrieval-based construction method.

#### Distinct N-gram

The burstiness property can correlate to the duplication in a sequence, which
may negatively affect models, e.g., models may tend to copy phrases from
context. We use SlimPajama, a high-quality and deduplicated dataset, as the
pre-training corpus, which can alleviate the duplication issue in Bm25Chunk.
We use the percentage of distinct n-grams within a sequence to analyse the
duplication issue, as shown in Table 10. The results show that, with
Bm25Chunk, pre-training sequences contain a lower percentage of distinct
n-grams than MixChunk and UniChunk.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 7:  Average distraction proportions over layers. We compare results using different corpora (Wikipedia and GitHub), distraction length ($|C_{d}|=256$ and $512$), and the separator [eos] and $\backslash\text{n}$). The first row, (a) (b) (c) and (d), use [eos] as the separator; the second row, (e) (f) (g) and (h), use $\backslash\text{n}$. The first and the third columns, (a) (c) (e) and (g), have an irrelevant context length $|C_{d}|$ of $256$, and the others are $512$. The first two columns, (a) (b) (e) and (f), present the results of Wikipedia, and the last two columns, (c) (d) (g) and (h), present the results of GitHub. We present the baseline $y=|C_{d}|/(|C_{d}|+x)$ whose attention scores are uniformly distributed over all preceding tokens.  Method |  $\Delta$ PPL $\%$ |  $\Delta$ DistProp $\%$
---|---|---
MixChunk | $14.6\%$ | $3.4\%$
UniChunk | $15.3\%$ | $4.6\%$
Bm25Chunk | $13.5\%$ | $4.6\%$
IntraDoc | $-0.7\%$ | $-0.6\%$
Table 8: The PPL and DistProp changes after replacing the separator [eos] by
$\backslash\text{n}$. A positive value means PPL or DistProp increases
(performance drops).

##  Appendix E Analysis of Distraction Proportions in Different Settings

In Figure 7, we report the average distraction proportion (defined in Equation
2) over layers using different settings. Specifically, we analyse distraction
proportions in different settings by varying the 1) modalities of corpus: text
and code using Wikipedia and GitHub; 2) the separator token: [eos] and line
break token $\backslash\text{n}$; 3) the length of distraction context,
$|C_{d}|=256$ and $512$.

Comparing different separators [eos] and $\backslash\text{n}$, (a) (e), (b)
(f), (c) (g), and (d) (h), we observe that causal masking models can obtain
lower distraction proportions using [eos], indicating causal masking models
can benefit from [eos] to ignore irrelevant context during pre-training. We
present the impact of changing the separator from [eos] to
$\backslash\text{n}$ on PPL and distraction proportion in Table 8. The results
show that PPL and DistProp increase after the replacement for causal masking
models, while IntraDoc obtains better results using $\backslash\text{n}$ as
the separator since it does not train on sequences where documents are
separated by [eos] using intra-document causal masking.

Comparing Wikipedia (a) (b) (e) (f) and GitHub (c) (d) (g) (h), MixChunk is
more distracted by the irrelevant context in code generation.

Comparing different length distraction contexts, (a) (b), (c) (d), (e) (f) and
(g) (h), models are more distracted when $|C_{d}|$ increases, while much
better than the baseline of uniform distribution $y=|C_{d}|/(|C_{d}|+x)$.

Comparing IntraDoc (red line) and causal masking models, we observe that
intra-document causal masking results in significantly lower distraction
proportions in all cases. This phenomenon may imply that using causal masking
without considering the boundaries of documents negatively impacts language
modelling performance, and the models can be more robust to irrelevant
contexts when increasing the relatedness of documents in pre-training chunks.

##  Appendix F Next Token Accuracy of Pre-Trained Language Models

$L$ | Model | CommonCrawl | C4 | Wikipedia | GitHub | StackExchange | Book | ArXiv | Avg.
---|---|---|---|---|---|---|---|---|---
2K |  MixChunk | $0.5429$ | $0.4950$ | $0.6238$ | $0.7665$ | $0.5974$ | $0.5001$ | $0.6406$ | $0.5952$
UniChunk | $0.5468$ | $0.4984$ | $0.6298$ | $0.7709$ | $0.6011$ | $0.5033$ | $0.6436$ | $0.5991$
Bm25Chunk | $\underline{0.5496}$ | $\underline{0.5021}$ | $\underline{0.6394}$ | $\underline{0.7782}$ | $\underline{0.6041}$ | $\underline{0.5050}$ | $\underline{0.6452}$ | $\underline{0.6034}$
IntraDoc | 0.5507 | 0.5048 | 0.6426 | 0.7793 | 0.6050 | 0.5062 | 0.6458 | 0.6049
8K |  MixChunk | $0.5402$ | $0.4867$ | $0.6219$ | $0.7443$ | $0.5820$ | $0.5042$ | $0.6531$ | $0.5903$
UniChunk | $0.5429$ | $0.4888$ | $0.6235$ | $0.7483$ | $0.5859$ | $0.5065$ | $0.6564$ | $0.5932$
Bm25Chunk | $\underline{0.5489}$ | $\underline{0.4952}$ | $\underline{0.6391}$ | $\underline{0.7621}$ | $\underline{0.5919}$ | $\underline{0.5108}$ | 0.6599 | $\underline{0.6011}$
IntraDoc | 0.5506 | 0.4988 | 0.6443 | 0.7643 | 0.5936 | 0.5119 | $\underline{0.6597}$ | 0.6033

Table 9: Evaluation of next token accuracy on SlimPajama’s test set.

In addition to PPL, we report the next token accuracy of pre-trained language
models in Table 9.

$L$ | Method |  Distinct 2-gram $\%$ |  Distinct 3-gram $\%$ |  Distinct 4-gram $\%$
---|---|---|---|---
2K |  MixChunk | $71.84_{\pm 14.68}$ | $84.06_{\pm 14.47}$ | $89.02_{\pm 13.16}$
UniChunk | $71.84_{\pm 15.07}$ | $84.17_{\pm 14.74}$ | $89.16_{\pm 13.26}$
Bm25Chunk | $71.49_{\pm 15.21}$ | $84.00_{\pm 14.91}$ | $89.07_{\pm 13.41}$
IntraDoc | $80.35_{\pm 15.26}$ | $89.01_{\pm 13.07}$ | $92.61_{\pm 11.34}$
8K |  MixChunk | $64.81_{\pm 12.84}$ | $80.61_{\pm 13.69}$ | $86.76_{\pm 12.76}$
UniChunk | $64.57_{\pm 14.09}$ | $80.61_{\pm 14.92}$ | $86.88_{\pm 13.64}$
Bm25Chunk | $63.49_{\pm 14.63}$ | $80.06_{\pm 15.64}$ | $86.56_{\pm 14.31}$
IntraDoc | $79.88_{\pm 14.86}$ | $88.90_{\pm 12.63}$ | $92.61_{\pm 10.96}$

Table 10: The percentages of the distinct n-grams in different pre-training
sequences.


# Iterative Calculation of Characteristic Modes Using Arbitrary Full-wave
Solvers

Johan Lundgren, , Kurt Schab, , Miloslav Capek, ,
Mats Gustafsson, , and Lukas Jelinek Manuscript received ; revised . This work
was supported by the Czech Science Foundation under project No. 21-19025M and
the Swedish Research Council (2017-04656).J. Lundgren and M. Gustafsson are
with Lund University, Lund, Sweden, (e-mails: {johan.lundgren,
mats.gustafsson}@eit.lth.se).K. Schab is with Santa Clara University, Santa
Clara, USA (e-mail: kschab@scu.edu).M. Capek and L. Jelinek are with Czech
Technical University in Prague, Czech Republic (e-mails:
{miloslav.capek,lukas.jelinek}@fel.cvut.cz).

###### Abstract

An iterative algorithm is adopted to construct approximate representations of
matrices describing the scattering properties of arbitrary objects. The method
is based on the implicit evaluation of scattering responses from iteratively
generated excitations. The method does not require explicit knowledge of any
system matrices (e.g., stiffness or impedance matrices) and is well-suited for
use with matrix-free and iterative full-wave solvers, such as FDTD, FEM, and
MLFMA. The proposed method allows for significant speed-up compared to the
direct construction of a full transition matrix or scattering dyadic. The
method is applied to the characteristic mode decomposition of arbitrarily
shaped obstacles of arbitrary material distribution. Examples demonstrating
the speed-up and complexity of the algorithm are studied with several
commercial software packages.

###### Index Terms:

Antenna theory, eigenvalues and eigenfunctions, computational
electromagnetics, characteristic modes, scattering.

##  I Introduction

Characteristic mode analysis centers on the decomposition of the scattering
properties of arbitrary structures into a basis with convenient properties,
see [1, 2, 3, 4, 5] for a detailed review. While characteristic mode analysis
is commonly associated with the study of perfectly conducting objects using
the method of moments [6], characteristic modes of arbitrary structures can be
calculated using any full-wave solver using scattering-based formulations [7,
8, 9]. This approach involves only the forward solution of a series of
scattering problems to construct matrices that describe the scattering
properties of the system under study.

An object’s transition matrix [10, §7.8] or its scattering dyadic [10, §7.8.1]
can be constructed using a series of simulations carried out by any full-wave
solver capable of determining scattered fields due to a known excitation. A
simple approach to this procedure (discussed in [7] and [9]), involves a
number of full-wave solutions coinciding with the selected dimension of the
transition matrix or scattering dyadic representation. For large problems
necessitating matrix-free methods (e.g., iterative FEM solvers, FMM, and
FDTD), [11, Ch. 11], the cost of performing each of these full-wave
simulations is typically far higher than the cost of decomposing the final
transition matrix or matrix representation of the scattering dyadic.

In this work, we consider an iterative algorithm for efficiently estimating
the complete transition matrix or scattering dyadic of arbitrary scatterers.
This method yields characteristic modes without explicit knowledge of any
matrices used within a particular numerical method. The proposed technique
represents a matrix-free method for computing characteristic modes in an
arbitrary full-wave solver. Additionally, the algorithm readily allows for
calculating all characteristic modes with modal significance above a
predefined threshold, which may be favorable over algorithms producing a fixed
number of modes in decreasing order of modal significance.

##  II Transition Matrix and Scattering Dyadic

Consider an obstacle $\varOmega$ illuminated by an incident field
$\boldsymbol{E}_{\mathrm{i}}$ and producing a scattered field
$\boldsymbol{E}_{\mathrm{s}}$. The transformation between incident and
scattered fields can be described by matrices by projecting both onto wave-
specific bases. Utilizing regular (Bessel) and outgoing (Hankel) spherical
vector waves to represent the incident and scattered field, the scattering
problem is completely defined by the transition matrix $\mathbf{T}$ [10]

$\mathbf{T}\mathbf{a}=\mathbf{f},$ (1)

where $\mathbf{a}$ and $\mathbf{f}$ are collections of spherical vector wave
expansion coefficients for the incident and scattered field, respectively.
Alternatively, if the incident field is described by a spectrum of plane waves

$\boldsymbol{E}_{\mathrm{i}}(\boldsymbol{r})=\int_{4\pi}\boldsymbol{E}(\hat{\boldsymbol{r}}^{\prime})\mathrm{e}^{-\mathrm{j}k\hat{\boldsymbol{r}}^{\prime}\cdot\boldsymbol{r}}\,\mathrm{d}\Omega^{\prime}$
(2)

and the scattered field is studied in terms of the far-field $\boldsymbol{F}$
defined as

$\boldsymbol{F}(\hat{\boldsymbol{r}})=\lim_{r\rightarrow\infty}\boldsymbol{E}_{\mathrm{s}}(\boldsymbol{r})r\mathrm{e}^{\mathrm{j}kr},$
(3)

then the scattering problem is completely described by the scattering dyadic
$\boldsymbol{S}$ as [10]

$\frac{4\pi\mathrm{j}}{k}\int_{4\pi}\boldsymbol{S}(\hat{\boldsymbol{r}},\hat{\boldsymbol{r}}^{\prime})\cdot\boldsymbol{E}(\hat{\boldsymbol{r}}^{\prime})\,\mathrm{d}\Omega^{\prime}=\boldsymbol{F}(\hat{\boldsymbol{r}}).$
(4)

Here $k$ is the background wave number, $\mathrm{j}^{2}=-1$,
$\hat{\boldsymbol{r}}=\boldsymbol{r}/r$, and $r=|\boldsymbol{r}|$. Applying a
quadrature rule to approximate the above integral transforms the scattering
dyadic description of the problem into matrix form, see [9].

##  III Scattering-based Characteristic Mode Decomposition

Characteristic modes are fields or currents excited by characteristic
excitations which are solutions to an eigenvalue problem involving either the
transition matrix or scattering dyadic [7, 9]. In the case when spherical
vector waves are used, characteristic excitations are given by expansion
coefficient vectors $\mathbf{a}_{n}$ satisfying [7]

$\mathbf{T}\mathbf{a}_{n}=t_{n}\mathbf{a}_{n},$ (5)

while in the case of a plane-wave basis, characteristic excitations are the
plane-wave spectra $\boldsymbol{E}_{n}$ computed from [9]

$\int\limits_{4\pi}\boldsymbol{S}(\hat{\boldsymbol{r}},\hat{\boldsymbol{r}}^{\prime})\cdot\boldsymbol{E}_{n}(\hat{\boldsymbol{r}}^{\prime})\,\mathrm{d}\varOmega^{\prime}=t_{n}\boldsymbol{E}_{n}(\hat{\boldsymbol{r}}).$
(6)

Note that, by the definitions of the transition matrix (1) and scattering
dyadic (4), the eigenvectors of either of the above eigenvalue problems are
simultaneously representations of both incident and scattered fields, i.e.,
both instances of $\mathbf{a}_{n}$ may be replaced by $\mathbf{f}_{n}$ in (5)
and both instances of $\boldsymbol{E}_{n}$ may be replaced by
$\boldsymbol{F}_{n}$ in (6). Additionally, the characteristic excitations
$\mathbf{a}_{n}$ or $\boldsymbol{E}_{n}$ may be applied to reconstruct modal
current densities and other modal quantities [8, 9]. The scattering-based
characteristic mode problem in (6) is equivalent to impedance-based problem
for lossless structures, with explicit algebraic links between the two
approaches available for many common integral equation formulations [7].
Characteristic mode eigenvalues of impedance-based formulations, commonly
denoted as $\lambda_{n}$ [2], are related to those of the scattering-based
formulation via [7]

$t_{n}=-\frac{1}{1+\mathrm{j}\lambda_{n}}.$ (7)

##  IV Construction of Scattering Operators

The transition matrix $\mathbf{T}$ and scattering dyadic $\boldsymbol{S}$ are
not, in general, known in closed form for arbitrary scattering systems.
However, construction of either quantity (or its discrete representation in
the case of the scattering dyadic) can be carried out with full-wave
simulations capable of mapping arbitrary incident fields onto the resulting
scattered fields. The number of incident field configurations (i.e., spherical
or plane waves) required to construct accurate representations of $\mathbf{T}$
or $\boldsymbol{S}$ is commonly dictated by the electrical size of an obstacle
[7, 9] and varies from tens to thousands. However, the resulting matrices are
often of low rank and their explicit calculation could be circumvented by a
matrix completion technique [12], such as the one introduced in the following
section, that constructs approximate representations of $\mathbf{T}$ or
$\boldsymbol{S}$ with a low number of calls to a full-wave solver.

Throughout this letter, we schematically denote the process of calling a full-
wave solver as
$\mathcal{L}(\boldsymbol{E}^{\mathrm{i}})=\boldsymbol{E}^{\mathrm{s}}$, where
the input (excitation) field $\boldsymbol{E}^{\mathrm{i}}$ and output
(scattered) field $\boldsymbol{E}^{\mathrm{s}}$ are assumed to be expressed in
bases appropriate for constructing the operator of interest. For example, a
solver assembling an incident field out of spherical waves with weights
contained in the vector $\mathbf{a}$ and returning a scattered field expressed
in terms of spherical wave weights $\mathbf{f}$ may be written schematically
as $\mathcal{L}(\mathbf{a})=\mathbf{f}$ even if the underlying transition
matrix (1) is not explicitly computed during the simulation process. A similar
notation is adopted for constructing incident fields with plane-wave weights
$\boldsymbol{E}(\hat{\boldsymbol{r}}^{\prime})$ and calculating the resulting
scattered far-fields $\boldsymbol{F}(\hat{\boldsymbol{r}})$.

##  V Iterative Algorithms

Algorithm 1 Estimation of the transition matrix

1: $m=0$

2: $\mathbf{a}_{0}\leftarrow\mathrm{rand}$

3:while stopping criteria are not met do

4: $\mathbf{a}_{m}\leftarrow\mathbf{a}_{m}/|\mathbf{a}_{m}|$

5: $\mathbf{f}_{m}\leftarrow\mathcal{L}(\mathbf{a}_{m})$

6: $\mathbf{T}_{m}\leftarrow\sum_{p\leq
m}\mathbf{f}_{p}\mathbf{a}_{p}^{\mathrm{H}}$

7: $\\{t_{n}\\}_{m}\leftarrow\mathrm{eig}(\mathbf{T}_{m})$

8: $\mathbf{P}_{m}\leftarrow\sum_{p\leq
m}\mathbf{a}_{p}\mathbf{a}_{p}^{\mathrm{H}}$

9: $\mathbf{a}_{m+1}\leftarrow\mathbf{f}_{m}-\mathbf{P}_{m}\mathbf{f}_{m}$

10: $m\leftarrow m+1$

11:end while

Algorithm 2 Estimation of the scattering dyadic

1:$m=0$

2:$\boldsymbol{E}_{0}(\hat{\boldsymbol{r}})\leftarrow\mathrm{rand}$

3:while stopping criteria are not met do

4:
$\boldsymbol{E}_{m}\leftarrow\boldsymbol{E}_{m}/\sqrt{\int|\boldsymbol{E}_{m}(\hat{\boldsymbol{r}})|^{2}\,\mathrm{d}\Omega}$

5:
$\boldsymbol{F}_{m}(\hat{\boldsymbol{r}})\leftarrow\mathcal{L}(\boldsymbol{E}_{m}(\hat{\boldsymbol{r}}^{\prime}))$

6:
$\boldsymbol{S}_{m}(\hat{\boldsymbol{r}},\hat{\boldsymbol{r}}^{\prime})\leftarrow\sum_{p\leq
m}\boldsymbol{F}_{p}(\hat{\boldsymbol{r}})\boldsymbol{E}^{*}_{p}(\hat{\boldsymbol{r}}^{\prime})$

7: $\\{t_{n}\\}_{m}\leftarrow\mathrm{eig}(\boldsymbol{S}_{m})$

8:
$\boldsymbol{P}_{m}(\hat{\boldsymbol{r}},\hat{\boldsymbol{r}}^{\prime})\leftarrow\sum_{p\leq
m}\boldsymbol{E}_{p}(\hat{\boldsymbol{r}})\boldsymbol{E}^{*}_{p}(\hat{\boldsymbol{r}}^{\prime})$

9:
$\boldsymbol{E}_{m+1}\leftarrow\boldsymbol{F}_{m}-\int\boldsymbol{P}_{m}(\hat{\boldsymbol{r}},\hat{\boldsymbol{r}}^{\prime})\cdot\boldsymbol{F}_{m}(\hat{\boldsymbol{r}}^{\prime})\,\mathrm{d}\Omega^{\prime}$

10: $m\leftarrow m+1$

11:end while

Procedures for estimating the transition or scattering dyadic matrix of an
object using a set of full-wave evaluations are sketched in Algorithms 1 and
2, respectively. Both algorithms follow similar steps, though the
implementation details differ in a few small, yet significant, ways. These
differences are highlighted in the following description of the procedure,
where steps of both algorithms are referenced in parallel.

In the setup steps 1 and 2, an iteration index $m$ is initialized to zero
while an excitation vector is initialized with random values. For the
transition matrix algorithm, the vector $\mathbf{a}_{0}$ is initialized with
random complex numbers while in the scattering dyadic algorithm the excitation
$\boldsymbol{E}_{0}$ is a random complex function.

Step 3 represents a condition for terminating the iterating component of the
algorithm. Options for this condition are discussed further at the end of this
section. Within the iterating loop, excitations are normalized in step 4 using
either a vector norm (transition matrix algorithm) or an inner product defined
over the unit sphere (scattering dyadic algorithm). The normalized excitation
is then used to drive a full-wave simulation in step 5.

In step 6, the transition matrix or scattering dyadic is estimated by a set of
outer products between all previous excitations and scattered fields. This
construction ensures that incident fields map to the observed scattered fields
when the incident fields are orthogonal in an appropriate inner product. The
estimate of the scattering dyadic or transition matrix is then used to
generate an estimate of the set of eigenvalues $\\{t_{n}\\}_{m}$ in step 7
using the appropriate choice of eigenvalue problem in (5) or (6).

In steps 8 and 9, the Gram-Schmidt procedure [13] is used to generate a new
excitation based on the previous scattered field with zero projection onto the
set of previous excitations. The index $m$ is then incremented and the
procedure repeats from step 4 until one or more stopping criteria are met.

###  V-A Implementation Considerations

Note that the classical Gram-Schmidt procedure described in step 8 is unstable
and the excitations lose orthogonality after a few iterations. The modified
Gram-Schmidt procedure stabilizes the procedure [13] and should be used in 8.
This modification also highlights the similarity with Arnoldi iteration [13],
but is for conceptual simplicity not described in Algorithms 1 and 2.
Additionally, the algorithms may be re-initialized with a random excitation in
the orthogonal complement to $\mathbf{P}_{m}$ or $\boldsymbol{P}_{m}$ to
improve robustness.

An example of a stopping criterion is detecting an updated excitation norm
less than a predefined value. Alternatively, the routine may be terminated
when all modes with modal significance above a certain threshold
$t_{\mathrm{thr}}$ are sufficiently converged, that is,

$\underset{n}{\max}\left\\{\frac{|\tilde{t}_{n,m}-\tilde{t}_{n,m-1}|}{|\tilde{t}_{n,m}|}\right\\}<\epsilon,$
(8)

where

$\\{\tilde{t}_{n,m}\\}=\\{t_{n,m}:|t_{n,m}|>t_{\mathrm{thr}}\\}$ (9)

and the selected set of eigenvalues $\\{\tilde{t}_{n,m}\\}$ is sorted in
decreasing absolute value.

###  V-B Extension to Transient Simulations

The presented iterative algorithms consider transition matrix and scattering
dyadic representations at a single frequency. However, in multi-frequency
cases, such as FDTD simulations, where a wide frequency response follows each
numerical evaluation, the algorithm could be altered to consider the entire
frequency interval. Provided multi-frequency simulations in which all
frequency points are excited with the same weighted incident field, steps 5–7
are evaluated for each frequency point. This information is compiled and
processed to provide an updated incident field in steps 8–9. One could
consider specific points in the interval; the highest frequency point, as
without any prior knowledge of the object, this is the region with the most
potential modes; or possibly the frequency point in which the sum of the
estimated modal significances is the highest. The latter option evaluated
every iteration of the algorithm provided the best results.

##  VI Numerical Examples

As a demonstration of the proposed procedure, we consider the characteristic
modes of a cylindrical dielectric resonator antenna on a finite ground plane
[14]. The cylinder has a diameter of $10.5\,\mathrm{mm}$, a height of
$2.3\,\mathrm{mm}$, and a relative permittivity of
$\varepsilon_{\mathrm{r}}=38$. It is placed on top of the center of a
perfectly-electrically-conducting square plate of side length
$42\,\mathrm{mm}$, see Fig. 1

To calculate the characteristic modes of this structure, a realization of
Algorithm 2 was implemented using an iterative FEM-MoM hybrid solver within
Altair FEKO [15]. The discrete representation of the scattering dyadic is set
up with Lebedev quadrature [9] of a degree $146$ and a dimension of $N=292$.
Convergence of characteristic mode eigenvalues is demonstrated in Fig. 1,
where the number of correctly evaluated digits is plotted as a function of
mode index and iteration number. Dark colors indicate convergence, while light
colors correspond to modes that are not yet converged. For all three studied
frequencies, the number of converged modes is approximately the number of
iterations (see diagonal $m=n$ line), though an offset of approximately $10$
iterations is required to obtain any converged eigenvalues in the highest
frequency case.

Horizontal lines indicate the number of modes with modal significances above
$10^{-2}$ and $10^{-5}$, while vertical lines indicate the number of
iterations to resolve all modes above these thresholds. In practical
applications of characteristic modes, only modes above the $|t_{n}|<10^{-2}$
line are typically considered. For the lowest frequency
($f=1~{}\mathrm{GHz}$), the data in Fig. 1 show that only six simulations are
required to accurately compute these dominant modes, much fewer than the $292$
solutions required to construct the entire matrix representing the scattering
dyadic. This trend also holds for the two higher frequencies, where 14 and 30
iterations are required.

Furthermore, a multi-frequency implementation of Algorithm 2 was constructed
using the scattering matrix obtained through an FDTD solver, FIT in CST Studio
Suite 2022 [16]. Similar to the FEM calculations above, the scattering matrix
has dimension $N=292$ at each frequency point. The 20 highest modal
significances from the complete scattering matrix are displayed in the
frequency interval 1–7 GHz in the three panels of Fig. 2 in dashed lines and
serve as a visual reference for the results of the discretized Algorithm 2
extensions to transient simulations displayed in solid lines. Due to
limitations in software the full matrices were used to generate the responses
of simultaneous excitations with arbitrary complex weights. With 7 iterative
excitations, top panel, the emergence of the modes can be seen with an only
partial agreement. Using an intermediate of 14 excitations most significant
modes are present but not fully reconstructed. Finally, in this numerical
example, 28 excitations were sufficient to produce visually indistinguishable
modes compared to the full-matrix, a reduction of $90\,\%$.

Figure 1: Number of correctly evaluated digits of eigenvalues $t_{n}$
depending on the number of iterations $m$. The number of digits is evaluated
from the comparison with the decomposition of fully constructed scattering
dyadic as described in [9], $292$ plane waves being used. The full-wave solver
used to gather the data is FEM-MoM hybrid implemented in Altair FEKO [15]. The
horizontal solid and dashed lines indicate characteristic modes reaching
depicted thresholds of modal significance. The corresponding vertical solid
and dashed line shows the number of iterations $m$ required to acquire these
modes.
Figure 2: The 20 highest modal significances of a dielectric cylinder on a
finite ground plane in the frequency interval $1$–$7\,\mathrm{GHz}$ obtained
from a scattering matrix obtained using 292 excitations (dashed) and the
estimates from $m\in\left\\{7,14,28\right\\}$ iterative evaluations (solid)
with a discretized version of Algorithm 2.

##  VII Discussion

To naïvely construct the transition matrix or a discrete representation of the
scattering dyadic of dimension $N$ requires $N$ full-wave evaluations.
Estimates for the minimum dimension $N_{\mathrm{min}}$ required to resolve
characteristic modes to a prescribed precision are available in the literature
[7, 9], though these estimates tend to be quite conservative. A dominant
trend, however, is that the dimension $N_{\mathrm{min}}$ generally increases
with the electrical size of the object under consideration. In the iterative
approach presented here, the dominant $K$ eigenvalues of the scattering dyadic
or transition matrix are estimated accurately using approximately $K_{0}+K$
iterations, i.e., in linear time with some offset $K_{0}$. While the values of
the parameters $N_{\mathrm{min}}$ and $K_{0}$ are difficult to quantitatively
predict due to their dependence on both geometric complexity and electrical
size, it holds that if the scattering dyadic or transition matrix has
dimension $N$ sufficient to resolve $K$ characteristic modes, then the
iterative cost $K_{0}+K$ is at worst equal to $N$. This indicates that the
iterative algorithm cannot perform worse, in terms of computational time, than
full, explicit calculation. Nevertheless, the exact quantitative speed-up
afforded by the iterative algorithm depends on the dimension $N$ of the
matrices being approximated, which can be skewed by _a priori_ knowledge of
the modal structure of the system being studied. For instance, incorrectly
setting $N$ unnecessarily high will lead to artificially high speed-up, while
prior knowledge of the number of significant modes might allow for the naïve
approach to realize accurate results with small $N$, thus greatly reducing the
observed speed-up afforded by the iterative approach.

While based on a fundamentally different formulation of characteristic modes,
the proposed iterative approach shares some motivational aspects with matrix-
free methods for computing characteristic modes of large structures [17],
where matrix-vector multiplications are implemented using MLMFA within
iterative eigenvalue algorithms to avoid the high cost of computing, storing,
and inverting large impedance matrices. In contrast to that work, however, the
approach taken here utilizes an iterative approach to reduce the high
computational burden of computing the scattering matrix, rather than
circumventing its computation altogether.

## References

  * [1] B. K. Lau, M. Capek, and A. M. Hassan, “Characteristic Modes: Progress, Overview, and Emerging Topics,” _IEEE Antennas and Propagation Magazine_ , vol. 64, no. 2, pp. 14–22, 2022.
  * [2] M. Capek and K. Schab, “Computational Aspects of Characteristic Mode Decomposition: An Overview,” _IEEE Antennas and Propagation Magazine_ , vol. 64, no. 2, pp. 23–31, 2022.
  * [3] J. J. Adams, S. Genovesi, B. Yang, and E. Antonino-Daviu, “Antenna Element Design Using Characteristic Mode Analysis: Insights and Research Directions,” _IEEE Antennas and Propagation Magazine_ , vol. 64, no. 2, pp. 32–40, 2022.
  * [4] H. Li, Y. Chen, and U. Jakobus, “Synthesis, Control, and Excitation of Characteristic Modes for Platform-Integrated Antenna Designs: A Design Philosophy,” _IEEE Antennas and Propagation Magazine_ , vol. 64, no. 2, pp. 41–48, 2022.
  * [5] D. Manteuffel, F. H. Lin, T. Li, N. Peitzmeier, and Z. N. Chen, “Characteristic Mode-Inspired Advanced Multiple Antennas: Intuitive Insight Into Element-, Interelement-, and Array Levels of Compact Large Arrays and Metantennas,” _IEEE Antennas and Propagation Magazine_ , vol. 64, no. 2, pp. 49–57, 2022.
  * [6] R. F. Harrington and J. R. Mautz, “Computation of Characteristic Modes for Conducting Bodies,” _IEEE Trans. Antennas Propag._ , vol. 19, no. 5, pp. 629–639, Sept. 1971.
  * [7] M. Gustafsson, L. Jelinek, K. Schab, and M. Capek, “Unified Theory of Characteristic Modes: Part I – Fundamentals,” _arXiv preprint arXiv:2109.00063_ , 2021.
  * [8] ——, “Unified Theory of Characteristic Modes: Part II – Tracking, Losses, and FEM Evaluation,” _arXiv preprint arXiv:2110.02106_ , 2021.
  * [9] M. Capek, J. Lundgren, M. Gustafsson, K. Schab, and L. Jelinek, “Characteristic Mode Decomposition Using the Scattering Dyadic in Arbitrary Full-Wave Solvers,” _arXiv preprint arXiv:2206.06783_ , 2022.
  * [10] G. Kristensson, _Scattering of Electromagnetic Waves by Obstacles_. Edison, NJ: SciTech Publishing, an imprint of the IET, 2016.
  * [11] J.-M. Jin, _Theory and Computation of Electromagnetic Fields_. Wiley, 2010.
  * [12] M. A. Davenport and J. Romberg, “An Overview of Low-Rank Matrix Recovery From Incomplete Observations,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 10, no. 4, pp. 608–622, 2016.
  * [13] G. H. Golub and C. F. Van Loan, _Matrix Computations_. Johns Hopkins University Press, 2012.
  * [14] S. Huang, C.-F. Wang, J. Pan, and D. Yang, “Accurate Sub-Structure Characteristic Mode Analysis of Dielectric Resonator Antennas With Finite Ground Plane,” _IEEE Transactions on Antennas and Propagation_ , vol. 69, no. 10, pp. 6930–6935, 2021.
  * [15] (2022) Altair FEKO. Altair. [Online]. Available: https://www.altair.com/feko/
  * [16] (2022) Simulia CST Studio Suite. Dassault Systemes. [Online]. Available: www.3ds.com/products-services/simulia/products/cst-studio-suite/
  * [17] Q. I. Dai, J. Wu, H. Gan, Q. S. Liu, W. C. Chew, and E. Wei, “Large-Scale Characteristic Mode Analysis With Fast Multipole Algorithms,” _IEEE Transactions on Antennas and Propagation_ , vol. 64, no. 7, pp. 2608–2616, 2016\.