Software that dynamically updates virtual machine templates at deterministic intervals in order to reduce patching time, by performing the following operations: (i) identifying a virtual machine (VM) provisioned according to a first VM template; (ii) initiating a patching process that applies a set of patch(es) to the VM, thereby creating a patched VM; (iii) determining that an amount of time taken to complete the patching process is greater than a predetermined threshold; and (iv) responsive to determining that the amount of time taken to complete the patching process is greater than the predetermined threshold, generating a second VM template based, at least in part, on the patched VM.