Residual-Formula Beliefs for Open-Vocabulary Temporal Monitoring

Robots and software agents are increasingly given temporal rules in plain language, such as "never place the sterile clamp on the unwashed tray, and eventually deliver it to the surgeon." To check or reward such rules, the standard move is to compile them into a small state machine, a finite automaton that remembers which obligations are met and which are pending. Two things break when the words in the rule come from an unrestricted vocabulary and their truth must be read from camera images. The first is that the perception model is noisy. The second is that a noisy perceiver forces the checker to track every automaton state the history could have led to, not just one. That set can grow combinatorially: this is the state-space explosion familiar from formal methods, now driven by perception uncertainty rather than by the length of the formula.

We propose to monitor and reward open-vocabulary temporal tasks by maintaining a probability distribution over residual formulas, meaning what remains of the task given the history. The observation model for this distribution comes from mask-level open-vocabulary segmentation rather than from independent per-word detectors. The main claim is that the structure of the vocabulary does most of the work in keeping this distribution small. Each image region is one thing. "Sterile clamp" implies "clamp." Only words still mentioned in the residual formula matter. Conversely, the residual formula tells the vision model which few words to look for, which shortens the prompt list and cuts the hallucinations that long prompt lists cause.

Core Claim

Take a task written in finite-trace linear temporal logic, a logic of "always," "eventually," and "until" over propositions that are arbitrary noun phrases. Let $b_t(\psi)$ be the probability that the residual formula after $t$ camera frames is $\psi$. Let $\mathrm{prog}(\psi, a)$ be the standard progression of $\psi$ under a truth assignment $a$, which returns what remains of the task after one step. The update is

$$b_{t+1}(\psi') = \sum_{\psi} b_t(\psi) \sum_{a \in \mathcal{A}_C(P_\psi)} p(a \mid o_{t+1}) \, [\mathrm{prog}(\psi, a) = \psi'],$$

where $P_\psi$ is the set of propositions that still occur in $\psi$, $o_{t+1}$ is the new image, and $\mathcal{A}_C(P_\psi)$ is the set of truth assignments to those propositions that respect a set $C$ of vocabulary constraints (implications and exclusions).

The support of $b_t$ is the real cost of monitoring. Our claim has three parts. First, computing $p(a \mid o)$ from a mask classifier, which gives one categorical distribution per image region, rather than from independent per-word scores, concentrates mass on far fewer assignments. Second, restricting to $P_\psi$ and to assignments consistent with $C$ merges most branches. Third, together these keep the belief support small enough for per-frame use while giving calibrated violation verdicts. The alternative, hard-thresholding labels, turns one false detection into an irreversible "safety violated."

Where This Sits

The proposal takes its automaton representation from Semantically Labelled Automata for Multi-Task Reinforcement Learning with LTL Instructions. That work labels each automaton state with its residual formula and builds states only when visited, constructing under 1% of the full automaton and reaching 91% success on Global-Safety tasks where the nearest baseline reached 12%. It assumes a fixed, hand-mapped proposition set. Its authors name learning labels from raw pixels as the open problem.

LTL and Beyond introduced reward machines and counterfactual Q-learning over them, and flags the same gap: its labeling function is hard-coded. Automata-less Monitoring via Trace-Checking shows that safety and cosafety formulas over finite traces can be checked in $O(|\sigma|\cdot|\phi|)$ time without building a deterministic automaton, but only when each trace step is a clean Boolean assignment. All three papers motivate this proposal. None of them models the step where propositions become uncertain and open-ended, and that step is where our contribution lies.

On the vision side, MaskFormer supplies the method we reuse: it splits segmentation into class-agnostic region proposals and per-region classification against arbitrary text embeddings. We use that split to build a structured joint over propositions. LoGoSeg supplies a global object-existence prior that suppresses categories named in the prompt list but absent from the image. LSeg supplies the two failure modes we must survive. When the true label is missing from the prompts, a region is assigned its nearest neighbor ("dog" becomes "toy"). And part-whole confusions occur ("car door" becomes "car"). These constrain the design: we always include a "none of these" prompt, and we encode part-whole relations as explicit constraints instead of hoping the embedding resolves them.

The closest work that joins open vocabulary with temporal logic is ROLEX. It retrieves expert-supplied mappings to parse natural language containing unseen terms into temporal logic, gaining 20 to 38% in open-vocabulary-construct F1 on its NL2LTL task. ROLEX stops at the formula string. It neither grounds propositions in perception nor faces the resulting blowup. We treat its output, a formula over novel noun phrases, as our input.

Research Program

We will build a monitor-and-reward module with three pieces.

The first is a residual-driven query step. At each frame, only the propositions in the support formulas of $b_t$ are sent as text prompts to a frozen open-vocabulary segmenter, together with a background prompt. As obligations are discharged, the prompt list shrinks.

The second is a structured observation model. From the segmenter's region proposals and per-region category distributions, we compute $p(a \mid o)$ for the queried propositions. Each proposition is read as "some region carries this category." The existence prior gates each proposition. We calibrate with temperature scaling on a held-out split so that probabilities mean something.

The third is the constraint set $C$. It holds implications from text hierarchy, obtained by querying a language model and checking entailment between prompts ("sterile clamp" implies "clamp"). It also holds exclusions: region-level exclusivity comes directly from the categorical per-region output, and scene-level exclusions are those declared in the task. Because implications derived from text can be wrong, $C$ is treated as an explicit environment assumption. The monitor also tracks the probability that the assumption is violated, and reports it alongside the task verdict, rather than trusting it silently.

Beliefs over residual formulas are stored as hash-consed formulas, so identical residuals merge exactly. A mass threshold $\epsilon$ drops branches only when the dropped mass is logged and bounded. The monitor outputs three things: a violation or satisfaction verdict once the belief mass on false or true exceeds $1-\delta$, an "undetermined" verdict otherwise, and the expected trueness feature from the semantically-labelled-automata work for use as a policy input. For reinforcement learning, the expected reward-machine reward under $b_t$ replaces the hard-coded labeling function.

The analysis question beyond "does it work" is how belief support scales with three quantities: the number of propositions, the segmenter's error rate, and the nesting of temporal operators. We also want to know which of the three mechanisms (region-structured joint, relevance restriction, constraints) contributes most.

Baselines

The naive reference point is hard thresholding: take the segmenter's per-proposition score, threshold it at a value tuned on validation data, and feed the resulting Boolean trace to the trace checker and to the semantically-labelled-automata agent. This is what one gets by plugging a vision model into existing pipelines. It runs on the same segmenter, the same frames and the same threshold-tuning budget as our method, and its per-step cost is minimal.

The oracle-label reference runs the same monitor and agent with ground-truth propositions. It is the ceiling, and for the agent it should reproduce the reported 91% Global-Safety success from Semantically Labelled Automata on the original environments.

The strongest competitor is filtered thresholding. It applies temporal smoothing (a k-frame majority vote or a per-proposition hidden-Markov filter) to the scores before thresholding, which removes most isolated false positives without any belief over formulas. It gets the same tuning budget as our calibration, with k and the transition probabilities chosen on validation data.

The second strong competitor is an unstructured belief with beam pruning. It tracks $b_t$ with independent per-proposition Bernoulli probabilities and keeps the top-K residuals. K is chosen so that wall-clock time per frame matches ours.

Our ablations remove, one at a time, the region-structured joint (reverting to independent Bernoullis while keeping everything else), the relevance restriction to $P_\psi$ (querying all task propositions each frame), and the constraint set $C$. They isolate which ingredient keeps the support small.

Beating the baselines means two things at matched per-frame compute. First, a lower false-violation rate at equal or lower missed-violation rate than filtered thresholding. Second, higher verdict accuracy than beam pruning at equal wall-clock time, with at least an order of magnitude smaller belief support than the unstructured belief.

For grounding quality we inherit reported numbers rather than claim to improve them. LoGoSeg reports 16.4 mIoU on ADE20K-847 with ViT-L/14 and 97.4 mIoU on PASCAL VOC 20 (LoGoSeg), which tells us the long-tail regime is genuinely noisy. No reported result found on Lacuna for temporal-logic monitoring or reward-machine learning with open-vocabulary visual propositions, so the head-to-head numbers will be new.

Why not just…?

Why not just threshold the segmenter and use existing trace checkers? A single false positive on a safety proposition ends the run with a violation verdict that cannot be undone, and false positives compound over long episodes. At 16.4 mIoU on long-tail categories (LoGoSeg), they will be frequent. The hard-threshold baseline measures this directly. If its false-violation rate on our benchmarks is already close to the oracle, the belief machinery is unnecessary, and we will report that.

Why not just smooth the labels over time and then threshold? This is the real threat. Filtering handles transient noise cheaply, and on slowly changing scenes it may match us. It cannot handle two cases: persistent, structured confusions (a clamp always read as a sterile clamp from one viewpoint) and obligations whose triggering event lasts one or two frames, which smoothing erases. We build benchmark splits with short events and persistent part-whole confusions specifically to test this. If filtering matches us on those splits too, we will conclude that the residual-formula belief adds nothing over good per-proposition filtering.

Why not just track the full belief and prune to the top K? Beam pruning bounds cost but discards probability mass without any notice. The branches it drops tend to be the rare ones that lead to violations, exactly the ones a safety monitor exists to catch. Our constraints and relevance restriction merge branches exactly rather than dropping them, and we log all mass removed by the $\epsilon$ threshold. The matched-compute comparison, with missed-violation rate on rare-violation episodes as the key metric, settles whether exact merging matters.

Why not just let a multimodal language model watch the stream and judge the rule? Neural agents without explicit progress tracking behave myopically on long-horizon constraints: in Semantically Labelled Automata such baselines fell to 12% on Global-Safety against 91% with explicit residual tracking. Seg-ReSearch notes that these models are confined by frozen internal knowledge on specialized visual tasks. We include a prompted judge as an additional monitoring baseline on the recorded episodes. We expect it to lose on long episodes, but we do not assume it.

Proposed Experiments

We will build visual variants of existing temporal-task environments. In the first, LetterWorld and the conveyor-belt domain from Semantically Labelled Automata, each symbolic cell is replaced by a photographic object crop drawn from FSS-1000 or ADE20K-847 categories. Tasks are sampled from the same formula families, including Global-Safety, but name long-tail categories. We add controlled part-whole pairs and near-synonym distractors. In the second, Office World and WaterWorld from LTL and Beyond are retextured so that events are recognized from rendered images. Held-out splits use categories never seen during calibration, and a second held-out split uses task formulas with deeper nesting.

The frozen perception front ends are LoGoSeg-style and MaskFormer-style mask classifiers. We run both to check that conclusions do not depend on one segmenter.

For monitoring we measure false-violation rate, missed-violation rate, the fraction of undetermined verdicts, belief support size over time, and per-frame latency. For learning we measure task success and sample efficiency with reward derived from each monitor, relative to the oracle-label agent.

The decisive checks are three. The first is whether belief support stays roughly flat as the number of task propositions grows from 4 to 32 under our method, while it grows steeply under the unstructured belief. This is the claim that vocabulary structure tames the blowup. The second is whether, at matched compute, our method closes most of the gap between filtered thresholding and the oracle on the short-event and persistent-confusion splits. The third is whether the assumption-violation probability for $C$ rises when we deliberately inject wrong implications. That would show that learned vocabulary constraints fail loudly rather than silently.

A negative result on the first check would mean perception noise, not formula structure, dominates the cost. A negative result on the second would mean per-proposition filtering suffices. Either is worth knowing before anyone deploys open-vocabulary temporal monitors on real robots.