Slower Generalization, Faster Memorization: A Sweet Spot in Algorithmic Learning

Technical Summary: Slower Generalization, Faster Memorization: A Sweet Spot in Algorithmic Learning

Problem Definition
While empirical scaling laws and "grokking" studies suggest that larger datasets generally improve model performance and that additional data accelerates validation convergence once a generalization threshold is crossed, this paper investigates whether this intuition holds universally for structured-output tasks. Specifically, the authors ask: After generalization becomes possible, does the largest dataset always yield the fastest validation convergence under a fixed optimization protocol? The study focuses on Needleman–Wunsch (NW) matrix generation, a task where a model must predict a full dynamic-programming score matrix from two input strings. Unlike scalar arithmetic tasks, NW requires the coordinated prediction of many dependent cells, creating a high-complexity structured output.

Methodology
The authors employ a controlled experimental protocol using decoder-only Transformers trained on NW matrix generation and a three-digit multiplication baseline.

• Task: The model maps input string pairs $(x, y)$ to a target matrix $M(x, y)$ generated by the NW dynamic programming recurrence. Correctness is measured via exact-match accuracy (all matrix entries must be correct).
• Variables: The primary variable is dataset size ($N$), swept across a wide range (from 200 to 300,000 examples). Model depth, optimizer settings (AdamW), and learning rate schedules are held fixed.
• Metrics: The study measures the number of optimizer updates required to reach specific exact-match accuracy thresholds ($\tau$) for both training ($IT$) and validation ($IV$). This "update-based" metric distinguishes convergence speed from epoch-normalized efficiency.
• Probes: To disentangle rule learning from memorization, the authors introduce a random-suffix probe, appending a four-bit random suffix to the target matrix. This isolates example-specific information (the suffix) from rule-generated structure (the matrix).
• Baselines: Three-digit multiplication serves as a contrast task to verify if the observed phenomena are specific to structured dynamic programming or artifacts of the exact-match evaluation.

Key Contributions
The paper makes three primary empirical contributions:

1. Identification of a Dataset-Size Sweet Spot: In NW matrix generation, validation convergence is fastest at an intermediate dataset size, not the largest one. This contradicts the standard post-threshold intuition that "more data is always faster" once generalization is attainable.
2. Acceleration of Fitting via Partial Rule Learning: In the regime where weak validation competence first appears, increasing the dataset size can actually reduce the number of updates needed to reach high training accuracy. This suggests that partial rule learning can accelerate the fitting process, rather than merely adding memorization burden.
3. Mechanistic Separation of Pressures: The authors propose a "two-pressure account" where additional data initially aids rule discovery (improving structural coverage) but eventually increases the cost of residual exact fitting (memorizing details not fully determined by the rule).

Results

• Non-Monotonic Validation Convergence: For NW, the number of updates to reach strict validation thresholds (e.g., $\tau=0.98$) follows a U-shaped curve. Small datasets fail to generalize or require long delays. Intermediate datasets converge fastest. Large datasets still generalize but require significantly more updates to reach the same threshold, indicating a "post-threshold slowdown."
• Contrast with Multiplication: The multiplication baseline does not exhibit this slowdown; validation convergence remains flat or improves with larger datasets. This confirms the phenomenon is tied to the specific structure of the NW task (long, dependent outputs) rather than the exact-match metric itself.
• Training vs. Validation Timing: Near the onset of generalization, larger datasets can reduce the updates needed for high training accuracy. This indicates that memorization and generalization are not strictly sequential; partial rule acquisition can make the remaining fitting task easier.
• Random-Suffix Diagnostics: At larger dataset sizes, the model fits the rule-generated matrix before it fits the random suffix. This supports the hypothesis that the structured component benefits from the learned rule, while the unstructured suffix represents the residual "exact-fitting" burden that grows with dataset size.
• Train-Validation Gap: The gap between training and validation accuracy ($G = A_T - A_R$) becomes positive precisely when validation accuracy begins to rise, suggesting that the same rule-mediated progress drives both.

Significance and Claims
The paper claims to refine, rather than contradict, the classical grokking and critical-data-size literature.

• Refining Critical Data Size: While critical data size ($N_c$) marks the onset of generalization (when a solution becomes identifiable), the authors show that the dataset size optimizing update-based convergence speed ($N^*$) can be distinct from $N_c$ and distinct from the maximum available dataset.
• Divergence of Learning Stages: The results demonstrate that in structured-output tasks, "learning the rule" and "completing exact-fitting" can diverge. Once a useful rule is discovered, further data may primarily increase the burden of fitting residual details, slowing down convergence in terms of gradient updates.
• Scope: The authors modestly claim this phenomenon is specific to tasks combining reusable algorithmic structure with high per-example output complexity (e.g., dynamic programming tables like edit distance or Viterbi decoding). They do not claim this applies to all algorithmic tasks or that larger datasets are intrinsically harmful for asymptotic accuracy, but rather that the path to convergence in terms of optimizer updates is non-monotonic in specific structured settings.

The study concludes that for structured-output learning, the fastest route to validation generalization may occur at an intermediate dataset size where the benefits of rule discovery have saturated, but the costs of residual exact fitting have not yet become dominant.