Search papers, labs, and topics across Lattice.
This paper critiques the notion of Large Language Models (LLMs) as universal problem solvers, highlighting intrinsic limitations imposed by language as a compressed communication medium. By modeling user-system interactions as a bilevel cheap-talk game, the authors derive PAC-Bayes bounds that reveal two critical error floors: one due to the expressivity limits of language and another stemming from alignment constraints. The findings indicate that certain task families are fundamentally unsolvable by prompt-conditioned LLMs, even with infinite data, underscoring the need for alternative interfaces to enhance task-relevant information processing.
Language models face irreducible error floors that prevent them from being universal solvers, revealing the critical limits of prompt-based learning.
Large Language Models (LLMs) are frequently portrayed as general-purpose solvers capable of solving arbitrary tasks. We argue that this view overlooks a fundamental constraint: language is a compressed and capacity-limited interface for conveying task information. Modelling User--System interaction as a bilevel \emph{cheap-talk} game, we analyse how latent tasks are encoded into prompts and reinterpreted under alignment and safety constraints. We introduce a conceptual decomposition separating task inference from execution and derive PAC-Bayes bounds that distinguish finite-sample estimation error from irreducible structural limitations. Our first main result establishes an \emph{expressivity floor}: language acts as a capacity-limited communication channel, and whenever the informational complexity of a task family exceeds the capacity of that channel, distinct tasks become unavoidably indistinguishable to the Solver, inducing a strictly positive error floor that cannot be eliminated by additional data, optimisation, or model scaling alone. We then establish an \emph{objective-misalignment floor}: when alignment constraints restrict the admissible output set, the User-ideal distribution may lie outside the feasible class, inducing an irreducible distortion. Together, these results yield a formal negative conclusion: prompt-conditioned LLMs are not universal problem solvers through prompting alone, as there exist task families for which correct behaviour is provably unattainable even in the infinite-data regime. More broadly, our analysis shows the limits of prompt-based generalisation arise from information-constrained communication and alignment-constrained objectives. This suggests that interfaces beyond natural language, including multimodal observations and, external memory, may reduce the inherent LLM limitations by increasing the task-relevant information available to the System.
