Beam Search over Partial Plans

hardPROAgent Loop Control & PlanningAI AgentsAI Agents 1

Problem Statement

Expand a tree of candidate plan steps with beam search: at each depth keep only the top-beam_width partial plans by cumulative score, then return the best complete plan's total score.

Background

Start from the root (empty plan, score 0). At each level, every kept partial plan branches into children given by successors(node), each child adding its step score. After generating all children of a level, keep the beam_width highest-scoring ones (ties broken by the smaller node id for determinism). A node with no successors is terminal. After exploring depth levels (or when no expansions remain), return the maximum total score among all partial plans ever kept (including terminals). Nodes are integer ids; successors maps an id to a list of (child_id, step_score).

Your Task

def beam_search(successors, root, beam_width, depth):

Return the best cumulative score (float) found, rounded to 4 decimals.

Input Format

successors (dict: id -> list of (child_id, score)), root (int), beam_width (int), depth (int).

Output Format

A float rounded to 4 decimals.

Sample

succ = {0: [(1, 2.0), (2, 5.0)], 1: [(3, 10.0)], 2: [(4, 1.0)]}
print(beam_search(succ, 0, 1, 2))

Output:

6.0

Example

Input

succ = {0: [(1, 2.0), (2, 5.0)], 1: [(3, 10.0)], 2: [(4, 1.0)]}
print(beam_search(succ, 0, 1, 2))

Output

6.0

Reasoning

Initialization: Start with the root node $0$ having a cumulative score of $0.0$ . The beam width is $1$ , meaning only the single best partial plan is kept at each step, and we explore up to a depth of $2$ .
Depth 1 Expansion: Expand the current beam $\{0\}$ using its successors. Node $0$ branches to node $1$ (score $0.0 + 2.0 = 2.0$ ) and node $2$ (score $0.0 + 5.0 = 5.0$ ). Since the beam width is $1$ , we keep only the highest-scoring child, which is node $2$ with a score of $5.0$ . The current best score is updated to $5.0$ .
Depth 2 Expansion: Expand the current beam $\{2\}$ using its successors. Node $2$ branches to node $4$ with a step score of $1.0$ . The new cumulative score is $5.0 + 1.0 = 6.0$ . This is the only child, so it becomes the new beam. The best score is updated to $6.0$ .
Termination: The maximum allowed depth of $2$ has been reached. The algorithm stops and returns the highest cumulative score observed in any kept beam, which is $6.0$ .
The final output is 6.0

Constraints

Beam keeps top beam_width by cumulative score each level; ties -> smaller node id.
A node absent from successors (or with empty list) is terminal.
Track the best cumulative score across all kept nodes; round to 4 decimals.

Learn this in

Self-Improvement: Reflexion, Self-Refine, Tree-of-Thought, LATSAgent Engineering Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primerPREVIEW

1. Background Knowledge

Beam search is a heuristic search algorithm that performs a breadth-first search but prunes the search space by keeping only the top- $k$ most promising nodes at each depth level. Unlike exhaustive breadth-first search, which retains all nodes at a given depth, beam search limits memory and computation by discarding lower-scoring candidates. The parameter $k$ (here, beam_width) controls the trade-off between search quality and efficiency: a larger beam width explores more of the tree but costs more time and space.

In this problem, the search tree is defined implicitly by a successors dictionary that maps each node ID to a list of (child_id, step_score) pairs. Each edge contributes a step score to the cumulative path score. The root starts with a cumulative score of $0$ . A node with no successors (or no entry in the dictionary) is terminal. The goal is not to find a specific target but to maximize the cumulative score over all partial plans kept during the search, up to a specified depth.

A critical detail is the tie-breaking rule: when two partial plans have the same cumulative score, the one with the smaller node ID is preferred. This ensures deterministic behavior, which is essential for reproducible results in agent planning loops.

2. Algorithm Approach

The algorithm follows a level-by-level expansion pattern:

Initialize the current beam with the root node, assigned a cumulative score of $0$ .
For each depth level from $1$ to depth:

Generate all children of every node in the current beam by looking up their successors.
Compute each child's cumulative score as the parent's score plus the edge's step score.
Track the best score seen so far across all generated children (and terminals).
Sort all generated children by cumulative score (descending), breaking ties by node ID (ascending).
Keep only the top beam_width children as the new beam for the next iteration.

If the beam becomes empty (no expansions remain), stop early.
Return the maximum cumulative score observed, rounded to 4 decimal places.

This is a greedy pruning strategy: at each level, we commit to the best-scoring partial plans and discard the rest, assuming that higher-scoring prefixes are more likely to lead to optimal complete plans.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.