acceptodds
Under review as a conference paper at ICLR 2027

Zero-Shot Logical Reasoning for Arbitrarily Structured Queries on Knowledge Graphs

Abstract

Real-world complex logical query answering (CLQA) requires reasoning over arbitrarily structured existential first-order (EFO) queries on unseen knowledge graphs (KGs). However, existing methods are often restricted to tree-shaped queries or fixed KGs. Moreover, they often rely on link predictors designed to predict a missing entity for a single triplet, making them suboptimal for queries involving multiple atoms that form complex structures. We propose VASIL, the first foundation model for CLQA designed to directly answer EFO queries with arbitrary structures in a zero-shot manner. Given an EFO query on a KG, VASIL autoregressively infers probability distributions of the variables while jointly predicting mutually dependent variables. At each step, it labels the entities and relations in the KG based on the atoms involving the variables being resolved and performs message passing over the labeled KG. The resulting representations are used to resolve the variables, yielding predictions conditioned on both the KG and the query. To train VASIL across diverse query structures, we construct queries by merging multiple random walks, a procedure that theoretically covers all conjunctive EFO query structures. Because variables are predicted based solely on the structures of the query and the labeled KG, VASIL can perform CLQA on KGs containing unseen entities and relations. Experiments on 37 benchmarks show that VASIL outperforms baselines in answering queries requiring reasoning beyond simple link prediction, including non-tree-shaped or multi-free-variable queries.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Knowledge Graph, Complex Logical Query Answering, Knowledge Graph Foundation Model, Logical Query Reasoning, Knowledge Graph Representation Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GKHtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces VASIL, a foundation model for Complex Logical Query Answering (CLQA) over knowledge graphs (KGs), targeting arbitrary Existential First-Order (EFO) query structures in a zero-shot setting, including unseen entities and relations. VASIL employs an autoregressive variable-resolution process in which a Query-Conditioned Compositional Reasoner labels the KG according to query atoms, updates entity and relation representations through message passing, and predicts distributions over mutually dependent variables. To support training without predefined query templates, the authors further propose a Dynamic Query Synthesizer that generates diverse training queries on the fly by combining random walks.

Critical strengths

VASIL demonstrates strong fully inductive generalization, outperforming UltraQuery across all 11 unseen WikiTopics graphs, with particularly substantial gains on multi-hop chain queries. Ablation results further suggest that its end-to-end design supports multi-hop reasoning even when trained only on 1-hop queries, while reducing training costs. Beyond performance, VASIL provides a flexible and broadly evaluated framework that natively handles complex query structures, including cycles, multi-edges, and multiple free variables, without decomposition or assignment search. Its template-free query synthesizer, extensive evaluation across 37 benchmarks and three task families, and comprehensive ablations further strengthen its practical value.

Critical weaknesses

VASIL decomposes queries and resolves variables step-by-step, running message passing over a newly labeled KG at each autoregressive step. While the paper mentions competitive inference times in an appendix, dynamically relabeling and aggregating messages across massive, real-world KGs for every subproblem could introduce severe latency bottlenecks.

The paper’s positioning against closely related work requires further clarification, particularly regarding its claim of being the first CLQA foundation model to support arbitrary query structures over unseen KGs. The paper lacks zero-shot comparisons of AnyCQ+ULTRA, which would provide a relevant test of its handling of multiple free variables. While differences in task formulation and architectural design are meaningful, their implications for relative capabilities remain unclear. Furthermore, CKGC shows strong performance, but it has not been empirically tested.

Questions for authors
  1. How does the Dynamic Query Synthesizer construct training queries beyond those whose answers are directly derived from connected triplets in the KG? Does its reliance on queries with non-empty answer sets limit the diversity of synthesized queries or introduce biases that affect the model’s ability to handle queries with no valid answers at inference time?

  2. Could the authors provide a controlled comparison with UltraQuery using the same four KGs and synthesized training queries, or evaluate VASIL trained on UltraQuery’s training data?

  3. Could the authors clarify why AnyCQ, FIT/QTO with ULTRA, and AnyCQ with ULTRA are omitted from Table 1 and the experimental evaluation?

2 comments
AuthorsOpenReview ↗

Response to Reviewer GKHt (1/2)

We appreciate the reviewer’s time and effort in reviewing our manuscript. Below, we provide our responses to the review comments. All line numbers refer to the revised manuscript. Our code is available at https://anonymous.4open.science/r/VASIL_3d7a/

W1.

VASIL decomposes queries and resolves variables step-by-step, running message passing over a newly labeled KG at each autoregressive step. While the paper mentions competitive inference times in an appendix, dynamically relabeling and aggregating messages across massive, real-world KGs for every subproblem could introduce severe latency bottlenecks.

Response: Resolving queries step-by-step is a widely adopted strategy in CLQA (e.g., CQD, GNN-QE, and UltraQuery). Moreover, VASIL groups variables into subproblems by their distance from the target variable and resolves the variables within each subproblem jointly. Thus, the number of autoregressive steps depends only on the maximum distance from the target variable in the query graph, which is a small constant (at most 4 in our benchmarks) regardless of the KG size.

Empirically, as reported in Appendix E, VASIL’s autoregressive decoding does not introduce a significant latency overhead compared to UltraQuery, while consistently outperforming UltraQuery across all settings in Tables 2, 3, and 4.


W2.

The paper’s positioning against closely related work requires further clarification, particularly regarding its claim of being the first CLQA foundation model to support arbitrary query structures over unseen KGs. The paper lacks zero-shot comparisons of AnyCQ+ULTRA, which would provide a relevant test of its handling of multiple free variables. While differences in task formulation and architectural design are meaningful, their implications for relative capabilities remain unclear.

Response: As discussed in the Related Work (Lines 127–139), AnyCQ and VASIL address different problem settings. AnyCQ targets Boolean query evaluation, whereas VASIL targets the standard CLQA setting, where answers must be ranked among a large set of candidate entities.

Evaluating AnyCQ (with Ultra) under the standard CLQA setting requires individually verifying every candidate entity per query, making full-scale evaluation computationally infeasible. Specifically, evaluating all test queries on a single dataset (FB15k-237-BetaE) is estimated to take 870,459 GPU hours (~99 GPU-years) on an A6000 GPU, whereas VASIL completes it in just 1.23 GPU hours. Please read our response to Q3 for the detailed runtime analysis.

VASIL is the first CLQA method that can simultaneously (i) handle complex queries with arbitrary structures and (ii) transfer to unseen KGs in a zero-shot manner. AnyCQ is not a CLQA method, and applying it to CLQA is infeasible due to its limited scalability.

Revision: We revised the Related Work section (Lines 134-137) to include the impracticality of applying AnyCQ to the standard CLQA task.


W3.

Furthermore, CKGC shows strong performance, but it has not been empirically tested.

Response: We found that the official implementation of CKGC uses both the training and validation graphs as the observed graph during testing, whereas the standard evaluation protocol followed by all other methods in Table 2 uses only the training graph. Since this provides CKGC with additional information unavailable to the other methods, its reported results are not directly comparable, and thus we did not include them in Table 2.

AuthorsOpenReview ↗

Response to Reviewer GKHt (2/2)

Q1.

How does the Dynamic Query Synthesizer construct training queries beyond those whose answers are directly derived from connected triplets in the KG? Does its reliance on queries with non-empty answer sets limit the diversity of synthesized queries or introduce biases that affect the model’s ability to handle queries with no valid answers at inference time?

Response: As stated in Appendix D, we probabilistically remove the edges used to construct queries in the KG, allowing training queries whose answers are not directly derived from connected triplets. Furthermore, since VASIL is primarily designed for the CLQA ranking task, it does not explicitly assume queries with no valid answers. While VASIL can handle queries with no valid answers via score thresholding, developing a more principled approach to address unanswerable queries remains an important direction for future work (Lines 529–531).


Q2.

Could the authors provide a controlled comparison with UltraQuery using the same four KGs and synthesized training queries, or evaluate VASIL trained on UltraQuery’s training data?

Response: As shown in its official repository, UltraQuery utilizes an Ultra backbone pre-trained on the exact same four KGs used in our experiments. Thus, VASIL and UltraQuery are trained on the identical set of KGs. The key distinction lies in how training queries are constructed. VASIL leverages our dynamic query synthesizer (one of the core contributions of our work) to generate diverse queries directly from these KGs. Our synthesizer encompasses complex structures such as non-tree-shaped queries and queries with multiple free variables, which UltraQuery cannot directly process. More importantly, while UltraQuery is fine-tuned on FB15k-237-BetaE training queries that share the same templates as the tree-shaped evaluation queries, VASIL is never exposed to any benchmark training queries.


Q3.

Could the authors clarify why AnyCQ, FIT/QTO with ULTRA, and AnyCQ with ULTRA are omitted from Table 1 and the experimental evaluation?

Response: These methods are omitted from Table 1 and the experimental evaluation because applying them to the standard CLQA task is computationally impractical:

  • FIT / QTO + Ultra: FIT and QTO operate on a neural adjacency matrix of size |R|×|V|×|V|, which contains the link predictor scores for all possible triples and is sparsified by a threshold. Ultra relies on a labeling trick that runs its GNN conditioned on each (head, relation) pair. Computing this matrix therefore requires re-encoding the graph with a separate GNN forward pass for every head entity and relation, i.e., |V|×|R| (≈6.9M on FB15k-237) forward passes. Even when the scores are computed on demand only for the intermediate candidates remaining after thresholding, the cost grows rapidly as the candidate sets become large.
  • AnyCQ, AnyCQ+Ultra: AnyCQ must verify every candidate entity individually for each query. Standard CLQA benchmarks contain thousands to tens of thousands of candidate entities, so this per-candidate verification becomes prohibitively costly. The cost grows further with Ultra. As mentioned above, Ultra must re-encode the graph with a separate GNN forward pass for every link prediction call made during verification due to its labeling trick.

To quantify this, we estimated the total evaluation time on FB15k-237-BetaE with a single A6000 GPU, based on the average inference time over five queries per query type:

MethodTime per QueryTotal Timevs. VASIL
AnyCQ4,868 s118.7k h (≈13.5 years)~10⁵×
AnyCQ + Ultra35,690 s870k h (≈99 years)~7×10⁵×
FIT + Ultra19.9 s486 h (≈20 days)~395×
QTO + Ultra31.7 s773 h (≈32 days)~630×
VASIL0.050 s1.23 h1×

Notably, AnyCQ-based methods require 13 to nearly 100 GPU-years, and even the fastest alternative, FIT with Ultra, requires over 395× more time than VASIL. Thus, these methods are impractical for CLQA.

Reviewer_2V9VOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
1
Read review
Paper summary

This paper introduces VASIL, an autoregressive foundational model for complex query answering (CLQA). They claim to be the first foundation model that can generalize to unseen entities and unseen relations without KG-specific training for non tree shaped queries with multiple variables. They manage to do so by a direct CLQA training rather than decomposing queries into link-prediction tasks (as UltraQuery does for example) and, hitting two targets with one shot, also getting rid of the tree-shape restriction appearing in SOTA methods.

The evidence that VASIL outperforms prior zero-shot CLQA methods is strong. Across tree-shaped, diverse-structure, and query-answer-classification benchmarks, VASIL consistently outperforms UltraQuery (the main SOTA zero-shot CLQA baseline), also on the fully-Inductive setting, which supports the main claim. This all while allowing non-tree-shaped or multi-free-variable queries.

Relative to prior methods, the proposed CLQA framework appears significantly broader in scope and better aligned with the characteristics expected of a foundation model. Nevertheless, the paper would benefit from a clearer explanation of this positioning regarding other models' restrictions.

Evidence for non-tree and multi-free variables are strong, the model outperforms previous methods on DAG benchmarks, EFOk-CQA benchmarks and EFO3 benchmarks.

Critical strengths

The paper strongly demonstrates the novelty of its methodology with strong fully-inductive results. Link prediction shows comparable performance than existing SOTA methods. Non-tree-shape and multi-free-variable queries are taken into account and the authors show SOTA performance on the corresponding benchmarks.

The statement about the expressivity of the dynamic query synthesizer is convincing as I understood it : any satisfiable conjunctive query corresponds to KG edges. Those edges can be covered by a finite collection of walks. Their generation process can replay those walks.

Finally ablations show substantial drops when removing: autoregression, query-conditioned labeling, complex query training, attention aggregation.

Critical weaknesses

The literature review does a reasonable job positioning the work with respect to the CLQA and logical query answering literature. However, I wonder how this method compares to UnRavL ( https://proceedings.mlr.press/v269/cucumides25a.html ). As that approach makes all methods that just use link predictors capable of answering other query shapes (and shows that early methods like MPQE can also be evaluated on these queries, though with poor performance). Moreover, all link predictor based methods, and I believe also UltraQuery, are such that they do in fact predict the intermediate variables. They just do not evaluate them in the original papers.

See question below on “all possible queries”.

Multiple free variables : CQD-Beam, QTO, and others can give answers to multiple free variables. This is a misrepresentation.

The random walk based method has a severe bias towards nodes with a high degree, which matches well with the bias in the evaluation datasets used. This implies that the results do not necessarily generalize to real-world use cases.

In the references, there are issues with the formatting. For example, capitalization of methods is wrong, or titles incomplete.

Questions for authors

The paper repeatedly characterizes VASIL as the first foundation model for arbitrary CLQA. However, prior work such as MPQE proposed a query-graph message-passing architecture capable of generalizing to unseen query structures. Could the authors clarify precisely which property (e.g., full-inductive transfer to unseen entities/relations/KGs, arbitrary EFO support, or some other criterion) distinguishes VASIL from MPQE and justifies the “first foundation model” claim?

A major claim in the paper is the ability to satisfy “all possible queries”. You address positive conjunctive EFO queries in the appendix. After that, you describe union and negation queries. I think the construction for unions is sound. However, for negations, you say you would negate some of the triples. This would mean that you can only construct queries with a negation if there is at least one pattern in the graph that has that pattern with that triple being positive. So, queries where that is not the case at all, could never be generated. Is this understanding correct? And is this a problem?

In table 2, for some of the entries that are indicated as “-”, it is unclear why there would be no results for that. For example, there are some entries under Tansductive/avg_p which have no entry for Transducitve+H/avg_p. Why?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 2V9V (1/2)

We appreciate the reviewer’s time and effort in reviewing our manuscript. Below, we provide our responses to the review comments. All line numbers refer to the revised manuscript. Our code is available at https://anonymous.4open.science/r/VASIL_3d7a/

W1.

However, I wonder how this method compares to UnRavL. As that approach makes all methods that just use link predictors capable of answering other query shapes (and shows that early methods like MPQE can also be evaluated on these queries, though with poor performance).

Response: Although UnRavL extends link-predictor-based methods to non-tree queries by unraveling them into tree-shaped approximations, it treats each revisit of a variable as an independent variable. For certain query structures such as cyclic queries, this may alter the semantics of the original query, since repeated occurrences of a variable are no longer constrained to bind to the same entity. In contrast, VASIL jointly predicts interdependent variables within the same subproblem, incorporating these dependencies into the variable representations.

Revision: We have added a citation and discussion of UnRavL to the Related Work section (Lines 110-112).


W2.

Moreover, all link predictor based methods, and I believe also UltraQuery, are such that they do in fact predict the intermediate variables. They just do not evaluate them in the original papers.

Response: While link-predictor-based methods such as UltraQuery also predict intermediate variables, they score each atom independently with the link predictor. When intermediate variables are interdependent, as in cyclic queries, their mutual dependency cannot be captured by a link predictor. In contrast, VASIL groups interdependent variables into the same subproblem and predicts them jointly (Section 4.2), incorporating their dependencies into the variable representations.


W3&Q2.

A major claim in the paper is the ability to satisfy “all possible queries”. You address positive conjunctive EFO queries in the appendix. After that, you describe union and negation queries. I think the construction for unions is sound. However, for negations, you say you would negate some of the triples. This would mean that you can only construct queries with a negation if there is at least one pattern in the graph that has that pattern with that triple being positive. So, queries where that is not the case at all, could never be generated. Is this understanding correct? And is this a problem?

Response: While our dynamic query synthesizer can only generate negation queries whose positive counterpart has at least one grounding in the graph, this does not affect VASIL's ability to handle negation queries. During training, we utilize the dynamic query synthesizer to generate only positive queries. Since VASIL handles negation probabilistically (Lines 301-313), it does not require training on negation queries. Notably, VASIL achieves comparable performance in Table 2 and superior performance in Table 3 on negation queries (see avgn\text{avg}_n, the average over negation queries, in Tables 2 and 3).

Revision: We revised Section 4.1 (Lines 223, 228-229) to clearly distinguish between the query set generated for training VASIL and the capability of VASIL to answer arbitrary queries, including those with negation and union.


W4.

Multiple free variables : CQD-Beam, QTO, and others can give answers to multiple free variables. This is a misrepresentation.

Response: If free variables are independent of each other, the query simply decomposes into separate queries, each with a single free variable. Multiple free variables therefore pose a distinct challenge when they are mutually dependent, i.e., when the assignments of free variables depend on each other. Accordingly, by "multiple free variables", we refer to the capability to jointly predict such mutually dependent free variables. Methods such as CQD-Beam and QTO predict answers for multiple free variables by first fixing one free variable's prediction and then inferring the others, and thus cannot perform joint prediction. In contrast, VASIL jointly predicts mutually dependent free variables on queries with arbitrary structures, capturing the interdependence between them.

AuthorsOpenReview ↗

Response to Reviewer 2V9V (2/2)

W5.

The random walk-based method has a severe bias towards nodes with a high degree, which matches well with the bias in the evaluation datasets used. This implies that the results do not necessarily generalize to real-world use cases.

Response: Although our random walk-based query synthesizer may favor high-degree nodes, we believe this bias has limited impact on VASIL’s generalization. VASIL is evaluated in a zero-shot manner: the KGs used for inference are not observed during training. Nevertheless, our experiments demonstrate that VASIL performs strongly across diverse KGs and query structures. This suggests that VASIL does not overfit to the distribution induced by the synthesizer and generalizes robustly to unseen distributions, supporting its applicability to real-world use cases.

For further elaboration, we compare the degree statistics of the pre-training KGs with two evaluation KGs, Organization and Science, in the table below.

KGUsageMean degreeMax degree
FB15k-237Pre-training37.527,614
CoDEx-MPre-training21.776,224
NELLPre-training3.611,780
WN18RRPre-training4.28482
OrganizationEvaluation6.0457
ScienceEvaluation2.501,372

Both KGs have degree distributions that differ from those of the pre-training KGs, with much lower mean or maximum degrees. Even so, VASIL achieves state-of-the-art performance on both datasets (Tables 30, 31). This indicates that VASIL does not depend on the high-degree bias of the synthesizer.


W6.

In the references, there are issues with the formatting. For example, capitalization of methods is wrong, or titles incomplete.

Response: We thank the reviewer for bringing this to our attention. We have rechecked the reference list but could not identify the entries in question. We would be grateful if the reviewer could point us to specific examples so that we can make the necessary corrections.


Q1.

The paper repeatedly characterizes VASIL as the first foundation model for arbitrary CLQA. However, prior work such as MPQE proposed a query-graph message-passing architecture capable of generalizing to unseen query structures. Could the authors clarify precisely which property (e.g., full-inductive transfer to unseen entities/relations/KGs, arbitrary EFO support, or some other criterion) distinguishes VASIL from MPQE and justifies the “first foundation model” claim?

Response: While MPQE generalizes to unseen query structures via message passing over query graphs, MPQE relies on KG-specific entity and relation parameters and therefore cannot transfer to unseen KGs. Moreover, it does not support predictions for queries involving negation or multiple free variables. In contrast, VASIL is the first CLQA model that simultaneously supports (i) zero-shot transfer to unseen KGs, including unseen entities and relations, with a single pre-trained model, and (ii) EFO queries with arbitrary structures, including cyclic queries, multi-edge queries, queries with multiple free variables, and queries with negation and union.

Revision: We have added a citation and discussion of MPQE to the Related Work section (Lines 120-123).


Q3.

In table 2, for some of the entries that are indicated as “-”, it is unclear why there would be no results for that. For example, there are some entries under Tansductive/avg_p which have no entry for Transducitve+H/avg_p. Why?

Response: As described in the Experiments section (Lines 353-354), "-" denotes either that the method is not applicable to the setting or that no publicly available results exist. We further clarify the “–” entries in Table 2 column by column:

  • Transductive / Transductive+H: All “–” entries indicate that results are not publicly available. The only exception is avg$_{n}$ of NPQE, which is not applicable since NPQE does not support negation.
  • Semi-Inductive: All “–” entries indicate that the method is not applicable, except for SAQE. SAQE is applicable, but its results on some datasets are not publicly available. Since Table 2 reports averages over all datasets, we could not include SAQE in the table. NPQE does not support negation, so its avg_n is not applicable.
  • Fully-Inductive: All “–” entries indicate that the method is not applicable. These methods are tied to a fixed relation vocabulary and cannot handle unseen relations.
Reviewer_VrGnOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a zero-shot query answering framework for knowledge graphs (KGs), aiming to answer existential first-order (EFO) queries on previously unseen KGs without requiring KG-specific training.

Critical strengths
  1. The paper introduces a zero-shot approach to answering existential first-order queries, demonstrating promising query answering accuracy on previously unseen knowledge graphs.

  2. The proposed dynamic query synthesizer is an interesting component that appears to facilitate more interpretable and potentially verifiable query answering.

Critical weaknesses
  1. Overly broad claims regarding the limitations of existing methods. The authors claim that existing approaches struggle with complex query structures and inductive generalization. However, this characterization appears overly broad and does not adequately account for recent advances. For example, AnyCQ [1] supports arbitrary conjunctive queries, including query graphs with multiple cycles and multiple free variables, without being restricted to predefined operator trees. The authors should more carefully position their contributions relative to such recent work and clarify which specific limitations their method addresses.

  2. Inaccurate characterization of earlier query embedding methods. The claim that earlier query embedding approaches are limited to query structures encountered during training is not entirely accurate. For instance, Query2Box [2] explicitly evaluates generalization to query structures that were not observed during training. Although Query2Box relies on KG-specific embeddings, which may limit its applicability to unseen KGs, this does not imply that it is restricted to query templates seen during training. The paper should distinguish more clearly between generalization to unseen query structures and generalization to unseen knowledge graphs.

  3. Lack of qualitative analysis and case studies. The paper lacks sufficient case studies or qualitative examples to illustrate how the proposed method works in practice. Including representative examples, particularly on unseen KGs or challenging query structures, would help readers better understand the method's behavior, advantages, and potential limitations.

  4. Concerns about the evaluation metrics. Many of the evaluation metrics reported in the main experiments appear difficult to independently verify or assess based on the information provided. This raises concerns about the rigor and transparency of the evaluation protocol and makes it difficult to determine whether the experimental results convincingly demonstrate the effectiveness of the proposed approach. The authors should provide clearer explanations and justifications for their choice of metrics, along with sufficient details to support their verification.

[1] Olejniczak et al. (2025). One Model, Any Conjunctive Query: Graph Neural Networks for Answering Queries over Incomplete Knowledge Graphs. LoG 2025.

[2] Ren et al. (2020). Query2Box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings. ICLR 2020.

Questions for authors

Please address the concerns raised in the Critical Weaknesses section, particularly regarding the positioning of the proposed method relative to AnyCQ and Query2Box, the generalization claims, and the validity and verifiability of the evaluation metrics.

2 comments
AuthorsOpenReview ↗

Response to Reviewer VrGn (1/2)

We appreciate the reviewer’s time and effort in reviewing our manuscript. Below, we provide our responses to the review comments. All line numbers refer to the revised manuscript. Our code is available at https://anonymous.4open.science/r/VASIL_3d7a/

W1.

Overly broad claims regarding the limitations of existing methods. The authors claim that existing approaches struggle with complex query structures and inductive generalization. However, this characterization appears overly broad and does not adequately account for recent advances. For example, AnyCQ [1] supports arbitrary conjunctive queries, including query graphs with multiple cycles and multiple free variables, without being restricted to predefined operator trees. The authors should more carefully position their contributions relative to such recent work and clarify which specific limitations their method addresses.

Response: As discussed in the Related Work (Lines 127–139), AnyCQ and VASIL address different problem settings. AnyCQ targets Boolean query evaluation, whereas VASIL targets CLQA, a ranking task over the entire entity set. Evaluating AnyCQ under the standard CLQA setting requires individually verifying every candidate entity per query, making full-scale evaluation computationally infeasible. We measured per-candidate inference time on FB15k-237-BetaE with a single A6000 GPU. Evaluating a single query takes on average 4,868 seconds. This amounts to 118,736 GPU hours (~13.5 GPU-years) for the full test set. In contrast, VASIL completes the evaluation on the entire test set in 1.23 GPU hours under the same environment. For these reasons, AnyCQ cannot be practically applied to existing CLQA benchmarks or to real-world scenarios with a large number of candidate entities. On the other hand, since VASIL can be applied to Query Answer Classification (QAC), a task introduced by AnyCQ, we compare VASIL and AnyCQ on QAC benchmarks, where VASIL outperforms AnyCQ (Table 4).

VASIL is the first CLQA method that can simultaneously (i) handle complex queries with arbitrary structures and (ii) transfer to unseen KGs in a zero-shot manner. AnyCQ is not a CLQA method, and applying it to CLQA is infeasible due to its limited scalability.

Revision: We revised the Related Work section (Lines 134-137) to include the impracticality of applying AnyCQ to the standard CLQA task.


W2.

Inaccurate characterization of earlier query embedding methods. The claim that earlier query embedding approaches are limited to query structures encountered during training is not entirely accurate. For instance, Query2Box [2] explicitly evaluates generalization to query structures that were not observed during training. Although Query2Box relies on KG-specific embeddings, which may limit its applicability to unseen KGs, this does not imply that it is restricted to query templates seen during training. The paper should distinguish more clearly between generalization to unseen query structures and generalization to unseen knowledge graphs.

Response: Query2Box learns projection and intersection operators and handles unions via disjunctive normal form, allowing it to generalize to unseen query structures. This generalization, however, is limited to tree-shaped queries (Lines 100–103). Query2Box computes the query embedding by applying operators sequentially from the anchor entities to the target variable, deriving each variable from its predecessors along a tree. Hence, non-tree queries must first be converted into trees. However, this conversion may alter the semantics of the original query, since repeated occurrences of a variable are no longer constrained to bind to the same entity. In contrast, VASIL can answer any query expressible as a query graph, including non-tree queries.

Revision: We revised Lines 40-42 to clarify that early CLQA approaches are limited to tree-shaped queries.

AuthorsOpenReview ↗

Response to Reviewer VrGn (2/2)

W3.

Lack of qualitative analysis and case studies. The paper lacks sufficient case studies or qualitative examples to illustrate how the proposed method works in practice. Including representative examples, particularly on unseen KGs or challenging query structures, would help readers better understand the method's behavior, advantages, and potential limitations.

Response: In the original submission, we provided a case study on the change of prediction for different combinations of the queries in Section 5.4 and the qualitative examples of our dynamic query synthesizer in Appendix B. Below, we provide an additional case study on a tree-shaped query and a cyclic query from ICEWS18+H, a KG unseen during VASIL's pre-training. Starting from the variable farthest from the target free variable, VASIL first predicts each intermediate variable as a distribution over entities. In the cyclic query, intermediate variables that belong to the same subproblem are predicted jointly in a single step (y1y_1 and y2y_2 in Step 1). The predicted distributions serve as soft labels for predicting the target variable. We list the top-3 predicted entities for each intermediate variable and the target free variable, with predicted probabilities shown in parentheses and ✓ marking a correct prediction.

Case 1: Tree-Shaped Query q=x,.,∃y1:;Express intent to cooperate(y1,Uzbekistan) ∧;Consult(x,y1)∧Consult(x,Li Keqiang)\begin{aligned} q = x \\,.\\, \exists y_1 :\\; & \text{Express intent to cooperate}(y_1, \text{Uzbekistan}) \\\ \wedge\\; & \text{Consult}(x, y_1) \wedge \text{Consult}(x, \text{Li Keqiang}) \end{aligned}

Ranky1y_1 (Step 1)xx (Step 2)
1Afghanistan (0.214) ✓Vladimir Putin (0.275) ✓
2Kyrgyzstan (0.200) ✓Nursultan Nazarbayev (0.245) ✓
3Kazakhstan (0.190) ✓Representatives (South Korea) (0.142) ✓

Case 2: Cyclic Query q=x,.,∃y1,y2:;Consult(Brett McGurk,y1)∧Demonstrate or rally(Protester (UK),y2) ∧;Express intent to meet or negotiate(y1,y2) ∧;Express intent to cooperate(y1,x)∧Make statement(x,y2)\begin{aligned} q = x \\,.\\, \exists y_1, y_2 :\\; & \text{Consult}(\text{Brett McGurk}, y_1) \wedge \text{Demonstrate or rally}(\text{Protester (UK)}, y_2) \\\ \wedge\\; & \text{Express intent to meet or negotiate}(y_1, y_2) \\\ \wedge\\; & \text{Express intent to cooperate}(y_1, x) \wedge \text{Make statement}(x, y_2) \end{aligned}

Ranky1y_1 (Step 1)y2y_2 (Step 1)xx (Step 2)
1Mohammed bin Salman (0.385) ✓United Kingdom (0.234) ✓Emmanuel Macron (0.288) ✓
2Royal Administration (Saudi Arabia) (0.318) ✓Donald Trump (0.214) ✓Boris Johnson (0.199) ✓
3Jens Stoltenberg (0.229) ✓Theresa May (0.171) ✓Donald Trump (0.160) ✓

In both examples, the top three predictions are all ground-truth entities. The intermediate distributions retain multiple valid entities and are passed to the next prediction step as soft labels. These examples illustrate how VASIL resolves variables sequentially to answer queries, jointly predicting mutually dependent ones as in the cyclic query.

Revision: We added this additional case study in Section 5.4 (Lines 484-517) and Table 7 in the revised manuscript.


W4.

Concerns about the evaluation metrics. Many of the evaluation metrics reported in the main experiments appear difficult to independently verify or assess based on the information provided. This raises concerns about the rigor and transparency of the evaluation protocol and makes it difficult to determine whether the experimental results convincingly demonstrate the effectiveness of the proposed approach. The authors should provide clearer explanations and justifications for their choice of metrics, along with sufficient details to support their verification.

Response: As described in Lines 369-371, 409-410, 431, and 455, we follow each benchmark's standard evaluation protocol and report its standard metric, which differs across benchmarks. This allows us to rigorously and transparently compare VASIL with the baselines. Baseline results are taken from their original papers or the corresponding benchmark papers unless otherwise stated (Lines 351–357). Detailed comparisons by dataset and query type are provided in Appendices F, G, and H.

Comments on the paper

1 comment
Area_Chair_sEVuOpenReview ↗

Please engage in the discussion with authors

Reviewers 2V9V and GKHt,

The discussion deadline is approaching. Please engage in the discussion with authors, thank you.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.