Beam Search

Concept

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.

First seen 7/2/2026

Last seen 7/2/2026

Evidence 1 chunks

Wiki v1

WIKI

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

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

2 connections

PCCoder ← uses 100% 1e

PCCoder uses an encoder-decoder DNN with beam search.

RobustFill ← uses 100% 1e

RobustFill uses beam search for decoding programs.

LINKED ENTITIES

2 links

PCCoder USES Extracted graph relationship

RobustFill USES Extracted graph relationship

CITATIONS

6 sources

6 citations — click to expand

[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