acceptodds
Under review as a conference paper at ICLR 2027

Approximating Inconsistency at Scale in Probabilistic Dependency Graphs

Abstract

We deliver significantly more performant algorithms and implementations for approximating the inconsistency of probabilistic dependency graphs (PDGs), a general problem that unifies and interpolates between many important problems in probabilistic modeling and machine learning. Previous methods are either unreliable (first-order optimizers with ad-hoc constraint penalties) or prohibitively expensive (second-order optimizers and convex solvers) for all but the smallest of PDGs. We provide the first sampling-based approach for this problem, combining a score-function gradient estimator with Rao-Blackwellization to optimize over parameterized Bayesian networks. Empirically, our method scales to substantially larger and more complex PDGs than existing approaches can handle. Our approach also naturally permits variational approximations of inconsistency, allowing the choice of Bayesian-network structure to trade computational efficiency for the tightness of the resulting upper bound.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
probabilistic graphical models, probabilistic dependency graphs, variational inference, Bayesian networks, stochastic optimization, Monte Carlo methods, Rao–Blackwellization, score-function gradient estimation

Reviews

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

This paper studies the computational problem of approximating inconsistency in probabilistic dependency graphs (PDGs), which provide a general framework for representing potentially incompatible probabilistic beliefs. Existing approaches based on convex optimization or gradient methods over calibrated cluster marginals can become computationally expensive as the size and treewidth of the underlying graphical structure increase.

The authors propose a sampling-based approach that optimizes over parameterized Bayesian networks. They derive a score-function expression for the gradient of the incompatibility objective and develop two practical gradient estimators: a plug-in estimator based on empirical conditional probabilities and a Rao--Blackwellization-based estimator exploiting the structure of the candidate Bayesian network. They also introduce source-coverage regularization to mitigate premature concentration during optimization.

Critical strengths
  1. The paper addresses a well-motivated computational bottleneck in probabilistic dependency graphs. Replacing optimization over calibrated cluster marginals with sampling-based optimization over Bayesian networks is a natural and practically useful direction. The resulting approach makes it possible to handle instances for which existing methods become computationally prohibitive.

  2. The methodological development is technically interesting. In particular, the score-function gradient identity provides a principled basis for stochastic optimization, while the Rao--Blackwellization-based estimator exploits graphical structure to improve conditional-probability estimation. The analysis carefully distinguishes variance reduction for conditional estimates from properties of the complete gradient estimator, which is an important technical point.

  3. The variational interpretation is a useful aspect of the framework. Restricting optimization to a chosen Bayesian-network family provides a clear trade-off between computational efficiency and approximation quality. This extends the applicability of inconsistency optimization beyond the setting in which an unrestricted optimum can be represented efficiently.

Critical weaknesses
  1. The empirical evaluation is based primarily on synthetically generated or synthetically perturbed probabilistic beliefs. While these experiments are appropriate for studying scalability and optimization behavior, a demonstration involving a naturally occurring collection of conflicting probabilistic beliefs would strengthen the practical motivation and applicability of the approach.

  2. The quality of the variational approximation depends on the selected Bayesian-network structure. The experiments generally use the underlying generating network as the candidate structure, which provides a reasonable setting for controlled comparisons. However, this leaves open how performance changes when the chosen structure is substantially misspecified or significantly more restrictive than the structure required for a tight approximation.

Questions for authors
  1. How sensitive is the proposed optimization procedure to the choice of the candidate Bayesian-network structure? In particular, have the authors investigated settings where the chosen variational family does not contain a good approximation to the unrestricted inconsistency minimizer? Such experiments would help clarify the practical trade-off between computational savings and approximation quality.

  2. The Rao--Blackwellization-based estimator generally performs well in the experiments, but its variance reduction guarantee applies to the estimated conditional probabilities rather than directly to the full gradient. Can the authors provide further intuition or empirical evidence characterizing the regimes in which this advantage is most pronounced?

1 comment

We are sincerely grateful for the thoughtful and encouraging review!

... a demonstration involving a naturally occurring collection of conflicting probabilistic beliefs would strengthen the practical motivation and applicability of the approach.

We agree, and would strongly prefer to find a realistic dataset on which to test our approaches. While PDGs are highly expressive, we are not aware of any established PDG datasets. With the notable exception of graphical models (e.g., BNs and factor graphs) the published conversions of other objects to PDGs remain, for now, mathematical constructions. We have some ideas for where to go next—we think gene regulatory networks are more naturally modeled with PDGs, for instance—but our translations would require separate validation.

In principle, there are many natural settings where our approach might be applied: sensor fusion, opinion aggregation, combining and training machine learning models, to name a few. Making each of these work would require either a clever way of cobbling together existing data, or non-trivial technical innovations (e.g., adaptations to handle continuous variables). Ultimately, we concluded that assembling a dataset of naturally occurring PDGs that have conflict would be of independent interest, and out of scope for the present paper. Perhaps the existence of a practical inference algorithm will help incentivize such efforts.

How sensitive is the proposed optimization procedure to the choice of the candidate Bayesian-network structure?

We agree this trade-off deserves a more direct evaluation. Appendix F.4 now experiments with varied choices of BN structure on four positive-incompatibility PDGs from Section 5.2. Starting with cluster-tree BN families (Appendix B.4), which have no representation gap, we progressively remove edges, ending with the fully independent family (all variables have no parents). We find, as expected, that larger, more expressive families generally run slower but attain lower incompatibility. However, the Insurance network results also show us that very large parameterizations can sometimes be harder to optimize, and so nonetheless attain higher incompatibility than less expressive parameterizations under the same number of iterations.

It is also important to note, however, that the choice of a less expressive BN family need not only be motivated by tractability, but may also encode known independence constraints specified by the modeler (in the structure A0\mathcal A_0 of the PDG). In this case, the restricted optimum measures the true irreducible inconsistency of the PDG beliefs, while the unrestricted optimum provides a lower bound by relaxing known constraints. See our response to reviewer sX1r for an extensive discussion on this point, including an example, and an argument that our positive incompatibility PDGs in section 5.2 naturally admit this interpretation.

The Rao-Blackwellization-based estimator generally performs well in the experiments, but its variance reduction guarantee applies to the estimated conditional probabilities rather than directly to the full gradient. Can the authors provide further intuition or empirical evidence characterizing the regimes in which this advantage is most pronounced?

Although the variance guarantee does not extend to the full gradient, our experiments show that RB improves both the bias and variance of gradient-estimates in practice. In our second reply to reviewer CjNb, we report results on eight PDGs at several sample sizes, comparing both estimators against exact gradients at the same parameter values throughout training. We report each estimator’s mean squared L2 gradient error over 100k iterations, together with the mean and median per-iteration percentage reduction achieved by RB.

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

This submission proposes an efficient method for approximating the inconsistency of probabilistic dependency graphs (PDGs) over discrete random variables. It represents the joint distribution with a candidate parametric Bayesian network (BN) and minimizes PDG incompatibility using gradient-based methods. To reduce the cost of exact gradients, the authors derive sampling-based plug-in and Rao–Blackwellized gradient estimators. They evaluate the method on PDGs constructed from randomly generated and existing benchmark BNs.

Critical strengths
  1. To my knowledge, the proposed framework seems novel. Although I am unfamiliar with research on PDGs, this submission seems to propose a substantially different approach compared to existing work such as Richardson et al. (2023).

  2. It seems that the proposed method is appropriately motivated and formulated. Computational cost is a convincing concern in estimating PDG inconsistency, and this approach seems a suitable way to address it. I see no major flaws in the main gradient derivations through Section 4.

Critical weaknesses
  1. A major concern is that modeling \mu_\theta requires a factorization determined by the structure of the candidate BN. This reduces the search space efficiently but may overestimate PDG inconsistency if the candidate family cannot adequately represent the joint distribution that minimizes the incompatibility. Relatedly, all experiments in Section 5 use candidate BNs with the same structures as the base BNs. This provides favorable information for structure selection and leaves effectiveness under unknown or inaccurate structures untested. To my understanding, Richardson et al. (2023) does not require assuming a factorization according to a candidate BN structure, and this difference would also be important when interpreting the performance comparison in Section 5.1. Perhaps these issues could be addressed by combining the proposed method with some procedure for estimating the structure of the candidate BN. The manuscript also identifies adaptation of the candidate structure as future work, but no concrete procedure or experimental verification is provided.

  2. It seems that the experimental comparison with existing work is insufficient. Richardson et al. (2023) is directly relevant, and I understand that the ''convex baseline'' and ''cluster-tree Adam'' mentioned in Section 5.1 correspond to methods proposed in that paper. However, under the settings used here, most runs are reported not to have completed because of computational resource limits, numerical issues, or other reasons. Such outcomes may occur because the problem sizes and execution conditions differ from those in the experiments of Richardson et al. (2023). However, although failure counts are reported, it is still unclear which sizes or structures cause failures or whether these also occur under the settings examined by Richardson et al. (2023). Even for the 74 cases for which the convex baseline returned results, no comparison of the attained incompatibility values is reported. I believe that inconsistency estimates and computation times should be evaluated in detail under matched conditions for settings similar to those examined by Richardson et al. (2023).

Questions for authors
  • How do inconsistency estimates and computational costs change when the candidate BN structures discussed in Section 4.2 and Appendix C differ from the structures of the corresponding base BNs?
  • Do the convex baseline and cluster-tree Adam also fail at the sizes and settings examined by Richardson et al. (2023)? If so, is this consistent with the results of Richardson et al. (2023)?
  • Can you report objective values and computation times for the 74 cases where the convex baseline returned results? Why are these omitted from Figure 1? Can the results of cluster-tree Adam at early termination also be evaluated?
  • Why was exact JAX run on a CPU and the proposed method on a GPU? Did this difference affect the comparison under the 25-minute time limit in Section 5.1?
  • How is the coverage regularization gradient estimated? Since the term covers all possible s, how are source configurations absent from the sample (i.e., \widehat c(s)=0) handled?
  • Are there experimental results for the same benchmark BNs as in Section 5.2 under a setting with no additional noise?
6 comments

Thank you for the thoughtful review!

Weakness 1

"To my understanding, Richardson et al. (2023) does not require assuming a factorization according to a candidate BN structure, ..."

This is true. Richardson et al. (2023) design algorithms optimizing calibrated marginals over a cluster-tree decomposition of the PDG. This approach requires no further "expert-guided" structure design. The incompatibility loss is also convex over calibrated marginals, leading perhaps to improved convergence.

Our approach inherits many of these strengths, while addressing some pain points. As we explain in Appendix C, absent a more informed BN structure, we may always simply select a BN encoding precisely the independencies implied by the cluster-tree decomposition (Lauritzen 1996).

Although the finite-logit incompatibility objective is no longer convex over BNs, it has no suboptimal critical points, as shown in Appendix B.4, and so still lends itself to gradient descent. Moreover, valid (i.e., calibrated) cluster-tree marginals come with constraints (i.e., overlapping clusters must agree), significantly complicating optimization compared to BN logits which are "calibrated" by design and always specify a distribution. Avoiding such constrained optimization is an important reason for our algorithms' improved performance over baselines.

This reduces the search space efficiently but may overestimate PDG inconsistency if the candidate family cannot adequately represent the joint distribution that minimizes the incompatibility.

This is also true, and a general feature of variational methods. Note, however, that restricted candidate families need not be motivated purely by approximation, but can also encode real structural beliefs. For example, let XX and YY be independent coin tosses conducted in separate rooms, and ZZ a noisy indicator of whether they agree. The natural BN structure here is X→Z←YX \rightarrow Z \leftarrow Y. Separate experiments may provide noisy estimates of P(X)P(X), P(Z∣X,Y)P(Z|X,Y), and P(Y∣X,Z)P(Y|X,Z), forming a PDG. Each edge is non-trivial, with no spurious parents under our BN's implied independencies. The cluster-tree BN, however, adds the edge X→YX\rightarrow Y, and indeed if P(Y∣X,Z)P(Y|X,Z) and P(Z∣X,Y)P(Z|X,Y) are noisily estimated, lower incompatibility may be attained by correlating XX and YY, despite our physical system having no mechanism to produce this correlation.

Here, the BN's independence constraints may already be specified by the modeler (in the structure A0\mathcal A_0 of the PDG), and not merely be variational approximation—in which case the restricted optimum measures the true irreducible inconsistency of our beliefs, while the unrestricted optimum provides a lower bound by relaxing a known independence constraint.

Our positive incompatibility experiments admit this interpretation. The PDG cpds represent noisy estimates from separate studies, and the given BN family encodes an expert-informed understanding of independencies in the system (e.g., earthquake occurrences are independent of burglaries). As above, due to sampling error, the incompatibility-minimizing joint distribution may exploit correlations that are impossible under the known BN structure. Optimizing within that family can be viewed either as a variational approximation of the cluster tree BN optimum or as computing inconsistency with respect to various informed independence constraints.

Still, we agree that studying the runtime–incompatibility tradeoff across variational families would be helpful. Preliminary experiments appear in the new Appendix F.4; as expected, smaller families process faster but leave higher inconsistency estimates. Cluster-tree BNs also attain lower incompatibility than base BN families, either due to greater expressiveness or an easier to navigate loss-landscape due to over-parameterization.

Weakness 2

In Appendix F.3.1-2, we perform evaluations on 100 synthetic PDGs generated using the written protocol for Richardson et al. (2023)'s Synthetic Experiment 2, and present baseline performance in our section 5.1 experiments in more detail. The results replicate those of Richardson et al. (2023), and affirm our existing conclusions. See Appendix for details.

Questions

Why Exact JAX on CPU: The exact algorithm computes exact marginals via variable elimination, which is less amenable to GPU parallelization than the sampling algorithms which estimate these marginals via JAX bincount operations. Even on small PDGs, exact JAX on GPU was about 8x slower per iteration and took 30x longer to compile.

Regularization when c^(s)=0\hat{c}(s)=0: Coverage regularization has 0 gradient when source configurations are absent; however, since we use a uniform initialization and gradient changes are small, the regularizer ideally prevents such collapses.

Zero-inc experiments for benchmark BNs: We have not run these yet, but agree they would be informative. We will include these results by the rebuttals deadline.

Thank you for your response.

Weakness 1. I understand that one can select an appropriate BN using a cluster-tree decomposition without a more informed BN structure. I also appreciate the evaluation in Appendix F.4. However, the large-scale experiments in Section 5 still use candidate BNs with the same structures as the base BNs, and evaluation remains limited when this information is unavailable. In fact, Appendix F.4 considers only four relatively small base BNs and reports a substantial increase in computational cost for Insurance when using a cluster-tree BN. Thus, it remains unclear how low an incompatibility can be achieved under the specified time and memory constraints in large-scale settings without using information from the base BN. It is also unclear whether the proposed method offers advantages over the methods of Richardson et al. (2023) under these conditions. Since scalability would be central to this submission, I think this issue needs more careful evaluation.

Weakness 2. I see Appendix F.3.1 reports the objective values attained by existing methods and their computation times, and Appendix F.3.2 evaluates the methods under settings similar to those of Richardson et al. (2023). These additions largely resolve my initial concerns. Separately, I note that convex optimization attains lower incompatibility than the sampling methods in all cases where it returns results. This makes it important to establish whether the proposed method offers advantages under the conditions discussed in Weakness 1.

JAX on CPU. I understand the reason for running exact JAX on a CPU. In my experience, an advantage for CPUs on small-scale problems does not necessarily generalize directly to large-scale problems. A somewhat more careful discussion may be helpful.

Zero-inc experiments. Thank you for considering these experiments. To my understanding, evaluation without added noise provides a clearer criterion for judging the success of optimization. I think these results would be particularly useful for evaluating large-scale settings using cluster-tree BNs.

Thank you for continuing to engage and push on these points. Your concerns are legitimate, but we believe we have all the pieces needed to address them satisfactorily.

Weakness 1. It seems to us that our primary point of divergence is whether or not it makes sense to supply a known BN structure to the algorithm. We argue that settings in which some qualitative structure is available are both common and already required for efficient Bayesian inference, even before we add the extra complexities of partial and conflicting information imported by the PDG formalism. We remind the reviewer that PDGs themselves can contain this structure. So, while one interpretation of the experiments of 5.1 are “leaking” a good (although perhaps suboptimal) structure, we can also view this as perfectly legitimate information already present in the inference problem.

Thank you for pushing here; at the very least, we agree that this should be flagged more clearly, and we will modify the introduction appropriately.

When it comes to the variational interpretation:

I also appreciate the evaluation in Appendix F.4. However, the large-scale experiments in Section 5 still use candidate BNs with the same structures as the base BNs, and evaluation remains limited when this information is unavailable. In fact, Appendix F.4 considers only four relatively small base BNs and reports a substantial increase in computational cost for Insurance when using a cluster-tree BN.

The small scale of these F.4 experiments was simply to test if this methodology would be convincing to you before investing too much compute. Even when no structural information is available, and we operate on the entire cluster tree BN, our previous experience suggests that our sampling-based approaches still offer significant benefits over alternative approaches. Observe in Figures 8 and 9, for the cluster-tree BN families (indicated by stars), that the exact JAX gradient method is many orders of magnitude slower, and ultimately attains higher incompatibility, than our sampling-based approaches—even when the sampling-based approaches make no structural assumptions. We are currently running more comprehensive zero-inc bnlearn experiments, which we will post at the end of the reviewing window. Nevertheless, PDG inference remains NP-hard, and the representation size of any exact representation of the optimal underlying distribution will, in the end, grow exponentially in the number of variables. This is unavoidable. Yet our method provides natural variational levers for easing this burden.

One option for forming the BN family in this setting is to start with the cluster-tree BN and use some procedure, random or heuristic, to incrementally remove edges until you are in a regime that is tractable for you. In practice, one could even experiment with multiple tractable BN families to search for ones which better resolve inconsistency, and perhaps combine elements from ones that perform well (e.g., use an evolutionary algorithm with our algorithm’s achieved incompatibility as the fitness criterion). In cases where there is access to joint samples of all the variables, structure learning methods like the PC algorithm could also be used.

The experiments currently running use the first (cluster-tree pruning) approach, but if time permits, we could also provide experiments using the structure learning approach. Are there any particular approaches to choosing the BN family that you would find helpful to see results for?

Weakness 2. The reviewer is correct: convex optimization does attain the best results among all approaches when it returns results, as, by construction, the solver can terminate only when it computes with strong accuracy the optimum of the given convex optimization problem. Unfortunately, such approaches do not scale, neither in memory nor computation time, and leave us with no way to estimate inconsistency of PDGs with larger scales. We agree that this necessitates testing on larger PDGs than the solver can handle. Note, however, that already the solver fails on two of the small-scale PDGs in our pilot study (Appendix F.4, lower plots of Figure 8, with PDGs built by augmenting the Insurance and Alarm BNs). We will get back to you with preliminary results at a larger scale soon.

JAX on CPU. Your point that CPU advantage on small problems need not generalize to larger ones is well-taken. In our case, we have experimented with both CPU and GPU at multiple scales, and at even moderately large scales, the compilation time for the GPU approach explodes, whereas the compilation time of CPU remains tractable over a larger range before also becoming prohibitive. We will include a discussion of this in the paper. Thank you for raising this potential issue explicitly.

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

This paper tackles the problem of estimating the inconsistency of a probabilistic dependency graph (PDG). It does so by restricting the optimization problem that defines the inconsistency to a parameterized bayesian network. The main contribution is the derivation of 2 estimators for the gradient of the incompatibility (the function we are optimizing) that can be used with standard optimization algorithms. The estimators differ in how they approximate intractable conditional probabilities needed to compute/estimate the gradient. Experiments on synthetic PDGs show the proposed methods scales substantially better than previous approaches.

Critical strengths

Reconciling incompatible conditional beliefs into a coherent joint is a worthwhile problem and the method addresses a clear computational obstacle: gradient based optimization requires the evaluation of intractable conditional probabilities. Estimating these conditionals from forward samples provides a practical route to stochastic optimization and the derivation appears sound.

The experiments compare the proposed methods with exact-gradient optimization within the same BN family. They show that the sampling methods reduce incompatibility quickly and remain usable on larger instances where exact-gradient updates become too expensive. The comparisons between plug-in and Rao-Blackwellized (RB), with and without coverage regularization, also give useful evidence of their practical benefits.

Critical weaknesses

Every candidate BN has the same factorization as the BN used to generate the PDG. While this is a reasonable setting for evaluating optimization, it does not test the advertised trade-off between BN expressivity and efficiency when a more restrictive structure is chosen.

The comparison with exact-gradient optimization shows that the estimators work in practice, but their finite-sample accuracy is not directly evaluated. This is a minor concer and easily remedied.

Questions for authors

What happens when the candidate BN imposes stronger independence assumptions than the generating graph? How much computation is saved and how does this affect the attained incompatibility?

Can you shed light on why RB achieves lower residual losses than plug-in? Direct comparisons with exact gradients at fixed parameter values could show for example whether RB reduces gradient bias.

3 comments

We thank the reviewer for their fair and accurate review.

Every candidate BN has the same factorization as the BN used to generate the PDG. While this is a reasonable setting for evaluating optimization, it does not test the advertised trade-off between BN expressivity and efficiency when a more restrictive structure is chosen.

The reviewer raises a good point, and we are thankful for the opportunity to revise the paper to address it more directly. We raise two points that are somewhat in tension. On one hand, for the noisy beliefs in our experiments, the base BN may not even be ideal for optimization: a richer family may reconcile sampling noise through correlations excluded by the generating BN. On the other hand, these exclusions may encode genuine structural knowledge and be a key part of the data of the PDG, in which case the restricted optimum may be significant in its own right, a possibility discussed extensively in our response to reviewer sX1r.

Ultimately, if the BN family is used as a variational approximation, the exact point on the trade-off is a matter of pragmatics. We have added some preliminary experiments to the paper (Appendix F.4; described below) which demonstrate the advertised trade-off more quantitatively, in case this helps practitioners make the decision. We welcome the opportunity to add a more comprehensive version of this experiment to the paper.

The comparison with exact-gradient optimization shows that the estimators work in practice, but their finite-sample accuracy is not directly evaluated. This is a minor concern and easily remedied.

Sample size is certainly another important lever (in addition to the choice of BN structure) that trades off accuracy for efficiency. Throughout the course of this work, we have experimented a lot with sample sizes. At one point, adaptively doubling sample sizes was a core part of the proposal—but in the present submission, we have simplified to the core part of the algorithm that most reliably delivers the best performance, under a fixed sample size large enough to handle the PDGs in our dev set.

Regarding finite-sample accuracy, we have strengthened Lemma 1 with an explicit finite-sample bound on the plug-in gradient bias (see Appendix D.2). Under the stated positivity assumptions,∥Eg^N−∇I∥∞≤1N∑aβaKSa(KTa−1)\Vert\mathbb{E}\widehat g_N-\nabla I\Vert_\infty\le\frac{1}{N}\sum_a\beta_aK_{S_a}(K_{T_a}-1)where KSaK_{S_a} and KTaK_{T_a} count source and target assignments. Crucially, the constant is independent of the smallest candidate probability, so it does not diverge as candidate probabilities become small. This establishes O(1/N)O(1/N) bias.

Although this bound applies only to the plug-in estimator, preliminary comparisons against exact gradients on three positive-inconsistency PDGs and one zero-inconsistency PDG confirm approximately 1/N1/N decay in gradient bias and MSE for both plug-in and RB. If there are additional experimental comparisons on this front that would be helpful to see, please let us know.

What happens when the candidate BN imposes stronger independence assumptions than the generating graph? How much computation is saved and how does this affect the attained incompatibility?

When the candidate BN imposes stronger independence assumptions than the true underlying process, it will in general overestimate inconsistency. As usual, choosing a variational family trades tightness for tractability; both effects depend on the strength of the imposed assumptions. Appendix F.4 quantifies this trade-off on four positive-incompatibility PDGs from our Section 5.2 dataset. For each, we start with a cluster-tree BN family (see Appendix B.4), having no representation gap, and progressively remove edges, passing through structures with independence assumptions comparable in strength to the base BN’s and ending at a mean-field approximation. As expected, each such ablation generally leads to a faster algorithm at the cost of a grosser over-estimate. At very large BN parameterizations, however, we do find optimization can become more difficult, and so the same number of iterations can end at a higher incompatibility.

Can you shed light on why RB achieves lower residual losses than plug-in? Direct comparisons with exact gradients at fixed parameter values could show for example whether RB reduces gradient bias.

Rao–Blackwellization reduces the variance of an estimator while preserving its expectation. Here, it is applied to estimates of the conditional probabilities μθ(t∣s)\mu_\theta(t\mid s). However, the gradient estimator depends nonlinearly on these estimates, so this guarantee does not directly extend to gradient bias or variance (Appendix E). Nevertheless, preliminary comparisons against exact gradients show that RB does indeed achieve lower gradient bias and variance at the states we examined. These improved gradient estimates explain RB’s lower residual losses. We will provide precise numerical results in a follow-up comment.

Here are numerical results providing a closer look at how sample size affects gradient estimate accuracy, and how much RB improves gradient accuracy over the plug-in estimator.

We evaluate eight PDGs of varied sizes: four with zero inconsistency and four with positive inconsistency. For each PDG, we test eight sample sizes, doubling from 8,000 to 1,024,000 samples per iteration. At each sample size, we run RB for 100k iterations without coverage regularization. At every iteration, we compute both the plug-in and RB gradient estimates at the same parameter values and measure their squared L2 error relative to the exact gradient. Below, we report each estimator’s mean error across all 100k iterations, together with the mean and median per-iteration percentage reduction achieved by RB over plug-in.

PDGStatistic8k16k32k64k128k256k512k1,024k
Asia 2N (zero-inc)Mean Plug-in Squared L2 Gradient Error0.0008240.0004110.0002080.0001025.18e-052.56e-051.28e-056.41e-06
Mean RB Squared L2 Gradient Error0.0004780.000240.0001236.06e-053.09e-051.51e-057.62e-063.81e-06
Mean / Median Reduction63.1% / 67.2%62.6% / 66.1%62.2% / 65.2%62.0% / 64.7%61.9% / 64.4%61.9% / 64.2%61.9% / 64.4%61.8% / 64.1%
Width grid n=29, w=5, d=4 (zero-inc)Mean Plug-in Squared L2 Gradient Error0.02160.006940.002610.0009730.0003780.0001627.55e-053.6e-05
Mean RB Squared L2 Gradient Error0.001790.0007990.0003630.000177.47e-053.89e-052.06e-051.04e-05
Mean / Median Reduction91.5% / 91.9%88.2% / 88.9%85.8% / 86.7%82.3% / 83.4%80.0% / 81.0%75.6% / 76.8%72.3% / 73.7%70.7% / 72.3%
Hailfinder 8N (zero-inc)Mean Plug-in Squared L2 Gradient Error0.3680.1720.08280.04050.02010.009990.004980.00249
Mean RB Squared L2 Gradient Error0.170.08140.03970.01960.009740.004860.002430.00122
Mean / Median Reduction62.0% / 64.1%61.4% / 63.5%61.0% / 63.1%60.7% / 62.8%60.6% / 62.7%60.4% / 62.5%60.1% / 62.2%60.0% / 62.1%
Pathfinder 2N (zero-inc)Mean Plug-in Squared L2 Gradient Error0.5940.2720.1210.0570.0260.01230.005760.00279
Mean RB Squared L2 Gradient Error0.5670.2620.1170.05530.02540.01210.005650.00275
Mean / Median Reduction34.3% / 35.8%26.4% / 27.4%25.4% / 26.8%26.0% / 26.9%20.7% / 22.2%20.1% / 21.2%21.1% / 21.4%18.7% / 18.8%
Asia 2N (positive-inc)Mean Plug-in Squared L2 Gradient Error0.0009260.0004620.0002330.0001155.78e-052.87e-051.44e-057.19e-06
Mean RB Squared L2 Gradient Error0.0005670.0002840.0001447.1e-053.57e-051.77e-058.89e-064.44e-06
Mean / Median Reduction61.1% / 65.5%60.7% / 64.7%60.5% / 64.4%60.4% / 64.1%60.3% / 64.2%60.3% / 64.1%60.4% / 64.0%60.3% / 63.9%
Alarm 4N (positive-inc)Mean Plug-in Squared L2 Gradient Error0.03790.01860.00920.004540.002270.001130.0005670.000284
Mean RB Squared L2 Gradient Error0.02560.01280.006380.003150.001580.000790.0003940.000198
Mean / Median Reduction35.3% / 36.1%34.1% / 34.9%33.3% / 34.1%33.4% / 34.1%33.2% / 34.0%33.1% / 33.9%33.0% / 33.8%32.9% / 33.8%
Hailfinder 8N (positive-inc)Mean Plug-in Squared L2 Gradient Error0.3750.1750.08440.04140.02050.01020.005090.00255
Mean RB Squared L2 Gradient Error0.1770.08460.04130.02040.01020.005120.002570.00129
Mean / Median Reduction61.3% / 63.3%60.6% / 62.6%60.1% / 62.1%59.7% / 61.7%59.3% / 61.4%58.9% / 60.8%58.4% / 60.3%58.0% / 59.9%
Pathfinder 2N (positive-inc)Mean Plug-in Squared L2 Gradient Error0.9470.4110.1870.08530.03830.01790.008740.00421
Mean RB Squared L2 Gradient Error0.9130.40.1820.08360.03770.01760.008630.00416
Mean / Median Reduction35.9% / 38.2%25.8% / 27.2%28.1% / 29.0%22.6% / 23.1%22.1% / 22.5%20.5% / 20.9%20.1% / 20.4%20.0% / 20.1%

I thank the authors for the detailed response and additional experiments which address my concerns and strengthen the empirical support for the method. I am maintaining my weak-accept recommendation with greater confidence following the rebuttal. I view the paper as a useful computational contribution, although I remain more reserved about its broader significance. My unchanged score reflects this overall assessment rather than any unresolved concerns.

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

The paper proposes a scalable sampling-based method for approximating inconsistency in probabilistic dependency graphs (PDGs). It represents a candidate joint distribution using a Bayesian network with logit-parameterized conditional probabilities and optimizes its parameters to reduce incompatibility. The authors develop plug-in and Rao–Blackwellization-based gradient estimators and evaluate them using Adam. The experiments show improved scalability, with the RB estimator generally achieving lower incompatibility than the plug-in estimator.

Critical strengths
  1. The proposed method is computationally efficient and scalable. The experiments show that it can handle larger PDGs where the compared methods exceed the wall-clock time.
  2. The paper addresses an interesting problem: combining probabilistic beliefs that may disagree with one another. Measuring and reconciling such disagreements is useful when working with information from different sources.
Critical weaknesses
  1. I found it difficult to assess how accurately the method estimates inconsistency when the beliefs conflict. The first experiment uses consistent or nearly consistent PDGs, and in the second, the true inconsistency is unknown. Also, both settings use the BN’s own graph from which beliefs were generated to provide the structure for the parameterized Bayesian network. Examples with known, nonzero inconsistency and comparisons using different BN structures would make the results more informative.

  2. Although cluster-tree baseline outcomes are reported, a comparison of the achieved incompatibility on cases where these methods return reliable solutions would make the evaluation more informative.

  3. The approach has two potential gaps. First, the chosen BN may be too restrictive to represent an optimal joint distribution. Second, optimization may not find the best solution within that BN family. The paper provides no general bounds on these errors, leaving it unclear how closely the final estimates approximate the true PDG inconsistency.

  4. Lemma 1 gives an O(1/N)O(1/N) bias bound at fixed parameters, but the constant CC is unspecified and depends on the model parameters. It is therefore difficult to judge how many samples are needed to obtain a small bias in practice, especially when some probabilities become very small. The extension of the Taylor bound to the whole simplex could also be explained more clearly.

  5. The latter part of the introduction (lines 072–085) focuses heavily on the paper’s technical contributions, while the problem itself remains abstract and difficult to follow. The introduction would benefit from a simpler, more detailed explanation of the problem, supported by a concrete example of conflicting probabilistic beliefs. This would help readers understand what PDG inconsistency means, why measuring it matters, and why existing methods struggle before introducing the proposed approach.

  6. Minor comment: Some notation needs more explanation in the main paper. For example, the role of A0\mathcal A_0 is unclear without reading the appendix. A brief explanation would make the paper easier to follow.

Questions for authors

Source-coverage regularization helps the plug-in estimator more than RB in Figure 1. Can the authors explain this difference and discuss sensitivity to the regularization schedule?

How sensitive are the final incompatibility and runtime to the chosen BN structure and optimizer? Comparisons with simpler or alternative BN structures, and with optimizers other than Adam, would help clarify this.

1 comment

Thank you for the helpful review!

Weaknesses 1 & 2

These are both real weaknesses of the submitted draft, and we have run new experiments to address them.

In Appendix F.3.2, we generate 100 conflicting PDGs following the published protocol of Richardson et al. (2023), obtaining accurate convex solutions for all 100, providing a natural testbed for baseline comparison in the "known, nonzero inconsistency" setting. Our methods use equivalent cluster-tree BNs, so the comparison has no representation gap and does not rely on a hidden generating BN. Both sampling algorithms closely approach the convex references, with worst relative excesses below 0.057% for RB and 0.27% for plug-in across three initializations. Exact JAX also closely matches these references, while the cluster-tree gradient baselines retain substantially larger residuals.

Appendix F.3.1 now plots accuracy and runtime on the 133 zero-inconsistency PDGs for which at least one baseline produced a valid result. Convex optimization is highly accurate when it succeeds, but its computational cost grows rapidly, exceeding that of our sampling algorithms before becoming intractable on larger instances under our resource limits. Compared with cluster-tree Adam, our sampling methods and exact JAX generally achieve substantially lower incompatibility in less time.

[...] comparisons using different BN structures would make the results more informative.

Our new experiments in appendix F.4 vary the BN structure on four noisy benchmark PDGs, comparing progressively pruned structures with full cluster-tree BNs. These experiments illustrate the tradeoff between runtime and achieved incompatibility, and show that greater expressiveness does not ensure better finite-time optimization. For two BNs (Asia and Child), convex references provide two additional cases with known nonzero inconsistency, and our cluster-tree BN fits closely approach these values.

For the full paper, we will run a comprehensive sweep and promote some of this material to the main text.

Weakness 3

This is an important point. Our approximation can incur both a representation gap from restricting the BN family (which can be controlled) and an optimization gap from not reaching that family’s optimum; we do not provide a general bound on their sum. It is possible to generate a fully-expressive BN structure for a given cluster tree; in this case, the representation gap vanishes, and the finite-logit objective has no suboptimal stationary points (Appendix B.4)—yet this favorable geometry still may not guarantee rapid convergence. For more restrictive BN families, both gaps may be nonzero.

Regarding restricted BN families, it's worth noting a representation gap need not indicate an inappropriate model family. The restrictions may encode informed structural knowledge about the system under study. In this case, the unrestricted optimum may reconcile noisy beliefs by introducing correlations the underlying system has no mechanism to support, and so represent an invalid reconciliation. In contrast, the restricted optimum would be the proper measure of irreducible inconsistency among the beliefs. See our response to reviewer sX1r for a detailed exposition on this point, an example, and an argument that our positive-incompatibility benchmarks naturally admit this interpretation.

Weakness 4

We have strengthened Lemma 1 and included an easy-to-follow, updated proof in Appendix D.2. For tabular BN logits under the stated positivity assumptions, the unclipped plug-in data gradient satisfies∥Eg^N−∇I∥∞≤1N∑aβaKSa(KTa−1)\Vert\mathbb{E}\widehat g_N-\nabla I\Vert_\infty\le\frac{1}{N}\sum_a\beta_aK_{S_a}(K_{T_a}-1)where KS,KTK_S,K_T count source and target assignments. The constant is independent of the smallest candidate probability.

Weaknesses 5 & 6

We agree. We will improve the intuition and motivational force of the introduction, and improve the explanation of the role of structural edges A0\mathcal{A}_0.

Questions

Coverage regularization (RB vs Plug-in): Intuitively, plug-in estimated conditionals use sample counts, and so require more samples to obtain an accurate estimate. RB extracts more information per sample using conditional averaging, potentially improving estimate variance. Appendix E shows that RB's conditional estimates have no greater variance than plug-in's, but also argues this does not necessarily imply that RB gradient estimates have less expected bias or variance. Nonetheless, in initial experiments, we find in our settings that RB gradient estimates do indeed have improved gradient bias and variance. Since RB can in practice learn from fewer samples per source, it empirically requires less source coverage regularization to preserve samples for each source.

Optimizer sensitivity: Across six PDGs and three starts, exact-gradient L-BFGS-B universally improved mean incompatibility over Adam at similar iteration counts, but took 6-15x longer. Of course, L-BFGS-B does not scale to larger PDGs.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.