PaperlayerView exact revision on arXiv

Source-linked AI summary

Binding Language Models in Symbolic Languages

Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, Noah A. Smith, Tao Yu

arXiv:2210.02875v2cs.CL

TL;DR

End-to-end neural NLP systems are flexible but lack interpretability and robustness, while symbolic systems have limited grammar coverage. BINDER combines executable SQL or Python programs with LM API calls, achieving state-of-the-art results on WikiTableQuestions and TabFact using only dozens of in-context demonstrations and no additional training.

  • Problem

    End-to-end neural systems lack interpretability and robustness, while symbolic systems have limited semantic coverage because their grammars cannot express all task questions.

  • Method

    BINDER uses Codex to parse inputs into executable SQL- or Python-based programs with unified LM API calls, then realizes those calls during program execution using few in-context exemplars.

  • Results

    BINDER achieves state-of-the-art performance on WikiTableQuestions and TabFact with only dozens of in-context demonstrations and no additional training.

  • Takeaways & Limitations

    BINDER provides flexible functionality integration and explicit programs that improve coverage while supporting human debugging.

  • Takeaways & Limitations

    BINDER can still produce incorrect programs when an API uses an incorrect value or operator, although the explicit program can expose the error source.

Abstract

from arXiv · show

Though end-to-end neural approaches have recently been dominating NLP tasks in both performance and ease-of-use, they lack interpretability and robustness. We propose Binder, a training-free neural-symbolic framework that maps the task input to a program, which (1) allows binding a unified API of language model (LM) functionalities to a programming language (e.g., SQL, Python) to extend its grammar coverage and thus tackle more diverse questions, (2) adopts an LM as both the program parser and the underlying model called by the API during execution, and (3) requires only a few in-context exemplar annotations. Specifically, we employ GPT-3 Codex as the LM. In the parsing stage, with only a few in-context exemplars, Codex is able to identify the part of the task input that cannot be answerable by the original programming language, correctly generate API calls to prompt Codex to solve the unanswerable part, and identify where to place the API calls while being compatible with the original grammar. In the execution stage, Codex can perform versatile functionalities (e.g., commonsense QA, information extraction) given proper prompts in the API calls. Binder achieves state-of-the-art results on WikiTableQuestions and TabFact datasets, with explicit output programs that benefit human debugging. Note that previous best systems are all finetuned on tens of thousands of task-specific samples, while Binder only uses dozens of annotations as in-context exemplars without any training. Our code is available at https://github.com/HKUNLP/Binder .

1 INTRODUCTION

BINDER addresses the limited coverage and interpretability trade-off between neural end-to-end and symbolic NLP systems by binding flexible LM functionality into executable programs with few annotations.

  • Motivation: Neural end-to-end systems are flexible and easy to use but lack interpretability and robustness, whereas symbolic systems provide explicit intermediate representations but limited grammar coverage.Neural systems directly map inputs to outputs; symbolic systems can execute logical forms, reasoning paths, or code.
  • Motivation: Existing neural-symbolic approaches commonly require task-specific languages, manually designed neural modules, and large domain-specific training datasets.Their modules and symbolic languages generally cover limited semantic phenomena within particular tasks and domains.
  • BINDER: BINDER is a training-free neural-symbolic framework that binds a unified LM API to programming languages such as SQL and Python using a few in-context program annotations.The framework maps task inputs to executable BINDER programs and uses Codex for both parsing and API-based functionality.
  • BINDER: BINDER parsing identifies language-supported portions, generates API calls for unsupported portions, and places those calls compatibly within the target program grammar.During execution, Codex realizes the API calls and the resulting values are integrated into the program before standard interpretation.
  • Results: BINDER achieves state-of-the-art results on WikiTableQuestions and TabFact with only a dozen or so annotations, while prior state-of-the-art methods require more than 10K annotated examples or extensive pretraining.The analysis reports the greatest gains on questions unsupported by the original SQL or Python grammar.

2 APPROACH

BINDER generates executable programs that combine a symbolic language with optional LM API calls, then executes those programs by resolving the calls and evaluating the resulting syntax tree.

  • Overview: Given a natural-language question Q and optional contexts D, BINDER generates an executable program Z whose execution produces answer A.Contexts may include passages, tables, images, or combinations of these sources.
  • BINDER Parsing: A BINDER API call f(Q̂;D̂) targets the portion of Q unsupported by the programming language and the relevant context needed to answer it.The call returns an answer represented as a variable compatible with the symbolic grammar; Q̂ or D̂ may also equal the full input.
  • BINDER Execution: The interpreter adds API calls to the grammar, parses the program into an abstract syntax tree, realizes calls with an LM, and evaluates the combined program.The execution phase includes lexical analysis, syntax analysis, and program evaluation.
  • In-context learning: Codex learns the modified BINDER grammar from a small number of in-context examples and serves as the LM for API-call outputs without parameter training.The examples may be manually selected or dynamically retrieved, balancing question diversity against input capacity.
  • SQL and Python APIs: In structured knowledge experiments, fcol maps table columns to inferred columns while fval directly derives values, with both outputs usable in SQL or Python programs.fcol can represent operations such as identifying North American countries, while fval can answer a sub-question such as selecting the most formal shirt.

3 EXPERIMENTS

BINDER is evaluated on WIKITQ and TABFACT using execution accuracy, with comparisons against strong fine-tuned baselines and Codex inference modes. It achieves state-of-the-art results while using only a few in-context annotations and no training, with gains over standard SQL and end-to-end QA.

  • 3.1 EXPERIMENT SETUP: BINDER is evaluated on WIKITQ and TABFACT using execution accuracy, including comparisons with strong published systems and Codex end-to-end and SQL baselines.WIKITQ and TABFACT require structured knowledge grounding; evaluation includes a pre-matching check for semantically correct WIKITQ outputs.
  • 3.1 EXPERIMENT SETUP: 14 in-context exemplar annotations are used for each dataset, while competing systems use full training sets, fine-tuning, or additional task-related pretraining.Codex is used both to generate programs and to execute API calls in the experiments.
  • 3.2 MAIN RESULTS: 1.3% is the absolute margin by which Codex BINDER surpasses the previous state-of-the-art on WIKITQ.The result is reported for WIKITQ execution accuracy, with development and test results presented in Table 1.
  • 3.2 MAIN RESULTS: 3.5% is Codex BINDER’s improvement over standard SQL on the WIKITQ test set, while its advantages over end-to-end QA and SQL are 15.9% and 12.4%, respectively.These comparisons are reported as evidence that BINDER mitigates coverage limitations of the original SQL language.
  • 3.2 MAIN RESULTS: 8.1% is Codex BINDER’s margin over the previous best symbolic method on TABFACT, while its few-shot advantages over standard SQL and end-to-end QA are 4.4% and 12.5%.Retrieving similar examples adds 0.9% and yields new state-of-the-art results against the previous best fine-tuned method.
  • 3.2 MAIN RESULTS: BINDER additionally provides explicit programs for human debugging and is reported to be robust to large or noisy inputs.The paper identifies interpretability and robustness as advantages beyond performance.

4 ANALYSIS

BINDER’s analyses show gains on program-unsolvable questions, improved interpretability through explicit programs, and resilience to larger tables, while extending to Python and multimodal inputs.

  • Ablation Study: BINDER outperforms Codex SQL by 10.1% on program-unsolvable WIKITQ questions and reduces the spurious rate from 33% to 12%.About 20% of WIKITQ questions are program-unsolvable; BINDER also scores higher than SQL on program-solvable questions.
  • Interpretability: Explicit BINDER programs expose semantic and execution errors, supporting human debugging and error analysis.In sampled WIKITQ errors, 32% were attributed to BINDER usage or structure errors, and 15% to incorrect execution.
  • Interpretability: BINDER’s explicit programs can identify and potentially fix errors that end-to-end systems leave unexplained and pure SQL cannot express.The example attributes an incorrect answer to a value and operator error and suggests in-context exemplars or fuzzy-match postprocessing as possible fixes.
  • Scalability: As table size increases, end-to-end QA performance drops dramatically, whereas BINDER remains stronger with only slight decreases.BINDER receives only three table rows for all tested table sizes.
  • Extensions: BINDER extends beyond SQL to Python and multimodal QA, where it achieves better performance than end-to-end QA and a fine-tuned baseline under Codex few-shot evaluation.With oracle retrieval on MMQA, it reaches performance comparable to the state of the art.

5 RELATED WORK

Prior neural-symbolic methods combine neural modules with symbolic languages but generally rely on task-specific designs, limited semantic coverage, and substantial training data. BINDER instead uses flexible API calls with general programming languages and few annotations.

  • Limitations of Prior Work: These methods commonly require elaborate human-designed symbolic languages, calibrated neural modules, and large task-specific training datasets.Their customized languages and modules cover limited semantic phenomena within particular tasks and domains.
  • Neural-Symbolic Methods: Earlier neural-symbolic systems combine neural modules and symbolic languages to seek both performance and interpretability.Examples include systems that generate programs softly executed by neural modules or decompose tasks into simpler QA modules.
  • BINDER: BINDER uses general programming languages and a unified prompting API, requiring only dozens of annotations while targeting diverse questions.The framework is described as maintaining performance, input scalability, interpretability, and robustness to noisy content.

6 CONCLUSION

The paper presents BINDER as a training-free bridge between end-to-end and symbolic NLP, combining broad functionality with explicit executable programs. It reports strong benchmark performance and analyses across robustness, scalability, multimodality, and language extensions.

  • Conclusion: BINDER maps inputs to executable programs that bind a unified LM API to programming languages, combining end-to-end coverage with symbolic interpretability.Codex serves as both parser and the model called by API functions.
  • Conclusion: BINDER achieves state-of-the-art performance on WIKITQ and TABFACT using dozens of in-context demonstrations without additional training.The paper contrasts this setting with existing systems trained on thousands of task-specific examples and sometimes domain-specific pretraining.
  • Conclusion: The paper analyzes performance gains, robustness to large or noisy inputs, multimodal knowledge sources, and extension to Python.These analyses support BINDER as a language-model-focused integration of neural and symbolic paradigms.

7 REPRODUCIBILITY

The experiments use OpenAI Codex for both program generation and API execution, with 14 annotated in-context exemplars per dataset and released implementation materials.

  • Implementation: BINDER experiments use OpenAI Codex code-davinci-002 as both the program parser and the underlying model for API calls.The implementation reports prompt templates, dataset-specific hyperparameters, and additional details in the appendices.
  • Reproducibility: The source code and implementation materials are provided to support result reproduction.

A MORE IMPLEMENTATION DETAILS

BINDER uses Codex in parsing and execution, with prompts, in-context examples, table formatting, and majority voting tailored to each dataset. Its evaluator handling also accounts for semantically correct outputs that differ from exact gold-answer forms.

  • Prompt construction: BINDER prompts Codex to generate programs from task-specific instructions, schemas, table rows, questions, and in-context examples.Prompts may include CREATE TABLE schemas, three example rows, row identifiers, lowercased table contents, and parsed BINDER programs.
  • Prompt construction: End-to-end QA uses full table contents in in-context examples, while semantic parsing benefits only modestly from full-table input.The authors report full-table input as necessary for end-to-end QA but only a small bonus for semantic parsing.
  • Codex configuration: Codex is called in both parsing and execution, with parsing using dozens of demonstrations and execution using Codex as the underlying model for neural functionalities.The execution setup can use image captioning for images, while specialized models may replace Codex for functionalities such as VQA.
  • Neural-module prompts: Neural-module prompts use a shared pool of 50 annotated samples, retrieving eight similar demonstrations for each inference example.The retrieval setup supports functionality such as mapping a column to a question-specific derived column.
  • Majority vote strategy: BINDER uses answer-biased majority voting in TabFact, assigning four votes to entailment and one to refutation because minor SQL errors can produce refuted outputs.This strategy is one of two voting variants used in the experiments.
  • Evaluator handling: WIKITQ evaluation adds pre-matching logic for yes/no and number-with-unit answers, and normalizes dates before judging program outputs.These adjustments address cases where executions are semantically correct but do not exactly match annotated answer strings.

C.2 RESULTS WITH WIKITQ OFFICIAL EVALUATORS

Under the official WIKITQ evaluator, BINDER and symbolic SQL methods lose more accuracy than end-to-end methods because certain semantically correct answer forms are judged incorrect.

  • Official evaluation: About 2.5% of symbolic SQL and BINDER performance drops under the official evaluator, compared with about 1% for end-to-end methods.The affected cases include A-or-B choice answers and answers containing units.

C.3 ABLATION STUDY OF #MAJORITY VOTE CANDIDATES

Increasing the number of candidate programs improves majority-vote performance on WIKITQ and TABFACT, while the authors describe additional scalability and domain-extension procedures.

  • Candidate ablation: Increasing majority-vote candidates effectively improves performance on both WIKITQ and TABFACT.The authors note that TABFACT requires more candidates to determine entailment or refutation and did not test WIKITQ beyond 20 candidates.
  • WIKITQ analysis: BINDER’s WIKITQ advantage also appears on the program-solvable subset because original SQUALL annotations used normalized tables and missed some solvable cases.Re-executing SQL annotations on normalized tables changes the estimated program-solvability partition.
  • Domain extension: Extending BINDER to a new domain involves selecting a programming language, providing in-context examples, generating programs, binding neural modules, and executing them.SQL is presented for tables, SPARQL or Cypher for knowledge graphs, and general-purpose languages for broader domains.
  • Domain extension: A dozen BINDER annotations can suffice for Codex to learn a modified grammar, while retrieving more examples can improve parsing accuracy.The paper gives a larger annotated pool, such as 100 examples, as an example of retrieval-based expansion.
  • Neural modules: Codex can serve as the underlying model for commonsense QA and information extraction, while specialized models may be bound for functions such as VQA.The paper uses Codex for all neural functionalities in its main setup.
  • Domain extension: The BINDER programs are executed with a deterministic language executor together with the bound neural models.

E.1 ERROR TYPES

The error analysis separates syntax, component-selection, BINDER-usage, execution, and annotation-related failures, while the interface supports real-time SQL and BINDER execution.

  • Error types: BINDER syntax errors include wrong columns, values, operators, overall query structure, or missing or improper BINDER usage.
  • Error types: Incorrect execution occurs when a predicted program is correct but intermediate neural-module answers or corner-case handling produce a wrong final result.
  • Error types: False negatives include incorrect gold annotations or predictions that are right but judged wrong because of executor limitations.
  • Annotation interface: The annotation interface supports real-time execution for SQL and BINDER with SQL and is intended for tasks involving symbolic languages.The paper demonstrates the interface with WIKITQ and TABFACT examples.
Loading 2210.02875v2…