arXiv CSopen access

Length Generalization with Log-Depth Recurrent Units

Length Generalization with Log-Depth Recurrent Units Charles Pert

[email protected]

Department of Computing Imperial College London

Dalal Alrajeh

[email protected]

arXiv:2605.26035v1 [cs.LG] 25 May 2026

Department of Computing Imperial College London

Alessandra Russo

[email protected]

Department of Computing Imperial College London

Abstract Length generalization remains a persistent challenge for neural networks: recurrent models tend to suffer from positional biases, while transformers are constrained by fixed computational depth. Regular languages provide a frequently used testbed for evaluating length generalization, as label prediction can be checked for any sequence length. We propose MLP-LDRU, a type of Log-Depth Recurrent Unit, which captures a class of associativitybiased operators designed to approximate recurrence through parallel reduction. We evaluate MLP-LDRU on 21 regular-language tasks, consisting of standard benchmarks and new prefix languages, where it achieves 100% out-of-distribution accuracy on 18 tasks and at least 99.9% on the remaining 3 when increasing max training length, outperforming comparable recurrent and attention-based models. We further evaluate MLP-LDRU beyond regular languages on ListOps and NLP classification benchmarks, where it performs competitively.

1

Introduction

Generalization to out-of-distribution (OOD) sequence lengths remains a central open challenge in neural modeling. As defining OOD sequences is difficult in natural language contexts, regular languages have become a popular testbed for studying this problem. Regular languages are diverse and enable precise mathematical formulation, directly connecting to automata theory, enabling exact validation of correctness at any sequence length. Evaluating models on these tasks enables precise measurement of whether a model has learned the rules underpinning the task, enabling a characterization of OOD generalization (Strobl et al., 2024). Prior works (Delétang et al., 2023; Chi et al., 2023; Butoi et al., 2025) highlight a trade-off: RNNs (Elman, 1990) offer length-adaptive computation, but earlier tokens undergo more recurrent steps than later ones, which can lead to long-range memory issues (Bengio et al., 1994). Transformers (Vaswani et al., 2017), on the other hand, apply a fixed stack of layers independent of sequence length, and tend to generalize less reliably to OOD lengths. We are interested in enabling recurrence using parallel reduction. It has been shown (Ladner & Fischer, 1980; Blelloch, 1990) that with an associative operator, the parallel reduction algorithm can give a log-depth implementation of a recurrence. But these operator-level constraints have not been sufficiently explored. We hypothesize that learning such operators via an explicit associativity (and identity) bias can improve length extrapolation on regular language tasks. We start from regular tasks as a rigorous first step toward exploring length-extrapolating sequence models in more complex settings. In this paper, we explore log-depth sequence processing by learning reduction operators, in particular, those designed to approximate associativity, and name this class Log-Depth Recurrent Units (LDRUs), which compose token embeddings via a binary operator applied in a balanced tree. Applying this operator in a reduction yields uniform O(log n) computational depth across tokens, mitigating the positional bias of 1

standard RNNs while enabling parallel computation to behave as a recurrence along the sequence. In this paper, we experiment using MLP-LDRU 1 , an LDRU given in Section 3. LDRUs are motivated by the monoid view of regular languages (see Appendix A for details), where concatenation corresponds to an associative product; this suggests that if a learned operator approximates associativity, then using it as a reduction operator will likewise approximate a sequential recurrence, a property that supports length generalization on regular tasks (Delétang et al., 2023). LDRU-based models form a subclass of balanced binary-tree recursive neural networks (BBT-RvNNs; Munkhdalai & Yu, 2017; Shen et al., 2019; Chowdhury & Caragea, 2023). We use the same log-depth reduction, but with a different learning target: instead of learning an unconstrained tree cell, we intentionally bias the operator toward approximate associativity and enforce identity behavior (padding acts as a neutral element). These biases ideally enable the learning of an approximation of a sequential recurrence. We evaluate length generalization on a suite of regular language transduction tasks, including prefix languages that isolate long-range dependency handling under length extrapolation. MLP-LDRU achieves 100% OOD accuracy on 18 of 21 tasks when trained on sequences up to length 40, and near-perfect performance on the remaining 3. Further analysis of the underlying monoids of the tasks suggests that remaining failures stem from insufficient coverage of monoid compositions in training data rather than an architectural limitation. We additionally study ListOps (Nangia & Bowman, 2018) to test compositional extrapolation and report results on several natural language classification benchmarks to probe behavior beyond regular languages. This paper makes the following contributions: • We propose MLP-LDRU, a specific Log-Depth Recurrent Unit, a binary operator designed to induce approximately associative behavior with identity handling. • We empirically evaluate MLP-LDRU on 21 regular tasks, with transfer probe experiments on ListOps extrapolation and NLP classification benchmarks. • We introduce prefix languages, a new class of regular tasks designed to test long-range dependency handling under length extrapolation. • We analyze training data requirements for length generalization, relating failures to insufficient coverage of equivalence class compositions in short sequences. The rest of this paper is organized as follows. Section 2 introduces the prefix languages. Section 3 details MLP-LDRU. Section 4 explains our experimental set-up, and we provide the results in Section 5. Related work is discussed in Section 7. We discuss the implications of our findings in Section 6. Finally, we conclude in Section 8.

2

Prefix Languages

We introduce prefix languages, denoted Pp,q , regular tasks for testing long-range dependency handling through a test of persistent memory of early-state information under distractors. The first p symbols determine the machine’s final state, requiring a model to retain memory of its current state while processing the remainder of the sequence. As each p-length prefix leads to a different final state, these tasks also require a model to distinguish between different orderings of the same information (i.e., consider positional information). We also parameterize q, the number of symbols in the alphabet. See Fig. 1 for a graphical representation of P2,2 . We give a mathematical definition of prefix languages in Appendix B.

3

Method

In this section, we describe the MLP-based operator (used in MLP-LDRU, denoted as ⊙θ ) used in our experiments and describe how it produces a sequence embedding. See Fig. 2 for an illustration of the parallel 1 Code will be released upon publication.

2

0 0/0

1/0

1 2/0

0 1

3/1

0, 1

4/2

0, 1

0 1

5/3

0, 1

6/4

0, 1

Figure 1: The prefix language P2,2 . Nodes are states, and edges are transitions. Labels within nodes X/Y indicate the state X and output symbol Y if a sequence’s run ends in X.

reduction on a length-8 sequence. Given a sequence of length n token embeddings, the model repeatedly applies ⊙θ in parallel to adjacent pairs for ⌈log2 n⌉ steps. Each step consists of applying the operator on all pairs, followed by a residual feedforward network, then layer normalization. The weights of these components are shared across steps. After each reduction step, we apply dropout, empirically observed to encourage more robust generalization (see Appendix E.1). At any step, if the length of the sequence is odd, we pad it with a zero embedding, 0. We treat 0 as a neutral placeholder in ⊙θ : if either input is 0, then the operator output is the other input (i.e., composition is skipped). The residual connection and layer normalization proceed as standard. This pass-through prevents padding-induced artifacts and avoids requiring ⊙θ to learn an identity map.

Figure 2: Log-depth reduction on a length-8 sequence: a pairwise composition operator is applied in parallel to reduce the sequence to a single embedding in log2 (8) = 3 steps, illustrating the O(log n) depth. The core of ⊙θ is an element-wise sum (a natural associative operation) with learned gating weights to control information flow. We produce the gating weights using an MLP. The operator’s gating design draws from the success of gating information flow in recurrent architectures (Hochreiter & Schmidhuber, 1997; Chung et al., 2014; Jozefowicz et al., 2015; Shen et al., 2019). We define ⊙θ : Rd × Rd → Rd on inputs hi , hj ∈ Rd as follows: [gi ; gj ] = MLP([hi ; hj ]) where gi , gj ∈ Rd

(1)

fi = Vi (gi ◦ hi ) + bi , fj = Vj (gj ◦ hj ) + bj

(2)

⊙θ (hi , hj ) = Wout (fi + fj ) + bout ∈ R ,

(3)

d

where [·; ·] denotes concatenation, ◦ is element-wise multiplication, Vi , Vj , Wout ∈ Rd×d are learned projection matrices, and bi , bj , bout ∈ Rd are learned bias vectors. We use a 3-layered MLP with expansion factors (1, 2, 1). Vi , Vj , and Wout are all initialized with the identity, and the corresponding biases are initialized to 0. The element-wise sum combining token embeddings and the combination of these initializations biases ⊙θ toward approximately associative behavior. We briefly describe how a sequence embedding is produced from beginning to end. An embedded sequence is reduced to a single embedding by iteratively applying ⊙θ steps. The single embedding, hn , is passed to a linear classifier to produce class logits. Complete model diagrams and initialization schemes are provided in Appendix C. 3

3.1

Complexity Analysis

MLP-LDRU achieves O(nd2 ) work complexity with O(log n) computational depth (referred to as depth), combining RNN-like linear scaling (of sequence length) with logarithmic-time parallelization. This contrasts with RNNs’ O(n) sequential depth and transformers’ O(n2 d + nd2 ) quadratic sequence length complexity. Further discussion on complexity is provided in Appendix D. Table 1: Computational complexity comparison. The LDRU achieves log n depth and avoids quadratic length scaling. Architecture

Work Complexity

Depth

O(nd ) O(n2 d + nd2 ) O(nd2 )

O(n) O(1) O(log n)

RNN Transformer MLP-LDRU (Ours)

2

We present the practical trade-offs between MLP-LDRU, RNN, and transformer in Fig. 3. We profile the forward and backward passes of the three architectures across sequence length with a batch size of 32. Although MLP-LDRU incurs higher FLOPs and peak memory usage than the RNN, its greater GPU parallelism yields higher throughput. Transformer is significantly slower and costs more FLOPs due to its quadratic length complexity. MLP-LDRU

Tokens per second

Total Time (ms)

RNN

200 100 0

1 0.5

211

1010 108 106

·10 1.5

Peak Memory (MB)

Est. FLOPs

22 29 210

2

2

9

2

2

10

2

11

Transformer 6

0 22 29 210 ·104 3 2 1 0 22 29 210

Sequence Length

211

211

Sequence Length

Figure 3: Empirical runtime analysis of MLP-LDRU, RNN, and transformer across small (160k) parameter regime used for our regular task study. We note that MLP-LDRU’s throughput reaches maxima at 2n as these are the optimally efficient lengths for reduction.

4

Experiments

We evaluate MLP-LDRU using sequence classification tasks. For regular tasks, this corresponds to predicting the single output symbol produced by the task’s corresponding Moore machine. We illustrate these machines in Appendix E. The regular tasks we evaluate are a combination of those previously studied by Delétang et al. (2023) and Bhattamishra et al. (2020), and 6 parameterizations of prefix languages. We also evaluate ListOps (Nangia & Bowman, 2018) to assess MLP-LDRU on hierarchical tasks beyond regular languages. We aim to answer the following research questions: 4

RQ1 Does MLP-LDRU’s generalization ability outperform established state-of-the-art architectures on: (a) regular tasks and (b) ListOps? RQ2 Does increasing the maximum training sequence length improve OOD performance? RQ3 Does the choice of reduction operator impact OOD performance? All models were trained under identical conditions (same training lengths, optimizer, regularization, and number of steps), with full hyperparameters detailed in Appendix E. We train each model by minimizing the cross-entropy loss between the class logits and the ground-truth labels. We use the AMSGrad (Reddi et al., 2018) optimizer for regular tasks, as we empirically observed improved generalization (see Appendix E.1 for details). We use the Adam (Kingma & Ba, 2015) optimizer for non-regular tasks. We do not use early stopping. We use 3 seeds for regular tasks, and 5 seeds for non-regular tasks. We now describe the experimental setup for each research question. RQ1a We train MLP-LDRUs on 21 regular tasks on sequences of variable length, from 1 to 40. We evaluate generalization using OOD accuracy, i.e., the mean accuracy over 512 sampled sequences for each length from 41 to 500. This setup is standard in length generalization studies on regular tasks (Delétang et al., 2023; Liu et al., 2023; Ruoss et al., 2023; Chi et al., 2023). We compare MLP-LDRU to the classic RNN, LSTM, Gated DeltaNet (Yang et al., 2025), transformer (TF), BBT-GRC (Shi et al., 2018), a BBT-RvNN equipped with a Gated Recursive Cell (GRC; Shen et al., 2019), and RegularGPT (Chi et al., 2023) models. We train for 100k or 1M steps, depending on the task. We use 3 positional encodings (PEs) for the transformer: NoPE (Kazemnejad et al., 2023), ALiBi (Press et al., 2022), and randomized RoPE (Ruoss et al., 2023), denoted as ∼RoPE. We assess the statistical significance of performance differences between MLP-LDRU and baseline architectures across tasks using Student’s t-tests. RQ1b We train MLP-LDRUs on ListOps sequences from length 5 to 40 with a maximum nesting of 3 and at most 9 arguments per list. We train models using 3 dataset sizes: 100k, 500k, and 1M sequences. For testing, we consider length buckets: [5, 20], [21, 40], [41, 60], [61, 80], [81, 100], [101, 200]; max depths: 3, 5; max arguments: 9, 14. We test 10k samples per combination, except for lengths [81, 100], [101, 200] with max depth 3 and max arguments 9. We compare MLP-LDRU to LSTM, transformer with NoPE, ALiBi, and Sinusoidal PEs, BBT-GRC, and RIR-GRC (Chowdhury & Caragea, 2023). Further details can be found in Appendix H.1. RQ2 We train MLP-LDRUs and RNNs on D4 , D6 , D8 , and D12 tasks (where Dn is the recognition of the Dyck-1 language up to n stack depth), with varied maximum training lengths: 40, 60, 100, and 150. We use these tasks because neither the RNN nor MLP-LDRU generalizes with 100% accuracy to these tasks when trained with a maximum training length of 40 (except for MLP-LDRU on D4 ). We report the OOD accuracy, e.g., for a maximum training length of 60, the evaluation is on sequences of length 61 to 500. RQ3 We compare five choices of reduction operator evaluated on the regular tasks from Delétang et al. (2023). All settings are otherwise the same as for RQ1. We test: (1) element-wise sum, (2) a linear projection of the concatenation of the two embeddings without activation, (3) a simple gated combination of the two embeddings, (4) GRC, and (5) the MLP-based operator used in MLP-LDRU. We report mean OOD accuracy for each operator-task combination.

5

Results

We present the results of the RQ1a regular experiments in Table 2. MLP-LDRU demonstrates stronger or comparable length generalization across these tasks, achieving 100% OOD accuracy on 18 tasks and near-perfect performance on the remaining 3 tasks. MLP-LDRU outperforms all 3 transformer variants except on D8 and D12 for ∼RoPE; moreover, ∼RoPE achieves the highest OOD accuracy of all baselines on D12 , indicating that while it is not as consistent as MLP-LDRU, it is certainly more powerful than NoPE and ALiBi on Dn . However, ∼RoPE does not provide consistent gains across regular tasks as its performance on Modular Arithmetic is much worse (31.4%) compared to the other TF PEs considered (76.0%, 54.4% for NoPE and ALiBi, respectively). Gated DeltaNet (and two additional SSMs that we include in the appendix, 5

Table 2: OOD accuracy results across 21 regular tasks. All architectures are trained on sequences with lengths 1–40 and evaluated on lengths 41–500. Results show mean ± standard deviation across seeds. ↓ indicates MLP-LDRU performance is statistically significantly better (p < 0.05) than the baseline, while ↑ indicates the baseline is statistically significantly better than MLP-LDRU. Task

RNN

LSTM

Gated DeltaNet TF (ALiBi) TF (∼RoPE) BBT-GRC MLP-LDRU

Even Pairs Modular Arithmetic Parity Check Cycle Navigation

77.4 ± 12.2 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 60.3 ± 2.4↓

52.2 ± 0.8↓ 76.5 ± 3.1↓ 53.4 ± 0.3↓ 25.8 ± 3.8↓

61.1 ± 5.1↓ 54.4 ± 4.5↓ 49.9 ± 0.0↓ 21.6 ± 0.7↓

91.5 ± 7.9 31.4 ± 5.5↓ 49.9 ± 0.0↓ 23.3 ± 1.5↓

100.0 ± 0.0 94.0 ± 3.2 100.0 ± 0.0 100.0 ± 0.1

D2 D3 D4 D6 D8 D12

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 97.7 ± 4.0 95.0 ± 8.7 100.0 ± 0.0 97.1 ± 4.7 98.4 ± 1.6 99.2 ± 1.3 89.0 ± 4.3 92.7 ± 9.5 82.1 ± 1.7↓

100.0 ± 0.0 91.6 ± 14.3 93.1 ± 6.0 75.6 ± 0.6↓ 76.0 ± 1.3↓ 74.6 ± 0.5↓

100.0 ± 0.0 98.3 ± 2.6 96.0 ± 4.7 92.3 ± 6.8 89.7 ± 7.7 84.4 ± 9.6

98.2 ± 1.7 92.5 ± 10.2 97.6 ± 0.4↓ 98.4 ± 1.0 98.7 ± 0.8 98.7 ± 1.0↑

100.0 ± 0.0 100.0 ± 0.0 98.5 ± 2.3 100.0 ± 0.0 84.6 ± 4.6↓ 100.0 ± 0.0 84.7 ± 6.0↓ 98.5 ± 2.4 84.3 ± 8.0 98.1 ± 1.6 90.5 ± 0.7 96.0 ± 2.1

Tomita 3 Tomita 4 Tomita 5 Tomita 6 Tomita 7

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

99.9 ± 0.1 99.1 ± 0.2↓ 75.1 ± 0.4↓ 54.7 ± 0.5↓ 100.0 ± 0.0

100.0 ± 0.0↓ 100.0 ± 0.0 74.3 ± 0.0↓ 50.0 ± 0.0↓ 100.0 ± 0.0

70.7 ± 8.9↓ 85.5 ± 2.1↓ 74.3 ± 0.0↓ 50.0 ± 0.0↓ 100.0 ± 0.0

99.4 ± 0.7 99.4 ± 1.1 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

P1,2 P2,2 P4,2 P1,4 P2,4 P4,4

82.2 ± 3.3↓ 65.4 ± 24.0 99.4 ± 1.0 61.4 ± 15.7 96.9 ± 2.5 85.0 ± 15.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 97.3 ± 2.2

52.4 ± 1.7↓ 22.0 ± 11.9↓ 18.9 ± 1.6↓ 30.1 ± 1.6↓ 21.5 ± 9.5↓ 69.4 ± 6.0↓

56.0 ± 2.3↓ 93.0 ± 5.6 90.0 ± 10.3 40.3 ± 2.4↓ 31.0 ± 8.1↓ 21.3 ± 7.6↓

89.2 ± 12.7 86.4 ± 5.0↓ 58.5 ± 11.1↓ 79.5 ± 7.0↓ 51.6 ± 7.6↓ 58.2 ± 2.7↓

100.0 ± 0.0 99.9 ± 0.1 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

S5 (Smith et al., 2023) and SD-SSM (Terzić et al., 2025a)) never exceeds MLP-LDRU performance on any task. Likewise, MLP-LDRU outperforms RegularGPT and matches or exceeds the capabilities of RNNs (except on D8 ), LSTMs, and BBT-GRC. We compared MLP-LDRU and RNN performance on D8 and determined that the performance gap is not significant. Full results tables are given in Appendix F. Table 3: ListOps test accuracy (%). Left block reports mean accuracy averaged across all reported sequencelength bins. Right block reports long-range accuracy on the longest reported bin (60–80 for (3,9), 101–200 for (3,14), (5,9), and (5,14)). Higher is better. Bins are labeled (x, y) where x is maximum depth and y is maximum arity. Mean Accuracy (%)

Longest Bin (%)

Architecture

(3, 9)

(3, 14)

(5, 9)

(5, 14)

(3, 9)

(3, 14)

(5, 9)

(5, 14)

RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

89.9 84.1 74.7 68.2 65.9 37.3 35.9

79.1 79.1 69.7 63.3 62.7 37.6 25.5

48.1 49.6 45.9 39.0 44.9 29.9 21.5

51.6 53.1 49.0 41.7 48.1 32.5 22.9

79.2 72.5 67.8 55.1 50.0 32.1 9.8

66.4 67.7 65.2 46.4 51.4 31.2 8.4

36.4 39.2 38.8 22.8 36.0 22.7 8.7

38.8 41.4 41.5 25.8 38.9 24.2 8.7

Table 3 presents the results of the RQ1b ListOps experiments on the 1M-size dataset (additional results provided in Appendix F). RIR-GRC and BBT-GRC achieve the highest accuracy across test sequences for all dataset sizes, followed by MLP-LDRU, then transformer (ALiBi) and LSTM, then the other transformers. Notably, under our ListOps experimental setup (train lengths 5-40, Adam optimizer), all models’ accuracy drops on sequences longer than those seen during training. A small hyperparameter sweep on MLP-LDRU 6

revealed that its performance improves when associativity regularization is applied to ⊙θ , i.e., minimizing the cosine distance between (ha ⊙θ hb ) ⊙θ hc and ha ⊙θ (hb ⊙θ hc ), see Appendix H.1 for performance varying the strength of this regularization term, λassoc . This observation indicates that, despite not achieving the highest performance, additional optimizer-level bias toward associativity improves performance. We detail this loss term in Appendix G. We present the results for RQ2 in Fig. 4. The OOD accuracy of both models tends to improve as the maximum training length increases. MLP-LDRU’s performance on D12 is consistent with its performance on the other Dn tasks, whereas the RNN’s performance on D12 indicates that it is highly sensitive to weight initialization. This observation suggests that it may be easier to induce a monoid-like structure rather than a DFA-like structure for complex languages.

OOD Accuracy

MLP-LDRU RNN 1.00 0.95 0.90 0.85

D4

D6

D8

D12

40 60 100 150 Max. Training Length

40 60 100 150 Max. Training Length

40 60 100 150 Max. Training Length

40 60 100 150 Max. Training Length

Figure 4: Trained MLP-LDRUs and RNNs tend to achieve higher OOD accuracy on the Dn tasks as maximum training length increases. We present the results of RQ3 in Table 4. MLP-LDRU achieves 100% OOD accuracy on the four tasks. Of the tasks, Modular Arithmetic appears to have the highest sensitivity to operator choice: with element-wise sum achieving 32.6%, linear operator achieving 60.8%, gated sum achieving 67.1%, and GRC achieving 82.3% OOD accuracy. In contrast, Parity Check and Cycle Navigation maintain 100.0% OOD accuracy across all operators. Even Pairs appears to be a task with intermediate sensitivity, with element-wise sum dropping to 51.9% while the other choices maintain 100.0% OOD accuracy. These results highlight that OOD generalization under the reduction depends considerably on the choice of operator. Table 4: OOD accuracies across different choices of operator.

6

Operator

Even Pairs

Modular Arithmetic

Parity Check

Cycle Navigation

E. Sum Linear G. Sum GRC MLP (ours)

51.9 ± 0.1 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.1 100.0 ± 0.0

32.6 ± 0.3 60.8 ± 1.7 67.1 ± 2.9 82.3 ± 15.3 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

Discussion

Maximum training length is the primary driver of OOD performance for regular tasks. As the maximum training length increases, MLP-LDRU reaches 100% OOD accuracy on D6 by length 60 and 99.9–100.0% on D8 and D12 by length 100 (Fig. 4). The RNN shows a similar trend but with higher variability on D12 (standard deviations 8.2–9.5% up to length 100). These observations are consistent with the positional bias of recurrent networks, where earlier tokens must pass through longer computational paths. Learning D12 requires the model to handle a greater number of possible state runs compared to the other Dn tasks, which may increasingly challenge its capacity for long-term dependencies. We do not claim a definitive causal explanation here, but emphasize MLP-LDRU’s more stable behavior under increased training lengths. 7

Fig. 5 provides insight into why MLP-LDRU does not reach 100.0% OOD accuracy on the Dn languages when trained with insufficient sequence lengths. The heatmaps show the empirical probability of witnessing equivalence class (EC) compositions in the underlying monoid for even-length sequences from D6 . This task provides a useful compromise: it is among the harder cases where models do not immediately generalize, while remaining tractable to visualize. The leftmost heatmap reflects training sequences of length 10–40 and shows that many complex compositions are rarely observed, whereas the rightmost heatmap, taken from the longest OOD sequences we evaluate, displays a denser pattern. This sparsity gap is consistent with the empirical observations provided in Fig. 4, where D6 achieves 98.5% OOD accuracy when trained on sequences up to length 40 but reaches 100% once trained on sequences of length 60 and above. These findings suggest that limited training lengths mean the model is not sufficiently exposed to rare EC compositions, leading to imperfect generalization. We provide further results on the interpretability of sequence embeddings from trained MLP-LDRUs in Appendix I. These results indicate that MLP-LDRU learns to cluster sequence embeddings according to their corresponding ECs in the syntactic monoid, further supporting the hypothesis that MLP-LDRU induces monoid-like structures to achieve length generalization.

10–40

42–60

62–100

102–150

480–500 Log Probabilities

EC

−2 −4 EC

EC

EC

EC

EC

−6

Figure 5: EC composition analysis for the D6 syntactic monoid across different sequence length ranges. Each heatmap shows the log probability of compositions between ECs in the monoid. The sparse composition patterns in shorter sequences (lengths 10–40) explain why training with insufficient length leads to imperfect generalization, as it does not cover all compositions in the longer sequences (lengths 480–500).

On ListOps, the tree-based baselines are superior: BBT-GRC achieves the strongest overall extrapolation across the majority of length/depth/arity buckets. MLP-LDRU nevertheless remains competitive, surpassing LSTM and transformer baselines at 500k and 1M training examples; at 100k, transformer (ALiBi) is slightly stronger. These results suggest that (i) explicit hierarchical inductive bias is valuable for ListOps, and (ii) encouraging approximate associativity remains beneficial outside regular languages. The LDRU’s design reflects two key principles for length generalization. First, the reduction’s structure gives all tokens equal computational depth, mitigating depth-related positional bias. Second, because we reuse an operator biased toward approximate associativity, length generalization reduces to learning the correct composition of pairs of subsequence embeddings. Empirically, however, operator choice is critical for harder tasks. Only MLP-LDRU achieves 100% OOD accuracy on Modular Arithmetic, whereas even strictly associative elementwise-sum fails, suggesting that associativity alone is not sufficient and that there must be some additional consideration to enable consistent generalization. Furthermore, despite the similarity between the GRC and the MLP operator, the GRC is inconsistent across seeds on Modular Arithmetic, indicating that it does not reliably learn approximately associative composition in this setting. Beyond formal languages, Appendix H.2 reports trained-from-scratch NLP classification experiments on GLUE (Wang et al., 2019), AG’s News, and DBPedia (Zhang et al., 2015). These results show that MLP-LDRU remains competitive with similarly trained Transformer baselines, and we leave pretrained and large-scale NLP evaluation to future work. 8

7

Related Work

We position the LDRU within the context of related work. Tree-Based Recursive Neural Networks BBT-RvNNs (Munkhdalai & Yu, 2017; Chowdhury & Caragea, 2023) form a superset of LDRUs, but they differ significantly in their purpose. Typically, RvNNs (Socher et al., 2013; Tai et al., 2015; Yu & Liu, 2018; Shi et al., 2018; Shen et al., 2019) use a recursive cell to process sequences according to a binary tree that is either fixed, heuristically chosen, or induced from a linguistic prior. In contrast, an LDRU is explicitly designed to approximate a compositional algebra. This inductive bias is absent in standard recursive cells, which makes them less suitable for learning stable or repeatable composition rules. More recent works, such as Recursion-in-Recursion (RIR) (Chowdhury & Caragea, 2023), also leverage log-depth recursion to achieve strong length generalization on complex algorithmic tasks, including ListOps. RIR is a framework for trading off speed with RvNN expressivity, via a two-level recursion using an RvNN (inner recursion) within an k-ary tree structure (outer recursion). The LDRU is distinct from these methods because the operators are biased toward learning associative structures. Approximate associativity allows the reduction to behave like a recurrence over the input sequence. This distinction matters for generalization: without an associativity bias, tree cells can learn composition rules that are not recurrence-like, whereas LDRUs are designed so that composing arbitrary subsequences under reduction is as consistent as possible. These algorithmic constraints align with our equivalence class analysis, explaining why MLP-LDRU generalized to D8 and D12 better as the maximum training length was increased. Length Generalization Formal languages are a key test of systematic reasoning and generalization in sequence models (Delétang et al., 2023; Butoi et al., 2025). Classic RNNs and LSTMs tend to show alignment with regular languages (Merrill et al., 2020), but using a state-based inductive bias limits efficient parallelization and introduces challenges with long-range dependencies (Bengio et al., 1993; 1994). Our evaluation of the prefix languages highlights the RNN’s difficulty in modeling long-range dependencies. transformers have well-documented length generalization problems (Anil et al., 2022; Liu et al., 2023; Hahn & Rofin, 2024; Zhou et al., 2024a;b; Huang et al., 2025b;a), and state space models (Gu et al., 2022) exhibit similar limitations (Fan et al., 2024; Sarrof et al., 2024; Terzić et al., 2025a; Grazzi et al., 2025). Furthermore, large-scale empirical studies on state-of-the-art SSMs (Terzić et al., 2025b; Walker et al., 2025) support that SSMs tend not to generalize to regular tasks. Our empirical evaluation also confirms this limitation, with the evaluated SSMs underperforming MLP-LDRU on all 21 regular tasks. Theoretical work has shown that transformers can solve specific regular tasks like Parity Check (Chiang & Cholak, 2022), but they are generally not suited to the structure of finite-state automata (Hahn, 2020). However, recurrent transformers trade parallelism for improved length generalization (Soulos et al., 2024; Fan et al., 2025). Of these architectures, RegularGPT (Chi et al., 2023) represents the closest approach to our work through adaptive weight sharing and sliding-window-dilated attention, which together implement the scan. However, layer norm parameters are not shared between adaptive layers, and empirically, RegularGPT’s performance underperforms MLP-LDRU. Architecture Modifications One line of research toward length generalization explores augmentations to existing architectures for improving length generalization. Approaches for improving generalization in transformers include scratchpad methods (Nye et al., 2022; Kazemnejad et al., 2023) that use intermediate reasoning steps, position coupling (Cho et al., 2024; McLeish et al., 2024; Cho et al., 2025) that assign structure to positional encodings, and modifying positional encodings (Press et al., 2022; Ruoss et al., 2023). In this work, our experiments focus on sequence classification or single-token prediction, where scratchpad methods and position coupling are not directly applicable, as they require autoregressive decoding. Prior evidence on randomized positional encodings shows that such modifications can yield task improvements, but they do not enable reliable generalization across regular tasks (Ruoss et al., 2023), consistent with our evaluation on ∼RoPE. Other work has considered additional loss terms to encourage length generalization (Butoi et al., 2025), observing that, again, its improvements are not robust across all tasks. This contrasts with MLP-LDRU, which achieves reliable generalization across all 21 regular tasks we evaluate. Reduction Applications The reduction (and its more general algorithm, the scan (Blelloch, 1990)) has been used to accelerate existing machine learning methods, including RNNs (Martin & Cundy, 2018) and 9

backpropagation (Wang et al., 2020). More recently, it has been used to more efficiently compute linear state updates in SSMs like S4 (Gu et al., 2022), Mamba (Gu & Dao, 2023), and S5 (Smith et al., 2023). These approaches have enabled fast, state-of-the-art performance in reinforcement learning contexts (Lu et al., 2023). Parallel DeltaNet (Yang et al., 2024) likewise accelerates linear recurrent updates but stays within a linear state-space formulation, and log-linear attention (Guo et al., 2025) achieves logarithmic depth by hierarchically expanding a linear RNN’s state. While BBT-RvNNs fall within the prefix-scannable characterization of Yau et al. (2025), our contribution concerns the design and analysis of a specific type of operator within that framework. Learnable monoids have also been proposed as aggregation functions over nodes in graphs (Ong & Veličković, 2022).

8

Conclusion

In this work, we make four contributions toward understanding length generalization in neural networks. We introduce LDRUs, a family of binary operators biased toward associativity, so that reduction can approximate a sequential recurrence. On 21 regular tasks, MLP-LDRU achieves 100% OOD accuracy on 18 tasks when trained on lengths 1–40, and reaches at least 99.9% on the remaining 3 when increasing the maximum training length. We complement these results with ListOps compositional extrapolation experiments and NLP classification benchmarks to probe behavior beyond regular tasks. We also (i) introduce prefix languages to isolate long-range dependency handling under length extrapolation, (ii) provide an empirical monoid-based analysis connecting MLP-LDRU’s generalization to exposure to equivalence class compositions, and (iii) report initial GPU benchmarks that quantify MLP-LDRU’s practical trade-offs compared to classic RNNs and transformers. Several research directions emerge from our findings. On the theory side, our Dn results suggest that success requires sufficient coverage of equivalence class compositions, but we lack bounds on the minimum training lengths or sample complexity needed to achieve this coverage and a characterization of which compositions matter for a given task family. On the modeling side, an important next step is to adapt associativity-biased reduction to standard autoregressive objectives and test whether the learned composition operator that enables reliable length extrapolation on regular tasks can transfer to next-token prediction. More broadly, while regular languages provide exact verification, it remains to determine how far these ideas extend to richer compositional problems under distribution shift; larger and more diverse evaluations would clarify the scope and limitations of associativity as an inductive bias. Finally, monoid extraction from MLP-LDRU, e.g., identifying equivalence classes from embeddings and estimating the composition table, would provide a useful interpretability test of whether the model has learned the correct monoid structure. Acknowledgments This work was supported by the UK EPSRC grant 2760033. We acknowledge computational resources and support provided by the Imperial College Research Computing Service.

References Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring Length Generalization in Large Language Models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, 2022. D. B. Arnold and M. R. Sleep. Uniform Random Generation of Balanced Parenthesis Strings. ACM Trans. Program. Lang. Syst., 2:122–128, 1980. ISSN 0164-0925. doi: 10.1145/357084.357091. URL https://doi.org/10.1145/357084.357091. Y. Bengio, P. Frasconi, and P. Simard. The Problem of Learning Long-Term Dependencies in Recurrent Networks. In IEEE International Conference on Neural Networks, 1993. doi: 10.1109/ICNN.1993.298725. Y. Bengio, P. Simard, and P. Frasconi. Learning Long-Term Dependencies with Gradient Descent is Difficult. IEEE Transactions on Neural Networks, 5, 1994. doi: 10.1109/72.279181. 10

S. Bhattamishra, Kabir Ahuja, and Navin Goyal. On the Ability and Limitations of Transformers to Recognize Formal Languages. In Conference on Empirical Methods in Natural Language Processing, 2020. URL https://api.semanticscholar.org/CorpusID:222225236. Guy E. Blelloch. Prefix sums and their applications. Technical report, School of Computer Science, Carnegie Mellon University, 1990. James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github.com/jax-ml/jax. Alexandra Butoi, Ghazal Khalighinejad, Anej Svete, Josef Valvoda, Ryan Cotterell, and Brian DuSell. Training Neural Networks as Recognizers of Formal Languages. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=aWLQTbfFgV. Ta-Chung Chi, Ting-Han Fan, Alexander Rudnicky, and Peter Ramadge. Transformer Working Memory Enables Regular Language Reasoning and Natural Language Length Extrapolation. In Findings of the Association for Computational Linguistics: EMNLP 2023. Association for Computational Linguistics, 2023. David Chiang and Peter Cholak. Overcoming a Theoretical Limitation of Self-Attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, 2022. doi: 10.18653/v1/2022.acl-long.527. URL https: //aclanthology.org/2022.acl-long.527/. Hanseul Cho, Jaeyoung Cha, Pranjal Awasthi, Srinadh Bhojanapalli, Anupam Gupta, and Chulhee Yun. Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: //openreview.net/forum?id=5cIRdGM1uG. Hanseul Cho, Jaeyoung Cha, Srinadh Bhojanapalli, and Chulhee Yun. Arithmetic Transformers Can LengthGeneralize in Both Operand Length and Count. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=eIgGesYKLG. Jishnu Ray Chowdhury and Cornelia Caragea. Recursion in Recursion: Two-Level Nested Recursion for Length Generalization with Scalability. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreview.net/forum?id=o6yTKfdnbA. Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio. Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling. In NIPS Deep Learning and Representation Learning Workshop, 2014. DeepMind, Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Antoine Dedieu, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, Iurii Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, George Papamakarios, John Quan, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Laurent Sartran, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Miloš Stanojević, Wojciech Stokowiec, Luyu Wang, Guangyao Zhou, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL http://github.com/google-deepmind. Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural Networks and the Chomsky Hierarchy. In 11th International Conference on Learning Representations, 2023. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. 2018. URL http://arxiv.org/abs/1810.04805. Stefan Elfwing, Eiji Uchibe, and Kenji Doya. Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learning. Neural Networks, 107:3–11, 2018. 11

Jeffrey L. Elman. Finding Structure in Time. Cognitive Science, 14(2):179–211, 1990. Ting-Han Fan, Ta-Chung Chi, and Alexander Rudnicky. Advancing Regular Language Reasoning in Linear Recurrent Neural Networks. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 2: Short Papers), pp. 45–53. Association for Computational Linguistics, 2024. doi: 10.18653/v1/2024.naacl-short.4. URL https://aclanthology.org/2024.naacl-short.4/. Ying Fan, Yilun Du, Kannan Ramchandran, and Kangwook Lee. Looped Transformers for Length Generalization. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=2edigk8yoU. Juan Fdez. del Pozo Romero and Luis F. Lago-Fernández. Gradient-Based Learning of Finite Automata. In Artificial Neural Networks and Machine Learning – ICANN 2023, pp. 294–305, 2023. ISBN 978-3-03144198-1. Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 249–256. PMLR, 2010. URL https://proceedings. mlr.press/v9/glorot10a.html. Riccardo Grazzi, Julien Siems, Jörg K.H. Franke, Arber Zela, Frank Hutter, and Massimiliano Pontil. Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=UvTo3tVBk2. Albert Gu and Tri Dao. Mamba: Linear-Time Sequence Modeling with Selective State Spaces. arXiv preprint arXiv:2312.00752, 2023. Albert Gu, Karan Goel, and Christopher Re. Efficiently Modeling Long Sequences with Structured State Spaces. In International Conference on Learning Representations, 2022. URL https://openreview.net/ forum?id=uYLFoz1vlAC. Han Guo, Songlin Yang, Tarushii Goel, Eric P Xing, Tri Dao, and Yoon Kim. Log-Linear Attention. arXiv preprint arXiv:2506.04761, 2025. Michael Hahn. Theoretical Limitations of Self-Attention in Neural Sequence Models. Transactions of the Association for Computational Linguistics, 8:156–171, 2020. Michael Hahn and Mark Rofin. Why are Sensitive Functions Hard for Transformers? In Proceedings of the 2024 Annual Conference of the Association for Computational Linguistics (ACL 2024), 2024. URL https://arxiv.org/abs/2402.09963. Tom Hennigan, Trevor Cai, Tamara Norman, Lena Martens, and Igor Babuschkin. Haiku: Sonnet for JAX, 2020. URL http://github.com/deepmind/dm-haiku. W. Daniel Hillis and Guy L. Steele. Data parallel algorithms. Commun. ACM, 1986. URL https: //doi.org/10.1145/7902.7903. Sepp Hochreiter and Jürgen Schmidhuber. Long Short-Term Memory. Neural Comput., 9(8), 1997. ISSN 0899-7667. doi: 10.1162/neco.1997.9.8.1735. URL https://doi.org/10.1162/neco.1997.9.8.1735. Markus Holzer and Barbara König. On Deterministic Finite Automata and Syntactic Monoid Size. Theoretical Computer Science, 2004. doi: https://doi.org/10.1016/j.tcs.2004.04.010. Ruiquan Huang, Yingbin Liang, and Jing Yang. How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias. In Forty-second International Conference on Machine Learning, 2025a. URL https://openreview.net/forum?id=yTAR011mOF. 12

Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, and Michael Hahn. A Formal Framework for Understanding Length Generalization in Transformers. In The Thirteenth International Conference on Learning Representations, 2025b. URL https://openreview.net/forum?id=U49N5V51rU. Lawrence Hubert and Phipps Arabie. Comparing Partitions. Journal of Classification, 2:193–218, 1985. ISSN 1432-1343. doi: 10.1007/BF01908075. Rafal Jozefowicz, Wojciech Zaremba, and Ilya Sutskever. An Empirical Exploration of Recurrent Network Architectures. In Proceedings of the 32nd International Conference on Machine Learning. PMLR, 2015. URL https://proceedings.mlr.press/v37/jozefowicz15.html. Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan, Payel Das, and Siva Reddy. The Impact of Positional Encoding on Length Generalization in Transformers. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreview.net/forum?id=Drrl2gcjzl. Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7–9, 2015, Conference Track Proceedings, 2015. Richard E. Ladner and Michael J. Fischer. Parallel Prefix Computation. J. ACM, 27(4):831–838, 1980. doi: 10.1145/322217.322232. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers Learn Shortcuts to Automata. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=De4FYqjFueZ. Chris Lu, Yannick Schroecker, Albert Gu, Emilio Parisotto, Jakob Nicolaus Foerster, Satinder Singh, and Feryal Behbahani. Structured State Space Models for In-Context Reinforcement Learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreview.net/forum?id= 4W9FVg1j6I. Eric Martin and Chris Cundy. Parallelizing Linear Recurrent Neural Nets Over Sequence Length. In International Conference on Learning Representations, 2018. Sean Michael McLeish, Arpit Bansal, Alex Stein, Neel Jain, John Kirchenbauer, Brian R. Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, Jonas Geiping, Avi Schwarzschild, and Tom Goldstein. Transformers Can Do Arithmetic with the Right Embeddings. In The 4th Workshop on Mathematical Reasoning and AI at NeurIPS’24, 2024. URL https://openreview.net/forum?id=cBFsFt1nDW. William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. A Formal Hierarchy of RNN Architectures. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 443–459. Association for Computational Linguistics, 2020. Tsendsuren Munkhdalai and Hong Yu. Neural Tree Indexers for Text Understanding. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pp. 11–21. Association for Computational Linguistics, 2017. URL https://aclanthology. org/E17-1002/. Nikita Nangia and Samuel Bowman. ListOps: A Diagnostic Dataset for Latent Tree Learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pp. 92–99, 2018. Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show Your Work: Scratchpads for Intermediate Computation with Language Models. In Deep Learning for Code Workshop, 2022. URL https://openreview.net/forum?id=HBlx2idbkbq. 13

Euan Ong and Petar Veličković. Learnable Commutative Monoids for Graph Neural Networks. In The First Learning on Graphs Conference, 2022. URL https://openreview.net/forum?id=WtFobB28VDey. Ofir Press, Noah Smith, and Mike Lewis. Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=R8sQPpGCv0. Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the Convergence of Adam and Beyond. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=ryQu7f-RZ. Peter J. Rousseeuw. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20:53–65, 1987. ISSN 0377-0427. doi: https://doi.org/ 10.1016/0377-0427(87)90125-7. Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. Randomized Positional Encodings Boost Length Generalization of Transformers. In 61st Annual Meeting of the Association for Computational Linguistics, 2023. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Yash Sarrof, Yana Veitsman, and Michael Hahn. The Expressive Capacity of State Space Models: A Formal Language Perspective. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=eV5YIrJPdy. Yikang Shen, Shawn Tan, Arian Hosseini, Zhouhan Lin, Alessandro Sordoni, and Aaron C Courville. Ordered Memory. In Advances in Neural Information Processing Systems 32, pp. 5038–5049, 2019. URL http://papers.nips.cc/paper/8748-ordered-memory.pdf. Haoyue Shi, Hao Zhou, Jiaze Chen, and Lei Li. On Tree-Based Neural Sentence Modeling. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 4631–4641. Association for Computational Linguistics, 2018. doi: 10.18653/v1/D18-1492. URL https://aclanthology.org/ D18-1492/. Jimmy T.H. Smith, Andrew Warrington, and Scott Linderman. Simplified State Space Layers for Sequence Modeling. In The Eleventh International Conference on Learning Representations, 2023. URL https: //openreview.net/forum?id=Ai8Hw3AXqks. Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive Deep Models for Semantic Compositionality Over a Sentiment Treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631–1642. Association for Computational Linguistics, 2013. URL https://aclanthology.org/D13-1170/. Paul Soulos, Aleksandar Terzic, Michael Hersche, and Abbas Rahimi. Recurrent Transformers Trade-off Parallelism for Length Generalization on Regular Languages. In The First Workshop on System-2 Reasoning at Scale, NeurIPS’24, 2024. URL https://openreview.net/forum?id=6PjZA4Jvge. Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What Formal Languages Can Transformers Express? A Survey. Transactions of the Association for Computational Linguistics, 12: 543–561, 2024. 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), pp. 1556–1566. Association for Computational Linguistics, 2015. doi: 10.3115/v1/P15-1150. URL https://aclanthology.org/P15-1150/. Aleksandar Terzić, Michael Hersche, Giacomo Camposampiero, Thomas Hofmann, Abu Sebastian, and Abbas Rahimi. On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages. In Proceedings of the AAAI Conference on Artificial Intelligence, 2025a. 14

Aleksandar Terzić, Nicolas Menet, Michael Hersche, Thomas Hofmann, and Abbas Rahimi. Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models. In Advances in Neural Information Processing Systems (NeurIPS), 2025b. Masaru Tomita. Dynamic Construction of Finite Automata From Examples Using Hill-Climbing. In Proceedings of the Fourth Annual Conference of the Cognitive Science Society, 1982. Laurens van der Maaten and Geoffrey Hinton. Visualizing Data using t-SNE. Journal of Machine Learning Research, 9(86):2579–2605, 2008. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural Information Processing Systems, 2017. Benjamin Walker, Lingyi Yang, Nicola Muca Cirone, Cristopher Salvi, and Terry Lyons. Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https://openreview.net/forum?id= HKDyRDzy1E. Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=rJ4km2R5t7. Shang Wang, Yifan Bai, and Gennady Pekhimenko. BPPSA: Scaling Back-propagation by Parallel Scan Algorithm. In Proceedings of Machine Learning and Systems, volume 2, pp. 451–469, 2020. Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing Linear Transformers with the Delta Rule over Sequence Length. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=y8Rm4VNRPH. Songlin Yang, Jan Kautz, and Ali Hatamizadeh. Gated delta networks: Improving mamba2 with delta rule. In The Thirteenth International Conference on Learning Representations, 2025. URL https: //openreview.net/forum?id=r8H7xhYPwz. Morris Yau, Sharut Gupta, Valerie Engelmayer, Kazuki Irie, Stefanie Jegelka, and Jacob Andreas. SequentialParallel Duality in Prefix Scannable Models. arXiv preprint arXiv:2506.10918, 2025. Zeping Yu and Gongshen Liu. Sliced Recurrent Neural Networks. In Proceedings of the 27th International Conference on Computational Linguistics, pp. 2953–2964. Association for Computational Linguistics, 2018. URL https://aclanthology.org/C18-1250/. Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level Convolutional Networks for Text Classification. In Advances in Neural Information Processing Systems, volume 28, 2015. Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Joshua M. Susskind, Samy Bengio, and Preetum Nakkiran. What Algorithms can Transformers Learn? A Study in Length Generalization. In The Twelfth International Conference on Learning Representations, 2024a. URL https://openreview. net/forum?id=AssIuHnmHX. Yongchao Zhou, Uri Alon, Xinyun Chen, Xuezhi Wang, Rishabh Agarwal, and Denny Zhou. Transformers Can Achieve Length Generalization But Not Robustly. In ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2024b. URL https://openreview.net/forum?id=DWkWIh3vFJ.

15

A

Connection to Automata Theory

This section provides the necessary automata theory to discuss the monoid representation of deterministic finite automata, directly motivating our classification of LDRU operators; Sakarovitch (2009) provides a thorough introduction to this area. An alphabet Σ is a finite set of symbols. A sequence is a finite concatenation of symbols from Σ, and Σ∗ denotes the set of all sequences. A language is a subset of Σ∗ . A deterministic finite automaton (DFA) is defined as A = (Q, Σ, δ, qI , F ), where Q is a finite set of states, δ is a transition function δ : Q × Σ → Q, qI ∈ Q is an initial state, and F ⊆ Q is a set of accepting states. δ(q, s) = r denotes a transition from q to r labeled with s. The (Q, Σ, δ) component of a DFA is a semiautomaton. A run is a sequence of states q0 , q1 , . . . , qn where there is a transition between each pair of consecutive states. A sequence is accepted by a DFA if and only if it induces a run from qI to a state in F using δ; otherwise, the sequence is rejected. The language a DFA recognizes is the sequences it accepts, and DFAs are equivalent when they recognize the same language. A DFA is minimal if no equivalent DFA has fewer states. A language is regular when it can be recognized by a DFA (Sakarovitch, 2009). Transduction tasks, like evaluating Modular Arithmetic expressions, require replacing F in the DFA with an output alphabet S and a function mapping states to output symbols g : Q → S. This replacement transforms a DFA into a Moore machine, i.e., (Q, Σ, S, δ, qI , g) (Sakarovitch, 2009). The final state of the run induced by processing a sequence is passed to g to produce that sequence’s output symbol. For consistency, we treat all tasks as transduction tasks by converting recognition tasks into Moore machines with S = {0, 1} and g(q) = 1 if q ∈ F and g(q) = 0 otherwise. A monoid is (M, ⊙, ϵ), where M is a set, ⊙ : M × M → M is an associative binary operator and ϵ is a neutral element for ⊙ (Sakarovitch, 2009). Let A be a DFA that recognizes language L. Every sequence w ∈ Σ∗ induces a function e : Q → Q in A. The transition monoid (E, ⊙, ϵ) of A is the monoid of e functions induced by Σ∗ in A. The monoid operator works by composing two state mappings into a new state mapping. We refer to e functions as equivalence classes (ECs) as there exists a canonical morphism φ : Σ∗ → E (Holzer & König, 2004). We can process a sequence w ∈ Σ∗ by computing φ(w)(qI ) ∈ F . Transition monoids are equivalent representations of semiautomata. The syntactic monoid is the transition monoid of the minimal DFA that recognizes L. It is not practically feasible to process a sequence w ∈ Σ∗ with φ(w) directly as its domain is infinite, but we can derive the sequence’s EC compositionally. We compose ECs of subsequences using ⊙. As ⊙ is associative, any composition order of ECs will result in a correct evaluation of φ(w). For example, let w = w1 . . . wn be a sequence and assume our task is to decide if w is accepted by the regular language L with minimal DFA (Q, Σ, δ, qI , F ) and syntactic monoid (E, ⊙, ϵ). Suppose instead of φ we have φ′ : Σ → E. If we apply φ′ to each wi , then we obtain a sequence of monoid elements φ(w) = φ′ (w1 ) ⊙ · · · ⊙ φ′ (wn ) = e1 ⊙ · · · ⊙ en with ei ∈ E. We can efficiently leverage the associativity to process regular languages using the reduction (Hillis & Steele, 1986). The reduction algorithm takes an associative binary operator ⊙ to reduce a sequence of elements e1 , . . . , en into a single result e1 ⊙ · · · ⊙ en . This result can be computed efficiently using a balanced binary tree (Blelloch, 1990) (see Fig. 2). Processing sequences with the reduction directly motivates the LDRU family: parameterized binary operators that learn to approximate a reduction operator ⊙.

16

B

Prefix Languages Definition

The prefix language, Pp,q , with a prefix length of p over q symbols is a Moore machine defined as:   q p+1 − 1 Pp,q = (Q = 0, 1, 2, . . . , −1 , q−1 Σ = {0, . . . , q − 1} , S = {0, . . . , q p } , δ = δp,q , I = 0, g = gp,q ), o n p p −1 −1 − 1 and i − ( qq−1 − 1) otherwise. The transition function δp,q is where gp,q (i) = 0 when i ∈ 0, . . . , qq−1 o n p −1 − 1 . Otherwise, δ(i, j) = i ∀j ∈ Σ. The output function gp,q δ(i, j) = iq + 1 + j when i ∈ 0, . . . , qq−1 p

−1 ensures that the first qq−1 − 1 states output 0, and the remaining states output their state number minus q p −1 q−1 − 1.

Worked Example To illustrate how to use this definition to construct a prefix language, we consider the case of P4,2 , i.e., the prefix language with a prefix length of 4 over an alphabet of size 2. For these values, we p+1 p −1 calculate the associated p, q based terms for P4,2 : q − 1 = 1, q p = 16, q q−1−1 − 1 = 30 and qq−1 − 1 = 14. To provide clarity on these terms: 1. the first is the maximum integer present in the alphabet, Σ = {0, 1}; 2. the second is the maximum integer present in the output alphabet, S = {0, . . . , 16} (we do not subtract 1 here because 0 is the invalid prefix symbol and the remainder are the possible different prefixes); P4 3. the third is the maximum state, Q = {0, 1, . . . , 30} (for a total of 31 states, i=0 q i = 31); 4. the fourth is the term controlling the output function, ensuring that the output is 0 for the first 15 states and the output is the state number minus 14 for the remaining states. It also controls the transition function, ensuring that the first 15 states can transition to the following states while reading the first p symbols, and defines self-transitions when reading any further symbols. These terms lead us to the Moore machine for P4,2 as follows: P4,2 = (Q = {0, . . . , 30}, Σ = {0, 1}, S = {0, . . . , 16}, δ = δ4,2 , I = 0, g = g4,2 ), where g4,2 (i) = 0 when i ∈ {0, . . . , 14} and i − 14 otherwise (i.e., when i ∈ {15, . . . , 30}). The transition function δ4,2 is defined as δ(i, j) = 2i + 1 + j when i ∈ {0, . . . , 14} and i otherwise. For example, δ4,2 (0, 0) = 1 and δ4,2 (0, 1) = 2. For state 1, δ4,2 (1, 0) = 3 and δ4,2 (1, 1) = 4.

C

MLP-LDRU Details

We provide further details of MLP-LDRU, ⊙θ , as described in the main text. The operator is designed to compute a weighted combination of two input embeddings hi , hj ∈ Rd using a three-layer MLP with gating vectors. We provide reference diagrams in Fig. 6. 17

Embed sequence hj

hi MLP([hi ; hj ])

Apply ⊙θ to non-overlapping consecutive pairs

gj

Residual FFN

gi

Repeat for ⌈log2 n⌉ steps gi ◦ hi

fi = Vi (gi ◦ hi ) + bi

Layer normalization

gj ◦ hj

Dropout

fj = Vj (gj ◦ hj ) + bj

Linear projection

W(fi + fj ) + bout

(a) Implementation of the MLP-LDRU operator showing the (b) Complete MLP-LDRU model processing of an nMLP gating mechanism with element-wise multiplication and length sequence, showing the reduction implementation separate linear projections. with residual connections and normalization.

Figure 6: MLP-LDRU architecture diagrams showing (a) operator implementation, and (b) complete processing pipeline. Residual FFN Within each reduction step, we apply a two-layer feedforward network to the post-⊙θ embeddings and add a residual connection, i.e., h ← h + FFN(h), followed by layer normalization and dropout. The FFN has expansion 4d and output d. We use ReLU activation for regular-language experiments and SiLU activation (Elfwing et al., 2018) for non-regular tasks. This FFN is shared across steps. The MLP used to produce the gating vectors from the concatenated embeddings [hi ; hj ] ∈ R2d is structured as follows. The MLP consists of three linear layers with ReLU activations in between, and it outputs two gating vectors gi , gj ∈ Rd , one for each input embedding. The hidden dimensions of the layers are (2d, 4d, 2d). We expand the MLP function used in Eq. 1 for further clarity. The MLP produces gating vectors given two input embeddings hi , hj ∈ Rd as follows: x = [hi ; hj ] ∈ R2d

(4)

z1 = W1 x + b1 ∈ R

2d

z2 = ReLU(z1 )

(5) (6)

z3 = W2 z2 + b2 ∈ R

(7)

z4 = ReLU(z3 )

(8)

4d

[gi ; gj ] = W3 z4 + b3 ∈ R . 2d

(9)

We initialize the weights of the MLP and linear projections using standard techniques to ensure effective training. The MLP weights are initialized using Glorot normal initialization (Glorot & Bengio, 2010). The projections Vi , Vj and the output projection Wout are initialized to the identity matrix. All biases are initialized to zero, enabling the model to behave as a gated element-wise sum initially.

D

Additional Complexity Analysis

We provide a detailed computational complexity analysis of MLP-LDRU compared to RNNs and transformers. We analyze complexity in terms of: 18

Work complexity Total number of operations required to process a sequence. Depth complexity Longest chain of sequential operations when processing a sequence (determines parallelizability). Memory complexity Total memory required to store parameters and intermediate results for processing a sequence. We consider a sequence of length n and embedding dimension d. MLP-LDRU processes the sequence using n − 1 ⊙θ operations, each requiring O(d2 ) work due to the MLP computation. The total work complexity is therefore O(nd2 ). The reduction processes sequences in exactly ⌈log2 n⌉ steps, giving it depth O(log n) because ⌈log2 n⌉ ≤ log2 (2n) = 1 + log2 (n). The parameters of ⊙θ are O(d2 ), leading to a total memory complexity of O(nd + d2 ) when including the storing of intermediate embeddings. Note that complexities reflect standard implementations; attention variants beyond dot-product attention can improve transformer scaling. Architecture

Work

Depth

Memory

RNN LSTM Transformer MLP-LDRU

O(nd2 ) O(nd2 ) O(n2 d + nd2 ) O(nd2 )

O(n) O(n) O(1) O(log n)

O(d2 ) O(d2 ) 2 O(n + nd + d2 ) O(nd + d2 )

Table 5: Complexity comparison across architectures. We give the experimental setup to benchmark the practical scaling of the RNN, MLP-LDRU, and transformer presented in Fig. 3. We used a batch size of 32, input size of 16, output size of 2 across all models. We set the hyperparameters for each scale to give models similar parameter counts, and we present their configurations with the corresponding number of model parameters in Table 6. We measured the wall-clock time for forward and backward passes across sequence lengths from 4 to 2048 on an NVIDIA RTX 6000 Ada Generation GPU. Runtimes exclude initialization overhead and were measured after warm-up. To obtain stable measurements, we averaged runtimes over 128 passes for each sequence length. Table 6: Model configurations used in the architecture ablation. Hyperparameters were selected to produce approximately matched parameter counts across architectures at each scale. Small Model RNN MLP-LDRU Transformer

E

Medium

Large

Config

Params

Config

Params

Config

Params

d = 400 d = 64 3 layers, d = 64

168k 162k 150k

d = 1024 d = 160 5 layers, d = 128

1.07M 1.01M 991k

d = 1600 d = 256 6 layers, d = 192

1.4M 1.5M 1.6M

Regular Task Experimental Details

This section provides detailed information about the experimental setup, including computing infrastructure, dataset generation procedures, and model hyperparameters to ensure reproducibility. Our codebase is fully implemented in JAX (Bradbury et al., 2018; DeepMind et al., 2020) in Haiku (Hennigan et al., 2020). The experiments were executed across different clusters consisting of NVIDIA RTX 6000 Ada Generation, NVIDIA L40S, and NVIDIA A100 80GB GPUs. Statistical Analysis To assess the statistical significance of performance differences between MLP-LDRU and baseline models across tasks, we performed single t-tests on baselines where MLP-LDRU has 100.0% generalization with zero deviation; otherwise, we conducted a paired t-test comparing the OOD accuracies of both methods. 19

RNN

MLP-LDRU

RNN

Transformer

MLP-LDRU

0 2

2

2

10

2

11

Peak Memory (MB)

2

9

Est. FLOPs

1011 10

9

107 2

2

9

2

2

10

2

11

2 0 2 ·104

2

2

9

2

10

200 100 0

11

2

2

2

3

9

2

2

10

2

1 0 2

Sequence Length

2

9

2

10

2

11

109

2

2

Sequence Length

9

2

2

10

2

0

·104 3

107 2

2

11

1011

2

5

·10 4

Tokens per second

100

4

Transformer

Peak Memory (MB)

200

Est. FLOPs

300

Total Time (ms)

·10 6

Tokens per second

Total Time (ms)

5

211

22 29 210

211

2 1 0

11

Sequence Length

(a) Medium scale

22 29 210

Sequence Length

(b) Large scale

Figure 7: Additional empirical runtime analysis of MLP-LDRU, RNN, and transformer across increased parameter scales. Task Details We present the task details and corresponding automata representations in Table 7 and Table 8. We present all tasks as Moore machines for consistency, as described in the main text. The tasks are selected from Delétang et al. (2023) (the regular tasks) and Bhattamishra et al. (2020), which are well-known benchmarks for evaluating length generalization in sequence processing models. The prefix languages evaluated can be constructed using the definition provided in Appendix B. Sequence Sampling Parity Check sequences are sampled by generating binary sequences uniformly at random of length n and determining the label using the sum of the sequence modulo 2. Likewise, Even Pairs sequences are sampled in the same manner, but the label is determined by counting the number of 01 and 10 pairs in the sequence and checking if their sum is even. Cycle Navigation sequences are sampled with a uniform distribution over the alphabet {−1, 0, 1}, and the label is determined by summing the sequence modulo the cycle length (5). Sampling Modular Arithmetic sequences is different as we always sample valid arithmetic expressions where sequences at even index (so the first token, third token, etc.) are operands ({0, 1, 2, 3, 4}) and sequences at odd index are operators ({+, −, ×}). Determining the label is not as simple as evaluating the expression, as we cannot obey the usual orders of operations (a restriction of regular languages), so we evaluate the expression from left to right, ignoring operator precedence. The label is the result of the expression modulo 5. We sample positive Dn sequences using a modification to the algorithm presented in Arnold & Sleep (1980) that samples balanced parenthesis strings. We constrain the algorithm to obey the fixed depth n and to close brackets at the end of the sequence to return to the initial state, ensuring that it is always a positive sequence. Within the training lengths, we further augment the algorithm with randomness to increase the diversity of the sequences. This randomness is introduced by modifying the probability of closing brackets at each step (when it is possible but not necessary to close a bracket) with noise sampled from N (0, 0.15) and a depth bias that decreases the probability of closing brackets as the depth increases. This ensures that the sequences are still positive while introducing variability. The depth bias is 0.1 × current_depth max_depth . These augmentations only occur within the training lengths, so the test sequences are sampled using the constrained algorithm without randomness. Negative sequences are sampled by generating binary sequences uniformly at random and checking if the sequence is accepted. Therefore, the batches are not guaranteed to be balanced, but it is unlikely to be significantly unbalanced.

20

2/2

3/3

0/0

4/4 4

3 4

0

4/4

2 2

14

3

0/0

2

1×

3

1

3/3

2

4

3

1−

2

0

0+

1

2/2 1

0×

+

1/1

×

3

0

0 −

2/2

0

4

×

− 0

2 2

+

2/2

4−

3

1

0

11

2

0 3

4

1

3 2

0 2 4

3+

4 3 4

4/4

3−

3×

3

1 2

×

4

3/3 2

2+

0 −

3/3

4×

3

3/3

4/4

4

4 1 +

0

+ 1

3

2×

×

0

4+

4 3

−

0−

3

2− 0

0/0

1/1

1

1+

0,1,2,3,4

1/1

4

−

1

0

+

2

×

2

0/0

1

1/1

2/2

1/1 0/0

4/4

Figure 8: Moore machine for evaluating Modular Arithmetic modulo 5 expressions. The automaton’s initial state is 0+. The sequences are constrained to valid arithmetic expressions, and the automaton handles multiplication, addition, and subtraction. Dashed states indicate symbolically linked states (i.e., the inner states) for presentation clarity.

21

Table 7: Descriptions of the Even Pairs, Modular Arithmetic, Parity Check, and Cycle Navigation tasks with diagrams. Task

Description

Automaton 1

0 1 0

Even Pairs

Determine if input sequence has an even number of 01 and 10 pairs.

0

0/ϵ 1

2/1

1/0

0 3/0

4/1 1

Modular Arithmetic (mod 5)

Evaluate the input sequence modulo 5.

1

0

Parity Check

Determine if input sequence has an even number of 1s. State 0 represents even parity, state 1 represents odd parity.

0

Presented separately in Fig. 8 due to its complexity. 0 1 0/1

1/0 1

0

1

Cycle tion

Naviga-

Navigate a cycle of 5 states based on the input sequence.

1

1/1

2/2

−1 0/0

−1 0 −1 0

0

1

−1 −1

3/3

0

1 4/4

1

For the Tomita languages, we explicitly construct their DFAs (Table 8) and simulate their behavior to sample sequences. Again, we sample positive and negative sequences separately, but we oversample sequences when we cannot guarantee the acceptance (or rejection) of the sampled sequences. For Tomita 3, we constrained positive sequence sampling by disallowing the transition from state 3 to state 4, but this does not guarantee acceptance, so we oversampled by a factor of 2. When sampling negative sequences, we sampled symbols uniformly at random and checked if the sequence was accepted by the DFA (oversampling factor 2.5). For Tomita 4, we can guarantee the sampling of positive sequences by disallowing the transition from state 2 to state 3. However, we cannot guarantee the rejection of sequences, so we oversample negative sequences by a factor of 3. For Tomita 5, we oversample positive sequences by a factor of 5 and oversample negative sequences by a factor of 2. For Tomita 6, we oversample positive sequences by a factor of 4 and negative sequences by a factor of 2. For Tomita 7, we are able to guarantee the acceptance of positive sequences, but uniform sampling of the transitions would have caused low diversity in the sequences, so we bias the 4 probabilities of taking transitions. We set the probability of a self-transition to 1 − max(length,16) , where 4 length is the sequence length. The probability to transitioning to the next state to max(length,16) . This ensures that the sequences are still positive while increasing diversity in the sequences. For negative sequences, we oversample by a factor of 5.

22

Table 8: Descriptions of the Dn and Tomita tasks with diagrams. The Tomita languages are originally sourced from Tomita (1982) and their diagrams are adapted from Fdez. del Pozo Romero & Lago-Fernández (2023). All languages in this table are defined over the binary alphabet {0, 1}. Task

Description

Automaton

Dn

Recognize sequences that belong to the regular ex∗ pression (0Dn−1 1)∗ where ∗ D1 = (01) . The diagram recognizes D3 .

0

0

0/1

0

1/0

2/0

1

3/0

1

1

0,1

0 1

Tomita 3

0/1

Recognize sequences where there is no odd-length 0 consecutive subsequence after an odd-length 1 consecutive subsequence.

0

1/1 1

1

3/0

4/0

0

1

0

2/1 0,1

1

Tomita 4

0

Recognize sequences where 000 does not occur

0/1 1

Recognize sequences where there are an even number of 0s and 1s.

0

Recognize sequences where number of 1s − number of 0s mod 3 = 0

0

0

0 1

3/0

2/0

1

1/0 0 0 0

0/1 1 0

Tomita 7

Recognize sequences that belong to the regular expression 0∗ 1∗ 0∗ 1∗ .

0/1

1

2/0 1

1

3/0

1/0

1

1

Tomita 6

0

2/1

1 1

0/1

Tomita 5

0

1/1

1/1

0 0

2/1

0,1

1 1

3/1

0

4/0

Sequences for Pp,q tasks are sampled by generating a sequence of length n with a uniform distribution over the alphabet {0, . . . , q − 1}. The label is determined by mapping the first p symbols to the corresponding output class. Hyperparameters We provide general training hyperparameters in Table 11 and task-specific training hyperparameters in Table 12. Model hyperparameters are detailed in Table 13. The model hyperparameters for the RNN, LSTM, and transformer are the same as in Delétang et al. (2023) to take advantage of their extensive experimentation. However, their training hyperparameters differ from ours as we apply linear-warmup on the learning rate, L2 regularization, and the AMSGrad optimizer instead of Adam. All baseline models were retrained under our optimization setup; we have not reused results from prior work to account for this difference. For RegularGPT hyperparameters, we ran a hyperparameter sweep using the Modular Arithmetic

23

task. We used the range of hyperparameters given in Chi et al. (2023). The hyperparameter grid is shown in Table 9. Tasks that did not converge by 100k steps for any architecture were trained for 1M steps for all architectures. Tasks that were trained for 1M steps were: Modular Arithmetic, D4 , D6 , D8 , and D12 . This allocation reflects the greater complexity of processing the underlying languages compared to simpler languages like the Tomita tasks and prefix languages. For MLP-LDRU, we maintained consistent hyperparameters within task families (e.g., one family is the Dn tasks). We used a lower dropout (0.1) for the Delétang et al. (2023) family compared to the other tasks (0.25) because we hypothesize that the Modular Arithmetic task requires more capacity in ⊙θ than the other tasks. Learning rates were assigned based on preliminary experiments and we typically applied a base learning rate of 1 × 10−3 for tasks on 100k steps and 1 × 10−4 for tasks on 1M steps (the only exceptions were: Modular Arithmetic with a learning rate of 1 × 10−3 and D2 and D3 with a learning rate of 1 × 10−4 to maintain learning rate consistency within task families). This was the case for MLP-LDRU, RNN, LSTM, Gated DeltaNet, transformer, and S5 architectures. However, we applied a learning rate of 1 × 10−4 for all tasks for RegularGPT and SD-SSM because it improved rate of convergence. We used negative eigenvalues for Gated DeltaNet as this empirically and theoretically improves the generalization performance (Grazzi et al., 2025). During these experiments, we noticed that Gated DeltaNet often converged to strong generalization performance but then diverges after training for further steps. We did not apply early stopping to maintain consistency across architectures, but we note that early stopping would likely have improved the results for Gated DeltaNet, including Parity Check where our results report almost random accuracy. Table 9: RegularGPT hyperparameter sweep on Modular Arithmetic task. Grid search over optimizer, learning rate, and dropout probability with fixed architectural parameters. Parameter

Values

Fixed Parameters Embedding dimension Number of heads Chunk size Shared weights Thickness

256 8 2 True 1

Varied Parameters Optimizer Learning rate Dropout probability

Adam, AMSGrad 1 × 10−4 , 3 × 10−4 , 5 × 10−4 0.0, 0.1

Total configurations

12

Table 10: RegularGPT hyperparameter sweep results on Modular Arithmetic task. OOD accuracy for a single seed per configuration. Models trained for 250k steps on sequences up to length 40, evaluated on lengths 41–500. Note: main results use 1M steps. Best configuration highlighted in bold. Optimizer

Learning Rate

Dropout = 0.0

Dropout = 0.1

Adam Adam Adam

−4

1 × 10 3 × 10−4 5 × 10−4

69.8 72.2 49.0

73.2 49.2 61.1

AMSGrad AMSGrad AMSGrad

1 × 10−4 3 × 10−4 5 × 10−4

88.7 68.4 80.8

73.2 78.1 73.4

24

Table 11: General training hyperparameters shared across all experiments. Parameter

Value

Optimizer AMSGrad Base learning rate 1 × 10−3 / 1 × 10−4 (Dn tasks; RegularGPT and SD-SSM) Init learning rate 1 × 10−8 Learning rate schedule Linear warmup (20% of steps) Weight decay 0.0 L2 regularization 5 × 10−4 Gradient clipping 1.0 (global norm) Centralized gradients Yes Batch size 256 Sequence length sampling Uniform between 1 and max length Max training length 40 (standard) / 60, 100, 150 (length experiments) Early stopping None Class balancing Equal positive/negative examples per batch Precision Float32 Seeds 0, 1, 2

Table 12: Task-specific training hyperparameters showing training steps (all architectures) and dropout (MLP-LDRU only). Task

Training Steps

Dropout

1) Delétang et al. (2023) Even Pairs Modular Arithmetic Parity Check Cycle Navigation

100,000 1,000,000 100,000 100,000

0.1 0.1 0.1 0.1

2) Bhattamishra et al. (2020) D2 D3 D4 D6 D8 D12 Tomita 3 Tomita 4 Tomita 5 Tomita 6 Tomita 7

100,000 100,000 1,000,000 1,000,000 1,000,000 1,000,000 100,000 100,000 100,000 100,000 100,000

0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25

3) Prefix languages (Ours) P1,2 P2,2 P4,2 P1,4 P2,4 P4,4

100,000 100,000 100,000 100,000 100,000 100,000

0.25 0.25 0.25 0.25 0.25 0.25

25

Model Architecture Hyperparameters We present the model hyperparameters for all baseline models and MLP-LDRU in Table 13. Table 13: Model architecture hyperparameters for all baseline models and MLP-LDRU. Note that while dropout can be applied to RegularGPT, the hyperparameter sweep indicated that zero dropout is better for Modular Arithmetic, so we did not use it. Total parameters rounded to 2 significant figures. Component

Parameter

RNN

LSTM

Gated DeltaNet

Transformer

S5

SD-SSM

RegularGPT

BBT-GRC

MLP-LDRU

Embedding

Embedding dim Initialization

None –

None –

None –

64 N (0, 0.02)

None –

None –

256 N (0, 0.02)

64 N (0, 1)

64 N (0, 0.02)

Core Architecture

Layers/Blocks Hidden dim

1 256

1 256

3 64

5 64

2 256

1 256

1 256

1 96

1 64

Residual Connections

Dimension

–

–

128

256

–

–

1024

–

256

Normalization

Layer norm

No

No

Pre-norm

Pre-norm & Post-norm

Post-norm

Post-norm

Pre-norm & Post-norm

Post-norm

Post-norm

MLP-LDRU

MLP hidden dims Activation MLP initialization Projection initialization

– – – –

– – – –

– – – –

– – – –

– – – –

– – – –

– – – –

128 → 64 → 256 GELU & Sigmoid – –

128 → 256 → 128 ReLU Glorot (Glorot & Bengio, 2010) Identity

Gated DeltaNet

Negative eigs.

–

–

Yes

–

–

–

–

–

–

S5

Size base Num blocks Activation fn Mode Clipped eigs. Discretization

– – – – – –

– – – – – –

– – – – – –

– – – – – –

256 8 GELU Mean pooling Yes ZOH

– – – – – –

– – – – – –

– – – – – –

– – – – – –

SD-SSM

Transition matrices Lp norm

– –

– –

– –

– –

– –

8 1.2

– –

– –

– –

Transformer

Attention heads Head dimension Positional encoding

– – –

– – –

4 12 None

8 8 Varies

– – –

– – –

8 32 None

– – –

– – –

RegularGPT

Chunk size Shared weights Dilated attention

– – –

– – –

– – –

– – –

– – –

– – –

2 Yes Yes

– – –

– – –

Total Parameters

Approx.

67k

270k

230k

250k

270k

530k

3200k

240k

160k

Different Operator Choices Here we describe the different reduction operators we evaluate. We have described the MLP-LDRU operator in the main text and Appendix C. Let hi , hj be the embeddings of the two input tokens. We also evaluate the following operators: Element-wise Sum (Elem. Sum) The element-wise sum of the two embeddings, hi + hj . Linear A linear projection of the concatenated embeddings, i.e, W([hi ; hj ]) + b, where W is a learned weight matrix and b is a learned bias vector. Gated Sum A gated sum of the two embeddings. We determine the gates using a linear projection of the concatenated embeddings, i.e., g = σ(Wg ([hi ; hj ]) + bg ), where σ is the sigmoid activation function. The output is then g ◦ hi + (1 − g) ◦ hj . Gated Recursive Cell Shen et al. (2019) Given in Eq. 12 and 13 of Shen et al. (2019), this operator uses gating mechanisms similar to MLP-LDRU to produce an embedding from two adjacent input embeddings. The most significant difference between GRC and MLP-LDRU is that there is nonassociativity bias due to the term σ(cit ) ⊙ uit in Eq. 13, where cit and uit are both computed by applying a feedforward network on [hi ; hj ]. E.1

Optimizer Ablation

Experimental Setup We use the Modular Arithmetic task to compare the OOD performance of MLP-LDRU when training with the Adam and AMSGrad optimizers with and without dropout. The experiments were conducted with fixed hyperparameters (except for the optimizer algorithm and dropout rate) found in Table 11 and Table 13. We train the models for 1M steps on sequences up to length 40 and evaluate them on sequences of lengths 41–500. The results are averaged over 10 seeds. Results We present the results of this ablation in Table 14 and Fig. 9. With both optimizers, dropout improves generalization, as the models trained without dropout (both Adam and AMSGrad) perform worse on the OOD test set. Adam without dropout demonstrated catastrophic forgetting on seed 9, indicating that it is more unstable compared to AMSGrad. AMSGrad with dropout achieves the best performance, indicating robustness when handling the Modular Arithmetic task. 26

Table 14: OOD accuracies when training MLP-LDRU with different optimizers and dropout combinations on the Modular Arithmetic task. Individual seed results with mean and standard deviation across 10 seeds. The results demonstrate that dropout is necessary for generalization, with AMSGrad showing superior performance when combined with dropout. We note that the AMSGrad optimizer without dropout achieves competitive OOD accuracy compared to the optimizers with dropout. Seed 0 1 2 3 4 5 6 7 8 9 Mean ± Std

(Adam, 0.0)

(Adam, 0.1)

(AMSGrad, 0.0)

(AMSGrad, 0.1)

99.606 99.691 99.888 99.684 99.113 95.143 99.966 98.689 99.925 40.231

99.963 99.980 99.986 99.959 99.990 99.993 99.997 99.997 99.868 99.976

99.963 99.949 99.888 99.946 99.963 99.898 99.868 99.963 99.983 99.864

100.000 99.997 100.000 100.000 99.997 99.997 99.986 100.000 99.993 100.000

93.194 ± 17.707

99.971 ± 0.037

99.928 ± 0.042

99.997 ± 0.004

While the experiment was training, we evaluated a validation batch of 1024 sequences of length 500 every 1000 steps: the performance on this batch is how we determined the validation loss (Val. Loss) and accuracy (Val. Acc.) presented in Fig. 9. This evaluation gave us an idea of how the model would perform on the most OOD sequences during training, and we found it to be a reliable indicator of the model’s generalization across all the sequences up to length 500. The test accuracy (Test Acc.) is the performance on the test set of sampled 512 sequences per length, from 1 to 500. The ∆Log Loss is the difference between the log of the validation loss and the log of the training loss, which indicates how well the model generalizes to OOD sequences and overfits to the training sequences. We also note that the validation loss is evaluated on the model parameters without dropout, while the training loss includes dropout. The ∆Log Loss reveals an interesting difference between AMSGrad with and without dropout: with dropout indicates improving performance on the validation set during training, while without dropout indicates that the model overfits to the training sequences without improving on the validation set.

F

All Regular Task Results

All Baselines We present the OOD accuracies of all baseline models on all tasks in Table 15 under the experimental settings for RQ1 (main text). The difference between Table 15 and Table 2 is that the former includes all baselines, while the latter does not include S5 and SD-SSM. We use the same statistical significance notation as in Table 2. In addition, we present the ID accuracies of all models in Table 16. Individual Seed Results for Main Tasks We present the OOD accuracies for individual seeds for all 21 regular language tasks in Table 17. The models were trained on sequences up to length 40 and evaluated on sequences of lengths 41–500. Extended Sequence Length Results We present the individual seed results for the sequence length experiments on Dn languages in Table 18. The models were trained on sequences up to length x ∈ [40, 60, 100, 150] and evaluated on sequences of length from x + 1 to 500. Operator Choice Results We present the individual seed results for the RQ3 experiments in Table 19. The models were trained on sequences up to length 40 and evaluated on sequences of lengths 41–500. The results show that the MLP operator achieves 100.0% OOD accuracy on all tasks. The other operators show varying performance—but none achieve 100.0% OOD accuracy on Modular Arithmetic.

27

(Adam, 0.1)

(AMSGrad, 0.0) Training Acc. (%)

Training Loss

(Adam, 0.0) 100

10−5 0

0.2

0.4 0.6 Step

0.8

1 ·10

∆ Log Loss

Val. Acc. (%) 0

0.2

0.4 0.6 Step

0.8

·10

0 −5 0.4 0.6 Step

0.8

0

0.2

1 ·106

0.4 0.6 Step

0.8

0.4 0.6 Step

0.8

1 ·106

1 0.5 0

5

0.2

0.6

6

10

0

0.8

1

Test Acc. (%)

Val. Loss

10−4 10−9

1

6

101

(AMSGrad, 0.1)

0.2

1 ·106

1.000 0.995 0.990 0.950 0.900

0

100 200 300 400 Sequence Length

500

Figure 9: Optimizer ablation study comparing Adam and AMSGrad performance on MLP-LDRU models. Standard deviations are shown as the filled area around the mean values. The experiments show that dropout is necessary to enable generalization outside of the training distribution. It is notable that the AMSGrad optimizer without dropout achieves the lowest cross-entropy training loss but has worse performance outside the training distribution. Note the broken axis on the y-axis for the test accuracy (Test Acc.) plot to better highlight the performance differences between the highly performing models.

28

Table 15: OOD accuracy results across 21 regular tasks. All models are trained on sequences with lengths 1–40 and evaluated on lengths 41–500. Results show mean ± standard deviation across seeds. A ↓ indicates MLP-LDRU performance is statistically significantly better (p < 0.05) than the baseline, while a ↑ indicates the baseline is statistically significantly better than MLP-LDRU. Task

RNN

LSTM

Gated DeltaNet

TF (NoPE)

TF (ALiBi)

TF (∼RoPE)

S5

1) Delétang et al. (2023) Even Pairs Modular Arithmetic Parity Check Cycle Navigation

77.4 ± 12.2 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 60.3 ± 2.4↓

↓

52.2 ± 0.8 76.5 ± 3.1↓ 53.4 ± 0.3↓ 25.8 ± 3.8↓

↓

50.3 ± 0.0 76.0 ± 0.0↓ 50.1 ± 0.0↓ 20.0 ± 0.0↓

↓

RegularGPT

BBT-GRC

MLP-LDRU

91.5 ± 7.9 31.4 ± 5.5↓ 49.9 ± 0.0↓ 23.3 ± 1.5↓

↓

61.1 ± 5.1 54.4 ± 4.5↓ 49.9 ± 0.0↓ 21.6 ± 0.7↓

2) Bhattamishra et al. (2020) D2 D3 D4 D6 D8 D12 Tomita 3 Tomita 4 Tomita 5 Tomita 6 Tomita 7

100.0 ± 0.0 100.0 ± 0.0 95.0 ± 8.7 97.1 ± 4.7 99.2 ± 1.3 92.7 ± 9.5 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 97.7 ± 4.0 100.0 ± 0.0 98.4 ± 1.6 89.0 ± 4.3 82.1 ± 1.7↓ 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 91.6 ± 14.3 93.1 ± 6.0 75.6 ± 0.6↓ 76.0 ± 1.3↓ 74.6 ± 0.5↓ 99.9 ± 0.1 99.1 ± 0.2↓ 75.1 ± 0.4↓ 54.7 ± 0.5↓ 100.0 ± 0.0

100.0 ± 0.0↓ 99.9 ± 0.0↓ 99.5 ± 0.0↓ 96.5 ± 0.0 89.0 ± 0.2↓ 81.3 ± 0.3↓ 98.7 ± 0.0↓ 96.1 ± 0.0↓ 74.3 ± 0.0↓ 50.2 ± 0.0↓ 100.0 ± 0.0

3) Prefix languages (Ours) P1,2 P2,2 P4,2 P1,4 P2,4 P4,4

82.2 ± 3.3↓ 65.4 ± 24.0 99.4 ± 1.0 61.4 ± 15.7 96.9 ± 2.5 85.0 ± 15.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 97.3 ± 2.2

52.4 ± 1.7↓ 22.0 ± 11.9↓ 18.9 ± 1.6↓ 30.1 ± 1.6↓ 21.5 ± 9.5↓ 69.4 ± 6.0↓

50.3 ± 0.0↓ 25.2 ± 0.0↓ 6.3 ± 0.0↓ 25.2 ± 0.0↓ 6.3 ± 0.0↓ 0.4 ± 0.0↓

SD-SSM

53.9 ± 0.8 47.6 ± 6.7↓ 50.1 ± 0.1↓ 22.9 ± 0.7↓

↓

65.7 ± 0.8 99.9 ± 0.0↓ 71.4 ± 1.4↓ 44.2 ± 0.8↓

↓

91.9 ± 0.7 99.1 ± 1.3 99.8 ± 0.7 99.9 ± 0.2

100.0 ± 0.0 94.0 ± 3.2 100.0 ± 0.0 100.0 ± 0.1

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 98.3 ± 2.6 96.0 ± 4.7 92.3 ± 6.8 89.7 ± 7.7 84.4 ± 9.6 100.0 ± 0.0↓ 100.0 ± 0.0 74.3 ± 0.0↓ 50.0 ± 0.0↓ 100.0 ± 0.0

98.2 ± 1.7 92.5 ± 10.2 97.6 ± 0.4↓ 98.4 ± 1.0 98.7 ± 0.8 98.7 ± 1.0↑ 70.7 ± 8.9↓ 85.5 ± 2.1↓ 74.3 ± 0.0↓ 50.0 ± 0.0↓ 100.0 ± 0.0

88.4 ± 10.3 83.6 ± 9.3 81.7 ± 10.3 75.0 ± 1.5↓ 73.7 ± 0.5↓ 73.5 ± 0.3↓ 72.8 ± 1.6↓ 72.3 ± 12.8 65.8 ± 3.2↓ 49.9 ± 0.1↓ 98.7 ± 2.2

100.0 ± 0.0 96.3 ± 3.9 97.3 ± 2.3 92.2 ± 4.3 87.2 ± 2.9 72.9 ± 4.3↓ 100.0 ± 0.0 100.0 ± 0.0 81.1 ± 1.8↓ 85.6 ± 3.7↓ 100.0 ± 0.0

93.7 ± 5.5 87.6 ± 4.6↓ 94.1 ± 4.7 87.9 ± 3.7↓ 91.0 ± 2.8↓ 89.8 ± 4.1↓ 93.7 ± 3.3 98.4 ± 1.5 97.7 ± 2.2 92.2 ± 4.7 100.0 ± 0.0

100.0 ± 0.0 98.5 ± 2.3 84.6 ± 4.6↓ 84.7 ± 6.0↓ 84.3 ± 8.0 90.5 ± 0.7 99.4 ± 0.7 99.4 ± 1.1 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 98.5 ± 2.4 98.1 ± 1.6 96.0 ± 2.1 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

56.0 ± 2.3↓ 93.0 ± 5.6 90.0 ± 10.3 40.3 ± 2.4↓ 31.0 ± 8.1↓ 21.3 ± 7.6↓

89.2 ± 12.7 86.4 ± 5.0↓ 58.5 ± 11.1↓ 79.5 ± 7.0↓ 51.6 ± 7.6↓ 58.2 ± 2.7↓

52.9 ± 2.8↓ 29.3 ± 1.8↓ 12.1 ± 2.1↓ 31.8 ± 3.6↓ 14.4 ± 1.3↓ 8.0 ± 3.4↓

61.8 ± 3.5↓ 34.0 ± 1.6↓ 99.8 ± 0.2 38.7 ± 0.5↓ 30.2 ± 4.9↓ 42.9 ± 2.5↓

100.0 ± 0.0 99.6 ± 0.3 91.5 ± 2.1↓ 100.0 ± 0.0 99.7 ± 0.2 95.3 ± 0.6↓

100.0 ± 0.0 99.9 ± 0.1 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

Table 16: ID accuracies across 21 regular tasks. All models are trained on sequences with lengths 1–40 and evaluated on lengths 41–500. Results show mean ± standard deviation across seeds. Task

RNN

LSTM

Gated DeltaNet

TF (NoPE)

TF (ALiBi)

TF (∼RoPE)

S5

SD-SSM

RegularGPT

BBT-GRC

MLP-LDRU

1) Delétang et al. (2023) Even∼Pairs Modular∼Arithmetic Parity∼Check Cycle∼Navigation

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 85.4 ± 2.6 100.0 ± 0.0 99.3 ± 0.4

90.1 ± 0.0 94.9 ± 0.0 90.1 ± 0.0 84.8 ± 0.1

100.0 ± 0.0 86.3 ± 1.0 51.9 ± 0.3 84.7 ± 7.1

99.4 ± 0.9 75.7 ± 5.3 56.6 ± 1.2 89.7 ± 5.2

100.0 ± 0.0 67.6 ± 0.7 99.1 ± 0.1 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 99.9 ± 0.1 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

2) Bhattamishra et al. (2020) D2 D3 D4 D6 D8 D12 Tomita∼3 Tomita∼4 Tomita∼5 Tomita∼6 Tomita∼7

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 93.8 ± 10.6 98.4 ± 2.6 98.7 ± 0.5 99.4 ± 0.8 96.7 ± 4.8 99.2 ± 1.4 100.0 ± 0.0 100.0 ± 0.0 99.9 ± 0.1 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 99.9 ± 0.0 99.3 ± 0.0 98.9 ± 0.0 98.7 ± 0.0 99.8 ± 0.0 99.7 ± 0.0 93.4 ± 0.0 89.7 ± 0.1 100.0 ± 0.0

98.7 ± 1.9 99.2 ± 1.0 99.8 ± 0.0 99.8 ± 0.1 99.8 ± 0.0 99.6 ± 0.3 99.1 ± 0.0 98.9 ± 0.1 74.2 ± 0.0 51.3 ± 0.0 99.0 ± 0.3

98.7 ± 0.4 99.1 ± 0.6 99.6 ± 0.0 99.8 ± 0.1 99.8 ± 0.1 99.9 ± 0.0 96.8 ± 0.6 98.7 ± 0.1 74.2 ± 0.0 51.3 ± 0.0 99.9 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 97.9 ± 2.0 93.5 ± 10.5 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 99.9 ± 0.0 99.9 ± 0.0 99.9 ± 0.0 99.9 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

3) Prefix languages (Ours) P1,2 P2,2 P4,2 P1,4 P2,4 P4,2 P4,4

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

98.8 ± 1.3 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

90.1 ± 0.0 85.0 ± 0.0 81.3 ± 0.0 85.0 ± 0.0 81.2 ± 0.0 81.3 ± 0.0 78.4 ± 0.1

99.9 ± 0.1 97.4 ± 0.1 99.3 ± 0.1 99.8 ± 0.1 98.3 ± 0.3 99.3 ± 0.1 99.0 ± 0.3

98.8 ± 2.1 96.2 ± 1.1 97.5 ± 0.9 99.9 ± 0.1 97.4 ± 0.1 97.5 ± 0.9 98.8 ± 0.3

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

Table 17: Individual seed results for all 21 regular language tasks. Models trained on sequences up to length 40, evaluated on lengths 41–500. RNN Task

LSTM

Gated DeltaNet

TF (NoPE)

TF (ALiBi)

TF (∼RoPE)

S5

SD-SSM

RegularGPT

BBT-GRC

MLP-LDRU

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

1) Delétang et al. (2023) Even Pairs Modular Arithmetic Parity Check Cycle Navigation

82.4 100.0 100.0 100.0

86.3 100.0 100.0 100.0

63.4 100.0 100.0 100.0

100.0 100.0 100.0 62.1

100.0 100.0 100.0 57.5

100.0 100.0 100.0 61.2

51.7 78.9 53.5 29.8

53.1 73.0 53.1 25.6

51.8 77.6 53.8 22.1

50.3 76.0 50.0 20.0

50.3 76.0 50.1 20.0

50.3 76.0 50.1 20.0

66.0 55.4 49.9 20.8

55.9 58.3 49.9 22.0

61.5 49.5 49.9 21.9

95.0 33.3 49.9 21.6

82.4 35.8 49.9 24.0

97.0 25.2 49.9 24.3

53.9 51.5 50.0 22.1

53.2 51.4 50.2 23.6

54.7 39.9 50.1 23.0

66.5 99.9 69.8 45.0

65.7 99.9 72.3 44.3

64.8 99.9 71.9 43.4

92.2 97.5 99.4 99.9

91.1 99.9 100.0 100.0

92.2 99.8 100.0 99.7

100.0 97.2 100.0 100.0

100.0 90.9 100.0 99.9

100.0 94.0 100.0 100.0

100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

2) Bhattamishra et al. (2020) D2 D3 D4 D6 D8 D12 Tomita 3 Tomita 4 Tomita 5 Tomita 6 Tomita 7

100.0 100.0 85.0 91.6 100.0 96.9 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 99.6 97.7 81.8 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0 99.9 99.3 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0 85.4 80.2 100.0 100.0 100.0 100.0 100.0

100.0 93.2 100.0 98.5 93.8 82.6 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 96.8 87.8 83.4 100.0 100.0 100.0 100.0 100.0

100.0 99.8 87.9 75.2 77.4 75.0 100.0 99.2 75.6 55.0 100.0

100.0 99.9 91.9 76.3 75.4 74.0 99.8 99.3 74.9 54.1 100.0

100.0 75.1 99.6 75.3 75.0 74.7 99.9 98.8 74.8 54.9 100.0

100.0 99.9 99.5 96.6 89.0 81.1 98.7 96.1 74.3 50.2 100.0

100.0 99.9 99.5 96.6 89.3 81.3 98.7 96.1 74.3 50.2 100.0

100.0 99.9 99.5 96.5 88.8 81.6 98.7 96.1 74.3 50.2 100.0

100.0 95.3 100.0 93.1 97.6 95.3 100.0 100.0 74.3 50.0 100.0

100.0 100.0 90.7 85.1 89.4 77.6 100.0 100.0 74.3 50.0 100.0

100.0 99.5 97.2 98.7 82.1 80.2 100.0 100.0 74.3 50.0 100.0

99.5 98.3 97.4 98.7 99.3 99.3 68.6 83.1 74.3 50.0 100.0

96.3 98.5 97.4 97.2 97.7 99.3 80.5 86.5 74.3 50.0 100.0

98.8 80.8 98.1 99.1 99.0 97.6 63.1 86.8 74.3 50.0 100.0

85.0 79.4 75.5 73.7 74.2 73.9 74.3 58.5 63.0 50.0 96.2

100.0 94.3 93.6 76.6 73.2 73.4 71.0 83.7 65.3 50.0 100.0

80.2 77.2 76.1 74.7 73.6 73.3 73.1 74.8 69.2 49.7 100.0

100.0 100.0 100.0 97.1 84.5 77.7 100.0 100.0 82.7 82.6 100.0

100.0 96.8 96.3 89.4 86.6 69.4 100.0 100.0 81.4 84.6 100.0

100.0 92.1 95.7 90.2 90.4 71.6 100.0 100.0 79.2 89.7 100.0

100.0 92.7 89.1 90.7 93.6 93.5 96.8 96.7 99.5 93.2 100.0

89.7 83.7 94.6 83.7 88.1 90.5 94.2 98.9 98.2 87.1 100.0

91.5 86.4 98.5 89.3 91.4 85.3 90.2 99.6 95.3 96.4 100.0

100.0 99.8 87.1 91.5 93.5 90.3 99.6 98.1 100.0 100.0 100.0

100.0 95.9 87.4 80.5 79.5 90.0 98.7 100.0 100.0 100.0 100.0

100.0 99.9 79.2 82.0 79.9 91.2 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 99.9 99.8 97.5 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 95.7 98.2 96.8 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 99.9 96.6 93.6 100.0 100.0 100.0 100.0 100.0

3) Prefix languages (Ours) P1,2 P2,2 P4,2 P1,4 P2,4 P4,4

78.4 43.4 100.0 78.4 94.1 68.0

84.3 61.8 100.0 57.0 97.7 90.0

84.0 91.0 98.2 47.8 98.9 96.8

100.0 100.0 100.0 100.0 100.0 98.4

100.0 100.0 100.0 100.0 100.0 94.7

100.0 100.0 100.0 100.0 100.0 98.8

54.4 28.1 18.0 28.9 12.2 66.6

51.7 29.6 18.1 32.0 31.2 65.3

51.2 8.3 20.8 29.5 21.2 76.2

50.3 25.2 6.3 25.2 6.3 0.4

50.3 25.2 6.3 25.2 6.3 0.4

50.3 25.2 6.3 25.2 6.3 0.4

58.7 86.5 78.0 38.8 27.9 30.1

54.2 97.0 96.2 39.0 40.2 17.4

55.2 95.5 95.6 43.1 24.8 16.5

97.8 87.1 62.0 86.8 59.9 60.0

95.1 91.0 67.5 72.9 49.7 59.4

74.6 81.2 46.0 78.9 45.1 55.1

56.1 30.6 14.5 28.6 15.5 5.8

50.6 27.2 11.2 35.7 13.0 11.9

52.1 30.0 10.6 31.1 14.7 6.2

65.8 32.2 99.9 38.3 27.6 43.3

60.2 34.7 99.5 39.3 27.0 40.2

59.4 35.2 100.0 38.5 35.9 45.2

100.0 99.3 93.0 100.0 99.5 95.1

100.0 99.8 89.1 100.0 99.7 95.9

100.0 99.9 92.4 100.0 99.8 94.8

100.0 99.8 100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0 100.0 100.0

29

Table 18: Individual seed results for sequence length experiments on Dn languages. RNN Task

Max Length

D4

MLP-LDRU

0

1

2

0

1

2

40 60 100 150

85.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

D6

40 60 100 150

91.6 99.9 100.0 100.0

99.6 98.8 100.0 100.0

100.0 99.9 100.0 100.0

99.9 100.0 100.0 100.0

95.7 100.0 100.0 100.0

99.9 100.0 100.0 100.0

D8

40 60 100 150

100.0 99.9 100.0 100.0

97.7 100.0 100.0 100.0

99.9 100.0 100.0 100.0

99.8 98.8 100.0 100.0

98.2 91.5 100.0 100.0

96.6 99.9 100.0 100.0

D12

40 60 100 150

96.9 81.8 91.3 99.4

81.8 82.1 77.8 99.5

99.3 98.1 92.6 100.0

97.5 96.1 99.9 99.9

96.8 98.2 99.9 99.9

93.6 96.5 99.9 99.9

Table 19: Individual seed results for operator study on the regular Delétang et al. (2023) tasks. All models were trained with a max sequence length of 40. MLP Task Even Pairs Modular Arith. Parity Check Cycle Nav.

GRC

Elem. Sum

Concat. Proj.

Gated Sum

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

100.0 100.0 100.0 100.0

99.9 99.6 100.0 100.0

100.0 76.5 100.0 100.0

100.0 70.7 100.0 100.0

51.9 32.4 100.0 100.0

51.8 32.6 100.0 100.0

51.9 32.9 100.0 100.0

100.0 59.4 100.0 100.0

100.0 60.3 100.0 100.0

100.0 62.7 100.0 100.0

100.0 68.7 100.0 100.0

100.0 68.8 100.0 100.0

100.0 63.7 100.0 100.0

30

!htbp Table 20: MLP-LDRU size ablation results on the regular Delétang et al. (2023) tasks. All models were trained with a max sequence length of 40 and evaluated on sequences of lengths 41–500. The results show that MLP-LDRU can learn to solve all four tasks with embedding dimensions as low as 64, while dimensions of 32 and 16 show some performance degradation on Modular Arithmetic. Embedding Dim.

Even Pairs

Modular Arithmetic

Parity Check

Cycle Navigation

16 32 64 128

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

50.2 ± 5.7 96.9 ± 4.7 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0 100.0 ± 0.0

MLP-LDRU Size Ablation To address whether MLP-LDRU’s regular-task performance depends on a tuned hidden dimension, we vary the embedding dimension on the four Delétang et al. (2023) tasks used in the operator study. Table 20 shows that dimensions 64 and 128 solve all four tasks, while dimension 32 nearly solves Modular Arithmetic and dimension 16 fails only on Modular Arithmetic.

G

Associativity Regularization

Our results on the regular tasks indicate that MLP-LDRU can learn to approximate an associative operator without explicit regularization. However, we hypothesize that adding an associativity regularization term to the training loss could further improve the model’s ability to learn an associative operator, especially in lowdata regimes or on non-regular tasks. Associativity encourages the operator to behave as a recurrence, which we believe is beneficial for generalization. To test this hypothesis, we added an associativity regularization term to the training loss during experiments on the ListOps experiments and the natural language tasks described in Appendix H. We compute this additional loss term by taking every locally valid triple (ha , hb , hc ) computed during the forward pass of an LDRU model’s reduction and punish deviations from associativity. Let ⊙θ denote a general LDRU operator. For each step k in the reduction, we partition the sequence of token embeddings into these triples and we evaluate the following expressions: x = ⊙θ (⊙θ (ha , hb ), hc ); y = ⊙θ (ha , ⊙θ (hb , hc )),

(10)

which enables us to compute the associativity loss as: ℓassoc (x, y) = (1 −

x·y )2 . |x||y| + ϵ

Let τk be the set of valid triples evaluated at step k. The associativity loss for step k is: X 1 L(k) ℓassoc (x, y), assoc = |τk |

(11)

(12)

(ha ,hb ,hc )∈τk

and the total associativity loss across all reduction steps is: K

Lassoc =

1 X (k) Lassoc . K

(13)

k=1

This loss term is then added to the standard training loss with a weighting factor λassoc : L = Ltask + λassoc Lassoc .

H

(14)

Non-Regular Language Experiments

We restrict our extended study to sequence classifications to maintain consistency with our regular language experiments. We provide additional details about the ListOps and natural language tasks below. 31

H.1

ListOps

We generated a dataset of ListOps sequences following the procedure outlined in Nangia & Bowman (2018). Each sequence is a list beginning with an operation (MAX, MIN, MED, SUM (modulo 10)) followed by either integer or nested list arguments. The sequences are generated with varying lengths, maximum depths, and maximum numbers of arguments per operation. We created training datasets of sizes 100k, 500k, and 1M sequences, containing sequences with lengths ranging from 5 to 40. The test data comprises of multiple sets where each set contains 10k sequences sampled ith different characteristics of length (bucketed), max depth and max number of arguments. This enables a comprehensive evaluation of length, depth and argument generalization of the trained models. We performed hyperparameter sweeps for each of the baseline models and MLP-LDRU on the ListOps task, except for RIR-GRC and BBT-GRC, where we used the default hyperparameters given in the codebase of Chowdhury & Caragea (2023). For RIR-GRC, we additionally reduced the model chunk size from 30 to 12 to account for a lower maximum training sequence length compared to the original experiments. This change maintains the ratio of max training length to chunk size as 0.3 to ensure that RIR-GRC can take advantage of the outer recursion. The hyperparameter sweeps included learning rate, dropout probability, and model hidden dimension, and in the case of MLP-LDRU: the weight of the associativity regularization. We used a single seed (1) for this sweep and we used the Adam (Kingma & Ba, 2015) optimizer with a batch size of 128. We continued to use linear warmup for 20% of the training steps initially set to 1e-8 but no L2 regularization was used. We trained each configuration for 200k steps on the 500k dataset and evaluated performance on a validation set of 2048 sequences sampled from the same distribution. We selected the best hyperparameters based on the highest average accuracy on the validation data. The final hyperparameters used for each model are presented in Table 22. Table 21: Hyperparameter sweep ranges for LSTM, transformer, and MLP-LDRU for ListOps. Model

Embedding / Hidden Dim

Dropout

Learning Rate

Associativity Regularization

{256, 512, 1024} {64, 128} {64, 128, 256} {256, 512}

– {0, 0.1} {0, 0.1, 0.2} {0.025, 0.05, 0.1}

{1e-5, 5e-5, 1e-4} {1e-5, 5e-5, 1e-4} {1e-5, 5e-5, 1e-4} {1e-4, 2.5e-4, 5e-4}

– – {0, 0.1, 1.0} {1.0}

LSTM Transformer MLP-LDRU MLP-LDRU (additional)

Table 22: Selected model hyperparameters for all baseline models, BBT–GRC, and MLP-LDRU for ListOps. Component

Parameter

LSTM

Transformer

MLP-LDRU

BBT-GRC

RIR-GRC

Embedding

Embedding dim Initialization

None –

128 N (0, 0.02)

256 N (0, 0.02)

128 –

128 –

Core Architecture

Layers/Blocks Hidden dim

1 1024

5 128

1 256

1 128

1 128

Residual Connections

Dimension

–

512

1024

–

–

Normalization

Layer norm

No

Pre-norm & Post-norm

Post-norm

Post-norm

Post-norm

MLP-LDRU

MLP hidden dims Activation MLP initialization Projection initialization

– – – –

– – – –

512 → 1024 → 512 SiLU Glorot Identity

– – – –

– – – –

Transformer

Attention heads Head dimension Positional encoding

– – –

8 8 ALiBi/NoPE/Sinusoidal

– – –

– – –

– – –

RIR-GRC

Chunk size

–

–

–

–

12

Regularization

Dropout locations Associativity

– –

Attention & Residual –

Post-norm Yes

In & Out –

In & Out –

Total Parameters

Approx.

4.3M

1.0M

2.6M

430k

430k

32

Table 23: Summary of ListOps ablation on associativity regularization strength. Left block reports validation accuracy; middle block reports mean accuracy averaged across all reported sequence-length bins, and right block reports long-range accuracy on the longest reported bin (60–80 for (3,9), 101–200 for [3,14], (5,9), and (5,14)). Higher is better. Bins are labeled (x, y) where x is maximum depth and y is maximum arity. ∗ indicates that the strength was not included in the original hyperparameter sweep and was added to provide a more complete picture of the relationship between associativity strength and performance. Val. Acc.

Mean Accuracy

Longest Bin

Assoc. Strength

(3, 9)

(3, 9)

(3, 14)

(5, 9)

(5, 14)

(3, 9)

(3, 14)

(5, 9)

(5, 14)

0.00 0.10 0.25∗ 0.50∗ 1.00 2.00∗ 5.00∗

84.0 83.7 89.0 84.6 88.7 84.2 89.3

65.5 65.3 75.7 66.4 76.6 67.1 76.7

63.8 63.8 70.3 64.8 71.0 64.9 70.8

44.3 44.1 46.8 44.5 47.1 44.6 47.1

47.7 47.2 49.6 47.5 50.4 47.9 50.2

56.8 57.8 68.1 59.1 69.1 58.5 69.3

58.8 59.6 65.0 59.6 65.3 59.1 65.3

39.0 39.0 38.6 39.3 38.6 38.6 38.7

41.7 42.1 41.0 41.1 41.2 41.6 41.4

Results We report an ablation of associativity strength on the performance of MLP-LDRU in Table 23. Aside for λassoc , we use the same settings as the initial hyperparameter sweep. These results indicate that further biases toward associativity is beneficial for performance on the ListOps task. We present the full results for the ListOps ablation study across all length buckets, max depth, and max number of arguments in Table 24. The results show that MLP-LDRU with associativity regularization achieves the highest accuracy across most buckets and dataset sizes, particularly in the out-of-distribution buckets. The performance of MLP-LDRU improves with increased training data, and it consistently outperforms the standard baselines at 500k and 1M training samples. These findings suggest that encouraging approximate associativity through regularization is a useful inductive bias for improving generalization on the ListOps task. The tables presented in Table 25 report accuracy and standard deviation for length buckets with four combinations of max depth and max number of arguments under three training-set sizes. BBT-GRC largely attains the highest accuracy across buckets and all dataset sizes. Increasing the training-set size systematically improves MLP-LDRU accuracy: the 500k and 1M models show uniform gains relative to the 100k model across both in-distribution and out-of-distribution buckets. Under the same change in training-set size, transformer with ALiBi exhibits smaller improvements. MLP-LDRU surpasses the standard baselines (LSTM, transformer) at 500k and 1M. A consistent pattern across all sweeps was that MLP-LDRU configurations with non-zero associativity regularization achieved higher validation accuracy than those without it, indicating that encouraging approximate associativity is empirically beneficial and functions as a useful inductive bias rather than a redundant constraint. H.2

Natural Language Tasks

We evaluate MLP-LDRU and transformer baselines on a set of standard sequence-classification datasets. We report results on all GLUE classification tasks except RTE, AX, and WNLI, which we exclude due to their small size, high variance, and limited incremental diagnostic value relative to the larger, more stable benchmarks. We also report results on AG’s News and DBPedia, text classification tasks outside of GLUE. We report performance on the validation data for the GLUE tasks (using the recommended metrics for each individual task) and accuracy on test data for the additional datasets. We use the BERT base (uncased) (Devlin et al., 2018) tokenizer for all tasks. For paired inputs u,v, the concatenation format was the conventional [CLS],u,[SEP],v,[SEP]. Task performance is reported in Table 26. We present the truncation lengths, learning rates, batch sizes, and training steps for each task in Table 27. We performed a hyperparameter sweep to find the best configurations for transformer baselines (using ALiBi) and MLP-LDRU. We used the AG’s News task to conduct the sweep, varying learning rate, dropout

33

Table 24: Full results of ListOps ablation on associativity regularization strength. Each row represents a different associativity regularization strength and entries indicate the corresponding accuracy. Higher is better. ∗ indicates that the strength was not included in the original hyperparameter sweep and was added to provide a more complete picture of the relationship between associativity strength and performance. Assoc. Str.

Sequence length 5–20

21–40

41–60

61–80

81–100

101–200

56.8 57.8 68.1 59.1 69.1 58.5 69.3

– – – – – – –

– – – – – – –

61.1 61.1 66.8 62.8 68.1 61.6 67.5

55.6 56.7 58.6 57.9 59.7 57.3 58.5

58.8 59.6 65.0 59.6 65.3 59.1 65.3

37.5 37.7 37.1 38.0 37.6 37.4 37.2

36.0 35.8 35.9 36.2 36.4 36.0 35.7

39.0 39.0 38.6 39.3 38.6 38.6 38.7

40.2 39.8 39.6 40.5 40.9 40.7 40.1

38.9 38.5 38.1 38.8 38.8 38.5 38.4

41.7 42.1 41.0 41.1 41.2 41.6 41.4

Max Depth: 3; Max Arguments: 9 0.0 0.1 0.25∗ 0.5∗ 1.0 2.0∗ 5.0∗

72.3 71.0 88.3 73.1 88.6 76.6 89.3

72.6 71.7 79.6 72.9 81.1 73.0 80.7

60.2 60.7 66.8 60.6 67.5 60.4 67.6

Max Depth: 3; Max Arguments: 14 0.0 0.1 0.25∗ 0.5∗ 1.0 2.0∗ 5.0∗

72.0 71.0 87.1 73.0 88.0 75.6 88.9

73.1 71.5 77.7 72.4 78.4 73.2 78.2

62.4 62.7 66.7 62.9 66.2 62.5 66.4

Max Depth: 5; Max Arguments: 9 0.0 0.1 0.25∗ 0.5∗ 1.0 2.0∗ 5.0∗

72.5 71.5 88.5 73.7 89.3 75.4 90.0

42.4 42.2 42.3 42.2 42.7 42.4 42.5

38.4 38.5 38.2 37.7 37.9 37.9 38.3

Max Depth: 5; Max Arguments: 14 0.0 0.1 0.25∗ 0.5∗ 1.0 2.0∗ 5.0∗

74.9 73.9 90.3 75.5 91.7 78.1 92.2

49.1 48.3 48.6 48.7 49.5 48.4 48.5

41.1 40.3 40.2 40.2 40.2 40.0 40.5

probability, and embedding/hidden dimension. For MLP-LDRU we additionally swept the associativityregularization weight. We used linear warmup over the first 20% of updates (initial learning rate 10−8 ), and no L2 regularization. We give the sweep parameters and embolden the selected parameters in Table 28. Additional model details for MLP-LDRU and transformer are listed in Table 29. Results The full results are shown in Table 30. Performance differences between MLP-LDRU and transformer baselines are largely moderate across all GLUE tasks, with each architecture exhibiting strengths on different subsets of benchmarks. On QQP and MNLI (matched and mismatched), MLP-LDRU achieves the highest average scores across seeds. On CoLA, SST-2, and MRPC, the transformer (Sinusoidal) obtains the strongest results. Transformer (NoPE) obtains the strongest results on QNLI. On the non-GLUE classification tasks, AG’s News and DBPedia, the MLP-LDRU obtains the lowest accuracy on AG’s News, but is similar to transformer performance in absolute terms. The MLP-LDRU also achieves the highest accuracy on DBPedia

34

Table 25: ListOps results across different training dataset sizes. Each table presents accuracies (in %) and standard deviations across 3 seeds for different length buckets under varying max depth and max number of arguments. MLP-LDRU benefits from increased training data, outperforming standard baselines at 500k and 1M training samples. 100k dataset Architecture

500k dataset Architecture

Sequence length 5–20

21–40

41–60

61–80

81–100

89.2±0.6 68.5±0.4 63.6±1.5 65.3±0.8 57.8±1.2 40.9±0.3 30.6±4.0

65.1±1.0 58.7±0.4 56.7±0.4 58.6±0.7 55.2±1.2 23.3±0.3 57.4±0.7

60.0±0.3 55.5±0.3 53.0±0.5 55.1±0.6 46.9±1.0 19.1±0.7 15.3±1.1

RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

56.8±0.5 52.4±0.6 51.1±0.4 51.3±0.5 42.4±0.6 18.2±0.9 12.8±0.9

– – – – – – –

– – – – – – –

61.3±0.4 59.7±0.7 57.1±0.3 57.9±0.8 50.5±1.0 22.5±0.3 16.1±1.4

60.2±0.2 58.3±0.3 55.8±0.6 56.6±0.8 46.8±1.0 20.7±0.6 13.5±1.3

58.2±0.3 57.5±0.1 54.2±0.6 55.0±1.2 43.8±1.5 19.5±0.4 11.9±0.6

57.5±0.3 56.0±0.5 54.6±0.5 51.9±1.9 39.1±4.1 17.4±1.9 8.8±2.7

86.5±0.7 69.6±0.5 64.1±1.5 66.0±0.7 57.7±1.4 43.1±0.2 30.8±4.7

65.3±0.5 61.7±0.3 59.9±0.2 60.3±0.7 57.2±1.0 26.9±0.3 58.8±0.5

40.2±0.6 41.3±0.4 38.2±0.3 34.8±1.1 34.6±0.6 15.8±0.8 13.3±0.7

39.2±0.2 40.7±0.4 37.6±0.3 34.3±1.1 33.8±0.9 15.0±1.4 11.7±0.8

37.8±0.4 39.3±0.2 36.5±0.3 33.1±1.2 31.2±1.2 14.1±0.9 11.0±0.5

39.4±0.3 40.6±0.2 38.9±0.3 33.5±0.6 27.2±2.2 12.7±1.0 8.8±0.9

90.5±0.2 73.4±0.4 68.2±1.9 71.1±1.0 63.0±1.2 51.9±0.6 35.4±5.8

45.2±0.6 45.7±0.4 41.4±0.6 39.2±1.1 40.0±0.7 19.0±0.6 43.4±0.5

41.9±0.4 43.9±0.3 40.1±0.3 36.5±1.7 35.9±0.9 16.3±0.8 12.2±0.7

40.9±0.4 42.5±0.5 39.3±0.3 35.5±1.5 34.4±1.5 15.6±0.6 11.3±0.6

41.9±0.5 43.8±0.3 41.8±0.3 36.0±1.1 30.4±2.2 14.1±0.6 9.2±1.8

93.1±0.3 75.9±0.3 71.1±2.4 74.0±1.2 65.3±1.6 56.8±0.5 36.4±7.1

49.7±0.4 50.4±0.3 46.3±0.5 44.4±0.4 43.6±0.7 21.1±0.5 46.8±0.3

Architecture 81–100

101–200

98.7±1.2 97.2±0.4 80.0±3.6 70.1±0.9 71.6±1.8 48.3±0.2 34.1±8.2

RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

96.7±1.3 97.2±0.5 79.6±4.0 70.1±0.6 71.1±2.0 50.6±0.2 35.8±8.0

42.1±0.5 44.0±0.3 40.1±0.4 36.9±1.0 36.4±0.6 16.8±0.5 13.5±0.8

RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

94.6±0.9 93.7±0.2 80.9±4.3 71.5±0.5 75.9±2.6 59.1±0.1 46.4±11.4

RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

96.9±1.0 96.9±0.3 83.6±4.7 72.9±0.8 78.0±2.8 64.2±0.3 49.1±12.9

92.3±3.3 89.4±1.0 75.1±2.3 84.5±3.4 76.6±2.7 35.3±0.2 90.0±2.9 86.4±2.7 88.7±1.0 74.6±2.8 80.8±4.6 75.7±1.8 38.7±0.2 78.7±3.1

21–40

83.6±2.5 80.6±1.2 62.5±2.2 61.7±1.3 55.9±0.8 31.5±0.2 11.1±0.6

74.6±2.2 72.7±0.8 61.1±2.6 54.6±1.3 48.2±0.8 31.9±0.3 9.7±0.9

– – – – – – –

– – – – – – –

77.1±2.0 80.9±1.6 64.4±1.6 64.1±1.1 59.3±0.9 35.1±0.2 10.9±1.2

69.9±1.6 74.8±1.3 63.4±1.4 58.8±1.9 53.6±1.5 34.5±0.5 9.7±1.3

65.1±2.8 71.3±1.4 57.3±1.0 55.5±2.6 51.3±1.9 33.4±0.8 9.2±1.7

62.1±3.1 67.9±0.8 61.3±2.3 44.6±9.6 49.2±2.6 32.1±1.3 8.2±1.5

39.5±0.4 40.9±0.3 38.3±0.5 33.7±1.0 37.2±0.2 23.4±0.2 10.7±0.9

38.1±1.0 40.2±0.2 37.6±0.6 31.4±1.7 37.0±0.4 23.5±0.1 10.1±0.9

36.3±1.2 38.8±0.2 35.9±0.5 29.4±2.6 35.7±0.5 22.2±0.1 9.6±0.8

36.0±2.4 39.9±0.5 38.6±0.4 21.7±6.5 35.3±1.1 22.0±0.3 8.6±0.8

41.4±0.5 43.5±0.4 40.4±0.5 34.0±1.8 38.9±0.4 24.3±0.2 10.3±0.6

40.4±0.7 42.5±0.2 40.3±0.5 32.4±2.8 38.8±0.3 24.6±0.2 9.8±1.3

39.1±1.4 41.8±0.3 38.7±0.7 31.1±3.3 39.0±0.4 24.2±0.4 9.8±1.3

36.8±2.9 42.6±1.1 41.6±0.3 23.6±6.5 38.3±1.3 23.9±0.6 8.5±0.7

RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

99.2±0.2 96.0±2.0 82.9±9.6 70.5±1.1 74.4±2.4 49.5±0.3 33.3±7.7

94.3±0.8 88.0±3.5 81.9±2.0 85.1±4.8 79.3±2.9 35.6±0.3 89.6±5.3

41–60

61–80

81–100

101–200

86.9±1.4 80.0±3.1 66.1±1.5 62.2±0.6 59.8±0.8 32.1±0.4 10.8±0.5

79.2±3.0 72.5±2.5 67.8±3.6 55.1±0.8 50.0±1.1 32.1±0.4 9.8±0.6

– – – – – – –

– – – – – – –

79.6±2.1 79.2±1.4 66.1±0.7 65.1±0.8 62.7±1.7 35.5±0.3 10.8±1.0

73.7±1.8 74.0±1.1 66.8±1.5 59.6±2.0 56.5±5.0 34.4±0.3 9.8±1.8

69.1±2.0 70.6±0.6 58.6±0.5 56.8±1.5 52.6±4.1 33.3±0.4 9.4±1.6

66.4±2.3 67.7±0.9 65.2±1.4 46.4±5.1 51.4±6.2 31.2±0.9 8.4±1.6

38.6±1.7 40.8±0.5 38.0±0.5 34.3±1.5 38.1±0.4 23.7±0.1 11.1±0.6

37.3±1.9 39.7±0.3 37.3±0.4 33.0±1.4 37.2±0.6 23.6±0.1 9.7±1.0

35.8±2.0 38.5±0.2 35.9±0.3 31.2±1.9 35.8±0.7 22.7±0.1 9.5±0.9

36.4±2.8 39.2±0.6 38.8±0.3 22.8±5.8 36.0±0.5 22.7±0.4 8.7±0.6

40.8±1.4 43.1±0.3 40.0±0.4 35.2±1.7 39.9±0.5 24.8±0.1 10.5±0.6

40.0±1.7 42.4±0.3 40.1±0.6 33.9±2.2 39.0±0.6 24.9±0.1 10.0±1.2

39.4±1.6 41.2±0.4 38.4±0.5 32.7±1.9 38.7±0.7 24.7±0.3 9.8±1.3

38.8±2.3 41.4±1.2 41.5±0.6 25.8±6.4 38.9±0.6 24.2±0.5 8.7±0.9

Max Depth: 3; Max Arguments: 14 RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

97.5±0.8 96.0±1.8 82.2±9.2 70.2±0.9 74.4±3.1 51.6±0.3 34.6±7.7

88.5±1.8 86.9±2.1 79.4±1.2 81.4±4.9 78.7±1.5 39.3±0.3 80.0±2.8

Max Depth: 5; Max Arguments: 9

46.8±1.0 46.7±0.3 42.5±0.4 41.2±2.0 42.6±0.4 26.1±0.2 45.3±0.8 54.3±1.5 54.1±0.7 48.9±0.6 48.8±2.3 49.2±0.7 30.3±0.3 51.8±1.7

Sequence length 5–20

Max Depth: 3; Max Arguments: 9

RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

Max Depth: 5; Max Arguments: 14

Max Depth: 5; Max Arguments: 14 RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

61–80

Max Depth: 5; Max Arguments: 9

Max Depth: 5; Max Arguments: 9 RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

41–60

Max Depth: 3; Max Arguments: 14

Max Depth: 3; Max Arguments: 14 RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

21–40

Max Depth: 3; Max Arguments: 9

Max Depth: 3; Max Arguments: 9 RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

Sequence length 5–20

101–200

1M dataset

94.8±0.2 93.1±0.8 82.6±10.2 71.4±0.9 78.5±3.2 60.4±0.3 44.9±9.7

45.5±2.3 46.5±0.7 42.8±0.2 41.4±2.0 43.8±0.4 26.3±0.1 45.2±1.0

Max Depth: 5; Max Arguments: 14 RIR-GRC BBT-GRC MLP-LDRU TF (ALiBi) LSTM TF (NoPE) TF (Sin.)

97.3±0.2 96.5±0.6 84.8±10.5 73.1±1.1 81.1±3.5 65.5±0.6 46.9±10.7

53.1±1.8 53.7±0.4 49.3±0.3 49.3±2.3 50.8±0.3 30.8±0.1 51.8±2.2

Table 26: Performance across GLUE benchmarks and two additional text classification datasets. Metrics follow GLUE conventions: CoLA (Matthew’s Correlation Coefficient), SST-2 / MNLI / QNLI (%, accuracy), QQP / MRPC (%, F1/accuracy). Subscript M indicates matched and MM mismatched accuracy for MNLI. AG’s News and DBPedia report classification accuracy on test data. Values are means across 5 seeds. GLUE Benchmarks

Additional Tasks

Architecture

CoLA

SST-2

MRPC

QQP

MNLIM

MNLIMM

QNLI

AG’s News

DBPedia

TF (ALiBi) TF (Sin.) TF (NoPE) MLP-LDRU

0.096 0.124 0.097 0.085

79.3 81.1 79.1 80.9

56.2/62.6 59.1/67.5 59.0/64.0 57.0/63.2

74.0/78.3 70.7/75.8 72.8/77.8 76.9/79.1

53.9 49.0 50.5 58.3

52.8 50.5 51.1 57.9

58.1 56.9 58.8 56.1

89.8 89.1 89.6 89.0

98.2 97.8 97.8 98.6

Table 27: Sequence-length truncation thresholds, learning rates, batch sizes, and training steps for all evaluated NLP datasets. Dataset

Truncation Length

Learning Rate

Batch Size

Steps

CoLA SST-2 MRPC QQP MNLI QNLI AG’s News DBPedia

64 64 128 256 384 384 512 256

1e-5 1e-4 1e-5 1e-4 1e-4 1e-4 1e-4 1e-4

128 128 32 32 32 32 32 32

4000 8000 4000 50000 35000 20000 20000 30000

(98.6%), exceeding all transformer variants. Variances across seeds are generally low for all models and tasks. Overall, these results indicate that MLP-LDRU is competitive with standard transformer architectures on natural language classification tasks, despite the fact that natural language is not a regular language.

35

Table 28: Hyperparameter sweep ranges for all models on natural language tasks. We used ALiBi as the PE for the hyperparameter sweep. Model

Embedding Dim

Dropout

Learning Rate

Weight Decay

Assoc. Reg.

{64, 128} {256} {64, 128, 256} {256}

{0, 0.1} {0.1} {0, 0.01, 0.025, 0.05} {0.01}

{1e-5, 5e-5, 1e-4} {1e-5} {1e-5, 5e-5, 1e-4} {1e-5, 5e-5}

{0.0, 1e-4, 1e-5} {1e-5} {0.0, 1e-4, 1e-5} {0.0, 1e-4, 1e-5}

– – {0, 0.1, 1.0} {0.5}

Transformer Transformer (Additional) MLP-LDRU MLP-LDRU (Additional)

Table 29: Model hyperparameters for all natural language tasks. We note that the hyperparameter values were selected based on a hyperparameter sweep on AG’s News: the selected values are emboldened in Table 28. The sweep included a transformer with approximately 12M parameters (embedding dimension 256), but this configuration was not selected as it did not outperform the smaller transformer presented here. Component

Parameter

Transformer

MLP-LDRU

Embedding

Embedding dim Initialization

128 N (0, 0.02)

256 N (0, 0.02)

Core

Layers/Blocks Hidden dim

5 128

1 256

Attention

Heads Head dim Positional encoding

8 16 ALiBi/NoPE/Sinusoidal

– – –

MLP-LDRU

MLP hidden dims Activation Assoc. Reg.

– – –

512 → 1024 → 512 SiLU Yes

Regularization

Dropout

0.1

0.01

Total Parameters

Approx.

4.9M

10M

36

Across the sweep on AG’s News, MLP-LDRU configurations with non-zero associativity regularization consistently outperformed those with zero weight, and the selected configuration for every dataset used λassoc = 0.1. This result indicates that encouraging approximate associativity is beneficial outside of regular-language settings as well. Table 30: Performance across GLUE benchmarks, AG’s News, and DBPedia. Metrics follow GLUE conventions: CoLA (Matthew’s Correlation Coefficient), SST-2 / MNLI / QNLI (Accuracy), MRPC / QQP (F1/Accuracy). AG’s News and DBPedia report classification accuracy on test data. We give the metrics and their standard deviations over 5 seeds. Subscript M indicates matched and MM mismatched accuracy for MNLI. GLUE Benchmarks

Additional Tasks

Architecture

CoLA

SST-2

MRPC

QQP

MNLIM

MNLIMM

QNLI

AG’s News

DBPedia

TF (ALiBi) TF (Sin.) TF (NoPE) MLP-LDRU

0.096 ± 0.031 0.124 ± 0.027 0.097 ± 0.028 0.085 ± 0.036

79.3 ± 1.0 81.1 ± 0.9 79.1 ± 1.2 80.9 ± 1.0

56.2 ± 1.8 / 62.6 ± 2.9 59.1 ± 1.4 / 67.5 ± 3.6 59.0 ± 1.6 / 64.0 ± 2.4 57.0 ± 3.6 / 63.2 ± 5.7

74.0 ± 1.9 / 78.3 ± 0.9 70.7 ± 0.7 / 75.8 ± 0.2 72.8 ± 1.6 / 77.8 ± 0.8 76.9 ± 0.3 / 79.1 ± 0.3

53.9 ± 0.7 49.0 ± 0.3 50.5 ± 0.4 58.3 ± 0.7

52.8 ± 0.7 50.5 ± 0.5 51.1 ± 0.6 57.9 ± 0.7

58.1 ± 0.2 56.9 ± 3.3 58.8 ± 0.9 56.1 ± 1.2

89.8 ± 0.4 89.1 ± 0.9 89.6 ± 0.3 89.0 ± 0.5

98.2 ± 0.1 97.8 ± 0.1 97.8 ± 0.1 98.6 ± 0.0

I

Interpretability Analysis

We analyze the embedding space of D6 to examine if MLP-LDRU’s representation is monoid-like. In Fig. 10a, we visualize the embeddings of all sequences up to length 12 using t-SNE (van der Maaten & Hinton, 2008). The upper and lower plots show embeddings of MLP-LDRU trained up to lengths 40 and 150, respectively. The embeddings display clustering into ECs, supporting our expectation that the MLP-LDRU’s induced representation aligns with monoid structures. If MLP-LDRU had learned to behave as a DFA, we would expect fewer clusters (8 states) compared to the syntactic monoid (141 classes). Max. Len. 40

50

Adj. Rand Index

Component 2

Max. Len. 40

0

-50

0.36 0.34 135

50

Silhouette Score

Component 2

Max. Len. 150

0

-50 −50 0 50 Component 1

Max. Len. 150

140

145

150

140 145 Number of Clusters

150

0.5 0.49 0.48 0.47

135

(a) t-SNE plot of D6 embeddings colored by EC, showing (b) Clustering analysis of D6 embeddings. The model distinct clusters learned by MLP-LDRU. with higher maximum training length displays improved alignment with the monoid structure, shown by higher ARI (top) and Silhouette Score peak (bottom).

Figure 10: Interpretability analysis of MLP-LDRU embeddings for D6 . We further analyze the embeddings using k-means clustering, varying k around 141, the number of ECs in the D6 syntactic monoid. We report the Adjusted Rand Index (ARI; Hubert & Arabie, 1985) and Silhouette Score (Rousseeuw, 1987) in Fig. 10b. The ARI measures the similarity between fitted clusters and the true ECs, while the Silhouette Score quantifies the separation between clusters. The length 150 model attains a higher ARI than the length 40 model, indicating improved alignment with ECs. The Silhouette Score peaks at k = 141 for the length 150 model, consistent with clustering at the expected granularity of the monoid. In contrast, the length 40 model has no clear peak, reflecting weaker alignment to the monoid. 37

J

Analysis of Monoid Compositions

This section describes how we computed the equivalence class composition patterns shown in Fig. 5 from the main text and further explains why training sequence length directly impacts generalization performance on Dn languages. Fig. 5 presents the composition patterns for D6 over varying training and test lengths. To illustrate the explicit structure of monoids for the Dn languages, we present the complete monoid table for D2 in Table 31, which recognizes the language (0(01)∗ 1)∗ . We present D2 because it has 15 equivalence classes, and D6 is significantly more complex with 141 classes. In general, the monoid of Dn has 1 + (n+1)(n+2)(2n+3) 6 equivalence classes. The complete D2 automaton has three states: state 0 (initial/accepting), state 1 (after reading ‘0’), state 2 (the bottom of the fixed stack), and state 3 (rejecting sink state). However, we focus on the equivalence classes that can be components of positive examples to reduce the complexity compared to modeling all compositions of possible subsequences in Dn . This restricts the equivalence classes that we examine to those that contain even-length sequences because of the balanced nature of Dn . Despite only considering a subset of equivalence classes (73 for D6 ), there can still be many classes, so we focus on the D6 language instead of D8 or D12 for tractability and simpler visualizations. We sample sequences of varying lengths in the same fashion as our experimental setup, but restrict the sampling to only positive sequences. We model the equivalence classes produced by a balanced reduction using a monoid composition table. To ensure a balanced distribution of equivalence classes for each length bucket, we target ≈1M equivalence classes for each heatmap in Fig. 5. We enforce this by tracking the total number of classes observed during reduction and scaling the number of sampled sequences accordingly. Table 31: Monoid elements for D2 . Each equivalence class is characterized by its state mapping function and representative sequences. All other sequences in Σ∗ can be characterized as one of these equivalence classes. A representative sequence is shown in the third column, and the description of each class is provided in the fourth column. The symbol ϵ denotes the empty sequence. Element

State Mapping

Representative

Description

e0 e1 e2

{0 7→ 0, 1 7→ 1, 2 7→ 2, 3 7→ 3} {0 7→ 1, 1 7→ 2, 2 7→ 3, 3 7→ 3} {0 7→ 3, 1 7→ 0, 2 7→ 1, 3 7→ 3}

ϵ 0 1

Identity Stack push Stack pop

e3 e4 e5 e6

{0 7→ 2, 1 7→ 3, 2 7→ 3, 3 7→ 3} {0 7→ 0, 1 7→ 1, 2 7→ 3, 3 7→ 3} {0 7→ 3, 1 7→ 1, 2 7→ 2, 3 7→ 3} {0 7→ 3, 1 7→ 3, 2 7→ 0, 3 7→ 3}

00 01 10 11

Double stack push Partial identity Partial identity Double stack pop

e7 e8 e9 e10 e11

{0 7→ 3, 1 7→ 3, 2 7→ 3, 3 7→ 3} {0 7→ 1, 1 7→ 3, 2 7→ 3, 3 7→ 3} {0 7→ 3, 1 7→ 0, 2 7→ 3, 3 7→ 3} {0 7→ 3, 1 7→ 2, 2 7→ 3, 3 7→ 3} {0 7→ 3, 1 7→ 3, 2 7→ 1, 3 7→ 3}

000 001 011 100 110

Annihilation Stack push Stack pop Stack push Stack pop

e12 e13 e14

{0 7→ 0, 1 7→ 3, 2 7→ 3, 3 7→ 3} {0 7→ 3, 1 7→ 1, 2 7→ 3, 3 7→ 3} {0 7→ 3, 1 7→ 3, 2 7→ 2, 3 7→ 3}

0011 0110 1100

Partial identity Partial identity Partial identity

Monoid Computation For D6 , we compute the monoid by first constructing the DFA recognizing the language (see Fig. 11) and then extracting equivalence classes by generating all sequences up to a fixed length and grouping them by their induced state mappings in the DFA. We enumerated all even-length sequences up to length 12 and found this to be sufficient empirically: longer even-length sequences did not introduce new ECs. We restrict to even lengths because our analysis is over positive sequences (which must be even length). This restriction is natural because the balanced reduction composes even-length subsequences (2, 4, 8, . . . ), so only ECs with even-length representatives arise in this setting. The equivalence classes we do not

38

discover are those that only contain odd-length sequences, meaning that we can characterize any even-length sequence by dividing it into smaller even-length sequences. 0 0/1

0 1/0

1

1 1

0 2/0

0 3/0

1

1 7/0

0

0 4/0

5/0 1

6/0 1

0

0,1

Figure 11: A complete DFA that recognizes D6 . We include the rejecting sink state (a state such that if a sequence reaches it, then it is rejected as it is malformed), omitted from the D3 figure in Table 8, to better illustrate the state mappings of the monoid. Reduction Simulation We simulate the reduction process to estimate the frequency of monoid element compositions that occur during training and testing: 1. We determine the number of sequences to generate based on fixing the number of equivalence class compositions we want to observe. We fix the number of compositions to 1,000,000 within a range of sequence lengths and vary the number of samples per length within the range to ensure an equal number of equivalence class compositions per length. The ranges of sequence lengths we examined were 10–40 (step 2), 42–60 (step 2), 62–100 (step 4), 102–150 (step 4), and 480–500 (step 2). 2. We determine the equivalence classes of even-length subsequences that reflect increasing depth in the reduction: the first are the 2-length, then 4-length, then 8-length subsequences, and so on until the subsequence is the entire sequence. Each of these subsequences will be composed by the reduction operator as the token embeddings are aggregated. 3. During reduction simulation, we count all pairwise compositions (ei , ej ) → ek that occur when applying the monoid operator ⊙. We do not count the compositions that result in the equivalence classes representing the 2-length subsequences because they are only 4 types of compositions (binary alphabet) and would dominate the composition counts. 4. We record composition frequencies to generate probability distributions over monoid element pairs. The simulation replicates the exact reduction binary tree structure, ensuring that recorded compositions match those encountered during actual model training. The heatmaps in Fig. 5 reveal insights into why training sequence length influences generalization success: Analysis Positive sequences of length 10–40 exhibit sparse composition patterns, with most equivalence class pairs showing low log probabilities (lighter regions). The concentration of high-probability compositions in the lower-index region (equivalence classes 0–15) occurs because these represent the most frequently encountered partial sequences in shorter training data. As training sequence length increases to 62–100 and beyond, additional composition patterns emerge. As equivalence classes are discovered dynamically from the generated sequences with increasing length, higher index equivalence classes tend to be rarer and sharper state mappings (i.e., an increasing number of annihilations, see Table 31). Complete generalization requires some exposure to all possible monoid element compositions that can occur during testing. The difference in sparsity between training and testing heatmaps directly explains the empirical results: insufficient training sequence length fails to provide sufficient coverage of rare monoid compositions. Moreover, some languages are likely to be impossible to learn (i.e., generalize to) without a sufficient maximum training sequence length, as they require compositions between equivalence classes that are never encountered in shorter sequences.

39