acceptodds
Under review as a conference paper at ICLR 2027

The Mismatch between Neural Affinity and Symbolic Simplicity

Abstract

A large body of work on simplicity bias shows that neural networks favor simple functions. Because the target functions in many real problems are expected to be highly structured, this preference is believed to aid generalization. But does this simplicity bias still hold in the space of symbolic rules? In other words, is the "simplicity" that networks prefer the "simplicity" that humans find easy to understand? We prove a mismatch between the two and establish that it is irreducible: almost every Boolean function has a longer description than parity yet sits at a lower frequency, and even at matched frequency, description lengths range from logarithmic to exponential. Experiments confirm the mismatch: what is cheap to describe is not what is cheap to learn. Even when a compact parity rule and a randomly drawn function fit the training labels equally well, MLPs learn the random function first, and so does a Transformer. These findings challenge the expectation that symbolically simple targets benefit from neural simplicity bias: short symbolic rules can instead face a learning disadvantage.

Primary area:
learning theory
Keywords:
inductive bias, spectral bias, Fourier analysis, symbolic complexity, deep learning theory

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_pLvzOpenReview ↗
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
  1. 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.
  2. 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.
  3. 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?
  4. 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?
  5. 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
AuthorsOpenReview ↗

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

Can you split the cosine overlaps into contributions from the agreement set, the trained disagreement inputs, and the held-out disagreement inputs?

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.

nLevelAgreement (both)Trained disagreement (P / R)Held-out disagreement (P / R)
890%0.550.00 / 0.00−0.17 / +0.17
895%0.560.00 / 0.00−0.22 / +0.22
8100%0.57—−0.23 / +0.23
1090%0.560.00 / 0.00+0.02 / −0.02
1095%0.570.00 / 0.00−0.03 / +0.03
10100%0.58—−0.05 / +0.05
1290%0.530.00 / 0.00+0.15 / −0.15
1295%0.530.00 / 0.00+0.23 / −0.23
12100%0.55—+0.34 / −0.34
1490%0.51+0.04 / −0.04+0.28 / −0.28
1495%0.51+0.01 / −0.01+0.36 / −0.36
14100%0.51—+0.45 / −0.45

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).

AuthorsOpenReview ↗

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.

CellHeld-out disagreement inputsVote matches random tableCompletion cos with parityCompletion cos with random table
n=8, 100% (Figure 1)357100.00%0.071
n=12, 95% (Figure 4)5,41699.94%0.060.94
All 12 cells (36 datasets)85,49498.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.

AuthorsOpenReview ↗

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)TakeoverInterpolation epochAdditional epochs to takeoverMedian delay ratioParity preferred (64 samples)
106421.064/151461,3868.3×33.00%
1212820.5915/152323,60112.1×99.80%
1425620.3315/152073,85017.9×100%
1012882.137/15842,63232.9×41.50%
1225681.1915/151071,86614.8×100%
1451280.6614/151173,36926.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.

Reviewer_LKqVOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors study a mismatch between "symbolic simplicity" and "neural affinity": tasks that are easy to describe for humans may not likewise be easy for neural networks to learn. They show theoretically and empirically that for tasks with short symbolic descriptions but spectral power distributed primarily in high frequencies (notably parity), a neural network will struggle to learn. On the other hand, for tasks with low frequency spectral power, neural networks learn readily but symbolic description length may vary widely.

Critical strengths

The authors study a fascinating topic. The "simplicity bias" of neural networks is frequently conflated with a simple symbolic description of the task, and the authors conduct a fascinating and rigorous investigation of this topic. The authors appear to have substantial empirical evidence to back up their theoretical assertions. The manuscript overall appears to be a valuable contribution that would be of general interest at this conference.

Critical weaknesses

The writing is somewhat terse and dense, and could benefit from a reorganization where intuitive results and informal theorem statements are presented in the main text, while detailed theoretical results are deferred to the appendix. The subject is topically very abstract and does not relate immediately to practical considerations for neural network training. The authors do not attempt to connect their intuitions to naturalistic settings, and could benefit from a more extended discussion or preliminary results performing an analogous spectral analysis of naturalistic tasks and identifying potential correlations (or lack of correlations) with description length.

Questions for authors
  1. Is there a naturalistic setting in which you can compare a spectral decomposition of the task and its description length?
  2. Is it possible to measure the spectral properties of a natural language task? Would the analog of description length simply be the number of natural language tokens required to pose a task? Can you think of settings in natural language with short description length, but high spectral complexity?
3 comments
AuthorsOpenReview ↗

Response to LKqV: Naturalistic settings and description length

Thank you for recognizing the value of distinguishing symbolic simplicity from neural learning preferences, the rigor of our investigation, and the empirical support for our theoretical results. Your main concerns relate to the connection to naturalistic tasks. Below, we discuss concrete examples in scientific symbolic regression and natural language, including how spectral structure and description length could be measured in these settings.

Q1: Is there a naturalistic setting in which you can compare a spectral decomposition of the task and its description length?

Yes—a natural setting is scientific symbolic regression, where the task is to recover a physical law from observations. For example, the equations in the AI Feynman benchmark provide explicit target functions whose spectral content can be compared with the lengths of their symbolic expressions. One could estimate each function’s spectrum over a specified input domain and measure expression length using a fixed symbolic language and parameter precision. Oscillatory laws offer an intuitive example: a function such as f(t) = A sin(ωt + φ) retains a compact symbolic expression even at high frequencies. This provides a concrete setting for investigating how spectral structure and symbolic complexity separately relate to neural learning difficulty.

Q2: Is it possible to measure the spectral properties of a natural language task? Would the analog of description length simply be the number of natural language tokens required to pose a task? Can you think of settings in natural language with short description length, but high spectral complexity?

Yes. One approach is to connect texts through small, meaningful edits and examine how a rule’s labels change. For an entailment rule, changing who did what to whom can change the label. With the input distribution and editing rules fixed, we can decompose the labels into slowly and rapidly varying patterns, much like our Boolean Fourier profile. Hahn et al. (2021) provide a starting point by estimating sensitivity on natural-language tasks and relating it to model performance.

Token count can be used if we fix the language, tokenizer, and what the reader is assumed to know. We would count the tokens in the shortest description that fully specifies the input–output rule, matching our use of a fixed description language to measure symbolic complexity.

For the third question, we could compare an entailment rule with a sentiment-based rule that has a longer description. Hahn et al. find higher sensitivity for entailment than for sentiment classification, making this a useful comparison to explore. As in our rule-competition experiments, the rules could agree on observed examples but disagree on unseen inputs. We could then ask whether the network prefers the rule with the shorter description.

Reference: Michael Hahn, Dan Jurafsky, and Richard Futrell. 2021. Sensitivity as a Complexity Measure for Sequence Classification Tasks. Transactions of the Association for Computational Linguistics, 9:891–908.

Thanks for answering my questions. I retain my positive assessment. Well done, and good luck!

Thank you for your encouraging feedback and for taking the time to review our work. We sincerely appreciate your thoughtful comments and positive assessment.

Reviewer_Q5S1OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper examines whether the “simplicity” preferred by DNNs aligns with the “simplicity” that humans find easy to understand. The authors theoretically establish an irreducible mismatch between symbolic complexity and spectral structure, demonstrating ordering reversals and complexity dispersion within frequency bands. They empirically investigate this mismatch through exhaustive four-bit enumeration under seven grammars, matched training controls, and competition between compact rules and random tables that explain the training labels equally well.

Critical strengths
  1. The paper systematically analyzes all four-bit Boolean functions under seven symbolic grammars, providing a detailed comparison between symbolic and spectral simplicity.

  2. The paper includes useful controlled comparisons: fixing symbolic cost while varying spectral structure, and fixing the frequency-energy profile while varying symbolic cost. These experiments help clarify how the two factors relate to learning speed.

Critical weaknesses
  1. The main conclusion is largely consistent with existing knowledge of spectral bias and the difficulty of learning parity. Although the paper provides systematic quantification and controlled experiments, it remains unclear what important new understanding these results add.

  2. The scope of the matched training experiments is limited, as the target functions depend on only four input variables. It remains unclear whether the findings generalize to more complex rules. Extending these comparisons to function families with more relevant variables and controlled symbolic costs would strengthen the generality of the conclusions.

Questions for authors
  1. What important new insights do the theoretical results and controlled experiments provide beyond existing work on spectral bias and parity learning? Which findings go beyond what prior work would lead us to expect?

  2. The core matched experiments primarily use target functions that depend on only four input variables. Do the findings extend to more complex rules involving more relevant variables? Could the authors provide evidence from broader function families with controlled symbolic costs?

  3. What concrete implications do these findings have for DNN learning in real-world settings? For example, when a task’s target rule has a short description, can these results help us assess whether a network will learn it easily and what additional factors need to be considered?

5 comments
AuthorsOpenReview ↗

Response to Q5S1 (1/3): Novelty and contributions

Thank you for recognizing the systematic analysis across seven symbolic grammars and the value of our controlled comparisons. Your main concerns relate to the contribution beyond existing spectral-bias and parity-learning results, the generality of the four-variable experiments, and the practical implications for learning short rules. We address these points below, including new experiments with 6, 8, and 10 relevant variables.

Q1: What important new insights do the theoretical results and controlled experiments provide beyond existing work on spectral bias and parity learning? Which findings go beyond what prior work would lead us to expect?

A1: Spectral bias has been well studied indeed. However, whether and how the simplicity favored by DNNs matches the simplicity for human understanding is not clear. Rahaman et al. (2019) associate spectral bias with networks that “prioritize learning simple patterns,” while Cao et al. (2021) describe it as being “biased towards learning less complex functions.” Existing work did not clearly distinguish such different types of simplicity, and may lead to an (incorrect) impression that a function that is symbolically simpler for humans to understand is also easier for DNNs to learn. We investigate this potential misunderstanding and explicitly demonstrate the mismatch between spectral and symbolic simplicity.

Since a preference for low-complexity functions is invoked to explain generalization, recognizing that spectral bias does not imply an affinity for shorter symbolic rules is essential to understanding how networks generalize across rule families.

Beyond establishing this mismatch, Theorem 2 quantifies the range of symbolic complexity within a narrow mean-frequency band, from logarithmic to exponential at admissible scales. Our theoretical contribution therefore does not rely solely on parity as a single special case. The competition experiments likewise include additional compact rules built from subset parity, majority, and modular counting (Figure 6).

Crucially, our fixed-profile training controls hold the complete frequency-energy profile constant and directly test whether shorter symbolic rules enjoy a learning advantage. By controlling for spectral bias, this experiment finds no detectable preference for shorter symbolic rules in either ReLU or tanh networks (Table 2). Instead, it suggests that improving DNN learning of compact symbolic rules may require introducing additional inductive biases through other mechanisms.

AuthorsOpenReview ↗

Response to Q5S1 (2/3): Extended controlled experiments

Q2: The core matched experiments primarily use target functions that depend on only four input variables. Do the findings extend to more complex rules involving more relevant variables? Could the authors provide evidence from broader function families with controlled symbolic costs?

We extended both controlled experiments to rules depending on 6, 8, and 10 relevant variables, with more varied rule structures and certified symbolic costs. All rules use the same 12-variable input space, with three initialization seeds per target. We report D95, the first epoch reaching 95% full-domain accuracy, to reduce the censoring encountered at the 99% threshold. All reported runs reached 95% within 2,000 epochs.

  1. Different frequency profiles at the same symbolic cost.

Experiment A includes AND–XOR, OR–XOR, and mixed AND–OR–XOR rules, using balanced, chain-like, and randomly generated expression trees. Each relevant variable appears exactly once, giving an exact minimum symbolic cost of 2k − 1 while allowing different logical structures and frequency-energy profiles.

For each k, we compared 16 pairs with identical symbolic cost but different high-frequency energy (T3, the total energy at Fourier degrees 3 and above). Here, ΔD95 denotes the learning-time difference between higher-tail and lower-tail rules, measured in epochs.

Relevant variables (k)Exact (Csym)PairsMean ΔD9595% bootstrap CI
611165.5[−0.56, +11.69]
8151622.38[+5.38, +39.25]
10191678.63[+42.94, +119.63]

Higher-tail rules took longer to learn on average across all three values of (k).

  1. Different symbolic costs at the same full frequency-energy profile.

Experiment B extends matched four-variable rules to k variables by XORing each rule with the same rule h over the remaining k − 4 variables. Each pair retains an identical full frequency-energy profile, with a proven symbolic cost difference: 2k − 1 for the simpler rule versus at least 2k + 1 for the more complex rule.

We expanded this control to 312 pairs, with four pairs per profile. Here, ΔD95 is higher-complexity minus lower-complexity learning time, in epochs.

Relevant variables (k)ProfilesPairsMean ΔD9595% profile-bootstrap CI
6624−2.43[−7.08, +1.82]
824963.08[+0.41, +5.96]
10481922.99[−0.28, +6.71]

Overall, these expanded fixed-profile experiments do not show a clear, consistent learning advantage for symbolically simpler rules. The observed mean differences are also much smaller in magnitude than the frequency-related differences in Experiment A.

AuthorsOpenReview ↗

Response to Q5S1 (3/3): Practical implications

Q3: What concrete implications do these findings have for DNN learning in real-world settings? For example, when a task’s target rule has a short description, can these results help us assess whether a network will learn it easily and what additional factors need to be considered?

When scientists try to infer a rule from a small set of measurements, the ground truth is often unknown, and several explanations may fit the available data equally well. Among these explanations, we would usually prefer a short, structured rule that is easy to interpret over a complicated, lookup-table-like rule. Our results show, however, that symbolic simplicity does not necessarily match a network’s learning preferences.

This suggests a practical consideration for model design: we should consider how the target rule’s Csym, under the chosen input representation, relates to the model’s bias, including its spectral bias. A rule that is short to describe may still be difficult for the network to learn. Exploring representations, architectures, optimization methods, or curricula that bring these preferences closer together is a promising direction for helping networks learn short rules more easily.

Our new competing-rule experiments also highlight the role of training time. Interpolation—fitting all observed training examples—is a milestone we can identify without knowing the ground truth. But reaching it does not mean that the network already favors the shorter rule. Among runs in which the shorter rule eventually took over, the median additional waiting time was approximately 8–33 times the number of epochs needed to reach interpolation. This quantifies a substantial gap between fitting the observations and developing a preference for the shorter rule. Within a limited training budget, that preference may never emerge. Evaluation should therefore distinguish between fitting the observed data and favoring the shorter rule on unseen inputs.

Thus, beyond description length, the additional factors to consider are alignment between the input representation and the model’s bias, how well the data cover the rule’s behavior, and the training budget and stopping point.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions to the Manuscript

We sincerely thank all reviewers for their time and constructive feedback. Following their valuable comments and suggestions, we have carefully revised our paper. All revisions are highlighted in blue. The major updates in the revised manuscript are as follows:

  • Section 6 (Conclusion): Revised the concluding sentence to make it more explicit and precise.
  • Appendix D: Corrected the regression to its rank-based specification, consistent with the rank-based correlations reported in the same paragraph.
  • Appendix D: Clarified the separation between the scalar-control correlation and the fixed-profile matched comparison.
  • Appendix G: Added per-grammar ordering-reversal statistics beyond the parity special case, with denominators and thresholds.
  • Appendix D: Added scale-extension experiments to 6, 8, and 10 relevant variables, at fixed symbolic cost and at fixed full profile, with certified costs and profile-bootstrap intervals.
  • Section 6 and Appendix H: Reported interpolation-to-takeover delay statistics and discussed the timescale gap between fitting training labels and favoring the compact rule.
  • Appendix H.1: Documented the random-table selection procedure and verified robustness on unselected tables.
  • Section 6 (Implications): Stated the practical factors beyond description length: representation–bias alignment, data coverage, and training budget with stopping point.
  • Section 6 and Appendix J: Added concrete settings beyond the Boolean cube, covering scientific symbolic regression and natural-language rules, with a new reference.
  • Section 1 (contributions): Refined the phrasing of the third contribution.
  • Appendix D: Added pooled and macro estimates over all 312 matched pairs.
  • Appendix H: Added training-data interventions and mechanistic diagnostics on late takeover.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.