An approach is provided for global voice-based entry of location information. The approach involves partitioning a global speech decoding graph into spatial partitions. The approach also involves determining key entities occurring in each spatial partitions to construct a combined set of key entities. The approach further involves creating a retrieval index to map the key entities in the combined set of key entities to a corresponding partition. A first partition, the combined set of key entities, and the retrieved index are stored in a memory of a device for processing a voice input signal. A second partition that is not in the memory of the device is retrieved based on the combined set of key entities and the retrieval index to automatically re-process the voice input signal when an out-of-vocabulary result is obtained from the first partition.