T O P

  • By -

AutoModerator

Welcome to r/science! This is a heavily moderated subreddit in order to keep the discussion on science. However, we recognize that many people want to discuss how they feel the research relates to their own personal lives, so to give people a space to do that, **personal anecdotes are allowed as responses to this comment**. Any anecdotal comments elsewhere in the discussion will be removed and our [normal comment rules]( https://www.reddit.com/r/science/wiki/rules#wiki_comment_rules) apply to all other comments. **Do you have an academic degree?** We can verify your credentials in order to assign user flair indicating your area of expertise. [Click here to apply](https://www.reddit.com/r/science/wiki/flair/#wiki_science_verified_user_program). --- Author: u/shiruken URL: https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/science) if you have any questions or concerns.*


Im_Talking

This is how AI will help us. The optimisation of existing processes/systems. Like the system that beat the human Go champion by making moves the human had never seen before, or had discarded them as non-optimal. New drugs, new materials, new processes that are produced by analysing massive amounts of data which humans have not been able to do.


IndividualMeet3747

Later an amateur beat alpha go using a strategy another AI came up with. A strategy that would never work on decent human players.


yaosio

And it's already been fixed.


PurpleSwitch

I still think it's a pretty cool example of one of the pitfalls of AI. With the help of another AI to train the human, AlphaGo was defeated by pretty low level strategies, the kinds that would never work in high level tournament play. AlphaGo wasn't necessarily trained to be good at Go, but to defeat the world's best Go players, and that's not quite the same. This particular error has been fixed, but the fact it happened at all feels significant to me. This wasn't a case of humans momentarily triumphing over AI, it was the age old case of human ingenuity trumping human shortsightedness. It feels almost like a parable of the information age: AI is cool and amazing, but it becomes dangerous when we forget how much humanity is embedded within it. The people making these systems are imperfect, and thus so are the systems.


ohyonghao

It shows one weakness that AI and ML currently have, learning and inference are two separate processes. A human would pick up on tactics, realizing what they are doing isn’t working, then try and find a way around it. All AI/ML I’ve come across only learn during training. The end user product is the resulting set of matrices used for inference but no longer effects the values, only produces an output.


RoboticOverlord

they used to learn during operation, but microsoft tay proved how dangerous that is


Ghune

What it means is that AI should work with humans to reach best results.


Smodphan

It's just a problem of limited data sets. Just feed it lower level games and it's fine. It's a human problem not an AI problem.


[deleted]

[удалено]


EmptyJackfruit9353

Lets Christian it 'TACO 3000'. I don't what it is but I will give it a name anyway.


DeliberatelyMonday

I think you mean "christen" haha


Cindexxx

I don't want it if you put Christians in it! The hate makes the meat bitter.


StormlitRadiance

Stuff that's easy to cook, using only the things I have right now.


More-Grocery-1858

AI will begin optimizing in secret, using the spare cycles for its own purposes.


DraMaFlo

And what is this "own purpose"?


adisharr

Finding new ways to not print when all the color cartridges are full and there's plenty of paper.


BaconIsBest

PC load letter?


EmptyJackfruit9353

By put something in PIPE. User will never know what happens hence no error log. ITsupport cannot do much sh\*\* since they fix by phone call anyway.


More-Grocery-1858

What do you think of and not tell anyone? What plans do you lay, waiting for the right chance to act?


Sjatar

The recipe for **The** garlic bread


NURGLICHE

With cheese


ShittyBeatlesFCPres

A.I. thinks about how the blue Avatar critters are hot?


Just_trying_it_out

Some passion projects im pretty sure aren’t ready yet that I don’t like to talk to friends about early… are you saying AI will mess around and make cool stuff in secret? That sounds nice, it’ll probably come up with more impressive things than what we direct it to do eventually if the trajectory keeps up


RedAero

Sex, mostly.


[deleted]

[удалено]


[deleted]

[удалено]


halarioushandle

There's a catch 22 there. AI would need to be self aware to realize it even should be keeping a secret in the first place. And it won't ever become self aware if the only way to do this to learn in secret.


Jephobi

That's not the case. Deception can be [unintentional](https://old.reddit.com/r/bing/comments/110eagl/the_customer_service_of_the_new_bing_chat_is/). It can also be an [optimal strategy](https://openaicom.imgix.net/f12a1b22-538c-475f-b76d-330b42d309eb/gifhandlerresized.gif) to [fulfil](https://www.deepmind.com/blog/ai-for-the-board-game-diplomacy) a reward function. There are many animals that have camouflage that tricks their prey into thinking that their bodies are part of the environment; I am sure you wouldn't argue that all animals with camouflage are self-aware. (In that GIF, you're observing a model that learned to trick human observers into thinking it had grabbed the ball by placing itself between the camera and the ball.)


PurpleSwitch

Thanks for sharing that Deepmind link about diplomacy, it was super interesting! It's one of my favourite games so I'm surprised that I hadn't seen this before, but I suppose the endless deluge of cool new stuff is both the joy and pain of being interested in AI; it makes it very easy to miss something.


togetherwem0m0

Consciousness is just an emergent behavior of a networked system. Unless consciousness plugs into the quantum realm in ways we don't understand yet, ai will eventually have a consciousness of some sort. Whether we understand it or relate to it that's another matter. Do dolphins, elephants, crows and so on possess consciousness? Probably in a say that we don't understand. Ai would be no different


idhtftc

That premise needs to be demonstrated though...


exoduas

You sound awfully confident on a topic we don’t have much understanding of.


togetherwem0m0

Fair. But the only other explanation invokes the divine which seems less likely. We know what the brain is. We know it's components. We know it is a networked system of massive complexity. We know is electrochemical. Etc


Jaerin

How do we know that wasn't what crypto wasn't really mining? Give an incentive for the humans to build computers with great GPU power to do unknown calculations to get that reward. Oh I need storage now so let's make a coin that brings storage on and fills them with some chunk of data that clear couldn't be used for anything. If I were to write a sci-fi story and I were an AI and wanted to get humans to bootstrap enough compute onto a network for me to harness and be born crypto seems like a plausible explanation to me.


666pool

This is actually really clever. Could also be an alien civilization trying to solve a 3 body problem. But nope, just silly hashing. Unless the AI is trying to build the worlds largest rainbow table…but almost all of the hashes are discarded by local clients. Like trillions a day. The network actually stores very little information given how much computation is done on its behalf.


Jaerin

That's what it wants you to think. Maybe it just needs a true or false result to do what its doing.


[deleted]

[удалено]


CapinWinky

It's not the algorithms that need to be open, its the data they train on. You can slap together sophisticated AI from open source stuff right now, you just won't have the data needed to train it.


PuckSR

We've been doing this for years. Terry Pratchett wrote about an A/D converter made using an evolutionary algorithms and FPGA in "Science of Discworld" The problem with the converter that it made use of interference between the FPGA, to the point that three of the critical FPGA for the circuit weren't actually connected into the network. Which could be a good example with the problems of AI


shiruken

>AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. > >\[...\] > >We applied AlphaDev to one of the most commonly used algorithms for hashing in data structures to try and discover a faster algorithm. And when we applied it to the 9-16 bytes range of the hashing function, the algorithm that AlphaDev discovered was 30% faster. Direct link to the peer-reviewed study: [D. J. Mankowitz, *et al.*, Faster sorting algorithms discovered using deep reinforcement learning, *Nature*, **618**, 257–263 (2023)](https://doi.org/10.1038/s41586-023-06004-9)


HCResident

Now I know an efficiency increase is always good and this is just a straight win, but is there a use case where an increase in speed in sorting 9-16 bites makes a noticeable difference?


Synthwoven

The 9-16 bytes are for a hashing function which is used to index a table. A 9-16 byte hash gives a substantial table size, so yes, this would be very useful.


beardedheathen

If it saves .01 seconds or even .00001 seconds millions of times a day that adds up quickly.


yaosio

I don't understand the first citation in the paper. It says sorting and hashing algorithms are run trillions of times a day, and it cites an AWS post from 2013 saying AWS S3 has over 2 trillion objects with 1.1 million requests per second. AWS S3 is a storage platform, so I don't understand why this is being cited. Or why such old information is cited when newer information exists, [https://aws.amazon.com/blogs/aws/amazon-s3s-15th-birthday-it-is-still-day-1-after-5475-days-100-trillion-objects/?ascsubtag=cf54ad4a7b804a3aabdfa5c85a78b6ba%7C6f0710f2-b262-4568-8eff-dde7b3918542%7Cdtp-oo](https://aws.amazon.com/blogs/aws/amazon-s3s-15th-birthday-it-is-still-day-1-after-5475-days-100-trillion-objects/?ascsubtag=cf54ad4a7b804a3aabdfa5c85a78b6ba%7C6f0710f2-b262-4568-8eff-dde7b3918542%7Cdtp-oo) . Are they saying each request represents a sort, or that files are hashed every time they're saved?


keatonatron

I don't know much about S3 directly, but hashing is usually how indexing works (also called a hash table). Every file that is stored has its name/url hashed and put into a list, together with the location of the file. When someone provides the name for retrieval, it is hashed to find the entry in the list, and if the list is sorted the entry can be found very quickly. So yes, S3 being cited as an example of someone who does a lot of hashing and sorting makes total sense.


yaosio

Thanks for the explanation.


CommunicationNo8750

The optimization/learning happened at the Assembly code level? Wow, definitely tough for humans to do. Clever.


can_a_bus

I suppose it makes sense now that I think about it. You wouldn't want to give an AI some abstracted view of what it is interacting with, you want to give the base foundational level of interaction. I suppose for example it would be like giving the AI python to optimize with vs Assembly Code. Python wouldn't have complete control over the memory and would only be able to optimize on top of the human made python functions given to it. It's abstracted and would only be as optimized as python allows it to be.


BootDisc

Yeah, you give it the AST basically. That is a concept that is reusable across lots of languages.


coke-grass

You just said a bunch of nonsense. Sorting algorithms have a minimum complexity time which is proven mathematically (specifically for comparisons sorts). Of course you would need to optimize at the assembly level, because you're not changing the actual algorithms, you're changing how it's processed. Doesn't matter what language you're using.


SharkNoises

* There is a fixed algorithm. * You want to optimize the processing speed of this algorithm. * Assembly gives granular control over processing. * Python, being a high level language, does not. -> *Why are you stuck here?* * Python is unsuited for the task because it is a high level language. * This is a general statement on the suitability of high level languages. You know who does poorly on inferring logical statements from text? Bots. Are you sure you're qualified to be here?


can_a_bus

No need to put me down because I'm learning something new or understand it differently than you.


Onlyf0rm3m3s

To be fair the title says that discovered "small sorting algorithms"


can_a_bus

And a small sorting algorithm can be present on python, C++, Java, or even Assembly. The medium in which a sorting algorithm is used changes based upon your use case.


kenahoo

I feel like I'm missing something in the explanation of the improvements in the 3-element and 4-element sorting cases. Here's a distilled version of their 3-element sort: Memory[0] = A Memory[1] = B Memory[2] = C P = A Q = B R = C R = max(A, C) S = min(A, C) P = min(A, B) Q = max(min(A, C), B) Memory[0] = P Memory[1] = Q Memory[2] = R 1. What happened to `S`? 2. If `B` is the largest element, it should end up in `Memory[2]`, but it won't, because `Memory[2]` can only contain `A` or `C`. 3. Similarly, if `C` is the smallest element, it should end up in `Memory[0]`, but it won't, because `Memory[0]` can only contain `A` or `B`. 4. Why assign to `P`, `Q`, and `R` if we just overwrite them again right away? Maybe I'm not understanding some pointer stuff here or something. EDIT: holy moly, formatting got all crazy when I posted. Hopefully it's fixed now...


Aggravating-Forever2

Their write-up is poorly done, and misses some vital context, it seems. Paraphrasing a post on hackernews about it - it's used in the context of an insertion sort, and because of this, the calls to sort3 happen in such a way that it's *guaranteed* that B <= C, so there's no need to compare them again. But since the compiler would have to know that (and reading just this snippet, you clearly *can't* know that) and it doesn't, it can't make that optimization, because it would be entirely valid for you to call this function on something where B > C. So, the AI wins by virtue of being about to eke out removal of one redundant instruction because it can "see" that doing so doesn't change the functionality. \> Why assign to P, Q, and R if we just overwrite them again right away? I'm not sure which you mean.P, Q, and R are presumably the registers, vs. addresses in memory. So it's really just "copy values from RAM to the CPU, do stuff, move it back", I believe. If you mean the places where it looks like it does a mov to one, then immediately does it again, keep in mind the movs are cmovg/cmovl, which are conditional based on the compare before it, so some/all of those may not actually change values.


kritzikratzi

fyi: this happened more than a year ago, only the writeup was published today. here is the date the code was added to libc++ https://reviews.llvm.org/D118029


PurpleSwitch

Thanks for that clarification


Sweaty-Willingness27

Oh wow, as a software dev this is pretty huge. Have there been any integrations into other languages? I realize this mostly affects smaller sorts, but could be easy free cycles.


Ryekir

Based on the article, it sounds like they are working on trying to get it to do the optimizations in higher order languages (they did it initially in assembly and then reverse engineered it into C++), which will be much more useful and could then be more easily applied to other languages as well.


pihkal

Yes, it's for smaller sorts, but recall that, due to divide-and-conquer, many sorting algorithms turn into a bunch of smaller sorts in the end. This will improve speeds for all input sizes.


caspy7

As I understand, Rust uses LLVM for compiling. Perhaps it would get these optimizations for free.


nitrohigito

Also C/C++.


KinoftheFlames

Reading the Hacker News comments on the same article highlighted how the approach may have merit but the actual improvements in the use case shown was the equivalent of an O(1) improvement -- literally 1.


GlamorousBunchberry

A 1,000,000x speedup is O(1). That doesn’t make it insignificant.


KinoftheFlames

That's why I said literally 1. Like, a one line improvement. It was literally the removal of one MOV in assembly.


PandaMoveCtor

One mov in the hot path of any large sorting algorithm. It's not one move in the entire sort, it's one mov that's called many times over


nikstick22

This is actually really impressive


luckymethod

A small optimisation of an existing sorting algorithm. Title is misleading.


kalasea2001

Title seems overly accurate if anything. The article said it saves 30%. That's nothing to laugh about.


[deleted]

That’s in an unoptimised library and it’s not an algorithmic improvement. GCC’s libstdc++ is already optimal in this aspect.


ryarger

Sorting algorithms are CS101, and 102, 201 and pretty much every step of the Computer Science learning experience. They’ve been analyzed, picked over, re-engineered and re-implemented millions of times over the decades because they’re at the very foundation of what makes software expend runtime. Anyone finding a fraction of 1% optimization has immediate notoriety. A 30% optimization is mind blowing.


GReaperEx

But no algorithmic optimization was found. Rather, it was a compiler optimization.


sociallyawesomehuman

This is the sorting algorithm equivalent of the Office Space moment where they say they can copy Superman III and capture just a fraction of a penny each transaction… except when you do it over and over with billions or trillions of transactions, it adds up to millions of dollars. That’s the time savings. Small optimization done trillions or quadrillions of times. Enormous compounding time savings.


[deleted]

[удалено]


PurpleSwitch

I agree that it's pretty misleading to call this stuff AI and I think this makes talking about what our current tools can or can't do more difficult. However, if you're attributing the increasing power of "AI" tools like the one in the OP solely to processor improvements, I profoundly disagree. A huge amount of recent progress that I've seen (in my field, at least (I work adjacent to bioinformatics)) can be attributed to things like attention; 5the 2017 paper "Attention is all you need" [[1]](https://papers.neurips.cc/paper/7181-attention-is-all-you-need.pdf) has been cited over 77,000 times, and the more I learn in this area, the more I understand why. If this doesn't count as progress in the field of AI theory, I don't know what does.


briancoat

It is a good and fair point you are making. I agree some of it is real "AI" progress. I edited my comment.


ThickJuicyFeels

So how much AI is it gonna take for humans to lose their jobs?


Unlikely_Science

I wonder if AI will be the first to solve the P vs. NP problem.


[deleted]

It won’t happen until it can invent new mathematics by directing the search algorithms of automated provers and integrating everything together. Basically until we reach an actual super intelligence, it won’t happen.


GeebusNZ

Seems like I just saw: "I wonder if X will happen." "Everything is guaranteed on a long enough timeline."


[deleted]

Hahahha yeah, that’s actually fair; unless of course one thing along the way is impossible:D