3 ms·
For the PARITY problem mentioned here, I recall from undergrad cs theory that there are some pretty neat provable lower-bounds on arithmetic circuit complexity,
by krackers 4y ago
For the PARITY problem mentioned here, I recall from undergrad cs theory that there are some pretty neat provable lower-bounds on arithmetic circuit complexity, e.g. parity is not in AC0 (bounded-depth, unlimited fan-in logic gates) circuits. Even providing more computational power via mod p gates still really doesn't buy you much: Razborov-Smolensky theorem shows that even adding mod-p gates you still can't compute modulo q, for p and q being distinct primes.
See also https://blog.computationalcomplexity.org/2023/02/why-cant-little-chatty-do-math.html https://blog.computationalcomplexity.org/2023/02/why-cant-li... for more discussion of LLMs from a circuit-complexity perspective.
- shawntan 4y agoThere's more detailed examination of Transformers from circuit complexity in this paper: https://arxiv.org/abs/2106.16213 https://arxiv.org/abs/2106.16213 There are a few references also in the blog post.
- krackers 4y agoThank you! I'd love more articles analyzing LLMs from a circuit-complexity perspective! Also seems modeling the transformer as in the TC0 class, in principle it should be able to do division and multiplication of numbers.