arXiv:2604.12651v1 [cs.CL] 14 Apr 2026
L EARNING C HAIN O F T HOUGHTS P ROMPTS FOR P REDICTING E NTITIES , R ELATIONS , AND EVEN L ITERALS ON K NOWLEDGE G RAPHS
Alkid Baci, Luke Friedrichs, Caglar Demir, N’Dah Jean Kouagou, Axel-Cyrille Ngonga Ngomo Department of Computer Science Paderborn University Warburger Str. 100, 33098 Paderborn, Germany {alkid.baci, caglar.demir, ndah.jean.kouagou, axel.ngonga}@upb.de [email protected]
April 15, 2026
A BSTRACT Knowledge graph embedding (KGE) models perform well on link prediction but struggle with unseen entities, relations, and especially literals, limiting their use in dynamic, heterogeneous graphs. In contrast, pretrained large language models (LLMs) generalize effectively through prompting. We reformulate link prediction as a prompt learning problem and introduce RALP, which learns stringbased chain-of-thought (CoT) prompts as scoring functions for triples. Using Bayesian Optimization through MIPRO algorithm, RALP identifies effective prompts from fewer than 30 training examples without gradient access. At inference, RALP predicts missing entities, relations or whole triples and assigns confidence scores based on the learned prompt. We evaluate on transductive, numerical, and OWL instance retrieval benchmarks. RALP improves state-of-the-art KGE models by over 5% MRR across datasets and enhances generalization via high-quality inferred triples. On OWL reasoning tasks with complex class expressions (e.g., ∃hasChild.F emale, ≥ 5 hasChild.F emale), it achieves over 88% Jaccard similarity. These results highlight prompt-based LLM reasoning as a flexible alternative to embedding-based methods. We release our implementation, training, and evaluation pipeline as open source: https://github.com/dice-group/RALP.
1
Introduction
Knowledge graphs (KGs) are a foundational component of modern AI systems, supporting applications such as search [1, 2], question answering [3, 4, 5], and recommender [6, 7] systems. Central to maintaining their utility is the task of link prediction—inferring missing facts by modeling the underlying structure of the graph. Traditional knowledge graph embedding (KGE) models [8, 9, 10] have made progress toward link prediction problem by representing entities and relations as continuous vectors and applying learned scoring functions. However, these methods are inherently limited when faced with unseen entities or relations, and they struggle to reason over literals, such as numerical values or descriptive text, which are pervasive in real-world KGs. Meanwhile, LLMs have demonstrated remarkable capabilities in few-shot and zero-shot learning through prompting—conditioning the model on examples or task instructions [11]. Prompting plays a critical role in retrievalaugmented generation (RAG) systems [12], where relevant context from external sources is injected into prompts to improve task performance [13, 14, 15]. While many RAG pipelines rely on handcrafted prompt templates, recent work explores automated prompt optimization using techniques such as APE [16], OPRO [17], EvoPrompt [18], and MIPRO [19]. DSPy [20] further formalizes LLM pipelines as transformation graphs with learnable prompts via declarative modules. These advances suggest that high-quality prompts can be learned to maximize downstream performance—even without access to gradients.
Triple Completion / Entity Prediction Reasoning DSPy Model Knowledge Graph
String Input
Triples
LLM Prompt Optimization (
Prediction (Confidence Scores)
)
“From the retrieved context, Costa Rica borders Nicaragua and Panama, both located in Central America. Hence, Costa Rica is also in Central America → (costa_rica, locatedin, central_america) — confidence score: 1.0”
Optimizer (MIPRO)
OWL Reasoning
Literal prediction DSPy Model
Knowledge Graph
LLM String Input
Triples
Sampled Triples
DSPy Model
Reasoning “Given the context, we know that Gabon’s total nominal GDP is 14,622,880,885.6842 USD and its population is 2,025,137. To estimate the nominal GDP per capita, we can divide the total nominal GDP by the population… Given that, Gabon’s nominal GDP per capita would fall between $1000 and $15000 with a point prediction of $7225.“
Reasoning
LLM
Prediction (Point prediction + interval range)
Triples
String input
Knowledge Graph
Rendered class expression
“The concept "person or (not person)" in Manchester syntax is logically equivalent to the top class (owl:Thing) because it represents a tautology: every individual is either a `person` or not a `person`. In OWL, this union covers all possible individuals in the ontology.Thus, the result is: [stefan, anna, markus…]“
Prediction (Classified entities)
Figure 1: Overview of the RALP framework in three different tasks within the link prediction problem. Notice that sampling of triples or MIPRO optimization can be performed in all three of them but is omitted because of space limitations. In this work, we revisit the classic link prediction problem in knowledge graphs and propose a new formulation: learning a string-parametrized scoring function ϕβ ≤c instead of the conventional continuous vector-parametrized one ϕΘ . Traditional knowledge graph embedding models [8, 9, 10] represent entities and relations as dense vectors and compute a real-valued score ŷ = ϕ(h, r, t) to estimate triple plausibility. In contrast, our method learns a prompt β ≤c —a CoT string of up to c tokens—that conditions an LLM to score triples, including those with unseen entities, relations, or literals. To our knowledge we are the first approach to treat numerical link prediction via prompt-based reasoning, using LLMs directly without regression layers or binning and achieving promising results. RALP key advantages: ✓ Requires only a few examples (≤ 30) to optimize β ≤c via gradient-free MIPRO; ✓ Supports reasoning over unseen entities, relations, and literals; ✓ Augments training data to improve downstream KGE models; × Assumes that entity/relation strings are semantically meaningful. In summary, we introduce RALP, a method that shifts the perspective of solving the link prediction problem by learning symbolic, CoT-based scoring functions over KGs using LLMs and automated prompt tuning. Our method generalizes beyond traditional KGE models, achieving strong performance across transductive, numerical, and OWL instance retrieval benchmarks—paving the way for symbolic reasoning with LLMs over rich and dynamic knowledge graphs. An overview of the RALP framework is given in Figure 1.
2
Background and Related Work
2.1
Knowledge Graphs
A knowledge graph represents structured collections of assertions describing the world [21]. These collections of assertions have been used in a wide range of applications, including drug discovery, web search, recommendation and question answering [21] Formally, a knowledge graph (KG) is often defined as a set of triples G := {(h, r, t) ∈ 2
E ×R×E}, where E and R stand for a set of entities and a set of relations, respectively [8, 22]. Each triple (h, r, t) ∈ G represents an assertion based on two entities h, t ∈ E and a relation r ∈ R. This formulation can be further extended to generalize over triples involving literals, e.g., G := {(h, r, t) ∈ E × R × E ∪ I}, where I denotes the set of unique numerical literals. These triples can be inferred from an existing set of triples by means of designing logical rules or learning continuous vector representations via knowledge graph embedding models [21]. 2.2
Knowledge Graph Embeddings and Link Prediction
Most KGE models map entities e ∈ E and relations r ∈ R found in a Knowledge Graph (KG) G ⊆ E × R × E to V, where V is a d-dimensional vector space and d ∈ N\{0} [22]. Most KGE models are often designed as a scoring function to learn continuous vector representations tailored towards link prediction [21]. They are often defined as parameterized scoring functions ϕΘ : E × R × E 7→ R, where Θ denotes parameters and often comprise entity embeddings E ∈ V|E|×de , relation embeddings R ∈ V|R|×dr , and additional parameters. Given (h, r, t) ∈ E × R × E, the prediction ŷ := ϕΘ (h, r, t) signals the likelihood of (h, r, t) being true [8, 22]. Since Gtrain contains only assertions that are assumed to be true, assertions assumed to be false are often generated by applying the negative sampling, 1vsAll or Kvsall training strategies [9]. Regardless of the selected training strategies, the training is often realized in the mini-batch stochastic gradient descent or its sophisticated variants fashion, e.g. ADAM. Let Θ denote {E, R} randomly initialized embeddings. An embedding update over a mini batch B can be defined as: 1 X Θ ← Θ − ∇η ∇Θ L(x, y, Θ) (1) |B| x,y∈B
where • Θ are the learnable parameters of ϕ, • η is the learning rate, • L(x, y, Θ) is the loss function evaluated at point x, y, • ∇Θ L(x, y, Θ) is the gradient of the loss w.r.t. parameters, • B is a mini-batch of training samples, and • ∇ represents the gradient operator. The cross-entropy loss function is often used as the L that is defined as L(x, y, Θ) = −ylog(ŷ) − (1 − y)log(1 − ŷ), (2) 1 . Depending where ŷ := σ(ϕΘ (x)) s.t. x := (h, r, t) and σ(·) denotes the logistic sigmoid function σ(s) = 1+exp(−s) on the selected training technique, the learning problem (as well as B) is rendered as binary classification (e.g. Negative Sampling), a multi-class classification (1vsAll) or a multi-label classification (KvsAll). The resulting models are then evaluated w.r.t. their ability of predicting missing entity rankings [9]. Regardless of the selected training strategies, the training is often realized in the mini-batch stochastic gradient descent or its sophisticated variants fashion. 2.3
LLMs for Knowledge Graph Completion
Recent work explores leveraging pretrained large language models (LLMs) for KG completion. Some approaches adapt model architectures or fine-tune on textualized triples. KGLM [23] incorporates entity and relation embeddings into pretrained language models via continued pretraining. KG-LLM [24] fine-tunes LLMs using ranking-based objectives over textualized triples and employs retrieval for scalable candidate pruning. LINKGPT [25] combines structural encodings with instruction tuning and retrieval–rerank mechanisms to improve efficiency. In contrast, promptbased methods avoid architectural changes and gradient-based fine-tuning. PDKGC [26] formulates link prediction as multiple-choice question answering and selects prompts via ranking-guided sampling, enabling few-shot generalization. These approaches demonstrate that LLMs can internalize graph structure when appropriately adapted. However, most rely on fine-tuning, ranking losses, or handcrafted prompt templates, and typically focus on entity prediction in transductive benchmarks. 2.4
Automated Prompt Optimization
Automated prompt optimization seeks to replace manual prompt engineering with principled search strategies. Prior work includes discrete and evolutionary search [27, 28], reinforcement learning and self-improvement mechanisms [29, 30], and large language models that optimize instructions via meta-prompting (e.g., OPRO [17]). DSPy [20] 3
formalizes LLM pipelines as declarative programs with learnable prompt modules. MIPRO [19] introduces Bayesian optimization for jointly refining instructions and demonstrations across multi-stage pipelines, enabling gradient-free optimization under weak supervision. These developments suggest that prompts can serve as learnable, discrete parameters optimized directly for downstream objectives. Positioning of Our Work. Unlike embedding-based KGE models, we replace continuous vector-parameterized scoring functions ϕΘ with a string-parameterized scoring function ϕβ ≤c , where β ≤c is a learned chain-of-thought prompt. Unlike prior LLM-based KG completion methods, we require no fine-tuning, architectural modification, or ranking loss. Instead, we cast link prediction—including numerical and OWL-style reasoning—as a discrete prompt optimization problem solved via Bayesian optimization. This formulation enables reasoning over unseen entities, relations, and literals while remaining fully gradient-free and model-agnostic.
3
Methodology
Most KGE models are defined as a scoring function ϕΘ : E × R × E 7→ R parameterized by a vector Θ. The learning problem is often formalized as a classification problem, where the performance is measured by a cross entropy loss function. Here, we propose a string-parameterized scoring function ϕβ ≤c : E × R × E 7→ R. This function predicts the likelihood of a triple being true, where the parameter β ≤c is a sequence of at most c vocabulary terms (tokens) βi ∈ Σ. Specifically, β ≤c represents the input prompt provided to a selected pretrained large language model LM, and c denotes the context length of LM. The prompt β ≤c is constructed for a given query input (e.g. pair (s, p) ∈ E × R or a triple (s, p, o) ∈ E × R × E) by a function Π(·). Π(·) can be interpreted as an initialization scheme for Θ, similar to how neural networks use random uniform or Xavier initialization [31]. Our goal is to learn such β ≤c initialized by Π(·) to accurately predict the likelihoods of triples being elements of G into β ≤c , while maximizing the link prediction performance. Therefore, we aim to learn β ≤c tailored towards the link prediction task. 3.1
Learning Chain of Thoughts Prompts for Link Prediction
To find suitable ϕβ ≤c for a given G and a selected LLM, we propose to use a gradient-free search method (MIPRO). As the guiding signal, we use the cross entropy as performance metric (e.g. MRR scores) averaged over an evaluation set, rather than a loss gradient averaged over a training mini-batch. While MIPRO utilizes Bayesian Optimization over a discrete search space of possible strings rather than gradient descent on continuous parameters Θ, its process is still iterative and data-driven, aiming to find an optimal string configuration. The “update” in MIPRO refers to the process by which the optimizer refines its search strategy and identifies the best-performing string parameter found so far based on evaluation results. Let β ≤c represent a specific candidate string parameter, a sequence of at most c vocabulary terms βi ∈ Σ. Σ corresponds to the vocabulary size of the byte pair encoded tokens. 1 The set of all possible candidate string parameters forms a discrete search space SΣ . Our objective is to find β ∗≤c ∈ SΣ that maximizes a performance metric on a validation set, such as the cross-entropy loss L averaged over evaluation triples. MIPRO performs a sequence of T trials. At each trial t, the Bayesian Optimization algorithm does the following: 1. Select Candidate βt≤c : Based on the observed performance of string parameters evaluated in previous trials {(βi≤c , Q(βi≤c ))}t−1 i=1 , a probabilistic model of the Q function over SΣ is updated. An function a(β ≤c |{(βi≤c , Q(βi≤c ))}t−1 i=1 ) is then used to select the next candidate string parameter βt≤c that is most promising for evaluation (e.g., maximizing expected improvement) βt≤c = arg max a(β ≤c |{(βi≤c , Q(βi≤c ))}t−1 i=1 ). β ≤c ∈SΣ
This step is the analogue to the “update” step in gradient descent elucidated in Equation 1, as it determines the next point in the search space (SΣ ) to explore, but it is based on probabilistic modeling and acquisition rather than a gradient calculation on continuous parameters. 1
|Σ| = 151936 when using the Qwen2.5 tokenizer [32].
4
2. Evaluate Q(βt≤c ): The selected candidate string parameter βt≤c is used with the scoring function ϕβ ≤c and t evaluated on a (mini)batch of the validation set to obtain its score. st = Q(βt≤c )
(3)
3. Update Best Found String Parameter: The best string parameter found so far, βt∗≤c , is updated if the current candidate βt≤c yields a higher score than the best score recorded in previous trials. βt∗≤c =
( βt≤c ∗≤c βt−1
∗≤c if st > Q(βt−1 ) otherwise
(4)
where β0∗≤c is the initial string parameter generated by Π(·). After T trials, the optimization process terminates, and the final best-found string parameter βT∗≤c is returned. Thus, the string parameter update involves the iterative selection of candidate string parameters guided by the Bayesian Optimization model and the tracking of the single best-performing string parameter found over the search process, rather than incrementally modifying continuous parameters like Θ. The learned βT∗≤c then serves as the optimized parameter for the scoring function ϕβ ∗≤c . T
3.1.1
Initialization:
Π(·) combines relevant information about the query, a definition of the link prediction task, and few-shot examples Dfew . Dfew is a set of query-answer pairs illustrating the task Dfew can be defined through negative sampling technique as well as KvsAll training Dfew = {[(s′ , r′ ), {o1 , . . . , on }]} ,e.g. the following holds in the KvsAll setup: ∀oi ∈ {o1 , . . . , on } (s′ , r′ , oi ) ∈ G. Thus, the prompt is formulated as: β ≤c = Π(Dfew , s, r).
(5)
β ≤c and Π can be predefined through expert prompt engineering or learned to maximize a downstream metric without access to gradients. In this work, we use the cross entropy loss function as Q defined as Q(β ≤c ) =
1 X −ylog(ŷ) − (1 − y)log(1 − ŷ), |B|
(6)
x,y∈B
where y ∈ {0, 1} and ŷ := σ(ϕβ ≤c (x)) s.t. x := (h, r, t) and σ(·) denotes the logistic sigmoid function σ(s) = 1 1+exp(−s) . 3.1.2
Approaches:
Here, we propose two main approaches: RALP and RALP† . While RALP directly utilizes the in-context learning ability of the selected LM with a default prompt, RALP† uses the MIPRO algorithm to learn β ≤c tailored towards the link prediction task on a given Knowledge Graph (KG) G. Given a subject entity and a relation (s, r), RALP predicts missing information (e.g., candidate objects for a (s, r, ?) query) and potentially their likelihoods by processing the prompt: ŷ =: RALP(s, r) = LM(Π(Dfew , s, r)),
(7)
where ŷ ∈ [0, 1]|E| predicted probabilites for entities, (s, r) denoting input pair, and LM denoting a selected pretrained LLM. The output of LM is then parsed to obtain predictions. RALP† uses MIPRO to learn a prompt specifically for the link prediction task as described above. RALP can be readily used to predict missing triples as well as its predictive capability can be leveraged to enrich the training data. We propose Algorithm 1 to identify potential missing triples within the training graph by querying RALP for existing head-relation pairs and adding highly-scored, non-existent triples to a set of missing triples. 5
Algorithm 1 Knowledge Graph Enrichment via In-context Learning Require: RALP: Link prediction function using LLM inference; Gtrain : Training triples; θ: Confidence threshold (> 0.5) 1: Initialize Gmissing ← ∅ 2: for all (s, p, o) ∈ Gtrain do 3: // Query RALP for potential objects given (s, p) 4: Let S be the set of predicted objects and their scores obtained from RALP(s, p) 5: for all o′ predicted by RALP(s, p) with score S[o′ ] > θ do 6: if (s, p, o′ ) ∈ / Gtrain then 7: Gmissing ← Gmissing ∪ {(s, p, o′ )} 8: end if 9: end for 10: end for 11: return Gmissing
Algorithm 1 iterates through every subject-relation pair present in the training graph (derived from triples (s, p, o) ∈ Gtrain ). For each pair (s, p), it queries RALP, which predicts a set of potential object entities S along with confidence scores. If a predicted object o′ for (s, p) has a score exceeding the threshold θ and the triple (s, p, o′ ) does not already exist in the training graph, it is considered a potentially missing true triple and added to Gmissing . In one of our experiments, we augment the training splits of benchmark datasets with respective Gmissing to measure the benefits of using RALP or RALP† as an augmentation technique for conventional Knowledge Graph Embedding (KGE) models. 3.2
Numerical Literal Prediction
For numerical prediction, Q(·) can be defined as a regression loss (e.g., MSE). Given (s, r) where r is a data property, prediction proceeds via contextual retrieval. We construct contextual subsets: G(s) = {(s′ , r′ , t) ∈ G | s′ = s ∧ r′ ̸= r } and G(r) = {(s′ , r′ , t) ∈ G | r′ = r ∧ s′ ̸= s} where G(s) provides subject-specific context, while G(r) supplies relation-level value patterns. Due to token constraints, subsets are sampled with priority given to G(s) to facilitate chain-of-thought reasoning. The resulting few-shot context is passed to RALP to predict the numerical literal.
4
Experimental Setup
4.1
Datasets
We utilized the benchmark datasets Countries-S1, Countries-S2, Countries-S3, LitWD1K, and Father [33, 34, 35]. These datasets are consider relatively small but nevertheless they effectively show the capabilities of our approach. While applying our approach to larger datasets is limited by the token size that the LLM can process, we put focus in this paper on highlighting the novelty of our approach while leaving scalability to future work. The LitWD1K dataset, derived from Wikidata, includes numerical literals. For our experiments, we focused on two subsets: numeric literals (10988 triples of the form (s, r, l) where l is a numerical literal) and the ’train’ set (26115 triples of the form (s,r,o)). To improve the understanding of the LM, we preprocessed LitWD1K by replacing Wikidata IDs with their corresponding labels, creating two additional batches. We specifically considered only float/integer literals within the numeric literals set. 4.2
Transductive Link Prediction Setup
We used the best hyperparameter reported in the dice-framework [33]. Throughout our experiments, each entity and relation is represented with 32-dimensional real valued vector across datasets and models, e.g., TransE, DistMult, MuRE in R32 and ComplEx, Keci, DeCaL in C16 , and QMult, QuatE H8 . We use the Adam optimizer with 0.1 learning rate and train each model for 256 epochs with the batch size of 1024. The dropout rate on the embeddings is set to 0.3. 4.3
Numerical Literal Link Prediction Setup
Given a (s, r) pair from the numeric literals set, we retrieve the relevant context for this pair and generate 3 values, ŷ, ŷmin and ŷmax . Each of these values, as well as y, the true value of l for this pair, is stored in 2-dimensional arrays. 6
Due to large number of properties, we select a subset R′ ⊆ Rnc uniformly at random, where Rnc denotes the set of all unique properties in numeric literals batch and |R′ | = 10. We proceed to create predictions for each (s, r) where r ∈ R′ and store the values grouped by each unique r. For our evaluation metric, we compute the mean value for the array that stores the y values and the one that stores the ŷ values. We also show the standard deviation for the y values. Whereas for checking the calibration of the interval [ŷmin , ŷmax ] we compute interval coverage rate (IRC): N
ICR =
1 X (i) (i) , 1 ŷmin ≤ y (i) ≤ ŷmax N i=1
(8)
where N is the total number of triples where the given property appears. To evaluat the sharpness of the interval we also compute the interval width (IW): N
IW =
4.4
1 X (i) (i) ŷmax − ŷmin . N i=1
(9)
Experimental Setup OWL Reasoning
To evaluate the ability of large language models (LLMs) to predict instances of a given concept, we employed a twostep pipeline on the Father dataset, which contains 130 concept expressions formulated in the ALCQHI description logic. The signature of the few-shot generation is defined as follows: Input fields: G, C (concept expression in LALCQHI ), S (LLM-generated explanation of C’s syntax), T ⊆ E (ground truth set of true entities satisfying C). Output field: E (CoT example demonstrating inference of T from C using G). We decided to add the syntax explanation S because it proved beneficial in reducing hallucinations and guiding accurate logical reasoning during empirical testing. The second step involves a ChainOfThought DSPy module, which predicts the set of instances corresponding to the input concept expression. The module is defined with the following signature: Input fields: G: The knowledge graph as above, C: The target concept expression, Eexamples : Few-shot CoT examples generated from Step 1. Output field: T̂ : The predicted set of entities that are classified as instances of concept C. To assess the performance of the model, we compute the Jaccard similarity between the predicted and true instance sets. Concepts are grouped according to their logical or structural characteristics as detailed in Table 4, and we report the mean Jaccard similarity score for each group. In total, two few-shot examples are generated using two distinct concept expressions along with their corresponding ground truth sets. 4.5
Hardware and LLM Setup
Throughout our experiments, we use an Ubuntu server with Intel(R) Xeon(R) Platinum with 4 NVIDIA H100 80GBs. Thereon, we locally hosted a vLLM instance of Qwen/Qwen2.5-32B-Instruct with 4 tensor core parallelization [36, 37, 38].
5
Results
5.1
Transductive Link Prediction
Table 1 report the impact of MIPRO optimization in the link prediction performances. Results suggest that RALP† even MIPRO light optimization reaches a new state-of-the-art link prediction performances on the Countries dataset. To best of our knowledge, there is no state-of-the-art knowledge graph embedding model reaching 1.000 MRR or Hits@1 on the S1 dataset. During optimization, RALP† with MIPRO medium learned the following two prompts: Learned Composer Prompt: ”You are a geography expert. Given a subject and a predicate, your task is to find multiple tail entities that could be related to the subject through the predicate. For example, if the subject is a country and the predicate is ’locatedin’, you should provide the continents or regions where the country is located. If the predicate is ’neighbor’, you should provide the names of the countries that border the subject country. Your response should include reasoning 7
Table 1: Link prediction results of RALP† on Countries-S1, Countries-S2, and Countries-S3. RALP single Bold and underlined results indicate the best results and second best results. Models †
RALP light RALP† medium
S1
S2
S3
MRR
@1
@3
@10
MRR
@1
@3
@10
MRR
@1
@3
@10
0.979 1.000
0.958 1.000
1.000 1.000
1.000 1.000
0.750 0.750
0.500 0.500
1.000 1.000
1.000 1.000
0.595 0.764
0.375 0.541
0.791 1.000
0.833 1.000
Table 2: Link prediction results on Countries-S1, Countries-S2, and Countries-S3. Link prediction results on the training and testing datasets are denoted with train and test. Bold results indicate the best generalization performance of a respective model. Models
S1
S2
S3
MRR
@1
@3
@10
MRR
@1
@3
@10
MRR
@1
@3
@10
DistMult DistMult-RALP
0.783 0.990
0.583 0.979
0.979 1.000
1.000 1.000
0.582 0.753
0.583 0.458
0.667 0.938
0.958 0.958
0.283 0.670
0.104 0.542
0.375 0.771
0.604 0.896
Keci Keci-RALP
0.716 1.000
0.479 1.000
0.917 1.000
1.000 1.000
0.627 0.596
0.501 0.521
0.667 0.696
0.896 0.950
0.292 0.667
0.188 0.500
0.333 0.771
0.583 0.917
DeCaL DeCaL-RALP
0.712 0.865
0.500 0.729
0.896 1.000
0.979 1.000
0.481 0.685
0.271 0.546
0.708 0.812
0.812 0.562
0.312 0.590
0.188 0.417
0.354 0.729
0.583 0.875
MuRE MuRE-RALP
0.693 0.969
0.458 0.938
0.979 1.000
1.000 1.000
0.677 0.690
0.458 0.375
0.896 0.875
0.979 0.979
0.205 0.601
0.021 0.354
0.333 0.750
0.500 0.958
ComplEx ComplEx-RALP
0.411 0.979
0.250 0.958
0.479 1.000
0.688 1.000
0.243 0.196
0.125 0.062
0.312 0.250
0.500 0.500
0.322 0.491
0.208 0.396
0.333 0.521
0.562 0.667
QMult QMult-RALP
0.214 0.670
0.130 0.521
0.229 0.812
0.374 1.000
0.467 0.476
0.375 0.375
0.479 0.562
0.688 0.708
0.127 0.324
0.021 0.208
0.146 0.417
0.354 0.542
QuatE QuatE-RALP
0.384 1.000
0.188 1.000
0.500 1.000
0.708 1.000
0.247 0.250
0.104 0.104
0.229 0.271
0.583 0.604
0.103 0.373
0.042 0.188
0.062 0.458
0.208 0.750
that explains the thought process leading to the prediction and a list of candidate entities found among the provided entities.” and Learned Scorer Prompt: ”Given a list of predicted entities, use your understanding of geographical relationships and historical contexts to provide reasoning and likelihood scores for each entity. Consider the broadness or specificity of the entity, as well as any known connections or conflicts within the region. Your reasoning should explain why each entity has been assigned its respective score.” Table 2 report the link prediction performance of state-of-the-art embeddings models w/o RALP† . Results suggest that RALP† can be used as an effective data augmenter to learn better representations. 5.2
Numerical Literal Prediction
Table 3 presents the results of numerical literal link prediction on a selection of data properties from the LitWD1K dataset, evaluated using the RALP framework. For each property, we report the true mean value (yavg ), standard deviation (σ), predicted mean value (ŷavg ), ICR, and IW. The results indicate that the predicted mean values ŷavg closely approximate the true means yavg across most properties. Additionally, the interval coverage rate—defined as the proportion of true values falling within the predicted bounds [ŷmin , ŷmax ]—exceeds 75% for all properties, indicating well calibrated interval estimates. At the same time, the reported interval widths (IW) suggest a reasonable trade-off between calibration and sharpness, with narrower intervals for more stable properties (e.g., height metre) and wider intervals for high-variance ones (e.g., population). Figure 2 further visualizes the regression predictions and their confidence intervals against ground truth values, illustrating the model’s capacity for calibrated uncertainty estimation. To provide qualitative insight into the model’s reasoning, we include a representative example for the subject-relation pair (s = "gabon", r = "nominal gdp per capita usd"). 8
Table 3: Numerical link prediction results in LitWD1K dataset. The shown data properties are selected randomly without replacement for the illustration purposes. We predict ŷ together with interval bounds ŷmax and ŷmin . For our evaluation we measure the mean value of y, standard deviation σ, the mean value of ŷ and for the interval prediction, we measure interval coverage rate (ICR) for calibration and interval width (IW) for sharpness. Data Property
yavg
σ
ŷavg
ICR
IW
population age of majority years old total fertility rate nominal gdp per capita usd human development index life expectancy second real gdp growth rate mass kilogram height metre coordinate location longitude
60 923 964 18.3 3.029 11 510 0.677 2 220 348 629 0.025 68.7 1.80 19.34
± 344 077 886 ± 1.1 ± 1.435 ± 19 408 ± 0.145 ± 236 968 936 ± 0.036 ± 7.4 ± 0.07 ± 70.20
58 504 042 18.1 2.756 11 034 0.698 2 204 513 934 0.028 69.9 1.81 15.27
0.90 0.90 0.80 0.75 0.79 0.81 0.78 0.80 0.82 0.83
167 280 658 3.175 2.709 15 140 0.236 640 296 028 0.114 19.5 0.19 22.80
Regression Predictions with Intervals vs. Ground Truth
Human Development Index
0.9 0.8 0.7 0.6 0.5
angola cambodia eswatini zambia são_tomé_and_príncipe equatorial_guinea ghana laos vanuatu honduras republic_of_the_congo kiribati bhutan timor-leste guatemala federated_states_of_micronesia nicaragua india namibia tajikistan guyana cape_verde morocco kyrgyzstan iraq state_of_palestine moldova bolivia indonesia egypt philippines el_salvador gabon turkmenistan libya marshall_islands uzbekistan samoa dominica belize botswana maldives suriname saint_vincent_and_the_grenadines tonga jamaica bosnia_and_herzegovina tunisia dominican_republic fiji mongolia armenia ecuador north_macedonia ukraine colombia saint_lucia jordan azerbaijan georgia algeria lebanon venezuela albania cuba grenada saint_kitts_and_nevis antigua_and_barbuda panama bulgaria trinidad_and_tobago mauritius romania costa_rica seychelles palau barbados kazakhstan malaysia kuwait uruguay the_bahamas latvia oman bahrain hungary croatia chile malta lithuania cyprus brunei saudi_arabia qatar andorra estonia united_arab_emirates spain belgium japan new_zealand united_states united_kingdom germany denmark singapore
0.4
Figure 2: RALP predictions for the human development index property (P1081) in LitWD1K dataset. Ground truth depicted in black dots, regression prediction in blue cross and interval range in teal lines. For this property we report a mean squared error of 0.006 and a mean absolute error of 0.059. Some countries are omitted from the plot because of the limited space.
The CoT module performs step-by-step reasoning as follows: “Given the context, we know that Gabon’s total nominal GDP is 14,622,880,885.6842 USD and its population is 2,025,137. To estimate the nominal GDP per capita, we can divide the total nominal GDP by the population. However, we also have data on other countries’ nominal GDP per capita which can help us set a reasonable range. The lowest nominal GDP per capita among the listed countries is 499 USD (Sierra Leone) and the highest is 40,698 USD (United Arab Emirates). Given Gabon’s economic status and the provided data, it is reasonable to assume that Gabon’s nominal GDP per capita would fall somewhere between these two extremes.” Based on this reasoning, the model predicts the following: ŷmin = 1000.0, ŷ = 7225.0, and ŷmax = 15000.0. The true value for this (s, r) pair is y = 7413.0, which lies within the predicted interval, reflecting both the accuracy and the reliability of the model’s interval prediction capabilities. We want to note here that the main focus of numerical link prediction is the find a relatively close ŷ to the true value y, whereas the interval prediction is made purely to ensure the reliability of the predicted values with no intended application. 9
Table 4: Results of instance retrieval on Father datasets using RALP. We show the mean Jaccard similarity measured between the true set and the predicted set for each concept type where ’#’ denotes the number of concepts per concept type, ’Namespace’ denotes whether we included the namespace for triples in the graph or not, ’M’ means that the expression was set in Manchester syntax and ’DL’ means that the expression was set in Description Logics syntax. The best results for each concept type are marked in bold. Concept Types Atomic Negation Conjunction Disjunction Existential Universal At least restriction At most restriction Nominals Inverse
5.3
# 3 55 19 33 44 4 12 12 40 36
Namespace
No Namespace
M
DL
M
DL
1.000 0.887 0.986 0.984 0.656 0.541 1.000 0.519 0.646 0.479
1.000 0.803 0.881 0.775 0.700 0.479 0.900 0.677 0.670 0.613
1.000 0.869 0.973 0.969 0.673 0.291 1.000 0.477 0.600 0.558
1.000 0.801 0.973 0.818 0.764 0.354 0.900 0.511 0.740 0.705
OWL Reasoning/Instance Retrieval
Table 4 presents a detailed analysis of model performance across various OWL concept types under different input configurations. Specifically, we evaluate the impact of two factors: (i) the syntactic representation of concept expressions (Manchester syntax vs. Description Logic (DL) syntax), and (ii) the format used for representing RDF triples in the knowledge graph (with or without namespace, i.e., using full IRIs or shortened identifiers). The results show that the model achieves perfect performance on atomic concepts across all configurations (Jaccard similarity = 1.000), underscoring its robustness for basic concept retrieval. The model also demonstrates strong performance on more complex constructs such as at least restriction, conjunction, disjunction, and negation, with the best results achieved when using Manchester syntax and full IRIs (1.000, 0.986, 0.984, and 0.887, respectively). In contrast, performance degrades considerably for certain logical operators, particularly universal restrictions, where the best configuration yields a Jaccard similarity of only 0.541. Similar challenges are observed for at most restrictions and inverse properties, suggesting that these constructs may pose greater difficulty for language model-based reasoning in instance retrieval settings. Our ablation study further reveals that using Manchester syntax generally outperforms DL syntax, particularly when combined with full IRI representations. This configuration consistently led to superior results across most concept types. These findings suggest that Manchester syntax may align better with the language model’s pretraining, likely due to its more natural and human-readable structure. Additionally, representing entities and relations using full IRIs appears to provide essential contextual cues that facilitate more accurate reasoning. We also observe that including the syntax field S—a short natural language description of the logical concept—contributes positively to model performance. This field improves both the coherence and groundedness of the generated reasoning chains, supporting prior findings that emphasize the role of explicit contextualization in mitigating hallucinations and enhancing logical consistency in LLM outputs. Overall, these results affirm the effectiveness of our method across a broad spectrum of logical constructs while highlighting specific areas, such as universal quantification and numerical restrictions, where targeted improvements could further enhance performance. Future work may also investigate the scalability of these methods to deeper nesting and more compositional concept expressions.
6
Limitations
One limitation we observed in the numerical link prediction setting arises when the contextual information provided to the LLM includes extreme outliers. In some cases, these outlier values deviate significantly from the distribution of other numerical values and can negatively impact the model’s prediction quality. For instance, in the LitWD1K dataset, Venezuela’s inflation rate is recorded as 16,988.4—an order of magnitude higher than the mean for other countries. When such outliers are included in the input context, they can distort the inferred value range for the 10
interval prediction. This issue, however, can be mitigated through simple pre-processing techniques, such as filtering or down-weighting statistical outliers in the context. Another practical constraint is that input context must be aligned with human-readable labels or descriptions, especially when entities or relations are referenced using identifiers (e.g., QIDs or URIs). Since LLMs are primarily trained on natural language, failing to map these identifiers to descriptive text reduces their ability to reason effectively over the input. Lastly, our method relies on large pre-trained language models, which can present challenges for scalability in terms of inference time and computational resources. Token limitation into representing the context used for inference becomes an issue when dealing with large graphs. However, a solution to that would be to craft a sampling algorithm that selects the most relevant triples to go into the context. While our approach enables strong zero-shot performance and generalization, future work could explore ways to distill or compress the reasoning capabilities into lighter-weight models for broader deployment.
7
Conclusion
In this work, we introduced a novel paradigm for predicting missing links by redefining the traditional continuous vector-parameterized scoring function as a string-parameterized function, ϕβ ≤c , leveraging the power of Large Language Models (LLMs) and automated prompt optimization. Unlike conventional Knowledge Graph Embedding (KGE) models that rely on static embeddings and struggle with unseen entities and relations, our approach learns a dynamic CoT prompt β ≤c via few-shot examples and gradient-free optimization with MIPRO. This string-based scoring function offers several key advantages: • it can be learned efficiently with a limited number of LLM calls, • it inherently supports inference over triples involving previously unseen entities, relations, or literals by incorporating them directly into the prompt, and • the learned scorer can effectively augment training data for traditional KGE models, enhancing their generalization capabilities. While sensitive to the syntactic representation of KG elements, our method demonstrates the viability of learning symbolic scoring functions using LLMs for KG tasks. We presented two main approaches: RALP, which utilizes in-context learning with a default prompt, and RALP† , which employs MIPRO to learn an optimized prompt tailored to the specific KG and task. We also proposed a method (Algorithm 1) to leverage these approaches for enriching knowledge graphs by identifying potentially missing triples. Our framework also extends naturally to numerical literal prediction, where it achieves low mean squared error and mean absolute error—demonstrating strong predictive accuracy in this underexplored setting. Additionally, we applied our approach to OWL instance retrieval, showing that using Manchester syntax yields better LLM performance than traditional DL syntax for expressing class expressions. By redefining the scoring function and introducing automated prompt learning, our work opens a flexible and generalizable path toward robust, literal-aware knowledge graph completion—even in zero-shot or out-of-knowledge-base scenarios.
References [1] Peilu Wang, Hao Jiang, Jingfang Xu, and Qi Zhang. Knowledge graph construction and applications for web search and beyond. Data Intelligence, 1(4):333–349, 2019. [2] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. arXiv preprint arXiv:2007.00808, 2020. [3] Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, and Jonathan Larson. From local to global: A graph rag approach to query-focused summarization. arXiv preprint arXiv:2404.16130, 2024. [4] Jinheon Baek, Alham Fikri Aji, and Amir Saffari. Knowledge-augmented language model prompting for zeroshot knowledge graph question answering. In Bhavana Dalvi Mishra, Greg Durrett, Peter Jansen, Danilo Neves Ribeiro, and Jason Wei, editors, Proceedings of the 1st Workshop on Natural Language Reasoning and Structured Explanations (NLRSE), pages 78–106, Toronto, Canada, June 2023. Association for Computational Linguistics. 11
[5] Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. G-retriever: Retrieval-augmented generation for textual graph understanding and question answering. Advances in Neural Information Processing Systems, 37:132876–132907, 2024. [6] Qingyu Guo, Fuzhen Zhuang, Chuan Qin, Hengshu Zhu, Xing Xie, Hui Xiong, and Qing He. A survey on knowledge graph-based recommender systems. IEEE Transactions on Knowledge and Data Engineering, 34(8):3549– 3568, 2020. [7] Hongwei Wang, Miao Zhao, Xing Xie, Wenjie Li, and Minyi Guo. Knowledge graph convolutional networks for recommender systems. CoRR, abs/1904.12575, 2019. [8] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018. [9] Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla. You CAN teach an old dog new tricks! on training knowledge graph embeddings. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. [10] Yuanfei Dai, Shiping Wang, Neal N Xiong, and Wenzhong Guo. A survey on knowledge graph embedding: Approaches, applications and benchmarks. Electronics, 9(5):750, 2020. [11] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199–22213, 2022. [12] Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM computing surveys, 55(9):1–35, 2023. [13] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. Retrieval-augmented generation for knowledgeintensive nlp tasks. Advances in neural information processing systems, 33:9459–9474, 2020. [14] Ori Ram, Yoav Levine, Itay Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin Leyton-Brown, and Yoav Shoham. In-context retrieval-augmented language models. Transactions of the Association for Computational Linguistics, 11:1316–1331, 2023. [15] Fabio Petroni, Aleksandra Piktus, Angela Fan, Patrick Lewis, Majid Yazdani, Nicola De Cao, James Thorne, Yacine Jernite, Vladimir Karpukhin, Jean Maillard, Vassilis Plachouras, Tim Rocktäschel, and Sebastian Riedel. KILT: a benchmark for knowledge intensive language tasks. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou, editors, Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2523–2544, Online, June 2021. Association for Computational Linguistics. [16] Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. In The Eleventh International Conference on Learning Representations, 2022. [17] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024. [18] Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. In The Twelfth International Conference on Learning Representations, 2024. [19] Krista Opsahl-Ong, Michael J Ryan, Josh Purtell, David Broman, Christopher Potts, Matei Zaharia, and Omar Khattab. Optimizing instructions and demonstrations for multi-stage language model programs. In Yaser AlOnaizan, Mohit Bansal, and Yun-Nung Chen, editors, Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 9340–9366, Miami, Florida, USA, November 2024. Association for Computational Linguistics. [20] Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan A, Saiful Haq, Ashutosh Sharma, Thomas T. Joshi, Hanna Moazam, Heather Miller, Matei Zaharia, and Christopher Potts. DSPy: Compiling declarative language model calls into state-of-the-art pipelines. In The Twelfth International Conference on Learning Representations, 2024. [21] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard de Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, et al. Knowledge graphs. ACM Computing Surveys (CSUR), 54(4):1–37, 2021. 12
[22] Caglar Demir and Axel-Cyrille Ngonga Ngomo. Clifford embeddings–a generalized approach for embedding in normed algebras. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 567–582. Springer, 2023. [23] Jason Youn and Ilias Tagkopoulos. Kglm: Integrating knowledge graph structure in language models for link prediction. arXiv preprint arXiv:2211.02744, 2022. [24] Dong Shu, Tianle Chen, Mingyu Jin, Chong Zhang, Mengnan Du, and Yongfeng Zhang. Knowledge graph large language model (kg-llm) for link prediction. arXiv preprint arXiv:2403.07311, 2024. [25] Zhongmou He, Jing Zhu, Shengyi Qian, Joyce Chai, and Danai Koutra. Linkgpt: Teaching large language models to predict missing links. arXiv preprint arXiv:2406.04640, 2024. [26] Yuxia Geng, Jiaoyan Chen, Yuhang Zeng, Zhuo Chen, Wen Zhang, Jeff Z Pan, Yuxiang Wang, and Xiaoliang Xu. Prompting disentangled embeddings for knowledge graph completion with pre-trained language model. Expert Systems with Applications, 268:126175, 2025. [27] Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with ”gradient descent” and beam search, 2023. [28] Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. Evoprompt: Connecting llms with evolutionary algorithms yields powerful prompt optimizers, 2025. [29] Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large language models can self-improve, 2022. [30] Bin Hu, Chenyang Zhao, Pu Zhang, Zihao Zhou, Yuanhang Yang, Zenglin Xu, and Bin Liu. Enabling intelligent interactions between an agent and an llm: A reinforcement learning approach, 2024. [31] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249–256. JMLR Workshop and Conference Proceedings, 2010. [32] An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412.15115, 2024. [33] Caglar Demir and Axel-Cyrille Ngonga Ngomo. Hardware-agnostic computation for large-scale knowledge graph embeddings. Software Impacts, 13:100377, 2022. [34] Genet Asefa Gesese, Mehwish Alam, and Harald Sack. Literallywikidata - a benchmark for knowledge graph completion using literals, April 2021. [35] Caglar Demir, Alkid Baci, N’Dah Jean Kouagou, Leonie Nora Sieger, Stefan Heindorf, Simon Bin, Lukas Blübaum, Alexander Bigerl, and Axel-Cyrille Ngonga Ngomo. Ontolearn—a framework for large-scale owl class expression learning in python. Journal of Machine Learning Research, 26(63):1–6, 2025. [36] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023. [37] Qwen Team. Qwen2.5: A party of foundation models, September 2024. [38] An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei, Huan Lin, Jialong Tang, Jialin Wang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Ma, Jin Xu, Jingren Zhou, Jinze Bai, Jinzheng He, Junyang Lin, Kai Dang, Keming Lu, Keqin Chen, Kexin Yang, Mei Li, Mingfeng Xue, Na Ni, Pei Zhang, Peng Wang, Ru Peng, Rui Men, Ruize Gao, Runji Lin, Shijie Wang, Shuai Bai, Sinan Tan, Tianhang Zhu, Tianhao Li, Tianyu Liu, Wenbin Ge, Xiaodong Deng, Xiaohuan Zhou, Xingzhang Ren, Xinyu Zhang, Xipin Wei, Xuancheng Ren, Yang Fan, Yang Yao, Yichang Zhang, Yu Wan, Yunfei Chu, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zhihao Fan. Qwen2 technical report. arXiv preprint arXiv:2407.10671, 2024.
13