CS Paper Radar

DASH: Fast, Valid Counterfactuals for Deep Networks via Batched Directional Search

Shraman Pal, Gabriel Medeiros, Clayton Escouper das Chagas, Can Li

cs.LG ·submitted 2026-10-03 21:52 UTC · v1

Abstract

Counterfactual explanations are most useful when they can be generated with low latency, remain close to the factual input, and satisfy input-domain, categorical, and actionability constraints. Achieving these objectives simultaneously is challenging for deep neural networks. Heuristic methods are often fast but may return invalid counterfactuals, whereas exact methods can certify global proximity but may not finish within practical time limits. We introduce DASH, a batched heuristic search method for finding close, valid, and actionable counterfactuals for deep neural networks under $\ell_1$, $\ell_2$, and $\ell_\infty$ objectives. DASH uses directional Lipschitz bounds and local affine models to generate anchors, then ranks and expands promising regions with batched network evaluations. We compare DASH against nine prior heuristic methods and time-limited exact mixed-integer baselines on four tabular datasets, with network depths from 2 to 32, and evaluate scalability on PBMC3k. Across 9,000 tabular query-norm cases, DASH returns a valid counterfactual within $5\%$ of the best heuristic-observed valid distance in $94.6\%$ of cases, with a median CPU search runtime of $0.061$ s. PGD-bisect, the baseline with the highest pooled within-$5\%$ coverage, meets this criterion in $41.1\%$ of cases, with a median runtime of $0.298$ s. These results show that the proposed search maintains high valid proximity across norms while keeping its search runtime practical.

Comment
9 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing

cs.LG ·2026-10-02 ·Ferran Hernandez Caralt, Simon Heilig, Adrián Bazaga, Asja Fischer, Moshe Eliasof +1 more
top venuebenchmarktheorycode/data similarity 0.62
Abstract · Published at the Conference on Neural Information Processing Systems (NeurIPS 2026). Track on Evaluations and Datasets

Empirical claims about the connection between over-squashing and long-range interactions in GNNs, can only be trusted if the benchmarks used to validate them genuinely require long-range interactions. The de-facto standard, the Long Range Graph Benchmark, has been repeatedly shown to be saturated by tuned short-range models, with existing synthetic alternatives being tied to specific topologies. As such, there is a lack of principled certificate of long-rangedness on arbitrary graphs. This state reflects the absence of a precise characterization of long-ranged benchmarks. We address this fundamental gap by introducing four verifiable axioms: Predictability, Tightness, Strictly $k$-Range, and Topology-Invariance, that any task claiming to test $k$-hop interactions must satisfy. We formally prove that violating any one of them admits failure modes that undermine conclusions drawn from the task. Based on these axioms, we introduce TRIP (Truly Ranged Interactions Problem) and its generalisation GRIP (Generally Ranged Interactions Problem), constructive procedures that turn any graph into a provably long-ranged task by drawing features from stable distributions. Moreover, by construction, GRIP admits a closed-form, per-range Maximum-Likelihood oracle that yields the first a priori per-range lower bound on test error available on any benchmark. Using our framework, we: (i) audit 4 common long-range benchmarks and identify their failures modes with respect to our axioms; (ii) on TRIP-instantiated topologies, we find a popular notion of curvature is uncorrelated with GNN performance, supporting topological-vs-computational bottleneck distinction; and (iii) we show that a novel benchmark's over-squashing measures factors beyond pure long-rangedness. Code to use the framework and reproduce experiments is released https://github.com/ferranhernandezc/graph-grip.

0.80

Inference Latency-Aware Tsetlin Machine Training

cs.LG ·2026-10-26 ·Yefan Zeng, Shengyu Duan, Rishad Shafik, Alex Yakovlev
published similarity 0.62
Abstract · Accepted at the 2026 International Symposium on the Tsetlin Machine (ISTM)

The Tsetlin Machine (TM) is a logic-based machine learning model well suited to low-latency inference on resource-constrained edge devices. Because each clause is an AND over Boolean literals, both the literals and their associated Tsetlin Automaton (TA) actions can be represented at the bit level, enabling bitwise evaluation and an early exit that is triggered as soon as any included literal evaluates to zero, forcing the clause output to zero. In this work, we study how the two TM training hyperparameters, T and s, govern both classification accuracy and inference latency. Building on the inversely proportional T-s relationship along which accuracy is nearly constant, we find that inference latency is reduced primarily by increasing s; rather than exhaustively searching the (T, s) grid at high training cost, we propose a directed search strategy that treats accuracy as a constraint and advances toward larger s to reduce inference latency within a fixed evaluation budget. Experimental results on the gem5 simulator with an ARM processor show that, for certain datasets, the search is able to increase s while preserving the baseline accuracy, thereby reducing inference latency at negligible accuracy cost: across six datasets, the method reduces inference latency by up to 16.34%, while some datasets exhibit an accuracy reduction of only 0.06%. The proposed strategy requires far fewer configuration evaluations than an exhaustive grid search.

0.39

RePair: Turning Retrieval Failures into Counterfactual Hard Pairs

cs.IR cs.CV ·2026-08-30 ·Siyi Liu, Xiaorong Zhu, Enjun Du, Xinyu Zuo, Lisheng Duan +4 more
top venue similarity 0.62
Abstract · EMNLP 2026 (Main Conference)

Vision-language retrieval with CLIP-style dual encoders achieves strong cross-modal performance, yet practical accuracy often hinges on localized semantic distinctions where top-ranked near misses differ from the true match by a single critical detail. Hard-sample mining can select confusable candidates but cannot construct corrected counterparts; synthetic augmentation can generate novel samples but, without conditioning on actual model failures, targets irrelevant dimensions of hardness. We observe that a top-ranked false positive is a counterfactual scaffold---sharing most of the query's semantics while differing in a localized failure-causing residual. Minimally correcting this residual yields a hard positive of the ground truth in the same modality; the corrected and unedited versions form a hard negative pair that straddles the decision boundary, producing complementary pull--push supervision. We introduce RePair, guided by three principles---Validity, Minimality, and Locality---which mines false positives bidirectionally, applies LLM-guided counterfactual editing, and trains with a local hard-pair contrastive objective. On Flickr30K and COCO30K, RePair outperforms controlled augmentation baselines with only 107K synthetic samples---26\%--75\% fewer than comparable methods---confirming failure-conditioned repair is more data-efficient than error-agnostic augmentation.

0.46

F$^{2}$DR: A Fine-Grained Full-Pipeline Reward Framework for DeepSearch Workflows

cs.CL ·2026-09-17 ·Bojian Xiong, Wentao Ding, Yujing Lu, Shaowei Zhang, Ling Shi +9 more
top venuebenchmarkcode/data similarity 0.59
Abstract

With the widespread industrial deployment of Large Language Models (LLMs), DeepSearch has emerged as the dominant paradigm for resolving complex user queries. It typically operates through an iterative closed-loop workflow consisting of planning and reflection, information retrieval, and answer generation. However, existing reward models (RMs) and evaluation benchmarks are primarily designed for static single-turn tasks, failing to capture the full-pipeline complexity of DeepSearch workflows. To address this limitation, we propose F2DR, a fine-grained full-pipeline DeepSearch reward framework. F2DR evaluates DeepSearch workflows across three dimensions: Content, Trajectory, and Answer, enabling comprehensive process-level assessment. We further construct DeepSearch RM-Bench, a dedicated benchmark for evaluating RMs in DeepSearch scenarios. Extensive experiments demonstrate that F2DR achieves significantly higher evaluation consistency than self-evaluation-based baselines, while DeepSearch RM-Bench exhibits strong discriminative capability across existing open-source RMs. We will publicly release the complete DeepSearch RM-Bench dataset soon.

0.49

RACE: Relation-Level Counterfactual Explanations for Heterogeneous Graph Neural Networks

cs.LG ·2026-09-29 ·Yuxiang Yao, Zijun Zhao
similarity 0.59
Abstract

Counterfactual explanations of graph neural networks identify edge deletions that flip a prediction. On heterogeneous graphs, however, existing methods first collapse the graph into untyped edges, so they cannot answer the question a domain expert actually asks: which relation type drives this prediction? We present RACE (Relation-Aware Counterfactual Explanations), which gives this question an exact, per-instance answer. For every explained instance, an exhaustive search over relation subsets returns the certified minimum relation-deletion set that flips the prediction -- or an explicit report that no such deletion exists; each relation-level answer is then refined into a typed edge set within the attributed relations, verified on the discrete model by single-edge restoration. The relation-level answer is exact and deterministic given the frozen backbone, whereas soft-mask baselines vary by 6-8 pp in success rate across runs differing only in random ordering. On ACM, a Cora-derived graph, and ogbn-mag, RACE improves counterfactual success rate over the strongest baseline by up to +2.7 pp while deleting fewer edges, and attains the highest success rate among all same-task baselines on every dataset; the advantage reproduces across four backbones on ogbn-arXiv and on DBLP, with cross-seed relation-set agreement up to 0.89. A synthetic study with known generating mechanisms confirms that the search recovers the relation the trained model actually relies on -- and reports infeasibility rather than fabricating an attribution when the model has learned none -- so the explanations stay trustworthy exactly where explanations matter.

0.26

Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark

cs.LG cs.AI ·2026-10-02 ·Steve Azzolin, Francesco Paolo Nerini, Stefano Teso, Francesco Bonchi, Bruno Lepri +2 more
benchmark similarity 0.58
Abstract · Preprint

Explainers for Graph Neural Networks (GNNs) are commonly evaluated by their plausibility, i.e., how well their explanations recover a predefined ground truth, such as a motif planted in the data. This protocol implicitly assumes that a GNN trained on such data relies on the intended motif. Although prior work has questioned this assumption, plausibility remains widespread. First, we show that the assumption is violated on several widely used benchmarks, where, e.g., degree statistics alone suffice to solve the task. Then, we remove this confounder by replacing training with compilation. We achieve this by introducing $\mathsf{Gracr}$, the first compiler translating graded modal logic formulas into GNN weights, yielding models that replicate the behaviour of the corresponding formulas. Since the behaviour of the model is now known by construction, we can define its ground truth explanation formally and compute it exactly. Building on this, we introduce $\mathsf{Gracr}\mathsf{Bench}$, a benchmark of compiled GNNs for the evaluation of explainers against this exact ground truth. Experiments on eleven explainers across six tasks show its effectiveness for fine-grained diagnostic evaluation: notably, we discover that most explainers are not robust to indirect influences or alternative implementations of the same formula. These results position $\mathsf{Gracr}\mathsf{Bench}$ as a novel, rigorous evaluation setting for graph post-hoc explainability.

0.20

P2N: Reusing Deep Representations for Greater Effective Depth

cs.CL ·2026-10-18 ·Yiqin Hao, Boyi Zeng, Zitong Wang, He Li, Shixiang Song +5 more
similarity 0.58
Abstract · 23 pages, 10 figures

Mathematical problem solving and autonomous agents are increasingly important applications of language models, demanding stronger reasoning capabilities. Computational depth is a key resource for such reasoning, but adding model layers increases both training and inference costs, while test-time scaling incurs substantial additional inference computation. We introduce P2N (Previous to Next), which reuses the previous token's deep representations, already available during generation, to increase effective computational depth with negligible decoding overhead. Specifically, P2N adds the previous token's deep hidden state to the current token's shallow representation, allowing subsequent layers to build on previously completed deep computation. This recurrence extends effective computational depth across tokens, while introducing only a single vector addition per decoding step. We train the recurrence using parallel Jacobi updates restricted to a middle-layer core. Experiments with Qwen-style models show that, at 1.5B parameters, P2N improves GSM8K accuracy by over 10 percentage points under both zero-shot and few-shot prompting, with nearly unchanged decoding latency. The benefits also extend to language modeling and average performance on general downstream benchmarks. on general downstream benchmarks.

0.19

Bad Genius: Counterfactual-Guided Harness Evolution Beyond Task-Specific Shortcuts

cs.AI cs.LGstat.ML ·2026-09-16 ·Guojun Zhu, Xunheng Huang, Peng Yin, Jiahui Xie, Sanguo Zhang +1 more
benchmark similarity 0.58
Abstract · 32 pages, 6 figures; includes references and supplementary material

Reliable agent evaluation is complicated by automatic harness optimization, which repeatedly uses a released benchmark $B_{\mathrm{rel}}$ to guide a Proposer that edits prompts, memory, retrieval, tools, and control code around a fixed foundation model. Task holdout is commonly used to guard against harness overfitting. It varies semantic tasks but leaves the benchmark protocol fixed, so a bad genius Proposer can produce a cheating harness whose improvement over the initial harness on $B_{\mathrm{rel}}$ depends on a benchmark-wide shortcut. We introduce Counterfactual Harness Search and Evolution (CHASE), which casts harness evolution as constraint generation over valid counterfactual benchmarks. After each Proposer update, a Challenger searches for an executable protocol transformation with large gain destruction. A validity firewall checks that task semantics are preserved, while a held-out confirmation set determines whether the counterfactual enters a finite archive. We formalize an ideal shortcut-neutralized benchmark $B_0$ and establish theoretical guarantees linking finite counterfactual archives to $B_0$ and characterizing sequential Challenger search. We evaluate CHASE on Syn-Ledger and OfficeQA, where CHASE retains strong released-benchmark gains while substantially reducing gain destruction under valid protocol transformations.

0.41