# Beam size is a parameter in some RNNs like TensorFlow's Magenta. What is beam size?

Magenta's melody_rnn_generate method includes a parameter beam_size. What is it and how does affect the melody?

Beam size, or beam width, is a parameter in the beam search algorithm which determines how many of the best partial solutions to evaluate. In an LSTM model of melody generation, for example, beam size limits the number of candidates to take as input for the decoder. A beam size of 1 is a best-first search - only the most probable candidate is chosen as input for the decoder. A beam size of $k$ will decode and evaluate the top $k$ candidates. A large beam size means a more extensive search - not only the single best candidate is evaluated.
Beam search is a heuristic search algorithm that uses breadth-first search to build its search tree and reduces the search space by eliminating candidates to reduce the memory and time requirements.1 Without the beam search, the worst time and space complexity for the best-search would be $\mathcal{O}(b^m)$ where $b$ is the branching factor and $m$ is the maximum depth. With beam search, the worst time complexity is $\mathcal{O}(kb)$ and the worst case space complexity is $\mathcal{O}(k)$2.
A larger beam generally means a more accurate prediction at the expense of memory and time. In one trial using attention_rnn, for example, modifying the beam width from 1 to 4 decreased the average negative log-likelihood of sequence (melody) generation from 84.2 to 38.6.