arXiv:2606.27917v1 cs.LG

문맥적 밴딧을 위한 그래프 차원 축소: 근사 평활성과 노이즈 고유공간 하의 구조 특화 후회 한계

Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces

Joyanta Jyoti Mondal, Ibne Farabi Shihab, Anuj Sharma

제출 2026-06-26

한국어 초록

그래프 구조 arm을 갖는 문맥적 밴딧(contextual bandits)은 추천, 인용 검색, 소셜 광고 등에서 등장하며, 그래프상에서 연결된 arm들은 보상(reward) 신호를 공유하는 경향이 있다. 표준 차원 축소(dimensionality reduction)는 이러한 구조를 무시하여 탐험(exploration) 비용을 $d/k$배 만큼 증가시킨다. 우리는 arm 특징을 그래프의 저주파 스펙트럴 부분공간(spectral subspace)에 투영하고, 그 결과 얻은 $k$차원 공간에서 선형 UCB를 실행하는 GraphDR-LinUCB를 제안한다. 스펙트럴 투영(spectral projection) 기반 문맥적 밴딧에 대해 최초의 $\wtO(k\sqrt{T})$ 후회(regret) 한계를 증명하며, 차원 의존성을 $d$에서 $k$로 줄인다; 섭동(perturbation) 논증으로 이를 노이즈 그래프까지 확장하고, 보상 평활성(reward smoothness) 불일치와 그래프 추정 오류에 대한 명시적 페널티를 제시한다. 핵심 이론적 발견은 고주파 보상 성분이 최악의 $T$에 선형인 페널티를 반드시 받을 필요는 없다는 것이다: 그 실제 비용은 총 에너지(total energy)가 아니라 실제 플레이 경로(played path)를 따른 실현된 영향(realized impact)에 달려 있다. 부분공간($\Gamma_k$) 간의 단순한 스펙트럴 비교는 주어진 데이터셋(dataset)에서 어떤 축소기(reducer)가 이길지 예측하며, 임계값을 학습하지 않고도 6개 실제 데이터셋 중 5개의 결과를 올바르게 맞춘다. 합성 벤치마크(benchmark)와 6개 실제 데이터셋(MovieLens, Amazon, LastFM, ogbn-arxiv, MIND)에 걸쳐, GraphDR-LinUCB는 전체 차원 LinUCB 대비 누적 후회(cumulative regret)를 $15\times$ 줄이고, 6개 중 5개에서 경쟁 그래프 인지(graph-aware) 방법을 능가한다; 유일한 실패는 바로 그래프의 스펙트럴 부분공간이 보상과 어긋난 경우이다.

원문 초록

Contextual bandits with graph-structured arms arise in recommendation, citation retrieval, and social advertising, where arms connected on a graph tend to share reward signal. Standard dimensionality reduction ignores this structure, inflating exploration cost by a factor of $d/k$. We propose GraphDR-LinUCB, which projects arm features onto the graph's low-frequency spectral subspace and runs linear UCB in the resulting $k$-dimensional space. We prove the first $\wtO(k\sqrt{T})$ regret bound for spectral-projection-based contextual bandits, reducing dimension dependence from $d$ to $k$; a perturbation argument extends this to noisy graphs, with an explicit penalty for reward-smoothness mismatch and graph-estimation error. Our central theoretical finding is that the high-frequency reward component need not incur a worst-case linear-in-$T$ penalty: its actual cost depends on its realized impact along the played path, not on its total energy. A simple spectral comparison between subspaces ($Γ_k$) predicts which reducer wins on a given dataset, correctly calling five of six real-dataset outcomes without any fitted threshold. Across a synthetic benchmark and six real datasets (MovieLens, Amazon, LastFM, ogbn-arxiv, MIND), GraphDR-LinUCB reduces cumulative regret by $15\times$ over full-dimensional LinUCB and outperforms competing graph-aware methods on five of six; the single failure is precisely where the graph's spectral subspace is misaligned with the reward.

제출 이력

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

  1. arXiv:2606.27917v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2609.26218v1cs.IR공통 태그 Retrieval, Recommendation Systems, Graph Learning

학술 출판 네트워크에 대한 시맨틱 접근법: OpenAlex 데이터 기반 문서 벡터 표현 및 하이브리드 구조적-시맨틱 융합

A Semantic Approach to the Academic Publishing Network: Document Vector Representations and Hybrid Structural-Semantic Fusion over OpenAlex Data

학술 출판 네트워크에 대한 구조적 그래프 분석은 엔티티 간의 위상학적 관계를 포착하지만 연구 저작물의 내용은 파악하지 못합니다. 본 연구는 기존 구조적 접근법을 바탕으로 시맨틱 층(layer)과 매개변수화된 구조적-시맨틱 융합을 통해 이를 보완합니다. 우리는 과학 문헌을 인용 정보 기반 벡터 임베딩(SPECTER2)으로 표현하고, 고유한 OpenAlex ID를 키로 하여 임베디드 벡터 데이터베이스에 저장함으로써 그래프 층과 직접 연결되도록 합니다. 또한 시맨틱 유사도(임베딩의 코사인 유사도)와 구조적 유사도(서지 결합)를 특정 태스크에 따라 값이 선택되는 조정 가능한 가중치(weight) 알파(alpha)로 결합하는 모듈형 후기 융합 함수를 정의합니다. VSB - Technical University of Ostrava 코퍼스를 대상으로 두 가지를 보여줍니다. 즉, 인용 정보 기반 임베딩은 TF-IDF 기준선(baseline)보다 전문가가 구축한 OpenAlex 주제 분류 체계와 더 잘 일치하며, 추천 활용 사례에서는 가용 데이터에 따라 구조적, 시맨틱 및 결합된 신호가 서로 다른 체계에서 정보를 전달한다는 점입니다. 여기서 하이브리드 융합은 보편적으로 더 우수한 방법이라기보다는 태스크에 맞추어 상호 보완적인 신호를 제어하기 위한 명시적 메커니즘입니다. 우리는 재현 가능한 워크플로와 함께 전체 접근법을 apnet 라이브러리의 오픈 소스 확장으로 공개합니다.

arXiv:2610.13889v1cs.AI공통 태그 Retrieval, Multi-Armed Bandits

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:2610.03651v1cs.AI공통 태그 Dimensionality Reduction, Retrieval

MRVQ: 차원 및 비트 전송률에 탄력적인 벡터 검색을 위한 단일 상주 인덱스

MRVQ: One Resident Index for Dimension- and Rate-Elastic Vector Search

밀집 검색(dense-retrieval) 서비스는 지연 시간, 품질 및 메모리 예산 변화에 따라 임베딩 접두 차원과 인덱스 비트 전송률(bit rate) 사이를 전환해야 합니다. 각 전송률마다 양자화기(quantizer)를 개별적으로 튜닝하면 최상의 품질을 얻을 수 있지만, 검색 계층이 여러 코드 스트림과 양자화기 상태를 동시에 유지해야 합니다. 본 논문에서는 동결된 임베딩을 위한 사후 잔차 양자화기인 마트료시카 잔차 벡터 양자화(MRVQ, Matryoshka Residual Vector Quantization)를 제안합니다. MRVQ의 최대 전송률 코드는 두 가지 방식으로 잘라낼 수 있습니다. 잔차 단계를 줄이면 전송률이 낮아지고, 임베딩 좌표를 줄이면 차원이 낮아집니다. 따라서 단 하나의 상주 아티팩트만으로 평가 대상인 모든 (차원, 전송률) 쌍을 처리할 수 있습니다. FiQA 및 NFCorpus, 4가지 임베딩 계열, {4, 8, 16}바이트 코드 전반에 걸쳐 MRVQ는 평가된 설계 중 가장 적은 RAM을 사용합니다. 이는 개별적으로 학습된 3개의 QINCo2 인덱스보다 17.8~22.0배 적은 메모리를 사용하며, 간소화된 공유 모델(shared-model) 스틸맨보다 1.89~2.02배 적은 메모리를 사용합니다. 이러한 메모리 절감이 공짜는 아닙니다. 전송률별 QINCo2는 FiQA에서 nDCG@10 기준 0.026~0.107 더 우수합니다. 그러나 MRVQ는 동일한 코드 크기에서 PQ, OPQ 및 AdANNS-OPQ를 능가합니다. 또한 중앙값 기준 420배 더 빠르게 피팅되면서 RaBitQ 및 그 확장 모델과 비슷한 품질을 달성하는 낮은 구축 비용의 PCA 스칼라 설계도 평가합니다. 마지막으로 두 가지 부정적 결과(negative results)를 보고합니다. QINCo2는 높은 전송률에서 학습될 때 붕괴되며, 랭킹 경계 가설은 사전에 지정된 수락 기준을 충족하지 못합니다. 따라서 MRVQ는 탄력적 검색을 위한 저메모리 운영 지점이지 만능 품질 승자는 아닙니다.

arXiv:2609.27155v1cs.CR공통 태그 Retrieval, Recommendation Systems

좋아요 함정: 유사도 기반 추천 시스템에서 에이전트를 겨냥한 다단계 포이즈닝 공격

The Like Trap: Multi-Stage Poisoning against Agents in Similarity-based Recommendation Systems

대규모 언어 모델(LLM) 및 LLM 기반 에이전트(agent)의 최근 발전과 함께, 이러한 에이전트들은 점차 자율성을 갖추며 인터넷상에서 사용자를 대신해 행동할 수 있는 더 넓은 접근 권한을 얻고 있다. 그러나 소셜 미디어 플랫폼에 배포된 자동화된 에이전트(예: 사용자의 개인 계정 관리)의 취약성은 아직 충분히 연구되지 않았다. 에이전트 포이즈닝에 관한 기존 연구들은 일반적으로 공격자가 에이전트에게 오염된 콘텐츠를 직접 노출할 수 있다고 가정한다. 이러한 공격은 직접적이고 효과적이지만, 감지 및 완화가 더 쉽다. 소셜 미디어 플랫폼 맥락에서는 추천 시스템 자체가 보다 은밀한 방식으로 이러한 콘텐츠를 에이전트에게 노출할 수 있는지 여부가 여전히 미해결 과제로 남아 있다. 이론적 분석을 통해 본 연구는 OASIS에서 사용되는 좋아요 점수(like-score) 메커니즘이 악용될 수 있음을 보이고, 다단계로 이루어진 오염된 게시물 연쇄가 에이전트의 피드를 유도할 수 있는 조건을 규명한다. 이러한 통찰을 바탕으로, 우리는 사실적인 오염 게시물을 제작하는 알고리즘을 추가로 개발한다. 실험을 통해 이론적 발견을 뒷받침하고 제안된 알고리즘의 효과를 입증한다. 특히, 좋아요 점수 피드백 루프를 악용함으로써 이 공격은 오염된 게시물의 사용자-게시물 유사도가 검색 임계값 미만으로 떨어지는 경우에도 추천 시스템이 해당 게시물을 선택하도록 만든다.

arXiv:2609.27953v1cs.IR공통 태그 Retrieval, Recommendation Systems

LLM 추천 리랭킹의 재현율 한계

The Recall Ceiling of LLM Recommendation Reranking

일부 LLM 기반 추천 리랭커는 정답 아이템이 평가 대상 집합에 반드시 존재하도록 보장하는 오라클 프로토콜로 평가된다. 이는 정답 아이템을 후보 목록에 주입하거나 샘플링된 네거티브와 비교하여 점수를 매기는 방식으로 이루어진다. 세 개의 주요 Amazon 데이터셋에서 이 프로토콜이 현실적인 NDCG@10을 92~95% 과대평가함을 보인다. 그 원인은 재현율 한계(recall ceiling)에 있다. 세 개 도메인의 여덟 개 데이터셋에 걸쳐, 현실적인 검색(retrieval)은 $K=100$에서 관련 아이템의 2~19%만을 포착하며, 이는 모든 폐쇄 후보(closed-candidate) 리랭커의 top-$k$ NDCG에 결정론적 상한을 부과한다. 리브-원-아웃(leave-one-out) 평가에서는 $\mathbb{E}[\mathrm{NDCG}@k] \leq \mathrm{Recall}@|W_\pi|$가 성립하며, 여기서 $W_\pi$는 리랭커의 후보 윈도우이다. 현실적인 검색 조건에서는 우리의 주요 Amazon 데이터셋에서 테스트한 어떤 최적화 전략도 협업 필터링(CF) 기준선을 유의미하게 개선하지 못한다. 이러한 전략에는 프롬프트 엔지니어링, 168배 매개변수 범위에 걸친 모델 스케일링, 순차 모델, 지도 학습 기반 신경망 리랭커, LoRA 미세조정, 하이브리드 검색, 점수 인지(score-aware) 프롬프팅, LLM+CF 융합이 포함된다. 텍스트 인지(text-aware) 검색은 한 데이터셋에서 재현율을 높이지만 종단 간(end-to-end) NDCG를 개선하지는 못하며, 상위 단계의 CF 점수를 제공하면 주로 LLM이 CF의 순서를 그대로 재현하게 된다. 따라서 우리는 재현율 인지 평가 프로토콜(Recall-Aware Evaluation Protocol, RAEP)을 제안한다. 먼저 검색 재현율 구간(regime)을 분류한 뒤, 상한이 의미 있는 차별화를 허용하는 경우에 한해 리랭킹을 평가하는 것이다. 여기서 측정된 낮은 재현율 구간에서는 리랭커의 정교함을 높이는 것보다 검색을 개선하는 것이 더 중요하다. 다만 이러한 순서가 더 높은 재현율, 더 풍부한 특징, 또는 온라인 피드백을 갖춘 프로덕션 시스템에서도 반드시 성립하는 것은 아니다.

arXiv:2609.28003v1cs.LG공통 태그 Retrieval, Graph Learning

실패로부터의 학습: 소형 언어 모델 도구 사용 에이전트를 위한 이종 그래프 메모리

Learning from Failures: Heterogeneous Graph Memory for Small Language Model Tool-Using Agents

중소형 언어 모델(language model)은 도구 사용 에이전트(agent)를 위한 비용 효율적인 실행자 역할을 하여 로컬 및 대규모 배포에 매력적인 선택지입니다. 그러나 장기적(long-horizon)이고 상태를 유지하는(stateful) 환경에서 이러한 모델(model)들은 필수적인 관측 누락, 조기 쓰기 수행, 실패한 호출 반복, 행동 전제 조건 위반과 같은 구조적 오류를 자주 범합니다. 이러한 오류는 잘못된 상태 업데이트, 정책 위반, 그리고 많은 비용이 들거나 되돌릴 수 없는 결과로 이어질 수 있어, 신뢰할 수 있는 도구 실행이 핵심적인 배포 과제가 됩니다. 기존의 미세조정(fine-tuning) 접근 방식은 상당한 양의 데이터와 연산을 필요로 하며, 평면적 메모리(flat memory)는 인과적 맥락이나 안전성(safety) 조건을 보존하지 못한 채 실패한 행동을 검색할 수 있습니다. 본 논문에서는 과거의 성공과 실패를 도구 사용 에이전트를 위한 구조화된 외부 경험으로 변환하는, 경험 구조화 이종 그래프 기반 실패 인지 검색 프레임워크인 FRESH(Failure-aware Retrieval framework over Experience-Structured Heterogeneous graphs)를 제안합니다. FRESH는 태스크, 행동, 오류, 복구, 실행 조건 간의 의존성을 명시적으로 모델링함으로써, 동결된(frozen) 언어 모델이 신뢰할 수 있는 전략을 재사용하고, 반복되는 실패를 방지하며, 상태 기반 도구 상호작용에서 더 안전한 결정을 내릴 수 있도록 돕습니다. 여러 오픈소스 모델을 사용해 $\tau$-Bench 및 AppWorld에서 수행한 실험에 따르면, FRESH는 메모리가 없는 에이전트 및 대표적인 메모리 기반 베이스라인 대비 태스크 성공률과 도구 사용 신뢰성을 일관되게 향상시킵니다.

토론

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