Abstract The Stochastically Excited Linear Prediction (SELP) algorithm for speech coding offers good performance at bit rates as low as 4.8 kbit/s. Linear Predictive Coding (LPC) techniques remove the short-term correlation from the speech. A pitch loop removes long-term correlation, producing a noise-like residual, which is vector quantized. Information describing the LPC filter coefficients, the long-term predictor, and the vector quantization is transmitted. In this paper, we describe improvements to the SELP algorithm which result in better speech quality and higher computational efficiency. In its closed-loop form, the pitch loop can be interpreted as a vector quantization of the desired excitation signal with an adaptive codebook populated by previous excitation sequences. To better model the non-stationarity of speech we extend this adaptive codebook with a special set of candidate vectors which are transform of other codebook entries. The second stage vector quantization is performed using a fixed stochastic codebook. In its original form, the SELP algorithm requires excessive computational effort. We employ a new recursive algorithm which performs a very fast search through the adaptive codebook. In this method, we modify the error criterion, and exploit the resulting symmetries. The same fast vector quantization procedure is applied to the stochastic codebook.