For multimedia communications, the computational scalability of a multimedia codec is required to match with different working platforms and integrated services of media sources. In this paper, two condensed stochastic codebook search approaches are proposed to progressively reduce the computation required for the algebraic code excited linear predictive (ACELP) and multi-pulse maximum likelihood quantization (MP-MLQ) coders. By reducing the candidates of the codebook before search procedure, the proposed methods can effectively diminish the computation required for the ITU-T G.723.1 dual rate speech coder. Simulation results show that the proposed methods can save over 50 percent for the stochastic codebook search with perceptually intangible degradation in speech quality.