I read the article: it does not look like very good research: It's simple to find flaws in LLMs reasoning / compositional capabilities looking at problems that are at the limit of what they can do now, or just picking problems that are very far from their computational model, or submitting riddles. But there is no good analysis of the limitations, nor inspection of how/how much better recently LLMs got exactly at this kind of problems. Also the article is full of uninformative and obvious things to show how LLMs fail in stupid tasks such as multiplication between large numbers.

But the most absurd thing is that the paper looks at computational complexity in terms of direct function composition, and there is no reason an LLM should just use this kind of model when emitting many tokens. Note that even when CoT is not explicit, the LLM output that starts to shape the thinking process still makes it able to have technically unbound layers. With CoT this is even more obvious.

Basically there is no bridge between their restricted model and an LLM.