Maybe they use some sort of locality-sensitive hash to efficiently gather a set of (approximate) candidates that are close by in that embedding space, and then

Maybe they use some sort of locality-sensitive hash to efficiently gather a set of (approximate) candidates that are close by in that embedding space, and then use some heuristics to further narrow down who the most probable match is.