acceptodds
Under review as a conference paper at ICLR 2027

An Attention Mechanism for Probabilistic Zero-Shot Monitoring of Formal Languages

Abstract

The deployment of autonomous systems raises the question of how safety-relevant properties can be assured at runtime. This is a challenging task for vision-based systems, in which safety-relevant quantities must be inferred from raw sensor data; the need for suitable solutions to this problem is reinforced by the increasing use of end-to-end policies, such as VLAs. We seek a monitor that a user can prompt with any property expressed in a formal language (a machine-interpretable specification language) and that predicts its satisfaction probability from the observation history zero-shot, i.e., without training on the specific property. We cast monitoring as attention over potential futures: the property acts as a mask over candidate futures in the chosen language, whilst a predictive state representation captures the probabilities of a fixed set of short candidate futures given the observation history. Via a linear decoder, attention over these short futures collapses into one fixed weight vector compiled from the property's syntax. Hence, one learned representation serves any property without property-specific data or training. Whilst the number of potential futures grows exponentially in the time horizon of the property, our monitor only evaluates an inner product at runtime at a cost independent of the horizon. Lastly, we compute calibrated error bounds for learned predictive state representations; a new property needs no new data or model training, only recalibration on stored calibration labels. We validate the zero-shot capabilities of our monitor on driving data spanning agent tracks, rendered bird's-eye views, and raw camera frames. We attain to % of the predictive skill of reference monitors which are trained separately for each property, answering each frame as it arrives at to times lower cost than a sampled autoregressive baseline.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Predictive State Representations, Zero-Shot Learning, Temporal Logic, Runtime Monitoring, Probabilistic Prediction

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_VPiqOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces a novel mechanism for monitoring formally specified properties in partially observable stochastic systems. The approach is zero-shot: it learns a general representation that can be used to monitor any property at test time without retraining. Instead of predicting full future state sequences, the method predicts only the probability of future words, and employs a factorised representation to circumvent the exponential complexity. This factorisation relies on a linearity assumption of the word probabilities. Given a new specification at test time, the proposed method uses formula progression to precompile a single vector representation thereof (based on the bounded formula horizon), which is then combined linearly with the learned observation history representation to predict the satisfaction probability. Finally, the paper employs histogram binning to provide a PAC-style certificate for the satisfaction probability.

Critical strengths
  • The paper proposes an interesting method for a well-motivated problem with applicability in a variety of domains.
  • The problem statement and the desirability of fixed-size, reusable representations is clearly developed and motivated.
  • Using future words as tests is a natural idea that greatly simplifies the monitoring problem. The authors acknowledge the exponential complexity of this approach in general, and propose a scalable factorisation technique to circumvent this.
  • The experiments demonstrate that the proposed method retains much of the performance of the per-property reference, while being general and applicable to arbitrary properties without further training. Compared to sampling-based approaches, the method only needs to compute a single dot product for decoding, leading to much faster inference at some performance cost.
Critical weaknesses
  • The assumption of linearity (i.e. the span assumption) seems somewhat strong and is not adequately discussed in the main text. When can this reasonably be assumed to hold in practice? If the assumption does not hold, does the proposed method still recover some approximate solution? This is especially relevant since the approach relies on factorising "all the way" to single letters. Some further analysis or discussion of this assumption would strengthen the paper.
  • The main advantage of the proposed factorisation is to circumvent the exponential complexity in the formula horizon. However, as the authors acknowledge in Section 5.1, the long-horizon accuracy of the factorisation significantly degrades due to errors accumulating. Some more systematic analysis of the prediction accuracy w.r.t. formula horizon, and the impact of factorisation for formulae with small horizon would be interesting.
  • The exposition reads a bit dense (although this might be because I'm not too familiar with the topic). Would it be possible to describe the factorisation more intuitively, and potentially include an example? Similarly, I found the architecture overview in the appendix quite helpful and encourage the authors to include this in the main paper. A real-world example of an STL specification and how monitoring it is useful could also help to make the background section easier to understand.
  • The certification procedure seems somewhat tacked on and separate from the main proposed method. As far as I can tell, this generally certifies the satisfaction of a formula based just on the trajectories - independent of the predictive state representation - and mainly consists in applying the histogram binning bounds from Gupta et al.
  • While the paper demonstrates the methods on three different experiments, they all stem from the same domain of vehicle driving. This is representative and includes real-world data (the Perception dataset), but experiments on further domain would make the paper stronger. It would also be appreciated if the authors could report standard deviations or confidence intervals, especially for the timing experiments.
  • To add to the above, the authors filter out candidate properties from the experiments based on how well the baseline per-property reference performs compared to a constant baseline. While this seems sensible, it leads to only 4 properties remaining for the Perception benchmark, which is the only benchmark where the proposed method outperforms the RNN and AR-64. Could this be due to the structure of these properties? Can the authors report the numbers for the full set of properties?
Questions for authors
  • Can you provide numbers for the full set of properties for the Perception benchmark?
  • Can you provide a systematic analysis of the scaling behaviour of the proposed method?
3 comments
AuthorsOpenReview ↗

Reply to Reviewer VPiq

We thank the reviewer for the detailed feedback and for recognizing the submission's strengths and potential.

Span assumption and factorization (W1, W2). As explained in the general comment (point 1), Assumption 1 is needed only for exact decoding (Theorem 1). Otherwise, the monitor approximates the satisfaction probability (Sec. 4.1), and the certificate remains valid (Proposition 1). Factorizing down to single letters has little accuracy cost at short horizons, with skill relative to the reference of 0.99 at H=5H = 5 (App. I.2). We now quantify the long-horizon loss, including the contribution from lost probability mass (Sec. 5 and App. I.2). Beyond making runtime independent of HH, factorization allows compilation at any horizon without enlarging the core-test set or retraining.

Exposition (W3). We followed the reviewer's suggestions. The extra page allowed us to move the architecture overview into Section 4. Section 2.2 now illustrates the setting with a benchmark property for sustained tailgating, □[0,36]◊[0,3]ph\square_{[0,36]}\lozenge_{[0,3]}p_h. It requires the headway to the vehicle ahead to recover to at least two seconds at least once in every four consecutive timesteps over the next 40 steps.

Certification (W4). The certificate is necessary for the monitor's correctness, rather than an optional addition. Predictions are exact when Assumption 1 holds and the predictive state and operators are known exactly. Both are estimated from finite data, so a raw prediction for a new property has estimation error of unknown size. The certificate bounds the bin-conditional satisfaction probability of each property, separately, regardless of that error, providing the guarantee needed for safety decisions. We use the histogram binning of Gupta et al. without modification and do not claim a new calibration method. Its independence from the representation is deliberate, so its guarantee does not depend on Assumption 1. Applicability to other monitors does not remove the need to certify ours. For zero-shot monitoring, a new property requires no new trajectories, inference, or training for recalibration, only stored labels (0.15–1.4 ms).

Domain and uncertainty (W5). Our limitations acknowledge that the evidence covers one application domain. Driving is nevertheless a demanding test case that is representative of real-world challenges in other domains. The datasets are real, and the scenes involve complex multi-agent interactions, with the monitored vehicle's future depending on many other road users. The three benchmarks span the perception stack, from agent tracks through bird's-eye-view renderings to raw camera frames. The revision adds seed standard deviations to Table 1 and interquartile ranges to all timings.

Perception properties (W6, Q1). Table 3 lists every candidate property, and the revision adds every monitor's Brier score for the excluded properties (general comment, point 2). Our advantage over the RNN and AR-64 persists across all 33 candidate Perception properties with both outcomes on the test split: our mean test Brier score is 0.0750, compared with 0.0778 for the RNN and 0.0851 for AR-64. Most were excluded because the frozen DINOv2 features carry little information about them. Training a dedicated encoder requires more vision data and compute than we had.

Scaling (Q2). Online cost is independent of the horizon and grows only slightly with the number of properties (Appendices I.2 and I.3). Exponential scaling arises only with the number of propositions.

  • Horizon: compiling a formula is done once, offline, in time linear in HH for a given automaton width. The general comment reports accuracy as a function of HH.
  • Number of properties: at 100 properties, our per-frame cost is 25–73 µs, against 5.6–6.2 ms for AR-64 and 28–35 ms for per-property RNNs (GPU, all three benchmarks).
  • Number of propositions: the number of letters, 2∣AP∣2^{|AP|}, grows exponentially with ∣AP∣|AP|, as for any automaton over APAP. Up to 5 propositions, accuracy on the paper's properties stays nearly constant, compiling one property takes 1.6 to 1.9 times longer per added proposition, and per-frame cost stays at 28 to 30 µs up to 32 letters (see our reply to Rpka).

Thank you for the detailed rebuttal. I appreciate the updates to the paper, especially regarding exposition, the span assumption, and the additional results.

Certification. I agree that the certificate is useful within the framework. However, it remains a generic component that can be applied to other methods, and there is little novelty in it. Further, it is limited to a fixed property and may be uninformative in practice.

Domain. I appreciate that driving is a demanding domain with complex scenes. I still think that at least one further, potentially significantly different, domain would strengthen the paper.

While these issues remain, I think the rebuttal has improved the paper, and I have hence decided to update my score to 3.

AuthorsOpenReview ↗

Additional Intensive Care Benchmark

We thank the reviewer for the reassessment and the increased score.

To address their request for a substantially different domain, we ran our monitor on intensive care data, where monitoring anticipates health deterioration that calls for clinical attention. We split data by patient, so the test patients are unseen. The monitor is trained across patients and conditions each prediction on the current patient's history. As in the paper, we compare our zero-shot monitor with a reference trained separately for each property.

We use the PhysioNet/CinC Challenge 2019 data of 40,336 ICU patients (one time step = one hour). The observations are vital signs, laboratory values, and demographics. The atomic propositions include tachycardia (heart rate above 100 beats per minute), hypotension, and fever. We monitor properties over horizons of 3, 6, and 12 hours, e.g., "hypotension within 6 h", "sustained hypotension within 12 h", and "no hypotension until fever". Over three random patient splits, our monitor reaches 95% of the reference's skill (0.951 ± 0.004), with AUROC 0.872 against 0.881:

horizon3 h6 h12 h
skill relative to the reference0.9970.9720.899
Reviewer_J5ULOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a zero-shot monitoring framework for predicting the satisfaction probabilities of STL specifications under partial observability. The key idea is to learn a shared predictive state representation (PSR) that captures the probabilities of short future label sequences, and then compile a given STL formula into a linear decoder. This allows the monitor to handle new formulas without retraining the predictive model. The authors also use histogram-based calibration to provide distribution-free lower bounds on the average satisfaction probability within prediction bins.

The method is evaluated on three driving datasets with different observation modalities, including agent tracks, BEV images, and camera frames. The results show reasonably good prediction accuracy compared to property-specific monitors, with much lower inference cost than an autoregressive sampling baseline.

Critical strengths

Learning a single predictive representation and then using the structure of STL formulas to obtain different monitors is a neat way to connect formal methods with data-driven prediction. The separation between the learned representation and the formula-dependent decoder is particularly appealing. I also find the constant-cost online readout interesting, since the monitoring cost can otherwise become quite expensive for long-horizon specifications.

The paper is generally well written, and I appreciate that the authors provide a fairly detailed theoretical treatment rather than just presenting another neural monitoring architecture. The experiments are also reasonably thorough, with several relevant baselines and different types of observations.

Critical weaknesses

My main concern is about how well the assumptions behind the PSR construction hold in practice. The theoretical result relies on Assumption 1, which requires the core tests to span predictions over extended histories. However, as the authors mention in Section 4.1, the learned operators are only identified from observation-history states, and these may not span the extended-history states needed for operator composition. I am not sure how much of a problem this causes in practice, especially when the operators are repeatedly composed to predict longer sequences. It would be good to understand this gap better.

I also wonder about the choice of the core-test length L. The experiments mainly use L = 2, but it is not clear how one should choose L for a new system, or whether there is a practical way to check how well Assumption 1 is satisfied. The long-horizon results make this question more important. For some properties, the prediction accuracy drops quite noticeably as the horizon increases. I understand that the online computational cost does not depend on the horizon, which is a nice property of the method, but the accuracy of long-horizon predictions is another matter. I would have liked to see more analysis of how L, the compression rank, and operator composition affect the results.

My other concern is about the practical advantage of the zero-shot approach. I was a little surprised by how strong the per-property reference is in Table 1. It generally achieves better Brier scores and faster inference, and fitting it for a new property only takes around 0.3–1.8 ms. This is already quite cheap. Of course, not having to fit a new model is still an attractive feature, especially if many properties need to be monitored. But I think the paper should make this advantage clearer. For example, how does the total cost compare when monitoring tens or hundreds of properties? Also, the reported new-property adaptation time seems to focus on compiling the decoder, while a new property still requires recalibration to obtain the certificate. I would be interested in the complete adaptation cost.

Finally, I am not entirely convinced by how representative the reported zero-shot accuracy is. The property filtering criteria are reasonable for computing the skill metric, and I appreciate that the authors report the excluded properties in the appendix. Still, only 4 out of 35 candidate properties are retained for the Perception benchmark. Since one of the motivations is monitoring safety-related properties specified by users, I think it is important to understand what happens for properties that are rare or difficult to predict. The additional experiments help, but I would prefer a more direct evaluation on the full candidate set.

Questions for authors
  1. How should the core-test length L be chosen in practice? Is there any way to check whether Assumption 1 is approximately satisfied for a given system? It would be helpful to see results with different values of L, especially for longer-horizon formulas.

  2. I am a bit unclear about the estimation of the letter operators. Since they are learned from observation-history states but later composed over extended histories, what makes this estimation reliable? Have the authors looked at how the errors accumulate when predicting longer label sequences? Some direct comparison between predicted and empirical multi-step sequence probabilities would be useful.

  3. Does the learned decoder preserve basic probability relationships between logically related formulas? For example, ideally the predictions for φ and ¬φ should sum to one, and logically equivalent formulas should give the same probability. Since the operators are learned through regression and the final predictions are clipped, I wonder whether such inconsistencies occur in practice. This seems worth checking for a monitor designed to handle arbitrary formulas.

  4. Could the authors clarify the advantage over the per-property reference when many properties are monitored? Its accuracy and inference time are already quite competitive, and adapting it to a new property appears inexpensive. A comparison of the overall computation and storage costs for a larger number of properties would help. I would also like to know the complete adaptation time when recalibration is included.

  5. Could the authors report more results on the properties excluded by the validation gate? I understand why these properties are not used to compute the average skill, but their Brier scores and calibration results would still be informative. In particular, I would like to know how well the method works for rare safety events and more difficult formulas.

5 comments
AuthorsOpenReview ↗

Reply to Reviewer J5UL (1/2)

We thank the reviewer for the detailed review and for recognizing the paper's value. We address weakness W1 and the Perception part of W4 in the general comment to all reviewers.

Selecting LL, rr, and the factorization (W2, Q1). We fixed L=2L = 2 after preliminary comparisons. Assumption 1 can be checked from data before deployment by regressing the length-(L+1)(L{+}1) word indicators on the predictive state and, separately, on the full history feature ξ\xi. If the predictive state retains nearly all of the improvement over the constant predictor, the span condition holds approximately. For a new system, LL can then be chosen, e.g., as the smallest value for which the predictive state retains nearly all of this improvement. At L=2L = 2, it retains 98 to 99.7% (general comment, point 1). The new ablation of LL and rank in Appendix I.1 shows that LL has little effect up to H=20H = 20: at rank 8, mean test Brier changes by at most 0.0006 between L=1L = 1, 2, and 3 on WOMD and Waymo BEV, and by 0.005 on Perception, which is within its seed spread. At H=40H = 40, the differences are larger, but no tested (L,r)(L, r) combination closes the gap to the reference (general comment, point 1). On WOMD and Waymo BEV, rank 4 performs worse, and larger ranks do not improve on rank 8. On Perception, with only 319 training scenarios, rank 4 is as accurate as rank 8. We factorize every word letter by letter, obtaining long-word probabilities by composing the letter operators. The next paragraph (Q2) quantifies the resulting error.

Error accumulation (Q2). Error accumulates with the number of composed operators, but slowly. On the monitored properties, skill relative to the per-property reference remains at 0.94 or above up to H=20H = 20, which corresponds to a predictive horizon of 2 s at WOMD's 10 Hz sampling rate. This horizon covers short-term safety properties such as an imminent collision. Skill decreases to 0.85 at H=40H = 40 (new horizon ablation in Appendix I.2). Part of this loss is bias from probability mass lost when the learned operators are composed. At H=40H = 40, this makes the predicted probabilities of all possible futures of length HH sum to only 0.95 (instead of 1). The remainder is error in the composed word probabilities.

To address your suggested comparison with empirical sequence probabilities, we compared composed probabilities with a regression fitted directly to each word. For words of length 2 and 10, composition retains 99.7% and 94% of the direct regression's accuracy, respectively. Individual longer words occur too rarely to estimate their frequencies.

Logical consistency (Q3). Logically equivalent formulas receive identical predictions by construction, however, estimation error can make the predictions for a formula and its negation sum to slightly less than one. The first follows from the fact that a formula's prediction is the sum of the estimated probabilities of its accepted words. Each word's probability is composed letter by letter, regardless of the formula, so the same approximate value is used in every formula. Equivalent formulas of the same horizon accept the same words and therefore receive exactly the same prediction. We verified this on all equivalent pairs in our catalog. For the second part, a formula and its negation split the words between them, so their predictions add up to the sum over all words. Due to the mass loss discussed in Q2, the estimated operators yield an average sum of 0.993 at H=5H = 5 and 0.946 at H=40H = 40 on WOMD. Dividing each prediction by this sum requires one extra inner product and restores normalization exactly before clipping, but changes mean Brier by at most 0.001. Small negative estimates arise from the same estimation error; predictions are clipped to [0, 1].

AuthorsOpenReview ↗

Reply to Reviewer J5UL (2/2)

Practical advantage (W3, Q4). Our main advantage over the per-property reference is admitting new properties without training. The reference must store its training data, evaluate each new property on it, and train a new head. Ours compiles the property from stored operators and needs outcomes only on the calibration split, which every certified monitor needs. To admit a new property with its certificate, our monitor needs to store 61 kB to 4.6 MB, against 0.9 to 45 MB for the reference, 10 to 24 times less (App. J.2). Neither amount includes the encoder and history-feature model, which both monitors need. Recall that all monitors were trained on server-class hardware (nodes with NVIDIA H200 or RTX 6000 Ada GPUs). A robot deployed in a physical AI setting has far less memory and compute, making separate training for every new property much more restrictive, clearly highlighting the advantage of our method.

Inference costs are similar. Both monitors compute one shared vector per frame (our predictive state or the reference's history feature) followed by one inner product per property. Monitoring 100 properties therefore costs about as much as monitoring one: 25–73 µs per frame for ours and 3–30 µs for the reference (ranges are over the three benchmarks, on GPU). A new property, including recalibration, costs 0.7–2.5 ms for ours and 0.4–3.2 ms for the reference. Our compiler has not yet been tuned for speed, so we expect its cost to improve as the implementation matures. The runtime advantage over monitors that learn their own history summaries (AR-64, RNN) is substantial: At 100 properties, AR-64 and the per-property RNN take up to 6.2 ms and 35 ms, respectively; a new RNN takes 7–81 s to train. Table 1, App. I.3, and App. J.2 give the full comparison.

Rare events (W4, Q5). For rare events, the Brier score mainly reflects the base rate and provides little information about detection. Appendix J.1 therefore also reports how well each monitor ranks histories by risk and what the certificate guarantees on WOMD. We measure ranking by AUROC, the probability that a history in which the event occurs receives a higher predicted event probability than one in which it does not.

  • Rarely satisfied properties (15 properties, base rate 1–3%): ours ranks slightly worse than the baselines (AUROC 0.89, against 0.94 for the reference, 0.94 for the RNN, and 0.92 for AR-64). But the certificate it provides remains informative: for the histories ours rates most likely, the satisfaction probability is certified to be at least 0.11 at the median, six times the base rate of 0.017, on all 15 properties.
  • Rarely violated properties (66 properties, violated in 0.1 to 4.1% of cases): ours ranks as well as AR-64 (AUROC 0.86 for both) and slightly below the reference (0.88) and the RNN (0.91).

I thank the authors for the explanations. The authors addressed some of my concerns regarding the design parameter choices.

However, my main concern regarding the gap between Assumption 1 and its empirical validation still holds. Specifically, teh assumption requires the span condition to hold for all extended histories (h,u). However, the proposed method evaluates predictive-state only on observed histories u=\epsilon. The additional length-10 comparison provides useful empirical evidence, but does not fully resolve this fundamental issue for general or longer formulae.

Reviewer_RpkaOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes a zero-shot probabilistic monitor for STL under partial observability. It learns a predictive state representation of future label sequences. Specifically, it uses learned linear operators and automaton-based formula progression to compile new specifications into linear decoders, avoiding property-specific retraining. The method also provides group-conditional probability bounds through calibration. Experiments on driving data show its high prediction accuracy and comparably low inference cost.

Critical strengths
  1. I appreciate the goal of supporting changing STL specifications without retraining a separate monitor for each property. Compiling a specification into a fixed linear decoder is an interesting way to achieve efficient runtime monitoring.
  2. The empirical results are encouraging. The method retains high predictive performance across multiple modalities, while being significantly faster than the autoregressive baselines. These results show the potential for this system to operate in the real world
Critical weaknesses
  1. My major concern is that the technical novelty beyond existing PSR and automata-based methods remains unclear. The method combines established linear PSR operators [1] with formula progression [2]. The paper does not clearly distinguish its novel technical contributions from this combination. In particular, the proposed attention mechanism appears to reinterpret a fixed linear readout rather than introduce a distinct attention mechanism.
  2. Also, the evidence for generalization and expressivity is limited. Zero-shot generalization is restricted to new formulas over a fixed set of atomic propositions. Moreover, exact linear decoding relies on the span assumption (Assumption 1), which may not hold for more complex dynamics; ridge regression cannot resolve the resulting representation error. Increasing the core-test set is also costly, as its size grows exponentially with the number of propositions. Experiments cover only driving data with 3–4 propositions, retain just 4 of 35 candidate properties in the raw-camera evaluation, and show degradation for some longer horizons. Thus, I’m worried about the method's broader applicability. [1] Links Between Multiplicity Automata, Observable Operator Models and Predictive State Representations — a Unified Learning Framework, 2015 [2] Planning for Temporally Extended Goals, 1998
Questions for authors
  1. Could the authors clarify what is the main technical difference between the proposed decoder and applying standard PSR sequence operators with automaton-based dynamic programming?
  2. Section 4.1 notes that the learned operators are identified on observation-history states, while their composition also involves extended histories. How does this mismatch affect prediction accuracy, particularly for longer horizons?
5 comments
AuthorsOpenReview ↗

Reply to Reviewer Rpka (1/2)

We thank the reviewer for recognizing the method's potential. We address W2's points on Assumption 1, horizon, and Perception property selection in the general comment to all reviewers, and the focus on driving benchmarks in our reply to Reviewer VPiq (W5).

Technical novelty (W1, Q1). The composition rule mσω=Mσmωm_{\sigma\omega} = M_\sigma m_\omega and formula progression are known results. However, our contribution is to develop a new theory along with efficient algorithms that allow to define and use PSRs for tests over letters, as required for the design of STL runtime monitors. Crucially, we note that the application of classical PSRs do not apply in this setting, so that we make the following three contributions:

  • Defining the predictive state. A classical PSR is defined on the system-dynamics matrix DD, whose rows are histories and whose columns are tests, both over the observed alphabet (see Figure 5a). Conditioning a history on a test outcome yields another history and therefore another row of DD. This closure is integral for the state update and the operators MσM_\sigma. In our setting, histories consist of observations, whereas tests are words of latent letters. Conditioning on a latent letter breaks this. Therefore, we introduce the extended system-dynamics matrix (Definition 4), whose rows are observation histories extended by latent letter prefixes. We prove that the operators exist under Assumption 1, which constrains only the columns of length L+1L+1 (Proposition 2 and Theorem 1). The classical PSR is the special case in which the letters are the observations.
  • Learning the predictive state. Classical PSR learning estimates DD by counting how often each test follows each history. Our histories are continuous (which never repeat) and test outcomes are never observed directly; so counting doesn't apply. Running the classical update with estimated operators would also compound errors and divide by estimates that can vanish for rare letters. Instead, we learn the predictive state by regression on a fixed-size history feature ξ\xi, using latent-word indicators as targets. This regression is trained once, independently of any property. The letter operators are fitted on observation histories but composed on extended histories, which runtime data doesn't cover. We measure the resulting error: Composed word probabilities retain 99.7%, 97%, and 94% of the accuracy of a regression fitted directly to each word, for words of length 2, 5, and 10, respectively (on WOMD; 99.9%, 99%, and 96% on Waymo BEV; etc.).
  • Reading out a property. By Theorem 1, a property's probability is computed by summing over all its accepted words. Enumerating up to ∣Σ∣H=1640|\Sigma|^H = 16^{40} words on WOMD is infeasible. Tracking the property automaton online, alongside the model, would require knowing the current letters. Our automaton reads latent letters, so its state is unknown at runtime. We compile the formula by formula progression into a layered automaton and run the backward recursion (Eq. 7) offline. The automaton represents the specification, and the operators represent the learned dynamics. The linear readout allows this recursion to reduce to one vector fφf_\varphi. Online evaluation then requires one inner product per frame, independent of the horizon HH, instead of O(H∣R∣∣Σ∣r2)O(H|R||\Sigma|r^2) for tracking the automaton product online.

The specification language fixes the core tests, removing the usually difficult problem of discovering PSR tests. One representation then serves every property of the fragment without new data or retraining. The revised Section 3.1 states the relation to standard PSRs explicitly.

Attention (W1). We agree that the readout is a fixed linear map. The attention view explains this map through a correspondence (Table 2), rather than adding an additional mechanism. The query encodes the property's mask over candidate futures (recall Figure 1) and is compiled exactly from the formula's syntax; it thus doesn't need to be learned. The revised Section 3.1 makes this distinction explicit.

AuthorsOpenReview ↗

Reply to Reviewer Rpka (2/2)

Generalization (W2). Zero-shot refers to new formulas over a fixed set of atomic propositions, as the limitations paragraph now states explicitly. In practice, having fixed propositions is the usual case rather than a restriction. Safety requirements are expressed in quantities such as time to collision, headway, or clearance, which are common quantities used to compose new requirements. During operation, the properties over these propositions change through new rules, horizons, etc. Our monitor handles these changes without new data or training. This restriction is also independent of what system dynamics the monitor can learn. The monitor learns the dynamics once per system and then serves every property over the given propositions. A new proposition requires labels for that proposition, as it does for every monitor trained on labelled data.

As with every automaton-based method over APAP, the number of letters, 2∣AP∣2^{|AP|}, grows exponentially with ∣AP∣|AP|. Rank reduction compresses the predictive state to r=8r = 8–16 here, but does not reduce the number of letter operators. In practice, safety monitors usually use only a handful of propositions, selected by the designer. The new ablation in Appendix I.4 increases the number of propositions: Compiling one property takes 1.6 to 1.9 times longer per added proposition, from 0.4 ms at 2 to 3.8 ms at 6 propositions. With the regressor and the rank projection stored as one matrix, our per-frame cost stays at a near-constant 28--30 µs from 4 to 32 letters (Waymo BEV).

Thanks for the detailed response and the additional experiments. I appreciate the effort the authors have put into addressing my concerns.

The clarification of the difference from classical PSRs is particularly helpful. I now better understand the challenge of having observation histories and tests over latent proposition labels, and why the standard PSR formulation cannot be directly applied. The extended system-dynamics matrix and the corresponding operator construction seem to provide a meaningful technical contribution. I also appreciate the clarification that the attention mechanism is an interpretation of the linear readout rather than a new attention architecture.

The additional experiments on the span assumption, prediction horizon, and number of propositions are also useful. They provide better evidence of when the method works well and where its limitations are. In particular, the results suggest that the method is reasonably effective for short-horizon monitoring, although the accuracy still degrades as the prediction horizon increases.

I still have some concerns about the assumptions behind the theoretical results. In particular, the span assumption needs to hold over extended histories, while the empirical validation is mainly based on observed histories. Therefore, I am not fully convinced how well the method would generalize to more complex dynamics or longer-horizon specifications. The restriction to a fixed set of propositions also limits the scope of zero-shot generalization, although I agree that this is reasonable for many practical monitoring applications.

Overall, I think the rebuttal has clarified the technical contributions and strengthened the experimental evaluation. I now see more novelty in the proposed PSR construction than I did initially, and I think the ability to support new specifications without retraining is a useful contribution. While some concerns about the assumptions and broader applicability remain, I am increasing my rating.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Comment to All Reviewers

We thank the reviewers for their detailed feedback. We ran additional experiments and uploaded a revised paper addressing their feedback, with changes marked in blue. The main changes are listed below. We address two issues common to all three reviews here and the remaining points in the individual replies.

1. Assumption 1 and composing PSR operators (Rpka W2/Q2, J5UL W1/Q2, VPiq W1/W2)

Theorem 1 requires Assumption 1 for exact decoding. However, our monitor is statistically calibrated in Proposition 1 and can be used without it, e.g., when Assumption 1 holds only approximately. In that case, the ridge-regression estimates of the PSR operators are linear approximations rather than exact operators, and the compiled decoder approximates the satisfaction probability of the queried property. The certificate of Proposition 1 remains valid in either case because it holds for any predictor fitted independently of the calibration data.

We now verify from data that Assumption 1 holds approximately in our settings (new Appendix I.1): When predicting the next-longer words (L+1L+1), the predictive state retains 98% of the full history feature's improvement over the constant predictor on WOMD and Waymo BEV, and 99.7% on Perception. Accuracy degrades noticeably only for property horizons beyond H=20H = 20, i.e., when the monitor must predict properties more than 2 s into the future (10 Hz sampling rate; new horizon ablation in Appendix I.2). This horizon covers short-term safety properties such as an imminent collision.

Skill relative to the per-property reference is 0.99, 0.98, and 0.94 at H=5H = 5, 10, and 20, and 0.85 at H=40H = 40 (on WOMD). Part of this loss is bias from probability mass lost during operator composition. The remainder is error in the composed word probabilities, which grows with the number of composed operators. The new Appendix I.1 shows that varying LL does not close this gap.

2. The Perception benchmark's property selection (Rpka W2, J5UL W4/Q5, VPiq W6/Q1)

We excluded Perception properties with a degenerate base rate, near-duplicates, and properties for which no monitor meaningfully improves on the constant base-rate predictor. Exclusion is decided based on the per-property reference, so it does not favour our method. Table 3 already listed the reason for each exclusion. The revision adds every monitor's accuracy on the excluded properties.

Perception, mean test BrieroursreferenceRNNAR-64constant
25 properties excluded for their base rate or accuracy gain0.06890.06780.07170.07950.0718
all 33 candidate properties with both outcomes on the test split0.07500.07340.07780.08510.0898

On the excluded properties, ours and the reference improve on the constant predictor's accuracy by only 0.003 and 0.004, respectively. The RNN matches it, and AR-64 is worse. Our method therefore also compares favourably with the RNN and AR-64 on the excluded properties. We excluded them because no monitor meaningfully improves on the constant predictor. Also, on the excluded properties, test frequencies meet the certified bounds in 98% of populated bins (mean certified lower bound 0.073).

Main changes in the revised PDF

  • New Appendix I: added ablations of LL and rank, including an empirical check of Assumption 1 (I.1), property horizon (I.2), number of properties (I.3), and number of propositions (I.4).
  • New Appendix J: added rare-event results (J.1) and the runtime spread, memory, and time required to admit a new property (J.2); Table 3 now reports every monitor's test Brier score on the excluded properties.
  • Table 1: added seed standard deviations, re-measured all timings, included recalibration in the cost of a new property, and updated the speed advantage over AR-64 (9 to 160 times).
  • Sec. 2.2, 3.1, and 4: added an example property, stated the differences to standard PSRs, clarified the attention view, and moved the architecture overview into the main text.
  • Sec. 4.1, 5, and Limitations: explained what the monitor estimates when Assumption 1 holds only approximately and reported its empirical check, explained part of the long-horizon loss through lost probability mass, and clarified the zero-shot framing.
AuthorsOpenReview ↗

Follow-Up: Any Remaining Questions or Concerns?

Dear Reviewers,

Thank you again for your detailed and thoughtful reviews. The revised version of the paper, with the changes highlighted in blue, has been uploaded. We believe that our responses and the revised manuscript address all of your comments. We would be glad to hear whether any questions remain that we could still address before the discussion period ends.

Kind regards, The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.