PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning

Tianle Xia, Liang Ding, Guojia Wan, Yibing Zhan, Bo Du, Dacheng Tao

arXiv:2405.01649v4cs.CL

TL;DR

Incomplete knowledge graphs leave missing facts, and prior embedding-based approaches are described as limited in using world knowledge for complex reasoning. LACT fine-tunes LLMs with binary-tree query decomposition and curriculum learning. It reports state-of-the-art performance beyond embedding- and PLM-based methods using 7B models, with gains over the previous SOTA on reported average metrics.

  • Problem

    Incomplete KGs leave missing triplets, and embedding-based methods are described as limited by insufficient information, underused semantics, query complexity, and graph-specific generalization.

    Source: Introduction · p. 1

  • Method

    LACT fine-tunes LLMs with KG-informed training data, binary-tree decomposition of logical queries, and curriculum learning across query difficulties.

    Source: Introduction · p. 2, Data Augmentation by Binary Tree… · p. 4

  • Results

    LACT achieves state-of-the-art performance beyond embedding-based and PLM-based methods using only 7B models, with average gains of 7.3% on avgp, 2.9% on avgodd, and 6.3% on avgn over the previous SOTA.

    Source: Introduction · p. 2, Main Results · p. 5

  • Takeaways & Limitations

    Across widely used KG datasets, the authors report LACT as an effective fine-tuning framework that can be applied to various LLM sizes and data sizes.

    Source: Conclusion · p. 7

Abstract

from arXiv · show

Answering complex queries over incomplete knowledge graphs (KGs) is a challenging job. Most previous works have focused on learning entity/relation embeddings and simulating first-order logic operators with various neural networks. However, they are bottlenecked by the inability to share world knowledge to improve logical reasoning, thus resulting in suboptimal performance. In this paper, we propose a complex reasoning schema over KG upon large language models (LLMs), containing a curriculum-based logical-aware instruction tuning framework, named LACT. Specifically, we augment the arbitrary first-order logical queries via binary tree decomposition, to stimulate the reasoning capability of LLMs. To address the difficulty gap among different types of complex queries, we design a simple and flexible logic-aware curriculum learning framework. Experiments across widely used datasets demonstrate that LACT has substantial improvements~(brings an average +5.5% MRR score) over advanced methods, achieving the new state-of-the-art.

Introduction

Incomplete knowledge graphs make complex logical queries difficult, while embedding-based methods have limited access to missing information and entity or relation semantics. LACT fine-tunes LLMs using KG-informed data, binary-tree decomposition, and curriculum learning, and the paper reports state-of-the-art performance with 7B models.

Introduction

  • Incomplete KGs leave triplets undiscovered, making complex logical reasoning over them a challenging task.The paper frames EFO1 queries as combining projection, negation, intersection, and union operators.Source: Introduction · p. 1
  • Embedding-based methods are described as limited by insufficient KG information, underused semantics, query complexity, and poor generalization across graphs.The paper notes that KG-specific embeddings may not generalize to graphs with different structure and content.Source: Introduction · pp. 1–2
  • Prompted LLMs can hallucinate on knowledge-intensive KG tasks, while manual query classification and decomposition increase practical constraints and reasoning cost.The authors therefore prefer fine-tuning over pure prompt engineering.Source: Introduction · p. 2
  • LACT incorporates KG knowledge into its training corpus, uses binary-tree decomposition to improve reasoning, and applies curriculum learning to smooth query-difficulty differences.The paper reports that curriculum learning improves results on difficult queries.Source: Introduction · p. 2
  • LACT is reported to achieve state-of-the-art performance beyond embedding-based and PLM-based methods using only 7B models.The authors also report that query-based fine-tuning data constructed with binary-tree decomposition and curriculum learning can enhance LLM logical reasoning.Source: Introduction · p. 2

Related Works

Prior KG reasoning work centers on embeddings and text-generation models, while this paper situates LLM reasoning and curriculum learning as areas for further exploration. The related work contrasts these approaches and reviews curriculum learning across NLP tasks.

Logical Reasoning over Knowledge Graph

  • Embedding-based KG methods represent EFO1 queries in vector or probability spaces, while PLM-based approaches textualize queries but are described as limited in world knowledge and reasoning.The cited work includes query decomposition, computation-tree optimization, and logical-message aggregation.Source: Logical Reasoning over Knowledge Graph · pp. 2–3

LLMs for KG Reasoning

  • Prior LLM-KG work covers several KG tasks, but complex logical reasoning with LLMs remains relatively unexplored in the cited discussion.The paper describes an earlier prompt-engineering attempt as using LLMs as text generators.Source: LLMs for KG Reasoning · p. 3

Curriculum Learning

  • Curriculum learning has been applied to NLU, machine translation, and LLM in-context learning or pre-training, while this work explores it for LLM fine-tuning.The passage identifies Curriculum Learning with Bengio et al. (2009).Source: Curriculum Learning · p. 3

Preliminary

The preliminary section defines a knowledge graph through its entity, relation, and triplet sets, then describes complex query answering as matching results through composed queries. It presents CNF and DNF query forms as equivalent under De Morgan’s law.

Knowledge Graph

  • A knowledge graph is represented as G = (E, R, T), with entity and relation sets and triplets connecting head and tail entities.A triplet is written as (v_s, r, v_t), where v_s and v_t are entities and r is a relation.Source: Knowledge Graph · p. 3

Complex logical query

  • Complex query answering seeks suitable results by composing queries, with the presented CNF and DNF forms equivalent under De Morgan’s law.The passage denotes a query by q and its subqueries by q_i.Source: Complex logical query · p. 3

Methodology

LACT builds KG-grounded question–answer training examples, decomposes complex queries into computation trees, and orders training by query difficulty. At inference, the model generates answers from templated queries, which are extracted using regular expressions.

Instruction Tuning on LLMs

  • Training examples pair a prompt containing the question description, KG-neighborhood triplets, and logical query with a textualized answer, and the model is fine-tuned by next-token prediction.The objective maximizes the log-likelihood of the next token.Source: Instruction Tuning on LLMs · p. 4

Data Augmentation by Binary Tree Decomposition

  • Complex EFO1 queries become logic-equivalent computation trees; intersection and union nodes are split into child nodes, then non-leaf nodes are traversed in reverse order to form branches.The tree root corresponds to the answer entity, and its edges follow child-to-parent directions.Source: Data Augmentation by Binary Tree… · p. 4

Fine-tuning Enhanced by Curriculum Learning

  • Samples are grouped by difficulty and trained in three stages, with the first stage using 80% easy, 10% medium, and 10% difficult samples.Difficulty is based on the number of decomposed sub-logical queries.Source: Fine-tuning Enhanced by Curriculum… · p. 5

Reasoning Module

  • At inference, LACT retrieves relevant information, textualizes the EFO1 query, and fills a template; generated answers are extracted with regular expressions.Source: Reasoning Module · p. 5

Experiments

Experiments compare LACT with KG reasoning baselines across several datasets and examine its components, transferability, and scaling. LACT outperforms baselines, while ablations and further analyses test how decomposition, curriculum learning, and task conditions relate to its performance.

Training Settings / Experimental Settings

Scalability Study

  • On FB15K-237, performance improves with model size; experiments also test different training-data ratios for robustness.Figure 2 covers model and data scales.Source: Figure 2 · p. 5, Scalability Study · p. 7

Ablation Studies

  • BTD improves difficult-query performance; decomposed-query PPL and training loss start slightly higher, then quickly fall below ordinary-query levels during training.The authors interpret this pattern as evidence that chain decomposition reduces the learning difficulty of complex queries.Source: Figure 3 · p. 5, Ablation Studies · p. 5
  • Curriculum learning gradually makes difficult samples easier to understand than random-shuffle training, but its gain is very small without logical-chain decomposition.The authors attribute the limited effect on undecomposed samples to difficulty differences that LLMs struggle to understand.Source: Figure 3 · p. 5, Ablation Studies · p. 6

Main Results

  • LACT outperforms baselines across all datasets, averaging gains of 7.3% on avgp, 2.9% on avgodd, and 6.3% on avgn versus the previous SOTA method.Table 1 reports MRR scores for 14 query types; avgp covers ordinary queries, avgodd OOD queries, and avgn queries with negation.Source: Main Results · p. 5, Table 1 · p. 6

Transferability Study

  • Task transfer yields a 9.9% relative gain on OOD queries; across datasets, performance drops less than 5%, and over 95% of OOD test samples follow logical-chain reasoning.These results concern task-level and dataset-level transfer, respectively.Source: Transferability Study · p. 6
  • LACT is reported to suit different base models, with all query types improving to some extent as the base model advances.The authors describe this as evidence of generalization across model types.Source: Transferability Study · p. 7

Discussion

LACT performs better with more complete relevant KG information, retains some complex-reasoning ability with none, and gains more on higher-difficulty queries.

  • LACT gains as relevant KG information becomes more complete, retains some reasoning ability at zero information, and yields larger gains on higher-hop difficulty queries.The paper defines query difficulty by the number of hops and evaluates information completeness using the proportion of relevant triplets in the provided context.Source: When and Where Does LACT Work? · p. 7

Conclusion

The conclusion presents LACT as a two-part fine-tuning framework for complex logical reasoning over KGs, comprising Binary Tree Decomposition and Curriculum Learning.

  • LACT combines Binary Tree Decomposition and Curriculum Learning and is presented as applicable across LLM sizes and data sizes.The authors report empirical effectiveness and universality on widely used KG datasets.Source: Conclusion · p. 7

Retrieval Algorithm

The retrieval algorithm gathers relevant KG triplets along possible reasoning paths while balancing context completeness against the LLM token limit.

Retrieval Algorithm

  • The algorithm searches for as many relevant triplets as possible along possible paths, balancing information completeness against the LLM token limit.For 1p queries, it retrieves triplets containing the entity or relation; for other queries, it traverses from each DAG leaf and applies projection, intersection, or union operations until the result is empty or reaches the root.Source: Retrieval Algorithm · p. 10
  • For 1p queries, retrieval selects all triplets containing the query entity or relation.Source: Retrieval Algorithm · p. 10
  • For other queries, retrieval traverses from each DAG leaf, applying projection or filtering operations until the result is empty or reaches the root.Source: Retrieval Algorithm · p. 10

Over-limit Solutions and Token distribution

The evaluation uses a 4096-token maximum sequence length and discards out-of-bounds samples, while the retrieval algorithm reduces token consumption.

Over-limit Solutions and Token distribution

EFO1 to Computational Trees

The paper converts EFO1 queries into computation trees and evaluates LACT across query types, datasets, and base models. Reported analyses include OOD reasoning, cross-dataset transfer, and case studies comparing LACT with ChatGPT.

EFO1 to Computational Trees

  • EFO1 formulas are converted through dependency-graph generation and union-branch duplication into computation trees rooted at the answer variable.Nodes represent variables and, for single-hop queries, entities; oriented edges encode relations, with constants as terminal nodes.Source: EFO1 to Computational Trees · p. 10

Prompt Template

  • LACT's prompts provide KG triplets, ask for step-by-step decomposition into subqueries, and request the final answer using the relevant triplets.Source: Prompt Template · p. 10

Evaluation Protocol Detail

  • Query difficulty is assigned by the number of decomposed subqueries, and evaluation distinguishes simple from hard answers and uses filtered MRR.The study uses 14 query types; FB15K, FB15K-237, and NELL995 are described as its datasets, with FB15K-237 addressing inverse-relation leakage to a certain extent.Source: Difficulty · p. 10, Dataset Details · p. 10, Table 4 · p. 11

Training Details

  • The experiments fully fine-tune LLaMA-2-base models at 7B and 13B parameters; the three-stage training takes about 10 hours on eight A100 GPUs.Training uses one epoch, batch size 128, and learning rate 3e-6.Source: Training Details · p. 11, Training Cost · p. 11

Model-level transferability

OOD results

  • More than 95% of OOD test samples can follow logical-chain reasoning; Figure 8 compares three state-of-the-art methods across three datasets.The authors also report that untested nin/nipn query types can be correctly decomposed and queried.Source: OOD results · p. 11, Overall comparison · p. 11, Table 7 · p. 12

Case Study

Dataset Ablation Results

Related papers

Loading 2405.01649v4…