A Guest Post from Associate Professor Nick Falkner
This is a very long rant about something I really don’t like about Generative AI. This rant is full of computer science and maths, but the hot takeaway is that GenAI makes up answers even when none are there to be found, which can make a worst case situation even worse.
Computer science is built on solving a specific class of problems that can be solved by a computer program in a finite number of steps. We produce algorithms that will do this but, because there can be many steps, we employ machines to do the grunt work of the solving, which they do, reliably, many times to arrive at the solution. A lot of the algorithms we use provide two key utilities: searching and sorting.
When you have a lot of information, finding things can get hard, which is why CS has spent a lot of time finding better ways to search. However, some things are easier if the data is sorted, so we’re also good at sorting algorithms. The two go hand-in-hand and we can use our knowledge of the algorithms to predict how much memory and time we’re going to need to search or sort (or both) a large amount of data.
One of the key issues in search is how quickly we can work out that something isn’t already there. We want to find things that ARE there quickly, but we don’t want to spend ages looking for things that AREN’T there. Let’s talk about socks. You are looking for your rainbow “all pride no prejudice” socks so you can rock the rally and you can’t find them. Now, in the back of your mind, you are aware that you might have left them in Sydney but you’re not sure. You start looking in your sock drawer. Your sock drawer is a mess and it has 1000 odd socks in it. Because it is chaotic and unsorted, you now have to remove enough socks that you can see that the sock you want isn’t there. (Notice I said “remove” because if you just rummage you might miss a sock that’s there, but hidden under another, you have to reduce the searching set by removing socks that don’t match.)
The sock isn’t there. Now you go to your laundry hamper. Your secondary hamper. The clothes line. Down the back of the couch.
Let’s assume that it is possible for you to search your entire house. Eventually, you cannot find the sock. Ok, it’s in Sydney, go find another pair.
Now, if you had organised your data, sorry, socks, and ensured that all the socks were in one drawer, that they were neatly arranged in pairs, then your search would take less time BUT you would have spent more time sorting things initially. This is a tradeoff that everyone does when storing information. How much sorting time do I invest to reduce my search time? How much search time can I tolerate to reduce my sorting time?
The algorithms we use describe the amount of time and resources consumed when running based on the complexity classes of the algorithms. The details are a little complicated to go into here, but, essentially, if you have a number of socks – let’s call that number n – does the amount of time it takes to find things stay the same regardless of n, does it grow at about the same rate n grows, or does it grow faster, or even much faster?
These estimates often look at the best case, the worst case, and the average. If I have to examine every sock to see if it’s the right one (I’m not wearing my glasses so I have to squint), then for n socks that’s n examinations. Let’s call each search a ‘squint’. If I happen to pick up the right one first time by chance, it’s only 1 squint! So the best case for this search is 1. But if I have to look across the whole set to see that my sock isn’t there, then that’s n ‘squints’.
The important thing here is when I want to check if something is there before I add it AGAIN. Let’s say I want to check if I already have a black cotton shirt. If I search my well-sorted wardrobe and can’t find it, then I can buy the new shirt and then I only have one. Some data representations make important assumptions about there only being one of something so this is important. We build our resources, our computing facilities, our performance expectations, around the known characteristics of these algorithms, using best, worst, and average cases to make computing as fast and efficient as we can. We can assert that something not found in a well-constructed dataset isn’t there and act accordingly. If we sort shit, it stays sorted unless we actively mess with it.
Here is some very quick maths. Our best search algorithms tend to find things in less than n squints. In fact, we can often organise things so that it’s a lot smaller than n. . Sorting things takes longer because we have to compare things, but we can generally get this into something like n multiplied by the logarithm of n squints. There are algorithms that work in n*n (n squared), which is fine if you have 10 pieces of data so it takes 100 operations, but once you have a thousand, a million operations take a little longer, so they are unwieldy for big data. And for all of this, we often want to know if something is there AND if something isn’t there, as quickly as possible.
Now, here’s the problem with Generative AI getting involved and pretending to be searching for you. Firstly, GenAI is not doing a search. It’s generating an answer that is a statistically plausible outcome of questions like yours that have been asked before. Secondly, in case you haven’t noticed, when in doubt, Generative AI generates SOMETHING and almost never tells you that something isn’t there. And it may have to be specifically pushed to tell you when something isn’t there. And every query is at least n times n squints (or squint equivalents). Every query is at least the worst case of every operation above and FAR worse than actual search.
Using Generative AI to find your socks is potentially going to result in it making new socks for you that say “PRID IS PREJOODICE” and returning it, with a power bill and water cost.
Not only have we totally removed any benefits from the best case and average case of the actual operations, but we’ve hidden one of the most important aspects of search – the certainty that something isn’t there.
Removing this certainty breaks one of the key guarantees of any good searching algorithm: that it only finds what is there. What this means is that any answer you get may have been fabricated from nothing to provide a plausible answer that appears to meet your requirement.
Web searching used to mean trying to find things that weren’t there as it then helped you to understand whether a question had been answered or not. It told you if somebody had already moved in a space; if what you were doing was new. It worked because web searching used to conduct a search over constructed and sorted indexes to find things if they were there and tell you if they weren’t. Quickly. Efficiently. Reliably.
GenAI doesn’t search, it uses the worst of worst case performance to then make a nonsense of what search used to be about, and it makes shit up when it has no actual answer to present.
My strong suggestion is that you trust nothing the machine gives you unless you verify it independently – and no, I don’t mean by asking Claude to check ChatGPT. I mean go and find an old website or book, something where actual information is stored.
But I keep coming back to the same question. This type of information retrieval is inherently less efficient and increasingly less effective. Adding to that, if you have to check every result manually, is it actually worth using it at all?
