A system for processing a query operates by receiving a first query segment that includes audio speech. Next, the system generates a representation for this first query segment, where the representation includes at least two paths associated with alternative phrase sequences for an ambiguity in the audio speech. The system then compares the paths in the representation to a group of documents and determines matching scores for the group of documents based on the comparisons. Finally, the system presents a ranking of the group of documents, where the ranking is based on the matching scores for the group of documents.