In this paper, we describe improvements to the CELP excitation model for speech coding at medium-low bit rates. The innovation signal in our coder is modeled by addition/subtraction of two codewords derived from the same stochastic codebook. An extremely efficient pre-selection procedure allows to choose the 'best' candidate codewords. The best couple of codewords is then selected among the pre-selected ones. The proposed method is amenable to the implementation of low complexity CELP coders based on stochastic excitation.