← AI Techniques Radar
Training & fine-tuning

PAC tree sampling to learn visibly pushdown language acceptors from black-box decisions

Adapts a VPG-learning workflow to a fully black-box setting by replacing a white-box equivalence oracle with PAC-style sampling over trees, querying only the acceptor’s binary accept/reject decisions. It further improves robustness by sampling trees directly (rather than well-formed sequences constrained by a permissive baseline automaton), using the resulting queries to estimate deviation from a target VPG model.

Discovered 2026-11-10 · Sources checked 2026-11-10

This summary was generated with AI assistance.

Why it matters

This enables learning formal language structure (visibly pushdown grammars / tree automata) from neural language acceptors without access to internal states, while also reducing blind spots caused by only testing well-formed strings in a restricted region of the language model’s behavior.

What changed

1) Swap the internal-state-based equivalence oracle for PAC sampling over trees using only black-box binary decisions. 2) Replace sequence sampling constrained to well-formed strings under the most permissive baseline (BParse) with direct tree sampling, so the procedure queries sequences beyond that region and can quantify deviation. 3) Extend the learner to build a tree-automaton model that captures target behaviors outside the previously covered subset (BParse).

Where it helps

  • Learning structured language acceptors (VPG-like) from black-box neural models
  • Extracting formal grammars from transformers when only accept/reject queries are available
  • Estimating how much a target acceptor deviates from a visibly pushdown behavior model
  • Extending grammar-learning coverage beyond a permissive baseline of well-formed strings

Evidence & reproduction

Reproduction not evaluated. A linked paper or repository does not establish independent reproduction.

Limitations & open questions

The method’s coverage still depends on what sequences are generated from the sampled trees, and the framework described is specialized to learning visibly pushdown grammar structure / related tree-automaton descriptions rather than arbitrary language classes.

Related World Models papers

Sources