Massive-scale Decoding for Text Generation using Lattices

• URL: http://arxiv.org/abs/2112.07660v1
• Date: Tue, 14 Dec 2021 18:56:11 GMT
• Title: Massive-scale Decoding for Text Generation using Lattices
• Authors: Jiacheng Xu and Greg Durrett
• Abstract summary: We present a search algorithm to construct lattices encoding a massive number of generation options. We show that our algorithm encodes hundreds to thousands of diverse options that remain grammatical and high-quality into one linear-sized lattice.
• Score: 34.2658286826597
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural text generation models like those used for summarization and translation generate high-quality outputs, but often concentrate around a mode when what we really want is a diverse set of options. We present a search algorithm to construct lattices encoding a massive number of generation options. First, we restructure decoding as a best-first search, which explores the space differently than beam search and improves efficiency by avoiding pruning paths. Second, we revisit the idea of hypothesis recombination: we can identify pairs of similar generation candidates during search and merge them as an approximation. On both document summarization and machine translation, we show that our algorithm encodes hundreds to thousands of diverse options that remain grammatical and high-quality into one linear-sized lattice. This algorithm provides a foundation for building downstream generation applications on top of massive-scale diverse outputs.

Related papers

• Adaptive Contrastive Search: Uncertainty-Guided Decoding for Open-Ended Text Generation [0.20971479389679337]
  We introduce adaptive contrastive search, a novel decoding strategy extending contrastive search. Our findings indicate performance enhancement in both aspects, across different model architectures and datasets.
  arXiv  Detail & Related papers  (2024-07-26T12:23:54Z)
• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings. In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions. Second, a variant of beam search to find a solution is employed. This method utilizes a newly developed guiding function based on an expected distance score of partial solutions.
  arXiv  Detail & Related papers  (2024-07-17T21:26:27Z)
• Planning with Large Language Models for Code Generation [100.07232672883897]
  Planning-Guided Transformer Decoding (PG-TD) uses a planning algorithm to do lookahead search and guide the Transformer to generate better programs. We empirically evaluate our framework with several large language models as backbones on public coding challenge benchmarks.
  arXiv  Detail & Related papers  (2023-03-09T18:59:47Z)
• Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
  We propose a deterministic search algorithm balancing both quality and diversity. The proposed algorithm is parameter-free, lightweight, efficient, and easy to use.
  arXiv  Detail & Related papers  (2022-11-22T00:26:13Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem. We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
  arXiv  Detail & Related papers  (2021-12-06T20:34:55Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Expressivity of Parameterized and Data-driven Representations in Quality Diversity Search [111.06379262544911]
  We compare the output diversity of a quality diversity evolutionary search performed in two different search spaces. A learned model is better at interpolating between known data points than at extrapolating or expanding towards unseen examples.
  arXiv  Detail & Related papers  (2021-05-10T10:27:43Z)
• Unsupervised Text Generation by Learning from Search [86.51619839836331]
  TGLS is a novel framework to unsupervised Text Generation by Learning. We demonstrate the effectiveness of TGLS on two real-world natural language generation tasks, paraphrase generation and text formalization.
  arXiv  Detail & Related papers  (2020-07-09T04:34:48Z)

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.