Estimating integrals of black-box, high-dimensional functions, from expectations and kernel mean embeddings to the softmax kernel in self-attention, is a basic subroutine in machine learning. Rank-1 lattice rules suit this setting: they query the integrand only at a fixed point set and need no gradients. When the
n points serve as a design matrix
X∈Rn×d for a feature map, however, computing
Ψ(X)⊤v or
Ψ(X)w for an elementwise nonlinearity
Ψ costs
O(nd) time and memory for any standard quasi-Monte Carlo point set. We study subgroup rank-1 lattices, whose Korobov generator
(1,t,…,td−1) uses a scalar
t of fixed multiplicative order
m. Splitting
Fn× into cosets of
⟨t⟩ reduces both maps to short cyclic correlations evaluated by FFT, giving exact results for arbitrary
Ψ in
O(nlogm) time and
O(n) memory, without forming
X. Since fixing
m falls outside classical component-by-component theory, we prove convergence directly: via resultants with the cyclotomic polynomial
Φm, the squared worst-case error in the Korobov space decays as
O(n−(α−1)/(m−1)) for prime
m≥d+1, and this threshold is exact. Using the splitting of
n in
Q(ζm), averaging over the
m−1 admissible generators improves the constant by a factor
Θ(m−1). Empirically, the subgroup lattice beats Gaussian and orthogonal random features and scrambled Sobol' and Halton points in 49 of 54 synthetic kernel-estimation settings and all 45 softmax-attention settings on nine real datasets, and builds a sample set with
d=2048,
n≈4.1×107 in 2.3 ms.