Trace Integrity for LLM Data Agents: Auditable Structured Reasoning in Real-World Systems

Answer accuracy gives an incomplete account of reliability for LLM data agents. In structured-data workflows, an agent can return the expected result even when its recorded computation contains an incorrect join, omitted filter, wrong aggregation, unintended grouping, or faulty schema binding. Such accidental successes are especially consequential as data agents are evaluated on larger databases and more complex analytical workflows: BIRD tests database-grounded reasoning across large, heterogeneous databases and domains [1], while Spider~2.0 extends this setting to enterprise workflows with large schemas, multiple SQL dialects, and multi-query analytical tasks [2]. For these systems, a correct result leaves an important reliability question unresolved: does the recorded computation provide auditable evidence that the answer is actually supported? We formalize this property as Trace Integrity, a reliability criterion for whether the computation recorded behind an answer is explicit, executable, schema-valid, operator-faithful, replayable, answer-consistent, and auditable. We operationalize Trace Integrity through an execution contract that binds user intent to schema elements, operator plans, assumptions, executable queries, verification status, and the reported answer. This supports validation that determines structured-data correctness and preserves enough information for independent inspection. We further introduce the Correct Answer / Invalid Trace (CAIT) Rate, which measures the fraction of answer-level successes whose recorded computations fail Trace Integrity checks. CAIT therefore captures a failure that aggregate accuracy cannot reveal: an agent may receive credit for the right result even when the computation recorded behind that result is not valid. We evaluate this framework on 100 stratified BIRD Mini-Dev examples using Claude Haiku~4.5 under three prompting conditions: Direct SQL, Operation Summary + SQL, and Contract-First SQL. Their answer accuracies are 20.0%, 22.0%, and 24.0%, respectively, while Trace Integrity Pass Rates are 39.0%, 43.0%, and 40.0%. The most consequential divergence appears among answers already counted as correct: the corresponding CAIT Rates are: 55.0%, 59.1%, and 45.8%. Across all three conditions, 46-59% of outputs counted as correct by answer-level evaluation are backed by traces that fail explicit computational checks. Result correctness and computational support therefore separate empirically: knowing that an agent reached the expected result does not establish that its recorded computation provides a valid basis for that result. This work complements recent efforts to examine limitations in Text-to-SQL evaluation [3,4]. Trace Integrity addresses a consequential question: whether the computation recorded behind an answer provides auditable support for the success attributed to the agent. By making the correct-answer/invalid-trace quadrant directly measurable, CAIT quantifies how much reliability answer-only evaluation can hide. For LLM data agents used in structured-data workflows, this distinction is important because answer-level correctness can overstate the reliability of the computation supporting the result. Thus, by making accidental correctness measurable, Trace Integrity supports evaluation protocols that assess not only the result returned by an agent, but also whether the computation supporting that result can be replayed and audited.