Cumulative Reasoning with Large Language Models

Thank you for your insightful feedback and the positive assessment of our work's conceptual novelty. We appreciate your constructive suggestions and will address each of your concerns in detail.

Why CR works

We recognize the importance of delving deeper into the theoretical foundations that contribute to the superior performance of CR over methods like CoT and ToT. Our investigation into this aspect was constrained by time during our submission to ICLR, but we believe that topos theory offers a compelling explanation.

Topos theory, a sophisticated concept bridging logic, programming theory, and mathematics, provides a framework for understanding how CR effectively decomposes problems in these fields. This theory can be visualized as a dynamically expanding graph. In this graph:

• Each node represents a claim or assertion.
• Edges or hyper-edges symbolize the relationships between these claims. As the CR process unfolds, it selectively utilizes some nodes from this graph to generate new ones. These new nodes can be seen as limits, subobjects, or objects in different categories within the topos framework. Crucially, once a new node is generated, it becomes a part of the foundational nodes for future derivations, embodying the cumulative nature of the process. However, it's important to note that not all nodes are used in each iteration, and they don't necessarily form a layered structure.

This topos-based structure, with its non-linear and cumulative expansion, aligns closely with the operational principles of CR. We propose that this elegant theoretical underpinning is a key reason behind CR's effectiveness in tackling complex problems in logic, programming, and mathematics. Our future work aims to elaborate on this foundation, offering a deeper understanding of why CR is particularly adept in these areas.

W1: Clarification of the contribution source in CR

We conducted an ablation study on FOLIO-wiki to measure the Verifier (which is the self-correctness ability you mentioned) as well as the random choice of premises in the Proposer (affecting the width of search among candidates and hypothesis you mentioned), and the results are shown in the table below:

It is evident that our Verifier, as well as the random choice of remises in Proposer, are quite effective. At the same time, it is straightforward that if we remove the Verifier but retain the random choice of remises skill in Proposer, the quality of propositions put forward by the Proposer without verification will obviously decrease significantly, which will ultimately have a negative impact. However, when both methods are applied, they enhance the reasoning capability of GPT-3.5-Turbo on FOLIO-wiki in a synergistic way, with an effect greater than the sum of their individual improvements.

What's more, we have the following few points that need to be supplemented：

• In the AutoTNLI experiment, we did not implement the verifier, just concatenate all the generated propositions to form a longer context, then still achieve superior results over Direct, CoT, and CoT-SC, even using relatively small language models such as LLaMA-13B and LLaMA-65B.

• In solving MATH problems without code environment experiments, we still did not implement the verifier LLM to reduce the computation cost, but still achieved SOTA results on this dataset:

Finally, on the MATH dataset, we establish new state-of-the-art results with 58.0% overall accuracy, surpassing the previous best approach by a margin of 4.2%, and achieving 43% relative improvement on the hardest level 5 problems (22.4% to 32.1%).

• In solving MATH problems with code environment experiments, we also did not implement the verifier LLM to reduce the computation cost (Only one LLM is used, with one consecutive thinking context session), but also achieved SOTA results on this dataset:

We achieved a 72.2% accuracy on the MATH dataset, significantly outperforming benchmarks like PAL (52%) and ToRA (60.8%). Notably, there was a 66.8% relative improvement over PAL and 12.8% over ToRA on the most challenging level 5 MATH problems, demonstrating the effectiveness of CR in a code environment and further validating the robustness of CR in handling complex tasks.

• In addition, in the successive work DetermLR (https://arxiv.org/pdf/2310.18659.pdf) based on our method CR (their code is mainly based on our released code, with more intricate thinking context management mechanism), the authors did comprehensive experiments on 4 different logical inference dataset, and find that our method and its extension DetermLR, consistently outperformed the renowned baselines, including CoT, CoT-SC, and ToT, with less computation cost (visited states).

W2: CR's adaptation to different tasks

CR's strength lies in its flexibility to adapt to different tasks by leveraging accumulated historical information and compositional reasoning based on previous results. While the methodology indeed varies with tasks, the core philosophy of CR—cumulative reasoning with validation and reporting—remains consistent. This adaptability is a testament to CR's robustness across varied problem domains.

For example, in the Game of 24, CR's methodology involves a more exploratory approach, which is indeed different from the FOLIO-wiki. However, this does not dilute the reasoning capability of CR; instead, it exemplifies its versatility in addressing diverse problem-solving paradigms.

W3: Generalizability of CR beyond FOL-defined tasks

CR is designed to be a general-purpose reasoning framework. Its application is not limited to tasks explicitly defined in FOL. For instance, in the MATH dataset, which is not based on FOL, CR still demonstrates superior performance. This indicates that CR's methodology, while particularly effective for FOL tasks, is adaptable and efficient for a broad spectrum of reasoning challenges.

Q1: Availability of prompts and code

We have made our code and the prompts used for each agent publicly available at https://anonymous.4open.science/r/cumulative-reasoning-anonymous-4477. This repository includes various few-shot examples for different language models, reflecting their specific roles in the CR framework. We also present the meta prompt for solving MATH problems, you can just play with it using OpenAI assistant API, we have created a demo using this prompt on chat.openai.com: https://chat.openai.com/g/g-L3a4ZCIHx-cr-agent-v0-1 .

Q2: Clarification on the parameter 'n'

In FOLIO tasks, 'n' represents the number of verified generated propositions. When 'n=1' and equipped with verifiers, CR still exhibits gains over baselines such as CoT and SC, indicating that the benefits of CR extend beyond merely a wide beam search approach. It is not the beam search numbers, but the number of accumulative intermediate results, that is, the beam search's results are disjointed, but our thinking context is consecutive, which makes the reasoning process of CR different from CoT-SC and ToT. In AutoTNLI, where we did not implement verifiers, 'n' refers to the number of accumulated generated propositions, and when n grows, the accuracy consistently improves. For more ablations on logical inference datasets, please see Figure 3 (The impact of the number of generated determinate premises) in the paper DetermLR (https://arxiv.org/pdf/2310.18659.pdf), which also shows consistent improvement with more accumulated propositions.

Q3: Examples for predictions in TNLI

The authors of AutoTNLI have made a brilliant webpage: https://autotnli.github.io/, and according to Table 1 in their paper (https://vgupta123.github.io/docs/autotnli.pdf), they have presented a nice example in Person category, the task is predicting the given hypothesis is True or False (they denoted them as Entail and Contradict).

Q4: Relevance of Logic Background in non-FOL-based tasks

The main theoretical motivation of our method lies in the intuitionistic logic, the philosophy of mathematical constructivism, and the topos theory, which asserts that the cumulative process of constructing new propositions is the most natural way to perform complex reasoning, especially in the realm of (higher-order) logic and pure mathematics.

The background on logic provided in Section 2 is crucial for tasks based on FOL. For tasks not explicitly grounded in logic, such as the Game of 24 or the MATH dataset, this background serves as a conceptual framework for the reasoning strategies employed by our CR method. It helps contextualize the approach and its potential applications in a broader spectrum of reasoning tasks, including those not strictly defined in FOL, such as the AutoTNLI dataset, which can only be represented in Higher-order Logic, and the MATH dataset, which can only be represented in Categorical Logic and Topos Theory.

Additional Comments:

• On Redundancy in Tables: We acknowledge the redundancy of Accuracy and Error columns. In our revised version, we have streamlined these metrics for clarity.
• Appendix Clarification: We have revised the appendix to provide clear captions and consistent presentation of model-predicted solutions

Dear Reviewer MLNq,

As the discussion period approaches its conclusion, we want to ensure that we have thoroughly addressed all your concerns and that our revised paper fully meets the standards of ICLR. We would highly value any additional feedback you may provide.

Thank you sincerely for your time and consideration.

Best regards,

The Authors

We appreciate the opportunity to address the insightful questions and concerns raised in your review.

Novelty

Please see the general response. We believe that compared with the existing methods like Faithful Reasoning, Maieutic Prompting, etc., the main contribution of CR is cumulative reasoning plus asking sub-questions/hints.

Baselines

Please see the general response. In our experiments, PAL and ToRA can be seen as CoT + verifier(w/ code), and ToT is selection-inference. We did not test decompose algorithms, because decompose algorithms usually need much more LLM APIs for dealing with subqueries generated by decomposition, and we will consider evaluate these kind of algorithms once we have enough OpenAI API resources.

Statistical Significance

Please see the general response. The DetermLR paper has reproduced CR and got consistent outcomes showing that CR is more effective than CoT/ToT with fewer visited states.

Game of 24 results

If we do not restrict the number of visited states, our method is indeed a brute force search algorithm for the Game of 24. However, what we did in CR is trying to exploit the preferences of LLM based on the current situation, so that we can get the correct answer by visiting as few states as possible, and avoid unnecessary mistakes. This process is not trivial and differentiates CR with pure brute force algorithm. Indeed, compared with baselines (ToT), CR has higher accuracy and smaller visited states, which is a non-trivial result. Moreover, as you said, our model indeed changes slightly here, where our main modification is setting the current explored state as a "premise", with the rest part unchanged.

Generating Hint

The hints were automatically generated by the proposer, which we consider as one of the most important features in CR. Once CR generates these sub-questions (you may treat them as hints/premises), the model will give much better accuracy in complex tasks like MATH. Therefore we did not change our algorithm description, it is just we tell LLM that the premises generated are "hints".

API calls

See the general response.

CR Prompt

We have made our code and prompts publicly available at https://anonymous.4open.science/r/cumulative-reasoning-anonymous-4477, which contains all the prompts that we used.

Test on entire FOLIO

As we mentioned in Section 4.1, we believe that the other source of FOLIO (hyb) contains misleading tasks that are not suitable for testing LLMs. However, in DetermLR paper (see general response), they test CR on the entire FOLIO, which gives better results than CoT.   [1] Decomposed Prompting: A Modular Approach for Solving Complex Tasks, Khot et al.

Dear Reviewer 1GrV,

We understand that our current presentation may give the impression that we are tailoring prompts for different tasks, potentially undermining the perception of our framework's universality.

However, we would like to emphasize the substantial achievements of the CR method on various datasets. Specifically, our performance on the MATH dataset with GPT-4 (without code) and GPT-4-turbo (with code only) demonstrates an impressive accuracy of 58% and 72.2%, respectively. It's worth noting that the MATH dataset is highly regarded and competitive within the research community. Achieving state-of-the-art performance on MATH alone is a significant accomplishment.

Furthermore, while other methods like PHP and SKiC rely on carefully crafted prompts, they still do not surpass the performance of our framework, especially on the hardest level 5 problems. This suggests that our approach, with its cumulative reasoning aspect, holds a unique advantage in tackling complex reasoning problems.

To us, it seems unfair to say "although your method achieves better performance on MATH, which is great, since you also use the same spirit but not exactly the same prompts to solve other tasks and achieve state-of-the-art results, I tend to reject your submission". Our method's ability to consistently achieve state-of-the-art performance across different datasets is a testament to its efficacy.

Dear Reviewer 1GrV,

As the discussion period approaches its conclusion, we want to ensure that we have thoroughly addressed all your concerns and that our revised paper fully meets the standards of ICLR. We would highly value any additional feedback you may provide.

Thank you sincerely for your time and consideration.

Best regards,

The Authors

We appreciate the opportunity to address the insightful questions and concerns raised in your review.

Computational Resources

You are right, in terms of total computational resources, CR is slightly higher than other methods. For example, as stated in General Response, CR with PHP needs 12 API calls, while complex-cot (w/ PHP) uses 7.77 API calls. However, CR explores fewer states compared with CoT/CoT-SC/ToT, which means CR just spends comparatively more time on each state. We'd like to highlight two important aspects in this context:

• Algorithmic Nature and Resource Utilization: It is difficult to adjust each algorithm so that all of them use similar number of API calls, because each algorithm inherently varies in its approach to problem-solving. CoT, for instance, employs a straightforward linear thinking process, naturally limiting its time spent per state. On the other hand, ToT involves a breadth-first search, where the extent of exploration is adjustable. CR's slightly higher resource use is a byproduct of its design philosophy, spending more resources on each state.

• Exploring LLMs' Capabilities: We are in an era of pushing the boundaries of what LLMs can achieve. Our focus with CR is to test the limits of LLMs in solving complex problems, potentially to a human-equivalent level. This exploration, even with a higher resource footprint, is vital for understanding the full potential of LLMs in tackling challenging tasks.

Reliance on verifier

We believe that the success of our method comes from the "cumulative" part, not the verified part. Indeed, in our MATH experiment, CR did not use verifiers, but it still significantly outperformed baseline algorithms. Moreover, in CR, the proposer will not use all the previous steps in each proposal, instead, it will pick a few promising ones. Therefore, the quality of verifier is important, but not crucially important. This makes the error analysis of verifier's accuracy fairly challenging. For now we can only claim we do not need verifiers in MATH, but we are open to testing this further in other domains.

Compare with other methods

Thank you for your suggestions on comparing with other methods! In fact, we have considered many of the methods that you mentioned, but most of them are not open sourced (except Maieutic prompting), which makes it difficult to have a fair comparison. We aim to include these baselines in future experiments, subject to resource availability and API access from OpenAI. Moreover, as we mentioned in the General Response, the experimental results from DetermLR paper have supported our method's efficacy.

Dear Reviewer zUS6,

As the discussion period approaches its conclusion, we want to ensure that we have thoroughly addressed all your concerns and that our revised paper fully meets the standards of ICLR. We would highly value any additional feedback you may provide.

Thank you sincerely for your time and consideration.

Best regards,

The Authors

We appreciate the opportunity to address the insightful questions and concerns raised in your review.

Q1: Comparison with ToT Baseline

Thank you for highlighting the importance of comparing our Cumulative Reasoning (CR) framework with the ToT baseline. While our initial submission did not include this comparison, recent work that builds on the Cumulative Reasoning (CR) framework, named DetermLR, show that CR outperforms ToT across several datasets, including LogiQA, ProofWriter, and LogicalDeduction, with fewer state visits. These results indirectly validate the efficacy of CR in contexts where ToT is also applicable, offering a broader perspective on CR's capabilities in various reasoning tasks. (Please see the General Response for detailed findings.)

Q2: Time/Compute Efficiency

Regarding time and compute efficiency, we meticulously controlled the total number of prompts used in CR to ensure it did not exceed a certain multiple of the baselines. Specifically, the total number of invocations in CR is kept within a manageable limit, comparable to other methods. As for the time aspect, it's challenging to provide an exact estimate due to dependencies on the response rate of the OpenAI API, which can vary based on user activity at the time of execution. We observed considerable variance in the server response speeds during our experiments. However, we ensured that efficiency was within reasonable bounds, making CR a viable alternative to existing methods in practical scenarios. We've provided #API calls comparison in the General Response.

Q3: Implementation of LLM Roles

We understand the importance of clarity in how the LLMs are employed for the different roles of proposer, verifier, and reporter in our method. To address this, we have made our code and the prompts publicly available at https://anonymous.4open.science/r/cumulative-reasoning-anonymous-4477. This repository includes detailed examples of the prompts used for each LLM role, providing insight into how these models collectively contribute to the CR framework. We believe this will offer a comprehensive understanding of their functionalities and interactions within our proposed method.

We hope these responses adequately address your queries and concerns. We are committed to continually refining our approach and are grateful for the opportunity to improve our work based on your feedback.

Dear Reviewer L3qv,

As the discussion period approaches its conclusion, we want to ensure that we have thoroughly addressed all your concerns and that our revised paper fully meets the standards of ICLR. We would highly value any additional feedback you may provide.

Thank you sincerely for your time and consideration.

Best regards,

The Authors