Skip to content
The methodOpen data
Back to the collection

Are Transformers universal approximators of sequence-to-sequence functions?

Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, Sanjiv Kumar

2019 · arXiv

Language models
Read the paper
HN score
1
Mentions
6
Readers
6
Months
5
What’s in a score?

From the abstract

Despite the widespread adoption of Transformer models for NLP tasks, the expressive power of these models is not well-understood. In this paper, we establish that Transformer models are universal approximators of continuous permutation equivariant sequence-to-sequence functions with compact support, which is quite surprising given the amount of shared parameters in these models. Furthermore, using positional encodings, we circumvent the restriction of permutation equivariance, and show that Transformer models can universally approximate arbitrary continuous sequence-to-sequence functions on a compact domain. Interestingly, our proof techniques clearly highlight the different roles of the self-attention and the feed-forward layers in Transformers. In particular, we prove that fixed width self-attention layers can compute contextual mappings of the input sequences, playing a key role in the universal approximation property of Transformers. Based on this insight from our analysis, we consider other simpler alternatives to self-attention layers and empirically evaluate them.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

6 selected excerpts · 6 total mentions

triclops200
Recommendation · rule
As a researcher in these fields: this reasoning is tired, overblown, and just wrong. We have a lot of understanding of how the brain works overall. You don't. Go read the active inference book by Friston et. al. for some of the epistemological and behavioral mechanics (Yes, this applies to llms as well, they easily satisfy the requirements to be considered the mathematical object described as a markov blanket). And, yes, if you could somehow freeze a human's current physical configuration at some time, you would absolutely, in principle, given what we know about the universe, be able to concretely map input to into actions. You cannot separate a human's representative…
Read the full comment
configuration from their environment in this way, so, behavior appears much more non-deterministic. Another paper by Friston et al (Path Integrals, particular kinds, and strange things) describes systems much like modern modeling and absolutely falls under the same action minimization requirements for the math to work given the kinds of data acquisition, loss functions, and training/post-training we're doing as a research society with these models. I also recommend https://arxiv.org/abs/2112.04035, but, in short, transformer models have functions and emergent structures provably similar both empirically and mathematically to how we abstract and consider things. Along with https://arxiv.org/pdf/1912.10077, these 4 sources, alone, together strongly rebuke any idea that they are somehow not capable of learning to act like and think like us, though there's many more.
Original comment The Case That A.I. Is Thinking
solid_fuel
Neutral mention · rule
1) You’re still wrong, this is prompt injection. 2) You continue to have basic misunderstandings of the issue. That bugs exist in other things does not mean a core design flaw in LLMs can magically be fixed. 3) https://arxiv.org/pdf/1912.10077 This paper doesn’t have any bearing to the question of the separation of user and command data in LLMs. Did you even bother to look at it? 4) Hey you’re the one that made the claim. If you can't event remember why, I can’t help you. 5) Because the world is stateful. 6) Wow so you just decided to add up all the ram after all, huh? If you want to play stupid, like you can’t understand why a real-world linux distribution is stateful…
Read the full comment
while an ideal LLM isn’t, then we can play stupid. By the broken logic you are trying to apply here, the state space of chatGPT includes the VRAM of all 10,000 GPUs your query runs across. It includes the memory in your computer, it includes the stack of the js interpreter in your browser, it includes the linux kernel itself that all those servers are running on, and so on.
Original comment ChatGPT Spontaneously Generates Sexual Violence and Hardcore Snuff Imagery
anuramat
Neutral mention · rule
> yes it is agree to disagree > every LLM has been vulnerable and every OS had bugs > show the logic https://arxiv.org/pdf/1912.10077 > you are the one asserting mappings existed I know? that's why I'm asking? > no useful system can be a pure function why not? surely you can describe useful systems with qm? evolution operator of a closed system seems pretty pure to me it's almost as if you could reformulate anything such that the state was one of the arguments of the function > you can start adding up the state space for the linux kernel I can give you a lower bound -- (your estimate for LLMs)*2, as you could imagine state "running two instances of llama-cpp"
Original comment ChatGPT Spontaneously Generates Sexual Violence and Hardcore Snuff Imagery
hodgehog11
Neutral mention · rule
Fine, that's fair. I believe the statement that you made is countered by my claim, which is: Theorem. For any tolerance epsilon > 0, there exists a transformer neural network of sufficient size that follows, up to the factor epsilon, the policy that most optimally achieves arbitrary goals in arbitrary stochastic environments. Proof (sketch). For any stochastic environment with a given goal, there exists a model that maximizes expected return under this goal (not necessarily unique, but it exists). From Solomonoff's convergence theorem (Theorem 3.19 in [1]), Bayes-optimal predictors under the universal Kolmogorov prior converge with increasing context to this model.…
Read the full comment
Consequently, there exists an agent (called the AIXI agent) that is Pareto-optimal for arbitrary goals (Theorem 5.23 in [1]). This agent is a sequence-to-sequence map with some mild regularity, and satisfies the conditions of Theorem 3 in [2]. From this universal approximation theorem (itself proven in Appendices B and C in [2]), there exists a transformer neural network of a sufficient size that replicates the AIXI agent up to the factor epsilon. This is effectively the argument made in [3], although I'm not fond of their presentation. Now, practitioners still cry foul because existence doesn't guarantee a procedure to find this particular architecture (this is the constructive bit). This is where the neural scaling law comes in. The trick is to work with a linearization of the network, called the neural tangent kernel; it's existence is guaranteed from Theorem 7.2 of [4]. The NTK predictors are also universal and are a subset of the random feature models treated in [5], which derives the neural scaling laws for these models. Extrapolating these laws out as per [6] for specific tasks shows that the "floor" is always below human error rates, but this is still empirical because it works with the ill-defined definition of superintelligence that is "better than humans in all contexts". [1] Hutter, M. (2005). Universal artificial intelligence: Sequential decisions based on algorithmic probability. Springer Science & Business Media. [2] https://arxiv.org/abs/1912.10077 [3] https://openreview.net/pdf?id=Vib3KtwoWs [4] https://arxiv.org/abs/2006.14548 [5] https://arxiv.org/abs/2210.16859 [6] https://arxiv.org/abs/2001.08361
Original comment The Problem with LLMs
logicchains
Neutral mention · rule
We already understand how transformers work: their architecture can learn to approximate a very large class of functions-on-sequences (specifically continuous sequence-to-sequence functions with compact support: https://arxiv.org/abs/1912.10077). It can do it more accurately than previous architectures like RNNs because transformers don't "forget" any information from prior items in the sequence. Training transformers to predict the next item in sequences eventually forces them to learn a function that approximates a world model (or at least a model of how the world behaves in the training text/data), and if they're large enough and trained with enough data then this world model is accurate enough for them to be useful for us. If you're asking for understanding the actual internal world model they develop, it's basically equivalent to trying to understand a human brain's internal world model by analysing its neurons and how they fire.
Original comment OpenAI – transformer debugger release
hackinthebochs
Neutral mention · rule
People really need to update their model of what a "statistical predictor" can accomplish. We know that Transformers are universal approximators of sequence-to-sequence functions[1], and so any structure that can be encoded into a sequence-to-sequence map can be modeled by Transformer layers. It follows that prediction and modeling are not categorically distinct capacities in LLMs, but exist on a continuum. How well the model predicts in a given instance is largely due to the availability of data during training. This is the basis for the beginnings of genuine understanding in LLMs. I talk about this in some length here[2]. Odd failures and hallucinations are just the model responding from different points along the prediction-modeling spectrum. [1] https://arxiv.org/abs/1912.10077 [2] https://www.reddit.com/r/naturalism/comments/1236vzf/on_larg...
Original comment Ask HN: Why can GPT4 en/decode base64?

Keep following the thread.

More in Language models

More from the same topics.