CS Paper Radar

One-Layer Transformer Provably Learns Multiclass One-Nearest Neighbor in Context

Skanda Athreya, Yutong Wang

cs.LG stat.ML ·submitted 2026-09-01 14:35 UTC · v1
unusual

Abstract

We extend recent work establishing an equivalence between one-layer transformers and nearest-neighbor classifiers in the binary setting to the multiclass case. By leveraging the simplex encoding, we show that one-layer transformers with an argmax classification head behave identically to a one-nearest-neighbor classifier in the multiclass setting. This closes a gap left by prior work, whose multiclass result relied on a non-standard rounding-based approach rather than the typical argmax head used in practice.

Closest papers

Nearest neighbours by meaning across the whole index.

One-Layer Transformers Provably Learn In-Context K-Nearest Neighbor Prediction with Chain-of-Thought

cs.LG stat.ML ·2026-10-12 ·Lyumin Wu, Yuan Cao
hot direction similarity 0.63
Abstract · 107 pages, 2 figures

Chain-of-Thought (CoT) enables transformers to solve complex reasoning tasks by generating intermediate reasoning steps. Despite strong empirical success, the mechanisms by which such reasoning abilities emerge during training remain poorly understood, particularly from a theoretical perspective. In this work, we study this question in a stylized yet fully analyzable setting: in-context $\mathrm{K}$-nearest-neighbor ($\mathrm{K}$-NN) prediction with a one-layer transformer. Earlier work has demonstrated that one-layer transformers can be trained to perform $1$-NN without CoT (Li et al., 2024a) by having the softmax attention attend to the nearest neighbor in context. However, this result on $1$-NN cannot be extended to $\mathrm{K}$-NN for $K>1$, as softmax attention is much less naturally suited to attending to the 2nd through $K$-th nearest neighbors. We first give a rigorous negative result showing that this limitation already appears on a well-separated class of binary classification tasks for odd $K>1$. We then give an explicit construction of a one-layer transformer, and show that it can solve $\mathrm{K}$-NN via CoT reasoning. We further prove that, under a stylized training setup, gradient descent can recover this construction, thereby showing that transformers can acquire the capability to solve $\mathrm{K}$-NN through training. In addition, we show that the resulting trained model applies to a broader test class than that assumed in the training analysis. Our results shed light on how CoT expands the ability of transformers to learn and solve tasks that are otherwise hard to solve.

0.29

Transformers Learn Two Competing Sorting Algorithms, and Only One Length-Generalizes

cs.LG cs.CL ·2026-10-18 ·Khashayar Gatmiry, Nathan W. Henry, Chloe H. Su, Emmanuel Abbe, Samy Bengio +3 more
similarity 0.54
Abstract

We show that two-layer transformers trained to near-zero loss on a sorting task converge to one of two mechanistically distinct solution classes depending on their initialization. One solution class consists of solutions that do not use the second attention layer to sort, but also fail to length-generalize. The other, which uses both attention layers, length-generalizes perfectly, despite only being trained to sort sequences of a fixed length. By carefully choosing the weight initialization, we demonstrate that we can steer the model toward learning one solution or the other. We identify input types that are rare at the training length but increasingly common at longer sequence lengths as a source of this disparity in length-generalization, and find that layer-wise specialization of the second class of solutions allows them to handle these rare sequences more accurately. In the second class, we discover a mechanism by which the second layer attention can use the contextual information gathered by the first layer attention to reduce its search space. On the related task of finding the minimum of a sequence, we find a similar two solution-type phenomenon, but with the opposite generalization pattern, where a different form of layer-wise specialization causes the two-layer solution to length-generalize worse than the single-attention solution.

0.22

Procedural Core: A Compact Recurrent Initialization for Vision Transformers

cs.LG cs.CV ·2026-09-29 ·Zachary Shinnick, Christian Internò, Hemanth Saratchandran, Anton van den Hengel, Damien Teney
code/data similarity 0.53
Abstract · Project page: zlshinnick.github.io/procedural-core/

Transformers are typically trained from random initialization, requiring all their capabilities to emerge from large-scale optimization. Recent work showed that a small amount of abstract procedurally generated data can help acquire generic inductive structure at low cost. However, this adds a pretraining stage that must be repeated for every target model. We propose Procedural Core, an initialization strategy that captures this generic structure into a compact set of weights that can be reused across models. We train a minimal recurrent transformer on procedural data, then expand its weights to initialize transformers of arbitrary width and depth. The resulting initialization improves performance on image classification, self-supervised visual learning (DINO), and modeling natural language (FineWeb-Edu) and code (CodeParrot). For image classification, expanding a 1M-parameter core to initialize an 85M-parameter ViT-Base improves ImageNet top-1 accuracy by 2.2 pp over standard random initialization. Our analysis identifies recurrence as essential for learning compact weights that transfer across models. In ViTs, we localize a key benefit in the suppression of high-norm tokens that produces substantial improvements in zero-shot segmentation (ImageNet-S mAP 32.3 to 42.9), object localization (VOC07 CorLoc 9.9 to 18.4), and depth estimation (NYUv2 RMSE 1.104 to 0.998). This demonstrates that transformers need not start from a blank slate, and can be initialized with generic capabilities at low cost with no domain- or task-specific data.

0.52

Training Dynamics of Transformers on Unbounded Inputs: Attention Learning Can Lag Output Layer Learning

cs.LG ·2026-10-14 ·Yaomengxi Han, Debarghya Ghoshdastidar
theory similarity 0.52
Abstract

The success of transformers is attributed to several factors, including their capacity to express formal languages over variable-length inputs, and ability of the attention mechanism to focus on relevant input features. However, there is limited understanding of the training dynamics of shallow transformers, specifically how to decouple the learning of the attention and the output (feedforward) layer. A natural extension of the theory of one-step gradient feature learning in feedforward networks suggests that one could first learn the attention weights with a single gradient step, and then train the output layer. We show that this fails for a shallow transformer trained to recognize a star-free language from unbounded-length input. We prove that the transformer can be trained to recognize the language with a three-phase gradient descent: the output layer is updated first, followed by an attention update, and the output layer is fine-tuned in the third phase. In contrast, the language cannot be learned by training only the attention or output layer, or by a single attention-layer update followed by finetuning the output layer. We empirically show that ``attention learning lagging output layer learning" is beneficial in other language recognition, regression, and in-context learning tasks as well.

0.24

SVD-Based Typicality Maps for Out-of-Distribution Detection in Vision Transformers

cs.CV ·2026-08-24 ·Aldo Sean Sartor, Leandro de Souza Rosa, Andriy Enttsel, Mauro Mangia, Riccardo Rovatti
similarity 0.52
Abstract

We present a method for analyzing the internal representations of Vision Transformers (ViTs) exploiting the geometry of their learned parameters. Each affine layer's weight matrix is factored via Singular Value Decomposition (SVD), and activations are projected onto the leading right singular vectors to obtain compact, layer-intrinsic representations. A class-conditional density model is then fitted at each layer, producing per-class \emph{typicality scores} that are stacked across depth into \emph{typicality maps}: two-dimensional summaries of how class-specific evidence evolves through the network. From these maps, we derive two post-hoc scores for Out-Of-Distribution (OOD) detection: a \emph{Prototype Alignment Score} (PAS), measuring agreement with class reference prototype patterns, and a \emph{Multi-Layer Soft Voting} (MLSV) score, capturing cross-layer consensus without stored prototypes. On ViT-B/16 fine-tuned on CIFAR-100, the proposed scores achieve competitive detection performance without retraining or OOD exposure.

0.15

Feature Evolution and Migration during Vision Transformer Training

cs.CV cs.LG ·2026-08-20 ·Joonas Järve, Halil Ibrahim Aysel, Tarun Khajuria, Meelis Kull
top venue similarity 0.51
Abstract · Accepted to CIKM 2026

We present a novel view on feature evolution in Vision Transformers (ViTs) by visualizing the training process over two dimensions -- network depth (layer) and training time (epochs). We employ Sparse Autoencoders (SAEs) to extract candidate sparse features from CLS-token representations and compare their activation profiles across epoch--layer pairs. This allows us to study feature-level dynamics that are not directly visible from representation-level similarity measures. Furthermore, we demonstrate how this framework of feature evolution allows us to describe feature migration, the change in the layer where a feature is most detectable during training. Our experiments show that migration is concentrated early in training, occurs more often toward earlier layers than toward deeper layers, and declines as feature organization stabilizes. We further find that deeper layers stabilize earlier and more strongly than shallow layers. The results show that our approach can be employed as a tool for understanding how ViTs learn and evolve.

0.30

Focus and Supplement: Dual-Enhanced Vision Transformer for Multi-Class Anomaly Classification

cs.CV ·2026-09-27 ·Xurui Li, Enjie Xu, Chenzhou Li, Shilei Zeng, Dayou Huang +2 more
code/data similarity 0.51
Abstract

Multi-class anomaly classification in industrial vision remains challenging due to noisy/incomplete anomaly representations and the unknown number of anomaly classes. To overcome this, we propose MACO, a novel multi-class anomaly classification framework that learns comprehensive representations and dynamically estimates class number without prior knowledge. First, a soft-focus attention uses anomaly maps to concentrate on relevant abnormal regions, while suppressing background noise. Second, auxiliary classification ([A-CLS]) tokens complement the [CLS] token. They collectively attend to diverse anomaly sub-regions, yielding more holistic and discriminative features. These [A-CLS] tokens are also effective across more tasks and domains. To infer the class number, we propose Correlation-based Number Estimation strategy. It computes the average correlation among labeled classes and transfers its separability cue to the unlabeled set. Experiments on MVTec AD and MTD datasets demonstrate our superiority. Under known class number, MACO improves ARI by 6.5% and $\textbf{16.3%}$ on both datasets, respectively. In the more challenging unknown number scenario, it achieves an $\textbf{11.2%}$ NMI gain on MTD and outperforms existing number estimation strategies by $\textbf{24.1%}$ UPS on MVTec AD. Code will be released at https://github.com/HUST-SLOW/MACO.

0.27

In-context learning of solution to simple linear regression task using transformer with masked linear self-attention

cs.LG ·2026-11-02 ·Katsuyuki Hagiwara
similarity 0.51
Abstract

In-context learning is a remarkable property of transformers and has recently received a lot of interest. In many studies of in-context learning, it has been shown that transformers are capable of implementing solvers for linear and non-linear regression problems, in which the most of them implement gradient descent algorithm. However, it is still unclear whether those implementations have actually been acquired through training. In this paper, we constructed a transformer with masked linear self-attention, which in-context learns the least squares estimate in a simple regression task. The point here is that the closed form (analytical) solution is obtained by using layer normalization rather than an approximate solution based on the gradient descent algorithm. Then, we showed an experimental example, in which, by taking the non-uniqueness of the transformer representation into account, our implementation for a closed form solution is used in the transformer trained with the l1 regularization when the target output is the least squares estimate.

0.06