The Limits of Algorithm Acquisition in Sequence Models

Can neural networks acquire computational procedures absent from training? Prior evaluations are confounded by the possibility that a model saw the target task during pretraining. We introduce , a procedurally generated benchmark in which target computations are sampled only after a pretrained model is fixed, isolating acquisition of genuinely unseen functions from primitive familiarity. Each target is a previously unseen member of a small, structured computational family – not an open-endedly novel procedure – but rapid acquisition of such a target is itself a nontrivial, underexamined question, and we claim no more than that. In small, controlled synthetic sequence models – not Internet-scale language models – we find a sharp acquisition bottleneck: single-stream computations are learned to near-perfect accuracy, while non-separable two-stream computations – additive or multiplicative combinations of raw stream values, and arbitrary joint lookups alike – fail catastrophically. Separability, not stream count, governs the outcome: two-stream targets built from two independently sampled, information-compressing per-stream transformations ($z=f(x)+g(y)$ or $z=f(x)g(y)$) are learned as well as single-stream targets, even though the same combination of untransformed streams fails completely. Separability alone is not sufficient, however – a bijective (information-preserving) separable variant fails just as badly, a result we report but do not fully explain. The failure persists across Transformer, recurrent, and convolutional architectures; a $271\times$ parameter range; and larger optimization budgets. Fixing one input stream restores near-perfect learning of the same target, and coupling the two streams progressively restores performance, localizing the bottleneck to jointly combining two independently varying streams – not to sequential state, target complexity, or capacity. Pretraining does not reliably remove this bottleneck in our setting; whether it persists at frontier scale remains open. NORA offers a framework for studying what pretrained representations contribute to acquiring genuinely new computations, and for locating exactly where that transfer breaks down.