arXiv:2610.02440v1 cs.LG

가산적 양자화 표현을 통한 밴딧

Bandits via Additive Quantized Representations

Ami Tavory, Noam Touitou, Tal Sarig, Frank Cheng, Ido Guy

제출 2026-10-01

저자 비고

arXiv Comments

40 pages, 16 figures, 12 tables. Accepted at NeurIPS 2026

한국어 초록

맥락적 밴딧(contextual bandit)은 비선형 보상(reward) 모델링과 온라인 효율성 사이의 균형을 필요로 한다. 트리 앙상블과 신경망 기반 방법은 비선형성을 포착할 수 있지만 주기적인 재학습과 대규모 리플레이 버퍼를 필요로 한다. 선형 모델은 관측값마다 O(1) 메모리로 효율적으로 업데이트할 수 있지만, 근본적으로 선형 보상 구조에만 제한된다. 우리는 이러한 간극을 메우기 위한 표현 층(representation layer)으로 잔차 양자화(Residual Quantization, RQ)를 제안한다. 오프라인으로 학습된 RQ 코드북(codebook)은 연속적인 맥락(context)을 여러 수준에 걸친 이산적 중심점(centroid) 할당으로 매핑하며, 이 수준들은 섀도 메커니즘(shadow mechanism)을 통해 동적으로 설정된다. 이를 통해 엄격하게 제한된 메모리로 비선형 표현력을 달성하는 다양한 가산적(additive) 밴딧 알고리즘을 구현할 수 있다. 13개의 데이터셋(dataset)에 걸쳐, RQ 변형들은 13개 중 11개 데이터셋에서 비-RQ 대응 모델을 종종 큰 차이로 능가했으며, 더블링 재학습(doubling-retrain) 방식의 XGBoost 및 신경망 베이스라인과 비슷한 성능을 최대 1000배 적은 메모리로 달성했다.

원문 초록

Contextual bandits require balancing nonlinear reward modeling with online efficiency. Tree ensembles and neural methods capture nonlinearities but require periodic retraining and large replay buffers. Linear models update efficiently per observation with O(1) memory, but are fundamentally restricted to linear reward structures. We propose Residual Quantization (RQ) as a representation layer to bridge this gap. An offline-trained RQ codebook maps continuous contexts into discrete centroid assignments across multiple levels, set dynamically through a shadow mechanism. This enables a spectrum of additive bandit algorithms that achieve nonlinear expressivity with strictly bounded memory. Across 13 datasets, RQ variants beat their non-RQ counterparts on 11 of 13 datasets, often by wide margins, while matching doubling-retrain XGBoost and neural baselines using up to 1000 times less memory.

제출 이력

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

  1. arXiv:2610.02440v1

함께 살펴볼 논문

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

arXiv:2610.13407v1cs.LG공통 태그 Computational Efficiency, Multi-Armed Bandits

지속적 후보 집합을 활용한 선형 밴딧 가속화

Accelerating Linear Bandits with Persistent Candidate Sets

행동의 수가 $K$개로 매우 큰 고정된 집합을 갖는 선형 밴딧(linear bandit)에서는 완전 낙관적 점수 산출(exhaustive optimistic scoring)로 인해 라운드당 $\mathcal{O}(K)$회의 점수 평가가 필요하여 행동 선택 비용이 커질 수 있습니다. 본 논문에서는 $k$개의 활성 행동을 유지하고 매 라운드마다 나머지 $K-k$개 행동 중에서 $q$개의 도전자(challenger)를 균등하게 표본추출하는 Persistent Candidate LinUCB(\textsc{PC-LinUCB})를 제안합니다. 이 $k+q$개의 후보에 대해서만 점수를 평가함으로써, \textsc{PC-LinUCB}는 라운드당 점수 평가 횟수를 $\mathcal{O}(k+q)$로 줄입니다. 고정된 신뢰 수준에서 표준 선형 밴딧 학습 항과 $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ 차수의 추가적 탐색 비용(discovery cost)으로 구성된 문제 독립적(problem-independent) 및 문제 의존적(problem-dependent) 고확률 후회 경계(regret bound)를 증명합니다. 특히, 이 추가 비용은 시간 지평(horizon)에 따라 증가하지 않습니다. 고정된 간격(gap)과 충분히 긴 시간 지평에 대해 균등 도전자 표본추출 조건 하에서 $\Omega\left((K-k)/q\right)$ 후회 하한을 도출하여, 부분 후보 접근 자체가 불가피한 후회 비용을 수반함을 보여줍니다. 실험 결과, \textsc{PC-LinUCB}는 유사한 수준의 후회를 유지하면서 LinUCB의 속도를 대폭 가속하며, 지속적 후보 메커니즘이 LinUCB를 넘어 다른 알고리즘으로도 확장될 수 있음을 보입니다.

arXiv:2610.13778v1cs.LG공통 태그 Quantization, Computational Efficiency

ReplaySSM: 상태 대신 SSM 입력 캐싱하기

ReplaySSM: Cache SSM Inputs, Not State

상태공간모델(State-space models, SSMs)은 고정 크기의 재귀 상태(recurrent state)를 유지하지만, 매 디코딩 스텝마다 이를 읽고 쓰는 것은 하이브리드 모델의 병목이 될 수 있다. 이러한 즉시적(eager) 상태 관리는 산술 강도(arithmetic intensity)가 낮은 대규모 상태 입출력(I/O)을 유발하고, 추측 디코딩(speculative decoding)에 저비용 롤백을 허용하지 않으며, 상태 양자화 오차를 이후의 재귀 업데이트에 그대로 전달한다. 우리는 재귀식을 펼쳐(unroll) 상태를 체크포인트와 최근 SSM 입력들의 버퍼로 표현하는 ReplaySSM을 제안한다. 이는 출력 계산을 체크포인트 업데이트로부터 분리한다. 체크포인트를 주기적으로 업데이트함으로써 ReplaySSM은 대부분의 스텝에서 상태 쓰기를 피하고, 주된 상태 메모리 트래픽을 대략 절반으로 줄인다. 최근 입력을 유지하는 것은 또한 추측적 롤백을 버퍼 포인터 연산으로 만들고, 중간 상태를 구체화(materialize)하지 않고도 출력만으로 검증(output-only verification)을 가능하게 한다. 동일한 분리를 통해 저정밀도 체크포인트가 대부분의 스텝에서 출력 계산을 담당하고 더 높은 정밀도의 체크포인트가 재귀 업데이트를 담당할 수 있어, 저정밀도 복사본의 라운딩 오차가 이후 업데이트로 전혀 유입되지 않는다. 우리는 ReplaySSM을 vLLM에서 Mamba-2와 Gated DeltaNet에 대해 구현했다. 서빙 배치 크기 256에서, 이는 네 개의 하이브리드 모델 전반에 걸쳐 튜닝된 vLLM 기준선 대비 표준 디코딩을 1.20–1.47배 가속하며, 두 개의 120B급 모델에서는 vLLM의 추측 디코딩 처리량의 약 1.8배를 제공한다. 상태 정밀도를 분리하는 것은 또한 공유 저정밀도 체크포인트에 비해 출력 KL 발산(KL divergence)과 다운스트림 정확도 손실을 줄인다.

arXiv:2610.10630v1cs.LG공통 태그 Quantization, Computational Efficiency

Phase-HDC: 이산 위상 학습에서 옵티마이저 히스토리를 그래디언트 임계값으로 대체하기

Phase-HDC: Replacing Optimizer History with Gradient Thresholds in Discrete Phase Learning

컴팩트한 모델을 학습(training)할 때는 종종 모델 저장보다 훨씬 더 많은 메모리가 필요한데, 이는 옵티마이저(optimizer)가 과거 그래디언트(gradient)의 자체 기록을 유지하기 때문입니다. 학습된 매개변수(parameter)가 저비트 각도인 초차원 분류기(hyperdimensional classifier)의 경우(이를 위상 메모리(\emph{phase memory})라 부름), 이러한 기록은 모델 자체보다 몇 배 더 많은 메모리를 차지합니다. 본 연구에서는 오직 모델 자체만을 저장하면서도 이러한 모델을 학습시킬 수 있는지 질문을 던집니다. 제안하는 방법인 Phase-HDC는 현재 그래디언트의 부호와 반대 방향으로, 그리고 해당 그래디언트가 충분히 클 때에만 업데이트당 저장된 각도를 최대 한 단계씩 회전시킵니다. 우리는 이 단순한 규칙이 변경된 모든 매개변수가 고정 비용을 지불하는 1차 손실(loss) 모델의 정확한 해임을 보여줍니다. 업데이트 규칙을 제외한 모든 조건을 동일하게 유지했을 때, Phase-HDC는 6비트 모멘텀을 사용하는 Adam과 동등한 정확도를 유지하면서도 3배 적은 저장 공간을 사용합니다. 11개의 이미지, 테이블형, 텍스트 데이터셋에 걸쳐, 이 방법은 표준 float32 Adam보다 16~23배, 8비트 Adam보다 4~6배 적은 저장 공간을 차지합니다. 이에 따른 대가는 float32 Adam 대비 평균 약 5%p의 정확도 손실이지만, Phase-HDC는 8비트 Adam이 붕괴하는 바이트 수준 텍스트 예측을 포함하여 11개 데이터셋 중 6개에서 8비트 Adam보다 더 높은 정확도를 달성합니다. 계측된 학습 실행 분석은 이러한 결과를 설명해 줍니다. 매개변수가 이산적인 그리드 상에 위치해야 하는 경우, Adam의 모멘텀은 주로 매개변수가 조금이라도 움직일지 여부만을 결정하게 되며, 이는 현재 그래디언트에 대한 임계값을 통해 메모리 없이도 내릴 수 있는 결정입니다. 또한 모멘텀의 거친 양자화(quantization)는 데이터에 드물게 포함된 입력에 대해 이러한 결정을 망가뜨립니다. 저장 공간 절감은 측정된 하드웨어 메모리가 아닌 논리적 상태 기준입니다.

arXiv:2610.10738v1cs.CL공통 태그 Quantization, Representation Learning

손실 압축 텍스트 오토인코더

Lossy Compressive Text Autoencoders

본 연구는 데이터 압축과 표현 학습(representation learning)의 접점에서 텍스트의 압축된 잠재 표현(latent representation)을 학습하는 방법을 탐구합니다. 우리는 잔여 저차원 이산 병목(residual low-dimension discrete bottleneck)과 함께 시간 축을 따라 은닉 표현의 잔여 다운스케일링 및 업스케일링을 수행하는 오토인코더 아키텍처를 제안합니다. 다양한 양자화(quantization) 방법, 학습(training) 목표 및 데이터셋에 대해 제안하는 접근 방식을 분석합니다. 다양한 압축 수준에 대해 표면적 수준(BLEU)과 의미론적 수준(대규모 언어 모델(LLM) 기반 판정기) 모두에서 원본 텍스트와 재구성된 텍스트 간의 유사도를 평가합니다. 또한 질의응답 및 의미론적 텍스트 유사도 다운스트림 벤치마크에서 모델을 평가합니다. 제안된 접근 방식은 웹 텍스트 데이터에서 바이트당 2.24비트로 무손실 텍스트 압축 알고리즘과 동등한 수준의 압축 표현을 산출하는 동시에, 우수한 재구성 및 다운스트림 태스크 성능을 달성합니다.

arXiv:2610.10933v1cs.LG공통 태그 Quantization, Computational Efficiency

스파이킹 언어 모델에서 시간적 인코딩과 비선형 연산 간의 트레이드오프 재고

Rethinking the Tradeoff Between Temporal Encoding and Nonlinear Computation in Spiking Language Models

스파이킹 언어 모델(Spiking language models)은 짧은 시간 윈도우에서 연속적인 의미적 특징을 표현하는 것과 비용이 많이 드는 비선형 어텐션(attention) 연산을 유지하는 것 사이의 트레이드오프에 직면합니다. 본 논문에서는 스파이크 인코딩과 어텐션 연산자를 공동 설계하는 Spora를 제안합니다. 이진 시간 가중치(binary temporal weights)를 통해 $T$개의 스파이크가 최대 $T$ 비트의 용량으로 구성적 값(compositional values)을 표현할 수 있도록 하며, 이는 스파이크 수 판독(spike-count readout)의 $O(\log_2 T)$ 비트와 대비됩니다. 단극성 이진 스파이킹(Unipolar Binary Spiking, UBS)은 임계값과 스파이크 트리거 잔차 감쇠를 사용하여 음이 아닌 정수 코드를 생성하고, 양극성 이진 스파이킹(Bipolar Binary Spiking, BBS)은 부호와 크기를 분리하며 부호화된 활성화에 대한 스케일을 학습합니다. 이러한 표현은 어텐션에서 누적 및 시프트(accumulation-and-shift) 내적과 정수 지수 매핑을 지원합니다. 4개 타임스텝에서 Spora는 평균 GLUE 점수 76.6점과 CoLA MCC 44.1점을 달성하여 SpikeLM 대비 각각 1.2점 및 6.2점 향상되었습니다. BBS를 6개 스텝으로 확장하면 이 점수는 각각 78.2점과 47.4점으로 상승합니다. 조건부 감쇠 분석, 예산 일치 활성화 양자화(quantization) 비교, 이벤트 워크로드 통계, 고정소수점 평가를 통해 인코딩 충실도와 계산 비용 간의 관계를 추가로 규명합니다.

arXiv:2610.10974v1cs.LG공통 태그 Multi-Armed Bandits, contextual bandits

오프-정책 평가를 위한 예산 제약 다중 소스 반사실적 주석 달기

Budgeted Multi-Source Counterfactual Annotation for Off-Policy Evaluation

오프-정책(off-policy) 평가(OPE)는 기록된 데이터로부터 타깃 정책의 가치를 추정하지만, 행동 정책의 제한된 커버리지로 인해 높은 분산의 가중치 재조정이나 보상(reward) 모델(model) 외삽이 불가피할 수 있습니다. 반사실적(counterfactual) 주석(annotation)은 관측되지 않은 행동에 대한 증거를 추가할 수 있지만, 도메인 전문가나 대규모 언어 모델(LLM)을 포함한 실제 소스는 비용이 많이 들거나 편향되거나 노이즈가 있을 수 있습니다. 본 연구에서는 맥락적 밴딧(contextual-bandit) OPE를 위해 이러한 주석을 예산 제약 하에서 획득하는 문제를 연구합니다. 소스별 비용과 오류 프로필이 주어졌을 때, 주석 계획에 의존하는 추정량 분산 성분을 최소화하도록 맥락-행동 쌍과 주석 소스에 대한 정수 할당 문제를 정형화합니다. 또한 첫 번째 주석 임계값과 국소적 주석 가치 영역을 통해 주석이 언제 유용한지 규명합니다. 결합된 다중 소스 문제에 대해, 목적 함수를 단조적으로 개선하는 동적 계획법 서브루틴 기반의 주화-최소화(majorization-minimization) 알고리즘을 개발합니다. 합성 임상 및 LLM 주석 기반 교육 밴딧 실험에서 본 할당 방법은 주석이 없는 경우 대비 고정 프로필 평균 제곱 오차(MSE)를 각각 20.58% 및 10.77% 감소시킴을 보여줍니다.

토론

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