Стремление преодолеть ограничения, связанные с нехваткой памяти, привело к тому, что в свое время предпочтение отдавалось алгоритмам, предусматривающим хранение в памяти только одного узла, но, как оказалось, такой подход часто является слишком радикальным способом экономии памяти. В алгоритме локального лучевого поиска предусмотрено отслеживание к состояний, а не только одного состояния. Работа этого алгоритма начинается с формирования случайным образом к состояний. На каждом этапе формируются все преемники всех к состояний. Если какой-либо из этих преемников соответствует целевому состоянию, алгоритм останавливается. В противном случае алгоритм выбирает из общего списка к наилучших преемников и повторяет цикл.

На первый взгляд может показаться, что локальный лучевой поиск с к состояниями представляет собой не что иное, как выполнение к перезапусков случайным образом, но не последовательно, а параллельно. Тем не менее в действительности эти два алгоритма являются полностью разными. При поиске с перезапуском случайным образом каждый процесс поиска осуществляется независимо от других. А в локальном лучевом поиске полезная информация передается по к параллельным потокам поиска. Например, если в одном состоянии вырабатывается несколько хороших преемников, а во всех других к-1 состояниях вырабатываются плохие преемники, то возникает такой эффект, как если бы поток, контролирующий первое состояние, сообщил другим потокам: "Идите все сюда, здесь трава зеленее!" Этот алгоритм способен быстро отказаться от бесплодных поисков и перебросить свои ресурсы туда, где достигнут наибольший прогресс.

В своей простейшей форме локальный лучевой поиск может страдать от отсутствия разнообразия между k состояниями, поскольку все эти состояния способны быстро сосредоточиться в небольшом регионе пространства состояний, в результате чего этот поиск начинает ненамного отличаться от дорогостоящей версии поиска с восхождением к вершине. Этот недостаток позволяет устранить вариант, называемый стохастическим лучевым поиском, который аналогичен стохастическому поиску с восхождением к вершине. При стохастическом лучевом поиске вместо выбора наилучших к преемников из пула преемников-кандидатов происходит выбор к преемников случайным образом, притом что вероятность выбора данного конкретного преемника представляет собой возрастающую функцию значения его оценки. Стохастический лучевой поиск имеет некоторое сходство с процессом естественного отбора, в котором "преемники" (потомки) некоторого "состояния" (организма) образуют следующее поколение в соответствии со "значением их оценки" (в соответствии с их жизненной пригодностью).