PaperlayerView exact revision on arXiv

Source-linked AI summary

ROTE: Benchmarking Neural Memorization on Complexity-Controlled Symbolic Sequences

Xinye Chen, Stefan Güttel, Mohammad Mozaffari

arXiv:2609.31918v1cs.LGcs.AI

TL;DR

Evaluating symbolic memorization requires controlled sequence complexity and attention to rule generalization, rollout stability, and computational cost. ROTE uses LZW-controlled sequences and shared finite-context prediction and rollout evaluations; its results identify GRU and LinearAttention as leading the main accuracy–cost trade-off, while the benchmark is limited to periodically extended symbolic sequences.

  • Problem

    Existing benchmarks often lack control over sequence complexity or structure, and give limited attention to computational efficiency and sequence similarity, despite the importance of measuring rule generalization.

    Source: §1 · p. 2

  • Method

    ROTE controls symbolic seed complexity with LZW compression and evaluates shared finite-context predictors through teacher-forced prediction and closed-loop rollout.

    Source: §1 · p. 2, §3.3 · p. 5, §3.3.1 · p. 6

  • Results

    GRU and LinearAttention dominate the main accuracy–cost trade-off, while minGRU is highly efficient but less reliable for exact long-horizon reconstruction.

    Source: §6 · p. 10

  • Takeaways & Limitations

    In this finite-data, finite-context setting, model size, training tokens, memory, and runtime should be considered together.

    Source: §6 · p. 10

    The benchmark tests reproduction of a known pattern within its period, so results should not be extrapolated to natural language data or large-scale training.

    Source: §5 · p. 10

Abstract

from arXiv · show

We introduce ROTE (RollOut Testing of Exact memorization), a benchmarking protocol for evaluating symbolic memorization of neural architectures. We study memorization and the extension of symbolic rules in neural sequence models by using sequences whose complexity is regulated by Lempel--Ziv--Welch (LZW) compression. Under ROTE, each architecture is trained as the same finite-context conditional predictor and is evaluated using teacher-forced one-step prediction as well as closed-loop rollout on the withheld symbols. Following a shared prediction-and-rollout evaluation routine, the benchmark evaluates gated recurrent, minimal recurrent, attention-based, and hybrid recurrent-attention models with their native computational characteristics preserved. Beyond standard predictive metrics, the benchmark reports normalized string distances, training time, memory usage, and parameter count across an LZW-complexity sweep. The study establishes a connection between the complexity of algorithmic sequences and the memorization capacity of neural architectures, revealing the trade-offs involving memorization quality, rollout stability, and computational expense. Our software and reproducible experimental code can be obtained from https://github.com/nla-group/rote.

1 Introduction

ROTE addresses the need to evaluate symbolic rule learning and memorization across controlled sequence complexity, while accounting for rollout stability and computational cost. It controls seed-pattern difficulty with LZW compression and evaluates models on held-out prediction and closed-loop rollout.

1 Introduction

  • Evaluating rule discovery, memorization, rollout stability, and computational cost under controlled sequence complexity matters for comparing sequence-model designs.Transformers show strong empirical performance through content-dependent attention, but standard self-attention has quadratic complexity in sequence length.Source: §1 · p. 1
  • The ability to generalize rules from sequential data is a fundamental learning capability relevant to reasoning, pattern recognition, and structured prediction.The passage identifies measuring this ability as important for guiding architecture design.Source: §1 · p. 2
  • Existing benchmarks often lack control of sequence complexity or structure and give little attention to computational efficiency or sequence-similarity metrics.They often use natural-language datasets or simple synthetic tasks, which may favor attention mechanisms over recurrent modeling.Source: §1 · p. 2
  • ROTE controls seed-pattern difficulty with LZW compression and evaluates held-out next-symbol prediction and closed-loop rollout.It also reports string distances, predictive metrics, parameter count, training time, and peak memory.Source: §1 · p. 2

2 Related work

Prior work compares recurrent and attention-based sequence models, studies recurrent models' capacity to represent structured languages and memorize strings, and develops efficient attention and hybrid designs. These lines of work motivate evaluating architectures across both sequence complexity and computational trade-offs.

2 Related work

  • Transformers process sequences in parallel using multi-head attention and have achieved state-of-the-art results in machine translation and text classification [Vaswani et al., 2017].RNNs update hidden states sequentially, but their memory limitations make long-range dependencies and scalability challenging.Source: §2 · p. 2
  • RNN research examines representation of context-free grammar structures [Guan et al., 2021] and finds GRUs perform better on low-complexity sequences while LSTMs perform better on high-complexity sequences [Cahuantzi et al., 2023].The cited memorization study also identifies learning rate and units per layer as important hyperparameters to tune.Source: §2 · p. 2
  • Efficient attention mechanisms target the quadratic cost of standard self-attention, but Long Range Arena reports nontrivial quality–memory trade-offs rather than a universally superior design [Tay et al., 2021].Linear attention recasts causal attention as recurrent computation, while Performer approximates softmax attention with random features [Katharopoulos et al., 2020, Choromanski et al., 2021].Source: §2 · p. 2

3 Models and benchmarking

ROTE separates seed compressibility from finite-context next-symbol prediction, then evaluates the same conditional-prediction task across architectures using both held-out windows and closed-loop rollout. The benchmark also frames model error in relation to sequence complexity, context length, and rollout horizon.

3.3 Finite-context prediction and rollout

  • Every architecture uses a shared finite-context conditional-prediction task, while retaining its own state update, attention, or pooling mechanism.The observable prefix supplies chronological training, validation, and test windows; the final target block is withheld for forecasting.Source: §3 · p. 3, §3.3 · p. 5

3.1 Controlled symbolic sequences

  • Seed alphabet size n and target LZW complexity c are controlled independently: n sets the output classification dimension, while c controls seed description length.The benchmark separates seed complexity from the finite-context supervised prediction problem.Source: §3.1 · p. 3, §3 · p. 3

3.1.1 LZW parsing, periodic reduction, and seed generation

  • Seeds are built by appending random alphabet symbols until their reduced-string LZW score reaches the target, then retaining only seeds with exact measured complexity.The score counts emitted LZW codes after exact-period reduction; it is a reproducible proxy for description length, not an absolute Kolmogorov complexity.Source: §3.1.1 · pp. 3–4

3.2 Finite-context identifiability

  • A context length r permits perfect one-step prediction exactly when every observed context has a unique next symbol; r⋆ is the smallest such length.If one context admits multiple next symbols, no deterministic rule of that context alone can match all transitions.Source: §3.2 · p. 5

3.3.1 Teacher-forced error versus rollout stability

  • Teacher-forced metrics assess local conditional prediction, while closed-loop rollout tests whether that rule remains stable on model-generated contexts.An early error can move later contexts outside the empirical distribution despite low one-step error.Source: §3.3.1 · p. 6

3.4 A complexity-aware scaling view

  • The benchmark treats model error as depending on model, data, and compute budgets together with an algorithmic and finite-context profile, rather than budgets alone.This is an organizing principle, not a fitted scaling law; it motivates joint sweeps over parameters, tokens, context, horizon, complexity, and predictive order.Source: §3.4 · p. 6

4 Experiments

ROTE compares recurrent, attention-based, and hybrid models on LZW-controlled symbolic sequences using a shared next-symbol prediction and rollout protocol. Across the benchmark, GRU and LinearAttention lead on rollout quality, while matched-size results show that parameter-count differences alone do not explain the ranking.

4.1 Experimental protocol

  • The 640-run comparison uses eight architectures, LZW complexities c=10–90, four alphabet sizes, length-100 contexts, and 100-symbol rollouts.A separate high-complexity track matches models to approximately 0.2M parameters at c=90; Performer’s reported runtime and memory are conservative because it uses a non-CUDA autoregressive fallback.Source: §4.1 · pp. 6–7

4.2 Accuracy under increasing symbolic complexity

  • Across models, normalized DL distance rises from 0.003 at c=10 to 0.099 at c=70, while test accuracy falls from 0.999 to 0.922.The improvement from c=70 to c=90 shows that LZW complexity is not a complete difficulty ordering; finite-context ambiguity, predictive order, alphabet size, and seed periodicity also vary.Source: §4.2 · p. 7, Figure 1 · p. 8
  • GRU and LinearAttention lead: exact 100-step rollout rates are 0.925 and 0.912, and c=90 mean DL distances are 0.015 and 0.013, versus Transformer’s 0.613 rate and 0.132 distance.LSTM remains competitive with an exact rollout rate of 0.887, while its higher test loss at c=90 suggests less stable optimization under the same budget.Source: §4.2 · pp. 7–8

4.3 Compute–accuracy trade-offs

  • minGRU is smallest and fastest, with median 0.067M parameters and 6.30s training time, but lower rollout fidelity than GRU or LinearAttention.LinearAttention reaches near-GRU rollout quality with fewer epochs and lower wall-clock time but larger memory use in this implementation; RWKV converges quickly and uses less memory than attention baselines, but has higher rollout error than the leading gated and linear-attention models.Source: §4.3 · pp. 8–9, Table 2 · p. 9, Figure 3 · p. 9

4.4 Matched-size high-complexity check

  • At matched size and c=90, LSTM, GRU, LinearAttention, and Performer exactly reproduce all eight rollouts; Transformer misses one, while RWKV is less stable in closed-loop generation.LinearAttention is the fastest exact model in this track, whereas Performer is exact but expensive because of its non-CUDA autoregressive fallback.Source: §4.4 · pp. 9–10, Table 3 · p. 10
  • The matched-size check does not reverse the qualitative ordering, so reducing parameter-count differences alone does not explain the remaining gap.The authors conclude that larger softmax-attention models need more careful scaling of tokens, parameters, and optimization budget before their parameter advantage can be interpreted fairly.Source: §4.4 · pp. 9–10

5 Limitations

The comparisons do not match realized optimizer updates or tune each architecture, and the matched-size check is limited in scope. The benchmark also tests periodically extended symbolic sequences with identifiable finite-context targets, so its results do not establish performance on unknown rules, natural language, or large-scale training.

5 Limitations

  • Early stopping produces different optimizer-update counts, so neither comparison is compute-matched or architecture-specifically tuned.The matched-size check only approximately matches six model families around 0.2 M parameters; it excludes minGRU and minLSTM and does not fix training tokens per parameter.Source: §5 · p. 10
  • The benchmark uses periodically extended symbolic sequences with at most a few million parameters, and its withheld suffix reproduces a known pattern rather than testing discovery of an unknown rule.The authors caution against extrapolating these results to natural language or large-scale training.Source: §5 · p. 10
  • Runs sharing a generated seed are not independent samples of symbolic structure, and reported standard deviations are descriptive rather than confidence intervals.The authors say small differences between leading models remain uncertain.Source: §5 · p. 10
  • All tested seeds have r⋆(u) ≤18 and α100(u) = 0, leaving the case w < r⋆(u) and αw(u) > 0 unexplored.In that untested case, perfect one-step prediction is not possible.Source: §5 · p. 10
  • Measured runtime and peak CUDA memory depend on the implementation and A100 GPU slice, and Performer was tested without its optional custom causal CUDA kernel.State-space models such as Mamba are also absent from the comparison.Source: §5 · p. 10

6 Conclusion

The conclusion finds that GRU and LinearAttention lead the main accuracy–cost trade-off, while minGRU is efficient but less reliable for exact long-horizon reconstruction. It argues that symbolic memorization comparisons should report task complexity and computational budgets together, while a compute-optimal scaling analysis remains future work.

6 Conclusion

  • GRU and LinearAttention dominate the main accuracy–cost trade-off, while minGRU is highly efficient but less reliable for exact long-horizon reconstruction.The vanilla Transformer and Performer do not automatically benefit from their larger parameter counts in this finite-data, finite-context setting.Source: §6 · p. 10
  • Studies of symbolic sequence learning should state task complexity, predictive order, finite-context ambiguity, and rollout horizon alongside model size and data budget.A full matched-scaling analysis would sweep sequence length, training-token multiplier, and parameter quantity.Source: §6 · pp. 10–11
  • The reported experiments are a fixed-budget comparison with a targeted robustness check, not a compute-optimal scaling analysis.The authors call for revisiting efficient attention and hybrid recurrent models with optimized kernels.Source: §6 · p. 11

A.1 Fixed-budget and matched-size comparison

Figure 4 compares the fixed-budget experiment with the matched-size robustness check on the shared high-complexity subset.

A.1 Fixed-budget and matched-size comparison

  • Figure 4 compares the fixed-budget and matched-size checks at c = 90 and n ∈{4, 8}, with rollout distance and teacher-forced test loss in its two panels.These are the benchmark’s two complementary measurements.Source: §A.1 · p. 13

A.2 Distance Metrics

The benchmark evaluates withheld rollouts with normalized Damerau–Levenshtein and Jaro–Winkler string distances. Both are better when smaller, and exact reconstruction scores zero on each.

A.2 Distance Metrics

  • Normalized Damerau–Levenshtein and Jaro–Winkler distances evaluate sequence-level rollout predictions, with smaller values better and exact reconstruction giving DL = JW = 0.The strings are not treated as embedded in a Euclidean space.Source: §A.2 · pp. 13–14
  • Damerau–Levenshtein edit distance is defined recursively over prefixes, with insertion, deletion, substitution, and adjacent-transposition cases.For equal-length strings, the benchmark reports a normalized score.Source: §A.2 · p. 13
  • Jaro–Winkler similarity uses matching symbols and transpositions, then applies a common-prefix adjustment capped at length 4 with ρ = 0.1.Symbols match when equal and within the stated positional window.Source: §A.2 · p. 14

A.3 Model architectures

The benchmark gives each architecture the same finite-context next-symbol prediction contract while preserving its native state representation and computational characteristics. The model set spans classical and minimal recurrent networks, attention models, and a recurrent-attention hybrid.

A.3 Model architectures

  • All models map a length-w one-hot context to next-symbol logits under a shared input–output contract while retaining native state representations.The scorer is fθ in Equation (6).Source: §A.3 · p. 14
  • LSTM and GRU process windows sequentially and predict from the final hidden state, with linear window-length cost and a recurrent inductive bias.LSTM uses input, forget, and output gates with a cell state; GRU uses reset and update gates [Cho et al., 2014].Source: §A.3 · p. 14
  • minGRU and minLSTM use simplified gated recurrences intended to retain sequence-modeling advantages while improving parallelizability and implementation simplicity.They use the same finite-context input and next-symbol objective as the classical recurrent models [Feng et al., 2024].Source: §A.3 · p. 14
  • The Transformer uses softmax attention with O(w^2dm) per-layer attention cost, while LinearAttention uses a kernelized map with implementation-dependent O(wd^2m) or linear-in-length autoregressive computation.The Transformer predicts from its final contextual representation [Vaswani et al., 2017]; LinearAttention tests whether recurrent-style computation can match gated recurrence [Katharopoulos et al., 2020].Source: §A.3 · p. 14
  • Performer approximates softmax attention with positive random features, and RWKV combines channel mixing with recurrent time-mixing and constant-size inference state.Performer’s measured run used a non-CUDA autoregressive fallback, making its empirical cost implementation-specific [Choromanski et al., 2021]; RWKV is a hybrid baseline [Peng et al., 2023].Source: §A.3 · p. 14

Related papers

Loading 2609.31918v1…