Does a larger beam guarantee a better answer?

No. It changes search effort and opportunities, but outcomes depend on the model and procedure.

Can two beam members come from the same parent?

Yes. Their successors compete in the shared pool.

Is sampling proportional to raw score mandatory?

No. It is one possible rule when scores are suitable; other valid increasing weight functions can be used.

AI Glossary / Graphs and symbolic AI / Intermediate

Stochastic beam search

Definition

Stochastic beam search is a search approach that maintains a limited collection of candidates and chooses the next collection partly at random, favoring better-scoring candidates. In the local-search meaning used here, successors from the current collection are pooled and sampled to form the next beam. Random selection can preserve alternatives that deterministic selection of only the highest scores would discard.

What it means

A beam is a bounded set or collection of candidates, often described by its width k. Deterministic local beam search retains the best k successors under its scoring rule. The stochastic version gives other candidates a chance, while still using scores to influence selection.
The term also appears in specialized sequence-sampling research with more specific algorithms and guarantees. Those meanings should not be assumed to follow from the broad local-search description. An implementation must state how scores become sampling weights, whether sampling uses replacement, and how duplicate candidates are treated. These choices can materially change the search.

How it works

Begin with a collection of candidate states. Generate their valid successors and score the resulting pool. Convert the scores into nonnegative selection weights or another valid probability rule that favors desirable candidates. Sample the next beam according to that rule, then repeat until a specified stopping condition is met.
Pooling allows successors from one current state to occupy several beam positions. This differs from independent searches that each retain their own fixed position. Randomness can help maintain variety, but it does not guarantee diversity or global optimality. A separate record of the best state found can be useful when the next sampled beam omits it.

Three practical examples

A scheduling experiment can maintain several complete schedules and sample among their neighboring alternatives.
A puzzle optimizer can compare deterministic top-k selection with score-biased sampling under the same evaluation budget.
A configuration-search prototype can study how beam width and sampling strength affect exploration of different promising regions.

Think of it this way

Think of selecting several proposals for further development through a weighted draw: strong proposals receive more chances, but the highest-ranked proposals do not automatically take every place. The analogy is limited because the weights are mathematical design choices, not objective probabilities that a proposal will ultimately succeed.

Worked example

Consider an original local-search example with beam width two. The successor pool contains four distinct candidates: A with positive selection weight 6, B with weight 3, C with weight 2, and D with weight 1. For this example only, the weights are also the scores to maximize.
Specify sampling without replacement: draw one candidate in proportion to its weight, remove it, then renormalize the remaining weights for the second draw. The first-draw probabilities are A = 6/12, B = 3/12, C = 2/12, and D = 1/12.
Suppose C is drawn first. The remaining total weight is ten, so the second-draw probabilities become A = 6/10, B = 3/10, and D = 1/10. A possible next beam is therefore C and A, even though deterministic top-two selection would retain A and B.
The probability of obtaining the unordered pair A and C is the sum of its two draw orders. Drawing A then C has probability (6/12) × (2/6) = 1/6. Drawing C then A has probability (2/12) × (6/10) = 1/10. Together they give 4/15, approximately 26.7%.
Assume, as a stipulated continuation, that A and B lead only to completed results scoring at most seven, while C has a successor scoring ten. Keeping C can preserve a useful route that deterministic selection would lose at this step. The weights alone do not reveal that future fact, and the stochastic method can still fail to select C.
The method can also omit A. Summing the probabilities of pairs B - C, B - D, and C - D under the same sequential rule gives approximately 18.8%. If retaining the best observed candidate is required, that must be implemented explicitly; it is not guaranteed by weighted sampling.
With replacement, duplicate selections and pair probabilities would differ. The calculations above therefore describe the stated sampling rule, not every algorithm called stochastic beam search.

Illustrative case study

In a fictional configuration-optimization project, a team finds that deterministic beams repeatedly contain near-identical candidates. It tests weighted sampling and records both objective values and a task-specific measure of candidate diversity.
The team repeats runs with different random seeds, keeps the evaluation budget fixed, and retains a separate best-found record. It checks whether added variety produces useful outcomes rather than assuming that randomness itself is an improvement. This is an illustrative experiment, not a reported benchmark result.

Common misconceptions and mistakes

Stochastic beam search is not uniform random search: scores influence selection. It is also not guaranteed to preserve the highest-scoring current candidate unless an explicit retention rule does so.
Do not normalize arbitrary negative objective values directly into probabilities. The score-to-weight transformation needs a valid definition. Do not confuse increased sampling variety with guaranteed coverage of all important regions. Finally, results from a specialized sequence-sampling algorithm should not be attributed automatically to this broader local-search family.

Business use

The approach offers a practical way to examine the tradeoff between concentrating effort on current favorites and retaining alternatives. That can be useful when short-term scores are imperfect guides to later solution quality.
Report beam width, successor generation, weight transformation, replacement policy, duplicate handling, stopping rule, and random-seed practice. Compare distributions of results across runs rather than presenting one favorable run as typical. Include computation spent scoring discarded candidates, since a small retained beam does not necessarily imply cheap generation.

Check your understanding

Why is the probability of selecting A and C not just the probability of drawing A first and C second?

Answer: The same unordered beam also occurs when C is drawn first and A second. Both mutually exclusive orders must be counted.

Related terms

Local beam search
Beam width
Stochastic hill climbing
Genetic algorithms
Weighted sampling
Search diversity
Candidate pool
Random seed
Genetic algorithm

Learn next

Next, make all four weights equal while keeping sampling without replacement. Each unordered pair then has probability one sixth. Explain how this removes score preference, and distinguish equal selection probabilities from equal eventual solution quality.

Sources

Primary source: Russell and Norvig, AIMA, local beam search and stochastic beam search discussion: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap04.pdf . The specified sampling procedure, probability calculations, and future-score scenario are original illustrations.

Previous: Stochastic algorithm Next: Stochastic block model