Designing Algorithms Empowered by Language Models: An Analytical Framework, Case Studies, and Insights
Authors: Yanxi Chen
Yaliang Li
Bolin Ding
Jingren Zhou
Venue: Accepted by TMLR ()

Abstract: This work presents an analytical framework for 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 such algorithms, ranging from basic LLM calls with prompt engineering to complicated LLM-powered agentic workflows and compound AI systems, have achieved remarkable empirical success, their design and optimization oftentimes require extensive trial-and-errors and case-by-case analysis. Our proposed framework serves as an attempt to mitigate such headaches, offering a formal and systematic approach for analyzing how the accuracy and efficiency of an LLM-based algorithm will be impacted by critical design choices, such as the pattern and granularity of task decomposition, or the prompt for each LLM call. Through a wide range of case studies covering diverse algorithm patterns (including parallel/hierarchical/recursive task decomposition and generic directed acyclic graphs), we demonstrate the proposed framework in action and derive interesting insights that generalize across scenarios, accompanied by systematic empirical validation in synthetic settings.

Published in Transactions on Machine Learning Research (10/2025)
Designing Algorithms Empowered by Language Models: An Analytical Framework, Case Studies, and Insights
Yanxi Chen Alibaba Group
Yaliang Li
Abbaba Croup
Bolin Ding
holin.dingg@albbbb--nn.....
Alibaba Group
Jingren Zhou
Alibaba Croup
Reviewed on OpenReview: https: // openreview. net/ forum? id- +JTEECoarr
Abstract
This work presents an analytical framework for the design and analysis of LLM-based algorithus, i.e., algorithuns that contain one or multiple calls of large language models (LLMs) sub-routines and critically rely on the capabilities of LLMs. While such algorithms, ranging from basic LLM calls with prompt engincering to complicated LLM- powered agentic workflows and compound Al systems, have achieved remarkable empirical success, their design and optimization oftentimes require extensive trial-and-errors and case-by-case analysis. Our proposed framework serves as an attempt to mitigate such headaches, offering a formal and systematic approach for analyzing how the accuracy and efficiency of an LLM-based algorithm will be impacted by critical design choices, such as the pattern and granularity of task decomposition, or the prompt for each LLM call. Through wide range of case studies covering diverse algorithm patterns (including parallel/ patrrarchcca/reeurrse demonstrate the proposed framework in action and derive interesting insights that generalize across scenarios, accompanied by systematic empirical validation in synthetic settings.
task decomposition and generic directed acyclic graphs),
1 Introduction
The rapid advancements of pre-trained large language models (LLMs) BBbeeck et al. 2023 Wei et al. 2022a; Schaeffer et al. (023) have given rise to the new paradigm of algorithmic problem solving, which utilizes LLMs as general-purpose solvers and prompts them with task descriptions and additional inputs that enhance their performance (Wei et al.] 2022b; Kojima et al. 2022 Zhang al.) 2024b). However, even the most advanced LLMs today exhibit limitations, such as finite context window sizes and difficulty with complex reasoning. Some of these limitations are fundamental (Merrill & Sabharwal 2023 Peng al. 2024 Thomm et al. 2024 Hahn & Rofin 2024 Wen et al., 2024 Merrill et al.) (0244), and resolving them requires new breakthroughs. Moreover, in resource-constraince scenarios where using the state-of-the-art LLMs is not feasible, one might have to resort to smaller and weaker LLMs for solving complex tasks.
All these have motivated the developments what we call LLM-bosed algorithmss, i.e., algorithms that contain one or multiple LLM calls as sub-routines and fundamentally rely on the capabilitics of LLMs. In its most basic form, an LLM-bbsed algorithm can be combination of one multiple LLM calls and
some prompt engineering Yao et. al. 2023a Besta et. al. 2023 Zhou et. al.] 2023 Wang et. al. 2023

---

Published in Transactions on Machine Learning Research (10/2025)
Pezeshkpour et al, 2024 Xi et al. 2023) and compound AT systems (Zaharia et al. 2024) that augment. L.MMs with additional abilities like tool use and long-term memory, as well as the emerging paradigm of LLM programming [Schlag ct al. 2023 Khattab et al. 2024 Zheng et al. 2024). LLM-based algorithms, in a similar spirit to neuro-symbolic programming (Chaudhuri el al. 2021 Gupta & Kembhavi 2023 and learning-augnentted algorithms (Mitzenmacher
More advanced examples include LLM-powered agentic workflows (Mialon al. 2023
Vassilvitskii 2022 Lindermayr & Megow| 2022). combine the advantages
of LLMs and traditional algorithms. An LLM- based algorithm, designed with human's intelligence and knowledge of algorithmic problem solving, can exhibit much better controllability and interpretability, stronger performance that is less reliant on delicate prompting, and capabilities that far exceed what a single LLM call can achieve.
Goal and motivations. A key principle underlying LLM-based algorithms is task decomposition. This is exemplified by the ReAct algorithm (Yao et al. (023b) that solve a problem via sequence of reasoning and acting steps, or long-text summarization methods that process the original text by chunks {Kryscinski cct al. 2022 Chang et al. 2024). The art of LLM-based algorithm design often lies in figuring out how to decompose the original task into sub-lasks appropriately, so that each can be handled by one LLM call or non-LLM program accurately and efficiently, and the performance of the overall algorithm is guaranteed. Numerous questions arisc in this process, such as:
While finer-grained dccomposition makes cach sub-task casier, it also increases the number of sub- lasks, which might potentially amplify the risk of error accumulation or cascading that could lead to catastrophic failure of the overall algorithm. What would be the appropriate granularity of task dccomposition that achieves a balance of these two aspects?
Different ways of task decomposition incur different accuracy and efficiency. Does higher accuracy necessarily come with worsened efficiency? When is it possible to achieve the best of both?
Long chain-of- offain-oftthought (CoT) reasoning (Wei al.) 2022b OpenAl 2024a DeepSeek-AL et al. 2025) can enhance the output quality of an LLM call, but also at substantially higher cost. the cost overhead worthy of the gain in accuracy? Should we apply CoT reasoning in solving every sub-task, apply it to a small number of critical sub-tasks only (and tolerate errors in other sub-tasks), or not using CoT at all?
Answering such questions often relies on extensive trial-and-errors in practice. Worse still, the obtained answers are often specific to a particular scenario and do not generalize to others. These challenges call for a more formal and systematic approach of algorithm design and analysis, which might help to predict the empirical performance of LLM-based algorithms, explain curious empirical phenomena, guide the choices of lyperparaneters, and potentially inspire better algorithm design.
Explain curious empirical observations
choices hyporparameters Inspire better algorithm design
LUM based algorithm
Analysis:
Design principle: task decompasition
performance of each node algorithm
Representation: computationa graph
Assumptions about LLMs
Enror metrics (accuracy)
LLM characterissics
(capabilities and limitations)
metrics (efficiency)
LLM inference service
Main contributions. As attempt towards achicving this goal, we propose an analytical framework for the design and analysis of LLM--ased algorithms,
Figure 1: An overview of the proposed analytical framework.
which is summarized in Figure [ and claborated in Section The framework represents an LLM- based algorithm as a computational graph (whose nodes correspond to the sub-tasks), and identifies key abstractions such as LLM characteristics (i.e., capabilities and limitations) and LLM inference service. Built
2

---

Published in Transactions on Machine Learning Research (10/2025)
upon these, error and cost metrics of the overall algorithm are determined by those of all graph nodes, in line with the task decomposition principle.
We further demonstrate the proposed framework in action for a diverse variety of case studies, deriving interesting and practical insights that generalize across scenarios. In particular, Section g investigates parallel decompasition, an elementary yet fundamental pattern of L.LM-based algorithms, with focus on understanding how the granularity of task decomposition impacts the efficiency (Insight [ and accuracy (Insight 2 of the overall algorithm. Section @ further studies more general patterns of LLM-based algorithms, offering insights for unified error analysis of generic algorithms under certain technical assumptions (Insight 3) critical design choices for iterative retrieval and reasoning (Insight 4 and making the proposed
framework applicable to recursive task decomposition via unrolling (Insight 5
2
An analytical framework for LLM-based algorithms
This section presents our proposed framework for the design and analysis of LLM-based algorithms.
2.1 Definition and representation
An LLM-based algorithm is simply algorithm that contains one multiple LLM calls as its key components. The simplest example would be a single LLM call. More generally, LLM-based algorithm can be agentic workflow compound Al system that utilizes multiple LLM calls and non-LLM programs to handle sub-tasks derived from the original problem, whose outputs together give rise to the final solution of the overall algorithm.
An LLM-based algorithm can be naturally represented as a compulational graph. Each graph node takes some inputs from its predecessor nodes, executes certain operations, and returns some outputs. The nodes can be categorized into two types - LLM nodes and non-LLM nodes demonstrated in Figure Within LLM node, the operations consist of a prompter that formats prompt based on the inputs, LLM call that processes the promp and parser that extracts the targeted information from the LLM's response. The prompter and parser, designed for the sub-task of the current node, serve as translators between natural language and traditional data structures. Within a non-LLM node, the operations can be anything that does not involve L.Mss. Examples include a symbolic algorithm, an APT call for a search engine, or a classical machine learning model.
Given such nodes, the computational graph is built by connecting them with directed edges that specify the data flows within the LLM-based algorithm. For example, Figure 3a shows the graph for the pattern of parallel decomposition, which divides the input problem into parallel sub-tasks, solves each of them with one LLM node, and aggregates the results for the final solution; Figure 33b illustrates an algorithm for book-length summarization (Chang et al., 2024 OpenAl 2024b), which divides the input text into multiple chunks and maintains a global summary via incremental updating; and Figure 3e represents the ReAct algorithm (Yao et al., 2023b), which consists of multiple iterations of reasoning. tool use and aggregation. The computationall-raaph formulation expressive enough to cover these diverse LLM--aased algorithms that have been proposed separately in prior works, and facilitates formal analysis for all of them in unified manner. The computational graph of an LLM-based algorithm can be pro-specified and static, or dynamically constructed at runtime, as will be demonstrated later in our case studies in Sections 3 and 4 of an LLM-based algorithm include how task decomposition is done (reflected by the graph topology and the sub-tasks of graph nodes), the methods of prompting and parsing for each LLM node, configurations of the LLM(s) being used, among others. The LLM nodes within one graph might use the same or different backbone L.MMs.
Configurations
2.2 Error and cost analysis
Given an input task and the corresponding LLM-based algorithm, we aim to analyze its performance how accurately and efficiently the algorithm solves the task akin to analysis for any generic algorithm.
1 We assume without loss generality that each LLM node contains one single LLM call, unless specified otherwise.
3

---

Published in Transactions on Machine Learning Research (10/2025)
Inputs (05)
Outputs (DS)
Inputs (DS)
Outputs (DS)
Prompter
Prompt (NL)
LLM
Response (NL)
Parser
Non-LLM program
LLM
non-LLLM node
Figure 2: An LLM node (left) or non-LLM node (right) in the computational graphs of LLM-basod algorithms. Each node can have one or multiple inputs/outputs. We use the abbreviation "NL" for "natural language", and "DS" for "data structure".
Inttal global
LLM node
summary
LIM node
instance
Didding (non-LLMi
LLM mode
Asprogation [LIM/non-LLM]
Output
Input text
Divicing (symbolic)
LUM node
summary
LLM mode
LUM node
(a)
Acting
Acting
Acting
Obsseevvtiio
Observation
Observation
Query
Reasaning (LLM)
Aggrogation
[symbolic)
Reasoning (LLM)
Aggregation
(symbolic)
Reasoning (UMI
Aparogation
[symbolic)
Answer
Figure 3: Examples of computational graph representations for LLM LLM-based algorithms. (a) Parallel decomposition. Detailed analysís and concrete examples for this graph pattern will be elaborated in Section 3 (b) Book-length summarization, ef. Figure 1 in (Chang al. 2024). The "dividing" node contains symbolic program that divides the input text into multiple smaller chunks. (c) The ReAct algorithm (Yo
et al. 2023b). Each "acting" node represents one API call for a certain tool, and each "aggregation" node aggregates the outputs of its predecessor nodes, c.g., by simple concatenation.
Following the task decomposition principle, error and cost analysis is done by analyzing for each LLM or non- LLM node first, and then for the overall algorithm. Unless otherwise specified, our analysis is deterministic, for given task instance and fixed random seed(s).
Error and cost metrics. The accuracy and efficiency of each graph node and the overall LLM-based algorithm be quantified by certain error metrics and cost metrics respectively. The performance of individual graph nodes, together with the graph topology, implies the performance of the overall algorithm. For each specific task or algorithm, one might define multiple error metrics and cost metrics, which can be analyzod in a unified manner within our proposed framework.
Error metries are task-specific in general. Moreover, the overall algorithm and the LLM nodes within it might have different error metrics. For instance, consider an LLM-based algorithm that answers a given question by first retrieving relevant sentences from the imput text with multiple LLM nodes, and then reasoning over the extracted sentences with another LLM node. In this case, the overall algorithm is evaluated by whether it answers the question correctly, while each LLM node responsible for retrieval is evaluated by whether it successfully extracts all necessary sentences within the input text that it handles
Cost metrics, on the other hand, are largely task agnostic.. Examples include the total length of prompts and total length of generated texts, measured by the numbers of characters or tokens, within one run of the overall algorithm; these metrics are correlated with the monetary costs for using proprietary LLMs via commercial
Thhooughout this work, use "aceuracy" refer the broader concept of "quality", and "error metrie" can any metric that how much the output of an algorithm deviates from certain criteria.

---

Published in Transactions on Machine Learning Research (10/2025)
API calls, well as the time and memory complexities of LLM inference. Another important cost metric is the end-to-end latency of running the overall algorithm; one particular property of this metric is that it can be impacted by parallelism of LLM calls, an important aspect of LLM inference service in practice. Other possible cost metrics include the peak memory usage, the total number LLM calls, FLOPs, energy consumption, carbon emission, among others. Unless specified otherwise, we focus on the costs of the LLM nodes and neglect those of the non-LLM nodes, since the latter is much smaller than the former in all concrete scenarios that we will consider later in this work.
LLM characteristics and inference service. For error and cost analysis of an LLM-based algorithm, it is necessary to make certain assumptions about the characteristics and inference service of the LLM(s) used within it.
Characteristies of LLMss, namely their capabilities and limitations, determine what the generated text will be for a spocific prompt, and thus directly affect the error metrics of individual graph nodes and the overall algorithm. They also affect the cost metries indirectly, via the lengths of prompis and generated lexts. Assumptions LLM characteristies can be task-specific or task-agnostic.
Assumptions on LLM inference service Yuan et al. 2024 Pope et al. 2023 Zhou et al. 2024). on the other hand, are task-agnostic and only affect the cost metrics, not error metrics. In particular, they determine the relation between the cost metrics and the lengths of prompt and generated text for each LLM call, the parallclism of LLM calls, among others. While LLM inference service in practice can be very diverse, we will see very soon that unified and formal analysis is possible with appropriate abstractions of it.
Error analysis. The error metrics for the output of each LLM node, which are calculated with respect to what the output should have been if all nodes accomplish their tasks with exact accuracy, depend on the characteristics, i.e., capabilities and limitations, of the LLM, as well as the specific problem instance and random seed(s). For a certain node v, the error of its output y can be bounded by some function fe (which depends on the aforementioned factors if u is an LLM node) of the errors of its inputs 2 .2,..., Tke Lee,, the outputs of its predecessor nodes:
E(v) S (()) ((xs))
(1)
The function fo can be general, for example:
E(y) < Gej E(mi) or Eiego E1;)). Such linear relationship will appear in a counting task that will be elaborated in Section 3
Ev)) minjejM] E(x:). In coding task, the algorithm might generate multiple code samples, and succeed as long one of the samples is correct (by passing all test cases).
Ev) < max E(x)). This is the case for sorting lask to be introduced in Section 3 where node v is responsible for merging multiple sorted lists and & stands for the foo error.
Finally, the error metrics of the overall algorithm are exactly those of the particular graph node that generates the final solution returned by the algorithm.
Cost analysis. Let us first consider the cost of one LLM call for specific input prompt, which consists of prefilling phase with a prompt of length Epre and a decoding phase that generates text of length L In our framework, we assume that the cost C of one LLM call can be bounded by
C C(prefilling) + C(decoding) = (Cre + Cdec Corer Ldec) = CLLM Ldec).
(2)
The functions Cpre and Cdec are specific to each LLM call, and depend the choices of cost metrics and LLM inference service. For example:
Charges of API calls: Cpre and Casc are lincar functions, namely (Cpre) Cpre x Cre Coec Ldec) = Gdee Ldec, where cpre and Cdec are the cost per token for the prompt and generated text. respectively.
5

---

Published in Transactions on Machine Learning Research (10/2025)
Latency: in memory-bound scenario (Agarwal et al. 2023 of memory TO (for loading model weights and KV caches) is dominant, we have approximately ( = (()) and Cdec Ldec) Ldec) = (Cdee); more generally, Cpre and Cdec might grow linearly or quadratically (e.g., for Transformers with full attention (Vaswani et al. 2017 with Lpee and Ldec-
where Lpre is limited and the latency
The cost of the overall algorithm can be written as a function of the cost metrics of all LLM nodes within its computational graph. It might be simple sum, e.g., for LLM API costs, or a more complex function, e.g., for the end-to-end latency in the presence of parallelism. As an example, consider & independent LLM calls with latencies Ci, C2, C, and ideal parallelism of degree p, i.e, no extra cost is induced by parallelism; then, the LLM calls can be divided into g [k/p] sequential groups, where each group of p parallel LLM calls is bottlenecked by the one with the largest latency, and thus the end-to-end latency becomes
C= Σ max (Cu- ()-1)) Cmin(tr.k)
(3)
jEGs
This result will be especially useful for our analysis parallel decomposition later in Section Remark 1. When applying the proposed framework to new task, we need to first characterize the capabilities and limitations of LLMs for this task (or for the sub-tasks derived from it), e-g., via profiling with handful of "training samples". This characterization can be quantitative or qualitative, procisc or coarse, depending on the purpose of analysis. For example, in many lasks of interest, a larger problem instance is harder than a smaller one, and thus incurs larger error metrics of an LLM call. For practical purposes like hyperparameter optimization, such coarse characterization might be sufficient already.
Remark 2. Understanding LLM inference service, especially from a system perspective, is crucial for in-depth analysis of cost metrics. LLM inference service can be diverse in practice: LLMs might run on CPUs in a personal laptop or on a distributed GPU cluster, inference might be compute-bound or memory-boun,, the complexity of long-sequence processing and generation might be linear or quadratic, parallelism at various levels (c.g., multiple LLMs deployed on multiple machines, or batch inference with one LLM) might be supported, and on. These are covered by our proposed framework in unified manner.
3 Case studies and insights: parallel decomposition
This section is dedicated to parallel decomposition, basic MapReduce-like pattern (Dean & Ghemawal, 2008) visualized in Figure 3a For concreteness, we consider three canonical tasks, which are abstract and synthetic versions of practical LLM applications.
(1) Counting: given string of length consisting of letters and digits, count the number of digits in it. (2) Sorting: given a list of n numbers, sort it in ascending order. (3) Retrieval: answer a given question that requires retrieving some key information from a long piece of text, Table I summarizes the LLMebased algorithms for solving these tasks by parallel decomposition, and Table presents a worked example for the counting task. Supplementary details for these lasks, as well as additional examples of parallel decomposition, can be found in Appendix A
A problem of particular interest in practice is: what is the proper granularity of task decomposition, the sub-lask size m, for solving lask of size n by pavallel decomposilion?? More specifically, we strive to answer the following questions:
Q1. How does the overall cost of the LLM-based algorithm change with the sub-task size mi?
Q2. Does a smaller m, Lee, finer-grained task decomposition, always imply a smaller final error?
Throughout this section, we answer these questions by leveraging the analytical framework proposed in Section 2 The results are summarized in Insights | and which will also be validated empirically.
Why synthetic tasks? For the purpose of building a solid foundation for rigorously understanding the accuracy and efficiency of LLM-basod algorithms, we have chosen to stick with synthetic scttings for our empirical studies in this work. This brings various benefits, such as reducing the risk of test data contamination, facilitating unambiguous and precise measurement of accuracy, allowing full transparency

---

Published in Transactions on Machine Learning Research (10/2025)
Table 1: Three concrete examples of parallel decomposition.
Task
Counting
Sorting
Retrieval
Step 1
Divide the input string into & disjoint sub-strings of lengths mı, ; M..
Divide the input list into k: disjoint sub-lists of lengths mu, ,y,,, ma.
Divide the input text into k overlapping chunks of lengths ma, My,
Step 2
For each i [k], use LLM call to count the number digits in the i-th sub-string, which returns an answer ye.
For each E [k), use LLM call to sort the i-th sub-list, which returns solution y1-
For each E [k], use one LLM call to try to answer the question based on that chunk.
Step 3
The final solution of the algorithm y Eiew Vi. symbolic algorithm (Listing D
Merge the sub-lists y1,-... Generate the final answer by into single list y using majority voting" of the valid answers'.
We adopt majority voting because, as the input text is chunked with overlapping, the correct answer might appear multiple times in Step 2. Moreover, there might cxist false positives in Step 2, in which case majority voting brings extra robustness. In Step 2, LLM call might return "I don't 't know" if it decides that the corresponding chunk does not contain sufficient. information for answering the question. Such answer is considered invalid, and excluded from majority voting in Step 3.
Table 2: A worked example for the counting task, showing the prompt and response of a specific LLM node.
# Prompt
User: Count the number digits in the following string:
Answer the following format: 'There are {ansver} digits in the given string'.
Do NOT output anything else.
# Response
Assistant: There are 19 digits in the given string
and control over task configurations, and making the current work as self-contained as possible. We start with the simplest settings and algorithms (for didactic purpose) in this section, and will gradually expand our proposed framework more complex and practical scenarios resembling those in prior empirical works, e.g.; retrioval-augmented generation in Appendix A.5 iteratíve retrieval and reasoning in Section 4.2 active information seeking and aggregation with recursive task decomposition in Section 4.3
Formal notations. We let denote the size of the input problem instance; it can be the length (e.g.. the number of characters tokens) of the text that represents the input problem instance, defined in terms of traditional data structures (e.g., the length of list). Let & denote the mumber of parallel sub-tasks after decomposition, and my denote the size of the i-th sub-task, where i E [A]. It is assumed that m, S m for some maximum value m that can fit into the context window of the LLM used by the algorithm. For most of our analysis, we will assume for simplicity that m, = m for all E [k], and that k = O(nmm). We denote p 2 as the maximum degree of parallelism supported by L.LM inference service. Finally, let fays be an upper bound for the length of the system prompt of cach LLM call, which includes everything in the prompt except for the input problem instance itself. The presence of Lays, which can be large in practice is essentially due to the fact that the LLM is used as general-purpose sub-routine, hence specifying the concrete task for each LLM call constitutes part of the complexity.
For notational convenience, we will often write f(n) S g(n) in place of f(n) = O(g(n),, which means there exists a universal constant > 0 such that f(n) < C- (Cg(n) for any positive integer n. In addition, f()) x g(n) means f() & g(n) and g(n) & f() both hold. To further simplify notation, we will often omit the big-O notation in the input arguments of cost functions Cpre/Ceec/ /CCec/CLLMM for example, given a prompt of length Lays + On)), will write the cost of the prefilling phase Cpre (oys + n) rather than Care(ayy (()).
7

---

Published in Transactions on Machine Learning Research (10/2025)
3.1 Answering Q1: cost analysis
We assume for simplicity that all parallel LLM nodes share the samne LLM backend and inference service, and thus the same cost functions Cpre, Cdec and CLLM-
The direct sum of costs. In many cases, the cost of the overall algorithm is the direct sum of the costs of LLM calls involved, egg., the monetary cost API calls for proprietary LLMs, or the end-to-end latency when all LLM calls are exccuted soquentially. In such cases, we can write the total cost C
C C(sub-tasks) C(aggregation),
where Claggrogation) is the cost of the final aggregation step, and C(sub-tasks) = k x C(one sub-task) I k x CLLMM(Sys + m, Ldee)
S n x CLUM(Gays + m, Ldec)
(4)
Here, the first inequality follows Eq. the second inequality follows k S n/m, and Lsec = (me is task-specific, e.g., O(1) for the counting and retrieval tasks, or (m)) for the sorting task.
This basic analysis already provides some hints for tuning the hyperparameter
If CLys + m, Ldec) Cpre (Cyys + m) + Cdec + m, Ldec) grows with at linear or sub-linear rate, then the right-hand side of Eq. 4 is monotonely decrcasing in m, which means C(sub-tasks)
is minimized at min(n, m.
A Transformer model with full attention suffers from quadratic complexity in long-sequence processing (Yuan et al. 2024 Zhou et al. 2024). With the simplified assumption that (Lays + m, Ldec) $ (osys m) we have
C(sub-tasks) S n CLLM(Coys + m. Ldee) S n
(Lays + m)2
+ m 2L
m
m
m
Assuming that m is sufficiently large, the right-hand side achieves the minimum x X Lays at an intermediate value m Lays-
More generally, may assume that
CLLM + m. Laee) S a x (Cays -m)² + B x (Lags + m) +
which takes into account a more precise characterization of LLM inference service, including the FLOPs as well as memory 10 for loading model weights and KV caches. In this case, we have
C(sub-tasks) E x CLLM( + m, Ldec)
(Cays + m)² + 3 X (Lays + m) +
C2 m
Lays +
=nx a x m
+ +2x Lays + +8).
and the right-hand side is minimized at C2na + Loys x B/B
The latency with parallelism. The above analysis can be exlended to the case with parallelism, which is especially relevant to the end-to-end latency of the overall algorithm. Considering parallel LLM calls for homogeneous sub-tasks in an ideal setting where parallelism incurs no additional cost, we have
k x CLLM + m, Ldec)
C(sub-tasks)
<
(5)
p
8

---

Published in Transactions on Machine Learning Research (10/2025)
according to Eq. 3 For large such that & S p. we have [k/p] = and thus C(sub-tasks) CLys + m, Ldee) is monotonely increasing in m. On the other hand, for sufficiently small and hence large k, we have [k/p] x k/p, and thus the upper bound for C(sub-tasks) can be approximated by
C(sub-tasks) S k x CLLM(Cays + m, Ldes) S " P
CLUM( + m, Ldec)
which might be monotonely decreasing in m if CLLm + m, fede)) grows with at a linear sub-linear rate. In this case, the overall cost C(subttasks) is minimized by ts x and hence m x n/p.
Summary. With the above analysis, our answer to Q1 is summarized as follows:
Insight 1. The relationship between the overall cost C(sub-tasks) and the sub-task size m depends on various factors, such as the choices of cost metrics and assumptions about LLM inference service. For example: (1) the direct sum of costs is minimized CLLm( + m, (m)) grows with m at faster rate; (2) if CLLM(Says + m, (m)) grows with (sub-)linearly, then the end-to-end latency with parallelism degree is minimized at m x n/p.
smaller value of if each sub-task cost
3.2
Answering Q2: error analysis
While error analysis is task-spocific and has to be conducted case by case, we will see that general principles can be derived for the pattern of parallel decomposition, to be summarized in Insight 2
3.2.1 Counting
Assume for notational convenience that m, m for all i [k), and & n/m is integer. We denote the ground-truth count for the complete string as y", and the ground-truth count for the i-th sub-string v
If & represent the absolute counting error, then the overall error is bounded by the sum of sub-task errors:
E(y) = ly --
Σ (y - ut) xE[k]
<
18
vil =
E(y:).
kE|
KE(A]
If & represent the normalized counting error instead, then
E(y) = y - 1r1
vil =
Σ E(1)),
n2
1o
m
k KE(
KE[K]
KE[M]
i.e, the overall error bounded by the average sub-task errors; since a smaller value m makes each sub-task easier, it is reasonable expect that the overall error Ely) will also become smaller as m decreases.
3.2.2 Sorting
Compared to counting, there are more diverse phenomena in the sorting task in terms of error metrics. In particular, there exist various failure modes in sorting with an LLM-based algorithm: (1) the output list might not be monotone; (2) the length of the output list might be larger or smaller than that the input list; (3) the output list might contain numbers that do not match exactly those of the input list.
To accommodate these failure modes, we may define the following error metrics for sorting a list, where y denotes the solution returned by the algorithm and y* denotes the ground-truth solution:
Exact-match error: = if matches y* exactly, and & = 1 otherwise;
Non- Con-monotonicity error: Eie(n- max Det1, 0), which is zero if and only if y is sorted;
mismathh ervor: & = |len(y) - len(y")) |len(y) nl:

---

Published in Transactions on Machine Learning Research (10/2025)
Fuzzy Lo and fuzzy normalized & errors: first convert, via simple extending or truncating, the output solution y to a version D that matches the length n of the input list, and then calculate the fuzzy foo error as E = 1 -yyll = maxiglm] Ii Ve ls or the fuzzy normalized & error as = 1 v*ll Eie(m) I MZ
Note that the same error metrics can be similarly defined for each parallel sub-task in Step 2 of the LLM- based algorithm, and it is reasonable to expect that they become smaller as the sub-task size decreases. On the other hand, analyzing the errors of the overall algorithm after the final merging step can be more complicated. As an example, focusing on the third failure mode and the Loo error metric, we have the following theoretical guarantee (whose proof is deferred to Appendix (..344):
Proposition 1. Assume that for each E [k], the solution yı returned by one LLM call for the i-th sub-task is monotone, matches the length of the corresponding imput æs, and has an lor error & Then the loo ervor of the final solution y is upper bounded by & max{E,,...,...
Consequently, if each sub-task error is monotone in m, then this error bound also monotone in m.
3.2.3 Retrieval
For the retrieval (or needle-in-a a-ataaaahaakk (Kamradt) 2023 task, we start by identifying two failure modes of each LLM call for retrieving the targeted information from a chunk of size m Step 2 of the algorithm:
1.
The LLM might mistakenly return "I don't know" or an incorrect passcode when the chunk contains the specific needle that necessary and sufficient for answering the question. In general, this failure mode will occur more frequently for larger values of m. Our early experiments with various LLMs confirmed that this failure mode begin to manifest when exceeds certain LLM-specifie threshold.
2. The LLM might mistakenly return a wrong answer when the needle is actually absent from the chunk (i.c., false positives). We observed empirically that some LLMs are more susceptible to this failure mode even when the value of m is small, while others are less so.
Based on the above observations, we can hypothetically categorize LLMs into two types: Type-A LLMs are only prone to the first failure mode, while Type-B LLMSs are prone to both.
It turns out that error analysis for the overall LLM-based algorithm depends critically on which type of LLM is used. If a Type-A LLM is used, a smaller value of m means the first failure mode is less likely to occur in Step 2 of the algorithm, which implies higher accuracy for the final solution of the overall algorithm. On the other hand, analysis is more complicated if a Type-B LLM is used, since both failure modes can possibly occur in Step 2 of the algorithm: a larger value m means the first failure mode more likely to occur, while a smaller value of m implies a larger number of chunks k x n/m, which can potentially increase the chance of error in the final step of the algorithm (i.c., majority voting), due to the frequent occurrence of the second failure mode in Step 2 of the algorithm. Consequently, the minimum error of the overall algorithm might be achieved by some intermediate value of m that achieves a balance between the two failure modes. If n is too large, then there might not exist a good value of m that can achieve a low error, as either failure mode must occur with high probability.
Remark 3. We present informal probabilistic analysis for the case of using Type-B LLM. Given the sub-task size m. denote the probability of the first and second failure modes as pi (m) and Pa(m) respectively. Then, the success rate of retrieval for the chunk containing the needle is 1 1-P1(m) (m), while the expected number of false positives from the remaining chunks approximately l x P2(m) = n x p2(m)/m. One might opt for a relatively small value of m, which hopefully increases --Pim)) and hence mitigates the first failure mode. However, even if p2(m)/m m is very small, say 10-3, the number of false positives can be large if the size of the original problem is large, causing errors in the solution returned by majority voting.
3.2.4 Summary
With the above analysis, we summarize our answer to Q2 as follows:
10

---

Published in Transactions on Machine Learning Research (10/2025)
Insight 2. If (1) each sub-task error is monotonely increasing in the sub-task size m, and (2) the overall error bounded by smooth aggregation (e.g., mean or max) of sub-task errors, then the overall error can be reduced by finer-grained parallel task decomposition, i.e,, smaller m. Otherwise, caution should be taken: there exist cases (e.g., retrieval with Type-B LLM) where the final output of the overall algorithm can be sensitive to individual sub-task errors, and finer-grained parallel decomposition (accompanied by larger number of sub-tasks) does not necessarily imply a smaller final crror.
0.25
0.8
Latency
0.15
0.10
0.6
0.00
100
200
100
150
200
50
100
150
200
50
100
150
200
Sub-owsk N2w
Sub-reek size
Sub-owsk
Sub--aukk
(a) Counting with -amnaa---BBIn-ttee n
200 is fixed while 17 varies..
Turny normalleed
0.25
32.5
0.20
0.15
27.5
15
0.10
0.00
22.5
(b) Sorting with Llama-3-70B- Instrucc;, 200 fixed while m varies. See Appendix A.3.3 for analysis and explanation of the zigzag part in the latency with = 4.
3.8
12.5
7.5
0.0
2,5
-02
0.5
5000
10000
2500
10000
(c) Retrieval with Llama-3-770B-nnstrues 10000 is fixed while m varies.
150
125
0.8
30
100
15
10
Sub-tokk
Sub-taek
(d) Retrieval with Llama-3 3-B-mm------IIncutttt 10000 is fixed while varies.
Figure 4: Empirical results for concrete examples of parallel decomposition. Each curve represents the mean and standard deviation 10 independent trials. See Appendix A for further details and complete results for the case studics on parallel decomposition.
11

---

Published in Transactions on Machine Learning Research (10/2025)
3.3 Empirical validation
The previous analysis has been validated empirically via experiments with Llama 3 models Meta 2024 A subset of empirical results are presented in Figure | with full implementation details and experimental results deferred to Appendix A For each figure, we fix the problem size n and use the sub-task size m as the X-axis.
Figure | confirms that for all tasks, the end-to-end latency of the overall algorithm is monotonely decreasing in m when the parallelism degree p (i.e.; no parallelism), non-monotone in with finite parallelism degree p 4, and monotonely increasing in when p 20, predicted by Insight 1
Figure 4 also shows that error metrics increase with m for the counting and sorting tasks, as well as for retrieval with --aaa---77-IIstrucct in contrast, errors are non-monotone in m for the retrieval task with Lamma-3-B-Instaan which is susceptible to false positives in retrieval (see Figure 13b
Appendix A.4.3)
and thus regarded as a Type-B LLM (ef. Section 3.2.3
4 Case studies and insights: more general patterns
In this section, we demonstrate the proposed analytical framework in action for more diverse patterns of LLM- based algorithms. Our exploration covers unified error analysis under the assumption of additive errors and bounded sensitivity (Section 4.1), two algorithms for iterative retrieval and reasoning that exhibit the pattern of hicrarchical decomposition (Section 4.2h, and an algorithm that conducts recursive task decomposition and constructs its computational graph d dynamically at runtime (Section 4.3 The corresponding analysis and results are summarized in Insights 3 and respectively.
4.1 Unified error analysis for directed acyclic graphs
For generic LLM-based algorithms that are represented by a direct acyelic graphs (DAG) and satisfy the technical assumption below, our framework allows deriving error bounds for them a unified manner:
Assumption 1. We say that an LLM--based algorithm satisfies the assumption of additive errors and bounded sensitivity, if for each node v with k inputs # T1...., Tx and a single output y, it holds that
E(v) S ((())))) E(xx)) E, + S
E(x4)
kE[k]
for some node-specific additive error E, and finite sensitivity parometer 2 0.
Proposition 2. Consider an LLM-based algorithm, represented by a DAG, that satisfies Assumption 4 Then the error of the output y(v) of any node v, including the one that generates the final oulput of the overall algorithm, is bounded by
8(y(t)) S Σ Σ
Slpathl E
(6)
NEV pathEP(ww-to)
Here, V denoles the node set of the DAG, |path) denoles the length of path on the DAG, and P(w + v) represents the set of paths from node w to node v if w + U, or a singleton set containing one hypothetical path of length if w = v. For the special case of S = this upper bound can be simplified as E(y(v)) S Evev IP(w- + v) Ew, where [P(w- > w)] denotes the number of paths from V.
This result, whose proof can be found in Appendix B characterizes precisely how individual sub-task errors propagate through the graph to the final output of the overall algorithm, depending the number and lengths of paths between graph nodes and the value of the scnsitivity parameter S:
Insight 3. Under the assumption of additive errors and bounded sensitivity, Proposition 2 indicates that:
(1) the final error of the overall algorithm is weighted average of all node-specific additive errors (Ew);
(2) the impact of cach node-specific error E grows (resp. shrinks) exponentially along each path to the final output if S >> (resp. S < 1), and also grows proportionally with the total nunber of paths.
12

---

Published in Transactions on Machine Learning Research (10/2025)
Justifications for Assumption 1 In some cases, Assumption | can be rigorously proved for a non- LLM node. For example, considering the aggregation node in the counting algorithm, our analysis in Section 3.2. implies that Assumption | holds true with node-specific additive error &, = O, and sensitivity parameter S = for the absolute counting error, or S = 1/k for the normalized counting error. As another example, considering the aggregation node in the sorting algorithm, Proposition indicates that its output lo error is bounded by S max Ex} S +..... Ex, which means Assumption 1 holds with & =0 and S ==1. 1.
|
For an LLM node, "additive error and bounded sensitivity" is assumption that we impose on the stability of an LLM's behavior when solving a sufficiently simple (with respect to its capability) sub-task. One motivating example comes from our case study to be presented in Section 4.3 which involves many LLM calls that are asked to calculate a 1-Lipschitz function (such as sum or max) of multiple input variables. We have observed empirically that the LLM, with CoT prompting, behaves with sufficient stability and makes small errors only occasionally. It this property that ensures the final error of the overall algorithm stays low and grows slowly (instcad of blowing up) with the task complexity and size of computational graph.
Needless say, there exist practical situations where Assumption does not hold (e.g., when the LLM's behavior is sensitive to input errors), in which case Proposition 2 is not applicable.
4.2 Iterative retrieval and reasoning
We consider a task, as an extension of the retricval task in Section 3.2.3. that roquires multi-hop reasoning over multiple clues ("needles") embedded separately in long piece of text ("haystack"). For example, the targeted question might be "what is the numeric value of A", while the needles are "A = B", "B = C", and "C
100", A practical approach for such a task is iterative retrieval and reasoning (Creswell et al.] 2023 Xiong
ct al. 2024 Twen-Team 2024 Yue et al.) 2024]: at each iteration, the algorithm performs retrieval based on the targeted question and the collected information from previous iterations, followed by reasoning over the retrieved information and deciding whether the targeted question can be answered already or requires further retrieval and reasoning. Within each iteration, retrieval can be done along with chunking, which leads to a pattern of hierarchical decomposition. Two variants of this approach are visualized in Figure 5 the "cyclic" version conducts retrieval over multiple chunks sequentially within each iteration, while the "parallel" version conducts retrieval in parallel. When adopting such an algorithm, two critical design choices need to be made:
1. For the "reasoning" nodes, one might prompt the LLM to "answer dircetly" for efficiency, or "think step by step" to potentially improve accuracy. Which option is better? How much cost overhead will be caused by chain-of-thought prompting in exchange for accuracy improvement?
2. For the task of retrieval from nultiple chunks at each iteration, which option would be more efficient, the "cyclic" or "parallel" one?
Our answers, derived with the proposed analytical framework, can be summarized as follows:
Insight 4. (1) Using chain-of-thought prompting for the reasoning nodes (which play a critical role in deciding the final output) will significantly boost accuracy, while incuring only a minor, additive cost overhead to the overall algorithm. See Fq. 9 and Fq. (10) in Appendix C.3.2 for the quantitative version of this statement. (2) The "cyclic" version requires fewer iterations, while the "parallel" version can benefit from parallelism. As result, in terms of the end-to-end latency, the "cyclic" version is likely to have advantage when the parallelism degree is small, while the reverse is true otherwise.
These insights have been validated empirically via experiments with Q Instrucct (Yang et al, 2024h. For example, Figure 6al shows that, across broad range of degree g (a measure of task complexity), prompting the LLM to calculate step by step for the reasoning nodes significantly roduces the error of the final output, while incuring negligible or no overhead in the total number of prefilling tokens, and minor overhead in the total number of decoding tokens. Moreover, Figure 6b compares the end-to-end latencies of two options for retricval: "cyelic" achioves lower latencies across a broad range of width w (another measure of task complexity) when there is no parallelism among LLM calls (i.e., p= 1), wheras "parallel" can benefit from an increased value of parallelism degree p and gain advantages over "cyclic".
13

---

Published in Transactions on Machine Learning Research (10/2025)
Inst al reforences [[] (lst of retrieved sentenced)
Input clues question
Retrieval
Retrieval
Retrieval update ref
Retrieval updete
Input clues questton
Retrieva
Retrieval
Recrivval update ref
Retriesal & update
Chunking
Outout answver
Chunking
Retrioval
Retrieval
Initial references
Update ref.
Update ref. reasaning
Reasoning
Ressoning
sentences)
LLM decides
the decides not to answer: use references for the next round of retrieval
(a) The "cyclic" version.
(b) The "parallel" version.
Figure 5: Two algorithms for iterative retrieval and reasoning. The number of iterations is assumed to be here; in reality, this value determined adaptively by the algorithm itself at runtime. For clarity, some LLM non-LLM nodes (cf. Figure 2) are merged into one, and arrow from the "chunking" node to shaded block means that each "retrieval" node within the block takes the corresponding chunk as input.
150
Answer directly
100000
Answer directly
Arswer directly
125
Calculate step by
Calculate
3580
Calculate by
90000
Absolute errer
100
Profiling Tokons
3000
80000
75
Decoding
2500
70000
2000
25
60000
1500
50000
1000
25
Degree 9
Degree g
Degree g
(a) Comparing two prompting methods ("answer directly" versus "step by step") for the reasoning nodes.
250
-
Cyclic Parallel
225
Cydic Parallel
Cycic
Parallel
200
Latency, paw (sec)
Latency (ee))
150
150
150
125
Latency,
100
100
75
50
25
50
100
150
200
250
300
50
100
150
200
250
300
100
150
200
250
300
Width
Width
Width
(b) Comparing two versions ("cyelic" versus "parallel") of iterative retrieval and reasoning.
Figure 6: Empirical results for itcrative retricval and reasoning. The X-axis of cach figure denotes a mcasure of task complexity. See Appendix C for further details and complete results of this case study.
We refer interested readers to Appendix for full details and results of this case study.
4.3 Recursive task decomposition
For the last case study, we study LLM--basod algorithms with recursive task decomposition. A recursive LLMd- algorithm starts from the original task of concern and recursively generates more intermediate
sub-tasks, that each sub-task be solved by aggregating the solutions to its children tasks, while being
14

---

Published in Transactions on Machine Learning Research (10/2025)
The ground-truth DAG relevant variables:
C
variables
Salved:
Solved: 4
Solved: f
Salved: [D,
Legend:
Task that has been Initialized but yet processed
6
Active task
Value found by LUM
Value found from dictionary
Solved: E,
Solved: (D, C,
Solved: C,
Figure 7: The computational graph of a recursive LLM-based algorithm is constructed dynamically, while a dictionary of solved tasks is maintained to avoid solving the same intermediate sub-task repetitively.
500
8000
directly
Calcullate step by stop
10000
Calculate step by stop
Calculate step
lite stop stop
400
250
Nexoline eror
300
mwitling Interns
8000
200
6000
Ducoding
4000
100
4000
2000
100
0-
2000
Dapth df
Dspth
Figure 8: Empiriaal results for recursive task decomposition. The X-axis of each figure denotes measure of task complexity. See Appendix D for further details and complete results of this case study.
unaware of other sub-tasks involved in the overall algorithm. In particular, solving and/or decomposing each sub-task can be achieved by LLM calls, while the outline of recursive task decomposition remains symbolic. Another feature of a recursive LLM-based algorithm is that its computational graph is not pre-specified or static, but rather constructed dynamically at runtime. Such algorithms have been widely adopted in prior
works (Kazemi et al. 2023 Schlag et al. 2023 Prasad et al. 2024 Schrooder et al. 2024 Lee Kim 2023
Khot al. 2023 Zhu al. 2024).
For concreteness, consider task that requires finding the value of specific variable connected to large number of other variables. Figure 7 shows an example, where the targeted variable A depends on B and C, and variable B further depends on C, D and E, and so on. The LLM-based algorithm need to decide adaptively which variables to query information about, and to execute the necessary calculation along the way. complete description of the recursive algorithm for this task can be found in Appendix D.2 Despite how different such an algorithm might scem from the previously investigated ones, can still be covered by our proposed analytical framework:
Insight 5. (1) The framework proposed in Section is applicable to a recursive LLM-based algorithm,
by unrolling it into a directed acyelic graph, as illustrated in Figure 7 (2) For the concrete example, prompting the LLM to conduct arithmetic calculation step by step will significantly boast the accuracy of the overall algorithm, but also increase the cost by a multiplicntive factor. See Eq. 11] Appendix D for the quantitative version of this statement.
The sccond insight has boen validated empirically via experiments with Oven-2-72B-Instrue (Yang et al. 2024). For example, Figure @ confirms the accuracy gain by prompting the LLM to calculate step by step, and shows that cost metries grow linearly with the depth d (a measure of task complexity); furthermore,
15

---

Published in Transactions on Machine Learning Research (10/2025)
step-by-step prompting has negligible impacts on the total number of prefilling tokens, but increases the total number of decoding tokens and end-to-end latency multiplicatively.
We refer interested readers to Appendix D for full details and results of this case study.
5
Related works
LLM-based algorithms. The concept of L.MM-based a algorithms is fairly broad and general. ranging from
combination of one or multiple LLM calls with some prompt engineering (Yao et al.,
2023a
Besta et al.
2023
2024
Lei et al.) 2023 Saha et al.] 2023 Zhou et al.] 2023 Wang et al.] [023 Prasad et al.
2024;
Chang
et al.
2024).
to Mowered agent systems (Mialon et al. 2023
Wu et al,, 2023
Hong et al, 2024
Gao
ct al.
2024a.
Shen et al. 2023; Zhuge et al. 2024 Pezeshkpour et al. 2024
Xi ct al.
2023 Qian et al.
2024
Kapoor et al. 2024; Sumers et al.) 2024 Anthropic 2024) and compound Al systems (Zhariia et al.
2024
Chen et al.
2024) that augment LLMs with additional abilities like tool use and long-term, memory, and to
the emerging paradigm of LLM programming (Schlag et al.] 2023 Khot et al. 2023 Khattab et al.! 2024
Zheng ct al. 2024| Kambhampati et al., 2024). Some elements of the framework proposed in Section 2 such
as the task decomposition principle, the computational graph representation, evaluation of and comparison between LLM-based algorithms with accuracy and efficiency taken into account simultaneously (Wang et al, 2024 Kapoor et al. 2024), etc., have alrcady appeared in one way or another in these prior works. It is primarily our unified, systemalic and formal investigation into the design of generic LLM-based algorithms, and the analysis of their accuracy and efficiency (akin to analysis of traditional algorithms), that distinguish the current work from this vast literature. It is worth noting that (Wu et al. 2025) presents formal analysis for thain-of-thought reasoning, and (Snell et al. 2024) presents formal analysis for sequential and parallel sampling. Both works are similar in spirit to the current. work, although the problem formulations and methodologies are mostly orthogonal and complementary.
LLM test-time scaling. Recent works have started to investigate, analytically or empirically, the scaling laws of LLM test-time computation. One line of research is about the scaling properties of repeated sampling, e.g.; randomly sampling multiple generations for the same prompt and then aggregating them for the final
output (Chen et al., 2024 Brown et al.) 2024 [nell et al. 2024: Wu et al. 2024 Chen et al., 2025), which might be regarded as a stochastic variant of parallel decomposition investigated in Section 3 Our work is orthogonal and complementary to this line, as our analysis is deterministic and largeted al generic patterns of LLM-based algorithms. One potential direction for expanding the analytical framework proposed in this work would be to augment with stochastic decoding and repeated sampling, along with relevant thcoretical results. Another line of works is about improving the oulput quality of an LLM call by generating more tokens autoregressively, e.g., via srain-of-thougee (Wei et al. 2022b Kojima et al. 2022 reasoning. This idea has been investigated theoretically (Feng et al. 2023 Merrill & Sabharwal 2024 Li et al., 2024b), and further popularized recently by OpenAl-ol (OpenAl 2024a), DeepSeek-RI (DeepSeck- AI et al. 2025), among many others. As this approach of scaling up the test-time computation of individual LLM calls is becoming more widely adopted, it is important to understand, analytically and quantitatively, how it will impact the overall accuracy and efficiency when such LLM calls are embedded within an LLM-based algorithm. Our work can be useful in achieving this, as illustrated in the case studies in Sections 4.2 and 1.3 where the impacts of prompting LLM calls to "think step by step" versus "answer directly" can be characterized analytically with our proposed framework.
Connections to non-LLM literature. Our work has drawn inspiration from the area of learning- augmented algorithms (Mitzenmacher & Vassilvitskii 2022 Lindermayr & Megow 2022). One standard paradigm of this area is to consider specific task (e.g., sorting (Bai & Coester 2023 or clustering (Ergun ct al. 2022)). ), assume access to black-box machine learning model that satisfies certain propertics (c.g., what additional computation or information it can offer), propose a novel algorithm that leverages this ML. model, provide theoretical guarantees for its accuracy and efficiency, and show the improvements over traditional, purely symbolic algorithms. Our work similar in spirit to this line of rescarch, but also substantially different, in that our framework is targeted at generic tasks and LLM-based algorithms, with assumptions the capabilities, limitations and inference service of LLMSs (regarded general-purpose problem solvers)
16

---

Published in Transactions on Machine Learning Research (10/2025)
that are quite different from typical assumptions for task-specific ML models in the literature of learning- augmented algorithms.
Our work is also connected to the literature of distributed computing (Lynch] 1996) (in particular, the MapReduce model (Dean & Ghemawat, 2008 Karloff et al. 2010) that the parallel decomposition pattern in Section closely resembles). as well as classical / non--ILM algorithm design and analysis (Cormen et al. 2022 Roughgarden 2021). When positioned in this context, one major contribution of our work is (1) identify the relevance of foundational clements in computer science task decomposition, computational graphs, MapReduce, etc. to the LLM context, and (2) integrate LLM-based algorithms with these elements, other theorctical tools, and symbolic programs, via appropriate abstractions and characterization for black-box LLMs. This is the key to facilitating formal analysis for the accuracy and efficiency of LLM- based algorithms. The unique and diverse features of LLMs and their implications distinguish our work from the classical / non-LLLM literature.
6 Conclusion
This work has introduced an analytical framework for studying the design and analysis of LLM-based algorithms. With the task decomposition principle, the computational graph representation, and other key abstractions tailored to LLMs, we are able to provide formal analysis for the accuracy and efficiency of generic LLM--baed algorithms, as demonstrated through diverse range of case studies.
One limitation of this work is the lack of empirical studies in more realistic settings. Although have presented case studies and empirical validation for various algorithms and synthetic settings (ranging from the most basic setting- - parallel decomposition - to more complex ones that resemble the settings in prior empirical works), there is obviously a gap between them and the most complex agentic workflows in real-world scenarios. henetheless, we believe that the results in this work can have broader implications in more general scenarios than the synthetic ones. For example, Insights [ and 2 can, at the minimum, warn practitioners against the common misconception that "finer-grained task dccomposition implics higher accuracy / higher total cost for the overall algorithm", beyond the parallel decomposition setting where these insights were originally derived. Moreover, we anticipate that our analysis for simple patterns could be used as building blocks for analysis of more complex algorithms since, as highlighted in Anthropic (2024), the most successful LLM agents in industry are often built with "simple, composable patterns".
We hope that our work will inspire future work on enhancing the analytical framework (e.g., by incorporating certain properties and challenges of realistic LLM usage that we might have abstracted away in this work), leveraging it to derive more novel and generalizable insights that can assist the best practice of real-world LLM applications.
Acknowledgments
The authors would like to thank the reviewers and Action Editor for their constructive feedback that helps improve this work. We also thank Yuchang Sun for helpful discussion, and the AgentScope team (especially Xuchen Pan, Dawei Gao and Weirui Kuang) for infrastructure support.
References
Megha Agarwal, Asfandyar Qureshi, Nikhil Sardana, Linden Li, Julian Quevedo, and Daya Khudia.
LLM Inference Performance Engineering: Best Practices.
11m-inferencee ort.reenneeeppp.toaaaaaaaaaaannn
2023.
Anthropic. Building effective agents.
building-effectivee affective-agents 2024.
Xingjian Bai and Christian Coester. Sorting with Predictions. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
17

---

Published in Transactions on Machine Learning Research (10/2025)
Maciej Besta, Nils Blach, Ales Kubíček, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of Thoughts: Solving Elaborate Problems with Large Language Models. In AAAI Conference on Artificial Intelligence, 2023.
Maciej Besta, Florim Memodi, Zhenyu Zhang, Robert Gerstenberger, Guangyuan Piao, Nils Blach, Piotr Nyczyk, Marcin Copik, Grzegorz Kwasniewski, Jurgen Muller, Lukas Gianinazzi, Ales Kubíček, Hubert Niewiadomski,, Aidan O' O'Mahony, Onur Mutlu, and Torsten Hoefler. Demystifying Chains, Trees, and Graphs of Thoughts. arXio, 2024.
Bradley Brown, Jordan Jurawsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling, arXiv, 2024.
Sebastion Bubeck, Varun Chandrasckaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang. Sparks of Artificial General Intelligence: Early experiments with GPT-4. arXiu, 2023.
Yapei Chang, Kyle Lo, Tanya Goyal, and Mohit Lyyer. BooookScore: A systematic exploration of book length summarization in the era of LLMs. In The Twelfth International Conference on Learning Representations, 2024.
Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, and Yisong Yue. Neurosymbolic Programming. Foundations and Trends in Programming Languages, 7(3):158-244 2021. ISSN 2325-1107. doi: 10.1561/2500000099
Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Malei Zaharia, and James Zou. Are more Ilm calls all you need? towards scaling laws of compound inference systems. arXiv, 2024.
Yanxi Chen, Xuchen Pan, Yaliang Li, Bolin Ding, and Jingren Zhou. Simple and provable scaling laws for the test-time compute of large language models. arXiu, 2025.
Thomas Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
Antonia Creswell, Murray Shanahan, and Irina Higgins. Sclection-Infernnce: Exploiting Large Language Models for Interpretable Logical Reasoning. In The Eleventh International Conference on Learning Representations, 2023.
Jeffrey Dean and Sanjay Ghemawat. MapReduce: simplified data processing on large clusters.
Communications of the ACM, 51:107-113, 2008.
DeepSeek-AT, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang, Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang. Kuai Yu, Lean Wang, Lecong Zhang, Liang Zhao, Litong Wang, Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang, Peng Zhang, Qiancheng Wang, Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, R. J. Chen, R. L. Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Yc, Shiyu Wang, Shuiping Yu, Shunfeng Zhou, Shuting Pan, S. S. Li, Shuang Zhou, Shaoqing Wu, Shengfeng Ye, Tao Yun, Tian Pei, Tianyu Sun, T. Wang, Wangding Zeng, Wanjia Zhao, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang, W. L. Xiao, Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X. Q Li, Xiangyue Jin, Xiaojin Shen, Xiaosha Chen, Xiaowen Sun, Xiaoxiang Wang, Xinnan Song, Xinyi
18

---

Published in Transactions on Machine Learning Research (10/2025)
Zhou, Xianzu Wang, Xinxia Shan, Y. K. Li, Y. Q. Wang, Y. X. Wei, Yang Zhang, Yanhong Xu, Yao Li, Yao Zhao, Yaoleng Sun, Yaohui Wang, Yi Yu, Yichao Zhang, Yifan Shi, Yiliang Xiong, Ying He, Yishi Piao, Yisong Wang, Yixuan Tan, Yiyang Ma, Yiyuan Liu, Yongqiang Guo, Yuan Ou, Yuduan Wang, Yue Gong, Yuheng Zou, Yujia Hc, Yunfan Xiong, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Y. Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng, Yuchen Zhu, Yunxian Ma, Ying Tang, Yukun Zha, Yuting Yan, Z. Z. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu Wu, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song, Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang. Deepscek-r1: Incentivizing reasoning capability in llss via reinforcement learning. arXiv, 2025.
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, and Samson Zhou, Learning-Augmentie Augmented k-means Clustering. In International Conference on Learning Representations, 2022.
Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards Rovealing the Mystery behind Chain of Thought: A Theoretical Perspective. In Thirly-seventh Conference on Newral Information Processing Systems, 2023.
Dawei Gao, Zitao Li, Xuchen Pan, Weirui Kuang, Zhijian Ma, Bingchen Qian, Fei Wei, Wenhao Zhang, Yuexiang Xie, Daoyuan Chen, Liuyi Yao, Hongyi Peng, Zeyu Zhang, Lin Zhu, Chen Cheng, Hongzhu Shi, Yaliang Li, Bolin Ding, and Jingren Zhou. Agentscope: A flexible yet robust multi-agent platform. or Xiv, 2024a.
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Meng Wang, and Haofen Wang. Retrieval- Auggeenned Generation for Large Language Models: A Survey, arXiv, 2024b.
Tanmay Gupta and Aniruddha Kembhavi. Visual Programming: Compositional visual reasoning without training. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognilion, volune 2023-June, pp. 14953 14962, 2023.
Michael Hahn and Mark Rofin. Why are Sensitive Functions Hard for Transformers? arXiv, 2024.
Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. Metagpt: Meta programming for multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations, 2024.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil Murthy, Position: Lims can't plan, but can help planning in 11m- Imdmooulo frameworks. In Forty-first International Conference on Machine Learning, 2024.
Greg Kamradt.
LLMIIest-WeelllhhAAaayytte
https://githhn http://tthub.coo.okkkaaaaaaa won//gaaaradtt//LMMee.....
Needle e InAAasstakk 2023.
Sayash Kapoor, Benedikt Stroebl, Zachary S. Sicgel, Nitya Nadgir, and Arvind Narayanan. Ai agents that maiter. arxiv, 2024.
Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Proceedings of the tweenyy-fist annual ACM-STAM symposium on Discrete Algorithmss, pp. 938-938--90 188-948.7. SIAM, 2010.
Mehran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, and Deepak Ramachandran. LAMBADA: Backward Chaining for Automated Reasoning in Natural Language. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 6547-6568, 2023.
Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan A, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. DSPy: Compiling declarative language model calls into state-of-tho-art pipelines. In The Twelfth International Conference on Learning Represenlations, 2024.
19

---

Published in Transactions on Machine Learning Research (10/2025)
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. In The Eleventh International Conference on Learning Representations, 2023.
Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Twasawa. Large Language Models are Zero-Shot Reasoners. In Advances in Neural Information Processing Systems, volume 35, pp. 22199 22213, 2022.
Wojeiech Kryscinski, Nazneen Rajani, Divyansh Agarwal, Caiming Xiong, and Dragomir Radev. BOOKSUM: A Collection of Datasets for Long-form Narrative Summarization. In Findings of the Association for Compulational Linguistics: EMNLP 2022, pp.
2022.
Yuri Kuratov, Aydar Bulatov, Petr Anokhin, Dmitry Sorokin, Artyom Sorokin, and Mikhail Burtsev. In Search of Needles in a 11M Haystack: Recurrent Memory Finds What LLMs Miss. arXiv, 2024.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient Memory Management for Large Language Model Serving with PagedAttention. In Proccedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
Philippe Laban, Alexander R. Fabbri, Caiming Xiong, and Chien-Sheng Wu. Summary of a Haystack: A Challenge to Long- Context LLMs and RAG Systems. arviv, 2024.
Soochan Lee and Gunhce Kim. Recursion of Thought: A Divide-and-
Approach to Multi-Context Reasoning with Language Models. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.),
Findings of the Association for Computational Linguistics: ACL 2023, pp. 623-658, 2023.
Bin Lei, Pei-Hung Lin, Chunhua Liao, and Caiwen Ding. Boosting Logical Reasoning in Large Language Models through a New Framework: The Graph of Thought. arxi 2023.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval- augmented generation for knowledge-intensive NLP tasks. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
Mo Li, Songyang Zhang, Yunxin Liu, and Kai Chen. NeedleBench: Can LLMs Do Retrioval and Reasoning in Million Context Window? arXiv, 2024a.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of Thought Empowers Transformers to Solve Inherently Serial Problems. In The Twelfth International Conference on Learning Representations, 2024b.
Alexander Lindermayr and Nicole Megow.
Algorithms with Predictions.
https://
algorithms whoortthmswith-aae pratdsiiiiiitssiiiiiiiiooo gi github. io 2022.
Nancy A Lynch. Distributed algorithms. Elsevier, 1996.
William Merrill and Ashish Sabharwal. The Parallelism Tradeoff:: Limitations of Log-Pricns Transformers.
Transactions of the Association for Computational Linguistics, 11:531 545, 2023.
William Merrill and Ashish Sabharwal. The Expressive Power of Transformers with Chain of Thought. In The Twelfth International Conference Learning Representations, 2024.
William Merrill, Jackson Petty, and Ashish Sabharwal. The Illusion of State in State-Space Models. arXiv, 2024.
Meta. Meta Llama
2024.
Grégoire Mialon, Roberto Dessi, Maria Lomeli, Christoforos Nalmpantis, Ramakanth Pasunuru, Roberta Railcanu, Baptiste Roziere, Timo Schick, Jane Dwivedi-Yu, Yu, Asli Colikyilmaz, Edouard Grave, Yann LeCun, and Thomas Scialom. Augmented language models; a survey. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
20

---

Published in Transactions on Machine Learning Research (10/2025)
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with Predictions. Commumications of the ACM, 65(7):33-30 35, 2022.
Amirkeivan Mohtashami and Martin Jaggi. Random-access infinite context length for transformers. Tn Advances in Neural Information Processing Systems, 2023.
ollama. ollama. http::///gtthubbccmmooooeeoee.e
2023.
OpenAl. GPT-4 Technical Report. arXiv, 2024.
OpenAL. OpenAl ol System Card.
2024a.
OpenAL. OpenAT Cookbook: Summarizing Long Documents. htttps:/cookkookk.o wwtp:/eopppaaccceeeaaaaeeeea wwwpp////////////////////
2024b.
Binghui Peng, Srini Narayanan, and Christos Papadimitrion. On Limitations of the Transformer Architecture. arviv, 2024.
Pouya Pezeshkpour, Eser Kandogan, Nikita Bhutani, Sajjadur Rahman, Tom Mitchell, and Estevam Hruschka. Reasoning capacity multi-agent systems: Limitations, challenges and human-centered solutions. arXiv, 2024.
Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently Scaling Transformer Inference. In Proceedings of Machine Learning and Systems, volume 5, pp. 606-624, 2023.
Archiki Prasad, Alexander Koller, Mareike Hartmann, Peter Clark, Ashish Sabharwal, Mohit Bansal, and Tushar Khot. ADaPT: As-needed decomposition and planming with language models. In Kevin Duh, Helena Gomez, and Steven Bethard (eds.), Findings of the Association for Computational Linguistics: NAACL 2024, pp. 4226 4252. Association for Computational Linguistics, 2024.
Chen Qian, Zihao Xic, Yifei Wang, Wci Liu, Yufan Dang, Zhuoyun Du, Weize Chen, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Scaling aarge-langugge-moil-bbassss multi-agent. collaboration. arXie, 2024.
Qwen-Team. Generalizing an LLM from 8k to 1M Context using Qwen-Agent, May 2024. URL https:
//quenmm.githu..io... http:///obblog/eeaaaae-e-------
Aymeric Roucher. LaungContess----AAAAMeelllddddas LongContext_ vs vs___vs____________ WeeeeeeenAHaaastcccciii 2023.
htte:://gstaabccco////yeerrrrrrr
Tim Roughgarden (ed.). Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2021.
Swarnadeep Saha, Omer Levy, Asli Celikyilmaz, Mohit Bansal, Jason Weston, and Xian Li. Branch-Solve- Merge Improves Large Language Model Evaluation and Generation. arXiv, 2023.
Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are Emergent Abilitics of Large Language Models a Mirage? In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Imanol Schlag, Sainbayar Sukhbaatar, Asli Celikyilmaz, Wen-tau Yih, Jason Weston, Jurgen Schmidhuber, and Xian Li. Large Language Model Programs. orXiv, 2023.
Philip Schroeder, Nathaniel Morgan, Hongyin Luo, and James Glass. THREAD: Thinking Deeper with Recursive Spawning. arXin, 2024.
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang, Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face. arXiv, 2023.
Freda Shi, Xinyun Chen, Kanishka Misra, Nathan Scales, David Dohan, Ed Chi, Nathanacl Schärli, and Denny Zhou. Large language models can be easily distracted by irrelevant context. In Proceedings of the 40th International Conference Machine Learning, 2023.
21

---

Published in Transactions on Machine Learning Research (10/2025)
Charlic Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv, 2024.
Theodore Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas Griffiths. Cognitive architectures for language agents. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Jonathan Thomm, Aleksandar Terzic, Giacomo Camposampiero, Michael Hersche, Bernhard Schölkopf, and Abbas Rahimi. Limits of Transformer Language Models on Learning to Compose Algorithms. arXiv, 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30, 2017.
Jesse Vig, Alexander Fabbri, Wojeiech Kryscinski, Chien-Sheng Wu, and Wenhao Liu. Exploring Neural Models for Query-Focused Summarization. In Findings of the Association for Computational Linguistics: NAACL 2022, pp. 1455 1468, 2022.
Junlin Wang, Siddhartha Jain, Dejiao Zhang, Baishakhi Ray, Varun Kumar, and Ben Athiwaratkun. Reasoning in token economies: Budget-aware evaluation of LLM reasoning strategies. In Proceedings of the 2024 Conference on Empirical Melhods in Natural Language Processing, 2024.
Xueshi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-Consistency Improves Chain of Thought Reasoning in Language Models. In The Eleventh International Conference on Learning Representations, 2023.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent Abilities of Large Language Models. Transactions on Machine Learning Research, 2022a. ISSN 2835-8856.
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Ed Huai hsin Chi, F. Xia, Quoc Le, and Denny Zhou. Chain of Thought Prompting Elicits Reasoning in Large Language Models. In Advances in Newral Information Processing Systems, 2022b.
Kaiyue Wen, Xingyu Dang, and Kaifeng Lyu. RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrieval. arXiv, 2024.
Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M. Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov. Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks. arXi 2015.
Jeff Wu, Long Ouyang, Daniel M. Ziegler, Nisan Stiemnon, Ryan Lowe, Jan Leike, and Paul Christiano. Recursively Summarizing Books with Human Feedback. arxiu, 2021.
Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, Ahmed Hassan Awadallah, Ryen W White, Doug Burger, and Chi Wang. Autogen: Enabling next-gen 11m applications via multi-agent conversation framework. arXiv, 2023.
Yangzhen WU, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. An empirical analysis of compute- optimal inference for problem-solving with language models. arXiv, 2024.
Yuyang Wu, Yifci Wang, Tianqi Du, Stefanic Jegelka, and Yisen Wang. When more is less: Understanding chain-of-thought length in 1lms. arXie, 2025.
Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, Rui Zheng, Xiaoran Fan, Xiao Wang, Limao Xiong, Yuhao Zhou, Weiran Wang, Changhao Jiang, Yicheng Zou, Xiangyang Liu, Zhangyue Yin, Shihan Dou, Rongxiang Weng, Wensen Cheng, Qi Zhang, Wenjuan Qin, Yongyan Zheng, Xipeng Qiu, Xuanjing Huang, and Tao Gui. The rise and potential of large language model based agents: A survey. arxi 2023.
22

---

Published in Transactions on Machine Learning Research (10/2025)
Guangzhi Xiong, Qiao Jin, Xiao Wang, Minjia Zhang, Zhiyong Lu, and Aidong Zhang. Improving Retrieval- Augmented Generation in Medicine with Tterative Follow-up Questions. arXin, 2024.
An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei, Huan Lin, Jialong Tang, Jialin Wang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Ma, Jianxin Yang, Jin Xu, Jingren Zhou, Jinze Bai, Jinzheng He, Junyang Lin, Kai Dang, Keming Lu, Keqin Chen, Kexin Yang, Mei Li, Mingleng Xue, Na Ni, Pei Zhang, Peng Wang, Ru Peng, Rui Men, Ruize Gao, Runji Lin, Shijie Wang, Shuai Bai, Sinan Tan, Tianhang Zhu, Tianhao Li, Tianyu Liu, Wenbin Ge, Xiaodong Deng, Xiaohuan Zhou, Xingzhang Ren, Xinyu Zhang, Xipin Wei, Xuancheng Ren, Xuejing Liu, Yang Fan, Yang Yao, Yichang Zhang, Yu Wan, Yunfei Chu, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, Zhifang Guo, and Zhihao Fan. Qwen2 Technical Report. arXiv, 2024.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpolQA: A Dataset for Diverse, Explainable Multi-hop Question Answering, In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2369- 2380, 2018.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of Thoughts: Deliberate Problem Solving with Large Language Models. In Thirly- seventh Conference on Neurol Information Processing Systems, 2023a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. ReAct: Synergizing Reasoning and Acting in Language Models. In The Eleventh International Conference on Learning Representations, 2023b.
Tian Ye, Zicheng Xu, Yuanzhi Li, and Zeyuan Allen-Zhu. Physics of Language Models: Part 2.1, Grade- School Math and the Hidden Reasoning Process. arx, 2024.
Zhihang Yuan, Yuzhang Shang, Yang Zhou, Zhen Dong, Zhe Zhou, Chenhao Xue, Bingzhe Wu, Zhikai Lí, Qingyi Gu, Yong Jae Loe, Yan Yan, Beidi Chen, Guangyu Sun, and Kurt Keutzer. L.M Inference Unveiled: Survey and Roofline Model Insights. arxi 2024.
Zhenrui Yue, Honglei Zhuang, Aijun Bai, Kai Hui, Rolf Jagerman, Hansi Zeng, Zhen Qin, Dong Wang, Xuanhui Wang, and Michael Bendersky. Inference scaling for long-conters context retrieval augmented generation. arXiv, 2024.
Matei Zaharia, Omar Khattab, Lingjiao Chen, Jared Quincy Davis, Heather Miller, Chris Potts, James Zou, Michael Carbin, Jonathan Frankle, Naveen Rao, and Ali Ghodsi. The shift from models to compound ai systems. https://bair: www.eeeyyeeeeu/bbloooooooooooo.. http:////w...aalooo////////////p
si-ststmss 2024.
Xinrong Zhang, Yingla Chen, Shengding Hu, Zihang Xu, Junhao Chen, Moo Khai Hao, Xu Han, Zhen Leng Thai, Shuo Wang, Zhiyuan Liu, and Maosong Sun. BeBchh Extending Long Context Evaluation Beyond 100K Tokens. arXiv, 2024a.
Yifan Zhang, Yang Yuan, and Andrew Chi-Chih Yao. Meta Prompting for Al Systems. arXiv, 2024b.
Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Josoph E. Gonzalez, Clark Barrett, and Ying Shong. Sglang: Efficient execution of structured language model programs. arXiv, 2024.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed H. Chi. Teast-to-Most Prompting Enables Complex Reasoning in Large Language Models. In The Eleventh International Conference on Learning Representations, 2023.
Zixuan Zhou, Xucfei Ning, Ke Hong, Tianyu Fu, Jiaming Xu, Shiyao Li, Yuming Lou, Luning Wang, Zhihang Yuan, Xiuhong Li, Shengen Yan, Guohao Dai, Xiao-Ping Zhang, Yuhan Dong, and Yu Wang. A Survey Effficient. Inference for Large Language Models. arXiv, 2024.
23

---

Published in Transactions on Machine Learning Research (10/2025)
Andrew Zhu, Liam Dugan, and Chris Callison-Burch. ReDel: A Toolkit for LLM-Powered Recursive Multi- Agent Systems. Xin, 2024.
Mingchen Zhuge, Wenyi Wang, Louis Kirsch, Francesco Faccio, Dmitrii Khizbullin, and Jürgen Schmidhuber. Gptswarm: Language agents optimizable graphs. In Forty-forst International Conference Machine Learning, 2024.
24

---

Published in Transactions on Machine Learning Research (10/2025)
A Supplementary materials for Section
This appendix complements Section 3 containing details of experiment settings, additional results for the concrete examples presented in Section and additional examples of parallel decomposition.
A.1
Experiment settings
We use the following LLMs, which cover a wide range of LLM characteristics and inference service:
Llama-3 1-88----mmm- 3-8B-Instruuct Instruct Meta 2024 supported by ollama follama 2023 and running on Macbook
Pro with M2 Pro chip and 16GB memory:
-amma-3-70-Insteeee
MMeta 2024 and (ren-2-22B-Instrvee Yang et al. 2024 supported by
vLLM Kwon al. 2023 and running on a server with 4 Nvidia A100-80G GPUs;
GPT-4-Turbo
OOpenAl 2024 accessed via API queries.
All of these LLMs are chat models. Each LLM call involved in our algorithms is prompted in chat format, according to the sub-task that it is responsible for. We use greedy decoding in all experiments.
Below are a few more details about our experiments. parallelism degree = 4 and = oc. Latencies in the presence of parallelism are simulated according to Eq. 33- (2) In all experiments, the number of tokens for a piece of text is estimated using the same tokenizer, namely the c1100k_ base encoding of the tiktoken package This simplification has no effect on the major conclusions from our experiment results. (3) Our experiment results inchude curves of some error metric (in blue) cost metric (in red) versus the problem size or sub-task size For each curve, plot the mcan and standard deviation of mcasured metrics from multiple independent trials, i.c., multiple randomly generated task instances.
(1) For ideal parallclism of LLM calls, we consider
A.2
Example: counting
A.2.1
Algorithm details
For each LLM call within the counting algorithun presented in Table [ we prompt the LLM to generate its answer directly without intermediate reasoning step Thus it reasonable assume, given the LLM's capability of instruction following, that the text generated by each LLM call has length Ldec O(1) and can be parsed into count number.
A.2.2 Cost analysis
Our analysis of cost metrics follows Section 3.1 More specifically, we have Ldec O(1) by assumption, and C (aggrrogation) since the final step of the algorithm is done by non-LLM node.
Considering the total prefilling length and decoding length cost metrics, one has
C(prefilling) S k x (Lays + m)
7 x (Lays + m) = n x m
Lays
+ 1),
m
C(decoding) S k x x k n m
both of which are monotonely decreasing in
More generally, the sum of costs of all LLM calls is
C(sub-tasks) < k
(Crre + m) Cdec Coeys + m, 1)
httpp://githhb. http///twwc..i.aaeooooooooooooaa htt.:////.....ooo/mmm///aaa///a/ www_toot_ttotttteeeeeooto coantt_tokes___e wiith tiktoken. titeteettttttttkoennnnnonmon ipynb On other band, stppby-step counting can yleld more accurate answer, but signihcantly higher cost, with Lase (m)) rather than O(1).
25

---

Published in Transactions on Machine Learning Research (10/2025)
(Cyy + m) + Cdec CLyys + -m,
n
m
The optimal choice of under various conditions has been discussed in Section 3.1
For the end-to-end latency with parallelism degree p, we have
k- x SpreeCosy + m) Cayys + m, mn,1)
C(sub-tasks)
p
Cpre (Rays m) Edee(Logy + m. 1))
p m
Under the assumptions explained in Section 3.1
the minimum is achieved around k p and m n/p.
A.2.3 Experiments
We validate our analysis with numerical experiments. For each problem instance, the input string is generated by randomly sampling n characters from the union of digits, lower-case letters and upper-case letters.
Results with Leama----B-Insee
The results are illustrated in Figure 9
In Figure Da we vary the problem size n and set m in our algorithm, in which case the algorithm becomes equivalent to single LLM call. Unsurprising, error metrics in this counting task monolonely increase with The number of prefilling tokens increases linearly with n, while the number of decoding tokens is insensitive to n, since we prompt the LLM to output its answer directly without intermediate reasoning steps. The latency of one LLM call also increases linearly with n, which is likely due to the relatively small sequence lengths and the compute-bound nature of LLM inference by a Llama-3-882 -eaee-------n-ttttee Instruct model running on a CPU.
In Figure 9b we fix 200 and vary the hyperparameter m, i.e., the size of each sub-task. It is confirmed that decomposing the original task into smaller parallel sub-tasks improves the accuracy of the overall algorithm, while incuring higher cost metrics, except for the latency with infinite parallelism (which is monotonely increasing in m) and the latency with parallelism degree p p=d 4 (which achieves the minimum at m m=n/p = 50, as was predicted by our previous analysis).
Results with EPT-4-Turbo Figure 10 demonstrates the empirical results for the same experiments but with GPT-4-Turbo. We observe from Figure 10a that the latency one LLM call insensitive to the input problem size n, which likely because LLM inference of GPT-4-Turbo memory-bound for the range of sequence lengths considered in our experiments. One potential implication is that the end-to-end latency with infinite parallelism p = might slightly increase for smaller and hence larger k due to the random variation of latencies in reality; this is indeed what observe from Figure 10b. Other than that, the results in Figure 10 are similar to those in Figure g
26

---

Published in Transactions on Machine Learning Research (10/2025)
200
Nor mormaaaed qounthgg crno
175
10.4
Courchig
10.2
Litencyy Doed
0.8
hrefiing
125
20.0
0.7
0.6
50
100
150
200
50
100
150
200
120
150
200
100
200
100
150
200
Tank k5m0
Tast 120
Tasc
Taks 62e
Tancc
(a) Vary 71 and sut (10 trials)
1000
200
courting 67TC2
800
80
LL3
600
nocoding
200-
borma coanking 69724
0.30
30
0.25
0.5
0.15
Latercyy
0.10
0.05
2-
0.6
0.00
100
200
50
100
150
200
50
100
150
200
50
100
150
200
Sub-task $28
Sub-lask size
Sub-Jask S/28
Sulb laik si20 m
(b) Fix = 200 and vary m. (10 trials)
Figure 9: Empirical results for counting with Llama-3-a
27

---

Published in Transactions on Machine Learning Research (10/2025)
10
Normalooss oounthig cro
10.4
Courcihg
140
10.2
Latency Caed
0.2
220
20.0
100
9.1
50
100
150
200
50
100
150
200
120
150
200
100
200
50
120
150
200
Tank kome
Tast 122
Tase
Taks 62e
Tase 8
(a) Vary 71 and sut (20 trials)
1000
20
Courting BECC
LL3
nocoding
300
400
20
200
20.0
Nerrekkeed countin W7C
100
17.3
80
0.3
Lasercy
60
10.0
40
20
5.0
0.0
2.5
50
100
150
200
53
100
150
200
50
100
150
200
100
200
Sub-task size
Sub-Jask S120
Sub-riok sice
Sub-task sice
(b) Fix = 200 and vary m. (10 trials)
Figure 10: Empirical results for counting with GPT-4-Turbo.
28

---

Published in Transactions on Machine Learning Research (10/2025)
A.3 Example: sorting
A.3.1 Algorithm details
We note two details about the sorting algorithm presented Table
To ensure efficiency and stability, for each LLM call, we prompt the LLM to generate the sorted list directly, without intermediate reasoning steps. It has been verified empirically that the LLMs considered in experiments follow such instructions, and generate text of length [dec(m) O(m) that can be easily parsed into a list.
Step of the algorithm relies on classical symbolic algorithm for merging two sorted lists, which maintains two moving pointers, one for each list, and chooses each entry of the merged list by comparing the values corresponding to the two pointers. Merging multiple sorted lists be done by merging one pair of lists at time, in an incremental or hierarchical manner. Python code for these procedures can be found in Listing at the end of this subsection. Although they are designed under the assumption that the input lists are sorted, they can also be applied to input lists that are not fully sorted, which can possibly happen within the LLM-bas based algorithm since the input lists in Step are gencrated by LLM calls in Step
A.3.2 Cost analysis
Cost analysis of for the LLM-based sorting algorithm follows Section 3.1 and is similar to that for counting. One major difference is that Ldec O(m) rather than O(1) for each sub-task.
Considering the total prefilling length and decoding length cost metrics, has
x (Lays m) Cays m
C(prefilling) k (Gays + m) m
+ 1),
C(decoding) S k m n.
The former is decreasing in m, while the latter is insensitive to m.
More generally, the sum of costs of all LLM calls
C = C(sub-tasks)
< k x (Crre + m) + CdeclEsys + m, mn)
n X Cpre(Cays + m) + Cdec Cays + m, m)
For the end-to-end latency with parallelism degree p, we have
= C(sub-tasks) <
x (Cpre (Cpre(aay Lays + m) + Cdoc (Lays + m, m))
n (Cpre(Lays + m) + Cdoc (Lays + m, mm,mm,)))) m))
m
A.3.3 Experiments
In our experiments, the input list of cach problem instance is generated by randomly sampling entries of the list from the uniform distribution over the interval [0, 1] and rounding each of them to two decimals.
Results with
The results are illustrated Figure II
In Figure Ia we vary the problem size n and set m in the LLM- based algorithm, in which case the algorithm becomes equivalent to single LLM call. We make the following observations:
Unsurprisingly, all error metrics in this task monotonely increase with
29

---

Published in Transactions on Machine Learning Research (10/2025)
While the LLM might output list that deviates from the foound-truth solution, it is at least good at ensuring that the output list itself is sorted or has a very small non-monotonicity error.
The prefilling length grows linearly with n, while the growth of the decoding length and end-to- end latency slows down slightly for large values of n, which is mainly because the LLM is prone to returning list that is shorter than the input list when n is large, reflected in the length-mismatch error curve.
In Figure 1ib we fix 200 and vary the sub-task size m. confirmed that decomposing the original task into smaller parallel sub-tasks implies lower error metrics achieved by the overall algorithm, while increasing certain cost metries. Two specific observations:
The total number of docoding tokens decreases with m at rate that matches the length-mismatch error curve. This does not contradict our previous analysis, which predicts upper bound that is insensitive to the value of m.
Regarding the end-to-end latency with parallelism degree p = 4, the zigzag part the curve might seems curious. In fact, fine-grained analysis can well explain this phenomenon. If we approximate the latency for one LLM call solving a sub-task of size m by O(m), then the end-to-end latency of the overall algorithm is approximately O(m x [k/p]). The numbers calculated in Table 3 for the concrete setting of this experiment match the empirical results and explain the zigzag part.
Results with GPT-4-Turbo. Figure 12
demonstrates the empirical results for the same experiments but with GPT-4-Turbo model. Similar observations can be made from these results, except that latencies exhibit higher variance due to the inference service of GPT-4-Turbo.
30

---

Published in Transactions on Machine Learning Research (10/2025)
Table 3: Fino-grained analysis for the latency with parallelism degree p = in Figure
11b
where n 200.
Sub-task size m
10
20
40
50
67
100
200
Number of sub-tasks & [n/m]
20
10
5
4
3
2
1
Sequential depth [k/p]
2
1
Predicted latency x d x
50
60
80
50
67
100
200
1.0
Turryl.
0.30
Fuzzy nornalized
0.30
Non Nen-monozoriicco arrer
0.002
Exacsmeth atto
0.25
0.25
0.20
0.20
0.001
0.15
0.15
8,000
0.10
0.10
0.0
0.05
0.00
Task
Tisk takkstze-n
Task
Tisk
1.00
25
1.02
600
200
11H cdt
1.00
Perting
600
600
315
0.98
10
0.96
200
100
200
100
200
100
150
200
50
100
150
200
ddw
Task
Tusk
(a) Vary n and set m = nt. (20 trials)
0.35
Fuzzyy
1.0
0.30
Fucay nor malizad It
0.04
0.25
Nom www.mmannnnniiioooooooooo
0.02
0.20
0.2
0.00
0.1
0.00
100
200
200
Sub 12.0k d22e
Sub-takk 5t0.akkkkeee.... m
Sub-aak size
Sub-ask dite
1.5
1500
600
L10 cats
3600
800
1100
300
150
200
100
200
100
200
Sut
sizu
Sub-task size
25-
Lacon 1000
32.5
1oe0
2.0
30.0
3.5
27.5
25.0
22.5
150
50
150
200
Sub task dize
Sub Kapk $220
Sub 225k siz2
(b) Fix 200 and vary (10 trials)
Figure 11: Empirical results for sorting with Bonaa-3-70B-Intttee
31

---

Published in Transactions on Machine Learning Research (10/2025)
0.04
0.020
Nan-monottriccky amor
0.52
0.035
Erter
9.03
0.100
0.01
0.00
0.065
0.00
Fuzzy
-0.
Fazzy norma leod
0.000
-3.01
1000
1.04
80
ILMC
1.02
800
R100
Lasanicy (444)
1.00
-00
0.58
20
200
300
100
200
50
130
200
Thsk sie
Task 5boe
Task
Thick site
Vary n and set TI. (10 trials)
Rucry
0.6
0.100
0.075
malized
8.050
8.075
0.02
0.54
3.025
0.2
8,000
Mon-
-0.025
3.04
-0.050
-2.050
200
Sabb-aadd
Sub-bank
Sup-tank
Sabooak
1020
1000
25:0
990
980
5-
1200
1100
260
100
150
200
100
200
100
200
Suo tack $220 m
Sub task dize
Sub tack size
140
Laboncy Ioed
120
60
50
200
60
40
30-
(b) Fix 200 and vary m. (10 trials)
Figure 12: Empirical results for sorting with GPT-4-Turbo.
32

---

Published in Transactions on Machine Learning Research (10/2025)
A.3.4 Proof of Proposition
Recall that yi denotes the solution returned by an LLM call, which is assumedd to be monotone, for sorting the i-th input sub-list. Let y? denote the ground-truth solution for sorting the i-th input sub-list. Assuming that lly; of oloo S e for all [k], our goal to prove that lyy 1ty-99 y S..
To start with, it is easy to check that merging multiple sorted lists is equivalent to sorting the concatenation of the lists. Therefore, we have
................................ ykl) sort (prt(perute(( yvl)),
y" sort(ly' vel) sort(permute( (vi, .v.....:.. 9ū)))
where permute can be any permutation of n elements in list. In particular, we let permute be the permutation that sorts 1y ........ VEl, which implies
y" sort(permute((y1) ..l.) permute -r1)-
Also notice that
|permute((g).....
y&l) permute( .f...... oilil y1. ....... ..kl ........ ykl max y: y S c. iE[M
Based on the above analysis, initial goal boils down to the following problem: given two lists 2, 2, E R. such that = x* lo and x" is sorted, need to show that [|sort(z) x ==1oo S Here, corresponds to permute(.y)..... ,k]), and x* corresponds to y².
To prove this, let us consider the classical in-place insertion-sort algorithm illustrated in Algorithm | We choose to prove by induction that, throughout the exccution this algorithm, it always holds that || 2ox S e, which immediately implies [|sor(=z) - z" ol S e. To prove this, notice that the only place Algorithm[[ where changed is the step of swapping 2y and 2 when the condition 2j 2 is satisfied. Under this condition, have the following:
2j 1 2)
> Ej -2 6,
2j-1 2)
Zzz11 - 2)-1 S 6,
2j =
< 2j-1 - = S e,
Zj zj-1 2 Fj =zj 2 -t,
which implies [zj-1 27] S and 12 2 1| < e. This means that the loo error bound is preserved after this swapping step, which concludes our proof.
A Algorithm 1: The classical insertion-sort algorithm
Input: a list I.th to be sortod.
for i 2,3,.... : do
for j = i ,, do
if 2j 2j-1 then
5
Break.
Swap Zj and 1-
Output: the sorted list z.
33

---

Published in Transactions on Machine Learning Research (10/2025)
import numpy up
def herge_two_ast sortttt__artte (listi, list2):
"." Merge non-empty lists up. arrays that assumed to be (at least approximately) sorted"*"
lemi, len2 = len len (listi), len (1ist)) idxi, idx2 0,
idx
11
solution np. zeros (len1 len2)
while idx len1 + len2:
18
if idxi len1:
val - list2
15
idx2 += 1
elif idx2 1en2:
17
val = listi [idxi]
18
idx1
else:
20
vali, val2 listi [idxi], list2 [idx2]
21
if val1 <= val2:
22
val val1
idr1 +=
24
else:
val val2
28
idx2 +=
27
solution [idx] val
28
idx += 1
28
30
return solution
31
33
sarge_sorted.. lists cests_increennaall (lists):
"""Merge lists [listi, list2, ...] in an incremental manner
35
for in range (len (lists) 1):
37
list1 lists p)p()
list2 lists p)p
39
solution
seree_tto__orteee (list1, 1ist2)
40
lista append (solution)
41
42
return lists [0]
43
44
45
def merge sange_sorted__ie ciststtherarcciccalCe (lists):
48
"n"Merge lists [listi, list2, ...] a hierarchical manner R1
48
while len (lists) >
niters len (lists) // 2
50
for in range (niters):
list1 lists pop (0)
52
list2 = lists. poppppppp00 (0) solution
53
(listi, list2)
54
lists append (solution)
55
56
return lists [0]
Listing Python code for merging sorted lists. We choose the hierarchical option our experiments.
34

---

Published in Transactions on Machine Learning Research (10/2025)
A.4
Example: retrieval
Our investigation of the retrieval task draws inspiration from the sondll-in-a-haystadd benchmark (Kmmrddt
2023) and other similar benchmarks that have been widely adopted for evaluating the long-context capability of LLMs as well as techniques of retrieval-augmennee generation (Weston et al. 2015 Roucher 2023 Kuratov
et al. 2024 Mohtashami & Jaggi 2023 Zhang et al. 2024a).. For concreteness, consider the following setting, A key message (the needle) of the form "The passcode to the {targeted object, e.g., red door) is {6-digit passcode)" randomly inserted into a piece of long text (the haystack). The algorithu asked to answer the question "What is the passcode the ftargeted object]??" To make the problem more challenging and fun, let. the haystack consist of alike sentences of the form "The passcode to the {colored object, e-g-- rod lock green door} is {6-digit passcode)"" with colored objects different from the targeted object. This allows us to investigale both sides of retrieval capabilities of LLMs and LLM-based algorithms: relrieving the targeted information correctly, while avoiding being confused or misled by background information that might seem relevant to the question (Shi et al. 2023). Note that while we use this concrete setting for our empirical study, the proposed algorithm and analysis in the following are actually applicable to generic cases of this retrieval task.
A.4.1 Algorithm details
We note a few details about the LLM-based retrieval algorithm presented in Table !
All lengths involved in the algorithm are measured by the number of characters.
In the first step of chunking, we let each pair of adjacent chunks share overlap that is larger than the length of the needle, to ensure that the needle will appears as a whole in at least one chunk.
For each LLM call in the second step, the LLM prompted to answer "I don't know" if it believes that there is not sufficient information in the corresponding chunk, e.g., when the chunk simply does not contain the needle. Such answers will be excluded from the final step of the algorithm.
In the final step, ie., majority voting, it is possible that there exist multiple (say h) candidate solutions with the same frequency, which case we let the algorithm return the list of such candidates. If this list contains the ground-truth solution, we calculate the exact-match error 1 - 1/h in our experiments.
A.4.2 Cost analysis
Let us assume for concreteness that each pair of adjacent chunks share an overlap of length m/2, and my = m for all i E [k: 1], 1], while m/2 < my S m. In this case, we have k = [2n/m- - -1]
Our cost analysis for this task largely the same as that for the counting task, despite how different these two tasks might seem. Under some mild conditions explained in Section 3.1 most cost metries of interest are monotonely docrcasing in m, except for the end-to-end latency with parallel LLM calls, which is increasing in m for parallelism degree p- do and possibly non-monolone for finite p. One thing to note is that, due to the overlaps between consecutive chunks, the number of parallel sub-tasks in Step 2 of the algorithm is k = 12n/m 11, rather than [n/m] as in the counting task. This implies that the value of m minimizing the latency can be predicted by letting 2n/m- - = p, namely m zs 2n/(p + 1).
A.4.3 Experiments
We validate our analysis with numerical experiments. For each task instance, the passcodes of all objects, the targeted object, the position of the haystack where the needle inserted, etc., are all randomly chosen. The error metric of interest, namely the exact-match error, takes value 0 the final solution of the algorithm is exactly the same as the ground-truth passcode to the targeted object, 1 1/h h if the algorithm returns a list. of h candidate solutions that includes the ground-truth passcode, and hewwise
35

---

Published in Transactions on Machine Learning Research (10/2025)
Results with -Lama-3-8B-Instzve The results are illustrated in Figure 13
In Figure 13a we vary the length n of the imput text containing one needle in haystack, and set m = n for the LLM-based algorithm, which becomes equivalent to a single LLM call. Notice that the exact-match error, which corresponds to the first failure mode explained earlier, approaches zero as the problem size n decreases. In addition, the decoding length O(1), and the wall-clock latency O + n); one detailed observation is that as increases, it becomes more likely that the LLM call returns "I don't 't know", which slightly decreases the number of decoding tokens and thus the latency.
Figure 136 includes the results for the same experiment setting, except that no needle is inserted into the haystack. One crucial observation is that the exact-match error in this case, which corresponds to the second failure mode of retrieval, remains non-zero even for very small values of n. This suggests that Llama-3-8B- 1er-3--B-Instrucc should be regarded as Type-B LLM that is prone to both failure modes explained
in Section 3.2.3
In Figures 13c and 13d we vary the sub-lask size while is fixed at 10000 and 20000 respectively. As predicted by our analysis, the error of the overall algorithm is not monotone in the value of m, due to the presence of two failure modes. Another difference from the previous counting or sorting task is that the latency with parallelism degree 4 achieves the minimum around m 2n/ + 1) = 0.4n rather than m = n/p = 0.25n, which again matches our previous analysis.
Results with 3-70----0t-nsttrucc. Figure 14 includes the results for the same experiments but with Llana-3-700-Instruct used within the LLM-based algorithm. In particular, Figure 14a shows that this LLM achieves lower errors in the first failure mode of retrieval compared to LLama-3-8B- Instrrccntt,, while Figure 14b suggests that it is much less prone to the second failure mode and hence might be regarded Type-A L.M.M Consequently, in Figures [4c and 14d the exact-match error exhibits more monotone relation with the sub-task size m. Regarding the cost metrics, results with 3lama-3-70B- Pr00B-Instuct are similar to those with Llama-3-88 -nInrrctt.
36

---

Published in Transactions on Machine Learning Research (10/2025)
Partiing tikens
Decoding tRAare
2000
6.5-
1500
6.0
0.-
1000
4000
Tank
(a) Vary n and set m 1t. (20 trials)
0.5
0.4
mog tdkeens
1000
Decoding tocane
7.5
3.0
3.5
800
2.5
2.0
1.5
200
4.
(b) Vary n and set m = n for the no-needle case. (20 trials)
1.0
8000
Preiking totarss
30
0000
4000
10
1.00
400
Lacunoo 244.00
35
Lozono 0O01
Liboncy 1200
30-
1.00
25
20
1.5
56
10-
5000
10000
2500
5000
7500 10000
2500
5000 7500 10000
Sub-taece
Sub-tase vow
Subbeekk stow
(c) Fix 72 10000 and vary
(10 trials)
14000
ovetenaci ance
70
Peeiiing tebeens
0.6
0.4
10000
300
8000
50
6000
10000
20000
10000
20000
10000
20000
5000
10000 15000 20003
Sub-iank Nizw
Sub-lasc 2
Sub-tenk sine
Sub-takk size mm
LaRoncy p-4 (X00
0-. (902)
-00
50
10a
3200
10020
15003
(d) Fix 20000 and vary (10 trials)
Figure Empirical results for retrieval with Llama- --aaa-----B----- Instruct.
37

---

Published in Transactions on Machine Learning Research (10/2025)
7.5
0.5
tikeess
pecceting tocees
V.D
0.4
2000
6.5
1000
-0.2
300
0.5
5000
7500
10000
Tank
Tank
(a) Vary n and set m nt. (20 trials)
0.50
tog 1dkerr
1000
Decoding tocams
200
4.2
0.50
-0.02
0.40
0.04
200
9.35
(b) Vary n and set m = n for the no-needle case. (20 trials)
Exeeh-mnce 6722
2.6
toterss
8000
150
30
100
0000
75
0.0
4000
10
0.2
1.0
Lacange owd Good
0.8
0.8
7.5
5.0
5000
10000
2500
5000
7505
10000
5000
10000
Sub-laek N/2
Sub-bask vine m
Sub-lekk sbme
(c) Fix 7 10000 and vary
(10 trials)
14000
3.0
Peeiiing tebeens
125
70
100
10000
8000
6000
10000
20000
10000
20000
10000
20300
5000
10000 15000 20005
Sub-wec 4ow
Sub-lasc 2
Sub-tekk sine
Sub-takk size m
15.0
LaRency p-4 (o0)
(302)
1..0
1.0
5.0
0.8
0.6
10000
12000
(d) Fix 20000 and vary (10 trials)
Figure 14: Empirical results for retrieval with Llama-3-270 Baamaa--77B-Inst-eee
38

---

Published in Transactions on Machine Learning Research (10/2025)
A.5 Example: retrieval-augmentee generation
Our next example is multiple-needle generalization of the previous retrieval task, which can be regarded syuthetic and simplified version of retrivaal-augmentt generation (RAG) (Lewis et al. 2020 Gao et al. 2024b). In particular, we consider fino-grained sentenco-level retricval by LLMs, rather than document-level or chunk-level retrieval by certain similarity measure of dense embedding vectors.
More concretely, suppose that the imput text is composed of sentences of the form "The {i}-th digit of the passcode to the {colored object)" is {digit}", where i [6]. The algorithm is asked answer the question "What is the 6-digit passcode to the (targeted object Compared with the previous single-needle retrieval task, here the algorithm need to retrieve multiple needles, each for one digit of the targeted object, in order to answer the question correctly; moreover, the final aggregation step requires certain capability of reasoning or summarization over the retrieved needles.
Note again that while we focus on this specific setting our experiments, the algorithm and analysis in the following can be extended to generic settings of this RAG task.
A.5.1 Algorithm
We consider the following LLMM-baed algorithm for solving this task:
1. Divide the imput text of length n into k overlapping chunks of lengths mi..... mi:
2. For each chunk, use one LLM call to retrieve sentences that can be useful for answering the question;
3. Put the retrieved sentences together, based on which one LLM call is invoked for answering the question.
We note a few details about this algorithm. (1) For each chunk in Step 2, we prompt the LLM to retrieve relevant sentences, or return "None" if no relevant sentence is found in that chunk. Such "None" results will be excluded from Step of the algorithm. (2) Unlike previous examples, the final aggregation step of this algorithm involves an LLM node, which adds to the cost metrics of the overall algorithm.
(3) For simplicity, we assume that the number of needles (i.c., length of the passcode) and the length of each needle are both O(1). For more general cases, the final aggregation step might benefit from further task decomposition. (4) We allow the algorithm to return partial answer, by placing a special character in the digit(s) of the passcode that it is uncertain about.
A.5.2 Analysis
Let us assume for concreteness that each pair of adjacent chunks share an overlap of length m/2, and m; = m for all i E [k: 1], while m/2 < my S m. In this case, we have h = [2n/m-
Error analysis. Our analysis of error metrics for this task is similar to that for the previous retrieval example. In particular, there are two possible failure modes in the retrieval step, and conclusions for the errors of the final solution returned by the overall algorithm are dependent LLM is being used. For example, if a Type-A LLM, which will not mistakenly retrieve irrelevant sentences from the input text, is used within the algorithm, then a smaller value of m implies higher accuracy of retrieval in Step 2 of the algorithm, which further leads to lower error metrics for the solution returned by the final aggregation step.
whether a Type-A or Type-B
Cost analysis. For simplicity, let us assume that Type-A LLM is used within the overall algorithm. Consequently, in Step 2 of the algorithm, each LLM call has Cpre & Lays + O(m) and Ldec O(1), since only the relevant text within the chunk is retrieved. Moreover, among the k LLM calls, only 0(1) of them return answers that are not "None". By excluding the "None" results from the final aggregation step, the last LLM call has Epre S Cays + (()) and Ldec = (1). ). Putting things together, with a degree of parallelism and the number of chunks k = [2n/ /mm - 11, the end-to-end latency C of the overall algorithm is bounded by
C- Csuub-tasks) Caggregation), where
39

---

Published in Transactions on Machine Learning Research (10/2025)
C(sub-tasks) _ k (Crr (Cys + +m) + Cdec (Cays + m, m,)
C(aggrogation) I Cpre (Cays 1) + Coyc + 1,1).
A.5.3 Experiments
We empirically validate the performance of the proposed LLM-based algorithm with a Llama-3-70B-Insrruct model. Two error metrics are considered: the exact-match error taking value [0, and the fraction of incorrect digits, which takes value in [0, 1] and is always no larger than the exact-match error.
In Figure 15a
we vary the problem size and set m in the LLM-based algorithm. It is observed that the error metrics are monotonely increasing in n, and approach zero as n decreases. Most cost metrics are also increasing in except for the number of decoding lokens, which is supposed to be determined by the number and lengths of the needles only, not the haystack, and thus should be insensitive to n.
In Figure 15b we fix n 20000 and vary the chunk size m. As was predicted by our analysis for Typo-A LLM, smaller value of m implies lower error metrics, indicating the efficacy of lask decompasition.
wrong diitt
6000
5000
4000
230
0.4
220
0.2
210
2000
200
-02
190
10000
20000
10000
20000
15000
20000
10000
20000
Task vow
Task sine
Tank sice
Task sine
Vary n and
n2. (20 trials)
20000
1400
wrng diglt
18000
16000
2000
202
660
400
10
10000
20000
10000
20000
10000
20000
5000
10000 15000 20000
Sub-taik 4lzw
Sub-last 22
Sub-best
Sub-iak size
60
30
50
Lacaho, 2-4 (o0
25
(000)
80
20
30
10000 15003 20000
3200 10020 15000
(b) Fix n 20000 and vary m. (10 trials)
Figure 15: Empirical results for RAG with Llama 3-70B- 770--Insturee
40

---

Published in Transactions on Machine Learning Research (10/2025)
A.6 Example: long-text summarization with chunking
For the final example of parallel decomposition, we apply our analytical framework to the task of long-text summarization [Kryscinski et al. 2022 Chang et al. 2024), where generating summary for the long input text with single LLM call is infeasible. Algorithms that process the long text to be sunmarized by chunks have been proposed, such as hierarchical merging (Wu et al. 2021 and incremental updating (OpenA] 2024b). The former first generates one summary for each chunk independently and then merge these intermodiate summarics into the final onc, while the latter maintains and updates a global summary as the chunks get processed one by one in order. Since objective and quantitative evaluation for the sunmarization task is known to be challenging (Chang et al., 2024) and remains an active research area, focus our study the cost metrics of both algorithms. Our analysis leads to interesting observations that are different from those in previous examples, primarily due to the various options of setting the number of generated tokens Dde for each LLM call within the algorithms.
A.6.1 Processing chunks in parallel
Algorithm. Let us consider the following algorithm that processes chunks in parallel, which a simplification of hierarchical merging (Chang al.) 2024) and visualized in Figure 3a.
1. Divide the input text of length n into k chunks of length mi, m2, ..... m,g
2. Summarize each chunk with one LLM call, independently and in parallel. For the i-th chunk, the LLM is prompted to generate a summary of length no larger than 8;.
3. Invoke one LLM call to merge the summaries into a single summary of length no larger than s.
Note that the targeted lengths of the intermediate and final summaries, denoted by {siheek and s, are hyperparameters of the algorithm that need be pre-specified, in addition to the number of chunks k and the chunk sizes (ma))
Analysis. For notational convenience, we assume that the chunk sizes satisfy m, m = n/k k for all i [k].
First, consider each individual LLM call: the cost of summarizing the i-th chunk can be bounded by (Lyy + m,),,, while the cost of the final merging step can be bounded by CLLM( + Σiew) 8 s). To further simplify notations, we assume that s; s1 for all i [k], which will soon be justified. Then the total cost C of the overall algorithm can be bounded by
C S C(summarize chunks) + C(merge summaries)
k CLLM(Gays + m, s1) + CLLM + 81,8),
while the end-to-end latency with parallelism degree can be bounded by
<
x CLu + m, 81) + CLys( + x 81,8).
Let us specify the hyperparameters 81 and more generally {st), assuming that the targeted length s of the final summary has been determined. If the targeted information that we wish to be included in the final summary is distributed evenly across the input text, e.g., in a story with linear narrative, then is reasonable to set 8; 81 s/k for all i [k]. In other scenarios where the targeled information is distributed unevenly (e.g., in focused summarization (Laban et al.) 2024 Vig et al. 2022)), it is generally safer to set 8; $1 = for all E [b:] The latency with parallelism degree p in both cases is summarized as follows:
[k/p] x Coys + m. s/k) + CLLM( + 8,8)
if 81 = s/k.
c<
xxs,s)) [k/p] x (Lys + m. 8) + CLLM + k x s,
if 5 = 8.
41

---

Published in Transactions on Machine Learning Research (10/2025)
Further analysis can be derived from here. To give example, let us focus the case of and try to find the chunk size that minimizes the latency with parallelism degree p. For simplicity, we ignore the length Sas of the system prompt and the limit in on the context window size. We also assume that the time complexity each LLM call is linear, namely (L Ldec) S Spre + Ldec. Then we have
k x (Lsss + m, 6) + (LLs + k kx C s [
Even in such oversimplified case, finding the optimal chunk size is non-trivial:
For large m 2 = n/p such that n/m < ps we have [k/p] = 1, and hence
n x 8
c k x
+
The right-hand side attains the minimum at m vn x
For small m < m = n/p, we have the approximation [k/p] Rs k/p, and hence
C
x
+
m +
(
( +
p
24
n
x
m P
+ = n
x
+
8
The right-hand hand side monotonely decreasing in m.
Given the above, it can be verified that the optimal chunk size m² that minimizes the latency C can be estimated by m² x mm, m] = max(vn x n/p).
A.6.2 Processing chunks sequentially
Algorithm. Let us consider the following algorithm that processes chunks sequentially, which is simplification of incremental updating (Chang et al. 2024h and visualized in Figure 3b
Divide the input text of length n into chunks of length m1, m2 m.
2. Initialize the global summary as an empty string, and update it incrementally via processing the chunks in order: at the i-th iteration, invoke one LLM call to utilize the global summary and the i-th chunk for generating a new global summary of length no larger than 8t.
3. The output of the overall algorithm is that of the final LLM call for summarizing the last chunk.
Analysis. While this algorithm clearly has sequential nature, our previous analysis for parallel decompasition can be easily adapted for this case. For the i-th step of updating the global summary, have Cpre Lays + s;-1 and Laee S si, and thus its cost is bounded by
C, s CLys + 8t)
Therefore, the total cost of the overall algorithm satisfies
C
C,
Σ
CLys - m 31-1,8;).
(E[A]
SE(M]
Further analysis can provide insights for choosing the hyperparameters that minimize the total cost, though we omit the details here to avoid repetition.
42

---

Published in Transactions on Machine Learning Research (10/2025)
B Proof of Proposition 2
We prove the proposition by induction. First, consider the base case where is Ieaf node of the DAG that has no input. Then it can be checked that Eq. ( holds true:
E(y(v)) S E
Σ E
glpathl x Ew-.
WEV pathEP(w->o)
The inequality follows the assumption, while the equality holds true because P(w + v) for a leaf node e is empty set unless v, in which case P(w v) contains only hypothetical path of length 0.
Next, consider non-leaf node v, whose predecessor nodes are denoted by u1, u2...., uu. Suppose that Eq. 66 holds true for each u, namely
E(v(u:)) & Σ E
Slpathl x Ewr: i i [k].
WEV patheP(w-tu)
To prove that Eq.
6 also holds true for node v, we start with the following:
E(y(o)) S & +SX x Σ E(y(u:))
SE(R]
& + x Σ
Σ
Σ
Sipathl x Ew
AE[R]
WE
pathe P -t)))
& + Σ
Σ
Slpathi Ew
wEVi pathe ((w-tu))
33 +Sx x Σ
Σ
E
slpathl x Ew
WEV (Elk) patheP(w-tu.
= Σ ΣEX
E
glpath|+1 x En.
(EV iE]k pathEP(w-au)
Here in the third line, replace the summation path from node to its predecessor node u, To move forward, notice that P(w + v) is union of & disjoint sets, where the i-th set contains paths ending with the directed edge from to v:
V with V (v), since there is certainly
P(w + +) U path + [w + v] path E P(w + u.)
iE(R]
With this, we can further simplify the previous upper bound:
E(v(v)) S E +
Σ
Σ
slpach|+1 x En
wEVV(v) (w) (E(M] PatheP(w-su)
= +
Σ
Σ
Slpath x En
we WEV) patheP(w-te)
Σ
Σ
gleathl E...
V P(w-))(ww-v))
This concludes our proof of the proposition.
43

---

Published in Transactions on Machine Learning Research (10/2025)
C Supplementary materials for Section 4.2
This appendix includes full details of our case study, presented in Section 4.2 on iterative retrieval and reasoning. For concreteness, we investigate challenging version of the RAG task studied in Section A.5 that requires multi-hop reasoning (Yang et al.) 2018 Li et al. 2024a]. Recall that in the previons RAG example, given a question and multiple text chunks, the algorithm (with the pattern of parallel decompasition) will first retricve useful sentences from cach chunk, and then invoke one LLM call to answer the question basod on the retrieved information. Such a method might not be feasible challenging scenarios where the needles embedded in the haystack are logically related, and some of the needles are related to the targeted question only indirectly via connection to other needles. For example, suppose that the question is "what is the numeric value of A", while the needles are "A B", "B C", and "C = 100", located separately in different chunks. Retrieving needles from their corresponding chunks solely based on the targeted question will certainly fail in this case.
To tackle this challenge, a natural idea is to extend the RAG algorithm considered in Section A.5 allowing it to perform multiple rounds of iterative retrieval and reasoning. For each round, the algorithm performs retrieval based on the targeted question as well additional information collected from previous rounds, followed by reasoning about the retrieved sentences and deciding whether the targeted question can be answered, further retrieval and reasoning is needed. Similar approaches have been widely adopted in prior work, e.g., in the -election-Inferenee framework (Creswell et al. 2023). in RAG system with iterative follow-up questions for applications in medicine (Xiong et al. 2024), as a technique of extending the effective context window of a LLM-powered agent system (Qwen- Team 2024), among others (Yue et al., 2024). The resulting algorithm for reasoning with iterative retrieval exhibits a hierarchical structure: the original task is docomposed into multiple soquential rounds, and each round further decomposed into multiple steps of retrieval and reasoning.
In the rest of this section, first elaborate the concrete setup and algorithms for this case study, and then demonstrate our analysis of accuracy and efficiency based on the proposed analytical framework, as well as insights derived from it. Finally, numerical experiments are conducted to validate the efficacy of the considered algorithm, as well as the derived analysis and insights.
C.1 Concrete setup
For concreteness, let us consider the task of finding the numeric value of a targeted variable embedded within a grid, similar to the setting considered in (Ye et al. 2024]. A visualization can be found in Figure [6] Configurations of the grid include its depth d, width w, and degree g. which control the difficulty of this task. More specifically, the grid consists of levels, each containing w variables; each variable at a certain level is function (e.g., addition, substraction, maximun minimum) of g variables at the next level, except for the variables at the final level, whose numeric values are given. Such information is provided in clues of the form "A2 = B1 + B3" or "C1 = 10", each of which corresponds to one variable. As a result, the total number of clues is d x w, and each clue has length Ogg). We refer to the clues that are necessary and sufficient for calculating the targeted variable as the needles, which constitute a directed acyelic graph (DAG) embedded within the grid. It assumed that the level of reasoning required in this case study is non- con-tiiiil yet also simple enough, in the sense that one single LLM call with step-by-step reasoning sufficient for answering the targeted question correctly if all needles are given priori.
C.2 Algorithm
To solve this task, consider LLM--based algorithm that involves multiple rounds of retrieval and reasoning, which is visualized in Figure 5 and explained in the following:
Divide the imput clues into l chunks. In addition, initialize an empty list of references, i.c., clues retrieved by LLM calls, which will be maintained and updated throughout the algorithm.
44

---

Published in Transactions on Machine Learning Research (10/2025)
1
3
4
Target variable: A2
Needles (sorted):
B
Depth
A2 = B1 + B3
B1 max(C2, C3)
B3 = C2 - C1
C1 10
c
C2 =
C3 20
Width
Figure 16: An example grid of variables with depth d = 3, width w = 4, and degree 2. The targeted variable is A2 at the top level, which is a function of B1 and B3 at the next level. The variables whose numeric values are necessary and sufficient for calculating A2 are highlighted in red, and their corresponding clues constilute DAG of needles.
2. For cach round of the algorithm, invoke h soquential (Figure 5al parallel (Figure 5b
LLM calls for retrieval from & chunks based on the targeted question and references, then invoke one LLM call to reason about the updated references and try to answer the targeted question.
If the LLM returns an answer, then the overall algorithm outputs that answer and terminate. If the LLM cannot answer, and no additional clue has been retrieved this round, then the algorithm terminates and f
Otherwise, move on to the next round of retrieval and reasoning, with the updated references.
Options for rcasoning and answering. We consider two options prompting the LLM to reason about the references and answer the targeted question: answering directly, thinking step by step before answering (Kojima et al. 2022). It is reasonable to expect that the latter will boost the accuracy while incurring higher costs, which will soon be investigated analytically and quantitatively in Section
Options for retrieval. We consider two options, referred to as "cyelic" and "parallel", for retrieval from multiple chunks during each round of the algorithm.
With the "cyelic" option (Figure 5a chunks are processed sequentially; more specifically, after retrieval for each chunk, the retrieved clues added to the list of references immediately, before retrieval for the next chunk starts. Consequently, the chunks are processed in a cyclic manner throughout the overall algorithm, which gives rise to the name of this option.
With the "parallel" option (Figure 5b chunks are processod independently and parallel, after which the list of references is updated once. This exemplifies using parallel decomposition (cf. Section 3 building block for more complicated L.M--based algorithms.
With the "cyclic" option, the overall algorithm typically need fewer rounds to answer the targeted question correctly, since each L.M call for retricval always leverages the most updated references. On the other hand, the "parallel" option can leverage parallelism of LLM calls for reducing the end-to-end latency of the overall algorithm. The comparison between these two options will soon be elaborated in Section
TThis is due the assumption that greedy decoding, which is deterministic, adopted. In this case, running round of retricval and reasoning will give the same result that the current round, which will be uscless and wastcful. A potential improvement adaptively decrease (e.g., halve) the chunk size and continue the algorithm with rounds; such improvements the focus of this work, and hence amitted here.
45

---

Published in Transactions on Machine Learning Research (10/2025)
C.3 Analysis
C.3.1
Error analysis
There exist two major failure modes for this algorithm:
Mistakes in reasoning and answering. For example, the LLM call responsible for reasoning and answering might mistakenly decide that it is not yet ready to answer the targeted question, or make mistakes when doing the arithmetic and thus return a wrong numeric value, even when all needles have been successfully retrieved. is also possible that the LLM call mistakenly returns a numeric value (e.g., the value of variable whose name is similar to that of the targeted variable), while the needles have not been fully retrieved yet. The probability of this failure mode is particularly related to whether the LLM call responsible for reasoning and answering is prompted to answer directly or think step by step before answering.
2. Failure to retrieve all needles. As long the ground-truth DAG of needles has limited size, the probability of this failure mode is largely determined by the choice of the chunk size. Since this has been thoroughly investigated in our previous retrieval (Section A.4 and RAG (Section A.5 examples, it will not be our focus in this section.
C.3.2 Cost analysis
Notations. Recall from Eq. (2) that CLLM(Cpre Cdec) = Cere(epre) + Cdec CCpee Edec) Edec) stands for the cost of one LLM call with prompt of length Cpre and generated text of length Ldec- We also adopt some notations from Section 3 in our previous study of parallel decomposition: n represents the total length (in tokens characters) of the input clues, represents upper bound for the chunk size, k S n/m denotes the number of chunks, and Lays denotes an upper bound for the length of the system prompt for each LLM call.
In addition, let Teyc (resp. rarr) denote the number of rounds determined adaptively by the "cyclic" (resp. "parallel"") algorithm itself at runtime. Finally, let l be the total length of the needles, ie., clues that are necessary and sufficient for answering the targeted question correctly. The value of & can depend the depth d, width w and degree g of the grid in various ways:
If g 1, then the needles form a chain of length d, in the form of "A B", "B CC, "C = D", and so on. In this case, we have é $ d.
If the width d=-1 1 is sufficiently large, then the number of needles can be upper bounded by the
size of tree with d levels and g children per node, namely 1 1+ g g² + + 1- (g 1)/(g 1).
Since each needle has length O(g), we have e (g - 1)/(9 1).
If the width w < d=- is limited, then a tighter bound for the number of needles will be d w, and thus & g d w.
The "cyclic" version (Figure 5a). Let us first study the cost of each LLM call.
An LLM call responsible for retrieval takes one chunk and the references as input, which has length Omm+f). In addition, it is supposed to output a list of clues, which has length O(f), that is relevant to the targeted question. In other words, we have Lpre I Lays + O(m + l), Ldec S e, and thus
C(retrieval) CLys + m mn+4 E,E)
An LLM call responsible for reasoning and answering takes the references of length O(f) as input, namely Cpre I Lays + O()). As for the length of generated text Ldec: is reasonable to assume that Ldec 1 if the LLM is prompted to answer directly, and Laee E if it is prompted to do the
46

---

Published in Transactions on Machine Learning Research (10/2025)
calculation step by step before returning its final answer C(reasoning) I CLLM + E, or t).
Consequently, has
Now we are ready to find out the cost of the overall algorithm with reye rounds of iterative retrieval (for k chunks) and reasoning:
C S Teye x C(one round)
(7)
Teyc
(k C(retrieval) + C(reasoning)
(8)
S reye (k CLys + + (, CLLM + f, or f)).
(9)
In particular, this bound quantifies how the cost of LLM calls responsible for reasoning and answering, namely Toyc CLys + +,1 or f), only occupies small fraction of the total cost of the overall algorithm.
The "parallel" version (Figure 5b Analysis of cost metries for the "parallel" version is largely the same as that for the "cyclic" version, with the following two major differences:
For the same task instance, the "parallel" version requires the same or larger number of rounds (Mpar 2 Teye), since in the "cyclic" version, each retrieval step always leverages the most updated references. For example, consider the case with degree g = 1 and a chain of d needles located separately different chunks. Then, the number of rounds will be Tarr = d for the "parallel" version, but can be as small as Teyc =1 for the "cyclic" version, the needles happen to appear the right order in the original clues.
If the cost metric of interest is the end-to-ent latency with parallelism degree p, then the k LLM calls for retrieval within each round can be parallelized, which implics
C S Parr X
x C(retrieval) + C(reasoning)
p
k
x CLLM(Lays + m + e, + CLLM( + 1,1 or 0))
S parr x
(10)
As result, the end-to-end latency of the "parallel" version with sufficiently large parallelism degree p can be potentially smaller than that of the "cyclic" version.
C.3.3 Insights
In sum, we derive two major insights from the above analysis:
LLM nodes responsible for reasoning and answering only occupy a small fraction of the costs of the overall algorithm, while playing critical role in the output of the algorithm and thus in the error metrics. Therefore, by step before answering (instead of answering directly), which will most likely boost the accuracy significantly with negligible loss in efficiency.
general recommendation is prompt these LLM calls to think step
2. Regarding the "cyclic" and "parallel" options for retrieval, we conclude that each of them has its own pros and cons. With the "cyclic" option, fewer rounds of retrieval and reasoning are needed (thanks to the timely updates to the references), but the downside is that all retrieval steps have to be exccuted sequentially. In contrast, with the "parallel" option, the algorithm typically requires more rounds retrieval and reasoning and thus larger costs in terms of most. metrics, but can leverage parallelism of LLM calls for reducing the end-to-end latency. Therefore, whether the "cyclic" "parallel" option is preferred largely depends on which cost metric is of more concern.
6There might exist more precisc characterizations of Ldee in this case, c.g., Laec S E X if the LLM tends take g stops calculating the sum g numbers. For simplicity, we mostly assume g = 0(1) in this study, and thus stick to the assumption that Ldne $
47

---

Published in Transactions on Machine Learning Research (10/2025)
C.4 Experiments
We validate our analysis via experiments with Qwen-2-728-Instrucc (Yang et al. 2024 supported by vLLM (Kwon et a (023) and running on server with 4 Nvidia A100-80G GPUs. For each experiment, we vary the depth, width or degrec of the grid of variables (which controls the difficulty of task instances), while validating the derived insights by comparing two options for prompting LLM calls that are responsible for reasoning and answering, or comparing the "cyclic" and "parallel" options for retrieval.
Error metrics of interest include (1) the exact-match error, which takes value 0 if the answer returned by the algorithm matches the ground-truth solution exactly, and value 1 otherwise; (2) the absolute error, i..., the absolute value of the difference between the algorithm's 's answer and the ground-truth solution; and (3) the missed-coverage error, i.e., the ratio of needles that the algorithm fails to retrieve and hence are not included in the references maintained by the algorithm. Note that missed coverage might arise not just from failures of the LLM calls responsible for retrieval, but also from the possibility that the algorithm terminates too early with fewer rounds than necessary, due hallucination by the LLM calls responsible for reasoning and answering. Cost metrics of interest are the same as those investigated in previous examples, plus the number of rounds, metric specific to this case study.
Remark (Mitigating hallucination in retrieval). During our early experiments, we observed that LLMs tend to make up clues not present the input during the retrieval steps. To address this, we prompt the LLM return exact copies of clues from the original text, and further use a symbolic program check whether the retrieved clues are indeed exact copies (which, from the perspective of LLM-powered agent systems, might be regarded tool use). Only those passing the test will be added to the list of references. It has been confirmed empirically that this simple method effectively mitigates the errors caused by hallucination of LLMs during retrieval, making the overall algorithm much more robust and accurate in our experiments.
Comparing two prompting options. For this experiment, we consider shallow and wide grids of variables, with depth = 2 and width w = 300. The degree varies, controlling the difficulty in arithmetic. The algorithm uses a fixed chunk size of 50 clues, and the "parallel" version of retrieval. In this case, the number of rounds should be 2 if each retrieval step succeeds.
Empirical results for this experiment are illustrated in Figure 17 which confirm our first insight, i.e., prompting the LLM to think step by step for reasoning and answering significantly boosts the accuracy of the overall algorithm while incurring minor overhead in cost metrics, compared to answering directly. Note from the last row, though, that the relative difference in terms end-to-end latencies increases with the parallelism degree p, which has been predicted by our analysis, particular Eq. (10).
Comparing the "cyclic" and "parallel" versions. In the following experiments, we consider grids with fixed degree g = 1 and thus chains of needles. We either fix the depth d = and vary the width w, or fix the width 100 and vary the depth d. The algorithm uses fixed chunk size of 100 clues, and prompts the LLM calls responsible for reasoning and answering to think step by step.
Empiriaal results for these two experiments can be found in Figures 18 and 19 which confirm that the considcred algorithm achioves high accuracy for a wide range of task configurations. The second insight from our analysis is also validated: compared with the "cyclic" version, the "parallel" version incurs a larger number of rounds and hence higher cost metrics, except for the end-to-end latencies with parallelism, for which the benefits of parallelism outweigh the downside of requiring more rounds.
48

---

Published in Transactions on Machine Learning Research (10/2025)
150
directly Calculate step
1.2
Answer directly
0.08
Answer directly
1.0
-
Calculate step by step
Calculate step by step
Missed cald--overrgge ratle
Absolute ereer
100
0.8
0.02
0.4
25
0.2
0.00
0-
-0.02
-25
0.2
Degret g
Degree g
Degree g
Answer directly
Calculate step by stop
Sumber
Degree g
100000
Answer directly
Answer directly
Answer directly Calculate
Calculate step
3500
Calculate
65
Prefiling tokens
Decocing takers
80000
2500
70000
2000
60000
1500
1000
40000
5
Degree
Degree
Degree
30
diractly Calculate step by step
Answer directly
Answer directly
140
-#
Calculate step by step
25
Calculate step by step
Latency (sec)
120
50
Latency, d= (sec)
20
Latency.
80
30
10
40
Degree
Degree g
Degree
Figure 17: Empirical results (10 trials) for reasoning with iterative retrieval, where two options of prompting the LLM calls responsible for reasoning and answering compared. The depth d = 2 and width 300 are fixed, while the degree g varies. The algorithm uses chunk size of 50 clues, and the "parallel" version of retrieval.
49

---

Published in Transactions on Machine Learning Research (10/2025)
Cyclc
Cydic Parallel
Cydic Farallel
Paralle!
Exact-match errer
Number of rounds
0.1
Miczed
0.0
2
-0.1
-0.2
2
3
Depth
Depth
Dopth
Cyclic
5000
Cyclic Parallel
Cyclic
120000
Parallel
Prefilingg tokens
Drcoding tokens
80
80000
3000
LLM calls
60000
2000
40
40000
1000
20000
3
Depth
Depth
Depth
Cyclc
140
Cyclic
140
Cydic
Paralle!
Paralle!
Parallel
175
Latency, pa (sec)
150
100
100
Latency (Sec)
125
80
80
100
Latency.
75
50
25
20
0
0-
Depth d
Depth d
Depth
Figure 18: Empirical results (10 trials) for reasoning with iterative retrieval, where two options of retrieval are compared. The degree and width w 100 are fixed, while the depth d varies. The algorithm uses chunk size of 100 clues, and prompis the LLM calls responsible for reasoning and answering to think step by step.
50

---

Published in Transactions on Machine Learning Research (10/2025)
Cydic Parallel
0.3
Cyclc Farallel
Cyclic
+ Parallel
Missed coverage ratl
Exact-match errer
0.2
Number of rounds
0.2
0.1
0.1
0.0
-0.1
-0.2
150 Width W
Width W
Width
Cyclic
6000
Cyclic
160
Cydic Parallel
175000
140
Prefiting tokens
Decoding takens
120
100
60
2000
50000
40
25000
1000
20
100
200
300
100
150
200
250
300
50
100
150
200
250
300
Width W
Width W
Wieth
Cyclic Paralle!
Cyclic
Cydic
250
Parallel
Parallel
Labency, pea (sec)
Latency (seq
150
125
Latency.
100
100
100
50
50
50
100
150
200
250
300
50
100
150
200
250
300
50
100
150
200
250
300
Width
Width
Width
Figure 19: Empirical results (10 trials) for reasoning with iterative retrieval, where two options of retricval, namely "cyclic" and "parallel", are compared. The degree g = 1 and depth 5 are fixed, while the width w varies. The algorithm a chunk size of 100 clues, and prompts the LLM calls responsible for reasoning and answering think step by step.
51

---

which is Published in Transactions on Machine Learning Research (10/2025)
D
Supplementary materials for Section 4.3
Recursive LLM-based algorithms have been widely applied in prior works, e.g., in LAMBADA (aazemi et al.
2023), LLM programs (Schlag et al. 2023), ADaPT (Prasad et al. 2024). THREAD [Schroeder et al. 2024
Recursion of Thought (Lee & Kim 2023 Decomposed Prompting (Khot et al. 2023 ReDel (Zhu et al.
20240, among many others. This appendix includes full details for our case study, presented in Section 4.3
of recursive task decomposition. In the following, we first introduce the concrete task under consideration, and then design a recursive LLM-based algorithm for solving it, highlighting the dynamic construction of its computational graph runtime. We then provide analysis for its accuracy and efficiency using the proposed framework, which is further validated with numerical experiments.
D.1 Concrete setup
For concreteness, we consider the same task introduced in Section C.1 and visualized in Figure 16
about calculating targeted variable based clues about a grid of many variables.
One major difference here is that consider much larger depth d, width w and/or degree for the grid of variables, which implies a larger DAG of needles, i.e., clues relevant to the targeted question. Even if all relevant clues are given a priori, the complex reasoning required to answer the targeted question correctly can be well beyond the capability of one single LLM call, which motivates docomposing the reasoning process into multiple LLM calls.
The other major difference is, we assume that the clues are not directly given in plain text, but rather need to be accossed via querying database (or more generally, source of information). For each query, the database takes name as input, and returns a clue for the variable of the same name, e.g., "A2 = B1 + B3" for input "A2" or "C1 = 10" for input "C1". The LLM-based algorithm need to decide by itself what to query from the database. Such a setting is motivated by, and can be regarded as an abstraction of, practical scenarios where an autonomous agent in the wild need to actively retrieve relevant information by itself in order to accomplish task (unlike in typical problem-solving benchmarks where such information given), via querying a real database or knowledge graph, using a search engine, retrieving from documents, etc. In this case study, we assume that querying the database does not involve LLM calls, and neglect its costs in our analysis for simplicity.
D.2 Algorithm
We consider the following recursive L.LM-based algorithm for solving this task. The overall algorithm maintains & dictionary of variables that have been calculated throughout its execution, and eventually outputs the value returned by applying a function named ProcessNode to the targeted variable.
The function ProcessNode,, which takes the name of a variable as input and returns its numeric value, is defined in a recursive manner:
1. If the input variable is found in the dictionary of calculated variables, then return its value directly.
2. Otherwise, query the database with the input variable, and invoke one LLM call with the returned clue, which is prompted to either answer with a numeric value or conduct further task decomposition, i.., identifying variables whose values will be necessary and sufficient for calculating the input variable.
(a) Tf the LLM chooses to answer with a numeric value, then return it. (b) Otherwise, invoke ProcessNode once for each variable identified by the LLM call, collect the answers returned by these children tasks, and finally invoke one LLM call to calculate and return the numeric value of the input variable.
We make few comments about this recursive algorithm. (1) The computational graph of this algorithm, or generic L.I.-bbseed algorithm following the pattern of recursive decomposition, is constructed dynamically
52

---

Published in Transactions on Machine Learning Research (10/2025)
in seats style at runtime. See Figure 7 for visualization. The final graph is symmetric about the nodes corresponding to the leaf variables (D, E); on the left are LLM calls for identifying children variables for the non-leaf variables (A, B, C), while on the right are LLM calls for calculating their numeric values. (2) The process of complex reasoning is docomposed recursively, so that each LLM call within this algorithm only need to handle a small step of reasoning, whose complexity is irrelevant to that of the overall task. (3) One particular configuration of this algorithm, like in the previous case study, is about how the LLM calls (especially the ones responsible for calculation) are prompted, e.g., to answer directly or think step by step. The impact of this design choice on the accuracy and efficiency of the overall algorithm will be investigated analytically and empirically soon in this section.
D.3 Error analysis
Recall from Eq. 1 that for a specific node with inputs Fi,...,5k; the error of its output y is assumed to be upper bounded by E(v) S [=((((1), (r,)),,)))......((()) for some function S For the concrete setting of the current case study, there are two major failure modes for the aforementioned algorithm: errors in recursive task decomposition, and errors in calculating the numeric values of specific variables. Empirical results during our early exploration suggested that LLMs make very few mistakes of the first kind, while the second failure mode much more common, due to the limited arithmetic capabilities of the LLMs under consideration. Moreover, all mathematical operations considered in this concrete settings (including addition, substraction, maximum and minimum) are 1-Lipschitz continuous with respect lo each input variable. Hence Proposition 2 which provides error bounds under the assumption of additive errors and bounded sensitivity, can be adopted for this case study, although we omit the details here for brevity.
D.4 Cost analysis
Let us first consider the cost of each LLM call. For each leaf variable, one LLM call is needed for finding its numeric value based on its corresponding clue of length O(1), which implies Lpr S Lays + O(1) and Ldec 5 O(),, and thus C(leaf) I CLLs( + 1)). For each non-leaf variable, two LLM calls are needed. One of them is responsible for task decomposition, i.e., identifying its children variables, which implies Cyre S Cays + Og)) and Ldsc S Ogg), and thus C(decomposition) S CLUM(Csys + g9 g). The other LLM call is responsible for calculating the numeric value of the current variable basod on the values of its children variables, which has Lpr S Lays + O(g), and Ldec S O(1) if the LLM is prompted to answer directly, or Ldec S [eale((g for some function Leate if it is prompted to do the calculation step by step (e.g.. Leale(g) S Ogg) O(g²), depending on how the LLM executes the calculation with 9 variables). In sum, we have C(calculation) I CLys( + g. 1 or (e)) for each LLM call responsible for calculation.
The analysis above has also revealed the total number of LLM calls. Let n and Meat be the number of relevant variables and the number of relevant leaf variables, respectively. These parameters are determined by d, w, g and other factors, as is the case for the l parameter (total length of relevant clues) in Section C Recall from above that each leaf variable requires one I.I.M call for finding its value from its corresponding clue, while each non-leaf variable requires two LLM calls, one for task decomposition and one for calculation. Assuming that task decomposition is done correctly by the LLM for each non-leaf variable, the total nunber of LLM calls will be 2 x (n- Telaa) + Meat = 2 x n Tleaa-
Putting things together, we finally arrive at the total cost of the overall recursive algorithm:
C (n ( (CLLM (Cays + 9.9) + CLLM + 1 or Lcate()))) neaa X CLLM 1).
(11)
In particular, prompting the LLM to do the calculation step by step, which is anticipated to significantly improve the accuracy of the overall algorithm, will increase most cost metrics (though not for the number of LLM calls or the total number of prefilling tokens) by multiplicative factor, in contrast to the previous case study in Section C where step-by-step prompting incurs minor additive cost overhead.
53

---

Published in Transactions on Machine Learning Research (10/2025)
D.5 Experiments
We validate our analysis via experiments with Sien-2-72B-Instruce (Yang et al., 2024 For each experiment, we vary the task complexity while comparing two options of prompting the LLM calls responsible for calculation, namely "answer directly" and "calculate step by step". Empirical results are shown in Figures 20 and 21 For the former, we fix the width w = and degree = 4, while varying the depth d: for the latter, we fix d 3 and w = 100, while varying g- The results confirm our previous analysis: compared to "answer directly"; prompting the LLM calls to "calculate step by step" significantly boosts the accuracy of the overall algorithm and leads to satisfactory performance for wide range of task configurations, while incurring higher costs in the latency and total number of decoding tokens by a multiplicative factor, and making no difference in the number of LLM calls or total number of prefilling tokens.
3.2
500
400
Aboduie smo:
300
0.52
0.8
200
8.00
0.2
200
5.0
Arswer diedly
-0.00
Caloabii sipp by sap
Depth
Depti
Depti of
00-
Cartu obe step stop
Asseer disccly
Arcierr dirdtle
culltee stop by step
8030
Calculate slop stop
Arpwert ciuccty
502
-a- Calculate siza
Arseer direcly
deal number LLM cs
252
LUN calss
8000
Docoding tovers
202
6032
150
4000
2020
20
Depth
Destho
Figure 20: Empirical results (10 trials) for reasoning with recursive task decomposition, where two options of prompting are compared. The width = 6 and degree g 4 are fixed, while the depth d varies.
3.2 -6o Ancaer direcly Cu stop by
Ansncr dieccly
Ansner dructlly
Caku dite stop stoc
0.00
Caku use stop stips
2.8
Abastette errie
30
0.02
20
20
-0.0
3.0
-0.08
-3.2
10m
5
Degree
Degres
Degree
70
Anower sirecty stop stos
Annwnr sirecty
3030
Appaer directy
Arsuwe dieccty
Calcoali sics by stop
Colcolale s1pp stop
Calculai dits by Stop
00
UMM la
2530
102-
50
hodf lng sakers
2036
Seod
83
40
6000
Decolinggoo
1930
63
20
0000
2030
20
10
Oegreez
Dagres
Degres
Figure 21: Empirical results (10 trials) for reasoning with recursive task decomposition, where two options of prompting are compared. The depth d = 3 and width w = 100 are fixed, while the degree g varies.
54


Reviews:
[{"review_id": "QvOfseJeNz", "reviewer": "Reviewer_cp4X", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I appreciate that this work tackles an important problem i.e., most LLM system design currently relies on ad-hoc experimentation. The computational graph abstraction is elegant and the mathematical treatment is rigorous. The derived insights about optimal granularity and cost-accuracy tradeoffs feel actionable.\nHowever, my main concern is the complete lack of realistic validation. All experiments are on toy problems: counting digits, sorting numbers, needle-in-haystack tasks. I have no evidence this framework would provide useful insights for actual applications like software engineering agents or complex reasoning systems. The gap between \"optimal chunk size for counting digits\" and real-world LLM applications feels enormous.\nThe assumptions also worry me. The additive error model assumes errors propagate linearly, but in my experience, reasoning errors cascade unpredictably. The framework treats LLM behavior as stable functions, ignoring context-sensitivity and prompt-dependence that characterize real usage.\nFinally, it's unclear how practitioners would apply this. The framework requires characterizing LLM error functions and estimating parameters, but there's little guidance on doing this for novel tasks without ground truth.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an analytical framework for designing and analyzing LLM-based algorithms using computational graphs. The key idea is to model LLM algorithms as graphs where nodes are either LLM calls or non-LLM operations, then analyze how design choices (task decomposition granularity, prompting strategies) affect accuracy and efficiency.\nThe main contributions are: a formal computational graph representation, cost and error analysis methodology, five practical insights from case studies on parallel/hierarchical/recursive decomposition patterns, and empirical validation on synthetic tasks. The framework aims to replace trial-and-error approaches with principled analysis of accuracy-efficiency tradeoffs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I need evidence this works for realistic tasks. Add at least one case study on a real application, such as code generation, mathematical reasoning, document analysis, etc. Show me the framework provides actionable insights beyond synthetic examples.\nI also need validation of the additive error assumption. Provide empirical evidence it holds for complex reasoning, or discuss when it breaks down and what that means.\nAddress scalability concerns: how does this work when optimal decomposition isn't obvious? When you lack ground truth? When LLM behavior is prompt-sensitive?\nAdditional improvements: test on diverse model families, provide concrete implementation guidance, compare predictions with established benchmarks.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3Fu8ZbIVQP", "reviewer": "Reviewer_Bz3T", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. This paper addresses a fundamentally under-explored problem with a formal framework. Rather than purely empirical benchmarking or heuristic-driven system design, it presents an analytical approach for LLM-based algorithms.\n2. The proposed use of computational graphs to model LLM-based algorithms enables the natural integration of both symbolic and LLM-invoked subroutines within a unified representation. \n3. The paper's insights are validated through both theoretical analysis and empirical case study.\n\n**Weaknesses**\n\n1. The case studies focus on highly synthetic tasks that abstract away many of the complexities present in real-world agentic workflows. For example, the retrieval task (Section 3.2.3) simplifies multi-document question answering into chunked retrieval followed by majority voting. It remains unclear how well the proposed framework scales to dynamic agent environments or tool-augmented workflows commonly used in real-world LLM systems.\n2. The insights are either trivial or closely aligned with intuition. Some key findings—such as \"finer-grained task decomposition leads to better accuracy but higher costs\"—are expected and may not offer significant new understanding.\n3. The analysis builds upon several assumptions, including simplified quadratic or linear cost models for token generation and bounded error sensitivity (Assumption 1 in Section 4.1), without sufficient justification or supporting citations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a formal analytical framework for designing and analyzing algorithms that embed one or more large language model (LLM) calls as core subroutines, named  LLM-based algorithms. By modeling algorithms as computational graphs, this work quantifies task decomposition and captures key abstractions like LLM characteristics and inference costs. Through this framework, the authors derive theoretical relationships between decomposition granularity, algorithmic accuracy, and computational efficiency. Through detailed case studies, the paper provides generalizable insights across a range of design patterns, including parallel, hierarchical, and recursive decomposition, and addresses trade-offs involving chain-of-thought reasoning and iterative retrieval.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Key assumptions in the theoretical framework require stronger empirical grounding or citations to establish their relevance. For example:\n   - Section 3.1: The claim that the Transformer model with full attention suffers from quadratic complexity in long-sequence processing.\n   - Section 4.1: The use of simplified quadratic or linear cost models for token generation, and assumptions regarding bounded error sensitivity.\n2. Expand the case study, or at least, discuss how the framework could be extended to support more complex agentic workflows.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "f6CcVl2kKr", "reviewer": "Reviewer_rZ8M", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths \n* The paper chooses a salient topic for analysis: the usage of LLMs as subroutines for solving larger tasks. While the paper largely focuses on toy settings and problems, this helps the paper build a solid foundation for this type of analysis. \n* The paper provides empirical validation for many of its theoretical claims. \n\n## Weaknesses\n* The novelty of the approach is unclear. The analysis of parallel decompositions feels very similar to that of parallel computation algorithms such as MapReduce [1] or Byzantine fault tolerance — except the compute nodes (\"map\" stage) are LLMs and we've replaced some deterministic algorithm with arbitrary time/memory complexity with an LLM (i.e., something non-deterministic w/ some non-certain success probability). In Table 1, Step 2 is essentially \"map\" and Step 3 is essentially \"reduce.\" \n    * At the very least, the paper would be significantly strengthened by discussion of the proposed framework in the context the literature in distributed computing. Textbooks on distributed computing [2] could be a good starting point for further literature review to discuss (1) connections to previously-known results, and (2) how the LLM-based setting introduces novel challenges. \n    * I think there's a subtlety that \"not all tokens cost the same\" (e.g., prefill vs. decoding phases) but it's not clear to me how this changes the analysis. \n* The clarity of the examples could be improved — counting and sorting are straightforward tasks, and it would help to see worked examples of these tasks to build further intuition.\n* Section 4.2 feels out of place — it's not clear to me why comparing CoT to the default prompting strategy used is an instance where the proposed analytical framework is useful. \n* Minor point: The nomenclature of Type I/Type II LLMs in 3.2.3 is a little confusing given Type I/II errors in hypothesis testing (e.g., I see that Type II hallucinates false positives = rejecting the null incorrectly = Type I?) — maybe there's a descriptive name that could be used instead? \n\n[1] Karloff, Howard, Siddharth Suri, and Sergei Vassilvitskii. \"A model of computation for mapreduce.\" Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2010.\n[2] Lynch, Nancy A. Distributed algorithms. Elsevier, 1996.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a framework for analyzing \"LLM-based algorithms,\" an algorithm that leverages LLM calls as a subroutine to conduct computation. The work formalizes task decomposition via LLMs into computational DAGs, bounds on errors given LLM failures, and provides theoretical and empirical evidence in support of the framework.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* My main concern is whether the theoretical tools provided have added value given pre-deep learning era work on distributed computing; i.e., is there a reason why handing off subtasks to LLMs is not \"merely\" an instance of MapReduce where nodes could provide noisy answers? Why are analytical approaches in past analysis of parallel distributed algorithms (e.g., Byzantine agreement methods [1]) not applicable here? \n    * At a minimum, I'd like to see further discussion of such approaches in the related work.\n* Here's a couple of suggestions for how to improve the clarity of presentation:\n    * A worked-example on a simple task (e.g., counting) near Eq. (4), maybe as a motivating example.\n    * Comparison to standard time- and memory-complexity analysis of algorithms, showing how one would draw different conclusions. I get that the \"units\" of analysis are different in the proposed approach but showing this comparison would really emphasize the value added by the proposed approach. \n\n[1] Pease, Marshall, Robert Shostak, and Leslie Lamport. \"Reaching agreement in the presence of faults.\" Journal of the ACM (JACM) 27.2 (1980): 228-234.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)