Link to original article

Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Bounded complexity of solving ELK and its implications, published by Rubi on July 19, 2022 on The AI Alignment Forum. This post was written for the SERI MATS program. I thank Evan Hubinger and Leo Gao for their mentorship in the program. Further thanks go to Simon Marshall and Leo Gao (again) for specific comments regarding the content of this post. The Eliciting Latent Knowledge (ELK) problem was first introduced by Paul Christiano, Mark Xu, and Ajeya Cotra. Arguments concerning the complexity of solving the problem and the resulting consequences of that have been made by Abram Demski and Leo Gao. This post aims to synthesize their thoughts in an accessible way, and extend them with my own original content. I assume familiarity with the initial ELK report, but not with subsequent posts. Epistemic status: 90% confident that I am accurately representing the thoughts of Abram and Leo at the time they wrote their posts, 70% confident my own arguments do not contain major logical flaws. Introduction We would like to solve the Eliciting Latent Knowledge (ELK) problem in the worst case scenario, or at least show that the task is practically impossible so that we can revise our expectations. One of the worst cases for ELK is when the direct reporter is arbitrarily computationally complex. As this case would still allow for approximating the direct reporter within certain tolerances, we extend it further to when the direct reporter and all other sufficiently close approximation are arbitrarily computationally complex. While Paul Christiano has suggested that the complexity of the predictor bounds the complexity of the reporter, we will show later that this only holds in a narrow formulation of the ELK problem. Abram Demski argues in "ELK Computational Complexity: Three Levels of Difficulty" that if the direct reporter can be arbitrarily computationally complex, a training process to find it is intractable. To get around this issue, it is necessary to find an upper bound on computational complexity, conditional on the predictor, thus ruling out the worst case scenario. Leo Gao's post "Observations about ELK" focuses on a limited case of ELK and arrives at marginally more optimistic results, arguing that proposals which do not depend on the predictor are unable to find the direct translator in the worst case scenario, which rules out most current proposals but leaves open the possibility of a new approach that can somehow get around the issues. This point summarizes and expands on Abram’s and Leo’s posts regarding the possibility and implications of arbitrarily computationally complex direct reporters. I make the case that, under relatively minor assumptions, it is possible to bound the computational complexity of answering any particular question that has an answer. However, I then go on to show that Leo’s argument against the tractability of proposals not depending on the predictor continues to apply even when computational complexity is bounded. Question Nets In the ELK report, it is assumed that both the human and the AI make predictions by doing inference in a Bayes net. While this may not be literally true, it is a useful approximation because it is often the case that there is an analogous Bayes net for however the agent is modeling the world. This is especially likely to hold true for sufficiently advanced agents, such as a human or an AI that can model the world at a superhuman level, so the Bayes net analogy is a safe one to make. Once we acknowledge that doing inference in a Bayes net is only an analogy, we can stretch the analogy further. In particular, think of a human’s Bayes net as consisting exactly of a node for every question they could conceive to ask. The information contained at each of these question nodes is the human’s beliefs over the distribution of a...