Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hard problems that reduce to document ranking

noperator.dev

Post reply on HN
Print view View original

31–40 of 57 posts

Re: Hard problems that reduce to document ranking

#31

Post by moralestapia »

riwsky wrote: post #30
moralestapia wrote: post #28

Earlier quoted context omitted.

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 nota…

To be honest, even the article is not a formal attempt at proving all of this, nor does it have to, it's a bit of a conjecture, but anyway.

My reasoning goes along this line, which of the following two sentences you think is more likely to be true?

A. All n-day vulnerability discovery problems can be mapped to a document rerank problem.

or

B. Some n-day vulnerability discovery problems can be mapped to a document rerank problem.

I lean towards B, without any proof for it. Hence why I think the correct way is to reduce reranks into n-days (and all the other "hard problems").

If you think A is true, you still have to show that all reranks can be reduced to n-days, to be rigorous and able to say that your proposed algorithm works in both domains.

In the end it could be that both alternatives are equivalent, but it's easier to just say "reranks can be reduced to n-days" and because of this "some n-days can be adequately solved by my algorithm that works in reranks".

Re: Hard problems that reduce to document ranking

#33

Post by janalsncm »

panarky wrote: post #17
adamkhakhar wrote: post #16

I'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).

You can learn a function that embeds diffs with vulnerability A near each other, and vulnerability B near each other, etc which is much more efficient than asking an LLM about hundreds of chunks one at a time.

Maybe you even use the LLM to find vulnerable snippets at the beginning, but a multi class classifier or embedding model will be way better at runtime.

Re: Hard problems that reduce to document ranking

#34

Post by bubblyworld »

moralestapia wrote: post #15

Minor nitpick, Should be "document ranking reduces to these hard problems", I never knew why the convention was like that, it seems backwards to me as well, but that's how it is.

Not quite - in complexity theory you say problem A reduces to problem B if an oracle for problem B can be used to solve problem A. So the title of the article is correct, as an oracle for document ranking (LLMs in this case) can be used to solve a list of hard problems (given in the article).

Re: Hard problems that reduce to document ranking

#35

Post by moralestapia »

bubblyworld wrote: post #34
moralestapia wrote: post #15

Minor nitpick, Should be "document ranking reduces to these hard problems", I never knew why the convention was like that, it seems backwards to me as well, but that's how it is.

Not quite - in complexity theory you say problem A reduces to problem B if an oracle for problem B can be used to solve problem A. So the title of the article is correct, as an oracle for document ranking (LLMs in this case) can be used to solve a list of hard problems (given in the article).

Wrong.

At least bother to read the discussion in the sibling comments.

Re: Hard problems that reduce to document ranking

#37

Post by crazygringo »

hexator wrote: post #12

This 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.

Why not both?

The LLM companies work on the LLMs, while tens of thousands of startups and established companies work on applying what already exists.

It's not either/or.

Re: Hard problems that reduce to document ranking

#38

Post by Ar-Curunir »

moralestapia wrote: post #20
dwringer wrote: post #18

Earlier 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.

If A reduces to B, it means that an algorithm implementing B can be used (with some pre- and post-processing) to solve A.

If A reduces to B, it means that B is at least as hard as A.

This is the standard terminology in every theoretical computer science; see for example the DPV textbook on page 210: https://github.com/eherbold/berkeleytextbooks/blob/master/Al...

Re: Hard problems that reduce to document ranking

#39

Post by moralestapia »

Ar-Curunir wrote: post #38
moralestapia wrote: post #20

Earlier quoted context omitted.

I know its counterintuitive, as I explained in my comment, but that's the correct terminology in CS world.

If A reduces to B, it means that an algorithm implementing B can be used (with some pre- and post-processing) to solve A. If A reduces to B, it means that B is at least as hard as A. This is the standard terminology in every theoretical computer science; see for example the DPV textbook on page 210: https://github.com/eherbold/berkeleytextbooks/blob/master/Al...

Isn't that what I wrote on [1]?

Do you have something to add or is it just ... a confirmation?

Weird.

1: https://news.ycombinator.com/item?id=43179918

Re: Hard problems that reduce to document ranking

#40

Post by telotortium »

janalsncm wrote: post #33
panarky wrote: post #17

Earlier quoted context omitted.

Because the question "does Diff A fix Vuln B" is not answered by the cosine distance between vector(Diff A) and vector(Vuln B).

You can learn a function that embeds diffs with vulnerability A near each other, and vulnerability B near each other, etc which is much more efficient than asking an LLM about hundreds of chunks one at a time. Maybe you even use the LLM to find vulnerable snippets at the beginning, but a multi class classifier or embedding model will be way better at runtime.

Perhaps you can learn such a function, but it may be hard to learn a suitable embedding space directly, so it makes sense to lean on the more general capabilities of an LLM model (perhaps fine-tuned and distilled for more efficiency).
Post reply on HN