Technical Summary: A Mathematical Theory of Balancing Relational Generalization and Memorization

Problem Statement

Learning systems, including humans, animals, and machine learning models, must simultaneously learn general rules to enable relational generalization and memorize specific exceptions to those rules. While extensive literature exists on compositional generalization and memorization in isolation, there is a lack of task paradigms and theoretical frameworks to understand how systems balance these opposing demands when both are required. Specifically, it remains unclear how learning systems handle ordered relations that are largely transitive but contain intransitive exceptions (e.g., $A > B > C$, but an exception $C > A$). Existing paradigms like Transitive Inference (TI) test pure generalization, while Transverse Patterning (TP) tests pure memorization of intransitive loops, but neither captures the complexity of real-world scenarios where rules and exceptions coexist.

Methodology

The authors introduce a novel task paradigm and a theoretical framework to analyze this balance:

1. Task Paradigm: Transitive Inference with Exceptions (TIwE)

   • The task involves a set of items $I_1, \dots, I_n$ with an underlying transitive ranking.
   • An "exception" is introduced: an intransitive pair $I_p > I_q$ where $p > q$ (violating the global order) and $|p-q| > 1$.
   • This creates two transitive sections ($O^{(1)}$ and $O^{(2)}$) separated by an intransitive section ($L$).
   • Evaluation focuses on four metrics: memorization of transitive pairs, memorization of intransitive pairs, within-section generalization, and cross-section generalization (e.g., inferring $I_1 > I_n$ despite the exception in the middle).

2. Theoretical Model: Kernel Ridge Regression

   • The authors analyze a random features model $\phi(x) = \sigma(Wx)$ in the infinite-width limit, which converges to Kernel Ridge Regression.
   • They assume an exchangeable representation, where the kernel $K(x, x')$ depends only on the overlap between items (identical, overlapping, or distinct pairs), formalized by parameters $\kappa_s, \kappa_o, \kappa_d$.
   • The model is characterized by two key parameters:
     • Conjunctivity factor ($\alpha$): Measures the degree of non-linear entanglement between items in the representation ($\alpha=0$ is fully compositional/additive; $\alpha=1$ is fully conjunctive).
     • Effective regularization ($\tilde{c}$): Scales the $L_2$ regularization strength.

3. Analytical Derivation

   • The authors analytically solve the ridge regression dual problem to derive the model's predictions.
   • They decompose the solution into an emergent ranking system ($r_j$) and a conjunctive response ($t_{j,k}$) that activates only on training data.
   • The ranking system is shown to be a perturbation of the standard TI ranking system, modified by the presence of the exception.

Key Contributions and Results

1. Theoretical Characterization of the Balance

The paper derives a closed-form solution (Theorem 1) showing that kernel models naturally balance generalization and memorization through a trade-off between the ranking system and the conjunctive readout:

• Generalization: The model learns a ranking system $r_j$ that is monotonically decreasing within transitive sections. However, the presence of an exception introduces non-monotonicity in the ranking system around the intransitive loop.
• Memorization: The model uses a conjunctive term $t_{j,k}$ to correct errors on the training set, specifically memorizing the exception.
• The Trade-off: Successful generalization (specifically cross-section generalization) and successful memorization are in tension.
  • Representational Geometry ($\alpha$): More compositional representations (low $\alpha$) favor generalization but struggle to memorize exceptions. More conjunctive representations (high $\alpha$) easily memorize exceptions but may fail to generalize across sections due to the non-monotonicity of the ranking system.
  • Regularization ($\tilde{c}$): Stronger regularization (smaller $\tilde{c}$) forces the model to rely more on the ranking system to minimize weight norms, leading to systematic errors in generalization (predicting $I_{q-1} < I_{p+1}$ incorrectly) and reduced memorization of the exception. Conversely, weak regularization allows better memorization but risks overfitting.

2. Mechanistic Explanation of Failure Modes

The authors explain that the non-monotonicity of the emergent ranking system is the root cause of systematic errors.

• To minimize the weight norm (regularization), the model must compromise between a "flat" ranking system (good for generalization) and a "corrected" ranking system (needed to fit the exception).
• This compromise results in a ranking system that is distorted near the exception, propagating errors to cross-section generalization tasks.
• Crucially, the paper notes that L2-regularization, typically beneficial for in-distribution generalization, can be counterproductive for out-of-distribution generalization in this specific task, inducing systematic errors where none would occur in standard TI.

3. Empirical Validation in Pretrained Language Models (PLMs)

The theoretical insights were validated by finetuning PLMs (Llama3.2, Qwen3.5) on TIwE tasks using sports team hierarchies and poker hand rankings.

• Generalization: Models successfully generalized within sections but showed inconsistent performance on cross-section generalization, often making systematic errors predicted by the theory (accuracy dropping below chance).
• Memorization: Models could memorize the exception, but performance was sensitive to regularization. Stronger regularization reduced accuracy on the exception pairs.
• Task Parameters: Increasing the length of transitive sections made cross-section generalization significantly harder, while increasing the length of the intransitive loop had a weaker effect, aligning with theoretical predictions.
• Finetuning Strategies: Full finetuning and linear probing generally outperformed LoRA, and the behavior of linear probing closely matched the kernel model predictions regarding the effects of regularization.

Significance and Claims

The paper claims to provide the first analytical framework for understanding how learning systems balance relational generalization with the memorization of exceptions. Its significance lies in:

1. Identifying a New Failure Mode: It demonstrates that tasks requiring a balance of rules and exceptions are fundamentally more challenging than pure rule-learning tasks, as they introduce a trade-off between representational geometry and regularization that can lead to systematic, non-random errors.
2. Re-evaluating Regularization: It highlights that standard regularization techniques (like L2) can hinder out-of-distribution generalization in compositional tasks with exceptions, contrary to their usual role.
3. Benchmarking: It proposes "Transitive Inference with Exceptions" as a necessary new paradigm to probe the limits of compositional generalization in both biological and artificial systems.
4. Theoretical Grounding: By showing that simple kernel models can capture the nuanced behavior of large language models on these tasks, it suggests that the limitations of PLMs in handling exceptions may stem from fundamental geometric constraints in their learning dynamics rather than just architectural complexity.

The authors conclude that explicitly modeling the effect of exceptions is critical for developing learning systems capable of robust real-world reasoning, and that future work should focus on task paradigms that capture this complexity.