Pith. sign in

REVIEW 3 major objections 5 minor 10 references

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

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Training on the Universal-AND problem learns a fully dense binary-weighted circuit, not the sparse constructions theory predicts.

desk verdict Solid empirical finding of dense binary circuits in a toy model; the efficiency argument is not yet proven. read the letter →

arxiv 2507.09816 v1 pith:DUKDPD7B submitted 2025-07-13 cs.LG cs.AI

Adam Newgas This is my paper
classification cs.LGcs.AI
keywords compressedcomputationUniversal-ANDproblemsuperpositiondensecircuitsbinaryweightedcircuitmechanisticinterpretabilityReLUMLPsparsefeatures
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether compressed computation—getting many Boolean results from a narrow layer of nonlinear neurons—is learnable, not just constructible in theory. Training a one-layer ReLU network with linear readout on the Universal-AND problem, which asks for the AND of every pair of sparse Boolean inputs, the author finds that the model learns a fully dense circuit whose weights take only two values. Every neuron contributes to every output, and a linear combination of four neuron classes recovers the AND truth table. The paper argues this dense circuit is more efficient than existing sparse constructions at low input sparsity, with per-output noise variance $O(s^2/d)$ compared with $O(s/(\sqrt{d}/\log m))$. If correct, this challenges the assumption that circuits in models are sparse subgraphs and shifts how interpretability tools should look for them.

What carries the argument

The load-bearing object is the four-class truth-table decomposition of neurons with respect to a chosen pair of inputs. With weights $u > 0 > l$ and bias $b$, class A ($u,u$), B1 ($u,l$), B2 ($l,u$), and C ($l,l$) give different ReLU outputs for the four input combinations, and the combination $4(A+C-B_1-B_2)$ yields the AND table while cancelling the bias terms. Interference from the other sparse inputs is modelled as independent binomial noise with variance $(u-l)^2 s p(1-p)$, and an unproved linear scaling constant $\beta$ converts that to output variance. The readout averages over $d p^2$ class-A neurons and analogous counts for the other classes, giving the $O(s^2/d)$ variance estimate that is then compared against the sparse construction's $O(s/(\sqrt{d}/\log m))$.

What would settle it

Measure the empirical per-output error of the trained dense circuit on the Universal-AND problem across a grid of sparsity values $s$ and hidden dimensions $d$, and compare the measured scaling of variance with the predicted $O(s^2/d)$; if the exponent in $s$ differs substantially from 2, or if the dense circuit is outperformed by the sparse construction in the claimed low-sparsity regime, the central efficiency claim is falsified.

Watch

Extended reading notes

Core claim

The central discovery is that, under pressure from a narrow hidden dimension, the trained model does not implement the sparse, provably bounded circuits proposed in prior theory. Instead it settles on a Binary Weighted Circuit: each input weight is drawn from one of two values, high with probability $p \approx 0.75$ and low with probability $1-p$, with no pattern in the assignment. For any pair of inputs the neurons fall into four classes according to which weight each of the two inputs receives; averaging the class activations with readout coefficients proportional to about $\pm 4\sqrt{s}$ reproduces $v_i \wedge v_j$. The circuit uses every neuron for every output, and the model prefers it across nearly all hidden dimensions tested, including $d = \binom{m}{2}$, where a dedicated neuron per pair would be possible.

Load-bearing premise

The efficiency comparison depends on treating the interference from unrelated inputs as independent binomial noise and assuming ReLU output variance is a constant multiple of input variance; the author states in Section 7 that these approximations are not rigorously proved.

Editorial extensions

If this is right

  • The same training setup finds a dense circuit at almost every hidden dimension studied; even when there are enough neurons to assign one per AND pair, the model spreads each computation over many neurons instead.
  • The learned circuit is robust to changes in sparsity and other key parameters within the low-sparsity regime, and fails only when sparsity becomes too high (around $s=10$ for $m=100$).
  • The readout can be recombined to implement other Boolean operations and multi-way truth tables, suggesting one layer of ReLU can host a library of Boolean circuits read out linearly.
  • Because the dense circuit has lower variance than the sparse construction in the low-sparsity regime, sparse theoretical constructions may not be the right reference point for what trained networks do.
  • Weight decay biases training toward spreading circuits out, so dense circuits are a natural product of regularized training rather than an anomaly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An alternative reading the paper itself raises in an appendix is that any Boolean function of sparse binary features held in random directions may be linearly readable with bounded error; this would make dense circuits a generic property of random embeddings, with binary weights only a modest constant-factor improvement.
  • If dense averaging is genuinely preferred, sparse-circuit interpretability methods such as pruning or sparse autoencoders may systematically miss the computational substrate in real models; this is an extension of the paper's conclusion, not proven here.
  • A direct test of the claimed scaling is to measure per-output error on the same task while varying $s$ and $d$ and comparing the empirical exponent of variance in $s$ to the predicted $s^2$; the paper does not report such a scaling sweep.
  • The XOR readout observation suggests regularized models will favour the lower-weight linear direction, which may explain why linear probes can still generalize despite the presence of XOR features.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper trains a one-layer ReLU MLP with a linear readout on the Universal-AND problem, where m sparse binary inputs must produce all pairwise AND outputs. The main empirical claim is that, for sufficiently sparse inputs, training converges to a 'Binary Weighted Circuit': each hidden neuron's input weights take (approximately) one of two values, and every neuron contributes to every readout. The paper groups neurons into four classes according to their weights on a distinguished input pair, derives an approximate truth table, and argues that a dense circuit has output variance O(s^2/d), compared with O(s/(sqrt(d)/log m)) for the sparse construction of Hänni et al., so the dense circuit is more efficient at low sparsity. Section 5 presents weight and readout plots supporting the empirical finding; Section 6 gives the circuit analysis and efficiency comparison; Section 7 explicitly acknowledges that the analysis relies on unproved approximations. The paper also notes extensions to other Boolean operations and discusses connections to superposition and interpretability.

Significance. The empirical observation that a trained model prefers a dense, approximately binary-weight circuit over the sparse theoretical constructions is a useful and potentially reproducible contribution to the mechanistic-interpretability and compressed-computation literature. The paper is honest about its limitations, and the inclusion of code in the supplemental materials is a strength. However, the advertised quantitative efficiency comparison is not established by the present analysis: it depends on an unproved readout-weight scaling and on a variance approximation whose s-dependence is uncontrolled. If the empirical finding is taken on its own, the paper is a solid empirical study; the theoretical efficiency claim should be read as an approximate, post-hoc explanation rather than a proven result.

major comments (3)
  1. [Section 6.2, footnote 5] The claim that the total readout weight for each of the four neuron classes is approximately ±4√s is asserted without proof, and it is load-bearing: it supplies one of the two factors of s in the claimed Var_Binary = O(s^2/d). The readout weights are not free; they must invert the 4x4 matrix of class-mean responses E[ReLU(X+c)] under the actual distribution of the interference term X_i. Solving that system with the paper's representative parameters (u=0.1, l=-0.25, p=0.75, b=0.05) gives total weights close to 4√s at s=3 (about 6.8 versus 6.9) but already about 10.2 at s=10, versus 12.6, and the system becomes increasingly ill-conditioned as s grows. The paper needs either an exact computation of the inverse class-mean matrix, or a rigorous bound showing that the total weight per class remains Θ(√s) over the range of s for which the crossover is claimed.
  2. [Section 6.2, Var(ReLU(X)) approximation] The approximation Var(ReLU(X)) = β Var(X) with a constant β is not justified. The sensitivity of E[ReLU(X+c)] to the class-specific shift c is proportional to Φ((μ+c)/σ), which depends on s through σ; as s grows, ReLU approaches an affine function and the class separation is produced in a regime where β may not be constant. Since both variance formulas contain β, a common constant would cancel in the ratio, but an s-dependent β could change the claimed crossover. The authors should either prove a bound on β over the relevant range or test the approximation directly with Monte Carlo estimates as a function of s.
  3. [Sections 5.1, 6.1, 6.2] The efficiency comparison is post-hoc with respect to the observed parameters: u, l, p, and b are taken from a single trained model, and the readout weights are then chosen to match the observed class means. The paper does not explain why the training dynamics select u=0.1, l=-0.25, p=0.75, b=0.05, nor does it give a bound on how the O(s^2/d) conclusion varies over the range of parameters that still satisfy the linear-independence condition. A concrete resolution would be to compare the measured loss of the learned circuit with the CiS construction under identical data and training, or to provide a theoretical bound over the parameter region.
minor comments (5)
  1. [Section 6.2] The line '= 0.35242sβsp(1−p)...' is typeset ambiguously; it appears to conflate the 0.35^2 factor with the 4^2 factor from the readout-weight scaling. Please clarify the algebra.
  2. [Appendix A.2] The word 'readaoutable' is a typo; it should be 'read-outable' or 'linearly decodable'.
  3. [Section 5.1] The description 'binary, i.e., takes on only one of two different values' is confusing because the two values are per-neuron and the charts show substantial deviations; consider saying 'per-neuron two-valued weights' and defining the approximation tolerance explicitly.
  4. [Section 6.1] The statement 'the exact choice of constants is not relevant to the key argument' is in tension with Section 6.2, where the specific values of u, l, p, and b affect the 4x4 matrix inversion and the ±4√s scaling. Please reconcile these claims.
  5. [Section 5] The boundary behavior for s≥10 and d≤m—where the model learns a pure-additive circuit or fails to update W—is important for delimiting the dense-circuit claim and deserves a fuller treatment than a brief appendix note.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the dense-circuit finding is empirical, and the Section 6 efficiency analysis is an explicitly approximate post-hoc explanation, not a prediction forced by fitted inputs.

full rationale

The paper's central empirical claim—that training on the Universal-AND problem yields a dense binary-weighted circuit—is established directly from training runs in Section 5 (Figures 2–6) and does not depend on the theoretical machinery of Section 6. The Section 6 analysis is explicitly framed as an explanation of an already-observed circuit: the abstract says 'We explain the found solution in detail and compute why it is more efficient,' and Section 6.2 asks 'Why is this dense Binary Weighted Circuit learned in preference to the CiS Construction?' The representative values u=0.1, l=-0.25, p=0.75 are read off the trained model and used as inputs to the explanation; they are not fitted to make a prediction. The efficiency comparison Var_Binary=O(s^2/d) versus Var_CiS=O(s/(√d/log²m)) rests on the unproved assertion in Footnote 5 that the total readout weight for each class is approximately ±4√s, plus other approximations (binomial interference, constant β). Section 7 explicitly disclaims these: 'Section 6 relies on several approximations that are not rigorously proved.' Those are correctness/rigor limitations, not circular reductions: no parameter is defined in terms of the target result, no fitted value is relabeled as a prediction, and the paper contains no load-bearing self-citations. Therefore, no circularity is present.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central empirical finding rests on the observed training runs; the theoretical efficiency analysis adds several unproved approximations. The key parameters u, l, p are taken from observation, not derived, and beta is an unspecified constant.

free parameters (3)
  • u, l, p (binary weight parameters) = u=0.1, l=-0.25, p=0.75 (representative)
    Observed from trained models and used as inputs to the theoretical error analysis in Sections 6.1 and 6.2, but not derived from first principles.
  • beta (ReLU variance scaling) = unspecified constant
    Introduced ad hoc in Section 6.2 to approximate Var(ReLU(X)) proportional to Var(X); no value or justification is given.
  • bias b = 0.05 in illustration
    Chosen for illustration in Section 6.1; the paper claims the exact value is not relevant, but it affects the truth table linear combination.
assumptions (4)
  • domain assumption Inputs are independent beyond the sparsity constraint.
    Used in Section 6.1-6.2 to model the interference term Xi as independent binomial noise.
  • ad hoc to paper ReLU output variance scales linearly with input variance via a constant factor beta.
    Assumed in Section 6.2 to derive Var(y_i) = beta * (u-l)^2 * s * p(1-p).
  • domain assumption The four neuron classes are linearly independent for the chosen parameters, allowing AND to be recovered by a linear combination.
    Stated in Section 6.1 to hold for a wide range of parameters, but not proven.
  • domain assumption Standard training dynamics with the described loss converge to the binary weighted circuit for the tested settings.
    Empirical claim based on the reported runs; no convergence analysis or multi-seed statistics are provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem." pith.science (2026). https://pith.science/paper/DUKDPD7B

@misc{pith2026250709816,
  author       = {Pith},
  title        = {Pith review of: Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DUKDPD7B}},
  note         = {Machine review of arXiv:2507.09816}
}
abstract

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 $m\choose 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.

Figures

Figures reproduced from arXiv: 2507.09816 by the authors.

Figure 1
Figure 1. Our found circuit: For every pair of inputs (e.g. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Model loss as d increases. We find that at low s values, the model does find solutions that are capable of solving the Universal￾AND problem, even extending to extremely low values of d. The model weights take on a simple pattern of binary weights described below. At higher values of s (starting at 10 for m = 100), the model starts to prefer more degenerate solutions, particularly for d ≤ m. It either learns pure-ad… view at source ↗
Figure 3
Figure 3. Distribution of Wij values for the first 10 neurons. Expressed mathematically Wij =  ui with probability pi li with probability 1 − pi We discuss why this is an effective choice in section 6.1. We chart the specific values of ui , li , pi in shown in fig. 4. It illustrates that all neuron weights are clustered in a tight region and uipi + li(1 − pi) ≈ 0 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Distribution of upper/lower weights by neuron. Error bars show 90th-percentile deviation [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: Readout weights by input weights (d = 2000) [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 7
Figure 7. Figure 7: Readout weight by input weights (uniform initialization, [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 9
Figure 9. Figure 9: Similarity of learned weight matrix to a binary distribution for various [PITH_FULL_IMAGE:figures/full_fig_p015_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

10 extracted references · 4 canonical work pages

  1. [1]

    On the complexity of neural computation in superposition

    Micah Adler and Nir Shavit. On the complexity of neural computation in superposition. CoRR, abs/2409.15318, 2024. URL https://doi.org/10.48550/arXiv.2409.15318

    work page doi:10.48550/arxiv.2409.15318 2024

  2. [2]

    Emmanuel Ameisen, Jack Lindsey, Adam Pearce, Wes Gurnee, Nicholas L. Turner, Brian Chen, Craig Citro, David Abrahams, Shan Carter, Basil Hosmer, Jonathan Marcus, Michael Sklar, Adly Templeton, Trenton Bricken, Callum McDougall, Hoagy Cunningham, Thomas Henighan, Adam Jermyn, Andy Jones, Andrew Persic, Zhenyi Qi, T. Ben Thompson, Sam Zimmerman, Kelley Rivo...

    2025

  3. [3]

    Interpretability in parameter space: Minimizing mechanistic description length with attribution-based parameter decomposition, 2025

    Dan Braun, Lucius Bushnaq, Stefan Heimersheim, Jake Mendel, and Lee Sharkey. Interpretability in parameter space: Minimizing mechanistic description length with attribution-based parameter decomposition, 2025. URL https://arxiv.org/abs/2501.14926

    arXiv 2025

  4. [4]

    Circuits in superposition: Compressing many small neural networks into one

    Lucius Bushnaq and Jake Mendel. Circuits in superposition: Compressing many small neural networks into one. https://www.lesswrong.com/posts/roE7SHjFWEoMcGZKd/circuits-in-superposition-compressing-many-small-neural, 2024. Accessed: 2025-05-09

    work page 2024

  5. [5]

    Sparse autoencoders find highly interpretable features in language models

    Hoagy Cunningham, Aidan Ewart, Logan Riggs, Robert Huben, and Lee Sharkey. Sparse autoencoders find highly interpretable features in language models. arXiv preprint arXiv:2309.08600, 2023

    arXiv 2023

  6. [6]

    Toy models of superposition

    Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-Dodds, Robert Lasenby, Dawn Drain, Carol Chen, et al. Toy models of superposition. arXiv preprint arXiv:2209.10652, 2022

    arXiv 2022

  7. [7]

    Mathematical models of computation in superposition

    Kaarel H \"a nni, Jake Mendel, Dmitry Vaintrob, and Lawrence Chan. Mathematical models of computation in superposition. In ICML 2024 Workshop on Mechanistic Interpretability, 2024. URL https://openreview.net/forum?id=OcVJP8kClR

    work page 2024

  8. [8]

    What’s up with llms representing xors of arbitrary features? https://www.lesswrong.com/posts/hjJXCn9GsskysDceS/what-s-up-with-llms-representing-xors-of-arbitrary-features, 2024

    Sam Marks. What’s up with llms representing xors of arbitrary features? https://www.lesswrong.com/posts/hjJXCn9GsskysDceS/what-s-up-with-llms-representing-xors-of-arbitrary-features, 2024. Accessed: 2025-05-09

    work page 2024

Show all 10 references
  1. [9]

    The linear representation hypothesis and the geometry of large language models

    Kiho Park, Yo Joong Choe, and Victor Veitch. The linear representation hypothesis and the geometry of large language models. In Causal Representation Learning Workshop at NeurIPS 2023, 2023. URL https://openreview.net/forum?id=T0PoOJg8cK

    2023

  2. [10]

    Polysemanticity and capacity in neural networks

    Adam Scherlis, Kshitij Sachan, Adam S Jermyn, Joe Benton, and Buck Shlegeris. Polysemanticity and capacity in neural networks. arXiv preprint arXiv:2210.01892, 2022

    2022 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.