GKR prover overhead

	A	B	C	D	E	F	G	I	J
1		Full rounds	8
2		Partial rounds	24
3
4			Adds	Muls
5	"Easy matmul" cost	X -> X * diag + sum(X)	31	16
6	"Full matmul" cost	X -> MX (assuming M is repeat of 4*4)	80	80
7	Ext*ext mul cost	Mod X^4 - 3. No karatsuba turns out to be faster	18	16
8
9			Base adds	Base muls	Ext adds	Base*ext muls	Ext*ext muls	Total base adds	Total base muls
10	RLC for linear sumcheck		14		14	14		70	56
11	Weights generation	Small-size (this also gets used for full layers)			0.25		0.25	5.5	4
12	Linear sumcheck (first layer)	Half-size due to Gruen's trick	1			1		1	4
13	Linear sumcheck (later layers)	N/4+N/8+N/16+... = half-size			1		1	22	16
14	Cubic sumcheck (first layer)	Half-size due to Gruen's trick	2	3		2		2	11
15	Cubic sumcheck (later layers)	N/4+N/8+N/16+... = half-size			2		5	98	80
16									0
17	Full layer (execution)		80	80				80	80
18	Partial layer (execution)		31	16				31	16
19	Total execution		1384	1024				1384	1024
20
21	Full layer (proving)		32	48	32.25	32	80.25	1605.5	1460
22	Partial layer (proving)		17	3	17.25	17	6.25	198.5	171
23	Total proving		664	456	672	664	792	17608	15784
24
25		Does not take into account memory bandwidth or differences in ability to parallelize different operations.
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100