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) andcausal_ignore_mask(to track which values represent future information). - Dynamic Masking: Operations like
matmulorsoftmaxare made "causality-aware." For example, if amatmuloperation 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, andGELU) and removed operations that inherently violate causality (like standardbatchnorm).
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:
- 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.
- TinyShakespeare: A character-level language modeling task using the works of Shakespeare.
- 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
ARCH4achieved an average accuracy of 58.22%, vastly outperforming the Transformer baseline, which struggled at 23.55%. - Language Modeling: On TinyShakespeare,
einspaceARfound 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.
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.
Summary updated