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

51–57 of 57 posts

Re: Hard problems that reduce to document ranking

#51

Post by moralestapia »

riwsky wrote: post #44
moralestapia wrote: post #31

Earlier quoted context omitted.

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

Even if you believe B, that’s still not reducing document ranking to n-day vulnerability discovery; it’s “reducing some n-day discovery to document ranking”. A does not require demonstrating doc-rank problems map to n-day problems, since reduction isn’t required to be symmetric. Where you might be getting caught up is in the mapping of problems vs the mapping of solutions . “Nday reduces to docrank” implies we can tu…

>Even if you believe B, that’s still not reducing [...]

I agree.

>A does not require demonstrating doc-rank problems map to n-day problems

Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure.

>since reduction isn’t required to be symmetric

That's exactly my point. A I would choose to do "reduce rerank to n-day (and all others)", because it feels like it would be easier down the road, but also because one typically reduces the problem that one knows best (more general, known bounds solutions, etc...) into the one that you're studying. That's why I wrote "minor nitpick".

Think about the textbook example of 3-SAT and all other problems it reduces to: clique, vertex cover, independent set, ... one does not reduce these problems into 3-SAT, it's the other way around. That doesn't mean you couldn't, some of them may have an complete equivalences to 3-SAT, but it's just easier to work out everything if you go from 3-SAT to the rest. My argument is the same, rerank is the thing that you reduce to all others.

Re: Hard problems that reduce to document ranking

#52

Post by Ar-Curunir »

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

Earlier quoted context omitted.

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

No, that is not what you wrote. You wrote “document ranking reduces to these hard problems", which means that document ranking can be solved with an algorithm for one of those hard problems. The article discusses the opposite: those hard problems can be solved by using algorithms for document ranking (which is itself a non-trivial problem)

Re: Hard problems that reduce to document ranking

#53

Post by janalsncm »

jasonjmcghee wrote: post #41
janalsncm wrote: post #33

Earlier quoted context omitted.

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.

I've thought about this and am very interested in this problem. Specifically, how can you efficiently come up with a kernel function that maps a "classic" embedding space to answer a specific ranking problem? With enough data, you could train a classic ml model, or you could keep the llm in the inference pipeline, but is there another way?

The typical methods would be

1. Train an embedding model which forces “similar” inputs close together using triplet loss. Here “similar” can mean anything, but you would probably want to mark similar vulnerabilities as being similar.

2. If you have a fixed set of N vulnerabilities you can train a multi class classifier. Of course it’s a pain in the ass to add a new class later on.

3. For any particular vulnerability you could train a ranking model using hinge loss. This is what most industrial ranking and recommendation systems do.

Re: Hard problems that reduce to document ranking

#54

Post by janalsncm »

telotortium wrote: post #40
janalsncm wrote: post #33

Earlier quoted context omitted.

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

In principle, there is no reason why an LLM should be able to do better than a more focused model, and a lot of reasons why it will be worse. You’re wasting a ton of parameters memorizing the capital of France and what the powerhouse of a cell is.

If data is the issue you can probably even generate vulnerabilities to create a synthetic dataset.

Re: Hard problems that reduce to document ranking

#55

Post by riwsky »

moralestapia wrote: post #51
riwsky wrote: post #44

Earlier quoted context omitted.

Even if you believe B, that’s still not reducing document ranking to n-day vulnerability discovery; it’s “reducing some n-day discovery to document ranking”. A does not require demonstrating doc-rank problems map to n-day problems, since reduction isn’t required to be symmetric. Where you might be getting caught up is in the mapping of problems vs the mapping of solutions . “Nday reduces to docrank” implies we can tu…

>Even if you believe B, that’s still not reducing [...] I agree. >A does not require demonstrating doc-rank problems map to n-day problems Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure. >since reduction isn’t required to be symmetric That's exactly my point. A I would choose to do "reduce rerank to n-day (and all others)",…

> >A does not require demonstrating doc-rank problems map to n-day problems > Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure.

But the article isn’t mapping docrank to nday, nor is it claiming to reduce docrank to nday. Its choice of A and B is clear.

Nday didn’t have an understood solution to leverage like docrank did.

> one typically reduces the problem that one knows best (more general, known bounds solutions, etc...) into the one that you're studying

Wikipedia: “”” There are two main situations where we need to use reductions:

First, we find ourselves trying to solve a problem that is similar to a problem we've already solved. In these cases, often a quick way of solving the new problem is to transform each instance of the new problem into instances of the old problem, solve these using our existing solution, and then use these to obtain our final solution. This is perhaps the most obvious use of reductions. “””

This is what the article does, reducing the new nday problem into the known docrank one.

“”” Second: suppose we have a problem that we've proven is hard to solve, and we have a similar new problem. We might suspect that it is also hard to solve. We argue by contradiction: suppose the new problem is easy to solve. Then, if we can show that every instance of the old problem can be solved easily by transforming it into instances of the new problem and solving those, we have a contradiction. This establishes that the new problem is also hard. “””

This is your ‘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’. “Nday discovery is at least as complicated as document ranking” is obvious, though, which is why it’s not the subject of a blog post.

Re: Hard problems that reduce to document ranking

#56

Post by moralestapia »

riwsky wrote: post #55
moralestapia wrote: post #51

Earlier quoted context omitted.

>Even if you believe B, that’s still not reducing [...] I agree. >A does not require demonstrating doc-rank problems map to n-day problems Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure. >since reduction isn’t required to be symmetric That's exactly my point. A I would choose to do "reduce rerank to n-day (and all others)",…

> >A does not require demonstrating doc-rank problems map to n-day problems > Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure. But the article isn’t mapping docrank to nday, nor is it claiming to reduce docrank to nday. Its choice of A and B is clear. Nday didn’t have an understood solution to leverage like docrank did. > on…

>Nday didn’t have an understood solution to leverage like docrank did.

Hence why you do docrank reduced to n-day. You typically map known into unknown. That's the point I'm trying to make.

I'm not saying the alternative is wrong, though, it's just not what one usually does.

(btw, even though this format makes everything look confrontative, I'm actually enjoying this thread a lot :D)

Re: Hard problems that reduce to document ranking

#57

Post by riwsky »

moralestapia wrote: post #56
riwsky wrote: post #55

Earlier quoted context omitted.

> >A does not require demonstrating doc-rank problems map to n-day problems > Of course you have to, that's pretty much the whole operation of reducing A to B. You may be doing it implicitly but you're doing it for sure. But the article isn’t mapping docrank to nday, nor is it claiming to reduce docrank to nday. Its choice of A and B is clear. Nday didn’t have an understood solution to leverage like docrank did. > on…

>Nday didn’t have an understood solution to leverage like docrank did. Hence why you do docrank reduced to n-day. You typically map known into unknown. That's the point I'm trying to make. I'm not saying the alternative is wrong, though, it's just not what one usually does. (btw, even though this format makes everything look confrontative, I'm actually enjoying this thread a lot :D)

"can map A to B, solve B, and use that to solve A" establishes the pre-order A ≤ B; you seem to pronounce "A ≤ B" as "B reduces to A", which indeed lines up with the wikipedia page for preorders in general—"when a≤b, one may say that b covers a or that a precedes b or that b reduces to a"—but compsci pronounces that the other way around, as per the Reduction (complexity) wiki page: "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)". As inelegant as the discrepancy may be, the compsci conjugation is much more common than the category-theoretic one, and this is a programming forum. Just think of it like an irregular verb.
Post reply on HN