Show HN: Speeding up LLM inference 2x times (possibly)

Maybe, but theres nothing that stops OpenAI from stealing these tricks.

In this case though, the algorithm should be just as useful to closed models as to open models. There is nothing there that is optimised specifically for Mistral - aside from the hard-coded dimensions in multiple places in the code :D

Having said that, it's awesome to have open source models out there, and I hope they will ultimately win in the end.

That seems fundamentally flawed to me. Closed providers can copy techniques from open models but not vice versa.

To me that reads as closed will always be a step ahead not an existential risk to OpenAI.

Thanks! The last full month was all about making sure all the research is as replicable and as trustworthy as I can do it. The original implementation was extremely inefficient, and even once I had the Metal/GPU mmul op working fast, I spent much time to bring the rest of the implementation as close to the Llama.cpp as possible to allow for easier benchmarking.

As for the approaches - it seems the papers you mention do this statically, and din't produce an algorithm for actually speeding up computations with their 20-50% results - which was a large part of the difficulty. I'll probably take some time off one day and do a thorough review of the literature finally.

Ultimately I want to add a citations page with these and some other papers people have posted in the comments soon. I expect sooner or later someone will find this algorithm written up by someone :)

While development asked gpt-4 and googled trying to find information about this method - everything seemed either static, or focused on removing full dimensions/layers ad hoc with eventual retraining. Didn't find anything matching this idea exactly.

It’s explained in detail here:

https://kolinko.github.io/effort/equations.html

Long story short - I kind of sort them and pick only the top % that would give a highest result.

One part is choosing them though - I think this was done before in some papers. But the second part was an implementation of multiplication that is efficient on both gpus and cpus when choosing weights almost at will.

All explained on the site, but I just got feedback that it may not be easy enough to read, so I’ll push it through gpt for grmamar fixes soon :) It’s also a bit complicated as an algorithm.

A bit like calculating the fastest route for a car, you probably don’t need to calculate the distances for the opposite side of earth if you will not drive there. Then multiply that by a billion, but the optimization still holds.

Hahah, thanks! It was a marathon to get develop this, and I'm glad it reached the front page.

The name was proposed by chatgpt :) It claims it doesn't recognise this approach - so there is a chance it's really a new thing.

I want to reach out to llama.cpp and the others - I hope it gets implemented. I considered just writing a patch to llama, but c++ and the scale of that project was beyond me.

As for CPU inference - it should speed it up just as well. But thanks to the fact that it can load up a fraction of weights (e.g. just 70%, skipping the least important ones), it should be possible now to run models on less VRAM than before (still, Q8 needs to implemented though).

Funnily - when I tried comparing benchmarks to llama.cpp, I couldn't find speeds for 7B/FP16 on MB Air 16GB, because it's impossible to run with regular methods. It is possible with Effort.

Ditto, I was running full resolution, but cropped, Mixtral on my 96GB M2, even though it usually takes 114GB ram. I just loaded 75% of weights, and it was working smoothly. (before I messed something up with implementation and it now produces crap output - needs a fix)

It originally started as a fork to Recmo’s cria pure numpy llama impl :)

https://github.com/recmo/cria

Took a whole night to compute a few tokens, but I used it to do the first tests.

Also, my friend pasted the paper to claude and it produced a working basic impl instantly :D

But in all seriousness - I think MLX implementation would be doable, or a wrapper to the Metal gou functionality

not sure why I got downvoted for asking this. seems like a reasonable thing in the ML space

anyway here's a numerical simulation written in PyTorch for those who want to consider this algo on their projects before fully integrating: https://gist.github.com/bwasti/78d7058aad7f42dc893d906c877b7...

happy hacking

Yes! That would be awesome. Especially since there are ~32*6 independent effort settings for every single token.

I tested the most basic implementation, with a flat effort setting for all the muls, but I bet the results could be pushed even further with such an approach. Or even with just doing some ML to figure out which layer/matrix needs more and which less effort.

I’d say that this expands on MoE really - MoE chooses dynamically which groups of weights may be needed, but it’s whole matrixes. Here it’s ingle weights.

Also, this works on top of MoE beautifully - most of the development and testing was done on Mixtral and it was getting (anecdotally) even better results - getting down to 15-18% effort before seriously losing quality.

I decided to release the Mistral version, but Mixtral was fully operational a few commits back :)

Also, the cool thing - because you can load only the top say 70% weights, I was running Mixtral full precision on my MB 96G - there were no bemchmarks for this in other impls because others need to load full model into the memory.

The real question is Q8 performance - I didn’t implement it fully so far.

It also feels similar to mixture of depths (https://arxiv.org/abs/2404.02258).

Being able to apply this post-training is pretty cool though, makes it easier to use across a wider range of setups.

Haha halfwit! I’m waiting for such a fork.

As for predicting the weights - not necessarily so. It seems most weights are being used, just not all the time. Kind of like that saying that humans are using just 5% of their brain - perhaps they are, but it’s various parts of the 5%.

Interestingly, Effort works just as well on MoE, if not better. I did most of the development on Mixtral and I think it go even to 15-20% effort before losing quality, but there is some sort of a bug right now that prevents the inference on Mixtral.

It’s on a todo to fix, but I didn’t want to delay the release because of it.

Effortless would be another great name (since you are literally reducing effort to get speed). OK, maybe not "great", but "an option if you're going for puns".

Halfweight. Half the weights, half the wait, half the wit.

Per VRAM - not much netter, because it still uses all the weights, just not all the time.

I mean - it can also load less weights, but quality seems to degrade quick after offloading more than 20-30% weights.

In other words - this algorithm decouples inference time from VRAM use.

Having said that, I’m curious as well if using effort you can get better results on Q8 cropped to 75% than on Q6.

But it’s still probably a few weeks to get the implementation polished enough to be well tested.

Can you rephrase the question? Not sure I get it.

The metric that's improved is computation speed, and it's achieved by essentially changing the computation (by not performing some computation that likely doesn't have large impact on the results).

Give that it's a different computation, you could argue that Mistral+effort is a new model with the improved metric of quality per amount of computation performed.

Otherwise - given that for every different input there's a seperate set of weights in the model that are excluded - I don't think you could conclude from this (if it holds up etc etc) that the base model is not optimal.

In a similar sense, quantization improved the "quality per model size" metric, but I don't think people are arguing that Mistral is less optimal than quantised Mistral (unless you're speaking about literally that metric). On the other hand, if you're targeting that metric specifically, then it would make perfect sense to say that quantised Mistral is more optimisal for it.

I guess it comes down to optimality being dependent on the metric you're looking at, and there being many things you might want to optimise for.

To note again, if this technique holds up, it's better than model distillation (just get rid of some of the weights) because for some inputs those weights could matter and this technique should (iiuc) account for that somewhat. To me, this is what it sounds like you're referring to when saying:

If removing weights improves some metrics, that may be a clue that the model is not optimal in some sense

The algorithm still uses all the weights, just not all the time - just skips the weights when they are not important given an input vector.

Also, approximation methods, as a field, are not new and they have shown their use.

Having said all that, extraordinary claims require extraordinary evidence - that’s why I hedge the communication messages. It’s „probably” until we get serious tests going on

Wait, does the second "it" refer to the true part? Because traditionally, it refers to the "too good" expression. So you'd say, "it _is_ too good to be true".

Similar theme, but they skip whole neurons, in my case it’s down to a level of single weights.

From my experiment, skipping whole neurons (so whole rows/columns of matrixes) didn’t allow for such good results. In my case 30-50% neurons whole are skipped with 15% effort, but the rest is used partially still.

There are a few papers on a similar theme that a friend sent me today morning - I plan to add them in the citations part

We've merged them. (other one was https://news.ycombinator.com/item?id=40067489)

oh, thanks, I fixed it. No idea what I meant there originally.

There are still a few typos on the page, I'll be fixing them tomorrow - it's midnight now, and my mental batteries are slowly drying out :)

At first glance, that sounds like it could work. From what I've read, there seems to be two main ways to regain some quality with quantization: post-training which happens after, and quantization-aware training which quantizes during training but leaves the activations and gradients full precision

A friend who first heard of the method immediately suggested this may work, perhaps even better in Diffusion models.

It is really a drop-in replacement for the regular matrix multiplication. The data structure is a bit more painful to work with (you have three datasets, not just one to represent a weight matrix), but it shouldn't be too difficult for devs of the existing inference engines to implement it for a test.

Half of my challenge was that I wasn't knowledgable enough to just patch llama.cpp or MLX and use their engines with bucketMul. That's why I opted for making my own - still not sure if it was a good choice to build everything from the ground up though, although I'm proud of the name :)

Finally - the basic math behind approximation suggest that this should work with all the models - cosine similarity score is 0.99 until the magical 25% mark for most of the matrixes I tried. It can vary within a model though - e.g. in Llama, on the first layer, wq/wv/wk could be easily approximated with 5% effort, whereas some deeper layers at 25% had just 0.90 cos score - still seemed enough to not lose coherency within the model.

Haha thanks! :) As far as I understand I had to implement the memory reads and some other things the opposite way to what is considered a proper approach.

Would love to have that code reviewed by someone who actually knows stuff about Metal - this is my first gpu programming attempt

Ah yes, forgot to make the repo public. Thanks a ton for pointing it out and writing the comment - I'd miss it if you didn't point it out on HN.

Oh, nice to finally bump into someone who has experience with CSR!

bucketMul has few uncoalesced reads, and it uses a different data structure than the regular CSR - it's decribed here: https://kolinko.github.io/effort/bucketmul.html It splits each Matrix row into 16 parts, and chooses which ones are necessary to read. The writes are fully linear.

Not sure if I speak sense though, it's getting a bit late today, and it's been a long day ;)

Thanks for checking it out!

I also can’t wait to have more tests done.

Also, I chose Apple Silicon because it was easier for me to develop on. It is possible that the algorithm would also have good performance on other architectures.

Nah, that's not it, I measure the CPU & GPU work separately, and 15ms happens between the kernel invocations. It also happens when I don't print out text.

Thanks for the idea though! I treat it as the first community contribution :D

hard to say for now, I’m curious as well, but I used simpler tests so far because of the implementation issues - most test suites are geared towards testing models and not model implementation.

I didn’t want to wait any longer with the release, but better tests will be coming soon I hope. Anecdotally, I think 30% effort should be comparable to Q8z

More importantly, this algorithm should work on top of Q8. The quality is not yet certain though - I could use help with the implementation.

What would definitely help would be a better understanding a GPU handles myVal - does it go to the cache, threadgroup memory or where. Or perhaps decompilation of the source kernel to see what's really going on there. If we knew, we could calculate the optimal parameters given an architecture.

There is also another approach I tried - I've kept it in the wildMul.swift/metal . More by the book. Splitting work so that one thread keeps track of only one or two output dimensions when going through the buckets. Didn't manage to get it working with a decent speed though.

The idea would be to make sure that one simdgroup reads 4/8 buckets in a batch (so still ~8-16 consecutive bytes which is considered minimum for an optimal read on Apple Silicon) and splits each single bucket among 4-8 threads. One thread might then need to remember only 2-4 dims in myVal, and this might stay in internal GPU registers.

Not sure if I'm explaining this all correctly though.

Having said this - the priority now will be to remove the overhead to get the whole inference time closer in speed to just the multiplication speeds, but above all - fixing the bugs causing suboptimal results at 100% (and breaking Mixtral), and doing Q8. The algorithm needs to work in Q8 to be really usable.

That was one of the ideas I was also considering originally! Don't remember why is skipped it though - may have been because I tried the published one and it worked well enough during the first tries.

As for indices for weight - not sure if I get what you mean, but the weights are sorted as a part of precomputations. Sorting is not done in runtime, because that would kill any efficiency - the moment you need to read all the weights, you've lost, because it's the memory reads, not computations that matter. If you can skip one memory read by doing 5-10 multiplications, it's a good tradeoff.

Yes! I hope, if it’s proven, that it will be implemented into the main inference engines.

40% effort is only a bit faster than a full base multiplication, but I hope both the speed and the accuracy could be improved further.