Manifold Sampling via Entropy Maximization

Cornelius V. Braun^* · Tilman Burghoff^* · Marc Toussaint

Technische Universität Berlin · Robotics Institute Germany
NeurIPS 2026 · ^*Equal contribution, authors in alphabetical order

Samples from MASEM-NHR (top row) and ground truth (bottom row) on five 2D benchmarks: connected disks, disconnected disks, seven lobes, sine and swiss roll. — **MASEM-NHR vs. ground truth on 2D benchmarks.** Black lines show equality constraints, green shaded areas the feasible region of the inequality constraints. MASEM allocates sample mass uniformly across disconnected components and along high-curvature manifolds.

Sampling from distributions on implicitly defined manifolds: prior work assumes that the feasible set is connected, but in practice it often decomposes into multiple disconnected components. We propose MAnifold Sampling via Entropy Maximization (MASEM) which uses a resampling scheme that maximizes the entropy of the empirical distribution based on \(k\)-nearest-neighbor density estimation, and improves over alternatives by an order of magnitude in Sinkhorn distance with competitive runtime.

Method

Goal Sample uniformly from a manifold that is only defined implicitly by constraints, which can be evaluated point-wise:

\[\Sigma := \{\, x \in \mathbb{R}^d \mid h(x) = 0,\ g(x) \le 0 \,\}\]

Challenge The manifold may be disconnected, with an unknown number of components. Local MCMC kernels cannot cross the infeasible gaps between components, so they cannot decide how much sample mass each component should receive.

Illustration of the sampling problem: local sampler chains move along an implicitly defined manifold.

MASEM solves this by adding an entropy-maximizing resampling step to any local constrained sampler:

1 · Project Random initial samples are projected onto the manifold with Gauss-Newton steps on the squared constraint violation.

2 · Mix A local constrained MCMC kernel, e.g. non-linear Hit-and-Run (NHR) or OLLA, mixes the samples within each component.

↻ Repeat

3a · Resample A \(k\)-nearest-neighbor estimate of the sample density gives samples in under-represented regions higher weights. Resampling by these weights moves mass toward a uniform allocation across components.

3b · Mix The local kernel mixes the resampled samples within each component again.

Theorem (simplified)

Assume the feasible set \(\Sigma\) splits into finitely many connected components and the local sampler mixes well within each component. Then, in the mean-field limit, every MASEM resampling step pulls the per-component sample mass \(\alpha_t\) toward the uniform (maximum-entropy) allocation \(\alpha^*\):

\[D_{\mathrm{KL}}\big(p_{\alpha_t} \,\|\, p_{\alpha^*}\big) \le C_0 \Big(1 - \frac{\tau}{p}\Big)^{2t}\]

\(\tau \in (0, p)\): resampling temperature · \(p\): intrinsic dimension of the manifold · \(t\): number of resampling steps.
Reaching \(D_{\mathrm{KL}} \le \varepsilon\) takes \(\mathcal{O}\big((\log(1/\varepsilon) + \log\log N)/\tau\big)\) steps in the worst case, for \(N\) particles.

The resampling step is modular and adds only a small runtime overhead to the underlying sampler.

Robotics samples

Feasible samples drawn with MASEM on robotics problems.

Grasp poses

robot arm grasp configurations

Motion paths

end-effector paths through an obstacle course

Humanoid poses

stable humanoid handstand configurations

Twister

multi-limb contact configurations on a Twister mat

Results

All curves show the mean and 95% confidence interval across seeds. Swipe wide figures sideways to see all panels.

Strong sampling at low cost

Local samplers like NHR and OLLA cannot move mass between disconnected components, so they stall at a high Sinkhorn distance. Once resampling starts, MASEM rebalances the components and converges to a distance that is an order of magnitude lower, without increasing constraint violation.

NHR OLLA SCMC Cluster-NHR MASEM-NHR (ours) MASEM-OLLA (ours)

MASEM-NHR samples on the disconnected disks benchmark. — **Disconnected disks.** MASEM-NHR samples, and Sinkhorn distance \(\mathcal{W}_2^2\), KL divergence and constraint violations over 5000 iterations.

Sinkhorn distance, KL divergence and constraint violations over 5000 iterations on the disconnected disks benchmark. — **Disconnected disks.** MASEM-NHR samples, and Sinkhorn distance \(\mathcal{W}_2^2\), KL divergence and constraint violations over 5000 iterations.

MASEM-NHR samples on the sine benchmark. — **Sine.** MASEM-NHR samples, and Sinkhorn distance \(\mathcal{W}_2^2\), KL divergence and constraint violations over 5000 iterations.

Sinkhorn distance, KL divergence and constraint violations over 5000 iterations on the sine benchmark. — **Sine.** MASEM-NHR samples, and Sinkhorn distance \(\mathcal{W}_2^2\), KL divergence and constraint violations over 5000 iterations.

Scaling with dimension

On a stress test with five disconnected components, MASEM achieves the lowest Sinkhorn distance as the dimension \(d\) grows. It also stays competitive in wallclock time with the baselines.

Sinkhorn distance versus ambient dimension with a fixed 2D manifold. — **Increasing ambient dimension.** The manifold dimension is fixed to 2 while \(d\) grows. The gap between MASEM and the baselines stays constant.

Wallclock time versus ambient dimension with a fixed 2D manifold. — **Increasing ambient dimension.** The manifold dimension is fixed to 2 while \(d\) grows. The gap between MASEM and the baselines stays constant.

Sinkhorn distance versus dimension with an increasing manifold dimension. — **Increasing manifold dimension.** Using an intrinsic manifold dimension of \(d-5\), MASEM outperforms NHR, OLLA and Cluster-NHR by an order of magnitude.

Wallclock time versus dimension with an increasing manifold dimension. — **Increasing manifold dimension.** Using an intrinsic manifold dimension of \(d-5\), MASEM outperforms NHR, OLLA and Cluster-NHR by an order of magnitude.

Robotics: motion planning with random obstacles

We sample constraint-satisfying spline trajectories for a 2D point mass through a course of 20 randomly placed obstacles. Without ground-truth samples, we report the feasible entropy and the entropy over homotopy classes: MASEM reaches the highest feasible entropy and covers more homotopy classes, i.e. more distinct routes through the obstacles.

50 sampled trajectories per method on the random-obstacle motion planning problem. — **Random obstacles** Qualitative Plots, 50 samples per method. MASEM-based approaches yield the highest sample entropy of all methods.

Feasible entropy, homotopy entropy, constraint violations and wallclock over iterations on the random-obstacle motion planning problem. — **Random obstacles** Feasible entropy, homotopy-class entropy, constraint violation and wallclock time.

Paper

Manifold Sampling via Entropy Maximization. Cornelius V. Braun, Tilman Burghoff, Marc Toussaint. NeurIPS 2026.
[PDF] [OpenReview]

If you find this work useful, please cite:

@inproceedings{braun2026manifold,
  title={Manifold Sampling via Entropy Maximization},
  author={Cornelius V. Braun and Tilman Burghoff and Marc Toussaint},
  booktitle={The Fortieth Annual Conference on Neural Information Processing Systems},
  year={2026},
  url={https://openreview.net/forum?id=mAVz31YJlN}
}

Code

The code is available at github.com/LIS-TU-Berlin/masem.