How Proficient Are Large Language Models in Formal Languages? An In-Depth Insight for Knowledge Base Question Answering

Jinxin Liu; Shulin Cao; Jiaxin Shi; Tingjian Zhang; Lunyiu Nie; Linmei Hu; Lei Hou; Juanzi Li

Source-linked AI summary

How Proficient Are Large Language Models in Formal Languages? An In-Depth Insight for Knowledge Base Question Answering

Jinxin Liu, Shulin Cao, Jiaxin Shi, Tingjian Zhang, Lunyiu Nie, Linmei Hu, Lei Hou, Juanzi Li

arXiv:2401.05777v2Jan 11, 2024cs.CL

TL;DR

KBQA semantic parsing translates natural-language questions into executable logical forms, but differences in LLM proficiency across formal languages have received little discussion. The paper evaluates LLM understanding and generation across such languages using in-context learning. LLMs approach human annotators in understanding, while generation remains challenging, and performance varies with the formal language.

Problem
There has been little discussion of how LLM proficiency differs across formal languages used as semantic-parsing targets, despite the relevance of such differences to choosing models and languages for specific scenarios.
Source: §1 · p. 1
Method
The paper evaluates LLM understanding and generation by prompting conversions between natural-language questions and logical forms in different formal languages, without additional fine-tuning.
Source: §1 · p. 1
Results
LLMs approach human annotators at understanding logical forms, but generating correct forms from a few examples remains challenging; KoPL performs best in nearly all experiments and is described as most LLM-friendly among the languages studied.
Source: §1 · p. 2, §8 · p. 9
Takeaways & Limitations
The findings support considering formal-language choice in LLM reasoning and KBQA, with the study identifying KoPL as the most LLM-friendly language among those examined.
Source: §8 · p. 9
The study does not systematically examine code-pretrained models and evaluates LLM proficiency in formal languages as a whole rather than through more detailed tasks such as completion.
Source: Limitations · p. 9

Abstract

from arXiv · show

Knowledge Base Question Answering (KBQA) aims to answer natural language questions based on facts in knowledge bases. A typical approach to KBQA is semantic parsing, which translates a question into an executable logical form in a formal language. Recent works leverage the capabilities of large language models (LLMs) for logical form generation to improve performance. However, although it is validated that LLMs are capable of solving some KBQA problems, there has been little discussion on the differences in LLMs' proficiency in formal languages used in semantic parsing. In this work, we propose to evaluate the understanding and generation ability of LLMs to deal with differently structured logical forms by examining the inter-conversion of natural and formal language through in-context learning of LLMs. Extensive experiments with models of different sizes show that state-of-the-art LLMs can understand formal languages as well as humans, but generating correct logical forms given a few examples remains a challenge. Most importantly, our results also indicate that LLMs exhibit considerable sensitivity. In general, the formal language with a lower formalization level, i.e., the more similar it is to natural language, is more friendly to LLMs.

1 Introduction

The paper studies how well LLMs understand and generate formal languages used in KBQA semantic parsing, where questions are translated into executable logical forms. It compares these abilities across formal languages using in-context learning, addressing a gap in knowledge about models’ proficiency and its relevance to choosing models and languages for specific scenarios.

1 Introduction

The paper evaluates original LLMs’ formal-language understanding and generation without additional fine-tuning, using conversion between logical forms and natural-language questions.Understanding converts a logical form to a question; generation converts a question to a logical form.Source: §1 · pp. 1–2
The study examines Lambda DCS, SPARQL, and KoPL, selected to represent different formalization levels and logical structures.The languages vary in their similarity to natural language and in structures such as trees, graphs, or chains.Source: §1 · p. 2
In-context learning and chain-of-thought generation condition outputs on a few demonstration pairs selected to resemble the target’s logical structure.A greedy minimum-edit-distance search is designed to solve a maximum-coverage problem when selecting demonstrations.Source: §1 · p. 2
Generated-question quality is assessed by comparing parsers trained on LLM-generated questions with parsers trained on manually labeled data.The paper motivates this contrastive evaluation as an alternative to unreliable text-similarity metrics and labor-intensive human evaluation.Source: §1 · p. 2
LLMs approach human annotators when translating logical forms into natural-language questions, but generating correct logical forms from a few examples remains challenging.The findings also report sensitivity to the formal language, with less-formalized, more natural-language-like forms generally easier to understand and generate.Source: §1 · p. 2

2 Related Work

Prior KBQA work includes retrieval-based and semantic-parsing approaches, while question generation and language-model evaluation have developed along related lines. This paper extends LLM evaluation to formal languages used in semantic parsing.

Knowledge Base Question Answering

KBQA methods include retrieving relevant triples or subgraphs and translating questions into logical forms executable against knowledge bases.Semantic-parsing methods may use graph searching and generation or sequence-to-sequence models trained on parallel data.Source: §2 · p. 2

Knowledge Base Question Generation

Earlier KBQG approaches used templates or neural models, while later work used LLM few-shot learning and chain-of-thought to generate questions from formal languages.This paper adapts the latter idea for its formal-language understanding task.Source: §2 · p. 2

Evaluation of LLMs

LLM evaluation has expanded from probing language and world knowledge to comprehensive task and dataset benchmarks.The paper extends this evaluation from natural language to various formal languages.Source: §2 · p. 3

3 Evaluation Task Definition

The paper defines two probing tasks for evaluating LLMs’ handling of formal languages: converting logical forms into questions and converting questions into logical forms. It evaluates generated questions indirectly through downstream parser performance and evaluates generated logical forms for correctness or answer accuracy.

3 Evaluation Task Definition

The evaluation defines formal-language understanding and formal-language generation as two probing tasks for LLMs.Understanding maps logical forms to natural-language questions; generation maps questions to logical forms.Source: §3 · p. 3, §3.1 · p. 3, §3.2 · p. 3

3.1 Formal Language Understanding

Generated-question quality is evaluated indirectly because BLEU and BERT-Score are considered unreliable for comparing text similarity.The approach compares a parser trained on model-generated questions with one trained on manually labeled questions.Source: §3.1 · p. 3

3.2 Formal Language Generation

For formal-language generation, the model translates a question into a logical form, which is assessed by exact match or executor answer accuracy.The generated logical form should be correct and semantically equivalent to the input question.Source: §3.2 · p. 3

4 Formal Language and Datasets

The study evaluates three formal languages with different structures and degrees of natural-language similarity, pairing each with a dataset and knowledge base. KoPL is described as more modular and human-readable than the other languages.

4 Formal Language and Datasets

Lambda DCS is a tree-structured language derived from lambda calculus, and the study uses the Overnight dataset with over 13,000 examples across eight Freebase domains.The dataset follows the standard split.Source: §4 · p. 3
SPARQL represents relations between entities as graph-structured triples, and the study uses GrailQA, with over 50,000 Freebase entries and entity-linking results.The study follows the dataset’s standard split.Source: §4 · pp. 3–4
KoPL combines symbolic functions into chain-structured programs, and the study uses KQA Pro, a Wikidata-based dataset with over 100,000 entries.KoPL functions represent atomic knowledge-base operations; each KQA Pro entry includes a question and corresponding KoPL and SPARQL query.Source: §4 · p. 4
KoPL is described as more modular and human-readable, with identifiers and function inputs closer to natural language than those in the other languages.KoPL and Lambda DCS can both potentially reflect chain-of-thought reasoning better than SPARQL.Source: §4 · p. 4

5 Implementation

The implementation probes LLMs with in-context examples selected for structural similarity and shared content. For generation, it adds entity-label guidance and a two-step skeleton-then-parameter procedure.

5.1 Formal Language Understanding

The understanding task retrieves logical-form/question pairs whose logical forms resemble the target in structure and relations.The overall implementation orders selected examples by similarity in the prompt.Source: §5.1 · p. 4, §5 · p. 4

5.1.1 Structure-Preserving Principle

For understanding, logical forms are converted into tree-like skeletons, and examples are ranked by edit distance as a practical substitute for tree edit distance.The authors report that grammar restrictions make small-distance candidates from the two methods almost the same.Source: §5.1.1 · pp. 4–5

5.1.2 Content-Preserving Principle

Demonstrations are selected first for structural similarity and then for shared content, with a greedy search covering labels absent from the target’s examples.After k steps, the method has selected k skeleton candidates; relations and entities can also contribute to shared content.Source: §5.1.2 · p. 5

5.2 Formal Language Generation

The generation setup retrieves structurally similar questions with BM25, masking entities and relations so conjunctions and prepositions can signal structure.The authors avoid embedding-based search because it may prioritize semantics over structure and also consider calculation speed.Source: §5.2 · p. 5

5.2.1 Entity Linking

Entity-linking techniques address frequent errors in generated knowledge-base entity and relation labels.The method retrieves related entities and relations before generation, then checks generated labels against knowledge-base names afterward.Source: §5.2.1 · p. 5

5.2.2 Chain-of-Thought Generation

A multi-step chain-of-thought approach generates a logical-form skeleton first, then fills its parameters.The authors adopt this approach because direct logical-form generation is difficult.Source: §5.2.2 · p. 5

6 Experiment Setup

The experiments investigate models of different sizes and use semantic parsers to evaluate the formal-language-understanding task. Parser choice varies by formal language and dataset.

6 Experiment Setup

The experiment setup introduces popular language models and semantic-parsing models for evaluating the understanding task.The model-scale investigation is described as examining capacity across different model sizes.Source: §6 · p. 5, §6.1 · p. 5

6.1 Investigated Models

Models of different sizes are selected to investigate how scale relates to capacity, spanning medium-sized and larger language-model families.The tested set includes GPT, FLAN-T5, Llama-2, text-davinci, and GLM models.Source: §6.1 · pp. 5–6

6.2 Evaluation Models

Evaluation uses semantic parsers chosen for each formal language and dataset, including BART-base, a bidirectional LSTM, and two SPARQL/GrailQA baselines.The two latter baselines are BART-base generation without explicit entity linking and a rank-and-generate pipeline with entity linking.Source: §6.2 · p. 6

7 Results and Analyses

The results compare LLMs’ understanding and generation of different formal languages, then probe zero-shot, low-resource, and same-dataset settings. Across these analyses, model performance varies with formal language, and direct logical-form generation remains harder than understanding.

7.1 Formal Language Understanding Result Analysis

All models show some formal-language understanding, larger models generally perform better, and performance is closer to human level on KoPL and SPARQL than on other languages.The authors report no significant difference between instruction-tuned and non-instruction-tuned models; model size has a more pronounced impact.Source: §7.1 · p. 6
FLAN-T5 performs worse than similarly sized models, and its performance deteriorates as model size increases.The authors report that FLAN-T5-XXL’s generated results are almost unintelligible.Source: §7.1 · p. 6

7.2 Formal Language Geration Result Analysis

Compared with their understanding ability, language models’ direct logical-form generation is much worse: even the most powerful model achieves only 15% to 50% accuracy against a parser trained on its generated data.Source: §7.2 · p. 7
More in-context examples notably improve KoPL generation but have limited effect on SPARQL and Lambda DCS; adding entity and relation names particularly improves SPARQL.Across settings, performance is best on KoPL, intermediate on SPARQL, and worst on Lambda DCS.Source: §7.2 · p. 7, Figure 3 · p. 7
The authors attribute KoPL’s advantage to its natural-language similarity and chain-like reasoning order, while SPARQL’s simpler grammar and entity-binding bottleneck help explain its results and response to entity hints.The SPARQL queries in GrailQA largely follow the same pattern; supplying entity and relation names addresses the stated binding bottleneck.Source: §7.2 · pp. 7–8

7.3 Zero-shot Understanding

Without retrieved examples, Text-Davinci-003 still shows understanding ability, but its performance drops by 25.8%.The comparison indicates that the carefully designed retrieval strategy contributes significantly to generated-question quality.Source: §7.3 · p. 8, Table 2 · p. 8

7.4 Different Seed Set Ratio

With 1% of KQA Pro’s training set as seeds, generated-question quality declines, but the resulting performance degradation is described as acceptable given the reduction in seed data.The experiment uses KQA Pro, the largest and most diverse dataset in the paper.Source: §7.4 · p. 8

7.5 All Formal Languages on One Dataset

On one dataset, results are overall consistent with the main findings, though generation performance drops somewhat when SPARQL entity and relation binding is skipped.The comparison uses KQA Pro and translates KoPL into Lambda DCS.Source: §7.5 · p. 8, Table 3 · p. 8

8 Conclusion

LLMs’ ability to generate structured semantics is notably weaker than their ability to understand them, and performance varies across formal languages. KoPL performs best in nearly all experiments, which the authors associate with its greater similarity to natural language while retaining structure and modularity.

LLMs’ ability to generate structured semantics is notably inferior to their ability to understand them.Source: §8 · p. 8
The choice of formal language and knowledge base can significantly influence model performance.Source: §8 · p. 9
KoPL yields the best results in nearly all experiments, and its natural-language-like expressions preserve structure and modularity.Source: §8 · p. 9
The authors recommend prioritizing formal languages that more closely resemble natural language, as a medium between LLMs and knowledge bases for QA and reasoning.Source: §8 · p. 9

Limitations

The authors identify limits in model coverage and task granularity, and describe probing procedures and findings across the appendix’s methods and results. Their formal-language understanding analysis reports differences by model size, language, and model family.

Limitations

The study omits a systematic evaluation of code-pretrained models and examines formal-language proficiency as a whole, leaving more detailed tasks such as completion for future work.Source: Limitations · p. 9

A.1 Formal Language Understanding

For formal-language understanding demonstrations, KoPL skeletons remove function inputs and are serialized by post-order traversal; Lambda DCS and SPARQL use bracket-tree forms.Source: §A.1 · p. 14

A.2 Formal Language Generation

For generation demonstrations, the prompt first produces an NLQ skeleton from a question with entities and relations masked, then adds arguments.Source: §A.2 · p. 14

A.3 Zero-shot Understanding

Table 8 presents the prompt used in the zero-shot understanding experiment.Source: §A.3 · p. 14

B.1.1 Performance of Different Models

Larger models generally perform better in formal-language understanding, while smaller models perform better on KoPL than on SPARQL or Lambda DCS.Source: §B.1.1 · p. 14
The FLAN-T5 series generalizes poorly to formal languages not seen during pretraining, and larger models produce lower-quality natural-language questions.Source: §B.1.1 · pp. 14–15

B.1.2 Error Types on KoPL

The appendix details error patterns in KoPL, SPARQL, and Lambda DCS generation, and specifies the experiment environment. For KoPL, errors depend partly on the structural match between retrieved examples and the input.

B.1.2 Error Types on KoPL

When retrieved KoPL examples have the same skeleton as the input, outputs are usually good, though hallucinated components sometimes remain; mismatched skeletons make hallucinations more likely.Source: §B.1.2 · p. 15

B.2 Formal language Generation

The generation-error analysis focuses on Text-Davinci-003 because most small models produce outputs that are usually meaningless.Source: §B.2 · p. 15

B.2.1 KoPL

Text-Davinci-003’s KoPL errors are mainly logical, including inappropriate functions or incorrect function inputs and order.Source: §B.2.1 · p. 15

B.3 SPARQL

On GrailQA, SPARQL errors mainly involve entity and relation names, especially generating the correct Freebase MID before alignment.Source: §B.3 · p. 16

B.4 Lambda DCS

Lambda DCS generation errors include both logical errors and naming errors.Source: §B.4 · p. 16

C.1 Experiment Environment

Experiments used up to four Nvidia A100 GPUs; generating the 10,000-entry KQA Pro dataset for understanding took up to 30 hours on one GPU.Source: §C.1 · p. 16

C.2 Semantic Parser for Evaluation

The appendix describes the semantic parsers used to evaluate formal-language understanding, the shared generation settings, and additional results by question type. Those results indicate that investigated models approach human understanding on simple problems but lag on difficult ones.

C.2 Semantic Parser for Evaluation

The understanding evaluation uses BART-base for KoPL and SPARQL, a rank-and-generation parser for SPARQL, and a baseline semantic parser for Lambda DCS.Source: §C.2 · pp. 16–17

C.3 LLMs Generation

Both probing tasks use beam search with beam size 5 and three demonstration examples, alongside top k 50, top p 0.9, and temperature 1.Source: §C.3 · p. 18

D.1 Detailed Analysis on LLMs’ Understanding on Different Question Types

The additional question-type analysis compares parsers trained on model-generated data with parsers trained on human-labeled data across seven KQA Pro question types.Source: §D.1 · p. 18
Assuming human annotations are fully correct, investigated models approach human understanding on simple problems but perform much worse on difficult ones.Source: §D.1 · p. 18

D.2 Detailed Results of the LLMs’ Generation Ablation Experiment

The appendix reports a Text-Davinci-003 generation ablation varying the number of demonstrations and use of entity linking, and supplies related performance tables and logical-form examples across tasks and formal languages.

D.2 Detailed Results of the LLMs’ Generation Ablation Experiment

Performance tables cover formal-language understanding on KoPL, SPARQL, and Lambda DCS, including a breakdown by seven question types.The listed types are Multi-hop, Qualifer, Compare, Logical, Count, Verify, and Zero-shot.Source: Table 9 · p. 20, Table 10 · p. 20, Table 11 · p. 21

EXAMPLE 1

Across four KoPL examples, GLM-130B has an excellent output with matching retrieved-example skeletons and hallucinated outputs with either matching or nonmatching retrieved-example skeletons.Tables 16 and 17 give Text-Davinci-003 error cases for KoPL and SPARQL formal-language generation.Source: Table 12 · p. 21, Table 13 · p. 22, Table 14 · p. 22
The examples include logical-form input/output pairs, including one output explicitly marked incorrect.The appendix also includes a natural-language question about Kobe Bryant’s points in the 2004 season and its logical form.Source: §D.2 · p. 21, EXAMPLE 1 · pp. 23–24

D.2 Detailed Results of the LLMs’ Generation Ablation Experiment

Table 20 reports Text-Davinci-003 generation results for varying demonstration counts and entity-linking use, based on three evaluations of sampled data.The supplied passage identifies the table's scope but does not provide its cell values.Source: §D.2 · p. 18, Table 20 · p. 24