Neural architecture search (NAS) advances beyond the state-of-the-art in various computer vision tasks by au- tomating the designs of deep neural networks. In this paper, we aim to address three important questions in NAS: (1) How to measure the correlation between architectures and their performances? (2) How to evaluate the correlation between different architectures? (3) How to learn these cor- relations with a small number of samples? To this end, we first model these correlations from a Bayesian perspective. Specifically, by introducing a novel Gaussian Process based NAS (GP-NAS) method, the correlations are modeled by the kernel function and mean function. The kernel function is also learnable to enable adaptive modeling for complex correlations in different search spaces. Furthermore, by in- corporating a mutual information based sampling method, we can theoretically ensure the high-performance architec- ture with only a small set of samples. After addressing these problems, training GP-NAS once enables direct per- formance prediction of any architecture in different scenar- ios and may obtain efficient networks for different deploy- ment platforms. Extensive experiments on both image clas- sification and face recognition tasks verify the effectiveness of our algorithm.