`random_state` does not make UMAP deterministic when the input contains duplicate rows

Summary

With random_state set, the docs state UMAP is reproducible ("prevent any stochastic behavior"). This holds for all-unique inputs, but breaks when the input contains duplicate (tied) rows: two seeded fit_transform calls on the identical array return different coordinates. Setting random_state already forces n_jobs=1 (UMAP warns it does), so this is not thread-count related.

Environment

python                3.13.7
platform              macOS-26.5-arm64-arm-64bit
umap-learn            0.5.12
numba                 0.65.1
numpy                 2.4.6
scikit-learn          1.9.0
sentence-transformers 5.5.1
torch                 2.12.0

Reproduction

Public data only (20 Newsgroups + all-MiniLM-L6-v2). One set is all-unique (control); the other is the same size but built from a 1500-doc base with 300 docs repeated 9x (2700 duplicate rows). Embeddings are computed once and reused, so the embedding model is not the variable.

import numpy as np
from sentence_transformers import SentenceTransformer
from sklearn.datasets import fetch_20newsgroups
from umap import UMAP

def fit(x):
    return UMAP(n_neighbors=15, n_components=5, min_dist=0.0,
                metric="cosine", random_state=42).fit_transform(x)

data = fetch_20newsgroups(subset="all", remove=("headers", "footers", "quotes"))["data"]
docs, seen = [], set()
for d in data:
    d = d.strip()
    if d and d not in seen:
        seen.add(d); docs.append(d)
    if len(docs) == 4200:
        break

model = SentenceTransformer("all-MiniLM-L6-v2")
control = model.encode(docs)                       # 4200 unique
base = docs[:1500]
treat = model.encode(base + [d for d in base[:300] for _ in range(9)])  # 1500 unique + 2700 dupes

a, b = fit(control), fit(control)
print("unique:    ", np.allclose(a, b), float(np.abs(a - b).max()))
c, e = fit(treat), fit(treat)
print("duplicated:", np.allclose(c, e), float(np.abs(c - e).max()))

Expected

Both lines print True 0.0 (identical output for identical seeded input).

Actual

unique:     True 0.0
duplicated: False 21.819...

The unique set is bit-identical; the set with duplicates is not (the exact max diff varies per run, but it is consistently nonzero). Deduplicating the rows restores determinism.

Likely cause

The approximate nearest-neighbor build (pynndescent) appears to break distance ties between identical points nondeterministically, and this is not controlled by random_state or n_jobs=1. Worth either fixing the tie handling or documenting that random_state does not guarantee reproducibility in the presence of duplicate rows.