- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
In this work the authors extended NeuroBE into a class of neurosymbolic algorithms (NCTE) operating over tree-decompositions. The authors empirically show that the new framework facilitates better performance in time/ accuracy in most of the problem instances tested. The empirical analysis shows that selecting a good tree-decomposition can be obtained by analyzing the problem structure combined with empirical estimation of some performance parameters from data.
Overall Assessment This is a solid systems-style extension paper (of NeuroBE). The core idea is straightforward: (1) NeuroBE trains a neural approximation at every large bucket; (2) NCTE merges buckets into larger clusters, thereby reducing the number of neural approximators and potentially reducing error propagation. The paper demonstrates substantial runtime improvements and often improved accuracy relative to NeuroBE. The empirical results are generally convincing for the specific claim: "Carefully chosen cluster-tree decompositions can outperform bucket-tree decompositions for neural message approximation. "
Critical strengths
-
Clear technical contribution The contribution is easy to understand: NeuroBE consists of many neural approximators. This is replaced with NCTE, which uses fewer neural approximators via cluster merging. This is conceptually clean and emerges naturally from classical bucket-tree versus cluster-tree elimination theory.
-
Strong empirical gains The reported runtime improvements are often dramatic. For example: grid20x20f10: no-merge: 50.5 min Reduce-NN: 3.9 min while also reducing error from 3.49→0.255 simultaneously. The paper claims several pedigree instances show similarly large gains.
-
The tradeoff theory is sensible The paper correctly identifies competing effects: benefits of fewer networks include less training cost, less error accumulation cost; in addition, larger eliminators lead to more expensive sample generation and higher local computational burden. The observed U-shaped runtime curves are consistent with this model.
This is achived via fewer neural approximators via cluster merging. This is conceptually clean and emerges naturally from classical bucket-tree versus cluster-tree elimination theory.
Critical weaknesses
-
Missing scale-up analysis This is perhaps the largest experimental weakness. The paper includes: grids, pedigrees, RBMs, and larger instances within those classes. However, it never really answers: How does NCTE scale as problem size grows? For example, I expected plots of: n↦"runtime" or n↦"error" variables ranging from 100 to 5000. Instead, we see isolated benchmark points. This is not true scaling analysis.
-
Almost no ablation study I searched specifically for ablations and found essentially none. The paper compares: no merge, subsumption-only, Reduce-NN; however, these are algorithm variants, not ablations.
Ablations would answer questions such as: Why does error improve? The paper asserts: "fewer neural approximations reduce error accumulation. " But I do not see experiments measuring: error per approximation stage, cumulative message distortion, approximation depth, propagation of local neural errors. The claimed mechanism is never directly tested.
-
No evidence for the error-propagation hypothesis The paper repeatedly suggests: "fewer NNs → less accumulated error → better accuracy. " But this remains a hypothesis. A convincing experiment would compute: ϵ_t="message error at depth " t along the elimination chain. Then show: ϵ_t grows substantially in NeuroBE but not NCTE. Nothing like this appears.
-
No architectural ablation All networks appear to use: 2 hidden layers, width 3∣S∣, ReLU. The paper never investigates: network depth, width, activations, sample counts. Consequently it is impossible to know whether: (a) cluster merging is the principal driver, or (b) training budget allocation is.
-
No sensitivity analysis of the learned approximation The implementation fixes N=O(∣S∣^2 log∣ S∣) samples. Yet there is no analysis of a range of sample bugets, e.g., from 20% to 100%: Therefore we cannot distinguish: Is NCTE robust because (a) clusters are intrinsically better? or (b) because merged networks receive more effective supervision?
What Experiments Are Missing?
A. Number-of-NNs ablation You need to artificially vary K="number of neural approximators" and then measure accuracy and runtime. This would directly test the central hypothesis.
B. Error accumulation study Measure exact message error against exact elimination: ∥λ_t-λ ̂_t∥ at successive levels. Then demonstrate error propagation. Currently the key mechanism is asserted but not shown.
C. Scale-up study For grids: 10×10 20×20 30×30 40×40 50×50 then plot: runtime, accuracy, number of networks, average separator size. The paper lacks this entirely.
D. Separating the two effects Merging changes two things simultaneously: fewer networks and larger eliminators. The paper never disentangles them. A proper ablation would independently vary: (a) number of NNs, (b) eliminator size.
E. Compare against modern neural inference methods The comparison is largely against NeuroBE and indirectly against earlier methods discussed in related work. For an ICLR paper, the audience will likely ask: Why not compare against current neural amortized inference approaches? The evaluation is somewhat narrow.
Theoretical Weakness: The paper's explanatory theory is fairly weak. The central argument is: "fewer neural approximations reduce accumulated approximation error. " But there is no theorem such as: "Error" (T_"cluster" )<"Error" (T_"bucket" ) under reasonable assumptions. Nor is there a bound relating: approximation depth, message error, and final partition-function error. As a result, much of the explanation remains intuitive.
Questions for authors
Q1: Why does accuracy improve? What experimentally measured mechanism causes the improvement? The paper does not answer this convincingly.
Q2: How does performance scale with graph size? I do not see a true scaling study.
Q3: How much of the gain comes from: • fewer NNs, • larger separators, • larger training sets, • different sample distributions? There is no ablation answering this.
Q4: Can the claimed error-propagation effect be measured directly? No experiment currently appears to do this.
3 comments
response to authors' rebuttal
Thanks to the authors for addressing my concerns about the experimental issues, such as scale-up and ablation studies. These are helpful to the ML audience.
I have a nagging issue with this response, based on a comment originally in my review: ML researchers are interested in "why" a phenomenon occurs; the increased empirical analysis helps to address this, but the rebuttal has not satisfied this issue properly. There is now significantly more empirical data, but what does this data point to? How can you use this data to improve tree decomposition in general? I still seem to be missing the overall conclusion. Without a true discussion of the outcome of the empirical analysis, I cannot improve my score.
Thank you. To answer the “why?”: when merging, we perform more exact computation (via more expensive variable elimination) in order to decrease the number of neural networks, and we hypothesize that this decrease lowers average log Z error. Merges either replace an NN approximation and exact message with an exact message or replace two NN approximations with one. In the latter case, the merged cluster’s message inherits the dimensionality of the parent’s message, motivating the expectation of comparable error per NN. Our local error study isolates this case of two NN-approximations merging into one. We find roughly stable average error per NN, i.e. more merging does not generally increase the per-NN error. Additionally, the merge-bound sweeps support the overall accuracy trend: tree decompositions with fewer neural approximations generally yield lower partition function error.
We have made the hypothesis, supporting evidence, and implications for tree-decomposition design explicit in Section 4.2 and the conclusion.
Changes:
- Section 4.2, “Local approximation error under merging”: clarified that the merged cluster inherits the parent’s separator.
- Section 4.2, “Implications for tree-decomposition design”: connected the local error study to the implications for tree-decomposition design.
- Section 5, “Summary and Conclusion”: summarized the implications for tree-decomposition design.
- Section 4.2, “Scaling with problem size,” and Appendix H, Table 7: added the completed results of the 28×N scaling study, with three runs per instance.
Response to Reviewer XQAd
Summary. We thank the reviewer for identifying several useful empirical questions. The revision adds a controlled scale-up study, controlled clustering comparisons, a direct local message-error study, and narrows the accuracy claims to what is empirically supported.
Scale-up analysis / Experiment C / Q2. We added a controlled 28×N Ising-grid study spanning 112 to 5,600 variables. Exact Z is computed by cluster tree elimination, while every approximate method uses the same width-28 ordering, holding induced width fixed while measuring exact-reference error, runtime, and number of learned messages.
Changes.
Ablation study / Experiments A and D / Q1. The reviewer asks to independently vary the number of neural approximations and eliminator size. In NCTE these are structurally coupled: reducing learned messages requires merging clusters, which necessarily changes the eliminator. We therefore compare three clustering strategies while holding architecture, loss, sampling policy, and elimination order fixed, and sweep emax to vary merging. On grid20x20.f5 and 38 of pedigree19’s 82 network clusters, the merged message has mean absolute local error 0.101 and 0.069, versus 0.192 and 0.145 for the summed magnitudes of the two learned messages it replaces. When a merge makes a message exactly computable, that approximation error disappears.
Changes.
Error-propagation hypothesis / Experiment B / Q4. We added an experiment measuring each learned message’s local contribution under exact surroundings. One merged approximation typically replaces two local error sources without inheriting their combined magnitude. We do not present this as a telescoping decomposition of the full NCTE run or proof of reduced propagation.
Changes.
Architecture and sample sensitivity / Q3. We use the same neural-network architecture rule, loss, uniform sampling policy, and sample-count rule for all clustering strategies, and do not reallocate computation saved by merging to increase capacity or sampling. Because merging can change separator sizes, resulting network widths and training-sample counts can change under these fixed rules. Thus, we evaluate clustering strategies under a common training protocol; we do not claim the gains are independent of architecture or sample count.
Change.
Experiment E. Comparison with modern neural inference methods. We did not identify a directly comparable baseline. For example, Belief Propagation Neural Networks (BPNNs) learn an inference procedure across a distribution of graphical models using training instances with known partition functions, while neural variational/autoregressive methods learn a global distribution or direct estimate of Z. NCTE instead trains instance-specific approximations of local elimination messages, yielding a reusable message-based representation. To broaden the direct comparison, we added WMB with moment matching and weight optimization at i-bound 20; across the 19 exact-reference configurations, Reduce-NN has lower mean absolute log10Z error (0.490 vs. 2.66), at higher mean runtime (11.6 vs. 7.1 minutes).
Change.
Theoretical weakness. Accuracy explanation. Our formal analysis addresses runtime only; we do not have a theoretical result showing merging reduces partition-function error. The explanation that reducing neural approximations may reduce accumulated error is therefore an empirical hypothesis. We examine it across the full emax sweep in Appendix D, Table 3 (pp. 19–20), which reports error, NN count, error per NN, and runtime, and more directly in the local-error study in Section 4.2 (pp. 8–9) and Appendix G (pp. 22–24). These results provide empirical evidence, not a theoretical guarantee.
Changes.