> This seems like somewhat of an artificial constraint?...The model might not be able to solve a problem directly but can in code.

First of all, I would say that it's not an "artificial constraint" so much as what you're saying is an artificial mitigation. When it comes to human programmers, we expect them to be able to execute small O(n^2) and O(2^n) algorithms on paper, and if they're not able to we rightfully question whether or not they actually understand the algorithm versus just having a bunch of code memorized.

But the bigger problem is that the O(n) limitation doesn't just apply to formal math/CS problems; many natural language queries have a computational complexity, and I believe this result puts a limit on those that GPT4 can (easily) solve. I'll give a concrete example from my testing GPT-4 last year[1]. Naively GPT-4 struggled to solve two simple problems:

1) Given a pair of sentences, choose the one that has the most words.

2) Given a list of n numbers, choose the largest.

Without chain-of-thought, GPT-4 was not able to solve these problems reliably because it was clearly using spurious statistical cues and "guessing," e.g. seeming to think "antidisestablishmentarian" was always in a sentence with many words. Using chain-of-thought prompting ("let's think step-by-step") GPT-4 was able to solve these problems easily.

However, these are both O(n) problems. If you asked GPT-4 "given a list of n sentences, choose the one with the most words. Let's think step by step:" it could not reliably solve the problem! It either counted the sentences step-by-step but then guessed as to what the largest number was; or it guessed the count of the sentences and them compared the count step-by-step. Its ability to solve two separate O(n) problems did not extend to an O(mn) problem - you would need to tailor the chain-of-thought prompt and basically hold GPT's hand to get the right answer. I think this theoretical result puts my experiment on firmer ground: transformer LLMs can be trained on a variety of linear complexity problems but they cannot natively extend those results to quadratic complexity.

And yes, GPT could put this in code and get the right answer. But you'd have to train it to write a Python function instead of using its own abilities. I don't think "if the problem seems too complex, try writing a Python function" will work as a prompting strategy: it's GPT-4's inability to recognize quadratic complexity that's the root cause of the problem. (It's also why chain-of-thought isn't a cure-all - humans need to decide whether CoT is appropriate! If you use CoT prompting on a simple factual question you'll get a bunch of useless "steps.")

Going back to the scaling - the promise of scaling is that eventually big data pays off and the LLM gains some sort of generalizable understanding of the problem. But if the performance varies smoothly and predictably, then that's probably not happening - LLMs never "grok" subjects, they just screw things up less and less. E.g. if GPT-3 got a 50% on 3-digit arithmetic because its training data include 30% of all 3-digit arithmetic problems, and GPT-4 got an 80% because its training data includes 50% of all such problems, then that's a vacuous and uninteresting form of scaling - there are only ~2,000,000 such problems so this isn't as ridiculous as it might sound. Likewise if GPT-4 had the same training data but doubled its performance because it doubled the resources spent on arithmetic training. The point isn't to deny that scaling exists, it's to question whether its worth all the money and excitement. I really don't think it is - it's not even interesting.

[1] GPT-4 can solve these examples correctly now, but that's mostly a testament to the impossibility of doing reproducible investigation on closed LLMs. I strongly suspect OpenAI later trained GPT-4 on this and other "dumb" problems: certainly you could write a Python script to generate appropriate training data. The problem is you would need to generate an ~O(mn) amount of data for every pair of O(m) and O(n) problems that someone might want to ask in conjunction. I don't actually use LLMs for work, so maybe you could see how performance varies between Claude, Mixtrial, etc.