ICML 2026
In-Context Universal Approximation, Compositional Generalization, and Algorithm Emulation
Prompts act as programs; a fixed-weight transformer executes and composes them.
Abstract
We study in-context universal approximation and compositional generalization in softmax transformers with fixed weights. A prompt specifies the computation to perform, while the transformer serves as an interpreter. We prove that a fixed-weight transformer can approximate a broad class of continuous sequence-to-sequence functions through this in-context emulation mechanism. We also establish composition results: prompts for simpler computations can be combined so that the same transformer executes their composition. The results give a constructive perspective on how a single model can carry out different algorithms and assemble more complex computations without task-specific weight updates.
Key results
In-context universality
Construct a fixed-weight softmax transformer that approximates a broad class of continuous sequence-to-sequence functions using task-specific prompts.
Compositional generalization
Show how prompts for simpler computations allow the same model to execute their composition.
A program-interpreter view
Separate the task description from the computation engine, offering a theoretical account of prompt-programmable behavior.
BibTeX
Official BibTeX from PMLR.
@InProceedings{pmlr-v306-hu26h,
title = {In-Context Universal Approximation, Compositional Generalization, and Algorithm Emulation},
author = {Hu, Jerry Yao-Chieh and Chen, Hong-Yu and Lin, Po-Chiao and Su, Maojiang and Liu, Han},
booktitle = {Proceedings of the 43rd International Conference on Machine Learning},
pages = {44705--44798},
year = {2026},
editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto},
volume = {306},
series = {Proceedings of Machine Learning Research},
month = {06--11 Jul},
publisher = {PMLR},
pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/hu26h/hu26h.pdf},
url = {https://proceedings.mlr.press/v306/hu26h.html},
abstract = {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.}
}