Multipole Semantic Attention: A Fast Approximation of Softmax Attention for Pretraining

• URL: http://arxiv.org/abs/2509.10406v2
• Date: Mon, 15 Sep 2025 15:24:37 GMT
• Title: Multipole Semantic Attention: A Fast Approximation of Softmax Attention for Pretraining
• Abstract summary: We present Multipole Semantic Attention (MuSe), an efficient approximation of softmax attention.<n>Our method addresses the quadratic computational complexity of transformers in the context length by clustering queries and keys separately.<n>For causal attention, we develop a hierarchical block decomposition that combines exact local computation with efficient long-range approximation.
• Score: 36.70261826975876
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present Multipole Semantic Attention (MuSe), an efficient approximation of softmax attention that combines semantic clustering with multipole expansions from computational physics. Our method addresses the quadratic computational complexity of transformers in the context length by clustering queries and keys separately in their learned representation spaces, enabling a hierarchical two-stage attention mechanism. Unlike prior clustering approaches that group only keys or use unified clustering, we maintain separate clusterings that respect attention's asymmetric treatment of these spaces. We augment centroid-based (monopole) approximations with dipole corrections that capture directional variance within clusters, preserving richer information during training. The method operates as a drop-in replacement for standard attention, requiring only hyperparameter specification without architectural modifications. Our approach achieves $\mathcal{O}(NCD)$ complexity for acausal attention with $C$ clusters and $\mathcal{O}(NCD \log N)$ for causal attention. On isolated attention layers, we demonstrate $3\times$ speedup over CUDNN Flash Attention at 8k context length, with relative squared errors below 20%. For causal attention, we develop a hierarchical block decomposition that combines exact local computation with efficient long-range approximation. In end-to-end pretraining of a 30M parameter model on book-length texts with 16k context, we achieve 12.2% runtime reduction with only 0.36% loss degradation, establishing the viability of multipole approximations for efficient transformer pretraining.

Related papers

• ClusterAttention: A training-free speedup of bidirectional attention [0.0]
  ClusterAttention is a training-free speedup of bidirectional attention layers.<n>On large-scale data ClusterAttention speeds up TabPFN-3 arXiv:2605.13986 by two to six times.
  arXiv  Detail & Related papers  (2026-08-27T11:04:41Z)
• SCOPE: Subspace Clustering with Online Per-Head Top-K Estimation for Sparse Video Attention [27.426483415833072]
  SCOPE is a training-free sparse attention framework for video-DiT inference.<n>It combines 3D-RoPE-aligned key subspace with clustering online per-head Top-$k$ estimation.<n>SCOPE consistently outperforms existing training-free baselines in both fidelity and latency.
  arXiv  Detail & Related papers  (2026-08-13T03:43:31Z)
• ATMA: Length-Invariant Language Modeling via Polar Attention and Gated-Delta Compression Memory [0.0]
  ATMA is a hybrid convolutional-attention architecture that integrates a novel three-channel attention mechanism.<n>We evaluate ATMA using a 120-run factorial ablation sweep, demonstrating that the combined Polar + memory model maintains induction needle-in-a-haystack retrieval accuracy above 90%.
  arXiv  Detail & Related papers  (2026-06-23T20:43:51Z)
• Mixtures of Subspaces for Bandwidth Efficient Context Parallel Training [54.43685601795611]
  We propose a compression method for communication-efficient context parallelism in decentralized settings.<n>Our key insight is to exploit the intrinsic low-rank structure of activation outputs by dynamically constraining them to learned mixtures of subspaces.
  arXiv  Detail & Related papers  (2026-06-15T08:17:13Z)
• Latent-Condensed Transformer for Efficient Long Context Modeling [60.72493959155964]
  We propose Latent-Condensed Attention (LCA) for large language models.<n>LCA condenses context within MLA's latent space, where representation is disentangled into semantic latent vectors and positional keys.<n>LCA achieves up to 2.5$times$ prefilling speedup and 90% KV cache reduction at 128K context.
  arXiv  Detail & Related papers  (2026-04-14T08:40:31Z)
• VSPrefill: Vertical-Slash Sparse Attention with Lightweight Indexing for Long-Context Prefilling [0.0]
  Existing sparse attention methods face a trade-off among context adaptivity, sampling overhead, and fine-tuning costs.<n>We propose VSPrefill, a mechanism requiring lightweight training that uses the vertical-slash structural pattern in attention distributions.<n>VSPrefill preserves 98.35% of the full attention accuracy while delivering a 4.95x average speedup at a context length of 128k.
  arXiv  Detail & Related papers  (2026-03-03T09:24:58Z)
• Neuronal Attention Circuit (NAC) for Representation Learning [2.0573301822495553]
  We introduce a CT-Attention mechanism that reformulates attention logits computation as the solution to a linear first-order ODE.<n>We implement NAC in diverse domains, including irregular time-series classification, lane-keeping for autonomous vehicles, and industrial prognostics.
  arXiv  Detail & Related papers  (2025-12-11T04:49:44Z)
• Rate optimal learning of equilibria from data [63.14746189846806]
  We close theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity.<n>For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM.<n>We provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
  arXiv  Detail & Related papers  (2025-10-10T12:28:35Z)
• RAT: Bridging RNN Efficiency and Attention Accuracy via Chunk-based Sequence Modeling [27.094682429698384]
  We propose RAT, an intermediate design that bridges the efficiency of RNNs and capacity of attention.<n>RAT partitions the input into chunks, applies recurrence within each chunk for local dependencies, and softmax-based attention across chunks for long-range interactions.<n>With a chunk size of 16, the RAT block achieves a 7x improvement in training speed with 100K token sequences and 9x in generation at the 4K position.
  arXiv  Detail & Related papers  (2025-07-06T15:08:49Z)
• Scalable Context-Preserving Model-Aware Deep Clustering for Hyperspectral Images [51.95768218975529]
  Subspace clustering has become widely adopted for the unsupervised analysis of hyperspectral images (HSIs)<n>Recent model-aware deep subspace clustering methods often use a two-stage framework, involving the calculation of a self-representation matrix with complexity of O(n2), followed by spectral clustering.<n>We propose a scalable, context-preserving deep clustering method based on basis representation, which jointly captures local and non-local structures for efficient HSI clustering.
  arXiv  Detail & Related papers  (2025-06-12T16:43:09Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• AnchorAttention: Difference-Aware Sparse Attention with Stripe Granularity [9.63873831179673]
  Large Language Models (LLMs) with extended context lengths face significant computational challenges during the pre-filling phase.<n>We propose textbfAnchorAttention, a difference-aware, dynamic sparse attention mechanism that efficiently identifies critical attention regions.<n>With its finer-grained sparsity strategy, textbfAnchorAttention achieves higher sparsity rates at the same recall level, significantly reducing computation time.
  arXiv  Detail & Related papers  (2025-05-29T14:59:06Z)
• Delta Attention: Fast and Accurate Sparse Attention Inference by Delta Correction [52.14200610448542]
  A transformer has a quadratic complexity, leading to high inference costs and latency for long sequences.<n>We propose a simple, novel, and effective procedure for correcting this distributional shift.<n>Our method can maintain approximately 98.5% sparsity over full quadratic attention, making our model 32 times faster than Flash Attention 2 when processing 1M token prefills.
  arXiv  Detail & Related papers  (2025-05-16T13:48:33Z)
• Radius-Guided Post-Clustering for Shape-Aware, Scalable Refinement of k-Means Results [1.9580473532948401]
  After standard k-means, each cluster center is assigned a radius (the distance to its assigned point), and clusters whose radii overlap are merged.<n>This post-processing step loosens the requirement for exact k long as k is.<n>The method can often reconstruct non-estimated shapes over meaningful merges.
  arXiv  Detail & Related papers  (2025-04-28T22:30:53Z)
• Squeezed Attention: Accelerating Long Context Length LLM Inference [61.787865959140994]
  We propose Squeezed Attention to accelerate applications where a large portion of the input context is fixed.<n>During inference, we compare query tokens from the user input with the centroids to predict which keys from the fixed context are semantically relevant.<n>We also present a hierarchical version of our algorithm which can reduce the complexity of attention from linear to logarithmic with respect to the fixed context length.
  arXiv  Detail & Related papers  (2024-11-14T18:54:19Z)
• Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap [24.073221004661427]
  A simple model to study subspace clustering is the high-dimensional $k$-Gaussian mixture model. We provide an exact characterization of the statistically optimal reconstruction error in this model in the high-dimensional regime with extensive sparsity.
  arXiv  Detail & Related papers  (2022-05-26T17:47:35Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  We present a new branch-and-bound algorithm for semi-supervised MSSC. Background knowledge is incorporated as pairwise must-link and cannot-link constraints. For the first time, the proposed global optimization algorithm efficiently manages to solve real-world instances up to 800 data points.
  arXiv  Detail & Related papers  (2021-11-30T17:08:53Z)
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain [6.824747267214373]
  We propose the ParChain framework for designing parallel hierarchical agglomerative clustering (HAC) algorithms. Compared to most previous parallel HAC algorithms, our new algorithms require only linear memory, and are scalable to large data sets. Our algorithms are able to scale to data set sizes with tens of millions of points, which existing algorithms are not able to handle.
  arXiv  Detail & Related papers  (2021-06-08T23:13:27Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  In this work we consider the problem of center-based clustering of trajectories. We propose the usage of a continuous version of DTW as distance measure, which we call continuous dynamic time warping (CDTW) We show a practical way to compute a center from a set of trajectories and subsequently iteratively improve it.
  arXiv  Detail & Related papers  (2020-12-01T13:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.