beam search
In plain wordsA search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility.
- 1
Decoding
A heuristic decodingdecoding, n.: The method a language model uses to turn its predictions into actual text — for example, always picking the most likely next word, or choosing somewhat at random among the likely ones. algorithm that keeps the B highest-scoring partial sequences (beams; B is the beam width) at each step: every beam is extended by every possible next tokentoken, n.: The small chunk of text an AI language model reads and writes — often a word, part of a word or a punctuation mark. AI usage, limits and prices are counted in tokens., candidates are scored by cumulative log probabilitylog probability, n.: The logarithm of the probability a model gives to a token or a text. Computers use it because multiplying many tiny probabilities runs into rounding problems, whereas adding their logarithms does not., and only the top B survive, while hypotheses that emit an end token are set aside as finished. It finds higher-likelihood outputs than greedy decodinggreedy decoding, n.: The simplest way for a language model to write: always pick the single most likely next word. It is fast and predictable but can produce dull or repetitive text. at roughly B times the cost and was the standard for machine translation, speech recognition and summarization, usually with a length penalty because raw log probability favors short outputs. In open-ended generation it tends to produce bland, repetitive text, and very wide beams can even lower quality, so chat models generally sample instead. Variants include diverse beam search and grid beam search for constrained decodingconstrained decoding, n.: Forcing an AI model's output to follow a required format — such as valid code or a fill-in form — by blocking, at every step, any word that would break the rules..
We decode translations with a beam width of 5 and a length penalty of 0.6.
- 2
Search algorithms
A heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. method for state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal. that bounds memory by pruning: like breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first. it advances one depth at a time, but after generating each new layer of successors it ranks them with a heuristic evaluation and discards all but a fixed number. Because a discarded branch is never revisited, the search can miss the goal or return a worse path than the best one. Local beam search applies the same pruning to hill climbing, keeping the k best states drawn from the successors of all current states.
Origin
Introduced in Bruce Lowerre's Harpy speech-recognition system at Carnegie Mellon University (1976 PhD thesis), developed within Raj Reddy's DARPA-funded speech-understanding research; first described as a 'locus model of search', it was being called beam search by 1977. It became the default decoder in statistical and then neural machine translation.
Usage note
Philipp Koehn and Rebecca Knowles (2017) reported that very wide beams lowered neural translation quality, a problem later dubbed the 'beam search curse'.
Related
- decodingdecoding, n.: The method a language model uses to turn its predictions into actual text — for example, always picking the most likely next word, or choosing somewhat at random among the likely ones.
- greedy decodinggreedy decoding, n.: The simplest way for a language model to write: always pick the single most likely next word. It is fast and predictable but can produce dull or repetitive text.
- breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first.
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- constrained decodingconstrained decoding, n.: Forcing an AI model's output to follow a required format — such as valid code or a fill-in form — by blocking, at every step, any word that would break the rules.
- log probabilitylog probability, n.: The logarithm of the probability a model gives to a token or a text. Computers use it because multiplying many tiny probabilities runs into rounding problems, whereas adding their logarithms does not.
- Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average.
- greedy decodinggreedy decoding, n.: The simplest way for a language model to write: always pick the single most likely next word. It is fast and predictable but can produce dull or repetitive text.
- top-p samplingtop-p sampling, n.: A way of making AI-written text varied but sensible: the model picks at random among the smallest group of likely next words whose chances add up to a set share, such as 90%.
Sources
- Lowerre, B. T. (1976). The Harpy Speech Recognition System. PhD thesis, Carnegie Mellon University.
- Koehn, P. & Knowles, R. (2017). Six Challenges for Neural Machine Translation. Proceedings of the First Workshop on Neural Machine Translation.
Mentioned in
best-of-n samplingbest-of-n sampling, n.: Asking an AI the same question several times and keeping whichever answer a scoring model or checker rates highest — a simple way to trade extra computing for better answers., constrained decodingconstrained decoding, n.: Forcing an AI model's output to follow a required format — such as valid code or a fill-in form — by blocking, at every step, any word that would break the rules., decode phasedecode phase, n.: The second stage of an AI's reply, in which it writes the answer one word-piece at a time, each step depending on everything written so far., decodingdecoding, n.: The method a language model uses to turn its predictions into actual text — for example, always picking the most likely next word, or choosing somewhat at random among the likely ones., greedy decodinggreedy decoding, n.: The simplest way for a language model to write: always pick the single most likely next word. It is fast and predictable but can produce dull or repetitive text., samplingsampling, n.: Picking some items at random from a larger set or from a range of possibilities — surveying 1,000 voters, say, or letting an AI choose its next word by a weighted lottery., sequence-to-sequence modelsequence-to-sequence model, n.: A model that turns one sequence into another, such as a French sentence into English or speech into text, by first reading the whole input and then writing the output step by step., state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal., Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination., best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next., connectionist temporal classificationconnectionist temporal classification, n.: A training method that lets a network learn to transcribe speech or handwriting without being told exactly where each letter or sound begins and ends., maximum a posteriori estimationmaximum a posteriori estimation, n.: Picking the single most believable setting of a model after combining the evidence with what was assumed beforehand. In practice it often amounts to ordinary training plus a penalty that keeps settings modest., PagedAttentionPagedAttention, prop. n.: A way of storing an AI model's working memory in small fixed-size blocks, like the pages of a computer's memory, so little space is wasted and more users can be served at once., Raj ReddyRaj Reddy, prop. n.: An Indian-American computer scientist who pioneered computer speech recognition and large AI systems at Carnegie Mellon University, and shared the 1994 Turing Award.