- Rating
- 3
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors present some identifiability results for learning Boolean functions. In this setting, there is a natural measure of "complexity of a downstream task", which is Fourier degree. Under a "simplicity assumption" which minimizes this Fourier degree, the representation of the "world"'s binary states is identifiable. The authors do some experiments in transformers which aim to support this theory.
Critical strengths
- The theorems seem correct and at least the identifiability result seems substantial relative to earlier well-received literature, to the extent I can evaluate them.
- The figures are extremely well-done and explain the ideas of the paper very well (specifically, Figures 1 & 2).
- The writing is precise enough that I can understand the key theoretical results, despite little familiarity.
Critical weaknesses
- The abstract is fairly difficult to read, with the staccato sentences. I would recommend a substantial rework.
- In general, the applicability to representation learning in practice is not clear to me. The experiments are fairly mechanical validation of the theorems, in my view, and do not say anything about real-world networks (despite using e.g. transformers) as a backbone, due to the nature of the supervision.
- The writing around the experimental results is difficult to follow.
- There is no limitations section, which makes it difficult to place this in the broader literature for me.
Questions for authors
- Does your work have practical implications for representation learning more broadly? Or is it purely a theoretical exercise (which would be fine - I just can't tell)?
- How does your identifiability result relate to other identifiability results in representation learning, such as those referenced in the first paragraph of related work?
2 comments
I thank the authors for their reply. My reading of the immediate practical implications is that they are fairly limited, and that there is limited connection to other identifiability results cited in the related work section, many of which I am much more familiar with.
I am generally convinced that the theory is well-written and technically correct, and I reiterate my position that the figures are helpful for understanding the work -- this is what underpins my score of 3, with relatively low confidence.
However, I am not convinced by the significance of the work, and would in general defer to other reviewers on this point. For myself, I see little relatedness to the identifiability topics that I work on, and little potential for immediate practical impact.
With regard to the writing: I maintain my position that the level of jargon in the abstract is unnecessary and hinders the understanding of the work; furthermore its structure and style is simply not conventional for the venue.
Practical implications, identifying information, and the revised experiments
W2/Q1. What practical implications does the theory provide?
Yes. The practical implications concern which shared tasks to train on and how to assess the resulting representation. Prediction accuracy alone cannot distinguish codes that retain the same information. For door and light states (D,L), both (D,L) and (D,DL) answer the same tasks, but reading L requires one coordinate in the former and a product in the latter.
For task selection, our new insight is that certain higher-order family constraints already rule out mixed codes without separately requiring direct coordinate tasks to remain first-order. Under the stated task laws and average-Fourier-degree criterion, joint cumulative quadratic and cubic spaces suffice at d=4, and the cumulative cubic space suffices at d≥5. “Cumulative cubic” includes interactions of order at most three. Every insufficient choice has an explicit counterexample. This lets researchers ask whether their task family constrains coordinate structure, rather than simply whether it contains many tasks.
For evaluation, coordinate readout from frozen representations complements task accuracy, with unseen states evaluated separately. Our added held-out-state experiment follows this design and improves coordinate accessibility over random encoders on all three splits. The paper's main contribution is an identifiability theory for finite bijective encodings; it supplies concrete task-selection and evaluation criteria, with neural experiments examining the associated phenomena.
Q2. How does this relate to other identifiability results?
These results all ask when representations are identifiable; they differ in the information that removes ambiguity and the transformations left afterward. We use shared tasks and their interaction complexity. The cited works use auxiliary variables, paired observations or interventions.
Khemakhem et al. use an auxiliary-conditioned exponential-family prior with rich modulation, identifying sufficient statistics up to an invertible affine map; stronger conditions refine this to block permutation. Locatello et al. (2020) use pairs sharing factors and a known number of changed factors, obtaining coordinatewise reparameterization and permutation under their regularity assumptions. Ahuja et al. combine polynomial reconstruction and support conditions for affine identification; hard interventions identify affected coordinates up to shift and scale.
Our binary ambiguity is signed coordinate permutation; the q-ary result allows coordinate and within-coordinate symbol permutations. Relative to Zhang et al., we classify which higher cumulative families force this structure without a separately weighted first-order family, with mixed-code witnesses for every failure case. The revised Related Work compares identifying information, assumptions and remaining ambiguity.
W2/W3. What does the experimental evidence establish?
We reorganized the experiments around three questions: can task responses reconstruct coordinates, can learned activations expose those coordinates, and does accessibility extend to unseen states? The synthetic reconstruction study recovers every state in all 180 runs at d=7. The original neural study trains a Transformer on exact cubic parities, freezes it, and fits supervised readouts using targets constructed from true states.
To address the supervision concern, the added six-bit study excludes 12 states from both encoder training and coordinate-probe fitting, then evaluates individual activations on fresh sequences. Mean held-out coordinate accuracy is 67.56%, 75.33% and 73.06%, versus 54.47%, 55.44% and 47.17% for random encoders. This directly tests whether task training makes coordinates accessible at unvisited states.
Task prediction is reported separately: held-out parity accuracy is 35.12–36.55%, versus 78.32–81.88% for all-state controls. Each experiment now states its supervision and evaluation target before presenting results; captions distinguish raw adjacency, corrected coordinate recovery and individual-activation readout.
W1/W4. Abstract and limitations.
The abstract preserves the original account of the problem, classification, recovery and experiments. Scope and computational requirements are explained beside the results they qualify.
The Introduction and Section 3 state the finite-bijection and global average-degree-minimization setting. Section 5 places the state-query lower bound, streaming complexity and partial/noisy-response conditions beside the recovery results. Section 7 distinguishes full-response reconstruction, supervised neural readout and the added held-out-state evaluation. Readers can check each result's conditions and experimental purpose where it is used.