S ala MA nder: Shapley-based Mathematical Expression Attribution and Metric for Chain-of-Thought Reasoning (2025)

Abstract: Chain-of-Thought (CoT) prompting enhances the math reasoning capability of large language models (LLMs) to a large margin. However, the mechanism underlying such improvements remains unexplored. In this paper, we present SalaMAnder ( S h a p l ey-b a sed M athematical Expression A ttribution a nd M e t r ic), a theoretically grounded methodology as well as a mathematically rigorous evaluation metric for quantifying component-level contributions in few-shot CoT reasoning. Concretely, we leverage the Shapley value for mathematical expression attribution and develop an efficient stratified sampling algorithm that significantly reduces the computational complexity. Besides, we develop the CoSP ( C ardinality o f S hapley P ositives) metric through covariance analysis. Comprehensive validation across popular LLM models and diverse mathematical benchmarks demonstrates that the CoSP metric within our SalaMAnder framework exhibits a robust monotonic correlation with model performance, not only providing theoretical explanations for the empirical success of existing few-shot CoT but also establishing mathematically rigorous principles for prompt construction optimization. Furthermore, we verify the reliability of the explanation, based on which we unify the insights of previous work.

## introduction chain-of-thought (cot) reasoning has elicited powerful mathematical ability within large language models (llms) reasoning tasks, ranging from arithmetic problem solving to theorem proving. despite the substantial improvements, the mechanism of how reasoning steps lead to correct answers remains underexplored, both heuristic speculation @xcite * work done during an internship at alibaba cloud computing. prior heuristic-driven approaches analyze the role of different components by defining customized input formats. for instance, @xcite and @xcite introduce tailored reasoning steps during inference and investigate the impact of step order and length, respectively. while labor-intensive approaches attempt to explain cot actions through ad hoc trial-and-error adjustments and case-specific manual inspections @xcite @xcite . there is also a shapley-value-based method (horovicz and goldshmidt, 2024) analyzing token-level attribution; nevertheless, the exponential computational complexity and indirect value function design hinder it from real-world applications. in this paper, we propose a unified framework salamander (short for shapley-based mathematical expression attribution and metric), introducing two novel ideas for efficient and semantically coherent cot analysis. first, we denote mathematical expressions as atomic units for shapley-based attribution, addressing the semantic fragmentation inherent in traditional token-level analyses through component-level decomposition. then, we develop a novel stratified sampling algorithm, namely salama (shapley-based mathematical expression attribution) that achieves exponential complexity reduction by decomposing shapley calculations according to component order, reducing time complexity from o(2 n+1 ) to o(2mn 2 ) while maintaining rigorous theoretical guarantees, where n refers to the number of components and m indicates the number of samples. to supplement salama, we also develop the cosp (cardinality of shapley positives) metric based on large language models expr1 expr2 expr3 expr4 the efficient and semantical shapley estimation. the proposed cosp metric within our sala-mander framework formally establishes the monotonic relationship with model performance. theoretically, we provide a rigorous mathematical analysis of this monotonic relation. experimentally, we apply salamander to few-shot learning scenarios, utilizing popular llms (llama-2-13b-chat @xcite , llama-3-8b-instruct @xcite , and qwen2.5-7b-instruct @xcite ) tested on various mathematical benchmarks (gsm8k @xcite , mathqa @xcite , aqua @xcite , multiarith @xcite , and svamp @xcite ) to compute the pearson correlation coefficient. then we further evaluate the reliability of the explanation results. last, we present novel insights that not only reinforce the effectiveness of our methods but also integrate and unify previous research. the contributions of this paper can be summarized as follows: cot methodologies cot prompting, introduced by @xcite , explicitly guides llms to generate intermediate reasoning steps, significantly improving performance on mathematical and symbolic tasks. subsequent work expanded this paradigm through path optimization (e.g., least-to-most prompting decomposes problems into subquestions @xcite ; progressive-hint iteratively refines solutions @xcite ), automation (e.g., automatic cot generates demonstrations via llms @xcite ; symbolic cot distillation transfers cot ability to smaller models @xcite ), and hybrid approaches (e.g., cof-cot combines coarse-to-fine prompting for multi-domain tasks @xcite ; deductive verification adds formal consistency checks @xcite ). despite these advances, most methods rely on heuristic designs without theoretical guarantees, and their efficacy varies significantly across domains-mathematical tasks benefit more from structured cot than openended reasoning. ## method in this section, we introduce the salamander framework, designed to explain the mathematical reasoning mechanisms of cot in llms using shapley values. we introduce our method in three sections: an introduction to shapley values, the salamander sparse computation of these values, and the cosp metric for evaluating cot reasoning contributions. ## experiments this section presents a comprehensive evaluation of the proposed salamander framework, demonstrating its applicability across various settings. appendix b describes the experimental settings, and sec 4.1 utilizes salamander in few-shot learning scenarios to assess the validity of our explanation method and metric. in sec 4.2, we further evaluate the reliability of explanation results. sec 4.3 demo1 demo2 demo3 demo4 ## conclusion in this paper, we propose salamander, a novel framework for understanding and optimizing chain-of-thought (cot) reasoning in large language models (llms). by introducing a theoretically grounded methodology based on shapley value attribution and developing the cosp (cardinality of shapley positives) metric, we have established a mathematically rigorous approach to quantifying component-level contributions in cot reasoning. extensive validation across various llm models and mathematical benchmarks demonstrates that the cosp metric within our sala-mander framework strongly and monotonically correlates with model performance. this correlation not only theoretically explains the empirical success of the existing few-shot cot but also provides rigorous guidelines for optimizing prompt construction. furthermore, it can be utilized to discover novel insights resonating with prior studies.