Verbalized Algorithms: Classical Algorithms are All You Need (Mostly)

2025/09/09 by Lall, Supriya, Hari Pathanjaly, Farrell, Christian +7
Computer Science · #Natural Language Processing Techniques #Topic Modeling #Machine Learning and Data Classification

paper · pdf · doi:10.48550/arxiv.2509.08150

Abstract

Reasoning is a fundamentally algorithmic task. Yet current work on LLM-based reasoning relies on free-form generation whose theoretical guarantees (soundness, completeness, complexity, optimality) remain poorly understood. We argue that we should not treat them as general-purpose reasoners, and as an alternative, we propose a paradigm we call verbalized algorithms (VAs), which combines LLMs and various algorithms with established guarantees. Instead of betting on LLM's ability to solve a reasoning task, VAs limit their scope by decomposing the task down to simple elementary operations on strings that they can answer reliably. For example, sorting a list of natural language strings could be done by using an LLM as a binary comparison oracle in a parallel or approximate sorting algorithm. We push the accuracy-runtime Pareto front with verbalized maximum, sorting, clustering, and submodular maximization, for numerical reasoning, topic clustering, Wi-Fi access point optimization, and multi-hop Q&A RAG task. These results suggest improving LLM-based reasoning through standard algorithmic analysis is a feasible and better grounded research direction.

Citations

• Chain of Retrieval: Multi-Aspect Iterative Search Expansion and Post-Order Search Aggregation for Full Paper Retrieval
• The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity
• "Don't Do That!": Guiding Embodied Systems through Large Language Model-based Constraint Generation
• XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models
• Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming
• Can Large Language Models Reason? A Characterization via 3-SAT
• Thought of Search: Planning with Language Models Through The Lens of Efficiency
• Make Large Language Model a Better Ranker
• SGLang: Efficient Execution of Structured Language Model Programs
• Efficient Memory Management for Large Language Model Serving with PagedAttention
• Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback
• Efficient Guided Generation for Large Language Models
• Lost in the Middle: How Language Models Use Long Contexts
• Large Language Models Enable Few-Shot Clustering
• Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting
• Direct Preference Optimization: Your Language Model is Secretly a Reward Model
• ClusterLLM: Large Language Models as a Guide for Text Clustering
• Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning
• MD3: The Multi-Dialect Dataset of Dialogues
• Zero-Shot Listwise Document Reranking with a Large Language Model
• Is ChatGPT Good at Search? Investigating Large Language Models as Re-Ranking Agents
• Translating Natural Language to Planning Goals with Large-Language Models
• Toolformer: Language Models Can Teach Themselves to Use Tools
• MTEB: Massive Text Embedding Benchmark
• Improving Passage Retrieval with Zero-Shot Question Generation
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• CUAD: An Expert-Annotated NLP Dataset for Legal Contract Review
• Algorithms with Predictions
• GoEmotions: A Dataset of Fine-Grained Emotions
• HouseExpo: A Large-scale 2D Indoor Layout Dataset for Learning-based Algorithms on Mobile Robots
• HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering
• Comparison Based Nearest Neighbor Search
• Parallel Correlation Clustering on Big Graphs
• Cumulated gain-based evaluation of IR techniques
• RANK ANALYSIS OF INCOMPLETE BLOCK DESIGNS
• A NEW MEASURE OF RANK CORRELATION
• Bridging Language and Items for Retrieval and Recommendation

Related

• SortBench: Benchmarking LLMs based on their ability to sort lists
• Full Automation of Goal-driven LLM Dialog Threads with And-Or Recursors and Refiner Oracles
• Access Paths for Efficient Ordering with Large Language Models
• Connecting the Dots: Evaluating Abstract Reasoning Capabilities of LLMs Using the New York Times Connections Word Game
• ThoughtProbe: Classifier-Guided LLM Thought Space Exploration via Probing Representations