Some background: I’ve recently become obsessed with combinators, specifically iota, where:
i x = x S K
It’s a single combinator basis that gives you
i i = I, i I = A (A x y = y), i A = K, i K = S
so you can recover S, K, and I and the full combinator calculus.
This of course leads to Micro Haskell, a project by Lennart Augustsson that compiles Haskell 2010 to combinators (with support for primitives/FFI to enable IO, fast math, etc.)
I’ve been using MicroHs for a few projects, and I thought, can we do LLMs in pure combinators?
To explore this idea, I looked at BitNet 1.58 from Microsoft.
It’s an interesting idea: instead of using floating point weights, there are only three weights: {-1, 0, 1}.
Using these we get an interesting property: you don’t need multiplication at all!
When you do the classic dot product, say [x1, x2, x3] x [-1,0,1], you get (-1)x1 + 0*x2 + 1*x3, which is of course x1 - x3. No multiplication required at all!
To get this back into the combinator world (where we really only have the naturals), you can model negative numbers as difference pairs: (a,b) = a - b, where a and b are church-encoded naturals.
So, can we then do the huge matrix multiplication in pure combinators? Turns out yes! It boils down to sum $ map (\(x,w) -> if w == 1 then x else swap x) $ filter ((/= 0) . snd) $ zip xs weights. on -1, we swap the pair (the C combinator), on 0 we drop it, and on 1 we keep it unchanged.
But it’s very slow. However! MicroHs has an FFI interface so we can define kernels to do the numerical parts (not pure combinators anymore, but we have to live with that).
Here are my results:
(The tokenizer is mostly due to lack of any aeson in MicroHs).
By adding a few small kernels and using MicroHs for the rest, we got quite OK performance, ~10 tokens/second.
We’re not going to beat GPU accelerated matrix multiplication any time soon, but it was very interesting for me to see how simple things can be, and the fact that BitNet 1.58 (despite its name) essentially lives in the integer world. We can represent the weights of the LLM in ~22 Billion combinators (~98 billion iotas), which gives you a sense of scale (though with all the intermediate steps the number of iotas at any point can get much bigger). If we imagine that the model was quantized to int8 tensors, we get a clearer picture:
So, ~60 million combinators in total, almost all of it data.
In any case, I thought this was a fun weekend project (Claude was surprisingly good at writing MicroHs and kernels), and if we ever run out of silicon, we can always manually reduce iotas to get our answers (though we’d need to figure out the tensors first). Maybe that’s how Deep Though came up with 42?
Here’s the codebase for the experiment for those interested:
And, for good measure, there’s also an interactive combinator playground, if you want to play around with combinators and iotas in a more sandbox setting. You can even compile MicroHs programs straight to the canvas!