The present invention relates to a method and apparatus for adding new vocabulary to interactive translation and dialog systems. In one embodiment, a method for adding a new word to a vocabulary of an interactive dialog includes receiving an input signal that includes at least one word not currently in the vocabulary, inserting the word into a dynamic component of a search graph associated with the vocabulary, and compiling the dynamic component independently of a permanent component of the search graph to produce a new sub-grammar, where the permanent component comprises a plurality of words that are permanently part of the search graph.