Query complexity of log-concave sampling
From OpenAI Aftermath
Query complexity of log-concave sampling concerns how many evaluations of a potential V and its gradient an algorithm needs to produce a sample close to the density proportional to e−V. For well-conditioned potentials on Rd, with a known minimizer and Hessian between the identity and twice the identity, discretizations of Langevin and Hamiltonian dynamics gave query bounds that grow like a fixed power of the dimension, such as d1/3 and, in 2026, d1/6 expected queries, while a lower bound of order log d was known. A manuscript in OpenAI's public mathematics collection (github.com/openai/math), listed as its result 139 and dated 26 September 2026, claims that for every fixed ε > 0 at most Cεdε exact value-and-gradient queries suffice on every run for total-variation accuracy 1/10, and that Ω(log d) queries are necessary, so that the optimal dimension exponent is zero. The collection includes a Lean formalization of both bounds.
Background
- As recounted in the introduction of the manuscript:
- Nonasymptotic analyses of the unadjusted Langevin algorithm are due to Dalalyan and to Durmus and Moulines; Cheng and coauthors analyzed the underdamped method, and randomized midpoint discretization improved the Wasserstein guarantees. The shifted-composition analysis of Altschuler and coauthors and a path-space rejection approach of Chen and coauthors give about d1/3 queries at fixed conditioning and total-variation accuracy.
- Chen and coauthors obtained about d1/6 expected gradient queries at fixed relative-entropy accuracy with a smoothed Picard method, and a subsequent preprint of 30 September 2026 by Chen and coauthors improved the high-accuracy dimension dependence to about d1/5; the manuscript describes the smoothed Picard work as a close methodological precedent. The Gaussian conditional-sampling framework is due to Lee and coauthors.
- High-order integration and polynomial collocation reduce the dimensional dependence of Hamiltonian Monte Carlo under stronger regularity or structural assumptions than the two-sided Hessian bounds.
The original results
- Claim. Theorem 1.1 of Subpolynomial query complexity for well-conditioned log-concave sampling states that, in an oracle model where algorithms may be randomized and adaptive and computation between queries is unrestricted, for every ε > 0 there is Cε such that the worst-case number of exact value-and-gradient queries needed for total-variation accuracy 1/10 is at most Cεdε for d ≥ 2, on every execution, and that it is at least c log d for large d, so the optimal dimension exponent is zero. The manuscript states that the result determines the exponent but not the finer growth rate, does not assert a polylogarithmic query count, and imposes or deduces no arithmetic or bit-complexity bound.
- Method, as described: Gaussian proximal conditioning reduces the problem to sampling small perturbations; Gaussian smoothing with all-split tensor estimates controls high derivatives; recursively nested noisy conditional means are implemented with finitely many queries to the original gradient, and the auxiliary noise is removed by a contraction argument. The logarithmic lower bound follows the strategy of earlier work of Chewi and coauthors.
- Formalization, as described by the repository. The scope note states that the formalized result determines the dimension exponent of exact value-and-gradient query complexity: the least worst-case budget for total-variation error at most 1/10 is at most Cεdε for every ε > 0 and at least c log d eventually, for measurable, randomized and adaptive algorithms, with arithmetic and bit costs not bounded. The Comparator statement is
LogConcaveQuery.lean. - Source (openai/math repository, commit
7ef5c0c): Subpolynomial query complexity for well-conditioned log-concave sampling, dated 26 September 2026.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 30 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | Subpolynomial queries for log-concave sampling, an article of the Latent Seminar blog at lowrank.github.io | Reading (exposition) | Explains the claimed zero dimension exponent for exact first-order query complexity: a Gaussian example showing the source of difficulty, proximal conditioning that creates a small perturbation, Gaussian smoothing with controlled high derivatives, a recursive implementation without an exact-mean oracle, the contraction and removal of the noise, and why logarithmically many queries remain necessary. | Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit c76f1e4, 14 October 2026) |
Review (fidelity of the formal statements) | Rates this family "full" and records a sandboxed Comparator pass for LogConcaveQuery. Its note states that the claim concerns the number of exact value-and-gradient queries only, with no time or bit-cost statement, as in the summary, and it lists the hand-written oracle model, which is non-uniform in the dimension, as the definitions to check. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K, run 38040214623 | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the LogConcaveQuery solution, in 1,360 s. C. Toledo's report lists the challenge among those certified by both kernels. |
Repository. |
| 2026-10-16 | AI Proved What?, episode 139 Sampling with almost no queries?, remade version of 26 October 2026 | Reading (exposition) | Video explainer of the claim that, for potentials on d-dimensional space with V of 0 equal to 0, gradient 0 at 0 and curvature between 1 and 2 in every direction, C epsilon times d to the power epsilon exact value-and-gradient queries suffice on every run, not just on average, to sample within total variation 1/10, so that the best exponent of d is zero, and that at least a constant times log d queries are needed. The episode states that no arithmetic or running-time bound is claimed, that the constants of the upper bound are not given and are astronomical by its reading, that nothing is claimed for other curvature windows or accuracies, and that with the constant in the proof the lower bound rules out one-query algorithms only beyond about 2 times 10 to the 12 dimensions. | Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as a preprint: OpenAI, 55 pages, dated September 26, 2026; under expert review: not yet; peer reviewed: not yet; checked in Lean: the upper bound, the logarithmic lower bound and the zero exponent; the site has not run the check. The page states that the preprint has not been revised, noting that it cites a September 30 preprint as subsequent, that the Lean formalization has 326 files and 63,748 lines with its imports and no unproved steps that it could find, that the paper is not among those OSVerify reviewed, and that it has seen no expert review. |
Notes
- The background summarizes the manuscript's own account of earlier work.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
