The Normalized Float Trick: Numerical Stability for Probabilistic Circuits without the LogSumExp Trick

• There is lack of motivation. The paper does not provide a convincing explanation or theoretical justification for why the NoFlo trick should lead to improved performance over the LogSumExp trick. The claim that it "simply works better" seems insufficient, leaving the reader wondering why this new method is superior beyond empirical results.

• the analysis on the computational cost actually seems to suggest that there's should be practically very limited computational advantage in using the trick, as the cost is dominated by C^2, which can be very high for large models.

• comparison with very relevant literature is missing [1]

• I do also have the feeling that something may be off implementation-wise. To check that models are actually encoding valid distributions, authors could build a small model for, say, 16 binary variables, compute all possible 2^16 log-likelihood and check if their sum is actually (very close to) zero. Could the authors try this test and report to me if the log-sum-exp implementation and the NoFlo return the same value? I'd also suggest to check what happens when playing with small models, without directly jumping to MNIST.

• I believe that the results reported in Fig 4 show that there's a bug somewhere as the difference in test-bpd between the LSE and NoFlo is too high to just be numerical precision. Playing with a toy dataset (as suggested above) might be insightful.

MINOR:

• The term "partition" in this paper is used in a different way than the common literature, and can therefore be misleading. Partition is in fact something usually referred to region graphs . Authors even cite relevant literature in this regard (see line 126), yet do not conform to the same language. For instance, the sentence "four partitions in the leaf layer" should just become "folded input layer", as authors seem to be somehow aware of folding techniques [2].

• Structured-decomposability is never formally defined, and when mentioned actually seems to refer to the simple "decomposability" (see L86-87)

• there's a typo in L155: what p_ki is?

[1] Yao, Lingyun, et al. "On Hardware-efficient Inference in Probabilistic Circuits." The 40th Conference on Uncertainty in Artificial Intelligence.

[2] Loconte, Lorenzo, et al. "What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?." arXiv preprint arXiv:2409.07953 (2024).

In summary, while I appreciate the overall idea, I believe this work needs to improve in several aspects (listed below) to be considered for publication (especially at such a prestigious venue). I highlight that I see potential in this research, in that it would be particularly strengthened by addressing some key limitations.

1. At line 453 the authors write "The code base will be made available to the reviewers through an anonymous link". Unless I somehow missed it, this is not true. Access to the source code can sometimes be very useful to the review process and denying it asks for a better justification than "lab's policy".

   [Extra] If such a policy is as unique as it seems to me, disclosing it may compromise the authors' anonymity to some extent (consider the extreme case where a single lab has such a policy and one of the reviewers knows that to be the case). The authors should be mindful of the potential issue.

2. No train-data performance is reported even though overfitting might be an important factor in the results. Without this information, one cannot disregard the possibility that the proposed method leads to higher numerical distortions compared to the LogSumExp trick, since this error could lead to some sort of regularization that would explain the improvements in test-data performance detected by the experiments. Put differently, it seems like a reasonable hypothesis that, by erasing information/adding noise, underflowing reduces the expressiveness of the model, which could lead to better generalization. This hypothesis seems worth of some discussion, at least.

   See Question 1.

3. Overall, the work lacks a deeper, more meaningful comparison with the reference method. When starting to read the paper, I was expecting to soon find some rich theoretical analysis of the numerical stability of the methods, perhaps with results bounding the error propagation in terms of the weight matrices (their spectral norm, I guess). Instead, the closest to that would be the estimations in section 3.3, which is a nice starting point but cannot be generalized too much given how complex the computational cost of low-level methods can become. (The authors seem aware of the difficulty, as they, e.g., hint at the significance of hardware particularities).

   Without a solid theory, generalizing the performance of the proposed method to other settings depends heavily on the experiments. However, those are too limited to fulfil this role.

   In summary, while I do not doubt it, I remain unconvinced of the generality of the results presented, and, thus, of the significance of the proposed method.

4. Given the striking analogy between the proposed method and the floating point representation used in hardware, it is surprising that the authors do not discuss any relationship between the two at all. For example, in terms of floating point representation, the proposed method could be loosely seen as increasing the precision in the representation of $\pi \in [0, 1]^d$ by storing an adaptively chosen common offset for the exponent (a.k.a. characteristic) of the representations of the coordinates of $\pi$, with this offset being stored in $\beta$. (Here, I ignored the significand (a.k.a. mantissa) for simplicity.)

   I am not sure to which extent issue is pertinent, so I will regard it as a minor one. Still, I recommend the authors consider it. For instance, I would not be surprised if investigating this direction led to some useful "bit-hacks" that improve the efficiency of the proposed method.

5. It is somewhat odd that section 3.3 eventually uses cycle-counts estimated for x86 architecture while experiments are run on GPUs. This inconsistency further reduces how much we can learn from the estimations in that section.

6. The writing is subpar.

   1. There are many typos.

   2. The overall text feels artificially stretched, with long phrasings, repetitions, and an overall slow pace that reduces clarity rather than increasing it.

   3. The mathematical writing is not tight enough. The authors frequently fail to fully characterize mathematical objects (usually by omitting domains of index variables) and typos are also present in the maths.

   4. Motivation, intuition, or references are missing around some important design choices. Without those, passages like paragraphs 286-290, 297-302, and 308-311 are hard to appreciate. Why those choices? What were the alternatives? How do they compare? What should be their positive and (more importantly) negative implications?

      An example would be the excerpt "For the sake of exposition we will limit ourselves to canonical polyadic layers and refer the reader to (Mari et al., 2023) for alternatives" (around line 126). It is fair and a good start for the authors to make this comment. However, this reference still asks for some discussion (even if brief) on how significant those alternatives are and how the authors' contribution relates to them.

      Even arbitrary choices need to be properly signalled as such to allow for proper interpretation of the results.

Minor issues and suggestions

1. The times reported in Figure 3 seem unusually long. Are you sure everything is consistently running on the GPU?

Regarding the presentation, I think the paper has some weaknesses as it introduces a different terminology from some concepts that are already known. I believe these can be addressed during the rebuttal. (1) The paper mention the concept of partition tree from a very recent paper (L097). However, the same definition looks the same of vtree [A] or pseudo tree [B]. (2) The paper defines partition circuits (Defn. 2.1.) and layered probabilistic circuits (Defn. 2.2.). The authors might be interested in unifying the terminology with the definition of tensorized circuit appearing in a follow-up work by Mari et al. 2023 [C].

[A] Pipatsrisawat, K.; and Darwiche, A. 2008. New Compilation Languages Based on Structured Decomposability. [B] Dechter, R.; and Mateescu, R. 2007. AND/OR search spaces for graphical models. [C] L. Loconte, A. Mari, G. Gala, et al. 2024. What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?

In the abstract and introduction of the paper, the authors mention that the NoFlo trick boosts performances of probabilistic circuits for distribution estimation. However, I do not believe this is a claim supported by the evidence. Although the paper reports a decrease in bits-per-dimension (BPD) when using the NoFlo trick either at evaluation or training time, this decrease cannot be interpreted as a significant improvement. The reason is that the "evaluation ground truth" -- the true BPD scores one would get with infinite precision -- is not known, and it could be closer to the one achieved by using the NoFlo or log-sum-exp trick. As such, the performance boost that has been observed empirically could be due to some additional unknown numerical instability occurring in the NoFlo trick.

The paper lacks experiments on smaller scales. By scaling the size of the circuits, it becomes more difficult to understand which evaluation method is more numerically stable and therefore determine which BPD is closer to the "ground truth" (see above). I think the paper would be much more solid if it provided results comparing three evaluation methods: NoFlo trick, log-sum-exp trick, and evaluation with no tricks (i.e., by evaluating sum and product as is). By performing these experiments on much smaller circuits and in float64 (thus avoiding underflows), the authors might be able to determine whether the differences in BPD is due to other types of numerical instabilities occurring in very large circuits only.

The two points mentioned above bring my score substantially down. However, I am open to increase it if further evidence is provided.

1. The authors claim the proposed method is more numerically stable than logsumexp, however, they do not verify or explain why this trick is more numerically stable. My understanding is that the proposed method is to cache the $\alpha_k$ terms during training and evaluation, but it’s unclear how this leads to improved stability. Is the stability enhancement due to reduced log and exp computations on $\alpha_k$? Comparing likelihoods would make this claim convincing.

2. In the experiments, the authors implement both logsumexp and nofloat trick to compare their performance, why not compare the log-likelihoods with existing methods, such as [1]? Is there still a performance improvement there. The architecture and training pipeline are bothn implemented by the authors themselves, why not use existing library, such as Peharz et al. or 2020; Liu et al., 2024; to the best of my knowledge, the existing libraries handle numerical stability very well. Is there still performance improvement if you use existing library.

3. The writing is not clear enough. For instance, is Proposition 2.3 based on prior work, and what role does it play in the overall argument?

4. The authors do not seem to be familiar with the related work, for example, in line 78, the layered circuit is not introduced in Shih et al. (2021). What Shih et al. (2021) does it to use neural models for parameter sharing and thus regularization. The architecture is commonly used and introduced in [2] and Peharz et al. or 2020.

[1] Pedro Zuidberg Dos Martires. Probabilistic Neural Circuits. AAAI 2024. [2] Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Xiaoting Shao, Kristian Kersting, and Zoubin Ghahramani. Random sum-product networks: A simple and effective approach to probabilistic deep learning. UAI, 2019.