토스, 정수계획법으로 추천 TopK 최적화해 CVR 7.55% 개선

토스 쇼핑 추천 시스템은 Retrieval 단계에서 가져오는 후보 수(TopK)를 경험적으로 정해왔다. 후보가 많으면 Ranking 비용과 응답 시간이 증가하고, 가치가 낮은 후보가 섞일 수 있어 효율적 배분이 필요했다.

토스 Commerce Personalization Team은 이 문제를 배낭 문제로 정의하고 **정수계획법(Integer Programming)**을 적용했다. 전체 후보 수를 기존 대비 약 50%로 제한하는 제약 조건 하에, 각 리트리벌 모델의 예상 구매 가치(pICVR) 합을 최대화하는 모델별 TopK를 산출했다.

7일간의 온라인 A/B 테스트 결과, 정수계획법 실험군은 비교군 대비 User CVR이 7.55%, Order PU(사용자당 주문 수)가 10.13% 상승했다. 반면 CTR은 3.71% 감소했으며, 이는 클릭 기회는 줄었지만 남은 클릭의 구매 전환 효율이 높아졌음을 시사한다. 또한 고유 노출 상품 수가 22.07% 줄어 다양성 감소 문제가 발생했다.

이후 후속 실험에서는 Gumbel Weighted Sampling을 적용해 피드 중복도를 11.25% 낮추고 노출 다양성을 4.61% 높였다. 토스는 향후 사용자 이력과 상태에 따라 모델별 TopK를 다르게 배정하는 개인화된 TopK 최적화를 검토 중이다.