We formally define algorithmic capture of combinatorial tasks as the ability of a transformer to extrapolate to arbitrary task sizes with controllable error and logarithmic sample adaptation, providing a sharp scaling criterion for distinguishing logic internalization from statistical interpolation. Empirically, across scaling ranges spanning up to 2.5 orders of magnitude, we observe evidence of capture and non-capture. By analyzing infinite-width transformers in both the lazy and rich regimes, we derive upper bounds on the inference-time computational complexity of the combinatorial tasks these networks can capture. We show that, despite their universal expressivity, transformers possess an inductive bias that disfavors higher-complexity algorithmic procedures within the efficient polynomial-time heuristic scheme class, consistent with successful capture on simpler combinatorial tasks such as induction heads, sort, and string matching.
Figures & tables
Regime
Evaluation
Inference Complexity
Evaluation Error
EPTHS
NNGP/NTK
Kernel estimate
O(PN\mtcT3)
P/N\mtc
O(T3+ϵ)
Forward-pass
O(NT2)
Pγ/N
O(T2+ϵ)
Rich Mean-Field Scaling
Forward-pass
O(NT2)
Pγ/N
O(T2+ϵ)
Table 1: Summary of theoretical results. For infinite lazy transformers, the kernel-predictor (NNGP/NTK) can be estimated using Monte Carlo with the specified inference complexity and error. Consequently, tasks with EPTHS complexity larger than T3 times log factors cannot be captured ( T3+ϵ ). Approximating this predictor by a forward-pass on an extensive width network ( N∝Pγ≥1 ), we obtain an improved bound on the complexity of capturable tasks under lazy learning. Making the reasonable assumption that extensive networks with rich scaling converge to their rich/mean-field limits, we obtain the same complexity bound even under strong feature learning.
Figure 1: Empirical Combinatorial Task Capture. We train various models on combinatorial task instances of size T0 (1st point on the x-axes) reaching accuracy δ after seeing P0(δ) datapoints. We then fine-tune these models on larger instance sizes ( T>T0 ), re-achieving δ -accuracy after P extra datapoints. Panels (a)-(c) show linear-log plots of relative adaptation cost ( P/P0 ). Panels (a)-(b) show evidence of task capture consistent across seeds. Panel (c) shows task capture on average while individual seeds transition between different slopes. Panels (e)-(f) present results from a study of the combinatorial graph tasks, SPP and MinCut, that exhibit accelerating curves on a linear-linear scale. Solid lines are best fits to Clog(T/T0) meant to guide the eye. To mitigate expressivity concerns, depth 40 networks were used for the purple datapoints in Panels (e)-(f). For the Context Free Grammar task on Panel (g), our theoretical bounds prohibit capture at fixed-depth regardless of model capacity. Panels (a,e,f) show average empirical curves with one STD error bars together with best fits to a log. Panels (b,c,g) report individual seeds (thin lines) as well as averages (thick lines).
We introduce universal transformers: fixed transformers that can simulate any transformer in a given class via a suitable input embedding. Analogous to a universal Turing machine, the input embedding encodes a description of the target model while all internal parameters remain fixed. We provide explicit sparse constructions achieving universality when the embedding dimension is sufficiently large, and further show that universality is generic: randomly initialized transformers are universal almost surely, which aligns with recent empirical results of Zhong and Andreas (2024). We empirically validate our theory on the algorithmic tasks of parenthesis balancing and multi-hop reasoning. Our results suggest that much of a transformer's expressive power may reside in its input representation rather than its learned weights.
Transformers are remarkably versatile and their design is largely consistent across a variety of applications. But are they optimal for any given task or dataset? The answer may be key for pushing AI beyond merely scaling current designs. Method. We present a method to optimize a transformer architecture for a given dataset, which we use as a tool to study optimal task-specific inductive biases. This method replaces the most important non-linearities (GeLUs,;softmax) with functions learned on held-out data. We then train the resulting architectures on other datasets, as a way to evaluate the compatibility between pairs of tasks. Findings. On algorithmic toy tasks, we identify new architectures with dramatic improvements in learning speed, in- and out-of-distribution generalization, and stability across seeds. The new designs prove very task-specific however, and indicate that these tasks require inductive biases very different from those of standard transformers. On code and language modeling datasets, we also find architectures with consistent, yet smaller improvements. These designs transfer much better across datasets and domains (English & computer code). Implications. Our results show that standard transformers are rarely a local optimum in the space of architectures. Simple alternatives can perform much better but sacrifice universality. This suggests that there may be room for improved architectures that better support multiple capabilities simultaneously, such as fluency and robust reasoning.
Learning generalizable algorithmic computations remains a challenge for neural networks, as reflected in persistent failures on compositional and length generalization benchmarks. We present a provably correct, transformer parameterization (with only 280 learnable parameters for Boolean algebra tasks) capable of learning and evaluating problems of any depth or length. We assume inputs are fully parenthesized, well-formed expressions. Our approach conceptualizes algorithmic tasks as circuit models embedded in transformers, enabling depth-1 circuit reduction in a single forward pass. To achieve depth generalization, we introduce a positional encoding that tracks each gate's depth within the circuit, enabling the model to identify evaluable subexpressions at each iteration via masked hard attention, with O(n) per-iteration complexity via linear attention. Combined with an autonomous halting criterion, the model terminates after d iterations for problems of depth d, yielding O(n⋅d) total complexity. We show that training on shallow problem instances (depth 1 and depth 2) effectively recovers interpretable parameters that {\em snap} into place, resulting in exact length generalization. Though we establish that our construction provably evaluates Boolean expressions -- a universal symbolic computation -- of arbitrary length perfectly, in other experiments we also demonstrate that our transformer variant can learn and generalize perfectly (100% accuracy) on other common length generalization benchmarks, including modular arithmetic and ListOps.