Abstract
Probabilistic circuits (PCs) are a unifying representation for probabilisticmodels that support tractable inference. Numerous applications of PCs likecontrollable text generation depend on the ability to efficiently multiply twocircuits. Existing multiplication algorithms require that the circuits respectthe same structure, i.e. variable scopes decomposes according to the samevtree. In this work, we propose and study the task of restructuringstructured(-decomposable) PCs, that is, transforming a structured PC such thatit conforms to a target vtree. We propose a generic approach for this problemand show that it leads to novel polynomial-time algorithms for multiplyingcircuits respecting different vtrees, as well as a practical depth-reductionalgorithm that preserves structured decomposibility. Our work opens up newavenues for tractable PC inference, suggesting the possibility of training withless restrictive PC structures while enabling efficient inference by changingtheir structures at inference time.