How do brains form stimulus-specific memories? We previously showed that in the fruit fly Drosophila, the odour-specificity of olfactory associative memories is enabled by sparse coding in the Kenyon cells of the mushroom body, i.e., only a small fraction of Kenyon cells responds to each odour. Too much Kenyon cell activity leads to failures to discriminate between similar odours, but too little activity could lead to detection failures – how do Kenyon cells achieve the correct ‘Goldilocks’ level of activity? The answer may lie in part in homeostatic plasticity: we found that the mushroom body circuitry homeostatically compensates for prolonged (4 d) excess inhibition, using a combination of reducing inhibition and increasing excitation. In addition, our computational models show that given the natural variability between Kenyon cells in network parameters governing excitability, the network performs best if variability in one parameter compensates for variability in another (e.g., Kenyon cells with few excitatory inputs have stronger excitatory inputs). Indeed, correlations predicted by our models appear in the fly connectome, and our experiments reveal cell-intrinsic activity-dependent compensation in Kenyon cells. Our results suggest that homeostatic plasticity and compensatory variability help maintain sparse coding for odour-specific memories.