Imagine asking GPT to multiply two $10,000 × 10,000$ matrices or compute $93726497^{93726497}$.

Not explain the algorithm. Not write Python code. But to actually compute the answer.

At some point, no matter how capable the model is, the task becomes impossible — not because it lacks knowledge, but because it simply cannot perform enough computation before producing its next token.

This realization changed how I think about Large Language Models. Their biggest limitation may not be hallucination or missing knowledge. It may be something much more fundamental: every LLM has a fixed computational budget during inference.

What Do LLMs Actually Do?

Ask almost anyone what ChatGPT do, and you'll probably hear one of two answers.

• 1. It just predicts the next token.
• 2. It reasons just like a human.

Interestingly, both are INCOMPLETE.

At the lowest level, every Large Language Model performs a remarkably simple task: given a sequence of tokens, it predicts the most probable next token. It does this by processing the entire context through a Transformer network, computing contextual representations using self-attention, and producing a probability distribution over the vocabulary. The token with the highest (or sampled) probability becomes the next token, and the process repeats.

But this explanation raises an important question.

If an LLM is only predicting the next token, how can it write software, explain quantum mechanics, solve mathematics, translate languages, and reason through complex problems?

The answer lies in what those token predictions are based on.

An LLM is not executing algorithms in the same way a CPU does. It doesn't create variables, update registers, execute loops, or repeatedly apply mathematical rules unless those steps are explicitly externalized into the generated text or delegated to external tools.

Instead, the model performs a single forward pass through a massive neural network and produces the next token based on the contextual representations it has learned during training. Those representations encode an extraordinary amount of statistical structure, factual knowledge, linguistic patterns, programming concepts, and reasoning heuristics.

This is why the phrase "LLMs are just pattern matching" is both TRUE and MISLEADING.

It's TRUE because the model ultimately predicts tokens by recognizing patterns in high-dimensional representations learned from vast amounts of data.

But it's MISLEADING because these are not simple lookup tables or surface-level text patterns. The network has learned rich abstractions that often behave like compressed algorithms, allowing it to generalize to many problems it has never seen verbatim.

The more interesting question, therefore, is not whether LLMs perform pattern matching.

THE REAL QUESTION IS: What happens when the correct next token depends on performing more computation than the model can effectively carry out during inference?

That question, I believe, reveals one of the most fundamental limitations of today's LLMs - Limited Compute Budget.

How Does LLM Inference Actually Work?

To understand the computational limits of LLMs, we first need to understand what happens during inference. Let's take a GPT-style decoder-only Transformer as an example.

Suppose you start a new conversation with ChatGPT and send the following prompt:

Tell me something about Paris.

The prompt is first broken into tokens. These tokens are converted into dense vector representations (embeddings) and passed through the Transformer network.

At this point, every token attends to all the tokens that came before it (and itself) using causal self-attention. Unlike encoder-decoder architectures, GPT has no encoder and no cross-attention. Prompt and model's generated response, all exists in a single growing sequence.

The entire prompt is processed simultaneously through every Transformer layer. This stage is commonly called the prefill phase.

After the final Transformer layer, the model doesn't directly produce a sentence. Instead, it produces a probability distribution over every token in its vocabulary for the next token only.

For example, after processing:

The capital of France is

the model might internally assign probabilities like:

Paris      : 98.7%
London     : 0.4%
Berlin     : 0.2%
Madrid     : 0.1%
...

The next token ("Paris") is selected according to the decoding strategy (greedy decoding, sampling, beam search, etc.) and appended to the sequence.

Now something interesting happens.

The model does not regenerate the entire sentence in one shot.

Instead, it repeats exactly the same process.

The new sequence becomes:

The capital of France is Paris

This updated sequence is again processed to predict only the next token.

This autoregressive loop continues until the model generates an end-of-sequence token or reaches a configured output limit.

Prefill vs Decode

Modern LLM inference consists of two distinct phases.

1. Prefill

• The entire input context is processed once during prefill.
• During this pass, the model computes contextual representations for every input token and stores their Key and Value tensors in what is known as the KV Cache.
• This is usually the computationally expensive part of inference.

2. Decode

• After the first output token has been generated, the model no longer recomputes the entire prompt.
• Thanks to the KV Cache, only the newly generated token passes through the Transformer while attending to the cached representations of all previous tokens.
• This makes token generation much faster than the initial prefill stage.

The Most Important Observation

Notice what never changes.

For every generated token, the model performs exactly one forward pass through its neural network.

The model cannot decide:

-> This next token is particularly difficult. 
-> I'll spend another million internal computation steps before answering.

A CPU can execute a loop for as long as necessary. A standard LLM cannot.

LLMs architecture is fixed. Every generated token receives one traversal through the same Transformer layers before the model must commit to a probability distribution for the next token.

This seemingly simple property turns out to have profound implications.

It suggests that every inference has a "Finite Computational Budget" — a budget that is independent of whether the next token requires a fact lookup or requires a solution to a computationally demanding problem.

In the next section, we'll explore why this distinction between neural inference and algorithm execution may be one of the most important ideas for understanding both the strengths and the limitations of modern LLMs.

Learned Knowledge vs. Computational Demand

Not every question asked to an LLM requires the same kind of work. Some questions are primarily knowledge retrieval. Others require fresh computation. Understanding this distinction is essential.

Suppose I ask:

Who developed the theory of General Relativity?

• The model doesn't need to rediscover modern physics.
• The answer already exists within the knowledge distilled during training.
• Inference simply retrieves that learned representation.

Similarly, if I ask:

What is the time complexity of Merge Sort?

• The model isn't deriving the algorithm from first principles.
• It has learned the concept during training and can reproduce it with remarkable reliability.

Now consider a different kind of question:

Multiply these two randomly generated 20,000-digit integers.

This problem is fundamentally different.

The answer certainly does not exist anywhere in the model's learned representations. It cannot be retrieved from memory, nor can it be approximated by recognizing a familiar pattern. Producing the correct answer requires executing an algorithm. Algorithm that performs thousands of sequential arithmetic operations while maintaining intermediate state.

This distinction is subtle but profound.

A CPU naturally executes such algorithms. It maintains registers, updates variables, performs loops, and continues until the computation is complete. A standalone LLM does none of these things internally.

Instead, LLM performs a bounded neural computation and produces a probability distribution for the next token. This leads to an important observation.

Many computationally demanding problems are not difficult because they require new ideas. They are difficult because they require many sequential state updates.

• Long multiplication.
• Gaussian elimination.
• Exhaustive search.
• Dynamic programming.
• Constraint satisfaction.
• Graph traversal.

The challenge is not understanding what to do. The challenge is carrying out every intermediate step correctly.

When a standalone LLM encounters such a problem, it cannot suddenly transform itself into an algorithm executor. It still performs exactly the same operation it performs for every other prompt: it computes contextual representations from the input and predicts the next token that appears most consistent with everything it has learned during training.

Sometimes LLMs works astonishingly well.

If the problem resembles many examples seen during training, or if the required computation is small enough to be effectively approximated through learned heuristics, the model may produce the correct answer.

But as the amount of required fresh computation grows, the model is increasingly forced to rely on approximation rather than execution.

Importantly, this does not mean the model begins "guessing" randomly. Nor does it imply that it stops reasoning altogether.

Instead, it continues to do exactly what it was designed to do: evaluate the context, leverage learned representations, and predict the most plausible continuation of the sequence.

The problem is that, for some tasks, plausibility and correctness eventually diverge.

Knowing how an algorithm works is not the same as executing that algorithm. This distinction explains a curious phenomenon observed in modern LLMs.

• They can often describe an algorithm perfectly.
• They can write correct implementations of that algorithm.
• They can even explain why the algorithm works.
• Yet they may still fail when asked to manually execute the algorithm on sufficiently large or adversarial inputs.

This, I believe, is one of the most important mental models for understanding the limitations of standalone LLMs. Their weakness is NOT simply that they lack knowledge. Weakness is that there exist problems whose correct solution requires certain amount or style of computations that cannot be replaced by learned representations alone.

Examples of LLMs Struggling with Computationally Intensive Tasks

If the previous sections are correct, we should expect standalone LLMs to perform exceptionally well on problems that primarily require learned knowledge or pattern recognition, while gradually struggling when the amount of fresh computation required during inference increases.

Interestingly, this is exactly what we observe in practice.

1. Matrix Multiplication - Consider multiplying two $1000 × 1000$ matrices.

The algorithm itself is elementary. Every element of the resulting matrix is simply the dot product of one row and one column. The difficulty is NOT Conceptual, IT IS Computational.

Producing the exact result requires millions (or even billions) of arithmetic operations depending on the matrix size. A standalone LLM cannot internally execute this enormous sequence of calculations. Instead, it continues doing what it always does: evaluating the prompt, constructing contextual representations, and predicting the next token.

For small matrices, this may be sufficient. For sufficiently large matrices, arithmetic errors become almost inevitable.

2. Large Integer Multiplication

The same phenomenon appears in integer arithmetic.

Ask an LLM to compute: $27 × 43$ and it almost always succeeds.

Then ask it to multiply two randomly generated 20,000-digit integers.

Now the problem is no longer about knowing multiplication. The required computation involves thousands of carries and intermediate states that must all remain consistent.

A CPU executes this algorithm exactly.

A standalone LLM has no internal execution engine performing long multiplication. It attempts to infer what the answer should look like based on learned representations and local reasoning, making exact correctness increasingly difficult as the problem scales.

3. Chess Master

Chess provides perhaps the most fascinating example.

Modern chess engines routinely search millions of positions before selecting a move. Standalone LLMs do not. Yet LLMs often play great chess. How?

Not by exhaustively searching the game tree, but by recognizing:

• patterns,
• strategic motifs,
• tactical ideas, and
• positional heuristics learned during training.

This works surprisingly well for many positions.

However, positions requiring deep tactical search eventually expose the difference between pattern recognition and algorithmic search. A dedicated chess engine can continue exploring the search tree until it finds the optimal continuation. A standalone LLM cannot suddenly decide to internally search another million positions before producing its next token.

These examples point toward an interesting hypothesis.

Perhaps the limitation is not intelligence itself, but the amount and type of computation available during inference.

The Limited Compute Budget Hypothesis

The discussion so far naturally leads to what I call the Limited Compute Budget Hypothesis.

Every inference performed by a standalone Large Language Model has a finite computational budget. Some problems require more fresh computation than can be performed within that budget.

Notice that this hypothesis says nothing about intelligence.

It also says nothing about whether LLMs "reason".

Instead, it focuses on a much simpler observation.

Every generated token receives one traversal through the Transformer network before the model must produce a probability distribution for the next token.

That amount of neural computation is FINITE. For many tasks, this is more than enough.

• Answering factual questions.
• Explaining algorithms.
• Writing software.
• Translating languages.
• Summarizing research papers.

These rely heavily on knowledge and abstractions already learned during training.

But other tasks fundamentally require the execution of long computational procedures.

• Large-scale arithmetic.
• Combinatorial search.
• Constraint satisfaction.
• Exhaustive graph traversal.
• Large optimization problems.

These cannot simply be retrieved from memory because the correct answer depends on computations that must be performed specifically for the current input.

The hypothesis suggests that: As the amount of required fresh computation grows beyond what can effectively occur during inference, the model becomes increasingly dependent on approximations, learned heuristics, and statistical regularities rather than exact execution.

Importantly, this does NOT imply that failure occurs at some precise computational threshold.

Instead, it predicts a gradual transition: As computational demand increases, exact execution becomes increasingly difficult for a standalone LLM without external tools, intermediate reasoning, or iterative computation.

Where the Limited Compute Budget Hypothesis Breaks Down

At first glance, this hypothesis appears closely related to classical computational complexity.

In fact, a recent research paper attempts to formalize a similar argument by comparing the computational complexity of Transformer inference with the computational complexity of the tasks specified in a prompt. From there, the authors invoke the Time Hierarchy Theorem to argue that tasks requiring asymptotically greater computation must inevitably produce hallucinations.

I believe this intuition is compelling.

However, I also think the argument needs important qualifications.

I. Neural Computation Is Not Algorithmic Computation

The first challenge is that Transformer inference and algorithm execution are fundamentally different computational processes.

A CPU executes algorithms by maintaining mutable state, updating variables, iterating through loops, and applying deterministic rules until a computation finishes. A standalone LLM does none of these things internally.

Comparing the complexity of these two computations is therefore not straightforward. They are different computational models.

II. Pattern Recognition Can Replace Computation

There is another subtle issue.

Some computationally difficult problems can be answered reliably by an LLM.

Why?

Because the model may not need to perform the underlying computation at inference time. Instead, it may recognize patterns, retrieve learned abstractions, or apply heuristics acquired during training.

A strong chess move is an excellent example.

• Finding the move from first principles may require searching millions of positions.
• Recognizing the move from prior experience may require no such search at all.

The computational complexity of FINDING a solution is therefore not always equal to the computational complexity of PREDICTING the solution.

III. Does the 'Time Hierarchy Theorem' Apply?

The Time Hierarchy Theorem remains a foundational result in computational complexity.

What is less clear is whether Transformer inference can be mapped directly onto the computational model assumed by the theorem.

The theorem concerns machines executing algorithms under bounded computational resources.

Standalone LLMs perform bounded neural inference over learned representations.

Whether those two notions of computation are equivalent for the purpose of complexity-theoretic arguments remains an open research question.

A More Conservative Conclusion

For these reasons, I prefer a more cautious formulation of the hypothesis.

For tasks whose correct output cannot be inferred from learned representations and instead requires the execution of an algorithm whose computational demands exceed the effective inference computation available to the model (or the model together with external reasoning and tools), a standalone LLM cannot reliably produce correct outputs across all instances.

This conclusion is less dramatic than claiming that every computationally difficult prompt inevitably causes hallucination.

But it better reflects what we currently understand about Large Language Models.

Their limitations arise not simply because computation is bounded, nor simply because they are pattern-matching systems, but because the relationship between learned representations, neural computation, and algorithm execution is still only partially understood.

That relationship, in my view, is one of the most interesting open questions in modern AI research.

Why Reasoning Models and AI Agents Exist

If this hypothesis is even partially correct, it also explains why the AI industry is rapidly moving beyond standalone LLMs.

Instead of expecting a single forward pass to solve every problem, modern AI systems augment LLMs with additional sources of computation.

• Chain-of-thought externalizes intermediate reasoning.
• Test-time compute allows the model to spend more computation on harder problems.
• Tool use delegates specialized tasks to calculators, search engines, or theorem provers.
• External memory enables knowledge access beyond the model's immediate context.
• Code execution transforms the LLM from an algorithm describer into an algorithm orchestrator.

In other words,

These systems don't necessarily make the model smarter. They make it capable of performing computation that the standalone model cannot reliably execute on its own.

Closing Thoughts

Whether the "Limited Compute Budget Hypothesis" ultimately proves to be correct or not, I believe it offers a useful mental model for thinking about the strengths and limitations of Large Language Models.

Perhaps the future of AI isn't about building models that simply memorize more knowledge or perform increasingly larger single-pass inference.

Perhaps it's about building systems that are cheap, fast, and intelligent enough to know when prediction is sufficient, and when they should stop predicting and start computing.

That, more than scaling model size alone, may be what ultimately separates language models from truly general-purpose intelligent systems.