A data processing apparatus includes control flow prediction circuitry that generates a control flow prediction in respect of a group of one or more instructions. Storage circuitry used by the control flow prediction circuitry stores data in association with groups of instructions used to generate the control flow prediction for each of the groups of instructions. Control flow prediction update circuitry inserts new data into the storage circuitry in association with a new group of one or more instructions in dependence on one or more conditions being met when a miss occurs for the group of one or more instructions in the storage circuitry.