From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models

• URL: http://arxiv.org/abs/2406.16838v2
• Date: Wed, 20 Nov 2024 17:57:26 GMT
• Title: From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models
• Authors: Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf, Alex Xie, Graham Neubig, Ilia Kulikov, Zaid Harchaoui,
• Abstract summary: This survey focuses on the benefits of scaling compute during inference. We explore three areas under a unified mathematical formalism: token-level generation algorithms, meta-generation algorithms, and efficient generation.
• Score: 63.188607839223046
• License:
• Abstract: One of the most striking findings in modern research on large language models (LLMs) is that scaling up compute during training leads to better results. However, less attention has been given to the benefits of scaling compute during inference. This survey focuses on these inference-time approaches. We explore three areas under a unified mathematical formalism: token-level generation algorithms, meta-generation algorithms, and efficient generation. Token-level generation algorithms, often called decoding algorithms, operate by sampling a single token at a time or constructing a token-level search space and then selecting an output. These methods typically assume access to a language model's logits, next-token distributions, or probability scores. Meta-generation algorithms work on partial or full sequences, incorporating domain knowledge, enabling backtracking, and integrating external information. Efficient generation methods aim to reduce token costs and improve the speed of generation. Our survey unifies perspectives from three research communities: traditional natural language processing, modern LLMs, and machine learning systems.

Related papers

• An Analysis under a Unified Fomulation of Learning Algorithms with Output Constraints [5.10832476049103]
  Neural networks (NN) perform well in diverse tasks, but sometimes produce nonsensical results to humans. Injecting human knowledge by reducing output constraints during training can improve model performance and reduce constraint violations. We propose new algorithms to integrate the information of main task and constraint injection.
  arXiv  Detail & Related papers  (2024-06-03T12:58:29Z)
• Executing Natural Language-Described Algorithms with Large Language Models: An Investigation [48.461999568129166]
  We examine the capacity of present-day large language models to comprehend and execute algorithms outlined in natural language. We selected 30 algorithms, generated 300 random-sampled instances, and evaluated whether popular LLMs can understand and execute these algorithms. Our findings reveal that LLMs, notably GPT-4, can effectively execute programs described in natural language, as long as no heavy numeric computation is involved.
  arXiv  Detail & Related papers  (2024-02-23T05:31:36Z)
• Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models [17.059322033670124]
  We propose a novel strategy that propels Large Language Models through algorithmic reasoning pathways. Our results suggest that instructing an LLM using an algorithm can lead to performance surpassing that of the algorithm itself.
  arXiv  Detail & Related papers  (2023-08-20T22:36:23Z)
• Fast Quantum Algorithm for Attention Computation [18.44025861624981]
  Large language models (LLMs) have demonstrated exceptional performance across a wide range of tasks. The attention scheme plays a crucial role in the architecture of large language models (LLMs) It is well-known that quantum machine computation has certain computational advantages compared to the classical machine.
  arXiv  Detail & Related papers  (2023-07-16T14:00:42Z)
• Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
  We focus on learning neural algorithmic reasoning only from the input-output pairs without appealing to the intermediate supervision. We build a self-supervised objective that can regularise intermediate computations of the model without access to the algorithm trajectory. We demonstrate that our approach is competitive to its trajectory-supervised counterpart on tasks from the CLRSic Algorithmic Reasoning Benchmark.
  arXiv  Detail & Related papers  (2023-06-23T09:57:44Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• Exploring Representation-Level Augmentation for Code Search [50.94201167562845]
  We explore augmentation methods that augment data (both code and query) at representation level which does not require additional data processing and training. We experimentally evaluate the proposed representation-level augmentation methods with state-of-the-art code search models on a large-scale public dataset.
  arXiv  Detail & Related papers  (2022-10-21T22:47:37Z)
• The CLRS Algorithmic Reasoning Benchmark [28.789225199559834]
  Learning representations of algorithms is an emerging area of machine learning, seeking to bridge concepts from neural networks with classical algorithms. We propose the CLRS Algorithmic Reasoning Benchmark, covering classical algorithms from the Introduction to Algorithms textbook. Our benchmark spans a variety of algorithmic reasoning procedures, including sorting, searching, dynamic programming, graph algorithms, string algorithms and geometric algorithms.
  arXiv  Detail & Related papers  (2022-05-31T09:56:44Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.