AI Model Complexity Boundaries


Problem: Users keep expecting AI’s ( Large Language Models / LLMs ) to work at any scale of complexity, with disastrous consequences for the accuracy, reliability, consistency, etc. of business software that relies on AI to get through business critical workflows.

Forces: No matter how large their training corpus and parametric knowledge base is, LLMs have fundamental limitations when it comes reasoning and knowledge retrieval. These limits can also be seen in human cognition and computer systems which all have natural bounds of statistical and computational complexity.


Theory

Initial versions of LLMs had trouble consistently finding a word or small sentence in large documents - the so called “needle in a haystack” problem. Subsequently models were retrained to have better haystack searching capabilities.

Currently an AI might be able to find a ‘needle’ if it’s a single word or phrase, even if the document (haystack) is very large. But if you have multiple sentences in a conceptual framework spread throughout the document you very quickly get ‘combinatorial explosion’ in terms of all the possible intersections of concepts that you’re looking for.


VC / P vs NP / Gödel/Turing

The Vapnik–Chervonenkis dimension is a mathematical concept in statistical learning theory that measures the capacity, complexity, or expressive power of a machine learning model. If a model has a very high VC dimension, it is highly flexible and can memorize the training data perfectly, which often leads to overfitting (seeing noise as a valid signal instead of finding the true underlying pattern).

P vs NP refers to one of the most famous unsolved problems in computer science and mathematics, asking whether every problem whose solution can be quickly verified can also be quickly solved. P stands for Polynomial time. This represents problems that a computer can solve quickly and efficiently (e.g., sorting a list of numbers). NP stands for Nondeterministic Polynomial time. This represents problems where, if you are given a potential answer, a computer can verify if it is correct quickly, but actually finding that answer from scratch might take an astronomically long time. The "Wall" here is that for complex NP problems, finding the perfect solution through brute-force calculation would take longer than the lifespan of the universe.

Gödel/Turing are two foundational pioneers in mathematics and computer science whose work established the absolute limits of logic and computation:

Kurt Gödel: Known for his Incompleteness Theorems, which proved that in any sufficiently complex mathematical system, there are true statements that cannot be proven true using the rules of that system.

Alan Turing: Known for the Halting Problem, which proved that it is impossible to create a universal algorithm that can perfectly predict whether every possible computer program will eventually finish running or run forever in an infinite loop.

So no matter how large a language model is and how well it’s trained there’s ‘laws of physics’ that limit the combinatorial complexity of the inference and retrieval that AI can accomplish. Are we expanding this complexity boundary with every new model, yes… but the boundary remains very finite and real in terms of it’s impact on countless current day AI inference results.

“Yet as models approach trillion-parameter regimes, the very process that powers their ascent also exposes fundamental limits that scale cannot surmount. Larger models not only perform better but also fail more confidently : they hallucinate, mis-reason, forget, and misalign in increasingly systematic ways. These pathologies persist even under massive data, suggesting deeper computational and statistical origins. In this paper, we argue that such behaviors are not transient artifacts of optimization or data curation but manifestations of intrinsic theoretical barriers , constraints imposed by computability, information theory, and learnability itself.”

— On the Fundamental Limits of LLMs at Scale; UC Berkely, Stanford University, Meta, Google DeepMind, University of Glasgow, et. al.; 2025

Solution: The above cited paper examines the complexity boundaries in 5 interacting dimensions: Long context window, Reasoning, Hallucination, Retrieval, Multi-modality. The latest ‘reasoning’ LLMs have remarkable reasoning capabilities, but core principles of computation and information theory impose ceilings on what scaling can achieve… what the study calls innate theoretical ceilings for LLM reasoning.

If for instance you have a query that requires many steps of reasoning, and the output from the LLM is unsatisfactory, break the problem into pieces.

Ironically, conventional business logic and GUI features can help reduce the scope of queries you send to LLMs before the model even sees them. If you are querying for a sales forecast of the coming quarter, and you have two orthogonal business units, bicycle parts and chocolate-dipped fruit baskets, let the user, via the GUI or the business logic in code, limit the scope of the query so the model doesn’t see any contextual data that is irrelevant.


Also: be aware of the level of compression of the parametric knowledge in your model. In so called ‘distilled’ models, for instance, the models ‘latent space’ (where reasoning occurs) is based on highly compressed vector data, which can lead to hallucinations, inaccuracies, etc. that wouldn’t occur in a less compressed model.

Also: Pay particular attention to the temporal natural of your query and the retrieval corpus and the model’s training cut-off date. If there is a large amount of content in play + a complex query + complex temporal fissures and splits, AI inference will suffer.

Context: Complexity boundaries emerge whenever you:

  • Ask the model to reason across very large bodies of content, where there is substantial complexity in terms of themes, subplots, actors. Often it will look like the model can handle this for a single query, but run 10 queries or 100 queries and a pattern of hallucination and inaccuracy will become clear..
  • Ask model to conduct reasoning that requires many interdependent steps and branching logic
  • Ask a model to answer questions where the language in the retrieval corpus is highly ambiguous with many subtle polymorphic interpretations.
  • Ask a model to answer questions from a large retrieval corpus, but not all the required data in in the corpus. This “Out of Distribution” problem is handled in the ‘AI Out of Distribution Reasoning’ pattern.


Model accuracy degrades rapidly for tail (e.g., out-of-distribution) entities.