Paderborn's RALP Beats Top Graph AI Models by 5% Without Any Training

Knowledge graph embedding models have a well-known weakness. They memorize the entities and relations seen during training, then fall apart the moment a new node, predicate, or literal value shows up. A team from Paderborn University has proposed a workaround that skips embeddings entirely: RALP, a system that treats a link prediction score as the output of a learned chain-of-thought prompt rather than a dot product between vectors.

The headline result: RALP improves state-of-the-art KGE models by over 5% MRR across datasets and enhances generalization via high-quality inferred triples, using Bayesian Optimization through the MIPRO algorithm with fewer than 30 training examples and no gradient access.

Why embeddings hit a wall

Traditional link prediction treats a knowledge graph as a set of triples of the form (head, relation, tail), and learns a scoring function that maps each triple to a real number indicating how plausible it is. Models like TransE, ComplEx, and DistMult do this by embedding entities and relations as dense vectors and training via stochastic gradient descent with cross-entropy loss.

The catch, as the authors point out, is that 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. Every new entity forces retraining. Numerical literals like GDP figures or population counts basically cannot be handled without special-purpose regression heads or binning tricks.

Swapping vectors for strings

RALP replaces the vector-parameterized scoring function with a string-parameterized one. Instead of learning a matrix of embeddings, the system learns a prompt, a chain-of-thought instruction of up to c tokens, that conditions a frozen LLM to output a plausibility score for a triple. The prompt itself becomes the learnable parameter.