acceptodds
Under review as a conference paper at ICLR 2027

Does Chain-of-Thought Follow the Computation? A Graph-Based Study of Reasoning Faithfulness

Abstract

Recent progress in large language models (LLMs) has renewed interest in whether the chain-of-thought (CoT) that a model writes is the real reason for its answer. Existing faithfulness metrics treat a CoT as a line of text: they cut it short or insert a mistake and check whether the answer flips (Lanham et al., 2023), or they track how the model’s confidence decays along the chain (Ye et al., 2026). Such metrics compare a CoT only with itself, but the computation behind many problems is a directed acyclic graph (DAG). We introduce metrics that compare a CoT with the exact computation graph G⋆ that a solver program produces for every problem. Order fidelity asks a simple question: does the model state each value in the same order that the computation actually needed it? Path-monotonic fidelity (PMF) asks a related but simpler question at the level of a single step. Propagation Fidelity (PF) comes from a direct experiment we call Dependency-Targeted Mistake Injection (DTMI): we deliberately corrupt one value inside the computation and then check, value by value, whether only the values that were supposed to be affected actually changed. We run both kinds of metrics on the same records, for five task families that cover shallow computation, dynamic programming, and P-complete computation, and seven open-weight LLMs. On the four families where order fidelity needs no correction, graph shape (depth, width, and treewidth) raises the R2 of order fidelity by 0.26, against 0.01–0.06 for the baseline metrics. On models that were not used in fitting, order fidelity reaches a held-out R2 of 0.38, against at most 0.06. Under DTMI the final answer changes in 71–82% of cases, so an answer-flip test would call every model faithful, yet PF is only 0.21– 0.26, because the error leaks into values that do not depend on the corrupted one. These findings suggest that CoT faithfulness reflects the structure of the underlying computation and should be judged against it.

Primary area:
interpretability and explainable AI
Keywords:
Chain of Thoughts, Computation graph, reasoning faithfulness, LLMs

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_yCFeOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes evaluating chain-of-thought faithfulness against an exact computation DAG generated by a predefined solver. It introduces Order Fidelity, Path-Monotonic Fidelity, and Propagation Fidelity, and evaluates them on five synthetic computational task families and seven open-weight LLMs. The results suggest that models may react to injected intermediate errors while allowing those errors to propagate beyond the nodes that should depend on them.

Critical strengths
  1. The paper clearly formalizes several graph-based metrics for evaluating CoT faithfulness.
  2. Using solver-generated computation graphs provides a more explicit reference than comparing a CoT only with modified versions of itself.
  3. The paper includes multiple task families, models, graph statistics, and controlled corruption experiments.
Critical weaknesses
  1. Limited novelty. The central message—that a correct final answer does not necessarily imply a faithful CoT—is important, but has been widely discussed in previous work. The graph formulation is a useful reframing, yet the conceptual advance over existing faithfulness studies appears limited.

  2. Potential false positives from a single reference graph. If a problem admits multiple valid solution strategies, the model may produce a coherent CoT corresponding to computation graph A, while the paper evaluates it against solver graph B. Such a CoT could be incorrectly classified as unfaithful simply because it does not match the authors’ chosen implementation.

  3. The empirical evaluation is not sufficiently comprehensive. The DTMI experiments are limited to two task families and three models, while the benchmark consists largely of synthetic computational problems under greedy decoding. The paper does not adequately evaluate alternative valid solvers, broader reasoning tasks, or stronger recent faithfulness baselines. In addition, several figures and tables are visually dense and could be presented more clearly.

Questions for authors

same as weakness

Reviewer_TgsnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the challenging question of whether chain of thought follows the computational dependencies of a task. Tests that truncate or edit CoT and observe changes in the final answer can reveal how sensitive the answer is to the reasoning text. The authors use a reference computation graph generated by a solver to extend the evaluation beyond the final answer to intermediate states and their dependencies. It has two complementary parts. That is, Order Fidelity and Path Monotonic Fidelity measure whether intermediate values appear in an order consistent with the reference graph. Dependency Targeted Mistake Injection perturbs an intermediate value, and Propagation Fidelity checks whether the model’s continuation matches the expected counterfactual results. This includes the expected values at descendant nodes and unchanged values at nodes that do not depend on the perturbed node. The paper also examines how graph depth, width, and treewidth relate to these behaviors and compares its measures with metrics based on changes to the final answer.

Critical strengths
  1. A change in the final answer does not fully describe how intermediate computations were affected. The paper then distinguishes descendants of the perturbed node from nodes that do not depend on it and examines their responses separately. This provides a more detailed view of whether the model follows the expected dependencies. Even when interpreted only as a behavioral test against a reference algorithm, the approach provides useful information.

  2. For the chosen algorithm, the solver provides intermediate states, dependency relations, and the values expected after an intervention. This reduces reliance on references supplied by humans or language models. Combining this reference with node perturbations lets the method calculate the expected propagation, reproduce problem instances, and check the metrics.

  3. The analyses consider answer correctness, CoT length, task family, and problem size. In particular, it reports the matching artifact caused by restating the CYK input and the near disappearance of the geometry gain after controlling for family x scale. These analyses help identify the method’s limits and show where the metrics and claims need revision.

Critical weaknesses
  1. The introduction defines faithfulness as written reasoning that reflects the computation the model actually used. However, the reference graph, however, describes only the chosen solver. A model may faithfully use a different algorithm. It may also obtain the answer through another process and then generate an explanation that matches the reference graph. The authors should validate the metrics using controlled reasoning processes whose faithfulness is known. Better prediction of OF from graph features and low correlations between OF and existing metrics will not replace this validation.

  2. Matching the first occurrence of a number can give a perfect score to text that shows no computation. Section 3.2 locates a computation node through the first occurrence of its numerical value. However, equal values do not necessarily identify the same node. The authors should explain how the matcher distinguishes input values, operands, state assignments, and repeated numerical values. This part of the method needs a more precise description.

  3. Order Fidelity (OF)may penalize computation orders that satisfy all dependencies. A DAG usually fixes only a partial order, for example, For A --> C and B --> C, both A, B, C and B, A, C satisfy every dependency, but if one is taken as the reference total order, the Kendall tau of the other is only 1/3. So if rank(v) comes from a linear topological order chosen by the solver, a low OF may only reflect a different arrangement of independent branches rather than a violation of the computation dependencies.

  4. The interpretation of DTMI leakage lacks a paired control without corruption. The paper does not report continuations without corruption for the same instances, prefix format, and probe nodes. Errors at nodes that do not depend on the perturbed node may therefore include computation or output errors that the model would have made anyway. The reported 65% to 74% cannot all be attributed to leakage caused by the intervention.

Questions for authors
  1. Could you provide complete definitions of node matching and rank, then validate the metrics using input restatements, repeated values, valid swaps of independent branches, and reasoning processes known to be faithful or unfaithful? Do the main regression results and model rankings hold after these issues are addressed?

  2. With paired controls without corruption on the same instances and probe nodes, how much of the error at nodes that should be unaffected can be attributed to the intervention? Do similar propagation patterns appear when the intervention is applied to the model’s own CoT?

  3. After clarifying which samples enter each analysis, could you test the geometry effect by holding task family and problem size fixed while varying graph structure? If the effect remains unclear under these controls, is there enough evidence to support the paper’s main conclusions?

Reviewer_z62eOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes judging CoT faithfulness against the exact computation graph a solver produces for each instance, over five task families in three complexity regimes. It introduces order fidelity and path-monotonic fidelity, which compare the order in which values appear in the CoT with the graph's dependency order, and Propagation Fidelity, obtained by corrupting one intermediate value and checking whether only its descendants change. On seven open-weight models it reports that depth, width and treewidth predict order fidelity better than the complexity tier, that models react to a corrupted value but leak the error into unrelated values, and that a CoT with no computation can fool a naive matcher.

Critical strengths
  • The idea of comparing the CoT with the exact computation graph built by a solver is interesting.
  • Experiments are performed on a wide set of models and on tasks from different computation categories, with the baseline metrics scored on the same records.
Critical weaknesses
  • Unclear measurement of faithfulness. The proposed metrics check whether the CoT follows the computation of a reference solver. They do not take into account that the model may decide to solve the task with a different algorithm from the solver's.
  • DTMI does not report a matched uncorrupted-prefix control. The behaviour under DTMI is not compared against the behaviour on the same prefix without the corruption. Mistakes unrelated to the corruption may occur even without it.
  • Insufficient validation of Order Fidelity. Sec 4.3 shows that OF can produce misleading numbers due to text-matching issues. Analogous checks are not shown for the other tasks.
Questions for authors
  • Some DAGs can be serialized into a chain of thought in different ways. Does the OF metric take this aspect into account?
  • When DTMI inserts an error into the CoT, does the model keep to the CoT formatting, or does it try to correct the error and thereby violate the task formatting?
  • In Sec 4.2, L343-346, it is reported that, once family and problem size are fixed, the graph numbers add almost nothing. Why do you think this is the case? What is the variance of the graph numbers once family and problem size are fixed?
  • Regarding W3, could you run the null-CoT check on the arithmetic and DP families?
  • Are models told which algorithm or output format to use?
  • How does the numerical matcher distinguish a computed node value from an earlier occurrence of the same numeral as an operand or index?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.