Tighter bounds on the expressivity of transformer encoders

Re:Tighter bounds on the expressivity of transformer encoders by transformi on Tuesday April 25, 2023 @07:07PM (#35707924)

is it possible to solve NP-hard problems with transformers/LLM?

[ Parent | on HN ]

Re:Tighter bounds on the expressivity of transformer encoders by ironbound on Tuesday April 25, 2023 @08:03PM (#35708296)

you'll be limited right away by the context lenght of 4096 tokens

[ Parent | on HN ]

Re:Tighter bounds on the expressivity of transformer encoders by cardboardbach on Tuesday April 25, 2023 @09:30PM (#35708791)

Of course.

[ Parent | on HN ]

Re:Tighter bounds on the expressivity of transformer encoders by shawntan on Tuesday April 25, 2023 @11:56PM (#35709507)

You should check out the work referenced in the abstract, the most recent here: https://twitter.com/lambdaviking/status/1630581475425828864

There are limitations for what a Transformer can compute if we do not allow for Chain-of-Thought type of output. By allowing the model to "show its work" allows it to effectively use the output as an "infinite tape". I'm simplifying but that's the basic gist of it.

I'll shamelessly plug my blog post from a week ago for a simpler take on the matter: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/

[ Parent | on HN ]

Re:Tighter bounds on the expressivity of transformer encoders by intalentive on Wednesday April 26, 2023 @02:12AM (#35710110)

They can't even learn parity checks.

https://arxiv.org/abs/2207.02098

[ Parent | on HN ]