Learn Before
Search Tree Structure in Token Generation
In NLP, the search space for generating output sequences is commonly structured as a search tree. Each node in this tree represents a prefix subsequence, and its child nodes are formed by appending one token from the vocabulary, along with the probability of predicting that token. The tree is organized into levels, where nodes at the same level correspond to sequences of identical length. As generation progresses, new tokens are incrementally appended, causing the tree to grow deeper and wider, representing an increasing number of potential sequence extensions.
0
1
Tags
Ch.5 Inference - Foundations of Large Language Models
Foundations of Large Language Models
Foundations of Large Language Models Course
Computing Sciences
Related
Hypothesis in LLM Inference
Mathematical Formulation of the Search Problem in LLM Inference
Exploration vs. Exploitation in LLM Search
Search Tree Structure in Token Generation
Heuristic Search Algorithms for LLM Inference
Efficient Generation of Candidate Solutions via Search Algorithms
Search for Optimal or Sub-optimal Sequences in LLM Inference
Root of the Search Space as a Representation of Input (x)
A text generation model has a vocabulary of 10,000 possible words it can choose from for each position in a sequence. If this model were to find the optimal output by evaluating every single possible sequence, how would the total number of sequences to check change if the desired output length is increased from 3 words to 5 words?
Evaluating an Inference Strategy
The Impracticality of Exhaustive Search
Historical Context and Computational Challenges of Maximum Probability Prediction
Mathematical Representation of an Output Sequence
Learn After
Breadth-First Search for Left-to-Right Token Generation
Root of the Search Tree as Input Representation
Expansion Step in Sequence Generation
In the process of generating an output, a language model considers two different candidate sequences:
Sequence A: 'The quick brown'andSequence B: 'A fast red'. Based on the conceptual model where token generation is a search through a tree, what is the most accurate statement regarding the positions of these two sequences within that tree?In the conceptual search tree for language model output generation, traversing from a parent node to one of its child nodes represents the action of appending a new token to the sequence represented by the parent node.
A language model is generating an output and has produced the following three candidate sequences:
S1: 'The cat sat',S2: 'The cat sat on', andS3: 'The dog ran'. According to the conceptual model of token generation as a search through a tree, which statement accurately describes the relationship between the nodes representing these sequences?Path in Decoding Search Tree as Output Sequence