acceptodds
Under review as a conference paper at ICLR 2027

Recoverable but Unreadable: Exact Accessibility Laws in Noisy Latent Parity Codes and Beyond

Abstract

A representation can contain nearly all information about a latent factor while exposing none of it to a simple probe. We formalize this gap by distinguishing recoverability, what the full representation reveals to the Bayes-optimal decoder, from accessibility, what is exposed through a restricted readout interface. We study this distinction in noisy latent parity codes, a fully analyzable benchmark family. Under the uniform prior, we prove an exact reveal law: the first order at which a target becomes readable is determined by a single combinatorial quantity of the mixing matrix, the minimum number of observed parities needed to synthe- size that target parity. This quantity also governs both local readout and low-order interaction readout. For balanced binary targets, every sub-threshold local view is exactly independent of the target, so Bayes-optimal prediction remains at chance. For random dense mixing below channel capacity, the full latent vector is decod- able with exponentially small error, yet each coordinate remains unreadable to every sub-threshold simple interface. In the BSC case, even the first nonzero wit- ness can be exponentially weak, so reveal need not imply learnability. We also use this family as an exact probing benchmark and show that accessibility-aware objectives can reduce low-order exposure while preserving strong global utility. A continuous learned bridge beyond the parity family exhibits the same qualitative pattern: strong global signal can coexist with substantially weaker local readabil- ity, and accessibility-aware shaping reduces low-order exposure there as well.

Primary area:
learning theory
Keywords:
Representation learning, representation probing, interpretability, information accessibility, latent parity codes, Boolean Fourier analysis, error-correcting codes

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_gbHSOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper provides a theory-backed separation between information which "exists" in a presentation, information that a restricted probe of that representation can actually access, and information that a model could learn from limited samples.

They very neatly define the differences, prove claims about the scope of those definitions, as well as a witness condition based on xor's in parity.

Empirical evidence supports all the theorems and claims, which hold tightly for the parity regime.

The mathematical details often exceed my direct area of expertise, particularly the denser coding-theoretic portions. My evaluation therefore focuses primarily on the conceptual contribution, internal consistency of the claims, clarity of assumptions, and alignment between the theoretical and empirical components.

Critical strengths
  1. Primary concepts of the paper are hyper concise, and focused on narrowly. The focus around witness complexity is tight and effective, and any sprawling from the main message are exact and relevant.
  2. None of the results seem to disagree either in favor or against any of the theoretical claims and bounds
  3. Scope being tightly connected to parity is honest and constructive
Critical weaknesses

The only weakness I can even remotely conceive of is practical usefulness. I thought this may have been a quantum paper when I first started reading, perhaps this is feedback more than a weakness.

Questions for authors
  1. The paper convincingly separates recoverability, accessibility, and learnability. What practical conclusion should a researcher designing probes or evaluating representations draw from these results?
  2. Witness complexity appears to be the central quantity throughout the paper. Are there existing representation-learning settings where witness complexity can be estimated or approximated in practice, or is it primarily a theoretical diagnostic?
  3. The paper argues that probe failure need not imply absence of information. How should the results change how readers interpret negative probing results in modern representation-learning settings?
3 comments
AuthorsOpenReview ↗

Response to Reviewer gbHS

Thank you for your positive feedback! The practical implication is that a probe result should be interpreted relative to the interface and learning procedure that produced it.

1. Practical probing. A probe study should specify (i) the observed interface (all coordinates, a subset, or allowed interactions), (ii) the function class and training objective, and (iii) the sample and compute budgets. This separates missing global information from interface-level unreadability and failure of a finite training procedure. Positive controls, learning curves, and stronger-interface references are useful when feasible. Our decoder-refitting experiment illustrates the distinction: on the same frozen parity matrices, fresh decoder training raises bit accuracy from about 0.52 to 0.86, while exact Bayes block accuracy and Mean Rec remain unchanged. A failed trained probe therefore need not imply that the representation lacks information.

2. Witness complexity. For a known parity matrix, rq(A)=min⁡A⊤v=q∣v∣r_q(A)=\min_{A^\top v=q}|v| can be computed exactly by bounded-order enumeration or syndrome search. This gives an exact unreadability certificate below the witness order. For general neural embeddings, the parity matrix and Walsh support are unknown, and a practical analogue is an accessibility profile over nested coordinate subsets, interaction orders, or feature groups. Such a profile is an empirical diagnostic, not an exact witness certificate.

3. Negative probing results. Under the uniform-prior parity assumptions, a balanced target is independent of every sub-threshold coordinate subset, so even a Bayes classifier is at chance. Zero correlation with low-degree polynomial scores is weaker: the three-coordinate BSC example reaches 0.68225 threshold accuracy despite zero degree-at-most-two score correlation. Thus a negative probe result is evidence about the tested interface, function class, loss, and training budget—not automatically about all information in the representation.

The continuous experiment illustrates the same distinction beyond parity. A rotation of the final normalized codebook preserves full Bayes information, while changing which signals are exposed through one- or two-coordinate interfaces. Across 20 encoders, access-aware mixing reduces best-two-coordinate Bayes accuracy relative to three prespecified Haar rotations by 4.48, 4.49, and 1.73 percentage points for triangle, left-half, and XOR (paired pointwise 95% intervals exclude zero). Unrestricted full-coordinate linear, quadratic, and MLP probe classes are invariant under orthogonal changes of basis, although finite-training accuracy can differ. A negative local probe and a successful global probe can therefore both be correct: they test different interfaces.

I appreciate the clarifications and the time put into the response period. There is, however, not much I can do to improve the score given I already like the paper and cannot see any revisions as of yet.

Thank you for following up. The revised PDF is on the submission page as a clean version, so the changes are incorporated into the text rather than highlighted. We should have pointed you to the relevant sections more clearly.

For practical probing (Q1), Sections 6.1 and 6.3 (pp. 7, 9) specify the evaluation metrics and probe-training scope. Section 6.4 and Appendix I.1 (pp. 9, 25–26) illustrate the gap between information in a fixed representation and what a trained decoder can extract. Section 6.5 and Appendix H (pp. 9, 22–24) extend this distinction to a continuous neural setting.

For witness complexity (Q2), Sections 3–4 (pp. 4–5) give the exact characterization for parity representations, while Appendix F.1 (p. 18) also treats grouped interfaces. The Limitations (p. 10) clarify the scope of these results and their applicability beyond parity.

For negative probing (Q3), Section 6.3 (p. 9) distinguishes low-degree score correlation from threshold-classification accuracy and clarifies the scope of the chance-level result. Appendix I.1 (pp. 25–26) further illustrates why a failed trained decoder need not imply missing information.

We hope these pointers make the relevant material easier to locate. Thank you again for your feedback and positive assessment.

Reviewer_CzLPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies when information can be recovered from a representation but remains inaccessible to restricted probes. For noisy parity codes, it proves that the minimum witness weight determines the first readable order for both local observations and polynomial scores. Random coding results establish a separation between global recovery and local prediction. Experiments examine whether training objectives can reduce low-order exposure.

Critical strengths
  1. Theorems 2 and 3 give a precise, shared threshold for local and polynomial readout under informative binary-input channels. For balanced binary targets, the local result establishes independence, which is stronger than zero correlation.
  2. Theorems 4 and 5 connect reliable global decoding to local unreadability. The separate analysis of a specified witness also makes clear that a nonzero signal may still require many samples to estimate.
Critical weaknesses
  1. The continuous results conflict with the stated setup. Appendix H.1 freezes the encoder and applies an orthogonal mixer, fixed-radius normalization, and isotropic Gaussian noise. These operations make the full observation equivalent to an invertible rotation of the baseline. Full Bayes accuracy and recoverability should therefore remain unchanged. Yet Table 7 reports a drop in full accuracy from 0.9390 to 0.8944 and in the full posterior proxy from 0.9071 to 0.8321. This discrepancy undermines the reported tradeoff and needs an implementation-level explanation.
  2. Zero correlation of polynomial scores does not imply chance accuracy for threshold classifiers. For example, take encoding rows (0,1,0), (0,0,1), and (1,1,1), with the first latent bit as the target. The witness threshold is 3. Under BSC(0.05), every linear score has zero correlation with the target, but predicting +1 when the sum of the three observations is negative achieves accuracy 0.68225. This does not contradict Theorem 3; it limits the classification interpretation in Section 6.3. Corollary 2 only proves impossibility for coordinate-local classifiers.
Questions for authors
  1. Why do the full Bayes quantities in Table 7 change under an orthogonal mixer? Please report the orthogonality error and verify the posterior calculation using the same frozen encoder and paired, rotated noise samples.
  2. How should the probe claims be interpreted in light of the threshold-classifier example above? Please distinguish score correlation from classification accuracy and state which conclusions depend on the training loss.
  3. In Table 1, the dense reference has the same zero order-2 exposure as the access-aware encoder but higher block accuracy (0.8636 versus 0.7309). What advantage does the proposed optimization offer over random screening at the same search budget? Please also report success rates and variability across all 20 learned-encoder seeds.
1 comment
AuthorsOpenReview ↗

Response to Reviewer CzLP

Thank you for the helpful review.

1. Table 7 and rotation invariance. An orthogonal rotation of the final representation, with isotropic noise, preserves full Bayes information. In the original continuous pipeline, the mixer was followed by per-sample feature centering, coordinate-dependent rescaling, and fixed-radius normalization. These operations need not commute with rotation: Norm(Qh)≠QNorm(h)\mathrm{Norm}(Qh)\ne Q\mathrm{Norm}(h), and can change codeword distances before noise is added. Thus the earlier full-accuracy and posterior-proxy changes (0.9390→0.89440.9390\to0.8944 and 0.9071→0.83210.9071\to0.8321) describe that geometry-changing pipeline, not a pure rotation of the final codebook. The revised Table 7 replaces the earlier results with a final-codebook rotation evaluation: a common normalized codebook is formed first, then each variant applies zs(Q)=Qzs(0)z_s(Q)=Qz_s^{(0)}, with Q⊤Q=IQ^\top Q=I and no further non-equivariant normalization.

For XOR, all variants have Full Acc. 0.87160.8716 and Full Rec 0.78930.7893. Across 20 encoders and 240 variant–target checks, maximum orthogonality error is 9.90×10−79.90\times10^{-7}, and paired full-accuracy and recoverability differences are at most 5.31×10−95.31\times10^{-9} and 1.31×10−81.31\times10^{-8}, with zero Bayes-decision disagreements (8,192 paired audit samples). Independent NumPy/PyTorch float64 posteriors agree to 2.89×10−152.89\times10^{-15}. Relative to three prespecified Haar rotations per encoder, access-aware mixing reduces Best-2 accuracy by 4.48, 4.49, and 1.73 pp for triangle, left-half, and XOR (paired pointwise 95% CIs [-5.86,-3.05], [-5.54,-3.35], [-2.72,-0.80]). Each effect favors access-aware in 18/20 encoders and persists on holdout. Haar is a reference, not an optimized-rotation search.

2. Thresholding a polynomial score. Your BSC$(0.05)$ counterexample is correct. For rows (010),(001),(111)(010),(001),(111) and target Z1Z_1, the witness order is 3; degree-≤2\le2 monomial correlations vanish, yet sign(−Y1−Y2−Y3)\mathrm{sign}(-Y_1-Y_2-Y_3) reaches 0.68225 accuracy. Its Boolean expansion, (Y1Y2Y3−Y1−Y2−Y3)/2(Y_1Y_2Y_3-Y_1-Y_2-Y_3)/2, contains the first nonzero degree-three witness. We revised Section 6.3: Theorem 3's interaction statement concerns score correlation, whereas Corollaries 1–2 give chance-level Bayes accuracy for classifiers restricted to fewer than the required input coordinates. With logistic loss, zero correlation makes the zero score a population minimizer within the degree-≤2\le2 score class. This does not constrain threshold classifiers whose Boolean expansions contain higher-degree terms.

3. When accessibility-aware optimization helps. Under the original order-2 constraint and a common 451-candidate post-hoc rule, random, global-only, and access-aware search all found feasible codes in 20/20 runs, and mean block accuracies were 0.86720/0.86795/0.86806. The access-aware gain over random was about 0.0009, so we do not claim an order-2 search advantage in this saturated setting.

We therefore strengthened feasibility to full rank and N≤3(A)=0N_{\le3}(A)=0. At 451 candidates, order-3 access-aware search achieved 20/20 feasible runs and mean feasible block accuracy 0.8647, versus 8/20 and 0.8214 for random, 3/20 and 0.8083 for global-only, and 7/20 and 0.8357 for the order-2 optimizer. At 2,048 candidates, it achieved 20/20 and 0.8678, versus 19/20 and 0.8254, 14/20 and 0.8298, and 19/20 and 0.8448. At a matched 1.4–1.55 s budget, order-3 search achieved 20/20 and 0.8670, compared with 0.8216–0.8254 for random, 0.8298 for global-only, and 0.8437–0.8448 for order-2 search.

A structure-specific GF(2) basis baseline chooses invertible CC whose columns avoid S≤3(A)={A⊤v:1≤∣v∣≤3}S_{\le3}(A)=\{A^\top v:1\le |v|\le3\} and sets A′=AC−⊤A'=AC^{-\top}. It yields N≤3(A′)=0N_{\le3}(A')=0 in 20,000/20,000 tests while preserving the codeword set and uniform-message optimal block accuracy. This changes the message-to-codeword assignment and coordinate-specific accessibility. At matched wall-clock time it achieves 20/20 and about 0.8680, close to order-3 search (20/20, 0.8670). Our claim is an advantage over generic random/global/order-2 search, not over this exact parity-specific construction.

To characterize learned-encoder variability, we report all 20 seeds per witness weight. Both N≤2=0N_{\le2}=0 and full-rank N≤2=0N_{\le2}=0 occurred in 1/20, 3/20, 3/20 runs at λwit=0/0.3/1.0\lambda_{\rm wit}=0/0.3/1.0. Bayes block accuracy (mean±seed SD) was 0.7546±0.0918 / 0.7967±0.0948 / 0.7848±0.0880, and Mean Rec was 0.8487±0.0519 / 0.8642±0.0974 / 0.8510±0.0953; LocalBayes$_{\le2}$ was 0.6323±0.0596 / 0.5841±0.0575 / 0.5772±0.0672. Strict learned success remains infrequent.

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

The paper distinguishes two things: how much information can be recovered in a complete representation, and how much signal can be extracted by a specified readout interface. Further investigate the design of parity encoders and the extension of continuous representations through experiments.

Critical strengths
  1. The derivation based on fractional coordinates is not only applicable to BSC, but also covers other binary input channels with information content. Theorem 3 and Corollary 1 accurately distinguish between local independence and zero correlation of interaction terms.
  2. The paper does not equate the "first appearance of non-zero signals" with "easy to learn";
Critical weaknesses

The experiment of learning odd even encoders did not demonstrate how stable the target can find an encoder that balances utility and readability. G. Section 3 states that each setting runs 20 seeds, but Table 5 only lists two examples for each setting. When lambda wit=1.0, one example has no second-order leakage, while the low order readability of the other reaches 0.712.

Questions for authors
  1. How to explain the global Bayesian variation in Table 7 under the settings of fixed encoder, orthogonal mixing, and isotropic noise? Did the actual experiment use different configurations, or were there any issues with the evaluation and tables?
  2. What is the proportion of N_ {<=2}=0 in all 20 learning runs for each regularization strength? What is the distribution of decoding accuracy and recoverability for these running blocks? How does it compare to filtering dense random constructions under similar search budgets?
3 comments
AuthorsOpenReview ↗

Response to Reciewer psBb

Thank you for your careful review of our submission.

1. Complete learned-parity evaluation. We now report a fully specified 20-seed evaluation per λwit\lambda_{\rm wit}, fixing initialization, relaxed-parity parameterization, loss reduction, straight-through hardening, and checkpoint selection, and all runs are included. We distinguish the requested N≤2=0N_{\le2}=0 count from the stricter condition that also requires full rank.

λwit\lambda_{\rm wit}Full rankN≤2=0N_{\le2}=0Full rank & N≤2=0N_{\le2}=0Bayes block (mean±SD)Mean Rec (mean±SD)LocalBayes$_{\le2}$ (mean±SD)MLP bit
019/201/201/200.7546±0.09180.8487±0.05190.6323±0.05960.5327
0.319/203/203/200.7967±0.09480.8642±0.09740.5841±0.05750.5197
1.019/203/203/200.7848±0.08800.8510±0.09530.5772±0.06720.5136

Both success counts coincide here; all strictly feasible runs have LocalBayes$_{\le2}=0.5$. Among strictly feasible runs, Bayes block mean [range] and Mean Rec mean [range] are: λ=0\lambda=0, 0.7341 (n=1) and 0.8435 (n=1); 0.30.3, 0.8219 [0.7930,0.8403] and 0.8809 [0.8696,0.8907]; 1.01.0, 0.7972 [0.7387,0.8415] and 0.8691 [0.8450,0.8893]. Their trained-MLP bit means are 0.5002, 0.5020, 0.5030. At λ=0.3\lambda=0.3, mean two-coordinate Bayes readability decreases by 0.04815 (paired 95% CI [−0.07605,−0.01823][-0.07605,-0.01823]), while mean Bayes block accuracy increases by 0.04209 ([0.02266,0.06271][0.02266,0.06271]), relative to λ=0\lambda=0. Reliable end-to-end acquisition remains challenging.

2. Recoverability versus decoder learnability. We froze the same 60 hardened matrices and compared the original decoder (D0) with a fresh decoder trained for 2,600 decoder-only steps (D1). For each matrix, exact Bayes block accuracy and Mean Rec are unchanged. Bit accuracy rises from 0.5329/0.5202/0.5133 to 0.8648/0.8646/0.8605 for λ=0/0.3/1.0\lambda=0/0.3/1.0; MLP block accuracy rises from 0.0026/0.0020/0.0018 to 0.4623/0.4799/0.4926. All paired 95% CIs exclude zero. These are additional decoder-only updates, not an equal-budget end-to-end advantage. The same representation can be recoverable while the original trained decoder fails to exploit it.

Under a matched 2,600-update hard-forward STE protocol, bit accuracy improves from 0.5222±0.0246 to 0.7089±0.1048, MLP block accuracy from 0.0021±0.0016 to 0.1455±0.1522, and Bayes block accuracy from 0.7787 to 0.8147; full-rank runs increase from 57/60 to 60/60. However, only 9/60 satisfy N≤2=0N_{\le2}=0, and none jointly satisfy this condition and bit accuracy ≥0.80\ge0.80. Joint success remains unresolved.

3. Matched screening and stricter accessibility. Under the order-2 constraint and a common 451-candidate rule, random, global-only, and access-aware search all achieve 20/20 feasibility, with mean block accuracies 0.86720, 0.86795, 0.86806; the access-aware gain over random is about 0.0009. We therefore strengthened feasibility to full rank and N≤3(A)=0N_{\le3}(A)=0. At 451 candidates, order-3 access-aware search achieves 20/20 feasible runs and block accuracy 0.8647, versus 8/20 and 0.8214 for random, 3/20 and 0.8083 for global-only, and 7/20 and 0.8357 for order-2 search. At matched wall-clock time, order-3 search achieves 20/20 and 0.8670. Separately, random screening matched to learned-encoder training time found 20/20 order-2-feasible codes (mean Bayes block 0.8681).

A parity-specific GF(2) basis construction chooses invertible CC with columns outside S≤3(A)={A⊤v:1≤∣v∣≤3}S_{\le3}(A)=\{A^\top v:1\le|v|\le3\} and sets A′=AC−⊤A'=AC^{-\top}. It achieves N≤3=0N_{\le3}=0 in 20,000/20,000 tests while preserving the codeword set and uniform-message optimal block accuracy; it changes the message-to-codeword assignment and coordinate-specific accessibility. It is stronger per candidate; at matched wall-clock it achieves 20/20 and about 0.8680, close to order-3 search (20/20, 0.8670). We limit the optimization claim to generic random/global/order-2 baselines.

4. Table 7. The original pipeline applies an orthogonal mixer before per-sample centering, coordinate-dependent rescaling, and fixed-radius normalization; these operations can change codeword distances. The revised Table 7 replaces the earlier measurements with rotations of the final normalized codebook. For XOR, all variants have Full Acc. 0.8716 and Full Rec 0.7893. Across 240 audit checks from 20 encoders, maximum orthogonality error is 9.90×10−79.90\times10^{-7}, full-accuracy/recoverability differences are at most 5.31×10−9/1.31×10−85.31\times10^{-9}/1.31\times10^{-8}, and there are zero decision disagreements. Access-aware mixing reduces best-two-coordinate Bayes accuracy versus Haar by 4.48, 4.49, and 1.73 pp for triangle, left-half, and XOR (paired 95% CIs exclude zero).

This is an effective response that answered some of my doubts. So, personally, I would like to improve the author's score

Thank you very much for your thoughtful follow-up and for raising your score for our paper. We sincerely appreciate your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.