Verbalized Algorithms

• URL: http://arxiv.org/abs/2509.08150v2
• Date: Mon, 03 Nov 2025 15:39:18 GMT
• Title: Verbalized Algorithms
• Abstract summary: Instead of querying LLMs in a one-shot manner, we propose a paradigm we call emphverbalized algorithms (VAs)<n>VAs decompose a task into simple elementary operations on natural language strings that they should be able to answer reliably.<n>We demonstrate the effectiveness of this approach on sorting and clustering tasks.
• Score: 0.9697877942346907
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Instead of querying LLMs in a one-shot manner and hoping to get the right answer for a reasoning task, we propose a paradigm we call \emph{verbalized algorithms} (VAs), which leverage classical algorithms with established theoretical understanding. VAs decompose a task into simple elementary operations on natural language strings that they should be able to answer reliably, and limit the scope of LLMs to only those simple tasks. For example, for sorting a series of natural language strings, \emph{verbalized sorting} uses an LLM as a binary comparison oracle in a known and well-analyzed sorting algorithm (e.g., bitonic sorting network). We demonstrate the effectiveness of this approach on sorting and clustering tasks.

Related papers

• Implementing Semantic Join Operators Efficiently [28.123361615101444]
  This paper proposes a novel algorithm for evaluating semantic joins.<n>The proposed algorithm integrates batches of rows from both input tables into a single prompt.<n>An adaptive variant of the proposed algorithm refers to cases in which the size of the output is difficult to estimate.
  arXiv  Detail & Related papers  (2025-10-09T17:30:01Z)
• RELIC: Evaluating Compositional Instruction Following via Language Recognition [37.49115450182637]
  Large language models (LLMs) are increasingly expected to perform tasks based only on a specification of the task provided in context.<n>We introduce the Recognition of Languages In-Context (RELIC) framework to evaluate instruction following using language recognition.
  arXiv  Detail & Related papers  (2025-06-05T16:17:24Z)
• Active Learning of Mealy Machines with Timers [3.087487671441056]
  We present the first algorithm for query learning Mealy machines with timers in a black-box context.<n>Our algorithm is an extension of the L# algorithm of Vaandrager et al. to a timed setting.
  arXiv  Detail & Related papers  (2024-03-04T13:20:52Z)
• 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)
• kNN-ICL: Compositional Task-Oriented Parsing Generalization with Nearest Neighbor In-Context Learning [50.40636157214161]
  Task-Oriented Parsing (TOP) enables conversational assistants to interpret user commands expressed in natural language. LLMs have achieved impressive performance in computer programs based on a natural language prompt. This paper focuses on harnessing the capabilities of LLMs for semantic parsing tasks.
  arXiv  Detail & Related papers  (2023-12-17T17:26:50Z)
• Leveraging Large Language Models for Exploiting ASR Uncertainty [16.740712975166407]
  Large language models must either rely on off-the-shelf automatic speech recognition systems for transcription, or be equipped with an in-built speech modality. We tackle speech-intent classification task, where a high word-error-rate can limit the LLM's ability to understand the spoken intent. We propose prompting the LLM with an n-best list of ASR hypotheses instead of only the error-prone 1-best hypothesis.
  arXiv  Detail & Related papers  (2023-09-09T17:02:33Z)
• 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)
• Large Language Models are Strong Zero-Shot Retriever [89.16756291653371]
  We propose a simple method that applies a large language model (LLM) to large-scale retrieval in zero-shot scenarios. Our method, the Language language model as Retriever (LameR), is built upon no other neural models but an LLM.
  arXiv  Detail & Related papers  (2023-04-27T14:45:55Z)
• PAL: Program-aided Language Models [112.94785609781503]
  We present Program-Aided Language models (PaL) to understand natural language problems. PaL offloads the solution step to a programmatic runtime such as a Python interpreter. We set new state-of-the-art results in all 12 benchmarks.
  arXiv  Detail & Related papers  (2022-11-18T18:56:13Z)
• Learning to Ask Conversational Questions by Optimizing Levenshtein Distance [83.53855889592734]
  We introduce a Reinforcement Iterative Sequence Editing (RISE) framework that optimize the minimum Levenshtein distance (MLD) through explicit editing actions. RISE is able to pay attention to tokens that are related to conversational characteristics. Experimental results on two benchmark datasets show that RISE significantly outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-30T08:44:19Z)
• 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)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

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.