A New Active Learning Framework: Efficiently Learning Temporal Specifications with Discriminating Queries

An active learning framework for LTLf where the teacher only labels traces and provides natural-language hints, efficiently identifying temporal specifications.
This article proposes a new active learning framework for Linear Temporal Logic on finite traces (LTLf) to reduce teacher burden and improve learning efficiency. Traditional active learning relies on equivalence queries and counterexample construction, and SAT-based learning restarts the search on each new example. In the new framework, the teacher only labels traces and answers natural-language questions (hints), while the learner maintains an enumerated version space, generates discriminating traces, and uses hints to rank candidates or restrict the search. Theoretical analysis proves consistency, bounded identification, and PAC guarantees. Experiments on 36 targets show that on average fewer than 7 queries beyond the initial 10 traces identify all targets, correct hints reduce queries by 16% and candidates by 20%, and the enumeration-based method is faster than SAT-based methods.
Temporal specifications play a key role in software verification and runtime monitoring, but hand-writing formulas that accurately capture intended behavior is exceptionally difficult. Active learning derives specifications through interaction between a learner and a teacher, yet it remains underexplored in the temporal logic domain. Existing methods require the teacher to answer equivalence queries and construct counterexamples, and often rely on SAT-based learning processes that restart the search whenever a new example appears. This article introduces an active learning framework for LTLf in which the teacher only needs to label traces and answer natural-language questions about intended behavior, while the learner maintains an enumerated version space, generates traces that discriminate between candidates, and uses teacher hints to rank candidates or restrict the search. Experiments show that the framework identifies all targets across 36 targets, requiring on average fewer than 7 queries beyond the initial 10 traces, and that the enumeration-based version space is faster than prior SAT-based methods.

Challenges of Active Learning and Temporal Specifications
Writing temporal specifications is a bottleneck in the verification process. Active learning offers a promising alternative: the learner progressively builds a specification by asking questions to the teacher. However, active learning for temporal logic faces unique challenges. Traditional methods rely on equivalence queries, where the teacher must judge whether a hypothesis formula is equivalent to the target and provide a counterexample when it is not. This requires strong formal skills from the teacher, and SAT-based learning processes must restart the search each time a new example is received, leading to inefficiency. Moreover, existing work has explored active learning for LTLf (Linear Temporal Logic on finite traces) relatively little.
LTLf (Linear Temporal Logic on finite traces) is a variant of Linear Temporal Logic (LTL) over finite traces. Traditional LTL is typically used to describe properties over infinite traces, such as "some condition will eventually hold" or "some condition always holds." However, many software verification scenarios (e.g., program termination, finite executions) involve only execution traces of finite length, and LTLf provides a formal specification language for such finite traces. Its syntax is similar to LTL, including temporal operators such as "X" (next), "F" (eventually), "G" (always), and "U" (until), but the semantics are interpreted over finite traces, thus avoiding the complexity introduced by infinite traces. LTLf has important applications in runtime monitoring and verification of finite-state systems.
An equivalence query is a standard query type in active learning, in which the learner provides a hypothesis (e.g., a candidate formula) and the teacher judges whether the hypothesis is equivalent to the target concept; if not, the teacher must provide a counterexample (i.e., a sample that the hypothesis misclassifies). Equivalence queries require strong formal reasoning ability from the teacher, because the teacher must determine the semantic equivalence of two formulas, which is particularly difficult in temporal logic. The framework in this article avoids equivalence queries and instead uses membership queries (labeling traces) and natural-language hints, reducing the teacher's burden.
Framework Design: Only Labeling and Natural-Language Hints Required
In this framework, the teacher's role is simplified to two tasks: labeling traces (judging whether they satisfy the target specification) and answering natural-language questions about intended behavior (i.e., "hints"). The learner maintains an enumerated version space—the set of all candidate formulas consistent with current observations. It generates traces that discriminate between candidates (i.e., traces on which different candidates yield different labels) and asks the teacher to label them. Teacher hints can be used to rank candidates or restrict the search space. The learner does not need to construct counterexamples and avoids the overhead of SAT restarts.
A version space is a core concept in active learning, referring to the set of hypotheses consistent with all current observations. In this article, the version space consists of all LTLf formulas consistent with the labeled traces. The learner queries the teacher by generating traces that discriminate between candidate formulas in the version space (i.e., traces on which different candidates give different labels), thereby efficiently shrinking the version space. An enumeration-based version space means explicitly maintaining and enumerating these candidate formulas rather than using symbolic or SAT encodings. This approach is more intuitive on small-scale problems and avoids the restart overhead of SAT solvers, but it may face combinatorial explosion.
Theoretical Guarantees: Consistency, Bounded Identification, and PAC Learning
The authors prove three key properties: consistency with observed examples (all retained candidates are consistent with the data), identification within a bounded hypothesis class (identifying the target with a bounded number of queries), and a PAC (Probably Approximately Correct) guarantee for the final hypothesis. These results provide a theoretical foundation for the reliability of the framework.
PAC (Probably Approximately Correct) learning is a framework in computational learning theory that describes the ability of a learning algorithm to learn an approximately correct hypothesis with high probability from a finite number of samples. Specifically, PAC learning requires that the hypothesis output by the learning algorithm has an error rate of no more than ε with probability at least 1−δ, where ε and δ are user-specified parameters. In this article, the PAC guarantee means that the LTLf formula ultimately output by the learner is approximately equivalent to the target specification in a probabilistic sense. This guarantee provides a theoretical cornerstone for the reliability of the framework.
Experimental Evaluation: Efficient Identification and the Gains from Hints
In experiments with a simulated teacher, across 36 targets (including targets in four standard environments), the learner identifies every target when comparing all competitors. On average, fewer than 7 queries are needed beyond a sample of the initial 10 traces. Correct hints reduce the number of queries by up to 16% and reduce the number of generated candidates by one fifth. Interestingly, hints used for ranking never prevented identification even when they were incorrect. Furthermore, the enumeration-based version space is faster than prior SAT-based methods at all target scales.
Conclusion and Outlook
This work provides a practical framework for active learning of LTLf that requires only labeling and natural-language hints, with theoretical guarantees. Its efficiency and robustness to hints make it promising for real-world verification scenarios. Future directions may include extending to richer temporal logics and handling more complex teacher interactions.
One-line Summary
An active learning framework for LTLf is proposed in which the teacher only needs to label traces and provide natural-language hints, efficiently identifying temporal specifications.
Paragraph Summary
This article proposes a new framework for active learning of Linear Temporal Logic on finite traces (LTLf), aiming to reduce the teacher's burden and improve learning efficiency. Traditional active learning relies on equivalence queries and counterexample construction, and SAT-based learning processes must restart the search whenever a new example appears. In the new framework, the teacher only needs to label traces and answer natural-language questions about intended behavior (hints), while the learner maintains an enumerated version space, generates traces that discriminate between candidates, and uses hints to rank candidates or restrict the search. Theoretical analysis proves consistency, bounded identification, and PAC learning guarantees. Experiments on 36 targets validate the framework's effectiveness: on average fewer than 7 queries beyond the initial 10 traces are needed to identify all targets, correct hints reduce queries by 16% and candidates by 20%, and the enumeration-based method is faster than SAT-based methods.
Related articles

Former Huawei Genius Youth Open-Sources AI Agent Guide: 90+ Hands-On Case Studies
Former Huawei Genius Youth Li Bojie open-sources AI Agent Book, the most systematic Chinese Agent learning repo on GitHub, with 90+ runnable examples covering context compression, memory frameworks, MCP tool calling, prompt injection attack and defense, and other enterprise-level hands-on content.

The Most Detailed FDE Tutorial on Bilibili: Case-Based Teaching from Business Practice to Interviews
B站UP主推出FDE从入门到面试实战教程,讲师深入业务一线,用马氏学习平台真实案例讲解FDE岗位要求。本文分析案例教学法、笔记策略与私密信息处理,为AI岗位求职者提供参考。

518 Dance Motion Chains + H3 Relay: Long-Video Choreography Breaks the Duration Limit
The open-source dance motion library adds 518 motion chains for choreography without reference videos. The H3 workflow combines AddGuide relay, CF Lift acceleration, and VDN to enable 30–60s long-video generation, breaking single-segment duration limits with independently controlled segmented prompts.