Active Learning of Temporal Specifications through Distinguishing Queries

Rajarshi Roy, Xiaowei HuangarXiv 2026 · arXiv

TL;DR

Researchers have developed a new active-learning framework that allows non-experts to teach robots complex temporal specifications (LTLf) simply by labeling execution traces and providing natural-language hints. By replacing difficult "equivalence queries" with "distinguishing queries" and using an efficient enumerated version space, the system identifies correct specifications faster and with fewer questions than previous SAT-based methods.

What Problem Does This Paper Address?

Formal methods—like verification, monitoring, and planning—rely on Temporal Logic to define how a system should behave over time (e.g., "If a robot picks up an item, it must eventually deliver it before picking up another"). However, writing these formulas is notoriously difficult and error-prone, even for experts.

Existing active-learning approaches (where a machine "asks" a human for guidance) typically rely on equivalence queries. This requires a human teacher to look at a complex logic formula and decide if it is exactly what they intended. If it isn't, they must provide a counterexample. For non-experts, this is a non-starter. Furthermore, many current learners use SAT-based solvers that restart their search from scratch every time they receive a new piece of information, making the process computationally sluggish as the complexity of the behavior grows.

Methods

The authors introduce a modular framework for learning Linear Temporal Logic on finite traces (LTLf) that shifts the burden away from the human. Key components include:

  • Distinguishing Queries: Instead of asking "Is this formula right?", the learner finds two candidate formulas that disagree on a specific execution trace. It then asks the teacher: "Is this specific trace acceptable?" The answer immediately eliminates one of the candidates (and potentially thousands of others).
  • Enumerated Version Space: Rather than re-solving a SAT problem, the learner maintains a "version space"—a large collection of all possible formulas within a certain size. As the teacher labels traces, the learner simply filters out inconsistent formulas.
  • Natural-Language Hints: The framework allows teachers to provide informal guidance at two levels:
  • Level 1: Identifying the type of requirement (e.g., "Something is missing" or "The order is wrong").
  • Level 2: Providing a specific partial requirement in natural language (e.g., "Every pickup must be followed by a delivery"), which is then translated into a logic fragment to prune or rank the search space.
  • Formula Progression: To find traces that distinguish between two formulas efficiently, the system uses "formula progression"—an on-the-fly search technique that avoids the memory explosion of building full automata for every candidate.

Datasets

The researchers evaluated their learner on 36 target specifications across two main categories:

  1. Free Traces: 20 LTLf targets over a generic set of atomic propositions, where any sequence of events is possible.
  2. Environment-Constrained Traces: 16 targets set within four standard reinforcement learning and verification benchmarks:
  3. Office World: A grid-based navigation task.
  4. Taxi: A classic passenger pickup and delivery environment.
  5. MiniGrid (DoorKey): Environments where an agent must find a key, unlock a door, and reach a goal.

Key Insights and Ideas

  • Human-in-the-loop Simplicity: By using membership queries (labeling traces) instead of equivalence queries, the system meets the user where they are. Humans are much better at judging a specific behavior than auditing a logic formula.
  • The Power of "Safe" Hints: The authors found that using hints to rank candidates is incredibly robust. Even if a user provides an incorrect hint, it might make the search slightly slower, but it never prevents the learner from eventually finding the correct target.
  • Enumeration Beats SAT (at this scale): While SAT solvers are powerful, the overhead of encoding and re-solving the problem for every new label is high. For the formula sizes typically used in system specifications (size 2–7), simply "listing and filtering" is significantly faster.

Key Results

  • High Efficiency: On average, the learner identified the correct target using fewer than seven queries beyond an initial small sample of ten traces.
  • Speedup: The enumeration-based approach was more than 2.5x faster than SAT-based alternatives for size-7 formulas (8.8 seconds vs. 22.4 seconds).
  • Hint Impact: Correct natural-language hints reduced the number of required queries by up to 16% and reduced the number of candidate formulas generated by 20%.
  • Scalability: The system successfully managed version spaces containing up to 5.1 million candidate formulas.

Limitations and Future Work

  • Known Size Bound: The current implementation assumes the learner knows the approximate size of the target formula (within one node). In a real-world scenario, the learner would need to iteratively increase the search bound, which could add overhead.
  • Simulated Teacher: While the paper proves the logic works, the "natural language" component was simulated. A critical next step is a user study with non-experts to see how they interact with the system and how the learner handles "noisy" or ambiguous hints.
  • Scaling to Large Formulas: While enumeration is fast for small-to-medium formulas, it will eventually hit a "memory wall." Future work may need to hybridize enumeration with SAT-based or neural approaches for very large specifications.

Summary updated

Abstract

Temporal specifications are essential for verification and monitoring, yet writing formulas that capture the intended behaviour is difficult. Active learning derives such specifications through interaction between a learner and a teacher, but remains underexplored for temporal logics. Existing approaches require the teacher to answer equivalence queries and to construct counterexamples, and they often rely on SAT-based learning procedures that restart the search after each new example. We present an active-learning framework for LTLf in which the teacher only labels traces and answers natural-language questions about the intended behaviour. The learner maintains an enumerated version space of candidate formulas, generates traces that distinguish candidates, and uses the teacher's hints to rank candidates or to restrict the search. We prove consistency with the observed examples, identification within bounded hypothesis classes with a bound on the number of queries, and a PAC guarantee for the final hypothesis. In experiments with a simulated teacher on 36 targets, including targets in four standard environments, the learner identifies every target when it compares all rivals, with fewer than seven queries beyond an initial sample of ten traces on average. Correct hints reduce the number of queries by up to 16% and the number of generated candidates by a fifth, and hints used for ranking never prevent identification, even when incorrect. Our enumeration-based version space is faster than the SAT-based approach of previous learners at every target size.
BibTeX
@misc{roy2026active,
  author = {Rajarshi Roy and Xiaowei Huang},
  title = {{Active Learning of Temporal Specifications through Distinguishing Queries}},
  year = {2026},
  eprint = {2611.17866},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17866},
}
Figure