A Trace-Grounded Structural Verification Framework for Faithful Explanations in Deterministic Planning Systems Surin Lee Gwangju Institute of Science and Technology

Abstract

Deterministic planning systems, such as Material Requirements Planning （MRP）, generate outcomes through well-defined sequences of interdependent events. While recent advances in large language models （LLMs） enable natural-language explanations of such systems, existing evaluation approaches primarily focus on atomic correctness, verifying individual facts such as dates or quantities. However, in deterministic settings, explanation faithfulness depends not only on factual accuracy but also on whether the explanation preserves the underlying relational structure of the computation. In this thesis, we show that explanations can be factually correct while misrepresenting temporal ordering and causal dependencies among events, revealing a fundamental limitation of conventional fact-level evaluation. To address this issue, we propose a trace-grounded structural verification framework that models deterministic execution processes as relational graphs and evaluates explanation faithfulness through graph alignment. The framework integrates deterministic trace construction, structured evi- dence extraction, and constrained explanation generation, followed by structural verification. We fur- ther construct a dataset with adversarial perturbations grounded in execution traces that explicitly decouple atomic correctness from structural consistency, enabling controlled evaluation of explanation behavior. Experimental results demonstrate that many explanations that pass atomic verification fail under structural evaluation, highlighting a significant gap between factual correctness and structural faithfulness. We also show that structural verification can be used not only for evaluation but also for improving explanation quality through verification-based reranking. These findings suggest that faith- ful explanations in deterministic systems require preserving both individual facts and the relational structure of the underlying process, and that structural evaluation provides a necessary complement to conventional fact-based approaches. Keywords: explainable AI, natural language explanations, faithfulness evaluation, deterministic reasoning ©2026 Surin Lee ALL RIGHTS RESERVED|결정적 계획 시스템（Deterministic Planning Systems）은 상호 의존적인 이벤트들의 순차적 상호 작용을 통해 결과를 생성한다. 대표적인 예로 Material Requirements Planning（MRP） 시스템은 수요와 공급 이벤트의 시간적 누적을 기반으로 자재 부족 시점과 필요 조달 시점을 계산한다. 최근 대규모 언어 모델（LLM）을 활용하여 이러한 시스템을 자연어로 설명하려는 연구가 활발히 진행되고 있으나, 기존의 설명 평가 방식은 날짜나 수량과 같은 개별 사실의 정확성（atomic correctness）에 주로 초점을 맞추고 있 다. 그러나 결정적 시스템에서는 설명의 신뢰성이 단순한 사실의 정확성뿐만 아니라, 이벤트 간의 시간적 순서와 의존 관계를 얼마나 정확하게 보존하는지에 의해 결정된다. 본 논문에서는 설명이 개별 사실 수준 에서는 정확하더라도, 이벤트 간의 시간적 순서나 의존 관계를 잘못 표현할 수 있음을 보이며, 이를 통해 기존사실기반평가의근본적인한계를분석한다.이를해결하기위해결정적실행과정을관계그래프로 표현하고, 설명과의 구조적 정렬을 통해 신뢰성을 평가하는 trace-grounded 구조적 검증 프레임워크를 제안한다. 제안하는 프레임워크는 결정적 trace 구성, 구조적 증거 추출, trace 기반 설명 생성, 그리고 구조적 검증 과정을 통합하며, 결정적 계산 과정과 자연어 생성 과정을 명시적으로 분리한다. 또한 사실 적 정확성과 구조적 일관성을 분리하여 평가할 수 있도록, 실행 trace에 기반한 적대적 변형（adversarial perturbation）을 포함하는 trace-grounded 데이터셋을 구축한다. 실험 결과, 기존 방법들은 사실적 정확 도에서는 비교적 높은 성능을 보이더라도 구조적 평가에서는 여전히 실패하는 경우가 많았으며, 이는 사실적 정확성과 구조적 신뢰성 사이에 유의미한 차이가 존재함을 보여준다. 또한 구조적 검증을 활용 한 재선택（verification-guided reranking）이 설명 품질을 향상시킬 수 있음을 확인하였다. 이러한 결과는 결정적 시스템에서 설명의 신뢰성을 평가하기 위해서는 개별 사실의 정확성만으로는 충분하지 않으며, 이벤트간의관계구조또한함께보존되어야함을보여준다.나아가구조적평가는기존사실기반평가를 보완하는 필수적인 기준이며, 신뢰성 있는 설명 시스템 설계를 위한 중요한 방향을 제시한다. ©2026 이 수 린 ALL RIGHTS RESERVED