Network Function Virtualization (NFV) allows operators to deploy network functions in virtual machines (VMs) and benefit from on-demand deployment. VMs are placed on one of the hosts in the cloud, and existing resource management algorithms assume full knowledge of the system’s state. For large clusters, attaining the system’s state creates bottlenecks and therefore it takes a long time to deploy network functionalities. Intuitively, placement can be accelerated if the resource management algorithm operates on a cached system state which is not entirely up to date, but the placement quality may suffer. Our work introduces a new cache refresh method that achieves an up to a 5.3x reduction in placement time with only a slight degradation of quality compared to having the complete and up to date system’s state.11The research leading to these results has received funding from the European Union under the H2020 and 5G-PPP Phase2 programmes, under Grant Agreement No. 761 557 (project NGPaaS)