# The Expressibility of Polynomial based Attention Scheme arXiv: https://arxiv.org/abs/2310.20051 · HTML: https://mlsanity.com/paper/2310.20051/ ## Key facts - Cited by 7 papers in the map (data through 14 Oct 2026). - Builds on 77 of its 112 references that are in the map. - First posted on arXiv 30 Oct 2023. ## Builds on (most cited first, 30 of 77) - [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017) - [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018) - [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020) - [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020) - [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019) - [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023) - [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023) - [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017) - [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023) - [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022) - [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021) - [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022) - [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022) - [ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks](https://mlsanity.com/paper/1908.02265/) (2019) - [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023) - [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020) - [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020) - [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020) - [Show, Attend and Tell: Neural Image Caption Generation with Visual Attention](https://mlsanity.com/paper/1502.03044/) (2015) - [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018) - [Discovering Latent Knowledge in Language Models Without Supervision](https://mlsanity.com/paper/2212.03827/) (2022) - [MetaMath: Bootstrap Your Own Mathematical Questions for Large Language Models](https://mlsanity.com/paper/2309.12284/) (2023) - [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022) - [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022) - [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022) - [Knowledge Neurons in Pretrained Transformers](https://mlsanity.com/paper/2104.08696/) (2021) - [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017) - [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021) - [Who's Harry Potter? Approximate Unlearning in LLMs](https://mlsanity.com/paper/2310.02238/) (2023) - [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023) ## Built on by (most cited first, 7 of 7) - [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024) - [Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers](https://mlsanity.com/paper/2405.05219/) (2024) - [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024) - [Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretraining](https://mlsanity.com/paper/2502.05790/) (2025) - [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025) - [CoVE: Compressed Vocabulary Expansion Makes Better LLM-based Recommender Systems](https://mlsanity.com/paper/2506.19993/) (2025) - [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025) ## Abstract (arXiv) Large language models (LLMs) have significantly improved various aspects of our daily lives. These models have impacted numerous domains, from healthcare to education, enhancing productivity, decision-making processes, and accessibility. As a result, they have influenced and, to some extent, reshaped people's lifestyles. However, the quadratic complexity of attention in transformer architectures poses a challenge when scaling up these models for processing long textual contexts. This issue makes it impractical to train very large models on lengthy texts or use them efficiently during inference. While a recent study by [KMZ23] introduced a technique that replaces the softmax with a polynomial function and polynomial sketching to speed up attention mechanisms, the theoretical understandings of this new approach are not yet well understood. In this paper, we offer a theoretical analysis of the expressive capabilities of polynomial attention. Our study reveals a disparity in the ability of high-degree and low-degree polynomial attention. Specifically, we construct two carefully designed datasets, namely D0 and D1, where D1 includes a feature with a significantly larger value compared to D0. We demonstrate that with a sufficiently high degree β, a single-layer polynomial attention network can distinguish between D0 and D1. However, with a low degree β, the network cannot effectively separate the two datasets. This analysis underscores the greater effectiveness of high-degree polynomials in amplifying large values and distinguishing between datasets. Our analysis offers insight into the representational capacity of polynomial attention and provides a rationale for incorporating higher-degree polynomials in attention mechanisms to capture intricate linguistic correlations.