TL;DR
Transformers often fail to extrapolate correctly on structured tasks because their default inductive bias favors simpler, incorrect polynomial solutions. While previous methods tried to inject structural priors via Query-Key (QK) matrix initialization, these priors are quickly washed out during training. This paper demonstrates that initializing a learnable, additive attention mask provides a persistent structural prior that survives optimization, leading to near-perfect extrapolation in logical and arithmetic tasks.
What Problem Does This Paper Address?
Transformers are highly flexible and excellent at interpolating data within a known distribution. However, they notoriously struggle with Generalization on the Unseen (GOTU). When faced with out-of-distribution inputs in structured domains like Boolean logic, Transformers exhibit a "minimum-degree interpolator" (MDI) bias: they fit the training data perfectly but extrapolate using the simplest possible rule, which is often systematically wrong.
To steer Transformers toward the correct extrapolation rule, researchers have tried injecting structural priors at initialization. Typically, this is done indirectly by initializing the Query (Q) and Key (K) projection matrices so that their similarity scores approximate a desired attention pattern. The catch? Because these same Q and K matrices must adapt to learn task-dependent representations during training, the injected structural priors are rapidly overwritten or "washed out."
The authors of this paper investigate how to inject structural priors into self-attention in a way that actually persists throughout the entire training process.
Methods
The authors propose Mask-Based Structured Initialization. Instead of modifying the Q and K weight matrices, they directly initialize the additive attention mask ($M$).
Unlike standard hard masks used to enforce causality or padding constraints, this mask is a finite, soft, and learnable attention-logit bias. The modified attention formulation is defined as:
$$\text{A}(X) = \text{softmax}\left(\frac{XW_QW_K^\top X^\top}{\sqrt{d}} + \log \sigma(M)\right)XW_V$$
where $\sigma(\cdot)$ is the sigmoid function.
By initializing $M$ with task-specific interaction structures (e.g., enforcing digit-wise alignment for addition or specific variable interactions for Boolean tasks), they encode the prior directly into the attention logits. Because the mask is additive, it decouples the structural prior from content-dependent similarity scores, preventing the optimization process from easily erasing it.
Datasets
The method was evaluated across a diverse set of benchmarks:
- Boolean Reasoning (GOTU setting): 2Parity (XOR), Cyclic3, 3-Bit Majority, and ThreeSym.
- Arithmetic Problems: 3-by-3 digit decimal addition and multiplication.
- Image Classification: CIFAR10, CIFAR100, and ImageNet100 (using a ViT-Tiny architecture).
- Language Modeling: TinyStories and WikiText-2.
Key Insights and Ideas
- Location Matters: Where you place a structural prior dictates its survival. QK-based initializations entangle the prior with query and key feature scales, making them highly susceptible to gradient distortion. Additive masks cleanly separate structural bias from content scores.
- Gradient-Level Persistence: The authors provide a mathematical proof (Theorem 1) showing that the gradients for the mask parameters are naturally moderated by a sigmoid factor $\sigma(-m) \le 1$. This causes mask-based priors to update more slowly and stably than QK-based initializations, preserving the intended interaction graph.
- Learnable vs. Fixed Masks: While fixed masks work well when you know the exact task structure, they degrade performance if the prior is slightly misaligned. Making the mask learnable allows the model to flexibly adapt and refine imperfect priors during training, offering robustness across complex datasets like ImageNet.
Key Results
- Perfect Boolean Extrapolation: On tasks like 2Parity and 3-Bit Majority, mask-based initialization achieved 100% test accuracy on unseen domains, whereas vanilla and QK-initialized Transformers remained trapped by their default inductive bias (stuck at 75% and 87.4% accuracy, respectively).
- Low-Data Arithmetic Acceleration: In a low-data regime for 3-by-3 digit multiplication (using only 3% of the training data), Mask Initialization achieved 69.49% sequence accuracy, drastically outperforming the default Transformer (5.01%) and the best QK-optimization method (27.82%).
- Competitive on Vision and Language: On ImageNet100, Mask Init achieved 85.92% Top-1 accuracy, outperforming both the default baseline (83.38%) and prior structured initialization techniques like Impulse initialization (83.16%).
Limitations and Future Work
The primary limitation of this approach is its dependence on an oracle assumption: the user must have prior knowledge of a meaningful token interaction structure to design the initial mask. While this is straightforward for algorithmic tasks (math, logic) or spatial data (vision locality), it is much less obvious for open-ended domains like natural language processing.
The authors suggest that a compelling direction for future work is developing methods to automatically learn or infer these persistent structural masks directly from data or from large pretrained models, rather than relying on manual construction.
Summary updated