kd-trees don't work well for high-dimensional vectors, so when working with embeddings, you typically have to use something else.

This hasn't been true for multiple decades at this point. SIFT was originally predicated on best bin first searching through kd-trees to find aproximate nearest neighbors for vectors with over 4000 dimensions.

If you prioritize the bins you search by distance, you are are more likely to find closer points sooner. If you are finding a set number of closest points, then you will have a minimum distance to be included in the point set sooner. If that minimum distance is shorter than the distance to a bin, you can skip it.

If you have heuristics fast enough to make kd-trees competitive, it would be interesting to have them added to http://ann-benchmarks.com/

What do you mean by "heuristics"? What I described was how flann works.

It is not only on those benchmarks but is one of the reasons they exist in the first place, since it instigated a lot of the research into approximate nearest neighbors.

I'm working on a project using kd-tree for high-dimensional embeddings. Could you send me some pointers?

You will have to be more specific.