Investigating how people evaluate more or less complex explanations has been a focal point of research. However, previous studies have either focused on choice between a limited set of explanations or do not systematically quantify the explanations' complexity. We provide a new approach for modeling explanation selection that foregrounds the balance between observed and latent structure in the mechanism being explained. We combine a Bayesian framework with program induction, enabling coverage of unbounded partially observable model space through sampling, and reflecting how a simplicity bias emerges naturally in this setting. Through simulation, we identify two novel principles: (1) simpler explanations should be favored as latent uncertainty (the number of hidden variables) increases; (2) latent structure is attributed a larger role when the observable patterns become less compressible. We found that these principles were reflected in human judgments, indicating that people are sensitive to latent uncertainty when selecting between explanations.