Quantitative predictions of the behavior of many deterministic systems are uncertain due to ubiquitous heterogeneity and insufficient characterization by data. We present a computational approach to quantify predictive uncertainty in complex phenomena, which can be modeled by (partial) differential equations with uncertain parameters exhibiting multi-scale variability. The approach is motivated by flow in random composites whose internal architecture (spatial arrangement of constitutive materials) and spatial variability of properties of each material are both uncertain. The proposed two-scale framework combines a random domain decomposition (RDD) and a probabilistic collocation method (PCM) on sparse grids to quantify these two sources of uncertainty, respectively. The use of sparse grid points significantly reduces the overall computational cost, especially for random processes with small correlation lengths. A series of one-, two-, and three-dimensional computational examples demonstrate that the combined RDD-PCM approach yields efficient, robust and nonintrusive approximations for the statistics of diffusion in random composites.