CS Paper Radar

Leaner Transformers Can Easily Learn to Cluster

Charlotte Park, Kenneth L. Clarkson, Lior Horesh, Takuya Ito, Parikshit Ram

cs.LG stat.ML ·submitted 2026-10-07 09:46 UTC · v2
top venue

Abstract

Transformers have in-context learning capabilities, where some known learning algorithms can be executed in the forward pass through the model. Recent work shows that transformers can exactly perform Lloyd's algorithm for $k$-means clustering with $n$ points in $d$ dimensions with an embedding size $d_{\textsf{emb}} = d+k$ (thus, requiring attention projection matrices of size $(d+k)^2$). In this work, we build upon this result in the following ways: First, we present an equally expressive but smaller transformer that executes Lloyd's algorithm with embedding size $d_{\textsf{emb}} = (d + \lceil \log_2 k \rceil)$. Next, we train these transformers to learn the clustering algorithms given a distribution of clustering tasks, and theoretically characterize and empirically validate the factors affecting the convergence and in-distribution generalization of learning algorithms based on stochastic gradients. Finally, we probe the general clustering abilities of these learned algorithms (in the form of transformers), and try to understand situations where they succeed and fail.

Comment
NeurIPS 2026 accepted paper

Closest papers

Nearest neighbours by meaning across the whole index.

Nonparametric In-Context Learning under Growing Geometric Complexity: Minimax Optimality and Local Geometry-Adaptivity of Transformers

cs.LG stat.MLmath.ST ·2026-09-25 ·Jaehee Seo, Jisu Kim
top venuetheory similarity 0.63
Abstract · 63 pages, 3 figures. Accepted at NeurIPS 2026

Transformers have become a central architecture for in-context learning (ICL), particularly through their state-of-the-art performance in large language models. This success motivates understanding how transformers exploit intrinsic geometry of real-world data. However, existing nonparametric ICL theory has largely focused on simplified settings, such as Euclidean domains or single manifold models, failing to fully explain its phenomenal empirical success in complex tasks. To address this gap, we study the prediction problem under unknown heterogeneous geometry, modeled by sample size-dependent mixtures of manifolds with heterogeneous dimensions, smoothness, and sampling masses. Under the growing geometric complexity model, we establish a minimax lower bound capturing the aggregate difficulty of the components and construct an oracle tangent local polynomial estimator with a matching upper bound. This estimator is connected to a structure-informed, two-stage softmax transformer with a geometric preconditioner and local polynomial solvers. The transformer achieves negligible approximation error relative to the minimax rate with logarithmic depth and polynomial size. Finally, we derive an in-context generalization bound for near empirical risk minimizers (ERM) over this class. Together, these results identify conditions under which the resulting predictor exploits local geometry and attains minimax rate.

0.58

Transformer-Based Masked Diffusion Models Provably Learn Distributions with Latent Structure

cs.LG cs.ITmath.STstat.ML ·2026-10-08 ·Jingda Wu, Changxiao Cai
similarity 0.62
Abstract

Masked diffusion models (MDMs) generate discrete data by iteratively unmasking multiple tokens in parallel using a learned mask predictor. Their output carries two errors: parallelization error due to parallel sampling, and estimation error from the mask predictor learned with finite samples. Existing theory treats these errors separately, and the available statistical bounds typically scale with the number $V^L$ of length-$L$ sequences over a vocabulary of size $V$, suffering from the curse of dimensionality. In this work, we establish end-to-end statistical guarantees showing that transformer-based MDMs learn structured distributions with a sample complexity governed by their latent structure. Specifically, we model this structure through mixtures of hidden Markov trees, which capture latent dependencies within components and heterogeneity across components. When the data distribution is well approximated by such a mixture, a transformer-based MDM with parallel unmasking schedules achieves $\varepsilon$-accurate sampling in KL divergence with $\widetilde{O}(LK_{\mathrm{par}}/\varepsilon)$ training samples, where $K_{\mathrm{par}}$ is polynomial in $L$, $V$, the number of hidden states, and the number of mixture components. The transformer network and sampling procedure require no knowledge of the tree topologies or component parameters, thereby adapting to the unknown latent structure automatically. Overall, our results provide theoretical justification for the empirical effectiveness of MDMs on real-world data.

0.41

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.62
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

Spectral Unlearning: Transformer Structure-Preserving Updates for Language Models

cs.LG cs.CLcs.CR ·2026-11-09 ·Sung Il Choi, Junhao Cai, Dohun Kim, Changhee Joo
top venuecode/data similarity 0.61
Abstract · Accepted at NeurIPS 2026

Machine unlearning in large language models (LLMs) aims to remove specific learned knowledge, capabilities, or behaviors while preserving model utility. Existing methods have mostly focused on the design of unlearning objectives, while largely overlooking the intrinsic matrix structure of transformer weights. In particular, standard optimizers operate on independent scalar coordinates, thereby ignoring this matrix structure. We propose spectral unlearning, an update framework that combines standard unlearning objectives with matrix-structured optimization. We show that the spectral update corresponds to the steepest-descent direction for transformers composed of linear layers with normalized inputs and outputs. Our approach is applied on top of existing unlearning methods and evaluated across complementary axes of memorization, privacy, and utility, summarized via their harmonic mean. Spectral unlearning consistently outperforms a broad range of baselines and closes most of the gap to a retain-trained reference. Code is available at https://github.com/unlearn-ml/spectral-unlearning/.

0.51

Dimension Reduction and Coresets for Min-Sum $k$-Clustering

cs.DS cs.CG ·2026-10-28 ·Asaf Dallal, Robert Krauthgamer
similarity 0.61
Abstract

The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two standard sketching methods, dimension reduction and coresets, which represent the input more compactly while preserving the min-sum cost of every $k$-partition up to $1\pm\varepsilon$ factor. Our first contribution addresses dimension reduction in Euclidean space. The Johnson-Lindenstrauss (JL) Lemma readily implies that a random linear map to target dimension $t=O(\varepsilon^{-2}\log n)$ preserves, with high probability, the min-sum cost of all $k$-partitions. We show that target dimension $t=O(\varepsilon^{-2}(ddim\cdot\log(1/\varepsilon)+\log k+\log\log n))$ suffices for Euclidean inputs of doubling dimension at most $ddim$, and moreover this bound is nearly optimal. We also show that target dimension $t=O(\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\logΔ))$ suffices for Euclidean inputs of aspect ratio at most $Δ$. Our second contribution is to design the first $\varepsilon$-coreset for metric min-sum $k$-clustering. It is actually a movement-based coreset, has size $(1/\varepsilon)^{O(ddim)} k\log n$ for inputs of doubling dimension at most $ddim$, and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.

0.18

Transformers as Generic Deep Neural Networks: Exact Compilation, the Cost of Removing Activation-Activation Products, and Multi-Agent Attention Clustering

cs.LG cs.MA ·2026-10-20 ·Sergey Salishev, Zeev Volkovich, Oleg Granichin
theorycode/data similarity 0.60
Abstract · 36 pages, 6 tables and 2 figures in the main text, 8 supplementary tables. Code: https://github.com/iceslice0/transformer-to-dnn

Transformers are deployed as a special model class. Neural processing units (NPU) add dedicated operators for attention and normalization, and quantization relies on Transformer-specific algorithms. We show the computation does not force this. Every Transformer block, with attention, LayerNorm and a GELU MLP, compiles exactly into a generic deep neural network built from fixed affine maps, routing and the square, sigmoid and inverse square root, plus GELU or its sigmoid approximation. Without activation-activation products, every transform-wise compilation adds at least $N^2$ scalar nonlinear evaluations per head for dense scores. Keeping that one operation type removes this cost; its elementwise form, present on every surveyed NPU, suffices with the sigmoid and inverse square root. For top-$k$ attention with exchangeable tail scores, we prove that exact or conditional-mean tail mass gives an unbiased, minimum-mean-square-error estimate of the attention distribution, while tail drop is conditionally biased. When queries or agents cluster, centroids choose the keys first, reducing the number of computed scores from $N^2$ to $Nk$ per head. On DeiT-Tiny, MambaIRv2-Light and Pythia-70M the compiled models match their references with all keys, standard post-training quantization applies, and the exact tail-mass estimate beats tail dropping with half as many keys on DeiT-Tiny and, for $k\le8$, on Pythia-70M.

0.27

Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling

cs.LG stat.MLmath.PR ·2026-09-06 ·Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar, Hoang-Son Tran
benchmark similarity 0.60
Abstract

Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computational constraints demand compact yet faithful summaries. A standard approach is to construct an \textit{$ε$-coreset}: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the \textit{$(k,z)$-clustering problem}, existing worst-case bounds on coreset size are essentially tight, ruling out substantially smaller coresets in general. However, such worst-case instances are often unrepresentative of real-world data. In this work, we show that significantly smaller coresets are possible under mild and natural assumptions on the underlying data distribution. We introduce a new correlated sampling framework, called \textit{determinantal sampling}, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible $\varepsilon$-coreset for $(k,z)$-clustering in $\mathbb R^d$ whose dependence on $1/\varepsilon$ has exponent strictly smaller than $2$ when $d$ is fixed. This improves over the worst-case $\varepsilon^{-2}$ barrier under our beyond-worst-case assumptions. To the best of our knowledge, this is the first result that provably surpasses these lower bounds through beyond-worst-case assumptions. Finally, we validate our approach on synthetic and real-world benchmark datasets, where it consistently achieves smaller coresets than existing state-of-the-art methods, even without explicitly enforcing the assumptions used in the analysis.

0.16

How Much Information Can We Fit inside a Transformer?

cs.AI ·2026-10-25 ·Amirhossein Basareh, Rishabh Sanjay, Daniel de Mello, Abulhair Saparov
code/data similarity 0.60
Abstract

How efficiently can transformers store factual knowledge? The answer to this question has implications for both model design and understanding the limits of transformer-based systems. Prior studies observe a linear relationship between the number of facts memorized and the number of model parameters required, substantially worse than what theoretical analyses predict is achievable. We re-examine empirical scaling: through rigorous and systematic experiments, including extensive hyperparameter search via Bayesian optimization, we determine the smallest model that can perfectly memorize a given set of facts, and measure how this minimum size scales with the number of facts. On synthetic datasets of random, independent (subject, relation, object) triples---e.g., (Paris, capital_of, France) ---drawn at random with no exploitable structure, we find that memorization capacity, the size of the largest dataset that a model memorizes completely, grows exponentially with the transformer dimension. Equivalently, the minimum transformer dimension $d_{\min}$ required to memorize $N$ facts grows logarithmically in $N$. Across 11 dataset sizes spanning $N = 45$ to $49{,}920$, a lack-of-fit F-test does not reject the logarithmic fit (with an offset), but it does reject all other tested alternatives including power-law. Along the depth axis, however, at fixed width, the maximum memorizable dataset size grows sublinearly with the number of layers over the measured range. We further extend our exploration to structured data containing symmetric relations or two-hop composition. In this setting, we find that transformers exploit these regularities to further improve capacity. All code to reproduce our results is available at https://github.com/Magronox/transformer_information_capacity.

0.31