Tail-Aware Repulsion Estimators for Heavy-Tailed t-SNE on GPUs

t-SNE is a method that draws high-dimensional data as a 2D map. Points that are neighbors in the original space attract each other, and all points push each other apart. How strongly two points still interact at large map distance is set by a "similarity kernel". If the kernel's tail is made heavier than standard t-SNE's Cauchy curve, the map reveals finer structure: handwriting styles within an MNIST digit, or many more cell types in single-cell RNA data. Heavier tails also have a cost. Clusters fly far apart, the map's bounding box grows, and the fast approximations that make t-SNE practical become wasteful or inaccurate. The grid-based ones are hit hardest. In practice, the "zoom lens" of heavy tails is turned off precisely on the large datasets where it would be most useful.

This proposal starts from a simple scaling observation. As the tail gets heavier, more of each point's total repulsion comes from distant points and less from nearby ones. The best way to estimate repulsion should therefore change with tail heaviness. We will build and test a GPU estimator designed around that shift. It computes near-field repulsion exactly from a spatially sorted neighbor list and estimates far-field repulsion by Monte Carlo sampling, with a coarse tree approximation used as a control variate, which is a cheap deterministic guess that is subtracted out so that only its error has to be sampled. The method needs no grid, so its memory cost does not depend on how far apart clusters drift. The headline question is whether it makes heavy-tailed t-SNE as fast and as faithful as standard t-SNE at million-point scale. Just as important, we ask whether a much simpler estimator, uniform negative sampling, already does so once tails are heavy.

Core Claim

The kernel family from Heavy-tailed kernels reveal a finer cluster structure in t-SNE visualisations is

$$k(d) = \left(1 + d^2/\alpha\right)^{-\alpha},$$

where $d$ is the distance between two map points and $\alpha$ controls the tail. Setting $\alpha = 1$ gives standard t-SNE, and smaller $\alpha$ gives a heavier tail. The repulsive force between two points then decays roughly as $d^{-(2\alpha+1)}$ at large distance.

Consider a 2D layout of roughly uniform density. The number of points at distance near $r$ grows like $r\,dr$, so the total repulsion magnitude from a ring at distance $r$ scales like $r^{-2\alpha}\,dr$. This has three consequences:

  • At $\alpha = 1$ the integral converges quickly, so repulsion is dominated by nearby points.
  • At $\alpha = 0.5$ it grows logarithmically, so near and far contribute comparably.
  • Below $\alpha = 0.5$ it is dominated by the far field.

Real layouts are clustered, and forces from opposite directions partly cancel, so this is a guide rather than a theorem. Measuring the actual near/far split on real embeddings is the first step of the program.

The claim follows from this argument. Grid methods pay for empty space between clusters, and tree methods make neighboring GPU threads take different branches. Both spend most of their effort on accuracy in regimes where heavy tails have made it either cheap or irrelevant. A hybrid that is exact near the point and sampled far from it should beat both at $\alpha \le 0.5$. The scaling also suggests a hypothesis about a known failure. The 1D filament collapse that Kobak et al. report below $\alpha = 0.5$ may be partly worsened by approximation error in exactly the far-field term that is starting to dominate. We will test this directly.

Relation to Prior Work

Work that motivates the gap. Heavy-tailed kernels reveal a finer cluster structure in t-SNE visualisations introduced the $\alpha$ family inside FIt-SNE, a version of t-SNE that computes repulsion by Fourier interpolation on an evenly spaced grid. The authors report that shrinking $\alpha$ inflates the bounding box and wastes grid points. They suggest tree or fast-multipole methods as a remedy but do not build one. We take that suggestion seriously and go further, asking whether trees are even the right tool once tails are heavy. Heavy-Tailed Symmetric Stochastic Neighbor Embedding supplies the original power-family generalization that we target.

Fast systems that hardcode $\alpha = 1$. Several systems accelerate t-SNE but fix the kernel to the Cauchy curve:

We reuse the Morton-code sort from the last paper, but only to build near-field neighbor tiles and a shallow coarse tree, not a deep traversal.

Work that supplies the method. Stochastic Barnes-Hut Approximation for Fast Summation on the GPU uses deterministic Barnes-Hut as a control variate for an unbiased path-sampling estimator. It reports 2x to 9.4x speedups over GPU Barnes-Hut on Coulomb and gravity sums over 3D meshes. It has never been tested on clustered embedding data, on 2D layouts, or on a kernel whose tail is a tunable parameter. Our contribution is not simply to apply it. We split near and far explicitly, choose the split radius from the measured tail behavior, and test the method inside an optimization loop, where gradient noise interacts with layout dynamics.

Work that sets up the main competitor. Force2Vec shows that force-directed layouts with sampled repulsion, mapped to sparse matrix–dense matrix products, scale to graphs with nearly a billion edges. That makes uniform negative sampling with an $\alpha$ kernel the simplest serious alternative. Our own scaling argument predicts it improves as $\alpha$ shrinks, so we treat it as a real threat rather than a straw man.

Outside our scope. Accelerating hyperbolic t-SNE and parametric heavy-tailed models such as t-SimCNE also need fast repulsion. We consider them only as future consumers of the estimator.

Research Program

Measurement. On exact $O(N^2)$ gradients for subsets of up to roughly 50,000 points, and along real optimization trajectories, we will measure how repulsion, and separately the normalization sum $Z = \sum_{ij} k(d_{ij})$, split across distance shells for $\alpha \in \{1, 0.7, 0.5, 0.3, 0.2\}$. This tests the scaling argument and tells us where the near/far boundary should sit.

Estimator. Map points are Morton-sorted each iteration. Near-field repulsion is computed exactly within fixed-size tiles of spatially adjacent points, which gives regular, divergence-free GPU work. The far field is estimated with a few hundred sampled partners per point, and a shallow Barnes-Hut summary serves as the control variate. Memory is linear in $N$ and independent of the bounding box. We will keep the estimator unbiased for both the force and $Z$. We will also use a variance-matched step size, so that gradient noise is controlled rather than ignored.

Stability study. At $\alpha < 0.5$ we will compare layouts produced by three gradients: exact, FIt-SNE, and our estimator, all from the same initialization. Suppose filaments appear only with approximate gradients. Then the instability is partly a numerical artifact, and the low-$\alpha$ regime is more usable than currently believed. Suppose they appear with exact gradients too. Then the instability belongs to the objective itself, and we report that as a constraint.

Baselines

Naive reference: standard t-SNE. The do-nothing option is standard $\alpha = 1$ t-SNE via t-SNE-CUDA, which reports MNIST in under 7 seconds and 1.2 million ImageNet activations in 486 seconds. It is the speed target a user would otherwise accept. Beating it on speed is not required. What we must show is that heavy-tailed layouts can be produced within a small constant factor, roughly 2x, of its wall-clock while preserving the extra structure.

Strongest existing method: FIt-SNE with variable $\alpha$. FIt-SNE as released by Kobak et al. is the only existing implementation that supports variable $\alpha$. It reports roughly 90–100 seconds on MNIST at 70,000 points across $\alpha$ values, on multi-threaded CPU. We will run it with its default and tuned grid settings on a 32-core CPU node, and run our method on one GPU. We will report both wall-clock and hardware-cost-normalized time, and stop each run at a matched final KL divergence rather than a fixed iteration count. Beating it means equal or lower final KL and nearest-neighbor preservation at $\alpha \le 0.5$, at lower wall-clock and with memory that does not grow with the bounding box. No reported result was found on Lacuna for FIt-SNE runtime or quality at $\alpha < 0.5$ beyond the qualitative instability note, so those numbers will be measured here.

Direct GPU port. We will port t-SNE-CUDA to the $\alpha$ kernel by changing the force formula and the summary-point accumulation. This is a deterministic Barnes-Hut competitor, and we will tune its opening angle $\theta$ over the same budget of trial runs as our method.

Sampling competitor. We will implement uniform negative sampling with the $\alpha$ kernel in the Force2Vec style and give it the same number of sampled partners per point as our far field.

Ablations. Two ablations isolate the key ingredients. The first removes the exact near field, which reduces the method to control-variate sampling only. The second removes the control variate, which leaves exact near field plus plain sampling.

Why not just…?

Why not just enlarge the FIt-SNE grid, or periodically rescale the map? Grid cost scales with bounding-box area. Kobak et al. themselves identify this growth as the bottleneck at small $\alpha$. Rescaling changes the effective kernel width unless it is undone exactly, which reintroduces the problem. Our benchmark sweeps $\alpha$ and records grid size, memory, and time. If FIt-SNE's cost stays flat down to $\alpha = 0.3$, this proposal's motivation is weaker than claimed, and we will say so.

Why not just port Barnes-Hut to the GPU with the new kernel? This is easy and is included as a baseline. The concern is that fragmented, tightly packed sub-clusters at small $\alpha$ make GPU threads diverge during tree descent. That is the failure documented in Stochastic Barnes-Hut for deterministic traversal. Profiling warp efficiency against $\alpha$ will show whether divergence actually worsens. If it does not, the simple port may suffice.

Why not just use uniform negative sampling? This is the most serious threat, because our own scaling argument predicts that sampling gets better as tails get heavier. Uniform sampling still rarely hits a point's immediate spatial neighbors, which carry the force that separates adjacent sub-clusters. The comparison with the "no exact near field" ablation settles this. It measures gradient error stratified by distance shell, and it checks whether fine structure appears, such as the italic versus upright MNIST ones or sub-type separation in the mouse cortex data. If uniform sampling matches our estimator at $\alpha \le 0.5$, we will recommend it and reframe the contribution as the measurement study explaining why.

Proposed Experiments

Datasets. We will use MNIST at 70,000 points, the adult mouse cortex single-cell data at 23,822 cells, and the 1.3-million-cell Mouse Brain dataset used by Chaudhary et al.. We will also use 128-dimensional SimCLR features of CIFAR-10, where t-SimCNE reports 89% 2D kNN accuracy for its end-to-end model, a useful quality reference point. HathiTrust will be added if it is accessible.

Metrics. We will report:

  • relative gradient error against exact gradients on subsets;
  • final KL divergence;
  • kNN preservation and 2D kNN class accuracy;
  • the number of clusters found by a fixed density-based clustering of the map, along with its agreement with the expert labels;
  • wall-clock time to matched KL, and peak memory, as functions of $\alpha$ and $N$.

Decisive checks. Three results settle the proposal:

  1. Whether the measured near/far force split tracks the predicted $r^{-2\alpha}$ trend.
  2. Whether our estimator beats both FIt-SNE and uniform sampling at $\alpha \in \{0.5, 0.3\}$ on time-to-matched-quality for the 1.3M-cell dataset.
  3. Whether filaments below $\alpha = 0.5$ persist under exact gradients.