Memorize or generalize? Searching for a compositional RNN in a haystack

Motivation

• Standard neural networks often require task specialization, show little cross-task transfer, and need large amounts of training data; compositional learning could improve generalization and reduce sample complexity.Compositional learning means discovering skills shared across problems and recombining them hierarchically for new challenges.Source: §1 · p. 1

Contribution

• The paper tests compositional generalization in standard RNNs without special architectural constraints using a lookup-table composition domain.The domain provides a simple, flexible setting for studying whether networks can compose learned functions.Source: §1 · p. 1
• With explicit hidden-layer supervision, the authors analytically show that an RNN can represent and compose functions in the proposed domain.The paper then removes this additional supervision to test whether compositional behavior can emerge through ordinary training.Source: §1 · pp. 1–2

Results

• A large random search finds partial compositional solutions in a small but non-negligible minority of RNNs, although an average training run does not converge compositionally.The result motivates combining gradient descent with evolutionary selection favoring models that develop more compositional approaches.Source: §1 · p. 2
• Compositional convergence depends more on seemingly minor factors such as task-presentation and weight-update order than on initialization.This conclusion supports searching for and selecting rare models that develop compositional behavior.Source: §1 · p. 2

Motivation

• Function composition is a useful test because it increases expressivity and enables recursion over potentially unbounded structures.The paper connects this combinatorial-infinity property to language, planning, and mathematical reasoning.Source: §2 · p. 2

Lookup-table domain

• Each table-lookup task is an arbitrary bijection over fixed-length bit strings, requiring rote memorization rather than sophisticated primitive-task solving.For 3-bit strings, the domain contains 8 possible inputs and 8! = 40, 320 distinct mapping tables.Source: §2 · p. 2
• Because lookup functions share domain and co-domain, every output is a valid input to another function, enabling an infinite number of compositions.Examples include cg(000) = 101, gg(000) = 001, and cgc(001) = 101.Source: §2 · p. 2

Task representation

• The composed-task output includes intermediate mapping results, making the sequence of function applications explicit.Table 1 illustrates this format for two atomic 3-bit tables, g and c, and their composition cg.Source: §2 · p. 2, Table 1 · p. 2

Evaluation

• The domain separates atomic and composed tasks, allowing zero-shot evaluation on unseen inputs after the component mappings have been learned.A compositional system that understands cg as the composition of g and c should produce correct outputs for new cg inputs.Source: §2 · p. 2

Sequence-to-sequence formulation

• The model processes atomic and composed lookup tasks as character-level sequence-to-sequence episodes, beginning output after the input terminator.An output is correct when it contains the specified function result and ends with a dot.Source: §3 · p. 2
• For composed tasks, the network generates the function-composition output sequence, including the intermediate-step representation required by the task format.The prompt uses function codes in application order, so the code gc means applying g before c.Source: §3 · p. 2

Evaluation

• Results remain stable when models are asked to produce only the final output rather than intermediate outputs.This is reported as a robustness check on the output-format requirement.Source: §3 · p. 2

Training objective

• The experiment’s objective resembles traditional language modeling because the network predicts output characters sequentially.At each step, the model selects the output character with the highest score from the softmax layer.Source: §3 · p. 3

Model

• The architecture uses a recurrent LSTM layer with 60 units and a sigmoid layer with 10 units, receiving concatenated one-hot encodings of the current input and previous output characters.The output layer is a three-unit softmax over 0, 1, and dot.Source: §3 · p. 3

Training

• The model is implemented in PyTorch and trained with Adam, with further training details specified separately for the two experiments.The supplied passage does not provide the experiment-specific optimization schedules.Source: §3 · p. 3

4.1. Experiment 1: Can an RNN encode a compositional solution through a finite-state automaton?

• The finite-state encoding stores the task stack, current input bits, output index, and previously produced bits across five recurrent-layer segments.The experiment used a 29-unit recurrent layer with segments A–E representing these state components.Source: §4.1 · p. 3
• 96% of atomic and composed test cases were correct after direct supervision trained the RNN’s finite-state transition structure and output mappings.The network saw no composed tasks during mapping training; generalization arose from the recurrent transition logic and hidden-layer connectivity.Source: §4.1 · p. 4

4.2. Experiment 2: Search for a compositional RNN over model initializations

• In a 50k-model search trained with standard gradient descent, ≈2% exceeded 80% zero-shot accuracy and 0.75% exceeded 90%, while baselines did not approach these levels.Models were evaluated on 128 withheld composed task–input combinations.Source: §4.2 · p. 5
• Consistently shuffled composed-task prompts left the performance curve largely unchanged, indicating that successful models memorized arbitrary task codes rather than decoding prompt structure.Additional tests on unseen composed tasks also found poor generalization, supporting this interpretation.Source: §4.2 · p. 6
• Training on composed tasks only produced 5.55% of models with zero-shot accuracy above 90%, although more models also fell to baseline-level generalization.This pattern suggests those models induced representations of atomic lookups while learning composed tasks rather than exploiting prior atomic-task representations.Source: §4.2 · pp. 6–7
• Re-running favorable and unfavorable initializations suggested that task-presentation and weight-update order, rather than initialization itself, determined convergence to successful models.A pure search without training produced no network better than chance.Source: §4.2 · pp. 5, 7

• Reinforcement-learning approaches typically compose skills by temporally concatenating action sequences, which lacks the recursive properties of function composition.Source: §5 · p. 7
• Modular neural systems combine task-specific modules with controllers or gating systems, but commonly require architectural assumptions, module supervision, or hand-coded functionality.Source: §5 · p. 7
• Differentiable skill-composition systems recursively combine skill embeddings, while separately training the skill networks and composition function.Source: §5 · p. 7
• Sequence-to-sequence RNNs evaluated in compositional navigation fail when generalization requires systematic compositional skills.Source: §5 · p. 8

6. Discussion

• RNNs can learn compositional solutions in the lookup-table domain, at least for a finite number of compositions, enabling zero-shot generalization to unseen composed-task inputs.The successful models appear to use a weaker form of composition that treats composed prompts as undecomposable task units.Source: §6 · p. 8
• Initializations had little effect on final performance, whereas task-presentation order and weight updates influenced whether models followed memorization-based or compositional paths.This indicates that seemingly minor stochastic factors can determine the solution found by training.Source: §6 · p. 8
• The compositional strategies induced by the best models remain insufficiently understood, motivating extraction of finite-state automata from learned RNNs.This reverses the paper’s earlier FSA-to-RNN direction.Source: §6 · p. 8
• The current training regime does not explicitly reward zero-shot generalization, which is evaluated only at test time after repetitive cross-entropy training.Future work therefore considers evolutionary techniques using held-out compositions as a fitness criterion.Source: §6 · p. 8
• Evolutionary methods may support more plastic and modular architectures, but informal NEAT experiments failed to solve even the atomic lookup tasks.The greater flexibility of evolutionary approaches therefore brings convergence difficulties in this domain.Source: §6 · p. 8
• The lookup-table findings have not yet been established for longer strings, more compositions, prompt comprehension, or other compositional problems such as language.These are identified as future tests of the domain’s and results’ scope.Source: §6 · p. 8