Transformer Approximations from ReLUs

Jerry Yao-Chieh Hu; Mingcheng Lu; Yi-Chen Lee; Han Liu

cs.LGApr 27, 2026

Transformer Approximations from ReLUs

Authors: Jerry Yao-Chieh Hu, Mingcheng Lu, Yi-Chen Lee, Han Liu

Organizations: Center for Foundation Models and Generative AI, Northwestern University, Evanston, IL 60208, USA · Department of Computer Science, Northwestern University, Evanston, IL 60208, USA · Department of Physics, National Taiwan University, Taipei 10617, Taiwan · ♯Department of Statistics and Data Science, Northwestern University, Evanston, IL 60208, USA

Abstract

We provide a systematic recipe for translating ReLU approximation results to softmax attention mechanism. This recipe covers many common approximation targets. Importantly, it yields target-specific, economic resource bounds beyond universal approximation statements. We showcase the recipe on multiplication, reciprocal computation, and min/max primitives. These results provide new analytical tools for analyzing softmax transformer models.

Explore similar work

Training-Free Universal Approximation by Prompting Random Transformers
Aug 10, 2026Alexander Hsu, Rongjie LaiSoftmax Attention Approximation
The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
May 18, 2026Moritz Brösamle, Stephan EcksteinTransformer Layers Gumbel-Softmax Relaxation
Vertex-Softmax: Tight Transformer Verification via Exact Softmax Optimization
May 8, 2026Navid Rezazadeh, Arash Gholami DavoodiGumbel-Softmax Relaxation Transformer Attention

Aug 10, 2026 · cs.LGJ/K move · Enter open · S save

Training-Free Universal Approximation by Prompting Random Transformers

Alexander Hsu, Rongjie Lai

How expressive is prompting a transformer? Answering this question is important for separating the roles of prompting, architecture, and pretraining in transformer models, and for determining whether task-specific behavior must be stored in model weights or can instead be induced at inference time through the prompt. We show, in an approximation-theoretic sense, that pretraining is optional: a single-layer softmax attention network with random, untrained weights can approximate any Hölder function on a compact manifold when steered by an appropriate soft prompt. Guided by the connection between softmax attention and kernel methods, we construct explicit soft prompts (a prompt per target function, independent of the query) as solutions to linear systems matching attention logits to Gaussian kernel exponents, under which the frozen transformer emulates the classical Nadaraya-Watson kernel estimator. The construction requires only a mild rank condition on the weights, which we show holds almost surely under Gaussian initialization. The prompted network inherits the theoretical guarantees of kernel regression, leading to universal approximation theorems with minimax-optimal rates that depend on the intrinsic dimension. We further quantify the cost of prompting, exposing a tradeoff between the norm of the constructed soft prompt tokens, prompt length, and hidden dimension. Numerical experiments corroborate the constructions and predicted rates.

Softmax Attention Approximation Prompt Engineering Training-Free 3D Gaussian Splatting

Open paper Ask about it PDF

Abstract

Explore similar work

Training-Free Universal Approximation by Prompting Random Transformers

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought

Vertex-Softmax: Tight Transformer Verification via Exact Softmax Optimization