ibUMAP: Coherent and Scalable Field Evaluation for UMAP Optimization

Bin Chen; Yumeng Xue; Patrick Paetzold; Yunhai Wang; Oliver Deussen

cs.LGOct 1, 2026

ibUMAP: Coherent and Scalable Field Evaluation for UMAP Optimization

Authors: Bin Chen, Yumeng Xue, Patrick Paetzold, Yunhai Wang, Oliver Deussen

Organizations: University of Konstanz · Renmin University of China

Abstract

UMAP achieves scalable layout optimization through stochastic negative sampling. However, this stochasticity can lead to unstable embeddings across reruns and downstream reuse, as the estimated repulsive forces depend on the ordering of sampling events. We present ibUMAP, a coherent field-based alternative that evaluates attraction and repulsion from a shared embedding snapshot and applies them synchronously. Its degree-weighted repulsive field is motivated by the conditional expectation of negative sampling for a fixed embedding and represented by three scalar moments, which are evaluated efficiently on CPUs and GPUs using an interpolation-based FFT scheme. This formulation avoids explicit all-pairs computations while inducing optimization dynamics that differ from those of standard online UMAP. Controlled experiments show that synchrony and kernel capping alter the local-global fidelity trade-off, whereas FFT evaluation produces small average changes in final quality. End-to-end benchmarks show median speedups of 3.29x unseeded and 5.79x seeded over umap-learn on CPU, and 1.44x over cuML on million-scale datasets under unseeded GPU execution. These gains accompany greater run-to-run stability and measurable fidelity trade-offs.

Figures & tables

Figure 1: ibUMAP: from sampled in-place updates to coherent field evaluation. (a) From shared initial coordinates, UMAP negative-sampling events update the head immediately, whereas ibUMAP evaluates a radial repulsive field at one snapshot and applies updates together. (b) Particle-to-mesh (P2M) deposition, FFT convolution with a shared capped scalar kernel, and mesh-to-particle (M2P) interpolation reconstruct

\widetilde{R}_{i}

from three scalar moments.

Figure 2: Paired per-dataset quality changes (later minus earlier variant; 59 datasets, seed-averaged; higher is better). Blue improves, orange worsens; diamonds are medians; numbers at right count improving datasets; triangles mark points beyond each 97.5th-percentile axis range. ∗ G

\to

H changes attraction update and execution path; A

\to

H is the net change from UMAP. Means: Table 3 .

Figure 3: End-to-end speed and run-to-run stability. (a) CPU speedup over umap-learn under matching unseeded and seeded profiles and (b) unseeded GPU speedup over cuML and TorchDR: points are baseline/ibUMAP ratios of five-run median times and the legends give cross-dataset medians. (c) Paired 15-NN overlap differences across unseeded reruns on the same 66/71/66 pairs: positive values favor ibUMAP and diamonds mark cross-dataset medians. Colors denote the same baseline in all panels; only vertical positions in (c) are jittered.

Platform	Method	TW $\uparrow$	C $\uparrow$	NP $\uparrow$	RTA $\uparrow$	$\rho_{D}$ $\uparrow$
CPU	umap-learn	0.9901	0.9942	0.3699	0.7249	0.6072
	ibUMAP	0.9853	0.9950	0.3436	0.7023	0.5493
GPU	cuML	0.9892	0.9950	0.3635	0.7349	0.6295
	TorchDR	0.9873	0.9943	0.3768	0.7647	0.6706
	ibUMAP	0.9851	0.9950	0.3407	0.7217	0.5897

Table 1: Unseeded local and global fidelity on the common 66 datasets: medians of dataset-level five-run mean scores. Metrics match Section 4 ; higher is better. Bold marks the highest displayed score per CPU/GPU block, including rounding ties, not statistical significance.

Panel of Figure 4 — Figure 4: The first two scheduled unseeded UMAP runs on the same frozen input, colored by HDBSCAN assignments. Cluster colors are matched by maximum cell overlap; gray denotes noise in (a,b). Run 2 is rigidly aligned to Run 1 for display, without scaling; clustering uses the original coordinates. Panel (c) locates assignment changes on Run 1, distinguishing changes between clusters from transitions to or from noise. All 56,962 cells are shown on a common coordinate scale. This pair has distance correlation $\rho=0.935$ , ARI $0.615$ , and 19.78% changed assignments.

Appendix figures & tables24 assets

Supplementary material from the paper’s appendix.

Appendix

Quantity	Median	Range
Mean scheduled count, $\bar{c}_{i}/(md_{i}^{(v)})$	$0.986$	$0.984$ – $0.987$
First activations drawing $m-1$ negatives (share of entries)	$0.766$	$0.728$ – $0.862$
Total count at $t=1$ / mean over $t\geq 1$	$0.173$	$0.163$ – $0.261$
Minimum total count over $t\geq 10$ / mean over $t\geq 1$	$0.983$	$0.907$ – $0.989$
Maximum total count over $t\geq 1$ / mean over $t\geq 1$	$1.016$	$1.012$ – $1.099$
$E_{i}/(\bar{c}_{i}/n)$ , equal to the D–G balance / reference	$0.507$	$0.507$ – $0.508$

Appendix

Table 2: Replayed sampling calendars on the 59 mechanism datasets (

T=200

m=5

). Per-point quantities are summarized by their median within each dataset; epoch totals are per dataset. The table gives the median and range of these values across datasets.

Variant	TW $\uparrow$	C $\uparrow$	NP $\uparrow$	RTA $\uparrow$	$\rho_{D}$ $\uparrow$
A. UMAP	0.9718	0.9834	0.4281	0.7070	0.5627
B. Synchronous sampled	0.9630	0.9825	0.3973	0.7006	0.5366
C. Synchronous event expectation	0.9648	0.9829	0.4118	0.7001	0.5349
D. Direct degree-weighted field	0.9568	0.9470	0.4010	0.6463	0.3583
E. D + kernel cap	0.9594	0.9813	0.3756	0.7013	0.5396
F. E with default FFT	0.9598	0.9812	0.3760	0.7012	0.5379

Appendix

Table 3: Local (TW, C, NP) and global (RTA,

\rho_{D}

) fidelity under a fixed graph and initialization: means across 59 datasets after averaging optimizer seeds within each dataset. Higher is better. H, the production optimizer used in Sections 5 and 6 , differs from G in both attraction aggregation and execution path; its net effect is read against A (UMAP), not as one mechanism after G.

Comparison	TW	C	NP	RTA	$\rho_{D}$
B–A	$-0.0055$ (0)	$+0.0001$ (34)	$-0.0302$ (1)	$-0.0064$ (21)	$-0.0211$ (18)
C–B	$+0.0010$ (44)	$+0.0001$ (46)	$+0.0128$ (57)	$+0.0007$ (39)	$+0.0023$ (33)
D–C	$-0.0023$ (18)	$-0.0018$ (12)	$-0.0121$ (14)	$-0.0489$ (11)	$-0.1211$ (12)
E–D	$-0.0011$ (25)	$+0.0022$ (48)	$-0.0232$ (5)	$+0.0431$ (54)	$+0.1112$ (53)
F–E	$+0.0001$ (35)	$+0.0000$ (34)	$+0.0004$ (34)	$+0.0000$ (32)	$+0.0001$ (31)
G–F	$+0.0002$ (33)	$+0.0001$ (47)	$+0.0002$ (32)	$+0.0017$ (47)	$+0.0089$ (50)

Appendix

Table 4: Distribution of paired quality changes across 59 datasets. Each cell gives the median signed quality improvement and, in parentheses, the number of datasets with an improvement, computed before rounding. Positive values favor the later variant. A–H match Table 3 , and Figure 2 plots the underlying per-dataset changes. The final row is the additional sampled-repulsion clipping control.

Dataset	Variant	Final ratio	Far points	Peak ratio	Updates $>10$
CIFAR-10	All safeguards	1.46	0	11.8 (7)	12
	No repulsion-norm clip	1,940	555 (0.9%)	1,940 (200)	200
	No attraction damping	1.70	0	90.2 (2)	157
scDEED CART	All safeguards	1.02	0	18.6 (21)	38
	No repulsion-norm clip	93.9	483 (0.8%)	93.9 (200)	146
	No attraction damping	2.08	1 ( $<$ 0.1%)	296 (17)	175

Appendix

Table 5: Safeguard failure cases on the fixed inputs of the mechanism study (production optimizer H, one safeguard switched off at a time; seed 42, as all three seeds give bitwise-identical embeddings). Ratio: bounding-box area of all points over that of the 99% of points nearest the median. Far points lie beyond twice the 99% radius. The peak is the largest ratio after any of the 200 updates, with the update index in parentheses; the last column counts updates after which the ratio exceeds 10.

Figure 5: Safeguard failure cases. (a) Final embeddings of production ibUMAP and of the same optimizer without the repulsion-norm clip or without attraction damping. Each panel spans the full extent of its embedding at equal aspect; orange marks far points, the dashed rectangle bounds the 99% core, and the inset gives the bounding-box area ratio. (b) The same ratio after every update. Without the clip, escaped points persist to the end; without damping, displaced hubs dominate the layout for most of the run and return only as the learning rate decays.

Device	Order	TW	C	NP	Time
CPU	$p=2$	$+0.00000$ (16/30)	$+0.00001$ (18/30)	$+0.00025$ (16/30)	$1.103\times$
	$p=3$	$-0.00005$ (13/30)	$+0.00002$ (19/30)	$-0.00013$ (14/30)	$1.239\times$
CUDA	$p=2$	$-0.00009$ (11/30)	$+0.00002$ (21/30)	$-0.00036$ (13/30)	$1.012\times$
	$p=3$	$-0.00003$ (13/30)	$+0.00001$ (20/30)	$-0.00003$ (14/30)	$1.019\times$

Appendix

Table 6: Interpolation-order sweep on 30 datasets, paired against

p=1

. Each quality cell gives the median signed difference and, in parentheses, the number of datasets improved. The last column is the median ratio of optimizer wall time to

p=1

; values above one indicate a slowdown.

Variant	TW $\uparrow$	C $\uparrow$	NP $\uparrow$	RTA $\uparrow$	$\rho_{D}$ $\uparrow$
A	0.9541	0.9758	0.3413	0.6989	0.5420
B	0.9460	0.9728	0.3182	0.6941	0.5213
C	0.9485	0.9734	0.3327	0.6940	0.5202
D	0.9377	0.9149	0.3194	0.6405	0.3401
E	0.9416	0.9683	0.2968	0.6956	0.5269
F	0.9421	0.9683	0.2978	0.6960	0.5258

Appendix

Table 7: Family-weighting sensitivity check. Entries average dataset scores within each of the five families, then average the families equally. Variant IDs and metric directions match Table 3 ; deterministic seed reuse is handled identically.

Component	Recorded value
GPU	NVIDIA RTX A5000, 24 GiB class
Operating system	Linux 5.15.0-124, x86_64, glibc 2.31
Python	3.11.15
CPU	Intel Core i7-11700K, 8 cores / 16 hardware threads, 3.60 GHz nominal frequency
Host RAM	32 GB class ( MemTotal 31.2 GiB)
umap-learn / PyNNDescent	0.5.12 / 0.5.13

Appendix

Table 8: Recorded benchmark environment. Values describe the execution host, not the host used to prepare this manuscript.

Comparison	Size group	$n$	Median S	Median U	Wins S	Wins U
CPU/UMAP	All	66	5.792	3.286	60/66	60/66
CPU/UMAP	$N<10^{3}$	6	0.310	0.167	0/6	0/6
CPU/UMAP	$10^{3}\leq N<10^{4}$	13	5.724	3.832	13/13	13/13
CPU/UMAP	$10^{4}\leq N<10^{5}$	41	5.937	3.042	41/41	41/41
CPU/UMAP	$10^{5}\leq N<10^{6}$	5	7.310	4.077	5/5	5/5
CPU/UMAP	$N\geq 10^{6}$	1	5.253	4.466	1/1	1/1

Appendix

Table 9: End-to-end speed ratios, baseline/ibUMAP, summarized by dataset size. S: seeded; U: unseeded. “Wins” counts dataset-level ratios strictly greater than one. CPU/UMAP compares ibUMAP CPU with umap-learn; both GPU comparisons use ibUMAP CUDA.

Figure 6: Dataset-level end-to-end speed ratios for CPU (left) and GPU versus cuML (right). Each ratio compares matching seeded or unseeded profiles after taking each algorithm’s five-run median time. The horizontal line denotes equal runtime; values above it favor ibUMAP. Both axes are logarithmic. CPU and GPU contain 66 and 71 paired datasets per profile, respectively.

Implementation	$n$	Median ratio	$n_{\geq 10^{6}}$	Ratio $N\geq 10^{6}$	Identical
umap-learn	66	1.664	1	1.170	66/66
ibUMAP CPU	66	0.961	1	0.995	66/66
cuML	71	1.071	6	9.191	70/71
ibUMAP CUDA	71	1.306	6	11.718	71/71
TorchDR	66	1.136	1	1.044	66/66

Appendix

Table 10: Runtime cost and observed output identity of the seeded profile. Time ratios are seeded/unseeded, so values above one indicate a seeded runtime penalty. “Identical” counts datasets with identical full embedding hashes in all five seeded runs. The million-scale column has only one dataset for CPU and TorchDR.

Figure 7: CPU runtime cost of seeded execution. Each point is one dataset’s seeded five-run median time divided by its unseeded five-run median, with 66 datasets per implementation. Diamonds mark medians across datasets. The horizontal scale is logarithmic; ratios above one indicate a seeded runtime penalty. Vertical jitter separates points.

Figure 8: Absolute end-to-end runtime for both execution profiles: CPU versus umap-learn (left, 66 datasets) and GPU versus cuML (right, 71 datasets). Each point is a five-run median. Both axes are logarithmic. Connecting lines are visual guides across different datasets, not controlled size sweeps. Seeded and unseeded fitting paths can have markedly different costs on large GPU workloads.

Panel of Figure 9 — Figure 9: Shares of ibUMAP end-to-end time by stage: CPU (a, b; 66 datasets) and CUDA (c, d; 71 datasets) under both execution profiles. For each dataset, every stage’s five-run median time is divided by the sum of these medians. Unattributed time is the measured call time not covered by the recorded stages. Tick marks along the top edge mark dataset sizes. Areas between them are visual interpolations across different datasets, not controlled size sweeps, and the two 70,000-observation datasets are averaged. The horizontal axis is logarithmic and shared by all panels.

CPU: common 66 datasets
Method	Profile	TW $\uparrow$	C $\uparrow$	NP $\uparrow$	RTA $\uparrow$	$\rho_{D}$ $\uparrow$
umap-learn	Unseeded	0.9728	0.985230	0.3983	0.7254	0.5952
ibUMAP	Unseeded	0.9672	0.984801	0.3762	0.6961	0.5292
umap-learn	Seeded	0.9727	0.985119	0.3979	0.7286	0.6006
ibUMAP	Seeded	0.9673	0.984823	0.3758	0.6971	0.5306
GPU: common 66 datasets

Appendix

Table 11: Mean fidelity by profile and coverage. Dataset scores use the first seeded run or the five-run unseeded mean; datasets receive equal weight. Bold marks the best score within each block and profile.

CPU: common 66 datasets
Method	Profile	TW $\uparrow$	C $\uparrow$	NP $\uparrow$	RTA $\uparrow$	$\rho_{D}$ $\uparrow$
umap-learn	Unseeded	0.9901	0.994200	0.3699	0.7249	0.6072
ibUMAP	Unseeded	0.9853	0.995031	0.3436	0.7023	0.5493
umap-learn	Seeded	0.9902	0.994569	0.3677	0.7259	0.6031
ibUMAP	Seeded	0.9852	0.995017	0.3443	0.6995	0.5396
GPU: common 66 datasets

Appendix

Table 12: Median fidelity for the same blocks and profiles as Table 11 , using the first seeded run or the five-run unseeded mean per dataset. Common-set unseeded rows reproduce Table 1 with extra precision for C. Bold marks the best score before rounding.

Mean of paired differences
Comparison	Profile	$n$	$\Delta$ TW	$\Delta$ C	$\Delta$ NP	$\Delta$ RTA	$\Delta\rho_{D}$
CPU/UMAP	Seeded	66	$-0.0054$	$-0.0003$	$-0.0221$	$-0.0315$	$-0.0700$
CPU/UMAP	Unseeded	66	$-0.0056$	$-0.0004$	$-0.0221$	$-0.0293$	$-0.0660$
GPU/cuML	Seeded	71	$-0.0018$	$+0.0006$	$-0.0048$	$-0.0148$	$-0.0372$
GPU/cuML	Unseeded	71	$-0.0051$	$-0.0001$	$-0.0158$	$-0.0162$	$-0.0408$
GPU/TorchDR	Seeded	66	$-0.0041$	$+0.0012$	$-0.0269$	$-0.0421$	$-0.0870$

Appendix

Table 13: Means and medians of paired fidelity differences, ibUMAP minus baseline, on each pair’s full available set. Dataset-level scores are paired before aggregation: the first seeded run or the mean of five unseeded runs. Positive differences favor ibUMAP for all five metrics. C retains six decimals in the median panel to avoid rounding a small negative difference to zero.

Figure 10: Unseeded fidelity differences on the full available pairs: CPU/umap-learn (66 datasets), GPU/cuML (71), and GPU/TorchDR (66). Each point is ibUMAP’s five-run mean score minus the baseline’s; diamonds mark means across datasets. Positive differences favor ibUMAP. Horizontal scales differ between metrics and are shared across comparisons within each panel. Vertical jitter separates overlapping points.

Comparison	Profile	Blocks	$\Delta$ TW	$\Delta$ C	$\Delta$ NP	$\Delta$ RTA	$\Delta\rho_{D}$
CPU/UMAP	Seeded	22	$-0.0029$	$-0.0011$	$-0.0083$	$-0.0361$	$-0.0717$
CPU/UMAP	Unseeded	22	$-0.0029$	$-0.0016$	$-0.0077$	$-0.0290$	$-0.0608$
GPU/cuML	Seeded	24	$-0.0015$	$+0.0021$	$+0.0012$	$-0.0014$	$+0.0024$
GPU/cuML	Unseeded	24	$-0.0044$	$-0.0002$	$-0.0041$	$-0.0092$	$-0.0192$
GPU/TorchDR	Seeded	22	$-0.0071$	$+0.0023$	$-0.0195$	$-0.0268$	$-0.0496$
GPU/TorchDR	Unseeded	22	$-0.0068$	$+0.0017$	$-0.0195$	$-0.0274$	$-0.0500$

Appendix

Table 14: Collection-weighted mean fidelity differences on the full paired sets, using the explicit grouping above. Positive differences favor ibUMAP. The corresponding dataset-weighted means are in the mean panel of Table 13 .

Implementation	$n$	Neighbor overlap	Distance correlation	Procrustes RMS
umap-learn	66	0.6929	0.9454	0.002100
ibUMAP CPU	66	0.8369	0.9902	0.000753
cuML	71	0.7311	0.9826	0.001065
ibUMAP CUDA	71	0.8851	0.9983	0.000337
TorchDR	66	0.6851	0.9632	0.001345

Appendix

Table 15: Unseeded run-to-run stability. Each entry is a median across dataset-level median scores. Higher neighbor overlap and distance correlation, and lower aligned RMS, indicate greater stability.

Comparison	$n$	Overlap wins	Median $\Delta$ overlap	Corr. wins	Median $\Delta$ corr.
CPU/UMAP	66	58/66	$+0.1436$	52/66	$+0.0357$
GPU/cuML	71	67/71	$+0.1308$	68/71	$+0.0147$
GPU/TorchDR	66	66/66	$+0.1961$	62/66	$+0.0256$

Appendix

Table 16: Dataset-paired unseeded stability comparisons. Differences are ibUMAP minus baseline. A difference of medians in Table 15 need not equal the median of paired differences shown here.

Dataset	$N$	$D$
iris	150	4
wine	178	13
diabetes	442	10
foresttype	523	27
breast cancer	569	30
seismic	646	24

Appendix

Table 17: All 71 benchmark datasets and their processed shapes. The 66 unmarked entries form the common quality set in Table 1 . A dagger marks the five additional datasets evaluated only with cuML and ibUMAP CUDA; both profiles of the other implementations are resource-skipped.

Profile	Embedding	+ HDBSCAN	$\rho$	ARI	Changed	Exact
UMAP unseeded	15.436	16.076	0.937	0.611	20.80%	No
UMAP seeded	49.062	49.696	1.000	1.000	0.00%	Yes
ibUMAP unseeded	7.095	7.722	0.999	0.601	22.01%	No
ibUMAP seeded	7.099	7.736	1.000	1.000	0.00%	Yes

Appendix

Table 18: Complete CPU reuse summary. Times are five-run medians in seconds. Distance correlation

\rho

, ARI, and changed-assignment fraction summarize ten unordered run pairs. “Exact” denotes identical full coordinates and raw labels across all five runs within that profile.

Figure 11: Live demo interface after a repeated seeded ibUMAP run on a 20,000-cell subset. Left: parameters and execution mode. Center: embedding colored by HDBSCAN cluster, with noise in gray. Right: comparison with the previous run (here 0.0% changed assignments and an identical fingerprint), runtimes, cluster count, noise fraction, and cluster sizes.

Explore similar work

FastUMAP: Scalable Dimensionality Reduction via Bipartite Landmark Sampling
May 12, 2026Hongmin LiDimensionality Reduction Data Manifold
School of Life Science and Technology, Institute of Science Tokyo · 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550, Japan 2Department of Computational Biology and Medical Sciences Graduate School of Frontier Sciences, The University of Tokyo
On Out-of-sample Embedding in UMAP
Jun 3, 2026Mohammad Tariqul Islam, Jason W. FleischerRepulsive Distribution Unsupervised
Media Lab, Massachusetts Institute of Technology, Cambridge, MA · Electrical and Computer Engineering, Princeton University, Princeton, NJ
ScaleMAP: Preserving Local Density and Neighborhood Structure in Low-Dimensional Embeddings
May 28, 2026Rajas Poorna, Marcus T. CiceroneDimensionality Reduction Multiscale
Georgia Institute of Technology · School of Chemical and Biomolecular Engineering Georgia Institute of Technology · School of Chemistry and Biochemistry Georgia Institute of Technology

May 12, 2026, cs.LGJ/K move · Enter open · S save

FastUMAP: Scalable Dimensionality Reduction via Bipartite Landmark Sampling

Hongmin Li

School of Life Science and Technology, Institute of Science Tokyo · 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550, Japan 2Department of Computational Biology and Medical Sciences Graduate School of Frontier Sciences, The University of Tokyo

Dimensionality Reduction Data Manifold One-Shot Medical Landmark Detection Benchmark Datasets

Open paper AskPDF arXiv

Exploratory analysis of high-dimensional data rarely stops at a single embedding. In practice, analysts rerun dimensionality reduction after changing preprocessing, subsets, or hyperparameters, and standard nonlinear methods can quickly become the bottleneck. We introduce FastUMAP (Bipartite Manifold Approximation and Projection), a landmark-based method designed for this repeated-use setting. FastUMAP builds a sparse point-landmark fuzzy graph, computes a Nystrom spectral warm start from the induced landmark affinity, and then refines all sample coordinates with a UMAP-style objective on the bipartite graph. The landmark ratio r = m/n provides a direct way to trade runtime against fidelity. On 9 benchmark datasets spanning 178 to 70,000 samples, FastUMAP has the lowest runtime on 7 datasets in our reported default-implementation comparison on one workstation. On MNIST and Fashion-MNIST (n=70000), it runs in about 4.6 seconds, compared with about 73--75 seconds for Barnes--Hut t-SNE, while reaching 91.4% mean kNN accuracy versus 94.6% for the strongest accuracy baseline. FastUMAP is therefore best viewed as a fast option for repeated exploratory embedding, rather than as a replacement for accuracy-first methods.

Abstract

Explore similar work

FastUMAP: Scalable Dimensionality Reduction via Bipartite Landmark Sampling

On Out-of-sample Embedding in UMAP

ScaleMAP: Preserving Local Density and Neighborhood Structure in Low-Dimensional Embeddings