 |
Reasoning language models are artificial intelligence systems that combine natural language processing with structured reasoning capabilities. These models are usually constructed by prompting, supervised finetuning (SFT), and reinforcement learning (RL) initialized with pretrained language models.
A language model is a generative model of a training dataset of texts. Prompting means constructing a text prompt, such that, conditional on the text prompt, the language model generates a solution to the task. Prompting can be applied to a pretrained model ("base model"), a base model that has undergone SFT, or RL, or both. [1]
Chain of Thought prompting (CoT) prompts the model to answer a question by first generating a "chain of thought", i.e. steps of reasoning that mimic a train of thought. [2] It was published in 2022 by the Brain team of Google on the PaLM-540B model. [3] In CoT prompting, the prompt is of the form "<Input> Let's think step by step", and the model would respond with a chain of reasoning steps, ended with an answer:Similarly, Tree of Thought prompting generalizes CoT by prompting the model to generate one or more "possible next steps", and then running the model on each of the possible next steps by breadth-first, beam, or some other method of tree search. [4] Similarly, Graph of Thought generalizes CoT so that the reasoning steps form a directed acyclic graph. [5]
Self-consistency decoding performs several chain-of-thought rollouts, then selects the most commonly reached conclusion out of all the rollouts. [6] If the rollouts disagree by a lot, a human can be queried for the correct chain of thought. [7]
A language model may answer a query by first querying a database of documents using the query. The document retrieval can be via a vector database, summary index, tree index, or keyword table index. [8] Following document retrieval, the LLM generates an output that incorporates information from both the query and the retrieved documents. [9]
Language models can perform long reasoning steps by calling external methods, such as numerical recipes, program interpreters, API calls, and so on. This can be prompt-engineered by describing the external methods in-context (an example of in-context learning) or finetuned into the model. [10]
A base model can be finetuned on a dataset of reasoning tasks with example solutions and reasoning traces. The finetuned model would then be able to generate reasoning traces for a given problem. [11] [12]
As it is expensive to get humans to write reasoning traces for a SFT dataset, researchers have proposed ways to automatically construct SFT datasets. In rejection sampling finetuning (RFT), new reasoning traces are collected via a loop: [13]
A pretrained language model can be further trained by RL. In the RL formalism, a generative language model is a policy. A prompt specifying a task to solve is an environmental state, and the response of the language model to the prompt is an action. The probability that the language model responds with is .
Training a reasoning language model by RL then consists of constructing a reward model to guide the RL process. Intuitively, a reward model describes how desirable/appropriate/good the response is for the prompt. For reasoning language model, the prompt describes a reasoning task, and the reward would be high if the response solves the task, and low if the response fails to solve the task.
For reasoning language models, the model's response may be broken down into multiple steps, in which case it is written as .
Outcome reward model, or outcome-supervised RM (ORM), [11] is a reward model that computes the reward of a step determined by the final answer: . They are also called "verifiers".
For tasks with an answer that is easy to verify, such as word problems in math, the outcome reward can simply be binary: 1 if the final answer is correct, and 0 otherwise. [11] If the answer is not easy to verify programmatically, humans can manually label the answers as correct or not, then the labels can be used to finetune a base model that predicts the human label. [12] For other kinds of tasks, such as creative writing, where task performance is not binary true/false, one can train a reward model by finetuning a base model on human ranked preference data, such as used in reinforcement learning from human feedback. [14] A base model can also be finetuned to predict, given a partial thinking trace , whether the final answer would be correct or not. This can then be used as a binary reward signal. [11]
The ORM is usually trained via logistic regression, i.e. minimizing cross-entropy loss. [15]
Given a PRM, an ORM can be constructed by multiplying the total process reward during the reasoning trace, [14] or by taking the minimum, [15] or some other method to aggregate the process rewards.
Process reward model, or process-supervised RM (PRM), [11] is a reward model that computes the reward of a step determined by the steps so far: .
Given a partial thinking trace , a human can be queried as to whether the steps so far are correct, regardless of whether the ultimate answer would be correct. This can then be used as a binary reward signal. As human labels are expensive, a base model can be finetuned to predict the human labels. [11] The PRM is usually trained via logistic regression, i.e. minimizing cross-entropy loss. [15]
As an example, in a 2023 OpenAI paper, 800K process labels were collected for 75K solution traces. A labeler would be presented with a solution trace, and keep labelling "positive" if the step progresses towards the solution, "neutral" if it is not wrong, but does not progress towards solution, and "negative" if it is a mistake. As soon as a "negative" label is entered, the labeler stops labeling that thinking trace, and begins labeling another one. The idea was that, while labelling subsequent reasoning steps can provide even richer supervision signals, simply labeling up to the first error was sufficient for training a competent PRM. [14] [16]
As human labels are expensive, researchers have proposed methods to create PRM without human labels on the processes. Inspired by Monte Carlo tree search (MCTS), the Math-Shepherd method samples multiple continuations until the end, starting at each reasoning step , and set the reward at that step to be either in the case of "soft estimation", or in the case of "hard estimation". This creates process reward using only an ORM, which is usually easier or cheaper to construct. After creating these process reward labels, a PRM can be trained on them. [15] Some have tried a fully MCTS approach. [17]
One can also use an ORM to implicitly construct a PRM, similar to direct preference optimization. [18]
A trained ORM can be used to select the best response. The policy would rollout multiple responses, and a trained ORM would select the best response. This allows a simple form of test time compute scaling ("best-of-N"). [12] [21]
A trained PRM can also be used to guide reasoning by greedy tree search. That is, the policy model generates several possible next reasoning steps, and the PRM selects the best one, and the process repeats. This is similar to how a trained ORM can be used to select the best response. [22] Beam search perform better than greedy search.
Lookahead search is another tree search method, where the policy model generates several possible next reasoning steps, then make a (partial) rollout for each. If a solution endpoint is reached during the forward simulation, the process halts early. Otherwise, the PRM is used to calculate the total reward for each rollout. The step with the highest rollout is selected. [23]
Self-consistency can be combined with an ORM. The model would be used to generate multiple answers, and the answers would be clustered, so that each cluster has the same answer. The ORM is used to compute the reward for each answer, and the rewards within each cluster is summed. The answer corresponding to the cluster with the highest summed reward is output. [15]
Prompt engineering was discovered in GPT-3 as "few-shot learning", [24] which began a period of research into "eliciting" capacities of pretrained language models. It was then found that a model could be prompted to perform CoT reasoning, which improves its performance on reasoning tasks.
The reasoning ability of language models are usually tested on problems of which there are unambiguous solutions that can be cheaply checked, and requires reasoning when solved by a human. These are usually in mathematics and competitive programming. The answer is usually an array of integers, a multiple choice letter, or a program that passes unit tests within a limited runtime.
The benchmark scores are of the following kinds:
The pass@n score can be estimated more accurately by making attempts, and use the unbiased estimator , where is the number of correct attempts. [29]
A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent Markov process. An HMM requires that there be an observable process whose outcomes depend on the outcomes of in a known way. Since cannot be observed directly, the goal is to learn about state of by observing . By definition of being a Markov model, an HMM has an additional requirement that the outcome of at time must be "influenced" exclusively by the outcome of at and that the outcomes of and at must be conditionally independent of at given at time . Estimation of the parameters in an HMM can be performed using maximum likelihood estimation. For linear chain HMMs, the Baum–Welch algorithm can be used to estimate parameters.
Hypercomputation or super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that could correctly evaluate every statement in Peano arithmetic.
A Bayesian network is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). While it is one of several forms of causal notation, causal networks are special cases of Bayesian networks. Bayesian networks are ideal for taking an event that occurred and predicting the likelihood that any one of several possible known causes was the contributing factor. For example, a Bayesian network could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can be used to compute the probabilities of the presence of various diseases.
In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another.
In mathematics and computer science, Zeno machines are a hypothetical computational model related to Turing machines that are capable of carrying out computations involving a countably infinite number of algorithmic steps. These machines are ruled out in most models of computation.
Recurrent neural networks (RNNs) are a class of artificial neural network commonly used for sequential data processing. Unlike feedforward neural networks, which process data in a single pass, RNNs process data across multiple time steps, making them well-adapted for modelling and processing text, speech, and time series.
Answer set programming (ASP) is a form of declarative programming oriented towards difficult search problems. It is based on the stable model semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates.
In probability theory and machine learning, the multi-armed bandit problem is a problem in which a decision maker iteratively selects one of multiple fixed choices when the properties of each choice are only partially known at the time of allocation, and may become better understood as time passes. A fundamental aspect of bandit problems is that choosing an arm does not affect the properties of the arm or other arms.
A constrained conditional model (CCM) is a machine learning and inference framework that augments the learning of conditional models with declarative constraints. The constraint can be used as a way to incorporate expressive prior knowledge into the model and bias the assignments made by the learned model to satisfy these constraints. The framework can be used to support decisions in an expressive output space while maintaining modularity and tractability of training and inference.
Neural machine translation (NMT) is an approach to machine translation that uses an artificial neural network to predict the likelihood of a sequence of words, typically modeling entire sentences in a single integrated model.
A transformer is a deep learning architecture that was developed by researchers at Google and is based on the multi-head attention mechanism, which was proposed in the 2017 paper "Attention Is All You Need". Text is converted to numerical representations called tokens, and each token is converted into a vector via lookup from a word embedding table. At each layer, each token is then contextualized within the scope of the context window with other (unmasked) tokens via a parallel multi-head attention mechanism, allowing the signal for key tokens to be amplified and less important tokens to be diminished.
Bidirectional encoder representations from transformers (BERT) is a language model introduced in October 2018 by researchers at Google. It learns to represent text as a sequence of vectors using self-supervised learning. It uses the encoder-only transformer architecture. It is notable for its dramatic improvement over previous state-of-the-art models, and as an early example of a large language model. As of 2020, BERT is a ubiquitous baseline in natural language processing (NLP) experiments.
Prompt engineering is the process of structuring or crafting an instruction in order to produce the best possible output from a generative artificial intelligence (AI) model.
Probabilistic numerics is an active field of study at the intersection of applied mathematics, statistics, and machine learning centering on the concept of uncertainty in computation. In probabilistic numerics, tasks in numerical analysis such as finding numerical solutions for integration, linear algebra, optimization and simulation and differential equations are seen as problems of statistical, probabilistic, or Bayesian inference.
This glossary of quantum computing is a list of definitions of terms and concepts used in quantum computing, its sub-disciplines, and related fields.
DisCoCat is a mathematical framework for natural language processing which uses category theory to unify distributional semantics with the principle of compositionality. The grammatical derivations in a categorial grammar are interpreted as linear maps acting on the tensor product of word vectors to produce the meaning of a sentence or a piece of text. String diagrams are used to visualise information flow and reason about natural language semantics.
In machine learning, reinforcement learning from human feedback (RLHF) is a technique to align an intelligent agent with human preferences. It involves training a reward model to represent preferences, which can then be used to train other models through reinforcement learning.
A large language model (LLM) is a type of machine learning model designed for natural language processing tasks such as language generation. LLMs are language models with many parameters, and are trained with self-supervised learning on a vast amount of text.
In machine learning, a neural scaling law is an empirical scaling law that describes how neural network performance changes as key factors are scaled up or down. These factors typically include the number of parameters, training dataset size, and training cost.
DeepSeek is a Chinese artificial intelligence company that develops open-source large language models (LLMs). Based in Hangzhou, Zhejiang, it is owned and funded by Chinese hedge fund High-Flyer, whose co-founder, Liang Wenfeng, established the company in 2023 and serves as its CEO.
