In one embodiment, a network element in a network maintains a probabilistic data structure indicative of devices in the network for which telemetry data is not to be sent to a device classification service. The network element detects a traffic flow sent from a source device to a destination device. The network element determines whether the probabilistic data structure includes entries for both the source and destination devices of the traffic flow. The network element sends flow telemetry data regarding the traffic flow to the device classification service, based on a determination that the probabilistic data structure does not include entries for both the source and destination of the traffic flow.