arXiv:2506.06557v3 cs.IR

Infinity Search: q-메트릭 공간 투영을 활용한 근사 벡터 검색

Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces

Antonio Pariente, Ignacio Hounie, Santiago Segarra, Alejandro Ribeiro

제출 2025-06-06

한국어 초록

초거리 공간(ultrametric space) 또는 무한대-메트릭 공간(infinity-metric space)은 삼각형의 모든 변이 다른 두 변 중 더 큰 변보다 크지 않다는 강한 삼각 부등식을 만족하는 비유사도 함수로 정의됩니다. 본 연구에서는 밴티지 포인트 트리(vantage point tree)를 사용한 초거리 공간에서의 검색이 트리의 깊이와 동일한 최악 조건 복잡도(worst-case complexity)를 가짐을 보입니다. 관심 대상이 되는 데이터셋은 일반적으로 초거리 공간을 따르지 않으므로, 최근접 이웃(nearest neighbors)을 보존하면서 임의의 비유사도 함수를 초거리 공간으로 변환하는 투영 연산자(projection operator)를 도입합니다. 나아가 쿼리 포인트와 데이터셋 내 포인트 간의 초거리 거리를 효율적으로 계산하기 위해 이 투영 연산자의 근사를 학습합니다. 이어서 삼각형의 변을 $q$제곱한 값이 다른 두 변의 $q$제곱의 합보다 작은 $q$-메트릭 공간에서의 투영을 고려하는 보다 일반적인 문제를 해결합니다. 투영된 $q$-메트릭 거리의 학습된 근사를 사용하면 검색 파이프라인이 근사(approximate) 검색으로 변환된다는 점에 유의해야 합니다. 실험을 통해 $q$ 값이 증가할수록 검색 속도는 빨라지지만 재현율은 낮아짐을 보입니다. 전반적으로 $q$-메트릭 및 무한대-메트릭 공간에서의 검색은 기존 검색 방식과 비교해 경쟁력이 있습니다.

원문 초록

An ultrametric space or infinity-metric space is defined by a dissimilarity function that satisfies a strong triangle inequality in which every side of a triangle is not larger than the larger of the other two. We show that search in ultrametric spaces with a vantage point tree has worst-case complexity equal to the depth of the tree. Since datasets of interest are not ultrametric in general, we employ a projection operator that transforms an arbitrary dissimilarity function into an ultrametric space while preserving nearest neighbors. We further learn an approximation of this projection operator to efficiently compute ultrametric distances between query points and points in the dataset. We proceed to solve a more general problem in which we consider projections in $q$-metric spaces -- in which triangle sides raised to the power of $q$ are smaller than the sum of the $q$-powers of the other two. Notice that the use of learned approximations of projected $q$-metric distances renders the search pipeline approximate. We show in experiments that increasing values of $q$ result in faster search but lower recall. Overall, search in q-metric and infinity metric spaces is competitive with existing search methods.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2506.06557v3

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.28290v1cs.CL공통 태그 Retrieval, Metric Learning, Information Retrieval

기하학보다 계산: 의미 동일성은 임베딩에 담겨 전달되는 것이 아니라 계산된다

Computation Over Geometry: Meaning Identity Is Computed, Not Shipped in the Embeddings

의미 동일성(표현이 바뀐 뒤에도 두 문장이 같은 내용을 말하는지 여부)은 검색과 RAG에서 독립적으로 인코딩된 문장 벡터의 기하학적 사실로 취급된다. 본 논문은 고정된(frozen) 기성 인코더와 언어 모델에서는 그렇지 않음을 보인다. 동일성은 두 문장이 하나의 순전파를 공유할 때 계산되며, 해당 시스템들이 제공하는 임베딩 기하학의 속성이 아니다. 중첩(overlap)을 맞춘 PAWS-X에서 목적 특화 인코더(BGE, E5, GTE, MiniLM, E5-Mistral-7B)는 영어 confirm AUC가 0.55-0.65에 그친다(dense 최고치 0.70). Llama 3, Mistral, Qwen의 독립적으로 인코딩된 마지막 토큰 상태도 더 나은 성능을 보이지 못하며, 두 벡터의 후기 융합(late fusion)은 우연 수준에 가깝다. 반면 동일한 프로브를 결합된 순전파에 적용하면 1.5B에서 32B까지 0.90-0.96에 도달하고, 짝을 섞으면(partner shuffle) 성능이 붕괴하며, 중간 깊이에서 나타나고, 3B 무렵 0.94 부근에서 포화되며, GPT-2 XL에서는 더 약하게(0.76) 나타난다. 이러한 격차는 Llama 계열을 넘어 다른 인과적 언어 모델, 양방향 인코더(DeBERTa, RoBERTa), 인코더-디코더(Flan-T5, T5, BART)에서도 유지된다. 고정된 독립 인코딩 위의 고정형 또는 선형 리더는 동일성을 끝내 복원하지 못하며, 비선형 쌍(pair) 리더는 전체 49k 쌍의 PAWS 학습 분할에서만 일부를 복원한다(0.68-0.87). 기성 리랭커는 결과가 갈린다. BGE-reranker-large는 0.94에 도달하는 반면, MS-MARCO와 Jina는 0.55-0.64에 머문다. 독립적으로 학습된 모델 계열들이 동일한 관계를 계산하며, 1.5B 결합 리더는 레이블 없는 교사(teacher) 점수로부터 이를 지식 증류할 수 있지만, 교사 자신의 독립 벡터에 대한 어떤 선형 함수로도 이는 불가능하다. 바이 인코더(bi-encoder)를 PAWS에 맞게 파인튜닝할 수는 있으나(0.87-0.93), 전이 성능과 STS-B 성능이 저하된다. 코사인 유사도는 표현의 이웃 관계를 비교할 뿐이며, 동일성은 어느 쪽 문장 벡터의 속성도 아닌, 저렴하게 계산되는 연산자이다.

arXiv:2609.23307v1cs.IR공통 태그 Retrieval, Metric Learning, Information Retrieval

의미 기반 후보자-직무 매칭: 하이브리드 검색에서 밀집 임베딩 모델의 비교 평가

Semantic Candidate-Job Matching: A Comparative Evaluation of Dense Embedding Models in Hybrid Retrieval

본 논문은 대량 채용 워크플로에서 의미적 후보자-직무 매칭을 위한 밀집 임베딩 모델에 대한 비교 평가를 제시한다. 유입되는 직무 기술서는 LLM 기반 파싱을 통해 구조화된 영어 검색 텍스트와 언어별 키워드로 변환되며, 후보자 프로필은 의미적으로 강화된 이력서 표현으로 색인된다. 벡터 유사도와 전문(full-text) 관련성을 상호 순위 융합(RRF)으로 결합하는 통합 하이브리드 검색 파이프라인 안에서 EmbeddingGemma(base)와 Cached Multiple Negatives Ranking Loss(MNRL)로 미세조정한 EmbeddingGemma를 비교 평가하고, 배포된 직무-후보자 매칭 채점 파이프라인으로 점수를 매긴 배치 비교 평가 데이터셋에서 둘 다 MPNet 모델과 벤치마크한다. 또한 모델 개발 과정에서 검토한 대조(contrastive) 미세조정 목표의 더 넓은 집합(AnglE/CoSENT 스타일 정제 포함)을 수학적으로 상세히 기록하고, 선호 구성으로 Cached-MNRL-only 적응만 유지한 경험적 근거를 제시한다. 재현 가능한 모델 선택을 지원하기 위해 동일한 하이브리드 검색 프로토콜 하에서 표준 정보 검색 지표(재현율@K, mean reciprocal rank, nDCG)를 포함하는 더 넓은 평가 프레임워크를 정의하되, 본 논문에서 보고하는 평가에 실제로 사용한 지표는 미세조정 수렴 진단과 배포된 AI-Match 점수 및 독립적인 LLM-as-a-Judge 관련성 점수를 활용한 배치 비교 평가이며, 전체 프레임워크를 측정한 것처럼 암시하지 않고 이 범위를 명시적으로 밝힌다. 본 논문은 범용 임베딩 벤치마크와 기업 환경의 직무-후보자 매칭 제약 사이의 간극을 다루며, 현실적인 직무-후보자 검색 조건에서 임베딩 전략을 비교할 수 있는 구조화된 기반을 제공한다.

arXiv:2609.24152v1cs.IR공통 태그 Retrieval, Metric Learning, Information Retrieval

대규모 이커머스 시각 검색을 위한 등급별 관련성 합성 멀티모달 검색

Graded-Relevance Composed Multimodal Retrieval for E-commerce Visual Search at Scale

대규모 이커머스 카탈로그에서의 시각 검색은 업로드된 이미지와 유사한 상품을 요구하는 "유사성(similarity)" 쿼리와, 원하는 수정(예: 색상 변경, 스타일 교체)을 설명하는 텍스트와 이미지로 이루어진 "수식어(modifier)" 쿼리를 모두 처리해야 한다. 후자는 합성 이미지 검색(composed image retrieval, CIR)으로 알려진 설정이다. 그러나 기존 CIR 방법은 관련성을 이진으로 취급하고 단일 positive target을 갖는 triplet으로 학습하는데, 이는 실제 카탈로그에서 많은 후보가 사용자 쿼리를 부분적으로 만족하고 그 부분 일치 스펙트럼에 걸친 순위화가 고객 경험을 좌우하는 현실에 잘 맞지 않는다. 우리는 등급별 관련성(graded relevance) 위에서 CIR 검색기를 학습하는 방법론을 제안하며, 이는 (i) VLM을 이용해 학습 데이터를 큐레이션하고, 객체 검출과 수식어 합성으로 쿼리를 생성하며 수동 주석 없이 4단계 관련성 라벨을 만드는 것, (ii) 학습 중인 검색기로부터 hard negative를 마이닝하여 학습 집합을 확장하는 반복적 관련성 피드백 루프, (iii) 등급 라벨을 이진 분할로 축소하지 않고 직접 학습하기 위한 계층 인식(hierarchy-aware) 각도 목적 함수로 구성된다. 이 방법론을 GradCIR라 부르며, 원시 Walmart 카탈로그 데이터에서 큐레이션한 350만 개의 등급별 쌍으로 학습한 PaliGemma2 bi-encoder에 구현했다. 등급 대 이진에 대한 통제된 ablation이 감독 세분성을 분리하여 NDCG@10에서 4.9%-5.9% 향상을 보여준다. 동일한 레시피를 다른 멀티모달 인코더에 적용하면 early-fusion 백본에서 NDCG@10이 최대 8.5%까지 향상된다. 공개 FashionIQ 벤치마크에서 GradCIR(PaliGemma2에 적용, 파인튜닝)은 평균 재현율 0.6703에 도달하여, 우리가 비교한 동료 심사 최강 감독 기준선보다 약간 앞서며, 발표된 모든 CLIP-L급 제로샷 CIR 방법과 동등하거나 그 이상이다. 이 시스템은 Walmart 프로덕션에 배포되어 라이브 시각 검색 사용자 트래픽을 처리하고 있다.

arXiv:2607.24567v1cs.AI공통 태그 Retrieval, Metric Learning, Information Retrieval

DSCH-Loss: 심층 의미 해싱을 위한 동적 의미 채널 목적 함수

DSCH-Loss: A Dynamic Semantic Channel Objective for Deep Semantic Hashing

고차원 데이터 공간에서 효율적인 근사 최근접 이웃 검색을 가능하게 하는 짧은 이진 해시 코드를 생성하는 의미 해싱 방법은 최근 몇 년간 광범위한 관심을 받아왔다. 심층 학습 기반 방법은 수동 특징 공학에 의존하는 전통적 접근법보다 더 나은 의미 포착 능력을 제공한다. 또한 이들은 다양한 데이터 모달리티에 걸친 의미 해싱에 대한 데이터 기반 접근을 가능하게 하며, 공유 해밍 공간 내에서 고품질 교차 모달 해시 코드를 생성한다. 이전 연구는 이 해밍 공간의 특성을 조사하고, 고정된 폭과 레이블 유사도에서 유도된 해밍 거리를 갖는 미리 정의된 소위 의미 채널에 기반한 손실 함수를 도입했다. 그러나 이러한 공식화는 손실 경관에 불연속성을 도입하기도 하여 최적화를 복잡하게 만들었다. 이러한 관찰에 기반하여, 우리는 손실 경관의 불연속성을 피하기 위해 동적으로 크기와 위치가 조정되는 의미 채널을 사용하는 새로 설계된 손실 함수인 동적 의미 채널 해싱(DSCH)을 제안한다. 또한, 해시 코드 거리의 이산성에서 발생하는 샘플 검색 순서의 모호성을 해결하기 때문에 tie-aware 평균 정밀도(mAP)를 평가 지표로 사용할 것을 권장한다. 마지막으로, 두 개의 인기 있는 데이터셋에서 수행되고 두 가지 서로 다른 모델 아키텍처를 포함하는 다양한 실험 설정은 DSCH 목적 함수를 사용한 학습이 다른 최신 손실 함수를 사용한 학습보다 우수함을 강력히 뒷받침한다. 총 40개의 교차 모달 및 모달 내 검색 작업 중 35개에서, DSCH로 학습된 모델은 테스트된 네 가지 해시 코드 길이 전반에 걸쳐 유의미하게 더 높은 tie-aware mAP 점수를 달성하며, 모델 아키텍처와 사용된 데이터셋 전반에 걸쳐 설득력 있는 결과를 보여준다. mAP 점수 향상은 일관되며, 각각의 2위 대비 최대 1.75퍼센트포인트에 이른다.

arXiv:2610.13889v1cs.AI공통 태그 Retrieval, Information Retrieval

RATED: 실행 역학을 통한 신뢰성 인식 AI 에이전트 도구 검색

RATED: Reliability-Aware AI Agent Tool Retrieval via Execution Dynamics

AI 에이전트(agent)의 외부 도구 의존도가 높아짐에 따라, 신뢰할 수 있는 동작을 위해서는 정확한 도구 검색이 필수적입니다. 기존 방식들은 의미적 관련성을 최적화하지만 실행 중 도구의 가용성은 대체로 무시합니다. 이러한 한계를 해결하기 위해, 본 논문에서는 강건한 의미적 매칭과 동적 신뢰성 적응을 결합한 검색 프레임워크인 RATED(Reliability-Aware Tool Retrieval via Execution Dynamics)를 제안합니다. RATED는 의미적 매칭을 위해 대조 미세조정(contrastive fine-tuning)이 적용된 고정된(frozen) 듀얼 인코더를 사용하며, 실시간 실행 피드백을 기반으로 후보군을 재순위화하는 경량 맥락적 밴딧(contextual bandit) 모듈을 사용합니다. 이러한 설계를 통해 모델의 값비싼 재학습 없이도 런타임 도구 실패에 신속하게 적응할 수 있습니다. 또한 오프라인 검색 및 동적 신뢰성 평가를 위해 5,172개의 실제 도구와 210,000개 이상의 쿼리-도구 쌍으로 구성된 벤치마크인 EcoAgent를 소개합니다. 실험 결과에 따르면, RATED는 실제 쿼리에서 ToolLLM API 검색기 대비 52.2%의 상대적 MRR 향상을 달성하고, 30%의 실패율을 보이는 심각한 API 장애 시나리오에서 오류 선택률을 86.2%에서 2.9%로 낮추는 동시에 인코딩 전용 추론(inference) 대비 1ms 미만의 미미한 지연 시간 오버헤드만을 발생시킵니다. 코드와 데이터셋은 https://github.com/Elliotes/EcoAgent 에서 확인할 수 있습니다.

arXiv:2609.32123v2cs.AI공통 태그 Retrieval, Information Retrieval

READ-Bench: 시계열 진단을 위한 과거 사례 검색 벤치마크

READ-Bench: Benchmarking Historical Instance Retrieval for Time-Series Diagnosis

시계열 진단 시스템은 관련 과거 사례를 검색하는 방식에 거의 의존하지 않으며, 이를 활용하더라도 검색 성능은 다운스트림 예측을 통해서만 간접적으로 평가됩니다. 본 연구에서는 다변량 시계열을 중심으로 12개의 진단 데이터셋에 걸쳐 과거 사례 검색을 평가하는 벤치마크인 READ-Bench를 소개합니다. READ-Bench는 신호의 형태 대신 공유된 고장 또는 이벤트 유형을 기준으로 관련성을 정의하므로, 동일한 고장이라도 시각적으로 다른 파형은 관련 사례로 간주되는 반면, 서로 다른 고장의 유사하게 보이는 파형은 관련 사례로 간주되지 않습니다. 검색을 기본 검색기(base retriever)와 리랭커(reranker)의 결합으로 구성하여, 유의성 검정과 함께 지도 수준, 데이터 오염(pollution), 코퍼스 규모를 다양화하는 단일 프로토콜 하에서 고전적 거리 지표, 기호 기반 검색기, 자기지도학습 및 파운데이션 모델 임베더와 이들의 융합, 그리고 라벨 인지형 및 언어 모델 리랭커를 평가합니다. 공통의 채널 독립적 인터페이스에서 사전학습된 표현은 검색 단계 단독으로는 강력한 고전적 및 기호 기반 베이스라인 대비 통계적으로 유의미한 이점을 보이지 않았습니다. 결정적인 요인은 리랭킹 단계에서 해결된 사례에 대한 소량의 지도 학습, 즉 임베딩 공간에서 소수의 이웃 라벨을 전파하는 가우시안 프로세스(Gaussian-process) 리랭커의 활용이었으며, 이는 더 정교한 표현이나 언어 모델 추론보다 훨씬 더 큰 도움이 되었고 데이터 오염 및 전체 코퍼스 규모에서도 유효했습니다. 이러한 결과를 바탕으로, 본 연구는 상호 순위 융합(reciprocal-rank fusion)을 통해 정상 잔차 점수 기반 임베더와 동적 시간 워핑(dynamic time warping) 방식을 결합한 후 가우시안 프로세스 리랭커로 재순위화하여, 12개 데이터셋 전체에서 자체 검색 단계 대비 NDCG@10을 향상시켰으며(리랭킹으로 +0.11 향상), 가장 강력한 단일 기본 검색기 대비 +0.16의 향상을 달성했습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.