Can universal function approximators be expensive to learn in practice?
This explores the gap between what a model can represent in theory (universal approximation — the proof that a network *could* express any function) and what it can actually learn from data at reasonable cost, which the corpus treats as two very different things.
This explores whether 'universal function approximator' is a theoretical badge that quietly stops mattering in practice — and the corpus answers with a resounding yes. The cleanest illustration is the finding that MLPs, despite being provably expressive enough to represent any function, fail to recover something as simple as a dot product similarity in collaborative filtering Can MLPs learn to match dot product similarity in practice?. They need enormous capacity and data to even approach what a tuned geometric similarity does for free — the punchline being that *inductive bias beats expressiveness*. Universal approximation tells you a function exists in the model's reach; it says nothing about whether gradient descent will find it before you run out of data and patience.
The same wedge between 'can represent' and 'can learn' shows up at the frontier. There's a proof that a single finite-size transformer can compute *any* computable function given the right prompt — prompts are literally Turing-complete programs Can a single transformer become universally programmable through prompts?. But the same work notes that standard training almost never produces a model that has actually learned to run arbitrary programs. The capability is latent and astronomically expensive to elicit; it doesn't fall out of ordinary optimization. So 'universal' is true and nearly useless as a guide to what you'll get.
What you get instead, repeatedly, is memorization wearing the costume of computation. LLMs asked to run iterative numerical methods don't iterate — they recognize a problem as template-similar to something seen before and emit plausible-but-wrong answers, a failure that doesn't go away with scale Do large language models actually perform iterative optimization?. Even RL fine-tuning, which you'd hope installs genuine procedures, mostly sharpens template-matching: GRPO-trained models collapse on slightly out-of-distribution variants of the very tasks they ace in-distribution Do fine-tuned language models actually learn optimization procedures?. And on genuine constrained optimization, models flatline around 55–60% regardless of parameter count or training regime — a ceiling, not a scaling gap Do larger language models solve constrained optimization better?. A universal approximator that plateaus is the whole paradox in one sentence.
The deeper reason these costs are structural, not incidental, is that the architecture has a grain. Treating an LLM as an autoregressive probability machine lets researchers *predict in advance* which logically-trivial tasks (counting letters, reciting the alphabet backwards) will be hard, because their target outputs are low-probability under the training distribution Can we predict where language models will fail?. Expressiveness is uniform across functions; learnability is not. The functions that are cheap to learn are the ones the architecture and data are already biased toward, and the rest can be arbitrarily expensive — sometimes practically unreachable.
The interesting flip side: when learning *is* affordable, it's usually because the method respects that grain rather than fighting it. Transformers achieve exponential length generalization on addition not by brute-forcing a universal solution but by iteratively self-training on their own correct outputs, bootstrapping into harder cases Can transformers improve exponentially by learning from their own correct solutions?. So the take-home isn't 'approximators are doomed' — it's that the cost of learning a function lives almost entirely in the mismatch between the function and the model's built-in biases, which is exactly what the universal-approximation theorem promises to ignore.
Sources 7 notes
Rendle et al. show that carefully tuned dot products substantially outperform learned MLP similarities in collaborative filtering. MLPs require excessive capacity and data to match simple geometric similarity, and they cannot be efficiently retrieved at scale—proving inductive bias matters more than expressiveness.
Research proves a single finite-size transformer exists that can compute any computable function given the right prompt, achieving complexity bounds nearly matching unbounded models. However, standard training rarely produces models that learn to implement arbitrary programs this way.
Research shows LLMs cannot perform iterative procedures in latent space. They recognize optimization problems as template-similar and emit plausible-looking but incorrect values, a failure mode that persists across model scale and training approaches.
Even GRPO-trained models show sharp performance drops on out-of-distribution variants (N-1 test sets) compared to in-distribution problems, indicating RL optimizes template-matching rather than genuine problem-solving procedures.
Across constrained-optimization tasks, LLMs converge to ~55–60% constraint satisfaction independent of architecture, parameter count, or training regime. Reasoning models do not systematically outperform standard models, suggesting a fundamental ceiling rather than a scaling gap.
By framing LLMs as autoregressive probability machines, researchers predicted tasks with low-probability target responses would be systematically harder, even when logically simple. Experiments confirmed predictions like backwards alphabet and letter counting.
Standard transformers generalize from 10-digit to 100-digit addition by repeatedly generating solutions, filtering for correctness, and retraining—showing exponential (not linear) out-of-distribution improvement across rounds without saturation.