and the training was only on Sudoku. Which means they need to train a small model for every problem that currently exists.

Back to ML models?

I would assuming that training a LLM would be unfeasible for a small research lab, so isn't tackling small problems like this unavoidable? Given that current LLMs have clear limitations, I can't think of anything better than developing beter architectures on small test cases, then a company can try scaling it later.

Not only on Sudoku, there is also maze solving and ARC-AGI.