# STED and Consistency Scoring: A Framework for Evaluating LLM Structured Output Reliability

arXiv: https://arxiv.org/abs/2512.23712 · HTML: https://mlsanity.com/paper/2512.23712/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 52 references that are in the map.
- First posted on arXiv 27 Nov 2025.

## Builds on (most cited first, 27 of 27)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [SimCSE: Simple Contrastive Learning of Sentence Embeddings](https://mlsanity.com/paper/2104.08821/) (2021)
- [CodeBERT: A Pre-Trained Model for Programming and Natural Languages](https://mlsanity.com/paper/2002.08155/) (2020)
- [GraphCodeBERT: Pre-training Code Representations with Data Flow](https://mlsanity.com/paper/2009.08366/) (2020)
- [Measuring and Improving Consistency in Pretrained Language Models](https://mlsanity.com/paper/2102.01017/) (2021)
- [Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks](https://mlsanity.com/paper/1503.00075/) (2015)
- [The Effect of Sampling Temperature on Problem Solving in Large Language Models](https://mlsanity.com/paper/2402.05201/) (2024)
- [GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph](https://mlsanity.com/paper/2105.02605/) (2021)
- [Non-Determinism of "Deterministic" LLM Settings](https://mlsanity.com/paper/2408.04667/) (2024)
- [Measuring Reliability of Large Language Models through Semantic Consistency](https://mlsanity.com/paper/2211.05853/) (2022)
- [StructEval: Benchmarking LLMs' Capabilities to Generate Structural Outputs](https://mlsanity.com/paper/2505.20139/) (2025)
- [StructuredRAG: JSON Response Formatting with Large Language Models](https://mlsanity.com/paper/2408.11061/) (2024)
- [SLOT: Structuring the Output of Large Language Models](https://mlsanity.com/paper/2505.04016/) (2025)
- [Verifiable Format Control for Large Language Model Generations](https://mlsanity.com/paper/2502.04498/) (2025)
- [Graph Edit Distance with General Costs Using Neural Set Divergence](https://mlsanity.com/paper/2409.17687/) (2024)
- [An Overview of Distance and Similarity Functions for Structured Data](https://mlsanity.com/paper/2002.07420/) (2020)
- [Prompt Stability Matters: Evaluating and Optimizing Auto-Generated Prompt in General-Purpose Systems](https://mlsanity.com/paper/2505.13546/) (2025)
- [Revisiting the tree edit distance and its backtracing: A tutorial](https://mlsanity.com/paper/1805.06869/) (2018)
- [Estimating LLM Consistency: A User Baseline vs Surrogate Metrics](https://mlsanity.com/paper/2505.23799/) (2025)
- [Tree Edit Distance Learning via Adaptive Symbol Embeddings](https://mlsanity.com/paper/1806.05009/) (2018)
- [Automated Consistency Analysis of LLMs](https://mlsanity.com/paper/2502.07036/) (2025)
- [The Online Min-Sum Set Cover Problem](https://mlsanity.com/paper/2003.02161/) (2020)

## Built on by (most cited first, 5 of 5)

- [Can Deep Research Agents Retrieve and Organize? Evaluating the Synthesis Gap with Expert Taxonomies](https://mlsanity.com/paper/2601.12369/) (2026)
- [From Accuracy to Auditability: A Survey of Determinism in Financial AI Systems](https://mlsanity.com/paper/2605.23955/) (2026)
- [Object Aligner: A Configurable JSON Schema Similarity Score for Graphs, Applied to LLM Prompt Optimization](https://mlsanity.com/paper/2607.01972/) (2026)
- [LatentMD: Benchmarking Markdown Boundary Failures in LLM-Generated Text](https://mlsanity.com/paper/2609.06993/) (2026)
- [Constrained Decoding Eliminates Structural Failures in Small LLMs but Reveals a Scale-Dependent Semantic Gap](https://mlsanity.com/paper/2609.23742/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) are increasingly deployed for structured data generation, yet output consistency remains critical for production applications. We introduce a comprehensive framework for evaluating and improving consistency in LLM-generated structured outputs. Our approach combines: (1) STED (Semantic Tree Edit Distance), a novel similarity metric balancing semantic flexibility with structural strictness when comparing JSON outputs, and (2) a consistency scoring framework aggregating multiple STED measurements across repeated generations to quantify reliability. Through systematic experiments on synthetic datasets with controlled schema, expression, and semantic variations, we demonstrate STED achieves superior performance (0.86-0.90 similarity for semantic equivalents, 0.0 for structural breaks) compared to existing metrics including TED, BERTScore, and DeepDiff. Applying our framework to benchmark six LLMs reveals significant variations: Claude-3.7-Sonnet demonstrates exceptional consistency, maintaining near-perfect structural reliability even at high temperatures (T=0.9), while models like Claude-3-Haiku and Nova-Pro exhibit substantial degradation requiring careful tuning. Our framework enables practical applications including targeted model selection for structured tasks, iterative prompt refinement for reproducible results, and diagnostic analysis to identify inconsistency root causes. This work provides theoretical foundations and practical tools for ensuring reliable structured output generation in LLM-based production systems.