The Gap Between Neural Expressivity and Practical Learnability

983 concepts611 papers2 proposals

Theoretical computer science loves to prove what neural networks can do. We know that recurrent neural networks (RNNs) and Transformers are Turing-complete under certain conditions, meaning they can theoretically simulate any classical algorithm. But if you have ever tried to train a standard Transformer to perform long-digit addition or perfectly track states in a complex game, you know there is a massive catch: proving a network can represent a solution does not mean gradient descent will ever find it.

This disconnect is known as the expressivity-learnability gap (or the optimization-representation trade-off). It represents the frontier between mathematical capacity and empirical reality. To understand why this gap exists, we must look at how we construct theoretical solutions versus how optimization algorithms navigate the loss landscape.

The Illusion of Capacity: Constructive Proofs

How do we know a neural network is capable of solving a complex task? In theoretical deep learning, researchers often use "constructive proofs"—manually engineering a specific set of weights to prove an architecture's capacity.

For example, Satwik Bhattamishra et al. proved that Transformers are Turing-complete even without explicit positional encodings by showing how specific residual connections can be mathematically forced to handle multi-step reasoning. To systematize this style of proof, Andy Yang et al. compiled a "cookbook" of exact mathematical recipes to manually program Transformers to execute arithmetic and formal logic.

These constructions can be incredibly sophisticated:

  • Debanjan Dutta et al. proved that a transformer encoder can act as a universal simulator of the attention mechanism itself.
  • Weimin Wu et al. showed that a deep Transformer can mathematically simulate the entire training process of a multi-layer ReLU network within a single forward pass.
  • In the realm of recurrent networks, Natalie Schluter demonstrated that RNNs are expressive enough to implicitly simulate complex dynamic programming algorithms like Eisner’s within their hidden states, while John Hewitt proved they can generate bounded hierarchical languages with optimal memory.

Yet, these perfect weight configurations exist as isolated, infinitesimally small points in a massive parameter space. As Shaobo Lin notes, constructing a weight matrix that solves a problem offers no guarantee that standard optimization algorithms can learn those weights from data. Proving that an architecture can express a solution does not mean standard training procedures will converge to it.

Why Optimization Fails: The Geometry of the Loss Landscape

If the perfect weights exist, why does standard training miss them? The answer lies in the geometry of the loss landscape. Gradient descent relies on local, continuous signals to navigate toward a global minimum. However, algorithmic and logical tasks often feature discrete state transitions that create highly irregular, flat, or noisy loss landscapes.

Shai Shalev-Shwartz et al. demonstrated that for families of simple problems like learning parities or multi-step visual tasks, gradient-based optimization fails because the gradient signal vanishes or becomes completely drowned out by noise. The issue isn't that a valid solution doesn't exist; it's that there is no informative path leading the optimizer there.

Furthermore, Peter Cholak et al. highlighted that as sequence lengths grow, the loss landscapes for tasks requiring strict logical precision (like computing parity) become highly sensitive, causing standard gradient methods to break down. This decoupling means that failures on complex logic tasks stem from optimization path challenges rather than inherent architectural limitations. Even outside gradient descent, such as in genetic programming, Nur Merve Amil proved that search dynamics often fail to locate optimal solutions within vast hypothesis spaces due to the sheer complexity of the search landscape.

The Gap in Action: Automata, Graphs, and Reasoning

The expressivity-learnability gap manifests across several domains, revealing a stark divergence between what models can express and what they actually learn.

Formal Languages and Automata

While Anej Svete et al. proved that Transformers can exactly represent any $n$-gram language model, empirical training often fails to discover these exact structures. Jaron Maene et al. extracted finite state machines from trained models and found that they often fail to learn critical "garbage states" when trained on finite data.

Similarly, Stefan C. Kremer established a representational ceiling for recurrent cascade-correlation networks, proving that even when an architecture might seem flexible, its optimization rules are strictly constrained by input periodicity. Gregoire Deletang bridged this with computation theory, demonstrating that a model's ability to generalize is fundamentally constrained by its architecture's position on the Chomsky Hierarchy, yet backpropagation often fails to find valid solutions even when the architecture allows it.

Graph Neural Networks (GNNs)

Martin Grohe and Ryoma Sato et al. have shown that while GNNs possess the theoretical capacity to represent specific graph properties or achieve optimal approximation ratios for combinatorial problems, gradient-based training routinely fails to converge on those parameters.

Davide Bacciu et al. showed how GNNs can approximate discrete dynamic programming algorithms via tropical algebra, yet they emphasize the fundamental disconnect between this representational capacity and practical trainability. Similarly, Chen Cai et al. proved that adding a virtual node makes message-passing networks theoretically as powerful as Graph Transformers, but note the gap between this mathematical capacity and the practical ability of gradient descent to learn the function within a specific model structure.

In-Context Learning (ICL) and Chain of Thought

A popular theoretical framework suggests that Transformers perform ICL by implicitly implementing gradient descent within their activations. Khashayar Gatmiry et al. provided the first proof that looped Transformers can actually learn to implement multi-step gradient descent for linear regression.

However, Zhijie Wang et al. caution that while a Transformer can act as a meta-optimizer for complex non-linear functions, standard training on large-scale datasets does not guarantee that this elegant mechanism will naturally emerge. This disconnect also explains why prompting tricks are necessary: Zhiyuan Li et al. showed that while Transformers can mathematically express solutions to inherently serial problems, they require Chain-of-Thought (CoT) prompting to alter the optimization dynamics and allow standard training to discover these complex serial algorithms.

Bridging the Gap: Compilers and Inductive Biases

To close this gap, researchers are developing tools to diagnose optimization failures and designing architectural modifications that smoothen the loss landscape.

One approach is to use intermediate execution traces to see exactly where standard training goes off the rails. Peter Shaw 0004 et al. introduced ALTA, a compiler that translates symbolic algorithms directly into Transformer weights. By comparing a trained model's internal activations to ALTA's "ground truth" program, the authors showed that models often satisfy training constraints using non-robust heuristics rather than the intended logical structure.

Another strategy involves altering the architecture to align its inductive biases with the target task. For instance, Peter Cholak et al. showed that incorporating layer normalization and a novel "log-length scaling" trick allows gradient descent to successfully find solutions that generalize to much longer sequences, effectively bridging the gap between theoretical capacity and practical trainability.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 651 papers
  2. Version 1 · 2026-10-04 · 455 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_expressivity_learnability_gap_f9e85ecc,
  title = {expressivity-learnability gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressivity-learnability-gap/rdr_f9e85ecc681d4a2c98ad9a64323ad99c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_expressivity_learnability_gap_f9e85ecc_v2,
  title = {expressivity-learnability gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressivity-learnability-gap/rdr_f9e85ecc681d4a2c98ad9a64323ad99c/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake