xu-2024-scaling-preserves-complexity-class
IN premise — summaries/2026/08/24/xu-2024-hallucination-innate-s4-discussion.md
Created 2026-08-24T17:11:29+00:00
Scaling parameters or adding training data to a polynomial-time LLM keeps it in the same complexity class (polynomial-time), so it will still hallucinate on exponential-time ground-truth functions regardless of scale.
Summary
No matter how many parameters you add or how much more data you feed a polynomial-time model, it stays a polynomial-time model, so it will keep guessing wrong on problems whose correct answer fundamentally requires exponential-time computation. This means scaling is not a path to fixing hallucination on those hard problems; the failure mode is structural, not a matter of size or data volume.