Why call it a stack if it is ranked?

The name is historical. Implementations need operations for selecting good candidates and often removing poor ones, beyond ordinary push and pop.

Is it identical to level-by-level beam search?

No. A single ranked collection can contain candidates at different depths, whereas a conventional beam often groups candidates by step.

Does a larger capacity guarantee a better user-facing answer?

No. It changes the explored search space, but the score may still be an imperfect measure of the user's intended quality.

AI Glossary / Graphs and symbolic AI / Intermediate

Stack search

Definition

Stack search is a search strategy that keeps a ranked collection of partial solutions, repeatedly expands a promising candidate, and inserts the resulting extensions. In a memory-limited form, it retains only a bounded number of candidates. The term is associated with stack decoding in areas such as language processing and sequential decoding, where a complete answer is built from a sequence of choices.

What it means

A partial solution might be the beginning of a sentence, a partial parse, or a partly decoded sequence. Its score estimates how promising it is relative to other candidates. The search develops one candidate while retaining alternatives that might later become preferable.
Despite the name, the collection is not necessarily a conventional last-in-first-out stack. Selecting the highest-scoring candidate requires an ordered or priority-based organization. Also, candidates can be at different depths or stages of completion, so their scores need to be meaningfully comparable. Simply preferring the newest partial answer would define a different strategy.

How it works

Initialize the candidate collection with an empty or starting hypothesis. Select the highest-ranked candidate. If it meets the stated completion condition, apply the stopping rule; otherwise generate valid extensions, score them, and return them to the collection.
A bounded version removes low-ranked candidates when the capacity limit is exceeded. That pruning saves storage but can permanently remove the route to the best answer. Some applications organize several separate candidate collections to compare hypotheses at similar stages. The scoring function, pruning policy, and termination condition are essential parts of the algorithm's behavior, not incidental settings.

Three practical examples

A statistical translation decoder can explore alternative partial word sequences before choosing a completed sentence under its model.
A parsing experiment can rank incomplete analyses and extend promising ones while managing the number retained.
A sequence-decoding demonstration can examine how a limited candidate collection trades search effort against the risk of discarding a useful path.

Think of it this way

Think of an editor maintaining a ranked tray of unfinished story outlines. The most promising outline is expanded, and the tray is reordered as more becomes known. The analogy is limited because search scores and completion rules must be explicit; an editor's intuition does not provide a formal guarantee that a discarded outline was inferior.

Worked example

Consider an original abstract search tree with larger scores preferred and a capacity of two candidates. The initial expansion produces partial candidates A with score 10, B with score 9, and C with score 8. Treat these partial scores as valid upper bounds on the best completed result below each candidate.
The capacity limit retains A and B and discards C. Expand A next. It produces partial A1 with score 7 and partial A2 with score 6. Together with B, the collection would contain B9, A1 at 7, and A2 at 6. Trimming to two retains B and A1.
Expand B. Its only extensions are complete results B1 with score 5 and B2 with score 4. The collection now contains A1 at 7, B1 at 5, and B2 at 4; trimming retains A1 and B1.
Expand A1. It produces one complete result with score 7. That result is highest in the remaining collection, so the stated top-complete stopping rule returns it.
However, suppose discarded C had a single completed result worth 8. The globally best result would have been 8, but the bounded search returns 7. Every partial upper bound was valid: A's true best was 7, B's was 5, and C's was 8. Accurate bound direction alone did not protect against capacity pruning.
Without that early deletion of C, after A is expanded the candidates would include B9, C8, A1 at 7, and A2 at 6. After examining B, C would become the most promising candidate and could produce the better result. The example isolates the effect of pruning rather than claiming to implement a particular language decoder.

Illustrative case study

In a fictional language-decoding laboratory, researchers compare several candidate limits using a fixed scoring model. They record when the chosen output changes and inspect whether the better-scoring reference hypothesis was never generated or was generated and later pruned.
That distinction helps separate model behavior from search limitations. The team also reviews linguistic quality because a higher model score does not automatically mean a better human judgment. This fictional experiment makes no claim of measured improvement.

Common misconceptions and mistakes

Stack search is not simply depth-first search using a last-in-first-out data structure. It is also not the same as beam-stack search, a separate method that combines beam search with backtracking.
Do not assume a bounded candidate collection preserves the best solution. Do not compare partial sequence scores of different lengths without understanding the scoring convention. Finally, finding the highest-scoring output under a model and finding the best answer for a user are separate questions; search quality and model quality can fail independently.

Business use

The concept helps teams understand why a system can miss an answer that its scoring model would have preferred. A search procedure may never reach that answer because of candidate limits, pruning, or an unsuitable comparison among partial hypotheses.
For evaluation, keep the scoring model fixed when studying search settings. Record candidate capacity, pruning behavior, completion rules, runtime, and output quality. If a benchmark provides a preferred answer, check whether the limitation is its model score or its elimination during search before choosing a remedy.

Check your understanding

If a partial candidate is pruned permanently, can its descendants later win the search without another route or explicit recovery mechanism?

Answer: No. They are no longer generated through that candidate. This is why irreversible pruning can remove the best solution.

Related terms

Beam search
Best-first search
Priority queue
Stack decoding
Partial hypothesis
Search pruning
Sequential decoding
Search error

Learn next

Next, rerun the worked example with capacity three. C survives the first trim, then can produce score 8 after B is explored. State exactly which candidates are kept at each step. Then distinguish permanent deletion from temporarily delaying a candidate that remains available for later expansion.

Sources

Wang and Waibel, Decoding Algorithm in Statistical Machine Translation: https://aclanthology.org/P97-1047/ Original paper PDF: https://aclanthology.org/P97-1047.pdf Jelinek, Fast Sequential Decoding Algorithm Using a Stack, original publication identifier: https://doi.org/10.1147/rd.136.0675

Previous: Stable model Next: Stacked generalization