Trained transformer models have been found to implement interpretable procedures for tasks like arithmetic and associative recall, but little is understood about how the circuits that implement these procedures originate during training. To what extent do they depend on the supervisory signal provided to models, and to what extent are they attributable to behavior already present in models at the beginning of training? To investigate these questions, we investigate what functions can be learned by randomly initialized transformers in which only the embedding layers are optimized, so that the only input--output mappings learnable from data are those already implemented (up to a choice of encoding scheme) by the randomly initialized model. We find that these random transformers can perform a wide range of meaningful algorithmic tasks, including modular arithmetic, in-weights and in-context associative recall, decimal addition, parenthesis balancing, and even some aspects of natural language text generation. Our results indicate that some algorithmic capabilities are present in transformers (and accessible via appropriately structured inputs) even before these models are trained.

Do neural networks, trained on well-understood algorithmic tasks, reliably rediscover known algorithms? Several recent studies, on tasks ranging from group operations to in-context linear regression, have suggested that the answer is yes. Using modular addition as a prototypical problem, we show that algorithm discovery in neural networks is sometimes more complex: small changes to model hyperparameters and initializations can induce discovery of qualitatively different algorithms from a fixed training set, and even learning of multiple different solutions in parallel. In modular addition, we specifically show that models learn a known *Clock* algorithm, a previously undescribed, less intuitive, but comprehensible procedure we term the *Pizza* algorithm, and a variety of even more complex procedures. Our results show that even simple learning problems can admit a surprising diversity of solutions, motivating the development of new tools for mechanistically characterizing the behavior of neural networks across the algorithmic phase space.

Unbounded SubsetSum is a classical textbook problem: given integers w1,w2, …, wn∈[1,u], c,u, we need to find if there exists m1,m2, …, mn ∈ ℕ satisfying c =Σni=1 wimi. In its all-target version, t ∈ ℤ+ is given and the answers for all integers c ∈ [0, t] are required. In this paper, we study three generalizations of this simple problem: All-Target Unbounded Knapsack, All-Target CoinChange and Residue Table. With new combinatorial insights into the structures of solutions, we present a novel two-phase approach. As a result, we show that: • All-Target CoinChange can be solved in Õ(u +t) time deterministically, improving the previous Õ(t4/3) time algorithm [Chan and He, ESA 2020]. • Residue Table can be solved in Õ(u) time deterministically, improving the previous Õ(u3/2) time algorithm [Klein, 2021]. •All-Target Unbounded Knapsack can be solved in Õ(T(u) + t) time, where is the running time for (min, +) convolution for length-n arrays, improving the previous O(u2 log u + t) time algorithm [Chan and He, ESA 2020].

A simplicial vertex of a graph is a vertex whose neighborhood is a clique. It is known that listing all simplicial vertices can be done in $O(nm)$ time or $O(n^ω)$ time, where $O(n^ω)$ is the time needed to perform a fast matrix multiplication. The notion of avoidable vertices generalizes the concept of simplicial vertices in the following way: a vertex $u$ is avoidable if every induced path on three vertices with middle vertex $u$ is contained in an induced cycle. We present algorithms for listing all avoidable vertices of a graph through the notion of minimal triangulations and common neighborhood detection. In particular we give algorithms with running times $O(n^{2}m)$ and $O(n^{1+ω})$, respectively. Additionally, based on a simplified graph traversal we propose a fast algorithm that runs in time $O(n^2 + m^2)$ and matches the corresponding running time of listing all simplicial vertices on sparse graphs with $m=O(n)$. Moreover, we show that our algorithms cannot be improved significantly, as we prove that under plausible complexity assumptions there is no truly subquadratic algorithm for recognizing an avoidable vertex. To complement our results, we consider their natural generalizations of avoidable edges and avoidable paths. We propose an $O(nm)$-time algorithm that recognizes whether a given induced path is avoidable.