Techniques are described for updating an automatic speech recognition (ASR) system that, prior to the update, is configured to perform ASR using a first finite-state transducer (FST) comprising a first set of paths representing recognizable speech sequences. A second FST may be accessed, comprising a second set of paths representing speech sequences to be recognized by the updated ASR system. By analyzing the second FST together with the first FST, a patch may be extracted and provided to the ASR system as an update, capable of being applied non-destructively to the first FST at the ASR system to cause the ASR system using the first FST with the patch to recognize speech using the second set of paths from the second FST. In some embodiments, the patch may be configured such that destructively applying the patch to the first FST creates a modified FST that is globally minimized.