Zhe Xu, Hanghang Tong, Ruizhong Qiu, Wenxuan Bao
We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.
Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.
Since the success of GPT, large language models (LLMs) have been revolutionizing machine learning and have initiated the so-called LLM prompting paradigm. In the era of LLMs, people train a single general-purpose LLM and provide the LLM with different prompts to perform different tasks. However, such empirical success largely lacks theoretical understanding. Here, we present the first theoretical study on the LLM prompting paradigm to the best of our knowledge. In this work, we show that prompting is in fact Turing-complete: there exists a finite-size Transformer such that for any computable function, there exists a corresponding prompt following which the Transformer computes the function. Furthermore, we show that even though we use only a single finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unboundedsize Transformers. Overall, our result reveals that prompting can enable a single finite-size Transformer to be efficiently universal, which establishes a theoretical underpinning for prompt engineering in practice. Published as a conference paper at ICLR 2025 Main contributions. Our main contributions are informally stated as follows: • Expressive power. We show that prompting is Turing-complete: there exists a finite-size Transformer Γ such that for any computable function ϕ, there exists a finite prompt π ϕ such that for any input x, the Transformer Γ computes ϕ(x) following the prompt π ϕ . Importantly, our constructed Transformer Γ is independent of the function ϕ, the prompt π ϕ is independent of the input x, and the input x can be arbitrarily long. • Simple construction. In fact, it is not hard to deduce the existence of such a Transformer Γ by combining Theorem 1 of Hennie & Stearns (1966) and Theorem 3.4 of Pérez et al. ( 2019), but explicitly constructing the Transformer via that approach is cumbersome. Instead, we provide a simple constructive proof, which makes it easy to further study the properties of the construction such as CoT complexity and precision complexity. • CoT complexity. We show that our Γ can compute any TIME 2 (t(n)) function within O(t(n)) CoT steps and can compute any TIME(t(n)) function within O(t(n) log t(n)) CoT steps for any length-n input. Notably, our result shows that even a single Transformer can still achieve nearly the same CoT complexity as the class of all Transformers does. • Precision complexity. We show that our Γ can compute any TIME(t(n)) function within O(log(n + t(n) )) bits of precision for any length-n input. Notably, our result shows that even a single Transformer can still achieve the same precision complexity as the class of all Transformers does. In particular, Γ can decide any P language within log-precision.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("2411.01992")
get_code_for_paper("2411.01992")
have("2411.01992")
The run record, dated, one paper per request, free:
curl https://syntology.ai/api/ran/2411.01992.json
A badge for a README (the split and the date, never a ratio):
[](https://syntology.ai/paper/2411.01992)
Connect an agent — have() is free.