Skip to content
STIMSMITH

Beam Search

Concept WIKI v1 · 7/2/2026

Beam search is a heuristic search strategy that explores a fixed-width frontier of candidate solutions, commonly used to guide discrete-output generation and adversarial search. In program synthesis it is paired with encoder–decoder neural networks (PCCoder, RobustFill), and in adversarial machine learning it has been adapted for black-box image and text attacks.

Beam Search

Beam search is a heuristic search strategy that, instead of committing to a single best candidate at each step (as in greedy search), maintains the top-k highest-scoring partial candidates (the "beam") and expands them in parallel. This trades a modest amount of additional computation for a much broader exploration of the search space and consistently better final candidates than greedy search.

Use in Program Synthesis

In neural program synthesis, beam search is the standard decoding strategy used on top of encoder–decoder models. Two representative systems that follow this pattern are:

  • PCCoder — an encoder–decoder neural network that decodes programs with beam search.
  • RobustFill — an LSTM-based encoder–decoder that decodes programs with beam search.

In a comparative study of program-synthesis schemes (Table 4 of the GENESYS paper), PCCoder is summarized as "Encoder decoder (DNN) + Beam search" and RobustFill as "Encoder decoder (LSTM) + Beam search". Other schemes in the same table use different search or optimization strategies — for example DeepCoder uses a DNN function-probability model combined with depth-first search (DFS), NPO uses an autoencoder embedding with CMA-ES, PushGP and NetSyn use genetic algorithms, and Shgo uses simplicial global optimization — providing useful context for why beam search–based decoders are benchmarked against. The same experimental comparison reports that GENESYS synthesizes at least 1.1% and up to 31.3% more programs across program lengths of 5, 7, and 10 than the recent techniques including DeepCoder, PCCoder, RobustFill, PushGP, and NetSyn; for length-10 programs GENESYS synthesizes on average 28.1% more programs than those existing schemes.

Use in Adversarial Machine Learning

Beam search has also been repurposed as a black-box adversarial-attack search strategy, where a model's outputs are used to score perturbations and the beam keeps the most promising historical perturbations:

  • Reversible Adversarial Examples with Beam Search Attack and Grayscale Invariance (cs.CR, 2023) proposes a framework that combines a beam-search-based black-box attack with reversible data hiding using grayscale invariance. The method uses beam search to evaluate the adversarial gain of historical perturbations and to guide new adversarial perturbations, and reports an average PSNR of at least 40 dB versus source images under a limited query budget, achieving a targeted black-box reversible adversarial attack for the first time.
  • BeamAttack (cs.CL / cs.CR, 2023) is a textual adversarial-attack algorithm that uses mixed semantic spaces together with an improved beam search to craft high-quality adversarial examples. It is reported to improve attack success rate by up to 7% over greedy search on the MR dataset and to save up to 85% of model queries versus heuristic search while maintaining a competitive success rate; the resulting adversarial examples are also reported to be highly transferable and to improve model robustness under adversarial training.

Properties Highlighted by the Evidence

  • Trades extra candidate evaluation for a wider, more diverse search than greedy search.
  • Naturally composes with scoring functions that come from neural networks (encoder–decoders, classifiers), making it a standard decoder for program synthesis and a flexible attacker for black-box adversarial settings.
  • Empirically compared against DFS, CMA-ES, and genetic-algorithm–based search in the program-synthesis literature, and against greedy and heuristic search in the adversarial-attack literature.

LINKED ENTITIES

2 links
PCCoder USES
RobustFill USES

CITATIONS

6 sources
6 citations
[1] PCCoder is an encoder–decoder (DNN) program-synthesis scheme that uses beam search as its decoding strategy. GENESYS: Synthesizing Programs with Continuous Optimization (Table 4)
[2] RobustFill is an encoder–decoder (LSTM) program-synthesis scheme that uses beam search as its decoding strategy. GENESYS: Synthesizing Programs with Continuous Optimization (Table 4)
[3] Other program-synthesis schemes compared alongside beam-search–based decoders include DeepCoder (DNN function probability + DFS), NPO (autoencoder embedding + CMA-ES), PushGP and NetSyn (genetic algorithms), and Shgo (simplicial global optimization). GENESYS: Synthesizing Programs with Continuous Optimization (Table 4)
[4] GENESYS synthesizes at least 1.1% and up to 31.3% more programs than DeepCoder, PCCoder, RobustFill, PushGP, and NetSyn across program lengths 5, 7, and 10, and on average 28.1% more length-10 programs. GENESYS: Synthesizing Programs with Continuous Optimization
[5] Reversible adversarial examples combine a beam-search-based black-box attack with reversible data hiding using grayscale invariance; beam search evaluates the adversarial gain of historical perturbations to guide new perturbations, achieving an average PSNR of at least 40 dB under a limited query budget and enabling targeted black-box reversible adversarial attacks. Reversible Adversarial Examples with Beam Search Attack and Grayscale Invariance
[6] BeamAttack uses mixed semantic spaces with an improved beam search to craft high-quality textual adversarial examples, improving attack success rate by up to 7% over greedy search on MR and saving up to 85% of model queries versus heuristic search while remaining competitive. BeamAttack: Generating High-quality Textual Adversarial Examples through Beam Search and Mixed Semantic Spaces