Implement Greedy and Beam Search Decoders

You are tasked with implementing two common decoding algorithms, Greedy Search and Beam Search, over a given directed token graph.

Problem Description

The input is a directed token graph represented as a Python dictionary. This dictionary maps each token to another dictionary, which in turn maps possible next tokens to their conditional probabilities.

• transitions: token -> { next_token: probability }
• A designated start_token (e.g., "I" or "<START>").
• A terminal_token (e.g., '.') that signifies the end of a sequence. A sequence also terminates if a token has no outgoing options (its key is missing from transitions or its value is an empty dictionary).

Probabilities are non-negative and represent conditional next-token probabilities. While you may assume they are normalized per node, your implementation should be robust enough to handle cases where they are not perfectly normalized.

Tasks

1. Greedy Search

Implement Greedy Search to generate a token sequence:

• At each step, select the next token with the highest probability.
• The search stops when the terminal_token is reached or when the current token has no outgoing options.
• Provide both an iterative and a recursive implementation.
• Return the generated token sequence, including the start_token.

2. Beam Search (BFS-style)

Implement Beam Search with a specified beam_size k:

• From each partial sequence currently in the beam, expand to all possible next tokens.
• From the expanded set of sequences, retain only the top k partial sequences. These sequences should be ranked by their cumulative log-probability.
• The search stops when all active beams have either reached the terminal_token or have no further continuations.
• Return the single highest-probability completed sequence. Optionally, you may also return all completed sequences.

Requirements

• Define clear function signatures for all implementations.
• Specify and implement a deterministic tie-breaking rule for cases with equal probabilities or scores.
• Analyze and state the time and space complexity for your implementations. Express complexity in terms of:
  • L: maximum sequence length
  • b: maximum branching factor (maximum number of outgoing options from any token)
  • |V|: vocabulary size (total number of unique tokens)
  • k: beam size