작업-깊이 트릴레마

📍 현재 위치: IV부 · 규모와 시스템 — 11장. GPU 추론은 완성 고정점의 각 파동을 행렬 대수로 바꾸어 값싸게 만들었습니다; 이 장은 배치화가 결코 건드릴 수 없는 단 하나, 곧 순서대로 실행되어야 하는 파동의 개수를 셉니다.

앞 장은 매 라운드가 하나의 배치화된 텐서 패스였던 고정점으로 끝을 맺었고, 공정한 질문 하나를 남겨 두었습니다: 한 라운드가 이제 단 하나의 행렬 연산이라면, 그 추론기는 빠른가? 이 질문에는 서로 다른 두 개의 답이 있는데, 비용에 서로 다른 두 축이 있기 때문입니다. 작업(work)이란 계산이 수행하는 연산의 총 개수로, 모든 곳에서 모든 것에 걸쳐 합산한 값입니다. 깊이(depth)란 각 연산이 바로 앞 연산의 결과를 필요로 하는 연산 사슬 중 가장 긴 것의 길이이며, 그래서 아무리 많은 하드웨어를 투입해도 그 연산들을 겹쳐 실행할 수 없습니다. 병렬 기계는 실행 시간을 깊이 쪽으로 줄여 갈 뿐, 결코 깊이보다 더 낮출 수는 없습니다. 이 장은 컴패니언 모듈 work_depth.py로 추론을 두 축 모두에서 측정하며, 그 프론티어가 하나의 선이 아니라 세 개임을 밝힙니다: 순수한 도달 가능성은 산더미 같은 추가 작업을 지수적으로 더 적은 깊이와 맞바꿀 수 있고, EL 완성 핵심은 그 거래를 아예 할 수 없으며(그리고 이론이 그 이유를 말해 줍니다), 그 둘 사이에는 이 권이 계속 돌려 볼 공학적 다이얼, 곧 고정된 라운드 수 이후에 잘라 낸 커널이 놓여 있는데, 이는 모든 예산에서 완벽하게 건전한 채로 남으며 오직 재현율만을 대가로 치릅니다. 세 번째 축인 메모리는 여기서는 오직 암묵적으로만 셈해지며, 끝에서 이 장의 제목이 트레이드오프가 아니라 트릴레마라고 말하는 정직한 이유로 되돌아옵니다.

쉽게 말하면

원하는 만큼 도우미를 데리고 결혼식 출장 요리를 한다고 상상해 보십시오. 청첩장 오백 장에 주소를 쓰는 일은 완벽하게 병렬화됩니다: 도우미 오백 명, 일 분, 끝입니다. 그러나 육수를 졸이는 일은 그렇지 않습니다: 뭉근히 끓이고, 졸이고, 맛을 보아야 하며, 각 단계는 앞 단계의 결과를 필요로 하므로, 아흔아홉 명의 요리사를 더 투입해도 아흔 분짜리 뭉근한 끓임을 단 일 초도 줄여 주지 않습니다. 그 뭉근히 끓이는 시간이 바로 깊이입니다. 모든 도우미가 일한 매 분을 합산한 총 노동 청구서가 바로 작업입니다. 때로는 작업으로 깊이를 사서 줄일 수 있습니다: 압력솥은 분당 훨씬 더 많은 에너지를 씀으로써 육수를 삼분의 일의 시간에 끝냅니다. 그리고 때로는 화학이 그 거래 자체를 거부합니다: 어떤 도구도 맛보기가 그것이 맛보는 졸임보다 먼저 일어나게 할 수는 없습니다. 추론에는 정확히 이 세 가지 상황이 있으며, 이 장은 커밋된 코드로 어떤 추론 규칙이 청첩장 같은지, 어떤 것이 압력솥으로 줄일 수 있는 육수 같은지, 어떤 것이 고집 센 화학 같은지를 셉니다.

이 장에서 다루는 내용

바닥부터 다시 세우는 작업과 깊이: 가능한 가장 작은 예제(숫자 목록을 합산하는 일) 위에서 세어 두 양을 정의하고, 왜 깊이가 프로세서 개수에 상관없이 실행 시간의 하한이 되는지, 그리고 정직한 역명제, 곧 작업이 누군가 항상 치러야 하는 청구서라는 것을 다룹니다.
두 가지 방식으로 값이 매겨지는 도달 가능성: 선형 파동 커널을 도달 가능성 행렬의 반복 제곱과 맞세우며, 둘 다 커밋된 코드에서 그대로 인용하고, 둘 다 독립적인 참조와 동일함을 단언하며, 사슬 길이 8, 64, 512에서 셈해진 깊이/작업 표와, 정확히 진술된 고전 정리(추이 폐쇄는 NC²에 있다)를 다룹니다.
거래를 거부하는 핵심: 레이블 도출과 엣지 도출이 서로를 엄격하게 교대로 필요로 하는 다섯-단 교대 사다리를 다루며, 그래서 고정점은 지름 1인 역할 그래프 위에서 11번의 파동을 필요로 하고, 상수-라운드 제곱 파이프라인은 한 장치에서는 증명 가능하게 미달하고 다른 장치에서는 불건전하게 초과함을 다룹니다.
규율을 지켜 들여온 복잡도의 벽: EL 포섭과 데이터로그 폐쇄가 PTIME-완전이며, NC = P가 아닌 한 PTIME-완전 문제는 다항로그-깊이·다항-작업량 알고리즘을 허용하지 않는다는 것을 다루며, 정리는 인용되고 추측의 상태는 진술되며, 장난감 예제는 그 메커니즘으로서 제시될 뿐 결코 증명으로 제시되지 않습니다.
절단 법칙: 파동 커널을 L 라운드 이후에 잘라 내는 것이 모든 L에서 건전하며(단조성에서 유도된 정확한 부분집합 단언) 정확히 L = D에서 완전해진다는 것을, 커밋된 재현율-대-L 곡선과 함께, 그리고 절단의 오류 방향이 왜 임베딩의 오류 방향과 정반대인지를 다룹니다.
삼단 규모 확장 법칙: 상수-깊이 재작성, 로그-깊이 제곱, 선형-깊이 파동을 하나의 표로 조립하며, 각 행마다 그 조각, 깊이, 작업, 근거를 담고, 확장성이 시스템보다 먼저 조각(fragment)에 속한다는 독법 규율을 더합니다.
다이얼이 다시 나타나는 곳: 고정-깊이 네트워크, 사고 사슬 디코딩, SATORI 커널의 고정-L 펼침을 각각 이 장의 법칙이 다른 옷을 입은 것으로 이름 붙입니다.

세어서 정의하는 작업과 깊이

어떤 구조든 지닌 가장 작은 계산을 하나 골라 봅시다: 숫자 목록 $a_1, a_2, \ldots, a_n$ 을 합산하는 일이며, 여기서 $n$ 은 목록의 길이이고 $a_i$ 는 $i$ 번째 위치의 숫자입니다. 눈에 보이는 뻔한 루프는 $((a_1 + a_2) + a_3) + \cdots$ 를 계산합니다: 이는 $n - 1$ 번의 덧셈을 수행하며, 모든 덧셈이 바로 앞 덧셈의 결과를 기다리므로, 총 연산 횟수와 가장 긴 의존 사슬의 길이가 둘 다 $n - 1$ 입니다. 이제 같은 덧셈들을 균형 트리로 재구성해 봅시다: 숫자들을 짝지어 각 쌍을 동시에 더하면 남는 값의 개수가 대략 절반으로 줄고, 그 값들을 다시 짝지어 반복합니다. 어떤 덧셈이든 여전히 두 값을 소비하고 하나를 내놓으며, 계산은 $n$ 개의 값으로 시작해 $1$ 개로 끝나므로, 어떻게 스케줄을 짜든 정확히 $n - 1$ 번의 덧셈이 일어납니다. 그러나 라운드의 개수는 완전히 달라집니다: 각 라운드는 살아남는 값의 개수를 적어도 절반으로 줄이므로, $t$ 번의 라운드 뒤에는 많아야 $\lceil n / 2^t \rceil$ 개의 값이 남고(천장 괄호 $\lceil \cdot \rceil$ 는 다음 정수로 올림한다는 뜻입니다), $2^t \ge n$ 이 되는 즉시, 즉 $t = \lceil \log_2 n \rceil$ 번의 라운드 뒤에 값이 하나만 남습니다. 여기서 $\log_2 n$ 은 $2$ 를 몇 제곱해야 $n$ 이 되는지를 나타내는 지수입니다. 이 두 스케줄이 이 장의 두 가지 양을 정의합니다 [1]:

작업(work) $W$ : 실행된 연산의 총 개수이며, 여기서는 두 스케줄 모두에서 $n - 1$ 입니다.
깊이(depth) $D$ : 각 연산이 앞선 연산의 출력을 필요로 하는 연산 사슬 중 가장 긴 것의 길이이며, 여기서는 루프의 경우 $n - 1$ , 트리의 경우 $\lceil \log_2 n \rceil$ 입니다.

이 한 쌍이 중요한 이유는 기계에 무관한 하나의 사실 때문입니다. $p$ 개의 프로세서를 갖춘 이상화된 병렬 기계(PRAM, parallel random-access machine, 병렬 무작위 접근 기계: 모든 프로세서가 매 단계마다 공유 메모리를 읽고 쓸 수 있는 표준적인 추상화입니다 [1]) 위에서, 실행 시간 $T_p$ 는 두 개의 하한을 동시에 따릅니다: $T_p \ge W / p$ 인데, $p$ 개의 프로세서는 매 단계 많아야 $p$ 번의 연산을 실행할 수 있고 $W$ 번의 연산 전부가 일어나야 하기 때문입니다. 그리고 $T_p \ge D$ 인데, 가장 긴 의존 사슬 위의 연산들은 프로세서가 아무리 많이 남아돌아도 하나씩 차례로 실행되어야 하기 때문입니다. 이와 짝을 이루는 상한인 브렌트의 스케줄링 경계(Brent's scheduling bound)는 $T_p \le W/p + D$ 라고 말합니다: 탐욕적 스케줄링은 두 하한을 그 합까지 동시에 달성합니다 [1]. 이 두 하한을 이 장의 두 가지 교훈으로 읽으십시오. 깊이는 어떤 발주서로도 제거할 수 없는 비용의 몫입니다: 프로세서가 몇 개든 상관없이 시간을 아래로 묶어 둡니다. 작업은 누군가 항상 치르는 몫입니다: 셈해진 연산 하나하나가 에너지와 하드웨어 점유를 비용으로 치르므로, 작업을 제곱해서 깊이를 절반으로 줄이는 알고리즘은 공짜가 아니라, 비용을 시계에서 전기 요금 청구서로 옮겨 놓았을 뿐입니다.

무언가를 셈하기 전에 지켜야 할 장부 규칙이 하나 있으며, 아래 숫자들이 감사 가능하도록 모듈의 셈 규칙 주석 블록에서 다시 풀어 씁니다(work_depth.py, 75–82행): 셈해지는 연산은 폐쇄 계산 자체의 불 반환(boolean-semiring) 연산입니다. 조밀한 $n \times n$ 불 행렬 곱은 $n^2 (2n - 1)$ 번의 연산을 셉니다. $n^2$ 개의 출력 칸 각각이 $n$ 번의 AND-탐침과 $n - 1$ 번의 OR-환원을 수행하기 때문입니다. 희소한 파동 커널은 조인 탐침 한 번마다 연산 하나를, 그리고 진짜로 새로운 쌍을 성공적으로 병합할 때마다 연산 하나를 셉니다. 고정점 판정 비교(행렬의 동등성, 프런티어의 공집합 여부)는 어느 커널에서도 셈해지지 않으므로, 두 커널의 비교는 동일한 기준끼리의 비교입니다.

두 가지 방식으로 닫히는 도달 가능성

첫 번째 시험대는 병렬화가 잘 되는, 추론과 가장 닮은 문제입니다: 반사·추이 폐쇄(reflexive-transitive closure)로, 방향 그래프에서 모든 노드 쌍 $(i, k)$ 에 대해 $i$ 에서 $k$ 로 가는 경로가 존재하는지를 판정하는 문제입니다. 이번 시리즈의 실행 예제에서 이는 정확히 원자적 포섭에 해당합니다. 2권의 정규화된 학계 TBox(용어 상자, 곧 온톨로지의 공리 집합) 가운데 nf1 조각, 곧 개념 이름들 사이의 $A \sqsubseteq B$ 모양을 한 모든 공리(읽는 법: 모든 $A$ 는 $B$ 이다; 이 관계 $\sqsubseteq$ 를 포섭이라 부릅니다)는 하나의 방향 그래프이며(모듈은 이를 ontology.py에서 el_completion.normalize를 거쳐 임포트할 뿐 결코 다시 타이핑하지 않습니다; work_depth.py, 184–192행), 도출된 포섭 관계 $A \sqsubseteq^{*} B$ 는 정확히 도달 가능한 쌍들입니다. 가장 긴 사슬은 $\mathsf{Dean} \sqsubseteq \mathsf{Professor} \sqsubseteq \mathsf{Researcher} \sqsubseteq \mathsf{Person}$ 입니다( $\mathsf{TenuredStudent}$ 를 거치는 두 사슬이 세 개의 엣지로 동률을 이룹니다). 이와 나란히 모듈은 최악의 경우인 사슬 $v_0 \to v_1 \to \cdots \to v_{n-1}$ 의 계열을 $n = 8, 64, 512$ 에서 닫습니다. 이 절과 그 도달 가능성 표에서 $D$ 는 그래프의 지름(diameter), 곧 임의의 두 노드 사이의 최단 경로 거리 가운데 가장 긴 유한한 값을 가리키며, 이는 셈해지는 두 커널 어디에도 손대지 않는 독립적인 너비 우선 탐색으로 계산됩니다(work_depth.py, 364–384행). 그리고 두 커널 모두 세 번째의 순수한 깊이 우선 탐색 참조와 동등함이 단언되므로(405–406행), 어느 한쪽이 다른 한쪽 하나만을 기준 삼아 채점되는 일은 결코 없습니다.

파동 커널: 적은 작업으로 이루어지는 D − 1번의 라운드

첫 번째 커널은 준순진(semi-naive) 폐쇄로, 1권의 전방 연쇄기와 앞 장의 델타 요령이 썼던 것과 같은 프런티어 규율입니다: 지금까지 찾아낸 폐쇄를 간직하고, 매 라운드마다 오직 가장 새로운 쌍들(프런티어 $\Delta$ )만을 기본 엣지 $M$ 과 조인하여, 모든 쌍이 정확히 한 번만 도출되게 합니다(work_depth.py, 108–139행):

    closure: set[tuple[str, str]] = {(u, u) for u in nodes} | set(edges)
    delta = set(closure)
    depth = 0
    ops = 0
    while delta:
        new: set[tuple[str, str]] = set()
        for i, j in delta:
            for k in out.get(j, ()):
                ops += 1                       # one ∧-probe of the join Δ ⋈ M
                if (i, k) not in closure and (i, k) not in new:
                    ops += 1                   # one ∨-merge of a new pair
                    new.add((i, k))
        if not new:
            break
        closure |= new
        delta = new
        depth += 1
    return closure, depth, ops

그 깊이는 정확히 $D - 1$ 번의 라운드이며, 이는 관찰이 아니라 유도로 보일 수 있습니다. $t$ 번의 생산적인 라운드 뒤에 갖게 되는 폐쇄를 $R_t$ 라 씁시다. 불변량은 $R_t$ 가 정확히 거리 $t + 1$ 이하인 쌍들을 담는다는 것입니다. 기저 사례: $R_0$ 은 $I \vee M$ , 곧 항등 쌍들(거리 $0$ )과 기본 엣지들(거리 $1$ )로 초기화되므로, 불변량은 $t = 0$ 에서 성립합니다. 귀납 단계: $t \ge 1$ 일 때 프런티어 $\Delta_t$ 는 정확히 최단 거리가 $t + 1$ 인 쌍들을 담습니다(이들은 라운드 $t$ 에서 새로 생긴 것들입니다; $t = 0$ 에서는 프런티어가 항등 쌍들도 추가로 담지만, $(i, i)$ 를 엣지 $(i, k)$ 와 조인해 보아야 $R_0$ 에 이미 있는 기본 엣지를 재생산할 뿐이므로 그 추가된 원소들은 아무것도 새로 더하지 않습니다). 이 라운드는 각 $(i, j) \in \Delta_t$ 를 각 기본 엣지 $(j, k) \in M$ 과 조인하여, 길이 $t + 1$ 인 최단 경로를 한 엣지만큼 늘려 길이 $t + 2$ 인 경로로 만듭니다. 이렇게 만들어진 경로 중 진짜로 새로운 것은 정확히 길이 $t + 2$ 를 가지며, 거꾸로 거리 $t + 2$ 에서 처음 도달 가능해지는 어떤 쌍이든 그런 분해를 가집니다(그 최단 경로의 마지막 엣지는 어떤 $(j, k) \in M$ 이고, 그 앞부분은 정확히 길이 $t+1$ 입니다). 그러므로 이 라운드는 정확히 거리- $(t{+}2)$ 인 쌍들을 더합니다. 따라서 새로운 쌍은 정확히 $t + 2 \le D$ 인 동안에만 존재하며, 이는 $D - 1$ 번의 생산적인 라운드를 주는데, 이것이 바로 모듈이 모든 그래프 위에서 단언하는 바입니다(408행).

셈해진 작업량은 놀랍도록 작으며, 사슬 위에서는 닫힌 형식을 가집니다. 각 폐쇄 쌍 $(i, j)$ 는 프런티어에 정확히 한 번 들어가며, $j$ 의 나가는 엣지 하나당 탐침 하나씩을 기여합니다; 사슬 위에서는 마지막 노드를 제외한 모든 노드가 나가는 엣지를 하나씩 가집니다. $n$ -사슬의 폐쇄는 $\sum_{i=0}^{n-1} (n - i)$ 개의 쌍을 가지는데, 여기서 합 기호 $\sum$ 는 $0$ 부터 $n - 1$ 까지의 모든 $i$ 에 대해 항 $n - i$ 를 한 번씩 더한다는 뜻이며, 이 합은 $n(n+1)/2$ 와 같습니다(노드 $v_i$ 는 자기 자신과 그 뒤의 모든 노드에 도달하여 $n - i$ 개의 쌍을 기여합니다). 탐침: 두 번째 좌표가 나가는 엣지를 가지는 쌍은 $n(n+1)/2 - n = n(n-1)/2$ 개입니다. 병합: $R_0$ 에 아직 없는 쌍은 $n(n+1)/2 - (2n - 1) = (n-1)(n-2)/2$ 개입니다. 두 항에서 $(n-1)$ 을 묶어 내면:

\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{2} \;=\; \frac{(n-1)\big(n + (n-2)\big)}{2} \;=\; (n-1)^2 .

$n = 512$ 일 때 이는 $511^2 = 261{,}121$ 번의 셈해진 연산을 예측하며, 아래의 커밋된 표는 정확히 그 숫자를 보여 줍니다. 파동 커널은 사실상 낭비되는 작업이 전혀 없습니다; 그 비용은 오직 깊이, 곧 엄격하게 순서 지어진 $510$ 번의 라운드에 있습니다.

반복 제곱: 많은 작업으로 이루어지는 ⌈log₂ D⌉번의 라운드

두 번째 커널은 깊이를 직접 공략합니다. 불 행렬 $A_0 = I \vee M$ 을 만들고(칸 $(i,k)$ 는 $i = k$ 이거나 $(i,k)$ 가 기본 엣지일 때 참입니다), 곱셈이 AND이고 덧셈이 OR인 불 행렬 곱 $\odot$ 아래에서 이를 반복해서 제곱합니다(work_depth.py, 142–174행):

    A = np.eye(n, dtype=bool) | M
    productive = 0
    executed = 0
    ops = 0
    while True:
        A2 = bmm(A, A)
        executed += 1
        # n² cells × (n ∧-probes + (n−1) ∨-reductions) per dense product.
        ops += n * n * (2 * n - 1)
        if np.array_equal(A2, A):
            break
        A = A2
        productive += 1

이제 불변량은 증가하는 대신 두 배씩 늘어납니다: $A_t$ 는 정확히 길이 많아야 $2^t$ 인 경로로 이어지는 쌍들을 담습니다. 기저 사례: $A_0 = I \vee M$ 은 길이 $0$ 과 $1$ , 즉 많아야 $2^0$ 을 담습니다. 귀납 단계: 이 곱의 정의는 $A_{t+1}[i,k] = \bigvee_j A_t[i,j] \wedge A_t[j,k]$ 이며, 여기서 $\bigvee_j$ 는 중간 노드 $j$ 전체에 대한 OR입니다; 길이 $\ell \le 2^{t+1}$ 인 어떤 경로든 $\min(\ell, 2^t)$ 걸음 뒤에 도달하는 노드에서 각각 길이 많아야 $2^t$ 인 두 절반으로 쪼갤 수 있고, 거꾸로 그런 두 절반을 이어 붙이면 길이 많아야 $2^{t+1}$ 인 경로가 되므로, 불변량은 그대로 이어집니다. 고정점은 $2^t \ge D$ 가 되는 즉시, 곧 정확히 $\lceil \log_2 D \rceil$ 번의 생산적인 제곱 뒤에 도달하며, 여기에 더해 아무것도 바뀌지 않았음을 증명하는 것만이 유일한 임무인 마지막 제곱 한 번이 더 있습니다. 모듈은 모든 그래프 위에서 이 두 셈 모두를 단언합니다(411–413행). 짚고 넘어갈 만한 세부 사항이 하나 있으며, 그 자체로 커밋된 시연을 얻습니다: 항등원은 제곱하기 전에 OR로 더해 넣어야 합니다. 있는 그대로의 $M^{2^t}$ 는 정확히 길이 $2^t$ 인 보행만을 담으므로, 비순환 그래프 위에서는 그보다 짧은 모든 경로를 잊고 무너져 버립니다; $\lvert M \rvert$ 를 $M$ 의 참인 성분 개수(행렬식이 아니라 개수)를 뜻하는 표기로 쓰기로 하면, 7-엣지 사슬 위에서 모듈은 $\lvert M \rvert = 7$ , $\lvert M^2 \rvert = 6$ , $\lvert M^4 \rvert = 4$ , $\lvert M^8 \rvert = 0$ , 곧 영행렬임을 검증합니다(443–449행).

그 대가는 밀도입니다. 실행되는 모든 제곱은 행렬이 희소하든 아니든 상관없이 $n^2(2n-1)$ 번의 셈해진 연산이 드는 완전한 조밀 곱입니다. $n = 512$ 에서: $512^2 = 262{,}144$ 개의 칸, 칸당 $2 \cdot 512 - 1 = 1023$ 번의 연산이므로 제곱 한 번당 $268{,}173{,}312$ 번의 연산이 들고, 실행된 제곱 $10$ 번이면 $2{,}681{,}733{,}120$ 번이 됩니다. 다음은 모듈의 실제 출력에서 그대로 인용한 커밋된 표입니다(python3 examples/frontier/work_depth.py 실행):

[1] the reachability slice, closed two ways (both == DFS reference)
                             linear semi-naive        (I ∨ M) squaring
  graph                n    D    waves          ops   sq(+1)            ops     work ratio
  chain n=8              8    7        6           49      3+1          3,840        78.4x
  chain n=64            64   63       62        3,969      6+1      3,641,344       917.4x
  chain n=512          512  511      510      261,121      9+1  2,681,733,120    10,270.1x
  academic ⊑-preorder    6    3        2           19      2+1          1,188        62.5x

이 거래의 두 방향을 한 행 위에서 함께 읽어 봅시다. $n = 512$ 에서 깊이는 순서 지어진 $510$ 번의 라운드에서 $9{+}1$ 로 떨어지는데, 이는 $\lceil \log_2 511 \rceil = 9$ 와 일치합니다. 반면 셈해진 작업량은 $261{,}121$ 에서 $2{,}681{,}733{,}120$ 로 치솟아 $10{,}270$ 배가 됩니다. 이 두 방향 모두 단지 보여지기만 하는 것이 아니라 지켜집니다: 모듈은 생산적인 제곱 횟수가 $\lceil \log_2 D \rceil$ 과 같음을 단언하고, 모든 사례에서 제곱의 작업량이 선형 작업량을 엄격히 웃돈다는 것을 단언하며, 그 단언에 딸린 주석은 이를 있는 그대로 부릅니다: 작업으로 사들인 로그 깊이(411–419행). 학계 선순서(preorder) 행은 실행 예제 위에서 같은 법칙을 그대로 보여 줍니다: $\mathsf{Dean}$ 에서 $\mathsf{Person}$ 까지의 사슬은 $D = 3$ 을 주며, 두 번의 파동 또는 $2{+}1$ 번의 제곱, $19$ 대 $1{,}188$ 번의 셈해진 연산입니다. 그리고 이 조각은 실제 계산법의 한 조각이므로, 모듈은 건전성에 대한 순환도 닫습니다: 도출된 모든 쌍 $A \sqsubseteq^{*} B$ 는 전체 분류의 포화된 레이블 안에, 곧 $B \in S(A)$ 안에 들어 있음이 단언되며, 이는 원본 완성 상태에 대비해 검사되는데, 전체 TBox가 $\mathsf{TenuredStudent} \sqsubseteq \bot$ 을 증명하고( $\bot$ 은 바닥 개념, 곧 원소가 하나도 없는 개념이므로 이 클래스는 충족 불가능합니다) 다듬어진 보고서는 충족 불가능한 개념들을 숨기기 때문입니다(424–433행).

제곱 열 뒤에 있는 이론은 하나의 고전적 정리이며, 여기서는 들여온 이론에 대한 이 시리즈의 관행이 그대로 적용됩니다. NC(닉의 부류, Nick's Class)는 다항 크기와 다항로그 깊이를 가진 균일한 불 회로족으로 풀리는 문제들의 부류입니다; $\text{NC}^k$ 는 깊이를 $O(\log^k n)$ 으로 제한하는데, 이는 깊이가 많아야 $\log n$ 의 $k$ 제곱에 어떤 상수를 곱한 만큼만 자란다는 뜻입니다. 풀어서 말하면: NC는 정확히 "원리상 대규모로 병렬화 가능함"을 뜻하며, 다항 작업량이 극도로 얕은 의존 구조 안에 조직되어 있다는 것입니다. 그 정리: $n$ 개의 정점을 가진 방향 그래프의 반사·추이 폐쇄는 $\text{NC}^2$ 에서 계산 가능하다, 곧 다항 크기와 $O(\log^2 n)$ 깊이를 가진 회로로 계산 가능하다는 것입니다 [1]. 이 두 개의 로그는 방금 인용한 커널 안에서 그대로 눈에 보입니다: $\lceil \log_2 D \rceil$ 번의 제곱 단계가 있고, 각 단계는 하나의 불 행렬 곱인데, 그 $n$ 개 항에 대한 $\bigvee_j$ 자체가 깊이 $\lceil \log_2 n \rceil$ 인 균형 OR-트리입니다. 회로 균일성 조건을 포함한 이 정리의 증명은 이 권의 범위를 넘어섭니다; 대신 컴패니언이 시연하는 것은 그 메커니즘과 그 셈해진 대가, 곧 $\lceil \log_2 D \rceil$ 번의 조밀 곱 일정과 $n = 512$ 에서의 $10{,}270$ 배 작업 청구서입니다.

핵심은 그 거래를 거부한다

그렇게 학계 위계는 제곱됩니다. 그런데 왜 완전한 완성 계산법은 같은 방식으로 제곱될 수 없을까요? 그 깊이가 도달 가능성 깊이가 아니기 때문입니다. 2권의 EL 완성은 두 종류의 상태, 곧 개념 레이블 $S(X)$ ( $X$ 의 도출된 상위개념)와 역할 엣지 $(X, Y) \in R(r)$ 를 유지하며, 그 규칙들은 한 종류를 읽어 다른 종류를 씁니다. 모듈은 이 메커니즘을 이미 2권 정규형에 있는 TBox인 $k$ -단 교대 사다리(alternation ladder) 안에 고립시킵니다(work_depth.py, 196–212행):

    axioms: list[tuple] = [("nf1", "A0", "M0")]
    for i in range(k):
        axioms.append(("nf3", f"M{i}", "r", f"B{i}"))
        axioms.append(("nf4", "r", f"B{i}", f"M{i + 1}"))

서술 논리(description logic, DL) 구문으로는: $A_0 \sqsubseteq M_0$ ; 그런 다음 각 단 $i$ 마다, $M_i \sqsubseteq \exists r.B_i$ (읽는 법: 모든 $M_i$ 는 $B_i$ 안에 $r$ -후속자를 가지므로, 레이블 $M_i$ 가 역할 엣지를 방출합니다)이고 $\exists r.B_i \sqsubseteq M_{i+1}$ ( $B_i$ 안에 $r$ -후속자를 가지는 것은 무엇이든 $M_{i+1}$ 이므로, 그 엣지가 다음 레이블을 산출합니다)입니다. 포화 커널은 완성 규칙들의 록스텝 파동 버전이며, 매 파동이 얼어붙은 이전 상태 위에서 CR1, CR3, CR4 전부를 발동시킵니다(work_depth.py, 245–291행): CR1은 원자적 포섭 관계를 레이블로 전파하고, CR3은 $A \sqsubseteq \exists r.B$ 를 만족하는 레이블 $A \in S(X)$ 를 엣지 $(X, B) \in R(r)$ 로 바꾸며, CR4는 $B \in S(Y)$ 이고 $\exists r.B \sqsubseteq C$ 를 만족하는 엣지 $(X, Y) \in R(r)$ 를 레이블 $C \in S(X)$ 로 바꿉니다. 개념 $A_0$ 에서 그 의존 관계를 따라가 봅시다: 레이블 $M_{i+1} \in S(A_0)$ 은 오직 CR4가 엣지 $(A_0, B_i)$ 를 읽어야만 만들어질 수 있고, 그 엣지는 오직 CR3이 레이블 $M_i \in S(A_0)$ 을 읽어야만 만들어질 수 있습니다. 새 레이블 하나마다 CR3 파동 하나와 CR4 파동 하나가 들고, 씨앗 레이블은 CR1 파동 하나가 들므로, 가장 깊은 사실인 $M_k \in S(A_0)$ 은 파동 $2k + 1$ 에 도착합니다. 모듈은 정확히 그 사실을 단언하며, 2권의 el_completion.complete 오라클과 사실 하나하나까지 정확히 일치함도 함께 단언합니다(458–460행).

이제 이 깊이를 앞 절의 깊이와 갈라놓는 핵심을 짚어 봅시다. 이 사다리가 도출하는 역할 그래프는 이분(bipartite)입니다: 모든 엣지는 주어(subject, $A_0$ 또는 어떤 $M_i$ )에서 어떤 $B_j$ 로 향할 뿐, 어떤 엣지도 $B_j$ 에서 나가지 않으므로, 두-엣지 경로 자체가 아예 존재하지 않습니다. 이 그래프의 진짜 추이 폐쇄는 쌍을 하나도 더하지 않으며, 모듈은 바로 그것을 단언합니다(463–464행). 커밋된 출력:

[3] the non-squarable core: the k=5 alternation ladder
    (A0 ⊑ M0;  Mi ⊑ ∃r.Bi;  ∃r.Bi ⊑ M(i+1)) — wave t+1's rule
    firing needs wave t's LABEL, interleaved with brand-new edges
    lockstep fixpoint == el_completion oracle: 68 facts in 11 waves (2k+1)
    the derived role graph is bipartite: transitive closure adds 0
    pairs — diameter 1, yet depth 11: the depth is NOT reachability

지름 $1$ 인 역할 그래프가 $11$ 번의 순서 지어진 파동을 강제했습니다. 그 깊이는 사실 종류 사이의 교대 안에 살고 있으며, 이는 정확히 반복 제곱이 볼 수 없는 구조입니다. 제곱은 하나의 관계 안에서 경로를 가속할 뿐이고, 이 사다리는 결코 한 엣지보다 긴 경로를 키우지 않기 때문입니다.

상수-라운드 허수아비: 미달과 초과

혹시 제곱을 좀 더 영리하게 적용하기만 하면 되지 않을까요? 모듈은 그래도 상수 깊이를 유지하는 가장 영리한 일정, 곧 허수아비 naive_squared_pipeline을 만듭니다(304–355행): (1) 제곱으로 원자적-포섭 그래프를 닫습니다(정확합니다: 이것이 바로 도달 가능성 조각입니다), (2) 완전히 병렬적인 CR3 한 차례, (3) 제곱으로 각 역할 행렬 $R(r)$ 을 추이적으로 닫습니다, (4) 완전히 병렬적인 CR4 한 차례, (5) 포섭 그래프를 다시 닫습니다. 다섯 라운드, 사례와 무관한 상수, 각 라운드는 다항로그 깊이입니다: 제곱 원시 연산으로 지어진 어떤 상수-라운드 일정이든 반드시 이런 모습이어야 합니다. (다항로그 개수의 교대 라운드를 허용받은 일정이라면 이 $k = 5$ 사다리는 깨뜨리겠지만, 단의 개수가 그 라운드 예산을 넘어서는 사다리에서는 똑같은 방식으로 실패합니다; 어떤 모양이든 다항로그-깊이 일정은 통하지 않는다는 주장은 다음 절의 조건부 정리이지, 장치 하나가 보여 줄 수 있는 것이 아닙니다.) 이는 가능한 두 방향 모두에서 실패하며, 모듈은 각 실패를 정확히 단언합니다.

사다리 위에서는 미달합니다. CR3 한 차례에 이어 CR4 한 차례는 각 의존 사슬을 정확히 레이블-엣지 한 쌍만큼만 전진시키는데, 고정점은 그런 교대를 $k$ 번 필요로 합니다. 다섯 라운드가 무엇을 놓치는지 세어 봅시다: $A_0$ 에서는 레이블 $M_2, \ldots, M_k$ 와 엣지 $(A_0, B_1), \ldots, (A_0, B_{k-1})$ 로, $2(k-1)$ 개의 사실입니다; 각 $M_i$ 에서는 레이블 $M_{i+2}, \ldots, M_k$ 와 엣지 $(M_i, B_{i+1}), \ldots, (M_i, B_{k-1})$ 로, $2(k - 1 - i)$ 개의 사실이며, 이를 $i = 0, \ldots, k-1$ 에 걸쳐 합하면 $2 \cdot k(k-1)/2$ 가 됩니다. 총합은

2(k-1) + 2\,\frac{k(k-1)}{2} \;=\; 2\left((k-1) + \frac{k(k-1)}{2}\right),

이며, $k = 5$ 에서는 $2(4 + 10) = 28$ 입니다. 모듈은 허수아비의 출력이 참값의 엄격한 부분집합임을 단언하고, 놓친 개수가 정확히 이 공식과 같음을 단언하며, 가장 깊은 레이블 $A_0 \sqsubseteq M_5$ 가 그 놓친 것들 가운데 있음을 단언합니다(468–472행): 참인 $68$ 개 중 $40$ 개의 사실만 도출됩니다.

두 번째 장치 위에서는 초과하며, 이쪽이 더 나쁩니다. 두-홉 TBox는 $X \sqsubseteq \exists r.Y$ , $Y \sqsubseteq \exists r.Z$ , $\exists r.Z \sqsubseteq C$ 입니다(215–221행). 참된 완성은 $C \in S(Y)$ 만을 도출합니다: CR4는 역할 엣지 하나만을 통해 살펴보며, $X \sqsubseteq \exists r.\exists r.Z$ 는 $X \sqsubseteq \exists r.Z$ 를 함의하지 않는데, EL의 역할들은 명시적인 사슬 공리 없이는 합성되지 않기 때문입니다. 의미론은 세 원소짜리 반례 모델로 이를 구체적으로 보여 줍니다: 정의역 $\{x, y, z\}$ 에 $r = \{(x,y), (y,z)\}$ , $X = \{x\}$ , $Y = \{y\}$ , $Z = \{z\}$ , $C = \{y\}$ 를 취합니다. 세 공리 모두 성립하지만( $x$ 는 $Y$ 안에 $r$ -후속자를 가지고, $y$ 는 $Z$ 안에 하나를 가지며, $Z$ 안에 $r$ -후속자를 가지는 유일한 원소는 $y$ 이고 $y \in C$ 입니다), $x \notin C$ 이므로 $X \sqsubseteq C$ 는 함의되지 않습니다. 허수아비의 단계 (3)은 $R(r)$ 을 도달 가능성 관계처럼 다루어 엣지 $(X, Z)$ 를 지어내고, 단계 (4)는 그로부터 $C \in S(X)$ 를 도출합니다. 모듈은 그 초과분이 정확히 이 두 사실이며 그 밖에는 아무것도 없음을 단언합니다(480–484행):

    two-hop gadget (X ⊑ ∃r.Y, Y ⊑ ∃r.Z, ∃r.Z ⊑ C): squaring R(r)
    invents the edge r(X, Z) and then the UNSOUND label X ⊑ C:
    overshoot = [('R', 'r', 'X', 'Z'), ('S', 'X', 'C')]  (EL derives C only at Y)

이 반례가 곧 논증입니다: 소박한 역할-행렬 제곱은 옳은 폐쇄의 더 느리거나 더 빠른 버전이 아니라, 틀린 폐쇄를 계산합니다. 완전한 계산법 안에서는, 포섭 선순서에 그토록 잘 통했던 로그-깊이 매입이 그저 비싸기만 한 것이 아닙니다: 이 장치 위에서는 불건전하며, 다음 절의 정리에 의해 NC = P가 아닌 한 일반적으로도 이용 불가능합니다.

규율을 지키며 이름 붙이는 벽

사다리는 하나의 메커니즘을 보여 주며, 정리는 그 메커니즘이 장난감 하나만의 인공물이 아니라고 말해 줍니다. 여기서 관련된 개념은 P-완전성(P-completeness)입니다: 어떤 문제가 PTIME(다항 시간에 풀 수 있음) 안에 있고, 어려운 부분을 몰래 들여오지 않을 만큼 약한 축약(로그 공간 축약) 아래에서 모든 PTIME 문제가 그것으로 환원될 때, 그 문제는 P-완전입니다. P-완전 문제는 복잡도 이론에서 "본질적으로 순차적"인 후보들입니다: 단조 회로값 문제, 혼 충족 가능성(Horn satisfiability), 데이터로그 폐쇄가 모두 P-완전이며, 이 가운데 어느 하나라도 다항로그-깊이·다항-작업량 병렬 알고리즘을 허용한다면, 모든 PTIME 문제가 그렇게 되어 NC = P로 붕괴할 것입니다 [2]. 이 조건문은 정확하게 진술되어야 합니다: 어떤 PTIME-완전 문제도 NC = P가 아닌 한 NC 안에 있지 않다. NC = P인지는 열린 문제입니다; 한 단계 아래에서 P ≠ NP와 같은 구조적 역할을 하는 보편적인 실무 추측은 그 붕괴가 일어나지 않는다는 것입니다 [2]. 같은 벽은 신경망 쪽 얼굴도 지니고 있으며, 여기서 미리 보여 주고 다음 장에서 발전시킵니다: 고정-깊이·로그-정밀도 트랜스포머는 다항 크기·상수-깊이 문턱 회로의 부류인 균일 TC⁰ 안의 함수만을 계산하므로, 그 계층 구조가 붕괴하지 않는 한 유한-깊이 병렬 스택은 P-완전 포화를 계산할 수 없습니다 [3]. 서술적 복잡도(descriptive complexity)는 이 모든 탑을 논리학에 묶어 주며, 왜 도달 가능성 조각이 그 벽을 피해 갔는지를 설명해 줍니다: 1차 논리는 상수 병렬 깊이에 대응하고, 추이 폐쇄 연산자로 확장된 1차 논리는 NC² 안에 있는 부류인 비결정론적 로그 공간을 포착합니다 [4]; 논리적으로 말해, 도달 가능성은 추이 폐쇄 연산자 하나만큼만 상수 깊이에서 떨어져 있습니다. 완성 핵심은 그렇지 않습니다: 일반 TBox를 갖춘 EL의 포섭은 PTIME-완전인데(소속, 곧 다항 시간 완성 알고리즘은 [5]의 정리입니다; 어려움 쪽은 EL의 일반 개념 포함이 명제 혼 절을 그대로 부호화하고 혼 충족 가능성이 P-완전이기 때문에 성립합니다 [2]), 1권 전방 연쇄기의 언어인 데이터로그 폐쇄 역시 PTIME-완전입니다 [2].

이 권의 들여온-이론 관행이 온전히 적용됩니다. 위의 정리들은 증명되지 않고 인용될 뿐입니다; 그 증명들(PTIME 문제들 사이의 축약, 회로 균일성, 서술적 특징 부여)은 이 권의 범위를 넘어섭니다. 그리고 컴패니언은 증명하는 대신 시연합니다: 유한한 사례 하나는 상수-라운드 제곱 일정을 무너뜨리는 사실 종류 사이의 교대라는 그 메커니즘을 보여 줄 수 있지만, 어떤 유한한 사례도 NC ≠ P를 증명할 수는 없으며, 모듈 자신의 문서 문자열도 그렇게 말합니다(work_depth.py, 44–48행). 정직한 역할 분담은 이렇습니다: 장난감은 벽이 왜 그 자리에 있는지를 보여 주고, 정리는 그 벽이 어디에나 있음을 보여 줍니다.

절단 법칙: 깊이가 사들이는 것

도달 가능성의 협상 가능한 깊이와 핵심의 협상 불가능한 깊이 사이에는 이후의 모든 장이 계속 돌려 볼 다이얼이 놓여 있습니다: 파동 커널을 어쨌든 돌리되, 사례의 참된 도출 깊이가 무엇이든 상관없이 $L$ 라운드라는 고정 예산 뒤에 멈추는 것입니다. 이 절은 그 도출 깊이를 다시 $D$ 라고 부릅니다(도달 가능성 조각에서는 그 깊이를 지름이 정했지만, 사다리에서는 역할 그래프의 지름이 $1$ 인데도 그 깊이는 파동 개수 $2k + 1 = 11$ 입니다). 커널은 그 예산을 매개변수로 받으며, 그 메커니즘 전체는 다음의 루프 조건입니다(work_depth.py, 266행):

    while L is None or waves < L:

두 가지 성질이 뒤따르며, 하나는 여기서 증명되고 둘 다 모듈에서 단언됩니다. 첫째, 모든 예산에서의 건전성입니다. 파동 단계는 단조 연산자 $T$ 의 한 사례입니다: 그것은 하나의 상태(레이블과 엣지 사실들의 집합)를, 그 상태에 어떤 규칙이 그로부터 도출하는 사실 전부를 더한 것으로 사상하며, 입력 상태를 넓히는 것이 규칙 발동을 무력화하지 않고 오직 새로운 것만 더하므로 단조입니다: $X \subseteq Y$ 이면 $T(X) \subseteq T(Y)$ 이며, 여기서 $\subseteq$ 는 "~의 부분집합이다"라고 읽습니다. 참된 폐쇄 $F$ 는 초기 상태 위에서 $T$ 의 최소 고정점이므로 $T(F) = F$ 입니다. 이제 예산에 대해 귀납해 봅시다. 초기 상태는 구성상 $F$ 안에 들어 있습니다. $t$ 번의 파동 뒤의 상태가 $F$ 안에 들어 있다면, $t + 1$ 번의 파동 뒤의 상태는 단조성에 의해 $T(\text{state}_t) \subseteq T(F) = F$ 입니다. 그러므로 모든 $L$ 에서, 절단된 실행 전부는 참값의 부분집합을 내놓습니다: 그 예산이 아무리 작아도 파동 예산이 거짓 사실을 도출하는 일은 결코 없습니다. 둘째, 완전성은 정확히 참된 깊이에서 도착합니다: $D$ 보다 적은 파동은 최단 도출이 깊이 $D$ 인 사실들을 담을 수 없습니다. 모듈은 모든 예산에서 정확한 부분집합 관계를 단언하고, $L$ 에 대한 단조성(예산이 늘어나도 사실을 결코 잃지 않음)을 단언하며, $D$ 보다 작은 모든 $L$ 에서 재현율이 엄격히 $1$ 미만임을 단언하고, $L = D$ 에서 재현율이 정확히 $1$ 임을 단언합니다(491–504행). 장부를 맞추는 한마디가 아래 표를 앞선 출력 블록과 화해시킵니다: 표의 분모가 사다리 고정점의 $68$ 이 아니라 $41$ 인 이유는, 재현율이 커널이 도출해야 하는 사실들 위에서 측정되기 때문입니다; $27$ 개의 초기화 레이블(모든 개념 $X$ 는 $S(X) = \{X, \top\}$ 로 시작합니다)은 $L = 0$ 에서 이미 존재하므로 도출 열과 참값 열 양쪽에서 제외됩니다(work_depth.py는 참값에서 $L = 0$ 상태를 뺍니다, 487–488행). 커밋된 곡선은, 참된 깊이 $D = 11$ 인 $k = 5$ 사다리 위에서("레버 B"는 SATORI 아키텍처 노트에서 빌려 온 컴패니언의 태그로, 정확히 이 고정-예산 움직임을 가리키며, VII부가 이를 다시 다룹니다):

[4] fixed-L truncation of the wave kernel (Lever B), true depth D = 11:
      L   derived / true      recall   sound (⊆ closure)?
    6 / 41        0.146   yes
   12 / 41        0.293   yes
   17 / 41        0.415   yes
   22 / 41        0.537   yes
   26 / 41        0.634   yes
   30 / 41        0.732   yes
   33 / 41        0.805   yes
   36 / 41        0.878   yes
   38 / 41        0.927   yes
   40 / 41        0.976   yes
   41 / 41        1.000   yes

각 열을 따로 읽으십시오. 서로 다른 것을 실어 나르기 때문입니다. 재현율 열은 $0.146$ 에서 $1.000$ 까지 올라가지만, 건전성 열은 전혀 움직이지 않습니다. 깊이가 사들이는 것은 재현율이지, 결코 건전성이 아닙니다. 이 문장이 이 장의 수출품이며, 그것이 중요한 이유는 그 오류 방향이 3권과 4권이 가르쳐 준 것과 정확히 반대이기 때문입니다. 절단된 커널은 오직 부작위(不作爲, omission)로만 실패합니다: 도출 가능하지만 아직 도출되지 않은 사실인 거짓 음성이며, 정밀도는 그대로 남습니다. 임베딩 채점기는 작위(作爲, commission)로 실패합니다: 모든 후보가 점수를 받으며, 함의되지 않는 사실도 높은 점수를 받을 수 있어, 모든 것을 덮으면서도 정밀도를 대가로 치릅니다. VII부의 보정 이야기는 이 둘을 결코 혼동하지 않는 데 달려 있으므로, 이 대조는 그 자체의 표를 가질 만합니다:

	D보다 낮은 예산 L에서 절단된 커널	임베딩 채점기(3–4권)
무엇을 내놓는가	깊이가 많아야 L인 도출을 가진 사실만	모든 후보 사실에 대한 점수
오류 방향	거짓 음성만(부작위)	거짓 양성 가능(작위)
저하되는 지표	재현율(사다리 위 $L = 1$ 에서 $0.146$ )	정밀도(불건전한 고득점)
살아남는 지표	정밀도: 내놓은 사실은 모두 참	커버리지: "아직 도출되지 않음"이 결코 없음
고치는 방법	라운드를 더 돌림; 커널은 언제든 멈출 수 있고 단조적임	보정, 기권, 검증(VII부)

삼단 규모 확장 법칙

이 장의 조각들은 이제 세 단으로 이루어진 하나의 법칙으로 조립되며, 각 단은 추론의 한 조각과 그 조각에 대해 알려진 어떤 커널이든 달성하는 가장 얕은 깊이를 짝짓습니다. 첫 번째 단은 구체화 대 재작성에서 물려받습니다: 1차-재작성 가능한 조각들(DL-Lite 차선)에서는, 질의를 재작성한 다음 그 재작성을 데이터 위에서 직접 평가함으로써 답하며, 폐쇄는 전혀 계산되지 않습니다; 1차 논리 평가는 서술적 관점의 상수-병렬-깊이 체제입니다 [4]. 두 번째 단은 이 장의 제곱 차선입니다: 학계 포섭 선순서 같은 도달-가능성-모양의 조각들은 반복 제곱으로 로그 깊이에서 닫히며, 조밀한 작업을 대가로 치릅니다. 세 번째 단은 파동 차선입니다: 레이블과 엣지가 교대하는 논리곱 완성 핵심은 도출 깊이 $D$ 에 비례하는 깊이, 기호로는 $\Theta(D)$ ( $D$ 의 상수배로 위아래가 모두 묶인다는 뜻)에서 돌아가며, 벽은 NC = P가 아닌 한 어떤 다항로그-깊이·다항-작업량 일정도 그것을 대체할 수 없다고 말합니다.

단계	조각의 모양	커널	깊이	작업	근거
재작성	FO-재작성 가능한 질의(DL-Lite 차선)	질의를 재작성함; 데이터를 결코 닫지 않음	질의당 상수	재작성된 질의의 평가에 비례	앞 장의 커밋된 시연; FO = 상수 병렬 깊이 [4]
제곱	도달-가능성-모양의 조각(원자적 ⊑-선순서)	$I \vee M$ 의 반복 제곱	$\lceil \log_2 D \rceil + 1$ 번의 라운드	라운드당 $n^2(2n-1)$ , 조밀함	위의 커밋된 표; NC²에 있는 TC [1]
파동	논리곱 완성 핵심(레이블과 엣지의 교대)	준순진 록스텝 파동	$\Theta(D)$ 번의 라운드(사다리 위에서는 $2k+1$ )	희소하며 출력에 비례함	커밋된 교대 반례; PTIME-완전(소속 [5], 혼-부호화 어려움 [2]), NC = P가 아닌 한 다항로그 깊이 없음 [2]

세 조각을 위한 세 차선: 상수-깊이 재작성, 조밀한 작업으로 사들인 로그-깊이 제곱, 그리고 NC = P 벽 뒤에 있는 선형-깊이 교대 핵심이며, 그 아래에는 재현율만을 맞바꾸고 건전성은 결코 맞바꾸지 않는 절단 다이얼이 있습니다. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

이 표는 이 권이 앞으로 계속 강제할 독법 규율 하나를 부여합니다: 추론기의 확장성은 시스템의 성질이기에 앞서 조각의 성질입니다. "시스템 X가 온톨로지 Y를 Z초 만에 구체화했다"고 말하는 벤치마크 결과는 그 조각의 이름이 붙기 전까지는 해석 불가능합니다. 선순서-모양의 TBox 위에서 날아다니는 바로 그 엔진이 교대-모양의 TBox 위에서는 기어가거나 절단해야 하기 때문입니다. 커밋된 도달 가능성 표의 지름 열과 사다리의 $2k+1$ 번의 파동은 서로 다른 조각의 옷을 입은 같은 숫자이며, 오직 그 조각만이 어떤 커널이 애초에 자격을 갖추는지를 말해 줍니다.

다이얼이 다시 나타나는 곳

절단 법칙은 이 모듈만의 진기한 사실이 아닙니다; 그것은 이 권의 나머지 부(Part)들을 떠받치는 문장이며, 이제 그 각각의 재등장을 정확히 이름 붙일 수 있습니다. 첫째, 고정-깊이 신경망은 절단된 커널입니다: $L$ 개 층으로 이루어진 스택은 그 깊이가 빌드 시점에 고정된 계산이므로, 어떤 반복적 포화를 흉내 내라고 요구받든 많아야 그것의 $L$ 번의 파동만을 표현할 수 있습니다. 다음 장은 이를 트랜스포머에 대해 정확하게 만드는데, 거기서는 TC⁰ 포함 관계 [3]가 여기서 NC = P 조건문이 했던 역할을 합니다. 둘째, 사고 사슬은 깊이를 순차적 디코딩 단계로 바꿉니다: 자신의 맥락에 중간 결론을 써넣고 그것을 다시 읽어 들이는 모델은 추론 시점에 추가적인 파동을 돌리고 있는 것이며, 층 대신 토큰으로 깊이 값을 치릅니다; 사고 사슬 장은 이 변환을 이 권의 계측 도구로 측정합니다. 셋째, SATORI 커널의 고정-L 펼침(VII부, 기호 어텐션 장)은 어텐션 가중치의 옷을 입은 이 장의 법칙입니다: 완성 파동 하나당 기호-어텐션 레이어 하나씩이 빌드 시점의 $L$ 에서 절단되며, 재현율-대-L 표는 위의 커밋된 곡선을 신경망 아키텍처 안에서 다시 측정한 것이고, 지켜야 할 보증도 같습니다: 모든 예산에서의 건전성입니다.

미해결 부분

이 장은 두 개의 축을 세고 하나의 거래에 값을 매겼지만, 정직한 회계에는 세 개의 축이 있으며, 그것이 바로 제목이 트릴레마라고 말하는 이유입니다. 메모리는 모듈이 오직 암묵적으로만 셈한 축입니다: 제곱 커널의 중간 결과 $A_t$ 는 폐쇄가 아무리 희소하든 상관없이 조밀한 $n \times n$ 행렬이며, 매 제곱은 입력과 비교하기 전에 완전히 조밀한 곱을 구체화합니다. 모듈의 $n = 512$ 에서는 중간 결과당 $262{,}144$ 개의 칸으로 사소하지만, SNOMED CT 규모의 개념 수십만 개를 가진 $n$ 에서는 중간 결과당 $10^{11}$ 개 정도의 칸이 되어, $n^3$ 남짓한 작업량이 인내심을 소진시키기 훨씬 전에 메모리를 소진시킵니다. 제곱의 조밀한 중간 결과는 작업량을 폭발시키기 전에 메모리를 먼저 폭발시키므로, 진짜 공학적 프론티어는 작업, 깊이, 상주 공간(residency) 사이의 삼자 협상이며, 모듈의 깔끔한 두-열짜리 표는 일부러 그것을 담아내지 않습니다(모듈의 문서 문자열은 조밀 커널이 장난감 규모의 $n$ 에서 하는 float32 행렬 곱일 뿐, 진짜 준입방(subcubic) 알고리즘이 아님을 인정합니다; work_depth.py, 44–48행). 둘째, 손익분기점은 어떤 점근적 분석도 담아내지 못하는 상수들이 지배합니다: 커밋된 비율( $n = 8$ 에서 $78.4$ 배, $n = 512$ 에서 $10{,}270$ 배)은 반환 연산을 셈한 것이지만, 벽시계 손익분기점은 메모리 대역폭, 희소성 구조, 배치 모양에 좌우되며, 이것이 바로 모듈이 셈해진 연산은 보고하되 타이밍 인쇄는 거부하는 정확한 이유입니다(50–51행). 셋째, 가장 열려 있는 것: 이 장의 모든 것은 고정된 일정, 곧 전부-파동이든 전부-제곱이든 고정 예산 $L$ 이든 그런 일정을 썼습니다. 깊이-적응적 추론기라면 사례가 필요로 하는 곳에 라운드를 쓸 것입니다: 이 TBox는 선순서-모양이니(제곱하라) 저 TBox는 교대-모양이니(파동을 돌려라)를 즉석에서 감지하거나, 프런티어가 공집합이라는 증명서와 함께 절단된 실행을 일찍 멈추는 것입니다. 사례별 깊이 증명서를 갖춘 언제든-멈출 수 있는 커널은 지금까지 규모 있게 측정된 적이 어디에도 없으며, 이 장의 표들은 정확히 그런 측정에 필요한 종류의 계측 도구입니다.

왜 중요한가

이 장은 IV부가 이 권을 V부에 넘겨주는 축입니다. 이 장 이전의 모든 것은 추론 한 라운드를 어떻게 값싸게 만들지를 물었습니다: 배치화, 델타, 텐서, 재작성. 이 장은 몇 번의 라운드가 순서대로 일어나야 하는지를 물었고, 그 답이 논리적 조각의 성질이며, 복잡도 이론의 표준적인 추측 하나가 그것을 방어하고, 오직 한 가지 화폐, 곧 재현율로만 협상 가능하다는 것을 밝혔습니다. 이 재구성은 연구자에게 구체적인 일을 해 줍니다. 조각이 명시되지 않은 규모 확장 주장은 주장이 아니라고 말해 줍니다; 추론 벤치마크 위에서 평가되는 고정-깊이 아키텍처는 벤치마크의 도출 깊이를 측정함으로써 훈련 이전에 알 수 있는 천장을 가진다고 말해 줍니다; 그리고 한정된 깊이 예산을 안전하게 쓰는 방법은 절단된 커널의 방식, 곧 건전성을 지키고 재현율을 내주는 것이라고 말해 줍니다. 왜냐하면 그 반대의 거래, 곧 커버리지를 지키고 정밀도를 내주는 거래는 나중에 보정 기계 장치가 고쳐야만 하는 것이기 때문입니다. 이 시리즈의 궤적에서, "깊이는 재현율을 사되 결코 건전성을 사지 않는다"는 문장은 트랜스포머 천장, 사고 사슬, SATORI 커널이 모두 그 위에 서 있는 다리입니다; 재현율 열이 오르는 동안 건전성 열이 고정된 채로 있는 것을 지켜본 독자는 그 문장을 슬로건이 아니라 측정된 사실로서 소유하게 됩니다.

핵심 용어

작업(work): 계산이 수행하는 연산의 총 개수로, 모든 프로세서에 걸쳐 합산한 값입니다; 벽시계가 무엇을 말하든 에너지와 하드웨어로 누군가 항상 치르는 청구서입니다.
깊이(depth): 각 연산이 앞선 연산의 결과를 필요로 하는 연산 사슬 중 가장 긴 것의 길이입니다; 프로세서가 몇 개든 실행 시간의 하한이 됩니다.
브렌트의 스케줄링 경계(Brent's scheduling bound): $p$ 개의 프로세서가 있을 때, 탐욕적 스케줄링은 작업량 $W$ 와 깊이 $D$ 를 가진 계산을 많아야 $W/p + D$ 의 시간에 실행하여, 두 하한 $W/p$ 와 $D$ 를 그 합까지 동시에 맞춥니다.
준순진(파동) 폐쇄(semi-naive closure): 매 라운드마다 오직 가장 새로운 사실들만을 기본과 조인하는 프런티어 규율입니다: 깊이 $D - 1$ 번의 라운드, 희소하고 출력에 비례하는 작업량, $n$ -사슬 위에서 $(n-1)^2$ 번의 셈해진 연산입니다.
반복 제곱(repeated squaring): $I \vee M$ 을 제곱하여 도달 가능성을 닫는 방법입니다: 깊이 $\lceil \log_2 D \rceil$ 번의 생산적인 라운드에 확인용 라운드 하나를 더한 것이며, 라운드당 $n^2(2n-1)$ 번의 조밀한 셈해진 연산이 듭니다.
NC / NC²: 다항 크기와 다항로그 깊이를 가진 균일한 회로족으로 풀리는 문제들입니다; NC²는 깊이 $O(\log^2 n)$ 을 허용하며, 추이 폐쇄가 그 안에 삽니다.
P-완전성(P-completeness): PTIME에 속함과 동시에 로그 공간 축약 아래에서 PTIME 전체에 대해 어려움을 뜻합니다; 어떤 P-완전 문제에 대한 다항로그-깊이·다항-작업량 알고리즘이든 NC = P로 붕괴시킬 것이므로, 이는 "본질적으로 순차적"이라는 개념의 형식적 정의입니다.
교대 사다리(alternation ladder): 레이블 도출과 엣지 도출이 엄격하게 맞물려, 지름 1인 역할 그래프 위에서 $2k+1$ 번의 파동을 강제하는 장치입니다: 도달 가능성 깊이 없는 도출 깊이입니다.
절단 법칙(truncation law): $L$ 라운드 뒤에 멈춘 단조 포화 커널은 모든 $L$ 에서 건전하며 정확히 $L = D$ , 곧 사례의 도출 깊이에서 완전합니다: 깊이는 재현율을 사되 결코 건전성을 사지 않습니다.
지름 대 도출 깊이(diameter versus derivation depth): 제곱이 압축할 수 있는 그래프 양과 제곱이 압축할 수 없는 의존 관계 양의 대비입니다; 이 둘을 혼동하는 것이 바로 허수아비의 실수입니다.

이 장이 이끄는 곳

트릴레마는 이 권이 직접 작성했고 검사할 수 있는 커널들 위에서 실행되었습니다. 다음 장은 같은 계측 도구를 아무도 손으로 작성하지 않는 커널에 겨눕니다: 바로 트랜스포머이며, 그 깊이는 설정 파일이 커밋되는 날 고정됩니다. 트랜스포머 깊이의 천장은 고정-깊이·로그-정밀도 어텐션 스택에 대한 TC⁰ 포함 관계를 진술하고, 이를 여기서 만난 P-완전성 벽에 연결한 다음, 이 권이 들여온 정리를 다룰 때마다 항상 하는 일을 합니다: 이론이 예측하는 그대로 천장이 작동함을 보여 주는 커밋된 장난감을 짓는 것입니다. 곧 도출 깊이가 자신의 층 수를 넘어서는 사례에서 실패하는 고정-깊이 모델이며, 절단 법칙의 재현율 곡선이 예전에 손실 곡선이 있던 자리에 다시 나타납니다.

컴패니언 코드: examples/frontier/work_depth.py는 세 단계 전부를 셈해진 작업과 깊이와 함께 구현합니다: 준순진 폐쇄와 제곱 폐쇄는 사슬 계열과 학계 ⊑-선순서 위에서 독립적인 DFS 참조에 맞서 단언되고, 교대 사다리와 두-홉 장치는 2권의 el_completion 오라클에 맞서 단언되며, 상수-라운드 허수아비의 미달과 초과는 정확히 단언되고, 고정-L 절단 표는 모든 예산에서 건전함이 단언됩니다. 이 장의 모든 숫자를 재현하려면 python3 examples/frontier/work_depth.py를 실행하십시오.

이 장에서 다루는 내용​

세어서 정의하는 작업과 깊이​

두 가지 방식으로 닫히는 도달 가능성​

파동 커널: 적은 작업으로 이루어지는 D − 1번의 라운드​

반복 제곱: 많은 작업으로 이루어지는 ⌈log₂ D⌉번의 라운드​

핵심은 그 거래를 거부한다​

상수-라운드 허수아비: 미달과 초과​

규율을 지키며 이름 붙이는 벽​

절단 법칙: 깊이가 사들이는 것​

삼단 규모 확장 법칙​

다이얼이 다시 나타나는 곳​

미해결 부분​

왜 중요한가​

핵심 용어​

이 장이 이끄는 곳​