(How) Do Large Language Models Understand High-Level Message Sequence Charts?

Technical Summary: Do Large Language Models Understand High-Level Message Sequence Charts?

Problem Definition
Large Language Models (LLMs) are increasingly deployed to automate tasks across the software development life-cycle. However, it remains unclear whether these models consistently respect the formal semantics of the artifacts they process, particularly in the domain of architectural design. This paper investigates this gap using High-Level Message Sequence Charts (HMSCs) as a case study. HMSCs are visual models with rigorous formal semantics, serving as a foundation for Sequence Diagrams in the Unified Modelling Language (UML). The core problem is determining if LLMs can "understand" (i.e., produce outputs consistent with a sound model of) the formal semantics of HMSCs, specifically regarding causal ordering, abstraction, composition, and trace generation.

Methodology
The study employs a controlled benchmark to quantify LLM performance on 129 semantic tasks derived from nine subject models (MSCs and HMSCs) taken from validated software specification lecture notes. The evaluation focuses on three contemporary LLMs: Gemini-3-Pro, GPT-5.4, and Qwen-3.6.

The methodology is structured around five Research Questions (RQs) and five categories of tasks:

1. Event Identification: Recognizing basic syntactic and semantic units (send, receive, internal actions).
2. Causal Ordering: Determining relations between events based on send-receive constraints, vertical instance ordering, and transitive closure.
3. Semantic Transformations: Performing Abstraction (removing events while preserving behavior) and Composition (combining charts via choice, sequence, or parallel operators).
4. Behavioral Semantics: Computing the set of traces (linear extensions of partial orders) and generating equivalent Labelled Transition Systems (LTS).
5. Performance Analysis: Evaluating accuracy stratified by model complexity, task complexity, and specific LLM.

The evaluation pipeline involves prompt design, execution, and manual assessment against reference solutions, with a focus on semantic correctness rather than mere syntactic matching.

Key Contributions

• Semantic Benchmark for HMSCs: The paper introduces a novel benchmark that directly tests LLMs on formal semantic concepts (ordering, traces, LTS) rather than relying on downstream tasks like code completion or equivalence checking.
• Stratified Accuracy Metrics: It provides a granular analysis of LLM performance, distinguishing between basic recognition tasks and complex reasoning tasks.
• Identification of "Pain Patterns": The study systematically identifies specific semantic concepts where LLMs consistently fail, particularly regarding co-regions (regions with no event ordering) and explicit causal dependencies in parallel compositions.
• Observation of Tool-Use Mitigation: The authors note that when LLMs succeed in complex reasoning, they often do so by generating and executing Python code to encode the semantic logic, suggesting a pathway for improving reliability via tool integration.

Results
The study reports an overall accuracy of approximately 52% across all models and tasks, revealing significant variability based on task complexity:

• Basic Semantics (High Performance): LLMs demonstrate strong competence in identifying events and basic causal ordering, achieving ~88% accuracy. Errors here were often visual artifacts (e.g., misinterpreting vertical positioning as causal order).
• Semantic Transformations (Low Performance): Performance drops drastically for abstraction and composition tasks, with an average accuracy of ~36%.
  • Abstraction: Models frequently failed to preserve causal ordering after removing events or introduced arbitrary orders when merging instances.
  • Composition: Models struggled with horizontal composition, incorrectly imposing order on parallel events (failing to utilize co-regions) and misinterpreting vertical composition.
• Behavioral Semantics (Moderate to Low Performance): Accuracy for trace identification was ~42%, while generating equivalent LTSs was even lower (~25%).
• Model Variability: There was no strict monotonic relationship between model "size" or "depth" and performance. Gemini-3 achieved the highest overall accuracy (55.8%), followed by Qwen-3.6 (48.8%) and GPT-5.4 (46.5%). Success in complex tasks was often correlated with the model's ability to generate and execute correct reasoning code.

Significance and Claims
The paper modestly claims to take the "first step" in characterizing the boundaries of LLM capabilities in architectural reasoning. It concludes that while LLMs possess a precise model of basic MSC constructs, they lack a sound notion of co-regions and explicit causal dependencies required for higher-level semantic reasoning.

The authors argue that the current limitations suggest LLMs cannot yet be relied upon for consistent architectural design comprehension without external support. The findings indicate that interfacing LLMs with sound reasoning tools (e.g., executing generated code for trace calculation) is a viable strategy to mitigate these semantic gaps. The study also highlights the need for future work to address the "pain patterns" of partial order reasoning and to expand benchmarks beyond the current dataset to ensure statistical robustness.