Sophisticated inferential tools coupled with the coalescent model have recently emerged for estimation of evolutionary parameters, such as past population sizes, from present-day samples of genomic data. Coalescent-based methods rely on the Kingman-coalescent genealogy to model the sample’s ancestry. Unfortunately, the state space of genealogies grows superexponentially with the number of samples and hence, inference is computationally challenging for large number of samples. Here, we present a new Bayesian approach that relies on lower resolution coalescent processes with drastically smaller hidden state spaces. We provide new algorithms for efficient and exact likelihood calculations exploiting a new representation on a directed acyclic graph. We compare the performance of our algorithms with state-of-the-art algorithms in population genetics.