arXiv:2610.07513v1 Announce Type: new Abstract: Approximating linear operators on high-dimensional spaces using only forward operator-vector product queries is a common but challenging task in scientific computing and machine learning arising when access to the adjoint action is experimentally unavailable or difficult to construct computationally. Existing query-efficient methods with polylogarithmic query complexity in the error tolerance rely on self-adjointness or access to the adjoint operator, while existing adjoint-free methods based on global low-order regularity have polynomial query complexity. We show that a priori local row-space information can be exploited for query-efficient, adjoint-free operator approximation, and that this information can be supplied by local high-order regularity estimates. Our approach first extends the fixed-sparsity matrix approximation algorithm of (Amsel et al., SIMAX, 2026) to approximating a matrix by one whose rows lie in prescribed subspaces, providing a general template for exploiting local row-space structure from forward queries alone. We then apply this framework to Hilbert-Schmidt integral operators with asymptotically smooth kernels. We establish asymptotic smoothness for Green's functions of canonical second-order elliptic PDEs in $d\leq 3$ dimensions including Poisson's equation in balls and constant coefficient equations on tori. In $d$ spatial dimensions, our algorithm uses $\mathcal{O}\big(\log(\varepsilon^{-1})\log^{d}(\varepsilon^{-1}\delta^{-1/2})\big)$ non-adaptive randomized queries to produce an $\varepsilon$-accurate approximation in Hilbert-Schmidt norm with probability $1-\delta$. This implies the error decreases as $\mathcal{O}\big( \exp(- c q^{1/(d+1)}) \big)$ in the query count $q$, which we observe in numerical experiments using tens to hundreds of queries to approximate solution operators of one-dimensional variable-coefficient second-order elliptic equations.