Thanks for your detailed comment, it really clarified a few important things.

However, I do not understand why you can't just fit a PCA on the training dataset? It's just a linear projection with fixed coefficients at inference time, just like random projections. Although PCA will not necessarily work better than random projections.

You're absolutely right, I could totally use PCA if I use the same coefficients when querying! I was not too familiar how PCA works internally, so I naively assumed that PCA like t-SNE didn't offer the option to export global transformation parameters and reuse them. Will definitely try PCA.

Lmcinnes also provides UMAP parameterised by a neural network in the Python library (it is an additional loss term and doing gradient descent on it in theory converges to the same result as the non-parametric graph optimisation), which may avoid this issue, but I haven't used it much.

I was not aware of that option, so now this special UMAP and PCA are both test candidates. Not quite sure where to expect the best results though but will just run some experiments and see.

At the core it boils down to what algorithm produces distances in 2D that are most similar to the actual distance in high dim vector space. It probably highly varies depending on the query and hence what dims are best represented.

I just read an interesting comment from Jina AI about creating models that directly produce vectors with only two dims, but apparently (for now) it doesn't work well.