Before revision:  We demonstrate the advantages of exact inference on synthetic data of interest to Dasgupta's cost as well as on two real world applications, in particle physics at the Large Hadron Collider at CERN and in cancer genomics  .
After revision:  We demonstrate the advantages of exact inference on synthetic data of interest to Dasgupta's cost as well as on two real world applications, in particle physics at the Large Hadron Collider at CERN and in cancer genomics , and we give examples in both areas, where our algorithms outperform greedy and beam search baselines. In addition, we consider Dasgupta's cost with synthetic data .