What Makes Models Compositional? A Theoretical View

1 Introduction

Compositionality is assumed to be integral to language processing [Pagin and Westerst˚ahl, 2010a; Pagin and Westerst˚ahl, 2010b]. 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´as 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: 1

• 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 RelatedWork

A definition of compositionality [Pagin and Westerst˚ahl, 2010a] states that the meaning µ(·) of an expression is:

where α is a (grammar) rule applied to the sub-terms ui to obtain the expression α(u1, . . . , uk), and rα is a meaning operation that depends on the rule α. 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.

1 A preliminary version of this work [Ram et al., 2023] was previously presented at the KBCG@IJCAI23 workshop, while the supplementary material for this submission [Ram et al., 2024] can be found at https://www.arxiv.org/abs/2405.02350.

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´as 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 ui, i ∈ �k�. 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 : X → Y with the domain X of input sequences X = {x1, . . . , xL} of atoms or tokens xi ∈ I from an input dictionary I. The range Y of f can be R for regression, {0, 1} for binary classification, or I for next token prediction.

Definition 1. To define f, we need the following components:

• Token encoder e : I × N → H (latent space), with ei =
• e(xi, i) ∈ H encoding the ith token in X ∈ X .
• A computation directed acyclic graph (DAG) or cDAG D : X → 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 : Hk → H maps k terms in the latent space into a new term in the latent space.
• Read-out function h : Hm → Y which maps the final set of terms in the latent space to the output space Y.

Given the above, we define a compositional function as

where g⊗D(X) is the recursive operation of g over D(X).

Next we further discuss the components.

A computation DAG or cDAG D(X) ≜ {N(X), E(X)} for a specific input sequence X ∈ 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 ≜ (l : i) ∈ N(X) has a level l and index i (see Appendix A.1 in supplement for details). The recursive application of g over D(X) induces a value vl:i ∈ H for each internal node n ∈ N(X). The sources is N(X) have level 0, and there is one source for each xi ∈ X, i ∈ �L� ≜ {1, . . . , L} with index i and value v0:i = e(xi, i) ∈ 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 ∈ N(X) with k parents P(n), the value vl:i = g(vl1:i1 , . . . , vlk:ik ) ∈ H where vlj:ij is the value of the j 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 xi, i ∈ �L� 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 : Hk → H takes as input k elements from the latent space H and outputs an element in 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 vl: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 : Hk → H is k. We do so for the ease of exposition, though our definition can incorporate more flexible span processors (see Appendix A.2 in supplement).

The read-out function h : Hm → Y finally maps m elements in the latent space to the output space 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 H distinct from Y. In some applications, H ⊇ 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. 3a for example), h would effectively be a mapping from X → 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 = [x1, . . . , x5], with f(X) = h (g (g (e1, e2) , g (g(e3, e4), e5))), k = 2 in-degree, q = 1 out-degree, m = 1 sink, ei = e(xi, i) ∈ H, span-processor g : H2 → H, and read-out function h : H → Y. The values v0:i = ei for sources 0:i, i ∈ {1, . . . , 5}, and the internal node values are: v1:1 ← g(e1, e2), v1:2 ← g(e3, e4), v2:1 ← g(v1:2, e5), v3:1 ← g(v1:1, v2:1). h operates on v3:1 at sink 3:1. Figure 1 (right) shows the cDAG D(X′ ) of the same f on X′ ̸= X with the same k = 2, q = 1,m = 1 and f(X′ ) = h (g(g(e1, g(e2, e3)), g(e4, e5))).

Example 2. Figure 2 (left) shows the cDAG D(X) for a compositional f on X = [x1, . . . , x7], with f(X) = h (v4:1, v3:1), k = 3 maximum in-degree, q = 3 maximum out-degree, m = 2 sinks, ei = e(xi, i) ∈ H, span processor g : H3 → H, and read-out function h : H2 → Y. The source values v0:i = ei for each i ∈ {1, . . . , 7}, and the internal node values are: v1:1 ← g(e1, e2, e3), v1:2 ← g(e2, e3, e4), v1:3 ← g(e3, e5, e7), v1:4 ← g(e4, e5, e6), v1:5 ← g(e5, e6, e7), v2:1 ← g(v1:1, v1:2, v1:3), v2:2 ← g(v1:1, v1:3, v1:4), v2:3 ← g(v1:2, v1:4, v1:5), v2:4 ← g(v1:3, v1:4, v1:5), v3:1 ← g(v2:1, v2:2, v2:3), v3:2 ← g(v2:2, v2:3, v2:4), v4:1 ← g(v3:2, v2:3, v2:4). h operates on v3:1 and v4:1 at sinks 3:1 and 4:1. Figure 2 (right) shows the cDAG D(X′ ) of the same f on X′ ̸= 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 outdegree 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′ 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 ui are recursively built up. At a non-technical level, we also believe that our proposed Definition 1 connects intuitively to existing definitions:

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 (vn1 , . . . , vnj , . . . , vnk ) ∈ Hk be any input to the span processor g, with vn = g(vn1 , . . . , vnj , . . . , vnk ) its output. Let ε ∈ H be a "perturbation" to the j th argument to g, j ∈ �k�, resulting in the perturbed output vjn (ε) = g(vn1 , . . . , vnj + ε, . . . , vnk ). Let c > 0 be an universal constant such that ∀j ∈ �k�, ∀ε ∈ H,

For a sequence X ∈ X of length L, and a source node 0:i in D(X), let P(xi) 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 δi = ∑P∈P(xi) c|P| , with |P| as the length of a path P ∈ P(xi), and the relative LoI as βi = δi/ ∑j∈�L� δ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 : Hk → H in terms of its smoothness, with higher values of c indicating more complex (less smooth) g. The absolute LoI δ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 δi of any input index i, more local its effect, and thus more structure that can be transferred between examples if xi is replaced with something else. A relative LoI βi greater than 1/L denotes that the input index i (and thus input token xi) has an out-sized effect on D(X) (and thus the computation) compared to the other indices (tokens). In Example 1 (left), δ1 = c2 , β1 = 1/2c+3 < 1/5 while δ3 = c3 , β3 = c/2c+3 > 1/5, implying that x3 has more influence (absolute and relative) function than x1 (assuming c > 1). In Example 2 (left), δ1 = c4 + 2c3 , β1 = c+2/27c+39 ≈ 1/22 < 1/7, while δ5 = 7c4 + 9c3 , β5 = 7c+9/27c+39 ≈ 1/4 > 1/7, hence x5 has a significantly larger influence than x1.

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

Definition 3. A function f : X → Y with components g, h, e, D is (k, q, m, δ, β)-compositional if, for any X ∈ X of length L (that is, |X| = L), the cDAG D(X) has a indegree of k, maximum outgoing degree of q, and m sink nodes, and for ∀i ∈ �L�, δi ≤ δ, and βi ≤ β ∈ [1/L, 1). We denote with F a class of such (k, q, m, δ, β)-compositional functions.

A small δ and a β 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 δ and a β 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 δ and a β 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 ui are sub-parts, we highlight a special case of our proposed Definition 3 of compositional functions: If the sub-parts ui, uj, i ̸= j are non-overlapping throughout the recursion, up to the base case where the sub-parts, ui, 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(xi)| = 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 ExistingModels 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 in the supplement.

We begin with the trivial cDAG of no hierarchical composition in Fig. 3a. All sources in D(X) connect to separate sinks. The composition is written as h(g(e1), g(e2), g(e3), g(e4)). For L-length inputs, this is a (k = 1, q = 1,m = L, δ = c, β = 1/L)-compositional function class.

4.1 Recurrent Composition

Figure 3b presents an example cDAG for unidirectional recurrent composition, with the corresponding compositional function h(g(g(g(e1, e2), e3), e4)). 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

(a) No hierarchy

(b) Unidirectional recurrence

(c) Bidirectional recurrence

(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.

is input-agnostic, that is D(X) = D(X′ )∀X,X′ ∈ X with |X| = |X′ |. 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 δ ≜ cL-1 , with a maximum relative LoI of β ≜ (cL - cL-1 )/(2cL - cL-1 - 1).

The absolute LoI is large (exponential in the input length), and the relative LoI is close to 1/2 ≫ 1/L for large enough L.

Figure 3c is an example of a cDAG of a bidirectional recurrent composition, which can be written algebraically as h(g(g(g(e1, e2), e3), e4), g(g(g(e4, e3), e2), e1)). 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 δ ≜ cL-1 + c, with a maximum relative LoI of β ≜ (cL - cL-1 + c2 - c)/2(2cL - cL-1 - 1).

Note that, while the δ for the bidirectional recurrent composition remains of the same order as that of the unidirectional recurrent one, β is approximately halved (approaching 1/4).

Figure 3d 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(e1, e2), g(e3, e4))). 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 δ ≜ c⌈log2 L⌉ , with a maximum relative LoI of β ≜ 1/L.

This form of composition significantly reduces the complexity of the cDAG relative to the previous two models both in terms of δ (linear dependence in L instead of exponential) and β (1/L instead of a constant ≫ 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 inputagnostic, 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; Shen et al., 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.

4.2 Convolutional Composition with Pooling

Figure 4a 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 Figure 5a in supplement for a detailed version of Fig. 4a that shows how repeated conv+pool implicitly induces the cDAG in Fig. 4a; Figure 5e and corresponding cDAG in Figure 5f in the supplement provides an example of convolution with padding over a span of size 2 and pooling over a span of 3). The composition in Fig. 4a can be algebraically written as h(g(g(e1, e2, e3), g(e3, e4, e5), g(e5, e6, e7))). 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 ≪ L, the conv+pool composition has a maximum absolute LoI of δ ∼ O(clog L), and a maximum relative LoI of β ∼ 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 5c shows an example of selective pooling, with the corresponding input-dependent cDAG shown in Figure 5d. This function can operate on arbitrary length input sequences.

4.3 Transformers

Figure 4b expresses the cDAG of a transformer with M levels or "blocks", where the span-processor g : Hk →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 Appendix B.5 in the supplement). We consider the version where, for inference, only the last token representation (after M transformer blocks) is utilized for prediction - 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 δ = LM+1 cM+1 , and a maximum relative LoI of β = 1/L.

This function class has a really high δ (exponential in the number of blocks M but polynomial in the input length L

unless M > L) and the lowest possible β = 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 β = 1/L, but the δ 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 β).

This composition does not explicitly have an inputdependent 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 ≪ L nonzero scores (rest zero), the cDAG will have much fewer edges as in Fig. 4c (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 withM blocks and K-sparse attention (K ≪ L) has a maximum absolute LoI of δ = LKM cM+1 , and a maximum relative LoI of β = 1/K.

Contrasting this to the complexity of the standard transformer (Proposition 5), we see that the δ is considerably lower (O(LLM ) vs O(LKM ) with K ≪ L), implying that the LoI of any one input token (thus the sensitivity) is substantially reduced. However, the relative LoI β 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.

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

Proposition 7. A decoder-only transformer with M blocks has a maximum absolute LoI is δ = LM cM+1 , and a maximum relative LoI of β = 1/(1 + ∑i∈�L-1� (i/L)M ).

As L or M grows, the sum ∑i (i/L)M goes to zero, and thus, β → 1. For some ∆ ∈ (0, 1), β ≜ 1/(1 + r∆) for the largest r ∈ �L� such that ∆ ≤ (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 δ, similar β). 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.

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 δ and relative LoI β. 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 Appendix 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 inputdependent). 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; see Appendix C in the supplement for details and proof.

Theorem 1 (condensed). Consider a (k, q,m, δ, β)- compositional function class F, and input sequences X ∈ X of length L. Consider a ground-truth function f ∈ F with components e,D, g, h, and a compositional function f ∈ F with components e, D, g, h, with an input-agnostic cDAG such that D(X) = D∀X ∈ X, |X| = L. 2 Then the worst-case approximation of f by f, for f, f ∈ F is given by:

where f(X) = h(g⊗D(X) (e(x1), . . . , e(xL)), and f(X) = h(g⊗D(e(x1), . . . , e(xL)), with general smoothness and structural assumptions, and universal constants Cl, Cu > 0.

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

2 We assume that the token encoder e is same for both f, f.

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 F, and training data S, generalization guarantees bound the difference between the true risk R( ˆ f) = E(X,y)ℓ(y, ˆ f(X)) of a learned model ˆ f ∈ F and its empirical risk RN( ˆ f). Here we present a condensed result; see Appendix D in the supplement for details.

Theorem 2 (condensed). Consider a (2, 1, 1, δ, β)- compositional function class F, input X ∈ X of length L, a training set S of N samples from a ground-truth function f ∈ 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 ˆ g and the read-out function ˆh to get ˆ f ≜ (e,D, ˆ g, ˆh). Then, with probability at least 1 - ξ,

where CN is a quantity dependent on N and ξ ∈ (0, 1).

If the model class F is expressive, the empirical risk RN( ˆ f) can be small. If CN ∼ O(1/N), then we recover the standard O(1/√N) rate. However, if the compositional complexity, δ, is high, this bound does not provide a favorable systematic generalization guarantee, highlighting that, even with cleanlyseparable 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 inputdependent 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.