A hypothesis space of a search graph may be determined. The hypothesis space may include n hypothesis-space transcriptions of an utterance, each selected from a search graph that includes t>n transcriptions of the utterance. An evidence space of the search graph may also be determined. The evidence space may include m evidence-space transcriptions of the utterance that are randomly selected from the search graph, where t>m. For each particular hypothesis-space transcription in the hypothesis space, an expected word error rate may be calculated by comparing the particular hypothesis-space transcription to each of the evidence-space transcriptions. Based on the expected word error rates, a lowest expected word error rate may be obtained, and the particular hypothesis-space transcription that is associated with the lowest expected word error rate may be provided.