# Language Models Need Inductive Biases to Count Inductively

Yingshan Chang
Carnegie Mellon University
<EMAIL_ADDRESS>
&Yonatan Bisk
Carnegie Mellon University
<EMAIL_ADDRESS>

###### Abstract

A key question for transformers is whether they learn (to approximate)
algorithms or memorize data and interpolate between samples. Testing for
length generalization is the canonical approach to distinguish learning from
memorization. Counting is a fundamental example of generalization, whether
viewed through the mathematical lens of Peano’s axioms defining the natural
numbers or the cognitive science literature for children learning to count.
The argument holds for both cases that learning to count means learning to
count infinitely. While few papers have tried to distill transformer
“reasoning" to the simplest case of counting, investigating length
generalization does occur throughout the literature.

In the NLP community, studies focus on the “train short, test long” paradigm
(Li et al., 2023; Press et al., 2021), where length refers to the training
sentence length. In formal language recognition, automata theory has been used
to characterize the computation model of Transformers, where length may refer
to the input sequence length, or the maximum stack size induced by a pushdown
automata (Del’etang et al., 2022; Liu et al., 2022; Yao et al., 2021). In
general problem solving via either deductive reasoning or learning recursive
algorithms, length may refer to the number of hops in a deductive reasoning
chain or the recursion depth (Dziri et al., 2023; Saparov et al., 2023; Zhang
et al., 2023). For all cases, the ability to count is central to task success.
And crucially, the ability to generalize counting inductively is central to
success on OOD (out-of-distribution) instances.

This work provides extensive empirical results on training LMs (language
models) to count. We experiment with architectures ranging from RNNs,
Transformers, State-Space Models and RWKV. We present carefully-designed task
formats, auxiliary tasks and positional embeddings to avoid limitations in
generalization with OOD-position and OOD-vocabulary. We find that while
traditional RNNs trivially achieve inductive counting, Transformers have to
rely on positional embeddings to count out-of-domain. As counting is the basis
for many arguments concerning the expressivity of Transformers, our finding
calls for the community to reexamine the application scope of primitive
functions defined in formal characterizations. Finally, modern RNNs also
largely underperform traditional RNNs in generalizing counting inductively. We
discuss how design choices that enable parallelized training of modern RNNs
cause them to lose merits of a recurrent nature.

##  1 Introduction

“Difficulty in generalizing to longer instances” is a recurring theme in the
discussion of Transformer limitations, regardless of the task domain (Dziri et
al., 2023; Saparov et al., 2023; Zhang et al., 2023; Del’etang et al., 2022;
Liu et al., 2022; Bhattamishra et al., 2020). We find that, although the
notion of length may vary across domains (e.g. sequence length, recursion
depth, counter states for DSAs, stack sizes for PDAs), counting is always
involved as a required component to successfully handle the task. In fact,
counting might be leveraged by Transformers more often than necessary as it
circumvents the need to implement recurrence. For example, Liu et al. (2022)
indicates that Transformers may rely on internal representations of counts to
model counter languages, as a remedy for its lack of a recurrent mechanism,
but failing immediately on instances with OOD counts. Further, Zhang et al.
(2023) indicates that for recursive problem-solving, specialized attention
heads count the recursion depth, dependent on which depth-specific solutions
are learned. Therefore, counting is crucial for Transformers to perform a
variety of tasks, from formal language recognition to algorithmic reasoning.
And generalizing to OOD counts is crucial for handling longer instances.
However, it remains unclear whether Transformers can learn to count
inductively.

On the other hand, RASP (Weiss et al., 2021), a programming language designed
to mimic Transformer computations, treats counting as a primitive function
based on which more complex algorithms are built (e.g. sorting, reverse,
Dyck). We question the generality of counting as a primitive building block
for Transformer computation. This paper conveys an important message that
counting does not come effortlessly as one might expect for a primitive
function. Nontrivial requirements on positional embeddings, input formats, and
the amount of training have to be satisfied in order for a Transformer to
learn counting in-domain. Moreover, Transformers do not learn to count
inductively, e.g. when the model knows increment(50)=51, it still cannot
output the length of a 51-symbol sequence as 51 if it has only been trained on
up to 50-length sequences. Notably, in this work we do a direct comparison
with both modern and classical recurrent architectures to begin elucidating
the source of this modern limitation, not shared by previous approaches.

We conduct extensive experiments training Transformers to count inductively.
We carefully design the input-output formats, auxiliary tasks and positional
embeddings to overcome the OOD-position and OOD-vocabulary issues. However, we
find negative evidence. Shallow 1L or 2L Transformers struggle to generalize
inductively. Successful generalization is observed with 4L Transformers, but
requiring different positional embeddings for different forms of counting.
Expanding our comparison to recurrent architectures, we find that RNN and LSTM
succeed at everything we have asked, whereas newer RNN architectures (e.g.
State-Space Models and RWKV) have degraded performance. Our work opens up
attractive challenges for augmenting Transformers with a counter-equivalent
mechanism, as well as hybridizing Transformer and RNN without breaking their
inherent strengths. 111 Code and data are released
https://github.com/zdxdsw/inductive_counting_with_LMs

##  2 Background

The inductive counting principle: If a word in an ordered number word list
refers to sets with cardinality $n$, then the next word refers to sets with
cardinality $n+1$.

###  2.1 Definition of Counting

We define counting as the ability to map a number word to the cardinality of a
set containing a corresponding number of items. The crucial inductive step
requires that, having learned the mapping of the first $n$ words to the first
$n$ cardinality values, one has to infer that adding one more item results in
a cardinality value corresponding to the $(n+1)^{th}$ word in the number word
list. This definition of counting is extensively studied in a branch of
cognitive science concerning how children learn to count (Davidson et al.,
2012; Rousselle and Vossius, 2021; Sarnecka and Carey, 2008; Spaepen et al.,
2018). The cognitive science research informs that children learn to count
from 1 to 5 independently in early ages, then drastically generalize to the
entire natural number system by inductively inferring how the number words in
one’s native language map to cardinality values (Wynn, 1992; Margolis and
Laurence, 2008). Further, the structure of the language (e.g. avoiding special
cases or change of bases) correspond to learning to count earlier in childhood
(Rousselle and Vossius, 2021).

Note how counting differs from knowing the ordered list of number words:
reciting the number word list constitutes an important prerequisite of
counting, but establishing the mapping of numbers from the language context to
the cardinal context is the core problem of interest. Also note that the
complexity of number words may vary across languages. This would only affect
the difficulty of learning the number word list, without changing the
requirements for establishing the mapping and performing induction. Thus, the
counting task studied in this paper is language-independent, and we use arabic
numerals, without loss of generality, for notational consistency. To avoid
confusion between number words and cardinality values, in our writings we use
arabic numerals with single quotation to denote numbers in the language
context (e.g. ‘3’), and use arabic numerals with vertical bars (e.g. |3|) to
denote numbers in the cardinal context. Numbers in the language context are
treated in the same way as input/output tokens in a language model, whereas
numbers in the cardinal context may only appear as internal states and its
exact form may vary across individuals.

###  2.2 The Transformer Architecture

A Transformer takes a discrete sequence as input and outputs a discrete
sequence. The input and output sequences share a vocabulary $\mathrm{\Sigma}$.
The embedding and unembedding layers project a one-hot vector with dim =
$|\mathrm{\Sigma}|$ to the Transformer’s hidden_dim and back to
$|\mathrm{\Sigma}|$.

Between the embedding and unembedding layers are $\mathrm{L}$ layers of
interleaved self-attention and MLP blocks, with LayerNorm and residual
connections inserted at appropriate locations. For an intuitive understanding,
self-attention layers communicate information across tokens, while MLP layers
allow each token to update information across the feature dimension (i.e.
hidden_dim) individually. Importantly, parameters are shared across tokens,
and all input tokens perform the same operation in parallel rather than
sequentially. Equation 1 mathematically defines the self-attention function.

$\mathrm{Attn}(Q,K,V)_{t}=\frac{\sum_{i=1}^{T}e^{q_{t}^{T}k_{i}}\odot
v_{i}}{\sum_{i=1}^{T}e^{q_{t}^{T}k_{i}}}$ (1)

Since all input tokens perform the same operation in parallel, the Transformer
does not intrinsically distinguish tokens based on positions. Thus, positional
information is needed to break this symmetry.

Sinusoidal Positional Embedding (Sine)(Vaswani et al., 2017) Sinusoidal PE
computes positional embeddings based on sine waves, which is added to token
embeddings at the input layer.

Absolute Positional Embedding (APE)(Devlin et al., 2019) APE assigns learnable
vectors to position ids $1,...,\mathrm{P}$, which is added to token embeddings
at the input layer.

Rotary Positional Embedding (RoPE)(Su et al., 2021) RoPE multiplies query and
key vectors by an unlearnable rotation matrix, such that the relative rotation
angle between two positions captures relative position. It requires a maximum
sequence length $\mathrm{P}$ to be predetermined.

Scaler Positional Embedding (SPE)(Yao et al., 2021) SPE sides aside one
dimension from the Transformer’s hidden_dim and inserts positional information
through a scaler value. Proposed by Yao et al. (2021) who found SPE’s
advantage over APE in modeling Dyck languages with bounded depth.

No Positional Embedding (NoPE) NoPE denotes the vanilla Transformer without
positions. Haviv et al. (2022) suggests that the causal mask could leak
positional information, by potentially allowing each token to count the number
of predecessors. However, this raises the same question of whether
Transformers can count. Thus, our experiments with NoPE will also inform how
reliable Transformers figure out absolute positions solely from causal masks.

A model easily falls apart if it has never seen the embedding for a position
beyond the training length. To tackle the OOD-position issue Kiyono et al.
(2021) proposes to augment the input position_ids with a random shift (shifted
PEs) so that you start numbering positions from a random integer between 1 and
$\mathrm{P}$, instead of always starting from 1. This ensures that all
position embeddings will be trained. Ruoss et al. (2023) proposes a more
general augmentation (randomized PEs), where the position_ids for a length=k
sequence is the sorted list of k integers randomly drawn from [1,
$\mathrm{P}$]. We empirically find that randomized PEs perform much worse than
shifted PEs. Thus we adopt shifted PEs.

###  2.3 Recurrent Architectures

A recurrent architecture, at each step, maintains a hidden state, updates the
hidden state when consuming a new input, and produces an output based on both
the current hidden state. We denote these three key operations, namely
reception, transition and emission, by $i\rightarrow h$, $h\rightarrow h$, and
$h\rightarrow o$, respectively. A standard (Elman) RNN implements these three
steps as a matrix multiplication followed by a nonlinear activation
($\sigma$). An LSTM adopts additional parameters to compute multiplicative
gates for these three steps, achieving more effective forgetting and memory.

$\centering
h_{t}=\sigma(\mathbf{W_{hh}}h_{t-1}+\mathbf{W_{ih}}x_{t}+b_{h})\qquad
o_{t}=\sigma(\mathbf{W_{ho}}h_{t}+b_{o})\@add@centering$ (2)

#### State Space Models (SSM)

also incorporate reception, transition and emission operations (Eq. 3).
Moreover, there is a feedthrough matrix $\mathbf{W_{io}}$ directly sending
information from the input to output, bypassing the hidden
state.222$\mathbf{W_{ih}}$, $\mathbf{W_{hh}}$, $\mathbf{W_{ho}}$ and
$\mathbf{W_{io}}$ correspond to $\mathbf{B}$, $\mathbf{A}$, $\mathbf{C}$ and
$\mathbf{D}$, respectively, in the SSM community. Importantly, an SSM differs
from a standard RNN in omitting the nonlinearity in state transitions. This
enables a reparameterization of SSMs into a convolutional form, presented in
Equation 4. The kernelization trick is essential for parallelization during
training.

$\centering h_{t}=\mathbf{W_{hh}}h_{t-1}+\mathbf{W_{ih}}x_{t}\qquad
o_{t}=\mathbf{W_{ho}}h_{t}+\mathbf{W_{io}}x_{t}\@add@centering$ (3)
$\centering
o=x\ast\mathbf{K}\qquad\mathbf{K}=(\mathbf{W_{ho}}\mathbf{W_{ih}},\mathbf{W_{ho}}\mathbf{W_{hh}}\mathbf{W_{ih}},...,\mathbf{W_{ho}}\mathbf{W_{hh}}^{k}\mathbf{W_{ih}},...)\@add@centering$
(4)

#### Linear Attention

Zhai et al. (2021), aims to substitute dot-product attention with sub-
quadratic complexity. Linear attention initially suffered from severe
performance drop, but was recently revitalized by the RWKV model family,
introducing input-dependent parameters to boost performance. At the core of
RWKV is the wkv operation where $q_{t}^{T}k_{i}$, as in attention, is replaced
by a weighted sum of history states with discounted weights. A major
innovation of RWKV-v6 versus previous RWKV models lies in input-dependent
derivation of the decay factor $w$.

$wkv_{t}=\frac{\sum_{i=1}^{t}\big{(}e^{-(t-1-i)w+k_{i}}\odot
v_{i}\big{)}+e^{u+k_{t}}\odot
v_{t}}{\sum_{i=1}^{t}e^{-(t-1-i)w+k_{i}}+e^{u+k_{t}}}$ (5)

The discounted moving average of history states can be rewritten in a
recurrent form, thereby exhibiting a flavor of state transition.

$\text{let}\ \alpha_{t}=\sum_{i=1}^{t}\big{(}e^{-(t-1-i)w+k_{i}}\odot
v_{i}\big{)},\ \text{then}\ \alpha_{t}=e^{-w}\alpha_{t-1}+e^{k_{t}}\odot
v_{t}$ (6)

###  2.4 Axes of Sequential Computation in Different Architectures

The induction step of counting can be trivially afforded by sequential
modeling, where “adding one more item to the set” is operationalized as the
model consuming one more input, and the increment on cardinality is
operationalized as unrolling one more step along the sequential axis. The axes
for sequential computation occur at different places for different
architectures (Table 1). Our work reveals the implication of these differences
on counting. In Transformers, due to the parallel processing of attention, in
order for a token to build on the computation results of its predecessors, it
has to proceed to the next layer. Thus, sequential computation occurs along
the axis of Transformer layers. In RNNs, sequential computation is realized
through state transitions. SSMs share the concept of state transition with
RNNs, but have varied implementations specific to individual models.

Architectures |  Repetitive components that realize sequential computation
---|---
Transformer |  Attention + MLP Blocks
RNN |  Matrix Multiplication +
LSTM |  Matrix multiplication +  \+ Multiplicative gating
S4, Mamba |  Matrix multiplication
Linear Attention (e.g. RWKV) |  Moving avg. of history with discounted weights
Table 1: Sequential computation enjoys the reuse of computation performed in previous steps and is realized along different axes in different architectures. Task Variants |  Encoder Setting |  Decoder Setting
---|---|---
Counting \+ Helper Object |  |
Counting \+ Helper Object \+ Shifted Start |  |
Counting \+ Shifted Start |  |
Modular (mod4) |  |
Selective |  |
Selective \+ Modular (mod2) |  |
Table 2: Illustration of counting tasks formats. In row 1-2, banana (‘b’) is
the helper object, to be seen with larger counts, while apple (‘a’) is the
main object, seen with restricted counts during training and tested with OOD
counts. In row 4 & 6, we show examples with mod4 & mod2 for conciseness, while
adopting mod10 & mod4, respectively, in our experiments. In row 5-6, apple and
kiwi represent two different objects, each maintaining its own counter. In our
experiments, we adopt 10 unique objects.

##  3 General Experimental Setup

Denote the maximum counting sequence length in training by N and the maximum
counting sequence length in testing by M. In our experiments, we adopt N=50
and M=100. We train 1, 2, 4-layer Transformers to count, where the input
sequence contains the object of counting, e.g. ‘a’, while the output sequence
is the ordered number word list, aligned to the input sequence such that each
token is essentially counting the number of its predecessors (including
itself). Our models are restricted to be shallow because counting should not
take much computation if it truly serves as the primitive building block for
other complex functions. Weiss et al. (2021) suggested that computing the
length of a sequence can be done within one layer. We generously increase the
budget to four layers. We follow the standard GPT-2 implementation,3338 heads,
1,024 dim and 4,096 MLP-dim. LR=1e-4 with 3k steps of linear warmup. Batch
size is 32. Models usually show signs of overfitting within 300k steps, at
which point we stop training. If the model show signs of continued
improvement, we train up to 625k steps. For each experiment, we use five
random seeds and report the best performance.

##  4 Counting

Training a model to count inductively requires us to provide 1) An ordered
number word list covering the full set of cardinality values, 2) Examples of
mapping between number words and sets of objects for small cardinalities.
Crucially, the full list of ordered number words should be taught without
exposing the model to any set of objects with an out-of-distribution
cardinality. Considering this, a vanilla approach would be to add the
succession sequence, i.e. ‘1’, ‘2’, …, to the training data. However, this is
largely ineffective, as shown in Table 3. This is because the model would
easily master the succession sequence by modeling the bi-gram statistics,
which brings no help to counting.

A more helpful approach is to teach counting with a “helper" object, which is
seen up to the cardinality of M. The cardinality of the main object remains to
be bounded by N in training. In fact, the helper token trivializes
generalization. Intuitively, this task asks: “If you have learned to count
bananas up to 100, but you have never seen as many as 100 apples, can you
count apples up to 100?" (Table 2, row1). Though generalization under this
setting does not require induction, we view this task as a useful sanity-check
because it is undesirable to establish the counting ability tied to specific
objects.

Next, we propose “shiftedstart", a modification to the input-output format, to
simultaneously achieve 1) full exposure of the vocabulary (as well as its
ordering) and 2) bounded exposure of cardinalities. Given that, we can test
generalization with the OOD cardinalities. Concretely, we insert a number word
(k) at the initial position to shift the beginning of the output counting
sequence from 1 to k+1. We illustrate this in Table 2, row 3. Compared to the
helper object setting, the shiftedstart setting imposes a greater challenge
since a cardinality above N is strictly absent from training data. Moreover,
shifted starts discourages a model to exploit a rigid mapping from input
positions to outputs — an undesirable solution that may inflate performance.
Finally, we also experiment with a “Helper Object + Shifted Start" to enrich
the evidence that our task design does not permit easily-hackable solutions.

|  | NoPE | Sine | APE | RoPE | SPE
---|---|---|---|---|---|---
Task |  L |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD
Counting \+ Succession |  2 |  2.0 |  0.0 |  100 |  0.0 |  100 |  0.0 |  2.0 |  0.0 |  100 |  0.0
|  4 |  2.0 |  0.0 |  100 |  0.0 |  100 |  0.0 |  2.0 |  0.0 |  100 |  0.0
Table 3: Transformer counting results, where the vocabulary corresponding to
OOD cardinality values is exposed via the succussion sequence, e.g. ‘1’, ‘2’,
.., ‘100’. Positional embeddings are augmented with random shift by default.
OOD accuracies are only calculated at extrapolation positions. Models achieve
perfect accuracy on reciting the succession sequence. The poor counting
results clearly show that augmenting training data with the ordered number
word list offers no assistance to counting.

The core results from these settings and their interaction with the
aforementioned positional embeddings are presented in Table 4. Rows 1-3 show
the counting performance of Transformers, with the training data augmented
with a helper object, shifted starts, or both. A helper object indeed makes
the task easier, as evidenced by near-perfect OOD accuracy of all five
positional embeddings. When the order of number words is only exposed by
virtue of the shifted starts, only a 4L RoPE Transformer is able to
generalize. The poor results for 1L and 2L models suggest that counting in
Transformers may require a non-trivial computation budget. This initial result
already calls into question the validity of treating counting as a primitive
operation in existing papers. Further, reasoning problems that treat counting
as a primitive operation would impose larger demands in order for inductive
generalizations. Otherwise, instances with larger counter states should be
explicitly demonstrated during training. Extrapolation to larger counter
states do not trivially emerge as a result of mastering in-domain data. A more
generous read is that current results relying on counting should only be
interpreted as valid for in-domain settings — not as general computational
engines as papers often characterize them.

|  | NoPE | Sine | APE | RoPE | SPE
---|---|---|---|---|---|---
Task |  L |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD
Counting \+ Helper Object |  2 |  100 |  100 |  100 |  76.4 |  100 |  80.6 |  100 |  100 |  100 |  92.9
|  4 |  100 |  100 |  100 |  71.7 |  100 |  69.3 |  100 |  100 |  100 |  99.8
Counting \+ Helper Object \+ Shifted Start |  1 |  100 |  4.1 |  99.7 |  0.0 |  100 |  13.6 |  100 |  7.4 |  100 |  4.1
|  2 |  100 |  100 |  100 |  100 |  100 |  81.34 |  100 |  78.7 |  100 |  18.3
|  4 |  100 |  100 |  100 |  95.6 |  100 |  100 |  100 |  100 |  100 |  99.8
Counting \+ Shifted Start |  1 |  100 |  16.7 |  100 |  4.3 |  100 |  50.5 |  100 |  37.7 |  100 |  9.0
|  2 |  100 |  25.0 |  100 |  78.7 |  100 |  27.8 |  100 |  92.5 |  100 |  57.8
|  4 |  100 |  46.1 |  100 |  48.6 |  100 |  51.9 |  100 |  100 |  100 |  83.8
Modular (mod10) |  1 |  11.8 |  11.8 |  100 |  100 |  100 |  71.2 |  11.8 |  11.8 |  100 |  8.2
|  2 |  12.0 |  11.8 |  100 |  100 |  100 |  100 |  11.8 |  11.8 |  100 |  8.2
|  4 |  11.8 |  11.8 |  100 |  100 |  100 |  100 |  11.8 |  11.8 |  100 |  12.1
Selective |  1 |  96.0 |  9.3 |  99.5 |  68.8 |  100 |  10.6 |  99.7 |  29.9 |  99.8 |  61.3
|  2 |  99.7 |  94.1 |  99.8 |  32.6 |  100 |  13.9 |  99.7 |  49.1 |  99.7 |  86.9
|  4 |  99.7 |  100 |  100 |  100 |  100 |  100 |  99.7 |  52.5 |  99.4 |  98.2
Selective \+ Modular (mod4) |  2 |  92.3 |  56.4 |  96.5 |  47.4 |  99.8 |  27.2 |  98.1 |  32.3 |  99.7 |  46.8
|  4 |  97.4 |  91.8 |  100 |  98.2 |  99.9 |  97.3 |  98.5 |  39.8 |  98.2 |  54.6
Table 4: Top: Transformer counting results. We teach the model number words
covering both IND and OOD counts, without exposing the model to OOD
cardinalities. This is ensured via either an auxiliary task involving a helper
object, or modifying the input-output format with a shifted start. Bottom:
Transformer counting for the modular or selective variants (or both).
Positional embeddings are augmented with random shift by default. We denote
Layers, L, and In/Out-of distribution as IND/OOD. OOD accuracies are only
calculated at extrapolation positions

#### Modular Counting

In the previous section, we find that Transformers largely failed to
generalize inductively except for those equipped with RoPE. This calls for the
next question: If it is too hard for Transformers to simulate “unbounded
counters", can they simulate modular counters — only requiring a finite
counter states? Modular counting will not run into the OOD-vocabulary issue,
so remedies we apply in the last section, including the helper token or
shifted starts are no longer necessary. However, modular counting introduces
additional complexity for modelling periodicity. We believe modular counting
should be as powerful as “unbounded counting" because, for example, a stack of
mod10 counters, coordinating appropriately, would give us the entire natural
number system. Table 4 row 4 shows that only APE and Sinusoidal PE generalize
well on modular counting. NoPE and RoPE failed catastrophically, not even
fitting the training data. The failure of RoPE is particularly interesting
because one would expect its formulation to inherently informs periodicity.
SPE achieved perfect training acc but performs at random on testing examples.
This implies that SPE can count modularly only for in-domain iterations,
breaking immediately once extrapolation is required.

#### Selective Counting

We examine whether Transformers can selectively count predecessors satisfying
a condition. In the counting context, selective counting is worth exploring
because when an unbounded counter is approximated via a modular counter stack,
counters above the first level will have to perform selective-modular
counting. More broadly, selectivity is important because observations that
carry useful information are sparse — the same consideration that motivates
Mamba’s proposal of selective-scan (Gu and Dao, 2023). In the general form of
selective-counting, a predicate function $\mathrm{pred}$ can be learned such
that each token $x$ outputs the number of predecessors $x_{i}$ where
$\mathrm{pred}(x,x_{i})=\mathrm{True}$. This corresponds to the
“selector_width" primitive in RASP. Our experiments simply regard the identity
indicator function as the selection condition. Learning predicate functions
adds complexity along an axis orthogonal to inductive counting, which we leave
for future research.

Note, we remove the requirement for generalizing to OOD counts via induction
on the mapping between vocabulary and cardinality, because this is the primary
subject of discussion in Section 4. In this section, we focus on the
additional challenge related to selectivity. We generate the training data
containing ten unique tokens such that the count of each unique token ranges
from zero to ten. In the testing data, we also ensure that the counts do not
exceed ten. However, our testing sequences are longer than the maximum
training length. Thus, the summation of counts for all tokens, as well as the
range of dependency in order to perform selection, are OOD.

Table 4 row 5 shows the results for selective counting. All PEs except for
RoPE succeed given 4 layers. The observation that NoPE outperforms other PEs
on selective counting is interesting. It suggests that causal masking may
indeed provide a viable path for calculating the number of predecessors a
token attends to. In this case, the model will not need PEs to break symmetry.
And, in fact, our results indicate that PEs might unintentionally introduce
exploitable shortcuts harmful to generalization. Finally, we perform
experiments on selective-modular counting. We adopt a smaller base (4 instead
of 10), in order to prevent a substantial growth of sequence length, since a
selective counting sequence contains 10 unique tokens interleaved together,
unlike a homogeneous sequence in previous counting tasks. Results are shown in
Table 4 row 6, which demonstrate a clear message: only PEs — Sinusoidal and
APE — which generalizes on both modular counting and selective counting
performs well on selective-modular counting. NoPE also achieves a fairly good
performance on selective-modular counting, in contrast to its poor performance
on modular counting, perhaps due to the difference in the modular bases (i.e.
mod10 in modular counting vs. mod4 in selective-modular counting).
Investigation of how performance correlates with modular base is left to
future work.

There are two major takeaways from our Transformer counting experiments: 1)
When counting is treated as a primitive towards more complicated reasoning, it
is better to cover all possible counter states in-domain, as Transformers
struggle to count inductively and rely on explicit encounter with each
cardinality value. 2) Different positional embedding designs exhibit strength
in different forms of counting. Put concisely, RoPE succeeds at unbounded
counting with shifted starts; Sinusoidal PE and APE generalize at both modular
and selective counting; NoPE and SPE are only competitive on selective
counting. Our results motivate the development of smarter information routing
inside a Transformer, or integration of multiple PE schemas to take advantage
of orthongonal strengths.

|  | RNN | LSTM | S4 | Mamba | RWKV-v6
---|---|---|---|---|---|---
Task |  L |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD
Counting \+ Helper Object |  1 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  15.5 |  100 |  100
|  2 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  12.07 |  100 |  100
|  4 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  76.5 |  100 |  100
Counting \+ Helper Object \+ Shifted Start |  1 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  1.5 |  100 |  3.2
|  2 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  5.1 |  100 |  0.0
|  4 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  100
Counting \+ Shifted Start |  1 |  100 |  100 |  100 |  100 |  100 |  96.3 |  100 |  7.8 |  99.9 |  29.4
|  2 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  99.9 |  100 |  30.8
|  4 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  97.5 |  100 |  93.8
Modular (mod10) |  1 |  100 |  100 |  100 |  100 |  100 |  98.3 |  91.8 |  11.5 |  100 |  8.2
|  2 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  11.1 |  100 |  11.0
|  4 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  16.6 |  100 |  12.8
Selective |  1 |  99.3 |  94.5 |  100 |  100 |  78.3 |  59.3 |  100 |  99.8 |  100 |  100
|  2 |  99.4 |  95.1 |  100 |  100 |  91.3 |  66.7 |  100 |  96.6 |  100 |  100
|  4 |  97.8 |  85.3 |  100 |  100 |  98.3 |  72.9 |  100 |  97.0 |  100 |  100
Selective and Modular (mod4) |  1 |  100 |  100 |  100 |  100 |  87.7 |  27.8 |  58.4 |  28.2 |  98.5 |  83.1
|  2 |  100 |  100 |  100 |  100 |  92.9 |  31.4 |  99.4 |  60.7 |  99.2 |  56.5
|  4 |  100 |  100 |  100 |  100 |  99.2 |  37.8 |  100 |  59.7 |  100 |  56.8
Table 5: Results for recurrent architectures (in-distribution, IND, and OOD).
OOD accuracies are only calculated at extrapolation positions. Note, that
while carefully compare counting paradigms and design decisions to enable
transformers to count, the simple RNN is able to do everything we have asked,
and the newer architectures have degraded performance.

##  5 Counting in Other LM Architectures

As counting is a fundamentally recurrent task, it is natural to validate our
conditions on recurrent architectures. Both the explicit modeling of hidden
state transitions, and the sequential unrolling of computation along the input
sequence dimension, naturally facilitate inductive counting. We first
demonstrate the performance of RNN Elman (1990) and LSTM Hochreiter and
Schmidhuber (1997) models in Table 5 col 1-2. Note, there exists prior work
hinting at counting in such architectures Shi et al. (2016); Suzgun et al.
(2019), but not directly evaluated in a systematic comparison. The traditional
architectures achieve perfect generalization with a single layer, except that
RNN slightly falls short on selective counting. This highlights that a
recurrent bias is likely key for inductive counting, which is precisely what
the Transformer lacks and must therefore rely on PEs as substitute.

The recent literature has seen a resurgence of modern RNN architectures (Gu
and Dao, 2023; Gu et al., 2021a; Peng et al., 2023, 2024) claiming to enjoy
the best of both worlds: parallelizable training, like Transformers, and
recurrent inference, like RNNs. It is important to investigate whether the
recurrent formulation of these architectures affords inductive counting in the
same way as traditional RNNs. To this end, we choose three modern RNNs — S4
(Gu et al., 2021a), Mamba (aka S6) (Gu and Dao, 2023) and RWKV-v6 (aka
Finch)(Peng et al., 2024) that rival Transformers on large-scale LM
benchmarks. We select the most performant hyperparameters for each individual
architecture.444lr $\in\\!\\{5e\\!-\\!5,1e\\!-\\!\\{4,3,2\\}\\}$, w_decay
$\in\\!\\{0.0,0.01,0.001\\}$, dim $\in\\!2^{\\{5,7,10\\}}$, dropout
$\in\\{0.0,0.1\\}$, batch=32 Task formats remain the same as our Transformer
experiments. Results are shown in Table 5 col 3-5. Somewhat surprisingly,
modern RNNs generalize much worse than traditional RNNs on counting. We
suspect the reason lies in less flexible state transitions, especially for
Mamba and RWKV. The very design that enables parallel training through
reformulating the model into the “convolutional mode" also limits the
expressivity of state transitions. As illustrated in Table 1, while
traditional RNNs apply a nonlinearity to state transitions, modern RNNs only
apply matrix multiplication or linear interpolation to history states, for the
sake of easy contraction of multiple sequential updates into a single
computation step. Our work demonstrates a potential limitation of this design,
and opens up questions about how the limitation on counting will carry over to
reasoning in real applications. A key question for future work is which
architectural elements imbue the necessary inductive biases for RNN counting,
and how can these be transferred to new architectures.

##  6 Related Works

Formally characterizing Transformer expressivity RASP (Weiss et al., 2021)
introduces a functional library of Transformer capabilities, based on the
Python programming language. It lays an important foundation for follow-up
works to expand on. For example, Tracr (Lindner et al., 2023) proposes a
compiler that allows for automatic crafting of Transformer weights from a RASP
script. This facilitates the comparison of solutions learned through SGD
versus “canonical” ones a human would create. Zhou et al. (2023) updates the
RASP library by adding more realistic assumptions on the numerical bounds, as
well as how the position indexes can contribute to the computation graph.

Others characterize Transformer computations from the perspective of boolean
circuits (Cong et al., 1996; Yang and Chiang, 2024; Strobl et al., 2024;
Merrill et al., 2022), where primitives are atomic boolean operations. This is
distinct from RASP, Tracr and our work, as we deal with functional primitives,
but may contribute complementary insights. Also note that there lacks
empirical validations accompanying this line of research, opening the room for
future work to bridge this gap.

Transformers can be analyzed through Automata Theory (Liu et al., 2022;
Del’etang et al., 2022). This branch has not reached agreement on where the
hard boundary for Transformer’s capacity lies. For example, while (Hahn, 2020)
proves the hard limits of self-attention on modeling Dyck, (Yao et al., 2021;
Ebrahimi et al., 2020) demonstrated empirical success. We believe that nuances
regarding the task format, architectural modifications and the definition of
generalization vary across studies. It invites significant future
contributions to either remove this complication or unify these nuances.

Empirically assessing Transformer expressivity Closely complementing the
theoretical progress, abundant prior works have empirically studied the
capacity of Transformer-based LMs. Categorizing by scale, these works include
1) testing Transformers with hand-constructed weights (Chiang and Cholak,
2022); 2) testing Transformers trained from scratch (Del’etang et al., 2022;
Abbe et al., 2023; Ebrahimi et al., 2020; Zhou et al., 2023; McLeish et al.,
2024); and 3) testing pretrained LMs with finetuning (Anil et al., 2022) or
prompting (Zhou et al., 2022). Categorizing by task design, prior works
usually adopt synthetic tasks organized into hierarchies, with a notion of
complexity informed by formal languages (Del’etang et al., 2022; Zhou et al.,
2023; Hao et al., 2022; Liu et al., 2022; Kazemnejad et al., 2024; Ebrahimi et
al., 2020; Ruoss et al., 2023) or boolean functions (Bhattamishra et al.,
2022; Abbe et al., 2023). Our work contributes to this body of empirical
evidence. Our task design additionally draws inspiration from cognitive
science. Of particular note is that Zhou et al. (2023) also studied counting,
which differs from ours by definition: the input includes a start and an end
token, the output is an incremental expansion, e.g. 12 16 > 12 13 14 15 16. We
believe that this can be handled by mastering the succession sequence plus a
termination checking. Hence, their definition of counting involves neither
numbers in the cardinality context nor induction.

Recurrence with attention Many studies attempt to promote new architectures
that address the fundamental tradeoff between efficient training and efficient
inference. Transformers achieve the former thanks to the parallel attention
mechanism, while an RNN features the latter with linear time complexity and
constant history memory. Towards achieving the best of both worlds, previous
works have focused on either proposing attention-ish mechanisms with
subquadratic time complexity (Zhai et al., 2021; Peng et al., 2023, 2024), or
modernizing RNN to permit parallelized training (Gu et al., 2021b; Gu and Dao,
2023; Nguyen et al., 2024). We refer the reader to Tiezzi et al. (2024); Wan
et al. (2023) for surveys on this emergent area. Extending the expressivity
analysis for Transformers to these new RNN architectures (Merrill, 2019;
Merrill et al., 2024) would be a fruitful direction.

##  7 Conclusion

Building on a growing body of work on formalizing the computation in
Transformers, this work investigates counting, which is believed to be a
primitive function enabling a Transformer to perform a wide range of complex
tasks, such as modeling counter languages (Bhattamishra et al., 2022; Hao et
al., 2022; Ebrahimi et al., 2020), simulating algorithms (Anil et al., 2022;
Zhong et al., 2024; Veličković et al., 2022), and tracking the depth of
reasoning chain (Saparov et al., 2023). However, there is an important
distinction between counting in-domain and counting infinitely, which is
understudied in the literature. While counting in-domain can be achieved with
various approximations, counting infinitely imposes a significant challenge
concerning induction and extrapolation. We provide extensive empirical
evidence showing that 1) Counting is not a primitive function of Transformer
computation as others have claimed, as it may require multiple layers to
succeed at counting in-domain; 2) Different positional embeddings enable out-
of-domain generalization in different forms of counting. Our findings have
implications for avoiding out-of-distribution counter states in practical
scenarios and the promise of integrating different positional embeddings. We
also extend our investigation to recurrent architectures, including both
traditional and modern models. We observe that while traditional RNNs easily
generalize counting inductively, no single modern RNN generalizes on all six
variants of our counting tasks, implying that inductive counting not only
requires a recurrent formulation, but also demands expressive state dynamics.
Thus, our investigation reveals a potential limitation where modern RNN
architectures pay the cost for their lauded parallel training, motivating
better solutions to combine the merits of Transformer and RNNs.

## References

  * Li et al. (2023) Shanda Li, Chong You, Guru Guruganesh, Joshua Ainslie, Santiago Ontanon, Manzil Zaheer, Sumit K. Sanghai, Yiming Yang, Sanjiv Kumar, and Srinadh Bhojanapalli.  Functional interpolation for relative positions improves long context transformers.  _ArXiv_ , abs/2310.04418, 2023.  URL https://api.semanticscholar.org/CorpusID:263829377.
  * Press et al. (2021) Ofir Press, Noah A. Smith, and Mike Lewis.  Train short, test long: Attention with linear biases enables input length extrapolation.  _ArXiv_ , abs/2108.12409, 2021.  URL https://api.semanticscholar.org/CorpusID:237347130.
  * Del’etang et al. (2022) Gr’egoire Del’etang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Marcus Hutter, Shane Legg, and Pedro A. Ortega.  Neural networks and the chomsky hierarchy.  _ArXiv_ , abs/2207.02098, 2022.  URL https://api.semanticscholar.org/CorpusID:250280065.
  * Liu et al. (2022) Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang.  Transformers learn shortcuts to automata.  _ArXiv_ , abs/2210.10749, 2022.  URL https://api.semanticscholar.org/CorpusID:252992725.
  * Yao et al. (2021) Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, and Karthik Narasimhan.  Self-attention networks can process bounded hierarchical languages.  In _Annual Meeting of the Association for Computational Linguistics_ , 2021.  URL https://api.semanticscholar.org/CorpusID:235166395.
  * Dziri et al. (2023) Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaïd Harchaoui, and Yejin Choi.  Faith and fate: Limits of transformers on compositionality.  _ArXiv_ , abs/2305.18654, 2023.  URL https://api.semanticscholar.org/CorpusID:258967391.
  * Saparov et al. (2023) Abulhair Saparov, Richard Yuanzhe Pang, Vishakh Padmakumar, Nitish Joshi, Seyed Mehran Kazemi, Najoung Kim, and He He.  Testing the general deductive reasoning capacity of large language models using ood examples.  _ArXiv_ , abs/2305.15269, 2023.  URL https://api.semanticscholar.org/CorpusID:258865898.
  * Zhang et al. (2023) Shizhuo Zhang, Curt Tigges, Stella Biderman, Maxim Raginsky, and Talia Ringer.  Can transformers learn to solve problems recursively?  _ArXiv_ , abs/2305.14699, 2023.  URL https://api.semanticscholar.org/CorpusID:258865729.
  * Bhattamishra et al. (2020) S. Bhattamishra, Kabir Ahuja, and Navin Goyal.  On the ability of self-attention networks to recognize counter languages.  _ArXiv_ , abs/2009.11264, 2020.  URL https://api.semanticscholar.org/CorpusID:221856691.
  * Weiss et al. (2021) Gail Weiss, Yoav Goldberg, and Eran Yahav.  Thinking like transformers.  _ArXiv_ , abs/2106.06981, 2021.  URL https://api.semanticscholar.org/CorpusID:235421630.
  * Davidson et al. (2012) Kathryn Davidson, Kortney Eng, and David Barner.  Does learning to count involve a semantic induction?  _Cognition_ , 123(1):162–173, 2012.
  * Rousselle and Vossius (2021) Laurence Rousselle and Line Vossius.  Acquiring the cardinal knowledge of number words: A conceptual replication.  _Journal of Numerical Cognition_ , 7(3):411–434, 2021.
  * Sarnecka and Carey (2008) Barbara W Sarnecka and Susan Carey.  How counting represents number: What children must learn and when they learn it.  _Cognition_ , 108(3):662–674, 2008.
  * Spaepen et al. (2018) Elizabet Spaepen, Elizabeth A Gunderson, Dominic Gibson, Susan Goldin-Meadow, and Susan C Levine.  Meaning before order: Cardinal principle knowledge predicts improvement in understanding the successor principle and exact ordering.  _Cognition_ , 180:59–81, 2018.
  * Wynn (1992) Karen Wynn.  Children’s acquisition of the number words and the counting system.  _Cognitive psychology_ , 24(2):220–251, 1992.
  * Margolis and Laurence (2008) Eric Margolis and Stephen Laurence.  How to learn the natural numbers: Inductive inference and the acquisition of number concepts.  _Cognition_ , 106(2):924–939, 2008.
  * Vaswani et al. (2017) Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Neural Information Processing Systems_ , 2017.  URL https://api.semanticscholar.org/CorpusID:13756489.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _North American Chapter of the Association for Computational Linguistics_ , 2019.  URL https://api.semanticscholar.org/CorpusID:52967399.
  * Su et al. (2021) Jianlin Su, Yu Lu, Shengfeng Pan, Bo Wen, and Yunfeng Liu.  Roformer: Enhanced transformer with rotary position embedding.  _ArXiv_ , abs/2104.09864, 2021.  URL https://api.semanticscholar.org/CorpusID:233307138.
  * Haviv et al. (2022) Adi Haviv, Ori Ram, Ofir Press, Peter Izsak, and Omer Levy.  Transformer language models without positional encodings still learn positional information.  _ArXiv_ , abs/2203.16634, 2022.  URL https://api.semanticscholar.org/CorpusID:247839823.
  * Kiyono et al. (2021) Shun Kiyono, Sosuke Kobayashi, Jun Suzuki, and Kentaro Inui.  Shape: Shifted absolute position embedding for transformers.  _ArXiv_ , abs/2109.05644, 2021.  URL https://api.semanticscholar.org/CorpusID:237491629.
  * Ruoss et al. (2023) Anian Ruoss, Gr’egoire Del’etang, Tim Genewein, Jordi Grau-Moya, R. Csordás, Mehdi Abbana Bennani, Shane Legg, and Joel Veness.  Randomized positional encodings boost length generalization of transformers.  _ArXiv_ , abs/2305.16843, 2023.  URL https://api.semanticscholar.org/CorpusID:258947457.
  * Zhai et al. (2021) Shuangfei Zhai, Walter Talbott, Nitish Srivastava, Chen Huang, Hanlin Goh, Ruixiang Zhang, and Josh Susskind.  An attention free transformer.  _ArXiv_ , 2021.  URL https://arxiv.org/abs/2105.14103.
  * Gu and Dao (2023) Albert Gu and Tri Dao.  Mamba: Linear-time sequence modeling with selective state spaces, 2023.
  * Elman (1990) Jeffrey L. Elman.  Finding structure in time.  _Cognitive Science_ , 14(2):179–211, 1990.  URL https://onlinelibrary.wiley.com/doi/abs/10.1207/s15516709cog1402_1.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural Computation_ , 9(8):1735–1780, 1997.
  * Shi et al. (2016) Xing Shi, Kevin Knight, and Deniz Yuret.  Why neural translations are the right length.  In Jian Su, Kevin Duh, and Xavier Carreras, editors, _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 2278–2282, Austin, Texas, November 2016. Association for Computational Linguistics.  doi: 10.18653/v1/D16-1248.  URL https://aclanthology.org/D16-1248.
  * Suzgun et al. (2019) Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann.  LSTM networks can perform dynamic counting.  In Jason Eisner, Matthias Gallé, Jeffrey Heinz, Ariadna Quattoni, and Guillaume Rabusseau, editors, _Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges_ , pages 44–54, Florence, August 2019. Association for Computational Linguistics.  doi: 10.18653/v1/W19-3905.  URL https://aclanthology.org/W19-3905.
  * Gu et al. (2021a) Albert Gu, Karan Goel, and Christopher Ré.  Efficiently modeling long sequences with structured state spaces.  _arXiv preprint arXiv:2111.00396_ , 2021a.
  * Peng et al. (2023) Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, et al.  Rwkv: Reinventing rnns for the transformer era.  _arXiv preprint arXiv:2305.13048_ , 2023.
  * Peng et al. (2024) Bo Peng, Daniel Goldstein, Quentin Anthony, Alon Albalak, Eric Alcaide, Stella Biderman, Eugene Cheah, Teddy Ferdinan, Haowen Hou, Przemys l aw Kazienko, G Kranthikiran, Jan Koco’n, Bartlomiej Koptyra, Satyapriya Krishna, Ronald McClelland, Niklas Muennighoff, Fares Obeid, Atsushi Saito, Guangyu Song, Haoqin Tu, Stanislaw Wo’zniak, Ruichong Zhang, Bingchen Zhao, Qihang Zhao, Peng Zhou, Jian Zhu, and Ruijie Zhu.  Eagle and finch: Rwkv with matrix-valued states and dynamic recurrence.  _ArXiv_ , abs/2404.05892, 2024.  URL https://api.semanticscholar.org/CorpusID:269010053.
  * Lindner et al. (2023) David Lindner, J’anos Kram’ar, Matthew Rahtz, Tom McGrath, and Vladimir Mikulik.  Tracr: Compiled transformers as a laboratory for interpretability.  _ArXiv_ , abs/2301.05062, 2023.  URL https://api.semanticscholar.org/CorpusID:255749093.
  * Zhou et al. (2023) Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran.  What algorithms can transformers learn? a study in length generalization.  _ArXiv_ , abs/2310.16028, 2023.  URL https://api.semanticscholar.org/CorpusID:264439160.
  * Cong et al. (1996) Jason Cong, John Peck, and Yuzheng Ding.  Rasp: A general logic synthesis system for sram-based fpgas.  In _Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays_ , pages 137–143, 1996.
  * Yang and Chiang (2024) Andy Yang and David Chiang.  Counting like transformers: Compiling temporal counting logic into softmax transformers.  _arXiv preprint arXiv:2404.04393_ , 2024.
  * Strobl et al. (2024) Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, and Ashish Sabharwal.  Transformers as transducers.  _arXiv preprint arXiv:2404.02040_ , 2024.
  * Merrill et al. (2022) William Merrill, Ashish Sabharwal, and Noah A Smith.  Saturated transformers are constant-depth threshold circuits.  _Transactions of the Association for Computational Linguistics_ , 10:843–856, 2022.
  * Hahn (2020) Michael Hahn.  Theoretical limitations of self-attention in neural sequence models.  _Transactions of the Association for Computational Linguistics_ , 8:156–171, 2020.
  * Ebrahimi et al. (2020) Javid Ebrahimi, Dhruv Gelda, and Wei Zhang.  How can self-attention networks recognize dyck-n languages?  _arXiv preprint arXiv:2010.04303_ , 2020.
  * Chiang and Cholak (2022) David Chiang and Peter Cholak.  Overcoming a theoretical limitation of self-attention.  _arXiv preprint arXiv:2202.12172_ , 2022.
  * Abbe et al. (2023) Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk.  Generalization on the unseen, logic reasoning and degree curriculum.  In _International Conference on Machine Learning_ , pages 31–60. PMLR, 2023.
  * McLeish et al. (2024) Sean McLeish, Arpit Bansal, Alex Stein, Neel Jain, John Kirchenbauer, Brian R Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, Jonas Geiping, Avi Schwarzschild, et al.  Transformers can do arithmetic with the right embeddings.  _arXiv preprint arXiv:2405.17399_ , 2024.
  * Anil et al. (2022) Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur.  Exploring length generalization in large language models.  _Advances in Neural Information Processing Systems_ , 35:38546–38556, 2022.
  * Zhou et al. (2022) Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi.  Teaching algorithmic reasoning via in-context learning.  _arXiv preprint arXiv:2211.09066_ , 2022.
  * Hao et al. (2022) Yiding Hao, Dana Angluin, and Robert Frank.  Formal language recognition by hard attention transformers: Perspectives from circuit complexity.  _Transactions of the Association for Computational Linguistics_ , 10:800–810, 2022.
  * Kazemnejad et al. (2024) Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy.  The impact of positional encoding on length generalization in transformers.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Bhattamishra et al. (2022) Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom.  Simplicity bias in transformers and their ability to learn sparse boolean functions.  _arXiv preprint arXiv:2211.12316_ , 2022.
  * Gu et al. (2021b) Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré.  Combining recurrent, convolutional, and continuous-time models with linear state space layers.  _Advances in neural information processing systems_ , 34:572–585, 2021b.
  * Nguyen et al. (2024) Eric Nguyen, Michael Poli, Marjan Faizi, Armin Thomas, Michael Wornow, Callum Birch-Sykes, Stefano Massaroli, Aman Patel, Clayton Rabideau, Yoshua Bengio, et al.  Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution.  _Advances in neural information processing systems_ , 36, 2024.
  * Tiezzi et al. (2024) Matteo Tiezzi, Michele Casoni, Alessandro Betti, Tommaso Guidi, Marco Gori, and Stefano Melacci.  On the resurgence of recurrent models for long sequences: Survey and research opportunities in the transformer era.  _arXiv preprint arXiv:2402.08132_ , 2024.
  * Wan et al. (2023) Zhongwei Wan, Xin Wang, Che Liu, Samiul Alam, Yu Zheng, Zhongnan Qu, Shen Yan, Yi Zhu, Quanlu Zhang, Mosharaf Chowdhury, et al.  Efficient large language models: A survey.  _arXiv preprint arXiv:2312.03863_ , 1, 2023.
  * Merrill (2019) William Merrill.  Sequential neural networks as automata.  _arXiv preprint arXiv:1906.01615_ , 2019.
  * Merrill et al. (2024) William Merrill, Jackson Petty, and Ashish Sabharwal.  The illusion of state in state-space models.  _arXiv preprint arXiv:2404.08819_ , 2024.
  * Zhong et al. (2024) Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas.  The clock and the pizza: Two stories in mechanistic explanation of neural networks.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Veličković et al. (2022) Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell.  The clrs algorithmic reasoning benchmark.  In _International Conference on Machine Learning_ , pages 22084–22102. PMLR, 2022.
  * Elhage et al. (2021) Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah.  A mathematical framework for transformer circuits.  _Transformer Circuits Thread_ , 2021.  https://transformer-circuits.pub/2021/framework/index.html.
  * Vig and Belinkov (2019) Jesse Vig and Yonatan Belinkov.  Analyzing the structure of attention in a transformer language model.  _arXiv preprint arXiv:1906.04284_ , 2019.

##  Appendix A Median Performance out of 5 Random Seeds

In our main analysis, we assess how models generalize on counting based on the
best performance out of 5 runs. However, we sometimes observe high variances
between runs, suggesting the difficulty for SGD to find a generalizable
solution. Table 6 & 7 report the median performance for the same experiments
presented in Section 4 (Table 4 & 5). There are large discrepancies between
the best and median results for Transformers with Sinusoidal PE, APE, or SPE.
Mamba and RWKV-v6 also exhibit such instability. Therefore, although certain
architectural choices allows for generalizable solutions, learnability remains
to be a matter of chance. We hope further study on training dynamics can find
out why the likelihood of learning a generalizable solution varies across
architectures.

|  | NoPE | Sine | APE | RoPE | SPE
---|---|---|---|---|---|---
Task |  L |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD
Counting \+ Helper Object |  2 |  100 |  98.5 |  100 |  66.3 |  100 |  55.3 |  100 |  100 |  100 |  14.2
|  4 |  100 |  100 |  100 |  59.9 |  100 |  68.4 |  100 |  100 |  100 |  65.8
Counting \+ Helper Object \+ Shifted Start |  1 |  100 |  4.1 |  99.4 |  0.0 |  100 |  13.1 |  100 |  5.3 |  100 |  4.1
|  2 |  100 |  100 |  100 |  99.3 |  100 |  81.3 |  100 |  48.5 |  100 |  6.8
|  4 |  100 |  99.7 |  100 |  84.3 |  100 |  100 |  100 |  100 |  100 |  84.5
Counting \+ Shifted Start |  1 |  100 |  15.3 |  99.8 |  2.7 |  100 |  40.6 |  100 |  37.4 |  99.6 |  8.7
|  2 |  100 |  20.9 |  100 |  2.0 |  100 |  19.7 |  100 |  86.6 |  100 |  43.7
|  4 |  100 |  39.2 |  100 |  36.7 |  100 |  26.6 |  100 |  96.6 |  100 |  30.7
Modular (mod10) |  1 |  11.8 |  11.8 |  100 |  97.9 |  100 |  56.5 |  11.8 |  11.8 |  100 |  8.3
|  2 |  11.8 |  11.8 |  100 |  100 |  100 |  99.5 |  11.8 |  11.8 |  100 |  8.3
|  4 |  11.8 |  11.8 |  100 |  100 |  100 |  99.9 |  11.8 |  11.8 |  100 |  10.2
Selective |  1 |  95.4 |  9.2 |  95.8 |  51.0 |  100 |  10.6 |  99.7 |  26.4 |  99.7 |  57.1
|  2 |  99.7 |  94.1 |  99.3 |  16.3 |  100 |  13.5 |  99.7 |  48.9 |  99.7 |  81.2
|  4 |  99.7 |  100 |  100 |  99.8 |  100 |  99.9 |  99.7 |  47.6 |  99.7 |  95.4
Selective \+ Modular (mod4) |  2 |  92.2 |  55.1 |  98.7 |  37.9 |  99.7 |  27.2 |  98.1 |  32.1 |  99.6 |  46.1
|  4 |  98.0 |  91.0 |  98.8 |  70.2 |  99.3 |  95.0 |  98.5 |  38.6 |  98.2 |  49.9
Table 6: Results for Transformers corresponding to Table 4, switching from best to median performance out of 5 runs. Bold entries indicate a >10 absolute gap between the median and best results.  |  | RNN | LSTM | S4 | Mamba | RWKV-v6
---|---|---|---|---|---|---
Task |  L |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD
Counting \+ Helper Object |  1 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  15.5 |  100 |  0.0
|  2 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  4.5 |  100 |  2.0
|  4 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  37.0 |  100 |  100
Counting \+ Helper Object \+ Shifted Start |  1 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  0.7 |  100 |  0.0
|  2 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  5.0 |  100 |  0.0
|  4 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  44.2
Counting \+ Shifted Start |  1 |  100 |  100 |  100 |  100 |  100 |  95.9 |  100 |  5.2 |  99.9 |  25.0
|  2 |  100 |  100 |  100 |  100 |  100 |  100 |  99.8 |  48.5 |  100 |  30.8
|  4 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  51.7 |  100 |  84.0
Modular (mod10) |  1 |  100 |  100 |  100 |  100 |  100 |  97.8 |  89.5 |  11.5 |  100 |  8.2
|  2 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  11.1 |  100 |  8.2
|  4 |  100 |  100 |  100 |  100 |  100 |  100 |  100 |  11.0 |  100 |  9.3
Selective |  1 |  98.6 |  92.5 |  100 |  100 |  72.9 |  53.0 |  100 |  99.3 |  99.9 |  98.6
|  2 |  99.3 |  93.7 |  100 |  100 |  91.3 |  66.7 |  100 |  94.8 |  100 |  99.9
|  4 |  97.3 |  81.9 |  100 |  100 |  98.2 |  67.2 |  100 |  96.7 |  100 |  97.7
Selective and Modular (mod4) |  1 |  100 |  100 |  100 |  100 |  86.1 |  27.3 |  58.1 |  27.4 |  98.5 |  83.1
|  2 |  100 |  100 |  100 |  100 |  91.0 |  31.4 |  99.1 |  55.0 |  99.2 |  56.5
|  4 |  100 |  100 |  100 |  100 |  99.2 |  35.9 |  100 |  57.9 |  100 |  55.1
Table 7: Results for recurrent architectures corresponding to Table 5,
switching from best to median performance out of 5 runs. Bold entries indicate
a >10 absolute gap between the median and best results.

##  Appendix B Importance of the Begin-of-sequence (bos) Token

|  | w/o bos | w/ bos
---|---|---|---
|  | NoPE | RoPE | NoPE | RoPE
Task |  L |  IND |  OOD |  IND |  OOD |  IND |  OOD |  IND |  OOD
Counting \+ Succession |  1 |  2.0 |  0.0 |  2.0 |  0.0 |  100 |  0.0 |  100 |  0.0
|  2 |  2.0 |  0.0 |  2.0 |  0.0 |  100 |  0.0 |  100 |  0.0
|  4 |  2.0 |  0.0 |  2.0 |  0.0 |  100 |  0.0 |  100 |  0.0
Modular (mod10) |  1 |  11.8 |  11.8 |  11.8 |  11.8 |  100 |  10.1 |  100 |  27.8
|  2 |  12.0 |  11.8 |  11.8 |  11.8 |  100 |  8.6 |  100 |  40.3
|  4 |  11.8 |  11.8 |  11.8 |  11.8 |  100 |  8.6 |  100 |  41.6
Table 8:  Grevious in-domain failures of NoPE and RoPE can be addressed by the
bos token, though their OOD performance benefits less from bos. This finding
calls for future work to investigate how bos affects NoPE and RoPE, and why
other PEs/tasks are not affected.

We observed grevious failures of NoPE and RoPE on Counting + Succession and
Modular counting (shown in Table 3 & 4, respectively), where both IND and OOD
performances were below chance-level. The inability to fit in-domain data took
us by surprise. We perform further analysis and find that NoPE and RoPE
crucially depend on the presence of a begin-of-sequence (bos) token in order
to fit the in-domain data. Concretely, we insert <bos>, a token distinct from
the remaining vocabulary, at the beginning of each training sequence. Loss
computation at the output side of <bos> is skipped. After such adjustment,
NoPE and RoPE are able to achieve perfect IND accuracy on both Counting +
Succession and Modular counting. Notably, <bos> also improves RoPE-OOD
performance on modular counting well beyond the chance level. A question
immediately arises: why other tasks were accomplished initially? To account
for the IND success of NoPE and RoPE in other tasks studied in Section 4, we
believe that the first token in a shifted start sequence may have concurrently
played the role of <bos>555 For the Counting + Helper Object task, we reused
the data generation process for shifted start sequences, simply fixing the
shift to be 0. We realized later that this inadvertently offered the
opportunity for the shifted start token to serve as ¡bos¿ in Counting + Helper
Object in the same way as in shifted start tasks. . For selective counting,
the task nature may remove the dependence on bos.

The special role of bos has been discussed in the literature. Chiang and
Cholak [2022] manually constructed Transformer weights for recognizing two
regular languages, where bos plays key roles in multiple steps of their
construction. Elhage et al. [2021] pointed out a phenomenon called “resting",
where an attention head predominantly attends to a meaningless token by
default (i.e. resting position) if there is no token matches what it looks
for. The bos token and punctuation tokens are common examples of resting
positions in a pretrained Transformer. Similarly, Vig and Belinkov [2019]
discovered that 57% of attention was directed to the first token in pretrained
GPT-2. These works provide clues for why bos is critical for NoPE and RoPE in
certain counting tasks. A detailed answer is left for future work. Another
intriguing question is why other PEs performed well without bos. One
possibility is that different PEs tend to direct the Transformer towards
different solutions, among which some relies on bos while others do not,
implying a diverse algorithmic phase space [Zhong et al., 2024] in
Transformers. Future work is needed to 1) characterize Transformers’
algorithmic phase space, and 2) analyze how PEs constrain the “navigation"
through such a space.


# Back to almost Ricci solitons

Vladimir Rovenski111University of Haifa, Dept. of Mathematics, 3498838, Haifa,
Israel. e-mail<EMAIL_ADDRESS>Sergey Stepanov222Financial
University, Dept. of Mathematics, 125993, Moscow, Russia; and
VINITI, Dept. of Mathematics, 20, 125190 Moscow, Russia. e-mail:
<EMAIL_ADDRESS>and Irina Tsyganok333Financial University, Dept. of
Mathematics, 125993, Moscow, Russia. e-mail<EMAIL_ADDRESS>
###### Abstract

In the paper, we study complete almost Ricci solitons using the concepts and
methods of geometric dynamics and geometric analysis. In particular, we
characterize Einstein manifolds in the class of complete almost Ricci
solitons. Then, we examine compact almost Ricci solitons using the orthogonal
expansion of the Ricci tensor, this allows us to substantiate the concept of
almost Ricci solitons.

Keywords: Almost Ricci soliton; energy density; infinitesimal harmonic
transformation; conformal Killing vector.

Mathematics Subject Classifications (2010) Primary: 53C21; Secondary: 58J05.

##  1 Introduction

One of the important components of the theory of Ricci flow are self-similar
solutions called Ricci solitons, see [7, pp. 153-176]. Ricci solitons, which
are a generalization of Einstein manifolds, have been studied more and more
intensively in the last twenty years. This theory, besides being known after
G. Perelman’s proof of the Poincaré conjecture (for details see [12]), has a
wide range of applications in differential geometry and theoretical physics.
In turn, the study of almost Ricci solitons, which are a generalization of
quasi-Einstein manifolds and Ricci solitons, was started by Pigola, Rigoli,
Rimoldi, and Setty, see [15]. An $n$-dimensional $(n\geq 2)$ Riemannian
manifold $(M,g)$ is called an almost Ricci soliton, if there exist a smooth
complete vector field $\xi$ and a function $\lambda\in C^{\infty}(M)$ such
that

${\rm Ric}=\frac{1}{2}\,{\cal L}_{\xi}\,g+\lambda\,g.$ (1.1)

Here, $Ric$ is the Ricci tensor and ${\cal L}_{\xi}$ is the Lie derivative
operator in the direction of $\xi$. Namely, $({\cal
L}_{\xi}\,g)(X,Y)=g(\nabla_{X}\xi,Y)+g(\nabla_{Y}\xi,X)$ for all smooth vector
fields $X,Y$ on $M$, where $\nabla$ is the covariant derivative (Levi-Civita
connection). Denote by $(M,g,\xi,\lambda)$ an almost Ricci soliton. For
$\lambda=const$, it is a Ricci soliton. Note that when $\xi$ is a Killing
vector field, i.e., ${\cal L}_{\xi}\,g=0$, an almost Ricci soliton
$(M,g,\xi,\lambda)$ is Einstein manifold, i.e., $Ric=\frac{s}{n}\,g$, from
which we can apply Schur’s lemma, e.g., [11], to obtain $\lambda=const$. In
the special case, where $\xi=\nabla f$ for some function $f\in C^{\infty}(M)$,
we say that $(M,g,\xi,\lambda)$ is a gradient almost Ricci soliton with
potential function $f$.

In [15], almost Ricci complete gradient solitons are considered. Other more
recent papers have studied compact almost Ricci solitons (e.g., [3, 2, 8]) or
almost Ricci solitons on manifolds with additional geometric structures, e.g.,
[10, 14]. There are also attempts to find applications of almost Ricci
solitons in theoretical physics, see, e.g., [9].

In Sections 2-3, we study complete almost Ricci solitons using concepts and
methods of geometric dynamics and geometric analysis. In Section 4, we study
compact almost Ricci solitons applying the orthogonal expansion of symmetric
two-tensors (see [5, p. 130]) to the Ricci tensor. In particular, this will
make it possible to substantiate the concept of almost Ricci solitons.

##  2 Complete almost Ricci solitons

Here, we study complete almost Ricci solitons from the point of view of
geometric dynamics, see [19, 1]. Denote by $\theta$ the $g$-dual one-form of
$\xi$ and $\bar{\Delta}=\nabla^{*}\nabla$ the Laplace operator for the formal
adjoint operator ${\nabla}^{*}$ of $\nabla$. First, we formulate a lemma
needed to prove our main results.

######  Lemma 2.1.

The vector field $\xi$ of an almost Ricci soliton $(M,g,\xi,\lambda)$
satisfies the equation

$\bar{\Delta}\,\theta={\rm Ric}(\xi,\cdot)-(n-2)\,d\lambda\,.$ (2.1)

Recall that a vector field $\xi$ generates a flow on a manifold, which is a
one-parameter group of infinitesimal self-diffeomorphisms [11, pp. 12-14]. A
vector field $\xi$ is an infinitesimal harmonic transformation on $(M,g)$ if
the local one-parameter group of infinitesimal self-diffeomorphisms generated
by $\xi$ is a group of harmonic self-diffeomorphisms. A vector field $\xi$ is
an infinitesimal harmonic transformation in $(M,g)$ if and only if
$\bar{\Delta}\,\theta=Ric(\xi,\,\cdot)$, where $\theta$ is the $g$-dual one-
form of $\xi$, see [17]. In particular, the Killing vector field is an example
of an infinitesimal harmonic transformation on $(M,g)$, see [16]. Moreover, a
vector field $\xi$ associated with a Ricci soliton $(M,g,\xi,\lambda)$ is also
an infinitesimal harmonic transformation on $(M,g)$ [17, 18]. Note that a
local one-parameter group of infinitesimal harmonic transformations, or a
harmonic flow generated by $\xi$, is directly related to De Turck harmonic
flows [7, pp. 113–117].

The next corollary follows from Lemma 2.1.

######  Corollary 2.1.

An $n$-dimensional $(n\geq 3)$ almost Ricci soliton $(M,g,\xi,\lambda)$ is a
Ricci soliton if and only if its vector field $\xi$ is an infinitesimal
harmonic transformation. At the same time, the vector field $\xi$ associated
with a two-dimensional almost Ricci soliton $(M,g,\xi,\lambda)$ is an
infinitesimal harmonic transformation.

The function

$e(\xi):=\frac{1}{2}\,\|\xi\|^{2}=\frac{1}{2}\,g(\xi,\xi).$

is said to be the energy density of the flow generated by the vector field
$\xi$, see [19, pp. 273–274]. The kinetic energy of the flow of $\xi$ is
defined by the integral formula, see [1, pp. 2; 19; 37],

$E(\xi)=\int_{M}\,e(\xi)\,d\,{\rm vol}_{g}\,.$

The kinetic energy can be infinite or finite (e.g., on a compact manifold).
Note that the kinetic energy plays an impotent role in Hamilton dynamics, see,
e.g., [1].

Based on the above definition and Lemma 2.1, we formulate our main theorem.

######  Theorem 2.1.

Let $(M,g,\xi,\lambda)$ be an $n$-dimensional $(n\geq 3)$ complete almost
Ricci soliton such that the rate of change of $\lambda$ along the trajectories
of the $\xi$-flow is pointwise bounded from below by ${\rm Ric}(\xi,\xi):$

${\cal L}_{\xi}\,\lambda\geq{\rm Ric}(\xi,\xi).$ (2.2)

If $E(\xi)<\infty$, then $\xi$ is a parallel vector field and $(M,g)$ is an
Einstein manifold. Furthermore, if the soliton has infinite volume, then
$\xi=0$.

According to the definition of the Lie derivative, e.g., [11, pp. 29-30], the
Lie derivative of a function $f\in C^{1}(M)$ with respect to vector field
$\xi$ in (2.2) is given by

${\cal L}_{\xi}f=\xi(f)=df(\xi)=\nabla_{\xi}f=g(\nabla f,\xi).$

In particular, it follows from Theorem 2.1 that not every complete Riemannian
manifold supports an almost Ricci soliton structure, see also [15, Corollary
1.5 and Example 2.4].

######  Remark 2.1.

If a Riemannian manifold $(M,g)$ admits a complete parallel vector field, then
$(M,g)$ is reducible, i.e., is locally the metric product of a real line and
some other Riemannian manifold. In Theorem 2.1, instead of condition “infinite
volume” one can assume that $(M,g)$ is not reducible.

Theorem 2.1 can be supplemented as follows. Let $(M,g,\xi,\lambda)$ be a two-
dimensional complete almost Ricci soliton satisfying $Ric(\xi,\xi)\leq 0$ and
$E(\xi)<\infty$, then $(M,g,\xi,\lambda)$ is isometric to Euclidean plane or
one of the flat complete surfaces: cylinder, torus, Möbius band and Klein
bottle.

The following assertion follows from (1.1) and Theorem 2.1.

######  Corollary 2.2.

Let $(M,g,\xi,\lambda)$ be a complete almost Ricci soliton such that
$E(\xi)<\infty$. If $\lambda$ is a non-decreasing function along trajectories
of this flow and ${\cal L}_{\xi}\sqrt{e(\xi)}\leq-\lambda$, then $(M,g)$ is an
Einstein manifold. Furthermore, if the soliton has infinite volume, then
$\xi=0$.

Recall that the volume form of $(M,g)$ is defined by equality
$\omega_{g}(\partial_{1},\ldots,\partial_{n})=\sqrt{\det g}$ for
$\partial_{k}={\partial}/{\partial x^{k}}$ with respect to local coordinates
$x^{1},\dots,x^{n}$. Note also that a Riemannian manifold $(M,g)$ has a
(global) volume element if and only if $(M,g)$ is orientable, see [13, p.
195]. A volume form on a connected manifold $(M,g)$ has a single global
invariant, namely the (overall) volume,
$\mathrm{Vol}(M,g)=\int_{M}{\omega_{g}}\,d\,{\rm vol}_{g}$, which is invariant
under volume-form preserving transformations. The volume $\mathrm{Vol}(M,g)$
can be infinite or finite (e.g., $\mathrm{Vol}(M,g)<\infty$ for a compact
manifold $M$).

On the other hand, a complete non-compact Riemannian manifold with non-
negative Ricci curvature has infinite volume, see [4]. For the volume form
$\omega_{g}$ of $(M,g)$, one can consider its Lie derivative along
trajectories of the flow of $\xi$. Namely, we have the following, see [12, p.
281]: ${\cal L}_{\xi}\,\omega_{g}=({\rm div}\,\xi)\,\omega_{g}$. According to
the definition of the Lie derivative, ${\cal L}_{\xi}\,\omega_{g}$ measures
the rate of the change of the volume form $\omega_{g}$ under deformations
determined by a one-parameter group of differentiable transformations (or a
flow) generated by the vector field $\xi$.

In the well-known monograph [13, p. 195] the function ${\rm div}\,\xi$ was
called the logarithmic rate of change of volume (or, in other words, rate of
volume expansion) under the flow generated by the vector field $\xi$. On the
other hand, the condition ${\rm div}\,\xi=0$ is equal to ${\cal
L}_{\xi}\,\omega_{g}=0$. This means that the one-parameter group of
differentiable transformations leaves $\omega_{g}$ invariant or, in other
words, the vector field $\xi$ is an infinitesimal automorphism of the volume
form, see [19, p. 6]. In dynamic, such a vector field $\xi$ is said to be
divergence-free and the flow generated by it is said to be incompressible, see
[13, p. 125]. The geometric dynamics of divergence-free vector fields was
studied in detail in the monograph [1].

The following proposition is true.

######  Lemma 2.2.

Let $(M,g,\xi,\lambda)$ be a complete oriented almost Ricci soliton such that
the length of $\xi$ is integrable. If the logarithmic rate of volumetric
expansion doesn’t change sign on $M$ under deformations determined by the flow
of $\xi$, then (1.1) has the form

${\rm Ric}=\frac{1}{2}\,{\cal L}_{\xi}\,g+\ \frac{s}{n}\,g\,,$

where components of the right hand side are orthogonal to each other with
respect to the standard pointwise scalar product. On the other hand, if (1.1)
is of the form indicated above, then the flow of $\xi$ is incompressible.

######  Corollary 2.3.

Let $(M,g,\xi,\lambda)$ be a complete oriented almost Ricci soliton such that
the length of $\xi$ is integrable. If the logarithmic rate of volumetric
expansion doesn’t change sign on $M$ under deformations determined by the flow
of $\xi$, then $\xi$ satisfies the equation

$\bar{\Delta}\,\theta=Ric(\xi,\cdot)-\frac{n-2}{n}\,ds.$

##  3 Proof of results in Section 2

Proof of Lemma 2.1 and Corollary 2.1. The equation (1.1) has the following
form with respect to local coordinates $x^{1},\,\ldots,\,x^{n}$:

$R_{ij}=\frac{1}{2}\,{\cal L}_{\xi}\,g_{ij}+\lambda\,g_{ij},$ (3.1)

where $R_{ij}$, $g_{ij}$ and ${\xi}_{i}$ stand, respectively, for the
components of the Ricci tensor $Ric$, the metric tensor $g$, and the
components ${\xi}_{i}=g_{ij}\,{\xi}^{j}$ of $\xi$. Also $\theta={\xi}^{j}$ is
the one-form corresponding to $\xi$ under the duality defined by the metric
$g$. According the formula ${\cal
L}_{\xi}\,g_{ij}=\nabla_{i}\,{\xi}_{j}+{\nabla}_{j}\,{\xi}_{i}$, where
${\nabla}_{i}={\nabla}_{\partial/\partial x^{i}}$, we obtain from (3.1) the
equality

${\rm div}\,\xi:={\nabla}_{i}\,\xi^{i}=s-n\,\lambda$ (3.2)

for the scalar curvature $s$ of the metric $g$. Applying the operator
${\nabla}^{i}=g^{ij}{\nabla}_{j}$ to (3.1), we find

$\nabla^{i}\,\nabla_{i}\,{\xi}_{j}+{\nabla}^{i}{\nabla}_{j}\,{\xi}_{i}={\nabla}_{j}\,s-2\,{\nabla}_{j}\,\lambda\,.$
(3.3)

Using the contracted second Bianchi identity, see [11], and
${\nabla}_{i}\,\xi^{i}$ of (3.2), we have

${\nabla}_{i}{\nabla}_{j}\,{\xi}^{i}={\nabla}_{j}{\nabla}_{i}\,{\xi}^{i}+R_{ij}\,{\xi}^{i}={\nabla}_{j}\,s-n{\nabla}_{j}\,\lambda+R_{ij}\,{\xi}^{i}.$

Using this and noting that $\bar{\Delta}=-\nabla^{i}\,\nabla_{i}$ (the Laplace
operator $\bar{\Delta}=\nabla^{*}\nabla$ and its expression in coordinates
coincide, see [5, Paragraph 1.55]), we rewrite (3.3) in the following form:

$\bar{\Delta}\,{\xi}_{j}=R_{ij}\,{\xi}^{i}-(n-2)\,{\nabla}_{j}\,\lambda\,.$
(3.4)

In coordinate-free form, (3.4) coincides with (2.1) that proves Lemma 2.1. By
this and (2.1), we complete the proof of Corollary 2.1. $\square$

Proof of Theorem 2.1. In our case, the second Kato inequality,
$\|\xi\|\,\Delta\|\xi\|\geq-g(\bar{\Delta}\,\xi,\xi)$, see [4, p. 380],

$\|\xi\|\,\Delta\|\xi\|\geq-g(\bar{\Delta}\,\xi,\xi),$

using Lemma 2.1, can be rewritten in the following form:

$\|\xi\|\,\Delta\|\xi\|\geq(n-2)\,{\cal L}_{\xi}\lambda-Ric(\xi,\xi),$

where $\Delta$ is the Laplace–Beltrami operator defined by the equality
$\Delta\,f={\rm trace}_{g}\nabla\,df$ for an arbitrary function $f\in
C^{2}(M)$. The assumption (2.2) for $n\geq 3$ implies that
$\|\xi\|\,\Delta\|\xi\|\geq 0$. Then by the classical theorem of geometric
analysis (see [21]), either $\int_{M}\|\xi\|^{p}\,d\,{\rm vol}_{g}=\infty$ for
a positive number $p>1$, or $\|\xi\|=const$. Thus, if $\|\xi\|\in L^{p}(M,g)$
at least for one $p>1$, then $\|\xi\|=const$. Note that the inequality
$E(f)<\infty$ is equivalent to $\|\xi\|\in L^{2}(M,g)$. By the above (for
$p=2$), and the condition $E(f)<\infty$, we get $\|\xi\|=const$. Using this
and (3.4), we derive

$0=\frac{1}{2}\,\Delta\,g(\xi,\xi)=-g(\bar{\Delta}\,\xi,\xi)+\|\nabla\,\xi\|^{2}=-Ric(\xi,\,\xi)+(n-2)\,{\cal
L}_{\xi}\,\lambda+\|\nabla\,\xi\|^{2}.$ (3.5)

By (3.5), $\xi$ is a parallel vector field, in particular, ${\cal
L}_{\xi}\,g=0$. From (1.1) we get $Ric=\lambda\,g$. Since $n\geq 3$, by
Schur’s lemma, e.g., [11], we get $\lambda=const$. Thus, $(M,g)$ is an
Einstein manifold. Next, if $\mathrm{Vol}(M,g)=\infty$, then using
$E(f)<\infty$ and $\|\xi\|=const$, we get $\xi=0$. $\square$

Proof of Corollary 2.2. From (3.1) we derive the following equation:

$R_{ij}\,{\xi}^{i}{\xi}^{j}={\xi}^{i}({\nabla}_{i}\,{\xi}_{j})\,{\xi}^{j}+\lambda\,\|\xi\|^{2},$
(3.6)

where
${\xi}^{i}({\nabla}_{i}\,\xi_{j}){\xi}^{j}=\frac{1}{2}\,{\xi}^{i}{\nabla}_{i}({\xi}_{j}\,{\xi}^{j})={\cal
L}_{\xi}\,e(\xi)$. Thus, we can rewrite (3.6) in the form

${\rm Ric}(\xi,\xi)=\lambda\,\|\xi\|^{2}+{\cal L}_{\xi}\,e(\xi).$

Therefore, the condition $Ric(\xi,\xi)\leq 0$ is equivalent to the inequality
${\cal L}_{\xi}\sqrt{e(\xi)}\leq-\lambda$. From the above, the validity of
Corollary 2.2 follows. $\square$

Proof of Lemma 2.2 and Corollary 2.3. Recall the following theorem, see [6]:
Let $\xi$ be a smooth vector field on a complete oriented Riemannian manifold
$(M,g)$ such that $\|\xi\|\in L^{1}(M,g)$ and ${\rm div}\,\xi$ does not change
sign on $(M,g)$, then ${\rm div}\,\xi=0$ on $(M,g)$. In particular, if $\xi$
is the vector field of a complete, noncompact and oriented almost Ricci
soliton $(M,g,\xi,\lambda)$, then from (3.2) we obtain $s=n\,\lambda$. In this
case, (1.1) can be rewritten in the form

${\rm Ric}=\frac{1}{2}\,{\cal L}_{\xi}\,g+\frac{s}{n}\,g.$ (3.7)

Hence, $g(\frac{1}{2}\,{\cal L}_{\xi}\,g,\,\frac{s}{n}\,g)=\frac{s}{n}\,{\rm
div}\,\xi=0$. Therefore, the terms of the right hand side of (3.7) are
orthogonal to each other with respect to the pointwise scalar product. In
turn, (2.1) takes the form $\bar{\Delta}\,\theta={\rm
Ric}(\xi,\,\cdot)+\frac{n-2}{n}\,ds$. $\square$

##  4 Compact almost Ricci solitons

Here, we study compact almost Ricci solitons using the orthogonal expansion of
the Ricci tensor, obtained using the Becce expansion of the space of symmetric
two-tensors, see [6, p. 130].

Denote by $S^{p}M$ the space of symmetric covariant $p$-tensors on a compact
Riemannian manifold $(M,g)$, and define the global scalar product for any
$\varphi,{\varphi}^{\prime}\in S^{p}M$ by the formula

$\langle\varphi,\
\varphi^{\prime}\rangle=\int_{M}{g(\varphi,\,\varphi^{\prime})}\,d\,{\rm
vol}_{g}.$ (4.1)

Let ${\delta}^{*}:C^{\infty}(S^{1}M)\to C^{\infty}(S^{2}M)$ be the first-order
differential operator defined by ${\delta}^{*}\theta=\frac{1}{2}\,{\cal
L}_{\xi}\,g$ for any smooth one-form $\theta$ and its $g$-dual vector field
$\xi$, see [5, p. 117; 514]. Let also $\delta:C^{\infty}(S^{2}M)\to
C^{\infty}(S^{1}M)$ be the formal adjoint operator for ${\delta}^{*}$, which
is called the divergence of symmetric two-tensors. In this case,
$\langle\varphi,{\delta}^{*}\theta\rangle=\langle\delta\varphi,\theta\rangle$
is true for any $\varphi\in C^{\infty}(S^{2}M)$ and $\theta\in
C^{\infty}(S^{1}M)$. For a compact Riemannian manifold $(M,g)$, the algebraic
sum $\mathrm{Im}\,{\delta}^{*}+C^{\infty}(M)\,\cdot g$ is closed in $S^{2}M$,
and the following decomposition is true:

$S^{2}M=(\mathrm{Im}\,{\delta}^{*}+C^{\infty}(M)\,\cdot
g)\oplus({\delta}^{-1}(0)\cap{\mathrm{trace}}^{-1}_{g}(0));$ (4.2)

furthermore, both factors in (4.2) are infinite-dimensional and orthogonal to
each other with respect to the global scalar product (4.1), see [5, p. 130].

######  Lemma 4.1.

Let $(M,g)$ be a compact $n$-dimensional Riemannian manifold and

${\rm Ric}=\frac{1}{2}\,{\cal L}_{\xi}\,g+\lambda\,g+\varphi$

the orthogonal expansion $($with respect to the global scalar product$)$ of
the Ricci tensor for some vector field $\xi$ and divergence-free and trace-
free symmetric two-form $\varphi$. Then

  1. 1.

for $n\geq 3$, the vector field $\xi$ is an infinitesimal harmonic
transformation if and only if $\lambda=const$, and for $n=2$, the vector field
$\xi$ is an infinitesimal harmonic transformation;

  2. 2.

the assumptions $n\geq 3$ and $\int_{M}({\cal L}_{\xi}\,s)\,d\,{\rm
vol}_{g}\geq 0$ imply that $\varphi=Ric-\frac{s}{n}\,g$ for the scalar
curvature $s=const$, and that $\xi$ is a conformal Killing vector field.

###### Proof.

For the Ricci tensor, decomposition (4.2) has the form

${\rm Ric}=\big{(}\frac{1}{2}\,{\cal L}_{\xi}\,g+\lambda\,g\big{)}+\varphi$
(4.3)

for some divergence-free and trace-free tensor $\varphi\in C^{\infty}(S^{2}M)$
and function $\lambda\in C^{\infty}(M)$. From (4.3) we get

$-\delta\theta:={\rm div}\,\xi=s-n\,\lambda.$

Applying the operator $\delta$ to (4.3), we find, see also (2.1),

$\bar{\Delta}\,\theta={\rm Ric}(\xi,\,\cdot)-(n-2)\,d\lambda.$

Therefore, for $n\geq 3$, $\xi$ is an infinitesimal harmonic transformation if
and only if $\lambda=const$, and for $n=2$, the vector field $\xi$ is an
infinitesimal harmonic transformation. On the other hand, using
$n\,\lambda=\delta\,\theta+s$, we derive the following equalities:

$\displaystyle 0$ $\displaystyle=\langle\varphi,\,{\delta}^{*}\theta+\lambda
g\rangle=\langle{\rm
Ric}-{\delta}^{*}\theta-\lambda\,g,{\delta}^{*}\theta+\lambda\,g\rangle$ (4.4)
$\displaystyle=\langle{\rm
Ric},{\delta}^{*}\theta\rangle-\langle{\delta}^{*}\theta,{\delta}^{*}\theta\rangle-\langle\lambda\,g,{\delta}^{*}\theta\rangle+\langle{\rm
Ric},\,\lambda\,g\rangle-\langle{\delta}^{*}\theta,\lambda\,g\rangle-\langle\lambda\,g,\lambda\,g\rangle$
$\displaystyle=\langle\delta{\rm
Ric},\theta\rangle-\langle{\delta}^{*}\theta,{\delta}^{*}\theta\rangle-2\langle\lambda\,g,{\delta}^{*}\theta\rangle+\int_{M}(\lambda\,s)\,d\,{\rm
vol}_{g}-n\int_{M}{\lambda}^{2}\,d\,{\rm vol}_{g}$
$\displaystyle=-\frac{1}{2}\,\langle
ds,\theta\rangle-\langle{\delta}^{*}\theta,{\delta}^{*}\theta\rangle+2\langle
d\lambda,\theta\rangle+\int_{M}\lambda(s-n\lambda)\,d\,{\rm vol}_{g}$
$\displaystyle=-\frac{1}{2}\,\langle
ds,\theta\rangle-\langle{\delta}^{*}\theta,{\delta}^{*}\theta\rangle+2\langle
d\lambda,\theta\rangle-\int_{M}(\lambda\,\delta\,\theta)\,d\,{\rm vol}_{g}$
$\displaystyle=-\frac{1}{2}\,\langle
ds,\theta\rangle-\langle{\delta}^{*}\theta,{\delta}^{*}\theta\rangle+\langle
d\lambda,\theta\rangle.$

Hence,

$n\,\langle d\lambda,\theta\rangle=\langle
d(\delta\,\theta+s),\theta\rangle=\langle d\delta\theta,\theta\rangle+\langle
ds,\theta\rangle=\langle\delta\theta,\delta\theta\rangle+\langle
ds,\theta\rangle.$ (4.5)

Therefore, from (4.4) and (4.5) we derive

$\frac{n-2}{2n}\int_{M}({\cal L}_{\xi}\,s)\,d\,{\rm
vol}_{g}=-\langle{\delta}^{*}\theta,{\delta}^{*}\theta\rangle+\frac{1}{n}\,\langle\delta\theta,\delta\theta\rangle\leq
0,$

because $\|\varphi\|^{2}\geq\frac{1}{n}\,{({\rm trace}_{g}\,\varphi)}^{2}$ for
any covariant two-tensor $\varphi$.

The assumptions $n\geq 3$ and $\int_{M}({\cal L}_{\xi}\,s)\,d\,{\rm
vol}_{g}\geq 0$, or, in particular, ${\cal L}_{\xi}\,s\geq 0$, imply

$\langle{\delta}^{*}\theta,{\delta}^{*}\theta\rangle-\frac{1}{n}\,\langle\delta\theta,\delta\theta\rangle=0.$
(4.6)

On the other hand, the following equality is valid:

$\big{\|}\frac{1}{2}\,{\cal L}_{\xi}\,g-\frac{1}{n}\,({\rm
div}\,\xi)\,g\big{\|}^{2}=g({\delta}^{*}\theta,{\delta}^{*}\theta)-\frac{1}{n}\,(\delta\,\theta)^{2}.$
(4.7)

From (4.6) and (4.7) we find that

$\frac{1}{2}\,{\cal L}_{\xi}\,g=\frac{1}{n}\,({\rm div}\,\xi)\,g,$

i.e., $\xi$ is a conformal Killing vector field. In this case, from (4.3) we
deduce that

$\varphi={\rm Ric}-\frac{s}{n}\,g,$

to which we can apply Schur’s lemma and then conclude that $s=const$.
$\square$

A statement similar to the following corollary was proved in [17] for Ricci
solitons.

######  Corollary 4.1.

Let $(M,g,\xi,\lambda)$ be an $n$-dimensional $(n\geq 3)$ compact almost Ricci
soliton such that

$\int_{M}({\cal L}_{\xi}\,s)\,d\,{\rm vol}_{g}\geq 0$

for its scalar curvature $s$. Then $(M,g)$ is isometric to a Euclidean
$n$-sphere.

###### Proof.

For $\varphi=0$, equations (4.3) have the form of almost Ricci soliton
equations (1.1). Thus, if $(M,g,\xi,\lambda)$ is a compact almost Ricci
soliton such that

$\int_{M}\,({\cal L}_{\xi}\,s)\,d\,{\rm vol}_{g}\geq 0,$

or, in particular, ${\cal L}_{\xi}\,s\geq 0$, then it is an Einstein manifold,
and $\xi$ is a conformal Killing vector field. By [20, Corollary 4.5], the
soliton is a Euclidean sphere. $\square$

######  Remark 4.1.

The concept of almost Ricci soliton was introduced in [15] as a Riemannian
manifold $(M,g)$ satisfying the equation

${\rm Ric}+\frac{1}{2}\,{\cal L}_{V}\,g=\lambda\,g,$

where $\lambda\in C^{\infty}(M)$ and $V$ is a smooth vector field on $M$. The
above equation and (1.1) are equivalent. Namely, if we suppose that $\xi=-V$,
then we derive (1.1) from the above equation. Thus, the inequalities ${\cal
L}_{\xi}\,s\geq 0$ and $\int_{M}({\cal L}_{\xi}\,s)\,d\,{\rm vol}_{g}\geq 0$
(with the scalar curvature $s$ of the metric $g$) can be rewritten in the form
${\cal L}_{V}\,s\leq 0$ and $\int_{M}({\cal L}_{V}\,s)\,d\,{\rm vol}_{g}\leq
0$, respectively, see also [3], where inequalities are replaced by equalities.
For example, if $s=const$ along the trajectories of the flow of $\xi$ on a
compact almost Ricci soliton $(M,g,\xi,\lambda)$ with a nonconstant function
$\lambda$, then $(M,g)$ is isometric to a Euclidean $n$-sphere, see [3].

## References

  * [1] Arnold V.I., Klesin B.A.: Topological methods in hydrodynamics, Springer-Verlag, New York (1998).
  * [2] Barros A., Gomes J.N., Rebeiro E.: _A note on rigidity of almost Ricci soliton_. Archiv der Mathematik, 100, 481–490 (2013).
  * [3] Barros A., Batista R., Ribeiro jr. E.: _Compact almost Ricci solitons with constant scalar curvature are gradient_. Monatshefte für Mathematik, 174, 29–39 (2014).
  * [4] Berard P.H.: _From vanishing theorems to estimating theorems: the Bochner technique revisited_. Bulletin of the American Mathematical Society, 19 (2), 371–406 (1988).
  * [5] Besse A.L.: Einstein manifolds, Springer-Verlag, Berlin and Heidelberg (2008).
  * [6] Caminha, A.: _The geometry of closed conformal Killing vector fields on Riemannian spaces_. Bull. Braz. Math. Soc. (N.S.), 41 (2), 277–300 (2011).
  * [7] Chow B., Lu P., Ni L.: Hamilton’s Ricci flow, in Grad. Stud. in Math., 77, AMS, Providence, RI (2006).
  * [8] Deshmukh S.: _Almost Ricci solitons isometric to spheres_. Int. J. of Geom. Methods in Modern Physics. 16 (5) 1950073 (2019).
  * [9] Duggal K.L., _Almost Ricci Solitons and Physical Applications_. Int. Electronic J. of Geometry, 10 (2), 1–10 (2017).
  * [10] Kar D., Majhi P.: _Beta-almost Ricci solitons on almost co-Kähler manifolds_. Korean J. Math., 27 (3), 691–705 (2019).
  * [11] Kobayashi S., Nomizu K.: Foundations of differential geometry. Vol. I. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York (1993).
  * [12] Morgan J., Tian G.: Ricci flow and Poincare conjecture, Clay Mathematics Monographs, 3. AMS, Providence, RI; Clay Mathematics Institute, Cambridge, MA (2007).
  * [13] O’Neil B.: Semi-Riemannian geometry with applications to relativity, Academic Press, London (1983).
  * [14] Patra D.S., Rovenski V.: _Almost $\eta$-Ricci solitons on Kenmotsu manifolds_. European J. Math., 7, 1753–1766 (2021).
  * [15] Pigola S., Rigoli M., Rimoldi M., Setti A. G., _Ricci almost solitons_. Ann. Scuola Norm. Sup. Pisa Cl. Sci. 10 (4), 757–799 (2011).
  * [16] Stepanov S.E., Shandra I.G.: _Geometry of infinitesimal harmonic transformations_. Annals of Global Analysis and Geometry, 24, 291–299 (2003).
  * [17] Stepanov S. E., Shelepova V. N.: _A note on Ricci solitons_. Mathematical Notes, 86 : 3, 447–450 (2009).
  * [18] Stepanov S.E., Tsyganok I.I., Mikeš J.: _From infinitesimal harmonic transformations to Ricci solitons_. Mathematica Bohemica, 138 (1), 25–36 (2013).
  * [19] Udriste C.: Geometric dynamics, Kluwer Academic Publishers, Dordrecht (2002).
  * [20] Yano K.: Integral formulas in Riemannian geometry, Marcel Dekker, New York (1970).
  * [21] Yau, S.-T.: _Some function-theoretic properties of complete Riemannian manifold and their applications to geometry_. Indiana Univ. Math. J., 25, 659–670 (1976).