Training-Free Universal Approximation by Prompting Random Transformers

This paper addresses the question of how expressive prompting is for transformer networks. The central finding is 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. The authors demonstrate this in an approximation-theoretic sense, showing that prompting alone can achieve universal approximation without any weight training.

The authors establish a connection between softmax attention and kernel methods, specifically showing that transformers can reproduce the Nadaraya-Watson (NW) kernel estimator in their forward pass. The approach is constructive: given a fixed transformer with random weights, the authors explicitly construct soft prompts as solutions to linear systems that match attention logits to Gaussian kernel exponents. Under this construction, the frozen transformer emulates the classical Nadaraya-Watson kernel estimator.

The paper states: "We show that prompting can reproduce the Nadaraya-Watson kernel estimator: given a single-layer softmax attention transformer whose weights satisfy a mild rank condition, and any set of n support points, we construct a soft prompt of prompt length n under which the transformer's output approximates the NW kernel estimator built on those points."

The hypothesis class consists of transformer networks with:

• An affine embedding layer (with zero padding in the deterministic case)

• One softmax single-headed attention layer

• An affine decoding layer

In the deterministic setting, the embedding maps input tokens to hidden dimension dh via homogeneous embedding with additional zero padding: E(x) = xemb:= [xT, 1, 0,..., 0]. The decoder reads out the bottom-right entry of the attention output.

The attention parameters must satisfy a rank condition: the matrix formed by the first din+1 rows of the query-key product matrix and the last column of the value matrix must have full row rank. The authors show this condition is satisfied almost surely under Gaussian initialization.

For any fixed set of n support points, there exists a soft prompt P* of length n such that the transformer output approximates the NW kernel estimator with error:

• O(1/(n2e2β)) · exp(3R2/h2) in squared error

• The soft prompt tokens have norm bounded by O(β + h−2)

The construction uses logit shifting (introducing a parameter β ≥ 0) to suppress the unwanted query self-attention term at an exponential rate.

For Hölder functions on a manifold, the prompted network achieves the minimax-optimal noisy approximation rate of Õ(n(−2α/(2α+dX))), where α is the Hölder exponent and dX is the intrinsic manifold dimension. This rate depends primarily on the intrinsic dimension, not the ambient dimension.

The error decomposition involves four terms:

1. The gap between transformer output and noisy kernel estimator (bounded by Theorem 1)

2. The noise term of the kernel estimator (Lemma 1): O(S2noise/(nh dX))

3. The finite-sample gap (Lemma 2): involves log(h−1)(3dX/4) · sqrt(log(4/δ)/(nh dX))

4. The kernel regression bias (Lemma 3): O(h α log(h−1))

The bandwidth and logit shift are chosen as h = n(−1/(2α+dX)) and β = (3R2/2)·n(2/(2α+dX)) (plus adaptive terms for random cases) to balance these terms.

With probability 1 over initialization, random Gaussian attention parameters satisfy the rank condition. The error bound becomes:

• CG/(n2e2β) · exp(3R2/h2), where CG is an almost surely finite random constant

• Token norms scale as O((β + h−2)/√dh) with high probability

When embedding and decoding are also random affine maps, the construction still works. The error bound involves a different random constant CG,aff, and token norms scale as O((β + h−2)/dh).

The paper tracks the cost of prompting in terms of prompt token magnitudes:

• Deterministic case (fixed embedding/decoding): O(n(2/(2α+dX)))

• Random attention: O(n(2/(2α+dX))/√dh + 1)

• Fully random transformers: O(n(2/(2α+dX))/dh + √dh)

The authors note: "The random versions distribute the constraints on each token densely across dh, which scales up W̃aff by a factor of √dh relative to W̃, whose zero padding embedding and coordinate readout decoding limit the constraints to a few rows."

Experiments on the unit sphere S2 ⊂ R3 validate:

1. Rank and σmin scaling: Minimum singular values scale as Ω(√dh) for Architecture A and Ω(dh) for Architecture B

2. Kernel approximation: The construction achieves the predicted n−2 scaling in prompt length and exponential decay in logit shift

3. Token norm bounds: Linear growth in logit shift as predicted

4. Minimax regression rate: The construction achieves the predicted n(−1/2) slope for α = 1, dX = 2, matching the oracle NW estimator

5. Prompt norm tradeoffs: Architecture A shows monotone decreasing norm with dh, while Architecture B shows a U-shaped curve reflecting the O(dh−1 + √dh) rate

The paper demonstrates that a single-layer softmax attention network with frozen random weights is a universal approximator under soft prompting. This separates the roles of prompting, architecture, and pretraining in transformer models, showing that task-specific behavior need not be stored in model weights but can be induced at inference time through the prompt alone. The results also connect to in-context learning, as the soft prompt is constructed based on the specific realization of weights and function but is independent of the query.

Improvement 1: Zero-Training Universal Function Approximation for Edge Deployment

The improved AI system can perform regression or classification on any continuous function (Hölder smooth) using a single-layer transformer with random, untrained weights, guided only by a constructed soft prompt. This eliminates backpropagation and GPU-based pretraining entirely. The system can be deployed on microcontrollers or edge devices with memory constraints, solving tasks like sensor calibration, anomaly detection, or low-dimensional control mapping (e.g., inverse kinematics) by simply computing a prompt from a few support points—no weight updates needed.

Improvement 2: Adaptive Prompt Construction for Dynamic Environments

The system can now adapt to non-stationary data streams in real time. Given a frozen transformer, it can recompute the soft prompt on-the-fly as new support points arrive, achieving the minimax-optimal regression rate Õ(n(−2α/(2α+dX))) without retraining. This enables continuous learning in robotics (e.g., adjusting to changing terrain friction) or financial forecasting (e.g., shifting market regimes) where model weights are fixed but prompts are updated every timestep, with provable error guarantees.

Improvement 3: Intrinsic-Dimension-Aware Prompt Engineering

The system can automatically estimate the intrinsic manifold dimension dX of the input data (via the prompt norm scaling) and choose the optimal bandwidth h and logit shift β accordingly. This yields near-optimal accuracy even when data lies on a low-dimensional manifold embedded in high-dimensional space (e.g., images on a 3D pose manifold). The improved system can then generate prompts that are exponentially smaller in norm than naive ambient-dimension approaches, reducing memory and compute for prompt storage.

Improvement 4: Uncertainty-Aware Prompting via Kernel Noise Control

By leveraging the explicit error decomposition (noise term, finite-sample gap, bias), the system can output confidence intervals alongside predictions. For any query, it can compute the variance of the underlying Nadaraya-Watson estimator and propagate it through the transformer’s forward pass, providing calibrated uncertainty estimates. This is critical for safety-critical applications like medical diagnosis or autonomous driving, where the system flags low-confidence predictions for human review.

Improvement 5: Prompt-Norm Regularization for Resource-Constrained Inference

The system can trade off prompt token magnitude against approximation error, as characterized by the O(n(2/(2α+dX))/dh) scaling. It can automatically select the smallest prompt norm that meets a user-specified error tolerance, minimizing energy consumption in battery-powered devices. For fully random transformers, it can choose the hidden dimension dh to balance the U-shaped prompt norm curve, finding the sweet spot where prompt storage is minimal.

Improvement 6: Zero-Shot In-Context Learning with Provable Guarantees

The system can perform in-context learning (ICL) without any pretraining, using only random weights. Given a few labeled examples in the prompt, it can generalize to new queries with the same theoretical guarantees as a trained kernel regressor. This enables few-shot classification or regression in novel domains (e.g., new languages, new sensor types) where no fine-tuning is possible, with explicit error bounds that degrade gracefully as n (number of examples) decreases.

Improvement 7: Robustness to Weight Perturbations and Hardware Noise

Because the construction only requires a mild rank condition (satisfied almost surely under Gaussian initialization), the system is inherently robust to small weight perturbations—e.g., from analog hardware, quantization, or radiation-induced bit flips. The improved system can verify the rank condition on-device and, if it fails, apply a fixed random rotation to the weights (without training) to restore solvability, ensuring reliable operation in harsh environments like space or nuclear reactors.

Improvement 8: Multi-Task Prompting via Shared Random Backbone

A single frozen transformer can serve multiple tasks simultaneously by concatenating task-specific prompts into a longer sequence. The system can allocate prompt length per task based on each task’s Hölder smoothness α, achieving per-task minimax rates without cross-task interference. This enables multi-modal AI assistants (e.g., vision + language + control) on a single chip, where each modality’s prompt is independently optimized while sharing the same random attention weights.