acceptodds
Withdrawn from ICLR 2027

Learning Rules, Memorizing Facts: An Information-Theoretic View of Hallucination

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Understanding the relationship between generalization and hallucination requires clarifying the role of memorization. We study this relationship from an information-theoretic perspective through a Selector-Density Conditional Mutual Information (CMI) framework. In the sparse random-fact limit, a uniformly bounded information budget per fact forces a nonvanishing false-positive rate at recall bounded away from zero, even when all facts are observed during training. In a rules-and-facts setting, we decompose model–data mutual information into rule learning, atomic-fact memory, and excess memorization, revealing competition between rule learning and factual memory even without excess memorization. A joint budget bound quantifies the resulting constraint on atomic hallucination under perfect atomic recall. Moreover, an additive Gaussian model shows that maintaining high recall for atomic and composite facts incurs false positives even under optimal data mixing. Finally, controlled relational experiments hint how training exposure, rule complexity, and model capacity shape these trade-offs.

Primary area:
learning theory
Keywords:
Conditional Mutual Information, Hallucination, Generalization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_DEyeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the information-theoretic trade-offs among memorizing facts, learning reusable rules, and hallucination under limited model capacity. It begins with the random-fact model of Guo and Li (2026), deriving a lower bound on the false-positive hallucination rate in terms of the factual information retained by the model. The paper then extends this setting to incorporate composite facts generated by reusable rules. By decomposing the information retained by the model, the authors show that rule learning and atomic-fact memorization compete for a shared information budget, leading to a further lower bound on the hallucination rate under perfect atomic recall. Finally, the paper analyzes an additive Gaussian model to illustrate how training-data mixtures affect factual recall and hallucination, and presents synthetic relational experiments to investigate these trade-offs.

Critical strengths
  1. Understanding the relationship between memorization, hallucination, and model capacity is an interesting and important research problem.

  2. The paper is generally well presented, and the mathematical derivations appear largely sound.

Critical weaknesses
  1. My main concern is the limited technical novelty. The random-fact setting and its results, particularly Theorem 3.3, appear to follow directly from Guo and Li (2026). The main conceptual novelty seems to lie in extending the framework to incorporate reusable rules. This could be an interesting contribution in its own right. However, the current technical development relies primarily on a mutual-information chain-rule decomposition and standard information-theoretic arguments, including techniques already used by Guo and Li (2026). It does not appear to provide substantial additional insights that exploit the specific structure of the rule sets or characterize how that structure affects the trade-off between rule learning and factual memorization.

  2. The tightness of the main information-theoretic bounds remains unclear. The paper establishes necessary information-budget constraints but does not provide matching achievability results for the rules-and-facts setting, even for specially constructed rule families, let alone realistic learning models. Consequently, it is unclear whether these lower bounds are tight or how accurately they characterize the fundamental trade-offs. In comparison, Guo and Li (2026) provide matching achievability constructions for their random-fact setting. Establishing a similarly tight characterization for the rules-and-facts extension would considerably strengthen the theoretical contribution.

  3. The experiments are more illustrative than a direct validation of the theoretical results. In particular, the experiments do not measure or estimate the information quantities introduced in the theoretical framework, nor do they quantitatively test the predicted information-budget constraints. As a result, the observed trends provide only qualitative support for the proposed interpretation, rather than convincing evidence that the theory explains the behavior of the trained models.

Questions for authors

See above

1 comment

Thank you for your response. I maintain my score.

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

The paper studies the relationship between generalization, memorization, and hallucination through a selector-density conditional mutual information framework. For random facts, it derives a lower bound on false-positive hallucinations under a limited information budget and a prescribed recall. When knowledge consists of atomic facts and reusable rules, it separates information retained about rules, atomic facts, and which facts appeared in training, yielding a joint capacity constraint. A Gaussian toy model illustrates how the training mixture affects recall and false positives, while synthetic relational experiments provide qualitative support for the competition between rule learning and factual memory.

Critical strengths

None

Critical weaknesses
  1. Limited novelty of the hallucination bound in Theorem 3.3. The bound follows from the binary-KL trade-off established by Guo & Li [1, Theorems 3.1 and 4.3]. Their Theorem 3.1 characterizes the minimum asymptotic memory rate through KL divergence, while Theorem 4.3 specializes this characterization to binary decisions with false-positive and false-negative constraints. The exponential lower bound in the present paper follows by rearranging and relaxing this binary-KL inequality.
  2. Unclear additional significance of Theorem 4.1. Guo & Li [1, Appendix A.3] already formalize competition between structured knowledge and random facts under a shared information budget. Theorem 4.1 appears to extend this argument by separately accounting for information about which facts were selected for training. While this finer decomposition is conceptually useful, the paper does not demonstrate a concrete consequence of the additional training-selection term beyond the existing rules–facts capacity argument.

References

[1] Anxin Guo and Jingwei Li. Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing. ICML, 2026.

Questions for authors
  1. Could the authors clarify the theoretical advances over Guo & Li [1]? In particular, does Theorem 3.3 provide additional generality beyond their Theorems 3.1 and 4.3, and what new conclusions does Theorem 4.1 enable beyond the rules–facts capacity trade-off in their Appendix A.3?
  2. Could the authors clarify what the CMI framework adds to the hallucination analysis beyond the mutual-information-based membership-testing framework of Guo & Li [1]? In Theorem 3.3, the candidate universe is fixed, so CMI reduces to ordinary mutual information. Which conclusions specifically benefit from the conditional formulation?
Reviewer_VE4YOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors use information theory to study how limited model capacity trades off learning reusable rules, memorizing atomic facts, and making false-positive hallucinations. They connect conditional mutual information (CMI) to random-fact false positives, split I(W; S) into rules, atomic facts, and sample selection, analyze a 1D Gaussian model, and train small Transformers on synthetic knowledge graphs.

Critical strengths
  • The problem is important and well motivated, since connecting hallucination to capacity limits between rules and facts gives a clear reason why models make confident false claims.
  • The decomposition in Lemma 4.1 (Eq. 4) is clean and intuitive, separating rule information, conditional fact memory, and training-set selection in one simple identity.
Critical weaknesses
  • Confusing notation. Across five pages in Sections 2-4, they give Z_tilde four different definitions and Theta two; even with warnings, it is hard to remember which Z_tilde applies on a given page. In Fig. 1, they also place the label "Composite Facts" directly under the rule instances X_1 to X_4.
  • Incomplete and noisy experimental reporting. The main-text experiment section is under one page and omits training steps, seed counts, and error bars everywhere, showing composite accuracy for only one setup (Fig. 5). In Fig. 2a and Fig. 5a, the log10 colorbar starts at 4.5, giving tens of thousands of false positives the same off-white color as "0 FP" (a very generous visual zero), and 0.5M appears twice on the y-axis of Fig. 5a without documented sizes. Results also vary sharply: on 6,400 rules, the largest model gets 0 FP across all four nearby mixtures in Fig. 6, yet hundreds of FPs in Fig. 2b.
  • Limited theoretical novelty. Despite claiming the first application of CMI [1] to hallucination in Section 1, they fix Z_tilde in Section 3.2 so conditioning does nothing (as they acknowledge) and state Theorem 3.3 with ordinary mutual information. They note Lemma 3.1 is similar to a lemma in [2], and in my view Theorem 3.3 at perfect recall (beta >= e^{-R}) has the same form as the classic space lower bound for approximate membership testing (such as Bloom filters).
  • Mismatch between theory and experimental metric. The authors never estimate C in Theorem 4.1 or compare it with measured Transformer capacity [3], and C_gen goes to zero when the generalization gap is small. Worse, Theorem 4.1 assumes perfect recall on atomic facts alone, whereas tau_* in Section 5 takes the minimum score over atomic facts B and an undefined composite set Z_tilde_comp, so one low-scoring composite fact lowers the threshold for all atomic negatives. In Fig. 5, when composite accuracy is zero, larger models get millions of false positives that drop to zero once composite accuracy rises, so AtomicFP partly measures composite failure rather than atomic memory.
  • The 1D Gaussian model has no memory bottleneck. Fitting N(W, 1) with one scalar mean W (Fig. 1) to atomic facts near 0 and composite facts near theta cannot memorize individual facts, and its false-positive rate in Eq. 7 does not depend on n_1 or a. Eq. 8 comes simply from covering two separated groups with one interval, and Remark 4.2 has no proof in Appendix D.
  • Confounded rule-scaling setup in Fig. 2b. Increasing the rule count at a fixed composite budget (Tab. 2) reduces composite training examples per rule by several hundred times (computed from Tab. 2), so higher false positives on larger rule sets may simply come from giving each rule too few examples.

[1]. Reasoning About Generalization via Conditional Mutual Information. Thomas Steinke, et. al. COLT 2020.

[2]. Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing. Anxin Guo, et. al. ICML 2026.

[3]. Physics of Language Models: Part 3.3, Knowledge Capacity Scaling Laws. Zeyuan Allen-Zhu, et. al. ICLR 2025.

Questions for authors
  1. Do the patterns in Fig. 2 and Fig. 5 hold when tau_* is computed using only atomic facts B (matching Theorem 4.1), and what is composite test accuracy in Fig. 2?

  2. How many training steps and seeds were used in Fig. 2, Fig. 5, and Fig. 6, what are the model dimensions in Fig. 5a, and does Fig. 2b hold when examples per rule are matched?

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

Related papers

Discussion (0)

Sign in to comment.