{"id":"23ae0eba-d836-4288-b23d-f67d5576e1ce","arxiv_id":"2510.15623","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"CQD-SHAP uses Shapley values over query atoms to quantify how much neural (versus symbolic) execution of each atom contributes to a target answer's ranking in complex query answering.","lead":"This paper proposes CQD-SHAP, a method that explains why a neurosymbolic query-answering model ranks a particular answer by attributing each query atom a Shapley value, based on whether that atom is executed neurally or symbolically. It matters because complex-query answering models are otherwise black boxes, and per-atom attributions can help users debug incorrect answers and identify missing knowledge.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The ΔRank payoff function is an unvalidated proxy for 'importance', so the Shapley values, while mathematically exact, may not provide the claimed explanation of atom contributions to ranking.","rationale":"The reader's verdict identified the same weakest assumption: the payoff function is an unvalidated proxy for importance. I agree. This is the most load-bearing concern because it directly determines whether the central claim—that CQD-SHAP explains why an answer is ranked as it is—actually holds. The mathematical machinery (exact Shapley values, efficiency) is sound, but the semantic grounding is not. The paper's evaluation in terms of necessary/sufficient explanations partially addresses usefulness, but it only tests whether the top-ranked atom is the 'most necessary' one, not whether the numerical Shapley values themselves are meaningful. Moreover, the selection-conditional nature of that evaluation (only top-ranked answers for necessary, etc.) further limits its reach. A concrete robustness check against alternative QoIs would settle whether the concern is real. If the atom importance rankings are stable across QoIs, the concern is less severe; if not, the paper's interpretation is ungrounded. Given the reader's CONDITIONAL verdict, my read does not change that verdict; it reinforces it. Hence UNCHANGED.","tokens_in":16675,"tokens_out":15965,"duration_ms":123888,"concrete_test":"Run CQD-SHAP on a random sample of 500 test queries (covering all 8 types) using three QoIs: ΔRank as in the paper, the change in raw score z(e_i), and the change in reciprocal rank (1/r_i). Compute the atom importance rankings produced by each QoI and measure Kendall's τ between ΔRank and each alternative. If τ < 0.5 on a substantial fraction of queries, the ΔRank-based Shapley values are not robust to reasonable alternative definitions of 'contribution', undermining the claim that they provide a unique explanation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central contribution is that CQD-SHAP computes exact Shapley values under the game v(S)=r_i(Q_empty)-r_i(Q_S), and that these values explain the contribution of each query atom to the ranking of a target answer. The load-bearing assumption is that filtered rank improvement is a semantically valid quantity of interest for 'importance'. The paper borrows ΔRank from ranking explanation literature (Pliatsika et al.), but provides no evidence that this QoI matches user intuitions or alternative formalizations such as score margins, set membership, or top-k inclusion. Rank is a highly non-linear and distribution-dependent statistic: it can change dramatically due to small score fluctuations of many irrelevant entities, so an atom's Shapley value can reflect global embedding-space behavior rather than the atom's direct logical/reasoning contribution. Without validation against alternative QoIs or human judgments, the claim that these values 'explain' the ranking is not established—the values are exact for a particular game, but the choice of that game is arbitrary and under-justified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes CQD-SHAP, a Shapley-value framework for explaining, at the level of query atoms, why a neurosymbolic complex-query-answering model ranks a particular answer entity where it does. The players of the cooperative game are the atoms of a query; a coalition S is executed by running the atoms in S with the neural link predictor and the remaining atoms symbolically, and the payoff is the change in filtered rank of the target answer between fully symbolic execution and the partial execution Q_S. Exact Shapley values are computed without approximation, and efficiency gives Eq. (9): the sum of atom attributions equals the total rank change between fully neural and fully symbolic execution. The method is evaluated with necessary/sufficient explanation scenarios on FB15k-237 and NELL995, plus a small case study.","tokens_in":16948,"tokens_out":7611,"duration_ms":70334,"significance":"If validated, CQD-SHAP is a useful first step toward explaining neural/neurosymbolic CQA systems, and it has the appeal of being exact and axiomatically grounded rather than heuristic. The game definition is clean and the efficiency identity is explicit. The paper is also reproducible: code, data, and pretrained models are released, and the main computation is exact with no sampling. The significance is, however, conditional on the choice of the rank-based quantity of interest being semantically appropriate and on the empirical evaluation being statistically credible; the current validation is weaker than the abstract implies.","major_comments":[{"comment":"The choice of DeltaRank as the quantity of interest is load-bearing but unvalidated. The Shapley values are exact for this particular game, but the game encodes a specific definition of 'importance' as improvement in filtered rank. Rank is a global and highly non-linear statistic: it can change because of score fluctuations of many irrelevant entities, so the attributions may reflect global embedding-space behavior rather than the atom's direct logical or reasoning contribution. The paper cites Pliatsika et al. for QoI definitions but gives no evidence that filtered rank improvement matches user-intuitive importance or better alternatives such as score margins, top-k membership, or set membership. Please either validate DeltaRank against alternative QoIs (and ideally human judgments) or reframe the central claim as 'attribution under the DeltaRank game'.","section":"Section 4, Eq. (7)"},{"comment":"The empirical validation reports means only, with no error bars, confidence intervals, or significance tests. Several comparisons with the score-based baseline are very close or even identical, for example FB15k-237 sufficient 2u (+0.348 vs. +0.348) and 2u1p (+0.205 vs. +0.205). The conclusion of 'consistent effectiveness' is therefore not statistically supported. Moreover, the necessary/sufficient evaluation is a consistency check on the same rank-based criterion used to define the Shapley game: selecting the atom with the highest Shapley value and then toggling that atom and measuring the rank change tests internal consistency, not external explanatory fidelity. Please report bootstrap confidence intervals and paired significance tests, and consider an independent ground truth or user study.","section":"Section 5.2, Table 2"},{"comment":"The notation in the filtered-rank definition is ambiguous and possibly inconsistent. If E_A is literally the 'answer set', then E_A \\ (E_easy ∪ (E_hard \\ {e_i})) leaves only {e_i}, making every rank equal to 1. The formula only makes sense if E_A is the full candidate entity set over which CQD scores are computed. In Section 3.1, however, E_A is defined as the answer set. Please define E_A, E_easy, and E_hard unambiguously and state explicitly that the filtered ranking is computed over the full entity set, with correct answers removed except for the target hard answer.","section":"Section 4, Eqs. (5)-(6)"},{"comment":"The implementation of symbolic intermediate atoms is underspecified with respect to tie-breaking. A symbolic atom assigns score 1 to every entity connected via the relation in the observed graph and a score near 0 to all other entities. When more than k entities satisfy an intermediate symbolic atom, the top-k beam search must break ties arbitrarily, and this can make the computed Shapley values depend on entity order and on beam size k. Since the paper claims exactness and reproducibility, the tie-breaking rule should be stated and sensitivity to k should be reported.","section":"Section 4, Eq. (4)"}],"minor_comments":[{"comment":"The phrase 'quantitative results of a case study' appears before Section 5.3, but the case study is qualitative. Reword to 'a case study' or 'quantitative results and a case study'.","section":"Section 5, p. 7"},{"comment":"The paper states that the value function satisfies 'all the fundamental Shapley value axioms' but does not verify them in the text. Since efficiency is central to the contribution, add a short proof or a precise reference to the matching proof in Chowdhury et al. / Pliatsika et al. for DeltaRank.","section":"Section 4, after Eq. (9)"},{"comment":"The use of the terms 'Nec.' and 'Suff.' in Table 4 is confusing because 'necessary' and 'sufficient' are also the names of the evaluation scenarios. Clarify that these columns are the numbers of hard answers that are ranked first by CQD (necessary) and not ranked first (sufficient).","section":"Appendix B, Table 4"},{"comment":"In the paragraph explaining structural differences, the statement 'this pattern is not completely observed for other baselines' is vague. Please name the specific baselines and query types for which the pattern does or does not hold.","section":"Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"The core game-theoretic construction is sound and the exactness/efficiency result is a real strength. The main risk is overclaiming: the semantic choice of DeltaRank and the lack of statistical validation make the explanatory claims stronger than the evidence. I would send this back for a revision that tightens the claims and adds the missing validation, but I would not reject it outright."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper gives CQA people what they didn't have: a principled way to attribute an answer's rank to query atoms, with exact Shapley values and a clean efficiency guarantee. The math is standard Shapley, but the game design over neural-vs-symbolic atom execution is new, and the paper is honest about its limits.\n\nWhat's actually new: first atom-level Shapley explanation for neurosymbolic CQA, plus necessary/sufficient evaluation metrics adapted for this setting. The value function v(S)=rank(Q_empty)-rank(Q_S) is well-defined, v(empty)=0, and Eq. 9 correctly gives efficiency. The case study (Paul Weller) is a nice demonstration: the two Shapley values (+123.5, -128.5) match the rank difference and the graph evidence. Code, data, and pretrained models are public.\n\nWhere the paper is soft: the payoff choice. ΔRank is a reasonable formalization of 'how much does neural execution improve this answer's rank', but it is not validated against user intuitions or alternative QoIs. Rank is a non-linear, distribution-dependent statistic, so a Shapley value can reflect global score behavior rather than a direct logical contribution. The paper sometimes words this as 'importance', which overreaches; the values are about rank attribution under a specific game. The necessary/sufficient evaluation is also a consistency check on the same value function, not an independent test of explanation quality, and Table 2 has no error bars or significance tests. These are fixable weaknesses, not fatal ones.\n\nI'd note one thing: the abstract I read says 'effectiveness ... for most query types', which matches the results; the conclusion is similarly measured. So the overclaiming the reviewer worried about isn't in the text.\n\nBottom line: a solid, reproducible paper that deserves serious review. It is not a breakthrough, but it fills a clear gap and the authors know exactly what they did and didn't show. I'd send it to a good venue and ask for additional empirical rigor and a more careful framing of the QoI. I'd cite it if I were working on CQA explainability.","headline":"A clean, workmanlike contribution: exact Shapley values for query atoms under a rank-based game, with honest limitations and fixable empirical gaps.","tokens_in":17391,"tokens_out":4422,"would_cite":true,"duration_ms":34614,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A Shapley-value game over query atoms attributes each part of a complex knowledge-graph query to its effect on an answer's rank.","keywords":["Explainable Query Answering","Shapley Value","Complex Query Answering","Neurosymbolic Query Answering","Knowledge Graph","Ranking Explanation","Necessary and Sufficient Explanations"],"falsifier":"Construct a query with a dummy atom that never affects the answer set (e.g., a relation that holds for no entities in either graph) and observe whether CQD-SHAP assigns it zero Shapley value; the null-player axiom demands zero, so a nonzero value would show the implementation violates the paper's axiomatic guarantees. Alternatively, on a small 2-atom query where all four coalition rankings can be computed by hand, verify that the reported Shapley values sum to r(Q_empty)-r(Q_neural) and that swapping the top-valued atom to symbolic actually produces the largest rank drop among all atoms—if a l","tokens_in":16587,"feed_emoji":"🧩","tokens_out":7339,"duration_ms":63226,"temperature":0.7,"pith_summary":"The paper introduces CQD-SHAP, a framework that explains why a neurosymbolic query-answering model ranks a particular entity as an answer to a complex query. It defines a cooperative game whose players are the query's atoms: an atom can be executed either by the neural link predictor or by plain symbolic graph lookup, and the payoff of a coalition is the improvement in the target answer's filtered rank over purely symbolic execution. The Shapley value of each atom measures, averaged over all combinations of other atoms, how much switching that atom from symbolic to neural execution helps or hurts the answer's rank. The values satisfy efficiency: they sum exactly to the rank difference between fully neural and fully symbolic execution, giving a formal budget for how the neurosymbolic model changed the ranking. The authors evaluate the resulting explanations on two knowledge-graph benchmarks, showing that the most important atoms identified by CQD-SHAP are more often necessary and sufficient for the ranking than baseline atom-selection rules.","feed_headline":"Shapley values pinpoint which query atom decides an answer's rank","feed_subtitle":"Each atom of a complex knowledge-graph query gets a number; together they sum exactly to the neural-vs-symbolic rank shift.","key_machinery":"The central object is the Shapley game over query atoms: players are the atoms of a DNF query, a coalition S is the partial query that executes atoms in S with the neural link predictor and all others with symbolic graph lookups, and the payoff v(S)=r(Q_empty)-r(Q_S) is the improvement in the target answer's filtered rank relative to fully symbolic execution. The Shapley value formula (weighted average of marginal payoffs over all coalitions) then yields per-atom contributions that satisfy the efficiency, symmetry, linearity, and null-player axioms; the efficiency identity (sum of atom values equals r(Q_empty)-r(Q_all)) is what gives the explanations a formal, checkable meaning.","core_discovery":"Under CQD-SHAP, a query atom's explanation is its Shapley value in the game v(S)=r(Q_empty)-r(Q_S), where Q_S executes atoms in S neurally and the rest symbolically, and r is the target answer's filtered rank. Because the empty coalition's payoff is zero by construction, the four Shapley axioms hold; in particular, the efficiency axiom yields that the sum of the atoms' values equals the total rank shift from fully symbolic to fully neural execution. Individual values are exact (no approximation is needed for typical query sizes), and they cleanly distinguish atoms whose high ranking comes from knowledge already in the graph from atoms where the neural model's inferred links are doing the wor","pith_inferences":["The same 'switch each atom between neural and symbolic execution and measure rank change' recipe could be applied to other neurosymbolic CQA models (e.g., box-based or message-passing decoders) as long as the model decomposes queries into atoms; the explanation method is not intrinsically tied to CQD's fuzzy-logic aggregation.","Because Shapley values are averages over all coalitions, the paper's own caveat holds: greedily executing atoms with positive values neurally and negative ones symbolically does not guarantee an optimal ranking; a natural extension is to use the values as inputs to a planner that selects a subset of atoms for neural execution under a budget.","The value function could be replaced by alternative quantities of interest (score margins, set membership, correctness) to match different user notions of 'importance'; comparing those variants against human judgments would clarify what the rank-based explanation really means.","The dataset-side observation in the paper (some 'hard' answers are actually symbolically reachable) suggests that future benchmark construction should verify answer hardness per query atom, otherwise explanation evaluations on such data can be biased."],"forward_implications":["For a given answer, each query atom receives a number that sums exactly to the total rank improvement of using the neurosymbolic model; this gives users a budget-like explanation of why the answer appeared.","Users can distinguish atoms that rely on facts already present in the knowledge graph from atoms where the neural predictor inferred missing links, enabling them to check whether the ranking is driven by a misleading correlation.","Because the method computes exact Shapley values (no sampling) and typical complex queries have few atoms, the explanation is fast enough for interactive inspection (tens to hundreds of milliseconds per query-answer pair).","The framework can also explain false positives: for an incorrect answer, the per-atom contributions show which query part the neural model wrongly over-trusted.","The necessary/sufficient evaluation protocol introduced here gives a concrete way to compare future explanation methods for complex query answering."],"fun_headline_variants":["Shapley values show each query atom's exact effect on rank","Explain complex KG queries with exact Shapley values","Which query atom lifts an answer? Shapley reveals","Game theory explains answer ranks in knowledge graphs","CQD-SHAP: Exact credit assignment for query answering"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole approach equates 'an atom's importance' with the change in the target answer's filtered rank when that atom is switched between neural and symbolic execution; if a user's notion of importance is better captured by score margins, set membership, or correctness, the Shapley values remain mathematically valid but may not match that notion.","fun_headline_variants_meta":{"raw":{"variants":["Shapley values show each query atom's exact effect on rank","Explain complex KG queries with exact Shapley values","Which query atom lifts an answer? Shapley reveals","Game theory explains answer ranks in knowledge graphs","CQD-SHAP: Exact credit assignment for query answering"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000308,"raw_usage":{"total_tokens":1597,"prompt_tokens":744,"completion_tokens":853,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":488,"completion_tokens_details":{"reasoning_tokens":773}},"tokens_in":488,"tokens_out":853,"duration_ms":7842,"temperature":1.0,"reasoning_tokens":773,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T09:20:55.955970+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a query with a dummy atom that never affects the answer set (e.g., a relation that holds for no entities in either graph) and observe whether CQD-SHAP assigns it zero Shapley value; the null-player axiom demands zero, so a nonzero value would show the implementation violates the paper's axiomatic guarantees. Alternatively, on a small 2-atom query where all four coalition rankings can be computed by hand, verify that the reported Shapley values sum to r(Q_empty)-r(Q_neural) and that swapping the top-valued atom to symbolic actually produces the largest rank drop among all atoms—if a l","supporting_citations":[],"review_version":1}