An exact algorithm for MAP, the hardest standard query in a Bayesian network, that is not limited by treewidth because its bounds are computed in linear time on a compiled arithmetic circuit.
MAP asks for the most likely joint state of a set of variables given evidence about the rest, and it is harder than ordinary probability queries. The standard exact methods for it are exponential in the network's constrained treewidth. This paper gives an exact algorithm whose scalability is not necessarily limited even by treewidth, by running a branch-and-bound search whose bounds are linear-time operations on a compiled arithmetic circuit.
On networks with local structure the authors saw orders-of-magnitude improvements over the previous best exact algorithm, and solved many problems where it ran out of memory.
The same compiled circuit that answers a probability query in constant time also gives the bounds that make a harder query tractable. It is an early demonstration of how much a compiled model can carry.
A methods paper. No product claims attach to it.