acceptodds
Under review as a conference paper at ICLR 2027

Runtime Verification of Language Model Agents Under Temporal Input/Output Logic

Abstract

Scalable, reliable, and robust monitoring of an AI agent's compliance with operational policies is central to AI governance. These policies often encode temporal normative constraints, including conditional and contrary-to-duty (CTD) norms that span multiple turns. LLM judges, widely used for evaluating compliance, are unreliable because they lack robust temporal reasoning, may degrade over long contexts, and are prone to conflating grounding with reasoning errors. We introduce a two-stage neurosymbolic pipeline for monitoring compliance of AI agents with norms specified in a novel temporal I/O logic. The first stage uses an LLM to ground each utterance into atomic propositions. The second stage uses Runtime Norm Compliance Monitor (RNCM), a deterministic, automata-theoretic monitor synthesized from temporal I/O specifications to determine compliance. We formalize the syntax of temporal I/O logic and define a graded compliance semantics that quantifies progress along reparation CTD chains. We prove soundness, completeness, and anytime correctness of the procedure, and show that RNCM scales linearly with number of norms. We evaluate the pipeline on -bench retail conversations and find that our method significantly outperformes six open- and closed-weight frontier AI LLM-as-judge baselines. Ablations show that all errors arise from proposition grounding, empirically validating the separation of grounding from reasoning.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
AI agents, LLM-as-a-judge, neuro-symbolic AI, temporal logic, automata, reactive synthesis, runtime verification, formal specification

Reviews

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

AI agents need oversight and guardrails to ensure that they follow operational rules set before them. LLMs typically act as their own judges to ensure compliance, resulting in a litany of issues. This paper proposes to enforce temporal logical constraints instead. The first contribution is the extension of I/O Logic to Temporal I/O logic. This enables policy violations to be tracked and the subsequent rectification steps to be monitored for logical satisfaction across finite logical traces. The second contribution is a compliance monitor that uses the Temporal I/O logic to actually track whether an LLM is following a specific policy. The important empirical results demonstrate that the proposed Temporal I/O monitor outperforms standard LLM judges by 12 points and that the LLM-based grounding has a smaller impact on the monitor than changing the model used for the baseline judges.

Critical strengths

Novelty / Utility - The paper proposes a significant extension of an existing logical framework to temporal logic and provides all formalizations nicely. I believe that such a framework is, as the authors claim, extremely useful for measuring whether a model is actually following a specified policy, and can see this being used in future work on agent guardrails. I believe the proposed monitor proves this point.

Significance - The problem being solved is universally consequential rather than a slight improvement to an existing algorithm.

Critical weaknesses

Clarity - It is not immediately clear to me how RCNM deals with incorrectly extracted or grounded predicates. My understanding is that these would trigger a non-compliance output, which isn't necessarily the underlying system's fault. Is this the approach that RCNM uses? If not, could the authors please clarify. If it is, the approach, is there any way to detect an error on the translation side and report the full trace as defective (or restart it), without penalizing the underlying system.

Questions for authors
  1. Future Work / Significance - This work focuses on finite LTL traces. However, signal and probabilistic logics also exist. Do the authors believe that RNCM is compatible with more complex logics? If so, what changes would be necessary? 3. Clarification / Significance - It is not readily apparent to me why the monitor must use finite traces. What are the limitations of the monitor that require finite traces?
2 comments

Thank you for your feedback and for highlighting the separation of LLM grounding from symbolic reasoning. We address your questions about grounding errors first, followed by your questions about the choice of logic and trace semantics.


It is not immediately clear to me how RCNM deals with incorrectly extracted or grounded predicates. My understanding is that these would trigger a non-compliance output, which isn't necessarily the underlying system's fault. Is this the approach that RCNM uses? If not, could the authors please clarify.

RNCM treats the AP labels it receives as ground truth. Its verdicts are correct under the assumption that grounding is correct (Thms 1-3). When the grounding incorrectly labels a message, the verdict may be incorrect.

The effect of a labeling error on the final trajectory verdict depends on the norm. For a norm ⟨⊤∣◊p⟩\langle \top \mid \Diamond p\rangle, mislabeling the true input word {p}{p}\{p\}\{p\} as {}{p}\{\}\{p\} leaves the verdict unchanged but the time step at which it is discharged changes. For ⟨⊤∣□p⟩\langle \top \mid \Box p\rangle, the same mislabeling flips the verdict to a violation. Conversely, under ⟨⊤∣□p⟩\langle \top \mid \Box p\rangle, mislabeling {}{p}\{\}\{p\} as {p}{p}\{p\}\{p\} masks a true violation.

We measured this sensitivity in Fig. 4b by injecting noise into ground truth (human) labels. RNCM achieved 100% verdict accuracy on the trajectories evaluated using true labels (human annotations). Verdict accuracy decreased as we added noise.

is there any way to detect an error on the translation side and report the full trace as defective (or restart it), without penalizing the underlying system.

Can RNCM detect a grounding error? Assuming that by "translation" you mean grounding natural-language turns into APs, RNCM cannot detect such an error on its own. When RNCM's verdict differs from that of ground-truth (e.g., human annotated), the discrepancy must involve a grounding error (Thms. 1–3). However, the proposed approach would need an auditor to inspect a message and its assigned AP label to check whether the proposition holds for that message. The benefit of our approach lies in the fact that answering the yes-or-no question about a message is typically easier than examining a long, multi-turn trajectory for a policy violation.

Can RNCM flag or restart a trace without penalizing the monitored agent? Since RNCM cannot detect a grounding error by itself, it cannot automatically flag a trajectory as defective or restart monitoring. During post-hoc evaluation, however, we can check an AP label against a ground truth. If the label caused a verdict discrepancy, we can identify any AP labeling errors. A calibrated model such as Jev could support relabeling when confidence is low. We leave confidence-based relabeling to future work.

We will clarify this behavior in the Introduction (after line 95):

RNCM evaluates the AP labels supplied by the grounding stage. An incorrect label can leave the final trajectory verdict unchanged, cause a false violation, or mask a true violation. The monitor cannot independently validate these labels.

Questions

This work focuses on finite LTL traces. However, signal and probabilistic logics also exist. Do the authors believe that RNCM is compatible with more complex logics? If so, what changes would be necessary?

We believe temporal I/O logic could support base logics other than LTLf. Any such logic must provide an efficient way to determine when an obligation is discharged and when it can no longer be discharged at runtime. TIOL uses these events to advance through the reparation chains. We have not explored either extension yet but believe that this could be an interesting future work.

Clarification / Significance - It is not readily apparent to me why the monitor must use finite traces. What are the limitations of the monitor that require finite traces?

We consider finite-trace semantics to model the AI agent conversations, which are often subject to maximum turn limits. This is a common modeling choice in robotics and AI applications. Finite trace semantics introduce technical challenges to handle end-of-trace. For example, a formulas ◊□p\Diamond \Box p and □◊p\Box \Diamond p both reduce to ◊(Last∧p)\Diamond (Last \wedge p) under finite trace semantics, while they have different meanings under infinite trace semantics (see [1]). However, these limitations are broadly understood in the literature.

[1] De Giacomo G, Vardi MY. Linear temporal logic and linear dynamic logic on finite traces. IJCAI, 2013.


Thank you again for your valuable feedback. If our clarifications and additional experiments have addressed your questions and concerns, we'd greatly appreciate your support for the paper being presented at ICLR. Please let us know if you have any remaining questions!

AuthorsOpenReview ↗

Thank you for your feedback

Dear Reviewer,

Thank you again for your thoughtful feedback on our submission. We hope our responses and additional experiments have addressed all of your questions and concerns. If so, we would be grateful for your support of our paper being presented at ICLR.

Sincerely,

The Authors

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

This paper studies whether language model agents comply with policies involving temporal constraints and reparative obligations across multi-turn interactions. It introduces Temporal I/O Logic to represent activation conditions, primary obligations, and contrary-to-duty reparation chains, together with an incremental Runtime Norm Compliance Monitor (RNCM). The pipeline uses an LLM or structural parsing to extract atomic propositions from conversation turns, then applies automata-based monitoring to determine compliance. The paper presents soundness, completeness, and anytime-correctness arguments relative to its formal semantics.

Experiments cover 1,368 conversations from the retail and telecom domains of τ²-bench, evaluated against roughly fifty manually formalized norms. With GPT-4.1 as the proposition sensor, the pipeline reports balanced accuracies of 86% and 91%, compared with 74% and 83% for the strongest respective LLM-as-judge baselines. The method assumes predefined formal specifications; translating natural-language policies into these specifications is performed manually and is outside the automated pipeline.

Critical strengths

Strengths

  • The introduction of Temporal I/O Logic and its integration with automata-based runtime monitoring constitute a concrete technical contribution beyond the general neuro-symbolic decomposition paradigm. In particular, the explicit modeling of contrary-to-duty (CTD) reparation chains, graded compliance semantics, and anytime monitoring provides a structured framework for representing and tracking temporal normative obligations across multi-turn agent interactions.

  • Separating semantic extraction from formal reasoning is a useful direction toward more trustworthy verification of agentic traces. Explicit temporal specifications make compliance decisions easier to inspect and audit than holistic LLM judgments.

  • Manually curated specifications provide a concrete mechanism for incorporating human policy intent and reviewing the rules enforced by the monitor.

Critical weaknesses

Weaknesses

  • The specification bottleneck remains unresolved. All evaluated policies require manual formalization, while facts about agent behavior are extracted automatically. The monitor’s guarantees are therefore conditional on both faithful specifications and correct grounding; they do not establish end-to-end soundness or completeness with respect to the original natural-language policies. The paper does not systematically assess specification fidelity or the human effort required to support new policies, and the methods proposed in the paper share the impreciseness of LLM judges (by definition) and the difficulty to scale up of human judges.

  • The evaluation provides limited evidence of generalization. Although the dataset contains 1,368 conversations, these conversations repeatedly exercise approximately fifty manually formalized norms from only two domains of τ²-bench. This limits the diversity of policies tested and leaves applicability to computer-use agents, personal assistants, and changing user-specific requirements unclear.

  • Comparisons with related neuro-symbolic approaches are insufficient. Relevant methods include FormalJudge (Zhou et al., 2026), Agent-C (Kamath et al., 2025), Solver-Aided Verification of Policy Compliance in Tool-Augmented LLM Agents (Winston et al., 2026), and AgentSpec (Wang et al., 2025). These methods, most of them published more than 6 months before the ICLR deadline (preventing them from being concurrent works of this paper), investigate complementary approaches to specification generation, formal reasoning, and runtime enforcement. Although some are discussed, the experiments primarily compare against LLM judges. Comparisons on compatible policy subsets would help distinguish the benefits of Temporal I/O Logic and CTD handling from those of neuro-symbolic decomposition more generally.

Questions for authors
  1. The experiments primarily use previous-generation closed-source models. Given the rapid recent progress in the formalization capabilities of open-weight models, could the authors explore automating policy formalization with frontier LLMs and reassess the justification for relying on manual formalization?

  2. How were the manually written specifications validated against the original policies? Were they independently reviewed or tested using positive and negative examples, or directly produced by human?

4 comments
AuthorsOpenReview ↗

Response Part 1 / 3

Thank you for your assessment and for supporting the paper's core idea of integrating temporal I/O logic (TIOL) with automata-based runtime monitoring. We group our responses by theme, starting with the specification bottleneck.


Specification bottleneck and automated formalization

The specification bottleneck remains unresolved. All evaluated policies require manual formalization, while facts about agent behavior are extracted automatically.

The experiments primarily use previous-generation closed-source models. Given the rapid recent progress in the formalization capabilities of open-weight models, could the authors explore automating policy formalization with frontier LLMs and reassess the justification for relying on manual formalization?

We deliberately left autoformalization (automatic translation of natural-language policies into formal specifications) outside of the scope of this paper because autoformalization for TIOL is substantially harder problem than that for propositional logic (PL) or LTL.

Logic such as PL or LTL admit Boolean verdicts; a trajectory either satisfies or violates the formula. However, TIOL admits (n+2)(n+2) possible verdicts (Def. 2): undetermined, kk-compliant for k=1,…,nk = 1,\ldots,n, and non-compliant. Hence, autoformalizing a policy into TIOL requires the pipeline to encode the trigger and all nn obligations, and preserve their order.

When we tried using Fable 5.1 to formalize tau2-bench retail policies from Appendix C, we found that nearly 60% of the resulting encodings were incorrect. Most of the incorrect encodings failed to capture semantic meaning of the policy (e.g., using a weak until that cannot be violated when a reparation is possible).

TIOL semantics help explain why encoding semantic meaning correctly can be difficult for LLMs. When formalizing logics with binary verdicts, the synthesized formula must correctly partition the trajectory space Σ∗\Sigma^\ast into satisfying and violating trajectories. For TIOL, the procedure must find (n+1)(n+1) LTLf formulas that jointly map each trajectory to one of (n+2)(n+2) verdicts. Since (n+1)(n+1) LTLf formulas could induce up to 2(n+1)2^{(n+1)} partitions of Σ∗\Sigma^*, encoding a correct semantic meaning requires additional logical reasoning, which could be challenging for a general-purpose LLM.

Therefore, we focus this paper to introduce TIOL, define its syntax and semantics, and evaluate its practical value for runtime monitoring. The error rate in this preliminary trial reinforces our decision to use manually formalized and reviewed specifications for this evaluation. We plan to pursue autoformalization for TIOL in follow-up work.

AuthorsOpenReview ↗

Response Part 2 / 3

Specification fidelity, validation, and human effort

The paper does not systematically assess specification fidelity or the human effort required to support new policies, and the methods proposed in the paper share the impreciseness of LLM judges (by definition) and the difficulty to scale up of human judges.

How were the manually written specifications validated against the original policies? Were they independently reviewed or tested using positive and negative examples, or directly produced by human?

Process and validation. One author with about 10 years of experience in formal logic encoded each natural-language policy in TIOL. Two other authors reviewed the resulting automata using both positive and negative examples using an automaton, checking whether the verdicts agreed with the original policies. We resolved disagreements through discussion and revised the encodings until we no longer observed undesirable behavior in the automaton. In a separate check, human annotators (three authors) assigned compliance verdicts to approximately 300 traces by reading the original natural-language policies. They assigned those verdicts independently of RNCM. We then compared the human and RNCM verdicts trace by trace. We will describe these checks in the revised experimental setup.

We describe this process and validation process in the revised experimental setup.

We encoded each policy in TIOL and reviewed the encoded formula using positive and negative examples and checked whether the verdicts agreed with the original policy. We resolved discrepancies through discussion and revised the encodings accordingly. In a separate check, we assigned compliance verdicts to approximately 300 traces by reading the original natural-language policies, independently of RNCM. We compared the human and RNCM verdicts trace by trace. Manual encoding took approximately six hours per policy.

Effort. The evaluation uses two tau2-bench policies, formalized as 38 retail norms and 18 telecom norms (Appendices C and D). The manual encoding took about six hours per policy. Once the policy is fixed and its atomic proposition (AP) labelers are configured, AP labeling and RNCM monitoring are fully automated, with all uncertainty isolated to the AP-labels that use LLMs for labeling APs labeled by LLMs. No further human effort is necessary.

Imprecision. Our approach uses LLMs to answer simple, binary questions about APs in individual messages, whenever the AP label cannot be assigned deterministically. RNCM uses the resulting labels to determine policy compliance across the conversation. In contrast, an LLM judge assigning a compliance verdict to a full conversation must identify the relevant events, determine their order, and assess compliance with a potentially ambiguous natural-language policy. LLMs are known to struggle with this task, as demonstrated by CompliBench [1]. Our method gives the LLM one yes-or-no question about one message at a time, a task for which LLMs have demonstrated advantages.

That said, AP labeling can still be difficult. An explicit request to cancel an order is easier to identify than an expression of dissatisfaction that must be inferred from context. Prior work reports strong performance from prompted LLMs on several binary text annotation tasks [2] and finds that supervised fine-tuning can improve annotation performance, with gains that vary by model and task [3]. Note that we have not evaluated fine-tuning approaches for AP labeling in this paper.

Structured events such as tool calls can be labeled deterministically. On the norms that rely exclusively on deterministic labelers, RNCM achieved 100% balanced accuracy in both retail and telecom (Fig. 4b). Given correct AP labels, RNCM returns the verdict prescribed by the TIOL specification (Thm. 2). Agreement with the original policy also requires a faithful specification. The end-to-end LLM judges in our evaluation produce verdicts directly from the conversation and policy. RNCM's formal guarantee applies to its symbolic monitoring stage.

References:

[1] J. Yang et al., “CompliBench: Benchmarking LLM Judges for Compliance Violation Detection in Dialogue Systems,” arXiv:2604.12312, 2026.

[2] Fields J, Chovanec K, Madiraju P. A survey of text classification with transformers: How wide? how large? how long? how accurate? how expensive? how safe?. Ieee Access. 2024 Jan 4;12:6518-31.

[3] Wang Z, Lin Y, Shen J, Zhu X. “A Survey of Large Language Models for Text Classification: What, Why, When, Where, and How,” TechRxiv preprint, 2025

AuthorsOpenReview ↗

Response Part 3 / 3

Generalization

The evaluation provides limited evidence of generalization. Although the dataset contains 1,368 conversations, these conversations repeatedly exercise approximately fifty manually formalized norms from only two domains of τ²-bench. This limits the diversity of policies tested and leaves applicability to computer-use agents, personal assistants, and changing user-specific requirements unclear.

We believe the experiments provide strong evidence of generalization, and the theoretical and empirical results support different aspects of that claim.

First, the correctness guarantee is general; it doesn't depend on specific domain. Given correct AP labels, RNCM returns the verdict prescribed by the TIOL norm for the trace (Thm. 2). Hence, the generalizability of our approach reduces to checking generality of LLM-as-classifier AP labeling.

Prior work on LLMs as binary classifiers [1, 2] has established strong binary classification performance for frontier models and near-perfect accuracy after fine-tuning on domain-specific data. We test these properties in two tau2 domains with different vocabularies (AP sets) using LLMs. We observe over 90% AP-labeling accuracy and that any improvement in AP-labeling accuracy translates directly into higher monitor verdict accuracy (Fig. 4b).

Because the theoretical guarantees and the binary classification properties of LLMs apply across domains, we believe our results provide strong evidence of generalization.

References:

[1] J. Yang et al., “CompliBench: Benchmarking LLM Judges for Compliance Violation Detection in Dialogue Systems,” arXiv:2604.12312, 2026.

[2] Fields J, Chovanec K, Madiraju P. A survey of text classification with transformers: How wide? how large? how long? how accurate? how expensive? how safe?. Ieee Access. 2024 Jan 4;12:6518-31.

[3] Wang Z, Lin Y, Shen J, Zhu X. “A Survey of Large Language Models for Text Classification: What, Why, When, Where, and How,” TechRxiv preprint, 2025


Thank you again for your valuable feedback. If our clarifications and additional experiments have addressed your questions and concerns, we'd greatly appreciate your support for the paper being presented at ICLR. Please let us know if you have any remaining questions!

AuthorsOpenReview ↗

Thank you for your feedback

Dear Reviewer,

Thank you again for your thoughtful feedback on our submission. We hope our responses and additional experiments have addressed all of your questions and concerns. If so, we would be grateful for your support of our paper being presented at ICLR.

Sincerely,

The Authors

Reviewer_XdcUOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors tackle the problem of reliability of using LLMs as judges of agent compliance. They introduce a new logic, temporal I/O logic where each rule takes the form,”if A occurs, do B and if B can’t be done, do C instead”. They decide satisfiability (sat) if one of the obligations is guaranteed to be met and unsatisfiability (unsat) once all the fallbacks have failed or can’t be met. The authors also introduce a new runtime monitoring scheme for monitoring LLM agents with this new logic. Their validation involves using LLMs to simulate conversations and then having human annotators mark which propositions hold at each point in the conversation and then using the monitor to determine satisfiability or violations against these labels. They then judge their method against LLMs judging the whole conversation directly.

Critical strengths
  1. The paper’s method allows really easy auditability. Usually, when an LLM-as-judge decides, it’s quite opaque and we can’t really know why it decided either way. The method proposed in the paper allows you to know whether the decision came from the per-turn labels or the monitor and so, when a verdict is wrong, you can identify the specific turn and proposition that led to the verdict. This is important to my assessment because most non-formal methods emphasise evaluation or training methods to get better LLM judge performance but this doesn't make the decisions any auditable.
  2. The method has consistent empirical gains over LLM judges. This is important to my assessment because it shows that the RCNM method works and provides advantages over various LLMs.
Critical weaknesses
  1. The main problem the paper identifies in the introduction is mostly not solved. On lines 039-041, the authors question,”How can we enable principled, auditable, scalable, and provably-reliable oversight for AI agents that allows formal verification of an agent’s compliance with a policy specification over multi-turn interactions?”. But then the authors work on an easier problem by checking hand-written LTL formulas against conversation traces whose atomic propositions have already been labelled. Solving the main problem raised in the introduction would require reliable translation of natural language policies into formal specifications and translating agent actions and behaviour into atomic propositions that can checked. This is the open problem and the paper sidesteps this by translating natural language policies manually and determining the atomic propositions at each step with LLMs that can’t be formally verified. I think that in real-life monitoring circumstances, the proposed method could not be used without extensive human annotation. This is important to my review because the paper opens by motivating a really interesting and consequential problem and then solves a simpler one by ignoring the main research that the problem needs.
  2. The values of the atomic propositions are determined by checking the logs but this hides a lot of the information that should be used in determining the value of a proposition. For example, if files or arguments follow the wrong order and if there’s some hidden state, these all may lead to incorrectly assigning a truth value to the AP. Furthermore, if we consider realistic agents that edit files or run code, these agents maintain multiple, complex states simultaneously and cannot be checked this way. This is important to my assessment because the application of this method relies on its ability to monitor complex agentic behaviour but many of the actions available to agents that give rise to complex behaviours are not considered.
  3. The evaluation is unrealistic in some parts. The evaluation is on LLM-simulated conversations and this doesn’t give any indication of real agentic behaviour. The neat single-turn nature of these conversations doesn’t give any indication as to how the method would behave in more realistic environments where tracking the APs would require more thoughtfulness.
Questions for authors
  1. Where does your ground-truth results come from? In Sect. 6, you mentioned that the per-turn propositions were labelled but not how the ground-truth compliance verdicts were produced.
  2. Could you run an ablation or could you just tell me how much of the gain comes from your logic? 44/58 of the norms have no fallback so these are just LTL formulas and thus, the problem reduces to LTL monitoring. Did you try using an LTL monitor? How about an LLM as a judge given the formulas and the labels? I know corrective action is a big part of your logic but these can be encoded in LTL just fine so is there a reason why temporal I/O logic is needed and why LTL can’t be used?
5 comments
AuthorsOpenReview ↗

Response Part 1 / 4

We appreciate your thoughtful review. We are glad that you found the core idea, of using LLMs for grounding natural language to atomic propositions (APs) and using temporal I/O logic (TIOL) to reason over normative temporal properties, promising and well-motivated. We also appreciated you highlighting the auditability and empirical gains that result from separation of neural and symbolic processing.

We start with a summary responses to a few key high-level concerns and then include detailed responses to specific comments.


Summary Responses

Autoformalization is a necessary for runtime monitoring of AI agents, but it is missing from the paper.

In this paper, we assume that the policy already formalized in TIOL. Automatically translating a natural-language policy into TIOL introduces new challenges, not observed when formalizing binary-verdict logics such as propositional logic and LTL. A key challenge here is that TIOL autoformalization requires extracting a trigger and an nn-obligation chain, whose order must be also be recovered accurately. For instance, in a preliminary trial with Fable 5.1 (high) on the tau2-bench retail policies, we observed almost 60% of the autoformalized TIOL formulas had semantic errors. Hence, we see reliable autoformalization for TIOL as a separate research question. We have made this assumption explicit in revised introduction.

Proposed approach is not scalable because it requires human-labeled APs.

There appears to be a misunderstanding. Human-labeled APs are not needed. More specifically, once a policy has been formalized and AP labelers configured (regex and LLM-as-judge --- neither of which requires human labeling), RNCM can monitor new conversations under that policy without further human annotation. The proposed method labels each turn using deterministic rules (regex) or LLM judges, and RNCM updates the verdict incrementally from those labels. In the paper, we used human-labeled APs only to obtain reference ground-truth verdicts for evaluating the effectiveness of the proposed approach. Manual formalization is an upfront cost per policy. We estimate it took about six hours per policy in our evaluation, and we agree that autoformalization is an important component of future end-to-end pipelines.

TIOL seems to be an ordered tuple of LTLf. What value does it add? What if LLM-as-judge is provided AP labels and TIOL formula?

TIOL can be viewed as an ordered tuple of (n+1)(n+1) LTLf formulae. However, through its semantics, it gives this tuple a concrete meaning aligned with a normative interpretation. When the trigger is met, the monitor checks the primary obligation. If the trace establishes that this obligation has been violated, the monitor moves to the next obligation in the reparation chain. The verdict records which obligation the agent ultimately discharged, if any. For example, issuing a required refund before deadline and sending it after the deadline yield different verdicts. This interpretation reduces the number of partitions of Σ∗\Sigma^*, the space of all possible trajectories, induced by the tuple of (n+1)(n+1) LTLf formulas from 2(n+1)2^{(n+1)} to (n+2)(n + 2).

Following your suggestion, we conducted an ablation study to investigate the marginal impact of the policy, the formula, and the AP-labeled conversation history. RNCM outperformed the judges by 16-22 percentage points when they received the natural-language policy alone, 15-24 points when they also received the TIOL formula, and 6-23 points when they received the policy, formula, and AP-labeled conversation history. We report the results by model below. We believe this is strong evidence in favor of TIOL.


Next, we briefly address three potential misinterpretations in your summary of our paper, and then address your concerns point-by-point.

AuthorsOpenReview ↗

Response Part 2 / 4

Clarifications on the review summary

They introduce a new logic, temporal I/O logic where each rule takes the form, "if A occurs, do B and if B can’t be done, do C instead". They decide satisfiability (sat) if one of the obligations is guaranteed to be met and unsatisfiability (unsat) once all the fallbacks have failed or can’t be met.

A TIOL formula admits up to (n+2)(n+2) verdicts, not just sat and unsat. If the trace is yet to satisfy the trigger condition, compliance is undetermined. Once the norm is triggered, a trace is kk-compliant if it violates the first (k−1)(k-1) obligations and satisfies the kk-th obligation. A trace is non-compliant if the norm is triggered and the trace violates all nn obligations.

Their validation involves using LLMs to simulate conversations and then having human annotators mark which propositions hold at each point in the conversation and then using the monitor to determine satisfiability or violations against these labels. They then judge their method against LLMs judging the whole conversation directly.

We use human annotations only to derive reference ground-truth verdicts for evaluating our proposed approach. At runtime, we automatically assign truth values to APs for each message. We use a regular expression to detect a fixed patterns in messages (e.g., tool calls) or an LLM-as-binary-classifier to evaluate propositions requiring natural language interpretation such as the user requested an order cancellation. RNCM uses the resulting labels to update its verdict.

To evaluate the proposed approach, we compare the RNCM's verdict against the ground-truth. We run RNCM on the human-annotated AP labels to derive a reference verdict, then compare it with the verdict RNCM produces from our grounding module. The former process yields ground-truth verdicts for each conversation because Thm. 2 provides a theoretical guarantee that RNCM returns correct verdict when the input AP labels are correct.

The method proposed in the paper allows you to know whether the decision came from the per-turn labels or the monitor and so, when a verdict is wrong, you can identify the specific turn and proposition that led to the verdict.

Given a fixed TIOL specification, Thm. 2 guarantees that RNCM determines the correct verdict when the AP labels are correct (empirically validated in Fig. 4b). Therefore, an incorrect verdict, which is determined by independent evaluation of trajectory (say, via human annotation), implies that at least one AP label is incorrect. Identifying the affected turn and proposition requires a separate check; our method does not point to specific message whose AP-label is incorrect.

The benefit separating neural and symbolic components is that investigating an error becomes manageable. Answering a yes/no question about a single message is a relatively easier and distributable task as compared to investigating how an opaque judge arrived at its verdict for the conversation as a whole.

AuthorsOpenReview ↗

Response 3 / 4

Comments

The main problem the paper identifies in the introduction is mostly not solved. [...] the authors work on an easier problem by checking hand-written LTL formulas against conversation traces whose atomic propositions have already been labelled. Solving the main problem raised in the introduction would require reliable translation of natural language policies into formal specifications and translating agent actions and behaviour into atomic propositions that can checked. This is the open problem and the paper sidesteps this by translating natural language policies manually and determining the atomic propositions at each step with LLMs that can’t be formally verified.

You're right that the question in lines 39-41 could be misinterpreted as the problem we solve in the paper. Our intent was to use it to motivate our work. For reasons stated in summary section, our starting point in this paper is that a policy is already formalized in TIOL. We have clarified this scope in the introduction:

These limitations motivate a broader question: How can we enable principled, auditable, scalable, and provably-reliable oversight for AI agents that allows formal verification of an agent’s compliance with a policy specification over multi-turn interactions? 

We study one part of this broader problem: monitoring an agent’s compliance over a multi-turn interaction given a policy already formalized in temporal input/output logic (TIOL). Our pipeline automatically labels each turn with atomic propositions (APs) and uses those labels to update the compliance verdict. In our evaluation, we formalize the policies manually.

For example, consider the policy: after a user requests account deletion, ...

Does your approach translate agent actions and behaviour into atomic propositions that can checked?

The proposed approach automatically labels each message using deterministic rules for recognizable patterns and LLM-as-binary-classifier for propositions requiring natural language understanding. It's generally possible to automate checking correctness of a deterministic labeler. However, for APs that we label with an LLM, we typically need comparison against human annotations or another independent source of ground truth.

The formal guarantees in the paper applies to the monitoring step. Given correct AP labels, RNCM returns the correct verdict under the TIOL specification. For a fixed specification, separating labeling from reasoning lets us inspect the AP labels when investigating an incorrect verdict, which must be detected independently, say, via human annotation. However, for norms depending only on deterministic AP labelers, this sepration completely eliminates LLM-related uncertainty from the verdict.

I think that in real-life monitoring circumstances, the proposed method could not be used without extensive human annotation.

As noted above, no human labeling is needed. Once we formalize the policy and configure the labelers, monitoring new traces under that policy requires no human annotation. Human annotation is required only for evaluation of the performance of our method.

The values of the atomic propositions are determined by checking the logs but this hides a lot of the information [...] if files or arguments follow the wrong order and if there's some hidden state, these all may lead to incorrectly assigning a truth value to the AP. Furthermore, [...] agents that edit files or run code [...] maintain multiple, complex states simultaneously and cannot be checked this way.

We agree that the contents and ordering of the logs matter. We assume that the logs contain enough information to evaluate every AP used by the norm. We will make this assumption explicit in Sect. 6, immediately after the description of how we ground APs:

... LLM-sensor norms contain LLM-sensor APs, which require LLM-based binary classification of natural-language turns (retail: 26 norms, 545 traces; telecom: 10, 404). We assume that the logged trace contains the information needed to evaluate every AP used by the norm and preserves the event order relevant to that norm. 

We score each retail trace on the norm it was built to exercise and each telecom trace on all 18 norms, ...

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.