Universality, Function Composition, and Algorithm Emulation All In-Context
Hong-Yu Chen, Po-Chiao Lin, Maojiang Su, Jerry Yao-Chieh Hu, Han Liu
Abstract
We study the in-context universal approximation and compositional generalization of softmax Transformers. We prove an in-context universality result: a fixed-weight softmax Transformer approximates a broad class of continuous sequence-to-sequence functions. Building on this universality, we establish a composition theorem: by concatenating prompts associated with simple ``subprograms,'' the same fixed Transformer executes their composition, and thereby synthesizes more complex programs on-the-fly. These results support a principled view of prompts as programs and fixed-weight Transformers as program interpreters. Moreover, we provide a concrete mechanism by which GPT-style models both execute and assemble algorithms in context.
BibTeX
@inproceedings{
hu2026incontext,
title={In-Context Universal Approximation, Compositional Generalization, and Algorithm Emulation},
author={Jerry Yao-Chieh Hu and Hong-Yu Chen and Po-Chiao Lin and Maojiang Su and Han Liu},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=ZK0U30zmDY}
}