Subpolynomial query complexity for log-concave sampling

What OpenAI claims

For C2 potentials with a supplied minimizer and I ⪯ ∇²V ⪯ 2I, proves that sampling within total variation 1/10 requires only C_ε d^ε exact value-and-gradient queries for every fixed ε > 0. The bound holds on every run, with unrestricted computation between queries. A logarithmic lower bound also holds, so the optimal power-law exponent in this oracle model is zero. (Lean)

Paper

1. Subpolynomial query complexity for well-conditioned log-concave sampling

   26 September 2026 · Preprint, not peer reviewed · PDF

   For every fixed ε > 0, we give a sampling algorithm using at most C_ε d^ε exact first-order queries on every execution for C2 potentials on ℝd with a known minimizer and Hessian between Id and 2I_d. The output has total-variation distance at most 1/10 from the target Gibbs law. Computation between queries is unrestricted. We also prove an Ω(log d) query lower bound for arbitrary randomized adaptive algorithms, determining the optimal dimension exponent to be zero.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.