REVIEW 3 major objections 3 minor 28 references
Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling
T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Under i.i.d. uniform hyperspherical embeddings, vMF-exp asymptotically samples each action with the same probability as Boltzmann Exploration while scaling to millions of actions.
desk verdict Solid asymptotic analysis of a simple, practical exploration method; the headline claim that it inherits B-exp's order preservation overstates what the expectation-level result supports. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the von Mises-Fisher distribution, a probability law on the unit sphere with density proportional to $e^{\kappa\langle V,\tilde V\rangle}$, whose exponent mirrors the softmax weight $e^{\kappa\langle V,X_i\rangle}$ that defines B-exp. Sampling $\tilde V$ and returning its nearest neighbor converts the discrete softmax into a geometric event: action $i$ is selected exactly when $\tilde V$ lands in $i$'s Voronoi cell, so $P_{\mathrm{vMF-exp}}(i)$ is the vMF mass of that cell. The asymptotic argument then leans on three tools: rotational symmetry of uniform sphere embeddings, which makes the expected Voronoi cell area $A(S^{d-1})/(n+1)$; the central limit theorem plus delta method for B-exp's softmax denominator; and Fisher–Tippett–Gnedenko extreme-value asymptotics on the largest inner product, which controls the first-order and remainder terms in the Taylor expansion of the vMF density over the shrinking cell.
What would settle it
Take a non-uniform but fixed unit-sphere embedding set, measure $P_{\mathrm{vMF-exp}}(a)$ and $P_{\mathrm{B-exp}}(a)$ for a state-action pair with large $|\langle V,A\rangle|$ as $n$ grows, and compare the ratio to Proposition 4.1: if the ratio does not approach 1, or the gap exceeds the $O(n^{-2/(d-1)})$ corrections of Propositions 4.3-4.4, the uniform assumption fails and the claimed asymptotic equivalence is restricted to that idealized regime. Alternatively, a simulation with i.i.d. uniform embeddings that violates Equation (16) would refute the central proposition directly.
Extended reading notes
Core claim
Under the theoretical setting of Section 4.1, in which the $n$ action embeddings are i.i.d. uniform on $S^{d-1}$, Proposition 4.1 states that the ratio of expected B-exp probability to expected vMF-exp probability for a fixed action $a$ converges to 1 as $n\to\infty$. Propositions 4.2 and 4.3 give the shared first-order approximation $P_0(a)=(f_{\mathrm{vMF}}(A\mid V,\kappa)\,A(S^{d-1}))/n$: the vMF density at $A$ times the average area of $A$'s Voronoi cell, divided by $n$, with B-exp converging as $o(1/(n\sqrt n))$ and vMF-exp as $O(1/n^{1+2/(d-1)})$ for $d>2$. Proposition 4.4 refines the vMF-exp rate in higher dimensions, showing that for large $d$ and fixed $\kappa$ vMF-exp explores slightly broader than B-exp. The authors read the ratio result as vMF-exp inheriting B-exp's order preservation and unrestricted radius while satisfying scalability, positioning it as a practical alternative to B-exp for action sets of millions of hyperspherical embeddings.
Load-bearing premise
The analysis assumes the action embeddings are independent and uniformly distributed on the unit hypersphere; real embeddings are not, and the paper's own experiments on word vectors show the gap between predicted and observed sampling probabilities grows as $|\langle V,A\rangle|$ increases.
Editorial extensions
If this is right
- At millions of actions, vMF-exp removes the need to compute all $n$ softmax weights: the per-decision cost is one constant-time vMF draw plus one approximate nearest-neighbor lookup.
- For large $n$, vMF-exp inherits B-exp's order preservation, so exploration probability increases with embedding similarity to the state, while every action keeps a strictly positive probability (unrestricted radius).
- In higher dimensions ($d\ge 20$), vMF-exp with the same $\kappa$ samples slightly more broadly than B-exp, giving practitioners a simple knob: accept the extra breadth or lower $\kappa$ to match B-exp's spread.
- The production recommender validation shows vMF-exp matching truncated B-exp in user engagement while yielding more diverse playlists, so the theoretical equivalence carries over to a deployed large-scale setting.
Reading between the lines
- Beyond the paper's setting, vMF-exp could serve as the exploration routine in contextual bandits and actor-critic systems with dynamically changing action sets, since nothing in the sampler depends on $n$ except the ANN index.
- The uniform-i.i.d. assumption is probably the binding constraint; extending the Voronoi-cell argument to clustered or non-isotropic embeddings would be the natural next step, and the public word-vector results suggest such an extension would need to track $\langle V,A\rangle$ more carefully.
- A testable engineering extension is a $\kappa$-calibration rule: given a target B-exp temperature, one could precompute the mapping $\kappa_{\mathrm{vMF}}(d,\kappa_B)$ so that vMF-exp matches B-exp's full probability vector rather than only the per-action ratio.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces von Mises-Fisher exploration (vMF-exp), a method that samples a hyperspherical vector from a vMF distribution centered on the current state embedding and then selects the sampled vector's nearest neighbor action. The authors claim that vMF-exp satisfies scalability (P1), unrestricted radius (P2), and order preservation (P3), and they prove that, under an i.i.d. uniform embedding assumption, the expected sampling probability of a given action converges to the same asymptotic value as Boltzmann exploration (B-exp), with explicit rates in Propositions 4.1--4.4. The empirical sections include Monte Carlo simulations, experiments on GloVe word embeddings, and a production deployment on the Deezer music streaming service.
Significance. If the main asymptotic equivalence holds, vMF-exp is a practically important contribution: it offers a scalable sampling procedure whose per-action probabilities match B-exp in the large-action limit without computing softmax values over the full action set. The paper's strengths include explicit asymptotic rates, a self-contained proof appendix, public reproducible code, and a real large-scale deployment with an online A/B test. The central weakness is that the paper overstates what the expectation-level results imply for the per-realization order-preservation property P3, which is defined for a fixed embedding set.
major comments (3)
- [Sections 3.2 and 4.2, Eqs. (4), (12), (14)--(16)]
- [Appendix A, Eqs. (27)--(31)]
- [Proposition 4.4, Eq. (20), and Appendix C.2.3]
minor comments (3)
- [Appendix C.1, Corollary C.6]
- [Appendix H.1]
- [Section 4.3, Figure 2 and Appendix G]
Circularity Check
No circularity: the vMF-exp asymptotics are derived from the stated uniform-embedding model, and the P3 inference gap is a validity limitation, not a circular reduction.
full rationale
The paper's central claim, Proposition 4.1, is obtained by derivation rather than by construction. Proposition 4.2 for B-exp follows from the CLT and Delta method applied to the empirical average of i.i.d. uniform embeddings, plus the vMF normalizing constant identity. Proposition 4.3 for vMF-exp follows from the expected Voronoi cell area (Lemma C.1), the expected normal vector (Lemmas C.2-C.3), and extreme-value asymptotics for the max inner product (Lemmas C.4-C.6, Corollary C.6). None of these lemmas takes the target equivalence P_B-exp/P_vMF-exp -> 1 as an input; the target is the output. No parameter is fitted to the predicted probabilities in the theoretical analysis: kappa is a hyperparameter common to both methods, and the papers' own equations define P0 and P1 from the model rather than from data. The self-citations in the paper (prior Deezer recommendation work, workshop versions of this method) are contextual background and are not load-bearing for the theoretical result. The paper's Appendix H honestly reports that GloVe vectors, which violate the i.i.d. uniform assumption, show deviations from the predicted probabilities that grow with |<V,A>|; this is a stated limitation of the assumptions, not evidence that the derivation is circular. One can question whether asymptotic equality of expected probabilities implies the per-realization order-preservation property P3, since Voronoi cell-area fluctuations can invert pairwise order on a non-vanishing fraction of realizations; however, that is a logical-strength gap in the interpretation, not an equation-level reduction of the claimed prediction to its own inputs. Under the review's standard of exhibiting a specific constructional equivalence, no circular step is present.
Assumptions & free parameters
free parameters (1)
- kappa
assumptions (5)
- domain assumption Action embeddings are i.i.d. uniform on S^{d-1} (Section 4.1, Eq. 13).
- domain assumption A nearest neighbor oracle returns the exact argmax in sublinear time (Section 2.1, Eq. 3).
- domain assumption Vectors have unit norm and inner product equals cosine similarity (Section 2.1).
- standard math Standard probabilistic facts: CLT, delta method, Fisher-Tippett-Gnedenko theorem, Taylor-Lagrange inequality.
- standard math The vMF normalization constant integrates to one over the hypersphere.
Cite this review
Pith. "Pith review of Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling." pith.science (2026). https://pith.science/paper/7XKIZTYM
@misc{pith2026250700518,
author = {Pith},
title = {Pith review of: Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling},
year = {2026},
howpublished = {\url{https://pith.science/paper/7XKIZTYM}},
note = {Machine review of arXiv:2507.00518}
}
read the original abstract
This paper introduces von Mises-Fisher exploration (vMF-exp), a scalable method for exploring large action sets in reinforcement learning problems where hyperspherical embedding vectors represent these actions. vMF-exp involves initially sampling a state embedding representation using a von Mises-Fisher distribution, then exploring this representation's nearest neighbors, which scales to virtually unlimited numbers of candidate actions. We show that, under theoretical assumptions, vMF-exp asymptotically maintains the same probability of exploring each action as Boltzmann Exploration (B-exp), a popular alternative that, nonetheless, suffers from scalability issues as it requires computing softmax values for each action. Consequently, vMF-exp serves as a scalable alternative to B-exp for exploring large action sets with hyperspherical embeddings. Experiments on simulated data, real-world public data, and the successful large-scale deployment of vMF-exp on the recommender system of a global music streaming service empirically validate the key properties of the proposed method.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[1]
(95) E. Link with Thompson Sampling At first glance, one might draw some similarities between vMF-exp and Thompson Sampling (TS) with Gaussian prior for contextual bandits (Chapelle & Li, 2011). Admittedly, vMF-exp shares a common spirit with TS, where action selection is preceded by sampling individual weights according to a Normal distribution centered ...
work page 2011
-
[2]
18 Exploring Large Action Sets with Hyperspherical Embeddings using von Mises-Fisher Sampling C. Asymptotic Behavior of vMF Exploration in d >2 dimensions (Proofs of Proposition 4.3, Part 2, and of Proposition 4.4) We now prove Proposition 4.3 when d >2, starting with a series of intermediary lemmas. We subsequently justify the approximate expression of P...
work page 1999
-
[5]
Douze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazar ´e, et al. The faiss library. arXiv preprint arXiv:2401.08281,
-
[6]
Z ˜V ∈SV orono¨ı(A|Xn+1) fvMF(A | V, κ)κ⟨V, ˜V − A⟩ d ˜V # (86) = fvMF(A | V, κ)κ ⟨V, E Xn∼U (S d−1)
For d = 3: vMF-exp explores the action A when ˜V lies in its V orono¨ı cell, shown in red. with R1( ˜V ) = P∞ i=2 (κ⟨V, ˜V −A⟩)i i! . Leveraging the linearity property of both integration and expectation (Jacod & Protter, 2004), we can study PvMF-exp(A | n, d, V, κ) by assessing separately the contribution of the different terms of the expansion of fvMF i...
work page 2004
-
[7]
Iwasaki, M. and Miyazaki, D. Optimization of indexing based on k-nearest neighbor graph for proximity search. arXiv preprint arXiv:1810.07355,
-
[10]
Interface of the “Mixes inspired by” recommender system on the music streaming service Deezer. To generate playlists, Deezer leverages a collaborative filtering model (Koren & Bell, 2015). This model learns unit norm song embedding representations of dimension d = 128 by factorizing a mutual information matrix based on song co-occurrences in various liste...
work page 2015
-
[12]
to infer that: √n[g(Dn) − g( 1 A(S d−1)Cd(κ) )] D − → N(0, σ2[g′( 1 A(S d−1)Cd(κ) )]2). (28) Replacing g and g′ by their respective values, we obtain: √n h 1 Dn − Cd(κ)A(S d−1) i D − → N(0, σ2(A(S d−1)Cd(κ))4). (29) Furthermore, recall that if a sequence Z1, Z2, ...of random variables converges in distribution to a random variable Z, then for all bounded ...
work page 2004
-
[15]
For every θ ∈ [0, 2π], we define RA,θ as the rotation around A of the angle θ
To do so, we will show that this average normal vector is invariant to any rotation aroundA. For every θ ∈ [0, 2π], we define RA,θ as the rotation around A of the angle θ. As discussed in the proof of Lemma C.1, Xn ∼ U(S d−1) ⇔ RA,θ(Xn) ∼ U (S d−1). Moreover, RA,θ(A) = A. Let us denote: N (A | n) = E Xn∼U (S d−1) h Z ˜V ∈SV orono¨ı(A|Xn+1) ˜V d ˜V i , (57...
work page 2009
Show all 28 references
-
[19]
and follows: fradial(t; κ, d) = (κ/2) d 2 −1 Γ( 1 2 )Γ( d−1 2 )I d 2 −1(κ) etκ(1 − t2) d−3 2 (97) This PDF can be used to sample r through rejection sampling (Gentle, 2009). F .4. Sampling ˜VO ˜VO can be obtained by following the steps of algorithm
2009
-
[20]
Algorithm 1 Sample ˜VO 1 - Sample vector U uniformly from S d−1; 2 - Compute projection of U on V : W = ⟨U, V⟩V ; 3 - Subtract projection and normalize: ˜VO = U −W ||U −W ||; 4 - return ˜VO Note that a simple way to sample U uniformly on S d−1 is to sample d standard Gaussians...
2009
-
[21]
We recall that PB-exp(a) and P0(a) are indistinguishable for this range of n values
We report complete results for the Monte Carlo simulations presented and discussed in Section 4.3, involving more combinations of d, κ, and ⟨V, A⟩). We recall that PB-exp(a) and P0(a) are indistinguishable for this range of n values. We emphasize that the y-axis is on a 1e-5 s...
2014
-
[23]
Performance of popular ANN algorithms on GloVe-25, extracted from the benchmark of Aum ¨uller et al. (2017). Following Simhadri et al. (2024), our performance metric is the maximum throughput, measured in Queries Per Second (QPS), for which the average recall of the exact top-...
2017
-
[24]
and the other from NMSLIB (Boytsov & Naidan, 2013), as well as ScaNN (Guo et al.,
2013
-
[25]
Exhaustive search is 2 to 3 orders of magnitude slower than ANN methods
and NGT-QG (Iwasaki & Miyazaki, 2018). Exhaustive search is 2 to 3 orders of magnitude slower than ANN methods. Algorithm Exhaustive Search HNSW (Faiss) HNSW (NMSLIB) ScaNN NGT-QG Maximum Throughput 34 6197 14080 23436 22733in Queries Per Second (QPS) 31 Exploring Large Action...
2018
-
[1943]
which states that if there exists a couple of sequences an and bn such that the left term of Equation (67) converges, then its limit should be the CDF of a Generalized Extreme Value distribution (GEV) with shape parameterγ, which is the right term of Equation (67). Theorem 5 o...
1943
-
[1948]
of fvM around θ0 and obtain: fvM(θ | κ) = fvM(θ0 | κ) + R0(θ), (41) where R0(θ) = P∞ i=1 f (i) vM (θ0|κ) i! (θ − θ0)i is the zero order remainder term of the Taylor series expansion of fvM near θ0. We can now estimate the portion of the integral of Equation(40) corresponding t...
1948
-
[1953]
distribution: ∀A ∈ Sd−1, fvMF(A | V, κ) = Cd(κ)eκ⟨V,A⟩, (23) where A(S d−1) is the surface area of S d−1, the d-dimensional unit hypersphere, and Cd(κ) is the normalizing constant. Proof. By definition, PB-exp(a | n, d, V, κ) = E Xn∼U (S d−1) eκ⟨V,A⟩ eκ⟨V,A⟩ + Pn i=1 eκ⟨V,Xi⟩ ...
2011
-
[1992]
Pennington, J., Socher, R., and Manning, C. D. Glove: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pp. 1532–1543,
2014
-
[2010]
Deep reinforcement learning in large discrete action spaces
Dulac-Arnold, G., Evans, R., van Hasselt, H., Sunehag, P., Lillicrap, T., Hunt, J., Mann, T., Weber, T., Degris, T., and Coppin, B. Deep reinforcement learning in large discrete action spaces. arXiv preprint arXiv:1512.07679,
-
[2011]
Adap-τ: Adaptively modulating embedding magnitude for recommendation
Chen, J., Wu, J., Wu, J., Cao, X., Zhou, S., and He, X. Adap-τ: Adaptively modulating embedding magnitude for recommendation. In Proceedings of the ACM Web Conference 2023, pp. 1085–1096,
2023
-
[2013]
We subtract the set’s average from each vector and divide them by their norms
from 2 billion tweets, represents a word token. We subtract the set’s average from each vector and divide them by their norms. We obtain a vector set, denotedG, with all vectors lying on the unit hypersphere, making GloVe-25 a relevant large-scale dataset for our study. Our ex...
2023
-
[2016]
Mixes inspired by
of playlists generated from the same initial selection, to assess how similar the songs sampled from the same state embedding were, for each method. Results reveal that TB-exp had an average Jaccard similarity 35% higher (less diverse playlists) than vMF-exp, a statistically s...
1999
-
[2018]
V ., Aum ¨uller, M., Ingber, A., Douze, M., Williams, G., Manohar, M
Simhadri, H. V ., Aum ¨uller, M., Ingber, A., Douze, M., Williams, G., Manohar, M. D., Baranchuk, D., Lib- erty, E., Liu, F., Landrum, B., et al. Results of the big ann: Neurips’23 competition. arXiv preprint arXiv:2409.17424,
-
[2019]
Mixes inspired by
for ANN. Currently, Deezer generates the entire playlist at once in production. The service is considering RL approaches to, instead, recommend songs one by one while adapting to user feedback on previous songs of the playlist (likes, skips, etc.). However, as explained in Sec...
2005
-
[2020]
Track mix generation on music streaming services using transform- ers
Bendada, W., Bontempelli, T., Morlon, M., Chapus, B., Cador, T., Bouabc ¸a, T., and Salha-Galvan, G. Track mix generation on music streaming services using transform- ers. In Proceedings of the 17th ACM Conference on Recommender Systems, pp. 112–115, 2023a. Bendada, W., Salha-...
2024
-
[2022]
A survey of exploration methods in reinforcement learning
Amin, S., Gomrokchi, M., Satija, H., van Hoof, H., and Pre- cup, D. A survey of exploration methods in reinforcement learning. arXiv preprint arXiv:2109.00157,
-
[2023]
An analysis of approaches taken in the acm recsys chal- lenge 2018 for automatic music playlist continuation
Zamani, H., Schedl, M., Lamere, P., and Chen, C.-W. An analysis of approaches taken in the acm recsys chal- lenge 2018 for automatic music playlist continuation. ACM Transactions on Intelligent Systems and Technology (TIST), 10(5):1–21,
2018
-
[2024]
von mises-fisher sampling of glove vectors
Bendada, W., Salha-Galvan, G., Hennequin, R., Bontem- pelli, T., Bouabc ¸a, T., and Cazenave, T. von mises-fisher sampling of glove vectors. In ICLR 2025 Workshop on Frontiers in Probabilistic Inference: Learning meets Sam- pling,
2025
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.