We describe an efficient framework for multiscale PDE problems that uses random sampling to capture low-rank local solution spaces arising in a domain decomposition framework. In contrast to existing techniques, our method does not rely on detailed analytical understanding of specific multiscale PDEs, in particular, their asymptotic limits. Our framework is applied to two specific problems - a linear kinetic equation and an elliptic equation with oscillatory media - for which recover the asymptotic preserving scheme and numerical homogenization, respectively. Numerical results confirm the efficacy of our approach.