Searching for Autoregressive Neural Architectures from Fundamental Operations

Thomas Woehrle, Linus Ericsson, Henry Gouk, Elliot J. CrowleyarXiv 2026 · arXiv

TL;DR

This paper introduces einspaceAR, a novel search space for Neural Architecture Search (NAS) that builds autoregressive sequence models from fundamental operations like additions and matrix multiplications. By explicitly tracking causality within a context-free grammar, the authors enable the discovery of high-performing sequence models from scratch, without relying on pre-defined high-level blocks like Transformers or Mamba.

What Problem Does This Paper Address?

Most Neural Architecture Search (NAS) algorithms operate within narrow constraints. They typically search for the best way to arrange high-level, human-designed "cells" or modules (like a standard Transformer block). While efficient, this approach prevents NAS from discovering truly novel architectural breakthroughs—it can find a better convolutional network, but it might never "invent" the Transformer.

To solve this, researchers previously developed "expressive" search spaces like einspace, which build architectures from the ground up using fundamental operations. However, these spaces were designed for image classification and fail at autoregressive (AR) sequence modeling. In AR tasks, a model must predict the next token without "peeking" at the future. Standard expressive search spaces have no inherent way to prevent this "future leakage," leading to architectures that "cheat" during training but fail during inference.

Methods

The authors extend the einspace framework to create einspaceAR. The core of their approach is modifying the Context-Free Grammar (CFG) that defines how architectures are sampled.

Key technical innovations include:

  • Causality Tracking: They added two new parameters to the CFG: causal_dim_index (to identify the sequence dimension) and causal_ignore_mask (to track which values represent future information).
  • Dynamic Masking: Operations like matmul or softmax are made "causality-aware." For example, if a matmul operation results in future leakage, the grammar automatically applies a causal mask or prevents the operation from being selected if it cannot be made causal.
  • Grammar Adjustments: They added fundamental operations necessary for modern sequence modeling (like causal_conv_1d, SiLU, and GELU) and removed operations that inherently violate causality (like standard batchnorm).
The grammar (CFG) used to define the search space. Red symbols are removed from the original einspace, and green ones are added for einspaceAR.

To ensure their discovered models were truly valid, they implemented a Causality Check: comparing a model's output on a full sequence versus a truncated prefix. If the outputs for the same position differ, the architecture is leaking information and is discarded.

Datasets

The authors evaluated their search space on:

  1. MAD (Mechanistic Architecture Design): A suite of 6 synthetic tasks (e.g., in-context recall, compression) designed to test specific sequence modeling capabilities. They tested both "Normal" and "Hard" versions.
  2. TinyShakespeare: A character-level language modeling task using the works of Shakespeare.
  3. BabiStories: A synthetic dataset of children's stories used to test more complex language modeling.

Key Insights and Ideas

  • Evolutionary "Cheating": The authors discovered that without strict causality tracking, evolutionary search algorithms are incredibly good at finding "bugs" in the search space to exploit future leakage, as it leads to a deceptively low training loss.
  • Rediscovering Attention: When searching from scratch (starting from a single symbol), the NAS often rediscovered constructs similar to linear self-attention and causal convolutions. This suggests these aren't just human biases but are fundamentally effective ways to process sequences.
  • Grammar as a Blueprint: The paper provides a "blueprint" for how other expressive search spaces can be adapted for autoregressive tasks by treating causality as a trackable tensor property within a grammar.

Key Results

The architectures found by einspaceAR (named ARCH1 through ARCH6) proved highly competitive with established baselines like Transformers and Mamba, despite being searched for from fundamental operations.

  • MAD Benchmarks: On the "Hard" MAD tasks, the discovered ARCH4 achieved an average accuracy of 58.22%, vastly outperforming the Transformer baseline, which struggled at 23.55%.
  • Language Modeling: On TinyShakespeare, einspaceAR found models from scratch that matched the perplexity of a GPT-2 baseline (~6.11 vs 6.14).
  • Efficiency: The NAS-found architectures were strictly smaller (in terms of parameter count) than the baseline models they were compared against.
Table 1: Accuracies on the 6 MAD (Poli et al., 2024) tasks. We search our einspaceAR search space three times per difficulty. The results show that einspaceAR finds architectures that approach the performance of the baselines. The baselines and NAS architectures are trained and evaluated three times on each task resulting in the reported mean and standard deviation. The NAS-found architectures are strictly smaller than the corresponding baseline architectures with details on parameter counts in appendix A.4.

Limitations and Future Work

  • Search Complexity: Because the search space is so vast (building from matmuls rather than blocks), the evolutionary search can be computationally expensive and sometimes results in high variance between runs.
  • Architectural Diversity: While the models perform well, they mostly rely on variants of linear attention. The authors suggest that adding more complex "primitives" (like the State Space Model operations found in Mamba) might be necessary for more difficult tasks like BabiStories.
  • Scaling: The current work focuses on small-scale models (up to 20M parameters). Testing how these "bottom-up" discovered architectures scale to billions of parameters remains an open question.
Visualizations of the discovered architectures. ARCH1 and ARCH6 show complex, non-standard connectivity patterns.

Summary updated

Abstract

Expressive Neural Architecture Search (NAS) search spaces are desirable as they do not restrict the space of potential architectures to what is already established. However, few search spaces are expressive enough to represent a broad range of architecture families, and those that are have focused primarily on image classification problems. The task of autoregressive sequence modelling has become ubiquitous in modern machine learning, but no existing search space supports the construction of and search over sequence models from fundamental operations, instead imposing strong inductive biases on the structure of potential architectures. This work describes how the expressive einspace search space can be extended to yield a search space capable of representing autoregressive models using fundamental operations. We perform a series of experiments showing that the novel einspaceAR search space can find capable autoregressive sequence models from scratch--i.e., without imposing strong inductive biases. We believe that our einspaceAR search space will be a useful part of the NAS toolbox and that the techniques described in this work can serve as a blueprint for the integration of autoregressive modelling in other expressive search spaces.
BibTeX
@misc{woehrle2026searching,
  author = {Thomas Woehrle and Linus Ericsson and Henry Gouk and Elliot J. Crowley},
  title = {{Searching for Autoregressive Neural Architectures from Fundamental Operations}},
  year = {2026},
  eprint = {2611.21111},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21111},
}
Figure