Semantics-Aware Caching for Concept Learning

Louis Mozart Kamdem Teyou; Caglar Demir; Axel-Cyrille Ngonga Ngomo

stat.MLMar 6, 2026

Semantics-Aware Caching for Concept Learning

Authors: Louis Mozart Kamdem Teyou, Caglar Demir, Axel-Cyrille Ngonga Ngomo

Organizations: Heinz Nixdorf Institute, Furstenalle 11, 33102 Paderborn, Germany · Paderborn University, Warburgerstr. 100, 33098 Paderborn, Germany

Abstract

Concept learning is a form of supervised machine learning that operates on knowledge bases in description logics. State-of-the-art concept learners often rely on an iterative search through a countably infinite concept space. In each iteration, they retrieve instances of candidate solutions to select the best concept for the next iteration. While simple learning problems might require a few dozen instance retrieval calls to find a fitting solution, complex learning problems might necessitate thousands of calls. We alleviate the resulting runtime challenge by presenting a semantics-aware caching approach. Our cache is essentially a subsumption-aware map that links concepts to a set of instances via crisp set operations. Our experiments on 5 datasets with 4 symbolic reasoners, a neuro-symbolic reasoner, and 5 popular pagination policies demonstrate that our cache can reduce the runtime of concept retrieval and concept learning by an order of magnitude while being effective for both symbolic and neuro-symbolic reasoners.

Figures & tables

Construct	Syntax	Semantics
Atomic concept	$A$	$A^{\mathcal{I}}\subseteq{\Delta^{\mathcal{I}}}$
Atomic role	$r$	$r^{\mathcal{I}}\subseteq{\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}}$
Top concept	$\top$	$\Delta^{\mathcal{I}}$
Bottom concept	$\bot$	$\emptyset$
Negation	$\neg C$	$\Delta^{\mathcal{I}}\setminus C^{\mathcal{I}}$
Conjunction	$C\sqcap D$	$C^{\mathcal{I}}\cap D^{\mathcal{I}}$

Table 1: Syntax & semantics for

\mathcal{ALC}

concepts.

\mathcal{I}

stands for an interpretation with domain

\Delta^{\mathcal{I}}

Dataset	$\|$ Ind. $\|$	$\|$ Classes $\|$	$\|$ Prop. $\|$	$\|\textbf{TBox}\|$	$\|\textbf{ABox}\|$	$\|\textbf{NC}\|$
Vicodi	33,238	194	10	204	116,181	2,105
Carcinogenesis	22,372	142	0 4	144	0 74,223	1,684
Mutagenesis	14,145	0 86	0 5	0 82	0 47,722	1,572
Family	00 202	0 18	0 4	0 26	000 472	1,236

Table 2: Datasets statistics.

|\textbf{NC}|

is the total number of concepts generated on each dataset.

|

Ind.

|

is the total number of individuals and

|

Prop.

|

is the total number of properties (relations) in each dataset.

Figure 1: Average runtime of concept learners using no cache, the semantic cache, and the non-semantic cache baseline across different datasets.

Panel of Figure 2 — Figure 2: Run time performance vs cache size for five reasoners on large datasets. The dotted horizontal lines represent the baseline performance of each reasoner without caching.

Figure 7: Average physical memory usage of concept learners using the semantic cache, and the non-semantic cache baseline across different datasets.

Concept Learning

See all 12 papers

MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation
May 24, 2026Ali Noshad, Zishan Zheng, Yinjun WuLLM Inference Efficiency RL for Combinatorial Optimization
School of Computer Science, Peking University, Beijing, China · School of Information, Renmin University of China, Beijing, China
KGCache: Amortized Subgraph Retrieval for KG Reasoning with LLMs
Aug 8, 2026Uros Stanic, Changcheng Yuan, Sabuj Laskar +1Knowledge Graph Question Answering
Texas A&M University College Station, TX, USA
Towards Reasonable Concept Bottleneck Models
Jun 5, 2025Nektarios Kalampalikis, Kavya Gupta, Georgi Vitanov +1Concept Bottleneck Models Interpretable ML
Department of Computer Science Saarland University, Germany

May 24, 2026J/K move · Enter open · S save

MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation

Ali Noshad, Zishan Zheng, Yinjun Wu

School of Computer Science, Peking University, Beijing, China · School of Information, Renmin University of China, Beijing, China

LLM Inference Efficiency RL for Combinatorial Optimization Semantic Caching

Open paper AskPDF arXiv

To reduce LLM costs and latency, semantic caching systems must accurately identify when a new prompt matches a cached one. Current methods often rely on simplistic similarity measures, which limit their effectiveness. We introduce MVR-cache, a novel semantic caching approach that significantly improves retrieval accuracy by integrating Multi-Vector Retrieval (MVR). MVR-cache is built upon a learnable segmentation model that intelligently splits prompts, enabling fine-grained similarity comparisons via MaxSim. We derive the model's training objective from a rigorous theoretical analysis. This can ensure that optimizing this objective directly maximizes cache hits under strict correctness constraints. To solve the resulting non-differentiable combinatorial optimization problem, we leverage a reinforcement learning-based training strategy with the theoretically grounded objectives as the reward. Experimental results on established benchmarks across diverse tasks confirm that in comparison to the state-of-the-art, MVR-cache consistently increases the cache hit rates by up to 37% while maintaining the same correctness guarantees. MVR-cache is available at https://github.com/PKU-SDS-lab/MVR-Cache

Abstract

Concept Learning

Explore similar work

MVR-cache: Optimizing Semantic Caching via Multi-Vector Retrieval and Learned Prompt Segmentation

KGCache: Amortized Subgraph Retrieval for KG Reasoning with LLMs

Towards Reasonable Concept Bottleneck Models