생성형 정보 검색(GIR)은 문서 검색을 기존의 '검색 후 순위화(retrieve-and-rank)' 워크플로에서 모델이 문서 식별자(DocID)를 직접 예측하는 시퀀스-투-시퀀스(sequence-to-sequence) 생성으로 전환하며 혁신적인 패러다임으로 부상했습니다. 이러한 DocID의 시맨틱 설계가 성능에 결정적이라는 점은 잘 알려져 있으나, '무엇이 좋은 DocID를 만드는가?'라는 근본적인 질문은 여전히 충분히 탐구되지 않았습니다. 기존 접근 방식은 계산 비용이 큰 다운스트림 평가에 크게 의존하여 체계적인 분석과 빠른 반복(iteration)을 저해합니다. 본 연구에서는 효과적인 수치형 DocID를 정의하는 속성, 메트릭, 트레이드오프에 대한 포괄적인 연구를 제시하여 이 문제를 해결합니다. 구체적으로 본 연구의 기여는 세 가지입니다. 첫째, 단일 설계 공간 내에서 곱 양자화(Product Quantization, PQ)와 잔차 양자화(Residual Quantization, RQ), 그리고 이들의 하이브리드 변형들을 통합하는 단일 프레임워크를 제안합니다. 이를 통해 DocID 길이 및 코드북 크기와 같은 하이퍼파라미터의 영향뿐만 아니라 계층 구조 대 병렬성과 같은 핵심 DocID 속성을 체계적으로 연구할 수 있습니다. 둘째, 전체 모델 학습(training)의 오버헤드 없이 DocID 품질을 정량화하고 구조적 충실도를 평가하기 위한 일련의 학습 프리(training-free) 내재적 메트릭을 정의합니다. MS MARCO 300K 및 NQ320K에 대한 광범위한 실험을 통해, 이러한 구조적 속성들이 검색 효과에 어떻게 영향을 미치는지 분석합니다.
In this paper, we introduce position graphs, a graph-based reasoning framework based on the formalization of position spaces. This framework utilizes two strict partial orders, representing horizontal and vertical alignment and precedence, to model the relative positions of discrete tokens. Unlike general qualitative spatial calculi, position graphs are constrained by a chain condition and compatibility requirements that focus on rows and columns. We provide a comprehensive theoretical analysis of this representation, beginning with a characterization of graph consistency. Conditions to ensure the consistency of position graphs are established. Furthermore, we investigate the computational complexity of structural pattern discovery, modeled as the induced subgraph isomorphism problem. We demonstrate that this problem remains NP-complete even within the restricted class of position graphs. While initially motivated by document processing, this work focuses on the underlying mathematical properties and algebraic consistency of position-based constraints, providing a formal logical layer that is independent of specific data extraction techniques.