In one embodiment, a router may store a “neighbor table” for storing the router's Border Gateway Protocol (BGP) neighbors. Each neighbor corresponds to a virtual routing and forwarding (VRF) instance and associated VRF identifier (ID), and the neighbor table indexes the BGP neighbors according to their respective VRF ID. In response to initiating a BGP update generation for a BGP table having BGP network entries, each entry having an associated VRF ID that indicates to which VRF instance the BGP entry is to be advertised, a single lookup operation for each BGP entry is performed into the neighbor table based on the corresponding VRF ID of each BGP entry to determine a corresponding VRF update group of indexed BGP neighbors to which each BGP entry is to be advertised. Accordingly, a shared BGP update may be generated for each VRF update group for the initiated BGP update generation.