- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies hallucination reduction in generative models by minimizing empirical negative log-likelihood (NLL) subject to a constraint on the probability of invalid outputs. Building on a connection to truncated statistics, the authors develop a projected stochastic gradient algorithm over nested likelihood sublevels. Under a structural condition called powerfulness, together with covariance, tail, and computational oracle assumptions, the algorithm achieves approximate likelihood optimality and validity guarantees. The paper also establishes an NP-hardness result and presents a synthetic Gaussian experiment.
Critical strengths
-
Reducing hallucinations while preserving generative quality is an important problem, and the constrained optimization formulation is meaningful.
-
The paper develops nontrivial technical arguments, particularly the connection between powerfulness and convex sublevel optimization and the construction of approximate boundary minimizers. The mathematical analysis appears largely sound under the stated assumptions
Critical weaknesses
-
My main concern is the limited applicability of the main theorem.
- The global covariance lower bound is incompatible with powerfulness whenever the sufficient statistics are bounded. Powerfulness forces the natural-parameter domain to be unbounded, and along any ray in it the variance of a bounded statistic cannot stay bounded away from zero. This excludes even categorical softmax models, which the introduction cites as motivation.
- The augmentation in Proposition 12 does not resolve this either. The variance of the added indicator vanishes with the invalid mass. Moreover, since no observation lies in , the NLL decreases monotonically as the coefficient of tends to , so the assumed interior NLL minimizer does not exist.
- Even if the covariance bound were required only locally, this construction would give . That introduces polynomial dependence on and undermines the claimed polylogarithmic truncated-sampling complexity.
- The only example verified to satisfy all assumptions is a one-dimensional Gaussian whose constrained optimum has a closed form.
The paper therefore does not exhibit a nontrivial setting where the main theorem applies and the proposed algorithm is needed.
-
The claim to settle the open problem of Hanneke et al. (2018) is overstated. The original question concerns statistical learning with valid outputs under an agnostic population-loss guarantee, given an optimization oracle. The present result instead establishes empirical NLL optimization within a restricted exponential family under additional structural and computational assumptions. No population generalization guarantee is provided, and the oracle model differs. Although the main text qualifies the claim, the abstract should describe the contribution as addressing a restricted variant of the open problem rather than settling it.
-
The experimental evidence is limited and largely illustrative. It consists of a single one-dimensional Gaussian example, without baselines or measurements of the likelihood–validity trade-off; no NLL values are reported. Specific concerns:
- Appendix H does not specify whether the full algorithm was implemented or how the projections were computed.
- The final invalid mass (0.034) lies consistently below the target . Since Lemma 13 implies the constrained optimum has mass exactly , this raises the question of whether the reported procedure attains the constrained optimum.
- The illustrated Gaussian appears to have a changing variance, whereas the verified example has fixed variance. The experiment therefore likely lies outside the setting of the theorem.
Given that computational efficiency is a central contribution, the algorithm should be demonstrated on a nontrivial setting satisfying its assumptions, with actual computational and oracle costs reported.
Questions for authors
see above
2 comments
Thank you for your response. I maintain my score.
Concern 1. Covariance and MLE
Thank you for pointing this out. We agree that the capacity construction should also admit an interior MLE when the original MLE is interior. As stated in Theorem 8, we assume a prescribed powerful family satisfying the regularity and access conditions. We will revise Proposition 12 to illustrate this capacity through the more natural operation of mixing with valid mass: qθ,w=(1−w)pθ+wδz, where z is a new valid atom. The regularity bounds for this augmentation depend on the base family and mixture weights.
The lower covariance bound is needed only on the enclosing NLL sublevel; the upper bound remains global. For pθ(x)∝eθx on {−1,0,1}, observation 0 and invalid set {−1}, the MLE is 0, projections clip intervals, and FS=L+logpθ(S)=−θ proves powerfulness. The minimum variance there is of order α, giving polynomial cost in 1/α.
Concern 2. Examples and powerfulness
Tilt the product of two mixtures 21N(−1,1)+21N(1,1), with observation (0,0) and S=((−2.5,−0.15)×(0.05,2))∪((−1.8,−0.30)×(−2.2,−1.6)). Covariance is diag(1+sech2θi), between I and 2I; centered tails are uniformly sub-Gaussian, sampling and evaluation are explicit, and the MLE is 0. Projections use scalar solves and multiplier bisection. Increasing θ1 sends invalid mass to zero and decreases FS, since ∂1FS=Eθ[X1∣S]<0. This proves powerfulness.
An immediate corollary needs powerfulness only at one sufficiently small level β<α. For each θ with s=pθ(S)>β, the family need only contain θ′ with mass β and L(θ′)≤L(θ)+log(s/β)+ξ, for sufficiently small accuracy-dependent ξ. Invalid mass need not approach zero. Keeping pθ with probability β/s and returning a known valid output otherwise gives this bound with ξ=0. The approximate comparison does not require exact mixture closure.
Concern 3. Scope and population risk
We answer Hanneke et al.'s computational question (2018, §5.1) for empirical log loss in prescribed exponential families: under our assumptions, the algorithm is polynomial-time and proper, without their model-fitting optimization oracle. We will state this scope in the abstract. Any finite collection of generative laws embeds in one exponential family after arbitrarily small smoothing (Bickis, 2015, §2.2).
The population guarantee is an immediate corollary using the same algorithm. If the sufficient-statistic mean error is at most η, population excess NLL is at most ε+2Rη, provided risks are finite and the output and a feasible population optimum lie in a common radius-R ball. The data law need not belong to the family.
Our strengthened reduction proves worst-case NP-hardness of near-optimal NLL with relaxed validity even given a strictly feasible parameter. Every other hypothesis of Theorem 8 holds: Gaussian statistics with identity covariance, an explicit interior MLE and projections, and efficient sampling and exact membership. Only powerfulness fails, including its approximate form at the required level. Both results use the same sampling-oracle model.
Concern 4. Gaussian experiment
Appendix H fitted mean and variance with a valid-conditioned update using only 20 of the 40 valid observations. It did not implement Algorithms 1–2; covariance bounds and Euclidean projection accuracy were not verified.
At target 0.05, seed 0 reduced estimated mass from 0.501665 to 0.02620, while all-data NLL rose from 2.1187 to 5.2268. A feasible Gaussian attains 3.47825, close to the numerical constrained benchmark 3.47814. This run incurred excess loss. The reported 0.034 averages ten seeds; the notebook records seed 0. We will correct Appendix H.
Concern 5. Measured cost
Our central efficiency guarantee is theoretical: polynomial running time and oracle complexity. We ran invalid-conditioned PSGD with random tilts, averaging, Euclidean projections and grid/bisection on the instance in Concern 2.
Across five seeds at target 0.10, mass fell from 0.201594 to 0.100044–0.100176, and NLL rose from 2.837877 to 3.034158–3.034732. The numerical benchmark at mass ≤0.10 is 3.034922. Gaussian CDFs checked masses; slight validity relaxation explains the lower NLLs.
Each run used 76,800 conditional draws and 4.25 million ordinary draws for mass estimates. Including rejection, the median was 5,074,647 membership queries and 2.54 seconds (AMD EPYC 9V74, one thread), for search, projections and oracle calls; benchmarking excluded. We used three tilts, 6,400 steps per tilt, grid 0.16 and tilt strength 0.018. These empirical budgets do not establish the theorem's confidence guarantee.