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

Jerry Yao-Chieh Hu, Hong-Yu Chen, Po-Chiao Lin, Maojiang Su, Han Liu
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:44705-44798, 2026.

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.

Cite this Paper

BibTeX
@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.} }
Endnote
%0 Conference Paper %T In-Context Universal Approximation, Compositional Generalization, and Algorithm Emulation %A Jerry Yao-Chieh Hu %A Hong-Yu Chen %A Po-Chiao Lin %A Maojiang Su %A Han Liu %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-hu26h %I PMLR %P 44705--44798 %U https://proceedings.mlr.press/v306/hu26h.html %V 306 %X 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.
APA
Hu, J.Y., Chen, H., Lin, P., Su, M. & Liu, H.. (2026). In-Context Universal Approximation, Compositional Generalization, and Algorithm Emulation. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:44705-44798 Available from https://proceedings.mlr.press/v306/hu26h.html.

Related Material