What does beam width control?

It controls how many candidate states are retained for the next iteration.

Why is it different from independent hill climbing?

Successors from all current states compete in one pool, so some parent states may contribute no survivors.

Does stochastic selection remove all local traps?

No. It can preserve different possibilities, but outcomes still depend on the problem, selection rule, and search budget.

AI Glossary / Graphs and symbolic AI / Intermediate

Local beam search

Definition

Local beam search is a local-search method that keeps several candidate states at once. At each iteration, it generates their successors and selects the best few from the combined pool to form the next group. The number retained is called the beam width, commonly written k.

What it means

A single hill-climbing search follows one current state. Local beam search gives the search several current possibilities, but these possibilities compete for the same limited set of places in the next beam. A promising region can therefore gain several places while another region disappears.
This differs from running k independent hill climbers, each of which keeps its own successor regardless of what the others find. Local beam search shares selection across candidates. That sharing can concentrate effort effectively, but it can also eliminate diversity too early and leave all candidates exploring the same unpromising region.

How it works

Choose an initial collection of k states, often randomly. Generate successors of the current states, evaluate them, and retain k selected successors. In the basic deterministic version, selection favors the best evaluation values. Repeat until a goal or stopping condition is reached.
The evaluation direction must be explicit: some tasks minimize cost, while others maximize value. Implementations must also define tie handling, duplicate handling, and whether current states are eligible for retention. Stochastic local beam search changes selection by introducing probability biased toward better candidates rather than always taking the deterministic top k.

Three practical examples

A timetable search can maintain several complete candidate schedules and explore local changes that reduce conflicts.
A configuration optimizer can compare nearby variants of multiple candidate settings within a limited search budget.
A teaching experiment can show how collective successor selection differs from independent restarts, even with the same initial states.

Think of it this way

Think of a team investigating several routes, then assigning the next round's attention to the most promising discoveries from any investigator. One route may receive several assignments while another is abandoned. The analogy is limited because the algorithm follows a numerical evaluation and explicit successor rules rather than human judgment or actual parallel staffing.

Worked example

Consider an invented minimization problem with beam width k = 2. Lower scores are better. The current states are A with score 8 and B with score 9. For this trace, current states are not automatically retained, all successors are distinct, and the stated successor lists are complete.
A produces A1 with score 4 and A2 with score 5. B produces B1 with score 6 and B2 with score 7. Local beam search pools all four successors and keeps A1 and A2, the two lowest-scoring states. Both slots now come from A's region.
Two independent hill climbers would instead retain A1 from A and B1 from B. They do not allow A's second-best successor to replace B's best successor. This is the key difference, not whether the computations happen on one processor or several.
Now suppose A1 and A2 lead only to states scoring 4 or worse, while B1 has a successor B3 scoring 0, the global goal in this tiny invented search space. Because the local beam dropped B1, it will not discover B3 through that branch. The independent run retaining B1 can reach it in the next step.
This example does not prove that independent hill climbing is generally superior. A different successor structure could favor shared selection. It demonstrates that increasing the number of current states does not eliminate the risk of discarding a route that looks less attractive locally but leads to a better result later.
An implementation may preserve diversity or use stochastic selection, but such choices change the search behavior and should be documented rather than assumed to arise automatically from k = 2.

Illustrative case study

In a fictional scheduling project, Spruce Planner maintains ten candidate schedules but notices that all ten become nearly identical after several rounds. The team had interpreted the beam width as ten independent explorations.
Inspection shows that the candidates share most of their structure because deterministic selection repeatedly chooses neighbors of the same high-scoring schedule. The team records candidate diversity alongside the best score and compares alternative selection policies. This invented case illustrates a diagnostic approach, not a claim that any particular policy will improve every scheduling problem.

Common misconceptions and mistakes

Local beam search is not simply k unrelated restarts. The combined selection step lets one search region replace others. It also does not require k processors: a single program can evaluate candidates sequentially.
A wider beam does not guarantee completeness or an optimal answer. More candidates increase resource use and may still collapse into one region. Also, selecting k states does not necessarily limit temporary memory to exactly k states if an implementation materializes every successor before selection. Finally, local beam search over complete configurations should be distinguished from beam search over partial sequences in language generation.

Business use

The method is relevant when a candidate configuration can be scored and nearby alternatives generated, while exhaustive search is impractical. Define the score in terms of the actual objective and keep hard feasibility requirements separate from preferences where appropriate.
Compare beam widths and selection policies under equal computation budgets. Report the best result, variability across initializations, and how often the method fails to find an acceptable configuration. Check duplicates and candidate diversity if the beam appears large but behaves like one search. A successful run is evidence about that run and model, not a universal guarantee about the optimization problem.

Check your understanding

Why does the example retain A2 instead of B1 even though B1 is B's best successor?

Answer: Selection is global across the successor pool. A2's score 5 is better than B1's 6, so A2 takes the second available beam slot.

Related terms

Local search
Hill climbing
Beam width
Evaluation function
Genetic algorithms
stochastic local beam search
random restart
successor function
search diversity
genetic algorithm

Learn next

Repeat the worked selection with beam width 3 and note whether B1 survives. Then add a duplicate successor generated by both parents and decide how a distinct-state implementation should handle it. Compare the resulting exploration with two independent hill-climbing runs.

Sources

Russell and Norvig, original AIMA local-search slides, local beam search: https://aima.cs.berkeley.edu/slides-pdf/chapter04b.pdf

Previous: LLM Temperature Next: Local case-control sampling