{"id":"3381394c-9cc2-4ce8-814a-d2234de39b13","arxiv_id":"1908.06514","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The balance heuristic estimator is recast on an extended space, yielding an unbiased parallel annealed importance sampling scheme and a general framework for estimators when proposal marginals are intractable.","lead":"This paper studies the balance heuristic estimator for computing normalising constants when the pool of proposals is far larger than the number of samples. It introduces an extended-space representation that enables new annealed importance sampling schemes and new estimators for problems where proposal densities are only available jointly with a discrete label.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Ẑ_GF2's bias is controlled only as N→∞, which is the wrong asymptotic for the advertised K≫N regime; no finite-N bias bound or proof is supplied.","rationale":"The reader's verdict is CONDITIONAL, and my concern is compatible with it, but the emphasis differs. The reader's weakest assumption focused on K_eff≪K; my strongest concern is more specific: the new intractable-proposal estimator Ẑ_GF2 has a bias that is only argued to vanish as N→∞, whereas the paper's stated setting is K≫N with N fixed. The extended-space representation and Theorem 2 for Ẑ_T,mAIS appear correct, so I do not object to the core unbiasedness result. However, the general framework's practical value for intractable proposals rests on Ẑ_GF2 (and, to a lesser extent, Ẑ_comb), and both lack finite-sample bias guarantees. The paper itself flags the bias and the K_eff≪K requirement, but it does not provide the missing analysis. A concrete analytical computation of the bias via Proposition 2, plus a targeted simulation with N fixed and K growing, would settle whether the advertised large-K regime is actually supported. I also noticed a factor-of-N typo in Lemma 1's stated variance formula, though the proof gives the correct expression and the optimal weights in Theorem 3 are unaffected; this is not the primary concern.","tokens_in":32363,"tokens_out":33674,"duration_ms":328273,"concrete_test":"Derive the exact bias E[Ẑ_GF2]-Z from Proposition 2 for the Gaussian running example, as a function of N and K for s=20 and s=∞, and evaluate it at N=500 for K=3000 and K=3×10^6. If the bias does not vanish as K→∞ at fixed N, the large-K claim fails. Additionally, rerun Figure 5 with N fixed and K increasing (e.g., 10^5, 10^6, 10^7) and report median/quantiles of log Ẑ_GF2 to check whether the boxplots approach Z rather than remaining offset.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main new estimator for the intractable-proposal setting, Ẑ_GF2, is advertised for K≫N with N fixed, but Section 3.3 only justifies its bias through the statement that 'the resulting bias vanishes as N→∞ due to the consistency of ρ_n'. This is an assertion, not a proof. Proposition 2 shows that Ẑ_GF2 actually targets Z(Ψ,ρ)=E_{L∼α⊗N,X∼π}[Σ_n ψ_n(X)ρ_n/(α(L_n)Σ_m ψ_m(X))] rather than Z. For the GF2 choice ψ_n(x)=¯q(x,L_n) and ρ_n=(K^{-1}+N_{L_n}-1)/N, equality with Z requires ρ_n/α(L_n)→1. For fixed N and K→∞, most sampled labels have N_{L_n}=1, giving ρ_n≈1/(NK), so ρ_n/α(L_n)≈1/N, not 1. No finite-N bias bound, no rate, and no K-asymptotic result is provided. The empirical evidence in Figure 5 is consistent with this concern: for s=20 (diffuse marginal proposal), Ẑ_GF2 is visibly biased at K=3000 and badly biased at K=3×10^6 with N=500. Since the paper's motivating regime is exactly large K with small N, the N-consistency argument does not support the claimed practical usefulness of Ẑ_GF2 in that regime.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the balance heuristic for estimating normalising constants when the number of proposals K is much larger than the number of importance points N. It introduces an extended-space representation of the balance heuristic (Eq. 8), from which it derives a modified annealed importance sampling estimator (Algorithm 2) and proves its unbiasedness (Theorem 2). The paper then considers the intractable-proposal setting in which only the joint density \\bar{q}(x,l) is available, and proposes a general framework (Eq. 14) that includes both the balance heuristic and linear combinations of unbiased estimators. Two specific estimators, \\hat{Z}_{GF1} and \\hat{Z}_{GF2}, are introduced and compared numerically on a Gaussian running example. The paper is explicitly candid about the bias of \\hat{Z}_{comb} and about the regime restrictions implied by K_eff << K, but the treatment of \\hat{Z}_{GF2} in the advertised K >> N regime is not supported by the analysis.","tokens_in":32665,"tokens_out":23149,"duration_ms":235518,"significance":"The extended-space representation of the balance heuristic is a genuinely useful conceptual contribution: it yields a clean derivation of the modified annealed importance sampling estimator, with an unbiasedness proof in Theorem 2, and it provides a common framework that contains both the balance heuristic and combinations of unbiased estimators. The proofs in Appendix 1 are substantially complete and appear correct for the balance-heuristic part. The paper is also commendably honest about the limitations of \\hat{Z}_{comb}. However, the main new estimator for the intractable-proposal setting, \\hat{Z}_{GF2}, is advertised for the regime K >> N with N fixed, while its bias is only argued to vanish as N → ∞; the numerical results in Figure 5 are consistent with a substantial bias in exactly that regime. In addition, the displayed formula for \\hat{Z}_{GF1} is internally inconsistent with the general estimator definition, changing its expectation by a factor of N. The core contribution on the balance heuristic and annealed importance sampling is sound, but the Section 3 claims need substantial revision.","major_comments":[{"comment":"The claim that the bias of \\hat{Z}_{GF2} 'vanishes as N → ∞ due to the consistency of ρ_n' addresses only the N-asymptotic, whereas the paper motivates GF2 precisely for K >> N with N fixed. From Eq. (14) and Proposition 2, the expectation of \\hat{Z}_{GF2} is Z times \\mathcal{Z} = E_{L,X∼π}[Σ_n q_{L_n}(X) ρ_n / (Σ_m q_{L_m}(X) α(L_m))]. For fixed N and K → ∞, most sampled labels are unique, giving ρ_n ≈ 1/(NK); when α is diffuse this yields ρ_n/α(L_n) ≈ 1/N and hence \\mathcal{Z} ≈ 1/N, not 1. The empirical bias in Figure 5(c) (s = 20, K = 3 × 10^6, N = 500) is consistent with this concern. No finite-N bias bound, convergence rate, or K-asymptotic argument is supplied. Because K >> N is the advertised regime, this is a load-bearing gap: either the bias must be proved to vanish in the relevant asymptotic, or \\hat{Z}_{GF2} must be repositioned as a heuristic whose bias is an explicit limitation.","section":"Section 3.3, Eq. (14), Proposition 2, Figure 5"},{"comment":"The general definition of \\hat{Z}_{GF} in the paragraph immediately above gives \\hat{Z}_{GF1} = Σ_n [\\tilde{π}(X_n)/\\bar{q}(X_n,L_n)] ρ_n, where ρ_n = (K^{-1} - 1 + N_{L_n})/N; this is (1/N) Σ_n [\\tilde{π}(X_n)/\\bar{q}(X_n,L_n)] (K^{-1} - 1 + N_{L_n}). The displayed equation for \\hat{Z}_{GF1} instead contains an additional factor 1/N. With that displayed estimator, E[\\hat{Z}_{GF1}] = Z/N rather than Z; with the general formula, Proposition 2 gives E[\\hat{Z}_{GF1}] = Z. This inconsistency changes the unbiasedness of the estimator by a factor of N and must be corrected. The numerical experiments should also state explicitly which version was implemented.","section":"Section 3.3, displayed formula for \\hat{Z}_{GF1}"}],"minor_comments":[{"comment":"The symbol Z is used both for the unknown normalising constant of π and for the integral of η_{GF}, which equals 1 for the balance heuristic and for GF1 but need not equal the target normalising constant. Renaming the latter, e.g. \\mathcal{Z}(Ψ,ρ), would prevent a serious source of confusion.","section":"Proposition 2 and Eq. (14)"},{"comment":"The pseudocode contains a duplicated loop line 'for t ∈ [1,T − 1] do'; one of the duplicated lines should be removed.","section":"Algorithm 1"},{"comment":"There is a typographical error in 'normalisi ng constants' in the title line of the arXiv text; it should read 'normalising constants'.","section":"Abstract and title"},{"comment":"The boxplot labels such as AIS_M3, AIS_M2, AIS_M1, AIS_G, and GF_T1 are not all defined in the captions or text; a brief explanation of the naming convention would improve readability.","section":"Figures 2 and 6"}],"recommendation":"major_revision","confidential_remarks":"The balance-heuristic and modified-AIS part of the paper is solid and worth publishing after revision. The main risk is in Section 3: the GF2 estimator is the paper's headline solution for intractable proposals, but its bias behaviour in the K >> N regime is not established, and the GF1 formula appears to have a factor-of-N inconsistency. These issues are fixable within the manuscript's scope by adding a rigorous bias analysis or by substantially qualifying the claims, so I do not recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead this one for the extended-space representation of the balance heuristic, which is the genuinely useful piece. It lets you write the balance heuristic estimator as importance sampling on a space that includes the per-sample chosen label, and that opens the door to a modified AIS scheme (Algorithm 2) that is unbiased, easy to parallelize, and less fiddly than the standard version. The general framework in Eq. (14) is also a nice unifying device: it recovers both the balance heuristic and linear combinations of unbiased estimators as special cases. The proofs I checked are correct: Theorem 2's unbiasedness argument is clean, Proposition 2 is a straightforward integration, and Lemma 1 is standard negative-correlation stuff.\n\nThe soft spot is the intractable-proposal estimator Ẑ_GF2. The paper says its bias vanishes as N→∞ because ρ_n is consistent. That is true for fixed K, but the whole point of the method is the K≫N regime with N modest. In that regime, for a typical label with N_l=1, ρ_n/α(l_n) is on the order of 1/N, not 1, so the expected estimator is not Z. There is no finite-N bias bound or a K-asymptotic result, and their own Figure 5 shows exactly this: for the diffuse proposal (s=20), Ẑ_GF2 is visibly biased at K=3000 and badly biased at K=3×10^6 with N=500. The paper is honest in the discussion that the method struggles there, but the theoretical claim in Section 3.3 gives the reader the wrong asymptotic to lean on. This should be fixed, either with a proper bias analysis or a clear restriction of the claims to the Keff≪K concentrated-proposal setting.\n\nAlso: Ẑ_comb's bias is acknowledged but never analyzed, and the empirical evaluation is just the Gaussian running example, with no code or real application. None of these are fatal; the theoretical core holds up.\n\nBottom line: this deserves a serious referee. It's a useful contribution to the MIS/evidence-estimation subfield, and the extended-space perspective is worth taking seriously. The authors need to tighten the bias story for the intractable-setting estimators before the practical claims are fully supported.\n\nBest","headline":"The extended-space representation and modified AIS are the real contributions; the intractable-proposal estimator Ẑ_GF2 has an unproved bias claim that points the wrong way as K grows.","tokens_in":33194,"tokens_out":6519,"would_cite":true,"duration_ms":55415,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The balance heuristic estimator is exactly an importance sampling estimator on an extended space whose target has the same normalising constant, and this representation yields an unbiased modified annealed estimator.","keywords":["balance heuristic","multiple importance sampling","normalising constants","extended-space representation","annealed importance sampling","intractable proposals","Rao-Blackwellized estimator","variance reduction"],"falsifier":"Take the running example with a diffuse marginal proposal ($s=20$) and very large $K$ (for instance $K=3\\times 10^6$) and compare the estimators; the paper's own Figures 5 and 6 show that $\\hat Z_{\\mathrm{GF1}}$ and $\\hat Z_{\\mathrm{GF2}}$ develop high variance or clear bias there, while the balance heuristic loses its cost advantage when $K_{\\mathrm{eff}}$ approaches $K$. The claim would be settled by measuring variance per unit cost of $\\hat Z_{\\mathrm{BH}}$ against $\\hat Z_{\\mathrm{RB}}$ in a regime with $K_{\\mathrm{eff}}\\approx K$.","tokens_in":32148,"feed_emoji":"🎲","tokens_out":8649,"duration_ms":76947,"temperature":0.7,"pith_summary":"This paper revisits the balance heuristic for estimating a normalising constant $Z$ in the setting where the number of available proposals $K$ far exceeds the number of importance points $N$. It establishes that the balance heuristic estimator can be written as an importance sampling estimator on an extended space, with extended target $\\eta_{\\mathrm{BH}}$ whose normalising constant is still $Z$ even though the original target $\\pi$ is not a marginal. On this representation it builds a modified annealed importance sampling algorithm that produces an unbiased estimator $\\hat Z_{T,\\mathrm{mAIS}}$ with no larger variance than the plain balance heuristic. The same extended-space viewpoint is generalised to a framework (Eq. 14) that recovers both the balance heuristic and linear combinations of unbiased estimators, and yields two estimators for the intractable case in which only the joint proposal density $\\bar q(x,l)$ is available. The payoff is that balance-heuristic-style estimates remain accurate at cost $O(N K_{\\mathrm{eff}})$ rather than $O(NK)$ when only a few proposals are actually used.","feed_headline":"Balance heuristic is importance sampling on an extended space","feed_subtitle":"An extended-space view yields unbiased annealed estimates and a route for intractable proposals.","key_machinery":"The object that carries the argument is an extended-space target. The key identity is the representation of $\\hat Z_{\\mathrm{BH}}$ as an importance weight for the joint proposal $\\bar q^{\\otimes N}(x_{1:N},l_{1:N})=\\prod_{n=1}^N q_{l_n}(x_n)\\alpha(l_n)$ when the target is $\\eta_{\\mathrm{BH}}$ of Eq. (8). This is what lets the paper view balance heuristic as a single point in a higher-dimensional space and bridge it to $\\bar q^{\\otimes N}$ by annealed intermediate distributions. The second load-bearing mechanism is the modified annealed importance sampling recursion of Algorithm 2, which keeps the labels $l_{1:N}$ fixed, runs independent annealed chains for each conditional $\\eta_t(dx_n|n,l_{1:N})$, and multiplies the per-chain weights; Theorem 2 shows the resulting estimator is unbiased. In the intractable setting, the general target $\\eta_{\\mathrm{GF}}$ with surrogate functions $\\psi_n$ and $\\rho_n$ plays the same role, allowing the balance-heuristic weighting to be mimicked using only joint evaluations $\\bar q(x,l)$.","core_discovery":"The paper's central claim is that the balance heuristic estimator\n$$\\hat Z_{\\mathrm{BH}} = \\sum_{n=1}^N \\frac{\\tilde\\pi(X_n)}{\\sum_{m=1}^N q_{L_m}(X_n)}, \\qquad (X_n,L_n)\\sim q_{L_n}\\$\\alpha$,$$\nis exactly an importance sampling estimator with a single point on the space $\\{1,\\dots,N\\}\\times \\mathcal{X}^N\\times\\{1,\\dots,K\\}^N$ under the extended target\n$$\\eta_{\\mathrm{BH}}(n,x_{1:N},l_{1:N}) = \\frac{\\pi(x_n)q_{l_n}(x_n)}{\\sum_{m=1}^N q_{l_m}(x_n)}\\,\\$\\alpha$(l_n)\\prod_{m\\neq n} q_{l_m}(x_m)\\$\\alpha$(l_m).$$\nThe normalising constant of $\\eta_{\\mathrm{BH}}$ is $Z$, by construction, even though $\\pi$ cannot be recovered by marginalising any variable. Theorem 2 proves that the modified annealed importance sampling estimator of Algorithm 2 is unbiased for $Z$, and standard AIS theory gives that its variance is no larger than that of $\\hat Z_{\\mathrm{BH}}$. The paper then generalises the construction to $\\eta_{\\mathrm{GF}}(n,x_{1:N},l_{1:N})\\propto \\pi(x_n)\\frac{\\psi_n(x_n)}{\\sum_{m=1}^N\\psi_m(x_n)}\\rho_n\\prod_{m\\neq n}\\bar q(x_m,l_m)$, which contains balance heuristic ($\\psi_n=q_{l_n}$, $\\rho_n=\\alpha(l_n)$) and the combined-estimator scheme ($\\psi_n\\equiv 1$, $\\rho_n=\\nu_{l_n}$) as special cases.","pith_inferences":["If the extended-space representation is correct, the per-point weights of Algorithm 2 could be reused across independent draws of the labels, giving a Rao-Blackwellized version of the modified AIS estimator that the paper does not explore.","The general framework suggests a constructive design rule: any approximation $\\psi_n$ of the unavailable conditional $q_{l_n}$ that makes the denominator $\\sum_m \\psi_m(x)$ track $\\sum_m q_{l_m}(x)$ should inherit the balance heuristic's variance reduction; a natural testable extension is to estimate $\\psi_n$ adaptively from a pilot sample.","A sequential Monte Carlo version of the modified AIS, which the paper flags as nontrivial because resampling can break unbiasedness, would turn balance heuristic into an online particle method; this is an open extension rather than a claim of the paper."],"forward_implications":["For any number of annealing steps $T\\ge 1$, the modified annealed importance sampling estimator $\\hat Z_{T,\\mathrm{mAIS}}$ is unbiased for $Z$ and has variance at most that of the plain balance heuristic estimator (Theorem 2).","Because the $N$ per-point chains in Algorithm 2 are conditionally independent given the labels, the estimator can be computed by $N$ parallel processes, each of cost $O(TN)$, replacing the serial $O(TN^2)$ weight computation of standard AIS.","In the intractable-proposal setting, the estimators $\\hat Z_{\\mathrm{GF1}}$ and $\\hat Z_{\\mathrm{GF2}}$ require only evaluations of the joint density $\\bar q(x,l)$, so they apply when the conditional $q_l(x)$ and label distribution $\\alpha(l)$ are individually unavailable, as with order-induced labels.","The computational cost of balance heuristic is $O(NK_{\\mathrm{eff}})$, which is much less than $O(NK)$ when the effective number of sampled labels $K_{\\mathrm{eff}}$ is small, so balance heuristic remains competitive against Rao-Blackwellized estimation for equal computational cost."],"supporting_citations":[{"why":"Introduces the balance heuristic estimator and its multiple importance sampling weights, the object this paper re-derives on an extended space.","marker":"Veach & Guibas (1995)"},{"why":"Provides the unbiasedness result for multiple importance sampling that Proposition 1 extends to the random-allocation setting.","marker":"Owen & Zhou (2000)"},{"why":"Supplies annealed importance sampling, the variance-reduction scheme the paper adapts to the extended-space target.","marker":"Neal (2001)"},{"why":"Gives the standard importance sampling setup and the normalising constant estimation problem that frames the whole paper.","marker":"Robert & Casella (2013)"},{"why":"Analyses variance differences between balance heuristic and Rao-Blackwellized estimators, referenced in Remark 2 for the case where the lower bound in Theorem 1 vanishes.","marker":"Elvira et al. (2019)"},{"why":"Motivates combining unbiased estimators through effective sample size, which the paper adapts to correlated estimators in the intractable-proposal setting.","marker":"Gramacy et al. (2010)"},{"why":"Gives another example of combining unbiased estimators in sequential Monte Carlo, used as motivation for the linear-combination approach.","marker":"Nguyen et al. (2015)"},{"why":"Provides recent work on linear combinations of unbiased adaptive IS estimators that the paper contrasts with its combination of correlated estimators.","marker":"Owen & Zhou (2019)"},{"why":"Establishes the sequential Monte Carlo sampler machinery that the paper notes could inspire a higher-level particle system for the modified AIS estimator.","marker":"Del Moral et al. (2006)"},{"why":"Identifies the intractable-proposal scenario arising from ordering labels, the main motivating application for Section 3.","marker":"Everitt et al. (2016)"}],"fun_headline_variants":["Balance heuristic is importance sampling in disguise","Extended-space view yields unbiased annealed estimates","Joint proposals handled via extended-space balance","Annealing balance heuristic reduces variance","New representation of balance heuristic enables annealing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the effective number of distinct proposals actually drawn, $K_{\\mathrm{eff}}$, is much smaller than the pool size $K$; the paper states in Section 4 that $K_{\\mathrm{eff}}\\ll K$ is vital, and its own figures show deterioration when the marginal proposal is diffuse or $K$ is huge.","fun_headline_variants_meta":{"raw":{"variants":["Balance heuristic is importance sampling in disguise","Extended-space view yields unbiased annealed estimates","Joint proposals handled via extended-space balance","Annealing balance heuristic reduces variance","New representation of balance heuristic enables annealing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000351,"raw_usage":{"total_tokens":1994,"prompt_tokens":1101,"completion_tokens":893,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":717,"completion_tokens_details":{"reasoning_tokens":842}},"tokens_in":717,"tokens_out":893,"duration_ms":8050,"temperature":1.0,"reasoning_tokens":842,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:44:01.489664+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the running example with a diffuse marginal proposal ($s=20$) and very large $K$ (for instance $K=3\\times 10^6$) and compare the estimators; the paper's own Figures 5 and 6 show that $\\hat Z_{\\mathrm{GF1}}$ and $\\hat Z_{\\mathrm{GF2}}$ develop high variance or clear bias there, while the balance heuristic loses its cost advantage when $K_{\\mathrm{eff}}$ approaches $K$. The claim would be settled by measuring variance per unit cost of $\\hat Z_{\\mathrm{BH}}$ against $\\hat Z_{\\mathrm{RB}}$ in a regime with $K_{\\mathrm{eff}}\\approx K$.","supporting_citations":[{"cited_title":"& Guibas, L","cited_arxiv_id":null,"evidence_quote":"Introduces the balance heuristic estimator and its multiple importance sampling weights, the object this paper re-derives on an extended space."},{"cited_title":"& Zhou, Y","cited_arxiv_id":null,"evidence_quote":"Provides the unbiasedness result for multiple importance sampling that Proposition 1 extends to the random-allocation setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies annealed importance sampling, the variance-reduction scheme the paper adapts to the extended-space target."},{"cited_title":"& Casella, G","cited_arxiv_id":null,"evidence_quote":"Gives the standard importance sampling setup and the normalising constant estimation problem that frames the whole paper."},{"cited_title":", Martino, L","cited_arxiv_id":null,"evidence_quote":"Analyses variance differences between balance heuristic and Rao-Blackwellized estimators, referenced in Remark 2 for the case where the lower bound in Theorem 1 vanishes."},{"cited_title":", Samworth, R","cited_arxiv_id":null,"evidence_quote":"Motivates combining unbiased estimators through effective sample size, which the paper adapts to correlated estimators in the intractable-proposal setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives another example of combining unbiased estimators in sequential Monte Carlo, used as motivation for the linear-combination approach."},{"cited_title":"The square root rule for adaptive importance sampling","cited_arxiv_id":"1901.02976","evidence_quote":"Provides recent work on linear combinations of unbiased adaptive IS estimators that the paper contrasts with its combination of correlated estimators."},{"cited_title":", Doucet, A","cited_arxiv_id":null,"evidence_quote":"Establishes the sequential Monte Carlo sampler machinery that the paper notes could inspire a higher-level particle system for the modified AIS estimator."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Identifies the intractable-proposal scenario arising from ordering labels, the main motivating application for Section 3."}],"review_version":1}