#  What makes Models Compositional?
A Theoretical View: With Supplement

Parikshit Ram<EMAIL_ADDRESS>Tim Klinger  Alexander G. Gray

###### Abstract

Compositionality is thought to be a key component of language, and various
compositional benchmarks have been developed to empirically probe the
compositional generalization of existing sequence processing models. These
benchmarks often highlight failures of existing models, but it is not clear
why these models fail in this way. In this paper, we seek to theoretically
understand the role the compositional structure of the models plays in these
failures and how this structure relates to their expressivity and sample
complexity. We propose a general neuro-symbolic definition of compositional
functions and their compositional complexity. We then show how various
existing general and special purpose sequence processing models (such as
recurrent, convolution and attention-based ones) fit this definition and use
it to analyze their compositional complexity. Finally, we provide theoretical
guarantees for the expressivity and systematic generalization of compositional
models that explicitly depend on our proposed definition and highlighting
factors which drive poor empirical performance.

##  1 Introduction

Compositionality is assumed to be integral to language processing Pagin and
Westerståhl (2010a, b). Generalizing in a compositional manner or
compositional generalization is of high interest when learning with sequences
since it can enable a (learned) model to generalize well to a possibly
infinite domain of sequences while learning from only a small number of
examples. With this motivation, there has been interest in quantifying the
compositional generalization of sequence or language models. This has led to
various language modeling benchmarks such as SCAN Lake and Baroni (2018), CFQ
Keysers et al. (2019), COGS Kim and Linzen (2020) and others Andreas (2018);
Hupkes et al. (2020), although compositional generalization can also be of
interest in vision Klinger et al. (2020).

These benchmarks empirically probe the compositionality of off-the-shelf
language models, often demonstrating the lack of compositional generalization.
These highlight examples on which the models fail, but there is no precise
understanding of why the failures occur. These findings are further put into
question by results highlighting how such models can in fact compositionally
generalize Csordás et al. (2021). Nonetheless, various novel methods with
improved compositional generalization (as measured by these benchmarks) have
been developed Russin et al. (2019); Gordon et al. (2019); Li et al. (2019);
Liu et al. (2020); Nye et al. (2020); Liu et al. (2021), utilizing specialized
models with compositional inductive biases. However, the area of compositional
generalization is still lacks a mathematical definition and measure of
compositionality.

#### Our contributions.

Inspired by existing discussions on compositionality, and recent solutions for
compositional generalization benchmarks, we make the following contributions:
111A preliminary version of this work Ram et al. (2023) was previously
presented at the KBCG@IJCAI23 workshop.

  * •

We propose a general modular definition of “compositional functions” to
facilitate concrete understanding of the expressiveness and generalization of
such functions, and propose the notion of “compositional complexity” to
quantify the complexity of such functions.

  * •

We demonstrate the flexibility of this definition by highlighting how various
existing models fit this definition, and how complex their compositions are.

  * •

Given these definitions of compositional functions and compositional
complexity, we precisely characterize the expressiveness and systematic
generalization of such functions.

##  2 Related Work

A definition of compositionality Pagin and Westerståhl (2010a) states that the
meaning $\mu(\cdot)$ of an expression is:

$\mu(\alpha(u_{1},\ldots,u_{k}))=r_{\alpha}(\mu(u_{1}),\ldots,\mu(u_{k})),$
(1)

where $\alpha$ is a (grammar) rule applied to the sub-terms $u_{i}$ to obtain
the expression $\alpha(u_{1},\ldots,u_{k})$, and $r_{\alpha}$ is a meaning
operation that depends on the rule $\alpha$. A non-technical phrasing of the
principle of compositionality Partee (1995) is(quoted from Hupkes et al.
2020): “The meaning of a whole is a function of the meanings of the parts and
of the way they are syntactically combined.” Among the expected properties of
compositional functions are systematicity – the ability to consistently handle
unknown combinations of known parts, and productivity – the ability to handle
arbitrary length sequences. For systematic generalization, a model learned
from some examples (“known parts”) is expected to generalize to unseen
examples (“unknown combinations”). Productive generalization requires learned
models to generalize to sequences longer than those seen during learning.

Understanding compositionality and its relation to systematicity has been of
long interest, and Zadrozny 1994 showed that compositional semantics can be
defined for any meaning function without necessarily inducing systematicity.
Recently, Rosenbaum et al. 2019 studied how networks (specifically routing
networks) can be composed of multiple modules, focusing mainly on the training
dynamics and empirical performance of such compositional models, while
Wiedemer et al. 2023 try to formalize compositional generalization from the
perspective of disentangled representations. In contrast to these works, we
focus on understanding the compositionality of functions in terms of
hierarchical computation needed to process the input (sequences), and the
kinds of hierarchy induced by existing sequence processing models, such as
recurrent, convolutional and attention-based models.

Dziri et al. 2023 empirically probe the compositionality of transformers on
problems that require “strict multi-step computations to derive correct
answers”, and consider the hierarchical computation necessary for the problem
solving similar to our definitions. While Dziri et al. 2023 and others Kim and
Linzen (2020); Sikarwar et al. (2022); Ontanon et al. (2022) show that
transformers struggle with such tasks, a separate line of work highlight how
transformers can be successful on compositional benchmarks Csordás et al.
(2021); Zhou et al. (2023); Drozdov et al. (2023), which begs the questions
(i) whether models (such as transformers) are at all capable of solving
compositional tasks, and (ii) when such models are able to solve compositional
tasks. Our proposed framework allows us to study such questions theoretically.

Jarvis et al. 2023 study systematicity for both datasets and functions,
showing that modular functions can systematically generalize on datasets with
compositional sub-structures, while general purpose non-modular functions do
not. However, if the function modularity is unable to appropriately segregate
the compositional sub-structure, even modular functions fail. To that end,
they study a space of datasets with cleanly separable systematic sub-
structures. In the context of Eq. 1, cleanly-separable systematic sub-
structures correspond to non-overlapping sub-terms $u_{i},i\in\llbracket
k\rrbracket$. Our proposed framework can be seen as a generalization where the
compositional sub-structures may not always be cleanly separable, but still
present, and we study general purpose sequence models and their ability to
express such compositional sub-structures.

##  3 Defining Compositionality

Our goal is to ground this principle into a mathematical form that will allow
us to quantify the compositionality of models and understand how this
quantification affects downstream compositional generalization. We define
compositional functions $f:\mathcal{X}\to\mathcal{Y}$ with the domain
$\mathcal{X}$ of input sequences $X=\\{x_{1},\ldots,x_{L}\\}$ of atoms or
tokens $x_{i}\in\mathcal{I}$ from an input dictionary $\mathcal{I}$. The range
$\mathcal{Y}$ of $f$ can be $\mathbb{R}$ for regression, $\\{0,1\\}$ for
binary classification, or $\mathcal{I}$ for next token prediction.

######  Definition 1.

To define $f$, we need the following components:

  * •

Token encoder $e:\mathcal{I}\times\mathbb{N}\to\mathcal{H}$ (latent space),
with $e_{i}=e(x_{i},i)\in\mathcal{H}$ encoding the $i^{\text{\sf th}}$ token
in $X\in\mathcal{X}$.

  * •

A computation directed acyclic graph (DAG) or cDAG
$D:\mathcal{X}\to\mathcal{D}$ (the space of DAGs), with $D(X)$ defining the
hierarchical processing of a sequence $X$. $D(X)$ can also be viewed as the
trace of program used by function $f$ to process $X$. We will describe this in
further detail soon.

  * •

Span processor $g:\mathcal{H}^{k}\to\mathcal{H}$ maps $k$ terms in the latent
space into a new term in the latent space.

  * •

Read-out function $h:\mathcal{H}^{m}\to\mathcal{Y}$ which maps the final set
of terms in the latent space to the output space $\mathcal{Y}$.

Given the above, we define a compositional function as

$f(X)=h\left(g^{\otimes D(X)}(e(x_{1},1),\ldots,e(x_{L},L))\right),$ (2)

where $g^{\otimes D(X)}$ is the recursive operation of $g$ over $D(X)$.

Next we further discuss the components.

0:11:10:20:31:22:13:10:40:5

0:10:21:12:13:10:30:41:20:5

Figure 1: cDAGs for $f(X)$ (left) and $f(X^{\prime})$ (right) in Example 1.
Nodes are labeled $l$:$i$ (level $l$, index $i$). Sources are Fuchsia, sinks
are Sepia, and internal nodes are Blue.

A computation DAG or cDAG $D(X)\triangleq\\{N(X),E(X)\\}$ for a specific input
sequence $X\in\mathcal{X}$ can depend on $X$ or be pre-specified. This cDAG is
a leveled DAG with set of nodes $N(X)$ and edges $E(X)$. Each node
$n\triangleq(l:i)\in N(X)$ has a level $l$ and index $i$ (see Section A.1 for
details). The recursive application of $g$ over $D(X)$ induces a value
$v_{l:i}\in\mathcal{H}$ for each internal node $n\in N(X)$. The sources is
$N(X)$ have level 0, and there is one source for each $x_{i}\in
X,i\in\llbracket L\rrbracket\triangleq\\{1,\ldots,L\\}$ with index $i$ and
value $v_{0:i}=e(x_{i},i)\in\mathcal{H}$. There are $m$ sinks in $N(X)$, and
at most $k$ incoming edges and $q$ outgoing edges at any node. For an internal
node $n\in N(X)$ with $k$ parents $P(n)$, the value
$v_{l:i}=g(v_{l_{1}:i_{1}},\ldots,v_{l_{k}:i_{k}})\in\mathcal{H}$ where
$v_{l_{j}:i_{j}}$ is the value of the $j^{\text{\sf th}}$ parent in $P(n)$.
Note that this cDAG corresponds to the “forward-pass” for inference.

We consider the explicit cDAG because it allows us to see how the different
elements $x_{i},i\in\llbracket L\rrbracket$ of the input sequence $X$ are
hierarchically composed to obtain the output. This will allow us to study the
complexity of any compositional function. A “simple” cDAG, where all source
nodes just connect to a single sink node, would be “applicable” to all
functions, but it does not allow us to study it in an interesting manner. When
we study the compositional functions induced by general purpose models (such
as recurrent, convolutional or transformer models), we will see that some
models have explicit cDAGs with more structure, while others have less
structured explicit cDAGs, but there are implicit structures induced in the
cDAG; whenever possible, we will explicitly state this implicit structure and
study its properties. From a neuro-symbolic perspective Sarker et al. (2021);
Garcez et al. (2022), this explicit cDAG can be seen as the symbolic part,
while the $e,g,h$ are the neural; note that, in some models, this symbolic
cDAG might be created with neural elements, while in others, the cDAG might be
obtained with a symbolic grammar. This neuro-symbolic view offers a novel
theoretical understanding of compositionality.

The span processor $g:\mathcal{H}^{k}\to\mathcal{H}$ takes as input $k$
elements from the latent space $\mathcal{H}$ and outputs an element in
$\mathcal{H}$. While the definition implies that the same $g$ needs to be
operated recursively over the cDAG $D(X)$, there is no restriction on the
inputs and output of $g$ regarding the information encoded in the latent
space. For example, if the level $l$ of any node $l$:$i$ is encoded into its
value $v_{l:i}$, then the $g$ will behave differently across levels (level-
dependent); if the index $i$ of the node $l$:$i$ is encoded into its value,
then $g$ will be sensitive to the positional information (order-dependent); if
the value of a node includes the type of the node (for example, a non-terminal
in a grammar), then $g$ can be type-dependent. Our definition states that the
arity of the span processor $g:\mathcal{H}^{k}\to\mathcal{H}$ is $k$. We do so
for the ease of exposition, though our definition can incorporate more
flexible span processors (see Section A.2).

The read-out function $h:\mathcal{H}^{m}\to\mathcal{Y}$ finally maps $m$
elements in the latent space to the output space $\mathcal{Y}$. This
separation between $g$ and $h$ was necessary in our proposed definition
because we require $g$ to be operable recursively, and thus $g$ can operate in
a latent space $\mathcal{H}$ distinct from $\mathcal{Y}$. In some
applications, $\mathcal{H}\supseteq\mathcal{Y}$, in which case, $h$ can be an
identity function. In an alternate scenario, where the $g$ function is
identity, and the cDAG function produces “trivial cDAGs” – cDAGs where the
source nodes are the sink nodes (see Fig. 3(a) for example), $h$ would
effectively be a mapping from $\mathcal{X}\to\mathcal{Y}$ (subsuming the token
encoder within $h$). But in this scenario, we are not able to explicitly view
the recursive operation desired in the “meaning of the whole is a function of
the meaning of the parts” principle of compositionality. Hence, we make this
separation between $h$ and $g$ explicit. There are couple of aspects of this
read-out function we wish to discuss explicitly – (i) We assume that $h$ is
specifically non-compositional and processes its input without breaking it up
into any sub-problems; we explicitly define the compositional function $f$
separating out $g,D,h$, where $g$ (neural) and $D$ (symbolic) represent the
compositional part. (ii) We require $h$ to have a fixed-arity of $m$ since $g$
and $D$ are aggregating the information over the input.

######  Example 1.

Figure 1 (left) shows the cDAG $D(X)$ for a compositional $f$ on
$X=[x_{1},\ldots,x_{5}]$, with
$f(X)=h\left(g\left(g\left(e_{1},e_{2}\right),g\left(g(e_{3},e_{4}),e_{5}\right)\right)\right)$,
$k=2$ in-degree, $q=1$ out-degree, $m=1$ sink,
$e_{i}=e(x_{i},i)\in\mathcal{H}$, span-processor
$g:\mathcal{H}^{2}\to\mathcal{H}$, and read-out function
$h:\mathcal{H}\to\mathcal{Y}$. The values $v_{\text{\tt 0:}i}=e_{i}$ for
sources 0:$i$, $i\in\\{1,\ldots,5\\}$, and the internal node values are:
$v_{\text{\tt 1:1}}\leftarrow g(e_{1},e_{2})$, $v_{\text{\tt 1:2}}\leftarrow
g(e_{3},e_{4})$, $v_{\text{\tt 2:1}}\leftarrow g(v_{\text{\tt 1:2}},e_{5})$,
$v_{\text{\tt 3:1}}\leftarrow g(v_{\text{\tt 1:1}},v_{\text{\tt 2:1}})$. $h$
operates on $v_{\text{\tt 3:1}}$ at sink 3:1. Figure 1 (right) shows the cDAG
$D(X^{\prime})$ of the same $f$ on $X^{\prime}\not=X$ with the same
$k=2,q=1,m=1$ and
$f(X^{\prime})=h\left(g(g(e_{1},g(e_{2},e_{3})),g(e_{4},e_{5}))\right)$.

0:11:12:13:10:21:20:31:32:23:24:10:41:42:30:51:52:40:60:7

0:10:21:12:10:30:41:22:23:14:10:51:32:30:61:42:43:24:20:71:5

Figure 2: cDAGs for $\mathsf{f}(X)$ (left) and $\mathsf{f}(X^{\prime})$
(right) in Example 2. Nodes are labeled $l$:$i$ (level $l$, index $i$).
Sources are Fuchsia, sinks are Sepia, and internal nodes are Blue.

######  Example 2.

Figure 2 (left) shows the cDAG $\mathsf{D}(X)$ for a compositional
$\mathsf{f}$ on $X=[x_{1},\ldots,x_{7}]$, with
$\mathsf{f}(X)=\mathsf{h}\left(v_{\text{\tt 4:1}},v_{\text{\tt 3:1}}\right)$,
$k=3$ maximum in-degree, $q=3$ maximum out-degree, $m=2$ sinks,
$e_{i}=e(x_{i},i)\in\mathcal{H}$, span processor
$\mathsf{g}:\mathcal{H}^{3}\to\mathcal{H}$, and read-out function
$\mathsf{h}:\mathcal{H}^{2}\to\mathcal{Y}$. The source values $v_{\text{\tt
0:}i}=e_{i}$ for each $i\in\\{1,\ldots,7\\}$, and the internal node values
are: $v_{\text{\tt 1:1}}\leftarrow\mathsf{g}(e_{1},e_{2},e_{3})$,
$v_{\text{\tt 1:2}}\leftarrow\mathsf{g}(e_{2},e_{3},e_{4})$, $v_{\text{\tt
1:3}}\leftarrow\mathsf{g}(e_{3},e_{5},e_{7})$, $v_{\text{\tt
1:4}}\leftarrow\mathsf{g}(e_{4},e_{5},e_{6})$, $v_{\text{\tt
1:5}}\leftarrow\mathsf{g}(e_{5},e_{6},e_{7})$, $v_{\text{\tt
2:1}}\leftarrow\mathsf{g}(v_{\text{\tt 1:1}},v_{\text{\tt 1:2}},v_{\text{\tt
1:3}})$, $v_{\text{\tt 2:2}}\leftarrow\mathsf{g}(v_{\text{\tt
1:1}},v_{\text{\tt 1:3}},v_{\text{\tt 1:4}})$, $v_{\text{\tt
2:3}}\leftarrow\mathsf{g}(v_{\text{\tt 1:2}},v_{\text{\tt 1:4}},v_{\text{\tt
1:5}})$, $v_{\text{\tt 2:4}}\leftarrow\mathsf{g}(v_{\text{\tt
1:3}},v_{\text{\tt 1:4}},v_{\text{\tt 1:5}})$, $v_{\text{\tt
3:1}}\leftarrow\mathsf{g}(v_{\text{\tt 2:1}},v_{\text{\tt 2:2}},v_{\text{\tt
2:3}})$, $v_{\text{\tt 3:2}}\leftarrow\mathsf{g}(v_{\text{\tt
2:2}},v_{\text{\tt 2:3}},v_{\text{\tt 2:4}})$, $v_{\text{\tt
4:1}}\leftarrow\mathsf{g}(v_{\text{\tt 3:2}},v_{\text{\tt 2:3}},v_{\text{\tt
2:4}})$. $\mathsf{h}$ operates on $v_{\text{\tt 3:1}}$ and $v_{\text{\tt
4:1}}$ at sinks 3:1 and 4:1. Figure 2 (right) shows the cDAG
$\mathsf{D}(X^{\prime})$ of the same $\mathsf{f}$ on $X^{\prime}\not=X$ with
the same $k=3,q=3,m=2$.

While Example 1 is a simple compositional function on a sequence, Example 2 is
a more sophisticated one. This is to highlight that our proposed Definition 1
can handle functions which require more complex interactions between the
tokens in a sequence. Example 1 has a cDAG with a maximum out-degree $q=1$,
implying a single path from any source to a sink. Example 2 has a cDAG with a
maximum out-degree $q=3$ across all levels in the DAG, implying that there can
be a large number of paths to any sink from a source. This allows the
definition to include functions where certain tokens in the sequence are of
much higher importance to the output than others. These examples also
highlight that edges in the cDAG are allowed to skip levels, and the sinks can
be from different levels, further highlighting the compositional flexibility.

We like to remark on a couple of points here: (i) Through these examples, we
show that our definition explicitly considers how the problem of sequence
processing is broken up into sub-problems – the cDAG embodies how disjoint or
intertwined these “sub-problems” are by explicitly considering the computation
hierarchy. (ii) For input sequences $X,X^{\prime}$ from the same problem
domain, and the same compositional function $f$, we allow the cDAG to be
different – cDAG $D(X)$ can be input-dependent – thereby allowing different
input sequences to have different sub-problem hierarchies.

Before we discuss properties of this form of compositional functions, we note
that such a precise yet flexible definition is one of our contributions, and
we will show how existing models (architectures) fit this definition. It is a
precise elaboration of the succinct recursive Eq. 1 – we make precise the
recursion, and how the sub-terms $u_{i}$ are recursively built up. At a non-
technical level, we also believe that our proposed Definition 1 connects
intuitively to existing definitions:

$\begin{split}\underbrace{\text{\footnotesize The meaning of the
whole}}_{f:\mathcal{X}\to\mathcal{Y}}\text{\footnotesize is
a}\underbrace{\text{\footnotesize
function}}_{h:\mathcal{H}^{m}\to\mathcal{Y}}\text{\footnotesize
of}\underbrace{\text{\footnotesize the meanings of the
parts}}_{g:\mathcal{H}^{k}\to\mathcal{H}}\\\ \text{\footnotesize
and}\underbrace{\text{\footnotesize of the way they are syntactically
combined.}}_{D:\mathcal{X}\to\mathcal{D}}\end{split}$

Both Examples 1 and 2 can be seen as compositional functions, but Example 2 is
clearly a more complex composition. In addition to its intuitive nature, our
proposed definition allows us to understand how complex the compositionality
is beyond just stating if a function is compositional.

#### Compositional Complexity.

This depends on the functions $g,h,e$ as well as the cDAG function $D$ that
drives the computation. For a sequence $X$ of length $L$, $D(X)$ has $L$
source nodes, maximum in-degree of $k$ (controlling the span size for $g$),
$m$ sink nodes (controlling the capacity of $h$), maximum out-degree of $q$
(quantifying the “localism” of the effect of a node). However, these do not
explicitly incorporate the fact that changes to nodes at lower levels of the
cDAG can have a larger effect on the output than changes to nodes at higher
levels of the cDAG. Instead, we propose a new quantification – the locus of
influence or LoI of any source node:

######  Definition 2 (LoI of a source node).

Consider a compositional function $f$ with components $e,D,g,h$ (as in
Definition 1). Let
$(v_{n_{1}},\ldots,v_{n_{j}},\ldots,v_{n_{k}})\in\mathcal{H}^{k}$ be any input
to the span processor $g$, with
$v_{n}=g(v_{n_{1}},\ldots,v_{n_{j}},\ldots,v_{n_{k}})$ its output. Let
$\varepsilon\in\mathcal{H}$ be a “perturbation” to the $j^{\text{th}}$
argument to $g$, $j\in\llbracket k\rrbracket$, resulting in the perturbed
output
$v_{n}^{j}(\varepsilon)=g(v_{n_{1}},\ldots,v_{n_{j}}+\varepsilon,\ldots,v_{n_{k}})$.
Let $c>0$ be an universal constant such that $\forall j\in\llbracket
k\rrbracket$, $\forall\varepsilon\in\mathcal{H}$,

$\left\|v_{n}-v_{n}^{j}(\varepsilon)\right\|\leq c\|\varepsilon\|.$ (3)

For a sequence $X\in\mathcal{X}$ of length $L$, and a source node 0:$i$ in
$D(X)$, let $P(x_{i})$ be the set of all unique paths from 0:$i$ to any of the
sink nodes in $D(X)$. We define the absolute LoI of index $i$ as
$\delta_{i}=\sum_{P\in P(x_{i})}c^{|P|}$, with $|P|$ as the length of a path
$P\in P(x_{i})$, and the relative LoI as
$\beta_{i}=\delta_{i}/\sum_{j\in\llbracket L\rrbracket}\delta_{j}$.

This definition of the complexity of composition incorporates both the
complexity of the cDAG $D(X)$ and the complexity of the span processor
$g:\mathcal{H}^{k}\to\mathcal{H}$ in terms of its smoothness, with higher
values of $c$ indicating more complex (less smooth) $g$. The absolute LoI
$\delta_{i}$ incorporates the effect of longer paths, with the effect growing
with path length, and corresponds to the sensitivity of the compositional
function output to any one input token in the sequence.

The smaller the absolute LoI $\delta_{i}$ of any input index $i$, more local
its effect, and thus more structure that can be transferred between examples
if $x_{i}$ is replaced with something else. A relative LoI $\beta_{i}$ greater
than $1/L$ denotes that the input index $i$ (and thus input token $x_{i}$) has
an out-sized effect on $D(X)$ (and thus the computation) compared to the other
indices (tokens). In Example 1 (left),
$\delta_{1}=c^{2},\beta_{1}=\nicefrac{{1}}{{2c+3}}<\nicefrac{{1}}{{5}}$ while
$\delta_{3}=c^{3},\beta_{3}=\nicefrac{{c}}{{2c+3}}>\nicefrac{{1}}{{5}}$,
implying that $x_{3}$ has more influence (absolute and relative) function than
$x_{1}$ (assuming $c>1$). In Example 2 (left),
$\delta_{1}=c^{4}+2c^{3},\beta_{1}=\nicefrac{{c+2}}{{27c+39}}\approx\nicefrac{{1}}{{22}}<\nicefrac{{1}}{{7}}$,
while
$\delta_{5}=7c^{4}+9c^{3},\beta_{5}=\nicefrac{{7c+9}}{{27c+39}}\approx\nicefrac{{1}}{{4}}>\nicefrac{{1}}{{7}}$,
hence $x_{5}$ has a significantly larger influence than $x_{1}$.

We utilize the LoI to define the complexity of a compositional function, and a
class of such compositional functions:

######  Definition 3.

A function $f:\mathcal{X}\to\mathcal{Y}$ with components $g,h,e,D$ is
$(k,q,m,{\boldsymbol{\delta}},{\boldsymbol{\beta}})$-compositional if, for any
$X\in\mathcal{X}$ of length $L$ (that is, $|X|=L$), the cDAG $D(X)$ has a in-
degree of $k$, maximum outgoing degree of $q$, and $m$ sink nodes, and for
$\forall i\in\llbracket L\rrbracket,\delta_{i}\leq{\boldsymbol{\delta}}$, and
$\beta_{i}\leq{\boldsymbol{\beta}}\in[1/L,1)$. We denote with $\mathcal{F}$ a
class of such
$(k,q,m,{\boldsymbol{\delta}},{\boldsymbol{\beta}})$-compositional functions.

A small ${\boldsymbol{\delta}}$ and a ${\boldsymbol{\beta}}$ close to $1/L$
signifies a function that possesses a high level of localism across all input
sequences and tokens in its domain. While this function has the most
structure, it might not be suitable for practical purposes. A high
${\boldsymbol{\delta}}$ and a ${\boldsymbol{\beta}}$ close to $1/L$ signifies
a very complex function where there is a lot of interaction between all the
input tokens in all input sequences, making it hard to exploit any
compositional structure in the function. A high ${\boldsymbol{\delta}}$ and a
${\boldsymbol{\beta}}$ significantly higher than $1/L$ indicates an
interesting class of functions where, some input tokens can have a high
influence over the function computation, but, for most tokens, there is a
compositional structure in the function that can be exploited. This
intuitively seems to be an interesting and more practical class of
compositional functions since assuming all tokens have an equal level of
relative influence seems quite restrictive.

#### Cleanly-separable systematic sub-structures.

Revisiting Eq. 1, where $u_{i}$ are sub-parts, we highlight a special case of
our proposed Definition 3 of compositional functions: If the sub-parts
$u_{i},u_{j},i\not=j$ are non-overlapping throughout the recursion, up to the
base case where the sub-parts, $u_{i}$, are the tokens in the input, then it
would induce a cDAG with a maximum outgoing degree $q=1$. This implies that
the number of paths $|P(x_{i})|=1$ for any source 0:$i$ – there is a single
source-to-sink path for any source, resulting in a cDAG with significantly
reduced compositional complexity.

##  4 Existing Models as Compositional Functions

Here we will discuss various model classes induced by existing model
architectures, how they fit Definition 1 of compositional functions, and how
they compare to each other. We will re-express existing sequence processing
models as per our definition, teasing out the symbolic cDAG (and the neural
$g,h$) and studying their compositional complexity. The presented cDAG for
each model class corresponds to a “forward-pass” for inference. Omitted
technical details are in Appendix B.

0:11:10:21:20:31:30:41:4 (a) No hierarchy

0:11:12:13:10:20:30:4 (b) Unidirectional recurrence

0:11:12:13:10:20:30:41:22:23:2 (c) Bidirectional recurrence

0:10:21:12:10:31:20:4 (d) Binary tree

Figure 3: Existing models - I. Nodes are labeled $l$:$i$ (level $l$, index
$i$). Sources are Fuchsia, sinks are Sepia, and internal nodes are Blue.

We begin with the trivial cDAG of no hierarchical composition in Fig. 3(a).
All sources in $D(X)$ connect to separate sinks. The composition is written as
$h(g(e_{1}),g(e_{2}),g(e_{3}),g(e_{4}))$. For $L$-length inputs, this is a
$(k=1,q=1,m=L,{\boldsymbol{\delta}}=c,{\boldsymbol{\beta}}=\nicefrac{{1}}{{L}})$-compositional
function class.

###  4.1 Recurrent Composition

Figure 3(b) presents an example cDAG for unidirectional recurrent composition,
with the corresponding compositional function
$h(g(g(g(e_{1},e_{2}),e_{3}),e_{4}))$. Specific choices of the $g$ and $h$
functions would give us specific recurrent neural network (RNN) models. The
cDAG recursively combines 2 nodes in the order of the original sequence to get
a class of compositional functions with $(k=2,q=1,m=1)$. The cDAG is input-
agnostic, that is $D(X)=D(X^{\prime})\forall X,X^{\prime}\in\mathcal{X}$ with
$|X|=|X^{\prime}|$. This composition can operate on arbitrary length
sequences, and its complexity is quantified as:

######  Proposition 1.

With unidirectional recurrent composition, the maximum absolute LoI is
${\boldsymbol{\delta}}\triangleq c^{L-1}$, with a maximum relative LoI of
${\boldsymbol{\beta}}\triangleq(c^{L}-c^{L-1})/(2c^{L}-c^{L-1}-1)$.

The absolute LoI is large (exponential in the input length), and the relative
LoI is close to $\nicefrac{{1}}{{2}}\gg\nicefrac{{1}}{{L}}$ for large enough
$L$.

Figure 3(c) is an example of a cDAG of a bidirectional recurrent composition,
which can be written algebraically as
$h(g(g(g(e_{1},e_{2}),e_{3}),e_{4}),g(g(g(e_{4},e_{3}),e_{2}),e_{1}))$. The
cDAG recursively combines 2 nodes in the order of the sequence, then in the
reverse order, giving us a function class with $(k=2,q=2,m=2)$. This is
similar to the unidirectional recurrence, but with two sink nodes instead of
one, and can operate on arbitrary length sequences but the cDAG is input-
agnostic. The compositional complexity is given by:

######  Proposition 2.

With bidirectional recurrent composition, the maximum absolute LoI is
${\boldsymbol{\delta}}\triangleq c^{L-1}+c$, with a maximum relative LoI of
${\boldsymbol{\beta}}\triangleq(c^{L}-c^{L-1}+c^{2}-c)/2(2c^{L}-c^{L-1}-1)$.

Note that, while the ${\boldsymbol{\delta}}$ for the bidirectional recurrent
composition remains of the same order as that of the unidirectional recurrent
one, ${\boldsymbol{\beta}}$ is approximately halved (approaching $1/4$).

Figure 3(d) shows an example of a balanced tree recurrent composition by
utilizing a balanced binary-tree cDAG with $(k=2,q=1,m=1)$ (as in a TreeLSTM
Tai et al. (2015)), with an algebraic form
$h(g(g(e_{1},e_{2}),g(e_{3},e_{4})))$. The cDAG is input-agnostic (like the
previous two), but can operate on arbitrary length sequences. The
compositional complexity is:

######  Proposition 3.

With balanced binary-tree recurrent composition, the maximum absolute LoI is
${\boldsymbol{\delta}}\triangleq c^{\lceil\log_{2}L\rceil}$, with a maximum
relative LoI of ${\boldsymbol{\beta}}\triangleq 1/L$.

This form of composition significantly reduces the complexity of the cDAG
relative to the previous two models both in terms of ${\boldsymbol{\delta}}$
(linear dependence in $L$ instead of exponential) and ${\boldsymbol{\beta}}$
($1/L$ instead of a constant $\gg 1/L$). There are versions of the tree
recurrent composition that leverage the parse tree of the input to define the
cDAG Socher et al. (2010), and thus, natively fit our definition. Here the
cDAG will no longer be input-agnostic, and Proposition 3 would not apply; the
complexity will depend on the grammar driving the input-dependent parse trees.
Various models Bowman et al. (2016); Shen et al. (2018, 2019) integrate parse-
tree structures into a RNN for an input-dependent cDAG for the recurrent
composition. They learn to generate a parse-tree for any given input (either
via supervision from an external parser or directly from the data). All these
models fit our definition of compositional functions with an input-dependent
tree-based cDAG. 222To the best of our knowledge, none of these architectures
have been evaluated with compositional generalization benchmarks, although the
motivations for these models leveraging parse-trees align well with the goals
of compositional generalization.

0:10:21:10:30:41:22:10:50:61:30:7 (a) Convolve + Pool

0:11:12:10:21:22:20:31:32:30:41:42:40:51:52:50:61:62:60:71:72:73:1 (b)
Transformer

0:11:12:10:21:22:20:31:32:30:41:42:40:51:52:50:61:62:60:71:72:73:1 (c)
Transformer + sparse att.

0:11:12:10:21:22:20:31:32:30:41:42:40:51:52:50:61:62:60:71:72:73:1 (d)
Decoder-only Transformer

Figure 4: Existing models - II. Nodes are labeled $l$:$i$ (level $l$, index
$i$). Sources are Fuchsia, sinks are Sepia, and internal nodes are Blue.

###  4.2 Convolutional Composition with Pooling

Figure 4(a) shows an example cDAG induced by repeated application of
convolution-then-pooling or conv+pool, performing a convolution over a span of
size 2, and pooling over a span of size 2 in this example (see Fig. 5(a) for a
detailed version of Fig. 4(a) that shows how repeated conv+pool implicitly
induces the cDAG in Fig. 4(a); Fig. 5(e) and corresponding cDAG in Fig. 5(f)
provides an example of convolution with padding over a span of size 2 and
pooling over a span of 3). The composition in Fig. 4(a) can be algebraically
written as
$h(g(g(e_{1},e_{2},e_{3}),g(e_{3},e_{4},e_{5}),g(e_{5},e_{6},e_{7})))$. In
general, we can consider a span processor $g$ function that performs
convolution over a span of size $w$ and then pools over a span of $p$. Here,
the number of sinks $m$ has to be user-specified, and the cDAG repeatedly
applies conv+pool until it reduces the number of nodes at the highest level to
$m$. This induces a compositional function class with $(k=w+p-1,q=w)$.

######  Proposition 4.

Assuming that $1<w,p\ll L$, the conv+pool composition has a maximum absolute
LoI of ${\boldsymbol{\delta}}\sim\mathcal{O}(c^{\log L})$, and a maximum
relative LoI of ${\boldsymbol{\beta}}\sim\mathcal{O}(2/(L(1+1/p)))$.

We would like to highlight an important subtlety here: If we utilize average
or sum pooling, the cDAG is input-agnostic; if the pooling is selective, such
as in max-pooling or min-pooling, some of the edges in the cDAG implicitly get
deactivated during the recursive computation of the function, leading to an
input-dependent cDAG – the cDAG itself depends on the input sequence, and can
change between inputs of same length. Figure 5(c) shows an example of
selective pooling, with the corresponding input-dependent cDAG shown in Fig.
5(d). This function can operate on arbitrary length input sequences.

###  4.3 Transformers

Figure 4(b) expresses the cDAG of a transformer with $M$ levels or “blocks”,
where the span-processor $g:\mathcal{H}^{k}\to\mathcal{H}$ is a transformer
block with the (multi-headed) self-attention, residual connections, layer
normalization, and the token-wise ReLU network Vaswani et al. (2017) (see
Section B.5). We consider the version where, for inference, only the last
token representation (after $M$ transformer blocks) is utilized for prediction
333The last token can be a [CLS] token for aggregation. – the read-out
function only applies to the last token representation. For a input sequence
of length $L$, $k=q=L$, with $m=1$ sink node. The compositional complexity is:

######  Proposition 5.

A transformer based composition with $M$ blocks has a the maximum absolute LoI
of ${\boldsymbol{\delta}}={L}^{M+1}c^{M+1}$, and a maximum relative LoI of
${\boldsymbol{\beta}}=1/L$.

This function class has a really high ${\boldsymbol{\delta}}$ (exponential in
the number of blocks $M$ but polynomial in the input length $L$ unless $M>L$)
and the lowest possible ${\boldsymbol{\beta}}=1/L$ – the output is equally
sensitive to all tokens in the sequence. It is interesting to contrast this
complexity to that of a balanced binary-tree recurrent composition, which has
the same level of relative LoI ${\boldsymbol{\beta}}=1/L$, but the
${\boldsymbol{\delta}}$ is linear in $L$ instead of polynomial (or exponential
if $M>L$); the unidirectional and bidirectional recurrent compositions have an
exponential dependence on the length $L$ (but much larger
${\boldsymbol{\beta}}$).

This composition does not explicitly have an input-dependent cDAG – all nodes
at a level always connect to all nodes at the next level since all attention
(scores) are positive. In practice, the attention weights are obtained with
softmax activation, which pushes the attention to be approximately sparse. If
we consider the attention to be exactly sparse Tay et al. (2022) with $K\ll L$
nonzero scores (rest zero), the cDAG will have much fewer edges as in Fig.
4(c) (here, $K=3$). If the attention weights and sparsity pattern are input-
dependent (as in with top-$K$ attention Gupta et al. (2021)), transformers
with hard attention will have input-dependent cDAGs. Here $k=K,q=L,m=1$, and
the compositional complexity is:

######  Proposition 6.

A transformer with $M$ blocks and $K$-sparse attention ($K\ll L$) has a
maximum absolute LoI of ${\boldsymbol{\delta}}=LK^{M}c^{M+1}$, and a maximum
relative LoI of ${\boldsymbol{\beta}}=1/K$.

Contrasting this to the complexity of the standard transformer (Proposition
5), we see that the ${\boldsymbol{\delta}}$ is considerably lower
($\mathcal{O}(L{L}^{M})$ vs $\mathcal{O}(LK^{M})$ with $K\ll L$), implying
that the LoI of any one input token (thus the sensitivity) is substantially
reduced. However, the relative LoI ${\boldsymbol{\beta}}$ can be considerably
higher ($1/L$ vs $1/K$), indicating that the composition is allowed to be
relatively more sensitive to certain tokens than others. Attention-based span-
processor $g$ can handle arbitrary length inputs (albeit at quadratic
computation per block/level), and the read-out function $h$ always has a fixed
arity of $m=1$. Thus, this transformer can operate on arbitrary length inputs.
444One practical length limitation with transformers is the (learned) absolute
positional encoding. However, that can be mitigated with the use of relative
positional encoding Shaw et al. (2018).

If we consider a decoder-only transformer, then for all levels $l<M$, all
edges from nodes $l$:$i\to l$+$1$:$j$ for $j<i$ would no longer be in the cDAG
(Fig. 4(d)). The complexity is:

######  Proposition 7.

A decoder-only transformer with $M$ blocks has a maximum absolute LoI is
${\boldsymbol{\delta}}=L^{M}c^{M+1}$, and a maximum relative LoI of
${\boldsymbol{\beta}}=1/(1+\sum_{i\in\llbracket
L-1\rrbracket}(\nicefrac{{i}}{{L}})^{M})$.

As $L$ or $M$ grows, the sum $\sum_{i}(\nicefrac{{i}}{{L}})^{M}$ goes to zero,
and thus, ${\boldsymbol{\beta}}\to 1$. For some $\Delta\in(0,1)$,
${\boldsymbol{\beta}}\triangleq 1/(1+r\Delta)$ for the largest $r\in\llbracket
L\rrbracket$ such that $\Delta\leq(1-r/L)^{M}$. We can similarly study the
decoder-only transformer with sparse/hard attention.

#### Efficient transformers.

While transformers are able to handle arbitrary length input, their
computational cost scales quadratically in the input length $L$ (compared to
the linear cost of recurrent models). To mitigate this issue, various
“efficient” transformers have been proposed Tay et al. (2022); Lin et al.
(2022). Various sparse attention mechanisms have been studied, utilizing
block-local, dilated, global or banded attention (see Lin et al.2022, Figure
4). These architectures reduce the quadratic cost often to almost linear. In
terms of their compositional complexity, these architectures can easily be
studied within our proposed framework, and will have significantly lower
complexity compared to the vanilla transformer (smaller
${\boldsymbol{\delta}}$, similar ${\boldsymbol{\beta}}$). However, these
architectures induce an input-agnostic sparsity pattern, thus leading to
input-agnostic cDAGs. In contrast, sparse attention schemes with input-
dependent sparsity patterns such as top-$K$ attention Gupta et al. (2021) and
sparse Sinkhorn attention Tay et al. (2020) induce input-dependent cDAGs.

Table 1: Complexities of existing models. LoI is specified approximately for the ease of exposition. IDC: Input-dependent cDAG. AL:  Arbitrary length operation. $\blacklozenge$: The cDAG can be input-dependent if a input parse tree is available. ${\dagger}$: Conv+Pool induces input-dependent cDAGs for max/min-pool, not for avg/sum-pool. ${\ddagger}$: The number of sinks $m$ needs to be specified for conv+pool, and the model can handle arbitrary length if it can recursively conv+pool until the number of nodes is reduced to $m$. $\bullet$: See discussion after Proposition 7. Model | IDC | AL | $(k,q,m)$ | ${\boldsymbol{\delta}}$ | ${\boldsymbol{\beta}}$
---|---|---|---|---|---
No-hier.(3(a)) | ✗ | ✗ | $(1,1,L)$ | $c$ | $1/L$
U-RNN(3(b)) | ✗ | ✓ | $(2,1,1)$ | $c^{L-1}$ | $1/2$
B-RNN(3(c)) | ✗ | ✓ | $(2,2,2)$ | $c^{L-1}$ | $1/4$
T-RNN(3(d)) | $\blacklozenge$ | ✓ | $(2,1,1)$ | $c^{\log L}$ | $1/L$
Cnv+pl(4(a)) | ${\dagger}$ | ${\ddagger}$ | $(\text{$w$+$p$},w,m)$ | $c^{\log L}$ | $\frac{2/L}{1+\nicefrac{{1}}{{p}}}$
Trf(4(b)) | ✗ | ✓ | $(L,L,1)$ | $(Lc)^{M}$ | $1/L$
SA-Trf(4(c)) | ✓ | ✓ | $(K,L,1)$ | $L(Kc)^{M}$ | $1/K$
D-Trf(4(d)) ∙ | ✗ | ✓ | $(L,L,1)$ | $(Lc)^{M}$ | $\frac{1}{(1+r\Delta)}$

###  4.4 Discussion

We discussed various existing sequence processing models in the context of our
definition of compositional functions (Definitions 1 and 3), and quantify
their corresponding complexities in the form of bounds on the absolute LoI
${\boldsymbol{\delta}}$ and relative LoI ${\boldsymbol{\beta}}$. We summarize
these properties in Table 1 to compare different models. Beyond complexities,
we also specify (i) whether they can operate on arbitrarily long sequences,
and (ii) whether the cDAGs are input-dependent or input-agnostic for some
fixed input length $L$. In Section B.9, we discuss a model’s ability to
process arbitrary lengths, and how it relates to parameter sharing across
different cDAG levels. Here, we focus on the topic of input-agnostic vs input-
dependent cDAGs.

As we summarize in Table 1, the only model with explicitly input-dependent
cDAG is the sparse attention versions of the transformer (and the tree based
recurrence if the tree is input-dependent). The conv+pool composition
implicitly induces an input-dependent cDAG if the pooling operation is
explicitly selective (such as using max-pooling or min-pooling).

Given (i) the success of the softmax attention mechanism in sequence
processing tasks, (ii) the use of explicitly input-dependent cDAGs in
efficient transformers such as Sinkhorn transformers, tree-based RNNs, and
specialized models for compositional generalization, and (iii) the wide use of
max/min-pooling instead of sum/average pooling (especially in vision tasks),
we think it is important to rigorously understand the value of input-dependent
cDAGs. First, it is fair to assume that most realistic problems involve input-
dependent cDAGs. For example, if the input, and the corresponding output, are
generated from a grammar, then the cDAG of any input $X$ would be closely
related to its parse-tree.

To this end, we specifically study the ability of the compositional function
with an input-agnostic cDAG to approximate a compositional function with
input-dependent cDAGs. We present a condensed version of the result for ease
of exposition; the detailed version and proof is presented in Appendix C:

######  Theorem 1 (condensed).

Consider a $(k,q,m,{\boldsymbol{\delta}},{\boldsymbol{\beta}})$-compositional
function class $\mathcal{F}$, and input sequences $X\in\mathcal{X}$ of length
$L$. Consider a ground-truth function $f\in\mathcal{F}$ with components
$e,D,g,h$, and a compositional function $\mathsf{f}\in\mathcal{F}$ with
components $e,\mathsf{D},\mathsf{g},\mathsf{h}$, with an input-agnostic cDAG
such that $\mathsf{D}(X)={\mathsf{D}}\,\forall X\in\mathcal{X},|X|=L$. 555We
assume that the token encoder $e$ is same for both $f,\mathsf{f}$. Then the
worst-case approximation of $f$ by $\mathsf{f}$, for
$f,\mathsf{f}\in\mathcal{F}$ is given by:

$C_{l}{\boldsymbol{\delta}}\leq\max_{\begin{subarray}{c}D,g,h,\\\
f\triangleq\\{e,D,g,h\\},\\\
f\in\mathcal{F},X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}{\mathsf{D}},\mathsf{g},\mathsf{h},\\\
\mathsf{f}\triangleq\\{e,\mathsf{D},\mathsf{g},\mathsf{h}\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|f(X)-\mathsf{f}(X)\right|\leq
C_{u}\frac{{\boldsymbol{\delta}}}{{\boldsymbol{\beta}}},$ (4)

where $f(X)=h(g^{\otimes D(X)}(e(x_{1}),\ldots,e(x_{L}))$, and
$\mathsf{f}(X)=\mathsf{h}(\mathsf{g}^{\otimes{\mathsf{D}}}(e(x_{1}),\ldots,e(x_{L}))$,
with general smoothness and structural assumptions, and universal constants
$C_{l},C_{u}>0$.

This result provides an upper and lower bound on the approximation error. Even
if we select the best possible fixed cDAG $\mathsf{D}$, and corresponding span
processor $\mathsf{g}$ and read-out function $\mathsf{h}$ (the $\min$ over
$\\{{\mathsf{D}},\mathsf{g},\mathsf{h}\\}$ for the approximation
$\mathsf{f}\in\mathcal{F}$), there are compositional functions $f$ such that,
for some input $X$ (the $\max$ over $\\{D,g,h\\}$ for $f\in\mathcal{F}$, and
the input $X\in\mathcal{X}$), the approximation error is at least
$\mathcal{O}({\boldsymbol{\delta}})$. The approximation is bounded from above
by $\mathcal{O}({\boldsymbol{\delta}}/{\boldsymbol{\beta}})$; note that the
maximum relative LoI ${\boldsymbol{\beta}}\in[1/L,1]$. This indicates that
function classes with large ${\boldsymbol{\delta}}$ are hard to approximate
with an input-agnostic cDAG of the same complexity. Furthermore, for the same
${\boldsymbol{\delta}}$, smaller ${\boldsymbol{\beta}}$ worsen the upper
bound. Overall, function classes with small ${\boldsymbol{\delta}}$, or
moderate ${\boldsymbol{\delta}}$ with large ${\boldsymbol{\beta}}$ can be
approximated well with input-agnostic cDAGs. As discussed earlier, for
function classes of particular interest to us, with moderately high
${\boldsymbol{\delta}}$ and high ${\boldsymbol{\beta}}$, input-agnostic cDAGs
do not provide promising approximation, though larger ${\boldsymbol{\beta}}$
is more favorable. This result makes precise the intuition that input-agnostic
cDAGs are not expressive enough to appropriately approximate functions with
input-dependent cDAGs.

We also study systematic generalization within our framework. We consider a
special class of compositional functions with a maximum out-degree $q=1$ in
the cDAG, inducing “cleanly-separable” sub-structures, and further focus on
the case with maximum in-degree $k=2$ and a single sink ($m=1$) in the cDAG.
Given a class of (compositional) functions $\mathcal{F}$, and training data
$S$, generalization guarantees bound the difference between the true risk
$R(\hat{f})=\mathbb{E}_{(X,y)}\ell(y,\hat{f}(X))$ of a learned model
$\hat{f}\in\mathcal{F}$ and its empirical risk $R_{N}(\hat{f})$. Here we
present a condensed result; see Appendix D for details.

######  Theorem 2 (condensed).

Consider a $(2,1,1,{\boldsymbol{\delta}},{\boldsymbol{\beta}})$-compositional
function class $\mathcal{F}$, input $X\in\mathcal{X}$ of length $L$, a
training set $S$ of $N$ samples from a ground-truth function $f\in\mathcal{F}$
with components $e,D,g,h$. Assume that the token encoder $e$ and the cDAG
function $D$ are given, and we only learn the span encoder $\hat{g}$ and the
read-out function $\hat{h}$ to get $\hat{f}\triangleq(e,D,\hat{g},\hat{h})$.
Then, with probability at least $1-\xi$,

$\left|R(\hat{f})-R_{N}(\hat{f})\right|\leq\gamma{\boldsymbol{\delta}}C_{N}\left(1+2N\sqrt{\frac{2\log(2/\xi)}{N}}\right),$
(5)

where $C_{N}$ is a quantity dependent on $N$ and $\xi\in(0,1)$.

If the model class $\mathcal{F}$ is expressive, the empirical risk
$R_{N}(\hat{f})$ can be small. If $C_{N}\sim O(\nicefrac{{1}}{{N}})$, then we
recover the standard $O(\nicefrac{{1}}{{\sqrt{N}}})$ rate. However, if the
compositional complexity, ${\boldsymbol{\delta}}$, is high, this bound does
not provide a favorable systematic generalization guarantee, highlighting
that, even with cleanly-separable compositions ($q=1$), our proposed
compositional complexity is directly tied to the systematic generalization.

##  5 Conclusion

In this paper, we proposed a precise novel definition of compositional
functions, separating out the neural and symbolic parts, and a consequent
compositional complexity, which explicitly quantifies the complexity in the
(symbolic) computation trace or the cDAG of any compositional function. We
demonstrated how existing models, such as recurrent, convolutional or
attention-based ones, fit into our proposed definition, allowing us to compute
and compare their compositional complexities. We categorized models into those
with input-dependent compositions and those with input-agnostic ones, and
established theoretical guarantees on the (in)ability of input-agnostic
compositions to approximate input-dependent ones. Based on this theoretical
framework, we also establish compositional generalization guarantees for
learned compositional functions, rigorously connecting our proposed notion of
compositional complexity to systematic generalization.

## References

  * Andreas [2018] Jacob Andreas.  Measuring compositionality in representation learning.  In _International Conference on Learning Representations_ , 2018.
  * Bousquet and Elisseeff [2000] Olivier Bousquet and André Elisseeff.  Algorithmic stability and generalization performance.  _Advances in Neural Information Processing Systems_ , 13, 2000.  URL https://proceedings.neurips.cc/paper_files/paper/2000/file/49ad23d1ec9fa4bd8d77d02681df5cfa-Paper.pdf.
  * Bowman et al. [2016] Samuel Bowman, Jon Gauthier, Abhinav Rastogi, Raghav Gupta, Christopher D Manning, and Christopher Potts.  A fast unified model for parsing and sentence understanding.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1466–1477, 2016\.  URL https://aclanthology.org/P16-1139.pdf.
  * Csordás et al. [2021] Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber.  The devil is in the detail: Simple tricks improve systematic generalization of transformers.  In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih, editors, _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 619–634, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.49.  URL https://aclanthology.org/2021.emnlp-main.49.
  * Dehghani et al. [2019] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser.  Universal transformers.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=HyzdRiR9Y7.
  * Drozdov et al. [2023] Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou.  Compositional semantic parsing with large language models.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=gJW8hSGBys8.
  * 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, et al.  Faith and fate: Limits of transformers on compositionality.  _Advances in Neural Information Processing Systems_ , 36, 2023.  URL https://arxiv.org/pdf/2305.18654.pdf.
  * Garcez et al. [2022] Artur d’Avila Garcez, Sebastian Bader, Howard Bowman, Luis C Lamb, Leo de Penning, BV Illuminoo, Hoifung Poon, and COPPE Gerson Zaverucha.  Neural-symbolic learning and reasoning: A survey and interpretation.  _Neuro-Symbolic Artificial Intelligence: The State of the Art_ , 342(1):327, 2022.  URL https://arxiv.org/pdf/1711.03902.pdf.
  * Gordon et al. [2019] Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt.  Permutation equivariant models for compositional generalization in language.  In _International Conference on Learning Representations_ , 2019.
  * Gupta et al. [2021] Ankit Gupta, Guy Dar, Shaya Goodman, David Ciprut, and Jonathan Berant.  Memory-efficient transformers via top-k attention.  In _Proceedings of the Second Workshop on Simple and Efficient Natural Language Processing_ , pages 39–52. Association for Computational Linguistics, 2021.  doi: 10.18653/v1/2021.sustainlp-1.5.  URL https://aclanthology.org/2021.sustainlp-1.5.
  * Hupkes et al. [2020] Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni.  Compositionality decomposed: how do neural networks generalise?  _Journal of Artificial Intelligence Research_ , 67:757–795, 2020.
  * Jarvis et al. [2023] Devon Jarvis, Richard Klein, Benjamin Rosman, and Andrew M Saxe.  On the specialization of neural modules.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=Fh97BDaR6I.
  * Keysers et al. [2019] Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al.  Measuring compositional generalization: A comprehensive method on realistic data.  In _International Conference on Learning Representations_ , 2019.
  * Kim and Linzen [2020] Najoung Kim and Tal Linzen.  COGS: A compositional generalization challenge based on semantic interpretation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9087–9105, 2020.
  * Klinger et al. [2020] Tim Klinger, Dhaval Adjodah, Vincent Marois, Josh Joseph, Matthew Riemer, Alex ’Sandy’ Pentland, and Murray Campbell.  A study of compositional generalization in neural models, 2020.
  * Lake and Baroni [2018] Brenden Lake and Marco Baroni.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _International Conference on Machine Learning_ , pages 2873–2882. PMLR, 2018.
  * Li et al. [2019] Yuanpeng Li, Liang Zhao, Jianyu Wang, and Joel Hestness.  Compositional generalization for primitive substitutions.  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 4284–4293, 2019.
  * Lin et al. [2022] Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu.  A survey of transformers.  _AI Open_ , 2022.  URL https://www.sciencedirect.com/science/article/pii/S2666651022000146.
  * Liu et al. [2021] Chenyao Liu, Shengnan An, Zeqi Lin, Qian Liu, Bei Chen, Jian-Guang Lou, Lijie Wen, Nanning Zheng, and Dongmei Zhang.  Learning algebraic recombination for compositional generalization.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 1129–1144, 2021.
  * Liu et al. [2020] Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang.  Compositional generalization by learning analytical expressions.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Nye et al. [2020] Maxwell Nye, Armando Solar-Lezama, Josh Tenenbaum, and Brenden M Lake.  Learning compositional rules via neural program synthesis.  _Advances in Neural Information Processing Systems_ , 33:10832–10842, 2020.
  * Ontanon et al. [2022] Santiago Ontanon, Joshua Ainslie, Zachary Fisher, and Vaclav Cvicek.  Making transformers solve compositional tasks.  In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 3591–3607, Dublin, Ireland, May 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.acl-long.251.  URL https://aclanthology.org/2022.acl-long.251.
  * Pagin and Westerståhl [2010a] Peter Pagin and Dag Westerståhl.  Compositionality I: Definitions and variants.  _Philosophy Compass_ , 5(3):250–264, 2010a.
  * Pagin and Westerståhl [2010b] Peter Pagin and Dag Westerståhl.  Compositionality II: Arguments and problems.  _Philosophy Compass_ , 5(3):265–282, 2010b.
  * Partee [1995] Barbara Partee.  Lexical semantics and compositionality.  _An invitation to cognitive science. Part I: Language_ , 1:311–360, 1995.  URL https://www.cs.brandeis.edu/~jamesp/classes/cs216-2009/readings2009/ParteeSemanticsAndCompositionality.pdf.
  * Ram et al. [2023] Parikshit Ram, Tim Klinger, and Alexander G. Gray.  How compositional is a model?  In _International Joint Conference on Artificial Intelligence 2023 Workshop on Knowledge-Based Compositional Generalization_ , 2023.  URL https://openreview.net/forum?id=OImyRhNLv3.
  * Rosenbaum et al. [2019] Clemens Rosenbaum, Ignacio Cases, Matthew Riemer, and Tim Klinger.  Routing networks and the challenges of modular and compositional computation.  _arXiv preprint arXiv:1904.12774_ , 2019.  URL https://arxiv.org/pdf/1904.12774.pdf.
  * Russin et al. [2019] Jake Russin, Jason Jo, Randall C O’Reilly, and Yoshua Bengio.  Compositional generalization in a deep seq2seq model by separating syntax and semantics.  _arXiv preprint arXiv:1904.09708_ , 2019.
  * Sarker et al. [2021] Md Kamruzzaman Sarker, Lu Zhou, Aaron Eberhart, and Pascal Hitzler.  Neuro-symbolic artificial intelligence.  _AI Communications_ , 34(3):197–209, 2021.  URL https://arxiv.org/pdf/2105.05330.pdf.
  * Shaw et al. [2018] Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani.  Self-attention with relative position representations.  In Marilyn Walker, Heng Ji, and Amanda Stent, editors, _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)_ , pages 464–468. Association for Computational Linguistics, 2018.  doi: 10.18653/v1/N18-2074.  URL https://aclanthology.org/N18-2074.
  * Shen et al. [2018] Yikang Shen, Zhouhan Lin, Chin wei Huang, and Aaron Courville.  Neural language modeling by jointly learning syntax and lexicon.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=rkgOLb-0W.
  * Shen et al. [2019] Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville.  Ordered neurons: Integrating tree structures into recurrent neural networks.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=B1l6qiR5F7.
  * Sikarwar et al. [2022] Ankur Sikarwar, Arkil Patel, and Navin Goyal.  When can transformers ground and compose: Insights from compositional generalization benchmarks.  In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 648–669, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.emnlp-main.41.  URL https://aclanthology.org/2022.emnlp-main.41.
  * Socher et al. [2010] Richard Socher, Christopher D Manning, and Andrew Y Ng.  Learning continuous phrase representations and syntactic parsing with recursive neural networks.  In _Proceedings of the NIPS-2010 deep learning and unsupervised feature learning workshop_ , volume 2010, pages 1–9, 2010.
  * Tai et al. [2015] Kai Sheng Tai, Richard Socher, and Christopher D Manning.  Improved semantic representations from tree-structured long short-term memory networks.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1556–1566, 2015.  URL https://arxiv.org/pdf/1503.00075.pdf.
  * Tay et al. [2020] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan.  Sparse sinkhorn attention.  _Proceedings of ICML_ , 2020.  URL http://proceedings.mlr.press/v119/tay20a/tay20a.pdf.
  * Tay et al. [2022] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler.  Efficient transformers: A survey.  _ACM Computing Surveys_ , 55(6), 2022.  ISSN 0360-0300.  URL https://doi.org/10.1145/3530811.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.  URL https://arxiv.org/pdf/1706.03762.pdf.
  * Wiedemer et al. [2023] Thaddäus Wiedemer, Prasanna Mayilvahanan, Matthias Bethge, and Wieland Brendel.  Compositional generalization from first principles.  _arXiv preprint arXiv:2307.05596_ , 2023.  URL https://arxiv.org/pdf/2307.05596.pdf.
  * Zadrozny [1994] Wlodek Zadrozny.  From compositional to systematic semantics.  _Linguistics and philosophy_ , 17:329–342, 1994.  URL https://www.jstor.org/stable/25001552.
  * Zhou et al. [2023] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed H. Chi.  Least-to-most prompting enables complex reasoning in large language models.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=WZH7099tgfM.

##  Appendix A Technical Details for §3

###  A.1 Node ordering at each level of the cDAG

A cDAG $D(X)\triangleq\\{N(X),E(X)\\}$ for a specific input sequence
$X\in\mathcal{X}$ can depend on $X$ or be pre-specified. This cDAG is a
leveled DAG with set of nodes $N(X)$ and edges $E(X)$. Each node
$n\triangleq(l:i)\in N(X)$ has a level $l$ and index $i$ – the level $l$ of
$n$ is one more than the highest level of any of its at most $k$ parents, the
index $i$ of $n$ (at its level) is based on the sort order of the (level,
index) tuples of its parents
$P(n)=\\{n^{\prime}\triangleq(l^{\prime}:i^{\prime})\in N(X):(n^{\prime}\to
n)\in E(X)\\}$ (these tuples themselves are sorted based on their position in
the argument list of $g$). This induces a total ordering at each level.

The cDAG function $D$ provides the argument order in $g$, which is then used
to sort the nodes in the same level. There can be multiple nodes with same set
of parents, but their ordering in the argument list must be different. We do
not need two nodes with the same set of parents and same argument ordering
(which leads to a partial ordering) since we can collapse such nodes into one,
and collect their outgoing edges. Thus, we can always get a total ordering of
the nodes at each level. If the $g$ function is independent of the ordering of
its arguments, then we can just utilize the sorted order of the (level, index)
tuples of the parents to get the total ordering.

###  A.2 Multi-arity of span processors

Our current definition states that the arity of the span processor
$g:\mathcal{H}^{k}\to\mathcal{H}$ is fixed to $k$. We do so for the ease of
exposition, though our definition can incorporate more flexible span
processors.

For example, with a maximum in-degree of $k$ in the cDAG, we can consider a
$g:\mathcal{H}^{k}\to\mathcal{H}$, and pad the input to $g$ for internal nodes
with less than $k$ parents – that is, for a node $n$ with $\tilde{k}<k$
parents $P(n)$ with values
$\\{v_{l_{1}:i_{1}},\ldots,v_{l_{\tilde{k}}:i_{\tilde{k}}}\\}$, the value of
node
$v_{n}=g(v_{l_{1}:i_{1}},\ldots,v_{l_{\tilde{k}}:i_{\tilde{k}}},\text{\tt[PAD]},\ldots,\text{\tt[PAD]})$,
where the padding is of length $(k-\tilde{k})$.

Another possibility is to consider span processors
$g:\cup_{j=2}^{k}\mathcal{H}^{j}\to\mathcal{H}$ that can handle multi-arity
inputs. One example of such a function would be a weighted average over all
the inputs (where the weights depend on the input). The in-degree $k$ of any
node in the cDAG $D(X)$, and thus, the maximum arity of $g$ for the function
$f$ under consideration, drives the length of the span needed to be considered
to process this function. In some general purpose models, we will see that $k$
can be as large at $L$, the length of the input.

###  A.3 Relationship between sensitivity and compositional complexity of a
function

The Definition 2 of the complexity of composition incorporates both the
complexity of the cDAG $D(X)$ and the complexity of the span processor
$g:\mathcal{H}^{k}\to\mathcal{H}$ in terms of its smoothness, with higher
values of $c$ indicating more complex (less smooth) $g$. The absolute LoI
$\delta_{i}$ incorporates the effect of longer paths, with the effect growing
with path length, and corresponds to the sensitivity of the compositional
function output to any one input token in the sequence. This sensitivity can
be formalized as follows:

######  Lemma 1.

Consider a compositional function $f:\mathcal{X}\to\mathcal{Y}$ with
components $e,D,g,h$ (as in Definitions 1 & 2). Let $X=[x_{1},\ldots,x_{L}]$
be an input of length $L$, and
$\tilde{X}^{j}=[\tilde{x}_{1},\ldots,\tilde{x}_{L}]$ be its “perturbation” at
the $j^{\text{th}}$ index, with $x_{i}=\tilde{x}_{i}\forall i\in\llbracket
L\rrbracket,i\not=j$, such that $D(X)=D(\tilde{X}^{j})$. Further, assume that
$\mathcal{Y}=\mathbb{R}$, and let $\gamma>0$ be the Lipschitz constant of
$h:\mathcal{H}^{m}\to\mathbb{R}$. Then the sensitivity of $f$ with respect to
the $j^{\text{th}}$ index is bounded as:

$\left|f(X)-f(\tilde{X}^{j})\right|\leq\gamma\delta_{j}\|e(x_{j},j)-e(\tilde{x}_{j},j)\|.$
(6)

###### Proof.

Let $S$ be the set of sink nodes in $D(X)$. Then $h$ maps the values $v_{n}$
of the sink nodes $n\in S$ to $\mathcal{Y}=\mathbb{R}$. Since
$D(X)=D(\tilde{X}^{j})$, the set of sink nodes in $D(\tilde{X}^{j})$ is also
$S$ but with different values $\tilde{v}_{n},n\in S$.

The perturbed input $\tilde{X}^{j}$ is different from $X$ only at the index
$j$, hence the source node values for $D(X)$ are the same for
$D(\tilde{X}^{j})$. That is, $v_{\text{\tt 0}:i}=\tilde{v}_{\text{\tt 0}:i}$
for all $i\in\llbracket L\rrbracket,i\not=j$.

Consider one sink node $n\in S$ in $D(X)=D(\tilde{X}^{j})$. Their values
$v_{n}$ and $\tilde{v}_{n}$ will be different only if there is a path to $n$
from 0:$j$ (the perturbed source node). Let 0:$j\xrightarrow{\text{path}}a$
denote that there is a path from the source node 0:$j$ to a non-source node
$a$.

Given the smoothness of $h$, we have the following:

$\left|h(v_{n_{1}},\ldots,v_{n_{m}})-h(\tilde{v}_{n_{1}},\ldots,\tilde{v}_{n_{m}})\right|\leq\gamma\sum_{n\in
S}\left\|v_{n}-\tilde{v}_{n}\right\|\mathbb{I}\left(\text{\tt
0}\text{:}j\xrightarrow{\text{path}}n\right).$ (7)

Consider one term corresponding to sink node $n\in S$ in the summation on the
right-hand-side of (7), and utilizing Definition 2, we can say that

$\displaystyle\left\|v_{n}-\tilde{v}_{n}\right\|\mathbb{I}\left(\text{\tt
0}\text{:}j\xrightarrow{\text{path}}n\right)$
$\displaystyle\leq\sum_{n_{1}\in\mathcal{P}(n)}c\left\|v_{n_{1}}-\tilde{v}_{n_{1}}\right\|\mathbb{I}\left(\text{\tt
0}\text{:}j\xrightarrow{\text{path}}n_{1}\right)$ (8)
$\displaystyle\leq\sum_{n_{1}\in\mathcal{P}(n)}c\left(\sum_{n_{2}\in\mathcal{P}(n_{1})}c\left\|v_{n_{2}}-\tilde{v}_{n_{2}}\right\|\mathbb{I}\left(\text{\tt
0}\text{:}j\xrightarrow{\text{path}}n_{2}\right)\right)$ (9)
$\displaystyle\leq\sum_{n_{1}\in\mathcal{P}(n)}c\left(\sum_{n_{2}\in\mathcal{P}(n_{1})}c\left(\cdots
c\left(\sum_{n_{l}\in\mathcal{P}(n_{l-1})}c\left\|v_{n_{l}}-\tilde{v}_{n_{l}}\right\|\mathbb{I}\left(\text{\tt
0}\text{:}j=n_{l}\right)\right)\right)\right),$ (10)

where $v_{a}$ is the value of any node $a$, and $\tilde{v}_{a}$ is the value
of the same node with the perturbed input, $\mathcal{P}(a)$ is the set of
parents of any node $a$. The right-hand-side of (10) is essentially
considering the set $P_{n}(\text{\tt 0}\text{:}j)$ of all paths from source
node 0:$j$ to sink node $n$, and can be re-written as

$\displaystyle\left\|v_{n}-\tilde{v}_{n}\right\|\mathbb{I}\left(\text{\tt
0}\text{:}j\xrightarrow{\text{path}}n\right)$
$\displaystyle\leq\sum_{\text{path }P\in P_{n}(\text{\tt
0}:j)}c^{|P|}\left\|v_{\text{0}:j}-\tilde{v}_{\text{0}:j}\right\|$ (11)
$\displaystyle=\sum_{\text{path }P\in P_{n}(\text{\tt
0}:j)}c^{|P|}\left\|e(x_{j},j)-e(\tilde{x}_{j},j)\right\|.$ (12)

Substituting the above in (7) gives us

$\displaystyle\left|h(v_{n_{1}},\ldots,v_{n_{m}})-h(\tilde{v}_{n_{1}},\ldots,\tilde{v}_{n_{m}})\right|$
$\displaystyle\leq\gamma\sum_{n\in S}\sum_{\text{path }P\in P_{n}(\text{\tt
0}:j)}c^{|P|}\left\|e(x_{j},j)-e(\tilde{x}_{j},j)\right\|$ (13)
$\displaystyle=\gamma\underbrace{\left(\sum_{\text{path }P\in P(\text{\tt
0}\text{:}j)}c^{|P|}\right)}_{\delta_{j}\text{ by
Definition~{}\ref{def:loi}}}\left\|e(x_{j},j)-e(\tilde{x}_{j}\right\|$ (14)
$\displaystyle=\gamma\delta_{j}\left\|e(x_{j},j)-e(\tilde{x}_{j},j)\right\|,$
(15)

where $P(\text{\tt 0}\text{:}j)$ is the set of all paths from the source node
0:$j$ to any sink node $n\in S$, giving us the statement of the lemma. ∎

The sensitivity of compositional functions $f$ in the compositional function
class $\mathcal{F}$ (as defined in Definition 3) to changes in the input can
be characterized as follows with respect to the compositional complexity (as
defined in Definition 2).

######  Corollary 1.

Given a class $\mathcal{F}$ of
$(k,q,m,{\boldsymbol{\delta}},{\boldsymbol{\beta}})$-compositional functions
as in Definition 3, and the conditions and notations of Lemma 1, $\forall
f\in\mathcal{F}$ and any $X\in\mathcal{X}$ of length $L$, $\exists C>0$
(universal constant) such that

$\max_{j\in\llbracket L\rrbracket}\left|f(X)-f(\tilde{X}^{j})\right|\leq
C\gamma{\boldsymbol{\delta}}.$ (16)

###### Proof.

Let $C=\max\limits_{\begin{subarray}{c}x,x^{\prime}\in\mathcal{I},\\\
i\in\llbracket L\rrbracket\end{subarray}}\|e(x,i)-e(x^{\prime},i)\|$. Then for
any $X,\tilde{X}^{j}\in\mathcal{X}$, by Lemma 1 and Definition 3, we know that

$\displaystyle\left|f(X)-f(\tilde{X}^{j})\right|$
$\displaystyle\leq\gamma{\boldsymbol{\delta}}\|e(x_{j},j)-e(\tilde{x}_{j},j)\|$
(17) $\displaystyle\leq\gamma{\boldsymbol{\delta}}C,$ (18)

giving us the statement of the corollary. ∎

##  Appendix B Details for §4

0:10:2conv(12)0:3conv(23)pool(123)1:10:4conv(34)0:5conv(45)pool(345)1:2conv(12)pool(123)2:10:6conv(56)0:7conv(67)pool(567)1:3conv(23)
(a) Convolution + Pooling (Detailed version of figure 4(a)): Convolution over
a window of size 2 (no padding), and pooling over a window of size 2.

0:10:21:10:30:41:22:10:50:61:30:7 (b) Conv+Pool (same as Figure 4(a)

0:10:2conv(12)0:3conv(23)pool(123)1:10:4conv(34)0:5conv(45)pool(345)1:2conv(12)pool(123)2:10:6conv(56)0:7conv(67)pool(567)1:3conv(23)
(c) Conv+Pool: Detailed version of selective pooling with Figure 5(a).

0:10:21:10:30:41:22:10:50:61:30:7 (d) Fig 5(c) condensed

0:1conv(*1)0:2conv(12)0:3conv(23)pool(
123)1:1conv(*1)0:4conv(34)0:5conv(45)pool(3456)1:2conv(12)pool(123)2:10:6conv(56)0:7conv(67)pool(
67)1:3conv(23) (e) Convolution + Pooling (Detailed version): Convolution over
a window of size 2 (with padding), and pooling over a window of size 3.

0:10:21:10:30:41:22:10:50:61:30:7 (f) Condensed version of Figure 5(a)

Figure 5: Existing models - Extra details

###  B.1 Proof of Proposition 1

######  Proposition 8.

With unidirectional recurrent composition, the maximum absolute LoI is
${\boldsymbol{\delta}}\triangleq c^{L-1}$, with a maximum relative LoI of
${\boldsymbol{\beta}}\triangleq(c^{L}-c^{L-1})/(2c^{L}-c^{L-1}-1)$.

###### Proof.

Both source nodes 0:$1$ and 0:$2$ have a single path to the single sink node
with path length $L-1$. Thus $\delta_{1}=\delta_{2}=c^{L-1}$. All source nodes
0:$i$, $i\in[3,L]$, have a single path to the single single node with a path
length of $L-i+1$. Thus $\sum_{i\in\llbracket
L\rrbracket}\delta_{i}=(2c^{L}-c^{L-1}-1)/(c-1)$.

Thus, ${\boldsymbol{\delta}}=\delta_{1}=\delta_{2}=c^{L-1}$, with
${\boldsymbol{\beta}}={\boldsymbol{\delta}}/\sum_{i\in\llbracket
L\rrbracket}\delta_{i}=(c^{L}-c^{L-1})/(2c^{L}-c^{L-1}-1)$. ∎

###  B.2 Proof of Proposition 2

######  Proposition 9.

With bidirectional recurrent composition, the maximum absolute LoI is
${\boldsymbol{\delta}}\triangleq c^{L-1}+c$, with a maximum relative LoI of
${\boldsymbol{\beta}}\triangleq(c^{L}-c^{L-1}+c^{2}-c)/2(2c^{L}-c^{L-1}-1)$.

###### Proof.

Source node 0:$1$ has two paths to each of two sink nodes, with path lengths
$L-1$ and $1$, which source node 0:$L$ has two paths of lenghts $1$ and $L-1$.
Thus $\delta_{1}=\delta_{L}=c^{L-1}+c$. All source nodes 0:$l$, $l\in[2,L]$,
have two paths to the two sink nodes with paths of lengths of $L-l+1$ and $l$.
Thus $\sum_{i\in\llbracket L\rrbracket}\delta_{i}=2(2c^{L}-c^{L-1}-1)/(c-1)$.

Thus,
${\boldsymbol{\delta}}=\delta_{1}=\delta_{2}=\delta_{L-1}=\delta_{L}=c^{L-1}+c$,
with ${\boldsymbol{\beta}}={\boldsymbol{\delta}}/\sum_{i\in\llbracket
L\rrbracket}\delta_{i}=(c^{L}-c^{L-1}+c^{2}-c)/2(2c^{L}-c^{L-1}-1)$. ∎

###  B.3 Proof of Proposition 3

######  Proposition 10.

With balanced binary-tree recurrent composition, and $L=2^{l}$ for some
positive integer $l$, the maximum absolute LoI is
${\boldsymbol{\delta}}\triangleq c^{\log_{2}L}$, with a maximum relative LoI
of ${\boldsymbol{\beta}}\triangleq 1/L$.

###### Proof.

All source nodes 0:$i$, $i\in\llbracket L\rrbracket$, have a single path to
the single sink node with path length $\log_{2}L$. Thus
${\boldsymbol{\delta}}\triangleq c^{\log_{2}L}$, and $\sum_{i\in\llbracket
L\rrbracket}\delta_{i}=Lc^{\log_{2}L}$, and ${\boldsymbol{\beta}}=1/L$. ∎

###  B.4 Proof of Proposition 4

######  Proposition 11.

Assuming $1<w,p\ll L$, the conv+pool composition has a maximum absolute LoI of
${\boldsymbol{\delta}}\sim\mathcal{O}(c^{\log L})$, and a maximum relative LoI
of ${\boldsymbol{\beta}}\sim\mathcal{O}(\nicefrac{{2}}{{L(1+1/p)}})$.

###### Proof.

We operate under the assumption that convolution does not reduce the length of
the sequence (usually it does not increase, but it can reduce in case there is
no padding at the ends of the sequence), and that pooling reduces the length
of the input sequence. Pooling over a window of size $p$ reduces a sequence of
length $L$ to $L/p$. This reduction in length corresponds to the number of
nodes in the cDAG at each level. At level 0, there are $L$ source nodes, and
after the conv+pool operation, there would be $L/p$ nodes at the level 1. If
the user specified number of sink nodes is $m$, then, the maximum length of a
source node to sink path would be $\log(L/m)/\log p\sim O(\log L)$.

We consider two cases: (i) $w>p$, (ii) $p<w$.

In case (i), $w>p$, so each node can be the parent of $(1+w/p)$ nodes in the
next level, thereby each source node can have at most
$\mathcal{O}((1+w/p)^{\log L})$ paths to a sink nodes. Thus
${\boldsymbol{\delta}}\sim\mathcal{O}((1+w/p)^{\log L}c^{\log L})\sim
O(c^{\log L})$, while ${\boldsymbol{\beta}}$ is close to $1/L$.

In case (ii), $p>w$, so only $L/p$ nodes can have $>1$ paths to any sink
nodes; the rest of the source nodes will have a single path to any sink node.
In this case, ${\boldsymbol{\delta}}$ is at most $2Cc^{\log L}$ for some
constant $C$, and $\beta_{i}$ for any such node is given by

$\beta_{i}=\frac{2Cc^{\log L}}{(2L/p+(L-L/p))Cc^{\log L}}=\frac{2}{L(1-1/p)}.$
(19)

Putting case (i) and (ii) together, we get
${\boldsymbol{\delta}}\sim\mathcal{O}(c^{\log L})$ and
${\boldsymbol{\beta}}=2/(L(1+1/p))$. ∎

###  B.5 Transformer block based span processor

For a node $l+1$:$i$, the value is given by

$v_{l+1:i}\leftarrow g(v_{l:i},v_{l:1},\ldots,v_{l:L})=\text{\sf
LN}(\tilde{v}_{l:i}+W_{2}^{l}\cdot\text{\sf ReLU}(W_{1}^{l}\tilde{v}_{l:i})),$

and

$\tilde{v}_{l:i}\leftarrow\text{\sf LN}(v_{l:i}+\sum_{h\in\llbracket
H\rrbracket}W_{h}^{l}\sum_{j\in\llbracket
L\rrbracket}a(v_{l:i}Q_{h}^{l},v_{l:j}K_{h}^{l})V^{l}_{h}v_{l:i}).$

Here $\text{\sf LN}(\cdot)$ is layer-normalization, $a(\cdot,\cdot)$ is the
normalized attention weight, $W_{h}^{l},Q_{h}^{l},K_{h}^{l},V_{h}^{l}$ are the
per-attention-head weights at level $l$.

###  B.6 Proof of Proposition 5

######  Proposition 12.

A transformer based composition with $M$ blocks has a the maximum absolute LoI
of ${\boldsymbol{\delta}}={L}^{M+1}c^{M+1}$, and a maximum relative LoI of
${\boldsymbol{\beta}}=1/L$.

###### Proof.

All source nodes 0:$i$, $i\in\llbracket L\rrbracket$, have a $L^{M}$ paths to
the $j$-th node $M$:$j$, $j\in\llbracket L\rrbracket$ at the $M$-th level, and
each node in the $M$-th level has a single path to the sink node.

This gives a total number of paths of $L\times L^{M}=L^{M+1}$. Each path is
exactly of length $M+1$.

Thus ${\boldsymbol{\delta}}\triangleq L^{M+1}c^{M+1}$, and
$\sum_{i\in\llbracket L\rrbracket}\delta_{i}=L^{M+2}c^{M+1}$, and
${\boldsymbol{\beta}}=1/L$. ∎

###  B.7 Proof of Proposition 6

######  Proposition 13.

A transformer with $M$ blocks and $K$-sparse attention ($K\ll L$) has a
maximum absolute LoI of ${\boldsymbol{\delta}}=LK^{M}c^{M+1}$, and a maximum
relative LoI of ${\boldsymbol{\beta}}=1/K$.

###### Proof.

In the presence of sparse or hard attention, there are exactly $L(K+1)$ edges
between nodes of two consecutive levels. The maximal number of paths for any
source node 0:$i^{\star}$ is in the scenario where, at each level $l$, there
is a set of exactly $K$ nodes, $\mu_{l}$, which are in the top-$K$ for all
nodes in level $l+1$, and the source node 0:$i^{\star}$ is the parent of all
the nodes in $\mu_{1}$. Note that, for any $b$ consecutive levels
$l,l+1,\ldots,l+b$, $\mu_{l},\mu_{l+1},\ldots,\mu_{b}$ are effectively a $b$
fully connected layers.

Let $\mu_{0}$ be the set of source nodes which are in the top-$K$ of all nodes
in level 1. In this scenario, the number of paths from a source node
0:$i^{\star}\in\mu_{0}$ to the sink node involving only the nodes in the
$\mu_{l},l\in\llbracket M\rrbracket$ is $K^{M}\times K$, where the $M$
effectively fully connected layers produce the $K^{M}$ paths from
0:$i^{\star}$ to any node in $\mu_{M}$, and every node in $\mu_{M}$ connects
to the sink node, giving the $K$ term.

For the paths from a source node 0:$i^{\star}$ in $\mu_{0}$ through the set of
nodes $\bar{\mu}_{l}$ that are not in $\mu_{l}$ at level $l$, the number of
paths is as follows:

  * •

The number of paths from 0:$i^{\star}$ to a node in $\bar{\mu}_{1}$ is 1.

  * •

The number of paths from 0:$i^{\star}$ to a node in $\bar{\mu}_{2}$ is $K+1$,
where $K$ paths are through the nodes in $\mu_{1}$, and the 1 additional path
is through the node in $\bar{\mu}_{1}$.

  * •

The number of paths from 0:$i^{\star}$ to a node in $\bar{\mu}_{3}$ is
$K^{2}+K+1$, where $K^{2}$ paths are through the nodes in $\mu_{1}$ and
$\mu_{2}$, and the $K+1$ additional path is through the node in
$\bar{\mu}_{2}$.

  * •

By induction, we can show that the number of paths from 0:$i^{\star}$ to a
node in $\bar{\mu}_{l}$ is
$\sum_{j=1}^{l}K^{j-1}=\nicefrac{{(K^{l}-1)}}{{(K-1)}}$.

Thus, 0:$i^{\star}$ has $\nicefrac{{(K^{M}-1)}}{{(K-1)}}$ paths to a node in
$\bar{\mu}_{M}$, and there are $(L-K)$ nodes in $\bar{\mu}_{M}$, giving
$(L-K)\nicefrac{{(K^{M}-1)}}{{(K-1)}}$ paths involving nodes not in
$\mu_{l},l\in\llbracket M\rrbracket$.

This gives us a total number of paths

$K\cdot K^{M}+(L-K)\cdot\frac{K^{M}-1}{K-1}\leq LK^{M},$

thus, leading to a ${\boldsymbol{\delta}}=LK^{M}c^{M+1}$ since each of the
paths are of length exactly $M+1$.

This scenario also produces the maximal $\beta_{i^{\star}}$. The $K$ source
nodes in $\mu_{0}$ all have a $\delta_{i}=LK^{M}c^{M+1}$. All other source
nodes have $\mathcal{O}(1)$ paths to the sink node. In this case,

$\beta_{i^{\star}}=\frac{\delta_{i^{\star}}}{\sum_{i\in\llbracket
L\rrbracket}\delta_{i}}\leq\frac{\delta_{i^{\star}}}{\sum_{i\in\mu_{0}}\delta_{i}}=1/K={\boldsymbol{\beta}},$
(20)

thus giving us the maximal relative LoI. ∎

###  B.8 Proof of Proposition 7

######  Proposition 14.

For a decoder-only transformer based composition with an input length $L$ and
$M$ levels, the maximum absolute LoI is $\max_{i\in\llbracket
L\rrbracket}\delta_{i}=\delta_{1}\triangleq{\boldsymbol{\delta}}\sim\mathcal{O}(L^{M}c^{M+1})$,
and a maximum relative LoI of
${\boldsymbol{\beta}}\sim\mathcal{O}\left(L^{M}/\sum_{i\in\llbracket
L\rrbracket}i^{M}\right)\sim\mathcal{O}\left(1/\left(1+\sum_{i\in\llbracket
L-1\rrbracket}(i/L)^{M}\right)\right)$.

###### Proof.

Given the structure of the decoder-only transformer, the source node 0:1 has
the largest number of paths to the sink node. We will count those paths as
follows:

  * •

For any node 1:$l$, $l\in\llbracket L\rrbracket$ at level 1, the number of
paths from 0:1 to it is exactly 1.

  * •

For any node 2:$l$, $l\in\llbracket L\rrbracket$ at level 2, the number of
paths from 0:1 to it is 1 (through 1:$l$) in addition to the number of paths
from 0:1 to a node 1:$j$ at level 1 for all $j<l$. From above, we know that
there is only 1 path from 0:1$\to$1:$j$ for any $j$. Thus, there are exactly
$l$ paths from 0:1$\to$2:$l$.

  * •

For any node 3:$l$, $l\in\llbracket L\rrbracket$ at level 3, the number of
paths from 0:1 to it is $l$ (through 2:$l$) in addition to the number of paths
from 0:1$\to$2:$j$ at level 2 for all $j<l$. From above, we know that there
will be $j$ paths from 0:1$\to$2:$j$ for any $j$. Thus, there are exactly
$\sum_{j\in\llbracket l\rrbracket}j=l(l+1)/2$ paths from 0:1$\to$3:$l$.

  * •

For any node 4:$l$, $l\in\llbracket L\rrbracket$ at level 4, the number of
paths from 0:1 to it is $l(l+1)/2$ (through 3:$l$) in addition to the number
of paths from 0:1$\to$3:$j$ at level 3 for all $j<l$. From above, we know that
there will be $j(j+1)/2$ paths from 0:1$\to$3:$j$ for any $j$. Thus, there are
exactly $\nicefrac{{1}}{{2}}\sum_{j\in\llbracket l\rrbracket}j(j+1)$ paths
from 0:1$\to$3:$l$. Now $\sum_{j\in\llbracket
l\rrbracket}j(j+1)\sim\mathcal{O}(\sum_{j\in\llbracket
l\rrbracket}j^{2})\sim\mathcal{O}(l^{3})$.

  * •

Continuing through this via induction, for any node $t$:$l$, $l\in\llbracket
L\rrbracket$ at level $t\leq M$, the number of paths from 0:1 to it is
$\mathcal{O}(l^{t-2})$ (through $(t-1)$:$l$) in addition to the number of
paths from 0:1$\to$ $(t-1)$:$j$ at level $(t-1)$ for all $j<l$. From above, we
know that there will be $\mathcal{O}(j^{t-2})$ paths from 0:1$\to$ $(t-1)$:$j$
for any $j$. Thus, there will be $\mathcal{O}\left(\sum_{j\in\llbracket
l\rrbracket}j^{t-2}\right)\sim\mathcal{O}(l^{t-1})$ paths from 0:1$\to$
$t$:$l$.

  * •

Finally, following this induction, the number of paths from 0:1$\to$ $M$:$l$
for $l\in\llbracket L\rrbracket$ at the final $M$ level (after the $M$-th
transformer block) will be $\mathcal{O}(l^{M-1})$.

Now summing the paths from 0:1 across all nodes $M$:$l$ at the $M$-th level,
we get a total number of paths of $\mathcal{O}\left(\sum_{l\in\llbracket
L\rrbracket}l^{M-1}\right)\sim\mathcal{O}(L^{M})$.

Each of these paths will be of length exactly $M+1$. Thus, the maximum LoI
${\boldsymbol{\delta}}\sim\mathcal{O}(L^{M}c^{M+1})$.

Using the same process as above, we can show that the absolute LoI
$\delta_{i}$ of the $i$-th source node 0:$i$ for $i\in\llbracket L\rrbracket$
will be given as $\delta_{i}\sim\mathcal{O}((L-i+1)^{M})$. Thus

$\sum_{i\in\llbracket
L\rrbracket}\delta_{i}\sim\mathcal{O}\left(\sum_{i\in\llbracket
L\rrbracket}(L-i+1)^{M}\right)\sim\mathcal{O}\left(\sum_{i\in\llbracket
L\rrbracket}i^{M}\right).$ (21)

Substituting this into the definition of ${\boldsymbol{\beta}}$ gives us the
order of magnitude of ${\boldsymbol{\beta}}$ in the statement of the
proposition. ∎

###  B.9 Operating on arbitrary length sequences (and how that relates to
parameter sharing).

For the models we have discussed (Table 2, ignoring the no-hierarchical
compositional model), the recurrent composition, the conv+pool composition,
and the transformer-based composition can operate on arbitrary length input
sequences, although the quadratic computation complexity (in the input
sequence length $L$) often requires the model to put limits on the input
sequence length for practical purposes. The multi-layered compositional models
require the maximum sequence length to be specified beforehand, and the models
will not operate on sequences of larger length – the maximum length can be set
a large value and suffice for all practical purposes, but of course this
results in models with large number of parameters. For the recurrent and
conv+pool compositions, the maximum number of levels in the cDAG is
proportional to the length $L$ of the input sequence. In this case,
effectively the span processor $g$ is shared across all levels $l$ of the cDAG
– we are sharing parameters across all levels of the cDAG. This sharing can
enable the ability to successfully operate on arbitrarily long sequences – if
a length was not previously encountered (say, during learning), the
corresponding higher levels of the cDAG were not encountered either, but the
model just applies the $g$ to all the levels and hence is operable. As
previously discussed, the span processor $g$ can be made level dependent by
including the level information of the parent nodes in the cDAG in the latent
representation of any internal node either explicitly (for example, by
appending the levels of the parents to the representation and defining
$g:(\mathcal{H}\times\mathbb{N})^{k}\to\mathcal{H}$ instead of the current
$g:\mathcal{H}^{k}\to\mathcal{H}$) or implicitly (as is done in various
recurrent models). For compositions with a pre-specified number of levels,
such as in the multi-layered fully-connected or the transformer-based
compositions, the maximum number of levels $M$ in the cDAG are not directly
related to the length $L$ of the sequence (and often is a hyperparameter). In
this case, usually the span processor $g$ is level-dependent, explicitly being
different span processor $g_{l},l\in\llbracket M\rrbracket$. We can still
incorporate it in our definition which makes use of a single span processor
$g$ by defining $g$ as a dictionary of functions
$g=\\{1:g_{1},2:g_{2},\cdots,M:g_{M}\\}$, and the level $l$ of a node $l$:$i$
being used to select the appropriate span processor $g[l]$. From the
perspective of expressiveness, it might be beneficial to have distinct span
processors for each level. However, this can be challenging during learning,
and it makes sense to utilize weight-sharing across the levels as in the
universal transformer Dehghani et al. [2019]. In fact, Csordás et al. 2021
highlight the ability of the universal transformer to compositionally
generalize better than the general transformer because of this weight sharing.

Table 2: Existing models in the context of Definition 3. The LoI are specified
approximately for the ease of exposition.

Model |  Input-dependent cDAG | Arbitrary length | $(k,q,m)$ | ${\boldsymbol{\delta}}$ | ${\boldsymbol{\beta}}$
---|---|---|---|---|---
No-hierarchy (3(a)) | ✗ | ✗ | $(1,1,L)$ | $c$ | $1/L$
Unidirectional recurrence (3(b)) | ✗ | ✓ | $(2,1,1)$ | $c^{L-1}$ | $1/2$
Bidirectional recurrence (3(c)) | ✗ | ✓ | $(2,2,2)$ | $c^{L-1}$ | $1/4$
Tree recurrence (3(d)) | $\blacklozenge$ | ✓ | $(2,1,1)$ | $c^{\log L}$ | $1/L$
Convolution then pooling (4(a)) | ${\dagger}$ | ${\ddagger}$ | $(\text{$w$+$p$},w,m)$ | $c^{\log L}$ | $\frac{2}{L(1+\frac{1}{p})}$
Transformer (4(b)) | ✗ | ✓ | $(L,L,1)$ | $L^{M+1}c^{M+1}$ | $1/L$
Transformer + sparse attention (4(c)) | ✓ | ✓ | $(K,L,1)$ | $LK^{M}c^{M+1}$ | $1/K$
Decoder-only transformer (4(d)) | ✗ | ✓ | $(L,L,1)$ | $L^{M}c^{M+1}$ | $\nicefrac{{1}}{{(1+r\Delta)}}^{\bullet}$

$\blacklozenge$ The cDAG can be input-dependent if a parse tree for the input
is available for the problem.
$\blacksquare$ The cDAG can be input-dependent if some form of hard gating or
attention is used in the memory access and update.
${\dagger}$ Conv+Pool induces input-dependent cDAGs for max/min-pool, but not
for avg/sum-pool.
${\ddagger}$ The number of sink nodes $m$ needs to be specified for conv+pool,
and the model can handle arbitrary length if it is allowed to recursively
conv+pool until the number of nodes is reduced to $m$.
$\bullet$ See discussion after Proposition 7.

##  Appendix C Technical Details for Theorem 1

######  Theorem 3.

Consider a $(k,q,m,{\boldsymbol{\delta}},{\boldsymbol{\beta}})$-compositional
function class $\mathcal{F}$, and input sequences $X\in\mathcal{X}$ of length
$L$. Consider a ground-truth function $f\in\mathcal{F}$ with components
$e,D,g,h$, and a compositional function $\mathsf{f}\in\mathcal{F}$ with
components $e,\mathsf{D},\mathsf{g},\mathsf{h}$, with an input-agnostic cDAG
such that $\mathsf{D}(X)=\mathsf{D}\,\forall X\in\mathcal{X},|X|=L$. 666We are
assuming that the token encoder $e$ is same for both $f,\mathsf{f}$. We
further assume that, given any input-agnostic cDAG $\mathsf{D}$ and any
$\mathsf{g},\mathsf{h}$, $\exists X\in\mathcal{X}$ and $D,g,h$, such that (A1)
$D(X)\not=\mathsf{D}$, but is isomorphic to it, (A2)
$h(g^{\otimes\mathsf{D}}(X))=\mathsf{h}(\mathsf{g}^{\otimes\mathsf{D}}(X))$,
and (A3)
$|f(X)-f(\tilde{X}^{i^{\star}})|=\kappa\delta_{i^{\star}}\|e_{i^{\star}}-\tilde{e}_{i^{\star}}\|$,
where $i^{\star}=\arg\max_{i\in\llbracket L\rrbracket}\beta_{i}$ for
$f:={e,D,g,h}$, $\tilde{X}^{i^{\star}}$ is the perturbation of $X$ at the
$i^{\star}$-th index, and $e_{i^{\star}}=e(x_{i^{\star}},i^{\star})$,
$\tilde{e}_{i^{\star}}=e(\tilde{x}_{i^{\star}},i^{\star})$. Then the worst-
case approximation of $f$ by $\mathsf{f}$, for $f,\mathsf{f}\in\mathcal{F}$ is
given by:

$C_{l}{\boldsymbol{\delta}}\leq\max_{\begin{subarray}{c}D,g,h,\\\
f:=\\{e,D,g,h\\},\\\ f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D},\mathsf{g},\mathsf{h},\\\
\mathsf{f}:=\\{e,\mathsf{D},\mathsf{g},\mathsf{h}\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|f(X)-\mathsf{f}(X)\right|\leq
C_{u}\frac{{\boldsymbol{\delta}}}{{\boldsymbol{\beta}}},$

where $f(X)=h(g^{\otimes D(X)}(e(x_{1}),\ldots,e(x_{L}))$, and
$\mathsf{f}(X)=\mathsf{h}(\mathsf{g}^{\otimes\mathsf{D}}(e(x_{1}),\ldots,e(x_{L}))$,
with general smoothness and structural assumptions, and universal constants
$C_{l},C_{u}>0$.

###### Proof.

Focusing on the upper bound, we can that

$\displaystyle\max_{\begin{subarray}{c}D,g,h,\\\ f:=\\{e,D,g,h\\},\\\
f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D},\mathsf{g},\mathsf{h},\\\
\mathsf{f}:=\\{e,\mathsf{D},\mathsf{g},\mathsf{h}\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|f(X)-\mathsf{f}(X)\right|$ (22)
$\displaystyle=\max_{\begin{subarray}{c}D,g,h,\\\ f:=\\{e,D,g,h\\},\\\
f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D},\mathsf{g},\mathsf{h},\\\
\mathsf{f}:=\\{e,\mathsf{D},\mathsf{g},\mathsf{h}\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|h(g^{\otimes
D(X)}(e(x_{1},1),\ldots,e(x_{L},L))-\mathsf{h}(\mathsf{g}^{\otimes\mathsf{D}}(e(x_{1},1),\ldots,e(x_{L},L))\right|$
(23) $\displaystyle\leq\max_{\begin{subarray}{c}D,g,h,\\\ f:=\\{e,D,g,h\\},\\\
f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D}\\\
\mathsf{f}:=\\{e,\mathsf{D},g,h\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|h(g^{\otimes
D(X)}(e(x_{1},1),\ldots,e(x_{L},L))-h(g^{\otimes\mathsf{D}}(e(x_{1},1),\ldots,e(x_{L},L))\right|$
(24)

Now consider the sequence $E=[e_{1},\ldots,e_{L}]$ where $e_{i}=e(x_{i},i)$.
Given that we are maximizing over $D$ and $X$, we can select them such that,
$D(X)$ is isomorphic to $\mathsf{D}$ but $D(X)\not=\mathsf{D}$. This is
possible since both $D(X)$ and $\mathsf{D}$ have the same compositional
complexity.

Now, let us sort the set of source nodes of $\mathsf{D}$ and of $D(X)$ with
respect to their corresponding LoI $\delta_{i}$ to get the sorted indices
$\tilde{S}$ and $S$. Then, consider a reordering
$\tilde{E}=[\tilde{e}_{1},\ldots,\tilde{e}_{L}]$ of the sequence $E$, where
$\forall i\in\llbracket L\rrbracket$, $\tilde{e}_{S[i]}\leftarrow
e_{\tilde{S}[i]}$. Given the selected isomorphic $D(X)$, the following holds:

$h(g^{\otimes
D(X)}(\tilde{e}_{1},\ldots,\tilde{e}_{L}))=h(g^{\otimes\mathsf{D}}(e_{1},\ldots,e_{L})).$
(25)

Then substituting (25) in (24), we have

$\displaystyle\max_{\begin{subarray}{c}D,g,h,\\\ f:=\\{e,D,g,h\\},\\\
f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D},\mathsf{g},\mathsf{h},\\\
\mathsf{f}:=\\{e,\mathsf{D},\mathsf{g},\mathsf{h}\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|f(X)-\mathsf{f}(X)\right|$ (26)
$\displaystyle\leq\max_{\begin{subarray}{c}D,g,h,\\\ f:=\\{e,D,g,h\\},\\\
f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D}\\\
\mathsf{f}:=\\{e,\mathsf{D},g,h\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|h(g^{\otimes
D(X)}(e_{1},\ldots,e_{L})-h(g^{\otimes
D(X)}(\tilde{e}_{1},\ldots,\tilde{e}_{L})\right|$ (27)
$\displaystyle\leq\gamma\sum_{i\in\llbracket
L\rrbracket}\delta_{i}\|e_{i}-\tilde{e}_{i}\|,$ (28)

where the last inequality is an application of Lemma 1.

With $C=\max\limits_{\begin{subarray}{c}x,x^{\prime}\in\mathcal{I}\\\
j\in\llbracket L\rrbracket\end{subarray}}\|e(x,j)-e(x^{\prime},j)\|$, we get
an upper bound of $\gamma C\sum_{i\in\llbracket L\rrbracket}\delta_{i}=\gamma
C{\boldsymbol{\delta}}/{\boldsymbol{\beta}}$, giving us the upper bound in the
statement of the theorem with $C_{u}=\gamma C$.

Focusing on the lower bound, we have the following:

$\displaystyle\max_{\begin{subarray}{c}D,g,h,\\\ f:=\\{e,D,g,h\\},\\\
f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D},\mathsf{g},\mathsf{h},\\\
\mathsf{f}:=\\{e,\mathsf{D},\mathsf{g},\mathsf{h}\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|f(X)-\mathsf{f}(X)\right|$ (29)
$\displaystyle=\max_{\begin{subarray}{c}D,g,h,\\\ f:=\\{e,D,g,h\\},\\\
f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D},\mathsf{g},\mathsf{h},\\\
\mathsf{f}:=\\{e,\mathsf{D},\mathsf{g},\mathsf{h}\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|h(g^{\otimes
D(X)}(e(x_{1},1),\ldots,e(x_{L},L)))-\mathsf{h}(\mathsf{g}^{\otimes\mathsf{D}}(e(x_{1},1),\ldots,e(x_{L},L)))\right|$
(30)

Now, with assumption (A2), we have for any $\mathsf{D},\mathsf{g},\mathsf{h}$

$\displaystyle\left|h(g^{\otimes
D(X)}(e(x_{1},1),\ldots,e(x_{L},L)))-\mathsf{h}(\mathsf{g}^{\otimes\mathsf{D}}(e(x_{1},1),\ldots,e(x_{L},L)))\right|$
(31) $\displaystyle=\left|h(g^{\otimes
D(X)}(e(x_{1},1),\ldots,e(x_{L},L)))-h(g^{\otimes\mathsf{D}}(e(x_{1},1),\ldots,e(x_{L},L)))\right|$
(32) $\displaystyle=\left|h(g^{\otimes
D(X)}(e_{1},\ldots,e_{L}))-h(g^{\otimes\mathsf{D}}(e_{1},\ldots,e_{L}))\right|,$
(33)

where $e_{i}=e(x_{i},i)$. Using (A1), and the technique used for the
upperbound, we can create a reordering
$\tilde{E}=[\tilde{e}_{1},\ldots,\tilde{e}_{L}]$ of the sequence
$E=[e_{1},\ldots,e_{L}]$ such that

$h(g^{\otimes
D(X)}(\tilde{e}_{1},\ldots,\tilde{e}_{L})=h(g^{\otimes\mathsf{D}}(e_{1},\ldots,e_{L})).$
(34)

Substituting above in (33), we have

$\displaystyle\left|h(g^{\otimes
D(X)}(e(x_{1},1),\ldots,e(x_{L},L)))-\mathsf{h}(\mathsf{g}^{\otimes\mathsf{D}}(e(x_{1},1),\ldots,e(x_{L},L)))\right|$
(35) $\displaystyle=\left|h(g^{\otimes D(X)}(e_{1},\ldots,e_{L}))-h(g^{\otimes
D(X)}(\tilde{e}_{1},\ldots,\tilde{e}_{L}))\right|,$ (36)
$\displaystyle\geq\left|h(g^{\otimes
D(X)}(e_{1},\ldots,e_{i^{\star}-1},e_{i^{\star}},e_{i^{\star}+1},\ldots,e_{L}))-h(g^{\otimes
D(X)}(e_{1},\ldots,e_{i^{\star}-1},\tilde{e}_{i^{\star}},e_{i^{\star}+1}\ldots,e_{L}))\right|,$
(37)

where $i^{\star}$ is the index with the highest LoI for $D(X)$, and the last
inequality stems from the fact that we are only perturbing a single index in
(37) instead of all indices as in (36).

Given that the two terms in the right-hand-side of (37) can be written as
$f(X)$ and $f(\tilde{X}^{i^{\star}})$, we can apply assumption (A3) to have

$\max_{\begin{subarray}{c}D,g,h,\\\ f:=\\{e,D,g,h\\},\\\ f\in\mathcal{F},\\\
X\in\mathcal{X}\end{subarray}}\min_{\begin{subarray}{c}\mathsf{D},\mathsf{g},\mathsf{h},\\\
\mathsf{f}:=\\{e,\mathsf{D},\mathsf{g},\mathsf{h}\\},\\\
\mathsf{f}\in\mathcal{F}\end{subarray}}\left|f(X)-\mathsf{f}(X)\right|\geq\eqref{aeq:lb-3}=\max_{X\in\mathcal{X}}\kappa\delta_{i^{\star}}\|e_{i^{\star}}-\tilde{e}_{i^{\star}}\|.$
(38)

With the maximization over $X$, we can select $X$ such that the
$\|e_{i^{\star}}-\tilde{e}_{i^{\star}}\|$ is greater than some universal
constant $C_{1}$. Then, setting $C_{l}$ in the statement of the theorem to
$C_{l}=C_{1}\kappa$ gives us the result since
$\delta_{i^{\star}}={\boldsymbol{\delta}}$. ∎

##  Appendix D Technical Details for Theorem 2

Systematic generalization is often described as being able to “handle unknown
combinations of known parts”. Here, we will specify a data generating function
and data distribution that enables us to study systematic generalization.
Usually, systematic generalization is often empirically evaluated in a setup
where there are cleanly separable parts of the input, and the model is exposed
to the individual parts but not all combinations. For an example, see Hupkes
et al. 2020, §3.1.1. This corresponds to the situation where the maximum
outgoing degree of the cDAG in the ground-truth data-generating function
$f:\mathcal{X}\to\mathcal{Y}$ is one (that is, $q=1$).

For the sake of simplicity of exposition, we will also consider the case where
the maximum incoming degree in the cDAG of $f$ is two (that is, $k=2$), and
there is exactly one sink node (that is, $m=1$). The results we present here
can be generalized to any reasonable $k>2$ and $m>1$ with additional technical
steps. For generalization guarantees, we have to consider a specific output
space $\mathcal{Y}$; here we will study a bounded regression problem and
assume that $\mathcal{Y}=[0,1]\subset\mathbb{R}$ without loss of generality.

Now, we need to precisely define the notion of cleanly-separable parts in any
$X\in\mathcal{X}$ to study systematic generalization.

######  Definition 4 (Parts of the input).

For any input $X=[x_{1},\ldots,x_{L}]\in\mathcal{X}$, we will define two parts
$\mathbf{a}(X)=\\{x_{i_{1}},\ldots,x_{i_{n_{a}}}\\}$ and
$\mathbf{b}(X)=\\{x_{j_{1}},\ldots,x_{j_{n_{b}}}\\}$, where
$i_{n},j_{n^{\prime}}\in\llbracket L\rrbracket\forall n\in\llbracket
n_{a}\rrbracket,\forall n^{\prime}\in\llbracket n_{b}\rrbracket$, and thus
each of the $x_{i_{n}}\in\mathbf{a}(X)$ and $x_{j_{n}}\in\mathbf{b}(X)$ are
tokens in $X$. Let $\mathbf{c}(X)=\\{x_{i},i\in\llbracket
L\rrbracket:x_{i}\notin\mathbf{a}(X)\cup\mathbf{b}(X)\\}$ be the set of
remaining tokens in any input sequence $X$ beyond the parts $\mathbf{a}(X)$
and $\mathbf{b}(X)$ that are necessary to make a valid input sequence
$X\in\mathcal{X}$.

######  Definition 5 (Processing of cleanly-separable parts).

For any input $X\in\mathcal{X}$ with parts
$(\mathbf{a}(X),\mathbf{b}(X),\mathbf{c}(X))$, there exists nodes
$\mathbf{N}_{a},\mathbf{N}_{b}$ and $\mathbf{N}$ in the cDAG $D(X)$ of $X$
such that, the sub-cDAG rooted at $\mathbf{N}_{a}$ and $\mathbf{N}_{b}$ only
contains source nodes corresponding to input tokens in $\mathbf{a}(X)$ and
input tokens in $\mathbf{b}(X)$ respectively, and
$\\{\mathbf{N}_{a},\mathbf{N}_{b}\\}$ forms the parent set of $\mathbf{N}$.

Fig. 6 visualizes some example cDAGs, highlighting the different parts and
corresponding nodes detailed in Definitions 4 and 5. Given that we are
considering the case where the outgoing degree $q=1$ (that is, the maximum
outgoing degree is 1), the above setup implies that there is no overlap
between the sub-parts $\mathbf{a}(X)$ and $\mathbf{b}(X)$ for any input $X$
(that is $\mathbf{a}(X)\cap\mathbf{b}(X)=\emptyset$).

0:11:10:20:3$\mathbf{N}_{a}$(1:2)$\mathbf{N}$(2:1)3:14:10:40:5$\mathbf{N}_{b}$(1:3)0:60:7

0:11:10:2$\mathbf{N}_{a}$(1:2)$\mathbf{N}$(2:1)3:14:10:3$\mathbf{N}_{b}$(1:3)0:41:40:50:60:7

Figure 6: Examples of cDAGs highlighting the notion of cleanly-separable parts
as presented in Definitions 4 and 5. Source nodes corresponding to the part
$\mathbf{a}(X)$ are bordered in Green; source nodes corresponding to the part
$\mathbf{b}(X)$ are bordered in Blue; the remaining source nodes,
corresponding to the remainder $\mathbf{c}(X)$, are bordered in Red. While the
example on the left shows parts $\mathbf{a}(X)=\\{x_{3},x_{4}\\}$ and
$\mathbf{b}(X)=\\{x_{5},x_{6}\\}$ constituting of consecutive input
tokens/source nodes (or a contiguous span of tokens), the example on the right
shows that our definition also allows for parts constituting non-contiguous
input tokens with $\mathbf{a}(X)=\\{x_{2},x_{6}\\}$ and
$\mathbf{b}(X)=\\{x_{3},x_{5}\\}$. In both these cases, $k=2,q=1,m=1$ and the
sequence length $L=7$.

######  Definition 6 (Goal of systematic generalization).

Let $\mathbf{a}(X)\in A$ and $\mathbf{b}(X)\in B$ be elements of types $T_{A}$
and $T_{B}$, where $A$ is the set of all sub-parts $\mathbf{a}(X)$ of any
$X\in\mathcal{X}$ of type $T_{A}$ over all $X\in\mathcal{X}$, and $B$ is the
set of all sub-parts $\mathbf{b}(X)$ of any $X\in\mathcal{X}$ for type $T_{B}$
over all $X\in\mathcal{X}$. To study systematic generalization, we study the
ability of a model trained with inputs containing sub-parts $a\in A$ of type
$T_{A}$ and $b\in B$ of type $T_{B}$ (but not all combinations of $a$ and $b$)
to generalize to all combinations of sub-parts $(a,b)\in A\times B$.

######  Definition 7 (Training set for systematic generalization).

For the training data, we will generating samples
$(X,y),X_{i}\in\mathcal{X},y=f(X)\in[0,1]$, where $f$ is the ground-truth
compositional function with components $(e,D,g,h)$, and the input sequence
$X$, with cleanly-separable parts
$(\mathbf{a}(X),\mathbf{b}(X),\mathbf{c}(X))$ (as in Definitions 4 & 5) is
sampled from a distribution $\mathcal{P}$ (that is, $X\sim\mathcal{P}$). The
training set will constitute $N$ samples
$S=\\{(X_{1},y_{1}),\ldots,(X_{N},y_{N})\\}$.

######  Assumption 1 (Distributional assumption).

We will assume the following structure on the distribution $\mathcal{P}$: With
a large enough training set $S\sim\mathcal{P}^{n}$ of size $n$, for any test
point $X\sim\mathcal{P}$ with parts
$(\mathbf{a}(X),\mathbf{b}(X),\mathbf{c}(X)),\mathbf{a}(X)\in
A,\mathbf{b}(X)\in B$ (as in Definition 4), there exists samples
$(X^{\prime},y^{\prime}),(X^{\prime\prime},y^{\prime\prime}),(X^{\prime\prime\prime},y^{\prime\prime\prime})$
in the training set $S$ such that, (i) $X^{\prime}$ has parts
$(\mathbf{a}(X^{\prime}),\mathbf{b}(X^{\prime}),\mathbf{c}(X^{\prime}))$ with
$\mathbf{a}(X)=\mathbf{a}(X^{\prime})$ and $\mathbf{b}(X^{\prime})\in B$, (ii)
$X^{\prime\prime}$ has parts
$(\mathbf{a}(X^{\prime\prime}),\mathbf{b}(X^{\prime\prime}),\mathbf{c}(X^{\prime\prime}))$
with $\mathbf{b}(X)=\mathbf{b}(X^{\prime\prime})$ and
$\mathbf{a}(X^{\prime\prime})\in A$, and (iii) $X^{\prime\prime\prime}$ has
parts
$(\mathbf{a}(X^{\prime\prime\prime}),\mathbf{b}(X^{\prime\prime\prime}),\mathbf{c}(X^{\prime\prime\prime}))$
with $\mathbf{c}(X^{\prime\prime\prime})=\mathbf{c}(X)$ and
$\mathbf{a}(X^{\prime\prime\prime})\in A,\mathbf{b}(X^{\prime\prime\prime})\in
B$, and the cDAGs $D(X)$ and $D(X^{\prime\prime\prime})$ are the same barring
sub-cDAGs rooted at $\mathbf{N}$ (the child of
$(\mathbf{N}_{a},\mathbf{N}_{b})$) and at $\mathbf{N}^{\prime\prime\prime}$
(the child of
$(\mathbf{N}_{a}^{\prime\prime\prime},\mathbf{N}_{b}^{\prime\prime\prime})$)
respectively; note that we do not require
$\mathbf{a}(X^{\prime\prime\prime})=\mathbf{a}(X)$ or
$\mathbf{b}(X^{\prime\prime\prime})=\mathbf{b}(X)$.

This assumption explicitly states the usual setup for systematic
generalization where we are ensuring that we are evaluating generalization
over known parts – that is, $\mathbf{a}(X)=\mathbf{a}(X^{\prime})$ and
$\mathbf{b}(X)=\mathbf{b}(X^{\prime\prime})$ have been seen in the training
set – and their unknown combination in $X$ – with parts
$(\mathbf{a}(X),\mathbf{b}(X),\mathbf{c}(X))$. The requirement in Assumption 1
on $\mathbf{c}(X)=\mathbf{c}(X^{\prime\prime\prime})$ (the remainder) ensures
that the combination of $\mathbf{c}(X^{\prime\prime\prime})$ with parts
$\mathbf{a}(X^{\prime\prime\prime}),\mathbf{b}(X^{\prime\prime\prime})$ of
types $T_{A},T_{B}$ respectively is seen in the training set. This whole setup
is visualized with the cDAG of an example test input $X$ in Fig. 7, with the
cDAG of $X$ visualized in Fig. 7(a) and the cDAGs of the related training
examples $X^{\prime},X^{\prime\prime},X^{\prime\prime\prime}$ visualized in
Figs. 7(b), 7(c) and 7(d). This assumption can potentially be satisfied with
$n=O(|A|+|B|)$ which is significantly smaller than the total number of unknown
combinations, which is $O(|A|\cdot|B|)$.

0:11:10:20:3$\mathbf{N}_{a}$(1:2)$\mathbf{N}$(2:1)3:14:10:40:5$\mathbf{N}_{b}$(1:3)0:60:7
(a) cDAG $D(X)$ for test example $X\sim\mathcal{P}$.

0:10:2$\mathbf{N}_{a}$(1:1)$\mathbf{N}^{\prime}$(2:1)3:14:10:30:41:20:5$\mathbf{N}_{b}^{\prime}$(1:3)0:60:7
(b) cDAG $D(X^{\prime})$ for training example $X^{\prime}$ with
$\mathbf{a}(X)=\mathbf{a}(X^{\prime})$.

0:11:10:20:3$\mathbf{N}_{a}^{\prime\prime}$(1:2)$\mathbf{N}^{\prime\prime}$(2:1)3:14:10:40:50:6$\mathbf{N}_{b}$(1:3)0:7
(c) cDAG $D(X^{\prime\prime})$ for training ex $X^{\prime\prime}$ with
$\mathbf{b}(X)=\mathbf{b}(X^{\prime\prime})$.

0:11:10:20:3$\mathbf{N}_{a}^{\prime\prime\prime}$(1:2)$\mathbf{N}^{\prime\prime\prime}$(2:1)3:14:10:4$\mathbf{N}_{b}^{\prime\prime\prime}$(1:3)0:50:60:7
(d) cDAG $D(X^{\prime\prime\prime})$ for training ex $X^{\prime\prime\prime}$
with $\mathbf{c}(X)=\mathbf{c}(X^{\prime\prime\prime})$.

Figure 7: Examples of cDAGs as per the distributional Assumption 1. Nodes
corresponding to the part $\mathbf{a}(X)$ and node $\mathbf{N}_{a}$ are in
Green; nodes corresponding to the part $\mathbf{b}(X)$ and node
$\mathbf{N}_{b}$ are in Blue; the remaining nodes, corresponding to the
remainder $\mathbf{c}(X)$, are in Red. The input $X$ has parts
$\mathbf{a}(X)=\\{x_{3},x_{4}\\}$ and $\mathbf{b}(X)=\\{x_{5},x_{6}\\}$, with
the remainder $\mathbf{c}(X)=\\{x_{1},x_{2},x_{7}\\}$. The test input $X$
corresponds to the “unknown combination” of “known parts”, with the known
parts $\mathbf{a}(X)=\mathbf{a}(X^{\prime})$ (Fig. 7(b)),
$\mathbf{b}(X)=\mathbf{b}(X^{\prime\prime})$ (Fig. 7(c)), and
$\mathbf{c}(X)=\mathbf{c}(X^{\prime\prime\prime})$ (Fig. 7(d)) highlighted
with matching colors. In all cases, $k=2,q=1,m=1$ and the sequence length
$L=7$.

######  Definition 8 (Learning setup).

We consider a learning setup where we are provided with the ground-truth token
encoder $e:\mathcal{I}\times\mathbb{N}\to\mathcal{H}\subset\mathbb{R}^{d}$ and
the ground-truth cDAG function $D:\mathcal{X}\to\mathcal{D}$, and the learning
algorithm $\mathcal{A}$ has to the learn a span encoder
$\hat{g}_{S}:\mathcal{H}^{2}\to\mathcal{H}$ and a readout function
$\hat{h}_{S}:\mathcal{H}\to[0,1]$ to give us the model
$\hat{f}_{S}\triangleq(e,D,\hat{g}_{S},\hat{h}_{S})$ using a training set $S$
by minimizing the population risk $R_{N}(\hat{f})=(1/N)\sum_{(X,y)\in
S}\ell(y,\hat{f}(X))$, where $\ell(y,y^{\prime})=|y-y^{\prime}|$ is absolute
loss. Let $\gamma>0$ be the Lipschitz constant of the learned readout function
$\hat{h}_{S}$ for any $S$.

######  Assumption 2 (Low training error).

Under the conditions of the above learning setup (as in Definition 8), we
assume that the learning algorithm $\mathcal{A}$ is able to learn a model
$\hat{f}_{S}$ from the training set $S$ such that, $\forall(X,y)\in
S,\ell(y,\hat{f}(X))\leq\epsilon$, for a small $\epsilon>0$.

As we are making the problem setup more precise, we have made various
simplifications (such as $q=1$, $k=2$, and learning only the span encoder and
readout functions). While these conditions do not capture all learning
scenarios, we would first like to highlight that we have not seen
compositional generalization being studied in a theoretically precise manner
in existing literature, and the precise definition of the setup is itself one
of our contributions. Secondly, even in this simplified setup, we will
highlight from our subsequent result on generalization that our proposed
notion of compositional complexity plays a critical role in generalization
even in this simplified setup. We plan to study more general setups in future
work (such as $k>1$, learning the cDAG function $D$, studying non-cleanly-
separable sub-problems), and we anticipate that the role of the compositional
complexity will become even more acute in those setups.

Now we present our systematic generalization guarantee:

######  Theorem 4.

Consider a
$(k=2,q=1,m=1,{\boldsymbol{\delta}},{\boldsymbol{\beta}})$-compositional
function class $\mathcal{F}$ (Definition 3), and a learning algorithm
$\mathcal{A}$ that obtains a function $\hat{f}_{S}\in\mathcal{F}$ using a
training set $S\sim\mathcal{P}^{N}$ of size $N$ sampled from a distribution
$\mathcal{P}$ with a ground-truth data-generating function
$f:\mathcal{X}\to[0,1]$. Under the conditions of above Definitions 4, 5, 7, 8,
and Assumptions 1, 2, with probability at least $1-(\xi+\xi^{\prime})$ for
some $\xi,\xi^{\prime}\in(0,1)$ with $(\xi+\xi^{\prime})<1$, we can provide
the following systematic generalization guarantee:

$\left|R(\hat{f}_{S})-R_{N}(\hat{f}_{S})\right|\leq
C_{N}\gamma{\boldsymbol{\delta}}+(2NC_{N}\gamma{\boldsymbol{\delta}}+1)\sqrt{\frac{2\log(2/\xi)}{N}},$
(39)

where $R(\hat{f})=\mathbb{E}_{X\sim\mathcal{P}}\ell(f(X),\hat{f}(X))$ is the
true risk of a learning model $\hat{f}$, and $C_{N}$ is a positive quantity
that depends on $N$ and $\xi^{\prime}$.

To prove this result, we will use the following definition of uniform
stability [Bousquet and Elisseeff, 2000, Definition 1] and the related
generalization guarantee [Bousquet and Elisseeff, 2000, Theorem 2], restated
using our notation:

######  Definition 9 (Uniform stability Bousquet and Elisseeff [2000]).

Let
$S=\\{(X_{1},y_{1}),\ldots,(X_{N},y_{N})\\}\sim\mathcal{P}^{n}\subset(\mathcal{X}\times[0,1])^{N}$
be the training set, and
$S^{i}=(S\setminus\\{(X_{i},y_{i})\\})\cup\\{(X_{i}^{\prime},y_{i}^{\prime})\\}$
be the training set where the $i$-th training example in $S$ is replaced with
a different training example
$(X_{i}^{\prime},y_{i}^{\prime})\sim\mathcal{P}\in\mathcal{X}\times[0,1]$ from
the same distribution. Let $\hat{f}_{S}$ be the model obtained by a symmetric
learning algorithm $\mathcal{A}$ using training set $S$, with $f_{S^{i}}$
being the model obtained by algorithm $\mathcal{A}$ on $S^{i}$. We say that
the algorithm $\mathcal{A}$ is $\sigma$-stable if the following holds:

$\forall
S\sim\mathcal{P}^{N}\forall(X_{i}^{\prime},y_{i}^{\prime}),(X,y)\sim\mathcal{P},\forall
i\in\llbracket
N\rrbracket\left|\ell(y,f_{S}(X))-\ell(y,f_{S^{i}}(X))\right|\leq\sigma.$ (40)

######  Theorem 5 (Bousquet and Elisseeff [2000]).

Let $\mathcal{A}$ be a $\sigma$-stable algorithm, such that
$0\leq\ell(y,f_{S}(X))\leq\mathcal{L}$ for all
$(X,y)\sim\mathcal{X}\times[0,1]$ and all training sets $S$. For all
$\varepsilon>0$, for any $N>1$, we have:

$\mathbb{P}_{S\sim\mathcal{P}^{N}}\left[\left|R_{N}(f_{S})-R(f_{S})\right|>\varepsilon+\sigma\right]\leq
2\exp\left(-\frac{N\varepsilon^{2}}{2(N\sigma+\mathcal{L})^{2}}\right).$ (41)

###### Proof of Theorem 4.

We will essentially leverage Theorem 5 by establishing a uniform stability
bound for the learning algorithm $\mathcal{A}$.

For any $(X,y)$, we first have the following inequality

$\displaystyle\ell(y,\hat{f}_{S}(X))$
$\displaystyle=|y-\hat{f}_{S}(X)|=|y-\hat{f}_{S^{i}}(X)+\hat{f}_{S^{i}}(X)-\hat{f}_{S}(X)|$
(42)
$\displaystyle\leq|y-\hat{f}_{S^{i}}(X)|+|\hat{f}_{S^{i}}(X)-\hat{f}_{S}(X)|$
(43)
$\displaystyle=\ell(y,\hat{f}_{S^{i}}(X))+|\hat{f}_{S^{i}}(X)-\hat{f}_{S}(X)|$
(44)
$\displaystyle\Rightarrow\ell(y,\hat{f}_{S}(X))-\ell(y,\hat{f}_{S^{i}}(X))$
$\displaystyle\leq|\hat{f}_{S^{i}}(X)-\hat{f}_{S}(X)|.$ (45)

Similarly, we can show that

$\displaystyle\ell(y,\hat{f}_{S^{i}}(X))$
$\displaystyle\leq\ell(y,\hat{f}_{S}(X))+|\hat{f}_{S}(X)-\hat{f}_{S^{i}}(X)|,$
(46)
$\displaystyle\Rightarrow\ell(y,\hat{f}_{S^{i}}(X))-\ell(y,\hat{f}_{S}(X))$
$\displaystyle\leq|\hat{f}_{S^{i}}(X)-\hat{f}_{S}(X)|.$ (47)

Thus, considering the left-hand-side of (40), we have

$\displaystyle\left|\ell(y,\hat{f}_{S}(X))-\ell(y,\hat{f}_{S^{i}}(X))\right|$
$\displaystyle=\max\left(\left(\ell(y,\hat{f}_{S}(X))-\ell(y,\hat{f}_{S^{i}}(X))\right),\left(\ell(y,\hat{f}_{S^{i}}(X))-\ell(y,\hat{f}_{S}(X))\right)\right)$
(48) $\displaystyle\leq|\hat{f}_{S^{i}}(X)-\hat{f}_{S}(X)|.$ (49)

We know that $\forall
y,y^{\prime}\in[0,1],\ell(y,y^{\prime})=|y-y^{\prime}|\leq 1$, thus
$\mathcal{L}=1$. Now if we can establish universally that
$|\hat{f}_{S^{i}}(X)-\hat{f}_{S}(X)|\leq\sigma$ for some $\sigma$, then we can
use Theorem 5 with $\mathcal{L}=1$ to show that
$|R_{N}(\hat{f}_{S})-R(\hat{f}_{S})|\leq\sigma+\varepsilon$ with probability
at least $1-2\exp(-\nicefrac{{N\varepsilon^{2}}}{{2(N\sigma+1)^{2}}})$.
Setting the failure probability to $\xi\in(0,1)$, we can see that

$\varepsilon\leq(2N\sigma+1)\sqrt{\frac{2\log\nicefrac{{2}}{{\xi}}}{N}},$ (50)

and thus, with probability at least $1-\xi$,

$\left|R_{N}(\hat{f}_{S})-R(\hat{f}_{S})\right|\leq\sigma+(2N\sigma+1)\sqrt{\frac{2\log\nicefrac{{2}}{{\xi}}}{N}}$
(51)

What remains is to provide a bound for $\sigma$.

Now, for any $X$ with parts
$(\mathbf{a}(X),\mathbf{b}(X),\mathbf{c}(X)),\mathbf{a}(X)\in
A,\mathbf{b}(X)\in B$ (as in Definition 4), and $S,S^{i}$ satisfying the
distributional Assumption 1, we have

$\displaystyle|\hat{f}_{S}(X)-\hat{f}_{S^{i}}(X)|$
$\displaystyle=|\hat{f}_{S}(X)-\hat{f}_{S}(X^{\prime\prime\prime})+\hat{f}_{S}(X^{\prime\prime\prime})-\hat{f}_{S^{i}}(X^{\prime\prime\prime})+\hat{f}_{S^{i}}(X^{\prime\prime\prime})-\hat{f}_{S^{i}}(X)|$
(52)
$\displaystyle\leq|\hat{f}_{S}(X)-\hat{f}_{S}(X^{\prime\prime\prime})|+|\hat{f}_{S}(X^{\prime\prime\prime})-\hat{f}_{S^{i}}(X^{\prime\prime\prime})|+|\hat{f}_{S^{i}}(X^{\prime\prime\prime})-\hat{f}_{S^{i}}(X)|,$
(53)

where $(X^{\prime\prime\prime},y^{\prime\prime\prime})$ is the training sample
present both in $S$ and $S^{i}$ (thus, $X^{\prime\prime\prime}\not=X_{i}$) and
$X^{\prime\prime\prime}$ has parts
$(\mathbf{a}(X^{\prime\prime\prime}),\mathbf{b}(X^{\prime\prime\prime}),\mathbf{c}(X^{\prime\prime\prime}))$,
where the remainder $\mathbf{c}(X^{\prime\prime\prime})=\mathbf{c}(X)$, that
is, the remainder part is common between $X$ and $X^{\prime\prime\prime}$.

For the second term on the right-hand side
$|\hat{f}_{S}(X^{\prime\prime\prime})-\hat{f}_{S^{i}}(X^{\prime\prime\prime})|$,
we have

$\displaystyle|\hat{f}_{S}(X^{\prime\prime\prime})-\hat{f}_{S^{i}}(X^{\prime\prime\prime})|$
$\displaystyle=|\hat{f}_{S}(X^{\prime\prime\prime})-y^{\prime\prime\prime}+y^{\prime\prime\prime}-\hat{f}_{S^{i}}(X^{\prime\prime\prime})|$
(54)
$\displaystyle\leq|y^{\prime\prime\prime}-\hat{f}_{S}(X^{\prime\prime\prime})|+|y^{\prime\prime\prime}-\hat{f}_{S^{i}}(X^{\prime\prime\prime})|\leq
2\epsilon,$ (55)

where the last inequality is obtained from Assumption 2 regarding low training
error.

Considering the term $|\hat{f}_{S}(X)-\hat{f}_{S}(X^{\prime\prime\prime})|$,
we know that, as per Definition 5, the cDAG $D(X)$ of $X$ contains nodes
$\mathbf{N}_{a},\mathbf{N}_{b},\mathbf{N}$ where node $\mathbf{N}_{a}$ (and
node $\mathbf{N}_{b}$) is the (respective) sink of the sub-cDAG with source
nodes in $\mathbf{a}(X)$ (and source nodes in $\mathbf{b}(X)$), and
${\mathbf{N}_{a},\mathbf{N}_{b}}$ are the sole parents of $\mathbf{N}$. Such
similar corresponding nodes
$\mathbf{N}_{a}^{\prime\prime\prime},\mathbf{N}_{b}^{\prime\prime\prime},\mathbf{N}^{\prime\prime\prime}$
will exist in the cDAG $D(X^{\prime\prime\prime})$ of
$X^{\prime\prime\prime}$.

Barring the sub-cDAG $\bar{D}_{\mathbf{N}}$ with sink $\mathbf{N}$ in $D(X)$
and the sub-cDAG $\bar{D}_{\mathbf{N}^{\prime\prime\prime}}$ with sink
$\mathbf{N}^{\prime\prime\prime}$ in $D(X^{\prime\prime\prime})$, the two
cDAGs processing $X$ and $X^{\prime\prime\prime}$ would be the same as per
Assumption 1.

Since the out-going degree of any node in $D(X)$ and
$D(X^{\prime\prime\prime})$ is one, any difference between $f_{S}(X)$ and
$f_{S}(X^{\prime\prime\prime})$ will start at the start at the corresponding
nodes $\mathbf{N}$ (in $D(X)$) and $\mathbf{N}^{\prime\prime\prime}$ (in
$D(X^{\prime\prime\prime})$) respectively, and propagate along the path in the
respective cDAGs to their respective sink nodes $S$ (in $D(X)$) and
$S^{\prime\prime\prime}$ (in $D(X^{\prime\prime\prime})$).

Let $v_{\Pi}\in\mathcal{H}$ denote the value of any node $\Pi$ in a cDAG.
First, let $P_{1},P_{2}$ be the parents of the sink node $S$ in $D(X)$ and
$P_{1}^{\prime\prime\prime},P_{2}^{\prime\prime\prime}$ be the parents of the
sink node $S^{\prime\prime\prime}$ in $D(X^{\prime\prime\prime})$. Since the
outgoing degree is one, and $D(X)$ and $D(X^{\prime\prime\prime})$ only differ
on the parts of the cDAGs involving the sub-parts
$(\mathbf{a}(X),\mathbf{b}(X))$ and
$(\mathbf{a}(X^{\prime\prime\prime}),\mathbf{b}(X^{\prime\prime\prime}))$
respectively, one of the two parent nodes of the sink node will have the same
value in both the cDAGs. We can assume that
$v_{P_{1}}=v_{P_{1}^{\prime\prime\prime}}$ and
$v_{P_{2}}\not=v_{P_{2}^{\prime\prime\prime}}$. Then we have

$\displaystyle|f_{S}(X)-f_{S}(X^{\prime\prime\prime})|$
$\displaystyle=|\hat{h}_{S}(\hat{g}_{S}(v_{P_{1}},v_{P_{2}}))-\hat{h}_{S}(\hat{g}_{S}(v_{P_{1}^{\prime\prime\prime}},v_{P_{2}^{\prime\prime\prime}}))|$
(56) $\displaystyle\leq\gamma c\|v_{P_{2}}-v_{P_{2}^{\prime\prime\prime}}\|,$
(57)

where we utilize the Lipschitz constant of $\hat{h}_{S}$ and of $g_{S}$ as
presented in Definition 2.

Let $\\{P_{21},P_{22}\\}$ be the parent nodes of $P_{2}$ in cDAG $D(X)$, and
$\\{P_{21}^{\prime\prime\prime},P_{22}^{\prime\prime\prime}\\}$ be the
corresponding parents of $P_{2}^{\prime\prime\prime}$ in cDAG
$D(X^{\prime\prime\prime})$. As above, given the clean-separability and
outgoing degree of one, one of the parents from each of the cDAGs will have
the same value, and we can assume $v_{P_{21}}=v_{P_{21}^{\prime\prime\prime}}$
while $v_{P_{22}}\not=v_{P_{22}^{\prime\prime\prime}}$.

$\displaystyle|f_{S}(X)-f_{S}(X^{\prime\prime\prime})|$
$\displaystyle\leq\gamma c\|v_{P_{2}}-v_{P_{2}^{\prime\prime\prime}}\|=\gamma
c\|\hat{g}_{S}(v_{P_{21}},v_{P_{22}})-\hat{g}_{S}(v_{P_{21}^{\prime\prime\prime}},v_{P_{22}^{\prime\prime\prime}})\|$
(58) $\displaystyle\leq\gamma
c^{2}\|v_{P_{22}}-v_{P_{22}^{\prime\prime\prime}}\|.$ (59)

We can continue this recursively till we get to the nodes $\mathbf{N}$ and
$\mathbf{N}^{\prime\prime\prime}$ in the cDAGs $D(X)$ and
$D(X^{\prime\prime\prime})$ respectively after $l$ steps.

Then we have

$\displaystyle|f_{S}(X)-f_{S}(X^{\prime\prime\prime})|$
$\displaystyle\leq\gamma
c^{l}\|v_{\mathbf{N}}-v_{\mathbf{N}^{\prime\prime\prime}}\|=\gamma
c^{l}\|\hat{g}_{S}(v_{\mathbf{N}_{a}},v_{\mathbf{N}_{b}})-\hat{g}_{S}(v_{\mathbf{N}_{a}^{\prime\prime\prime}},v_{\mathbf{N}_{b}^{\prime\prime\prime}})\|$
(60)

Consider the pairs
$U^{\star}\triangleq(v_{\mathbf{N}_{a}},v_{\mathbf{N}_{b}})\in\mathcal{H}^{2}$
and
$U\triangleq(v_{\mathbf{N}_{a}^{\prime\prime\prime}},v_{\mathbf{N}_{b}^{\prime\prime\prime}})\in\mathcal{H}^{2}$,
where the latter pair $U$ is seen in the training set with the remainder
$\mathbf{c}(X)=\mathbf{c}(X^{\prime\prime\prime})$. Let $\psi_{U}$ be the
probability measure induced from the training distribution $\mathcal{P}$ over
the pairs of the form $U$, where $\psi_{U}(B)\in[0,1]$ is the probability
measure in the set $B\subset\mathcal{H}^{2}$.

Let $\mathcal{B}(U^{\star},r)\subset\mathcal{H}^{2}$ denote a ball in
$\mathcal{H}^{2}$ centered around $U^{\star}$ with radius $r>0$. Since we want
to find a tight bound on $\|U^{\star}-U\|$, we essentially want to find the
smallest $r$ such that $\mathcal{B}(U^{\star},r)$ will contain at least one
$U$ from the training set of the aforementioned form.

Let $\hat{\psi}_{U}(B)=\nicefrac{{1}}{{N}}\sum_{(X,y)\in S}\mathbb{I}(U\in B)$
be the empirical estimate of $\psi_{U}(B)$ ($U$ is derived from $X$). Let us
consider a radius $r^{\star}$ such that the empirical estimate
$\hat{\psi}_{U}(\mathcal{B}(U^{\star},r^{\star}))=\nicefrac{{1}}{{N}}$. With
Hoeffding’s inequality, we can show that, with probability at least
$1-\xi^{\prime},\xi^{\prime}\in(0,1)$

$\left|\hat{\psi}_{U}(\mathcal{B}(U^{\star},r^{\star})-\psi_{U}(\mathcal{B}(U^{\star},r^{\star})\right|\leq\sqrt{\frac{\log\nicefrac{{1}}{{\xi^{\prime}}}}{N}}.$
(61)

Thus, a true measure
$\psi_{U}(\mathcal{B}(U^{\star},r^{\star}))=\frac{1}{N}+\sqrt{\frac{\log\nicefrac{{1}}{{\xi^{\prime}}}}{N}}$
will ensure a $U$ from the training set within a radius $r^{\star}$ of
$U^{\star}$ with high probability. Then

$r^{\star}=\psi_{U}^{-1}\left(\frac{1}{N}+\sqrt{\frac{\log\nicefrac{{1}}{{\xi^{\prime}}}}{N}}\right)\triangleq
r(N,\xi^{\prime}),$ (62)

where $\psi_{U}^{-1}$ is the inverse measure around $U^{\star}$. We define the
right-hand-side in the above equation as positive function $r(N,\xi^{\prime})$
that depends on $N$ and $\xi^{\prime}$. This gives us

$\displaystyle|f_{S}(X)-f_{S}(X^{\prime\prime\prime})|$
$\displaystyle\leq\gamma
c^{l}\|v_{\mathbf{N}}-v_{\mathbf{N}^{\prime\prime\prime}}\|=\gamma
c^{l}\|\hat{g}_{S}(v_{\mathbf{N}_{a}},v_{\mathbf{N}_{b}})-\hat{g}_{S}(v_{\mathbf{N}_{a}^{\prime\prime\prime}},v_{\mathbf{N}_{b}^{\prime\prime\prime}})\|$
(63) $\displaystyle\leq\gamma
c^{l+1}\left[\|(v_{\mathbf{N}_{a}},v_{\mathbf{N}_{b}})-(v_{\mathbf{N}_{a}^{\prime\prime\prime}},v_{\mathbf{N}_{b}^{\prime\prime\prime}})\|\right]=\gamma
c^{l+1}\|U^{\star}-U\|$ (64)
$\displaystyle\leq\gamma\,c^{l+1}\,r^{\star}=\gamma\,c^{l+1}\,r(N,\xi^{\prime}).$
(65)

Since we want a uniform bound on $|f_{S}(X)-f_{S}(X^{\prime\prime\prime})|$
for all $X$, $\mathbf{N}_{a},\mathbf{N}_{b}$ can be source nodes in the cDAG
$D(X)$, with $\mathbf{N}_{a}$ and $\mathbf{N}_{b}$ having the longest path to
the sink node in $D(X)$. In that case,

$\displaystyle|f_{S}(X)-f_{S}(X^{\prime\prime\prime})|$
$\displaystyle\leq\gamma\,\max_{l}c^{l+1}\,r(N,\xi^{\prime})\leq\gamma\,{\boldsymbol{\delta}}\,r(N,\xi^{\prime}),$
(66)

where the last inequality is based on the Definition 2 of the locus of
influence in a cDAG with $q=1$, where the
${\boldsymbol{\delta}}=\max_{i\in\llbracket L\rrbracket}\delta_{i}$ is for the
source node with the longest path to the sink node since there is only a
single path from a source node to the sink node.

We can similarly bound $|f_{S^{i}}(X)-f_{S^{i}}(X^{\prime\prime\prime})|$ and
get the following value for the uniform stability bound $\sigma$:

$\sigma\triangleq
2(\epsilon+\gamma\,{\boldsymbol{\delta}}\,r(N,\xi^{\prime})).$ (67)

For sufficiently small $\epsilon$, we can select a positive quantity $C_{N}>0$
which depends on $N$ and $\xi^{\prime}$, such that $\sigma\leq
C_{N}\,\gamma\,\delta$. Plugging this upper bound of $\sigma$ in (51) gives us
(39) in the statement of the theorem with an overall failure probability of
$(\xi+\xi^{\prime})$. ∎