Evaluating Step-by-step Reasoning Traces: A Survey

1 Introduction

• The survey offers a systematic review of step-by-step reasoning evaluation criteria to address the lack of consensus amid rapid growth in evaluators and datasets.It aims to provide a foundation for implementing evaluators.Source: §1 · p. 1
• The survey categorizes and compares evaluator implementations, including architecture trade-offs in computational cost and expected performance and non-architectural factors such as training data and format.It also identifies additional dimensions for consideration.Source: §1 · p. 1
• It defines a clear, universal taxonomy of step-by-step reasoning evaluation criteria.The taxonomy is intended as a foundation for evaluator implementation.Source: §1 · p. 1
• It surveys existing datasets and evaluators across diverse reasoning tasks and evaluation criteria based on their implementations.This contribution covers both datasets and evaluators.Source: §1 · pp. 1–2
• The survey identifies recent findings and promising directions for reasoning-trace evaluation.Source: §1 · p. 2

2.1 Step-by-step reasoning

• A reasoning instance pairs a query with an autoregressively generated natural-language trace whose final answer can be compared with ground truth.The final answer is part of the reasoning trace.Source: §2.1 · p. 2

2.2 Evaluation

• Reasoning trace evaluators score trace quality against a criterion, using approaches ranging from intrinsic metrics to models specialized for evaluation.Source: §2.2 · p. 2

2.3 Meta-evaluation

• Evaluator quality can be assessed either with step-labeled meta-evaluation benchmarks or by measuring improvements in downstream reasoning tasks.Source: §2.3 · p. 2

2.3.1 Meta-evaluation Benchmarks

• Benchmark evaluation measures accuracy in classifying step-quality labels and reveals criterion-specific strengths, but human annotation is costly and gains may not transfer downstream.Prior work reports these annotation costs (Lightman et al., 2024; Zheng et al., 2024a) and limited generalization (Zhang et al., 2025).Source: §2.3.1 · p. 2

2.3.2 Downstream performance improvement

• Verifier-guided search uses evaluator scores to select promising traces through Best-of-N decoding or tree search, often comparing performance with Self-consistency majority voting.A larger performance gap over Self-consistency indicates a better evaluator; cited methods include Lightman et al. (2024), Zhang et al. (2024c), Yao et al. (2023), Guan et al. (2024), Zhu et al. (2024b), and Wang et al. (2023b).Source: §2.3.2 · p. 2
• In reinforcement learning, evaluators supply training rewards; higher final-answer accuracy suggests useful rewards, while success despite spurious-feature reward hacking suggests evaluator robustness.Length is one cited spurious feature (Zhang et al., 2024a).Source: §2.3.2 · p. 2

3.1 Factuality

• Factuality distinguishes grounding in the query or reliable sources from parametric knowledge, whose subtle commonsense claims remain difficult to verify.Groundedness also requires using correct numbers and constraints supplied by the query, including in less factual tasks such as math.Source: §3.1 · p. 3

3.2 Validity

• Validity concerns logical soundness: steps may need to follow from or avoid contradicting prior steps, while math and logic often assess correctness against calculations or premises.Examples include accurate arithmetic and drawing the correct logical conclusion from provided premises.Source: §3.2 · p. 3

3.3 Coherence

• Coherence asks whether a step’s preconditions have been established earlier, so a trace can be valid yet incoherent when its premise is only deducible from the query.Judgments are pragmatic and subjective; annotators have disagreed on whether seemingly trivial steps are necessary.Source: §3.3 · pp. 3–4

3.4 Utility

• Utility measures a step’s contribution to the answer, assessed as progress toward a ground-truth solution or as a value estimated from sampled continuations.The value-function approach can scale using reward computed from the gold answer, without human annotation or ground-truth solutions.Source: §3.4 · p. 4

• Reasoning-trace datasets support evaluator training and evaluator meta-evaluation, and Table 4 summarizes existing resources.Source: §4 · p. 4
• PRM800k (Lightman et al., 2024) uses crowdsourced positive, negative, and neutral tertiary validity labels at each step, framing error detection as sequence classification.Its design inspired successors (Zeng et al., 2024a; Xia et al., 2025).Source: §4 · p. 4
• Because human annotation is costly and difficult to scale, works estimate utility with MCTS (Wang et al., 2024c; Luo et al., 2024b; Setlur et al., 2024) or generate perturbed traces with LLMs (Lu et al., 2024; Song et al., 2025).Source: §4 · pp. 4–5
• More recent datasets enable multi-criteria meta-evaluation (Jacovi et al., 2024; Tyen et al., 2024; Song et al., 2025) and extend coverage beyond mathematics to diverse domains (Zeng et al., 2024b, 2025).Source: §4 · p. 5

5 Evaluator types

• The survey summarizes eight popular evaluator types according to their evaluated criteria, strengths, and weaknesses.Choosing an evaluator for a target criterion and task is non-trivial.Source: §5 · p. 5

5.1 Rule-based matching

• For graph-representable tasks, rule-based matching checks relations for factuality, step order for coherence, and gold-chain presence for utility, but does not generalize to tasks without clear symbolic representations.Examples include knowledge graphs for factual reasoning and computation graphs for arithmetic problems (Nguyen et al., 2024; Li et al., 2023b); utility is based on the gold reasoning chain (Nguyen et al., 2024; Saparov and He, 2023).Source: §5.1 · p. 5

5.2 Intrinsic metrics

• Uncertainty-based evaluators use model uncertainty as a quality proxy, mainly for factuality but also for validity and utility, making uncertainty a criteria-agnostic signal.Methods include token-probability entropy (Qiu et al., 2024) and entropy over clusters of semantically similar tokens (Kossen et al., 2024).Source: §5.2 · p. 5
• V-information measures how much a trace raises the probability of the final answer, indicating utility, while a step’s V-information given prior steps roughly indicates coherence.Chen et al. (2023) apply V-information to trace utility, while Prasad et al. (2023) use it to assess whether a step follows from its context.Source: §5.2 · p. 5
• LLM-as-value-function evaluators align rewards with token probabilities and can retain trace-generation ability, but require many good and bad traces and mostly target utility.When rewards depend on final-answer correctness, token probabilities correspond to utility (Mahan et al., 2024; Lai et al., 2024; Xie et al., 2024; Pang et al., 2024); training objectives include DPO (Rafailov et al., 2023) and GRPO (Shao et al., 2024).Source: §5.2 · pp. 5, 7

5.3 External evaluators

• Cross-encoders evaluate a step against the query for factuality or prior steps for validity, but limited language understanding and context length restrict complex-task performance.They can be trained on off-the-shelf tasks (Golovneva et al., 2023a; Zha et al., 2023; Prasad et al., 2023) or LLM-perturbed data (Zhu et al., 2024b).Source: §5.3 · p. 7
• Sequence classifiers predict supervised numeric scores at the step or trace level and can assess validity or utility, achieving performance and efficiency but requiring costly stepwise labels and offering limited explainability.They cannot generate rationales for scores, which can lead to spurious errors (Ankner et al., 2024; She et al., 2025).Source: §5.3 · p. 7
• Critic models treat trace evaluation as a reasoning task and can assess factuality, validity, coherence, and utility across diverse tasks, but rationale generation requires substantial time and computation.They can use prompting or fine-tuning, including chain-of-thought prompting (Huang et al., 2024a) and reinforcement learning with verifiable rewards (Chen et al., 2025a).Source: §5.3 · p. 7

Validity and utility are complementary

• Combining validity and utility improves sequence-classifier performance over either criterion alone and yields better Best-of-N performance than either score individually.Zhang et al. (2025) uses critic judgments for validity and MCTS-based rollouts for utility; Sun et al. (2024) and Kim et al. (2025b) report gains from averaging critic scores.Source: §6 · pp. 7–8
• Invalid but useful steps—logically wrong steps that reach the correct answer—drive validity–utility misalignment and can cause reasoning ability to be overestimated.These steps are also described as unfaithful reasoning (Lyu et al., 2023; Schnitzler et al., 2024).Source: §6 · p. 8

Partial context allows efficient and accurate evaluation

• Full-context evaluation may exceed evaluator context limits, particularly for long traces from large reasoning models.Validity and coherence evaluate steps based on preceding steps, motivating alternatives to using the full preceding context.Source: §6 · p. 8
• Partial-context evaluation uses entailment graphs to select relevant premises, reducing context length, improving efficiency and accuracy, and distinguishing direct from accumulated errors.Direct errors have valid premises but invalid reasoning; accumulated errors have invalid premises but valid reasoning.Source: §6 · p. 8, Figure 4 · p. 8

Test-time scaling improves evaluator performance

• Majority voting improves incorrect-step detection with log K, while longer traces from large reasoning models significantly improve error detection.Under constrained compute, majority voting often outperforms verifier-guided search for weaker evaluators, but stronger sequence classifiers or critic models can outperform majority voting in Best-of-N.Source: §6 · p. 8, Figure 4 · p. 8

7 Future directions

• Evaluators and meta-evaluation benchmarks should cover realistic tasks such as repository-level coding, medicine, and law that require up-to-date external knowledge retrieval.Existing datasets mostly cover simple factual reasoning or self-contained problems; broader coverage could make evaluation more applicable to realistic scenarios.Source: §7 · pp. 8–9
• Evaluation resources for long reasoning traces should distinguish critical errors that are later corrected from errors left uncorrected, which a single scalar score can obscure.Large reasoning models produce complex traces involving self-verification and backtracking, and evaluation resources could improve understanding of their behavior, performance, and credibility.Source: §7 · p. 9
• Finding premises for NLI-based validity and coherence evaluation remains difficult: ROSCOE uses minimum pairwise NLI scores, while recent work has LLMs annotate premises.Uncertainty-based methods and parsers that represent step dependencies as graphs are plausible but underexplored alternatives.Source: §7 · p. 9

Symbol-grounded evaluation of reasoning traces

• Symbolic solutions can define precise evaluators for validity and utility, but extending trace-parsing approaches to first-order logic and interactive-prover math remains unattempted.Rule-based parsing has been applied to simpler reasoning tasks; formal math settings include Lean and Isabelle.Source: Symbol-grounded evaluation of… · p. 9
• Complex, expert-level tasks need specific rubrics, but automatically generating high-quality, expert-level rubrics across diverse reasoning tasks remains an open question.Manual rubric creation is costly and less scalable; AutoRace generates rubrics from incorrect responses, while RaR extracts checklist-style rubrics from biomedical documents.Source: Symbol-grounded evaluation of… · p. 9

8 Conclusion

• The survey provides a unified taxonomy of evaluation criteria for step-by-step reasoning traces.It aims to support understanding and improvement of LLM reasoning capabilities.Source: §8 · p. 9
• The survey reviews existing evaluators and their implementation, and examines directions for improving them.Source: §8 · p. 9
• Evaluators can become obsolete as new reasoning tasks and methods emerge, especially for complex traces from new tasks and models.Precisely evaluating traces and understanding LLM errors will remain important as LLMs are used in challenging, high-stakes real-world reasoning tasks.Source: §8 · p. 9

A Tasks

• Different reasoning tasks share evaluation criteria, but task-specific literature emphasizes different ones, contributing to divergent terminology and definitions.Source: A Tasks · p. 20

A.1 Multi-hop Question Answering

• Factual multi-hop question answering (MHQA) evaluation mainly checks trace factuality through semantic alignment with retrieved documents, as solving often entails identifying bridging entities (Yang et al., 2018; Golovneva et al., 2023a).Source: §A.1 · p. 20
• Commonsense MHQA may require implicit knowledge, making factuality, validity, and coherence difficult to separate and validity or coherence judgments potentially subjective (Jacovi et al., 2024; Zeng et al., 2024b).Source: §A.1 · p. 20

A.2 Symbolic Reasoning

• Symbolic tasks make utility and validity prominent criteria, while math benchmarks range from arithmetic word problems to games requiring search and backtracking (Amini et al., 2019; Cobbe et al., 2021; Yao et al., 2023; Kurtic et al., 2024).The survey uses symbolic reasoning broadly to include math and logical reasoning expressible in symbols (Sprague et al., 2024).Source: §A.2 · p. 21
• Deductive and constraint-based datasets diagnose LLM reasoning but are often synthetically generated and may not generalize to real-world linguistic diversity and commonsense; algorithmic tasks manipulate strings or data structures (Tafjord et al., 2021; Zhong et al., 2021; Wei et al., 2022).BIG-Bench-Hard and NPHardEval include 11 and 9 algorithmic tasks, respectively, described as challenging for GPT-4 and PaLM-540B (Suzgun et al., 2022; Fan et al., 2024).Source: §A.2 · p. 21

A.3 Others

• Science reasoning combines complex facts and world knowledge with precise math or logic, while expert-domain tasks require domain knowledge and strategies but are often simplified because expert annotation is costly (Hendrycks et al., 2021; Rein et al., 2024; Holzenberger and Van Durme, 2021; Guha et al., 2023).Source: §A.3 · pp. 21–22
• Code’s strict syntax and execution-based assessment make step segmentation and answer-explicit metrics difficult, so specialized evaluators mostly measure trace-level utility via predefined unit-test pass rates (Dai et al., 2025).Source: §A.3 · p. 22

B Appendix for Meta-evaluation Datasets

• The appendix discusses dataset construction with a focus on annotation and label types and points to Table 4 for a summary of existing datasets.Source: B Appendix for Meta-evaluation Datasets · p. 22

B.1.1 Labeling methods

• Lightman et al. (2024) crowdsourced validity labels for 800k steps across 75k reasoning traces, using active learning to add hard samples to subsequent reward-model training.The selected hard samples had incorrect final answers but were judged valid by the reward model.Source: §B.1.1 · p. 22
• LLM labels are a cheaper alternative but remain error-prone, so they often augment training; perturbations create diverse erroneous traces but may not reflect real LLM errors.Zhu et al. (2024b) and Lu et al. (2024) prompt an LLM to introduce predefined errors into traces that reach the correct answer.Source: §B.1.1 · p. 22
• Step-level utility uses rollout success or binary search for low-utility steps, while trace-level utility uses final-answer correctness; both are cheaper but unreliable proxies for factuality, coherence, and validity.Setlur et al. (2024) use advantage labels for the change in expected reward before and after a step; correct-answer traces can still contain factual or logical errors.Source: §B.1.1 · pp. 22–23

B.1.2 Inter-annotator agreement

• Three annotators agreed on 95.9% of GSM8k correct-trace cases but only 47.8% of OmniMATH incorrect-trace cases, showing greater disagreement on harder, incorrect examples.ProcessBench reports this contrast across the easiest and hardest cases.Source: §B.1.2 · p. 23
• REVEAL (Jacovi et al., 2024) found disagreement over world knowledge and unclear references, while BIG-Bench-Mistake reported Krippendorf’s α > 0.97 on linguistically uniform algorithmic tasks.Disagreement categories also appear in simpler textual-entailment tasks, linking linguistic vagueness with annotator disagreement.Source: §B.1.2 · p. 23

B.2 Label types

• Sequence classification assigns labels to each step or trace; Lightman et al. (2024) used a neutral validity label for ambiguous cases, and treating it as positive or negative changed Best-of-N performance by less than 1.0p.Wang et al. (2024c) use binary step labels based on utility, while Lightman et al. (2024) use correct, incorrect, or neutral labels.Source: §B.2 · pp. 23–24
• Because sequence labels after an initial error are ambiguous, preference learning compares winning and losing traces, often from shared prefixes or perturbed traces, and can train value models with DPO (Rafailov et al., 2023).The ambiguity is whether later steps should be incorrect due to relying on faulty premises or correct under those premises.Source: §B.2 · p. 24
• First-error-index labels identify the earliest erroneous step or predict -1 when none exists, bypassing propagated-error ambiguity; converting them to binary labels can improve sequence-classifier and critic performance.Zheng et al. (2024a) and Zeng et al. (2024a) use this labeling setting.Source: §B.2 · p. 24

C.1 Comparison between proposed definitions

• Factuality relates a step to provided or external knowledge, while validity relates it to earlier generated steps; a claim can fail either criterion for different reasons.For example, saying Einstein died in 1965 conflicts with the stated 1955 date, while it is invalid if prior premises imply he died in 1955.Source: §C.1 · p. 24
• The factuality–validity boundary can be vague in commonsense reasoning; REVEAL uses human annotators, and LLMs classify factual statements versus inferences poorly (F1<0.65).The cited examples and findings are reported by REVEAL (Jacovi et al., 2024) and LLM studies (Anil et al., 2023; Brown et al., 2020).Source: §C.1 · p. 24
• Validity judges a step’s logical correctness, whereas coherence concerns its pragmatic informativeness: omitting a needed step can make a later step incoherent but still valid.The omitted step can be deduced from the query and preceding steps, even though it is absent from the trace.Source: §C.1 · p. 24
• 51.8% of invalid traces have correct answers in ProcessBench’s olympiad-level Omni-MATH; separating validity from utility improves classifier training and Best-of-N decoding.The cited findings are reported by ProcessBench (Zheng et al., 2024a) for Omni-MATH (Gao et al., 2024b), and for classifier training (Zhang et al., 2025) and Best-of-N decoding (Sun et al., 2024; Kim et al., 2025b).Source: §C.1 · pp. 24–25

C.2 Comparison to other definitions

• Hallucination can cover validity/coherence failures and factuality errors, while faithfulness may mean query-and-step consistency or accurately reflecting internal reasoning, a coherence concern.These definitions vary across cited works, including Ji et al. (2023), Banerjee et al. (2024), Maynez et al. (2020), and Lyu et al. (2023).Source: §C.2 · p. 25
• Informativeness means adding helpful information toward the answer and is synonymous with utility; its absence is described as redundancy or irrelevance.Redundancy means removing the step does not affect reasoning, while irrelevance means it is unrelated to the query’s topic or task.Source: §C.2 · p. 25

D Details for Section 6

• Section D provides further details for Section 6’s Figure 4; its compute estimate uses parameter and token counts, with parameter count constant across evaluators sharing a base model.The approximation follows Snell et al. (2024) and Kim et al. (2025b).Source: D Details for Section 6 · p. 25, §D.1 · p. 25

D.1 Estimating Compute

• Sequence classifiers use one forward pass, while stepwise evaluators scale with 6.11 average steps; DeepSeek LRMs use 7.58× tokens, PARC reduces token cost, and majority voting multiplies compute by 8.Fine-tuned critics (She et al., 2025) and LRMs are stepwise; DeepSeek-Distill-Qwen-2.5-7B (DeepSeek-AI, 2025) has the longer traces, and PARC (Mukherjee et al., 2025) uses an average of 1.57 premises per step.Source: §D.1 · p. 25

D.2 Data source

• Base-model and majority-voting scores came from Qwen-2.5-7B-Instruct experiments using Kim et al.’s (2025b) code, while fine-tuned LRM scores were reported in that paper.Source: §D.2 · p. 26
• Sequence-classifier scores came from Zhang et al. (2025), and fine-tuned critic-model scores came from She et al. (2025).Source: §D.2 · p. 26
• Partial-context scores were provided by PARC authors (Mukherjee et al., 2025) on request; they were absent from the then-available paper version but slated for its published version.Source: §D.2 · p. 26