복잡한 질의 응답 (Complex Query Answering, CQA)은 불완전한 지식 그래프 (Knowledge Graphs, KGs) 상에서 수행되는 근본적인 지식 표현 및 추론 작업입니다. $k$개의 자유 변수를 가진 존재론적 1차 질의 (existential first-order queries, 즉 $\text{EFO}_k$ 질의)에 답하는 것은 매우 중요하지만 도전적인 문제인데, 이는 $\mathcal{E}$가 KG의 엔티티 집합을 나타낼 때 $\mathcal{E}^k$ 내의 정답 튜플 (answer tuples)을 순위 매겨야 하기 때문입니다. $k$가 증가함에 따라 이 문제는 빠르게 처리 불가능한 수준이 됩니다. 결과적으로, 기존의 벤치마크와 방법론들은 개별 변수에 대한 주변 순위 (marginal rankings)에 의존하고 있습니다. 그러나 주변 순위는 튜플의 실제 결합 순위 (joint ranking)를 나타내는 불충분한 대리 지표입니다. $\text{EFO}_1$ 질의를 위한 신경망 심볼릭 탐색 (neural symbolic search)을 기반으로, 우리는 $\mathcal{E}^k$를 열거하지 않고도 결합 순위를 근사하는 예산 기반 프레임워크인 NS3 (Neural Scalable Symbolic Search)를 제안합니다. NS3는 (i) 필요한 후보 집합을 얻기 위해 주변화된 하위 질의 (marginalized sub-queries)에 답하고, (ii) 동적 예산 $B$에 의해 도메인이 가지치기(pruned)되고 제어되는 하이퍼노드 (hypernodes)로 여러 자유 변수를 병합하며, (iii) 예산이 할당된 축소된 도메인 위에서 $\text{EFO}k$ 질의를 $\text{EFO}{k-1}$ 질의로 점진적으로 축소합니다. 세 가지 표준 KG 데이터셋에 대해, NS3는 강력한 주변 정확도 (marginal accuracy)를 유지하면서 결합 순위 성능을 실질적으로 향상시킵니다. 우리는 더 나아가 기존 $\text{EFO}_1$ 데이터셋을 $k=3$까지 확장하여 다중 변수 질의의 체계적인 평가를 가능하게 하는 결합 순위 벤치마크를 공개합니다. 우리의 코드는 https://github.com/HKUST-KnowComp/NS3_KDD2026 에서 제공됩니다.