In this paper, the simplified search designs for the stochastic codebook of algebraic code excited linear prediction (ACELP) for ITU-T G.729D speech coder are proposed. By using two search rounds and limiting the search range, the computational complexity of the proposed approach is only 6.25% of the full search method recommended by G.729D. In addition, the computational complexity of proposed approach is only 59% of the global pulse replacement search method recommended by G.729.1. Simulation results show that the coded speech quality evaluated by using the standard subjective and objective quality measurements is with perceptually negligible degradation.