Training-Free Universal Approximation by Prompting Random Transformers

Alexander Hsu; Rongjie Lai

cs.LGAug 10, 2026

Training-Free Universal Approximation by Prompting Random Transformers

Authors: Alexander Hsu, Rongjie Lai

Abstract

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.

Explore similar work

Apr 27, 2026cs.LG

Transformer Approximations from ReLUs

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.

Jerry Yao-Chieh Hu, Mingcheng Lu, Yi-Chen Lee +1

Gumbel-Softmax Relaxation Rectified Linear Unit Transformer Architectures Approximation Economies

Ask PDF

May 9, 2026stat.ML

Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity

This paper investigates the learning theory of Transformer networks for regression tasks on the compact Euclidean domain

[0,1]^d

and

d

-dimensional compact Riemannian manifolds. We propose a novel constructive approximation framework for Transformers that builds local approximations of the target function and aggregates them into a global approximation via softmax partition of unity. This approach leverages the attention mechanism to achieve spatial localization through affine transformations of the input. The softmax activation plays a crucial role in aggregating local approximations to a global output. From an approximation perspective, we prove that a dense Transformer equipped with only two encoder blocks and standard single-hidden-layer point-wise feed-forward networks can achieve a uniform

\varepsilon

-approximation error for

α

-Hölder continuous functions with

α\in (0,1]

using

\mathcal{O}(\varepsilon^{-d/α})

total parameters. Building upon this approximation guarantee, we establish a near minimax-optimal generalization error bound of order

\mathcal{O}\big(n^{-\frac{2α}{2α+d}} \log n\big)

for the empirical risk minimizer, where

n

is the training data size. The Transformer architecture studied in this paper is dense, shallow and wide, and employs softmax activation and sinusoidal positional encodings, closely reflecting practical implementations.

Zhongjie Shi, Wenjing Liao

Transformer Architectures Approximation Activation Functions Generalization Bounds Feed-Forward Network Partitioning

Ask PDF

May 8, 2026cs.LG

Approximation Error Upper and Lower Bounds for Hölder Class with Transformers

We explore the expressive power of Transformers by establishing precise approximation error upper and lower bounds for Hölder class. Specifically, a new approximation upper bound is derived for the standard Transformer architecture equipped with Softmax operators, ReLU activation functions, and residual connections. We prove that a Transformer network composed of at most

\mathcal{O}(\varepsilon^{-{d_{0}}/α})

blocks can approximate any bounded Hölder function with

d_{0}

-dimensional input and smoothness

α\in(0,1]

under any accuracy

\varepsilon>0

. In the case of approximation lower bounds, leveraging the VC-dimension upper bound, we are the first to rigorously prove that Transformers demand for at least

Ω(\varepsilon^{-{d_{0}}/({4α})})

blocks to achieve the

\varepsilon

approximation accuracy. As a final step, we extend the derived results for standard Transformers to a general regression task and establish the corresponding excess risk rates demonstrating Transformers' empirical effectiveness in real-world settings.

Xin He, Yuling Jiao, Xiliang Lu +1

Transformer Architectures Generalization Bounds Approximation Lower Bounds Expressivity

Ask PDF