- Rating
- 3(+1)
- Confidence
- 3(−1)
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper separates three notions that are often run together: symbolic complexity, meaning the minimum description cost in a grammar or Kolmogorov complexity; the Fourier frequency-energy profile on the Boolean cube; and "neural affinity", operationalized as epochs to reach an accuracy threshold. On theory, Theorem 1 shows that once n is large enough, all but a 2^-n + 2^(1-2^n) fraction of Boolean functions have a longer Kolmogorov description than parity and a lower mean frequency. Corollary 4.1 carries this over to any "lean" grammar that prices parity polynomially. Theorem 2 shows that a band of fixed mean frequency contains functions whose Kolmogorov complexity runs from logarithmic up to order 2^m. On experiments, the authors enumerate all 65536 four-bit functions under seven grammars and find Spearman correlations between Csym and L1 of only -0.32 to -0.55, with wide spread of cost inside a fixed spectral profile. Paired controls on 4-bit targets embedded in 12 inputs show that T3 shifts training difficulty at fixed Csym, while Csym shows no effect at a fixed full profile. The headline experiment builds datasets that parity and a random table explain equally well. With 6x256 MLPs at n from 8 to 14, the random-table overlap always rises first and parity takes over late, if it takes over at all. A tanh MLP never takes over, and a small Transformer takes over in one of 27 runs. The conclusion is that a network's preferred completion tracks frequency rather than symbolic brevity, with a warning for neural rule extraction.
Critical strengths
The four-bit study is exhaustive, exact, and checked across grammars. All 65536 functions get exact minimum costs under seven grammars. I verified that the G0 layer sizes on p. 18, lines 954 to 955, sum to 65536. The within-profile percentile spans in Table 7 on p. 23 are a nice way to show that a fixed spectral profile admits nearly the full range of symbolic cost. The grammar sweep also makes clear that whether parity counts as simple depends entirely on whether XOR is native: parity4 costs 7 in G0 and 34 in G1, Table 8, p. 23. That is a concrete, reusable point for anyone who calls a rule "simple" without naming the language.
The empirical reporting is transparent to a degree I rarely see. The paper discloses per-run takeover and interpolation epochs in Figure 5 and Table 10, a collapsed run at n = 14 on p. 25, lines 1335 to 1338, the dependence among the 15 runs of a cell on p. 25, lines 1332 to 1334, and the 10 of 27 Transformer runs that never leave chance on p. 29, line 1515. Every parameter count I recomputed is correct. These are 331521 for the n = 8 MLP, 332545 for the n = 12 MLP, 355949 for the Transformer with 174360 per block, a 7.0% gap between the two, and 18305 for the 12 to 128 to 128 to 1 network. Because of this, the experiments can be audited, and I could reason about the confound below from the paper's own description.
Critical weaknesses
First, the competition experiment confirms a known bias rather than separating brevity from frequency in a new way. Training includes all inputs where parity and the random table agree, p. 7, line 365, and p. 24, line 1276. On the disagreement inputs the training labels are split half and half, p. 24, lines 1282 to 1283, so once the labels are fit, those inputs cancel exactly when the two overlaps are compared. At the 100% level, m = 0, so there are no trained disagreement inputs at all. For a network that fits its training labels, the full-domain cosine gap between the two candidates therefore comes entirely from the held-out disagreement inputs, where the random table equals minus parity by construction. Every Hamming neighbor of such an input flips parity, so its neighbors in the agreement set carry the random table's value. In my reconstruction of the design at n from 8 to 12 and all three levels, a Hamming neighbor vote returns the random table's value on 98.9% to 99.9% of held-out inputs, and the completion that follows the random table has an average sensitivity of about 4 to 6, against 7 to 12 for the completion that follows parity. Since mean frequency equals average sensitivity, p. 21, line 1115, preferring the random table here is the same thing as preferring the smoother, low-sensitivity completion.
That makes the outcome a direct instance of the known low-sensitivity bias of networks on the cube and of their failure to extrapolate parity, studied by Abbe et al., ICML 2023, in "Generalization on the Unseen", rather than new evidence. The random table's long description never enters the mechanism. The experiment does show that when brevity and frequency conflict at the extreme that parity represents, frequency wins. It cannot show that brevity is irrelevant when frequency is held fixed, so the general claim on p. 9, lines 453 to 454, that a preferred completion "reflects frequency content, not symbolic brevity" reaches beyond this one pairing. A cleaner design would pit a compact rule against a random table at matched mean frequency, for example chi_S with |S| near n/2. Even taken at face value, the effect shrinks as n grows. Takeover goes from 0 of 15 at every level at n = 8 to 15 of 15 at the 90% and 95% levels at n = 12, and terminal parity overlap reaches 0.96 at n = 14, Table 10, p. 26. Meanwhile Figure 1 is drawn from n = 8, the one dimension where parity never wins under ReLU. The paper discusses late takeover openly on p. 9, lines 456 to 461, but for a ReLU MLP trained to convergence at n of 12 or more the final preferred completion is parity, which sits uneasily with the conclusion on lines 453 to 454.
Second, the "irreducible" theory is a counting argument about one outlier, and the appendix regression does not cleanly support the empirical claim. Order preservation, defined on p. 4, line 211, demands that every higher-frequency function cost at least as much as every lower-frequency one. One cheap function at top frequency is enough to break it, and parity is that function by Lemma A.1. Theorem 1 and Corollary 4.1 then follow because almost all functions are incompressible, p. 5, lines 216 to 218. That is correct but silent on structured functions, the regime that matters for rule discovery. Theorem 2 needs m of at least 16 with m at most min of 2v and 2(n minus v), p. 15, lines 801 to 804, so its admissible range is empty for every n below 16, including every experiment in the paper, even though the statement reads "for every n ≥ 4". On the empirical side, p. 2, line 72, states that difficulty "follows the spectral coordinate, not the symbolic one". The per-function regression on p. 21, lines 1101 to 1103, reports marginal Spearman correlations of 0.74 for Csym and 0.80 for T3, partial correlations of +0.56 for T3 given Csym and +0.38 for Csym given T3, and standardized coefficients of 0.49 for Csym and 0.39 for T3. If the betas and the Spearman correlations are on the same scale, these numbers cannot all hold, because with two standardized predictors the larger marginal correlation always carries the larger coefficient. If the regression uses raw values, the Pearson correlations are needed to check it. Csym also keeps a conditional correlation of +0.38, which sits uneasily with the conclusion on p. 9, line 452, that symbolic cost "shows no detectable effect", even if that sentence refers to the fixed-profile control.
Questions for authors
- Can you split the cosine overlaps into contributions from the agreement set, the trained disagreement inputs, and the held-out disagreement inputs? Can you also report how a simple local interpolator, such as a Hamming neighbor vote or a kernel regressor, scores on the same datasets? If it reproduces the random-first preference, Section 5.3 should present the result as an instance of the known low-sensitivity bias, since the random table's complexity plays no role in it.
- Have you run a competition between a compact rule and a random table at matched mean frequency, such as a degree n/2 character versus a random table? This is the only design I see that isolates symbolic brevity from frequency.
- On p. 21, T3 has the larger marginal correlation but Csym has the larger standardized coefficient. Were the betas computed on ranks or on raw values, and how do you reconcile a conditional Csym correlation of +0.38 with the main-text claim that difficulty follows the spectral and not the symbolic coordinate? Is the fixed-profile null a power issue, given that only 18 profiles and Csym gaps of at least 3 are used?
- The n = 8 and n = 10 random tables are "the three highest-overlap tables of an earlier frozen batch", p. 24, lines 1249 to 1250. How was that batch drawn, and do the n = 8 results hold for unselected tables?
- Why does takeover become more frequent as n grows? Does it reflect the ratio of capacity to domain size, or the growing absolute number of held-out disagreement inputs? This determines whether the mismatch matters at realistic scale or fades.
13 comments
Response to pLvz (2/6): Local interpolation and matched-frequency competition
Q1(b). Hamming Neighbor Vote and Low-Sensitivity Bias
Can you also report how a simple local interpolator, such as a Hamming neighbor vote or a kernel regressor, scores on the same datasets?
We evaluated a Hamming one-hop neighbor vote on the same datasets, retaining training labels on observed inputs and using neighbor votes elsewhere.
Table 2. Hamming one-hop vote on held-out disagreement inputs. In the first two rows, input counts are summed across the three datasets and cosine overlaps are averaged across them; the last row reports the total count and ranges across all 12 cells.
| Cell | Held-out disagreement inputs | Vote matches random table | Completion cos with parity | Completion cos with random table |
|---|---|---|---|---|
| n=8, 100% (Figure 1) | 357 | 100.00% | 0.07 | 1 |
| n=12, 95% (Figure 4) | 5,416 | 99.94% | 0.06 | 0.94 |
| All 12 cells (36 datasets) | 85,494 | 98.44–100.00% | 0.00 to +0.21 | +0.86 to +1.00 |
These results are consistent with the reviewer's low-sensitivity explanation. On the Boolean cube, average sensitivity equals mean Fourier degree, so a preference for low sensitivity is also a preference for low mean Fourier degree.
Q2. Matched-Frequency Rule Competition
Have you run a competition between a compact rule and a random table at matched mean frequency, such as a degree n/2 character versus a random table? This is the only design I see that isolates symbolic brevity from frequency.
We conducted the suggested matched-frequency rule competition. Before presenting its results, we first clarify the distinct roles of the fixed-profile controls and the rule competition.
Our existing fixed-profile control experiments have examined how symbolic complexity (Csym) affects learning difficulty while holding the entire frequency-energy profile constant, a stricter control than matching mean frequency alone. We believe these experiments address the reviewer's central concern about isolating symbolic complexity from frequency.
The rule competition serves a different purpose: to illustrate a possible consequence of this mismatch in an extreme setting, where a symbolically simple, high-frequency rule competes with a symbolically complex, lower-frequency rule. A single matched-frequency competition would compare only one selected pair of rules, potentially limiting the generality of its findings. In contrast, our fixed-profile experiments compare learning difficulty across multiple frequency profiles and multiple pairs of symbolically simple and complex rules. And to further address the reviewer's concern about statistical power, we have expanded these experiments during the rebuttal period; the expanded design and results are reported in our response to Q3(c).
For the suggested matched-frequency rule competition, at n=12, we compared a degree-6 character with 10 independently drawn random tables whose mean frequencies were within 0.10 of 6, using three initialization seeds per table and the original 95% agreement protocol. All 30 runs favored the random table throughout epochs 2–20, and all eventually switched to the character and stayed ahead through epoch 5,000. Across these successful takeovers, the median interpolation time was 66.5 epochs, the median additional time to takeover was 1,215 epochs, and the median delay ratio was 18.16× (the same order of magnitude as the 8.3–32.9× ratios in our Q5 table). We computed the ratio for each run by dividing its post-interpolation delay by its interpolation time.
Although the character and random tables are closely matched in mean frequency, their full frequency-energy profiles still differ. This result, therefore, does not isolate symbolic brevity from frequency. It is consistent with our fixed-profile findings and shows why the full frequency-energy profile matters when comparing neural affinity.
Response to pLvz (3/6): Late parity takeover and neural affinity
On Late Parity Takeover and Neural Affinity (W1, Q5)
Q5. Dimension-Dependent Takeover
Why does takeover become more frequent as n grows? Does it reflect the ratio of capacity to domain size, or the growing absolute number of held-out disagreement inputs? This determines whether the mismatch matters at realistic scale or fades.
Response to Q5: Dimension-dependent takeover.
To investigate the dimensional trend, we conducted two complementary experiments: (A) controlling the capacity-to-domain ratio and (B) controlling the number of held-out disagreement inputs used for evaluation.
(A) Capacity-to-domain ratio. We ran 180 additional ReLU MLP experiments with fresh, unselected random tables, varying network width to match (P/2^n) across dimensions. Matching this ratio does not eliminate the dimensional trend, and increasing it fourfold at fixed (n) does not suppress takeover. Thus, relative parameter count alone cannot explain the trend.
(B) Held-out disagreement count. We re-evaluated terminal preference using 64 randomly sampled held-out disagreement inputs, with 200 repeated, reweighted evaluations per run. The dimensional trend persists: parity is preferred in 33–42% of evaluations at (n=10), compared with 96.5–100% at (n=12,14). Hence, the increase in held-out evaluation-set size does not explain the trend.
The table reports the 95% accuracy setting (three random tables × five initializations per configuration):
| (n) | Width | (P/2^n) | Takeover | Interpolation epoch | Additional epochs to takeover | Median delay ratio | Parity preferred (64 samples) |
|---|---|---|---|---|---|---|---|
| 10 | 64 | 21.06 | 4/15 | 146 | 1,386 | 8.3× | 33.00% |
| 12 | 128 | 20.59 | 15/15 | 232 | 3,601 | 12.1× | 99.80% |
| 14 | 256 | 20.33 | 15/15 | 207 | 3,850 | 17.9× | 100% |
| 10 | 128 | 82.13 | 7/15 | 84 | 2,632 | 32.9× | 41.50% |
| 12 | 256 | 81.19 | 15/15 | 107 | 1,866 | 14.8× | 100% |
| 14 | 512 | 80.66 | 14/15 | 117 | 3,369 | 26.8× | 96.50% |
Interpolation and delay medians are computed over runs with successful takeover. The delay ratio is calculated per run as the post-interpolation delay divided by interpolation time. The 100% accuracy setting shows the same qualitative trends.
Implications. While these controls do not fully identify the cause of dimension-dependent takeover, they establish that the mismatch remains consequential. All 180 runs favor the random candidate first and eventually interpolate the training labels. Even when parity takes over, the additional training required is roughly 8.3–32.9 times the time needed for interpolation. Thus, a network may fit its training data quickly yet require far more optimization to favor the compact symbolic rule. Eventual takeover does not mean the mismatch has disappeared.
Regarding W1 (p. 9, lines 453–454). We have revised the concluding sentence in Section 6 to make the statement more precise. Our conclusion concerns the network's initial learning preference, not its terminal preference. More importantly, eventual parity takeover does not eliminate the mismatch: fitting the training labels and recovering the compact symbolic rule can operate on dramatically different timescales, with the latter requiring 8.3–32.9 times the interpolation time in additional training in our successful-takeover runs.
Response to pLvz (1/6): Novelty and overlap decomposition
Thank you for recognizing the exact, exhaustive analysis across symbolic grammars and the transparency of our empirical reporting. Your main concerns relate to novelty beyond known spectral bias, the design and interpretation of the competition experiments, the scope of the theory, the regression and fixed-profile controls, and robustness to random-table selection. We address these points below with additional controls, expanded experiments, and clarifications, including the distinction between early learning preferences and late parity takeover.
On the Novelty Beyond Known Spectral Bias (W1)
We agree that the random-first preference is consistent with the known low-sensitivity bias. Our contribution is not to discover a new learning bias, but to examine how this known bias relates to symbolic simplicity—a different notion of complexity that matters for human-understandable rule discovery.
Our theoretical results establish ordering reversals between symbolic complexity and spectral structure, as well as large differences in symbolic cost at fixed mean frequency. Our matched controls further examine learning difficulty while holding the full frequency-energy profile fixed. Finally, the competition experiment shows a practical consequence of this mismatch: even after fitting the training data, a network may continue to favor a more complex rule over a shorter one.
We address the competition mechanism, spectral controls, and delayed parity takeover in Q1(b), Q2, and Q5, respectively.
On the Competition Design and Controls (W1, Q1–Q2)
Q1(a). Decomposition of Cosine Overlaps
We decompose the terminal (epoch 5,000) cosine overlaps with parity (P) and the random table (R) into contributions from three subsets: the agreement set (A), trained disagreement inputs (T), and held-out disagreement inputs (H).
Using the same full-domain normalization, the contributions to parity overlap satisfy
cos(f, P) = contribution from A + contribution from T + contribution from H
for each run. For the random-table overlap, the agreement contribution is unchanged, while the disagreement contributions have opposite signs.
Table 1. Contributions to terminal cosine overlaps (epoch 5,000). Entries are medians over 15 runs per cell. P / R indicates the contributions to parity and random-table overlaps, respectively.
The terminal preference is primarily determined by predictions on held-out disagreement inputs. Their contribution favors the random table at (n=8), is near zero at (n=10), and consistently favors parity at (n=12) and (n=14).