We describe how to efficiently add new vocabulary directly to an existing optimized ASR decoder graph. The augmented decoder graph is represented by two weighted finite-state transducers, a primary graph that represents the static portion and a secondary graph that represents the dynamic portion, together with a mapping that specifies that some states in the two graphs are to be merged. Determinism is obtained by excluding from the secondary graph any prefixes already present in the primary graph. Correct context-dependency is obtained by including in the primary graph all prefixes needed to properly merge with the secondary graph. We report experiments comparing this approach to an existing one that requires on-the-fly construction of the decoder graph.