1. A method of incremental partition recombination for tracking multiple dialog states, the method causing a computing device to perform steps comprising: receiving an N-best list of speech recognition candidates; receiving a list of current partitions and a belief for each of the current partitions, wherein a partition is a group of dialog states; in an outer loop, iterating over each of the speech recognition candidates in the N-best list; in an inner loop, performing a split, update, and recombination process to generate a fixed number of partitions after each speech recognition candidate in the N-best list; and recognizing speech based on the N-best list and the fixed number of partitions.