We present an algorithm for the incremental generation of word graphs. Incremental means that the speech signal is processed left-to-right by a time synchronous Viterbi algorithm and word hypotheses are generated with some delay to Viterbi decoding. The incrementally generated word hypotheses can be used for early interaction between linguistic analysis and acoustic recognition. Therefore, it is possible to derive acoustic constraints from linguistic restrictions dynamically.