Semantic parsing

Overview

Semantic parsing maps natural language to a formal representation, such as SQL, an intermediate program or a logic formula, that a deterministic system then runs. The parser has to work out what the words refer to inside that formal language. For a table, that means the column names and cell values the question mentions 2005.08314 §1. For a logic problem, it means the entities, facts and rules in the text 2305.12295 §3.1.

Four papers with cards fit this definition in different ways, and a fifth describes the input side. A controlled natural language is an English-based language with fixed rules, and some are designed for formal representation. The survey classifies them, and rates the formal-representation ones on precision, expressiveness, naturalness and simplicity 1507.01701 §3 1507.01701 tab. 3. TaBERT is a trained encoder that a semantic parser uses over tables. The question and the table are encoded together so the parser can align the words with the columns and cells 2005.08314 §1 2005.08314 §4. Logic-LM uses no trained parser: a prompted large language model rewrites the problem into a formal program, and a symbolic solver executes it 2305.12295 §3. The two targets also differ: TaBERT's parsers emit SemQL for Spider and logical forms for WikiTableQuestions 2005.08314 §4, while Logic-LM targets four logic languages 2305.12295 tab. 1. The two remaining cards are about knowledge bases and prompting. A knowledge-base parser maps a question to a logical form that a knowledge base can execute 2011.07743 §2.1. The retriever in EPR does not parse at all: it chooses the examples that an LLM parser sees in its prompt 2112.08633 §3.2.

Variants

Table-aware encoder with sampled rows (TaBERT)

The encoder is BERT, further pretrained on 26.6M table-and-text pairs: 1.3M Wikipedia tables and 25.3M WDC tables, each with nearby text [arxiv:2005.08314 §3.2] 2005.08314 app. A.1. For a question, the encoder first picks K rows of the table by n-gram overlap with the question, with n at most 3 2005.08314 §3.1. Each row becomes one sequence: the question tokens, then one string per cell that holds the column name, a data type (text or real) and the value 2005.08314 §3.1 2005.08314 eq. 1. BERT encodes each row separately. Three vertical self-attention layers then link the rows at each position 2005.08314 §3.1 2005.08314 §5.

Pretraining sums three losses: masked language modelling, masked column prediction (20% of columns have their names and types masked), and cell value recovery 2005.08314 §3.2 2005.08314 app. A.2. As an encoder it replaces the LSTM in MAPO for WikiTableQuestions. For Spider it feeds a TranX-based parser that emits SemQL 2005.08314 §4.2 [arxiv:2005.08314 §4.1]. On WikiTableQuestions, MAPO with TaBERT-Large and K = 3 reaches 51.8 test mean (± 0.6), and 52.3 for the run that was best on dev, against 46.9 for the previous ensemble of 10 2005.08314 tab. 1. On Spider dev, the TranX parser with TaBERT-Large and K = 3 reaches 64.5 mean (± 0.6), below RyanSQL with BERT at 66.6 in the same table 2005.08314 tab. 2. Card: TaBERT.

Generic BERT encoder (paper's baseline)

The same parsers with an off-the-shelf BERT encoder, which is not pretrained on tables. With BERT-Base and K = 1, MAPO reaches 49.6 ± 0.5 dev mean on WikiTableQuestions, against 51.2 ± 0.5 for TaBERT-Base with K = 1 2005.08314 tab. 1. On Spider dev, TranX reaches 61.8 with BERT-Base and 63.3 with TaBERT-Base, both at K = 1 2005.08314 tab. 2. Feeding only column names to BERT gives 49.0 on WikiTableQuestions dev and 58.6 on Spider dev 2005.08314 tab. 4. Card: TaBERT.

LLM as formulator with a symbolic solver (Logic-LM)

No trained parser here. A prompted LLM turns the problem and the goal into one of four formal languages: logic programming, first-order logic, constraint satisfaction, or satisfiability modulo theories (SMT). Each has its own solver: Pyke, Prover9, python-constraint and Z3 2305.12295 §3.1 [arxiv:2305.12295 tab. 1]. The demonstrations pair each formula with its source sentence, so the alignment between words and symbols is explicit 2305.12295 §3.1. The solver then executes the program and returns the answer 2305.12295 §3.2.

If the solver reports an execution error, the LLM gets the faulty program, the error message and examples of common mistakes, and rewrites the program. This repeats until the program runs or a revision limit is reached [arxiv:2305.12295 §3.3]. The paper does not state the limit in the text 2305.12295 §3.3. If the program still cannot run, the paper falls back to chain-of-thought prompting 2305.12295 §4.1.

With GPT-4, the authors report accuracy of 83.20 on PrOntoQA against 98.79 for chain-of-thought. On ProofWriter (79.66 against 68.11), FOLIO (78.92 against 70.58), LogicalDeduction (87.63 against 75.25) and AR-LSAT (43.04 against 35.06), the same model with Logic-LM is ahead 2305.12295 tab. 2. With GPT-3.5, self-refinement raised the share of FOLIO programs the solver executes from 66.7% to 84.3%, and accuracy on executed programs from 61.8 to 64.3. The table header says only "GPT-3.5" 2305.12295 tab. 3. Card: Logic-LM.

Schema-aware seq2seq parser with candidate ranking (GrailQA)

A BERT-based parser for knowledge base question answering. BERT reads the question together with the names of the schema items: relations, classes and functions 2011.07743 §4.2 2011.07743 §2.2. The paper compares two decoding modes. Transduction generates an S-expression token by token from a vocabulary pruned to items within two hops of the linked entities 2011.07743 §4.2. Ranking enumerates candidate logical forms that use at most two relations and start from a linked entity, then returns the best-scoring one 2011.07743 §4.4.

The two modes trade coverage for flexibility. Candidates reach about 80% recall on the dataset, so ranking cannot return a query outside its set. Questions with superlatives or comparatives often have no topic entity and fall outside it 2011.07743 §4.4. On the GrailQA test set, ranking reaches 58.0 overall F1 against 36.8 for transduction. On zero-shot questions it reaches 55.7 F1 with BERT and 33.8 without 2011.07743 tab. 3. The authors name BERT as the main factor for compositional and zero-shot results 2011.07743 §5.3. Without BERT, ranking scores higher on i.i.d. exact match, 62.2 against 59.9 2011.07743 tab. 3. Entity linking with BERT reaches 72.2 F1 on GrailQA, against 17.2 for Aqqu [arxiv:2011.07743 §4.3]. In a sample of 100 errors, 33% came from entity linking and 34% from coverage 2011.07743 §5.4. Card: Beyond I.I.D..

Retrieved in-context examples for an LLM parser (EPR)

No parser is trained here. The method trains a small retriever that picks the few-shot examples shown to a language model, which then writes the logical form. Two BERT-base encoders make up the retriever: one reads the question and the other reads example pairs 2112.08633 §3.2. The training labels come from a scoring LM. For each training example, BM25 over the output proposes 50 candidates. The scoring LM rates each candidate by how likely it makes the gold output. The top five become positives and the bottom five hard negatives 2112.08633 §3.1 2112.08633 §4.2. The scoring LM is GPT-Neo 2.7B 2112.08633 §4.3. At test time, one vector search over the training examples returns the prompt 2112.08633 §3.2.

On BREAK development data with GPT-Neo as scorer and inference LM, the method reaches 31.9 LF-EM. BM25 reaches 26.0 and CBR, the best supervised baseline, 25.7 2112.08633 tab. 2. On MTOP it reaches 64.2 EM against 57.0 for CBR 2112.08633 tab. 2. With a larger model doing inference on a 1,000-example development sample, it is ahead of every baseline in every row of the table. For example, on BREAK with GPT-3 it reaches 25.3 against 21.3 for CBR 2112.08633 tab. 5. Each row is a single run, with no variance reported 2112.08633 §4.3. Labelling scores each candidate separately, so the cost grows with the candidate set. Scoring all pairs of training examples would be quadratic and prohibitive 2112.08633 §3.1. Card: Learning To Retrieve Prompts for In-Context Learning.

Controlled natural language as the input (CNL survey)

This is not a parser. It is a constraint on the input text, which is written by people and then read by a deterministic translator. A controlled natural language (CNL) is based on one natural language, is more restrictive than it in lexicon, syntax or semantics, keeps most of its natural properties, and is explicitly constructed 1507.01701 §2.1. The survey's naturalness boundary for a CNL is N3 or higher 1507.01701 §3.3. Languages with formal-representation or automatic-execution intent carry the property code f 1507.01701 tab. 1. The survey places 54 catalogued CNLs in this group. Their average scores are 4.4 for precision, 2.3 for expressiveness, 3.8 for naturalness and 3.2 for simplicity 1507.01701 tab. 3. Compared with the comprehensibility group (precision 2.0, expressiveness 4.3), they are more precise and less expressive 1507.01701 tab. 3. The survey reads the catalogue as one connected cloud between English and propositional logic, not as separate groups 1507.01701 §5.1. The survey reports no parsing accuracy, so it gives no evidence on how well a CNL parser performs. Card: A Survey and Classification of Controlled Natural Languages.

When to use which

Use the WikiTableQuestions test figure with care: 52.3 is the run that was best on dev, and the mean is 51.8 2005.08314 tab. 1.

Implementation sketch

Our own pseudocode for each family's core. The parser is the variant. For TaBERT, the parser on top (TranX or MAPO) is not described in this card.

TaBERT encoder:

# 1. Pick the K rows with most n-gram overlap with the question, n <= 3
#    [arxiv:2005.08314 §3.1]
snapshot = top_k_rows_by_ngram_overlap(question, table, k=3)

# 2. One sequence per row: question tokens, then "column | type | value"
#    cell strings joined by a separator [arxiv:2005.08314 §3.1] [eq. 1]
for row in snapshot:
    sequence = question_tokens + join(cell_strings(row), SEP)

    # 3. Encode the row with BERT, mean-pool each cell's tokens [§3.1]
    token_vectors = bert(sequence)

# 4. Vertical self-attention across rows at each position, 3 layers [§3.1] [§5]
hidden = vertical_attention(stack_rows(token_vectors), layers=3)

# 5. Pool over rows: one vector per column, one per question token [§3.1]
column_vectors = mean(hidden[cell_positions], axis=rows)
question_vectors = mean(hidden[question_positions], axis=rows)

# 6. Hand both to the parser: TranX for Spider, MAPO for WikiTableQuestions
#    [arxiv:2005.08314 §4.1] [arxiv:2005.08314 §4.2]

LLM formulator with a solver:

# 1. Choose the formal language from the problem type [arxiv:2305.12295 §3.1]
#    [tab. 1]
language = formalism_for(problem.kind)

# 2. Few-shot translation of the problem and goal into that language [§3.1]
program = formulator.translate(problem, goal, language)

# 3. Run the deterministic solver on the program [arxiv:2305.12295 §3.2]
answer, error = solver.execute(program)
for _ in range(max_revisions):
    if answer is not None:
        break
    # 4. Rewrite the program from the solver's error message [§3.3]
    program = formulator.refine(program, error)
    answer, error = solver.execute(program)

# 5. Fall back when no answer is produced: chain-of-thought in the paper [§4.1]
if answer is None:
    return fallback(problem, goal)

# 6. Map the solver's result onto an option [arxiv:2305.12295 §3.4] [app. D]
return option_for(answer, goal)

Contradictions

No direct disagreement: the papers report different tasks, datasets and models, so their numbers are not comparable. Inside the papers:

• EPR copy-analysis totals. Table 7 gives total accuracy of 32.3% on BREAK and 54.5% on SMCalFlow for the GPT-Neo setting. The main table gives 31.9 and 54.3 for the same setting 2112.08633 tab. 2 2112.08633 tab. 7. The paper does not explain the difference. Not resolved here; see the EPR card.
• Logic-LM headline averages. The abstract gives 39.2% over standard prompting and 18.4% over chain-of-thought. §4.1 attributes the 39.2% to GPT-3.5 alone 2305.12295 §4.1. Some gains in §4.1 cannot be reproduced from tab. 2 2305.12295 tab. 2. Not resolved here; see the Logic-LM card.
• TaBERT Spider numbers are dev-set numbers, not test numbers 2005.08314 tab. 2.
• TaBERT paper and code differ in how rows are chosen at inference and in other details 2005.08314 §3.1. Those differences are listed on the TaBERT card, not resolved here.

Papers

• TaBERT: Pretraining for Joint Understanding of Textual and Tabular Data: a BERT encoder pretrained on tables, with K-row sampling and vertical attention, plugged into two semantic parsers.
• Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases: a BERT-based parser for knowledge base QA, in transduction and ranking modes, with the GrailQA dataset for three levels of generalization.
• Learning To Retrieve Prompts for In-Context Learning: a BERT retriever, trained on labels from a scoring LM, picks the few-shot examples an LLM parser sees.
• Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning: an LLM writes a formal program, a symbolic solver runs it, and failing programs are rewritten from the solver's error.
• A Survey and Classification of Controlled Natural Languages: a survey of 100 English-based controlled natural languages, with a four-dimension classification (PENS) and no algorithm or experiments.