{"id":"0f67f521-595c-4e96-9c2a-f033b6a8fe55","arxiv_id":"1908.06335","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Prune Sampling is a new MCMC method for discrete Bayesian networks that provably converges to the posterior distribution even under determinism, though it trails standard methods on large networks.","lead":"Prune Sampling is a new MCMC method for Bayesian networks that provably converges to the true posterior even when deterministic relationships break standard Gibbs sampling. It is fast on small and medium networks, but slow and less accurate on large ones.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The convergence guarantee rests entirely on exact uniform sampling from the pruned state space; the paper's own fixed-size heuristic breaks that uniformity, so 'always converges' holds only for the idealized enumeration-based algorithm, not for the practical large-BN variant.","rationale":"The mathematical argument for the idealized algorithm is internally coherent: detailed balance is checked termwise for each non-pruned label set Cnp containing both Cx and Cy, and regularity follows because, with positive probability, all positive CPT entries are kept, making every feasible state reachable in one step. I therefore find no flaw in the core reversibility proof as stated. The load-bearing weakness is exactly the one the reader identified: the transition step requires exact uniform sampling over SCnp_x, an operation that is only practical when the pruned state space is small. For large BNs the paper itself proposes a heuristic that breaks uniformity and thus invalidates the proof. Since the paper's headline claim is unqualified ('always converge'), this is a genuine gap between theory and the practical algorithm. The experimental ROC methodology is also ad hoc — the choice of δ and the interpretation of σ_t^2 are not rigorously justified — but this affects performance claims, not the central convergence theorem. The reader's CONDITIONAL verdict already captures this situation: the theoretical result is sound under an explicit oracle assumption, but the paper should qualify the convergence claim, release code/data, and clarify that the heuristic variant has no guarantee. My stress-test does not reveal a reason to move away from CONDITIONAL, so the verdict remains unchanged.","tokens_in":13594,"tokens_out":11188,"duration_ms":125707,"concrete_test":"Implement the exact enumeration version of Prune Sampling on the block-shaped BN of length n=10 used in the paper, and verify that its empirical stationary distribution matches the exact posterior. Then implement the paper's proposed fixed-size V heuristic (e.g., V=50 using random forward sampling to populate V) on the same network, running 100 chains of 100,000 samples each. Compute the average Hellinger distance between the estimated and exact one-variable marginals as a function of chain length. If the heuristic's error plateaus above zero and does not decrease toward the exact algorithm's error, this confirms that the fixed-size heuristic does not inherit the convergence guarantee, validating the concern that the practical large-BN variant is not covered by the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central proof that Prune Sampling is regular and reversible with respect to P depends on the transition step drawing y exactly from U(SCnp_x), the uniform distribution over all feasible states of the pruned network. This requires exhaustive enumeration (and hence counting) of SCnp_x. The paper acknowledges in 'Practical Implementation' that for large BNs this enumeration can be infeasible, and it proposes replacing exact uniformity with random forward sampling into a fixed-size set V, followed by uniform sampling from V. That substitution changes the transition kernel: the proposal mass is no longer 1/|SCnp_x| but 1/|V|, and the detailed-balance computation in Equations (5)-(7) no longer applies because the normalizing constant Z = |SCnp_x| is replaced by an uncontrolled data-dependent quantity. Consequently, the claim that the Markov chain always converges to the desired posterior is proven only for the exact-enumeration oracle, not for the heuristic used when enumeration is too expensive. Moreover, even exact enumeration is not a general polynomial-time procedure: counting feasible states of a pruned deterministic BN is a #P-hard problem in the worst case, so 'exhaustive listing of all solutions of the pruned BN is possible' is an assumption about problem size and pruning effectiveness, not a theorem. The paper itself flags the limitation, but the abstract and conclusion state the convergence guarantee without this essential qualification.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces Prune Sampling, an MCMC inference method for discrete Bayesian networks with deterministic relations. At each step the algorithm prunes CPT entries around the current state, enumerates all feasible states of the pruned network, and draws the next state uniformly. The authors prove that the resulting Markov chain is regular and reversible with respect to the posterior, and they compare accuracy, rate of convergence, and runtime with Gibbs and Metropolis sampling on benchmark networks. They report that Prune Sampling converges even where Gibbs fails, but is generally less accurate and slower except on small and medium networks.","tokens_in":13865,"tokens_out":10517,"duration_ms":100905,"significance":"If the convergence guarantee holds as stated, Prune Sampling is a valuable addition to approximate inference in deterministic BNs, avoiding the memory-intensive translation to Markov logic networks used by MC-SAT. The paper gives a self-contained reversibility proof and a comparison on standard benchmarks. However, the proof relies on an exact enumeration oracle whose feasibility is not guaranteed in general, and the paper's own heuristic for large networks invalidates the proof. The rate-of-convergence extrapolation is also heuristic. The central idea is sound and the paper is a reasonable first step, but the advertised universality of the convergence claim needs qualification before the result can be taken at face value.","major_comments":[{"comment":"The convergence proof assumes that the next state is drawn exactly from U(SCnp_x), the uniform distribution over all feasible states of the pruned network. In the section on sampling from the pruned network, the paper proposes for large BNs to replace this exact draw by first using random forward sampling to construct a fixed-size set V and then sampling uniformly from V. This heuristic does not produce a uniform distribution over SCnp_x, so the transition probability is no longer of the form in Eq. (5) and the detailed-balance computation in Eq. (7) no longer applies. The claim in the abstract and conclusion that 'Markov chains created by Prune Sampling always converge to the desired posterior distribution' is therefore proven only for the exact-enumeration algorithm, not for the heuristic recommended for large networks. The authors should restrict the convergence claim explicitly to the exact version or provide a separate analysis of the heuristic.","section":"Practical Implementation; Eq. (5)-(7)"},{"comment":"Even the exact-enumeration step is not guaranteed to be tractable: listing all feasible states of a pruned BN is a #P-hard counting problem in general. The statement that 'the exhaustive listing of all solutions of the pruned BN is possible' is an empirical assumption about the instances and the effect of pruning, not a theorem. Consequently, the 'always converges' claim in the abstract should be qualified: the Markov chain converges whenever the exact uniform draw can be implemented, but the method as a whole is not a polynomial-time inference algorithm and may be infeasible for large or highly connected networks. This does not invalidate the Markov-chain theory, but it materially narrows the scope of the central claim as advertised.","section":"Practical Implementation, 'Sampling from the pruned network'"},{"comment":"The proof writes P(x) for the product over CPT entries and ends with 'where Z = |SCnp_{x,y},h|'. This is confusing and technically misleading: P was previously introduced as the posterior probability distribution, whose normalizer is the sum over all feasible states of the product, not the cardinality of the pruned state space. The detailed-balance computation is valid if P is read as the unnormalized product measure, because reversibility with an unnormalized measure implies stationarity of the normalized measure. Please rewrite the proof to explicitly distinguish the unnormalized product from the normalized posterior and remove the incorrect identification Z = |SCnp|.","section":"Argument for a reversible Markov chain, Eq. (7)"},{"comment":"The procedure to estimate α, the proportionality constant of the rate of convergence, relies on fitting g(t) = σ_t^2 sqrt(t) = α(1 + β t^{-δ}) and states 'We learn how to choose δ by doing.' No concrete fitting criterion, search grid, or model selection rule is given, and no goodness-of-fit or sensitivity results are reported. Since Table 2 and the runtime comparisons depend on these α values, the ROC characterization is not reproducible from the description. The authors should specify an automated fitting procedure (for example, profile likelihood or least squares over a range of δ with a stated selection rule) or present the ROC claim as an approximation with explicit caveats.","section":"Rate of convergence"}],"minor_comments":[{"comment":"The quantity σ_t^2 is defined as ⟨y_t^2⟩ − ⟨y_t⟩^2, which is a variance, but the text repeatedly calls it the standard deviation; please correct the terminology.","section":"Rate of convergence"},{"comment":"In the final paragraph, 'uniformly sampling from the entire sample space' should read 'uniformly sampling from the entire state space'.","section":"Conclusion"},{"comment":"The abstract describes Prune Sampling as 'a competitive method for all types of small and medium sized BNs', but Figure 5 shows that Prune Sampling consistently has a higher average Hellinger distance than Gibbs and Metropolis on all networks where those methods converge. The claim should be qualified as competitive in runtime, not in overall accuracy.","section":"Abstract and Conclusion"},{"comment":"The sentence 'And SCnp_x exist of two feasible states' should read 'consists of two feasible states'.","section":"Example 3"}],"recommendation":"major_revision","confidential_remarks":"The central reversibility proof is essentially correct but the presentation conflates the unnormalized product measure with the normalized posterior, and the paper's practical heuristic for large networks is not covered by the proof. The rate-of-convergence extrapolation is the weakest experimental element; the fitting procedure for δ is too underspecified for a journal publication. The novelty is acceptable: the method is a BN-specific variant of MC-SAT, and the authors acknowledge the connection. I would support publication after the convergence claim is properly scoped and the experimental methodology is tightened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nRead the Prune Sampling paper. The core idea is a BN-native version of MC-SAT's random pruning: around each state, delete CPT entries with probability equal to one minus their value, then sample uniformly from states consistent with the surviving entries. The contribution is the proof that this chain is regular and reversible with respect to the target distribution, giving a sound MCMC method for deterministic BNs where Gibbs can get stuck. The proof is essentially correct. There is a confusing 1/Z in the detailed balance calculation that is set equal to the size of the pruned state space; it is superfluous and cancels, so it does not damage the argument.\n\nWhere the paper is honest: the guarantee rests on exhaustive enumeration of the pruned state space, and the authors admit in the Practical Implementation section that for large networks this becomes infeasible. They propose a fixed-size heuristic (random forward sampling into a set V) that breaks uniformity and therefore loses the theoretical guarantee. The abstract and conclusion still say the chain 'always converges' without this qualification, which is an overstatement. The proof applies to the exact-enumeration algorithm, not the heuristic. That said, the experiments use the exact version, so what is tested is what is proven.\n\nThe experimental section is the weaker half. No code or data is released, the ROC analysis fits an auxiliary expansion with free parameters alpha, beta, delta to short runs and extrapolates, and the Hellinger distance formula is ambiguous. Error bars are absent. These problems make the accuracy and speed comparisons suggestive rather than definitive. They do not touch the correctness proof.\n\nThe citation pattern looks fine: MC-SAT is credited clearly, and the relevant sampling literature is present.\n\nBottom line: this is a modest but real contribution. A serious referee should look at it, mainly to check the reversibility proof (which, as far as I can tell, holds) and to push for a qualified abstract and released code. Not a game-changer, but not a desk reject.\n\nBest,\n[You]","headline":"Sound proof for an exact-enumeration MCMC sampler for deterministic BNs; the 'always converges' claim needs the enumeration assumption stated, and the experiments are rougher than the theory.","tokens_in":14379,"tokens_out":3962,"would_cite":true,"duration_ms":38867,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J22","62F15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Prune Sampling guarantees MCMC convergence to the correct posterior for discrete Bayesian networks, including deterministic ones where Gibbs sampling gets stuck.","keywords":["Prune Sampling","Markov chain Monte Carlo","Bayesian networks","deterministic relations","detailed balance","approximate inference","Gibbs sampling","convergence"],"falsifier":"Build the deterministic two-node network from Example 1, run Prune Sampling with exact enumeration for 10,000 iterations, and verify the empirical frequency of $A=1$ approaches $0.5$; if it does not, detailed balance fails, and the same test with approximate uniform sampling on the block-shaped network should reveal whether the chain is trapped.","tokens_in":13400,"feed_emoji":"🎲","tokens_out":4180,"duration_ms":37414,"temperature":0.7,"pith_summary":"The paper introduces Prune Sampling, a Markov chain Monte Carlo method for discrete Bayesian networks, and claims it always converges to the true posterior even when the network has deterministic relations. The key step is to randomly prune conditional probability table entries around the current state, then uniformly sample the next state from the small set of feasible states of the pruned network. The authors prove the resulting chain is regular and reversible with respect to the posterior, so it has that posterior as its unique stationary distribution. They show experimentally that on small and medium networks the method is competitive, and on deterministic or block-shaped networks it recovers the correct marginals where Gibbs sampling fails.","feed_headline":"New sampler converges to correct posterior where Gibbs fails","feed_subtitle":"Prune Sampling randomly shrinks the network each step and samples uniformly, proving convergence even with deterministic relations.","key_machinery":"The central object is the pruning procedure around a state $x$: each CPT entry not used by $x$ is deleted with probability $1-c$, where $c$ is the entry's probability, and the remaining entries define a pruned Bayesian network. The next state is drawn uniformly from the feasible states of that pruned network. This random, state-dependent restriction of the full network keeps the transition space small enough to enumerate, while the detailed-balance calculation shows the chain is reversible with respect to $P$.","core_discovery":"For any discrete Bayesian network, the paper claims, the Prune Sampling Markov chain is regular (every state can reach every other state in a fixed number of steps with positive probability) and reversible with respect to the posterior distribution $P$. The proof constructs, for each ordered pair of states $x$ and $y$, the set of pruned-label collections that allow a transition, and verifies detailed balance term-by-term: $P(x)R_h(x \\to y) = P(y)R_h(y \\to x)$, where $R_h$ combines the pruning probabilities of CPT entries with uniform sampling over the pruned network's feasible states. From regularity and reversibility it follows that $P$ is the unique stationary distribution, so the chain converges to the correct posterior, unlike Gibbs sampling when deterministic CPT zeros trap the chain in a subset of states.","pith_inferences":["A natural testable extension is a variant that replaces exact uniform enumeration with a provably near-uniform sampler (for example, a coupling or bounded-time enumeration) and checks whether the detailed-balance error remains small enough for useful convergence.","The proof treats the pruned network as a deterministic function of the labels kept; one could generalise the scheme to continuous or mixed distributions by pruning density regions rather than table entries, though the uniformity and reversibility arguments would need reworking.","The comparison suggests the method's niche is exactly the regime where Gibbs breaks: deterministic small and medium networks; a targeted benchmark suite of such networks with exact marginals would sharpen the practical guidance."],"forward_implications":["On deterministic or block-shaped BNs where Gibbs sampling cannot leave a subset of the state space, Prune Sampling still visits the whole state space and estimates marginals correctly.","For small and medium sized BNs, Prune Sampling reaches a given variance threshold faster in wall-clock time than Gibbs or Metropolis sampling.","On large BNs, the required exhaustive enumeration of feasible states of the pruned network makes Prune Sampling time-intensive and less accurate than standard methods.","The rate of convergence of the method is $O(t^{-1/2})$ with a proportionality constant larger than Gibbs and Metropolis, so it converges more slowly per sample on networks where those methods work."],"supporting_citations":[{"why":"Supplies the Markov chain theory (regular, reversible, unique stationary distribution) used to frame and prove convergence.","marker":"[4]"},{"why":"Provides the MC-SAT algorithm whose random sample space construction Prune Sampling adapts to BNs, and whose soundness is cited as inspiration.","marker":"[5]"},{"why":"Documents that Gibbs sampling can get trapped on deterministic BNs, the problem Prune Sampling aims to solve.","marker":"[8]"},{"why":"Supplies SampleSearch, an importance-sampling alternative in deterministic models, consulted as related work.","marker":"[6]"}],"fun_headline_variants":["Prune Sampling always converges to correct posterior, even for deterministic BNs","Prune Sampling: a MCMC method that flips Gibbs' failure into success","Prune Sampling converges where Gibbs sampling can't","New MCMC: prune the network, sample uniformly, converge"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The convergence proof assumes the algorithm can always enumerate every feasible state of the randomly pruned network and pick one uniformly; when the pruned state space is too large for exhaustive enumeration, as the paper concedes for large networks, the suggested approximation breaks the uniformity and the convergence guarantee no longer applies.","fun_headline_variants_meta":{"raw":{"variants":["Prune Sampling always converges to correct posterior, even for deterministic BNs","Prune Sampling: a MCMC method that flips Gibbs' failure into success","Prune Sampling converges where Gibbs sampling can't","New MCMC: prune the network, sample uniformly, converge"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001183,"raw_usage":{"total_tokens":4867,"prompt_tokens":907,"completion_tokens":3960,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":3886}},"tokens_in":523,"tokens_out":3960,"duration_ms":26368,"temperature":1.0,"reasoning_tokens":3886,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:48:51.606360+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build the deterministic two-node network from Example 1, run Prune Sampling with exact enumeration for 10,000 iterations, and verify the empirical frequency of $A=1$ approaches $0.5$; if it does not, detailed balance fails, and the same test with approximate uniform sampling on the block-shaped network should reveal whether the chain is trapped.","supporting_citations":[{"cited_title":"Sound and efficient inference with probabilistic and deterministic dependencies","cited_arxiv_id":null,"evidence_quote":"Provides the MC-SAT algorithm whose random sample space construction Prune Sampling adapts to BNs, and whose soundness is cited as inspiration."},{"cited_title":"Giss: Combining gibbs sampling and samplesearch for inference in mixed probabilistic and deter- ministic graphical models","cited_arxiv_id":null,"evidence_quote":"Documents that Gibbs sampling can get trapped on deterministic BNs, the problem Prune Sampling aims to solve."},{"cited_title":"Samplesearch: Importance sampling in presence of determin- ism","cited_arxiv_id":null,"evidence_quote":"Supplies SampleSearch, an importance-sampling alternative in deterministic models, consulted as related work."}],"review_version":1}