SeqoFlow가 LLM 의미 질의의 계획과 스케줄을 동시에 적응시킨다

무엇인가

이 논문은 LLM 기반 의미 연산자가 관계형 처리와 섞인 분석 질의를 여러 개 동시에 서비스할 때 생기는 런타임 동적성을 다룬다. 질의가 계속 도착하고 완료되며 LLM 자원 요구가 달라지는 외부 동적성과, 입력 배치마다 선택도와 토큰 비용이 달라지는 내부 동적성이 맞물린다. 문제는 스케줄러가 남은 LLM 작업량을 알아야 우선순위를 정할 수 있는데, 그 남은 작업량은 실행 중에야 관찰되는 계획 선택에 달려 있다는 점이다. 기존 시스템은 질의 최적화와 추론 스케줄링을 따로 처리해 이 순환 의존을 닫지 못한다.

어떻게 동작하나

SeqoFlow는 정적 전처리기와 동적 실행 엔진으로 이 고리를 닫는다. 전처리기는 질의를 논리적 연산자 트리로 보고, 조인을 기준으로 소스·싱크 파티션을 나눈 뒤 데이터 의존성과 의미 보존 규칙을 지키는 교환만으로 동등한 계획들을 열거해 메모이제이션한다. 실행 엔진은 질의를 배치 경계의 Subquery Execution Unit(SEU)로 잘라, 이미 끝난 배치의 작업을 버리지 않고 남은 배치에 대해 다른 동등 계획으로 갈아탈 수 있게 한다. 동시에 SEU 경계에서 질의를 선점해 다른 질의로 전환할 수 있어, 질의 전체를 끝낼 때까지 붙잡는 run-to-completion 모델의 head-of-line blocking을 피한다.

무엇과 다른가

계획 열거의 핵심은 무손실 최적화다. 저자들은 LLM 출력의 확률적 변동은 무시하고 연산자 의도에 대한 결정론적 의미가 같은 계획만 후보로 둔다. 부모·자식 연산자 교환은 두 규칙으로 제한된다. 부모가 자식이 만든 속성을 읽으면 데이터 의존성 때문에 교환할 수 없고, 행 단위 연산자끼리 또는 행 단위 연산자와 조인 사이에서만 의미 훼손 없이 교환할 수 있다. 집계·정렬 같은 집합 단위 연산자와의 교환은 금지된다. 이렇게 도달 가능한 계획 수는 N!을 2^J와 각 연산자의 hook length 곱으로 나눈 값 이하로 묶이며, 열거된 계획은 중복 없이 동등 계획 공간을 덮는다. 흥미로운 점은 그룹·정렬 키 위로 필터를 올리는 것처럼 동등하지만 열거 공간 밖에 있는 변환은 알고리즘 단순화를 위해 제외한다는 것이다.

어떻게 쓰나

런타임 결정은 가벼운 추정으로 연결된다. SeqoFlow는 후보 계획을 대상 LLM에서 전부 프로파일링하지 않고, 대표 서브쿼리를 작은 언어모델(SLM)로 실행해 연산자별 선택도와 토큰 처리 비용을 모은다. 이 통계를 호환되는 계획 후보들에 전파해 남은 실행 비용을 추정하고, 그 추정값으로 SEU 안의 계획 선택과 질의 간 스케줄링을 동시에 조정한다. 스케줄러는 최단 잔여 시간 우선(SRTF) 같은 선점 기반 정책을 지원하며, 대기 질의에 aging을 적용해 긴 질의가 무한정 굶지 않도록 한다. 논문은 이 추정이 질의 최적화와 LLM 추론 사이의 피드백 루프를 닫는다고 주장한다.

전제와 한계

실험은 Qwen3-4B로 추정하고 Qwen3-32B로 실행하며, 8×A100 서버의 두 vLLM 인스턴스에서 TP=8, 4096토큰 이하 chunked prefill로 구성했다. 프로파일링 오버헤드는 결과에 포함했다. 연속 도착 실험에서 같은 SRTF 스케줄러를 쓸 때 SeqoFlow는 같은 P50 지연에서 Static-1보다 최대 1.9배, Static-2보다 최대 4.3배 높은 처리량을 유지했고 모든 워크로드에서 더 높은 부하까지 포화되지 않았다. 사후에 고른 최적 고정 계획인 Static-Best*보다도 높은 용량을 보였으며, 연산자 비용 변동이 큰 Patent와 Legal에서 격차가 가장 컸다.

스케줄러 효과도 분리해 보고한다. SeqoFlow 내부에서 SRTF는 포화 근처에서 FCFS, MLFQ, PreemptDB보다 P50 지연을 2.5~4배 낮췄고 낮은 부하에서는 비슷했다. SRTF가 긴 작업을 굶겨 꼬리 지연을 키운다는 우려에 대해서는 aging으로 대기 시간을 제한해, LOTUS와 Eddies가 FCFS를 쓸 때보다 P99 지연이 커지기 전까지 1.9배 더 많은 부하를 견뎠고 FCFS를 쓴 SeqoFlow와도 1.4배 이내에 머물렀다. 실제 트레이스 200개를 쓰는 유한 워크로드에서는 SRTF를 쓴 SeqoFlow의 P50이 두 데이터셋에서 LOTUS+FCFS보다 각각 3.6배, 3.5배 낮았고 P99 정체 구간도 약 2배 낮았다. 단일 질의 최적화에서는 모든 설정에서 LOTUS를 이겼고 최대 7배 빨랐으며, 사람이 만든 Static-1·Static-2와 대등하거나 여러 설정에서 앞섰다.

동적성 실험은 배치의 10~90%에서 연산자 비용과 선택도를 뒤집는다. 그 비율이 커질수록 Static-Best*는 Eddies보다도 나빠지지만, SeqoFlow는 배치마다 계획을 다시 골라 모든 비율에서 둘을 이기고 Eddies 대비 종단 간 1.32~1.43배 빨랐다. 추정 정확도도 보고한다. 70% 배치를 뒤집은 조건에서 80% 넘는 배치가 실제 비용 대비 10% 이내 오차로 추정됐고, 95% 넘는 배치에서 실제 비용 기준 상위 2개 계획 중 하나를 실행했다. SRTF 순위는 aging 없이 최대 94.5%의 질의 쌍을 올바르게 정렬했고 Spearman ρ는 최대 0.92였으며, aging 후에도 최소 74.8%를 유지했다. 동일 4B SLM을 DeepSeek-Flash와 GPT-6 Luna API에 붙여도 Static-Best*보다 높은 처리량을 유지했다. 오버헤드는 대부분 질의에서 추정이 10% 미만, 계획 열거는 무시할 수준이었지만, 계획 공간이 1000개를 넘는 극단과 가장 어려운 Q8에서는 추정이 실행 시간의 41.6%를 차지했다.

개발자 관점에서 이 논문은 LLM 호출이 섞인 분석 파이프라인에서 질의 플랜과 GPU 추론 스케줄러를 별도 계층으로 두면 남은 작업량 추정이 쉽게 낡아진다는 점을 보여준다. 배치 단위 선점 경계, 동등 계획 열거, SLM 기반 비용 추정을 함께 설계해야 고정 계획의 한계를 피할 수 있고, 특히 선택도가 입력 내용에 따라 크게 흔들리는 필터·조인·프로젝션이 많은 워크로드에서 효과가 크다. 다만 저자들은 계획 공간이 독립 연산자에서 O(N!)까지 커질 수 있어 원칙 있는 가지치기가 향후 과제라고 밝힌다. 또한 동시 데이터 수정과 일관성, 질의 간 연산자·LLM 호출 공유는 다루지 않으며, 저장 백엔드가 배치 처리를 지원해야 하고, 동등성은 LLM 출력의 확률적 변동을 무시한 결정론적 의미 기준이다. 그룹·정렬 키 위로 필터를 올리는 등 동등하지만 열거 공간에서 제외한 변환이 있고, Q0처럼 연산자가 적어 후보가 거의 없는 질의에서는 개선 여지가 작고 프로파일링 오버헤드가 상대적으로 커질 수 있다.