A frequently used testbed for coherence models is the discourse ordering problem, which occurs often in text generation, complex question answering, and multi-document summarization: given discourse units, what is the most coherent ordering of them (Marcu, 1996; Lapata, 2003;<cite> Barzilay and Lee, 2004</cite>; Barzilay and Lapata, 2005) ? Because the problem is NP-complete (Althaus et al., 2005) , it is critical how coherence model evaluation is intertwined with search: if the search for the best ordering is greedy and has many errors, one is not able to properly evaluate whether a model is better than another.