Papers

We present a formal framework connecting LLM reasoning failures to computational complexity classes. Through 176,000 evaluations across 12 model families and 9 diagnostic tasks, we show that reasoning gaps cluster into six types predictable from problem structure. Chain-of-thought closes gaps for serial composition (+35 pp) but not for problems requiring parallel search or architectural capabilities (+9 pp).

We develop a formal framework for the computational complexity of verifying language model outputs. We characterize verification difficulty across output types and prove that for several natural problem classes, verification is strictly easier than generation — but this gap varies systematically with output structure.

Drawing on 50+ deployment incidents from autonomous agent systems, we construct a structured taxonomy of failure modes. Categories span planning failures, tool-use errors, context management breakdowns, and goal drift. We connect each category to architectural mitigations and evaluate their effectiveness.

We establish theoretical bounds on unsupervised self-improvement in language models. Under standard complexity assumptions, we show that certain capability gains require external signal — no amount of self-play or self-evaluation can substitute for ground truth on specific problem classes.