TL;DR
While multi-call LLM workflows, compound AI systems, and agents are increasingly popular, they are almost universally designed through trial-and-error heuristics. This paper introduces a formal analytical framework that models LLM-based algorithms as computational graphs, applying classical algorithmic principles—such as task decomposition, error propagation bounds, and parallel complexity—to predict and optimize their accuracy, token consumption, and runtime latency.
What Problem Does This Paper Address?
Modern applications increasingly wrap Large Language Models (LLMs) into compound systems—such as pipelines with parallel calls, multi-hop retrieval-augmented generation (RAG), and recursive reasoning agents. However, engineering these workflows is notoriously ad-hoc: developers tune chunk sizes, prompts, and tool topologies via trial and error.
Because LLMs are black boxes, computer science has lacked a formal foundation to analyze questions like:
- How fine-grained should task decomposition be?
- How does error compound across interconnected LLM steps?
- Under what conditions does parallelizing sub-calls actually reduce wall-clock latency rather than just inflating token costs?
This paper establishes formal abstractions to analyze the accuracy and efficiency of LLM-based algorithms mathematically before running them.
Methods
The authors formalize an LLM-based algorithm as a directed computational graph consisting of:
- LLM Nodes: Composed of a prompter (converts structured data to natural language), an LLM sub-routine, and a parser (converts natural language outputs back into structured data).
- Non-LLM Nodes: Standard deterministic or symbolic algorithms (e.g., merging sorted lists, API calls, symbolic verification).
Using this formulation, the authors analyze algorithms across three core decomposition paradigms:
- Parallel Decomposition: Splitting a problem of size $n$ into $k$ sub-tasks of size $m$, processing them (sequentially or across $p$ parallel workers), and aggregating outputs.
- Hierarchical Decomposition: Multi-round workflows where each outer iteration spawns lower-level retrieval and reasoning sub-tasks (e.g., multi-hop question answering).
- Recursive Decomposition: Dynamically generated depth-first execution trees where an LLM recursively spawns child sub-problems until reaching base cases, maintaining a memoized dictionary of solved states.
Key Theoretical Tools
- Cost Modeling: Total cost and wall-clock latency are modeled as functions of prefill length $L_{\text{pre}}$, decode length $L_{\text{dec}}$, and parallelism capacity $p$, accounting for batching depth $d = \lceil k/p \rceil$.
- Error Propagation in DAGs (Proposition 1 & 3): Under additive error and bounded Lipschitz sensitivity $S$, the error at any node $v$ is bounded across all paths from predecessor nodes $w$: $$\mathcal{E}(y(v)) \le \sum_{w \in \text{DAG}} \sum_{\text{path} \in \mathcal{P}(w \to v)} S^{|\text{path}|} \mathcal{E}_w$$
Datasets
To isolate algorithmic properties from real-world data noise and contamination, the authors evaluate their framework on controlled, synthetic benchmark tasks:
- Character Counting: Counting target digits in randomized alphanumeric strings of length $n$.
- List Sorting: Sorting arrays of floats uniformly sampled in $[0, 1]$ rounded to two decimal places.
- Adversarial Needle-in-a-Haystack Retrieval: Locating a target passcode among distractor sentences with overlapping color/object patterns.
- Multi-Needle RAG: Extracting scattered passcode digits across text chunks.
- Multi-Hop Dependency Grids: Directed acyclic graphs of variable equations (e.g., $A_2 = B_1 + B_3$) parameterized by grid depth $d$, width $w$, and arithmetic degree $g$.
Evaluated backends include Llama-3-8B, Llama-3-70B, GPT-4-Turbo, and Qwen2-72B-Instruct (using deterministic greedy decoding).
Key Insights and Ideas
- Explaining Non-Monotonic Latency "Zigzags": In parallelized sorting, increasing sub-task size $m$ produces a non-monotonic, "zigzag" latency curve. The framework demonstrates this is caused by the ceiling function of the scheduling depth $d = \lceil k/p \rceil = \lceil \lceil n/m \rceil / p \rceil$; latency spikes whenever an extra batch iteration is triggered.
- The Two Failure Modes of Retrieval: The authors categorize LLMs into:
- Type-1 LLMs (mostly false negatives: miss the needle when present).
- Type-2 LLMs (both false negatives and false positives: hallucinate answers from empty chunks).
For Type-2 models, chopping a prompt into smaller chunks ($m$) backfires: while smaller chunks make the needle easier to read, they increase the total number of chunks $k \approx n/m$, massively multiplying false positives during majority voting.
- The "Reasoning Overhead" Fallacy in Hierarchical Systems: In iterative multi-hop pipelines, LLM calls for reasoning/answering represent only a tiny fraction of the total token and latency footprint compared to the retrieval nodes. Consequently, forcing reasoning nodes to use expensive "think step-by-step" (Chain-of-Thought) yields substantial accuracy gains with almost no relative system overhead.
Key Results
- Sorting Lists via Hybrid LLM + Symbolic Merge: By sorting chunks of size $m$ with an LLM and merging them symbolically, the overall system preserves the maximum component $\ell_\infty$ error ($\mathcal{E} \le \max_i \mathcal{E}_i$, Proposition 2). On $n=200$, using $m=10$ vs. $m=200$ dropped exact-match error from $1.0$ to $0.0$.
- Parallel Retrieval Optimization: For haystack retrieval with parallelism degree $p=4$, latency was mathematically predicted—and experimentally verified—to reach its minimum near $m \approx 2n / (p + 1) = 0.4n$, rather than the intuitive $n/p = 0.25n$, due to chunk overlap.
- Recursive Reasoning: On deep variable graphs ($d=8$), switching from direct answers to step-by-step reasoning eliminated catastrophic arithmetic error accumulation without increasing the number of LLM calls ($2n - n_{\text{leaf}}$) or prompt prefill tokens.
Limitations and Future Work
- Deterministic Focus: The analysis primarily studies deterministic execution (greedy decoding). Incorporating stochastic sampling schemes (e.g., Best-of-$N$, Self-Consistency, tree search) is left for future work.
- Stateless Nodes: Nodes in the computational graph are treated as stateless; the paper does not model persistent state or evolving agent memory.
- Black-Box Error Estimation: While sensitivity propagation is bounded formally, the base additive error of individual LLM calls must still be empirically profiled for specific tasks.
Summary updated