REVIEW 4 cited by
Ask, and it shall be given: On the Turing completeness of prompting
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
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 unbounded-size 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.
Forward citations
Cited by 4 Pith papers
-
Hierarchical Domain Generalization
Over infinite domains, hierarchy-uniform domain generalization is impossible for every nontrivial hypothesis class; a length-generalization bound is a property of the length hierarchy, not a hierarchy-free guarantee.
-
SelfElicit: Your Language Model Secretly Knows Where is the Relevant Evidence
SelfElicit uses deep-layer attention to automatically highlight relevant evidence sentences in the input context, yielding consistent QA accuracy gains across six instruction-tuned LLMs.
-
Breaking Silos: Adaptive Model Fusion Unlocks Better Time Series Forecasting
A learnable fusor that reads meta-features of an input time series and weights 13 pre-trained forecasters per sample outperforms each individual model on most benchmark samples, including zero-shot settings.
-
A Survey on Latent Reasoning
A survey that organizes latent reasoning methods into vertical recurrence, horizontal recurrence, and infinite-depth diffusion, arguing that silent reasoning can beat explicit chain-of-thought.
Discussion (0). Continue with ORCID to comment.