Executive Summary

주요 수치

삭제는 완벽하게 작동했고, 그런데도 검색 결과는 달라졌습니다.

출처: Mukkuzhi 외, arXiv:2608.20352

논문은 병원 이야기로 시작합니다. 환자 앨리스의 인슐린 처방 기록이 RAG 시스템 안에 들어 있고, 앨리스가 GDPR 제17조에 따라 삭제를 요구합니다. 운영자가 벡터 DB에 삭제 요청을 보내면 API는 밀리초 단위로 완료를 회신합니다. 관측 가능한 모든 지점에서 삭제는 끝난 것으로 보입니다. 그런데 같은 질의 창구를 쓰는 제3자는 앨리스의 기록을 직접 꺼내 보지 않고도 그 기록이 거기 있었다는 사실을 알아챌 수 있습니다. 기록을 조회하는 대신, 그 기록이 빠진 자리가 시스템이 대신 꺼내 오는 문서들을 어떻게 바꿔 놓았는지 지켜보는 방식입니다.

원인은 벡터 DB가 검색을 빠르게 하려고 쓰는 자료구조에 있습니다. 오늘날 대부분의 벡터 DB는 HNSW라는 근접 그래프 색인을 씁니다. 문서를 넣을 때마다 그 문서가 이웃으로 삼을 노드들이 정해지고, 그 연결이 이후 모든 질의의 탐색 경로가 됩니다. 삭제는 보통 그 노드에 지워졌다는 표시를 다는 일에 가깝습니다. 노드는 결과에서 빠지지만, 그 노드가 들어오면서 새로 그어진 이웃 연결과 그 연결이 밀어낸 옛 경로는 그대로 남습니다. 저자들은 이렇게 남은 자리를 지워진 노드가 남긴 구덩이라고 부릅니다.

논리적 삭제와 진짜 의미적 소거 사이의 이 어긋남에 저자들은 검증 격차라는 이름을 붙였습니다. 삭제 준수를 확인하는 감사가 식별자 수준에서 끝난다면, 그 감사는 통과하면서도 검색 위상에는 흔적이 남아 있는 상태가 성립합니다. 저자들은 이렇게 적었습니다. 이용자는 데이터가 사라졌다고 안내받았지만, 시스템은 여전히 그 데이터에 의해 모양이 잡혀 있습니다.

공격자로 상정된 쪽의 권한은 좁습니다. 저장소도 색인 파일도 모델 내부도 보지 못하고, 다른 이용자와 똑같은 질의 API만 씁니다. 목표도 문서 복원이 아닙니다. 삭제 전후로 같은 질의를 던져 돌아온 문서 목록과 점수, 본문 텍스트를 비교하는 것이 전부입니다. 이 설정이 중요한 이유는 관리형 클라우드 벡터 DB를 쓰는 조직 대부분이 정확히 그만큼만 볼 수 있기 때문입니다. 운영자가 볼 수 있는 창구와 외부인이 볼 수 있는 창구가 같습니다.

이런 주장을 증명하려면 비교 기준이 필요합니다. 이상적인 기준은 그 문서를 애초에 넣지 않았을 때의 색인입니다. 운영 중인 시스템에서는 관측할 수 없는 세계입니다. 그래서 저자들은 대신 같은 클러스터 안에서 대상이 아닌 이웃 문서를 지운 경우를 기준으로 세웠습니다. 질의도 그대로, 대상 문서의 정체도 그대로, 주변 이웃 구조도 그대로 둔 채 지우는 대상만 바꾼 것입니다. 이 기준을 넘는 만큼이 대상 문서 고유의 흔적이 됩니다.

대조군은 셋입니다. 아무것도 지우지 않고 색인 자체의 잡음을 재는 조건, 멀리 떨어진 클러스터의 무관한 문서를 지우는 조건, 그리고 같은 클러스터의 이웃을 지우는 엄격한 기준선입니다. 세 번째가 가장 까다로운 비교 대상인 이유는, 클러스터 전체가 흔들려서 생긴 변화와 특정 문서 때문에 생긴 변화를 갈라 주기 때문입니다. 이웃 하나를 지워도 그만큼은 움직인다면, 그 위로 올라간 부분만 대상 고유의 몫입니다.

코퍼스는 개인정보를 닮은 짧은 문단 500건입니다. 실제 환자 기록이 아니라 연구진이 생성한 합성 데이터이고, 이름 대신 고유 별칭 토큰과 진단 표지, 인구 속성 문구를 넣어 의료 저장소 문서의 구조를 흉내 냈습니다. 문서를 384차원 임베딩으로 바꾼 뒤 열 개 의미 클러스터로 나누고, 밀도가 높은 쪽과 중간, 성긴 쪽에서 여섯 건씩 골라 삭제 대상 18건을 정했습니다. 색인 구성 순서를 바꾸는 무작위 시드 세 개를 곱하면 비교쌍 54개가 나옵니다. 뒤에 나오는 수치는 모두 이 54쌍에서 얻은 값입니다.

측정에 들어가기 전에 저자들은 삭제 자체가 제대로 되는지부터 확인했습니다. 대상 18건을 다섯 개 백엔드와 시드 세 개에 걸쳐 돌린 270회 시행에서, 먼저 대상 문서가 유도 질의의 1순위로 뜨는지 확인하고, 표준 API로 지운 뒤, 같은 질의를 다시 던져 상위 40개 안에 그 식별자가 없는지 봤습니다. 클라우드 백엔드에는 비동기 반영을 감안한 대기 시간도 뒀습니다. 270회 전부가 100% 배제였습니다. 뒤에 나올 이동값을 구현 버그나 캐시 문제로 돌릴 수 없게 만드는 사전 작업입니다.

확인하는 방식 자체도 느슨하지 않았습니다. 저자들은 삭제 API가 돌려주는 HTTP 상태 코드를 믿지 않고 벤더가 보낸 응답 본문을 직접 파싱해 식별자가 빠졌는지 확인했습니다. 좌표를 비교할 때 생기는 부동소수점 편차를 줄이려고 기준 벡터를 별도 저장소에 고정해 두기도 했습니다. 논문이 세운 소거의 기준선도 그만큼 엄격합니다. 삭제된 기록이 조회되지 않는 것으로는 부족하고, 그 기록과 무관한 이용자가 던지는 질의에서 검색 정확도와 이웃 관련성, 반환되는 의미 맥락까지 그 문서를 애초에 넣지 않았을 때와 구별되지 않아야 소거가 확인된 것으로 봅니다.

측정 대상은 두 가지입니다. 하나는 무게중심 이동입니다. 질의 하나에 돌아온 상위 5개 문서의 임베딩을 평균 내면 그 질의가 짚은 의미의 좌표가 하나 나옵니다. 삭제 전과 후의 좌표 사이 거리를 잰 것이 무게중심 이동입니다. 다른 하나는 어휘 변화입니다. 돌아온 다섯 문서의 본문을 이어 붙여 토큰 집합을 만들고, 삭제 전후 두 집합이 얼마나 겹치지 않는지를 잽니다. 두 번째 값은 반환된 텍스트만 있으면 계산할 수 있어서 내부 접근 권한이 전혀 필요 없습니다.

한 문서가 빠지면 그 자리를 여섯 번째 문서가 메웁니다. 남은 넷은 그대로인데 새로 들어온 하나가 다섯 개의 평균을 끌어당깁니다.

ChromaDB에서 상위 5개를 기준으로 잰 결과가 아래 표입니다. 대상 문서를 지웠을 때 무게중심은 0.1522 움직였고 95% 신뢰구간은 0.1415에서 0.1629입니다. 같은 클러스터의 이웃을 지운 경우는 0.0412에 그쳤습니다. 멀리 있는 무관한 문서를 지운 경우와 아무것도 지우지 않은 경우는 둘 다 정확히 0입니다. 어휘 변화도 같은 순서를 그립니다. 대상 삭제는 0.285, 이웃 삭제는 0.095, 나머지 둘은 0입니다. 반환된 다섯 문서 중 넷이 그대로여도 본문 구성은 눈에 띄게 달라진다는 뜻입니다.

논문이 든 예시에서는 삭제 전 상위 문서들에서 모인 토큰 묶음에 인슐린과 복용량이 들어 있었는데, 대상 문서가 빠지고 대체 문서가 들어오자 그 자리를 혈당과 모니터링 같은 일반적인 임상 어휘가 메웠습니다. 두 묶음이 공유하는 토큰은 다섯 개, 합쳐서 아홉 개라 이 예시의 어휘 변화는 0.44입니다. 앞의 앨리스 이야기로 돌아가면, 인슐린 처방이라는 구체적인 단서가 사라진 자리에 평범한 당뇨 관련 문구가 들어서는 변화입니다. 좌표를 한 번도 들여다보지 않고 돌려받은 본문만 세어도 나오는 값이라는 점이 이 지표의 성격을 말해 줍니다.

중앙값보다 눈길이 가는 것은 일관성입니다. 54개 비교쌍 가운데 53쌍에서 대상 삭제가 같은 조건의 이웃 삭제를 넘어섰습니다. 양측 윌콕슨 부호순위검정 p값은 0.001 미만입니다. 밀도가 높은 클러스터든 성긴 클러스터든 순서는 뒤집히지 않았고, 검색 깊이를 1에서 20까지 바꿔 봐도 마찬가지였습니다. 깊이를 키우면 격차가 좁아지는데, 지워진 문서 한 건이 더 큰 평균에 기여하는 몫이 작아지니 예상되는 방향입니다. 같은 순서가 FAISS를 쓴 별도 재현에서도 나타났습니다. 다만 정량 특성화가 끝난 백엔드는 ChromaDB 하나입니다.

3.1질의 다섯 번이면 읽힌다

측정값이 크다는 것과 남이 알아챌 수 있다는 것은 다른 문제입니다. 저자들은 질의 예산을 줄여 가며 탐지 정확도를 쟀고, 대상과 관련된 질의 다섯 번에서 61.1%가 나왔습니다. 곡선은 그 지점 부근에서 이미 평평해집니다. 질의를 늘려도 크게 나아지지 않는다는 뜻이고, 반대로 말하면 대량 질의로 흔적을 남기지 않아도 되는 크기의 신호입니다.

다만 다섯 번은 탐지 단계의 질의 수입니다. 그전에 대상 문서의 의미 이웃에 정확히 떨어지는 질의를 만들어 내는 과정이 따로 있습니다. 저자들은 이웃 근처에 탐침 질의를 몇 개 던져 순위 신호를 모은 뒤, 후보 열 개를 조금씩 흔들어 대상의 순위를 끌어올리는 방향으로 최대 스무 번까지 질의를 다듬는 방식을 썼습니다. 여기 쓰이는 정보도 API가 돌려주는 순위와 결과뿐이라 내부 접근은 여전히 필요 없지만, 아무 질의나 다섯 번 던져서 되는 일은 아닙니다.

신호가 새는 통로가 이것만은 아닙니다. 나머지 둘은 저자들이 탐색적 관찰로 분류해 두었습니다. 질의를 유도하지 않고 순위 변화만 지켜보는 수동 관측은 500건 규모에서는 무시할 수준이었는데, 코퍼스가 5,000건으로 커지자 평균 0.18의 어휘 변화로 드러났습니다. 클라우드 백엔드를 묶어 보면 지워진 노드의 잔여 구조를 밟고 지나가는 탐색에서 응답 시간이 15.69밀리초 길어지는 차이도 관측됐습니다.

사라진 어휘 쪽에서는 조금 다른 성질이 나옵니다. 삭제 전 결과에는 있었는데 삭제 후 결과에서 빠진 토큰 집합을 모아 보니, 서로 다른 대상 문서끼리 그 집합이 겹치는 비율이 3% 미만이었습니다. 지워진 문서가 무슨 내용이었는지 복원하지 않고도, 지워진 것이 어느 문서였는지를 구별하는 지문 역할을 할 수 있다는 관찰입니다. 다만 이 지점에서 논문의 범위를 분명히 해 둘 필요가 있습니다. 여기서 확인된 것은 검색 맥락의 이동이지 본문 복원이나 벡터 복구가 아닙니다. 같은 연구실이 앞서 내놓은 Ghost Vectors는 디스크에 물리적으로 남은 임베딩을 다뤘고, 이번 연구는 그 임베딩이 진짜로 지워진 뒤에도 남는 위상의 문제를 다룹니다. 저장 계층과 검색 계층이라는 서로 다른 층위입니다.

운영자라면 곧바로 떠올릴 대응이 있습니다. 색인을 통째로 다시 만들거나, 지우기 전에 벡터에 잡음을 조금 섞거나, 벤더가 제공하는 정리 작업을 돌리거나, 지우기 전에 벡터를 아예 다른 값으로 덮어쓰는 방법입니다. 저자들은 이 넷을 차례로 시험했고, 넷 다 측정된 이동을 없애지 못했습니다.

가장 확실해 보이는 대응은 전체 재구축인데, 이것이 아무 효과가 없었습니다. 재구축은 살아남은 문서들에 대해 구조적으로 올바른 그래프를 만들어 냅니다. 그러나 대상 문서가 애초에 들어오지 않았다면 존재했을 배치를 복원하지는 못합니다. 문서가 한 번 삽입되면서 정해진 이웃 관계는 나중에 지워진 뒤에도 다른 노드들의 좌표와 연결에 이미 반영돼 있습니다. 벤더의 정리 작업이 소용없는 이유도 같습니다. 그것은 저장 공간을 정돈하는 위생 작업이지 소거 기제가 아니라고 저자들은 적었습니다.

섭동은 프라이버시와 검색 품질을 동시에 만족시키는 지점이 없었습니다. 잡음이 작으면 이동이 거의 그대로고, 잡음을 키우면 이동은 0.1089로 줄지만 검색 품질이 급격히 나빠집니다. 덮어쓴 뒤 삭제는 방향 자체가 반대로 나왔습니다. 덮어쓰기는 저장된 좌표를 바꿀 뿐 삽입 시점에 기록된 이웃 목록과 진입점을 지우지 못하고, 그 뒤에 이어진 삭제가 원래보다 더 큰 교란을 퍼뜨렸습니다.

시간이 해결해 주지도 않았습니다. 지워진 대상의 이웃 근처에 새 문서 2,500건을 넣어 색인이 자라게 두자, 흔적이 옅어지는 대신 짙어졌습니다. 새로 들어온 노드들이 이미 뒤틀린 경로를 그대로 물려받아 그 구덩이 주변으로 정렬됐기 때문입니다. 원래 이웃에 대한 검색 품질은 1.00에서 0.00까지 무너졌습니다. 삭제 권한을 악용하는 방향의 경계 사례도 함께 보고됐습니다. 한 클러스터에서 연결이 많은 허브 노드 여섯 개를 골라 지우면 그 주변을 질의하는 무고한 이용자들의 검색 품질이 74% 떨어져 0.26이 됐습니다.

네 가지 실패가 같은 원인을 가리킵니다. 근접 그래프 색인은 삽입 시점의 경로 선택을 간선 구조에 직접 새겨 넣고, 그 구조는 좌표나 식별자에 무슨 일이 생기든 남습니다. 특정 제품의 버그가 아니라 이 색인 방식의 성질입니다. 실제로 저자들은 2026년 초 평가 대상 벤더들에 이 내용을 알렸고, 벤더들은 관측된 동작이 현재 구현의 결함이 아니라 근접 그래프 색인에서 논리적 삭제가 올바르게 작동한 결과로 나타나는 의미 계층의 현상이라고 답했습니다. 클라우드를 쓰는 조직 입장에서 보면, 이 격차는 이용자 쪽 쓰기 작업으로는 닫을 수 없고 제공자 쪽 책임 영역에 있습니다.

저자들이 제시한 방향은 두 갈래이고 둘 다 향후 과제입니다. 색인 위상 소거는 삽입 시점의 이웃 목록과 진입점을 기록해 두었다가 삭제할 때 그 배치를 되돌려 놓습니다. 통제된 로컬 실험에서 이동을 0.1522에서 0.0012로 99.21% 줄였다고 보고했지만, 현재 클라우드 API의 블랙박스 경계 안에서는 구현할 수 없습니다. 나머지 하나는 색인 수명을 구간으로 나눠 구간마다 다른 키로 좌표를 암호화하고 삭제 시 그 키를 파기하는 방식입니다. 이쪽은 그래프의 뒤틀림을 고치지는 못하고, 남은 좌표의 내용을 읽을 수 없게 만듭니다.

GDPR 제17조나 HIPAA 같은 규정은 삭제 절차를 정하지만, 이행 확인은 대개 API 층위에서 끝납니다. 요청을 보냈고 응답이 왔고 조회해도 나오지 않는다는 세 가지가 확인되면 증빙이 됩니다. 이 논문이 보여 준 것은 그 세 가지가 모두 참인 상태에서도 검색 위상에는 측정 가능한 흔적이 남는다는 사실입니다. 저자들은 결론을 이렇게 맺었습니다. 검색 기반 시스템에서 삭제권의 질문은 어떤 기록을 숨길 수 있느냐가 아니라 그 기록이 검색에 미치는 영향을 제거할 수 있느냐입니다.

저자들은 이 결과를 기계 소거 연구와 나란히 놓고 견줍니다. 모델 가중치에서 특정 데이터를 지우는 연구는 대개 모델 상태에 직접 쓸 권한이 있다고 가정하고 출발합니다. 관리형 벡터 DB의 이용자에게는 그래프 위상에 손댈 권한이 없습니다. 그래서 인터페이스 층위의 검증은 삭제권을 좀 더 엄격하게 읽는 해석이 요구하는 것보다 약한 보증이라고 저자들은 적었습니다. 같은 문서를 두고도 지웠다는 말의 무게가 어디까지인지가 층위마다 달라지는 셈입니다.

실무로 옮기면 두 가지가 남습니다. 삭제 이행 증빙의 범위, 그리고 계약과 안내에 쓰는 말입니다. 지금의 증빙이 식별자 배제까지만 다룬다면, 그것으로 무엇을 보장했고 무엇은 보장하지 않았는지가 문서에 적혀 있어야 합니다. 서비스 제공자가 지운다고 할 때의 층위와 이용자가 지운다고 들을 때의 층위가 다르면, 기술적으로 완벽하게 이행한 삭제도 나중에 설명하기 어려워집니다.

논문의 한계도 함께 봐야 합니다. 정량 특성화가 끝난 백엔드는 ChromaDB 하나이고, FAISS는 같은 경향을 확인하는 수준입니다. Pinecone과 Weaviate, Milvus는 삭제 정확성 검증과 일부 완화책 실험에 쓰였을 뿐 이동값 정량화 대상이 아닙니다. 코퍼스는 500건과 5,000건 규모의 합성 데이터라 실제 운영 코퍼스의 크기나 다양성과는 다릅니다. 검색 맥락의 이동이 실제 LLM 답변을 얼마나 바꾸는지도 모델과 배포 설정에 따라 달라지는 별개 문제로 남겨 뒀습니다. 결정론적 설정의 소형 모델로 돌린 탐색적 평가에서는 지워진 자리에 들어온 맥락을 최종 답변에 그대로 받아들일 위험이 59.6%로 나왔고, 그렇게 만들어진 잘못된 복약 안내를 모델이 91.82%의 확신으로 내놓았습니다. 다만 저자들 스스로 이 값을 본 결과가 아닌 탐색적 관찰로 분류했습니다.

원문은 arXiv:2608.20352에서 볼 수 있습니다.

참고문헌

학술 논문

• 1.Mukkuzhi, A., Uwayisenga, N., Bizualem, Y., Kammerzell, J., & Chakraborttii, C. (2026). "Ghost Echoes: Semantic Erasure Failure in Retrieval-Backed Applications." arXiv:2608.20352.
• 2.Chakraborttii, C., Alvarado, J.G., Abdulofizova, S., & Dwivedi, S. (2026). "Ghost Vectors: Soft-Deleted Embeddings Remain Reconstructible in HNSW Vector Databases." arXiv:2606.18497.
• 3.Lewis, P. et al. (2020). "Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks." NeurIPS 2020.
• 4.Malkov, Y.A., & Yashunin, D.A. (2020). "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs." IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4).

공식 문서

• 5.European Union (2016). "Regulation (EU) 2016/679, Article 17 — Right to Erasure ('Right to be Forgotten')."