Un factor que afecta la eficiencia de los algorimos de búsqueda local es el tamaño de la vecindad. Si se consideran muchos vecinos la búsqueda es muy costosa, especialmente si se requieren muchos pasos antes de llegar a un óptimo local, o si el costo para evaluar la función objetivo es muy alto.
La idea de fast local search es ignorar vecinos que probablemente no mejoren la función objetivo.
La vecindad se divide en sub-vecinos a los cuales se les asigna un bit de activación.
La idea es revisar sólo los sub-vecinos cuyo bit de activación sea 1.
Inicialmene todos los bits están activos. Si un sub-vecindario es probado que no tiene movimienos que produzcan alguna mejora, entonces se desactiva.
La división de la vecindad en subvecindades depende del problema. Algo que se puede hacer es revisar cómo se escanean los vecinos y si estos se hacen con fors anidados, entonces se pueden juntar los elementos dentro de un loop.
La decisión de si se mejora o no la función objetivo debe de considerar si existe algún cambio en los elementos de la función y no sólo el resultado final.
El principal problema de búsqueda local es que queda atrapado es mínimos locales. Se han propuesto una gran cantidad de algoritmos para aliviar esto. Lo que sigue es una descripción de algunos extensiones a búsqueda local para hacerla más efectiva.