# Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem

arXiv: https://arxiv.org/abs/2507.09816 · HTML: https://mlsanity.com/paper/2507.09816/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 10 references that are in the map.
- First posted on arXiv 13 Jul 2025.

## Builds on (most cited first, 7 of 7)

- [Sparse Autoencoders Find Highly Interpretable Features in Language Models](https://mlsanity.com/paper/2309.08600/) (2023)
- [Toy Models of Superposition](https://mlsanity.com/paper/2209.10652/) (2022)
- [The Linear Representation Hypothesis and the Geometry of Large Language Models](https://mlsanity.com/paper/2311.03658/) (2023)
- [Polysemanticity and Capacity in Neural Networks](https://mlsanity.com/paper/2210.01892/) (2022)
- [Mathematical Models of Computation in Superposition](https://mlsanity.com/paper/2408.05451/) (2024)
- [Interpretability in Parameter Space: Minimizing Mechanistic Description Length with Attribution-based Parameter Decomposition](https://mlsanity.com/paper/2501.14926/) (2025)
- [On the Complexity of Neural Computation in Superposition](https://mlsanity.com/paper/2409.15318/) (2024)

## Built on by (most cited first, 1 of 1)

- [The Ball and the Box: Two Geometries of Computation in Superposition](https://mlsanity.com/paper/2610.11744/) (2026)

## Abstract (arXiv)

Neural networks are capable of superposition -- representing more features than there are dimensions. Recent work considers the analogous concept for computation instead of storage, proposing theoretical constructions. But there has been little investigation into whether these circuits can be learned in practice. In this work, we investigate a toy model for the Universal-AND problem which computes the AND of all mchoose 2 pairs of m sparse inputs. The hidden dimension that determines the number of non-linear activations is restricted to pressure the model to find a compute-efficient circuit, called compressed computation. We find that the training process finds a simple solution that does not correspond to theoretical constructions. It is fully dense -- every neuron contributes to every output. The solution circuit naturally scales with dimension, trading off error rates for neuron efficiency. It is similarly robust to changes in sparsity and other key parameters, and extends naturally to other boolean operations and boolean circuits. We explain the found solution in detail and compute why it is more efficient than the theoretical constructions at low sparsity. Our findings shed light on the types of circuits that models like to form and the flexibility of the superposition representation. This contributes to a broader understanding of network circuitry and interpretability.