In one embodiment, a device in a network determines whether a destination address of a packet received by the device is within a neighbor discovery (ND) cache of the device. The device determines whether the destination address is not in a set of addresses used to generate an address lookup array or possibly in the set of addresses used to generate the address lookup array, in response to determining that the destination address of the packet is not within the ND cache. The device performs address resolution for the destination address of the packet, in response to determining that the destination address of the packet is possibly in the set of addresses used to generate the address lookup array.