Algorithmic Capture, Computational Complexity, and Inductive Bias of Infinite Transformers

This paper formally defines algorithmic capture as the ability of infinite-width transformers to generalize to arbitrary problem sizes and demonstrates that, despite their universal expressivity, their inductive bias restricts them to learning only low-complexity algorithms within the Efficient Polynomial Time Heuristic Scheme (EPTHS) class.

The Gist

Imagine you have a super-smart student named Transformer. This student is famous for reading millions of books and memorizing patterns. If you ask them to finish a sentence, they are usually spot on. But here's the big question: Does Transformer actually understand how to solve a problem, or are they just really good at guessing the next word based on what they've seen before?

This paper tries to answer that by testing if Transformer can truly "learn" an algorithm (like a recipe for sorting numbers or finding the shortest path) and apply it to problems of any size, even ones it has never seen before.

Here is the breakdown of their findings using some everyday analogies:

1. The "Grokking" Test: Memorization vs. Understanding

The authors define a strict test called "Algorithmic Capture."

• The Scenario: Imagine you teach Transformer to sort a list of 10 numbers.
• The Real Test: Can it then sort a list of 1,000 numbers, or even 1,000,000 numbers, with almost no extra practice?
• The Result:
  • True Understanding: If it learns the logic of sorting, it can handle the huge list easily. It's like learning the rules of chess; you can play a game with 100 pieces just as well as with 32.
  • Statistical Guessing: If it just memorized patterns from the small list, it will get confused and fail when the list gets huge. It's like a student who memorized the answers to a 10-question quiz but fails the 1,000-question exam because they didn't learn the math.

2. The "Brain Size" Experiment

To be fair, the researchers didn't just use a normal computer. They imagined a Transformer with infinite brain power (infinite width).

• The Analogy: Think of a normal Transformer as a regular human brain. An "infinite" Transformer is like a supercomputer that can hold every possible thought in the universe at once.
• The Surprise: Even with this god-like brain power, the Transformer still couldn't learn everything.

3. The "Speed Limit" on Thinking

The paper discovered that Transformers have a hidden speed limit on how complex a problem they can solve in real-time.

• The Metaphor: Imagine a librarian (the Transformer) trying to find a book in a library.
  • Easy Tasks (Induction & Sorting): If the librarian needs to find a book based on a simple pattern (like "find the book that comes after 'A'"), they can do it quickly, even if the library grows to the size of a city. This is like O(T²) complexity (quadratic). It gets harder as the library grows, but it's manageable.
  • Hard Tasks (Shortest Path & Max Flow): If the librarian needs to find the absolute shortest path through a maze that changes every time, or calculate the maximum water flow through a complex pipe network, the time it takes explodes.
• The Finding: The Transformer's "thinking speed" is capped. It can handle tasks that scale like a square ($T^2$) or a cube ($T^3$), but it hits a wall with anything more complex. It's like trying to run a marathon; you can run fast for a while, but eventually, your legs give out. No matter how much you "understand" the concept of running, you physically cannot run faster than your body allows.

4. What Can It Actually Do?

The researchers tested Transformer on specific puzzles:

• ✅ It Succeeded at:
  • Induction Heads: Finding a pattern like "If I see 'A', the next letter is 'B'." (Like a detective spotting a clue).
  • Sorting: Arranging numbers from smallest to largest.
  • Why? These tasks are like simple recipes. The Transformer can follow the steps efficiently.
• ❌ It Failed at:
  • Shortest Path: Finding the quickest route between two points in a massive, random map.
  • Min-Cut/Max-Flow: Figuring out how to split a network to stop the most traffic.
  • Why? These tasks require a level of "global planning" that is too computationally heavy for the Transformer's architecture. It's like asking a person to solve a Rubik's cube while blindfolded; they might get lucky on a small cube, but a giant one is impossible for their specific method.

5. The "Lazy" vs. "Rich" Learning

The paper also looked at how the Transformer learns:

• Lazy Learning: The Transformer just tweaks its existing knowledge slightly (like adjusting the volume on a radio). It's fast but limited.
• Rich Learning: The Transformer rewires its brain to learn new features (like learning to play a new instrument).
• The Conclusion: Even when the Transformer "rewires" its brain to be smarter, it still hits the same speed limit. It can't magically become a super-computer that solves impossible math problems instantly.

The Big Takeaway

This paper tells us that Large Language Models (LLMs) are not magic.

They are incredibly good at pattern matching and can learn simple algorithms (like sorting or copying). However, they have a fundamental inductive bias (a built-in preference) for simple, low-complexity solutions. They are not designed to be universal problem solvers for every type of math or logic puzzle.

In short: Transformer is a brilliant librarian who can organize books and find simple patterns, but if you ask it to solve a complex, multi-layered maze in real-time, it will hit a wall. It's not that it doesn't "try"; it's that its brain architecture has a built-in speed limit.

Technical Summary

Here is a detailed technical summary of the paper "Algorithmic Capture, Computational Complexity, and Inductive Bias of Infinite Transformers" by Orit Davidovich and Zohar Ringel.

1. Problem Statement

The central question addressed is the extent to which Large Language Models (LLMs), specifically Transformers, possess genuine "algorithmic understanding" versus merely exploiting statistical correlations (interpolation). While empirical evidence suggests LLMs can "grok" (suddenly generalize) certain algorithms, it remains unclear if they can generalize to arbitrary problem sizes ($T$) with minimal sample adaptation.

The authors argue that true algorithmic learning requires generalization to out-of-distribution (OOD) instance sizes, a setting where simple statistical interpolation fails. They seek to determine if the inductive biases of Transformers (specifically in the infinite-width limit) allow them to learn algorithms of arbitrary computational complexity or if they are inherently biased toward low-complexity solutions.

2. Methodology

A. Formal Definition of Algorithmic Capture

The authors introduce a rigorous definition of Algorithmic Capture. A neural network captures an algorithm $A$ if:

1. Scalability: It generalizes to arbitrary input sizes $T$.
2. Sample Efficiency: It requires a fixed sample budget $P_0$ to learn the task logic on small instances ($T \le T_0$).
3. Minimal Adaptation: For larger instances ($T > T_0$), it requires only a logarithmic number of additional samples, $O(\log(T/T_0))$, to fine-tune. This logarithmic cost is attributed to correcting architectural non-idealities (e.g., attention dilution, positional encoding drift) rather than re-learning the algorithmic logic.

B. Theoretical Framework: Infinite-Width Limits

To analyze the computational complexity of inference without the bottlenecks of finite depth, the authors study Transformers in the infinite-width limit under two regimes:

1. Lazy Regime (NTK/NNGP): The network behaves as a kernel machine where parameters evolve linearly. The predictor is a weighted sum of training data via a Neural Tangent Kernel (NTK).
2. Rich Regime (Mean-Field): The network learns features, but the authors assume convergence to a limit where the discrepancy between the finite network and the infinite limit scales as $P^\gamma/N$.

C. Complexity Analysis

The core of the methodology involves deriving upper bounds on the inference-time computational complexity (Floating Point Operations, FLOPs) required to evaluate the predictor for a sequence of length $T$.

• They analyze the cost of evaluating the kernel predictor, which involves propagating token-to-token covariance matrices through the network layers.
• They utilize Monte Carlo (MC) sampling to estimate the expectations in the kernel recursion, analyzing how the number of samples ($N_{MC}$) scales with $T$ to maintain constant accuracy.

3. Key Contributions

1. Formal Definition of Algorithmic Learning: The paper provides the first verifiable, formal definition distinguishing true algorithmic learning from statistical interpolation based on sample complexity scaling with problem size.
2. Inductive Bias towards Low Complexity: The authors prove that despite the universal expressivity of infinite-width Transformers (they can theoretically represent any function), their inductive bias restricts them to learning algorithms within the Efficient Polynomial Time Heuristic Scheme (EPTHS) class.
   • Lazy Regime Bound: The inference complexity is bounded by $O(T^{3+\epsilon})$.
   • Rich Regime Bound: Under reasonable assumptions about feature learning convergence, the bound tightens to $O(T^{2+\epsilon})$.
   • Implication: Transformers cannot capture algorithms requiring heuristic complexity higher than these bounds, regardless of depth or training data.
3. Empirical Verification of Capture vs. Failure:
   • Captured: The model successfully captures Induction Heads (search-like behavior) and Sorting. These tasks align with the $O(T^2)$ or $O(T^3)$ bounds and show logarithmic sample scaling.
   • Failed: The model fails to capture Shortest Path Problem (SPP) and MinCut/MaxFlow, even with very deep architectures (40 layers). These tasks have heuristic complexities ($O(T \log T)$ for SPP, $O(T^3)$ for MinCut) that either push against or exceed the derived inference bounds, resulting in superlinear sample scaling (failure to generalize).

4. Key Results

• Theoretical Bounds (Table 1):

  • Lazy (NTK) Regime: Inference complexity is $O(T^3)$ (dominated by kernel evaluation and matrix multiplication).
  • Rich Regime: If the network converges to a rich limit with width scaling $N \propto P^\gamma$, the complexity drops to $O(T^2)$, matching the cost of a standard forward pass.
  • Conclusion: Feature learning (Rich regime) improves sample complexity but does not fundamentally alter the inference-time complexity class; the inductive bias remains towards $O(T^2)$ or $O(T^3)$ algorithms.

• Experimental Findings:

  • Induction & Sorting: Showed "Algorithmic Capture." The relative cost of fine-tuning ($P/P_0$) grew logarithmically with $T$, confirming the definition.
  • SPP & MinCut: Showed "Algorithmic Failure." Both shallow and deep models exhibited superlinear growth in sample cost as $T$ increased. Even 40-layer networks failed to generalize to larger graph sizes, suggesting the algorithmic complexity of these tasks exceeds the Transformer's inductive bias.

5. Significance and Implications

• Redefining "Understanding": The paper moves beyond philosophical debates about "understanding" by providing a mathematical criterion: if a model cannot generalize with logarithmic sample adaptation, it has not algorithmically captured the task.
• Limits of Scaling: The results suggest that simply increasing model depth or width (scaling laws) may not enable Transformers to learn high-complexity algorithms (like general graph traversal or flow optimization) if the inference-time complexity of the algorithm exceeds the model's inherent bias ($O(T^2)$ or $O(T^3)$).
• Inductive Bias vs. Expressivity: It highlights a crucial distinction: Infinite-width Transformers are universally expressive (can represent complex functions) but are not universally learnable (their inductive bias prevents them from finding high-complexity solutions via gradient descent/kernel methods).
• Future Directions: The paper suggests that to solve higher-complexity problems, architectures may need to be structurally isomorphic to the target algorithm (e.g., Graph Neural Networks for graph problems) or utilize mechanisms like "scratchpads" (chain-of-thought) that effectively change the inference complexity class, which was outside the scope of this specific single-token prediction analysis.

In summary, the paper establishes that Transformers possess a "low-complexity bias" that allows them to master tasks like sorting and induction but fundamentally inhibits them from learning complex combinatorial algorithms like MinCut or general shortest paths, regardless of depth, due to the computational cost of their inference mechanisms.