PaperlayerView exact revision on arXiv

Source-linked AI summary

$L^*LM$: Learning Automata from Examples using Natural Language Oracles

Marcell Vazquez-Chanlatte, Karim Elmaaroufi, Stefan J. Witwicki, Matei Zaharia, Sanjit A. Seshia

arXiv:2402.07051v2cs.LGcs.AIcs.CLcs.FL

TL;DR

Learning formal task specifications from demonstrations can be sample-inefficient, while task representations should support analysis and composition. L∗LM combines language-model membership queries with demonstration-informed labeled examples to learn DFAs. The authors report that natural-language descriptions, unsure responses, and additional language-model queries improve DFA learning performance.

  • Problem

    Learning formal task specifications from demonstrations can be sample-inefficient, and learned artifacts should support formal analysis and composition.

    Source: §1 · p. 1

  • Method

    L∗LM learns DFAs by combining language-model membership queries with DISS-generated labeled-example problems informed by expert demonstrations.

    Source: §1 · pp. 2–3

  • Results

    The authors report that natural-language descriptions improve DFA learnability, unsure responses improve performance, and more language-model queries improve performance.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Neither demonstrations nor natural language alone consistently identifies the correct DFA in the running example, motivating their combined use.

    Source: §1 · p. 3, §2 · p. 5

    Labeled examples given to the LLM must be consistent with the DFA, whereas demonstrations may include slips or be only prefixes of a path.

    Source: §5 · p. 8

Abstract

from arXiv · show

Expert demonstrations have proven an easy way to indirectly specify complex tasks. Recent algorithms even support extracting unambiguous formal specifications, e.g. deterministic finite automata (DFA), from demonstrations. Unfortunately, these techniques are generally not sample efficient. In this work, we introduce $L^*LM$, an algorithm for learning DFAs from both demonstrations and natural language. Due to the expressivity of natural language, we observe a significant improvement in the data efficiency of learning DFAs from expert demonstrations. Technically, $L^*LM$ leverages large language models to answer membership queries about the underlying task. This is then combined with recent techniques for transforming learning from demonstrations into a sequence of labeled example learning problems. In our experiments, we observe the two modalities complement each other, yielding a powerful few-shot learner.

1. Introduction

The paper targets task specifications that support formal analysis and composition, proposing L∗LM to learn DFAs from natural language, labeled examples, and expert demonstrations. Its membership-query protocol and DISS integration combine language-model judgments with demonstration-informed examples.

1. Introduction

  • DFAs are chosen as task representations because they expose finite memory, have flowchart-like semantics, and express regular tasks including reach-avoid specifications.Source: §1 · p. 2
  • The membership-query protocol asks the language model simple yes/no/unsure questions, with constrained output used instead of evaluating arbitrary generated code.The authors identify avoiding arbitrary code execution as a way to remove code-injection vulnerabilities.Source: §1 · p. 2
  • Allowing the language model to answer “unsure” lets the learner skip uncertain queries, which the authors report improves performance, especially alongside demonstration-based inferences.The paper notes that incomplete task context, including withheld environment dynamics, can make membership judgments uncertain.Source: §1 · pp. 2–3
  • DISS turns demonstration-based DFA learning into iterative labeled-example problems, where the LLM labels queries it is confident about and DISS supplies corrective feedback.The authors describe this as combining natural-language reasoning with analysis dependent on environment dynamics.Source: §1 · p. 3
  • L∗LM learns DFAs from natural language, labeled examples, and expert demonstrations, aiming to produce task specifications that support formal analysis and composition.The paper also states that its algorithm outputs a valid DFA consistent with input examples and requires no arbitrary code evaluation.Source: §1 · pp. 1, 3
  • Experiments report that natural-language descriptions improve DFA learnability, allowing unsure responses improves performance, and more LLM queries improve performance.Source: §1 · p. 3

2. Related Work

The related-work discussion situates L∗LM at the intersection of automata learning, demonstration-based task learning, and language-model extraction. It distinguishes the approach through multimodal learning, membership-query interaction, and integration with DISS.

2. Related Work

  • Automata-learning work includes identifying minimal DFAs consistent with labeled strings and learning through membership and equivalence queries.The paper situates its DFA-identification pipeline among SAT-based identification and active version-space learning methods.Source: §2 · pp. 3–4
  • Earlier inverse-reinforcement-learning approaches lack a principled way to compose learned reward artifacts and require relevant memory features to be known in advance.The paper contrasts these limitations with Boolean specifications that support composition and explicitly encode temporal constraints.Source: §2 · p. 4
  • DISS recasts learning a DFA from demonstrations as iterative grammatical-inference problems over labeled examples, using a proxy gradient over surprisal to suggest label changes.L∗LM uses the LLM to fill some examples and DISS to provide others.Source: §2 · p. 4
  • L∗LM combines demonstrations and language to learn task specifications, unlike prior LLM extraction work described as directly extracting automata or producing policies.The paper emphasizes that its membership-query restriction avoids arbitrary code execution and guarantees a valid DFA faithful to input examples.Source: §2 · p. 4
  • The paper distinguishes its unsure-response protocol from retraining language models to refuse uncertain queries, citing constrained decoding as its approach.Source: §2 · p. 4
  • In the running example, demonstrations imply the omitted rule to dry off before recharging, while neither demonstrations nor natural language alone consistently identifies the correct DFA.Source: §2 · p. 5

3. Refresher on Automata Learning

This section defines DFAs and labeled-example consistency, then reviews passive identification and active learning through membership and equivalence queries. It extends the membership-query setup to allow an unsure response.

3. Refresher on Automata Learning

  • A DFA consists of finite states, an alphabet, a transition function, an initial state, and accepting states; it accepts a string when the lifted transition ends in an accepting state.Source: §3 · p. 5
  • A labeled-example set separates positive from negative strings, and a consistent DFA accepts every positive example and rejects every negative example.Source: §3 · p. 6
  • The DFA identification problem seeks minimum-size consistent automata, but finite examples generally leave infinitely many candidates and state-minimization versions are NP-hard.SAT-based implementations are reported to solve the identification problem efficiently in practice.Source: §3 · p. 6
  • Active learning queries an oracle for membership and equivalence, while L∗ uses both; because equivalence queries are often unavailable in practice, they are approximated or replaced by candidate elimination.Source: §3 · p. 6
  • The extended membership query returns true, false, or unsure, and the active learner ignores unsure responses; in the paper’s L∗ experiments, unsure is mapped to false.Source: §3 · p. 6

4. Extracting DFAs from LLM Interaction

The section treats language models as approximate membership oracles for active DFA learning. Constrained responses make answers parseable, while an incrementally extended prompt carries prior interaction context.

4. Extracting DFAs from LLM Interaction

  • The section frames language models as a natural approximation to the membership oracle used in active automata-learning protocols.The algorithm is identified as an instance of version-space learning.Source: §4 · p. 6
  • Figure 3 depicts converting an LLM into a membership oracle; the proposed extended query and cache address hallucinations.The paper notes that ablations of this design appear in Section 6.Source: Figure 3 · p. 7
  • Constrained decoding structures the LLM response as reasoning followed by a final yes, no, or unsure answer, making it parseable as a membership response.The response grammar can also leave room for prompt-engineering approaches such as ReAct or chain-of-thought.Source: §4 · p. 7
  • The learner asks whether a queried word is a positive example, extending the prompt with prior responses, task instructions, and known labeled examples.The initial task description is user-provided.Source: §4 · p. 7

5. Incorporating Expert Demonstrations

L∗LM incorporates expert demonstrations through DISS, which turns demonstrations into iterative labeled-example learning. The combined method uses DISS both to supervise DFA learning and to connect demonstrations with natural-language task descriptions.

5. Incorporating Expert Demonstrations

  • A demonstration is a path generated by an agent in a Markov Decision Process to satisfy an objective, with the path featurized over a finite alphabet for DFA acceptance.Source: §5 · p. 7
  • Unlike labeled examples, a demonstration need not be accepted by the target DFA because it may include an accidental violation or be only a real-time prefix.Source: §5 · p. 8
  • DISS generates counterfactual labeled examples intended to make expert demonstrations less surprising, then uses them to learn DFAs with lower energy U.The energy combines DFA description complexity with the demonstration under its corresponding policy; λ reflects an a-priori expectation of DFA size.Source: §5 · p. 8
  • Each DISS iteration runs DFA extraction with a fixed query budget split between random and candidate-elimination queries, ranks the resulting DFA by U, and returns the lowest-energy DFA after fixed steps.The process repeats for a fixed number of steps.Source: §5 · p. 8
  • L∗LM uses DISS as a supervisory signal to add expert demonstrations as a learning modality.The interaction protocol runs the DFA extraction algorithm each DISS iteration and returns the DFA with minimal U.Source: §5 · p. 8
  • The combination can resolve ambiguities in natural-language task descriptions and indirectly restrict DISS’s concept class using the prompt.Source: §5 · p. 8

6. Experiments

The experiments examine DFA learning with natural-language queries and demonstrations, including variations in backend, task-description completeness, unsure responses, and query budget. In the robotic workspace, more language-model queries tend to lower final energy, while demonstration analysis remains necessary; outcomes also vary across backends and response settings.

6. Experiments

  • In the Tomita Grammar experiment, allowing unsure reduces eliminations but does not eliminate them, prompting the shift to demonstrations as an additional grounded supervisory signal.Source: §6 · p. 8

6.1. Robotic Workspace

  • With zero language-model queries, runs fail to reach ground-truth energy, while allowing more queries tends to lower final energy for both L∗ and candidate elimination.Many runs learn the exact DFA; others learn variants nearly indistinguishable in the demonstration and environment.Source: §6.1 · pp. 9–10
  • The robotic-workspace experiment varies rule completeness, whether unsure is allowed, the DFA-learning backend, and the per-iteration query budget, using two demonstrations and Mixtral-8x7B-Instruct.The figures plot minimum energy by DISS iteration; line color encodes query count and the red dotted line marks ground-truth DFA energy.Source: §6.1 · p. 9
  • Even with all task rules provided, learning a good DFA still takes 5 to 15 DISS iterations, so the natural-language prompt alone is not enough.Source: §6.1 · p. 10
  • Including all rules has a small effect for the candidate-elimination backend but substantially improves the L∗ backend.Figure 4 compares the L∗ and candidate-elimination variants.Source: Figure 4 · p. 9, §6.1 · p. 10
  • Allowing unsure responses improves performance, particularly in the L∗ setting, where queries can be less useful and hallucinations can yield unnecessarily large DFAs.DISS may then provide a correcting labeled example that is unnecessary given the size prior.Source: Figure 4 · p. 9, §6.1 · p. 10
  • The SAT-based candidate-elimination backend performs equal to or better than the L∗ backend, which often converges just above the ground-truth energy line.The reported explanation is that less useful L∗ queries make hallucinations more damaging comparatively.Source: §6.1 · pp. 9–10
  • LLM code output never helps learn an adequate DFA in the tested setting; the authors attribute this to superficial query decisions and note code-injection risk from arbitrary execution.They say mitigation strategies such as sandboxes should be employed.Source: §6.1 · p. 10

Appendix A. Demonstration Informed Specification Search (DISS) Overview

DISS combines a concept sampler and planner to infer DFA specifications from labeled examples and expert demonstrations. Its iterative loop adds hypothesized labeled examples while minimizing an energy that includes DFA complexity and demonstration likelihood.

Appendix A. Demonstration Informed Specification Search (DISS) Overview

  • DISS combines a concept sampler that returns a DFA consistent with labeled examples and a planner that returns an entropy-regularized policy for that DFA.These are the two components DISS requires.Source: Appendix A · p. 14
  • Each loop proposes a candidate DFA, analyzes demonstrations to hypothesize new labeled examples, and adds them to the example buffer for the next round.The goal is to minimize the energy of DFA description complexity plus the demonstration given its policy.Source: Appendix A · p. 14
  • The DISS energy weights DFA size using λ, which is set from the a-priori expectation of size(D).Source: Appendix A · p. 14

Appendix B. Tomita Grammars

The Tomita Grammar experiments find frequent membership-query hallucinations across the tested language models. An unsure option reduces, but does not eliminate, those errors, motivating grounded supervision alongside language-model answers.

Appendix B. Tomita Grammars

  • Hallucination rates ranged from 3.33% to 100%, with a median of 33.33%, across the Tomita Grammar experiments.The experiments tested seven grammars with 30 membership queries each for GPT3.5-Turbo and GPT4-Turbo, using original L* and L*LM with extended membership queries.Source: Appendix B · p. 14
  • Allowing an unsure response reduced hallucination rates by up to 10%, but no tested model completely avoided hallucinations.Similar rates were observed with Mixtral-8x7B-v0.1, and a few experiments also included GPT-4o.Source: Appendix B · p. 14
  • Because hallucinations persisted, the authors conclude that L*LM cannot strictly rely on an LLM as its oracle and motivate learning through multiple modalities.The experiments motivate adding a grounded supervisory signal.Source: Appendix B · p. 14

Appendix D. Psuedo code for L*LM

The pseudocode uses distinguishing membership queries to label candidate words, then returns a minimal DFA consistent with the accumulated examples. In the DISS loop, demonstration-based counterfactuals suggest label updates.

Appendix D. Psuedo code for L*LM

  • Within a query budget, the routine asks membership queries that distinguish remaining candidates, using an LLM wrapper and SAT-based DFA identification.Source: Appendix D · p. 15
  • Oracle responses labeled true or false are added to positive or negative examples, while an unsure response is handled separately; the routine returns a minimal consistent DFA.Source: Appendix D · p. 15
  • In the DISS loop, the candidate DFA is evaluated using a counterfactual based on the demonstration's negative log likelihood gradient to suggest label changes.Source: Appendix D · p. 15

E.1. Detailed Results

The detailed results concern active learning on the seven Tomita Grammars, with separate tables for original and unsure-enabled membership variants. The prompts define sequence acceptance and rejection, and alternative prompt-generation approaches produced no downstream difference.

E.1. Detailed Results

  • Table 1 reports active learning on the seven Tomita Grammars using L*LM with original L*; results are identical for GPT-3.5-Turbo and GPT-4-Turbo.Source: Table 1 · p. 16
  • Table 2 reports the unsure-enabled membership variant on the seven Tomita Grammars, with identical results for GPT-3.5-Turbo and GPT-4-Turbo.Source: Table 2 · p. 16

Prompts

  • The meta-prompt frames each task as a rule for labeling sequences as accepted or rejected and instructs the model to answer true, false, or unsure.The no-unsure treatment omits the instruction permitting an unsure answer.Source: Prompts · pp. 16–17
  • Human-written prompts, ChatGPT-4o-generated explanations, and paraphrased prompts produced no difference in downstream L*LM results.Source: Prompts · p. 17

Appendix F. Task Prompt

The prompt represents a robot’s grid-world behavior as a sequence of tile colors. A sequence is positive only if it follows the recharge, lava-avoidance, and drying-order rules.

Appendix F. Task Prompt

  • The robot’s behavior is recorded as a sequence over red, yellow, blue, and green grid-world tiles.These tiles represent lava, recharging, water, and drying, respectively.Source: Appendix F · p. 19
  • A positive sequence must include yellow, avoid red entirely, and visit green before yellow if blue is visited.The colors represent recharging (yellow), lava (red), water (blue), and drying (green).Source: Appendix F · pp. 19–20
  • Consecutive repeats collapse to one color, so [yellow,yellow,blue] becomes [yellow,blue].A positive example must conform to all the rules.Source: Appendix F · p. 20
Loading 2402.07051v2…