{"id":"1acd535d-5115-4f57-9fe8-74e3551ff958","arxiv_id":"2505.08155","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A complex query answering method reduces symbolic search to top-k candidate domains and uses approximate local search for cycles, reaching near-FIT accuracy at a fraction of the cost.","lead":"This paper introduces NLISA, a neural-symbolic search framework that prunes the candidate entity set for each query variable to a small top-k list, then runs a quadratic-cost local search to answer complex knowledge graph queries including cyclic ones. It reports nearly lossless accuracy on standard benchmarks while making large-scale graphs feasible.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The top-k index recall assumption is unverified and load-bearing; without direct recall measurements, the near-lossless MRR claims do not establish that reduced domains preserve the answer set.","rationale":"The reader identified the top-k recall assumption as the weakest point, and my independent reading reaches the same conclusion. The paper's central claim—that reducing each variable's domain to a top-k set cuts data complexity from O(|E|^2) to O(|D|^2) while preserving MRR—depends entirely on the assumption that the correct intermediate entities appear in the reduced domains. The paper provides no theoretical bound, no recall analysis, and only indirect empirical evidence through final MRR. A direct oracle-recall check would settle whether the assumption actually holds on the benchmarks. This is a fixable weakness rather than a fundamental inconsistency; the method may work well, but the paper does not currently demonstrate why. Therefore the appropriate verdict remains CONDITIONAL, as the reader proposed. I do not see a need to move to ACCEPT or REJECT based on this concern alone.","tokens_in":598,"tokens_out":3778,"duration_ms":152559,"concrete_test":"Reconstruct the ground-truth witness assignments for all BetaE and Real EFO1 test queries (these benchmarks are generated by sampling paths, so intermediate entities are available). For each query, for both NLISA(Local) and NLISA(Global), compute whether every existential variable and the free variable's true answer lie in the corresponding reduced domains D_x and D_y, using the paper's k settings (2000, 2000, 6000, and 8000). Report recall@k per query type. If recall@k is below 99% for any query type, the near-lossless MRR is achieved despite truncated search domains, and the claim that NLI preserves answer sets is unsupported; if recall@k is high, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1 defines the reduced domain as I(x) = Topk(h(GS_x), k) and then restricts the optimization in Eq. (4) to these domains. If any true intermediate entity is missing from its variable's top-k set, no later search step can recover it, so the final answer set is irreversibly truncated. This is the central premise for the claimed O(|D|^2) complexity and the 'nearly the same performance' result. The paper never measures the recall of these neural logical indices; it only reports final MRR. That indirect evidence is insufficient because a query embedding could rank a true free-variable answer highly even when the intermediate domains omit the true existential witness, especially with t-norm scoring that tolerates low-probability partial assignments. The issue applies to both the local constraints strategy (Section 3.2), which predicts relation tails without conditioning on the anchor entity, and the global constraints strategy (Section 3.3/Appendix C), where LMPNN is used to score existential variables as if they were free variables. On FB400K (Section 6.3), only 2% of entities are retained, making the recall assumption even more extreme, yet no recall statistic is reported. Without a direct check of whether the true witnesses lie in the top-k domains, the paper's core efficiency claim is not adequately supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes NLISA, a neural-symbolic search framework for answering existential first-order logic (EFO1) queries over knowledge graphs. It computes neural logical indices that restrict each variable's search domain to a top-k candidate set, using either local constraints (relation-tail prediction via a hypernet) or global constraints (query embeddings, specifically LMPNN). For cyclic queries, it replaces the exact enumeration used by FIT with a greedy autoregressive local search. The authors claim this reduces data complexity from O(|E|^2) to O(|D|^2), makes cyclic queries tractable in quadratic time, cuts computational load by 90%, and maintains close to the MRR of the precise symbolic baseline FIT across tree-form and cyclic benchmarks, including on a 400K-entity graph.","tokens_in":17003,"tokens_out":7869,"duration_ms":79396,"significance":"If the claims hold, the paper offers a practical scalability recipe for neural-symbolic CQA: prune the search space aggressively with learned indices, then solve the remaining optimization with a parallel local search. The experiments are comprehensive in coverage (three KG sizes, tree-form and cyclic queries), the code is provided, and I do not see a direct scoring circularity in the design: final answer scores are computed from KG embedding truth values, not from the models used to build the reduced domains. The main value is conditional, however, on the recall of the top-k domains and on an honest accounting of the index-construction cost, neither of which is currently established. The approximate cyclic-query solver is also validated only through aggregate MRR, so its behavior on individual queries remains opaque.","major_comments":[{"comment":"The central premise is that I(x)=Topk(h(GS_x), k) contains the true entities for every variable, but this premise is never directly tested. Because Eq. (4) restricts the optimization to xi in Di, any true witness that falls outside the top-k set is irrecoverable in later search steps. The paper reports only final MRR, which can remain high even when existential witnesses are pruned: the t-norm aggregation in Eq. (4) tolerates low-probability partial assignments, and the free-variable ranking may still place the true answer near the top. This concern is most acute in Section 6.3, where |D| is only 2% of |E| on FB400K. Please report recall@k of the neural logical indices separately for existential and free variables, and separately for cyclic and acyclic queries, ideally restricted to hard answers, so the reader can verify that the reduced domains preserve the true witnesses.","section":"Section 3.1, Eq. (4)"},{"comment":"The stated time complexity O((|Dx||Dy| + |Ex|^2 + |Dx| + |Dy|)d) covers node removal and local optimization, but it omits the CUTDOMAIN step. Computing I(x) for each variable requires ranking entities by h(GS_x), which costs at least O(|E|) per variable under the scoring functions described; the paper does not describe an approximate-nearest-neighbor or precomputed-index scheme. If indices are built per query, the end-to-end complexity still contains an |E| term, and if they are precomputed offline, the storage and update costs must be stated. The symbol |Ex| is undefined. Please provide an end-to-end complexity statement and an empirical runtime breakdown that includes index construction, since this is load-bearing for the scalability claim.","section":"Section 4.3, Algorithm 1"},{"comment":"The headline speedups in the abstract (10x) and introduction (13x) are not supported by the efficiency table. From Table 2, the QPS ratios relative to FIT are approximately 3.7x/2.8x on FB15k-237 (local/global), 5.5x/4.0x on FB15K, and 11.7x/6.7x on NELL; no configuration reaches 13x, and only NELL-local reaches roughly 10x. Please state exactly which configuration and experimental setup produce the claimed 10x/13x speedups, and report total end-to-end time including CUTDOMAIN rather than only the search phase. This matters because the abstract's '90% computational load reduction' is not by itself a wall-clock speedup claim.","section":"Section 6.1, Table 2"},{"comment":"The greedy autoregressive local search is the only mechanism for escaping the NP-hard enumeration of cyclic queries, yet its approximation quality is validated only indirectly through aggregate MRR. I recommend a direct validation: on a subset of cyclic queries with small reduced domains, compare the greedy assignment's truth value and final answer rank against exact enumeration, and report the fraction of queries where the greedy solution matches the exact optimum. This would substantiate the claim that cyclic queries are approximately solved in quadratic time rather than merely reporting comparable average MRR.","section":"Section 4.2, Eq. (5)"}],"minor_comments":[{"comment":"The text contains an unresolved reference 'As shown in Fig. ??'; the efficiency figure for Real EFO1 queries is missing and should be included.","section":"Section 6.2"},{"comment":"The notation contains typos and undefined symbols: |Ex| appears in the complexity formula without definition, and the expression |Dy|×|D_y| in Section 4.1 appears malformed. Also, 'QSP' in Section 6.1 should be 'QPS'.","section":"Sections 4.1 and 4.3"},{"comment":"The global constraints strategy is described in only two short paragraphs; please provide the actual algorithm for treating existential variables as free variables with LMPNN, including how negated edges and cyclic query graphs are handled.","section":"Appendix C"},{"comment":"The hypernet MRR values of 0.99-1.0 on relation tail prediction are surprisingly high; please describe the evaluation protocol (filtered vs unfiltered, candidate set size) and explain why the task is nearly saturated, since this is important for interpreting the quality of the local-constraint indices.","section":"Table 5"},{"comment":"The conclusion says 'with a 10% reduced search domain, our method achieves 90% performance'; this phrasing conflates search-space reduction with performance retention. Please reword to distinguish 10% of the search space from the reported relative MRR values, and reconcile the 97% claim in the introduction with the 90% wording here.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take on arXiv:2505.08155: the central idea is worth your time. The paper prunes each variable's search domain to a top-k candidate set using a learned relation-tail predictor (local) or a query embedding (global), then runs symbolic search on the reduced domains. That turns O(|E|^2) work into O(|D|^2) and allows cyclic queries to be handled with a quadratic-time local search instead of enumeration. On BetaE and Real EFO1, the method keeps roughly 95-100% of FIT's MRR while running substantially faster, and on the 400K-entity Smore graph it beats CQD-CO with the same backbone. Code is available. That's a genuinely useful addition to the neural-symbolic CQA toolbox.\n\nThe soft spots are real but fixable. The stress-test's main worry is that the top-k index recall is never measured. That's fair: if a true intermediate witness falls outside the domain, no later step can recover it, and final MRR is only indirect evidence. A direct recall check for the indices, especially for existential variables, would settle it. That said, the FB400K result (58.9 MRR vs 43.3 for CQD-CO) gives me some confidence the pruning is not silently dropping answers; it's hard to see how you beat the full-domain baseline by that margin if the domains were missing the true witnesses.\n\nThe more annoying issues are presentation. The abstract says \"10x speedup\" and the intro says \"13x\", but Table 2's QPS numbers imply a range of roughly 3x-12x depending on dataset and variant. The speedup claim needs to be tied to a specific comparison. The paper also has a missing figure reference (\"Fig. ??\") for the cyclic-query efficiency results, and the conclusion says \"90% performance\" where the abstract says 97% MRR--those should be reconciled. The statement that the approximate search is \"precise for acyclic queries\" is misleading once you've pruned to top-k domains; it's precise only if the domains are complete.\n\nNo error bars is a minor gripe, not a dealbreaker, but it would help to know if the small differences from FIT are noise. The implementation details for the global constraints strategy are thinner than I'd like, but there is code.\n\nBottom line: this deserves serious peer review. The core idea is good, the experiments are suggestive, and the open questions (top-k recall, actual speedup, cyclic-query efficiency) are all answerable. I'd send it to review with a request for a recall analysis and a cleanup of the claims. If I worked on KG reasoning, I'd cite it.\n\nBest.","headline":"Solid top-k pruning idea with strong empirical results; the recall assumption is worth probing, and the speedup claims need better support.","tokens_in":17509,"tokens_out":4212,"would_cite":true,"duration_ms":40363,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"NLISA achieves near-FIT accuracy at a tenth of the search cost by replacing full variable domains with top-k neural indices and solving the cyclic core by local search.","keywords":["complex query answering","knowledge graphs","neural-symbolic search","neural logical indices","local search","cyclic queries","scalability","fuzzy logic"],"falsifier":"Construct a benchmark case where the correct intermediate entity is ranked just below $k$ by the neural index while the precise FIT method assigns it high fuzzy truth; run NLISA at that $k$ and check whether the final MRR drops specifically because that entity cannot be reached. If the loss appears and cannot be explained by the local search on a full domain, the top-$k$ cut is falsified as a universally safe reduction.","tokens_in":16500,"feed_emoji":"⚡","tokens_out":9377,"duration_ms":83735,"temperature":0.7,"pith_summary":"Complex query answering over knowledge graphs has two scalability walls: symbolic search over all entities costs $O(|E|^2)$ time, and cyclic queries are NP-hard. This paper argues both walls can be bypassed by computing a Neural Logical Index for each query variable; a top-$k$ list of candidate entities returned by a neural link predictor; and using that reduced domain as the search space. For cyclic queries, it replaces exact enumeration with an autoregressive local search that is quadratic in the reduced domain. The paper reports that on standard benchmarks the method keeps about 97% of the MRR of the precise FIT baseline while cutting search-space and compute by 90%, and it runs on a 400,000-entity graph where FIT runs out of memory. If it is right, interpretable symbolic reasoning becomes practical on large knowledge graphs and on query shapes that previously caused exponential blowups.","feed_headline":"Pruning the search space makes knowledge graph queries 13x faster","feed_subtitle":"A 10% candidate set plus local search keeps 97% of exact accuracy, even on cyclic queries.","key_machinery":"The load-bearing object is the Neural Logical Index, $I(x) = \\operatorname{Topk}(h(G_S^x), k)$, a map from each query variable to a small candidate-entity set produced by applying a neural ranking function $h$ to the variable's constraint subgraph $G_S^x$. The local strategy computes the index from only the relations adjacent to the variable, using a hypernetwork-adapted relation-tail predictor; the global strategy uses a query embedding model over the whole query. A second mechanism is the local-search step, which fixes the free-variable candidate and greedily assigns the remaining variables by maximizing the t-norm truth value of their local constraints, giving $O(|D_x|^2+|D_x||D_y|)$ work per candidate. Together the index (the $CUTDOMAIN$ operation) and the local optimizer replace full-domain enumeration and carry the paper's complexity claims.","core_discovery":"The paper's claim is that precise search over the full entity set is unnecessary: every variable in an EFO1 query can be assigned a reduced domain $D_x = I(x) = \\operatorname{Topk}(h(G_S^x), k)$, where $h$ ranks entities by how well they satisfy the constraints in the variable's neighborhood (local strategy) or the whole query graph (global strategy). Working inside these domains changes the cost of node removal from $O(|E|^2)$ to $O(|D_x|^2+|D_x||D_y|)$ per operation, and the remaining cyclic core is handled by greedily optimizing variable assignments from the free variable outward, a quadratic parallel local search rather than exponential enumeration. Empirically the paper shows NLISA reaches roughly 97% of FIT's MRR on tree queries with a $10\\times$ speedup using 10% of the search space, and on cyclic Real EFO1 queries it keeps about 95% of FIT's performance. The named contribution is that general EFO1 complex query answering, including NP-hard cyclic instances, becomes tractable under data and query complexity that are both quadratic in the reduced domain.","pith_inferences":["The top-k recall assumption could be tested directly: run FIT on a sample of queries, form its exact fuzzy vectors, and measure how often the true intermediate entity falls outside the neural index at various $k$; that would isolate pruning loss from search loss.","The same domain-cutting recipe transfers to any learned-scoring constraint satisfaction problem: if a neural scorer can rank candidates for each variable, the search can be restricted to top-$k$ sets without changing the search algorithm.","NLISA's global variant is only as strong as the query embedding model used to build the index; improving query embeddings would improve NLISA(Global) independently of the search machinery, a claim the paper does not test.","The paper's appendix notes that the parallel caching scheme for the training-fact mask cannot mark observed edges in parallel and may cause a small performance drop; a fair reproduction should treat that as an implementation caveat when comparing against FIT's exact mask."],"forward_implications":["Symbolic complex query answering can be run on knowledge graphs with hundreds of thousands of entities, where exact methods like FIT exhaust memory.","Cyclic EFO1 queries, previously exponential via variable enumeration, are answerable in quadratic time at near-baseline accuracy.","The same precise node-removal pipeline can be kept for acyclic tree queries, so the method is an accelerator that preserves exactness where possible rather than a wholesale replacement.","The search-space fraction $|D|/|E|$ becomes an explicit accuracy-efficiency knob: at 10% it gives roughly 97% relative MRR, and users can trade accuracy for speed by changing $k$.","Because the reduced-domain operations are parallelizable and cache-friendly, the method's queries-per-second approaches query-embedding models while retaining symbolic interpretability."],"supporting_citations":[{"why":"supplies the arc-consistency view that motivates pruning variable domains to candidate sets.","marker":"(Chen et al., 2011)"},{"why":"defines the BetaE benchmark and the MRR/HIT evaluation protocol used for tree-form queries.","marker":"(Ren and Leskovec, 2020)"},{"why":"provides the ComplEx embedding model that is adapted for link prediction and relation-tail prediction.","marker":"(Trouillon et al., 2016)"},{"why":"introduces the relation-prediction auxiliary training setup on which the hypernetwork-based local constraints are built.","marker":"(Chen et al., 2021)"},{"why":"supplies CQD-CO, a neural link predictor baseline and the pretrained checkpoints reused for fair comparison.","marker":"(Arakelyan et al., 2020)"},{"why":"defines QTO, the precise tree-form symbolic search that the reduced-domain pipeline accelerates.","marker":"(Bai et al., 2023b)"},{"why":"defines FIT, the precise search baseline for general EFO1 queries, and the Real EFO1 benchmark with cyclic query types.","marker":"(Yin et al., 2024)"},{"why":"provides the Smore large-scale FB400K benchmark and baseline numbers showing exact methods run out of memory.","marker":"(Ren et al., 2022)"},{"why":"provides LMPNN, the query-embedding model used to compute global-constraint neural logical indices.","marker":"(Wang et al., 2023b)"}],"fun_headline_variants":["KG queries 10x faster using 10% of search space","97% of accuracy with a tenth of the search space","Symbolic search scales: 10x speedup, cyclic support","Prune to 10%: Complex KG queries get 10x speedup","Efficient symbolic search for large-scale KG queries"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on the unproven assumption that every entity that could contribute to a correct answer is already inside the short top-k candidate list the neural index returns, because anything outside that list is never reconsidered.","fun_headline_variants_meta":{"raw":{"variants":["KG queries 10x faster using 10% of search space","97% of accuracy with a tenth of the search space","Symbolic search scales: 10x speedup, cyclic support","Prune to 10%: Complex KG queries get 10x speedup","Efficient symbolic search for large-scale KG queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000254,"raw_usage":{"total_tokens":1587,"prompt_tokens":984,"completion_tokens":603,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":515}},"tokens_in":600,"tokens_out":603,"duration_ms":6316,"temperature":1.0,"reasoning_tokens":515,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:02:14.335862+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a benchmark case where the correct intermediate entity is ranked just below $k$ by the neural index while the precise FIT method assigns it high fuzzy truth; run NLISA at that $k$ and check whether the final MRR drops specifically because that entity cannot be reached. If the loss appears and cannot be explained by the local search on a full domain, the top-$k$ cut is falsified as a universally safe reduction.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the relation-prediction auxiliary training setup on which the hypernetwork-based local constraints are built."}],"review_version":1}