CS Paper Radar

The Canonical Order Problem: When Large Language Models Are Unreliable Knowledge Bases for Multi-Valued Relations

Timo Pierre Schrader, Annemarie Friedrich, Simon Razniewski, Lukas Lange

cs.CL ·submitted 2026-09-28 20:09 UTC · v1
published

Abstract

Large language models (LLMs) are increasingly used as knowledge bases (KBs) due to the vast amount of knowledge they acquire during pre-training. While many works focus on extracting single relational triples, most real-world relations are multi-valued and require generating sets of entities. In this paper, we investigate how LLMs represent and generate multi-valued relations. We identify the canonical order problem: The probabilistic distributions inside LLMs organize many multi-valued relations according to a canonical ordering (e.g., alphabetical or chronological). Through mechanistic analysis, we show that set generation in LLMs can be thought of in terms of three phases: (1) retrieval of candidate entities, (2) internal sorting, and (3) selection of the next element. As a result, prompts aiming to construct KBs that deviate from this internal canonical ordering lead to a markedly reduced reliability of LLMs when aiming to generate complete sets for multi-valued relations.

Comment
Accepted at AKBC@EMNLP2026

Closest papers

Nearest neighbours by meaning across the whole index.

Weighted First-Order Model Counting over Ordered Domains

cs.LO ·2026-08-11 ·Jan Tóth, Qipeng Kuang, Kuncheng Zou, Václav Kůla, Yuyi Wang +2 more
similarity 0.61
Abstract · Submitted to JAIR

The Weighted First-Order Model Counting Problem (WFOMC) asks for the weighted sum of models of a first-order logical sentence over a domain. It is a fundamental problem in statistical relational learning, with applications extending to enumerative combinatorics and graph polynomials. Computing WFOMC for the three-variable fragment is $\mathsf{\#P}_1$-hard, whereas polynomial-time algorithms exist for the two-variable fragment and its extensions by cardinality constraints and counting quantifiers. In this work, we explore computing WFOMC in polynomial time over linearly ordered domains, enabling tractable reasoning across inference scenarios and combinatorial problems involving sequences. Because encoding a linear order in standard first-order logic requires three variables, negating our polynomial-time aspirations, we add a linear order axiom directly to the language. This forces one predicate to impose a total ordering on domain elements. We first prove that WFOMC with the linear order axiom can be solved in time polynomial in the domain size. We then extend this result to ordered domains with access to successor relations. While this holds when successors are explicitly defined via the linear order, we demonstrate an alternative implicit approach where successor relations are part of the axiom. This implicit method exhibits significantly better performance on all tested instances, sometimes providing exponential runtime improvements. Finally, we analyze scenarios with two distinct linear orders. We show that WFOMC over the two-variable fragment with two linear orders is $\mathsf{\#P}_1$-hard. However, we develop a polynomial-time algorithm for WFOMC with one linear order and a successor relation of another, pushing the intractability barrier further, yet still leaving the question of how close to a second full linear order one can get.

0.35

AutoOntic: Automatic Ontology Induction from Text for Knowledge Graph Construction

cs.CL cs.AIcs.LG ·2026-11-11 ·Alla Chepurova, Aydar Bulatov, Mikhail Burtsev, Yuri Kuratov
code/data similarity 0.60
Abstract

Graph-based retrieval-augmented generation depends on the quality of the knowledge graph (KG) it retrieves over, yet schema-free LLM-based extraction pipelines typically produce flat graphs: deduplicated entities and relations with no type hierarchy and no domain/range constraints. We present AutoOntic, a pipeline that automatically constructs an ontology from text by canonicalizing open-vocabulary entity types and relations, inducing a hierarchy over the canonicalized types, and mining relation-level domain and range constraints. Its hierarchy induction procedure prioritizes types using corpus-derived relation-argument profiles and places them through local, LLM-adjudicated parent/child checks, allowing newly inserted types to trigger reassignment of existing parent-child links. The resulting hierarchy constrains entity deduplication and supports the induction of relation-level domain/range constraints. For intrinsic evaluation, we introduce a reference-based protocol that classifies induced ontology types as exact, broader, narrower, or unrelated to reference domain and range classes. On the Wikidata-TekGen and DBpedia-WebNLG subsets of Text2KGBench, over 90% of AutoOntic's induced endpoint types are semantically aligned with the reference classes across two LLM backbones: about half match exactly, while most remaining differences concern granularity. On MINE, knowledge graphs organized using an ontology built by AutoOntic achieve 88% retrieval accuracy. AutoOntic is available at https://github.com/screemix/AutoOntic.

0.29

GenSPARQL: A Generative Extension of SPARQL for Incomplete Knowledge Graphs

cs.DB cs.AI ·2026-11-19 ·Jingcheng Wu, Yi Wang, Hongkuan Zhou, Steffen Staab, Bo Xiong
code/data similarity 0.60
Abstract · 4 pages, 2 figures, 1 table. Demo paper submitted to The Web Conference 2027 (WWW 2027). Code: https://github.com/0sidewalkenforcer0/GenSPAR…

Knowledge graphs on the Web are incomplete, and SPARQL answers a query only from the stored triples. Large language models (LLMs) can predict missing facts, but an LLM returns names instead of IRIs and requires one call per binding of a query variable. We present GenSPARQL, a generative extension of SPARQL 1.1 with an operator GENOP that binds values generated by an LLM to query variables during query evaluation. A similarity join maps generated names to entities of the graph, and the query planner invokes the LLM only for the bindings selected by the other graph patterns and filters. In a web workbench, attendees query two graphs built from Wikidata and inspect generated values, mapped entities and LLM calls. In our evaluation with three open-weight LLMs, the embedding similarity maps 83% of the entities named by the LLMs and yields only one incorrect match.

0.31

Parameter-Efficient Retrievers for Polish and European Languages

cs.CL ·2026-09-11 ·Sławomir Dadas, Rafał Poświata, Małgorzata Grębowiec, Michał Perełkiewicz
similarity 0.59
Abstract

Dense retrieval systems increasingly rely on multi-billion-parameter language models, whose memory and computational requirements make large-scale indexing, frequent corpus updates, and low-latency serving costly. We present a three-stage training pipeline for developing compact and efficient retrievers that remain competitive with substantially larger models. The pipeline combines cross-lingual alignment, relational knowledge distillation, and contrastive fine-tuning. It requires no original ground-truth relevance labels, relying exclusively on supervision generated by strong embedding models and rerankers utilised as teachers. Using this pipeline, we develop PolDense and EuroDense, both supporting contexts of up to 8,192 tokens. PolDense is a family of six Polish retrievers ranging from 17M to 1B parameters. EuroDense is a 435M-parameter retriever supporting nine European languages. We conduct an extensive evaluation covering 41 Polish and 150 multilingual retrieval tasks. The results demonstrate strong quality-efficiency trade-offs. PolDense-1B outperforms the evaluated retrievers with up to 9B parameters, while the PolDense family forms the Pareto frontier across model sizes. Among the evaluated models below 1B parameters, EuroDense ranks first in both task-averaged and language-averaged performance and leads in seven of nine languages. We release all models publicly.

0.19

When Direction Matters: Diagnosing Relational Instruction Following in Dense Retrieval

cs.IR ·2026-11-11 ·Zhanyu Wu, Richong Zhang
similarity 0.58
Abstract

Dense retrievers increasingly claim the ability to condition retrieval on natural-language relevance criteria beyond a short query. We identify a specific weakness in this capability: the evaluated models perform well when lexical or attribute cues distinguish the target, but become much less reliable when relevance depends on a directional relation over the same entities. We introduce SwitchIR, a controlled diagnostic that contrasts Constraint Shift and Explicit Filtering with Relational Flip, where the query and document pair remain fixed while the requested relation direction reverses. Across representative embedding and late-interaction retrievers, the primary joint metric is high on the two cue-available controls and consistently low on Relational Flip; the same ordering persists in an LLM-assisted, manually reviewed realistic variant. An exact margin decomposition shows that both directions are correct only when the direction-sensitive query--document interaction exceeds the direction-invariant pair preference. Empirically, direction-sensitive changes are common, but their aligned interaction is usually too weak to overcome that preference. Diagnostic fine-tuning shows that models can learn relational behavior that generalizes across relation families, with stronger generalization in the larger model.

0.13

A Multi-granularity Interaction Network for Relational Triple Extraction

cs.CL ·2026-10-18 ·Xiaocheng Luo, Yanping Chen, Zaifu Zhan
code/data similarity 0.58
Abstract

Relational triple extraction identifies entity relations from raw sentences without depending on entity type information. The performance of traditional methods is seriously degenerated by ``unseen'' entities, because these methods can't build contextual dependencies relevant ``unseen'' entities. This paper addresses this challenge by proposing a multi-granularity interaction network that leverages word-word, entity-relation, and head-tail interactions to capture deep semantic dependencies. By incorporating multiple iterations, the multi-granularity interaction network is effective to refine the representations corresponding to head and tail entities. It enhances the global semantic features associated with relational triples, aiding in the remediation of triples that may have been overlooked or omitted in earlier steps. Strong and consistent performance is achieved by our method on two rearranged datasets, with a significant improvement in identifying relational triples, including those involving ``unseen'' named entities. For example, our model improves F1-score by 3.1%/20.5% over previous approaches on the NYT-R/WebNLG-R datasets in the Unseen metric. Code: https://github.com/xiaocen-luo/Interaction-Network.

0.27

Ontology-Guided Knowledge Graph Construction and Robust Evidence Retrieval for Indian Knowledge Systems

cs.IR ·2026-11-10 ·Anand Kaniyaar Sriranga Prasad, Avinash Holenarasipur Nagendra, Mohan Raghavan
similarity 0.58
Abstract · 22 pages, 15 figures, 4 tables

Retrieving evidence from Indian Knowledge Systems is complicated by transliteration variants, ambiguous names, and relations distributed across passages. We present an ontology-guided knowledge graph (KG) pipeline that links typed entities and relations extracted with Qwen3-32B to original textual evidence. Retrieval combines sense-aware grounding, bounded graph traversal, lexical anchors, relationship-vector search, and passage reranking. We evaluate KG alone, single-vector retrieval (SV), and KG unions with SV and Entity Notes on 320 questions from Dhara Bench, matching the per-question candidate count across internal systems under BGE and Qwen rerankers. Standalone KG has the highest Precision@5 under both rerankers and the highest MRR@20 in Counting, Composite, and Multi-hop among the evaluated internal configurations. With Qwen, KG achieves Multi-hop MRR@20 of 0.8722, compared with 0.7622 for the fully reranked KG + SV union. The KG + SV + Entity Notes union instead provides the highest overall Recall@20 (0.5134), compared with 0.4347 for KG. On the 15 Multi-hop questions, Qwen KG achieves complete-evidence MRR@20 of 0.4651 versus 0.3372 for SV, while both full unions complete ten questions within twenty results compared with nine for KG. Gemini 3.7 Flash, evaluated through manually reviewed source mappings, re mains stronger on overall MRR and nDCG, while internal systems have category-specific advantages. All comparisons are descriptive. A separate deployment timing study measures mean retrieval times of 20.374 s for KG and 0.646 s for SV. The findings support selecting KG or its unions according to the required balance of early relevance, evidence completeness, and retrieval cost.

0.07

Evaluating Semantic Relation Knowledge through Bidirectional Relation Prediction from Gloss Pairs

cs.CL ·2026-10-10 ·Zhihan Cao, Adam Nohejl, Hitomi Yanaka
dataset similarity 0.58
Abstract · under review

Semantic relations organise word senses and are fundamental to lexical semantics. In order to evaluate semantic relation knowledge of large language models (LLMs), we propose a challenging task in which an LLM predicts the relation between two glosses (definitions of senses) presented in two different orders. The predictions for the two orders are evaluated for consistency with the symmetry or asymmetry of semantic relations. Our task is designed for both monolingual and cross-lingual evaluation, allowing us to examine whether relation knowledge remains accessible when the same senses are verbalised through glosses in different languages. We construct a dataset of 3,069 sense pairs, with each sense verbalised in English, Greek, Romanian, Turkish, and Japanese. Experiments with 17 LLMs in zero-shot and five-shot settings reveal generally poor performance. In each setting, only eight LLMs achieve a macro-averaged F1 score significantly above a random baseline, and only one (zero-shot) and two (five-shot) significantly outperform a neural baseline. In particular, LLMs often fail to generate bidirectionally consistent predictions for hypernymy and to make correct predictions for holonymy in either direction. Our results suggest limitations in current LLMs' semantic relation knowledge, both in identifying relations and in respecting asymmetry.

0.18