Abstract
We initiate a formal investigation into the design and analysis of LLM-based algorithms, i.e. algorithms that contain one or multiple calls of large language models (LLMs) as sub-routines and critically rely on the capabilities of LLMs. While LLM-based algorithms, ranging from basic LLM calls with prompt engineering to complicated LLM-powered agent systems and compound AI systems, have achieved remarkable empirical success, the design and optimization of them have mostly relied on heuristics and trial-and-errors, which is largely due to a lack of formal and analytical study for these algorithms. To fill this gap, we start by identifying the computational-graph representation of LLM-based algorithms, the design principle of task decomposition, and some key abstractions, which then facilitate our formal analysis for the accuracy and efficiency of LLM-based algorithms, despite the black-box nature of LLMs. Through extensive analytical and empirical investigation in a series of case studies, we demonstrate that the proposed framework is broadly applicable to a wide range of scenarios and diverse patterns of LLM-based algorithms, such as parallel, hierarchical and recursive task decomposition. Our proposed framework holds promise for advancing LLM-based algorithms, by revealing the reasons behind curious empirical phenomena, guiding the choices of hyperparameters, predicting the empirical performance of algorithms, and inspiring new algorithm design.
Introduction
Building complex systems with Large Language Models (LLMs)—such as agentic workflows or advanced Retrieval-Augmented Generation (RAG) pipelines—is currently more of an art than a science. Developers often rely on "vibes-based" iteration, tweaking prompts or changing task decomposition until the system "seems to work." This paper addresses the lack of a rigorous way to predict how design choices, such as the granularity of task decomposition or the use of Chain-of-Thought (CoT), impact final system performance and cost. Specifically, we tackle the challenges of error accumulation across multiple LLM calls and the non-linear relationship between parallelization and end-to-end latency.
The Analytical Framework
The core contribution is an analytical framework that treats an LLM-based algorithm as a computational graph. This framework allows for a systematic optimization of the trade-offs between accuracy (error propagation) and efficiency (latency and cost).
The framework consists of three main components:
- Representation: Algorithms are modeled as computational graphs where nodes represent either LLM calls (comprising a prompter, model, and parser) or non-LLM symbolic programs. Edges represent data flow.
- Error Analysis: We model how errors at individual nodes propagate through the graph. A "sensitivity parameter" ($S$) is introduced to describe how much a node's output error is affected by its input errors.
- Cost Analysis: Costs are partitioned into "prefilling" (prompt processing) and "decoding" (text generation). This allows for modeling latency under varying degrees of parallelism ($p$), revealing that optimal task granularity depends heavily on available compute resources.
Task Decomposition Patterns
We apply this framework to three fundamental patterns commonly found in LLM-based systems: parallel, hierarchical/recursive, and iterative decomposition.
- Parallel Decomposition: Breaking a large task into independent chunks (e.g., counting or sorting).
- Iterative Retrieval/Reasoning: Multi-hop tasks where the model sequentially finds clues and reasons.
- Recursive Decomposition: Dynamically breaking a problem into sub-problems at runtime, which can be analyzed by "unrolling" the recursion into a Directed Acyclic Graph (DAG).
Experimental Methodology
To ensure rigorous measurement and avoid data contamination, we utilized synthetic tasks including character counting, list sorting, "needle-in-a-haystack" retrieval, and multi-hop grid reasoning. Evaluations were conducted using Llama-3 (8B and 70B), Qwen-2 (72B), and GPT-4-Turbo.
Key Insights and Results
Our analysis revealed several non-intuitive phenomena:
- The "Type-B" LLM Trap: While finer granularity is often assumed to improve accuracy, "Type-B" models (prone to false positives) can suffer in retrieval tasks if broken into too many small chunks, as noise from false positives overwhelms the aggregator.
- Non-Monotone Latency: With finite parallelism, there is a "sweet spot" for sub-task size. Chunks that are too small incur sequential overhead, while chunks that are too large lose parallelization benefits.
- CoT Trade-offs: Chain-of-Thought (CoT) provides a massive accuracy boost for negligible additive cost in iterative systems but can increase costs multiplicatively in recursive systems.
- Error Propagation: We proved that final error is a weighted average of node-specific errors, growing exponentially if sensitivity $S > 1$.
Conclusion
This framework moves LLM system design from heuristic trial-and-error toward a formal engineering discipline. While currently focused on deterministic synthetic tasks, future work will incorporate stochasticity and explore more complex multi-agent abstractions to bridge the gap toward subjective real-world applications.
Summary updated