デコーダは全く翻訳されていない仮説から探索を始める．そして入力文Jの翻訳されていないフレーズを選択肢，翻訳モデルのフレーズ対を用いて翻訳候補を生成する．このとき，翻訳候補の確率を計算し，その翻訳候補のスコアとする．この動作を繰り返し翻訳を行う．しかし入力文が長くなる場合，用いるフレーズ対の組み合わせは莫大となる．したがって，翻訳候補を全探索し，最適な翻訳文を決定することは困難である．
そこで，現在，計算量を削減する方法として，ビームサーチ法とマルチスタック法を組み合わせた手法が一般に用いられている．
![\fbox{
\includegraphics[scale=0.5]{search.eps}
}](img134.png)