Understanding Chain-of-Thought in LLMs Through Information Theory

Authors: Jean-Francois Ton, Muhammad Faaiz Taufiq, Yang Liu
Primary area: foundation or frontier models, including LLMs
Keywords: large language models, chain-of-thought

Abstract:
Large Language Models (LLMs) have shown impressive performance in complex reasoning tasks through the use of Chain-of-Thought (CoT) reasoning, allowing models to break down problems into manageable sub-tasks. However, existing CoT evaluation techniques either require annotated CoT data or fall short in accurately assessing intermediate reasoning steps, leading to high rates of false positives. In this paper, we formalize CoT reasoning in LLMs through an information-theoretic lens. Specifically, our framework quantifies the `information gain' at each reasoning step, enabling the identification of failure modes in LLMs without the need for expensive annotated datasets. We demonstrate the efficacy of our approach through extensive experiments on toy and GSM-8K data, where it significantly outperforms existing outcome-based methods by providing more accurate insights into model performance on individual tasks.

Decision: reject
Reviewer scores: 6, 5, 8, 5, 8

Reviews and discussion:
<thread>
creation date:
1730073573622

thread_type:
official_review

<thread_object>
creator: reviewer_mocu

<content>
summary:
The paper proposes a novel, information-theoretic framework to analyze Chain-of-Thought (CoT) reasoning in large language models (LLMs). The authors focus on quantifying the "information gain" at each reasoning step, offering a method to detect errors in intermediate steps without requiring human-annotated CoT data. The framework uses concepts like task unidentifiability and conditional mutual information to identify at which intermediate step an LLM fails to execute a particular sub-task during a CoT process. The paper introduces a practical algorithm based on this framework to offer a more granular evaluation of LLM performance on reasoning tasks. Extensive experiments are conducted on toy datasets and the GSM-8K benchmark, showing that this method outperforms existing baselines such as Outcome Reward Models (ORM) and Math-Shepherd in detecting errors and providing insights into model performance.

strengths:
1. The paper presents a novel approach to evaluating CoT reasoning by using information theory, specifically through the concept of information gain at each reasoning step. Compared to traditional methods like ORM, which focus on final outcome, the focus on intermediate reasoning steps allows for a more granular analysis of where a model might be going wrong which is important for LLM reasoning. 

2. The authors provide clear mathematical foundations and definitions for the formulation of their framework. The methodology is well-structured, and the theoretical assumptions are systematically translated into a practical algorithm. The paper’s thorough empirical validation using toy data and GSM-8K provides strong evidence of the framework’s effectiveness in identifying sub-task failures.

3.  By offering a means to detect specific reasoning failures without annotated data, this approach could reduce the need for expensive human supervision and help improve the interpretability and reliability of LLMs in complex reasoning tasks.

weaknesses:
1. In section 3.3, while the information-theoretic approach is innovative, the need to train a separate supervisor model to estimate information gain might introduce complexity. The paper states that the framework doesn't require annotated data, but the supervisor also requires finetune to predict the ground truth final output. 
2. In section 2.2, The framework relies on the decomposition of tasks into primitive sub-tasks, and the assumption that each primitive task contributes incrementally to the information gain. For complex reasoning tasks with intertwined dependencies between sub-tasks, the information gain for each step will be more complex, and this assumption might not always hold.
3. There are some errors in the paper, for example, in appendix B.1.1, the annotation for task $\lambda_2$, if I understand correctly, should be $z_1[0], z_1[0]+z_1[1], z_1[0]+z_1[1]+z_1[2]$.

questions:
1. For math problems, the primitive tasks are intuitive to define. Have you tested your framework with other tasks, e.g. Blocksworld, or commonsense QA, where the definition of primitive tasks is less straightforward? Will different primitive task affect the conclusion?
2. In section 5.1.1, you mentioned the evaluation only considers samples where the final answer of the LLM was incorrect. Could you explain why you apply such a setting since it's also a common failure for CoT to get a correct answer but with incorrect intermediate steps?
3.  Also in section 5.1.1, when discussing about pitfall of the baselines, for ORM, you stated that the classifier becomes confident that the final output will be wrong right after $\lambda_2$, even though the error occurs at $\lambda_3$. But this is what we expect from the error detection, right? I understand you want to show the classifier will overfit on learning the false correlation between $z_2[2] > 150$ and the final error as in section 5.2. But this statement/setting doesn't seem correct to me.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730498342389

thread_type:
official_review

<thread_object>
creator: reviewer_h9ff

<content>
summary:
This paper proposes a new method to understand the effectiveness of chain-of-thoughts. Specifically, The paper proposes to analyze CoT from the information theory perspective. By training a model to predict the information gain, the proposed method could analyze the quality of generated thinking steps and thus select the better answer. The theoretical formulation is intuitive, but more empirical challenges are overlooked. I think more experiments on the general-purpose datasets are needed to justify the value of the proposed framework. Please refer to my questions for more details.

strengths:
1. The authors give a thorough and detailed rhetorical formulation of the proposed solution.
2. The paper is clearly written and easy to follow.

weaknesses:
1. The gap between the proposed framework and the claimed application scenarios remains big, which affects the potential impact of this work.
2. Some of the terms are not clearly defined, especially in the LLM scenarios. (e.g., steps) 
Please refer to the questions section for more detailed comments.

questions:
1. Section 2.1. Do we need to, and how to define the set of lambda in a realistic task?
2. How do you define a step in a generation task?
3. It seems like the key is modeling the information gain. However, a separate model approximates the conditional distribution in the proposed framework, which is then used to model the information gain. As we all know, the training of a separate model is determined by the training data and sampled trajectories. How do you guarantee the learned model can model the conditional distribution well? In other words, what is the requirement for training such a model? Do we need to guarantee that the training data of the separate model follows a similar distribution of the final task?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730518866504

thread_type:
official_review

<thread_object>
creator: reviewer_a8gb

<content>
summary:
The paper presents an algebraic framework to model CoT-based reasoning process in an LLM and in the ground truth. Specifically, it is assumed that there is a set of "primitive tasks", the members of which can be used to generate any task via composition. Such a notion of composition also induces a notion of "span" of a set of tasks and the notion of unidenfiability of a task (with respect to a given set of tasks). The key assumptions in this framework is that when the model's CoT for a prompt contains an unidenfiable task with respect to the tasks involved in the CoT of the ground truth, a "fork-structured" Bayesian network is induced, and due to d-separation, certain conditional independence property holds, which in turn suggests that after the forking point, information gain becomes zero. 

Using this framework, the paper introduce a new scheme for evaluating the CoT of LLM. Experimental results are given demonstrating the advantage of this framework and the proposed scheme.

strengths:
The algebraic formulation and information-theoretic perspective in this paper are very nice. The approach taken is clean. Although the assumptions (particularly Assumption 3.2) may be subject to debate, I think this work is making an important step towards theoretical understanding of the CoT in LLM.  The presentation is also very good. I very much enjoy reading this paper.

weaknesses:
I have only one concern about this paper, namely, I question if the sample-wise information gain (Equation 5) is a valid measure.  

Note that although the standard mutual information (or "distribution-wise mutual information") is well-known to be non-negative and zero mutual information gives independence, the "sample-wise mutual information" (namely, the term without expectation) can be negative in general. The "intuitive" argument the authors give (lines 299 to 303)  to justify the use of sample-wise mutual information is not convincing to me. -- I feel this is the main weakness of an otherwise very elegant development. I encourage the authors to resolve this issue.

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730668436891

thread_type:
official_review

<thread_object>
creator: reviewer_a3yv

<content>
summary:
The paper presents an information-theoretic framework for evaluating the quality of Chain-of-Thought (CoT) reasoning in Large Language Models (LLMs). The authors propose a method that quantifies the "information gain" at each reasoning step to identify failure modes without requiring expensive annotated datasets. The research shows that this approach is more effective than existing methods such as Outcome Reward Modeling (ORM) and Math-Shepherd in assessing intermediate steps in reasoning, especially when dealing with complex CoT processes. The authors claim that with the presented framework, intermediate steps can be used to detect errors, rather than just relying on the final answer. This is a step towards more interpretable CoT reasoning.

strengths:
Applying an information theory perspective to the CoT reasoning chain provides a novel and rigorous method for evaluating the contribution of each step to the final output. This fresh approach differs from existing methods by quantifying the information gain at each reasoning step, rather than relying only on the final answer. This makes it possible to identify when errors occur, improving the interpretability and reliability of the model.

Unlike other methods, it does not require annotated data to train a verifier model, providing a cost-effective alternative to process-monitoring style models. By eliminating this requirement, it provides a scalable solution that is particularly useful for domains or tasks where generating annotated CoT data is impractical or prohibitively expensive.

Finally, the authors experimented with a toy dataset and a real dataset (GSM8K) and compared their approach to baselines. The improvements over the baseline demonstrate the effectiveness of the method.

weaknesses:
I am still unsure about the experimental design, which contradicts some claims of the paper. For example, the use of a supervising model requires a lot of data, which is needed to train the supervising model. This requirement adds computational complexity, requiring additional processing power, memory, and time that the authors claim is not needed compared to the process monitoring models in the introduction. 

In addition, using a supervising model to predict the answer given the previous steps in the chain of reasoning as a way to understand whether the previous steps contain information needed to answer a question may not be correct. For example, many questions can be answered directly by the model in an answer-only setup ("The answer is X"). For these questions, no CoT reasoning is needed. But in this framework this will not be the case and these steps will be listed as important steps. Basically, the framework's sample-wise information gain is designed to detect errors on a per-sample basis. However, there are instances where a model may accidentally reach the correct final answer, even with incorrect intermediate steps. This can lead to "false negatives," where a faulty chain of reasoning is not flagged because the final answer happens to be correct.

Similarly, a lot of time CoT reasoning can hurt performance if the initial step is wrong and then it is hard for the model to recover (https://arxiv.org/abs/2311.07945). In such cases, the steps are considered important if the model can predict the answer correctly, which in many cases is not the case if the start is wrong. There is no analysis done in the paper.
Also, the advantage of the approach presented in the paper is to understand and find the errors in the intermediate steps compared to predicting the final answer. This analysis is missing in the paper, especially in the areas where the intermediate errors are analyzed in detail. 

The experimental results rely heavily on controlled settings, such as toy datasets and GSM-8K, where task types and error points are clearly defined. In real-world scenarios, errors in CoT reasoning may not follow the structured patterns present in these datasets. This reliance on controlled experiments raises the question of how well the framework would perform on naturally occurring data with more diverse error types. This is important for understanding the scalability of the method as the number of reasoning steps increases or the chain becomes more complicated.

questions:
There needs to be an analysis of questions where the model can directly predict the answers and how this framework addresses those questions. Are intermediate steps needed in such cases? And what about false negatives, where a faulty chain of reasoning is not flagged because the final answer happens to be correct? This analysis needs to be presented in the paper. 

The analysis of errors made at different steps needs more analysis. Even better if these stepwise errors form some patterns. How reliable the supervisor model is in identifying these errors would be interesting to see. 
Cost comparison between training the supervisor model presented in the paper and the process supervision paper needs to be analyzed to determine if training a supervisor model is even cheaper as claimed in the paper. 

Doubts about theoretical assumptions: Does the framework assume a linear sequence of reasoning steps, and how would it handle nonlinear or branching reasoning paths? Or what about cases where multiple reasoning chains lead to the correct answer?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730682272692

thread_type:
official_review

<thread_object>
creator: reviewer_qeak

<content>
summary:
The paper proposes to use information theory to quantify the information gain of each reasoning step in a COT solution. The notation of task is introduced for each reasoning step, and assumptions are made for reasoning errors being unidentifiable primitive tasks by the LLMs. The information gain is formulated as a conditional probability difference between two subsequent steps with respect to the final correct answer. A supervisor model is trained to predict such conditional probability. A toy data with 5 primitive tasks are constructed to train the supervisor model and to test the efficacy of the proposed method against baselines including ORM and Math-Shepherd. The paper demonstrated the effectiveness of the Information Gain method to capture errors in reasoning steps (Figure 3 and Table 1).

strengths:
1. The idea of using information gain to detect the helpfulness of each reasoning step is very novel and interesting.
2. The controlled experiments using toy data and GSM8K are well conducted and clearly demonstrate the advantage of Information Gain over baseline methods such as ORM.
3. The paper is well written and easy to follow.

weaknesses:
1. A significant weakness of the paper is that it is unclear how applicable it is to real world reasoning tasks. More experiments involving more challenging tasks such as MMLU or MATH would be more convincing.
2. The assumption of needing to annotate the task involved in each step is too restrictive. In reality, such a one-to-one mapping is neither possible nor necessary. A single reasoning step could use more than a single primitive task. It could also use no primitive task at all by simply being a filer step.
3. The distinction between error steps and irrelevant steps is mentioned but it is unclear how the IG method handles them separately. More clarity is needed. From the description, it looks like they will be treated equally. However, irrelevant steps are not as harmful as error steps.

questions:
1. The paper can benefit from grammar checks.
Line 055 `detect` is repeated twice.
Line 164 `tasks` is supposed to be `task`.
Line 295, `which step went wrong` is using past tense while most of the paper is using present tense. Same for `chose` in line 429.
2. The proposition 3.4 is problematic as Equation (3) is asymmetric with respect to Y and Xj, while we know that mutual information should be symmetric.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733081623637

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Additional experiments on PRM800K dataset

comment:
To further demonstrate the practical applicability of our method, we have conducted an additional experiment on OpenAI's PRM800k dataset [Lightman et al., 2023] which is obtained by labelling the intermediate steps of the MATH dataset. 

More specifically, this dataset is a process supervision dataset containing step-level correctness labels for model-generated solutions to problems from the MATH dataset. To collect this dataset,  Lightman et al., 2023 presented human data-labelers with step-by-step solutions to the MATH problems sampled using a fine-tuned GPT-4 model. The human annotators assigned each step in the solution a label of positive (+1), negative (-1), or neutral (0). A positive label indicates that the step is correct and reasonable. A negative label indicates that the step is either incorrect or unreasonable. A neutral label indicates ambiguity. In practice, a step may be labelled neutral if it is subtly misleading, or if it is a poor suggestion that is technically still valid.

The goal of this experiment was to detect incorrect CoT steps (i.e., the steps labelled as negative by human labellers), using our method as well as the ORM baseline. 


**Aggregate results**

The table below shows the aggregate information gain as well as the mean probability of correctness across the positive, negative and neutral sub-steps (along with 2 standard errors):

|  Human annotations  | -1 | 0 | +1 | 
| -------- | ------- | ------- | ------- |
| IG (Ours)  |  0.058 ± 0.062  | -0.011 ± 0.050 | 0.168 ± 0.030 |
| ORM |   0.734 ± 0.004  | 0.745 ± 0.008 | 0.744 ± 0.002 |

As expected, these results show that the information gain across incorrect steps (with labels -1) is significantly lower than the information gain for labels +1. Additionally, we observe that the information gain across neutral steps (with labels 0) is also comparatively small, which could be explained by the fact that these steps are deemed irrelevant and hence do not add any useful information regarding the ground truth. 

In contrast, the average probability of correctness for the ORM classifier is roughly the same across each label and, on average, is not very informative.

**Sample wise detection**

Additionally, we also used the sample-wise information gain (IG) as well as the ORM baseline to classify if a step is correct (as outlined in Section 3.3.). To avoid ambiguity, we filtered out the neutral sub-steps (with labels 0) for this experiment and considered a balanced held-out dataset with equal number of correct and incorrect steps. The table below shows the sample-wise results for both methods (where we chose the best thresholds for each baseline using a held-out dataset). 

|    | Accuracy | TPR $\uparrow$ | FPR $\downarrow$ | TNR $\uparrow$ | FNR $\downarrow$ |
| -------- | ------- | ------- | ------- | ------- | ------- |
| IG (Ours)  |  0.74  | 0.84 | 0.37 | 0.64 | 0.16 |
| ORM |   0.69  | 0.55 |  0.18 |  0.82 | 0.45 | 

It can be seen that the accuracy of our method is higher than that of the ORM classifier. Additionally, our method also leads to higher TPR and a lower FNR than the ORM classifier. 

The results above show that our method not only remains applicable to more complex datasets such as the MATH data, but additionally, it out-performs the outcome-based baseline in this setting as well. 

Finally, we thank the reviewers for their suggestions to improve our paper and will also include these results in the final version of our paper.

**References**

Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, Karl Cobbe. Let's Verify Step by Step. 2023
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary:
The paper tries to improve the evaluation of chain-of-thought (CoT) reasoning in large language models (LLMs)  with an information-theoretic approach. The core idea is to measure the "information gain" at each step of reasoning, enabling the detection of failure modes without relying on annotated datasets. Through experiments on toy data and the GSM-8K dataset, the paper demonstrates that this approach identifies errors in CoT more effectively than chosen baseline methods such as outcome-based reward models (ORMs) and Math-Shepherd.

Strengths:
- Interesting solution using information gain
- Provides a mathematical formulation for the framework

Weakness:
- The paper received a mixed response from the reviewers
- Generalizability: Initial experiments were mainly on toy datasets and controlled settings. Questions about applicability to more complex reasoning tasks beyond arithmetic remain. It would be useful to compare to baselines in more natural settings and compare against reported numbers in addition to the newly designed controlled settings.
- Limited Real-World Validation: Only intermediate step accuracy reported, no downstream usage such as verifier or reward model
- Assumptions: The framework makes some strong assumptions about task decomposition and primitive tasks. In particular, the requirement for one-to-one mappings of reasoning steps to primitive tasks is restrictive and may not generalize to real-world tasks.
- Supervisor Model: Still requires training a separate supervisor model, adding computational complexity
- Clarity on Error Types: Distinctions between irrelevant and error steps could be better elucidated within the framework.

Decision:
While the work shows promise and addresses an important problem with an interesting solution, unfortunately, the paper can't be accepted in its current form and addressing all the concerns (e.g. more comprehensive evaluation) would warrant another round of reviewing.