Andrew Chi-Chih Yao
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Andrew Chi-Chih Yao has a total of 40 co-authors. Here are the top co-authors by number of shared publications:
- Yuan Yang
Southeast University
6 shared publications Chao Li
3 shared publications- Yunlei Zhao
Fudan University, Shanghai, China
3 shared publications - Frances F. Yao
City University of Hong Kong
2 shared publications - Jianlong Chen
The Chinese University of Hong Kong Shenzhen
2 shared publications - Xiaoming Sun
Institute of Computing Technology
2 shared publications
Latest Publications
- Open Access
Clarifying Before Reasoning: A Coq Prover with Structural Context
In this work, we investigate whether improving task clarity can enhance reasoning ability of large language models, focusing on theorem proving in Coq. We introduce a concept-level metric to evaluate task clarity and show that adding structured semantic context to the standard input used by modern LLMs, leads to a 1.85$\times$ improvement in clarity score (44.5\%~$\rightarrow$~82.3\%). Using the general-purpose model \texttt{DeepSeek-V3}, our approach leads to a 2.1$\times$ improvement in proof success (21.8\%~$\rightarrow$~45.8\%) and outperforms the previous state-of-the-art \texttt{Graph2Tac} (33.2\%). We evaluate this on 1,386 theorems randomly sampled from 15 standard Coq packages, following the same evaluation protocol as \texttt{Graph2Tac}. Furthermore, fine-tuning smaller models on our structured data can achieve even higher performance (48.6\%). Our method uses selective concept unfolding to enrich task descriptions, and employs a Planner--Executor architecture. These findings highlight the value of structured task representations in bridging the gap between understanding and reasoning.
Open AccessClarifying Before Reasoning: A Coq Prover with Structural Context
In this work, we investigate whether improving task clarity can enhance reasoning ability of large language models, focusing on theorem proving in Coq. We introduce a concept-level metric to evaluate task clarity and show that adding structured semantic context to the standard input used by modern LLMs, leads to a 1.85$\times$ improvement in clarity score (44.5\%~$\rightarrow$~82.3\%). Using the general-purpose model \texttt{DeepSeek-V3}, our approach leads to a 2.1$\times$ improvement in proof success (21.8\%~$\rightarrow$~45.8\%) and outperforms the previous state-of-the-art \texttt{Graph2Tac} (33.2\%). We evaluate this on 1,386 theorems randomly sampled from 15 standard Coq packages, following the same evaluation protocol as \texttt{Graph2Tac}. Furthermore, fine-tuning smaller models on our structured data can achieve even higher performance (48.6\%). Our method uses selective concept unfolding to enrich task descriptions, and employs a Planner--Executor architecture. These findings highlight the value of structured task representations in bridging the gap between understanding and reasoning.
- Open Access
Existing LLMs Are Not Self-Consistent For Simple Tasks
Large Language Models (LLMs) have grown increasingly powerful, yet ensuring their decisions remain transparent and trustworthy requires self-consistency -- no contradictions in their internal reasoning. Our study reveals that even on simple tasks, such as comparing points on a line or a plane, or reasoning in a family tree, all smaller models are highly inconsistent, and even state-of-the-art models like DeepSeek-R1 and GPT-o4-mini are not fully self-consistent. To quantify and mitigate these inconsistencies, we introduce inconsistency metrics and propose two automated methods -- a graph-based and an energy-based approach. While these fixes provide partial improvements, they also highlight the complexity and importance of self-consistency in building more reliable and interpretable AI. The code and data are available at https://github.com/scorpio-nova/llm-self-consistency.
Open AccessExisting LLMs Are Not Self-Consistent For Simple Tasks
Large Language Models (LLMs) have grown increasingly powerful, yet ensuring their decisions remain transparent and trustworthy requires self-consistency -- no contradictions in their internal reasoning. Our study reveals that even on simple tasks, such as comparing points on a line or a plane, or reasoning in a family tree, all smaller models are highly inconsistent, and even state-of-the-art models like DeepSeek-R1 and GPT-o4-mini are not fully self-consistent. To quantify and mitigate these inconsistencies, we introduce inconsistency metrics and propose two automated methods -- a graph-based and an energy-based approach. While these fixes provide partial improvements, they also highlight the complexity and importance of self-consistency in building more reliable and interpretable AI. The code and data are available at https://github.com/scorpio-nova/llm-self-consistency.
- Open Access
Hierarchical Attention Generates Better Proofs
Large language models (LLMs) have shown promise in formal theorem proving, but their token-level processing often fails to capture the inherent hierarchical nature of mathematical proofs. We introduce \textbf{Hierarchical Attention}, a regularization method that aligns LLMs' attention mechanisms with mathematical reasoning structures. Our approach establishes a five-level hierarchy from foundational elements to high-level concepts, ensuring structured information flow in proof generation. Experiments demonstrate that our method improves proof success rates by 2.05\% on miniF2F and 1.69\% on ProofNet while reducing proof complexity by 23.81\% and 16.50\% respectively. The code is available at https://github.com/Car-pe/HAGBP.
Open AccessHierarchical Attention Generates Better Proofs
Large language models (LLMs) have shown promise in formal theorem proving, but their token-level processing often fails to capture the inherent hierarchical nature of mathematical proofs. We introduce \textbf{Hierarchical Attention}, a regularization method that aligns LLMs' attention mechanisms with mathematical reasoning structures. Our approach establishes a five-level hierarchy from foundational elements to high-level concepts, ensuring structured information flow in proof generation. Experiments demonstrate that our method improves proof success rates by 2.05\% on miniF2F and 1.69\% on ProofNet while reducing proof complexity by 23.81\% and 16.50\% respectively. The code is available at https://github.com/Car-pe/HAGBP.
- Top Cited PapersOpen Access
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (23) , 24605-24613
Augmenting Math Word Problems via Iterative Question Composing
Despite the advancements in large language models (LLMs) for mathematical reasoning, solving competition-level math problems remains a significant challenge, especially for open-source LLMs without external tools. We introduce the MMIQC dataset, comprising a mixture of processed web data and synthetic question-response pairs, aimed at enhancing the mathematical reasoning capabilities of base language models. Models fine-tuned on MMIQC consistently surpass their counterparts in performance on the MATH benchmark across various model sizes. Notably, Qwen-72B-MMIQC achieves a 45.0% accuracy, exceeding the previous open-source state-of-the-art by 8.2% and outperforming the initial version GPT-4 released in 2023. Extensive evaluation results on Hungarian high school finals suggest that such improvement can generalize to unseen data. Our ablation study on MMIQC reveals that a large part of the improvement can be attributed to our novel augmentation method, Iterative Question Composing (IQC), which involves iteratively composing new questions from seed problems using an LLM and applying rejection sampling through another LLM.
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (23) , 24605-24613
Top Cited PapersOpen AccessAugmenting Math Word Problems via Iterative Question Composing
Despite the advancements in large language models (LLMs) for mathematical reasoning, solving competition-level math problems remains a significant challenge, especially for open-source LLMs without external tools. We introduce the MMIQC dataset, comprising a mixture of processed web data and synthetic question-response pairs, aimed at enhancing the mathematical reasoning capabilities of base language models. Models fine-tuned on MMIQC consistently surpass their counterparts in performance on the MATH benchmark across various model sizes. Notably, Qwen-72B-MMIQC achieves a 45.0% accuracy, exceeding the previous open-source state-of-the-art by 8.2% and outperforming the initial version GPT-4 released in 2023. Extensive evaluation results on Hungarian high school finals suggest that such improvement can generalize to unseen data. Our ablation study on MMIQC reveals that a large part of the improvement can be attributed to our novel augmentation method, Iterative Question Composing (IQC), which involves iteratively composing new questions from seed problems using an LLM and applying rejection sampling through another LLM.
- Open Access
- 1 January 2025
- Published by Association for Computational Linguistics (ACL)
- p. 4168-4189
Autonomous Data Selection with Zero-shot Generative Classifiers for Mathematical Texts
Yifan Zhang, Yifan Luo, Yang Yuan, Andrew C Yao. Findings of the Association for Computational Linguistics: ACL 2025. 2025.
- 1 January 2025
- Published by Association for Computational Linguistics (ACL)
- p. 4168-4189
Open AccessAutonomous Data Selection with Zero-shot Generative Classifiers for Mathematical Texts
Yifan Zhang, Yifan Luo, Yang Yuan, Andrew C Yao. Findings of the Association for Computational Linguistics: ACL 2025. 2025.
- Open Access
- 1 January 2025
- Published by Association for Computational Linguistics (ACL)
- p. 17506-17520
Hierarchical Attention Generates Better Proofs
Jianlong Chen, Chao Li, Yang Yuan, Andrew C Yao. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.
- 1 January 2025
- Published by Association for Computational Linguistics (ACL)
- p. 17506-17520
Open AccessHierarchical Attention Generates Better Proofs
Jianlong Chen, Chao Li, Yang Yuan, Andrew C Yao. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.
- Open Access
Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression
One of the major open problems in machine learning is to characterize generalization in the overparameterized regime, where most traditional generalization bounds become inconsistent even for overparameterized linear regression. In many scenarios, this failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. This paper demonstrate that the generalization behavior of overparameterized model should be analyzed in a both data-relevant and algorithm-relevant manner. To make a formal characterization, We introduce a notion called data-algorithm compatibility, which considers the generalization behavior of the entire data-dependent training trajectory, instead of traditional last-iterate analysis. We validate our claim by studying the setting of solving overparameterized linear regression with gradient descent. Specifically, we perform a data-dependent trajectory analysis and derive a sufficient condition for compatibility in such a setting. Our theoretical results demonstrate that if we take early stopping iterates into consideration, generalization can hold with significantly weaker restrictions on the problem instance than the previous last-iterate analysis.
Open AccessTowards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression
One of the major open problems in machine learning is to characterize generalization in the overparameterized regime, where most traditional generalization bounds become inconsistent even for overparameterized linear regression. In many scenarios, this failure can be attributed to obscuring the crucial interplay between the training algorithm and the underlying data distribution. This paper demonstrate that the generalization behavior of overparameterized model should be analyzed in a both data-relevant and algorithm-relevant manner. To make a formal characterization, We introduce a notion called data-algorithm compatibility, which considers the generalization behavior of the entire data-dependent training trajectory, instead of traditional last-iterate analysis. We validate our claim by studying the setting of solving overparameterized linear regression with gradient descent. Specifically, we perform a data-dependent trajectory analysis and derive a sufficient condition for compatibility in such a setting. Our theoretical results demonstrate that if we take early stopping iterates into consideration, generalization can hold with significantly weaker restrictions on the problem instance than the previous last-iterate analysis.
- 11 August 2022
- Published by Taylor & Francis in Climate Policy
- Vol. 22 (9-10) , 1333-1342
An authenticated and secure accounting system for international emissions trading
Expanding the international emissions trading system is crucial to filling the existing mitigation gap for the 2°C climate target. Trustworthy emissions accounting is the cornerstone of such a system encompassing different jurisdictions. However, traditional emissions measuring, reporting, and verification, as well as data disclosure practices that support data authenticity in a regional emissions trading system, might not be compatible with data transparency requirements in a future international system that covers countries with gaps in governance and social trust. This transparency requirement can cause severe data security concerns. In this study, we propose a cryptographic framework for an authenticated and secure emissions accounting system that can resolve this dilemma. We demonstrate that integrating a sequence of cryptographic protocols can preserve data authenticity and security for a stylized multi-country emissions trading system. We call for more research to promote joint work by policy researchers and computer scientists to strengthen collaboration in future international climate governance. Key policy insights
- 11 August 2022
- Published by Taylor & Francis in Climate Policy
- Vol. 22 (9-10) , 1333-1342
An authenticated and secure accounting system for international emissions trading
Expanding the international emissions trading system is crucial to filling the existing mitigation gap for the 2°C climate target. Trustworthy emissions accounting is the cornerstone of such a system encompassing different jurisdictions. However, traditional emissions measuring, reporting, and verification, as well as data disclosure practices that support data authenticity in a regional emissions trading system, might not be compatible with data transparency requirements in a future international system that covers countries with gaps in governance and social trust. This transparency requirement can cause severe data security concerns. In this study, we propose a cryptographic framework for an authenticated and secure emissions accounting system that can resolve this dilemma. We demonstrate that integrating a sequence of cryptographic protocols can preserve data authenticity and security for a stylized multi-country emissions trading system. We call for more research to promote joint work by policy researchers and computer scientists to strengthen collaboration in future international climate governance. Key policy insights
- 10 June 2022
- Published by Springer Nature in Science China Information Sciences
- Vol. 65 (7) , 1-2
Perspectives from the second Global Forum on Development of Computer Science
- 10 June 2022
- Published by Springer Nature in Science China Information Sciences
- Vol. 65 (7) , 1-2
Perspectives from the second Global Forum on Development of Computer Science