On the Design and Analysis of LLM-Based Algorithms

Comments on writing

Thank you for the suggestions. We will incorporate them in the revision.

Asymptotic notation

The confusion seems to arise because we use the notation $n$ in Lines 279 - 284 where we explain the generic asymptotic notation, which coincides with the notation $n$ in our analysis for parallel decomposition. We will use a different variable name in Lines 279 - 284 in the revision to fix this issue. In our analysis for parallel decomposition, $n$ is not the only variable that can grow to infinity.

The paper is missing a discussion of limitations and related works.

As mentioned in Section 6, we defer the full discussion on related works to Appendix A, and discussion on limitations and future work to Appendix B, due to space limitations.

Reading 4 pages of "how to decompose an algorithm into a computation graph" sounds much too lengthy.

Since the proposed analytical framework described in Section 2 is the core component of this work, we think it might be useful to make the descriptions as precise and detailed as possible. While readers who are proficient in the topic of this work might find it a bit lengthy, other readers with different backgrounds might feel that the length is just fine. Also, the content in the first 4 pages is not merely about "how to decompose an algorithm into a computation graph" like you described in your (somewhat sarcastic) comment.

Thank you for your careful reading and extensive comments. We hope our response can address your concerns.

Takeaways from this work?

If there is a single takeaway from this work, it would be the proposed analytical framework described in Section 2. The primary goal of our work is to share this useful tool with anyone working on LLMs and LLM-based algorithms.

The case studies in Sections 3, 4, 5 (and in the appendix) mainly serves as examples of how to use the proposed framework for solving concrete problems. If we draw an analogy between the proposed framework and PyTorch, then the case studies in our work are like the quickstart examples in PyTorch's official tutorials (e.g., "how to analyze a parallel-decomposition algorithm for the counting task using the analytical framework" is just like "how to build and train a convolutional neural network using PyTorch"), which help the users get started with using the proposed tool to solve their own problems.

The case studies also serve the purpose of validating the usefulness of the proposed framework and showing what can be achieved with it. Of course, its usefulness for a particular reader of this work can vary, and it is understandable that some readers may find it unnecessary, just like one can always build and train a CNN from scratch using NumPy alone and without the need of PyTorch or any other deep learning frameworks.

If there must be some takeaways from our analysis in the case studies, they would be the quantitative and analytical results that were non-trivially obtained with the proposed framework, rather than those wrap-up comments or casual remarks that you quoted in many of your comments and mistakenly regarded as the takeaways that we try to convey. Examples of such takeaways include the math expressions for the total cost with quadratic complexity and its minimizer in Lines 303 - 310 (which you quoted in one of your comments for Section 3), or the formula $m \asymp n / p$ in Line 321 that explains what we precisely mean when we say something like "the overall cost is minimized at some intermediate value of $m$".

We believe that this response can address most of your comments about the takeaways from this work. Further responses are presented below to some of these comments, and skipped for the remaining ones to avoid repetition.

Then, you derive a bound on the cost with quadratic complexity and find a minimizer for that, which is approximately $L_{sys}$. This is actually interesting and surely non-trivial, but sadly no further discussion is provided.

The math expressions for the cost and minimizer seem like the kind of "precise and non-trivial takeaways" that you are looking for, while a further discussion will likely fall into the category of "the optimal value of m might depend on various factors, period" comments that you strongly dislike. Could you provide some hints on what kind of further discussions would be useful here?

Then, you state that the cost is minimized by $m \asymp n / p$. That would be interesting, but I cannot find any justification for that statement.

The justification can be found in Lines 315 - 321, right above the quoted statement.

The "implication" in line 323 literally states that "The optimal value of m might depend on various factors, period".

The quoted line is just a wrap-up comment for the quantitative analysis above it, not a takeaway message that we try to convey.

Section 3.2 applies the derived formulas to a counting example. However, (1) the cost analysis is little beyond simply rewriting the formulas, (2) the takeaway is again straightforward (overall counting error is smaller if chunks are smaller)

• We rewrite the formulas for the cost metrics, so that a reader does not have to go back and forth when reading this part.

• The formulas from our analysis for parallel decomposition can be reused not only here but also in other concrete examples of parallel decomposition, or even in more complex algorithms that use parallel decomposition as a building block. Analyzing everything from scratch is thus unnecessary in these cases. This is exactly one of the benefits of having a unified analysis, isn't it?

• We agree that the takeaway about the overall counting error looks straightforward, once the analysis in Lines 343 - 350 has been presented. After all, as mentioned in Line 333, the "counting" example is merely a warm-up exercise that demonstrates how to use the proposed framework in solving a concrete problem.

Thank you for your reply. We do appreciate your thoughtful comments and suggestions, which will certainly be helpful in improving the writing and presentation of our work.

How would I characterize the capabilities of any given LLM in a way that allows to determine what the output would be for a given prompt?

It is true that determining what the exact output by the LLM would be for a given prompt is infeasible, but that should not prevent us from trying to understand and analyze the performance of LLM-based algorithms. Our analytical framework is proposed in an effort to achieve this, and we have shown throughout this work that meaningful analysis is possible without the need for exact characterization of LLMs.

For example, by applying the analytical framework to the "counting" task described in Section 3.2, we are able to predict how the performance of the LLM-based algorithm are impacted by the hyperparameter $m$, based on two weak and natural assumptions about the LLM: (1) the error in solving a sub-task of size $m$ is increasing in $m$, and (2) for each sub-task, the LLM generates a response of length $\mathcal{L}_{\text{dec}} = O(1)$.

In practice, one can leverage measuring and profiling in order to better characterize the capabilities of LLMs. A related discussion on these practical considerations can be found in Appendix B.2.

The paper is far too long for a conference format (the appendix is twice as long as the main paper and includes sections that should be part of the main paper, like related work). This paper would be more suitable as a journal paper.

• There have been many ICLR/ICML/NeurIPS papers that have similar length, and ICLR allows an appendix of unlimited length.
  Similarly, many papers in the past defer full discussion on related works to the appendix, like we do in this manuscript.

• Most of the appendix in our manuscript is about case studies and concrete examples, which are non-essential to our core contribution, namely the proposed analytical framework. A reader of this work should feel free to refer to the appendix selectively, based on their own needs.

Thank you for your review. We hope our response can address your concerns.

The insights the analyses in the paper provide are very generic: "the optimal value of m that minimizes costs might depend on the choices of cost metrics and assumptions of LLM inference service, among other factors", "the minimum error of the overall algorithm might be obtained by some intermediate value of m that achieves a balance between these two failure modes", "each option of retrieval has its own pros and cons". None of these are actionable, and it is unclear that the proposed framework is necessary to obtain them.

Each of the statements that you quoted has been accompanied by concrete, precise and non-trivial analyses obtained with the proposed framework: Lines 286 - 321 for the first quote, Lines 386 - 400 for the second, and Lines 458 - 460 for the third. Each of the quoted statements is merely a wrap-up comment for the corresponding analyses right above it, rather than an insight or key message that we try to convey.

It is unclear whether other insights are generally true, in particular "since a smaller value of m makes each sub-task easier, it is reasonable to expect that the overall error E(y) with this metric will also become smaller as m decreases" -- while the individual errors might decrease, combining multiple steps potentially compounds individual errors, resulting in an overall increase in error.

• We made the quoted claim merely for the "counting" example, and the claim has been backed by both formal analysis (Lines 347 - 349) and empirical validation (Appendix C.1).

• We did not claim that the quoted statement must be generally true and, like you said, there are of course cases where it is not.

• Other examples where the overall error of an LLM-based algorithm depends gracefully on the individual errors include the "sorting" example (Proposition 2 in Appendix C.2.2), as well as the case of additive errors and bounded sensitivity (Proposition 1 with sensitivity parameter $S < 1$). The quoted insight for each of these examples is again backed by formal analysis (thanks to the proposed analytical framework) and empirical validation.

Section 3.3 describes the answer being generated by majority voting, but the correct answer appears only once. Dividing the input text into chunks, it seems that there would be a lot of incorrect and "don't know" answers and, hopefully, a single correct one (for the chunk that did contain the answer). How can majority voting possibly return the correct result in this case?

It is reasonable to use majority voting because we adopt chunking with overlaps in this task, as mentioned in Appendix C.3.1; we will add this note to Section 3.3 in the revision. In this case, the correct answer can appears in multiple chunks, and thus majority voting (with the "don't know" answers excluded, as noted in Line 382) can be helpful when incorrecet answers appear occasionally. More details about majority voting in this example can be found in Appendix C.3.1.

Thank you for your review. We hope our response can address your concerns.

The theoretical part proposes a framework for analysis which looks like a simplistic variant of analysis of parallel algorithms, something one learns during undergrad CS studies.

This claim seems to miss a large part of the content of our work. In fact, the analysis for parallel decomposition (which has its own complications due to the use of LLMs, compared to analysis of parallel algorithms in other domains) only occupies a small fraction of our analysis in this work.

The 'empirical' evaluation in the body of the paper is just a qualitative description of application of the proposed (rather standard) methodology to a few problems.

Could you clarify which "empirical evaluation in the body of the paper" are you referring to? As far as we can tell, all empirical/numerical evaluation has been deferred to the appendix.

"There is 'numerical evaluation' in the appendix, which is not convincing and lacks detail." "While I welcome the idea of systematic analysis of algorithms, including LLM-based ones, the paper lacks both theoretical novelty and empirical justification. Significant effort has to be spent to bring this paper to the level of a publication at a major conference such as ICLR."

We would appreciate more concrete and actionable feedback on our work, e.g., why the numerical evaluation is not convincing, what additional details will be useful, references to prior works that make it plausible to deem our work to be "lacking theoretical novelty", etc.

What part of your analysis is applicable exclusively to LLMs rather than to any parallel algorithm using external resource?

Examples for this include:

• We incorporate the diversity of LLM inference service in our analysis of efficiency and cost metrics. For example, the various forms of the cost function $C_{LLM}(L_{pre}, L_{dec})$ are specific to LLMs.

• We incorporate the inexactness of LLM's computation in our analysis of accuracy and error metrics. For example, in parallel decomposition, the choice of the sub-task size $m$ impacts not only efficiency but also accuracy of the overall algorithm, which is not the case for parallel algorithms in many other domains (e.g., DNN training with data parallelism).

• Any part of our analysis that is not about parallel algorithms.

Thank you for your review. We hope our response can address your concerns.

"Proposition 1 is the key result, and it is quite weak." "It seems like the article builds up to Proposition 1."

This is a misunderstanding. Proposition 1 is not the key result of this work, and it is not even mentioned in the abstract or introduction section. The most important key result of this work should be the proposed analytical framework itself.

The paper states: use “accuracy” to refer to the broader concept of “quality”, and an “error metric” can be any metric that measures how much the output of an algorithm deviates from certain criteria."

Could you clarify what is your concern about this statement?

Concerns about computational graphs, non-determinism, lack of uniqueness, stochastic analysis, etc.

In fact, an LLM call can be deterministic, e.g., when greedy decoding is adopted. Even if stochastic decoding is adopted (along with other randomness), our analysis is conditioned on fixed random seeds (as noted in Lines 213 and 219), which again makes everything deterministic.

Stochastic analysis for LLM-based algorithms is certainly a valuable direction for future work, and it can be built upon our deterministic analysis, though this is beyond the scope of our current work. A related discussion can be found in Lines 883 - 890.

Are the defined costs just qualitative?

Our analysis of cost metrics is obviously quantitative rather than qualitative, as exemplified in Lines 228 - 246, Lines 286 - 323, Lines 435 - 452, among many others in the appendix.

"Hypothetically categorize LLMs into two types: Type-1 LLMs are only prone to the first failure mode, while Type-2 LLMs are prone to both". "Too much speculation in this article."

• We make this simplified categorization merely for the purpose of explanation and illustration. And it is not just speculation, but actually backed by empirical observations (as discussed in Appendix C.3.3).

• It feels unfair to say that there is "too much speculation in this article" merely based on this single sentence from one specific case study in our work.