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

41–50 of 57 posts

Re: Hard problems that reduce to document ranking

#41

Post by jasonjmcghee »

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.

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?

Re: Hard problems that reduce to document ranking

#42

Post by jasonjmcghee »

I see in the readme you investigated tournament style, but didn't see results.

How'd it perform compared to listwise?

Also curious about whether you tried schema-based querying to the llm (function calling / structured output). I recently tried to have a discussion about this exact topic with someone who posted about pairwise ranking with llms.

https://lobste.rs/s/yxlisx/llm_sort_sort_input_lines_semanti...

Re: Hard problems that reduce to document ranking

#43

Post by barrenko »

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.

Currently we are using mllms like lego blocks to build lego-powered-like devices.

Re: Hard problems that reduce to document ranking

#44

Post by riwsky »

moralestapia wrote: post #31
riwsky wrote: post #30

Earlier quoted context omitted.

> 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 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 turn every nday problem into a docrank problem, and every docrank solution into an nday solution, but does not say anything about whether we can turn docrank problems into nday problems, or nday solutions into docrank solutions.

Re: Hard problems that reduce to document ranking

#45

Post by bubblyworld »

moralestapia wrote: post #35
bubblyworld wrote: post #34

Earlier quoted context omitted.

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.

It's standard terminology. I'm not going to waste time arguing about it.

Re: Hard problems that reduce to document ranking

#46

Post by adamkhakhar »

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

"does Diff A fix Vuln B" is not the ranking solution proposed by the author. the ranking set-up is the same as the embedding case.

Re: Hard problems that reduce to document ranking

#47

Post by [deleted] »

moralestapia wrote: post #35
bubblyworld wrote: post #34

Earlier quoted context omitted.

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.

[deleted]

Re: Hard problems that reduce to document ranking

#48

Post by iamnotempacc »

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

Are you trolling or what. Let's see what's written in the comment above.

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

Here we say that that we can solve a "hard problem" if we can express it in terms of the "Document Ranking" problem.

Let's rewrite that quoted sentence:

An algorithm implementing "Document Ranking" can be used (with some pre- and post-processing) to solve "Hard problem".

Let's do substitution in the first part of the sentence, "If A reduces to B", where A is "hard problem" and B is "Document Ranking":

Hard problem reduces to Document Ranking.

That means EXACTLY that we can USE Document Ranking to SOLVE the Hard Problem. Just as we wanted.

Re: Hard problems that reduce to document ranking

#49

Post by moralestapia »

bubblyworld wrote: post #45
moralestapia wrote: post #35

Earlier quoted context omitted.

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

It's standard terminology. I'm not going to waste time arguing about it.

Define what's an oracle for you, that's a concept that's not even needed for this discussion.

I don't think you understand what is being talked about here.

Re: Hard problems that reduce to document ranking

#50

Post by moralestapia »

iamnotempacc wrote: post #48
moralestapia wrote: post #39

Earlier quoted context omitted.

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

Are you trolling or what. Let's see what's written in the comment above. > If A reduces to B, it means that an algorithm implementing B can be used (with some pre- and post-processing) to solve A. Here we say that that we can solve a "hard problem" if we can express it in terms of the "Document Ranking" problem. Let's rewrite that quoted sentence: An algorithm implementing "Document Ranking" can be used (with some pr…

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

moralestapia: If I transform B to A and I know the solution to A, then I solved B.

Ar-Curunir: If A reduces to B, it means that B is at least as hard as A.

moralestapia: [...] B is at least as complex as A

Can you even read?

Post reply on HN