This paper proposes a stochastic understanding model and its utilization on recognition word-graphs, to enhance the end-to-end performance of spontaneous speech understanding systems. The understanding model is constructed automatically based on Binary Decision Trees, which account for the semantic probability for a word sequence. We apply the model on word-graphs provided by speech recognition, and search the most profitable paths that maximize the acoustic, linguistic, and semantic probabilities for the utterances. Speech understanding experiments show that our approach improves understanding accuracy from 65.6% to 68.5%, compared to the simple understanding results for recognition top-best hypotheses.