Exact Search, Uncertain Arrows: Auditing Learned Score Tables

A learned score can prefer the wrong causal graph even when search finds its exact optimum. To understand this mismatch, we introduce an audit framework that separates the ability to find high-scoring graphs from the ability of the score to favor accurate structures. We also examine which arrow directions the predictor favors. Our framework uses tables that store one score per variable and candidate parent set. We project these scores so that all graphs in a Markov equivalence class receive the same total score, then use exact search to find a highest-scoring graph. The component removed by this projection compares how well opposite edge directions fit the data. Better predictive fit alone does not establish the causal direction. We build 180 full ten-variable TabPFN tables and compute their exact optima, enabling repeated search comparisons without further predictor queries. On 70 tables, policy-gradient search finds a graph closer to the true structure than the highest-scoring graph, despite receiving a lower score. BOSS-style search does so on 51. These reversals occur mainly on scale-free graphs, where the highest-scoring equivalence classes often direct edges that the true class leaves undirected. This orientation error persists from 500 to 2000 observations. On Erdős-Rényi graphs, the highest-scoring graph is usually closer to the true structure than the graphs returned by heuristic search. For larger graphs, we find the highest-scoring graph within a restricted search space or using a table with estimated entries. Together, these tables provide a reusable benchmark for assessing search methods and identifying when higher scores fail to yield more accurate causal structures.