Binding Language Models in Symbolic Languages

In plain words

Some questions are easy to answer with a short program, such as a SQL query over a table, but the program's language has no operator for the rest. "Which of these countries is in North America?" is one example: a database cannot know that from the country names alone. Binder lets the model write the program anyway, and leave a placeholder where the missing knowledge goes.

That placeholder is a call back to the same language model, asking it a small question about a few cells or columns. The program is then run like ordinary code, with the answers from those calls filled in. The model is shown only a few worked examples, so nothing is trained. Several programs are written for each question and their results are compared by vote. Because the output is an explicit program, a wrong answer can be traced to the step that caused it.

TL;DR

• Binder maps a question and table to a SQL or Python program in which some sub-expressions are calls to a language model (LM) §2.1.
• It needs only a few annotated program exemplars and no training; the paper uses Codex (code-davinci-002) for both parsing and the LM calls §2.2 §3.1.
• It reports state-of-the-art execution accuracy on WikiTQ and TabFact among the systems it compares with, but these are author-reported and depend on the evaluator (see Pitfalls).

Problem

Fine-tuned end-to-end models beat symbolic parsers on table benchmarks, but symbolic programs cannot express steps outside their grammar, and neural-symbolic systems so far needed a task-specific language and training data per domain §1. The paper also notes that about 20% of WikiTQ questions cannot be annotated in SQL §3.1; the later re-split in app. C.4 gives a much larger share, see Pitfalls.

Method

Framework. Given a question Q and optional context D, the parser produces an executable Binder program Z, and the answer A is obtained by running Z with a Binder interpreter §2.1. A program is an ordinary expression in a symbolic language (SQL, Python) that may contain API calls f(Q̂ ; D̂). Q̂ is the part of the question the language cannot answer, D̂ is the context needed for it, and the call's output is a variable the grammar accepts §2.1. Q̂ = Q or D̂ = D is also allowed; with both, the method reduces to end-to-end LM prompting §2.1.

Parsing. The LM is prompted with k annotated exemplars (Q_i, D_i, Z_i) and the test input. It returns n candidate programs §2.2. The paper states that the exemplars can be fixed or retrieved per input, and that k and n are hyperparameters §2.2.

Execution. The interpreter parses each program into a syntax tree whose leaves may be API calls, evaluates the calls bottom-up so that nested calls work, and feeds each call's result back as a variable §2.1. The LM receives the call's Q̂ and D̂ as a prompt §2.2.

Voting. Each candidate program is executed, and the most frequent answer wins §2.2 app. A.3. The paper says this is similar to MBR-EXEC app. A.3.

SQL implementation. Two APIs are used §2.3:

• f_col(Q̂ ; D̂) maps a (sub-)table to a new column. It replaces a column name in the SQL, for example asking whether each country is in North America to form a yes/no column §2.3.
• f_val(Q̂ ; D̂) maps a sub-table to a single value, and sits where a value goes, for example in an ORDER BY or a comparison. It sees only the sub-table, which also limits input length §2.3.

The output of f_col must be a table, not a bare list, because the rows must stay aligned with their row ids app. A.2.

Python implementation. The same API is added to Python with Pandas, and the paper evaluates it only on the program-unsolvable subset §4.4.

Multimodal (MultiModalQA). Images are turned into text captions with OFA before prompting. For non-table questions the program calls f_val over a passage or image title §4.4 app. A.2.

# Binder inference for one question  [§2.2] [§2.1]
# Input:  question, table, k exemplars, n samples
# Output: answer

def binder_answer(question, table, exemplars, n):
    # Build a prompt from k exemplars and the test input  [§2.2]
    prompt = build_prompt(exemplars, question, table)
    # Sample n candidate programs from the LM  [§2.2] [app. A.2]
    programs = lm_sample(prompt, n=n)
    answers = []
    for program in programs:
        # Run each program; its API calls go back to the LM  [§2.1]
        answers.append(run_program(program, table))
    # Most frequent valid answer wins  [app. A.3]
    return majority_vote(answers)

# Interpreter for one Binder program  [§2.1] [§2.3]
# Input:  program text, table
# Output: answer

def run_program(program, table):
    # Parse with the grammar extended by the API call  [§2.1]
    tree = parse_extended_grammar(program)
    # Evaluate leaves first, so nested calls are allowed  [§2.1]
    for node in bottom_up(tree):
        if node is an API call:
            # Select the sub-table the call refers to  [§2.3]
            sub_table = select_columns(table, node.columns)
            # Ask the LM the sub-question; store the result as a variable  [§2.2]
            node.result = lm_call(node.question, sub_table)
    # Run the rest with a standard SQL or Python engine  [§2.1]
    return execute_standard(tree, table)

Hyperparameters

Codex hyperparameters for parsing and for the LM calls made during execution app. A.2. "Parsing" is program generation; "execution" is the API calls.

The API-call exemplars are chosen by BLEU similarity of question and table header; the header term has weight 0.2 in the code retriever.py. The paper does not give this weight app. A.2.

Results

Author-reported. Setup: Codex code-davinci-002 with 14 annotated exemplars (WikiTQ, TabFact) §3.1. Execution accuracy with the semantic-match evaluator §3.1 app. A.5. Baselines were fine-tuned models unless stated §3.1.

Main results, WikiTQ §3.2

The paper reports a gain of 1.3 points over the previous best (OmniTab, 63.3) on test §3.2.

Main results, TabFact (small test, 2,000 examples) §3.2

The retriever adds 0.9 points over fixed exemplars, which the paper calls comparatively small §3.2.

WikiTQ, official evaluator app. C.2: Binder reaches 62.6 dev and 61.9 test. OmniTab is 62.9 on test under the same evaluator, so the ranking flips.

Ablation, WikiTQ dev §4.1:

Codex end-to-end QA without table input scores 12.4 overall §4.1. Of 100 correct predictions shared by SQL and Binder on the program-unsolvable subset, the paper judged 12% spurious for Binder and 33% for SQL §4.1.

Error types, 100 WikiTQ dev errors for Binder (SQL) §4.2: syntax 5%; semantic 64% (incorrect column/value/operator 10%, wrong structure 22%, missing Binder API use 32%); incorrect execution 15%; false negative 16%.

Robustness §4.3: when 15% of gold-column cells are replaced with distractors, Binder drops 1.3 points and end-to-end QA drops 6.7 points. On expanded tables (100, 200, 500 rows), end-to-end QA degrades sharply, while Binder keeps only three table rows as input and degrades slightly. These two results are shown only in figures; no numbers are given in the text §4.3.

Python and MultiModalQA §4.4: on the program-unsolvable WikiTQ subset, Python with Binder API calls reaches 34.4 against 30.7 for plain Python. On MMQA dev (F1 / EM): Binder 57.1 / 51.0; with an oracle retriever 64.5 / 58.1; end-to-end QA 55.4 / 48.0; fine-tuned Implicit-Decomp 55.5 / 48.8; fine-tuned PReasM-Large 65.5 / 59.0.

Paper vs code

Code: HKUNLP/Binder at commit 287ab979506a1294c1c7cd6a1f34776f9dc832cf. The repository is linked from the abstract. Its owner is HKUNLP, the University of Hong Kong NLP group, and Tao Yu is listed with a University of Hong Kong affiliation. I did not run the code.

• Model. Paper: code-davinci-002 §3.1. Code default engine for both scripts is gpt-3.5-turbo annotate_binder_program.py execute_binder_program.py. The README says OpenAI no longer supports Codex and the engine was changed README.md.
• Exemplar count. Paper: 14 for WikiTQ and TabFact app. A.2. The WikiTQ command in run.py does not pass --n_shots, so the script default of 8 applies run.py annotate_binder_program.py. The commented TabFact command uses 18 run.py; the TabFact prompt file has 18 exemplars tab_fact_binder.txt.
• Parsing token limit. Paper: 512 for all datasets app. A.2. The commented TabFact command uses 256 run.py; the script default is 256 annotate_binder_program.py.
• Context budget. Paper: Codex input limit 8,000 tokens §3.1. The annotation script sets a total budget of 3,800 tokens and shrinks the exemplar count to fit annotate_binder_program.py annotate_binder_program.py.
• Answer-biased vote. Paper: 4 votes for "1", 1 for "0" app. A.3. The commented TabFact command uses weight 3 run.py. The weight multiplies the count utils.py.
• Program-biased vote. Paper: 10 votes per Binder program app. A.3. The code has lf_biased: 10 votes for a program containing map@ or ans@, 1 otherwise utils.py. No command in run.py uses it.
• Notation. Paper writes API calls as f(Q̂ ; D̂) §2.1 app. A.1. Code writes QA("map@<question>"; <columns>) for a column and QA("ans@<question>"; <sql>) for a value wikitq_binder.txt. Map and ans route to different branches of the QA module openai_qa.py.
• Execution retrieval. Paper: a BLEU retriever returns 8 exemplars app. A.2. Code also uses a header term with weight 0.2 retriever.py.
• Logprobs. Chat models return no logprobs; the code then sets logprob to 1 generator.py. The code's logprob tie-break is inert with these engines (see Pitfalls).
• Experiments not in the repo. run.py lists the analysis commands (scalability, robustness, Python) with no body run.py. The paper says the source will be released app. C.4; datasets for scalability are in datasets/.
• Repository state. run.py contains unresolved merge markers (<<<<<<< HEAD, =======, >>>>>>>) at lines 9, 18 and 27, so it will not run as written run.py run.py run.py.

Pitfalls

• The reported model is retired. Reproducing the paper needs code-davinci-002 or a substitute. The code's default is a chat model with no logprobs, so the numbers in the paper may not transfer. The paper does not discuss this.
• Ties in voting. The simple vote breaks ties by the first candidate's logprob utils.py. With chat models every logprob is 1, so ties are decided by the order in which answers first appear generator.py.
• Failed programs. Programs that error or return an empty answer are dropped from the vote utils.py. If all fail, the executor returns its placeholder, which defaults to 0 execute_binder_program.py rather than the function's string default utils.py.
• Execution is eval. A value sub-expression written by the LM is passed to Python's eval nsql_exec.py. Run programs in a sandbox.
• Cost. The paper samples 20 programs per question for WikiTQ and MMQA and 50 for TabFact app. A.2. Each program can contain several LM calls. It takes about 6 hours for 1,000 examples at 200 queries per minute §3.1. The number of calls per program is not stated.
• Non-determinism. Temperature 0 still gave different outputs between runs app. A.2.
• Split and metric. The authors re-derived the program-unsolvable split: 1,251 (44.19%) unsolvable and 1,580 solvable, against 625 (22.08%) in the SQUALL annotation app. C.4. The main text says "about 20%" §3.1 §4.1. Subset numbers depend on which split is used. Whether Binder ranks above OmniTab depends on the evaluator app. C.2.
• Evaluator. The paper's semantic-match evaluator accepts 1 for "yes", 0 for "no", one side of an "A or B" answer, and answers that differ only in a unit or date format app. A.5 evaluator.py. Other systems were re-run with it for fairness §3.1. The official evaluator changes the numbers by 1 to 2.5 points app. C.2.
• Exemplar selection. The paper uses 14 fixed exemplars on WikiTQ, while TabFact uses retrieval from a pool of 200 §3.1. The retrieval gain is small §3.2. Exemplar choice matters: the paper says the choice of examples is an open problem §3.2.
• Vague details. The paper does not give the SQL engine used, the seed, the hardware, the exact exemplar text for TabFact retrieval, or how the BLEU retriever weights columns app. A.2.

Lineage

• Builds on: Codex (code-pretrained GPT-3) as the LM §2.2; the MBR-EXEC voting idea app. A.3; the SQUALL SQL annotations for the solvable split §3.1.
• Compared against: Tapex, OmniTab, TaCube, T5-3B (UnifiedSKG), SASP, BART-Large §3.1 §3.2.
• Related paradigms the paper contrasts with: end-to-end prompting, chain-of-thought prompting, and semantic parsing or code generation app. B.