<p>I'm not aware of any such research.  I'm familiar with two standard datasets for evaluating the effectiveness of LLMs at solving math problems: GSM8K (Cobbe et al, arXiv:2110.14168) and MATH (Hendrycks et al, arxiv:2103.03874). I suspect any research of this sort might cite one of those two papers, so you could hop on Google Scholar to find all papers that cite one of those two and check for any that use PCP/ECC.</p>
<p>The blog post mentions as its key motivation the limited context window of LLMs.  But modern LLMs have a much larger context window, and expanding the context window is not the hard part.  So that might not be the most compelling motivation; I suspect a more compelling motivation would be if PCP-style proofs allow one to be resilient to the LLM being error-prone.</p>
<p>I suspect the bigger challenge is: what is the accuracy of LLMs at generating decent candidate proofs?  what is their accuracy at checking each step of a candidate proof?  Those sound like empirical questions, that I imagine will in turn influence whether a PCP-style approach is useful in practice.</p>
<p>I imagine that one challenge with using LLMs with PCP-style proofs might lie in generating candidate proofs that are written in a PCP style.  Most proofs found on the web are written in natural style, not PCP style.  LLMs are best at generating text that is similar to that found on the web.  Therefore, I'm not sure whether current LLMs will be any good at generating candidate PCP-style proofs.</p>
<p>We are just starting to see research on using LLMs to solve math problems step-by-step and on checking each step.  See, e.g., <a href="https://arxiv.org/abs/2305.20050" rel="nofollow noreferrer">Let's Verify Step by Step</a> (Lightman et al), which trains a verifier LLM to check each step of a math proof to see whether that step is correct, uses a generator LLM to generate many candidate proofs, and uses the verifier LLM to see if any of the candidate proofs appear to be correct (in every step).  It is not clear to me whether the limiting bottleneck in this approach is the ability to accurately verify each step; or the ability to generate candidate proofs.  If the verifier LLM is not very accurate, I'm not sure whether a PCP-structured proof will be helpful.</p>

CC BY-SA 4.0
2023-12-15T23:48:48.667Z
2023-12-15T23:48:48.667Z
D.W.
<p>Are there any interesting results in applying error correcting codes and ideas from PCP (Probabilistically Checkable Proofs) to improve the quality of large language models (LLM), or connecting them to &quot;Chain of Thought&quot;?</p>
<p>It seems a very natural idea, and others have also thought about it as well (e.g. see <a href="https://windowsontheory.org/2023/01/03/memento-and-large-language-models/" rel="nofollow noreferrer">this blog post</a> by Boaz).</p>
<p>I did a Google search but couldn't find anything useful.</p>

<cc.complexity-theory><machine-learning><coding-theory><pcp>
Application of PCP and error correcting codes to LLMs?
Kaveh
# Application of PCP and error correcting codes to LLMs?

(Asked by: username_0 on 2023-12-15)

Are there any interesting results in applying error correcting codes and ideas from PCP (Probabilistically Checkable Proofs) to improve the quality of large language models (LLM), or connecting them to "Chain of Thought"?

It seems a very natural idea, and others have also thought about it as well (e.g. see [this blog post](https://windowsontheory.org/2023/01/03/memento-and-large-language-models/) by Boaz).

I did a Google search but couldn't find anything useful.

**Tags:** cc.complexity-theory, machine-learning, coding-theory, pcp


---

## 1 answers

### Answer by username_1 on 2023-12-15. Score: 2

I'm not aware of any such research. I'm familiar with two standard datasets for evaluating the effectiveness of LLMs at solving math problems: GSM8K (Cobbe et al, arXiv:2110.14168) and MATH (Hendrycks et al, arxiv:2103.03874). I suspect any research of this sort might cite one of those two papers, so you could hop on Google Scholar to find all papers that cite one of those two and check for any that use PCP/ECC.

The blog post mentions as its key motivation the limited context window of LLMs. But modern LLMs have a much larger context window, and expanding the context window is not the hard part. So that might not be the most compelling motivation; I suspect a more compelling motivation would be if PCP-style proofs allow one to be resilient to the LLM being error-prone.

I suspect the bigger challenge is: what is the accuracy of LLMs at generating decent candidate proofs? what is their accuracy at checking each step of a candidate proof? Those sound like empirical questions, that I imagine will in turn influence whether a PCP-style approach is useful in practice.

I imagine that one challenge with using LLMs with PCP-style proofs might lie in generating candidate proofs that are written in a PCP style. Most proofs found on the web are written in natural style, not PCP style. LLMs are best at generating text that is similar to that found on the web. Therefore, I'm not sure whether current LLMs will be any good at generating candidate PCP-style proofs.

We are just starting to see research on using LLMs to solve math problems step-by-step and on checking each step. See, e.g., [Let's Verify Step by Step](https://arxiv.org/abs/2305.20050) (Lightman et al), which trains a verifier LLM to check each step of a math proof to see whether that step is correct, uses a generator LLM to generate many candidate proofs, and uses the verifier LLM to see if any of the candidate proofs appear to be correct (in every step). It is not clear to me whether the limiting bottleneck in this approach is the ability to accurately verify each step; or the ability to generate candidate proofs. If the verifier LLM is not very accurate, I'm not sure whether a PCP-structured proof will be helpful.


---

