Certain embodiments described herein are generally directed to using a flow cache with packets comprising dynamic headers. Embodiments include receiving a packet of a packet flow from a network, parsing the packet in order to determine a flow key, and comparing the flow key to entries in the flow cache. Upon determining that the flow key does not match any of the entries, embodiments include determining whether the packet comprises a dynamic header. Upon determining that the packet comprises a dynamic header, embodiments include canceling recorded flow cache information for the packet, performing an operation on the packet, re-parsing the packet in order to determine a new flow key, and comparing the new flow key to the entries in the flow cache. Upon determining that the flow key matches an entry, embodiments include determining cached actions to perform for the packet based on the entry and performing the cached actions.