In this paper, we propose a fast decoding algorithm to recognize a very large number of item names on a resource-limited embedded device. The proposed algorithm is based on a multi-pass search scheme. The algorithm is composed of a two-stage HMM-based coarse match and a detailed match. The two-stage HMM-based coarse match is aimed at rapidly selecting a small set of candidates that are assumed to contain a correct hypothesis with high probability, and the detailed match re-ranks the candidates by performing acoustic rescoring. The proposed algorithm is implemented on an in-car navigation system with a 32-bit fixed-point processor operating at 620MHz. The experimental result shows that the proposed method runs at maximum speed 1.74 times real-time on the embedded device while minimizing the degradation of the recognition accuracy for a 220K Korean Point-of-Interest (POI),recognition domain.