Hum... The gotcha is that LLMs can rank for subject relevance, but not for most other kinds of quality.
Hard problems that reduce to document ranking
21–30 of 57 posts
Re: Hard problems that reduce to document ranking
#22Hum... The gotcha is that LLMs can rank for subject relevance, but not for most other kinds of quality.
What other kinds of quality are you thinking of?
Re: Hard problems that reduce to document ranking
#23Earlier quoted context omitted.
"Document ranking reduces to these hard problems" would imply that document ranking is itself an instance of a certain group of hard problems. That's not what the article is saying.
I know its counterintuitive, as I explained in my comment, but that's the correct terminology in CS world.
I want to hear more about your point of view, because I disagree and am curious if there's another definition of "reduce". In my CS world, reduce is a term that you use to take a list of stuff and return a smaller list or instance of stuff. For example: [1, 2, 3].reduce(+) => 6. The title would go like [hardProblem1, hardProblem2, hardProblem3].reduce(...) => documentRanking. I think this mental model works for the non-CS world. So I'm curious what your viewpoint is.
Re: Hard problems that reduce to document ranking
#24Earlier quoted context omitted.
I know its counterintuitive, as I explained in my comment, but that's the correct terminology in CS world.
I want to hear more about your point of view, because I disagree and am curious if there's another definition of "reduce". In my CS world, reduce is a term that you use to take a list of stuff and return a smaller list or instance of stuff. For example: [1, 2, 3].reduce(+) => 6. The title would go like [hardProblem1, hardProblem2, hardProblem3].reduce(...) => documentRanking. I think this mental model works for the n…
In (Theoretical) Computer Science it is sometimes helpful to be able to say "Any instance of an A-type Problem can be transformed into an instance of a B-type Problem by applying this polynomial-time procedure".
Say you have a problem that you know reasonably well (A-type) and another one that you're studying (B-type), intuitively, you'd say "If I transform B to A and I know the solution to A, then I solved B" but what you actually need to do is to transform A to B, this is called "reducing A to B", for some reason, and then you can say things like "B is at least as complex as A" and "I can solve some instances of B the way I solve the general case of A".
This doesn't really apply here since neither the "hard problems" TFA mentions nor "document ranking" are canonical problems that you would typically use in these proofs, but since he's borrowing the term from this part of CS I wanted to make that remark on its proper use. Hence why I wrote "minor nitpick".
The reduce operation that you mentioned doesn't make sense within the context of the article.
Re: Hard problems that reduce to document ranking
#25I'm curious - why is LLM ranking preferred over cosine similarity from an embedding model (in the context of this specific problem)?
Because the question "does Diff A fix Vuln B" is not answered by the cosine distance between vector(Diff A) and vector(Vuln B).
What if u embed `askLLM("5 thins this Diff could fix" + chunk)` instead of `chunk`? That should be closer in the latent space.
Re: Hard problems that reduce to document ranking
#26Earlier quoted context omitted.
I want to hear more about your point of view, because I disagree and am curious if there's another definition of "reduce". In my CS world, reduce is a term that you use to take a list of stuff and return a smaller list or instance of stuff. For example: [1, 2, 3].reduce(+) => 6. The title would go like [hardProblem1, hardProblem2, hardProblem3].reduce(...) => documentRanking. I think this mental model works for the n…
In (Theoretical) Computer Science it is sometimes helpful to be able to say " Any instance of an A-type Problem can be transformed into an instance of a B-type Problem by applying this polynomial-time procedure". Say you have a problem that you know reasonably well (A-type) and another one that you're studying (B-type), intuitively, you'd say "If I transform B to A and I know the solution to A, then I solved B" but w…
Wikipedia: “Intuitively, problem A is reducible to problem B, if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently.”
The article takes for granted that LLM-driven listwise comparisons efficiently solve document ranking (problem B), and then shows this can also be used as a subroutine to solve various hard problems like vulnerability analysis (problems A) efficiently.
Re: Hard problems that reduce to document ranking
#27This furthers an idea I've had recently that we (and the media) are focusing too much on creating value by making more ever more complex LLMs, and instead we are vastly underestimating creative applications of current generation AI.
Agree. I think LLMs are usually not "harnessed" correctly for complex, multi-step problems—hence the `raink` CLI tool: https://github.com/noperator/raink
[deleted]
Re: Hard problems that reduce to document ranking
#28Earlier quoted context omitted.
In (Theoretical) Computer Science it is sometimes helpful to be able to say " Any instance of an A-type Problem can be transformed into an instance of a B-type Problem by applying this polynomial-time procedure". Say you have a problem that you know reasonably well (A-type) and another one that you're studying (B-type), intuitively, you'd say "If I transform B to A and I know the solution to A, then I solved B" but w…
Wikipedia: “Intuitively, problem A is reducible to problem B, if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently.” The article takes for granted that LLM-driven listwise comparisons efficiently solve document ranking (problem B), and then shows this can also be used as a subroutine to solve various hard problems like vulnerability analys…
Hmm, the discussion here requires a deeper understanding of these concepts, much deeper than a casual read of one sentence picked from Wikipedia.
I wouldn't have wrote that sentence to introduce people to reduction, because it misses a very important property of the operation that changes the whole thing. That sentence could lead you to think that reducing A There's a reason why the reduction equivalence classes form a preorder, as stated on the Wikipedia page you quoted.
Re: Hard problems that reduce to document ranking
#29Re: Hard problems that reduce to document ranking
#30Earlier quoted context omitted.
Wikipedia: “Intuitively, problem A is reducible to problem B, if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently.” The article takes for granted that LLM-driven listwise comparisons efficiently solve document ranking (problem B), and then shows this can also be used as a subroutine to solve various hard problems like vulnerability analys…
Hmm, the discussion here requires a deeper understanding of these concepts, much deeper than a casual read of one sentence picked from Wikipedia. I wouldn't have wrote that sentence to introduce people to reduction, because it misses a very important property of the operation that changes the whole thing. That sentence could lead you to think that reducing A There's a reason why the reduction equivalence classes form…
> When this is true, solving A cannot be harder than solving B. "Harder" means having a higher estimate of the required computational resources in a given context (e.g., higher time complexity, greater memory requirement, expensive need for extra hardware processor cores for a parallel solution compared to a single-threaded solution, etc.). The existence of a reduction from A to B can be written in the shorthand notation A ≤m B, usually with a subscript on the ≤ to indicate the type of reduction being used (m : mapping reduction, p : polynomial reduction).
The article indeed argues that solving n-day vulnerability discovery is no harder than document ranking. It does not argue that document ranking is no harder than n-day discovery, because it assumes that most people already would assume that; nor does it set out to disprove it.