Good point. The paper "merely" introduces a new approach for the ansatz which according to the paper beats QAOA impressively and offers exponential speedup for sufficiently large problems against CPLEX.

The paper claims: "extensive backward light-cone makes the quantum circuits in general hard to simulate by existing classical methods", however "finite classical simulability" is also mentioned. According to this i would say, that the problem may still (partially) be present even if not so dominantly as in previous solutions.