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

Competitive Programming with AlphaCode

deepmind.com

Post reply on HN
Print view View original

291–300 of 415 posts

Re: Competitive Programming with AlphaCode

#291

Post by sytelus »

YeGoblynQueenne wrote: post #277
baobabKoodaa wrote: post #76

Earlier quoted context omitted.

The median rating is not descriptive of median ability, because a large number of Codeforces competitors only do one or a few competitions. A very small number of competitors hone their skills over multiple competitions. If we were to restrict our sample to competitors with more than 20 competitions, the median rating would be much higher than 1300. It's amazing that Alphacode achieved a 1300 rating, but compared to…

>> To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down. Sorry, but it's nothing of the sort. The approach is primitive, obsolete, and its results are very poor. I've posted this three times already but the arxiv preprint includes an evaluation against a formal benchmark dataset, APPS. On that more objective measure of performance, the best performing variant of AlphaCode teste…

Aren't you missing the point that even though success percentage is low, it is still same as estimated average human performance? So it is impressive the overall system (however cluncky it is) is indeed able to match human performance. If you don't find this impressive, do you have any other example of system that exceeds this performance?

Re: Competitive Programming with AlphaCode

#292

Post by Veedrac »

Jensson wrote: post #190
rfoo wrote: post #147

Earlier quoted context omitted.

1553D is a quite confusing case though. On the AlphaCode Attention Visualization website [1], the Accepted code shown for 1553D is a O(n^2) Python one, which is supposed to be TLE. It correctly implements a two-pointer solution, but failed to "realize" that list.pop(0) is O(n) in Python. I'm not sure how it passed. [1] https://alphacode.deepmind.com/#layer=30,problem=34,heads=11...

Likely the python runtime has a strange string implementation for cases like this, just like javascript strings.

It does not. Really the strings just never get long enough that O(n²) would be catastrophic; the maximum possible length is 2e5.

Re: Competitive Programming with AlphaCode

#293

Post by YeGoblynQueenne »

sytelus wrote: post #291
YeGoblynQueenne wrote: post #277

Earlier quoted context omitted.

>> To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down. Sorry, but it's nothing of the sort. The approach is primitive, obsolete, and its results are very poor. I've posted this three times already but the arxiv preprint includes an evaluation against a formal benchmark dataset, APPS. On that more objective measure of performance, the best performing variant of AlphaCode teste…

Aren't you missing the point that even though success percentage is low, it is still same as estimated average human performance? So it is impressive the overall system (however cluncky it is) is indeed able to match human performance. If you don't find this impressive, do you have any other example of system that exceeds this performance?

To clarify, the low percentage of 25% of correct solutions is on the APPS dataset, not against human coders. See table 10 (page 21 of the pdf) on the arxiv paper if you are unsure about the difference:

https://storage.googleapis.com/deepmind-media/AlphaCode/comp...

Evaluation against the average competitor on Codeforces is not the "estimated average human performance", it's only the average of the coders on Codeforce who are an unknown proportion of all human coders with an unknowable level of coding ability. So evaluating against that is actually a pretty meaningless metric.

The benchmarking against APPS is much more meaningful but the results are pretty poor and so they are omitted from the article above.

So, no. I'm not missing the point. Rather, the article above is eliding the point: which is that on the one meaningful evluation they attempted, their system sucks.

Edit: Here's table 10, for quick reference:

                       Filtered From (k)  Attempts (k)  Introductory  Interview  Competition
                                                        n@k           n@k        n@k
  GPT-Neo 2.7B         N/A                1             3.90%         0.57%      0.00%
  GPT-Neo 2.7B         N/A                5             5.50%         0.80%      0.00%
  Codex 12B            N/A                1             4.14%         0.14%      0.02%
  Codex 12B            N/A                5             9.65%         0.51%      0.09%
  Codex 12B            N/A                1000          25.02%        3.70%      3.23%
  Codex 12B            1000               1             22.78%        2.64%      3.04%
  Codex 12B            1000               5             24.52%        3.23%      3.08%
  AlphaCode 1B         N/A                1000          17.67%        5.24%      7.06%
  AlphaCode 1B         1000               5             14.36%        5.63%      4.58%
  AlphaCode 1B         10000              5             18.18%        8.21%      6.65%
  AlphaCode 1B         50000              5             20.36%        9.66%      7.75%
And its caption:

Table 10 | n@k results on APPS. If there is no filtering, then n = k and the metric is pass@k. Finetuned GPT-Neo numbers reported from Hendrycks et al. (2021), Codex numbers from Chen et al. (2021). We used a time limit of 3 seconds per test to match Codex 12B, and report average numbers over 3 different fine-tuning runs for AlphaCode.

Edit 2: And now that I posted this, I note that the 25% solutions are from Codex. AlphaCode's best result was 20%.

Re: Competitive Programming with AlphaCode

#294

Post by Veedrac »

YeGoblynQueenne wrote: post #277
baobabKoodaa wrote: post #76

Earlier quoted context omitted.

The median rating is not descriptive of median ability, because a large number of Codeforces competitors only do one or a few competitions. A very small number of competitors hone their skills over multiple competitions. If we were to restrict our sample to competitors with more than 20 competitions, the median rating would be much higher than 1300. It's amazing that Alphacode achieved a 1300 rating, but compared to…

>> To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down. Sorry, but it's nothing of the sort. The approach is primitive, obsolete, and its results are very poor. I've posted this three times already but the arxiv preprint includes an evaluation against a formal benchmark dataset, APPS. On that more objective measure of performance, the best performing variant of AlphaCode teste…

The APPS benchmark was for a “small 1B parameter model”, fine-tuned “without using clustering, tags, ratings, value conditioning, or prediction”.

> Overall, that's a brute-force, almost random approach that is ignoring entire decades of program synthesis work.

You don't get answers to these questions by random search. Not even close. I have looked at non-neural program synthesis papers. It is not remotely competitive.

Re: Competitive Programming with AlphaCode

#295

Post by lugu »

buscoquadnary wrote: post #119
qualudeheart wrote: post #90

Calling it now: If current language models can solve competitive programming at an average human level, we’re only a decade or less off from competitive programming being as solved as Go or Chess. Deepmind or openAI will do it. If not them, it will be a Chinese research group on par with them. I’ll be considering a new career. It will still be in computer science but it won’t be writing a lot of code. There’ll be sev…

The problem is this view continues to view software engineers as people that write code, that's not what my job is, it is figuring out how to solve a business problem using technology, and getting people on board with that solution and updating and refining it. This viewpoint seems to me to be very similar to the idea of 3rd generation languages replacing developers because programming will be so easy, it isn't about…

If I am given the ability to produce a program by formalizing the fuzzy requirements I am given, I will not hesitate to abuse this option. I can see a future where there is be a "market" for specifications to be composed together.

Analyzing the requirements is a hard problem when we do it with our brain. But our job would be very different if all we had to do it to write down the constraints, and press a button to see an error: invalid requirements, can't support this and that at the same time.

Re: Competitive Programming with AlphaCode

#296

Post by [deleted] »

Veedrac wrote: post #294
YeGoblynQueenne wrote: post #277

Earlier quoted context omitted.

>> To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down. Sorry, but it's nothing of the sort. The approach is primitive, obsolete, and its results are very poor. I've posted this three times already but the arxiv preprint includes an evaluation against a formal benchmark dataset, APPS. On that more objective measure of performance, the best performing variant of AlphaCode teste…

The APPS benchmark was for a “small 1B parameter model”, fine-tuned “without using clustering, tags, ratings, value conditioning, or prediction”. > Overall, that's a brute-force, almost random approach that is ignoring entire decades of program synthesis work. You don't get answers to these questions by random search. Not even close. I have looked at non-neural program synthesis papers. It is not remotely competitive…

[deleted]

Re: Competitive Programming with AlphaCode

#297

Post by YeGoblynQueenne »

Veedrac wrote: post #294
YeGoblynQueenne wrote: post #277

Earlier quoted context omitted.

>> To clarify, this is a HUGE leap in AI and computing in general. I don't mean to play it down. Sorry, but it's nothing of the sort. The approach is primitive, obsolete, and its results are very poor. I've posted this three times already but the arxiv preprint includes an evaluation against a formal benchmark dataset, APPS. On that more objective measure of performance, the best performing variant of AlphaCode teste…

The APPS benchmark was for a “small 1B parameter model”, fine-tuned “without using clustering, tags, ratings, value conditioning, or prediction”. > Overall, that's a brute-force, almost random approach that is ignoring entire decades of program synthesis work. You don't get answers to these questions by random search. Not even close. I have looked at non-neural program synthesis papers. It is not remotely competitive…

Yes, apparently they couldn't use their full approach because "of missing information in the dataset". That points to a further limitation of the approach: it works for Codeforces problems but not for APPS problems (so it's very purpose-specific).

Btw, APPS is not much of a benchmark. It evaluates code generation according to how close it resembles code written by humans. That's standard fare for text generation benchmarks, like evaluating machine translation on some arbitrary set of human translations. There are no good benchmarks for text generation (and there are no good metrics either).

But the comparison against the average competitor on Codeforces is even more meaningless because we have no way to know what is the true coding ability of that average competitor.

Re: Competitive Programming with AlphaCode

#298

Post by plutonorm »

briga wrote: post #280
FiberBundle wrote: post #217

It never ceases to amaze me what you can do with these transformer models. They created millions of potential solutions for each problem, used the provided examples for the problems to filter out 99% of incorrect solutions and then applied some more heuristics and the 10 available submissions to try to find a solution. All these approaches just seem like brute-force approaches: Let's just throw our transformer on thi…

Another way to frame it is that these models still perform very poorly at the task they're designed to do. Imagine if real programmer needed to write a solution a hundred times before they were able to achieve (average) performance. You'd probably wonder if it was just blind luck that got them to the solution. You'd also fire them. What these models are very good at doing is plagiarizing content, so part of me wonder…

How do you know the inner workings of the mind don't operate in a similar manner? How many different solutions to the problem are constructed within your mind before the correct one 'just arrives'?

Re: Competitive Programming with AlphaCode

#299

Post by aduitsis »

EVa5I7bHFq9mnYK wrote: post #210
mirrorlake wrote: post #88

I've been wondering this for a while: In the future, code-writing AI could be tasked with generating the most reliable and/or optimized code to pass your unit tests. Human programmers will decide what we want the software to do, make sure that we find all the edge cases and define as many unit tests as possible, and let the AI write significant portions of the product. Not only that, but you could include benchmarks…

It seems to me that writing an exhausting set of unit cases is harder than writing the actual code.

Otherwise the AI will just over-fit the unit test case subset.

Re: Competitive Programming with AlphaCode

#300

Post by Veedrac »

YeGoblynQueenne wrote: post #297
Veedrac wrote: post #294

Earlier quoted context omitted.

The APPS benchmark was for a “small 1B parameter model”, fine-tuned “without using clustering, tags, ratings, value conditioning, or prediction”. > Overall, that's a brute-force, almost random approach that is ignoring entire decades of program synthesis work. You don't get answers to these questions by random search. Not even close. I have looked at non-neural program synthesis papers. It is not remotely competitive…

Yes, apparently they couldn't use their full approach because "of missing information in the dataset". That points to a further limitation of the approach: it works for Codeforces problems but not for APPS problems (so it's very purpose-specific). Btw, APPS is not much of a benchmark. It evaluates code generation according to how close it resembles code written by humans. That's standard fare for text generation benc…

> Btw, APPS is not much of a benchmark. It evaluates code generation according to how close it resembles code written by humans.

No, the metric used in this paper was the percentage of questions it could solve against the hidden tests.

> That points to a further limitation of the approach: it works for Codeforces problems but not for APPS problems (so it's very purpose-specific).

This does not matter typically since you'd just pretrain on the data that works. However, “[t]he CodeContests training set has a non-empty intersection with the APPS test set, and therefore CodeContests cannot be used during training when evaluating on the APPS benchmark.” This is purely an evaluation issue; leakage doesn't matter so much in production.

Post reply on HN