Training-Free Universal Approximation by Prompting Random Transformers

TL;DR - A theory paper showing that a single-layer softmax attention network with random, untrained weights can universally approximate Hölder functions on a compact manifold when steered by a suitably constructed soft prompt — implying that, in an approximation-theoretic sense, pretraining is optional and task behavior can live in the prompt rather than the weights.

• Soft prompts are constructed explicitly (one per target function, independent of the query) by solving linear systems that match attention logits to Gaussian kernel exponents, making the frozen transformer emulate the classical Nadaraya-Watson kernel estimator.
• The construction needs only a mild rank condition on the weights, which the authors show holds almost surely under Gaussian initialization.
• Because it inherits kernel-regression guarantees, the prompted network achieves universal approximation with minimax-optimal rates governed by the data's intrinsic dimension, not the ambient one.
• The paper quantifies the "cost of prompting" as a tradeoff among soft-prompt token norm, prompt length, and hidden dimension, with numerical experiments corroborating the constructions and predicted rates.