Systems, methods, and computer-readable media are disclosed for a scalable process for validating multiple paths used for routing network traffic in a network using segment routing. In one aspect, a method includes identifying, by a first network hop, one or more second network hops, for each of the one or more second network hops, determining a corresponding flow label, the corresponding flow label including a corresponding test packet for validating packet forwarding between the first network hop and a corresponding second network hop, and performing a validation process for validating packet forwarding from the first network hop to the corresponding second network hop using at least the corresponding flow label. The method further includes determining a queue of additional network hops to be validated based on a result of the validation process, and iteratively validating packet forwarding for each additional network hop in the queue.