The method of synchronizes network address translation (NAT) records between an active gateway and a standby gateway. The method of some embodiments synchronizes NAT records of long-term data flows more frequently than those of short-term flows. Multiple data flows pass between a device at an internal source address and a device at an external destination address through the active NAT gateway. For each flow, the method generates a NAT record. The method then determines whether the data flow is a short-term flow or a long-term flow and synchronizes the NAT records of the long-term flows, but not the NAT records of the short-term flows, with the standby gateway. The method of some embodiments synchronizing NAT records more frequently when NAT records are being generated quickly relative to prior generation rates and less frequently when NAT records are being generated slowly relative to the prior generation rates.