  Deep Neural Networks (DNNs) are becoming integral components of real world
services relied upon by millions of users. Unfortunately, architects of these
systems can find it difficult to ensure reliable performance as irrelevant
details like random initialization can unexpectedly change the outputs of a
trained system with potentially disastrous consequences. We formulate the model
stability problem by studying how the predictions of a model change, even when
it is retrained on the same data, as a consequence of stochasticity in the
training process. For Natural Language Understanding (NLU) tasks, we find
instability in predictions for a significant fraction of queries. We formulate
principled metrics, like per-sample ``label entropy'' across training runs or
within a single training run, to quantify this phenomenon. Intriguingly, we
find that unstable predictions do not appear at random, but rather appear to be
clustered in data-specific ways. We study data-agnostic regularization methods
to improve stability and propose new data-centric methods that exploit our
local stability estimates. We find that our localized data-specific mitigation
strategy dramatically outperforms data-agnostic methods, and comes within 90%
of the gold standard, achieved by ensembling, at a fraction of the
computational cost
