Linear 연산 합성 실험 결과 분석

1. 실험 목적

이번 실험은 두 개의 연속된 Linear 연산을 하나의 Linear 연산으로 합성했을 때 다음 사항을 확인하기 위한 것이다.

1. 원래 연산과 합성된 연산의 출력이 동일한가
2. 중간 차원 축소로 생긴 정보 손실이 합성 후에도 유지되는가
3. 출력 차원이 다시 커져도 원래 입력 정보가 복구되지 않는가
4. 이러한 성질을 정적 의미 분석기가 정확하게 추적하는가

실험에 사용한 연산 구조는 다음과 같다.

입력 4차원
   ↓
Linear 1: 4 → 2
   ↓
Linear 2: 2 → 4
   ↓
출력 4차원

이를 하나의 연산으로 합성하면 겉보기에는 다음과 같다.

Fused Linear: 4 → 4

그러나 내부적으로는 반드시 2차원 병목을 거쳤으므로, 합성된 가중치 행렬의 rank는 최대 2이다.

---

2. 연산 정의

첫 번째 Linear 연산은 다음과 같다.

y = xW1 + b1

여기서:

W1 shape = (4, 2)
b1 shape = (2,)

두 번째 Linear 연산은 다음과 같다.

z = yW2 + b2

여기서:

W2 shape = (2, 4)
b2 shape = (4,)

두 식을 합치면:

z = (xW1 + b1)W2 + b2

분배하면:

z = x(W1W2) + b1W2 + b2

따라서 합성된 파라미터는 다음과 같다.

W_fused = W1 @ W2
b_fused = b1 @ W2 + b2

실제 계산 결과:

W_fused =
[[ 1.  2.  0. -1.]
 [ 0.  1.  3.  2.]
 [ 1.  3.  3.  1.]
 [ 2.  3. -3. -4.]]

b_fused =
[ 1.5  -0.5  -2.75 -0.5 ]

---

3. Shape inference 결과

입력 텐서의 shape는 다음과 같다.

(2, 4)

여기서 2는 batch 크기이고, 4는 feature 차원이다.

각 연산 이후 shape는 다음과 같이 추론됐다.

입력:             (2, 4)
Linear 1 이후:    (2, 2)
Linear 2 이후:    (2, 4)
Fused Linear 이후: (2, 4)

Shape inference는 정상적으로 동작했다.

합성 전과 합성 후의 외부 입력·출력 shape도 동일하다.

원래 연산: 4 → 2 → 4
합성 연산: 4 → 4

하지만 여기서 주의해야 할 점이 있다.

shape preservation ≠ information preservation

출력 feature 수가 다시 4가 되었다고 해서, 중간에 손실된 입력 정보가 복구되는 것은 아니다.

---

4. 원래 연산과 합성 연산의 동등성

입력은 다음과 같다.

x =
[[ 1.   2.   3.   4. ]
 [-1.   0.5  2.  -2. ]]

첫 번째 Linear 연산의 출력:

middle =
[[12.5  0. ]
 [-2.5  3.5]]

원래 두 연산을 순서대로 실행한 결과:

original_output =
[[ 13.5   24.5    0.25 -10.5 ]
 [ -1.5   -2.    10.75  11.5 ]]

합성된 Linear 하나를 실행한 결과:

fused_output =
[[ 13.5   24.5    0.25 -10.5 ]
 [ -1.5   -2.    10.75  11.5 ]]

두 결과의 최대 절댓값 차이는 다음과 같다.

0.0

그리고:

All close: True

따라서 이번 입력에서는 원래 연산과 합성 연산이 수치적으로 완전히 동일하다.

이는 다음 rewrite가 올바르다는 것을 확인한다.

Linear(W1, b1)
→ Linear(W2, b2)

를:

Linear(W1W2, b1W2 + b2)

로 치환할 수 있다.

단, 이 합성은 두 Linear 사이에 ReLU, GELU, Dropout 같은 비선형 연산이 없을 때만 가능하다.

예를 들어 다음은 일반적으로 합성할 수 없다.

Linear → ReLU → Linear

ReLU 때문에 전체 연산이 단일 affine transformation으로 표현되지 않기 때문이다.

---

5. Parameter count 변화

합성된 Linear 분석 결과의 parameter count는 다음과 같다.

parameter_count: 20

합성된 연산의 파라미터는:

가중치: 4 × 4 = 16
bias:   4
총합:   20

원래 두 Linear 연산의 파라미터 수는 다음과 같다.

첫 번째 Linear:

가중치: 4 × 2 = 8
bias:   2
총합:   10

두 번째 Linear:

가중치: 2 × 4 = 8
bias:   4
총합:   12

따라서 원래 연산 전체는:

10 + 12 = 22

이고, 합성 후에는:

20

이다.

이번 예제에서는 파라미터 수가 22개에서 20개로 감소했다.

그러나 Linear fusion이 항상 파라미터 수를 줄이는 것은 아니다.

일반적으로:

입력 차원 = I
중간 차원 = H
출력 차원 = O

라면 원래 가중치 수는:

I×H + H×O

이고, 합성 후 가중치 수는:

I×O

이다.

따라서 다음 조건에 따라 파라미터 수가 증가하거나 감소할 수 있다.

I×O < I×H + H×O

이면 감소하고,

I×O > I×H + H×O

이면 오히려 증가한다.

그러므로 실제 compiler pass에서는 수학적 합성 가능성뿐 아니라 파라미터 증가, 메모리 트래픽, 실행 latency도 함께 판단해야 한다.

---

6. Rank 분석

합성된 가중치 행렬의 shape는 다음과 같다.

(4, 4)

그러나 실제 matrix rank는 다음과 같다.

Concrete matrix rank: 2

구조적으로 추론한 rank upper bound 역시 다음과 같다.

Structural rank upper bound: 2

두 결과가 정확히 일치한다.

그 이유는 다음 rank 부등식 때문이다.

rank(W1W2) ≤ min(rank(W1), rank(W2))

또한 행렬 크기만 고려해도:

rank(W1) ≤ 2
rank(W2) ≤ 2

이므로:

rank(W1W2) ≤ 2

이다.

합성된 행렬은 4×4 정사각 행렬이지만 full rank인 4가 될 수 없다.

즉, 행렬의 외형만 보면 4차원 공간을 4차원 공간으로 보내지만, 실제 출력은 최대 2차원 부분공간에만 존재한다.

---

7. 특이값 분석

합성된 가중치 행렬의 singular values는 다음과 같다.

[6.9745, 5.41815, 0, 0]

4개의 singular value 중 2개만 0이 아니고, 나머지 2개는 0이다.

행렬의 rank는 0이 아닌 singular value의 개수이므로:

rank = 2

이다.

이를 기하학적으로 해석하면 다음과 같다.

입력은 4차원 공간에 존재하지만, 합성된 Linear 연산은 입력 공간의 두 방향만 출력에 반영한다.

나머지 두 방향으로 입력을 변화시켜도 출력은 변하지 않는다.

즉, 입력 공간에는 2차원의 null space가 존재한다.

Rank-nullity theorem에 따르면:

입력 차원 = rank + nullity

이므로:

4 = 2 + nullity

따라서:

nullity = 2

이다.

---

8. Null direction 실험

실제로 null space에 속하는 벡터 하나를 구한 결과:

v =
[ 0.896693  0.059237 -0.338389 -0.279152]

이 벡터는 다음 조건을 만족한다.

v @ W_fused ≈ 0

실제 출력:

v @ W_fused =
[0, 0, -0, 0]

잔차의 크기:

||v @ W_fused||₂ = 1.1920929e-07

정확히 0이 아닌 이유는 float32 부동소수점 계산 오차 때문이다.

수치적으로는 0으로 보아도 된다.

원래 입력:

x0 =
[1, 2, 3, 4]

null direction을 더한 입력:

x0 + v =
[1.896693, 2.059237, 2.661611, 3.720848]

두 입력은 명백히 다르다.

그러나 출력은 동일하다.

fused(x0) =
[13.5, 24.5, 0.25, -10.5]

fused(x0 + v) =
[13.5, 24.5, 0.25, -10.5]

최대 차이:

0.0

그 이유는 다음과 같다.

f(x0 + v)
= (x0 + v)W + b
= x0W + vW + b

여기서:

vW = 0

이므로:

f(x0 + v) = x0W + b = f(x0)

이다.

이 실험은 합성된 연산이 many-to-one이라는 사실을 직접 보여준다.

서로 다른 여러 입력이 동일한 출력으로 매핑된다.

---

9. Affine과 Linear의 구분

분석 결과에는 다음이 출력됐다.

linear: False
affine: True
nonlinear: False
algebraic_kind: affine
bias_enabled: True

이는 정확한 판정이다.

엄밀한 수학적 선형 변환은 다음 형태다.

f(x) = xW

선형 변환은 반드시 다음 조건을 만족한다.

f(0) = 0

하지만 bias가 존재하면:

f(x) = xW + b

이고:

f(0) = b

이므로 일반적으로 0이 아니다.

따라서 bias가 있는 Linear layer는 딥러닝에서는 흔히 Linear라고 부르지만, 수학적으로는 affine transformation이다.

그렇다고 비선형 연산인 것은 아니다.

따라서 다음 판정이 함께 성립한다.

linear: False
affine: True
nonlinear: False

---

10. Shape preservation과 정보 보존의 차이

분석 결과:

shape_preserving: True
dimension_effect: preservation
feature_dimension_effect: preservation

이 값은 입출력 feature 차원이 모두 4라는 의미다.

4 → 4

하지만 동시에:

irreversible: True
many_to_one: True
input_recoverable: False

이다.

두 판정은 모순이 아니다.

dimension_effect: preservation은 텐서 shape 관점의 판정이다.

입력 feature 수 = 4
출력 feature 수 = 4

그러나 정보론적·선형대수적 관점에서는 rank가 2이므로 실제 독립 정보 차원은 2에 불과하다.

즉:

표현 공간의 크기: 4차원
실제 도달 가능한 부분공간: 최대 2차원

이다.

따라서 framework에서는 다음 개념을 분리해서 다루는 것이 중요하다.

shape dimension
structural rank
information recoverability

Shape만 분석하면 이 연산을 잠재적으로 가역적인 4→4 변환으로 잘못 판단할 수 있다.

Structural rank metadata가 있어야 중간 병목으로 인한 정보 손실을 합성 이후에도 추적할 수 있다.

---

11. Semantic analysis 결과

분석기는 다음과 같이 판정했다.

structural_matrix_rank_upper_bound: 2
irreversible_guaranteed: True
potentially_input_recoverable: False
potentially_surjective: False
potentially_bijective: False
source_linear_count: 2

각 결과를 해석하면 다음과 같다.

11.1 structural_matrix_rank_upper_bound

value = 2
level = guaranteed

합성된 가중치 행렬의 rank는 구조적으로 2를 초과할 수 없다.

이 값은 현재 파라미터를 실제로 계산해서 얻은 값이 아니라, 원래 연산 구성에서 상속된 구조적 사실이다.

따라서 가중치 값이 바뀌더라도 rank가 2를 초과하지 않는다는 점이 보장된다.

---

11.2 source_linear_count

value = 2
level = guaranteed

현재 하나의 fused Linear가 원래 두 개의 Linear 연산을 대표한다는 의미다.

이는 단순한 디버깅 정보 이상의 역할을 할 수 있다.

예를 들어 compiler가 다음을 추적하는 데 사용할 수 있다.

몇 개의 원래 연산이 하나로 합쳐졌는가
fusion 이후 provenance가 무엇인가
비용 모델에서 kernel launch가 몇 번 감소했는가
semantic metadata가 어떤 연산들로부터 상속됐는가

---

11.3 irreversible

value = True
level = guaranteed

입력 feature dimension은 4지만 rank upper bound는 2다.

따라서 입력 전체를 출력에서 복구할 수 없다.

이 비가역성은 현재 가중치 값에 우연히 나타난 것이 아니라, 4→2 병목 구조 자체에서 발생한다.

---

11.4 many_to_one

value = True
level = guaranteed

입력 공간에 nontrivial null direction이 반드시 존재하므로, 서로 다른 입력들이 동일한 출력으로 매핑된다.

실험에서 실제로:

x0 ≠ x0 + v

이지만:

f(x0) = f(x0 + v)

임을 확인했다.

---

11.5 input_recoverable

value = False
level = guaranteed

출력만으로 원래 입력을 유일하게 복원할 수 없다.

최소 두 개 이상의 서로 다른 입력이 동일한 출력을 만들기 때문이다.

정확히는 null space가 2차원이므로, 하나의 출력에 대응하는 입력은 보통 다음과 같은 affine subspace를 이룬다.

x + Null(W)

즉, 입력 후보가 단지 두 개 존재하는 것이 아니라 연속적으로 무한히 많이 존재한다.

---

11.6 surjective

value = False
level = guaranteed

출력 공간은 4차원이지만 matrix rank가 최대 2이므로 모든 4차원 출력 벡터를 생성할 수 없다.

가능한 출력은 다음 형태다.

y = xW + b

여기서 xW는 최대 2차원 부분공간에 존재하고, bias는 그 공간을 평행 이동시킬 뿐 차원을 증가시키지 않는다.

따라서 reachable output set은 4차원 전체 공간이 아니라 최대 2차원의 affine subspace다.

---

11.7 bijective

value = False
level = guaranteed

Bijective이려면 다음 두 조건을 모두 만족해야 한다.

injective
surjective

하지만 현재 연산은:

many-to-one이므로 injective가 아니고
출력 전체 공간을 덮지 못하므로 surjective도 아니다

따라서 bijective일 수 없다.

---

12. Static structural fact와 observed fact의 차이

이번 실험에서는 두 종류의 rank 정보가 함께 확인됐다.

정적 구조 분석:

structural rank upper bound = 2
level = guaranteed

실제 파라미터 계산:

concrete matrix rank = 2
singular values = [6.9745, 5.41815, 0, 0]

첫 번째는 연산 구조만으로 얻은 보장이다.

두 번째는 현재 가중치 값을 실제로 검사한 관찰 결과다.

이번에는 둘이 같지만 항상 같은 것은 아니다.

예를 들어 structural rank upper bound가 4인 행렬도 실제 값이 특수하면 concrete rank는 3이나 2가 될 수 있다.

structural upper bound = 4
observed concrete rank = 2

이 경우 의미는 다음과 같다.

구조적으로는 full rank가 가능하지만,
현재 파라미터 값에서는 rank deficiency가 관찰됐다.

따라서 framework에서는 다음을 구분하는 것이 중요하다.

GUARANTEED
연산 구조상 반드시 참

POSSIBLE
구조상 가능하지만 확정되지 않음

OBSERVED
현재 파라미터나 실행 결과에서 실제로 관찰됨

---

13. Compiler 관점에서의 의미

이번 실험은 단순히 두 행렬을 곱해 연산 수를 줄이는 것 이상의 의미가 있다.

일반적인 compiler fusion은 다음과 같이 변환한다.

Linear 1
Linear 2

를:

Fused Linear

로 바꾼다.

이 과정에서 그래프의 외형은 단순해진다.

하지만 단순한 fused weight만 저장하면 원래 존재했던 중간 병목 정보를 잃을 수 있다.

합성된 행렬의 shape만 보면:

4 → 4

이므로, 이후 분석기가 다음과 같이 오판할 수 있다.

정사각 행렬이므로 가역 가능성이 있다.

그러나 원래 연산이:

4 → 2 → 4

였다면 rank는 반드시 최대 2다.

따라서 fusion 과정에서 다음 metadata를 함께 전달해야 한다.

structural_rank_upper_bound = 2
source_linear_count = 2

이 metadata 덕분에 fusion 이후에도 다음 사실을 보존할 수 있다.

정보 손실 발생
비가역성 보장
many-to-one 보장
surjective 아님
bijective 아님

즉, rewrite는 계산 결과뿐 아니라 연산의 의미론적 성질도 보존하거나 정확히 전달해야 한다.

---

14. 검증 결과

마지막 assertion 결과는 다음과 같다.

Original chain == fused execution: PASS
Null direction residual is zero: PASS
fused(x0) == fused(x0 + v): PASS

세 검증이 의미하는 바는 다음과 같다.

계산 동등성

원래 두 Linear 실행 결과
=
합성된 Linear 실행 결과

Fusion rewrite가 올바르다.

Null-space 검증

v @ W_fused ≈ 0

출력에 영향을 주지 않는 입력 방향이 실제로 존재한다.

Many-to-one 검증

fused(x0) = fused(x0 + v)

서로 다른 입력이 동일한 출력으로 매핑된다.

---

15. 최종 결론

이번 실험은 다음 사항을 확인했다.

첫째, 연속된 두 affine Linear 연산은 정확히 하나의 affine Linear 연산으로 합성할 수 있다.

W_fused = W1W2
b_fused = b1W2 + b2

둘째, 합성 전후 출력은 완전히 동일했다.

maximum absolute difference = 0

셋째, 4→2→4 구조는 출력 shape가 다시 4가 되더라도 중간 2차원 병목으로 인한 정보 손실을 복구하지 못한다.

넷째, 합성된 4×4 행렬의 rank는 2였으며 입력 공간에는 2차원의 null space가 존재한다.

다섯째, 서로 다른 입력에 동일한 출력이 생성됨을 실제로 확인했다.

여섯째, semantic analyzer는 다음 성질을 정확히 판정했다.

irreversible = True
many_to_one = True
input_recoverable = False
surjective = False
bijective = False

마지막으로 가장 중요한 점은 다음과 같다.

그래프 rewrite는 출력 값의 동등성만 보존해서는 충분하지 않다.

Fusion 이전의 연산 구조가 가지고 있던 rank bottleneck, 정보 손실, 비가역성 같은 의미론적 사실도 함께 전달해야 한다.

이번 구현의 structural_rank_upper_bound와 source_linear_count는 바로 그러한 정보를 fusion 이후에도 유지하기 위한 metadata다.

따라서 현재 Linear 구현과 semantic analysis는 단순한 shape 분석을 넘어, 연산이 입력 정보를 어떻게 보존하거나 소실하는지를 추적하는 방향으로 정상적으로 동작하고 있다.