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.
Compositionality is assumed to be integral to language processing [1]. 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 (CG) of sequence or language models. This has led to various language modeling benchmarks [2,3,4,5]. These benchmarks empirically probe the compositionality of language models, often demonstrating the lack of CG. These highlight examples on which the models fail, but there is no precise understanding of why the failures occur. Nonetheless, various novel methods with improved compositional generalization (as measured by these benchmarks) have been developed [6,7,8], utilizing specialized models with compositional inductive biases. However, the area of CG is still lacks a mathematical definition and measure of compositionality.
Our contributions. Inspired by existing discussions, and recent solutions for CG 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. Our definition teases out what we believe to be the "neural" (continuous functions) and the "symbolic" (discrete functions) parts of a model. β’ We demonstrate the flexibility of this definition by highlighting how various existing sequence processing models such as recurrent models [11], convolutional models and transformer based models [12] fit this definition, and how complex their compositions are.
We define compositional functions π : π³ β π΄ with the domain π³ of input sequences π = {π₯ 1 , . . . , π₯ πΏ } of atoms or tokens π₯ π β β from an input dictionary β. The range π΄ of π can be R for regression, {0, 1} for binary classification, or β for next token prediction.
Definition 1. To define π , we need the following components:
β’ Token encoder π : β Γ N β β (latent space), with π π = π(π₯ π , π) β β encoding the π th token in π β π³ .
β’ A computation directed acyclic graph (DAG) or cDAG π· : π³ β π, where π is the space of DAGs, and π·(π) defines the hierarchical processing of a sequence π. π·(π) can also be viewed as the trace of program used by function π to process π. We will describe this in further detail soon. β’ Span processor π : β π β β maps π terms in the latent space into a new term in the latent space.
β’ Read-out function β : β π β π΄ maps the final set of terms in the latent space to the output space π΄. With π βπ·(π) denoting the recursive operation of π over π·(π), we define a compositional function as:
A computation DAG or cDAG π·(π) β {π (π), πΈ(π)} for a specific input sequence π β π³ can depend on π or be pre-specified. This cDAG is a leveled DAG with set of nodes π (π) and edges πΈ(π). Each node π β (π : π) β π (π) has a level π and index π. The recursive application of π over π·(π) induces a value π£ π:π β β for each internal node π β π (π). The sources is π (π) have level 0, and there is one source for each π₯ π β π, π β πΏ β {1, . . . , πΏ} with index π and value π£ 0:π = π(π₯ π , π) β β. There are π sinks in π (π), and at most π incoming edges and π outgoing edges at any node. For an internal node π β π (π) with π parents π (π), the value π£ π:π = π(π£ π 1 :π 1 , . . . , π£ π π :π π ) β β where π£ π π :π π is the value of the π th parent in π (π). One way to interpret this cDAG is as the trace of "forward-pass" for inference.
We consider the explicit cDAG because it allows us to see how the different elements π₯ π , π β πΏ of the input sequence π 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 [13,14], this explicit cDAG can be seen as the symbolic part, while the π, π, β 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 π : β π β β takes as input π elements from the latent space β and outputs an element in β. While the definition implies that the same π needs to be operated recursively over the cDAG π·(π), there is no restriction on the inputs and output of π regarding the information encoded in the latent space. For example, if the level π of any node π:π is encoded into its value π£ π:π , then the π will behave differently across levels (level-dependent); if the index π of the node π:π is encoded into its value, then π 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 π can be type-dependent. Our definition states that the arity of the span processor π : β π β β is π. We do so for the ease of exposition, though our definition can incorporate more flexible span processors (see Ram et al. [10,Appendix A.2]).
The read-out function β : β π β π΄ finally maps π elements in the latent space to the output space π΄. This separation between π and β was necessary in our proposed definition because we require π to be operable recursively, and thus π can operate in a latent space β distinct from π΄. In some applications, β β π΄, in which case, β can be an identity function. There are couple of aspects of this read-out function we wish to discuss explicitly -(i) We assume that β is specifically non-compositional and processes its input without breaking it up into any sub-problems; we explicitly define the compositional function π separating out π, π·, β, where π (neural) and π· (symbolic) represent the compositional part. (ii) We require β to have a fixed-arity of π since π and π· are aggregating the information over the input.
In the following, we will illustrate Definition 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 π = 1, implying a single path from any source to a sink. Example 2 has a cDAG with a maximum out-degree π = 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 π, π Β―from the same problem domain, and the same compositional function π , we allow the cDAG to be different -cDAG π·(π) can be input-dependentthereby allowing different input sequences to have different sub-problem hierarchies. 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. The compositional complexity of π depends on the functions π, β, π as well as the cDAG function π· that drives the computation. For a sequence π of length πΏ, π·(π) has πΏ source nodes, maximum in-degree of π (controlling the span size for π), π sink nodes (controlling the capacity of β), maximum out-degree of π (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. We propose a new quantification -the locus of influence (LoI): This definition of the complexity of composition incorporates both the complexity of the cDAG π·(π) and the complexity of the span processor π : β π β β in terms of its smoothness, with higher values of π indicating more complex (less smooth) π. The absolute LoI πΏ π 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 πΏ π of any input index π, more local its effect, and thus more structure that can be transferred between examples if π₯ π is replaced with something else. A relative LoI π½ π greater than 1/πΏ denotes that the input index π (and thus input token π₯ π ) has an out-sized effect on π·(π) (and thus the computation) compared to the other indices (tokens). In Example 1 (left), πΏ 1 = π 2 , π½ 1 = 1 /2π+3 < 1 /5 while πΏ 3 = π 3 , π½ 3 = π /2π+3 > 1 /5, implying that π₯ 3 has more influence (absolute and relative) function than π₯ 1 (assuming π > 1). In Example 2 (left), πΏ 1 = π 4 + 2π 3 , π½ 1 = π+2 /27π+39 β 1 /22 < 1 /7, while πΏ 5 = 7π 4 + 9π 3 , π½ 5 = 7π+9 /27π+39 β 1 /4 > 1 /7, hence π₯ 5 has a significantly larger influence than π₯ 1 . We utilize the LoI to define the complexity of a compositional function, and a class of such compositional functions: Definition 3. A function π : π³ β π΄ with components π, β, π, π· is (π, π, π, πΏ, π½)-compositional if, for any π β π³ of length πΏ, the cDAG π·(π) has a in-degree of π, maximum outgoing degree of π, and π sink nodes, and for βπ β πΏ , πΏ π β€ πΏ, and π½ π β€ π½ β [1/πΏ, 1). We denote with β± a class of such (π, π, π, πΏ, π½)-compositional functions.
A small πΏ and a π½ close to 1/πΏ 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/πΏ 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/πΏ 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. The cDAG for various existing sequence processing models such as the unidirectional and bidirectional recurrence models, convolutional models and attention based transformer models. In Fig. 2, we re-express existing sequence processing models as per our definition, teasing out the symbolic cDAG (and the neural π, β), and we present their (simplified) compositional complexity in Table 1 assuming that all models classes utilize span processors π with the same smoothness parameter π for the ease of exposition. This highlights the flexibility and utility of our proposed quantification of compositionality (see Ram et al. [10,Section 4] for more details and models). Beyond the properties of the cDAG (the in-degree π, out-degree π and number of sink nodes π) and the upper bounds on the absolute LoI πΏ and relative LoI π½, we also highlight two properties: (i) Whether the model utilizes (implicitly or explicitly) an input-dependent cDAG (that is, π·(π) is not the same DAG for all π of length πΏ), and (ii) Whether the same model is able to operate on arbitrary length input sequences. The use of input-dependent cDAG has implications in terms of the expressivity of the model -it can be shown that functions from a model class (with compositional complexites πΏ, π½) with a fixed input-agnostic cDAG cannot approximate functions from a model class of matching compositional complexity (that is, same compositional complexity πΏ, π½) that utilize input-dependent cDAGs. Ram et al. [10,Theorem 1] show that the approximation is lower and upper bounded by πͺ(πΏ) and πͺ(πΏ/π½) respectively. This implies that a higher value of absolute compositional complexity πΏ, and a smaller relative compositional complexity π½ adversely affect the approximation guarantees. The absolute compositional complexity πΏ has been shown to be directly tied to the generalization gap for a learned compositional function, with higher πΏ implying worse systematic generalization guarantee [10,Theorem 2]. The ability to operate on arbitrary length sequences is a prerequisite to the ability of a model to possess length generalization or productivity -the ability to generalize to sequences of larger lengths than those seen during training. We will be pursuing length generalization in our future work.
In this paper, we briefly present our novel definition of compositional functions that explicitly separates out the neural and symbolic aspects of a model for the ease of analysis. We also present a notion of compositional complexity that quantifies the complexity with which the tokens in an input sequence are put together to get to the output. We briefly highlight the generality and utility of this definition by demonstrating how existing sequence processing models fit into this definition.