acceptodds
Under review as a conference paper at ICLR 2027

EQUINOX: Benchmarking Natural-Language-to-TLA+ Formalisation by Bounded Trace Equivalence

Abstract

A TLA+ specification describes a protocol's behaviour. The distributed computing community uses TLA+ to find protocol defects before deployment. Writing these specifications requires substantial time and expertise, which motivates the use of AI agents. Current natural-language-to-TLA+ benchmarks accept a specification that parses, runs, and satisfies its declared properties. However, a specification can pass all three checks yet describe a different protocol by omitting required behaviour, allowing extra behaviour, or both. We present EQUINOX, a benchmark for protocol formalisation in TLA+. It contains 115 tasks and evaluates each output using bounded trace equivalence. Each task uses a published specification as a hidden reference. EQUINOX compares the behaviours of the agent output and the hidden reference in both directions. We evaluate five agents: Codex + GPT-5.6 Sol, Codex + GPT-5.6 Terra, Claude Code + Opus 5, Claude Code + Sonnet 5, and OpenCode + GLM-5.3. We report three results. First, execution is necessary but not sufficient for successful formalisation. Nontrivial execution accepts 73.0% of the 1723 eligible attempts, but only 24.0% satisfy bounded trace equivalence. Second, the agents solve similar sets of tasks: no agent solves 71 of 115 tasks, while all five agents solve 24 tasks. Third, more attempts rarely resolve modelling errors. Codex + GPT-5.6 Sol solves 1 of 11 selected failed tasks across 110 further attempts. Together, these results show a capability gap for frontier AI agents in protocol formalisation.

Primary area:
datasets and benchmarks
Keywords:
AI agent, formal verification, TLA+

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_bsU3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The current natural-language-to-TLA+ benchmarks may overestimate the correctness of the generated specifications, failing to capture the semantics mismatches between the generated and the reference protocols. So this paper proposes EQUINOX benchmark, which forcus on designing strict criterion for the generated specifications from agents. It applies bounded trace equivalence as the criterion, which will checks if there are ommited behaviours or extra behaviours between the agent output and the reference. The experiments show that 1. the proposed criterion will refuse most samples that could have passed execution checks, 2. the agents show similar distribution of success samples, 3. repeated attempts don't change the failures.

Critical strengths
  1. The paper addresses part of the evaluation correctness problems of the previous execution pass checks
Critical weaknesses
  1. The proposed method of checking the validity is a good improvement over the previous methods, but it still could not provide assurance on the validity. I still don't know how much is the difference between the real pass rate and the current pass rate.
  2. The experiments seems not comparing the proposed check method and the corresponding component of the previous benchmarks. The paper only compares the checks defined by the authors.
Questions for authors
  1. I wonder if the checking methods of current benchmarks are the same as the experimented ones (G1, G2, G3)?
Reviewer_Up9UOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

EQUINOX is a benchmark of 115 natural-language-to-TLA+ formalisation tasks derived from published specifications. Its central evaluation criterion requires bounded behavioural equivalence between a generated specification and a hidden reference, checking both missing and additional behaviours. The paper evaluates five agents with three attempts per task and reports that 73.0% of eligible attempts produce executable, nontrivial specifications, while 24.0% pass the proposed equivalence checks. It also reports overlapping failure sets across agents and limited improvement from additional attempts on selected tasks. The main contribution is the benchmark and its evaluation methodology.

Critical strengths
  • The paper addresses an important evaluation problem. Executability and satisfaction of selected properties do not establish that a generated specification faithfully captures the intended protocol. Evaluating behavioural correspondence between generated specifications and target systems is therefore a worthwhile direction.

  • The benchmark provides useful infrastructure and provenance documentation. The collection spans multiple protocol families and repositories, with pinned source specifications, explicit interfaces, and separation between generation and hidden evaluation. These components could support further research if the validity of the central measurement is established.

Critical weaknesses

The core measurement validity is not established. The evaluator measures agreement with a particular hidden reference under a prescribed interface. However, the paper does not establish that disagreement reliably indicates an incorrect formalisation of the public requirements. This inference requires evidence that the natural-language description and interface sufficiently determine the reference behaviour, and that the evaluation accommodates alternative representations permitted by the task.

Prescribing an interface can be a legitimate task constraint, but interface noncompliance should not automatically be interpreted as a modelling error. Similarly, behavioural differences may arise from underspecified requirements or permissible modelling choices. Appendix A explicitly acknowledges that the study cannot separate prompt insufficiency from agent incapability. This uncertainty directly affects the interpretation of the main experimental results. Although the paper acknowledges this issue, I consider it sufficiently serious to undermine the validity of the measurement itself.

Reference-derived positive controls do not resolve this concern: demonstrating that a rewritten reference passes does not establish that independently developed, correct formulations will be accepted. The paper lacks an independent assessment of rejected outputs, including a systematic analysis of their underlying failure causes, that distinguishes genuine protocol errors from interface incompatibilities and representation issues. Consequently, the reported failure rates, shared failures, and unsuccessful retries do not adequately support the broader capability conclusions. Addressing this issue requires substantive validation and potentially reanalysis of the experimental results.

The comparison with relevant behavioural evaluation work is incomplete, particularly the omission of SysMoBench. SysMoBench already evaluates syntax, runtime behaviour, conformance to system execution traces, and invariant correctness, and explicitly addresses mappings between generated models and system artefacts. It therefore directly bears on both the motivation for behavioural evaluation and the treatment of representational differences.

The two benchmarks have different task settings and acceptance criteria. Nevertheless, the paper should explain these differences and establish the additional value of its approach. Without this comparison, the novelty and practical benefits of the central contribution remain insufficiently substantiated.

Questions for authors
  1. What evidence establishes that the public descriptions and interfaces determine the reference behaviours sufficiently precisely to justify treating failure of either inclusion check as a formalisation error? I do not believe that natural language alone can precisely specify a state machine. Does the present study resolve this issue, and if so, how? How does the evaluator handle alternative specifications that satisfy the public requirements but differ from the reference?

  2. Can the authors provide a sample of rejected submissions independently reviewed by human experts, distinguishing actual violations of public requirements from interface issues, alternative representations, and underspecified requirements? Can the authors estimate the proportion of all failures attributable to each category?

Reviewer_TmbMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

EQUINOX evaluates natural-language-to-TLA+ formalisation using bounded trace equivalence with a hidden reference specification. It introduces 115 tasks derived from published executable specifications and checks whether generated specifications both preserve required behaviour and exclude additional behaviour over a declared observable interface at a finite scope. The authors evaluate five agents with three attempts per task. Pass@3 ranges from 23.5% to 35.7%. Across eligible attempts, 73.0% achieve nontrivial execution, but only 24.0% pass the equivalence criterion. The paper additionally reports substantial overlap in solved tasks and a focused experiment in which 110 additional attempts solve only one of 11 selected failed tasks. Its main contributions are the evaluation framework, the curated benchmark, and the empirical characterisation of agent performance.

Critical strengths

S1. The evaluation addresses a consequential gap between executable specifications and faithful formalisation. Checking both omitted and additional behaviour directly tests agreement with the reference. The large execution–equivalence gap in Section 4.3 demonstrates that successful execution provides weak evidence of faithful formalisation. This makes the framework potentially useful for evaluating systems trained or selected using automated verification feedback.

S2. The benchmark provides a useful foundation for reproducible evaluation. Its tasks span 11 protocol families, derive from published specifications, and retain source provenance and pinned revisions. Separating generation inputs from hidden evaluation data also strengthens the experimental design. These choices give the benchmark practical value as a reusable resource, while the explicit discussion of contamination and finite-scope limitations helps readers interpret its results.

Critical weaknesses

W1. The benchmark does not sufficiently establish that the public descriptions determine the reference behaviour. Appendix A acknowledges that failures may reflect underspecified prompts and reports no expert baseline using only the public inputs. Source-derived positive controls establish that an acceptable submission exists, but do not establish that it can be inferred from the prompt. This is particularly consequential because 71 tasks are unsolved by every agent: the reported failures cannot currently be separated into genuine modelling failures and ambiguities in the benchmark inputs. The results establish low reference agreement, but provide less direct support for the claimed capability gap. For a benchmark paper, this uncertainty substantially weakens the interpretation of its central measurements.

W2. The empirical comparison does not quantify the improvement over stronger existing evaluation procedures. The headline 73.0% versus 24.0% comparison concerns nontrivial execution. However, Section 2.1 describes prior methods that additionally check selected properties or apply mutation-based tests. The paper does not report how those complete acceptance procedures classify the same generated outputs. Consequently, the practical extent to which EQUINOX corrects misleading success estimates from existing evaluators remains unclear. This comparison is consequential because improving evaluation is the paper’s principal contribution.

Questions for authors

Q1: Clarification regarding task validity: Beyond source-to-sentence mappings and curator review, is there evidence that experts given only the public inputs can produce accepted specifications? For representative universally unsolved tasks, can the observed mismatches be traced to requirements explicitly stated in the prompts? This would materially affect my assessment of the capability-gap interpretation.

Q2: Clarification regarding comparative evaluation: Were any outputs evaluated using the full property- and mutation-based acceptance procedures described in Section 2.1? If so, how many outputs accepted by those procedures fail EQUINOX, and what kinds of mismatches remain undetected?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.