Informally, a 'spurious correlation' is the dependence of a model on some\naspect of the input data that an analyst thinks shouldn't matter. In machine\nlearning, these have a know-it-when-you-see-it character; e.g., changing the\ngender of a sentence's subject changes a sentiment predictor's output. To check\nfor spurious correlations, we can 'stress test' models by perturbing irrelevant\nparts of input data and seeing if model predictions change. In this paper, we\nstudy stress testing using the tools of causal inference. We introduce\ncounterfactual invariance as a formalization of the requirement that changing\nirrelevant parts of the input shouldn't change model predictions. We connect\ncounterfactual invariance to out-of-domain model performance, and provide\npractical schemes for learning (approximately) counterfactual invariant\npredictors (without access to counterfactual examples). It turns out that both\nthe means and implications of counterfactual invariance depend fundamentally on\nthe true underlying causal structure of the data -- in particular, whether the\nlabel causes the features or the features cause the label. Distinct causal\nstructures require distinct regularization schemes to induce counterfactual\ninvariance. Similarly, counterfactual invariance implies different domain shift\nguarantees depending on the underlying causal structure. This theory is\nsupported by empirical results on text classification.\n