# A Text is Worth Several Tokens:
Text Embedding from LLMs Secretly Aligns Well with The Key Tokens

Zhijie Nie1,3, Richong Zhang1,2, Zhanyu Wu1
1CCSE, School of Computer Science and Engineering, Beihang University,
Beijing, China
2Zhongguancun Laboratory, Beijing, China
3Shen Yuan Honors College, Beihang University, Beijing, China
<EMAIL_ADDRESS>Corresponding author

###### Abstract

Text embeddings from large language models (LLMs) have achieved excellent
results in tasks such as information retrieval, semantic textual similarity,
etc. In this work, we show an interesting finding: when feeding a text into
the embedding LLMs, the obtained text embedding will be able to be aligned
with the key tokens in the input text. We first fully analyze this phenomenon
on eight embedding LLMs and show that this phenomenon is universal and is not
affected by model architecture, training strategy, and embedding method. With
a deeper analysis, we then find that the main change in embedding space
between the embedding LLMs and their original generative LLMs is in the first
principal component. By adjusting the first principal component, we can align
text embedding with the key tokens. Finally, we give several examples to
demonstrate the vast application potential of this finding: (1) we propose a
simple and practical sparse retrieval method based on the aligned tokens,
which can achieve 80% of the dense retrieval effect of the same model while
reducing the computation significantly; (2) we show that our findings provide
a fresh perspective to help understand fuzzy concepts (e.g., semantic
relatedness vs. semantic similarity) and emerging technologies (e.g.,
instruction-following embedding) in this field.

A Text is Worth Several Tokens:
Text Embedding from LLMs Secretly Aligns Well with The Key Tokens

Zhijie Nie1,3, Richong Zhang1,2††thanks:  Corresponding author, Zhanyu Wu1
1CCSE, School of Computer Science and Engineering, Beihang University,
Beijing, China 2Zhongguancun Laboratory, Beijing, China 3Shen Yuan Honors
College, Beihang University, Beijing, China
<EMAIL_ADDRESS>

##  1 Introduction

Large language models (LLMs) have recently made rapid progress on various
natural language understanding tasks using the generative paradigm Brown et
al. (2020). However, not all tasks lend themselves to the generative paradigm
in practice; tasks such as information retrieval, text clustering, and
semantic text similarity usually rely on high-quality text embeddings. Thus,
more and more attention has been focused on obtaining high-quality textual
embeddings from large language models Jiang et al. (2023b); Springer et al.
(2024); BehnamGhader et al. (2024).

As shown on the left half of Figure 1, the LLM for generation takes the texts
as input and output. The input text is tokenized and passed through the module
$f$ to obtain its hidden states. Then, a decoder layer $g$ is required, which
maps the high-dimensional hidden states to the vocabulary-length logits and
computes the decoded probability for each token. When LLMs are converted for
text embedding, current methods typically incorporate the following changes:
(1) $g$ is discarded because there is no need to map to the vocabulary; (2)
$f$ is converted into $\hat{f}$ using prompt-engineering Jiang et al. (2023b);
Springer et al. (2024) or contrastive learning Muennighoff (2022);
BehnamGhader et al. (2024); and (3) a pooling strategy $p$ is used to weighted
sum of hidden states and obtain the text embedding.

Figure 1: Existing paradigms on LLMs for text generation and embedding (left)
and the novel findings of this work (right).

In this paper, we are not proposing a new text embedding method for LLMs.
Instead, our research surrounds a very interesting finding: when the text
embedding obtained by $\hat{f}$ passes through the decoder layer $g$ from the
same LLM, the tokens with the highest decoding probability are highly related
to the input text. In other words, the embedding of the input text is aligned
with some key tokens of that text. As shown in the right half of Figure 1,
when the input text is “What diseases are parrots prone to ?”, we can find the
literally-related tokens, such as “disease” and the semantically-related
tokens, such as “birds” and “suscept” have the highest decoding probabilities.

Considering the unusual nature of this phenomenon, we first introduce eight
LLMs for text embedding and prove that the above phenomenon is universal and
independent of the LLMs’ architecture, the training strategy, and the
embedding method. Subsequently, we performed qualitative and quantitative
analyses based on these LLMs to understand this finding more intuitively and
precisely. (Section 3). To better explain this phenomenon, we compare the
embedding spaces of $f$ and $\hat{f}$ using spectral analysis (Section 4). We
find that the dominant change in $\hat{f}$ is mainly concentrated in the first
principal component. By manually adjusting the first principal component of
the embedding space, we can replicate the phenomenon of aligning text
embeddings to key tokens.

With a deeper understanding of our findings, we believe that it has a rich
potential for application (Section 5). For example, we find that the criticism
of LLM-generated embedding mainly stems from its high dimensionality
(1024-4096), resulting in significant inference and storage overhead
Muennighoff et al. (2024). To address this, we propose a new sparse retrieval
method based on our findings. We convert document embeddings into a sparse
representation consisting only of aligned tokens and utilize a few aligned
tokens from the query embedding for expansion. Despite its simplicity, our
method achieves over 80% of the performance of the original LLM’s dense
retrieval and outperforms strong baselines like BM25 Robertson et al. (2009)
and SPLADE v2 Formal et al. (2021). At the same time, we show that our work
helps to intuitively understand (1) the training-data influence to semantic
relevance and semantic similarity tasks and (2) the working mechanism of the
instruction-following embedding Su et al. (2023) in the Appendix.

The contributions of this paper are summarized as follows:

  * •

We find an interesting and unusual phenomenon: the text embeddings obtained in
the embedding LLM align with the key tokens;

  * •

We explain why this phenomenon occurs from the perspective of spectral
analysis and find that the current method mainly changes the first principal
component of the original embedding space of the LLMs;

  * •

We show a series of example applications, including improvements to the method
and interpretability of the model, demonstrating that our findings have large
application value.

##  2 Background

###  2.1 Basic Paradigm

Given a LLM $F$, we can divide it into two parts:

$F=g\circ f$ (1)

where $g$ is the decoder layer, and $f$ is the rest modules of the LLM. In the
existing LLM embedding methods, $g$ is discarded, while $f$ can be used as an
encoder. Given a text $s_{i}$, we convert it to a token sequence using LLM’s
tokenizer and get $s_{i}=\\{t_{i1},\cdots,t_{il}\\}$, where $l$ is the
sequence length; then we can get the hidden state of the last layer:

${\bf H}=[{\bf h}_{i1}^{(t)},\cdots,{\bf h}_{il}^{(t)}]=f(s_{i})$ (2)

where ${\bf H}\in\mathbb{R}^{d\times L}$ and ${\bf
h}_{ij}^{(t)}\in\mathbb{R}^{d\times 1}$ is the $i$-th $d$-dimensional column
vector of $\bf{H}$. Subsequently, the pooling strategy $p(.)$ is used to
$\bf{H}$ for the text embedding ${\bf h}_{i}$, which can be expressed as

${\bf h}_{i}=p(f(s_{i}))=p({\bf H})=\sum\nolimits_{j=1}^{L}\alpha_{j}{\bf
h}_{ij}^{(t)}$ (3)

where $\alpha_{j}$ is the weight of the hidden states and
$\sum_{j=1}^{L}\alpha_{j}=1$. Specifically, there are three popular pooling
strategies in practice: for last pooling, $\alpha_{j}=1$ when $j=L$ else is
$0$; for mean pooling, $\alpha_{j}=1/L$ for each i; for weighted mean pooling
Muennighoff (2022), $\alpha_{j}=j/\sum\nolimits_{j=1}^{L}j$.

However, text embeddings obtained directly from the encoder $f$ show poor
performance. It is unsurprising since the pre-training task, i.e., the next
token prediction, is not designed for embedding, and the unidirectional
attention detracts from the expressive power of the hidden states Springer et
al. (2024). In the subsequent subsections, we describe how the existing
methods improve the embedding’s quality based on the top of $f$. For
simplicity, we indiscriminately refer to the models proposed by the existing
methods as $\hat{f}$.

###  2.2 Embedding via Prompt Engineering

The model $\hat{f}$ based on prompt engineering fills the text into prompt
templates to improve the quality of text embedding, which can be expressed as

$\hat{f}(s_{i})=f(t(s_{i}))$ (4)

where $t(.)$ represents the operation of filling the text into a fixed prompt
template.

PromptEOL Jiang et al. (2023b) introduces a prompt template: This
sentence:"[text]" means in one word:", where [text] is a placeholder. In
practice, the template where [text] is replaced by a specific text is sent
into the encoder $f$, and the last pooling strategy is used to obtain the text
embedding. The following works design the better prompt template based on
task-oriented Lei et al. (2024) or chain-of-thought Zhang et al. (2024) can
lead to better performance. Springer et al. (2024) proposes a prompt template:
Rewrite the sentence: [text], rewritten sentence: [text], where both [text]
are the placeholder. In practice, both placeholders are filled with the same
text, and the text embedding is obtained by the mean pooling strategy, but it
is pooled only within the range of the second occurrence of the text.

The methods based on prompt engineering are simple and training-free, so they
do not potentially compromise the generative capabilities of the LLMs.
However, they provide limited performance improvement for text embedding
tasks.

###  2.3 Embedding via Contrastive Learning

The methods based on contrastive learning inherited the good experience of the
BERT-based encoder era Gao et al. (2021). In these methods, $\hat{f}$ is fine-
tuned $f$ with contrastive learning. Due to the large parameter count of $f$
itself, parameter-efficient fine-tuning methods such as LoRA Hu et al. (2021)
are usually used.

Given a text dataset $D$, for any text $s_{i}$ sampled from $D$, we first
obtain its embedding ${\bf h}_{i}$ from $f$ with a specific pooling strategy.
Then positive pairs $({\bf h}_{i},{\bf h}_{i}^{+})$ and negative pairs
$\\{({\bf h}_{i},{\bf h}_{ij}^{-})\\}_{j=1}^{N}$ are constructed following
different settings, where $N$ is the negative example number. In the
unsupervised setting, two data-augmented views of a text are considered a
positive pair, while the negative samples are randomly sampled from the
datasets. In the supervised setting, the positive pair is a labelled text
pair, which can be query-document, question-answer or hypothesis-entailment Li
et al. (2023), etc., while potential hard negative pairs may be introduced,
such as hypothesis-contradiction. Finally, the contrastive loss can be
expressed as

$\mathcal{L}_{\rm cl}=-\log\frac{e^{d({\bf h}_{i},{\bf
h}_{i}^{+})/\tau}}{e^{d({\bf h}_{i},{\bf
h}_{i}^{+})/\tau}+\sum_{j=1}^{N}e^{d({\bf h}_{i},{\bf h}_{ij}^{-})/\tau}}$ (5)

where $d(.,.)$ is a distance function, $\tau$ is the temperature hyper-
parameter. During fine-tuning, the contrastive loss draws positive text pairs
close while pushing negative text pairs away.

#### Additional Tricks

There are some effective tricks in the existing works, which include: (1)
switching casual attention to bi-directional attention BehnamGhader et al.
(2024); (2) using different instruction prefixes for the datasets from
different tasks to minimize inter-task interference Su et al. (2023); (3) co-
training contrastive learning and next word prediction to minimize reductions
to generative capability Muennighoff et al. (2024).

Model | Architecture | Fine-Tuning | Embedding
---|---|---|---
Backbone | Attention | Task | Corpus | Pooling | Similarity
SGPT${}_{\text{nli}}$ | GPT-Neo | casual | SCL | NLI | weighted mean | cosine
SGPT${}_{\text{msmarco}}$ | (1.3B) | casual | SCL | MS MARCO | weighted mean | cosine
OPT${}_{\text{EOL}}$ | OPT | casual | PE | - | last token | dot product
OPT${}_{\text{EOL+CSE}}$ | (1.3B) | casual | PE+SCL | NLI | last | dot product
LLaMA${}_{\text{EOL}}$ | LLaMA | casual | PE | - | last token | dot product
LLaMA${}_{\text{EOL+CSE}}$ | (7B) | casual | PE+SCL | NLI | last | dot product
GritLM | Mistral | bi-directional | SCL+NTP | Tulu 2+E5+S2ORC | mean | cosine
LLM2Vec | (7B) | bi-directional | MNTP$\rightarrow$SCL | E5 | weighted mean | cosine
Table 1: Detailed information on the model used to study the embedding space.
SCL, UCL, PE, NTP, and MNTP represent supervised contrastive learning,
unsupervised contrastive learning, prompt engineering, next token prediction,
and masked next token prediction BehnamGhader et al. (2024) separately.

##  3 Embedding Aligns with Key Tokens

###  3.1 Motivation

To analyze the pre-trained transformer in the embedding space, Elhage et al.
(2021); Geva et al. (2022); Dar et al. (2022) attempt to multiply the
attention or feed-forward layer parameters with the token embedding matrix to
explain how these parameters work. For example, Geva et al. (2022) finds that
multiplying the feed-forward value vector with the token embedding matrix can
obtain a distribution over the vocabulary, and the tokens with high
probability can explain what the FFN updates to hidden layer representations.
Inspired by these works, we try to interpret the text embeddings obtained from
LLMs by mapping them into the token space.

###  3.2 Method

To implement the above idea, we need a text dataset $D$, and some
$(\hat{f},T,{\bf E}_{g})$ triplets. $\hat{f}$ is the LLM output
$d$-dimensional text embeddings, $T=\\{t_{1},\cdots,t_{L}\\}$ is the $L$-sized
vocabulary and ${\bf E}_{g}=[{\bf e}_{t_{1}},\cdots,{\bf
e}_{t_{L}}]^{\top}\in\mathbb{R}^{L\times d}$ is the token embedding matrix
from the decoded layer $g$, where ${\bf e}_{t_{j}}\in\mathbb{R}^{d\times 1}$
is the token embedding of token $t_{j}$.

Note that $T$ and ${\bf E}_{g}$ are determined by the original LLM $F$. ${\bf
E}_{g}$ is also the only parameter in $g$111To the best of our knowledge, all
popular LLMs follow the original design of the decoder layer from GPT Radford
et al. (2018), i.e., a linear layer without bias, which also can be regarded
as a token embedding matrix., therefore, there is no difference between ${\bf
E}_{g}{\bf h}_{i}$ and $g({\bf h}_{i})$ for any text embedding ${\bf
h}_{i}\in\mathbb{R}^{d\times 1}$.

Process 1 Embedding-Token Alignment Analysis

0: A text dataset $D$ and the $(\hat{f},T,{\bf E}_{g})$ triplet.

1: Initialization: $i\leftarrow 0$, $j\leftarrow 0$

2: while $i\leq|D|$ do

3: Get the $i$-th text $s_{i}$ in $D$

4: Deduplicate $\text{tokenizer}(s_{i})$ to obtain $T_{s_{i}}$

5: Calculate ${\bf h}_{i}\leftarrow\text{pooling}(\hat{f}(s_{i}))$

6: while $j\leq|T|$ do

7: Calculate $p(t_{j}|s_{i})\leftarrow{\bf e}_{t_{j}}^{\top}{\bf h}_{i}$

8: Update $j\leftarrow j+1$

9: end while

10: Sort $T$ in descending order by $p(t_{i}|s_{i})$ to get $\hat{T}_{s_{i}}$

11: Update $i\leftarrow i+1$

12: end while

12: $T_{s_{i}}$ and $\hat{T}_{s_{i}}$

Given a text $s_{i}$ sampled from $D$, we need to obtain its literal token set
$T_{s_{i}}$ and aligned token set $\hat{T}_{s_{i}}$ and capture the potential
relation between these two sets. We use Process 1 to analyze the alignment of
text embedding with the tokens. For $T_{s_{i}}$, we (1) convert $s_{i}$ into
tokens by the tokenizer of $f$ and (2) deduplicate the token sequence to form
a token set $T_{s_{i}}$. For $\hat{T}_{s_{i}}$, we (1) follow the pooling
strategy of $\hat{f}$ to obtain the text embedding, (2) multiply the text
embedding with the token embedding matrix and get the decoding score
$p(t_{j}|s_{i})$ for each token $t_{j}$, and (3) obtain the ordered token set
$\hat{T}_{s_{i}}$ by sorting in descending order according to the score.

Model | Top 10 Aligned Tokens
---|---
GPT-Neo |  _and , Ċ _in _( . _the _as _on _for
SGPT${}_{\text{nli}}$ |  _2003 2003 _03 _3 _March _game _released _three _games 03
SGPT${}_{\text{msmarco}}$ |  _Advance _Game _Released _Releases _ADV Game _GAME _release _released _releases
OPT |  Ċ _The _It _A _In _This </s> _An _As _Its
OPT${}_{\text{EOL}}$ |  released Re Released reve Game re November It in In
OPT${}_{\text{EOL+CSE}}$ |  _Game _March _games _Nintendo _game _Microsoft _PlayStation _Games Game _2003
LLaMA |  <0x0A> _The _It _A _In _This _Play _An _As </s>
LLaMA${}_{\text{EOL}}$ |  Re it re It _Re _it _It in The In
LLaMA${}_{\text{EOL+CSE}}$ |  _game _games _Game game Game _Games _March _release _released _November
Mistral |  , _and 2 _ 1 _in _( _as - _the
GritLM |  _Game _Xbox _Pok _game _cross _revealed _Windows , _ _reveal
LLM2Vec |  _release _releases _released _Release _revealed _releasing release _Xbox _game _reveal
Table 2: The top 10 aligned tokens for eight $\hat{f}$ for text embedding and
their corresponding $f$ for text generation when the input text is “Revealed
in March 2003, it was released across Game Boy Advance, PlayStation 2,
GameCube, Xbox and Microsoft Windows in November 2003”. Figure 2: The
evaluation metric comparison of four LLMs and their eight variant for text
embeddings.

###  3.3 Experiment

#### Dataset $D$

We randomly sample 10K of the 1M Wikipedia texts provided by Gao et al. (2021)
and report the metric calculated by this dataset. We observe that experiments
on other datasets, such as SNLI Bowman et al. (2015) and MSMARCO Nguyen et al.
(2016), lead to similar conclusions; please refer to Appendix E for details.

#### Triplet $(\hat{f}$, $T$, ${\bf E}_{g})$

We selected eight embedding model based on LLMs for analysis, which includes
SGPT${}_{\text{nli}}$ and SGPT${}_{\text{msmarco}}$ Muennighoff (2022);
OPT${}_{\text{EOL}}$, OPT${}_{\text{EOL+CSE}}$, LLaMA${}_{\text{EOL}}$ and
LLaMA${}_{\text{EOL+CSE}}$ Jiang et al. (2023b); GritLM Muennighoff et al.
(2024) and LLM2Vec BehnamGhader et al. (2024). The key information overview of
these models is placed in Table 1. We consider these embedding LLMs as
$\hat{f}$ and obtain $T$ and ${\bf E}_{g}$ from their backbone models.

Note that none of the improvement ideas for these models go beyond what we
describe in Section 2, and please refer to Appendix A for detailed information
on each model. Additionally, to ensure the generalizability of subsequent
conclusions, the LLMs selected have the following attributes:

  * •

Different Architecture: The backbones of these LLMs include: GPT-Neo Gao et
al. (2020), OPT Zhang et al. (2022), LLaMA Touvron et al. (2023) and Mistral
Jiang et al. (2023a). GritLM and LLM2Vec enable bi-directional attention,
while the other LLMs keep the casual attention;

  * •

Different Fine-Tuning Methods: These LLMs rely on different methods to improve
the embedding capability, such as prompt engineering, contrastive learning, or
multi-task learning, while the different corpus was used for fine-tuning.

  * •

Different Embedding Methods: These LLMs use different pooling strategies to
obtain embeddings and calculate the similarity using cosine similarity or dot
product 222Regardless of what the similarity metric is recommended, we use a
simple matrix multiplication between ${\bf E}_{g}$ and ${\bf h}_{i}$, to
ensure consistency with the original decoding process..

###  3.4 Qualitative Analysis

Since the ordered set $\hat{T}_{s_{i}}$ is as large as $T$, we analyze only
the top $K$ tokens in $\hat{T}_{s_{i}}$. We introduce $\hat{T}_{s_{i}}^{K}$ to
denote the first $K$ elements in $\hat{T}_{s_{i}}$. We sample an input text
from $D$ and show the top 10 aligned tokens of the text embedding, i.e.,
$\hat{T}_{s_{i}}^{\text{1}0}$, in Table 2. We also show the aligned tokens for
the original $f$, using the same pooling strategy as the corresponding
$\hat{f}$ for fair comparison.

We use different colors to indicate the relationship between each token and
the surface token set $T_{s_{i}}$: Green represents the token is in
$T_{s_{i}}$; Yellow represents the token and a token in $T_{s_{i}}$ are same
after stemming or lemmatization333We use the tools provided by NLTK Loper and
Bird (2002): SnowballStemmer for stemming and WordNetLemmatizer for
lemmatization.; Red represents the token and any tokens in $T_{s_{i}}$ have no
literal connection. As shown in Table 2, we find that: (1) the text embeddings
from the original $f$ align with some tokens related $T_{s_{i}}$, but most of
them are meaningless tokens, such as “and” and “the” etc; (2) compared to
those aligned from $f$, the text embeddings from $\hat{f}$ also align with the
tokens related to $T_{s_{i}}$ but more meaningful, such as “game” and
“November”; (3) even though some tokens are marked red, this only means that
they are literally unrelated to $T_{s_{i}}$, but there may be a deeper
connection. For example, “Nintendo” is the development company of “Game Boy
Advance” in the input text. Note that the input text is not specially
selected, and we provide more cases in Appendix E.

###  3.5 Quantitative Analysis

To quantitatively reflect the connection between $\hat{T}_{s_{i}}^{K}$ and
$T_{s_{i}}$, we propose three evaluation metrics:

#### Hit@K

To measure whether the top $K$ tokens of $\hat{T}_{s_{i}}$ contains any token
in $T_{s_{i}}$, we propose the metric of Hit@K as follows:

$\text{Hit@K}=\underset{s_{i}\sim
D}{\mathbb{E}}\left[\mathbb{I}\left(\left|\hat{T}_{s_{i}}^{K}\cap
T_{s_{i}}\right|>0\right)\right]$ (6)

where $\mathbb{I}(.)$ is the indicator function, $|\cdot|$ represents the
element number of the set.

#### Local Alignment Rate

To measure the overlap degree between the tokens in $T_{s_{i}}$ and the top
$|T_{s_{i}}|$ tokens in $\hat{T}_{s_{i}}$, we propose the metric of Local
Alignment Rate (LAR) as follows:

$\text{LAR}=\underset{s_{i}\sim
D}{\mathbb{E}}\left[\left|\hat{T}_{s_{i}}^{K_{i}}\cap
T_{s_{i}}\right|/K_{i}\right]$ (7)

where $K_{i}$ is denoted as $|T_{s_{i}}|$ for simplicity.

#### Global Alignment Rate

LAR can not reflect the global alignment situation. For example, elements in
$\hat{T}_{s_{i}}^{K_{i}}\cap T_{s_{i}}$ and $\hat{T}_{s_{j}}^{K_{j}}\cap
T_{s_{j}}$ can be either the completely same or completely different, but
cannot be reflected in LAR. To measure the overlap degree in the dataset $D$
globally, we propose the metric of Global Alignment Rate (GAR) as follows:

$\text{GAR}=\left|\cup_{i=1}^{|D|}\left(\hat{T}_{s_{i}}^{K_{i}}\cap
T_{s_{i}}\right)\right|/\left|\cup_{i=1}^{|D|}T_{s_{i}}\right|$ (8)

where $|D|$ represents the text number of $D$.

We report the Hit@10, LAR, and GAR for the original LLM and their variants
used for text embedding in Figure 2. The following findings can be easily
concluded: (1) all $f$ and $\hat{f}$ except LLaMA maintain a high Hit@10,
which means at least one token in the input text is aligned; (2) all $\hat{f}$
also maintain a low LAR and but higher GAR than that of the corresponding $f$;
(3) compared to OPT${}_{\text{EOL}}$ and LLaMA${}_{\text{EOL}}$,
OPT${}_{\text{EOL+CSE}}$ and LLaMA${}_{\text{EOL+CSE}}$ lead to a lower LAR
and a higher GAR after contrastive learning.

Combined with the qualitative analysis, we conclude that text embeddings from
$f$ and $\hat{f}$consistently aligns certain tokens in the text, and that
$\hat{f}$-aligned tokens tend to be more diversed and more key to the input
text.

###  3.6 Discussion

#### How to understand?

The text embedding aligns well with some key tokens in the input text after
passing through the decoder layer, which means the text embedding is closer to
these tokens than other tokens in high-dimensional space. Note that the
absolute position of the text embedding in the whole space is described here,
rather than in a subspace, since, as far as we can observe, all LLMs’ decoder
layer weights, i.e., the token embedding matrixes, are full rank.

#### How to explain?

The explanation for this phenomenon is not straightforward because (1) the
decoding layer, whose weights are never seen during the process from $f$ to
$\hat{f}$, can precisely decode some tokens related to the input text from the
embedding; (2) the optimization objective of contrastive learning by itself
does not guarantee that this will happen. Therefore, we analyze the singular
value spectrum of the embedding space before and after training in Section 4.

#### How to use?

This interesting finding brings extreme interpretability to text embedding. In
Section 5, we show the aligning tokens of the text embedding change with
different training data and different instructions. Meanwhile, we propose a
sparse retrieval method for solving the computational and storage overhead
caused by the ultra-high dimensionality of LLM representations.

(a) GPT-Neo and SGPT${}_{\text{nli}}$

(b) OPT and OPT${}_{\text{EOL+CSE}}$

(c) LLaMA and LLaMA${}_{\text{EOL+CSE}}$

(d) Mistral and GritLM

Figure 3: The variation in each principal component of the embedding space.

(a) Contribution to the aligned tokens.

(b) Aligned tokens after adjusting ${\bf u}_{1}$.

Figure 4: The situation of the aligned token when $f$ is GPT-Neo, $\hat{f}$ is
SGPT${}_{\text{nli}}$ and the input text is “Making a Killing is a 2018
Canadian-American crime-mystery film co-written, co-produced and directed by
Devin Hume.”

##  4 Spectral Analysis of Embedding Space

For a deeper understanding of the phenomenon, we use the same text dataset $D$
in Section 3 and some $(f,\hat{f})$ pairs. We convert all texts in $D$ into
embeddings via $f$ and use the SVD decomposition to obtain a set of standard
orthogonal bases in $d$-dimensional space, which can be expressed as

${\bf U}=\left[{\bf u}_{1},\cdots,{\bf u}_{d}\right]\in\mathbb{R}^{d\times d}$
(9)

where ${\bf u}_{j}\in\mathbb{R}^{d\times 1}$ corresponds to the singular
vector of $j$-th largest singular value.

For any text $s_{i}$ from $D$, we denote its embedding obtained from $f$ and
$\hat{f}$ as ${\bf h}_{i}$ and $\hat{\bf h}_{i}$, separately. Then we metric
the variation in each principal component between ${\bf h}_{i}$ and $\hat{\bf
h}_{i}$ based on ${\bf U}$:

$v_{j}=\underset{s_{i}\sim D}{\mathbb{E}}\left[\left(\hat{\bf h}_{i}-{\bf
h}_{i}\right)^{\top}{\bf u}_{j}\right]$ (10)

where $v_{j}$ represents the variation in the $j$-th largest principal
component. Due to space limitations, we select four $(f,\hat{f})$ pairs and
plot their $\\{v_{j}\\}_{j=1}^{d}$ in Figure 3 and show the variation of the
other four embedding LLMs in Appendix D.

######  Observation 1.

Compared to the original embedding space, the variation of the largest
principal component, i.e., $v_{1}$, is dominant.

Compared with the original LLMs, the embedding space corresponding to
SGPT${}_{\text{nli}}$, OPT${}_{\text{EOL+CSE}}$, and
LLaMA${}_{\text{EOL+CSE}}$ significantly decreases in the first principal
component, while only the pair corresponding to GritLM shows a small increase.
As with the qualitative analysis, we speculate that this results from co-
tuning with contrastive learning and next-token prediction. We further find
that the embedding space corresponding to LLM2Vec has a significant decrease
in the first principal component, too; please refer to Appendix D for details.

We further analyze the contribution of the first principal component and the
other components in aligning tokens. Specifically, we divide the text
embedding ${\bf h}_{i}$ into two components:

${\bf h}_{i}={\bf h}_{i}^{\text{1st}}+{\bf h}_{i}^{\text{rest}}$ (11)

where ${\bf h}_{i}^{\text{1st}}={\bf u}_{1}^{\top}{\bf h}_{i}{\bf u}_{1}$ and
${\bf h}_{i}^{\text{rest}}=\sum_{j=2}^{d}{\bf u}_{j}^{\top}{\bf h}_{i}{\bf
u}_{j}$. We then measure the contribution of ${\bf h}_{i}^{\text{1st}}$ and
${\bf h}_{i}^{\text{rest}}$ to aligning tokens. Based on the matrix
decomposition, we divide the contribution into two parts:

$\underbrace{{\bf E}_{g}{\bf h}_{i}}_{C_{s_{i}}}=\underbrace{{\bf E}_{g}{\bf
h}_{i}^{\text{1st}}}_{C_{s_{i}}^{\text{1st}}}+\underbrace{{\bf E}_{g}{\bf
h}_{i}^{\text{rest}}}_{C_{s_{i}}^{\text{rest}}}.$ (12)

Specifically, we sample a text $s_{i}$ from $D$, rank and obtain the top $K$
tokens based on $C_{s_{i}}$ and see how much $C_{s_{i}}^{\text{1st}}$ and
$C_{s_{i}}^{\text{text}}$ contribute to the logits. Due In Figure 4a, we
provide an example and obtain the following observation:

######  Observation 2.

The first principal component contributes much more to meaningless tokens than
meaningful tokens.

Combining Observation 1 and 2, we can see: (1) current text embedding LLMs
always maximize the perturbation of the first principal component, while (2)
the first principal component contributes mainly to meaningless tokens.
Therefore, we give the following hypothesis:

######  Hypothesis 1.

The text embeddings of original LLMs have been aligned with the key tokens but
are not reflected due to the affection by the first principal component.

To verify the hypothesis, we manually adjust the embeddings from $f$.
Specifically, considering that the variation on the other principal components
is small compared to the first principal component, we can simplify as
follows:

$\displaystyle\underset{s_{i}\sim D}{\mathbb{E}}\left[\left(\hat{\bf
h}_{i}-{\bf h}_{i}\right)^{\top}{\bf U}\right]\approx[v_{1},0,\cdots,0]$ (13)
$\displaystyle\Rightarrow$ $\displaystyle\underset{s_{i}\sim
D}{\mathbb{E}}\hat{\bf h}_{i}\approx\underset{s_{i}\sim D}{\mathbb{E}}{\bf
h}_{i}+v_{1}{\bf u}_{1}$

Therefore, for each text embedding ${\bf h}_{i}$, we subtracted a certain
amount of the first principal component and obtained the adjusted embedding
${\bf h}_{i}^{\text{adj}}$:

${\bf h}_{i}^{\text{adj}}={\bf h}_{i}+\lambda{\bf u}_{1}$ (14)

where $\lambda\in R$ is a hyper-parameter. In Figure 4b, we report the top 10
tokens aligned by ${\bf h}_{i}^{\text{adj}}$ and their corresponding logits
when adjusting $\lambda$ for 0.95$v_{1}$, $v_{1}$ and 1.05$v_{1}$. As shown in
Figure 4b, the embedding from $f$ can align with more meaningful tokens of the
input text by adjusting only the first principal component, verifying our
hypothesis. We show that similar conclusions exist on $f$ of other studies in
Appendix D.

##  5 Potential Application

#### Sparse Retrieval

The LLMs for embedding show superior Information Retrieval (IR) performance
over the embedding models based on traditional PLMs (e.g., BERT Kenton and
Toutanova (2019) and RoBERTa Liu et al. (2019)). However, the dimensionality
of these LLMs’ output embeddings (1024$\sim$4096) far exceeds the 768
dimensions of traditional PLMs, which will incur exponential computation and
storage overhead in practice. To overcome this problem, we propose a new
sparse retrieval method to generate high-quality query extensions for queries
and sparse representations for documents.

For each document $d_{i}$, we obtain its embedding $\hat{\bf h}_{d_{i}}$ and
aligned token set $\hat{T}_{d_{i}}$ using the embedding LLM. Then we can
maintain a vocabulary-length sparse vector
$\tilde{h}_{d_{i}}=[w_{t_{1}},\cdots,w_{t_{L}}]$, where only those dimensions
corresponding to the top $K$ aligned tokens are not zero:

$w_{t_{i}}=\begin{cases}{\bf e}_{t_{i}}^{\top}\hat{\bf h}_{d_{i}}&\text{if
}t_{i}\in\hat{T}_{d_{i}}^{K}\\\ 0&\text{otherwise}\end{cases}$ (15)

For each query $q_{i}$, we get its surface token set $T_{q_{i}}$ using the
tokenizer and its aligned token set $\hat{T}_{q_{i}}$. It is easy to see that
we can extend $T_{q_{i}}$ using the first $M$ elements in $\hat{T}_{q_{i}}$,
obtaining the expanded token set
$\tilde{T}_{q_{i}}=T_{q_{i}}\cup\hat{T}_{q_{i}}^{M}$.

In ad-hoc retrieval scenarios, all document sparse representations can be
computed and cached in advance while the query is computed and extended on the
fly. Therefore, we can calculate the similarity of $q_{i}$ and $d_{j}$ as
follows:

$\
\text{Similarity}(q_{i},d_{j})=\sum\nolimits_{t_{k}\in(\tilde{T}_{q_{i}}\cap\hat{T}_{d_{i}}^{K})}w_{t_{i}}$
(16)

Model | FiQA | NFCorpus | SciFact | ArguAna
---|---|---|---|---
BM25 | 0.236 | 0.325 | 0.665 | 0.315
SPLADEv2 | 0.336 | 0.334 | 0.693 | 0.479
LLM2Vec | 0.531 | 0.393 | 0.789 | 0.575
+Spar. | 0.404 | 0.326 | 0.669 | 0.481
GirtLM | 0.600 | 0.409 | 0.792 | 0.632
+Spar. | 0.457 | 0.336 | 0.703 | 0.526
Table 3: The performance comparison on the four IR datasets. “+ Spar.” is our
sparse retrieval method.

We select LLM2Vec and GritLM due to their SOTA performance and up to 4096
embedding dimensions. For evaluation, we select four information retrieval
datasets: FiQA Maia et al. (2018), NFCorpus Boteva et al. (2016), SciFact
Wadden et al. (2020) and ArguAna Wachsmuth et al. (2018) and report the
nDCG@10. For hyper-parameter, we experiment under the settings
$K\in\\{1000,2000,3000\\}$ and $M\in\\{25,50,75,100\\}$ and report the best
results in Table 3. We report the detailed results in Appendix C and find that
performance is insensitive to $K$, while increasing with the increase of $M$
in most cases.

Our sparse retrieval approach preserves 80% of the text embeddings’
performance, outperforming the strong baselines: BM25 and SPLADEv2. Since the
length of sparse representation is fixed, our sparse retrieval method can
achieve a retrieval efficiency similar to that of BM25 when ignoring the
consumption of the query encoding process.

#### More Insights

Due to space constraints, we provide more sights in Appendix B, mainly
explaining that different training data and different instructions align
embeddings of the same input text to different tokens, achieving better
performance for specific downstream tasks.

##  6 Conclusion

In this work, we show the alignment of text embeddings obtained from LLMs for
embedding with key tokens in the input text. We first perform qualitative and
quantitative analyses on eight LLMs to demonstrate the generalizability of our
conclusions. Then, We use spectral analysis to understand the phenomenon
better and show that text embeddings can be aligned to key tokens by adjusting
the first principal component. For application, three examples given on
interpretability or information retrieval demonstrate our findings’ broad
application promise and continued research value.

## Limitation

We summarize several limitations of this work as follows:

  * •

For the universality of our findings, we cannot observe a similar phenomenon
in the embedding models based on traditional PLMs (such as SBERT Reimers and
Gurevych (2019) or SimCSE Gao et al. (2021)). We conjecture that the reason
comes from two sources: (1) traditional PLMs have a higher degree of embedding
space variation than LLMs due to too few parameters; (2) traditional PLMs use
a complex MLM head for training, and the text embedding is obtained too far
away from the final decoded token embedding matrix, resulting in no
dependencies between them.

  * •

For the study targets, we only conducted the empirical study for the LLMs for
English embedding. We have not extended the study to a multi-lingual setting
due to insufficient LLMs for multi-lingual embedding.

  * •

In Section 4, we have only shown that adjusting the first principal component
can achieve alignment with key tokens, but we have not yet been able to
explain why the pre-training phase of the LLMs can form such an embedding
space, nor can we achieve the same performance as the existing methods by
tuning only the first principal component. At the same time, it is conceivable
that we cannot achieve a similar embedding quality to contrastive learning by
adjusting only the first principal component.

## References

  * BehnamGhader et al. (2024) Parishad BehnamGhader, Vaibhav Adlakha, Marius Mosbach, Dzmitry Bahdanau, Nicolas Chapados, and Siva Reddy. 2024.  Llm2vec: Large language models are secretly powerful text encoders.  _arXiv preprint arXiv:2404.05961_.
  * Boteva et al. (2016) Vera Boteva, Demian Gholipour, Artem Sokolov, and Stefan Riezler. 2016.  A full-text learning to rank dataset for medical information retrieval.  In _Advances in Information Retrieval: 38th European Conference on IR Research, ECIR 2016, Padua, Italy, March 20–23, 2016. Proceedings 38_ , pages 716–722. Springer.
  * Bowman et al. (2015) Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. 2015.  A large annotated corpus for learning natural language inference.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 632–642.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Dar et al. (2022) Guy Dar, Mor Geva, Ankit Gupta, and Jonathan Berant. 2022.  Analyzing transformers in embedding space.  _arXiv preprint arXiv:2209.02535_.
  * Elhage et al. (2021) Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. 2021.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_ , 1:1.
  * Formal et al. (2021) Thibault Formal, Carlos Lassance, Benjamin Piwowarski, and Stéphane Clinchant. 2021.  Splade v2: Sparse lexical and expansion model for information retrieval.  _arXiv preprint arXiv:2109.10086_.
  * Gao et al. (2020) Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. 2020.  The pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_.
  * Gao et al. (2021) Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021.  Simcse: Simple contrastive learning of sentence embeddings.  _arXiv preprint arXiv:2104.08821_.
  * Geva et al. (2022) Mor Geva, Avi Caciularu, Kevin Ro Wang, and Yoav Goldberg. 2022.  Transformer feed-forward layers build predictions by promoting concepts in the vocabulary space.  _arXiv preprint arXiv:2203.14680_.
  * Hu et al. (2021) Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. 2021.  Lora: Low-rank adaptation of large language models.  In _International Conference on Learning Representations_.
  * Huh et al. (2024) Minyoung Huh, Brian Cheung, Tongzhou Wang, and Phillip Isola. 2024.  The platonic representation hypothesis.  _arXiv preprint arXiv:2405.07987_.
  * Jiang et al. (2023a) 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. 2023a.  Mistral 7b.  _arXiv preprint arXiv:2310.06825_.
  * Jiang et al. (2023b) Ting Jiang, Shaohan Huang, Zhongzhi Luan, Deqing Wang, and Fuzhen Zhuang. 2023b.  Scaling sentence embeddings with large language models.  _arXiv preprint arXiv:2307.16645_.
  * Kenton and Toutanova (2019) Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of naacL-HLT_ , volume 1, page 2.
  * Lei et al. (2024) Yibin Lei, Di Wu, Tianyi Zhou, Tao Shen, Yu Cao, Chongyang Tao, and Andrew Yates. 2024.  Meta-task prompting elicits embedding from large language models.  _arXiv preprint arXiv:2402.18458_.
  * Li et al. (2023) Zehan Li, Xin Zhang, Yanzhao Zhang, Dingkun Long, Pengjun Xie, and Meishan Zhang. 2023.  Towards general text embeddings with multi-stage contrastive learning.  _arXiv preprint arXiv:2308.03281_.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Loper and Bird (2002) Edward Loper and Steven Bird. 2002.  Nltk: The natural language toolkit.  In _Proceedings of the ACL-02 Workshop on Effective Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics_ , pages 63–70.
  * Maia et al. (2018) Macedo Maia, Siegfried Handschuh, André Freitas, Brian Davis, Ross McDermott, Manel Zarrouk, and Alexandra Balahur. 2018.  Www’18 open challenge: financial opinion mining and question answering.  In _Companion proceedings of the the web conference 2018_ , pages 1941–1942.
  * Muennighoff (2022) Niklas Muennighoff. 2022.  Sgpt: Gpt sentence embeddings for semantic search.  _arXiv preprint arXiv:2202.08904_.
  * Muennighoff et al. (2024) Niklas Muennighoff, Hongjin Su, Liang Wang, Nan Yang, Furu Wei, Tao Yu, Amanpreet Singh, and Douwe Kiela. 2024.  Generative representational instruction tuning.  _arXiv preprint arXiv:2402.09906_.
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  Ms marco: A human-generated machine reading comprehension dataset.
  * Peng et al. (2024) Letian Peng, Yuwei Zhang, Zilong Wang, Jayanth Srinivasa, Gaowen Liu, Zihan Wang, and Jingbo Shang. 2024.  Answer is all you need: Instruction-following text embedding via answering the question.  _arXiv preprint arXiv:2402.09642_.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. 2018.  Improving language understanding by generative pre-training.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3982–3992.
  * Robertson et al. (2009) Stephen Robertson, Hugo Zaragoza, et al. 2009.  The probabilistic relevance framework: Bm25 and beyond.  _Foundations and Trends® in Information Retrieval_ , 3(4):333–389.
  * Saravia et al. (2018) Elvis Saravia, Hsien-Chi Toby Liu, Yen-Hao Huang, Junlin Wu, and Yi-Shin Chen. 2018.  Carer: Contextualized affect representations for emotion recognition.  In _Proceedings of the 2018 conference on empirical methods in natural language processing_ , pages 3687–3697.
  * Springer et al. (2024) Jacob Mitchell Springer, Suhas Kotha, Daniel Fried, Graham Neubig, and Aditi Raghunathan. 2024.  Repetition improves language model embeddings.  _arXiv preprint arXiv:2402.15449_.
  * Su et al. (2023) Hongjin Su, Weijia Shi, Jungo Kasai, Yizhong Wang, Yushi Hu, Mari Ostendorf, Wen-tau Yih, Noah A Smith, Luke Zettlemoyer, and Tao Yu. 2023.  One embedder, any task: Instruction-finetuned text embeddings.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 1102–1121.
  * 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, et al. 2023.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Wachsmuth et al. (2018) Henning Wachsmuth, Shahbaz Syed, and Benno Stein. 2018.  Retrieval of the best counterargument without prior topic knowledge.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 241–251.
  * Wadden et al. (2020) David Wadden, Shanchuan Lin, Kyle Lo, Lucy Lu Wang, Madeleine van Zuylen, Arman Cohan, and Hannaneh Hajishirzi. 2020.  Fact or fiction: Verifying scientific claims.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7534–7550.
  * Wang et al. (2023) Liang Wang, Nan Yang, Xiaolong Huang, Linjun Yang, Rangan Majumder, and Furu Wei. 2023.  Improving text embeddings with large language models.  _arXiv preprint arXiv:2401.00368_.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel R Bowman. 2018.  A broad-coverage challenge corpus for sentence understanding through inference.  In _Proceedings of NAACL-HLT_ , pages 1112–1122.
  * Zhang et al. (2024) Bowen Zhang, Kehua Chang, and Chunping Li. 2024.  Simple techniques for enhancing sentence embeddings in generative language models.  _arXiv preprint arXiv:2404.03921_.
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. 2022.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_.

##  Appendix A Detailed Information of Models

This section details the text embedding LLMs used for the study in the main
text. Note taht these LLMs are CC BY 4.0 compliant and open source and can be
used to obtain text embedding or any of the downstream applications they
support.

  * •

SGPT${}_{\text{nli}}$ are based on GPT-Neo and fine-tuned with contrastive
learning on both SNLI Bowman et al. (2015) and MNLI Williams et al. (2018)
dataset. SGPT${}_{\text{nli}}$ includes four versions of 125m, 1.3B, 2.7B and
5.7B variants, and the variant used for this work is SGPT-1.3B-weightedmean-
nli444https://huggingface.co/Muennighoff/SGPT-1.3B-weightedmean-nli.

  * •

SGPT${}_{\text{msmarco}}$ share the same backbone and training paradigm with
SGPT${}_{\text{nli}}$ except the training data. The variant used for this work
is SGPT-1.3B-weightedmean-msmarco-specb-
bitfit555https://huggingface.co/Muennighoff/SGPT-1.3B-weightedmean-msmarco-
specb-bitfit.

  * •

OPT${}_{\text{EOL}}$ are based on OPT and use prompt template This
sentence:"[text]" means in one word:" to guide OPTs in aggregating the
semantics of the whole text into a single location. Due to the training-free
nature of OPT${}_{\text{EOL}}$, it can be easily applied to any variant of
OPT, and the variant used for this work is
OPT-1.3B666https://huggingface.co/facebook/opt-1.3b.

  * •

OPT${}_{\text{EOL+CSE}}$ are parameter-efficient fine-tuned with contrastive
learning on SNLI and MNLI dataset on the top of OPT${}_{\text{EOL}}$. All LoRA
weights of OPT${}_{\text{EOL+CSE}}$ are open-sourced, and the weight
corresponds to OPT-1.3B777https://huggingface.co/royokong/prompteol-opt-1.3b
are used for comparing fairly with OPT${}_{\text{EOL}}$.

  * •

LLaMA${}_{\text{EOL}}$ share the same prompt template with
OPT${}_{\text{EOL}}$ but are based on LLaMA. The variant used for this work is
LLaMA-7B888https://llama.meta.com/llama-downloads/.

  * •

LLaMA${}_{\text{EOL+CSE}}$ are parameter-efficient fine-tuned with contrastive
learning on SNLI and MNLI dataset on the top of LLaMA${}_{\text{EOL}}$. The
weight corresponds to LLaMA-7B999https://huggingface.co/royokong/prompteol-
llama-7b are used for comparing fairly with OPT${}_{\text{EOL}}$.

  * •

GirtLM is fine-tuned with instruction-tuning and contrastive learning to
achieve a better trade-off between the generation and embedding capabilities.
GritLM-7B101010https://huggingface.co/GritLM/GritLM-7B, whose backbone is
Mistral-7B-Instruct-v0.2, is used in this work.

  * •

LLM2Vec is a three-step method to adjust LLMs for text embeddings, which
includes (1) changing the casual attention to bi-directional attention; (2)
fine-tuning the LLM with a new task, masked next token prediction (MNTP), to
adapt the LLM to use bi-directional attention; (3) fine-tuning the LLM with
supervised contrastive learning to improve the embedding capability. The
second-step 111111https://huggingface.co/McGill-NLP/LLM2Vec-
Mistral-7B-Instruct-v2-mntp and third-step
121212https://huggingface.co/McGill-NLP/LLM2Vec-Mistral-7B-Instruct-v2-mntp-
supervised LoRA weights corresponding to Mistral-7B-Instruct-v0.2 are used.

##  Appendix B More Application Demonstration

###  B.1 Semantic Relevance v.s. Similarity

Current textual embedding models are often fine-tuned with different datasets
depending on their evaluation task. For example, the NLI dataset is often used
for training when evaluating the Semantic Text Similarity (STS) task on
“semantic similarity”. Instead, the MS-MARCO dataset is often used for
training when evaluating the information retrieval task on “semantic
relevance”. Previously, it was difficult to distinguish the embedding spaces
obtained from training on different datasets, although both above settings
only use contrastive learning to fine-tune. Benefiting from the “token align”
phenomenon, we can now understand this phenomenon by mapping the text
embeddings to token space.

We select SGPT${}_{\text{nli}}$ and SGPT${}_{\text{msmarco}}$ to study because
there is no difference between them except for the fine-tuning dataset.
Considering a toy example of two sentences $(S_{A},S_{B})$:

$S_{A}$: I like apples.

$S_{B}$: I dislike apples.

We obtain the embedding of both two sentences with SGPT${}_{\text{nli}}$ and
SGPT${}_{\text{msmarco}}$ and align the embedding to the token space with the
decoder layer. As shown in Table 4, most aligned tokens of $S_{A}$ are related
to “apple”, while there is some difference in the tokens aligned by $S_{B}$.
Specifically, when SGPT${}_{\text{nli}}$ is used, tokens related to “dislike”
are in the majority, whereas when SGPT${}_{\text{msmarco}}$ is used, the ratio
of tokens related to “dislike” and “apple” is balanced.

Model | Top 5 aligned token of $S_{A}$
---|---
SGPT${}_{\text{nli}}$ | _apple _apples _Apple apple Apple
SGPT${}_{\text{msmarco}}$ | _apple _Apple Apple apple _liking
| Top 5 aligned token of $S_{B}$
SGPT${}_{\text{nli}}$ | _dislike _disliked hate _hates _apple
SGPT${}_{\text{msmarco}}$ | _dislike _Apple _disliked _apple Apple
Table 4: Comparison of the aligned tokens when using different fine-tuning
data.

We believe that this phenomenon can help to intuitively understand the
difference between “semantic similarity” and “semantic relatedness”:

  * •

In the semantic similarity setting, $S_{A}$ and $S_{B}$ are not considered to
have a high degree of similarity because one of them is an affirmative $S_{A}$
and the other is a negative sentence. SGPT${}_{\text{nli}}$ aligns the
embedding of $S_{B}$ to “dislike” to ensure that the embedding of the two
sentences is far enough apart. Therefore, the similarity of the two sentences
given by SGPT${}_{\text{nli}}$ is only 0.419;

  * •

In the semantic relevance setting, $S_{A}$ and $S_{B}$ can be considered
highly relevant because they both describe whether “I” like “apples” or not.
SGPT${}_{\text{msmarco}}$ aligns the embedding of $S_{B}$ to both "dislike"
and "apple" to ensure that the final similarity reflects their relevance.
Therefore, the similarity of the two sentences given by
SGPT${}_{\text{msmarco}}$ is 0.816;

###  B.2 Instruction v.s. No-Instruction

Recent works such as Instructor Su et al. (2023); Peng et al. (2024) use
different instruction prefixes to distinguish between different embedding
tasks. To explain the validity of the instruction-following embedding, we show
that the same text will align to different tokens when prompted by different
instructions. Considering a toy example of three sentences:
$(S_{A},S_{B},S_{C})$ and one instruction $I$:

$S_{A}$: I really enjoyed the movie last night.

$S_{B}$: I didn’t enjoy the movie last night at all.

$S_{C}$: I had a great time watching the film this afternoon.
$I$: Classify the emotion expressed in the given Twitter message into one of
the six emotions: anger, fear, joy, love, sadness, and surprise.

where $I$ is introduced by Wang et al. (2023) and used for the
EmotionClassification dataset Saravia et al. (2018). We use LLM2Vec as the
studied LLM and observe whether aligned tokens from the same text differ with
the instruction and without the instruction.

As shown in Table 5, the tokens aligned by all sentences largely changed when
adding $I$. Specifically, when $I$ is not added, all tokens are aligned to the
non-sentiment tokens first. Interestingly, when $I$ is added, $S_{A}$ and
$S_{C}$ is mainly aligned to the tokens related to "joy", while $S_{B}$ is
mainly aligned to the token related to "sadness".

Similarly, we believe that this phenomenon can help to understand how the
instruction-following embeddings work intuitively:

  * •

When no instruction is added, the LLM can only “randomly” select some key
tokens to align. For both $S_{A}$ and $S_{B}$, the LLM happen to both choose
topic-related tokens. As a result, similarity$(S_{A},S_{B})$=0.821 is higher
than similarity$(S_{A},S_{C})$=0.718.

  * •

When the instruction for sentiment classification is added, the LLM
“adaptively” selects the sentiment tokens to align with. As a result,
similarity$(I+S_{A},I+S_{B})$=0.814 is lower than
similarity$(I+S_{A},I+S_{C})$=0.829, .

Setting | Top 5 aligned tokens of $S_{A}$
---|---
-wo $I$ | _Movie _movie _cinema _movies _watched
-w $I$ | _Joy _joy _happiness joy _Love
| Top 5 aligned tokens of $S_{B}$
-wo $I$ | _movie _Movie _movies _cinema _Mov
-w $I$ | _sad _Sad _disappointment _disappointed _anger
| Top 5 aligned tokens of $S_{C}$
-wo $I$ | _afternoon _cinema _movie _Movie _movies
-w $I$ | _joy _Joy joy _happiness _delight
Table 5: Comparison of the aligned tokens when using the instruction or not.

(a) GPT-Neo and SGPT${}_{\text{msmarco}}$

(b) OPT and OPT${}_{\text{EOL}}$

(c) LLaMA and LLaMA${}_{\text{EOL}}$

(d) Mistral and LLM2Vec

Figure 5: The variation in each principal component of the embedding space.

(a) Performance of sparse retrieval based on LLM2Vec.

(b) Performance of sparse retrieval based on GritLM.

Figure 6: Performance Variation of sparse retrieval with hyper-parameters.

Note that a similar phenomenon has also been observed by Peng et al. (2024)
under the special fine-tuning method and the last-pooling strategy. The
phenomenon we observed is more general because LLM2Vec does not even seem to
have any instructions when fine-tuning and is using a weighted-mean pooling
strategy. We similarly emphasize that this interesting phenomenon is present
in most embedding LLMs and is easy to verify.

##  Appendix C Details of Sparse Retrieval

###  C.1 Evaluation Dataset and Metric

Dataset | Domain | #Query | #Corpus | Relevancy
---|---|---|---|---
FiQA | Finance | 648 | 57,638 | Binary
NFCorpus | Medical | 323 | 6,633 | 3-level
SciFact | Science | 300 | 5,183 | Binary
ArguAna | Misc. | 1,406 | 8,674 | Binary
Table 6: Statistics of the evaluation dataset. Relevancy represents the query-
document relation level.

(a) The metrics when the dataset $D$ contains 10K documents sampled from the
SNLI training set.

(b) The metrics when the dataset $D$ contains 10K documents sampled from the
MSMARCO document set.

Figure 7: The comparison of evaluation metric when embedding with eight
$\hat{f}$ and their corresponding $f$.

We provide the statistics of four evaluation datasets in Table 6 and use the
version provided by BEIR131313https://github.com/beir-cellar/beir.. nDCG@10
used for evaluation is the recommended metric for the BEIR Benchmark. The
calculation of nDCG@10 can be divided into two main steps: (1) calculating
DCG@10:

$DCG@10=\sum_{i=1}^{10}\frac{2^{rel_{i}}-1}{\log_{2}(i+1)}$ (17)

where $rel_{i}$ is the relevance score of the $i$-th item, which is usually a
nonnegative integer and $\log_{2}(i+1)$ is the positional discount factor,
which is used to reduce the weight of lower-ranked items because users are
more likely to pay attention to the top-ranked items. (2) calculating
$IDCG@10$ (Ideal DCG@10), which is the DCG value when assuming that the
retrieved results are ordered optimally. This means that the results are
sorted from highest to lowest based on the relevance score. (3) normalizing
$DCG@10$ and obtaining nDCG@10:

$nDCG@10=\frac{DCG@10}{IDCG@10}$ (18)

###  C.2 Implementation Details

We follow the evaluation methods of LLM2Vec and GirtLM by adding different
instructions in front of different datasets. The instruction is given in Table
7. We use Python 3.10 and Pytorch 2.3.0 for the implementation, while our
experiments are all done on a single NVIDIA A100 40GB with CUDA 12.4.

###  C.3 Hyper-parameter Experiment

Since no validation set exists for ArguAna and Scifact, we report the
performance variation on the non-zero number of sparse representation, i.e.,
$K$, and the extended token number of query, i.e., $M$, on the test set of all
four datasets. We find that $K$ has little effect on the results, so selecting
a lower K is a good choice for low storage scenarios. The situation is more
complex for $M$: (1) the performance on FiQA and NFCorpus peaks at $M$=75
while the other two datasets show a steady boost ; (2) when the embedding LLM
is good enough, such as the case of GritLM, even a large $M$ can lead to a
steady boost in retrieval results.

Dataset | Instruction
---|---
FiQA | Given a financial question, retrieve user replies that best answer the question
NFCorpus | Given a question, retrieve relevant documents that best answer the question
SciFact | Given a scientific claim, retrieve documents that support or refute the claim
ArguAna | Given a claim, find documents that refute the claim
Table 7: Instruction used when obtaining embedding from LLM2Vec and GirtLM.

##  Appendix D Additional Results on Spectral Analysis

#### Variation of Principal Components

We show the variation principal component for the remaining 4 embedding LLMs
in Figure 5. We find that, with the exception of LLaMA${}_{\text{EOL}}$, the
embedding spaces of the other three $\hat{f}$ decrease significantly on the
first principal component. We would like to explain the anomaly of
LLaMA${}_{\text{EOL}}$ in terms of the recently popular “Platonic
Representation Hypothesis”Huh et al. (2024). LLaMA${}_{\text{EOL}}$ is based
on prompt engineering and is not considered a powerful embedding model
compared to other $\hat{f}$. According to the “Platonic Representation
Hypothesis”, powerful embedding models always produce convergent embeddings,
while weaker embedding models produce embeddings that will be more disparate
from them. Thus, we conjecture that the anomalies of LLaMA${}_{\text{EOL}}$
indicate precisely that the embedding space generated by it is not good
enough. This is corroborated by the fact that LLaMA${}_{\text{EOL+CSE}}$ in
Figure 3 behaves consistently with other models.

#### Adjusting First Principal Components

In Figure 8, we show the first principal component adjustment corresponding to
the 3 additional $(f,\hat{f})$ pairs. It can be observed that although the
effects vary, the overall adjusting first principal components all align the
embedding to the key tokens, in line with the conclusion of Section 4.

(a) Contribution to the aligned tokens (OPT). (b) Aligned tokens after
adjusting ${\bf u}_{1}$ guided by OPT${}_{\text{EOL+CSE}}$.

(c) Contribution to the aligned tokens (LLaMA). (d) Aligned tokens after
adjusting ${\bf u}_{1}$ guided by LLaMA${}_{\text{EOL+CSE}}$.

(e) Contribution to the aligned tokens (Mistral). (f) Aligned tokens after
adjusting ${\bf u}_{1}$ guided by GirtLM.

Figure 8: Situation of the aligned token when the input text is “Making a
Killing is a 2018 Canadian-American crime-mystery film co-written, co-produced
and directed by Devin Hume.”. Figure (a)-(b) show the situation when $f$ is
OPT, $\hat{f}$ is OPT${}_{\text{EOL+CSE}}$; Figure (c)-(d) show the situation
when $f$ is LLaMA, $\hat{f}$ is LLaMA${}_{\text{EOL+CSE}}$; Figure (e)-(f)
show the situation when $f$ is Mistral, $\hat{f}$ is GirtLM.

##  Appendix E More Results for Analysis

###  E.1 Additional Qualitative Analysis

In Table 8, we provide three more examples from Wiki1M, SNLI, and MSMARCO to
reflect the generalizability of our findings. We observe similar alignment
phenomena as in Section 3.4, demonstrating the generalizability of our
findings.

###  E.2 Additional Quantitative Analysis

Similar to in Figure 2, we computed the same metrics on the SNLI and MAMARCO
document sets and plotted the results in Figure 7. SNLI is dominated by
shorter sentences, whereas MSMARCO is all about longer documents. This changes
the absolute values of LAR and GAR; however, it does not affect the
conclusions in Section 3.5.

Dataset | Input Text
---|---
Wiki1M | Chatwood was chosen for the role as Ubisoft wanted music that
had Persian elements in it to fit the setting, while not being pure Persian
music.
GPT-Neo |  _in _the , _to _" _âĢ _as _and Ċ _a
SGPT${}_{\text{nli}}$ |  _Persian _music _MUS _Music _musical _mus _compos _Persia _Pers _Iranian
SGPT${}_{\text{msmarco}}$ |  _Ubisoft _Music _music _MUS WOOD _soundtrack _playlist Music _XCOM _Persian
OPT |  Ċ _ _The _He _Chat _It _I _This _In _They
OPT${}_{\text{EOL}}$ |  pure not Music We _Persian Not U The music Pure
OPT${}_{\text{EOL+CSE}}$ |  _Chat _chat _music _Music Chat _Persian _Ubisoft chat _musical _Persia
LLaMA |  _The _Ch <0x0A> _He _She _" _U _It _In _This
LLaMA${}_{\text{EOL}}$ |  Ch Pers _Pers _Ch I _we _he the The it
LLaMA${}_{\text{EOL+CSE}}$ |  _Ch _chat _music _Pers chat _Iran Ch _musical _Music music
Mistral |  , _" _in _to _for _as _and _the _a _
GritLM |  _Pers _chat _Chat _wood _U _music Chat _Wood _pers Pers
LLM2Vec |  _Chat _music _chat Chat _U _Pers _Music _wood _Wood chat
Dataset | Input Text
NLI | In 2000, GNP was less than GDP because income receipts from
the rest of the world were less than U.S. payments to the rest of the world.
GPT-Neo |  Ċ _( . , _in _G _the _GDP _and _of
SGPT${}_{\text{nli}}$ |  _less _GN _impover _income _GDP _low _lesser _economic _little _poverty
SGPT${}_{\text{msmarco}}$ |  _GN _GDP GN _Pik _Krugman _Gross Gs _Gn _income G
OPT |  _ Ċ _In _Now _GN _The _Today _That _This _Since
OPT${}_{\text{EOL}}$ |  GN _GN G _less less In The the _the _In
OPT${}_{\text{EOL+CSE}}$ |  _GN _income _GDP _payments _2000 _2001 GN _Income _incomes _Global
LLaMA |  $\backslash$n _In _The _This _G _That _But </s> _However _Net
LLaMA${}_{\text{EOL}}$ |  def the The _the _The In USA _U _trade G
LLaMA${}_{\text{EOL+CSE}}$ |  _income _rece _pay _payment Rece pay _Pay _G _exports _deb
Mistral |  _the , _in _( _of _for . _ _and -
GritLM |  _payments _G _income _world _rece _U _rest _US _the _Pay
LLM2Vec |  _G _income _payments _world _U _less _payment _rece _World _pay
Dataset | Input Text
MSMARCO | Disney’s Theme Parks had an operating cost of 571 million dollars divided by their 11 parks
and being open 365 days a year, on average their operating cost per day is
around $355,000.
GPT-Neo |  _a $\backslash$n _( . _in , _for _and _the _per
SGPT${}_{\text{nli}}$ |  Ĥ¬ _5 _five _operating _365 _$ _cost _55 _operation _operations
SGPT${}_{\text{msmarco}}$ |  _operating _Operating _Theme _theme _operation _OPER _Operation _Parks operation _cost
GPT-Neo |  _a Ċ _( . _in , _for _and _the _per
SGPT${}_{\text{nli}}$ |  Ĥ¬ _5 _five _operating _365 _$ _cost _55 _operation _operations
SGPT${}_{\text{msmarco}}$ |  _operating _Operating _Theme _theme _operation _OPER _Operation _Parks operation _cost
OPT |  _ Ċ _So _That _This _The _They _I _If </s>
OPT${}_{\text{EOL}}$ |  Disney _Disney $ _$ The _operating Cost average the _The
OPT${}_{\text{EOL+CSE}}$ |  _Disney Disney _Disneyland _parks _operating _Walt _5 _costing _annual _park
LLaMA |  <0x0A> 0 _This _That _The _If _Disney _With _I _In
LLaMA${}_{\text{EOL}}$ |  Dis _Disney The the _the _ _per aver Oper oper
LLaMA${}_{\text{EOL+CSE}}$ |  _Disney _park Theme _Park _theme park _cost _operating theme _par
Mistral |  , _ 1 _in . _( _and _per _a 2
GritLM |  _operating _theme _Disney _cost _Theme _day _parks _park _costs _daily
LLM2Vec |  _operating _parks _park _Disney _theme _Park _Theme _Oper _daily Theme
Table 8: The top 10 aligned tokens for eight $\hat{f}$ for text embedding and
their corresponding $f$ for text generation.


# There is no perfect Mondrian partition for squares of side lengths less than
1001.

Natalia García-Colín  Natalia García-Colín, Département d’Informatique,
Université Libre de Bruxelles and Department of Statistical Learning, ScaDS.AI
Leipzig<EMAIL_ADDRESS>,  Dimitri Leemans  Dimitri Leemans,
Département de Mathématique, Université libre de Bruxelles, and Department of
Statistical Learning, ScaDS.AI Leipzig<EMAIL_ADDRESS>,  Mia Müßig
Mia Müßig, Ludwig Maximilian University of Munich, and Department of
Statistical Learning, ScaDS.AI Leipzig<EMAIL_ADDRESS>and  Érika Roldán
Érika Roldán, Max Planck Institute for Mathematics in the Sciences and
Department of Statistical Learning, ScaDS.AI Leipzig<EMAIL_ADDRESS>
###### Abstract.

In mathematics, a dissection of a square (or rectangle) into non-congruent
rectangles is a Mondrian partition. If all the rectangles have the same area,
it is called a perfect Mondrian partition. In this paper, we present a
computational result by which we can affirm that there is no perfect Mondrian
partition of a length $n$ square for $n\leq 1000$. Using the same algorithm we
have been able to establish that there is no perfect Mondrian partition of a
$n\times m$ rectangle for $n,m\leq 400$.

###### Key words and phrases:

Tesselations, Mondrian problem

###### 2020 Mathematics Subject Classification:

52C20, 52-08

##  1\. Introduction

In the Journal of the Archimedeans (Cambridge University Mathematical
Society), number 34, October 1971 [5], Blanche Decartes111Collaborative
pseudonym used by the English mathematicians R. Leonard Brooks, Arthur Harold
Stone, Cedric Smith, and W. T. Tutte. published a note by the title of
_“Division of a square into rectangles”_ as a curious extension of their
classic paper _“The dissection of rectangles into squares”_ [1]. In the
former, they pose and solve the following problem:

“… Instead of dividing a square into rectangles of different sizes but all of
the same shape (namely squares), _one can divide it into rectangles of
different shapes but of the same area_. This leads to a system of nonlinear
equations. The simplest solution is that shown in Fig …”.

Their solution [5] shows that the smallest configuration has seven rectangles
of irrational side lengths. Furthermore they provide a general construction
for dividing any square into $7+n$ equal area rectangles of different shapes
for any $n>0$. This construction became known in the literature as a Blanche’s
Dissection [13].

When one adds the extra requirement that the lengths of the sides of the
rectangles are integers, this dissection problem is known as the _Mondrian art
problem_ in reference to the famous works of the dutch artist Piet Mondrian. A
dissection of a square (or rectangle) into non-congruent rectangles of equal
area and integer lengths is referred to as a _perfect Mondrian partition_. It
is not known whether a perfect Mondrian partition exists at all. However there
has been research related to the so called _defect_ of a Mondrian partition
which is defined as the difference between the area of the smallest rectangle
and the biggest rectangle. Thus, a perfect Mondrian partition has defect zero.

Traditionally the quest for perfect Mondrian partitions has focused on
squares, in this context $M(n)$ denotes the _Mondrian number_ of a square of
size $n$, defined as the minimum defect among all possible Mondrian partitions
of a square of size $n$. As an $n\times n$ square can be partitioned into two
non-congruent parts of roughly equal size, a natural upper bound for $M(n)$ is
$n$ when $n$ is odd and $2n$ when $n$ is even.

It has been proven computationally that $M(n)>0$ for $n\leq 65$, furthermore
all $M(n)$ numbers for $n\leq 65$ are known and can be found as sequence
A276523 of _The On-Line Encyclopedia of Integer Sequences_. The researchers
who found the sequence have conjectured that
$M(n)\leq\lceil(n/\log(n))\rceil+3$. This bound is computationally proven to
hold, through the construction of examples, up to n=96 (see [10] and [11]).

A different approach, introduced in [8] is to study the properties of the
number $x(n)=|\\{x\in\mathbb{N},|x\leq n\text{ and }M(x)\neq 0\\}|$. This
number accounts for all the different numbers smaller than or equal to $n$ for
which there is not a perfect Mondrian configuration. Thus, if there exists a
perfect Mondrian configuration for a value $n^{*}$, necessarily $x(m)<m$ for
any $m\geq n^{*}$. For example, the results of the previous paragraph imply
$x(65)=65.$ In [8] they prove a lower bound for $x(m)$, which was later
improved in [3], namely
$\frac{m}{log(m)}(1+\log(log(m))+\frac{(log(log(m)))^{2}}{2})<x(m)$. This
bound is far from being tight.

There is other recent work in probability inspired by Mondrian partitions. For
example, in [12], a family of geometric stochastic processes that resemble or
are inspired by Mondrian-like configurations has been defined. These Mondrian
processes give, in particular, ways of generating interesting random graph
structures such as random forests [9, 6, 7].

In this paper we present an algorithm that helps us conclude that there is no
perfect Mondrian partition of a length n square for $n\leq 1000$ and that
there is no perfect Mondrian partition of a $n\times m$ rectangle for $n,m\leq
400$.

The results are presented as follows. In Section 2 we prove that a perfect
Mondrian partition, if it exists, needs to have at least seven pieces. In
Section 3, we describe the algorithms we used to check the results mentioned
above.

##  2\. The minimum number of pieces of a perfect Mondrian partition.

Let $n$ and $m$ be two positive integers. A perfect Mondrian partition (PMP)
for the pair $(n,m)$ is a partition of a $n\times m$ rectangle in pairwise
non-congruent rectangles that all have same area. We include some easy
observations about the structure of a PMP (if it exists). As all of these are
necessary conditions for a PMP to exist they have been explicitly or
implicitly used in [8, 3, 4, 5]. We include them here for completeness and
provide a new proof.

######  Lemma 2.1.

A PMP must have at least 7 pieces.

###### Proof.

It is easy to see that any rectangular dissection of a rectangle with two or
three pieces is such that at least two pieces will need to have the same width
or height.

A PMP with four different pieces has to be arranged in such a way that each
piece touches exactly one corner of the rectangle, otherwise it would contain
a smaller three piece PMP. The PMP cannot have exactly 4 pieces, as this would
force them all to be congruent.

Hence if there was a PMP with five pieces , we must have a different rectangle
touching every corner of the dissected rectangle and an internal rectangle
that touches each piece in a configuration similar to that of Figure 1. As
seen in the figure, for this configuration to be a PMP the heights and widths
of the rectangles must satisfy the system of equations:

  * •

$a_{i}\times b_{i}=\frac{n\times m}{5}$,

  * •

$a_{1}+a_{2}=n,\;a_{1}+a_{3}+a_{4}=n,\;a_{4}+a_{5}=n$,

  * •

$b_{1}+b_{5}=m,\;b_{2}+b_{3}+b_{5}=m,\;b_{2}+b_{4}=m$.

Where $n,m$ are the lengths of the sides of the dissected rectangle. This
system can be solved by elementary methods to show that any solution (be it in
the real or integer numbers) forces the rectangles touching opposite corners
to be congruent. Thus there is no PMP with exactly 5 pieces.

$a_{5}\times b_{5}$$a_{4}\times b_{4}$$a_{2}\times b_{2}$$a_{1}\times
b_{1}$$a_{3}\times b_{3}$ Figure 1. The configuration of a theoretical
5-square perfect Mondrian partition.

Suppose that there is a PMP with six pieces. Then we can argue that there must
be a side of the boundary rectangle that touches at least three pieces.
Firstly, having only one piece touching one the sides of the boundary
rectangle is not possible as the remaining five pieces would have to form a
five piece PMP. Secondly, if exactly two pieces touched each of the sides of
the boundary, we would be forced to have a configuration similar to that of
Figure 1 but with two pieces in the center; these pieces would have to be
congruent. Thus there is a side of the dissected rectangle that touches at
least three pieces of the partition, without loss of generality we may assume
this side is the base. The rectangles touching the base all have different
height and neither of them reaches the top, thus, in order to complete the
partition, the one with the lowest height has to have at least two different
rectangles on top and the other two have to have at least one additional
rectangle on top, that makes a minimum of 7 rectangles. ∎

##  3\. Algorithms

Let $n$ be the height and $m$ be the width of the rectangle we want to fill-in
with non-congruent rectangles having the same area. Let $r$ be the number of
pieces we want to use to cover the rectangle. Obviously, $r$ must be a divisor
of $nm$ and each of the pieces will have area $\alpha:=nm/r$. Additionally, as
all rectangles must be pairwise non-congruent, $\alpha$ has to have a large
enough number of divisors, $\\{d_{1},d_{2},\ldots,d_{k}\\}$, such that
$d_{i}\leq n$ and $\alpha/d_{i}\leq m$ for all $i$ . For convenience we may
assume that $d_{1}<d_{2}<\ldots<d_{k}$.

Now consider the following set of tuples of widths and heights;

${\mathcal{P}}(n,m,r):=\\{d_{1}\times\alpha/d_{1},\ldots,d_{k}\times\alpha/d_{k}\\}.$

In the vector $d_{i}=\alpha/d_{k+1-i}$. That is, piece $i$ is a 90 degrees
rotation of piece $k+1-i,$ thus they are congruent and they cannot be
simultaneously used in a successful perfect Mondrian partition.

###  3.1. (Side) Find pieces that could fill one side or the rectangle.

The idea of this algorithm is to check, given a tuple $(n,m,r)$, if we can
find a subset
$\mathcal{S}:=\\{d_{j_{1}}\times\alpha/d_{j_{1}}\ldots,d_{j_{l}}\times\alpha/d_{j_{l}}\\}\subseteq\mathcal{P}(n,m,r)$
such that either the widths of the pieces sum to $n$,
$\sum_{i:=1}^{l}d_{j_{i}}=n$, or the heights of the pieces sum to $m$,
$\sum_{i:=1}^{l}\alpha/d_{j_{1}}=m$.

Thus, this algorithm needs to solve a variation of the famously NP-complete
_Subset sum problem_. For small $n$ and $m$, we can use a simple backtracking
approach to check if a solution exists and even find all solutions, this will
become important in the next section.

We use this approach in conjunction with Lemma 2.1 to show that there is no
PMP of a $n\times n$-square for $n<84$ . The first instance where there exists
a set of at least two pieces whose width (or height) add up to $n$ occurs for
$n=84$, $r=7$, with pieces of area $\alpha=84^{2}/7=1008$. In this case the
set of possible tuples of width and height of pieces is

${\mathcal{P}}(84,84,7)=\\{12\times 84,14\times 72,16\times 63,18\times
48,21\times 42,24\times 36,28\times 28,\linebreak 36\times 24,42\times 21,$
$\ldots,84\times 12\\}.$

Figure 2 shows the width of an $84\times 84$ square filled bye a $12\times 84$
rectangle and a $72\times 14$ rectangle. A quick look at the remaining pieces
allows us to see that the remaining two sides of the $84\times 84$ square
cannot be covered. This finding motivates the next algorithm.

Figure 2. A $84\times 84$ square with bottom horizontal side filled.

###  3.2. (Perimeter) Find rectangles that can be placed around the perimeter.

This algorithm is an extension of the previous one, its purpose is to check
given a tuple $(n,m,r)$, if we can find a subset
$\mathcal{S}:=\\{d_{j_{1}}\times\alpha/d_{j_{1}}\ldots,d_{j_{l}}\times\alpha/d_{j_{l}}\\}\subseteq\mathcal{P}(n,m,r)$
such that a combination of the widths and the heights of the pieces sum to
$2(n+m)$, the perimeter of an $n\times m$ rectangle. Unlike the previous case,
here the geometry plays a bigger role as both the width and height of the four
corner pieces count for the sum, which is not the case for the rest of the
pieces.

Our algorithm checks first for which tuples $(n,m,r)$ there exists a set of
pieces that can cover the perimeter of the square and later it checks if there
is still enough space remaining in the enclosed area to place at least one of
the remaining pieces.

The algorithm begins by using the ”filling one side” algorithm described in
the previous section to find all subsets of the rectangles with a total height
of $n$ and all subsets of the rectangles with a total width of $m$. We call
the former type a ”vertical subset” and the latter a ”horizontal subset”. We
say that a vertical subset is neighboured to a horizontal subset, if both
subsets share exactly one rectangle and we save this relationship in a simple
lookup table. For the purpose of filling the perimeter of the rectangle, we
can use neighboured subsets to fill adjacent sides where the shared rectangle
is placed in the corner.

In practice, the algorithm goes through each vertical subset and checks for
_every pair_ of its neighboured horizontal subsets if they share another
vertical subset as neighbour. In other words, the algorithm tries to find a
four cycle of adjacencies that alternates between vertical and horizontal
subsets. Such a set is a potential candidate for a perimeter of the $n\times
m$-rectangle. In addition, the algorithm must check that the four selected
subsets do not contain duplicate (congruent) rectangles with the exception of
the four corner rectangles; and that the union of the subsets contains at most
$r$ rectangles (since the PMP we are seeking must have $r$ rectangles in
total). If all those conditions are met the four subsets of rectangles are a
viable candidate for a filling the perimeter of a PMP of a rectangle. Note
that this approach does not fix the order of the rectangles not placed in a
corner.

When running the computations in the case of squares for this second part we
find that the first possible $n$ (regardless of $r$) for which we can find a
perimeter is 360. Therefore, we are already able to affirm that there is no
PMP-square for $n<360$.

A perimeter candidate for a square with sides $n,m=360$ has $r=12$, horizontal
sides covered by the rectangles

$[240\times 45,120\times 90],[60\times 180,100\times 108,200\times 54],$

and vertical sides covered by the rectangles

$[240\times 45,80\times 135,60\times 180],[120\times 90,50\times 216,200\times
54].$

The remaining rectangles not used in the perimeter are:

$36\times 300,40\times 270,48\times 225,72\times 150,75\times 144.$

Notice that in this instance the five remaining rectangles must be used in the
partition as $r=12.$ Figure 3 shows a possible arrangement of the perimeter
listed above.

###  3.3. (Gap) Fitting pieces in the smallest gaps formed by the perimeter.

Once a potential perimeter has been computed, we can look at the rectangle
with the lowest height on the bottom side of the perimeter. This rectangle is
sandwiched between two other rectangles, if it is not a corner rectangle, or
it has a rectangle lying on top of it on one side and a rectangle with larger
height on the other side. Either way there is a _horizontal gap_ that forms on
top of said rectangle with the lowest height. This gap has a certain width
that has to be filled exactly by one or several rectangles. For example,
Figure 3, shows such a gap. In that instance the width of the gap is 160 and
it has to be filled in with the following remaining rectangles:

$36\times 300,40\times 270,48\times 225,72\times 150,75\times 144.$

We implemented a check to see if the remaining pieces can fill this gap.
Notice that this process is indifferent to which side we have chosen to be the
_bottom side_ , thus the check can be applied to the four sides.

In the example above, the gap left to be filled on the right side is of lenght
$216$, it is not hard to check that it is impossible to add $216$ exactly with
a combination of the heights or the widths of the rectangles in the list
above. So this case can be discarded.

Utilising the previous three checks (Side, Perimeter, Gap) we are already able
to say that there is no PMP-square for $n<420$.

In the example above, notice that, for the gap of length $160$ left on the
bottom side we do have a possible combination of heights and widths of
rectangles adding to $160$, namely 40+48+72. However, as the height of the
rectangle with width of $40$ is $270$ a quick look at Figure 3 allows us to
see that this rectangle would intersect the rectangles in the top side of the
square. This phenomenon has inspired the next check.

$240\times 45$$120\times 90$$60\times 180$$100\times 108$$200\times
54$$80\times 135$$50\times 216$$160$$216$ Figure 3. An example of a perimeter
with $n=360$ with a hole to fit.

###  3.4. (Hole) Are the remaining rectangles small enough to fit in the hole
formed by the perimeter?

Once a potential perimeter has been computed, we can easily obtain an upper
bound on the size of the hole formed by the perimeter. An upper bound on the
width of the hole, the _mwh_ , can be obtained by deducting from $n$ the two
minimum widths of the rectangles in each of the two vertical subsets.
Similarly, an upper bound on the height of the hole, the _mhh_ , can be
computed by deducting from $m$ the two minimum heights of the rectangles in
each of the two horizontal subsets.

We know that every rectangle not in the perimeter has to have a width smaller
or equal than the _mwh_ and a height smaller or equal than the _mhh_. Thus, if
not enough of the remaining rectangles satisfy this property, we can eliminate
the case. For instance, in the example that we have been using $mwh=250$ and
$mhh=261$ (see Figure 4), but we also know that we need to place all 5
rectangles not in the perimeter in the hole. However, in the list of remaining
rectangles, we have are rectangle of size $36\times 300$ which clearly cannot
fit horizontally or vertically in the hole. Hence, we discard this case.

$240\times 45$$120\times 90$$60\times 180$$100\times 108$$200\times
54$$80\times 135$$50\times 216$$250$$261$ Figure 4. An example of a perimeter
with $n=360$.

Saddly, adding this check does not allow us to immediately improve the
previous bound for $n$ in the case of squares.

However, implementing all these checks together, we can greatly reduce the
number of cases where a _brute force computation_ of all possible cases is
needed. For the case of squares, only the following values of $n<1001$ could
not be ruled out by the Side, Perimeter, Gap and Hole checks:

(1) $\\{420,480,630,660,720,780,840,900,924,960,990\\}$

For these cases we implemented a backtracking algorithm that we describe in
the next section.

###  3.5. The backtracking algorithm

This simple backtracking algorithm will take as input the width and height of
the base rectangle $n$ and $m,$ respectively, and output a PMP if there is one
and FALSE otherwise.

What follows is an outline of the logic behind the algorithm. The full code is
accessible in the following repository.

https://github.com/PhoenixSmaug/Mondrian

Given a pair $(n,m)$ of integers, start by generating the set of all divisors
of $n\times m$, and for each divisor $r\geq 7$ generate the set of all
possible tuples of widths and heights

${\mathcal{P}}(n,m,r):=\\{d_{1}\times\alpha/d_{1},\ldots,d_{k}\times\alpha/d_{k}\\}$

with product equal to $\frac{n\times m}{r},$, such that $d_{i}\leq n$ and
$\alpha/d_{i}\leq m$ for all $i.$ If the cardinality of ${\mathcal{P}}(n,m,r)$
is less than $r$ the case can be discarded. Else, proceed to use the
rectangles to fill in the base of the $n\times m$–rectangle from left to
right.

The data structure we used to keep track of the locations, inside the main
rectangle, that are covered by rectangles at any given time during the
execution is an integer vector, $V,$ of size $n$, that contains, at position
$i$ the height already covered at that width, following ideas of [2].

At any time during the execution, the position chosen as the bottom left
corner of the next rectangle to be placed is the smallest index
$i\in[n]:=\\{1,\ldots,n\\}$ such that $V[i]=\min_{i\in[n]}\\{V[i]\\}.$ It
follows that, when a piece of width $w$ and height $h$ has to be placed in the
main rectangle, we first need to check that it can indeed be placed in the
horizontal gap available, i.e. $V[j]=V[i]$ for all $j\in\\{i,\ldots,i+w-1\\}$.
If that check succeeds, then we fill the vector $V$ with value $h+V[j]$ for
entries $j=i$ to $i+w-1.$ We must also keep track of the rectangles that have
already been used in order to make sure we do not reuse them or their
90-degree-rotations, and also to be able to backtrack easily.

In the case where $n=m$, we are dealing with a square and we can take
advantage of the fact that it has a group of symmetries of order 8 so, we can
potentially avoid making the same computation 8 times. In order to speed up
the search, we make use of two of the symmetries of the square, the _vertical
mirror symmetry_ defined by the vertical line through the midpoints of the two
horizontal sides of the square, and a _diagonal symmetry_ , defined by the
line through the bottom left corner and the top right corner of the square,
see Figure 5). This will allow us to avoid making the same computation 4
times. We believe it will rarely happen that the top left corner will be
reached by the backtracking algorithm and hence, implementing a check to use a
third symmetry to reduce even more the number of cases to be considered will
end up increasing computing time.

Figure 5. The two symmetries of the square used to reduce the search tree.

The chosen diagonal symmetry of the square allows to restrict the search to
the cases where the width and the height of the first rectangle placed
satisfies $d_{i}\leq\alpha/d_{i}.$ This holds because if there was a PMP
corresponding to starting with such rectangle there is a PMP corresponding to
starting with the rotation of such rectangle. Therefore, we can restrict the
first choice to the set of rectangles
$\\{d_{1}\times\alpha/d_{1},\ldots,d_{\lceil\frac{n}{2}\rceil}\times\alpha/d_{\lceil\frac{n}{2}\rceil}\\}.$
The vertical mirror symmetry implies that, when considering a piece in the
bottom left corner that has width $d_{i}$ and height $\alpha/d_{i}$, then the
only pieces to be considered for placement at the bottom right corner must
have width $d_{j}$ and height $\alpha/d_{j}$ with $i<j$. Furthermore, as the
rectangles with index $j\geq k+1-i$ are rotations of the rectangles with index
$j\leq i,$ the diagonal symmetry allows to conclude that we can further
restrict the rectangle to be placed in the bottom right corner to have an
index satisfying $j<k+1-i$.

When $n\neq m$, the diagonal symmetry cannot be used anymore but the vertical
one can. However, in our computations we did not use the vertical symmetry as
it was not drastically reducing the computing time.

###  3.6. Benchmarks

The backtracking algorithm described is very slow, as such, it is better to
use it only for the values of $n<1001$ for which we did not obtain a negative
answer with the Side, Perimeter, Gap and Hole algorithms. That is, the values
in Equation 1. Out of the values in the list, the hardest cases to compute for
the backtracking algorithm were for $n=840$ and $r=20$ or $21$.

Figure 6. Average run-time after 10 samples of checking for each $n\times m$
rectangle with $n,m\leq 400$ if a perfect Mondrian partition exists. Since you
can always rotate the rectangle such that $n\geq m$, the data is mirrored
along the diagonal. The data was collected using the Julia library
”BenchmarkTools.jl” on a PC with an ”AMD Ryzen 9 5950X”.

The logarithmic colour plot visualizes the exponential run-time of the
problem, which depends strongly on the number of divisors of $nm$. This
behavior produces distinct lines of higher run-time for side lengths with many
divisors, such as $240$, $256$, and $360$. On the lower left one can also see
a quarter circle where the product $nm$ is just too small. It should be noted
that the number of divisors is only an orientation of the run-time and, as
with many other NP-complete problems, it is very difficult to predict how
difficult a particular case is.

The cutoff $n,m\leq 400$ was chosen because the run-time increases even
further and the one-time check for each $420\times m$-rectangle with $m\leq
420$ already takes more than two weeks. The $840\times 840$ rectangle has a
run-time of about 400 days, although it should be noted that this is only an
estimate of the program itself and we checked for a Mondrian partition in this
case using parallel computation. To do this, we went through all the
combinations for the placement of the first two rectangles and then dispatched
a thread to check if the rest of the rectangles fit.

## Acknowledgements

Dimitri Leemans acknowledges financial support from the Communauté Française
Wallonie Bruxelles through an Action de Recherche Concertée grant.

## References

  * Brooks et al. [1940] R. Brooks, C. Smith, A. Stone, and W. Tutte.  The dissection of rectangles into squares.  _Duke Mathematical Journal_ , 7, 1940.
  * Chazelle [1983] B. Chazelle.  The bottom-left bin-packing heuristic: an efficient implementation.  _IEEE Transactions on computers_ , c-32(8):697–707, 1983.
  * Dalfó et al. [2021a] C. Dalfó, M. A. Fiol, and N. López.  New results for the Mondrian art problem.  _Discrete Applied Mathematics_ , 293:64–73, 2021a.
  * Dalfó et al. [2021b] C. Dalfó, M. A. Fiol, N. López, and A. Martínez-Pérez.  Decompositions of a rectangle into non-congruent rectangles of equal area.  _Discrete Mathematics_ , 344(6):112389, 2021b.
  * Decartes [1971] B. Decartes.  Division of a square into rectangles.  _Eureka_ , 34, 1971.
  * Martínez and Nagel [2023] S. Martínez and W. Nagel.  Tessellation-valued processes that are generated by cell division.  _arXiv preprint arXiv:2303.16297_ , 2023.
  * Mourtada et al. [2021] J. Mourtada, S. Gaïffas, and E. Scornet.  AMF: Aggregated Mondrian forests for online learning.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 83(3):505–533, 2021.
  * O’Kuhn [2018] C. O’Kuhn.  The Mondrian puzzle: A connection to number theory.  _arXiv preprint arXiv:1810.04585_ , 2018.
  * O’Reilly and Tran [2022] E. O’Reilly and N. M. Tran.  Stochastic geometry to generalize the Mondrian process.  _SIAM Journal on Mathematics of Data Science_ , 4(2):531–552, 2022.
  * Pegg [2016a] E. J. Pegg.  Partition an $n\times n$ square into multiple non-congruent integer-sided rectangles. $a(n)$ is the least possible difference between the largest and smallest area., 2016a.
  * Pegg [2016b] E. J. Pegg.  Mondrian art problem.  Wolfram Demonstrations Project, 2016b.  URL http://demonstrations.wolfram.com/MondrianArtProblem/.
  * [12] D. M. Roy and Y. Teh.  The mondrian process.  In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, _Advances in Neural Information Processing Systems_. Curran Associates, Inc.
  * [13] E. W. Weisstein.  Blanche’s dissection.  MathWorld–A Wolfram Web Resource.