In language evaluation systems, user expressions are often evaluated by speech recognizers and language parsers, and among several possible translations, a highest-probability translation is selected and added to a dialog sequence. However, such systems may exhibit inadequacies by discarding alternative translations that may initially exhibit a lower probability, but that may have a higher probability when evaluated in the full context of the dialog, including subsequent expressions. Presented herein are techniques for communicating with a user by formulating a dialog hypothesis set identifying hypothesis probabilities for a set of dialog hypotheses, using generative and/or discriminative models, and repeatedly re-ranks the dialog hypotheses based on subsequent expressions. Additionally, knowledge sources may inform a model-based with a pre-knowledge fetch that facilitates pruning of the hypothesis search space at an early stage, thereby enhancing the accuracy of language parsing while also reducing the latency of the expression evaluation and economizing computing resources.