{"id":"7815b83f-56cb-4b82-9ab9-bac44b8038fb","arxiv_id":"2505.24060","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Randomly initialized depth-2 discrete networks are a priori biased toward Boolean functions with small disjunctive normal form complexity, and this bias quantitatively predicts training and generalization behavior including weight-decay effects.","lead":"Depth-2 discrete neural networks on Boolean inputs are shown to be equivalent to logical formulas in disjunctive normal form, making the network's inductive bias analytically tractable. The paper derives how this built-in simplicity bias shapes learning, feature formation, and generalization, including why weight decay helps simple targets but not complex ones like parity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (7)'s minimal-norm approximation is not merely unquantified: redundant safe clauses make the posterior sum over θ for f=x1 dominated by high-norm states, so the claimed e^{-λK(f)} factor is exponentially wrong for large n.","rationale":"Good-faith reading: the paper's central contribution is an end-to-end tractable account of inductive bias, and Eq. (7) is the analytical bridge that turns weight decay into a function-space prior. The bijection in Proposition 2.7 and the P(f) bounds in Table 2 appear sound, and the experiments are suggestive. The problem is that Eq. (7)'s saddle-point assumption is not a loose asymptotic that improves with n; it is structurally inverted by the exponential number of redundant safe-clause representations. The generating-function calculation for 1-parity is exact and shows that the minimal-norm term has measure zero under the conditional prior. This invalidates the claimed exp(-λK) factor, and it also means the MCMC algorithm's observed convergence to minimal DNFs is a non-equilibrium property rather than a property of the posterior that Eq. (7) describes. The paper should either drop the quantitative posterior claim or redo the marginalization exactly, which is tractable per function via the row generating function, and state the corrected effective complexity. Because the qualitative empirical findings may survive such a correction, a conditional verdict is appropriate rather than outright rejection; however, the current form of Eq. (7) cannot be accepted as a derivation.","tokens_in":34464,"tokens_out":28293,"duration_ms":302811,"concrete_test":"Compute the exact weight-decay factor R_f(λ) = Σ_{θ:fθ=f} e^{-λ||θ||1} / |{θ:fθ=f}| for n=3, αw=1 by exhaustive enumeration of all 2·3^12 ≈ 10^6 DFCN parameter vectors, for f=x1 and f=x1⊕x2, and compare R_f(0.01) with e^{-0.01 K(f)}. Then evaluate the same ratios for n=7, αw=2 using the closed-form row generating function (this is exact, no sampling): R_{x1} ≈ [(1+e^{-λ}(1+2e^{-λ})^{n-1})/(1+3^{n-1})]^M and R_{x1⊕x2} ≈ [(1+2e^{-3λ})/3]^M. If R_{x1} is smaller than R_{x1⊕x2} while K(x1)<K(x1⊕x2), or if either ratio differs from e^{-λK(f)} by more than a factor of 2, Eq. (7)'s factorization fails as stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central quantitative claim is Eq. (7), which writes the weight-decay posterior over functions as Pλ(f|S) ≈ e^{-λK(f)}P(f|S) up to normalization. This requires the sum over parameter configurations implementing f to be dominated by the minimal-norm configuration. That assumption is violated by the DFCN prior because of redundant 'safe' clauses. For β=1, any clause whose satisfying assignments are contained in f^{-1}(1) can be added to a representation of f without changing f. For f=x1 (1-parity), every clause containing the literal x1 is safe: there are S=3^{n-1} such clauses per row. Conditional on θ implementing f, each row is non-zero with probability S/(S+1), so the typical norm is ≈M·(1+2(n-1)/3+1), which is O(n2^{n-1}), not K(f)=1. The exact conditional average of e^{-λ||θ||1} is [(1+e^{-λ}(1+2e^{-λ})^{n-1})/(1+3^{n-1})]^M, up to the requirement of at least one pure clause, which is negligible for large M. For n=7, αw=2, λ=0.01 this is ≈0.002, while e^{-λK(f)}=0.99. For f=2-parity, only two safe clauses exist, so the same ratio is ≈0.077. Thus the exact weight-decay factor is neither exp(-λK(f)) nor monotone in K(f): it suppresses the K=1 function about 50 times more than the K=4 function. The paper's statement that the approximation 'gets more accurate for larger n' is backwards; the entropy of safe clauses grows exponentially with n. Consequently Eq. (7) does not follow, and the claimed quantification of weight decay as a sharpened simplicity prior is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies depth-2 discrete fully connected networks (DFCNs) on Boolean functions, proving a bijection between DFCNs and DNF formulas. It introduces a prior P(f) over functions induced by random DFCN parameters, derives scaling laws for P(f) for constant, t-entropy, and k-parity functions, and runs experiments with MCMC and a greedy SGD-like algorithm showing that generalization correlates with P(f). The central quantitative claim is Eq. (7): weight decay multiplies the posterior by approximately e^{-λK(f)}, where K(f) is the DNF complexity.","tokens_in":34827,"tokens_out":16732,"duration_ms":147181,"significance":"If correct, the paper would provide a rare end-to-end analytically tractable account linking architecture, prior, training dynamics, and generalization. The bijection proof (Proposition 2.7) and the explicit scaling laws in Table 2 are careful and constitute a useful contribution, and the comparison between the MCMC sampler and the min-norm oracle provides independent empirical grounding. However, the central weight-decay formula, Eq. (7), is quantitatively wrong: the Laplace-style approximation is violated by the exponential number of redundant safe clauses, and the exact factor is neither e^{-λK(f)} nor monotone in K(f) in the paper's own experimental setting. This undermines contribution 4 as stated and requires revision.","major_comments":[{"comment":"The approximation that the norm-penalized sum over parameter configurations implementing f is dominated by the minimal-norm configuration is violated by the exponential number of redundant 'safe' clauses. For f = x1 with β = 1, every clause containing the literal x1 is safe, so there are 3^{n-1} safe active clauses per row. Conditioning on θ implementing x1, each row is active with probability 3^{n-1}/(1+3^{n-1}), and the conditional expectation of e^{-λ||θ||_1} is exactly [(1+e^{-λ}(1+2e^{-λ})^{n-1})/(1+3^{n-1})]^M (up to a negligible correction for requiring at least one active clause). For the paper's experimental setting (n=7, αw=2, M=128, λ=0.01), this equals about 0.0017, whereas e^{-λK(f)} = e^{-0.01} = 0.99. The error is not a small finite-size effect: the number of safe clauses grows as 3^{n-1}, so the approximation becomes exponentially worse with n, contrary to the claim in Section 4.2 that it 'gets more accurate for larger n'.","section":"Section 4.2, Eq. (7)"},{"comment":"The exact weight-decay factor is not monotone in K(f), which is necessary for the paper's explanation of the weight-decay experiments. For the t=1 function (a single input mapped to 1), K(f)=n, and the exact factor is [(1+e^{-nλ})/2]^M; for n=7, λ=0.01, this is about 0.0066. This is larger than the exact factor for f=x1 (K=1), which is about 0.0017, so weight decay suppresses the K=1 function more strongly than the K=7 function, reversing the simplicity ordering that e^{-λK(f)} would predict. The claim that weight decay 'sharpens the native simplicity bias' via a factor e^{-λK(f)} is therefore unsupported, and the interpretation of Figure 4 in Section 4.3 needs to be revisited.","section":"Section 4.2, Eq. (7) and Section 4.3"}],"minor_comments":[{"comment":"In the case t > 2^{n-1}, the text says 'we instead use a network with layer sizes ⟨n, 2^{n-1} − t, 1⟩', but for t > 2^{n-1} this dimension is negative; it should be 2^n − t, the number of false inputs. The constant-true function t = 2^n is not covered by the construction and should be handled separately.","section":"Appendix B.7, proof of Proposition 2.7"},{"comment":"The parameter-space size is written as |{θ}| = 2 · 3^{n 2^{n-1}}, which assumes the width multiplier αw = 1, but Definition 2.6 and the experiments use width αw 2^{n-1} with αw = 2. The formula should include αw in the exponent.","section":"Definition 3.1"},{"comment":"The validity condition 'αw ≫ (3/4)^n' is confusing because (3/4)^n < 1 for n ≥ 1, so αw ≥ 1 already satisfies it; presumably the intended condition is about αw times powers of (3/4), and the caption should be clarified.","section":"Table 2 caption"},{"comment":"The sentence '∥θ∥1 ≃ ∥W(1)∥1, which gets more accurate for larger n since the parameter space is largely dominated by W(1)' is true but does not address the main failure of Eq. (7); the dominant contribution to the norm-sum comes from the entropy of W(1) configurations, not from the comparison of W(1) and W(2).","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper's bijection and the scaling-law analysis are solid and could be published after the weight-decay claim is corrected or substantially weakened. The authors should replace Eq. (7) with the exact conditional expectation or clearly state the restricted regime in which the approximation holds, and they should revisit the interpretation of the weight-decay experiments in light of the non-monotonicity demonstrated by the t=1 versus x1 comparison. I would not reject the paper on this basis, but the current text overclaims the quantitative content of the weight-decay result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the DFCN–DNF bijection and the Table 2 scaling laws are solid, careful work. Second, Eq. (7) — the claim that ℓ1 weight decay just multiplies the posterior by e^{-λK(f)} — is not supported, and the stress-test note has a real point, even though one of its supporting calculations is wrong.\n\nWhat is actually good: the bijection (Prop. 2.7) is proved cleanly in the appendix, and the bounds on P(f) for constants, t-entropy, and k-parity are concrete, checkable results. The empirical study on n=7 is well designed; the min-norm oracle is especially valuable because it separates inability-to-find from prior-implausibility. The paper also honestly flags that the asymptotic regime is not tested and that continuous networks are out of reach.\n\nThe soft spot is Eq. (7). The paper assumes the weighted sum over θ implementing f is dominated by the minimal-norm θ and that total norm ≈ first-layer norm. The stress-test note computes, for f=x1, the actual average of e^{-λ||θ||} over implementing θ and finds it ≈0.002 for n=7, α_w=2, λ=0.01, while e^{-λK}=0.99. That arithmetic checks out. The note's additional claim that 2-parity has only two safe clauses is wrong — there are 2·3^{n-2} — but the core objection survives: the prior assigns enormous volume to high-norm redundant representations, so the sum is not minimal-norm dominated, and the paper's assertion that the approximation 'gets more accurate for larger n' runs backwards because safe-clause entropy grows exponentially. This is a load-bearing flaw for the paper's quantitative interpretation of weight decay. The empirical results can still stand — the MCMC sampler actively seeks low norms, so it finds sparse features — but the Bayesian-posterior story in Eq. (7) does not follow as written.\n\nWho this is for: people working on simplicity bias and analyzable toy models of deep learning. It deserves a serious referee: the scaling laws and the oracle experiments are worth publishing, provided Eq. (7) is rederived with a proper saddle-point that includes entropy, or weakened to a qualitative claim. I would not cite Eq. (7) itself, but I would cite the bijection and P(f) bounds.","headline":"Clean toy model with real scaling-law content, but the weight-decay posterior factorization (Eq. 7) fails because redundant safe clauses dominate the norm-weighted sum.","tokens_in":35429,"tokens_out":14290,"would_cite":true,"duration_ms":119273,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68Q32","06E30"],"pacs":[],"model":"deepseek-v4-flash","headline":"A depth-2 Boolean network's inductive bias is a simplicity prior over logic formulas, sharpened by weight decay.","keywords":["inductive bias","Boolean functions","DNF complexity","simplicity bias","weight decay","feature learning","Bayesian posterior","discrete neural networks"],"falsifier":"For n=4 or n=5, enumerate every DFCN parameter configuration and compute the exact posterior under a uniform prior, an 01-likelihood, and ℓ1 weight decay; if the ratio P_λ(f|S) / [$e^{{-λK(f)}}$ P(f|S)] is not approximately constant in λ and f, the minimal-norm-dominance assumption underlying Eq. (7) fails.","tokens_in":1826,"feed_emoji":"🧠","tokens_out":2577,"duration_ms":91948,"temperature":0.7,"pith_summary":"The paper tries to establish an end-to-end, analytically tractable account of inductive bias, feature learning, and generalization for a depth-2 discrete fully-connected network on Boolean data. It proves a one-to-one correspondence between such networks and disjunctive normal form (DNF) formulas, so that the first-layer weight norm literally counts the literals in a logic formula and the minimal-norm network for a function is its minimal DNF. From this it derives the prior probability P(f) over Boolean functions and shows that P(f) is strongly biased toward low-DNF-complexity functions, with explicit scaling laws for constant, t-entropy, and k-parity families. Training experiments show that generalization tracks P(f), that weight decay acts as an approximate multiplicative factor $e^{{-λK(f)}}$ in the posterior, and that this sharpened prior drives the emergence of minimal, interpretable representations. A sympathetic reader should care because this makes the vague notion of simplicity bias precise and links it to a concrete mechanism that can be followed step by step from architecture to trained features.","feed_headline":"Discrete Boolean networks are born biased toward simple logic rules","feed_subtitle":"Mapping nets to logic formulas makes weight decay's effect on generalization analytically tractable.","key_machinery":"The central object is the DFCN-DNF bijection (Proposition 2.7): every depth-2 discrete network with first-layer weights in {-1,0,1} and biases set as in Definition 2.6 computes exactly one DNF formula, and every DNF is realized by some such network. The first-layer ℓ1 norm counts literals, so minimizing it over all networks for a fixed function f defines the DNF complexity K(f). The prior P(f) counts the fraction of admissible parameter configurations implementing f, and the posterior approximation P_λ(f|S) ≈ $e^{{-λK(f)}}$ P(f|S) / normalization is the paper's main quantitative tool for understanding weight decay. This machinery converts simplicity from a vague empirical observation into an architecture-linked, computable quantity and ties it directly to training dynamics and feature formation.","core_discovery":"For a depth-2 discrete fully-connected network on Boolean inputs, there is a bijection between networks and DNF formulas up to row and clause permutations, with the first-layer ℓ1 norm equal to the number of literals in the corresponding formula. Consequently, the minimal-norm network realizing a Boolean function f exactly expresses its DNF complexity K(f), and the uniform prior over parameters induces a prior P(f) over Boolean functions that is dominated by small-K(f) functions, scaling as $e^{{-Θ(K(f))}}$ for constant, t-entropy, and k-parity families. Training with a Metropolis-Hastings sampler and a greedy SGD-like algorithm shows that generalization correlates with P(f), that high-complexity targets such as full parity are effectively unlearnable, and that ℓ1 weight decay multiplies the posterior by approximately $e^{{-λK(f)}}$, sharpening the native simplicity bias and enabling the network to discover minimal DNF representations.","pith_inferences":["The same volume-ratio argument should transfer to any architecture whose parameter-function map is a finite cover over an interpretable function class; any norm that defines a complexity measure will exponentially suppress high-complexity functions when regularized.","The paper's repeating-pattern examples suggest architecture-linked complexity K(f) can diverge sharply from string-compression measures such as Lempel-Ziv; a direct test would compare sample complexity on functions that are LZ-simple but DNF-hard, where this framework predicts poor generalization despite compressibility.","The discrete, Boolean setting leaves open whether the e^{-λK(f)} factor survives in continuous networks; testing ReLU networks with ℓ1 regularization and ternary-initialized weights on the same Boolean targets would directly probe that gap, which the paper itself flags as a limitation."],"forward_implications":["If the DFCN prior is as claimed, sample complexity for a Boolean target is set by K(f): functions with small minimal DNF need few examples, while k-parity needs exponentially many.","Because P(f) is a parameter-space volume, a Bayesian learner that interpolates the training set will with high probability output a low-K(f) function, and the paper's experiments confirm test accuracy tracks P(f) across function families.","Weight decay acts as an approximate multiplicative prior e^{-λK(f)}, so it reliably improves generalization on targets with a low-complexity representation and leaves inherently complex targets such as 7-parity essentially unlearnable.","The greedy SGD-like algorithm on DFCNs shows qualitatively the same learning curves as Metropolis sampling, suggesting the simplicity bias is a property of the parameter-function map rather than an artifact of the discrete sampler.","For high-parity targets, more training data can lower test accuracy, because the posterior concentrates on lower-complexity functions that match the training subset and disagree with the rest of the input space."],"supporting_citations":[{"why":"Supplies the DFCN-DNF bijection and full-expressivity construction that Proposition 2.7 formalises.","marker":"(Mingard et al., 2019)"},{"why":"Establishes the empirical simplicity-bias bound P(f) ≲ 2^{-K_LZ(f)+O(1)} that the paper refines into architecture-linked DNF-complexity bounds.","marker":"(Valle-Pérez et al., 2018)"},{"why":"Provides the algorithmic-information-theoretic bound connecting output probability to complexity, motivating the P(f)-K(f) scaling analysis.","marker":"(Dingle et al., 2018)"},{"why":"Argues SGD approximates a Bayesian posterior and that P(f) predicts generalization, the claim the DFCN training experiments test.","marker":"(Mingard et al., 2021)"},{"why":"Identifies the Zipf-law prior as optimal for Bayesian learning, used as the reference point for width scaling and prior quality.","marker":"(Ridout et al., 2024)"},{"why":"Supplies the standard DNF representation and Boolean-analysis background used to define clauses and complexity.","marker":"(O'Donnell, 2014)"},{"why":"Documents the built-in Occam's-razor simplicity bias in deep networks, which the DFCN makes analytically explicit.","marker":"(Mingard et al., 2025)"}],"fun_headline_variants":["Boolean nets' prior favors low-complexity logic formulas","Net-to-DNF bijection reveals why simple rules generalize better","Weight decay sharpens the simplicity bias of Boolean nets","Mapping nets to DNF formulas explains their inductive bias","Simplicity prior in discrete nets: a tractable case study"],"cache_read_input_tokens":37376,"weakest_assumption_plain":"The load-bearing premise is that, for any function f, the lowest-norm parameter setting dominates all other settings that compute the same function, and that the total norm is essentially the first-layer norm; if that fails, weight decay does not reduce to the clean $e^{{-λK(f)}}$ factor in the posterior.","fun_headline_variants_meta":{"raw":{"variants":["Boolean nets' prior favors low-complexity logic formulas","Net-to-DNF bijection reveals why simple rules generalize better","Weight decay sharpens the simplicity bias of Boolean nets","Mapping nets to DNF formulas explains their inductive bias","Simplicity prior in discrete nets: a tractable case study"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000204,"raw_usage":{"total_tokens":1343,"prompt_tokens":853,"completion_tokens":490,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":469,"completion_tokens_details":{"reasoning_tokens":409}},"tokens_in":469,"tokens_out":490,"duration_ms":5400,"temperature":1.0,"reasoning_tokens":409,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:37:06.109685+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For n=4 or n=5, enumerate every DFCN parameter configuration and compute the exact posterior under a uniform prior, an 01-likelihood, and ℓ1 weight decay; if the ratio P_λ(f|S) / [$e^{{-λK(f)}}$ P(f|S)] is not approximately constant in λ and f, the minimal-norm-dominance assumption underlying Eq. (7) fails.","supporting_citations":[],"review_version":1}