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 verbalized algorithms (VAs), which combines LLMs with classical algorithms with established theoretical guarantees. VAs decompose a task into simple elementary operations on natural language strings that LLMs are able to answer reliably, and limit the scope of LLMs to those simple tasks. For example, for sorting a series of natural language strings, verbalized sorting uses an LLM as a binary comparison oracle in a known and well-analyzed sorting algorithm (e.g., bitonic sorting network). Although this is already known as pairwise ranking in the literature, we additionally demonstrate the effectiveness of verbalized maximum, verbalized clustering, and verbalized submodular maximization for numerical reasoning, topic clustering and multi-hop Q&A RAG task, which guarantees $O(n)$ runtime, $O(n \log n)$ runtime, and $1/(1-e)$ optimality, respectively. Clustering and submodular maximization outperformed or improved the nearest neighbor search using state-of-the-art embedding models.
Introduction
Large Language Models (LLMs) often struggle with complex reasoning tasks when prompted in a "one-shot" manner. For instance, asking an LLM to sort a list of 50 numbers or cluster 100 complex sentences frequently leads to hallucinations, missing items, or logically inconsistent results. This stems from a fundamental tension: while LLMs excel at atomic semantic operations (e.g., comparing two items), they are unreliable at managing the global execution logic of complex algorithms.
Current solutions typically attempt to force the LLM to handle the entire logic at once or translate the task into a formal language like PDDL. However, natural language's inherent ambiguity often makes rigid symbolic solvers impractical. We propose Verbalized Algorithms (VAs) as a middle ground, nesting LLMs as "oracles" within classical algorithms to provide both semantic power and formal guarantees.
Methodology
The VA framework follows a three-step process: decomposition of a task into a classical algorithm, identification of atomic decision steps, and verbalization of those steps into constrained LLM queries.
We demonstrate this approach across several domains:
- Verbalized Maximum: Finding the optimal element via pairwise comparisons.
- Verbalized Sorting: Utilizing algorithms like Powersort or Bitonic networks where the LLM serves as a binary comparison oracle.
- Verbalized Clustering: Building a graph via triplet comparisons and applying greedy modularity maximization.
- Verbalized Submodular Maximization (VGSM): Enhancing Retrieval-Augmented Generation (RAG) by iteratively selecting informative documents with a $1 - 1/e$ optimality guarantee.
To improve reliability, we employ Robust VAs (majority voting) and Symmetrized VAs (order-swapping to mitigate positional bias). Efficiency is maintained through KV-caching techniques like RadixAttention.
Experimental Evaluation
VAs were evaluated on diverse benchmarks including numerical reasoning (sorting integers), sentiment analysis (Amazon Reviews), topic clustering (Medarxiv and xkcdcolors), and multi-hop Q&A (HotpotQA and CUAD).
Key Results
A significant finding is that small models (e.g., 1.7B parameters) using VAs can outperform much larger models (e.g., 32B) performing one-shot tasks. The algorithm provides the structural "brain" that smaller models lack. As shown in the results for numerical reasoning, the Mean Absolute Error (MAE) drops to zero for verbalized approaches even on small models, whereas baseline performance degrades significantly as the task size increases.
In sorting tasks, VAs eliminated "invariance violations" (missing or duplicate items) common in standard prompting. In clustering, the "xkcdcolors" dataset—a difficult out-of-distribution task—saw Verbalized Clustering achieve an Adjusted Rand Index (ARI) significantly higher than state-of-the-art embedding models. Furthermore, the VGSM approach for RAG consistently improved document retrieval likelihood compared to BM25 or embedding-based methods.
Discussion and Future Work
The primary challenge for VAs is the increased latency and cost associated with multiple API calls. While parallelization and KV-caching mitigate this, the overhead remains a factor for large datasets. Future research will explore expanding the VA library to include cycle detection for logic pruning, garbage collection for document summarization, and more complex combinatorial optimization for retrieval tasks.
Summary updated