In-Context Universal Approximation, Compositional Generalization, and Algorithm Emulation

We study in-context universal approximation and compositional generalization in frozen softmax Transformers as prompt-programmable computation. We prove in-context universality via in-context emulation: a fixed-weight Transformer emulates target computations specified by the prompt and hence approximates a broad class of continuous sequence-to-sequence functions. Building on this view, we establish one-pass and multi-pass composition theorems: prompts associated with simple ``subprograms'' let the same fixed Transformer execute their composition and thereby synthesize more complex programs on-the-fly. These results support a principled view of prompts as programs and fixed-weight Transformers as program interpreters. They also provide concrete mechanisms by which GPT-style models execute and assemble algorithms in context. Please see arXiv for the full version.

Modern AI models can do many tasks by changing only the prompt. Their internal settings often stay fixed. This paper studies why this is possible. We focus on a simple idea: a prompt can act like a program. The prompt tells the model what computation to run. The input gives the data for that computation. The model then follows the prompt and produces the output. We prove this idea in a mathematical setting. We show that one fixed Transformer can approximate many different input-output rules. The model does not need to be retrained for each rule. Only the prompt changes. We also study multi-step tasks. In many real uses, a person asks a model to do one step, then another step, and then combine the results. We prove that prompts for simple steps can be assembled so the same fixed model executes the full composed task. Together, these results give a theory of prompts as programs and Transformers as program executors.