Ask, and it shall be given: Turing completeness of prompting

• URL: http://arxiv.org/abs/2411.01992v1
• Date: Mon, 04 Nov 2024 11:26:38 GMT
• Title: Ask, and it shall be given: Turing completeness of prompting
• Authors: Ruizhong Qiu, Zhe Xu, Wenxuan Bao, Hanghang Tong,
• Abstract summary: Large language models (LLMs) have been revolutionizing machine learning and initiated the so-called LLM prompting paradigm. Here, we present the first theoretical study on the LLM prompting paradigm to the best of our knowledge. We show that prompting is 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.
• Score: 47.08833920586575
• License:
• 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.

Related papers

• Provably Transformers Harness Multi-Concept Word Semantics for Efficient In-Context Learning [53.685764040547625]
  Transformer-based large language models (LLMs) have displayed remarkable creative prowess and emergence capabilities. This work provides a fine mathematical analysis to show how transformers leverage the multi-concept semantics of words to enable powerful ICL and excellent out-of-distribution ICL abilities.
  arXiv  Detail & Related papers  (2024-11-04T15:54:32Z)
• Supervised Chain of Thought [5.389461633686935]
  Chain of Thought (CoT) prompting offers a promising approach to solving complex reasoning tasks. One-prompt-for-all approach poses significant challenges for models to generate the correct reasoning steps. We show how task-specific supervision is essential for navigating the prompt space accurately and achieving optimal performance.
  arXiv  Detail & Related papers  (2024-10-18T06:25:27Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  We study transformers' ability to learn random $n$-gram LMs of two kinds. We find that classic estimation techniques for $n$-gram LMs such as add-$lambda$ smoothing outperform transformers.
  arXiv  Detail & Related papers  (2024-10-03T21:21:02Z)
• Large Language Models and the Extended Church-Turing Thesis [0.0]
  We investigate the computational power of large language models (LLMs) by the classical means of computability and computational complexity theory. We show that any fixed (non-adaptive) LLM is computationally equivalent to a, possibly very large, deterministic finite-state transducer. We discuss the merits of our findings in the broader context of several related disciplines and philosophies.
  arXiv  Detail & Related papers  (2024-09-11T03:09:55Z)
• In-Context Learning with Representations: Contextual Generalization of Trained Transformers [66.78052387054593]
  In-context learning (ICL) refers to a capability of pretrained large language models, which can learn a new task given a few examples during inference. This paper investigates the training dynamics of transformers by gradient descent through the lens of non-linear regression tasks.
  arXiv  Detail & Related papers  (2024-08-19T16:47:46Z)
• Universal Approximation Theory: The Basic Theory for Transformer-based Large Language Models [9.487731634351787]
  Large-scale Transformer networks have quickly become the leading approach for advancing natural language processing algorithms. This paper explores the theoretical foundations of large language models (LLMs) It offers a theoretical backdrop, shedding light on the mechanisms that underpin these advancements.
  arXiv  Detail & Related papers  (2024-07-01T04:29:35Z)
• Sumformer: Universal Approximation for Efficient Transformers [2.4832703558223725]
  We introduce Sumformer, a novel and simple architecture capable of universally approxingimating sequence-to-sequence functions. We derive a new proof for Transformers, showing that just one attention layer is sufficient for universal approximation.
  arXiv  Detail & Related papers  (2023-07-05T13:59:35Z)
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective [39.47116013338394]
  Chain-of-Thought prompting (CoT) can dramatically improve the performance of Large Language Models (LLMs) We show that CoT can handle a general class of decision-making problems known as Dynamic Programming.
  arXiv  Detail & Related papers  (2023-05-24T17:59:21Z)
• Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
  We mathematically analyze the power of RPE-based Transformers regarding whether the model is capable of approximating any continuous sequence-to-sequence functions. We present a negative result by showing there exist continuous sequence-to-sequence functions that RPE-based Transformers cannot approximate no matter how deep and wide the neural network is. We develop a novel attention module, called Universal RPE-based (URPE) Attention, which satisfies the conditions.
  arXiv  Detail & Related papers  (2022-05-26T14:51:30Z)
• Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations [51.77000472945441]
  Long Short-Term Memory (LSTM) and Transformers are two popular neural architectures used for natural language processing tasks. In practice, it is often observed that Transformer models have better representation power than LSTM. We study such practical differences between LSTM and Transformer and propose an explanation based on their latent space decomposition patterns.
  arXiv  Detail & Related papers  (2021-12-16T19:56:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.