Neural Scalable Symbolic Search Framework for Compl... | AI Research

What the paper is about

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., $\text{EFO}_k$ queries) is a crucial yet challenging problem, as it requires ranking answer tuples in $\mathcal{E}^k$, where $\mathcal{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 $\text{EFO}_1$ queries, we propose Neural Scalable Symbolic Search (NS3), a budgeted framework that approximates joint ranking without enumerating $\mathcal{E}^k$. 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 $\text{EFO}k$ query to an $\text{EFO}{k-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 $\text{EFO}_1$ datasets to $k=3$, enabling systematic evaluation of multi-variable queries. Our code is provided in this https URL .

What it covers

\setcctype by Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables Weizhi Fei [email protected] 1234-5678-9012 Department of Mathematical Sciences, Tsinghua University Beijing China , Hang Yin [email protected] 1234-5678-9012 Squarepoint Capital Singapore Singapore , Zihao Wang [email protected] 1234-5678-9012 TSY Capital Hong Kong Hong Kong , Shukai Zhao [email protected] 1234-5678-9012 Department of Computer Sciences, University of Rochester New York USA , Wei Zhang [email protected] 1234-5678-9012 Department of Mathematical Sciences, Tsinghua University Beijing China and Yangqiu Song [email protected] 1234-5678-9012 Department of Computer Science and Engineering, HKUST Hong Kong Hong Kong (2026) Abstract. Complex Query Answering (CQA) is a fundamental knowledge representation and reasoning task over incomplete knowledge graphs (KGs). Answering existential first-order queries with k k free variables (i.e., EFO k \text{EFO}{k} queries) is a crucial yet challenging problem, as it requires ranking answer tuples in ℰ k \mathcal{E}^{k} , where ℰ \mathcal{E} denotes the entity set of a KG. This quickly becomes intractable as k 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 EFO 1 \text{EFO}{1} queries, we propose Neural Scalable Symbolic Search (NS3), a budgeted framework that approximates joint ranking without enumerating ℰ k \mathcal{E}^{k} . 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 B , and (iii) progressively reduces an EFO k \text{EFO}{k} query to an EFO k − 1 \text{EFO}{k-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 EFO 1 \text{EFO}{1} datasets to k = 3 k=3 , enabling systematic evaluation of multi-variable queries. Our code is provided in https://github.com/HKUST-KnowComp/NS3_KDD2026 . complex query answering, neural graph database, knowledge graph † † journalyear: 2026 † † copyright: cc † † conference: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2; August 9–13, 2026; Jeju Island, Republic of Korea. † † booktitle: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD 2026), August 9–13, 2026, Jeju Island, Republic of Korea † † isbn: 979-8-4007-2259-2/2026/08 † † doi: https://doi.org/10.1145/3770855.3817755 † † ccs: Computing methodologies Machine learning † † ccs: Information systems Retrieval tasks and goals † † ccs: Theory of computation Logic Resource Availability: The source code of this paper has been made publicly available at https://doi.org/10.5281/zenodo.20355345 . 1. Introduction Knowledge Graphs (KGs) are powerful graph databases with machine-interpretable semantics, which have been widely adopted for many advanced web applications (Rastogi, 2012 ; Hirsch et al. , 2009 ; Remus et al. , 2017 ; Fei et al. , 2026 ; Bai et al. , 2026 ; Liu et al. , 2022 ; Liu, 2025b , a ; Liu and Yan, 2026 ) . Despite their wide applications, current large-scale KGs are often incomplete, with substantial knowledge missing from the observed graphs (Safavi and Koutra, 2020 ; Hu et al. , 2020 ) . Complex Query Answering (CQA) was proposed to predict completed answers to complex logical queries utilizing machine learning models. Traditional graph search methods overlook these potential answers, while large language models fail to provide faithful answers due to hallucinations. To facilitate interpretable reasoning on incomplete structured knowledge, CQA has emerged as a crucial task that simultaneously addresses knowledge discovery and complex logical reasoning (Ren and Leskovec, 2020 ; Yin et al. , 2024b ; Ren et al. , 2023 ) . Figure 1. Visualization of EFO 2 \text{EFO}{2} in fraudulent activities. We present its logical formula and query graph. Notably, the answers to this query are tuples. With significant advancements, the scope of complex logical queries supported by CQA models has continued to expand (Hamilton et al. , 2018 ; Ren et al. , 2020 ; Ren and Leskovec, 2020 ; Wang et al. , 2021 ; Yin et al. , 2025 ; Bai et al. , 2025 ) . However, most existing studies have primarily focused on Existential First-Order logic queries with a single free variable ( EFO 1 \text{EFO}{1} queries). The answers to these queries are single entities rather than tuples of entities. In particular, Existential First-Order logical queries with k k free variables ( EFO k \text{EFO}{k} queries) not only enhance the expressive power of logical queries but also can effectively facilitate many real-world applications (Ren et al. , 2023 ) . For example, as illustrated in Figure 1 , EFO k \text{EFO}{k} queries can be used to identify groups of individuals involved in fraudulent activities, a task that naturally arises in finance, security, and social network analysis. Answering EFO k \text{EFO}{k} queries is fundamentally challenging due to the exponential growth of the candidate answer space. With entity set ℰ \mathcal{E} , a k k -variable query has candidates in the Cartesian product ℰ k \mathcal{E}^{k} . Under KG incompleteness, many tuples can be valid answers only after reasoning over missing facts, which makes exhaustive joint inference over ℰ k \mathcal{E}^{k} computationally prohibitive for realistic KGs. Due to this difficulty, the only existing benchmark for multi-variable CQA, EFO k \text{EFO}{k} -CQA (Yin et al. , 2025 ) , evaluates models primarily via marginal rankings , where each free variable is ranked independently over ℰ \mathcal{E} . However, marginal rankings are a weak proxy for the true joint ranking over tuples. For instance, if the true 2-tuple answers are { ( 1 , 3 ) , ( 2 , 4 ) } {(1,3),(2,4)} , the marginal answer sets are { 1 , 2 } {1,2} and { 3 , 4 } {3,4} , which cannot eliminate non-answers such as ( 1 , 2 ) (1,2) or ( 2 , 3 ) (2,3) . Although EFO k \text{EFO}{k} -CQA also proposes an approximation by sorting tuples from the Cartesian product, its empirical performance remains suboptimal (Yin et al. , 2025 ) . Consequently, there remains a clear gap between (i) the correct objective of joint tuple ranking and (ii) what existing benchmarks and methods can efficiently support. To bridge this gap, we propose Neural Scalable Symbolic Search (NS3) , a framework that directly infers joint rankings for EFO k \text{EFO}{k} queries by progressively reducing the joint candidate space. NS3 builds on neural-symbolic search methods developed for well-studied EFO 1 \text{EFO}{1} (Bai et al. , 2023c ; Yin et al. , 2024b ; Fei et al. , 2025a ) , preserving their strengths in interpretability and strong performance while extending them to multi-variable joint inference. Our key idea is to transform an EFO k \text{EFO}{k} query into an equivalent EFO 1 \text{EFO}{1} query over a budgeted reduced domain: (i) a marginalization transformation generates marginal queries over subsets of free variables, whose results provide necessary conditions for pruning candidate tuples; (ii) a merge transformation packages multiple free variables with pruned domains into a hypernode with a reduced domain, enabling symbolic search to operate on joint candidates; (iii) a budgeting algorithm dynamically selects and merges variables, progressively reducing an EFO k \text{EFO}{k} query to an EFO 1 \text{EFO}{1} query under a reduced computational budget. We evaluate NS3 on three standard KGs. On the existing EFO k \text{EFO}{k} -CQA benchmark, we compute marginal rankings by solving the corresponding marginal queries and consistently outperform all baselines across multiple metrics. To directly assess joint inference and scalability beyond k = 2 k=2 , we further construct a concise yet scalable EFO k \text{EFO}{k} dataset tailored for joint ranking evaluation, introducing more challenging multi-variable query structures. Experiments on this dataset demonstrate that NS3 achieves substantial improvements in joint ranking over all baseline methods, highlighting its robustness and scalability. 2. Related work Complex query answering extends KG link prediction (Shi and Weninger, 2018 ; Trouillon et al. , 2016 ; Toutanova et al. , 2015 ) to logical queries with conjunction, disjunction, negation, existential quantification, directed graph structures, cycles, and multiple free variables (Hamilton et al. , 2018 ; Ren et al. , 2020 ; Ren and Leskovec, 2020 ; He et al. , 2025 ; Yin et al. , 2024b , 2025 ) . Existing work also studies CQA over temporal, event, and multi-modal KGs (Fei et al. , 2025b ; Lin et al. , 2023 ; Bai et al. , 2023a ; Kharbanda et al. , 2024 ; Li et al. , 2026 ) . Neural query encoders. Query embedding methods encode logical queries into latent regions or distributions, including vectors (Hamilton et al. , 2018 ) , boxes (Ren et al. , 2020 ) , cones (Zhang et al. , 2021 ; Yin et al. , 2024a ) , Beta distributions (Ren and Leskovec, 2020 ) , Gaussian densities (Choudhary et al. , 2021 ) , and other distributions (Yang et al. , 2022 ; Wang et al. , 2023a ) . GNN- and Transformer-based models further encode query graphs or linearized query structures (Wang et al. , 2023b ; Zhang et al. , 2024 ; Bai et al. , 2023b ; Zheng et al. , 2025 ; Liu et al. , 2025 ) . The surprising theoretical upper bound for the query embedding method was recently revealed in (Wang et al. , 2026 ) , but gaps remain in learnability. Multi-modal distribution methods such as Query2Particles and Query2GMM improve single-variable answer distributions; Appendix C discusses why they differ from tuple-level EFO k \mathrm{EFO}{k} joint ranking. Neural-symbolic and LLM-based methods. Neural-symbolic methods represent variables as fuzzy sets and apply differentiable logical operations or symbolic search (Chen et al. , 2022 ; Zhu et al. , 2022 ; Xu et al. , 2022 ; Galkin et al. , 2024 ; Arakelyan et al. , 2020 , 2023 ; Bai et al. , 2023c ; Yin et al. , 2024b ) . Recent work further accelerates symbolic search by pruning variable domains with neural scores (Fei et al. , 2025a ) . LLM-based CQA methods decompose logical queries and reason over retrieved subgraphs (Xu et al. , 2024 ; Zheng et al. , 2024 ; Choudhary and Reddy, 2023 ; Xia et al. , 2025 ; Liu et al. , 2026 ; Liu and Shu, 2025 ; Liu, 2025c ) , but they are mainly designed for decomposable single-free-variable settings. In contrast, NS3 targets joint tuple ranking for EFO k \mathrm{EFO}{k} queries by combining marginal pruning, hypernode merging, and budgeted symbolic search. Figure 2. Visualization of the inferring the EFO 1 \text{EFO}{1} query with existing neural symbolic search methods (Yin et al. , 2024b ) . These methods gradually remove the edges connected with constant nodes, self-loop edges, and the edges connected with leaf nodes. The fuzzy vectors are updated accordingly, and the final fuzzy vector for the free variable can induce the predicted answer set. 3. Background 3.1. Preliminaries in EFO k \text{EFO}{k} queries Let ℰ \mathcal{E} and ℛ \mathcal{R} be the set of real-world entities and relations, respectively. The knowledge graph is defined as 𝒦 ​ 𝒢 ⊆ ℰ × ℛ × ℰ \mathcal{KG}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E} , where each triple ( s , r , o ) ∈ 𝒦 ​ 𝒢 (s,r,o)\in\mathcal{KG} indicates that the relation r r holds between entities s s and o o . Without loss of generality, we assume the EFO k \text{EFO}{k} queries are expressed as the Disjunctive Normal Form (DNF) to simplify the discussion. Definition 3.1 (Atomic Formula). Let variables x x and y y range over entities ℰ \mathcal{E} . An atomic formula r ​ ( h , t ) ∈ { True , False } r(h,t)\in{\texttt{True},\texttt{False}} is a binary predicate, where r ∈ ℛ r\in\mathcal{R} and h , t h,t are either entities or variables. Definition 3.2 ( EFO k \text{EFO}{k} query). An EFO k \text{EFO}{k} query is a first-order logic formula involving logical connectives ∧ \land , ∨ \lor , ¬ \lnot , and existential quantification ∃ \exists , with k k free variables. It is defined as (1) ψ ​ ( y 1 , ⋯ , y k ; x 1 , ⋯ , x t ) = ∃ x 1 , ⋯ , x t . \displaystyle\psi(y{1},\cdots,y_{k};x_{1},\cdots,x_{t})=\exists x_{1},\cdots,x_{t}. (2) ( c 1 1 ∧ ⋯ ∧ c n 1 ) ∨ ⋯ ∨ ( c 1 κ ∧ ⋯ ∧ c n κ κ ) , \displaystyle(c^{1}{1}\land\cdots\land c^{1}{n})\lor\cdots\lor(c^{\kappa}{1}\land\cdots\land c^{\kappa}{n_{\kappa}}), where x x and y y represent existential variables and free variables. The term c c denotes the atomic formula r ​ ( h , t ) r(h,t) or its negation ¬ r ​ ( h , t ) \neg r(h,t) . Definition 3.3 (Answer set of the EFO k \text{EFO}{k} query). Given an EFO k \text{EFO}{k} query ψ ​ ( y 1 , ⋯ , y k ) \psi(y_{1},\cdots,y_{k}) and the corresponding knowledge graph 𝒦 ​ 𝒢 \mathcal{KG} , its answer set is defined as a set of tuples: 𝒜 ​ [ ψ ​ ( y 1 , ⋯ , y k ) ] = { ( a 1 j , ⋯ , a k j ) | ψ ​ ( a 1 j , ⋯ , a k j ) ​ is True in 𝒦 ​ 𝒢 } . \displaystyle\mathcal{A}[\psi(y_{1},\cdots,y_{k})]={(a_{1}^{j},\cdots,a_{k}^{j})|\psi(a_{1}^{j},\cdots,a_{k}^{j})\text{ is True in $\mathcal{KG}$}}. Because the observed KGs are incomplete, many answers can only be predicted by machine learning methods are important. The KGs are usually split as train/valid/test nested graphs. The hard answers that emerged from the unseen facts in the valid/test KG are particularly important, as they can only be predicted by machine learning models. Previous EFO 1 \text{EFO}{1} queries utilize the metrics based on ranking of these hard answers as evaluation protocols, including MRR, and HIT @ ​ 10 @10 (Ren and Leskovec, 2020 ) . Answering EFO k \text{EFO}{k} queries requires ranking over Cartesian product of size | ℰ | k |\mathcal{E}|^{k} , which quickly becomes computationally infeasible even for moderate k k . 3.2. Limitations of the existing CQA methods for EFO k \text{EFO}{k} queries While existing CQA methods are effective for EFO 1 \text{EFO}{1} queries, extending them to EFO k \text{EFO}{k} queries introduces significant computational challenges. The joint answer space grows exponentially with the number of free variables k k , making it infeasible for existing methods to score all candidate tuples. This challenge is particularly pronounced for query embedding methods, which rely on large-scale training over sampled queries. As a result, standard EFO k \text{EFO}{k} benchmarks (e.g., EFO k \text{EFO}{k} -CQA) evaluate models using marginal rankings rather than joint rankings. However, marginal ranking is insufficient for representing joint ranking of multi-variable answers. Although the joint metrics propose one closed solution to estimate joint rankings by marginal rankings, the empirical results are suboptimal. 3.3. Neural symbolic search methods for the EFO 1 \text{EFO}{1} query Neural symbolic search methods employ knowledge graph embeddings as neural link predictors to infer unobserved facts. By leveraging fuzzy logic (Mendel, 1995 ) to relax logical operators, these methods show that answering EFO 1 \text{EFO}{1} queries is equivalent to performing a sequence of edge-removal operations on the query graph. Each variable node is associated with a fuzzy vector representing its soft assignments over entities. As edges are progressively removed and logical constraints are propagated, the query graph is iteratively simplified until only the free variable remains. The fuzzy vector of the free variable then induces the predicted answer set. Figure 2 illustrates this execution process, including the elimination of constant nodes, self-loop edges, and leaf nodes. Definition 3.4 (Product norm). Fuzzy logic is employed to execute the fuzzy logical operations replacing the logical operations. We provide the widely used product norm as follows, where Conjunction: α ⊤ P β = α ∗ β \alpha~\top{P}\beta=\alpha*\beta , Negation: 1 − α 1-\alpha , and Disjunction: α ⊥ P β = 1 − ( 1 − α ) ⊤ P ( 1 − β ) \alpha\bot_{P}~\beta=1-(1-\alpha)\top_{P}(1-\beta) . Definition 3.5 (Query graph). Let ϕ \phi be a conjunctive query, its query graph G ϕ = { ( h i , r i , t i , Neg i ) } G_{\phi}={(h_{i},r_{i},t_{i},\textsc{Neg}{i})} consists of quadruples, where each quadruple corresponds to an atomic formula or its negation. This representation corresponds to an edge with two endpoints h h and t t , along with two attributes: r r , which denotes the relation, and Neg i \textsc{Neg}{i} , a boolean variable indicating whether the atom is positive. Definition 3.6 (Fuzzy vector). If we index the entities in ℰ = { e 1 , … , e | ℰ | } \mathcal{E}={e_{1},\ldots,e_{|\mathcal{E}|}} , we represent a fuzzy set over entities for each variable x x using a fuzzy vector C x ∈ [ 0 , 1 ] | ℰ | C_{x}\in[0,1]^{|\mathcal{E}|} , where the i i -th entry C x ​ [ i ] C_{x}[i] denotes the membership degree of entity e i e_{i} being a valid assignment for x x under current constraints. We define μ ​ ( s , C x ) \mu(s,C_{x}) to retrieve the membership degree of entity s s for variable x x . Figure 3. Visualization to infer the joint ranking of EFO 2 \text{EFO}{2} query by the marginalization and merge transformation. First, we infer the marginal answer sets on two marginal queries. Second, we merge the 2 2 free variables as one hypernode and reduce the search space by marginal answers. Finally, we adapt the symbolic search method to infer this new query on the reduced domain, thereby resulting in joint ranking. 4. Methodology In this section, we present Neural Scalable Symbolic Search (NS3) , a framework for answering existential first-order queries with multiple free variables ( EFO k \mathrm{EFO}{k} ) over incomplete knowledge graphs. NS3 extends neural symbolic search methods originally developed for EFO 1 \mathrm{EFO}{1} queries to the multi-variable setting by explicitly controlling the joint search space. Rather than enumerating the exponential candidate space ℰ k \mathcal{E}^{k} , NS3 performs a budgeted joint search through two key steps: (1) identifying necessary candidate sets via marginalization, and (2) progressively merging free variables into hypernodes with bounded joint domains. An overview of the framework is illustrated in Figure 3 . 4.1. Marginalization as a Necessary Condition We begin by formalizing marginalization, which provides a necessary (but not sufficient) condition for valid joint answers and serves as the basis for safe candidate pruning. Marginalization. Any valid joint answer tuple to an EFO k \mathrm{EFO}{k} query must project to a valid answer of each corresponding marginal query obtained by existentially quantifying a subset of free variables. Therefore, candidate assignments that violate any marginal constraint can be safely pruned. However, satisfying all marginal constraints does not guarantee joint validity, which motivates the subsequent joint reasoning steps in NS3. Definition 4.1 (Marginalization of an EFO k \mathrm{EFO}{k} Query). Given an EFO k \mathrm{EFO}{k} query ϕ ​ ( 𝒴 ) \phi(\mathcal{Y}) with free variables 𝒴 = { y 1 , … , y k } \mathcal{Y}={y_{1},\ldots,y_{k}} and a subset 𝒴 δ ⊊ 𝒴 \mathcal{Y}^{\delta}\subsetneq\mathcal{Y} , the marginalization of ϕ \phi over 𝒴 δ \mathcal{Y}^{\delta} is defined as (3) ℳ ​ [ ϕ , 𝒴 δ ] = ϕ ​ ( 𝒴 δ ) , \mathcal{M}[\phi,\mathcal{Y}^{\delta}]=\phi(\mathcal{Y}^{\delta}), where free variables not in 𝒴 δ \mathcal{Y}^{\delta} are transformed into existentially quantified variables. Definition 4.2 (Marginalization on Answer Sets). Let the answer set of an EFO k \mathrm{EFO}{k} query be 𝐚 = { ( a 1 j , … , a k j ) } \mathbf{a}={(a{1}^{j},\ldots,a_{k}^{j})} , and let 𝒴 γ = { y i 1 , … , y i τ } \mathcal{Y}^{\gamma}={y_{i_{1}},\ldots,y_{i_{\tau}}} be a subset of free variables. The marginalization of 𝐚 \mathbf{a} over 𝒴 γ \mathcal{Y}^{\gamma} is defined as (4) ℳ ​ [ 𝐚 , 𝒴 γ ] = { ( a i 1 j , … , a i τ j ) } . \mathcal{M}[\mathbf{a},\mathcal{Y}^{\gamma}]={(a_{i_{1}}^{j},\ldots,a_{i_{\tau}}^{j})}. A formal proof of the commutativity between marginalization and answer sets is provided in Appendix D . This result ensures that marginal answer sets can be obtained by directly solving marginalized queries using existing symbolic search methods. Unlike independently scoring each free variable, the marginalized query preserves cross-variable constraints by existentially quantifying the other free variables. 4.2. Merge Transformation Marginalization reduces the number of free variables but does not eliminate the need to reason over joint assignments. To enable joint reasoning while reusing EFO 1 \mathrm{EFO}{1} symbolic search procedures, we introduce a merge transformation that groups multiple free variables into a single hypernode with a reduced joint domain. Intuition. The merge transformation converts a multi-variable query into an EFO 1 \mathrm{EFO}{1} query over a reduced joint domain. This reduction is approximate: it preserves high-confidence joint candidates while discarding low-probability regions of the Cartesian product. Definition 4.3 (Merge Transformation). Let G ϕ G_{\phi} be the query graph of an EFO k \mathrm{EFO}{k} query ϕ \phi , and let y i 1 y{i_{1}} and y i 2 y_{i_{2}} be two free variables. The merge transformation replaces y i 1 y_{i_{1}} and y i 2 y_{i_{2}} with a hypernode γ \gamma . All edges incident to y i 1 y_{i_{1}} or y i 2 y_{i_{2}} are reconnected to γ \gamma , whose domain represents joint assignments of ( y i 1 , y i 2 ) (y_{i_{1}},y_{i_{2}}) . 4.3. Reduced Joint Domain Construction We now describe how to construct a reduced joint domain for a merged hypernode. For clarity, we first consider merging two free variables. Let ℳ ​ [ ϕ , { y 1 } ] \mathcal{M}[\phi,{y_{1}}] and ℳ ​ [ ϕ , { y 2 } ] \mathcal{M}[\phi,{y_{2}}] denote the marginal queries for y 1 y_{1} and y 2 y_{2} , producing fuzzy vectors C y 1 C_{y_{1}} and C y 2 C_{y_{2}} . Let B B be the per-variable budget. We allocate a reduced joint domain of size 2 ​ B ≪ | ℰ | 2 2B\ll|\mathcal{E}|^{2} . To estimate effective marginal domain sizes, we compute fuzzy counts (5) C 1 = ∑ i C y 1 ​ [ i ] , C 2 = ∑ i C y 2 ​ [ i ] . C_{1}=\sum_{i}C_{y_{1}}[i],\quad C_{2}=\sum_{i}C_{y_{2}}[i]. Budget Allocation Heuristic. We allocate budgets using (6) λ = 2 ​ B C 1 ​ C 2 , b 1 = λ ​ C 1 , b 2 = λ ​ C 2 , \lambda=\sqrt{\frac{2B}{C_{1}C_{2}}},\quad b_{1}=\lambda C_{1},\quad b_{2}=\lambda C_{2}, such that b 1 ​ b 2 ≈ 2 ​ B b_{1}b_{2}\approx 2B . This heuristic ensures that the overall joint budget is respected while allocating more capacity to variables with diffuse marginal distributions and prioritizing highly constrained variables. We then select the top- b 1 b_{1} entities for y 1 y_{1} and the top- b 2 b_{2} entities for y 2 y_{2} , and form the reduced joint domain via their Cartesian product. Padding is applied when necessary to meet the budget constraint. The budget parameter B B therefore controls a trade-off between recall and efficiency, which we empirically analyze in Section 5.6 and Appendix C . 4.4. Inferring EFO 2 \mathrm{EFO}{2} Queries via Marginalization and Merge After merging two free variables into a hypernode, the resulting query can be treated as an EFO 1 \mathrm{EFO}{1} query over the reduced joint domain. Two modifications are required to adapt existing symbolic search procedures. First, edges between the merged variables become self-loop edges on the hypernode. Second, when removing an edge incident to the hypernode, its fuzzy vector is updated via constraint slicing : each symbolic constraint induces a mask over the joint domain, and the fuzzy vector is updated by element-wise multiplication with this mask, followed by normalization. This operation propagates symbolic constraints over joint assignments without explicitly enumerating ℰ 2 \mathcal{E}^{2} . 4.5. Progressive Budgeting for EFO k \mathrm{EFO}{k} Queries For general EFO k \mathrm{EFO}{k} queries, NS3 progressively applies merge transformations until all free variables are consolidated into a single hypernode, yielding an EFO 1 \mathrm{EFO}{1} query. If a hypernode γ \gamma represents n γ n{\gamma} free variables, its budget is set to B γ = n γ ⋅ B B_{\gamma}=n_{\gamma}\cdot B , ensuring linear growth with respect to the number of variables. Budgeting Algorithm. We first compute fuzzy vectors for all single-variable marginal queries. At each step, we greedily merge the pair of variables (or hypernodes) whose estimated marginal domain sizes yield the smallest product. This strategy prioritizes merging the most constrained variables first, thereby limiting the growth of intermediate joint domains. After each merge, we estimate the fuzzy count of the resulting hypernode using symbolic search. The process repeats until a single hypernode remains, at which point joint ranking is computed via EFO 1 \mathrm{EFO}{1} symbolic search. 4.6. Complexity Analysis The space complexity of NS3 is dominated by the neural link predictor, requiring 𝒪 ​ ( ( | ℰ | + | ℛ | ) ​ d ) \mathcal{O}((|\mathcal{E}|+|\mathcal{R}|)d) memory, where d d is the embedding dimension.NS3 avoids storing dense adjacency tensors of size 𝒪 ​ ( | ℰ | 2 ​ | ℛ | ) \mathcal{O}(|\mathcal{E}|^{2}|\mathcal{R}|) . For time complexity, let n n be the number of atomic formulas and B B the per-variable budget. Computing marginal queries requires 𝒪 ​ ( n ​ k ​ B 2 ) \mathcal{O}(nkB^{2}) time. At the i i -th merge step, symbolic inference over the merged hypernode costs 𝒪 ​ ( n ​ ( i ​ B ) 2 ) \mathcal{O}(n(iB)^{2}) . Summing over all merge steps yields an overall complexity of 𝒪 ​ ( n ​ k 3 ​ B 2 ) \mathcal{O}(nk^{3}B^{2}) . While this complexity grows polynomially with k k for fixed B B , NS3 achieves practical scalability by operating with small k k and moderate budgets, as validated empirically in Section 5 . 5. Experiments Table 1. The statistics for the three knowledge graphs are provided, including the number of entities, relations, and edges. Additionally, we present the division of the training, validation, and test graphs. Dataset Entities Relations Training Edges Validation Edges Test Edges FB15k 14,951 1,345 483,142 50,000 59,071 FB15k-237 14,505 237 272,115 17,526 20,438 NELL 63,361 200 114,213 14,324 14,267 To validate the effectiveness of NS3 in addressing EFO k \text{EFO}{k} queries, we not only evaluate the existing EFO k \text{EFO}{k} -CQA benchmark involving 2 2 free variables, but also propose a new EFO k \text{EFO}{k} benchmark that is concise and scalable to include more free variables. These benchmarks are constructed over three standard knowledge graphs: FB15k (Bordes et al. , 2013 ) , FB15k-237 (Toutanova et al. , 2015 ) , and NELL995 (Xiong et al. , 2017 ) , with statistics provided in Table 1 .To study the sensitivity and effectiveness of domain budgeting, we vary the budget size and analyze its effects. Additionally, to demonstrate the effectiveness of our proposed budgeting algorithm, we conduct an ablation study comparing our approach to directly merging all free variables at once. 5.1. Implementation details We adapt the neural symbolic search method NLISA (Fei et al. , 2025a ) to implement our proposed NS3 framework. NS3 (J) infers the joint ranking, while NS3 (M) infers the marginal ranking by considering the marginal queries derived from the marginalization process. Since our framework only generates truth values for the reduced domain, the discarded tuples/entities that belong to the answer set are assigned a score of zero. Specifically, we set the budget B B to 4,000 for FB15K (14,951 entities), 4,000 for FB15K-237 (14,505 entities), and 6,000 for NELL (60,000 entities). We provide further details about the implementation and the running time of our method in Appendix B.1 . Table 2. HIT@10 scores(%) of three metrics for answering queries with 2 2 free variables on FB15k-237. e e is the number of existential variables. We use SDAG, Multi, and Cyclic to denote the simple directed acyclic graph, multigraph, and cyclic graph, which represents the topology of query graph. NS3 (M) represents the results of marginal ranking in our framework. Model Type e = 0 e=0 e = 1 e=1 e = 2 e=2 Avg S M S M C S M C BetaE Marg 36.8 37.5 34.3 35.3 49.7 27.1 25.8 37.7 33.0 Mult 28.9 25.3 24.2 22.5 32.6 23.9 22.0 26.4 24.1 Joint 5.9 5.7 5.1 4.9 12.3 2.2 2.1 6.6 4.6 LogicE Marg 39.7 38.8 36.2 36.5 51.1 27.8 26.2 38.3 34.0 Mult 31.9 27.3 26.4 24.3 34.5 25.1 23.2 26.5 25.4 Joint 6.4 6.3 5.7 5.4 13.6 2.6 2.3 7.0 5.0 ConE Marg 40.1 40.8 37.6 38.1 55.0 28.8 27.5 41.4 35.8 Mult 32.8 28.9 27.7 25.3 37.9 26.0 23.9 30.4 27.0 Joint 6.7 7.2 6.0 5.8 14.2 2.7 2.4 7.6 5.4 CQD Marg 36.7 34.3 35.6 36.4 49.6 25.5 24.0 39.3 33.0 Mult 34.6 28.7 29.8 26.9 36.8 28.8 25.0 28.8 27.9 Joint 6.4 6.9 6.3 6.4 13.9 3.0 2.7 7.6 5.6 lmpnn Marg 40.9 40.0 38.5 38.4 52.7 30.3 27.0 39.0 35.4 Mult 34.6 28.7 29.8 26.9 36.8 28.8 25.0 28.8 27.9 Joint 6.8 7.5 5.9 5.6 13.1 2.6 2.3 6.4 5.0 FIT Marg 45.9 43.1 45.0 45.4 50.2 36.4 34.8 42.0 41.2 Mult 40.7 34.3 37.2 34.4 33.7 36.2 34.7 33.7 35.0 Joint 6.7 7.0 7.1 7.2 11.7 3.2 3.4 7.1 5.9 NS3M Marg 48.0 46.7 46.0 46.1 59.0 35.5 33.2 48.7 42.8 Mult 40.1 33.9 36.9 33.3 40.2 34.6 31.1 39.1 34.