  Ensembles of neural networks achieve superior performance compared to
stand-alone networks in terms of accuracy, uncertainty calibration and
robustness to dataset shift. \emph{Deep ensembles}, a state-of-the-art method
for uncertainty estimation, only ensemble random initializations of a
\emph{fixed} architecture. Instead, we propose two methods for automatically
constructing ensembles with \emph{varying} architectures, which implicitly
trade-off individual architectures' strengths against the ensemble's diversity
and exploit architectural variation as a source of diversity. On a variety of
classification tasks and modern architecture search spaces, we show that the
resulting ensembles outperform deep ensembles not only in terms of accuracy but
also uncertainty calibration and robustness to dataset shift. Our further
analysis and ablation studies provide evidence of higher ensemble diversity due
to architectural variation, resulting in ensembles that can outperform deep
ensembles, even when having weaker average base learners. To foster
reproducibility, our code is available: \url{https://github.com/automl/nes}
