On the Reasoning Gaps of Large Language Models: A Formal Characterization
NeurIPS 2026 Pre-Print
We present a formal framework for characterizing reasoning failures in large language models. Through 176,000 evaluations across 12 models and 9 benchmark tasks spanning P to coNP complexity classes, we demonstrate that LLM reasoning gaps are systematic, predictable, and correlate with the computational complexity of the underlying task. Our taxonomy identifies six distinct gap types with measurable signatures.
LLM reasoning · computational complexity · benchmark design · formal characterization
The Computational Complexity of Verifying LLM Outputs Across Reasoning Domains
ICLR 2027 In Progress
We develop a complexity-theoretic framework for analyzing when LLM outputs can be efficiently verified. Our approach connects verification difficulty to the VC dimension of the underlying reasoning task, with three main theorems establishing bounds on cross-model verification, self-consistency checking, and interactive verification protocols.
verification complexity · scalable oversight · cross-model verification
A Taxonomy of Failure Modes in LLM-Based Autonomous Agents
ACL 2027 In Progress
Drawing from 50+ real deployment incidents, we construct a comprehensive taxonomy of how LLM-based autonomous agents fail. Our 9-category framework with C1-C8 failure code mapping enables systematic diagnosis and mitigation of agent failures across tool use, planning, and self-monitoring dimensions.
autonomous agents · failure taxonomy · LLM agents · reliability
Impossibility Results for Unsupervised Self-Improvement in Language Models
ICLR 2027 Early Stage
We investigate theoretical limits on what language models can learn from their own outputs without external supervision. Preliminary results suggest fundamental bounds on self-improvement through self-training, self-refinement, and constitutional AI approaches.
self-improvement · impossibility results · self-training · theoretical ML