# Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables

arXiv: https://arxiv.org/abs/2605.25985 · HTML: https://mlsanity.com/paper/2605.25985/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 59 references that are in the map.
- First posted on arXiv 25 May 2026.

## Builds on (most cited first, 30 of 37)

- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings](https://mlsanity.com/paper/2002.05969/) (2020)
- [Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs](https://mlsanity.com/paper/2010.11465/) (2020)
- [Embedding Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/1806.01445/) (2018)
- [CoDEx: A Comprehensive Knowledge Graph Completion Benchmark](https://mlsanity.com/paper/2009.07810/) (2020)
- [Complex Query Answering with Neural Link Predictors](https://mlsanity.com/paper/2011.03459/) (2020)
- [ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13715/) (2021)
- [Open-World Knowledge Graph Completion](https://mlsanity.com/paper/1711.03438/) (2017)
- [Neural-Symbolic Models for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2205.10128/) (2022)
- [Generate-on-Graph: Treat LLM as both Agent and KG in Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2404.14741/) (2024)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization](https://mlsanity.com/paper/2212.09567/) (2022)
- [Probabilistic Entity Representation Model for Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13522/) (2021)
- [Logical Message Passing Networks with One-hop Inference on Atomic Formulas](https://mlsanity.com/paper/2301.08859/) (2023)
- [GammaE: Gamma Embeddings for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2210.15578/) (2022)
- [Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints](https://mlsanity.com/paper/2305.19068/) (2023)
- [Neural-Symbolic Reasoning over Knowledge Graphs: A Survey from a Query Perspective](https://mlsanity.com/paper/2412.10390/) (2024)
- [Neural-Symbolic Entangled Framework for Complex Query Answering](https://mlsanity.com/paper/2209.08779/) (2022)
- [Logic Embeddings for Complex Query Answering](https://mlsanity.com/paper/2103.00418/) (2021)
- [Wasserstein-Fisher-Rao Embedding: Logical Query Embeddings with Local Comparison and Global Transport](https://mlsanity.com/paper/2305.04034/) (2023)
- [A Foundation Model for Zero-shot Logical Query Reasoning](https://mlsanity.com/paper/2404.07198/) (2024)
- [TFLEX: Temporal Feature-Logic Embedding Framework for Complex Reasoning over Temporal Knowledge Graph](https://mlsanity.com/paper/2205.14307/) (2022)
- [Top Ten Challenges Towards Agentic Neural Graph Databases](https://mlsanity.com/paper/2501.14224/) (2025)
- [EFOk-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation](https://mlsanity.com/paper/2307.13701/) (2023)
- [Fuzzy Logic Based Logical Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2108.02390/) (2021)
- [Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning](https://mlsanity.com/paper/2405.01649/) (2024)
- [CLR-Fact: Evaluating the Complex Logical Reasoning Capability of Large Language Models over Factual Knowledge](https://mlsanity.com/paper/2407.20564/) (2024)
- [Graph-O1 : Monte Carlo Tree Search with Reinforcement Learning for Text-Attributed Graph Reasoning](https://mlsanity.com/paper/2512.17912/) (2025)
- [Intention Knowledge Graph Construction for User Intention Relation Modeling](https://mlsanity.com/paper/2412.11500/) (2024)

## Abstract (arXiv)

Complex Query Answering (CQA) is a fundamental knowledge representation and reasoning task over incomplete knowledge graphs (KGs). Answering existential first-order queries with k free variables (i.e., EFOk queries) is a crucial yet challenging problem, as it requires ranking answer tuples in Ek, where E denotes the entity set of a KG. This quickly becomes intractable as k grows. Consequently, existing benchmarks and methods rely on marginal rankings over individual variables; however, marginal rankings are a poor proxy for the true joint ranking of tuples. Building on neural symbolic search for EFO1 queries, we propose Neural Scalable Symbolic Search (NS3), a budgeted framework that approximates joint ranking without enumerating Ek. NS3 (i) answers marginalized sub-queries to obtain necessary candidate sets, (ii) merges multiple free variables into hypernodes whose domains are pruned and controlled by a dynamic budget B, and (iii) progressively reduces an EFOk query to an EFOk-1 query over a budgeted reduced domain. Across three standard KG datasets, NS3 substantially improves joint ranking performance while retaining strong marginal accuracy. We further release a joint-ranking benchmark that extends existing EFO1 datasets to k=3, enabling systematic evaluation of multi-variable queries. Our code is provided in https://github.com/HKUST-KnowComp/NS3KDD2026.