David Chiang, Peter Cholak, Anand Pillay
2023 · arXiv
Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform $TC^0$. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.
Metadata: arXiv. Abstracts retain their original authors’ rights.
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
4 selected excerpts · 4 total mentions
Transformers with fixed precision and any amount of memory are not Turing complete. They're bounded by a variant of first order logic with counting quantifiers. https://arxiv.org/abs/2301.10743 This supports the intuitive idea that they "learn circuits for things" that I've heard a few others mention. If they have infinite precision then I suppose they can simulate a Turing machine in their infinitely precise states...
To that, what can these express, precisely, is an interesting question; so for transformer encoders: https://arxiv.org/abs/2301.10743 Another interesting research topic is the trusted generation of tasks for finetuning https://arxiv.org/abs/2306.08568 And I suppose too running these at the edge is terribly interesting too, if you can find analyses of "quantization" this is a highly active research are, and results are pretty incredible since it cuts resources by huge factors and no one quite knows why. This is one that's easy to dive into with consumer hardware, but don't know any great papers myself Run locally: https://github.com/ggerganov/llama.cpp Quantized models: https://huggingface.co/TheBloke Explainability is under research, though I haven't seen any good solutions. This nay arise from skeptics who are calling the things stochastic parrots, incapable of reason, without a world model, etc.
The current generation of LLMs will never generalize on problems whose expected complexity is significantly harder than the training set. One way to think of why this is the case is because transformers are learning shortcuts to multistep reasoning tasks [1, 2], but do not learn to reason systematically and unsurprisingly fail to generalize when presented with more challenging tasks. The proper way to evaluate systematic reasoning is by training on a curriculum of problems of increasing average-case complexity. Think random k-SAT in the critical region, bisimulation games, or interpolation in certain logical theories. Although there is a growing evidence that Transformers…
and GNNs have foundational limits to expressivity [3, 4, 5], if the scaling crowd could show strong generalization results on these sorts of problems they would have the last laugh... [1]: https://arxiv.org/pdf/2210.10749.pdf [2]: https://arxiv.org/pdf/2305.18654.pdf [3]: https://arxiv.org/pdf/2106.16213.pdf [4]: https://arxiv.org/pdf/2301.10743.pdf [5]: https://arxiv.org/pdf/2303.04613.pdf
This has been built on extensively over the past two years. For instance: Tighter Bounds on the Expressivity of Transformer Encoders https://arxiv.org/abs/2301.10743. I find it interesting that transformers are equivalent to first order logic on circuits with counters. Amazing what you can do even if you're not Turing complete!
More from the same topics.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan +11
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.
Tom B. Brown, Benjamin Mann, Nick Ryder +28
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski +10
We trained a convolutional neural network (CNN) to map raw pixels from a single front-facing camera directly to steering commands.