Verbalized Algorithms (arxiv.org)

The paper introduces "verbalized algorithms" (VAs), a paradigm that combines classical algorithms with large language models by limiting LLMs to simple, reliable operations on natural-language strings. Instead of asking an LLM to solve a complex reasoning task in one shot, VAs decompose the task into elementary subroutines—for example, using an LLM only as a binary comparison oracle—and plug those oracles into well-studied algorithmic structures like a bitonic sorting network. The authors demonstrate this idea on sorting and clustering problems, showing that composition with provable algorithms yields more robust behavior than monolithic prompting. This approach is significant because it aligns LLM strengths (flexible language comparisons and local judgments) with formal algorithmic guarantees (correctness, complexity, parallelism). Technically, VAs reduce brittleness and hallucination by constraining LLM responsibilities, make error modes easier to analyze (oracle error rates propagate through known algorithmic bounds), and enable predictable performance trade-offs (e.g., choosing a sorting network for parallelism vs. comparison-optimal algorithms for fewer queries). Practical implications include simpler prompt design, modular debugging, and the possibility of hybrid systems that apply calibration or redundancy on the oracle level. Limitations remain—LLM oracle reliability and error-correction strategies determine end-to-end accuracy—but VAs offer a promising bridge between symbolic algorithmics and probabilistic LLM behavior.