We present an efficient generalization of the sparse pseudo- input Gaussian pro- cess (SPGP) model developed by Snelson and Ghahramani (1), applying it to binary classification problems. By taking advantage of the S PGP prior covari- ance structure, we derive a numerically stable algorithm with O(NM2) training complexity—asymptotically the same as related sparse methods such as the in- formative vector machine (2), but which more faithfully represents the posterior. We present experimental results for several benchmark problems showing that in many cases this allows an exceptional degree of sparsity without compromis- ing accuracy. Following (1), we locate pseudo-inputs by gradient ascent on the marginal likelihood, but exhibit occasions when this is lik ely to fail, for which we suggest alternative solutions.