Automating Potential Discovery for the $k$-Server Conjecture

Motivation

• Known: k-server 추측은 경쟁 분석 분야의 대표적 미해결 문제이며, Work Function Algorithm(WFA)이 (2k-1)-competitive임이 알려져 있고, 여러 metric family에서는 potential function을 구성해 k-competitiveness를 증명하는 방식이 주 증명 패러다임이다. circle metric의 경우 k=3은 Huang & Zhang(2022)에 의해 해결되었으나 k=4를 포함한 일반 경우는 여전히 열려 있다.
• Gap: potential function 발견은 지금까지 사람의 수작업 구성과 검증에 의존해왔으며, 이 과정을 자동화하고 AI 에이전트가 탐색 가능한 형태로 정식화한 선행 연구는 없었다. 특히 circle metric의 k=4 case는 어떤 알려진 potential도 모든 제약을 만족시키지 못하는 상태로 남아있다.
• Why: 이 연구는 potential function 탐색이라는 수학적으로 중요하지만 사람이 직접 구성하기 어려운 문제를 program search 기반 AI 에이전트가 다룰 수 있는 executable optimization 문제로 변환함으로써, 이론 컴퓨터 과학의 대표적 난제에 대한 자동화된 접근을 최초로 제시하고, 동시에 code 기반 수학 발견 에이전트를 평가할 수 있는 벤치마크를 제공한다.
• Approach: 유한 metric space에서 work-function graph를 구성하고, 후보 potential function Φ가 모든 엣지에 대해 Φ(w_v) - Φ(w_u) ≥ γ(u,r,v) 부등식을 만족하는지 자동으로 검증하는 verifier를 설계하여, agent가 제출한 Python 프로그램 형태의 potential을 위반 부등식 개수로 채점한다.

Achievement

Figure 1. 10 independent runs of SHINKAEVOLVE, BEST-OF-N, LOONGFLOW powered by gpt-oss-120b per task design: (i) no

1. Executable optimization으로서의 증명 탐색: potential-function 발견을 프로그램 제출과 부등식 위반 개수 채점으로 이루어진 executable optimization 문제로 최초로 정식화했다.
2. Potential discovery를 위한 tooling 구축: work-function 부등식 시스템 구성, 다양한 discretization level과 k-taxi augmentation을 가진 circle instance 생성, 빠른 부등식 검증, 진단용 위반 리포트, 재현 가능한 비교를 지원하는 표현 형식 등 전체 파이프라인을 구현했다.
3. 해결/미해결 영역에서의 실증적 진전: agentic method가 해결된 k=3 circle case에서 zero-violation potential을 복구했고, 미해결 k=4 영역에서도 augmented k=4, m=6 instance의 위반 수를 기존 17에서 3으로 줄이는 부분적 진전을 이루었다.

How

Figure 1. 10 independent runs of SHINKAEVOLVE, BEST-OF-N, LOONGFLOW powered by gpt-oss-120b per task design: (i) no

• 유한 metric space M과 정수 k가 주어지면 work-function graph (V,E)를 구성하고, 각 노드는 서버 배치 configuration에 대한 work-function 벡터 w_u와 연관됨
• 각 방향 엣지 (u,r,v)는 가중치 γ(u,r,v)를 가지며, 목표는 모든 엣지에서 Φ(w_v)-Φ(w_u) ≥ γ(u,r,v)를 만족하는 potential Φ를 찾는 것
• 무한한 circle metric을 다루기 위해 점점 세밀해지는 discretization 시퀀스와 k-taxi augmentation을 활용하여 유한 instance들로 근사
• 유한 instance에서 모든 부등식을 만족시키면 해당 instance에 대한 WFA의 k-competitiveness 증명서(certificate)가 됨 (Proposition 2.1)
• SHINKAEVOLVE, BEST-OF-N, LOONGFLOW 등 agentic 방법을 verifier와 결합해 10회 독립 실행으로 potential 탐색 실험을 수행

Originality

• 수학 난제의 증명 구성 요소(potential function)를 AI 에이전트가 다룰 수 있는 sound하지만 incomplete한 executable optimization 문제로 정식화한 최초의 시도
• work-function graph라는 개념을 명시적으로 formalize하여 기존 문헌에서 암묵적으로만 사용되던 그래프 기반 관점을 공식화함
• 단순 점진적 score 개선이 아니라 zero-violation이라는 명확한 목표를 통해 방법론 간 우열을 명확히 가릴 수 있는 벤치마크를 제안, 기존 code 기반 open-ended discovery 벤치마크의 saturation 및 random baseline 강세 문제를 보완

Limitation & Further Study

• zero-violation 달성이 sound하지만 incomplete한 증거이며, 실제 무한 circle metric에 대한 완전한 수학적 증명을 구성하지는 못함
• k=4 circle case는 여전히 미해결로 남아 있으며, agent가 발견한 potential도 완전한 해를 제공하지 못하고 지속적인 실패 모드(failure mode)를 보임
• discretization과 k-taxi augmentation에 의한 근사가 실제 무한 metric의 모든 구조를 포착하는지에 대한 이론적 보장이 제한적임
• 후속 연구로 더 정교한 discretization 전략, 다양한 agentic 탐색 알고리즘의 적용, 그리고 발견된 potential의 수학적 분석을 통한 완전한 증명으로의 확장이 필요함

Evaluation

총평: k-server 추측이라는 이론 컴퓨터 과학의 대표적 미해결 문제에 AI 에이전트 기반 자동화 탐색을 적용한 참신하고 시의적절한 시도로, 완전한 해결에는 이르지 못했지만 명확한 벤치마크와 실증적 진전을 제시한 의미 있는 워크샵 논문이다.