3 ms·

What LLMs can do is limited, they are superior to wet-wear in some tasks like finding and matching patterns in higher dimensional space, they are still fundamen

What LLMs can do is limited, they are superior to wet-wear in some tasks like finding and matching patterns in higher dimensional space, they are still fundamentally limited to a tiny class of problems outside of that pattern finding and matching. LLMs will be tools for some math needs and even if we ever get quantum computers will be limited in what they can do. LLMs, without pattern matching, can only do up to about integer division, and while they can calculate parity, they can't use it in their calculations. There are several groups sitting on what are known limitations of LLMs, waiting to take advantage of those who don't understand the fundamental limitations, simplicity bias etc... The hype will meet reality soon and we will figure out where they work and where they are problematic over the next few years. But even the most celebrated achievements like proof finding with Lean, heavily depends on smart people producing hints that machines can use. Basically lots of the fundamental hints of the limits of computation still hold. Model logic may be an accessable way to approach the limits of statistical inference if you want to know one path yourself. A lot of what is in this article relates to some the known fundamental limitations. Remember that for all the amazing progress, one of the core founders of the perceptron, Pitts drank him self to death in the 50s because it was shown that they were insufficient to accurately model biological neurons. Optimism is high, but reality will hit soon. So think of it as new tools that will be available to your child, not a replacement.

ComplexSystems 2y ago
"LLMs, without pattern matching, can only do up to about integer division, and while they can calculate parity, they can't use it in their calculations." - what do you mean by this? Counting the number of 1's in a bitstring and determining if it's even or odd?
- nyrikki 2y ago
  Yes, in this case PARITY is determining if the number of 1s in a binary input is odd or even It is an effect of the complex to unpack descriptive complexity class DLOGTIME-uniform TC0, which has AND, OR and MAJORITY gates. http://arxiv.org/abs/2409.13629 http://arxiv.org/abs/2409.13629 The point being that the ability to use parity gates is different than being able to calculate it, which is where the union of the typically ram machine DLOGTIME with the circuit complexity of uniform TC0 comes into play. PARITY, MAJ, AND, and OR are all symmetric, and are in TCO, but PARITY is not in DLOGTIME-uniform TC0, which is first-order logic with Majority quantifiers. Another path, if you think about symantic properties and Rice's theorem, this may make sense especially as PAC learning even depth 2 nets is equivalent to the approximate SVP. PAC-learning even depth-2 threshold circuits is NP-hard. https://www.cs.utexas.edu/~klivans/crypto-hs.pdf https://www.cs.utexas.edu/~klivans/crypto-hs.pdf For me thinking about how ZFC was structured so we can keep the niceties of the law of the excluded middle, and how statistics pretty much depends on it for the central limit and law of large numbers, IID etc... But that path runs the risk of reliving the Brouwer–Hilbert controversy.

ComplexSystems 2y ago

"LLMs, without pattern matching, can only do up to about integer division, and while they can calculate parity, they can't use it in their calculations." - what do you mean by this? Counting the number of 1's in a bitstring and determining if it's even or odd?

nyrikki 2y ago
Yes, in this case PARITY is determining if the number of 1s in a binary input is odd or even It is an effect of the complex to unpack descriptive complexity class DLOGTIME-uniform TC0, which has AND, OR and MAJORITY gates. http://arxiv.org/abs/2409.13629 http://arxiv.org/abs/2409.13629 The point being that the ability to use parity gates is different than being able to calculate it, which is where the union of the typically ram machine DLOGTIME with the circuit complexity of uniform TC0 comes into play. PARITY, MAJ, AND, and OR are all symmetric, and are in TCO, but PARITY is not in DLOGTIME-uniform TC0, which is first-order logic with Majority quantifiers. Another path, if you think about symantic properties and Rice's theorem, this may make sense especially as PAC learning even depth 2 nets is equivalent to the approximate SVP. PAC-learning even depth-2 threshold circuits is NP-hard. https://www.cs.utexas.edu/~klivans/crypto-hs.pdf https://www.cs.utexas.edu/~klivans/crypto-hs.pdf For me thinking about how ZFC was structured so we can keep the niceties of the law of the excluded middle, and how statistics pretty much depends on it for the central limit and law of large numbers, IID etc... But that path runs the risk of reliving the Brouwer–Hilbert controversy.