PoM: A Linear-Time Replacement for Attention with the Polynomial Mixer

David Picard; Nicolas Dufour; Lucas Degeorge; Arijit Ghosh; Davide Allegro; Tom Ravaud; Yohann Perron; Corentin Sautier

cs.CVApr 7, 2026

PoM: A Linear-Time Replacement for Attention with the Polynomial Mixer

Authors: David Picard, Nicolas Dufour, Lucas Degeorge, Arijit Ghosh, Davide Allegro, Tom Ravaud, Yohann Perron, Corentin Sautier,

Organizations: LIGM, CNRS, Univ Gustave Eiffel, ENPC, Institut Polytechnique de Paris, France · LIX, École Polytechnique, CNRS, IP Paris, France · AMIAD, Pole recherche · Department of Information Engineering, Università degli Studi di Padova, Italy ·

Abstract

This paper introduces the Polynomial Mixer (PoM), a novel token mixing mechanism with linear complexity that serves as a drop-in replacement for self-attention. PoM aggregates input tokens into a compact representation through a learned polynomial function, from which each token retrieves contextual information. We prove that PoM satisfies the contextual mapping property, ensuring that transformers equipped with PoM remain universal sequence-to-sequence approximators. We replace standard self-attention with PoM across five diverse domains: text generation, handwritten text recognition, image generation, 3D modeling, and Earth observation. PoM matches the performance of attention-based models while drastically reducing computational cost when working with long sequences. The code is available at https://github.com/davidpicard/pom.

Figures & tables

Panel of Figure 3 — Figure 3: Evaluation Across Domains. We evaluate PoM on various tasks from multiple domains, simply replacing some or all the self-attention blocks in SOTA Transformer-based models. Left : For OCR, given a page of handwritten text (top) split into lines, the goal is to recognize each character and group them into words (bottom). Middle : For Earth observation, given a time series of satellite images (top), the goal is to classify each pixel as a crop type by the end of the series (bottom). Right : For 3D segmentation, given a 3D point cloud (top), the goal is to classify each point according to classes (bottom).

Table 1: Natural Language Processing.

	#Params	Performance		Throughput
Model	$\times 10^{6}$	OA $\uparrow$	mIoU $\uparrow$	km 2 /s
TSViT (paper)	1.7	83.4	65.1	-
TSViT (retrained)	1.7	82.8	64.6	7.2
TSViPoM	1.7	82.7	64.6	26.3

Table 3: Satellite Image Time Series Segmentation. We compare of TSViT and TSViPoM on PASTIS fold 1. We report the overall accuracy (OA), mean IoU (mIoU), and throughput.

		#Param	Performance	Throughput
	Model	$\times 10^{6}$	mIoU $\uparrow$	$10^{6}$ pts/s
Scannet	PTv3	46.2	76.7	1.98
	PPoMv3	47.9	75.9	2.17
	PPoMv3 Hyb.	46.8	76.8	2.01
SKITTI	PTv3	46.2	67.2	1.12
	PPoMv3	47.9	66.6	1.22

Table 4: 3D Point Cloud Segmentation. We compare PTv3 with PPoMv3 on two classic 3D datasets.

Panel of Figure 4 — Figure 4: Computational Efficiency. We report the speed at generating image for various resolutions for SiT-XL/2 and its PoM counterpart SiPoM-XL/2.

Figure 5: Qualitative Results on Class-Conditional Generation . Images sampled from SiPom-XL/2 with different classes at 256 resolution. We use classifier-free guidance with $\omega=6$ .

	#Param	Performance	Throughput
Model	$\times 10^{6}$	FID $\downarrow$	img/s
SiT-L/2	458	18.8	1, 9842
SiPoM-L/2	414	17.6	11,954
SiT-XL/2	675	17.2	1, 4041
SiPoM-XL/2	609	17.2	1, 8146

Table 5: Class-Conditional Image Generation . We compare SiT [ 52 ] with SiPoM trained on ImageNet for generating images of resolution 256 2 for a batch size of 1024.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

	ARC-easy Acc.Norm $\uparrow$	HellaSwag Acc.Norm $\uparrow$	Winogrande Acc. $\uparrow$	Throughput 4096 tok., tok/s $\uparrow$
PoM-hyb k=2	29.0	33.8	51.9	163
PoM-hyb k=3	29.5	33.4	49.6	161
PoM-hyb k=5	28.6	33.9	49.5	153
MHA	29.4	33.3	49.4	42
Performer	training failed			59
Mamba	29.3	30.8	48.0	384

Appendix

Table 6: Additional ablations and baselines. MHA throughput uses Flash-Attention, Performer uses torch_geometric .

Panel of Figure 6 — Figure 6: Uncurated 256² images for the class loggerhead, loggerhead turtle, Caretta caretta (33).

Panel of Figure 7 — Figure 7: Uncurated 256² images for the class macaw (88).

Panel of Figure 8 — Figure 8: Uncurated 256² images for the class otter (360).

Panel of Figure 9 — Figure 9: Uncurated 256² images for the class volcano (980).

Self-Attention

Self-attention lets sequence elements exchange context through learned query-key matches, powering Transformers and their efficient variants.

See all 225 papers

Polynomial Mixing for Efficient Self-supervised Speech Encoders
Feb 28, 2026Eva Feillet, Ryan Whetten, David Picard +1Speech Processing Self-Supervised Speech Representation Learning
Universit´e Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Num´erique · Miles team, Universit´e Paris-Dauphine-PSL · Laboratoire Informatique d’Avignon, Avignon Universit´e +1
Controllably Efficient Language Models
Nov 7, 2025Jatin Prakash, Aahlad Puli, Rajesh RanganathEfficient Transformer Inference Long-Context Language Modeling
New York University
Multi-Mixer Models: Flexible Sequence Modeling with Shared Representations
May 27, 2026Kevin Y. Li, Asher Trockman, Ananda Theertha Suresh +1Parameter Sharing Transformer Attention
Carnegie Mellon University · Google Research

Feb 28, 2026J/K move · Enter open · S save

Polynomial Mixing for Efficient Self-supervised Speech Encoders

Eva Feillet, Ryan Whetten, David Picard, Alexandre Allauzen

Universit´e Paris-Saclay, CNRS, Laboratoire Interdisciplinaire des Sciences du Num´erique · Miles team, Universit´e Paris-Dauphine-PSL · Laboratoire Informatique d’Avignon, Avignon Universit´e+1

Speech Processing Self-Supervised Speech Representation Learning

Open paper AskPDF arXiv

State-of-the-art speech-to-text models typically employ Transformer-based encoders that model token dependencies via self-attention mechanisms. However, the quadratic complexity of self-attention in both memory and computation imposes significant constraints on scalability. In this work, we propose a novel token-mixing mechanism, the Polynomial Mixer (PoM), as a drop-in replacement for multi-head self-attention. PoM computes a polynomial representation of the input with linear complexity with respect to the input sequence length. We integrate PoM into a self-supervised speech representation learning framework based on BEST-RQ and evaluate its performance on downstream speech recognition tasks. Experimental results demonstrate that PoM achieves a competitive word error rate compared to full self-attention and other linear-complexity alternatives, offering an improved trade-off between performance and efficiency in time and memory.

Abstract

Self-Attention

Explore similar work

Polynomial Mixing for Efficient Self-supervised Speech Encoders

Controllably Efficient Language Models

Multi-Mixer Models: Flexible Sequence Modeling with Shared Representations