CTL ++: Evaluating Generalization on Never-Seen Compositional Patterns of Known Functions, and Compatibility of Neural Representations (2022)

Abstract: Well-designed diagnostic tasks have played a key role in studying the failure of neural nets (NNs) to generalize systematically. Famous examples include SCAN and Compositional Table Lookup (CTL). Here we introduce CTL++, a new diagnostic dataset based on compositions of unary symbolic functions. While the original CTL is used to test length generalization or productivity, CTL++ is designed to test systematicity of NNs, that is, their capability to generalize to unseen compositions of known functions. CTL++ splits functions into groups and tests performance on group elements composed in a way not seen during training. We show that recent CTL-solving Transformer variants fail on CTL++. The simplicity of the task design allows for fine-grained control of task difficulty, as well as many insightful analyses. For example, we measure how much overlap between groups is needed by tested NNs for learning to compose. We also visualize how learned symbol representations in outputs of functions from different groups are compatible in case of success but not in case of failure. These results provide insights into failure cases reported on more complex compositions in the natural language domain. Our code is public.

## introduction neural networks (nns) should ideally learn from training data to generalize systematically @xcite , by learning generally applicable rules instead of pure pattern matching. existing nns, however, typically don't. for example, in the context of sequence processing nns, superficial differences between training and test distributions, e.g., with respect to input sequence length or unseen input/word combinations, are enough to prevent current nns from generalizing (lake and @xcite . training on a large amounts of data might alleviate the problem, but it is infeasible to cover all possible lengths and combinations. indeed, while large language models trained on a large amounts of data have obtained impressive results @xcite , they often fail on tasks requiring simple algorithmic reasoning, e.g., simple arithmetics @xcite . a promising way to achieve systematic generalization is to make nns more compositional @xcite , by reflecting and exploiting the hierarchical structure of many problems either within some nn's learned weights, or through tailored nn architectures. for example, recent work by @xcite proposes architectural modifications to the standard transformer @xcite motivated by the principles of compositionality. the resulting neural data router (ndr) exhibits strong length generalization or productivity on representative datasets such as compositional table @xcite ; @xcite ). the focus of the present work is on systematicity: the capability to generalize to unseen compositions of known functions/words. that is crucial for learning to process natural language or to reason on algorithmic problems without an excessive amount of training examples. some of the existing benchmarks (such as cogs @xcite and pcfg @xcite ) are almost solvable by plain nns with careful tuning @xcite , while others, such as cfq @xcite , are much harder. a recent analysis of cfq by @xcite suggests that the difficult examples have a common characteristic: they contain some local structures (describable by parse trees) which are not present in the training examples. these findings provide hints for constructing both challenging and intuitive (simple to define and analyze) diagnostic tasks for testing systematicity. we propose ctl++, a new diagnostic dataset building upon ctl. ctl++ is basically as simple as the original ctl in terms of task definition, but adds the core challenge of compositional generalization absent in ctl. such simplicity allows for insightful analyses: one low-level reason for the failure to generalize compositionally appears to be the failure to learn functions whose outputs are symbol representations compatible with inputs of other learned neural functions. we will visualize this. well-designed diagnostic datasets have historically contributed to studies of systematic generalization in nns. our ctl++ strives to continue this tradition. ## extensions for systematicity: ctl++ to introduce a systematicity split to the ctl framework, we divide the set of functions into disjoint groups and restrict the sampling process such that some patterns of compositions between group elements are never sampled for training, only for testing. based on this simple principle, we derive three variations of ctl++. they differ from each other in terms of compositional patterns used for testing (excluded from training) as described below. we'll also visualize the difference using sampling graphs in which the nodes represent the groups, and the edges specify possible compositional patterns. the colors of the edges reflect when the edges are used: black for both training and testing, blue for training, and red only for testing. variation 'a' (as in 'alternating'). here functions are divided in groups g a and g b . during training, successively composed functions are sampled from different groups in an alternating wayi.e., successive functions cannot be from the same group. during testing, however, only functions from the same group can be composed. the sampling graph is shown in fig. 1 . importantly, the single function applications are part of the training set, to allow the model to learn common input/output symbol representations for the interface between different groups. variation 'r' (as in 'repeating'). this variant is the complement of variation 'a' above. to get a training example, either g a or g b is sampled, and all functions in that example are sampled from that same group for the whole sequence. in test examples, functions are sampled in an alternating way. there is thus no exchange of information between the groups, except for the shared input embeddings and the output classification weight matrix. the sampling graph is like in fig. 1 for 'a' except that blue edges should become red and vice versa (see fig. 5 in the appendix). variation 's' (as in 'staged'). in this variant, functions are divided into five disjoint groups: g a1 , g a2 , g b1 , g b2 and g o . as indicated by the indices, each group belongs to one of the two paths ('a' or 'b') and one of the two stages ('1' or '2'), except for g o which only belongs to stage '2' shared between paths 'a' and 'b' during training. the corresponding sampling graph is shown in fig. 2 . to get a training example, we sample an integer k which defines the sequence length as 2k + 1, and iterate the following process for @xmath0, .., k] and @xmath1: we first sample a path @xmath2, b} and then a function f i from g p1 and a function f i+1 from g p2 ∪ g o . each example always contains an even number of functions, and no isolated single function application is part of training, unlike in the previous two variants. for testing, we sample a path @xmath3, b} and a function f i from g p1 , but then sample a function f i+1 from g {a,b}\{p}2 , which results in a compositional pattern never seen during training. the unique feature of this variant is the use of two stages: as can be seen in fig. 2 , during training, given a path @xmath4, b}, outputs of any functions belonging to g p1 are only observed by the functions belonging to g p2 , i.e., the stage '2' group belonging to the same path p, or g o . hence, if g @xmath5, the model has no incentive to learn common representations for the interface between g a1 and g b1 : to solve the training examples, it suffices to learn output representations of g a1 which are 'compatible' with the input representations of g a2 ; similarly for g b1 and g b2 . there is no reason for outputs of g a1 to be compatible with the inputs of g b2 (analogously for g b1 and g a2 ) which is required at test time. the size of g o is our first parameter for controlling task difficulty (the y-axis of fig. 4 which we will present later). we introduce further restrictions: for each function @xmath6, we define a set of symbols s f a for g a1 (and s f b for g b1 ), and we only allow for sampling f if the output symbol of function from g a1 (or g b1 ) belongs to s f a (or s f b ). this allows for defining another control parameter: the number of overlapping symbols between s f a and s f b (same for all f ; the x-axis of fig. 4 ). note that we ensure that the union of shared symbols defined for functions in g o cover all possible symbols. this might not be the case in a more realistic scenario, but as we'll see, the standard models already struggle in this setting. by controlling these two parameters, we precisely control the degree of overlap offered by g o in terms of both the number of functions and symbols. ideal models should be "sample efficient" in terms of this overlap, since we cannot expect the training set to contain all combinations of such overlaps in a practical scenario with semantically rich domains such as natural language. ## results we evaluate standard ctl-tested models on the new ctl++ task, including: the transformer @xcite with shared layers @xcite , the neural data router (ndr) @xcite • @xcite , and the bi-directional lstm (hochreiter @xcite @xcite . recall that both ndr and bi-directional lstm are reported to perfectly solve the original ctl's length generalization split @xcite , unlike the transformer. further experimental details can be found in appendix a. ## conclusion motivated by the historically crucial role of diagnostic datasets for research on systematic generalization of nns, we propose a new dataset called ctl++. unlike the classic ctl dataset, typically used for testing productivity, ctl++ is designed for testing systematicity. we propose three variants, 'a,' 'r,' and 's.' despite their simplicity, even the ctl-solving transformer variant fails on 'a' and 'r.' using 's,' we show that existing approaches require impractically large amounts of examples to achieve perfect compositional generalization. the small task size allows for conducting exhaustive visualizations of (in)compatibility of learned symbol representations in outputs of functions with inputs of subsequent functions. of course, the ultimate goal is to go beyond just solving ctl++. nevertheless, we hope ctl++ will become one of the standard diagnostic datasets for testing systematicity of nns.