The verifier side of speculative window decoding: a predictability bracket, a machine-checked blast-radius bound, and a decoder-agnostic recover loop

기술 요약: 추측적 윈도우 디코딩(Speculative Window Decoding)의 검증 측면

문제 정의
실시간 양자 오류 정정(QEC)은 심각한 레이턴시 병목 현상에 직면해 있다. 신드롬 라운드는 고정된 하드웨어 케이던스(초전도 큐비트의 경우 약 1마이크로초)에 따라 도착하지만, 디코더가 이를 따라가지 못하면 신드롬 백로그가 쌓여 결맞음(decoherence)이 논리적 상태를 파괴할 때까지 기다려야 한다. "윈도우 디코딩"은 신드롬 이력을 병렬화 가능한 청크로 분할하지만, 인접한 윈도우들은 여로 직렬 의존성을 갖는다. 즉, 한 윈도우에서 확정된 정정이 다음 윈도우의 디코딩 문제를 결정한다. 이전 연구들, 특히 SWIPER와 ARTERY는 예측(speculation)을 통해 이 직렬 병목을 제거하려고 시도했다. 즉, 다운스트림 윈도우가 조기에 시작할 수 있도록 경계 간 결정을 예측하고, 전체 디코딩은 지연 실행(lazy execution)하며 검증하는 방식이다. 그러나 이 시스템들은 예측 단계만을 구현했을 뿐(~90% 정확도 달성), 엄격한 검증 측면이 결여되어 있었다. 결과적으로 네 가지 근본적인 질문이 해결되지 않은 채 남아 있었다: 예측 정확도의 이론적 한계, 오예측(misprediction) 발생 시 최악의 경우 발생하는 "폭발 반경(blast radius)", 예측의 위험을 감수할 가치가 있는지에 대한 여부, 그리고 전체 '예측-검증-복구(predict-verify-recover)' 루프가 실제 디코더에서 레이턴시를 숨기고 올바르게 복구하는지 여부였다.

방법론
저자들은 이 질문들에 답하기 위해 Stim(회전 표면 코드)과 PyMatching(최소 가중치 완벽 매칭, MWPM)을 사용하여 재구성된 **SWIPER 하네스(harness)**를 구축했다. 방법론은 네 단계로 진행된다:

1. 예측 가능성 브래키팅(Predictability Bracketing): 단일 휴리스틱 예측자에 의존하는 대신, 저자들은 반지름 $R$의 로컬 MWPM 디코더를 사용하여 달성 가능한 정확도의 상한선("천장")을 설정했다. 이 디코더는 경계 컷으로부터 $R$ 라운드 이내의 신드롬 데이터만을 사용하며, 개방형 경계를 윈도우 디코더와 동일하게 취급한다. 이는 어떤 예측기도 주어진 로컬 정보 내에서 달성할 수 있는 이론적 한계를 괄호 안에 묶어 보여준다.
2. 폭발 반경 경계 설정 및 반증(Blast Radius Bounding and Falsification): 저자들은 오예측(잘못된 의존성 비트)이 하나의 윈도우를 통해 전파되는 모델을 구축했다. 먼저, 오예측이 '결함 경로(faulty path)'를 필요로 한다는 감소 가설(reduction hypothesis)에 조건적인 Lean 4 기반의 기계 검증 확률 코어를 사용하여 최악의 시간적 경계를 설정했다. 그 후, 이 감소 메커니즘을 반증하기 위해 날카로운 단일 비트 적대 모델을 대상으로 "샷 바이 샷(shot-by-shot)" 테스트를 엄격하게 수행했다.
3. 컴파일러 패스 유도(Compiler Pass Derivation): 측정된 예측 가능성과 폭발 반경을 사용하여 최적의 재시작 정책을 도출하는 컴파일러 패스를 개발했다. 이 패스는 추상적인 윈도우 의존성 그래프 상에서 작동하며, 비용 모델 $cost = predictability \times slack - blast\_radius$를 기반으로 경계에 스펙큘레이션 플래그를 주석 처리한다.
4. 런타임 실행 및 디코더 불가지론(Runtime Execution and Decoder Aggnosticism): 하네스 상에서 전체 '예측-검증-복구' 루프를 실행하기 위한 런타임 실행기를 구축했다. 발견된 내용 중 무엇이 MWPM 디코더에 특화된 것인지, 아니면 스펙큘레이션 프레임워크 자체의 고유한 특성인지를 결정하기 위해, 저자들은 알고리즘적으로 구별되는 두 번째 디코더인 Union-Find 디코더(가중치 없는 클러스터 성장 방식)를 사용하여 핵심 실험을 재실행했다.

주요 기여 및 결과

• 예측 가능성은 국소적이며 포화 상태에 가깝다: 경계 간 결정은 컷의 양쪽 각각 약 3 라운드의 신드롬에 의해 결정된다. $R=3$의 수용 영역을 가진 로컬 MWPM은 ~0.999의 정확도를 달성했으며, 이는 기존 예측기(SWIPER)의 ~90% 정확도가 근본적인 한계가 아니라 약간의 확산된 여유 공간(코드 거리에 따라 0.019 ~ 0.063)을 남겨두고 있었음을 나타낸다.
• 폭발 반경은 1이다 (시간적 격리): 오예측이 다음 윈도우로 전파될 최악의 확률은 커밋 폭 $W$에 따라 지수적으로 감소한다. 표준 폭($W=d$)에서 전파 확률은 논리적 오류율보다 몇 자릿수 더 낮다(예: $d=7$에서 $10^{-7}$ vs $10^{-5}$). 이는 스펙큘레이션이 에러 플로어(error floor)를 추가하지 않음을 입증한다.
• 결함 경로 메커니즘의 반박: Lean 4 증명은 전파가 "결함 경로"(플립된 비트와 컷을 연결하는 오류 체인)를 필요로 한다는 가설에 조건적이었다. 샷 바이 샷 반증 결과, 이 가설은 거짓임이 드러났다. 전파는 플립된 비트 근처에 결함 경로가 전혀 없음에도 불구하고 일상적으로 발생한다. 실제 메커니즘은 **글로벌 최소 가중치 재-페어링(global minimum-weight re-pairing)**이다. 즉, 디코더가 로컬 흡수가 비용이 더 많이 들기 때문에 기존의 결함을 플립된 비트로 재라우팅하는 것이다. 이 메커니즘은 특히 임계값 근처의 노이즈에서 퇴화(degeneracy)에 의해 주도된다.
• 정확한 복구 및 레이턴시 은닉: 런타임 실행기는 '예측-검증-복구' 루프가 정확하게 복구됨을 확인했다. 16개의 윈도우 체인에서 시스템은 이론적 최대치인 ~16.00의 속도 향상을 달ach하며, 무시할 만한 수준의 재시작 페널티($\sim 10^{-5}$)를 제외하고 직렬 커밋 체인의 스톨(stall)을 제거한다.
• 디코더 불가지론적 구조적 현상: 절대적인 정확도 크기와 특정 "최소 가중치" 메커니즘은 디코더마다 다르지만, 구조적 발견은 견고하다. Union-Find 디코더 실험은 컷 결정이 국소적이며($R=3$에서 포화), 결함 경로 없이도 전파가 지속됨을 확인하여 스펙큘레이션 래퍼의 구조적 현상을 검증했다.

의의 및 주장
본 논문은 추측적 윈도우 디코딩의 누락된 "검증 측면"을 구축하여, 이를 경험적 휴리스틱에서 엄격하게 경계가 설정된 시스템으로 변모시켰다고 주장한다. 그 의의는 다음과 같다:

1. 안전성 입증: 스펙큘레이션이 기계 검증된 확률 경계 내에서 오직 반지름 1 내로 오예측을 격리함으로써 에러 플로어를 도입하지 않음을 입증했다.
2. 메커니즘 명확화: 직관적인 "결함 경로" 모델을 올바른 "글로벌 재-페어링" 메커니즘으로 대체하여, 왜 직접적인 오류 체인이 없음에도 전파가 발생하는지 설명했다.
3. 자동화 가능성: 하드코딩된 수치가 아닌 측정된 수치로부터 재시작 정책을 도출하는 컴파일러 패스를 제공하여, 다양한 코드 레이아웃과 제어 스택에 대한 이 접근법의 이식성을 높였다.
4. 재사용성: '예측-검증-복구' 래퍼를 특정 디코딩 알고리즘과 분리되어 존재하는 재사용 가능한 레이어로 확립하여, 스펙큘레이션 로직을 디코더로부터 독립시켰다.

저자들은 분석적인 선형 체인 맵을 기반으로 한 속도 향상 수치(전체 SWIPER-SIM 파이프라인은 공개되지 않음)를 언급하며 범위에 대해 겸손한 태도를 유지하고 있으며, 매칭 가중치 경계(지수적 감소의 원천)의 정식화는 향후 과제로 남겨두었다. 본 연구는 재현 가능한 코드와 기계 검증된 증명을 통해 검증된, 실시간 QEC를 위한 기초적인 레이어로 제시된다.