The main problem is that the embeddings are getting larger and larger (1,000+ dimensions). The pressure is then on reducing memory use through techniques such as Product Quantization while not losing too much accuracy.

Once this is done, the search heuristics are not difficult (find the cells to explore and return nearest neighbors).